GENERALIZED PERMUTOHEDRA
FROM PROBABILISTIC GRAPHICAL MODELS

arXiv:1606.01814v3 [] 7 Dec 2017

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

Abstract. 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.

1. Introduction
A graphical model encodes conditional independence (CI) relations via the Markov properties.
Our main goal is to understand the polyhedral geometry and combinatorics of the collection of
CI relations encoded by a directed acyclic graph (DAG), a directed graph without directed cycles.
It is natural, especially in view of causal inference, to associate to each conditional independence
statement a collection of pairs of adjacent permutations of random variables that are compatible
with that statement. Each of these pairs can be viewed as an edge of a permutohedron or a wall in
the Sn fan, which is the normal fan of the permutohedron. Removing these walls gives a coarsening
of the fan and a natural question is whether this fan is the normal fan of a polytope.
For undirected graphical models, the theory is well understood. The coarsening of the Sn fan
corresponding to the CI relations encoded by an undirected graph is the normal fan of a polytope
called a graph associahedron [MPS+ 09]. These polytopes are Minkowski sums of standard simplices
(MSS), and their facial structure has a nice description via tubings [CD06, PRW08].
In this paper we will show that the coarsened Sn fan arising from any DAG model is the normal
fan of a polytope, which we call a DAG associahedron. We give two concrete constructions of DAG
associahedra, one using multiinformation or relative entropy, and another using matroids. While in
this paper we mainly concentrate on DAG models, we also show that these two constructions can
be extended to more general graphical models that have been studied in the literature containing a
mix of undirected, directed and bidirected edges. In contrast to graph associahedra, we show that
DAG associahedra are in general not simple polytopes and cannot be realized as a Minkowski sum
of standard simplices. Our main motivation for studying DAG associahedra is causal inference:
Given a set of CI relations that are inferred from data, the goal is to estimate the underlying DAG
model, also known as a Bayesian network. A DAG is defined by an ordering of the nodes and an
undirected graph. We show how our geometric insight on DAG associahedra can be applied to
construct a new ordering-based search algorithm for causal inference.
Keywords: Graphical model, graphoid, permutohedron, causal inference, submodular function, matroid, entropy.
MSC(2010): 62H05 (primary); 52B12, 52B40 (secondary).
1

2

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

Other polyhedral approaches for learning Bayesian networks have been described in the literature [CHS17, HLS12, JSGM10, SVH10, SHHL12]. These approaches are based on using integer
programming or linear programming relaxations to maximize a score function over a polytope —
most notably, the Family Variable Polytope (FVP) and the Characteristic Imset Polytope (CIP),
whose vertices correspond to all possible DAGs on n nodes, up to Markov equivalence, respectively.
While the FVP and the CIP are high-dimensional (n(2n−1 − 1) and (2n − n − 1), respectively) and
very complex polytopes (facet description only known for n ≤ 4), we here present a new polyhedral
approach for learning Bayesian networks that is based on DAG associahedra, n − 1-dimensional
polytopes for which we give a concrete construction.
2. Notation and background
In this section, we discuss the relationship between CI relations, the Sn fan, and generalized
permutohedra. We refer the reader to Appendix A for basic definitions concerning polytopes and
fans and to Appendix C for a “dictionary” of concepts.
Let [n] = {1, . . . , n}, and let P be a joint distribution on the random variables Xi for i ∈ [n]. For
notational simplicity we often write I for {Xi : i ∈ I} where I ⊆ [n]. For pairwise disjoint subsets
I, J, K ⊂ [n] we say that I is conditionally independent of J given K under P if the conditional
probability P(A | J, K) does not depend on J for any measurable set A in the sample space of XI .
This statement is denoted by I ⊥
⊥ P J | K or simply I ⊥
⊥ J | K. If K = ∅, we write I ⊥
⊥ J. The set
of CI relations arising from a distribution satisfies the following basic implications, known as the
semigraphoid properties [Pea88]:
(SG1’)
(SG2’)
(SG3’)
(SG4’)

if
if
if
if

I
I
I
I

⊥
⊥J
⊥
⊥J
⊥
⊥J
⊥
⊥J

|L
|L
|L
|L

then J ⊥
⊥ I | L,
and U ⊆ I, then U ⊥
⊥ J | L,
and U ⊆ I, then I \ U ⊥
⊥ J | (U ∪ L),
and I ⊥
⊥ K | J ∪ L, then I ⊥
⊥ (J ∪ K) | L.

In this paper, CI relations can be considered as formal constructs and do not necessarily have
probabilistic interpretation. In addition, we will only work with relations in which I and J are both
singletons, denoted by lowercase letters i, j; see [Mat92]. To simplify notation, we use concatenation
to denote union among subsets and elements of [n], e.g. Lij means L ∪ {i, j}. Then a semigraphoid
can be identified with a set of elementary CI relations
(SG1) if i ⊥
⊥ j | L then j ⊥
⊥ i | L,
(SG2) if i ⊥
⊥ j | L and i ⊥
⊥ k | jL, then i ⊥
⊥ k | L and i ⊥
⊥ j | kL,
for distinct i, j, k ∈ [n] and L ⊆ [n] \ {i, j, k}.
For distributions with strictly positive densities such as regular Gaussian distributions, the intersection axiom holds in addition to the semigraphoid axioms, namely
(INT) if i ⊥
⊥ j | kL and i ⊥
⊥ k | jL, then i ⊥
⊥ j | L and i ⊥
⊥ k | L.
The implications (SG1), (SG2) and (INT) together are known as the graphoid properties. Note
that these implications are not a complete list of CI implications that hold for distributions. In
fact, Studený [Stu92] proved that there exists no finite such characterization.
In [LM07], Lněnička and Matúš defined gaussoids as the graphoids satisfying the following additional axioms:
(G1) if i ⊥
⊥ j | L and i ⊥
⊥ k | L, then i ⊥
⊥ j | kL and i ⊥
⊥ k | jL,
(G2) if i ⊥
⊥ j | L and i ⊥
⊥ j | kL, then i ⊥
⊥ k | L or j ⊥
⊥ k | L.

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

3

The property (G1) is the converse of the intersection axiom, and (G2) is known as weak transitivity.
The CI relations of any regular Gaussian distribution form a gaussoid, but not all gaussoids arise
this way. The set of CI relations coming from any undirected graphical model or a DAG model can
be faithfully represented by a regular Gaussian distribution, hence forming a gaussoid.
We will associate a geometric object to a collection of CI relations as follows: Consider the
hyperplanes in Rn defined by equations of the form xi = xj for all 1 ≤ i < j ≤ n. The complement
of these hyperplanes consists of points in Rn with distinct coordinates, and they are partitioned
into n! connected components corresponding to the permutations of [n] as follows: We identify a
permutation (bijection) π : [n] → [n] with the linear order π(1)  π(2)  · · ·  π(n). To every
vector u ∈ Rn with distinct coordinates, we associate a linear order  on [n] by defining i  j if
and only if ui > uj . For example, the vector u = (25, 4, 16, 9) gives the linear order 1  3  4  2,
which we denote using its descent vector of the form (1|3|4|2). Two points in the complement of
the hyperplanes xi = xj in Rn are in the same connected component if and only if they have the
same descent vector.
The closures of the n! cones and all their faces form a fan, which we will call the Sn fan. It is also
known as the permutohedral fan or the An−1 fan or the braid arrangement fan. Each cone in the
fan contains the line in direction (1, 1, . . . , 1) and is generated by a collection of 0/1 vectors, every
pair of which is nested (when each 0/1 vector is identified with its set of nonzero coordinates).
To each CI relation i ⊥
⊥ j | K, where i, j ∈ [n] distinct and K ⊆ [n] \ {i, j}, we associate pairs of
adjacent permutations of the form
(1)

(a1 | · · · |ak |i|j|b1 | · · · |bn−k−2 ) and (a1 | · · · |ak |j|i|b1 | · · · |bn−k−2 ),

where {a1 , . . . , ak } = K and {b1 , . . . , bn−k−2 } = [n]\(K ∪ {i, j}). We will denote such a pair by
(a1 | · · · |ak |i j|b1 | · · · |bn−k−2 ). For each relation i ⊥
⊥ j | K there are |K|! (n − |K| − 2)! such pairs.
A fan F in Rn is said to be a coarsening of the Sn fan if every cone in the Sn fan is contained in
a cone of F, or equivalently, if every cone of F is a union of some cones of the Sn fan. In particular,
maximal cones of F are unions of maximal cones of the Sn fan, and F can be constructed from the
Sn fan by removing certain walls (codimension one cones). This gives an equivalence relation on
Sn — two permutations are equivalent if and only if their corresponding cones in the Sn fan are
contained in the same cone in F. Such an equivalence relation coming from a fan is called a convex
rank test in [MPS+ 09]. We will see in §8 that for DAG models this equivalence relation coincides
with that coming from the Sparsest Permutation Algorithm of Raskutti and Uhler [RU14].
We identify a coarsening of the Sn fan with the collection of walls which are removed. Each wall
corresponds to an adjacent pair of permutations as in (1), which gives a CI relation i ⊥
⊥ j | {a1 , . . . , ak }.
It was shown in [MPS+ 09, Theorem 6] that a set of walls forms the missing walls in a fan that
coarsens the Sn fan if and only if the corresponding set of CI relations forms a semigraphoid. In
particular, if the wall associated to the pair (1) is not a wall in a coarsened Sn fan F, then any pair
obtained by permuting the a’s among themselves and the b’s among themselves is also not a wall
in F.
A complete fan F in Rn is called polytopal if it is the normal fan of a polytope. The Sn fan itself is
polytopal since it is the normal fan of a permutohedron Pn defined as follows. Let a1 < a2 < · · · < an
be real numbers. Let
Pn = conv{(aσ(1) , aσ(2) , . . . , aσ(n) ) : σ ∈ Sn } ⊆ Rn .
Different choices of ai ’s give different polytopes but with the same normal fan. We associate to
each vertex of Pn a permutation given by its descent vector as explained above, e.g. a point with
coordinates (2, 3, 4, 1) ∈ R4 is associated with its descent vector (3|2|1|4), which is a permutation
and not a point in R4 . Two vertices of Pn are connected by an edge if and only if their descent

4

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

(0, 1, 0)

1⊥
⊥3|2
2⊥
⊥ 3 (2|3|1) (2|1|3) 1 ⊥
⊥2
(3|2|1)

(0, 1, 1)

(1, 1, 0)

(0, 0, 1)

(1, 0, 0)

(1|2|3)

1⊥
⊥ 2 | 3 (3|1|2) (1|3|2) 2 ⊥
⊥3|1
1⊥
⊥3

(1, 0, 1)

(a) The S3 fan modulo the line (1, 1, 1). Maximal cones are labeled with permutations
and the walls are labeled with CI relations.

(b) Permutohedron P3 with outer normals of
its facets.

Figure 1. The permutohedron P3 and its normal S3 -fan. Only the descent vectors,
not coordinate vectors, of the vertices of P3 are shown in (a).
vectors differ by an adjacent transposition as in (1). Thus each CI relation corresponds to a certain
set of edges of Pn .
A generalized permutohedron (see [PRW08]) is a polytope whose normal fan is a coarsening of
the Sn fan. See Figures 1 and 2 for some examples. These polytopes have other equivalent definitions, and are also called M -convex polyhedra or base polyhedra [Mur03, (4.43)]. Their projections
along a coordinate direction give generalized polymatroids [Fuj05, Theorem 3.58]. We use the term
“generalized permutohedron” to highlight the connection to permutations.
Example 2.1 (Undirected graphical models and graph associahedra). Let G be an undirected
graph with node set [n]. We associate a random variable Xi to each node i of the graph. The
joint distribution P of the random vector X = (X1 , . . . , Xn ) satisfies the undirected (global) Markov
property with respect to G if I ⊥
⊥ J | K for all disjoint subsets I, J, K ⊆ [n] such that K separates
I and J in G, i.e. every path between nodes i ∈ I and j ∈ J passes through a node k ∈ K. If a
distribution P satisfies exactly the CI relations corresponding to separations in the graph G, then
P is called faithful or perfectly Markovian with respect to G.
For any undirected graph there exist faithful regular Gaussian distributions; see [Lau96, Chapter 3] for more details. Hence for any undirected graph G the corresponding CI relations defined by
the Markov property satisfy the gaussoid axioms. The coarsened Sn fan associated to the gaussoid
of an undirected graph is the normal fan of a polytope, which can be realized as the Minkowski sum
of standard simplices ∆I = conv{ei : i ∈ I} where I runs over all sets of nodes that induce connected subgraphs of G [MPS+ 09]. These polytopes are called graph associahedra and were studied
in [Dev09, CD06, PRW08].

We will now summarize a characterization of coarsened Sn fans that are polytopal, based
on [MPS+ 09] and [HMS+ 08]. Let 2[n] denote the power set of [n], the set of all subsets of [n].
A function ω : 2[n] → R is called submodular if
(2)

ω(Ki) + ω(Kj) ≥ ω(Kij) + ω(K)

for all K ⊆ [n] and i, j ∈ [n]\K. A submodular function also satisfies ω(A) + ω(B) ≥ ω(A ∪ B) +
ω(A ∩ B) for all A, B ⊆ [n]. Note that a submodular function on 2[n] is an L-convex function on
the unit cube {0, 1}n [Mur03].

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

(a) The standard simplex conv{e1 , e2 , e3 }.

(b) The matroid polytope of U2,3 , conv{e1 +
e2 , e1 + e3 , e2 + e3 }.

5

(c) The DAG associahedron of
1 → 3 ← 2 with CI relation
1 ⊥
⊥ 2. This polytope is not a
Minkowski sum of scaled standard simplices.

Figure 2. Some generalized permutohedra. Compare with the fan in Figure 1.
Definition 2.2. A semigraphoid on [n] is called submodular if there is a submodular function ω on
2[n] with ω(∅) = 0 such that ω(Ki) + ω(Kj) = ω(Kij) + ω(K) if and only if the relation i ⊥
⊥j|K
is in the semigraphoid.
Submodular semigraphoids correspond to structural independence models [Stu05, §5.4.2], which
can be viewed as semigraphoids obtained from supermodular functions, whose negatives are submodular functions.
The following result shows that every submodular function determines a semigraphoid, and the
semigraphoids that arise this way are precisely those corresponding to polytopal coarsenings of the
Sn fan.
Lemma 2.3. A polytope P ⊆ Rn is a generalized permutohedron if and only if there exists a
submodular function ω : 2[n] → R with ω(∅) = 0 such that
X
X
(3)
P = {x ∈ Rn :
xi ≤ ω(I) for each nonempty I ⊆ [n], and
xi = ω([n])}.
i∈I

i∈[n]

A wall in the Sn fan corresponding to i ⊥
⊥ j | K is missing in the normal fan of P defined by ω as
above if and only if ω(Ki) + ω(Kj) = ω(Kij) + ω(K). In particular, a coarsened Sn fan is polytopal
if and only if the corresponding semigraphoid is submodular.
The lemma follows from the conjugacy between L- and M - convex functions and also from [Mur03,
Theorem 4.15]. A part of it appeared in [MPS+ 09, Proposition 12 and Theorem 14]. We provide
a proof in Appendix B, as it is difficult to find a complete proof in the literature.
Remark 2.4. If ω is a submodular function on 2[n] with ω(∅) = 0, then ω 0 : 2[n] → R defined as
ω 0 (S) = ω([n]\S) − ω([n]) is also submodular with ω 0 (∅) = 0. The polytopes P and P 0 , defined by
ω and ω 0 as in (3), are related by −P = P 0 .

Example 2.5. Consider the submodular function ω on 2[n] whose value is 1 on all nonempty sets
and 0 on the empty set. This function is known as the rank function of the uniform rank one
matriod on [n]. The generalized permutohedron defined by this submodular function is a standard
simplex of dimension n − 1 whose outer normal vectors are eI for subsets I of size n − 1. Any set
of n − 2 facet normals spans a wall in the normal fan, with pairs of the form (1), where K = ∅,
corresponding to relations of the form i ⊥
6⊥ j | ∅. See Figures 1 and 2.

This characterization leads to the following questions for any given semigraphoid:

6

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

Question A. Is a given semigraphoid submodular? And if so, can we construct a submodular
function with the desired equalities as in Definition 2.2?
In the following sections we will give a positive answer to these questions for semigraphoids
coming from DAG models.
Rank functions of matroids are submodular functions, so every matroid M on the ground set [n]
gives a semigraphoid on [n] as follows:
i⊥
6⊥ j | K ⇐⇒ rank(Ki) + rank(Kj) > rank(Kij) + rank(K)
Note that since a matroid rank function takes integer values and rank(Aa) ≤ rank(A) + 1 for any
A ⊆ [n] and a ∈ [n], we obtain
(4)

i⊥
6⊥ j | K ⇐⇒ rank(K) + 1 = rank(Ki) = rank(Kj) = rank(Kij).

In this case, the coarsening of the Sn fan is the outer normal fan of the matroid polytope,
which is defined as the convex hull of the indicator functions of the bases of the matroid. For
example, the standard simplex ∆I = conv{ei : i ∈ I} is the matroid polytope of the rank one
matroid in which each element of I forms a base. The intersection of two semigraphoids (as
sets of conditional independence relations) is again a semigraphoid. This intersection operation
corresponds to common refinement, Minkowski sum, and sum, respectively, for fans, polytopes,
and submodular functions.
Question B. Which submodular semigraphoids can be obtained from the sums of rank functions
of matroids (as in Definition 2.2)? Which fans arising from semigraphoids are normal fans of
Minkowski sums of matroid polytopes?
For example, the Minkowski sum of all standard simplices ∆I , for all nonempty subsets I ⊆ [n], is
affinely equivalent to the permutohedron Pn , i.e. they have the same normal fan, which is the entire
Sn fan. This decomposition is not unique, however, e.g. P3 is a hexagon and can be decomposed as
the Minkowski sum of either two triangles or three line segments, all of which are matroid polytopes.
Example 2.6. Let G be the following DAG.
1

2
3

We will see in the next section that the Markov property on G defines a single CI relation, namely
1⊥
⊥ 2. Removing the corresponding wall in the S3 fan gives a fan with 5 maximal cones. Figure 2(c)
depicts a polytope with this normal fan. It is straightforward to check that this fan is not the normal
fan of a Minkowski sum of standard simplices, but it is the normal fan of the Minkowski sum of
the simplex in Figure 2(b) together with two line segments, which are all matroid polytopes.

3. Bayesian networks
Similarly to undirected graphs we can define probabilistic models on DAGs. Such graphical
models are also known as Bayesian networks.
Let G be a DAG with nodes [n]. If there is a directed edge from i to j in G, which we denote by
i → j in G or (i, j) ∈ G, the node i is called a parent of the node j. The set of all parent nodes of
j is denoted by pa(j).
We now review the concept of separation for DAGs. A path in G is an alternating sequence of
nodes and edges, starting and ending at nodes, in which each edge is adjacent in the sequence to

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

7

its two endpoints1. The path may contain repeated edges and nodes. We do not assume that the
direction of the edges is compatible with the ordering of the nodes in the path.
Definition 3.1. Let G be a DAG on [n] and let i, j ∈ [n] and K ⊆ [n] \ {i, j}. A Bayes ball path
from i to j given K in G is a path from i to j in G such that
(1) if a → b → c or a ← b → c or a ← b ← c is on the path, then b ∈
/ K;
(2) if a → b ← c is on the path, then b ∈ K (where a and c need not be distinct). In this case
the node b is called a collider along the path.
See Figures 3 and 5 for examples. Informally we think of a directed edge i → j as pointing down
from i to j. A “Bayes ball” rolls along edges of the DAG. It cannot roll through nodes that are in
K, but it can “bounce off” them by going down, touching K, then going back up along either the
same or a different edge.
For subsets of nodes I, J, K ⊆ [n], we say that I and J are directionally separated or d-separated
by K in G if there is no Bayes-ball path from any element of I to any element of J given K [VP90].
This led to the construction of the Bayes-Ball algorithm [Sha98], an algorithm for determining
d-separation statements. Similarly as for undirected graphs, we can also associate a random vector
with joint distribution P to the nodes of a DAG G. Then P satisfies the directed (global) Markov
property with respect to G if I ⊥
⊥ J | K for all disjoint subsets I, J, K ⊂ V such that K d-separates
I and J in G. A faithful distribution to G, i.e. a distribution that satisfies exactly the CI relations
corresponding to d-separation in G, can be realized by regular Gaussian distributions (see §4).
Hence, for any DAG G the CI relations of the form i ⊥
⊥ j | K, where i and j are d-separated given
K in G, form a gaussoid, which we call a DAG gaussoid.
It is important to note that while the set of separation statements uniquely determines an
undirected graph, this is not the case for d-separation statements for DAGs. Two DAGs are called
Markov equivalent if they imply the same d-separation statements. The Markov equivalence class
is determined by the skeleton of a DAG and its V-structures — triples of nodes (i, j, k) such that
i → k ← j and i, j are not adjacent [AMP97]. An essential graph [AMP97] (also called a completed
partially directed acyclic graph or CPDAG in [Chi02a] and a maximally oriented graph in [Mee95])
is a graph with undirected and directed edges that uniquely represents a Markov equivalence class
of DAGs. It has the same skeleton as the DAGs in the Markov equivalence class and contains a
directed edge i → j if and only if each DAG in the Markov equivalence class contains the directed
edge i → j.
The following is our main result and answers Questions A and B for DAG gaussoids.
Theorem 3.2 (Main Theorem). Every DAG gaussoid is submodular. Equivalently, the associated
coarsening of the Sn fan is the normal fan of a polytope. Moreover, there is a realization of this
polytope as a Minkowski sum of matroid polytopes.
The equivalence of the first two statements follows from Lemma 2.3 above. We call any such polytope resulting from a DAG gaussoid a DAG associahedron. DAG associahedra are uniquely defined
up to equivalence of normal fans, and they only depend on the DAG up to Markov equivalence.
Remark 3.3. Let G be a DAG. The normal fan of the DAG associahedron corresponding to G can
be obtained by coarsening the normal fan of the graph associahedron corresponding to the moral
graph of G — the undirected graph with edges (i, j) if i → j in G, j → i in G, or i → k ← j for
some k in G; see Figure 3.

1This is often called a “walk”, but we prefer to use “path” in order to be consistent with the notion of a “Bayes ball

path”.

8

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

1

2

1

2

3

3

4

4

Figure 3. The DAG G (left) and its moral graph G (right) discussed in Example 3.4.
In the next two sections, we will give two independent proofs for the submodularity of DAG
gaussoids. In the first proof, in §4, we use multiinformation, or relative entropy, to give a formula
for the submodular function and hence a realization of DAG associahedra. However, in general
the constant terms of the inequalities in this construction are not rational. We will discuss some
heuristic methods for finding exact combinatorial information from approximate inequalities. In
the second proof, in §5, we give a realization of DAG associahedra as Minkowski sums of matroid
polytopes, which are integral polytopes. The submodularity of a semigraphoid can be tested using
linear programming [HMS+ 08]. So our theorem states that the linear programs coming from DAG
gaussoids are always feasible, and our proofs give an explicit construction of a feasible solution.
We illustrate the concepts introduced so far with an example of a DAG model on 4 nodes and
describe the corresponding DAG associahedron.
Example 3.4. Consider the DAG G shown in Figure 3. An example of a Bayes ball path in G is
the path from node 1 to 2 given K = {4}, since on the path 1 → 3 → 4 ← 3 ← 2 the node 3 ∈
/K
but 4 ∈ K. The DAG gaussoid corresponding to G consists of the CI relations
1⊥
⊥ 2,

1⊥
⊥ 4 | 3,

2⊥
⊥ 4 | 3,

1⊥
⊥ 4 | {2, 3},

2⊥
⊥ 4 | {1, 3}.

The corresponding edges of the permutohedron are shown in green and blue in Figure 4(a). Since
these CI relations form a semigraphoid, we obtain a coarsening of the Sn fan by removing the edges
(12|3|4), (12|4|3), (3|14|2), (3|24|1), (2|3|14), (3|2|14), (1|3|24) and (3|1|24). The resulting coarsening of the Sn fan obtained by contracting the colored edges in the permutohedron is polytopal.
The convex polytope corresponding to this DAG associahedron is shown in Figure 4(c).
The moral graph G of G is shown in Figure 3 (right). The gaussoid corresponding to G consists
of the CI relations
1⊥
⊥ 4 | 3,

2⊥
⊥ 4 | 3,

1⊥
⊥ 4 | {2, 3},

2⊥
⊥ 4 | {1, 3}.

In general, any DAG gaussoid contains the gaussoid of its moral graph. The edges corresponding
to the CI relations for the moral graph are shown in green in Figure 4(a). By contracting the
green edges in the permutohedron we obtain the graph associahedron corresponding to G shown
in Figure 4(b). By further contracting also the blue edges, we obtain the DAG associahedron
corresponding to G.
As we will see in Proposition 3.6, the DAG associahedron in this example cannot be realized as
a Minkowski sum of simplices. However, we will show in §5 that it can be realized as the following
Minkowski sum of matroid polytopes:
∆13 + ∆23 + ∆34 + ∆134 + ∆234 + conv{e12 , e13 , e23 } + conv{e12 , e13 , e23 , e14 , e24 }.
As we will see in §5, the first three polytopes in the sum correspond to the three edges in the DAG,
the next two correspond to the paths 1 3 4 and 2 3 4, which have no colliders, and the last two
correspond to the paths 1 3 2 (given 3) and 1 3 4 3 2 (given 4) respectively. See Example 5.4.

We end this section with two observations about DAG associahedra. In the following example
we show that unlike graph associahedra, DAG associahedra need not be simple.

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

9

Example 3.5 (A non-simple DAG associahedron). Let G be the following DAG.
1

2

4

3

The corresponding DAG gaussoid consists only of the CI relation 1 ⊥
⊥ 3 | 2, which corresponds to
a single edge 2|13|4 on the permutohedron P4 . Contracting this edge gives a vertex adjacent to
4 edges on a 3-dimensional polyhedron, so the resulting polytope is not simple. In this case, the
combinatorial operation of contracting the edge can be realized geometrically by pushing the two
neighboring square facets toward each other until they meet at a vertex. In other words, the edge
shared by two hexagonal faces contracts to a single vertex.

Furthermore, as already mentioned in Example 3.4, unlike graph associahedra, DAG associahedra
need not be Minkowski sums of standard simplices (MSS) in the sense of [MPS+ 09]. In fact, the
following result shows that a DAG associahedron can be realized as a MSS if and only if the DAG
gaussoid equals the gaussoid of its moral graph, or in other words, if and only if the DAG model
coincides with an undirected graphical model.
Proposition 3.6. The DAG associahedron associated to a DAG G is MSS if and only if G does
not contain any V-structures, i.e. the DAG model coincides with an undirected graphical model.
We saw in Example 2.6 that a V-structure cannot be MSS. We can generalize this example to
the following consequence of [MPS+ 09, Proposition 20]:
Lemma 3.7. If a semigraphoid arises from a Minkowski sum of standard simplices, then for any
i, j ∈ [n] distinct and K ⊆ K 0 ⊆ [n] \ {i, j}, we have
i⊥
⊥ j | K =⇒ i ⊥
⊥ j | K 0.

(a) Permutohedron P4 . The
green edges correspond to CI
relations in the moral graph
G in Example 3.4. The blue
edges correspond to the additional CI relations in G.

(b) The graph associahedron
of the moral graph G obtained by contracting the
green edges.

(c) DAG associahedron for G
obtained by contracting both,
green and blue edges.

Figure 4. The vertices are labeled by descent vectors of permutations, with “|”s
removed. The figures show how the combinatorics of the polytope changes as edges
are contracted, but the polytopes are not drawn to be geometrically correct.

10

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

Proof. For I ⊆ [n], the standard simplex ∆I is the matroid polytope of the rank one matroid on
[n] whose loops are [n]\I. By (4) the semigraphoid corresponding to ∆I contains i ⊥
6⊥ j | K where
i, j ∈ I and K ∩ I = ∅. Taking a Minkowski sum of such simplices corresponds to taking the union
of the associated conditional dependence statements. It follows that i ⊥
6⊥ j | K 0 =⇒ i ⊥
6⊥ j | K for
0
all K ⊆ K ⊆ [n] \ {i, j}.

Using Lemma 3.7 we can now easily prove Proposition 3.6.
Proof of Proposition 3.6. If G does not contain any V-structures, then the corresponding DAG
gaussoid is equivalent to the gaussoid obtained from an undirected graph, namely the skeleton of
G, so it is MSS.
Conversely, suppose that G contains a V-structure i → ` ← j. Let K ⊂ [n] be the set of
nondescendants of i and j in G, i.e. the set of k ∈ [n] \ {i, j} such that there is no directed path
from i to k or from j to k in G. Then the CI relation i ⊥
⊥ j | K is contained in the gaussoid
corresponding to G. However, the CI relation i ⊥
⊥ j | K` is not in the gaussoid of G, since there is
a Bayes ball path from i to j given K` in G. Hence by Lemma 3.7 above, the DAG associahedron
corresponding to G is not MSS.

4. A construction of DAG associahedra from multiinformation
The multiinformation of a probability measure P on [n] is a function mP : 2[n] → [0, ∞] defined
by
mP (S) = H(P|Πi∈S P{i} ),
where H denotes the relative entropy with respect to a product of one-dimensional marginals P{i} .
For the case of most interest to us, when P is a regular Gaussian, there is a simpler formula as
follows. Let P be a regular Gaussian measure on [n] with covariance matrix Σ. Let Γ be the
correlation matrix of P — a symmetric positive definite matrix obtained from Σ by simultaneously
rescaling the rows and columns so that all the diagonal entries are equal to one. In other words,
Γ = D−1/2 ΣD−1/2 where D = diag(Σ). Then we have
(5)

i⊥
⊥ j | K ⇐⇒ rank(ΓKi,Kj ) ≤ |K|

where ΓA,B denotes the submatrix of Γ with rows and columns indexed by A and B, respectively [Sul09]. By [Stu05, Corollary 2.6] the multiinformation mP (A) for A ⊆ [n] is
1
mP (A) = − log det(ΓA,A ).
2
Since Γ is positive definite, all its principal minors det(ΓA,A ) are nonzero. We define det(Γ∅,∅ ) to
be 1. By [Stu05, Corollary 2.2] we have
mP (A) = 0 for all A ⊆ [n], |A| ≤ 1, and
mP (ABC) + mP (C) ≥ mP (AC) + mP (BC) for all A, B, C ⊂ [n]
with equality if and only if A ⊥
⊥ B | C under P.
We summarize this discussion in the following lemma.
Lemma 4.1. If P is a regular Gaussian distribution with correlation matrix Γ, then its semigraphoid
is submodular, with submodular function given by
A 7→ log det(ΓA,A ).

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

11

The submodularity of DAG gaussoids (i.e. the first part of Theorem 3.2) follows from the lemma
above and the fact that any DAG gaussoid has a faithful regular Gaussian realization. See for
example [DSS09, §3.3], where the following construction is described.
Let G be a DAG on the nodes [n]. Assume that the nodes are labeled so that if i → j is an edge
in G, then i < j. Let Λ be an upper-triangular matrix whose entries have the form

if i = j,
 1
−`ij if i → j is an edge in G,
Λi,j =

0
otherwise,
where `ij are real numbers. Let K = ΛΛT and Σ = K −1 . Then K is symmetric positive definite
by construction, and so is Σ. For almost all choices of real numbers `ij (apart from an algebraic
hypersurface), a Gaussian distribution P with covariance matrix Σ is faithful to the DAG gaussoid
of G [URBY13].
In fact, as explained in the following lemma, the inequalities for the desired generalized permutohedron can also be computed directly from minors of K = ΛΛT instead of from the correlation
matrix Γ = D−1/2 Λ−T Λ−1 D−1/2 , where D = diag(Λ−T Λ−1 ). This result simplifies computations
considerably since we do not need to perform any matrix inversion on ΛΛT .
Lemma 4.2. Let K be a positive definite matrix and let ω be the submodular function on 2[n] given
by ω(A) = log det(KA,A ). Let P be the polytope defined as in (3). Then −P is the generalized permutohedron corresponding to the semigraphoid of a regular Gaussian distribution P with covariance
matrix Σ = K −1 .
Proof. The polytope defined by the submodular function A 7→ log det(ΓA,A ) is obtained from the
polytope defined by the submodular function A 7→ log det(ΣA,A ) by translation in each coordinate
direction i by − log Σi,i . Thus these two polytopes have the same normal fans and encode the same
semigraphoids.
For A ⊆ [n] and B = [n]\A, we have (ΣA,A )−1 = KA,A − KA,B (KB,B )−1 KB,A , the Schur
complement. Using the equality det(K) = det(KB,B ) · det(KA,A − KA,B (KB,B )−1 KB,A ), we obtain
log det(ΣA,A ) = − log det(ΣA,A )−1
= − log det(KA,A − KA,B (KB,B )−1 KB,A )
= log det(KB,B ) − log det(K).
Combining this with Remark 2.4, it follows that the polytopes given by A 7→ log det(ΣA,A ) and by
A 7→ log det(KA,A ) are negatives of each other.

In other words, by using K instead of Σ we obtain the dual semigraphoid defined in [MPS+ 09].
In particular, if a semigraphoid has a faithful regular Gaussian distribution, then so does its dual.
Example 4.3 (Multiinformation of the 4-node DAG in Example 3.4). We start by constructing Λ
from G using edge weights 1 (i.e. `ij = 1 if i → j is an edge in G). This choice of edge weights is
sufficiently generic, since it results in a distribution that is faithful to G. We then compute ΛΛT :




1 0 −1 0
2
1 −1 0
 0 1 −1 0 
1
2 −1 0 


Λ=
K = ΛΛT = 
 0 0 1 −1 
−1 −1 2 −1
0 0 0
1
0
0 −1 1

12

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

Taking the log of the principal minors, we arrive at the system of inequalities:
x1
x2
x3
x4
x1 + x2

≤ log 2
≤ log 2
≤ log 2
≤0
≤ log 3

x1 + x3
x1 + x4
x2 + x3
x2 + x4
x3 + x4

≤ log 3
≤ log 2
≤ log 3
≤ log 2
≤0

x1 + x2 + x3
x1 + x2 + x4
x1 + x3 + x4
x2 + x3 + x4
x1 + x2 + x3 + x4

≤ log 4
≤ log 3
≤0
≤0
=0




2 −1
, whose determinant is 3, giving the inequal−1 2
ity x1 + x3 ≤ log 3. These inequalities give a realization of the DAG associahedron in Example 3.4.
This realization is geometrically different from but has the same normal fan as the rational realization obtained by matroid polytopes that we will present in §5.

For instance, the submatrix K{1,3},{1,3} is

As seen in the example above, there is a problem with this construction: The constant terms in
the inequalities will almost never be all rational numbers, making it difficult to obtain exact combinatorial information such as the f -vector and the normal fan. We found that the following heuristic
works well in practice to obtain exact combinatorial information from this polytope description:
First, round off the real numbers in the inequalities to nearby rational numbers (e.g. using 52
bit precision). Then use exact arithmetic to compute the vertices of the polytope defined by these
approximate inequalities. This results in approximations of the true vertices. Then form an approximate slack matrix by evaluating each approximate inequality at each approximate vertex and replace
the entries in the slack matrix by 0 or 1 depending on whether the entry is approximately zero or
not (e.g. by rounding off to 35 bit precision) to obtain an incidence matrix between the vertices and
facets. By eliminating duplicate rows and columns from this matrix we obtain the incidence matrix
of a new polytope, from which its face lattice can be computed. In our simulations, the incidence
matrix obtained this way gives the correct number of vertices and facets of the DAG associahedron,
at least in small dimensions. However, this does not immediately lead to a rational realization of the
polytope. Our code is available on Github at https://github.com/foxflo/DAG-associahedra.
It is possible that in some (or even all) instances we may be able to choose the parameters
`ij ’s in such a way that the logarithms of the principal minors are all rational. However, we do
not know of any systematic way to do this, nor do we know of a systematic way to transform a
nonrational realization into a rational realization. We leave this as an open problem for future
work. However, it is clear that if there is a nonrational realization, then there is also a rational
realization, since a realization is a submodular function that satisfies some of the inequalities in (2)
(those corresponding to the CI relations) at equalities and the rest as strict inequalities, and these
linear constraints have rational coefficients.
To end this section, note that although for this paper it is sufficient to study the Gaussian
setting, submodularity of the multiinformation holds for any probability distribution with finite
multiinformation, which includes for example marginally continuous measures [Stu05]. Hence any
set of CI relations that has a faithful realization by a distribution with finite multiinformation gives
rise to a polytope similar to a DAG associahedron when contracting the edges correspond to CI
relations in the permutohedron.
5. A construction of DAG associahedra as Minkowski sums of matroid polytopes
In the following, we obtain a construction of DAG associahedra as Minkowski sums of matroid
polytopes, resulting in a rational realization of these polytopes. Until now we viewed a semigraphoid as defined by CI relations. However, we can equivalently define a semigraphoid by its

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

13

complementary conditional dependence relations. Minkowski addition of generalized permutohedra translates to taking the union of the corresponding conditional dependence relations, since the
union of normal cones to the edges of the Minkowski sum is the union of normal cones to the edges
in the summand polytopes.2
For every dependence relation i ⊥
6⊥ j | K in the semigraphoid defined by a DAG G, we wish to find
a matroid whose semigraphoid, defined by its rank function as in (4), contains the given relation
and whose dependence relations are all valid for the semigraphoid of the DAG.
We now describe how to construct these matroids. For any conditional dependence relation
i⊥
6⊥ j | K in the semigraphoid defined by a DAG G, there is a Bayes ball path from i to j given K.
We first partition the Bayes ball path into canyons and treks as follows.
Definition 5.1. A trek along a path is a consecutive subpath that does not contain any colliders.
A canyon along a path is a consecutive subpath that is palindromic with exactly one collider in the
middle such that all edges are directed toward the collider. A Bayes ball path is called simple if no
node is repeated except in the same canyon and the maximal canyons are pairwise disjoint.
If we think of the arrows as always pointing down, then a canyon is a path that first goes down
and then backtracks up the same edges to the first node. See Figure 5 for an example. A single
collider is a canyon by itself but not necessarily a maximal one.
The active paths in [Sha98] can be obtained from simple Bayes ball paths by replacing each
canyon with only the top of the canyon, e.g. for the Bayes ball path 1 4 8 4 3 (given {8}) we get an
active path 1 4 3. We prefer to keep the canyons in the path because we will need them for our
matroid construction below.
Lemma 5.2. If there is a Bayes ball path from i to j given K, then there is a simple one that is
an alternating sequence of disjoint treks and canyons, starting and ending with treks.
Proof. Suppose there is a repeated node a. Then we can take the first edge into a and the last edge
out of a. This is allowed except when a would become a collider on the new path and a is not in
the conditioned set K. In this case there must be a descendant of a that is a collider, hence in K,
so we can make a canyon between a and this collider. The same argument shows that we can make
the maximal canyons to be pairwise disjoint and that the end nodes i and j are not in any canyons.
2In other words, the tropical hypersurface of a Minkowski sum of polytopes is the union of the tropical hypersurfaces

of individual polytopes.

2
1

3

5
6

4
7

8
Figure 5. In the DAG, 1 → 4 ← 3 ← 2 → 6 → 7 ← 6 ← 5 → 8 is a Bayes ball
path from 1 to 8 given {4, 7}. The treks and canyons along the path are overlined
and underlined respectively.

14

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

On the simple path, each connected component of the maximal canyons and their adjacent edges
is a trek by definition, since it does not contain any colliders. Note that a single collider is considered
a canyon. There must be at least one collider, hence a canyon, between any two such treks. For
every canyon, we may assume that the node at the top must have two arrows pointing into it on
the path; otherwise we can replace the canyon with just the top of the canyon to get another simple
Bayes Ball path. If there are two consecutive canyons, then the edge between them cannot have
an arrowhead at both canyons, so we can shortcut at least one of them. Thus we may assume that
canyons do not occur next to each other, i.e. any two canyons are separated by a trek.

For example, in Figure 5 the Bayes ball path 1 4 8 7 4 3 from 1 to 3 given {8} has a repeated
node 4, and simply removing the path between the two occurrences of 4 would give 1 4 3, which is
not a Bayes ball path given {8} since the collider 4 is not in the conditioned set {8}. However, 4
has a descendant, 8, which is a collider in the original Bayes Ball path, so we can create a canyon
4 → 8 ← 4 and take the path 1 4 8 4 3 instead.
Construction of a matroid from a simple Bayes ball path.
Let α be a simple Bayes ball path from i to j given K which is an alternating sequence of
treks and canyons as in Lemma 5.2. Suppose we have d + 1 treks t1 , . . . , td+1 and d canyons
c1 , . . . , cd , in the order t1 c1 t2 c2 · · · cd td+1 . For k = 1, . . . , d, let Mi be the rank 2 uniform matroid
on {tk , ck , tk+1 }, i.e. a subset is independent if and only if it has size ≤ 2. It can be represented by
affine independence among three distinct points on an affine line or as linear independence among
three non-parallel vectors in a 2-dimensional vector space or as edges of a triangle.
Let T Cα be the matroid on the set of treks and canyons {t1 , c1 , . . . , td , cd , td+1 }, defined as the
parallel connection or (free and proper) amalgam of these k matroids along the treks [Oxl11, §7,
§11]. The parallel connection of two graphic matroids is obtained by gluing two graphs along an
edge, which corresponds to a trek in our case. The parallel connection of two affine independence
matroids is obtained by placing the affine spaces in a common ambient affine space in such a way
that they only intersect at one point, which corresponds to a trek in our case. The matroid T Cα
is constructed by repeating this operation, which is clearly associative.
Finally the matroid Mα on the node set [n] of the DAG, is defined as follows. Let T Cα0 be the
matroid T Cα with an additional loop element `. Let f : [n] → T Cα0 be a function that sends each
element on the path α to the trek or canyon containing it and all other elements to the loop `.
We say that a subset S ⊆ [n] is independent in the matroid Mα if {f (a) : a ∈ S} is independent
in T Cα0 . In particular, elements in the same trek or the same canyon become parallel elements
(two-element circuits). Two examples of such matroids for different Bayes ball paths are shown in
Figure 6.
A subset S of a matroid is called a flat if rank(S ∪ {a}) > rank(S) for every a ∈
/ S. The
intersection of two flats is a flat. The span or the closure of a set is the smallest flat containing it.
More precisely
span(S) = {a : rank(S ∪ {a}) = rank(S)}.
A subset A ⊆ {t1 , c1 , . . . , td , cd , td+1 } is a flat in T Cα if and only if A ∩ {tk , ck , tk+1 } is a flat for each
k = 1, . . . , d [Oxl11, Proposition 11.4.13]. This can also be checked directly from the realization of
T Cα using affine/linear independence or graphs. Note that a subset of {tk , ck , tk+1 } is a flat if and
only if it has size 6= 2. Flats of Mα are inverse images under f of flats in T Cα0 .
It follows that a subset S ⊆ Mα is a flat if and only if it satisfies all of the following conditions:
(F0) S contains all the loops (the nodes that are not on α)
(F1) If an element of a trek or a canyon is in S, then all the other nodes in the same trek or
canyon are also in S.

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

15

(F2) For each k = 1, . . . , d, if S intersects (thus contains) two out of three treks/canyons in
{tk , ck , tk+1 }, then it also intersects (thus contains) the third.

Recall from §2 that the rank function of a matroid gives a collection of conditional dependence
relations of the form a ⊥
6⊥ b | C, where a, b ∈ [n] and C ⊆ [n] \ {a, b} satisfy the condition (4), namely
(6)

rank(C) + 1 = rank(Ca) = rank(Cab) = rank(Cb)

Lemma 5.3. Let G be a DAG and let α be a simple Bayes ball path from i to j given K in G.
Then the conditional dependence relations of the matroid Mα form a subset of the set of conditional
dependence relations defined by the semigraphoid corresponding to G.
Proof. Suppose the relation a ⊥
6⊥ b | C comes from the matroid Mα . We wish to show that there is
a Bayes ball path in G between a and b given C. The condition (6) can be translated as
(7)

span(C) ( span(Ca) = span(Cab) = span(Cb).

Let us first consider the case when a and b are in the same trek or in the same canyon. Then
C cannot contain any element from the same trek/canyon; otherwise both a and b would be in
span(C), contradicting (7). Any two nodes in the same trek or the same canyon are connected by
a Bayes ball path if no node is conditioned. Thus there is a Bayes ball path between a and b given
C, along α.
Now suppose that a and b are in different treks/canyons. Then condition (7) implies that span(C),
hence C, cannot contain any element in the treks/canyons containing a or b.
We claim that C does not intersect any trek that lies strictly between a and b along α. Otherwise,
if we compute span(Ca) by adding to span(C) nodes along the path starting at a, then the process
would terminate (i.e. the conditions (F0),(F1),(F2) would be satisfied) at or before the trek that
intersects C, before it reaches b. Thus b ∈
/ span(Ca), contradicting the condition span(Ca) =
span(Cb) in (7).
Next we claim that C intersects every canyon that lies strictly between a and b along α. Suppose
C does not intersect a canyon. But we have already shown that C does not intersect the next trek
(which may contain b) after the canyon, on the path from a to b along α. Then as before, the
computation of span(Ca) stops before it reaches b; so again b ∈
/ span(Ca).
Putting everything together we conclude that C intersects all the canyons and none of the treks
that lie strictly between a and b along α. This means that the subpath between a and b along α

1

•

•
4

•

•

5,8

6,7

•
2,3
(a) The matroid corresponding to the Bayes ball
path 1 4 3 2 6 7 6 5 8, which goes from 1 to 8 given
{4, 7}.

1

•

•
4

•

•

5,6,8

7

•
3
(b) The matroid corresponding to the Bayes
ball path 1 4 3 7 6 5 8, which goes from 1 to 8
given {4, 7}. The element 2 is a loop in the
matroid, i.e. {2} is dependent.

Figure 6. Two matroids that are compatible with the DAG in Figure 5.

16

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

forms a Bayes ball path given C in G, and the relation a ⊥
6⊥ b | C is valid for the semigraphoid of
G.

A proof of our main result now follows.
Proof of Theorem 3.2. For every conditional dependence relation i ⊥
6⊥ j | K in the semigraphoid
corresponding to a DAG G, we find a simple Bayes ball path α from i to j given K and construct
a matroid Mα . By Lemma 5.3, all the conditional dependence relations coming from Mα are
among those in the semigraphoid corresponding to G. By taking all the matroids of the form Mα
where α runs over all simple Bayes ball paths in G, we obtain exactly all the conditional dependence
relations that are valid in the semigraphoid of G. Taking the union of all these dependence relations
translates into taking the Minkowski sum of all the corresponding matroid polytopes. Hence, DAG
associahedra are obtained as Minkowski sums of matroid polytopes.

Example 5.4 (Example 3.4 continued). Consider the DAG with 4 nodes from Example 3.4. The
path 1 3 4 3 2 is a Bayes ball path from 1 to 2 given {4}. The corresponding rank 2 matroid is
realized by affine dependence among 3 distinct points in R. For example, we can take the matroid
on the points v1 = 1, v2 = 2, v3 = v4 = 3 on thereal line R under
affine independence. Equivalently,

1 1 1 1
the matroid is given by columns of the matrix
under linear independence. The bases
1 2 3 3
are all pairs {vi , vj } where i 6= j, except the pair {v3 , v4 }. The matroid polytope is a square-based
pyramid, with e1 + e2 as the top of the pyramid.

6. Generalizing to mixed graphs
The MSMP construction generalizes to a much more general setting of semigraphoids arising
from loopless mixed graphs (LMG) introduced by Sadeghi and Lauritzen in [SL14]. We first recall
the definitions. A mixed graph is a graph with three possible types of edges: undirected (i—j),
directed (i ←− j or i −→ j), or bidirected (i ←→ j), which are also called lines, arrows, and arcs
respectively. Multiple types of edges are allowed between any two nodes. A loopless mixed graph
is a mixed graph without a loop, or an edge between a node and itself.
A node j is called an ancestor of a node i, and i is called a descendant of j, if there is a path
i = i0 , i1 , . . . , in = j from i to j in which the edges (ik , ik+1 ) are arrows (directed edges) pointing
from ik to ik+1 for all k = 0, . . . , n − 1. Note that undirected and bidirected edges are not used
in the definition of ancestors.
The set of ancestors of a node i is denoted by an(i). For any set of
[
nodes K, let an(K) =
an(k).
k∈K

For the path ijk (where we may have i = k) the node j is called a collider if the path is one of
i −→ j ←− k, i ←→ j ←− k, or i −→ j ←→ k. Otherwise k is a noncollider.
Let K be a subset of the node set of an LMG. A path is called a Bayes ball path given K
(called an m-connecting path given K in [SL14]) if all its collider nodes are in K ∪ an(K) and all
its noncollider nodes are outside K. We say that i 6⊥
⊥ j | K if there exists a Bayes ball path from i
to j given K. This collection of CI relations forms a graphoid [SL14].
We define treks, canyons, and simple Bayes ball paths in an LMG in exactly the same way as in
Definition 5.1. Only directed edges (arrows) can appear in a canyon, but all three types of edges
are allowed on a trek. A trek or a canyon may consist of only one node, but it may not be empty.
Lemma 6.1. Let i, j be nodes in an LMG and K be a set of nodes such that {i, j} ∩ K = ∅. If
there is a Bayes ball path from i to j given K, then there is a simple one that is a sequence of treks
and canyons, starting and ending with treks, such that

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

17

(1) between any two treks there is at least one canyon
(2) on the edge between a trek and a canyon, there must be an arrowhead at the canyon, and
(3) two consecutive canyons can only be connected by a bidirected edge.
Proof. The existence of a simple path follows from the same argument as in the proof of Lemma 5.2.
On the simple path, each connected component of the complement of maximal canyons (and adjacent edges) is a trek, since it does not contain any collider. Note that a single collider is considered
a canyon. The property (1) follows from the construction of treks as connected components. Consider an edge connecting a trek and a canyon. If there is no arrowhead at the canyon, then the
top of the canyon does not have two arrowheads pointing into it. We can then cut the canyon
short, replacing the canyon with only the top of it, to get another simple Bayes ball path. Thus
property (2) is satisfied. An analogous argument shows that an edge between two canyons must
have arrowheads at both canyons; otherwise we can cut the canyons short. Thus property (3) is
also satisfied.

Now we can describe a generalization of the matroid construction from the previous section.
Construction of a matroid from a Bayes ball path in an LMG. Let α be a simple Bayes ball
path from i to j given K satisfying the conditions from Lemma 6.1. Suppose there are d + 1 treks
t1 , . . . , td+1 on α, in this order. For k = 1, . . . , d, let mk denote the number of canyons between
tk and tk+1 . For each subpath tk ck,1 · · · ck,mk tk+1 of two treks separated by canyons, consider
the uniform matroid Umk +1,mk +2 on {tk , ck,1 , . . . , ck,mk , tk+1 }, which can be represented by affine
independence among mk + 2 general points in Rmk . We then take the parallel connection of these
uniform matroids along the treks. In other words, we place the affine spaces, one for each pair of
treks separated by a sequence of canyons, in a common ambient space so that any two consecutive
ones only meet at one point and they affinely span maximum possible dimension. As before, a
subset is a flat if and only if its intersection with each of the uniform matroids is also a flat.
The matroid Mα on the node set [n] of the LMG is defined as before by replacing each trek
(resp. canyon) with parallel elements corresponding to the nodes in the trek (resp. canyon) and
considering nodes not on α as loops.
A subset S of the node set [n] is a flat in Mα if and only if it satisfies (F0), (F1), and
(F20 ) For each k = 1, . . . , d, if S intersects (thus contains) mk + 1 out of mk + 2 treks/canyons in
{tk , ck,1 , . . . , ck,mk , tk+1 }, then it also intersects (thus contains) the remaining one.

For example, for the Bayes ball path t1 ←→ c1,1 ←→ c1,2 ←− t2 ←→ c2,1 ←→ c2,2 ←− t3 , we can
take the following representation via affine independence in R4 :
trek or canyon
representation
as points in R4

t1 c1,1 c1,2 t2 c2,1 c2,2 t3
0
1
2
3
3
3
3
0
1
4
9
9
9
9
0
0
0
0
1
2
3
0
0
0
0
1
4
9

We have a rank 3 uniform matroid on the first four elements and another rank 3 uniform matroid
on the last four elements, meeting at a point t2 .
Theorem 6.2 (Generalization of Main Theorem). The semigraphoid of any loopless mixed graph
is submodular. The associated coarsening of the Sn -fan is the normal fan of the Minkowski sum of
matroid polytopes corresponding to simple Bayes ball paths satisfying the conditions in Lemma 6.1.

18

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

Proof. The result and the proof of Lemma 5.3 and the Proof of Theorem 3.2 in §5 can be repeated
word for word, with the word DAG replaced by LMG and the condition (F2) replaced by (F20 ). 
7. Relationship among families of semigraphoids
Recall from Lemma 2.3 that submodular functions on 2[n] correspond to polytopal coarsenings
of the Sn fan, and these are exactly the normal fans of generalized permutohedra.
Graph associahedra and DAG associahedra are special classes of generalized permutohedra that
are defined up to equivalence of normal fans. The former can be realized as Minkowski sums of
standard simplices and the latter can be realized as Minkowski sums of matroid polytopes (MSMP).
What additional classes of generalized permutohedra can be realized in this way? Since the standard
simplices are matroid polytopes, MSS polytopes are also MSMP.
Unfortunately, this question seems difficult to answer in general. For n = 3, 4, 5 respectively,
the cone of submodular functions has 5, 37, and 117978 extreme rays of which only 5, 23, and
149, respectively correspond to (connected) matroid polytopes. It suffices to consider connected
matroids because the direct sum of matroids corresponds to the Minkowski sum of the corresponding
matroid polytopes. Thus the matroid polytope of a disconnected matroid, which is the direct sum
of nontrivial matroids, is the Minkowski sum of the matroid polytopes of these direct summands.
Although the structure of these extreme rays is unclear, it seems unlikely due to their sparsity that
many submodular semigraphoids will arise in this way.
Another interesting class of semigraphoids are gaussoids [LM07], an abstraction of regular Gaussian distributions in the language of CI relations; see §2. Since we have seen that probabilistic graphical models can be faithfully realized by regular Gaussian distributions, another natural question
is whether all regular Gaussian models (also called representable gaussoids) or even all gaussoids
are MSMP. Our interest in gaussoids stems from Theorem 8.3, where gaussoids are natural.
Gaussoids appear to be incompatible with the MSMP construction. We have computationally
verified that for 3 ≤ n ≤ 8 no submodular semigraphoid corresponding to a connected matroid on
[n] is a gaussoid. Thus, none of the extreme matroidal rays of the submodular cone are gaussoids.
Conversely, not all gaussoids, in fact not even all representable gaussoids, can be obtained via
MSMP. For example, [DX10, table A.1] lists all Gaussian CI models on four variables (up to
equivalence) and examples 19, 20, 34, 50, 51 are not MSMP. On the other hand, the CI relations
corresponding to graphical models in this list all correspond to generalized permutohedra arising
as MSMP.
In Figure 7 we illustrate the relationship of all the different coarsenings of the Sn fan discussed
in this paper by a Venn diagram. We have seen that undirected graphical models give rise to MSSs,
while DAG models can be realized by MSMPs. In Proposition 3.6 we showed that a DAG model is
MSS if and only if it coincides with an undirected graphical model, i.e. if and if it is a decomposable
model. As we have discussed above, gaussoids are incompatible with the MSMP construction. In
fact, gaussoids are also incompatible with the MSS construction. For example, it is easy to check
that the standard simplex in Figure 2(a) is not a gaussoid. While every representable gaussoid is a
submodular gaussoid as shown in Lemma 4.1, this is not the case for gaussoids. The semigraphoid
studied in [HMS+ 08, Section 3] is a gaussoid that is not submodular.
8. Causal inference
In this section, we describe how DAG associahedra can be used to perform causal inference. The
main problem in causal inference is the following: We obtain data from an unobserved DAG G.
From this data we infer a set of CI relations C. Under the faithfulness assumption, which we will

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

19

gaussoids
representable gaussoids
DAG
models

undirected
graphical
models
MSS

MSMP
submodular semigraphoids
semigraphoids

Figure 7. Venn diagram representing the relationship of all the different coarsenings of the Sn fan discussed in this paper.
assume throughout this section, C coincides with the gaussoid of G. The goal is to learn G from
C. This problem is ill defined since d-separation does not uniquely identify a DAG. So instead the
problem is to learn G up to Markov equivalence, or in other words, to learn from C the essential
graph, which is a partially directed graph with the same skeleton as G where an edge is directed if
and only if it is directed the same way in every DAG in the Markov equivalence class.
A popular algorithm for learning the Markov equivalence class of a DAG is Greedy Equivalence
Search (GES) [Mee97, Chi02b], a greedy algorithm that searches through the space of DAGs by
maximizing a scoring criterion such as the Bayesian Information Criterion (BIC). Under the faithfulness assumption GES is known to be consistent, i.e. it learns the correct essential graph with
probability approaching 1 as the sample size goes to infinity [Mee97, Chi02b]. To reduce computation time, Teyssier and Koller [TK05] suggested to replace the greedy search in DAG space
by a greedy search in the space of all orderings; a scoring criterion such as BIC is optimized by
performing a walk on the edges of the permutohedron. Although no consistency guarantees were
given for this greedy algorithm, simulations suggest that the greedy ordering-based search has a
similar performance and lower computational costs as compared to GES [TK05]. In the following,
we use our geometric insight on DAG associahedra to develop a new greedy ordering-based search
with consistency guarantees.
Let F be a coarsening of the Sn fan. Each cone in F is defined by inequalities of the form xi ≤ xj
and can be labeled a poset on [n]. Then we get a map from permutations of [n] to the set of partial
orders on [n], derived from the map sending a maximal Sn cone to the maximal cone F containing
it. The preimage permutation (total order) is a linear extension of its image partial order. Hence
the maximal cones of the coarsened Sn fan — or the vertices of the generalized permutohedron if
the fan is polytopal — can be labeled by posets so that every permutation is a linear extension of
exactly one of the posets. If two permutations π and τ are mapped to the same partial order, then
we denote this by π ∼ τ .
A semigraphoid C on [n] also gives a map from Sn to the set of DAGs on nodes [n] as described
in [RU14]: To every permutation π we associate a DAG Gπ with
(8)

(πi , πj ) ∈ Gπ ⇐⇒ i < j and πi ⊥
6⊥ πj | {π1 , . . . , πmax(i,j) } \ {πi , πj }.

In other words, the edge directions in the graph must be compatible with the ordering π =
(π1 |π2 | · · · |πn ), and the existence of an edge means that the two nodes are not independent given

20

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

Algorithm 1 Greedy SP algorithm on the permutohedron
Input: A set of CI relations C on n random variables and a starting permutation π ∈ Sn
Output: An essential graph G.
(1) Set t := 0 and π (0) := π.
(2) Set t := t + 1. Randomly select a permutation π (t) that differs from π (t−1) in a single
adjacent transposition such that Gπ(t) is at least as sparse as Gπ(t−1) .
(3) Iterate (2) until convergence to the sparsest Markov equivalence class and output the
corresponding essential graph.
all the nodes that come before them in the ordering. Gπ is also known as a minimal I-map or a
directed independence graph.
We call π a topological ordering of G if any edge (i, j) in G implies that i  j in π. Note that if
the semigraphoid comes from a DAG G and π is a topological ordering of G, then G = Gπ .
In [RU14], it was proposed to use the number of edges of Gπ as a scoring criterion. It was shown
that an algorithm that outputs the Markov equivalence class of Gπ with the fewest number of edges
is consistent, i.e. it outputs the correct Markov equivalence class, under strictly weaker conditions
than faithfulness. A permutation π giving a sparsest DAG is called a sparsest permutation. However
the sparsest permutation (SP) algorithm is problematic from a computational point of view since it
requires searching over all permutations. Instead, similarly as suggested in [TK05], we can perform
a greedy search by traversing the edges of the permutohedron, using the number of edges of Gπ as
a scoring function (see Algorithm 1).
Algorithm 1 requires searching through neighboring permutations even when they give rise to
the same DAG. For example, the neighboring permutations π = (1|2|3|4) and τ = (2|1|3|4) in
Example 3.4 give rise to the same DAG Gπ = Gτ = G shown in Figure 3 (left). We next discuss how
to reduce the search space and hence computation time by performing the greedy search on the
smaller DAG associahedron instead of the full permutohedron. The difficulty is that this needs to
be done without having access to the DAG G on which the DAG associahedron is based. In order
to do this, we give a description of the vertices and edges of a DAG associahedron in terms of the
DAGs Gπ that are associated to its vertices.
Theorem 8.1. For any fixed graphoid and two permutations π and τ , we have
π ∼ τ ⇐⇒ Gπ = Gτ .
Moreover, the equivalence class of π consists of all topological orderings of Gπ .
Proof. Suppose π ∼ τ . We may assume that
π = (a1 | · · · |ak |i|j|b1 | . . . |bn−k−2 )

and τ = (a1 | · · · |ak |j|i|b1 | . . . |bn−k−2 ),

where i ⊥
⊥ j | {a1 , . . . , ak }, since any pair of equivalent permutations is connected by a sequence of
such pairs. Now let us compare the edges in Gπ and Gτ . There is no edge between i and j in either
DAG. Between any two nodes in [n]\{i, j}, it is clear that Gπ and Gτ coincide.
Now suppose that (a` , j) is not an edge in Gπ for some `. Let K = {a1 , . . . , ak }\{a` }. Then by
applying the intersection property (INT) of graphoids from §2 we obtain
(INT)

i⊥
⊥ j | Ka` and j ⊥
⊥ a` | Ki =⇒ j ⊥
⊥ a` | K.
Thus (a` , j) is not an edge in Gτ either. Similarly if (a` , j) is not an edge in Gτ , then applying the
semigraphoid property (SG2) we obtain
(SG2)

j⊥
⊥ a` | K and i ⊥
⊥ j | K ∪ {a` } =⇒ j ⊥
⊥ a` | Ki.

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

1 11 1

2 22 2 1 11 1

2 22 2

3 33 3

4 44 4

4 44 4

3 33 3

1 11 1

2 22 2 1 11 1

1 11 1

2 22 2

3 33 3

3 33 3

3 3
1 1

2 22 2

4 44 4 1 11 1

4 424 42

2 22 21 11 1

2 22 2 1 11 1

2 212 21

21

3 3
4 4

2 2

4 4

1 1
2 2

1 1

2 2

3 33 3

3 33 3

3 33 3

3 33 3

3 3

3 3

4 44 4

4 44 4

4 44 4

4 44 4

4 4

4 4

Figure 8. Posets and their corresponding DAGs representing the new (compared
to the permutohedron) vertices of the DAG associahedron discussed in Examples 3.4
and 8.2.
Thus (a` , j) is not an edge in Gπ either.
We can check in a similar fashion by setting K = {a1 , . . . , ak } that for any b` ∈ [n]\({a1 , . . . , ak }∪
{i, j}) the edge (j, b` ) is in Gπ if and only if it is in Gτ . The same claims also hold for i by switching
π and τ .
For the converse, suppose τ is a topological ordering of Gπ . In particular, this holds when Gπ = Gτ .
We wish to prove that π ∼ τ . Without loss of generality we may assume that τ = (1|2| · · · |n).
Let π = (π1 |π2 | · · · |πn ). If π 6= τ , then there is an i ∈ [n − 1] such that πi > πi+1 . Since πi and
πi+1 appear with opposite orders in π and τ and τ is a topological ordering of Gπ , there is no edge
between πi and πi+1 in Gπ . By construction of Gπ , we must have πi ⊥
⊥ πi+1 | {π1 , . . . , πi−1 } in the
graphoid. Let π 0 = (π1 | · · · |πi−1 |πi+1 |πi |πi+2 | · · · |πn ). Then π 0 ∼ π by definition, so Gπ0 = Gπ as
shown above. Since τ is also a topological ordering of Gπ0 , the statement τ ∼ π follows by induction
on the number of inversions in π.

In the following example we illustrate Theorem 8.1 and show how the vertices of a DAG associahedron can be labeled by posets or by DAGs.
Example 8.2. We return to Example 3.4. Compared to the permutohedron, the DAG associahedron corresponding to G has six new vertices, namely:
(a)
(b)
(c)
(d)
(e)
(f)

(1|2|3|4), (2|1|3|4),
(1|2|4|3), (2|1|4|3),
(1|3|2|4), (1|3|4|2),
(2|3|1|4), (2|3|4|1),
(3|4|1|2), (3|1|4|2), (3|1|2|4),
(3|4|2|1), (3|2|4|1), (3|2|1|4).

The posets representing these vertices and the corresponding DAGs are shown in Figure 8. Each
of the other vertices of the DAG associahedron corresponds to a single permutation and the corresponding DAG has no missing edges.

If we have a description of the vertices of a DAG associahedron in terms of posets, then we
know the maximal cones in the normal fan, so we can directly obtain all other normal cones by
intersecting the maximal cones. In the following, we give an alternative description of the edges of

22

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

the DAG associahedron in terms of the DAGs Gπ , Gτ corresponding to the vertices adjacent to an
edge (π, τ ).
Chickering [Chi95] introduced the notion of a covered edge: a directed edge (i, j) in G is covered
if
pa(i) = pa(j) \ {i}.
We denote by G the skeleton of a DAG G. In addition, for two undirected graphs G and G0 we say
that G is a subset of G0 , i.e., G ⊆ G0 , if G and G0 have the same node set and every edge in G is
also an edge in G0 .
The following result shows that given a DAG label of a vertex of a DAG associahedron, we can
find neighboring vertices whose underlying graph is not bigger by flipping the direction of a covered
edge. We will prove this result more generally for gaussoids.
Theorem 8.3. Let F be a coarsened Sn fan corresponding to a gaussoid. Suppose the equivalence
classes of π = (π1 |π2 | · · · |πn ) and τ = (π1 |π2 | · · · |πi+1 |πi | · · · |πn ) are adjacent maximal cones in F.
Then G τ ⊆ G π if and only if (πi , πi+1 ) is a covered edge in Gπ .
Proof. First, note that (πi , πi+1 ) is an edge in Gπ , since otherwise Gπ = Gτ by Theorem 8.1.
We now prove the “if” direction. Without loss of generality we assume that π = (1|2| · · · |n),
τ = (1|2| · · · |i − 1|i + 1|i|i + 2| · · · |n) and (i, i + 1) is a covered edge in Gπ . Note that from the
definition of Gπ and Gτ the only difference between these two DAGs can be in the presence or
absence of edge (`, i) or (`, i + 1) with ` < i. In order to prove that Gτ ⊆ Gπ , we need to show
that any missing edge (`, i) or (`, i + 1) in Gπ is also not present in Gτ . Now suppose that (`, i) is
a missing edge in Gπ for some ` < i. Since the edge (i, i + 1) is covered in Gπ , then (`, i + 1) is also
a missing edge in Gπ . Let K = {1, . . . , i − 1}\{`}. By the definition of Gπ and Gτ we get that
`⊥
⊥i|K

and ` ⊥
⊥ i + 1 | Ki,

and hence by the semigraphoid property (SG2) we obtain that ` ⊥
⊥ i + 1 | K and ` ⊥
⊥ i | K ∪ {i + 1}.
Therefore, (`, i) and (`, i + 1) are also missing edges in Gτ , and we conclude that Gτ ⊆ Gπ .
For the “only if” direction suppose that Gτ ⊆ Gπ . We want to show that the edge (πi , πi+1 ) is a
covered edge in Gπ . Assume on the contrary that it is not.
We first consider the case when there is an a < i with (a, i + 1) ∈ Gπ but (a, i) ∈
/ Gπ . Then
(a, i) ∈
/ Gτ , and hence
a⊥
⊥ i | K ∪ {i + 1},

(9)

where K = {1, . . . , i−1}\{a}. We claim that (a, i+1) ∈ Gτ . Otherwise we would have a ⊥
⊥ i+1 | K,
which together with (9) implies a ⊥
⊥ i + 1 | Ki by (SG2), contradicting (a, i + 1) ∈ Gπ . From
(a, i + 1) ∈ Gτ , we have
a⊥
6⊥ i + 1 | K.

(10)
Next we claim that

i⊥
6⊥ i + 1 | K.

(11)

Otherwise, together with (9) we would have i ⊥
⊥ i + 1 | Ka by (SG2), contradicting the assumption
that π and τ lie in adjacent cones of the fan F. Finally, from the weak-transitivity axiom (G2) for
gaussoids we obtain
(12)

i⊥
6⊥ i + 1 | K

(G2)

and a ⊥
6⊥ i + 1 | K =⇒ a ⊥
6⊥ i | K

or a ⊥
6⊥ i | K ∪ {i + 1}

Combining (9) and (12), we obtain a ⊥
6⊥ i | K, that is, (a, i) ∈ Gπ , contradicting the assumption that
(a, i) ∈
/ Gπ .

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

23

Algorithm 2 Greedy SP algorithm on the DAG associahedron
Input: A set of CI relations C on n random variables and a starting permutation π ∈ Sn
Output: An essential graph G.
(1) Set t = 0 and π (0) = π.
(t−1)
(t−1)
(2) Set t := t + 1. Randomly select a covered edge (πi
, πj
) in Gπ(t−1) and reverse its
direction. Let π (t) denote the resulting permutation and Gπ(t) the corresponding DAG.
(3) Iterate (2) until convergence to the sparsest Markov equivalence class and output the
corresponding essential graph.
Now we consider the case where (a, i) ∈ Gπ , but (a, i + 1) ∈
/ Gπ , so (a, i + 1) ∈
/ Gτ . Then
(13)

a⊥
⊥ i + 1 | Ki and a ⊥
⊥ i + 1 | K.

By the gaussoid axiom (G1), we have
(14)

i + 1⊥
6⊥ a | Ki or

i + 1⊥
6⊥ i | Ka ⇒ a ⊥
6⊥ i + 1 | K

or i ⊥
6⊥ i + 1 | K.

Since π and τ are in adjacent cones of the fan F, we have i + 1 ⊥
6⊥ i | Ka, so by (13) and (14),
(15)

i⊥
6⊥ i + 1 | K.

Since by assumption (a, i) ∈ Gπ , then a ⊥
6⊥ i | K. This together with (15) and weak transitivity (G2)
gives us a ⊥
6⊥ i + 1 | Ki or a ⊥
6⊥ i + 1 | K, which contradicts (13).

This result directly gives rise to an improved version of Algorithm 1, which corresponds to
performing a greedy search on the DAG associahedron instead of the permutohedron and does not
require knowing the underlying true DAG (see Algorithm 2). In this algorithm, we are given a
set of CI relations C that are induced from a fixed but unknown DAG G. In each iteration the
algorithm outputs an auxiliary DAG, whose skeleton contains the skeleton of G. In a statistical
follow-up work [SWMU17] we show the importance of the geometric results obtained in this paper
for applications to causal inference. In particular, we prove that Algorithm 2 is consistent under
the faithfulness condition, i.e., that it converges to G under the faithfulness assumption. We end
by providing a sketch of the proof. Let G denote the true DAG. Then G = Gπ for some π (any
topological ordering of G). Let τ ∈ Sn . Then every independence relation that holds for Gτ also
holds for G [RU14, Lemma 2.1]. This implies G ⊆ Gτ . If a permutation π differs from τ only in the
reversal of a covered edge in Gτ , then by Theorem 8.3 we have Gπ ⊆ Gτ . At a high level, the proof
follows from a result by Chickering [Chi02b, Theorem 4] which says that using such edge reversals
one can go from any DAG Gτ to any DAG Gπ with Gπ ⊆ Gτ . The difficulty lies in showing that
there exists such a Chickering sequence which corresponds to a walk on the DAG associahedron,
which is proven in [SWMU17].
Appendix A. Polytopes and fans
Most of the following definitions can be found in [Zie95]. A polyhedron is a subset of a real
vector space Rn defined by finitely many linear inequalities. A polytope is a bounded polyhedron.
Equivalently, a polytope is the convex hull of a finite set of points in Rn . The Minkowski sum of
two polyhedra P and Q is defined as P + Q = {x + y | x ∈ P and y ∈ Q}. A (polyhedral) cone
is a polyhedron that is closed under addition and scaling by a nonnegative real number. A face of
a polyhedron P is a subset of P that maximizes some linear functional. A face F of a nonempty
polyhedron P is proper if F 6= P . A facet is an inclusion maximal proper face of P .
A fan is a family F of nonempty polyhedral cones such that

24

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

(1) every face of a cone in F is also a cone in F;
(2) the intersection of any two cones in F is a face of both.
A fan in Rn is complete if the union of its cones is equal to Rn . A wall in a complete fan in Rn is
an (n − 1)-dimensional cone in the fan.
For each face F of P , the outer normal cone NF is the set of all linear functionals that are
maximized on F , i.e.
NF = {c ∈ (Rn )∗ | F ⊆ {x ∈ P | c · x = max(c · y)}}.
y∈P

The outer normal fan of a polytope P is the collection {NF : F is a face of P }, which is a complete
fan in (Rn )∗ . We identify (Rn )∗ and Rn using the usual dot product. The inner normal cones and
fans are defined analogously by replacing “max” with “min”. For two faces F and F 0 of P , we have
F ⊆ F 0 if and only if NF ⊇ NF 0 . In particular, the smallest cone in the normal fan of P is a linear
space, namely the orthogonal complement of P . The normal cones of facets are inclusion-minimal
cones that strictly contain the smallest cone. The maximal full-dimensional cones in the normal
fan are normal cones of the vertices of P .
Appendix B. A proof of Lemma 2.3
Lemma 2.3. A polytope P ⊆ Rn is a generalized permutohedron if and only if there exists a
submodular function ω : 2[n] → R with ω(∅) = 0 such that
X
X
(3)
P = {x ∈ Rn :
xi ≤ ω(I) for each nonempty I ⊆ [n], and
xi = ω([n])}.
i∈I

i∈[n]

A wall in the Sn fan corresponding to i ⊥
⊥ j | K is missing in the normal fan of P defined by ω
as above if and only if ω(Ki) + ω(Kj) = ω(Kij) + ω(K). In particular, a coarsened Sn fan is
polytopal if and only if the corresponding semigraphoid is submodular.
Before proving the lemma, we first recall a general construction of the normal fan of a polytope
from a halfspace description. See also [DLRS10, Theorem 9.5.6].
Let P = {x ∈ Rn : Ax + b ≥ 0} be a polytope, where A is a k × n matrix and b ∈ Rk is a
column vector. Let us assume that P is nonempty but is not necessarily full-dimensional. Also
assume that all inequalities are tight but possibly redundant. In particular, if ai = aj , then bi = bj
where (ai , bi ) and (aj , bj ) are rows of [A|b]. Let C ∗ be the cone in Rn × R generated by the rows
of the concatenated matrix [A|b] and the vector (0, 1). The row (ai , bi ) of [A|b] is called a lift of
the vector ai ∈ Rn . Since P is bounded, for any z ∈ Rn we have Az ≥ 0 ⇒ z = 0; otherwise P
would be unbounded in direction z. Then the rows of A cannot be all contained in a halfspace
{x : x · z ≥ 0} for any nonzero z, so the rows of A positively span Rn , and the cone C ∗ projects
surjectively onto Rn .
The dual cone of C ∗ is
C :={v ∈ Rn+1 : u · v ≥ 0 for all u ∈ C ∗ }
(16)

={v ∈ Rn+1 : [A|b]v ≥ 0 and vn+1 ≥ 0}
= cone{(x, 1) : x ∈ P },

where cone{·} denotes the conical hull. All nonzero vectors in the cone C have positive last
coordinates and hence all proper faces of C ∗ are on the lower hull of C ∗ , that is, they have inward
pointing normal vectors with positive last coordinate. In particular, if a vector (a, b) lies on the
boundary of C ∗ , then (a, b + ε) does not lie on the boundary of C ∗ for any ε > 0. Since each

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

25

inequality ai x + bi ≥ 0 is assumed to be tight, there is a point xi ∈ P satisfying ai xi + bi = 0, so the
vector (ai , bi ) belongs to a proper face of C ∗ that minimizes the linear functional u 7→ (xi , 1) · u.
We claim that the projections of proper faces of C ∗ onto Rn form the inner normal fan of P . Let
p be a point in P and consider the inner normal cone
Np := {c ∈ Rn : c · p ≤ c · q for all q ∈ P }.
We will show that Np is the projection of the following face of C ∗ that minimizes the dot product
with (p, 1):
face(p,1) (C ∗ ) := {u ∈ C ∗ : u · (p, 1) ≤ u0 · (p, 1) for all u0 ∈ C ∗ } = {u ∈ C ∗ : u · (p, 1) = 0}.
Let c ∈ Np . and let u = (c, −c · p). Then u · (p, 1) = c · p − c · p = 0 and u · (q, 1) = c · q + un+1 ≥
c · p + un+1 = u · (p, 1) = 0 for any q ∈ P ; so we have found a vector u ∈ face(p,1) (C ∗ ) whose
projection is c. For the other inclusion, let u ∈ face(p,1) (C ∗ ). Then (u1 , . . . , un ) · p + un+1 = 0,
while (u1 , . . . , un ) · q + un+1 ≥ 0 for all q ∈ P , and hence (u1 , . . . , un ) · p ≤ (u1 , . . . , un ) · q. Thus
the projection (u1 , . . . , un ) belongs to Np . This shows that normal cones of P are precisely the
projections of proper faces of C ∗ .
In summary, a complete fan F in Rn is the normal fan of a polytope if and only if there exists a
cone K ⊂ Rn × R with (0, 1) ∈ K whose proper faces project precisely onto cones of F. Given such
a cone K, the desired polytope is obtained by slicing the dual cone C of K with the hyperplane
xn+1 = 1 and projecting out xn+1 . Given a polytope P , the desired cone K can be obtained two
ways: either as K = (cone{(x, 1) : x ∈ P })∗ , or from an inequality description Ax + b ≥ 0 of P
by lifting the rows of A to height b and taking the conical hull of these lifted rows together with
the vector (0, 1). Tightness of an inequality means that the corresponding vector is lifted to the
boundary of K.
For any collection of vectors {(a1 , b1 ), . . . , (ak , bk )} that spans K as a conical hull, we can consider
the polytope {x ∈ Rn : ai · x + bi ≥ 0 for all i}. The arguments above show that this polytope is
equal to P .
Proof of Lemma 2.3. Let F be a coarsened Sn fan which is the normal fan of a polytope P . Every
cone in F contains a line in direction (1, 1, . . . , 1) and is generated by this line together with
some 0/1 vectors. Then F consists of the projection of faces of a cone in Rn × R generated by
lifts of the 0/1 vectors and ±(1, . . . , 1). By the paragraph preceding the proof, P must have a
tight halfspace description with normal vectors from the set V = {eI | ∅ 6= I ⊆ [n]} ∪ {−e[n] }.
The “right-hand sides” of the inequalities give a lift ω : V → R such that the proper faces of
the cone C ∗ = cone{(v, ω(v)) | v ∈ V } project precisely onto the cones of F and every lifted
vector is on the boundary of C ∗ . Since all cones in F contain the line (1, 1, . . . , 1), we must have
ω(e[n] ) = −ω(−e[n] ). Such lifts can be identified with functions on 2[n] with value 0 on ∅. We will
show that ω is submodular.
For any I, J ⊆ [n], the vectors eI , eI∩J , eI∪J lie in a common cone in the Sn fan. Since F coarsens
the Sn fan, they also lie in a common cone in F. Similarly eJ , eI∩J , eI∪J lie in a common cone of F.
First, consider the case when eI and eJ are lifted to the same proper face of C ∗ . Then this cone also
contains eI∩J and eI∪J . Since we assumed that all lifted vectors lie on the boundary, hence a proper
face, of C ∗ , and ω is linear on this face, we must have that ω(eI ) + ω(eJ ) = ω(eI∩J ) + ω(eI∪J ).
Now suppose that eI and eJ are not lifted to the same proper face of C ∗ . Then ω is not linear
on the vectors eI , eJ , eI∩J , and eI∪J . We must then have that ω(eI ) + ω(eJ ) > ω(eI∩J ) + ω(eI∪J ),
because ω(eI ) + ω(eJ ) < ω(eI∩J ) + ω(eI∪J ) would imply that
(eI∩J + eI∪J , ω(eI∩J ) + ω(eI∪J )) > (eI + eJ , ω(eI ) + ω(eJ )),
contradicting the fact that eI∩J and eI∪J are lifted to the same cone in the lower hull of C ∗ .

26

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

For the converse, suppose ω is a submodular function on 2[n] with ω(∅) = 0 and consider the
lift of eI to ω(I) for each I ⊆ [n] and −e[n] to −ω([n]). Let F be the projection of the lower hull of
the lifted cone C ∗ . The submodularity inequality ω(eI ) + ω(eJ ) ≥ ω(eI∩J ) + ω(eI∪J ) ensures that
whenever eI and eJ are lifted to the same cone in the lower hull of C ∗ , then so are eI∩J and eI∪J .
In other words, whenever a cone of F contains both, eI and eJ , then it must also contain both,
eI∩J and eI∪J , showing that F is a coarsening of the Sn fan.
Now suppose that the coarsened Sn fan F is polytopal and defined by a submodular function ω
as above. Consider a wall of the Sn fan corresponding to the adjacent permutations
(a1 | · · · |ak |i|j|b1 | · · · |bn−k−2 ) and (a1 | · · · |ak |j|i|b1 | · · · |bn−k−2 ),
where {a1 , . . . , ak } = K and {b1 , . . . , bn−k−2 } = [n]\(K ∪ {i, j}). This wall is not contained in a
wall of F if and only if the two adjacent maximal cones are contained in the same cone of F. In
particular, this happens if and only if eKi and eKj are in the same cone where K = {a1 , . . . , ak }.
This is equivalent to having
ω(Ki) + ω(Kj) = ω(Kij) + ω(K).
Let P be the polytope defined by (3). Its inner normal fan is obtained by lifting the rays −eI
to height ω(I) for nonempty I ⊆ [n] and e[n] to height −ω([n]). This is the negation of the fan F,
which is obtained by lifting eI to ω(I) and −e[n] to −ω([n]). This shows that F is the outer normal
fan of P .

Appendix C. Dictionary
The statements or data in each row are equivalent.
CI relations

Fans

the set of walls in the Sn fan of
CI relation i ⊥
⊥j|K
the form σ|i j|τ where σ and
where i, j ∈ [n], K ⊆
τ are permutations of K and
[n] \ {i, j}
[n]\Kij respectively
a collection of CI re- removing the walls in the Sn
lations that satisfy the fan corresponding to the indesemigraphoid axioms
pendence relations gives a fan
a semigraphoid that
a coarsening of Sn fan that is
arises from a submodpolytopal or regular
ular function
a union of dependence
relations of a semi- a common refinement of fans
graphoid

Polytopes
the set of edges of a permutohedron
connecting two permutations of the
form σ|i|j|τ and σ|j|i|τ where σ and
τ are permutations of K and [n]\Kij,
respectively
the set of edges of the permutohedron corresponding to the independence relations satisfies the square
and hexagon axioms [MPS+ 09]
there is a generalized permutohedron
that realizes contraction of edges in
the permutohedron corresponding to
the CI relations
a Minkowski sum of polytopes (if the
semigraphoid is submodular)

Acknowledgment
CU was partially supported by DARPA (W911NF-16-1-0551), NSF (DMS-1651995), ONR (N0001417-1-2147), a Sloan Fellowship, and the Austrian Science Fund (Y 903-N35). JY was partially
supported by the US NSF grant DMS #1600569. We are grateful to the anonymous referees for
very helpful comments on earlier versions of this paper.

GENERALIZED PERMUTOHEDRA FROM PROBABILISTIC GRAPHICAL MODELS

27

References
[AMP97] S. A. Andersson, D. Madigan, and M. D. Perlman, A characterization of Markov equivalence classes for
acyclic digraphs, The Annals of Statistics 25 (1997), no. 2, 505–541.
[CD06] M. P. Carr and S. L. Devadoss, Coxeter complexes and graph-associahedra, Topology and its Applications
153 (2006), no. 12, 2155–2168.
[Chi02a] D. M. Chickering, Learning equivalence classes of Bayesian-network structures, Journal of Machine Learning Research 2 (2002), no. 3, 445–498.
[Chi02b] D. M. Chickering, Optimal structure identification with greedy search, Journal of Machine Learning Research 3 (2002), 507–554.
[Chi95] D. M. Chickering, A transformational characterization of equivalent Bayesian network structures, Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence, 1995, pp. 87–98.
[CHS17] J. Cussens, D. Haws, and M. Studený, Polyhedral aspects of score equivalence in Bayesian network structure learning, Mathematical Programming, Series A 164 (2017), 285–324.
[Dev09] S. L. Devadoss, A realization of graph associahedra, Discrete Mathematics 309 (2009), no. 1, 271–276.
[DLRS10] J. A. De Loera, J. Rambau, and F. Santos, Triangulations, Algorithms and Computation in Mathematics,
vol. 25, Springer-Verlag, Berlin, 2010.
[DSS09] M. Drton, B. Sturmfels, and S. Sullivant, Lectures on Algebraic Statistics, Oberwolfach Seminars, vol. 39,
Birkhäuser Verlag, Basel, 2009.
[DX10] M. Drton and H. Xiao, Smoothness of Gaussian conditional independence models, Algebraic methods in
statistics and probability II, 2010, pp. 155–177.
[Fuj05] S. Fujishige, Submodular Functions and Optimization, Second, Annals of Discrete Mathematics, vol. 58,
Elsevier, Amsterdam, 2005.
[HLS12] Raymond Hemmecke, Silvia Lindner, and Milan Studenỳ, Characteristic imsets for learning bayesian
network structure, International Journal of Approximate Reasoning 53 (2012), no. 9, 1336–1349.
[HMS+ 08] R. Hemmecke, J. Morton, A. Shiu, B. Sturmfels, and O. Wienand, Three counter-examples on semigraphoids, Combinatorics, Probability and Computing 17 (2008), no. 2, 239–257.
[JSGM10] T. Jaakkola, D. Sontag, A. Globerson, and M. Meila, Learning Bayesian network structure using LP
relaxations, Proceedings of the 13th international conference on artificial intelligence and statistics, 2010,
pp. 358–365.
[Lau96] S. L. Lauritzen, Graphical Models, Oxford Statistical Science Series, vol. 17, The Clarendon Press, Oxford
University Press, New York, 1996. Oxford Science Publications.
[LM07] R. Lněnička and F. Matúš, On Gaussian conditional independent structures, Kybernetika (Prague) 43
(2007), no. 3, 327–342.
[Mat92] F. Matúš, Ascending and descending conditional independence relations, Transactions of the 11th prague
conference on information theory, statistical decision functions and random processes, 1992, pp. 189–200.
[Mee95] C. Meek, Causal inference and causal explanation with background knowledge, Proceedings of the 11th
Conference on Uncertainty in Artificial Intelligence, 1995, pp. 403–410.
[Mee97] C. Meek, Graphical models: Selecting causal and statistical models, 1997. PhD thesis, Carnegie Mellon
University.
[MPS+ 09] J. Morton, L. Pachter, A. Shiu, B. Sturmfels, and O. Wienand, Convex rank tests and semigraphoids,
SIAM Journal on Discrete Mathematics 23 (2009), no. 3, 1117–1134.
[Mur03] K. Murota, Discrete Convex Analysis, SIAM Monographs on Discrete Mathematics and Applications,
Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2003.
[Oxl11] James Oxley, Matroid theory, Second Edition, Oxford Graduate Texts in Mathematics, vol. 21, Oxford
University Press, Oxford, 2011. MR2849819
[Pea88] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, The Morgan
Kaufmann Series in Representation and Reasoning, Morgan Kaufmann, San Mateo, CA, 1988.
[PRW08] A. Postnikov, V. Reiner, and L. Williams, Faces of generalized permutohedra, Documenta Mathematica
13 (2008), 207–273.
[RU14] G. Raskutti and C. Uhler, Learning directed acyclic graphs based on sparsest permutations, 2014.
arXiv:1307.0366.
[Sha98] R. D. Shachter, Bayes-ball: Rational pastime (for determining irrelevance and requisite information in
belief networks and influence diagrams), Proceedings of the 14th Conference on Uncertainty in Artificial
Intelligence, 1998, pp. 480–487.
[SHHL12] M. Studený, D. Haws, R. Hemmecke, and S. Lindner, Polyhedral approach to statistical learning graphical
models, Harmony of gröbner bases and the modern industrial society: the 2nd crest-sbm international
conference (T. Hibi ed.), 2012, pp. 346–372.

28

FATEMEH MOHAMMADI, CAROLINE UHLER, CHARLES WANG, AND JOSEPHINE YU

[SL14] Kayvan Sadeghi and Steffen Lauritzen, Markov properties for mixed graphs, Bernoulli 20 (2014), no. 2,
676–696. MR3178514
[Stu05] Milan Studený, Probabilistic conditional independence structures, Information Science and Statistics,
Springer, London, 2005. MR3183760
[Stu92] M. Studenỳ, Conditional independence relations have no finite complete characterization, Information
Theory, Statistical Decision Functions, Random Processes B (1992), 377–396.
[Sul09] S. Sullivant, Gaussian conditional independence relations have no finite complete characterization, Journal
of Pure and Applied Algebra 213 (2009), no. 8, 1502–1506.
[SVH10] M. Studený, J. Vomlel, and R. Hemmecke, A geometric view on learning Bayesian network structures,
International Journal of Approximate Reasoning 51 (2010), 578–586.
[SWMU17] L. Solus, Y. Wang, L. Matejovicova, and C. Uhler, Consistency guarantees for permutation-based causal
inference algorithms, 2017. arXiv:1702.03530.
[TK05] M. Teyssier and D. Koller, Ordering-based search: A simple and effective algorithm for learning Bayesian
networks, Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence, 2005, pp. 584–590.
[URBY13] C. Uhler, G. Raskutti, P. Bühlmann, and B. Yu, Geometry of the faithfulness assumption in causal
inference, The Annals of Statistics 41 (2013), no. 2, 436–463.
[VP90] T. Verma and J. Pearl, Equivalence and synthesis of causal models, Proceedings of the 6th Annual
Conference on Uncertainty in Artificial Intelligence, 1990, pp. 255–270.
[Zie95] G. M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New
York, 1995.
School of Mathematics, University of Bristol, Bristol, BS8 1TW, UK
E-mail address: fatemeh.mohammadi@bristol.ac.uk
Department of Electrical Engineering & Computer Science, and Institute for Data, Systems and
Society, Massachusetts Institute of Technology, Cambridge MA, USA
E-mail address: cuhler@mit.edu
Department of Mathematics, University of California, Berkeley, CA, USA
E-mail address:

charles@math.berkeley.edu

School of Mathematics, Georgia Institute of Technology, Atlanta GA, USA
E-mail address: jyu@math.gatech.edu

