Graph sparsification by effective resistances

ABSTRACT

We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph G=(V,E,w) and a parameter ε>0, we produce a weighted subgraph H=(V,~E,~w) of G such that |~E|=O(n log n/ε²) and for all vectors x in R^V. (1-ε) ∑uv ∈ E (x(u)-x(v))²w_uv≤ ∑uv in ~E(x(u)-x(v))²~w_uv ≤ (1+ε)∑uv ∈ E(x(u)-x(v))²w_uv. This improves upon the sparsifiers constructed by Spielman and Teng, which had O(n log^c n) edges for some large constant c, and upon those of Benczur and Karger, which only satisfied (1) for x in {0,1}^V. We conjecture the existence of sparsifiers with O(n) edges, noting that these would generalize the notion of expander graphs, which are constant-degree sparsifiers for the complete graph. A key ingredient in our algorithm is a subroutine of independent interest: a nearly-linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in O(log n) time.

REFERENCES

• 1: Dimitris Achlioptas, Database-friendly random projections, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.274-281, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375608]
• 2: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 3: S. Arora, E. Hazan, and S. Kale. A fast random sampling algorithm for sparsifying matrices. In APPROX-RANDOM '06, volume 4110 of Lecture Notes in Computer Science, pages 272--279. Springer, 2006.
• 4: András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237827]
• 5: B. Bollobas. Modern Graph Theory. Springer, July 1998.
• 6: A. K. Chandra , P. Raghavan , W. L. Ruzzo , R. Smolensky, The electrical resistance of a graph captures its commute and cover times, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.574-586, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73062]
• 7: F. R. K. Chung. Spectral Graph Theory. CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997.
• 8: P. Doyle and J. Snell. Random walks and electric networks. Math. Assoc. America., Washington, 1984.
• 9: P. Drineas , R. Kannan, Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.452, October 14-17, 2001
• 10: Petros Drineas , Ravi Kannan, Pass efficient algorithms for approximating large matrices, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 11: Aykut Firat , Sangit Chatterjee , Mustafa Yilmaz, Genetic clustering of social networks using random walks, Computational Statistics & Data Analysis, v.51 n.12, p.6285-6294, August, 2007 [doi>10.1016/j.csda.2007.01.010]
• 12: Francois Fouss , Alain Pirotte , Jean-Michel Renders , Marco Saerens, Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation, IEEE Transactions on Knowledge and Data Engineering, v.19 n.3, p.355-369, March 2007 [doi>10.1109/TKDE.2007.46]
• 13: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast monte-carlo algorithms for finding low-rank approximations, Journal of the ACM (JACM), v.51 n.6, p.1025-1041, November 2004 [doi>10.1145/1039488.1039494]
• 14: C. Godsil and G. Royle. Algebraic Graph Theory. Graduate Texts in Mathematics. Springer-Verlag, 2001.
• 15: A V Goldberg , R E Tarjan, A new approach to the maximum flow problem, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.136-146, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12144]
• 16: Stephen Guattery , Gary L. Miller, Graph Embeddings and Laplacian Eigenvalues, SIAM Journal on Matrix Analysis and Applications, v.21 n.3, p.703-723, Feb.-March 2000 [doi>10.1137/S0895479897329825]
• 17: W. Johnson and J. Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemp. Math., 26:189--206, 1984.
• 18: J. Kelner. Lecture notes for 18.409, an algorithmist's toolkit. 2007.
• 19: Rohit Khandekar , Satish Rao , Umesh Vazirani, Graph partitioning using single commodity flows, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132574]
• 20: G. Lugosi. Concentration-of-measure inequalities, 2003. Available at http://www.econ.upf.edu/ lugosi/anu.ps.
• 21: M. Rudelson. Random vectors in the isotropic position. J. of Functional Analysis, 163(1):60--72, 1999.
• 22: Mark Rudelson , Roman Vershynin, Sampling from large matrices: An approach through geometric functional analysis, Journal of the ACM (JACM), v.54 n.4, p.21-es, July 2007 [doi>10.1145/1255443.1255449]
• 23: Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007372]
• 24: D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. Available at http://www.arxiv.org/abs/cs.NA/0607105, 2006.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
electrical flows, random sampling, spectral graph theory