Exact Recovery Threshold in the Binary Censored Block Model

Abstract—Given a background graph with n vertices, the bi-nary censored block model assumes that vertices are partitioned into two clusters, and every edge is labeled independently at random with labels drawn from Bern(1 − ) if two endpoints are in the same cluster, or from Bern() otherwise, where ∈ [0, 1/2] is a fixed constant. For Erdős-Rényi graphs with edge probability p = a logn/n and fixed a, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold a( 1 − − √)2> 1 for exactly recovering the partition from the labeled graph with probability tending to one as n→∞. For random regular graphs with degree scaling as a logn, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold aD(Bern(1/2)‖Bern())> 1, where D denotes the Kullback-Leibler divergence. I