Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space

Abstract: In the dynamic graph streaming model, an algorithm processes, in a single pass, a stream of edge insertions and deletions to an $n$-node graph. With limited space and runtime, the goal is to output a function or approximation of the graph at the end of the stream. A central challenge in the dynamic streaming model is developing algorithms for spectral graph sparsification, which is a powerful generic approximation method.

In this paper, we resolve the complexity of this problem up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses nearly linear space, processes each edge update in polylogarithmic time, and with high probability, recovers a spectral sparsifier from the sketch in nearly linear time. Prior results either achieved near optimal space, but quadratic recovery time [Kapralov et al. `14], or ran in subquadratic time, but used polynomially suboptimal space [Ahn et al `13].

Our main technical contribution is a novel method for recovering graph edges with high effective resistance from a linear sketch. We show how to do so in nearly linear time by `bucketing' vertices of the input graph into clusters using a coarse approximation to the graph's effective resistance metric. Our result can be viewed as giving the first efficient $\ell_2$-sparse recovery algorithm for graphs.