# Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs

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

## Key facts

- Cited by 2 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 30 May 2025.

## Builds on (most cited first, 30 of 32)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)
- [ROLAND: Graph Learning Framework for Dynamic Graphs](https://mlsanity.com/paper/2208.07239/) (2022)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Motifs in Temporal Networks](https://mlsanity.com/paper/1612.09259/) (2016)
- [Building powerful and equivariant graph neural networks with structural message-passing](https://mlsanity.com/paper/2006.15107/) (2020)
- [Edge Directionality Improves Learning on Heterophilic Graphs](https://mlsanity.com/paper/2305.10498/) (2023)
- [Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunities](https://mlsanity.com/paper/2302.01018/) (2023)
- [Provably expressive temporal graph networks](https://mlsanity.com/paper/2209.15059/) (2022)
- [Modern temporal network theory: A colloquium](https://mlsanity.com/paper/1508.01303/) (2015)
- [Memory in network flows and its effects on spreading dynamics and community detection](https://mlsanity.com/paper/1305.4807/) (2013)
- [Temporal Graph Kernels for Classifying Dissemination Processes](https://mlsanity.com/paper/1911.05496/) (2019)
- [Can co-location be used as a proxy for face-to-face contacts?](https://mlsanity.com/paper/1712.06346/) (2017)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [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)
- [Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks](https://mlsanity.com/paper/1307.4030/) (2013)
- [When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks](https://mlsanity.com/paper/1702.05499/) (2017)
- [De Bruijn goes Neural: Causality-Aware Graph Neural Networks for Time Series Data on Dynamic Graphs](https://mlsanity.com/paper/2209.08311/) (2022)
- [Expressive Power of Temporal Message Passing](https://mlsanity.com/paper/2408.09918/) (2024)
- [Higher-Order Aggregate Networks in the Analysis of Temporal Networks: Path structures and centralities](https://mlsanity.com/paper/1508.06467/) (2015)
- [Directed Percolation in Temporal Networks](https://mlsanity.com/paper/2107.01510/) (2021)
- [Using Time-Aware Graph Neural Networks to Predict Temporal Centralities in Dynamic Graphs](https://mlsanity.com/paper/2310.15865/) (2023)

## Built on by (most cited first, 2 of 2)

- [Beat the Counter First: A Baseline for Temporal-Graph Anomaly Detectors](https://mlsanity.com/paper/2608.15965/) (2026)
- [A Unifying Relational Perspective on Expressive Lottery Tickets](https://mlsanity.com/paper/2608.18819/) (2026)

## Abstract (arXiv)

An important characteristic of temporal graphs is how the directed arrow of time influences their causal topology, i.e., which nodes can possibly influence each other causally via time-respecting paths. The resulting patterns are often neglected by temporal graph neural networks (TGNNs). To formally analyze the expressive power of TGNNs, we lack a generalization of graph isomorphism to temporal graphs that fully captures their causal topology. Addressing this gap, we introduce the notion of consistent event graph isomorphism, which utilizes a time-unfolded representation of time-respecting paths in temporal graphs. We compare this definition with existing notions of temporal graph isomorphisms. We illustrate and highlight the advantages of our approach and develop a temporal generalization of the Weisfeiler-Leman algorithm to heuristically distinguish non-isomorphic temporal graphs. Building on this theoretical foundation, we derive a novel message passing scheme for temporal graph neural networks that operates on the event graph representation of temporal graphs. An experimental evaluation shows that our approach performs well in a temporal graph classification experiment.