An Efficient Algorithm for Learning Locally Stationary Graph Processes

The modeling of graph signals as stochastic processes has led to quite accurate inference algorithms in the recent years. While most methods assume a globally stationary process model that is valid on the whole graph, in many practical settings the statistics of the process may vary locally, providing motivation for locally stationary graph process (LSGP) models. In this work, we address the problem of learning locally stationary graph process models in a computationally efficient way. We build on a recent work that represents local stationarity in terms of a collection of membership functions and spectral kernels, each of which defines a local component of the LSGP. In order to alleviate the complexity of model computation, in this work we adopt a low-dimensional model for the membership functions. We propose an algorithm for learning the model parameters from realizations of the process based on several convex relaxations. The proposed LSGP model is much lighter than that in the previous reference work, regarding the number of model parameters. We show that the proposed method achieves a significant improvement in the computational complexity, while experiments on real data sets demonstrate its competitiveness in terms of signal estimation performance.

I. Introduction

Stochastic graph process models have found widespread usage in the analysis and inference of data sets acquired on irregular topologies. In the recent years, several studies have addressed the modeling of graph signals as stationary graph processes [1]–[3]. While most of the existing works assume that a graph process can be expressed with a single global model that is valid on the whole graph, in practice, the statistics of a process may vary locally on the graph in many applications. For instance, user behaviors may be subject to regional variations in a social network, or data statistics may vary geographically over a sensor network.