More Web Proxy on the site http://driver.im/

research-article

LSTGCN: Inductive Spatial Temporal Imputation Using Long Short-Term Dependencies

Authors:

Jiangtao CuiAuthors Info & Claims

ACM Transactions on Knowledge Discovery from Data, Volume 18, Issue 9

Article No.: 235, Pages 1 - 25

https://doi.org/10.1145/3690645

Published: 08 November 2024 Publication History

Abstract

Spatial temporal forecasting of urban sensors is essentially important for many urban systems, such as intelligent transportation and smart cities. However, due to the problem of hardware failure or network failure, there are some missing values or missing monitoring sensors that need to be interpolated. Recent research on deep learning has made substantial progress on imputation problem, especially temporal aspect (i.e., time series imputation), while little attention has been paid to spatial aspect (both dynamic and static) and long-term temporal dependencies. In this article, we proposed a spatial temporal imputation model, named Long Short-Term Graph Convolution Networks (LSTGCN), which includes gated temporal extraction (GTE) module, multi-head attention-based temporal capture (MHAT) module, long-term periodic temporal encoding (LPTE) module, and bidirectional spatial graph convolution (BSGC) module. The GTE adopts a gated mechanism to filter short-term temporal information, while the MHAT utilizes position encoding to enhance the difference of each timestamps, then use multi-head attention to capture short-term temporal dependency. The BSGC is adopted to handle with spatial relationships between sensor nodes. And we design a periodic encoding technique to process long-term temporal dependencies. The BSGC handles spatial relationships between sensor nodes, and a periodic encoding technique is used to process long-term temporal dependencies. Our experimental analysis includes completion and forecasting tasks, as well as transfer and ablation analyses. The results show that our proposed model outperforms state-of-the-art baselines on real-world datasets.

References

[1]

Gabriel Appleby, Linfeng Liu, and Li-Ping Liu. 2020. Kriging Convolutional Networks. Proceedings of the AAAI Conference on Artificial Intelligence 34 (Apr. 2020), 3187–3194. DOI:

[2]

M. T. Bahadori, Y. Qi, and L. Yan. 2014. Fast Multivariate Spatio-Temporal Analysis via Low Rank Tensor Learning. Advances in Neural Information Processing Systems 4 (2014), 3491–3499.

[3]

Wei Cao, Dong Wang, Jian Li, Hao Zhou, Lei Li, and Yitan Li. 2018. BRITS: Bidirectional Recurrent Imputation for Time Series. Advances in Neural Information Processing Systems, 31 (2018).

[4]

Cen Chen, Kenli Li, Sin G. Teo, Xiaofeng Zou, Kang Wang, Jie Wang, and Zeng Zeng. 2019. Gated Residual Recurrent Graph Neural Networks for Traffic Prediction. Proceedings of the AAAI Conference on Artificial Intelligence 33, 01 (Jul. 2019), 485–492. DOI:

Digital Library

[5]

Xinyu Chen, Zhaocheng He, and Lijun Sun. 2019. A Bayesian Tensor Decomposition Approach for Spatiotemporal Traffic Data Imputation. Transportation Research Part C: Emerging Technologies 98 (2019), 73–84.

[6]

Dingxiong Deng, Cyrus Shahabi, Ugur Demiryurek, Linhong Zhu, Rose Yu, and Yan Liu. 2016. Latent space model for road networks to predict time-varying traffic. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’16). ACM, New York, NY, USA, 1525–1534. DOI:

Digital Library

[7]

Zulong Diao, Xin Wang, Dafang Zhang, Yingru Liu, Kun Xie, and Shaoyao He. 2019. Dynamic spatial-temporal graph convolutional neural networks for traffic forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, 890–897.

Digital Library

[8]

Shengnan Guo, Youfang Lin, Ning Feng, Chao Song, and Huaiyu Wan. 2019. Attention based spatial-temporal graph convolutional networks for traffic flow forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, 922–929.

Digital Library

[9]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc. DOI: https://proceedings.neurips.cc/paper/2017/file/5dd9db5e033da9c6fb5ba83c7a7ebea9-Paper.pdf

Digital Library

[10]

William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Proceedings of the Neural Information Processing Systems, 1024–1034.

[11]

Thomas N. Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907. Retrieved from https://doi.org/10.48550/arXiv.1609.02907

[12]

Sanmukh R. Kuppannagari, Yao Fu, Chung Ming Chueng, and Viktor K. Prasanna. 2021. Spatio-temporal missing data imputation for smart power grids. In Proceedings of the 12th ACM International Conference on Future Energy Systems, 458–465.

Digital Library

[13]

Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. 2017. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. arXiv:1707.01926. Retrieved from https://doi.org/10.48550/arXiv.1707.01926

[14]

Yuankai Wu, Dingyi Zhuang, Aurelie Labbe, Lijun Sun. (2021). Inductive Graph Neural Networks for Spatiotemporal Kriging. In Proceedings of the AAAI Conference on Artificial Intelligence, 35, 5 (2021), 4478–4485. Retrieved from https://doi.org/10.1609/aaai.v35i5.16575

[15]

Yuxuan Liang, Yutong Xia, Songyu Ke, Yiwei Wang, Qingsong Wen, Junbo Zhang, Yu Zheng, and Roger Zimmermann. 2023. Airformer: Predicting nationwide air quality in China with transformers. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37, 14329–14337.

Digital Library

[16]

Yukai Liu, Rose Yu, Stephan Zheng, Eric Zhan, and Yisong Yue. 2019. NAOMI: Non-Autoregressive Multiresolution Sequence Imputation. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, Article 1008 (2019), 11238–1124.

[17]

Yonghong Luo, Ying Zhang, Xiangrui Cai, and Xiaojie Yuan. 2019. E2gan: End-to-end generative adversarial network for multivariate time series imputation. In Proceedings of the 28th International Joint Conference on Artificial Intelligence. AAAI Press, 3094–3100.

[18]

Jiali Mei, Yohann De Castro, Yannig Goude, and Georges Hébrail. 2017. Nonnegative matrix factorization for time series recovery from a few temporal aggregates. In Proceedings of the International Conference on Machine Learning. PMLR, 2382–2390.

[19]

Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda, and Michael M. Bronstein. 2017. Geometric deep learning on graphs and manifolds using mixture model CNNs. In Proceedings of the Computer Vision and Pattern Recognition, 5425–5434.

[20]

T. Subba Rao. 2012. Statistics for Spatio-Temporal Data. Journal of Time Series Analysis 33, 4 (2012), 699–700.

[21]

Ruslan Salakhutdinov and Andriy Mnih. 2008. Bayesian probabilistic matrix factorization using Markov chain Monte Carlo. In Proceedings of the 25th International Conference on Machine Learning, 880–887.

Digital Library

[22]

David Salinas, Michael Bohlke-Schneider, Laurent Callot, Roberto Medico, Jan Gasthaus. 2019. High-Dimensional Multivariate Forecasting with Low-Rank Gaussian Copula Processes. Advances in neural information processing systems 32 (2019).

[23]

Koh Takeuchi, Hisashi Kashima, and Naonori Ueda. 2017. Autoregressive tensor factorization for spatio-temporal predictions. In Proceedings of the 2017 IEEE International Conference on Data Mining (ICDM), 1105–1110. DOI:

[24]

Chunyang Wang, Yanmin Zhu, Tianzi Zang, Haobing Liu, and Jiadi Yu. 2021. Modeling inter-station relationships with attentive temporal graph convolutional network for air quality prediction. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 616–634.

Digital Library

[25]

Hong-Wei Wang, Zhong-Ren Peng, Dongsheng Wang, Yuan Meng, Tianlong Wu, Weili Sun, and Qing-Chang Lu. 2020. Evaluation and Prediction of Transportation Resilience under Extreme Weather Events: A Diffusion Graph Convolutional Approach. Transportation Research Part C: Emerging Technologies 115 (2020), 102619.

[26]

Yuandong Wang, Hongzhi Yin, Hongxu Chen, Tianyu Wo, Jie Xu, and Kai Zheng. 2019. Origin-destination matrix prediction via graph convolution: A new perspective of passenger demand modeling. In Proceedings of the 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 1227–1235.

Digital Library

[27]

Yuankai Wu, Dingyi Zhuang, Aurelie Labbe, Lijun Sun. (2021). Inductive Graph Neural Networks for Spatiotemporal Kriging. In Proceedings of the AAAI Conference on Artificial Intelligence 35, 5 (2021), 4478–4485. Retrieved from https://doi.org/10.1609/aaai.v35i5.16575

[28]

Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. 2019. Graph WaveNet for deep spatial-temporal graph modeling. arXiv:1906.00121. Retrieved from https://doi.org/10.48550/arXiv.1906.00121

[29]

Mingxing Xu, Wenrui Dai, Chunmiao Liu, Xing Gao, Weiyao Lin, Guo-Jun Qi, and Hongkai Xiong. 2020. Spatial-temporal transformer networks for traffic flow forecasting. arXiv:2001.02908.

[30]

Jin-Ming Yang, Zhong-Ren Peng, and Lei Lin. 2021. Real-Time Spatiotemporal Prediction and Imputation of Traffic Status Based on LSTM and Graph Laplacian Regularized Matrix Factorization. Transportation Research Part C: Emerging Technologies 129 (2021), 103228.

[31]

Jinsung Yoon, James Jordon, and Mihaela Schaar. 2018. GAIN: Missing data imputation using generative adversarial nets. In Proceedings of the International Conference on Machine Learning. PMLR, 5689–5698.

[32]

Bing Yu, Haoteng Yin, and Zhanxing Zhu. 2018. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. In Proceedings of the International Joint Conference on Artificial Intelligence, 3634–3640.

[33]

Chuanpan Zheng, Xiaoliang Fan, Cheng Wang, and Jianzhong Qi. 2020. GMAN: A graph multi-attention network for traffic prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34, 1234–1241.

[34]

T. Zhou, H. Shan, A. Banerjee, and G. Sapiro. 2012. Kernelized probabilistic matrix factorization: Exploiting graphs and side information. In Proceedings of the 12th SIAM International Conference on Data Mining, 403–414.

Cited By

Xing YGan WChen Q(2025)Artificial intelligence in landscape architecture: a surveyInternational Journal of Machine Learning and Cybernetics10.1007/s13042-025-02536-wOnline publication date: 29-Jan-2025
https://doi.org/10.1007/s13042-025-02536-w
Chen ZGan W(2024)Towards episode rules with non-overlapping frequency and targeted miningInformation Sciences: an International Journal10.1016/j.ins.2024.121028678:COnline publication date: 8-Aug-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.121028

Index Terms

LSTGCN: Inductive Spatial Temporal Imputation Using Long Short-Term Dependencies
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
    1. Redundancy
  2. Embedded and cyber-physical systems
    1. Embedded systems
    2. Robotics
2. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Temporal reasoning

Recommendations

Multi-dimensional spatial–temporal graph convolution for urban sensors imputation and enhancement
Abstract
Spatio-temporal data are critical for intelligent systems, such as smart transportation and smart cities. However, due to sensor failure or power failure, the spatiotemporal data missing tends to have a big impact on downstream tasks. Meanwhile, ...
Spatial–temporal multi-feature fusion network for long short-term traffic prediction
Abstract
Exploiting deep spatial–temporal features for traffic prediction has become growing widespread. Accurate traffic prediction is still challenging due to the complex spatial dependencies and time varying temporal dependencies, especially ...
Highlights
- Capturing complex spatial–temporal correlations for short and long term prediction.
Long-term multi-dimensional spatial-temporal graph convolution for urban sensors imputation and augmentation
SIGSPATIAL '22: Proceedings of the 30th International Conference on Advances in Geographic Information Systems

Due to sensor failure or power failure, the spatiotemporal data missing tends to have a greater impact on downstream tasks. Meanwhile, if sensors are scarce, some spatial positions without sensors need data augmentation. Existing workarounds focus on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Knowledge Discovery from Data

ACM Transactions on Knowledge Discovery from Data Volume 18, Issue 9

November 2024

730 pages

EISSN:1556-472X

DOI:10.1145/3613722

Editor:
Jian Pei
Duke University, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 November 2024

Online AM: 02 September 2024

Accepted: 20 July 2024

Revised: 06 May 2024

Received: 14 October 2022

Published in TKDD Volume 18, Issue 9

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
711
Total Downloads

Downloads (Last 12 months)711
Downloads (Last 6 weeks)34

Reflects downloads up to 26 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xing YGan WChen Q(2025)Artificial intelligence in landscape architecture: a surveyInternational Journal of Machine Learning and Cybernetics10.1007/s13042-025-02536-wOnline publication date: 29-Jan-2025
https://doi.org/10.1007/s13042-025-02536-w
Chen ZGan W(2024)Towards episode rules with non-overlapping frequency and targeted miningInformation Sciences: an International Journal10.1016/j.ins.2024.121028678:COnline publication date: 8-Aug-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.121028

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

Figures

Tables

Media

View full text|Download PDF

View Issue’s Table of Contents