# Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 16 Jun 2023.

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

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [GEMSEC: Graph Embedding with Self Clustering](https://mlsanity.com/paper/1802.03997/) (2018)
- [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)
- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Improved Analysis of Spectral Algorithm for Clustering](https://mlsanity.com/paper/1912.02997/) (2019)
- [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 Clustering: O(1)-Approximation for Well-Clustered Graphs](https://mlsanity.com/paper/2112.09055/) (2021)
- [Partitioning into Expanders](https://mlsanity.com/paper/1309.3223/) (2013)
- [Online Hierarchical Clustering Approximations](https://mlsanity.com/paper/1909.09667/) (2019)
- [Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds](https://mlsanity.com/paper/2207.02581/) (2022)

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

- [Unsupervised Skin Lesion Segmentation via Structural Entropy Minimization on Multi-Scale Superpixel Graphs](https://mlsanity.com/paper/2309.01899/) (2023)
- [Hyperbolic Continuous Structural Entropy for Hierarchical Clustering](https://mlsanity.com/paper/2512.00524/) (2025)
- [USL-Net: Uncertainty Self-Learning Network for Unsupervised Skin Lesion Segmentation](https://mlsanity.com/paper/2309.13289/) (2023)
- [A Spectral Framework for Tracking Communities in Evolving Networks](https://mlsanity.com/paper/2412.07378/) (2024)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)
- [Rethinking Divisive Hierarchical Clustering from a Distributional Perspective](https://mlsanity.com/paper/2601.19718/) (2026)
- [Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examples](https://mlsanity.com/paper/2605.07119/) (2026)

## Abstract (arXiv)

This paper presents two efficient hierarchical clustering (HC) algorithms with respect to Dasgupta's cost function. For any input graph G with a clear cluster-structure, our designed algorithms run in nearly-linear time in the input size of G, and return an O(1)-approximate HC tree with respect to Dasgupta's cost function. We compare the performance of our algorithm against the previous state-of-the-art on synthetic and real-world datasets and show that our designed algorithm produces comparable or better HC trees with much lower running time.