Graph-based clustering methods such as the constrained Laplacian rank (CLR) approach learn a similarity graph and force it to split into exactly $k$ disconnected pieces. They do this by pushing the $k$ smallest eigenvalues of the graph Laplacian to zero, the matrix whose zero eigenvalues count connected components. The result is a clean partition with no K-means post-processing and good robustness to noise. The drawback is cost. Every iteration recomputes the bottom eigenvectors of an $n \times n$ matrix, so these methods rarely run beyond a few thousand points. We propose enforcing the rank constraint on a small "skeleton" graph over $m \ll n$ landmark points instead. The skeleton is obtained by exactly eliminating all other nodes, a step called Kron reduction. On the full graph, each iteration then needs only sparse linear solves.
The observation behind this is a known fact that clustering work has not used. Eliminating nodes preserves random-walk commute times between the remaining nodes. It also preserves the number of connected components exactly, provided every component contains a landmark. The recursive spectral-mapping literature on fractal and subdivided graphs explains why the rank constraint suits this reduction. That literature tracks eigenvalues across levels by eliminating vertices. The elimination is exact for every eigenvalue only if the reduction is recomputed for each eigenvalue, and the plain static reduction is exact only at eigenvalue zero. Eigenvalue zero is the only one a rank constraint cares about. So the constraint can be imposed exactly on the skeleton, where most spectral objectives could only be approximated there.
Core Claim
Let $L$ be the Laplacian of a learned nonnegative graph on $n$ points. Split its nodes into landmarks $\alpha$ ($|\alpha| = m$) and eliminated nodes $\beta$. The Kron-reduced Laplacian is the Schur complement
$$S = L_{\alpha\alpha} - L_{\alpha\beta} L_{\beta\beta}^{-1} L_{\beta\alpha},$$
which is itself a valid graph Laplacian on the landmarks. It satisfies $x^\top S x = \min_y [x; y]^\top L [x; y]$, where the minimizing $y = -L_{\beta\beta}^{-1}L_{\beta\alpha}x$ is the harmonic extension of $x$ to the eliminated nodes. The min–max principle then gives
$$\lambda_i(L) \le \lambda_i(S) \quad \text{for } i = 1, \dots, m.$$
It also gives $\mathrm{nullity}(S) = \mathrm{nullity}(L)$ whenever every connected component of the graph contains a landmark, which is exactly the condition for $L_{\beta\beta}$ to be invertible. Two consequences follow. First, driving $\sum_{i\le k}\lambda_i(S)$ to zero drives the fine-scale Ky Fan term $\sum_{i\le k}\lambda_i(L)$ to zero. The coarse penalty is an upper bound that becomes an equality at the feasible point. Second, the gradient of the coarse penalty with respect to a fine edge weight $w_{uv}$ has a simple form, by the envelope theorem:
$$\frac{\partial}{\partial w_{uv}} \mathrm{Tr}(F^\top S F) = \lVert X_u - X_v \rVert^2, \qquad X = \begin{bmatrix} F \\ -L_{\beta\beta}^{-1}L_{\beta\alpha}F \end{bmatrix}.$$
Here $F \in \mathbb{R}^{m\times k}$ holds the bottom eigenvectors of $S$, and $X$ is their harmonic extension to all $n$ points. This has exactly the form of the edge-weight update in The Constrained Laplacian Rank Algorithm for Graph-Based Clustering, which penalizes $\lVert f_u - f_v\rVert^2$ using the fine eigenvectors. The only change is that fine eigenvectors are replaced by harmonically extended coarse ones. The proposal is therefore a drop-in replacement for CLR's eigenvector step. One iteration costs $k$ solves with the sparse, grounded, well-conditioned block $L_{\beta\beta}$, plus an $O(m^3)$ eigendecomposition, instead of an $n \times n$ eigendecomposition.
Relation to Prior Work
Three rank-constrained methods supply the objective we accelerate, and all three pay the full-matrix eigen cost. CLR learns an exactly $k$-component graph close to an initial affinity. Clustering with Similarity Preserving adds kernel fidelity. Structured Graph Learning Via Laplacian Spectral Constraints (SGL) optimizes edge weights, eigenvectors and eigenvalues by block majorization. We keep their objectives and change only where the spectrum is computed.
Hierarchical Representation Learning in Graph Neural Networks With Node Decimation Pooling supplies the reduction machinery: MAXCUT-based node selection, Kron reduction, and sparsification of the dense result. It applies these as a fixed offline pooling step on a given graph. We apply them inside an optimization that keeps changing the fine graph, and we rely on a nullity-preservation guarantee that pooling never needed.
The normalized Laplacian spectrum of subdivisions of a graph and Spectra, Hitting Times and Resistance Distances of q- Subdivision Graphs derive eigenvalue maps across subdivision levels. These maps are eigenvalue-dependent eliminations of the added vertices. Their exact maps, together with those of Hitting Times of Random Walks on Edge Corona Product Graphs, give us closed-form ground truth for how every nonzero eigenvalue moves under elimination. We use them to measure how loose the inequality above is away from zero.
Reachability-Aware Laplacian Representation in Reinforcement Learning shows that unscaled Laplacian eigenvectors misrepresent commute-time geometry across bottlenecks. That result motivates a second design choice. The skeleton should carry resistance, which Kron reduction preserves, rather than two-hop similarity.
The closest competitor in spirit is anchor-graph rank-constrained clustering, for example Efficient Unsupervised Clustering of Hyperspectral Images via Flexible Multi-Anchor Graphs. It also reduces cost to the number of anchors. However, it replaces the data graph with a bipartite data–anchor graph, so any two points are related only through shared anchors. We keep a general sparse point-to-point graph and reduce it exactly. On long, thin manifolds, connectivity passes through chains of non-landmark points. The skeleton still sees that connectivity, whereas an anchor graph needs an anchor near every link of the chain.
Research Program
The theory work has three parts. We will prove the nullity-preservation and eigenvalue-inequality statements for weighted graphs, and extend them to the normalized Laplacian. We will also quantify what happens when the coverage condition nearly fails, which is the practical risk. A true cluster with no landmark makes $L_{\beta\beta}$ singular. We will ground each eliminated block with a small $\varepsilon I$ and show that an uncovered component then appears as a detectably tiny diagonal entry of $L_{\beta\beta}^{-1}$. That signal lets us add a landmark adaptively. The recursive structure of the fractal literature carries over directly, because the Schur complement of a Schur complement is a Schur complement. Multilevel skeletons $n \to m_1 \to m_2$ therefore inherit the nullity guarantee level by level. This settles Gap 3 of the file for Kron reduction, not just for subdivisions.
The algorithm alternates three steps. It forms $S$ (or applies it implicitly) with a sparse Laplacian solver. It takes the bottom $k$ eigenvectors of $S$, extends them harmonically, and applies the CLR/SGL edge-weight update using the gradient identity. It sparsifies $S$ as in NDP when $m$ is large.
Landmarks come from NDP's spectral MAXCUT selection, from k-means++ seeding, or uniformly at random. Their choice is an ablation, not a tuned component. The number of clusters $k$ can be read from the eigengap of $S$. This partly addresses the fixed-$k$ rigidity that SGL acknowledges.
The skeleton also helps with the tension between rank constraints and random walks noted in Gap 4. The effective resistance between landmarks, read directly from the pseudoinverse of the small matrix $S$, grows without bound exactly for landmark pairs being separated. This yields an inexpensive trace of which clusters split first during the penalty continuation. We will test whether this signal can replace heuristic penalty schedules.
Baselines
The naive reference is two-stage normalized cut: a $k$-nearest-neighbor Gaussian affinity, the bottom $k$ eigenvectors from a Lanczos solver, then K-means with the same random restarts. CLR reports 79.44% accuracy for normalized cut on COIL20 and 63.65% on Umist (The Constrained Laplacian Rank Algorithm for Graph-Based Clustering). Any rank-constrained method should clear these numbers, including ours with a small skeleton.
The strongest existing methods are exact CLR and SGL. The file reports CLR-L2 at 87.36% on COIL20 and 72.87% on Umist, and SGL at 99.87% on PANCAN against 98.62% for CLR (Structured Graph Learning Via Laplacian Spectral Constraints). SPC reaches 93% on Two Moons against 73.67% for K-means (Clustering with Similarity Preserving). We will rerun CLR, SGL and SPC ourselves from the same initial affinity, the same $k$-nearest-neighbor sparsity and the same penalty continuation, on identical hardware. We will then place our method on top of each by swapping only the eigenvector step.
At sizes where exact CLR runs, "beating" it means matching its accuracy and normalized mutual information within one standard deviation over seeds at $m/n \le 0.1$ with at least a tenfold wall-clock reduction. At sizes where exact CLR does not finish, we compare against anchor graphs.
The anchor-graph rank-constrained method of Efficient Unsupervised Clustering of Hyperspectral Images via Flexible Multi-Anchor Graphs is the fair large-scale competitor. We will run it with the same number of anchors as our landmarks, chosen by the same selection rule, and tune both methods on the same hyperparameter grid. No reported result found on Lacuna for this method on the benchmarks below. Beating it means higher accuracy at equal $m$, or equal accuracy at smaller $m$, especially on elongated-manifold data.
Two ablations isolate the key ingredient. The first, "reduce once", Kron-reduces the initial affinity a single time and runs CLR on the fixed $m$-node skeleton. This is NDP-style offline coarsening followed by clustering, and it tests whether updating fine edges through the harmonic-extension gradient matters. The second replaces Kron reduction with a Nyström-style landmark subgraph that simply drops non-landmark nodes and the edges between them. It tests whether exact resistance preservation, rather than landmark count alone, drives the results.
Why not just…?
Why not just use two-stage spectral clustering with a fast sparse eigensolver? It is cheap, but it discards the benefit that motivates rank constraints. CLR shows normalized cut collapsing at synthetic noise levels 0.6 to 0.8 where CLR-L1 and CLR-L2 still recover the blocks, along with the accuracy gaps cited above. We include it as the floor and expect to reproduce this gap at scale. Otherwise, the rank constraint is not worth scaling.
Why not just keep CLR and replace the dense eigendecomposition with Lanczos on the sparse fine Laplacian? This is the real threat to the speed claim. On a sparse learned graph, Lanczos is far cheaper than $O(n^3)$. Our counter-argument is specific but unproven. As the penalty drives $k$ eigenvalues toward zero, they cluster tightly near the bottom of the spectrum. Plain Lanczos then converges slowly and needs shift-invert, which means linear solves with a nearly singular $L$. Our method instead solves with $L_{\beta\beta}$, which the landmarks keep nonsingular. We will run CLR with ARPACK shift-invert Lanczos as a named baseline and report wall-clock and iteration counts along the penalty continuation. If it matches our cost, the contribution reduces to the guarantee and the multilevel structure, and we will say so.
Why not just use an anchor graph, which already puts the rank constraint on an $m$-sized problem? Anchor methods trade away point-to-point connectivity. Our advantage should appear exactly where connectivity runs along chains of non-anchor points, which is the bottleneck geometry that Reachability-Aware Laplacian Representation in Reinforcement Learning shows distorts cheaper representations. Accuracy as a function of $m$ on scaled Two Moons and on interleaved-spiral data decides the question. If anchor graphs match us at equal $m$ on these datasets, the advantage of exact reduction is not practically meaningful.
Why not just coarsen the graph once and cluster the skeleton? That is the "reduce once" ablation. It cannot correct noisy fine edges, which is the source of CLR's robustness. We expect it to lose on the noisy block-diagonal synthetic setting from CLR, and on Extended Yale B-style data. If it matches, the dynamic reduction is unnecessary.
Proposed Experiments
The first check is exact and inexpensive. On iterated subdivisions of disconnected seed graphs, and on edge corona products $G \diamond K_q$, we verify that the skeleton's nullity equals the number of components at every level. We also compare the skeleton's nonzero eigenvalues with the closed-form eigenvalue maps of the subdivision and corona papers, and with their exact Kemeny constants. This measures how loose $\lambda_i(L)\le\lambda_i(S)$ is away from zero as landmark density varies.
The second check reproduces the accuracy of exact CLR, SGL and SPC on COIL20, Umist, PANCAN, Two Moons, TR11 and USPS, using accuracy, normalized mutual information and purity over ten seeds. It then sweeps $m/n$ from 0.02 to 0.5 to locate where accuracy degrades.
The third check scales to COIL100 and USPS and to synthetic Two Moons and spiral sets of up to $10^6$ points. Here exact CLR is infeasible, and the comparison is against anchor graphs and Lanczos-CLR on time to reach a fixed accuracy.
The decisive outcome combines the second and third checks. The method succeeds if it matches exact CLR within noise at $m/n\le0.1$, beats anchor graphs at equal $m$ on the elongated-manifold sets, and beats shift-invert Lanczos-CLR in wall-clock time along the continuation. The approach should be abandoned if anchor graphs match it on the manifold sets and Lanczos-CLR matches its cost.
References
- The Constrained Laplacian Rank Algorithm for Graph-Based Clustering
- Clustering with similarity preserving
- Structured Graph Learning Via Laplacian Spectral Constraints
- Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling
- The normalized Laplacian spectrum of subdivisions of a graph
- Spectra, Hitting Times and Resistance Distances of q- Subdivision Graphs
- Hitting Times of Random Walks on Edge Corona Product Graphs
- Reachability-Aware Laplacian Representation in Reinforcement Learning
- Efficient Unsupervised Clustering of Hyperspectral Images via Flexible Multi-Anchor Graphs