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:
- 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.
- 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.
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.
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