Joshua Batson
Skip Abstract Section
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.
- Abraham, I., Neiman, O. Using petal-decompositions to build a low stretch spanning tree. In (2012).Google Scholar
- Achlioptas, D., Mcsherry, F. Fast computation of low-rank matrix approximations., 2 (2007), 9.Google Scholar
- Alon, N., Milman, V.D. λ1, isoperimetric inequalities for graphs, and superconcentrators., 1 (1985), 73--88.Google Scholar
- Althöfer, I., Das, G., Dobkin, D., Joseph, D., Soares, J. On sparse spanners of weighted graphs. (1993), 81--100, 10.1007/BF02189308. Google ScholarDigital Library
- Andersen, R., Chung, F., Lang, K. Local graph partitioning using pagerank vectors. In (2006), 475--486. Google ScholarDigital Library
- Andersen, R., Yuval, P. Finding sparse cuts locally using evolving sets. In (2009), ACM, 235--244. Google ScholarDigital Library
- Batson, J.D., Spielman, D.A., Srivastava, N. Twice-Ramanujan sparsifiers. 6 (2012), 1704--1721.Google Scholar
- Benczúr, A.A., Karger, D.R. Approximating s-t minimum cuts in O(n2) time. In (1996), 47--55. Google ScholarDigital Library
- Bollobás, B. The isoperimetric number of random regular graphs., 3 (May 1988), 241--244. Google ScholarDigital Library
- Chandra, A.K., Raghavan, P., Ruzzo, W.L., Smolensky, R., Tiwari, P. The electrical resistance of a graph captures its commute and cover times. In (1989), ACM, New York, NY, USA, 574--586. Google ScholarDigital Library
- Cheeger, J. A lower bound for smallest eigenvalue of Laplacian. In (1970), Princeton University Press, 195--199.Google Scholar
- Chierichetti, F., Lattanzi, S., Panconesi, A. Rumour spreading and graph conductance. In (2010), 1657--1663. Google ScholarDigital Library
- Christiano, P., Kelner, J.A., Madry, A., Spielman, D.A., Teng, S.H. Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In (2011), 273--282. Google ScholarDigital Library
- Chung, F.R.K. Spectral graph theory. CBMS Regional Conference Series in Mathematics, American Mathematical Society, 1997.Google Scholar
- de Carli Silva, M.K., Harvey, N.J.A., Sato, C.M. Sparse sums of positive semidefinite matrices. (2011), abs/1107.0088.Google Scholar
- Ding, J., Lee, J.R., Peres, Y. Cover times, blanket times, and majorizing measures. In (2011), 61--70. Google ScholarDigital Library
- Friedman, J. A Proof of Alon's Second Eigenvalue Conjecture and Related Problems. Number 910 in Memoirs of the American Mathematical Society. American Mathematical Society, 2008.Google Scholar
- Fung, W.S., Hariharan, R., Harvey, N.J.A., Panigrahi, D. A general framework for graph sparsification. In (2011), 71--80. Google ScholarDigital Library
- Golub, G.H., Van Loan, C.F. Matrix Computations, 2nd edn, Johns Hopkins University Press, 1989.Google Scholar
- Goyal, N., Rademacher, L., Vempala, S. Expanders via random spanning trees. In (2009), 576--585. Google ScholarDigital Library
- Kapralov, M., Panigrahy, R. Spectral sparsification via random spav nners. In (2012), 393--398. Google ScholarDigital Library
- Kolla, A., Makarychev, Y., Saberi, A., Teng, S.H. Subgraph sparsification and nearly optimal ultrasparsifiers. In (2010), 57--66. Google ScholarDigital Library
- Koutis, I., Levin, A., Peng, R. Improved spectral sparsification and numerical algorithms for SDD matrices. In (2012), 266--277.Google Scholar
- Koutis, I., Miller, G.L., Peng, R. A nearly-m log n time solver for SDD linear systems. In (2011), 590--598. Google ScholarDigital Library
- Leiserson, C. Fat-trees: universal networks for hardware-efficient supercomputing., 10 (0ctober1985), 892--901. Google ScholarDigital Library
- Lubotzky, A., Phillips, R., Sarnak, P. Ramanujan graphs., 3 (1988), 261--277.Google Scholar
- Margulis, G.A. Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators., 1 (July 1988), 39--46.Google Scholar
- Naor, A. Sparse quadratic forms and their geometric applications. (2011), 1033.Google Scholar
- Peleg, D., Ullman, J.D. An optimal synchronizer for the hypercube., 4 (1989), 740--747. Google ScholarDigital Library
- Rudelson, M. Random vectors in the isotropic position., 1 (1999), 60--72.Google Scholar
- Sinclair, A., Jerrum, M. Approximate counting, uniform generation and rapidly mixing Markov chains. 1 (July 1989), 93--133. Google ScholarDigital Library
- Spielman, D.A., Srivastava, N. Graph sparsification by effective resistances. 6 (2011), 1913--1926. Google ScholarDigital Library
- Spielman, D.A., Teng, S.H. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. (2008), abs/cs/0607105.Google Scholar
- Spielman, D.A., Teng, S.H. Spectral sparsification of graphs., 4 (2011), 981--1025. Google ScholarDigital Library
- Zhou, D., Huang, J., Scholkopf, B. Learning from labeled and unlabeled data on a directed graph. In (2005), 1041--1048.Google Scholar
- Zhu, X., Ghahramani, Z., Lafferty, J.D. Semi-supervised learning using Gaussian fields and harmonic functions. In (2003).Google Scholar
Index Terms
- Spectral sparsification of graphs: theory and algorithms
Recommendations
Spectral Sparsification of Graphs
We introduce a new notion of graph sparsification based on spectral similarity of graph Laplacians: spectral sparsification requires that the Laplacian quadratic form of the sparsifier approximate that of the original. This is equivalent to saying that ...
Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices
We study algorithms for spectral graph sparsification. The input is a graph G with n vertices and m edges, and the output is a sparse graph G˜ that approximates G in an algebraic sense. Concretely, for all vectors x and any ϵ > 0, the graph G˜ satisfies ...
Comments