TY - JOUR

T1 - SINGLE pass spectral sparsification in dynamic streams

AU - Kapralov, M.

AU - Lee, Y. T.

AU - Musco, C. N.

AU - Musco, C. P.

AU - Sidford, A.

N1 - Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2017

Y1 - 2017

N2 - 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(1/ϵ2 n polylog(n)). Using this sketch, at any point, the algorithm can output a (1 ± ϵ) spectral sparsifier for G with high probability. While O( 1/ϵ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, 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 ω (1/ϵ2 n5/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 l2=l2 sparse recovery, a natural extension of the l0 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, arXiv:1211.2713v1, 2012]. Under certain restrictions, our approach also extends to the problem of maintaining a spectral approximation for a general matrix AT A given a stream of updates to rows in A.

AB - 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(1/ϵ2 n polylog(n)). Using this sketch, at any point, the algorithm can output a (1 ± ϵ) spectral sparsifier for G with high probability. While O( 1/ϵ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, 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 ω (1/ϵ2 n5/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 l2=l2 sparse recovery, a natural extension of the l0 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, arXiv:1211.2713v1, 2012]. Under certain restrictions, our approach also extends to the problem of maintaining a spectral approximation for a general matrix AT A given a stream of updates to rows in A.

KW - Graph sketch

KW - Linear sketch

KW - Sparse recovery

KW - Spectral sparsification

KW - Streaming

UR - http://www.scopus.com/inward/record.url?scp=85014468603&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85014468603&partnerID=8YFLogxK

U2 - 10.1137/141002281

DO - 10.1137/141002281

M3 - Article

AN - SCOPUS:85014468603

SN - 0097-5397

VL - 46

SP - 456

EP - 477

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 1

ER -