Clustering from Sparse Pairwise Measurements

Abstract

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.

References in corpus (5)

• Community Detection in the Labelled Stochastic Block Model
• Spectral Clustering of Graphs with the Bethe Hessian
• Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence
• Spectral Detection in the Censored Block Model
• Matrix Completion from Fewer Entries: Spectral Detectability and Rank Estimation

Cited by in corpus (5)

• Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
• Mixed Membership Graph Clustering via Systematic Edge Query
• Fast Randomized Semi-Supervised Clustering
• Robust Spectral Detection of Global Structures in the Data by Learning a Regularization
• Spectral Bounds for the Ising Ferromagnet on an Arbitrary Given Graph