Network Reconstruction from Graph-stationary Signals with Hidden Variables

Abstract

Network topology inference from nodal observations has attracted a lot of attention in different fields with a wide variety of applications. While most of the existing works assume that signal observations at all the nodes are available, this is not always the case. We investigate the problem of inferring the topology of an undirected network in the presence of hidden variables, meaning that only a subset of the nodes of the graph is being observed. To address this problem it is assumed that: (i) the nodal signals are stationary in the unknown underlying graph; and (ii) the number of observed nodes is considerably larger than the number of hidden variables. Graph stationarity implies that the covariance of the nodal signals can be expressed as a polynomial of the matrix representation of the whole graph. Rooted in this prior knowledge, the network topology inference is approached as a (low-rank and sparse) optimization problem where we aim to recover the matrix representation of the observed nodes without ignoring the influence of the hidden variables. Different convex relaxations are proposed and robust designs are presented. Finally, numerical experiments using simulations showcase the performance of the developed methods and compare them with existing alternatives.