Single Pass Spectral Sparsification in Dynamic Streams

Abstract

We present the first single pass algorithm for computing spectral sparsifiers for 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 (\frac{1}{\epsilon^2}n{polylog} (n))$. Using this sketch, at any point, the algorithm can output a $(1 \pm \epsilon)$ spectral sparsifier for $G$ with high probability. While $O (\frac{1}{\epsilon^2} n{polylog}(n))$ space algorithms are known for computing cut sparsifiers in dynamic streams [K. J. Ahn, S. Guha, and A. McGregor, in Proceedings of the 31st ACM Symposium on Principles of Database Systems, 2012, pp. 5--14; A. Goel, M. Kapralov, and I. Post, \hrefhttp://arXiv.org/abs/1203.4900 arXiv:1203.4900, 2002] and spectral sparsifiers in insertion-only streams [J. A. Kelner and A. Levin, Theory Comput. Syst., 53 (2013), pp. 243--262], prior to our work, the best known single pass algorithm for maintaining spectral sparsifiers in dynamic streams required sketches of dimension $\Omega (\frac{1}{\epsilon^2}n^{5/3})$ [K. J. Ahn, S. Guha, and A. McGregor, in Proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2013, pp. 1--10]. To achieve our result, we show that using a coarse sparsifier for $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 [K. J. Ahn, S. Guha, and A. McGregor, in Proceedings of the 31st ACM Symposium on Principles of Database Systems, 2012, pp. 5--14]. Recent work on row sampling for matrix approximation gives a recursive approach for obtaining the required coarse sparsifiers [G. L. Miller and R. Peng, ŭlhttp://arXiv.org/abs/1211.2713v1, 2012]. Under certain restrictions, our approach also extends to the problem of maintaining a spectral approximation for a general matrix $A^\top A$ given a stream of updates to rows in $A$.