# Clustering from Sparse Pairwise Measurements

arXiv: https://arxiv.org/abs/1601.06683 · HTML: https://mlsanity.com/paper/1601.06683/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2016.

## Built on by (most cited first, 2 of 2)

- [Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs](https://mlsanity.com/paper/2103.03561/) (2021)
- [Analysis of High-dimensional Gaussian Labeled-unlabeled Mixture Model via Message-passing Algorithm](https://mlsanity.com/paper/2411.19553/) (2024)

## Abstract (arXiv)

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.