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
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
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
pe = min ( 1,C/min(du, dv)) for each edge e = (u,v),
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
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.
is a ( 1 + ε)-spectral
Then with probability at least 1/2,
approximation of G.