# Hierarchical Clustering better than Average-Linkage

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

## Key facts

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

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

- [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)
- [An Information-theoretic Perspective of Hierarchical Clustering](https://mlsanity.com/paper/2108.06036/) (2021)
- [HyperAid: Denoising in hyperbolic spaces for tree-fitting and hierarchical clustering](https://mlsanity.com/paper/2205.09721/) (2022)
- [A Survey of Distance-Based Vessel Trajectory Clustering: Data Pre-processing, Methodologies, Applications, and Experimental Evaluation](https://mlsanity.com/paper/2407.11084/) (2024)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [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)
- [Hierarchical Clustering: New Bounds and Objective](https://mlsanity.com/paper/2111.06863/) (2021)
- [The Complexity of Finding Local Optima in Contrastive Learning](https://mlsanity.com/paper/2509.16898/) (2025)
- [Expanding the class of global objective functions for dissimilarity-based hierarchical clustering](https://mlsanity.com/paper/2207.14375/) (2022)
- [A Revenue Function for Comparison-Based Hierarchical Clustering](https://mlsanity.com/paper/2211.16459/) (2022)
- [Hierarchical Clustering via Local Search](https://mlsanity.com/paper/2405.15983/) (2024)
- [A Greedy Strategy for Graph Cut](https://mlsanity.com/paper/2412.20035/) (2024)
- [Hierarchical F-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs](https://mlsanity.com/paper/2607.13217/) (2026)

## Abstract (arXiv)

Hierarchical Clustering (HC) is a widely studied problem in exploratory data analysis, usually tackled by simple agglomerative procedures like average-linkage, single-linkage or complete-linkage. In this paper we focus on two objectives, introduced recently to give insight into the performance of average-linkage clustering: a similarity based HC objective proposed by [Moseley and Wang, 2017] and a dissimilarity based HC objective proposed by [Cohen-Addad et al., 2018]. In both cases, we present tight counterexamples showing that average-linkage cannot obtain better than 1/3 and 2/3 approximations respectively (in the worst-case), settling an open question raised in [Moseley and Wang, 2017]. This matches the approximation ratio of a random solution, raising a natural question: can we beat average-linkage for these objectives? We answer this in the affirmative, giving two new algorithms based on semidefinite programming with provably better guarantees.