mlsanityData to 7 Oct 2026

Optimal Inference in Contextual Stochastic Block Models

arXiv 2306.07948 ↗First posted 6 Jun 2023cs.SI cs.LGcited by 11

Not on the map. Why?

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.

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

Builds on

19 of 31 references.

References · 19

  1. 2017Community Detection and Stochastic Block Modelscited by 317
  2. 2020Design Space for Graph Neural Networkscited by 182
  3. 2018Contextual Stochastic Block Modelscited by 134
  4. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  5. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  6. 2022A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networkscited by 49
  7. 2021p-Laplacian Based Graph Neural Networkscited by 39
  8. 2016Mutual information for symmetric rank-one matrix estimation: A proof of the replica formulacited by 26
  9. 2022EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networkscited by 26
  10. 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
  11. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
  12. 2016Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clusteringcited by 13
7 more
  1. 2022Homophily modulates double descent generalization in graph convolution networkscited by 13
  2. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  3. 2016Covariate Regularized Community Detection in Sparse Graphscited by 12
  4. 2021An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guaranteescited by 10
  5. 2022Learnable Graph Convolutional Attention Networkscited by 8
  6. 2022On Classification Thresholds for Graph Attention with Edge Featurescited by 5
  7. 2023Neural-prior stochastic block modelcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 5; 2026: 1.

11 papers.

  1. 2024Joint Graph Rewiring and Feature Denoising via Spectral Resonancecited by 11
  2. 2025Spectral Thresholds in Correlated Spiked Models and Fundamental Limits of Partial Least Squarescited by 4
  3. 2024Asymptotic generalization error of a single-layer graph convolutional networkcited by 3
  4. 2024Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Modelscited by 2
  5. 2025Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block modelcited by 2
  6. 2024Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networkscited by 0
  7. 2024Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networkscited by 0
  8. 2025Is Noise Conditioning Necessary? A Unified Theory of Unconditional Graph Diffusion Modelscited by 0
  9. 2025How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?cited by 0
  10. 2025Inference in Spreading Processes with Neural-Network Priorscited by 0
  11. 2026HoTS: Homophily-Aware Temperature Scaling for Graph Neural Network Calibrationcited by 0