The graph Laplacian L = D − W encodes connectivity. Its eigenvectors reveal cluster structure. The Fiedler vector (eigenvector of λ₂) partitions the graph by sign — the algebraic connectivity.
λ₂ = — (Fiedler value)
Spectral clustering (Shi-Malik 2000, Ng-Jordan-Weiss 2002): build similarity W_ij=exp(-||x_i-x_j||^2/2sigma^2), form normalized Laplacian L=I-D^{-1/2}WD^{-1/2}, take top k eigenvectors, run k-means on rows. Cheeger inequality: h(G)^2/2 le lambda_2 le 2h(G). Eigenvectors = slow modes of random walk on graph. Finds non-convex clusters k-means misses.