# TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2023.

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

- [On the cohesion and separability of average-link for hierarchical agglomerative clustering](https://mlsanity.com/paper/2411.05097/) (2024)
- [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)
- [Efficient Recommendations via Graph Coarsening and Label Propagation](https://mlsanity.com/paper/2607.22287/) (2026)
- [Refining Heuristic-Based Bitcoin Address Clustering with Graph Neural Networks](https://mlsanity.com/paper/2609.01942/) (2026)

## Abstract (arXiv)

We introduce TeraHAC, a (1+ε)-approximate hierarchical agglomerative clustering (HAC) algorithm which scales to trillion-edge graphs. Our algorithm is based on a new approach to computing (1+ε)-approximate HAC, which is a novel combination of the nearest-neighbor chain algorithm and the notion of (1+ε)-approximate HAC. Our approach allows us to partition the graph among multiple machines and make significant progress in computing the clustering within each partition before any communication with other partitions is needed. We evaluate TeraHAC on a number of real-world and synthetic graphs of up to 8 trillion edges. We show that TeraHAC requires over 100x fewer rounds compared to previously known approaches for computing HAC. It is up to 8.3x faster than SCC, the state-of-the-art distributed algorithm for hierarchical clustering, while achieving 1.16x higher quality. In fact, TeraHAC essentially retains the quality of the celebrated HAC algorithm while significantly improving the running time.