Research map / Learning theory and algorithms / Clustering
Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs
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 |
|---|---|---|---|
| Replace arbitrary-vertex bucketing with SpecWRSC (spectral clustering + degree bucketing + WRSC) versus MS, Linkage++, AverageLinkage | Hierarchical clustering on real-world datasets · Iris, Wine, Cancer, Newsgroup | running time: lowest of four methods on all datasets | Helped |
| SpecWRSC algorithm versus MS and Linkage++ baselines | Dasgupta cost on real-world datasets · Iris, Wine, Cancer, Newsgroup | Dasgupta cost: lower cost than MS and Linkage++ (figure only) | Helped |
| SpecWRSC on GEMSEC Facebook artist graph | Scalability · GEMSEC Facebook artist (50,515 nodes) | running time: only method finishing within 12 hours | Helped |
| SpecWRSC on synthetic SBM with 100,000 nodes | Scalability · SBM n=100,000 | running time: finishes in ~4 hours while all others time out after 12 hours | Helped |
| Spectral-gap condition: SpecWRSC benefits when lambda_{k+1}/lambda_k is large | SpecWRSC on real-world datasets · Iris, Wine, Cancer, Newsgroup | Dasgupta cost relative to gap | Mixed |
Closest papers by meaning
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.90)
- Learning-Augmented Hierarchical Clustering (ICML 2025 · similarity 0.90)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.89)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.88)
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.87)
- From Logits to Hierarchies: Hierarchical Clustering made Simple (ICML 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.