Research map / Learning theory and algorithms / Clustering
A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph 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 near-linear time O(1)-approximation for balanced cut in the semi-random monotone random-cut model (and an extension to Dasgupta's hierarchical clustering objective), by replacing the slow SDP-based heavy-vertex removal with approximate subsampling-based removal inside a matrix multiplicative weights framework.
Problem
Balanced cut (and Dasgupta hierarchical clustering) in the semi-random monotone random-cut model; prior polynomial-time algorithms require solving many SDPs and are too slow for near-linear time.
Approach
Approximate heavy-vertex removal via subsampling (accepting balls of radius sqrt(2)·delta) combined with a probabilistic low-width separation oracle that exploits geometric expansion, so that matrix multiplicative weights can run with infeasible SDP solutions in near-linear time.
Key results
- Algorithm outputs an Omega(a)-balanced cut of value O(n^2 eta) in time O(|V|^{1+o(1)} + |E|^{1+o(1)}) with probability 1-o(1), matching the error guarantee of the slow MMW algorithm.
- Requires eta >= Omega((log n)^2 (log log n)^2 / n), compared to (sqrt(log n)(log log n)^2)/n for the slow algorithm.
- Gives a near-linear time O(1)-approximation to Dasgupta's objective for the semi-random hierarchical SBM with p_min = Omega(log n / n^{2/3}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the near-linear algorithm instead of the prior semi-random balanced-cut algorithm | Semi-random balanced cut · Semi-random balanced cut | running time: \Omega(n^3) -> O(|V(G)|^{1+o(1)} + |E(G)|^{1+o(1)}) | Helped |
| Use the near-linear algorithm instead of the prior semi-random balanced-cut algorithm | Semi-random balanced cut · Semi-random balanced cut | cut approximation: O(\alpha) -> O(n^2\cdot \eta) | No clear effect |
| Extend the approach to semi-random hierarchical stochastic block model inputs | Near-linear algorithm · Semi-random hierarchical stochastic block model | Dasgupta objective | Helped |
| Require the denser cut regime for the near-linear-time guarantee | Near-linear balanced-cut algorithm · Semi-random balanced cut | minimum cut density: \Omega((\log n)^2\cdot(\log\log n)^2/n) vs. \Omega((\sqrt{\log n}\cdot(\log\log n)^2)/n) | Hurt |
Limitations
- Density requirement eta >= (log n)^2 (log log n)^2 / n is stronger than the prior algorithm's requirement, and the authors leave open what density is necessary.
- Matches the prior algorithm's error guarantees only in the near-linear time setting; not competitive with practical bisection heuristics yet.
- Analysis is theoretical with no experiments.
Experimental setup
Metrics: cut value approximation factor running time
Baselines: Makarychev-Makarychev-Vijayaraghavan 2012 algorithm
Builds on: Makarychev-Makarychev-Vijayaraghavan semi-random balanced cut algorithm matrix multiplicative weights for SDPs Dasgupta hierarchical clustering objective almost-linear time maximum flow
Closest papers by meaning
- Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs (NeurIPS 2021 · similarity 0.91)
- Hierarchical Clustering Beyond the Worst-Case (NeurIPS 2017 · similarity 0.90)
- On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models (NeurIPS 2024 · similarity 0.88)
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better (ICML 2024 · similarity 0.88)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.88)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (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.