Research map / Graph learning / GNN architectures
The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterises the logical expressiveness of three temporal GNN classes (recursive, time-and-graph, global) by relating them to the two-dimensional product logic PTL×K and its fragments.
Problem
Understanding which spatio-temporal graph properties temporal GNNs can express, since prior expressiveness work on TGNNs used Weisfeiler-Leman or direct architecture comparisons rather than logic.
Approach
Model TGNN computations as combinations of modal (graph) and temporal (past-time) operators in a product logic PTLp×K; recursive TGNNs capture the full product logic, while time-and-graph and global TGNNs capture only syntactically restricted fragments.
Key results
- PTLK is at most as expressive as recursive TGNNs with truncated-ReLU MPNNs: PTLK ≤ idTGNN[M̂] (Theorem on recursive TGNNs).
- PTLK is not expressible by time-and-graph TGNNs or global TGNNs for any MPNN, cell, time function class, via counterexamples on formulas like Diamond(c1 ∧ prev Diamond c2) and prev c1.
- Fragment L1 is captured by time-and-graph TGNNs with single-layer truncated-ReLU FNN cells; fragment L2 is captured by global TGNNs with msg-MPNNs and time2vec.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use recursive TGNNs that apply static MPNNs recursively over time | Recursive TGNNs with truncated-ReLU FNN combinations and sum aggregation · PTL × K temporal graph properties | logical expressiveness | Helped |
| replace K and its matching MPNN with lognunn and its matching MPNN | Recursive TGNNs · tlognunn temporal graph properties | logical expressiveness | Helped |
| use OL-truncated-ReLU GNNs as the matching MPNN for L-MP² | Recursive TGNNs · tlogbenedikt temporal graph properties | logical expressiveness | Helped |
| use time-and-graph TGNNs instead of an architecture capable of arbitrary temporal–spatial operator interaction | Time-and-graph TGNNs · PTL × K temporal graph properties | logical expressiveness | Hurt |
| restrict formulas to fragment L1, with constrained interaction between temporal and modal operators | Time-and-graph TGNNs with truncated-ReLU MPNNs and single-layer truncated-ReLU cell functions · L1 temporal graph properties | logical expressiveness | Helped |
| use global TGNNs with temporal messages passed among nodes across time | Global TGNNs · PTL × K temporal graph properties | logical expressiveness | Hurt |
| restrict formulas to L2, where past operators apply to modal subformulas | Global TGNNs with learnable message functions, time2vec, and concatenation · L2 temporal graph properties | logical expressiveness | Helped |
| replace recursive TGNNs with time-and-graph TGNNs | Time-and-graph TGNNs with truncated-ReLU MPNNs and single-layer truncated-ReLU cell functions · Temporal graph properties expressible by the time-and-graph class | logical expressiveness | Hurt |
| use time-and-graph TGNNs rather than global TGNNs, or vice versa | Time-and-graph and global TGNNs · Temporal graph properties | relative logical expressiveness | Mixed |
Surprising findings
- Global TGNNs cannot express the simple property prev c1 (a node's own past colour), since they only access neighbours' past information.
Limitations
- Results are purely formal expressiveness; they do not show which properties are learnable in practice.
- Covers only snapshot-based (discrete) temporal graphs and specific TGNN classes.
- Tight expressive bounds not established.
Experimental setup
Baselines: time-and-graph TGNNs global TGNNs recursive TGNNs
Builds on: PTL×K product logic MPNN / AC-GNN logical characterisation time2vec GRU
Closest papers by meaning
- Logical characterizations of recurrent graph neural networks with reals and floats (NeurIPS 2024 · similarity 0.89)
- Expressive Power of Temporal Message Passing (AAAI 2025 · similarity 0.89)
- Recurrent Graph Neural Networks and Their Connections to Bisimulation and Logic (AAAI 2024 · similarity 0.88)
- TeLoGraF: Temporal Logic Planning via Graph-encoded Flow Matching (ICML 2025 · similarity 0.86)
- Learning More Expressive General Policies for Classical Planning Domains (AAAI 2025 · similarity 0.85)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.