Spectral clustering: cluster by the graph Laplacian's eigenvectors, not by distance — non-convex shapes unfold into blobs

Plain k-means assigns every point to the nearest centroid, so the boundary between two clusters is always a straight line — and it fits convex blobs beautifully. But real structure is often non-convex: two crescent moons that interlock, a ring inside a ring. No set of centroids carves those apart, so k-means (and GMM's ellipses) split them straight down the middle and get it badly wrong. Spectral clustering sidesteps geometry entirely — it turns the data into a graph and reads the answer off the graph Laplacian's eigenvectors. I built a demo that runs the whole pipeline live in the browser. Here's what it taught me.

The similarity graph: k-NN + RBF affinity

Turn the cloud into a weighted graph. Connect each point only to its k nearest neighbours — so far-apart points on different moons are never linked directly — and weight each surviving edge by the RBF kernel, close = strong, far = weak. Symmetrize so the affinity matrix W is symmetric.

const w = Math.exp(-d2(pts[i], pts[j]) / (2 * sigma * sigma));  // RBF affinity
W[i][j] = W[j][i] = Math.max(W[i][j], w);                       // kNN, symmetric

The Laplacian L = D − W

The degree Dᵢ is the total edge weight at node i. The unnormalized Laplacian is L = D − W; the demo uses the normalized symmetric form L_sym = I − D^-½ W D^-½ (the Ng–Jordan–Weiss choice), which balances clusters of different densities. Its eigenvalues live in [0, 2], and the multiplicity of eigenvalue 0 equals the number of connected components.

L[i][j] = (i === j ? 1 : 0) - dinv[i] * W[i][j] * dinv[j];   // I − D^-½ W D^-½

The smallest eigenvectors embed the points

The whole method rests on the eigenvectors of the smallest eigenvalues. For a symmetric matrix the classic Jacobi rotation finds them all with no libraries — repeatedly zero the largest off-diagonal with a plane rotation Gᵀ L G, accumulate into V, and when the off-diagonals vanish the diagonal holds the eigenvalues and the columns of V the eigenvectors. Stack the k smallest as columns: row i is point i's new coordinate. Row-normalize each to unit length and the tangled shapes collapse into tight, well-separated clumps.

const T = pts.map((_, i) => {                 // row i = point i in spectral space
  const row = vectors.slice(0, k).map(v => v[i]);
  const nrm = Math.hypot(...row) || 1;
  return row.map(v => v / nrm);               // NJW row-normalize -> onto a sphere
});

k-means in spectral space, and the eigengap picks k

Run ordinary k-means in that spectral space and the non-convex mess that failed on raw coordinates is now trivially separable — that embedding is the whole trick made visible. And you don't have to guess the cluster count: a graph with c near-separate pieces has c near-zero eigenvalues, so the biggest eigengap — the jump after the k-th smallest eigenvalue — votes for k. Eigenvector #1 is the Fiedler vector, whose sign alone splits the graph in two before any k-means runs.

const gaps = eig.slice(1).map((v, i) => v - eig[i]);   // λ_{i+1} − λ_i
const k = gaps.indexOf(Math.max(...gaps)) + 1;         // biggest jump = cluster count

On the two-moons and concentric-circles datasets spectral hits ~100% while raw k-means sits near chance; switch to convex blobs and the two tie — spectral's edge shows up only where the clusters aren't round, which is exactly the sanity check you want. The dense Jacobi solver here is O(n³), which is why the demo keeps N modest; in production you use a sparse k-NN graph and a Lanczos/ARPACK solver that returns only the few smallest eigenvectors — exactly what sklearn.cluster.SpectralClustering does under the hood.

The takeaway I now carry: when clusters aren't round blobs, stop measuring distance to centroids — build a similarity graph and let the Laplacian's spectrum unfold the shape for you.

Pick two moons, and watch spectral nail them at ~100% while k-means cleaves them in half:
https://dev48v.infy.uk/ml/day49-spectral-clustering.html