Research map / Learning theory and algorithms / Clustering
Efficient Centroid-Linkage 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.
Gives a subquadratic c-approximate centroid-linkage HAC algorithm built on a new dynamic ANNS structure robust to adaptive updates, and a practical DiskANN-based heap implementation that reaches up to 36x sequential speedup with comparable clustering quality.
Problem
Centroid-linkage hierarchical agglomerative clustering requires quadratic time in high dimensions, and existing subquadratic approximate methods for other linkages do not handle centroid linkage's non-monotone merge distances or the adaptive-update issue in dynamic nearest-neighbor search.
Approach
Reduce centroid-linkage HAC to dynamic approximate nearest-neighbor search over cluster centroids, and make the ANNS structure safe under adaptive updates via a merge-and-reduce scheme over LSH-based oblivious structures combined with a covering net for queries; in practice, replace the theory structure with a Vamana/DiskANN graph index that supports merging centroids by pruning neighbor unions.
Key results
- Dynamic ANNS for adaptive updates achieves O(c)-approximate queries with update time n^{1/c^2+o(1)} times log(Delta/beta) times d^2, and the merge-and-reduce reduction adds only an O(log n) factor to query and insertion time.
- At epsilon=0.1 the approximate centroid HAC's ARI and NMI are on average within 7% and 2% of exact centroid HAC across benchmark datasets.
- On a single core, the heap-based approximate centroid HAC achieves up to 36x speedup (average 5x) over fastcluster exact centroid HAC; with 192 threads, speedups reach up to 175x (average 22x).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use approximate Centroid HAC with epsilon 0.1 instead of exact Centroid HAC | Centroid-Linkage HAC · Benchmark datasets (Avg) | ARI: 0.453 -> 0.471 | No clear effect |
| Use approximate Centroid HAC with epsilon 0.1 instead of exact Centroid HAC | Centroid-Linkage HAC · Benchmark datasets (Avg) | NMI: 0.561 -> 0.564 | No clear effect |
| Use approximate Centroid HAC with epsilon 0.1 instead of exact Centroid HAC | Centroid-Linkage HAC · SIFT-1M slices (single thread) | speedup: average speed-up of 5×; max speed-up of 36× | Helped |
| Use approximate Centroid HAC with epsilon 0.1 instead of exact Centroid HAC | Centroid-Linkage HAC · SIFT-1M slices (192 threads) | speedup: average speed-up of 22×; max speed-up of 175× | Helped |
| Set epsilon to 0.2 instead of 0.1 (ablation) | Approximate Centroid HAC · Benchmark datasets (Avg) | ARI: 0.471 -> 0.465 | No clear effect |
| Set epsilon to 0.2 instead of 0.1 (ablation) | Approximate Centroid HAC · Benchmark datasets (Avg) | NMI: 0.564 -> 0.569 | No clear effect |
| Set epsilon to 0.4 instead of 0.1 (ablation) | Approximate Centroid HAC · Benchmark datasets (Avg) | ARI: 0.471 -> 0.452 | No clear effect |
| Set epsilon to 0.4 instead of 0.1 (ablation) | Approximate Centroid HAC · Benchmark datasets (Avg) | NMI: 0.564 -> 0.560 | No clear effect |
| Set epsilon to 0.8 instead of 0.1 (ablation) | Approximate Centroid HAC · Benchmark datasets (Avg) | ARI: 0.471 -> 0.467 | No clear effect |
| Set epsilon to 0.8 instead of 0.1 (ablation) | Approximate Centroid HAC · Benchmark datasets (Avg) | NMI: 0.564 -> 0.575 | No clear effect |
Surprising findings
- Centroid-linkage merge distances are non-monotone, so the minimum inter-cluster distance can shrink after merges, breaking assumptions used in prior subquadratic HAC analyses for Ward and average linkage.
- Prior subquadratic average- and Ward-linkage HAC analysis overlooked the adaptive-update issue, which the authors confirmed with the original authors.
Limitations
- The practical implementation uses DiskANN/Vamana, a heuristic ANNS with no theoretical approximation guarantee, so the '(1+epsilon)' label is not a true guarantee.
- The theoretical adaptive-update ANNS is not implemented; the experiments rely on the heuristic graph index.
- The bucket-based baseline performs many redundant NNS queries and fails to scale on a single thread.
Experimental setup
Datasets: iris wine cancer digits faces MNIST birds covertype SIFT-1M
Benchmarks: iris wine cancer digits faces MNIST birds SIFT-1M
Metrics: ARI NMI dendrogram purity Dasgupta cost running time speedup
Baselines: fastcluster exact centroid HAC bucket-based approximate centroid HAC exact centroid HAC via framework (epsilon=0)
Builds on: Abboud, Cohen-Addad and Houdrouge approximate HAC DiskANN ParlayANN FreshDiskANN locality-sensitive hashing
Closest papers by meaning
- New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering (ICML 2024 · similarity 0.88)
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.85)
- On the cohesion and separability of average-link for hierarchical agglomerative clustering (NeurIPS 2024 · similarity 0.85)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.85)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.85)
- Proportional Fairness in Non-Centroid Clustering (NeurIPS 2024 · similarity 0.85)
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.