Expressive Power of Temporal Message Passing
<|reference_start|>Expressive Power of Temporal Message Passing: 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.<|reference_end|>
@article{wałęga2024expressive,
    title={Expressive Power of Temporal Message Passing},
    author={Przemys{l}aw Andrzej Wa{l}k{e}ga, Michael Rawson},
    journal={arXiv preprint arXiv:2408.09918},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.09918},
    primaryClass={cs.LG}
}