---
kind: concept
slug: spectral-clustering
title: Spectral clustering
summary: >-
  Clustering by the eigenvectors of a graph Laplacian built from pairwise affinities; the classic route needs an N-by-N affinity matrix and an O(N³) eigendecomposition. Anchor-based transfer cut solves a p-by-p eigenproblem instead. A 270-dataset R benchmark ranks spectral first at default settings, with K set to the true class count.
tags: [clustering, graph-partitioning, eigendecomposition, large-scale]
papers: ["1612.08388", "2203.11572", "2012.08496"]
related: [k-means-clustering, clustering-evaluation, multi-view-clustering, ensemble-clustering, community-detection]
status: draft
updated_at: 2026-10-19
---

## 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 [arxiv: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
[arxiv: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](/papers/2012.08496), 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
[arxiv: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 [arxiv: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
[arxiv: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 [arxiv: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 [arxiv:2203.11572 eq. 11] [arxiv: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
[arxiv: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 [arxiv: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
[arxiv: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](/papers/1612.08388).

- **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% [arxiv:1612.08388 tab. 2]. The authors set K
  to the true number of classes for these runs [arxiv:1612.08388 supp. S1].
- **Tuning gain.** Changing the kernel parameter in a one-dimensional sweep on
  DB2C2F gives a mean gain of 7.36% [arxiv: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 [arxiv:2203.11572 §3.4]. Card:
[Fast Multi-view Clustering via Ensembles](/papers/2203.11572). 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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:2012.08496 §3.4].
Card: [Spectral Methods for Data Science: A Statistical Perspective](/papers/2012.08496).

- **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) [arxiv: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 [arxiv:2012.08496 §4.5].
  The constants are not given numerically. Below p < log n / n, isolated vertices
  make exact recovery impossible [arxiv: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 [arxiv: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 [arxiv: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)
[arxiv: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

| Situation | Use | Why |
|---|---|---|
| Small N, one view, exact graph affordable | Full affinity graph | The paper states quadratic memory and a cubic eigensolve [arxiv:2203.11572 §1]; accepting that cost is our call |
| One view, benchmark-like data, default settings, K known | Kernel spectral (`specc`) at defaults | Highest average ARI at defaults over 270 synthetic datasets, with K set to the true class count [arxiv:1612.08388 tab. 2] [supp. S1] |
| K unknown, or data unlike the benchmark's generator | Do not rely on the ranking | Subspace clustering has the higher default ARI on DB2C10F and DB10C10F [arxiv:1612.08388 tab. 10]. Underestimating K was worse than overestimating it for all methods [arxiv:1612.08388 §5.2] |
| Large N, where N² memory or an N-sized eigensolve is out of reach | Anchor-based transfer cut | Cost is governed by p, the anchor count; the paper sets p = min{1000, N} [arxiv:2203.11572 §4.2] |
| Several feature views per sample | Ensemble of anchor graphs (see [multi-view clustering](/concepts/multi-view-clustering)) | The paper builds one anchor graph per random group of views and fuses them [arxiv:2203.11572 §3.2–§3.5] |
| Two equal communities, edge model with known p and q, and a guarantee is wanted | SBM spectral sign rule | The monograph proves recovery conditions for this setting [arxiv:2012.08496 §3.4] [§4.5]; it reports no test on real graphs [arxiv:2012.08496 §1.1] |
| Gaussian clusters with fixed r and large separation | Spectral method on the mean-matrix structure | Guarantee needs separation growing faster than log(n + p) [arxiv:2012.08496 §3.5]; the algorithm is not summarised here |
| Reproducible runs are required | Plan your own seeding | The code reseeds from the clock; the paper states no seed [arxiv:2203.11572 §4.2] [code: FastMICE_EnsembleGeneration.m#L50] |

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 [arxiv:2203.11572 §4.2] [tab. 3]. Do
not read the "no tuning" claim as "no inputs". The benchmark's synthetic
generator is underspecified [arxiv: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
[arxiv:2012.08496 §2.3] and [§3.4].

## Implementation sketch

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

```pseudocode
# 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 [arxiv:2203.11572 §3.4] [code: Tcut_for_bipartite_graph.m#L37]
[code: Tcut_for_bipartite_graph.m#L40-L41]. Pick one convention and document it.
The paper states neither the Gaussian bandwidth nor the k-means iteration count
[arxiv: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.

```pseudocode
# 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](/papers/1612.08388), margin.** The paper reports
  spectral's lead at defaults as "of at least 10%" [arxiv: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](/papers/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) [arxiv:1612.08388 tab. 10].
- **Between cards.** None known on the reported numbers. [arxiv:2203.11572](/papers/2203.11572)
  does not benchmark plain spectral clustering [arxiv:2203.11572 §4.2], so its
  numbers do not bear on the default-settings ranking. [arxiv:2012.08496](/papers/2012.08496)
  reports proven bounds and no clustering benchmark [arxiv:2012.08496 §1.1].
  Its settings differ too: the SBM rule assumes known p and q [arxiv:2012.08496 §3.4],
  while the benchmark sets K to the true class count [arxiv:1612.08388 supp. S1].
  Those results are not directly comparable.

## Papers

- [Clustering Algorithms: A Comparative Approach](/papers/1612.08388): 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](/papers/2203.11572): 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](/papers/2012.08496):
  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.