# Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space

arXiv: https://arxiv.org/abs/1903.12150 · HTML: https://mlsanity.com/paper/1903.12150/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2019.

## Built on by (most cited first, 2 of 2)

- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Streaming Kernel PCA Algorithm With Small Space](https://mlsanity.com/paper/2303.04555/) (2023)

## Abstract (arXiv)

In this paper we consider the problem of computing spectral approximations to graphs in the single pass dynamic streaming model. We provide a linear sketching based solution that given a stream of edge insertions and deletions to a n-node undirected graph, uses tilde O(n) space, processes each update in tilde O(1) time, and with high probability recovers a spectral sparsifier in tilde O(n) time. Prior to our work, state of the art results either used near optimal tilde O(n) space complexity, but brute-force Omega(n2) recovery time [Kapralov et al.'14], or with subquadratic runtime, but polynomially suboptimal space complexity [Ahn et al.'14, Kapralov et al.'19]. Our main technical contribution is a novel method for `bucketing' vertices of the input graph into clusters that allows fast recovery of edges of sufficiently large effective resistance. Our algorithm first buckets vertices of the graph by performing ball-carving using (an approximation to) its effective resistance metric, and then recovers the high effective resistance edges from a sketched version of an electrical flow between vertices in a bucket, taking nearly linear time in the number of vertices overall. This process is performed at different geometric scales to recover a sample of edges with probabilities proportional to effective resistances and obtain an actual sparsifier of the input graph. This work provides both the first efficient ℓ2-sparse recovery algorithm for graphs and new primitives for manipulating the effective resistance embedding of a graph, both of which we hope have further applications.