Research map / Learning theory and algorithms / Clustering
Hierarchical Clustering: $O(1)$-Approximation 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 |
|---|---|---|---|
| Use degree-ordered recursive splits to construct a tree on high-conductance graphs | Hierarchical clustering under Dasgupta's cost · Expander graphs | approximation ratio: O(1) | Helped |
| Use PruneMerge rather than directly merging cluster trees from the partition | Hierarchical clustering on well-clustered graphs · Well-clustered graphs | approximation ratio: O(k^{22}/λ_{k+1}^{10}) | Helped |
| Directly merge the degree-based trees for the partition clusters without pruning | Hierarchical clustering on the constructed two-cluster example · Two planted-clique expander clusters with crossing edges | approximation ratio: Ω(n^{0.1}) | Hurt |
| Use the proposed algorithm instead of the previous state-of-the-art | Well-clustered graph hierarchical clustering · Synthetic graphs with unequal-size clusters and embedded cliques | hierarchical clustering cost reduction: up to 50% | Helped |
| Use the proposed algorithm instead of the previous state-of-the-art | Well-clustered graph hierarchical clustering · Stochastic block models | hierarchical clustering cost | Helped |
Closest papers by meaning
- Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs (ICML 2023 · similarity 0.93)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.92)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.91)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.89)
- Online Sparsification of Bipartite-Like Clusters in Graphs (ICML 2025 · similarity 0.89)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.89)
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.