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 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
- points (or any similarity matrix) and → a cluster label per point
- Learns
- nothing parametric: an spectral embedding of the training points, then k-means centroids in that space
- Training cost
- to build a dense affinity matrix, for a dense eigendecomposition; much less with a sparse kNN graph and a Lanczos / LOBPCG solver for only eigenvectors
- Prediction cost
- none built in (transductive). A new point needs a re-fit, or the Nyström extension at
- Hyperparameters
- ; the graph (RBF bandwidth 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 disagrees: splitting into rows costs a within-cluster sum of squares of , while cutting the picture into a left block of 4 points and a right block of 6 costs only , 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 and charging 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 with weight when and are similar
- Affinity matrix W
- the symmetric matrix of edge weights, zero diagonal. Built by an RBF kernel, a kNN graph, or an -neighbourhood graph — or given directly (e.g. a social network)
- Degree
- , the total edge weight at node ;
- Volume
- , the "size" of a set of nodes measured in edge weight
- Cut
- , the weight of the edges you remove to separate from
- RatioCut / Ncut
- cut criteria balanced by cluster size: divide each cut by (RatioCut) or by (normalized cut)
- Graph Laplacian
- (unnormalized), , (normalized)
- Fiedler vector
- the eigenvector of the second-smallest Laplacian eigenvalue ; its sign pattern is the relaxed best 2-way cut. itself is the algebraic connectivity
- Spectral embedding
- the matrix whose columns are the bottom eigenvectors; row is the new coordinate of point
- Eigengap
- ; a large gap says the graph has nearly separate groups
The math
Step 1 — the graph. The default (scikit-learn's affinity="rbf") is a Gaussian kernel on squared distances:
- the -th data point
- similarity of points i and j, between 0 and 1
- bandwidth parameter: larger γ = similarity decays faster = sparser effective graph
- equivalent length scale: points much farther apart than σ are effectively unconnected
Step 2 — the Laplacian and its quadratic form. With the diagonal degree matrix, define . For any vector , expand and write :
- unnormalized graph Laplacian; symmetric, rows sum to 0
- any assignment of one number per node
- how much f jumps across edge (i, j); weighted by the edge's strength
Three facts follow. is positive semi-definite, so its eigenvalues are . The constant vector has , so . And exactly when 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 , pick on and on . Only edges crossing the cut contribute to the sum above, and a short calculation gives
- total weight of edges between the two groups
- number of points in A; dividing by it punishes tiny groups
- the complement of A
This also satisfies and . Minimizing over the discrete choices of is NP-hard. Relax: let be any real vector with those two constraints. By the Rayleigh–Ritz (Courant–Fischer) theorem the minimum of over is , attained by the Fiedler vector. Rounding it back — cluster by the sign of , 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:
- sum of degrees in cluster c
- random-walk Laplacian; D⁻¹W is the transition matrix P of a random walk on the graph
- symmetric normalized Laplacian — same eigenvalues, eigenvectors rescaled by D^{1/2}
- eigenvalues lie in for both normalized Laplacians
The same derivation with indicator entries turns Ncut into under the constraint , and relaxing gives the generalized eigenproblem . It has a lovely reading: means , so a small 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 — clusters. Stack scaled indicator vectors into with ; then terms equal . Relaxing to any orthonormal matrix, the minimizer is the matrix of the bottom eigenvectors, and the minimum is . 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 and first normalize each row to unit length; scikit-learn uses , the random-walk eigenvectors.)
- relaxed cluster-indicator matrix, one column per cluster
- eigenvector of the c-th smallest eigenvalue
- trace — the sum of the k quadratic forms, one per cluster
What each hyperparameter does, mathematically
- γ (or σ)
- For a within-cluster neighbour at distance and a between-cluster neighbour at distance , the weight ratio is : raising widens it, so the cut between clusters becomes cheap and . Too small, and 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 and isolated points become their own "clusters".
- n_neighbors
- A kNN graph has 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 that maximizes : with perfectly separated groups, .
- Laplacian
- (RatioCut) balances by ; / (Ncut) balance by volume and are consistent as under milder conditions. Prefer or .
Worked example: two rows of points
Ten points in two rows — A along and B along . We use the RBF graph with (), the normalized Laplacian and , exactly as SpectralClustering(n_clusters=2, gamma=2) does.
| Point | x | y | Point | x | y |
|---|---|---|---|---|---|
| A1 | 0 | 0 | B1 | 0 | 1.5 |
| A2 | 1 | 0 | B2 | 1 | 1.5 |
| A3 | 2 | 0 | B3 | 2 | 1.5 |
| A4 | 3 | 0 | B4 | 3 | 1.5 |
| A5 | 4 | 0 | B5 | 4 | 1.5 |
Spectral clustering by hand
- 1Weights. Only four distances matter. Same-row neighbours (): . Vertically opposite (): . Diagonal across (): . Two apart in a row (): . Everything farther is below . A row-neighbour edge is times heavier than a vertical one.
- 2Degrees. End point A1: . Inner points A2, A4: ; centre A3: (B is the mirror image). Each row has volume .
- 3Cut values. Separating the rows removes of weight, so . The best vertical cut ( vs ) has to sever two heavy row edges: , . The graph criterion prefers the rows — the reverse of k-means.
- 4Eigenvalues of : , , , , … is close to the row cut's Ncut (0.1173) — the relaxation is nearly tight because the true partition is nearly an eigenvector.
- 5Fiedler vector (unit length): on A1–A5 and the same values with on B1–B5. Check row A1 of : , and .
- 6Assign labels. The embedding rows are where is constant, so only separates points: five values near , five near . k-means on the rows (or simply the sign) returns {A1…A5} and {B1…B5} — the rows.
- 7A new point . Spectral clustering has no
predict, but the Nyström extension evaluates the eigen-equation at : . Its weights are to B2 and B3, to A2 and A3, to B1 and B4, to A1 and A4; . That gives — the B side, so x joins row B.
| Point | Degree dᵢ | Fiedler v₂ | Spectral label | k-means on x |
|---|---|---|---|---|
| A1 | 0.1483 | −0.3040 | A | left |
| A2 | 0.2851 | −0.3221 | A | left |
| A3 | 0.2855 | −0.3281 | A | right |
| A4 | 0.2851 | −0.3221 | A | right |
| A5 | 0.1483 | −0.3040 | A | right |
| B1 | 0.1483 | +0.3040 | B | left |
| B2 | 0.2851 | +0.3221 | B | left |
| B3 | 0.2855 | +0.3281 | B | right |
| B4 | 0.2851 | +0.3221 | B | right |
| B5 | 0.1483 | +0.3040 | B | right |
The bandwidth decides everything. Re-running with other values of on the same ten points:
| γ | λ₂ | λ₃ | Split found |
|---|---|---|---|
| 0.25 | 0.5387 | 0.9357 | left | right (like k-means) |
| 0.5 | 0.3646 | 0.7493 | left | right |
| 1 | 0.2783 | 0.4296 | left | right |
| 2 | 0.1165 | 0.2779 | row A | row B |
| 3 | 0.0312 | 0.2879 | row A | row B |
| 4 | 0.0086 | 0.2914 | row A | row B |
| 8 | 0.0001 | 0.2929 | row A | row B |
For the vertical edges are nearly as heavy as the row edges, so the cheapest balanced cut slices the long rows in half. From on, falls towards 0 (the rows become almost separate components) while stays put, so the eigengap widens and the row split becomes unambiguous.
The algorithm, step by step
SpectralClustering(X, k)
- 1Graph. Compute the affinity matrix : RBF weights (dense), or a symmetrized kNN connectivity graph (sparse). Set .
- 2Degrees. , .
- 3Laplacian. (or , or the generalized problem ).
- 4Eigenvectors. Compute only the smallest eigenpairs — with Lanczos (ARPACK), LOBPCG or AMG for sparse .
- 5Embed. Form ; use the rows of (Shi–Malik) or of normalized to unit length (Ng–Jordan–Weiss) as the new points.
- 6Round. Run k-means (several restarts) on the rows; point gets the label of row .
Complexity. A dense RBF graph costs time and memory — about 8 GB at in float64 — and a full eigendecomposition . With a kNN graph, has non-zeros and an iterative solver needs a modest number of sparse matrix–vector products, each , so it scales to – points. The final k-means on an matrix is cheap. Graph construction (the nearest-neighbour search) and the eigensolver dominate.
Variants and practical tuning
| Variant | Eigenproblem | Relaxes | Embedding rows |
|---|---|---|---|
| Unnormalized | L u = λ u | RatioCut (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 = λ u | Ncut | U with each row scaled to unit length |
Tuning in practice
- Pick the graph first
- Use
affinity="nearest_neighbors"(sparse, density-adaptive, robust to scale) for anything beyond a few thousand points; useaffinity="rbf"with a tunedgammafor 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
1import numpy as np23def 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-loops7 return W89def 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 break19 C = newC20 sse = ((E - C[lab]) ** 2).sum()21 if sse < best[0]:22 best = (sse, lab)23 return best[1]2425def spectral_clustering(X, k, gamma):26 W = rbf_affinity(X, gamma)27 d = W.sum(1) # degrees28 Dm = np.diag(1 / np.sqrt(d))29 L_sym = np.eye(len(X)) - Dm @ W @ Dm # normalized Laplacian30 lam, U = np.linalg.eigh(L_sym) # ascending eigenvalues31 V = Dm @ U[:, :k] # random-walk eigenvectors D^-1/2 u32 V /= np.linalg.norm(V, axis=0)33 return kmeans(V, k), lam, V, W, d3435X = 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 negative39print("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]4344# Nystrom out-of-sample extension for a new point45x_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")1import numpy as np2from sklearn.cluster import KMeans, SpectralClustering34X = 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]])67sc = SpectralClustering(n_clusters=2, affinity="rbf", gamma=2.0,8 assign_labels="kmeans", random_state=0)9print("spectral:", sc.fit_predict(X))1011km = KMeans(n_clusters=2, n_init=10, random_state=0).fit(X)12print("k-means: ", km.labels_, "SSE", round(km.inertia_, 3))1314for gamma in [0.5, 1, 2, 4]: # the bandwidth decides everything15 lab = SpectralClustering(2, affinity="rbf", gamma=gamma, random_state=0).fit_predict(X)16 print(f"gamma={gamma:<4}", lab)1718knn = SpectralClustering(2, affinity="nearest_neighbors", n_neighbors=3, random_state=0)19print("3-NN graph:", knn.fit_predict(X))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 , form a Laplacian ( or a normalized one); measures how much 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 or the number of neighbours decides the answer; use the eigengap to choose and to check stability.
- ✓Dense graphs cost memory and eigen-solves; use sparse kNN graphs and iterative solvers for large . There is no native predict — re-fit or use the Nyström extension.