Spectral clustering

On this page 7

Spectral clustering is a family of unsupervised machine learning methods that partition data by building a similarity graph over the points and then clustering the points in a low-dimensional embedding formed by the eigenvectors of the graph Laplacian. In machine learning and the wider field of artificial intelligence, it is valued because it can recover non-convex, intertwined clusters that centroid-based methods such as k-means clustering cannot separate.

The method rests on a simple idea: points that are strongly connected in the graph should end up in the same group, even when the groups are curved, ring-shaped or elongated in the original feature space. Spectral clustering turns that graph-cutting problem into a linear algebra problem that standard eigensolvers can handle.

How spectral clustering works step by step

Spectral clustering works by converting pairwise similarities into a graph, computing a spectral embedding from that graph and running a simple clustering algorithm in the embedded space. The pipeline has four stages, and each stage introduces choices that strongly affect the result.

  1. Build an affinity matrix W, where each entry measures how similar two points are, usually with a Gaussian (RBF) kernel or a k-nearest-neighbor rule.
  2. Compute the degree matrix D, a diagonal matrix holding the sum of each row of W.
  3. Form a graph Laplacian, such as L = D – W or a normalized variant, and compute its k eigenvectors with the smallest eigenvalues.
  4. Stack those eigenvectors as columns, treat each row as the new coordinates of a point and run k-means in the embedded space.

The key insight is that the smallest eigenvectors of the Laplacian are nearly constant within well-connected components. If the graph had k perfectly disconnected groups, the Laplacian would have exactly k zero eigenvalues, and the embedding would place each group at a single point. Real data adds noise, but the embedded points still form compact, easily separated blobs.

The following table summarizes what each stage produces and which decision matters most at that stage.

StageOutputCritical decision
Similarity graphAffinity matrix W (n x n)Kernel type and bandwidth
Laplacian constructionMatrix LUnnormalized or normalized form
Eigendecompositionk eigenvectorsNumber of clusters k
Embedding clusteringCluster labelsk-means restarts or discretization
Stages of the spectral clustering pipeline

Graph construction and Laplacian variants

The quality of spectral clustering depends more on the similarity graph than on any later step. A poorly chosen graph produces a misleading embedding, and no clustering of that embedding can repair it. Practitioners usually choose among three graph types.

  • A fully connected Gaussian graph uses exp(-||x – y||^2 / 2 sigma^2) for every pair, where the bandwidth sigma controls how quickly similarity decays.
  • A k-nearest-neighbor graph connects each point to its k closest neighbors, which produces a sparse matrix and adapts to varying density.
  • An epsilon-neighborhood graph connects points closer than a fixed radius, which is simple but fragile when density varies.

The Laplacian variant matters as well. The normalized forms correct for differences in node degree and usually give better results when clusters differ in size or density. The table below compares the three common variants.

LaplacianDefinitionAssociated graph cutTypical behavior
UnnormalizedL = D – WRatioCutSensitive to degree imbalance
Symmetric normalizedI – D^(-1/2) W D^(-1/2)Normalized cutRequires row normalization of the embedding
Random walkI – D^(-1) WNormalized cutRobust default in practice
Common graph Laplacian variants

The symmetric normalized version is associated with the Ng-Jordan-Weiss algorithm, while the random walk version follows the Shi-Malik normalized cut formulation used in image segmentation. Both relax a discrete, NP-hard graph partitioning problem into a continuous eigenvalue problem that can be solved efficiently.

Spectral clustering compared with other clustering methods

Spectral clustering differs from other clustering methods mainly in what it assumes about cluster shape. k-means assumes compact, roughly spherical groups, while spectral clustering assumes only that members of a cluster are connected through chains of similar points.

The comparison below places spectral clustering next to the neighboring methods in the same toolbox.

MethodCluster shapeNeeds k in advanceScalability
Spectral clusteringArbitrary, connectivity-basedYesLimited by eigendecomposition
k-means clusteringConvex, sphericalYesVery high
DBSCANArbitrary, density-basedNoHigh with spatial indexes
Gaussian mixture modelEllipticalYesModerate
Hierarchical clusteringDepends on linkageNoLow for large n
Spectral clustering and related clustering methods

Spectral clustering also has a close relationship to kernel k-means: with suitable weighting, the normalized cut objective is mathematically equivalent to a weighted kernel k-means objective. It is also related to Laplacian eigenmaps, a dimensionality reduction method that uses the same embedding without the final clustering step.

Choosing parameters in practice

Applying spectral clustering in practice means choosing the graph parameters, the number of clusters and the solver with care. Defaults rarely suit every dataset, so each choice deserves validation.

The eigengap heuristic is the standard tool for choosing k: sort the Laplacian eigenvalues in ascending order and pick the k where the gap between the k-th and (k+1)-th eigenvalue is largest. A clear gap signals well-separated clusters, while a smooth spectrum warns that the data has no strong cluster structure.

The decision table below lists typical situations and the configuration that usually works best.

SituationRecommended choiceReason
Clusters with different densitiesk-nearest-neighbor graphAdapts locally to density
Unknown similarity scaleSelf-tuning local bandwidthAvoids one global sigma
More than 10,000 pointsSparse graph with Lanczos solverKeeps memory and time manageable
Unequal cluster sizesNormalized LaplacianBalances degree differences
Unknown number of clustersEigengap inspectionReveals natural group count
Configuration choices by situation

Feature scaling must happen before building the graph, because distances drive every similarity value. For large datasets, approximations such as the Nystrom method, landmark-based graphs or randomized eigensolvers reduce the typical O(n^3) cost of a dense eigendecomposition to something tractable.

Limitations and common mistakes

The main limitation of spectral clustering is its computational cost: a dense affinity matrix needs O(n^2) memory, so one million points would require terabytes. The method is therefore best suited to small and medium datasets or to sparse graphs.

The most frequent mistakes come from treating the method as parameter-free. The table below links typical symptoms to their cause and fix.

SymptomLikely causeFix
One giant cluster plus tiny onesBandwidth too largeReduce sigma or use a kNN graph
Many isolated singletonsBandwidth too smallIncrease sigma or neighbors
Results change between runsRandom k-means initializationUse many restarts or discretization
Clusters follow one featureMissing feature scalingStandardize features first
Typical symptoms, causes and fixes

Spectral clustering is also transductive: it labels the points it was given and has no natural way to assign a new point without recomputing the graph or using an out-of-sample extension. It does not detect noise points the way DBSCAN does, so outliers are forced into some cluster.

Explained without jargon

Spectral clustering sorts items into groups by first asking which items are close neighbors. It draws a web of connections between similar items, with stronger threads between closer pairs.

It then looks for the places where the web can be cut with the fewest broken threads. Imagine two friend circles that share only a handful of acquaintances: cutting those few ties separates the circles cleanly, even if each circle has an odd shape. The key takeaway is that spectral clustering groups items by how they are connected, not by how close they are to a central point.

A typical use case

A medical imaging team needs to separate tissue regions in 512 x 512 pixel MRI slices. Neighboring pixels with similar intensity are connected in a sparse graph, with each pixel linked to its 8 adjacent pixels and edge weights based on intensity difference. Because regions such as gray matter are folded and curved, k-means on raw intensity mixes regions that happen to share brightness.

The team builds the normalized Laplacian, computes the 6 smallest eigenvectors with a sparse Lanczos solver and runs k-means on the embedding. The eigengap after the fifth eigenvalue confirms five meaningful regions. The resulting segmentation follows anatomical boundaries much more closely than intensity thresholding, and radiologists need far fewer manual corrections before the masks are used for volume measurements.