Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance — Paper

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.

Authors 4

Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

Specification

Official page: arxiv.org/abs/2609.11173
Source:arXiv (Atom API + RSS)T1observed 35 min agohigh
Arxiv announce type: new
Source:arXiv (Atom API + RSS)T1observed 35 min agohigh
arXiv id: 2609.11173
Source:arXiv (Atom API + RSS)T1observed 35 min agohigh
Categories: cs.LG, stat.ME, stat.ML
Source:arXiv (Atom API + RSS)T1observed 35 min agohigh
PDF: arxiv.org/pdf/2609.11173
Source:arXiv (Atom API + RSS)T1observed 35 min agohigh
Primary category: cs.LG
Source:arXiv (Atom API + RSS)T1observed 35 min agohigh
Published: 11 Sept 2026
Source:arXiv (Atom API + RSS)T1observed 35 min agohigh

Each value shows its source, tier and observation time. Conflicting claims are kept side by side and flagged — never averaged. How AI Atlas records facts →

Provenance

Attributed facts

9

Source tiers

T19

Freshest observation

35 min ago

Conflicts

None

No models linked to this paper yet.

Authors: Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser

As of

Rewind the record: see this entity's attributes exactly as AI Atlas knew them on a given day.

Claim history · Arxiv announce type

1 claims · 1 propertiesShow all properties

Arxiv announce typearxiv_announce_type1

Claim history for Arxiv announce type
Value	Valid from → to	Status	Source	Confidence	Extractor
new	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Claims are temporal and append-only: a new observation closes the previous claim (valid_to) instead of overwriting it. Conflicting claims from different sources are kept side by side and flagged — never averaged. Methodology →

11 Sept 2026
New paperPaperHierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
New paper: Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
arxiv
rss.arxiv.org

Full timeline →

Source documents
Source	Document	Type	Tier	Last observed	Snapshots
arXiv (Atom API + RSS)	rss.arxiv.org/rss/cs.LG	feed	T1· Official	35 min ago	1

Tier 1 = official/primary, 2 = quality secondary, 3 = community, 4 = unverified. Every snapshot is archived; see all sources and the methodology.