Document Open Access Logo

Planted Models for k-Way Edge and Vertex Expansion

Authors Anand Louis, Rakesh Venkat

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2019.23.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Semidefinite programming
  • Theory of computation → Graph algorithms analysis
Keywords
  • Vertex Expansion
  • k-way partitioning
  • Semi-Random models
  • Planted Models
  • Approximation Algorithms
  • Beyond Worst Case Analysis

Metrics

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

Abstract

Graph partitioning problems are a central topic of study in algorithms and complexity theory. Edge expansion and vertex expansion, two popular graph partitioning objectives, seek a 2-partition of the vertex set of the graph that minimizes the considered objective. However, for many natural applications, one might require a graph to be partitioned into k parts, for some k >=slant 2. For a k-partition S_1, ..., S_k of the vertex set of a graph G = (V,E), the k-way edge expansion (resp. vertex expansion) of {S_1, ..., S_k} is defined as max_{i in [k]} Phi(S_i), and the balanced k-way edge expansion (resp. vertex expansion) of G is defined as min_{{S_1, ..., S_k} in P_k} max_{i in [k]} Phi(S_i) , where P_k is the set of all balanced k-partitions of V (i.e each part of a k-partition in P_k should have cardinality |V|/k), and Phi(S) denotes the edge expansion (resp. vertex expansion) of S subset V. We study a natural planted model for graphs where the vertex set of a graph has a k-partition S_1, ..., S_k such that the graph induced on each S_i has large expansion, but each S_i has small edge expansion (resp. vertex expansion) in the graph. We give bi-criteria approximation algorithms for computing the balanced k-way edge expansion (resp. vertex expansion) of instances in this planted model.

Cite As Get BibTex

Anand Louis and Rakesh Venkat. Planted Models for k-Way Edge and Vertex Expansion. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.FSTTCS.2019.23

Author Details

Anand Louis
  • Indian Institute of Science, Bangalore, India
Rakesh Venkat
  • Indian Institute of Technology, Hyderabad, India

Funding

  • Louis, Anand: Supported in part by SERB Award ECR/2017/003296 and a Pratiksha Trust Young Investigator Award.

References

  1. Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall. Exact recovery in the stochastic block model. IEEE Transactions on Information Theory, 62(1):471-487, 2016. Google Scholar
  2. Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In IEEE 56th Annual Symp. on Foundations of Computer Science (FOCS), 2015, pages 670-688. IEEE, 2015. Google Scholar
  3. Emmanuel Abbe and Colin Sandon. Recovering communities in the general stochastic block model without knowing the parameters. In Advances in neural information processing systems, pages 676-684, 2015. Google Scholar
  4. Naman Agarwal, Afonso S Bandeira, Konstantinos Koiliaris, and Alexandra Kolla. Multisection in the stochastic block model using semidefinite programming. In Compressed Sensing and its Applications, pages 125-162. Springer, 2017. Google Scholar
  5. Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83-96, 1986. Google Scholar
  6. Noga Alon and Vitali D Milman. λ₁, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 38(1):73-88, 1985. Google Scholar
  7. Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2), 2009. (Preliminary version in 36th STOC, 2004). URL: https://doi.org/10.1145/1502793.1502794.
  8. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, and Roy Schwartz. Min-max graph partitioning and small set expansion. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 17-26. IEEE, 2011. Google Scholar
  9. Roberto Battiti and Marco Protasi. Approximate Algorithms and Heuristics for MAX-SAT. In Handbook of Combinatorial Optimization: Volume1-3, pages 77-148, Boston, MA, 1999. Springer US. URL: https://doi.org/10.1007/978-1-4613-0303-9_2.
  10. Sergey Bobkov, Christian Houdré, and Prasad Tetali. λ_∞, Vertex Isoperimetry and Concentration. Combinatorica, 20(2):153-172, 2000. Google Scholar
  11. Ravi B. Boppana. Eigenvalues and Graph Bisection: An Average-case Analysis. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, SFCS '87, pages 280-285, Washington, DC, USA, 1987. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.1987.22.
  12. T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang. Spectral Properties of Hypergraph Laplacian and Approximation Algorithms. J. ACM, 65(3):15:1-15:48, 2018. URL: https://doi.org/10.1145/3178123.
  13. Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM Journal on Computing, 38(2):629-657, 2008. URL: https://doi.org/10.1137/05064299X.
  14. Uriel Feige and Joe Kilian. Heuristics for semirandom graph problems. Journal of Computer and System Sciences, 63(4):639-671, 2001. Google Scholar
  15. Olivier Guédon and Roman Vershynin. Community detection in sparse networks via Grothendieck’s inequality. Probability Theory and Related Fields, 165(3-4):1025-1049, 2016. Google Scholar
  16. Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983. Google Scholar
  17. Mark Jerrum and Gregory B Sorkin. The Metropolis algorithm for graph bisection. Discrete Applied Mathematics, 82(1):155-175, 1998. Google Scholar
  18. George Karypis and Vipin Kumar. Analysis of Multilevel Graph Partitioning. In Proceedings of the 1995 ACM/IEEE Conference on Supercomputing, Supercomputing '95, New York, NY, USA, 1995. ACM. URL: https://doi.org/10.1145/224170.224229.
  19. George Karypis and Vipin Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM J. Sci. Comput., 20(1):359-392, December 1998. URL: https://doi.org/10.1137/S1064827595287997.
  20. 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: https://doi.org/10.1145/2488608.2488611.
  21. James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):37, 2014. Google Scholar
  22. Tom Leighton and Satish Rao. Multicommodity Max-flow Min-cut Theorems and Their Use in Designing Approximation Algorithms. J. ACM, 46(6):787-832, November 1999. URL: https://doi.org/10.1145/331524.331526.
  23. Anand Louis and Konstantin Makarychev. Approximation algorithm for sparsest k-partitioning. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1244-1255. SIAM, 2014. Google Scholar
  24. Anand Louis and Yury Makarychev. Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion. Theory of Computing, 12(1):1-25, 2016. URL: https://doi.org/10.4086/toc.2016.v012a017.
  25. Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. Algorithmic extensions of Cheeger’s inequality to higher eigenvalues and partitions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 315-326. Springer, 2011. Google Scholar
  26. 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, pages 1131-1140. ACM, 2012. Google Scholar
  27. Anand Louis, Prasad Raghavendra, and Santosh Vempala. The Complexity of Approximating Vertex Expansion. In Proc. of the 54th Annual Symp. on Foundations of Computer Science, FOCS '13, pages 360-369, Washington, DC, USA, 2013. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2013.46.
  28. Anand Louis and Rakesh Venkat. Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery. In 45th International Colloquium on Automata, Languages, and Programming (ICALP), pages 101:1-101:15, 2018. Full Version at: URL: https://arxiv.org/abs/1805.09747.
  29. Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Approximation Algorithms for Semi-random Partitioning Problems. In Proc. of the 44th Annual ACM Symp. on Theory of Computing, STOC '12, pages 367-384. ACM, 2012. URL: https://doi.org/10.1145/2213977.2214013.
  30. Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Constant Factor Approximation for Balanced Cut in the PIE Model. In Proc. of the 46th Annual ACM Symp. on Theory of Computing, STOC '14, pages 41-49, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2591796.2591841.
  31. Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Learning Communities in the Presence of Errors. In 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1258-1291, Columbia University, New York, New York, USA, 23-26 June 2016. PMLR. URL: http://proceedings.mlr.press/v49/makarychev16.html.
  32. Laurent Massoulié. Community Detection Thresholds and the Weak Ramanujan Property. In Proc. of the 46th Annual ACM Symp. on Theory of Computing, STOC '14, pages 694-703, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2591796.2591857.
  33. Frank D. McSherry. Spectral Partitioning of Random Graphs. In Proc. of the 42nd IEEE Symp. on Foundations of Computer Science (FOCS), pages 529-537, Washington, DC, USA, 2001. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=874063.875554.
  34. Ankur Moitra, William Perry, and Alexander S Wein. How robust are reconstruction thresholds for community detection? In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 828-841. ACM, 2016. Google Scholar
  35. Elchanan Mossel, Joe Neeman, and Allan Sly. Belief propagation, robust reconstruction and optimal recovery of block models. In Conference on Learning Theory, pages 356-370, 2014. Google Scholar
  36. Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency Thresholds for the Planted Bisection Model. In Proc. of the 47th Annual ACM Symp. on Theory of Computing, STOC '15, pages 69-75, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2746539.2746603.
  37. Elchanan Mossel, Joe Neeman, and Allan Sly. A proof of the block model threshold conjecture. Combinatorica, 2017. URL: https://doi.org/10.1007/s00493-016-3238-8.
  38. J Naor and Yuval Rabani. Tree Packing and Approximating fc-Cuts. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, volume 103, page 26. SIAM, 2001. Google Scholar
  39. R. Peng, H. Sun, and L. Zanetti. Partitioning Well-Clustered Graphs: Spectral Clustering Works! SIAM Journal on Computing, 46(2):710-743, 2017. URL: https://doi.org/10.1137/15M1047209.
  40. Prasad Raghavendra and David Steurer. Graph Expansion and the Unique Games Conjecture. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC '10, pages 755-764, New York, NY, USA, 2010. ACM. URL: https://doi.org/10.1145/1806689.1806792.
  41. Prasad Raghavendra, David Steurer, and Prasad Tetali. Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC '10, pages 631-640, New York, NY, USA, 2010. ACM. URL: https://doi.org/10.1145/1806689.1806776.
  42. R Ravi and Amitabh Sinha. Approximating k-cuts using network strength as a lagrangean relaxation. European Journal of Operational Research, 186(1):77-90, 2008. Google Scholar
  43. Huzur Saran and Vijay V Vazirani. Finding k cuts within twice the optimal. SIAM Journal on Computing, 24(1):101-108, 1995. 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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact