# Scalable Hierarchical Clustering with Tree Grafting

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Dec 2019.

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

- [Cross-document Coreference Resolution over Predicted Mentions](https://mlsanity.com/paper/2106.01210/) (2021)
- [Estimating the Performance of Entity Resolution Algorithms: Lessons Learned Through PatentsView.org](https://mlsanity.com/paper/2210.01230/) (2022)
- [Hierarchical clustering with dot products recovers hidden tree structure](https://mlsanity.com/paper/2305.15022/) (2023)
- [Exact and Approximate Hierarchical Clustering Using A*](https://mlsanity.com/paper/2104.07061/) (2021)
- [ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain](https://mlsanity.com/paper/2106.04727/) (2021)
- [Variational Pseudo Marginal Methods for Jet Reconstruction in Particle Physics](https://mlsanity.com/paper/2406.03242/) (2024)
- [Hierarchical Clustering via Local Search](https://mlsanity.com/paper/2405.15983/) (2024)

## Abstract (arXiv)

We introduce Grinch, a new algorithm for large-scale, non-greedy hierarchical clustering with general linkage functions that compute arbitrary similarity between two point sets. The key components of Grinch are its rotate and graft subroutines that efficiently reconfigure the hierarchy as new points arrive, supporting discovery of clusters with complex structure. Grinch is motivated by a new notion of separability for clustering with linkage functions: we prove that when the model is consistent with a ground-truth clustering, Grinch is guaranteed to produce a cluster tree containing the ground-truth, independent of data arrival order. Our empirical results on benchmark and author coreference datasets (with standard and learned linkage functions) show that Grinch is more accurate than other scalable methods, and orders of magnitude faster than hierarchical agglomerative clustering.