Predicting the future state of a complex system based on its interaction structure is a fundamental challenge. Equally important is reconstructing the interaction structure from temporal observations. This study bridges these two seemingly disparate problems using information theory. Many models exist for predicting system dynamics based on network structure, using techniques like dimension reduction and mean-field approximations. Conversely, network reconstruction methods have been extensively developed to infer interaction networks from time series data. These methods are crucial in various fields, including neuroscience, where brain connectomes are reconstructed from functional time series to subsequently predict brain disorders. However, the relationship between predictability and reconstructability remains poorly understood, despite their interconnected nature. For example, prior research demonstrated that time series generated from a deterministic system on a specific graph can be accurately predicted using vastly different graphs. This highlights the limitations of our intuitive understanding of how structure affects function. Although graph neural networks utilize proxy networks to enhance predictive capabilities, a solid theoretical framework grounding this approach is still lacking. This research addresses this gap by establishing a rigorous information-theoretic framework for understanding predictability, reconstructability and their intricate relationship in complex systems.

The authors review existing literature on network models and dynamics, highlighting the efforts invested in understanding the structure-function relationship. They cite numerous studies using network models to assess the influence of network structure on temporal evolution, as well as data-driven models, dimension-reduction techniques, and mean-field frameworks for improving predictive capabilities. They acknowledge the relationship between dynamics, criticality, and network properties like degree distribution, eigenvalue spectrum, and community structure. The literature on network reconstruction is also reviewed, focusing on techniques like thresholding correlation matrices, Bayesian inference of graphical models, and models of dynamics on networks used for reverse engineering. Applications of these techniques across various disciplines, including neuroscience, genetics, epidemiology, and finance are discussed. The authors specifically note the growing field of network neuroscience, which leverages both network reconstruction and dynamics prediction to understand brain function and dysfunction. Finally, the authors mention existing information theory work applied to networks and dynamics, such as characterizing random graph ensembles, developing network null models, community detection, quantifying predictability and complexity in dynamical systems, and understanding information transmission near critical points.

The authors develop a framework based on information theory to quantify the structure-function relationship in complex systems. They start by defining a random graph G with a probability distribution P(G) representing prior knowledge of the system's structure. A general discrete-time stochastic process X (the dynamics) with T timesteps evolves on a realization of G. The probability of a time series X given G, P(X|G), is a key component. Mutual information I(X; G) quantifies the codependence between X and G, expressed as I(X; G) = H(X) - H(X|G) = H(G) - H(G|X), where H represents entropy (uncertainty). This mutual information is interpreted as a measure of both predictability and reconstructability: the reduction in uncertainty about the dynamics X when the structure G is known, and vice versa. The authors introduce normalized uncertainty coefficients U(X|G) = I(X; G)/H(X) and U(G|X) = I(X; G)/H(G), which represent the relative amounts of information and range from 0 to 1. U(X|G) = 1 implies perfect predictability, while U(G|X) = 1 implies perfect reconstructability. The framework is extended to incorporate past information about X. The paper describes how to evaluate I(X; G), noting its intractability in large systems. A graph enumeration approach is used for small graphs, and a variational mean-field (MF) approximation is proposed for larger systems to bound the mutual information. The MF approximation assumes conditional independence of edges. A Markov chain Monte Carlo (MCMC) algorithm with a Metropolis-Hastings acceptance criterion is used to sample from the posterior distribution. Two types of moves are considered: hinge flips for Erdős-Rényi graphs and double-edge swaps for configuration model graphs. For prediction accuracy assessment, the authors compare the true transition probabilities of the process to those predicted by graph-independent models (logistic regression and MLP) using the mean absolute error (MAE). Reconstruction accuracy is evaluated using the area under the curve (AUC) of the receiver operating characteristic (ROC) curve. The paper formally defines θ-duality, a situation where uncertainty coefficients U(X|G) and U(G|X) vary in opposite directions with respect to a parameter θ. A theorem is presented, proving the universality of T-duality (duality with respect to the number of timesteps T) for Markov chains under certain conditions.

The study uses mutual information as a unifying concept for both predictability and reconstructability in complex systems. It shows how mutual information and uncertainty coefficients can effectively quantify the relationship between the system's structure and its dynamics. The research introduces efficient numerical techniques for evaluating these measures in large systems. A significant finding is the discovery of a duality between predictability and reconstructability. This duality means that these two aspects of a system can show opposing behaviors: increasing one can decrease the other. The paper formally defines and proves the existence of such a duality, particularly when varying the length of the time series (T-duality). This is shown mathematically and then validated through numerical simulations using three distinct binary dynamics: Glauber dynamics, susceptible-infected-susceptible (SIS) dynamics, and Cowan dynamics. These simulations involved both synthetic (Erdős-Rényi, configuration model with geometric degree distribution) and real-world networks (Little Rock Lake food web, European airline network, C. elegans neural network). The study demonstrates that the T-duality persists even when including past information in the analysis. Finally, the research shows numerical evidence suggesting a close relationship between this duality and critical phenomena in complex systems. The predictability and reconstructability coefficients exhibit maxima near (but above) the critical points of the three dynamics. This suggests that the predictability-reconstructability duality might be a universal feature of systems near criticality.

The findings of this study significantly advance our understanding of the relationship between structure and function in complex systems. By unifying the concepts of predictability and reconstructability under the umbrella of information theory, the authors provide a more comprehensive framework for analyzing these systems. The identification of the predictability-reconstructability duality highlights the importance of considering both aspects simultaneously rather than treating them as independent. This duality implies a trade-off: optimizing for reconstructability may compromise predictability, and vice versa. This trade-off has practical implications for network modeling and inference. The observed connection between this duality and critical phenomena in complex systems provides a novel perspective on criticality, suggesting that this duality is a fundamental characteristic near phase transitions. The application of the framework to real-world networks demonstrates the generality and applicability of the theoretical findings. The use of different types of dynamics and networks allows for a robust validation of the observed duality. These findings generalize previous work on spin dynamics and have implications for understanding various systems, including the brain.

This paper presents a novel information-theoretic framework for understanding the relationship between predictability and reconstructability in complex systems. The key contribution is the identification and formalization of a predictability-reconstructability duality, particularly apparent when considering the length of the time series. This duality is proven mathematically and demonstrated through numerical simulations on both synthetic and real-world networks, suggesting a link to critical phenomena. The framework is general and applicable to a wide range of systems and can inform the development of improved network modeling and inference techniques. Future research could explore the duality in more complex systems, delve deeper into its connection with criticality, and investigate its implications for various applications.

The computational cost of evaluating mutual information in large systems is a limitation. The study uses a mean-field approximation to address this, but the accuracy of this approximation depends on the validity of the conditional independence assumption. The universality of the T-duality is proven under specific conditions, and it may not hold for all types of systems or processes. While the study provides compelling evidence for a connection between duality and criticality, further investigation is needed to fully elucidate this relationship. The focus on binary dynamics may also limit the generalizability of the findings to systems with continuous-valued states.