A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Spectral graph algorithms use eigenvalues and eigenvectors of graph-associated matrices (adjacency matrix, Laplacian) to solve graph problems. The graph Laplacian L = D - A (degree matrix minus adjacency matrix) has eigenvalues 0 = lambda_1 <= lambda_2 <= ... <= lambda_n, where the multiplicity of zero equals the number of connected components and lambda_2 (the algebraic connectivity or Fiedler value) measures how well-connected the graph is. The Fiedler vector (eigenvector for lambda_2) provides a spectral bisection that approximates the minimum ratio cut within a Cheeger-inequality factor of sqrt(lambda_2). Spectral methods yield near-linear time algorithms for graph partitioning, Laplacian system solving (Spielman-Teng), and effective resistance computation, with applications in machine learning (spectral clustering), network analysis, and scientific computing.
Every graph has a matrix representation, and the eigenvalues of that matrix encode global structural properties. The graph Laplacian L = D - A is the most important such matrix. Its eigenvalues are all nonnegative (L is positive semidefinite), and the pattern of small eigenvalues reveals the graph's large-scale connectivity structure. Zero eigenvalues correspond to connected components; near-zero eigenvalues indicate bottlenecks (subsets connected by few edges relative to their size).
The Cheeger inequality makes this correspondence quantitative. It relates the second-smallest Laplacian eigenvalue lambda_2 to the edge expansion h(G) — the minimum ratio of cut edges to subset size. Specifically, lambda_2/2 <= h(G) <= sqrt(2*lambda_2). This means spectral methods cannot find the exact minimum cut (the lower bound has a square root), but they provide a useful relaxation that is computable in polynomial time. The Fiedler vector — the eigenvector for lambda_2 — assigns each vertex a real number reflecting its "position" in the graph's connectivity structure, and sweep cuts based on this vector find near-optimal partitions.
Spectral methods extend naturally to multiple clusters via k-way partitioning. The first k eigenvectors of the Laplacian embed each vertex in Rk, where vertices in the same cluster are mapped close together and vertices in different clusters are mapped far apart. Running k-means in this embedding gives spectral clustering, which is both practical (widely used in machine learning and network analysis) and theoretically grounded (provable recovery under stochastic block models). The eigengap lambda_k - lambda_{k+1} predicts how cleanly the clusters separate in the spectral embedding.
The computational frontier is Laplacian system solving. The Spielman-Teng breakthrough showed that Lx = b can be solved in nearly linear time using a multilevel preconditioner built from graph sparsifiers. This has cascading algorithmic consequences: maximum flow algorithms based on interior point methods reduce each iteration to a Laplacian solve, yielding near-linear time max-flow algorithms (Kelner et al., 2014). Effective resistances, random spanning tree generation, and graph sparsification itself all reduce to Laplacian solving. The near-linear time Laplacian solver is becoming the universal subroutine for graph algorithms, much as FFT is for signal processing.