Spectral Clustering

Spectral Graph Theory & Laplacian Clustering

Spectral clustering uses eigenvectors of the graph Laplacian to find natural communities. The Laplacian L = D − A (degree matrix minus adjacency matrix) encodes graph connectivity.

L = D − A | L_sym = D^(-1/2) L D^(-1/2)

Fiedler vector: 2nd eigenvector of L (smallest non-zero eigenvalue)

For k clusters: use eigenvectors v₂,...,v_{k+1} as feature rows, then k-means

The eigenvalue gap (spectral gap) reveals how many natural clusters exist. A graph with k disconnected components has exactly k zero eigenvalues. The Cheeger inequality bounds the cut: h_G ≤ √(2λ₂).

Spectral clustering is used in image segmentation, community detection, and manifold learning (Laplacian eigenmaps).