# Hierarchical Clustering: Objective Functions and Algorithms

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

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Apr 2017.

## Built on by (most cited first, 30 of 60)

- [Neural Concept Binder](https://mlsanity.com/paper/2406.09949/) (2024)
- [Quantum Vision Clustering](https://mlsanity.com/paper/2309.09907/) (2023)
- [From A-to-Z Review of Clustering Validation Indices](https://mlsanity.com/paper/2407.20246/) (2024)
- [Group-SAE: Efficient Training of Sparse Autoencoders for Large Language Models via Layer Groups](https://mlsanity.com/paper/2410.21508/) (2024)
- [DriveQA: Passing the Driving Knowledge Test](https://mlsanity.com/paper/2508.21824/) (2025)
- [A Rapid Review of Clustering Algorithms](https://mlsanity.com/paper/2401.07389/) (2024)
- [Emergence of Hierarchical Emotion Organization in Large Language Models](https://mlsanity.com/paper/2507.10599/) (2025)
- [Combating noisy labels in object detection datasets](https://mlsanity.com/paper/2211.13993/) (2022)
- [Long-form analogies generated by chatGPT lack human-like psycholinguistic properties](https://mlsanity.com/paper/2306.04537/) (2023)
- [Quant 4.0: Engineering Quantitative Investment with Automated, Explainable and Knowledge-driven Artificial Intelligence](https://mlsanity.com/paper/2301.04020/) (2022)
- [ClusterFormer: Clustering As A Universal Visual Learner](https://mlsanity.com/paper/2309.13196/) (2023)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [DSAP: Analyzing Bias Through Demographic Comparison of Datasets](https://mlsanity.com/paper/2312.14626/) (2023)
- [FedCCL: Federated Dual-Clustered Feature Contrast Under Domain Heterogeneity](https://mlsanity.com/paper/2404.09259/) (2024)
- [A Perceptual Measure for Evaluating the Resynthesis of Automatic Music Transcriptions](https://mlsanity.com/paper/2202.12257/) (2022)
- [Hyperbolic Geometry in Computer Vision: A Survey](https://mlsanity.com/paper/2304.10764/) (2023)
- [Mystique: Deconstructing SVG Charts for Layout Reuse](https://mlsanity.com/paper/2307.13567/) (2023)
- [zScore: A Universal Decentralised Reputation System for the Blockchain Economy](https://mlsanity.com/paper/2503.05718/) (2025)
- [Should Top-Down Clustering Affect Boundaries in Unsupervised Word Discovery?](https://mlsanity.com/paper/2507.19204/) (2025)
- [Unsupervised Clustering of Roman Potsherds via Variational Autoencoders](https://mlsanity.com/paper/2203.07437/) (2022)
- [Graph-based Semi-supervised Local Clustering with Few Labeled Nodes](https://mlsanity.com/paper/2211.11114/) (2022)
- [From Logits to Hierarchies: Hierarchical Clustering made Simple](https://mlsanity.com/paper/2410.07858/) (2024)
- [High-dimensional Clustering onto Hamiltonian Cycle](https://mlsanity.com/paper/2304.14531/) (2023)
- [Mixed-type Distance Shrinkage and Selection for Clustering via Kernel Metric Learning](https://mlsanity.com/paper/2306.01890/) (2023)
- [Can Your Model Tell a Negation from an Implicature? Unravelling Challenges With Intent Encoders](https://mlsanity.com/paper/2403.04314/) (2024)
- [The Lie of the Average: How Class Incremental Learning Evaluation Deceives You?](https://mlsanity.com/paper/2509.22580/) (2025)
- [Exact and Approximate Hierarchical Clustering Using A*](https://mlsanity.com/paper/2104.07061/) (2021)
- [ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain](https://mlsanity.com/paper/2106.04727/) (2021)
- [Tab2vox: CNN-Based Multivariate Multilevel Demand Forecasting Framework by Tabular-To-Voxel Image Conversion](https://mlsanity.com/paper/2209.10516/) (2022)
- [When Does Bottom-up Beat Top-down in Hierarchical Community Detection?](https://mlsanity.com/paper/2306.00833/) (2023)

## Abstract (arXiv)

Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, Dasgupta framed similarity-based hierarchical clustering as a combinatorial optimization problem, where a `good' hierarchical clustering is one that minimizes some cost function. He showed that this cost function has certain desirable properties. We take an axiomatic approach to defining `good' objective functions for both similarity and dissimilarity-based hierarchical clustering. We characterize a set of "admissible" objective functions (that includes Dasgupta's one) that have the property that when the input admits a `natural' hierarchical clustering, it has an optimal value. Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better algorithms. For similarity-based hierarchical clustering, Dasgupta showed that the divisive sparsest-cut approach achieves an O(log3/2 n)-approximation. We give a refined analysis of the algorithm and show that it in fact achieves an O(√log n)-approx. (Charikar and Chatziafratis independently proved that it is a O(√log n)-approx.). This improves upon the LP-based O(log n)-approx. of Roy and Pokutta. For dissimilarity-based hierarchical clustering, we show that the classic average-linkage algorithm gives a factor 2 approx., and provide a simple and better algorithm that gives a factor 3/2 approx.. Finally, we consider `beyond-worst-case' scenario through a generalisation of the stochastic block model for hierarchical clustering. We show that Dasgupta's cost function has desirable properties for these inputs and we provide a simple 1 + o(1)-approximation in this setting.