Source-linked AI summary
A cost function for similarity-based hierarchical clustering
Sanjoy Dasgupta
TL;DR
Hierarchical clustering has lacked precise objective functions, despite the value of explicit costs for defining and comparing algorithms. The paper introduces a tree cost based on pairwise similarities, shows sensible behavior on canonical instances, and gives a top-down procedure with a provably good approximation ratio.
Problem
Hierarchical clustering methods are often specified procedurally rather than by precise objective functions, making their targets difficult to characterize and compare.
Method
The paper defines a cost function that assigns a score to each hierarchy from pairwise similarities represented as a weighted graph.
Results
The criterion behaves sensibly on canonical instances and admits a provably good top-down approximation procedure, although optimizing it exactly is NP-hard.
Takeaways & Limitations
The cost function provides a concrete optimization problem for hierarchical clustering and gives theoretical justification for a widely used recursive graph-partitioning heuristic.
Takeaways & Limitations
The procedure assumes pairwise similarities as input, represented as a weighted graph, and the resulting optimization problem is NP-hard.
Abstract
from arXiv · showhide
The development of algorithms for hierarchical clustering has been hampered by a shortage of precise objective functions. To help address this situation, we introduce a simple cost function on hierarchies over a set of points, given pairwise similarities between those points. We show that this criterion behaves sensibly in canonical instances and that it admits a top-down construction procedure with a provably good approximation ratio.
1 Introduction
The paper addresses the lack of precise objective functions for hierarchical clustering by introducing a similarity-based cost function and studying its optimization. The criterion behaves sensibly on canonical examples and supports a provably good top-down approximation procedure.
- 1 Introduction: Hierarchical clustering represents data through a rooted tree, avoiding a fixed cluster count and capturing structure at multiple granularities.Leaves correspond to data points, while internal nodes represent clusters of descendant leaves.
- 1 Introduction: Existing methods such as single, average, and complete linkage are widely used but are specified procedurally rather than through explicit objective functions.This leaves the kinds of clusters they find insufficiently transparent.
- 1 Introduction: Explicit cost functions make problem definitions precise, support complexity analysis and algorithm comparison, and can incorporate prior information or requirements.Such requirements can be represented as constraints or regularization terms.
- 1 Introduction: The paper introduces a cost function that scores any tree using pairwise similarities between data points.The authors study which hierarchies it favors through lemmas and canonical examples.
- 1 Introduction: The cost function is NP-hard to optimize but admits a provably good approximation through a simple top-down heuristic.The heuristic has variants widely used in graph partitioning.
- 1 Introduction: Related work includes phylogenetic cost functions, statistical consistency analyses, and evaluations that truncate hierarchies for flat-clustering objectives.This paper instead treats the hierarchy itself as the object to optimize.
2 The cost function and its basic properties
The proposed objective scores rooted trees from pairwise similarity graphs by penalizing similarities cut higher in the hierarchy. Its basic properties include a cut-based interpretation, existence of an optimal binary tree, and separation of disconnected components at the top.
- 2 The cost function and its basic properties: The input is a weighted graph whose vertices are data points and whose positive edge weights encode pairwise similarities.Edges connect pairs of similar points; unit weights may be assumed when weights are omitted.
- 2 The cost function and its basic properties: For any rooted tree with data points as leaves, the lowest common ancestor of two leaves identifies the smallest subtree containing both points.This subtree determines where their similarity edge is separated.
- 2 The cost function and its basic properties: The cost penalizes similarity edges according to how high they are cut, assigning smaller penalties when edges are separated deeper in the tree.An edge cut at the root incurs penalty n, while a cut in a subtree containing α fraction of the data incurs αn for unit weight.
- 2.1 Two interpretations of the cost function: Equivalently, each binary split S → (S1, S2) contributes |S|w(S1, S2), and the tree cost sums these splitting costs over internal nodes.The same construction extends to k-ary splits.
- 2.1 Two interpretations of the cost function: The objective seeks a hierarchy that minimizes the average distance between similar points.The tree also induces an ultrametric distance, and the cost can be expressed using weighted pairwise distances up to an additive constant.
- 2.3 The optimal tree is binary: There always exists an optimal tree that is binary.Replacing a subtree preserves the surrounding structure while enabling cost comparisons through the sum-of-splits formulation.
- 2.4 Different connected components must first be split apart: When the similarity graph has multiple connected components, an optimal hierarchy separates those components before making cuts within them.An optimal subtree whose induced graph is disconnected must have a top split of zero cut weight.
3 Illustrative examples
The cost function behaves sensibly on canonical graphs: balanced recursive splits are favored on a line, all trees tie on a complete graph, and planted clusters are separated before within-cluster edges are cut. For planted partitions, near-optimal trees respect the planted structure with high probability.
- The line: On a line, the best hierarchy splits as evenly as possible, with cost C(n) = n log_2 n + O(n).Single-edge splits suffice, and the recurrence is C(n) = n + min_{1≤j≤n−1} C(j) + C(n−j).
- The complete graph: On the complete graph with unit edge weights, every tree on n leaves has exactly the same cost.This equality is also used later in the planted-partition analysis.
- Planted partitions: For general planted partitions, an expected-cost minimizer cuts all intercluster edges before cutting any edge within a cluster.The associated weighted graph has connected components corresponding to the planted clusters.
- Planted partitions: In the simple planted partition model, non-ϵ-good trees have expected cost exceeding that of a top-level planted-cluster split by more than 1.The result applies for 0 < ϵ < 1/6 and p > q.
- Planted partitions: With high probability, a cost-minimizing tree in the simple planted partition model misplaces at most an O((ln n)/n) fraction of the data.The analysis compares expected-cost separation with fluctuations caused by the random graph.
4 Hardness of finding the optimal clustering
The paper proves that optimizing the proposed hierarchical-clustering cost is NP-hard, using a reduction from a restricted not-all-equal satisfiability problem. The construction links high-cost trees to satisfying assignments and shows that maximization and minimization are equivalent under graph complementation.
- Complementation: Maximizing cost(T) on a graph is equivalent to minimizing cost(T) on its complement, with an analogous relation for complementary edge weights.Thus hardness for the maximization formulation transfers to minimization.
- Reduction to NAESAT∗: NAESAT∗ uses CNF clauses of size two or three, with each variable appearing once in a 3-clause and twice with opposite polarities in 2-clauses.Its question is whether every clause has at least one satisfied and one unsatisfied literal.
- Reduction to NAESAT∗: The reduction preserves satisfiability: the transformed formula φ′ is not-all-equal satisfiable if and only if the original formula φ is.Agreement among duplicated variables is enforced by added clauses.
- Reduction to NAESAT∗: NP-hardness of maximizing cost(T) is established through a polynomial-time reduction from NAESAT∗.The reduction constructs a weighted graph G and threshold M such that φ is not-all-equal satisfiable exactly when some tree has costG(T) ≥ M.
- Graph construction: The constructed graph has 2n vertices, one for each positive or negative literal, with edges divided into three categories.The threshold argument analyzes the costs of the top split and subsequent splits in this graph.
- Cost correspondence: For a satisfying assignment, the constructed tree has costG(T) = 10nm + 4nm′ + 2n^2W.The top split cuts all but one edge per triangle, and the remaining edges are cut at the second level.
- Cost correspondence: Conversely, any tree reaching the threshold induces a balanced literal partition that yields a not-all-equal satisfying assignment.The top split must separate opposite literal copies and cut all other edges except the unavoidable one per triangle.
5 A greedy approximation algorithm
The paper develops a greedy top-down heuristic that recursively chooses approximate sparsest cuts. Its returned tree has cost at most O(α_n log n) times optimal, where α_n is the cut-approximation ratio.
- Split criterion: The split cost is |V| · w(S, V \ S), so smaller resulting clusters reduce the multipliers applied to later recursive splits.This motivates maximizing shrinkage per unit cut cost.
- Split criterion: The heuristic recursively splits V into S and V \ S using an approximate minimizer of w(S, V \ S) / (|S| · |V \ S|).This ratio is the sparsest-cut objective, balancing cut weight against expected cluster shrinkage.
- Approximate cuts: Sparsest cut is NP-hard to optimize, but available approximation algorithms provide an α_n-approximation; the Leighton–Rao algorithm has α_n = O(log n).The analysis assumes α_n is positive and nondecreasing with n.
- Approximation guarantee: The resulting algorithm returns a tree of cost at most O(α_n log n) times optimal.The induction combines the approximate top split with recursively constructed trees on the two sides.
- Approximation analysis: Every tree contains a balanced partition A, B with |V|/3 ≤ |A|, |B| ≤ 2|V|/3 and a bounded sparsest-cut ratio.The proof aggregates cuts along a root-to-leaf path until one side reaches one-third of the vertices.
- Approximation analysis: The proof bounds the optimal costs of the induced subgraphs by restricting the optimal tree’s cuts to each side of the top partition.The restricted trees’ combined split costs are no greater than the corresponding costs in the original optimal tree.
6 A generalization of the cost function
The paper generalizes the cost by replacing cluster size with a strictly increasing function f of that size. The earlier structural properties persist, but complete-graph trees can differ in cost.
- Generalized objective: The generalized cost preserves the properties developed earlier, with f(|S|) replacing |S| where appropriate.This extends the framework beyond the original linear cluster-size weighting.
- Canonical behavior: For a complete graph on four nodes, different tree shapes need not have the same generalized cost.The equality of all tree costs for the clique is therefore not preserved for arbitrary f.
K4 T1 T2
For the generalized objective, the heuristic selects an approximate balanced cut using f-weighted cluster sizes. The approximation analysis is modified accordingly, and the K4 comparison depends on whether f is concave or convex.
- K4 comparison: For the K4 example, T1 is preferable when f is concave, while T2 is preferable when f is convex.The comparison follows from f(2) + f(4) ≤ 2f(3) in the concave case.
- Modified heuristic: The modified heuristic approximately minimizes w(S, V \ S) / min(f(|S|), f(|V \ S|)) subject to a balanced split.The selected partition satisfies |V|/3 ≤ |A|, |B| ≤ 2|V|/3.
- Generalized analysis: A balanced partition exists with w(A, B) / min(f(|A|), f(|B|)) bounded by cost(T) divided by f(⌊2n/3⌋)f(⌈n/3⌉).This is the generalized analogue of the sparsest-cut lemma.
- Generalized analysis: The generalized top-down procedure is analyzed by induction using the modified split bound and restricted optimal trees on the two subgraphs.Monotonicity of f is used in the top-level inequality.
- Generalized analysis: The recursive costs combine with the top split through the bound (c_n ln n)cost(T∗).The displayed derivation uses the corresponding inductive bounds for the two recursively solved sides.