# Exact and Approximate Hierarchical Clustering Using A*

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 54 references that are in the map.
- First posted on arXiv 14 Apr 2021.

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

- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering](https://mlsanity.com/paper/2010.00402/) (2020)
- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Hierarchical Clustering: Objective Functions and Algorithms](https://mlsanity.com/paper/1704.02147/) (2017)
- [CESI: Canonicalizing Open Knowledge Bases using Embeddings and Side Information](https://mlsanity.com/paper/1902.00172/) (2019)
- [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)
- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [Objective-Based Hierarchical Clustering of Deep Embedding Vectors](https://mlsanity.com/paper/2012.08466/) (2020)
- [Scalable Hierarchical Clustering with Tree Grafting](https://mlsanity.com/paper/2001.00076/) (2019)
- [Hierarchical clustering in particle physics through reinforcement learning](https://mlsanity.com/paper/2011.08191/) (2020)
- [Distributed, partially collapsed MCMC for Bayesian Nonparametrics](https://mlsanity.com/paper/2001.05591/) (2020)

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

- [Variational Pseudo Marginal Methods for Jet Reconstruction in Particle Physics](https://mlsanity.com/paper/2406.03242/) (2024)

## Abstract (arXiv)

Hierarchical clustering is a critical task in numerous domains. Many approaches are based on heuristics and the properties of the resulting clusterings are studied post hoc. However, in several applications, there is a natural cost function that can be used to characterize the quality of the clustering. In those cases, hierarchical clustering can be seen as a combinatorial optimization problem. To that end, we introduce a new approach based on A* search. We overcome the prohibitively large search space by combining A* with a novel trellis data structure. This combination results in an exact algorithm that scales beyond previous state of the art, from a search space with 1012 trees to 1015 trees, and an approximate algorithm that improves over baselines, even in enormous search spaces that contain more than 101000 trees. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks. We describe how our method provides significantly improved theoretical bounds on the time and space complexity of A* for clustering.