mlsanityData to 14 Oct 2026

Expressiveness and Approximation Properties of Graph Neural Networks

arXiv 2204.04661 ↗First posted 10 Apr 2022cs.LGcited by 64

Not on the map. Why?

Abstract (arXiv)

Characterizing the separation power of graph neural networks (GNNs) provides an understanding of their limitations for graph learning tasks. Results regarding separation power are, however, usually geared at specific GNN architectures, and tools for understanding arbitrary GNN architectures are generally lacking. We provide an elegant way to easily obtain bounds on the separation power of GNNs in terms of the Weisfeiler-Leman (WL) tests, which have become the yardstick to measure the separation power of GNNs. The crux is to view GNNs as expressions in a procedural tensor language describing the computations in the layers of the GNNs. Then, by a simple analysis of the obtained expressions, in terms of the number of indexes and the nesting depth of summations, bounds on the separation power in terms of the WL-tests readily follow. We use tensor language to define Higher-Order Message-Passing Neural Networks (or k-MPNNs), a natural extension of MPNNs. Furthermore, the tensor language point of view allows for the derivation of universality results for classes of GNNs in a natural way. Our approach provides a toolbox with which GNN architecture designers can analyze the separation power of their GNNs, without needing to know the intricacies of the WL-tests. We also provide insights in what is needed to boost the separation power of GNNs.

Key facts. Cited by 64 papers in the map (data through 14 Oct 2026). Builds on 15 of its 40 references that are in the map. First posted on arXiv 10 Apr 2022.

Builds on

15 of 40 references.

References · 15

  1. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  2. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,102
  3. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  4. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  5. 2020Can Graph Neural Networks Count Substructures?cited by 236
  6. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  7. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  8. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  9. 2020The expressive power of kth-order invariant graph networkscited by 34
  10. 2015FAQ: Questions Asked Frequentlycited by 14
  11. 2017Homomorphisms Are a Good Basis for Counting Small Subgraphscited by 14
  12. 2017On the expressive power of query languages for matricescited by 14
3 more
  1. 2018On the expressive power of linear algebra on graphscited by 14
  2. 2019Graded modal logic and counting bisimulationcited by 13
  3. 2020A Novel Higher-order Weisfeiler-Lehman Graph Convolutioncited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 14; 2023: 15; 2024: 24; 2025: 6; 2026: 5.

64 papers.

Sort:

By area:

  1. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  2. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  3. 2022Ordered Subgraph Aggregation Networkscited by 57
  4. 2023How does over-squashing affect the power of GNNs?cited by 53
  5. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  6. 2022Linkless Link Prediction via Relational Distillationcited by 39
  7. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 39
  8. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  9. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  10. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  11. 2023WL meet VCcited by 31
  12. 2022Weisfeiler and Leman Go Relationalcited by 28
38 more
  1. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  2. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  3. 2022On Representing Mixed-Integer Linear Programs by Graph Neural Networkscited by 23
  4. 2024Clifford Group Equivariant Simplicial Message Passing Networkscited by 22
  5. 2023Some Might Say All You Need Is Sumcited by 21
  6. 2022A Practical, Progressively-Expressive GNNcited by 20
  7. 2024Homomorphism Counts for Graph Neural Networks: All About That Basiscited by 16
  8. 2024Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programscited by 16
  9. 2024On the Expressive Power of Spectral Invariant Graph Neural Networkscited by 15
  10. 2024Bundle Neural Networks for message diffusion on graphscited by 14
  11. 2022Agent-based Graph Neural Networkscited by 13
  12. 2022Homophily modulates double descent generalization in graph convolution networkscited by 13
  13. 2024On the hardness of learning under symmetriescited by 13
  14. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  15. 2022ReFactor GNNs: Revisiting Factorisation-based Models from a Message-Passing Perspectivecited by 12
  16. 2022On the Ability of Graph Neural Networks to Model Interactions Between Verticescited by 12
  17. 2024Rethinking the Capacity of Graph Neural Networks for Branching Strategycited by 12
  18. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  19. 2022Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networkscited by 9
  20. 2024Improving the Expressiveness of K-hop Message-Passing GNNs by Injecting Contextualized Substructure Informationcited by 9
  21. 2023On the power of graph neural networks and the role of the activation functioncited by 8
  22. 2024Aligning Transformers with Weisfeiler-Lemancited by 8
  23. 2024Almost Surely Asymptotically Constant Graph Neural Networkscited by 7
  24. 2022Generalizing Downsampling from Regular Data to Graphscited by 6
  25. 2023State of the Art and Potentialities of Graph-level Learningcited by 6
  26. 2024Future Directions in the Theory of Graph Machine Learningcited by 6
  27. 2025Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centralitycited by 5
  28. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 5
  29. 2024Demystifying Higher-Order Graph Neural Networkscited by 4
  30. 2025Homomorphism Expressivity of Spectral Invariant Graph Neural Networkscited by 4
  31. 2022Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysiscited by 3
  32. 2024Can GNNs Learn Link Heuristics? A Concise Review and Evaluation of Link Prediction Methodscited by 3
  33. 2025On Universality of Deep Equivariant Networkscited by 3
  34. 2023Can strong structural encoding reduce the importance of Message Passing?cited by 2
  35. 2023Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational and Temporal Graphscited by 2
  36. 2024Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learningcited by 2
  37. 2024Separation Power of Equivariant Neural Networkscited by 2
  38. 2024Current Symmetry Group Equivariant Convolution Frameworks for Representation Learningcited by 2

50 most cited of 64 All 64 (JSON)