DIRECTED NETWORK TOPOLOGY INFERENCE VIA GRAPH FILTER IDENTIFICATION
Rasoul Shafipour, Santiago Segarra, Antonio Garcia Marques, Gonzalo Mateos · 2018
We address the problem of inferring a directed network from nodal observations of graph signals generated by linear diffusion dynamics on the sought graph. Observations are modeled as the outputs of a linear graph filter (i.e., a polynomial on a local diffusion graph-shift operator encoding the unknown graph topology), excited with an ensemble of independent graph signals with arbitrarily-correlated nodal components. In this context, we first rely on observations of the output signals along with prior statistical information on the inputs to identify the diffusion filter. Such problem entails solving a system of quadratic matrix equations, which we recast as a smooth quadratic minimization subject to Stiefel manifold constraints. Subsequent identification of the network topology given the graph filter estimate boils down to finding a sparse and structurally admissible shift that commutes with the given filter, thus forcing the latter to be a polynomial in the sought graph-shift operator. Preliminary numerical tests corroborating the effectiveness of the proposed algorithms in recovering synthetic and real-world digraphs are provided.