# On the Generalization Capability of Temporal Graph Learning Algorithms: Theoretical Insights and a Simpler Method

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 60 references that are in the map.
- First posted on arXiv 26 Feb 2024.

## Builds on (most cited first, 19 of 19)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [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)
- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)
- [dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning](https://mlsanity.com/paper/1809.02657/) (2018)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [TCL: Transformer-based Dynamic Graph Modelling via Contrastive Learning](https://mlsanity.com/paper/2105.07944/) (2021)
- [Temporal Knowledge Graph Completion: A Survey](https://mlsanity.com/paper/2201.08236/) (2022)
- [TGL: A General Framework for Temporal GNN Training on Billion-Scale Graphs](https://mlsanity.com/paper/2203.14883/) (2022)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [Provably expressive temporal graph networks](https://mlsanity.com/paper/2209.15059/) (2022)
- [Double Equivariance for Inductive Link Prediction for Both New Nodes and New Relation Types](https://mlsanity.com/paper/2302.01313/) (2023)
- [Generalization Properties of NAS under Activation and Skip Connection Search](https://mlsanity.com/paper/2209.07238/) (2022)
- [Time-Aware Neighbor Sampling for Temporal Graph Networks](https://mlsanity.com/paper/2112.09845/) (2021)
- [On the Equivalence between Positional Node Embeddings and Structural Graph Representations](https://mlsanity.com/paper/1910.00452/) (2019)
- [Long Short-Term Preference Modeling for Continuous-Time Sequential Recommendation](https://mlsanity.com/paper/2208.00593/) (2022)

## Built on by (most cited first, 3 of 3)

- [BACKTIME: Backdoor Attacks on Multivariate Time Series Forecasting](https://mlsanity.com/paper/2410.02195/) (2024)
- [DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs](https://mlsanity.com/paper/2408.06966/) (2024)
- [Towards Ideal Temporal Graph Neural Networks: Evaluations and Conclusions after 10,000 GPU Hours](https://mlsanity.com/paper/2412.20256/) (2024)

## Abstract (arXiv)

Temporal Graph Learning (TGL) has become a prevalent technique across diverse real-world applications, especially in domains where data can be represented as a graph and evolves over time. Although TGL has recently seen notable progress in algorithmic solutions, its theoretical foundations remain largely unexplored. This paper aims at bridging this gap by investigating the generalization ability of different TGL algorithms (e.g., GNN-based, RNN-based, and memory-based methods) under the finite-wide over-parameterized regime. We establish the connection between the generalization error of TGL algorithms and "the number of layers/steps" in the GNN-/RNN-based TGL methods and "the feature-label alignment (FLA) score", where FLA can be used as a proxy for the expressive power and explains the performance of memory-based methods. Guided by our theoretical analysis, we propose Simplified-Temporal-Graph-Network, which enjoys a small generalization error, improved overall performance, and lower model complexity. Extensive experiments on real-world datasets demonstrate the effectiveness of our method. Our theoretical findings and proposed algorithm offer essential insights into TGL from a theoretical standpoint, laying the groundwork for the designing practical TGL algorithms in future studies.