Research map / Learning theory and algorithms / Clustering
Achieving Optimal Misclassification Proportion in Stochastic Block Models
Chao Gao, Zongming Ma, Anderson Y. Zhang, Harrison H. Zhou
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 |
|---|---|---|---|
| add the refinement stage after spectral initialization (balanced simulation) | USC/NSC initializers · Simulated balanced SBM (n=2500, k=10) | misclassified nodes: from around 30 to around 5 | Improved |
| add the refinement stage after spectral initialization (sparse simulation) | USC/NSC initializers · Simulated sparse SBM (n=4000, k=10) | misclassified nodes: reduces the number of misclassified nodes by 50% | Improved |
| add the refinement stage after spectral initialization (imbalanced simulation) | USC/NSC initializers · Simulated imbalanced SBM (n=2000, k=4) | misclassified nodes | Improved |
| use simplified single-initialization refinement instead of per-node refinement (ablation) | refinement algorithm · Simulated SBMs | misclassified nodes | No clear effect |
| add refinement to USC(inf) | USC(inf) · Political blogs (1222 nodes) | nodes misclassified: 383 -> 116 | Improved |
| add refinement to USC(2d) | USC(2d) · Political blogs (1222 nodes) | nodes misclassified: 583 -> 307 | Improved |
| add refinement to NSC(0) | NSC(0) · Political blogs (1222 nodes) | nodes misclassified: 579 -> 585 | No clear effect |
| add refinement to NSC(d) | NSC(d) · Political blogs (1222 nodes) | nodes misclassified: 308 -> 86 | Improved |
| iterate the simplified refinement until convergence | simplified refinement · Political blogs (1222 nodes) | nodes misclassified: 86 -> 61, 58 or 63 out of 1222 | Improved |
| use regularization tau=2d for USC instead of no regularization in simulation (ablation) | USC · Simulated balanced SBM (n=2500, k=10) | misclassified nodes | No clear effect |
Closest papers by meaning
- Determining the Number of Communities in Degree-corrected Stochastic Block Models (JMLR 2021 · similarity 0.91)
- Community Detection and Stochastic Block Models: Recent Developments (JMLR 2018 · similarity 0.91)
- Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information (JMLR 2020 · similarity 0.90)
- Community models for networks observed through edge nominations (JMLR 2023 · similarity 0.90)
- Optimal Cluster Recovery in the Labeled Stochastic Block Model (NeurIPS 2016 · similarity 0.89)
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting (JMLR 2019 · 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.
