AI Paper Atlas

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

JMLR 2017 · Learning theory and algorithms › Clustering · approach: Correlation clustering · 147 citations (OpenAlex)

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 changedWhereMeasuredEffect
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 5Improved
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 nodesImproved
use simplified single-initialization refinement instead of per-node refinement (ablation)refinement algorithm · Simulated SBMsmisclassified nodesNo clear effect
add refinement to USC(inf)USC(inf) · Political blogs (1222 nodes)nodes misclassified: 383 -> 116Improved
add refinement to USC(2d)USC(2d) · Political blogs (1222 nodes)nodes misclassified: 583 -> 307Improved
add refinement to NSC(0)NSC(0) · Political blogs (1222 nodes)nodes misclassified: 579 -> 585No clear effect
add refinement to NSC(d)NSC(d) · Political blogs (1222 nodes)nodes misclassified: 308 -> 86Improved
iterate the simplified refinement until convergencesimplified refinement · Political blogs (1222 nodes)nodes misclassified: 86 -> 61, 58 or 63 out of 1222Improved
use regularization tau=2d for USC instead of no regularization in simulation (ablation)USC · Simulated balanced SBM (n=2500, k=10)misclassified nodesNo clear effect

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy