Spectral clustering

Embed points with the bottom eigenvectors of a similarity graph's Laplacian, then run k-means in that space.

18 min read1845 wordsadvanced15 viewsupdated 2026-10-07

Definition

Spectral clustering turns the data into a similarity graph — points are nodes, and strongly similar points are joined by heavy edges — and looks for the partition that cuts as little edge weight as possible. Finding that cut exactly is intractable, so it is relaxed into an eigenvector problem: the bottom kk eigenvectors of the graph's Laplacian give every point new coordinates, and in those coordinates plain k-means finds clusters that may be curved, nested or elongated in the original space.

At a glance

Task
Clustering (unsupervised); also graph partitioning / community detection
Input → output
nn points (or any n×nn\times n similarity matrix) and kk → a cluster label per point
Learns
nothing parametric: an n×kn\times k spectral embedding of the training points, then k-means centroids in that space
Training cost
O(n2d)O(n^2 d) to build a dense affinity matrix, O(n3)O(n^3) for a dense eigendecomposition; much less with a sparse kNN graph and a Lanczos / LOBPCG solver for only kk eigenvectors
Prediction cost
none built in (transductive). A new point needs a re-fit, or the Nyström extension at O(nk)O(nk)
Hyperparameters
kk; the graph (RBF bandwidth γ\gamma or number of neighbours); which Laplacian; how labels are assigned (k-means, discretize, QR)
Assumes
clusters are groups that are well connected inside and weakly connected to each other under your similarity — not that they are round, convex or Gaussian

The problem

k-means (see K-Means) assigns each point to the nearest centroid, so every cluster is a convex Voronoi cell; a Gaussian mixture (see Gaussian mixtures & EM) generalizes the cells to ellipses. Both describe a cluster by where its centre is. Many real clusters are not like that: two interleaved half-moons, a ring around a disc, a road network, pixels of one object in an image. What makes them a group is that you can walk from any member to any other in small steps without leaving the group — connectivity, not compactness.

The smallest example is two parallel rows of five points, 1 apart along each row and 1.5 apart between rows (the worked example below). The "obvious" clusters are the rows. k-means with k=2k=2 disagrees: splitting into rows costs a within-cluster sum of squares of 2020, while cutting the picture into a left block of 4 points and a right block of 6 costs only 10.62510.625, so k-means picks the vertical cut. It is not a bad initialization — it is the k-means objective itself preferring compact blobs.

Density-based methods (DBSCAN, HDBSCAN, OPTICS) also follow connectivity, by growing clusters through dense regions. Spectral clustering takes a different route: it states the "cut few edges" goal as an optimization over a graph and solves a continuous relaxation of it exactly, with linear algebra.

The idea

Build a graph whose edge weights say how similar two points are, with weights that fall off fast with distance so only near neighbours are strongly linked. A good clustering is then a cut: remove the edges between groups, and you want the removed weight to be small while each group stays reasonably large.

Now imagine assigning every node a number fif_i and charging wij(fi−fj)2w_{ij}(f_i-f_j)^2 for every edge. Numbers that vary smoothly along heavy edges are cheap; numbers that jump across a heavy edge are expensive. The cheapest non-constant assignment, subject to a normalization, is an eigenvector of the graph Laplacian — and it is nearly constant inside each well-connected group and changes where the edges are weak. Plot each point at its eigenvector values and the curved clusters collapse into tight blobs, which k-means then separates trivially.

Vocabulary

Similarity graph
nodes = data points; an edge (i,j)(i,j) with weight wij≥0w_{ij}\ge0 when ii and jj are similar
Affinity matrix W
the n×nn\times n symmetric matrix of edge weights, zero diagonal. Built by an RBF kernel, a kNN graph, or an ε\varepsilon-neighbourhood graph — or given directly (e.g. a social network)
Degree
di=∑jwijd_i=\sum_j w_{ij}, the total edge weight at node ii; D=diag⁡(d1,…,dn)D=\operatorname{diag}(d_1,\dots,d_n)
Volume
vol⁡(A)=∑i∈Adi\operatorname{vol}(A)=\sum_{i\in A}d_i, the "size" of a set of nodes measured in edge weight
Cut
cut⁡(A,B)=∑i∈A, j∈Bwij\operatorname{cut}(A,B)=\sum_{i\in A,\,j\in B}w_{ij}, the weight of the edges you remove to separate AA from BB
RatioCut / Ncut
cut criteria balanced by cluster size: divide each cut by ∣A∣|A| (RatioCut) or by vol⁡(A)\operatorname{vol}(A) (normalized cut)
Graph Laplacian
L=D−WL=D-W (unnormalized), Lsym=I−D−1/2WD−1/2L_{\text{sym}}=I-D^{-1/2}WD^{-1/2}, Lrw=I−D−1WL_{\text{rw}}=I-D^{-1}W (normalized)
Fiedler vector
the eigenvector of the second-smallest Laplacian eigenvalue λ2\lambda_2; its sign pattern is the relaxed best 2-way cut. λ2\lambda_2 itself is the algebraic connectivity
Spectral embedding
the n×kn\times k matrix whose columns are the bottom kk eigenvectors; row ii is the new coordinate of point ii
Eigengap
λk+1−λk\lambda_{k+1}-\lambda_k; a large gap says the graph has kk nearly separate groups

The math

Step 1 — the graph. The default (scikit-learn's affinity="rbf") is a Gaussian kernel on squared distances:

wij=exp⁡ ⁣(−γ ∥xi−xj∥2)(i≠j),wii=0,γ=12σ2w_{ij}=\exp\!\big(-\gamma\,\lVert x_i-x_j\rVert^2\big)\quad(i\ne j),\qquad w_{ii}=0,\qquad \gamma=\frac{1}{2\sigma^2}
xix_i
the ii-th data point
wijw_{ij}
similarity of points i and j, between 0 and 1
γ\gamma
bandwidth parameter: larger γ = similarity decays faster = sparser effective graph
σ\sigma
equivalent length scale: points much farther apart than σ are effectively unconnected

Step 2 — the Laplacian and its quadratic form. With DD the diagonal degree matrix, define L=D−WL=D-W. For any vector f∈Rnf\in\mathbb{R}^n, expand f⊤Lf=∑idifi2−∑ijwijfifjf^\top Lf=\sum_i d_if_i^2-\sum_{ij}w_{ij}f_if_j and write ∑idifi2=12∑ijwij(fi2+fj2)\sum_i d_if_i^2=\tfrac12\sum_{ij}w_{ij}(f_i^2+f_j^2):

f⊤Lf=12∑i,jwij (fi−fj)2  ≥0f^\top L f=\frac12\sum_{i,j}w_{ij}\,(f_i-f_j)^2\;\ge 0
L=D−WL=D-W
unnormalized graph Laplacian; symmetric, rows sum to 0
ff
any assignment of one number per node
(fi−fj)2(f_i-f_j)^2
how much f jumps across edge (i, j); weighted by the edge's strength

Three facts follow. LL is positive semi-definite, so its eigenvalues are 0=λ1≤λ2≤⋯≤λn0=\lambda_1\le\lambda_2\le\dots\le\lambda_n. The constant vector 1\mathbf 1 has f⊤Lf=0f^\top Lf=0, so λ1=0\lambda_1=0. And f⊤Lf=0f^\top Lf=0 exactly when ff is constant on every connected component — so the number of zero eigenvalues equals the number of components, and the indicator vectors of the components span that eigenspace. Real data is not perfectly disconnected, but if the clusters are joined only by light edges, the bottom eigenvectors are a small perturbation of those indicators.

Step 3 — cuts become a quadratic form. For two groups A,AˉA,\bar A, pick fi=∣Aˉ∣/∣A∣f_i=\sqrt{|\bar A|/|A|} on AA and fi=−∣A∣/∣Aˉ∣f_i=-\sqrt{|A|/|\bar A|} on Aˉ\bar A. Only edges crossing the cut contribute to the sum above, and a short calculation gives

f⊤Lf=n⋅RatioCut⁡(A,Aˉ),RatioCut⁡(A,Aˉ)=cut⁡(A,Aˉ)∣A∣+cut⁡(A,Aˉ)∣Aˉ∣f^\top L f=n\cdot\operatorname{RatioCut}(A,\bar A),\qquad \operatorname{RatioCut}(A,\bar A)=\frac{\operatorname{cut}(A,\bar A)}{|A|}+\frac{\operatorname{cut}(A,\bar A)}{|\bar A|}
cut⁡(A,Aˉ)\operatorname{cut}(A,\bar A)
total weight of edges between the two groups
∣A∣|A|
number of points in A; dividing by it punishes tiny groups
Aˉ\bar A
the complement of A

This ff also satisfies f⊥1f\perp\mathbf 1 and ∥f∥2=n\lVert f\rVert^2=n. Minimizing over the 2n2^n discrete choices of AA is NP-hard. Relax: let ff be any real vector with those two constraints. By the Rayleigh–Ritz (Courant–Fischer) theorem the minimum of f⊤Lf/f⊤ff^\top Lf/f^\top f over f⊥1f\perp\mathbf 1 is λ2\lambda_2, attained by the Fiedler vector. Rounding it back — cluster by the sign of fif_i, or run k-means on its entries — gives the approximate cut.

Step 4 — normalized cut. RatioCut balances by point counts; Shi and Malik's normalized cut balances by volume, which works better when degrees vary:

Ncut⁡(A1,…,Ak)=∑c=1kcut⁡(Ac,Aˉc)vol⁡(Ac)    →relax    Lv=λDv    ⟺    Lrwv=λv    ⟺    Lsym u=λu,  u=D1/2v\operatorname{Ncut}(A_1,\dots,A_k)=\sum_{c=1}^{k}\frac{\operatorname{cut}(A_c,\bar A_c)}{\operatorname{vol}(A_c)}\;\;\xrightarrow{\text{relax}}\;\; L v=\lambda D v\;\iff\; L_{\text{rw}}v=\lambda v\;\iff\; L_{\text{sym}}\,u=\lambda u,\;u=D^{1/2}v
vol⁡(Ac)\operatorname{vol}(A_c)
sum of degrees in cluster c
Lrw=I−D−1WL_{\text{rw}}=I-D^{-1}W
random-walk Laplacian; D⁻¹W is the transition matrix P of a random walk on the graph
Lsym=I−D−1/2WD−1/2L_{\text{sym}}=I-D^{-1/2}WD^{-1/2}
symmetric normalized Laplacian — same eigenvalues, eigenvectors rescaled by D^{1/2}
λ\lambda
eigenvalues lie in [0,2][0,2] for both normalized Laplacians

The same derivation with indicator entries 1/vol⁡(A)1/\sqrt{\operatorname{vol}(A)} turns Ncut into f⊤Lff^\top Lf under the constraint f⊤Df=1f^\top Df=1, and relaxing gives the generalized eigenproblem Lv=λDvLv=\lambda Dv. It has a lovely reading: Lrwv=λvL_{\text{rw}}v=\lambda v means Pv=(1−λ)vPv=(1-\lambda)v, so a small λ\lambda is a direction that a random walk barely mixes — a walker started in one cluster stays there for a long time. Ncut is exactly the probability of jumping from a cluster to the rest of the graph in one step, summed over clusters.

Step 5 — kk clusters. Stack kk scaled indicator vectors into H∈Rn×kH\in\mathbb{R}^{n\times k} with H⊤H=IH^\top H=I; then ∑cRatioCut⁡\sum_c \operatorname{RatioCut} terms equal Tr⁡(H⊤LH)\operatorname{Tr}(H^\top LH). Relaxing HH to any orthonormal matrix, the minimizer is the matrix of the bottom kk eigenvectors, and the minimum is λ1+⋯+λk\lambda_1+\dots+\lambda_k. Its rows are no longer exact indicators, so a final clustering step recovers discrete labels — k-means on the rows of the embedding. (Ng, Jordan & Weiss use LsymL_{\text{sym}} and first normalize each row to unit length; scikit-learn uses D−1/2UD^{-1/2}U, the random-walk eigenvectors.)

min⁡H⊤H=ITr⁡ ⁣(H⊤LH)=∑c=1kλc,H⋆=[ u1  u2  ⋯  uk ]\min_{H^\top H=I}\operatorname{Tr}\!\big(H^\top L H\big)=\sum_{c=1}^{k}\lambda_c,\qquad H^\star=[\,u_1\;u_2\;\cdots\;u_k\,]
HH
relaxed cluster-indicator matrix, one column per cluster
ucu_c
eigenvector of the c-th smallest eigenvalue
Tr⁡\operatorname{Tr}
trace — the sum of the k quadratic forms, one per cluster

What each hyperparameter does, mathematically

γ (or σ)
For a within-cluster neighbour at distance aa and a between-cluster neighbour at distance b>ab>a, the weight ratio is eγ(b2−a2)e^{\gamma(b^2-a^2)}: raising γ\gamma widens it, so the cut between clusters becomes cheap and λ2→0\lambda_2\to0. Too small, and WW approaches the complete graph with equal weights — every balanced cut costs about the same and the result degenerates into compact geometric halves, like k-means. Too large, and points lose all their edges, degrees →0\to0 and isolated points become their own "clusters".
n_neighbors
A kNN graph has ≈nk\approx nk edges, so it is sparse and adapts to local density (each point gets the same number of edges). Too few neighbours fragments clusters into components; too many adds bridges between clusters.
k
How many eigenvectors to keep and how many k-means clusters. The eigengap heuristic picks the kk that maximizes λk+1−λk\lambda_{k+1}-\lambda_k: with kk perfectly separated groups, λ1=⋯=λk=0<λk+1\lambda_1=\dots=\lambda_k=0<\lambda_{k+1}.
Laplacian
LL (RatioCut) balances by ∣A∣|A|; LrwL_{\text{rw}} / LsymL_{\text{sym}} (Ncut) balance by volume and are consistent as n→∞n\to\infty under milder conditions. Prefer LrwL_{\text{rw}} or LsymL_{\text{sym}}.

Worked example: two rows of points

Ten points in two rows — A along y=0y=0 and B along y=1.5y=1.5. We use the RBF graph with γ=2\gamma=2 (σ=0.5\sigma=0.5), the normalized Laplacian and k=2k=2, exactly as SpectralClustering(n_clusters=2, gamma=2) does.

PointxyPointxy
A100B101.5
A210B211.5
A320B321.5
A430B431.5
A540B541.5
The data. Neighbours along a row are 1 apart; vertically opposite points are 1.5 apart. Highlighted: row A.

Spectral clustering by hand

  1. 1Weights. Only four distances matter. Same-row neighbours (d2=1d^2=1): w=e−2=0.1353w=e^{-2}=0.1353. Vertically opposite (d2=2.25d^2=2.25): e−4.5=0.0111e^{-4.5}=0.0111. Diagonal across (d2=3.25d^2=3.25): e−6.5=0.0015e^{-6.5}=0.0015. Two apart in a row (d2=4d^2=4): e−8=0.0003e^{-8}=0.0003. Everything farther is below 10−410^{-4}. A row-neighbour edge is e2.5≈12e^{2.5}\approx12 times heavier than a vertical one.
  2. 2Degrees. End point A1: 0.1353+0.0003+0.0111+0.0015=0.14830.1353+0.0003+0.0111+0.0015=0.1483. Inner points A2, A4: 0.28510.2851; centre A3: 0.28550.2855 (B is the mirror image). Each row has volume vol⁡(A)=vol⁡(B)=1.1523\operatorname{vol}(A)=\operatorname{vol}(B)=1.1523.
  3. 3Cut values. Separating the rows removes cut⁡(A,B)=0.0676\operatorname{cut}(A,B)=0.0676 of weight, so Ncut⁡=0.0676/1.1523⋅2=0.1173\operatorname{Ncut}=0.0676/1.1523\cdot2=0.1173. The best vertical cut (x≤2x\le2 vs x≥3x\ge3) has to sever two heavy row edges: cut⁡=0.2861\operatorname{cut}=0.2861, Ncut⁡=0.4967\operatorname{Ncut}=0.4967. The graph criterion prefers the rows — the reverse of k-means.
  4. 4Eigenvalues of Lsym=I−D−1/2WD−1/2L_{\text{sym}}=I-D^{-1/2}WD^{-1/2}: λ1=0\lambda_1=0, λ2=0.1165\lambda_2=0.1165, λ3=0.2779\lambda_3=0.2779, λ4=0.4064\lambda_4=0.4064, … λ2\lambda_2 is close to the row cut's Ncut (0.1173) — the relaxation is nearly tight because the true partition is nearly an eigenvector.
  5. 5Fiedler vector v2=D−1/2u2v_2=D^{-1/2}u_2 (unit length): −0.304,−0.322,−0.328,−0.322,−0.304-0.304,-0.322,-0.328,-0.322,-0.304 on A1–A5 and the same values with ++ on B1–B5. Check row A1 of Pv=(1−λ2)vPv=(1-\lambda_2)v: (0.1353(−0.3221)+0.0003(−0.3281)+0.0111(0.304)+0.0015(0.3221))/0.1483=−0.2687≈0.884×(−0.304)\big(0.1353(-0.3221)+0.0003(-0.3281)+0.0111(0.304)+0.0015(0.3221)\big)/0.1483=-0.2687\approx0.884\times(-0.304), and 1−λ2=0.88351-\lambda_2=0.8835.
  6. 6Assign labels. The embedding rows are (v1,v2)(v_1,v_2) where v1v_1 is constant, so only v2v_2 separates points: five values near −0.31-0.31, five near +0.31+0.31. k-means on the rows (or simply the sign) returns {A1…A5} and {B1…B5} — the rows.
  7. 7A new point x=(1.5, 1.2)x=(1.5,\,1.2). Spectral clustering has no predict, but the Nyström extension evaluates the eigen-equation at xx: v2(x)=11−λ2∑jw(x,xj)d(x)v2,jv_2(x)=\frac{1}{1-\lambda_2}\sum_j \frac{w(x,x_j)}{d(x)}v_{2,j}. Its weights are 0.50660.5066 to B2 and B3, 0.03400.0340 to A2 and A3, 0.00930.0093 to B1 and B4, 0.00060.0006 to A1 and A4; d(x)=1.1011d(x)=1.1011. That gives v2(x)=+0.3214v_2(x)=+0.3214 — the B side, so x joins row B.
PointDegree dᵢFiedler v₂Spectral labelk-means on x
A10.1483−0.3040Aleft
A20.2851−0.3221Aleft
A30.2855−0.3281Aright
A40.2851−0.3221Aright
A50.1483−0.3040Aright
B10.1483+0.3040Bleft
B20.2851+0.3221Bleft
B30.2855+0.3281Bright
B40.2851+0.3221Bright
B50.1483+0.3040Bright
Intermediate results at γ = 2. The Fiedler vector is almost constant within each row and flips sign between rows.

The bandwidth decides everything. Re-running with other values of γ\gamma on the same ten points:

γλ₂λ₃Split found
0.250.53870.9357left | right (like k-means)
0.50.36460.7493left | right
10.27830.4296left | right
20.11650.2779row A | row B
30.03120.2879row A | row B
40.00860.2914row A | row B
80.00010.2929row A | row B
Eigenvalues of L_sym and the resulting 2-way split as γ varies (k = 2).

For γ≤1\gamma\le1 the vertical edges are nearly as heavy as the row edges, so the cheapest balanced cut slices the long rows in half. From γ=2\gamma=2 on, λ2\lambda_2 falls towards 0 (the rows become almost separate components) while λ3≈0.29\lambda_3\approx0.29 stays put, so the eigengap λ3−λ2\lambda_3-\lambda_2 widens and the row split becomes unambiguous.

▸ spectral clustering
graphklabels fromshow
data space · edge opacity = similarity w_ij · drag pointsA1A2A3A4A5B1B2B3B4B5eigenvalues λ of L_sym0.000λ10.116λ20.278λ30.406λ40.945λ51.060λ6gapFiedler vector v₂ (one stem per point)A1A2A3A4A5B1B2B3B4B5sign of v₂ = the 2-way cut
λ₂ = 0.1165λ₃ = 0.2779eigengap λ3−λ2 = 0.1614Ncut = 0.1173k-means SSE on x = 10.625purity vs true groups = 100%
fig.The worked example at γ = 2: edges are drawn with opacity proportional to w_ij, dashed rose edges are the ones the cut removes. The eigenvalue panel shows λ₂ = 0.1165 and λ₃ = 0.2779 (eigengap 0.1614), the Fiedler stems flip sign between rows, and Ncut = 0.1173 — while k-means on the raw coordinates (SSE 10.625) cuts left from right. Drag γ down to 1 and spectral clustering also cuts vertically. Press "spectral space" to watch the points glide to their (v₂, v₃) coordinates, where each row collapses onto one side. Switch to the kNN graph (n_neighbors = 2 gives two components and λ₂ = 0), drag any point, or load the two-moons and disc-in-ring data and compare with k-means.

The algorithm, step by step

SpectralClustering(X, k)

  1. 1Graph. Compute the affinity matrix WW: RBF weights e−γ∥xi−xj∥2e^{-\gamma\lVert x_i-x_j\rVert^2} (dense), or a symmetrized kNN connectivity graph (sparse). Set wii=0w_{ii}=0.
  2. 2Degrees. di=∑jwijd_i=\sum_jw_{ij}, D=diag⁡(d)D=\operatorname{diag}(d).
  3. 3Laplacian. Lsym=I−D−1/2WD−1/2L_{\text{sym}}=I-D^{-1/2}WD^{-1/2} (or LL, or the generalized problem Lv=λDvLv=\lambda Dv).
  4. 4Eigenvectors. Compute only the kk smallest eigenpairs u1,…,uku_1,\dots,u_k — with Lanczos (ARPACK), LOBPCG or AMG for sparse WW.
  5. 5Embed. Form U=[u1⋯uk]∈Rn×kU=[u_1\cdots u_k]\in\mathbb{R}^{n\times k}; use the rows of D−1/2UD^{-1/2}U (Shi–Malik) or of UU normalized to unit length (Ng–Jordan–Weiss) as the new points.
  6. 6Round. Run k-means (several restarts) on the nn rows; point ii gets the label of row ii.

Complexity. A dense RBF graph costs O(n2d)O(n^2d) time and O(n2)O(n^2) memory — about 8 GB at n=32,000n=32{,}000 in float64 — and a full eigendecomposition O(n3)O(n^3). With a kNN graph, WW has O(nknn)O(nk_{\text{nn}}) non-zeros and an iterative solver needs a modest number of sparse matrix–vector products, each O(nknn)O(nk_{\text{nn}}), so it scales to 10510^5–10610^6 points. The final k-means on an n×kn\times k matrix is cheap. Graph construction (the nearest-neighbour search) and the eigensolver dominate.

Variants and practical tuning

VariantEigenproblemRelaxesEmbedding rows
UnnormalizedL u = λ uRatioCut (balance by |A|)U
Shi & Malik (2000)L v = λ D v (L_rw)Ncut (balance by vol(A))D^{-1/2} U — scikit-learn's choice
Ng, Jordan & Weiss (2002)L_sym u = λ uNcutU with each row scaled to unit length
The three classic flavours differ only in the Laplacian and the row treatment before k-means.

Tuning in practice

Pick the graph first
Use affinity="nearest_neighbors" (sparse, density-adaptive, robust to scale) for anything beyond a few thousand points; use affinity="rbf" with a tuned gamma for small data. Standardize features first — the graph is built from distances.
Bandwidth
A good starting σ is the median (or a low percentile) of nearest-neighbour distances; self-tuning spectral clustering (Zelnik-Manor & Perona) uses a local σᵢ = distance to the 7th neighbour and weights exp(−d²/σᵢσⱼ).
Choosing k
Plot the first 10–20 eigenvalues and look for the eigengap; confirm with silhouette or stability across γ / n_neighbors.
Label assignment
assign_labels="kmeans" (default; random restarts), "discretize" (Yu & Shi rotation, less sensitive to initialization), "cluster_qr" (deterministic, no tuning).
Eigensolver
eigen_solver="arpack" by default; "amg" (needs pyamg) or "lobpcg" are much faster on large sparse graphs.
Precomputed similarities
affinity="precomputed" accepts any symmetric non-negative W — a social graph, sequence similarity, co-occurrence counts — so spectral clustering works on data that has no coordinates at all.
Large n
Nyström approximation (sample m landmarks, extend the eigenvectors to the rest) or landmark-based spectral clustering reduce the cost to roughly O(nm²).

In code

python
1import numpy as np
2
3def rbf_affinity(X, gamma):
4 sq = ((X[:, None, :] - X[None, :, :]) ** 2).sum(-1)
5 W = np.exp(-gamma * sq)
6 np.fill_diagonal(W, 0.0) # no self-loops
7 return W
8
9def kmeans(E, k, n_init=10, iters=100, seed=0):
10 rng = np.random.default_rng(seed)
11 best = (np.inf, None)
12 for _ in range(n_init):
13 C = E[rng.choice(len(E), k, replace=False)]
14 for _ in range(iters):
15 lab = ((E[:, None] - C[None]) ** 2).sum(-1).argmin(1)
16 newC = np.array([E[lab == j].mean(0) if (lab == j).any() else C[j] for j in range(k)])
17 if np.allclose(newC, C):
18 break
19 C = newC
20 sse = ((E - C[lab]) ** 2).sum()
21 if sse < best[0]:
22 best = (sse, lab)
23 return best[1]
24
25def spectral_clustering(X, k, gamma):
26 W = rbf_affinity(X, gamma)
27 d = W.sum(1) # degrees
28 Dm = np.diag(1 / np.sqrt(d))
29 L_sym = np.eye(len(X)) - Dm @ W @ Dm # normalized Laplacian
30 lam, U = np.linalg.eigh(L_sym) # ascending eigenvalues
31 V = Dm @ U[:, :k] # random-walk eigenvectors D^-1/2 u
32 V /= np.linalg.norm(V, axis=0)
33 return kmeans(V, k), lam, V, W, d
34
35X = np.array([[0, 0], [1, 0], [2, 0], [3, 0], [4, 0],
36 [0, 1.5], [1, 1.5], [2, 1.5], [3, 1.5], [4, 1.5]], dtype=float)
37labels, lam, V, W, d = spectral_clustering(X, k=2, gamma=2.0)
38v2 = V[:, 1] * np.sign(-V[0, 1]) # sign convention: A1 negative
39print("degrees ", d.round(4))
40print("lambda ", lam[:4].round(4))
41print("v2 ", v2.round(4))
42print("labels ", labels) # [1 1 1 1 1 0 0 0 0 0]
43
44# Nystrom out-of-sample extension for a new point
45x_new = np.array([1.5, 1.2])
46w = np.exp(-2.0 * ((X - x_new) ** 2).sum(1))
47v_new = (w / w.sum()) @ v2 / (1 - lam[1])
48print("v2(x_new)", round(v_new, 4), "-> row", "B" if v_new > 0 else "A")
From scratch with NumPy: RBF graph, normalized Laplacian, embedding, k-means — and the Nyström extension for a new point. Output: degrees 0.1483 … 0.2855, λ = 0, 0.1165, 0.2779, 0.4064, v₂ = ∓0.304 … ∓0.3281, the two rows as clusters, and v₂(x_new) = 0.3214 → row B.
python
1import numpy as np
2from sklearn.cluster import KMeans, SpectralClustering
3
4X = np.array([[0, 0], [1, 0], [2, 0], [3, 0], [4, 0],
5 [0, 1.5], [1, 1.5], [2, 1.5], [3, 1.5], [4, 1.5]])
6
7sc = SpectralClustering(n_clusters=2, affinity="rbf", gamma=2.0,
8 assign_labels="kmeans", random_state=0)
9print("spectral:", sc.fit_predict(X))
10
11km = KMeans(n_clusters=2, n_init=10, random_state=0).fit(X)
12print("k-means: ", km.labels_, "SSE", round(km.inertia_, 3))
13
14for gamma in [0.5, 1, 2, 4]: # the bandwidth decides everything
15 lab = SpectralClustering(2, affinity="rbf", gamma=gamma, random_state=0).fit_predict(X)
16 print(f"gamma={gamma:<4}", lab)
17
18knn = SpectralClustering(2, affinity="nearest_neighbors", n_neighbors=3, random_state=0)
19print("3-NN graph:", knn.fit_predict(X))
scikit-learn on the same data. Output: spectral [1 1 1 1 1 0 0 0 0 0]; k-means [0 0 1 1 1 0 0 1 1 1] with SSE 10.625; γ = 0.5 and 1 give the left/right split, γ = 2 and 4 the rows; the 3-NN graph gives a broken split [0 1 1 1 1 0 0 0 0 1].

Use when

  • +Clusters are defined by connectivity: curved, nested, elongated or manifold-shaped groups that k-means and GMMs cut through.
  • +You only have pairwise similarities or a graph (networks, kernels on strings, image affinities) — no coordinates needed.
  • +n is small to moderate (up to ~10⁴ dense, ~10⁶ with sparse kNN graphs and AMG/LOBPCG solvers).
  • +You want a principled objective (normalized cut) with a global, non-iterative solution of its relaxation plus an eigengap diagnostic for k.

Avoid when

  • −n is large and you can only afford a dense RBF matrix — O(n²) memory and O(n³) eigen-solves.
  • −You need to assign new points cheaply and repeatedly: there is no predict, only re-fitting or a Nyström approximation.
  • −Clusters overlap heavily or vary wildly in density and scale — no single γ fits; consider HDBSCAN.
  • −There is noise you need flagged as outliers: every point is forced into one of k clusters (DBSCAN/HDBSCAN label noise).
  • −You do not know k and the eigenvalue spectrum shows no clear gap.

Where it's used

Image segmentation

Shi & Malik's normalized cuts: pixels are nodes, edges weight colour/texture similarity times spatial proximity; the Fiedler vector splits the image into coherent regions.

Community detection

Partition social, citation or communication networks into tightly knit groups, directly from the adjacency matrix (affinity="precomputed").

Single-cell and gene-expression analysis

Group cells or genes from a kNN similarity graph, where cell types form curved manifolds in expression space.

Speaker diarization and 3-D shape segmentation

Cluster speech segments by embedding similarity (with the eigengap choosing the number of speakers), and split meshes or point clouds into parts via the mesh Laplacian.

Check yourself

A similarity graph has 6 nodes with edges 1–2, 2–3 and 4–5 (weight 1), and node 6 has no edges. How many eigenvalues of its Laplacian L = D − W equal 0?

Check yourself

Two nodes joined by one edge of weight 0.5. For f = (1, −1), what is fᵀLf?

Check yourself

A 2-way partition removes edges of total weight 0.2; the two sides have volumes 1 and 4. What is its normalized cut?

Check yourself

In the worked example, why does k-means on the raw coordinates split left from right while spectral clustering (γ = 2) finds the two rows?

Remember

  • ✓Build a similarity graph WW, form a Laplacian (L=D−WL=D-W or a normalized one); f⊤Lf=12∑wij(fi−fj)2f^\top Lf=\tfrac12\sum w_{ij}(f_i-f_j)^2 measures how much ff jumps across strong edges.
  • ✓Zero eigenvalues count connected components; the bottom k eigenvectors are the relaxed solution of RatioCut (L) or normalized cut (L_rw, L_sym).
  • ✓Embed each point as its row of the bottom-k eigenvectors, then run k-means there: curved clusters become tight blobs.
  • ✓The graph is the model: the RBF bandwidth γ\gamma or the number of neighbours decides the answer; use the eigengap λk+1−λk\lambda_{k+1}-\lambda_k to choose kk and to check stability.
  • ✓Dense graphs cost O(n2)O(n^2) memory and O(n3)O(n^3) eigen-solves; use sparse kNN graphs and iterative solvers for large nn. There is no native predict — re-fit or use the Nyström extension.
← back to ML Algorithms roadmap