Document Open Access Logo

Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery

Authors Anand Louis, Rakesh Venkat

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.101.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Anand Louis
  • Indian Institute of Science, Bangalore, India
Rakesh Venkat
  • Hebrew University of Jerusalem, Israel

Funding

  • Venkat, Rakesh: Supported by an I-CORE Algorithms Fellowship

Cite As Get BibTex

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 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 101:1-101:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.101

Abstract

The problem of computing the vertex expansion of a graph is an NP-hard problem. The current best worst-case approximation guarantees for computing the vertex expansion of a graph are a O(sqrt{log n})-approximation algorithm due to Feige et al. [Uriel Feige et al., 2008], and O(sqrt{OPT log d}) bound in graphs having vertex degrees at most d due to Louis et al. [Louis et al., 2013].
We study a natural semi-random model of graphs with sparse vertex cuts. For certain ranges of parameters, we give an algorithm to recover the planted sparse vertex cut exactly. For a larger range of parameters, we give a constant factor bi-criteria approximation algorithm to compute the graph's balanced vertex expansion. Our algorithms are based on studying a semidefinite programming relaxation for the balanced vertex expansion of the graph.
In addition to being a family of instances that will help us to better understand the complexity of the computation of vertex expansion, our model can also be used in the study of community detection where only a few nodes from each community interact with nodes from other communities. There has been a lot of work on studying random and semi-random graphs with planted sparse edge cuts. To the best of our knowledge, our model of semi-random graphs with planted sparse vertex cuts has not been studied before.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Semi-Random models
  • Vertex Expansion
  • Approximation Algorithms
  • Beyond Worst Case Analysis

Metrics

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

Related Versions

References

  1. Emmanuel Abbe. Community detection and stochastic block models: recent developments. arXiv preprint arXiv:1703.10146, 2017. Google Scholar
  2. Emmanuel Abbe, Afonso S Bandeira, Annina Bracher, and Amit Singer. Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. IEEE Transactions on Network Science and Engineering, 1(1):10-22, 2014. Google Scholar
  3. 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
  4. 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
  5. 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
  6. Emmanuel Abbe and Colin Sandon. Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic bp, and the information-computation gap, 2017. arXiv: 1512.09080 To Appear in Communications on Pure and Applied Mathematics (2017). Google Scholar
  7. 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
  8. Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83-96, 1986. URL: http://dx.doi.org/10.1007/BF02579166,
  9. 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
  10. Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM, 56(2), 2009. (Preliminary version in 36th STOC, 2004). URL: http://dx.doi.org/10.1145/1502793.1502794.
  11. 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: http://dx.doi.org/10.1007/978-1-4613-0303-9_2,
  12. Sergey Bobkov, Christian Houdré, and Prasad Tetali. λ_∞, Vertex Isoperimetry and Concentration. Combinatorica, 20(2):153-172, 2000. Google Scholar
  13. 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: http://dx.doi.org/10.1109/SFCS.1987.22,
  14. 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: http://doi.acm.org/10.1145/3178123, URL: http://dx.doi.org/10.1145/3178123.
  15. Amin Coja-Oghlan. Colouring semirandom graphs. Combinatorics, Probability and Computing, 16(4):515–552, 2007. URL: http://dx.doi.org/10.1017/S0963548306007917.
  16. 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, http://arxiv.org/abs/https://doi.org/10.1137/05064299X, URL: http://dx.doi.org/10.1137/05064299X.
  17. Uriel Feige and Joe Kilian. Heuristics for semirandom graph problems. Journal of Computer and System Sciences, 63(4):639-671, 2001. Google Scholar
  18. 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
  19. Bruce Hajek, Yihong Wu, and Jiaming Xu. Achieving exact cluster recovery threshold via semidefinite programming: Extensions. IEEE Transactions on Information Theory, 62(10):5918-5937, 2016. Google Scholar
  20. Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983. Google Scholar
  21. Mark Jerrum and Gregory B Sorkin. The metropolis algorithm for graph bisection. Discrete Applied Mathematics, 82(1):155-175, 1998. Google Scholar
  22. 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: http://doi.acm.org/10.1145/224170.224229, URL: http://dx.doi.org/10.1145/224170.224229.
  23. 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: http://dx.doi.org/10.1137/S1064827595287997,
  24. Chiheon Kim, Afonso S. Bandeira, and Michel X. Goemans. Community detection in hypergraphs, spiked tensor models, and sum-of-squares. arXiv preprint: arXiv:1705.02973 [cs.DS], 2017. Google Scholar
  25. Victor Klee and George J Minty. How good is the simplex algorithm. In Shisha, Oved. Inequalities III (Proc. of 3rd Symp. on Inequalities, UCLA), pages 159-175. Academic Press, California, 1972. Google Scholar
  26. 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: http://doi.acm.org/10.1145/331524.331526, URL: http://dx.doi.org/10.1145/331524.331526.
  27. Anand Louis and Yury Makarychev. Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), volume 28 of Leibniz International Proceedings in Informatics (LIPIcs), pages 339-355, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.339.
  28. Anand Louis and Prasad Raghavendra, 2014. Personal Communication. Google Scholar
  29. 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: http://dx.doi.org/10.1109/FOCS.2013.46,
  30. 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: http://doi.acm.org/10.1145/2213977.2214013, URL: http://dx.doi.org/10.1145/2213977.2214013.
  31. 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: http://doi.acm.org/10.1145/2591796.2591841, URL: http://dx.doi.org/10.1145/2591796.2591841.
  32. 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 Jun 2016. PMLR. URL: http://proceedings.mlr.press/v49/makarychev16.html.
  33. 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: http://dx.doi.org/10.1145/2591796.2591857.
  34. 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.
  35. 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
  36. 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
  37. 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: http://doi.acm.org/10.1145/2746539.2746603, URL: http://dx.doi.org/10.1145/2746539.2746603.
  38. 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, URL: http://dx.doi.org/10.1007/s00493-016-3238-8.
  39. 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: http://doi.acm.org/10.1145/1806689.1806792, URL: http://dx.doi.org/10.1145/1806689.1806792.
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