# Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 16 Dec 2021.

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

- [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)
- [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)
- [Distributed Graph Clustering and Sparsification](https://mlsanity.com/paper/1711.01262/) (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)
- [Partitioning into Expanders](https://mlsanity.com/paper/1309.3223/) (2013)
- [Online Hierarchical Clustering Approximations](https://mlsanity.com/paper/1909.09667/) (2019)
- [Hierarchical Clustering for Euclidean Data](https://mlsanity.com/paper/1812.10582/) (2018)
- [Hermitian Laplacians and a Cheeger inequality for the Max-2-Lin problem](https://mlsanity.com/paper/1811.10909/) (2018)
- [Hierarchical Clustering via Sketches and Hierarchical Correlation Clustering](https://mlsanity.com/paper/2101.10639/) (2021)

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

- [Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs](https://mlsanity.com/paper/2306.09950/) (2023)
- [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)
- [Expanding the class of global objective functions for dissimilarity-based hierarchical clustering](https://mlsanity.com/paper/2207.14375/) (2022)
- [A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time](https://mlsanity.com/paper/2310.17878/) (2023)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)
- [Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examples](https://mlsanity.com/paper/2605.07119/) (2026)
- [Beyond Convolution: Advancing Hypergraph Neural Networks with Hypergraph U-Nets](https://mlsanity.com/paper/2606.09051/) (2026)

## Abstract (arXiv)

Hierarchical clustering studies a recursive partition of a data set into clusters of successively smaller size, and is a fundamental problem in data analysis. In this work we study the cost function for hierarchical clustering introduced by Dasgupta, and present two polynomial-time approximation algorithms: Our first result is an O(1)-approximation algorithm for graphs of high conductance. Our simple construction bypasses complicated recursive routines of finding sparse cuts known in the literature. Our second and main result is an O(1)-approximation algorithm for a wide family of graphs that exhibit a well-defined structure of clusters. This result generalises the previous state-of-the-art, which holds only for graphs generated from stochastic models. The significance of our work is demonstrated by the empirical analysis on both synthetic and real-world data sets, on which our presented algorithm outperforms the previously proposed algorithm for graphs with a well-defined cluster structure.