Graph Clustering using Effective Resistance

Authors Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis Gharan



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.41.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Vedat Levi Alev
Nima Anari
Lap Chi Lau
Shayan Oveis Gharan

Cite AsGet BibTex

Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph Clustering using Effective Resistance. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ITCS.2018.41

Abstract

We design a polynomial time algorithm that for any weighted undirected graph G = (V, E, w) and sufficiently large \delta > 1, partitions V into subsets V(1),..., V(h) for some h>= 1, such that at most \delta^{-1} fraction of the weights are between clusters, i.e. sum(i < j) |E(V(i), V(j)| < w(E)/\delta and the effective resistance diameter of each of the induced subgraphs G[V(i)] is at most \delta^3 times the inverse of the average weighted degree, i.e. max{ Reff(u, v) : u, v \in V(i)} < \delta^3 · |V|/w(E) for all i = 1,..., h. In particular, it is possible to remove one percent of weight of edges of any given graph such that each of the resulting connected components has effective resistance diameter at most the inverse of the average weighted degree. Our proof is based on a new connection between effective resistance and low conductance sets. We show that if the effective resistance between two vertices u and v is large, then there must be a low conductance cut separating u from v. This implies that very mildly expanding graphs have constant effective resistance diameter. We believe that this connection could be of independent interest in algorithm design.
Keywords
  • Electrical Flows
  • Effective Resistance
  • Conductance
  • Graph Partitioning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. In 46th Annual Symposium on Theory of Computing, pages 79-88, 2014. Google Scholar
  2. David Aldous. The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discrete Math., 3(4):450-465, 1990. Google Scholar
  3. Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph clustering using effective resistance. ArXiv e-prints, 2017. URL: http://arxiv.org/abs/1711.06530.
  4. Vedat Levi Alev and Lap Chi Lau. Approximating unique games using low diameter graph decomposition. In APPROX/RANDOM 2017, pages 18:1-18:15, 2017. Google Scholar
  5. Noga Alon and V. D. Milman. lambda_1, isoperimetric inequalities for graphs, and superconcentrators. J. Comb. Theory, Ser. B, 38(1):73-88, 1985. Google Scholar
  6. Nima Anari and Shayan Oveis Gharan. Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP. In 56th Annual Symposium on Foundations of Computer Science, pages 20-39, 2015. Google Scholar
  7. Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. In 51th Annual Symposium on Foundations of Computer Science, pages 563-572, 2010. Google Scholar
  8. Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. Unique games on expanding constraint graphs are easy. In 40th Annual Symposium on Theory of Computing, pages 21-28, 2008. Google Scholar
  9. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, and Roy Schwartz. Min-max graph partitioning and small set expansion. In 52nd Annual Symposium on the Theory of Computation, pages 17-26. IEEE, 2011. Google Scholar
  10. Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In 52nd Annual Symposium on Foundations of Computer Science, pages 472-481, 2011. Google Scholar
  11. Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, pages 184-193, 1996. Google Scholar
  12. Punyashloka Biswal, James R. Lee, and Satish Rao. Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. J. ACM, 57(3):13:1-13:23, 2010. Google Scholar
  13. Andrei Z. Broder. Generating random spanning trees. In 30th Annual Symposium on Foundations of Computer Science, pages 442-447, 1989. Google Scholar
  14. Andrei Z Broder and Anna R Karlin. Bounds on the cover time. Journal of Theoretical Probability, 2(1):101-120, 1989. Google Scholar
  15. Gruia Călinescu, Howard J. Karloff, and Yuval Rabani. Approximation algorithms for the 0-extension problem. In 12th Annual Symposium on Discrete Algorithms, pages 8-16, 2001. Google Scholar
  16. Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of a graph captures its commute and cover times. Computational Complexity, 6(4):312-340, 1997. Google Scholar
  17. Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed steiner problems. In 9th Annual Symposium on Discrete Algorithms, pages 192-200, 1998. Google Scholar
  18. Jeff Cheeger. A lower bound for the smallest eigenvalue of the laplacian. Problems in analysis, pages 195-199, 1970. Google Scholar
  19. Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In 43rd Symposium on Theory of Computing, pages 273-282, 2011. Google Scholar
  20. David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva. Sampling random spanning trees faster than matrix multiplication. In 49th Annual Symposium on Theory of Computing, pages 730-742, 2017. Google Scholar
  21. Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, and Kunal Talwar. An improved approximation algorithm for the 0-extension problem. In 14th Annual Symposium on Discrete Algorithms, pages 257-265, 2003. Google Scholar
  22. Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput., 38(2):629-657, 2008. Google Scholar
  23. Anupam Gupta and Kunal Talwar. Approximating unique games. In 17th AnnualSymposium on Discrete Algorithms, pages 99-106, 2006. Google Scholar
  24. Venkatesan Guruswami and Ali Kemal Sinop. Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives. In 52nd Annual Symposium on Foundations of Computer Science, pages 482-491, 2011. Google Scholar
  25. Ravi Kannan, Santosh Vempala, and Adrian Vetta. On clusterings: Good, bad and spectral. J. ACM, 51(3):497-515, 2004. URL: http://dx.doi.org/10.1145/990308.990313.
  26. Jonathan A. Kelner, James R. Lee, Gregory N. Price, and Shang-Hua Teng. Higher eigenvalues of graphs. In 50th Annual Symposium on Foundations of Computer Science, pages 735-744, 2009. Google Scholar
  27. Jonathan A. Kelner and Aleksander Madry. Faster generation of random spanning trees. In 50th Annual Symposium on Foundations of Computer Science, pages 13-21, 2009. Google Scholar
  28. Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In 45th Annual Symposium on Theory of Computing, pages 911-920, 2013. Google Scholar
  29. Gustav Kirchhoff. Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird. Annalen der Physik, 148(12):497-508, 1847. Google Scholar
  30. Douglas J Klein and Milan Randić. Resistance distance. Journal of mathematical chemistry, 12(1):81-95, 1993. Google Scholar
  31. Philip Klein, Serge A Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 682-690. ACM, 1993. Google Scholar
  32. Alexandra Kolla. Spectral algorithms for unique games. Computational Complexity, 20(2):177-206, 2011. Google Scholar
  33. Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD linear systems. In 51th Annual Symposium on Foundations of Computer Science, pages 235-244, 2010. Google Scholar
  34. Ioannis Koutis, Gary L. Miller, and Richard Peng. A nearly-m log n time solver for SDD linear systems. In 52nd Annual Symposium on Foundations of Computer Science, pages 590-598, 2011. Google Scholar
  35. Robert Krauthgamer and Tim Roughgarden. Metric clustering via consistent labeling. Theory of Computing, 7(1):49-74, 2011. Google Scholar
  36. Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians - fast, sparse, and simple. In 57th Annual Symposium on Foundations of Computer Science, pages 573-582, 2016. Google Scholar
  37. James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. J. ACM, 61(6):37:1-37:30, 2014. Google Scholar
  38. James R. Lee and Anastasios Sidiropoulos. Genus and the geometry of the cut graph. In 21st Annual Symposium on Discrete Algorithms, pages 193-201, 2010. Google Scholar
  39. Nathan Linial and Michael E. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. Google Scholar
  40. Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation of random spanning trees and the effective resistance metric. In 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2019-2036, 2015. Google Scholar
  41. Peter Matthews. Covering problems for brownian motion on spheres. The Annals of Probability, pages 189-199, 1988. Google Scholar
  42. Shayan Oveis Gharan and Luca Trevisan. Partitioning into expanders. In 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1256-1266, 2014. Google Scholar
  43. Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput., 40(6):1913-1926, 2011. Google Scholar
  44. Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM J. Comput., 40(4):981-1025, 2011. Google Scholar
  45. Daniel A. Spielman and Shang-Hua Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Analysis Applications, 35(3):835-885, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail