ABSTRACT

The task of network reconstruction from dynamics, in which edges indicating functional dependence are inferred from time series observed on a set of nodes, has wide reaching applications across various scientific fields. For such dynamics, it is important to incorporate autoregressive dependencies through time delay embeddings, which are difficult to reproduce in traditional inference objectives obtained through explicit statistical generative models. Thus, with its capacity for capturing flexible nonparametric dependencies among time series, transfer entropy has become widely used for network reconstruction when the underlying dynamics are highly nonlinear and autocorrelated, gaining popularity in research focusing on neural, climate, and other complex systems. However, when applied to discrete data, transfer entropy in its standard form exhibits two major shortcomings for network reconstruction: (a) It provides substantially inflated values for completely uncorrelated time series when the data is sparsely sampled; (b) It has no clear means of assessing statistical significance, requiring expensive simulations and the choice of an arbitrary significance level, which should be corrected for multiple comparisons and large sample sizes. I show that these issues are fundamentally a result of treating the observed time series as instances of random variables, and propose utilizing the Minimum Description Length (MDL) principle to develop a combinatorial formulation of transfer entropy in which information is shared only during a single finite transmission event rather than among underlying stochastic processes, alleviating the above issues to nonparametrically reconstruct networks from discrete dynamics. This approach results in a ``reduced'' transfer entropy which is asymptotically equivalent to the standard maximum likelihood plug-in estimator but introduces a finite-size correction that allows for negative transfer entropy values when it is more compressive to transmit a time series’ future values using only its own time delay embedding than to also include another series' time delay embedding. The proposed measure also allows for automatic selection of the optimal temporal lags for constructing the time delay embeddings, and can be generalized to compute a multivariate transfer entropy measure for reconstructing networks with non-redundant information sharing among nodes.