# Optimality of Message-Passing Architectures for Sparse Graphs

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 64 references that are in the map.
- First posted on arXiv 17 May 2023.

## Builds on (most cited first, 30 of 36)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics](https://mlsanity.com/paper/1908.02591/) (2019)
- [Relational Pooling for Graph Representations](https://mlsanity.com/paper/1903.02541/) (2019)
- [Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction](https://mlsanity.com/paper/2111.00064/) (2021)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [How Powerful are K-hop Message Passing Graph Neural Networks](https://mlsanity.com/paper/2205.13328/) (2022)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [k-hop Graph Neural Networks](https://mlsanity.com/paper/1907.06051/) (2019)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [Message passing all the way up](https://mlsanity.com/paper/2202.11097/) (2022)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [Graph Attention Retrospective](https://mlsanity.com/paper/2202.13060/) (2022)

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

- [TacticAI: an AI assistant for football tactics](https://mlsanity.com/paper/2310.10553/) (2023)
- [The Interpretable and Effective Graph Neural Additive Networks](https://mlsanity.com/paper/2406.01317/) (2024)
- [Asynchronous Algorithmic Alignment with Cocycles](https://mlsanity.com/paper/2306.15632/) (2023)
- [Optimal Inference in Contextual Stochastic Block Models](https://mlsanity.com/paper/2306.07948/) (2023)
- [Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees](https://mlsanity.com/paper/2605.18775/) (2026)
- [Asymptotic generalization error of a single-layer graph convolutional network](https://mlsanity.com/paper/2402.03818/) (2024)
- [Analysis of Corrected Graph Convolutions](https://mlsanity.com/paper/2405.13987/) (2024)
- [Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model](https://mlsanity.com/paper/2503.01361/) (2025)
- [Sharp Bounds for Poly-GNNs and the Effect of Graph Noise](https://mlsanity.com/paper/2407.19567/) (2024)
- [Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks](https://mlsanity.com/paper/2412.13754/) (2024)
- [On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model](https://mlsanity.com/paper/2510.21392/) (2025)
- [A Spectral Theory of Normalized Corrected GNN Propagation](https://mlsanity.com/paper/2606.23572/) (2026)
- [The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy](https://mlsanity.com/paper/2607.16676/) (2026)

## Abstract (arXiv)

We study the node classification problem on feature-decorated graphs in the sparse setting, i.e., when the expected degree of a node is O(1) in the number of nodes, in the fixed-dimensional asymptotic regime, i.e., the dimension of the feature data is fixed while the number of nodes is large. Such graphs are typically known to be locally tree-like. We introduce a notion of Bayes optimality for node classification tasks, called asymptotic local Bayes optimality, and compute the optimal classifier according to this criterion for a fairly general statistical data model with arbitrary distributions of the node features and edge connectivity. The optimal classifier is implementable using a message-passing graph neural network architecture. We then compute the generalization error of this classifier and compare its performance against existing learning methods theoretically on a well-studied statistical model with naturally identifiable signal-to-noise ratios (SNRs) in the data. We find that the optimal message-passing architecture interpolates between a standard MLP in the regime of low graph signal and a typical convolution in the regime of high graph signal. Furthermore, we prove a corresponding non-asymptotic result.