The Smallest Eigenvalues of a Graph Laplacian

spectral-graph-theoryclusteringeigenvaluesgraph-laplacianmachine-learning

Abstraction: Graph Laplacian eigenvalues zero and second-smallest enable spectral clustering and partitioning

Key points:

Graph Laplacian L = D − A; eigenvalue 0 has multiplicity k iff the graph has exactly k connected components, with eigenvectors that identify which vertices belong to each component
Spectral clustering: build a k-NN graph from data points, compute Laplacian eigendecomposition, keep first k eigenvector columns, feed to k-means — handles non-convex cluster shapes by capturing manifold structure
Second smallest eigenvalue λ₁ (Fiedler value, named after Miroslav Fiedler) measures algebraic connectivity; λ₁ = 0 means graph is disconnected
Fiedler vector (eigenvector of λ₁) provides graph bisection: assign +1 or −1 to each vertex by sign of the vector component to minimize cut edges while keeping balanced partitions
Continuous Fiedler vector values can be thresholded at the median or mean to produce hard assignments
Performance of spectral clustering depends heavily on graph construction quality; a too-large k producing a fully connected graph yields poor results

Connections: Miroslav Fiedler · Spectral Clustering · Graph Laplacian · Eigenvalues