Spectral detection in the censored block model

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Saade, Alaa, Lelarge, Marc, Krzakala, Florent, Zdeborova, Lenka
Format: Conference Proceeding
Language:English
Subjects:
Algorithms
Asymptotic properties
Belief propagation
Blocking
Communities
Eigenvalues and eigenfunctions
Glass
Image edge detection
Mathematical models
Optimization
Physics
Spectra
Stochastic processes
Symmetric matrices
Tasks
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2157-8095
2157-8117
DOI:10.1109/ISIT.2015.7282642