Abstract:Temporal graph neural network (TGNN) has demonstrated strong performance in dynamic graph representation learning and are widely used in temporal prediction tasks. TGNNs rely on multi-layer temporal sampling to capture temporal sequences. Although deeper models have the potential to improve representation capability, their development is constrained by sampling complexity, which grows exponentially with the number of layers and sampled neighbors. Existing studies mainly focus on optimizing data transfer, while the sampling stage remains under explored. This study investigates the widely used most-recent neighbor sampling strategy in TGNNs, analyzes its incremental property, and proposes an incremental computational graph caching scheme, IncCGCache, which reuses historical sampling results and updates them incrementally to eliminate redundant sampling, reducing the complexity by an order of magnitude under cache hits. Vectorized indexing is employed to enable parallel cache operations, while cache updates are decoupled from model computation and executed asynchronously, further improving the speedup. In addition, to mitigate the negative impact of commonly used random negative sampling on cache effectiveness, a cache-aware negative sampling strategy is proposed, which improves the cache hit rate with negligible impact on model performance. Experimental results on representative models such as TGN, TIGER, and SEAN and commonly used datasets demonstrate that IncCGCache provides up to 3.68× speedup for the sampling stage.