Halving Graphs with Balanced Signs: Fast, Constraint-Exact Spectral Sparsification

Many graph algorithms only need a small "proxy" graph that behaves like the original one: same cuts, same random-walk behaviour, same answers when you solve a linear system on it. The standard way to build such a proxy is to sample edges at random, keeping each edge with probability proportional to how much it matters. A different route treats sparsification as a balancing game. Give every edge a sign, so that $+1$ means "keep it and double its weight" and $-1$ means "drop it." Choose the signs so the doubled and dropped edges cancel spectrally, then repeat on the survivors until the graph is small enough. Choosing balanced signs is the classic problem of discrepancy minimization. Its main algorithmic tool is iterative partial coloring: fix signs for a constant fraction of items at a time, and keep the rest fractional so they stay flexible. Spectral Sparsification by Deterministic Discrepancy Walk showed that this halving view yields sparsifiers that independent sampling cannot produce, for example sparsifiers that keep every vertex's degree exactly. The construction, however, is slow and offline, and fast versions are the paper's main open problem.

This proposal builds a practical, near-linear-time version of the halving walk. Each step of the walk costs a handful of Laplacian solves, the linear systems that fast graph solvers already handle, and no dense matrix work. The walk targets the regularized Laplacian that machine-learning tasks actually use, rather than the full spectrum. The central bet is that, at a fixed edge budget, balanced-sign halving gives lower spectral error than effective-resistance sampling, and keeps exact linear constraints such as vertex degrees for free. We test that bet against the obvious cheap alternative: random sampling followed by a degree-repair step.

Core Claim

Let $L$ be the graph Laplacian (the matrix whose quadratic form $x^T L x$ sums squared differences of $x$ across edges), and let $\gamma \ge 0$ be a regularization level. One halving round assigns fractional signs $x_e \in [-1,1]$ to edges $e$ with weights $w_e$ and rank-one edge Laplacians $L_e$. Its goal is to keep the normalized error

$$\Big\| (L+\gamma I)^{-1/2} \Big(\sum_e x_e w_e L_e\Big) (L+\gamma I)^{-1/2} \Big\|_{\mathrm{op}}$$

small while every sign drifts to $\pm 1$. Here $\|\cdot\|_{\mathrm{op}}$ is the largest absolute eigenvalue. Each round can also enforce exact linear constraints, such as $\sum_{e \ni v} x_e w_e = 0$ for every vertex $v$, which makes the halved graph keep every degree. We claim three things. First, the walk can be run so that each step is dominated by $O(1)$ approximate Laplacian solves, so a round costs near-linear time times the number of walk steps. Second, $\gamma > 0$ shrinks the effective dimension of the problem: edges that matter only below the noise floor $\gamma$ can be signed almost arbitrarily. This should let the walk freeze edges faster than in the unregularized setting of Lau, Wang and Zhou. Third, at equal final edge count, the result should have smaller measured $\epsilon$ than leverage-score sampling. That sampling method's guarantee carries an extra $\log n$ factor in size (Single Pass Spectral Sparsification in Dynamic Streams gives $O(n\epsilon^{-2}\log n)$ edges, versus $O(n\epsilon^{-2})$ for discrepancy-based constructions). The sampled sparsifier also violates degrees unless it is repaired.

What is new relative to the closest work is speed, regularization and evaluation. Spectral Sparsification by Deterministic Discrepancy Walk supplies the method: a potential-controlled walk in restricted subspaces with exact linear constraints. That walk is deterministic and preserves the full spectrum, and it pays super-linear algebra per step. We give up determinism in exchange for randomized sketches of the potential, adopt the $\gamma$-regularized target of Improved Large-Scale Graph Learning through Ridge Spectral Sparsification, and measure everything on real graphs. That paper argues that full-spectrum preservation is overkill for smoothing and semi-supervised learning, and it motivates our target. It does not use discrepancy.

Research Program

The walk follows the Gaussian-step style of partial coloring, as in Lovett–Meka and the Edge-Walk used by Fast Discrepancy Minimization with Hereditary Guarantees. At each step we draw a random direction over the edges that are not yet frozen and remove three kinds of components from it. We remove the component that would violate the linear constraints. For degree constraints this projection onto a null space reduces to a single Laplacian solve, because the constraint matrix is the incidence matrix. We zero out the coordinates of frozen edges. We also remove the component that pushes along the few directions where the current error matrix is already largest. We estimate those directions by a short randomized power iteration on the normalized error, much as GRASS uses generalized power iterations to find the edges that dominate spectral error. Each power iteration step needs one solve against $L+\gamma I$. Edges whose sign reaches $\pm 1$ freeze. A round ends when half the live edges have frozen. Remaining fractional signs are rounded randomly, and the next round runs on the reweighted kept edges.

Fast Discrepancy Minimization with Hereditary Guarantees is the methodological precedent here. It made vector partial coloring practical by projecting away from the spectral directions of $A^TA$ that carry large row norms. It paid an extra $\lg^{1/2} m$ factor in the discrepancy bound for that speed. We expect an analogous price and will measure it rather than assume it away.

The analytic part asks what survives sketching. We will bound the extra error caused by approximate solves and by estimating only a few top error directions, as a function of $\gamma$, the solver tolerance and the number of directions $k$. We want a statement of the form "with $k$ directions and solver accuracy $\delta$, each round adds at most $O(\sqrt{d_\gamma/m_{\mathrm{live}}}) + O(\delta)$ normalized error." Here $d_\gamma$ is the $\gamma$-effective dimension and $m_{\mathrm{live}}$ is the number of live edges. We would not claim this bound before deriving it. The form is conjectured from the Lau–Wang–Zhou per-round bound with $n$ replaced by the regularized dimension.

Baselines

The naive reference point is uniform edge sampling at the target budget, reweighted by the inverse sampling rate, together with the $k$-neighbors heuristic. Graph Sparsification Approaches for Laplacian Smoothing called $k$-neighbors the practical winner on Google+: it cut 3 million edges to about 380,000 with a 5–10x speedup and "virtually no increase" in MSE or misclassification. That paper reports no exact error values in the file. On the Amazon graph, Improved Large-Scale Graph Learning through Ridge Spectral Sparsification found that $k$-neighbors "showed significantly higher error." Beating the naive reference means lower spectral error at equal size on graphs with uneven density.

The strongest existing method for the regularized task is DiSRe, the ridge resparsification from Improved Large-Scale Graph Learning through Ridge Spectral Sparsification. It reduced the 98.5M-edge Amazon co-purchase graph to 7.3M edges with "virtually the same error rates as the EXACT baseline" on smoothing and semi-supervised learning, with solves taking 1–2 minutes instead of 12. No numeric error value is given in the file, so we will rerun it. The comparison holds $\gamma$, the final edge count, the solver and the hardware fixed. Each method gets the same budget of Laplacian solves for computing its importance scores or walk steps. Beating DiSRe means reaching the same downstream error with fewer edges, or lower measured $\epsilon_\gamma$ at 7.3M edges.

For full-spectrum and preconditioning use, the strongest baseline is GRASS, a low-stretch spanning tree augmented with high-energy off-tree edges. Its file-reported result is that, on a 2D mesh, 400 added edges reduced the relative condition number by a factor of 640. We compare relative condition number and preconditioned conjugate-gradient iteration counts at matched edge counts.

The Lau–Wang–Zhou walk with exact potentials, run on the graphs small enough for it, serves as an ablation. It isolates what sketching costs in quality.

Two further ablations isolate the key ingredients. One runs our walk with the error-direction projection removed, leaving only constraint projection and freezing. This tests whether the walk's balancing beats plain random halving. The other replaces the walk with "leverage-score sampling plus degree repair," where repair is a minimal-norm reweighting of the sampled edges, solved by one Laplacian solve, that restores exact degrees. This tests whether exact constraints come cheaply without discrepancy.

Why not just…?

Why not just sample by effective resistance and stop there? It is near-linear and well understood. It cannot hold degrees exactly, though, and its size guarantee carries a $\log n$ factor that halving avoids in theory (Spectral Sparsification by Deterministic Discrepancy Walk). Whether that factor shows up empirically at practical $\epsilon$ is an open empirical question, and the matched-budget $\epsilon$ curves settle it directly. If sampling matches us at every budget, the speed claim is moot and only the constraint claim remains.

Why not just sample and then repair degrees by reweighting? This is the real threat. If a cheap linear correction after sampling restores degrees without inflating spectral error, the walk's constraint handling buys nothing. The repair ablation measures this directly. Our expectation, which is unproven, is that repair concentrates weight changes on low-degree vertices and inflates $\epsilon$ there. If it does not, we will reframe the contribution around spectral error alone, or drop it.

Why not just run DiSRe or GRASS, which already scale? They do scale: GRASS solved a 40-million-unknown system in under two minutes. Neither enforces linear constraints, and GRASS has no worst-case guarantee and is parameter-sensitive, as dyGRASS notes for its own thresholds. If they match us on spectral error and downstream accuracy, our advantage narrows to constraint-exact sparsifiers, and we will say so.

Proposed Experiments

The data are the densified Amazon co-purchase graph (334,863 nodes, 98,465,352 edges), Google+ (about 49,000 nodes and 3 million edges), and the EDA and finite-element benchmark graphs reused by dyGRASS from inGRASS. We add synthetic graphs built from clusters of very different densities, where uniform sampling is known to fail.

The primary metric is the measured $\epsilon_\gamma$: the extreme generalized eigenvalues of $(\tilde L+\gamma I)$ against $(L+\gamma I)$, computed by Lanczos iteration. We report it at $\gamma = 0$ on graphs where it is computable. Secondary metrics are maximum and mean degree violation, downstream smoothing and semi-supervised error under the protocols of the Amazon and Google+ papers, preconditioned conjugate-gradient iteration counts, and wall-clock time.

The decisive check is a plot of $\epsilon_\gamma$ against edge count for our walk, leverage sampling, leverage sampling with repair, and DiSRe, all under an equal solve budget. The proposal succeeds if our curve lies strictly below the others on at least the uneven-density and Amazon graphs. A second check fits runtime against $m$ across graph sizes; the slope should be close to 1. A third check sweeps $\gamma$ and confirms that the number of walk steps per round falls as $d_\gamma$ falls, which is the mechanism the regularized analysis predicts.