Research map / Learning theory and algorithms / Clustering
Scalable and Effective Conductance-Based Graph Clustering
Longlong Lin, Ronghua Li, Tao Jia
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 |
|---|---|---|---|
| Use degree-ratio peeling instead of spectral clustering | PCon_de vs SC · DBLP, Youtube, Pokec, LJ, Orkut, Twitter | runtime (seconds): 56 -> 11; 552 -> 39; 165 -> 141; 14492 -> 345; 837 -> 577; 130570 -> 7655 | Improved |
| Use degree-ratio peeling instead of spectral clustering | PCon_de vs SC · DBLP | conductance: 0.009 -> 0.027 | Hurt |
| Use degree-ratio peeling instead of spectral clustering | PCon_de vs SC · Youtube, Pokec, LJ, Orkut, Twitter | conductance: 0.006 -> 0.004; 0.002 -> 0.001; 0.001 -> 0.000; 0.007 -> 0.006; 0.002 -> 0.000 | Improved |
| Use degeneracy ordering rather than degree-ratio scores | PCon_core vs PCon_de · Real-world graphs | runtime (seconds) | Improved |
| Use degeneracy ordering rather than degree-ratio scores | PCon_core vs PCon_de · Real-world graphs | conductance | Hurt |
| Use linear-space peeling algorithms instead of SC | PCon_core and PCon_de vs SC · Real-world graphs | memory overhead: 1.4 ∼ 7.8 times less memory | Improved |
| Increase diffusion parameter ε | NIBBLE_PPR and HK_Relax · Real-world graphs | conductance | Hurt |
Closest papers by meaning
- Online Sparsification of Bipartite-Like Clusters in Graphs (ICML 2025 · similarity 0.88)
- Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.85)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.85)
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs (ICLR 2024 · similarity 0.85)
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.85)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.85)
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.
