  Predicting the evolution of a large system of units using its structure of
interaction is a fundamental problem in complex system theory. And so is the
problem of reconstructing the structure of interaction from temporal
observations. Here, we find an intricate relationship between predictability
and reconstructability using an information-theoretical point of view. We use
the mutual information between a random graph and a stochastic process evolving
on this random graph to quantify their codependence. Then, we show how the
uncertainty coefficients, which are intimately related to that mutual
information, quantify our ability to reconstruct a graph from an observed time
series, and our ability to predict the evolution of a process from the
structure of its interactions. Interestingly, we find that predictability and
reconstructability, even though closely connected by the mutual information,
can behave differently, even in a dual manner. We prove how such duality
universally emerges when changing the number of steps in the process, and
provide numerical evidence of other dualities occurring near the criticality of
multiple different processes evolving on different types of structures.
