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

• URL: http://arxiv.org/abs/2505.11930v1
• Date: Sat, 17 May 2025 09:34:57 GMT
• Title: The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics
• Authors: Marco Sälzer, Przemysław Andrzej Wałęga, Martin Lange,
• Abstract summary: We study the logical characterisation of temporal GNNs by connecting them to two-dimensional product logics.<n>We show that the expressive power of temporal GNNs depends on how graph and temporal components are combined.
• Score: 4.096453902709292
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Position: Message-passing and spectral GNNs are two sides of the same coin [60.47572761832418]
  Graph neural networks (GNNs) are commonly divided into message-passing neural networks (MPNNs) and spectral graph neural networks (SGNs)<n>This paper argues that this divide is mostly artificial, hindering progress in the field.
  arXiv  Detail & Related papers  (2026-02-10T17:53:40Z)
• Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregation [22.086161213961244]
  We propose Path-Neighbor enhanced GNN (PN-GNN) to enhance the logical expressive power of GNN.<n>First, we analyze the logical expressive power of existing GNN-based methods and point out the shortcomings of these methods.<n>Then, we theoretically investigate the logical expressive power of PN-GNN, showing that it not only has strictly stronger expressive power than C-GNN but also that its $(k+1)$-hop logical expressiveness is strictly superior to that of $k$-hop.
  arXiv  Detail & Related papers  (2025-11-11T08:59:10Z)
• Weisfeiler-Lehman meets Events: An Expressivity Analysis for Continuous-Time Dynamic Graph Neural Networks [0.0]
  Graph Neural Networks (GNNs) are known to match the distinguishing power of the 1-Weisfeiler-Lehman (1-WL) test.<n>GNNs can universally approximate any target function on graphs in probability up to any precision.<n>We extend the theory of attributed discrete-dynamic graphs to attributed continuous-time dynamic graphs with arbitrary connectivity.
  arXiv  Detail & Related papers  (2025-08-25T14:10:45Z)
• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
  Graph Neural Networks (GNNs) have become the standard approach for learning and reasoning over relational data.<n>This paper explores the computational limitations of GNNs through the lens of circuit complexity.<n>Specifically, we analyze the circuit complexity of common GNN architectures and prove that under constraints of constant-depth layers, linear or sublinear embedding sizes, and precision, GNNs cannot solve key problems such as graph connectivity and graph isomorphism.
  arXiv  Detail & Related papers  (2025-01-11T05:54:10Z)
• DTFormer: A Transformer-Based Method for Discrete-Time Dynamic Graph Representation Learning [38.53424185696828]
  The representation learning of Discrete-Time Dynamic Graphs (DTDGs) has been extensively applied to model the dynamics of temporally changing entities and their evolving connections. This paper introduces a novel representation learning method DTFormer for DTDGs, pivoting from the traditional GNN+RNN framework to a Transformer-based architecture.
  arXiv  Detail & Related papers  (2024-07-26T05:46:23Z)
• Temporal Spiking Neural Networks with Synaptic Delay for Graph Reasoning [91.29876772547348]
  Spiking neural networks (SNNs) are investigated as biologically inspired models of neural computation. This paper reveals that SNNs, when amalgamated with synaptic delay and temporal coding, are proficient in executing (knowledge) graph reasoning.
  arXiv  Detail & Related papers  (2024-05-27T05:53:30Z)
• Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats [6.176021290715425]
  In this article, we give exact logical characterizations of recurrent graph neural networks (GNNs) in two scenarios.<n>For floats, the formalism matching recurrent GNNs is a rule-based modal logic with counting, while for reals we use a suitable infinitary modal logic.<n>Applying our characterizations, we prove that, relative to graph properties definable in monadic second-order logic, our infinitary and rule-based logics are equally expressive.
  arXiv  Detail & Related papers  (2024-05-23T14:19:21Z)
• LOGICSEG: Parsing Visual Semantics with Neural Logic Learning and Reasoning [73.98142349171552]
  LOGICSEG is a holistic visual semantic that integrates neural inductive learning and logic reasoning with both rich data and symbolic knowledge. During fuzzy logic-based continuous relaxation, logical formulae are grounded onto data and neural computational graphs, hence enabling logic-induced network training. These designs together make LOGICSEG a general and compact neural-logic machine that is readily integrated into existing segmentation models.
  arXiv  Detail & Related papers  (2023-09-24T05:43:19Z)
• Contextualizing MLP-Mixers Spatiotemporally for Urban Data Forecast at Scale [54.15522908057831]
  We propose an adapted version of the computationally-Mixer for STTD forecast at scale. Our results surprisingly show that this simple-yeteffective solution can rival SOTA baselines when tested on several traffic benchmarks. Our findings contribute to the exploration of simple-yet-effective models for real-world STTD forecasting.
  arXiv  Detail & Related papers  (2023-07-04T05:19:19Z)
• Towards Expressive Spectral-Temporal Graph Neural Networks for Time Series Forecasting [101.5022396668152]
  Spectral-temporal graph neural network is a promising abstraction underlying most time series forecasting models.<n>We establish a theoretical framework that unravels the expressive power of spectral-temporal GNNs.<n>Our findings pave the way for devising a broader array of provably expressive GNN-based models for time series.
  arXiv  Detail & Related papers  (2023-05-11T05:56:38Z)
• Space-Time Graph Neural Networks with Stochastic Graph Perturbations [100.31591011966603]
  Space-time graph neural networks (ST-GNNs) learn efficient graph representations of time-varying data. In this paper we revisit the properties of ST-GNNs and prove that they are stable to graph stabilitys. Our analysis suggests that ST-GNNs are suitable for transfer learning on time-varying graphs.
  arXiv  Detail & Related papers  (2022-10-28T16:59:51Z)
• Universal approximation property of invertible neural networks [76.95927093274392]
  Invertible neural networks (INNs) are neural network architectures with invertibility by design. Thanks to their invertibility and the tractability of Jacobian, INNs have various machine learning applications such as probabilistic modeling, generative modeling, and representation learning.
  arXiv  Detail & Related papers  (2022-04-15T10:45:26Z)
• Space-Time Graph Neural Networks [104.55175325870195]
  We introduce space-time graph neural network (ST-GNN) to jointly process the underlying space-time topology of time-varying network data. Our analysis shows that small variations in the network topology and time evolution of a system does not significantly affect the performance of ST-GNNs.
  arXiv  Detail & Related papers  (2021-10-06T16:08:44Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  Markov Logic Networks (MLNs) can be used to address many knowledge graph problems. Inference in MLN is computationally intensive, making the industrial-scale application of MLN very difficult. We propose a graph neural network (GNN) variant, named ExpressGNN, which strikes a nice balance between the representation power and the simplicity of the model.
  arXiv  Detail & Related papers  (2020-01-29T23:34:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.