Department of Engineering

In many applications we are confronted with the following scenario: we observe snapshots of data describing the state of a system at particular times, and based on these observations we want to infer the (dynamical) interactions between the entities we observe. However, often the number of samples we can obtain from such a process are far too few to identify the network exactly. Can we still reliable infer some aspects of the underlying system?
Motivated by this question we consider the following alternative system identification problem: instead of trying to infer the exact network, we aim to recover a (low-dimensional) statistical model of the network based on the observed signals on the nodes.  More concretely, here we focus on observations that consist of snapshots of a diffusive process that evolves over the unknown network. We model the (unobserved) network as generated from an independent draw from a latent stochastic block model (SBM), and our goal is to infer both the partition of the nodes into blocks, as well as the parameters of this SBM. We present simple spectral algorithms that provably solve the partition and parameter inference problems with high-accuracy.