Spectral Sparsification of Graphs
Dan Spielman from Yale Institute for Network Science
We introduce a notion of what it means for one graph to be a good spectral approximation of another, and prove that every graph can be well-approximated by a graph with few edges.
We ask how well a given graph can be approximated by a sparse graph. Expander graphs can be viewed as sparse approximations of complete graphs, with Ramanujan expanders providing the best possible approximations. We prove that every graph can be approximated by a sparse graph almost as well as the complete graphs are approximated by the Ramanujan expanders: our approximations employ at most twice as many edges to achieve the same approximation factor.
We also present an efficient randomized algorithm for constructing sparse approximations that only uses a logarithmic factor more edges than optimal.
Our algorithms follow from the solution of a problem in linear algebra. Given any expression of a rank-n symmetric matrix A as a sum of rank-1 symmetric matrices, we show that A can be well approximated by a weighted sum of only O(n) of those rank-1 matrices.
This is joint work with Joshua Batson, Nikhil Srivastava and Shang-Hua Teng.