PaperlayerView exact revision on arXiv

Source-linked AI summary

Directed Information Graphs

Christopher J. Quinn, Negar Kiyavash, Todd P. Coleman

arXiv:1204.2003v2cs.ITcs.AIstat.ML

TL;DR

The paper addresses how to represent and recover causal influences in networks of stochastic processes from observed activity. It proposes minimal generative model and directed-information graph frameworks, efficient structure-learning algorithms, and estimators with uncertainty guarantees. The methods recover influence structure in synthetic and Twitter data, including news-source effects inferred from tweet times alone.

  • Problem

    The paper addresses the need to identify causal influences and graph structure among interacting stochastic processes from observed network time-series.

  • Method

    It develops minimal generative model and directed-information graphs, efficient structure-learning algorithms, directed-information estimators, confidence intervals, and robust approximations.

  • Results

    The framework identifies which news agencies influenced which Twitter users using activity data, with high precision and without follower relationships or message content.

  • Takeaways & Limitations

    The paper provides a broadly applicable framework combining graphical representations, graph-identification algorithms, data-based estimation procedures, and robustness to unreliable estimates.

Abstract

from arXiv · show

We propose a graphical model for representing networks of stochastic processes, the minimal generative model graph. It is based on reduced factorizations of the joint distribution over time. We show that under appropriate conditions, it is unique and consistent with another type of graphical model, the directed information graph, which is based on a generalization of Granger causality. We demonstrate how directed information quantifies Granger causality in a particular sequential prediction setting. We also develop efficient methods to estimate the topological structure from data that obviate estimating the joint statistics. One algorithm assumes upper-bounds on the degrees and uses the minimal dimension statistics necessary. In the event that the upper-bounds are not valid, the resulting graph is nonetheless an optimal approximation. Another algorithm uses near-minimal dimension statistics when no bounds are known but the distribution satisfies a certain criterion. Analogous to how structure learning algorithms for undirected graphical models use mutual information estimates, these algorithms use directed information estimates. We characterize the sample-complexity of two plug-in directed information estimators and obtain confidence intervals. For the setting when point estimates are unreliable, we propose an algorithm that uses confidence intervals to identify the best approximation that is robust to estimation error. Lastly, we demonstrate the effectiveness of the proposed algorithms through analysis of both synthetic data and real data from the Twitter network. In the latter case, we identify which news sources influence users in the network by merely analyzing tweet times.

I. INTRODUCTION

The paper develops graphical models and structure-learning methods for recovering causal influences among stochastic processes from time-series activity. It connects minimal generative model graphs with directed information and demonstrates the framework on Twitter data.

  • The work develops tools that analyze network time-series to identify underlying causal influences between agents.
  • The proposed minimal generative model graph represents processes as nodes and influences as directed edges, with consistency to directed information graphs under conditions.Directed information graphs are motivated by Granger causality.
  • The paper clarifies how directed information connects with Granger causality beyond strong Granger causality based on conditional independence tests.
  • The paper provides algorithms for exact graph recovery, bounded-degree approximation, robustness to estimation errors, and recovery of strictly causal influences without assuming no instantaneous influence.
  • It characterizes sample complexity and confidence intervals for plug-in estimators of directed information.
  • Using only message times from 16 news corporations and 48 Twitter accounts, the algorithms accurately infer many influence relationships without follower graphs or message content.

3) Structure learning for graphical models for networks of processes:

The paper places its structure-learning approach within work on graphical models for process networks and defines the information-theoretic quantities used to identify directed dependencies. Directed information is asymmetric and quantifies statistical causation in the paper’s framework.

  • 3) Structure learning for graphical models for networks of processes:: Prior work includes exact and heuristic structure-learning methods for graphical models of i.i.d. variables, with directed-information tests analogous to mutual-information tests.
  • 3) Structure learning for graphical models for networks of processes:: Related process-network methods include bounded-degree identification, tree approximations, sparse-network approaches, and adaptive directed-information graph learning.
  • A. Notation and Information-Theoretic Definitions •: The framework considers finite-alphabet, discrete-time random processes over a finite horizon and allows extensions beyond the finite-alphabet presentation.
  • A. Notation and Information-Theoretic Definitions •: Mutual information measures statistical interdependence, whereas directed information measures statistical causation and is generally direction-dependent.

III. MINIMAL GENERATIVE MODELS AND DIRECTED INFORMATION GRAPHS

The paper defines minimal generative model graphs from reduced temporal factorizations and relates them to directed information graphs based on Granger causality. Under positivity and strict causality, the two graph representations are unique and equivalent.

  • Relationship Between Graphical Models: Under positivity and strict causality, the minimal generative model graph exists uniquely and is equivalent to the directed information graph.The paper therefore obtains consistency between the factorization-based and Granger-based representations under Assumption 1.
  • Minimal Generative Models: A minimal generative model selects parent sets with minimal cardinalities that preserve the full dynamics of the joint process distribution.Its graph represents processes as nodes and parent relationships as directed edges.
  • Minimal Generative Models: Minimal generative model graphs may fail to exist or be unique without strict causality and positivity assumptions.The paper gives an example with two equally valid graphs when positivity is violated.
  • Granger Causality and Directed Information: Directed information equals the value of causal side information in sequential prediction under minimal expected log loss.This provides an information-theoretic interpretation of Granger causality for the specified prediction setting.
  • Directed Information Graphs: Directed information graphs encode pairwise causal influence using directed information conditioned on the remaining processes.The directed information graph always exists and is unique, although it can omit indirect relationships and misrepresent network structure.

IV. GRAPHICAL MODEL IDENTIFICATION – GENERAL

This section develops structure-learning algorithms that recover graphical models by testing directed information, with progressively lower-dimensional statistics when sparsity or structural assumptions apply. The guarantees depend on the relevant distributional assumptions and parent-set bounds.

  • General Identification: Structure learning can use either directed-information edge tests or searches for parent sets, avoiding direct estimation of the full network topology.Efficiency is measured by the dimension of the required statistics.
  • Edge Tests: Algorithm 2 recovers the directed information graph under Assumption 1 by testing each pair with all other processes as causal conditioning.It uses the O(m^2) directed-information values in DIDI, and its tests can be executed in parallel.
  • Adaptive Identification: In general, directed informations involving K or fewer processes cannot guarantee recovery when K is the largest parent-set size, motivating tests involving K +2 processes.The limitation arises because lower-order directed-information tests can miss dependencies revealed by conditioning.
  • Adaptive Identification: When in-degrees are unknown, an adaptive algorithm can recover sparse graphs using near-minimal-dimensional statistics by increasing conditioning-set size incrementally.This guarantee requires Assumption 2, which excludes relationships such as exclusive-or and perfect cancellation.

V. GRAPHICAL MODEL IDENTIFICATION – CONSTRAINED TOPOLOGY

The paper develops bounded in-degree algorithms that recover parent sets using directed-information comparisons, and proves optimal-approximation and robust variants when bounds or estimates are unreliable.

  • Bounded in-degree recovery: Algorithm 4 uses directed-information values from K(i)-sized candidate sets to identify each process’s parent set.Candidate sets containing the true parents have maximal influence, and their intersection yields the parent set.
  • Bounded in-degree recovery: Under Assumption 1, Algorithm 4 recovers the directed information graph when |A∗(i)| ≤ K(i) ≤ m −2 for every process.The theorem explicitly requires valid upper bounds that are at least the true in-degrees and exclude the trivial bound m−1.
  • Practical conditions: The algorithms require directed-information calculations or estimates, and the bounded approach depends on assumed in-degree bounds.The paper motivates confidence-interval methods because point estimates may be unavailable or unreliable.
  • Optimal approximation: When in-degree bounds are invalid, the modified algorithm returns an optimal approximation with the specified degree constraints.The approximation independently selects parent sets maximizing the summed directed information along edges.
  • Robust estimation: Algorithm 5 uses confidence intervals to identify the approximation with minimum regret across possible directed-information scenarios.Under Assumption 1, it identifies the robust approximation; with equal-width intervals, Algorithm 4 gives the same result.

VI. ESTIMATION OF DIRECTED INFORMATION

The paper analyzes two finite-alphabet plug-in estimators for directed information, deriving their sample-complexity rates and confidence guarantees under stationary, ergodic, finite-order Markov assumptions.

  • Estimators: The estimation analysis covers empirical-distribution and parametric plug-in estimators for pairwise directed information.The results also generalize to directed information involving sets of K+1 processes.
  • Assumptions: The analysis assumes the network is jointly stationary, ergodic, and finite-order Markov, with pairwise processes also Markov of finite order.These assumptions support convergence and joint estimation of directed-information values.
  • Confidence intervals: Confidence intervals can be constructed for directed information using joint convergence results and estimated covariance matrices.The covariance calculations may be difficult in some cases, motivating practical approximations.
  • Empirical estimator: The empirical estimator has sample-complexity δ = O(n−1/2+ϵ′) for fixed m and n = O(log m) for fixed δ.The result concerns jointly estimating all pairwise directed informations.
  • Parametric estimator: The parametric plug-in estimator has sample-complexity δ = O(n−1/2) for fixed m and n = O(log m) for fixed δ.The result is established under the stated network and parametric regularity assumptions.

VII. SIMULATIONS

Synthetic AR-network experiments evaluate Algorithms 2, 3, and 4 on parent recovery and captured dynamics across network sizes m = 6 and m = 15.

  • Setup: The experiments used 200 trials of 750 time-steps for each network size, with randomly generated Markov order-1 AR processes.Network coefficients were scaled to produce a limiting stationary distribution.
  • Metrics: Performance was measured by correctly identified edges and the directed-information ratio between estimated and true parent sets.Results were averaged over trials with standard error bars.
  • Results: Algorithms 2 and 4 captured almost all dynamics despite misclassifying some edges, suggesting the missed edges were weak influences.The result distinguishes dynamic influence recovery from exact edge recovery.

1) Setup:

Further experiments evaluate optimal and robust approximations on unconstrained AR networks, consensus games, and Twitter activity, showing how approximation quality and inferred influence behave across settings.

  • Optimal approximation: The optimal approximation retained a monotonically increasing proportion of dynamics as the in-degree bound increased.The percentage of correctly identified edges was concave, peaking near the expected number of parents: 2.5 for m = 6 and 7 for m = 15.
  • Optimal approximation: Algorithm 4 does not remove weak edges, and removing parents from an optimal set does not necessarily produce the optimal smaller set.This limits how the optimal approximation can be reduced after selection.
  • Robust approximation: In consensus games, Algorithm 4 performed almost the same as Algorithm 5, with a small gap at n = 10 samples.With n = 10, both were near random guessing, while Algorithm 4 quickly caught up.
  • Twitter analysis: Twitter analysis used tweet times from 16 news corporations and 48 users to infer news-source influence with high precision.The algorithms identified which news agency accounts influenced which user accounts using relevant post activity.
  • Twitter analysis: The Twitter study selected thresholds manually, and performance degraded for lower thresholds.No formal sensitivity analysis was conducted.

C. Estimation

The paper estimates directed information from parametric models with MDL controls, evaluates graph-recovery algorithms against a sparsity-aware baseline, and demonstrates practical utility on Twitter data. The algorithms are conservative but achieve high precision while identifying influential news agencies and users.

  • Directed-information estimation: Directed information is estimated from logistic models of causally conditioned entropy terms, with MDL penalties used to reduce overfitting.The estimate compares H(Y∥Z) and H(Y∥X,Z), using model complexity J log2(n′)/(2n′).
  • Evaluation: The evaluation classifies inferred edges as true or false positives and negatives, then measures accuracy, precision, true positive rate, and false positive rate against a random-guessing baseline.The baseline knows in-degrees but randomly guesses influences.
  • Synthetic-data results: The algorithms performed comparably and significantly better than baseline on ROC performance, although sparse ground truth also gives the baseline high accuracy.The ground-truth graph had average in-degree 1.3 ± 0.5, and the algorithms achieved approximately 95% accuracy.
  • Synthetic-data results: The methods were conservative: they selected few edges, produced very low false-positive rates, and consequently achieved high precision.Algorithm 2 was most conservative, while Algorithm 4 with K =3 was least conservative; precision decreased as false-positive rate increased.
  • Framework contribution: The framework combines graphical representations, multiple graph-identification algorithms, efficient statistics estimation, and robust procedures for unreliable estimates.Some algorithms use prior knowledge to improve efficiency, while others remain useful when estimates are unreliable.
  • Limitations and future directions: The framework assumes a time-invariant graph and stationarity for how process futures depend on others’ pasts, while computational feasibility and small-sample behavior remain open issues.The paper identifies dynamic topologies, data-rich applications, and limited characterization of small-sample estimator performance as future research directions.

APPENDIX A STRICTLY CAUSAL APPROXIMATIONS AND INFORMATION DECOMPOSITION

The appendix analyzes strictly causal approximations and shows how directed information separates strictly causal influence from instantaneous dependence. Under positivity and the stated causality assumptions, directed-information parent sets coincide with the unique minimal generative model.

  • Scope and future directions: The analysis assumes strict causality, while future work includes time-varying graphical models and estimation procedures.The appendix also notes that sampling-rate and observability conditions matter for demonstrating the model’s applicability.
  • Graphical-model equivalence: Under strict causality, directed-information graph parent sets equal the parent sets of the minimal generative model.The result relies on positivity and establishes consistency between the two graphical representations.
  • Graphical-model equivalence: Algorithms 1–4 correctly recover the directed information graph under the appendix’s positivity-based conditions.The proof extends correctness beyond strict causality through the equivalence between pairwise and local Granger-causal Markov properties.
  • Strictly causal approximations: Strictly causal approximation quality depends on how closely the approximation matches the strictly causal marginal of the original distribution.The best approximation for the strictly causal marginal is also the best approximation for the original distribution in the stated sense.
  • Information decomposition: The chain rule decomposes network dependencies into strictly causal and instantaneous correlative components.This extends the two-process mutual-information decomposition to total correlation across the network.

APPENDIX B

This appendix formalizes directed information as the value of causal side information in a specific sequential prediction problem. With probability-measure predictors and logarithmic loss, the optimal expected loss reduction equals causally conditioned directed information, measured in bits.

  • Scope of Granger causality: Conditional dependence alone need not imply predictive usefulness for every sequential prediction setting.The appendix distinguishes dependence-based strong Granger causality from the value of side information under a chosen loss and prediction space.
  • Sequential prediction interpretation: Directed information is precisely the value of causal side information in a specific sequential prediction problem.Different prediction spaces, losses, and temporal aggregation rules yield different formulations of Granger causality.
  • Sequential prediction interpretation: With probability measures as predictors and logarithmic loss, directed information quantifies influence strength through the reduction in prediction loss in bits.This setting parallels Granger’s comparison of predictors with and without side information.
  • Sequential prediction interpretation: Theorem B.1 identifies the optimal predictors as the true conditional distributions and the expected loss reduction as causally conditioned directed information.The result compares predictions using the full past with predictions excluding the past of one process.
  • Graphical-model connection: The directed-information graph’s parent-set characterization is equivalent to the minimal generative model under the stated Markov and causality assumptions.Pairwise and local Granger-causal Markov properties are shown equivalent under Assumption 1.

APPENDIX D

This appendix establishes directed-information inequalities used by structure-learning algorithms and gives a three-process counterexample showing why low-dimensional statistics can be insufficient. The algorithms require statistics involving up to K+2 or K+1 processes, depending on the procedure.

  • Information inequalities: The directed-information chain rule yields monotonicity: adding candidate conditioning processes cannot increase the residual influence measured in the stated decomposition.Equality is characterized by containment of the minimal generative-model parent set.
  • Algorithmic requirements: Algorithms 3 and 4 use directed informations involving up to K+2 and K+1 processes, respectively, where K is the largest parent-set size.These orders determine the statistics required by the two recovery procedures.
  • Algorithmic requirements: No algorithm using directed informations involving K processes or fewer can generally recover the graph.The appendix gives an explicit XOR-based construction establishing this lower bound.
  • Counterexample: In the XOR construction, all one- and two-process directed informations into Z are zero, although the three-process directed information is positive.Thus, pairwise and lower-order tests cannot reveal the three-parent dependence.
  • Counterexample: The example makes Z’s three-parent graph indistinguishable from a zero-parent graph for methods restricted to directed informations of order K = 3 or less.The obstruction arises because dependence appears only jointly across W, X, and Y.

APPENDIX I

This appendix derives concentration and asymptotic results for directed-information estimators. Plug-in estimation error decreases at the usual square-root rate, while maintaining fixed accuracy across more processes requires sample size growing logarithmically with network size.

  • Finite-sample concentration: For every ordered process pair, the directed-information estimation error is bounded by −4|X|2l+1ϵ log ϵ.The bound follows by decomposing directed information into entropies and applying an L1 entropy bound.
  • Finite-sample concentration: As n increases, ϵ decays as n^-1/2, implying δ = O(n^-1/2+ϵ′) for every ϵ′ > 0.Here ϵ measures empirical-probability error and δ measures directed-information estimation error.
  • Finite-sample concentration: For fixed estimation accuracy and error probability, the required sample size grows as log m when the number of processes increases.This dependence appears in both the finite-sample and asymptotic analyses.
  • Asymptotic behavior: The Fisher information covariance simplifies under the finite-alphabet assumptions and the stated regularity conditions.For non-finite alphabets, an additional condition is needed for the corresponding lemma.
  • Asymptotic behavior: The asymptotic directed-information vector has square-root-norm scaling, with δ = O(n^-1/2).The result follows from asymptotic normality after normalization by the covariance structure.

APPENDIX L

The appendix proves that Algorithm 5 can identify robust parent sets independently and returns the individually most robust parent set for each node. The proof relies on rectangularity of the scenario set and shows that the resulting graph is bProb.

  • Theorem 5.2 establishes that, for any scenario, parent sets can be found independently.
  • When the separability equality holds, the parent sets of bProb can be identified independently.This equality follows from the rectangular structure of S and the independent optimization of the terms.
  • Rectangularity of S makes the maximization separable because each term optimizes over disjoint coordinate sets.The values of other coordinates are irrelevant, so the maximization can be moved inside the sum without loss.
  • If j1 = j2, Bj1 is the most robust parent set; if j1 ≠ j2, either Bj1 or Bj2 is most robust.Algorithm 5 selects Bj1 in the first case and uses the corresponding comparison in the second case.
  • Algorithm 5 returns the individually most robust parents for every node Xi and therefore returns bProb.
Loading 1204.2003v2…