# Provably expressive temporal graph networks

arXiv: https://arxiv.org/abs/2209.15059 · HTML: https://mlsanity.com/paper/2209.15059/

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 66 references that are in the map.
- First posted on arXiv 29 Sep 2022.

## Builds on (most cited first, 30 of 47)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks](https://mlsanity.com/paper/1908.01207/) (2019)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Structured Sequence Modeling with Graph Convolutional Recurrent Networks](https://mlsanity.com/paper/1612.07659/) (2016)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019)
- [GRAND: Graph Neural Diffusion](https://mlsanity.com/paper/2106.10934/) (2021)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Time2Vec: Learning a Vector Representation of Time](https://mlsanity.com/paper/1907.05321/) (2019)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)

## Built on by (most cited first, 30 of 56)

- [Towards Better Dynamic Graph Learning: New Architecture and Unified Library](https://mlsanity.com/paper/2303.13047/) (2023)
- [Do We Really Need Complicated Model Architectures For Temporal Networks?](https://mlsanity.com/paper/2302.11636/) (2023)
- [Temporal Graph Benchmark for Machine Learning on Temporal Graphs](https://mlsanity.com/paper/2307.01026/) (2023)
- [Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunities](https://mlsanity.com/paper/2302.01018/) (2023)
- [Long Range Propagation on Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2406.02740/) (2024)
- [TempME: Towards the Explainability of Temporal Graph Neural Networks via Motif Discovery](https://mlsanity.com/paper/2310.19324/) (2023)
- [Improving Temporal Link Prediction via Temporal Walk Matrix Projection](https://mlsanity.com/paper/2410.04013/) (2024)
- [Deep learning for dynamic graphs: models and benchmarks](https://mlsanity.com/paper/2307.06104/) (2023)
- [GPT-ST: Generative Pre-Training of Spatio-Temporal Graph Neural Networks](https://mlsanity.com/paper/2311.04245/) (2023)
- [RDGSL: Dynamic Graph Representation Learning with Structure Learning](https://mlsanity.com/paper/2309.02025/) (2023)
- [Modular Flows: Differential Molecular Generation](https://mlsanity.com/paper/2210.06032/) (2022)
- [BenchTemp: A General Benchmark for Evaluating Temporal Graph Neural Networks](https://mlsanity.com/paper/2308.16385/) (2023)
- [Towards Expressive Spectral-Temporal Graph Neural Networks for Time Series Forecasting](https://mlsanity.com/paper/2305.06587/) (2023)
- [Towards Adaptive Neighborhood for Advancing Temporal Interaction Graph Modeling](https://mlsanity.com/paper/2406.11891/) (2024)
- [SPEED: Streaming Partition and Parallel Acceleration for Temporal Interaction Graph Embedding](https://mlsanity.com/paper/2308.14129/) (2023)
- [A Survey of Link Prediction in Temporal Networks](https://mlsanity.com/paper/2502.21185/) (2025)
- [Unifying Text Semantics and Graph Structures for Temporal Text-attributed Graphs with Large Language Models](https://mlsanity.com/paper/2503.14411/) (2025)
- [Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs](https://mlsanity.com/paper/2210.00032/) (2022)
- [DyG2Vec: Efficient Representation Learning for Dynamic Graphs](https://mlsanity.com/paper/2210.16906/) (2022)
- [Recurrent Temporal Revision Graph Networks](https://mlsanity.com/paper/2309.12694/) (2023)
- [iLoRE: Dynamic Graph Representation with Instant Long-term Modeling and Re-occurrence Preservation](https://mlsanity.com/paper/2309.02012/) (2023)
- [Learning-Based Link Anomaly Detection in Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2405.18050/) (2024)
- [A Survey on Temporal Interaction Graph Representation Learning: Progress, Challenges, and Opportunities](https://mlsanity.com/paper/2505.04461/) (2025)
- [On the Generalization Capability of Temporal Graph Learning Algorithms: Theoretical Insights and a Simpler Method](https://mlsanity.com/paper/2402.16387/) (2024)
- [UniDyG: A Unified and Effective Representation Learning Approach for Large Dynamic Graphs](https://mlsanity.com/paper/2502.16431/) (2025)
- [Understanding and Improving Laplacian Positional Encodings For Temporal GNNs](https://mlsanity.com/paper/2506.01596/) (2025)
- [Are Large Language Models Good Temporal Graph Learners?](https://mlsanity.com/paper/2506.05393/) (2025)
- [Learnable Spatial-Temporal Positional Encoding for Link Prediction](https://mlsanity.com/paper/2506.08309/) (2025)
- [Scalable and Efficient Temporal Graph Representation Learning via Forward Recent Sampling](https://mlsanity.com/paper/2402.01964/) (2024)
- [Todyformer: Towards Holistic Dynamic Graph Transformers with Structure-Aware Tokenization](https://mlsanity.com/paper/2402.05944/) (2024)

## Abstract (arXiv)

Temporal graph networks (TGNs) have gained prominence as models for embedding dynamic interactions, but little is known about their theoretical underpinnings. We establish fundamental results about the representational power and limits of the two main categories of TGNs: those that aggregate temporal walks (WA-TGNs), and those that augment local message passing with recurrent memory modules (MP-TGNs). Specifically, novel constructions reveal the inadequacy of MP-TGNs and WA-TGNs, proving that neither category subsumes the other. We extend the 1-WL (Weisfeiler-Leman) test to temporal graphs, and show that the most powerful MP-TGNs should use injective updates, as in this case they become as expressive as the temporal WL. Also, we show that sufficiently deep MP-TGNs cannot benefit from memory, and MP/WA-TGNs fail to compute graph properties such as girth. These theoretical insights lead us to PINT -- a novel architecture that leverages injective temporal message passing and relative positional features. Importantly, PINT is provably more expressive than both MP-TGNs and WA-TGNs. PINT significantly outperforms existing TGNs on several real-world benchmarks.