PaperlayerView exact revision on arXiv

Source-linked AI summary

Dasgupta's Hierarchical Clustering Objective: Geometry and the Price of the Cardinality Constraint

Peiyuan Sun

arXiv:2609.07205v1cs.DS

TL;DR

The paper asks how much the cardinality labels in Dasgupta’s hierarchy constrain its geometric cost relative to freely chosen labels. It recasts the comparison using dominating ultrametrics and connected binary hierarchies, then establishes a sharp worst-case gap and smaller bounds under structural conditions.

  • Problem

    The paper asks how costly cardinality-realizable labels are compared with freely chosen scales in dominating ultrametrics over a support graph’s shortest-path metric.

    Source: §I · p. 1

  • Method

    It represents hierarchies as ultrametrics and uses connectedification to compare cardinality-labeled and diameter-labeled connected binary hierarchies.

    Source: §I · p. 1, §VI · p. 5

  • Results

    The worst-case ratio is (2n−1)/3, while hereditary fragmentation gives O(log n) under uniform local control and a constant gap under polynomial scale decay.

    Source: §XII · p. 11

  • Takeaways & Limitations

    Cardinality labels have a linear worst case but admit smaller bounds under structural conditions, with logarithmic order tight on bounded-degree unweighted trees.

    Source: §XI · p. 10, §XII · p. 11

    The geometric interpretation uses the support graph’s unit-length metric, which is discrete for complete support and most informative for sparse or thresholded graphs.

    Source: §XI · p. 11

Abstract

from arXiv · show

The cost of a hierarchical clustering can be represented by an ultrametric whose lowest-common-ancestor labels are cluster cardinalities. We relate this known representation to the shortest-path geometry of a similarity graph. For a connected support graph $G$, let $d_G$ be its unit-length shortest-path metric and let the edge weights enter only the objective. We prove that the shifted Dasgupta optimum is exactly the minimum edge-weighted cost of a cardinality-realizable ultrametric that dominates $d_G$. Connectedification lemmas put this problem and its freely labeled dominating-ultrametric relaxation on the same class of connected binary hierarchies, labeled respectively by cardinality and graph diameter. As a sharp baseline, we determine the exact worst-case price of cardinality realizability: on every $n$-vertex instance the ratio of the two optima is at most $(2n-1)/3$, with equality on the unweighted complete graph; the sharp factor for the standard unshifted objective is $2(n+1)/3$. Our principal structural result bounds this gap by a hereditary weighted fragmentation profile defined through connected balanced cuts. Uniform local control gives an $O(\log n)$ gap, polynomial decay gives a constant gap, and the logarithmic order is tight even for unweighted trees of maximum degree $3$. On locally regular bounded-degree trees, the hierarchy can be constructed in $O(n\log n)$ time. An energy decomposition and a geometric density bound provide supporting instance-sensitive estimates. Thus the cardinality label has an unavoidable linear worst case but admits substantially smaller bounds on natural sparse graph classes.

I. INTRODUCTION

The paper compares cardinality-labeled ultrametrics with freely labeled dominating ultrametrics over a support graph’s unweighted shortest-path metric. It positions this comparison as distinct from work on heuristic quality and other tree or ultrametric objectives.

II. RELATED WORK

  • Prior work analyzes particular algorithms and the Dasgupta objective, whereas this paper compares optimal hierarchies under cardinality labels and free scales.Moseley and Wang studied algorithm quality; the present comparison changes the admissible ultrametric labels.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • The comparison keeps the support-graph metric, edge-weight measure, and non-contraction fixed, changing only whether internal labels must equal cluster cardinalities.The support metric is unweighted shortest-path distance; similarity magnitudes enter the objective, not the metric.Source: §I · p. 1
  • The paper identifies geometric equivalence and common connected normal forms, an exact worst-case cardinality price, and hereditary fragmentation bounds with a tight sparse-tree example.Its secondary estimates include an energy decomposition and a geometric density bound.Source: §I · pp. 1–2
  • The paper does not give new approximation guarantees for practical clustering heuristics; its factors compare two optimized geometric benchmarks.The comparison isolates a structural restriction rather than the computational difficulty of approximating Dasgupta’s objective.Source: §I · pp. 1–2

II. RELATED WORK

  • The ultrametric representation of dendrograms is established prior work, but this paper uses it to compare objective values under different feasible label sets.Carlsson and Mémoli’s cited theory addresses method behavior under perturbation and sampling, not this objective comparison.Source: §I · p. 1, §II · p. 2
  • The paper distinguishes its benchmark comparison from prior tree-embedding distortion and metric-fitting objectives, which use different criteria or fit supplied dissimilarities.Its weights are similarities on support edges, while the unweighted support metric supplies non-contraction.Source: §II · p. 3

III. PRELIMINARIES

The preliminaries separate the support graph’s unit-length shortest-path metric from similarity weights and define the hierarchy and objective formulations used in the comparison.

III. PRELIMINARIES

  • The graph is finite, connected, and positively weighted, but its unit-length shortest-path metric depends on the support edges rather than their weights.Weights enter only the objective.Source: §III · p. 3
  • A hierarchy is a rooted tree on the vertices, and each pair’s cost is associated with its lowest-common-ancestor cluster.A hierarchy is connected when every cluster induces a connected subgraph.Source: §III · p. 3
  • The diameter labeling of a connected hierarchy yields a dominating ultrametric, providing the free geometric benchmark.Graph diameter is monotone under set inclusion, and the resulting ultrametric dominates the support metric.Source: §III · p. 3

IV. CONNECTEDIFICATION OF THE FREE ULTRAMETRIC

A dominating ultrametric can be converted into a connected binary hierarchy whose diameter labels remain dominating and do not increase the cost on support edges.

IV. CONNECTEDIFICATION OF THE FREE ULTRAMETRIC

  • Every dominating ultrametric admits a connected binary hierarchy whose diameter ultrametric dominates the support metric and has no greater value on any support edge.The construction forms nested connected components within ultrametric equivalence classes, then refines any nonbinary nodes without increasing edge labels.Source: §IV · pp. 3–4
  • Nested components of induced subgraphs form the connected hierarchy, and labeling each cluster by its graph diameter gives the required ultrametric.Connectedness of the support graph ensures the top partition is the whole vertex set.Source: §IV · p. 4

V. A NORMAL FORM FOR THE FREE OPTIMUM

The free dominating-ultrametric optimum has a connected diameter-normalized hierarchy representation, so it can be minimized over connected binary hierarchies.

V. A NORMAL FORM FOR THE FREE OPTIMUM

  • The free optimum is attained by a connected binary hierarchy labeled by cluster diameters.This representation makes the free ultrametric benchmark an optimization over the same connected hierarchy class used in the comparison.Source: §V · pp. 4–5

VI. CARDINALITY CONNECTEDIFICATION AND EQUIVALENCE

The shifted Dasgupta optimum has an equivalent geometric form as a minimum weighted edge-stretch objective over cardinality-realizable ultrametrics dominating the graph metric. Connectedification shows that restricting to connected binary hierarchies preserves the optimum.

VI. CARDINALITY CONNECTEDIFICATION AND EQUIVALENCE

  • A hierarchy labels each pair by its lowest common ancestor’s cluster cardinality minus one, yielding an ultrametric required to dominate the graph metric on all pairs.The labels are nondecreasing toward the root.Source: §VI · p. 5
  • Every binary hierarchy can be converted into a connected binary hierarchy with no greater shifted cost.The construction forms connected components of induced graph clusters, then refines nonbinary nodes using connected prefix unions.Source: §VI · p. 5
  • The unrestricted, cardinality-realizable dominating, and connected-hierarchy shifted optima are equal.Connected hierarchies dominate the graph metric, while connectedification supplies a connected hierarchy of no greater cost than any binary hierarchy.Source: §VI · p. 5
  • The shifted optimum is the minimum weighted average stretch on support edges among cardinality-realizable ultrametrics that dominate the graph metric.The equivalence also has a connected normal form.Source: §VI · p. 5

VII. THE EXACT CARDINALITY-REALIZABILITY GAP

The section establishes a sharp worst-case gap bound, attained by the unweighted complete graph. It also gives the corresponding sharpness result for the standard objective and uses a pair-cardinality identity in the argument.

VII. THE EXACT CARDINALITY-REALIZABILITY GAP

  • For any rooted binary tree shape with n leaves, the sum of pair-cardinality contributions depends only on n, not on the tree shape.The identity supports the shape-independent cost calculation used in the sharpness argument.Source: §VII · p. 6
  • For every n, the worst-case upper factor is sharp, with equality on the unweighted complete graph.The complete graph’s constant ultrametric dominates its graph metric.Source: §VII · p. 6
  • Randomly labeling a fixed binary tree shape gives an edge-cost expectation, from which a deterministic labeling with no greater cost can be chosen and connectedified without increasing cost.The expectation calculation uses a uniform random bijection from vertices to leaves.Source: §VII · p. 6
  • For the standard Dasgupta objective, the stated factor is best possible and is attained by the unweighted complete graph.Source: §VII · p. 6

VIII. HEREDITARY WEIGHTED FRAGMENTATION

A hereditary profile of connected balanced cuts bounds the gap between cardinality and free ultrametric costs through a recursively constructed connected hierarchy. The logarithmic order is tight even on unweighted trees of maximum degree 3.

Theorem 9

  • Theorem 9 uses a hereditary weighted fragmentation profile to construct a connected binary hierarchy with a scale-wise bound.The profile is defined over connected sets and does not depend on a hierarchy or optimal solution.Source: §VIII · p. 7

Construction

  • Recursively choosing connected α-balanced cuts attaining each set’s fragmentation produces a connected binary hierarchy.A connected α-balanced fragmentation splits a set into two connected parts whose shifted cardinalities are balanced.Source: §VIII · pp. 6–7

Corollary 10

  • Corollary 10 treats uniform and decaying fragmentation regimes, and the scale-sum bound distinguishes uniform regularity from stronger decay.Its proof bounds contributions scale by scale before summing them.Source: §VIII · p. 7

Corollary 13

  • For locally regular weighted trees of bounded degree, the recursive hierarchy construction runs in O(n log n) time for fixed degree.At each depth, the current subtrees are vertex-disjoint, so scans take O(n) time per depth.Source: §VIII · p. 8

Theorem 14

  • The gap has logarithmic order on a sequence of unweighted trees of maximum degree 3.The upper bound follows from unit fragmentation on connected induced subgraphs, and the matching lower bound completes the tight result.Source: §VIII · pp. 8–9

Remark 15

  • For general support graphs, construction is relative to a balanced-connected-cut oracle; polynomial-time solvability of that oracle is not claimed.An oracle returning a cut within factor β of the normalized optimum adds factor β to the hierarchy bound.Source: §VIII · p. 9

IX. ENERGY DECOMPOSITION

The section decomposes hierarchy costs by the cluster where each support edge is separated, then relates the cardinality cost to a free-energy-weighted ratio. It also gives a hierarchy-dependent tail condition as a sufficient diagnostic for bounds.

Lemma 16

  • Grouping each edge at the unique internal cluster where it crosses the children gives the cut-energy decomposition for connected binary hierarchies.The decomposition supplies identities for the hierarchy’s diameter objective and cut energy.Source: §IX · p. 9

Lemma 17

  • The shifted cardinality cost equals diameter cost times the free-energy-weighted mean of the cardinality-to-diameter ratio.For a free-optimal hierarchy, this yields a bound by evaluating its cardinality cost.Source: §IX · pp. 9–10

Corollary 19

  • The polynomial-tail corollary follows from the first-moment theorem, which also yields a logarithmic bound when the tail integral is bounded by A log(n −1).The cited corollary specifies the polynomial-tail case; the stated integral bound is given separately.Source: §IX · p. 10

Theorem 18

  • A tail premise on the hierarchy-dependent free-energy distribution is a sufficient condition for the first-moment bound, not a canonical graph-regularity assumption.The authors do not derive the premise from a stochastic model.Source: §IX · pp. 9–10

X. GEOMETRIC CONSEQUENCES AND OBSTRUCTIONS

The section gives geometric and weight-based diagnostics for the gap between the free and cardinality-constrained benchmarks. Connected-set density and linear ball growth provide one bound, while paths, cycles, trees, and cliques illustrate how the bounds compare.

Instance-sensitive bounds

  • The energy profile is weight-sensitive, while the simpler geometric bound controls the same ratio pointwise.The supplied passages do not state the energy-profile formula.Source: §X · p. 10

Connected-set density

  • The connected-set density parameter Γ(G) is equivalent, up to a factor of 2, to a linear ball-growth constant; graph balls are connected, and each connected set of diameter r lies in a radius-r ball.For a path, Γ(G) = 1, and the free and cardinality-constrained optima coincide.Source: §X · p. 10

Representative graphs

  • On cycles, linear ball growth and balanced cuts give a constant gap; on complete binary trees, density can be large despite a unit fragmentation profile and logarithmic gap.The complete graph has the sharp linear gap, with its root fragmentation value coming from a balanced cut.Source: §X · p. 10

Weight obstructions

  • Conditions based only on ties or the numerical weight aspect ratio cannot guarantee a constant gap.The proposition considers complete graphs with distinct weights arbitrarily close to 1, while the proof uses the discrete support metric and a feasible constant free ultrametric.Source: §X · p. 10

XI. DISCUSSION AND LIMITATIONS

The discussion distinguishes the hereditary fragmentation condition from weight-only regularity and from hierarchy-specific diagnostics. It also qualifies what connectedification preserves and which support-graph metric the geometric interpretation uses.

Structural bounds

  • A hereditary fragmentation profile bounds the gap through recursively assembled light connected balanced cuts; uniform control gives O(log n), tight even for unweighted maximum-degree-3 trees, while polynomial decay gives a constant gap.The condition is local to every connected induced subtree, not merely the global multiset of weights.Source: §XI · pp. 10–11

Energy diagnostic

  • The energy identity diagnoses a large gap when substantial free-objective cost falls on connected clusters large relative to their graph diameter, but is not a graph-structural theorem or weakest regularity principle.It is a diagnostic for a supplied hierarchy.Source: §XI · p. 11

Connectedification scope

  • Connectedification preserves the comparison edgewise, not necessarily for nonedge pairs, because refinement may delay their merger without affecting the support-edge objective.The resulting diameter ultrametric still dominates d_G on every vertex pair.Source: §XI · p. 11

Metric scope

  • The geometric interpretation uses the unit-length support-graph metric, while similarity weights affect only the objective; changing a positive weight leaves that metric unchanged, but removing an edge can change it discontinuously.The interpretation is most informative for sparse or deliberately thresholded support graphs; the paper does not claim this metric is a canonical conversion of similarity magnitudes.Source: §XI · p. 11

XII. CONCLUSION

The conclusion recasts shifted Dasgupta clustering as a cardinality-realizable dominating-ultrametric problem and contrasts it with a free-label relaxation. It emphasizes a sharp linear worst case alongside hereditary conditions that yield smaller gaps on sparse graph classes.

Geometric formulation

  • The shifted Dasgupta optimum equals the minimum cost of a cardinality-realizable ultrametric dominating d_G, and connectedification puts it and the free relaxation on a common hierarchy class.The worst-case ratio is exactly (2n−1)/3; the standard unshifted objective has sharp factor 2(n + 1)/3.Source: §XII · p. 11

Structural result

  • A hereditary weighted fragmentation profile gives a constructive gap bound: uniform local control yields O(log n), tight on bounded-degree unweighted trees, while polynomial scale decay gives a constant gap.On locally regular bounded-degree trees, the recursive construction runs in O(n log n) time.Source: §XII · p. 11

Scope

  • The free-energy-weighted mean of (|S|−1)/diamdG(S) is an auxiliary instance-dependent diagnostic, not the paper’s structural guarantee or a new linkage-heuristic approximation guarantee.The structural guarantee is the hereditary fragmentation theorem.Source: §XII · p. 11
Loading 2609.07205v1…