Given a background graph with n vertices, the binary 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 − e) if two endpoints are in the same cluster, or from Bern(e) otherwise, where e ∈ [0; 1/2] is a fixed constant. For Erdős-Renyi graphs with edge probability p = a log n/n and fixed a, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold equation 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 log n, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold aD(Bern(1/2)∥Bern(e)) > 1, where D denotes the Kullback-Leibler divergence.
['Bruce E. Hajek', 'Yihong Wu', 'Jiaming Xu']
Exact recovery threshold in the binary censored block model