Predicting the evolution of stationary graph signals

In the problem of modeling and predicting statistical processes, (wide-sense) stationarity is a helpful assumption, that allows us to learn the spectral characteristics of a process using very few samples. Especially for time-series prediction, learning from few samples is crucial, as one needs to estimate future values after only partially observing a single realization of the statistical process. This is the main reason why classical models for estimation and prediction of univariate processes, such as Wiener filters and auto-regressive moving average models (ARMA), rely on stationarity to produce predictions. For multivariate statistical processes, following the same methodology is often problematic, as the number of parameters to be estimated increases quadratically with the number variables, often rendering the problem intractable. A common way to deal with this dimensionality issue is to assume that there is an inherent structure to the process that can be captured by a graph. The graph assumption appears frequently in the machine learning and signal processing literature, and has been shown invaluable for tasks such as clustering [1], [18], low-rank extraction [14], spectral estimation [12], [10] and semi-supervised learning [2], [17]. Nevertheless, despite their promise, so far state-of-the-art graph-based methods predominantly ignore the time-dimension of data. The objective of this paper is to identify multivariate models that exploit the graph structure inherent to the data so as to facilitate the task of prediction.