Clustering Through the Graph Laplacian

Non-convex shapes that defeat k-means fall apart cleanly in the spectral embedding.

Ch 8 8.5

Explorer

Unsupervised Learning & Text

22 mindifficulty 4/5

Controls

Dataset

Pointsn100

Noise0.080

Perturbation added to the generating curve.

Affinity graph

Bandwidthσ0.250

Controls how quickly similarity decays with distance.

Clustersk2

Random seed

Every result on this page is a deterministic function of the seed and the controls.

Spectral clustering

Points colored by cluster label from the graph embedding.

k-means in original space

Same points; Euclidean k-means fails on non-convex shapes.

Spectral embedding

Fiedler vector (2nd eigenvector) vs the 3rd, colored by spectral label.

Eigenvalue spectrum

Smallest eigenvalues of the normalized Laplacian; the eigengap is highlighted.

Eigengap

0.2093

largest jump after index 4

Bandwidth σ

0.250

Spectral vs truth (ARI)

0.543

adjusted Rand index

k-means vs truth (ARI)

0.404

Euclidean k-means, same k

Read the eigengap

The number of near-zero eigenvalues of the normalized Laplacian is (approximately) the number of well-separated clusters in the affinity graph. A large jump — the eigengap — after the k-th eigenvalue is evidence that k clusters is the right choice; a small, ambiguous gap means the graph does not cleanly separate into k pieces.

Predict before you look

On the two-moons dataset, which method will separate the two moons correctly?

Scenarios

Teacher-ready starting points.

Documentation

What this shows

A toy dataset (moons, circles, blobs, or spirals) is turned into a similarity graph via a Gaussian or k-nearest-neighbor affinity. The graph's normalized Laplacian is eigendecomposed, the smallest eigenvectors form a new embedding, and k-means run on that embedding is compared against k-means run directly on the raw coordinates.

The normalized graph Laplacian

Given an affinity matrix W with degree matrix D = diag(Σⱼ Wᵢⱼ), the symmetric normalized Laplacian is L_sym = I − D^(−1/2) W D^(−1/2). It is positive semi-definite, and its smallest eigenvalue is always 0 with eigenvector proportional to D^(1/2)𝟙.

If the graph has k well-separated connected components, L_sym has an eigenvalue 0 with multiplicity k (approximately, for noisy near-components). Stacking the k smallest eigenvectors as columns gives an n×k embedding in which points from the same component collapse together — even when the original data manifold is curved.

Running k-means on the row-normalized embedding (Ng–Jordan–Weiss) recovers the components because straight-line k-means in the embedding space corresponds to graph-community structure, not to Euclidean shape in the original space. The eigengap — the jump between the k-th and (k+1)-th eigenvalue — is the standard diagnostic for choosing k.

L_sym = I − D^{-1/2} W D^{-1/2}

L_sym u_i = λ_i u_i,  0 = λ_1 ≤ λ_2 ≤ … ≤ λ_n

embedding: y_i = (u_1(i), …, u_k(i)) / ‖(u_1(i), …, u_k(i))‖

eigengap: Δ_k = λ_{k+1} − λ_k

Try this

Load two moons with σ ≈ 0.25. Compare the spectral ARI and k-means ARI readouts directly.
Slide σ from 0.1 to 2 on the same dataset and watch the eigengap shrink and the spectral labels degrade.
Switch to concentric circles: k-means centroids cannot separate rings sharing a common center, but the graph Laplacian can.
Compare full Gaussian affinity against kNN affinity at matched σ — sparsification often produces a cleaner eigengap.
Raise noise toward 1 on spirals and find the point where even spectral clustering's eigengap collapses.

Common misconception

“Clustering means finding groups that are round blobs in space, so k-means is 'the' clustering algorithm.”

k-means partitions space by Euclidean distance to centroids, which only recovers convex, roughly spherical groups. Spectral clustering instead asks which points are locally connected on a similarity graph, so it recovers clusters defined by connectivity and shape — moons, rings, spirals — that are not separable by any set of centroids.

8.3 Clustering Geometry: When k-Means Fails