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

• URL: http://arxiv.org/abs/2609.11173v1
• Date: Thu, 10 Sep 2026 07:20:10 GMT
• Title: Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
• Abstract summary: Kleinberg's Impossibility Theorem shows that no flat clustering method can simultaneously satisfy three natural axioms.<n>We show that, in contrast to the flat clustering setting, the hierarchical analog of these axioms are jointly satisfiable.<n>We explicitly construct several admissible methods, including methods based on well-separated clusters and a non-binary version of single linkage.
• Score: 11.198418635553976
• License: http://creativecommons.org/licenses/by/4.0/
• 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 papers

• Weight-Informed Self-Explaining Clustering for Mixed-Type Tabular Data [63.62853416081748]
  WISE is a framework that unifies representation, feature weighting, clustering, and interpretation.<n>It produces faithful, human-interpretable explanations grounded in the same primitives that drive clustering.
  arXiv  Detail & Related papers  (2026-04-07T13:18:31Z)
• Universal NP-Hardness of Clustering under General Utilities [11.62669179647184]
  We formalise the common optimisation core motivating a diverse-time computable partition utility over a finite metric space.<n>By mapping ten major paradigms -- including k-means, GMMs, DBSCAN, spectral clustering, and affinity propagation -- to the UCP framework, we demonstrate that each inherits this fundamental inability.
  arXiv  Detail & Related papers  (2026-02-27T13:08:15Z)
• Topological Mixed States: Phases of Matter from Axiomatic Approaches [15.433292838001103]
  In closed quantum systems, topological orders are understood through the equivalence classes of ground states of gapped local Hamiltonians.<n>Here, we fill this gap by proposing an approach based on three axioms: ($i$) local recoverability, ($ii$) absence of long-range correlations, and ($iii$) spatial uniformity.<n>From these axioms, a rich set of topological data naturally emerges; importantly, these data are robust under relaxation of axioms.
  arXiv  Detail & Related papers  (2025-06-04T17:58:45Z)
• Unextendibility, uncompletability, and many-copy indistinguishable ensembles [49.1574468325115]
  We show that the complement of any bipartite pure entangled state is spanned by product states which form a nonorthogonal unextendible product basis (nUPB) of maximum cardinality.<n>We also report a class of multipartite many-copy indistinguishable ensembles for which local indistinguishability property increases with decreasing number of mixed states.
  arXiv  Detail & Related papers  (2023-03-30T16:16:41Z)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  Method for unsupervised meta-learning, CACTUs, is a clustering-based approach with pseudo-labeling. This approach is model-agnostic and can be combined with supervised algorithms to learn from unlabeled data. We prove that the core reason for this is lack of a clustering-friendly property in the embedding space.
  arXiv  Detail & Related papers  (2022-09-27T19:04:36Z)
• Asymptotic Theory of Geometric and Adaptive $k$-Means Clustering [0.0]
  We revisit Pollard's classical result on consistency for $k$-means clustering in Euclidean space.<n>We show that all clustering procedures described above are strongly consistent.
  arXiv  Detail & Related papers  (2022-02-27T18:56:41Z)
• Towards Continuous Consistency Axiom [0.0]
  Development of new algorithms in the area of machine learning, especially clustering, requires availability of labeled data sets. We propose an alternative axiomatic system, in which Kleinberg's inner consistency axiom is replaced by a centric consistency axiom. We demonstrate that the new system is satisfiable for a hierarchical version of $k$-means with auto-adjusted $k$, hence it is not contradictory.
  arXiv  Detail & Related papers  (2022-02-12T08:25:01Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• Local indistinguishability and incompleteness of entangled orthogonal bases: Method to generate two-element locally indistinguishable ensembles [0.0]
  Local indistinguishability of states with the properties of unextendibility and uncompletability of entangled bases for bipartite and multipartite quantum systems. We identify a method of constructing two-element ensembles, based on the concept of unextendible entangled bases, that can potentially lead to information sharing applications.
  arXiv  Detail & Related papers  (2020-08-04T15:04:27Z)
• 3D Correspondence Grouping with Compatibility Features [51.869670613445685]
  We present a simple yet effective method for 3D correspondence grouping. The objective is to accurately classify initial correspondences obtained by matching local geometric descriptors into inliers and outliers. We propose a novel representation for 3D correspondences, dubbed compatibility feature (CF), to describe the consistencies within inliers and inconsistencies within outliers.
  arXiv  Detail & Related papers  (2020-07-21T02:39:48Z)
• Revealing consensus and dissensus between network partitions [0.0]
  Community detection methods attempt to divide a network into groups of nodes that share similar properties, thus revealing its large-scale structure. Many methods exist to establish a consensus among them in the form of a single partition "point estimate" that summarizes the whole distribution. Here we show that it is in general not possible to obtain a consistent answer from such point estimates when the underlying distribution is too heterogeneous. We provide a comprehensive set of methods designed to characterize and summarize complex populations of partitions in a manner that captures not only the existing consensus, but also the dissensus between elements of the population.
  arXiv  Detail & Related papers  (2020-05-28T13:29:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.