  Semidefinite programs have recently been developed for the problem of
community detection, which may be viewed as a special case of the stochastic
blockmodel. Here, we develop a semidefinite program that can be tailored to
other instances of the blockmodel, such as non-assortative networks and
overlapping communities. We establish label recovery in sparse settings, with
conditions that are analogous to recent results for community detection. In
settings where the data is not generated by a blockmodel, we give an oracle
inequality that bounds excess risk relative to the best blockmodel
approximation. Simulations are presented for community detection, for
overlapping communities, and for latent space models.
