Graph Structure Learning for Spatial-Temporal Imputation: Adapting to Node and Feature Scales
Xinyu Yang, Yu Sun, Xinyang Chen, Ying Zhang, Xiaojie Yuan · 2024
Read Graph Structure Learning for Spatial-Temporal Imputation: Adapting to Node and Feature Scales by Xinyu Yang, Yu Sun, Xinyang Chen, Ying Zhang, Xiaojie Yuan (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18535.txt.
Introduction
Xinyu Yang, Yu Sun, Xinyang Chen, Ying Zhang, and Xiaojie Yuan fill gaps in sensor data by learning the map between stations as they go, in a 2024 paper. Spatial-temporal data often arrive with missing values. Most filling methods assume one fixed map of relations. That assumption fails when different measures relate differently across space. Air temperature and traffic, say, follow different geographies. The team's framework learns several maps at once.
One learning layer adapts the map per feature across stations. Another finds shared structure among features at each station. A prominence step weights important stations and features more. Cross-feature and cross-time learning capture the remaining patterns. Six real incomplete datasets tested the system. It beat prior methods on the filling task. The authors argue dynamic maps are the key advance. Fixed graphs, they say, belong to a simpler era of sensor networks.
Catalog record
| CREATOR | Xinyu Yang, Yu Sun, Xinyang Chen, Ying Zhang, Xiaojie Yuan |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-18535
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph Structure Learning for Spatial-Temporal Imputation: Adapting to Node and Feature Scales Xinyu Yang, Yu Sun, Xinyang Chen, Ying Zhang, Xiaojie Yuan Abstract Spatial-temporal data collected across different geographic locations often suffer from missing values, posing challenges to data analysis. Existing methods primarily leverage fixed spatial graphs to impute missing values, which implicitly assume that the spatial relationship is roughly the same for all features across different locations. However, they may overlook the different spatial relationships of diverse features recorded by sensors in different locations. To address this, we introduce the multi-scale G raph S tructure L earning framework for spatial-temporal I mputation ( GSLI ) that dynamically adapts to the heterogeneous spatial correlations. Our framework encompasses node-scale graph structure learning to cater to the distinct global spatial correlations of different features, and feature-scale graph structure learning to unveil common spatial correlation across features within all stations. Integrated with prominence modeling, our framework emphasizes nodes and features with greater significance in the imputation process. Furthermore, GSLI incorporates cross-feature and cross-temporal representation learning to capture spatial-temporal dependencies. Evaluated on six real incomplete spatial-temporal datasets, GSLI showcases the improvement in data imputation. Introduction The stations at different geographic locations may occur missing values when recording spatial-temporal data through multiple kinds of sensors ( Zhao et al. 2020b ; Fan et al. 2023 ) . Figure 1 (a) presents an example of spatial-temporal data with four features recorded by seven stations located in the Netherlands. As shown in Figure 1 (b), the readings of feature FH in station AMS at t_{3} and feature DD in station DBT at t_{17} are missing. This may lead to anomalies in the patterns discovered by analysis models, thus creating challenges in mining spatial-temporal data ( Ren et al. 2023 ) . The spatial correlation of spatial-temporal data is usually given as a graph where stations are nodes and edges indicate geographic distance or connectivity between stations ( Li et al. 2018 ; Wu et al. 2019 ; Fan et al. 2023 ) . Existing works typically utilize the given graph and graph neural networks (GNN) to capture spatial dependencies ( Cini, Marisca, and Alippi 2022 ; Liu et al. 2023a ) . Since AMS and DBT stations are geographically closest to each other, their corresponding edge weights in the graph are larger. Therefore, as shown in Figure 1 (b), we can get an accurate imputation result of the feature DD in DBT, according to the DD value in AMS station. Unfortunately, this is not always the case, and we can observe that using the FH value in DBT station will mislead the existing methods for imputing the FH value in AMS station. The reason is that features DD and FH are recorded by sensors from different domains, where DD captures wind direction data and FH is related to wind speed. There is a significant correlation between wind direction information from AMS and DBT stations as they are located close to each other. However, since AMS is situated in an airport with a relatively sparse environment and DBT is located in a municipality with many buildings, the relationship between wind speed values of two stations is not clear. Figure 1 (c) illustrates the spatial relationships of different features across all stations, where we extract the attention map from the cross-feature self-attention mechanism. As shown, the spatial relationships for different features are varied, unlike the implicit assumption by existing methods that spatial relationships across stations are similar for different features. In addition, in Figure 1 (d), we also find that there is a relatively fixed spatial relationship between the features within each station. Specifically, the attention maps between features within the two stations ELD and ELL are generally similar. This suggests that there also exist correlations between different features across all stations. However, this correlation cannot be reflected in the given graph and thus cannot contribute to the imputation of existing methods. Figure 1: (a) Incomplete spatial-temporal data with four features recorded in different stations in the Netherlands. (b) Imputation examples at timestamps \mathit{t}_{3} and \mathit{t}_{17} . (c) The extracted attention maps for features DD and FH. (d) The extracted attention maps for the four features in stations ELD and ELL. Enlightened by the aforesaid analysis, we consider the multi-scale G raph S tructure L earning framework for spatial-temporal I mputation ( GSLI ). Our main contributions can be summarized as follows. (1) We present the node-scale graph structure learning to model the fine-grained global spatial correlations of different features. By adaptively learning independent global graph structures for different features, our framework can mitigate the negative effects between features in different domains and improve imputation performance. (2) We design feature-scale graph structure learning to learn the common spatial correlation of different features over all nodes. Our framework can capture the spatial dependencies between features across each station with the help of the learned feature-scale graph structure. (3) We incorporate prominence modeling into the graph structure learning processes to account for the varying influence of different nodes and different features. Thus, the nodes and features that contribute more to imputation can get stronger weights in the graph structures. Experimental evaluations over real-world incomplete datasets demonstrate the superiority of our GSLI, by utilizing cross-feature representation learning and cross-temporal representation learning. Related Work Spatial-Temporal Imputation Spatial-temporal data, when viewed as multivariate time series by disregarding spatial correlation, often undergoes imputation using time series imputation methods. Time series imputation utilizes various methods, including statistical approaches like mean imputation ( Kantardzic 2011 ) , last observation carried forward ( Amiri and Jensen 2016 ) , and local interpolation ( Acuna and Rodriguez 2004 ) , alongside techniques such as TRMF ( Yu, Rao, and Dhillon 2016 ) , BTMF ( Chen and Sun 2022 ) , and TIDER ( Liu et al. 2023b ) which employ low-rank matrix factorization. RNN-based methods GRU-D ( Che et al. 2018 ) and BRITS ( Cao et al. 2018 ) , along with GAN-integrated methods GAN-2-Stage ( Luo et al. 2018 ) , E 2 GAN ( Luo et al. 2019 ) , SSGAN ( Miao et al. 2021b ) , as well as self-attention and convolutional approaches in STCPA ( Xu et al. 2022 ) , SAITS ( Du, Côté, and Liu 2023 ) , and TimesNet ( Wu et al. 2023 ) emphasize temporal dependencies. Moreover, VAEs in MIWAE ( Mattei and Frellsen 2019 ) , GP-VAE ( Fortuin et al. 2020 ) , TimeCIB ( Choi and Lee 2024 ) , diffusion models in CSDI ( Tashiro et al. 2021 ) , MIDM ( Wang et al. 2023b ) , SSSD ( Alcaraz and Strodthoff 2023 ) , and GPT4TS ( Zhou et al. 2023 ) using large language models are explored. These methods, however, typically ignore the spatial adjacency crucial for spatial-temporal data, indicating potential improvements in the spatial dependency modeling. For spatial-temporal imputation, LRTC-TNN ( Xinyu, Jinming, and Lijun 2020 ) uses low-rank tensor completion, GRIN ( Cini, Marisca, and Alippi 2022 ) pioneers GNNs, and SPIN ( Marisca, Cini, and Alippi 2022 ) targets error accumulation of GRIN for highly sparse data. STD-GAE ( Fan et al. 2023 ) focuses on denoising