Communications of the ACM

used to obtain a good spectral sparsifier for every graph. Their construction was strongly motivated by the work of Benczúr and Karger8 and Achlioptas and McSherry. 2

The sampling procedure involves assigning a probability pu, v to each edge (u, v) Î G, and then selecting edge (u, v) to be in the graph with probability pu, v. When edge (u, v) is chosen to be in the graph, we multiply its weight by 1/pu, v.

This procedure guarantees that The key step in this approach is to determine the sampling probability pu, v for each edge; there is a tension between choosing small pu, v to generate a sparser and choosing larger pu, v to more accurately approximate G. Spielman and Teng recognized that some edges are more essential than others, and used a graph decomposition process to implicitly identify these edges and set the sampling probabilities accordingly.

1/2 1/2, GG D LD − − = L

where D is the diagonal matrix whose u-th entry is du. The discrete version3, 31 of Cheeger’s11 inequality (Theorem 2) relates the second eigenvalue of the normalized Laplacian to the conductance of a graph.

Theorem 2 (Discrete Cheeger Inequality).

We define a decomposition of G to be a partition of V into
sets (A1, …, Ak), for some k. The boundary of a decomposition
(A1, …, Ak) is then the set of edges between different vertex
sets in the partition:
We say that the decomposition is a f-decomposition if
for all i, where G(Ai) denotes the subgraph induced
on Ai. It is a λ-spectral decomposition if the smallest non-zero
normalized Laplacian eigenvalue of G(Ai) is at least λ, for
all i. By Cheeger’s inequality, every f -decomposition is a
(f 2/2)-spectral decomposition.

The following two theorems (see Spielman and Teng34) together imply that for all ε, every graph has a (( 1 + ε), O(ε− 2 log7 n) )-spectral sparsifier.

Theorem 3 (Spectral Decomposition). Every G has an Ω (log−2n)-spectral decomposition with boundary size at most |E|/2.

Theorem 4 (Sampling works for Expanders). Suppose ε ∈ (0, 1/2) and G = (V, E) is an unweighted graph with smallest non-zero normalized Laplacian eigenvalue at least λ. Let

= (V, , ) be a graph obtained by sampling the edges of G with probabilities

pe = min ( 1,C/min(du, dv)) for each edge e = (u,v),

where

C = Θ ((log n) 2 (ελ)- 2)

and setting weights (e) = 1/pe for e ∈ . Then, with probability at least 1/2, is a ( 1 + ε)-spectral approximation of G, and the average degree of is O( (log n) 2 (ελ)− 2)

To construct a spectral sparsifier of an arbitrary unweighted graph, we first apply Theorem 3 to find a W -spectral decomposition of the graph in which the boundary has at most half the edges. We then sparsify each of the components by random sampling, and we sparsify the graph formed by the boundary edges recursively. Adding the sparsifiers obtained yields a sparsifier for the original graph, as desired.

3. 3. sampling by effective resistance

By using effective resistances to define the edge sampling probabilities pe, Spielman and Srivastava32 proved that every graph has a (( 1 + ε), O(log n/ε2))-spectral sparsifier. These spectral sparsifiers have a similar number of edges to the cut sparsifiers described in Theorem 1, and many fewer edges than those produced by Spielman and Teng34. We define Re, the effective resistance of an edge e, to be the effective resistance between its endpoints. It is well-known that Re is proportional to the commute time between the end-vertices of e, 10 and is equal to the probability that e appears in a random spanning tree of G. Spielman and Srivastava proved that sampling with edge probability pe proportional to weRe is the “right” distribution for creating spectral sparsifiers.

Theorem 5 (Sampling by Effective Resistance). For any weighted graph G = (V, E, w) and 0 < ε ≤ 1, let be the graph obtained by the following random process:

Set q = 8n log n/ε2. Choose a random edge of G with probability pe proportional to weRe, and add e to the edge set of with weight we/qpe. Take q samples independently with replacement, summing weights if an edge is chosen more than once.