STRAP: Spatio-Temporal Pattern Retrieval for Out-of-Distribution Generalization

Thank you for your insightful comments. We address your concerns and answer your questions below.

W1

We greatly value the reviewer’s insightful concerns regarding the generalizability across various spatio-temporal data types and sensitivity in feature selection.

We acknowledge that the performance results of our methodology indeed depend on feature selection. However, existing research demonstrates that different types of spatio-temporal data exhibit common statistical properties and structural patterns in specific dimensions, such as periodicity and local spatial autocorrelation as universal characteristics (Chen et al., NeurIPS 2024; Trirat et al., 2024). These shared structural properties enable spatio-temporal pattern keys adapted to one task to capture cross-domain statistical invariances and structural regularities, thus naturally containing understanding capabilities for other similar spatio-temporal sequence tasks and possessing generalization potential for different spatio-temporal data types.

To better assist future research in feature selection and explore the impact of different features on experimental results, we conducted ablation experiments on features in both spatial and temporal dimensions. Spatial 1, 2 refers to the combination of features from the aspect of local structure and the shortest path statistics feature from global connectivity, while Spatial 3 represents the Forman-Ricci curvature from geometric properties. In terms of time, Temporal 1, 2, and 3 correspond to Statistical and spectral descriptors, Multi-resolution analysis, and Temporal dependencies and complexity, respectively:

Through in-depth analysis of the results, we believe that in feature selection:

1. We should prioritize complementary feature combinations with cross-domain transferability. The Spatial 1,2 demonstrate detailed understanding of community structures through local features (such as node degree and clustering coefficients), while global features (such as shortest path statistics) help reveal the overall graph structure. This local-global complementarity shows strong generalization across different spatio-temporal data types.
2. Feature selection needs to consider signal variation trends and complexity, prioritizing features that can reflect transient changes, periodicity, and temporal dependencies, as these features better capture the essential statistical properties of spatio-temporal data. In future work, we plan to explore more suitable adaptive feature selection methods, incorporating meta-learning frameworks to reduce dependence on manual feature construction.

[1] Chen W, Hao X, Wu Y, et al. Terra: A multimodal spatio-temporal dataset spanning the earth[J]. Advances in Neural Information Processing Systems, 2024, 37: 66329-66356.

[2] Yi Z, Zhou Z, Huang Q, et al. Get rid of isolation: A continuous multi-task spatio-temporal learning framework[J]. Advances in Neural Information Processing Systems, 2024, 37: 136701-136726.

W2

We thank the reviewer for raising this important question about computational efficiency, which is indeed a critical consideration for streaming applications.

As reported in our experimental logs, STRAP does incur moderate computational costs compared to some lightweight methods, which is an inherent characteristic of retrieval-augmented approaches:

This computational overhead stems from three main factors: (1) maintaining the pattern library, (2) performing similarity-based retrieval operations, and (3) integrating retrieved patterns with current observations. However, we find this trade-off justified as it prioritizes prediction accuracy and robustness to distribution shifts over computational efficiency - similar to how retrieval-augmented approaches have transformed other domains by accepting reasonable computational costs for substantially improved performance.

Q1

We sincerely thank the reviewer for pointing out this oversight in our notation. We apologize for the lack of clear definitions for $\mu_{d}$ and $\sigma_{d}$ in the expression which introduces $\mu_{d}$ and $\sigma_{d}$ in Section 4.2.1.

To clarify, $\mu_{d}$ represents the mean node degree in the graph $G_S$, while $\sigma_{d}$ denotes the standard deviation of node degrees. Together with $\max(d)$ and $\min(d)$, these four statistical measures provide a comprehensive description of the degree distribution in the spatial graph, capturing both central tendency and variability characteristics.

We will ensure these definitions are explicitly included in the revised manuscript to improve clarity.

To clarify, $\mu_{d}$ represents the mean value of the degree distribution across all nodes in the graph $G_S$, and $\sigma_{d}$ represents the standard deviation of the degree distribution.

These statistical measures, along with the maximum and minimum degree values, provide a comprehensive characterization of the graph's connectivity patterns, which is essential for accurate pattern matching in our retrieval mechanism.

We commit to adding these explicit definitions in the revised manuscript to ensure clarity. Additionally, we will conduct a thorough review of all notation throughout the paper to ensure all symbols are properly defined before use. Thank you again for helping us improve the precision and readability of our work.

Thank you for your insightful comments. We address your concerns and answer your questions below.

W1

We appreciate the reviewer's comment regarding our spatio-temporal library construction approach. We would like to clarify that our motivation for defining the spatio-temporal library as a product of separate spatial and temporal libraries is both theoretically sound and empirically validated in our work.

From a theoretical perspective, as we discussed in Section 4.2.1, the tensor product (cross-product) operation allows us to capture the complex interactions between spatial and temporal patterns simultaneously rather than treating them as independent factors. This approach enables our model to learn comprehensive representations where temporal dynamics can vary across different spatial regions and spatial relationships can evolve over time - a critical characteristic of traffic forecasting problems.

Furthermore, we conducted extensive ablation studies (Figure 2) that explicitly compare our cross-product approach against alternatives. These ablation studies provide strong empirical evidence supporting our design choice, showing that the multiplicative interaction between spatial and temporal components creates a more expressive representation space that better captures the complex interdependencies in traffic data. This approach also offers computational efficiency advantages, as it allows us to maintain a compact representation of both dimensions while still modeling their joint distribution effectively.

W2

We thank the reviewer for this important observation regarding efficiency analysis. We acknowledge that our framework, being a retrieval-augmented approach, is computationally more intensive than lightweight streaming models: (ENERGY-Stream dataset on ASTGNN)

Our method embraces the inherent trade-off of retrieval-augmented generation (RAG) systems: higher computational cost for significantly improved prediction accuracy. Similar to how RAG approaches have transformed NLP by sacrificing some computational efficiency for dramatically better performance, our work demonstrates that traffic prediction can benefit from the same paradigm.

We believe this represents a worthy trade-off, particularly for critical applications where prediction accuracy significantly impacts downstream decision-making. Many traffic management systems prioritize prediction quality over minimal latency, especially for longer-term forecasting horizons.

To time complexity, STRAP's time complexity can be analyzed across its main components: (1) Spatio-Temporal Subgraph Chunking with complexity $O(|V|\cdot|E|\cdot\tau_S)$ for spatial subgraphs, $O(|V|\cdot k \cdot T)$ for temporal subgraphs, and $O(|V|^3)$ for spectral clustering; (2) Pattern Library Construction with $O(|V|^2)$ for spatial keys, $O(T\log T)$ for temporal keys, and $O(B_{STGNN})$ for pattern value generation; (3) Pattern Retrieval and Fusion requiring $O(|B|\cdot d)$ for similarity computation and $O(|B|\log k)$ for top-k retrieval. The overall time complexity is $\mathbf{O(|V|^3 + |B|\log k + B_{backbone})}$, where $|V|$ is the number of nodes, $|E|$ is the number of edges, $\tau_S$ is the time window length, $T$ is the time sequence length, $|B|$ is the pattern library size, $d$ is the feature dimension, $k$ is the number of retrieved patterns, and $B_{backbone}$ is the backbone complexity.

W3

We appreciate the reviewer's valid concern regarding hyperparameter sensitivity analysis, which is indeed crucial for understanding model robustness and deployment considerations.

We would like to clarify that we conducted extensive hyperparameter sensitivity studies, which are presented in Appendix C.4. Due to space constraints in the main paper, we had to place these detailed analyses in the supplementary materials. This appendix includes comprehensive experiments examining the model's sensitivity to key hyperparameters, including fusion ratio, dropout ratio and retrieval count. Our findings demonstrate that while certain hyperparameters (particularly library size and retrieval depth) do impact performance, the model maintains robust performance across reasonable parameter ranges.

We acknowledge that placing this important analysis in the appendix may make it less accessible during review. In the revised version, we will restructure the paper to incorporate the most critical aspects of this hyperparameter analysis into the main text, particularly highlighting the stability regions for key parameters that are most relevant for practical deployment scenarios.

Thank you for your insightful comments. We address your concerns and answer your questions below.

W1+Q2

We appreciate the reviewer's concern regarding our design choice of maintaining three separate pattern libraries (spatial, temporal, and spatio-temporal) instead of a single unified library. We would like to address this concern by referencing both our theoretical analysis in the appendix and our ablation study results.

As demonstrated in our appendix, the three types of patterns capture fundamentally different aspects of the data distribution. Spatial patterns capture location-specific correlations that remain relatively stable over time but vary across space. Temporal patterns capture time-dependent evolution that is consistent across spatial locations. Spatio-temporal patterns capture complex interactions where spatial correlations evolve differently over time. Our theoretical analysis (Appendix B.1) proves that these three pattern types span different subspaces of the overall distribution space. These subspaces are orthogonal to each other, meaning they capture non-overlapping aspects of the data. A single unified library would require significantly more patterns to approximate the same distribution space, as it would need to independently learn combinations of these fundamentally different pattern types.

In addition, our ablation study results also address the concern about potential redundancy. When we remove any single pattern library (spatial, temporal, or spatio-temporal), we observe significant performance degradation across all metrics. This confirms that each library captures unique and necessary information that the others cannot compensate for. Most importantly, we explicitly compared our approach with a unified library variant that uses the same total number of patterns. This unified approach performed substantially worse despite having the same pattern capacity. This demonstrates that the separation into specialized libraries is not just a design choice but a necessary architectural component for effective pattern learning and utilization.

W2

We thank the reviewer for this valuable feedback regarding the comparison with retrieval-based graph learning methods. We addressed this concern by including comprehensive comparisons with RAGraph[1] and PRODIGY[2], two state-of-the-art retrieval-based graph learning methods mentioned in our introduction.

We extended our experimental evaluation to include RAGraph and PRODIGY across all four backbone architectures (STGNN, ASTGNN, DCRNN, TGCN) on ENERGY-Stream. The updated results demonstrate that while they indeed provide improvements over baseline methods, our STRAP approach consistently outperforms it across all metrics and backbone architectures. (Due to character limitations, we only show the STGNN backbone here. The rest will be shown in the appendix.)

[1] Jiang X, Qiu R, Xu Y, et al. Ragraph: A general retrieval-augmented graph learning framework[J]. Advances in Neural Information Processing Systems, 2024, 37: 29948-29985.

[2] Huang Q, Ren H, Chen P, et al. Prodigy: Enabling in-context learning over graphs[J]. Advances in Neural Information Processing Systems, 2023, 36: 16302-16317.

Q1

In response to your request for hyperparameter details, we provide the complete configuration used in our experiments. For fair comparison, we maintained consistent hyperparameter settings across all methods whenever possible, only adjusting when necessary to achieve optimal performance for each approach. The learning rates and batch sizes for all methods across the three datasets are summarized in the table below. For all backbone architectures, we used the same hyperparameter values within each dataset to ensure fair comparison: (We will add these experimental settings to the appendix later.)

Q3

We sincerely thankful for your thoughtful consideration of the relative importance of the feature extraction components. In our study, we conducted a series of ablation experiments to evaluate the contributions of various features in the spatial and temporal pattern keys to effective retrieval. Below is an overall analysis of the experimental results and a discussion of the key features.

Specifically, Spatial 1 and 2 refer to features from the aspect of local structure and the shortest path statistics feature from global connectivity, while Spatial 3 represents the Forman-Ricci curvature from geometric properties. In terms of time, Temporal 1, 2, and 3 correspond to Statistical and spectral descriptors, Multi-resolution analysis, and Temporal dependencies and complexity, respectively.

The experimental results with the TGCN backbone demonstrate that Spatial pattern 1 and Spatial pattern 2 each contribute to the effect of local structure and global connectivity features, significantly enhancing the model's understanding of dynamic graph changes, while the multi-resolution analysis feature (Temporal pattern 2) performs best with a MAPE of 44.98±2.32%, its sensitivity to short-term trends effectively capturing signal transients and complexity, thus better adapting to dynamic spatio-temporal environments.

Inspired by your comments, we also plan to integrate more spatial and temporal features in future work to explore their interactions and gain a more comprehensive understanding of the complexities in spatio-temporal data.

Q4

Thank you for highlighting the connection between our work and the broader retrieval-augmented learning paradigm. STRAP builds upon this emerging direction while introducing several key innovations specifically designed for spatio-temporal graph data under distribution shifts.

STRAP's superior performance stems from several important distinctions:

1. While previous methods typically maintain a single pattern repository, STRAP's separate spatial, temporal, and spatio-temporal libraries enable more precise matching along different dimensions of variation. This is crucial for streaming data where distribution shifts can occur independently in different dimensions.
2. STRAP employs domain-specific topological and temporal feature extractors designed to capture the unique characteristics of spatio-temporal graphs. In contrast, general retrieval-based methods often rely on generic graph embeddings that may not adequately capture complex spatial-temporal dependencies.
3. Our framework incorporates a learnable fusion weight that dynamically balances the contribution of retrieved patterns and current observations. This adaptability is particularly valuable in streaming settings where the relevance of historical patterns can vary substantially.
4. As shown in our theoretical analysis (Theorem B.1), our decomposed approach provides higher mutual information with the underlying data distribution compared to unified representation approaches used in previous methods.

In addition, we supplemented the RAGraph experiment, as detailed in W2.

Q5

We appreciate this important question about STRAP's performance in few-shot adaptation scenarios. To address this, we conducted additional experiments using the ENERGY dataset as a representative benchmark, as it exhibits complex spatio-temporal dependencies and significant distribution shifts.

We tested STRAP against several strong baselines under data-limited conditions, specifically when only 70% (30% missing) and 50% (50% missing) of the target distribution data is available for adaptation. The results, summarized in the table below, demonstrate STRAP's superior robustness in few-shot scenarios: (Due to character limitations, only the 30% missing scenario is presented here, with the 50% missing scenario supplemented later in the appendix.)

Thank you for your insightful comments. We address your concerns and answer your questions below.

W1+Q1+W2

We appreciate the reviewer's concerns about the distinction between Continual Learning (CL) and Out-of-Distribution (OOD) generalization in our work. We would like to clarify the scope of our work as follows.

Continual Learning (CL) refers to the ability of a model to learn from a continuous stream of data over time, adapting to new patterns while retaining knowledge from previous experiences. In traditional CL paradigms, models are often retrained at fixed intervals to incorporate new information. Out-of-Distribution (OOD) Generalization concerns a model's ability to perform well on test data whose distribution differs from the distribution of the training data.

Our work addresses a more nuanced challenge at the intersection of the above two domains. While we operate within a CL framework where models learn from streaming data across different time periods, our focus is on the distribution shifts that occur within each time period between training and testing sets. Specifically, for each time period, we divide the data into training set and testing set. The distributions of the training data and the testing data are different, which is actually the classical OOD setting.

As demonstrated in our revised Figure 3, there are substantial distribution shifts between training and testing data within each individual period. Rather than simply preventing catastrophic forgetting (the typical goal of CL) or broadly generalizing to unseen distributions (the typical goal of OOD methods), STRAP learns and leverages specific patterns from historical data that provide the most informative signal for current predictions under shifted distribution.

Q2+W3

We appreciate the reviewer's question regarding computational efficiency.

As reported in our experimental logs, STRAP's computational efficiency (seconds/epoch) is slightly lower than some lightweight methods but significantly higher than other more computationally intensive baselines. Specifically, using ASTGNN as the backbone with ENERGY-Stream, our approach requires moderately higher computational resources than some lightweight methods but significantly less than the most computationally intensive baselines.

Our retrieval-augmented framework inherently requires additional computational resources due to the pattern library maintenance and retrieval operations. In future work, we plan to explore efficiency improvements through techniques such as optimized pattern library indexing and adaptive retrieval mechanisms.

Q4+W4+Q5

We appreciate the reviewer's feedback regarding the evidence of distribution shifts between training and testing data.

In response to this concern, we revised Figure 3 to include both training and testing data distributions across all time periods (we will revise and add this figure to the final version). The updated figure demonstrates significant distribution shifts not only among different time periods but also between training and testing data in the same time period.

W5

We appreciate the reviewer's thoughtful comments regarding evaluation metrics for catastrophic forgetting. This is an insightful observation that deserves clarification.

We acknowledge that our approach does not address catastrophic forgetting in the traditional sense, as we are not concerned with performance on past data but rather focus exclusively on future prediction performance in our application scenarios. The primary objective of our work is accurate spatio-temporal prediction under distribution shifts, where historical pattern retrieval serves an auxiliary role in enhancing prediction robustness. Similarly, previous research focusing on catastrophic forgetting primarily examines whether preserved historical information effectively contributes to future predictions under distribution shifts [1][2]. The ultimate measure of whether a model has "forgotten" useful patterns is reflected directly in its prediction accuracy on current data that resembles historical distributions. When our model encounters patterns similar to those seen historically, it maintains strong performance because our model's architecture naturally stores and leverages useful historical data without explicit forgetting prevention mechanisms.

The standard evaluation metrics (MAE, RMSE, MAPE) in our experiments indirectly but comprehensively capture forgetting effects. When the model encounters a traffic pattern similar to one it has seen before, poor performance would indicate catastrophic forgetting of that pattern.

[1] Chen W, Liang Y. Expand and compress: Exploring tuning principles for continual spatio-temporal graph forecasting. arXiv preprint arXiv:2410.12593, 2024.

[2] Wang B, et al. Stone: A spatio-temporal ood learning framework kills both spatial and temporal shifts. ACM SIGKDD. 2024: 2948-2959.

W6

We appreciate the reviewer's suggestion to update our discussion on replay-based methods and strengthen our comparison with retrieval-based approaches.

We would like to clarify that experience replay is a general strategy commonly employed as a component within many continual learning models. For instance, both STKEC and TrafficStream incorporate replay mechanisms, but these are presented as standard components rather than their novel contributions. Their primary innovations lie elsewhere—in knowledge extraction techniques and streaming architectures, respectively. Thus, we did not categorize them as replay-based methods.

Regarding retrieval-based methods, we strengthened our comparative analysis by including additional experimental results for RAGraph [1] and PRODIGY [2] on the ENERGY-Stream dataset (STGNN backbone). While RAGraph and PRODIGY perform reasonably well on this dataset, our STRAP method still achieves superior performance across all prediction horizons. These results further validate our approach's effectiveness compared to state-of-the-art retrieval-based methods. (Due to character limitations, we only show the STGNN backbone here. The rest will be shown in the appendix.)

[1] Jiang X et al. Ragraph: A general retrieval-augmented graph learning framework. NIPS 2024, 37: 29948-29985.

[2] Huang Q et al. Prodigy: Enabling in-context learning over graphs. NIPS 2023, 36: 16302-16317.

W7

We appreciate the reviewer's concern regarding the clarity of our task definition. Our manuscript addresses a specific spatiotemporal prediction problem:

In Section 3.1 of our manuscript, we provided a comprehensive definition of our task. Specifically, we formulated the problem as predicting future values at multiple locations at time t+h given historical observations from time steps t-n to t, while explicitly addressing the challenge that testing data distributions differ substantially from those encountered during training.

To further clarify, our work focused on streaming data scenarios, as detailed in Appendix C.3, where data arrived continuously over time in sequential periods. This streaming nature introduced unique challenges, as the model had to adapt to evolving patterns and distribution shifts without complete knowledge of future data characteristics.

Our training approach reflected this streaming paradigm: rather than batch training on the entire dataset, the model updated sequentially as new data became available in each period. Specifically, at each time step, the model trained on the most recent available data while leveraging its pattern library to maintain robustness to distribution shifts between training and testing sets within each period.

Thank you for pointing out the typos. We carefully corrected the typos throughout the manuscript to ensure clarity and consistency in our presentation.

Q6

We appreciate the reviewer's suggestion regarding the clarification of prediction horizons in Table 1. We agree that this detail is important for readers who may be unfamiliar with the field.

In our revised manuscript, we modified Table 1 to properly clarify the prediction horizons by:

Adding a clear column header that reads "Prediction Horizon" followed by the specific time units for each dataset (Table 6):

• For PEMS-Stream: "(15 min, 30 min, 60 min)"
• For Air-Stream: "(3 hours, 6 hours, 12 hours)"
• For Energy-Stream: "(30 min, 1 hour, 2 hours)"

We sincerely appreciate the time and effort you have dedicated to reviewing our work. In response to your valuable feedback, we have provided detailed explanations for the issues raised.

As the discussion period progresses, we are eager to hear your thoughts on our responses, including whether they have adequately addressed your concerns. If our revisions and discussions indicate the potential for a score adjustment, we would be very grateful for your consideration.

We are committed to incorporating all of your suggestions to further enhance the quality of our manuscript. We look forward to your further comments and discussion.

Thanks for the response. We would like to provide more clarification to address your concerns as follows.

Paragraph 1: Regarding the efficiency test

Regarding computational efficiency, we would like to clarify several important points:

First, the pattern library construction is primarily a one-time upfront cost during the initial period. As shown in Table 2, after the initial period (Period 0), STRAP's computational requirements actually decrease and stabilize (from 2.27 to 1.83-2.10). This indicates that once the pattern library is constructed, it can be continuously leveraged with minimal additional overhead.

Second, in real-world traffic prediction applications, predictions are typically updated at fixed intervals (e.g., every 5-15 minutes). Our method's additional computational cost of 1-1.5 seconds is negligible within these operational timeframes. Taking PEMS-Stream as an example, where predictions are generated every 5 minutes (300 seconds), our method's additional processing time represents less than 1% of the available time window between predictions. This practical context demonstrates that the modest computational overhead has minimal impact on real-time deployment while delivering substantial accuracy improvements, making the efficiency-accuracy tradeoff highly favorable in operational settings.

Third, we would emphasize that STRAP is designed specifically for STOOD scenarios where distribution shifts create significant challenges for conventional models. In such critical scenarios, the substantial performance improvements (19-24% error reduction) far outweigh the moderate increase in computational cost, particularly since this cost remains well within practical constraints for real-time applications.

Paragraph 2: evaluation metrics

We disagree with the reviewer's assessment regarding the evaluation of catastrophic forgetting. Our evaluation approach is both methodologically sound and consistent with established practices in the field.

First, our work directly addresses catastrophic forgetting through a retrieval-augmented approach, which has been widely recognized as an effective strategy for mitigating forgetting in continual learning settings. The significant improvements we observe in standard evaluation metrics (MAE, RMSE, MAPE) across all test periods - particularly during distribution shifts - provide clear evidence that our method successfully preserves knowledge of previously encountered patterns while adapting to new ones.

This retrieval-augmented approach to mitigate catastrophic forgetting has strong theoretical foundations and empirical support in recent literature:

1. Long Y, Chen K, Jin L, et al. DRAE: Dynamic Retrieval-Augmented Expert Networks for Lifelong Learning and Task Adaptation in Robotics. ACL 2025

2. Gutiérrez B J, Shu Y, Qi W, et al. From rag to memory: Non-parametric continual learning for large language models. ICML 2025

Second, we have already noted in our previous response that standard evaluation metrics (MAE, RMSE, MAPE) are consistently used to evaluate catastrophic forgetting in spatiotemporal prediction literature. This is not an isolated case but the established methodology in the field. Models that suffer from catastrophic forgetting show degraded performance on these metrics when distribution shifts occur, while models that successfully mitigate forgetting maintain stable performance across time periods.

Thanks again. We are more than willing to discuss more with you.