Balanced Graph Structure Learning for Multivariate Time Series Forecasting

Weijun Chen, Yanze Wang, Chengshuo Du, Zhenglong Jia, Feng Liu, Ran Chen

TL;DR

Balanced Graph Structure Learning for Forecasting (BGSLF) is a new framework that strikes a perfect chord between computational efficiency and model flexibility in multivariate time series forecasting. By introducing a "Smooth Sparse Unit" for differentiable graph learning and a selection mechanism to pick the best graph for each input, it achieves state-of-the-art accuracy with up to 190x fewer parameters than previous leading models.

What Problem Does This Paper Address?

Predicting multivariate time series (MTS)—like traffic flow across hundreds of sensors or power output from multiple solar plants—is hard because variables are deeply interconnected. While Graph Neural Networks (GNNs) are great at modeling these relationships, they usually require a predefined "graph" (a map of how sensors relate).

In many real-world scenarios, we don't have a perfect map. Recent "Graph Structure Learning" (GSL) models try to learn this map automatically, but they hit three major roadblocks:

  1. The Efficiency-Flexibility Trade-off: Models either learn one "global" graph for everything (efficient but rigid) or a unique graph for every single data batch (flexible but memory-intensive).
  2. Lack of Domain Knowledge: Many models start with random noise rather than using the inherent patterns in the data to guide the graph's shape.
  3. The Sparsity Headache: Real-world relationships are sparse (most sensors don't affect most others). However, forcing a graph to be sparse usually involves non-differentiable functions (like Top-K), which makes the model very difficult to train.

Methods

The authors propose BGSLF, which consists of three innovative components:

  • Multi-Graph Generation Network (MGN): Instead of one graph or infinite graphs, MGN generates a small, specified set of candidate graphs ($R$). It uses "difference operations" (looking at how values change over time) to capture moderate correlations, which is a common trick in time-series domain knowledge.
  • Graph Selection Module: For every new batch of input data, the model calculates the cosine similarity between the input and the $R$ candidate graphs. it then selects the most "fitting" graph to use for that specific prediction. This provides flexibility without the massive overhead of generating a new graph from scratch every time.
  • Smooth Sparse Unit (SSU): This is the mathematical "secret sauce." Inspired by smooth manifolds, SSU is a differentiable function that pushes adjacency matrix values toward 0 or 1. This allows the model to learn sparse, continuous graphs using standard gradient descent, avoiding the training instability of discrete methods like Gumbel-Softmax.

The backbone of the forecasting itself relies on a Diffusion Convolutional Recurrent Network (DCRNN), which is well-suited for capturing both spatial and temporal dynamics.

Datasets

The model was evaluated on four diverse, real-world benchmarks:

  • PEMS04 & PEMS08: Traffic flow data (speed and volume) from California sensors.
  • METR-LA: Traffic speed data from Los Angeles highways.
  • Solar-Energy: Solar power output from 137 PV plants in Alabama.

Key Insights and Ideas

  • Continuous > Discrete: The authors found that continuous adjacency matrices (where a connection can be 0.7 instead of just 0 or 1) represent complex correlations much better than binary ones.
  • The Power of Sparsity: By using the SSU, the model naturally ignores "noise" connections. Visualizations in the paper show the model starting with dense, messy graphs and refining them into clean, sparse structures that mirror real-world geography.
  • Extreme Parameter Efficiency: By learning a small set of representative graphs rather than a massive adjacency matrix for every possible pair of nodes, the model is incredibly "light." On the METR-LA dataset, BGSLF uses ~202k parameters, while the competing GTS model uses over 38 million.

Key Results

BGSLF consistently outperformed or matched state-of-the-art models (like MTGNN, AGCRN, and GTS) across all datasets and time horizons (3, 6, and 12 steps ahead).

  • Accuracy: On the PEMS08 dataset, BGSLF achieved the lowest Mean Absolute Error (MAE) across all horizons.
  • Efficiency: The most striking result is the parameter count. In the METR-LA test, BGSLF achieved better accuracy than the GTS model while being 190 times smaller in terms of trainable parameters. This makes it a prime candidate for deployment in resource-constrained environments.

Limitations and Future Work

While the paper demonstrates excellent results, a few areas remain open for exploration:

  • Fixed Graph Count: The number of candidate graphs ($R$) is a hyperparameter that must be set manually. Future work could involve a model that dynamically determines how many "basis graphs" it needs.
  • Backbone Dependency: The current framework is built on DCRNN. It would be interesting to see if these graph-learning modules (SSU and MGN) provide similar boosts to newer Transformer-based temporal architectures.
  • Generalization: The authors suggest that the well-trained embeddings and learned graphs could be applied to other downstream tasks beyond forecasting, such as anomaly detection.

Summary updated

Abstract

Accurate forecasting of multivariate time series is an extensively studied subject in finance, transportation, and computer science. Fully mining the correlation and causation between the variables in a multivariate time series exhibits noticeable results in improving the performance of a time series model. Recently, some models have explored the dependencies between variables through end-to-end graph structure learning without the need for predefined graphs. However, current models do not incorporate the trade-off between efficiency and flexibility and lack the guidance of domain knowledge in the design of graph structure learning algorithms. This paper alleviates the above issues by proposing Balanced Graph Structure Learning for Forecasting (BGSLF), a novel deep learning model that joins graph structure learning and forecasting. Technically, BGSLF leverages the spatial information into convolutional operations and extracts temporal dynamics using the diffusion convolutional recurrent network. The proposed framework balance the trade-off between efficiency and flexibility by introducing Multi-Graph Generation Network (MGN) and Graph Selection Module. In addition, a method named Smooth Sparse Unit (SSU) is designed to sparse the learned graph structures, which conforms to the sparse spatial correlations in the real world. Extensive experiments on four real-world datasets demonstrate that our model achieves state-of-the-art performances with minor trainable parameters. Code will be made publicly available.
BibTeX
@misc{chen2022balanced,
  author = {Weijun Chen and Yanze Wang and Chengshuo Du and Zhenglong Jia and Feng Liu and Ran Chen},
  title = {{Balanced Graph Structure Learning for Multivariate Time Series Forecasting}},
  year = {2022},
  eprint = {2201.09686},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2201.09686},
}
Figure