# Neural-prior stochastic block model

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 42 references that are in the map.
- First posted on arXiv 17 Mar 2023.

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

- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Deep Learning Techniques for Inverse Problems in Imaging](https://mlsanity.com/paper/2005.06001/) (2020)
- [Model-Based Deep Learning](https://mlsanity.com/paper/2012.08405/) (2020)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Entropy and mutual information in models of deep neural networks](https://mlsanity.com/paper/1805.09785/) (2018)
- [Community Detection in Networks with Node Attributes](https://mlsanity.com/paper/1401.7267/) (2014)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Graph-based Approximate Message Passing Iterations](https://mlsanity.com/paper/2109.11905/) (2021)
- [Covariate-assisted spectral clustering](https://mlsanity.com/paper/1411.2158/) (2014)
- [Bayesian stochastic blockmodeling](https://mlsanity.com/paper/1705.10225/) (2017)
- [Contextual Stochastic Block Model: Sharp Thresholds and Contiguity](https://mlsanity.com/paper/2011.09841/) (2020)
- [The spiked matrix model with generative priors](https://mlsanity.com/paper/1905.12385/) (2019)
- [Learning curves for the multi-class teacher-student perceptron](https://mlsanity.com/paper/2203.12094/) (2022)
- [Synthetic Graph Generation to Benchmark Graph Learning](https://mlsanity.com/paper/2204.01376/) (2022)
- [Multi-Layer Generalized Linear Estimation](https://mlsanity.com/paper/1701.06981/) (2017)
- [Phase transitions in semisupervised clustering of sparse networks](https://mlsanity.com/paper/1404.7789/) (2014)
- [On Classification Thresholds for Graph Attention with Edge Features](https://mlsanity.com/paper/2210.10014/) (2022)
- [Transformers meet Stochastic Block Models: Attention with Data-Adaptive Sparsity and Cost](https://mlsanity.com/paper/2210.15541/) (2022)

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

- [Optimal Inference in Contextual Stochastic Block Models](https://mlsanity.com/paper/2306.07948/) (2023)
- [Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions](https://mlsanity.com/paper/2407.03522/) (2024)
- [Asymptotic generalization error of a single-layer graph convolutional network](https://mlsanity.com/paper/2402.03818/) (2024)
- [Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model](https://mlsanity.com/paper/2503.01361/) (2025)

## Abstract (arXiv)

The stochastic block model (SBM) is widely studied as a benchmark for graph clustering aka community detection. In practice, graph data often come with node attributes that bear additional information about the communities. Previous works modeled such data by considering that the node attributes are generated from the node community memberships. In this work, motivated by a recent surge of works in signal processing using deep neural networks as priors, we propose to model the communities as being determined by the node attributes rather than the opposite. We define the corresponding model; we call it the neural-prior SBM. We propose an algorithm, stemming from statistical physics, based on a combination of belief propagation and approximate message passing. We analyze the performance of the algorithm as well as the Bayes-optimal performance. We identify detectability and exact recovery phase transitions, as well as an algorithmically hard region. The proposed model and algorithm can be used as a benchmark for both theory and algorithms. To illustrate this, we compare the optimal performances to the performance of simple graph neural networks.