Pattern in Motion: Retrieval-Augmented Learning for Dynamic Spatio-Temporal Graphs

Spatio-Temporal Graph Neural Networks (STGNNs) have emerged as powerful tools for modeling dynamic systems, yet they face critical generalization challenges in streaming Spatio-Temporal Out-of-Distribution (STOOD) scenarios, where spatial structures and temporal dynamics evolve beyond the distributions observed in historical training periods. Existing approaches encounter a fundamental dilemma: parametric methods suffer from catastrophic forgetting and gradient conflicts, while replay-based methods struggle to distinguish cross-period recurring patterns from period-specific transient patterns. To overcome these limitations, we propose PRAL (Pattern Retrieval-Augmented Learning for Dynamic Spatio-Temporal Graphs), a novel framework that explicitly stores historical knowledge in external pattern libraries rather than implicitly encoding it in model parameters. PRAL constructs multidimensional pattern libraries that capture representative patterns across spatial, temporal, and Spatio Temporal dimensions, where pattern keys serve as efficient retrieval indices while pattern values encapsulate rich contextual features. Recurring and transient components within the stored patterns are further distinguished through the Stable Subspace Projector (SSP) and Shift-Aware Retrieval Reweighting (SR2) mechanisms. After training, PRAL retrieves relevant patterns via similarity-based matching and adaptively fuses them with current observations through a learnable balancing mechanism. Extensive experiments on multiple real-world streaming graph datasets demonstrate that PRAL achieves the best average performance among all compared methods, with an average MAE/RMSE/MAPE improvement of 15-30% over the strongest non-retrieval baselines, while trading off against STRAP on certain backbone-dataset configurations; it further achieves robust generalization in streaming STOOD settings without task-specific fine-tuning.