spectral clustering

Spectral clustering finds groups in data by listening to the low frequencies of a graph. Build a graph where similar items are linked, then use a few eigenvectors of its Laplacian to place each item on a line or in a low-dimensional space, where well-separated groups become easy to see and easy to split.

The method: form a similarity graph and its Laplacian L, compute the eigenvectors for the smallest few eigenvalues (skipping the trivial all-ones one), stack them as columns to embed each node as a short vector, then run ordinary k-means on those vectors. The smallest eigenvectors are the smoothest labelings, the ones that change least across edges, so they respect the graph's natural seams.

Why it works is the Laplacian's quadratic form x^T L x = sum over edges (x_i - x_j)^2. Minimizing it under an orthogonality constraint is a relaxation of the NP-hard balanced minimum-cut problem; the eigenvectors are the continuous solution, and rounding them recovers a near-optimal cut. The second eigenvector, the Fiedler vector, gives the first two-way split.

Why it matters: spectral clustering captures non-convex, intertwined shapes that plain k-means in the raw space cannot, and it works on any data you can turn into a similarity graph. The caveats: results depend heavily on how you build the graph (the similarity kernel and its scale), and the eigendecomposition is costly for very large graphs without sparse or approximate methods.