Abstract
We propose a new semidefinite programing hierarchy for statistical inference problems and illustrate its efficacy on the problem of community detection in block models, a model of random graphs where vertices are partitioned into $k$ communities, and a graph is sampled conditional on a prescribed number of inter- and intra-community edges. The detection problem, where we are to decide with high probability whether a graph was drawn from this model or from the Erdős-Renyi model, is conjectured to undergo a computational phase transition at a point called the Kesten-Stigum (KS) threshold. We prove that sufficiently large (but constant) levels of our hierarchy can perform detection arbitrarily close to the KS threshold, and further show that below this threshold every constant level fails. Our algorithm is additionally robust to a linear number of adversarial edge perturbations, unlike simple spectral detection algorithms using the adjacency or non-backtracking matrix.
In this two-part talk, we will introduce this hierarchy, sketch the analysis of its performance in the context of community detection, and present some interesting directions to pursue.