# Chamfer-Linkage for Hierarchical Agglomerative Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 50 references that are in the map.
- First posted on arXiv 11 Feb 2026.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [Towards General Text Embeddings with Multi-stage Contrastive Learning](https://mlsanity.com/paper/2308.03281/) (2023)
- [EMNIST: an extension of MNIST to handwritten letters](https://mlsanity.com/paper/1702.05373/) (2017)
- [PLAID: An Efficient Engine for Late Interaction Retrieval](https://mlsanity.com/paper/2205.09707/) (2022)
- [Transductive Zero-Shot Learning with Visual Structure Constraint](https://mlsanity.com/paper/1901.01570/) (2019)
- [MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings](https://mlsanity.com/paper/2405.19504/) (2024)
- [Scalable Hierarchical Agglomerative Clustering](https://mlsanity.com/paper/2010.11821/) (2020)
- [Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time](https://mlsanity.com/paper/2106.05610/) (2021)
- [Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth](https://mlsanity.com/paper/2206.11654/) (2022)
- [Alloprof: a new French question-answer education dataset and its use in an information retrieval case study](https://mlsanity.com/paper/2302.07738/) (2023)
- [TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs](https://mlsanity.com/paper/2308.03578/) (2023)
- [PAM: Parallel Augmented Maps](https://mlsanity.com/paper/1612.05665/) (2016)
- [Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering](https://mlsanity.com/paper/2205.04956/) (2022)

## Abstract (arXiv)

Hierarchical Agglomerative Clustering (HAC) is a widely-used clustering method based on repeatedly merging the closest pair of clusters, where inter-cluster distances are determined by a linkage function. Unlike many clustering methods, HAC does not optimize a single explicit global objective; clustering quality is therefore primarily evaluated empirically, and the choice of linkage function plays a crucial role in practice. However, popular classical linkages, such as single-linkage, average-linkage and Ward's method show high variability across real-world datasets and do not consistently produce high-quality clusterings in practice. In this paper, we propose Chamfer-linkage, a novel linkage function that measures the distance between clusters using the Chamfer distance, a popular notion of distance between point-clouds in machine learning and computer vision. We argue that Chamfer-linkage satisfies desirable concept representation properties that other popular measures struggle to satisfy. Theoretically, we show that Chamfer-linkage HAC can be implemented in O(n2) time, matching the efficiency of classical linkage functions. Experimentally, we find that Chamfer-linkage consistently yields higher-quality clusterings than classical linkages such as average-linkage and Ward's method across a diverse collection of datasets. Our results establish Chamfer-linkage as a practical drop-in replacement for classical linkage functions, broadening the toolkit for hierarchical clustering in both theory and practice.