mlsanityData to 14 Oct 2026

Optimality of Message-Passing Architectures for Sparse Graphs

arXiv 2305.10391 ↗First posted 17 May 2023cs.LG stat.MLcited by 13

Not on the map. Why?

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.

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

36 of 64 references.

References · 36

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  4. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  6. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  7. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
  8. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  9. 2020Simple and Deep Graph Convolutional Networkscited by 860
  10. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  11. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 509
  12. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
24 more
  1. 2018Invariant and Equivariant Graph Networkscited by 346
  2. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 320
  3. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 222
  4. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  5. 2019Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensicscited by 164
  6. 2019Relational Pooling for Graph Representationscited by 150
  7. 2021Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Predictioncited by 138
  8. 2018Contextual Stochastic Block Modelscited by 134
  9. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  10. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  11. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  12. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 59
  13. 2019k-hop Graph Neural Networkscited by 57
  14. 2013Community detection thresholds and the weak Ramanujan propertycited by 47
  15. 2022Message passing all the way upcited by 47
  16. 2013A Proof Of The Block Model Threshold Conjecturecited by 36
  17. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  18. 2022Graph Attention Retrospectivecited by 24
  19. 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
  20. 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
  21. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
  22. 2023Revisiting Robustness in Graph Machine Learningcited by 19
  23. 2022Learnable Graph Convolutional Attention Networkscited by 8
  24. 2022On Classification Thresholds for Graph Attention with Edge Featurescited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 5; 2025: 2; 2026: 3.

13 papers.

Sort:

By area:

  1. 2023TacticAI: an AI assistant for football tacticscited by 44
  2. 2024The Interpretable and Effective Graph Neural Additive Networkscited by 20
  3. 2023Asynchronous Algorithmic Alignment with Cocyclescited by 13
  4. 2023Optimal Inference in Contextual Stochastic Block Modelscited by 12
  5. 2026Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guaranteescited by 7
  6. 2024Asymptotic generalization error of a single-layer graph convolutional networkcited by 3
  7. 2024Analysis of Corrected Graph Convolutionscited by 2
  8. 2025Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block modelcited by 2
  9. 2024Sharp Bounds for Poly-GNNs and the Effect of Graph Noisecited by 1
  10. 2024Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networkscited by 0
  11. 2025On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Modelcited by 0
  12. 2026A Spectral Theory of Normalized Corrected GNN Propagationcited by 0
1 more
  1. 2026The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomycited by 0