cs.DSApr 26, 2026

Characterizing Admissible Objective Functions for Hierarchical Clustering

Authors: Ryuki Tsukuba, Kazutoshi Ando

Organizations: Graduate School of Integrated Science and Technology, Shizuoka University,Jun Hamamatsu, Shizuoka 432-8561, Japan · Faculty of Engineering, Shizuoka University, Johoku 3-5-1, 432-8561 Hamamatsu, Japan

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Hierarchical clustering is a fundamental task in data analysis, but classical methods have long lacked a principled objective function. Dasgupta [STOC 2016] took an important step toward addressing this gap by proposing a well-motivated objective function for cluster trees. Cohen-Addad et al. [J. ACM 2019] subsequently introduced the notion of admissibility: an objective function is admissible if, whenever the input similarity matrix admits generating trees, its minimizers are precisely those generating trees. They also gave a necessary and sufficient condition for admissibility within a family of objective functions based on aggregate intercluster similarity. We refer to this family as sum-type objective functions. However, apart from Dasgupta's original objective function, no explicit admissible objective functions in this family were provided. In this paper, we study admissible objective functions for hierarchical clustering in two directions. For sum-type objective functions, we give a complete characterization when the scaling function is a symmetric polynomial of degree at most two, and we derive sufficient conditions for degree-three polynomials. We also show that the recursive sparsest cut algorithm achieves an O(φ)(φ)-approximation ratio for the admissible objective functions covered by our characterization, where φφ is the approximation factor of the sparsest cut subroutine. We then introduce max-type objective functions, where cluster interaction is measured by maximum, rather than aggregate, intercluster similarity. For this class, we characterize which objective functions are admissible for arbitrary symmetric scaling functions and give a complete characterization when the scaling function is a symmetric polynomial of degree at most two.

Explore similar work

CardsList
Sep 11, 2026cs.LG

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

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.
Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser +1
Cluster StructureHierarchicalHeterogeneityMaximum Independent SetSeparabilityInvariance+1
AskPDF
Jul 14, 2026cs.DS

Hierarchical F\mathcal{F}-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs

Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the remaining cluster is a graph belonging to a class F\mathcal{F}. We call this problem Hierarchical F\mathcal{F}-Clustering and we measure the quality of any solution using adapted Dasgupta's clustering objective. We study two natural choices of F\mathcal{F}: trees and graphs of bounded diameter. We present the first polynomial time O(log⁡n⋅log⁡log⁡n)\mathcal{O}(\log n\cdot\log\log n) and O(log⁡n)\mathcal{O}(\log n)-approximation algorithms for clustering into trees and bounded diameter graphs respectively. Our main technical contribution is a framework for approximating such problems based on linear programming. In fact, we characterize graphs classes F\mathcal{F} for which our approach can be applied and show that it includes both trees and bounded diameter graphs. However, our ideas are not limited to them and might be useful for other structures as well. Broadly speaking, our framework applies whenever the corresponding flat clustering problem, which we call pFp_{\mathcal{F}}-Partitioning, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees. Intuitively, given a set of vertices called terminals, the problem is to find an edge set whose removal results in satisfying certain vertex-dependent structural predicate for each terminal. We then use these ingredients to build clustering trees with the aforementioned approximation guarantees. To complement these results, we show that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.
Michał Szyfelbein, Dariusz Dereniowski
Image ClusteringApproximation AlgorithmsApproximationTreesHard
AskPDF
Feb 27, 2026cs.CC

Universal NP-Hardness of Clustering under General Utilities

Clustering is a central primitive in unsupervised learning, yet practice is dominated by heuristics whose outputs can be unstable and highly sensitive to representations, hyperparameters, and initialisation. Existing theoretical results are largely objective-specific and do not explain these behaviours at a unifying level. We formalise the common optimisation core underlying diverse clustering paradigms by defining the Universal Clustering Problem (UCP): the maximisation of a polynomial-time computable partition utility over a finite metric space. We prove the NP-hardness of UCP via two independent polynomial-time reductions from graph colouring and from exact cover by 3-sets (X3C). 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 intractability. Our results provide a unified explanation for characteristic failure modes, such as local optima in alternating methods and greedy merge-order traps in hierarchical clustering. Finally, we show that clustering limitations reflect interacting computational and epistemic constraints, motivating a shift toward stability-aware objectives and interaction-driven formulations with explicit guarantees.
Angshul Majumdar
Image ClusteringNp-HardPartitioningUnsupervised
AskPDF