# Online Algorithm for Node Feature Forecasting in Temporal Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 45 references that are in the map.
- First posted on arXiv 30 Jan 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [Are Transformers Effective for Time Series Forecasting?](https://mlsanity.com/paper/2205.13504/) (2022)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Graph WaveNet for Deep Spatial-Temporal Graph Modeling](https://mlsanity.com/paper/1906.00121/) (2019)
- [Explaining Explanations: An Overview of Interpretability of Machine Learning](https://mlsanity.com/paper/1806.00069/) (2018)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [T-GCN: A Temporal Graph ConvolutionalNetwork for Traffic Prediction](https://mlsanity.com/paper/1811.05320/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [A Recurrent Latent Variable Model for Sequential Data](https://mlsanity.com/paper/1506.02216/) (2015)
- [Techniques for Interpretable Machine Learning](https://mlsanity.com/paper/1808.00033/) (2018)
- [Spatial-Temporal Graph ODE Networks for Traffic Flow Forecasting](https://mlsanity.com/paper/2106.12931/) (2021)
- [PyTorch Geometric Temporal: Spatiotemporal Signal Processing with Neural Machine Learning Models](https://mlsanity.com/paper/2104.07788/) (2021)
- [Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunities](https://mlsanity.com/paper/2302.01018/) (2023)
- [A Survey on Embedding Dynamic Graphs](https://mlsanity.com/paper/2101.01229/) (2021)
- [Dissecting the Diffusion Process in Linear Graph Convolutional Networks](https://mlsanity.com/paper/2102.10739/) (2021)
- [AutoCTS: Automated Correlated Time Series Forecasting -- Extended Version](https://mlsanity.com/paper/2112.11174/) (2021)
- [Identification of Gaussian Process State Space Models](https://mlsanity.com/paper/1705.10888/) (2017)
- [Learning and Forecasting Opinion Dynamics in Social Networks](https://mlsanity.com/paper/1506.05474/) (2015)
- [Chickenpox Cases in Hungary: a Benchmark Dataset for Spatiotemporal Signal Processing with Graph Neural Networks](https://mlsanity.com/paper/2102.08100/) (2021)
- [LightCTS: A Lightweight Framework for Correlated Time Series Forecasting](https://mlsanity.com/paper/2302.11974/) (2023)
- [Graph-based Multi-ODE Neural Networks for Spatio-Temporal Traffic Forecasting](https://mlsanity.com/paper/2305.18687/) (2023)
- [A Primer on Temporal Graph Learning](https://mlsanity.com/paper/2401.03988/) (2024)

## Abstract (arXiv)

In this paper, we propose an online algorithm mspace for forecasting node features in temporal graphs, which captures spatial cross-correlation among different nodes as well as the temporal auto-correlation within a node. The algorithm can be used for both probabilistic and deterministic multi-step forecasting, making it applicable for estimation and generation tasks. Comparative evaluations against various baselines, including temporal graph neural network (TGNN) models and classical Kalman filters, demonstrate that mspace performs at par with the state-of-the-art and even surpasses them on some datasets. Importantly, mspace demonstrates consistent performance across datasets with varying training sizes, a notable advantage over TGNN models that require abundant training samples to effectively learn the spatiotemporal trends in the data. Therefore, employing mspace is advantageous in scenarios where the training sample availability is limited. Additionally, we establish theoretical bounds on multi-step forecasting error of mspace and show that it scales linearly with the number of forecast steps q as O(q). For an asymptotically large number of nodes n, and timesteps T, the computational complexity of mspace grows linearly with both n, and T, i.e., O(nT), while its space complexity remains constant O(1). We compare the performance of various mspace variants against ten recent TGNN baselines and two classical baselines, ARIMA and the Kalman filter across ten real-world datasets. Additionally, we propose a technique to generate synthetic datasets to aid in evaluating node feature forecasting methods, with the potential to serve as a benchmark for future research. Lastly, we have investigate the interpretability of different mspace variants by analyzing model parameters alongside dataset characteristics to derive model and data-centric insights.