Source-linked AI summary
Single Pass Spectral Sparsification in Dynamic Streams
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford
TL;DR
The paper tackles single-pass spectral sparsification for dynamic graph streams, where edges can be inserted and deleted. It combines linear sketches, coarse sparsifiers, and effective-resistance sampling to recover a high-probability spectral sparsifier, with extensions to structured matrices. The general-matrix extension is limited by condition number and row sparsity.
Problem
Dynamic semi-streaming lacked a small-space single-pass method for maintaining spectral sparsifiers under both edge insertions and deletions.
Method
The approach maintains linear sketches of the incidence matrix, recursively constructs coarse sparsifiers, and refines them through effective-resistance sampling.
Results
The algorithm recovers with high probability a (1±ε) spectral sparsifier with O((1/ε^2)n log n) edges from a single dynamic-stream pass.
Takeaways & Limitations
Oblivious linear sketches can retain enough information to extract a spectral sparsifier, and the approach extends under restrictions to structured matrix A^T A.
Takeaways & Limitations
For general matrices, the result depends on the condition number; recovery can require O(n^2) space in the worst case and is near-linear under constant row sparsity.
Abstract
from arXiv · showhide
We present the first single pass algorithm for computing spectral sparsifiers of graphs in the dynamic semi-streaming model. Given a single pass over a stream containing insertions and deletions of edges to a graph G, our algorithm maintains a randomized linear sketch of the incidence matrix of G into dimension O((1/epsilon^2) n polylog(n)). Using this sketch, at any point, the algorithm can output a (1 +/- epsilon) spectral sparsifier for G with high probability. While O((1/epsilon^2) n polylog(n)) space algorithms are known for computing "cut sparsifiers" in dynamic streams [AGM12b, GKP12] and spectral sparsifiers in "insertion-only" streams [KL11], prior to our work, the best known single pass algorithm for maintaining spectral sparsifiers in dynamic streams required sketches of dimension Omega((1/epsilon^2) n^(5/3)) [AGM14]. To achieve our result, we show that, using a coarse sparsifier of G and a linear sketch of G's incidence matrix, it is possible to sample edges by effective resistance, obtaining a spectral sparsifier of arbitrary precision. Sampling from the sketch requires a novel application of ell_2/ell_2 sparse recovery, a natural extension of the ell_0 methods used for cut sparsifiers in [AGM12b]. Recent work of [MP12] on row sampling for matrix approximation gives a recursive approach for obtaining the required coarse sparsifiers. Under certain restrictions, our approach also extends to the problem of maintaining a spectral approximation for a general matrix A^T A given a stream of updates to rows in A.
1 Introduction
The paper addresses spectral sparsification in dynamic semi-streaming, where edge insertions and deletions must be processed in one pass using near-linear space. It introduces linear-sketch methods that recover spectral sparsifiers and extends the approach to structured matrices.
- Problem setting: Dynamic semi-streaming supports edge insertions and deletions while targeting small-space graph representations and efficient output.The model is intended for large graphs and permits about O(n polylog(n)) space.
- Sparsification background: Spectral sparsifiers preserve graph Laplacian properties more strongly than cut sparsifiers and support approximate Laplacian linear-system solutions.They also preserve cut approximations and can approximate effective resistances.
- Prior work: Insertion-only spectral sparsification methods do not directly extend to dynamic streams because deletions require information beyond the sparsifier itself.Dynamic cut sparsifiers instead demonstrated the usefulness of linear graph sketches.
- Contribution: The main result is a first single-pass dynamic algorithm that maintains linear sketches and recovers a (1±ε) spectral sparsifier with O((1/ε^2)n log n) edges.Recovery succeeds with high probability; the theorem describes a weighted subgraph with the stated spectral guarantee.
- Method: The method combines oblivious linear sketches with effective-resistance sampling, recursive coarse sparsifiers, and an ℓ2 heavy-hitters sampling primitive.The paper identifies the streaming effective-resistance sampler as its main technical contribution.
- Extension: With modifications, the approach maintains spectral approximations to A^T A for structured matrices whose rows come from a polynomial-size fixed dictionary.The graph case is recovered by taking A to be the vertex-edge incidence matrix.
2 Notation and Preliminaries
The paper represents graph Laplacians as B^T B and defines spectral sparsification through quadratic-form preservation. It uses leverage-score sampling, equivalent to effective-resistance sampling for graphs, together with ℓ2 heavy-hitter sketches for streaming recovery.
- Graph notation: B is formed by selecting rows from the complete-graph incidence matrix, and the graph Laplacian is K = B^T B.Rows corresponding to absent edges are zeroed rather than removed.
- Spectral sparsification: A (1 ± ε) spectral sparsifier preserves x^T K x within factors 1 − ε and 1 + ε for every vector x.The same condition is written as (1 − ε)K ⪯ K̃ ⪯ (1 + ε)K.
- Leverage scores and row sampling: For a rank-r matrix, the paper defines leverage scores using the reduced singular-value decomposition and the Moore–Penrose pseudoinverse of B^T B.These scores quantify the importance of rows for preserving the quadratic form.
- Leverage scores and row sampling: In graphs, a row’s leverage score equals its edge weight times effective resistance, so leverage-score sampling becomes effective-resistance sampling.Sampling by score overestimates yields a spectral approximation with high probability.
- Streaming recovery: An ℓ2 heavy-hitters sketch recovers coordinates larger than an η fraction of a vector’s ℓ2 norm using O(η^-2 polylog(N)) sketch dimension.The sketch can be maintained and decoded in the same asymptotic space.
3 Algorithm Overview
The overview turns effective-resistance sampling into a dynamic-streaming procedure by estimating scores with a coarse sparsifier and identifying sampled edges through linear sketches. Geometric subsampling and sparse recovery make the procedure compatible with insertions and deletions.
- Sampling principle: Sampling edges independently by leverage score produces a weighted subgraph with O(ε^-2 n log n) edges that spectrally approximates the graph.For graph incidence matrices, leverage scores are effective resistances.
- Testing edge presence: The incidence matrix is viewed as containing zero rows for nonexistent edges, allowing the algorithm to test whether a sampled candidate edge is present.For candidate e, the corresponding vector entry is zero when e is absent and equals τ_e when e is present.
- Coarse score estimation: A coarse sparsifier provides constant-factor estimates of every leverage score through quadratic forms involving its pseudoinverse.These estimates suffice for the sampling guarantees, and sparse coarse approximations support iterative or nearly-linear-time solves.
- Sparse recovery: Randomly zeroing entries at a rate related to τ_e makes the target edge a heavy hitter, enabling sparse recovery to detect it from the sketch.After sampling, the target entry has constant-order magnitude relative to the remaining ℓ2 norm.
- Geometric subsampling: The algorithm maintains O(log n) linear sketches of geometrically subsampled incidence matrices and chooses the level whose sampling rate approximates each candidate’s leverage score.Linearity allows multiplication by the coarse inverse during post-processing.
- Recursive construction: A recursive chain of coarse sparsifiers starts from a weighted identity and progressively recovers sparsifiers up to the original Laplacian.Each recovered approximation serves as the coarse approximation for the next level.
4 Recursive Sparsifier Construction
The recursive construction adds diagonal regularization to create a chain of well-conditioned matrices, then refines sparsifiers level by level. The chain has O(log n) levels for graph Laplacians and preserves approximation quality without compounding error.
- Matrix chain: The construction forms matrices K^(0), …, K^(d), K by incrementally adding diagonal weight so adjacent matrices weakly approximate one another.The diagonal weight decreases toward the original matrix.
- Matrix chain: For an unweighted graph Laplacian, the eigenvalue bounds imply d = O(log n) recursive levels.The largest eigenvalue is below 2n and the smallest nonzero eigenvalue exceeds 8/n^2.
- Refinement theorem: Theorem 3 provides an O(n polylog(n))-size sketch that refines a sparse coarse approximation into a more accurate sparsifier.The recovery algorithm uses O(n polylog(n)) space.
- Approximation and sparsity: Each recursive level recovers an ε-approximation with O(ε^-2 n log n) nonzero entries with high probability.The base case and inductive case both maintain this sparsity bound.
- Approximation and sparsity: Approximation error does not compound across levels because the refinement theorem absorbs coarse-approximation error through a constant-factor increase in sampled rows.The theorem is agnostic to the sparsity of the coarse approximation.
- Final output: After the final regularization is removed, the output is the Laplacian of a weighted subgraph with O(ε^-2 n log n) edges and a (1 ± ε) spectral approximation.The complete recovery takes O(n^2 polylog(n)) time across O(log n) levels.
5 Streaming Row Sampling
The streaming refinement routine combines leverage-score estimates, geometric hash-based subsampling, and ℓ2 sparse recovery to emulate independent row sampling from a dynamic stream. Concentration and threshold tests establish correct sampling with high probability while keeping the sketch and output small.
- Refinement routine: RefineSparsifier estimates leverage scores using a coarse matrix and applies the leverage-score sampling lemma to rows of the incidence matrix.The procedure’s challenge is performing this sampling from a sketch rather than from the full matrix.
- Streaming sketches: The maintained sketch stacks O(log n) ℓ2-recovery sketches of incidence matrices subsampled at geometrically decreasing rates.Uniform hash functions determine which rows enter each subsampled matrix.
- Edge recovery: For each candidate edge, the algorithm selects a sampling level, applies the corresponding sketch to a coarse-inverse vector, and runs heavy hitters to test presence.A detected edge receives the corresponding reweighting.
- Dynamic updates: Hash-based updates support both insertions and deletions, so all required sketches are constructed in one dynamic-streaming pass.Recovery occurs during post-processing, and the sketches use O(n polylog(n)) total space.
- Space and levels: O(log n) sampling levels suffice because higher levels are empty with high probability, while the output contains O(n log n ε^-2) sampled edges in addition to identity edges.The output therefore fits in small space.
- Correctness: Concentration bounds show that the recovered edge is included exactly when its row appears in the designated subsample, yielding the desired independent sampling distribution.A union bound over all possible edges gives the claimed high-probability correctness.
6 Sparsification of Weighted Graphs
The weighted-graph extension represents each edge weight bitwise, maintains a separate unweighted graph per precision bit, and combines their sparsifiers into a spectral sparsifier for the weighted graph.
- Weighted-graph extension: Polynomially bounded edge weights are represented using O(log n) bits, with a separate unweighted graph maintained for each bit of precision.This extends the unweighted dynamic-streaming approach to weighted graphs where an edge’s weight is specified at deletion.
- Weighted-graph extension: The weighted graph satisfies G = sum_i 2^i G_i, so the corresponding Laplacian is assembled from the bit-level graph Laplacians.The construction applies the same binary decomposition to the graph and its Laplacian components.
- Combining sparsifiers: If each component K_i has a (1 ± ǫ) sparsifier K̃_i, then their weighted sum is a spectral sparsifier for the Laplacian K of G.The component sparsifiers are combined as sum_i 2^i K̃_i.
7 Sparsification of Structured Matrices
The structured-matrix extension supports dynamic row updates using compressed sketches and leverage-score-based sampling, but its guarantees depend on structural and conditioning assumptions. The procedure produces a sparse spectral approximation with high probability.
- Assumptions: The extension assumes a polynomial-size row dictionary, sparse rows, and a bounded condition number to obtain small-space compression.These conditions avoid an Ω(n^2 polylog(n)) lower bound for general streaming regression.
- Guarantee: O(n polylog(m, κu)) sketch space supports recovery of a (1 ± ǫ) spectral sparsifier with O(ǫ−2n log n) reweighted rows.Recovery runs in poly(m, ǫ, n, log κu) time.
- Sampling: General-matrix row sampling uses multiple independent sampling rates and sketches to approximate leverage-score sampling.The method differs from the graph case because the sampled matrices are independently generated at each rate.
- Limitations: The general-matrix result depends on an upper bound for the condition number, and recovery can require O(n^2) space without sparse rows.With constant row sparsity, recovery uses O(n polylog(m)) space.
8 Using a Pseudorandom Number Generator
The algorithm compresses the randomness needed for edge subsampling by using a pseudorandom generator, preserving the sketch-based computation while reducing space to near-linear polylogarithmic size.
- Space challenge: Naively storing O(log n) hash functions for every possible edge requires O(n^2 log n) space.Each possible edge would need O(log n) random bits.
- Pseudorandomness: Nisan’s pseudorandom generator converts a space-S algorithm using R random bits into one using O(S log R) random bits.The resulting output distribution is close to the truly random distribution.
- Implementation: Because sketch updates commute, the algorithm can generate pseudorandom bits as needed on a general insertion-deletion stream.This reduces the working space to O(n polylog n).
- Implementation: Generating log n random bits per streamed edge takes O(n polylog(n)) time per update.This dominates the time required to process each streaming update.
- Generalization: The general structured-matrix variant requires O(m log^2 n) random bits when the row dictionary has m = poly(n) rows.The same pseudorandomness argument then applies.
A Sparse Recovery
The sparse-recovery component converts linear sketches into approximate heavy hitters, enabling recovery of large coordinates with near-linear dependence on the inverse error parameter and polylogarithmic dependence on dimension.
- Primitive: ℓ2 heavy hitters is equivalent to ℓ2/ℓ2 sparse recovery, and the paper derives the former from a sparse-recovery primitive.This supplies the recovery tool needed by the streaming algorithm.
- Sparse recovery: The sparse-recovery theorem returns a sparse approximation from a linear sketch with O(k log^O(1) N / ǫ) measurements and comparable decoding time.The approximation guarantee is stated relative to the best k-term approximation.
- Heavy hitters: Hashing coordinates into O(η−2) buckets and applying sparse recovery to each bucket recovers heavy coordinates with additive error η∥x∥2.The initial success probability is amplified through repeated trials and medians.
- Complexity: The resulting ℓ2 heavy-hitters sketch uses O(η−2 polylog(N)) space and decoding time.The sketch remains linear in the input vector.
B Recursive Sparsification
Recursive sparsification constructs a chain of PSD matrices across eigenvalue scales, enabling repeated refinement from a coarse approximation to a final spectral sparsifier.
- Construction: The recursive construction applies to PSD matrices whose largest eigenvalue is at most λu and smallest nonzero eigenvalue at least λl.The chain length is d = ⌈log2(λu/λl)⌉.
- Graph specialization: For an unweighted graph Laplacian, λmax < 2n and λmin > 8/n2, so the recursive chain has O(log n) levels.The lower bound applies to the smallest nonzero eigenvalue.
- Correctness: The eigenvalue bounds use PSD ordering and the fact that the endpoint regularization terms lie below or above the relevant spectral range.These relations establish the successive spectral comparisons in the chain.
- Scope: For weighted graphs, the eigenvalue argument extends when the ratio between the heaviest and lightest edge is polynomially bounded in n.The condition is needed for the stated eigenvalue-range reasoning.