Community Recovery on Noisy Stochastic Block Models

2025/05/13 by Washieu Anan, Anan, Washieu, G. Frank Liu +1
Physics and Astronomy · Computer Science · #Complex Network Analysis Techniques #Gaussian Processes and Bayesian Inference #Advanced Graph Neural Networks

paper · pdf · doi:10.48550/arxiv.2505.08251

Abstract

We study the problem of community recovery in geometrically-noised stochastic block models (SBM). This work presents two primary contributions: (1) Motif--Attention Spectral Operator (MASO), an attention-based spectral operator that improves upon traditional spectral methods; and (2) Iterative Geometric Denoising (GeoDe), a configurable denoising algorithm that boosts spectral clustering performance. We demonstrate that the fusion of GeoDe+MASO significantly outperforms existing community detection methods on noisy SBMs. Furthermore, we show that using GeoDe+MASO as a denoising step improves belief propagation's community recovery by 79.7% on the Amazon Metadata dataset.

Citations

• MixHop: Higher-Order Graph Convolutional Architectures via Sparsified\n Neighborhood Mixing
• The Geometric Block Model
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• On semidefinite relaxations for the block model
• Non-backtracking spectrum of random graphs: community detection and\n non-regular Ramanujan graphs
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Stochastic Block Models and Reconstruction
• Community detection in graphs
• Stochastic blockmodels: First steps
• The Rotation of Eigenvectors by a Perturbation. III

Related

• A spectral method for community detection in moderately-sparse degree-corrected stochastic block models
• Community Detection and Stochastic Block Models
• How Robust are Reconstruction Thresholds for Community Detection?
• Beyond Asymptotics: Practical Insights into Community Detection in Complex Networks
• Improved Community Detection using Stochastic Block Models