The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics

Marco Sälzer, Przemysław Andrzej Wałęga, Martin Lange · 2025

Read The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics by Marco Sälzer, Przemysław Andrzej Wałęga, Martin Lange (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11930.txt.

Introduction

Marco Sälzer, Przemysław Wałęga, and Martin Lange characterize the logical expressiveness of temporal graph neural networks. Their 2025 arXiv paper links learning models to formal logic. Expressive power of many architectures is now mapped logically. Models mixing graph structure with time resisted such analysis. Two-dimensional product logics supply the needed bridge here.

Recursive temporal networks match a product of temporal and modal logic. They apply static graph networks repeatedly across time steps. Other fusion styles land at different expressive levels. How space and time components combine decides the outcome. The results guide architecture choice for temporal graph data. Logicians gain a cleaner taxonomy of these models. The study opens a research line rather than closing one.

Catalog record

CREATORMarco Sälzer, Przemysław Andrzej Wałęga, Martin Lange
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-11930

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics Marco Sälzer, Przemysław Andrzej Wałęga, Martin Lange Abstract In recent years, the expressive power of various neural architectures—including graph neural networks (GNNs), transformers, and recurrent neural networks—has been characterised using tools from logic and formal language theory. As the capabilities of basic architectures are becoming well understood, increasing attention is turning to models that combine multiple architectural paradigms. Among them particularly important, and challenging to analyse, 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 by connecting them to two-dimensional product logics. We show that the expressive power of temporal GNNs depends on how graph and temporal components are combined. In particular, temporal GNNs that apply static GNNs recursively over time 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 express restricted fragments of this logic, where the interaction between temporal and spatial operators is syntactically constrained. These results yield the first logical characterisations of temporal GNNs and establish new relative expressiveness results for temporal GNNs. 1 Introduction Recent years have seen significant progress in understanding the expressive power of neural architectures using tools from logic, formal language theory, and graph theory. Some of the most prominent results concern Graph Neural Networks (GNNs), whose distinguishing power has been famously characterised with the Weisfeiler-Leman isomorphism test morris2019weisfeiler ; DBLP:conf/iclr/XuHLJ19 and whose logical expressiveness has been captured with modal and first-order logics BarceloKM0RS20 ; Grohe21 ; NunnSST24 ; BenediktLMT24 ; ahvonen2024logical . These insights have revealed both the limitations and strengths of GNNs, inspiring the development of more expressive variants such as higher-order GNNs morris2019weisfeiler . They have also opened the way for extracting logical rules from GNNs, advancing explainability in graph-based learning DBLP:conf/kr/CucalaGMK23 ; DBLP:conf/kr/CucalaG24 . Consequently, the logical expressiveness of GNNs has become a rapidly evolving research area. As the capabilities of standard GNN architectures become relatively well understood, research interest is shifting to more complex architectures, which combine multiple dimensions of structure. One particularly prominent and challenging case is that of Temporal Graph Neural Networks (TGNNs) LongaLSBLLSP23 ; DBLP:journals/access/SkardingGM21 ; GR22 , which can be seen as an extension of GNNs enabling to process temporal graphs , that is, graphs whose topology evolves over time. As a result, TGNN computations combine the spatial (graph structure) with temporal (changes in time) dimensions. Considerable advancements have been made in the design of various TGNN architectures LongaLSBLLSP23 and their deployment across diverse applications such as traffic forecasting, financial applications, and epidemiological contexts YuYZ18 ; ParejaDCMSKKSL20 ; Kapoor20 . However understanding expressive capabilities of TGNNs remains limited, with the first steps only comparing some TGNN architectures GR22 ; chen2023calibrate or establishing relations with temporal versions of the Weisfeiler-Leman test SouzaMKG22 ; WR24 . To the best of our knowledge no characterisation of TGNNs with logics has been established prior to this work. Our contribution. In this work, we initiate the analysis of the logical expressiveness of TGNNs. Our goal is to characterise the temporal graph properties that TGNNs can express using logical languages. To achieve this, we propose a novel approach—analysing the logical expressiveness of TGNNs using two-dimensional product logics. This is based on the key insight that the computations of TGNNs, which process both the structural properties of static graphs and their evolution over time, naturally correspond to combinations of modal and temporal properties. Both modal and temporal logics have been extensively studied in the logic community for decades, and more recent work has connected them to the expressiveness of neural architectures BarceloKM0RS20 ; NunnSST24 ; DBLP:conf/iclr/BarceloKLP24 ; DBLP:journals/corr/abs-2404-04393 . Likewise, many-dimensional logics, especially products of modal and temporal logics, have a rich theoretical foundation and well-established tools for analysing definability and complexity kurucz2003many ; DBLP:journals/apin/BennettCWZ02 ; DBLP:conf/time/LutzWZ08 . We are the first to apply product logics as a framework for analysing the expressive power of TGNNs. At a technical level, we show that certain TGNN architectures are (in-)capable of expressing certain combinations of model-temporal properties. Our results are as follows: • The class \mathcal{T}_{\textsf{rec}}[\hat{\mathcal{M}}] of TGNNs recursively applying standard static GNNs (from class \hat{\mathcal{M}} ) over time, can express all properties definable in the product logic \mathsf{PTL}_{\mathsf{P}{},\mathsf{Y}}{\times}\mathsf{K} , which combines the seminal (past) propositional temporal logic \mathsf{PTL}_{\mathsf{P},\mathsf{Y}} and the modal logic \mathsf{K} (Theorem 1 ). • Analogous results hold if we replace \hat{\mathcal{M}} and \mathsf{K} with matching expressiveness GNNs and logics. In particular, we show that such results hold for two specific pairs of static GNNs and logics, recently studied in literature NunnSST24 ; BenediktLMT24 (Theorem 2 ). • In contrast to recursive TGNNs, the class of time-and-graph TGNNs GR22 does not allow us to express all properties expressible in \mathsf{PTL}_{\mathsf{P}{},\mathsf{Y}}{\times}\mathsf{K} (Theorem 3 ). We show, however, that time-and-graph TGNNs can express all properties definable in a fragment of \mathsf{PTL}_{\mathsf{P}{},\mathsf{Y}}{\times}\mathsf{K} , in which the allowed interplay between temporal and modal operators is syntactically restricted (Theorem 4 ). • The class of global TGNNs WR24 also does not allow us to express all properties expressible in \mathsf{PTL}_{\mathsf{P}{},\mathsf{Y}}{\times}\mathsf{K} (Theorem 5 ). As in the previous case, we determine a fragment of \mathsf{PTL}_{\mathsf{P}{},\mathsf{Y}}{\times}\mathsf{K} , such that global TGNNs can express all properties definable in this fragment (Theorem 6 ). This fragment, however, allows for different interactions between temporal and modal operators, than the fragment from Theorem 3 . • We show how our results allow to determine relative expressive power of TGNN classes considered in the paper ( Corollary 1 and Theorem 7 ). Beyond their theoretical significance, these results open the door to novel avenues in explainable and trustworthy AI. Just as logical characterisations of static GNNs have enabled the extraction of symbolic rules from neural models DBLP:conf/kr/CucalaGMK23 ; DBLP:conf/kr/CucalaG24 , our analysis lays the foundation for extracting temporal rules and dynamic specifications from TGNNs. 2 Related work Temporal GNNs. There exists a plethora of TGNN models LongaLSBLLSP23 , differing on representation and processing temporal graphs. There exists various classifications of TGNNs LongaLSBLLSP23 , but one of the main distinction is between snapshot-based models, where a temporal graph is given as a sequence of its timestamped snapshots HajiramezanaliH19 ; SankarWGZY20 ; MicheliT22 ; YouDL22 ; Cini_Marisca_Bianchi_Alippi_2023 , and event-based models, where a temporal graph is given as a sequence of events modifying the a graph structure XuRKKA20 ; rossi2020temporal ; Luo22a . In this paper we focus on the snapshot-based TGNNs, but it is worth to observe that in many settings these two types of temporal graph representation can be translated into each other. Initial work on the expressive power of TGNNs has been conducted exploiting their relation to variants of the Weisfeiler-Lehman isomorphism test SouzaMKG22 ; WR24 and by directly comparing expressiveness of particular TGNNs architectures GR22 ; chen2023calibrate . However, to the best of our knowledge, no work has yet studied the expressive power of TGNNs from the perspective of logics. Logical expressiveness of static GNNs. The seminal logical characterisation of (message-passing) GNNs established that the properties expressible both by GNNs and first-order logic coincide with those definable

Read the complete text