PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

arXiv:2609.11173v1cs.LGstat.MEstat.ML

TL;DR

The paper asks whether Kleinberg’s impossibility for flat clustering persists when outputs are hierarchies. It defines and constructs hierarchical methods satisfying analogous axioms, finding uncountably many admissible methods with both substantial diversity and a shared well-separated backbone.

  • Problem

    Kleinberg’s theorem leaves open whether scale invariance, richness, and consistency can coexist when clustering outputs are hierarchies rather than flat partitions.

  • Method

    The paper defines hierarchical analogs of the axioms, constructs admissible methods, and studies their refinement order and well-separated backbone structure.

  • Results

    Uncountably many admissible hierarchical methods exist, forming a diverse class with no greatest element while sharing a nontrivial common backbone of sufficiently well-separated clusters.

  • Takeaways & Limitations

    Hierarchical outputs jointly accommodate the three axioms while allowing freedom in additional clusters and enforcing a common conservative structure.

  • Takeaways & Limitations

    Any downstream procedure that must return a flat partition still requires a cut-selection rule, and Kleinberg’s theorem applies to that induced flat method.

Abstract

from arXiv · show

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.

1 Introduction

Clustering is underdetermined, and Kleinberg’s theorem shows that flat methods cannot jointly satisfy scale invariance, richness, and consistency. This paper asks whether hierarchies avoid that impossibility and finds many admissible methods, while retaining substantial diversity and a shared well-separated backbone.

  • Flat clustering lacks a universally accepted cluster definition, motivating axiomatic frameworks for comparing desirable properties.
  • Kleinberg’s theorem rules out any flat method that simultaneously satisfies scale invariance, richness, and consistency.
  • Hierarchies can preserve a cluster while also representing newly revealed, properly nested subclusters after dissimilarities are strengthened.
  • The hierarchical analogs of the axioms are jointly satisfiable, with uncountably many admissible methods including well-separated-cluster and non-binary single-linkage constructions.
  • Admissible methods form a diverse refinement-ordered family with no greatest element, yet every method and every finite collection share a sufficiently well-separated backbone.
  • Exactness on ultrametrics preserves uncountable diversity and backbone phenomena while adding a least element, and preprocessing transformations are analyzed for axiom preservation.

2 From Impossibility to Achievability

The paper recalls Kleinberg’s flat impossibility result and defines hierarchical analogs of its axioms for methods returning nested clusters. It then proves achievability, including uncountably many admissible methods constructed through explicit examples.

  • Kleinberg’s flat axioms require scale invariance, richness, and consistency, but no flat method satisfies all three simultaneously.
  • A hierarchical method maps dissimilarities to a hierarchy represented by nested clusters, rather than to one partition.
  • The hierarchical axiom system adds permutation invariance to scale invariance, partition richness, and partition consistency.
  • Theorem 6 proves that uncountably many admissible hierarchical methods exist.
  • The achievability proof is constructive, with explicit admissible methods developed afterward.

3 Explicit Construction of Admissible Methods

The paper constructs admissible hierarchical clustering methods from non-binary linkage rules, separation conditions, and stable clusters. Non-binary single linkage and Bryant–Berry stable clusters are admissible, while several other classical linkage variants are not.

  • 3.1 Linkage Methods: Non-binary single linkage is admissible, whereas non-binary complete, average, Ward, centroid, and median linkage violate at least one axiom.Allowing simultaneous merges resolves the incompatibility between binary output and permutation invariance.
  • 3.2 Separation Methods: Separation-based methods declare clusters when within-cluster dissimilarities are sufficiently smaller than cross-cluster dissimilarities, producing hierarchies directly from the dissimilarity.Global and local families differ in whether comparisons use arbitrary reference points or the same reference point.
  • 3.2 Separation Methods: The separation margins control sensitivity: larger margins detect closer-to-one separabilities but become more vulnerable to noise.A tiny decrease in one dissimilarity can create a cluster under a sufficiently sensitive margin.
  • 3.3 Bryant-Berry Stable Clusters: The Bryant–Berry construction defines stable clusters through positive average isolation weights, and its stable-cluster family forms a hierarchy.Computing stability is NP-hard, while the stable-cluster family is contained in the average-linkage hierarchy.
  • 3.3 Bryant-Berry Stable Clusters: The paper explicitly establishes admissibility for the Bryant–Berry stable-cluster method and for its composed variants.These constructions provide admissible methods beyond separation-based and linkage-based approaches.

4 The Structure of the Set of Admissible Methods

The admissible methods form a highly diverse partially ordered set under refinement, yet share a structured backbone. There is no greatest method, but every finite family has a common well-separated lower-bound hierarchy and every method extends to a maximal one.

  • 4.3 Intersection and Union of Methods: Refinement defines a partial order on hierarchical methods, and the admissible class is closed under finite intersections but not generally under infinite intersections.Finite intersections yield admissible common lower bounds, whereas an infinite intersection can reduce to the non-admissible trivial method.
  • 4.1 The Diversity of Admissible Methods: The admissible class has uncountable height, width, and cellularity, with uncountably many pairwise-incompatible methods and no greatest element.Thus no universal admissible method refines all other admissible methods.
  • 4.2 Uniformity: A Well-separated Backbone: Every admissible method refines a hierarchy of sufficiently well-separated clusters, and every finite collection shares such a common backbone.The shared backbone uses a separation-margin sequence obtained from the individual methods’ sequences.
  • 4.3 Intersection and Union of Methods: The admissible class has no least element: its infimum is the trivial root-and-leaves method, which fails partition richness.The infimum exists in the larger poset of all hierarchical methods but is not itself admissible.
  • 4.3.2 Existence of Maximal Admissible Methods: Maximal admissible methods exist, every admissible method is refined by one, and uncountably many maximal methods are pairwise incompatible.This contrasts with the absence of a greatest admissible method.

5 Extensions of the Canonical Framework

The paper extends the framework with exactness on ultrametric inputs and studies preprocessing transformations, showing that strong admissibility remains highly diverse while gaining a least element.

  • 5.1 Exactness on Ultrametric Inputs: Exactness requires recovering the canonical hierarchy induced by every ultrametric input, without requiring its associated heights.Ultrametric distances and dendrograms have a one-to-one correspondence, motivating this fidelity requirement.
  • 5.1 Exactness on Ultrametric Inputs: The strongly admissible class remains uncountable and retains uncountably many incompatible maximal elements and the backbone property.Theorem 23 also identifies TSL, Tglob, Tloc, and T^(p)stable as strongly admissible methods.
  • 5.1 Exactness on Ultrametric Inputs: Unlike the canonical admissible class, strongly admissible methods have a least element, Tglob, which is the coarsest method under refinement.Every strongly admissible method refines Tglob, whose hierarchy can contain many non-singleton clusters.
  • 5.2 Preprocessing Transformations: Preprocessing is modeled by composing a hierarchical method T with a transformation µ that first changes the dissimilarity and then constructs the hierarchy.The framework asks when transformations preserve axioms for every method satisfying them.
  • 5.2 Preprocessing Transformations: Sufficient preservation conditions require transformations to maintain the input relations relevant to scale, richness, consistency, permutation invariance, and ultrametric exactness.These conditions preserve scaling, strengthenings, relabelings, or canonical ultrametric hierarchies as appropriate.
  • 5.2 Preprocessing Transformations: Power transformations preserve both admissibility and strong admissibility, while PCA preprocessing preserves permutation invariance but need not preserve the remaining axioms.PCA can fail to preserve strengthenings, richness, or ultrametric exactness, and may yield a pseudodissimilarity when projections collide.

6 Related Work

Related work studies axiomatic clustering through alternative outputs, structural constraints, objective functions, population models, and asymmetric dissimilarities. This paper instead keeps Kleinberg-like input-to-hierarchy axioms and emphasizes the resulting diversity under refinement.

  • Ways prior work modifies the problem: Other research modifies the axioms, adds the desired number of clusters, studies clustering-quality functions, or optimizes hierarchical-clustering objectives to bypass Kleinberg’s impossibility.These lines include quality-function axioms, prescribed cluster counts, and cost-based formulations.
  • Hierarchical axiomatic frameworks: Earlier hierarchical frameworks characterize particular methods using dendrograms, ultrametrics, functoriality, normalization, separation, locality, or outer consistency.These approaches retain more numerical or structural information than the unweighted hierarchies studied here.
  • Asymmetric dissimilarities: Related work also develops axiomatic frameworks for asymmetric networks, including uniqueness results and broader families of admissible hierarchical methods.These studies address hierarchical quasi-clustering and asymmetric dissimilarities.
  • Population-level perspectives: Population-level approaches axiomatize hierarchies of probability measures or density structures rather than maps from pairwise dissimilarities to hierarchies.Their objects of study and inputs therefore differ from this paper’s framework.
  • Positioning of this framework: This paper maps pairwise dissimilarities to unweighted hierarchies and constrains behavior under rescaling, strengthening, relabeling, and realizability of hierarchical structures.Its axioms impose fewer structural constraints than dendrogram-based formulations.

7 Conclusion

The paper shows that hierarchical outputs remove Kleinberg’s flat-clustering incompatibility while admitting a large but structured family of methods. Extensions preserve this picture, but open questions and cut-selection limits remain.

  • Main conclusion: Hierarchical analogs of scale invariance, richness, and consistency are jointly satisfiable, with uncountably many admissible methods.This contrasts with Kleinberg’s impossibility theorem for flat clustering.
  • Structure of admissible methods: Under refinement, admissible methods form a highly complex poset with uncountable height, width, and cellularity, no greatest or least element, and uncountably many incompatible maximal elements.Despite this diversity, every method contains sufficiently well-separated clusters and finite collections share a common backbone.
  • Extensions: Exactness on ultrametric inputs preserves the main structural picture while strengthening the connection between dissimilarities and their canonical hierarchies.The paper also identifies preprocessing conditions that preserve axioms under composition.
  • Open questions: Open questions include identifying other and explicit maximal admissible methods and determining which additional axioms meaningfully reduce the admissible class.Ultrametric exactness is one step toward this goal because it yields a least strongly admissible method.
  • Limitations and future directions: A hierarchy avoids specifying the number of clusters in advance, but downstream tasks needing a flat partition still require a cut-selection rule.Kleinberg’s theorem implies that no such rule can simultaneously satisfy scale invariance, richness, and consistency.

A.3 Robustness of the Structural Results

The paper shows that structural results persist across alternative axiom systems, while their order-theoretic diversity depends strongly on whether order invariance is required. Closure properties also yield common backbones and least or maximal elements under specified conditions.

  • Closure properties: Finite intersections, upward-directed unions, and compatible unions preserve many invariance, richness, consistency, ultrametric, and backbone requirements.Strict hierarchical richness is the main stated exception for compatible unions because extra clusters can prevent exact realization of a prescribed hierarchy.
  • Closure properties: The canonical admissible class is closed under arbitrary nonempty intersections and nonempty upward-directed unions.Strong admissibility additionally remains closed under arbitrary nonempty intersections and directed unions.
  • Robustness under alternative axioms: For any conjunction of the introduced axioms, admissible methods exist, including Tglob, Tloc, and TSL; maximal extensions exist under stated richness or ultrametric-exactness conditions.The same result also gives finite-intersection closure when strict hierarchical richness is absent or exactness on ultrametrics is required.
  • Diversity versus order invariance: Without order invariance, method classes have uncountable height, width, and cellularity; with order invariance, every such class is finite.The finite case follows because order-invariant methods are constant on finitely many equivalence classes of dissimilarities.
  • Least elements: When the unit-backbone requirement is included, Tglob is the least element of the resulting refinement poset.Every method in the class refines Tglob, and Tglob itself belongs to the class.

B.3 Applications to Axiom-Preserving Transformations

The paper analyzes transformations of dissimilarities and establishes conditions under which they preserve clustering axioms and the single-linkage construction. Minimum spanning trees provide an equivalent computational characterization of the bottleneck ultrametric.

  • Axiom-preserving transformations: Power transformations g(t)=t^p with p>0 preserve admissibility and strong admissibility.They preserve the five analyzed properties, including scale invariance, richness, consistency, permutation invariance, and exactness on ultrametrics.
  • The minimax map: B*(d)(x,y) can be computed from a minimum spanning tree as the largest edge weight on the unique tree path between x and y.This gives a direct computational route from the complete weighted graph to the single-linkage hierarchy.
  • The minimax map: The bottleneck dissimilarity B*(d) is an ultrametric, and TSL(d) equals the hierarchy of B*(d).At level r, the clusters are the connected components of the graph containing edges with d(x,y)≤r.
  • The minimax map: Strictly increasing transformations preserve order invariance for the minimax bottleneck map because B*(g∘d)=g∘B*(d).The same transformation also preserves exactness on ultrametrics for the bottleneck-based construction.
  • Non-binary linkage methods: Non-binary linkage procedures merge every connected component of tied minimum inter-cluster dissimilarities simultaneously.This tie rule is defined over the graph of active clusters whose pairwise linkage value equals the current minimum.

C.2.2 Non-admissibility of the Other Linkage Methods

The paper proves that several classical non-binary linkage methods are not admissible because they violate partition consistency, including complete, average, Ward, centroid, and median variants.

  • Consistency failures: Complete, unweighted and weighted average, Ward, centroid, and median linkages do not satisfy partition consistency and therefore are not admissible.The conclusion holds regardless of the tie-breaking rule.
  • Consistency failures: Under a carefully constructed strengthening of the dissimilarity, each tested linkage can include a cluster under d but exclude it under d1.The construction uses four distinguished points, auxiliary points at distance 100, and squared Euclidean dissimilarities for the relevant parameter values.
  • Consistency failures: All comparisons in the counterexamples are strict, so the violations do not depend on how ties are broken.This removes tie-breaking as an alternative explanation for the failures.

C.3.1 Basic properties

Separation-based hierarchical methods are admissible for every separation-margin sequence, and distinct sequences produce distinct methods. The unit-margin methods additionally coincide with canonical hierarchies on ultrametric inputs and satisfy order invariance.

  • Admissibility: For every separation margin sequence η, the methods Tη_loc and Tη_glob satisfy the required hierarchical clustering properties and are admissible.Their outputs are laminar, and the construction gives scale invariance, cluster-wise consistency, permutation invariance, and hierarchical richness.
  • Distinct constructions: Distinct separation margin sequences define distinct methods, yielding an uncountable family of separation-based constructions.A dissimilarity can be chosen so that a cluster is accepted by one sequence but rejected by another.
  • Exactness and order invariance: The unit-margin methods Tη_loc and Tη_glob are exact on ultrametrics and coincide with the hierarchy Ψu.For η=1, both methods equal Ψu on every ultrametric input; if η differs from 1, exactness fails.
  • Exactness and order invariance: The unit-margin local method is order invariant because its cluster condition depends only on strict comparisons of within- and cross-cluster dissimilarities.Strictly increasing transformations preserve those comparisons, so Tloc(g∘d)=Tloc(d).
  • Exactness and order invariance: Any non-unit margin sequence produces a local method that is not order invariant.The paper constructs order-equivalent dissimilarities whose transformed values cross the relevant margin threshold differently.

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

The Tstable method builds hierarchies from Bryant–Berry stable clusters and satisfies the hierarchical axioms, including scale invariance, consistency, and permutation invariance.

  • Tstable is a hierarchical clustering method satisfying scale invariance, exactness on ultrametrics, cluster-wise consistency, and permutation invariance.Stable clusters form a laminar family; adding the root and singleton clusters makes the output a hierarchy.
  • Scaling all dissimilarities by β>0 scales isolation weights by β, preserving which clusters are stable.
  • For ultrametric dissimilarities, Tstable contains the associated hierarchy Ψu, and the proof establishes the reverse inclusion.
  • Strengthening within-cluster and cross-cluster dissimilarities cannot destroy a stable cluster, because its isolation weight does not decrease.
  • The stability construction is permutation invariant because permutations biject the admissible triples used to compute isolation weights.

D.1 Incompatibility among Methods

The paper constructs dissimilarities showing that admissible hierarchical methods can be mutually incompatible, so no hierarchy can simultaneously contain all of their clusters.

  • Tstable^(p) and Tstable^(q) cannot share a common hierarchical refinement because their selected clusters overlap without either containing the other.
  • For every p>0, Tstable^(p) and Tstable^(q) are mutually incompatible whenever p≠q.A four-point construction produces overlapping clusters selected by the two power-transformed methods, and the construction extends to larger domains.
  • For any p>0, non-binary single linkage TSL and Tstable^(p) are incompatible.The witness clusters are {1,2,3} and {2,3,4}, whose overlap violates laminarity.
  • The incompatibility construction for TSL and Tstable^(p) extends from four points to every domain size n≥4.

D.2.1 Proof of Theorem 15

Theorem 15 shows that every admissible method contains a hierarchy of sufficiently well-separated clusters, with separation thresholds depending only on cluster size under permutation invariance.

  • A cluster whose internal-to-external separation ratio is below a positive threshold must be selected by any method satisfying scale invariance, richness, and consistency.
  • The proof derives cluster-wise selection from partition consistency by preserving a realized partition under a suitable strengthening of dissimilarities.
  • Permutation invariance makes the separation threshold depend only on the cluster size, yielding a sequence η1,…,ηn−2.
  • Every admissible method contains the global backbone hierarchy Tglob.The proof establishes Tglob⊆T for every admissible method T.
  • The backbone hierarchy can be embedded into any admissible method after a strictly increasing transformation of dissimilarities when order invariance is assumed.

Appendix E. Empirical Size of Backbone Hierarchy

Across four standard datasets, the global backbone hierarchy contains a substantial fraction of the nontrivial clusters found by non-binary single linkage.

  • The evaluation removes duplicate feature vectors, standardizes features, uses Euclidean dissimilarities, and compares nontrivial-cluster counts.
  • Table 3 compares the size of Tglob with the non-binary single-linkage hierarchy TSL.
  • Tglob contains approximately 19%–29% of TSL’s nontrivial clusters across the datasets, with 23.0% in aggregate.
Loading 2609.11173v1…