Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
Abstract
Despite its ubiquity, clustering lacks a universally accepted definition of what is a cluster. Kleinberg's Impossibility Theorem formalizes this difficulty by showing that no flat clustering method can simultaneously satisfy three natural axioms: scale invariance, richness, and consistency. In this paper, we ask whether this impossibility persists when the output is a hierarchy rather than a single partition. We show that, in contrast to the flat clustering setting, the hierarchical analog of these axioms are jointly satisfiable. In fact, there exist uncountably many hierarchical clustering methods satisfying these axioms, which we call admissible. We explicitly construct several admissible methods, including methods based on well-separated clusters and a non-binary version of single linkage. For certain pairs of admissible methods, the hierarchy produced by one always refines that produced by the other. This refinement relation defines a partial order on the class of admissible methods. This partially ordered set has no greatest element and contains uncountably many pairwise incompatible maximal elements, revealing substantial diversity among admissible methods. Nevertheless, this diversity is constrained: every admissible method contains a hierarchy of sufficiently well-separated clusters, and every finite collection of admissible methods shares such a nontrivial common backbone.
Related
- Invariance of Clustering Operations in Causal Effect Identification
- On the Consistency of Spectral Clustering under Generalized Gaussian Mixture Models
- Consistency of Optimal Matching-based Clustering for Mixtures of Markov Chains
- Hierarchical clustering of X-Ray Fluorescence images using a dissimilarity based on the likelihood ratio statistic
- Round-Trip KNN Clustering: multiscale hierarchical cluster detection on directed nearest-neighbour graphs
BibTeX
@misc{kuroda2026hierarchical,
title = {{Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance}},
author = {Daichi Kuroda and Maximilien Dreveton and Matthias Grossglauser and Patrick Thiran},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11173},
eprint = {2609.11173},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11173},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
AU - Daichi Kuroda
AU - Maximilien Dreveton
AU - Matthias Grossglauser
AU - Patrick Thiran
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11173
UR - https://arxiv.org/abs/2609.11173
AB - Despite its ubiquity, clustering lacks a universally accepted definition of what is a cluster. Kleinberg's Impossibility Theorem formalizes this difficulty by showing that no flat clustering method can simultaneously satisfy three natural axioms: scale invariance, richness, and consistency. In this paper, we ask whether this impossibility persists when the output is a hierarchy rather than a single partition. We show that, in contrast to the flat clustering setting, the hierarchical analog of these axioms are jointly satisfiable. In fact, there exist uncountably many hierarchical clustering methods satisfying these axioms, which we call admissible. We explicitly construct several admissible methods, including methods based on well-separated clusters and a non-binary version of single linkage. For certain pairs of admissible methods, the hierarchy produced by one always refines that produced by the other. This refinement relation defines a partial order on the class of admissible methods. This partially ordered set has no greatest element and contains uncountably many pairwise incompatible maximal elements, revealing substantial diversity among admissible methods. Nevertheless, this diversity is constrained: every admissible method contains a hierarchy of sufficiently well-separated clusters, and every finite collection of admissible methods shares such a nontrivial common backbone.
ER -