Research map / Learning theory and algorithms / Clustering
Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use dynamic low-outdegree orientation to limit how many average-linkage edge weights need updating | Exact average-linkage HAC · Arbitrary sparse graphs | time complexity: \tilde{O}(n\sqrt{m}) | Helped |
| Use bounded staleness and rebuilds instead of eagerly updating all average-linkage weights | Approximate average-linkage HAC · SNAP real-world graphs | runtime: 6.9x | Helped |
| Use the graph-based framework for single-, complete-, and WPGMA-linkage | Graph-based HAC · SNAP real-world graphs | speedup: up to 730x | Helped |
| Cluster an approximate k-NN graph rather than run metric HAC directly | Graph-based HAC · Fashion-MNIST (60,000 points) | end-to-end runtime: 20.7x | Helped |
| Use graph-based approximate average-linkage with an approximate k-NN graph | Graph-based HAC · Iris, wine, digits, cancer, and faces | Adjusted Rand-Index: 1.8% better | Helped |
| Use graph-based approximate average-linkage with an approximate k-NN graph | Graph-based HAC · Iris, wine, digits, cancer, and faces | Normalized Mutual Information: 0.5% better | Helped |
| Use approximate rather than simple-exact average-linkage | Average-linkage HAC · Digits | Adjusted Rand-Index and Normalized Mutual Information: less than 1% better | Hurt |
| Replace metric HAC with graph-based approximate average-linkage | Graph-based HAC · NYTimes | end-to-end speedup: up to 36.2x | Helped |
| Replace metric HAC with graph-based approximate average-linkage | Graph-based HAC · Last.fm | end-to-end speedup: 76.5x | Helped |
| Use approximate graph-based complete-linkage on a k-NN graph missing long-distance edges | Complete-linkage HAC · Iris, wine, digits, cancer, and faces | clustering quality | Hurt |
| Use complete-linkage on the complete graph instead of the k-NN graph | Complete-linkage HAC · Classification datasets | clustering quality | Helped |
Closest papers by meaning
- New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering (ICML 2024 · similarity 0.91)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.90)
- Efficient Centroid-Linkage Clustering (NeurIPS 2024 · similarity 0.90)
- On the cohesion and separability of average-link for hierarchical agglomerative clustering (NeurIPS 2024 · similarity 0.90)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.88)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.88)
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.