parallel graph partitioning
**Parallel Graph Partitioning** is the **problem of dividing a graph's vertices into k roughly-equal-sized subsets (partitions) while minimizing the number of edges crossing partition boundaries (the edge cut)**, which is fundamental to distributing graph computations, mesh decomposition for scientific simulation, and circuit placement. High-quality partitioning directly determines distributed algorithm communication cost.
Graph partitioning is NP-hard in general, but practical multilevel heuristics achieve near-optimal results for most real-world graphs.
**Multilevel Partitioning Framework** (METIS, ParMETIS, KaHIP):
| Phase | Action | Purpose |
|-------|--------|---------|
| **Coarsening** | Repeatedly contract edges to create smaller graphs | Reduce problem size |
| **Initial partition** | Partition the small coarsened graph | Get starting solution |
| **Uncoarsening** | Project partition back through levels, refining at each | Improve quality |
**Coarsening**: Heavy-edge matching — greedily match vertices connected by heavy-weight edges and collapse them into single vertices. Each coarsening level roughly halves the graph. Continue until the graph has a few hundred vertices. Alternative: random matching, sorted heavy-edge matching, or algebraic multigrid-inspired coarsening.
**Initial Partitioning**: On the coarsest graph (small enough for exact or expensive heuristics). Methods: recursive bisection, spectral partitioning, or greedy growing from random seeds.
**Refinement**: At each uncoarsening level, apply local refinement to improve the cut. **Kernighan-Lin (KL)** / **Fiduccia-Mattheyses (FM)** algorithms: iteratively move vertices between partitions to maximize cut reduction while maintaining balance constraints. FM runs in O(|E|) per pass and is the standard refinement algorithm.
**Parallel Partitioning Challenges**: Distributed graphs may not fit in a single machine's memory. ParMETIS parallelizes each phase: parallel matching for coarsening, parallel refinement with boundary vertex exchange, and parallel initial partitioning. Communication overhead during refinement is proportional to the number of boundary vertices.
**Quality Metrics**: **Edge cut** (primary metric — fewer cross-partition edges = less communication); **balance** (max partition size / average partition size — target <1.03); **communication volume** (sum of unique boundary vertices per partition — may differ from edge cut for hypergraph/multi-constraint problems); and **partition connectivity** (number of different partitions each partition communicates with — affects message count).
**Applications**: **Distributed graph processing** (each machine processes one partition, communication proportional to edge cut); **FEM mesh decomposition** (load-balance computation while minimizing inter-processor data exchange); **VLSI circuit placement** (recursive bisection for min-cut placement); **sparse matrix partitioning** (row/column reordering for parallel SpMV); and **social network analysis** (community detection as graph partitioning).
**Streaming and Dynamic Partitioning**: For graphs too large to load or evolving over time: streaming algorithms assign vertices to partitions as they arrive (hash-based or balanced greedy), and dynamic repartitioning incrementally adjusts partitions as the graph changes.
**Graph partitioning is the foundational preprocessing step for virtually all distributed graph computation — the quality of the partition directly determines parallel efficiency, making it one of the most impactful algorithmic choices in large-scale graph processing.**