NeurIPS 2020

Near-Optimal Comparison Based Clustering

Meta Review

The paper shows how using only O(n\ln^2{n}) triplet queries (point i is more similar to j than k), it is possible to recover the exact clusters of a planted model. While the technique of using SDP for recovering planted clusters is not new, overall, the adaptation to handle comparison queries is quite nontrivial. The paper also provides empirical results on real and synthetic data.