Characterizations of Admissible Objective Functions for Hierarchical Clustering

Kazutoshi Ando; Ryuki Tsukuba

arxiv: 2604.23628 · v1 · submitted 2026-04-26 · 💻 cs.DS · cs.LG

Characterizations of Admissible Objective Functions for Hierarchical Clustering

Ryuki Tsukuba , Kazutoshi Ando This is my paper

Pith reviewed 2026-05-08 05:29 UTC · model grok-4.3

classification 💻 cs.DS cs.LG

keywords hierarchical clusteringadmissible objective functionssum-type objectivesmax-type objectivesscaling functionssymmetric polynomialsapproximation algorithmscluster trees

0 comments

The pith

Admissible sum-type objective functions for hierarchical clustering are characterized exactly when the scaling function is a symmetric polynomial of degree at most two.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper characterizes admissible sum-type objective functions when the scaling function g is a symmetric polynomial of degree at most two, together with sufficient conditions in the degree-three case. For admissible functions in this class, the recursive sparsest cut algorithm achieves an O(φ)-approximation ratio. It also introduces max-type objective functions, where interactions are measured by maximum rather than summed similarities, and gives a general characterization of admissibility for arbitrary g plus a complete one when g is a symmetric polynomial of degree at most two. These results matter because they identify precisely which objective functions are guaranteed to recover consistent hierarchical representations from input similarities that admit them.

Core claim

We characterize admissible sum-type objective functions when the scaling function g is a symmetric polynomial of degree at most two, together with sufficient conditions in the degree-three case. For admissible objective functions in this class, we show that the recursive sparsest cut algorithm achieves an O(φ)-approximation ratio, where φ denotes the approximation factor of the sparsest cut subroutine. We establish a general characterization of admissibility for arbitrary scaling functions g, and a complete characterization when g is a symmetric polynomial of degree at most two for the new max-type class.

What carries the argument

The admissibility criterion, which requires that minimizers of the objective recover consistent hierarchical representations from similarities that admit them.

If this is right

Admissible sum-type objectives with symmetric polynomial scaling of degree at most two can be optimized to within an O(φ) factor of optimal using recursive sparsest cut.
Max-type objectives provide an alternative formulation that measures cluster interactions by the strongest pairwise similarity rather than aggregate sums.
The characterizations supply necessary and sufficient conditions that delimit the admissible members of both the sum-type and max-type classes.
Sufficient conditions for degree-three sum-type functions identify additional admissible objectives beyond the exact characterization for lower degrees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Designers could now enumerate candidate scaling functions g within the characterized families to produce new objectives that are both admissible and amenable to approximation.
Max-type objectives may prove more stable under noisy or outlier similarities because they emphasize the strongest connections.
The framework could be tested on real similarity data to check whether the recovered hierarchies align with domain-expected structure when using the identified admissible g.

Load-bearing premise

The input similarities are assumed to come from some consistent hierarchical representation for the admissibility recovery guarantee to be meaningful.

What would settle it

A similarity matrix constructed from a known hierarchy that admits a consistent representation but is not recovered as a minimizer under a function the characterization declares admissible.

Figures

Figures reproduced from arXiv: 2604.23628 by Kazutoshi Ando, Ryuki Tsukuba.

**Figure 1.** Figure 1: Cluster trees on X with |X| = 5: (a) T1; (b) T2; (c) T3. Proposition 2.3 restricts the possible forms of polynomial scaling functions satisfying the uniform-similarity condition. We next examine which of these functions satisfy the monotonicity condition, leading to admissible objectives. Proposition 2.4. Let g(a, b) be a symmetric polynomial of degree at most three. A sufficient condition for a sum-type … view at source ↗

**Figure 2.** Figure 2: (a) Tree T; (b) Tree T ′ . From equations (24)–(28), it follows that Γ ∗ (a + b + c + d) − X i∈{a,b,c,d} Γ ∗ (i) = g(a + b, c + d) + g(a, b) + g(c, d) = g(a + c, b + d) + g(a, c) + g(b, d). □ Proof of Theorem 3.1. [The “only if” part:] Suppose Γ is admissible. We show conditions (i) and (ii) hold. First, to show (i), assume M(x, y) = 1 for all distinct x, y ∈ X. Any cluster tree T on X is a generating tree… view at source ↗

**Figure 3.** Figure 3: (a) Tree T ∗ of M; (b) Tree T on X; (c) Tree T˜; (d) Tree T ′ . which a generating tree exists. Let T ∗ be a generating tree of M ( view at source ↗

read the original abstract

Hierarchical clustering is a fundamental task in data analysis, yet for a long time it lacked a principled objective function. Dasgupta [STOC 2016] initiated a formal framework by introducing a discrete objective function for cluster trees. This framework was subsequently expanded by Cohen-Addad et al. [J. ACM 2019], who introduced the notion of admissibility -- a criterion ensuring that, whenever the input similarities admit consistent hierarchical representations, the minimizers of an objective function recover them. They also provided a necessary and sufficient condition for admissibility within a broad class of objective functions, which we refer to as sum-type objective functions. Our contributions are twofold. First, we characterize admissible sum-type objective functions when the scaling function g is a symmetric polynomial of degree at most two, together with sufficient conditions in the degree-three case. For admissible objective functions in this class, we show that the recursive sparsest cut algorithm achieves an O($\phi$)-approximation ratio, where $\phi$ denotes the approximation factor of the sparsest cut subroutine. Second, we introduce a new class of objective functions for hierarchical clustering, which we term max-type objective functions, where cluster interactions are measured by maximum rather than aggregate similarity. For this class, we establish a general characterization of admissibility for arbitrary scaling functions g, and a complete characterization when g is a symmetric polynomial of degree at most two. These results provide new theoretical insights into admissible objective functions for hierarchical clustering and clarify the scope of algorithmic guarantees for optimizing them.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper characterizes admissible sum-type objectives for low-degree polynomial scaling functions and introduces a new max-type class with its own characterizations, plus a standard approximation result.

read the letter

The main things to know are that the paper characterizes admissible sum-type objectives for symmetric polynomial scaling functions of degree at most two (with sufficient conditions for degree three) and introduces a new max-type class with general and low-degree characterizations, plus an O(phi) approximation via recursive sparsest cut for the admissible sum-type objectives. The work does a good job filling in the details left open by prior papers on admissibility. The max-type family is a fresh idea, and the polynomial cases give concrete, usable conditions. The arguments seem to rest on direct application of the admissibility definition to the objective forms, which keeps things clean and avoids circularity. Soft spots are limited. The results only apply when the similarities admit a consistent hierarchy, a common but restrictive assumption that means the guarantees do not extend to general noisy inputs. The degree-three characterization is incomplete, covering only one direction. The approximation guarantee is the expected one and does not strengthen the dependence on the sparsest-cut factor. This is a paper for specialists in theoretical clustering and approximation algorithms. A reader looking to understand or extend admissible objectives will find it valuable as a reference point. It deserves serious referee attention because the claims are scoped tightly and the new class provides something concrete to build on. I recommend sending it to peer review. The execution looks careful within the stated boundaries, and experts can help tighten the remaining loose ends like the degree-three case.

Referee Report

0 major / 3 minor

Summary. The manuscript characterizes admissible objective functions for hierarchical clustering. For sum-type objectives with scaling function g a symmetric polynomial of degree at most 2, it gives necessary and sufficient conditions for admissibility along with sufficient conditions in the degree-3 case. It proves that the recursive sparsest cut algorithm achieves an O(φ)-approximation ratio on admissible instances in this class. It introduces a new max-type class of objectives (using maximum rather than aggregate similarity) and establishes a general characterization of admissibility for arbitrary g together with a complete characterization when g is a symmetric polynomial of degree at most 2. All results are scoped to inputs admitting consistent hierarchical representations.

Significance. If the characterizations hold, the work provides concrete, usable descriptions of admissible objectives in restricted but natural classes, which can guide the design of new hierarchical clustering objectives with recovery guarantees. The O(φ)-approximation links the admissible sum-type objectives to existing sparsest-cut approximation algorithms. The introduction and characterization of the max-type class expands the framework beyond the sum-type setting of prior work. These scoped, explicit results strengthen the theoretical foundations of the admissibility approach to hierarchical clustering objectives.

minor comments (3)

§2: The definition of symmetric polynomials of degree d would benefit from an explicit example (e.g., for d=2) to clarify the algebraic form used in the subsequent characterizations.
§3.2, Theorem 3: The statement of the O(φ) approximation could include a brief reminder of how φ is defined in terms of the sparsest-cut subroutine to improve readability for readers unfamiliar with the prior literature.
The paper would benefit from a short table summarizing the characterization results across the sum-type and max-type classes and the different degree bounds on g.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the summary of our characterizations for sum-type and max-type objectives, the O(φ)-approximation result, and the recommendation for minor revision. No specific major comments appear in the provided report.

Circularity Check

0 steps flagged

No significant circularity; derivations are direct mathematical characterizations

full rationale

The paper derives necessary and sufficient conditions for admissibility of sum-type and max-type objective functions by direct algebraic analysis of the admissibility definition (when similarities admit consistent hierarchies) applied to the functional forms involving scaling function g. These characterizations are scoped to symmetric polynomials of degree ≤2 (complete) and degree 3 (sufficient conditions), plus a general result for max-type with arbitrary g. No parameters are fitted to data and then renamed as predictions; no self-citations are load-bearing for the central claims; the O(φ)-approximation for recursive sparsest cut follows from the admissibility property without reduction to inputs by construction. The argument chain is self-contained within the stated classes and does not invoke uniqueness theorems or ansatzes from prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claims rest on the admissibility definition introduced by Cohen-Addad et al., standard algebraic properties of symmetric polynomials, and the newly introduced definition of max-type objectives. No data-fitted parameters appear.

axioms (1)

domain assumption Admissibility criterion: whenever input similarities admit consistent hierarchical representations, the minimizers of the objective recover them (Cohen-Addad et al., J. ACM 2019)
This is the load-bearing property the paper characterizes for the two objective classes.

invented entities (1)

max-type objective functions no independent evidence
purpose: Measure interactions between clusters by the maximum similarity rather than an aggregate sum
Newly defined class for which general and polynomial-specific admissibility results are proved.

pith-pipeline@v0.9.0 · 5574 in / 1438 out tokens · 59316 ms · 2026-05-08T05:29:13.837637+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

[1]

Arora, S

S. Arora, S. Rao and U. Vazirani: Expander flows, geometric embeddings and graph parti- tioning.Journal of the Association for Computing Machinery56(2009) Article 5

work page 2009
[2]

Charikar and V

M. Charikar and V. Chatziafraitis: Approximate hierarchical clustering via sparsest cut and spreading metrics. In:Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17)(2017), pp. 841-854

work page 2017
[3]

Cohen-Addad, V

V. Cohen-Addad, V. Kanade, F. Mallman-Trenn and C. Mathieu: Hierarchical clustering: Objective functions and algorithms.Journal of the Association for Computing Machinery 66(2019) Article 26

work page 2019
[4]

Dasgupta: A cost function of similarity-based hierarchical clustering

S. Dasgupta: A cost function of similarity-based hierarchical clustering. In:Proceedings of the 48-th Annual ACM SIGACT Symposium on Theory of Computing (STOC’16)(ACM, New York, 2016), pp. 118-127

work page 2016
[5]

Roy and S

A. Roy and S. Pokutta: Hierarchical clustering via spreading metrics.Journal of Machine Learning Research18(2017) 1-35

work page 2017
[6]

Semple and M

C. Semple and M. Steel:Phylogenetics(Oxford Lecture Series in Mathematics and its Ap- plications Vol. 24, Oxford University Press, 2003)

work page 2003

[1] [1]

Arora, S

S. Arora, S. Rao and U. Vazirani: Expander flows, geometric embeddings and graph parti- tioning.Journal of the Association for Computing Machinery56(2009) Article 5

work page 2009

[2] [2]

Charikar and V

M. Charikar and V. Chatziafraitis: Approximate hierarchical clustering via sparsest cut and spreading metrics. In:Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17)(2017), pp. 841-854

work page 2017

[3] [3]

Cohen-Addad, V

V. Cohen-Addad, V. Kanade, F. Mallman-Trenn and C. Mathieu: Hierarchical clustering: Objective functions and algorithms.Journal of the Association for Computing Machinery 66(2019) Article 26

work page 2019

[4] [4]

Dasgupta: A cost function of similarity-based hierarchical clustering

S. Dasgupta: A cost function of similarity-based hierarchical clustering. In:Proceedings of the 48-th Annual ACM SIGACT Symposium on Theory of Computing (STOC’16)(ACM, New York, 2016), pp. 118-127

work page 2016

[5] [5]

Roy and S

A. Roy and S. Pokutta: Hierarchical clustering via spreading metrics.Journal of Machine Learning Research18(2017) 1-35

work page 2017

[6] [6]

Semple and M

C. Semple and M. Steel:Phylogenetics(Oxford Lecture Series in Mathematics and its Ap- plications Vol. 24, Oxford University Press, 2003)

work page 2003