Abstract
The forecasting of multi-variate time processes through graph-based techniques has recently been addressed under the graph signal processing (GSP) framework. However, significant challenges arise when each node in a network tracks a vector of quantities rather than a single scalar. This paper introduces a novel framework based on the Product Graph Vector Autoregressive (PG-VAR) model. By leveraging product graphs to model high-dimensional data, we develop a forecasting methodology where the number of parameters is independent of the network size, maintaining linear computational complexity. Numerical results on moving point clouds demonstrate the efficacy of the proposed approach.
Introduction
Forecasting time-varying processes on graphs is a critical task in domains ranging from sensor networks to social media analysis. While Vector Autoregressive (VAR) models are standard for time-series prediction, they scale poorly with network size. Graph-based VAR (G-VAR) models mitigate this by using graph filters to restrict interactions, but they are typically limited to scalar signals per node. In many real-world applications, such as weather monitoring or motion capture, nodes carry multi-dimensional features. This paper addresses the need for a scalable model that captures both spatial dependencies between nodes and structural dependencies between features.
The Curse of Dimensionality in Networked Time Series
In a network with $N$ nodes, a standard VAR model of order $P$ requires $P N^2$ parameters. As $N$ grows, this becomes computationally prohibitive. G-VAR models reduce this complexity by assuming that a node's future state depends only on its neighbors, using graph filters with a small number of coefficients. However, when each node has $F$ features, a naive application of G-VAR either treats features independently (ignoring cross-feature correlations) or treats the entire $NF$ system as a single graph, which reintroduces high parameter counts and computational strain.
Methods: Leveraging Product Graphs
The authors propose the Product Graph VAR (PG-VAR) model. The core idea is to represent the multi-dimensional signal as a single-dimensional signal on a larger "product graph" $\mathcal{G}_\diamond$. This product graph is constructed from two components:
- The Inter-node Graph ($\mathcal{G}$): Represents the physical or logical connections between different nodes in the network.
- The Intra-node Feature Graph ($\mathcal{G}_F$): Represents the relationships between different features at a single node (e.g., the correlation between temperature and humidity).
By using the Cartesian product of these graphs, the PG-VAR model can apply graph filters that account for both spatial and feature-wise proximity. The number of trainable parameters depends only on the filter orders ($K$ and $L$) and the temporal lag ($P$), making it invariant to the number of nodes or features. For cases where the exact relationship between features is unknown, a "Generalized PG-VAR" is proposed to learn the optimal combination directly from data.
Experimental Validation: The Walking Dog Mesh
The model was evaluated on a 3D Walking Dog Mesh dataset, consisting of $N = 251$ spatial points (nodes) moving over $T = 59$ time instants. Each point tracks $F = 3$ features (the $x, y, z$ coordinates). A 10-nearest neighbor (10NN) graph was used to connect the spatial points.
Key results include:
- Scalability: The model maintains high accuracy with a fraction of the parameters required by traditional methods.
- Performance: As training data increases (from 50% to 90%), PG-VAR significantly outperforms standard G-VAR by capturing the inherent correlations between spatial coordinates, 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.
Conclusion
The PG-VAR framework provides a mathematically principled and computationally efficient way to forecast multi-dimensional processes on graphs. By incorporating structural priors through feature graphs, it overcomes the limitations of scalar-based graph models. Future work will focus on applying the generalized model to larger, more diverse datasets and exploring more complex "ad-hoc" structures for forecasting purposes.
Summary updated