# Spectral clustering

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

Source: https://www.mlfoundry.in/learn/spectral-clustering  
Section: ML Algorithms › Unsupervised · Clustering  
Level: advanced · 18 min read · updated 2026-10-07

**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 $k$ 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.

- **Task:** Clustering (unsupervised); also graph partitioning / community detection
- **Input → output:** $n$ points (or any $n\times n$ similarity matrix) and $k$ → a cluster label per point
- **Learns:** nothing parametric: an $n\times k$ spectral embedding of the training points, then k-means centroids in that space
- **Training cost:** $O(n^2 d)$ to build a dense affinity matrix, $O(n^3)$ for a dense eigendecomposition; much less with a sparse kNN graph and a Lanczos / LOBPCG solver for only $k$ eigenvectors
- **Prediction cost:** none built in (transductive). A new point needs a re-fit, or the Nyström extension at $O(nk)$
- **Hyperparameters:** $k$; 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=2$ disagrees: splitting into rows costs a within-cluster sum of squares of $20$, while cutting the picture into a left block of 4 points and a right block of 6 costs only $10.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 $f_i$ and charging $w_{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)$ with weight $w_{ij}\ge0$ when $i$ and $j$ are similar
- **Affinity matrix W:** the $n\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:** $d_i=\sum_j w_{ij}$, the total edge weight at node $i$; $D=\operatorname{diag}(d_1,\dots,d_n)$
- **Volume:** $\operatorname{vol}(A)=\sum_{i\in A}d_i$, the "size" of a set of nodes measured in edge weight
- **Cut:** $\operatorname{cut}(A,B)=\sum_{i\in A,\,j\in B}w_{ij}$, the weight of the edges you remove to separate $A$ from $B$
- **RatioCut / Ncut:** cut criteria balanced by cluster size: divide each cut by $|A|$ (RatioCut) or by $\operatorname{vol}(A)$ (normalized cut)
- **Graph Laplacian:** $L=D-W$ (unnormalized), $L_{\text{sym}}=I-D^{-1/2}WD^{-1/2}$, $L_{\text{rw}}=I-D^{-1}W$ (normalized)
- **Fiedler vector:** the eigenvector of the second-smallest Laplacian eigenvalue $\lambda_2$; its sign pattern is the relaxed best 2-way cut. $\lambda_2$ itself is the *algebraic connectivity*
- **Spectral embedding:** the $n\times k$ matrix whose columns are the bottom $k$ eigenvectors; row $i$ is the new coordinate of point $i$
- **Eigengap:** $\lambda_{k+1}-\lambda_k$; a large gap says the graph has $k$ nearly separate groups

## The math

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

$$
w_{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}
$$

- $x_i$: the $i$-th data point
- $w_{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 $D$ the diagonal degree matrix, define $L=D-W$. For any vector $f\in\mathbb{R}^n$, expand $f^\top Lf=\sum_i d_if_i^2-\sum_{ij}w_{ij}f_if_j$ and write $\sum_i d_if_i^2=\tfrac12\sum_{ij}w_{ij}(f_i^2+f_j^2)$:

$$
f^\top L f=\frac12\sum_{i,j}w_{ij}\,(f_i-f_j)^2\;\ge 0
$$

- $L=D-W$: unnormalized graph Laplacian; symmetric, rows sum to 0
- $f$: any assignment of one number per node
- $(f_i-f_j)^2$: how much f jumps across edge (i, j); weighted by the edge's strength

Three facts follow. $L$ is positive semi-definite, so its eigenvalues are $0=\lambda_1\le\lambda_2\le\dots\le\lambda_n$. The constant vector $\mathbf 1$ has $f^\top Lf=0$, so $\lambda_1=0$. And $f^\top Lf=0$ exactly when $f$ 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,\bar A$, pick $f_i=\sqrt{|\bar A|/|A|}$ on $A$ and $f_i=-\sqrt{|A|/|\bar A|}$ on $\bar A$. Only edges crossing the cut contribute to the sum above, and a short calculation gives

$$
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|}
$$

- $\operatorname{cut}(A,\bar A)$: total weight of edges between the two groups
- $|A|$: number of points in A; dividing by it punishes tiny groups
- $\bar A$: the complement of A

This $f$ also satisfies $f\perp\mathbf 1$ and $\lVert f\rVert^2=n$. Minimizing over the $2^n$ discrete choices of $A$ is NP-hard. **Relax**: let $f$ be any real vector with those two constraints. By the Rayleigh–Ritz (Courant–Fischer) theorem the minimum of $f^\top Lf/f^\top f$ over $f\perp\mathbf 1$ is $\lambda_2$, attained by the **Fiedler vector**. Rounding it back — cluster by the sign of $f_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:

$$
\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
$$

- $\operatorname{vol}(A_c)$: sum of degrees in cluster c
- $L_{\text{rw}}=I-D^{-1}W$: random-walk Laplacian; D⁻¹W is the transition matrix P of a random walk on the graph
- $L_{\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]$ for both normalized Laplacians

The same derivation with indicator entries $1/\sqrt{\operatorname{vol}(A)}$ turns Ncut into $f^\top Lf$ under the constraint $f^\top Df=1$, and relaxing gives the **generalized** eigenproblem $Lv=\lambda Dv$. It has a lovely reading: $L_{\text{rw}}v=\lambda v$ means $Pv=(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 — $k$ clusters.** Stack $k$ scaled indicator vectors into $H\in\mathbb{R}^{n\times k}$ with $H^\top H=I$; then $\sum_c \operatorname{RatioCut}$ terms equal $\operatorname{Tr}(H^\top LH)$. Relaxing $H$ to any orthonormal matrix, the minimizer is the matrix of the **bottom $k$ eigenvectors**, and the minimum is $\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 $L_{\text{sym}}$ and first normalize each row to unit length; scikit-learn uses $D^{-1/2}U$, the random-walk eigenvectors.)

$$
\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\,]
$$

- $H$: relaxed cluster-indicator matrix, one column per cluster
- $u_c$: eigenvector of the c-th smallest eigenvalue
- $\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 $a$ and a between-cluster neighbour at distance $b>a$, the weight ratio is $e^{\gamma(b^2-a^2)}$: raising $\gamma$ widens it, so the cut between clusters becomes cheap and $\lambda_2\to0$. Too small, and $W$ 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 $\to0$ and isolated points become their own "clusters".
- **n_neighbors:** A kNN graph has $\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 $k$ that maximizes $\lambda_{k+1}-\lambda_k$: with $k$ perfectly separated groups, $\lambda_1=\dots=\lambda_k=0<\lambda_{k+1}$.
- **Laplacian:** $L$ (RatioCut) balances by $|A|$; $L_{\text{rw}}$ / $L_{\text{sym}}$ (Ncut) balance by volume and are consistent as $n\to\infty$ under milder conditions. Prefer $L_{\text{rw}}$ or $L_{\text{sym}}$.

## Worked example: two rows of points

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

The data. Neighbours along a row are 1 apart; vertically opposite points are 1.5 apart. Highlighted: row A.

| 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**

1. **Weights.** Only four distances matter. Same-row neighbours ($d^2=1$): $w=e^{-2}=0.1353$. Vertically opposite ($d^2=2.25$): $e^{-4.5}=0.0111$. Diagonal across ($d^2=3.25$): $e^{-6.5}=0.0015$. Two apart in a row ($d^2=4$): $e^{-8}=0.0003$. Everything farther is below $10^{-4}$. A row-neighbour edge is $e^{2.5}\approx12$ times heavier than a vertical one.
2. **Degrees.** End point A1: $0.1353+0.0003+0.0111+0.0015=0.1483$. Inner points A2, A4: $0.2851$; centre A3: $0.2855$ (B is the mirror image). Each row has volume $\operatorname{vol}(A)=\operatorname{vol}(B)=1.1523$.
3. **Cut values.** Separating the rows removes $\operatorname{cut}(A,B)=0.0676$ of weight, so $\operatorname{Ncut}=0.0676/1.1523\cdot2=0.1173$. The best vertical cut ($x\le2$ vs $x\ge3$) has to sever two heavy row edges: $\operatorname{cut}=0.2861$, $\operatorname{Ncut}=0.4967$. The graph criterion prefers the rows — the reverse of k-means.
4. **Eigenvalues** of $L_{\text{sym}}=I-D^{-1/2}WD^{-1/2}$: $\lambda_1=0$, $\lambda_2=0.1165$, $\lambda_3=0.2779$, $\lambda_4=0.4064$, … $\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. **Fiedler vector** $v_2=D^{-1/2}u_2$ (unit length): $-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-\lambda_2)v$: $\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-\lambda_2=0.8835$.
6. **Assign labels.** The embedding rows are $(v_1,v_2)$ where $v_1$ is constant, so only $v_2$ separates points: five values near $-0.31$, five near $+0.31$. k-means on the rows (or simply the sign) returns **{A1…A5}** and **{B1…B5}** — the rows.
7. **A new point** $x=(1.5,\,1.2)$. Spectral clustering has no `predict`, but the Nyström extension evaluates the eigen-equation at $x$: $v_2(x)=\frac{1}{1-\lambda_2}\sum_j \frac{w(x,x_j)}{d(x)}v_{2,j}$. Its weights are $0.5066$ to B2 and B3, $0.0340$ to A2 and A3, $0.0093$ to B1 and B4, $0.0006$ to A1 and A4; $d(x)=1.1011$. That gives $v_2(x)=+0.3214$ — the B side, so **x joins row B**.

Intermediate results at γ = 2. The Fiedler vector is almost constant within each row and flips sign between rows.

| 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 $\gamma$ on the same ten points:

Eigenvalues of L_sym and the resulting 2-way split as γ varies (k = 2).

| γ | λ₂ | λ₃ | 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 $\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 $\gamma=2$ on, $\lambda_2$ falls towards 0 (the rows become almost separate components) while $\lambda_3\approx0.29$ stays put, so the eigengap $\lambda_3-\lambda_2$ widens and the row split becomes unambiguous.

> Figure: 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.

> **Why the embedding makes k-means easy:** If the graph had exactly $k$ connected components, the bottom $k$ random-walk eigenvectors would be (combinations of) component indicators: every point of a component maps to **one single point** of $\mathbb{R}^k$. Weak edges between clusters perturb this only slightly, so in spectral space each cluster is a tight blob — exactly the shape k-means is good at, no matter how twisted the cluster was in the input.

## The algorithm, step by step

**SpectralClustering(X, k)**

1. **Graph.** Compute the affinity matrix $W$: RBF weights $e^{-\gamma\lVert x_i-x_j\rVert^2}$ (dense), or a symmetrized kNN connectivity graph (sparse). Set $w_{ii}=0$.
2. **Degrees.** $d_i=\sum_jw_{ij}$, $D=\operatorname{diag}(d)$.
3. **Laplacian.** $L_{\text{sym}}=I-D^{-1/2}WD^{-1/2}$ (or $L$, or the generalized problem $Lv=\lambda Dv$).
4. **Eigenvectors.** Compute only the $k$ smallest eigenpairs $u_1,\dots,u_k$ — with Lanczos (ARPACK), LOBPCG or AMG for sparse $W$.
5. **Embed.** Form $U=[u_1\cdots u_k]\in\mathbb{R}^{n\times k}$; use the rows of $D^{-1/2}U$ (Shi–Malik) or of $U$ normalized to unit length (Ng–Jordan–Weiss) as the new points.
6. **Round.** Run k-means (several restarts) on the $n$ rows; point $i$ gets the label of row $i$.

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

## Variants and practical tuning

The three classic flavours differ only in the Laplacian and the row treatment before k-means.

| 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; 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²).

> **Relatives:** Spectral clustering is equivalent to a weighted **kernel k-means** on the same similarity (Dhillon, Guan & Kulis, 2004) — the eigen-relaxation is that objective solved without the discreteness constraint. Its embedding step alone is **Laplacian eigenmaps**, a nonlinear dimensionality reduction (scikit-learn's `SpectralEmbedding`), closely related to the graph step of UMAP. For clusters defined by density rather than graph cuts, with automatic noise labelling and no k, see DBSCAN, HDBSCAN and OPTICS; for mode seeking, Mean Shift.

## In code

```python
import numpy as np

def rbf_affinity(X, gamma):
    sq = ((X[:, None, :] - X[None, :, :]) ** 2).sum(-1)
    W = np.exp(-gamma * sq)
    np.fill_diagonal(W, 0.0)                       # no self-loops
    return W

def kmeans(E, k, n_init=10, iters=100, seed=0):
    rng = np.random.default_rng(seed)
    best = (np.inf, None)
    for _ in range(n_init):
        C = E[rng.choice(len(E), k, replace=False)]
        for _ in range(iters):
            lab = ((E[:, None] - C[None]) ** 2).sum(-1).argmin(1)
            newC = np.array([E[lab == j].mean(0) if (lab == j).any() else C[j] for j in range(k)])
            if np.allclose(newC, C):
                break
            C = newC
        sse = ((E - C[lab]) ** 2).sum()
        if sse < best[0]:
            best = (sse, lab)
    return best[1]

def spectral_clustering(X, k, gamma):
    W = rbf_affinity(X, gamma)
    d = W.sum(1)                                   # degrees
    Dm = np.diag(1 / np.sqrt(d))
    L_sym = np.eye(len(X)) - Dm @ W @ Dm           # normalized Laplacian
    lam, U = np.linalg.eigh(L_sym)                 # ascending eigenvalues
    V = Dm @ U[:, :k]                              # random-walk eigenvectors D^-1/2 u
    V /= np.linalg.norm(V, axis=0)
    return kmeans(V, k), lam, V, W, d

X = np.array([[0, 0], [1, 0], [2, 0], [3, 0], [4, 0],
              [0, 1.5], [1, 1.5], [2, 1.5], [3, 1.5], [4, 1.5]], dtype=float)
labels, lam, V, W, d = spectral_clustering(X, k=2, gamma=2.0)
v2 = V[:, 1] * np.sign(-V[0, 1])                 # sign convention: A1 negative
print("degrees  ", d.round(4))
print("lambda   ", lam[:4].round(4))
print("v2       ", v2.round(4))
print("labels   ", labels)                        # [1 1 1 1 1 0 0 0 0 0]

# Nystrom out-of-sample extension for a new point
x_new = np.array([1.5, 1.2])
w = np.exp(-2.0 * ((X - x_new) ** 2).sum(1))
v_new = (w / w.sum()) @ v2 / (1 - lam[1])
print("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
import numpy as np
from sklearn.cluster import KMeans, SpectralClustering

X = np.array([[0, 0], [1, 0], [2, 0], [3, 0], [4, 0],
              [0, 1.5], [1, 1.5], [2, 1.5], [3, 1.5], [4, 1.5]])

sc = SpectralClustering(n_clusters=2, affinity="rbf", gamma=2.0,
                        assign_labels="kmeans", random_state=0)
print("spectral:", sc.fit_predict(X))

km = KMeans(n_clusters=2, n_init=10, random_state=0).fit(X)
print("k-means: ", km.labels_, "SSE", round(km.inertia_, 3))

for gamma in [0.5, 1, 2, 4]:                      # the bandwidth decides everything
    lab = SpectralClustering(2, affinity="rbf", gamma=gamma, random_state=0).fit_predict(X)
    print(f"gamma={gamma:<4}", lab)

knn = SpectralClustering(2, affinity="nearest_neighbors", n_neighbors=3, random_state=0)
print("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].

> **A kNN graph can be too sparse or tie-prone:** In scikit-learn `n_neighbors` counts the point itself. On the ten points, `n_neighbors=2` links each point only to a row neighbour, so the rows are two separate components (λ₁ = λ₂ = 0) and the split is perfect. `n_neighbors=3` gives every end point a vertical edge, λ₂ = λ₃ = 0.191 tie, the second eigenvector is ambiguous, and the labels come out as a meaningless mix. Check the eigenvalues before trusting the clusters.

**Strengths**

- 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.

**Limitations**

- 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.

- **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.

> **The bandwidth is the model:** As the table above shows, the same ten points give the "right" rows at $\gamma\ge2$ and a k-means-like vertical cut at $\gamma\le1$. $\gamma$ has units of 1/distance², so it must match the scale of your features: standardize first, start from the nearest-neighbour distance scale, and check that the answer is stable across a range of $\gamma$ (or switch to a kNN graph).

> **Eigenvectors are only defined up to sign and rotation:** An eigenvector's sign is arbitrary, and when eigenvalues are (nearly) equal any rotation of their eigenvectors is equally valid. Never interpret the raw embedding coordinates or compare them across runs; compare the cluster *partitions* (e.g. with the adjusted Rand index). A tie such as $\lambda_2=\lambda_3$ means the requested $k$ is not supported by the graph.

**Question:** 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?

- A. 1
- B. 2
- C. 3
- D. 6

**Answer:** C. 3 — The number of zero eigenvalues equals the number of connected components: {1,2,3}, {4,5} and the isolated {6}. The spectrum is 0, 0, 0, 1, 2, 3.

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

- A. 0.5
- B. 1
- C. 2
- D. 4

**Answer:** C. 2 — $f^\top Lf=\tfrac12\sum_{i,j}w_{ij}(f_i-f_j)^2$ counts the edge twice (as $(1,2)$ and $(2,1)$), giving $0.5\cdot(1-(-1))^2=2$.

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

- A. 0.04
- B. 0.2
- C. 0.25
- D. 0.4

**Answer:** C. 0.25 — $\operatorname{Ncut}=\tfrac{0.2}{1}+\tfrac{0.2}{4}=0.2+0.05=0.25$. The small side pays most of the penalty — that is how Ncut discourages chopping off tiny groups.

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

- A. k-means was badly initialized
- B. The left/right split has lower within-cluster squared error (10.625 vs 20), but cuts far more graph weight (Ncut 0.51 vs 0.12)
- C. Spectral clustering uses more clusters
- D. The rows are not separable by any method

**Answer:** B. The left/right split has lower within-cluster squared error (10.625 vs 20), but cuts far more graph weight (Ncut 0.51 vs 0.12) — k-means minimizes squared distance to centroids, which favours compact blocks; the rows are long and thin. The graph criterion only charges for the edges it removes, and the vertical cut has to sever heavy row edges.

**Key points**

- Build a similarity graph $W$, form a Laplacian ($L=D-W$ or a normalized one); $f^\top Lf=\tfrac12\sum w_{ij}(f_i-f_j)^2$ measures how much $f$ 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 $\lambda_{k+1}-\lambda_k$ to choose $k$ and to check stability.
- Dense graphs cost $O(n^2)$ memory and $O(n^3)$ eigen-solves; use sparse kNN graphs and iterative solvers for large $n$. There is no native predict — re-fit or use the Nyström extension.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
