Reversible Edge Regrowth for Sparse Subspace Clustering Graphs

Subspace clustering groups unlabeled data points that lie near a union of low-dimensional linear subspaces, such as face images of one person under varying lighting. The standard recipe writes each point as a sparse combination of other points, treats the weights as edges of a graph, and cuts that graph with spectral clustering. Fast greedy solvers make the recipe scale to hundreds of thousands of points, but they choose the fewest possible neighbors. The resulting graph keeps edges inside the correct subspace and then falls apart into many small pieces. Every fix in current use either adds a dense penalty whose weight must be hand-tuned, or patches the broken graph after the fact with a fragile merging step.

This note proposes a different repair. We treat the graph's edges the way dynamic pruning methods treat neural-network weights: as provisional decisions that can be undone. Starting from a fast greedy graph, edges between fragments are grown back only when points in one fragment can be rebuilt from atoms (other data points) in another. Edges are removed again if that evidence weakens. Regrowth stops once the graph has the target number of connected pieces. Spectral clustering needs that number, the number of clusters $L$, anyway, so the approach replaces a hard-to-tune regularization weight with a quantity the user already supplies. The intended result has three parts: connectivity comparable to two-stage merging, cost near that of greedy pursuit, and a much wider range of acceptable settings than an Elastic Net penalty allows.

Background and gap

Two requirements pull against each other. Each point should connect only to points in its own subspace, a property called subspace preservation. All points of one subspace should also form a single connected component. Noisy Sparse Subspace Clustering analyzes the noisy $\ell_1$ program and identifies the tension. Graph Connectivity in Noisy Sparse Subspace Clustering proves that sparse representations fail to keep subspaces of dimension $d \ge 4$ connected. Its fix is a two-stage pipeline: a Lasso graph per point, then subspace estimation on each fragment, then single-linkage merging by subspace angle. On its synthetic benchmark this raises accuracy from 73% to 99% without noise and from 77% to 93% with noise. It still solves $n$ Lasso problems, and it merges whole fragments in one irreversible step based on estimated subspaces. These two papers motivate the problem. The two-stage pipeline is also the most direct competitor on accuracy.

Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit uses Orthogonal Matching Pursuit (OMP), a greedy method that adds one best-correlated atom at a time. It proves that OMP edges are subspace-preserving under broad conditions and reports 12 minutes against nearly 4 hours for Basis Pursuit on 6,000 MNIST points. The authors note that OMP graphs are too sparse, often exactly $d$ neighbors per point. Our method starts from this graph.

Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering takes a different route. It mixes $\ell_1$ and $\ell_2$ penalties (Elastic Net subspace clustering, EnSC) to buy connectivity, and solves the result with an active-set method called ORGEN, which restricts each point's candidates to an "oracle region" on the sphere. That reaches 581,012 points. The connectivity–purity balance still rests on a mixing weight $\lambda$ that must be tuned by hand.

Dynamic Network Surgery for Efficient DNNs supplies the core mechanism. It keeps masked weights alive in the background and splices them back when their magnitude crosses a higher threshold $b > a$. The gap between the two thresholds prevents on/off flapping. Learning Sparse Neural Networks through L_0 Regularization offers a gradient-based alternative in which gates can reopen during training. Both were developed only for supervised network compression. Neither has been applied to self-expressive affinity graphs, and neither ties regrowth to a structural signal like connectivity.

Core Claim

Over-segmentation by greedy sparse solvers is a premature-commitment error of the same kind dynamic network surgery fixes in neural networks. It should be repaired by reversible, evidence-gated edge regrowth driven by the graph's component count, not by a denser penalty or by post-hoc merging.

Concretely, let fragment $A$ be a connected component of the current graph. Let $x_i \in A$ be a point near its boundary, meaning it is one of the few nearest neighbors of points in another fragment $B$. We run OMP for $x_i$ using atoms restricted to $B$, and compute the normalized residual $r_i(B) = \|x_i - X_B c\|_2 / \|x_i\|_2$, where $X_B$ holds the atoms of $B$ and $c$ is the OMP coefficient vector. An edge from $x_i$ into $B$ is spliced in when $r_i(B) < a$. A spliced edge is pruned again if, after later fragments have changed, its residual rises above $b > a$.

Fragments are joined only when a minimum fraction $\rho$ of $A$'s boundary points have spliced edges into $B$. This is edge-level voting, in contrast to the single subspace-angle comparison used by Graph Connectivity in Noisy Sparse Subspace Clustering. The voting rule is meant to resist the chaining failure of single linkage. The loop of candidate generation, splicing, pruning and component recount stops when the component count reaches $L$, or when no admissible edges remain.

The method should not be sensitive to $a$, $b$ or $\rho$, because these only gate geometric evidence. A fragment of the same subspace yields residuals near the noise level. A different subspace yields residuals bounded below by the angle between the subspaces. The safe range of $a$ is therefore set by that gap rather than by a fragile trade-off.

Research Program

The first component is the algorithm and its cost analysis. Candidate pairs come from approximate nearest-neighbor search over fragment boundaries. Each restricted OMP call costs about $O(Dd \cdot |B_{\text{cand}}|)$, where $D$ is the ambient dimension and $B_{\text{cand}}$ the candidate atoms, so total work grows with the number of boundary points rather than with $n^2$. We will measure wall-clock time against SSC-OMP and EnSC-ORGEN up to CovType scale.

The second component is analysis of the residual-gap argument. We aim to show a separation between same-subspace residuals and cross-subspace residuals. This requires fragments to be large relative to $d$; the residual stays near the noise level once a fragment contains more than $d$ well-spread points. Noise must also stay below the identifiability limit of $\sigma_\ell/\sqrt{d}$ discussed in Graph Connectivity in Noisy Sparse Subspace Clustering. The analysis would explain why $a$ has a wide valid interval.

The third component tests the reversible design directly. We will check whether hysteresis is needed: if fragments evolve during regrowth, a single threshold may let early cross-subspace splices persist.

Baselines

The naive reference is plain SSC-OMP from Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit, run with the same features, the same neighbor count and the same spectral clustering step. Any regrowth that fails to beat it on clustering accuracy and on component count is worthless.

The strongest accuracy-at-scale baseline is EnSC-ORGEN from Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering. It reports 93.79% accuracy on the full 70,000-digit MNIST, against 92.46% for SSC-SPAMS, and 53.52% on CovType. For fairness, we will give EnSC the same tuning budget as our method, a fixed number of configurations selected by the same unsupervised criterion. We will also report its best-oracle $\lambda$. Beating it means matching or exceeding its accuracy under equal budget, with lower variance across the tuning grid, at no more than its wall-clock cost.

The strongest connectivity baseline is the two-stage method of Graph Connectivity in Noisy Sparse Subspace Clustering, at 99% noiseless and 93% noisy on its synthetic $d \ge 4$ benchmark. We will also run a scalable variant that replaces its Lasso stage with OMP. That variant isolates our edge-level reversible voting from whole-fragment angular merging on an identical initial graph.

Ablations will remove hysteresis (setting $a = b$), remove pruning (regrowth only, irreversible), and replace connectivity-driven stopping with a fixed number of rounds.

Why not just…?

Why not just tune the Elastic Net weight? EnSC is a real threat on accuracy. Its reported MNIST number is strong, and our method may not beat its best-tuned point. Our claim is narrower: comparable accuracy without needing to know $\lambda$. The experiment settles this by plotting accuracy against each method's free parameter on log-spaced grids, and comparing the width of the range within two points of the peak.

Why not just let OMP pick more than $d$ atoms? Extra greedy picks beyond the spanning set have no reason to fall in a different fragment of the same subspace. Under noise they risk selecting atoms from intersecting subspaces, and the $d \ge 4$ result in Graph Connectivity in Noisy Sparse Subspace Clustering argues that sparse selection stays concentrated. We will sweep $k$ from $d$ to $4d$ and report both connectivity and the fraction of cross-subspace edges. If some $k$ matches our method, the idea fails and we will say so.

Why not just merge fragments afterward, or union several randomized graphs? Post-hoc merging is exactly the OMP-plus-merging baseline above, which isolates the value of reversibility. Graph unions in the spirit of Scalable and robust sparse subspace clustering using randomized clustering and multilayer graphs are another cheap competitor. The file does not describe that method in detail, so we will implement a union of OMP graphs over random atom subsets at matched compute, and compare connectivity and edge purity directly.

Proposed Experiments

The decisive first check is the synthetic connectivity-breaking benchmark with $d \ge 4$ from Graph Connectivity in Noisy Sparse Subspace Clustering. Success means reaching 99% (noiseless) and 93% (noisy) at OMP-like cost, while the cross-subspace edge fraction stays near SSC-OMP's.

Real-data experiments use Extended Yale B, where subspaces have $d \approx 9$; no reported accuracy was found on Lacuna for SSC-OMP there. They also use full MNIST against ORGEN's 93.79%, CovType against 53.52%, and YTF-100 from the One-step Bipartite Graph Cut suite. No numeric result was found on Lacuna for YTF-100, so there we run OBCut ourselves.

Metrics are accuracy, normalized mutual information (NMI), number of connected components before spectral clustering, cross-subspace edge fraction, wall-clock time, and the width of the parameter range within two points of peak accuracy.

The idea is falsified if a tuned OMP with larger $k$, or a matched-compute graph union, reaches the same connectivity and purity.