Spectral Graph Theory

Spectral Graph Drawing

Draw a graph using its Laplacian's eigenvectors as coordinates — and watch hidden communities fall into place.

Nodes start on a circle, then relax to (v₂, v₃) — their Laplacian-eigenvector coordinates. Colors mark the planted communities; the positions use no labels at all, only the spectrum.

What you're seeing

A graph has no inherent geometry — only nodes and edges. Spectral drawing invents coordinates for it from the Laplacian L = D − A (degree matrix minus adjacency). We take the eigenvectors belonging to its smallest nonzero eigenvalues — the Fiedler vector v₂ and the next, v₃ — and give node i the position (v₂[i], v₃[i]). Press play: the nodes leave their meaningless circle and settle into that layout, and the densely-connected communities pull apart into distinct blobs. The colors are the planted ground truth; the positions were computed without them.

The rule

L = D − A                       # graph Laplacian (D = degrees, A = adjacency)
solve for the eigenvectors of the smallest eigenvalues:
   v₁ = constant   (eigenvalue 0)        ← discarded
   v₂ = Fiedler vector
   v₃ = next eigenvector
position(i) = ( v₂[i], v₃[i] )

Here the eigenvectors come from dependency-free power iteration with deflation (the atlas's numlib), run on cI − L so that "smallest of L" becomes "largest of cI − L."

The invariant

The Fiedler vector is the answer to a crisp optimization. Among all coordinate assignments x that are centered (Σxᵢ = 0) and normalized, v₂ minimizes the total squared edge stretch Σ_(i~j) (xᵢ − xⱼ)² — which equals xᵀ L x, the Laplacian quadratic form. In words: place the nodes on a line so that edges are as short as possible without collapsing everything to a point. The minimizing placement is exactly the Fiedler vector, with value the second-smallest eigenvalue λ₂ (the graph's algebraic connectivity). Adding v₃ as a second axis gives the best 2-D version of the same principle. Because edges within a community vastly outnumber edges between them, "minimize edge stretch" forces each community into a tight cluster — which is why the spectrum reveals structure no one labeled. (This is also why v₂'s sign gives a good graph bipartition — see spectral partitioning.)

The cost

This demoAt scale Eigenvectorspower iterationLanczos / sparse MatrixO(n²) dense LO(edges) sparse

We use a small dense Laplacian and a few rounds of power iteration — fine for a few dozen nodes. Real graphs are huge and sparse, so production uses Lanczos / implicitly-restarted Arnoldi (ARPACK, SciPy's eigsh) that touch only the O(edges) nonzeros and never form a dense matrix. The algebraic connectivity λ₂ is the headline number: larger means harder to disconnect (better connected); near zero means a near-bottleneck the layout will stretch open.

In the wild

Spectral embeddings of the Laplacian are everywhere structure-from-connectivity matters. Spectral clustering (run k-means on the bottom eigenvectors) is a staple of machine learning for non-convex clusters. Graph-drawing and layout tools use it to seed force-directed layouts. Spectral partitioning bisects meshes and circuits for parallel computing and VLSI. And the same Laplacian eigenvectors are the discrete analog of vibration modes and heat diffusion on the graph — the bridge between graph theory and physics. It is the computational heart of an entire field, spectral graph theory, which reads a graph's structure off the numbers in its matrices.

Try this

Set Communities to 2 and the layout splits cleanly along one axis (the Fiedler vector alone). Raise it to 4 or 5 and watch the blobs arrange themselves in the plane. Each New graph is a fresh random graph with the same community structure — the layout finds it every time, because it's reading the connectivity, not a label.

References

  1. Fiedler, M. "Algebraic connectivity of graphs." Czechoslovak Mathematical Journal 23(2):298–305, 1973. The Fiedler vector.
  2. Spielman, D. Spectral and Algebraic Graph Theory (Yale) — Laplacians, the quadratic form xᵀLx, drawing graphs with eigenvectors. cs.yale.edu/homes/spielman/sagt.
  3. von Luxburg, U. "A tutorial on spectral clustering." Statistics and Computing 17(4):395–416, 2007.
  4. Andoni, A. Advanced Algorithms (Columbia COMS 4995-8, 2021), Lectures 13–16 (spectral graph theory; drawing graphs with the Laplacian). course materials.