# Hierarchical Clustering: New Bounds and Objective

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 28 references that are in the map.
- First posted on arXiv 12 Nov 2021.

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

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [Fair Hierarchical Clustering](https://mlsanity.com/paper/2006.10221/) (2020)
- [Hierarchical Clustering via Spreading Metrics](https://mlsanity.com/paper/1610.09269/) (2016)
- [Hierarchical Clustering better than Average-Linkage](https://mlsanity.com/paper/1808.02227/) (2018)
- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [An Improved Cost Function for Hierarchical Cluster Trees](https://mlsanity.com/paper/1812.02715/) (2018)
- [Adaptive Hierarchical Clustering Using Ordinal Queries](https://mlsanity.com/paper/1708.00149/) (2017)
- [Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection](https://mlsanity.com/paper/1912.06983/) (2019)
- [Hierarchical Clustering: a 0.585 Revenue Approximation](https://mlsanity.com/paper/2006.01933/) (2020)
- [Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time](https://mlsanity.com/paper/2106.05610/) (2021)
- [Online Hierarchical Clustering Approximations](https://mlsanity.com/paper/1909.09667/) (2019)
- [An Objective for Hierarchical Clustering in Euclidean Space and its Connection to Bisecting K-means](https://mlsanity.com/paper/2008.13235/) (2020)
- [Hierarchical Clustering for Euclidean Data](https://mlsanity.com/paper/1812.10582/) (2018)
- [Hierarchical Clustering via Sketches and Hierarchical Correlation Clustering](https://mlsanity.com/paper/2101.10639/) (2021)
- [Hierarchical Clusterings of Unweighted Graphs](https://mlsanity.com/paper/2008.03061/) (2020)
- [Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering](https://mlsanity.com/paper/2010.01459/) (2020)

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

- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)

## Abstract (arXiv)

Hierarchical Clustering has been studied and used extensively as a method for analysis of data. More recently, Dasgupta [2016] defined a precise objective function. Given a set of n data points with a weight function wi,j for each two items i and j denoting their similarity/dis-similarity, the goal is to build a recursive (tree like) partitioning of the data points (items) into successively smaller clusters. He defined a cost function for a tree T to be Cost(T) = sumi,j ∈ [n] big(wi,j × |Ti,j| big) where Ti,j is the subtree rooted at the least common ancestor of i and j and presented the first approximation algorithm for such clustering. Then Moseley and Wang [2017] considered the dual of Dasgupta's objective function for similarity-based weights and showed that both random partitioning and average linkage have approximation ratio 1/3 which has been improved in a series of works to 0.585 [Alon et al. 2020]. Later Cohen-Addad et al. [2019] considered the same objective function as Dasgupta's but for dissimilarity-based metrics, called Rev(T). It is shown that both random partitioning and average linkage have ratio 2/3 which has been only slightly improved to 0.667078 [Charikar et al. SODA2020]. Our first main result is to consider Rev(T) and present a more delicate algorithm and careful analysis that achieves approximation 0.71604. We also introduce a new objective function for dissimilarity-based clustering. For any tree T, let Hi,j be the number of i and j's common ancestors. Intuitively, items that are similar are expected to remain within the same cluster as deep as possible. So, for dissimilarity-based metrics, we suggest the cost of each tree T, which we want to minimize, to be CostH(T) = sumi,j ∈ [n] big(wi,j × Hi,j big). We present a 1.3977-approximation for this objective.