Near-Optimal Comparison Based Clustering

Michaël Perrot, Pascal Mattia Esser, Debarghya Ghoshdastidar

TL;DR

Researchers have developed a new method for clustering objects using only "ordinal comparisons" (e.g., "A is more like B than C") rather than explicit similarity scores. By using simple additive similarity functions and semi-definite programming (SDP), they prove that you can perfectly recover hidden clusters using a near-optimal number of comparisons—significantly fewer than previously thought possible.

What Problem Does This Paper Address?

Standard clustering algorithms (like k-means) usually require a clear numerical distance or similarity score between objects. However, in many real-world scenarios—like judging the taste of food or the aesthetic of cars—it is much easier for humans to provide relative comparisons than absolute scores.

The challenge lies in the passive setting, where a researcher is handed a fixed set of comparisons (triplets or quadruplets) without the ability to ask for more. Previous theoretical work suggested that to cluster $n$ objects accurately in this setting, you might need nearly all possible comparisons ($O(n^3)$ or $O(n^4)$). This paper asks: Can we achieve exact clustering with far fewer comparisons, approaching the efficiency of "active" methods that can strategically pick which objects to compare?

Methods

The authors propose a two-step pipeline:

  1. Additive Similarity Construction (AddS-3 and AddS-4): Instead of complex kernels, they use a simple counting method. For any two items $i$ and $j$, the similarity score is essentially the number of times they were judged "more similar" minus the number of times they were judged "less similar" in the available data. These functions are computationally efficient and can be built in a single pass over the data.
  2. SDP-based Clustering: They feed these similarity matrices into a Semi-Definite Programming (SDP) framework. Specifically, they use a version called SDP-$\lambda$, which doesn't require knowing the number of clusters ($k$) in advance. It uses a penalty parameter $\lambda$ to balance the fit of the clusters against the total number of clusters found.

To make the system practical, they also introduce a modified version of the SPUR algorithm to automatically tune the $\lambda$ parameter and estimate the correct number of clusters.

Datasets

The authors evaluated their approach on three types of data:

  • Simulated Data: A "planted partitioning" model where items belong to hidden clusters with random internal and external similarities.
  • MNIST Subsets:
    • MNIST 1vs.7: A subset of 2,163 images of the digits 1 and 7 (visually similar).
  • MNIST 10: A subset of 2,000 images covering all 10 digit classes.
  • Real-World Comparison Data:
    • Food Dataset: 100 items with ~190,000 triplet comparisons (no ground truth labels).
  • Car Dataset: 60 examples across 3 classes (SUV, city, sport) with ~12,000 triplet comparisons.

Key Insights and Ideas

  • Near-Optimality: The paper proves that $\Omega(n (\ln n)^2)$ passive comparisons are sufficient for exact recovery. Since you need at least $\Omega(n)$ comparisons just to see every object once, this result is "near-optimal" and much better than the previous $O(n^3)$ benchmarks.
  • Simplicity Wins: While previous methods used multiplicative kernels, this paper shows that simple additive similarities (counting wins vs. losses) are theoretically robust and practically faster.
  • Noise Tolerance: The framework accounts for two types of noise: "crowd noise" (random errors in human judgment) and "intrinsic noise" (the fact that a dessert might actually taste more like a main dish than another dessert).
  • Online Capability: Because the similarity matrices are additive, they can be updated "on the fly" as new comparisons arrive in a stream.

Key Results

Performance comparison of AddS and MulK methods
  • Efficiency: On the planted model, the proposed AddS methods reached a perfect Adjusted Rand Index (ARI) of 1.0 with significantly fewer comparisons than existing multiplicative kernels (MulK).
  • MNIST Performance: For the MNIST 1vs.7 task, the method reached peak performance using only $n(\ln n)^2$ triplets, matching the performance of k-means even though k-means had access to the actual pixel data.
  • Real Data: On the Car dataset, the method correctly identified the underlying structure. Interestingly, it suggested a 2-cluster solution (perhaps grouping by brand or color) was also highly plausible, highlighting the subjective nature of comparison-based data.

Limitations and Future Work

  • Distributional Assumptions: The current theoretical analysis assumes that similarities within and between clusters are identically distributed. The authors suggest that a more refined analysis could relax these assumptions for even broader applicability.
  • Computational Scaling: While the similarity construction is fast, solving large-scale SDPs can be computationally expensive for very large $n$.
  • Beyond Clustering: The authors note that their AddS-3 and AddS-4 similarity matrices could potentially be used for other tasks like semi-supervised learning or data embedding, which remains an open area for exploration.

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