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

Temporal graph learning (TGL) has emerged as an important machine learning problem and is widely used in a number of real-world applications, such as traffic prediction [Yuan and Li, 2021, Zhang et al., 2021], knowledge graphs [Cai et al., 2022, Leblay and Chekol, 2018], and recommender systems [Kumar et al., 2019, Rossi et al., 2020, Xu et al., 2020a]. A typical downstream task of temporal graph learning is link prediction, which focuses on predicting future interactions among nodes. For example in an online video recommender system, the user-video clicks can be modeled as a temporal graph whose nodes represent users and videos, and links are associated with timestamps indicating when users click videos. Link prediction between nodes can be used to predict if and when a user is interested in a video. Therefore, designing graph learning models that can capture node evolutionary patterns and accurately predict future links is important. TGL is generally more challenging than static graph learning, thereby requiring more sophisticated algorithms to model the temporal evolutionary patterns [Huang et al., 2023]. In recent years, many TGL algorithms [Kumar et al., 2019, Xu et al., 2020a, Rossi et al., 2020, Sankar et al., 2020, Wang et al., 2021e] have been proposed that leverage memory blocks, self-attention, time-encoding function, recurrent neural networks (RNNs), temporal walks, and message passing to better capture the meaningful structural or temporal patterns. For instance, JODIE [Kumar et al., 2019] maintains a memory block for each node and utilizes an RNN to update the memory blocks upon the occurance of each interaction; TGAT [Xu et al., 2020a] utilizes self-attention message passing to aggregate neighbor information on the temporal graph; TGN [Rossi et al., 2020] combines memory blocks with message passing to allow each node in the temporal graph to have a receptive field that is not limited by the number of message-passing layers; DySAT [Sankar et al., 2020] uses self-attention to capture structural information and uses RNN to capture temporal dependencies; CAW [Wang et al., 2021e] captures temporal dependencies between nodes by performing multiple temporal walks from the root