Single Pass Spectral Sparsification in Dynamic Streams

Introduction

When processing massive graph datasets arising from social networks, web topologies, or interaction graphs, computation may be as limited by space as it is by runtime. To cope with this issue, one might hope to apply techniques from the streaming model of computation, which restricts algorithms to few passes over the input and space polylogarithmic in the input size. Streaming algorithms have been studied extensively in various application domains – see [Mut05] for an overview. However, the model has proven too restrictive for even the simplest graph algorithms. For example, testing $s$-$t$ connectivity requires $\Omega(n)$ space [HRR99].

In the dynamic semi-streaming model, the graph stream may include both edge insertions and deletions [AGM12a]. This extension captures the fact that large graphs are unlikely to be static. Dynamic semi-streaming algorithms allow us to quickly process general updates in the form of edge insertions and deletions to maintain a small-space representation of the graph from which we can later compute a result. Sometimes the dynamic model is referred to as the insertion-deletion model, in contrast to the more restrictive insertion-only model.

Work on semi-streaming algorithms in both the dynamic and insertion-only settings is extensive. Researchers have tackled connectivity, bipartiteness, minimum spanning trees, maximal matchings, and spanners among other problems [FKM+05, ELMS11, Elk11, AGM12a, AGM12b]. In [McG14], McGregor surveys much of this progress and provides a more complete list of citations.

2 Streaming Sparsification

There has also been a focus on computing general purpose graph compressions in the streaming setting. The goal is to find a subgraph of an input graph $G$ that has significantly fewer edges than $G$, but still maintains important properties of the graph. Hopefully, this sparsified graph can be used to approximately answer a variety of questions about $G$ with reduced space and time complexity. Typically, the goal is to find a subgraph with just $O(n\log n)$ edges in comparison to the possible $O(n^{2})$ edges in $G$.

First introduced by Benczúr and Karger [BK96], a cut sparsifier of a graph $G$ is a weighted subgraph with only $O(\frac{1}{\epsilon^{2}}n\log n)$ edges that preserves the total edge weight over every cut in $G$ to within a $(1\pm\epsilon)$ multiplicative factor. Cut sparsifiers can be used to compute approximations for minimum cut, sparsest cut, maximum flow, and a variety of other problems over $G$. In [ST11], Spielman and Teng introduce the stronger spectral sparsifier, a weighted subgraph whose Laplacian spectrally approximates the Laplacian of $G$. In addition to maintaining the cut approximation of Benczúr and Karger, spectral sparsifiers can be used to approximately solve linear systems over the Laplacian of $G$, and to approximate effective resistances, spectral clusterings, random walk properties, and a variety of other computations.

3 Our Contribution

Our main result is an algorithm for maintaining a small graph sketch from which we can recover a spectral sparsifier. For simplicity, we present the algorithm in the case of unweighted graphs. However, in Section 6, we show that it is easily extended to weighted graphs. This model matches what is standard for dynamic cut sparsifiers [AGM12b, GKP12].

The fact that our algorithm maintains a linear sketch of the streamed graph allows for the simple handling of edge deletions, which are treated as negative edge insertions. Additionally, due to their linearity, our sketches are composable – sketches of subgraphs can simply be added to produce a sketch of the full graph. Thus, our techniques are directly applicable in distributed settings where separate processors hold different subgraphs or each processes different edge substreams.

4 Road Map

Lay out notation, build linear algebraic foundations for spectral sparsification, and present lemmas for graph sampling and sparse recovery required by our algorithm.

Give an overview of our central algorithm, providing intuition and motivation.

Present an algorithm of Miller and Peng ([MP12]) for building a chain of coarse sparsifiers and prove our main result, assuming a primitive for sampling edges by effective resistance in the streaming model.

Develop this sampling primitive, our main technical contribution.

Show how to extend the algorithm to weighted graphs.

Show how to extend the algorithm to general structured matrices.

Remove our assumption of fully independent hash functions, using a pseudorandom number generator to achieve a final small space algorithm.

Notation and Preliminaries

We write the vertex edge incidence matrix of an unweighted, undirected graph $G(V,E)$ as $\mathbf{B}=\mathbf{S}\mathbf{B}_{n}$ where $\mathbf{S}$ is an ${n\choose 2}\times{n\choose 2}$ diagonal matrix with ones at positions corresponding to edges contained in $G$ and zeros elsewhere.Typically rows of $\mathbf{B}$ that are all are removed, but we find this formulation more convenient for our purposes. The $n\times n$ Laplacian matrix of $G$ is given by $\mathbf{K}=\mathbf{B}^{\top}\mathbf{B}$.

2 Spectral Sparsification

3 Leverage Scores and Row Sampling

The leverage score, $\tau_{i}$, for a row $\mathbf{b}_{i}$ in $\mathbf{B}$ is defined as

The last inequality follows from the fact that every row in a matrix with orthonormal columns has norm less than 1. In a graph, $\tau_{i}=r_{i}w_{i}$, where $r_{i}$ is the effective resistance of edge $i$ and $w_{i}$ is the edge’s weight. Furthermore,

A proof of Lemma 1 based on a matrix concentration result from [Tro12] can be found in [CLM+15] (Lemma 4). Note that, when applied to the vertex edge incidence matrix of a graph, leverage score sampling is equivalent to effective resistance sampling, as introduced in [SS11] for graph sparsification.

4 Sparse Recovery

This procedure allows us to distinguish from a sketch whether or not a specified entry in $\mathbf{x}$ is equal to 0 or has value $>2\eta\|\mathbf{x}\|_{2}$. We give a proof of Lemma 2 in Appendix A

Algorithm Overview

Before formally presenting a proof of our main result, Theorem 1, we give an informal overview of the algorithm to provide intuition.

As explained in Section 2.3, spectral sparsifiers can be generated by sampling edges, i.e. rows of the vertex edge incidence matrix. For an unweighted graph $G$, each edge $e$ is sampled independently with probability proportional to its leverage score, $\tau_{e}$. After sampling, we reweight and combine any sampled edges. The result is a subgraph of $G$ containing, with high probability, $O(\frac{1}{\epsilon^{2}}n\log n)$ edges and spectrally approximating $G$.

If we view $G$ as an electrical circuit, with each edge representing a unit resistor, the leverage score of an edge $e=(i,j)$ is equivalent to its effective resistance. This value can be computed by forcing $1$ unit of current out of vertex $i$ and $1$ unit of current into vertex $j$. The resulting voltage difference between the two vertices is the effective resistance of $e$. Qualitatively, if the voltage drop is low, there are many low resistance (i.e. short) paths between $i$ and $j$. Thus, maintaining a direct connection between these vertices is less critical in approximating $G$, so $e$ is less likely to be sampled. Effective resistance can be computed as:

Note that $\tau_{e}$ can be computed for any pair of vertices, $(i,j)$, or in other words, for any possible edge in $G$. We can evaluate $\mathbf{b}_{e}^{\top}\mathbf{K}^{+}\mathbf{b}_{e}$ even if $e$ is not present in the graph. Thus, we can reframe our sampling procedure. Instead of just sampling edges actually in $G$, imagine we run a sampling procedure for every possible $e$. When recombining edges to form a spectral sparsifier, we separately check whether each edge $e$ is in $G$ and only insert into the sparsifier if it is.

2 Sampling in the Streaming Model

With this procedure in mind, a sampling method that works in the streaming setting requires two components. First, we need to obtain a constant factor approximation to $\tau_{e}$ for any $e$. Known sampling algorithms, including our Lemma 1, are robust to this level of estimation. Second, we need to compress our edge insertions and deletions in such a way that, during post-processing of our sketch, we can determine whether or not a sampled edge $e$ actually exists in $G$.

Solving part two (determining which edges are actually in $G$) is a bit more involved. As a first step, consider writing

Referring to Section 2, recall that $\mathbf{B}=\mathbf{S}\mathbf{B}_{n}$ is exactly the same as a standard vertex edge incidence matrix except that rows in $\mathbf{B}_{n}$ corresponding to nonexistent edges are zeroed out instead of removed. Denote $\mathbf{x}_{e}=\mathbf{S}\mathbf{B}_{n}\mathbf{K}^{+}\mathbf{b}_{e}$. Each nonzero entry in $\mathbf{x}_{e}$ contains the voltage difference across some edge (resistor) in $G$ when one unit of current is forced from $i$ to $j$.

where $\mathbf{x}_{e}^{1/2^{s}}(e)$ is $\mathbf{x}_{e}$ sampled at rate $1/2^{s}\approx\tau_{e}$. Then, as explained, we can use our sparse recovery routine to determine whether or not $e$ is present. If it is, we have obtained a sample for our spectral sparsifier!

3 A Chain of Coarse Sparsifiers

Putting everything together, we maintain $O(\log n)$ sketches for $\begin{bmatrix}\mathbf{K}(0),\mathbf{K}(1),\ldots,\mathbf{K}(d),\mathbf{K}\end{bmatrix}$. We first use a weighted identity matrix as a coarse approximation for $\mathbf{K}(0)$, which allows us to recover a good approximation to $\mathbf{K}(0)$ from our sketch. This approximation will in turn be a coarse approximation for $\mathbf{K}(1)$, so we can recover a good sparsifier of $\mathbf{K}(1)$. Continuing up the chain, we eventually recover a good sparsifier for our final matrix, $\mathbf{K}$.

Recursive Sparsifier Construction

In this section, we formalize a recursive procedure for obtaining a chain of coarse sparsifiers that was introduced by Miller and Peng – “Introduction and Removal of Artificial Bases” [MP12]. We prove Theorem 1 by combining this technique with the sampling algorithm developed in Section 5.

So, $\gamma(0)=\lambda_{u}$ and $\gamma(d)\leq\lambda_{l}$. Then the chain of PSD matrices, $\begin{bmatrix}\mathbf{K}(0),\mathbf{K}(1),\ldots,\mathbf{K}(d)\end{bmatrix}$ with

$\mathbf{K}\preceq_{r}\mathbf{K}(d)\preceq_{r}2\mathbf{K}$,

$\mathbf{K}(0)\preceq 2\gamma(0)\mathbf{I}\preceq 2\mathbf{K}(0)$.

When $\mathbf{K}$ is the Laplacian of an unweighted graph, its largest eigenvalue $\lambda_{max}<2n$ and its smallest non-zero eigenvalue $\lambda_{min}>8/n^{2}$. Thus the length of our chain, $d=\lceil\log_{2}\lambda_{u}/\lambda_{l}\rceil$, is $O(\log n)$.

Furthermore, by assumption we have the inequalities:

Finally, to obtain a bonafide graph sparsifier (a weighted subgraph of our streamed graph), let:

Streaming Row Sampling

In this section, we develop the sparsifier refinement routine required for Theorem 1.

The challenge in the semi-streaming setting is actually sampling edges given only a sketch of $\mathbf{B}$. The general idea is explained in Section 3, with detailed pseudocode included below.

For $s\in\{1,...O(\log n)\}$ let $h_{s}:{n\choose 2}\rightarrow\{0,1\}$ be a uniform hash function. Let $\mathbf{B}_{s}$ be $\mathbf{B}$ with all rows except those with $\prod_{j\leq s}h_{j}(e)=0$ zeroed out. So $\mathbf{B}_{s}$ is $\mathbf{B}$ with rows sampled independently at rate $\frac{1}{2^{s}}$. $\mathbf{B}_{0}$ is simply $\mathbf{B}$.

Maintain sketchs $\mathbf{\Pi}_{0}\mathbf{B}_{0},\mathbf{\Pi}_{1}\mathbf{B}_{1},...,\mathbf{\Pi}_{O(\log n)}\mathbf{B}_{O(\log n)}$ where $\{\mathbf{\Pi}_{0},\mathbf{\Pi}_{1},...\mathbf{\Pi}_{O(\log n)}\}$ are drawn from the distribution from Lemma 2 with $\eta=\frac{\epsilon}{c_{1}\sqrt{\log n}}$.

Output all of these sketches stacked: $\boldsymbol{\Pi}\mathbf{B}=\mathbf{\Pi}_{0}\mathbf{B}_{0}\oplus\ldots\oplus\mathbf{\Pi}_{O(\log n)}\mathbf{B}_{O(\log n)}$.

For every edge $e$ in the set of ${n\choose 2}$ possible edges:

If it is determined that $\mathbf{x}_{e}(e)\neq 0$ set $\mathbf{W}(e,e)=2^{s}$.

Implementation in the Semi-Streaming Model.

Unfortunately, storing $O(\log n)$ uniform hash functions over ${n\choose 2}$ requires $O(n^{2}\log n)$ space, and is thus impossible in the semi-streaming setting. If Section 8 we show how to cope with this issue by using a small-seed pseudorandom number generator.

For step 2(a), the $s$ chosen to guarantee $\min\{1,p_{e}\}\leq\frac{1}{2^{s}}\leq\min\{1,2p_{e}\}$ could in theory be larger than the index of the last sketch $\boldsymbol{\Pi}_{i}\mathbf{B}_{i}$ maintained. However, if we take $O(\log n)$ samplings, our last will be empty with high probability. Accordingly, all samplings for higher values of $s$ can be considered empty as well and we can just skip steps 2(b) and 2(c) for such values of $s$. Thus, $O(\log n)$ sampling levels are sufficient.

Correctness

The probability that $\mathbf{b}_{e}$ is included in the sampled matrix $\mathbf{B}_{s(e)}$ is simply $1/2^{s(e)}$, and sampling is done independently using uniform hash functions. So, we just need to show that, with high probability, any $\mathbf{b}_{e}$ included in its respective $\mathbf{B}_{s(e)}$ is recovered by Step 2(b).

we can set $\delta=\epsilon$ and conclude that

Sparsification of Weighted Graphs

Sparsification of Structured Matrices

We overcome this problem by modifying our algorithm to compute more sketches. Rather than computing a single $\mathbf{\Pi}\mathbf{A}_{s}$, for every sampling rate $1/2^{s}$, we compute $O(\log n)$ sketches of different samplings of $\mathbf{A}$ at rate $1/2^{s}$. Each sampling is fully independent from the all others, including those at the same and different rates. This differs from the graph case, where $\mathbf{B}_{1/2^{s+1}}$ was always a subsampling of $\mathbf{B}_{1/2^{s}}$ (for ease of exposition). Our modified set up lets us show that, with high probability, the norm of $\mathbf{x_{i}}^{s(i)}$ is close to its expectation for at least a $(1-\epsilon)$ fraction of the independent samplings for rate $s(i)$. We can recover row $i$ if it is present in one of the ‘good’ samplings.

Ultimately, we argue, in a similar manner to [KP12], that we can sample rows according to some distribution that is close to the distribution obtained by independently sampling rows according to leverage score. Using this primitive, we can proceed as in the previous sections to prove Theorem 4. In Section 7.1, we provide the row sampling subroutine and in Section 7.2, we show how to use this sampling routine to prove Theorem 4.

Our leverage score sampling algorithm for the streaming model is as follows:

For all $s\in[S]$ and $t\in[T]$ maintain sketch $\mathbf{\Pi}_{s}^{(t)}\mathbf{F}_{s}^{(t)}\mathbf{A}$ where each $\mathbf{\Pi}_{s}^{(t)}$ is drawn independently from the distribution in Lemma 2 with $\eta^{2}=\frac{1}{C}$ and $C=c_{1}\epsilon^{-3}\log m\log n$.

Add rows of $\gamma\mathbf{I}$, independently sampled at rate $\frac{1}{2^{s}}$ , to each sketch.

Pick $t_{i}\in[T]$ uniformly at random and use Lemma 2 to check if $\mathbf{x}_{s_{i}}^{(t_{i})}(i)^{2}\geq C^{-1}\|\mathbf{x}_{s_{i}}^{(t_{i})}\|_{2}^{2}$.

If $i$ is recovered, add row $i$ to the set of sampled edges with weight $2^{s_{i}}$.

2 Generalized Recursive Sparsification

Next we show how to construct a spectral sparsifier in the streaming model for a general structured matrix using the row sampling subroutine, RowSampleMatrix. In the graph case, Theorem 1 shows that, if we can find a sparsifier to a graph $G$ using a coarse sparsifier, then we can use the chain of spectrally similar graphs provided in Theorem 2 to find a final $(1\pm\epsilon)$ sparsifier for our input graph.

The proof of Theorem 1 includes our third reliance on the fact that we are sparsifying graphs – we claim that the condition number of an unweighted graph is polynomial in $n$. This fact does not hold in the general matrix case since the condition number can be exponentially large even for bounded integer matrices. Therefore, our result for general matrix depends on the condition number of $\mathbf{A}$.

Using a Pseudorandom Number Generator

In the proof of our sketching algorithm, Theorem 3, we assume that MaintainSketches has access to $O(\log n)$ uniform random hash functions, $h_{1},\ldots,h_{O(\log n)}$ mapping every edge to $\{0,1\}$. These functions are used to subsample our vertex edge incidence matrix, $\mathbf{B}$, at geometrically decreasing rates. Storing the functions as described would require $O(n^{2}\log n)$ space - we need $O(\log n)$ random bits for each possible edge.

Any randomized algorithm running in $space(S)$ and using $R$ random bits may be converted to one that uses only $O(S\log R)$ random bits (and runs in space $O(S\log R)$).

[Nis92] gives this conversion explicitly by describing a method for generating $R$ pseudorandom bits from $O(S\log R)$ truly random bits. For any algorithm running in $space(S)$, the pseudorandom bits are “good enough” in that the output distribution of the algorithm under pseudorandom bits is very close to the output distribution under truly random bits. In particular, the total variation distance between the distributions is at worst $2^{-O(S)}$ (see Lemma 3 in [Nis92]). It follows that using pseudorandom bits increases the failure probability of any randomized algorithm by just $2^{-O(S)}$ in the worst case.

Acknowledgements

We would like to thank Richard Peng for pointing us to the recursive row sampling algorithm contained in [MP12], which became a critical component of our streaming algorithm. We would also like to thank Jonathan Kelner for useful discussions and Jelani Nelson for a helpful initial conversation on oblivious graph compression.

This work was partially supported by NSF awards 0843915, 1111109, and 0835652, CCF-1065125, CCF-AF-0937274, CCF-0939370, and CCF-1217506, NSF Graduate Research Fellowship grant 1122374, Hong Kong RGC grant 2150701, AFOSR grants FA9550-13-1-0042 and FA9550-12-1-0411, MADALGO center, Simons Foundation, and the Defense Advanced Research Projects Agency (DARPA).

References

Appendix A Sparse Recovery

where $\mathbf{x}_{k}$ is the best $k$-term approximation to $\mathbf{x}$ and $C>1$. Our main sparse recovery primitive is the following result of [GLPS12]:

with probability at least $3/4$. The decoding algorithm runs in time $O(k\log^{O(1)}N/\epsilon)$.

Using this primitive, we can prove Lemma A.

Note that since we are only using Markov’s inequality, it is sufficient to have $h$ be pairwise independent. Such a function $h$ can be represented in small space. Now invoke the result of Theorem 7 on $\mathbf{y}^{h(i)}$ with $k=1$, $\epsilon=1$, and let $\mathbf{w}^{h(i)}$ be the output. We have

This shows that applying sketches from Theorem 7 to vectors $\mathbf{y}^{j}$, for $j=1,\ldots,16/\eta^{2}$ and outputting the vector $\mathbf{w}$ with $\mathbf{w}_{i}=\mathbf{w}^{h(i)}_{i}$ allows us to recover all $i\in[N]$ with $\eta\|\mathbf{x}\|_{2}$ additive error with probability at least $3/4-1/8$.

Appendix B Recursive Sparsification

For completeness, we give a short proof of Theorem 2:

So, $\gamma(d)\leq\lambda_{l}$ and $\gamma(0)=\lambda_{u}$. Then the chain of PSD matrices, $\begin{bmatrix}\mathbf{K}(0),\mathbf{K}(1),\ldots,\mathbf{K}(d)\end{bmatrix}$ with:

$\mathbf{K}\preceq_{r}\mathbf{K}(d)\preceq_{r}2\mathbf{K}$

$\mathbf{K}(0)\preceq 2\gamma(0)\mathbf{I}\preceq 2\mathbf{K}(0)$

When $\mathbf{K}$ is the Laplacian of an unweighted graph, $\lambda_{max}<2n$ and $\lambda_{min}>8/n^{2}$ (where here $\lambda_{min}$ is the smallest nonzero eigenvalue). Thus the length of our chain, $d=\lceil\log_{2}\lambda_{u}/\lambda_{l}\rceil$, is $O(\log n)$.

Relation 1 follows trivially from the fact that $\gamma(d)\leq\lambda_{l}$ is smaller than the smallest nonzero eigenvalue of $\mathbf{K}$. For any $\mathbf{x}\perp\operatorname*{ker}(\mathbf{K})$:

The other direction follows from $\gamma(d)\mathbf{I}\succeq 0$. Using the same argument, relation 3 follows from the fact that $\gamma(0)\geq\lambda_{max}(\mathbf{K})$. For relation 2:

Finally, we need to prove the required eigenvalue bounds. For an unweighted graph, $\lambda_{max}<n$ follows from fact that $n$ is the maximum eigenvalue of the Laplacian of the complete graph on $n$ vertices. $\lambda_{min}>8/n^{2}$ by Lemma 6.1 of [ST14]. Note that this argument extends to weighted graphs when the ratio between the heaviest and lightest edge is bounded by a polynomial in $n$. ∎