Cut a graph into its communities with a single eigenvector. Build the Laplacian L = D − A; its second-smallest eigenvalue is the algebraic connectivity, and the eigenvector that goes with it — the Fiedler vector — carries the split. The sign of each entry tells a vertex which side it is on. Down the center, data flows: a graph goes in, one eigenvector is chosen, the partition comes out. The blue team builds and defends it against brute force; the red team tries to break it.
source M. Fiedler, "Algebraic connectivity of graphs," Czech. Math. J. (1973); J. Shi & J. Malik, "Normalized Cuts and Image Segmentation," IEEE TPAMI 22(8):888–905 (2000) — DOI 10.1109/34.868688. Rendered, not quoted.
A vertex's side is not chosen; it falls out of the spectrum. Sort the Laplacian eigenvalues 0 = λ₁ ≤ λ₂ ≤ …. The eigenvector of λ₂ is the Fiedler vector v; assign vertex i to side − or side + by sign(vᵢ).
Live Fiedler vector on the current graph — value and the side its sign assigns:
| vertex | vᵢ | sign → side |
|---|
Fiedler (1973) named λ₂ the algebraic connectivity: it is 0 exactly when the graph falls apart, and it grows as the graph knits tighter. His deeper find was that its eigenvector orders the vertices — the first hint that a spectrum could cut a shape.
That is the second eigenvector of the-graph-laplacian. Shi & Malik turned it into image segmentation by normalizing the cut. Each sphere is the next one's premise: the Laplacian's spectrum here becomes a pair of scissors.
The blue team's live check: on the planted two-community graph, re-confirm that the Fiedler signs separate the communities exactly, that its cut equals the brute-force minimum balanced cut, and that λ₂ > 0. If red swaps the eigenvector, this badge is where it shows.
A graph of 8 vertices in two planted communities: A = {0,1,2,3} and B = {4,5,6,7}, each a tight clique (K₄), joined by a few bridge edges. This is the whole input to the panel: an adjacency matrix A, from which the degree matrix D and Laplacian L = D − A are built.
Toggle the bridges below to change how tightly the two halves are tied — watch λ₂ move.
Constructed graph: two cliques + the active bridges. Eigen-decomposition is exact (Jacobi rotations, residual < 1e-9).
side − side + cut edge
Laplacian spectrum (sorted). amber = λ₂, the Fiedler value:
The chosen eigenvector's entries (bar up = +, down = −):
Change any control — the Laplacian is rebuilt and re-diagonalized on the spot; the partition is read from the eigenvector's signs, never looked up.
What the machine produces, proven: on the constructed graph the Fiedler signs cut it into exactly {0,1,2,3} | {4,5,6,7} — the planted communities — with a cut of 1 edge, matching the brute-force minimum balanced cut over all 35 balanced splits, and λ₂ = 0.354249.
The blue witness (left) confirms these live; the red team (right) tries to make the split wrong.
And the cut it finds is a relaxation: min-cut is NP-hard, spectral clustering solves a real-valued surrogate, so the partition is near-optimal, not provably optimal. It also breaks on heterogeneous degrees — unnormalized cuts (ratio-cut) drift toward lopsided splits, which is exactly why Shi & Malik use the normalized cut. Assume none of this is free.
"The Fiedler vector gives the true minimum cut." Cut. It gives the minimizer of a relaxed objective; here it happens to match the brute-force min balanced cut — verified, not assumed.
"Any eigenvector will reveal the clusters." Cut. Only λ₂ does. The largest-eigenvalue vector is the highest-frequency mode — it oscillates within clusters. Window 6 proves it.
"λ₂ = 0 just means weakly connected." Kept, corrected. λ₂ = 0 iff the graph is disconnected; its multiplicity counts the connected components exactly.
The red team's move: cluster with the eigenvector of the largest eigenvalue — the highest-frequency mode — instead of the Fiedler vector. The blue team's witness (window 7) is watching.
Swap in the top eigenvector and its signs scramble the vertices across both communities — the partition no longer matches the planted split, the witness recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.