Document Open Access Logo

A Schur Complement Cheeger Inequality

Author Aaron Schild

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.65.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Aaron Schild
  • University of California, Berkeley, CA, USA

Funding

  • Schild, Aaron: Supported by NSF grant CCF-1816861.

Cite As Get BibTex

Aaron Schild. A Schur Complement Cheeger Inequality. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 65:1-65:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.65

Abstract

Cheeger's inequality shows that any undirected graph G with minimum normalized Laplacian eigenvalue lambda_G has a cut with conductance at most O(sqrt{lambda_G}). Qualitatively, Cheeger's inequality says that if the mixing time of a graph is high, there is a cut that certifies this. However, this relationship is not tight, as some graphs (like cycles) do not have cuts with conductance o(sqrt{lambda_G}).
To better approximate the mixing time of a graph, we consider a more general object. Specifically, instead of bounding the mixing time with cuts, we bound it with cuts in graphs obtained by Schur complementing out vertices from the graph G. Combinatorially, these Schur complements describe random walks in G restricted to a subset of its vertices. As a result, all Schur complement cuts have conductance at least Omega(lambda_G). We show that unlike with cuts, this inequality is tight up to a constant factor. Specifically, there is a Schur complement cut with conductance at most O(lambda_G).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Spectra of graphs
Keywords
  • electrical networks
  • Cheeger's inequality
  • mixing time
  • conductance
  • Schur complements

Metrics

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

References

  1. 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, January 11-14, 2018, Cambridge, MA, USA, pages 41:1-41:16, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2018.41.
  2. N. Alon and V. D. Milman. λ₁, Isoperimetric Inequalities for Graphs, and Superconcentrators, 1985. Google Scholar
  3. Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83-96, 1986. Google Scholar
  4. Afonso S. Bandeira, Amit Singer, and Daniel A. Spielman. A Cheeger Inequality for the Graph Connection Laplacian. SIAM J. Matrix Analysis Applications, 34(4):1611-1630, 2013. Google Scholar
  5. 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
  6. Jeff Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. In Proceedings of the Princeton conference in honor of Professor S. Bochner, pages 195-199, 1969. Google Scholar
  7. Charles J. Colbourn, Robert P. J. Day, and Louis D. Nel. Unranking and Ranking Spanning Trees of a Graph. J. Algorithms, 10(2):271-286, 1989. Google Scholar
  8. Venkatesan Guruswami. Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey). CoRR, abs/1603.01512, 2016. Google Scholar
  9. Nabil Kahale. A semidefinite bound for mixing rates of Markov chains. In William H. Cunningham, S. Thomas McCormick, and Maurice Queyranne, editors, Integer Programming and Combinatorial Optimization, pages 190-203, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg. Google Scholar
  10. Jonathan A. Kelner, James R. Lee, Gregory N. Price, and Shang-Hua Teng. Metric uniformization and spectral bounds for graphs. CoRR, abs/1008.3594, 2010. Google Scholar
  11. Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan. Improved Cheeger’s Inequality: Analysis of Spectral Partitioning Algorithms Through Higher Order Spectral Gap. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC '13, pages 11-20, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2488608.2488611.
  12. Rasmus Kyng. Approximate Gaussian Elimination. PhD thesis, Yale University, 2017. Google Scholar
  13. James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multi-way Spectral Partitioning and Higher-order Cheeger Inequalities. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 1117-1130, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2213977.2214078.
  14. Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. Many Sparse Cuts via Higher Eigenvalues. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 1131-1140, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2213977.2214079.
  15. Ulrike Luxburg. A Tutorial on Spectral Clustering. Statistics and Computing, 17(4):395-416, December 2007. URL: http://dx.doi.org/10.1007/s11222-007-9033-z.
  16. Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast Generation of Random Spanning Trees and the Effective Resistance Metric. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 2019-2036, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.134.
  17. Marina Meila and Jianbo Shi. Learning Segmentation by Random Walks. In Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems (NIPS) 2000, Denver, CO, USA, pages 873-879, 2000. URL: http://papers.nips.cc/paper/1830-learning-segmentation-by-random-walks.
  18. Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888-905, August 2000. URL: http://dx.doi.org/10.1109/34.868688.
  19. Alistair Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing, 1:351-370, 1992. Google Scholar
  20. 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. URL: http://dx.doi.org/10.1137/090771430.
  21. John Steenbergen, Caroline Klivans, and Sayan Mukherjee. A Cheeger-type inequality on simplicial complexes. Advances in Applied Mathematics, 56:56-77, 2014. URL: http://dx.doi.org/10.1016/j.aam.2014.01.002.
  22. Luca Trevisan. Lecture 4 from cs359g: Graph partitioning and expanders, Stanford University. http://theory.stanford.edu/~trevisan/cs359g/lecture04.pdf, January 2011.
  23. Nisheeth K. Vishnoi. Lx = b. Foundations and Trends in Theoretical Computer Science, 8(1-2):1-141, 2013. URL: http://dx.doi.org/10.1561/0400000054.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact