Spectral clustering: how eigenvectors of the graph Laplacian reveal cluster structure

From points to a similarity graph

Spectral clustering starts by throwing away Euclidean distance as the primary signal and building a similarity graph instead: a weighted graph where an edge weight w_ij measures how "close" points i and j are. The most common choice is a Gaussian (RBF) kernel restricted to a neighbourhood:

The key idea: two points can be "close" in graph terms — connected through a chain of nearby neighbours — even if they're far apart in straight-line distance. That's exactly what lets spectral clustering trace a crescent or a spiral as a single connected region.

The graph Laplacian

Given the weighted adjacency matrix W and the diagonal degree matrix D (D_ii = Σⱼ w_ij), the unnormalized graph Laplacian is:

That quadratic form is the whole story: xᵀLx is small exactly when strongly-connected points i, j are assigned similar values xᵢ, xⱼ. Minimizing it is a smoothness constraint over the graph — and its minimizers are the low eigenvectors of L. In practice the normalized Laplacian is preferred, since it corrects for wildly different node degrees:

The Fiedler vector and graph cuts

L is positive semi-definite, so all its eigenvalues are ≥ 0, and the smallest one is always 0 with eigenvector 1 (constant) — for a connected graph, exactly one zero eigenvalue. The second-smallest eigenvalue λ₂ and its eigenvector, the Fiedler vector, encode the graph's best "bisection": points with a positive entry in the Fiedler vector form one side of a low-weight cut, negative entries form the other.

Normalized cut and the relaxation trick

Formally, we'd like to partition the graph into k groups minimizing the total edge weight cut between groups, normalized by group size so the optimizer can't just isolate a single outlier node (Ncut, Shi & Malik, 2000). Solving this exactly is NP-hard — it's a discrete combinatorial problem. The trick is to relax the discrete ±1 cluster-membership constraint into continuous real values, which turns Ncut minimization into:

The relaxed solution is exactly the eigenvectors of the generalized eigenproblem Lx = λDx (equivalently, the eigenvectors of L_rw). Rounding the continuous eigenvector solution back to discrete cluster labels — usually with plain k-means in the eigenvector space — recovers an approximate but usually excellent Ncut partition.

The algorithm in JavaScript

Putting it together: build the similarity graph, compute the first k eigenvectors of the normalized Laplacian, stack them as columns to get an n×k embedding, then run k-means on the rows of that embedding.

function spectralClustering(points, k, sigma = 1.0, kNN = 10) {
  const n = points.length;
  const W = buildKnnSimilarityGraph(points, kNN, sigma); // n×n sparse weights
  const D = W.map(row => row.reduce((a, b) => a + b, 0));

  // Symmetric normalized Laplacian: L_sym = I - D^-1/2 W D^-1/2
  const Lsym = identity(n).map((row, i) =>
    row.map((_, j) => (i === j ? 1 : 0) − W[i][j] / Math.sqrt(D[i] * D[j]))
  );

  // Smallest k eigenvectors (excluding the trivial constant one)
  const { eigenvectors } = symmetricEigenDecomposition(Lsym);
  const embedding = eigenvectors.slice(0, k); // k smallest, columns

  // Row-normalize (Ng-Jordan-Weiss trick) then cluster with k-means
  const rows = transposeAndNormalizeRows(embedding, n, k);
  return kMeans(rows, k);
}

Choosing k: the eigengap heuristic

Unlike k-means, spectral clustering gives you a principled way to pick k without a separate silhouette sweep: plot the sorted eigenvalues λ₁ ≤ λ₂ ≤ … and look for the largest jump (eigengap) — |λ_k+1 − λ_k|. A large gap after λ_k suggests k well-separated clusters, because k eigenvalues are clustered near zero and the rest jump away sharply.

Where spectral clustering wins

Spectral clustering's real strength is that it makes almost no assumption about cluster shape — only about graph connectivity — which is precisely where centroid-based methods like k-means break down.

• Image segmentation: the original Shi-Malik Ncut application — pixels as nodes, brightness/texture similarity as edges.
• Community detection: finding tightly-knit groups in social or citation networks.
• Non-convex clusters: concentric rings, spirals, and interlocking moons that defeat k-means outright.
• Dimensionality reduction: the eigenvector embedding itself (Laplacian Eigenmaps) is used as a manifold-learning technique independent of clustering.
• Speech and audio segmentation: speaker diarization pipelines often cluster embedding similarity graphs spectrally.