Source-linked AI summary
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto, Euiwoong Lee, Mohammad Mahdian, Konstantin Makarychev, Grigory Yaroslavtsev
TL;DR
Hierarchical clustering lacked a concrete objective for evaluating its trees. The paper combines Max-Uncut Bisection with Average-Linkage for the Moseley–Wang objective, achieving a .4246 approximation and proving conditional hardness.
Problem
Hierarchical clustering lacked a concrete objective for evaluating trees, unlike flat clustering methods with standard objectives.
Source: §1 · pp. 1–2Method
The algorithm uses Max-Uncut Bisection as a black box to create a top split, then runs Average-Linkage within each side.
Source: §3 · p. 4Results
.4246 of the optimum is guaranteed for the Moseley–Wang objective, improving on the previous .3363 guarantee; under the Small Set Expansion hypothesis, the objective is APX-hard even for unweighted graphs.
Source: §1 · p. 2, §5 · p. 11Takeaways & Limitations
The approximation guarantee degrades with the quality of the Max-Uncut Bisection primitive, yielding a family of algorithms that can be analyzed rigorously and empirically.
Source: §1 · p. 2Even with an exact Max-Uncut Bisection algorithm, the analysis cannot yield better than .444.
Source: §3 · p. 4
Abstract
from arXiv · showhide
Hierarchical Clustering is an unsupervised data analysis method which has been widely used for decades. Despite its popularity, it had an underdeveloped analytical foundation and to address this, Dasgupta recently introduced an optimization viewpoint of hierarchical clustering with pairwise similarity information that spurred a line of work shedding light on old algorithms (e.g., Average-Linkage), but also designing new algorithms. Here, for the maximization dual of Dasgupta's objective (introduced by Moseley-Wang), we present polynomial-time .4246 approximation algorithms that use Max-Uncut Bisection as a subroutine. The previous best worst-case approximation factor in polynomial time was .336, improving only slightly over Average-Linkage which achieves 1/3. Finally, we complement our positive results by providing APX-hardness (even for 0-1 similarities), under the Small Set Expansion hypothesis.
1 Introduction
Hierarchical clustering represents data through nested clusters, but its analysis lacked a concrete objective until Dasgupta introduced one. This paper improves the approximation guarantee for the Moseley–Wang objective and establishes conditional hardness.
1 Introduction
- Hierarchical clustering recursively decomposes data into finer clusters, represented by a tree whose leaves are data points and internal nodes are clusters.Source: §1 · p. 1
- Dasgupta introduced an objective for hierarchical clustering, which previously lacked a concrete criterion beyond Single-Linkage’s combinatorial structure.The objective encourages similar points to remain together until lower levels of the tree.Source: §1 · pp. 1–2
- The algorithm combines Max-Uncut Bisection with Average-Linkage, guaranteeing .4246 of the optimum versus .3363 for the previous best approach.Its Max-Uncut Bisection primitive is used as a black box, and the guarantee degrades with the quality of that primitive.Source: §1 · p. 2
- Under the Small Set Expansion hypothesis, approximating the Moseley–Wang objective within a factor of (1 −ε) is NP-hard, even for 0-1 similarities..Source: §1 · p. 2
2 Preliminaries
The preliminaries specify the pairwise-similarity input and tree-based objective, then introduce Average-Linkage and Max-Uncut Bisection as components of the algorithm.
2 Preliminaries
- The input is an n × n matrix of nonnegative pairwise similarities, also represented as a weighted graph G(V, E, w).Source: §2 · p. 3
- For a tree T, the Moseley–Wang objective uses total graph weight W and has the trivial upper bound (n −2)W.Source: §2 · p. 3
- Average-Linkage repeatedly merges clusters with the highest average similarity and achieves a 1/3 approximation, tight in the worst case.Source: §2 · p. 3
- Max-Uncut Bisection splits a weighted graph into two sets to maximize the weight of edges left uncut; a polynomial-time .8776 approximation is known.Source: §2 · p. 3
- Average-Linkage’s worst-case tightness depends on a brittle pathological example, despite much better practical performance.Source: §2 · p. 3
- The proposed tree starts with a Max-Uncut Bisection split, then runs Average-Linkage separately on each side.Source: §2 · p. 4
3 0.4246 approximation for HC
The algorithm combines a Max-Uncut Bisection top split with Average-Linkage within each side to obtain a binary hierarchical-clustering tree. Its guarantee is at least 4ρ/[3(2ρ+1)] of optimum, or at least 0.4246 for ρ = 0.8776.
3 0.4246 approximation for HC
- Algorithm 2 uses Max-Uncut Bisection for the top split, then runs Average-Linkage within each side.The proof overview notes that recursive Max-Uncut Bisection leaves the approximation unchanged, but Average-Linkage is typically substantially more efficient.Source: §3 · p. 4, §3.1 · p. 4
3.1 Overview of the proof
- The proof divides an optimal binary tree into child subtrees A and B and the outside set C, then analyzes whether within-set or cross-set similarity weight is larger.The children each have at most n/2 leaves, while their parent subtree has more than n/2.Source: §3.1 · pp. 4–5
3.2 Proof of Theorem 3.1
- When within-set weight α is no greater than cross-set weight β, Average-Linkage alone gives a 4/9 approximation.This is the α ≤ β case of the proof.Source: §3.2 · p. 6
- When α ≥ β, a randomized balanced cut preserves expected uncut red-edge weight of (1 − δ)α and at least δβ of blue-edge weight.The resulting bound is α − (α − β)δmax(c), where δmax(c) = c(1 − 2c)/(1 − 3c²).Source: §3.2 · pp. 6–8
3 0.4246 approximation for HC
- 0.42469 is the proved lower bound on Algorithm 2’s approximation factor, using a ρ = 0.8776 Max-Uncut Bisection approximation.The bound is 4ρ/[3(2ρ+1)]; even exact Max-Uncut Bisection raises the analysis only to .444.Source: §3 · p. 4, §3.2 · p. 9
4 Hardness of Approximation
The Moseley-Wang hierarchical-clustering objective is APX-hard under the Small Set Expansion hypothesis, with hardness applying even to unweighted graphs. The proof obtains a constant gap between YES- and NO-case objective values.
4 Hardness of Approximation
- Under the Small Set Expansion hypothesis, approximating the Moseley-Wang objective within 1 − ε is NP-hard for some ε > 0.Source: §4 · p. 10
- The reduction builds a hierarchical-clustering instance from a graph, assigning weight 1 to edges and 0 to nonedges.For this instance, the total weight W equals the graph’s number of edges.Source: §4 · p. 10
- The proof separates YES- and NO-case objective values by a constant gap when ε is sufficiently small and q is sufficiently large.The respective bounds are nW(1 − 1/q − ε − o(ε)) and nW(1 − 2C√ε/9).Source: §4 · p. 11
5 Conclusion
The paper presents an approximation algorithm for the Moseley-Wang hierarchical-clustering objective and establishes hardness under the Small Set Expansion hypothesis.
5 Conclusion
- The paper gives a .4246 approximation algorithm using Max-Uncut Bisection and proves SSE-based hardness of approximation, even for unweighted graphs.Source: §5 · p. 11