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 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 $\approx 2/3 + 0.0004$ was due to Charikar et al. (SODA'19).

Introduction

Hierarchical clustering (HC) organizes data into a tree structure (a dendrogram) where internal nodes represent clusters of increasing granularity. While essential for tasks like anomaly detection and recommendation systems, HC faces two major hurdles in the era of Big Data: scalability and the "Random Tree" trap. Classic "bottom-up" algorithms typically require $O(n^2)$ or $O(n^3)$ time, which is prohibitively slow for datasets with millions of entries. Furthermore, in high-dimensional spaces, data points often exhibit a "concentration of measure" where distances become very similar, causing even random trees to achieve deceptively high scores on standard objectives. This study evaluates algorithms on massive datasets (up to 4.5 million entries) to find solutions that are both mathematically sound and computationally efficient.

Methods

The researchers propose two primary algorithms and a new way to measure success:

  • B++&C (Bisect++ and Conquer): This practical workhorse uses a top-down approach, recursively splitting the dataset. It employs gradient descent to optimize partitions and an "inverse kernel trick" to represent similarities as dot products, reducing computational complexity from $O(n^2)$ to $O(nk)$, where $k$ is the embedding dimension.
  • B2SAT&C: A theoretical algorithm that reduces the clustering problem to a "Balanced MAX-2-SAT" problem, achieving a 0.74-approximation for the distance-based objective (CKMM).
  • Normalized Objectives: To solve the "Random Tree" trap, the authors introduced normalized versions of the Moseley-Wang (MW) and Cohen-Addad (CKMM) objectives to measure performance specifically against a random baseline.
Algorithm 2: Bisect++ and Conquer (B++&C) pseudocode.

Key Results

B++&C consistently outperformed scalable alternatives like Bisecting K-Means, GRINCH, and PERCH by 5% to 59% on normalized objectives across almost all datasets. On the 4.5-million-point Wikipedia dataset, B++&C matched the speed of Bisecting K-Means while providing significantly higher quality clusters. The theoretical B2SAT&C algorithm also demonstrated superior performance, marking the first substantial improvement over the trivial 2/3-approximation in recent literature.

Normalized objective performance (alpha*_C) for various algorithms on ImageNet and Word2vec.

Discussion and Conclusion

The study reveals that top-down methods are generally superior for capturing the global structure of high-dimensional data. Interestingly, the quality of hierarchical clustering remained stable even when models faced distribution shifts (e.g., from ImageNet to ImageNetV2) that typically degrade classification accuracy. While B++&C allows for imbalanced splits to handle real-world data, providing rigorous theoretical guarantees for such splits remains an open challenge. Future research will also focus on extending these rigorous comparisons to non-binary trees.

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 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 $\approx 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