mlsanityData to 7 Oct 2026

Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs

arXiv 2210.03990 ↗First posted 8 Oct 2022cs.LG cs.AIcited by 12

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs) are a large class of relational models for graph processing. Recent theoretical studies on the expressive power of GNNs have focused on two issues. On the one hand, it has been proven that GNNs are as powerful as the Weisfeiler-Lehman test (1-WL) in their ability to distinguish graphs. Moreover, it has been shown that the equivalence enforced by 1-WL equals unfolding equivalence. On the other hand, GNNs turned out to be universal approximators on graphs modulo the constraints enforced by 1-WL/unfolding equivalence. However, these results only apply to Static Attributed Undirected Homogeneous Graphs (SAUHG) with node attributes. In contrast, real-life applications often involve a much larger variety of graph types. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for two other graph domains that are particularly interesting in practical applications, namely dynamic graphs and SAUGHs with edge attributes. Dynamic graphs are widely used in modern applications; hence, the study of the expressive capability of GNNs in this domain is essential for practical reasons and, in addition, it requires a new analyzing approach due to the difference in the architecture of dynamic GNNs compared to static ones. On the other hand, the examination of SAUHGs is of particular relevance since they act as a standard form for all graph types: it has been shown that all graph types can be transformed without loss of information to SAUHGs with both attributes on nodes and edges. This paper considers generic GNN models and appropriate 1-WL tests for those domains. Then, the known results on the expressive power of GNNs are extended to the mentioned domains: it is proven that GNNs have the same capability as the 1-WL test, the 1-WL equivalence equals unfolding equivalence and that GNNs are universal approximators modulo 1-WL/unfolding equivalence.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 36 of its 64 references that are in the map. First posted on arXiv 8 Oct 2022.

Builds on

36 of 64 references.

References · 36

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  6. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  7. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  8. 2017Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecastingcited by 1,125
  9. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  10. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  11. 2015Gated Graph Sequence Neural Networkscited by 792
  12. 2020Inductive Representation Learning on Temporal Graphscited by 454
24 more
  1. 2019Provably Powerful Graph Networkscited by 385
  2. 2018Invariant and Equivariant Graph Networkscited by 339
  3. 2016Learning Convolutional Neural Networks for Graphscited by 314
  4. 2016Structured Sequence Modeling with Graph Convolutional Recurrent Networkscited by 273
  5. 2019Representation Learning for Dynamic Graphs: A Surveycited by 260
  6. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  7. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  8. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  9. 2021Identity-aware Graph Neural Networkscited by 197
  10. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  11. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  12. 2017Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphscited by 149
  13. 2021Nested Graph Neural Networkscited by 136
  14. 2020Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A surveycited by 123
  15. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  16. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  17. 2020TeMP: Temporal Message Passing for Temporal Knowledge Graph Completioncited by 61
  18. 2021A Survey on Embedding Dynamic Graphscited by 60
  19. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  20. 2019Coloring graph neural networks for node disambiguationcited by 49
  21. 2021Dynamic Network Embedding Surveycited by 44
  22. 2022Graph Neural Networks Designed for Different Graph Types: A Surveycited by 21
  23. 2020The Iteration Number of Colour Refinementcited by 12
  24. 2021On the approximation capability of GNNs in node classification/regression taskscited by 9

Built on by

Cited by year (2026 to 7 Oct)

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

12 papers.

  1. 2023Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunitiescited by 60
  2. 2024Expressive Power of Temporal Message Passingcited by 7
  3. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  4. 2025Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphscited by 2
  5. 2025T-GRAB: A Synthetic Diagnostic Benchmark for Learning on Temporal Graphscited by 2
  6. 2023Torsion Graph Neural Networkscited by 1
  7. 2025Deep Graph Learning will stall without Network Sciencecited by 1
  8. 2023Enhancing Signed Graph Neural Networks through Curriculum-Based Trainingcited by 0
  9. 2024Mesh-Informed Reduced Order Models for Aneurysm Rupture Risk Predictioncited by 0
  10. 2025Full-History Graphs with Edge-Type Decoupled Networks for Temporal Reasoningcited by 0
  11. 2025Weisfeiler-Lehman meets Events: An Expressivity Analysis for Continuous-Time Dynamic Graph Neural Networkscited by 0
  12. 2026A Unifying Relational Perspective on Expressive Lottery Ticketscited by 0