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 σ is a scale parameter. Small σ makes the graph local: only genuinely near neighbours matter, and distant structure is ignored. Large σ makes the graph dense and blurs local detail. There is no universally correct σ , 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 * (W + W.T)

# Step 2: symmetric normalised Laplacian
L_sym = csgraph.laplacian(W, normed=True)

# Step 3: two smallest eigenvectors
_, U = eigsh(L_sym, k=2, which="SM")

# Step 4: row normalisation to unit length
T = U / np.linalg.norm(U, axis=1, keepdims=True)

# Step 5: k-means in embedding space
labels = KMeans(n_clusters=2, n_init=10, random_state=0).fit_predict(T)

Run this, and the two moons are recovered almost perfectly, where plain k-means on X cuts each moon in half. Two details are worth noting. First, the graph uses connectivity weights, not Gaussian weights, which is enough when the neighbour structure is what matters. Second, only two eigenvectors are needed for two clusters, but in general you need k eigenvectors for k clusters, and choosing k is a modelling decision, not something the eigenvectors decide for you.

A useful diagnostic is the eigengap: the difference between successive eigenvalues. If λk+1​−λk​ is large relative to neighbouring gaps, then k is a natural number of clusters, because the first k eigenvectors are well separated from the rest. The eigengap heuristic is not a proof, and it can be noisy on real data, but a large gap at k is genuine evidence that the graph has roughly k weakly connected regions, and a flat spectrum with no clear gap is a warning that the cluster structure is weak or that the graph construction is wrong.

Limitations and common pitfalls

Spectral clustering is powerful, but it is not a default to reach for blindly. Its failure modes are specific, and recognising them saves a lot of wasted tuning.

Graph construction dominates everything. A poor similarity graph gives poor eigenvectors, and no amount of eigenvector fiddling fixes it. If σ is too small, the graph fragments into many tiny components and the eigenvectors describe fragments, not clusters. If σ is too large, distinct clusters bleed into each other. If features are on wildly different scales and are not standardised, Euclidean distances in the kernel are meaningless. Standardise features, inspect the graph, and try a k-nearest-neighbour graph before blaming the eigensolver.

Choosing the number of clusters is still hard. Spectral clustering does not discover k . The eigengap helps, but on messy data it is ambiguous, and the method will happily return k clusters for any k you ask for. Validate the result with domain knowledge, stability across subsamples, or a downstream task, not with the fact that the algorithm produced an answer.

It scales badly in its naive form. A dense eigendecomposition costs on the order of n3 time, and a dense similarity matrix costs n2 memory. That rules out naive spectral clustering for very large data. Practical workarounds include sparse k-nearest-neighbour graphs with iterative eigensolvers, Nyström approximations that compute eigenvectors from a landmark subset, and landmark-based methods that cluster a sample and assign the rest. Each approximation trades accuracy for scale, and the trade should be checked, not assumed.

Degree heterogeneity can mislead unnormalised versions. In graphs where some nodes have much higher degree than others, the unnormalised Laplacian can be dominated by high-degree structure. The normalised Laplacians correct for this, which is why they are the default in practice. If you use the unnormalised Laplacian, you should have a reason, not just a habit.

It is not probabilistic and not density-based. Spectral clustering returns a hard partition, with no uncertainty, no density estimate, and no notion of an outlier. A point far from everything will still be assigned to some cluster, and a point on a bridge between clusters will be assigned to one side without any flag. If you need outlier detection, soft assignments, or a generative model of the clusters, use a method that provides them, or add that layer yourself on top of the embedding.

High dimensions hurt the graph first. In high-dimensional spaces, Euclidean distances concentrate, nearest neighbours become less meaningful, and the similarity graph becomes less informative. Spectral clustering on raw high-dimensional features often underperforms. Dimensionality reduction, feature selection, or a learned similarity is usually needed first, and at that point the quality of the result depends more on that step than on the spectral step.

When to use it, and when not to

Use spectral clustering when clusters have non-convex shapes, when the data lie on a low-dimensional manifold, when you have a natural similarity measure that is not Euclidean distance in the raw space, or when you can build a good graph from domain knowledge, for example a citation graph, a social graph, or a graph built from co-occurrence. Image segmentation is a classic success: pixels are nodes, similarity combines colour and spatial closeness, and the normalised cut objective directly expresses the idea that a segment should be internally coherent and separated by weak boundaries.

Do not use it as a first attempt on large data, on data where clusters are already round and well separated, where k-means or a Gaussian mixture model is simpler and faster, or where you need a probabilistic interpretation. Spectral clustering earns its complexity when geometry matters. When geometry does not matter, it is an expensive way to get the same answer as a simpler method.

Takeaway

Spectral clustering works because it changes the problem before solving it. It replaces points in Euclidean space with nodes in a graph, replaces cluster shape with graph connectivity, and replaces a hard discrete cut with a continuous eigenvalue problem whose solution is computable. The eigenvectors of the Laplacian are smooth functions on the graph, and smooth functions that respect the graph are, to a good approximation, cluster indicators. Embed the data in those eigenvectors, and a simple method like k-means can finish a job it could not start in the original space.

The method repays careful graph construction and punishes careless scaling, and it should be judged on the graph you actually built, not on the idealised graph in a textbook. Get the graph right, check the eigengap, normalise the rows of the embedding, and spectral clustering will reveal structure that centre-based methods cannot see.

Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial