Graph Partitioning

Splitting a network into balanced, tightly knit groups while cutting as few ties as possible, trading cut size against piece size.

A four-node path cut in the middle scores NCut 0.67 while cutting off one end node scores 1.20, so balance picks the middle

Why Does This Exist?

Splitting decides placements: chips across dies, tasks across machines, users into cohorts, meshes across solvers. Every split wants two things that fight: few ties cut (cheap communication, clean communities) and balanced pieces (even load, meaningful groups). Optimizing cut size alone has a degenerate answer (peel off one node), and optimizing balance alone ignores the wiring. Partitioning is the bicriteria problem, and its relaxations are why spectra matter to systems. The cut object is the Laplacian, the relaxation is the spectral view, and the graph encoding is in fundamentals.

The one idea you need first

For pieces $A$ and $B$ , $\mathrm{cut}(A,B)$ counts crossing edges and $\mathrm{vol}(A)$ sums degrees inside. Normalized cut $\mathrm{NCut} = \mathrm{cut}(1/\mathrm{vol}(A) + 1/\mathrm{vol}(B))$ charges per unit volume, so tiny pieces pay dearly. Minimizing it exactly is hard; thresholding the Fiedler vector approximates it well.

Think of It Like This

Dividing a school into two teams

A principal splits 200 pupils into two houses minimizing broken friendships, with houses of equal size. Cutting one loner off alone breaks one friendship: the smallest cut possible, and a useless answer. The principal really wants few broken friendships per pupil housed, which sends the loner back inside and finds the genuine fault line (say, juniors versus seniors).

Spectral partitioning is that per-pupil accounting made into arithmetic: the Fiedler vector orders pupils along the weakest axis, and each possible split point prices its cut against its balance. The cheapest per-pupil split wins.

Where the analogy stops: real graphs weight edges, fix some nodes in place, and recurse to $k$ pieces with k-means on several eigenvectors rather than one threshold.

How It Actually Works

Objectives. Ratio cut divides by node counts, NCut by volumes. Both penalize splinters. Modularity (for community detection) compares inside-edges against a random null model instead of fixing $k$ .

Spectral relaxation. Encode a two-way split as signs $x_i \in \{+1,-1\}$ ; then $\mathrm{cut} \propto x^\top Lx$ . Relax signs to reals with norm and balance constraints, and the minimizer is the Fiedler vector. Threshold its signs (or sweep for the best NCut) to round back to a split. For $k$ pieces, embed rows of the first $k$ eigenvectors and k-means them, row-normalized.

Beyond spectral. Kernighan-Lin swaps across the cut, Louvain and Leiden greedily maximize modularity near-linearly, and multilevel schemes coarsen, split small, and refine. Spectral gives guarantees; greedy gives scale.

Worked example

Path $1 - 2 - 3 - 4$ with degrees $1, 2, 2, 1$ .

Middle cut $\{1,2\}\mid\{3,4\}$ : crosses edge $(2,3)$ only, so $\mathrm{cut} = 1$ . Volumes are $1+2 = 3$ each. $\mathrm{NCut} = 1/3 + 1/3 \approx 0.667$ .

End cut $\{1\}\mid\{2,3,4\}$ : crosses edge $(1,2)$ , $\mathrm{cut} = 1$ . Volumes $1$ versus $2+2+1 = 5$ . $\mathrm{NCut} = 1/1 + 1/5 = 1.20$ .

Same single edge cut, but the end slice scores nearly twice as bad: NCut prices the splinter. The Fiedler signs $(+,+,-,-)$ propose exactly the middle cut, which is why spectral rounding finds the balanced answer here.

Watch Out For

Minimizing raw cut and getting singletons

Unnormalized objectives (and code that forgets the volume denominators) return the cheapest edge set, which on real graphs is one low-degree node's ties. Recursing repeats the peel, producing a "clustering" of singletons plus one giant piece.

Symptom: cluster sizes like 1, 1, 2, 9996. Fix: always normalize (NCut or ratio cut), check size distributions before trusting quality scores, and prefer Leiden or Louvain when balance is a hard constraint rather than a wish.

Trusting one spectral split on noisy or multi-scale graphs

A single Fiedler threshold assumes two clean pieces at one scale. Overlapping communities, hierarchies, and heavy noise give flat spectra with no clear gap, and the returned split is an arbitrary rotation of a degenerate eigenspace.

Symptom: nearby $k$ values give unrelated answers, and the $\lambda_3 - \lambda_2$ gap sits near zero. Fix: inspect the eigengap before rounding, sweep $k$ with stability checks, and row-normalize eigenvector embeddings before k-means for $k > 2$ .

The Quick Version

Partitioning trades cut size against balance; NCut prices cuts per unit volume.
On the 4-path, middle cut NCut is 0.67 versus 1.20 for an end slice.
Spectral relaxation thresholds the Fiedler vector; $k$ -way uses k-means on eigenvectors.
Raw min-cut peels singletons: always normalize or constrain balance.
Greedy modularity methods scale where spectra cannot; check gaps before trusting one split.