Spectral Clustering
Spectral Clustering via Graph Laplacian Eigenvectors (Ng–Jordan–Weiss Algorithm) · Also known as: NJW spectral clustering, graph Laplacian clustering, normalized spectral clustering, spectral graph clustering, SC
Spectral Clustering is a graph-based unsupervised learning algorithm, formalized by Ng, Jordan, and Weiss in 2002, that maps data points into a low-dimensional eigenspace derived from the similarity graph's Laplacian before applying k-means. This spectral embedding makes it possible to recover clusters of arbitrary shape — rings, crescents, interleaved spirals — that Euclidean distance-based methods consistently fail to separate.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
+5 more
When to use it
Spectral Clustering is well suited when the clusters in the data are non-convex, non-linearly separable, or connected by thin bridges that Euclidean partitioning methods cannot detect — common examples include ring-shaped clusters, interleaved spirals, and image segments. It is appropriate when pairwise similarity between points can be computed meaningfully (either from a kernel on raw features or from a pre-supplied affinity matrix), and when the number of clusters k is known or can be estimated from the eigengap heuristic. The method requires no distributional assumptions on the cluster shapes. Practical limitations include quadratic memory in the number of points (for the full affinity matrix) and cubic time for eigendecomposition, making the standard formulation expensive beyond roughly 10,000 points. Approximate methods (Nystrom, sparse graphs, randomized SVD) extend its reach to larger datasets.
Strengths & limitations
- Detects clusters of arbitrary shape, including non-convex and non-linearly separable configurations that defeat k-means and Gaussian mixture models.
- Can operate on any pairwise similarity matrix, not just Euclidean distances, making it applicable to graphs, strings, and other structured data.
- The eigengap heuristic provides a principled data-driven guide for choosing the number of clusters k.
- Grounded in a rich spectral graph theory, enabling formal analysis of convergence and cluster quality.
- Conceptually simple and easily implemented using standard linear-algebra libraries.
- Constructing the full n-by-n affinity matrix requires O(n^2) memory and O(n^3) time for eigendecomposition, making the naive algorithm infeasible for large datasets.
- Results are sensitive to the choice of the kernel bandwidth sigma and to the graph construction strategy; poor choices can merge or fragment clusters.
- k-means initialization in the spectral embedding introduces randomness; different runs may yield different partitions.
- Does not scale gracefully to very high-dimensional feature spaces without careful kernel selection.
- Provides cluster labels only; it offers no generative model and no natural out-of-sample extension for new points.
Frequently asked
How do I choose the number of clusters k?
The eigengap heuristic is the standard guidance: compute the eigenvalues of the normalized Laplacian in ascending order and look for the largest gap between consecutive eigenvalues. The index at which this gap occurs suggests the natural number of clusters. When the eigengap is ambiguous, stability-based approaches — running the algorithm for several values of k and comparing cluster assignments across perturbations — can help.
How should I set the Gaussian kernel bandwidth sigma?
A common heuristic is the median of pairwise distances in the dataset, or a nearest-neighbour self-tuning scheme (Zelnik-Manor & Perona, 2004) that assigns a local bandwidth to each point. In practice, sigma should be validated by inspecting the connectivity of the resulting affinity graph: every point should have at least a few high-weight neighbours, and the graph should not fragment into isolated components.
Why is the row-normalization step necessary?
The eigenvectors of the Laplacian can differ substantially in scale. Without normalizing each row of the embedding matrix to unit length, the k-means step may be dominated by eigenvectors with large magnitudes and ignore informative but smaller-magnitude components. The row-normalization introduced by Ng, Jordan, and Weiss maps all points onto the unit sphere so that k-means responds to the angular geometry of the embedding.
Can spectral clustering handle very large datasets?
Not in its naive form, which requires O(n^2) memory and O(n^3) eigendecomposition time. For large n, standard remedies include: building a sparse k-nearest-neighbour graph instead of a full affinity matrix; using the Nystrom approximation to estimate eigenvectors from a subsample; or applying randomized SVD. These approximate methods recover most of the accuracy at a fraction of the cost.
Sources
- Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856. link ↗
- von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416. DOI: 10.1007/s11222-007-9033-z ↗
- Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905. DOI: 10.1109/34.868688 ↗
How to cite this page
ScholarGate. (2026, June 3). Spectral Clustering via Graph Laplacian Eigenvectors (Ng–Jordan–Weiss Algorithm). ScholarGate. https://scholargate.app/en/machine-learning/spectral-clustering
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- DBSCANMachine learning↔ compare
- Hierarchical ClusteringMachine learning↔ compare
- K-meansMachine learning↔ compare
- Principal Component AnalysisMachine learning↔ compare
- t-SNEMachine learning↔ compare