Graph partitioning

Deep dive

How it works

Parts:

• coarsener — heavy-edge matching and contraction, one level per round
• initial partitioner — greedy graph growing or recursive bisection on the coarsest graph
• projector — maps a partition one level back onto the finer graph
• refiner — Kernighan-Lin / Fiduccia-Mattheyses passes on the boundary, with bucket gains
• streaming assigner — LDG or Fennel rule that places each arriving vertex in one pass, without coarsening

Minimize cut = Σ w(u,v) over edges with part(u) ≠ part(v), subject to |P_i| ≤ (1+ε)·n/k.

1. Coarsen with heavy-edge matching: pair each vertex with the unmatched neighbour on its heaviest edge, contract pairs (sum weights, merge parallel edges). Heavy edges vanish inside super-vertices, so they are never cut.
2. Initial partition of the coarsest graph (greedy graph growing, recursive bisection; best of several tries).
3. Uncoarsen + refine: project the partition down one level, run Kernighan-Lin / Fiduccia-Mattheyses passes on the boundary.
4. FM pass (2 parts): gain(v) = external(v) − internal(v). Move the best unlocked, balance-feasible vertex, lock it, update neighbour gains; negative gains are allowed to escape local minima. Roll back to the best prefix. k-way: recursive bisection or direct k-way refinement.
5. Streaming: LDG (Stanton, Kliot) puts each arriving vertex in argmax_i |N(v) ∩ P_i| · (1 − |P_i|/C); Fennel (Tsourakakis et al.) trades neighbours against a convex size penalty.

G0 ─match─► G1 ─match─► ... Gm (≈ hundreds of vertices) ─► initial partition
 ▲ refine    ▲ refine                                          │
 └─ project ◄┴─ project ◄──────────────────────────────────────┘

Code

pub type Adj = Vec<Vec<u32>>;

pub fn edge_cut(adj: &Adj, part: &[u8]) -> usize {
    let mut c = 0;
    for (v, ns) in adj.iter().enumerate() {
        c += ns.iter().filter(|&&u| part[u as usize] != part[v]).count();
    }
    c / 2
}

/// Linear Deterministic Greedy: one pass over the vertex stream.
pub fn ldg(adj: &Adj, order: &[u32], k: usize, cap: usize) -> Vec<u8> {
    let mut part = vec![u8::MAX; adj.len()];
    let mut size = vec![0usize; k];
    let mut cnt = vec![0usize; k];
    for &v in order {
        cnt.iter_mut().for_each(|c| *c = 0);
        for &u in &adj[v as usize] {
            if part[u as usize] != u8::MAX { cnt[part[u as usize] as usize] += 1; }
        }
        let mut best = (f64::MIN, 0);
        for p in 0..k {
            if size[p] >= cap { continue; }
            let s = cnt[p] as f64 * (1.0 - size[p] as f64 / cap as f64);
            if s > best.0 || (s == best.0 && size[p] < size[best.1]) { best = (s, p); }
        }
        part[v as usize] = best.1 as u8;
        size[best.1] += 1;
    }
    part
}

/// One Fiduccia-Mattheyses pass for 2 parts; returns the cut reduction (>= 0).
pub fn fm_pass(adj: &Adj, part: &mut [u8], max_side: usize) -> i64 {
    let n = adj.len();
    let off = adj.iter().map(|a| a.len()).max().unwrap_or(0) as i64;
    let mut gain = vec![0i64; n];
    for v in 0..n {
        for &u in &adj[v] {
            gain[v] += if part[u as usize] != part[v] { 1 } else { -1 };
        }
    }
    // buckets[side][gain + off]: candidates to move out of `side`
    let mut b: [Vec<Vec<u32>>; 2] = [vec![vec![]; 2 * off as usize + 1], vec![vec![]; 2 * off as usize + 1]];
    let mut top = [0usize; 2];
    for v in 0..n {
        let (s, g) = (part[v] as usize, (gain[v] + off) as usize);
        b[s][g].push(v as u32);
        top[s] = top[s].max(g);
    }
    let mut size = [0usize; 2];
    part.iter().for_each(|&p| size[p as usize] += 1);
    let (mut locked, mut moves) = (vec![false; n], Vec::new());
    let (mut cum, mut best, mut best_len) = (0i64, 0i64, 0usize);
    loop {
        // best valid candidate per side; skip sides whose target is full
        let mut pick: Option<(usize, u32)> = None;
        for s in 0..2 {
            if size[1 - s] >= max_side { continue; }
            loop {
                match b[s][top[s]].last() {
                    Some(&v) if !locked[v as usize] && part[v as usize] as usize == s
                        && (gain[v as usize] + off) as usize == top[s] => {
                        if pick.map_or(true, |(_, p)| gain[v as usize] > gain[p as usize]) { pick = Some((s, v)); }
                        break;
                    }
                    Some(_) => { b[s][top[s]].pop(); } // stale entry
                    None if top[s] > 0 => top[s] -= 1,
                    None => break,
                }
            }
        }
        let Some((s, v)) = pick else { break };
        b[s][top[s]].pop();
        locked[v as usize] = true;
        cum += gain[v as usize];
        part[v as usize] = (1 - s) as u8;
        size[s] -= 1; size[1 - s] += 1;
        moves.push(v);
        for &u in &adj[v as usize] {
            let u = u as usize;
            if locked[u] { continue; }
            gain[u] += if part[u] == part[v as usize] { -2 } else { 2 };
            let (us, g) = (part[u] as usize, (gain[u] + off) as usize);
            b[us][g].push(u as u32);
            top[us] = top[us].max(g);
        }
        if cum > best { best = cum; best_len = moves.len(); }
    }
    for &v in &moves[best_len..] { part[v as usize] ^= 1; } // roll back past the best prefix
    best
}

ldg streams; fm_pass refines a 2-way partition (run it per V-cycle level). Weights omitted.

Complexity and constants

• FM pass: O(E) with bucket gains; KL without buckets is O(V²) per pass.
• Matching and contraction: O(E) per level; levels roughly halve the graph, so a V-cycle costs a small multiple of one finest-level pass.
• Memory: CSR is 4 B per directed edge plus 4-8 B per vertex; the partition is 1 B per vertex.
• Cost driver: part[u] for every neighbour u is a random access; once part leaves cache, each edge costs a miss, order of 5-50 ns.

Efficiency

Cost: Measured on an Apple M4 Pro, one thread: on a 200,000-vertex, 2.01 M-edge graph one LDG pass takes 34 ms and two FM passes about 250 ms; bound is cache misses. Each cut edge is one message per superstep and direction, so at an assumed 8 B per message the hash cut (1,005,697 edges) moves about 16 MB per superstep and the refined cut (10,000) about 0.16 MB.

Levers:

• Coarsening — FM works on graphs that fit in cache and moves whole super-vertices, escaping local minima (Karypis, Kumar 1998) — mesh-like and large graphs.
• Bucket gain structure — O(1) insert, update, max instead of heap or scan (Fiduccia, Mattheyses 1982) — small integer gains (unit weights); use a heap for wide weight ranges.
• BFS arrival order for streaming — 150,043 cut vs 759,261 with random order on the graph below (measured) — when you control the stream; see BFS/DFS.
• Boundary-only refinement — touch only vertices with a cross-part neighbour — once the partition is decent.
• Warm start — re-run FM from the previous partition instead of repartitioning — slowly changing graphs.

Naive → standard → state of the art:

• hash(v) mod k · no compute, cut about 50 % of edges at k=2 (measured: 1,005,697 of 2,009,974)
• multilevel heavy-edge matching + FM (METIS) · near-linear in E, the usual baseline
• KaHIP / Mt-KaHyPar (flow-based, evolutionary or multithreaded refinement) · better cut at more time

Test: planted two-cluster graph, k=2, 2 % imbalance (asserts: refined cut under a tenth of the hash cut; FM gain equals the real cut drop).

Implementation notes

• Use CSR for sequential scans; Vec<Vec<u32>> costs a pointer chase per vertex.
• Lazy deletion (push on gain change, skip stale on pop) avoids unlinking from buckets.
• Weight vertices by expected load, not 1, when shards are balanced by work.
• Restream: a second pass using the first assignment as neighbour hints improves the cut.

Pitfalls

• Power-law graphs: a hub cuts almost all its edges wherever it goes.
• Cut is not communication volume: 100 edges from one vertex into one part need one value if batched.
• The cut drifts as the graph grows; repartition with migration cost as a term.

Variants and alternatives

In production

Scientific computing: METIS and ParMETIS in finite-element solvers (domain decomposition, nested-dissection ordering); Scotch in HPC codes. Distributed graph processing: vertex-cut loaders in PowerGraph. Chip design: FM and multilevel hypergraph cuts in VLSI placement (hMETIS; Karypis et al. 1999). Databases: Schism partitions transactional workloads from a graph of co-accessed tuples (Curino et al. 2010).

Implementations

Sources

• G. Karypis, V. Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM J. Sci. Comput. 20(1), 1998. paper · code
• B. Kernighan, S. Lin, An Efficient Heuristic Procedure for Partitioning Graphs, Bell System Technical Journal 49(2), 1970. paper
• C. Fiduccia, R. Mattheyses, A Linear-Time Heuristic for Improving Network Partitions, DAC 1982. paper
• M. Garey, D. Johnson, L. Stockmeyer, Some Simplified NP-Complete Graph Problems, Theoretical Computer Science 1(3), 1976. paper
• I. Stanton, G. Kliot, Streaming Graph Partitioning for Large Distributed Graphs, KDD 2012. paper
• C. Tsourakakis, C. Gkantsidis, B. Radunovic, M. Vojnovic, FENNEL: Streaming Graph Partitioning for Massive Scale Graphs, WSDM 2014. paper
• J. Gonzalez, Y. Low, H. Gu, D. Bickson, C. Guestrin, PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs, OSDI 2012. paper
• P. Sanders, C. Schulz, Engineering Multilevel Graph Partitioning Algorithms, ESA 2011. paper · code
• L. Gottesbüren, T. Heuer, N. Maas, P. Sanders, S. Schlag, Scalable Shared-Memory Hypergraph Partitioning, ALENEX 2021. paper · code
• G. Karypis, R. Aggarwal, V. Kumar, S. Shekhar, Multilevel Hypergraph Partitioning: Applications in VLSI Domain, IEEE Transactions on VLSI Systems 7(1), 1999. paper
• C. Curino, E. Jones, Y. Zhang, S. Madden, Schism: a Workload-Driven Approach to Database Replication and Partitioning, PVLDB 3(1-2), 2010. paper