Autonomous inference of complex network dynamics from incomplete and noisy data

Ting-Ting Gao, Gang YanNat. Comput. sci 2022 · DOI

TL;DR

This paper introduces a novel two-phase approach for autonomously inferring the underlying dynamics of complex networks, even when the data is incomplete and noisy. This method successfully reconstructs the governing equations for various systems, from brain activity to disease spread, offering a powerful tool for understanding intricate real-world phenomena.

What Problem Does This Paper Address?

Understanding complex systems, whether they are biological, social, or technological, often requires deciphering the intricate interplay between their components. While we've made strides in collecting data on these systems (e.g., neuronal activity, human mobility), a significant challenge remains: how to extract the underlying rules that govern their behavior from this data. This is particularly difficult when the data is imperfect – missing information, corrupted measurements, or incomplete network structures. Existing methods struggle with these real-world data limitations, making it hard to reliably infer the complex network dynamics. This paper aims to bridge this gap by providing a robust computational framework that can autonomously infer these dynamics from incomplete and noisy data.

Methods

The core of this work is a "two-phase inference approach."

  • Phase I: Global Regression: This phase begins by constructing extensive libraries of potential elementary functions for both self-dynamics (how a node behaves on its own) and interaction dynamics (how nodes influence each other). The observed time-series data is then used to map these functions into time-varying matrices. A global regression step, employing lasso regression, identifies the most relevant elementary functions that are likely constituents of the true network dynamics. This phase significantly narrows down the search space but doesn't yield a dynamically generative model on its own.
  • Phase II: Local Fine-Tuning: Building on the reduced set of functions from Phase I, this phase refines the model. It uses "topological sampling" to mimic incomplete network structures and a "weighted Akaike's Information Criterion" (wAIC) to determine the minimal set of elementary functions needed for a concise and accurate model. This fine-tuning process leads to the final inferred dynamical equations.

A key innovation is the handling of noisy and incomplete data. The approach incorporates normalization steps in Phase I to mitigate the impact of data scale variations and uses topological sampling in Phase II to account for missing or spurious links in the network structure.

Datasets

The authors validate their approach on a variety of synthetic and empirical datasets:

  • Synthetic Networks: Erdős-Rényi (ER) and scale-free (SF) networks were generated.
  • Empirical Networks:
    • Neuronal networks: C. elegans connectome, Drosophila mushroom-body region.
  • Social networks: Advogato trust network.
  • Technological networks: North-Europe and U.S. power grids.
  • Empirical Data for Dynamics:
    • H1N1, SARS, and COVID-19 spreading data (using worldwide airline network data).

Key Insights and Ideas

  • Robustness to Imperfection: The most striking insight is the method's resilience to real-world data imperfections. It can infer dynamics even with low-resolution data, observational and dynamical noise, and missing or spurious links in the network topology. This is a significant leap beyond methods that require pristine data.
  • Autonomous Inference: The "autonomous" aspect is crucial. The approach doesn't require prior knowledge of the specific functional forms of the dynamics; it discovers them from the data. This is a powerful capability for exploring unknown complex systems.
  • Two-Phase Strategy: The separation into a global regression (Phase I) for broad identification and a local fine-tuning (Phase II) for precision and conciseness is an elegant way to manage the complexity of inferring network dynamics.
  • Generalizability: The successful application to diverse systems – from neuronal firing to epidemic spread – highlights the broad applicability of the framework. The fact that a model inferred from H1N1 data can also capture SARS and COVID-19 dynamics is particularly compelling.

Key Results

  • The approach successfully infers the dynamics of five different systems: Hindmarsh-Rose (HR) and FitzHugh-Nagumo (FHN) neuronal systems, social balance dynamics, Kuramoto dynamics, and coupled heterogeneous Rössler oscillators.
  • Inferred coefficients show high accuracy, with relative errors typically below 3% for well-behaved systems and below 20% for more challenging cases (like heterogeneous dynamics).
  • The inferred dynamical equations exhibit "generative power," meaning they can accurately reproduce the observed system behavior and predict future trajectories.
  • The method demonstrates robustness:
  • It requires only 5-50% of data for inference under low-resolution conditions.
  • It can tolerate dynamical noise up to 15% of the average amplitude and 30-dB observational noise.
  • It can handle up to 25% spurious and 30% missing links in network topology.
  • The inferred model for H1N1 spread, derived from empirical data, accurately captures the early dynamics of SARS and COVID-19, demonstrating its generalizability.

Limitations and Future Work

  • Stochasticity: The authors acknowledge that some real complex systems might exhibit stronger stochasticity than considered, suggesting that extending the approach to handle more complex stochastic differential equations would be beneficial.
  • Discrete/Boolean Dynamics: The current method does not account for discrete or boolean dynamics, or systems with thresholding terms or irregular dynamics.
  • Higher-Order Interactions: The approach primarily focuses on pairwise interactions. The authors note that higher-order couplings can significantly impact dynamics and suggest extending the framework to infer these.
  • Multi-dimensional Observation: For multi-dimensional node activity, experimental access might be limited to a subset of dimensions. Future work could explore how to effectively capture dynamics from such partial observations.

Summary updated

BibTeX
@article{gao2022autonomous,
  author = {Ting-Ting Gao and Gang Yan},
  title = {{Autonomous inference of complex network dynamics from incomplete and noisy data}},
  journal = {Nat. Comput. sci},
  year = {2022},
  doi = {10.1038/s43588-022-00217-0},
}
Figure