Expressive Power of Temporal Message Passing
This provides theoretical insights for researchers developing temporal graph neural networks, though it is incremental as it builds on existing message-passing frameworks.
The paper analyzed the expressive power of global and local temporal message-passing mechanisms in graph neural networks, showing they are incomparable for arbitrary temporal graphs but local mechanisms are strictly more expressive for colour-persistent temporal graphs, with experimental validation.
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.