A State-Dependent Vector Autoregressive Model for Online Forecasting of Time Series on Graphs

Abstract

In complex networks, online forecasting of multivariate time series is challenging due to the complex nonlinear dynamics of nodes’ signals, the need for computational efficiency with streaming data, and inaccurate prior knowledge of the network topology. In particular, a critical factor in these nonlinear dynamics is the coupling between node signals and the underlying network structure, where connection strengths are not static but are dynamically modulated by the signals themselves. To address these issues, we introduce a novel State-Dependent Vector Autoregressive (SDVAR) model. It characterizes the coupling by defining the weights as nonlinear functions of the system’s past signals. For online point forecasting, we develop an efficient algorithm, Kernel-based Online Forecasting with Inexact Proximal Gradient Descent (KOF-IPGD), which employs kernel methods to learn these nonlinear weight functions. To enable computational tractability and efficiency, KOF-IPGD uses random Fourier feature approximation of the kernels and adopts an inexact proximal online gradient descent (IP-OGD) scheme, thereby achieving a lower computational complexity than standard gradient descent. To accommodate the inaccurate prior knowledge of the network, our algorithm learns a sparse and directed graph structure from a given set of candidate edges. Experiments on real-world datasets demonstrate that KOF-IPGD achieves higher prediction accuracy than existing model-based algorithms, matches the performance of state-of-the-art deep learning baselines, and does so with computational efficiency.