Talks
Fall 2020

# Local Statistics, Semidefinite Programming, and Community Detection II

Monday, Sep. 21, 2020 11:05 am11:30 am PDT

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.