Research map / Graph learning / Graph algorithms and clustering
Statistical guarantees for local graph clustering
Wooseok Ha, Kimon Fountoulakis, Michael W. Mahoney
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 l1-reg. PR output with BFS expansion as SimpleLocal input (ablation) | SimpleLocal · PPI-mips (Actin) | F1score: 0.98 -> 0.04 | Hurt |
| replace l1-reg. PR output with BFS expansion as SimpleLocal input (ablation) | SimpleLocal · Sfld (urease) | F1score: 0.38 -> 0.42 | Hurt |
| add SimpleLocal refinement on top of l1-reg. PR (ablation) | l1-reg. PR · Sfld (urease) | F1score: 0.75 -> 0.38 | Hurt |
| add SimpleLocal refinement on top of l1-reg. PR (ablation) | l1-reg. PR · PPI-mips (RNA) | F1score: 0.87 -> 0.80 | Hurt |
| add SimpleLocal refinement on top of l1-reg. PR (ablation) | l1-reg. PR · PPI-mips (Spindle) | F1score: 0.85 -> 0.82 | Hurt |
| add SimpleLocal refinement on top of l1-reg. PR (ablation) | l1-reg. PR · PPI-mips (mc-complex) | F1score: 0.78 -> 0.79 | Improved |
| add SimpleLocal refinement on top of l1-reg. PR (ablation) | l1-reg. PR · PPI-mips (most clusters) | F1score | No clear effect |
| use APPR instead of l1-reg. PR | l1-reg. PR · Orkut (282 clusters) | F1score | No clear effect |
| use APPR instead of l1-reg. PR | l1-reg. PR · Orkut (282 clusters) | running time: 75 hours | No clear effect |
| increase conductance of target cluster toward 0.4 | l1-reg. PR · Orkut (282 clusters) | F1score: around 0.8 | Hurt |
| select solution by minimum conductance instead of best F1 (ablation) | l1-reg. PR with stagewise path · SBM (10 clusters of 20 nodes, p=0.5) | F1score | Mixed |
| increase stagewise step size eta (ablation) | stagewise l1-reg. PR path · SBM (n=1000, p=0.5, q=0.002) | path approximation: 7706, 1527, 764 iterations | Mixed |
Closest papers by meaning
- Statistical Guarantees for Local Spectral Clustering on Random Neighborhood Graphs (JMLR 2021 · similarity 0.86)
- Local Graph Clustering with Noisy Labels (ICLR 2024 · similarity 0.85)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.83)
- Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.83)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.83)
- Multi-View Stochastic Block Models (ICML 2024 · similarity 0.83)
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.
