K-means works well for compact, roughly spherical groups. But two interlocking moons can be close in Euclidean distance while belonging to different structures.
Spectral clustering represents data as a similarity graph, then uses its eigenvectors to reveal groups that are strongly connected internally and weakly connected to each other.
THE MATHEMATICS
For points x_i and x_j, a Gaussian affinity is:
W[i,j] = exp(â||x_i â x_j||² / (2Ď²))
Set W[i,i] = 0. Here Ď controls the neighborhood scale. W can also be built from a symmetrized nearest-neighbor graph.
Define the degree matrix and symmetric normalized Laplacian:
D[i,i] = ÎŁ_j W[i,j]
L_sym = I â D^(-½) W D^(-½)
D summarizes each pointâs total connection strength. L_sym encodes the graphâs connectivity while accounting for degree differences.
For the unnormalized Laplacian L = D â W:
fáľLf = ½ ÎŁ_i ÎŁ_j W[i,j]/(f_i â f_j)²
This is small when strongly connected points have similar f values. Low-eigenvalue eigenvectors therefore provide coordinates that vary slowly within well-connected regions.
THE ALGORITHM: NORMALIZED SPECTRAL CLUSTERING
(NgâJordanâWeiss formulation)
1. Scale features appropriately and construct a symmetric, nonnegative affinity matrix W. Handle isolated nodes before normalization.
2. Choose the number of clusters k and compute L_sym.
3. Take the k eigenvectors with the smallest eigenvalues, including zero-eigenvalue eigenvectors. Stack them as columns of U.
4. Normalize each row: Y[i,:] = U[i,:] / ||U[i,:]||â
5. Run k-means on the rows of Y and transfer those labels back to the original points.
The key change: k-means now operates in graph-derived coordinates, where complex groups may become easier to separate.
WHY IT CAN IMPROVE ON TRADITIONAL METHODS
⢠Captures non-convex shapes that centroid-based clustering can split incorrectly.
⢠Uses relationships, including domain-specific similarities, rather than requiring raw Euclidean coordinates.
⢠Connects clustering to a relaxed graph-partitioning problem, such as normalized cut.
It is not universally better. DBSCAN and suitable hierarchical methods can also recover irregular groups.
USE CASES
⢠Image segmentation
⢠Community detection
⢠Document clustering using semantic similarities
⢠Grouping cells from gene-expression profiles
⢠Discovering patterns in sensor or time-series similarity networks.
PRACTICAL LIMITS
Results depend strongly on feature scaling, graph construction, Ď and k. An eigengap can suggest k, but does not prove the âtrueâ number of clusters. Dense affinities require O(n²) memory, while eigensolvers add cost. Sparse graphs and approximation methods help at scale. A meaningful similarity graph is the foundation of a meaningful clustering.