# Optimal Inference in Contextual Stochastic Block Models

arXiv: https://arxiv.org/abs/2306.07948 · HTML: https://mlsanity.com/paper/2306.07948/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 31 references that are in the map.
- First posted on arXiv 6 Jun 2023.

## Builds on (most cited first, 19 of 19)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Design Space for Graph Neural Networks](https://mlsanity.com/paper/2011.08843/) (2020)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [p-Laplacian Based Graph Neural Networks](https://mlsanity.com/paper/2111.07337/) (2021)
- [Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula](https://mlsanity.com/paper/1606.04142/) (2016)
- [EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks](https://mlsanity.com/paper/2205.13892/) (2022)
- [Contextual Stochastic Block Model: Sharp Thresholds and Contiguity](https://mlsanity.com/paper/2011.09841/) (2020)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering](https://mlsanity.com/paper/1610.02918/) (2016)
- [Homophily modulates double descent generalization in graph convolution networks](https://mlsanity.com/paper/2212.13069/) (2022)
- [Optimality of Message-Passing Architectures for Sparse Graphs](https://mlsanity.com/paper/2305.10391/) (2023)
- [Covariate Regularized Community Detection in Sparse Graphs](https://mlsanity.com/paper/1607.02675/) (2016)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [Learnable Graph Convolutional Attention Networks](https://mlsanity.com/paper/2211.11853/) (2022)
- [On Classification Thresholds for Graph Attention with Edge Features](https://mlsanity.com/paper/2210.10014/) (2022)
- [Neural-prior stochastic block model](https://mlsanity.com/paper/2303.09995/) (2023)

## Built on by (most cited first, 12 of 12)

- [Joint Graph Rewiring and Feature Denoising via Spectral Resonance](https://mlsanity.com/paper/2408.07191/) (2024)
- [Spectral Thresholds in Correlated Spiked Models and Fundamental Limits of Partial Least Squares](https://mlsanity.com/paper/2510.17561/) (2025)
- [Asymptotic generalization error of a single-layer graph convolutional network](https://mlsanity.com/paper/2402.03818/) (2024)
- [Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models](https://mlsanity.com/paper/2412.15496/) (2024)
- [Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model](https://mlsanity.com/paper/2503.01361/) (2025)
- [Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networks](https://mlsanity.com/paper/2402.07340/) (2024)
- [Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks](https://mlsanity.com/paper/2412.13754/) (2024)
- [Is Noise Conditioning Necessary? A Unified Theory of Unconditional Graph Diffusion Models](https://mlsanity.com/paper/2505.22935/) (2025)
- [How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?](https://mlsanity.com/paper/2506.11869/) (2025)
- [Inference in Spreading Processes with Neural-Network Priors](https://mlsanity.com/paper/2509.02073/) (2025)
- [HoTS: Homophily-Aware Temperature Scaling for Graph Neural Network Calibration](https://mlsanity.com/paper/2609.32426/) (2026)
- [PATTERN Can Be Solved from Memory: Generator-Aware Baselines for Synthetic Node Classification](https://mlsanity.com/paper/2610.15020/) (2026)

## Abstract (arXiv)

The contextual stochastic block model (cSBM) was proposed for unsupervised community detection on attributed graphs where both the graph and the high-dimensional node information correlate with node labels. In the context of machine learning on graphs, the cSBM has been widely used as a synthetic dataset for evaluating the performance of graph-neural networks (GNNs) for semi-supervised node classification. We consider a probabilistic Bayes-optimal formulation of the inference problem and we derive a belief-propagation-based algorithm for the semi-supervised cSBM; we conjecture it is optimal in the considered setting and we provide its implementation. We show that there can be a considerable gap between the accuracy reached by this algorithm and the performance of the GNN architectures proposed in the literature. This suggests that the cSBM, along with the comparison to the performance of the optimal algorithm, readily accessible via our implementation, can be instrumental in the development of more performant GNN architectures.