Source-linked AI summary
Twice-Ramanujan Sparsifiers
Joshua Batson, Daniel A. Spielman, Nikhil Srivastava
TL;DR
The paper addresses how to construct sparse spectral approximations for arbitrary weighted graphs while retaining strong approximation guarantees. It uses Laplacian and barrier-function techniques to obtain a weighted subgraph with a linear number of edges, while identifying limitations in the corresponding complete-graph comparison.
Problem
A central technical challenge is satisfying two barrier conditions simultaneously while shifting both barriers without increasing either potential.
Method
The approach represents graph Laplacians through incidence matrices and uses barrier functions to choose rank-one updates that construct the sparsifier.
Results
⌈d(n −1)⌉ edges suffice for a weighted subgraph H of any n-vertex graph, giving average degree at most 2d.
Takeaways & Limitations
The construction extends the sparsifier perspective beyond complete graphs, while its output generally changes the original edge weights.
Takeaways & Limitations
The authors believe a stronger lower bound should hold for graphs of average degree d, but they are unable to prove it and establish only a weaker claim.
Abstract
from arXiv · showhide
We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every $d>1$ and every undirected, weighted graph $G=(V,E,w)$ on $n$ vertices, there exists a weighted graph $H=(V,F,\tilde{w})$ with at most $\lceil d(n-1) \rceil$ edges such that for every $x \in \mathbb{R}^{V}$, \[ x^{T}L_{G}x \leq x^{T}L_{H}x \leq (\frac{d+1+2\sqrt{d}}{d+1-2\sqrt{d}})\cdot x^{T}L_{G}x \] where $L_{G}$ and $L_{H}$ are the Laplacian matrices of $G$ and $H$, respectively. Thus, $H$ approximates $G$ spectrally at least as well as a Ramanujan expander with $dn/2$ edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing $H$.
1 Introduction
The paper develops spectral sparsifiers with linear edge counts, matching the approximation quality associated with Ramanujan expanders while extending the construction beyond complete graphs. It also gives a deterministic polynomial-time construction and identifies limitations concerning weights and comparison bounds.
- 1 Introduction: Spectral sparsification preserves quadratic forms x^T L_G x through Laplacian-based similarity, strengthening cut sparsification guarantees.The paper’s notion requires the spectral inequality to hold for every real vector, whereas cut sparsification checks characteristic vectors of vertex sets.
- 1 Introduction: The approximation is at least as good as that of a Ramanujan graph with twice as many edges, relating arbitrary-graph sparsifiers to expander graphs.For complete graphs, the construction produces weighted, possibly irregular expanders whose weighted degrees may vary slightly.
- 1 Introduction: ⌈d(n −1)⌉ edges suffice for a weighted subgraph H of every undirected weighted n-vertex graph, with average degree at most 2d.The construction retains edges from G but generally changes their weights.
- 1 Introduction: The deterministic greedy algorithm computes H in time O(dn^3m), although the comparison with the Ramanujan bound is only established in a restricted d regime.The stated regime includes the actual Ramanujan graphs, where d is an integer greater than 2.
- 1 Introduction: For complete graphs, the paper proves a weaker lower-bound claim for weighted average-degree-d graphs than the conjectured asymptotically optimal bound.The authors state that they believe the stronger bound but are unable to prove it.
- 1 Introduction: The work affirmatively resolves the conjecture that spectral sparsifiers can use O(n/ϵ^2) edges, improving over earlier O(n log n/ϵ^2)-edge constructions.Earlier constructions cited in the paper were randomized, whereas this work gives the first deterministic algorithm with these guarantees.
2 Preliminaries
The preliminaries represent graph Laplacians through signed incidence matrices and edge-weight diagonals, then develop spectral and pseudoinverse tools alongside rank-one update identities.
- The Incidence Matrix and the Laplacian: The Laplacian factors as L = B^TWB, where B is the signed edge-vertex incidence matrix and W contains edge weights.Each incidence entry is 1 at an edge’s head, −1 at its tail, and 0 otherwise.
- The Incidence Matrix and the Laplacian: A connected graph has Laplacian kernel span(1), while L is positive semidefinite.The kernel characterization is expressed through ker(L) = ker(W^1/2B) = span(1).
- The Pseudoinverse: Because L is symmetric, it can be diagonalized using orthonormal eigenvectors associated with its nonzero eigenvalues.The nonzero-eigenvalue decomposition supports the subsequent definition of the Moore–Penrose pseudoinverse.
- The Pseudoinverse: The Moore–Penrose pseudoinverse acts as the projection onto the span of L’s nonzero eigenvectors, and LL+ = L+L is the identity on im(L).For connected graphs, im(L) equals ker(L)^⊥.
- Formulas for Rank-one Updates: The Sherman–Morrison formula describes inverse changes under rank-one matrix updates.The matrix determinant lemma provides a related description of determinant changes under the same update.
3 The Main Result
The paper reduces graph sparsification to a linear-algebraic selection theorem: a sparse weighted sum of rank-one matrices remains spectrally controlled. A barrier-based deterministic construction realizes this selection while controlling all eigenvalues.
- The Main Result: Theorem 3.1 selects nonnegative coefficients for at most dn vectors while preserving a bounded spectral condition.This theorem is the core linear-algebraic ingredient for sparsification.
- The Main Result: Applying the theorem to graph-incidence vectors yields a subgraph with at most d(n−1) weighted edges and a spectral approximation to the original graph.The reduction restricts the Laplacian to its image and encodes selected coefficients in a diagonal weight matrix.
- The Main Result: The proof is constructive and yields a deterministic polynomial-time algorithm for finding the coefficients used in the sparsifier.The paper contrasts this deterministic construction with earlier randomized sampling approaches based on effective resistance.
- 3.2 Proof by Barrier Functions: The proof builds the matrix incrementally by adding fractional rank-one updates and maintains lower and upper barriers around its eigenvalues.The lower barrier pushes eigenvalues forward, while the upper barrier prevents them from advancing too far.
- 3.1 Intuition for the Proof: Rank-one updates interlace eigenvalues, and the equal-projection intuition connects repeated updates to associated Laguerre polynomials.After k = dn iterations, known zero locations provide the ratio underlying the final approximation factor.
- 3.2 Proof by Barrier Functions: Barrier potential functions quantify eigenvalue proximity to the barriers, diverging when eigenvalues approach them and tracking all eigenvalues simultaneously.The construction seeks an update that shifts both barriers without increasing either potential.
4 Sparsifiers of the Complete Graph
For complete graphs, the constructed sparsifiers behave as weighted, possibly irregular expanders. The section establishes both their expander-like properties and a lower-bound constraint on approximation quality.
- Sparsifiers of the Complete Graph: The constructed sparsifiers of complete graphs are weighted and may be irregular, but their weighted degrees vary only slightly.This motivates examining whether they satisfy standard expander properties despite not being regular unweighted graphs.
- Sparsifiers of the Complete Graph: They have high edge-conductance, rapidly mixing random walks, nearly uniform stationary behavior, and the Expander Mixing Property.Near-uniform weighted degrees are important for interpreting these properties as expander behavior.
- Sparsifiers of the Complete Graph: For d-regular unweighted graphs, the Alon–Boppana approach gives an asymptotic barrier, while the paper conjectures the same bound for weighted graphs and proves a weaker result.The weighted irregular setting is therefore not fully resolved by the strongest known bound.
- Sparsifiers of the Complete Graph: The paper proves a lower bound on κ by constructing vectors orthogonal to the all-ones vector and comparing their quadratic forms.The argument focuses on a vertex of degree d and its incident edge weights.
- Sparsifiers of the Complete Graph: A weighted graph that κ-approximates the complete graph must have all weighted degrees between n and nκ.This degree constraint follows directly from the spectral approximation.
5 Conclusion
The conclusion connects the paper’s main theorem to the Kadison–Singer conjecture and identifies stronger theorem variants that would imply it. It also derives consequences for unweighted sparsifiers and spectrally splitting graphs with bounded effective resistances.
- Theorem 3.1 is connected to the Kadison–Singer conjecture, which is equivalent to the Paving Conjecture and a stronger restricted invertibility theorem.
- A strengthened theorem producing scalars restricted to 0 or β with approximation factor κ < β would yield a proof of Conjecture 5.1 with r = 2.
- Such a strengthened result would imply unweighted sparsifiers for complete and sufficiently dense edge-transitive graphs.
- For graph-derived vectors, the norm-boundedness condition corresponds to bounded effective resistances on all edges.
- Consequently, graphs with sufficiently small edge resistances could be split into two graphs that approximate the original spectrally.