Neural-prior stochastic block model

Abstract

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.

References in corpus (22)

• Community detection in graphs
• Message Passing Algorithms for Compressed Sensing
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Statistical physics of inference: Thresholds and algorithms
• Phase transition in the detection of modules in sparse networks
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Entropy and mutual information in models of deep neural networks
• Covariate-assisted spectral clustering
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Phase transitions in semisupervised clustering of sparse networks
• Model-Based Deep Learning
• Fundamental limits of low-rank matrix estimation: the non-symmetric case
• Disordered Systems Insights on Computational Hardness
• Learning curves for the multi-class teacher-student perceptron
• The high-dimensional asymptotics of first order methods with random data
• Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
• Synthetic Graph Generation to Benchmark Graph Learning
• On Classification Thresholds for Graph Attention with Edge Features
• Transformers meet Stochastic Block Models: Attention with Data-Adaptive Sparsity and Cost

Cited by in corpus (3)

• Inference in Spreading Processes with Neural-Network Priors
• Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model
• Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions