Spectral clustering

Overview

Spectral clustering groups samples using the eigenvectors of a matrix that encodes which samples are similar. The classic pipeline builds an affinity graph over all samples and partitions it through its eigenstructure. The multi-view paper on this page describes that cost plainly: an affinity matrix takes O(N²d) time and O(N²) space, and spectral clustering on it needs an SVD and takes O(N³) time 2203.11572 §1. The cost, not the idea, is what the anchor-based variant below addresses.

A benchmark card on this page measures one spectral implementation in R against six other single-view methods, on synthetic data with known classes 1612.08388 §4.1 §5.1. It is the only card here that compares spectral clustering with other methods head-to-head.

The monograph on this page, Spectral Methods for Data Science: A Statistical Perspective, treats the same kind of estimator as a statistical problem. Its perturbation bounds say how far a leading eigenvector can move under noise, in terms of the noise size divided by the eigengap 2012.08496 §2.3. It also gives a spectral labelling rule for two communities in a stochastic block model, with guarantees rather than benchmark numbers 2012.08496 §3.4.

The shared core in the anchor-based variant is a bipartite graph between samples and a small set of anchors, partitioned via a reduced eigenproblem 2203.11572 §3.4:

1. Anchor graph. Choose p representatives and connect each sample to its nearest anchors, so the cross-affinity matrix B has shape N × p.
2. Reduced eigenproblem. Work on the p-by-p matrix E = Bᵀ D⁻¹ B instead of the N-by-N graph 2203.11572 eq. 9.
3. Lift and discretise. Map the small eigenvectors back to the N samples and run k-means on the resulting embedding 2203.11572 eq. 11 2203.11572 §3.4.

The invariant is that the samples' embedding stays a function of their anchor affinities, so the expensive N-by-N eigenproblem never appears.

Variants

Full affinity graph (classic)

Build the sample-to-sample affinity matrix, form the Laplacian and take its smallest eigenvectors. The multi-view paper treats this as the baseline that does not scale: time and space are quadratic in N and the eigenproblem is cubic 2203.11572 §1. No card covers the original formulation. The benchmark below covers a library implementation that uses a Nyström approximation by default, which is a different thing.

Kernel spectral clustering in R (kernlab specc)

The benchmark runs specc from the kernlab package 1612.08388 tab. 1. Its defaults are the "rbfdot" kernel, an automatically chosen kernel parameter, Nyström sampling with a sample size of N_b / 6, and 200 iterations 1612.08388 supp. S1. Because the default already approximates the graph, a default run is not the exact affinity-graph method above. Card: Clustering Algorithms: A Comparative Approach.

• Author-reported result. Averaged over 270 datasets with default settings, this method has the highest mean ARI of the seven methods, 65.80%; the next is subspace clustering at 58.58% 1612.08388 tab. 2. The authors set K to the true number of classes for these runs 1612.08388 supp. S1.
• Tuning gain. Changing the kernel parameter in a one-dimensional sweep on DB2C2F gives a mean gain of 7.36% 1612.08388 §5.2 tab. 3. The paper's random search does not single out this method.

Anchor-based transfer cut

Partition a sample-to-anchor bipartite graph instead, using the transfer cut of Li et al. (CVPR 2012), which the paper adopts 2203.11572 §3.4. Card: Fast Multi-view Clustering via Ensembles. The eigenproblem is on the p anchors, so the dense work per partition is in p, not N. The paper states an overall cost of O(NMp^{1/2}V^{1/2}) under the assumption that the cluster count, neighbour count, ensemble size and view count are much smaller than p, and p is much smaller than N; it drops the M·p³ eigenproblem term and the k_c³ consensus term from that statement 2203.11572 §3.6.1. The paper uses this inside an ensemble of M base clusterings, so the single-graph transfer cut is one piece of a larger method.

• Author-reported result. On 22 datasets the method has the best average NMI rank, 1.23 against 4.41 for the next best method 2203.11572 §4.3. These are the authors' numbers and are not reproduced here.

Two-community stochastic block model (theory)

Model the graph as two equal groups, where a pair of vertices is connected with probability p if they share a group and q otherwise, with p > q 2012.08496 §3.4. Build the surrogate M = A − ((p + q)/2) 11ᵀ + pI from the adjacency matrix A, and label each vertex by the sign of the leading eigenvector of M 2012.08496 §3.4. Labels are recovered only up to a global sign. Building M needs p and q, which the monograph assumes known. It sketches a version that avoids them, using the second eigenvector of A, but does not analyse it 2012.08496 §3.4. Card: Spectral Methods for Data Science: A Statistical Perspective.

• Author-proven guarantees. Weak recovery, meaning a fraction 1 − o(1) of labels correct, holds when p ≳ log n / n and √(p/n) = o(p − q) 2012.08496 §3.4. For exact recovery in the regime p = α log n / n and q = β log n / n, the monograph states the condition (√p − √q)² ≥ 2(1+ε) log n / n 2012.08496 §4.5. The constants are not given numerically. Below p < log n / n, isolated vertices make exact recovery impossible 2012.08496 §4.5.
• No benchmark. The only simulation for this model is a figure of success rate over 200 trials, described in words and not tabulated 2012.08496 §1.1.

Gaussian mixtures (theory)

For data drawn from Gaussian clusters, the monograph writes the mean of the data matrix as a rank-r matrix with block-constant structure, and applies the spectral method to its spiked structure 2012.08496 §3.5. With r = O(1), dimension p ≳ log³ n, and centre separation Δ satisfying log(n + p) = o(Δ) and (p log(n+p)/n)^{1/4} = o(Δ), it proves a mis-clustering rate of o(1) 2012.08496 §3.5. The card does not summarise the algorithm itself, so this page gives no steps for it; read §3.5 of the monograph before implementing.

When to use which

The multi-view paper calls its method tuning-free, but it still needs the cluster count k and the distance to be chosen by the user, and the reported runs average 20 repetitions with large spreads 2203.11572 §4.2 tab. 3. Do not read the "no tuning" claim as "no inputs". The benchmark's synthetic generator is underspecified 1612.08388 §4.1, so its ranking tells you about that generator, not about your data. The monograph's SBM rule needs p and q, and its guarantees hold only with the eigengap and noise conditions stated in 2012.08496 §2.3 and §3.4.

Implementation sketch

The transfer cut as the paper describes it, in our own words. The steps follow 2203.11572 §3.4, with the code's extra row normalisation noted below.

# Transfer cut on a sample-to-anchor graph B of shape (N, q)  [arxiv:2203.11572 §3.4]
# Output: k cluster labels for the N samples

def transfer_cut(B, k):
    # Row sums give each sample's degree  [arxiv:2203.11572 §3.4]
    sample_degree = B.sum(axis=1)                          # (N,)
    # Reduced anchor-by-anchor matrix  [arxiv:2203.11572 eq. 9]
    anchor_affinity = B.T @ (B / sample_degree[:, None])   # (q, q)
    # Smallest k generalised eigenpairs  [arxiv:2203.11572 eq. 9]
    deltas, u = smallest_generalized_eigenpairs(anchor_affinity, k)
    # Convert each delta to lambda  [arxiv:2203.11572 eq. 10]
    lam = 1 - sqrt(1 - deltas)                             # (k,)
    # Lift the eigenvectors to the samples  [arxiv:2203.11572 eq. 11]
    embedding = (B / sample_degree[:, None]) @ u / (1 - lam)  # (N, k)
    # Discretise the sample rows with k-means  [arxiv:2203.11572 §3.4]
    return kmeans(embedding, k)

Where implementations differ: the text divides the lifted embedding by (1 − λ), but the code does not; the code also normalises each row to unit length and clusters with cosine distance 2203.11572 §3.4 Tcut_for_bipartite_graph.m Tcut_for_bipartite_graph.m. Pick one convention and document it. The paper states neither the Gaussian bandwidth nor the k-means iteration count 2203.11572 §3.3.

The two-community SBM rule is the full-graph counterpart, and it needs known p and q. It builds a dense n-by-n matrix, so the cost discussion in the Full affinity graph variant applies to it too.

# Two-community SBM spectral labels  [arxiv:2012.08496 §3.4]
# Input:  adjacency A (n, n) with zero diagonal; edge probabilities p > q
# Output: labels (n,) in {+1, -1}, correct up to a global sign

def sbm_spectral_labels(A, p, q):
    n = A.shape[0]
    # Shift by the mean edge level and add p on the diagonal  [arxiv:2012.08496 §3.4]
    M = A - (p + q) / 2 * ones((n, n)) + p * eye(n)
    # Eigenvector of the largest eigenvalue of M  [arxiv:2012.08496 §3.4]
    eigenvalues, eigenvectors = eigh(M)
    u = eigenvectors[:, argmax(eigenvalues)]
    # Sign rule; a zero entry is labelled -1 as in the paper  [arxiv:2012.08496 §3.4]
    return where(u > 0, 1, -1)

Contradictions

• Within arxiv:1612.08388, margin. The paper reports spectral's lead at defaults as "of at least 10%" 1612.08388 §5.1. In the card's table, the margin is at least 10 points for NMI (smallest 12.49, against k-means) tab. 2, but for ARI the margin over subspace clustering is 7.22 points tab. 2. The paper does not say whether margins are percentage points or relative terms.
• Within arxiv:1612.08388, ranking. The pooled default ranking does not hold on every subset. On DB2C10F and DB10C10F, subspace clustering has the higher default ARI (89.9 against 82.4, and 86.1 against 70.9) 1612.08388 tab. 10.
• Between cards. None known on the reported numbers. arxiv:2203.11572 does not benchmark plain spectral clustering 2203.11572 §4.2, so its numbers do not bear on the default-settings ranking. arxiv:2012.08496 reports proven bounds and no clustering benchmark 2012.08496 §1.1. Its settings differ too: the SBM rule assumes known p and q 2012.08496 §3.4, while the benchmark sets K to the true class count 1612.08388 supp. S1. Those results are not directly comparable.

Papers

• Clustering Algorithms: A Comparative Approach: benchmark of seven R clustering methods on 270 synthetic datasets; the kernlab spectral method has the highest average ARI at default settings.
• Fast Multi-view Clustering via Ensembles: anchor-based transfer cut on bipartite graphs, used per random view group and in a consensus step.
• Spectral Methods for Data Science: A Statistical Perspective: monograph on spectral methods; gives eigenvector perturbation bounds, a two-community SBM spectral rule with recovery guarantees, and a Gaussian-mixture result. Proven bounds, no benchmark.