Doi: 10.1145/2492007.2492029
Spectral Sparsification of Graphs:
Theory and Algorithms
abstract
Graph sparsification is the approximation of an arbitrary
graph by a sparse graph.
We explain what it means for one graph to be a spectral
approximation of another and review the development of
algorithms for spectral sparsification. In addition to being
an interesting concept, spectral sparsification has been
an important tool in the design of nearly linear-time algorithms for solving systems of linear equations in symmetric,
diagonally dominant matrices. The fast solution of these
linear systems has already led to breakthrough results in
combinatorial optimization, including a faster algorithm
for finding approximate maximum flows and minimum cuts
in an undirected network.
1. intRoDuction
A sparse graph is one whose number of edges is reasonably viewed as being proportional to its number of vertices. In contrast, the complete graph on n vertices, with
about n2/2 edges, is the paradigmatic dense graph. Sparse
graphs are often easier to handle than dense ones. Most
graph algorithms run faster, sometimes by orders of magnitude, when there are fewer edges, and the graph itself
can be stored more compactly. By approximating a dense
graph of interest by a suitable sparse one, one can save
time and space.
We will work with weighted graphs, where the weights
might represent capacities, conductance, similarity, or
just coefficients in a linear system. In a sparse graph, all
of the edges can be important for a graph’s structure. In a
tree, for example, each edge provides the only path between
its endpoints. Not so in a dense graph, where some edges
will serve similar functions. A collection of low-weight
edges connecting two clusters of vertices in a graph might
be approximable by a single high-weight edge connecting
vertices representative of those clusters. Sparsification can
be viewed as a procedure for finding a set of representative
edges and weighting them appropriately.
What exactly do we mean by sparse? We would certainly
consider a graph sparse if its average degree were less than
10, and we would probably consider a graph sparse if it had
one billion vertices and average degree one hundred. We
formalize the notion of sparsity in the usual analysis-of-algorithms way by considering infinite families of graphs,
and proclaiming sparse those whose average degrees are
bounded by some constant, or perhaps by a polynomial in
the logarithm of their number of vertices.
One may at first think that sparsification is unnecessary,
as common wisdom holds that all large real-world graphs
are sparse. While this may be true of natural graphs such as
social networks, it is not true of the graphs that arise inside
algorithms. Many algorithms involve the construction of
graphs that are dense, even when solving problems on
graphs that are sparse. Moreover, the common wisdom may
be an artifact of the difficulty of storing and manipulating a
large dense graph. Improvements in sparsification may one
day ameliorate these difficulties.
2. notions of similaRity
A few conventions: we specify a weighted graph by a
3-tuple, G = (V, E, w), with vertex set V = { 1, …, n}, edge set
E ⊆ {(u, v) | u, v ∈ V}, and weights w(u, v) > 0 for each (u, v) ∈ E.
All graphs will be undirected and weighted, unless otherwise stated. We sometimes express a graph simply by G = (V, w),
as E can be defined implicitly by setting w(u, v) = 0 for all
(u, v) ∉ E. We will always write n for the number of vertices in
a graph and m for the number of edges. When measuring
the similarity between two graphs, we will always assume
that they have the same set of vertices.
2. 1. cut similarity
The notion of cut similarity of graphs was first considered
by Benczúr and Karger8 as part of an effort to develop fast
algorithms for the minimum cut and maximum flow problems. In these problems, one is interested in the sum of the
weights of edges that are cut when one divides the vertices of
a graph into two pieces. Two weighted graphs on the same
vertex set are cut-similar if the sum of the weights of the
edges cut is approximately the same in each such division.
To write this symbolically, we first observe that a division
of the vertices into two parts can be specified by identifying
A previous version of the paper, “Twice-Ramanujan
Sparsifiers,” was published in the Proceedings of the
41st Annual ACM Symposium on the Theory of Computing
(2009), 255–262.