Spectral Clustering

Graph Laplacian eigenvectors reveal non-convex cluster structure

Blobs Concentric Rings Two Moons Spiral k=2 k=3 k=4 Regenerate

How it works: Build a k-NN graph on the points. Compute the normalized graph Laplacian L = I − D⁻¹/²AD⁻¹/². Its eigenvectors corresponding to small eigenvalues encode cluster membership. Running k-means in this eigenspace finds clusters that are connected but not necessarily convex.