# Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 41 references that are in the map.
- First posted on arXiv 10 Jun 2021.

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

- [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)
- [Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable](https://mlsanity.com/paper/1805.05208/) (2018)
- [Low-Latency Graph Streaming Using Compressed Purely-Functional Trees](https://mlsanity.com/paper/1904.08380/) (2019)
- [PAM: Parallel Augmented Maps](https://mlsanity.com/paper/1612.05665/) (2016)
- [Parallel Ordered Sets Using Join](https://mlsanity.com/paper/1602.02120/) (2016)
- [Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity](https://mlsanity.com/paper/2002.10142/) (2020)

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

- [The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure](https://mlsanity.com/paper/2312.04762/) (2023)
- [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)
- [Hierarchical Clustering: New Bounds and Objective](https://mlsanity.com/paper/2111.06863/) (2021)
- [Stars: Tera-Scale Graph Building for Clustering and Graph Learning](https://mlsanity.com/paper/2212.02635/) (2022)
- [The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering](https://mlsanity.com/paper/2411.10290/) (2024)
- [Chamfer-Linkage for Hierarchical Agglomerative Clustering](https://mlsanity.com/paper/2602.10444/) (2026)
- [Beyond Convolution: Advancing Hypergraph Neural Networks with Hypergraph U-Nets](https://mlsanity.com/paper/2606.09051/) (2026)

## Abstract (arXiv)

We study the widely used hierarchical agglomerative clustering (HAC) algorithm on edge-weighted graphs. We define an algorithmic framework for hierarchical agglomerative graph clustering that provides the first efficient tildeO(m) time exact algorithms for classic linkage measures, such as complete- and WPGMA-linkage, as well as other measures. Furthermore, for average-linkage, arguably the most popular variant of HAC, we provide an algorithm that runs in tildeO(n√m) time. For this variant, this is the first exact algorithm that runs in subquadratic time, as long as m=n2-ε for some constant ε > 0. We complement this result with a simple ε-close approximation algorithm for average-linkage in our framework that runs in tildeO(m) time. As an application of our algorithms, we consider clustering points in a metric space by first using k-NN to generate a graph from the point set, and then running our algorithms on the resulting weighted graph. We validate the performance of our algorithms on publicly available datasets, and show that our approach can speed up clustering of point datasets by a factor of 20.7--76.5x.