PaperlayerView exact revision on arXiv

Source-linked AI summary

Causal Network Inference by Optimal Causation Entropy

Jie Sun, Dane Taylor, Erik M. Bollt

arXiv:1401.7574v2cs.IT

TL;DR

Large time-series collections do not eliminate the difficulty of inferring directed network structure from limited knowledge of the generating dynamics. The paper develops causation entropy and an optimal-causation-entropy-guided discovery-and-removal algorithm, which outperforms conditional Granger and transfer-entropy approaches in reported Gaussian-network studies while requiring sample sizes governed more by network characteristics than node count.

  • Problem

    Inferring directed causal network structure from abundant time series remains difficult because the underlying network dynamics are limitedly known and direct links must be separated from indirect influences.

  • Method

    The paper develops causation entropy and proves that, for stationary Markov processes, a target’s causal parents are the unique minimal set maximizing it, enabling greedy discovery-and-removal algorithms.

  • Results

    The oCSE approach consistently outperforms conditional Granger and transfer entropy in Gaussian-process simulations on large random networks.

  • Takeaways & Limitations

    Accurate inference sample requirements appear to depend on link density and information diffusion rate rather than network size, supporting oCSE for large sparse causal networks.

  • Takeaways & Limitations

    Practical oCSE use for general stochastic processes requires non-parametric causation-entropy estimators, and temporal stationarity assumptions may be violated in real applications.

Abstract

from arXiv · show

The broad abundance of time series data, which is in sharp contrast to limited knowledge of the underlying network dynamic processes that produce such observations, calls for a rigorous and efficient method of causal network inference. Here we develop mathematical theory of causation entropy, an information-theoretic statistic designed for model-free causality inference. For stationary Markov processes, we prove that for a given node in the network, its causal parents forms the minimal set of nodes that maximizes causation entropy, a result we refer to as the optimal causation entropy principle. Furthermore, this principle guides us to develop computational and data efficient algorithms for causal network inference based on a two-step discovery and removal algorithm for time series data for a network-couple dynamical system. Validation in terms of analytical and numerical results for Gaussian processes on large random networks highlight that inference by our algorithm outperforms previous leading methods including conditioned Granger causality and transfer entropy. Interestingly, our numerical results suggest that the number of samples required for accurate inference depends strongly on network characteristics such as the density of links and information diffusion rate and not necessarily on the number of nodes.

1. Introduction.

The paper addresses causal network inference from abundant high-dimensional time series when direct network structure is difficult to observe. It develops causation-entropy theory and efficient algorithms to identify direct causal parents while avoiding indirect links.

  • Motivation: Time series measurements are often more accessible than direct network identification in neuronal, genetic, and other complex systems.The paper emphasizes directed cause-and-effect relationships because they can provide deeper insight than nondirected relationships such as correlations.
  • Motivation: Large networks make it difficult to separate direct causal links from indirect and erroneous ones.A node may potentially be influenced by many or all other nodes through network interactions.
  • Related limitations: Transfer entropy can produce systematic multivariate inference errors without proper conditioning, including errors from indirect influences and dominant neighbors.The paper frames causal-parent identification as retaining nodes that directly influence a target while pruning noncausal nodes.
  • Methodological gap: Conditioning is widely used to distinguish direct from indirect relationships, but network inference still needs theoretically sound, reliable, and efficient conditioning strategies.The paper highlights the need to choose which candidate links and conditioning sets to examine.
  • Contribution: The optimal causation entropy principle identifies a target node’s causal parents as the unique minimal set maximizing causation entropy.The paper uses this result to recast causal inference as an optimization problem.
  • Contribution: Greedy algorithms solve the causation-entropy optimization efficiently, and results on Gaussian processes suggest required sample size depends on link density and information diffusion rate rather than node count.The algorithms were evaluated analytically and numerically on trees, loops, and random networks.

2. Stochastic Process and Causal Network Inference.

The paper formulates causal network inference as recovery of the underlying directed topology from node-state samples. Its framework uses stochastic network dynamics in which each node depends on past states of its causal parents, while focusing on topology rather than weights or functional forms.

  • Stochastic process: The framework applies to linear and nonlinear stochastic systems with or without added noise.It is introduced as a general framework for inferring causal networks from high-dimensional time series.
  • Network representation: A directed weighted graph represents the network, with adjacency entry Aij encoding the weight of link j →i.The unweighted adjacency matrix χ0(A) records whether each directed link exists.
  • Causal parents: The causal parents of node i are Ni = {j|Aij≠ 0}, and the causal parents of a node set I are NI = ∪i∈INi.These definitions identify the direct incoming neighbors used by the inference problem.
  • Stochastic process: Each node’s state depends stochastically on the past states of its causal parents, alongside a random fluctuation term.The supplied formulation specifies dependence on past states at time t−1 and includes node-specific noise.
  • Inference target: The broader system-identification problem includes topology, link weights, and functional dependencies, but this paper focuses on topology χ0(A).Topology is treated as the skeleton of the actual network dynamics.
  • Inference target: The input is sampled node-state time series, and the goal is to estimate the underlying causal-network structure.The paper expresses this goal as minimizing the discrepancy between the true and estimated unweighted adjacency matrices.
  • Practical requirements: Hundreds of nodes can coexist with sample sizes too small for reliable estimation of the full joint distribution, motivating model-free, efficient, and data-efficient methods.One stated requirement is avoiding assumptions about the underlying model’s form or parameters.

1. Model-free.

The paper requires a model-free inference method that does not assume the form or parameters of the process generating the observations.

  • Model-free: The method should not rely on assumptions about either the form or parameters of the underlying model.

2. Computational Efficient.

The paper requires a computationally efficient method for causal network inference.

  • Computational Efficient: The method should be computationally efficient.

3. Data Efficient.

The paper establishes assumptions and analytical properties that make causation entropy suitable for data-efficient causal network inference, while identifying challenges from high-dimensional conditioning and subset search.

  • Markov assumptions: Under stationarity and Markov assumptions, each node’s future depends on its causal parents, while other nodes’ past becomes irrelevant when those parents are known.The framework also assumes unique causal parents and observable effects from every causal parent.
  • Information-theoretic measure: Causation entropy is introduced as a model-free information-theoretic statistic for inferring direct causal relationships.It is developed from conditional mutual information and complements transfer entropy in multivariate networks.
  • Information-theoretic measure: In multivariate networks, unconditioned transfer entropy cannot reliably distinguish direct from indirect causality, motivating causation entropy.Without appropriate conditioning, indirect influences and dominant neighbors can produce systematic errors.
  • Analytical properties: Causation entropy obeys redundancy, no-false-positive, true-positive, and decomposition properties under the stated Markov assumptions.These properties characterize when conditioned causation entropy is zero or positive relative to causal parents and conditioning sets.
  • Data efficiency: Large-network inference remains challenging because full conditioning requires high-dimensional estimation, whereas subset-based criteria require combinatorial search.Both difficulties become acute when the network size is large and data are limited.
  • Optimal causation entropy principle: The optimal causation entropy principle identifies a node’s causal parents as the minimal set maximizing causation entropy.Equivalent inference criteria support direct inference and partial conditioning removal, converting network inference into causation-entropy estimation.

Then the set of causal parents satisfies

Under the stated Markov-process conditions, causal parents are characterized through causation entropy: they are retained by positive conditional contributions, while non-causal nodes contribute zero once the parents are included.

  • Then the set of causal parents satisfies: The causal-parent set N_I is the minimal set that maximizes causation entropy to node I.The supplied passages state this characterization through the theorem's proof and its minimax interpretation.
  • Then the set of causal parents satisfies: Brute-force inference enumerates subsets by increasing cardinality until adding any node no longer increases causation entropy.This procedure identifies K = N_I but requires O(n^|N_I|) causation-entropy evaluations.
  • Then the set of causal parents satisfies: The proposed computational strategy avoids brute-force enumeration by first constructing a superset of causal parents and then removing non-causal nodes.The two stages are illustrated as aggregative discovery followed by progressive removal.
  • Then the set of causal parents satisfies: Aggregative discovery adds nodes with the largest positive conditional causation entropy until the remaining candidates have zero maximum contribution.Lemma 2.4 guarantees that the resulting set K_q contains N_I.

Algorithm 2.1 Aggregative Discovery of Causal Nodes

Algorithm 2.1 builds a candidate set by repeatedly selecting the node with maximal conditional causation entropy, stopping when no remaining node contributes positively.

  • Algorithm 2.1 Aggregative Discovery of Causal Nodes: The algorithm initializes K as empty and continues while the maximum conditional causation entropy exceeds zero.At each iteration, it evaluates every node outside K.
  • Algorithm 2.1 Aggregative Discovery of Causal Nodes: Algorithm 2.1 therefore supplies the superset that Algorithm 2.2 prunes to recover the causal-parent set.The two-step relationship is stated explicitly in the algorithmic description.

Algorithm 2.2 Progressive Removal of Non-Causal Nodes

Algorithm 2.2 starts from a superset of causal parents and iteratively deletes nodes whose conditional causation entropy is zero, leaving exactly the causal parents.

  • Algorithm 2.2 Progressive Removal of Non-Causal Nodes: The algorithm takes node set I and candidate set K as input and outputs an inferred causal-parent set.Its loop tests every node j in K.
  • Algorithm 2.2 Progressive Removal of Non-Causal Nodes: After all candidates are processed, the final set equals N_I.Algorithm 2.2 is described as converging to the causal parents, and the two algorithms together infer the entire network.
  • Algorithm 2.2 Progressive Removal of Non-Causal Nodes: Starting from K ⊃ N_I, the removal procedure preserves every causal parent while deleting non-causal nodes.The proof uses positive conditional causation entropy for causal parents and zero conditional causation entropy for non-causal nodes.

3. Application to Gaussian Process: Analytical Results.

Analytical results for Gaussian network processes establish closed-form causation-entropy expressions and show when it agrees with transfer entropy. They also show that appropriate conditioning is essential for distinguishing direct from indirect causal links, especially in directed trees.

  • Analytical framework: The analysis compares causation entropy, transfer entropy, and conditional Granger causality for Gaussian stochastic network dynamics.Causation entropy generalizes transfer entropy and conditional Granger causality under appropriate node and conditioning-set choices.
  • Analytical framework: The Gaussian-process derivation assumes a stable system, with stability defined by spectral radius ρA < 1.Under stability, the covariance series converges and the asymptotic covariance satisfies a discrete Lyapunov equation.
  • Directed linear chain: For directed linear chains, causation entropy equals transfer entropy and is positive exactly when a direct link exists.Both measures increase monotonically with node position toward the chain’s end, and the value depends only on the upstream portion through node j + 1.
  • Directed loop: For directed loops, causation entropy equals transfer entropy, is independent of noise variance, and is positive exactly for direct links.By symmetry, both measures are equal through each link and increase monotonically with link weight w.
  • Directed trees: The tree formulas shown under equal-noise assumptions extend to general link weights and node variances, but the corresponding equations are too cumbersome to list.The stated extension preserves the scope of the analytical result without providing explicit general formulas.
  • Directed trees: For directed trees, unconditioned transfer entropy can infer a superset of actual links, whereas causation entropy with parent selection identifies the correct topology.Selecting the node that maximizes causation entropy for each non-root node and conditioning on it makes causation entropy from other nodes zero.

4. Application to Gaussian Process: Numerical Results.

Numerical experiments on Gaussian processes over large signed Erdős–Rényi networks evaluate oCSE against conditional Granger and transfer entropy. oCSE achieves accurate inference with sample requirements governed more by network density and information diffusion than by network size.

  • Practical considerations: The practical approach combines entropy estimation with a permutation test because finite samples make estimated causation entropy positive even when the null hypothesis holds.The test uses r random temporal permutations and significance threshold θ to assess whether an observed causation entropy is significant.
  • Comparison with prior methods: oCSE maintains near-zero false positive and false negative ratios as network size increases, whereas conditional Granger error rises sharply when network size exceeds sample size.oCSE relies on entropy estimation in dimensions roughly comparable to the number of causal parents, unlike conditional Granger's full n-dimensional estimation.
  • Comparison with prior methods: Unconditioned transfer entropy produces increasing false positives as ρ(A) approaches 1, while oCSE remains nearly accurate by distinguishing indirect from direct causal nodes through conditioning.Both methods have similar false negatives near ρ(A) ≈ 0, where dynamics are dominated by noise.
  • Threshold effects: The false negative ratio converges toward zero as sample size increases, while the false positive ratio saturates near 1 − θ under the permutation test.Higher θ can improve accuracy with sufficient samples, but reliable implementation requires more permutations and therefore greater computational complexity.
  • Network characteristics: For fixed average degree and spectral radius, the critical sample size T* remains mostly constant as network size grows, but increases with average degree and sharply as ρ(A) decreases.The experiments indicate that sample requirements depend on link density and information diffusion rather than directly on network size.

5. Discussion and Conclusion.

The paper develops causation entropy and the oCSE algorithm for inferring causal networks from time series, with theory identifying causal parents and simulations demonstrating efficient inference. It also identifies open challenges involving entropy estimation, stationarity, and the relation between information and physical causality.

  • Causation entropy is a conditional-mutual-information statistic whose maximizing minimal set for a node is exactly its causal parents.The optimal causation entropy principle is proved for general network stochastic processes.
  • The oCSE algorithm uses aggregative discovery and progressive removal to jointly infer each node’s causal parents.This two-step development is identified as the paper’s central algorithmic contribution.
  • oCSE consistently outperforms conditional Granger causality with full conditioning and transfer entropy in Gaussian-process simulations on large random networks.The simulations evaluate both effectiveness and data efficiency.
  • For sparse networks, oCSE keeps entropy-estimation conditioning sets low-dimensional, generally requiring fewer samples and computations.The required sample count depends more on link density and spectral radius than on network size.
  • Practical use remains limited by the need for non-parametric causation-entropy estimators, treatment of nonstationary data, and clarification of information versus physical causality.These are presented as unresolved problems for broader application.

Appendix A. Causal Inference of Finite-Order Markov Processes.

The appendix extends the framework from first-order to finite-order stationary Markov processes by encoding delayed states as variables in an equivalent first-order process. Causal inference then identifies the parents of the variables representing the current states.

  • A finite-order stationary Markov process can be converted into a first-order process by representing variables at different time layers.The transformation applies to any finite order τ.
  • The conditional distribution of X_t given its infinite past equals the distribution conditioned on only the preceding τ states.This equality establishes the first-order Markov property of the transformed process.
  • Inference in the transformed process identifies causal parents of nodes corresponding to Z_t, provided the main framework’s conditions are satisfied.The appendix therefore reduces finite-order causal inference to the first-order results.
  • Figure A.1 illustrates a second-order process on n = 3 nodes and its equivalent first-order representation using multiple node instances.The original process contains links across lags of one or two time steps.
  • When Markov order is unknown, it must be estimated before applying the first-order conversion.The appendix notes that traditional χ2-based order tests are valid only in the infinite-sample limit.

Appendix B. Necessity of the Faithfulness Assumption.

The appendix shows why faithfulness is needed for the theorem’s true-positive claim: jointly causal variables can have zero individual causation entropy while having positive joint causation entropy.

  • The faithfulness assumption is required for Theorem 2.2(c) to guarantee true positives.Without it, causal relationships may not be detectable through individual links.
  • For three Bernoulli variables, Y and Z can jointly cause X even though each individual causation entropy is zero.The example specifies equal probabilities of 0.5 for both binary variables.
  • The joint causation entropy is C_(Y,Z)→X = log 2 > 0, while C_Y→X = C_Z→X = 0.This demonstrates a causal relationship that cannot be decomposed into separate individual effects.
  • Such non-decomposable joint causation is considered rare and is commonly excluded through the faithfulness or stability assumption.The example occurs only under precisely matched discrete probabilities.
Loading 1401.7574v2…