Spectral clustering is a family of unsupervised learning methods that groups observations by analyzing the eigenvectors of a matrix representing their similarities. Rather than assigning clusters directly in the original feature space, it constructs a weighted graph, maps its vertices into a spectral representation, and partitions that representation, often with k-means clustering. The approach can identify nonconvex groups, such as curved or interlocking shapes, when the graph captures their underlying connectivity. Its results depend strongly on how similarities and graph connections are defined.
Mathematical foundations
Representing data as a graph
Given observations , spectral clustering constructs an undirected, weighted graph whose vertices represent observations and whose edge weights represent similarity. These weights form a symmetric affinity matrix , with entries . A missing edge has weight zero. Self-weights are commonly set to zero.
One common affinity is the Gaussian similarity:
where sets the distance scale. Small values emphasize local relationships; large values make distant observations more similar.
Common graph constructions include:
- Fully connected graphs: every pair of distinct observations receives a similarity weight.
- Nearest-neighbor graphs: each observation connects to a specified number of nearby observations. Because the neighbor relation can be asymmetric, the graph is usually symmetrized by retaining either the union or intersection of neighbor relations.
- Neighborhood-radius graphs: an edge exists only when the distance between two observations is below a threshold.
The neighbor count used to construct the graph is distinct from the desired number of clusters. A nearest-neighbor graph also does not make spectral clustering a form of nearest-neighbor classification: it specifies relationships among unlabeled observations rather than predicting labels from labeled neighbors.
Affinities may instead come from network connections, document similarities, or domain-specific measurements. Ordinary spectral clustering assumes a symmetric, nonnegative affinity matrix; directed graphs and signed similarities require modified formulations.
Graph Laplacians
The degree of vertex is
Let . The unnormalized graph Laplacian is
Two widely used normalized forms are
and
These definitions assume positive degrees; isolated vertices require separate handling or an explicit convention.
For a real vector ,
Thus, low values of this quadratic form correspond to functions that vary little across strongly connected vertices. This is the central mechanism of spectral clustering: eigenvectors associated with small Laplacian eigenvalues provide coordinates that change slowly within strongly connected groups.
The eigenvalues and eigenvectors also encode exact connectivity. The multiplicity of the zero eigenvalue equals the number of connected components. For the unnormalized Laplacian, component-indicator vectors span the zero eigenspace. For , the corresponding vectors are degree-weighted indicators. When components are weakly connected rather than completely disconnected, small nonzero eigenvalues can indicate approximate cluster structure.
Connection to graph partitioning
Spectral clustering can be derived as a relaxation of discrete graph partitioning problems.
For disjoint vertex sets and , define
and define the volume of a set by
Minimizing cut weight alone can favor separating a single weakly connected vertex. Balanced objectives counter this tendency by accounting for cluster size or volume.
For a partition into nonempty sets , two important objectives are
and
Here denotes the complement of . Ratio cut balances by the number of vertices; normalized cut balances by total incident edge weight.
Important balanced-cut formulations are NP-hard. Spectral methods replace discrete cluster indicators with real-valued vectors, producing tractable relaxations. In particular, the ratio-cut relaxation leads to
whose solutions use eigenvectors associated with the smallest eigenvalues of .
The normalized-cut relaxation can be expressed as
leading to the generalized eigenproblem
It can equivalently be transformed into an ordinary symmetric eigenproblem involving .
These relaxations explain the method’s computational structure, but they do not generally recover the exact optimum of the original discrete objective. Converting continuous eigenvectors into cluster labels introduces a further approximation.
Main algorithmic variants
A typical spectral clustering procedure has four stages:
- Construct the affinity graph.
- Compute a Laplacian or related normalized matrix.
- Extract a small set of eigenvectors to form an embedding.
- Convert embedded coordinates into cluster labels.
The choice of matrix, eigenvectors, normalization, and final partitioning rule distinguishes the variants.
Unnormalized spectral clustering
Compute eigenvectors corresponding to the smallest eigenvalues of , arrange them as columns of , and cluster the rows of .
This variant follows the ratio-cut relaxation. It can behave poorly when graph degrees vary greatly, because its size-balancing objective does not account for those degree differences.
Random-walk normalized clustering
Solve , or equivalently use the right eigenvectors of associated with its smallest eigenvalues. Cluster the rows of the resulting eigenvector matrix.
This formulation is closely associated with normalized cut. For a two-way partition, a threshold on a nontrivial eigenvector can be used instead of a separate multidimensional clustering step.
Symmetric normalized clustering
A widely used procedure forms the first eigenvectors of , places them in the columns of , and normalizes each nonzero row:
K-means then partitions the row vectors . This row normalization is a characteristic part of the Ng–Jordan–Weiss formulation.
An equivalent formulation uses the eigenvectors associated with the largest eigenvalues of , since this matrix equals .
For standard multiway normalized clustering, the eigenvectors generally include the trivial eigenvector. Other spectral embedding tasks may discard it; the two conventions should not be treated as interchangeable.
Interpretation and related methods
Random walks
The matrix
is a transition matrix for a random walk on the graph. For a connected undirected graph, its stationary distribution is proportional to vertex degree.
A useful cluster is a region in which a random walk tends to remain before crossing into another region. Normalized cut measures the tendency to leave clusters relative to their volumes. This interpretation connects spectral clustering to diffusion-based methods and the study of slowly mixing processes.
Geometry and representation
Spectral clustering is also a form of representation learning: it replaces the original coordinates with graph-derived coordinates. Two observations can become close in this representation because they belong to the same connected structure, even if their original coordinates are far apart.
For example, two interlocking crescent-shaped groups may be difficult to separate with k-means in the original plane. A local similarity graph can strongly connect points along each crescent while creating few connections between them. The spectral representation can then make the groups easier to separate.
This relationship places spectral clustering near manifold learning, particularly Laplacian eigenmaps. Their goals differ: manifold learning typically emphasizes a useful low-dimensional representation, whereas spectral clustering uses such a representation to produce a partition.
Relationship to kernel methods
Spectral clustering is related to kernel methods because both can operate through pairwise similarity matrices. Certain graph-cut objectives are equivalent to appropriately constructed weighted kernel k-means objectives. Nevertheless, a nonnegative graph affinity matrix is not necessarily a positive semidefinite kernel matrix, and spectral clustering is not simply ordinary k-means applied to an arbitrary kernel.
Parameter selection and numerical behavior
Similarity scale and preprocessing
Graph construction is often more consequential than the choice among standard spectral variants. Distance-based affinities depend on units, irrelevant variables, and the chosen metric. Feature scaling or a domain-specific similarity measure can substantially change the resulting graph.
An excessively local graph may fragment into disconnected pieces. An overly dense graph, or an excessively large Gaussian bandwidth, may blur meaningful separation. Locally scaled affinities use neighborhood-dependent bandwidths to accommodate varying sampling density, but introduce their own assumptions.
Number of clusters
The number of clusters is often supplied in advance. A common heuristic examines the ordered Laplacian eigenvalues
and looks for a substantial gap between and . Such an eigengap can support a -cluster interpretation, but is not a universal selection rule. Noise, overlapping groups, uneven density, and graph parameters can all change the spectrum.
Stability and label assignment
Eigenvectors have arbitrary signs, and an eigenspace with repeated eigenvalues admits different orthonormal bases. These ambiguities do not inherently change Euclidean distances between embedded rows under a common orthogonal transformation. However, a small gap between selected and unselected eigenvalues can make the selected subspace sensitive to perturbations.
The final k-means stage can produce different results under different initializations. Thresholding, discretization methods, and alternative rounding procedures provide other ways to assign labels.
Computational cost and scalability
Spectral clustering can be expensive because it operates on relationships among observations rather than only their individual feature vectors.
A dense affinity matrix requires storage, and straightforward pairwise-distance construction requires quadratic work in the number of observations, with additional dependence on feature dimension. A full dense eigendecomposition has approximately time complexity.
Practical implementations usually compute only a few eigenvectors. Sparse neighborhood graphs and iterative eigensolvers can reduce storage and computation considerably. Their cost depends on graph sparsity, spectral gaps, numerical tolerances, and the number of requested eigenvectors; there is no single runtime bound that describes all implementations.
Large-scale approaches include:
- sparse graph construction and approximate neighbor search;
- landmark and Nyström approximations;
- graph coarsening and multilevel partitioning;
- distributed eigensolvers;
- learned approximations to spectral embeddings.
These methods can alter the effective graph or embedding. Their accuracy therefore depends on whether they preserve the structures relevant to the partition.
Applications and limitations
Spectral clustering has been used in image segmentation, document grouping, network community detection, motion segmentation, and the analysis of relational data. In computer vision, affinities can combine appearance and spatial proximity. In document analysis, they can represent similarity between sparse text vectors or learned embeddings.
Its main limitations are:
- Dependence on similarity design: a partition reflects the chosen graph, not an objective grouping independent of representation.
- Sensitivity to noise and degree imbalance: outliers, weak connections, and uneven sampling can distort eigenvectors or create unintended partitions.
- Limited scalability: affinity construction and eigenvector computation can dominate memory and runtime.
- Transductive structure: standard formulations cluster the observations used to build the graph. Assigning new observations requires an extension, such as an out-of-sample embedding or a separately trained prediction rule.
- Hard partitioning: standard variants assign each observation to one group, which may not represent overlapping or hierarchical structure.
- No universal shape guarantee: the ability to separate some nonconvex groups does not imply reliable recovery of arbitrary shapes or densities.
Historical development
Spectral clustering developed from spectral graph theory and numerical graph partitioning. Miroslav Fiedler’s work in the 1970s established important connections between graph connectivity and Laplacian eigenvalues. The eigenvector associated with the second-smallest Laplacian eigenvalue became central to spectral bisection.
In computer vision, Jianbo Shi and Jitendra Malik’s normalized-cut work, published in 2000, connected graph partitioning with perceptual image segmentation. Andrew Ng, Michael Jordan, and Yair Weiss subsequently presented an influential normalized spectral clustering formulation in the early 2000s. These developments helped establish spectral clustering as a standard approach within machine learning, linking graph-cut objectives, spectral embeddings, and conventional clustering procedures.