# A Revenue Function for Comparison-Based Hierarchical Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 45 references that are in the map.
- First posted on arXiv 29 Nov 2022.

## Builds on (most cited first, 18 of 18)

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Hierarchical Clustering: Objective Functions and Algorithms](https://mlsanity.com/paper/1704.02147/) (2017)
- [Hierarchical Clustering better than Average-Linkage](https://mlsanity.com/paper/1808.02227/) (2018)
- [Cost-Effective HITs for Relative Similarity Comparisons](https://mlsanity.com/paper/1404.3291/) (2014)
- [An Improved Cost Function for Hierarchical Cluster Trees](https://mlsanity.com/paper/1812.02715/) (2018)
- [Interactive Bayesian Hierarchical Clustering](https://mlsanity.com/paper/1602.03258/) (2016)
- [Adaptive Hierarchical Clustering Using Ordinal Queries](https://mlsanity.com/paper/1708.00149/) (2017)
- [Hierarchical Clustering: a 0.585 Revenue Approximation](https://mlsanity.com/paper/2006.01933/) (2020)
- [Foundations of Comparison-Based Hierarchical Clustering](https://mlsanity.com/paper/1811.00928/) (2018)
- [Comparison Based Nearest Neighbor Search](https://mlsanity.com/paper/1704.01460/) (2017)
- [Crowdsourced correlation clustering with relative distance comparisons](https://mlsanity.com/paper/1709.08459/) (2017)
- [Comparison Based Learning from Weak Oracles](https://mlsanity.com/paper/1802.06942/) (2018)
- [Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT](https://mlsanity.com/paper/2102.11548/) (2021)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [Estimation of perceptual scales using ordinal embedding](https://mlsanity.com/paper/1908.07962/) (2019)
- [Near-Optimal Comparison Based Clustering](https://mlsanity.com/paper/2010.03918/) (2020)
- [Kernel functions based on triplet comparisons](https://mlsanity.com/paper/1607.08456/) (2016)
- [Boosting for Comparison-Based Learning](https://mlsanity.com/paper/1810.13333/) (2018)

## Abstract (arXiv)

Comparison-based learning addresses the problem of learning when, instead of explicit features or pairwise similarities, one only has access to comparisons of the form: Object A is more similar to B than to C. Recently, it has been shown that, in Hierarchical Clustering, single and complete linkage can be directly implemented using only such comparisons while several algorithms have been proposed to emulate the behaviour of average linkage. Hence, finding hierarchies (or dendrograms) using only comparisons is a well understood problem. However, evaluating their meaningfulness when no ground-truth nor explicit similarities are available remains an open question. In this paper, we bridge this gap by proposing a new revenue function that allows one to measure the goodness of dendrograms using only comparisons. We show that this function is closely related to Dasgupta's cost for hierarchical clustering that uses pairwise similarities. On the theoretical side, we use the proposed revenue function to resolve the open problem of whether one can approximately recover a latent hierarchy using few triplet comparisons. On the practical side, we present principled algorithms for comparison-based hierarchical clustering based on the maximisation of the revenue and we empirically compare them with existing methods.