Near-Optimal Comparison Based Clustering

Michaël Perrot, Pascal Mattia Esser, Debarghya Ghoshdastidar

Introduction

Traditional clustering typically relies on explicit similarity or distance metrics. However, in many subjective domains—such as human perception of style or taste—ordinal comparisons (e.g., "Is object $i$ more similar to $j$ than to $k$? ") are more reliable than absolute scores. This paper investigates the passive setting, where a fixed set of such comparisons is provided, and demonstrates that near-optimal clustering recovery is possible with significantly fewer samples than previously theorized.

Methodology

The authors introduce a two-step framework for clustering from passive comparisons:

  1. Additive Similarity Estimation (AddS-3 and AddS-4): Unlike traditional multiplicative kernels, the proposed AddS functions increment or decrement similarity based on triplet or quadruplet comparisons. This additive approach allows for single-pass computation, making it highly scalable for streaming data.
  2. SDP-based Clustering: The resulting similarity matrix is processed using a Semi-Definite Programming (SDP) solver. By employing an SDP-$\lambda$ formulation, the method can estimate clusters without prior knowledge of the total number of clusters ($k$).

To enhance practicality, the authors provide the SPUR algorithm, which automates the tuning of the penalty parameter $\lambda$ and the estimation of $k$.

Theoretical and Empirical Results

A key contribution of this work is closing the gap between active and passive learning. The authors prove that $\Omega(n \ln^2 n)$ passive comparisons are sufficient for exact recovery, nearly matching the theoretical lower bounds for active methods. This is a significant improvement over the $O(n^{3.5} \ln n)$ bounds found in prior literature.

Comparison of recovery performance (ARI) against the number of triplets ($|T|$) and quadruplets ($|Q|$). Additive similarity methods (AddS) achieve perfect recovery significantly earlier than multiplicative kernels (MulK).

Empirical validation on synthetic models and datasets like MNIST, car images, and food items confirms these theoretical gains. As shown in the figure above, the AddS methods reach an Adjusted Rand Index (ARI) of 1.0 (perfect recovery) with far fewer comparisons than the baseline MulK methods.

Noise Robustness

The framework is designed to handle both "crowd noise" (human error) and "intrinsic noise" (inherent ambiguity). The additive similarity functions demonstrate superior robustness to noise compared to multiplicative alternatives.

Performance of AddS-3 vs. MulK-3 under varying noise levels ($\epsilon$). AddS-3 maintains high accuracy even with higher noise compared to the baseline.

As illustrated, AddS-3 achieves perfect recovery at much higher noise levels (lower $\epsilon$) than MulK-3. This robustness ensures that the method remains effective even when human-provided comparisons are inconsistent.

Conclusion

By shifting from multiplicative kernels to additive similarity functions, this research proves that passive comparison-based clustering is far more efficient than previously believed. The proposed method achieves near-optimal sample complexity and robust performance on real-world datasets, offering a scalable solution for subjective data clustering.

Summary updated

Abstract

The goal of clustering is to group similar objects into meaningful partitions. This process is well understood when an explicit similarity measure between the objects is given. However, far less is known when this information is not readily available and, instead, one only observes ordinal comparisons such as "object i is more similar to j than to k." In this paper, we tackle this problem using a two-step procedure: we estimate a pairwise similarity matrix from the comparisons before using a clustering method based on semi-definite programming (SDP). We theoretically show that our approach can exactly recover a planted clustering using a near-optimal number of passive comparisons. We empirically validate our theoretical findings and demonstrate the good behaviour of our method on real data.
BibTeX
@inproceedings{perrot2020near,
  author = {Michaël Perrot and Pascal Mattia Esser and Debarghya Ghoshdastidar},
  title = {{Near-Optimal Comparison Based Clustering}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=5vfaf4i6zOk},
}
Figure