Generalized Permutohedra from Probabilistic Graphical Models

Fatemeh Mohammadi, Caroline Uhler, Charles Wang, Josephine Yu

Research output: Contribution to journalArticle (Academic Journal)peer-review

6 Citations (Scopus)
39 Downloads (Pure)


A graphical model encodes conditional independence relations via the Markov properties. For an undirected graph these conditional independence relations can be represented by a simple polytope known as the graph associahedron, which can be constructed as a Minkowski sum of standard simplices. There is an analogous polytope for conditional independence relations coming from a regular Gaussian model, and it can be defined using multiinformation or relative entropy. For directed acyclic graphical models and also for mixed graphical models containing undirected, directed, and bidirected edges, we give a construction of this polytope, up to equivalence of normal fans, as a Minkowski sum of matroid polytopes. Finally, we apply this geometric insight to construct a new ordering-based search algorithm for causal inference via directed acyclic graphical models.
Original languageEnglish
Pages (from-to)64-93
Number of pages30
JournalSIAM Journal on Discrete Mathematics
Issue number1
Early online date2 Jan 2018
Publication statusPublished - 2 Jan 2018


  • graphical model
  • graphoid
  • permutohedron
  • causal inference
  • submodular function
  • matroid
  • entropy


Dive into the research topics of 'Generalized Permutohedra from Probabilistic Graphical Models'. Together they form a unique fingerprint.

Cite this