# An Information-theoretic Perspective of Hierarchical Clustering

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 13 Aug 2021.

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

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [Hierarchical Clustering better than Average-Linkage](https://mlsanity.com/paper/1808.02227/) (2018)
- [Objective-Based Hierarchical Clustering of Deep Embedding Vectors](https://mlsanity.com/paper/2012.08466/) (2020)
- [Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection](https://mlsanity.com/paper/1912.06983/) (2019)
- [Partitioning into Expanders](https://mlsanity.com/paper/1309.3223/) (2013)

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

- [SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization](https://mlsanity.com/paper/2303.09778/) (2023)
- [Adversarial Socialbots Modeling Based on Structural Information Principles](https://mlsanity.com/paper/2312.08098/) (2023)
- [Effective Exploration Based on the Structural Information Principles](https://mlsanity.com/paper/2410.06621/) (2024)
- [Hyperbolic Continuous Structural Entropy for Hierarchical Clustering](https://mlsanity.com/paper/2512.00524/) (2025)
- [Structural Optimization Makes Graph Classification Simpler and Better](https://mlsanity.com/paper/2109.02027/) (2021)
- [Semi-Supervised Clustering via Structural Entropy with Different Constraints](https://mlsanity.com/paper/2312.10917/) (2023)

## Abstract (arXiv)

A combinatorial cost function for hierarchical clustering was introduced by Dasgupta citedasgupta2016cost. It has been generalized by Cohen-Addad et al. citecohen2019hierarchical to a general form named admissible function. In this paper, we investigate hierarchical clustering from the information-theoretic perspective and formulate a new objective function. We also establish the relationship between these two perspectives. In algorithmic aspect, we get rid of the traditional top-down and bottom-up frameworks, and propose a new one to stratify the sparsest level of a cluster tree recursively in guide with our objective function. For practical use, our resulting cluster tree is not binary. Our algorithm called HCSE outputs a k-level cluster tree by a novel and interpretable mechanism to choose k automatically without any hyper-parameter. Our experimental results on synthetic datasets show that HCSE has a great advantage in finding the intrinsic number of hierarchies, and the results on real datasets show that HCSE also achieves competitive costs over the popular algorithms LOUVAIN and HLP.