# Toric and non-toric Bayesian networks

Lisa Nicklasson The author was supported by the grant KAW 2019.0512

(Università degli Studi di Genova
<EMAIL_ADDRESS>
###### Abstract

In this paper we study Bayesian networks from a commutative algebra
perspective. We characterize a class of toric Bayesian nets, and provide the
first example of a Bayesian net which is provably non-toric under any linear
change of variables. Concerning the class of toric Bayesian nets, we study
their quadratic relations and prove a conjecture by Garcia, Stillman, and
Sturmfels [9] for this class. In addition, we give a necessary condition on
the underlying directed acyclic graph for when all relations are quadratic.

##  1 Introduction

A _Bayesian network_ is a graphical model given by a directed acyclic graph
(DAG) where the vertices are random variables. In this paper we consider
_finite_ Bayesian networks, in the sense that the DAG has a finite number of
vertices, and each random variable takes a finite number of values. In
general, a _statistical model_ is identified with a collection of probability
distributions and can often, as in the case of finite Bayesian nets, be
realized as a real algebraic variety. Such statistical models can be described
explicitly by finding a parameterization of the variety, or implicitly as the
zero set of a system of equations. For a Bayesian net $G$ the implicit
description gives rise to a polynomial prime ideal which we denote $P_{G}$.

Every finite Bayesian network has two graphical representations: the DAG
mentioned above, and a _staged tree_. Staged trees are rooted directed trees
where a vertex coloring encodes invariances among conditional distributions,
and describe a large class of statistical models, not all which are Bayesian
networks. As staged trees were first introduced in [16] earlier work on
Bayesian networks does not mention this representation. Nevertheless, staged
trees proves to be a helpful tool when studying finite Bayesian networks, not
least in the work presented in this paper.

In Section 2 we introduce staged trees, Bayesian networks, and their
associated ideals in a fashion that suits the purposes of this paper. For a
more thorough introduction to staged tree models the reader is referred to
[4]. An introduction to graphical models can be found for instance in [14].

_Toric models_ are statistical models which can be realized as toric
varieties. Clearly, being toric opens up to using tools for from the well
studied research field of toric geometry, and its benefits for statistical
models are discussed for example in [15]. An example of a class of toric
models are the discrete _undirected graphical models_ [10]. Related to
directed graphical models, the so called _Conjunctive Bayesian networks_
studied in [2] are toric. A class of toric staged trees is characterized in
[12]. In Section 3 of this paper we investigate which finite Bayesian networks
are toric. Applying the result of [12] we deduce a class of toric Bayesian
nets, described by a property on the induced subgraph of the non-sinks of the
DAG, see Theorem 3.3. In general it is a difficult task to prove that a
variety is not toric, under any linear change of coordinates. However, in
Theorem 3.6 we give the first example of a Bayesian network proved to not be
toric in any choice of basis.

An implicit description of a graphical model is often given in terms of
conditional independence relations. Given a finite Bayesian network $G$, these
relations gives rise to a quadratic ideal $I_{G}\subseteq P_{G}$. In Section 4
we examine the relationship between these two ideals. It is conjectured in [9]
that the quadratic part of $P_{G}$ is given precisely by $I_{G}$. In Theorem
4.2 we prove this conjecture for the toric Bayesian nets given by Theorem 3.3.
Moreover, we show in Theorem 4.4 that, under the assumption of Theorem 3.3,
for the two ideals to be equal it is necessary that $G$ does not contain an
induced cycle of length greater than three.

In Section 5 we state three open problems, hoping to inspire further research
on commutative algebra of Bayesian networks.

##  2 Preliminaries

###  2.1 Staged trees

Consider a directed tree $T=(V,E)$ with a distinguished root, such that every
edge is directed away from the root. For a vertex $v\in V$ let $E(v)\subset E$
denote the set of edges $v\to v^{\prime}$ emanating from $v$. To each edge we
assign a label, and we let $\Theta$ denote the set of edge labels. The
function $\theta:E\to\Theta$ maps each edge to its edge label. The tree $T$ is
called a _staged tree_ if

  * •

for every $v\in V$ the edges $E(v)$ gets distinct labels, i. e.
$|\theta(E(v))|=|E(v)|$,

  * •

for every pair $v,w\in V$ the sets $\theta(E(v))$ and $\theta(E(w))$ are
either equal or disjoint.

The tree to the right in Figure 1 is an example of a staged tree. We define an
equivalence relation $\sim$ on $V$ by $v\sim w$ if
$\theta(E(v))=\theta(E(w))$. The equivalence classes are called _stages_. When
drawing a staged tree $T$ we visualize the stages with a vertex coloring by
giving vertices of the same stage the same color. To make the pictures in this
paper as clear as possible, we choose to only give color to stages with more
than one vertex. White vertices should be considered uncolored, meaning that
each white vertex belongs to a stage consisting of only that single vertex.

The _level_ of a vertex $v$ is the distance, i. e. the number of edges,
between $v$ and the root. A staged tree is called _stratified_ if vertices of
the same stage are on the same level, and all leaves are on the same level.
All staged trees considered in this paper are stratified.

Let $\rho:\Theta\to(0,1)$ be a map that assigns a real value in the open
interval $(0,1)$ to each edge label, requiring

$\sum_{e\in E(v)}\\!\\!\rho(\theta(e))=1\quad\text{for each}\ v\in V.$ (1)

Let $N$ be the number of leaves in the tree $T$. Each leaf $\ell$ is assigned
a value in $(0,1)$ by taking the product $\prod\rho(\theta(e))$ over all edges
$e$ on the directed path from the root to $\ell$. This produces a point in
$\mathbb{R}^{N}$. The set of all points in $\mathbb{R}^{N}$ obtained by
varying $\rho$ is the _staged tree model_ $\mathcal{M}_{T}$.

The staged tree model can also be described in terms of algebraic geometry.
Let $\mathbb{R}[\boldsymbol{x}]=\mathbb{R}[x_{1},\ldots,x_{N}]$ be the
polynomial ring where each variable is associated to a leaf in the staged tree
$T$, and let $\mathbb{R}[\Theta]$ be the polynomial ring on the edge labels.
Let $\langle\boldsymbol{\theta}-1\rangle$ denote the ideal of
$\mathbb{R}[\Theta]$ generated by the relations

$\sum_{e\in E(v)}\\!\\!\\!\theta(e)-1\quad\text{for each}\ v\in V.$

Note that it is enough to consider one vertex from each stage. Now we define a
homomorphism
$\varphi:\mathbb{R}[\boldsymbol{x}]\to\mathbb{R}[\Theta]/\langle\boldsymbol{\theta}-1\rangle$
by sending each variable to the product of the edge labels along the root-to-
leaf path. Then

$\mathcal{M}_{T}=\mathcal{V}(\ker\varphi)\cap\Big{\\{}p\in\mathbb{R}^{N}\
\Big{|}\ \sum_{i=1}^{N}p_{i}=1\ \text{and}\ 0<p_{i}<1\ \text{for}\
i=1,\ldots,N\Big{\\}}.$

Note that the ideal $\ker\varphi$ is not homogeneous as
$\varphi(x_{1}+\dots+x_{N}-1)=0$. For practical reasons we will work with a
homogenized version of the map $\varphi$. To this end we introduce a
homogenizing variable $z$, and let
$\langle\boldsymbol{\theta}-z\rangle\subset\mathbb{R}[\Theta,z]$ denote the
ideal generated by

$\sum_{e\in E(v)}\\!\\!\\!\theta(e)-z\quad\text{for each}\ v\in V.$

For a given stratified staged tree $T$ we let $P_{T}$ denote the kernel of the
map
$\bar{\varphi}:\mathbb{R}[\boldsymbol{x}]\to\mathbb{R}[\Theta,z]/\langle\boldsymbol{\theta}-z\rangle$,
defined in the same way as $\varphi$. Note that $P_{T}$ is a prime ideal as
$\mathbb{R}[\Theta,z]/\langle\boldsymbol{\theta}-z\rangle$ is a domain.
Moreover, $P_{T}$ is homogeneous as
$\mathbb{R}[\Theta,z]/\langle\boldsymbol{\theta}-z\rangle$ is a graded ring,
and $\bar{\varphi}$ maps homogeneous polynomials to homogeneous elements.

######  Lemma 2.1.

With notation as above, and $T$ a stratified staged tree

$\ker\varphi=P_{T}+\langle x_{1}+\dots+x_{N}-1\rangle.$

###### Proof.

Let $d$ be the length of a root-to-leaf path in $T$. Take $f\in\ker\varphi$
and consider the image of $f$ under $\bar{\varphi}$. Each term in
$\bar{\varphi}(f)$ has degree divisible by $d$. We reduce the number of terms
in the presentation of $\bar{\varphi}(f)$ as much as possible working modulo
$\langle\boldsymbol{\theta}-z\rangle$. The resulting representation is a
polynomial where all terms cancel after substituting $z=1$. In other words, if
we see a term $m$ in $\bar{\varphi}(f)$, there is also a term $-z^{ds}m$. It
follows that

$\ker\varphi=\ker\bar{\varphi}+\bar{\varphi}^{-1}(\langle
z^{d}-1\rangle)=\ker\bar{\varphi}+\langle x_{1}+\dots+x_{N}-1\rangle.\qed$

See also the discussion about passing to projective space when studying
statistical models for discrete random variables in [18, Section 3.6].

###  2.2 Bayesian networks

Throughout this paper a Bayesian network is a DAG $G=(V,E)$ where the vertex
set $V$ is a set of $n$ finite random variables. Each random variable $X$
takes a number of values say $1,\ldots,\kappa$ with some probabilities
$\theta_{1},\ldots,\theta_{\kappa}$, given the values of the parents of $X$.

Figure 1: A DAG and a staged tree representing a Bayesian network on four
binary random variables

The Bayesian network $G$ can be represented by a stratified staged tree
$T_{G}$ with leaves on level $n$, as we see for instance in Figure 1. The
staged tree is produced in the following way. First we order the vertices
$V=\\{X_{1},\ldots,X_{n}\\}$ in a way such that if $X_{i}\to X_{j}$ is an
edge, then $i<j$. Let $1,\ldots,\kappa_{i}$ denote the possible values of the
finite random variable $X_{i}$. The vertices on level $i$ in $T_{G}$ have
$\kappa_{i+1}$ outgoing edges, representing the possible values of $X_{i+1}$.
A vertex $v$ on level $j$ can be identified with a vector
$v=(v_{1},\ldots,v_{j})$ where $v_{1},\ldots,v_{j}$ are the values of
$X_{1},\ldots,X_{j}$ defining the directed path from the root to $v$. Two
vertices $v$ and $w$ on level $j$ are in the same stage if $v_{i}=w_{i}$
whenever $X_{i}\to X_{j}$ is an edge in $G$. When working with staged trees of
Bayesian networks´ it is sometimes convenient to employ the notation

$\theta(X_{j}=1\ |\ X_{i}=v_{i}\ \text{for}\
X_{i}\in\operatorname{Pa}(X_{j})),\ldots,\theta(X_{j}=\kappa_{j}\ |\
X_{i}=v_{i}\ \text{for}\ X_{i}\in\operatorname{Pa}(X_{j}))$

for the labels of the edges $E(v)$. Here Pa$(X_{j})$ stands for the set of
parents of $X_{j}$ in $G$, that is the $X_{i}$’s such that $X_{i}\to X_{j}$ is
an edge. For example, if $v$ is any of the yellow vertices in Figure 1, then
the edge labels in the picture translates to the new notation as

$\theta_{411}=\theta(X_{4}=1\ |\
X_{1}=1,X_{2}=1),\quad\theta_{412}=\theta(X_{4}=2\ |\ X_{1}=1,X_{2}=1).$

We use the notation $P_{G}$, rather than $P_{T_{G}}$, for the prime ideal
associated to $T_{G}$. When studying the ideal $P_{G}$ of a Bayesian network
$G$ it can be convenient to index the variables in
$\mathbb{R}[\boldsymbol{x}]$ by vectors $u=(u_{1},\ldots,u_{n})$ encoding the
values of $X_{1},\ldots,X_{n}$. Then $P_{G}$ is defined as the kernel of the
map
$\mathbb{R}[\boldsymbol{x}]\to\mathbb{R}[\Theta,z]/\langle\boldsymbol{\theta}-z\rangle$
defined by

$x_{u}\mapsto\prod_{j=1}^{n}\theta(X_{j}=u_{j}\ |\ X_{i}=u_{i}\ \text{for}\
X_{i}\in\operatorname{Pa}(X_{j})).$ (2)

######  Remark 2.2.

The ideal $P_{G}$ is independent (up to a reindexing of the variables in
$\mathbb{R}[\boldsymbol{x}]$) of the choice of ordering of the random
variables $X_{1},\ldots,X_{n}$, as long as the numbering respects the
directions of the edges. This can be seen from (2), as an admissible
reordering of $X_{1},\ldots,X_{n}$ only reorders the factors in the image.

Moreover, we allow replacing some of the $u_{i}$’s by the symbol + to denote
the sum of all $x_{u}$’s with fixed values for a subset of the random
variables $X_{1},\ldots,X_{n}$. More precisely, let
$\Lambda\subseteq\\{1,\ldots,n\\}$, and fix some values $1\leq
u_{i}\leq\kappa_{i}$ for each $i\in\Lambda$. Let $u+$ denote the $n$-vector
where the $i$-th entry is $u_{i}$ if $i\in\Lambda$ and + otherwise. Then
$x_{u+}=\sum x_{v}$ where the sum is taken over all integer vectors
$v=(v_{1},\ldots,v_{n})$ such that $1\leq v_{i}\leq\kappa_{i}$ and
$v_{i}=u_{i}$ if $i\in\Lambda$.

When discussing the underlying DAG of a Bayesian network we will often denote
the vertices by the integers $1,\ldots,n$ referring to the random variables
$X_{1},\ldots,X_{n}$.

###  2.3 Conditional independence

Let $G$ be a Bayesian network on $n$ vertices, and let $A,B,$ and $C$ be
disjoint subsets of the vertices. We write $A\perp\\!\\!\\!\perp B\ |\ C$ for
the conditional independence statement “$A$ is independent of $B$ given $C$”.
This should be understood as “the probability of the random variables in $A$
taking any fixed values is independent of the values of the random variables
in $B$, given the values of the random variables $C$”. The perhaps most
intuitive conditional independence statements are those of the _ordered Markov
property_. The ordered Markov property is the set of conditional independence
statements

$j\perp\\!\\!\\!\perp(\\{1,\ldots,j-1\\}\setminus\operatorname{Pa}(j))\ |\
\operatorname{Pa}(j).$

For example, the statement $4\perp\\!\\!\\!\perp 3\ |\ \\{1,2\\}$ holds for
the DAG in Figure 1.

Suppose we fix a value $1\leq a_{i}\leq\kappa_{i}$ for each $i\in A$, and let
$a$ denote this choice of values. In the same way we fix values $b$ and $c$
for the random variables in $B$ and $C$. Let $abc$ denote the $n$-vector where
the $i$-th entry is $a_{i},b_{i},$ or $c_{i}$ if $i\in A,B$ or $C$, and +
otherwise. Let $M_{c}$ denote a matrix where the rows are indexed by all
combinations $a$ of values for the random variables in $A$, and the column by
the different choices of $b$. The entry on position $(a,b)$ in $M_{c}$ is
$x_{abc}$, and we define $I_{c}$ as the ideal generated by the $2\times
2$-minors of $M_{c}$. In other words, the generators of
$I_{c}\subset\mathbb{R}[\boldsymbol{x}]$ are quadratic forms

$x_{abc}x_{a^{\prime}b^{\prime}c}-x_{a^{\prime}bc}x_{ab^{\prime}c}.$ (3)

We define the ideal $I_{A\perp\\!\\!\\!\perp B|C}$ as the sum of all $I_{c}$,
for all different combinations $c$ of values of the random variables in $C$.
The conditional independence statement $A\perp\\!\\!\\!\perp B\ |\ C$ is then
equivalent to the ideal containment $I_{A\perp\\!\\!\\!\perp B|C}\subseteq
P_{G}$. For a proof of this fact see [17, Proposition 8.1].

A _trail_ in a DAG is a path where the directions of the edges are not taken
into account. Following [14] the statement $A\perp\\!\\!\\!\perp B\ |\ C$
translates to graph theoretical terms as $A$ and $B$ being _separated_ by $C$
in the following sense. If there is a trail $\pi$ connecting a vertex from $A$
and a vertex from $B$ there must be a vertex $j$ on $\pi$ such that either

  1. _S1._

$j\in C$, and the directions of the edges of $\pi$ at $j$ are _not_
$\rightarrow j\leftarrow$, or

  2. _S2._

$j\notin C$ and $j$ has no descendant in $C$, and the edges of $\pi$ at $j$
are directed as $\rightarrow j\leftarrow$.

In particular, a vertex in $A$ can not have a child or a parent in $B$. The
set of all conditional independence statements that holds for a Bayesian
network $G$ is called the _global Markov property_ of $G$. Employing the same
notation as [9] we let $I_{\operatorname{global}(G)}$ denote the sum of all
ideals $I_{A\perp\\!\\!\\!\perp B|C}$ for which $A\perp\\!\\!\\!\perp B\ |\ C$
holds.

By definition $I_{\operatorname{global}(G)}\subseteq P_{G}$, and it follows by
[9, Theorem 8] that $P_{G}$ is a minimal prime of
$I_{\operatorname{global}(G)}$.

##  3 Conditions for toric Bayesian networks

A _toric ideal_ in $\mathbb{R}[\boldsymbol{x}]$ is a prime binomial ideal.
Equivalently, an ideal is toric if it is the kernel of a monomial map, i. e. a
homomorphism between polynomial rings where each variable is mapped to a
monomial. Note that the ring homomorphisms defining the ideals $P_{G}$ are not
monomial maps, as the image lies in a quotient ring. Moreover, being a
binomial ideal is a property that depends on the choice of basis for the
polynomial ring $\mathbb{R}[\boldsymbol{x}]$. In this section we study the
question: For which Bayesian networks $G$ are the ideals $P_{G}$ toric, after
a suitable linear change of variables?

The most immediate class of toric Bayesian nets are those for which the
associated prime ideal is binomial in the given variables. A DAG $G$ is called
_perfect_ if for every vertex $i$ the induced undirected subgraph on Pa$(i)$
is a complete graph. It was first proved in [14, Proposition 3.28] that the
ideal $P_{G}$ is binomial when $G$ is perfect. Moreover, by [8, Theorem 3.1]
$G$ is perfect precisely when the staged tree $T_{G}$ is a so called _balanced
tree_ , which in turn is equivalent to the associated prime ideal being
binomial in the given variables, [7]. We summarize this result in Theorem 3.1.

######  Theorem 3.1 ([7], [8], [14]).

Let $G$ be a Bayesian network. The ideal $P_{G}$ is binomial in the given
variables if and only if $G$ is perfect.

In [12] the class of toric staged trees is extended by considering a change of
variables. We shall apply this result to obtain a class of toric Bayesian
nets. To do this we restate the special case of [12, Theorem 5.4] concerning
stratified staged trees as Theorem 3.2. A _subtree_ of a staged tree $T$
always inherits the edge labels from $T$. For two subtrees to be _identical_
their edge labelings must be identical. For a vertex $v$ in a staged tree $T$,
the _induced subtree of $v$_ is the subtree $T(v)$ containing every directed
path starting in $v$.

######  Theorem 3.2 ([12]).

For a stratified staged tree $T$ and an integer $d\geq 0$, let $S$ be the
subtree with same root as $T$ and with leaves on level $d$. Suppose

  1. 1.

$S$ is balanced, and

  2. 2.

for any vertex $v$ on level $\geq d$ the induced subtrees of the children of
$v$ are identical.

Then the prime ideal associated to $T$ is toric after a linear change of
variables.

Let us analyze the second condition. Take a vertex $v$ on level $d$, and let
$v_{1}$ and $v_{2}$ be children of $v$. Then the induced subtrees $T(v_{1})$
and $T(v_{2})$ are identical, so in particular $v_{1}\sim v_{2}$. But
condition 2 should also hold for $v_{1}$, so all children of $v_{1}$ must be
in the same stage. As $T(v_{1})$ and $T(v_{2})$ are identical the $k$-th
children of $v_{1}$ and $v_{2}$ must be in the same stage. Then in fact all
grandchildren of $v$ must be in the same stage. Continuing this argument we
can rephrase condition 2 as

  1. 2’.

For any vertex $u$ on level $d$ and any vertices $v,w$ in $T(u)$ on the same
level, $v\sim w$.

Theorem 3.2 translates to the following statement on the DAG $G$, in the case
$T=T_{G}$.

######  Theorem 3.3.

Let $G$ be a Bayesian network for which the induced subgraph on the non-sinks
is perfect. Then the ideal $P_{G}$ is toric, after a linear change of
variables.

###### Proof.

Suppose the induced subgraph on the non-sinks of $G$ if perfect. We may assume
that the vertices are ordered so that the induced subgraph $H$ on the vertices
$1,\ldots,d$ is perfect, and that every vertex $i>d$ is a sink. Then condition
1 of Theorem 3.2 is satisfied with $S=T_{H}$. Let now $u$ be a vertex on level
$d$ in the staged tree $T_{G}$, and take two vertices $v$, $w$ on level $j$
both contained in $T(u)$. As $\operatorname{Pa}(j)\subseteq\\{1,\ldots,d\\}$
it follows that $v\sim w$. ∎

######  Remark 3.4.

The algorithm in the proof of [12, Theorem 5.4] produces the change of
variables which makes the ideal $P_{G}$ binomial. In the case of Theorem 3.3
we get the following. For a given integer vector $u=(u_{1},\ldots,u_{n})$ with
$1\leq u_{i}\leq\kappa_{i}$ let $u+$ be the vector obtained from $u$ by
replacing $u_{i}$ by the symbol + if $i$ is a sink and $u_{i}=\kappa_{i}$. The
set of all linear forms $x_{u+}$ obtained in this way is the basis of
$\mathbb{R}[\boldsymbol{x}]$ for which $P_{G}$ is binomial. The image of
$x_{u+}$ is then obtained by applying the substitution

$\theta(X_{j}=\kappa_{j}\ |\ X_{i}=u_{i}\ \text{for}\
i\in\operatorname{Pa}(j))\mapsto z\quad\text{if}\ j\ \text{is a sink}$

to (2). This gives the parametrization of the toric variety
$\mathcal{V}(P_{G})$.

######  Example 3.5.

Let $G$ be the Bayesian network of four binary random variables given in
Figure 1. The DAG is not perfect, as Pa$(3)=\\{1,2\\}$ but there is no edge
between 1 and 2. But if we remove the two sinks 3 and 4 the resulting graph is
perfect, so $P_{G}$ is toric by Theorem 3.3. The basis for
$\mathbb{R}[\boldsymbol{x}]$ and the monomial parameterization is given by

$\begin{aligned}
x_{1111}&\mapsto\theta_{11}\theta_{21}\theta_{311}\theta_{411}\\\
x_{111+}&\mapsto\theta_{11}\theta_{21}\theta_{311}z\\\
x_{11+1}&\mapsto\theta_{11}\theta_{21}z\theta_{411}\\\
x_{11++}&\mapsto\theta_{11}\theta_{21}z^{2}\\\
x_{1211}&\mapsto\theta_{11}\theta_{22}\theta_{321}\theta_{421}\\\
x_{121+}&\mapsto\theta_{11}\theta_{22}\theta_{321}z\\\
x_{12+1}&\mapsto\theta_{11}\theta_{22}z\theta_{421}\\\
x_{12++}&\mapsto\theta_{11}\theta_{22}z^{2}\end{aligned}\qquad\quad\begin{aligned}
x_{2111}&\mapsto\theta_{12}\theta_{21}\theta_{331}\theta_{431}\\\
x_{211+}&\mapsto\theta_{12}\theta_{21}\theta_{331}z\\\
x_{21+1}&\mapsto\theta_{12}\theta_{21}z\theta_{431}\\\
x_{21++}&\mapsto\theta_{12}\theta_{21}z^{2}\\\
x_{2211}&\mapsto\theta_{12}\theta_{22}\theta_{341}\theta_{441}\\\
x_{221+}&\mapsto\theta_{12}\theta_{22}\theta_{341}z\\\
x_{22+1}&\mapsto\theta_{12}\theta_{22}z\theta_{441}\\\
x_{22++}&\mapsto\theta_{12}\theta_{22}z^{2}.\end{aligned}\vspace{-20pt}$

∎

Now the question is: Are there more toric Bayesian networks, not characterized
by Theorem 3.3? In [12, Conjecture 7.1] it is conjectured that all Bayesian
networks are toric. However, Theorem 3.6 provides a counterexample to the
conjecture.

Figure 2: DAG and staged tree representation of a non-toric Bayesian network

######  Theorem 3.6.

Let $G$ be the Bayesian network on four binary random variables illustrated in
Figure 2. Then there is no linear change of basis for which the prime ideal
$P_{G}$ is toric.

######  Remark 3.7.

The ideal $P_{G}$ is toric if and only if the quotient ring
$\mathbb{R}[\boldsymbol{x}]/P_{G}$ is isomorphic to a subring
$S=\mathbb{R}[m_{1},\ldots,m_{s}]$ of a polynomial ring, where
$m_{1},\ldots,m_{s}$ is a minimal generating set of monomials. We know that
$\mathbb{R}[\boldsymbol{x}]/P_{G}$ is indeed isomorphic to a subring
$A\subseteq\mathbb{R}[\Theta,z]$ minimally generated by 16 polynomials.
Explicit expressions of the generators are given in Example 5.1, and one
easily checks that they are linearly independent. Finding a change of
variables under which $P_{G}$ is binomial is equivalent to finding an
isomorphism $\psi:S\to A$. Such an isomorphism $\psi$ sends the given
generating set of $S$ to a generating set of $A$. It is therefore necessary
that $s=16$, and for each $i$ the image $\psi(m_{i})$ must be a linear
combination of the generators of $A$. Hence it is enough to consider _linear_
changes of variables in order to determine whether $P_{G}$ is toric or not.

The proof of Theorem 3.6 uses matrix representation of quadratic forms. Every
quadratic form $f$ on variables $x_{1},\ldots x_{N}$ can be represented by a
symmetric coefficient matrix $S$ by $f=x^{\top}Sx$. Here $x$ denotes the
column vector $(x_{1},\ldots,x_{N})$. The _rank of $f$_ refers to the rank of
$S$, which is invariant under linear change of coordinates. If $f$ is a
binomial then the rank is at most four.

We also recall some basic facts about minimal generating sets of homogeneous
ideals of polynomial rings. A generating set is _minimal_ if no proper subset
generates the same ideal. Minimal generating sets are not unique in general.
However, if $f_{1},\ldots,f_{r}$ and $g_{1},\ldots,g_{s}$ are two minimal
homogeneous generating sets for the same ideal, then $r=s$ and (after possibly
reindexing) $\deg(f_{i})=\deg(g_{i})$.

###### Proof of Theorem 3.6.

The computational software Macaulay2 [11] will be used in two steps of this
proof.

The global Markov property of $G$ consists of $2\perp\\!\\!\\!\perp 1$ and
$4\perp\\!\\!\\!\perp 1\ |\ \\{2,3\\}$. The ideal $I_{2\perp\\!\\!\\!\perp 1}$
is generated by the determinant

$f_{1}=\begin{vmatrix}x_{11++}&x_{21++}\\\ x_{12++}&x_{22++}\end{vmatrix},$

and $I_{4\perp\\!\\!\\!\perp 1|\\{2,3\\}}$ is generated by the four
determinants

$\displaystyle f_{2}=\begin{vmatrix}x_{1111}&x_{2111}\\\
x_{1112}&x_{2112}\end{vmatrix},\quad f_{3}=\begin{vmatrix}x_{1121}&x_{2121}\\\
x_{1122}&x_{2122}\end{vmatrix},$ $\displaystyle
f_{4}=\begin{vmatrix}x_{1211}&x_{2211}\\\ x_{1212}&x_{2212}\end{vmatrix},\quad
f_{5}=\begin{vmatrix}x_{1221}&x_{2221}\\\ x_{1222}&x_{2222}\end{vmatrix}.$

The Macaulay2 commands

    I=ideal(f_1, f_2, f_3, f_4, f_5)
    trim I
    isPrime I

with $f_{1},\ldots,f_{5}$ being the polynomials given above, verifies that
this is a minimal generating set for the ideal
$I_{\operatorname{global}(G)}=I_{2\perp\\!\\!\\!\perp
1}+I_{4\perp\\!\\!\\!\perp 1|\\{2,3\\}}$. Moreover, the last line tells us
that $I_{\operatorname{global}(G)}$ is a prime ideal. As $P_{G}$ is a minimal
prime of $I_{\operatorname{global}(G)}$ we have
$P_{G}=I_{\operatorname{global}(G)}$. Hence any minimal generating set of
$P_{G}$ consists of five linear combinations
$\lambda_{1}f_{1}+\dots+\lambda_{5}f_{5}$. Such a quadratic form is
represented by the symmetric matrix

$S=\begin{pmatrix}0&A\\\ A^{\top}&0\end{pmatrix}\quad\text{where}\quad
A=\left(\begin{smallmatrix}0&\lambda_{2}&0&0&\lambda_{1}&\lambda_{1}&\lambda_{1}&\lambda_{1}\\\
-\lambda_{2}&0&0&0&\lambda_{1}&\lambda_{1}&\lambda_{1}&\lambda_{1}\\\
0&0&0&\lambda_{3}&\lambda_{1}&\lambda_{1}&\lambda_{1}&\lambda_{1}\\\
0&0&-\lambda_{3}&0&\lambda_{1}&\lambda_{1}&\lambda_{1}&\lambda_{1}\\\
-\lambda_{1}&-\lambda_{1}&-\lambda_{1}&-\lambda_{1}&0&\lambda_{4}&0&0\\\
-\lambda_{1}&-\lambda_{1}&-\lambda_{1}&-\lambda_{1}&-\lambda_{4}&0&0&0\\\
-\lambda_{1}&-\lambda_{1}&-\lambda_{1}&-\lambda_{1}&0&0&0&\lambda_{5}\\\
-\lambda_{1}&-\lambda_{1}&-\lambda_{1}&-\lambda_{1}&0&0&-\lambda_{5}&0\\\
\end{smallmatrix}\right)$

in the basis $\\{x_{1111},x_{1112},\ldots,x_{2222}\\}$. For $S$ to represent a
binomial the rank must be at most four, so all ${5\times 5}$-minors must
vanish. Running the commands

    J = radical minors(5,S)
    primaryDecomposition J

where $S$ is the matrix given above with entries in a polynomial ring,
computes the radical of the ideal of $5\times 5$-minors as

$(\lambda_{1}\lambda_{2},\lambda_{1}\lambda_{3},\lambda_{1}\lambda_{4},\lambda_{1}\lambda_{5},\lambda_{2}\lambda_{3},\lambda_{2}\lambda_{4},\lambda_{2}\lambda_{5},\lambda_{3}\lambda_{4},\lambda_{3}\lambda_{5},\lambda_{4}\lambda_{5})$

which has the primary decomposition

$(\lambda_{2},\lambda_{3},\lambda_{4},\lambda_{5})\cap(\lambda_{1},\lambda_{3},\lambda_{4},\lambda_{5})\cap\dots\cap(\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4}).$

This shows that $S$ has rank less than five only if all but one
$\lambda_{i}=0$, so the only possible binomials are $f_{1},\ldots,f_{5}$
themselves. Indeed, $f_{2},\ldots,f_{5}$ are binomials, and $f_{1}$ is a
binomial after a change of variables. The next step is to see that there is no
change of variables for which they are all binomials. Any quadratic binomial
is the determinant of a $2\times 2$-matrix where the entries are variables.
The fact that $f_{1},\ldots,f_{5}$ are all of rank four means that we are
looking for $2\times 2$-matrices with four distinct entries. Then there must
be a pair $f_{i}$, $f_{j}$ which share a variable. For such a pair,
$f_{i}+f_{j}$ is a quadratic form in at most seven variables, so it has rank
at most seven. It is easily verified that each linear combination
$f_{i}+cf_{j}$, with $c\neq 0$, in fact has rank eight. We can conclude that
there is no linear change of variables which makes all of $f_{1},\ldots,f_{5}$
binomials, and hence there is no basis for which $P_{G}$ is a binomial ideal.
∎

##  4 Quadratic relations

For any Bayesian network $G$ we have the ideal containment
$I_{\operatorname{global}(G)}\subseteq P_{G}$, and the ideal
$I_{\operatorname{global}(G)}$ is generated in degree two by definition. The
prime ideal $P_{G}$ is not always generated in degree two, so the two ideals
are not equal in general. It is conjectured in [9] that the two ideals agree
in degree two.

######  Conjecture 4.1 ([9, Conjecture 7]).

For any Bayesian network $G$, the quadrics of $P_{G}$ generate the ideal
$I_{\operatorname{global}(G)}$.

We shall now prove the conjecture for the toric Bayesian networks covered by
Theorem 3.3.

######  Theorem 4.2.

Let $G$ be a Bayesian network for which the induced subgraph on all non-sinks
is perfect. Then $I_{\operatorname{global}(G)}$ is generated by all quadrics
of $P_{G}$.

###### Proof.

By Theorem 3.3 the ideal $P_{G}$ is toric in this case, and we use the basis
for $\mathbb{R}[\boldsymbol{x}]$ given in Remark 3.4. The idea is to prove
that any quadratic binomial in $P_{G}$ belongs to
$I_{\operatorname{global}(G)}$. So, take
$x_{u}x_{u^{\prime}}-x_{v}x_{v^{\prime}}$ where $u,u^{\prime},v$ and
$v^{\prime}$ are $n$-vectors with entries in $\mathbb{Z}\cup\\{+\\}$ as
described in Remark 3.4. In particular, the $i$-th entry can only be a + if
$i$ is a sink in $G$.

The image of $x_{u}$ in
$\mathbb{R}[\Theta,z]/\langle\boldsymbol{\theta}-z\rangle$ is $p=p_{1}\cdots
p_{n}$ where

$p_{j}=\begin{cases}z&\text{if}\ u_{j}=+\\\ \theta(X_{j}=u_{j}\ |\
X_{i}=u_{i}\ \text{for}\ i\in\operatorname{Pa}(j))&\text{if}\
u_{j}\neq+.\end{cases}$

In the same way we write the images of $x_{u^{\prime}},x_{v}$ and
$x_{v^{\prime}}$ as monomials $p^{\prime}=p_{1}^{\prime}\cdots
p_{n}^{\prime}$, $q=q_{1}\cdots q_{n}$, and $q^{\prime}=q_{1}^{\prime}\cdots
q_{n}^{\prime}$. The equality $pp^{\prime}=qq^{\prime}$ implies

$\begin{cases}p_{i}=q_{i}\\\
p_{i}^{\prime}=q_{i}^{\prime}\end{cases}\quad\text{or}\quad\begin{cases}p_{i}=q_{i}^{\prime}\\\
p_{i}^{\prime}=q_{i}\end{cases}\quad\text{for each }i=1,\ldots,n.$ (4)

For $x_{u}x_{u^{\prime}}-x_{v}x_{v^{\prime}}$ to be of the form (3) we can not
have $u_{j}\neq+$ while $u_{j}^{\prime}=+$. So suppose we are in this
situation, and say $p_{j}=q_{j}$ and $p_{j}^{\prime}=q_{j}^{\prime}$. As
$u_{j}\neq+$ we have $z\neq p_{j}=q_{j}$ and it follows that $u_{i}=v_{i}$ for
each $i\in\operatorname{Pa}(j)$. By (4) we then also have
$u_{i}^{\prime}=v_{i}^{\prime}$ for each $i\in\operatorname{Pa}(j)$. This
allows us to replace $u_{j}^{\prime}=+$ and $v_{j}^{\prime}=+$ by integers
$1,\ldots,\kappa_{j}$ and in this way produce valid relations in $P_{G}$. As
$j$ is not a parent, only $p_{j}^{\prime}$ and $q_{j}^{\prime}$ are affected
by this operation. Let $f_{1},\ldots,f_{\kappa_{j}}$ denote the quadratic
forms obtained from $x_{u}x_{u^{\prime}}-x_{v}x_{v^{\prime}}$ by changing the
$j$-th entries of $u^{\prime}$ and $v^{\prime}$ to integers. Then

$x_{u}x_{u^{\prime}}-x_{v}x_{v^{\prime}}=f_{1}+\dots+f_{\kappa_{j}}.$

By this argument we can now restrict to the case where for each $j$ either all
of $u_{j},u^{\prime}_{j},v_{j}$, and $v_{j}^{\prime}$ are integers or all +.

Now let $A,B,C$ be subsets of $\\{1,\ldots,n\\}$ defined by

$\displaystyle C$ $\displaystyle=\\{i\ |\
u_{i}=u_{i}^{\prime}=v_{i}=v_{i}^{\prime}\neq+\\}$ $\displaystyle A$
$\displaystyle=\\{i\ |\ p_{i}=q_{i}\neq
p_{i}^{\prime}=q_{i}^{\prime}\\}\setminus C$ $\displaystyle B$
$\displaystyle=\\{i\ |\ p_{i}=q_{i}^{\prime}\neq
p_{i}^{\prime}=q_{i}\\}\setminus C.$

Note that if $i\notin A\cup B\cup C$ then
$p_{i}=p_{i}^{\prime}=q_{i}=q_{i}^{\prime}=z$ and in particular $i$ is a sink.
With these sets $A,B,C$ our binomial relation
$x_{u}x_{u^{\prime}}-x_{v}x_{v^{\prime}}$ is of the form (3), but we need to
verify that the statement $A\perp\\!\\!\\!\perp B\ |\ C$ is true. We do this
by the graph theoretical interpretation. So, assume we have a trail $\pi$
connecting vertices $k\in A$ and $\ell\in B$. We want to prove that there is a
vertex $j$ on $\pi$ satisfying one of the conditions _S1_ or _S2_ given in
Section 2.3. We may assume that the vertex next to $k$ on $\pi$ is not in $A$,
because if this is the case we can consider the shorter subtrail instead.
Let’s first consider three special cases.

  1. 1.

$k\to\ell$ or $k\leftarrow\ell$ is an edge. Say $k\leftarrow\ell$. As $k\in A$
we have $p_{k}=q_{k}$. This requires $u_{i}=v_{i}$ for each
$i\in\operatorname{Pa}(k)$, so in particular $u_{\ell}=v_{\ell}$. As $\ell\in
B$ we have $p_{\ell}=q_{\ell}^{\prime}$ and $p_{\ell}^{\prime}=q_{\ell}$.
Altogether we then have
$u_{\ell}=v_{\ell}=u^{\prime}_{\ell}=v^{\prime}_{\ell}$, so $\ell\in C$,
contradicting $\ell\in B$. Similarly we get a contradiction if $k\to\ell$ is
an edge. We can conclude that this situation does not occur.

  2. 2.

$\pi=k\to j\leftarrow\ell$ for some $j$. As $k\in A$ we have $p_{k}=q_{k}\neq
z$ and $p^{\prime}_{k}=q_{k}^{\prime}\neq z$. In particular $u_{k}=v_{k}$ and
$u^{\prime}_{k}=v_{k}^{\prime}$. Then $u_{k}\neq v_{k}^{\prime}$ as $k\notin
C$. In the same way $\ell\in B$ implies $u_{\ell}\neq v_{\ell}$. By (4) we
have $p_{j}=q_{j}$ or $p_{j}=q_{j}^{\prime}$. If $p_{j}\neq z$ then
$p_{j}=q_{j}$ would imply $u_{\ell}=v_{\ell}$ and $p_{j}=q_{j}^{\prime}$ would
imply $u_{k}=v_{k}^{\prime}$ as $k,\ell\in\operatorname{Pa}(j)$. So $p_{j}=z$,
which then implies $u_{j}=+$ and $j\notin C$. We have proved that $j$
satisfies condition _S2_.

  3. 3.

$\pi=k\leftarrow j\cdots$. Since $j$ is not a sink $j\in A\cup B\cup C$. By
assumption $j\notin A$, and we cannot have $j\in B$ by the same argument as in
1 above. So we can conclude $j\in C$, and therefore satisfies condition S1.

Next, we assume $\pi=k\to j\cdots$ and argue by induction over the length of
$\pi$. As we saw in the first special case $j\notin B$, and $j\notin A$ by
assumption. If $j\notin C$ then $j$ is a sink, so $\pi=k\to j\leftarrow\cdots$
and condition S2 is satisfied. Assume $j\in C$. Then S1 is satisfied, unless
$\pi=k\to j\leftarrow j^{\prime}\cdots$. Suppose, in this case, that $j$ is a
sink. As $j^{\prime}$ is not a sink $j^{\prime}\in A\cup B\cup C$. If
$j^{\prime}\in A$ we can reduce to a shorter trail, and we are done by
induction. We cannot have $j^{\prime}\in B$ as this would imply $j\notin C$ by
2. Hence we are left with $j^{\prime}\in C$, so $j^{\prime}$ satisfies S1.
Finally, suppose $j$ is not a sink. Then there is an edge $k\to j^{\prime}$ or
$k\leftarrow j^{\prime}$, as otherwise the induced subgraph on the non-sinks
of $G$ would not be perfect. The case $k\leftarrow j^{\prime}$ is already
covered by 3 above. Assume we have the edge $k\to j^{\prime}$. By induction
there is a $j^{\prime\prime}$ on the shorter trail $k\to j^{\prime}\cdots\ell$
satisfying S1 or S2. Then $j^{\prime\prime}$ satisfies these conditions also
considered as a vertex on $\pi$, except in the case of S2 and
$j^{\prime\prime}=j^{\prime}$. But this cannot happen as $j^{\prime}$ has a
descendant in $C$, namely $j$. We have now proved that the statement
$A\perp\\!\\!\\!\perp B\ |\ C$ holds. ∎

It is well known that the ideal $P_{G}$ of a Bayesian network is quadratic if
$G$ is perfect. It is proved in [14] that models given by perfect DAGs are the
same as decomposable undirected graphical models. Those in turn have ideals
with quadratic Gröbner basis, [13]. Alternatively, proofs for the more general
result that prime ideals of balanced staged trees have quadratic Gröbner bases
can be found in [1] and [12]. Together with Theorem 4.2 we recover Corollary
4.3, which was originally proved in [19] and [6]. See also the discussion
after Theorem 4.3 in [10].

######  Corollary 4.3 ([6], [19]).

Let $G$ Bayesian network given by a perfect DAG. Then
$I_{\operatorname{global}(G)}=P_{G}$.

This leads to the question for which of the toric Bayesian networks in Theorem
3.3 we have $I_{\operatorname{global}(G)}=P_{G}$. That is, when is $P_{G}$
quadratic? Adapting the terminology from [9] we say that a DAG has an _induced
cycle_ if there is an induced subgraph consisting of two directed paths
sharing the same start and end points but are otherwise disjoint. Among all
Bayesian networks on four binary random variables that satisfy the hypothesis
of Theorem 3.3, there are two for which $I_{\operatorname{global}(G)}\neq
P_{G}$. These are networks 15 and 17 in [9, Table 1], and those are precisely
the two DAGs on four vertices with an induced cycle of length more than three.
In Theorem 4.4 we see that such networks will always have relations of degree
greater than two.

######  Theorem 4.4.

Let $G$ be a Bayesian network for which the induced subgraph on all non-sinks
is perfect. If $P_{G}$ is quadratic then $G$ contains no induced cycle of
length more than three.

In the proof of Theorem 4.4 we need the following lemma.

######  Lemma 4.5.

Let $G$ be a Bayesian network on vertices $1,\ldots,n$, and let $G^{\prime}$
be the induced subgraph on $1,\ldots,n-1$. If a minimal generating set for
$P_{G^{\prime}}$ has an element of degree $d>2$, then so does any minimal
generating set for $P_{G}$.

###### Proof.

Let $R$ denote the polynomial ring over $\mathbb{R}$ on variables
$x_{v_{1}\ldots v_{n}}$ with $1\leq v_{i}\leq\kappa_{i}$ for $i=1,\ldots,n$.
Similarly, let $R^{\prime}$ denote the polynomial ring on variables
$x_{v_{1}\ldots v_{n-1}}$ with $1\leq v_{i}\leq\kappa_{i}$ for
$i=1,\ldots,n-1$. Then we have the two maps

$\varphi:R\to\mathbb{R}[\Theta,z]/\langle\boldsymbol{\theta}-z\rangle\quad\text{and}\quad\varphi^{\prime}:R^{\prime}\to\mathbb{R}[\Theta,z]/\langle\boldsymbol{\theta}-z\rangle$

so that $P_{G}=\ker\varphi$ and $P_{G^{\prime}}=\ker\varphi^{\prime}$. Define
an embedding

$\displaystyle\epsilon:$ $\displaystyle R^{\prime}\hookrightarrow R$
$\displaystyle x_{v_{1}\ldots v_{n}}\mapsto x_{v_{1}\ldots v_{n-1}+}.$

Then $\epsilon(P_{G^{\prime}})\subseteq P_{G}$. Let $\rho:\Theta\to\mathbb{R}$
be a map assigning values to the edge labels respecting the sum-to-one
conditions as described in (1). We define a projection

$\displaystyle\psi:$ $\displaystyle R\to R^{\prime}$ $\displaystyle
x_{v_{1}\ldots,v_{n}}\mapsto x_{v_{1}\ldots
v_{n-1}}\cdot\rho(\theta(X_{n}=v_{n}\ |\ X_{i}=v_{i}\ \text{for}\
i\in\operatorname{Pa}(n))).$

Then $\psi(P_{G})\subseteq P_{G^{\prime}}$ and
$\psi(\epsilon(x_{v_{1}\ldots,v_{n-1}}))=x_{v_{1}\ldots,v_{n-1}}$. Now, assume
$P_{G^{\prime}}$ has a homogeneous minimal generator $f$ of degree $d>2$. Then
$\epsilon(f)$ is an element of degree $d$ in $P_{G}$. If $P_{G}$ would not
have minimal generators of degree $d$, then
$\epsilon(f)=h_{1}g_{1}+\dots+h_{t}g_{t}$ for some $g_{1},\ldots,g_{t}\in
P_{G}$ of degrees all less than $d$. But then

$f=\psi(\epsilon(f))=\psi(h_{1}g_{1}+\dots+h_{t}g_{t})=\psi(h_{1})\psi(g_{1})+\dots+\psi(h_{t})\psi(g_{t})$

would contradict $f$ being a minimal generator. Hence $P_{G}$ also has minimal
generators of degree $d$. ∎

###### Proof of Theorem 4.4.

Let $G$ be a Bayesian network such that the induced subgraph on the non-sinks
is perfect. In addition, assume that $G$ has a induced cycle of length more
than three. We shall prove that there is a relation of degree four in $P_{G}$
which cannot be reduced by the quadrics of $P_{G}$.

Let $\pi_{1}$ and $\pi_{2}$ be the two directed paths who constitute the
induced cycle of length more than three. The common endpoint of $\pi_{1}$ and
$\pi_{2}$ must be a sink, otherwise the induced subgraph on the non-sinks of
$G$ cannot be perfect. By Remark 2.2 we may number the vertices of $G$ in a
suitable way, as long as the numbering respects the direction of the edges. In
particular we can give the sinks consecutive numbers ending with $n$.
Moreover, we can then switch the numbers of two sinks without violating the
direction of the edges. If there is more than one sink we order them so that
the endpoint of $\pi_{1}$ and $\pi_{2}$ is not $n$. Then we can apply Lemma
4.5 to remove $n$. By repeating this argument we can reduce to the case where
the endpoint of $\pi_{1}$ and $\pi_{2}$ is $n$, which is the only sink. This
implies that $G$ is connected, and the induced subgraph on
$\\{1,\ldots,n-1\\}$ is perfect.

Let $k_{1}$ and $k_{2}$ denote the parents of $n$ on $\pi_{1}$ and $\pi_{2}$.
Our next step is to define disjoint vertex sets $A$, $B$, $C$ such that

  * •

$A\perp\\!\\!\\!\perp B\ |\ C$ ,

  * •

$A\cup B\cup C=\\{1,\ldots,n-1\\}$,

  * •

$k_{1}\in A$, and the induced subgraph on $A$ is connected,

  * •

$k_{2}\in B$, and the induced subgraph on $B$ is connected,

  * •

every vertex in $C$ has a child or parent in $A$, and a child or parent in
$B$.

We construct $A$, $B$, and $C$ through three steps. To start, let
$A=\\{k_{1}\\}$ and $B=\\{k_{2}\\}$, and let $C$ be the set of all vertices
that lies on a trail connecting $k_{1}$ and $k_{2}$, excluding $k_{1}$,
$k_{2}$ and $n$. Now we claim that $A\perp\\!\\!\\!\perp B\ |\ C$. Indeed, the
only way our choice of $C$ would violate the conditions S1 and S2 for
separating $A$ and $B$ is if there would be a vertex $i$ with
$k_{1}\rightarrow i\leftarrow k_{2}$. But as the induced subgraph on
$\\{1,\ldots,n-1\\}$ is perfect, and there is no edge between $k_{1}$ and
$k_{2}$ this cannot happen. Next, we would like to extend $A$, $B$, and $C$ so
that $A\cup B\cup C=\\{1,\ldots,n-1\\}$. Consider the induced subgraph on
$\\{1,\ldots,n-1\\}\setminus C$. We extend $A$ to be all vertices in the
connected component of $k_{1}$, and $B$ to all vertices in the connected
component of $k_{2}$. Then we add all remaining vertices in
$\\{1,\ldots,n-1\\}$ to $C$. There are no new trails connecting $A$ and $B$ to
consider, as such a trail would also connect $k_{1}$ and $k_{2}$. Hence the
statement $A\perp\\!\\!\\!\perp B\ |\ C$ is still valid. Last, say there is a
vertex $i\in C$ with a child or parent $k\in A$. If $i$ has no child or parent
in $B$ we would like to remove $i$ from $C$ and add it to $A$. If there is no
trail connecting $i$ and $B$ it is clear that this can be done. Suppose there
is a trail $\pi$ connecting $i$ and $B$. We can extend this trail to also
include $k\in A$. Hence there is a vertex on $\pi$ satisfying S1 or S2. Let
$j$ be the vertex next to $i$ on the trail $\pi$. Is $j=n$ then $j$ satisfies
S2, and we can safely move $i$ from $C$ to $A$. Assume $j\neq n$, and recall
that $j\notin B$ as it is a child or parent of $i$. So we must have $j\in
A\cup C$. If $j\in A$ there must be another vertex on $\pi$, between $j$ and
the endpoint in $B$ satisfying S1 or S2, and we can add $i$ to $A$. Say
instead $j\in C$. Then $j$ satisfies S1, unless we have $i\to j\leftarrow\ell$
in $\pi$. Since we are considering a perfect DAG we would then have an edge
between $i$ and $\ell$, and we can repeat the above argument with $\pi$
replaced by a shorter trail. We conclude that the statement
$A\perp\\!\\!\\!\perp B\ |\ C$ is still valid after removing $i$ from $C$ and
adding it to $A$. In the same way we can move a vertex from $C$ to $B$. We
continue doing this until every vertex that remains in $C$ has a parent or
child in $A$, and a parent or child in $B$. Now all five conditions are
satisfied.

Next let’s assign values to the random variables of the vertices in $A,B,C$,
and encode those values in vectors $a,b,c$. In addition, we make a different
assignment $a^{\prime},b^{\prime},c^{\prime}$. We do this so that $a$ and
$a^{\prime}$ differ in every entry, and the same for $b$ and $b^{\prime}$. We
choose $c$ and $c^{\prime}$ so that they have the same entry in $i$ if and
only if $i\in\operatorname{Pa}(n)$. Note that $C$ contains a vertex from
$\pi_{1}$ or $\pi_{2}$, which is not a parent of $n$. Hence $c$ and
$c^{\prime}$ differ in at least one entry. This gives us two quadratic
binomials

$x_{abc}x_{a^{\prime}b^{\prime}c}-x_{a^{\prime}bc}x_{ab^{\prime}c},\quad
x_{abc^{\prime}}x_{a^{\prime}b^{\prime}c^{\prime}}-x_{a^{\prime}bc^{\prime}}x_{ab^{\prime}c^{\prime}}\
\in P_{G}.$

Here $abc$ denotes the $n$-vector with entries determined by $a,b$, and $c$,
and analogously for $a^{\prime}b^{\prime}c$, $a^{\prime}bc$, and so on, as in
(3). As $A\cup B\cup C=\\{1,\ldots,n-1\\}$ the first $n-1$ entries are
integers, and the last entry is +. Let $abc1$ denote the vector $abc$ with the
last entry replaced by $1$, and consider the binomial

$f=x_{abc1}x_{a^{\prime}b^{\prime}c1}x_{a^{\prime}bc^{\prime}1}x_{ab^{\prime}c^{\prime}1}-x_{a^{\prime}bc1}x_{ab^{\prime}c1}x_{abc^{\prime}1}x_{a^{\prime}b^{\prime}c^{\prime}1}.$
(5)

To prove that $f\in P_{G}$ first note that for the edge labels in the staged
tree representation of $G$, we have

$\theta(X_{n}=1\ |\ X_{i}=abc_{i}\ \text{for}\
i\in\operatorname{Pa}(n))=\theta(X_{n}=1\ |\ X_{i}=abc^{\prime}_{i}\
\text{for}\ i\in\operatorname{Pa}(n))$

as $c$ and $c^{\prime}$ agree on the parents of $n$. Let $\theta_{ab}$ denote
this edge label. We define $\theta_{a^{\prime}b}$, $\theta_{ab^{\prime}}$, and
$\theta_{a^{\prime}b^{\prime}}$ analogously. Under the map
$\varphi:\mathbb{R}[\boldsymbol{x}]\to\mathbb{R}[\Theta,z]/\langle\boldsymbol{\theta}-z\rangle$
with $P_{G}=\ker\varphi$ we have

$\displaystyle\varphi(f)=\theta_{ab}\theta_{a^{\prime}b}\theta_{ab^{\prime}}\theta_{a^{\prime}b^{\prime}}\frac{\varphi(x_{abc}x_{a^{\prime}b^{\prime}c}x_{a^{\prime}bc^{\prime}}x_{ab^{\prime}c^{\prime}}-x_{a^{\prime}bc}x_{ab^{\prime}c}x_{abc^{\prime}}x_{a^{\prime}b^{\prime}c^{\prime}})}{z^{4}}=0$

so $f\in P_{G}$.

Now we shall prove that $f$ cannot be reduced by a binomial of degree two in
$P_{G}$. As we have reduced to the case where $n$ is the only sink, and the
induced subgraph on the non-sinks is perfect, $P_{G}$ is a binomial ideal when
using the $x_{u}$’s with $u=(u_{1},\ldots,u_{n})$ where $1\leq
u_{i}\leq\kappa_{i}$ for $1\leq i<n$ and $u_{n}=1,\ldots,\kappa_{n}-1$, or $+$
as basis for the polynomial ring. By Theorem 4.2 the quadrics of $P_{G}$
belongs to $I_{\operatorname{global}(G)}$, so we ask whether $f$ can be
reduced by binomials of the form (3) in the $x_{u}$’s just described. If this
is the case then there is a binomial $g\in I_{\operatorname{global}(G)}$ such
that one of the terms of $g$ divides one of the terms of $f$. This gives us 12
possible terms, one of which must occur as a term of $g$. Let’s first consider
the the case $g=x_{abc1}x_{a^{\prime}b^{\prime}c1}-x_{u}x_{v}$, for some
$u,v$. For a conditional independence statement $D\perp\\!\\!\\!\perp E\ |\ F$
to give rise to $g$ it is necessary that $D\cup E\cup F=\\{1,\ldots,n\\}$, and
$F\subseteq\\{i\ |\ abc1_{i}=a^{\prime}b^{\prime}c1_{i}\\}$. If there is a
$j\notin F$ such that $abc1_{j}=a^{\prime}b^{\prime}c1_{j}$ then the statement
$D\setminus\\{j\\}\perp\\!\\!\\!\perp E\setminus\\{j\\}\ |\ F\cup\\{j\\}$ also
gives rise to the binomial $g$, but we need to verify that this conditional
independence statement is true. No new trails connecting $D$ and $E$ can
appear by removing $j$ from $E\cup D$ and adding $j$ to $F$. The problem that
might arise is if $j$ would be the descendant of a vertex $j^{\prime}$
satisfying S2 on a trail $\pi$ connecting $D$ and $E$. In that case there
would be an edge between the parents of $j^{\prime}$ on $\pi$, as the induced
subgraph on the non-sinks is perfect. This produces a shorter trail connecting
$D$ and $E$, and we can find another vertex on $\pi$ satisfying S1 or S2. By
repeating this argument we may assume $F=\\{i\ |\
abc1_{i}=a^{\prime}b^{\prime}c1_{i}\\}$, which is precisely the set
$C\cup\\{n\\}$. Then $k_{1}$ and $k_{2}$ must both be in $D$ (or both in $E$),
otherwise the trail $k_{1}\to n\leftarrow k_{2}$ violates the condition for
$F$ separating $D$ and $E$. Every vertex in $A$ is connected to $k_{1}$ via a
trail inside $A$, so $D$ must contain $A$. But in the same way every vertex of
$B$ is connected to $k_{2}$, so $D$ must contain $B$. We end up with $D=A\cup
B$ and $E=\emptyset$, and then $I_{D\perp\\!\\!\\!\perp E|F}=\langle
0\rangle$.

Another option is $g=x_{abc1}x_{a^{\prime}bc^{\prime}1}-x_{u}x_{v}$, for some
$u,v$. By the same arguments as in the previous case, we are looking for a
conditional independence statement $D\perp\\!\\!\\!\perp E\ |\ F$ with $D\cup
E\cup F=\\{1,\ldots,n\\}$ and

$F=\\{i\ |\
abc1_{i}=a^{\prime}bc^{\prime}1_{i}\\}=B\cup(C\cap\operatorname{Pa}(n))\cup\\{n\\}.$

Then $D\cup E=A\cup(C\setminus\operatorname{Pa}(n))$, and the induced subgraph
on these vertices is connected. Again we are forced to choose $D=\emptyset$ or
$E=\emptyset$, as there are no two proper subsets being separated by $F$. We
get $I_{D\perp\\!\\!\\!\perp E|F}=\langle 0\rangle$ also in this case.

By symmetry, all other possibilities for terms of $g$ leads to the same
conclusion. This proves that $f$ is not generated by binomials of degree two
in $P_{G}$. ∎

Note that both Theorem 4.2 and Theorem 4.4 connects properties of the ideals
$P_{G}$ and $I_{\operatorname{global}(G)}$ with properties of the DAG $G$, not
taking into account the numbers $\kappa_{1},\ldots,\kappa_{n}$ of possible
values of the random variables $X_{1},\ldots,X_{n}$. Can the quadratic toric
ideals $P_{G}$ from Theorem 3.3 be characterized by conditions of the DAG $G$?
We conclude this section with an example showing that the numbers
$\kappa_{1},\ldots,\kappa_{n}$ do play a role when considering Bayesian
networks that are not necessarily toric.

Figure 3: A Bayesian net $G$ for which $P_{G}\neq
I_{\operatorname{global}(G)}$

######  Example 4.6.

The Bayesian network $H$ on four binary random variables with the DAG in
Figure 3 has $P_{H}=I_{\operatorname{global}(H)}$. This is number 21 in [9,
Table 1]. If we instead consider the Bayesian network $G$ on the same DAG, but
where $X_{1}$ takes values $1,2,3$, as illustrated by the staged tree in
Figure 3, then $P_{G}\neq I_{\operatorname{global}(G)}$. To see this, let’s
have a closer look at the generating set of $I_{\operatorname{global}(G)}$. We
have $I_{\operatorname{global}{G}}=I_{2\perp\\!\\!\\!\perp
1}+I_{4\perp\\!\\!\\!\perp\\{1,2\\}|3}$ where $I_{2\perp\\!\\!\\!\perp 1}$ is
generated by the $2\times 2$ minors of the matrix

$\begin{pmatrix}x_{11++}&x_{21++}&x_{31++}\\\
x_{12++}&x_{22++}&x_{32++}\end{pmatrix}$

and $I_{4\perp\\!\\!\\!\perp\\{1,2\\}|3}$ is generated by the $2\times 2$
minors of the two matrices

$\begin{pmatrix}x_{1111}&x_{1211}&x_{2111}&x_{2211}&x_{3111}&x_{3211}\\\
x_{1112}&x_{1212}&x_{2112}&x_{2212}&x_{3112}&x_{3212}\end{pmatrix},$
$\begin{pmatrix}x_{1121}&x_{1221}&x_{2121}&x_{2221}&x_{3121}&x_{3221}\\\
x_{1122}&x_{1222}&x_{2122}&x_{2222}&x_{3122}&x_{3222}\end{pmatrix}.$

Running the Macaulay2 command trim ann(x_1111+x_1112) in the quotient ring
$\mathbb{R}[\boldsymbol{x}]/I_{\operatorname{global}(G)}$ shows that
$x_{111+}$ has zero divisors of degree 3. Hence we have forms $f$ of degree 3
such that $x_{111+}f\in I_{\operatorname{global}(G)}\subseteq P_{G}$, and as
$x_{111+}\notin P_{G}$ we have $f\in P_{G}$. As $f\notin
I_{\operatorname{global}(G)}$ it follows that $P_{G}\neq
I_{\operatorname{global}(G)}$. This means that $P_{G}$ is not quadratic, or
Conjecture 4.1 is wrong.

Hoping to shed some light on the nature of generating sets of ideals $P_{G}$
which are not necessarily toric, we here give a concrete construction of the
forms $f$, deduced by analyzing the output of the Macaulay2 computation. Let

$M=\begin{pmatrix}x_{111+}&x_{211+}&x_{311+}\\\
x_{111+}+x_{112+}&x_{211+}+x_{212+}&x_{311+}+x_{312+}\\\
x_{121+}+x_{122+}&x_{221+}+x_{222+}&x_{321+}+x_{322+}\end{pmatrix}.$

Note that rows 2 and 3 are the matrix defining $I_{2\perp\\!\\!\\!\perp 1}$,
and hence $\det(M)\in I_{\operatorname{global}(G)}$. If we were to delete all
terms $x_{ij2+}$ in $M$ the resulting matrix has determinant zero, as rows 1
and 2 becomes identical. Hence, when expanding $\det(M)$ as a polynomial in
$x_{ijk+}$ the terms only supported in variables $x_{ij1+}$ cancel. Hence we
can write $\det(M)$ as a linear combination of terms $x_{u}x_{v}x_{w}$ where
one of $u,v,w$ has its third entry equal to 1, and another one has its third
entry equal to 2. Next, we obtain a form $f$ from $\det(M)$ by replacing each
term $x_{ij1+}x_{k\ell 2+}x_{mno+}$ by $x_{ij11}x_{k\ell 21}x_{mno+}$.
Considering the map
$\varphi:\mathbb{R}[\boldsymbol{x}]\to\mathbb{R}[\Theta,z]/\langle\boldsymbol{\theta}-z\rangle$
with $P_{G}=\ker\varphi$ we have

$\varphi(x_{ij11}x_{k\ell 21})=\theta(X_{4}=1\ |\ X_{3}=1)\theta(X_{4}=1\ |\
X_{3}=2)\frac{\varphi(x_{ij1+}x_{k\ell 2+})}{z^{2}}.$

Applying this to every term of $f$ we get

$\varphi(f)=\theta(X_{4}=1\ |\ X_{3}=1)\theta(X_{4}=1\ |\
X_{3}=2)\frac{\varphi(\det(M))}{z^{2}}=0.\qed$

To the best of the authors knowledge, there is no known example of a Bayesian
net without induced cycles of length $\geq 3$, and where the induced subgraph
of the non-sinks is perfect, but the ideal $P_{G}$ is not quadratic.

##  5 Open problems

In this last section we suggest three open problems on prime ideals of
Bayesian networks. The first two questions asks whether Theorem 3.3 and
Theorem 4.4 gives complete characterizations of toric Bayesian networks, and
toric Bayesian networks for which $P_{G}=I_{\operatorname{global}(G)}$.

######  Question 1.

Are all toric Bayesian networks characterized by DAGs such that the induced
subgraphs on the non-sinks are perfect?

######  Question 2.

Let $G$ be a Bayesian network such that the induced subgraph on the non-sinks
is perfect. Is $P_{G}=I_{\operatorname{global}(G)}$ if and only if $G$
contains no induced cycle of length greater than three?

If $P_{G}$ is toric then the algebra $\mathbb{R}[\boldsymbol{x}]/P_{G}$ is
isomorphic to a monomial algebra. When $G$ is perfect we know that $P_{G}$ is
toric, and by [12, Theorem 3.10] the algebra
$\mathbb{R}[\boldsymbol{x}]/P_{G}$ is normal and Cohen-Macaulay. Computation
shows that the same holds for every Bayesian network $G$ on four binary random
variables. In the case $G$ is toric the software Normaliz [3] was used to
check whether the monomial parameterization defines a normal algebra. In those
cases where we do not have a monomial parameterization an intermediate step is
needed, as described in Example 5.1.

######  Example 5.1.

Let $G$ be the Bayesian network in Figure 2. We can define $P_{G}$ as the
kernel of the map $\mathbb{R}[\boldsymbol{x}]\to\mathbb{R}[\Theta,z]$ defined
by $x_{ijk\ell}\mapsto f_{ijk\ell}$ where

$\begin{aligned} f_{1111}&=\theta_{1}\theta_{2}\theta_{31}\theta_{41},\\\
f_{1112}&=\theta_{1}\theta_{2}\theta_{31}(z-\theta_{41}),\\\
f_{1121}&=\theta_{1}\theta_{2}(z-\theta_{31})\theta_{42},\\\
f_{1122}&=\theta_{1}\theta_{2}(z-\theta_{31})(z-\theta_{42}),\\\
f_{1211}&=\theta_{1}(z-\theta_{2})\theta_{32}\theta_{43},\\\
f_{1212}&=\theta_{1}(z-\theta_{2})\theta_{32}(z-\theta_{43}),\\\
f_{1221}&=\theta_{1}(z-\theta_{2})(z-\theta_{32})\theta_{44},\\\
f_{1222}&=\theta_{1}(z-\theta_{2})(z-\theta_{32})(z-\theta_{44}),\end{aligned}\
\begin{aligned} f_{2111}&=(z-\theta_{1})\theta_{2}\theta_{33}\theta_{41},\\\
f_{2112}&=(z-\theta_{1})\theta_{2}\theta_{33}(z-\theta_{41}),\\\
f_{2121}&=(z-\theta_{1})\theta_{2}(z-\theta_{33})\theta_{42},\\\
f_{2122}&=(z-\theta_{1})\theta_{2}(z-\theta_{33})(z-\theta_{42}),\\\
f_{2211}&=(z-\theta_{1})(z-\theta_{2})\theta_{34}\theta_{43},\\\
f_{2212}&=(z-\theta_{1})(z-\theta_{2})\theta_{34}(z-\theta_{43}),\\\
f_{2221}&=(z-\theta_{1})(z-\theta_{2})(z-\theta_{34})\theta_{44},\\\
f_{2222}&=(z-\theta_{1})(z-\theta_{2})(z-\theta_{34})(z-\theta_{44}).\end{aligned}$

Then
$A:=\mathbb{R}[f_{1111},\ldots,f_{2222}]\cong\mathbb{R}[\boldsymbol{x}]/P_{G}$.
Let $\succ$ denote the degree reverse lexicographic term order on
$\mathbb{R}[\Theta]$ with
$\theta_{1}\succ\theta_{2}\succ\theta_{31}\succ\dots\succ\theta_{34}\succ\theta_{41}\succ\dots\succ\theta_{44}\succ
z.$ The _initial algebra_ $\operatorname{in}_{\succ}(A)$ is the monomial
algebra generated by all leading terms of polynomials in $A$, w. r. t. the
term order $\succ$. We run the commands

    A = flatten entries gens sagbi B
    inA = A/leadTerm
    N = gens normalToricRing inA
    sort inA == sort N

in Macaulay2 with the packages Normaliz and SubalgebraBases [SubalgebraBases]
loaded, where the input B is a list of the polynomials
$f_{1111},\ldots,f_{2222}$. The first two rows computes the monomials
generating the algebra $\operatorname{in}_{\succ}(A)$, and the third row
computes the normalization of $\operatorname{in}_{\succ}(A)$. The last row
checks that $\operatorname{in}_{\succ}(A)$ and its normalization in fact has
the same generators, so $\operatorname{in}_{\succ}(A)$ is normal. By [5,
Corollary 2.3] the original algebra $A$ is then normal and Cohen-Macaulay. ∎

######  Question 3.

Is the ring $\mathbb{R}[\boldsymbol{x}]/P_{G}$ normal and Cohen-Macaulay for
every Bayesian network $G$?

### Acknowledgements

I would like to thank Aldo Conca for our discussions about commutative algebra
of Bayesian networks, and especially for suggesting the technique used in the
proof of Theorem 3.6. Thanks also to Christiane Görgen for helpful comments on
a draft of this manuscript. Finally, I thank the two anonymous referees for
their careful reading.

## References

  * [1] Lamprini Ananiadi and Eliana Duarte.  Gröbner bases for staged trees.  Algebraic Statistics, 12(1):1–20, 2021.
  * [2] Niko Beerenwinkel, Nicholas Eriksson, and Bernd Sturmfels.  Conjunctive Bayesian networks.  Bernoulli, 13(4):893 – 909, 2007.
  * [3] Winfried Bruns, Bogdan Ichim, Christof Söger, and Ulrich von der Ohe.  Normaliz. Algorithms for rational cones and affine monoids.  Available at https://www.normaliz.uni-osnabrueck.de.
  * [4] Rodrigo A. Collazo, Christiane Görgen, and Jim Q. Smith.  Chain Event Graphs.  CRC Computer Science and Data Analysis Series. Chapman & Hall, 2017.
  * [5] Aldo Conca, Jürgen Herzog, and Giuseppe Valla.  Sagbi bases with applications to blow-up algebras.  Journal für die Reine und Angewandte Mathematik, 474:113–138, 1996\.
  * [6] Adrian Dobra.  Markov bases for decomposable graphical models.  Bernoulli, 9(6):1093–1108, 2003.
  * [7] Eliana Duarte and Christiane Görgen.  Equations defining probability tree models.  Journal of Symbolic Computation, 99:127–146, 2020.
  * [8] Eliana Duarte and Liam Solus.  A new characterization of discrete decomposable graphical models.  Proceedings of the American Mathematical Society, 151:1325–1338, 2023.
  * [9] Luis David Garcia, Michael Stillman, and Bernd Sturmfels.  Algebraic geometry of Bayesian networks.  Journal of Symbolic Computation, 39:331–355, 2005.
  * [10] Dan Geiger, Christopher Meek, and Bernd Sturmfels.  On the toric algebra of graphical models.  The Annals of Statistics, 34(3):1463 – 1492, 2006.
  * [11] Daniel R. Grayson and Michael E. Stillman.  Macaulay2, a software system for research in algebraic geometry.  Available at https://math.uiuc.edu/Macaulay2/.
  * [12] Christiane Görgen, Aida Maraj, and Lisa Nicklasson.  Staged tree models with toric structure.  Journal of Symbolic Computation, 113:242–268, 2022.
  * [13] Serkan Hoşten and Seth Sullivant.  Gröbner bases and polyhedral geometry of reducible and cyclic models.  Journal of Combinatorial Theory, Series A, 100(2):277–301, 2002\.
  * [14] Steffen L. Lauritzen.  Graphical Models.  Oxford Statistical Science Series. Oxford University Press, 1996.
  * [15] Fabio Rapallo.  Toric statistical models: parametric and binomial representations.  Annals of the Institute of Statistical Mathematics, 59:727–740, 2007.
  * [16] Jim Q. Smith and Paul E. Anderson.  Conditional independence and chain event graphs.  Artificial Intelligence, 172(1):42–68, 2008.
  * [17] Bernd Sturmfels.  Solving systems of polynomial equations.  In American Mathematical Society, CBMS Regional Conferences Series, No. 97, 2002.
  * [18] Seth Sullivant.  Algebraic Statistics, volume 194 of Graduate studies in Mathematics.  AMS, 2018.
  * [19] A.R. Takken.  Monte Carlo Goodness-of-fit Tests for Discrete Data.  Ph.D. thesis, Stanford University, 1999.