Document Open Access Logo

The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime

Authors Jess Banks, Robert Kleinberg, Cristopher Moore

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.28.pdf
  • Filesize: 0.53 MB
  • 22 pages

Document Identifiers

Author Details

Jess Banks
Robert Kleinberg
Cristopher Moore

Cite As Get BibTex

Jess Banks, Robert Kleinberg, and Cristopher Moore. The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 28:1-28:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.28

Abstract

We derive upper and lower bounds on the degree d for which the Lovasz theta function, or equivalently sum-of-squares proofs with degree two, can refute the existence of a k-coloring in random regular graphs G(n,d). We show that this type of refutation fails well above the k-colorability transition, and in particular everywhere below the Kesten-Stigum threshold. This is consistent with the conjecture that refuting k-colorability, or distinguishing G(n,d) from the planted coloring model, is hard in this region. Our results also apply to the disassortative case of the stochastic block model, adding evidence to the conjecture that there is a regime where community detection is computationally hard even though it is information-theoretically possible. Using orthogonal polynomials, we also provide explicit upper bounds on the theta function for regular graphs of a given girth, which may be of independent interest.

Subject Classification

Keywords
  • Lovász Theta Function
  • Random Regular Graphs
  • Sum of Squares
  • Orthogonal Polynomials

Metrics

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

References

  1. E. Abbe, A. S. Bandeira, and G. Hall. Exact recovery in the stochastic block model. IEEE Transactions on Information Theory, 62(1):471-487, 2016. Google Scholar
  2. Emmanuel Abbe. Community detection and stochastic block models: recent developments. J. Machine Learning Research, 2017. to appear. Google Scholar
  3. Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In Proc. 56th Annual Symposium on Foundations of Computer Science, FOCS, pages 670-688, 2015. Google Scholar
  4. 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. ArXiv preprints, 1512.09080, 2015. URL: http://arxiv.org/abs/1512.09080.
  5. Emmanuel Abbe and Colin Sandon. Achieving the KS threshold in the general stochastic block model with linearized acyclic belief propagation. In Proc. Neural Information Processing Systems (NIPS), pages 1334-1342, 2016. URL: http://papers.nips.cc/paper/6365-achieving-the-ks-threshold-in-the-general-stochastic-block-model-with-linearized-acyclic-belief-propagation.
  6. Emmanuel Abbe and Colin Sandon. Crossing the KS threshold in the stochastic block model with information theory. In IEEE Intl. Symp. on Information Theory, ISIT, pages 840-844, 2016. URL: http://dx.doi.org/10.1109/ISIT.2016.7541417.
  7. Dimitris Achlioptas and Cristopher Moore. The chromatic number of random regular graphs. In Proc. 8th International Workshop on Randomization and Computation (RANDOM), pages 219-228, 2004. Google Scholar
  8. Dimitris Achlioptas and Assaf Naor. The two possible values of the chromatic number of a random graph. Ann. Math., 162:1335-1351, 2005. Google Scholar
  9. Naman Agarwal, Afonso S. Bandeira, Konstantinos Koiliaris, and Alexandra Kolla. Multisection in the stochastic block model using semidefinite programming. ArXiv preprints, 1507.02323, 2015. URL: http://arxiv.org/abs/1507.02323.
  10. Sarah R. Allen, Ryan O'Donnell, and David Witmer. How to refute a random CSP. In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 689-708, 2015. Google Scholar
  11. Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin. Non-backtracking random walks mix faster. Communications in Contemporary Mathematics, 9(04):585-603, 2007. Google Scholar
  12. Jess Banks, Cristopher Moore, Joe Neeman, and Praneeth Netrapalli. Information-theoretic thresholds for community detection in sparse networks. In Proc. 29th Conference on Learning Theory, COLT, pages 383-416, 2016. URL: http://jmlr.org/proceedings/papers/v49/banks16.html.
  13. Boaz Barak, Samuel B. Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. In Proc. 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 428-437, 2016. Google Scholar
  14. Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. Electronic Colloquium on Computational Complexity (ECCC), 21:59, 2014. URL: https://eccc.weizmann.ac.il/report/2014/059/.
  15. P. Barucca. Spectral partitioning in random regular blockmodels. ArXiv e-prints, 1610.02668, 2016. URL: https://arxiv.org/abs/1610.02668.
  16. Peter J. Bickel and Aiyou Chen. A nonparametric view of network models and Newman-Girvan and other modularities. Proc. Natl. Acad. Sci. USA, 106:21068-21073, 2009. Google Scholar
  17. Charles Bordenave, Marc Lelarge, and Laurent Massoulié. Non-backtracking spectrum of random graphs: Community detection and non-regular Ramanujan graphs. In Proc. 56th Annual Symposium on Foundations of Computer Science, FOCS, pages 1347-1357, 2015. Google Scholar
  18. Gerandy Brito, Ioana Dumitriu, Shirshendu Ganguly, Christopher Hoffman, and Linh V. Tran. Recovery and rigidity in a regular stochastic block model. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1589-1601, 2016. Google Scholar
  19. A. Coja-Oghlan, C. Efthymiou, N. Jaafari, M. Kang, and T. Kapetanopoulos. Charting the replica symmetric phase. ArXiv preprints, 1704.01043, 2017. URL: https://arxiv.org/abs/1704.01043.
  20. Amin Coja-Oghlan. The Lovász number of random graphs. In 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 228-239, 2003. Google Scholar
  21. Amin Coja-Oghlan, Charilaos Efthymiou, and Samuel Hetterich. On the chromatic number of random regular graphs. J. Comb. Theory, Ser. B, 116:367-439, 2016. Google Scholar
  22. Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborová. Information-theoretic thresholds from the cavity method. Proc. 49th Annual ACM on Symposium on Theory of Computing, STOC, 2017. URL: http://arxiv.org/abs/1611.00814.
  23. Amin Coja-Oghlan, Elchanan Mossel, and Dan Vilenchik. A spectral approach to analysing belief propagation for 3-colouring. Combinatorics, Probability and Computing, 18(6):881-912, 2009. Google Scholar
  24. Amin Coja-Oghlan and Dan Vilenchik. Chasing the K-colorability threshold. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 380-389, 2013. Google Scholar
  25. Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E, 84:066106, 2011. URL: http://dx.doi.org/10.1103/PhysRevE.84.066106.
  26. Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Inference and phase transitions in the detection of modules in sparse networks. Phys. Rev. Lett., 107:065701, 2011. URL: http://dx.doi.org/10.1103/PhysRevLett.107.065701.
  27. Yash Deshpande and Andrea Montanari. Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. In Proc. 28th Conference on Learning Theory, COLT, pages 523-562, 2015. Google Scholar
  28. Paul Erdős. Some remarks on the theory of graphs. Bulletin of the American Mathematical Society, 53(4):292-294, 1947. Google Scholar
  29. Joel Friedman. A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems. American Mathematical Society, 2008. Google Scholar
  30. B. Hajek, Y. Wu, and J. Xu. Achieving exact cluster recovery threshold via semidefinite programming. IEEE Transactions on Information Theory, 62(5):2788-2797, 2016. Google Scholar
  31. B. Hajek, Y. Wu, and J. Xu. Achieving exact cluster recovery threshold via semidefinite programming: Extensions. IEEE Trans. on Information Theory, 62(10):5918-5937, 2016. Google Scholar
  32. Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, and Tselil Schramm. On the integrality gap of degree-4 sum of squares for planted clique. In Proc. of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1079-1095, 2016. Google Scholar
  33. Graeme Kemkes, Xavier Pérez-Giménez, and Nicholas Wormald. On the chromatic number of random d-regular graphs. Advances in Mathematics, 223(1):300-328, 2010. Google Scholar
  34. H. Kesten and B. P. Stigum. Additional limit theorems for indecomposable multidimensional Galton-Watson processes. Ann. Math. Stat., 37:1463-1481, 1966. Google Scholar
  35. H. Kesten and B. P. Stigum. Limit theorems for decomposable multi-dimensional Galton-Watson processes. J. Math. Anal. Appl., 17:309, 1966. Google Scholar
  36. Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Proc. 49th Annual ACM Symposium on Theory of Computing, STOC, 2017. Google Scholar
  37. J. L. Krivine. Anneaux préordonnés. Journal d'Analyse Mathématique, 12(1):307-326, 1964. Google Scholar
  38. F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang. Spectral redemption in clustering sparse networks. Proc. Natl. Acad. Sci. USA, 110(52):20935-20940, 2013. URL: http://dx.doi.org/10.1073/pnas.1312486110.
  39. Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci. USA, 104(25):10318-10323, 2007. URL: http://dx.doi.org/10.1073/pnas.0703685104.
  40. Florent Krzakala and Lenka Zdeborová. Hiding quiet solutions in random constraint satisfaction problems. Phys. Rev. Lett., 102:238701, 2009. Google Scholar
  41. Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3):796-817, 2001. Google Scholar
  42. Tomasz Łuczak. A note on the sharp concentration of the chromatic number of random graphs. Combinatorica, 11(3):295-297, 1991. Google Scholar
  43. Laurent Massoulié. Community detection thresholds and the weak Ramanujan property. In Proc. 46th Annual ACM Symposium on Theory of Computing (STOC), pages 694-703, 2014. Google Scholar
  44. Brendan D. McKay. The expected eigenvalue distribution of a random labelled regular graph. Linear Algebra and its Applications, 40:203-216, 1981. Google Scholar
  45. Raghu Meka, Aaron Potechin, and Avi Wigderson. Sum-of-squares lower bounds for planted clique. In Proc. 47th Annual ACM on Symposium on Theory of Computing (STOC), pages 87-96, 2015. Google Scholar
  46. M. Molloy and B. A. Reed. The chromatic number of sparse random graphs, 1992. Masters thesis, University of Waterloo. Google Scholar
  47. Cristopher Moore. The computer science and physics of community detection: Landscapes, phase transitions, and hardness. Bulletin of the EATCS, 121:25-61, 2017. Google Scholar
  48. Elchanan Mossel, Joe Neeman, and Allan Sly. A proof of the block model threshold conjecture. ArXiv preprints, 1311.4115, 2013. URL: http://arxiv.org/abs/1311.4115.
  49. Elchanan Mossel, Joe Neeman, and Allan Sly. Belief propagation, robust reconstruction and optimal recovery of block models. In Proc. 27th Conference on Learning Theory, COLT, pages 356-370, 2014. URL: http://jmlr.org/proceedings/papers/v35/mossel14.html.
  50. Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency thresholds for the planted bisection model. In Proc. Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pages 69-75, 2015. URL: http://dx.doi.org/10.1145/2746539.2746603.
  51. Elchanan Mossel, Joe Neeman, and Allan Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162(3-4):431-461, 2015. Google Scholar
  52. Yurii Nesterov. Squared functional systems and optimization problems. High Performance Optimization, 33:405-440, 2000. Google Scholar
  53. M. E. J. Newman and Travis Martin. Equitable random graphs. Phys. Rev. E, 90:052824, 2014. Google Scholar
  54. Pablo A. Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, 2000. Google Scholar
  55. Grant Schoenebeck. Linear level Lasserre lower bounds for certain k-CSPs. In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 593-602, 2008. Google Scholar
  56. N. Z. Shor. An approach to obtaining global extremums in polynomial mathematical programming problems. Cybernetics, 23(5):695-700, 1987. Google Scholar
  57. Gilbert Stengle. A nullstellensatz and a positivstellensatz in semialgebraic geometry. Mathematische Annalen, 207(2):87-97, 1974. Google Scholar
  58. Gabor Szegő. Orthogonal Polynomials. American Mathematical Society, 1939. Google Scholar
  59. N. Wormald. Models of random regular graphs. In Surveys in Combinatorics, pages 239-298. Cambridge University Press, 1999. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact