Spectral Clustering

K-means clustering assumes clusters look like round blobs centred somewhere, which fails badly on data shaped like two interlocking spirals or two concentric rings — no straight-line distance-to-a-centre rule can separate them. Spectral clustering solves this not by inventing a fancier distance rule but by first re-describing the data in a completely different coordinate system, one where the awkward shapes straighten out and plain k-means suddenly works.

The analogy: untangling a knotted necklace by its connections

Picture a tangled necklace where nearby beads are connected by thread, and you want to identify separate strands without being fooled by how the whole thing is coiled up in a box. Looking only at raw 3D position is useless — a bead from one strand can be physically closer to a bead from a different strand than to its own neighbour, because the necklace is coiled. But if you instead ask "which beads are directly connected by thread," and use that connectivity to figure out layout, the true strands become obvious. Spectral clustering builds exactly this connectivity graph between data points, then re-lays them out using the graph's structure rather than their raw coordinates.

The maths: graph, Laplacian, eigenvectors

First build a similarity graph: connect each point to its nearby neighbours, weighted by how similar they are (often via an RBF-style kernel). This gives an adjacency matrix $W$ and a degree matrix $D$ (each diagonal entry is how connected that point is overall). The graph Laplacian is

$$L = D - W$$

In words: $L$ encodes how much each point differs from its neighbourhood average — it is small where connections are strong and consistent, and it is the object whose structure reveals natural groupings. The key move is computing the eigenvectors of $L$ corresponding to its smallest eigenvalues, and using the first $k$ of them as new coordinates for each point — each original data point gets re-plotted using these eigenvector values instead of its original features. Ordinary k-means is then run on these new coordinates.

$$L v = \lambda v$$

Here $v$ is an eigenvector and $\lambda$ its eigenvalue. In words: eigenvectors of $L$ with small eigenvalues correspond to directions along which the graph varies smoothly within a cluster but sharply between clusters — exactly the axis you'd want to cluster along, and one that raw coordinates never provided.

Worked example 1: two rings, why raw distance fails

Two concentric rings of points, inner ring radius 1, outer ring radius 5. A point at the top of the inner ring $(0,1)$ and a point at the top of the outer ring $(0,5)$ are only distance $4$ apart — closer than that inner-ring point is to a point on the opposite side of its own ring, at $(0,-1)$, distance $2$... actually closer, but consider a point at $(1,0)$ on the inner ring versus $(0,5)$ on the outer: distance $\sqrt{1+25}\approx5.1$, while $(1,0)$ to $(0,1)$, both inner ring, is $\sqrt2 \approx 1.4$. K-means mostly survives on this simple case, but shrink the ring gap and it fails: raw Euclidean distance simply doesn't track "which ring." Spectral clustering instead connects each point only to its handful of nearest neighbours — a point on the inner ring connects only to other nearby inner-ring points, never to the outer ring, however close in raw distance a fluke pairing might be. The resulting graph has two nearly disconnected pieces, one per ring, and the Laplacian's eigenvectors reflect that split cleanly.

Worked example 2: a tiny graph by hand

Four points, two clearly-connected pairs: $A$–$B$ (similarity 1) and $C$–$D$ (similarity 1), with only a faint cross-link $B$–$C$ (similarity 0.05). Degree matrix diagonal: $A=1, B=1.05, C=1.05, D=1$. The Laplacian $L = D - W$ has mostly-zero off-diagonal entries except the strong $A$–$B$ and $C$–$D$ links and the tiny $B$–$C$ one. Its second-smallest eigenvector (the one used for 2-cluster splits) will assign nearly opposite-signed values to $\{A,B\}$ versus $\{C,D\}$, because that's the split that requires cutting only the weak $0.05$ link rather than a strong $1$-weight one — the eigenvector is, in effect, finding the cheapest possible cut through the graph.

The explorer above shows eigenvectors as the directions a linear transformation doesn't rotate — spectral clustering uses the Laplacian's eigenvectors the same way, as the natural axes along which the graph's structure is best described.

Compare a rigid boundary to a flexible one in the explorer above: spectral clustering's whole purpose is producing boundaries as flexible as the ring or spiral example, which a distance-based method like plain k-means cannot draw.

What this means in practice

Spectral clustering suits data with non-convex, intertwined, or graph-structured cluster shapes — grouping assets by a correlation network rather than raw return distance, or clustering entities connected through a transaction graph. It costs more than k-means: building the similarity graph and its eigenvectors scales poorly with the number of points, typically limiting practical use to thousands rather than millions of points without approximations.