On the cohesion and separability of average-link for hierarchical agglomerative clustering
Not on the map. Why?
Abstract (arXiv)
Average-link is widely recognized as one of the most popular and effective methods for building hierarchical agglomerative clustering. The available theoretical analyses show that this method has a much better approximation than other popular heuristics, as single-linkage and complete-linkage, regarding variants of Dasgupta's cost function [STOC 2016]. However, these analyses do not separate average-link from a random hierarchy and they are not appealing for metric spaces since every hierarchical clustering has a 1/2 approximation with regard to the variant of Dasgupta's function that is employed for dissimilarity measures [Moseley and Yang 2020]. In this paper, we present a comprehensive study of the performance of average-link in metric spaces, regarding several natural criteria that capture separability and cohesion and are more interpretable than Dasgupta's cost function and its variants. We also present experimental results with real datasets that, together with our theoretical analyses, suggest that average-link is a better choice than other related methods when both cohesion and separability are important goals.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 11 of its 33 references that are in the map. First posted on arXiv 7 Nov 2024.
Builds on
11 of 33 references.
References · 11
- 2015A cost function for similarity-based hierarchical clusteringcited by 63
- 2018Hierarchical Clustering better than Average-Linkagecited by 16
- 2020Scalable Hierarchical Agglomerative Clusteringcited by 13
- 2021Hierarchical Agglomerative Graph Clustering in Nearly-Linear Timecited by 8
- 2020An Objective for Hierarchical Clustering in Euclidean Space and its Connection to Bisecting K-meanscited by 6
- 2022Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depthcited by 6
- 2023TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphscited by 6
- 2018Hierarchical Clustering for Euclidean Datacited by 5
- 2024Optimization of Inter-group Criteria for Clustering with Minimum Size Constraintscited by 2
- 2019Analysis of Ward's Methodcited by 1
- 2021ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chaincited by 1
Built on by
Citing papers per year: 2025: 2.
2 papers.