EvoST: Learning Evolving Graph Structures and Temporal Patterns for Continual Spatio-Temporal Traffic Forecasting

Continual spatio-temporal traffic forecasting is ought to accommodate expanding traffic sensor networks and adapt to spatial and temporal distribution shifts across successive periods. Existing methods address network evolution while underexploit node-specific spatial correlations and explicit temporal patterns. In this paper, we propose EvoST, a spatio-temporal learning paradigm that jointly learns evolving graph structures and temporal patterns for continual traffic forecasting. For spatial modeling, EvoST maintains two learnable node embeddings to parameterize adaptive graph adjacencies. At each period transition, embeddings of existing nodes are inherited and augmented with randomly initialized embeddings of newly deployed traffic sensors. The optimization in the current period retains and refines previously learned relations and discovers new dependencies involving newly added nodes. For temporal modeling, a calendar embedding dictionary independent of the sensor count is inherited and updated across periods, transferring learned periodic regularities while adapting to changing temporal patterns. We instantiate this paradigm with linearized kernel graph convolution for efficient spatial aggregation and lightweight weekly time embeddings that combine discrete low-rank representations with continuous phase features. These components enable scalable modeling of spatial correlations and temporal regularities as the traffic network expands. Comprehensive experiments on three real-world continuous traffic flow datasets demonstrate the effectiveness, versatility, efficiency, and interpretability of our method. The source codes of EvoST are available at https://anonymous.4open.science/r/EvoST for review.