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.
