Expressive Power of Temporal Message Passing
Przemysław Andrzej Wałęga, Michael Rawson
Abstract
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.
BibTeX
@article{Wałęga_Rawson_2025, title={Expressive Power of Temporal Message Passing}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/35396}, DOI={10.1609/aaai.v39i20.35396}, abstractNote={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.}, number={20}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Wałęga, Przemysław Andrzej and Rawson, Michael}, year={2025}, month={Apr.}, pages={21000-21008} }