# Weisfeiler-Lehman meets Events: An Expressivity Analysis for Continuous-Time Dynamic Graph Neural Networks

arXiv: https://arxiv.org/abs/2508.18052 · HTML: https://mlsanity.com/paper/2508.18052/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 11 references that are in the map.
- First posted on arXiv 25 Aug 2025.

## Builds on (most cited first, 7 of 7)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A survey](https://mlsanity.com/paper/2005.07496/) (2020)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs](https://mlsanity.com/paper/2210.03990/) (2022)
- [On the approximation capability of GNNs in node classification/regression tasks](https://mlsanity.com/paper/2106.08992/) (2021)
- [A Topological characterisation of Weisfeiler-Leman equivalence classes](https://mlsanity.com/paper/2206.11876/) (2022)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are known to match the distinguishing power of the 1-Weisfeiler-Lehman (1-WL) test, and the resulting partitions coincide with the unfolding tree equivalence classes of graphs. Preserving this equivalence, GNNs can universally approximate any target function on graphs in probability up to any precision. However, these results are limited to attributed discrete-dynamic graphs represented as sequences of connected graph snapshots. Real-world systems, such as communication networks, financial transaction networks, and molecular interactions, evolve asynchronously and may split into disconnected components. In this paper, we extend the theory of attributed discrete-dynamic graphs to attributed continuous-time dynamic graphs with arbitrary connectivity. To this end, we introduce a continuous-time dynamic 1-WL test, prove its equivalence to continuous-time dynamic unfolding trees, and identify a class of continuous-time dynamic GNNs (CGNNs) based on discrete-dynamic GNN architectures that retain both distinguishing power and universal approximation guarantees. Our constructive proofs further yield practical design guidelines, emphasizing a compact and expressive CGNN architecture with piece-wise continuously differentiable temporal functions to process asynchronous, disconnected graphs.