Graph Sparsification by Effective Resistances

Introduction

The goal of sparsification is to approximate a given graph $G$ by a sparse graph $H$ on the same set of vertices. If $H$ is close to $G$ in some appropriate metric, then $H$ can be used as a proxy for $G$ in computations without introducing too much error. At the same time, since $H$ has very few edges, computation with and storage of $H$ should be cheaper.

We study the notion of spectral sparsification introduced by Spielman and Teng . Spectral sparsification was inspired by the notion of cut sparisification introduced by Benczúr and Karger to accelerate cut algorithms whose running time depends on the number of edges. They gave a nearly-linear time procedure which takes a graph $G$ on $n$ vertices with $m$ edges and a parameter $\epsilon>0$, and outputs a weighted subgraph $H$ with $O(n\log n/\epsilon^{2})$ edges such that the weight of every cut in $H$ is within a factor of $(1\pm\epsilon)$ of its weight in $G$. This was used to turn Goldberg and Tarjan’s $\widetilde{O}(mn)$ max-flow algorithm into an $\widetilde{O}(n^{2})$ algorithm for approximate $st$-mincut, and appeared more recently as the first step of an $\widetilde{O}(n^{3/2}+m)$-time $O(\log^{2}n)$ approximation algorithm for sparsest cut .

In this work, we construct sparsifiers that achieve the same guarantee as Spielman and Teng’s but with $O(n\log n/\epsilon^{2})$ edges, thus improving on both and . Our sparsifiers are subgraphs of the original graph and can be computed in $\widetilde{O}(m)$ time by random sampling, where the sampling probabilities are given by the effective resistances of the edges. While this is conceptually much simpler than the recursive partitioning approach of , we need to solve $O(\log n)$ linear systems to compute the effective resistances quickly, and we do this using Spielman and Teng’s linear equation solver.

Our main idea is to include each edge of $G$ in the sparsifier $H$ with probability proportional to its effective resistance. The effective resistance of an edge is known to be equal to the probability that the edge appears in a random spanning tree of $G$ (see, e.g., or ), and was proven in to be proportional to the commute time between the endpoints of the edge. We show how to approximate the effective resistances of edges in $G$ quickly and prove that sampling according to these approximate values yields a good sparsifier.

To define effective resistance, identify $G=(V,E,w)$ with an electrical network on $n$ nodes in which each edge $e$ corresponds to a link of conductance $w_{e}$ (i.e., a resistor of resistance $1/w_{e}$). Then the effective resistance $R_{e}$ across an edge $e$ is the potential difference induced across it when a unit current is injected at one end of $e$ and extracted at the other end of $e$. Our algorithm can now be stated as follows.

Sparsifiers that satisfy this condition preserve many properties of the graph. The Courant-Fischer Theorem tells us that

and the eigenspaces spanned by corresponding eigenvalues are related. As the eigenvalues of the normalized Laplacian are given by

and are the same as the eigenvalues of the walk matrix $D^{-1}L$, we obtain the same relationship between the eigenvalues of the walk matrix of the original graph and its sparsifier. Many properties of graphs and random walks are known to be revealed by their spectra (see for example ). The existence of sparse subgraphs which retain these properties is interesting its own right; indeed, expander graphs can be viewed as constant degree sparsifiers for the complete graph.

We remark that the condition (2) also implies

where $L^{+}$ is the pseudoinverse of $L$. Thus sparsifiers also approximately preserve the effective resistances between vertices, since for vertices $u$ and $v$, the effective resistance between them is given by the formula $(\chi_{u}-\chi_{v})^{T}L^{+}(\chi_{u}-\chi_{v})$, where $\chi_{u}$ is the elementary unit vector with a coordinate 1 in position $u$.

We prove Theorem 1 in Section 3. At the end of Section 3, we prove that the spectral guarantee (2) of Theorem 1 is not harmed too much if use approximate effective resistances for sampling instead of exact ones(Corollary 6).

In Section 4, we show how to compute approximate effective resistances in nearly-linear time, which is essentially optimal. The tools we use to do this are Spielman and Teng’s nearly-linear time solver and the Johnson-Lindenstrauss Lemma . Specifically, we prove the following theorem, in which $R_{uv}$ denotes the effective resistance between vertices $u$ and $v$.

There is an $\widetilde{O}(m(\log r)/\epsilon^{2})$ time algorithm which on input $\epsilon>0$ and $G=(V,E,w)$ with $r=w_{max}/w_{min}$ computes a $(24\log n/\epsilon^{2})\times n$ matrix $\widetilde{Z}$ such that with probability at least $1-1/n$

Since $\widetilde{Z}(\chi_{u}-\chi_{v})$ is simply the difference of the corresponding two columns of $\widetilde{Z}$, we can query the approximate effective resistance between any pair of vertices $(u,v)$ in time $O(\log n/\epsilon^{2})$, and for all the edges in time $O(m\log n/\epsilon^{2})$. By Corollary 6, this yields an $\widetilde{O}(m(\log r)/\epsilon^{2})$ time for sparsifying graphs, as advertised.

In Section 5, we show that $H$ can be made close to $G$ in some additional ways which make it more useful for preconditioning systems of linear equations.

2 Related Work

Batson, Spielman, and Srivastava have given a deterministic algorithm that constructs sparsifiers of size $O(n/\epsilon^{2})$ in $O(mn^{3}/\epsilon^{2})$ time. While this is too slow to be useful in applications, it is optimal in terms of the tradeoff between sparsity and quality of approximation and can be viewed as generalizing expander graphs. Their construction parallels ours in that it reduces the task of spectral sparsification to approximating the matrix $\Pi$ defined in Section 3; however, their method for selecting edges is iterative and more delicate than the random sampling described in this paper.

The use of effective resistance as a distance in graphs has recently gained attention as it is often more useful than the ordinary geodesic distance in a graph. For example, in small-world graphs, all vertices will be close to one another, but those with a smaller effective resistance distance are connected by more short paths. See, for instance , which use effective resistance/commute time as a distance measure in social network graphs.

Preliminaries

Let $G=(V,E,w)$ be a connected weighted undirected graph with $n$ vertices and $m$ edges and edge weights $w_{e}>0$. If we orient the edges of $G$ arbitrarily, we can write its Laplacian as $L=B^{T}WB$, where $B_{m\times n}$ is the signed edge-vertex incidence matrix, given by

It is immediate that $L$ is positive semidefinite since

We also have $\ker(L)=\ker(W^{1/2}B)=\textrm{span}(\mathbf{1})$, since

2 The Pseudoinverse

Since $L$ is symmetric we can diagonalize it and write

where $\lambda_{1},\ldots,\lambda_{n-1}$ are the nonzero eigenvalues of $L$ and $u_{1},\ldots,u_{n-1}$ are a corresponding set of orthonormal eigenvectors. The Moore-Penrose Pseudoinverse of $L$ is then defined as

Notice that $\ker(L)=\ker(L^{+})$ and that

3 Electrical Flows

Begin by arbitrarily orienting the edges of $G$ as in Section 2.1. We will use the same notation as to describe electrical flows on graphs: for a vector $\mathbf{i_{\textrm{ext}}}(u)$ of currents injected at the vertices, let $\mathbf{i}(e)$ be the currents induced in the edges (in the direction of orientation) and $\mathbf{v}(u)$ the potentials induced at the vertices. By Kirchoff’s current law, the sum of the currents entering a vertex is equal to the amount injected at the vertex:

By Ohm’s law, the current flow in an edge is equal to the potential difference across its ends times its conductance:

by the definition of $L^{+}$ in Section 2.2.

Recall that the effective resistance between two vertices $u$ and $v$ is defined as the potential difference induced between them when a unit current is injected at one and extracted at the other. We will derive an algebraic expression for the effective resistance in terms of $L^{+}$. To inject and extract a unit current across the endpoints of an edge $e=(u,v)$, we set $\mathbf{i_{\textrm{ext}}}=b_{e}^{T}=(\chi_{v}-\chi_{u})$, which is clearly orthogonal to $\mathbf{1}$. The potentials induced by $\mathbf{i_{\textrm{ext}}}$ at the vertices are given by $\mathbf{v}=L^{+}b_{e}^{T}$; to measure the potential difference across $e=(u,v)$, we simply multiply by $b_{e}$ on the left:

It follows that the effective resistance across $e$ is given by $b_{e}L^{+}b_{e}^{T}$ and that the matrix $BL^{+}B^{T}$ has as its diagonal entries $BL^{+}B^{T}(e,e)=R_{e}$.

The Main Result

We will prove Theorem 1. Consider the matrix $\Pi=W^{1/2}BL^{+}B^{T}W^{1/2}$. Since we know $BL^{+}B^{T}(e,e)=R_{e}$, the diagonal entries of $\Pi$ are $\Pi(e,e)=\sqrt{W(e,e)}R_{e}\sqrt{W(e,e)}=w_{e}R_{e}$. $\Pi$ has some notable properties.

(iv) follows from $\Pi^{2}(e,e)=\Pi(\cdot,e)^{T}\Pi(\cdot,e)$, since $\Pi$ is symmetric. ∎

We may describe the outcome of $H=\mathbf{Sparsify}(G,q)$ by the following random matrix:

Suppose $S$ is a nonnegative diagonal matrix such that

To show that $\|\Pi S\Pi-\Pi\Pi\|_{2}$ is likely to be small we use the following concentration result, which is a sort of law of large numbers for symmetric rank 1 matrices. It was first proven by Rudelson in , but the version we state here appears in the more recent paper by Rudelson and Vershynin.

We can now finish the proof of Theorem 1.

$\mathbf{Sparsify}$ samples edges from $G$ independently with replacement, with probabilities $p_{e}$ proportional to $w_{e}R_{e}$. Since $\sum_{e}w_{e}R_{e}=\textrm{Tr}(\Pi)=n-1$ by Lemma 3.(iii), the actual probability distribution over $E$ is given by $p_{e}=\frac{w_{e}R_{e}}{n-1}$. Sampling $q$ edges from $G$ corresponds to sampling $q$ columns from $\Pi$, so we can write

for vectors $y_{1},\ldots,y_{q}$ drawn independently with replacement from the distribution

We can now apply Lemma 5. The expectation of $yy^{T}$ is given by

Taking $q=9C^{2}n\log n/\epsilon^{2}$ gives:

for $n$ sufficiently large, as $\epsilon$ is assumed to be at least $1/\sqrt{n}$.

with probability at least $1/2$. By Lemma 4, this completes the proof of the theorem. ∎

We now show that using approximate resistances for sampling does not damage the sparsifier very much.

Suppose $Z_{e}$ are numbers satisfying $Z_{e}\geq R_{e}/\alpha$ and $\sum_{e}w_{e}Z_{e}\leq\alpha\sum_{e}w_{e}R_{e}$ for some $\alpha\geq 1$. If we sample as in $\mathbf{Sparsify}$ but take each edge with probability $p_{e}^{\prime}=\frac{w_{e}Z_{e}}{\sum_{e}w_{e}Z_{e}}$ instead of $p_{e}=\frac{w_{e}R_{e}}{\sum_{e}w_{e}R_{e}}$, then $H$ satisfies:

and proceed as in the proof of Theorem 1. The norm of the random vector $y$ is now bounded by:

which introduces a factor of $\alpha$ into the final bound on the expectation, but changes nothing else.∎

Computing Approximate Resistances Quickly

It is not clear how to compute all the effective resistances $\{R_{e}\}$ exactly and efficiently. In this section, we show that one can compute constant factor approximations to all the $R_{e}$ in time $\widetilde{O}(m\log r)$. In fact, we do something stronger: we build a $O(\log n)\times n$ matrix $\widetilde{Z}$ from which the effective resistance between any two vertices (including vertices not connected by an edge) can be computed in $O(\log n)$ time.

If $u$ and $v$ are vertices in $G$, then the effective resistance between $u$ and $v$ can be written as:

Thus effective resistances are just pairwise distances between vectors in $\{W^{1/2}BL^{+}\chi_{v}\}_{v\in V}$. By the Johnson-Lindenstrauss Lemma, these distances are preserved if we project the vectors onto a subspace spanned by $O(\log n)$ random vectors. For concreteness, we use the following version of the Johnson-Lindenstrauss Lemma due to Achlioptas .

Our goal is now to compute the projections $\{QW^{1/2}BL^{+}\chi_{v}\}$. We will exploit the linear system solver of Spielman and Teng , which we recall satisfies:

There is an algorithm $x=\mathtt{STSolve}(L,y,\delta)$ which takes a Laplacian matrix $L$, a column vector $y$, and an error parameter $\delta>0$, and returns a column vector $x$ satisfying

where $\left\|y\right\|_{L}=\sqrt{y^{T}Ly}$. The algorithm runs in expected time $\widetilde{O}\left(m\log(1/\delta)\right)$, where $m$ is the number of non-zero entries in $L$.

Let $Q$ be a random $\pm 1/\sqrt{k}$ matrix of dimension $k\times n$ where $k=24\log n/\epsilon^{2}$.

Compute $Y=QW^{1/2}B$. Note that this takes $2m\times 24\log n/\epsilon^{2}+m=\widetilde{O}(m/\epsilon^{2})$ time since $B$ has $2m$ entries and $W^{1/2}$ is diagonal.

We now prove that, for our purposes, it suffices to call STSolve with

for every pair $u,v\in V$. If for all $i$,

Consider an arbitrary pair of vertices $u$, $v$. It suffices to show that

As $G$ is connected, there is a simple path $P$ connecting $u$ to $v$. Applying the triangle inequality twice, we obtain

We will upper bound this later term by considering its square:

by Proposition 10. Combining these bounds, we have

If $G=(V,E,w)$ is a connected graph, then for all $u,v\in V$,

By Rayleigh’s monotonicity law (see ), each resistance $R_{uv}$ in $G$ is at least the corresponding resistance $R_{uv}^{\prime}$ in $G^{\prime}=w_{{max}}\times K_{n}$ (the complete graph with all edge weights $w_{{max}}$) since $G^{\prime}$ is obtained by increasing weights (i.e., conductances) of edges in $G$. But by symmetry each resistance $R_{uv}^{\prime}$ in $G^{\prime}$ is exactly

Thus $R_{uv}\geq\frac{2}{nw_{{max}}}$ for all $u,v\in V$. ∎

Thus the construction of $\widetilde{Z}$ takes $\widetilde{O}(m\log(1/\delta)/\epsilon^{2})=\widetilde{O}(m\log r/\epsilon^{2})$ time. We can then find the approximate resistance $\|\widetilde{Z}(\chi_{u}-\chi_{v})\|^{2}\approx R_{uv}$ for any $u,v\in V$ in $O(\log n/\epsilon^{2})$ time simply by subtracting two columns of $\widetilde{Z}$ and computing the norm of their difference. ∎

Using the above procedure, we can compute arbitrarily good approximations to the effective resistances $\{R_{e}\}$ which we need for sampling in nearly-linear time. By Corollary 6, any constant factor approximation yields a sparsifier, so we are done.

An Additional Property

Corollary 6 suggests that $\mathbf{Sparsify}$ is quite robust with respect to changes in the sampling probabilities $p_{e}$, and that we may be able to prove additional guarantees on $H$ by tweaking them. In this section, we prove one such claim.

The following property is desirable for using $H$ to solve linear systems (specifically, for the construction of ultrasparsifiers , which we will not define here):

This says, roughly, that not too many of the edges incident to any given vertex get blown up too much by sampling and rescaling. We show how to incorporate this property into our sparsifiers.

Suppose we sample $q>4n\log n/\beta$ edges of $G$ as in $\mathbf{Sparsify}$ with probabilities that satisfy

for some constant $0<\beta<1$. Then with probability at least $1-1/n$,

For a vertex $v$, define i.i.d. random variables $X_{1},\ldots,X_{q}$ by:

so that $X_{i}$ is set to $1/p_{e}$ with probability $p_{e}$ for each edge $e$ attached to $v$. Let

We want to show that with high probability, $D_{v}\leq 2\deg(v)$ for all vertices $v$. We begin by bounding the expectation and variance of each $X_{i}$:

Since the $X_{i}$ are independent, the variance of $D_{v}$ is just

We now apply Bennett’s inequality for sums of i.i.d. variables (see, e.g., ), which says

Taking a union bound over all $v$ gives the desired result.∎

satisfies the requirements of both Corollary 6 (with $\alpha=2$) and Lemma 11 (with $\beta=1/2$) and yields a sparsifier with the desired property.

References