Directed Information Graphs

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

Research output: Contribution to journalArticle

Abstract

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 in terms of Kullback-Leibler (KL) divergence. 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. Last, we demonstrate the effectiveness of the proposed algorithms through the 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.

Original languageEnglish (US)
Article number7273888
Pages (from-to)6887-6909
Number of pages23
JournalIEEE Transactions on Information Theory
Volume61
Issue number12
DOIs
StatePublished - Dec 1 2015

Keywords

  • Causality
  • directed information
  • generative models
  • graphical models
  • network inference

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Directed Information Graphs'. Together they form a unique fingerprint.

  • Cite this

    Quinn, C. J., Kiyavash, N., & Coleman, T. P. (2015). Directed Information Graphs. IEEE Transactions on Information Theory, 61(12), 6887-6909. [7273888]. https://doi.org/10.1109/TIT.2015.2478440