Spectral Sparsification in the Semi-streaming Setting

Let G be a graph with n vertices and m edges. A sparsifier of G is a sparse graph on the same vertex set approximating G in some natural way. It allows us to say useful things about G while considering much fewer than m edges. The strongest commonly-used notion of sparsification is spectral sparsification; H is a spectral sparsifier of G if the quadratic forms induced by the Laplacians of G and H approximate one another well. This notion is strictly stronger than the earlier concept of combinatorial sparsification.

In this paper, we consider a semi-streaming setting, where we have only \(\tilde{O}(n)\) storage space, and we thus cannot keep all of G. In this case, maintaining a sparsifier instead gives us a useful approximation to G, allowing us to answer certain questions about the original graph without storing all of it. We introduce an algorithm for constructing a spectral sparsifier of G with O(nlogn/ϵ ²) edges (where ϵ is a parameter measuring the quality of the sparsifier), taking \(\tilde{O}(m)\) time and requiring only one pass over G. In addition, our algorithm has the property that it maintains at all times a valid sparsifier for the subgraph of G that we have received.

Our algorithm is natural and conceptually simple. As we read edges of G, we add them to the sparsifier H. Whenever H gets too big, we resparsify it in \(\tilde{O}(n)\) time. Adding edges to a graph changes the structure of its sparsifier’s restriction to the already existing edges. It would thus seem that the above procedure would cause errors to compound each time that we resparsify, and that we should need to either retain significantly more information or reexamine previously discarded edges in order to construct the new sparsifier. However, we show how to use the information contained in H to perform this resparsification using only the edges retained by earlier steps in nearly linear time.

1. Spielman and Srivastava actually showed that this holds with probability at least 1/2 using Rudelson’s sampling theorem [9], but a straightforward application of a stronger concentration of measure result [14, Corollary 4] yields the high probability claim.

2. Recall that we say \(f(n) = \tilde{O}(g(n))\) if f(n)≤g(n)log^O(1) n, i.e. the notation hides poly-logarithmic factors.

We would like to thank the referees for their helpful comments. This work was partially supported by National Science Foundation grant CCF-0843915. The second author is supported by a National Science Foundation graduate fellowship.

Authors and Affiliations

1. Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA

   Jonathan A. Kelner & Alex Levin

Corresponding author

Correspondence to Alex Levin.

Appendix: Table of Notation

Table 1 summarizes the notation used in the analysis of the resparsification step.

Reprints and permissions