ML//unsupervised learning//clustering//spectral clustering

2026-09-06

Spectral clustering is a clustering method that groups samples using the eigenvectors of a matrix built from the relations between them, turning local relations into coordinates. K-means optimizes compactness around centroids in the coordinates it is given; spectral clustering changes the coordinates first, so that connectivity rather than distance to a centre defines the groups, and K-means is still its last step.

Building the graph is part of the model. Each sample xix_ixi is a node, and a common affinity, often restricted to nearby neighbors, is the Gaussian one:

wij=exp⁡ ⁣(−∥xi−xj∥22σ2),wii=0.w_{ij}=\exp\!\left(-\frac{\|x_i-x_j\|^2}{2\sigma^2}\right),\qquad w_{ii}=0.wij=exp(−2σ2∥xi−xj∥2),wii=0.

The width σ\sigmaσ sets a similarity scale and the groups change with it; the number of neighbors sets local connectivity, and a neighbor graph needs a symmetrization rule before an undirected Laplacian is used (adjacency and degree). Neither has a universal value: too few connections fragment a group, too many merge distinct regions.

The symmetric normalized variant is one concrete recipe, working on DDD and Lsym=I−D−1/2WD−1/2L_{\mathrm{sym}}=I-D^{-1/2}WD^{-1/2}Lsym=I−D−1/2WD−1/2 (normalized Laplacian):

1Handle isolated nodes, then form DDD and LsymL_{\mathrm{sym}}Lsym2Take KKK orthonormal eigenvectors of the smallest eigenvalues as the columns of U∈RN×KU\in\mathbb R^{N\times K}U∈RN×Ktrivial mode included3Normalize each nonzero row to unit length4Apply K-means to those rows5Carry the labels back to the samples

A zero row calls for revisiting components, never dividing by zero. Other variants (LrwL_{\mathrm{rw}}Lrw, the problem Lv=λDvLv=\lambda DvLv=λDv, the original Ng, Jordan and Weiss operator) bring their own normalizations.

The modes separate communities through the null space. With KKK disconnected components the null space has dimension KKK and its patterns identify the components; in the symmetric version, row normalization removes degree-induced magnitude differences within each component. With weak connections, low-disagreement patterns appear that distinguish regions well connected inside and poorly outside (spectral gap, with the random walk's reading in stationary distribution). The number of groups is read in the eigengap: KKK small eigenvalues followed by a clearly larger one.

The partition it favors is the one with the smallest normalized cut. For a node set SSS, cut⁡(S,Sˉ)=∑i∈S,j∉Swij\operatorname{cut}(S,\bar S)=\sum_{i\in S,j\notin S}w_{ij}cut(S,Sˉ)=∑i∈S,j∈/Swij and vol⁡(S)=∑i∈Sdi\operatorname{vol}(S)=\sum_{i\in S}d_ivol(S)=∑i∈Sdi, and the normalized cut is this sum:

Ncut⁡(S,Sˉ)=cut⁡(S,Sˉ)vol⁡(S)+cut⁡(S,Sˉ)vol⁡(Sˉ).\operatorname{Ncut}(S,\bar S)=\frac{\operatorname{cut}(S,\bar S)}{\operatorname{vol}(S)}+\frac{\operatorname{cut}(S,\bar S)}{\operatorname{vol}(\bar S)}.Ncut(S,Sˉ)=vol(S)cut(S,Sˉ)+vol(Sˉ)cut(S,Sˉ).

It favors regions with few external connections relative to their total connectivity. The spectral problem relaxes this objective, so the K-means step does not guarantee the combinatorial optimum.

Caveats travel with the intuition: degree normalization leaves some density effects, and cutting by the sign of one vector is a two-group heuristic. spectral coordinates distinguishes columns from rows; two-community graph works an exact case. The cost is an eigendecomposition of an N×NN\times NN×N matrix: manageable with thousands of samples (grouping 200 pumps by their vibration spectra to find families of behaviour), sparse methods with millions.

The sources are von Luxburg, A Tutorial on Spectral Clustering (2007), section 6; Ng, Jordan and Weiss, On Spectral Clustering: Analysis and an Algorithm (NIPS 2001), section 2; Spielman, Spectral Graph Theory, lecture 1, sections 1.5 and 1.6