On the Generalization Capability of Temporal Graph Learning Algorithms:
  Theoretical Insights and a Simpler Method
Weilin Cong Jian Kang Hanghang Tong Mehrdad Mahdavi
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.