We propose a new hierarchy of semidefinite programming relaxations for inference problems and demonstrate their application to regular stochastic block models.

A regular stochastic block model (RSBM) is a random graph model wherein the vertices are partitioned into $k$ communities, and a random regular graph is sampled conditioned on a prescribed number of edges between the communities. For example, if we sample a graph with no edges within communities, we obtain a model for sampling $k$-colorable graphs.  The Kesten-Stigum (KS) threshold is widely conjectured to mark a computational threshold for the problem of community detection for both RSBMs and general (irregular) SBMs.

In this work, we apply our hierarchy of SDP relaxations to RSBMs, and prove the following results:

1. For every $\epsilon$, there exists $m \in \N$ such that the $m^{th}$ level of the SDP hierarchy can detect communities in a dissortative RSBM which is $\epsilon$-above the KS threshold
2. The resulting SDP based algorithm is robust to $o(n)$-perturbations of the graph.
3. Below the KS threshold, no constant level of our hierarchy can solve the community detection in an RSBM.