Score-and-search methods for the recovery of structure in networks of dynamic systems

A relevant problem in many areas of science is to determine the structure of a network by observing its nodes. A desirable property of any network reconstruction techniques is consistency, namely the convergence of the reconstructed network to the actual structure when the time horizon of the observations goes to infinity. Unfortunately, when feedthrough components are present in the network, multiple structures could give rise to the same observations. Hence, in these situations, the best theoretical result that can be achieved is the determination of all the possible structures compatible with what is being observed. There are some results offering such theoretical guarantees, but these methods rely on a large number of statistical tests making their sample complexity relatively large. This article proposes the adoption of reconstruction techniques where, given the observed data, each structure is evaluated according to a score representing the likelihood that such structure is the actual one. Such a technique is proven to have the same consistency properties of state-of-the-art methods based on statistical tests, while numerical experiments show it to have a lower sample complexity.