Objective-Based Hierarchical Clustering of Deep Embedding Vectors

Stanislav Naumov, Grigory Yaroslavtsev, Dmitrii Avdiukhin

Abstract

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 data points 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.

Introduction

Hierarchical clustering (HC) is essential for organizing data into a "tree" of relationships (dendrograms), but it faces two major hurdles when applied to modern deep learning: scalability and deceptive metrics. Classic bottom-up (agglomerative) methods are computationally prohibitive for datasets with millions of vectors. Furthermore, in high-dimensional spaces, even a random tree can achieve 85-97% "accuracy" on standard objectives because of the way distances concentrate. This makes it difficult to distinguish a truly effective algorithm from a mediocre one. This paper bridges the gap between theoretical HC objectives and the practical need to cluster millions of image and text embeddings.

Methodology

The paper proposes two primary algorithms and a new evaluation framework to address these challenges.

B++&C (Bisect++ and Conquer)

B++&C is a practical, top-down algorithm that recursively splits the dataset using a gradient descent approach. To avoid the $O(n^2)$ cost of building a full similarity matrix, the authors utilize an "Inverse Kernel Trick", representing the similarity matrix as a product of low-rank matrices. This allows for gradient computation in $O(nk)$ time (where $k$ is the embedding dimension), making the algorithm extremely fast and parallelizable. Additionally, it supports imbalanced splits, which better reflects real-world data hierarchies compared to standard bisection.

B2SAT&C

A theoretical algorithm that reduces the clustering problem to a "Balanced Max-2-SAT" problem. It provides a 0.74-approximation for the distance-based (CKMM) objective, a significant improvement over the previous best of approximately 0.66.

Normalized Metrics

To provide a more honest assessment of performance, the authors introduce normalized approximation factors ($\alpha^*$). These metrics subtract the expected performance of a random tree, allowing researchers to see the actual "value add" of a specific algorithm.

Normalized approximation factors ($\alpha^*_C$) for ImageNet and Word2vec datasets, showing the clear performance gain of B++&C over other scalable methods.

Experimental Setup

The methods were evaluated on a massive scale across Computer Vision (CV) and Natural Language Processing (NLP) domains:

  • CV: ImageNet (1.2M images), ImageNetV2, and NaBirds.
  • NLP: Twitter (Glove), Wikipedia (Word2vec), and SST-2 (SBERT). Datasets ranged from 50,000 to 4.5 million entries, with embedding dimensions up to 2048.

Key Results and Insights

  • Performance Gains: B++&C outperformed all other scalable alternatives (like Bisecting K-Means and GRINCH) by 5% to 20% on average across the normalized MW and CKMM objectives.
  • Word2vec Success: On the Wikipedia Word2vec dataset, B++&C showed a massive 35% improvement over the next best scalable method in terms of the normalized CKMM objective.
  • Efficiency: The algorithm handled 4.5 million vectors within a 5-hour timeout window, a feat impossible for classic agglomerative methods.
  • Structural Stability: Interestingly, hierarchical clustering quality remained stable when moving from ImageNet to ImageNetV2, even though classification accuracy typically drops. This suggests HC objectives capture more fundamental structural properties of the data.
Experimental results for the CKMM objective across various CV and NLP datasets, including dataset statistics.

Conclusion

B++&C represents a significant step forward in scalable hierarchical clustering for deep embeddings. By combining efficient top-down partitioning with a novel low-rank gradient computation and more rigorous evaluation metrics, this work provides a robust framework for organizing massive high-dimensional datasets. Future research will focus on extending these methods to non-binary trees and providing theoretical guarantees for imbalanced splits.

Summary updated

Abstract

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 data points 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)
BibTeX
@inproceedings{naumov2021objective,
  author = {Stanislav Naumov and Grigory Yaroslavtsev and Dmitrii Avdiukhin},
  title = {{Objective-Based Hierarchical Clustering of Deep Embedding Vectors}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=CB8mNOGHEku},
}
Figure