mlsanityData to 7 Oct 2026

Provably expressive temporal graph networks

arXiv 2209.15059 ↗First posted 29 Sep 2022cs.LGcited by 56

Not on the map. Why?

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.

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

Builds on

47 of 66 references.

References · 47

  1. 2017Attention Is All You Needcited by 59,932
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,016
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  7. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  8. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  9. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  10. 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
  11. 2020Simple and Deep Graph Convolutional Networkscited by 857
  12. 2020Temporal Graph Networks for Deep Learning on Dynamic Graphscited by 521
35 more
  1. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  2. 2020Inductive Representation Learning on Temporal Graphscited by 454
  3. 2019EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphscited by 443
  4. 2019Predicting Dynamic Embedding Trajectory in Temporal Interaction Networkscited by 443
  5. 2019Provably Powerful Graph Networkscited by 385
  6. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  7. 2016Structured Sequence Modeling with Graph Convolutional Recurrent Networkscited by 273
  8. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  9. 2019Representation Learning for Dynamic Graphs: A Surveycited by 260
  10. 2021GRAND: Graph Neural Diffusioncited by 258
  11. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  12. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  13. 2019Time2Vec: Learning a Vector Representation of Timecited by 208
  14. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  15. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  16. 2021Inductive Representation Learning in Temporal Networks via Causal Anonymous Walkscited by 188
  17. 2020Random Features Strengthen Graph Neural Networkscited by 184
  18. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  19. 2019What Can Neural Networks Reason About?cited by 155
  20. 2021ETA Prediction with Graph Neural Networks in Google Mapscited by 130
  21. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  22. 2020Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A surveycited by 123
  23. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  24. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  25. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  26. 2017Dynamic Graph Convolutional Networkscited by 83
  27. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  28. 2020APAN: Asynchronous Propagation Attention Network for Real-time Temporal Graph Embeddingcited by 78
  29. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
  30. 2019Understanding the Representation Power of Graph Neural Networks in Learning Graph Topologycited by 52
  31. 2019Self-attention with Functional Time Representation Learningcited by 52
  32. 2018dynnode2vec: Scalable Dynamic Network Embeddingcited by 32
  33. 2020Graph Homomorphism Convolutioncited by 27
  34. 2021On the Equivalence Between Temporal and Static Graph Representations for Observational Predictionscited by 10
  35. 2021Temporal Graph Network Embedding with Causal Anonymous Walks Representationscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 16; 2024: 12; 2025: 15; 2026: 10.

56 papers.

Sort:

  1. 2023Towards Better Dynamic Graph Learning: New Architecture and Unified Librarycited by 154
  2. 2023Do We Really Need Complicated Model Architectures For Temporal Networks?cited by 141
  3. 2023Temporal Graph Benchmark for Machine Learning on Temporal Graphscited by 137
  4. 2023Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunitiescited by 60
  5. 2023TempME: Towards the Explainability of Temporal Graph Neural Networks via Motif Discoverycited by 27
  6. 2024Long Range Propagation on Continuous-Time Dynamic Graphscited by 26
  7. 2024Improving Temporal Link Prediction via Temporal Walk Matrix Projectioncited by 21
  8. 2023Deep learning for dynamic graphs: models and benchmarkscited by 19
  9. 2023GPT-ST: Generative Pre-Training of Spatio-Temporal Graph Neural Networkscited by 14
  10. 2023RDGSL: Dynamic Graph Representation Learning with Structure Learningcited by 13
  11. 2022Modular Flows: Differential Molecular Generationcited by 11
  12. 2023BenchTemp: A General Benchmark for Evaluating Temporal Graph Neural Networkscited by 9
38 more
  1. 2023Towards Expressive Spectral-Temporal Graph Neural Networks for Time Series Forecastingcited by 8
  2. 2024Towards Adaptive Neighborhood for Advancing Temporal Interaction Graph Modelingcited by 8
  3. 2023SPEED: Streaming Partition and Parallel Acceleration for Temporal Interaction Graph Embeddingcited by 7
  4. 2025A Survey of Link Prediction in Temporal Networkscited by 6
  5. 2025Unifying Text Semantics and Graph Structures for Temporal Text-attributed Graphs with Large Language Modelscited by 6
  6. 2022Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphscited by 5
  7. 2023Recurrent Temporal Revision Graph Networkscited by 5
  8. 2022DyG2Vec: Efficient Representation Learning for Dynamic Graphscited by 4
  9. 2023iLoRE: Dynamic Graph Representation with Instant Long-term Modeling and Re-occurrence Preservationcited by 4
  10. 2024Learning-Based Link Anomaly Detection in Continuous-Time Dynamic Graphscited by 4
  11. 2025A Survey on Temporal Interaction Graph Representation Learning: Progress, Challenges, and Opportunitiescited by 4
  12. 2024On the Generalization Capability of Temporal Graph Learning Algorithms: Theoretical Insights and a Simpler Methodcited by 3
  13. 2025UniDyG: A Unified and Effective Representation Learning Approach for Large Dynamic Graphscited by 3
  14. 2025Understanding and Improving Laplacian Positional Encodings For Temporal GNNscited by 3
  15. 2025Are Large Language Models Good Temporal Graph Learners?cited by 3
  16. 2025Learnable Spatial-Temporal Positional Encoding for Link Predictioncited by 3
  17. 2024Scalable and Efficient Temporal Graph Representation Learning via Forward Recent Samplingcited by 2
  18. 2024Todyformer: Towards Holistic Dynamic Graph Transformers with Structure-Aware Tokenizationcited by 2
  19. 2024CoDy: Counterfactual Explainers for Dynamic Graphscited by 2
  20. 2025The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logicscited by 2
  21. 2025Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphscited by 2
  22. 2025T-GRAB: A Synthetic Diagnostic Benchmark for Learning on Temporal Graphscited by 2
  23. 2025Revisiting Node Affinity Prediction in Temporal Graphscited by 2
  24. 2023From random-walks to graph-sprints: a low-latency node embedding framework on continuous-time dynamic graphscited by 1
  25. 2024Temporal Graph Analysis with TGXcited by 1
  26. 2024Expressivity of Representation Learning on Continuous-Time Dynamic Graphs: An Information-Flow Centric Reviewcited by 1
  27. 2025Higher-order Structure Boosts Link Prediction on Temporal Graphscited by 1
  28. 2023Towards Temporal Edge Regression: A Case Study on Agriculture Trade Between Nationscited by 0
  29. 2023LasTGL: An Industrial Framework for Large-Scale Temporal Graph Learningcited by 0
  30. 2024Towards Dynamic Graph Neural Networks with Provably High-Order Expressive Powercited by 0
  31. 2024Information propagation dynamics in Deep Graph Networkscited by 0
  32. 2025Community-Aware Temporal Walks: Parameter-Free Representation Learning on Continuous-Time Dynamic Graphscited by 0
  33. 2025Trajectory Encoding Temporal Graph Networkscited by 0
  34. 2025Graph Structure Learning with Temporal Graph Information Bottleneck for Inductive Representation Learningcited by 0
  35. 2026TFWaveFormer: Temporal-Frequency Collaborative Multi-level Wavelet Transformer for Dynamic Link Predictioncited by 0
  36. 2026Decoupled and Divergence-Conditioned Prompt for Multi-domain Dynamic Graph Foundation Modelscited by 0
  37. 2026Attention Dispersion in Dynamic Graph Transformers: Diagnosis and a Transferable Fixcited by 0
  38. 2026A2QTGN: Adaptive Amplitude Quantum-Integrated Temporal Graph Network for Dynamic Link Predictioncited by 0

50 most cited of 56 All 56 (JSON)