  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.
