Spectral Graph Theory

Spectral Partitioning

Split a graph into two balanced, weakly-connected halves by sweeping a cut along the Fiedler vector — provably near-optimal.

Nodes are laid out by their Fiedler coordinate; the dashed line sweeps the cut. Blue/purple are the two sides; orange edges are cut by the current split.

What you're seeing

We want to split the graph into two sides while cutting as few edges as possible — but trivial splits (one node vs the rest) cut few edges yet are useless, so we measure quality by conductance φ(S) = (edges cut) / min(vol S, vol S̄), which punishes lopsided cuts. Brute-forcing all 2ⁿ splits is hopeless. Instead we order the nodes by their Fiedler-vector value (the x-axis), then sweep a single threshold left to right — only n−1 candidate cuts — and keep the one with the lowest conductance. Watch the dashed line sweep; the readout tracks the running best.

The rule

compute v = 2nd eigenvector of the normalized Laplacian (the Fiedler vector)
order nodes by v[i]
for each prefix S of that order:        # n−1 sweep cuts
    φ(S) = cut(S, S̄) / min(vol S, vol S̄)
return the prefix with the smallest φ

The invariant

The guarantee is Cheeger's inequality, the cornerstone of spectral graph theory. Let λ₂ be the second-smallest eigenvalue of the normalized Laplacian L = I − D^{−1/2} A D^{−1/2}, and φ_G the best conductance of any cut. Then λ₂/2 ≤ φ_G ≤ √(2λ₂). The lower bound says no cut can be much better than the spectrum predicts; the upper bound is constructive — the proof shows that some prefix of the Fiedler ordering achieves conductance ≤ √(2λ₂), which is exactly the sweep we run. So a cheap eigenvector plus a linear scan is provably within a quadratic factor of the optimum — and on this entry the readout shows the found φ* sitting inside the two bounds, every time. (Using the normalized Laplacian matters: the combinatorial one's eigenvalue does not obey Cheeger.)

The cost

Optimal cutSpectral sweep SearchNP-hard (exact)1 eigenvector + O(n) sweep Qualityφ_G≤ √(2λ₂)

Finding the minimum-conductance cut exactly is NP-hard; spectral partitioning trades exactness for a provable approximation at the cost of one eigenvector (here dense power iteration; at scale, sparse Lanczos). The sweep itself is a single sorted pass with an incrementally-maintained conductance.

In the wild

Spectral bisection is a classic tool for graph and mesh partitioning — dividing a finite-element mesh or sparse matrix across processors so each chunk is balanced and the boundary (communication) is small. It underlies image segmentation (Shi & Malik's normalized cuts), community detection in networks, and circuit placement in VLSI. Recursively applying it gives a multiway partition. Modern partitioners (METIS) often use multilevel heuristics, but spectral partitioning remains the method with a clean theoretical guarantee — and the bridge to the rest of spectral graph theory.

Try this

Turn Inter-cluster edges down: the two communities separate cleanly, λ₂ drops toward 0, and the best conductance plummets (an easy cut). Turn it up and the cut gets expensive, λ₂ rises, and the Cheeger band widens — watch φ* stay inside [λ₂/2, √(2λ₂)] the whole time.

References

  1. Cheeger, J. "A lower bound for the smallest eigenvalue of the Laplacian." Problems in Analysis, Princeton, 1970. (The continuous original; the discrete analog is standard.)
  2. Spielman, D. Spectral and Algebraic Graph Theory (Yale), the Cheeger-inequality lectures. cs.yale.edu/homes/spielman/sagt.
  3. Shi, J. & Malik, J. "Normalized cuts and image segmentation." IEEE TPAMI 22(8), 2000.
  4. Andoni, A. Advanced Algorithms (Columbia COMS 4995-8, 2021), Lecture 16 (Cheeger & spectral partitioning). course materials.