# Hierarchical clustering with dot products recovers hidden tree structure

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 51 references that are in the map.
- First posted on arXiv 24 May 2023.

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

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Statistical exploration of the Manifold Hypothesis](https://mlsanity.com/paper/2208.11665/) (2022)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [Fair Hierarchical Clustering](https://mlsanity.com/paper/2006.10221/) (2020)
- [Hierarchical Clustering via Spreading Metrics](https://mlsanity.com/paper/1610.09269/) (2016)
- [Scaling Hierarchical Agglomerative Clustering to Billion-sized Datasets](https://mlsanity.com/paper/2105.11653/) (2021)
- [Fair Algorithms for Hierarchical Agglomerative Clustering](https://mlsanity.com/paper/2005.03197/) (2020)
- [The evolutionary origins of hierarchy](https://mlsanity.com/paper/1505.06353/) (2015)
- [Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs](https://mlsanity.com/paper/2112.09055/) (2021)
- [Scalable Hierarchical Clustering with Tree Grafting](https://mlsanity.com/paper/2001.00076/) (2019)
- [Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering](https://mlsanity.com/paper/1506.06422/) (2015)
- [Statistical Inference for Cluster Trees](https://mlsanity.com/paper/1605.06416/) (2016)
- [Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT](https://mlsanity.com/paper/2102.11548/) (2021)
- [FNETS: Factor-adjusted network estimation and forecasting for high-dimensional time series](https://mlsanity.com/paper/2201.06110/) (2022)

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

- [How high is `high'? Rethinking the roles of dimensionality in topological data analysis and manifold learning](https://mlsanity.com/paper/2505.16879/) (2025)
- [Hierarchical Linkage Clustering Beyond Binary Trees and Ultrametrics](https://mlsanity.com/paper/2511.18056/) (2025)

## Abstract (arXiv)

In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure. We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance. We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model. The key technical innovations are to understand how hierarchical information in this model translates into tree geometry which can be recovered from data, and to characterise the benefits of simultaneously growing sample size and data dimension. We demonstrate superior tree recovery performance with real data over existing approaches such as UPGMA, Ward's method, and HDBSCAN.