Source-linked AI summary
Hierarchical Clustering: Objective Functions and Algorithms
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu
TL;DR
The paper asks how to define and optimize good hierarchical-clustering objectives when natural hierarchical structure exists. It characterizes admissible objectives and analyzes algorithms across worst-case, stochastic, and perturbed inputs, obtaining improved approximation guarantees and near-optimal recovery in structured settings.
Problem
Hierarchical clustering lacked a theory-centered framework for defining good objectives and evaluating practical algorithms, especially when inputs possess natural hierarchical structure.
Method
The paper takes an axiomatic approach to objective functions, characterizes admissibility, and analyzes or develops algorithms for similarity, dissimilarity, stochastic, and perturbed inputs.
Results
3/2-approximation is achieved for dissimilarity-based clustering, while Dasgupta’s objective is within 1 + o(1) of OPT with high probability in the hierarchical stochastic block model.
Takeaways & Limitations
Admissible objectives make natural ground-truth trees optimal, and several practical or simple algorithms recover or approximate such trees in structured settings.
Takeaways & Limitations
The ground-truth-tree framework does not extend cleanly from ultrametrics to general tree metrics, where a candidate tree may be more suitable than the generating tree.
Abstract
from arXiv · showhide
Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, Dasgupta framed similarity-based hierarchical clustering as a combinatorial optimization problem, where a `good' hierarchical clustering is one that minimizes some cost function. He showed that this cost function has certain desirable properties. We take an axiomatic approach to defining `good' objective functions for both similarity and dissimilarity-based hierarchical clustering. We characterize a set of "admissible" objective functions (that includes Dasgupta's one) that have the property that when the input admits a `natural' hierarchical clustering, it has an optimal value. Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better algorithms. For similarity-based hierarchical clustering, Dasgupta showed that the divisive sparsest-cut approach achieves an $O(\log^{3/2} n)$-approximation. We give a refined analysis of the algorithm and show that it in fact achieves an $O(\sqrt{\log n})$-approx. (Charikar and Chatziafratis independently proved that it is a $O(\sqrt{\log n})$-approx.). This improves upon the LP-based $O(\log n)$-approx. of Roy and Pokutta. For dissimilarity-based hierarchical clustering, we show that the classic average-linkage algorithm gives a factor 2 approx., and provide a simple and better algorithm that gives a factor 3/2 approx.. Finally, we consider `beyond-worst-case' scenario through a generalisation of the stochastic block model for hierarchical clustering. We show that Dasgupta's cost function has desirable properties for these inputs and we provide a simple 1 + o(1)-approximation in this setting.
1 Introduction
The paper formulates hierarchical clustering around objective functions, characterizes when such objectives recover natural trees, and analyzes approximation algorithms in worst-case and structured settings.
- 1 Introduction: Hierarchical clustering is represented by rooted trees, but unlike flat clustering it has historically been studied more through procedures than optimized objectives.Practical methods include agglomerative and divisive heuristics.
- 1 Introduction: Admissible objectives are exactly those that are symmetric, increasing in child-cluster cardinalities, and assign equal cost to all binary trees on unit-weight cliques.Dasgupta’s objective satisfies these criteria.
- Beyond worst-case: Dasgupta’s objective has cost at most 1 + o(1) times OPT with high probability on hierarchical stochastic block model inputs.The algorithm also recovers the ground-truth tree in this setting.
- Worst-case approximation: The recursive φ-approximate sparsest-cut algorithm achieves an O(φ) approximation for similarity-based inputs, improving prior O(φ log n) and O(log n) guarantees.The paper gives an independent refined analysis, with a stated 6.75φ guarantee.
- Worst-case approximation: For dissimilarity-based inputs, average-linkage achieves a 2-approximation, while the locally densest-cut algorithm achieves a 3/2-approximation.The guarantees extend to other admissible objectives with function-dependent ratios.
- Beyond worst-case: On ground-truth inputs, practical linkage and related algorithms recover a ground-truth tree, and a faster algorithm is also optimal.The paper presents these results as progress toward understanding objective-based hierarchical clustering and practical heuristics.
2 Preliminaries
The preliminaries define graph, tree, ultrametric, and generating-tree terminology, then explain how ultrametric structure supplies ground-truth hierarchical clusterings.
- Cluster trees: A cluster tree is a rooted binary tree with one distinct vertex-labeled leaf per graph vertex.LCAT denotes the lowest common ancestor of two vertices, and V(N) denotes the descendant leaves of node N.
- Ultrametrics: An ultrametric satisfies d(x,y) ≤ max{d(x,z), d(y,z)} for every triple of points.Similarity graphs use non-increasing functions of ultrametric distances, whereas dissimilarity graphs use non-decreasing functions.
- Generating trees: A generating tree represents a graph generated by a minimal ultrametric through internal-node weights and a bijection between leaves and graph vertices.The paper relates generating trees to dendograms, whose internal heights encode pairwise distances at least common ancestors.
- Ground-Truth Inputs: A ground-truth input is a similarity or dissimilarity graph generated from an ultrametric, equivalently one admitting a generating tree.The associated clusters preserve a level-by-level similarity ordering: within-cluster pairs are at least as similar as pairs reaching outside the cluster.
- Ground-Truth Inputs: Linkage algorithms can recover generating trees for ultrametric-generated graphs, but tree-metric inputs need not have an unambiguous natural clustering.For a five-node caterpillar example, Dasgupta’s objective can prefer a candidate cluster tree over the generating tree.
3 Quantifying Output Value: An Axiomatic Approach
The paper defines admissible hierarchical-clustering objectives axiomatically and characterizes them through clique invariance, symmetry, and monotonicity. These objectives identify generating trees as optimal on ultrametric inputs, with the characterization extending to dissimilarities.
- Admissibility: Admissibility requires that generating trees, and only generating trees, optimize the objective on ultrametric-generated graphs.For similarities they attain minimum cost; for dissimilarities they attain maximum value.
- Objective Functions: Admissible objectives sum cut weights multiplied by functions of the two child-cluster sizes, including Dasgupta’s objective.The framework assigns costs at internal tree nodes and restricts the objective to this structural form.
- Characterization: Theorem 3.4 characterizes admissible cost functions by three conditions: equal cost for all cliques, symmetry of g, and monotonicity of g.The monotonicity condition is g(n1 + 1, n2) > g(n1, n2).
- Characterization: Equal clique costs follow because every cluster tree for a uniformly weighted clique is generating and therefore must be optimal.This establishes the first condition required by admissibility.
- Open Direction: The proof’s final inequality uses that g(n,1)/(n+1) is non-decreasing, and the authors leave relaxing this requirement as an open direction.This condition is used in the analysis showing Dasgupta’s objective is not unique.
- Dissimilarity Objectives: The similarity-case characterization also holds for dissimilarity objectives after reversing the relevant inequality directions.Thus the same structural conditions govern both settings.
4 Similarity-Based Inputs: Approximation Algorithms
For similarity-based hierarchical clustering, the paper analyzes recursive approximate sparsest-cut algorithms using a charging argument. The resulting guarantee is 6.75φ for Dasgupta’s objective and extends in function-dependent form to admissible objectives.
- Algorithm and Guarantee: 6.75φ-approximation: recursive φ-sparsest-cut achieves this guarantee for Dasgupta’s hierarchical-clustering cost.The algorithm recursively splits the graph using a φ-approximate sparsest cut.
- Algorithm and Guarantee: The algorithm constructs a binary tree top-down by finding an approximate sparsest cut, recursing on both sides, and joining the resulting trees at a root.Its sparsest-cut subproblem minimizes cut weight divided by the product of the two side sizes.
- Charging Analysis: The balanced-cut argument compares the algorithm’s approximate cut against a cut whose two sides each contain between n/3 and 2n/3 vertices.This balance enables the charging scheme used to relate the algorithm’s cost to the comparison tree.
- Charging Analysis: The analysis charges each edge for costs induced by algorithmic cuts and bounds its total charge using the lowest common ancestor in an arbitrary comparison tree.Lemma 4.2 gives an overall edge-charge bound of (9/2)φ min((3/2)|V(LCAT*(v1,v2))|, n)w(e).
- Extensions: The same approach yields an O(fnφ)-approximation for any admissible cost function, where fn = maxn f(n)/f(⌊n/3⌋).The approximation ratio therefore depends on the particular admissible objective.
- Worst-Case Comparison: The sparsest-cut approach is presented as more reliable in worst-case settings because standard agglomerative heuristics can perform poorly there.The paper separately finds agglomerative algorithms efficient on ground-truth and random-graph inputs.
5 Admissible Objective Functions and Algorithms for Random Inputs
The paper studies admissible objectives and hierarchical clustering algorithms for random graphs with hidden hierarchical structure. For admissible objectives, the ground-truth tree is optimal in expectation, while an SVD-plus-agglomerative algorithm achieves near-optimal cost for smooth objectives with high probability.
- Expected-cost guarantee: For any admissible objective, the ground-truth tree has optimal expected cost in the hierarchical stochastic block model.Expected costs are computed using the complete expected graph, by linearity of expectation.
- High-probability guarantee: For smooth admissible objectives, including Dasgupta’s objective, the ground-truth cost is concentrated within a 1 + o(1) factor of its expectation with high probability.Consequently, the ground-truth tree has cost at most (1 + o(1))OPT with high probability.
- Algorithm: An SVD-based projection followed by agglomerative heuristics outputs a tree with cost at most (1 + o(1))OPT with high probability.Repeating the randomized procedure and selecting the least-cost output boosts the success probability; one candidate is also the ground-truth tree with high probability.
- Random graph model: The hierarchical stochastic block model generates random graphs from k bottom-level clusters arranged according to a hierarchy.Cluster memberships determine edge probabilities through an underlying ultrametric graph on the k clusters.
- Objective functions: Admissible objective functions are characterized so that, on ground-truth inputs, the ground-truth tree has optimal cost.The expected-cost characterization is exact: a tree is optimal if and only if it is a ground-truth tree.
6 Dissimilarity-Based Inputs: Approximation Algorithms
For dissimilarity-based hierarchical clustering, the paper analyzes practical approximation algorithms and introduces a recursive locally-densest-cut method. Average-linkage achieves a 2-approximation, while the new method achieves a 3/2 + ε approximation with stated running time.
- Problem setting: The dissimilarity-based optimization problem is NP-hard, so the analysis focuses on approximation algorithms.The objective is expressed through a value function associated with tree nodes and their child clusters.
- Average-linkage: 2-approximation is achieved by the average-linkage algorithm for the dissimilarity setting.The guarantee applies to the objective analyzed in this section, and analogous guarantees for admissible objectives depend on the objective function.
- Recursive locally-densest cuts: 3/2 + ε approximation is achieved by a recursive algorithm that repeatedly computes locally-densest cuts and recurses on both sides.The method uses a local-search heuristic rather than approximating the densest-cut problem directly.
- Recursive locally-densest cuts: The local-search procedure computes an ε/n-locally-densest cut in time O(n(n + m)/ε).The recursive algorithm then uses these cuts to construct the output tree.
- Recursive locally-densest cuts: The recursive locally-densest-cut algorithm runs in O(n^2(n + m)/ε) time.The bound combines the local-search cost at each recursive call with recursion depth O(n).
7 Perfect Ground-Truth Inputs and Beyond
On ground-truth inputs, standard linkage and divisive algorithms recover optimal trees for admissible objectives. The section also gives efficient exact algorithms and a robust δ-approximation for adversarial perturbations.
- Perfect Ground-Truth Inputs: For any admissible objective, average-linkage, single-linkage, and complete-linkage return optimal solutions on similarity or dissimilarity ground-truth inputs.The guarantee holds regardless of the algorithm’s tie-breaking rule.
- Perfect Ground-Truth Inputs: For strict ground-truth inputs, bisection 2-Center returns an optimal solution for any admissible objective.
- Perfect Ground-Truth Inputs: For similarity ground-truth inputs, recursive sparsest-cut computes an optimal tree; for dissimilarity inputs, the analogous densest-cut algorithm has the same guarantee.A sparsest cut can be computed in O(n) time on the relevant similarity graphs.
- A Near-Linear Time Algorithm: Algorithm 8 computes an optimal tree in O(n log^2 n) time with high probability on strict inputs and in O(n^2) time on general ground-truth inputs.
- Beyond Structured Inputs: A robust algorithm returns a δ-approximation for δ-adversarially perturbed ground-truth inputs, with the same guarantee for every admissible objective function.Its running time is O(n(n + m)).
8 Worst-Case Analysis of Common Heuristics
Worst-case constructions show that common hierarchical-clustering heuristics can perform badly, even on simple graphs. The failures contrast with their optimality on structured ground-truth inputs.
- Overview: Common linkage heuristics may perform badly on both similarity and dissimilarity inputs, motivating analysis beyond structured ground-truth cases.
- Similarity Graphs: Single-linkage and complete-linkage have families of inputs with cost Ω(n OPT / log n).The result is stated for each algorithm separately over an infinite family of inputs.
- Similarity Graphs: On path graphs, the optimal cost is O(n log n), while complete-linkage can produce a tree with cost Ω(n^2).The construction exploits a permitted sequence of consecutive merges.
- Similarity Graphs: Average-linkage has an infinite family of inputs where its output cost is Ω(n^(1/3) OPT).
- Dissimilarity Graphs: Single-linkage, complete-linkage, and bisection 2-Center each have input families where their output value is O(OPT / n).The construction uses one edge with weight W ≥ n^3 and compares the resulting trees with an optimum of at least nW.