Duality between predictability and reconstructability in complex systems

The relationship between structure and function is fundamental in complex systems, and important efforts have been invested in developing network models to better understand it. Models of dynamics on networks have been proposed to assess the influence of network structure over temporal evolution, and data-driven models, dimension-reduction techniques, and mean-field frameworks have deepened predictive capabilities, linking dynamics and criticality with network properties such as degree distribution, eigenvalue spectra, and community structure. This motivates the measurement and use of real-world networks to predict complex system behavior. In parallel, dynamics on networks are used for network reconstruction when interaction networks are unavailable, noisy or faulty. A variety of techniques exist: thresholding correlation-based matrices or other measures from time series, Bayesian inference of graphical models, and dynamics-based approaches, with applications in neuroscience, genetics, epidemiology, and finance. Despite their conceptual connection, dynamics prediction and network reconstruction are usually considered separately. Recent works show that deterministic dynamics on a given graph can be predicted accurately with alternative graphs, challenging intuitions about structure-function relationships. Additionally, deep learning on graphs leverages proxy network substrates to enhance predictions, but lacks a rigorous theoretical justification. Consequently, there is a need for a solid, theoretical foundation unifying reconstructability, predictability, and their relationship in networked systems. This work establishes such a framework using information theory, defining mutual information between structure and dynamics to formalize predictability and reconstructability, providing analytical and numerical tools, and identifying conditions leading to a duality between them.

The paper surveys and integrates strands from network science, information theory, and dynamics on networks. Prior work has: (1) characterized random graph ensembles (e.g., configuration model and stochastic block models) via entropy-based methods for null models and community detection; (2) quantified predictability, complexity, and causal emergence in stochastic dynamical systems using information-theoretic measures; (3) shown information transmission peaks near critical points in equilibrium spin systems; and (4) developed diverse network reconstruction techniques, including correlation/thresholding approaches, Bayesian inference of graphical models, and dynamics-based models, widely applied in neuroscience, genetics, epidemiology, and finance. Recent studies report that accurate prediction of deterministic dynamics can be achieved without the true interaction graph, and that graph neural networks benefit from proxy substrates, though without rigorous theoretical underpinning. These observations motivate a unifying information-theoretic framework to connect and compare predictability and reconstructability across settings.

Framework: Consider a random graph G over a support of graphs 𝒢 with prior P(G), and a discrete-time process X=(X_t)_{t=1}^T evolving on G with likelihood P(X|G). Define mutual information I(X;G)=H(X)−H(X|G)=H(G)−H(G|X), and uncertainty coefficients U(X|G)=I(X;G)/H(X) (predictability) and U(G|X)=I(X;G)/H(G) (reconstructability), both in [0,1]. Illustrative interpretations are provided via information diagrams and examples (e.g., spin systems with coupling J). Past-dependent measures: Split X into past X_past of length τ and future X_future of length T−τ. Define partial measures via conditional mutual information I(X_future;G|X_past) and normalized coefficients U(X_future|G;X_past)=I(X_future;G|X_past)/H(X_future|X_past) and U(G|X_future;X_past)=I(X_future;G|X_past)/H(G|X_past). Example: A toy model with two possible graphs g1,g2 and up to three outcomes for X demonstrates regimes of perfect reconstruction with partial predictability (s=0), partial both (s=1), and intermediate dual behavior when 0<s<1. Models of dynamics: The main empirical focus is on binary Markov chains on graphs X=(X_1,…,X_T), with global transition probability P(X_{t+1}|X_t,G)=∏_{i=1}^N [α(m_i,n_i)]^{(1−X_{i,t})X_{i,t+1}} [β(m_i,n_i)]^{X_{i,t}(1−X_{i,t+1})} × complementary factors, where m_i and n_i are active/inactive neighbor counts. Three instances: (i) Glauber dynamics (Ising) with logistic activation/deactivation depending on coupling J; (ii) SIS epidemic with transmission rate λ, recovery β, and small spontaneous activation; (iii) Cowan (neuronal) dynamics with thresholded logistic activation (parameter ν), recovery β, slope α, μ. Graph models: Experiments use Erdős–Rényi graphs (fixed N,E) and configuration model multigraphs with fixed degree sequence k (including real-network degree sequences: Little Rock Lake food web, European airline network, C. elegans neural network). Estimation of information measures: Exact I(X;G) via graph enumeration is feasible only for very small N (e.g., N≤5). For larger systems, the authors introduce: (1) a Monte Carlo estimator using paired samples (g^{(m)},x^{(m)}); (2) a variational mean-field (MF) approximation to the posterior P(G|X) assuming conditional independence of edges, yielding a lower bound on H(G|X) and thus a biased lower bound on I(X;G); (3) MCMC sampling from P(G|X) via Metropolis–Hastings with efficient O(T) updates of likelihood ratios; proposals tailored to Erdős–Rényi (hinge flips) and configuration model (double-edge swaps). Algorithmic performance comparisons: Predictability is evaluated by training graph-independent models (logistic regression, MLP) that map current state X_t to transition probabilities and comparing to true graph-dependent transition probabilities via mean absolute error (MAE). Reconstruction accuracy is assessed by AUC of ROC for methods such as correlation matrices, Granger causality, and transfer entropy, computed from time series generated by the true dynamics on graphs. Theoretical results: Theorem 1 proves a universal T-duality for a broad class of discrete-state Markov chains with positive entropy rate, finite state spaces, and nonzero H(G): as T increases, I(X;G) increases monotonically, implying U(G|X) increases while U(X|G) decreases asymptotically, establishing a region of T-duality. Formal definitions of local and global θ-duality are provided, along with lemmas linking extrema and duality. Criticality analysis: The framework is applied to explore duality with respect to coupling parameters (J, λ, ν) near phase transitions, using both synthetic and real-network degree sequences. Experimental settings include N up to 1000, edges M≈2500, and time series lengths T up to 5000 depending on the dataset.

- Mutual information I(X;G) quantitatively unifies predictability (U(X|G)) and reconstructability (U(G|X)) of dynamics on random graphs; it explains observed performance of both prediction (MAE against graph-independent models) and reconstruction algorithms (AUC for correlation, Granger, transfer entropy). In simulations (e.g., Glauber on Erdős–Rényi with N=100, M=250, T=100), peaks of I(X;G) coincide with best algorithmic performance ranges as coupling J varies. - Normalized uncertainty coefficients differentiate scenarios where the same I(X;G) yields high predictability but low reconstructability (H(G)≫H(X)) or the reverse (H(X)≫H(G)). - Theorem 1 (universality of T-duality): For non-deterministic Markov chains with positive entropy rate and finite state spaces, as T grows, U(G|X) increases (since I(X;G) increases and H(G) is fixed) while U(X|G) decreases (since H(X) grows approximately linearly with T), establishing a T-duality beyond some finite T≥Φ. - Past-dependent measures retain duality: Conditional mutual information I(X_future;G|X_past) yields partial predictability/reconstructability that also exhibit τ-duality for moderate τ (e.g., τ=T/2); for sufficiently large τ, duality may diminish. - Across three binary dynamics (Glauber, SIS, Cowan) on small ER graphs (N=5,E=5), numerical experiments show clear τ-duality between U(G|X) and U(X|G) as T increases, for multiple coupling values. - On configuration-model graphs with synthetic (geometric) and real degree sequences (food web, airline, C. elegans), both U(G|X) and U(X|G) exhibit maxima near but above critical points (J_c, λ_c, ν_c). Shaded regions of coupling parameters display θ-duality; this aligns with prior results that information flow peaks above criticality in spin systems. - Model-specific observations: Glauber is overall less predictable (higher H(X)) due to time reversibility, while SIS and Cowan are nearly unpredictable and unreconstructable below their critical points (dynamics quickly quiescent), with both measures rising near and above criticality. - Simple analytical examples (two-graph, three-outcome system) demonstrate regimes of perfect reconstructability (U(G|X)=1) with imperfect predictability (U(X|G)<1) and intervals where increasing a parameter reduces U(X|G) while increasing U(G|X), illustrating duality. - Practical implication: A trade-off exists—tuning parameters to maximize reconstructability may reduce predictability and vice versa, analogous to an uncertainty trade-off.

The study formalizes the structure–function link in complex systems by treating the interaction graph G as conditioning the dynamics X and quantifying their dependence via mutual information. This directly addresses the dual tasks of predicting future dynamics and reconstructing underlying structure from observations. By introducing uncertainty coefficients, the work clarifies why identical mutual information levels can correspond to very different practical capabilities in prediction versus reconstruction depending on the relative entropies H(X) and H(G). Theoretical results establish that as observational time increases, reconstructability improves while predictability (relative to total dynamical uncertainty) can worsen, resolving apparent paradoxes where long sequences make structure easier to infer yet the dynamics remain intrinsically complex. Numerical experiments across canonical binary processes on both synthetic and real-network structures corroborate the theory and reveal that near criticality, both predictability and reconstructability are maximized and display regions of θ-duality. This aligns with and generalizes previous findings on information flow near critical points, extending them from fixed lattices to heterogeneous random and real networks. Overall, the framework offers principled diagnostics for when and how structural knowledge aids forecasting and when observed dynamics suffice to uncover structure, guiding the design and interpretation of algorithms in applications like neuroscience and epidemiology.

The paper introduces a general information-theoretic framework that unifies predictability and reconstructability for dynamics on random graphs using mutual information and normalized uncertainty coefficients. It provides analytical illustrations, efficient numerical estimators for otherwise intractable mutual information, and rigorous conditions under which predictability and reconstructability are dual with respect to process length (T-duality). Extensive simulations across Glauber, SIS, and Cowan dynamics on synthetic and real-network structures demonstrate duality and show that maxima in predictability and reconstructability occur near critical points. Practically, this implies a trade-off in parameter selection between inference of structure and forecasting of dynamics. Future directions include: extending the framework to adaptive coevolving systems (X↔G), inverse settings where X generates G (e.g., geometric embeddings), developing more efficient and scalable estimators via dimension reduction or approximate master equations, and exploring broader classes of dynamics and network priors to map where dualities arise and how they relate to critical phenomena.

- Computational tractability: Exact evaluation of I(X;G) is feasible only for very small graphs (e.g., N≤5). For larger systems, estimators (e.g., mean-field posterior approximations) are biased lower bounds and can yield negative estimates; MCMC sampling and evidence estimation are computationally costly. - Model assumptions: Many results assume discrete-time, discrete-state Markov chains with finite state spaces and positive entropy rate; universality of T-duality may not hold for non-stationary or deterministic processes. Initial conditions are treated as independent of G. - Specific dynamics and priors: Empirical demonstrations focus on binary processes (Glauber, SIS, Cowan) and specific graph ensembles (Erdős–Rényi, configuration model) and degree sequences; generalization to other dynamics, weighted/directed/temporal networks, and alternative priors may require additional analysis. - Criticality estimation: Phase transition thresholds are estimated via simulations and may vary with finite-size effects and specific network realizations. - SIS variant includes small spontaneous activation, eliminating a true absorbing state; interpretations near criticality are approximate in that regime.