Spectral Clustering: Why the Eigenvectors of a Graph Laplacian Reveal Clusters

K-means is the first clustering method most people learn, and it is also the first one to fail in an instructive way. Give it two interleaving crescents, two concentric rings, or a long thin chain next to a dense ball, and it will cut straight through the structure you can see with your eyes. The failure is not a tuning problem. K-means assumes clusters are round blobs around a centre, and it measures closeness in raw Euclidean distance. When the shape of a cluster matters more than its centre, that assumption is wrong.

Spectral clustering takes a different route. Instead of clustering points directly, it first turns the data into a graph, then asks a linear algebra question about that graph: which smooth, low-energy functions on the graph separate one region from another? The answer is given by the smallest eigenvectors of the graph Laplacian. Cluster in that eigenvector space, and crescents, rings, and chains suddenly become easy. This article explains what the Laplacian is, why its eigenvectors encode cuts, how the full algorithm works, and where it breaks down.

From points to a graph

Start with data points x1​,…,xn​ . Spectral clustering does not work on the points themselves. It works on a weighted graph in which each point is a node and each edge weight wij​ measures how similar points $i$ and $j$ are. Similar points get a heavy edge, dissimilar points get a light edge or no edge at all. The clustering problem then becomes a graph partitioning problem: cut the graph into pieces so that few heavy edges are cut and each piece is internally well connected.

The graph construction is the first real decision, and it matters more than most textbooks admit. Three common choices are:

• Epsilon neighbourhood graph: connect points closer than some radius $ϵ$ .
• k-nearest-neighbour graph: connect each point to its $k$ nearest neighbours, usually symmetrised by keeping an edge if either endpoint lists the other.
• Fully connected graph with a Gaussian kernel: connect everything, with weight decaying with distance.

The Gaussian kernel is the usual default for a fully connected graph:

Here $\sigma$ is a scale parameter. Small $\sigma$ makes the graph local: only genuinely near neighbours matter, and distant structure is ignored. Large $\sigma$ makes the graph dense and blurs local detail. There is no universally correct $\sigma$ , and a bad one can destroy the result before any eigenvectors are computed. In practice, a k-nearest-neighbour graph is often more robust than a fully connected Gaussian graph, because it adapts to varying density: a point in a sparse region still gets neighbours, and a point in a dense region is not swamped by weak long-range edges.

Collect the weights into a similarity matrix $W$ , with entries wij​ and zeros on the diagonal. Define the degree of node $i$ as the total weight of its edges:

Put the degrees on the diagonal of a matrix $D$ . The unnormalised graph Laplacian is then:

That simple definition carries a surprising amount of structure.

What the Laplacian measures

Take any function $f$ on the nodes, a vector with one value fi​ per point. The quadratic form fTLf has a clean expansion:

Read that carefully, because it is the whole intuition in one line. The quadratic form is a weighted sum of squared differences across edges. If $f$ assigns similar values to strongly connected points, the sum is small. If $f$ jumps across a heavy edge, the sum is large. So a function with small fTLf is smooth on the graph: it varies slowly inside well-connected regions and only changes where the graph is weakly connected.

That is exactly what a cluster indicator should do. An ideal cluster indicator is constant inside each cluster and jumps only between clusters. If clusters correspond to weakly connected regions, the jump crosses only light edges, so the quadratic form stays small. Spectral clustering is, in this sense, a search for smooth functions on the graph.

The Laplacian is symmetric and positive semidefinite, so its eigenvalues are real and non-negative. Sort them as 0=λ1​≤λ2​≤⋯≤λn​ , with eigenvectors u1​,…,un​ . The smallest eigenvalue is always zero, with the constant vector as its eigenvector: a constant function has no variation across any edge, so its quadratic form is zero. The interesting structure lives in the next few eigenvectors.

The multiplicity of the zero eigenvalue has a precise meaning: it equals the number of connected components of the graph. If the graph has two disconnected components, there are two zero eigenvalues, and their eigenvectors can be chosen as indicators of the two components. This is the clean case. In real data the graph is usually connected, but if it is nearly disconnected, with two regions joined only by light edges, then λ2​ is small but positive, and the corresponding eigenvector, the Fiedler vector, is approximately constant on each region with a jump between them. Its sign alone often gives a good two-way split. That is the core insight: small eigenvectors are soft, continuous versions of cluster indicators.

From cuts to eigenvectors

Why should eigenvectors be the right objects, rather than some other smooth functions? The answer comes from graph cut objectives. Suppose we want to split the nodes into two sets $A$ and its complement. The cut weight is the total weight of edges crossing the split:

Minimising the cut alone is a bad objective: it is minimised by peeling off a single isolated node, which cuts almost nothing but is not a cluster. The standard fixes balance the cut against the size or volume of the pieces. The RatioCut divides by the number of nodes in each piece, and the Normalised Cut divides by the volume, the sum of degrees, of each piece:

where vol(A)=∑i∈A​di​ . Normalised Cut penalises cutting off a tiny low-degree piece, because its volume is small and the ratio is large. This is usually the objective you want.

Minimising Normalised Cut exactly over discrete partitions is NP-hard. Spectral clustering solves a relaxation: allow the indicator to take continuous values instead of just two values, and constrain its norm. The relaxed problem is a generalised eigenvalue problem, and its solution is given by the smallest eigenvectors of a normalised Laplacian. There are two standard normalisations:

The symmetric normalised Laplacian Lsym​ is symmetric, so its eigenvectors are orthogonal and numerically well behaved. The random-walk Laplacian Lrw​ has the same eigenvalues, and its eigenvectors are related by a scaling with D1/2 . The random-walk view is worth knowing because it gives a second intuition: D−1W is the transition matrix of a random walk on the graph, moving from a node to a neighbour with probability proportional to edge weight. A random walk stays inside a cluster for a long time before escaping, so the slow modes of the walk, the eigenvectors with eigenvalues near one, describe clusters. Spectral clustering and slow random-walk modes are two descriptions of the same object.

In short, the relaxation is not a heuristic bolted on afterwards. The eigenvectors are the exact solution of the relaxed cut problem, and the relaxation is tight when the clusters are well separated.

The algorithm, step by step

The widely used Ng-Jordan-Weiss version of the algorithm, for $k$ clusters, is:

1. Build a similarity graph and its weight matrix $W$ , as above.
2. Compute the normalised Laplacian, usually Lsym​ .
3. Compute its $k$ smallest eigenvectors, and stack them as columns of a matrix $U$ with $n$ rows and $k$ columns.
4. Normalise each row of $U$ to unit length, giving a matrix $T$ . Each row of $T$ is the new representation of one data point, in $k$ -dimensional spectral embedding space.
5. Run k-means on the rows of $T$ . Assign each original point to the cluster of its row.

Step 4 deserves emphasis, because it is easy to skip and hard to recover from. Row normalisation projects each point onto the unit sphere in embedding space, which corrects for degree differences: without it, high-degree nodes can dominate the geometry of the embedding. With it, points in the same cluster tend to point in the same direction, and k-means on directions works well even when the raw embedding is stretched.

Why does k-means work in embedding space when it failed in the original space? Because the embedding has already done the hard geometric work. Two crescents that are interleaved in the original plane become two well-separated blobs, or two distinct directions, in spectral space. The eigenvectors unfold the manifold structure of the graph into a space where Euclidean distance finally means something like graph distance. Spectral clustering is best understood as representation learning followed by a simple clustering step, not as a clustering method that happens to use eigenvectors.

A concrete example

The following short example builds two moons, constructs a k-nearest-neighbour graph, computes the normalised Laplacian eigenvectors, and clusters in embedding space. It uses scikit-learn for the data and the eigensolver, and numpy for the rest. The point is not the library call, which hides the machinery, but the shape of the pipeline: graph, Laplacian, eigenvectors, embedding, k-means.

import numpy as np from sklearn.datasets import make_moons from sklearn.neighbors import kneighbors_graph from sklearn.cluster import KMeans from scipy.sparse.linalg import eigsh from scipy.sparse import csgraph X, _ = make_moons(n_samples=400, noise=0.05, random_state=0) # Step 1: k-nearest-neighbour graph, symmetrised W = kneighbors_graph(X, n_neighbors=10, mode="connectivity") W = 0.5 * ...