State-Space Network Topology Identification from Partial Observations

Identifying how entities are connected by observing the evolution of time series is an important problem is biology, finance, and sensor networks. The problem known as "network topology identification (NTI)" is both challenging to solve and difficult to be characterised theoretically. In our work, we undust some old tools from system identification literature and show how they can be used for NTI. This link allowed us to provide theoretical guarantees on when a topology is identifiable from partial measurements and to develop an algorithm for retreiving it. When the theoretical conditions are met, our proposed algorithm finds the #true network being responsible for the dynamics. 

Abstract. In this work, we explore the state-space formulation of a network process to recover, from partial observations, the underlying network topology that drives its dynamics. To do so, we employ subspace techniques borrowed from system identification literature and extend them to the network topology identification problem. This approach provides a unified view of the traditional network control theory and signal processing on graphs. In addition, it provides theoretical guarantees for the recovery of the topological structure of a deterministic continuous-time linear dynamical system from input-output observations even though the input and state interaction networks might be different. The derived mathematical analysis is accompanied by an algorithm for identifying, from data, a network topology consistent with the dynamics of the system and conforms to the prior information about the underlying structure. The proposed algorithm relies on alternating projections and is provably convergent. Numerical results corroborate the theoretical findings and the applicability of the proposed algorithm.