PaperlayerView exact revision on arXiv

Source-linked AI summary

Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks

Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, Chengqi Zhang

arXiv:2005.11650v1cs.LGstat.ML

TL;DR

Multivariate time-series methods often underuse latent dependencies between variables, while GNNs require graph structures that are usually unavailable. The paper learns directed relations from data within an end-to-end graph-temporal framework, outperforming state-of-the-art methods on 3 of 4 benchmark datasets and matching other approaches on two traffic datasets.

  • Problem

    Existing multivariate time-series methods do not efficiently exploit latent interdependencies, while GNNs require graph structures that are generally unavailable.

  • Method

    The framework jointly learns a sparse directed graph and models spatial and temporal dependencies with graph convolution and temporal convolution modules.

  • Results

    The method outperforms state-of-the-art baselines on 3 of 4 benchmark datasets and achieves on-par performance with other GNNs on two traffic datasets.

  • Takeaways & Limitations

    The framework extends graph-based forecasting to multivariate time series with or without predefined graph structures.

  • Takeaways & Limitations

    The graph adjacency matrix is not provided in most cases and must therefore be learned by the model.

Abstract

from arXiv · show

Modeling multivariate time series has long been a subject that has attracted researchers from a diverse range of fields including economics, finance, and traffic. A basic assumption behind multivariate time series forecasting is that its variables depend on one another but, upon looking closely, it is fair to say that existing methods fail to fully exploit latent spatial dependencies between pairs of variables. In recent years, meanwhile, graph neural networks (GNNs) have shown high capability in handling relational dependencies. GNNs require well-defined graph structures for information propagation which means they cannot be applied directly for multivariate time series where the dependencies are not known in advance. In this paper, we propose a general graph neural network framework designed specifically for multivariate time series data. Our approach automatically extracts the uni-directed relations among variables through a graph learning module, into which external knowledge like variable attributes can be easily integrated. A novel mix-hop propagation layer and a dilated inception layer are further proposed to capture the spatial and temporal dependencies within the time series. The graph learning, graph convolution, and temporal convolution modules are jointly learned in an end-to-end framework. Experimental results show that our proposed model outperforms the state-of-the-art baseline methods on 3 of 4 benchmark datasets and achieves on-par performance with other approaches on two traffic datasets which provide extra structural information.

1 INTRODUCTION

The introduction frames multivariate time series forecasting as a graph-based problem whose latent interdependencies and temporal dynamics are not fully exploited by existing methods. It proposes an end-to-end framework that learns graph structure alongside spatial and temporal representations.

  • Motivation and challenges: Existing forecasting methods assume interdependencies among variables but fail to exploit latent relationships efficiently and effectively.Statistical approaches such as VAR and GP assume linear dependencies, while their model complexity grows with the number of variables.
  • Motivation and challenges: Spatial-temporal GNNs improve forecasting by using structural information, but they generally require an externally provided graph that multivariate time series often lacks.The relationships among variables must therefore be discovered from data rather than supplied as ground-truth knowledge.
  • Proposed framework: The proposed framework combines graph learning, graph convolution, and temporal convolution to learn sparse variable dependencies and model spatial and temporal relationships.Its graph learning layer adaptively extracts a sparse adjacency matrix from data, while graph convolution addresses spatial dependencies and temporal convolution captures temporal dependencies.
  • Proposed framework: All framework parameters are learned jointly through gradient descent, enabling simultaneous multivariate forecasting and internal graph-structure discovery in an end-to-end manner.The learning algorithm also uses curriculum learning to find a better local optimum and reduce memory occupation when processing large graphs.
  • Contributions: The study presents a graph-based perspective for multivariate time series, a module for learning hidden spatial dependencies, and a generic joint framework for forecasting and graph learning.The authors characterize this as the first study to generally model multivariate time series with GNNs from a graph-based perspective.

2 BACKGROUNDS

Traditional time-series forecasting is dominated by statistical models for representing temporal and cross-series relationships, while graph neural networks model spatial dependencies through interactions among neighboring entities.

  • Statistical forecasting: Statistical forecasting methods include ARIMA and VAR, with VAR extending autoregression to capture linear interdependencies among multiple time series.The passage identifies ARIMA as a family of linear models involving AR, MA, and ARMA components.
  • Graph neural networks: Graph neural networks assume that each node’s state depends on neighboring nodes’ states, enabling representation learning over networked entities.The passage describes message passing, information propagation, and graph convolution as mechanisms for capturing spatial dependencies.
  • Graph neural networks: GNN variants capture high-level node representations by passing information among connected entities through message passing, information propagation, or graph convolution.These mechanisms serve similar roles in modeling spatial dependencies among entities in a network.

3 PROBLEM FORMULATION

The task is to forecast future values of a multivariate time series from historical observations, while representing variables as graph nodes whose relationships are captured by a learned adjacency matrix.

  • Forecasting task: Given P historical time steps of an N-dimensional multivariate series, the model predicts either the Q-step-ahead value or Q future values.The historical input is X = {z_t1, z_t2, · · ·, z_tP}, and the target may be Y = {z_tP+Q} or Y = {z_tP+1, z_tP+2, · · ·, z_tP+Q}.
  • Graph definitions: A graph is defined as G = (V, E), with V denoting nodes and E denoting edges.The graph formalism provides the structure for representing relationships among entities.
  • Graph definitions: For a node v, the neighborhood N(v) contains nodes u connected to v by an edge e = (v,u).The edge is defined as pointing from u to v.
  • Graph formulation: Variables in a multivariate time series are treated as nodes in a graph.Their relationships are represented using a graph adjacency matrix.
  • Graph formulation: Because the adjacency matrix is usually unavailable from the data, the model learns it from the multivariate time series.This learned matrix describes relationships among the graph nodes.

4 FRAMEWORK OF MTGNN

MTGNN jointly learns a hidden graph and interleaves graph and temporal convolution modules to model spatial and temporal dependencies in multivariate time series. Its graph learning, mix-hop propagation, and dilated inception components support directed, sparse relational modeling and multi-range temporal pattern extraction.

  • Overall Framework: MTGNN comprises a graph learning layer, graph convolution modules, temporal convolution modules, and an output module trained in an end-to-end framework.The learned adjacency matrix is provided to all graph convolution modules, which are interleaved with temporal convolution modules.
  • Graph Learning: The graph learning layer extracts uni-directional relationships by regularizing the adjacency matrix asymmetrically and selecting top-k neighbors to reduce computation.If A_vu is positive, the diagonal counterpart A_uv is zero; top-k selection makes the adjacency matrix sparse.
  • Graph Learning: The graph learning layer can use static node attributes and reduces per-iteration complexity from O(N^2) to (N/s)^2 by grouping node embeddings.After training, a global graph can be constructed and its adjacency matrix precomputed before prediction.
  • Graph Convolution: The graph convolution module separately processes inflow and outflow through two mix-hop propagation layers that recursively propagate and selectively combine information across hops.The propagation step retains part of the root node’s original states, while the selection step represents information from different propagation depths.
  • Temporal Convolution: The dilated inception layer combines multiple filter sizes with dilated convolution to capture temporal patterns across varied ranges and handle very long sequences.The 1D temporal convolution module uses filters with multiple sizes, addressing the trade-off between short-term detail and long-term pattern discovery.

5 EXPERIMENTAL STUDIES

Experiments evaluate MTGNN on single-step and multi-step forecasting against multivariate time-series and spatial-temporal graph baselines. Results show state-of-the-art performance across most tasks, on-par multi-step performance without predefined graphs, and benefits from key architectural components.

  • Experimental setup: MTGNN is evaluated on single-step and multi-step forecasting using benchmark multivariate time-series and spatial-temporal graph datasets.The evaluation uses MAE, RMSE, MAPE, RRSE, and CORR, with lower values preferred for the first four and higher values for CORR.
  • Overall results: MTGNN achieves state-of-the-art results on most tasks, while sampling sub-graphs for training causes only marginal performance degradation.The main experimental results are reported for MTGNN and MTGNN+sampling.
  • Single-step forecasting: MTGNN achieves state-of-the-art results over almost all horizons on Solar-Energy, Traffic, and Electricity in single-step forecasting.On Traffic, MTGNN lowers RSE by 7.24%, 3.88%, and 4.83% at horizons 3, 12, and 24, respectively.
  • Multi-step forecasting: MTGNN achieves on-par multi-step performance with spatial-temporal graph neural networks without using a pre-defined graph.DCRNN, STGCN, and MRA-BGCN fully rely on pre-defined graphs, while Graph Wavenet uses a self-adaptive adjacency matrix combined with a pre-defined graph.
  • Ablation study: Ablation results show that graph convolution, mix-hop propagation, inception, and curriculum learning contribute to MTGNN’s improved outcomes.Graph convolution enables information flow among isolated but interdependent nodes; mix-hop selects useful information, inception significantly affects RMSE, and curriculum learning increases task difficulty progressively.
  • Graph learning analysis: The uni-directed-A graph-learning method improves marginally over undirected-A and directed-A in MAE and MAPE and is more robust due to lower RMSE.The comparison is conducted on METR-LA validation data averaged over 10 runs.

6 CONCLUSIONS

The paper introduces a graph-based deep learning framework for multivariate time series forecasting that exploits dependencies among multiple series. It reports strong performance across diverse forecasting tasks and positions GNNs as a new approach for handling multivariate time series.

  • The paper introduces a novel framework for multivariate time series forecasting.
  • The approach uses graph-based deep learning to exploit inherent dependency relationships among multiple time series.
  • The method demonstrates superb performance across a variety of multivariate time series forecasting tasks.
  • The framework opens a new door for using GNNs to handle diverse multivariate time series.

A.1 Complexity Analysis

The paper analyzes the time complexity of MTGNN’s main components, showing that its graph learning layer scales quadratically with the number of nodes when feature dimensions are treated as constants.

  • Graph Learning Layer: The graph learning layer has time complexity O(Ns1s2 + N 2s2), where N is the node count and s1 and s2 are input and hidden feature dimensions.The analysis attributes this complexity to pairwise computation of node hidden features.
  • Graph Learning Layer: O(N 2) is the graph learning layer’s time complexity when s1 and s2 are treated as constants.This quadratic scaling follows from the layer’s pairwise node computations.

A.2 Data

The paper summarizes the statistics of its benchmark datasets in Table 1 and introduces dataset details below.

  • Table 1 summarizes statistics for the benchmark datasets, with further details introduced below.

A.2.1 Single-step forecasting.

The study evaluates single-step forecasting on four multivariate time-series datasets, using chronological splits and a 168-step input to predict horizons 3, 6, 12, and 24.

  • Datasets: Four benchmarks cover traffic occupancy, solar generation, electricity consumption, and exchange rates across hundreds of sensors, plants, clients, or countries.The datasets include 862 traffic sensors, 137 photovoltaic plants, 321 electricity clients, and eight countries’ exchange rates.
  • Experimental setup: Each dataset is split chronologically into 60% training, 20% validation, and 20% test data.The split follows.
  • Experimental setup: Models use an input sequence length of 168 and output sequence length of 1 for single-step forecasting.This setup predicts one target future step at a time.
  • Experimental setup: Models are trained independently for target horizons 3, 6, 12, and 24.The horizon identifies the future step being predicted.

A.2.2 Multi-step forecasting.

The study evaluates multi-step traffic forecasting on METR-LA and PEMS-BAY, using chronological splits and 12-step inputs to predict the next 12 steps. Time-of-day features augment inputs, while baselines use road-network distances as predefined graphs.

  • Datasets: METR-LA contains traffic speeds from 207 loop detectors in Los Angeles County, spanning March 2012 to June 2012.The measurements come from the Los Angeles Metropolitan Transportation Authority.
  • Datasets: PEMS-BAY contains traffic speeds from 325 Bay Area sensors, spanning January 2017 to May 2017.The measurements come from California Transportation Agencies (CalTrans).
  • Evaluation setup: The datasets are split chronologically into 70% training, 20% validation, and 10% test sets, with 12 input steps predicting the next 12 future steps.Time of day is included as an auxiliary input feature, and selected baselines use pairwise road-network distances as predefined graph structures.

A.3 Experimental Setup

The model is evaluated over repeated runs and trained with specified optimization, regularization, normalization, dropout, propagation, and architectural settings. Its architecture uses stacked graph and temporal convolution modules with defined channel widths and a 30-epoch training schedule.

  • Evaluation and optimization: The experiment is repeated 10 times, with evaluation metrics reported as averages.
  • Evaluation and optimization: Training uses Adam with gradient clipping at 5, a learning rate of 0.001, and an l2 penalty of 0.0001.
  • Evaluation and optimization: Dropout of 0.3 follows each temporal convolution module, while layer normalization follows each graph convolution module.
  • Architecture: The mix-hop propagation depth is 2 with a retain ratio of 0.05, and training lasts 30 epochs.
  • Architecture: The model contains 5 graph convolution modules and 5 temporal convolution modules, with temporal dilation exponential factor 2 and 16 output channels in both module types.

A.3.1 Single-step forecasting. · A.3.2 Multi-step forecasting. · A.4 Parameter Study

The supplied passages specify the multi-step forecasting configuration and evaluation metrics, and introduce a parameter study of eight MTGNN hyper-parameters. No substantive passage for single-step forecasting is included.

  • A.3.2 Multi-step forecasting.: The multi-step forecasting model uses 3 graph convolution modules and 3 temporal convolution modules with dilation exponential factor 1.
  • A.3.2 Multi-step forecasting.: The model begins with a 1 × 1 convolution having 2 input channels and 32 output channels.
  • A.3.2 Multi-step forecasting.: Graph and temporal convolution modules each have 32 output channels, while skip connection layers have 64 output channels.
  • A.3.2 Multi-step forecasting.: The output module uses 128 output channels in its first layer and 12 output channels in its second layer.
  • A.3.2 Multi-step forecasting.: The configuration uses 20 neighbors per node, 100 training epochs, and batch size 64, with MAE, RMSE, and MAPE as evaluation metrics.
  • A.4 Parameter Study: The parameter study examines eight core hyper-parameters that influence MTGNN model complexity.
  • A.4 Parameter Study: The study varies layers from 1 to 6, filters from 4 to 128, and neighbors from 10 to 60, while identifying saturation rate α as another parameter.
Loading 2005.11650v1…