PrivParts

PrivParts is the implementation accompanying PrivParts: A Scalable Offstream Vertex Partitioner that Minimizes Cross-Partition Exposure of Sensitive Data. It is a privacy-aware vertex partitioner for large graphs: vertices are assigned to exactly one partition, while an edge incident to at least one privacy vertex is a privacy edge. The primary privacy metric is the privacy cut ratio (PCR), the fraction of privacy edges that cross partitions.

The implementation follows the paper's two-stage architecture:

1. Input graph splitter. Privacy vertices and their one-hop neighbors are admitted to the offline subgraph first. Remaining capacity admits high-degree regular vertices together with their neighborhoods.
2. Multilevel-P offline stage. The offline subgraph is partitioned with a METIS-compatible backend, with optional privacy clustering, privacy-weighted edges, simulated-annealing initialization, and PBOFM refinement.
3. Stateful PFennel streaming stage. Vertices outside the offline subgraph are placed incrementally. The offline assignments seed the partition state; PFennel's privacy score is active only for privacy vertices.

The repository contains a public Fuzhou medical example, focused experiment drivers, and an evaluation utility. Large benchmark inputs and generated artifacts stay outside version control.

Repository Layout

privparts/
  include/       Graph, splitter, and privacy-coarsening interfaces
  src/           PrivParts executable and offline/streaming implementation
tools/           Batch privacy-cut evaluator for edge-list inputs
examples/        Public Fuzhou medical example and local-data documentation
experiments/     Paper-oriented stage and component ablation drivers
results/         Local experiment artifacts; ignored by git

See docs/PAPER_CODE_MAP.md for a direct mapping from the paper's components and metrics to source files and options.

Dependencies

• CMake 3.10 or newer
• A C++17 compiler
• An offline graph partitioning backend installed on the system

For very large graphs, use a backend build with 64-bit vertex and edge indices.

Build

cmake -S . -B build \
  -DCMAKE_BUILD_TYPE=Release \
  -DPRIVPARTS_PARTITIONER_ROOT=/path/to/backend-install
cmake --build build --parallel

The build produces the privparts executable in build/privparts/. It also builds privacy_cut_edgelist_batch in the same directory. OpenMP is used by the evaluator when the compiler provides it.

If the backend is installed in a standard system path, the root option can be omitted:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel

Some backend installations keep GKlib symbols in a separate source tree or library. If linking reports unresolved gk_* symbols, provide the GKlib source directory as well:

cmake -S . -B build \
  -DCMAKE_BUILD_TYPE=Release \
  -DPRIVPARTS_PARTITIONER_ROOT=/path/to/backend-install \
  -DPRIVPARTS_GKLIB_SOURCE_DIR=/path/to/GKlib
cmake --build build --parallel

Input Data

Graph datasets should be placed under examples/ locally. They are ignored by git because the benchmark graphs used in the experiments are large.

PrivParts accepts a text graph format with a header and adjacency lists:

n m ew has_privacy
vid privacy_flag nbr1 nbr2 ...   # when has_privacy=1
vid nbr1 nbr2 ...                # when has_privacy=0

Vertex ids and neighbor ids are 1-based. A separate privacy file can also be provided with one private vertex id per line.

Internally, PrivParts stores the graph in a compact CSR structure:

struct PrivPartsGraph {
  int64_t n;              // number of vertices
  int64_t m;              // undirected edge count from the input header
  int ew;                 // edge-weight flag; currently must be 0
  int has_privacy;        // whether privacy flags are embedded in the graph file
  vector<idx_t> xadj;     // CSR offsets, size n + 1
  vector<idx_t> adjncy;   // 0-based neighbor ids
  vector<int> privacy;    // privacy flag per vertex, size n
};

The loader converts all vertex ids from the 1-based input format to 0-based internal indices. Self-loops are ignored. Duplicate edges are not removed in the loader, so benchmark inputs should already be deduplicated. For large graphs, the loader builds CSR in two passes: the first pass computes vertex degrees and xadj, and the second pass fills adjncy.

See examples/README.md for the recommended local data layout.

Example

./build/privparts/privparts examples/my_dataset/my_dataset_privparts_0.2 \
  --k 8 \
  --out results/my_dataset.privparts.k8.partition \
  --max_memory_gb 16 \
  --privacy_file examples/my_dataset/my_dataset_privacy_0.2 \
  --offline_coarsen privacy_cluster \
  --offline_init sa \
  --offline_refine_mode pbofm \
  --stream_state_layer offline

The output partition file contains one line per vertex:

vid privacy_flag part

Run ./build/privparts/privparts --help for the full option set.

Reproduce the Public Smoke Test

The checked-in Fuzhou medical example supports a small end-to-end run:

(cd build && ctest --output-on-failure)

Or run it manually and keep an auditable command and log:

mkdir -p results/fuzhou_smoke
./build/privparts/privparts \
  examples/fuzhou_medical/fuzhou_medical_privparts_0.2 \
  --k 8 \
  --out results/fuzhou_smoke/partition.txt \
  --max_memory_gb 0.02 \
  --tau_p 0.2 \
  --offline_coarsen privacy_cluster \
  --offline_init sa \
  --offline_sa_rounds 1 \
  --offline_refine_passes 1 \
  --offline_seed 1 \
  --offline_refine_seed 1 \
  > results/fuzhou_smoke/console.log 2>&1

The final Run summary: line is machine-readable and includes balance, cut_ratio, privacy_cut_ratio, memory use, and phase-level timings.

Experiment Drivers

The scripts under experiments/ preserve every invocation in cmd.sh, write the complete console log, and collect parsed CSV summaries:

• run_four_mode_ablation_5seeds.sh: paper Table 2 stage ablation over five seeds: Full, w/o offline, w/o state layer, and w/o streaming.
• run_four_mode_ablation.sh: single-seed version of the stage ablation.
• run_three_mode_comparison.sh: compares offline-only, state-layer, and cold-start streaming paths.
• run_fuzhou_ablation.sh and run_fb_dblp_ablation.sh: component ablations for privacy clustering, PBOFM, SA initialization, PFennel privacy scoring, and the state layer.

The Facebook/DBLP scripts deliberately reference local benchmark paths from the original experiment environment. Edit their dataset arguments before use on a different machine.

Metrics

PrivParts reports the following full-graph metrics:

• LB: max_partition_size / ceil(|V| / k).
• CR: cut / |E|.
• PCR: privacy_cut / |E_privacy|, where E_privacy contains every edge with at least one privacy endpoint.

The privacy_cut_edgelist_batch helper evaluates multiple partitions and privacy sets in one pass over an edge-list graph. It accepts both generic two-column <vertex_id> <part_id> partition maps and the three-column <vertex_id> <privacy_flag> <part_id> files produced by PrivParts:

./build/privparts/privacy_cut_edgelist_batch \
  --edges examples/my_dataset/my_dataset.txt \
  --partmap 8 results/my_dataset.privparts.k8.partition \
  --privacy 0.2 examples/my_dataset/my_dataset_privacy_0.2 \
  --out results/my_dataset.privacy_cut.csv

An edge (u, v) is counted as a privacy cut when part[u] != part[v] and at least one endpoint is private.

Notes For Large Graphs

• Keep datasets, generated partitions, logs, and CSV result files outside git.
• Use 64-bit index builds for billion-edge graphs.
• Expect the offline stage to dominate runtime and memory when the private subgraph is large.

License

See LICENSE.