Source-linked AI summary
Discrete Graph Structure Learning for Forecasting Multiple Time Series
Chao Shang, Jie Chen, Jinbo Bi
TL;DR
The paper asks how to exploit pairwise information for forecasting multiple time series when the graph is unknown. It jointly learns a probabilistic graph and GNN through differentiable discrete-graph sampling, and reports lower training cost and better forecasting quality than LDS and broad forecasting baselines.
Problem
Graph structure can help forecast interrelated time series, but it may be unavailable or incomplete, motivating automatic graph learning jointly with forecasting.
Method
GTS learns a probabilistic graph distribution and a GNN end-to-end, parameterizing the distribution with neural networks so discrete graphs can be sampled differentiably.
Results
The approach attains the best forecasting quality across comprehensive comparisons and significantly reduces training cost relative to LDS.
Takeaways & Limitations
The learned graph is useful as forecasting information, while its quality is judged by forecasting accuracy rather than causal identification or recovery of a ground-truth graph.
Takeaways & Limitations
Causal discovery among multiple multivariate time series requires a nontrivial extension beyond this study.
Abstract
from arXiv · showhide
Time series forecasting is an extensively studied subject in statistics, economics, and computer science. Exploration of the correlation and causation among the variables in a multivariate time series shows promise in enhancing the performance of a time series model. When using deep neural networks as forecasting models, we hypothesize that exploiting the pairwise information among multiple (multivariate) time series also improves their forecast. If an explicit graph structure is known, graph neural networks (GNNs) have been demonstrated as powerful tools to exploit the structure. In this work, we propose learning the structure simultaneously with the GNN if the graph is unknown. We cast the problem as learning a probabilistic graph model through optimizing the mean performance over the graph distribution. The distribution is parameterized by a neural network so that discrete graphs can be sampled differentiably through reparameterization. Empirical evaluations show that our method is simpler, more efficient, and better performing than a recently proposed bilevel learning approach for graph structure learning, as well as a broad array of forecasting models, either deep or non-deep learning based, and graph or non-graph based.
1 INTRODUCTION
The paper addresses forecasting multiple interrelated time series when graph structure is unavailable or incomplete by learning a graph jointly with a GNN. Its unilevel parameterization is presented as less expensive, more scalable, and focused on forecasting quality rather than causal or graph recovery.
- Pairwise similarities and connections among multiple time series can improve forecasting accuracy, while GNNs leverage graph structure to forecast series simultaneously.
- Graph structure may be unavailable or incomplete because obtaining it is difficult or sensitive information is deliberately withheld.
- LDS learns graph probabilities through bilevel optimization, where GNN weights are optimized for each graph and continuous probabilities replace discrete adjacency values for differentiability.
- LDS is computationally expensive because differentiating through its recursive inner optimization can be memory intensive or time consuming, and its Θ(n2) graph parameters hinder scaling.
- The proposed approach reverses the parameterization: neural-network parameters θ(w) define the graph distribution while GNN and graph parameters are optimized in one level.
- The approach is less expensive and better scales because unilevel gradients are straightforward and efficient, while parameter counts do not grow quadratically with the number of time series.
- GTS uses learned graphs to improve forecasting quality, not to identify causal relationships or recover a ground-truth graph, and regularizes departures from prior graph beliefs.
2 RELATED WORK
Related work spans classical and deep forecasting models, graph neural networks for temporal data, and graph structure learning with or without causal constraints. The paper positions its approach alongside LDS, MTGNN, and NRI while allowing a more general structural prior.
- Classical forecasting methods include autoregressive models, ARIMA, hidden Markov models, and Kalman filters.
- RNN variants such as LSTM, BiLSTM, and GRU address limitations of vanilla RNNs, while Transformers provide more recent deep-learning alternatives.
- Specialized graph architectures for time series combine temporal processing with graph structure, including GCRN, DCRNN, STGCN, and T-GCN.
- Graph structure learning includes causality-oriented methods enforcing directed acyclic structure and general-graph methods such as LDS, MTGNN, and NRI.
- Unlike MTGNN’s degree-k graph parameterization, the paper allows a more general structural prior and compares its approach with the closely related latent-graph method NRI.
3 METHOD
GTS jointly learns a probabilistic graph structure and a graph-based forecasting model for multiple time series. It parameterizes edge probabilities with neural networks, samples discrete graphs differentiably, and uses recurrent graph convolution for forecasting.
- Graph structure learning: GTS models the binary adjacency matrix as independent Bernoulli variables whose edge probabilities are parameterized by θ.Each Aij is sampled from Ber(θij).
- Graph structure learning: Gumbel reparameterization makes discrete graph sampling differentiable during optimization, with temperature annealed toward zero.As the temperature approaches zero, sampled edges become binary with Bernoulli probabilities θij.
- Graph structure learning: A neural feature extractor and pairwise link predictor map each series and series pair to edge probabilities θij.The extractor produces zi for each series, and the link predictor applies fully connected layers to concatenated feature vectors.
- Graph neural network forecasting: The forecasting model uses seq2seq encoding and decoding, with recurrent graph convolution updating hidden states for all series simultaneously.The encoder summarizes T observed steps, while the decoder generates the next τ steps; DCRNN diffusion convolution is used for directed graphs.
- Design comparison: The structure-learning component is more crucial than the particular GNN architecture, because replacing the forecasting GNN preserves similar performance while removing structure learning reduces performance.The comparison is made against models using no graph or requiring a supplied graph.
- Training: The base training loss is mean absolute error between forecasts and ground truth, optionally combined with a cross-entropy regularizer from an a priori graph.A kNN prior can encourage sparsity when k is small.
4 EXPERIMENTS
Experiments evaluate GTS across forecasting benchmarks, baselines, computational cost, and graph regularization. GTS achieves strong forecasting performance while learning useful structures with favorable training overhead and controllable similarity to prior graphs.
- Forecasting quality: GTS significantly outperforms LDS and DCRNN on METR-LA, while its structure-learning component contributes more to performance than the choice of GNN forecasting component.GTSv performs between GTS and LDS, supporting the reported importance of the structure-learning component.
- Forecasting quality: GTS produces the best prediction in all reported PEMS-BAY and PMU scenarios and under all metrics.On PMU, NRI is generally second to GTS/GTSv and better than LDS in most cases.
- Computational efficiency: GTS training takes approximately three times as long as DCRNN, whereas LDS requires orders of magnitude more time than DCRNN.GTS learns the graph as a byproduct of model training rather than through LDS's bilevel optimization.
- Effect of regularization: On PMU, stronger regularization or a smaller k yields sparser learned graphs while maintaining MAEs around 2.4e-4, compared with LDS's 4.9e-4.Regularization combines forecasting error with cross entropy to incorporate a kNN graph prior.
- Learned structures: For PMU, METR-LA, and PEMS-BAY, intermediate regularization can keep forecasts close to the best quality while making the learned structure closer to the prior adjacency matrix Aa.For PMU, λ = 20 gives average cross entropy 0.34, and thresholding θ at 0.5 can produce false-positive edges.
5 CONCLUSIONS
The paper presents an end-to-end model that learns graph structure and forecasts multiple time series with a GNN. It reports strong forecasting quality and lower training cost than LDS, while regularization incorporates prior graph knowledge.
- GTS learns graph structure and forecasts multiple time series simultaneously with a GNN.
- The graph and GNN are learned end-to-end to exploit pairwise interactions among data streams.
- GTS attains the best forecasting quality across comparisons with non-deep, deep, graph-based, and non-graph baselines.
- Parameterizing the graph with neural networks reduces training cost compared with the bilevel LDS approach.
- Regularization incorporates prior knowledge and yields a healthy variation of the given graph for more accurate forecasting.
A ADDITIONAL DETAILS OF DATA SETS
The experiments use two traffic benchmarks with given graphs and a power-grid PMU dataset without a topology. The PMU data require filtering and aggregation to address unreliable and missing readings.
- METR-LA contains 207 sensors recording four months of five-minute traffic data with a distance-based sensor graph.
- PEMS-BAY contains 325 Bay Area sensors recorded for six months at five-minute frequency, using the same graph-construction procedure as METR-LA.
- PMU contains one month of voltage- and current-magnitude data from 42 U.S. power-grid PMUs, aggregated to five-minute intervals.
- Visual correlations and synchronous patterns among PMU series support learning graph structure between the sensors.
- PMU preprocessing filters extreme values and handles missing readings using available-reading means or whole-series means.
B ADDITIONAL DETAILS OF EXPERIMENT SETTING
The experiments tune several model and regularization hyperparameters, estimate training expectations with one graph sample, and run PyTorch implementations on one GPU. Code is publicly available.
- Grid search tunes learning rate, dropout, LSTM embedding size, kNN k, and regularization weight.
- The loss expectation is averaged over 10 random samples for evaluation, while training uses one sample with a stochastic optimizer.
- All models are implemented in PyTorch and experiments use one GPU on an IBM Power9 compute node.
- The implementation code is available in the authors' GitHub repository.
C ADDITIONAL RESULTS FOR FORECASTING QUALITY
Additional results show that GTS produces the best PEMS-BAY forecasts across scenarios and metrics. The accompanying figure illustrates standardized PMU time series rather than raw values.
- GTS produces the best PEMS-BAY prediction in all scenarios and under all metrics.
- Figure 7 presents example PMU time series after standardization, with vertical axes that do not show raw values.
- Table 3 reports forecasting error results for PEMS-BAY.
D UPDATES OF TABLES 1, 2, AND 3
The authors corrected Tables 1–3 after identifying differences between their DCRNN implementation’s metric calculations and the official DCRNN reporting. The corrected results appear in Tables 4–6, while the comparative observations and conclusions remain unchanged.
- The authors corrected MAE, RMSE, and MAPE calculations to match the official DCRNN results.
- Despite the correction, the authors report that comparisons among methods and their conclusions remain unchanged.
- Table 4 presents the corrected METR-LA forecasting errors.
- Table 5 presents the corrected PMU forecasting errors.
- Table 6 presents the corrected PEMS-BAY forecasting errors.