Hierarchical clustering costs and graph distances compared and bounded
Dasgupta's Hierarchical Clustering Objective: Geometry and the Price of the Cardinality Constraint
Data Structures and Algorithms
Summary
Hierarchical clustering organizes data into nested groups, and measuring the cost of this grouping helps understand how well it fits the data. The authors study how these costs relate to distances found in graphs that represent data similarities. They identify exact relationships and show that requiring clusters to reflect size limits increases the cost, but this increase can be precisely bounded. They also find that for many types of graphs, especially sparse ones, this cost increase is much smaller than in the worst case. Their work provides clearer understanding and algorithms for making these clusterings efficiently.
hierarchical clusteringultrametricshortest-path metricsimilarity graphcardinality constraintgraph diameterconnected graphbalanced cutsworst-case boundssparse graphs
Authors
Peiyuan Sun
Abstract
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.