# Objective-Based Hierarchical Clustering of Deep Embedding Vectors

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2020.

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

- [An Information-theoretic Perspective of Hierarchical Clustering](https://mlsanity.com/paper/2108.06036/) (2021)
- [EGRC-Net: Embedding-induced Graph Refinement Clustering Network](https://mlsanity.com/paper/2211.10627/) (2022)
- [Contrastive Hierarchical Clustering](https://mlsanity.com/paper/2303.03389/) (2023)
- [Explainable AI in Speaker Recognition -- Making Latent Representations Understandable](https://mlsanity.com/paper/2604.23354/) (2026)
- [Exact and Approximate Hierarchical Clustering Using A*](https://mlsanity.com/paper/2104.07061/) (2021)
- [Variational Pseudo Marginal Methods for Jet Reconstruction in Particle Physics](https://mlsanity.com/paper/2406.03242/) (2024)
- [The Complexity of Finding Local Optima in Contrastive Learning](https://mlsanity.com/paper/2509.16898/) (2025)
- [Tree-Guided Rare Feature Selection and Logic Aggregation with Electronic Health Records Data](https://mlsanity.com/paper/2206.09107/) (2022)
- [Rethinking Divisive Hierarchical Clustering from a Distributional Perspective](https://mlsanity.com/paper/2601.19718/) (2026)

## Abstract (arXiv)

We initiate a comprehensive experimental study of objective-based hierarchical clustering methods on massive datasets consisting of deep embedding vectors from computer vision and NLP applications. This includes a large variety of image embedding (ImageNet, ImageNetV2, NaBirds), word embedding (Twitter, Wikipedia), and sentence embedding (SST-2) vectors from several popular recent models (e.g. ResNet, ResNext, Inception V3, SBERT). Our study includes datasets with up to 4.5 million entries with embedding dimensions up to 2048. In order to address the challenge of scaling up hierarchical clustering to such large datasets we propose a new practical hierarchical clustering algorithm B++&C. It gives a 5%/20% improvement on average for the popular Moseley-Wang (MW) / Cohen-Addad et al. (CKMM) objectives (normalized) compared to a wide range of classic methods and recent heuristics. We also introduce a theoretical algorithm B2SAT&C which achieves a 0.74-approximation for the CKMM objective in polynomial time. This is the first substantial improvement over the trivial 2/3-approximation achieved by a random binary tree. Prior to this work, the best poly-time approximation of ≈ 2/3 + 0.0004 was due to Charikar et al. (SODA'19).