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.

本研究通过研究不同TGL算法的广义能力以及与GNN-/RNN-based TGL方法的层数/步数和特征-标签对齐度得分的关系建立了理论基础，提出了Simplified-Temporal-Graph-Network，该算法具有小的泛化误差、改进的整体性能和较低的模型复杂性。实验结果表明了我们的方法的有效性，理论发现和提出的算法为未来研究的实际TGL算法设计提供了重要见解。

关于时间图学习算法的泛化能力：理论洞察和简化方法