Abstract
In recent years, the expressive power of various neural architectures --including graph neural networks (GNNs), transformers, and recurrent neuralnetworks -- has been characterised using tools from logic and formal languagetheory. As the capabilities of basic architectures are becoming wellunderstood, increasing attention is turning to models that combine multiplearchitectural paradigms. Among them particularly important, and challenging toanalyse, are temporal extensions of GNNs, which integrate both spatial(graph-structure) and temporal (evolution over time) dimensions. In this paper,we initiate the study of logical characterisation of temporal GNNs byconnecting them to two-dimensional product logics. We show that the expressivepower of temporal GNNs depends on how graph and temporal components arecombined. In particular, temporal GNNs that apply static GNNs recursively overtime can capture all properties definable in the product logic of (past)propositional temporal logic PTL and the modal logic K. In contrast,architectures such as graph-and-time TGNNs and global TGNNs can only expressrestricted fragments of this logic, where the interaction between temporal andspatial operators is syntactically constrained. These provide us with the firstresults on the logical expressiveness of temporal GNNs.