# Expressive Power of Temporal Message Passing

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 22 references that are in the map.
- First posted on arXiv 19 Aug 2024.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019)
- [Time2Vec: Learning a Vector Representation of Time](https://mlsanity.com/paper/1907.05321/) (2019)
- [Examining COVID-19 Forecasting using Spatio-Temporal Graph Neural Networks](https://mlsanity.com/paper/2007.03113/) (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)

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

- [TeMP-TraG: Edge-based Temporal Message Passing in Transaction Graphs](https://mlsanity.com/paper/2503.16901/) (2025)
- [The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics](https://mlsanity.com/paper/2505.11930/) (2025)
- [Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs](https://mlsanity.com/paper/2505.24438/) (2025)
- [Forget Less, Generalize More: Unifying Temporal and Structural Adaptation for Dynamic Graphs](https://mlsanity.com/paper/2605.29453/) (2026)
- [Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win](https://mlsanity.com/paper/2506.03919/) (2025)
- [MLGIB: Multi-Label Graph Information Bottleneck for Expressive and Robust Message Passing](https://mlsanity.com/paper/2605.13126/) (2026)
- [A Unifying Relational Perspective on Expressive Lottery Tickets](https://mlsanity.com/paper/2608.18819/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) have recently been adapted to temporal settings, often employing temporal versions of the message-passing mechanism known from GNNs. We divide temporal message passing mechanisms from literature into two main types: global and local, and establish Weisfeiler-Leman characterisations for both. This allows us to formally analyse expressive power of temporal message-passing models. We show that global and local temporal message-passing mechanisms have incomparable expressive power when applied to arbitrary temporal graphs. However, the local mechanism is strictly more expressive than the global mechanism when applied to colour-persistent temporal graphs, whose node colours are initially the same in all time points. Our theoretical findings are supported by experimental evidence, underlining practical implications of our analysis.