2015

Semidefinite Programs on Sparse Random Graphs and their Application to Community Detection

Montanari, Andrea, Sen, Subhabrata

Understand

Denote by $A$ the adjacency matrix of an Erdos-Renyi graph with bounded average degree.

We consider the problem of maximizing $\langle A-E\{A\},X\rangle$ over the set of positive semidefinite matrices $X$ with diagonal entries $X_{ii}=1$.
We prove that for large (bounded) average degree $d$, the value of this semidefinite program (SDP) is --with high probability-- $2n\sqrt{d} + n\, o(\sqrt{d})+o(n)$.
For a random regular graph of degree $d$, we prove that the SDP value is $2n\sqrt{d-1}+o(n)$, matching a spectral upper bound.

Built on

Jarl Waldemar Lindeberg, Eine neue herleitung des exponentialgesetzes in der wahrscheinlichkeitsrechnung , Mathematische Zeitschrift 15
1922
Earlier work this paper cites.
Ronald E Rietz, A proof of the Grothendieck inequality , Israel Journal of Mathematics 19
1974
Earlier work this paper cites.
P. W. Holland, K. Laskey, and S. Leinhardt, Stochastic blockmodels: First steps , Social Networks 5
1983
Earlier work this paper cites.
Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming , Journal of the ACM (JACM) 42
1995
Earlier work this paper cites.
Alexander Grothendieck, Résumé de la théorie métrique des produits tensoriels topologiques , Resenhas do Instituto de Matemática e Estatística da Universidade de São Paulo 2
1996
Earlier work this paper cites.
Noga Alon, Michael Krivelevich, and Benny Sudakov, Finding a large hidden clique in a random graph , Random Structures and Algorithms 13
1998
Earlier work this paper cites.
Arkadi Nemirovski, Cornelis Roos, and Tamás Terlaky, On maximization of quadratic form over intersection of ellipsoids with common center , Mathematical Programming 86
1999
Earlier work this paper cites.
Svante Janson, Tomasz Luczak, and Andrzej Rucinski, Random graphs , John Wiley and Sons., 2000
2000
Earlier work this paper cites.
Dima Grigoriev, Linear lower bound on degrees of positivstellensatz calculus proofs for the parity , Theoretical Computer Science 259
2001
Earlier work this paper cites.
Frank McSherry, Spectral partitioning of random graphs , Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, IEEE, 2001, pp. 529–537
2001
Earlier work this paper cites.
Alexandre Megretski, Relaxations of quadratic programs in operator theory and system analysis , Systems, approximation, singular integral operators, and related topics, Springer, 2001, pp. 365–392
2001
Earlier work this paper cites.
Andrew Y Ng, Michael I Jordan, Yair Weiss, et al., On spectral clustering: Analysis and an algorithm , Advances in neural information processing systems 2
2002
Earlier work this paper cites.
Amin Coja-Oghlan, The Lovász number of random graphs , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer, 2003, pp. 228–239
2003
Earlier work this paper cites.
Silvio Franz and Michele Leone, Replica bounds for optimization problems and diluted spin systems , J. Stat. Phys. 111
2003
Earlier work this paper cites.
Silvio Franz, Michele Leone, and Fabio L. Toninelli, Replica bounds for diluted non-poissonian spin systems , J. Phys. A 36
2003
Earlier work this paper cites.
Joel Friedman, A proof of alon’s second eigenvalue conjecture , Proc. of the 35th Symp. on Theory of Computing, San Diego, 2003, pp. 720–724
2003
Earlier work this paper cites.
Michael Krivelevich and Benny Sudakov, The largest eigenvalue of sparse random graphs , Combinatorics, Probability and Computing 12
2003
Earlier work this paper cites.
Francesco Guerra and Fabio L. Toninelli, The high temperature region of the Viana-Bray diluted spin glass models , J. Stat. Phys 115
2004
Earlier work this paper cites.
Dmitry Panchenko and Michel Talagrand, Bounds for diluted mean-fields spin glass models , Probability Theory and Related Fields 130
2004
Earlier work this paper cites.

Similar

Jinho Baik, Gérard Ben Arous, and Sandrine Péché, Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices , Annals of Probability (2005), 1643–1697
2005
Cited alongside, same era.
Sourav Chatterjee, A simple invariance theorem , arXiv math/0508213
2005
Cited alongside, same era.
Uriel Feige and Eran Ofek, Spectral techniques applied to sparse random graphs , Random Structures & Algorithms 27
2005
Cited alongside, same era.
Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor, Quadratic forms on graphs , Inventiones mathematicae 163
2006
Cited alongside, same era.
Delphine Féral and Sandrine Péché, The largest eigenvalue of rank one deformation of large wigner matrices , Communications in mathematical physics 272
2007
Cited alongside, same era.
Grant Schoenebeck, Linear level Lasserre lower bounds for certain k-CSPs , Foundations of Computer Science, 2008. FOCS’08. IEEE 49th Annual IEEE Symposium on, IEEE, 2008, pp. 593–602
2008
Cited alongside, same era.
Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni, An introduction to random matrices , Cambridge studies in advanced mathematics., Cambridge University Press, 2009
2009
Cited alongside, same era.
Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin, The positive semidefinite grothendieck problem with rank constraint , Automata, Languages and Programming, Springer, 2010, pp. 31–42
2010
Cited alongside, same era.
Briët, Jop and de Oliveira Filho, Fernando Mário and Vallentin, Frank, Grothendieck inequalities for semidefinite programs with rank constraint , arXiv:1011.1754
Original
2010
Cited alongside, same era.
Amir Dembo, Andrea Montanari, et al., Gibbs measures and phase transitions on sparse random graphs , Brazilian Journal of Probability and Statistics 24
2010
Cited alongside, same era.
Mireille Capitaine, Catherine Donati-Martin, Delphine Féral, Maxime Février, et al., Free convolution with a semicircular distribution and eigenvalues of spiked deformations of wigner matrices , Electron. J. Probab 16
2011
Cited alongside, same era.
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications , Physical Review E 84
2011
Cited alongside, same era.

Then

Alex Bloemendal and Bálint Virág, Limits of spiked random matrices i , Probability Theory and Related Fields 156
2013
Later among the works it cites.
Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang, Spectral redemption in clustering sparse networks , Proceedings of the National Academy of Sciences 110
2013
Later among the works it cites.
Antti Knowles and Jun Yin, The isotropic semicircle law and deformation of wigner matrices , Communications on Pure and Applied Mathematics (2013)
2013
Later among the works it cites.
Elchanan Mossel, Joe Neeman, and Allan Sly, A proof of the block model threshold conjecture , arXiv:1311.4115
Original
2013
Later among the works it cites.
Alessandro Pizzo, David Renfrew, and Alexander Soshnikov, On finite rank deformations of wigner matrices , Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 49
2013
Later among the works it cites.
Emmanuel Abbe, Afonso S. Bandeira, and Georgina Hall, Exact recovery in the stochastic block model , arXiv:1405.3267
Original
2014
Later among the works it cites.
Afonso S Bandeira, Moses Charikar, Amit Singer, and Andy Zhu, Multireference alignment using semidefinite programming , Proceedings of the 5th conference on Innovations in theoretical computer science, ACM, 2014, pp. 459–470
2014
Later among the works it cites.
Yudong Chen and Jiaming Xu, Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices , arXiv:1402.1267
Original
2014
Later among the works it cites.
Olivier Guédon and Roman Vershynin, Community detection in sparse networks via grothendieck’s inequality , arXiv:1411.4686
Original
2014
Later among the works it cites.
Bruce Hajek, Yihong Wu, and Jiaming Xu, Achieving exact cluster recovery threshold via semidefinite programming , arXiv:1412.6156
Original
2014
Later among the works it cites.
Laurent Massoulié, Community detection thresholds and the weak Ramanujan property , Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, 2014, pp. 694–703
2014
Later among the works it cites.
Pranjal Awasthi, Afonso S Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, and Rachel Ward, Relax, no need to round: Integrality of clustering formulations , Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ACM, 2015, pp. 191–200
2015
Closest in time.
Emmanuel Abbe and Colin Sandon, Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms , Foundations of Computer Science (FOCS), 2015 IEEE 55th Annual Symposium on, 2015
2015
Closest in time.
Charles Bordenave, Marc Lelarge, and Laurent Massoulié, Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs , Foundations of Computer Science (FOCS), 2015 IEEE 55th Annual Symposium on, 2015
2015
Closest in time.
Endre Csóka, Balázs Gerencsér, Viktor Harangi, and Bálint Virág, Invariant gaussian processes and independent sets on regular graphs of large girth , Random Structures & Algorithms 47
2015
Closest in time.
Peter Chin, Anup Rao, and Van Vu, Stochastic block model and community detection in the sparse graphs: A spectral algorithm with optimal rate of recovery , arXiv:1501.05021
Original
2015
Closest in time.
Amir Dembo, Andrea Montanari, and Subhabrata Sen, Extremal cuts of sparse random graphs , arXiv:1503.03923
Original
2015
Closest in time.
Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi, Phase transitions in semidefinite relaxations , In preparation, 2015
2015
Closest in time.
Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh, Matrix completion from noisy entries , Journal of Machine Learning Research 11
2078
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…