# Scalable Spatiotemporal Graph Neural Networks

arXiv: https://arxiv.org/abs/2209.06520 · HTML: https://mlsanity.com/paper/2209.06520/

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 65 references that are in the map.
- First posted on arXiv 14 Sep 2022.

## Builds on (most cited first, 23 of 23)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Modeling Long- and Short-Term Temporal Patterns with Deep Neural Networks](https://mlsanity.com/paper/1703.07015/) (2017)
- [Graph WaveNet for Deep Spatial-Temporal Graph Modeling](https://mlsanity.com/paper/1906.00121/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks](https://mlsanity.com/paper/2005.11650/) (2020)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [GMAN: A Graph Multi-Attention Network for Traffic Prediction](https://mlsanity.com/paper/1911.08415/) (2019)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Structured Sequence Modeling with Graph Convolutional Recurrent Networks](https://mlsanity.com/paper/1612.07659/) (2016)
- [Highway Networks](https://mlsanity.com/paper/1505.00387/) (2015)
- [A Gentle Introduction to Deep Learning for Graphs](https://mlsanity.com/paper/1912.12693/) (2019)
- [Filling the G_ap_s: Multivariate Time Series Imputation by Graph Neural Networks](https://mlsanity.com/paper/2108.00298/) (2021)
- [Inductive Graph Neural Networks for Spatiotemporal Kriging](https://mlsanity.com/paper/2006.07527/) (2020)
- [Learning to Reconstruct Missing Data from Spatiotemporal Graphs with Sparse Observations](https://mlsanity.com/paper/2205.13479/) (2022)
- [Reservoir computing approaches for representation and classification of multivariate time series](https://mlsanity.com/paper/1803.07870/) (2018)
- [FC-GAGA: Fully Connected Gated Graph Architecture for Spatio-Temporal Traffic Forecasting](https://mlsanity.com/paper/2007.15531/) (2020)
- [Multivariate Time Series Forecasting with Latent Graph Inference](https://mlsanity.com/paper/2203.03423/) (2022)
- [TraverseNet: Unifying Space and Time in Message Passing for Traffic Forecasting](https://mlsanity.com/paper/2109.02474/) (2021)

## Built on by (most cited first, 30 of 52)

- [A Survey on Graph Neural Networks for Time Series: Forecasting, Classification, Imputation, and Anomaly Detection](https://mlsanity.com/paper/2307.03759/) (2023)
- [Temporal Graph Benchmark for Machine Learning on Temporal Graphs](https://mlsanity.com/paper/2307.01026/) (2023)
- [LargeST: A Benchmark Dataset for Large-Scale Traffic Forecasting](https://mlsanity.com/paper/2306.08259/) (2023)
- [Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunities](https://mlsanity.com/paper/2302.01018/) (2023)
- [Taming Local Effects in Graph-based Spatiotemporal Forecasting](https://mlsanity.com/paper/2302.04071/) (2023)
- [A Comprehensive Survey of Dynamic Graph Neural Networks: Models, Frameworks, Benchmarks, Experiments and Challenges](https://mlsanity.com/paper/2405.00476/) (2024)
- [Long Range Propagation on Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2406.02740/) (2024)
- [Graph Deep Learning for Time Series Forecasting](https://mlsanity.com/paper/2310.15978/) (2023)
- [Relational Deep Learning: Challenges, Foundations and Next-Generation Architectures](https://mlsanity.com/paper/2506.16654/) (2025)
- [Deep learning for dynamic graphs: models and benchmarks](https://mlsanity.com/paper/2307.06104/) (2023)
- [Graph-based Time Series Clustering for End-to-End Hierarchical Forecasting](https://mlsanity.com/paper/2305.19183/) (2023)
- [Graph-based Forecasting with Missing Data through Spatiotemporal Downsampling](https://mlsanity.com/paper/2402.10634/) (2024)
- [Temporal Graph ODEs for Irregularly-Sampled Time Series](https://mlsanity.com/paper/2404.19508/) (2024)
- [Expand and Compress: Exploring Tuning Principles for Continual Spatio-Temporal Graph Forecasting](https://mlsanity.com/paper/2410.12593/) (2024)
- [Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling](https://mlsanity.com/paper/2505.18728/) (2025)
- [Intrinsic User-Centric Interpretability through Global Mixture of Experts](https://mlsanity.com/paper/2402.02933/) (2024)
- [A Novel Approach to Temporal QoS Estimation via Extended Kalman Filter-Incorporated Latent Feature Analysis](https://mlsanity.com/paper/2606.23010/) (2026)
- [Continuous Product Graph Neural Networks](https://mlsanity.com/paper/2405.18877/) (2024)
- [LITE: Modeling Environmental Ecosystems with Multimodal Large Language Models](https://mlsanity.com/paper/2404.01165/) (2024)
- [Joint Estimation and Prediction of City-wide Delivery Demand: A Large Language Model Empowered Graph-based Learning Approach](https://mlsanity.com/paper/2408.17258/) (2024)
- [Over-squashing in Spatiotemporal Graph Neural Networks](https://mlsanity.com/paper/2506.15507/) (2025)
- [Graph State-Space Models and Latent Relational Inference](https://mlsanity.com/paper/2301.01741/) (2023)
- [Edge of stability echo state networks](https://mlsanity.com/paper/2308.02902/) (2023)
- [Contextualizing MLP-Mixers Spatiotemporally for Urban Data Forecast at Scale](https://mlsanity.com/paper/2307.01482/) (2023)
- [Synthetic Datasets for Machine Learning on Spatio-Temporal Graphs using PDEs](https://mlsanity.com/paper/2502.04140/) (2025)
- [Leveraging Temporal Graph Networks Using Module Decoupling](https://mlsanity.com/paper/2310.02721/) (2023)
- [Interpreting Temporal Graph Neural Networks with Koopman Theory](https://mlsanity.com/paper/2410.13469/) (2024)
- [The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics](https://mlsanity.com/paper/2505.11930/) (2025)
- [S2Transformer: Scalable Structured Transformers for Global Station Weather Forecasting](https://mlsanity.com/paper/2509.19648/) (2025)
- [FaST: Efficient and Effective Long-Horizon Forecasting for Large-Scale Spatial-Temporal Graphs via Mixture-of-Experts](https://mlsanity.com/paper/2601.05174/) (2026)

## Abstract (arXiv)

Neural forecasting of spatiotemporal time series drives both research and industrial innovation in several relevant application domains. Graph neural networks (GNNs) are often the core component of the forecasting architecture. However, in most spatiotemporal GNNs, the computational complexity scales up to a quadratic factor with the length of the sequence times the number of links in the graph, hence hindering the application of these models to large graphs and long temporal sequences. While methods to improve scalability have been proposed in the context of static graphs, few research efforts have been devoted to the spatiotemporal case. To fill this gap, we propose a scalable architecture that exploits an efficient encoding of both temporal and spatial dynamics. In particular, we use a randomized recurrent neural network to embed the history of the input time series into high-dimensional state representations encompassing multi-scale temporal dynamics. Such representations are then propagated along the spatial dimension using different powers of the graph adjacency matrix to generate node embeddings characterized by a rich pool of spatiotemporal features. The resulting node embeddings can be efficiently pre-computed in an unsupervised manner, before being fed to a feed-forward decoder that learns to map the multi-scale spatiotemporal representations to predictions. The training procedure can then be parallelized node-wise by sampling the node embeddings without breaking any dependency, thus enabling scalability to large networks. Empirical results on relevant datasets show that our approach achieves results competitive with the state of the art, while dramatically reducing the computational burden.