Research map / Learning theory and algorithms / Clustering
On the cohesion and separability of average-link for hierarchical 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.
Analyzes average-link hierarchical agglomerative clustering in metric spaces under interpretable cohesion and separability criteria (avg-min separation, max diameter, max average pairwise distance), proving logarithmic or constant guarantees and showing separations from single-linkage and complete-linkage, with experiments on 10 real datasets.
Problem
Existing theory for average-link hierarchical clustering relies on Dasgupta-style cost functions that do not separate average-link from a random hierarchy and are uninformative in metric spaces, and they do not describe cohesion/separability of the k-clusterings produced.
Approach
Replace Dasgupta-type objectives with interpretable k-clustering criteria (min/average inter-cluster avg distance for separability; max diameter and max average intra-cluster distance for cohesion) and prove average-link's approximation bounds for them in metric spaces, including separations from single-linkage, complete-linkage and random hierarchies.
Key results
- Average-link satisfies goodnessav <= 1 for every k (tight), while single-linkage and complete-linkage can be Omega(n) and Omega(sqrt(n)) worse and random hierarchies are unbounded.
- Average-link is O(log n)-approximate for goodnessdm, with lower bound Omega(log n / log log n) showing near tightness.
- Average-link's maximum diameter is at most min{k, 1+4 ln n} k^{log2 3} OPT_AVG, separating it from single-linkage when k = Omega(log^{2.41} n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use average-link instead of complete-linkage | Hierarchical agglomerative clustering · 10 real datasets, Euclidean metric; Small, Medium and Large k | costmin ratio to best: 0,82 -> 0,99; 0,81 -> 1; 0,81 -> 1 | Helped |
| Use average-link instead of the strongest baseline | Hierarchical agglomerative clustering · 10 real datasets, Euclidean metric; Small, Medium and Large k | costavg ratio to best: 0,94 -> 0,97; 1 -> 0,97; 1 -> 0,98 | Mixed |
| Use average-link instead of complete-linkage | Hierarchical agglomerative clustering · 10 real datasets, Euclidean metric; Small, Medium and Large k | maxdiamset ratio to best: 1 -> 0,85; 1 -> 0,8; 1 -> 0,76 | Hurt |
| Use average-link instead of complete-linkage | Hierarchical agglomerative clustering · 10 real datasets, Euclidean metric; Small, Medium and Large k | maxavgset ratio to best: 0,96 -> 0,95; 0,89 -> 0,99; 0,84 -> 0,99 | Mixed |
| Use average-link instead of complete-linkage | Hierarchical agglomerative clustering · 10 real datasets, Euclidean metric; Small, Medium and Large k | goodnessdm ratio to best: 0,92 -> 0,96; 0,97 -> 0,95; 0,99 -> 0,93 | Mixed |
| Use average-link instead of complete-linkage | Hierarchical agglomerative clustering · 10 real datasets, Euclidean metric; Small, Medium and Large k | goodnessav ratio to best: 0,82 -> 0,98; 0,73 -> 1; 0,68 -> 1 | Helped |
Surprising findings
- Every hierarchical clustering has a 1/2 approximation for the CKMM dissimilarity variant of Dasgupta's cost in metric spaces, so that objective cannot separate average-link from random hierarchies.
- Separability and cohesion criteria can conflict: a method bounded for max diameter must output a clustering with costavg only O(1/k) of optimum.
Limitations
- Metric-space assumption is needed for most results
- Experiments use only 10 datasets
- Several bounds are not tight
Experimental setup
Datasets: 10 real datasets (e.g., Airfoil, Banknote, Collins)
Benchmarks: 10 real-world datasets with Euclidean metric
Metrics: costmin costavg maxdiam maxavg goodnessdm goodnessav
Baselines: single-linkage complete-linkage random hierarchy
Builds on: Dasgupta's cost function Cohen-Addad et al. linkage analysis for maximum diameter
Closest papers by meaning
- New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering (ICML 2024 · similarity 0.94)
- Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search (NeurIPS 2017 · similarity 0.91)
- Hierarchical Agglomerative Clustering via Relaxed Representatives (NeurIPS 2026 · similarity 0.90)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.87)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.87)
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.86)
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.