The d-separation criterion in Categorical Probability

Tobias Fritz
Department of Mathematics, Technikerstr. 13,  A-6020 Innsbruck, Austria

Andreas Klingler
Institute for Theoretical Physics, Technikerstr. 21a,  A-6020 Innsbruck, Austria

[2020]18M30, 62A09 (Primary), 18M35, 60A05, 62D20 (Secondary)

Acknowledgments. We thank Rob Spekkens for the original idea behind the definition of categorical $d$-separation and Patrick Forré for discussion and pointers to the literature. AK acknowledges support from the Stand Alone project P33122-N of the Austrian Science Fund (FWF)

The $d$-separation criterion detects the compatibility of a joint probability distribution with a directed acyclic graph through certain conditional independences. In this work, we study this problem in the context of categorical probability theory by introducing a categorical definition of causal models, a categorical notion of $d$-separation, and proving an abstract version of the $d$-separation criterion. This approach has two main benefits. First, categorical $d$-separation is a very intuitive criterion based on topological connectedness. Second, our results apply in measure-theoretic probability (with standard Borel spaces), and therefore provide a clean proof of the equivalence of local and global Markov properties with causal compatibility for continuous and mixed variables.

§ INTRODUCTION

The $d$-separation criterion [18] is a necessary and sufficient condition for the compatibility of a probability distribution with a causal structure in the form of a directed acyclic graph (DAG).
It states that a joint probability distribution of a collection of random variables is compatible with the DAG—in the sense that each of its nodes is one of the given variables, and each arrow denotes the possibility of causal influence—if and only if the distribution satisfies a list of conditional independence relations encoded in the structure of the DAG.

In this paper, we study this causal compatibility problem in the framework of categorical probability theory. We elaborate on the framework of generalized causal models recently proposed in [10], introduce a categorical notion of $d$-separation, and prove a categorical generalization of the $d$-separation criterion.

The framework of generalized causal models involves freely generated categories called free Markov categories [10].
Starting from a set of morphisms as building blocks (representing the basic causal mechanisms), we construct a morphism in this category by assembling these blocks consistently.
More precisely, a morphism in such a free category is a string diagram consisting of wires and boxes. In our context, these diagrams represent the causal models. Each wire corresponds to a local random variable and each box to a causal mechanism generating one or several new output variables from its input ones.
A morphism in any Markov category is compatible with such a causal model if it can be decomposed in the form specified by the causal model; this generalizes the standard factorization definition of Bayesian networks [6].

Further, we define a categorical notion of $d$-separation in terms of the string diagrams. A causal structure displays $d$-separation of a collection of outputs $\mathcal{Z}$ if it becomes disconnected upon removing the corresponding wires in $\mathcal{Z}$. We show that this is equivalent to classical $d$-separation for the class of causal models for which the latter is defined, namely those corresponding to DAGs.

Finally, we prove an abstract version of the $d$-separation criterion for our categorical notions of causal model and $d$-separation. We show that a given distribution, possibly depending on additional input variables, is compatible with a causal structure if and only if it displays conditional independence between sets of variables whenever the causal model displays $d$-separation for the corresponding sets of wires. This result goes beyond the classical result for “distributions”; it holds for arbitrary morphisms in any suitable Markov category $\cat{C}$. A central structural ingredient in the proof is the assumption that $\cat{C}$ has conditionals [9]. Intuitively, this property states that every Markov kernel with multiple output variables arises by generating one output variable after the other, namely as a function of the input variables and previously generated outputs. Such conditionals exist in the Markov category $\cat{FinStoch}$ which describes discrete random variables, but also for continuous or mixed random variables (technically for variables taking values in standard Borel spaces, but not arbitrary measurable spaces) as well as Gaussian variables. This implies that our definitions and results apply equally easily to all of these cases.

This approach leads to new insights into the structure of $d$-separation and generalizes the classical result, to the best of our knowledge, in two notable directions:

* It gives a criterion for compatibility of Markov kernels with a causal structure rather than probability distributions.[For a different approach to causal compatibility of Markov kernels we refer to [7].] This is because Markov categories describing probabilities have Markov kernels as their morphisms, which therefore become the basic primitives of our formalism.

* It provides a uniform proof of the equivalence between $d$-separation and causal compatibility for discrete variables, continuous variables (or rather arbitrary variables taking values in standard Borel spaces), and Gaussian variables. This follows from the fact that we reason abstractly and even more generally in any Markov category with conditionals. This approach generalizes the $d$-separation criterion on the pure DAG-setting for continuous variables shown for distribution with a density [15, 14], which was later extended to arbitrary variables with values in standard Borel spaces [8].

This paper is organized as follows. In <Ref>, we give a more detailed non-technical overview of the main concepts of this paper, including causal models as string diagrams and categorical $d$-separation.
In <Ref>, we recall and explain the definitions of Markov categories and gs-monoidal categories. In <Ref>, we review the construction of free gs-monoidal and free Markov categories, leading to generalized causal models and causal compatibility for morphisms in Markov categories. In <Ref>, we present the notions of conditionals and conditional independence. In <Ref> we introduce a categorical notion of $d$-separation and prove the main results of this paper, namely the equivalence with classical $d$-separation (<Ref>) and our abstract version of the $d$-separation criterion for causal compatibility (<Ref>).

§ CAUSAL MODELS AND MARKOV CATEGORIES

In this paper, we study causal models, in the sense of Bayesian networks, from a categorical perspective. In order to make this accessible to readers without a formal background in category theory, we outline this paper's main concepts and results in this section.

<Ref> gives a non-technical introduction to the string-diagrammatic formalism representing causal models and its relation to the classical DAG formalism. We then present the concept of causal compatibility in <Ref> as a functorial property.
In <Ref>, we present categorical $d$-separation as a statement about the connectedness of the string diagram and explain our result on the $d$-separation criterion in <Ref>. Therefore, the string diagrammatic approach opens the door for a new perspective on $d$-separation and its connection to causal compatibility.

§.§ Extending Bayesian networks with string diagrams

Traditionally, the definition of Bayesian networks relies on the concept of directed acyclic graphs (DAG), since such a graph encodes the underlying causal structure. To each node $v \in V(G)$ of a DAG $G$ is associated a random variable $X_v$, and each directed arrow $w \to v$ is associated a direct possible causal dependence of the variable $X_v$ on $X_w$.
Formally, if we index the nodes by $1,\ldots,n$, then this means that a joint probability distribution $P$ is compatible with the causal structure $G$ if $P$ factorizes into

\begin{equation*}
P\big(X_1, \ldots, X_n\big) = \prod_{i=1}^{n} P\big(X_i \ | \ \textsf{Pa}(X_i)\big)
\end{equation*}

where $\textsf{Pa}(X_i) = \{X_j: G \text{ contains the arrow } j \to i\}$ is the set of parents of $X_i$ relative to $G$.

In the categorical framework, we can refine the notion of Bayesian networks via string diagrams, an idea that extends the categorical approach developed by Fong [6] and others [19, 20, 12, 13].
These diagrams arise naturally in categorical probability, which refers more generally to recent work on axiomatizing probability theory with simple, algebraic rules which avoid the low-level machinery of measure theory by hiding it in the proofs of the relevant axioms [9].

In categorical probability, a probability measure or probability distribution on a set or measurable space $X$ is a morphism $p: I \to X$, depicted as

\begin{equation*}
\tikzfig{figures/singleOutputProbability}
\end{equation*}

Here $I$ is a singleton set that is not drawn in the diagram, the upper wire represents the probability space $X$, and the box $p$ a probability distribution, considered now as a function with no input and one (random) output in $X$. Depending on the particular context, $p$ can be a finite probability distribution, a Gaussian, or a probability measure on an arbitrary measurable space. A conditional probability distribution—also known as a Markov kernel—is represented as a general morphism $f: X \to Y$, depicted as

\begin{equation*}
\tikzfig{figures/singleOutputMorphism}
\end{equation*}

where the wire $X$ represents the input and $Y$ the output space.
The basic primitives in categorical probability are Markov kernels, of which probability distributions as above are special cases obtained by setting $X = I$.

These morphisms can be composed into new ones. For example, composing $f$ with $p$, pictorially

\begin{equation*}
\tikzfig{figures/composition}
\end{equation*}

gives rise to a new distribution of a random variable with values in $Y$. In the concrete setting, the composition is given by the Chapman-Kolmogorov equation, which reads for discrete distributions as

\begin{equation*}
(f \circ p)(y) \coloneqq \sum_{x \in X} f(y|x) \cdot p(x)
\end{equation*}

and for Markov kernels on arbitrary measurable spaces as

\begin{equation*}
(f \circ p)(A) \coloneqq \int_{X} f(A|x) \, p(\mathrm{d} x).
\end{equation*}

where $A \in \Sigma_Y$, with $\Sigma_Y$ the $\sigma$-algebra of the measurable space $Y$.

Each random variable can be copied or marginalized over, for which there exists special string-diagrammatic notation:

\begin{equation*}
\tikzfig{figures/copy} \qquad \text{ and } \qquad \tikzfig{figures/del}
\end{equation*}

We formally axiomatize the semantics of the resulting string diagram calculus in <Ref> as the definition of a Markov category.
This definition consists of a set of rules which axiomatize the behaviour of Markov kernels.

Each flavour of probability has its own Markov category. There is a Markov category for discrete probabilities (called $\cat{FinStoch}$), one for Gaussian probability ($\cat{Gauss}$), one for probability theory on standard Borel spaces ($\cat{BorelStoch}$), and one for probability theory on arbitrary measurable spaces ($\cat{Stoch}$).
But there are also other Markov categories in which the morphisms are not Markov kernels.
These include the so-called free Markov categories, which form our framework for causal structures which generalize DAGs.
Rather than Markov kernels, the morphisms in a free Markov category are the string diagrams themselves, i.e. all ”networks“ that can be built by wiring together a set of boxes, similar to how an electrical circuit is obtained by wiring together electrical components.
In this way, string diagrams constitute generalized causal models.
In particular, we will see that string diagrams can represent arbitrary DAG causal models.
Consider for example this DAG:

\begin{equation}
\label{eq:DAGScenarioDAG}
\begin{tikzpicture}[scale=0.75, shift={(-5,-3)}]
\draw[fill=white, line width=0.2mm] (0,0) circle (0.8cm) node{\scriptsize $Z$};
\draw[fill=white, line width=0.2mm] (-3,3) circle (0.8cm) node{\scriptsize $X$};
\draw[fill=white, line width=0.2mm] (3,3) circle (0.8cm) node{\scriptsize $Y$};
\draw[fill=white, line width=0.2mm] (0,6) circle (0.8cm) node{\scriptsize $W$};

\draw[-stealth,line width=0.2mm,rotate=45] (0,1) -- (0,3.25);
\draw[-stealth,line width=0.2mm,rotate=-45] (0,1) -- (0,3.25);

\draw[-stealth,line width=0.2mm,rotate around={45:(3,3)}] (3,4) -- (3,6.25);
\draw[-stealth,line width=0.2mm,rotate around={-45:(-3,3)}] (-3,4) -- (-3,6.25);

\end{tikzpicture}
\end{equation}

As a string diagram, this causal structure looks like this:

\begin{equation}
\label{eq:DAGScenario}
\tikzfig{figures/DAGscenario1WithoutType}
\end{equation}

Each loose wire[Note that we use the term ”wire“ as referring to an entire connected piece of circuitry, i.e. traversing a black dot in the diagram does not leave the wire.] represents a random variable where the wire's name indicates the variable's name. Further, each variable has a corresponding type, a placeholder for the measurable space in which the variable takes values. Unless necessary, we will not explicitly mention the type of each variable.

In our setting, some wires are connected to an ”output“ representing a variable that is ”observed“ rather than marginalized over, as indicated by the white dots. Note that every variable then becomes an output in at most one way.
In certain situations, we consider causal models where every wire is connected to an output. Throughout the paper, we call such diagrams pure blooms (see <Ref>). Unless stated otherwise, we will denote the output by the name of the wire connected to the output. We will define certain operations, like $d$-separations, only with respect to output wires, highlighting that we cannot address latent variables (i.e. wires that are not connected to an output) in general.

Causal models given by a DAG correspond to pure bloom string diagrams where each box has precisely one output wire, and the input wires represent the parents of the node in the DAG. The following table explains the relation between nodes in a DAG, boxes in the string diagram and the corresponding conditional probability distribution.

p0.2cm p0.5cm |[1pt] >p3.8cm | >p3.8cm | >p3.8cm p0.2cm

1p0.3cm |[1pt]     DAG     string diagram     conditional distribution

[rotate=90] at (0,0) one output;
[-stealth,line width=0.2mm] (0,1) – (0,2);
[-stealth, line width=0.2mm] (0,-2) – (0,-1);
[-stealth, line width=0.2mm, rotate=30] (0,-2) – (0,-1);
[-stealth, line width=0.2mm, rotate=-30] (0,-2) – (0,-1);
[fill=white, line width=0.2mm] (0,0) circle (0.8cm) node$X$;

figures/morphismDAG1     $P(X|ABC)$

[rotate=90] at (0,0) ident. outputs;

[-stealth,line width=0.2mm, rotate=15] (0,1) – (0,2);
[-stealth,line width=0.2mm, rotate=-15] (0,1) – (0,2);
[-stealth, line width=0.2mm] (0,-2) – (0,-1);
[-stealth, line width=0.2mm, rotate=30] (0,-2) – (0,-1);
[-stealth, line width=0.2mm, rotate=-30] (0,-2) – (0,-1);
[fill=white, line width=0.2mm] (0,0) circle (0.8cm) node$X$;

figures/morphismDAG2     $P(XX|ABC)$

[rotate=90] at (0,0) diff. outputs;

figures/morphismDAG3     $P(XY|ABC)$

Using string diagrams themselves as generalized causal models allows us to go beyond the DAG approach in several directions:

* String diagrams in Markov categories describe Markov kernels instead of just probability distributions. Therefore, the string diagram language allows for modeling causal structures with inputs, such as

\begin{equation*}
\tikzfig{figures/tripartiteScenarioOpen}
\end{equation*}

This describes a causal structure in which the input variable at the bottom does not have any particular distribution itself.

* As indicated in the table, boxes in the string diagram can have more than a single output wire. This allows for causal structures like

\begin{equation*}
\tikzfig{figures/DAGImpossibleScenario}
\end{equation*}

which are not native to the DAG framework (see <Ref><ref> for a detailed discussion of this structure).

* String diagrams allow for the use of identical boxes multiple times. In particular, we can represent symmetric causal structures, for example,

\begin{equation*}
\tikzfig{figures/tripartiteScenarioSymmetric}
\end{equation*}

represents a causal structure in which one random variable with distribution $p$ causally influences four others with the additional constraint that the causal mechanism must be the same for all four. Further, in this situation the types of the variables $X_1, \ldots, X_4$ must be the same.

§.§ Causal compatibility for Markov categories

A distribution is compatible with a causal model if it can be written as a composition in precisely the way specified by the corresponding string diagram. In other words, every type $W$ in the string diagram must be mapped to a concrete measurable space $FW$ and every box $f$ to a concrete Markov kernel $Ff$.

In category-theoretic language, this is captured in the following way [6]. A morphism $p$ in a concrete Markov category is compatible with a causal structure $\varphi$ if and only if there exists a Markov functor $F$ such that $p = F\varphi$. Intuitively, this functor acts in the following way:

[thick, gray!30!white] (-11,-4.5) rectangle (-3,7.5);
[thick, gray!30!white] (15.5,-4.5) rectangle (3.5,7.5);
[style=none,gray!70!white] at (-7,6.8) $\cat{FreeMarkov}$;
[style=none,gray!70!white] at (9.5,6.8) $\cat{Stoch}$, $\cat{BorelStoch}$,;
[style=none,gray!70!white] at (9.5,5.6) $\cat{Gauss}$, etc.;

[thick, white, line width=0.15cm] (-6.25, -3.5) to[in=-160, out=-20] (6.25, -3.5);
[thick, blue, opacity=0.3, -stealth] (-6.25, -3.5) to[in=-160, out=-20] (6.25, -3.5);

[thick, white, line width=0.15cm] (-8.25, 3.5) to[in=160, out=20] (4.25, 3.5);
[thick, blue, opacity=0.3, -stealth] (-8.25, 3.5) to[in=160, out=20] (4.25, 3.5);

[thick, white, line width=0.15cm] (-4.25, 3.5) to[in=160, out=20] (8.25, 3.5);
[thick, blue, opacity=0.3, -stealth] (-4.25, 3.5) to[in=160, out=20] (8.25, 3.5);

[thick, white, line width=0.15cm] (-4.25, -0.2) to[in=-160, out=-20] (7.75,-0.2);
[thick, orange, opacity=0.3, -stealth] (-4.25, -0.2) to[in=-160, out=-20] (7.75,-0.2);

[thick, white, line width=0.15cm] (-8.25, -0.2) to[in=-160, out=-20] (3.75,-0.2);
[thick, orange, opacity=0.3, -stealth] (-8.25, -0.2) to[in=-160, out=-20] (3.75,-0.2);

[style=boxSmall] (0) at (-9, 0.5) $f$;
[style=boxSmall] (1) at (-5, 0.5) $g$;
[style=blackDot] (2) at (-7, -1.25) ;
[style=none] (3) at (-7, -3) ;
[style=none] (4) at (-5, 3) ;
[style=none] (5) at (-9, 3) ;
[style=none] (6) at (-5, 3.7) $Y$;
[style=none] (7) at (-9, 3.7) $X$;
[style=none] (8) at (-7, -3.7) $Z$;
[style=whiteDot] at (-7, 3) ;
[style=whiteDot] at (-7, -3) ;
[style=whiteDot] at (-5, 3) ;
[style=whiteDot] at (-9, 3) ;

[style=none] (9) at (-7, 3) ;
[style=boxSmall] (11) at (5, 0.5) $Ff$;
[style=boxSmall] (12) at (9, 0.5) $Fg$;
[style=blackDot] (13) at (7, -1.25) ;
[style=none] (14) at (7, -2.25) ;
[style=none] (15) at (9, 2.25) ;
[style=none] (16) at (5, 2.25) ;
[style=none] (17) at (9, 2.75) $FB$;
[style=none] (18) at (5, 2.75) $FA$;
[style=none] (19) at (7, -2.75) $FC$;
[style=none] (20) at (7, 2.25) ;
[style=none] (21) at (7, 2.75) $FC$;
[style = none] at (10.7,0.8) $\stackrel{!}{=}$;
[style=boxBroad] (22) at (13, 0.5) $p$;
[style=none] (23) at (13, -1.75) ;
[style=none] (24) at (14.5, 2.25) ;
[style=none] (25) at (13, 2.25) ;
[style=none] (26) at (11.5, 2.25) ;
[style=none] (27) at (13.5, 0.75) ;
[style=none] (28) at (12.5, 0.75) ;
[style=none] (29) at (13, -2.75) $Z'$;
[style=none] (30) at (11.5, 2.75) $X'$;
[style=none] (31) at (13, 2.75) $Z'$;
[style=none] (32) at (14.5, 2.75) $Y'$;

[style=edge] (2) to (3.center);
[style=edge, in=-90, out=0] (2) to (1);
[style=edge, in=-90, out=180] (2) to (0);
[style=edge] (1) to (4.center);
[style=edge] (0) to (5.center);
[style=edge] (2) to (9.center);
[style=edge] (13) to (14.center);
[style=edge, in=-90, out=0] (13) to (12);
[style=edge, in=-90, out=180] (13) to (11);
[style=edge] (12) to (15.center);
[style=edge] (11) to (16.center);
[style=edge] (13) to (20.center);
[style=edge] (23.center) to (22);
[style=edge] (22) to (25.center);
[style=edge, in=-90, out=90, looseness=1.25] (27.center) to (24.center);
[style=edge, in=-90, out=90, looseness=1.25] (28.center) to (26.center);

[line width=0.05cm, color=brown!70!black, -stealth] (-2.5, 0.5) – node[midway, above]$F$ (3, 0.5);

where $p$ is the given morphism in a concrete Markov category and $\cat{FreeMarkov}$ the free Markov category whose morphisms capture the causal models. Further, $X$ has type $A$, $Y$ has type $B$, and $Z$ has type $C$.
So if the original $p$ takes input from a measurable space $Z'$ and outputs values in measurable spaces $X'$, $Z'$ and $Y'$, then the types must match in the sense that $FA = X'$ etc.

§.§ Categorical d-separation

The notion of $d$-separation for DAGs is a criterion relating conditional independence in causal models to the causal compatibility with a DAG. In <Ref>, we introduce a categorical notion of $d$-separation from a different perspective. Although this notion looks different and much simpler than classical $d$-separation, we prove that it coincides with the classical one when considering causal models on DAGs.

An output wire $Z$ categorically $d$-separates the output $X$ from output $Y$ if $X$ and $Y$ become disconnected upon marginalizing over all wires that are not involved in the $d$-separation relation and removing the wire $Z$. Consider, for example, the DAG in Equation (<ref>). $Z$ classically $d$-separates $X$ from $Y$, as one can see based on the fact that the only paths between $X$ and $Y$ are the collider $X \rightarrow W \leftarrow Y$ and the fork $X \leftarrow Z \rightarrow Y$. In the corresponding string diagram, Equation (<ref>), we witness categorical $d$-separation by first marginalizing over $W$, then removing the $Z$ wire, and finally observing that $X$ and $Y$ are disconnected, pictorially:

\begin{equation*} \tikzfig{figures/DAGscenario1MARG} \ = \quad \tikzfig{figures/DAGscenario1XYZ} \qquad \xrightarrow{\qquad \Cut_Z \qquad} \qquad \tikzfig{figures/DAGscenario1CUT} \end{equation*}

On the other hand, $X$ is not $d$-separated from $Y$ by $W$ and $Z$ due to the collider $X \rightarrow W \leftarrow Y$. In the string diagram, this is apparent since upon removing the wires $Z$ and $W$,

\begin{equation*} \tikzfig{figures/DAGscenario1WithoutType} \qquad \xrightarrow{\qquad \Cut_{W,Z} \qquad} \qquad \tikzfig{figures/DAGscenario1CUT2} \end{equation*}

$X$ and $Y$ are still connected.

§.§ $d$-separation and causal compatibility

For Bayesian networks, $d$-separation detects conditional independences for any compatible probability distribution. In particular, if two output wires $X$ and $Y$ are $d$-separated by the output wire $Z$, we have $X \perp Y \ | \ Z$.

Conditional independence in Markov categories is defined string diagrammatically. A probability distribution $p$ on a product space $X \times Y \times Z$ displays the conditional independence $X \perp Y \ | \ Z$ if it can be written in the form

\begin{equation*}
\tikzfig{figures/tripartiteProbability} \quad = \quad \tikzfig{figures/conditionalIndepTripartiteProbability}
\end{equation*}

This reflects the classical notion of conditional independence; in the situation of finite probability distributions, it encodes the equation

\begin{equation*} P(X=x,Y=y,Z=z) \,=\, P(X = x| Z = z) \cdot P(Y = y| Z = z) \cdot P(Z = z).
\end{equation*}

But also for Gaussian random variables as well as measures on standard Borel spaces, one recovers the intuitive notions of conditional independence <cit.>. Moreover, the diagrammatic definition is even sufficient to derive the semigraphoid properties <cit.>.
It also generalizes to a notion of conditional independence for morphisms with inputs (see <Ref>).

In <Ref>, we prove that the categorical $d$-separation criterion applies to generalized causal models in Markov categories. For this reason, we define a notion of conditional independence which applies to arbitrary Markov kernels (<Ref>). We first prove the soundness of the $d$-separation, namely, if $Z$ categorically $d$-separates $X$ from $Y$, then $X \perp Y \ | \ Z$ (<Ref>). Second, we prove the completeness of $d$-separation for causal compatibility: if a Markov kernel satisfies the global Markov property for a causal structure (i.e. every $d$-separated triple shows conditional independence), then the Markov kernel is compatible with the structure (see <Ref> for the precise assumptions and also the equivalence with the local Markov property).

A central assumption for the proof is the existence of conditionals (see <Ref>). Intuitively it says that the outputs of any morphism $f$ can be generated successively while having access to all prior information. Conditionals exist in discrete probability, measure-theoretic probability on standard Borel spaces and in Gaussian probability, and this facilitates the application of our results to all of these cases, where the second case includes continuous random variables.

§ GS-MONOIDAL AND MARKOV CATEGORIES

In the following, we recall the definitions of Markov categories and gs-monoidal categories. Markov categories are the basic structure modeling different flavors of probability, including discrete random variables, Gaussian random variables, continuous random variables on standard Borel spaces, or random variables on arbitrary measurable spaces.
We assume some familiarity with symmetric monoidal categories and string diagrams.

The notion of gs-monoidal categories goes back to Gadducci’s thesis <cit.> and an associated paper by Corradini and Gadducci [5]. There, it was considered with a different motivation in the context of term graphs and term graph rewriting.

* A gs-monoidal category $\cat{C}$ is a symmetric monoidal category with monoidal unit $I$ equipped with a commutative comonoid structure for every object $X \in \cat{C}$ given by a counit $\Del{X} \ : \ X \to I$ and a comultiplication $\Copy{X} \ : \ X \to X \otimes X$. In the string diagrammatic notation, these operations are depicted as

\[ \Del{X} \ \coloneqq \  \tikzfig{figures/del} \hspace{3cm} \Copy{X} \ \coloneqq \ \tikzfig{figures/copy}\]

They are required to satisfy the commutative comonoid equations, diagrammatically given by

\begin{equation}
\label{eq:commcom}
\begin{gathered}
\tikzfig{figures/comonoid1} \ = \ \tikzfig{figures/comonoid2} \hspace{1.4cm} \tikzfig{figures/leftCopyContraction} \ = \ \tikzfig{figures/rightCopyContraction} \ = \ \tikzfig{figures/Id} \hspace{1.4cm} \tikzfig{figures/copy_long} \ = \ \tikzfig{figures/copy_swap}
\end{gathered}
\end{equation}

and to be compatible with the monoidal structure, i.e.
\begin{equation}
\label{eq:comonoidalStruc}
\tikzfig{figures/delTensor1} \ = \ \ \ \tikzfig{figures/delTensor2} \hspace{1.5cm} \tikzfig{figures/copy_tensor1} \ \ \ = \  \tikzfig{figures/copy_tensor2}
\end{equation}

as well as

\begin{equation}
\label{eq:copyDelI} \tikzfig{figures/emptyDel} \quad = \quad \tikzfig{EmptyBox} \hspace{2cm} \tikzfig{figures/emptyCopy} \quad = \quad \tikzfig{EmptyBox} \hspace{0.4cm}
\end{equation}

* A gs-monoidal category is called a Markov category if $\Del{}$ is in addition natural, i.e. if for all morphisms $f$,

\begin{equation}
\label{eq:naturality} \tikzfig{figures/fBox} \quad = \quad \tikzfig{figures/longdel}
\end{equation}

We refer to <cit.> for more details on the multifarious history of these notions.
When considering morphisms with multiple outputs, we often denote the collective inputs and outputs as sets instead of tensor products. For example, we write

\begin{equation*}
\tikzfig{figures/MorphismSet1} \ = \quad \tikzfig{figures/MorphismSet2}
\end{equation*}

where $\mathcal{V} = \{A,B,C\}$ and $\mathcal{W} = \{X, Y\}$.
Modulo some abuse of notation, the order of the inputs and outputs is irrelevant since we can always permute the wires, and therefore it is enough to consider $\mathcal{V}$ and $\mathcal{W}$ as sets rather than lists or totally ordered sets.

The most important examples of Markov categories for probability theory are the following:

* $\cat{FinStoch}$ is the Markov category of finite stochastic maps. The objects are finite sets $X$, morphisms $p: I \to X$ are probability distributions and general morphisms $f: X \to Y$ are stochastic matrices.

* $\cat{Stoch}$ is the Markov category of arbitrary Markov kernels on measurable spaces. The objects are measurable spaces, morphisms $p: I \to X$ are probability measures, and general morphisms $f : X \to Y$ are measurable Markov kernels.

* $\cat{BorelStoch}$ is given by $\cat{Stoch}$ restricted to standard Borel spaces as objects.

* $\cat{Gauss}$ is the Markov category of Gaussian probability distributions. The objects are the spaces $\mathbb{R}^n$, morphisms $p: I \to \mathbb{R}^n$ are Gaussian probability measures and general morphisms $f: \mathbb{R}^n \to \mathbb{R}^m$ can be understood as stochastic maps

\begin{equation*}
x \mapsto A x + \xi
\end{equation*}

where $A$ is any real $m \times n$ matrix and $\xi$ is Gaussian noise.
$\cat{Gauss}$ is a (non-full) subcategory of $\cat{BorelStoch}$.

In each case, composition, the symmetric monoidal structure and the Markov category structure are the obvious ones.
For more details and further examples we refer to [9].
In our context, gs-monoidal categories that are not Markov categories play more of an auxiliary role which we will detail below.

§ FREE MARKOV CATEGORIES AND GENERALIZED CAUSAL MODELS

Causal models are a framework for studying and modeling dependencies between random variables.
In this section, we introduce such a framework in the language of Markov categories. We therefore investigate causal relationships independently of the particular notion of probability behind it (discrete, measure-theoretic, Gaussian, etc).[It is also possible to instantiate all of our definitions and results in a ”possibilistic“ rather than probabilistic setting. While this would be interesting e.g. in the context of non-determinism in computer science, the focus of the present work is on the probabilistic case.]

Free Markov categories are the tailored notion for these purposes. These categories contain precisely all blueprints for causal networks that can be built from a bunch of given causal mechanisms. A morphism in this category is then a generalized causal model.

The remainder of this section explains this in technical detail based on the formalism of free gs-monoidal categories and free Markov categories from [10][Another very similar construction of free gs-monoidal categories has been given independently in [16].]. This part is structured as follows: In <Ref>, we introduce the category of hypergraphs. In <Ref> we use hypergraphs to define gs-monoidal string diagrams, free gs-monoidal categories, and subsequently free Markov categories. In <Ref> we introduce generalized causal models and causal compatibility of morphisms in arbitrary Markov categories.

§.§ The category of hypergraphs

A gs-monoidal string diagram, and therefore also a generalized causal model is defined as a hypergraph with extra structure.
To define the relevant notion of hypergraph following [1], let first $\cat{I}$ be the category defined in the following way:

* The set of objects is given by $\{(k, \ell) \mid k, \ell \in \mathbb{N}\} \cup \{\star\}$.

* Besides the identity morphisms, for every $(k,\ell)$ there are $k + \ell$ different morphisms

$$\mathsf{in}_1, \ldots, \mathsf{in}_k, \mathsf{out}_1, \ldots, \mathsf{out}_{\ell}: (k,\ell) \to \star,$$

and no other morphisms.

It is not necessary to specify a composition rule in $\cat{I}$, since no compositions except the trivial ones can be formed.

A functor $G: \cat{I} \to \cat{Set}$ is called a hypergraph. Accordingly, we define the functor category

\begin{equation*}
\cat{Hyp} \coloneqq \cat{Set}^{\cat{I}}
\end{equation*}

to be the category of hypergraphs.

Intuitively, the functor $G$ characterizes our common interpretation of (directed) hypergraphs in the following way:

* $W(G) \coloneqq G(\star)$ is the set of vertices, which we will call wires.

* $B_{k,\ell}(G) \coloneqq G((k,\ell))$ is the set of hyperedges, which we will call boxes, with $k$ inputs and $\ell$ outputs.

* $G(\mathsf{in}_i)$ specifies the $i$th input wire of every box.

* $G(\mathsf{out}_j)$ specifies the $j$th output wire of every box.

While the set of wires and boxes of a hypergraph may be infinite, the number of inputs and outputs of a box is always finite. We present a pictorial representation of a hypergraph in <Ref>.

Pictorial representation of a hypergraph with wire set $\{A,B,C,D,E\}$ and box set $\{f,g,h,m,n\}$. For example, the box $f$ has one input incident to the wire $B$ and two outputs both incident to the wire $A$. The wire $E$ is not incident to any box.

Given a box $b \in B_{k,\ell}(G)$ and a wire $A \in W(G)$, we define

\begin{align*}
\mathsf{in}(b,A) &\coloneqq \big|\big\{j \in \{1, \ldots, \ell\}: \mathsf{in}_{j}(b) = A\big\}\big|, \\
\mathsf{out}(b,A) &\coloneqq \big|\big\{i \in \{1, \ldots, k\}: \mathsf{out}_{i}(b) = A\big\}\big|.
\end{align*}

Thus $\mathsf{in}(b,A)$ and $\mathsf{out}(b,A)$ counts the number of incoming or outgoing wires of type $A$ in the box $b$. We also define the sets of inputs and outputs as

\begin{align*}
\In(b) &\coloneqq \big\{\In_i(b): i \in \{1, \ldots, \ell\}\big\}, \\
\Out(b) &\coloneqq \big\{\Out_i(b): i \in \{1, \ldots, k\}\big\},
\end{align*}

where repeated wires are counted only once.

Next, we analyze the morphisms in $\cat{Hyp}$. Since $\cat{Hyp}$ is a functor category, a morphism $\alpha: F \to G$ is precisely a natural transformation $\alpha: F \Rightarrow G$. Such a natural transformation is fully determined by its components

\begin{equation*}
\alpha_{\star}: W(F) \to W(G) \quad \text{ and } \quad \alpha_{(k,l)}: B_{(k,\ell)}(F) \to B_{(k,\ell)}(G) \quad \text{ for all } k, \ell \in \mathbb{N}
\end{equation*}

satisfying naturality, i.e. commutativity of all diagrams of the form

\begin{equation*}
\begin{tikzcd}
B_{k,\ell}(F) \ar{d}{\alpha_{k,\ell}} \ar{r}{\mathsf{in}_i} & W(F) \ar{d}{\alpha_{k,\ell}} \\
B_{k,\ell}(G) \ar{r}{\mathsf{in}_i} & W(G)
\end{tikzcd} \qquad \qquad \qquad \begin{tikzcd}
B_{k,\ell}(F) \ar{d}{\alpha_{k,\ell}} \ar{r}{\mathsf{out}_j} & W(F) \ar{d}{\alpha_{k,\ell}} \\
B_{k,\ell}(G) \ar{r}{\mathsf{out}_j} & W(G).
\end{tikzcd}
\end{equation*}

In other words, every natural transformation is a structure-preserving map between hypergraphs, i.e. if box $f$ is incident to wire $A$ in its $i$th input in the hypergraph $F$, then the same applies to their images with respect to $\alpha$ in the hypergraph $G$.

A hypergraph can contain an infinite set of wires and boxes. In the following we mainly restrict to finite hypergraphs, i.e. functors $G : \cat{I} \to \cat{Set}$ where $W(G)$ and

$$ B(G) \coloneqq \coprod_{k,\ell \in \mathbb{N}} B_{k,\ell}(G).$$

are finite sets.
We denote the corresponding full subcategory of $\cat{Hyp}$ by $\cat{FinHyp}$.

§.§ gs-monoidal string diagrams and free Markov categories

The pictorial representation of hypergraphs indicates their use for modeling causal structures in a categorical framework. In this subsection, we use hypergraphs in order to construct free Markov categories generated by a fixed hypergraph $\Sigma$. These are Markov categories in which the morphisms are string diagrams formed out of the boxes in $\Sigma$, or equivalently generalized causal models.

However, three apparent problems make hypergraphs not directly applicable to represent string diagrams:

* General hypergraphs might contain loops, for example in the sense that an output wire of a box may directly feed back as an input.

* While the splitting of a wire into two represents the copying of values and makes sense in any Markov category, the merging of wires as in <Ref> does not make sense.

* A hypergraph in itself does not include any information about which wires are inputs or outputs of the overall diagram.

We resolve these issues by restricting to acyclic and left monogamous hypergraphs and by representing gs-monoidal string diagrams by cospans thereof:

Let $\Sigma$ be a hypergraph. A gs-monoidal string diagram for $\Sigma$ is a cospan in the slice category $\cat{FinHyp}/\Sigma$ of the form

\begin{equation*}
\begin{tikzcd}
& G & \\
\underline{n} \arrow{ru}{p}  & & \underline{m} \arrow[swap]{lu}{q}
\end{tikzcd}
\end{equation*}

satisfying that:

* $G$ is acyclic, i.e.	there is no family of wires $A_0, \ldots, A_{k-1} \in W(G)$ and boxes $f_0, \ldots, f_{k-1} \in B(G)$ such that

\begin{equation*}
\mathsf{in}(f_i, A_i) \geq 1 \quad \text{ and } \quad \mathsf{out}(f_i, A_{i+1}) \geq 1,
\end{equation*}

where the subscripts are modulo $k$.

* $G$ is left monogamous, i.e. for every wire $W \in W(G)$ we have

\begin{equation*}
|p^{-1}(W)| + \sum_{f \in E(G)} \mathsf{out}(f,W) \leq 1.
\end{equation*}

By abuse of notation, we also write $G$ for the underlying hypergraph of the object $G$ in $\cat{FinHyp} / \Sigma$, and we write $\mathsf{type} : G \to \Sigma$ for the morphism that makes it into an object of $\cat{FinHyp} / \Sigma$.

In this definition, the discrete hypergraph $\underline{n}$ is defined to have $W(\underline{n}) = \{1,\ldots,n\}$ and contains no boxes. Thus the morphism $p : \underline{n} \to G$ simply equips some wires with labels from $1,\ldots,n$, thereby telling us which wires of $G$ are input wires of the overall diagram and in which order. The other cospan leg $q : \underline{m} \to G$ similarly encodes the $m$ output wires.

Pictorially, an acyclic hypergraph does not contain a family of wires which form a loop. Further, left monogamy requires that every wire in the hypergraph arises as either a global input or as an output of a box in precisely one way, ensuring that no ”merging“ of wires occurs. See <Ref> for an illustration of all of this. The hypergraph morphisms $\mathsf{type} : G \to \Sigma$ are given by mapping the wires $A_i$ to $A$ in both examples as well as mapping the two distinct boxes $f_i$ to the only morphism $f$ in $\Sigma$, etc. The first and second hypergraphs are acyclic, while the third one is not. The first and third hypergraphs are left monogamous, while the second one is not since $A_2$ is an output of two boxes. Finally, we have $n = 0$ in the first two cases, so that the left cospan leg $p$ is trivial, while the right leg $q$ maps each number $i$ to the $i$th overall output wire as counted from left to right.

\begin{equation*}
\tikzfig{figures/hypergraph_example_morphism1}
\end{equation*}

\begin{equation*}
\tikzfig{figures/hypergraph_example_morphism2}
\end{equation*}

\begin{equation*}
\tikzfig{figures/hypergraph_example_morphism3}
\end{equation*}

An example and two non-examples of gs-monoidal string diagrams where $\Sigma$ is the hypergraph from <Ref>. The hypergraph morphisms to $\Sigma$ are given by mapping the wires $A_i$ to $A$ in both examples as well as mapping the boxes labelled $f_i$ to the $f$ in $\Sigma$.

The notion of gs-monoidal string diagram is the main ingredient for constructing a gs-monoidal category whose morphisms are freely generated by the wires and boxes in a fixed hypergraph $\Sigma$.
Indeed we can now define the category $\cat{FreeGS}_{\Sigma}$ as follows:

* Objects are all hypergraph morphisms $\sigma: \underline{n} \to \Sigma$ for $n \in \mathbb{N}$, or equivalently finite sequences of wires in $\Sigma$.

* Morphisms are the isomorphism classes of gs-monoidal string diagrams.

Composition in $\cat{FreeGS}_\Sigma$ is defined by a pushout which which coincides with the way of stacking and connecting up drawings of string diagrams. The gs-monoidal structure likewise corresponds to the obvious operations in terms of string diagrams. We refer to [10] for details.
In the following, we will not distinguish between a gs-monoidal string diagram and its isomorphism class.

$\cat{FreeGS}_{\Sigma}$ is typically not a Markov category. For example, the first step in the following simplification does not hold since the (cospans of) hypergraphs are not isomorphic, while the second equation does hold:

\begin{equation}
\label{eq:eliminablemorphism}
\tikzfig{figures/elim_boxes1} \quad \neq \quad \tikzfig{figures/elim_boxes2} \quad = \quad \tikzfig{figures/elim_boxes3}
\end{equation}

In the following, we define the free Markov category $\cat{FreeMarkov}_{\Sigma}$ by taking a quotient of $\cat{FreeGS}_{\Sigma}$ which enforces Equation (<ref>), so that also the first equation above becomes true.

\begin{equation}
\label{eliminable}
\varphi \coloneqq \begin{tikzcd}
& G & \\
\underline{n} \arrow{ru}{p}  & & \underline{m} \arrow[swap]{lu}{q}
\end{tikzcd}
\end{equation}

be a gs-monoidal string diagram.

* A box $b \in B(G)$ is called eliminable if each output of $b$ gets discarded, i.e. if for every $W \in W(G)$ such that $\mathsf{out}(b,W) > 0$ we have

* $q^{-1}(W) = \emptyset$.

* $\mathsf{in}(b', W) = 0$ for every box $b' \in B(G)$.

* $\varphi$ is called normalized if it contains no eliminable boxes.

Every gs-monoidal string diagram has a normalized version obtained by iteratively applying the rule of Equation (<ref>) to any eliminable box. Since every diagram is finite, this procedure terminates after finitely many steps, and we reach the normalized version. In addition, this diagram is unique since the order of elimination does not matter.

The free Markov category $\cat{FreeMarkov}_\Sigma$ is now defined just as $\cat{FreeGS}_\Sigma$, but with morphisms restricted to the normalized gs-monoidal string diagrams.
The composition of morphisms is then defined as composition in $\cat{FreeGS}_\Sigma$ followed by normalization since the composition of two normalized diagrams need not be normalized.
See [10] for details.

The morphism

\begin{equation*} \varphi \quad = \quad \tikzfig{figures/NonConectednessExample2} \end{equation*}

is not normalized, since the output of $b$ gets discarded. Applying Equation (<ref>), also the output of $c$ get discarded. Therefore the normalization of $\varphi$ is

\begin{equation*}
\norm(\varphi) \quad = \quad	\tikzfig{figures/NonConectednessExample3}
\end{equation*}

In general, normalizing a gs-monoidal string diagram defines a strict gs-monoidal functor

\[
\norm : \cat{FreeGS}_\Sigma \to \cat{FreeMarkov}_\Sigma
\]

that is identity-on-objects.

§.§ Causal models and causal compatibility

We now introduce the notion of a generalized causal model and define when a morphism in a Markov category is considered compatible with a generalized causal model.

Given a hypergraph $\Sigma$, a generalized causal model is a normalized gs-monoidal string diagram (<ref>) over $\Sigma$ such that $q$ is injective.

Intuitively, a generalized causal model is a morphism in $\cat{FreeMarkov}_{\Sigma}$ where the injectivity of $q$ ensures that each wire is connected to at most one output. This lets us identify the global inputs and outputs with the wires in $W(G)$ (see <Ref>). In the traditional terminology of random variables, the injectivity of $q$ guarantees that different outputs correspond to different variables. <Ref> shows examples of generalized causal models.

One relevant subclass of generalized causal models are pure blooms. These morphisms represent causal models in which all variables are observed, i.e. every wire is an output in exactly one way, such as in <Ref>(C).

Let $\varphi$ be a generalized causal model represented by a gs-monoidal string diagram

\begin{equation*}
\varphi = \begin{tikzcd}
& G & \\
\underline{n} \arrow{ru}{p}  & & \underline{m} \arrow[swap]{lu}{q}
\end{tikzcd}
\end{equation*}

Then $\varphi$ is called pure bloom if $q$ is a bijection on wires.

Non-example of a generalized causal model.[.3]figures/NoCausalModel
The Bell scenario.[.3]figures/BellScenarioMorphism
The instrumental scenario with every variable being observed.[.3]figures/InstrumentalScenarioNoVar
(Non-)Examples of generalized causal models. While (B), (C) are generalized causal models, the string diagram (A) is not since the output wire of $g$ is connected to two global outputs. Concerning <Ref>, the generalized causal model (B) is not a pure bloom since the output of $\Lambda$ is not connected to a global output. The generalized causal model (C) is a pure bloom without inputs. For a further analysis of (C) regarding $d$-separation, see <Ref><ref>. In all three examples, we have $\Sigma = G$ and assume $\mathsf{type}$ to be the identity map for simplicity.

For an example of a pure bloom morphism, we refer to <Ref>. We will show that the soundness of the $d$-separation criterion holds for arbitrary generalized causal models (see <Ref>) while the completeness holds for pure bloom morphisms (see <Ref>).

To define causal compatibility, we make the following assumption for the rest of the paper for convenience:

Throughout, $\cat{C}$ is a strict Markov category.

Although most examples like $\cat{FinStoch}$, $\cat{BorelStoch}$ or $\cat{Stoch}$ already fail strictness, this does not exclude these examples since we can always work with a strictification instead <cit.>, which satisfies <Ref>.
On the other hand, our free Markov categories $\cat{FreeMarkov}_\Sigma$ already satisfy this condition ”on the nose“.
In any case, <Ref> is a useful convenience that holds without loss of generality.

For the rest of the paper, we will assume that $\varphi$ is a generalized causal model with

\begin{equation*}
\varphi \quad \coloneqq \quad \begin{tikzcd}
& G & \\
\underline{n} \arrow{ru}{p}  & & \underline{m} \arrow[swap]{lu}{q}
\end{tikzcd}
\end{equation*}

which becomes a cospan in $\cat{FinHyp} / \Sigma$ through $\mathsf{type} : G \to \Sigma$.

We identity inputs and outputs with the wires they map to under $p$ and $q$ and refer to them as such. In particular, we define

\begin{align}
\label{phi_defn}
\In(\varphi) &\coloneqq p(\underline{n}) \subseteq W(\varphi)\\
\label{phi_defn2}
\Out(\varphi) &\coloneqq q(\underline{m}) \subseteq W(\varphi)
\end{align}

for the set of all input/output wires. If $\varphi$ is a pure bloom morphism, then $\Out(\varphi) = W(\varphi)$.

Note that $\varphi$ is a morphism

\[
\varphi : \bigotimes_{i=1}^n \mathsf{type}(p(i)) \longrightarrow \bigotimes_{j=1}^m \mathsf{type}(q(j))
\]

in $\cat{FreeMarkov}_\Sigma$.

In the following, we present the notion of causal compatibility for a generalized causal model $\varphi$. Intuitively, a morphism $f$ in any Markov category $\cat{C}$ is compatible with $\varphi$ if we can plug in a morphism from $\cat{C}$ into every box in $B(\Sigma)$ in such a way that the composite is exactly $f$, and such that the global input and output wires of $\varphi$ correspond to a given tensor factorization of the domain and codomain of $f$:

For $\Sigma$ a hypergraph, let $\varphi$ be a generalized causal model as in (<ref>).
Let further

\[
f : \bigotimes_{i=1}^n W'_i \to \bigotimes_{j=1}^m V'_j
\]

be a morphism in any Markov category $\cat{C}$ satisfying <Ref>, equipped with a fixed tensor decomposition of its domain and codomain as indicated.

We call $f$ compatible with $\varphi$ if there exists a strict Markov functor[i.e. a strict symmetric monoidal functor which preserves the comonoid structure.] $F: \cat{FreeMarkov}_{\Sigma} \to \cat{C}$ such that:

* We have

\begin{equation}
\label{F_wires_map}
W'_i = F(\mathsf{type}(p(i))), \qquad V'_j = F(\mathsf{type}(q(j)))
\end{equation}

for all input indices $i = 1,\ldots,n$ and output indices $j = 1,\ldots,k$.

* $f = F(\varphi)$.

This generalizes the functorial definition of causal models as first studied by Fong [6].

Note that the functor $F$ must assign to every wire type (i.e., wire in $\Sigma$) a corresponding object in the category $\cat{C}$. This implies that wires in $W(G)$ with identical types must map to the same object in $\cat{C}$. For example, one may consider a situation where $f$ is a probability distribution with no inputs and all output variables are real-valued. In this case, we have $V'_j = \mathbb{R}$ for all $j$, and one may want to consider a causal model $\varphi$ in which all wires are likewise of the same type.

Similarly, the hypergraph morphism $\mathsf{type} : G \to \Sigma$ assigns to each box in $G$ a specific ”type“ box in $\Sigma$. This means that under $F$, any two boxes with the same type must map to the same morphism in $\cat{C}$.
This is why generalized causal models in our sense can naturally incorporate the condition that several causal mechanisms must be the same, namely when choosing the types in a way enforcing this.

In the following, we denote for every wire $X \in W(G)$ in $\varphi$ the corresponding object $F(\mathsf{type}(X))$ in $\cat{C}$ by $X'$.
Similarly, for every set of wires $\mathcal{W} \subseteq W(G)$ in $\varphi$, we denote the corresponding multiset of wires in $\cat{C}$ by $\mathcal{W}'$. For the rest of the paper, we will associate this multiset with the corresponding tensor product in $\cat{C}$ obtained by tensoring its elements, where we ignore the question of how to order the factors.

§ CONDITIONALS AND CONDITIONAL INDEPENDENCE

§.§ Existence of conditionals

To use the $d$-separation criterion to detect causal compatibility, we need in addition the existence of conditionals. This notion has been studied in categorical terms in [3] in a special case, where the authors call it admitting disintegration, and subsequently in [9] in general. In the following, we briefly review the definition following <cit.>.

Let $\cat{C}$ be a Markov category. We say that $\cat{C}$ has conditionals if for every morphism $f : A \to X \otimes Y$, there is a morphism $f_{|_X}$ such that

\begin{equation*}
\tikzfig{figures/ConditionalsDefinition1} \quad = \quad \tikzfig{figures/ConditionalsDefinition2}
\end{equation*}

Examples of categories having conditionals are $\cat{FinStoch}$, $\cat{Gauss}$ as well as $\cat{BorelStoch}$. In contrast, $\cat{Stoch}$ does not have conditionals (see <cit.> and references therein).

§.§ Conditional independence

A second ingredient of the $d$-separation criterion is the definition of conditional independence. The following definition has been introduced in several works (see for example <cit.> or [4] in a different setup) and shown to satisfy the well-known semigraphoid properties. In addition, [9] shows that it is still meaningful to define conditional independence in the absence of conditionals.

A morphism $f : I \to \mathcal{X} \otimes \mathcal{Z} \otimes \mathcal{Y}$ in $\cat{C}$ displays the conditional independence $\mathcal{X} \perp \mathcal{Y} \ | \ \mathcal{Z}$ if it can be written as

\begin{equation*}
\tikzfig{figures/tripartiteState} \quad = \quad \tikzfig{ConditionalIndependence}
\end{equation*}

In other words, $\mathcal{X} \perp \mathcal{Y} \ | \ \mathcal{Z}$ holds if $f$ is compatible with the generalized causal model which corresponds to the string diagram on the right-hand side (where all boxes are of distinct type, and we leave labels off for simplicity).

The conditional independence $\mathcal{X} \perp \emptyset \ | \ \mathcal{Z}$ is equivalent to the existence of the conditional $r_{|_\mathcal{Z}}$. Therefore, if $\cat{C}$ has conditionals, then every state $r$ satisfies $\mathcal{X} \perp \emptyset \ | \ \mathcal{Z}$ for every tensor factorization of its codomain $\mathcal{X} \otimes \mathcal{Z}$.

As we have already done in the previous definition, we write $\mathcal{X}, \mathcal{Y}, \ldots$ for arbitrary lists of objects in $\cat{C}$.
We also allow for implicit reordering of these lists—effectively identifying these lists with multisets—and omit mention of the relevant compositions of $f$ by swap morphisms.[Of course, these kinds of bookkeeping mechanisms are also present in the traditional notation of probability distributions and measures, though rarely made explicit in that context.]
This allows us to talk about conditional independence with respect to any tripartition of the tensor factors in the codomain of any state $f$.

With this in mind, we now introduce a notion of conditional independence for morphisms with inputs. This notion is the key ingredient of the $d$-separation criterion presented in <Ref>, and it is the categorical generalization of the transitional conditional independence introduced recently by Forré <cit.>.

A morphism $f: \mathcal{A} \to \mathcal{X} \otimes \mathcal{Y} \otimes \mathcal{Z}$ in $\cat{C}$ displays the conditional independence $\mathcal{X} \perp \mathcal{Y} \ | \ \mathcal{Z}$ if there exists a factorization of the form

\begin{equation*}
\tikzfig{figures/tripartiteMorphism} \quad = \quad \tikzfig{figures/ConditionalIndependenceMorphism}
\end{equation*}

Note that the above definition of conditional independence is not symmetric, i.e. $\mathcal{X} \perp \mathcal{Y} \ | \ \mathcal{Z}$ does not necessarily imply $\mathcal{Y} \perp \mathcal{X} \ | \ \mathcal{Z}$.
If $\cat{C}$ has conditionals then $\mathcal{X} \perp \mathcal{Y} \ | \ \mathcal{Z}$ rewrites to

\begin{equation*}
\tikzfig{figures/tripartiteMorphism} \quad = \quad \tikzfig{figures/ConditionalIndependenceMorphism} \quad = \quad \tikzfig{figures/ConditionalIndependenceMorphismLeg}
\end{equation*}

which highlights the asymmetry. Moreover, if $\mathcal{A}$ is trivial, then the conditional independence coincides with <Ref>.

Due to the asymmetry, the outputs in $\mathcal{Y}$ might contain information about the inputs $\mathcal{A}$ which cannot be retrieved just from the outputs in $\mathcal{Z}$. On the other hand, the outputs in $\mathcal{X}$ are generated using only the information from the outputs in $\mathcal{Z}$. The local Markov property that we will use in <Ref> explicitly highlights this asymmetry: the output of a box (corresponding to $\mathcal{X}$) is independent of its non-descendants ($\mathcal{Y}$) given its inputs ($\mathcal{Z}$). Every global input is non-descendant to any box; however, not every global input wire is directly an input of the box itself.

§ DECIDING CAUSAL COMPATIBILITY WITH D-SEPARATION

The main goal of this section is to prove that the $d$-separation criterion <cit.> correctly detects causal compatibility not just in discrete probability but in all Markov categories with conditionals.
To this end, we introduce a categorical notion of $d$-separation phrased in terms of connectedness of the gs-monoidal string diagram representing the causal model. We then show that this notion coincides with the classical notion of $d$-separation whenever the latter applies.

This part is structured as follows. In <Ref>, we introduce the categorical notion of $d$-separation on generalized causal models. Moreover, we show in <Ref> that this notion coincides with the classical notion of $d$-separation for all those generalized causal models that correspond to DAGs. In <Ref>, we first show that $d$-separation implies conditional independences for compatible morphisms in Markov categories with conditionals. We then show in <Ref> that $d$-separation fully characterizes causal compatibility.

§.§ Categorical d-separation

For a gs-monoidal string diagram

\begin{equation*}
\varphi \,= \begin{tikzcd}
& G & \\
\underline{n} \arrow{ru}{p}  & & \underline{m} \arrow[swap]{lu}{q}
\end{tikzcd}
\end{equation*}

and a set of output wires $\mathcal{Z} \subseteq \Out(\varphi)$, we define a new gs-monoidal string diagram $\Cut_{\mathcal{Z}}(\varphi)$ obtained by removing the wires in $\mathcal{Z}$ in the following sense. Its underlying hypergraph $H$ is such that the set of boxes is the same, $B(H) \coloneqq B(G)$, while the set of wires is $W(H) \coloneqq W(G) \setminus \mathcal{Z}$.
Each box has the same input and output wires as before, expect in that those in $\mathcal{Z}$ are simply removed, which lowers the arities of the boxes correspondingly.
We also remove all occurrences of wires in $\mathcal{Z}$ from the global inputs and outputs, and this results in a gs-monoidal string diagram

\begin{equation*}
\Cut_{\mathcal{Z}}(\varphi) \coloneqq \begin{tikzcd}
& H & \\
\underline{n}' \arrow{ru}{p'}  & & \underline{m}' \arrow[swap]{lu}{q'}
\end{tikzcd}
\end{equation*}

Note that $\Cut_{\mathcal{Z}}(\varphi)$ is generally not a morphism in $\cat{FreeMarkov}_{\Sigma}$ anymore since it is not normalized. However, it can be understood as a morphism in $\cat{FreeGS}_{H}$. <Ref> will present a few examples.

We next introduce some notation for paths of wires.

Let $\varphi$ be a gs-monoidal string diagram in $\cat{FreeGS}_{\Sigma}$.

*  An undirected path between two wires $X,Y \in W(G)$ is a sequence of wires

\[
X = W_1, \, W_2, \, \ldots, \, W_{n}, \, W_{n+1} = Y
\]

together with a sequence of boxes $b_1, \ldots, b_n \in B(G)$ such that

\begin{equation*}
\In(b_i, W_i) + \Out(b_i, W_i) \geq 1 \quad \text{ and } \quad  \In(b_i, W_{i+1}) + \Out(b_i, W_{i+1}) \geq 1.
\end{equation*}

If there exists an undirected path between $X$ and $Y$, then we write $X \minus Y$.

*  For two wires $A, B \in W(G)$, we write $A \rightarrow B$ if there exists a box $b \in B(G)$ such that

\begin{align} \In(b, A) = 1 \quad \text{ and } \quad \Out(b, B) = 1.\end{align}

* For two wires $A,B \in W(G)$, we write $A \twoheadrightarrow B$ if there exists a sequence of wires $W_1, \ldots, W_{n} \in W(G)$ such that

\begin{equation}
\label{eq:directedPath} A \rightarrow W_1 \rightarrow \ \ldots \ \rightarrow W_n \rightarrow B.
\end{equation}

Thus, an undirected path in $\varphi$ may traverse a box not just from input or output or vice versa, but also from input to input or output to output.

The intuitive idea behind the following definition of $d$-separation, as already briefly discussed at <cit.>, was communicated to us by Rob Spekkens.

Let $\varphi$ be a generalized causal model. For three disjoint sets of output wires $\mathcal{X}, \mathcal{Y}, \mathcal{Z} \subseteq \Out(\varphi)$, we say that $\mathcal{Z}$ $d$-separates $\mathcal{X}$ and $\mathcal{Y}$ if

\begin{equation*}
\Cut_{\mathcal{Z}}(\varphi_{\mathcal{X}, \mathcal{Y}, \mathcal{Z}})
\end{equation*}

has no undirected path between any output in $\mathcal{X}$ and any output in $\mathcal{Y}$.

Here, $\varphi_{\mathcal{W}} \coloneqq \norm(\Del{\mathcal{W}^{c}} \circ \varphi)$ denotes the marginal on $\mathcal{W} \subseteq \Out(\varphi)$ in $\cat{FreeMarkov}_{\Sigma}$.
The absence of an undirected path as in the definition manifests itself in the string diagrams simply as topological disconnectedness.

The following examples constitute the basic components of ”classical“ $d$-separation and illustrate the simplicity of categorical $d$-separation.
In all cases, the unlabeled boxes denote distinct generators, i.e. distinct boxes in the generating hypergraph $\Sigma$.

* Fork: consider the morphism

\begin{equation*}
\varphi \quad = \quad \tikzfig{figures/tripartiteDSeparationExample}
\end{equation*}

Then $Z$ $d$-separates $X$ from $Y$, since

\begin{equation*}
\Cut_{Z}(\varphi) \quad = \quad \tikzfig{figures/tripartiteDSeparationExample2}
\end{equation*}

has disconnected $X$ and $Y$.

* Chain: consider the morphism

\begin{equation*}
\varphi \quad = \quad \tikzfig{figures/sequentialDSeparationExample}
\end{equation*}

Then $Z$ $d$-separates $X$ from $Y$, since

\begin{equation*}
\Cut_{Z}(\varphi) \quad = \quad \tikzfig{figures/sequentialDSeparationExample2}
\end{equation*}

has disconnected $X$ and $Y$.

* Collider: consider the morphism

\begin{equation*}
\varphi \quad = \quad \tikzfig{figures/NonConectednessExample1}
\end{equation*}

Then $Z$ does not $d$-separate $X$ from $Y$, since we have

\begin{equation*}
\varphi_{X,Z,Y} \quad = \quad \tikzfig{figures/NonConectednessExample4} \quad =  \quad \tikzfig{figures/NonConectednessExample5}
\end{equation*}

and therefore

\begin{equation*}
\Cut_{Z}(\varphi_{X,Z,Y}) \quad = \quad \tikzfig{figures/NonConectednessExample6}
\end{equation*}

which still contains an undirected path $X - Y$. The same reasoning applies when $\mathcal{Z} = \{W\}$ or $\mathcal{Z} = \{W, Z\}$. However, if $\mathcal{Z} = \emptyset$, then

\begin{equation*}
\varphi_{X,Y} \quad = \quad \tikzfig{figures/NonConectednessExample2_unlabelled} \quad = \quad \tikzfig{figures/NonConectednessExample3_unlabelled}
\end{equation*}

which has disconnected $X$ and $Y$.
Therefore $\emptyset$ $d$-separates $X$ and $Y$.

* Consider the morphism

\begin{equation*}
\varphi \quad = \quad \tikzfig{figures/tripartiteDSeparationExampleMarginal}
\end{equation*}

The normalized marginal $\varphi_{X,Y,Z}$ is given by

\begin{equation*}
\varphi_{X,Y,Z} \quad = \quad \tikzfig{figures/tripartiteDSeparationExampleMarginal2}
\end{equation*}

which again shows that $Z$ $d$-separates $X$ from $Y$, since cutting $Z$ makes $X$ and $Y$ disconnected.

In order to define the classical notion of $d$-separation, we note that certain gs-monoidal string diagrams have an underlying DAG, given by using wires as nodes and taking the edges to be $\to$ as in <Ref>.
We use the term DAG path to refer to an undirected path in this DAG, i.e. to a sequence of wires connected by boxes from input to output or vice versa (but not from input to input or output to output).
We also define the ancestor wires of a given set of wires as

\begin{equation*}
\An(\mathcal{X}) = \{U \in W(G): \exists X \in \mathcal{X} \textrm{ such that } U \twoheadrightarrow X \}.
\end{equation*}

and the set of descendant wires as

\begin{equation*}
\Dec(\mathcal{X}) = \{U \in W(G): \exists X \in \mathcal{X} \textrm{ such that } X \twoheadrightarrow U \}.
\end{equation*}

Note that $\mathcal{X} \subseteq \An(\mathcal{X}), \Dec(\mathcal{X})$.
To state the following classical definition <cit.> in our language, we restrict further to those generalized causal models that are determined by their underlying DAGs.
In a causal structure as represented by a DAG, it is (implicitly) assumed that every node or variable has its own causal mechanism associated with it; in our framework, this means that every box has exactly one output. Moreover, DAGs have no global inputs which implies in our framework that $\In(\varphi) = \emptyset$.

Let $\varphi$ be a pure bloom causal model with $\In(\varphi) = \emptyset$ and such that every box has exactly one output. Then:

* A DAG path $p$ in $\varphi$ is called $d$-separated by a set of wires $\mathcal{Z} \subseteq \Out(\varphi)$ if:

* $p$ contains a chain $W \rightarrow Z \rightarrow U$ or a fork $W \leftarrow Z \rightarrow U$ for some $Z \in \mathcal{Z}$.

* $p$ contains a collider $W \rightarrow M \leftarrow U$ where $M \notin \An(\mathcal{Z})$.

* $\mathcal{X}$ is $d$-separated from $\mathcal{Y}$ by $\mathcal{Z}$ if every DAG path between every $X \in \mathcal{X}$ and $Y \in \mathcal{Y}$ is $d$-separated by $\mathcal{Z}$.

We will now prove the equivalence of categorical $d$-separation with classical $d$-separation for the class of causal models on which the latter is defined. This requires some preparation.

Let $\varphi$ be a pure bloom causal model, $b \in B(G)$ a box in $\varphi$ and $\mathcal{W} \subseteq \Out(\varphi)$ a subset of its wires. The following statements are equivalent:

*  $\Out(b) \cap \An(\mathcal{W}) = \emptyset$.

*  $b$ gets discarded in $\varphi_\mathcal{W} = \norm(\Del{\mathcal{W}^{c}} \circ \varphi)$.

$\ref{bloomlem2} \Longrightarrow \ref{bloomlem1}$: To prove the contrapositive, assume $\exists A \in \Out(b)$ such that $A \in \An(\mathcal{W})$. Then there is a path $A \twoheadrightarrow W$ with $W \in \mathcal{W}$. Since $W$ is still an overall output that does not get discarded, this path is still valid in $\Del{\mathcal{W}^{c}} \circ \varphi$. Therefore $b$ remains in $\norm(\Del{\mathcal{W}^{c}} \circ \varphi)$.

$\ref{bloomlem1} \Longrightarrow \ref{bloomlem2}$: Consider the set $\Dec(\Out(b))$. By assumption, we have that $\Dec(\Out(b)) \cap \An(\mathcal{W}) = \emptyset$. We show that the box $b$ gets discarded in $\norm(\Del{\Dec(\Out(b))} \circ \varphi)$, which is enough because of $\mathcal{W}^c \supseteq \Dec(\Out(b))$.
By definition of $\Dec(\Out(b))$, there exists a final box[As defined in [10], a final box is one whose outputs are global outputs of $\varphi$ without further copy or discard. Such a box always exists since $\varphi$ is pure bloom and normalized (compare <cit.>).] $\hat{b}$ such that $\Out(\hat{b}) \subseteq \Dec(\Out(b))$. This shows that $\hat{b}$ gets discarded in $\norm(\Del{\Dec(\Out(\hat{b}))} \circ \varphi)$.

Define $\widetilde{\varphi} \coloneqq \norm(\Del{\Dec(\Out(\hat{b}))} \circ \varphi)$. Repeating the above procedure with $\widetilde{\varphi}$, we arrive after finite number of steps at $b$ itself being a final box. Since it is then eliminable after composing with $\Del{\Dec(\Out(b))}$, it indeed no longer appears in the normalization.

We can now show the promised equivalence result between categorical $d$-separation and classical $d$-separation in the cases where $\varphi$ represents a causal structure given by a DAG, i.e. $\In(\varphi) = \emptyset$ and every box has a single output.

Both concepts of $d$-separation coincide on pure bloom causal models $\varphi$ with $\In(\varphi) = \emptyset$ and in which every box has exactly one output.

To make the proof more intuitive, we introduce the term $d$-connected as the negation of $d$-separated (in either version).

We start by showing that classical $d$-connectedness implies categorical $d$-connectedness. Let $p$ be a DAG path between some $X \in \mathcal{X}$ and some $Y \in \mathcal{Y}$ which witnesses that $\mathcal{Z}$ makes $\mathcal{X}$ and $\mathcal{Y}$ be $d$-connected in the classical sense, which means that the following hold:

*  For every chain $W \rightarrow M \rightarrow U$ or fork $W \leftarrow M \rightarrow U$ in $p$, we have $M \not\in \mathcal{Z}$.

*  For every collider $W \rightarrow M \leftarrow U$ in $p$, we have $M \in \An(\mathcal{Z})$.

For simplicity, we also assume without loss of generality that $p$ contains only one wire twice from $\mathcal{X}$ and $\mathcal{Y}$ each, say $X$ and $Y$ respectively.
Then this $p$ can also be interpreted as an undirected path in $\varphi$, but generally not in $\varphi_{\textrm{cut}} \coloneqq \Cut_{\mathcal{Z}}(\varphi_{\mathcal{X}, \mathcal{Y}, \mathcal{Z}})$, since it may traverse wires that are not in $\varphi_{\textrm{cut}}$.
However, we now show that there still is an undirected path $p'$ between $X$ and $Y$ in $\varphi_{\textrm{cut}}$.
By the above assumption <ref>, if $p$ contains a wire $Z \in \mathcal{Z}$, then it has to arise from a collider $U \rightarrow Z \leftarrow W$ in $p$.
Removing wire $Z$ from $p$ still defines a valid undirected path between $X$ and $Y$, pictorially:

\begin{equation*}
\tikzfig{figures/dSepGadget1} \qquad \Longrightarrow \qquad \tikzfig{figures/dSepGadget1CUT}
\end{equation*}

We prove that the path $p'$ obtained by removing all wires in $\mathcal{Z}$ from $p$ like this is an undirected path in $\varphi_{\textrm{cut}}$, which implies categorical $d$-connectedness. To this end, it only remains to show that each wire in $p'$ is an existing wire in $\varphi_{\textrm{cut}}$, which we do as follows:

* $X$ and $Y$ themselves are still in $\varphi_{\textrm{cut}}$.

* Every $Z \in \mathcal{Z}$ in $p$ is part of a collider $U \rightarrow Z \leftarrow W$ as above, so that $U, W \in \An(\mathcal{Z})$.
This implies that $U$ and $W$ survive in $\varphi_{\mathcal{X},\mathcal{Y},\mathcal{Z}}$ by <Ref>.

* Since $U$ and $W$ are themselves either the middle node in a chain or fork or the start or end of $p$, we have $U, W \not \in \mathcal{Z}$.
This implies $U, W \in \An(\mathcal{Z}) \setminus \mathcal{Z}$, and therefore $U$ and $W$ survive also in $\varphi_{\textrm{cut}}$.

* For every chain $W \rightarrow M \rightarrow U$ in $p$, if $U$ survives in $\varphi_{\textrm{cut}}$, then so does $M$ (since it survives in $\varphi_{\mathcal{X},\mathcal{Y},\mathcal{Z}}$ and $M \not\in \mathcal{Z}$).

* For every fork $W \leftarrow M \rightarrow U$ in $p$, if $U$ or $W$ survives in $\varphi_{\textrm{cut}}$, then so does $M$ (since it survives in $\varphi_{\mathcal{X},\mathcal{Y},\mathcal{Z}}$ and $M \not\in \mathcal{Z}$).

Since the wires in $p'$ are exactly those of $p$ minus some of the colliders, we can start with the first two observations and then apply the latter two repeatedly on any segment bounded by colliders or the starting node $X$ or the final node $Y$ in order to conclude that all wires in $p'$ are present in $\varphi_{\textrm{cut}}$.
This concludes one direction of the proof.

The converse direction of showing that categorical $d$-connectedness implies classical $d$-connectedness works similarly. Let $p$ be an undirected path between $X \in \mathcal{X}$ and $Y \in \mathcal{Y}$ in $\varphi_{\textrm{cut}}$. We assume without loss of generality that all wires in $p$ are distinct.
Furthermore, we also assume without loss of generality that $p$ is of the form

\begin{equation}
\label{no_bad_colliders}
X \twoheadleftarrow A - B \twoheadrightarrow Y,
\end{equation}

where every wire that is in between $A$ and $B$ is not contained in $\An(\mathcal{X})$ or $\An(\mathcal{Y})$, or equivalently that every wire in $p$ that is also in $\An(\mathcal{X})$ is directly reached from $X$ by output-to-input traversals in $p$, and similarly for all wires in $\An(\mathcal{Y})$.
This property can be achieved by taking every wire in $p$ which is additionally in $\An(\mathcal{X})$ and replace it by the path from $X$ to it by a sequence of output-to-input traversals, and similarly for every wire in $\An(\mathcal{Y})$.
Note that this replacement may involve changing the starting and ending wires $X$ and $Y$ as well.

In order to turn $p$ into a DAG path $p'$ that witnesses classical $d$-separation, we need to remove all direct input-to-input traversals of a box in $p$; direct output-to-output traversals cannot occur due to the assumption that every box has exactly one output.
We can hence simply add to $p$ the unique output wire of every box that has an input-to-input traversal in $p$, and we obtain a valid DAG path $p'$.

It remains to verify the conditions on chains, forks and colliders. Clearly $p'$ does not contain any chain $W \to Z \to U$ or fork $W \leftarrow Z \to U$ with $Z \in \mathcal{Z}$, since such a configuration cannot occur in $p$ to begin with. For a collider $W \to M \leftarrow U$, the unique box which outputs $M$ must be contained in $\varphi_{\mathcal{X},\mathcal{Y},\mathcal{Z}}$, and therefore be in $\An(\mathcal{X} \cup \mathcal{Y} \cup \mathcal{Z})$ by <Ref>. However, $M$ being in $\An(\mathcal{X})$ or $\An(\mathcal{Y})$ violates the assumption that $p$ is of the form (<ref>). Therefore $M$ has to be in $\An(\mathcal{Z})$, showing the collider condition <ref>.

We record one more observation on categorical $d$-separation for further use below.

Let $\varphi$ be a pure bloom causal model and $\mathcal{X}, \mathcal{Y}, \mathcal{Z} \subseteq \Out(\varphi)$ a partition of all output wires such that $\mathcal{Z}$ categorically $d$-separates $\mathcal{X}$ and $\mathcal{Y}$. Then every box $b \in B(G)$ in $\varphi$ satisfies at least one of the cases:

*  $\In(b), \Out(b) \subseteq \mathcal{X} \cup \mathcal{Z}$.

*  $\In(b), \Out(b) \subseteq \mathcal{Y} \cup \mathcal{Z}$.

If there exist $Y \in \mathcal{Y} \cap \Out(b)$ and $X \in \mathcal{X} \cap \Out(b)$, then these wires are still in the output of $b$ in $\varphi_{\textrm{cut}}$, and this contradicts the assumed disconnectedness of $\varphi_{\textrm{cut}}$ with respect to $\mathcal{X}$ and $\mathcal{Y}$. Since $\mathcal{X}, \mathcal{Y}, \mathcal{Z}$ form a partition, this shows that either $\Out(b) \subseteq \mathcal{X} \cup \mathcal{Z}$ or $\Out(b) \subseteq \mathcal{Y} \cup \mathcal{Z}$.

Proving $\Out(b) \subseteq \mathcal{X} \cup \mathcal{Z} \Rightarrow \In(b) \subseteq \mathcal{X} \cup \mathcal{Z}$ and $\Out(b) \subseteq \mathcal{Y} \cup \mathcal{Z} \Rightarrow \In(b) \subseteq \mathcal{Y} \cup \mathcal{Z}$ works similarly, and this then proves the statement.

Pictorially, <Ref> shows that if $\mathcal{Z}$ $d$-separates $\mathcal{X}$ and $\mathcal{Y}$, then every box $b$ in $\varphi$ is of the form

\begin{equation*}
\tikzfig{figures/boxXZ} \qquad \text{ or } \qquad \tikzfig{figures/boxYZ}
\end{equation*}

where $\mathcal{X}_i \subseteq \mathcal{X}$, $\mathcal{Y}_i \subseteq \mathcal{Y}$, $\mathcal{Z}_i \subseteq \mathcal{Z}$.

§.§ Causal compatibility

In the following, we show that $d$-separation implies conditional independence for any generalized causal model. We first prove this result for a partition of wires in a pure bloom causal model in <Ref>. We then refine it to any disjoint collection of wires in <Ref> in any generalized causal model. Finally, we show in <Ref> that $d$-separation fully characterizes causal compatibility for pure bloom causal models in all Markov categories with conditionals.

Throughout, we also use the following convenient notation: If a morphism $f$ in $\cat{C}$ is compatible with a causal model $\varphi$ in the sense of <Ref>, then we refer to the wires of $\varphi$ to indicate conditional independence instead of the objects in the tensor factorization of $f$. In other words, instead of writing $\mathcal{X}' \perp \mathcal{Y}' \ | \ \mathcal{Z}'$, we simply write $\mathcal{X} \perp \mathcal{Y} \ | \ \mathcal{Z}$. Here, each $W' = F(\mathsf{type}(W))$ is the object in $\cat{C}$ associated with the wire $W$ by the causal model functor $F$ (see <Ref>).

Let $\cat{C}$ be a strict Markov category with conditionals, and let $\varphi$ be a pure bloom causal model. Further, let $\mathcal{X}, \mathcal{Y}, \mathcal{Z} \subseteq \Out(\varphi)$ be a partition of wires in $\varphi$ such that $\In(\varphi) \subseteq \mathcal{Y} \cup \mathcal{Z}$ and $\mathcal{X}$ and $\mathcal{Y}$ are $d$-separated by $\mathcal{Z}$.

If a morphism $f$ in $\cat{C}$ is compatible with $\varphi$, then $\mathcal{X} \perp \mathcal{Y} \ | \ \mathcal{Z}$ (as in <Ref>).

Choose a total ordering of all boxes $b_1, \ldots, b_{k-1} \in B(G)$ and a chain of sets of wires in $\Out(\varphi)$,

\begin{equation*}
\In(\varphi) = \mathcal{W}_1 \subseteq \ldots \subseteq \mathcal{W}_k = \Out(\varphi),
\end{equation*}

such that $\mathcal{W}_{i+1} = \Out(b_i) \cup \mathcal{W}_i$ and $\An(\mathcal{W}_i) = \mathcal{W}_i$. Note that there is a factorization

\begin{equation*}
\varphi \quad = \quad \tikzfig{figures/morphismFactorization}
\end{equation*}

in $\cat{FreeMarkov}_\Sigma$, where $\eta_i$ is again a pure bloom and $\eta_1$ is an identity morphism.
The existence of such a chain of sets follows easily by induction on the number of boxes based on the existence of a final box.[It is also worth noting that for causal models which correspond do DAGs, this statement amounts to the standard fact that every DAG can be refined to a total order.]

Then for every $i \in \{1, \ldots, k\}$, we show the existence of a decomposition

\begin{equation}
\label{eq:goalDecompose}
f \quad = \quad \tikzfig{figures/dSepCriterionProof1}
\end{equation}

Since $\mathcal{W}_n^{c} = \emptyset$, setting $i = k$ proves the desired statement.

We prove this stronger claim by induction on $i$. The start of the induction at $i = 1$ is trivial since $\eta_1$ is the identity and therefore

\begin{equation*}
f \quad = \quad \tikzfig{figures/dSepCriterionProof1a}
\end{equation*}

since $\mathcal{Y} \cap \mathcal{W}_1 = \mathcal{Y} \cap \In(\varphi) = \emptyset$. 	For the induction step, we prove the statement at $i+1$. Since $\varphi$ is pure bloom and since $\An(\mathcal{W}_{i+1}) = \mathcal{W}_{i+1}$, we can peel off the box $b_i$ with $\mathcal{W}_{i+1} = \Out(b_i) \cup \mathcal{W}_i$ from $\psi_i$, so as to achieve the decomposition

\begin{equation} \label{eq:dSepInductionStep}
f \quad = \quad \tikzfig{figures/dSepCriterionProof2}
\end{equation}

where we have used the induction assumption to obtain a decomposition as in the lower half, and the dashed wires indicate that only some of them may be present, since the inputs of $b_i$ are an unspecified subset of $\mathcal{W}_i$.

By <Ref> we have to distinguish two cases:

* $\In(b_i),\Out(b_i) \subseteq \mathcal{X} \cup \mathcal{Z}$. Then, the third dashed wire in the above decomposition of $f$ is not needed, and we consider the morphism

\begin{equation*}
g \quad \coloneqq \quad \tikzfig{figures/dSepCriterionProof3}
\end{equation*}

which is part of that decomposition.
By the existence of conditionals, we can rewrite $g$ in the form

\begin{equation*}
g \quad = \quad \tikzfig{figures/dSepCriterionProof4}	\quad = \quad \tikzfig{figures/dSepCriterionProof5}
\end{equation*}

where both lower boxes can be refined with internal structure consisting of carrying $(\mathcal{Z} \cap \mathcal{W}_i)'$ forward on a separate wire, but this internal structure is not relevant for the remainder of the proof.
Substituting this form of $g$ into Equation (<ref>), i.e. replacing the morphism $k_i$ there with the left box here and merging the lower box here with $h_i$ there, proves the induction step.

* $\In(b_i),\Out(b_i) \subseteq \mathcal{Y} \cup \mathcal{Z}$. Then, the first dashed wire in the above decomposition of $f$ is not needed, and we can merge $F(b_i)$ with $h_i$, which shows the statement.

We will now generalize <Ref> to all generalized causal models and to arbitrary disjoint sets $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$ which do not necessarily partition the set of all wires.

Let $\varphi$ be a generalized causal model and $\mathcal{X}$, $\mathcal{Y}$, $\mathcal{Z} \subseteq \Out(\varphi)$ a tripartition of output wires in $\varphi$ such that $\In(\varphi) \subseteq \mathcal{Y} \cup \mathcal{Z}$ and such that $\mathcal{Z}$ categorically $d$-separates $\mathcal{X}$ and $\mathcal{Y}$. Then there exists a tripartition of wires $\widetilde{\mathcal{X}} \supseteq \mathcal{X}$, $\widetilde{\mathcal{Y}} \supseteq \mathcal{Y}$, $\mathcal{Z}$ in the pure bloom version $\varphi_{\textrm{pure-bloom}}$ of $\varphi$[The pure-bloom version $\varphi_{\textrm{pure-bloom}}$ is obtained by copying each wire so to make it into an output. It is part of the bloom-circuitry factorization of [10].] such that

\begin{equation*}
\mathcal{Z} \text{ $d$-separates } \widetilde{\mathcal{X}} \text{ and } \widetilde{\mathcal{Y}} \qquad \text{ in } \varphi_{\textrm{pure-bloom}}
\end{equation*}

With $\varphi_{\textrm{cut}} \coloneqq \Cut_{\mathcal{Z}}(\varphi_{\textrm{pure-bloom}})$, define

\begin{equation*}
\widetilde{\mathcal{X}} \coloneqq \{U \in \Out(\varphi_{\textrm{cut}}): \exists X \in \mathcal{X}: X - U \textrm{ in } \varphi_{\textrm{cut}} \} \supseteq \mathcal{X}
\end{equation*}

to be the connected component of $\mathcal{X}$ in $\varphi_{\textrm{cut}}$, and

\begin{equation*}
\widetilde{\mathcal{Y}} \coloneqq \Out(\varphi_{\textrm{pure-bloom}}) \setminus \left(\widetilde{\mathcal{X}} \cup \mathcal{Z}\right) \supseteq \mathcal{Y}.
\end{equation*}

By definition, $\widetilde{\mathcal{X}}, \widetilde{\mathcal{Y}}$, $\mathcal{Z}$ form a tripartition of wires in $\varphi_{\textrm{pure-bloom}}$. Moreover,
$\widetilde{\mathcal{X}}$ and $\widetilde{\mathcal{Y}}$ are categorically $d$-separated by $\mathcal{Z}$ since any path in $\Cut_{\mathcal{Z}}(\varphi_{\textrm{pure-bloom}})$ is a valid path in $\Cut_{\mathcal{Z}}(\varphi)$ and vice versa.

Let $\cat{C}$ be a strict Markov category with conditionals, and let $\varphi$ be a generalized causal model.[In this situation $\varphi$ does not need to be pure bloom.] Further, let $\mathcal{X}, \mathcal{Y}, \mathcal{Z} \subseteq \Out(\varphi)$ be disjoint sets of output wires in $\varphi$ such that $\In(\varphi) \subseteq \mathcal{Y} \cup \mathcal{Z}$ and $\mathcal{X}$ and $\mathcal{Y}$ are $d$-separated by $\mathcal{Z}$. If $f$ is compatible with $\varphi$, then $\mathcal{X} \perp \mathcal{Y} \ | \ \mathcal{Z}$.

In this statement, we use another standard convention: when the disjoint sets $\mathcal{X},\mathcal{Y},\mathcal{Z}$ do not partition the set of wires of $\varphi$, then the conditional independence $\mathcal{X} \perp \mathcal{Y} \ | \ \mathcal{Z}$ is to be understood as <Ref> applied to the corresponding marginal $f_{\mathcal{X}',\mathcal{Y}',\mathcal{Z}'}$ rather than to $f$ itself.

We prove this statement by reducing it to the case of pure bloom causal models treated in <Ref>.

Consider the restricted causal model $\psi \coloneqq \varphi_{\mathcal{X}, \mathcal{Y}, \mathcal{Z}}$ and its compatible morphism $g \coloneqq F(\psi)$ obtained from the compatibility of $f$ with $\varphi$, which is a marginal of $f$. By the definition of categorical $d$-separation, $\mathcal{Z}$ $d$-separates $\mathcal{X}$ and $\mathcal{Y}$ also in $\psi$. Let $\psi_{\textrm{pure-bloom}}$ be the pure bloom version of $\psi$. Since $g$ is compatible with $\psi$, we can extend $g$ to a pure bloom version

\begin{equation*}
g_{\textrm{pure-bloom}} \coloneqq F(\psi_{\textrm{pure-bloom}})
\end{equation*}

of which $g$ is a marginal.

By <Ref>, for $\psi_{\textrm{pure-bloom}}$ there is a tripartition of output wires $\widetilde{\mathcal{X}} \supseteq \mathcal{X}, \widetilde{\mathcal{Y}} \supseteq \mathcal{Y}$, $\mathcal{Z}$ such that $\mathcal{Z}$ $d$-separates $\widetilde{\mathcal{X}}$ and $\widetilde{\mathcal{Y}}$. Since $\cat{C}$ has conditionals, <Ref> provides us with a decomposition of the form

\begin{equation*}
g_{\textrm{pure-bloom}} \quad = \quad \tikzfig{figures/ConditionalIndependenceMorphismTilde}
\end{equation*}

By marginalizing over $\widetilde{\mathcal{X}}' \setminus \mathcal{X}'$, $\widetilde{\mathcal{Y}}' \setminus \mathcal{Y}'$ in $g_{\textrm{pure-bloom}}$, we obtain the desired conditional independence for the marginal $f_{\mathcal{X}', \mathcal{Y}', \mathcal{Z}'}$.

Note that this result includes the soundness of the classical $d$-separation criterion in the classical case of discrete random variables in Bayesian networks[See [21] for the original proof and <cit.> for a textbook account.], which is obtained upon restricting to pure bloom causal models with $\In(\varphi) = \emptyset$, the Markov category $\cat{FinStoch}$, and every box having precisely one output, since then conditional independence reduces to <Ref> by <Ref>.

Let $\varphi$ be a generalized causal model and $f$ a morphism in a strict Markov category $\cat{C}$. Then we say that $f$ satisfies:

* the global Markov property with respect to $\varphi$ if for every three disjoint sets of outputs $\mathcal{X},\mathcal{Y}$, $\mathcal{Z} \subseteq \Out(\varphi)$ with $\In(\varphi) \subseteq \mathcal{Y} \cup \mathcal{Z}$:

\begin{equation*}
\mathcal{X} \text{ and } \mathcal{Y} \text{ are categorically $d$-separated by  } \mathcal{Z} \; \text{ in } \varphi \quad \Longrightarrow \quad \mathcal{X} \perp \mathcal{Y} \ | \ \mathcal{Z} \; \text{ in } f.
\end{equation*}

* the local Markov property with respect to $\varphi$ if for every box $b$ in  $\varphi$, we have

\begin{equation*}
\Out(b) \perp \Dec(\Out(b))^{c} \setminus \In(b) \ | \ \In(b) \; \text{ in } f.
\end{equation*}

Suppose that we are given the following:

* $\cat{C}$ is a strict Markov category with conditionals.

* $\varphi$ is a pure bloom causal model over a hypergraph $\Sigma$ such that the boxes in $\varphi$ have distinct types in $\Sigma$.

* $f : \bigotimes_{i=1}^n W'_i \to \bigotimes_{j=1}^m V'_j$ is a morphism in $\cat{C}$.

Then the following statements are equivalent:

*  $f$ is compatible with the causal model $\varphi$.

*  $f$ satisfies the global Markov property.

*  $f$ satisfies the local Markov property.

$\ref{thm_compat} \Longrightarrow \ref{thm_global}$: The global Markov property is precisely the statement of <Ref>.

$\ref{thm_global} \Longrightarrow \ref{thm_local}$: This follows from the fact that $\Dec(\Out(b))^{c}$ and $\Out(b)$ are $d$-separated by $\In(b)$, and $\In(\varphi) \subseteq \Dec(\Out(b))^{c}$, which makes the global Markov property specialize to the local one.

$\ref{thm_local} \Longrightarrow \ref{thm_compat}$: We prove this statement by induction over the number of boxes $k \coloneqq |B(G)|$. The case $k = 1$ is trivial. For the step from $k$ to $k+1$, let $b$ be a final box in $\varphi$, which means that $\Dec(\Out(b)) = \Out(b)$. Then, $\varphi$ factorizes as

\begin{equation*}
\varphi \quad = \quad \tikzfig{figures/proofLocalMarkov0}
\end{equation*}

where $\psi$ is another causal model satisfying all of our assumptions, and no box in $\psi$ has the same type in $\Sigma$ as $b$ does.

In order to construct a functor $F$ as in <Ref>, note first that it must satisfy (<ref>), which already lets us write the domain of $f$ as $\In(\varphi)'$, and similarly for the codomain.
Since $f$ satisfies the local Markov property with respect to $b$, we can decompose $f$ by <Ref> as

\begin{equation}
\label{eq:proofLocalMarkov1} \tikzfig{figures/proofLocalMarkov1} \quad = \quad \tikzfig{figures/proofLocalMarkov4a}
\end{equation}

By induction hypothesis, we have that $g$ is compatible with $\psi$ since $g$ satisfies the local Markov properties specified by $\psi$. Since the box $b$ appears only once in $\varphi$, we can freely define the action of the functor $F$ on $b$ as $F(b) \coloneqq h$. Then, we obtain

\begin{equation*}
\tikzfig{figures/proofLocalMarkov3} \quad = \quad \tikzfig{figures/proofLocalMarkov4a} \quad = \quad \tikzfig{figures/proofLocalMarkov4} \quad = \quad \tikzfig{figures/proofLocalMarkov5}
\end{equation*}

where we use in the first step Equation (<ref>) and in the last the fact that $F$ is a Markov functor.

* Note that we have used the assumption that $\cat{C}$ has conditionals only for the implication $\ref{thm_compat} \Longrightarrow \ref{thm_global}$. Therefore, for an arbitrary strict Markov category, the global as well as the local Markov property is a sufficient condition for the compatibility of a morphism with a generalized causal model (satisfying our assumptions). However, these Markov properties require implicitly the existence of certain conditionals. Consider for example the generalized causal model

\begin{equation*}
\varphi \quad = \quad \tikzfig{figures/emptySeparationExample}
\end{equation*}

where all boxes are of distinct types.
Choosing $\mathcal{X} = \{M\}, \mathcal{Y} = \emptyset$ and $\mathcal{Z} = \{X, Y\}$, a morphism $f$ satisfying the global Markov property displays in particular the conditional independence $\{M\} \perp \emptyset \ | \ \mathcal{Z}$, pictorially:

\begin{equation*}
f \quad = \quad \tikzfig{figures/emptySeparationExample2}
\end{equation*}

This shows that the conditional $f_{|_\mathcal{Z}}$ exists, and this recovers the box that outputs $M$ (up to almost sure equality).

* <Ref> shows that $d$-separation correctly detects causal compatibility for the Markov categories $\cat{FinStoch}$, $\cat{Gauss}$ or $\cat{BorelStoch}$. For the Markov category $\cat{Stoch}$, which does not have conditionals, the global and local Markov properties are at least sufficient for the compatibility, since our proof of these implications has not used conditionals.

* Note that <Ref> only applies to causal models where each box appears at most once in the model (which in particular implies that $\varphi$ has no nontrivial symmetries). However, the implication $\ref{thm_compat} \Longrightarrow \ref{thm_global}$ applies to arbitrary generalized causal models as proven in <Ref>.

We now present two examples which go beyond the classical $d$-separation criterion. In (i) we will study a causal structure which does not arise from a DAG, while in (ii) we study a DAG causal structure with continuous variables.

*  Let $\varphi$ be the causal structure

\begin{equation*}
\tikzfig{figures/DAGImpossibleScenarioConcrete}
\end{equation*}

and let $\cat{C}$ be a strict Markov category with conditionals. By <Ref>, a morphism $t : I \to X' \otimes Z'_1 \otimes Z'_2 \otimes Y'$ in $\cat{C}$ is compatible with this structure if and only if it satisfies

\begin{equation*}
X \perp \{Y, Z_2\} \ | \ Z_1 \quad \text{ and } \quad Y \perp \{X, Z_1\} \ | \ Z_2
\end{equation*}

For a general class of examples, consider $X' = Z'_2$ and $Y' = Z'_1$ and any morphism in $\cat{C}$ of the form

\begin{equation*}
\tikzfig{figures/BipartiteProbability00}
\end{equation*}

We claim that such a distribution is compatible with $\varphi$ if and only if there exist morphisms $d$ and $d'$ such that

\begin{equation}
\label{eq:deterministicCompatibility} \tikzfig{figures/BipartiteProbability} \quad = \quad \tikzfig{figures/BipartiteProbabilityDeterministicMorphism} \quad = \quad \tikzfig{figures/BipartiteProbabilityDeterministicMorphism2}
\end{equation}

where $s$ is the first marginal of $r$, and similarly $d' : Z'_2 \to Z'_1$ satisfies the same equations the other way around.
Here, the second equation states that the morphism $d$ is $s$-a.s. deterministic <cit.>, and similarly for $d'$.

Indeed, assuming compatibility we have that

\begin{equation}
\label{eq:deterministic1}
\tikzfig{figures/BipartiteProbability01} \quad = \quad \tikzfig{figures/BipartiteProbability02}
\end{equation}

which shows the first equality in Equation (<ref>). For the second equality we have that

\begin{equation*}
\tikzfig{figures/BipartiteProbability03} \quad = \quad \tikzfig{figures/BipartiteProbability04} \quad = \quad \tikzfig{figures/BipartiteProbability05}
\end{equation*}

where we have used the conditional independence $Z_2 \perp X \ | \ Z_1$ in the first step and Equation (<ref>) in the second step. Since the morphism is symmetric with respect to permutations of the output wires $X$ and $Z_2$, we have $a = F(f)$ $s$-a.s. which shows the second equality in Equation (<ref>).
Proving the existence of $d'$ works analogously by interchanging the roles of $X$ and $Y$ as well as $Z_1$ and $Z_2$.

Conversely, we have

\begin{equation*}
\tikzfig{figures/BipartiteProbability00} \quad = \quad \tikzfig{figures/BipartiteProbability06} \quad = \quad \tikzfig{figures/BipartiteProbability07} \quad = \quad \tikzfig{figures/BipartiteProbability08}
\end{equation*}

where we have used the assumption that $d$ is $s$-a.s. deterministic in the second equation. Repeating this calculation interchanging the roles of $Z_1$ and $Z_2$ as well as $X$ and $Y$ shows the statement.

* Consider the instrumental scenario, given by the DAG

\begin{equation*}
\begin{tikzpicture}[scale=0.75]
\draw[fill=white, line width=0.2mm] (0,0) circle (0.8cm) node{\scriptsize $A$};
\draw[fill=white, line width=0.2mm] (6,0) circle (0.8cm) node{\scriptsize $B$};
\draw[fill=white, line width=0.2mm] (3,3) circle (0.8cm) node{\scriptsize $\Lambda$};
\draw[fill=white, line width=0.2mm] (0,4) circle (0.8cm) node{\scriptsize $X$};

\draw[-stealth,line width=0.2mm] (0,3) -- (0,1);
\draw[-stealth,line width=0.2mm] (1,0) -- (5,0);
\draw[-stealth,line width=0.2mm, rotate around={45:(3,3)}] (3,2) -- (3,-0.2);
\draw[-stealth,line width=0.2mm, rotate around={-45:(3,3)}] (3,2) -- (3,-0.2);
\end{tikzpicture}
\end{equation*}

This has been previously studied mainly in the context of DAGs with latent variables [17, 2]. For our analysis we assume each variable to be observed, which means that the causal structure reads string-diagrammatically as

\begin{equation}
\label{eq:PearlStringDiagram}
\varphi \quad = \quad \tikzfig{figures/InstrumentalScenario}
\end{equation}

There are two non-trivial $d$-separations:

* Between $X$ and $B$ by $\{A, \Lambda\}$,

* Between $X$ and $\Lambda$.

Therefore, <Ref> implies that a distribution $P$ on a four-fold tensor product object in a Markov category with conditionals is compatible with $\varphi$ if and only if $X \perp B \ | \ A, \Lambda$ and $X \perp \Lambda$.
In $\cat{BorelStoch}$, this means that $P$ is compatible with $\varphi$ if and only if

\begin{align*}
& P(X \in E_1, A \in E_2, B \in E_3, \Lambda \in E_4) \\ &= \int_{E_2} \int_{E_4} P_{X|A, \Lambda}(X \in E_1|a, \lambda) \, P_{B|A, \Lambda}(B \in E_3|a, \lambda) \, P_{A,\Lambda}(\mathrm{d} a, \mathrm{d}\lambda)
\end{align*}

\begin{align*}
P(X \in E_1, \Lambda \in E_4) = P(X \in E_1) \cdot P(\Lambda \in E_4)
\end{align*}

where $E_i$ are measurable sets in the Borel $\sigma$-algebras of the spaces $X', A', B'$ and $\Lambda'$.

For simplicity, assume that all random variables take values in $\mathbb{R}$ and are absolutely continuous, i.e. there exists a density $f: X' \times A' \times B \times \Lambda' \to [0,\infty)$ such that

\begin{equation*}
P(X \in E_1, A \in E_2, B \in E_3, \Lambda \in E_4) = \int_{E_1 \times E_2 \times E_3 \times E_4} f(x,a,b,\lambda) \diff x \diff a \diff b \diff \lambda
\end{equation*}

The causal compatibility now amounts to the following two conditions:

* $X \perp \Lambda$, i.e.

\begin{equation}
\label{eq:Ind}
f_{X,\Lambda}(x,\lambda) = f_{X}(x) \cdot f_{\Lambda}(\lambda) \quad \text{ a.e.}
\end{equation}

where a.e. means almost everywhere with respect to the Lebesgue measure on $\mathbb{R}$.

* $X \perp B \ | \ A, \Lambda$, i.e.
\begin{equation}
\label{eq:condInd}
f(x,a,b,\lambda) = f_{X|A,\Lambda}(x,a,\lambda) \cdot f_{A,\Lambda}(a,\lambda) \cdot f_{B|A,\Lambda}(b,a,\lambda) \quad \text{ a.e.},
\end{equation}

where the conditional densities are defined implicitly by

\[
f_{A|X\Lambda}(a|x,\lambda) \cdot f_{X,\Lambda}(x,\lambda) = f_{X,A,\Lambda}(x,a,\lambda) \quad \text{ a.e.}
\]

Combining Eq. (<ref>) and Eq. (<ref>) results in

\begin{equation*}
f(x,a,b,\lambda) = f_{\Lambda}(\lambda) \cdot f_{X}(x) \cdot f_{A|X\Lambda}(a,x,\lambda) \cdot f_{B|A,\Lambda}(b,a,\lambda) \quad \text{ a.e.}
\end{equation*}

which is the usual factorization condition for compatibility with the causal structure in (<ref>).

Can <Ref> be extended to more general causal models? In particular, what about allowing the same box to appear several times in $\varphi$?

[1]
F. Bonchi, F. Gadducci, A. Kissinger, P. Sobociński, and F. Zanasi.
Rewriting modulo symmetric monoidal structure.
Proceedings - Symposium on Logic in Computer Science, pages
710–719, 2016.

[2]
B. Bonet.
Instrumentality tests revisited.
In Proceedings of the Seventeenth Conference on Uncertainty in
Artificial Intelligence, pages 48–55. Morgan Kaufmann Publishers Inc.,

[3]
K. Cho and B. Jacobs.
Disintegration and Bayesian inversion via string diagrams.
Mathematical Structures in Computer Science, 29:938–971, 2019.

[4]
B. Coecke and R. W. Spekkens.
Picturing classical and quantum Bayesian inference.
Synthese, 186:651, 2011.

[5]
A. Corradini and F. Gadducci.
An algebraic presentation of term graphs, via gs-monoidal categories.
Applied Categorical Structures, 7:299–331, 1999.

[6]
B. Fong.
Causal theories: A categorical perspective on Bayesian networks.
Master's thesis, University of Oxford, 2013.

[7]
P. Forré.
Transitional conditional independence, 2021.

[8]
P. Forré and J. M. Mooij.
Markov properties for graphical models with cycles and latent
variables, 2017.

[9]
T. Fritz.
A synthetic approach to Markov kernels, conditional independence
and theorems on sufficient statistics.
Advances in Mathematics, 370:1–98, 2020.

[10]
T. Fritz and W. Liang.
Free gs-monoidal categories and free Markov categories, 2022.

[11]
F. Gadducci.
On The Algebraic Approach To Concurrent Term Rewriting.
PhD thesis, University of Pisa, 1996.

[12]
D. Gao.
Functorial causal models: Towards an algebraic approach to causal
Bachelor's thesis, Brown University, 2022.

[13]
B. Jacobs, A. Kissinger, and F. Zanasi.
Causal inference by string diagram surgery.
Lecture Notes in Computer Science, 11425 LNCS:313–329, 2019.

[14]
S. L. Lauritzen.
Graphical Models, volume 18 of Oxford Statistical Science
Oxford University Press, 1996.

[15]
S. L. Lauritzen, A. P. Dawid, B. N. Larsen, and H.-G. Leimer.
Independence properties of directed markov fields.
Networks, 20:491–505, 1990.

[16]
A. Milosavljevic and F. Zanasi.
String diagram rewriting modulo commutative monoid structure, 2022.

[17]
J. Pearl.
On the testability of causal models with latent and instrumental
In Proceedings of the Eleventh Conference on Uncertainty in
Artificial Intelligence, pages 435–443. Morgan Kaufmann Publishers Inc.,

[18]
J. Pearl.
Causality: Models, reasoning, and inference.
Cambridge University Press, 2009.
Second edition.

[19]
E. F. Rischel.
The category theory of causal models.
Master's thesis, University of Copenhagen, 2020.

[20]
E. F. Rischel and S. Weichwald.
Compositional abstraction error and a category of causal models.
In Proceedings of the Thirty-Seventh Conference on Uncertainty
in Artificial Intelligence, volume 161, pages 1013–1023. MLResearchPress,

[21]
T. Verma and J. Pearl.
Causal networks: Semantics and expressiveness.
In Proceedings of the Fourth Conference on Uncertainty in
Artificial Intelligence, volume 9, pages 69–76. Morgan Kaufmann Publishers,