CAN-ST: Clustering Adaptive Normalization for Spatio-temporal OOD Learning

1 Introduction

The rise of sensor networks has led to the widespread collection of spatio-temporal time series in urban environments. As these datasets expand rapidly, accurate spatio-temporal time series forecasting becomes increasingly crucial for various real-world applications, including transportation [Jiang et al., 2021; Jin et al., 2023], weather [Angryk et al., 2020; Gong et al., 2024], and economics [Lai et al., 2018; Dong et al., 2024]. Given the significance and urgency of urban spatio-temporal prediction, recent advancements in deep learning techniques [Li et al., 2024; Qu et al., 2022; An et al., 2024; Deng et al., 2024a; Deng et al., 2022; Deng et al., 2024b] have accelerated research in this domain.

∗Corresponding author.

However, accurately predicting spatio-temporal patterns remains a challenge due to the rapid evolution of distributions over time, which results in spatio-temporal out-ofdistribution (OOD) scenarios [Liu et al., 2024]. One such example is illustrated in Figure 1, showing the dynamic evolution of urban areas. Several months ago during T1, subway construction disrupted the road between N2 and N4, altering spatial dependencies by weakening the N2-N4 correlation and strengthening the N2-N1 correlation. These changes reverted after the project was completed during T2. Additionally, the relocation of the entertainment mall at N3 to N5, expansion of the N2-N4 road for the subway station, and construction of a new residential building at N3 led to further shifts in spatial relations.

These changes altered the spatio-temporal joint distribution, rendering previous deep learning models ineffective. A decade ago, research showed that machine learning systems could fail significantly when evaluated on data outside the domain of their training examples, mainly due to their dependence on the training distribution [Dai and Van Gool, 2018; Wang et al., 2024b]. To alleviate the impact of distribution shifts, normalization methods have been proposed as a viable solution [Passalis et al., 2019; Liu et al., 2024]. These methods aim to remove non-stationary factors, infer output statistics from input statistics, and estimate the output distribution via de-normalization. However, these methods learn statistics evolution patterns for each location time series independently, overlooking potential shared patterns across spatial dimensions. As a result, when correlations between spatial nodes change, suboptimal solutions can arise.

For instance, in urban traffic flow prediction, changes at specific spatio-temporal nodes can lead to significant shifts in distribution patterns. As shown in Figure 1, the demolition of the entertainment mall at N3 and its replacement with a residential area during T1 caused a dramatic shift in observed patterns. Previous methods, which focused solely on individual locations, experienced notable performance degradation at this node during T2. In fact, the behavior at N3 during T2 could be inferred from data at other nodes, such as N2 and N4 during T1, as these locations exhibit similar trends to residential areas. In practice, this provided valuable insights, revealing shared patterns critical for understanding dynamics in spatio-temporal OOD learning.

This observation suggests the use of clustering to extract representative spatio-temporal patterns. When distribution shifts occur at a specific spatio-temporal node, these clusterlevel patterns can be leveraged to infer the new distribution, mitigating the impact of such changes. Motivated by this, we propose Clustering Adaptive Normalization (CAN-ST), a model-agnostic framework for spatio-temporal OOD learning. CAN-ST operates in three steps: (1) it normalizes input data using statistics to remove non-stationary factors, ensuring more reliable predictions; (2) it applies adaptive clustering to group spatio-temporal nodes with similar patterns, facilitating the extraction of representative spatio-temporal semantics and reducing reliance on individual historical time series; (3) it uses a parameter register to capture distributional evolution patterns specific to each cluster, enabling flexible and accurate de-normalization and distribution transformations, even under severe spatio-temporal OOD conditions.

Unlike existing methods that focus on individual nodes or time series, CAN-ST captures both localized distributional changes at each node and shared distributional evolution patterns among nodes within the same cluster. By integrating these features, CAN-ST ensures robust normalization and denormalization in spatio-temporal OOD scenarios. Extensive experiments conducted on widely used datasets demonstrate that CAN-ST significantly improves the performance of various mainstream prediction models, consistently outperforming state-of-the-art normalization approaches. In summary, our work makes the following key contributions:

• We introduce CAN-ST, a general normalization framework specifically designed for spatio-temporal OOD learning tasks. As a plugin, CAN-ST can be easily integrated into various spatio-temporal prediction models.
• We propose an adaptive spatio-temporal clustering
• method to capture shared distributional evolution patterns, along with a parameter register that ensures stable and flexible distribution transformations, even under spatio-temporal distribution shifts.
• We validate CAN-ST through extensive experiments on four real-world datasets. The results demonstrate that it consistently enhances predictive performance across mainstream models and surpasses state-of-the-art normalization methods, showcasing its effectiveness in tackling spatio-temporal OOD challenges.

2 RelatedWork

2.1 Spatio-temporal Out-of-Distribution Learning

Previous studies in spatio-temporal data mining have extensively explored out-of-distribution (OOD) challenges [Wang et al., 2024a; Du et al., 2021; Yao et al., 2022; Deng et al., 2023], laying the groundwork for understanding distributional shifts in real-world applications. Recent focus has shifted to OOD issues in spatio-temporal urban prediction, where urbanization and evolving mobility patterns introduce significant temporal and spatial discrepancies. Infrastructure changes, seasonal variations, and unforeseen events further exacerbate non-stationarity in urban data. Recent works [Xia et al., 2024; Zhou et al., 2023], address OOD scenarios using causal inference within spatio-temporal frameworks. Xia [2024] proposed a hybrid approach combining disentanglement blocks for backdoor adjustment and frontdoor adjustment with edge-level convolution. Zhou [2023] reformulated invariant learning to identify stable parameters robust under varying distributions. These methods highlight the potential of causal inference to mitigate OOD effects.

However, causality-based methods often require complex training, significant computational resources, and expertise, limiting scalability and real-time use. CAN-ST offers a practical and model-agnostic alternative. By tackling OOD challenges through a lightweight framework, CAN-ST balances computational efficiency with predictive accuracy, making it ideal for dynamic, non-stationary environments.

2.2 NormalizationMethods for Non-stationary Time Series Forecasting

Approaches to normalization have been devised to address the challenges posed by non-stationarity. To account for instance-specific variations, [Ogasawara et al., 2010] propose leveraging normalization techniques that rely on local characteristics rather than global statistics. Passalis [2019] advance this instance-wise normalization framework by introducing an adaptive and learnable approach. While these methods effectively eliminate non-stationary elements from inputs, predicting non-stationary time series in the outputs remains a significant challenge.

To address this, reversible instance normalization [Kim et al., 2021] was introduced, allowing the removed nonstationary components to be reintroduced for output reconstruction. However, it presumes consistent trends between inputs and outputs. Kim [2021] further refine this idea through RevIN, focusing on evolving trends within input sequences.

Recent studies [Fan et al., 2023; Ogasawara et al., 2010] delve into trend modeling at finer granularities, such as at the segment level. Additionally, Ye [2024] and Dai [2024] extended normalization using Fourier Transform to capture frequency-domain information.

These works focus on independent time series, ignoring spatio-temporal dependencies. In contrast, CAN-ST employs adaptive clustering to capture shared patterns and a parameter register to dynamically model local and global relationships.

3 ProblemDefinition

Let G = (V,E,A) represent a spatial network, where V and E denote the sets of vertices and edges, respectively. The adjacency matrix of G is denoted as A. Furthermore, we define the graph signal matrix xt ∈ RN×D for G, where D represents the feature dimension, N = |V | is the number of vertices, and xt represents the observations of G at time step t. Overall, the goal of spatio-temporal tasks is to learn a multistep prediction function f based on historical observations:

where T is the input length of past time step observations, and τ is the number of future steps we aim to predict.

Unlike traditional spatio-temporal learning tasks, spatiotemporal OOD learning allows the graph relationships to differ between training and testing phases and to evolve over time during training. Specifically, following the setup of previous works, we assume that the graph GTest , representing spatial relationships, and the spatio-temporal distribution pTest (X) in the test set differ from those in the training set, such that:

4 Methodology

We propose a general, model-agnostic normalization framework for spatio-temporal OOD learning, termed Clustering Adaptive Normalization (CAN-ST), to address the aforementioned spatio-temporal distribution shift challenges. In this section, we provide a detailed explanation of the framework of CAN-ST and illustrate how it handles data affected by spatio-temporal distribution shifts. The whole framework CAN-ST be referred to in Figure 2.

4.1 Normalization

Given a spatio-temporal input denoted as Xi ∈ RT×N×D, which represents { xt-T , . . . , xt-1 }, CAN-ST normalizes the input to remove the non-stationary factors. Specifically, we normalize the input data Xi using its instance-specific mean and standard deviation, which is widely accepted as instance normalization [Kim et al., 2021]. The mean and standard deviation are computed for every spatio-temporal instance:

where ϵ is a small positive constant, typically set to 1×10-5 . Finally, the transformed ¯ Xi , with non-stationary factors removed, is used as the new input for the prediction model.

4.2 Adaptive Spatio-temporal Clustering

Unlike existing methods, which normalize and de-normalize only the time series of individual spatial nodes, CAN-ST addresses a natural challenge: how to estimate future evolution distributions without solely relying on historical time series in the presence of spatio-temporal distribution shifts?

In scenarios where such shifts occur, using the mean and variance of a single historical time series for de-normalization can lead to significant performance degradation, as the output statistics deviate from µi and σi. Additionally, for nodes introducing new spatio-temporal relationships (such as N3 at future temporal node in Figure 1), sharp changes in the spatiotemporal distribution create an urgent need for interactions with nodes that exhibit similar trends. To address these issues, it is essential to extract shared knowledge from similar spatio-temporal nodes as a reserve. During distribution shifts, the model can bypass sole reliance on the historical data of individual nodes for de-normalization by leveraging shared knowledge from all nodes. This shared knowledge is used to infer the required statistical properties for de-normalization, enabling a more robust transformation.

Motivated by this, CAN-ST clusters all spatio-temporal nodes to identify representative spatio-temporal patterns within the dataset. First, CAN-ST performs adaptive spatiotemporal clustering based on the input data. Unlike tasks in NLP and CV, where features generally correspond to similar types of information, each feature in urban spatio-temporal computing often conveys distinct meanings, such as vehicle speed and traffic volume. Therefore, we model each feature separately, as outlined below:

where W ∈ RD×TN×C is the clustering matrix. ˜ Xi ∈ RD×TN is the reshaping of Xi . C is the predefined number of spatio-temporal clusters. Each row of S[d, :] represents the probability of the spatio-temporal sample belonging to each cluster for feature d.

4.3 Statistics Residual Affine &Denormalization

Then, we performs match-based de-normalization according to the clustering results. To achieve more accurate denormalization, CAN-ST learns to infer the statistics of output.

To leverage the patterns of typical spatio-temporal clusters and eliminate reliance on the historical sequences of individual nodes, CAN-ST is equipped with transformation parameter registers. These registers store the statistics transformation patterns from input's distribution space to output's of each cluster. For given spatio-temporal nodes, the register is matched based on there clustering scores, producing affine coefficients that integrate global spatio-temporal dependencies. We assigns separate transformation parameter registers for the mean and variance, which are learned end-to-end alongside the prediction model. These registers are randomly initialized as Rµ ∈ RD×C×C′ and Rσ ∈ RD×C×C′ . Next, we match the spatio-temporal nodes with the parameter registers based on the clustering results to obtain transformation coefficients:

where W1 ∈ RC′×1 and W2 ∈ RC′×1 are learnable pooling weights used to reduce the dimension from C ′ to 1. Then Wµ ∈ RD×1 and Wσ ∈ RD×1 are used to infer the statistics of the output. We incorporate the residual learning technique [He et al., 2016] into our method, enabling the module to learn the difference between the statistics of the future output and the input, rather than directly predicting the exact value. This approach reduces the difficulty of mean modeling by leveraging prior knowledge of future trends:

where ⊙ denotes element-wise multiplication. While predicting the statistics, CAN-ST feeds the normalized spatiotemporal data into the prediction model f(∗), which generates the internal output ¯ Y . Finally, CAN-ST applies denormalization to the output from the prediction model f(∗), inferring the distribution of output to produce accurate predictions:

5 Experiment

In this section, we conduct sufficient experiments within a widely used benchmark dataset compared to state-of-the-art methods to evidence the effectiveness of our proposed CANST framework.

5.1 Experimental Setup

All experiments followed strict fairness protocols in a benchmark [Wang et al., 2024b].

Datasets: We conduct our experiments on four real-world datasets: BikeCHI 1 , TaxiCHI 2 , PEMS08 3 and SpeedNYC 4 . The details about these datasets are listed in the Table 1. We adhere to the in-distribution and out-of-distribution testing protocols outlined in to rigorously evaluate model performance. Specifically, models are trained on data from year A and subsequently evaluated on datasets from both year A (in-distribution) and year A + 1 (out-of-distribution), which has been proven to be reasonable [Wang et al., 2024b]. It should be noted that using data from year A for testing corresponds to the conventional experimental setup in spatiotemporal learning. We adopted the data partitioning strategy established in prior work [Jiang et al., 2021], which chronologically divides the data into training, validation, and testing subsets with a 6:2:2 ratio [Wang et al., 2024b].

1 https://www.divvybikes.com/system-Data

2 https://data.cityofchicago.org/

3 https://pems.dot.ca.gov/

4 https://www.nyc.gov/html/dot/html/motorist/atis.shtml

Backbone models: CAN-ST is a model-agnostic framework applicable to any spatio-temporal forecasting model f(∗). To demonstrate the effectiveness of the framework, we select several mainstream models based on different architectures and evaluate their performance under both in-distribution and out-of-distribution conditions: the dilated convolution and graph convolution based Graph WaveNet [Wu et al., 2019], the Transformer-based STAEformer [Liu et al., 2023], the recurrent neural network and graph convolution based AGCRN [Bai et al., 2020], and the temporal convolution and graph convolution based STGCN [Yu et al., 2017]. We follow the implementation and settings provided in the official code of the spatio-temporal OOD learning benchmark [Wang et al., 2024b].

Experiments details: We use ADAM [Kingma, 2014] as the default optimizer across all the experiments and report the root mean squared error (RMSE) and mean absolute error (MAE) as the evaluation metrics.

5.2 Main Results

We present the spatio-temporal prediction results in Table 2 and Table 3. For the TaxiCHI and BikeCHI datasets, the prediction horizons are set to {1 hour, 3 hours}, while for other datasets, the horizons are {5 minutes, 15 minutes}. Regarding the input sequence length, we follow standard protocols, fixing the input window length to 12 hours for the TaxiCHI and BikeCHI datasets and 1 hour for the remaining datasets. From these results, we derive several key observations as follows:

1. CAN-ST consistently delivers substantial performance gains across multiple datasets and testing scenarios. Both RMSE and MAE metrics show that models equipped with CAN-ST outperform their baseline counterparts in most cases. This demonstrates the adaptability of CAN-ST in varying testing environments, including both In-Distribution (IN) and Out-of-Distribution (OUT) settings.
2. CAN-ST effectively enhances both Transformer-based models (e.g., STAEformer) and GCN-based models (e.g., STGCN, GWNET, and AGCRN). Specifically, CAN-ST achieves an average relative performance improvement of 22.32%, 22.24%, 19.33%, and 24.24% over STAEformer, STGCN, GWNET, and AGCRN, respectively.
3. Under out-of-distribution testing, CAN-augmented models show substantial improvements. For instance, integrating CAN-ST reduces STAEformer's RMSE on TaxiCHI by 46.5% (1-hour: 63.08→31.50; 3-hour: 83.38→44.63). Consistent gains across other models highlight CAN's efficacy in adapting to distribution shifts.
4. The observed performance gains are consistent across different baseline architectures, including STAEformer, STGCN, GWNET, and AGCRN. This underlines the generalizability and compatibility of CAN-ST as a plug-in module for spatio-temporal prediction tasks.

5.3 Comparison with Advanced Normalization Methods

In this section, we compare CAN-ST with state-of-the-art normalization methods, including SAN [Liu et al., 2024]

and Dish-TS [Fan et al., 2023] for non-stationary time series forecasting, ST-Norm [Deng et al., 2021] for non-stationary spatio-temporal forecasting, and Z-score normalization. For the TaxiCHI and BikeCHI datasets, the prediction horizons are set to {1 hour, 2 hours, . . . , 12 hours}. Regarding the input sequence length, we follow the same experimental settings outlined in Section 5.2. We report the average results across all prediction horizons for STAEformer, STGCN, GWNET, and AGCRN, as well as the relative improvements in Table 4, revealing CAN-ST demonstrates superior performance compared to existing normalization methods across all evaluated scenarios and models. The experimental results validate the effectiveness of CAN-ST and highlight its key design advantages, which can be attributed to following primary factors:

(1) Unlike traditional normalization methods, such as ZScore, which apply static transformations based on fixed statistical metrics calculated from the entire dataset, CAN-ST introduces a dynamic mechanism that adapts to evolving distributional patterns. This adaptability ensures that the normalization process remains aligned with the underlying data distribution, effectively mitigating the impact of distribution shifts and enhancing the robustness and accuracy of downstream predictive models.

(2) Compared to SAN and DishST, which focus on single time series for the specific spatial node, CAN-ST provides a more comprehensive solution by simultaneously addressing localized and shared distributional changes through cluster spatio-temporal nodes. This holistic approach makes it more robust in diverse scenarios.

(3) STNorm's dependence on global statistics limits its effectiveness under spatio-temporal distribution shifts (e.g., emerging nodes or dynamic node behaviors). In contrast, CAN-ST dynamically clusters similar nodes and adapts transformation parameters, maintaining robust performance despite severe shifts.

5.4 Investigation of Clustering Approaches

In this section, we investigate the impact of different clustering methods on experimental results. We examined three approaches ann presented the results in Figure 3.

• Naive: Do not utilize clustering approaches.
• CAN-ST: Our method clusters both temporal and spatial nodes of the input space simultaneously.
• ST-parallel: This approach clusters temporal and spatial nodes separately in parallel, matches them with the parameter register, and then fuses the results to obtain the affine coefficients.
• ST-sequential: This method clusters using the entire temporal sequence of spatial nodes, directly matching them with the parameter register to derive the affine coefficients.

CAN-ST consistently achieves the lowest RMSE and MAE by effectively modeling spatio-temporal patterns, outperforming other methods in both stable and shifting data distributions. While ST-sequential shows moderate robustness, and ST-parallel offers limited flexibility, both occasionally underperform baseline methods. In contrast, CAN-ST maintains robust superiority, demonstrating that simple parallel or sequential feature processing fails to capture complex spatiotemporal dynamics effectively.

5.5 Hyperparameters Analysis

CAN-ST clusters spatio-temporal nodes into C classes based on their spatio-temporal distributions, where C is the size of Wc in Section 4.2. We analyze the influence of different C values on prediction accuracy in Figure 4. When C = 16, the model consistently achieves optimal performance. Although the RMSE under the Out-of-Distribution testing setting is minimized when C = 20, other metrics are not consistently optimal in this configuration. Consequently, it is evident that performance significantly outperforms other variants in most cases when using the most appropriate C, highlighting the effectiveness of clustering.

5.6 Discussion of Complexity and Runtime

We analyze the computational overhead of CAN-ST through theoretical complexity analysis and empirical runtime measurements. The framework introduces three main lightweight components: Normalization: Instance-wise statistics calculation (Eqs. 1-3) requires O(TND) operations; Adaptive Clustering: Feature-specific clustering (Eq. 6) has O(DTNC) complexity, where C (default 16) denotes cluster count. This scales linearly with T, N, and D; Parameter Register: Transformation coefficient derivation (Eqs. 7-8) involves O(DCC ′ ) operations. On TaxiCHI (N = 77, T = 12), CAN-ST adds only 0.59s/epoch to STAEformer's training time (16.24s vs. 16.83s), demonstrating efficient computation while improving OOD performance. Similar observations were made on other datasets and backbone models.

6 Conclusion

In this study, we propose CAN-ST, a model-agnostic framework for spatio-temporal OOD learning. Its threestep approach-normalization, adaptive clustering, and cluster-aware denormalization-effectively handles distribution shifts by jointly modeling local variations and global patterns. Experiments validate CAN-ST's superior performance over SOTA methods across diverse models and datasets.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (62476154, 62202270), and Major Basic Research Project of Shandong Provincial Natural Science Foundation (ZR2024ZD03) and the Shandong Excellent Young Scientists Fund (Oversea) (2022HWYQ044), and the Taishan Scholar Project of Shandong Province (tsqn202306066), and Shandong University Qilu Young Scholars Program.