mlsanityData to 7 Oct 2026

The Logic of Graph Neural Networks

arXiv 2104.14624 ↗First posted 29 Apr 2021cs.LG cs.AI cs.LOcited by 84

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) are deep learning architectures for machine learning problems on graphs. It has recently been shown that the expressiveness of GNNs can be characterised precisely by the combinatorial Weisfeiler-Leman algorithms and by finite variable counting logics. The correspondence has even led to new, higher-order GNNs corresponding to the WL algorithm in higher dimensions. The purpose of this paper is to explain these descriptive characterisations of GNNs.

Key facts. Cited by 84 papers in the map (data through 7 Oct 2026). Builds on 19 of its 65 references that are in the map. First posted on arXiv 29 Apr 2021.

Builds on

19 of 65 references.

References · 19

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  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. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  6. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,684
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  8. 2019Provably Powerful Graph Networkscited by 385
  9. 2018Invariant and Equivariant Graph Networkscited by 339
  10. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  11. 2020Random Features Strengthen Graph Neural Networkscited by 184
  12. 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
7 more
  1. 2018Lov'asz Meets Weisfeiler and Lemancited by 26
  2. 2015Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinementcited by 16
  3. 2019Graded modal logic and counting bisimulationcited by 13
  4. 2017The Weisfeiler-Leman Dimension of Planar Graphs is at most 3cited by 10
  5. 2013Dimension Reduction via Colour Refinementcited by 6
  6. 2015Limitations of Algebraic Approaches to Graph Isomorphism Testingcited by 2
  7. 2017The pebbling comonad in finite model theorycited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 14; 2023: 17; 2024: 15; 2025: 14; 2026: 14.

84 papers.

Sort:

By area:

  1. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  2. 2021From Statistical Relational to Neurosymbolic Artificial Intelligence: a Surveycited by 72
  3. 2022Ordered Subgraph Aggregation Networkscited by 57
  4. 2021Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limitscited by 38
  5. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  6. 2023A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphscited by 32
  7. 2023WL meet VCcited by 30
  8. 2022Weisfeiler and Leman Go Relationalcited by 28
  9. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  10. 2023The Descriptive Complexity of Graph Neural Networkscited by 26
  11. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  12. 2022Learning Generalized Policies Without Supervision Using GNNscited by 22
38 more
  1. 2025How Expressive are Knowledge Graph Foundation Models?cited by 22
  2. 2023Some Might Say All You Need Is Sumcited by 21
  3. 2022A Practical, Progressively-Expressive GNNcited by 20
  4. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 20
  5. 2021The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphscited by 19
  6. 2023On the Expressivity of Persistent Homology in Graph Learningcited by 18
  7. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  8. 2024Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floatscited by 13
  9. 2023PlanE: Representation Learning over Planar Graphscited by 11
  10. 2024Towards Principled Graph Transformerscited by 11
  11. 2025Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspectivecited by 10
  12. 2022Fundamental Limits in Formal Verification of Message-Passing Neural Networkscited by 9
  13. 2023Three iterations of (d-1)-WL test distinguish non isometric clouds of d-dimensional pointscited by 9
  14. 2024Link Prediction with Relational Hypergraphscited by 9
  15. 2024A Logic for Reasoning About Aggregate-Combine Graph Neural Networkscited by 9
  16. 2022On the expressive power of message-passing neural networks as global feature map transformerscited by 8
  17. 2022Weisfeiler and Leman Go Walking: Random Walk Kernels Revisitedcited by 8
  18. 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
  19. 2026AI Can Learn Scientific Tastecited by 8
  20. 2023Zero-One Laws of Graph Neural Networkscited by 7
  21. 2023On the power of graph neural networks and the role of the activation functioncited by 7
  22. 2024Symmetries and Expressive Requirements for Learning General Policiescited by 7
  23. 2024Logical Distillation of Graph Neural Networkscited by 6
  24. 2021Target Languages (vs. Inductive Biases) for Learning to Act and Plancited by 5
  25. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  26. 2021Relational Reasoning Networkscited by 4
  27. 2023Improving Subgraph-GNNs via Edge-Level Ego-Network Encodingscited by 4
  28. 2023Learning Graph Neural Networks using Exact Compressioncited by 3
  29. 2024Highly Accurate Disease Diagnosis and Highly Reproducible Biomarker Identification with PathFormercited by 3
  30. 2025A Logical View of GNN-Style Computation and the Role of Activation Functionscited by 3
  31. 2025Learning General Policies with Policy Gradient Methodscited by 3
  32. 2021Querying in the Age of Graph Databases and Knowledge Graphscited by 2
  33. 2025Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limitcited by 2
  34. 2025Halting Recurrent GNNs and the Graded μ-Calculuscited by 2
  35. 2025The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logicscited by 2
  36. 2025Understanding Generalization in Node and Link Predictioncited by 2
  37. 2025Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Studycited by 2
  38. 2025Vejde: A Framework for Inductive Deep Reinforcement Learning Based on Factor Graph Color Refinementcited by 2

50 most cited of 84 All 84 (JSON)