Research map / Graph learning / GNN architectures
Expressive Power of Temporal Message Passing
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 expressive power of global and local temporal message-passing GNNs via Weisfeiler-Leman tests on constructed knowledge graphs, showing they are incomparable on arbitrary temporal graphs and local is strictly more expressive on colour-persistent ones, supported by TGB 2.0 link-prediction experiments.
Problem
Expressive power of temporal message-passing GNNs is poorly understood; it is unclear how global (aggregating embeddings from all past time points) and local (aggregating only same-time embeddings) mechanisms compare.
Approach
Transform temporal graphs into knowledge graphs (one global, one local) so that standard relational 1-WL exactly characterises the node distinguishability of each temporal message-passing type; use this to prove incomparability in general and local superiority on colour-persistent graphs, and introduce timewise isomorphism as the right indistinguishability notion.
Key results
- On colour-persistent benchmarks, the local model achieved higher MRR than the global model on all three datasets (tgbl-wiki 0.264 vs 0.223, tgbl-review 0.359 vs 0.321, tgbl-coin 0.635 vs 0.628).
- Global and local models reach nearly equal MRR at 5 layers on tgbl-wiki, consistent with the theory that local is more expressive but differences are small.
- Global and local temporal message-passing mechanisms are incomparable on arbitrary temporal graphs; local is strictly more expressive on colour-persistent graphs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use local rather than global temporal message passing | Proof-of-concept temporal message-passing models · tgbl-wiki | MRR: 0.223 -> 0.264 | Helped |
| Use local rather than global temporal message passing | Proof-of-concept temporal message-passing models · tgbl-review | MRR: 0.321 -> 0.359 | Helped |
| Use local rather than global temporal message passing | Proof-of-concept temporal message-passing models · tgbl-coin | MRR: 0.628 -> 0.635 | Helped |
| Vary the number of message-passing layers from 1 to 8 (ablation) | Global model · tgbl-wiki | MRR | Helped |
| Vary the number of message-passing layers from 1 to 8 (ablation) | Local model · tgbl-wiki | MRR | Helped |
| Use random node features (ablation) | Global and local models · Temporal link prediction benchmarks | MRR | No clear effect |
| Use transductively learnable node features (ablation) | Global and local models · Temporal link prediction benchmarks | MRR | Hurt |
Surprising findings
- Global and local temporal message-passing can distinguish pointwise isomorphic nodes, so pointwise isomorphism is not an adequate indistinguishability notion.
- Global message-passing is not more expressive than local in general, contrary to the expectation that aggregating over all past time points yields greater power.
Limitations
- Experiments use basic, untuned models and small-to-medium benchmarks; differences in MRR are relatively small.
- Global model training uses a train-time approximation that freezes embeddings from previous time points, so training is not exact.
- Results concern node distinguishability under 1-WL, not generalisation or graph-level tasks.
Experimental setup
Datasets: tgbl-wiki tgbl-review tgbl-coin
Benchmarks: tgbl-wiki tgbl-review tgbl-coin
Metrics: MRR
Baselines: global temporal GNN (TE-style) local temporal GNN (MP-TGN-style)
Builds on: 1-WL relational 1-WL (R-MPNN) TGAT TGN TDGNN NAT
Closest papers by meaning
- Provably expressive temporal graph networks (NeurIPS 2022 · similarity 0.90)
- Towards Dynamic Message Passing on Graphs (NeurIPS 2024 · similarity 0.89)
- The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics (NeurIPS 2025 · similarity 0.89)
- What Expressivity Theory Misses: Message Passing Complexity for GNNs (NeurIPS 2025 · similarity 0.88)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.87)
- State Space Models on Temporal Graphs: A First-Principles Study (NeurIPS 2024 · similarity 0.87)
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.