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

Technical Summary: Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance

Problem Statement
Clustering lacks a universally accepted definition of a "cluster," a difficulty formalized by Kleinberg's Impossibility Theorem (Kleinberg, 2002). This theorem demonstrates that no flat clustering method (mapping dissimilarities to a single partition) can simultaneously satisfy three natural axioms: scale invariance (independence from the units of measurement), richness (the ability to produce any possible partition given an appropriate input), and consistency (the property that strengthening intra-cluster similarities and weakening inter-cluster similarities should not alter the output partition). The tension arises because consistency allows for the creation of new substructures within a cluster, which a flat partition cannot express without violating the axiom.

This paper investigates whether this impossibility persists when the output is a hierarchy (a nested family of clusters) rather than a flat partition. The authors ask if hierarchical analogs of Kleinberg's axioms can be jointly satisfied.

Methodology and Definitions
The authors define a hierarchical clustering method as a map $T$ from a set of dissimilarity functions $D(X)$ to the set of hierarchies $T(X)$, where a hierarchy is a laminar family of clusters containing the full set $X$ and all singletons. They formulate four axioms for hierarchical clustering:

1. Scale Invariance: $T(\beta d) = T(d)$ for any scaling factor $\beta > 0$.
2. Partition Richness: For every partition $\mathcal{C}$ of $X$, there exists a dissimilarity $d$ such that $\mathcal{C} \subseteq T(d)$. (Note: The hierarchy must contain the partition as a subset of its clusters).
3. Partition Consistency: If a partition $\mathcal{C}$ is contained in $T(d)$, and $d'$ is a $\mathcal{C}$-strengthening of $d$ (intra-cluster distances decrease, inter-cluster distances increase), then $\mathcal{C} \subseteq T(d')$.
4. Permutation Invariance: The output depends only on the dissimilarity structure, not on the labeling of points.

A method satisfying all four is termed admissible. The authors also consider a stronger condition, exactness on ultrametrics, requiring that if the input is an ultrametric, the method recovers the canonical hierarchy associated with that ultrametric.

Key Contributions and Results

1. Achievability of Admissibility
Contrary to the flat clustering setting, the authors prove that admissible hierarchical methods exist. In fact, there are uncountably many such methods.

• Explicit Constructions: The paper constructs several admissible methods:
  • Non-binary Single Linkage ($T_{SL}$): Unlike standard binary single linkage, the non-binary variant (merging all tied clusters simultaneously) is admissible.
  • Separation Methods: Two families of methods, $T_{glob}^\eta$ and $T_{loc}^\eta$, based on global and local separation margins. These define clusters where internal dissimilarities are sufficiently small compared to external ones.
  • Bryant-Berry Stable Clusters ($T_{stable}$): A method based on combinatorial stability criteria, along with its power-transformation variants $T_{stable}^{(p)}$.
• Impossibility for Other Linkages: Non-binary variants of complete, average, Ward, centroid, and median linkage are shown to violate at least one axiom.

2. Structural Analysis of Admissible Methods
The set of admissible methods, denoted $H_{\alpha_{adm}}(X)$, is analyzed under the refinement order ($T_1 \sqsubseteq T_2$ if $T_1(d) \subseteq T_2(d)$ for all $d$).

• Diversity: The set forms a partially ordered set (poset) with uncountable height, width, and cellularity.
• No Greatest Element: There is no single "finest" admissible method that refines all others.
• Incompatibility: There exist uncountably many pairwise incompatible maximal elements (methods that cannot be jointly refined by any other admissible method). Specifically, the family $\{T_{stable}^{(p)} : p > 0\}$ forms a strong upward antichain.
• Common Backbone: Despite this diversity, the axioms enforce a nontrivial common structure. Every admissible method refines a hierarchy of sufficiently well-separated clusters ($T_{glob}^\eta$ for some margin sequence $\eta$). Furthermore, any finite collection of admissible methods shares a common backbone.
• No Least Element: The trivial method (returning only singletons and the root) is the infimum in the space of all hierarchical methods but is not admissible because it fails partition richness. Thus, the admissible class has no least element.

3. Strong Admissibility and Ultrametrics
When the axiom of exactness on ultrametrics is added, the class becomes strongly admissible ($H_{\alpha_{adm}^+}(X)$).

• This class remains uncountable and retains the diversity of maximal elements.
• Crucially, unlike the canonical admissible class, the strongly admissible class has a least element: $T_{glob}$ (the method with margin sequence $\eta = \mathbf{1}$). This provides a coarsest strongly admissible method.

4. Preprocessing and Composition
The paper studies preprocessing transformations $\mu: D(X) \to D(X)$ applied before clustering.

• Preservation Conditions: The authors derive general conditions under which a transformation preserves the axioms (e.g., scaling commutes with $\mu$, strengthenings map to strengthenings).
• Examples:
  • Minimax-path (Subdominant Ultrametric): The transformation $B^*$ that maps a dissimilarity to its subdominant ultrametric preserves scale invariance, permutation invariance, and ultrametric exactness. This leads to the factorization $T_{SL} = T_{glob} \circ B^*$, showing single linkage as a composition of an ultrametric transformation and a separation method.
  • PCA and HDBSCAN: The paper analyzes PCA and mutual-reachability preprocessing, showing they preserve scale and permutation invariance but generally fail to preserve richness or consistency.

Significance
The paper demonstrates that the fundamental impossibility of satisfying Kleinberg's axioms is an artifact of restricting the output to flat partitions. By moving to hierarchical outputs, the axioms become jointly satisfiable, opening the door to a vast landscape of admissible methods.

The work reveals that while the space of admissible methods is extremely diverse (lacking a unique optimal solution), it is not unstructured. The axioms enforce a "conservative" backbone of well-separated clusters that all admissible methods must respect, while allowing freedom in how finer structures are resolved. This provides a principled framework for understanding the trade-offs in hierarchical clustering and suggests that the choice of a specific method within the admissible class depends on the desired balance between sensitivity to noise and the granularity of the output, rather than a violation of fundamental axiomatic principles.

The authors note that this framework connects to prior work by Carlsson and Mémoli (2010) and Ackerman and Ben-David (2016) but differs by focusing on unweighted hierarchies and retaining the full strength of Kleinberg's consistency axiom, resulting in a broader, more diverse class of methods rather than a characterization of a single algorithm.