Spectral clustering groups data by the shape of the similarity graph among points rather than by distance to cluster centers. That lets it separate intertwined spirals and concentric rings, which k-means cannot. Anchor-graph methods make it affordable. They pick a few hundred to a few thousand representative points ("anchors"), connect every data point only to its nearest anchors, and do all the heavy linear algebra on an anchor-sized matrix. The strongest recent anchor methods also add a balance term that stops one cluster from swallowing the dataset. Every one of them, however, keeps an $n \times m$ or $n \times c$ matrix in RAM while it iterates, where $n$ is the number of points, $m$ the number of anchors and $c$ the number of clusters. The only anchor method whose memory is truly independent of $n$ has no balance term at all.
This note claims that the two properties need not be traded off. When cluster labels are carried from anchors to points through the anchor graph, both families of balance regularizer used in the literature can be computed exactly from two small accumulated quantities: the $m \times m$ anchor co-occurrence matrix and the $m$-vector of anchor degrees. Both can be gathered in one streaming pass over data on disk. Balanced anchor clustering can then run as three sequential disk passes plus an optimization whose cost per iteration does not grow with $n$ at all. What remains open is empirical. The question is how much accuracy is lost by restricting labels to this anchor-transmitted form, compared with methods that optimize point-level labels in RAM.
Core Claim
Let $Z \in \mathbb{R}^{n\times m}$ be the sparse, row-stochastic matrix linking each point to its $k$ nearest anchors, as in Large Graph Construction for Scalable Semi-Supervised Learning. Let $G \in \mathbb{R}^{m\times c}$ be the soft label matrix of the anchors, and let point labels be obtained by transmission, $F = ZG$. Define $S = Z^\top Z$ (an $m\times m$ matrix) and $d = Z^\top \mathbf{1}$ (the total weight each anchor receives). Then two identities hold:
$$F^\top F = G^\top S G, \qquad \mathbf{1}^\top F = d^\top G.$$
The first identity says that the singular values of the $n\times c$ label matrix are the square roots of the eigenvalues of a $c\times c$ matrix built from $S$. Therefore the Schatten $p$-norm maximization that Large Scale Manifold Balanced Clustering (LMBC) uses to enforce balance can be evaluated and differentiated without touching $n$. (The Schatten $p$-norm is the $\ell_p$ norm of a matrix's singular values.) The second identity says that cluster masses are linear in $G$ with coefficients $d$. The lower and upper mass bounds of SC-FAGC: Size Constrained Fast Anchor-based Graph Clustering therefore become an optimal-transport problem on an $m\times c$ plan, with anchor marginals proportional to $d$. It can be solved by the same Sinkhorn-Knopp scaling (an alternating row-and-column rescaling algorithm) that SC-FAGC runs over the full bipartite graph.
The spectral part of the objective already depends only on $S$ and anchor degrees. That fact is what Scalable Sequential Spectral Clustering (SeqSC) exploits when it accumulates $Z^\top Z = \sum_b Z_b^\top Z_b$ block by block. The whole balanced objective thus lives in $O(m^2 + md)$ memory, the same footprint SeqSC reports, and each optimizer iteration costs $O(m^2 c)$ instead of $O(nm^2)$.
Relation to Prior Work
Three works motivate the gap. SeqSC shows that sequential accumulation of the Gram matrix gives $n$-independent memory: it reports an $O((m+d)m)$ footprint on a 1GB desktop. SeqSC has no balance mechanism, however, and it places anchors by a single stochastic-gradient pass whose result depends on the order in which data arrive. LMBC and SC-FAGC supply the balance regularizers we reuse, but both hold the full indicator or assignment matrix in RAM. LMBC additionally optimizes point-level labels rather than transmitted ones. Our reduction is exact for SC-FAGC's anchor-level mass bounds. For LMBC it is an approximation whose cost we measure rather than assume away.
Ultra-Scalable Spectral Clustering and Ensemble Clustering (U-SPEC) supplies our anchor-selection method. It downsamples points to a candidate pool, runs k-means on that pool only, and searches for nearest representatives among sub-regions. U-SPEC still keeps all $N$ points in RAM, which caps it near the 20 million points it handles on 64GB. We run its pool-based selection on a reservoir sample drawn during a streaming pass. A reservoir sample is a fixed-size uniform sample maintained over a stream, and it is uniform regardless of the order in which data arrive.
Consistency of anchor-based spectral clustering shows that anchor spectral clustering recovers separated clusters when anchors cover the data density and neighborhoods scale as $K \ge C\log m$. Uniform coverage is exactly what a reservoir gives and what an order-dependent single pass may not. That paper therefore constrains our design choice for anchors.
Coreset Spectral Clustering reports that projecting labels back to all points becomes the memory bottleneck at tens of millions of nodes. In our setting labels are $F = ZG$, so the projection is a final streaming pass that writes labels to disk block by block. It needs only $G$ and the anchors in RAM. This addresses that bottleneck for feature-vector data, not for the explicit input graphs that paper targets.
Online nonnegative matrix factorization, as in Online Multi-view Clustering with Incomplete Views, already achieves $O(s)$ memory in the mini-batch size $s$. It fits only linear factors, though, so it plays the role of a bounded-memory reference that should fail on non-linear shapes.
Research Program
The system makes three passes over data stored on disk. Pass one maintains a reservoir sample, runs U-SPEC-style k-means on it to produce $m$ anchors, and builds U-SPEC's sub-region index over them. Pass two computes each block's sparse $Z_b$, accumulates $S$ and $d$, and discards the block. The optimization stage alternates two steps on $G$ using only $S$, $d$ and the anchor graph. One step is a spectral or anchor-space k-means step. The other is a balance step: either a projected-gradient step on the Schatten term, or a double-bounded Sinkhorn solve with anchor marginals $d$. Pass three streams the data again and writes $\arg\max$ of $Z_bG$ for each block.
The analysis has two parts. The first proves the exactness statements above and characterizes what is lost relative to point-level labels. Transmitted labels are constrained to the $m$-dimensional span of $Z$'s columns, so the gap should shrink as $m$ grows and as $k$ shrinks. We will measure this directly rather than bound it loosely. The second part quantifies anchor drift. We will compare reservoir-plus-pool anchors against SeqSC's single-pass anchors on streams presented in random order versus sorted by class or by a feature. Sorted order is the adversarial case suggested by the consistency analysis.
Baselines
The naive reference point is subsample-then-extend. A random subset as large as the RAM budget allows is clustered with the in-memory method (SC-FAGC or LMBC), and every remaining point takes the label of its nearest anchor. This is also exactly what the consistency paper's AnchorNN does at scale, so it is the most natural "do nothing new" option. It is run under the same RAM budget and the same anchor count, with the subsample size maximized.
The strongest bounded-memory competitor is SeqSC. It shares our memory profile, so any accuracy gain on skewed data isolates the value of the balance term. We will run it under identical RAM budgets (1GB and 4GB), anchor counts, $k$, and a matched hyperparameter search over bandwidth. The file gives SeqSC's memory bound and hardware but no accuracy figure; no reported result found on Lacuna for SeqSC clustering accuracy on MNIST or Covtype, so we rerun it.
The strongest balanced method is SC-FAGC run fully in memory wherever it fits. The file reports 88.83% accuracy for it on USPS20, and we will reproduce that number before comparing. LMBC is run the same way; no reported result found on Lacuna for LMBC accuracy on any benchmark. For speed at scale, U-SPEC reports about 10 seconds on TB-1M, against over 100 seconds for Nyström and LSC-K.
Beating the baselines means two things. On datasets where SC-FAGC or LMBC fit in RAM, we should match their accuracy to within about one point of accuracy (ACC) or normalized mutual information (NMI). On skewed or out-of-core data, we should clearly exceed SeqSC and subsample-then-extend at equal memory.
Two ablations isolate the key ingredients. The first removes the balance step, which gives SeqSC with reservoir anchors. The second swaps reservoir anchors for SeqKM anchors while keeping the balance step.
Why not just…?
Why not just cluster a RAM-sized subsample with SC-FAGC and assign the rest by nearest anchor? This is the most serious threat. On balanced, stationary data with a large subsample it may perform nearly as well. The weakness is that the balance constraint is enforced on the subsample's mass distribution, while $n - n_{sub}$ points are labeled with no balance control. Small, sparse clusters that are under-sampled can also be lost. Our statistics $d$ include every point, so mass bounds apply to the true full-data masses. The experiment varies the subsample fraction and the class imbalance. If subsample-then-extend matches us at realistic budgets, we will report that the contribution is chiefly the out-of-core label pass and the exact mass accounting, not accuracy.
Why not just run SeqSC and fix balance afterward, for example by size-constrained k-means on its embedding? Post-hoc balancing can only reassign points after the spectral embedding is fixed. SC-FAGC's premise is that balance must shape the partition during optimization to prevent collapse, and its perfect accuracy on Two Ring shows that joint optimization preserves non-linear structure. We include a post-hoc-balanced SeqSC as an additional baseline. If it matches our joint objective on skewed synthetic manifolds, then the joint formulation is unnecessary, and we will say so.
Why not just memory-map the sparse $Z$ and run SC-FAGC as-is, since $Z$ has only $k$ nonzeros per row? With $k=5$, $Z$ for $10^8$ points is several gigabytes, so this is plausible on a large machine. Two things still count against it. SC-FAGC's iterations each sweep all $n$ rows at $O(nm^2)$ cost, which turns each iteration into a full disk scan under a small budget. And the raw features still have to be streamed to build $Z$. We will run memory-mapped SC-FAGC at 1GB and 4GB budgets and report wall-clock time against ours. The advantage we expect is iteration cost independent of $n$, not feasibility alone.
Why not just use online NMF, which already runs in $O(s)$ memory? It fits linear factors, and the manifold benchmarks exist precisely because linear methods fail on rings and spirals. We include online NMF on TB-1M and Flower-20M to confirm this rather than assert it.
Proposed Experiments
The first check is exactness and approximation cost. We use MNIST, USPS, PenDigits, Covtype and Extended MNIST, where in-memory SC-FAGC and LMBC fit, and report ACC, NMI and adjusted Rand index (ARI) for our streamed version against both. With SC-FAGC's constraints placed at the anchor level, objective values should agree to numerical precision. The LMBC gap is reported as a function of $m$ and $k$.
The second check is skew. We build imbalanced resamplings of MNIST and Covtype with size ratios up to 50:1, and imbalanced versions of TB-1M. Here we expect SeqSC to collapse clusters and the balanced streamed method not to; minimum cluster recall is reported alongside ACC.
The third check is order robustness. Streams sorted by class and by feature are fed to both anchor schemes. The consistency analysis predicts that SeqKM coverage degrades and the reservoir does not, which we measure as ARI and as the fraction of true clusters left with no anchor.
The decisive check is scale under a fixed budget. On Flower-20M and synthetic manifold generators scaled to $10^8$ and $10^9$ points, under 1GB, 4GB and 64GB RAM caps, we plot peak resident memory and wall-clock time against $n$. The proposal succeeds if memory stays flat in $n$, time grows linearly, and accuracy stays within the in-memory methods' range where comparison is possible. Meanwhile U-SPEC, memory-mapped SC-FAGC and subsample-then-extend should either fail or lose accuracy beyond the 20-million-point regime U-SPEC reports.
References
- Large Graph Construction for Scalable Semi-Supervised Learning
- Large Scale Manifold Balanced Clustering
- SC-FAGC: Size Constrained Fast Anchor-based Graph Clustering
- Scalable Sequential Spectral Clustering
- Ultra-Scalable Spectral Clustering and Ensemble Clustering
- Consistency of Anchor-based Spectral Clustering
- Coreset Spectral Clustering
- Online multi-view clustering with incomplete views