Semidefinite programs on sparse random graphs and their application to community detection

Denote by A the adjacency matrix of an Erdos-Renyi graph with bounded average degree. We consider the problem of maximizing 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. Informally, Erdos-Renyi graphs appear to behave similarly to random regular graphs for semidefinite programming. We next consider the sparse, two-groups, symmetric community detection problem (also known as planted partition). We establish that SDP achieves the information-theoretically optimal detection threshold for large (bounded) degree. Namely, under this model, the vertex set is partitioned into subsets of size n/2, with edge probability a/n (within group) and b/n (across). We prove that SDP detects the partition with high probability provided (a-b)^2/(4d)> 1+o_d(1), with d= (a+b)/2. By comparison, the information theoretic threshold for detecting the hidden partition is (a-b)^2/(4d)> 1: SDP is nearly optimal for large bounded average degree. Our proof is based on tools from different research areas: (i) A new 'higher-rank' Grothendieck inequality for symmetric matrices; (ii) An interpolation method inspired from statistical physics; (iii) An analysis of the eigenvectors of deformed Gaussian random matrices.

Authors

• Andrea Montanari
• Subhabrata Sen

Keywords

• Community Detection
• Phase Transitions
• Semidefinite Programming Relaxation