Spectral Sparsification of Graphs

Introduction

Graph sparsification is the task of approximating a graph by a sparse graph, and is often useful in the design of efficient approximation algorithms. Several notions of graph sparsification have been proposed. For example, Chew [Che89] was motivated by proximity problems in computational geometry to introduce graph spanners. Spanners are defined in terms of the distance similarity of two graphs: A spanner is a sparse graph in which the shortest-path distance between every pair of vertices is approximately the same in the original graph as in the spanner. Motivated by cut problems, Benczur and Karger [BK96] introduced a notion of sparsification that requires that for every set of vertices, the weight of the edges leaving that set should be approximately the same in the original graph as in the sparsifier.

Motivated by problems in numerical linear algebra and spectral graph theory, we introduce a new notion of sparsification that we call spectral sparsification. A spectral sparsifier is a subgraph of the original whose Laplacian quadratic form is approximately the same as that of the original graph on all real vector inputs. The Laplacian matrix For more information on the Laplacian matrix of a graph, we refer the reader to one of [Bol98, Moh91, GR01, Chu97]. of a weighted graph $G=(V,E,w)$, where $w_{(u,v)}$ is the weight of edge $(u,v)$, is defined by

It is better understood by its quadratic form, which on $x\in{\rm I\kern-2.0ptR}^{V}$ takes the value

We say that $\widetilde{G}$ is a $\sigma$-spectral approximation of $G$ if for all $x\in{\rm I\kern-2.0ptR}^{V}$

Our notion of sparsification captures the spectral similarity between a graph and its sparsifiers. It is a stronger notion than the cut sparsification of Benczur and Karger: the cut-sparsifiers constructed by Benczur and Karger [BK96] are only required to satisfy these inequalities for all $x\in\left\{0,1\right\}^{V}$. In Section 5 we present an example demonstrating that these notions of approximation are in fact different.

Our main result is that every weighted graph has a spectral sparsifier with $\widetilde{\mathcal{O}}\left(n\right)$ edges that can be computed in $\widetilde{\mathcal{O}}\left(m\right)$ time, where we recall that $\widetilde{\mathcal{O}}\left(f(n)\right)$ means $O(f(n)\log^{c}f(n))$, for some constant $c$. In particular, we prove that for every weighted graph $G=(V,E,w)$ and every $\epsilon>0$, there is a re-weighted subgraph of $G$ with $\widetilde{\mathcal{O}}\left(n/\epsilon^{2}\right)$ edges that is a $(1+\epsilon)$ approximation of $G$. Moreover, we show how to find such a subgraph in $\widetilde{\mathcal{O}}\left(m\right)$ time, where $n=\left|V\right|$ and $m=\left|E\right|$. The constants and powers of logarithms hidden in the $\widetilde{\mathcal{O}}$-notation in the statement of our results are quite large. Our goal in this paper is not to produce sparsifiers with optimal parameters, but rather just to prove that spectral sparsifiers with a nearly-linear number of edges exist and that they can be found in nearly-linear time.

Our sparsification algorithm makes use of a nearly-linear time graph partitioning algorithm, $\mathtt{ApproxCut}$, that we develop in Section 8 and which may be of independent interest. On input a target conductance $\phi$, $\mathtt{ApproxCut}$ always outputs a set of vertices of conductance less than $\phi$. With high probability, if the set it outputs is small then its complement is contained in a subgraph of conductance at least $\Omega(\phi^{2}/\log^{4}m)$.

The Bigger Picture

This paper arose in our efforts to design nearly-linear time algorithms for solving diagonally-dominant linear systems, and is the second in a sequence of three papers on the topic. In the first paper [ST08a], we develop fast routines for partitioning graphs, which we then use in our algorithms for building sparsifiers. In the last paper [ST08b], we show how to use sparsifiers to build preconditioners for diagonally-dominant matrices and thereby solve linear equations in such matrices in nearly-linear time. Koutis, Miller and Peng [KMP10] have recently developed an algorithm for solving such systems of linear equations in time $O(m\log^{2}n)$ that does not rely upon the sparsifiers of the present paper.

The quality of a preconditioner is measured by the relative condition number, which for the Laplacian matrices of a graph $G$ and its sparsifier $\widetilde{G}$ is

So, if $\widetilde{G}$ is a $\sigma$-spectral approximation of $G$ then $\kappa(G,\widetilde{G})\leq\sigma^{2}$. This means that an iterative solver such as the Preconditioned Conjugate Gradient [Axe85] can solve a linear system in the Laplacian of $G$ to accuracy $\epsilon$ by solving $O(\sigma\log(1/\epsilon))$ linear systems in $\widetilde{G}$ and performing as many multiplications by $G$. As a linear system in a matrix with $m$ non-zero entries may be solved in time $O(nm)$ by using the Conjugate Gradient as a direct method [TB97, Theorem 28.3], the use of the sparsifiers in this paper alone provides an algorithm for solving linear systems in $L_{G}$ to $\epsilon$-accuracy in time $\widetilde{\mathcal{O}}\left(n^{2}\log(1/\epsilon)\right)$, which is nearly optimal when the Laplacian matrix has $\Omega(n^{2})$ non-zero entries. In our paper on solving linear equations [ST08b], we show how to get the time bound down to $\widetilde{\mathcal{O}}\left(m\log(1/\epsilon)\right)$, where $m$ is the number of non-zero entries in $L_{G}$.

Outline

In Section 4, we present technical background required for this paper, and maybe even for the rest of this outline. In Section 5, we present three examples of graphs and their sparsifiers. These examples help motivate key elements of our construction.

There are three components to our algorithm for sparsifying graphs. The first is a random sampling procedure. In Section 6, we prove that this procedure produces good spectral sparsifiers for graphs of high conductance. So that we may reduce the problem of sparsifying arbitrary graphs to that of sparsifying graphs of high conductance, we require a fast algorithm for partitioning a graph into parts of high conductance without removing too many edges. In Section 7, we first prove that such partitions exist, and use them to prove the existence of spectral sparsifiers for all unweighted graphs. In Section 8, we then build on tools from [ST08a] to develop a graph partitioning procedure that suffices. We use this procedure in Section 9 to construct a nearly-linear time algorithm for sparsifying unweighted graphs. We show how to use this algorithm to sparsify weighted graphs in Section 10.

We conclude in Section 11 by surveying recent improvements that have been made in both sparsification and in the partitioning routines on which the present paper depends.

Background and Notation

By $\log$ we always mean the logarithm base $2$, and we denote the natural logarithm by $\ln$.

As we spend this paper studying spectral approximations, we will say “$\sigma$-approximation” instead of “$\sigma$-spectral approximation” wherever it won’t create confusion.

We may express (2) more compactly by employing the notation $A\preccurlyeq B$ to mean

We will overload notation by writing $G\preccurlyeq\widetilde{G}$ for graphs $G$ and $\widetilde{G}$ to mean $L_{G}\preccurlyeq L_{\widetilde{G}}$.

to indicate the graph whose Laplacian is $L_{G}+L_{H}$. That is, the weight of every edge in $G+H$ is the sum of the weights of the corresponding edges in $G$ and $H$. We will use this notation even if $G$ and $H$ have different vertex sets. For example, if their vertex sets are disjoint, then their sum is simply the disjoint union of the graphs. It is immediate that $G\preccurlyeq\widetilde{G}$ and $H\preccurlyeq\widetilde{H}$ imply

In many portions of this paper, we will consider vertex-induced subgraphs of graphs. When we take subgraphs, we always preserve the identity of vertices. This enables us to sum inequalities on the different subgraphs to say something about the original.

For an unweighted graph $G=(V,E)$, we will let $d_{v}$ denote the degree of vertex $v$. For $S$ and $T$ disjoint subsets of $V$, we let $E(S,T)$ denote the set of edges in $E$ connecting one vertex of $S$ with one vertex of $T$. We let $G(S)$ denote the subgraph of $G$ induced on the vertices in $S$: the graph with vertex set $S$ containing the edges of $E$ between vertices in $S$.

The conductance of a graph is related to the smallest non-zero eigenvalue of its Laplacian matrix, but is even more strongly related to the smallest non-zero eigenvalue of its Normalized Laplacian matrix (see [Chu97]), whose definition we now recall. Let $D$ be the diagonal matrix whose $v$-th diagonal is $d_{v}$. The Normalized Laplacian of the graph $G$, written $\mathcal{L}_{G}$, is defined by

It is well-known that both $L_{G}$ and $\mathcal{L}_{G}$ are positive semi-definite matrices, with smallest eigenvalue zero. The eigenvalue zero has multiplicity one if an only if the graph $G$ is connected, in which case the eigenvector of $L_{G}$ with eigenvalue zero is the constant vector (see [Bol98, page 269], or derive from (1)).

Our analysis exploits a discreet version of Cheeger’s inequality[Che70] (see [Chu97, SJ89, DS91]), which relates the smallest non-zero eigenvalue of $\mathcal{L}_{G}$, written $\lambda_{2}(\mathcal{L}_{G})$, to the conductance of $G$.

A few examples

We first consider what a sparsifier of the complete graph should look like. Let $G$ be the complete graph on $n$ vertices. All non-zero eigenvalues of $L_{G}$ equal $n$. So, for every unit vector $x$ orthogonal to the all-1s vector,

From Cheeger’s inequality, one may prove that graphs with constant conductance, called expanders, have a similar property. Spectrally speaking, the best of them are the Ramanujan graphs [LPS88, Mar88], which are $d$-regular graphs all of whose non-zero Laplacian eigenvalues lie between $d-2\sqrt{d-1}$ and $d+2\sqrt{d+1}$. So, if we let $\widetilde{G}$ be a Ramanujan graph in which every edge has been given weight $n/d$, then for every unit vector $x$ orthogonal to the all-1s vector,

Thus, $\widetilde{G}$ is a $\left(1-2\sqrt{d-1}/d\right)^{-1}$-approximation of $G$.

2 Example 2: Joined Complete Graphs

Next, consider a graph on $2n$ vertices obtained by joining two complete graphs on $n$ vertices by a single edge, $e$. Let $V_{1}$ and $V_{2}$ be the vertex sets of the two complete graphs. We claim that a good sparsifier for $G$ may be obtained by setting $\widetilde{G}$ to be the edge $e$ with weight 1, plus $(n/d)$ times a Ramanujan graph on each vertex set. To prove this, let $G_{1}$ and $G_{2}$ denote the complete graphs on $V_{1}$ and $V_{2}$, and let $G_{3}$ denote the graph just consisting of the edge $e$. Similarly, let $\widetilde{G}_{1}$ and $\widetilde{G}_{2}$ denote $(n/d)$ times a Ramanujan graph on each vertex set, and let $\widetilde{G}_{3}=G_{3}$. Recalling the addition we defined on graphs, we have

We already know that for $\sigma=\left(1-2\sqrt{d-1}/d\right)^{-1}$, and $i\in\left\{1,2\right\}$

The other inequality follows by similar reasoning. This example demonstrates both the utility of using edges with different weights, even when sparsifying unweighted graphs, and how we can combine sparsifiers of subgraphs to sparsify an entire graph. Also observe that every sparsifier of $G$ must contain the edge $e$, while no other edge is particularly important.

3 Example 3: Distinguishing cut sparsifiers from spectral sparsifiers

Our last example will demonstrate the difference between our notion of sparsification and that of Benczur and Karger. We will describe graphs $G$ and $\widetilde{G}$ for which $\widetilde{G}$ is not a $\sigma$-approximation of $G$ for any small $\sigma$, but it is a very good sparsifier of $G$ under the definition considered by Benczur and Karger. The vertex set $V$ will be $\left\{0,\dotsc,n-1\right\}\times\left\{1,\dotsc,k\right\}$, where $n$ is even. The graph $\widetilde{G}$ will consist of $n$ complete bipartite graphs, connecting all pairs of vertices $(u,i)$ and $(v,j)$ where $v=u\pm 1\mod n$. The graph $G$ will be identical to the graph $\widetilde{G}$, except that it will have one additional edge $e$ from vertex $(0,1)$ to vertex $(n/2,1)$. As the minimum cut of $G$ has size $2k$, and $\widetilde{G}$ only differs by one edge, $\widetilde{G}$ is a $(1+1/2k)$-approximation of $G$ in the notion considered by Benczur and Karger. To show that $\widetilde{G}$ is a poor spectral approximation of $G$, consider the vector $x$ given by

So, inequality (2) is not satisfied for any $\sigma$ less than $1+n/4k^{2}$.

Sampling Graphs

In this section, we show that if a graph has high conductance, then it may be sparsified by a simple random sampling procedure. The sampling procedure involves assigning a probability $p_{i,j}$ to each edge $(i,j)$, and then selecting edge $(i,j)$ to be in the graph $\widetilde{G}$ with probability $p_{i,j}$. When edge $(i,j)$ is chosen to be in the graph, we multiply its weight by $1/p_{i,j}$. As the graph is undirected, we implicitly assume that $p_{i,j}=p_{j,i}$. Let $A$ denote the adjacency matrix of the original graph $G$, and $\widetilde{A}$ the adjacency matrix of the sampled graph $\widetilde{G}$. This procedure guarantees that

Sampling procedures of this form were examined by Benczur and Karger [BK96] and Achlioptas and McSherry [AM01]. Achlioptas and McSherry analyze the approximation obtained by such a procedure through a bound on the norm of a random matrix of Füredi and Komlós [FK81]. As their bound does not suffice for our purposes, we tighten it by refining the analysis of Füredi and Komlós.

If $\widetilde{G}$ is going to be a sparsifier for $G$, then we must be sure that every vertex in $\widetilde{G}$ has edges attached to it. We guarantee this by requiring that, for some parameter $\Upsilon>1$,

The parameter $\Upsilon$ controls the number of edges we expect to find in the graph, and will be set to at least $\Omega\left(\log n\right)$ to ensure that every vertex has an attached edge.

We will show that if $G$ has high conductance and (4) is satisfied for a sufficiently large $\Upsilon$, then $\widetilde{G}$ will be a good sparsifier of $G$ with high probability. The actual theorem that we prove is slightly more complicated, as it considers the case where we only apply the sampling on a subgraph of $G$.

Let $\epsilon,p\in(0,1/2)$ and let $G=(V,E)$ be an unweighted graph whose smallest non-zero normalized Laplacian eigenvalue is at least $\lambda$. Let $S$ be a subset of the vertices of $G$, let $F$ be the edges in $G(S)$, and let $H=E-F$ be the rest of the edges. Let

and let $\widetilde{G}=(V,\widetilde{F}\cup H)$. Then, with probability at least $1-p$,

$\widetilde{G}$ is a $(1+\epsilon)$-approximation of $G$, and

The number of edges in $\widetilde{F}$ is at most

$\widetilde{G}=\mathtt{Sample}(G,\epsilon,p,\lambda)$ 1. Set $k=\max\left(\log_{2}(3/p),\log_{2}n\right)$. 2. Set $\Upsilon=\left(\frac{12k}{\epsilon\lambda}\right)^{2}$. 3. For every edge $(i,j)$ in $G$, set $p_{i,j}=\min\left(1,\frac{\Upsilon}{\min(d_{i},d_{j})}\right)$. 4. For every edge $(i,j)$ in $G$, with probability $p_{i,j}$ put an edge of weight $1/p_{i,j}$ between vertices $(i,j)$ into $\widetilde{G}$.

Let $D$ be the diagonal matrix of degrees of vertices of $G$. To prove Theorem 6.1, we establish that the 2-norm of $D^{-1/2}(L_{G}-L_{\widetilde{G}})D^{-1/2}$ is probably small Recall that the 2-norm of a symmetric matrix is the largest absolute value of its eigenvalues., and then apply the following lemma.

Let $L$ be the Laplacian matrix of a connected graph $G$, $\widetilde{L}$ be the Laplacian of $\widetilde{G}$, and let $D$ be the diagonal matrix of degrees of $G$. If

$\lambda_{2}\left(D^{-1/2}LD^{-1/2}\right)\geq\lambda$, and

$\left\|D^{-1/2}(L-\widetilde{L})D^{-1/2}\right\|\leq\epsilon$,

then $\widetilde{G}$ is a $\sigma$-approximation of $G$ for

Let $x$ be any vector and let $y=D^{1/2}x$. By assumption, $G$ is connected and so the nullspace of the normalized Laplacian $D^{-1/2}LD^{-1/2}$ is spanned by D^{1/2}{\mbox{\boldmath1}}. Let $z$ be the projection of $y$ orthogonal to D^{1/2}{\mbox{\boldmath1}}, so

The lemma follows from these inequalities. ∎

Let $A$ be the adjacency matrix of $G$ and let $\widetilde{A}$ be the adjacency matrix of $\widetilde{G}$. For each edge $(i,j)$,

To prove Theorem 6.1, we will observe that

where $\widetilde{D}$ is the diagonal matrix of the diagonal entries of $\widetilde{L}$. It will be easy to bound the second of these terms, so we defer that part of the proof to the end of the section. A bound on the first term comes from the following lemma.

Our proof of this lemma applies a modification of techniques introduced by Füredi and Komlós [FK81] (See also the paper by Vu [Vu07] that corrects some bugs in their work). However, they consider the eigenvalues of random graphs in which every edge can appear. Some interesting modifications are required to make an argument such as ours work when downsampling a graph that may already be sparse. We remark that without too much work one can generalize Theorem 6.1 so that it applies to weighted graphs.

Recalling that the eigenvalues of $\Delta^{k}$ are the $k$-th powers of the eigenvalues of $\Delta$, and taking $k$-th roots, we conclude

Recall that the $(v_{0},v_{k})$ entry of $\Delta^{k}$ satisfies

We will now describe a way of coding every sequence $v_{1},\dotsc,v_{k-1}$ that could possibly contribute to the sum. Of course, any sequence containing a consecutive pair $(v_{i-1},v_{i})$ for which $\Delta_{v_{i-1},v_{i}}$ is always zero will contribute zero to the sum. So, for a sequence to have a non-zero contribution, each consecutive pair $(v_{i-1},v_{i})$ must be an edge in the graph $A$. Thus, we can identify every sequence with non-zero contribution with a walk on the graph $A$ from vertex $v_{0}$ to vertex $v_{k}$.

The first idea in our analysis is to observe that most of the terms in this sum are zero. The reason is that, for all $v_{i}$ and $v_{j}$

As $\Delta_{v_{i},v_{j}}$ is independent of every term in $\Delta$ other than $\Delta_{v_{j},v_{i}}$, we see that the term

corresponding to $v_{1},\dotsc,v_{k-1}$, will be zero unless each edge $(v_{i-1},v_{i})$ appears at least twice (in either direction).

We now describe a method for coding all walks in which each edges appears at least twice. We set $T$ to be the set of time steps $i$ at which the edge between $v_{i-1}$ and $v_{i}$ does not appear earlier in the walk (in either direction). Note that $1$ is always an element of $T$. We then let $\tau$ denote the map from $[k]-T\rightarrow T$, indicating for each time step not in $T$ the time step in which the edge traversed first appeared (regardless of in which direction it is traversed). Note that we need only consider the cases in which $\left|T\right|\leq k/2$, as otherwise some edge appears only once in the walk. To finish our description of a walk, we need a map

indicating the vertex encountered at each time $i\in T$.

Using $T$, $\tau$ and $\sigma$, we can inductively reconstruct the sequence $v_{1},\dotsc,v_{k-1}$ by the rules

if $i\not\in T$, and $v_{i-1}=v_{\tau(i)-1}$, then $v_{i}=v_{\tau(i)}$, and

if $i\not\in T$, and $v_{i-1}=v_{\tau(i)}$, then $v_{i}=v_{\tau(i)-1}$.

If $v_{i-1}\not\in\left\{v_{\tau(i)},v_{\tau(i)-1}\right\}$, then the tuple $(T,\tau,\sigma)$ does not properly code a walk on the graph of $A$. We will call $\sigma$ a valid assignment for $T$ and $\tau$ if the above rules do produce a walk on the graph of $A$ from $v_{0}$ to $v_{k}$.

is independent of the others, and involves a product of the terms $\Delta_{v_{s-1},v_{s}}$ and $\Delta_{v_{s},v_{s-1}}$. In Lemma 6.6, we will prove that

To bound the sum of products on the right hand-side of (10), fix $T$ and $\tau$ and consider the following random process for generating a valid $\sigma$ and corresponding walk: go through the elements of $T$ in order. For each $s\in T$, pick $\sigma(s)$ to be a random neighbor of the $s-1$st vertex in the walk. If possible, continue the walk according to $\tau$ until it reaches the next step in $T$. If the process produces a valid $\sigma$, return it. Otherwise, return nothing. The probability that any particular valid $\sigma$ will be returned by this process is

As there are at most at most $2^{k}$ choices for $T$, and at most $\left|T\right|^{k-\left|T\right|}\leq\left|T\right|^{k}$ choices for $\tau$, we may combine inequalities (10) and (11) with (8) to obtain

If $p_{i,j}=1$, then $\Delta_{i,j}=0$. If not, then we have $\Upsilon/\min(d_{i},d_{j})=p_{i,j}<1$. With probability $1-p_{i,j}$,

On the other hand, with probability $p_{i,j}$,

As $\Delta_{i,j}\geq 0$ in this case, we have established $\left|\Delta_{i,j}\right|\leq 1/\Upsilon$. ∎

For all edges $(r,t)$ and integers $k\geq 1$ and $l\geq 0$,

First, if $p_{i,j}=1$, then $\Delta_{i,j}=0$. Second, if $k+l=1$, $\mbox{\bf E}\left[\Delta_{r,t}^{k}\Delta_{t,r}^{l}\right]=0$. So, we may restrict our attention to the case where $k+l\geq 2$ and $p_{i,j}<1$, which by (4) implies $p_{i,j}=\Upsilon/\min(d_{r},d_{t})$. Claim 6.5 tells us that for $k\geq 1$,

A similar statement may be made for $l\geq 1$. So, it suffices to prove the lemma in the case $k+l=2$.

As $\Delta_{r,t}=(\widetilde{A}_{r,t}-1)/d_{r}$ and $\Delta_{t,r}=(\widetilde{A}_{r,t}-1)/d_{t}$, we have

In the case $k=1$, $l=1$, we finish the proof by

This finishes the proofs of Lemmas 6.4 and 6.3. We now turn to the last ingredient we will need for the proof of Theorem 6.1, a bound on the norm of the difference of the degree matrices.

Let $G$ be a graph and let $\widetilde{G}$ be obtained by sampling $G$ with probabilities $p_{i,j}$ that satisfy (4). Let $D$ be the diagonal matrix of degrees of $G$, and let $\widetilde{D}$ be the diagonal matrix of weighed degrees of $\widetilde{G}$. Then,

The lemma now follows by taking a union bound over $i$. ∎

We use the following variant of the Chernoff bound from [Rag88].

Let $\alpha_{1},\dotsc,\alpha_{n}$ all lie in $[0,\beta]$ and let $X_{1},\dotsc,X_{n}$ be independent random variables such that $X_{i}$ equals $\alpha_{i}$ with probability $p_{i}$ and $0$ with probability $1-p_{i}$. Let $X=\sum_{i}X_{i}$ and $\mu=\mbox{\bf E}\left[X\right]=\sum\alpha_{i}p_{i}$. Then,

For $\epsilon<1$, both of these probabilities are at most $e^{-\mu\epsilon^{2}/3\beta}$.

We remark that Raghavan [Rag88] proved this theorem with $\beta=1$; the extension to general $\beta>0$ follows by re-scaling.

Let $L$ be the Laplacian of $G$, $A$ be its adjacency matrix, and $D$ its diagonal matrix of degrees. Let $\widetilde{L}$, $\widetilde{A}$ and $\widetilde{D}$ be the corresponding matrices for $\widetilde{G}$. The matrices $L$ and $\widetilde{L}$ only differ on rows and columns indexed by $S$. So, if we let $L(S)$ denote the submatrix of $L$ with rows and columns in $S$, we have

Applying Lemma 6.3 to the first of these terms, while observing

Applying Lemma 6.7 to the second term, we find

Thus, with probability at least $1-2p/3$,

in which case Lemma 6.2 tells us that $\widetilde{G}$ is a $\sigma$-approximation of $G$ for

Finally, we use Theorem 6.8 to bound the number of edges in $\widetilde{F}$. For each edge $(i,j)$ in $F$, let $X_{(i,j)}$ be the indicator random variable for the event that edge $(i,j)$ is chosen to appear in $\widetilde{F}$. Using $d_{i}$ to denote the degree of vertex $i$ in $G(S)$, we have

One may similarly show that $\mbox{\bf E}\left[\sum X_{(i,j)}\right]\geq\Upsilon\left|S\right|/2$. Applying Theorem 6.8 with $\epsilon=1$ (note that here $\epsilon$ is the parameter in the statement of Theorem 6.8), we obtain

Graph Decompositions

In this section, we prove that every graph can be decomposed into components of high conductance, with a relatively small number of edges bridging the components. A similar result was obtained independently by Trevisan [Tre05]. We prove this result for three reasons: first, it enables us to quickly establish the existence of good spectral sparsifiers. Second, our algorithm for building sparsifiers requires a graph decomposition routine which is inspired by the computationally infeasible routine presented in this section The routine idealDecomp is infeasible because it requires the solution of an NP-hard problem in step 2. We could construct sparsifiers from a routine that approximately satisfies the guarantees of idealDecomp, such as the clustering algorithm of Kannan, Vempala and Vetta [KVV04]. However, their routine could take quadratic time, which is too slow for our purposes. . Finally, the analysis of our algorithm relies upon Lemma 7.2, which occupies most of this section. Throughout this section, we will consider an unweighted graph $G=(V,E)$, with $V=\left\{1,\dotsc,n\right\}$. In the construction of a decomposition of $G$, we will be concerned with vertex-induced subgraphs of $G$. However, when measuring the conductance and volumes of vertices in these vertex-induced subgraphs, we will continue to measure the volume according to the degrees of vertices in the original graph. For clarity, we define the boundary of a vertex set $S$ with respect to another vertex set $B$ to be

we define the conductance of a set $S$ in the subgraph induced by $B\subseteq V$ to be

For convenience, we define $\Phi^{G}_{B}\left(\emptyset\right)=1$ and, for $\left|B\right|=1$, $\Phi^{G}_{B}{}=1$.

We introduce the notation $G\{B\}$ to denote the graph $G(B)$ to which self-loops have been added so that every vertex in $G\{B\}$ has the same degree as in $G$. For $S\subseteq B$

Because $\Phi^{G}_{B}$ measures volume by degrees in $G$ and those degrees are higher than in $G(B)$,

So, when we prove lower bounds on $\Phi^{G}_{B}{}$, we obtain lower bounds on $\Phi_{G(B)}{}$.

We define a decomposition of $G$ to be a partition of $V$ into sets $(A_{1},\dotsc,A_{k})$, for some $k$. We say that a decomposition is a $\phi$-decomposition if $\Phi^{G}_{A_{i}}{}\geq\phi$ for all $i$. We define the boundary of a decomposition, written $\partial\left(A_{1},\dotsc,A_{k}\right)$ to be the set of edges between different vertex sets in the partition:

We say that a decomposition $(A_{1},\dotsc,A_{k})$ is a $\lambda$-spectral decomposition if the smallest non-zero normalized Laplacian eigenvalue of $G(A_{i})$ is at least $\lambda$, for all $i$. By Cheeger’s inequality (Theorem 4.1), every $\phi$-decomposition is a $(\phi^{2}/2)$-spectral decomposition.

Let $G=(V,E)$ be a graph and let $m=\left|E\right|$. Then, $G$ has a $\left(6\log_{4/3}2m\right)^{-1}$-decomposition with $\left|\partial\left(A_{1},\dotsc,A_{k}\right)\right|\leq\left|E\right|/2$.

2 Existence of spectral sparsifiers

Before proving Theorem 7.1, we first quickly explain how to use Theorem 7.1 to prove that spectral sparsifiers exist. Given any graph $G$, apply the theorem to find a decomposition of the graph into components of conductance $\Omega(1/\log n)$, with at most half of the original edges bridging components. Because this decomposition is a $\Omega(1/\log^{2}n)$-spectral decomposition, by Theorem 6.1 we may sparsify the graph induced on each component by random sampling. The average degree in the sparsifier for each component will be $O(\log^{6}n)$. It remains to sparsify the edges bridging components. If only $\widetilde{\mathcal{O}}\left(n\right)$ edges bridge components, then we do not need to sparsify them further. If more edges bridge components, we sparsify them recursively. That is, we treat those edges as a graph in their own right, decompose that graph, sample the edges induced in its components, and so on. As each of these recursive steps reduces the number of edges remaining by at least a factor of two, at most a logarithmic number of recursive steps will be required, and thus the average degree of the sparsifier will be at most $O(\log^{7}n)$. The above process also establishes the following decomposition theorem.

Recently, Batson, Spielman and Srivastava [BSS09] have shown that $(1+\epsilon)$-spectral sparsifiers with $O(n/\epsilon^{2})$ edges exist.

3 The Proof of Theorem 7.1

Theorem 7.1 is not algorithmic. It follows quickly from the following lemma, which says that if the largest set with conductance less than $\phi$ is small, then the graph induced on the complement has conductance almost $\phi$. This lemma is the key component in our proof of Theorem 7.1, and its analog for approximate sparsest cuts (Theorem 8.1) is the key to our algorithm.

Let $S$ be a set of maximum size that satisfies $(C.1)$ and $(C.2)$, let

and assume by way of contradiction that $\Phi^{G}_{B-S}{}<\phi\beta.$ Then, there exists a set $R\subset B-S$ such that

To upper bound the conductance of $T$, we compute

We will prove Theorem 7.1 by proving that the following procedure produces the required decomposition.

To see that the recursive procedure terminates, recall that we have defined $\Phi^{G}_{B}{}=1$ when $\left|B\right|=1$.

Let $(A_{1},\dotsc,A_{k})$ be the output of $\mathtt{idealDecomp}(V)$. Lemma 7.2 implies that $\Phi^{G}_{A_{i}}{}\geq\phi/3$ for each $i$.

Approximate Sparsest Cuts

Unfortunately, it is NP-hard to compute sparsest cuts. So, we cannot directly apply Lemma 7.2 in the design of our algorithm. Instead, we will apply a nearly-linear time algorithm, $\mathtt{ApproxCut}$, that computes approximate sparsest cuts that satisfy an analog of Lemma 7.2, stated in Theorem 8.1. Whereas in Lemma 7.2 we proved that if the largest sparse cut is small then its complement has high conductance, here we prove that if the cut output by $\mathtt{ApproxCut}$ is small, then its complement is contained in a subgraph of high conductance.

The algorithm $\mathtt{ApproxCut}$ works by repeatedly calling a routine for approximating sparsest cuts, $\mathtt{Partition}$, from [ST08a]. On input a graph that contains a sparse cut, with high probability the algorithm $\mathtt{Partition}$ either finds a large cut or a cut that has high overlap with the sparse cut. We have not been able to find a way to quickly use an algorithm satisfying such a guarantee to certify that the complement of a small cut has high conductance. Kannan, Vempala and Vetta [KVV04] showed that if we applied such an algorithm until it could not find any more cuts then we could obtain such a guarantee. However, such a procedure could require quadratic time, which it too slow for our purposes.

Let $\phi,p\in(0,1)$ and let $G=(V,E)$ be a graph with $m$ edges. Let $D$ be the output of $\mathtt{ApproxCut}(G,\phi,p)$. Then

If $D\not=\emptyset$ then $\Phi_{G}\left(D\right)\leq\phi$, and

there exists a set $W\supseteq V-D$ for which $\Phi^{G}_{W}\geq f_{2}(\phi)$, where

Moreover, the expected running time of $\mathtt{ApproxCut}$ is $O\left(\phi^{-4}m\log^{9}m\log(1/p)\right)$.

The code for $\mathtt{ApproxCut}$ follows. It relies on a routine called $\mathtt{Partition2}$ which in turn relies on a routine called $\mathtt{Partition}$ from [ST08a]. While one could easily combine the routines $\mathtt{ApproxCut}$ and $\mathtt{Partition2}$, their separation simplifies our analysis. The algorithm $\mathtt{Partition2}$ is very simple: it just calls $\mathtt{Partition}$ repeatedly and collects the cuts it produces until they contain at least $1/5$ of the volume of the graph or until it has made enough calls. The algorithm $\mathtt{ApproxCut}$ is similar: it calls $\mathtt{Partition2}$ in the same way that $\mathtt{Partition2}$ calls $\mathtt{Partition}$.

The algorithm $\mathtt{Partition}$ from [ST08a], satisfies the following theorem (see [ST08a, Theorem 3.2])

Let $D$ be the output of $\mathtt{Partition}(G,\tau,p)$, where $G$ is a graph and $\tau,p\in(0,1)$. Then

If $D\not=\emptyset$ then $\Phi_{G}\left(D\right)\leq\tau$, and

Moreover, the expected running time of $\mathtt{Partition}$ is $O\left(\tau^{-4}m\log^{7}m\log(1/p)\right)$.

If either $(P.3.a)$ or $(P.3.b)$ occur for a set $S$ satisfying (15), we say that $\mathtt{Partition}$ succeeds for $S$. Otherwise, we say that it fails.

One can view condition $(A.3)$ in Theorem 8.1 as reversing the quantifiers in condition $(P.3)$ in Theorem 8.2. Theorem 8.2 says that for every set $S$ of low conductance there is a good probability that a substantial portion of $S$ is removed. On the other hand, Theorem 8.1 says that with high probability all sets of low conductance will be removed.

The algorithm $\mathtt{Partition2}$ satisfies a guarantee similar to that of $\mathtt{Partition}$, but it strengthens condition $(P.3.b)$.

Let $D$ be the output of \text{\mathtt{Partition2}}(G,\theta,p,\epsilon), where $G$ is a graph, $\theta,p\in(0,1)$ and $\epsilon\in(0,1)$. Then

If $D\not=\emptyset$ then $\Phi_{G}\left(D\right)\leq\theta$, and

Moreover, the expected running time of $\mathtt{Partition2}$ is $O\left(\theta^{-4}m\log^{7}m\log(1/\epsilon)\log(\log(1/\epsilon)/p)\right)$.

If either $(Q.3.a)$ or $(Q.3.b)$ occur for a set $S$ satisfying (16), we say that $\mathtt{Partition2}$ succeeds for $S$. Otherwise, we say that it fails.

The proof of this lemma is routine, given Theorem 8.2.

To prove (Q.3), let $S$ be a set satisfying (16), and let $S_{j}=S\cap W_{j}$. From Theorem 8.2, we know that with probability at least $1-p/r$,

Finally, the bound on the expected running time of $\mathtt{Partition2}$ is immediate from the bound on the running time of $\mathtt{Partition}$. ∎

2 Proof of Theorem 8.1

The rest of this section is devoted to the proof of Theorem 8.1, with all but one line devoted to part (A.3). Our goal is to prove the existence of a set of vertices $W$ of high conductance that contains all the vertices not cut out by $\mathtt{ApproxCut}$. We will construct this set $W$ in stages. Recall that $V_{i}=V-D_{1}\cup\dotsb\cup D_{i}$ is the set of vertices that are not removed by the first $i$ cuts. In stage $i$, we will express $W_{i}$, a superset of $V_{i}$, as a set of high conductance $U_{i-1}$ plus some vertices in $V_{i}$. We will show that in each stage the volume of the vertices that are not in the set of high conductance shrinks by at least a factor of 2.

We then construct sets $S_{i}$, $U_{i}$ and $W_{i}$ by the following inductive procedure.

If $W_{i}$ contains a set $S_{i}$ such that

set $S_{i}$ to be such a set of maximum size.

If there is no such set, set $S_{i}=\emptyset$, set $U_{i}=W_{i}$, stop the procedure and leave $W_{i+1}$ undefined.

Set $\sigma_{i+1}=(1-2\epsilon)\theta_{i}$.

Set $W_{i+1}=U_{i}\cup(S_{i}\cap V_{i+1})$.

Set $W=W_{i}$ where $i$ is the last index for which $W_{i}$ is defined.

Note that there may be many choices for a set $S_{i}$. Once a choice is made, it must be fixed for the rest of the procedure so that we can reason about it using Lemma 8.3.

For all $i$ such that $W_{i+1}$ is defined,

We prove this by induction on $i$. For $i=0$, we know that $V_{i}=W_{i}$. As $W_{i}=U_{i}\cup S_{i}$ and the algorithm ensures $V_{i+1}\subseteq V_{i}$,

Follows immediately from Lemma 7.2 and the definitions of $S_{i}$ and $\theta_{i}$. ∎

We now show that if at most an $\epsilon$ fraction of each $S_{i}$ appears in $V_{i+1}$, then the sets $S_{i}\cap V_{i+1}$ shrink to the point of vanishing.

If all defined $S_{i}$ and $V_{i}$ satisfy

then for all $i\geq 1$ for which $S_{i}$ is defined,

In particular, the set $S_{r}$ is empty if it is defined.

Combining this inequality with $(c)$ yields

Similarly, we may conclude from Lemma 8.6 that

from which the second part of the lemma follows.

We conclude that the set $S_{r}$ must be empty if it is defined. ∎

This geometric shrinking of the volumes of the sets $S_{i}$ allows us to prove a lower bound on $\theta_{i}$.

As $i\leq r$ and $\epsilon=\min(1/5,1/2r)$, we have

To analyze the other product, we apply Lemma 8.7 to prove

We first lower-bound the volume of the intersection of $S_{i}$ with $V_{i}$ by

The proofs of (A.1) and (A.2) are similar to the proofs of (Q.1) and (Q.2).

To prove (A.3), we will assume that for each set $S_{i}$ that satisfies conditions (16) in $G\{V_{i}\}$ the call to $\mathtt{Partition}$2 succeeds and that the same holds for all sets $V_{i}-S_{i}$ that satisfy conditions (16) in $G\{V_{i}\}$. As this assumption involves at most $2r$ sets, by Lemma 8.3 it holds with probability at least $1-2r(p/2r)=1-p$.

Observe that the algorithm $\mathtt{ApproxCut}$ calls $\mathtt{Partition}$2 with

then $S_{i}$ satisfies the conditions (16) in $G\{V_{i}\}$.

We may now apply Lemma 8.7 to show that $S_{r}$ is empty if it is defined. So, there is an $i$ for which $W_{i}=U_{i}$ and by Claim 8.5 and Lemma 8.8

as $V-D=V_{r}\subseteq V_{i}\subseteq W_{i}$, the set $W=W_{i}$ satisfies (A.3.b). ∎

Sparsifying Unweighted Graphs

We now show how to use the algorithms $\mathtt{ApproxCut}$ and $\mathtt{Sample}$ to sparsify unweighted graphs. More precisely, we treat every edge in an unweighted graph as an edge of weight $1$. The algorithm $\mathtt{UnwtedSparsify}$ follows the outline described in Section 7.2. Its main subroutine $\mathtt{PartitionAndSample}$ calls $\mathtt{ApproxCut}$ to partition the graph. Whenever $\mathtt{ApproxCut}$ returns a small cut, we know that the complement is contained in a subgraph of large conductance. In this case, $\mathtt{PartitionAndSample}$ calls $\mathtt{Sample}$ to sparsify the large part. Whenever the cut returned by $\mathtt{ApproxCut}$ is large, $\mathtt{PartitionAndSample}$ recursively acts on the cut and its complement so that it eventually partitions and samples both. The output of $\mathtt{PartitionAndSample}$ is the result of running $\mathtt{Sample}$ on the graphs induced on the vertex sets of a decomposition of the original graph. The main routine $\mathtt{UnwtedSparsify}$ calls $\mathtt{PartitionAndSample}$ and then acts recursively to sparsify the edges that go between the parts of the decomposition produced by $\mathtt{PartitionAndSample}$.

Let $G=(V,E)$ be a graph. Let $\widetilde{G}_{1},\dotsc,\widetilde{G}_{k}$ be the output of $\mathtt{PartitionAndSample}(G,\phi,\hat{\epsilon},\hat{p})$. Let $V_{1},\dotsc,V_{k}$ be the vertex sets of $\widetilde{G}_{1},\dotsc,\widetilde{G}_{k}$, respectively, and let $G_{0}$ be the graph with vertex set $V$ and edge set $\partial\left(V_{1},\dotsc,V_{k}\right)$.

$\left|\partial\left(V_{1},\dotsc,V_{k}\right)\right|\leq\left|E\right|/2$.

the total number of edges in $\widetilde{G}_{1},\dotsc,\widetilde{G}_{k}$ is at most $c_{3}\epsilon^{{-2}}\left|V\right|\log^{30}(n/p)$, for some absolute constant $c_{3}$.

We will assume for the rest of the analysis that

for every call to $\mathtt{Sample}$ in line 2, $\widetilde{G}_{1}$ is a $(1+\hat{\epsilon})$ approximation of $G$ and the number of edges in $\widetilde{G}_{1}$ satisfies (S.2),

for every call to $\mathtt{Sample}$ in line 3a, $\widetilde{G}_{1}+G(D)+\partial\left(D,V-D\right)$ is a $(1+\hat{\epsilon})$ approximation of $G$ and the number of edges in $\widetilde{G}_{1}$ satisfies (S.2), and

First observe that at most $n$ calls are made to $\mathtt{Sample}$ and $\mathtt{ApproxCut}$ during the course of the algorithm. By Theorem 8.1, the probability that assumption $3$ fails is at most $n\hat{p}$. If assumption $3$ never fails, we may apply Theorem 6.1 to prove that assumptions 1 and 2 probably hold, as follows. Consider a subgraph $G(V-D)$ on which $\mathtt{Sample}$ is called, using $D=\emptyset$ if $\mathtt{Sample}$ is called on line 2. Assumption 3 tells us that there is a set $W\supseteq V-D$ for which $\Phi^{G}_{W}\geq f_{2}(\phi)$. Theorem 4.1 tells us that the smallest non-zero normalized Laplacian eigenvalue of $G(W)$ is at least $\lambda$, where $\lambda$ is set in line $0$. Treating $G(W)$ as the input graph, and $S=V-D$, we may apply Theorem 6.1 to show that assumptions $1$ and $2$ fail with probability at most $\hat{p}$ each. Thus, all three assumptions hold with probability at least $1-3n\hat{p}$.

Property $(PS.3)$, and the existence of the constant $c_{3}$, is a consequence of assumptions $1$ and $2$. Using these assumptions, we will now establish $(PS.2)$ by induction on the depth of the recursion. For a graph $G$ on which $\mathtt{PartitionAndSample}$ is called, let $d$ be the maximum depth of recursive calls of the algorithm on $G$, let $\widetilde{G}_{1},\dotsc,\widetilde{G}_{k}$ be output of $\mathtt{PartitionAndSample}$ on $G$, and let $V_{1},\dotsc,V_{k}$ be the vertex sets of $\widetilde{G}_{1},\dotsc,\widetilde{G}_{k}$, respectively. We will prove by induction on $d$ that

We base our induction on the case in which the algorithm does not call itself, in which case it returns the output of $\mathtt{Sample}$ in line $2$, and the assertion follows from assumption 1.

is a $(1+\hat{\epsilon})^{d}$-approximation of $H$. We then have

is a $(1+\hat{\epsilon})^{d}$-approximation of $G$, establishing (19) in the second case.

For $\epsilon,p\in(0,1/2)$ and an unweighted graph $G$ with $n$ vertices, let $\widetilde{G}$ be the output of $\mathtt{UnwtedSparsify}(G,\epsilon,p)$. Then,

The edges of $\widetilde{G}$ are a subset of the edges of $G$; and

$\widetilde{G}$ is a $(1+\epsilon)$-approximation of $G$, and

$\widetilde{G}$ has at most $c_{4}\epsilon^{-2}n\log^{31}(n/p)$ edges, for some constant $c_{4}$.

Moreover, the expected running time of $\mathtt{UnwtedSparsify}$ is $O\left(m\log(1/p)\log^{15}n\right)$.