mlsanityData to 14 Oct 2026

Breaking the Limits of Message Passing Graph Neural Networks

arXiv 2106.04319 ↗First posted 8 Jun 2021cs.LG cs.AIcited by 101

Not on the map. Why?

Abstract (arXiv)

Since the Message Passing (Graph) Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs, they have been widely implemented and still raise a lot of interest even though their theoretical expressive power is limited to the first order Weisfeiler-Lehman test (1-WL). In this paper, we show that if the graph convolution supports are designed in spectral-domain by a non-linear custom function of eigenvalues and masked with an arbitrary large receptive field, the MPNN is theoretically more powerful than the 1-WL test and experimentally as powerful as a 3-WL existing models, while remaining spatially localized. Moreover, by designing custom filter functions, outputs can have various frequency components that allow the convolution process to learn different relationships between a given input graph signal and its associated properties. So far, the best 3-WL equivalent graph neural networks have a computational complexity in O(n3) with memory usage in O(n2), consider non-local update mechanism and do not provide the spectral richness of output profile. The proposed method overcomes all these aforementioned problems and reaches state-of-the-art results in many downstream tasks.

Key facts. Cited by 101 papers in the map (data through 14 Oct 2026). Builds on 32 of its 44 references that are in the map. First posted on arXiv 8 Jun 2021.

Builds on

32 of 44 references.

References · 32

  1. 2017Attention Is All You Needcited by 60,361
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Graph Attention Networkscited by 8,923
  4. 2017Inductive Representation Learning on Large Graphscited by 6,320
  5. 2018How Powerful are Graph Neural Networks?cited by 4,393
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  7. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  8. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  9. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  10. 2018Relational inductive biases, deep learning, and graph networkscited by 1,360
  11. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  12. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
20 more
  1. 2020Benchmarking Graph Neural Networkscited by 680
  2. 2019Provably Powerful Graph Networkscited by 389
  3. 2017Residual Gated Graph ConvNetscited by 346
  4. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  5. 2020Can Graph Neural Networks Count Substructures?cited by 236
  6. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  7. 2020Random Features Strengthen Graph Neural Networkscited by 186
  8. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 183
  9. 2020Machine Learning on Graphs: A Model and Comprehensive Taxonomycited by 156
  10. 2019On the Universality of Invariant Networkscited by 152
  11. 2019Relational Pooling for Graph Representationscited by 150
  12. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 97
  13. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 69
  14. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  15. 2019Understanding the Representation Power of Graph Neural Networks in Learning Graph Topologycited by 52
  16. 2019Coloring graph neural networks for node disambiguationcited by 52
  17. 2017On the expressive power of query languages for matricescited by 14
  18. 2018On the expressive power of linear algebra on graphscited by 14
  19. 2016ESCAPE: Efficiently Counting All 5-Vertex Subgraphscited by 8
  20. 2016Linear Programming Heuristics for the Graph Isomorphism Problemcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 27; 2023: 32; 2024: 23; 2025: 14; 2026: 1.

101 papers.

Sort:

By area:

  1. 2021Frame Averaging for Invariant and Equivariant Network Designcited by 168
  2. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  3. 2021Equivariant Subgraph Aggregation Networkscited by 154
  4. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  5. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  6. 2024Let Your Graph Do the Talking: Encoding Structured Data for LLMscited by 118
  7. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  8. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  9. 2023A Comprehensive Survey on Deep Graph Representation Learningcited by 72
  10. 2022A Survey on Graph Representation Learning Methodscited by 66
  11. 2022Benchmarking Graphormer on Large-Scale Molecular Modeling Datasetscited by 64
  12. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 64
38 more
  1. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  2. 2022Ordered Subgraph Aggregation Networkscited by 57
  3. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 56
  4. 2024KAGNNs: Kolmogorov-Arnold Networks meet Graph Learningcited by 49
  5. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 39
  6. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  7. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  8. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  9. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  10. 2023WL meet VCcited by 31
  11. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  12. 2024A Canonicalization Perspective on Invariant and Equivariant Learningcited by 27
  13. 2023A Survey on Spectral Graph Neural Networkscited by 26
  14. 2023Learning Probabilistic Symmetrization for Architecture Agnostic Equivariancecited by 26
  15. 2022On Representing Mixed-Integer Linear Programs by Graph Neural Networkscited by 23
  16. 2022A Practical, Progressively-Expressive GNNcited by 20
  17. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
  18. 2023From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networkscited by 17
  19. 2024Spatio-Spectral Graph Neural Networkscited by 17
  20. 2025Beyond Message Passing: Neural Graph Pattern Machinecited by 17
  21. 2022Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Coloringscited by 15
  22. 20221-WL Expressiveness Is (Almost) All You Needcited by 15
  23. 2022Going Deeper into Permutation-Sensitive Graph Neural Networkscited by 15
  24. 2023Dynamic Graph Representation Learning with Neural Networks: A Surveycited by 15
  25. 2023Hypergraph Neural Networks through the Lens of Message Passing: A Common Perspective to Homophily and Architecture Designcited by 15
  26. 2023Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-based Similaritycited by 14
  27. 2023Facilitating Graph Neural Networks with Random Walk on Simplicial Complexescited by 14
  28. 2022ES-GNN: Generalizing Graph Neural Networks Beyond Homophily with Edge Splittingcited by 13
  29. 2023An Efficient Subgraph GNN with Provable Substructure Counting Powercited by 13
  30. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  31. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  32. 2024Revisiting Random Walks for Learning on Graphscited by 13
  33. 2022On the Ability of Graph Neural Networks to Model Interactions Between Verticescited by 12
  34. 2023Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Powercited by 12
  35. 2023TransGNN: Harnessing the Collaborative Power of Transformers and Graph Neural Networks for Recommender Systemscited by 11
  36. 2023Graph Neural Networks with Diverse Spectral Filteringcited by 9
  37. 2022On the expressive power of message-passing neural networks as global feature map transformerscited by 8
  38. 2023Cycle Invariant Positional Encoding for Graph Representation Learningcited by 8

50 most cited of 101 All 101 (JSON)