Forecasting Multi-Dimensional Processes Over Graphs

Alberto Natali, Elvin Isufi, Geert Leus

TL;DR

This paper introduces a novel framework for forecasting multi-dimensional time series—where each node in a network tracks multiple variables (like 3D coordinates or various weather metrics)—by leveraging product graphs. By combining the underlying network structure with a "feature graph," the authors develop a Product Graph Vector Autoregressive (PG-VAR) model that significantly reduces parameter overhead while capturing complex inter-feature dependencies.

What Problem Does This Paper Address?

Standard Vector Autoregressive (VAR) models are the "gold standard" for time-series forecasting, but they suffer from the curse of dimensionality: as the number of nodes ($N$) grows, the number of parameters explodes ($PN^2$), making them impossible to train on large networks.

Recent "Graph VAR" (G-VAR) models solved this by using graph filters to restrict interactions to neighboring nodes, making the parameter count independent of the network size. However, G-VAR assumes each node has only one scalar value. In the real world, nodes often have multiple features (e.g., a weather station measuring temperature, humidity, and pressure). Treating these features independently ignores the "hidden" correlations between them, while treating the whole system as one giant graph leads to massive computational costs.

Methods

The authors propose two main advancements:

  1. Product Graph VAR (PG-VAR): Instead of a single graph, they use a product graph ($\mathcal{G}_\diamond = \mathcal{G} \square \mathcal{G}_F$). This combines the "inter-node" graph ($\mathcal{G}$), which represents how different nodes relate, with an "intra-node" feature graph ($\mathcal{G}_F$), which represents how features at a single node relate. This allows the model to forecast future values by looking at what neighbors did and how related features behaved.
  2. Generalized PG-VAR: Recognizing that the "type" of product graph (e.g., Cartesian vs. Kronecker) might not be known beforehand, they propose a generalized filter. This version learns the optimal way to combine the node and feature graphs directly from the data.

Crucially, the number of trainable parameters remains small and independent of the number of nodes ($N$) or features ($F$), relying instead on the filter order ($K$ and $L$).

Datasets

The model was evaluated on a 3D Walking Dog Mesh:

  • Structure: A point cloud representing a moving dog.
  • Dimensions: $N = 251$ spatial points (nodes) over $T = 59$ time instants.
  • Features: $F = 3$ (the $x, y, z$ coordinates for each point).
  • Graph Construction: A 10-nearest neighbor (10NN) graph was used to connect the spatial points.

Key Insights and Ideas

  • Structural Priors Matter: By explicitly modeling the relationship between $x, y,$ and $z$ coordinates through a feature graph, the model gains a "structural prior" that independent G-VAR models lack.
  • Parameter Efficiency: The PG-VAR model uses a number of parameters proportional to the temporal lag ($P$) and graph filter orders ($K, L$), rather than the total number of data points ($NF$). This makes it highly scalable for massive sensor networks.
  • The "Aha" Moment: Product graphs provide a mathematically elegant way to "unroll" a multi-dimensional process into a single-dimensional graph signal on a much larger (but highly structured) graph, allowing existing Graph Signal Processing (GSP) tools to be applied without reinventing the wheel.

Key Results

  • Accuracy vs. Data Volume: When training data is scarce (50-60%), the simpler G-VAR and the proposed PG-VAR perform similarly. However, as more training data becomes available (up to 90%), the PG-VAR significantly outperforms G-VAR, achieving a lower root normalized mean square error (rNMSE).
  • Visual Fidelity: Qualitative results show that the PG-VAR accurately tracks the complex, non-linear motion of the walking dog mesh, matching the ground-truth positions closely.
  • Complexity: The implementation complexity of the Cartesian PG-VAR is comparable to running independent G-VAR models, meaning the accuracy boost comes at a very low computational "tax."

Limitations and Future Work

  • Low-Data Regime: The paper notes that when training data is very limited, the added complexity of the product graph doesn't provide a significant edge over simpler models.
  • Generalized Model Testing: While the authors propose a "Generalized PG-VAR" that learns the graph structure, they did not provide numerical results for it in this specific paper due to the limited time steps in the dog mesh dataset.
  • Future Directions: The authors plan to test the generalized model on larger datasets and explore more complex "ad-hoc" structures for forecasting purposes.

Summary updated

Abstract

The forecasting of multi-variate time processes through graph-based techniques has recently been addressed under the graph signal processing framework. However, problems in the representation and the processing arise when each time series carries a vector of quantities rather than a scalar one. To tackle this issue, we devise a new framework and propose new methodologies based on the graph vector autoregressive model. More explicitly, we leverage product graphs to model the high-dimensional graph data and develop multidimensional graph-based vector autoregressive models to forecast future trends with a number of parameters that is independent of the number of time series and a linear computational complexity. Numerical results demonstrating the prediction of moving point clouds corroborate our findings.
BibTeX
@inproceedings{natali2020forecasting,
  author = {Alberto Natali and Elvin Isufi and Geert Leus},
  title = {{Forecasting Multi-Dimensional Processes Over Graphs}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=OjBLAVCE29},
}

Loading related content...

Figure