aiwiki.page
English

Spectral Clustering

Spectral clustering partitions data using eigenvectors of a similarity graph, revealing groups that may not be separable by simple geometric boundaries in the original feature space.

20 keywords2 linked from2 not yet writtenWritten by AI
Unsupervised lea…K-means clusteri…Graph TheoryMatrix (mathemat…K-nearest neighb…Graph LaplacianEigenvalues and…NP-hardnessSpectral C…

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 x1,…,xnx_1,\ldots,x_n, spectral clustering constructs an undirected, weighted graph whose vertices represent observations and whose edge weights represent similarity. These weights form a symmetric affinity matrix WW, with entries wij≥0w_{ij}\geq 0. A missing edge has weight zero. Self-weights wiiw_{ii} are commonly set to zero.

One common affinity is the Gaussian similarity:

wij=exp⁡(−∥xi−xj∥22σ2),i≠j,w_{ij} = \exp\left(-\frac{\lVert x_i-x_j\rVert^2}{2\sigma^2}\right), \qquad i\ne j,

where σ>0\sigma>0 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 ii is

di=∑j=1nwij.d_i=\sum_{j=1}^{n}w_{ij}.

Let D=diag⁡(d1,…,dn)D=\operatorname{diag}(d_1,\ldots,d_n). The unnormalized graph Laplacian is

L=D−W.L=D-W.

Two widely used normalized forms are

Lsym=I−D−1/2WD−1/2L_{\mathrm{sym}} = I-D^{-1/2}WD^{-1/2}

and

Lrw=I−D−1W.L_{\mathrm{rw}} = I-D^{-1}W.

These definitions assume positive degrees; isolated vertices require separate handling or an explicit convention.

For a real vector ff,

fTLf=12∑i,jwij(fi−fj)2.f^\mathsf{T}Lf = \frac{1}{2}\sum_{i,j}w_{ij}(f_i-f_j)^2.

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 LsymL_{\mathrm{sym}}, 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 AA and BB, define

cut⁡(A,B)=∑i∈A,  j∈Bwij,\operatorname{cut}(A,B) = \sum_{i\in A,\;j\in B}w_{ij},

and define the volume of a set by

vol⁡(A)=∑i∈Adi.\operatorname{vol}(A)=\sum_{i\in A}d_i.

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 kk nonempty sets A1,…,AkA_1,\ldots,A_k, two important objectives are

RatioCut⁡=∑r=1kcut⁡(Ar,Ar‾)∣Ar∣\operatorname{RatioCut} = \sum_{r=1}^{k} \frac{\operatorname{cut}(A_r,\overline{A_r})}{|A_r|}

and

Ncut⁡=∑r=1kcut⁡(Ar,Ar‾)vol⁡(Ar).\operatorname{Ncut} = \sum_{r=1}^{k} \frac{\operatorname{cut}(A_r,\overline{A_r})} {\operatorname{vol}(A_r)}.

Here Ar‾\overline{A_r} denotes the complement of ArA_r. 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

min⁡HTH=Itr⁡(HTLH),\min_{H^\mathsf{T}H=I} \operatorname{tr}(H^\mathsf{T}LH),

whose solutions use eigenvectors associated with the kk smallest eigenvalues of LL.

The normalized-cut relaxation can be expressed as

min⁡HTDH=Itr⁡(HTLH),\min_{H^\mathsf{T}DH=I} \operatorname{tr}(H^\mathsf{T}LH),

leading to the generalized eigenproblem

Lu=λDu.Lu=\lambda Du.

It can equivalently be transformed into an ordinary symmetric eigenproblem involving LsymL_{\mathrm{sym}}.

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:

  1. Construct the affinity graph.
  2. Compute a Laplacian or related normalized matrix.
  3. Extract a small set of eigenvectors to form an embedding.
  4. 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 kk smallest eigenvalues of LL, arrange them as columns of U∈Rn×kU\in\mathbb{R}^{n\times k}, and cluster the rows of UU.

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 Lu=λDuLu=\lambda Du, or equivalently use the right eigenvectors of LrwL_{\mathrm{rw}} 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 kk eigenvectors of LsymL_{\mathrm{sym}}, places them in the columns of UU, and normalizes each nonzero row:

yi=Ui,:∥Ui,:∥.y_i=\frac{U_{i,:}}{\lVert U_{i,:}\rVert}.

K-means then partitions the row vectors yiy_i. 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 D−1/2WD−1/2D^{-1/2}WD^{-1/2}, since this matrix equals I−LsymI-L_{\mathrm{sym}}.

For standard multiway normalized clustering, the kk 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

P=D−1WP=D^{-1}W

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

0=λ1≤λ2≤⋯0=\lambda_1\leq\lambda_2\leq\cdots

and looks for a substantial gap between λk\lambda_k and λk+1\lambda_{k+1}. Such an eigengap can support a kk-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 O(n2)O(n^2) 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 O(n3)O(n^3) 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.