Provably Correct Reconstruction of Dynamical Networks from Finite, Non-Ideal Data Streams

Many complex phenomena, such as neural interactions in the brain, weather patterns, heat flow in computing systems, and price fluctuations in financial markets, can be viewed as networks of interacting systems. The behavior of these systems is determined by the individual components and how they interact with each other. Often, the interactions are complex enough to preclude reconstruction of the interaction structure from first-principles. In this proposal we propose to develop data-driven approaches to unravel the interaction structure. However, identification of interaction structure from data poses many challenges that include data collected irregularly in time, unmeasured components, temporal patterns (for example, in the weather) that make data correlated across time, and common physical processes driving the behavior of multiple components. The scientific goal of this project is to devise methods that can correctly identify the links in networks in these challenging, real-world scenarios. This project will transform the methodology and understanding of network reconstruction by showing how to discover network structures with realistic data and model conditions, with provable guarantees. Toward reconstruction of interaction structure, this project will provide results on quantitatively characterizing the accuracy of estimating power spectral densities with respect to the data-size, quantitative end-to-end error bounds on the estimation of mutual information rates between time-series, and methods to provably recover exact low-rank/block-sparse decompositions from temporally correlated data, which are of independent interest. The specific innovations for network reconstruction will result in algorithms with rigorous provable correctness guarantees that are applicable in scenarios with finite data size, linear or nonlinear dynamics, data sampled irregularly in time, unmeasured components, spatial dependencies in driving processes, and statistical non-stationarity. The performance of these methods will be examined in simulations and on real-world time-series data instantiated with computational, power, and weather systems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.