Identifying Undirected Network Structure via Semidefinite Relaxation

Abstract

We address the problem of inferring an undirected graph from nodal observations, which are modeled as non-stationary graph signals generated by local diffusion dynamics on the unknown network. We propose a two-step approach where we first estimate the unknown diffusion (graph) filter, from which we recover the eigenvectors of the so-called graph-shift operator (a matrix representation of the graph). We then estimate the eigenvalues by imposing desirable properties on the graph to be recovered. To carry out the initial system identification step, we assume that second-order statistics of the inputs are available. While such quadratic filter identification problem boils down to a non-convex fourth order polynomial minimization, we propose a semidefinite relaxation with provable performance guarantees. Finally, numerical tests illustrate the use of the proposed algorithm to unveil urban mobility patterns.