Core ML2001intermediate11 min read

On Spectral Clustering: Analysis and an Algorithm

عن التَّعنقُد الطيفي: تحليل وخوارزمية

Ng, A. Y. · Jordan, M. I. · Weiss, Y. — NeurIPS

The problem

By 2001, algorithms like k-means worked well only when clusters were convex blobs. Real data — image segments, social networks, gene expression profiles — often forms rings, spirals, or irregular shapes that k-means cannot separate. Several researchers had proposed using eigenvectors of graph-derived matrices, but the field had many competing variants with no unifying analysis, and most lacked theoretical guarantees.

The contribution

A clean, simple spectral clustering (NJW): build a Gaussian affinity matrix, compute the normalized Laplacian, extract the top-k eigenvectors, row-normalize, then run k-means in that space. Using matrix perturbation theory, the authors prove that when clusters are well-separated, the algorithm provably recovers them. The row- step — mapping points to the unit sphere — is key to handling clusters of varying connectivity.

The impact

The NJW algorithm became the standard reference for spectral clustering, cited over 10,000 times. It established spectral methods as a practical, principled alternative to k-means for non-convex data. Its ideas flow directly into graph neural networks (GNNs), where the same Laplacian eigenvectors serve as positional encodings, and into community detection in social networks, image , and speaker diarization.

Imagine you want to divide a city into neighborhoods. Drawing circles on a map (k-means) works for grid-planned cities — but not for a city built along a winding river, where two houses on opposite banks are close as the crow flies yet belong to different communities.

Spectral clustering takes a different approach: it looks at which houses are actually connected by streets — the road network — then listens to the network's natural "resonance frequencies" (eigenvectors). Each frequency highlights a different way the city naturally splits. Group by those frequencies, and the river banks separate themselves.

The ceiling: k-means only sees convex blobs

K-means assigns each point to its nearest centroid, which means it implicitly draws Voronoi cells — convex polygons — around each center. This works perfectly when clusters are roughly spherical. But what about two concentric rings? Or a crescent wrapped around a ball? K-means will slice through them because it can only think in straight-line distances to centroids.

The key insight behind spectral clustering is to stop thinking about where points are and start thinking about how they're connected. Two points in the same ring are connected by a chain of nearby points; two points in different rings have no such chain, even if they're spatially close. If we can capture this connectivity structure, we can cluster any shape.

Open in Lab

Toggle between k-means and spectral clustering on concentric rings. Notice how k-means cuts through the rings while spectral clustering separates them cleanly.

The demo wakes as you arrive…

Step 1: Build a similarity graph

The first step is to translate raw data points into a graph. Given $n$ points $s_1, \ldots, s_n$ , we build an affinity matrix $A$ where entry $A_{ij}$ measures how similar points $i$ and $j$ are. The paper uses a Gaussian (RBF) :

Every pair of points gets a score that decays exponentially with squared distance. The parameter $\sigma$ controls the radius of "friendship": small $\sigma$ means only very close points are friends; large $\sigma$ means even distant points share some connection. The diagonal is set to zero ( $A_{ii} = 0$ ) so no point is its own neighbor.

Think of the affinity matrix as an of a weighted graph: each point is a node, and the edge weight between two nodes reflects how strongly they're connected.

A_{ij} = \begin{cases} \exp\!\bigl(-\|s_i - s_j\|^2 / 2\sigma^2\bigr) & i \neq j \\ 0 & i = j \end{cases}

Gaussian affinity matrix — Each off-diagonal entry is a Gaussian-weighted similarity. σ controls the neighborhood scale: small σ → tight neighborhoods, large σ → broad neighborhoods.

Open in Lab

Drag σ to see how the affinity matrix changes. Small σ produces a sparse, block-like matrix; large σ produces a dense, uniform one.

The demo wakes as you arrive…

Step 2: The normalized graph Laplacian

Raw affinity alone isn't enough — nodes in dense regions have many strong connections, while isolated nodes have few. To level the playing field, the algorithm normalizes the affinity matrix. First, define the $D$ : a diagonal matrix where $D_{ii}$ equals the sum of the $i$ -th row of $A$ — essentially how "popular" each node is. Then form the normalized Laplacian:

This normalization ensures that each node's connections are measured relative to its own popularity. It's like adjusting for the fact that a celebrity has many weak connections while a small-town resident has few but strong ones — after normalization, both contribute equally to the clustering.

L = D^{-1/2}\, A\, D^{-1/2}

Normalized graph Laplacian (NJW variant) — D is diagonal with D_ii = Σⱼ A_ij. Multiplying by D^{-1/2} on both sides normalizes each entry by the geometric mean of the two endpoints' degrees.

Step 3: Eigenvectors reveal the hidden cluster map

Here is the core magic. If the data has $k$ perfectly separated clusters (no edges between them), the normalized Laplacian $L$ would be block-diagonal, and its top $k$ eigenvectors would be indicator vectors — each one constant within a cluster and zero outside it. Stacking those eigenvectors as columns gives a matrix $X$ where rows belonging to the same cluster are identical. Running k-means on those rows trivially recovers the clusters.

In the real world, clusters aren't perfectly separated — there are weak cross-cluster edges. Matrix perturbation theory tells us that small perturbations to a block-diagonal matrix produce small perturbations in its eigenvectors. So the rows of $X$ won't be identical within a cluster, but they'll be close — close enough for k-means to separate them.

Think of it this way: the eigenvectors are like tuning forks for the graph. Each one resonates with a different natural grouping. Points that vibrate together in the same pattern belong together.

Open in Lab

See how the top eigenvectors of the Laplacian assign similar values to points in the same cluster. Each eigenvector highlights a different cluster boundary.

The demo wakes as you arrive…

Step 4: Row normalization — projecting to the sphere

After extracting the top $k$ eigenvectors into a matrix $X$ , the algorithm normalizes each row to have unit length, producing a matrix $Y$ where $Y_{ij} = X_{ij} / (\sum_j X_{ij}^2)^{1/2}$ . This maps every point to the surface of a unit sphere in $k$ -dimensional space.

Why? Without normalization, points in loosely connected clusters get smaller eigenvector entries than points in tightly connected clusters. Row normalization erases this density-dependent scaling, so k-means treats all clusters equally regardless of how dense they are internally. It's like making every person's vote count equally, whether they live in a dense city or a sparse countryside.

The authors note this step is "cosmetic" — it can sometimes be skipped — but in practice it dramatically improves results on data with varying cluster densities.

Y_{ij} = \frac{X_{ij}}{\bigl(\sum_{j} X_{ij}^2\bigr)^{1/2}}

Row normalization to the unit sphere — Each row of the eigenvector matrix is scaled to unit length. This projects all points onto a hypersphere, making the representation invariant to cluster density.

The full NJW algorithm

The beauty of the NJW algorithm is its simplicity — implementable in a few lines of code, yet backed by rigorous theory. Here is the full pipeline:

Open in Lab

Click each step to see what happens at that stage of the algorithm. The final k-means step operates in the eigenvector space, not the original data space.

The demo wakes as you arrive…

The σ parameter: how wide is 'nearby'?

The scaling parameter $\sigma$ in the Gaussian kernel is the single most important . It defines the scale at which the algorithm perceives structure:

Too small: Only the nearest neighbors have non-zero affinity. The graph fragments into many tiny disconnected components, and eigenvectors become noisy.
Too large: All points are equally connected. The graph becomes nearly uniform, and eigenvectors lose the ability to discriminate clusters.
Just right: Points within a cluster are strongly connected, points between clusters are weakly connected, and the eigenvectors cleanly separate the groups.

The paper demonstrates that with the right $\sigma$ , the algorithm's theoretical guarantees kick in. In practice, choosing $\sigma$ often requires domain knowledge or heuristics like using the median pairwise distance. Later work by Zelnik-Manor and Perona (2004) introduced local scaling — adaptive per-point $\sigma_i$ — to handle multi-scale data automatically.

Open in Lab

Drag the σ slider to see the sweet spot between a fragmented graph (too small) and a uniform blob (too large).

The demo wakes as you arrive…

Why it works: the matrix perturbation argument

The theoretical backbone of the paper uses the Davis-Kahan theorem from matrix perturbation theory. The argument goes like this:

Imagine we have an "ideal" affinity matrix $\hat{A}$ that is perfectly block-diagonal — zero affinity between clusters. Its top- $k$ eigenvectors are perfect indicator vectors. The real affinity matrix $A$ is a perturbation of $\hat{A}$ : $A = \hat{A} + H$ , where $H$ contains the small cross-cluster affinities.

Davis-Kahan tells us that the eigenvectors of $A$ are close to those of $\hat{A}$ when the perturbation $\|H\|$ is small relative to the eigengap $\delta$ (the gap between the $k$ -th and $(k+1)$ -th eigenvalues). Specifically, the angle between the true and ideal eigenvector subspaces is bounded by $O(\|H\| / \delta)$ .

So when clusters are well-separated (small $\|H\|$ , large $\delta$ ), the rows of the eigenvector matrix $X$ form tight clusters near the ideal indicator positions, and k-means can recover them.

The same idea in code

The NJW spectral clustering algorithm, completepython

Simplified to show the idea — not the real implementation.

import numpy as np
from scipy.spatial.distance import pdist, squareform
from sklearn.cluster import KMeans

def spectral_clustering(data, k, sigma):
    """Ng-Jordan-Weiss spectral clustering.
       data: (n, d) array of points
       k: number of clusters
       sigma: Gaussian kernel bandwidth
    """
    # Step 1: Build affinity matrix
    dists = squareform(pdist(data, 'sqeuclidean'))
    A = np.exp(-dists / (2 * sigma ** 2))
    np.fill_diagonal(A, 0)          # no self-loops

    # Step 2: Normalized Laplacian  L = D^{-1/2} A D^{-1/2}
    D_inv_sqrt = np.diag(1.0 / np.sqrt(A.sum(axis=1)))
    L = D_inv_sqrt @ A @ D_inv_sqrt

    # Step 3: Top-k eigenvectors
    eigenvalues, eigenvectors = np.linalg.eigh(L)
    X = eigenvectors[:, -k:]        # largest k

    # Step 4: Row-normalize → project to unit sphere
    norms = np.linalg.norm(X, axis=1, keepdims=True)
    Y = X / norms

    # Step 5: K-means in eigenvector space
    labels = KMeans(n_clusters=k).fit_predict(Y)
    return labels

Practical insights: when to use spectral clustering

Spectral clustering shines in specific situations, but it's not a universal replacement for k-means. Here's when to reach for it:

Non-convex clusters — rings, spirals, manifolds. If your data has complex geometric structure, spectral clustering can separate what k-means cannot.
Graph-structured data — social networks, citation graphs, biological networks. The affinity matrix is already given by the graph's adjacency.
Image segmentation — pixels form a natural grid graph, and spectral clustering identifies regions by connectivity.

And when to be cautious:

Large datasets — the algorithm requires computing and decomposing an $n \times n$ matrix, making it $O(n^3)$ . For large $n$ , approximate methods or Nyström approximations are needed.
Choosing σ and k — unlike k-means which only needs $k$ , spectral clustering also needs $\sigma$ . The eigengap heuristic helps with $k$ , but $\sigma$ requires care.
No out-of-sample extension — new points require re-running the entire algorithm (a limitation shared with t-SNE).

Impact: from clustering to graph neural networks

2000
Shi & Malik — Normalized Cuts
Introduced spectral graph partitioning for image segmentation using the normalized cut criterion. Showed that the optimal cut is given by the second eigenvector of the generalized eigenvalue problem.
2001
Ng, Jordan, Weiss — NJW Algorithm
Unified spectral clustering with a simple, analyzable algorithm. First theoretical guarantees via matrix perturbation theory. Over 10,000 citations.
2004
Zelnik-Manor & Perona — Self-Tuning
Replaced the global σ with local scaling σᵢ per point, automatically adapting to multi-scale data. Also proposed automatic k selection via eigenvector alignment.
2007
Von Luxburg — Tutorial on Spectral Clustering
A definitive tutorial deriving spectral algorithms from multiple perspectives — graph cuts, random walks, and perturbation theory. Became the standard reference for teaching the subject.
2017
Graph Convolutional Networks (GCN)
Kipf & Welling used the same normalized Laplacian from spectral clustering as the foundation for learnable graph convolutions. Spectral clustering's math became the bridge to deep learning on graphs.
2020
Spectral GNNs & Positional Encodings
Laplacian eigenvectors — the same ones used in spectral clustering — became standard positional encodings in graph transformers, carrying spectral clustering's ideas into the era of foundation models.

The NJW paper's most lasting contribution may not be the algorithm itself, but the insight that the Laplacian's eigenvectors encode the natural grouping structure of a graph. This idea flows directly into graph convolutional networks, where Laplacian eigenvectors serve as the graph's "Fourier basis," enabling on irregular structures. Every time a learns to classify nodes or predict molecular properties, it builds on the foundation laid by spectral clustering.

CitationNg, Jordan, Weiss. On Spectral Clustering: Analysis and an Algorithm. NeurIPS, 2001.

Terms in this paper

Clusteringالعنقَدة
Eigenvectorالمتجه الذاتي
Eigenvalueالقيمة الذاتية
Graph Laplacianلابلاسيان الرسم البياني
Adjacency Matrixمصفوفة التجاور
Degree Matrixمصفوفة الدرجات
k-means Clusteringالعنقَدة بـ k-متوسطات
Similarityدرجة التشابه
Kernelالنواة الحسابية
Dimensionality Reductionاختزال وتقليص الأبعاد الحسابية
Manifoldالمتشعب الهندسي
Gaussian Distributionالتوزيع الغاوسي
Normalizationالمعايرة القياسية للبيانات