Source-linked AI summary
Graph Sparsification by Effective Resistances
Daniel A. Spielman, Nikhil Srivastava
TL;DR
The paper addresses how to build sparse graph proxies that preserve spectral quadratic forms for every real vector while improving prior edge bounds. It samples edges using effective resistances and develops a nearly-linear-time procedure for approximating those resistances. The resulting sparsifiers use O(n log n/ε^2) edges, retain the all-vector guarantee, and support O(log n) approximate-resistance queries.
Problem
Prior cut sparsifiers preserved the guarantee only for x∈{0,1}^V, while stronger spectral sparsifiers used O(n log^c n) edges; the goal is a sparser all-vector guarantee.
Method
Sample edges independently with probabilities proportional to their effective resistances, using approximate resistances computed through a nearly-linear-time solver and Johnson–Lindenstrauss projections.
Results
The algorithm produces a weighted subgraph with O(n log n/ε^2) edges that preserves the quadratic form within (1±ε) for all x∈R^n.
Takeaways & Limitations
The construction provides a nearly-linear-time spectral sparsifier and a data structure supporting approximate effective-resistance queries in O(log n) time.
Takeaways & Limitations
The stated theorem assumes ε≥1/√n and sufficiently large n, with the electrical-flow formulation requiring balanced injected and extracted current.
Abstract
from arXiv · showhide
We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph $G=(V,E,w)$ and a parameter $ε>0$, we produce a weighted subgraph $H=(V,\tilde{E},\tilde{w})$ of $G$ such that $|\tilde{E}|=O(n\log n/ε^2)$ and for all vectors $x\in\R^V$ $(1-ε)\sum_{uv\in E}(x(u)-x(v))^2w_{uv}\le \sum_{uv\in\tilde{E}}(x(u)-x(v))^2\tilde{w}_{uv} \le (1+ε)\sum_{uv\in E}(x(u)-x(v))^2w_{uv}. (*)$ This improves upon the sparsifiers constructed by Spielman and Teng, which had $O(n\log^c n)$ edges for some large constant $c$, and upon those of Benczúr and Karger, which only satisfied (*) for $x\in\{0,1\}^V$. A key ingredient in our algorithm is a subroutine of independent interest: a nearly-linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in $O(\log n)$ time.
1 Introduction
The paper develops spectral graph sparsifiers with O(n log n/ε^2) edges that preserve quadratic forms for all x∈R^n, using effective-resistance sampling and nearly-linear-time resistance approximation.
- Background and significance: Spectral sparsification strengthens cut sparsification by preserving the quadratic-form guarantee for all real vectors rather than only cut characteristic vectors.The resulting sparse graph can preserve spectral, random-walk, and effective-resistance properties.
- Contributions: Effective resistances determine edge-sampling probabilities, and approximate resistances suffice to obtain a good sparsifier.The algorithm samples edges with probability proportional to w_eR_e and assigns reweighted sampled edges.
- Contributions: O(n log n/ε^2) edges achieve Spielman–Teng’s all-vector spectral guarantee, improving on both prior sparsifier constructions.The guarantee holds with probability at least 1/2 under the stated sampling bound and ε range.
- Contributions: A nearly-linear-time algorithm computes approximate effective resistances for every vertex pair, enabling O(log n/ε^2)-time queries.The construction uses a nearly-linear-time linear solver and the Johnson–Lindenstrauss Lemma.
- Additional properties: The sparsifier can also be made close to the original graph in additional ways useful for preconditioning linear systems.This connects the construction to earlier uses of sparsifiers for nearly-linear-time solvers.
2 Preliminaries
The preliminaries represent a weighted graph through its incidence matrix and Laplacian, then use the Laplacian pseudoinverse to characterize electrical flows and effective resistance.
- 2.1 The Incidence Matrix and the Laplacian: L = B^TWB represents the Laplacian of a connected weighted graph using an oriented incidence matrix B and diagonal edge-weight matrix W.The rows of B encode edge heads, tails, and nonincident vertices.
- 2.2 The Pseudoinverse: The Laplacian is positive semidefinite and can be diagonalized using its nonzero eigenvalues and corresponding orthonormal eigenvectors.The pseudoinverse L+ is defined from these nonzero spectral components.
- 2.2 The Pseudoinverse: L+ acts as the inverse of L on im(L)=ker(L)⊥=span(1)⊥, a fact used in the proof of the main theorem.Outside this subspace, the Laplacian has a nullspace associated with the all-ones vector.
- 2.3 Electrical Flows: Electrical flows satisfy Kirchhoff’s current law and Ohm’s law, linking injected currents, edge currents, vertex potentials, and conductances.The total injected current must be balanced by extracted current, so the external-current vector is orthogonal to span(1).
- 2.3 Electrical Flows: Effective resistance between u and v is the potential difference produced by injecting unit current at one vertex and extracting it at the other.For an edge e, the resistance can be expressed algebraically using the incidence vector and L+.
3 The Main Result
The main result samples edges according to effective resistance and proves that the resulting subgraph preserves graph quadratic forms spectrally. Approximate resistances suffice, so the construction remains nearly linear-time.
- Projection structure: Π = W^1/2BL+B^TW^1/2 is a projection whose nonzero eigenvalues are 1 with multiplicity n−1, and whose diagonal entries encode edge effective resistances.Its image is im(W^1/2B), and Π(e,e)=∥Π(·,e)∥2.
- Spectral preservation: Preserving y^TΠy through sampling preserves x^TLx and x^T˜Lx, because Π acts as the identity on im(W^1/2B).Vectors in the kernel of W^1/2B have zero quadratic form for both Laplacians.
- Sampling scheme: Sparsify samples edges independently with replacement, assigning each edge probability proportional to weRe and rescaling sampled weights by the inverse sampling probability.The sampling matrix S satisfies E S=I and E˜L=L.
- Approximate resistances: Sampling with approximate resistances still yields a sparsifier when the estimates satisfy the stated multiplicative lower-bound condition.The approximation introduces a factor α into the final bound without changing the rest of the argument.
4 Computing Approximate Resistances Quickly
The paper computes approximate effective resistances by embedding resistance distances into O(log n) dimensions and approximating the embedding with a nearly-linear-time Laplacian solver. The resulting data structure answers pair queries in logarithmic time.
- Problem and goal: Exact computation of all effective resistances is unclear, motivating a nearly-linear-time algorithm for constant-factor approximations.The resulting construction is also used for the sampling probabilities required by sparsification.
- Query data structure: A O(log n) × n matrix ˜Z supports approximate resistance queries between any two vertices, including nonadjacent pairs, in O(log n) time.A query subtracts the corresponding columns of ˜Z and computes the norm of their difference.
- Johnson–Lindenstrauss embedding: Effective resistances are pairwise distances between vectors W^1/2BL+χv, so Johnson–Lindenstrauss reduces their computation to O(log n)-dimensional projections.The stated embedding preserves all vertex-pair distances with high probability.
- Approximate linear solves: The algorithm computes projected vectors using Spielman–Teng’s approximate Laplacian solver STSolve applied to the rows of QW^1/2B.The construction uses a randomized projection matrix Q and repeated approximate solves.
- Running time: The construction takes ˜O(m log(1/δ)/ε^2)=˜O(m log r/ε^2) time, and constant-factor approximations are sufficient for sparsification.This establishes the nearly-linear-time resistance-estimation subroutine used by the main algorithm.
5 An Additional Property
The section adds a per-vertex control on sampling and rescaling, while preserving the conditions needed for the sparsifier’s guarantee. With suitable probabilities and enough samples, the resulting algorithm achieves the desired property with high probability.
- 5 An Additional Property: The additional property limits how many edges incident to any vertex are excessively increased by sampling and rescaling.This property is motivated by using the sparsifier to solve linear systems, specifically in constructing ultrasparsifiers.
- 5 An Additional Property: q > 4n log n/β sampled edges are required in Lemma 11 for probabilities satisfying its stated condition.Under this sampling regime, the lemma provides a high-probability bound for the per-vertex quantity being controlled.
- Proof: For each vertex v, the proof represents sampled incident-edge contributions with independent random variables Xi, where Xi equals 1/p_e with probability p_e.The number of times each edge is sampled contributes to the vertex quantity D_v, which the proof seeks to bound.
- Proof: The proof targets D_v ≤ 2 deg(v) simultaneously for every vertex v.It computes the expectation and variance of Xi, applies Bennett’s inequality, and then uses a union bound over vertices.
- Conclusion: The chosen sampling probabilities satisfy Corollary 6 with α = 2 and Lemma 11 with β = 1/2, yielding a sparsifier with the desired property.The theorem states that the resulting weighted subgraph has O(n log n/ε^2) edges and is produced in eO(m/ε^2) time with probability at least 1/2 while satisfying both guarantees.