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.