Tracking Topological Shifts: How Can Dynamic Graph Invariant Learning Enable Reliable Out-of-Time Spatio-Temporal Prediction?

1 Introduction

With the development of smart cities, spatio-temporal prediction has become a critical pillar for urban management and planning [Lv et al., 2014; Liang et al., 2021]. However, underlying traffic generation mechanisms evolve continuously over time, driven by factors such as the opening of new subway lines or shifts in commercial hubs [Wang et al., 2023]. This phenomenon directly violates the core assumption of independent and identically distributed (i.i.d.) training and test data in traditional spatio-temporal models, resulting in a decline in predictive performance when deployed in an evolved real-world environment. Therefore, developing robust methods capable of adapting to such distribution shifts is essential

*Corresponding authors.

(a) Various incidents of road network (b) Dynamic evolution of graph topology

Figure 1: Evolution of graph topology driven by traffic incidents

for ensuring the long-term reliability of models in dynamic urban systems.

To address this problem, researchers have increasingly focused on out-of-distribution (OOD) learning paradigms, which enhance model robustness across diverse and shifting data distributions [Li et al., 2025]. These methods aim to uncover underlying stable causal mechanisms or invariant relationships from observed data under varying conditions. Strategies include manually constructing causal models [Xia et al., 2023; Zhou et al., 2023], using environments as self-supervision signals to disentangle confounding factors [Ji et al., 2025], or augmenting environment diversity via graph perturbations [Wang et al., 2024]. By extracting robust knowledge, these approaches improve model generalization to new distributions without requiring additional training.

Although previous work has achieved significant progress in spatio-temporal prediction under distribution shift, they typically assume shift factors are independent to the passage of time, such as weather or accidents. However, in non-stationary systems like traffic, shifts often occur systematically as time progresses, for instance, the persistent topological dynamics (see Fig. 1(b)) induced by real-world changes (see Fig. 1(a)), which continuously introduce new and unforeseen environments associated with the progression of time. This represents a temporal evolution of topology. Therefore, addressing such shifts that are inherent to the passage of time, referred to as out-of-time (OOT) generalization, is essential for a model's ability to maintain performance when deployed across future unseen time periods. Existing methods typically learn from static graph structures, overlooking gradual, long-term topological evolution. To overcome this, a model must explicitly capture topological dy-

namics and track the graph's own evolution.

However, two major challenges must be addressed to achieve this goal. First, how to construct a dynamic graph adaptable to continuous evolution and OOT generalization? Existing work often rely on ahistorical, fullyconnected, and deterministic graph structures. However, graph evolution is gradual, not instantaneous, such as the strengthened correlations caused by the opening of a new subway line. Moreover, fully-connected graphs introduce spurious dependencies that obscure robust spatial patterns [Ju et al., 2024], while deterministic graphs cannot adequately model the uncertainty and temporariness of structural changes caused by unforeseen events. Second, how to learn node-level knowledge that is invariant to dynamic topological shifts? Existing methods often apply random interventions to the global graph to create training environments, ignoring the heterogeneous and node-specific nature of topological change. For example, connections at an accidentprone intersection are more likely to toggle abruptly than those along a stable one-way arterial. Additionally, using a globally shared prediction function can hinder the learning of node-specific invariant patterns, ultimately limiting OOT generalization.

To address the aforementioned challenges, this paper introduces DynaSTar, a Dynamic Spatio Temporal Graph Invariant learning model for robust traffic prediction. To track dynamic topology, we employ a dynamic probabilistic graph structure, where each edge is parameterized as a Bernoulli distribution whose parameters evolve via a momentum-based update rule. This design ensures the graph reflects gradual, historically-grounded structural changes. A sparse sampling mechanism is then applied to instantiate a clear, sparse adjacency matrix at each step, reducing spurious edges and enhancing robustness. Next, to extract representations robust to heterogeneous node conditions, we propose neighborhood environment set construction to simulates diverse, plausible topological shift scenarios for each node. For prediction, we use a modulated predictor that fuses node-conditioned vectors with a global predictor, allowing the model to learn both locally stable and globally transferable patterns. Finally, guided by multi-objective optimization, the model jointly integrates accurate prediction, and node-heterogeneous invariant knowledge, improving its OOT generalization. The main contributions of this paper are summarized as follows:

• To the best of our knowledge, this work presents the first formal investigation that explicitly models topological dynamics to address OOT generalization in spatiotemporal traffic prediction, distinguishing it from conventional OOD scenarios.
• We propose DynaSTar, a novel framework that integrates dynamic topology tracking with nodeheterogeneous invariant learning for robust OOT spatiotemporal prediction. Our model employs a evolving dynamic graph coupled with a node-specific environment construction and modulation mechanism to capture topological shifts and extract heterogeneous invariant representations.
• Extensive experiments on two large-scale, long-term

real-world datasets demonstrate DynaSTar's superior OOT generalization performance across various scenarios with dynamic topologies. The code is made publicly available at https://github.com/ShaunHao/dynastar.

2 RelatedWork

Accurate spatio-temporal prediction is crucial for intelligent transportation systems in various tasks, such as urban flow [Gong et al., 2022; Qu et al., 2023; Lv et al., 2026], traffic speed [Weng et al., 2023; Weng et al., 2025a; Huang et al., 2025], and travel time [Shen et al., 2025]. However, distributional inconsistency in urban systems poses a cross-scenario generalization challenge for models trained under the i.i.d. assumption. To enhance models' generalization, research focuses on learning cross-scenario invariant knowledge. Knowledge transfer methods [Jin et al., 2022; Yuan et al., 2024; Li et al., 2024; Hao et al., 2025] learn citylevel generalizable patterns, yet overlook temporal distribution shifts within cities. OOD learning methods, which use prior knowledge to simulate test distributions during training, are gaining traction. Temporal OOD methods [Du et al., 2021; Lu et al., 2022] employ unsupervised domain generalization, while spatio-temporal OOD techniques leverage structural causal models to learn generalizable representations. Among them, [Xia et al., 2023] for causal data generation, [Zhou et al., 2023] for invariant relations, [Ji et al., 2025] for disentangling confounders, and [Wang et al., 2024] for semantic graph interventions. However, current research primarily models distribution shifts using static adjacency relations, overlooking inherent topological dynamics and structural evolution. This causes learned knowledge to degrade over time, impairing OOT generalization.

3 Preliminaries

Definition 1 (Temporal Phase). To analyze distribution shifts after model deployments, we partition the continuous timeline into non-overlapping intervals (e.g., several months or a year) called temporal phases. Let P𝑘 denote the 𝑘-th phase, containing timestamps {𝑡 𝑘 1 , . . . , 𝑡 𝑘 𝐿𝑘 }. Data distributions and topologies may shift across phases.

Definition 2 (Spatio-Temporal Graph). At time 𝑡, the traffic network is represented as a graph G𝑡 = (V, X𝑡 , A𝑡 ). V = {𝑣1, . . . , 𝑣𝑁} is the node set. X𝑡 ∈ R 𝑁×𝐶 denotes node features (e.g., traffic flow). A𝑡 ∈ R 𝑁×𝑁 is a adjacency matrix encoding inter-node relationships.

Definition 3 (Spatio-Temporal Prediction under Dynamic Topology). Given a historical window X[𝑡-𝑇ℎ+1:𝑡 ] and corresponding adjacency matrices A[𝑡-𝑇ℎ+1:𝑡 ] , the goal is to learn a predition function 𝐹Θ to predict future states:

Definition 4 (Long-Term Deployment Spatio-Temporal Prediction Learning). In real-world deployment, the model encounters unseen temporal phases {P𝑀+1, . . . }. Both the data distribution 𝑃(X, Y) and the graph structure A𝑡 may shift across phases. The objective is to train a model on historical phases {P1, . . . , P𝑀} that minimizes the expected prediction error on all future phases, thereby requiring OOT generalization under topological dynamics.

4 Methodology

This section details our DynaSTar model depicted in Fig. 2, which first extracts an evolving dynamic graph from traffic data, then performs node-specific future prediction. Joint training enables learning invariant predictive knowledge for topological shifts. The key designs are described below.

4.1 Dynamic Topological Shifts Tracking

Modeling a graph structure that reflects the continuous evolution of topologies is a prerequisite for reliable long-term deployment of traffic prediction. To achieve this, we first compute a dynamic correlation graph to quantify the realtime linkage strength between nodes. Next, we introduce a momentum mechanism to update the graph, smooth the transition of topological changes, and then transformed it into a dynamic probabilistic graph prototype. Finally, a sparse binary adjacency matrix is sampled from the updated graph via reparameterization trick for prediction learning.

Memory-Enhanced Dynamic Correlation Graph Construction

To capture the time-varying patterns of each node, we first encode raw traffic data into dynamic representations. Given input X[𝑡-𝑇ℎ+1:𝑡 ] ∈ R 𝑁×𝑇ℎ×𝐶 at time 𝑡, we use 𝐿 stacked spatio-temporal attention blocks, which can be formulated as

where SA denotes a graph attention with the original adjacency matrix [Veliˇckovi´c et al., 2018] and TA denotes a windowed temporal attention [Cirstea et al., 2022]. Each block's output is projected by a fully-connected (FC) layer, then concatenated to form the final dynamic representation Z(𝑡 ) ∈ R 𝑁×𝑑 , synthesizing multi-scale information for robust graph inference

To distill a more purified signal for graph generation from Z(𝑡 ) , we use a memory-enhanced module that projects nodes into a latent space of relational prototypes [Weng et al., 2025b]. Using a learnable meta memory bank M ∈ R 𝑀×𝑑𝑚 , each node's representation z 𝑡 𝑖 queries it via cross-attention, yielding a topology-refined graph-generating embedding g𝑖 :

where m𝑝 is the 𝑝-th memory vector, and W𝑄,W𝐾,W𝑉 are projection matrices. Finally, the dynamic correlation score between node 𝑖 and node 𝑗 at time 𝑡 is computed from their graph generation embeddings:

where W𝜙,W𝜓 are two FC operation. The collection of 𝑠 𝑡 𝑖 𝑗 for all node pairs forms a dynamic correlation graph G 𝑡 𝑝, which reflects the global real-time linkage strength.

Momentum-based Graph Updating and Probabilistic Modeling

The instantaneous graph G 𝑡 𝑝 lacks historical memory, making it noise-sensitive. Inspired by [Ioffe, 2015], We maintain a momentum-updated graph prototype G𝑝𝑟𝑜𝑡𝑜 to ensure smooth and historically grounded evolution, accumulating knowledge from previous graphs:

where 𝛽 ∈ (0, 1) is a momentum coefficient. We train on sequential data partitions, updating the graph prototype per batch and resetting it only after the final partition to simulate continuous learning. During inference, the prototype updates after each prediction, integrating current dependencies with long-term trends for stable, adaptive deployment.

To model the fluctuations of inter-node dependencies, each edge is treated as a random variable. Specifically, the graph prototype G 𝑡 𝑝𝑟𝑜𝑡𝑜 is transformed into a probabilistic one � A 𝑡 via sigmoid:

where � A 𝑡 𝑖 𝑗 ∈ (0, 1) is the probability of an edge from node 𝑖 to 𝑗 . The probabilistic graph � A 𝑡 models temporary structural fluctuations, providing an dynamic topological foundation for node-level invariant learning.

Differentiable Dynamic Sparse Graph Generation

From the fully-connected probabilistic prototype � A (omit the time index 𝑡 for simplicity), we sample a sparse graph instance using Straight-Through Gumbel-Softmax reparameterization [Liu et al., 2022], enabling efficient and robust prediction within gradient-based learning. Firstly, we apply the Gumbel-Softmax function [Jang et al., 2016] to each edge, obtaining a continuous and differentiable relaxation ¯𝐴𝑖 𝑗 of it:

where 𝜋 1 𝑖 𝑗 = � A𝑖 𝑗 , 𝜋 0 𝑖 𝑗 = 1 - � A𝑖 𝑗 , 𝜖 0 𝑖 𝑗 , 𝜖 1 𝑖 𝑗 ∼ Gumbel(0, 1) are i.i.d. Gumbel noise samples, and 𝜏𝑔 is a temperature coefficient. As 𝜏 → 0, ¯𝐴𝑖 𝑗 converges to a one-hot vector where category 1's selection probability equals � A𝑖 𝑗 , effectively sampling from the Bernoulli distribution. Next, the discrete edge ˆ𝐴𝑖 𝑗 is obtained by an argmax operation:

where I[·] is the indicator function. Finally, To allow gradients to flow through this operation, we use the straightthrough estimator to obtain a discrete graph ˆA that remains differentiable for backpropagation:

where detach(·) is the stop-gradient operation. This enables gradient-based optimization of the underlying probabilistic graph parameters � A. During inference, we directly threshold the edge probability, yielding a sparse and binary adjacency matrix A inf for stable and deterministic predictions:

4.2 Node-Heterogeneous Invariant Learning

Adapting to individual node patterns and extracting their topological-invariant knowledge is critical for accurate prediction in OOT scenarios. To accomplish this, we first construct multiple neighborhood environments per node through dynamic probabilistic graph sampling. Next, we learn nodespecific dynamic condition vectors to modulate prediction, customizing unique inference per node while maintaining globally prediction knowledge. Finally, under multi-loss optimization, the model learns stable prediction for OOT generalization.

Node Neighborhood Environment Set Construction

The OOT challenge posed by real-world topological shifts (i.e., random neighborhood compositions) requires modeling edge-level heterogeneity and dynamics. To address this, our dynamic probabilistic graph prototype � A 𝑡 directly learns these properties, rather than relying on global random perturbations. For node 𝑖 at time 𝑡, its neighborhood environment is parameterized by a multivariate Bernoulli distribution as

where 𝑎 𝑡 𝑖 𝑗 ∈ {0, 1} is the directed edge from 𝑖 to 𝑗 at time 𝑡.

Leveraging this time-varying distribution, we generate diverse neighborhood environments per node. For each training batch, we sample the sparse adjacency matrix 𝑝𝑒 times via Straight-Through Gumbel-Softmax, yielding a global environment set E = { ˆA (1) , ..., ˆA ( 𝑝𝑒 ) }. From node 𝑖's perspective, this corresponds to sampling 𝑝𝑒 times from its own distribution 𝑃(N 𝑡 𝑖 ), producing a neighborhood set {N (1) 𝑖 , ...,N (𝑝𝑒) 𝑖 }. Training across these diverse sampled environments simulates heterogeneous topological shifts per node, forcing the model to extract node-level invariant predictive patterns across varying neighborhood contexts.

Node-Specific Modulation for Prediction

Conventional models use a globally shared prediction mapping, learning an average pattern that suppresses nodespecific signals. To address heterogeneous shifts, we design a node-specific modulation mechanism that disentangles and leverages personalized knowledge for robust prediction.

For each node 𝑖, we first derive a dynamic condition vector c 𝑡 𝑖 by fusing its dynamic representation z 𝑡 𝑖 obtained fromSection 4.1 with a learnable time-of-day embedding via a MultiLayer Perceptron (MLP):

where etime(𝑡) is the time-of-day embedding. This vector serves as an adaptive code for node-specific prediction conditioning. Next, a modulated predictor integrates node-specific knowledge with globally shared patterns via Feature-wise Linear Modulation [Perez et al., 2018]. Specifically, a modulation generator MLP transforms the condition vector c 𝑡 𝑖 into

layer-specific affine parameters w (𝑙) 𝑖 , b (𝑙) 𝑖 for each predictor layer 𝑙:

Notably, the predictor shares the same attention block architecture as in Section 4.1, but its intermediate representations I (𝑙) = SA � TA � I (𝑙-1) � , ˆA � are modulated by node-specific affine parameters:

where ⊙ denotes element-wise multiplication. Finally, the modulated outputs from all layers are projected and aggregated to produce the final prediction for node 𝑖:

This design decouples predictor into shared and node-specific components, enabling conditional mapping per node to handle heterogeneous shifts.

Node-Heterogeneous Model Optimization

To refine condition vectors and enhance their discriminative power, we introduce a node-heterogeneity contrastive loss. This enforces semantic similarity for vectors from the same node across time, and distinctiveness for vectors from different nodes. Formally, within a batch, condition vector pairs from the same node at different times are positive samples, whereas pairs from different nodes are negatives. We optimize an InfoNCE-based [Oord et al., 2018] loss:

where L (𝑖) node = log - � 𝑡′ ∈T𝑖 \{𝑡 } exp(sim(c 𝑡 𝑖 ,c 𝑡 ′ 𝑖 )/𝜏) � 𝑁 𝑗=1,𝑡 ′′ ∈T𝑗 I[ 𝑗≠𝑖 or 𝑡′′≠𝑡 ] exp(sim(c 𝑡 𝑖 ,c 𝑡 ′′ 𝑗 )/𝜏) , sim(·, ·)

is cosine similarity, 𝜏 is temperature, and T𝑖 are timestamps for node 𝑖. This loss distills stable node-specific vectors for effective personalized modulation. Furthermore, to ensure robustness against heterogeneous topological shifts, we enforce a node-level invariance constraint with the simulated neighborhood environments E𝑖 = {N (1) 𝑖 , . . . ,N (𝑝𝑒) 𝑖 } [Arjovsky et al., 2019]. Let Φ represent the modulated predictor, the predictive risk for node 𝑖 in a specific sampled environment 𝑒 ∈ E𝑖 is:

where ℓ(·) is a prediction error metric (e.g., MAE). The nodelevel invariant loss aims to penalize variance in predictive risk across environments:

where Var(·) computes risk variance. This loss drives the model to extract stable and invariant predictive patterns from each node's traffic, regardless of fluctuating connectivity.

4.3 Model Training

The training process integrates the previously described components and objectives into a coherent end-to-end learning framework. The primary optimization target is the mean prediction loss, aggregated over all 𝑝𝑒 sampled graph environments as

The overall training objective integrates the prediction loss with the proposed auxiliary losses:

where coefficients 𝛾1, 𝛾2 control the contributions of each loss term. This multi-objective optimization jointly ensures accurate prediction, distinctive node representation, and robustness to topological shifts.

5 Experiments

5.1 Experiment Settings

Datasets

We employ two real-world traffic datasets as benchmarks: the San Diego (SD) and the South Greater Bay Area (SGBA) datasets, to evaluate the robustness of DynaSTar model in dynamic and evolving traffic prediction scenarios. These datasets are subsets of the LargeST dataset [Liu et al., 2023], recording traffic flow data collected at 5-minute intervals by thousands of sensors over a two-year period from 2019 to 2020. The SD dataset comprises 716 sensors, while the SGBA dataset includes 1278 sensors from several adjacent counties in the southern part of the Greater Bay Area (i.e., Alameda, San Francisco, Santa Clara, San Mateo and San Benito). Their static spatial graphs are constructed based on the travel distance between sensors.

Task Settings

Due to the distribution shifts introduced by continuously evolving topology, the characteristics of the shift differ across temporal phases. For prediction models deployed long-term, performance across various phases is crucial, not just during a single specific period. Therefore, we adopt two task settings, near-term and long-term, to comprehensively assess the stability of our model's performance in OOT scenarios at different stages post-deployment. For both the SD and SGBA datasets, we use the 2019 data for model training, splitting it into training and validation sets with a 7:3 ratio. The test set is drawn from the 2020 data of each dataset. Predictions for the first half of the year (January 1st to June 30th) represent the near-term OOT scenario after deployment, while the second half (July 1st to December 31st) is used to test the performance after long-term evolution. Additionally, Z-Score normalization is applied for data preprocessing.

Baselines

We compare the performance of DynaSTar with a series of prediction models, which can be categorized into three distinct groups: i) GNN-based spatio-temporal models: STGCN [Yu et al., 2017], GWNet [Wu et al., 2019], AGCRN [Bai et al., 2020]; ii) Temporal OOD prediction models: AdaRNN [Du et al., 2021], Diversify [Lu et al., 2022], RevIN [Kim et al., 2021]; iii) Spatio-temporal OOD prediction models: CaST [Xia et al., 2023], CauSTG [Zhou et al., 2023], STONE [Wang et al., 2024], STEVE [Ji et al., 2025]. We evaluate the models using the official code released in the respective papers and the model parameters that achieve the best performance on the validation set.

Implementation Details

DynaSTar is implemented using PyTorch. We stack three spatio-temporal attention blocks to extract spatio-temporal representations. Within each block, the hidden dimensions for the temporal and spatial attention modules are 32, and the output FC layer has a dimension of 256. For memoryenhanced graph generation, we employ a 32 × 32 memory bank, with each projection having a dimension of 32. In the node-specific modulated predictor, an MLP with a hidden dimension of 8 generates a 64-dimensional dynamic conditioning vector, and its prediction output is projected by a 512dimensional hidden layer. During training, the sparse graph generation samples 2 graphs with a temperature of 10, the temperature for the node-heterogeneity contrastive loss is 1, and the loss weights 𝛾1 and 𝛾2 are set to 0.01 and 1, respectively. We configure the model to predict the next 12 steps (i.e., 1 hour) based on the previous 12 steps of observations. Model performance is evaluated using the Mean Absolute Error (MAE) and Mean Absolute Percentage Error (MAPE) averaged over forecasting horizons of 3, 6, and 12 steps.

5.2 Evaluations

Multi-Phase Performance across Unseen Time Periods

We evaluate the model's performance across two critical scenarios: the near-term deployment phase and the long-term deployment phase, and report the average results of 5 independent runs of each method in Table 1. We make the following obeservations. (1) Most methods show higher prediction errors in long-term versus near-term scenarios. GNN-based and temporal OOD models degrade significantly over time, indicating OOT distribution shifts are more unpredictable and challenging. (2) GNN-based spatio-temporal models outperform specialized temporal OOD models, demonstrating that effective spatial aggregation is more critical than merely addressing temporal shifts. Although real-time neighbor features can partially mitigate temporal shifts, static or learnable static graphs that ignore potential spurious correlations still underperform in long-term deployment. Notably, AGCRN's high errors suggest severe overfitting of its node-adaptive parameters, hindering OOT generalization. (3) Spatio-temporal OOD prediction models consistently outperform others, highlighting the necessity of addressing distribution shifts. While methods like CauSTG and CaST learn effects of fixed confounders, they overlook the need for modeling of the constantly changed interference factors. STEVE and STONE partially consider confounders or spatial-temporal changes but neglect the continuous evolution of topology, which complicates learning invariant relationships for OOT prediction. (4) By modeling topological dynamics and continuously updating the graph structure, DynaSTar achieves state-of-theart results in both near-term and long-term scenarios. This confirms our dynamic graph structure's effectiveness in perceiving topological evolution, providing consistent, superior adaptability across diverse scenarios without explicit interference modeling. Furthermore, our predictor learns heterogeneous yet invariant node-specific patterns, retaining node uniqueness while avoiding overfitting to spurious correlations, ensuring robust predictions against distribution shifts.

Impact of Components

We conduct an ablation study across two types of variants of DynaSTar: (1) Removing the memory-enhanced module (w/o ME), replacing the momentum-updated graph with an instantaneous graph (w/o MG), and disabling sparse graph generation (w/o SG); (2) Removing node-specific modulation (w/o NM) and removing neighborhood environment construction (w/o NE). As shown in Table 2, all ablated variants exhibit performance degradation. Among (1), w/o MG shows the most significant decline, underscoring the importance of modeling an evolving and stable graph for long-term deployment. Similarly, both (2) reduce accuracy, highlighting the necessity of modeling node-level heterogeneity and learning neighborhood-invariant representations to handle distribution shifts under topological evolution.

• (a) Time vs. num. of samples
• (b) Throughput vs. graph size

Table 2: Ablation results on MAE of 60-minute horizon

Efficiency Study

To evaluate computational efficiency, we compare the execution time and throughput of DynaSTar against the two leading baselines, STEVE and STONE, across varying problem scales. As shown in Fig. 3(a), execution time increases with sample size for all methods, but DynaSTar consistently achieves the lowest runtime. This advantage grows with graph size. Fig. 3(b) illustrates that DynaSTar maintains the highest throughput as the number of nodes increases. In contrast, STEVE and STONE exhibit steeper drops. This efficiency stems from DynaSTar's aggregation on sparse graphs, which avoids the overhead of dense-graph operations and ensures scalable performance under increased complexity.

Generalization Performance on Unseen Graphs

To evaluate generalization to unseen graph structures, we partition sensors in the GBA dataset (excluding SGBA) into two sub-graphs, forming the NWGBA and NEGBA test sets. Models trained exclusively on SGBA are tested on these datasets in a zero-shot setting. As shown in Fig. 4, DynaSTar achieves more accurate predictions than the competitive baselines STONE and STEVE, even on unseen topologies. This robustness stems from its node-heterogeneous invariant learning, which captures specific yet transferable patterns during training. Consequently, DynaSTar can adapt to new graphs with distinct topologies, demonstrating scalable generalization to previously unseen scenarios.

Analysis of Dynamic Graph Structure Learning

DynaSTar can generate meaningful dynamic edges by evaluating real-time dependency scores of nodes and updating them. To verify this, we visualize the 40-day traffic flow sequences of a node pair from the SD dataset alongside a heatmap showing the corresponding fluctuations of the edge probability scores output by our model in Fig. 5. Two key observations emerge. (1) The edge probability score exhibits two significant declines, corresponding to periods of approximately 4 and 9 days, respectively, during which the patterns of the two node's sequences differ significantly from each

• (a) Near-term on NEGBA

Methods

• (c) Near-term on NWGBA
• (b) Long-term on NEGBA
• (d) Long-term on NWGBA

Figure 5: Visualization of the dynamic edge probability generated by our graph structure learning module for a node pair in SD

other. This indicates our model successfully captures changes in the topological relationship across different temporal segments. (2) The green-shaded period's high-frequency noise causes a more significant drop in correlation than the orange period's, highlighting our momentum-based update mechanism's sensitivity to varying topological change intensities.

6 Conclusion

This paper proposes a topological shifts-aware dynamic spatio-temporal graph invariant learning model (DynaSTar), a novel paradigm designed to enhance the robustness and generalization capability of OOT traffic prediction in longterm deployment scenarios. By explicitly capturing evolving graph structures and incorporating node-level invariant learning, DynaSTar achieves superior, stable performance in both near-term and long-term deployment. Future work could extend DynaSTar's principles to other spatio-temporal tasks (e.g., grid-based and irregular point process data modeling), laying a foundation for adaptive urban intelligent systems.

Ethical Statement

There are no ethical issues.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 62272033), Frontier Technologies R&D Program of Jiangsu (Grant No. BF2024052), Nanjing Municipal Science and Technology Bureau (Grant No.202512136).