# Foundations of Comparison-Based Hierarchical Clustering

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2018.

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

- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [An objective function for order preserving hierarchical clustering](https://mlsanity.com/paper/2109.04266/) (2021)
- [A Revenue Function for Comparison-Based Hierarchical Clustering](https://mlsanity.com/paper/2211.16459/) (2022)
- [Metric k-clustering using only Weak Comparison Oracles](https://mlsanity.com/paper/2601.19333/) (2026)
- [Rethinking Divisive Hierarchical Clustering from a Distributional Perspective](https://mlsanity.com/paper/2601.19718/) (2026)
- [Optimal VC Dimension of Contrastive Learning with Margin](https://mlsanity.com/paper/2609.38834/) (2026)

## Abstract (arXiv)

We address the classical problem of hierarchical clustering, but in a framework where one does not have access to a representation of the objects or their pairwise similarities. Instead, we assume that only a set of comparisons between objects is available, that is, statements of the form "objects i and j are more similar than objects k and l." Such a scenario is commonly encountered in crowdsourcing applications. The focus of this work is to develop comparison-based hierarchical clustering algorithms that do not rely on the principles of ordinal embedding. We show that single and complete linkage are inherently comparison-based and we develop variants of average linkage. We provide statistical guarantees for the different methods under a planted hierarchical partition model. We also empirically demonstrate the performance of the proposed approaches on several datasets.