# A cost function for similarity-based hierarchical clustering

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2015.

## Built on by (most cited first, 30 of 63)

- [Hyperbolic Deep Neural Networks: A Survey](https://mlsanity.com/paper/2101.04562/) (2021)
- [Hyperbolic Deep Learning in Computer Vision: A Survey](https://mlsanity.com/paper/2305.06611/) (2023)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [HIER: Metric Learning Beyond Class Labels via Hierarchical Regularization](https://mlsanity.com/paper/2212.14258/) (2022)
- [Contrastive Multi-view Hyperbolic Hierarchical Clustering](https://mlsanity.com/paper/2205.02618/) (2022)
- [Hyperbolic Diffusion Embedding and Distance for Hierarchical Representation Learning](https://mlsanity.com/paper/2305.18962/) (2023)
- [Neural Distance Embeddings for Biological Sequences](https://mlsanity.com/paper/2109.09740/) (2021)
- [Supervised Tree-Wasserstein Distance](https://mlsanity.com/paper/2101.11520/) (2021)
- [GeoPhy: Differentiable Phylogenetic Inference via Geometric Gradients of Tree Topologies](https://mlsanity.com/paper/2307.03675/) (2023)
- [Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time](https://mlsanity.com/paper/2106.05610/) (2021)
- [Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs](https://mlsanity.com/paper/2112.09055/) (2021)
- [Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs](https://mlsanity.com/paper/2306.09950/) (2023)
- [Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering](https://mlsanity.com/paper/2107.01804/) (2021)
- [An Information-theoretic Perspective of Hierarchical Clustering](https://mlsanity.com/paper/2108.06036/) (2021)
- [Fairness Degrading Adversarial Attacks Against Clustering Algorithms](https://mlsanity.com/paper/2110.12020/) (2021)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy](https://mlsanity.com/paper/2410.21107/) (2024)
- [Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost](https://mlsanity.com/paper/2205.14198/) (2022)
- [Hyperbolic Geometry in Computer Vision: A Survey](https://mlsanity.com/paper/2304.10764/) (2023)
- [HyperAid: Denoising in hyperbolic spaces for tree-fitting and hierarchical clustering](https://mlsanity.com/paper/2205.09721/) (2022)
- [CEO: Corpus-based Open-Domain Event Ontology Induction](https://mlsanity.com/paper/2305.13521/) (2023)
- [An Axiomatic Definition of Hierarchical Clustering](https://mlsanity.com/paper/2407.03574/) (2024)
- [From Logits to Hierarchies: Hierarchical Clustering made Simple](https://mlsanity.com/paper/2410.07858/) (2024)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [Hierarchical clustering with dot products recovers hidden tree structure](https://mlsanity.com/paper/2305.15022/) (2023)
- [Fair Polylog-Approximate Low-Cost Hierarchical Clustering](https://mlsanity.com/paper/2311.12501/) (2023)
- [Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints](https://mlsanity.com/paper/2401.07091/) (2024)
- [A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering](https://mlsanity.com/paper/2406.04857/) (2024)
- [On the cohesion and separability of average-link for hierarchical agglomerative clustering](https://mlsanity.com/paper/2411.05097/) (2024)
- [Exact and Approximate Hierarchical Clustering Using A*](https://mlsanity.com/paper/2104.07061/) (2021)

## Abstract (arXiv)

The development of algorithms for hierarchical clustering has been hampered by a shortage of precise objective functions. To help address this situation, we introduce a simple cost function on hierarchies over a set of points, given pairwise similarities between those points. We show that this criterion behaves sensibly in canonical instances and that it admits a top-down construction procedure with a provably good approximation ratio.