Clustering from sparse pairwise measurements

We consider the problem of grouping items into clusters based on few random pairwise comparisons between the items. We introduce three closely related algorithms for this task: a belief propagation algorithm approximating the Bayes optimal solution, and two spectral algorithms based on the non-backt...

Full description

Saved in:
Bibliographic Details
Main Authors: Saade, Alaa, Krzakala, Florent, Lelarge, Marc, Zdeborova, Lenka
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Approximation
Approximation algorithms
Asymptotic properties
Belief propagation
Clustering algorithms
Clusters
Density measurement
Information theory
Jacobian matrices
Optimization
Spectra
Tasks
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of grouping items into clusters based on few random pairwise comparisons between the items. We introduce three closely related algorithms for this task: a belief propagation algorithm approximating the Bayes optimal solution, and two spectral algorithms based on the non-backtracking and Bethe Hessian operators. For the case of two symmetric clusters, we conjecture that these algorithms are asymptotically optimal in that they detect the clusters as soon as it is information theoretically possible to do so. We substantiate this claim for one of the spectral approaches we introduce.
ISSN:2157-8117
DOI:10.1109/ISIT.2016.7541405