6533b7cffe1ef96bd12583d0

RESEARCH PRODUCT

Graph recursive least squares filter for topology inference in causal data processes

subject

description

In this paper, we introduce the concept of recursive least squares graph filters for online topology inference in data networks that are modelled as Causal Graph Processes (CGP). A Causal Graph Process (CGP) is an auto regressive process in the time series associated to different variables, and whose coefficients are the so-called graph filters, which are matrix polynomials with different orders of the graph adjacency matrix. Given the time series of data at different variables, the goal is to estimate these graph filters, hence the associated underlying adjacency matrix. Previously proposed algorithms have focused on a batch approach, assuming implicitly stationarity of the CGP. We propose an online method for a recursive estimation of the adjacency matrix based on the sequential arrival of new data, which we call Graph Recursive Least Squares (GRLS) Filter. In addition to advantages in terms of complexity when compared to a batch approach, this method can also capture the dynamics of the underlying graph process and adapt to new observations. Our experimental results show that the GRLS algorithm has a low mean square error in terms of topology inference, and approaches the error associated to the batch solution rapidly as the number of data samples increases.