Research map / Learning theory and algorithms / Clustering
New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Improves upper bounds on the maximum diameter of complete-linkage (to k^1.59 OPT_avg and k^1.30 OPT_dim, and 2k-2 for k<=4) and extends an analogous cohesion bound to average-linkage and minimax.
Problem
Theoretical approximation guarantees of linkage methods (complete-linkage, single-linkage, average-linkage, minimax) for hierarchical clustering with respect to the maximum diameter and cohesion criteria of k-clusterings in metric spaces.
Approach
Track a dynamic partition of complete-linkage clusters into families bounded via a target k-clustering, and use a graph/forest of families with a "pure cluster" accounting that merges families in connected components to get a tighter recursive diameter bound; the same analysis extends to any linkage whose merge function and cohesion criterion align.
Key results
- Complete-linkage's maximum diameter is at most k^1.59 OPT_avg (avg-diameter optimum), improving on the prior O(k^1.59 OPT_dim) bound since OPT_avg <= OPT_dim.
- Complete-linkage's maximum diameter is at most (2k-2) OPT_dim for k<=4 and k^1.30 OPT_dim for k>4, narrowing the gap to the Omega(k OPT_dim) lower bound.
- An instance shows single-linkage can produce a cluster of diameter Omega(k^2 OPT_avg), separating it from complete-linkage in the OPT_avg measure.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Bound complete-linkage maximum diameter using OPTAVGK instead of OPTDIMK | Complete-linkage · Metric spaces, arbitrary k | maximum cluster diameter upper bound: k^{1.59} \OPTAVGK; previous bound: O(k^{1.59}\OPTDIMK) | Helped |
| Use the tighter OPTDIMK-based analysis | Complete-linkage · Metric spaces, k > 4 | maximum cluster diameter upper bound: k^{1.30}\OPTDIMK | Helped |
| Use the tighter OPTDIMK-based analysis | Complete-linkage · Metric spaces, k ≤ 4 | maximum cluster diameter upper bound: (2k-2) \OPTDIMK | Helped |
| Compare maximum diameter against OPTAVGK | Complete-linkage versus single-linkage · Metric spaces, arbitrary k | maximum cluster diameter: k^{1.59} \OPTAVGK versus \Omega( k^2 \OPTAVGK) | Helped |
| Bound average pairwise cluster distance by OPTAVGK | Average-linkage · Metric spaces, arbitrary k | average pairwise distance: k^{1.59} \OPTAVGK | Helped |
| Bound cluster radius by OPTAVGK | Minimax · Metric spaces, arbitrary k | cluster radius: k^{1.59} \OPTAVGK | Helped |
Surprising findings
- With OPT_dim as the reference, complete-linkage and single-linkage have the same order of worst-case diameter approximation, so the separation only appears with OPT_avg.
Limitations
- Bounds for large k remain far from the Omega(k OPT_dim) lower bound (k^1.30 vs k).
- Analysis of average-linkage and minimax yields only k^1.59 OPT_avg bounds, without tight matching lower bounds.
- The paper leaves tight bounds for complete-linkage in terms of OPT_avg or OPT_dim as an open question.
Experimental setup
Metrics: maximum diameter approximation factor average pairwise distance (cohesion)
Baselines: complete-linkage prior bound O(k^1.59 OPT_dim) single-linkage minimax average-linkage
Builds on: complete-linkage analysis of Ackermann et al. (k^2 bound) single-linkage lower bounds minimax linkage
Closest papers by meaning
- On the cohesion and separability of average-link for hierarchical agglomerative clustering (NeurIPS 2024 · similarity 0.94)
- Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search (NeurIPS 2017 · similarity 0.92)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.88)
- Efficient Centroid-Linkage Clustering (NeurIPS 2024 · similarity 0.88)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.87)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.