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

1 Introduction

• Hierarchical clustering admits uncountably many methods satisfying the three axioms, including well-separated-cluster and non-binary single-linkage constructions, while several other linkage variants fail.The admissible methods form a diverse refinement poset with no greatest element, yet every method and every finite collection share a sufficiently well-separated-cluster backbone.Source: §1 · p. 3

1.1 Definitions and Notation

• The framework uses finite dissimilarity-based item sets and unweighted hierarchies, extending flat clustering’s axiomatic setting to nested cluster structures.Hierarchical outputs retain nested clusters rather than merge heights, while exactness on ultrametrics defines a strongly admissible class that remains uncountable and has a least refinement element.Source: §1 · pp. 2–4, §1.1 · p. 4

1.2 Structure of the Paper

• The paper states axioms and achievability results, constructs methods, studies admissible-method structure, adds ultrametric exactness, analyzes preprocessing, reviews related work, and concludes.Omitted proofs and technical lemmas appear in the Appendix.Source: §1.2 · p. 4

1.3 Use of Large Language Models (LLM)

• The authors report using GPT-5.6 Sol for clarity, drafting assistance, minor corrections, and numerical simulations, while retaining responsibility for the mathematical content and verification.LLM-developed proof techniques were limited to Proposition 11, Lemmas 13 and 52, and Proposition 37(iv).Source: §1.3 · p. 4

2.1 Kleinberg’s Impossibility Theorem for Flat Clustering

• Kleinberg proved that no flat clustering method can simultaneously satisfy scale invariance, richness, and consistency.These axioms require invariance to positive rescaling, surjectivity over partitions, and stability under strengthening.Source: §2.1 · p. 5

2.2 Achievability of Hierarchical Clustering

• Hierarchical clustering outputs nested clusters, and its admissibility axioms require scale invariance, partition richness, partition consistency, and permutation invariance.A hierarchy is a laminar family containing the full dataset and every singleton; permutation invariance ensures outputs do not depend on point labels.Source: §2.2 · pp. 5–6
• Unlike flat clustering, hierarchical clustering admits methods satisfying the canonical axiom system αadm, with uncountably many admissible methods existing.The result is constructive, and the paper next gives explicit examples of admissible hierarchical clustering methods.Source: §2.2 · pp. 6–7

3.1 Linkage Methods

• Non-binary single linkage is admissible, whereas non-binary complete, average, Ward, centroid, and median linkage each violate at least one axiom.Binary hierarchies are incompatible with permutation invariance, motivating simultaneous merges of all tied clusters.Source: §3.1 · pp. 7–8

3.2 Separation Methods

• Two admissible separation-method families identify clusters whose internal dissimilarities are sufficiently smaller than cross-cluster dissimilarities, using global or local reference-point comparisons.The global family enforces worst-case comparisons over pairs of points, while the local family sets the two reference points equal; both yield admissible hierarchies.Source: §3.2 · pp. 8–9
• Separation margins control sensitivity: higher values detect clusters with separability closer to one but make the methods more susceptible to noise.For example, an arbitrarily small decrease in one dissimilarity can create a cluster under Tglob, while a lower margin can exclude it.Source: §3.2 · p. 9

3.3 Bryant-Berry Stable Clusters

• The Bryant–Berry stable-cluster method and every power-transformation variant T_stable^(p) for p > 0 are admissible.Stable clusters form a laminar hierarchy, but deciding stability is NP-hard in general; their family is contained in the average-linkage hierarchy.Source: §3.3 · p. 10

4.1.1 Refinement: A Partial Order on Hierarchical Clustering Methods

• Admissible methods are ordered by refinement, where one method is finer when it returns a hierarchy containing the other method’s clusters for every dissimilarity.This refinement relation is a partial order on both all hierarchical methods and the admissible subclass.Source: §4.1.1 · p. 11

4.1.3 Diversity of Admissible Methods

• The admissible-method poset has uncountable height, width, and cellularity, and no greatest element because uncountably many admissible methods are pairwise incompatible.Thus no universal admissible method refines all others, and some pairs lack any common refinement even among all hierarchical methods.Source: §4.1.3 · p. 12

4.2 Uniformity: A Well-separated Backbone

• Every admissible method refines a globally well-separated hierarchy for some method-dependent separation margin sequence.Consequently, admissible methods share a nontrivial conservative cluster backbone despite disagreeing on individual clusters.Source: §4.2 · p. 13
• Every finite collection of admissible methods has a common admissible lower bound, obtained by taking the pointwise minimum of their separation-margin sequences.This finite-family uniformity does not extend to the entire admissible class, whose infimum is the non-admissible trivial method containing only the root and singleton leaves.Source: §4.2 · pp. 13–14
• The common-backbone result upgrades partition richness to hierarchical richness: every hierarchy can occur within some admissible method’s output for a suitable dissimilarity.This follows because each admissible method refines a globally separated hierarchy and that hierarchy ranges over all hierarchies.Source: §4.2 · p. 14

4.3.1 Intersection and Union of Methods

• Intersections of admissible methods remain admissible for finite families, while unions remain admissible for upward-directed families; therefore the admissible poset is a meet-semilattice but not a join-semilattice.Arbitrary unions are hierarchy-valued only when the methods are pairwise compatible, and infinite intersections can collapse to the non-admissible trivial method.Source: §4.3.1 · p. 15

4.3.2 Existence of Maximal Admissible Methods

• Maximal admissible methods exist, every admissible method is refined by at least one, and uncountably many maximal methods are pairwise incompatible.Zorn’s lemma supplies maximal extensions through unions of chains, while incompatibility prevents a universal maximal method.Source: §4.3.2 · pp. 15–16

5.1 Exactness on Ultrametric Inputs

• Exactness on ultrametrics yields uncountably many strongly admissible methods, with Tglob as the least method under refinement and the backbone and maximality results preserved.The strongly admissible class has uncountable height, width, and cellularity, including TSL, Tglob, Tloc, and Tstable^(p) for every p > 0.Source: §5.1 · pp. 17–18

5.2.1 General Preservation Principles

• A transformation preserves an axiom when composing it with every method satisfying that axiom preserves the property; sufficient conditions cover scaling, richness, consistency, permutations, and ultrametric exactness.For pointwise transformations µg, strict monotonicity preserves consistency and exactness, surjectivity preserves richness, and homogeneous scaling preserves scale invariance; power transformations preserve all listed axioms.Source: §5.2.1 · pp. 18–19

5.2.2 Examples and Applications

• Single linkage exactly factors as TSL = Tglob ∘ B*, where B* is the minimax-path ultrametric, and this factorization transfers scale invariance, permutation invariance, and ultrametric exactness.The same representation can use any method exact on ultrametric inputs, including Tloc and Tstable.Source: §5.2.2 · pp. 19–20
• PCA preprocessing preserves scale and permutation invariance under unique-subspace and distinct-projection assumptions, but may fail consistency, richness, and ultrametric exactness.Projection collisions can produce pseudodissimilarities, particularly for highly symmetric configurations, making the chosen dimension unsuitable when dissimilarity-valued output is required.Source: §5.2.2 · p. 20
• Mutual-reachability preprocessing in HDBSCAN preserves scale and permutation invariance, while Gaussian-kernel preprocessing converts dissimilarity strengthenings into corresponding similarity strengthenings and commutes with permutations.The Gaussian-kernel example lies outside the dissimilarity-valued framework and therefore uses the analogous similarity axioms.Source: §5.2.2 · p. 21

• Earlier responses to Kleinberg’s impossibility relax the framework by changing axioms, inputs, or problem formulations, whereas this paper changes only the output form to a hierarchy.Examples include restricting the number of clusters, weakening consistency, limiting allowed transformations, or extending the setting to graphs.Source: §6 · p. 21
• Other related frameworks address asymmetric networks through hierarchical quasi-clustering or characterize broader admissible method families under different axioms.Carlsson et al. (2014) obtain a uniqueness result, while Carlsson et al. (2017) characterize broader families for asymmetric networks.Source: §6 · p. 22
• The paper differs from earlier hierarchical characterizations by retaining Kleinberg-like requirements while admitting diverse methods whose refinement structure is central.Carlsson and Mémoli characterize single linkage through normalization, separation, and functoriality, while the present framework concerns unweighted hierarchies on a fixed ground set; linkage work instead characterizes methods through locality and outer consistency.Source: §6 · p. 22
• The paper studies methods mapping pairwise dissimilarities to hierarchies, unlike objective-function frameworks that axiomatize how a hierarchy should be scored.Dasgupta (2016) and Cohen-Addad et al. (2019) characterize hierarchical clustering objectives rather than the behavior of the clustering map itself.Source: §6 · pp. 22–23
• Population-level approaches define or extend hierarchies from probability measures, density topology, or user-specified elementary-measure clusterings rather than constraining dissimilarity-to-hierarchy methods.Thomann et al. (2015) study unique extensions under additivity and continuity, while Arias-Castro and Coda (2025) characterize density-based cluster trees and recover Hartigan’s cluster tree under suitable conditions.Source: §6 · pp. 22–23

7 Conclusion

• Hierarchical analogs of scale invariance, richness, and consistency are jointly satisfiable, yielding uncountably many admissible hierarchical clustering methods.Admissible methods form a highly diverse refinement poset, yet every method contains sufficiently well-separated clusters and every finite collection shares a nontrivial backbone.Source: §7 · p. 23
• Admissible methods also support ultrametric exactness and preprocessing transformations under conditions that preserve the axioms, while open questions concern maximal methods and stronger axioms.Hierarchy-based outputs remain richer than flat partitions, but any cut-selection rule still inherits Kleinberg’s impossibility constraints.Source: §7 · pp. 23–24

Appendix A. Alternative Axioms and Robustness

• Appendix A formalizes requirements and shows that the canonical system combines scale invariance, partition richness, partition consistency, and permutation invariance, with ultrametric exactness defining strong admissibility.Its comparison framework studies logical implication, equivalence, conjunction, and structural closure properties across alternative axioms.Source: Appendix A · p. 24

A.1.1 Order invariance

• Order invariance strengthens scale invariance by requiring outputs to depend only on pairwise-dissimilarity orderings under strictly increasing transformations.The appendix defines this requirement and places it among the alternative axioms summarized in Table 1.Source: §A.1.1 · p. 24, Table 1 · p. 25

A.1.2 Richness variants

• Richness variants range from realizing individual clusters to realizing complete hierarchies, with ultrametric refinement providing an alternative richness requirement to ultrametric exactness.The implication chain is αsuhr ⇒ αshr ⇒ αhr ⇒ αpr ⇒ αcwr, alongside αsuhr ⇒ αuhr ⇒ αhr.Source: §A.1.2 · pp. 25–26, §A.2 · p. 26

A.1.3 Consistency variants

• Consistency variants define cluster-wise and hierarchical preservation under contractions and expansions, while absence consistency is the contrapositive of partition consistency.Hierarchical consistency is equivalent to cluster-wise consistency and implies partition consistency.Source: §A.1.3 · p. 26, §A.2 · p. 27

A.2 Relations Among the Axioms

• The axiom relations collapse richness variants: under suitable scale-invariance and consistency assumptions, partition richness, hierarchical richness, and the backbone property become equivalent.Proposition 32 establishes two such equivalence chains, including one using cluster-wise richness and consistency.Source: §A.2 · pp. 26–27
• The canonical axiom system therefore admits an equivalent positive-margin backbone formulation, which is useful because backbone properties behave better under intersections than partition richness.This equivalence supports the appendix’s structural closure results and Lemma 20(i).Source: §A.2 · p. 27

A.3 Robustness of the Structural Results

• Closure principles preserve invariance, ultrametric, richness, consistency, and backbone requirements under specified intersections and unions, yielding closure of canonical admissible methods under intersections and upward-directed unions.Strict hierarchical richness is not generally preserved by compatible unions, whereas non-strict richness is; finite conjunctions inherit any closure property shared by their component requirements.Source: §A.3 · pp. 28–29
• Under alternative axiom systems, achievability, maximal extensions, finite intersections, and least-element results persist under stated conditions, while order invariance changes the admissible class from uncountably diverse to finite.The class contains Tglob, Tloc, and TSL; maximal extensions and finite-intersection closure require the listed richness, backbone, or ultrametric conditions, and Tglob is least when the unit-backbone property is required.Source: §A.3 · p. 30

Appendix B. Relational Properties and Axiom-Preserving Transformations

• Relational properties encode axioms through an input relation on dissimilarities and an output relation on hierarchies, and any transformation preserving the input relation preserves the axiom.If an axiom is a conjunction of relational properties, preservation of every component preserves the conjunction; partition richness instead relies on surjectivity.Source: Appendix B · p. 32, §B.1 · pp. 32–33

B.2 Relational Formulations of the Axioms

• Scale invariance is relational with input pairs (d, βd) for β > 0 and diagonal output relation, yielding T(βd) = T(d); order invariance is likewise relational.These representations identify the input structure that preprocessing must preserve for the corresponding axiom.Source: §B.2 · p. 33
• Order invariance is represented relationally using strictly increasing transformations of dissimilarities that preserve the required hierarchy relation.Source: §B.2 · p. 33
• Permutation invariance is expressed by requiring the output hierarchy to transform according to the same permutation applied to the input.Source: §B.2 · p. 33
• Cluster-wise consistency, hierarchical consistency, and absence consistency admit relational representations, with hierarchical and absence consistency equivalent to conjunctions of relational properties.Source: §B.2 · pp. 33–34
• The resulting representations establish the corresponding relational-class entries, including that the combined admissibility property αadm+ belongs to γrp.Source: §B.2 · p. 34

B.3 Applications to Axiom-Preserving Transformations

• More generally, strictly increasing transformations preserve partition consistency and exactness on ultrametrics, while surjective transformations preserve partition richness and suitable homogeneous transformations preserve scale invariance.For strictly increasing g, µ_g(u) is an ultrametric and induces the same hierarchy as u; additional surjectivity and homogeneity conditions provide richness and scale preservation.Source: §B.3 · pp. 34–35
• Power transformations d ↦ d^p, for p > 0, preserve all five properties and therefore preserve both admissibility and strong admissibility.The result follows because the transformation satisfies the required order, consistency, exactness, richness, and scale conditions.Source: §B.3 · p. 35

Appendix C. Proofs for Section 3 (Admissible Methods)

• The appendix establishes stronger axiom requirements for several methods, including T_SL, T_glob, and T_loc in H_ord^cwc^adm+ and T_stable in H_cwc^adm+.These stronger requirements are used when proving the properties of the methods introduced in Section 3.Source: Appendix C · p. 35

C.1.1 Single linkage and minimum spanning tree

• Single linkage’s minimum bottleneck B*(d) can be computed from a minimum spanning tree: B*(d)(x,y) is the largest edge weight on the tree path between x and y.The minimum bottleneck is characterized by the unique path in any minimum spanning tree of the complete weighted graph.Source: §C.1.1 · pp. 35–36
• For every dissimilarity d, B*(d) is an ultrametric and T_SL(d) equals Ψ_B*(d), with level-r clusters given by connected components of the graph containing edges of weight at most r.Thus single linkage admits the standard minimax-path characterization.Source: §C.1.1 · p. 36

C.1.2 Properties of Single Linkage

• The minimax map preserves order invariance, exactness on ultrametrics, permutation invariance, and cluster-wise consistency, so the corresponding single-linkage properties follow.Strictly increasing transformations commute with B*, while strengthening preserves connectivity within clusters and prevents newly formed links across cluster boundaries.Source: §C.1.2 · pp. 36–37

C.2.1 Definitions of the Linkage Methods Considered

• The non-binary linkage procedure repeatedly merges all connected components formed by active-cluster pairs attaining the minimum linkage dissimilarity.Ties are handled transitively: if C1 ties with C2 and C2 ties with C3, all three are merged even when C1 and C3 are not directly tied.Source: §C.2.1 · p. 37
• The considered linkage rules use Lance–Williams updates, restrict Ward and Centroid linkages to squared Euclidean dissimilarities, and require deterministic tie-breaking when multiway updates depend on merge order.The tie-breaking convention makes the hierarchical method well-defined and does not affect the stated counterexamples because their relevant comparisons are strict.Source: §C.2.1 · pp. 37–38, Table 2 · p. 38

C.2.2 Non-admissibility of the Other Linkage Methods

• Complete, unweighted and weighted average, Ward, centroid, and median linkages are non-admissible because they fail partition consistency.The result holds regardless of the tie-breaking rule.Source: §C.2.2 · p. 38
• A C-strengthening can change the hierarchy so that A belongs to T(d) but not T(d1), directly violating partition consistency.The construction uses squared Euclidean dissimilarities d and d1 and has C contained in T(d).Source: §C.2.2 · pp. 38–39
• Under d, the linkage rules first merge {2,3} and then form A, whereas under d1 they merge {1,2} and then {3,4}.These differing merge sequences establish the required inconsistency counterexample.Source: §C.2.2 · p. 38
• Because all comparisons in the counterexample are strict, non-admissibility is independent of the tie-breaking convention.The conclusion applies to each of the six linkage rules considered.Source: §C.2.2 · p. 39

C.3 Separation Methods: Proof of Proposition 10

• For every separation-margin sequence η, the resulting hierarchical clustering method is admissible, satisfying scale invariance, cluster-wise consistency, permutation invariance, and hierarchical richness.The proof uses cluster-wise consistency and strict hierarchical richness to obtain the corresponding partition properties.Source: §C.3 · p. 39
• Distinct separation-margin sequences define distinct admissible methods, yielding an uncountable family; unit-margin methods additionally have ultrametric exactness and order invariance.These stronger properties are recorded separately from the admissibility proof.Source: §C.3 · p. 39

Basic properties

• For every separation margin sequence η, T^η_loc is a hierarchical clustering method satisfying the required conditions, and the analogous global construction is obtained similarly.The proof uses laminarity, together with inclusion of the root X and all singleton leaves; T_loc is identified as a known hierarchical clustering method.Source: §C.3.1 · p. 39
• Distinct separation margin sequences induce distinct methods: if η ≠ η′, some dissimilarity yields a cluster included by one construction but not the other.Choosing a subset C whose size matches a differing sequence coordinate and assigning within-group dissimilarity r separates the two outputs.Source: §C.3.1 · pp. 40–41
• η = 1 is equivalent to T^η_loc and T^η_glob exactly matching the ultrametric hierarchy on every ultrametric input.When η ≠ 1, an ultrametric containing a cluster at a level between η_s and 1 shows that neither method is exact.Source: §C.3.1 · pp. 40–41
• Every hierarchy can be realized exactly by T^η_loc for a sufficiently small positive scale q below the minimum separation margin.The construction assigns exponentially decreasing heights to clusters according to tree depth, producing an ultrametric whose selected clusters are precisely the target hierarchy.Source: §C.3.1 · p. 41
• T^η_loc is order-invariant under strictly increasing transformations of dissimilarities exactly when η = 1.For η = 1, strict within-cluster versus cross-cluster inequalities are preserved by any strictly increasing transformation; for η ≠ 1, a constructed transformation changes cluster membership.Source: §C.3.1 · pp. 41–42

C.4 Bryant-Berry Stable Clusters: Proof of Proposition 11

• Positive power transformations preserve strong admissibility, so Tstable and every power-transformed variant are admissible.The result holds for every p > 0.Source: §C.4 · p. 42
• Tstable is strongly admissible because it is hierarchical and satisfies scale invariance, exactness on ultrametrics, cluster-wise consistency, and permutation invariance.This establishes the core claim needed for Proposition 11.Source: §C.4 · p. 42
• Tstable is a hierarchy because Bryant–Berry stable clusters form a laminar family, augmented with the root X and all singleton clusters.This supplies the structural part of the hierarchical clustering method definition.Source: §C.4 · p. 42
• Scale invariance holds because scaling dissimilarities by β > 0 scales every stability value by β without changing which clusters have positive stability.Thus Tstable(βd) = Tstable(d).Source: §C.4 · p. 43
• On ultrametrics, every stable cluster is an ultrametric ball, so Tstable exactly recovers the hierarchy Ψu.The proof shows external points are equidistant from the cluster and internal dissimilarities are strictly smaller, yielding the ball representation.Source: §C.4 · p. 43
• Cluster-wise consistency follows because a strengthening preserves each cluster’s positive stability: ιd1(C) ≥ ιd(C) > 0.Within-cluster dissimilarities decrease while between-cluster dissimilarities increase, so every admissible triplet’s separation score cannot decrease.Source: §C.4 · pp. 43–44
• Permutation invariance holds because relabeling bijects the admissible triples used to compute each cluster’s stability.Therefore the stability of ϕ(C) under dϕ equals the stability of C under d.Source: §C.4 · p. 44

D.1 Incompatibility among Methods

• For every 0 < p < q, T_stable^(p) and T_stable^(q) are mutually incompatible, because they can output overlapping, non-laminar clusters.The construction uses four points and extends to any domain with at least four points.Source: §D.1 · pp. 44–45
• No hierarchy can contain both C1 = {1,2,3} and C2 = {2,3,4}, since they overlap without either containing the other.Such clusters violate laminarity, so no common refinement can include both.Source: §D.1 · p. 44
• The incompatibility of T_stable^(p) and T_stable^(q) is witnessed by a dissimilarity whose ordering satisfies ε < 1 < t < h < M.Under this construction, C1 belongs to T_stable^(p) while C2 belongs to T_stable^(q).Source: §D.1 · p. 44
• For the displayed parameter d0, single linkage TSL and T_stable^(p) are incompatible because their clusters overlap without either containing the other.Source: §D.1 · p. 45
• The single-linkage incompatibility persists after transforming d0 by d(x,y) = d0(x,y)^(1/p), because single linkage is order invariant while T_stable^(p) depends on the transformed metric.The same two non-laminar clusters therefore remain in the union of the methods’ outputs.Source: §D.1 · p. 45
• The TSL versus T_stable^(p) incompatibility extends to every n ≥ 4 by assigning large distances to added points.The original single-linkage cluster remains unchanged, while the positive isolation-weight condition for the stable cluster is preserved.Source: §D.1 · p. 45

D.2.1 Proof of Theorem 15

• The key cluster-wise lemma transfers selection from a reference dissimilarity to any strengthening that decreases within-C dissimilarities and increases cross-cut dissimilarities.The proof constructs an intermediate dissimilarity and uses partition consistency twice to preserve the partition containing C and singleton blocks.Source: §D.2.1 · pp. 45–46
• If a cluster C is sufficiently well separated from its complement, every method satisfying scale invariance, partition richness, and partition consistency selects C.Lemma 54 establishes an η_C > 0 such that ϱ(d, C) < η_C implies C ∈ T(d).Source: §D.2.1 · p. 46
• For permutation-invariant methods, the separation threshold depends only on |C|, yielding a margin sequence η_s with 0 < η_s ≤ 1.The upper bound follows because larger thresholds would force overlapping, incomparable clusters into one laminar hierarchy under uniform dissimilarity.Source: §D.2.1 · pp. 46–47
• The resulting global well-separated hierarchy T^η_glob is contained in every admissible method T.Every non-singleton proper cluster in T^η_glob satisfies the corresponding separation margin, while roots and singletons occur in both hierarchies.Source: §D.2.1 · p. 46

D.3 Additional Lemmas

• Any method satisfying ultrametric refinement and partition consistency also contains T^η_glob.For a cluster in T^η_glob, an auxiliary ultrametric makes the cluster an ultrametric ball; strengthening back to the original dissimilarity then preserves it.Source: §D.3 · p. 48
• For admissible order-invariant methods, a strictly increasing transformation g can amplify dissimilarity gaps so that T^η_glob(d) is contained in T^η_glob(g ∘ d).Choosing g(δ_i)=q^i with q > 1/η_min ensures every globally well-separated cluster meets the relevant margin after transformation.Source: §D.3 · p. 48
• Order invariance then transfers the transformed-hierarchy containment back to the original dissimilarity, proving T^η_glob ⊆ T.The conclusion holds for every dissimilarity d because T(g ∘ d)=T(d).Source: §D.3 · p. 48

• The evaluation covers Iris, Wine, Breast Cancer, and Digits after removing exact duplicate feature vectors and standardizing each feature.Euclidean dissimilarities are used throughout.Source: Appendix E · pp. 48–49
• The reported ratio compares the number of nontrivial clusters returned by Tglob with those returned by TSL, the non-binary single-linkage hierarchy.Only clusters satisfying 1 < |C| < n are counted.Source: Appendix E · p. 49, Table 3 · p. 49
• Approximately 19%–29% of nontrivial single-linkage clusters are retained by Tglob across the datasets, with 23.0% retained in aggregate.These results show that the backbone is nontrivial on the evaluated examples.Source: Table 3 · p. 49, Appendix E · p. 49