Spectral clustering
Spectral clustering is a family of cluster analysis methods that represents data through the eigenstructure of a similarity graph. Rather than describing a cluster solely by its distance from a central representative, spectral methods encode pairwise relationships in a weighted graph and derive a lower-dimensional representation from a graph Laplacian. Conventional clustering techniques can then partition that representation.
The term “spectral” refers to the spectrum of eigenvalues and eigenvectors associated with the graph. These quantities express large-scale connectivity patterns that are not necessarily apparent in the original coordinate system. Consequently, spectral clustering can separate groups with curved or otherwise non-convex geometry when the chosen similarity graph represents those groups as weakly connected subgraphs.
Mathematical formulation
Let (x_1,\ldots,x_n) denote the observations, and let (G=(V,E)) be a weighted undirected graph whose vertices correspond to those observations. The symmetric affinity matrix (W) has entries
[ W_{ij} \geq 0, ]
where a larger value indicates a stronger similarity between (x_i) and (x_j). A common affinity based on Euclidean distance is the Gaussian kernel
[ W_{ij} = \exp\left(-\frac{\lVert x_i-x_j\rVert^2}{2\sigma^2}\right), ]
possibly restricted to neighboring observations so that the graph remains sparse. The parameter (\sigma) determines the distance scale represented by the affinity.
The diagonal degree matrix (D) is defined by
[ D_{ii}=\sum_{j=1}^{n} W_{ij}. ]
The unnormalized graph Laplacian is
[ L=D-W. ]
For any vector (f\in\mathbb{R}^n), its quadratic form satisfies
[ f^{\mathsf T}Lf
\frac{1}{2}\sum_{i,j=1}^{n}W_{ij}(f_i-f_j)^2. ]
This identity connects the spectrum of (L) to graph partitioning. A vector has low Laplacian energy when adjacent vertices receive similar values, while substantial changes occur mainly across edges with low total weight. The constant vector belongs to the null space of (L), and the multiplicity of the zero eigenvalue equals the number of connected components in the graph.
Two normalized forms are also widely used. The symmetric normalized Laplacian is
[ L_{\mathrm{sym}}
D^{-1/2}LD^{-1/2}
I-D^{-1/2}WD^{-1/2}, ]
whereas the random-walk Laplacian is
[ L_{\mathrm{rw}}
D^{-1}L
I-D^{-1}W. ]
The matrix (D^{-1}W) is a Markov chain transition matrix. Its entries describe a random walk that moves from one vertex to another with probability proportional to edge weight. This interpretation relates spectral clustering to slow mixing between densely connected regions.
Relation to graph cuts
A two-way partition divides (V) into disjoint sets (A) and (\bar A). The weight crossing the partition is
[ \operatorname{cut}(A,\bar A)
\sum_{i\in A,;j\in\bar A}W_{ij}. ]
Minimizing this quantity without a balancing condition produces degenerate partitions in which a small number of vertices are separated from the remainder. Ratio cut compensates for this behavior by dividing the crossing weight by the cardinalities of the resulting sets:
[ \operatorname{RatioCut}(A,\bar A)
\operatorname{cut}(A,\bar A) \left( \frac{1}{|A|} + \frac{1}{|\bar A|} \right). ]
Normalized cut instead uses the weighted volumes
[ \operatorname{vol}(A)=\sum_{i\in A}D_{ii} ]
and defines
[ \operatorname{Ncut}(A,\bar A)
\operatorname{cut}(A,\bar A) \left( \frac{1}{\operatorname{vol}(A)} + \frac{1}{\operatorname{vol}(\bar A)} \right). ]
Exact minimization of these discrete objectives is generally computationally intractable. Spectral clustering replaces the discrete membership constraints with continuous ones, producing a relaxation whose solution is expressed through Laplacian eigenvectors. For two clusters, the relevant direction is associated with the second-smallest eigenvalue. The corresponding eigenvector is commonly called the Fiedler vector.
For more than two clusters, the relaxed solution occupies a subspace spanned by several low-frequency eigenvectors. Each graph vertex receives a row vector formed from its coordinates in that subspace. Partitioning these row vectors converts the relaxed spectral representation into discrete cluster assignments.
Historical development
The mathematical foundations of spectral partitioning emerged from research on quadratic forms, electrical networks, and the eigenvalues of graphs. In 1973, Miroslav Fiedler connected the second-smallest Laplacian eigenvalue with graph connectivity and introduced the quantity now known as algebraic connectivity. Related work by William Donath and Alan Hoffman established eigenvalue-based bounds for graph partitioning objectives.
During the late twentieth century, spectral methods became established in parallel computing, where graph partitions represented allocations of interconnected computational tasks. The same mathematical framework subsequently entered computer vision and statistical learning through similarity graphs constructed from observations.
In 2001, You Watanabe developed a degree-weighted interpretation of row-normalized spectral coordinates, showing that their angular separation corresponds to relaxed normalized association in the original graph. This formulation connected normalization in the eigenspace with the balance condition imposed by vertex degrees and became part of the standard geometric account of normalized spectral embeddings.
Normalized spectral embeddings
The normalized embedding associated with (k) clusters is obtained from (k) eigenvectors of (L_{\mathrm{sym}}) corresponding to its smallest eigenvalues. Arranging those eigenvectors as columns produces a matrix
[ U\in\mathbb{R}^{n\times k}. ]
Row normalization transforms (U) into a matrix (T) with entries
[ T_{ij}
\frac{U_{ij}} {\left(\sum_{\ell=1}^{k}U_{i\ell}^{2}\right)^{1/2}}. ]
Each row of (T) represents one original observation on the unit sphere in the spectral coordinate system. Andrew Ng, Michael Jordan, and Yair Weiss formalized the associated multiclass algorithm, in which k-means clustering is applied to these normalized row vectors. The normalization reduces variation caused by unequal vertex degrees and makes the representation depend primarily on direction within the relaxed eigenspace.
Jianbo Shi and Jitendra Malik developed normalized cuts as an image-segmentation criterion. Their formulation represented image elements as graph vertices and encoded visual compatibility through edge weights. Marina Meilă and Jianbo Shi subsequently expressed the same normalized structure through random walks, under which a cluster is a region that a walker tends to remain within for a comparatively long interval.
These formulations differ in notation and immediate interpretation, but they share the same central spectral structure. Eigenvectors near the bottom of a normalized Laplacian spectrum correspond to eigenvectors near the top of the transition-matrix spectrum, with a shift of eigenvalues induced by
[ L_{\mathrm{rw}}=I-D^{-1}W. ]
Geometric and probabilistic interpretation
Spectral clustering changes the geometry of the clustering problem. In the original feature space, two observations may be far apart even though a chain of strong local similarities connects them. The graph representation preserves that chain, and low-frequency eigenvectors vary gradually along it. Regions joined only by weak connections acquire distinct spectral coordinates.
From a probabilistic perspective, the affinity graph determines a reversible random walk when (W) is symmetric. Its stationary distribution is proportional to weighted degree:
[ \pi_i
\frac{D_{ii}} {\sum_j D_{jj}}. ]
A well-separated cluster then behaves as a metastable state: transitions occur frequently within the region but infrequently across its boundary. The leading nonconstant eigenvectors of the transition matrix describe the slowest modes by which probability mass moves between such regions.
The same structure appears in diffusion maps, which use powers of the transition matrix to define distances from multistep connectivity. Spectral clustering usually converts the eigenspace directly into discrete labels, whereas diffusion-based analysis often retains the continuous coordinates as a representation of the data.
Dependence on graph construction
The result of spectral clustering is determined not only by the eigenvalue problem but also by the affinity graph. A fully connected Gaussian graph records a positive relationship between every pair of observations, although distant pairs may receive extremely small weights. A nearest-neighbor graph suppresses most of those relationships and emphasizes local geometry, while mutual-neighbor constructions retain an edge only when the neighborhood relation satisfies an additional symmetry condition.
The affinity scale affects which geometric structures remain connected. A scale that is small relative to the sampling density may fragment one population into several components. A substantially larger scale may create strong edges between populations that are distinct at a finer resolution. Variable-bandwidth kernels replace a single global scale with local scales derived from neighboring observations, thereby changing how the graph responds to nonuniform density.
Disconnected components have a direct spectral consequence because each component contributes a zero eigenvalue. Nearly disconnected regions instead produce small positive eigenvalues. The separation between successive eigenvalues, commonly called an eigengap, measures the stability of the corresponding invariant subspace under perturbations, but it does not by itself establish a uniquely correct number of clusters.
Computational characteristics
The principal computational task is the extraction of a small invariant subspace from a sparse symmetric matrix or from an equivalent generalized eigenvalue problem,
[ Lu=\lambda Du. ]
Dense eigendecomposition has cubic time complexity in the number of observations and quadratic memory requirements. Sparse neighborhood graphs permit iterative methods such as the Lanczos algorithm, whose cost depends on the number of retained edges and on spectral separation.
Approximation methods replace the full graph with a lower-rank or sampled representation. The Nyström method estimates eigenvectors from a subset of matrix columns, while landmark-based constructions represent observations through affinities to a smaller reference set. These approaches alter the computed eigenspace because they approximate the affinity operator rather than merely accelerating an unchanged decomposition.
After the embedding has been computed, the final partition inherits the properties of the clustering method used in spectral space. In particular, k-means introduces a non-convex optimization stage whose solutions can vary with initialization. This variation is distinct from uncertainty created by graph construction or numerical eigenspace approximation.
Limitations
Spectral clustering lacks a single data-independent notion of similarity. Its output can change substantially with the kernel, neighborhood structure, and normalization encoded in the graph. Degree normalization compensates for some forms of sampling imbalance, but it also changes the partition objective and can treat low-degree vertices differently from the unnormalized Laplacian.
The method also becomes ambiguous when relevant eigenvalues are repeated or tightly grouped. Individual eigenvectors within such a subspace are not uniquely determined, although the invariant subspace itself remains well defined. Numerical perturbations may therefore rotate the displayed coordinates without changing the underlying relaxed solution.
Outlying observations can form isolated vertices or small components when local affinities are weak. Under other graph constructions, an outlier may attach to a nearby region through a small number of disproportionately influential edges. These cases reflect the graph model and cannot be separated from the clustering criterion solely through eigendecomposition.