Learning networks via non-invasive observations

Abstract

Learning the underlying structure of a networked dynamic system from observational data is an important problem in many domains, from climate studies to economics. One of the most well-known approaches to this problem is Granger causality, which relies on the premise that data are sampled at a frequency sufficient to capture the cause-to-effect delays, leading to strictly causal observed dynamics. For such strictly causal systems, it has been shown that Granger causality consistently reconstructs the underlying graph of the network. However, in many domains, such as finance, neuroscience or climate studies, the observed dynamics does not follow the strict causality assumption. Thus, many reconstruction methods that try to deal with non-strictly causal dynamics have been developed in the last decade. These methods, however, tend to put limiting assumptions on the graph structures of networks. Furthermore, as we show in this dissertation, the network reconstruction problem is not well-posed in the non-strictly causal case, as in general, it does not admit a unique solution. Thus, many of the existing methods also do not provide any theoretical guarantees for the learned network. In this work, we develop network reconstruction methods for a large class of networks with non-strictly causal dynamics. We provide theoretical guarantees for the reconstruction, while posing no limitations on the underlying structure. We also address the ill-posedness of the network reconstruction problem. The only required assumption in the novel methods is that at least one strictly causal operator is present in every feedback loop. We also provide orientation rules that can orient some of the non-strictly causal links in the network. We test the methods on several benchmark examples, on random networks via simulations, and we also apply them on real-world datasets that show the effectiveness of the proposed algorithms.