Spectral Detection in the Censored Block Model
This provides an optimal solution for partial recovery in the censored block model, which is relevant for community detection and related tasks.
The paper tackles the problem of partially recovering hidden binary variables from censored edge weights, with applications in community detection and synchronization, by proposing two spectral algorithms based on non-backtracking and Bethe Hessian operators that achieve asymptotic optimality for detection.
We consider the problem of partially recovering hidden binary variables from the observation of (few) censored edge weights, a problem with applications in community detection, correlation clustering and synchronization. We describe two spectral algorithms for this task based on the non-backtracking and the Bethe Hessian operators. These algorithms are shown to be asymptotically optimal for the partial recovery problem, in that they detect the hidden assignment as soon as it is information theoretically possible to do so.