On semidefinite relaxations for the block model
  The stochastic block model (SBM) is a popular tool for community detection in
networks, but fitting it by maximum likelihood (MLE) involves a computationally
infeasible optimization problem. We propose a new semidefinite programming
(SDP) solution to the problem of fitting the SBM, derived as a relaxation of
the MLE. We put ours and previously proposed SDPs in a unified framework, as
relaxations of the MLE over various sub-classes of the SBM, revealing a
connection to sparse PCA. Our main relaxation, which we call SDP-1, is tighter
than other recently proposed SDP relaxations, and thus previously established
theoretical guarantees carry over. However, we show that SDP-1 exactly recovers
true communities over a wider class of SBMs than those covered by current
results. In particular, the assumption of strong assortativity of the SBM,
implicit in consistency conditions for previously proposed SDPs, can be relaxed
to weak assortativity for our approach, thus significantly broadening the class
of SBMs covered by the consistency results. We also show that strong
assortativity is indeed a necessary condition for exact recovery for previously
proposed SDP approaches and not an artifact of the proofs. Our analysis of SDPs
is based on primal-dual witness constructions, which provides some insight into
the nature of the solutions of various SDPs. We show how to combine features
from SDP-1 and already available SDPs to achieve the most flexibility in terms
of both assortativity and block-size constraints, as our relaxation has the
tendency to produce communities of similar sizes. This tendency makes it the
ideal tool for fitting network histograms, a method gaining popularity in the
graphon estimation literature, as we illustrate on an example of a social
networks of dolphins. We also provide empirical evidence that SDPs outperform
spectral methods for fitting SBMs with a large number of blocks.
