Efficient methods to compute optimal tree approximations of directed information graphs

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

Research output: Contribution to journalArticlepeer-review


Recently, directed information graphs have been proposed as concise graphical representations of the statistical dynamics among multiple random processes. A directed edge from one node to another indicates that the past of one random process statistically affects the future of another, given the past of all other processes. When the number of processes is large, computing those conditional dependence tests becomes difficult. Also, when the number of interactions becomes too large, the graph no longer facilitates visual extraction of relevant information for decision-making. This work considers approximating the true joint distribution on multiple random processes by another, whose directed information graph has at most one parent for any node. Under a Kullback-Leibler (KL) divergence minimization criterion, we show that the optimal approximate joint distribution can be obtained by maximizing a sum of directed informations. In particular, each directed information calculation only involves statistics among a pair of processes and can be efficiently estimated and given all pairwise directed informations, an efficient minimum weight spanning directed tree algorithm can be solved to find the best tree. We demonstrate the efficacy of this approach using simulated and experimental data. In both, the approximations preserve the relevant information for decision-making.

Original languageEnglish (US)
Article number6506113
Pages (from-to)3173-3182
Number of pages10
JournalIEEE Transactions on Signal Processing
Issue number12
StatePublished - 2013
Externally publishedYes


  • Directed trees
  • graphical models
  • network approximations

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Efficient methods to compute optimal tree approximations of directed information graphs'. Together they form a unique fingerprint.

Cite this