mlsanityData to 7 Oct 2026

Message passing all the way up

arXiv 2202.11097 ↗First posted 22 Feb 2022cs.LG cs.SI stat.MLcited by 47

Not on the map. Why?

Abstract (arXiv)

The message passing framework is the foundation of the immense success enjoyed by graph neural networks (GNNs) in recent years. In spite of its elegance, there exist many problems it provably cannot solve over given input graphs. This has led to a surge of research on going "beyond message passing", building GNNs which do not suffer from those limitations -- a term which has become ubiquitous in regular discourse. However, have those methods truly moved beyond message passing? In this position paper, I argue about the dangers of using this term -- especially when teaching graph representation learning to newcomers. I show that any function of interest we want to compute over graphs can, in all likelihood, be expressed using pairwise message passing -- just over a potentially modified graph, and argue how most practical implementations subtly do this kind of trick anyway. Hoping to initiate a productive discussion, I propose replacing "beyond message passing" with a more tame term, "augmented message passing".

Key facts. Cited by 47 papers in the map (data through 7 Oct 2026). Builds on 55 of its 70 references that are in the map. First posted on arXiv 22 Feb 2022.

Builds on

55 of 70 references.

References · 55

  1. 2017Graph Attention Networkscited by 8,854
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  5. 2018Dynamic Graph CNN for Learning on Point Cloudscited by 2,220
  6. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  7. 2017Deep Setscited by 1,394
  8. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  9. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  10. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  11. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  12. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
38 more
  1. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  2. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  3. 2020A Generalization of Transformer Networks to Graphscited by 653
  4. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  5. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  6. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  7. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  8. 2019Diffusion Improves Graph Learningcited by 414
  9. 2019Provably Powerful Graph Networkscited by 385
  10. 2018Neural Relational Inference for Interacting Systemscited by 339
  11. 2018Invariant and Equivariant Graph Networkscited by 339
  12. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  13. 2021Do Transformers Really Perform Bad for Graph Representation?cited by 318
  14. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  15. 2020Can Graph Neural Networks Count Substructures?cited by 235
  16. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  17. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  18. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  19. 2020Random Features Strengthen Graph Neural Networkscited by 184
  20. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  21. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  22. 2020The Hardware Lotterycited by 160
  23. 2021Equivariant Subgraph Aggregation Networkscited by 154
  24. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  25. 2019Relational Pooling for Graph Representationscited by 150
  26. 2021GraphiT: Encoding Graph Structure in Transformerscited by 146
  27. 2020Directional Graph Networkscited by 132
  28. 2021ETA Prediction with Graph Neural Networks in Google Mapscited by 130
  29. 2021UniGNN: a Unified Framework for Graph and Hypergraph Neural Networkscited by 127
  30. 2021You are AllSet: A Multiset Function Framework for Hypergraph Neural Networkscited by 124
  31. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  32. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  33. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  34. 2019On the Limitations of Representing Functions on Setscited by 89
  35. 2020Line Graph Neural Networks for Link Predictioncited by 89
  36. 2020Differentiable Graph Module (DGM) for Graph Convolutional Networkscited by 86
  37. 2021Reconstruction for Powerful Graph Representationscited by 65
  38. 2020Hierarchical Inter-Message Passing for Learning on Molecular Graphscited by 59

50 most cited of 55 All 55 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 12; 2023: 15; 2024: 11; 2025: 7; 2026: 2.

47 papers.

Sort:

  1. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  2. 2023Everything is Connected: Graph Neural Networkscited by 85
  3. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  4. 2022Expander Graph Propagationcited by 75
  5. 2024Position: Topological Deep Learning is the New Frontier for Relational Learningcited by 65
  6. 2023Architectures of Topological Deep Learning: A Survey of Message-Passing Topological Neural Networkscited by 43
  7. 2023TacticAI: an AI assistant for football tacticscited by 43
  8. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 38
  9. 2022Global Concept-Based Interpretability for Graph Neural Networks via Neuron Analysiscited by 32
  10. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
  11. 2023Simplicial Representation Learning with Neural k-Formscited by 18
  12. 2024TopoTune : A Framework for Generalized Combinatorial Complex Neural Networkscited by 18
35 more
  1. 2022Equivariant Hypergraph Neural Networkscited by 14
  2. 2022Agent-based Graph Neural Networkscited by 13
  3. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  4. 2023Asynchronous Algorithmic Alignment with Cocyclescited by 13
  5. 2022ReFactor GNNs: Revisiting Factorisation-based Models from a Message-Passing Perspectivecited by 12
  6. 2025A Survey of Graph Transformers: Architectures, Theories and Applicationscited by 12
  7. 2024Towards Dynamic Message Passing on Graphscited by 11
  8. 2025Copresheaf Topological Neural Networks: A Generalized Deep Learning Frameworkcited by 11
  9. 2022FlowGNN: A Dataflow Architecture for Real-Time Workload-Agnostic Graph Neural Network Inferencecited by 10
  10. 2022De Bruijn goes Neural: Causality-Aware Graph Neural Networks for Time Series Data on Dynamic Graphscited by 10
  11. 2024Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Productscited by 8
  12. 2024On the Expressive Power of Sparse Geometric MPNNscited by 7
  13. 2023Architecture Matters: Uncovering Implicit Mechanisms in Graph Contrastive Learningcited by 6
  14. 2023Unsupervised Multiplex Graph Learning with Complementary and Consistent Informationcited by 5
  15. 2025HollowFlow: Efficient Sample Likelihood Evaluation using Hollow Message Passingcited by 5
  16. 2023Higher-Order Expander Graph Propagationcited by 4
  17. 2024CKGConv: General Graph Convolution with Continuous Kernelscited by 4
  18. 2022Causally-guided Regularization of Graph Attention Improves Generalizabilitycited by 3
  19. 2024In-n-Out: Calibrating Graph Neural Networks for Link Predictioncited by 3
  20. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  21. 2022Graph Convolutional Networks from the Perspective of Sheaves and the Neural Tangent Kernelcited by 2
  22. 2022Graph Neural Network Expressivity and Meta-Learning for Molecular Property Regressioncited by 2
  23. 2022Beyond 1-WL with Local Ego-Network Encodingscited by 2
  24. 2023Efficient Network Representation for GNN-based Intrusion Detectioncited by 2
  25. 2024Scalable Graph Compressed Convolutionscited by 2
  26. 2023GNNBuilder: An Automated Framework for Generic Graph Neural Network Accelerator Generation, Simulation, and Optimizationcited by 1
  27. 2025GNN-Suite: a Graph Neural Network Benchmarking Framework for Biomedical Informaticscited by 1
  28. 2025What Expressivity Theory Misses: Message Passing Complexity for GNNscited by 1
  29. 2023Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Testcited by 0
  30. 2023Graph Coordinates and Conventional Neural Networks -- An Alternative for Graph Neural Networkscited by 0
  31. 2024Topological Neural Networks: Mitigating the Bottlenecks of Graph Neural Networks via Higher-Order Interactionscited by 0
  32. 2025Directed Semi-Simplicial Learning with Applications to Brain Activity Decodingcited by 0
  33. 2025Spatiotemporal graph neural process for reconstruction, extrapolation, and classification of cardiac trajectoriescited by 0
  34. 2026Unified Graph Prompt Learning via Low-Rank Graph Message Promptingcited by 0
  35. 2026Adaptive Recurrent Message Passing for Test Time Computing on Graphscited by 0