# Sparse Graph Learning from Spatiotemporal Time Series

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 56 of its 84 references that are in the map.
- First posted on arXiv 26 May 2022.

## Builds on (most cited first, 30 of 56)

- [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)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Graph WaveNet for Deep Spatial-Temporal Graph Modeling](https://mlsanity.com/paper/1906.00121/) (2019)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks](https://mlsanity.com/paper/2005.11650/) (2020)
- [Self-critical Sequence Training for Image Captioning](https://mlsanity.com/paper/1612.00563/) (2016)
- [Adaptive Graph Convolutional Recurrent Network for Traffic Forecasting](https://mlsanity.com/paper/2007.02842/) (2020)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [Neural Relational Inference for Interacting Systems](https://mlsanity.com/paper/1802.04687/) (2018)
- [Graph Neural Network-Based Anomaly Detection in Multivariate Time Series](https://mlsanity.com/paper/2106.06947/) (2021)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Structured Sequence Modeling with Graph Convolutional Recurrent Networks](https://mlsanity.com/paper/1612.07659/) (2016)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Discrete Graph Structure Learning for Forecasting Multiple Time Series](https://mlsanity.com/paper/2101.06861/) (2021)

## Built on by (most cited first, 22 of 22)

- [A Survey on Graph Neural Networks for Time Series: Forecasting, Classification, Imputation, and Anomaly Detection](https://mlsanity.com/paper/2307.03759/) (2023)
- [Taming Local Effects in Graph-based Spatiotemporal Forecasting](https://mlsanity.com/paper/2302.04071/) (2023)
- [Graph Deep Learning for Time Series Forecasting](https://mlsanity.com/paper/2310.15978/) (2023)
- [Relational Conformal Prediction for Correlated Time Series](https://mlsanity.com/paper/2502.09443/) (2025)
- [A Systematic Literature Review of Spatio-Temporal Graph Neural Network Models for Time Series Forecasting and Classification](https://mlsanity.com/paper/2410.22377/) (2024)
- [Graph-based Virtual Sensing from Sparse and Partial Multivariate Observations](https://mlsanity.com/paper/2402.12598/) (2024)
- [LLM as Clinical Graph Structure Refiner: Enhancing Representation Learning in EEG Seizure Diagnosis](https://mlsanity.com/paper/2604.28178/) (2026)
- [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)
- [Learning Latent Graph Structures and their Uncertainty](https://mlsanity.com/paper/2405.19933/) (2024)
- [CR-LSO: Convex Neural Architecture Optimization in the Latent Space of Graph Variational Autoencoder with Input Convex Neural Networks](https://mlsanity.com/paper/2211.05950/) (2022)
- [Assessment of Spatio-Temporal Predictors in the Presence of Missing and Heterogeneous Data](https://mlsanity.com/paper/2302.01701/) (2023)
- [Diffusion model for relational inference](https://mlsanity.com/paper/2401.16755/) (2024)
- [Interpreting Temporal Graph Neural Networks with Koopman Theory](https://mlsanity.com/paper/2410.13469/) (2024)
- [Online Graph Topology Learning via Time-Vertex Adaptive Filters: From Theory to Cardiac Fibrillation](https://mlsanity.com/paper/2411.01567/) (2024)
- [Joint Hypergraph Rewiring and Memory-Augmented Forecasting Techniques in Digital Twin Technology](https://mlsanity.com/paper/2408.12634/) (2024)
- [A Review of Graph-Powered Data Quality Applications for IoT Monitoring Sensor Networks](https://mlsanity.com/paper/2410.21006/) (2024)
- [PeakWeather: MeteoSwiss Weather Station Measurements for Spatiotemporal Deep Learning](https://mlsanity.com/paper/2506.13652/) (2025)
- [Beyond Softmax: A Natural Parameterization for Categorical Random Variables](https://mlsanity.com/paper/2509.24728/) (2025)
- [Efficient Linear Attention for Multivariate Time Series Modeling via Entropy Equality](https://mlsanity.com/paper/2511.03190/) (2025)
- [Virtual Smart Metering in District Heating Networks via Heterogeneous Spatial-Temporal Graph Neural Networks](https://mlsanity.com/paper/2604.10166/) (2026)
- [Bilevel Graph Structure Learning, Revisited: Inner-Channel Origins of the Reported Gain](https://mlsanity.com/paper/2605.07577/) (2026)

## Abstract (arXiv)

Outstanding achievements of graph neural networks for spatiotemporal time series analysis show that relational constraints introduce an effective inductive bias into neural forecasting architectures. Often, however, the relational information characterizing the underlying data-generating process is unavailable and the practitioner is left with the problem of inferring from data which relational graph to use in the subsequent processing stages. We propose novel, principled - yet practical - probabilistic score-based methods that learn the relational dependencies as distributions over graphs while maximizing end-to-end the performance at task. The proposed graph learning framework is based on consolidated variance reduction techniques for Monte Carlo score-based gradient estimation, is theoretically grounded, and, as we show, effective in practice. In this paper, we focus on the time series forecasting problem and show that, by tailoring the gradient estimators to the graph learning problem, we are able to achieve state-of-the-art performance while controlling the sparsity of the learned graph and the computational scalability. We empirically assess the effectiveness of the proposed method on synthetic and real-world benchmarks, showing that the proposed solution can be used as a stand-alone graph identification procedure as well as a graph learning component of an end-to-end forecasting architecture.