istributional Invariances and Interventional Markov Equivalence for Mixed Graph Model

The invariance properties of interventional distributions relative to the observational distribution, and how these properties allow us to refine Markov equivalence classes (MECs) of DAGs, is central to causal DAG discovery algorithms that use both interventional and observational data. Here, we show how the invariance properties of interventional DAG models, and the corresponding refinement of MECs into interventional MECs, can be generalized to mixed graphical models that allow for latent cofounders and selection variables. We first generalize interventional Markov equivalence to all formal independence models associated to loopless mixed graphs. For ancestral graphs, we prove the resulting interventional MECs admit a graphical characterization generalizing that of DAGs. We then define interventional distributions for acyclic directed mixed graph models, and prove that this generalization aligns with the graphical generalization of interventional Markov equivalence given for the formal independence models. This provides a framework for causal model discovery via observational and interventional data in the presence of latent confounders that applies even when the interventions are uncontrolled.

Introduction {#sec: introduction}
============

A major goal in statistics is to predict the effects of interventions amongst jointly distributed random variables. This is relevant in fields such as medicine, computational biology, and economics where practitioners are interested in altering predicted outcomes @P00 [@RHB00; @SGS01]. Oftentimes, the goal is to learn a causal DAG, which encodes a set of conditional independence (CI) relations and whose edges encode causal relations amongst the variables. However, using observational data alone, it is only possible to learn a causal DAG up to the CI relations it encodes, which are the same for all DAGs in its Markov equivalence class (MEC) @AMP97.

By further sampling from interventional distributions, i.e., distributions produced by modifying variables within the system, identifiability of a causal DAG can be improved. For example, perfect (or hard) interventions @EGS05, which force the targeted variables to the values of independent variables, partition an MEC of DAGs into perfect ${\mathcal{I}}$-MECs @HB12. Similarly, general interventions, which do not necessarily force the targeted variables to become independent, partition an MEC of DAGs into (general) ${\mathcal{I}}$-MECs @YKU18. Recently, @HB12 and @YKU18 gave graphical characterizations of perfect ${\mathcal{I}}$-MECs and ${\mathcal{I}}$-MECs for DAGs, respectively. These characterizations play a key role in algorithms that use observational and interventional data to learn causal DAGs @HB12 [@WSKU17; @YKU18].

While DAG models are a natural starting point for causal inference, they make restrictive assumptions that can be alleviated by working with more general mixed graph models. For example, biologists are interested in learning protein synthesis networks that use both directed and bidirected arrows @Sachs05. Mixed graph models associate CI relations to a graph with edges that may be directed, bidirected, or undirected, and thereby incorporate latent confounders and selection variables into the model. The goal then is to relate the interventional and observational distributions so as to learn the signaling network exactly; that is, to learn exactly which edge types are in which locations. For DAG models this is done by studying the invariances in the factorization of the interventional distribution with respect to a DAG relative to the factorization for the observational distribution. In @YKU18, the authors showed that these invariance properties of DAG model factorizations are encoded entirely by combinatorial separation properties of DAGs. Thus, to generalize the theory of interventional Markov equivalence for DAG models to mixed graph models, there are two avenues to consider: (1) generalize the distributional invariance properties of DAG models to models admitting similar factorization criteria, and (2) generalize the invariance properties as they are encoded via combinatorial separation statements in mixed graphs. Here, we will study both of these generalizations to the fullest extent possible (as permitted by the existing theory of mixed graph models). In doing so, we will provide a complete generalization of the theory of interventional Markov equivalence for DAG models (i.e., a theory unifying both (1) and (2)) to the family of directed ancestral graph models.

To do so, we first generalize interventional Markov equivalence to all formal independence models for loopless mixed graphs. Under mild assumptions on the intervention targets, we extend the graphical characterization of interventional Markov equivalence of @YKU18 to all ancestral graphs (AGs). We then define interventional distributions for acyclic directed mixed graph models (ADMGs) based on invariance properties of their factorization criterion. We prove that any distribution arising as the marginal of a post-intervention distribution Markov to a DAG over the observed variables will be an interventional distribution with respect to the ADMG that is the latent projection of the DAG onto the observed variables. Finally, we prove that our generalization of interventional Markov equivalence for AGs via formal independence models and the probabilistic version for ADMGs coincide at their intersection; i.e., for all directed AGs. In this case, we require no assumptions on the intervention targets. In particular, the theory developed here extends the recent work of @KJSB19 who studied interventional Markov equivalence when the interventions are *controlled*; an assumption restricting the distributions that can be considered. The theory presented here applies to any mixture of observational and interventional data, even for uncontrolled interventions.

Formal Independence Models and Mixed Graphs {#sec: independence models and mixed graphs}
===========================================

We first recall the necessary basics of mixed graph models, formal independence models, and interventions. All graph theory terms that are not defined in the following are defined in the appendix. A *mixed graph* is a graph ${\mathcal{G}}= ([p],E)$ in which the set of edges $E$ contains a mixture of *undirected* $i-j$, *bidirected* $i \leftrightarrow j$, and *directed* $i\rightarrow j$ edges. If it is ambiguous as to whether or not there is an arrowhead at the endpoint $i$ of an edge $e$, we will place an empty circle at the endpoint $i$; for example, $i {\,\circ\!\!\! \rightarrow \! }j$. A *loopless mixed graph* (LMG) is a mixed graph that does not contain any *loops*; i.e., edges which have both endpoints being the same node. We will call an LMG *simple* if between any two nodes there is at most one edge. We can define a notion of separation within an LMG that generalizes the notion of $d$-separation in DAGs @SL14: Let ${\mathcal{G}}= ([p],E)$ be an LMG and $C\subset[p]$. A path $\langle v_1,v_2,v_3\rangle$ in ${\mathcal{G}}$ is a *collider path* if the two edges on the path both have arrows pointing towards $v_2$. It is further called a *v-structure* if $v_1$ and $v_3$ are non-adjacent in ${\mathcal{G}}$. A path $\pi$ is *$m$-connecting* given $C$ in ${\mathcal{G}}$ if all of its collider subpaths $\langle v_1,v_2,v_3\rangle$ have $v_2\in C\cup\an_{\mathcal{G}}(C)$ and all of its nodes that are not $v_2$ for some collider subpath are not in $C$. For two disjoint subsets $A,B\subset[p]$, we say $C$ *$m$-separates* $A$ and $B$ in ${\mathcal{G}}$ if there is no $m$-connecting path between a node in $A$ and a node in $B$ given $C$ in ${\mathcal{G}}$.

To an LMG ${\mathcal{G}}= ([p],E)$, we associate a collection of triples ${\mathcal{J}}({\mathcal{G}})$, where $
\langle A, B \mid C\rangle \in {\mathcal{J}}({\mathcal{G}})
$ if and only if $A$ and $B$ are $m$-separated given $C$ in ${\mathcal{G}}$. We call the set of triples ${\mathcal{J}}({\mathcal{G}})$ the *(formal) independence model* for ${\mathcal{G}}$. In general, ${\mathcal{G}}$ is not uniquely determined by ${\mathcal{J}}({\mathcal{G}})$, which leads to the notion of Markov equivalence:

\[def: markov equivalence\] Two LMGs ${\mathcal{G}}$ and ${\mathcal{H}}$ are *Markov equivalent*, denoted ${\mathcal{G}}\approx{\mathcal{H}}$, and belong to the same *Markov equivalence class* (MEC) if ${\mathcal{J}}({\mathcal{G}}) = {\mathcal{J}}({\mathcal{H}})$.

A distribution $\mathbb{P}$ over random variables $X_1,\ldots,X_p$ is *Markov* with respect to ${\mathcal{G}}$ if $\mathbb{P}$ entails $X_A{\protect\mathpalette{\protect\independenT}{\perp}}X_B\mid X_C$ whenever $\langle A, B\mid C\rangle\in {\mathcal{J}}({\mathcal{G}})$. We let ${\mathcal{M}}({\mathcal{G}})$ denote the collection of all density functions of distributions $\mathbb{P}$ that are Markov to ${\mathcal{G}}$. If there exists $\mathbb{P}$ such that ${\mathcal{J}}({\mathcal{G}})$ encodes precisely the set of CI relations entailed by $\mathbb{P}$ then we call ${\mathcal{J}}({\mathcal{G}})$ a *probabilistic independence model*. A number of families of LMGs yield well-studied probabilistic independence models.

The structure of an LMG ${\mathcal{G}}= ([p],E)$ is intimately tied to the factorization of the distributions in ${\mathcal{M}}({\mathcal{G}})$. The LMG ${\mathcal{G}}$ is called a *directed acyclic graph* (DAG) if it has only directed edges and no directed cycles. In this case, $f\in {\mathcal{M}}({\mathcal{G}})$ if and only if it factorizes in a simple way: $$\label{eqn:DAG}
f(x) = \prod_{i\in[p]}f(x_i \mid x_{\pa_{\mathcal{G}}(i)}).$$ In the case of DAGs, typically all members of an MEC only have a subset of their directed arrows in common. Thus, we can only learn a subset of the causal relations between nodes by sampling from the observational distribution. One way to improve identifiability of the causal DAG, i.e., learn more of the directed arrows, is to perform interventions on variables in the system and sample data from the resulting interventional distributions. Let $X = (X_1,\ldots,X_p)$ be a random vector with joint distribution $\mathbb{P}$ Markov to a DAG ${\mathcal{G}}= ([p],E)$, and let $f^{(\emptyset)}$ denote its density function. Given a subset $I\subset[p]$, called an *intervention target*, a distribution with density $f^{(I)}$ admitting a factorization $$\label{eqn: interventional distribution}
f^{(I)}(x) = \prod_{i\in I}f^{(I)}(x_i \mid x_{\pa_{\mathcal{G}}(i)})\prod_{i\notin I}f^{(\emptyset)}(x_i \mid x_{\pa_{\mathcal{G}}(i)})$$ is called an *interventional distribution* (with respect to ${\mathcal{G}}$ and $I$). The intervention is *perfect* if $f^{(I)}(x_i \mid x_{\pa_{\mathcal{G}}(i)}) = f^{(I)}(x_i)$ for all $i\in I$.

Let ${\mathcal{I}}$ be a multiset of intervention targets, and $(f^{(I)})_{I\in{\mathcal{I}}}$ be a sequence of densities over $X = (X_1,\ldots,X_p)$ indexed by the elements of ${\mathcal{I}}$. For a DAG ${\mathcal{G}}= ([p],E)$, define the set of *intervention settings* for ${\mathcal{G}}$ with respect to ${\mathcal{I}}$ as $$\label{eqn: DAG interventional distributions}
\begin{split}
{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) :=&\{(f^{(I)})_{I\in{\mathcal{I}}} \mid
\forall I,J\in{\mathcal{I}}: f^{(I)}\in{\mathcal{M}}({\mathcal{G}}), \mbox{ and }\\ 
&f^{(I)}(x_i\mid x_{\pa_{\mathcal{G}}(i)}) = f^{(J)}(x_i\mid x_{\pa_{\mathcal{G}}(i)}) \mbox{ for all } i\notin I\cup J\}.\\
\end{split}$$ Since ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ represents the collection of all sequences of densities that can be generated from the interventions ${\mathcal{I}}$, @YKU18 used this to formally define Markov equivalence of DAGs under general interventions:

@YKU18 [Definition 3.4] \[def: I-Markov equivalence of DAGs\] For the intervention targets ${\mathcal{I}}$, two DAGs ${\mathcal{G}}$ and ${\mathcal{H}}$ are *${\mathcal{I}}$-Markov equivalent* and belong to the same *${\mathcal{I}}$-Markov equivalence class* (${\mathcal{I}}$-MEC) if ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$.

Notice that this definition, which relies on invariance properties of the factorization <span> </span>, is fundamentally different than the definition of Markov equivalence of DAGs given by Definition \[def: markov equivalence\], which is phrased in terms of global Markov properties. However, the result of @YKU18 [Theorem 3.9] demonstrates that ${\mathcal{I}}$-Markov equivalence of DAGs can also be defined using the global Markov property of DAGs. This suggests a generalization to mixed graph models, for which it is easier to work with global Markov properties since the corresponding factorization criteria generalizing <span> </span> are not as simple (or simply unknown).

Interventional graphs and global ${\mathcal{I}}$-Markov properties  {#subsec: interventional graphs and global I-markov properties}
-------------------------------------------------------------------

We now recall the result of @YKU18 so as to set the stage for our corresponding generalization.

\[def: interventional graph\] Let ${\mathcal{G}}= ([p],E)$ be an LMG and ${\mathcal{I}}$ a collection of intervention targets. The *interventional graph for ${\mathcal{I}}$* (${\mathcal{I}}$-LMG) is the graph ${\mathcal{G}}^{\mathcal{I}}$ with nodes $[p]\cup W_{\mathcal{I}}$, where $$W_{\mathcal{I}}:=\{\omega_I \mid I\in{\mathcal{I}}\backslash\{\emptyset\}\},$$ and edges $E\cup E_{\mathcal{I}}$, where $$E_{\mathcal{I}}:= \{\omega_I\rightarrow i \mid i\in I, I\in{\mathcal{I}}\backslash\{\emptyset\}\}.$$

\[thick,scale=0.3\]

\(1) at (-24,3) <span>$1$</span>; (2) at (-22,0) <span>$2$</span>; (3) at (-21,3) <span>$3$</span>; (4) at (-18,3) <span>$4$</span>; (5) at (-15,3) <span>$5$</span>; (6) at (-15,0) <span>$6$</span>; (7) at (-18,0) <span>$7$</span>;

(g1) at (-9,3) <span>$1$</span>; (g2) at (-7,0) <span>$2$</span>; (g3) at (-6,3) <span>$3$</span>; (g4) at (-3,3) <span>$4$</span>; (g5) at (0,3) <span>$5$</span>; (g6) at (0,0) <span>$6$</span>; (g7) at (-3,0) <span>$7$</span>;

(gw1) at (-10,5) ; (gw14) at (-6,6) ; (gw4) at (-1,5) ;

\(1) – (2) ; (2) – (3) ; (4) – (3) ; (4) – (5) ; (5) – (6) ; (6) – (7) ; (7) – (4) ;

(g1) – (g2) ; (g2) – (g3) ; (g4) – (g3) ; (g4) – (g5) ; (g5) – (g6) ; (g6) – (g7) ; (g7) – (g4) ; (gw1) – (g1) ; (gw14) – (g1) ; (gw14) – (g4) ; (gw4) – (g4) ;

at (-9,5.5) <span>$\omega_{\{1\}}$</span>; at (-4,6) <span>$\omega_{\{1,4\}}$</span>; at (0,5.5) <span>$\omega_{\{4\}}$</span>; at (-13.5,-1) <span>${\mathcal{G}}$</span>; at (1.5,-1) <span>${\mathcal{G}}^{\mathcal{I}}$</span>;

Figure \[fig: intervention example\] shows an LMG and its ${\mathcal{I}}$-LMG.[^1] @VP91 proved two DAGs are Markov equivalent if and only if they have the same adjacencies and the same v-structures. The characterization of ${\mathcal{I}}$-MECs given by @YKU18 extends this result via the combinatorics of ${\mathcal{I}}$-DAGs. When considered in the context of @VP91, their characterization frames ${\mathcal{I}}$-Markov equivalence for DAGs in terms of the global Markov property for DAGs. In the following, if $\langle i,j,k\rangle$ is a v-structure in an ${\mathcal{I}}$-LMG ${\mathcal{G}}^{\mathcal{I}}$ such that $i$ or $k$ is in $W_{\mathcal{I}}$, we call it an *${\mathcal{I}}$-v-structure*.

@YKU18 [Theorem 3.9] \[thm: YKU characterization\] Let ${\mathcal{I}}$ be a collection of interventional targets for which $\emptyset\in{\mathcal{I}}$. Two DAGs ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent if and only if ${\mathcal{G}}$ and ${\mathcal{H}}$ are Markov equivalent and ${\mathcal{G}}^{\mathcal{I}}$ and ${\mathcal{H}}^{\mathcal{I}}$ have the same ${\mathcal{I}}$-v-structures.

It is worth noting that @MCM16 also consider ${\mathcal{I}}$-LMGs in their *Joint Causal Inference* (JCI) framework, in which they use the ${\mathcal{I}}$-LMG to learn causal structure by applying classic causal discovery algorithms to the ${\mathcal{I}}$-LMG. On the other hand, they do not provide explicit graphical characterizations of ${\mathcal{I}}$-MECs as in Theorem \[thm: YKU characterization\].

By the result of @VP91, Theorem \[thm: YKU characterization\] equivalently states that two DAGs ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent if and only if ${\mathcal{G}}^{\mathcal{I}}$ and ${\mathcal{H}}^{\mathcal{I}}$ are Markov equivalent. The former interpretation (stated in Theorem \[thm: YKU characterization\]) captures the intuition that intervening on nodes of a graph should "lock" more arrows in place; that is, determine more causal relations. However, the latter interpretation suggests a natural generalization of ${\mathcal{I}}$-Markov equivalence to formal independence models for LMGs, free of a factorization criterion, and based solely on global Markov properties:

\[def: LMG I-Markov equivalence\] Let ${\mathcal{I}}$ be a collection of intervention targets. Two LMGs ${\mathcal{G}}$ and ${\mathcal{H}}$ are *${\mathcal{I}}$-Markov equivalent* and belong to the same *${\mathcal{I}}$-Markov equivalence class* (${\mathcal{I}}$-MEC) if $${\mathcal{J}}({\mathcal{G}}^{\mathcal{I}}) = {\mathcal{J}}({\mathcal{H}}^{\mathcal{I}}).$$

\[rmk: graphical invariance\] It may seem counterintuitive to define a notion of interventional equivalence based solely on the graph structure and without regard to the invariance properties of the underlying distribution. However, Theorem \[thm: YKU characterization\] in fact gives a completely graph-theoretical way of viewing these invariances. Recall that the ${\mathcal{I}}$-DAG ${\mathcal{G}}^{\mathcal{I}}$ adds a new source node $\omega_I$ to ${\mathcal{G}}$ such that $\omega_I\rightarrow i$ for all $i\in I$. Theorem \[thm: YKU characterization\] states that the intervention represented by the addition of this node will not change the causal mechanisms of nodes from which the point of intervention can be $d$-separated. For example, the causal mechanism $f(x_j\mid x_{\pa_{\mathcal{G}}(j)})$ for any ancestor $j\notin I$ of a node $i\in I$ will remain unchanged by the intervention $I$, and this is captured graphically by the fact that $\omega_I$ is $d$-separated from $j$ in ${\mathcal{G}}^{\mathcal{I}}$ given only $W_{\mathcal{I}}\setminus w_I$. In Section \[sec: factorization criteria\], our choice of abstraction to this level will be further justified when we show that any two directed AGs are ${\mathcal{I}}$-Markov equivalent in terms of Definition \[def: LMG I-Markov equivalence\] if and only if they encode the same interventional settings from a standard causal perspective.

In the case of DAGs, notice that Theorem \[thm: YKU characterization\] would be trivial if we take Definition \[def: LMG I-Markov equivalence\] as the definition of ${\mathcal{I}}$-Markov equivalence instead of Definition \[def: I-Markov equivalence of DAGs\]. This is because an ${\mathcal{I}}$-DAG is again a DAG. However, as seen in Figure \[fig: intervention example\], an ${\mathcal{I}}$-LMG ${\mathcal{G}}^{\mathcal{I}}$ need not always be in the same subclass of LMGs as ${\mathcal{G}}$. This makes generalizing Theorem \[thm: YKU characterization\] with respect to Definition \[def: LMG I-Markov equivalence\] nontrivial for classes of LMGs other than DAGs. In particular, we would like to generalize Theorem \[thm: YKU characterization\] to one such family of LMGs, called ancestral graphs (AGs). Doing so will allow for modeling interventions in the same fashion as DAGs, but now in the presence of latent confounders and selection variables. A complete generalization of Theorem \[thm: YKU characterization\] to all AGs with arbitrary intervention targets is impossible (as we will see in Example \[ex: doubly intervened\]). However, it will extend to all AGs under reasonable assumptions on the intervention targets. Notice that the generalization given in Definition \[def: LMG I-Markov equivalence\] is for formal independence models, and hence any corresponding generalization of Theorem \[thm: YKU characterization\], such as the one we will prove in Theorem \[thm: main\], will be a purely mathematical result. To give such a result probabilistic meaning, it is also necessary to generalize the collection of intervention settings associated to a DAG to more general LMGs and relate such generalizations to Definition \[def: LMG I-Markov equivalence\]. This is done in Section \[sec: factorization criteria\] (specifically, Theorem \[thm: coincide\]), so as to completely generalize Theorem \[thm: YKU characterization\] to a more general family of LMGs; namely, the directed AGs.

Some subfamilies of LMGs {#subsec: ancestral and ribbonless graphs}
------------------------

We now introduce families of LMGs, and some of their properties, that will be necessary to generalize Theorem \[thm: YKU characterization\]. A *ribbon* in ${\mathcal{G}}$ is a collider path $\langle i,j,k \rangle$ such that in ${\mathcal{G}}$:

1.  There is no endpoint-identical edge between $i$ and $k$; i.e., there is no $i\leftrightarrow k$ edge in the case $i\leftrightarrow j\leftrightarrow k$, no $i\rightarrow k$ edge in the case $i\rightarrow j \leftrightarrow k$, and no $i - k$ edge in the case $i\rightarrow j \leftarrow k$, and

2.  $j$ or a descendant of $j$ is an endpoint of an undirected edge or is on a directed cycle.

A *ribbonless graph* (RG) is an LMG containing no ribbons. See Figure \[fig: intervention example\] and @S12 for examples. RGs are *probabilistic*; i.e., ${\mathcal{J}}({\mathcal{G}})$ is a probabilistic independence model. In fact, each such model can be induced by marginalizing and conditioning a DAG model @S12. A subclass of RGs admitting this property @RS02 are the ancestral graphs. An LMG ${\mathcal{G}}$ is an *ancestral graph* (AG) if:

1.  ${\mathcal{G}}$ contains no directed cycles,

2.  whenever ${\mathcal{G}}$ contains a bidirected edge $i\leftrightarrow j$, there is no directed path from $i$ to $j$ or $j$ to $i$ in ${\mathcal{G}}$, and

3.  whenever ${\mathcal{G}}$ contains an undirected edge $i-j$, neither $i$ nor $j$ has an arrowhead pointing towards it.

AGs were introduced by @RS02 as a generalization of DAG models that are closed under marginalization and conditioning. They offer a means by which to model causation in the presence of latent confounders and selection variables. The bidirected edge $i\leftrightarrow j$ can be interpreted as representing a triple $i\leftarrow k \rightarrow j$ where the node $k$ corresponds to an unobserved random variable. Similarly, the undirected edge $i - j$ can be thought of as a triple $i\rightarrow k \leftarrow j$ in which the variable corresponding to $k$ has been conditioned upon (a selection variable). We call the endpoints of an undirected edge $x - y$ *selection adjacent nodes*, and we let $\sa({\mathcal{G}})$ denote the collection of selection adjacent nodes in ${\mathcal{G}}$.

If an AG contains no undirected edges we call it a *directed AG*. Directed AGs are precisely those AGs that are also *acyclic directed mixed graphs* (ADMGs); i.e., graphs containing only directed or bidirected edges and no directed cycles. Hence, the results we derive in Section \[sec: factorization criteria\] on the invariance properties of factorization criterion for ADMGs will apply to all directed AGs. The two key differences between AGs and RGs are that RGs allow directed cycles and arrowheads pointing into selection adjacent nodes. In Figure \[fig: hierarchy\], we depict the hierarchy of the subfamilies of LMGs studied in this paper. An extensive treatment of the many well-studied subfamilies of LMGs can be found in @SL14.

\[thick,scale=0.3\]

(h1) at (0,0) <span>LMGs</span>; (h1) at (2.5,0) <span>$\subsetneq$</span>; (h2) at (5,0) <span>RGs</span>; (h1) at (7.5,0) <span>$\subsetneq$</span>; (h3) at (10,0) <span>AGs</span>; (h1) at (12.5,0) <span>$\subsetneq$</span>; (h4) at (17,0) <span>directed AGs</span>; (h5) at (10,4) <span>ADMGs</span>; (h1) at (15,4) <span>$\subsetneq$</span>; (h6) at (19,4) <span>DAGs</span>;

(h1) at (7,2) <span>$\subsetneq$</span>; (h1) at (18,2) <span>$\subsetneq$</span>;

An LMG ${\mathcal{G}}$ is called *maximal* if adding any edge to ${\mathcal{G}}$ changes the collection ${\mathcal{J}}({\mathcal{G}})$. @RS02 [Theorem 5.1] showed that every AG ${\mathcal{G}}$ is contained in a unique *maximal ancestral graph* (MAG) $\overline{{\mathcal{G}}}$, and that $\overline{{\mathcal{G}}}$ is produced from ${\mathcal{G}}$ by adding bidirected arrows between the endpoints of the *inducing paths* in ${\mathcal{G}}$ (see the appendix for a definition). A similar result holds for RGs @S12. The existence of a unique maximal extension of a given RG will play a key role in the coming section.

${\mathcal{I}}$-Markov Equivalence for Ancestral Graphs {#sec: I-Markov equivalence for MAGs}
=======================================================

With the definitions and observations of the previous section, we can now say exactly how Theorem \[thm: YKU characterization\] generalizes to AGs. To understand the context in which the desired generalization holds, consider the following example:

\[ex: doubly intervened\] Let ${\mathcal{G}}$ and ${\mathcal{H}}$ be the Markov equivalent AGs depicted in Figure \[fig: doubly intervened\]. As seen here, by taking ${\mathcal{I}}= \{\{1,4\},\{1,5\}\}$, the LMGs ${\mathcal{G}}^{\mathcal{I}}$ and ${\mathcal{H}}^{\mathcal{I}}$ have the same ${\mathcal{I}}$-v-structures. However, ${\mathcal{G}}$ and ${\mathcal{H}}$ are not ${\mathcal{I}}$-Markov equivalent. For example, $\langle\omega_{\{1,5\}}, \omega_{\{1,4\}}\mid 2\rangle\in{\mathcal{J}}({\mathcal{G}}^{\mathcal{I}})$, but $\langle\omega_{\{1,5\}}, \omega_{\{1,4\}}\mid 2\rangle\notin{\mathcal{J}}({\mathcal{H}}^{\mathcal{I}})$. The induced subgraph of ${\mathcal{G}}^{\mathcal{I}}$ on the node set $\{\omega_{\{1,4\}},\omega_{\{1,5\}},1,2\}$ is a special type of ribbon in ${\mathcal{G}}^{\mathcal{I}}$ called a *straight ribbon* @SL14. The underlying problem appears to be the "double intervention" on selection adjacent nodes, which results in a straight ribbon in the interventional graph. As we will see, assuming that we do not doubly-intervene on selection adjacent nodes is equivalent to assuming that ${\mathcal{G}}^{\mathcal{I}}$ is ribbonless. This will be a sufficient condition for generalizing Theorem \[thm: YKU characterization\] to AGs.

\[thick,scale=0.3\]

(h1) at (0,6) <span>$1$</span>; (h2) at (0,3) <span>$2$</span>; (h3) at (0,0) <span>$3$</span>; (h4) at (-2,2) <span>$4$</span>; (h5) at (2,2) <span>$5$</span>;

(hw14) at (-3,7) ; (hw15) at (3,7) ;

(g1) at (-14,6) <span>$1$</span>; (g2) at (-14,3) <span>$2$</span>; (g3) at (-14,0) <span>$3$</span>; (g4) at (-16,2) <span>$4$</span>; (g5) at (-12,2) <span>$5$</span>;

(gw14) at (-17,7) ; (gw15) at (-11,7) ;

(h1) – (h2) ; (h2) – (h3) ; (h3) – (h4) ; (h3) – (h5) ; (hw14) – (h1) ; (hw14) – (h4) ; (hw15) – (h1) ; (hw15) – (h5) ;

(g1) – (g2) ; (g2) – (g3) ; (g3) – (g4) ; (g3) – (g5) ; (gw14) – (g1) ; (gw14) – (g4) ; (gw15) – (g1) ; (gw15) – (g5) ;

at (-4.5,6.5) <span>$\omega_{\{1,4\}}$</span>; at (4.75,6.5) <span>$\omega_{\{1,5\}}$</span>; at (-18.5,6.5) <span>$\omega_{\{1,4\}}$</span>; at (-9.25,6.5) <span>$\omega_{\{1,5\}}$</span>; at (-12,-0.5) <span>${\mathcal{G}}^{\mathcal{I}}$</span>; at (2,-0.5) <span>${\mathcal{H}}^{\mathcal{I}}$</span>;

Even with the assumption mentioned in Example \[ex: doubly intervened\], we still capture useful causal models. For example, it does not rule out cases in which we can target single variables, such as when we generate interventional distributions for studying gene regulatory networks via targeted gene deletions using the CRISPR/CAS-9 system @Dixit16. It is also a trivial assumption if there are no selection variables; i.e., in the case of directed AGs.

We further note that intervention settings that doubly-intervene on nodes arise naturally in practical contexts. For instance, the intervention setting considered in @Sachs05 considers a multiset of intervention targets when learning a specific protein signaling network. Here, researchers are interested in modeling an interventional setting that includes different interventional experiments for the regulation of targeted molecules. The result is a model containing doubly-intervened nodes, as depicted in Figure \[fig: Sachs\] in the appendix. Similarly, doubly-intervened nodes such as depicted in Figure \[fig: doubly intervened\] can arise when the reagents for regulating expression target more than one molecule at a time.

\[def: doubly-intervened\] Let ${\mathcal{G}}=([p],E)$ be an LMG and ${\mathcal{I}}$ a collection of intervention targets. We say that ${\mathcal{I}}$ *doubly-intervenes* on a node $i\in[p]$ if there exist two distinct elements $I$ and $J$ in the multiset ${\mathcal{I}}$ such that $i\in I\cap J$.

Recall that AGs are a subclass of RGs. In the appendix, we show that, when intervening on an AG ${\mathcal{G}}$, the target collection ${\mathcal{I}}$ does not doubly-intervene on any selection adjacent nodes in ${\mathcal{G}}$ if and only if ${\mathcal{G}}^{\mathcal{I}}$ is ribbonless. This is because the only ribbons one can create in an AG are straight ribbons. However, ${\mathcal{G}}^{\mathcal{I}}$ may not be ribbonless if ${\mathcal{G}}$ is an RG but not an AG. For example, if for the RG ${\mathcal{G}}$ from Figure \[fig: intervention example\], we intervene at ${\mathcal{I}}= \{\{4\},\{1,4\}\}$, then ${\mathcal{G}}^{\mathcal{I}}$ is not ribbonless even though ${\mathcal{I}}$ does not doubly-intervene on any selection-adjacent nodes in ${\mathcal{G}}$. This is due to the *cyclic ribbon* $\langle \omega_{\{1,4\}},4,\omega_{\{1\}}\rangle$.

@ARS09 showed that two MAGs are Markov equivalent if and only if they have the same *colliders with order*. A collider $\langle i,j,k\rangle$ has *order $0$* if $i$ and $k$ are not adjacent. For $t\geq0$, if we let $\mathfrak{D}_t$ denote the set of all *triples of order $t$* in a given LMG ${\mathcal{G}}$, then $\langle i,j,k\rangle\in\mathfrak{D}_{t+1}$ if it is not a triple with order $s<t+1$, and there is a path $\langle v_0,v_1,\ldots,v_m,b,c\rangle$ with either $\langle i,j,k\rangle = \langle v_m,b,c\rangle$ or $\langle k,j,i\rangle = \langle v_m,b,c\rangle$ such that $$\langle v_0,v_1,v_2\rangle, \langle v_1,v_2,v_3\rangle, \ldots, \langle v_{m-1},v_m,b\rangle\in\bigcup_{s\leq t}\mathfrak{D}_s,$$ $v_0$ and $c$ are nonadjacent in ${\mathcal{G}}$, and $v_0,\ldots,v_m$ are parents of $c$. The path $\pi$ is a *discriminating path* for $j$. For example, the path $\langle \omega_{\{1\}}, 1, 2, 3\rangle$ is a discriminating path for $2$ in the right-hand graph in Figure \[fig: collider with order\].

Just as how ${\mathcal{I}}$-MECs refine an MEC of DAGs by the presence of new v-structures (i.e., the ${\mathcal{I}}$-v-structures), we will see that ${\mathcal{I}}$-MECs of MAGs are defined by the presence new colliders with order. Given an LMG ${\mathcal{G}}$, a *${\mathcal{I}}$-collider with order in ${\mathcal{G}}^{\mathcal{I}}$* is a collider with order in ${\mathcal{G}}^{\mathcal{I}}$ that is not a collider with order in ${\mathcal{G}}$. An example is given in Figure \[fig: collider with order\]. We can now state our main theorem in this section:

\[thick,scale=0.3\]

(t1) at (0,-8) <span>$1$</span>; (t2) at (3,-8) <span>$2$</span>; (t3) at (5,-5) <span>$3$</span>;

(r1) at (13,-8) <span>$1$</span>; (r2) at (16,-8) <span>$2$</span>; (r3) at (18,-5) <span>$3$</span>;

(rwIJ) at (10,-7.8) ;

(t1) – (t2) ; (t2) – (t3) ; (t1) – (t3) ;

(r1) – (r2) ; (r2) – (r3) ; (r1) – (r3) ; (rwIJ) – (r1) ;

at (9,-8.5) <span>$\omega_{\{1\}}$</span>; at (1,-5) <span>${\mathcal{G}}$</span>; at (14,-5) <span>${\mathcal{G}}^{\mathcal{I}}$</span>;

\[thm: main\] Let ${\mathcal{G}}$ and ${\mathcal{H}}$ be AGs, and let ${\mathcal{I}}$ be a collection of intervention targets such that no selection adjacent node is doubly-intervened in either ${\mathcal{G}}$ or ${\mathcal{H}}$. The following are equivalent:

1.  ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent.

2.  $\overline{{\mathcal{G}}}$ and $\overline{{\mathcal{H}}}$ are ${\mathcal{I}}$-Markov equivalent.

3.  $\overline{{\mathcal{G}}}$ and $\overline{{\mathcal{H}}}$ are Markov equivalent and $\overline{{\mathcal{G}}}^{\mathcal{I}}$ and $\overline{{\mathcal{H}}}^{\mathcal{I}}$ have the same ${\mathcal{I}}$-colliders with order.

Condition 3 in Theorem \[thm: main\] is actually a graphical characterization of ${\mathcal{I}}$-Markov equivalence. This is because there already exist graphical characterizations of Markov equivalence of MAGs, such as @ARS09 [Theorem 3.2] or @ZZL05 [Theorem 2.1]. Thus, even though $\overline{{\mathcal{G}}}^{\mathcal{I}}$ and $\overline{{\mathcal{H}}}^{\mathcal{I}}$ are not necessarily AGs, by condition 3 we can still apply these graphical characterizations and the condition on the ${\mathcal{I}}$-colliders with order in $\overline{{\mathcal{G}}}^{\mathcal{I}}$ and $\overline{{\mathcal{H}}}^{\mathcal{I}}$ to get graphical characterizations of ${\mathcal{I}}$-Markov equivalence for the AGs ${\mathcal{G}}$ and ${\mathcal{H}}$. For example, the two AGs ${\mathcal{G}}$ and ${\mathcal{H}}$ in Figure \[fig: doubly intervened\] are Markov equivalent with the same ${\mathcal{I}}$-colliders with order when we take ${\mathcal{I}}= \{\{1,4\}\}$ even though the left-hand graph ${\mathcal{G}}$ is such that ${\mathcal{G}}^{\mathcal{I}}$ is not ancestral. On the other hand, in the special case of Theorem \[thm: main\] in which no selection adjacent nodes are intervened upon in either ${\mathcal{G}}^{\mathcal{I}}$ or ${\mathcal{H}}^{\mathcal{I}}$, condition 3 is equivalent to saying that ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent if and only if $\overline{{\mathcal{G}}}^{\mathcal{I}}$ and $\overline{{\mathcal{H}}}^{\mathcal{I}}$ are Markov equivalent MAGs, which can be deduced by the graphical characterizations of @ARS09 [Theorem 3.2] or @ZZL05 [Theorem 2.1].

For directed AGs, we note that Theorem \[thm: main\] places no restrictions on the intervention targets ${\mathcal{I}}$. In the coming section, we will see that directed AGs, and more generally ADMGs, admit a generalization of the interventional settings ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ via a known factorization criterion for such models. This allows us to give probabilistic meaning to Theorem \[thm: main\]. Using this, we will recover a complete generalization of Theorem \[thm: YKU characterization\] to directed AGs.

Finally, we note that Theorem \[thm: main\] can be used to describe ${\mathcal{I}}$-MECs for families of AGs in a number of contexts arising in practice: For instance, it applies when practitioners are able to design interventional experiments where each intervention target is a singleton. This case arises in genetics, where one can perform targeted gene deletions @Dixit16. On the other hand, Theorem \[thm: main\] is also applicable when practitioners are not able to place such restrictions on their intervention targets but are willing to model without the incorporation of selection variables.

Factorization Criteria and ${\mathcal{I}}$-ADMGs {#sec: factorization criteria}
================================================

We have now generalized a characterization of ${\mathcal{I}}$-Markov equivalence for DAGs to AGs from the perspective of formal independence models as specified by Definition \[def: LMG I-Markov equivalence\]. However, it is typical to think of interventions as modifications to conditional factors of the density (i.e., modifications to causal mechanisms), and the formal independence model perspective obscures this. In Definition \[def: I-Markov equivalence of DAGs\], ${\mathcal{I}}$-Markov equivalence for DAGs is defined in terms of modified densities, which is fundamentally different than the perspective taken in Definition \[def: LMG I-Markov equivalence\]. The choice to use Definition \[def: LMG I-Markov equivalence\] can be made when there is no known factorization criterion for the graphical model that allows one to encode interventions via distributional invariances. However, since distributional invariance is how we statistically measure the effects of intervention, it is important that we check that Definition \[def: LMG I-Markov equivalence\] coincides with such distributional invariances when a factorization criterion for the model is known. The most general family of LMGs for which we have a conditional factorization criterion is the family of ADMGs introduced in Subsection \[subsec: ancestral and ribbonless graphs\], which contains all directed AGs. In this section, we extend the definition of the interventional settings ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ to ADMGs via their factorization criteria, and we characterize when two ADMGs ${\mathcal{G}}$ and ${\mathcal{H}}$ satisfy ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$. As a corollary, we will prove that for directed AGs, such an equality holds if and only if the two graphs satisfy the conditions in Theorem \[thm: main\] imposed by our definition of ${\mathcal{I}}$-Markov equivalence for formal independence models.

For an ADMG ${\mathcal{G}}= ([p],E)$, we let $
{\mathcal{A}}({\mathcal{G}}) :=\{ A \mid A = \an_{\mathcal{G}}(A)\},
$ be the collection of all *ancestrally closed sets* in ${\mathcal{G}}$. The *induced bidirected graph* ${\mathcal{G}}_{\leftrightarrow}$ is the graph formed by removing all edges from ${\mathcal{G}}$ that are not bidirected. Its path-connected components are called *districts* (or *$c$-components* @TP02). We denote the collection of all districts in ${\mathcal{G}}$ by $\dis({\mathcal{G}})$, and we let $\dis_{\mathcal{G}}(i)$ denote the district of ${\mathcal{G}}$ containing the vertex $i\in[p]$. If $A\subset[p]$, we also let $\dis(A):=\dis({\mathcal{G}}\langle A\rangle)$ and $\dis_A(i) :=\dis_{{\mathcal{G}}_A}(i)$. For $A\subset[p]$, let $$\barren_{\mathcal{G}}(A) :=\{x\in A \mid \de_{\mathcal{G}}(x)\cap A = \{x\}\}.$$ We can then define the following functions on $A\subset[p]$: First set $\Phi_{\mathcal{G}}(\emptyset):=\emptyset$ and $\Psi_{\mathcal{G}}^0(A):=A$. Then set $$\begin{split}
\Phi_{\mathcal{G}}(A)&:=\{H \mid H=\cap_{i\in H}\barren_{\mathcal{G}}(\an_{\mathcal{G}}(\dis_A(i))) \mbox{ and } H\neq\emptyset\}, \mbox{ and}\\
\Psi_{\mathcal{G}}(A)&:=A\setminus\bigcup_{H\in\Phi_{\mathcal{G}}(A)}H.\\
\end{split}$$ Applying the function $\Psi_{\mathcal{G}}$ repeatedly produces a partition of $A$ into a collection of *heads* denoted $$[A]_{\mathcal{G}}:=\bigcup_{k\geq 0}\Phi_{\mathcal{G}}(\Psi_{\mathcal{G}}^k(A)).$$ Each head $H\in[A]_{\mathcal{G}}$ is a path-connected subgraph of ${\mathcal{G}}_{\leftrightarrow}$, and it satisfies $H = \barren_{\mathcal{G}}(\an_{\mathcal{G}}(H))$. For $H\in[A]_{\mathcal{G}}$, we define the associated *tail* $$\tail(H) := (\dis_{\an(H)}(H)\setminus H)\cup\pa_{\mathcal{G}}(\dis_{\an(H)}(H)).$$ @R09 derived the following factorization criterion for ADMGs:

@R09 [Theorem 4] \[thm: richardson factorization\] A probability distribution $\mathbb{P}$ with density function $f$ is Markov to an ADMG ${\mathcal{G}}$ if and only if for every $A\in{\mathcal{A}}({\mathcal{G}})$, the marginal density $f(x_A)$ factors as $$\label{eqn: ADMG factorization}
f(x_A) = \prod_{H\in[A]_{\mathcal{G}}}f(x_H \mid x_{\tail(H)}).$$

Using Theorem \[thm: richardson factorization\], we can extend the notion of an interventional distribution captured in equation <span> </span> to ADMGs:

\[def: ADMG interventional density\] A distribution with density function $f^{(I)}$ is called an *interventional distribution* with respect to the intervention target $I$ and ADMG ${\mathcal{G}}$ if for all $A\in{\mathcal{A}}({\mathcal{G}})$ $$\label{eqn: ADMG interventional factorization}
\begin{split}
f(x_A) &= \prod_{H\in[A]_{\mathcal{G}}: I\cap H \neq \emptyset}f^{(I)}(x_H \mid x_{\tail(H)})\prod_{H\in[A]_{\mathcal{G}}: I\cap H = \emptyset}f^{(\emptyset)}(x_H \mid x_{\tail(H)}),
\end{split}$$ where $f^{(\emptyset)}$ is the density of a distribution Markov to ${\mathcal{G}}$.

The collection of sequences of interventional distributions $(f^{(I)})_{I\in{\mathcal{I}}}$ that can be generated by intervening on a collection of targets ${\mathcal{I}}$ with respect to an observational density Markov to an ADMG ${\mathcal{G}}$ is then $$\label{eqn: ADMG interventional density sets}
\begin{split}
{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) := \{&(f^{(I)})_{I\in{\mathcal{I}}} \mid \mbox{$\forall I,J\in{\mathcal{I}}$ } \mbox{ and $A\in{\mathcal{A}}({\mathcal{G}})$: $f^{(I)}\in{\mathcal{M}}({\mathcal{G}})$ and } \\
    & f^{(I)}(x_H\mid x_{\tail(H)}) = f^{(J)}(x_H\mid x_{\tail(H)}) \mbox{ $\forall H\in[A]_{\mathcal{G}}$: $H\cap(I\cup J) = \emptyset$}\}.
\end{split}$$ A proof of this fact is given in the appendix.

\[rmk: causal connection\] In Theorem \[thm: causal alignment\], we will show that our definition for general interventions with respect to an ADMG (Definition \[def: ADMG interventional density\]) and our corresponding generalization of the collection ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ to ADMGs capture the intuitive notion of intervention given by interpreting a distribution Markov to an ADMG as the marginal over the observed variables in a distribution Markov to a causal DAG. To prove Theorem \[thm: causal alignment\], we will first characterize when ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$ for two ADMGs ${\mathcal{G}}$ and ${\mathcal{H}}$.

Definition \[def: ADMG interventional density\] and <span> </span> are the natural extensions of equations <span> </span> and <span> </span> to the family of ADMGs. With these definitions, we can generalize the *${\mathcal{I}}$-Markov property for DAGs* introduced in @YKU18 [Definition 3.6] by simply passing from $d$-separation to $m$-separation:

\[${\mathcal{I}}$-Markov Property\] \[def: ADMG local I-Markov properties\] Let ${\mathcal{I}}$ be a collection of intervention targets such that $\emptyset\in{\mathcal{I}}$ and $(f^{(I)})_{I\in{\mathcal{I}}}$ a set of strictly positive distributions over $X_1,\ldots,X_p$. For an ADMG ${\mathcal{G}}= ([p], E)$, we say that $(f^{(I)})_{I\in{\mathcal{I}}}$ satisfies the *${\mathcal{I}}$-Markov property* with respect to ${\mathcal{G}}^{\mathcal{I}}$ if and only if

1.  $X_A {\protect\mathpalette{\protect\independenT}{\perp}}X_B \mid X_C$ in $f^{(I)}$ for all $I\in{\mathcal{I}}$ and any $A,B,C\subset[p]$ for which $\langle A,B \mid C\rangle \in {\mathcal{J}}({\mathcal{G}})$.

2.  $f^{(\emptyset)}(X_B\mid X_C) = f^{(I)}(X_B\mid X_C)$ for any $I\in{\mathcal{I}}$ and $B,C\subset[p]$ such that\
    $\langle B,\{\omega_I\} \mid C\cup W_{\mathcal{I}}\setminus\{\omega_I\}\rangle\in{\mathcal{J}}({\mathcal{G}}^{\mathcal{I}})$.

\[rmk: causal I-Markov property\] @KJSB19 [Definition 1] recently introduced an alternative ${\mathcal{I}}$-Markov property that is more restrictive than Definition \[def: ADMG local I-Markov properties\]. The original definition of @YKU18, and Definition \[def: ADMG local I-Markov properties\], are designed to characterize exactly the invariances between observational and interventional distributions detectable in their factorizations, whereas the definition of @KJSB19 is motivated by a generalization of Pearl's do-calculus to soft interventions @CB19. Consequently, their ${\mathcal{I}}$-Markov property, which we will call the *controlled ${\mathcal{I}}$-Markov property*, is tied to additional invariances which are exhibited when the interventions are *controlled*; meaning that if $I,J\in{\mathcal{I}}$ both target the node $j$, then they change the causal mechanism associated to $j$ in the exact same way. That is, $f^{(I)}(X_j\mid X_{\pa_{\mathcal{G}}{(j)}}) = f^{(J)}(X_j\mid X_{\pa_{\mathcal{G}}{(j)}})$. It follows that the controlled ${\mathcal{I}}$-Markov property imposes more invariances than the ${\mathcal{I}}$-Markov property. In Section \[app: comparing\], we show for any ADMG ${\mathcal{G}}$ and collection of intervention targets ${\mathcal{I}}$, the collection of interventional settings satisfying the controlled ${\mathcal{I}}$-Markov property with respect to ${\mathcal{G}}$ is a (generally strict) subset of those satisfying the ${\mathcal{I}}$-Markov property. Even for DAGs, this inclusion is often strict. The assumption that all interventions are controlled can be restrictive in, for example, biological contexts when using different reagents to regulate protein expression: Two reagents may target the same molecule but regulate its expression in very different ways. The theory we provide here does not assume interventions are controlled and, hence, is applicable to these more general contexts.

@YKU18 [Proposition 3.8] showed that for a DAG ${\mathcal{G}}$, if $\emptyset\in{\mathcal{I}}$, then $(f^{(I)})_{I\in{\mathcal{I}}}$ is in ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ if and only if $(f^{(I)})_{I\in{\mathcal{I}}}$ satisfies the ${\mathcal{I}}$-Markov property with respect to ${\mathcal{G}}^{\mathcal{I}}$. The following theorem generalizes this result to all ADMGs, and hence characterizes interventional model equivalence for ADMGs from the perspective of distributional invariances in their associated factorization criteria.

\[thm: local I-Markov equivalence characterization\] Suppose $\emptyset\in{\mathcal{I}}$ and ${\mathcal{G}}$ is an ADMG. Then $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ if and only if $(f^{(I)})_{I\in{\mathcal{I}}}$ satisfies the ${\mathcal{I}}$-Markov property with respect to ${\mathcal{G}}^{\mathcal{I}}$.

Interventions in ADMGs causally {#subsec: causal perspective}
-------------------------------

Since ADMGs can be used to represent causal DAGs with latent confounders, we would like to see that our definition of interventional setting given in <span> </span> captures the intuitive of notion interventional setting arising from this perspective. To formalize this, we first recall the connection between causal DAGs with latent confounders and ADMGs.

\[def: latent projection\] Let ${\mathcal{G}}$ be a DAG with vertex set $[p]\sqcup L$, where the vertices in $[p]$ are observed and those in $L$ are latent, and $\sqcup$ denotes a disjoint union. The *latent projection* ${\mathcal{G}}([p])$ is a mixed graph with vertex set $[p]$ such that for every pair of distinct vertices $i,j\in[p]$

1.  ${\mathcal{G}}([p])$ contains an edge $i\rightarrow j$ if there exists a directed path in ${\mathcal{G}}$ $i\rightarrow\cdots\rightarrow j$ on which every non-endpoint vertex is in $L$, and

2.  ${\mathcal{G}}([p])$ contains an edge $i\leftrightarrow j$ if there exists a path in ${\mathcal{G}}$ between $i$ and $j$ such that the endpoints are all non-colliders in $L$ and such that the edge adjacent to $i$ and the edge adjacent to $j$ both have arrowheads pointing towards $i$ and $j$, respectively.

Since ${\mathcal{G}}= ([p]\sqcup L,E)$ is a DAG, we see that ${\mathcal{G}}([p])$ is an ADMG. In the following, given $f\in{\mathcal{M}}({\mathcal{G}})$, we let $\tilde{f}:=\int_LfdL$ denote the marginal density of $f$ over $[p]$. It is well-known that $\tilde{f}$ is Markov to ${\mathcal{G}}([p])$ (see for instance @RS02 [Theorem 7.1]).

Given an ADMG ${\mathcal{H}}= ([p],E)$ we can always produce a DAG ${\mathcal{G}}= ([p]\sqcup L,E^\prime)$ such that ${\mathcal{H}}= {\mathcal{G}}([p])$ by replacing each bidirected arrow $i\leftrightarrow j$ in ${\mathcal{H}}$ with $i\leftarrow \ell_{i,j}\rightarrow j$ and letting $L :=\{\ell_{i,j}: i\leftrightarrow j \text{ an edge in } {\mathcal{H}}\}$. Thus, given a DAG $G = ([p]\sqcup L,E)$ and an interventional setting $(f^{(I)})_{I\in{\mathcal{I}}}\in {\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ for ${\mathcal{I}}= \{\emptyset,I_1,\ldots,I_K\}$ with $I_k\in[p]$ for all $k\in[K]$ we would like to see that $(\tilde{f}^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}([p]))$. This would imply that the invariance properties used to define interventional densities and interventional settings for ADMGs in Definition \[def: ADMG interventional density\] and <span> </span> align with the standard notion given by Definition \[eqn: interventional distribution\] and the causal interpretation of ADMGs as latent projections of causal DAGs. To prove this, we use the fact that $d$-separation statements on the observed variables in the DAG ${\mathcal{G}}= ([p]\sqcup L,E)$ are in one-to-one correspondence with the $m$-separation statements in the latent projection ${\mathcal{G}}([p])$. A proof of this fact appears first in @V93 and later on in @RERS17 [Proposition 4]. Combining this fact with our Theorem \[thm: local I-Markov equivalence characterization\], we can prove that our definition of interventional setting for ADMGs aligns with the causally intuitive notion.

\[thm: causal alignment\] Let ${\mathcal{G}}= ([p]\sqcup L,E)$ be a DAG, where $[p]\sqcup L$ is a disjoint union. Let ${\mathcal{I}}$ be a collection of intervention targets satisfying $\emptyset\in{\mathcal{I}}$ and $I\subset [p]$ for all $I\in{\mathcal{I}}$. If $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ then $(\tilde{f}^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}([p]))$.

Directed ancestral graphs {#subsec: directed AGs}
-------------------------

Our last goal is to connect the interventional settings for ADMGs with the combinatorial characterization of ${\mathcal{I}}$-Markov equivalence for formal independence models given in Theorem \[thm: main\]. Theorem \[thm: local I-Markov equivalence characterization\] says two ADMGs ${\mathcal{G}}$ and ${\mathcal{H}}$ satisfy ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$ if and only if they have the same ${\mathcal{I}}$-Markov properties. Theorem \[thm: main\] characterizes ${\mathcal{I}}$-MECs of AGs via global Markov properties. Our last theorem says these two generalizations coincide for LMGs that are both AGs and ADMGs; i.e., for directed AGs. This unifies all of our previous results, and it completely generalizes Theorem \[thm: YKU characterization\] to a context in which we can incorporate latent confounders without assuming controlled interventions.

\[thm: coincide\] Let ${\mathcal{G}}$ and ${\mathcal{H}}$ be two directed AGs and let ${\mathcal{I}}$ be a collection of intervention targets. Suppose $\emptyset\in{\mathcal{I}}$. Then the following are equivalent:

1.  ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent,

2.  $\overline{{\mathcal{G}}}$ and $\overline{{\mathcal{H}}}$ are ${\mathcal{I}}$-Markov equivalent,

3.  ${\mathcal{G}}$ and ${\mathcal{H}}$ are Markov equivalent and $\overline{{\mathcal{G}}}^{\mathcal{I}}$ and $\overline{{\mathcal{H}}}^{\mathcal{I}}$ have the same ${\mathcal{I}}$-colliders with order, and

4.  ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$.

\[rmk: refined\] @KJSB19 defined a notion of ${\mathcal{I}}$-Markov equivalence by saying that two ADMGs, ${\mathcal{G}}$ and ${\mathcal{H}}$, are ${\mathcal{I}}$-Markov equivalent if and only if the set of distributions satisfying the controlled ${\mathcal{I}}$-Markov property with respect to ${\mathcal{G}}$ and ${\mathcal{I}}$ and ${\mathcal{H}}$ and ${\mathcal{I}}$ are the same. Under the assumption of controlled interventions, they characterized this phenomenon in a similar fashion as to our Theorem \[thm: coincide\]. Since, as noted in Remark \[rmk: causal I-Markov property\], the assumption of controlled interventions requires that (in general strictly) more invariances hold among the distributions in an interventional setting satisfying the controlled ${\mathcal{I}}$-Markov property, the ${\mathcal{I}}$-Markov equivalence classes studied by @KJSB19 should refine the ${\mathcal{I}}$-Markov equivalence classes identified by Theorem \[thm: coincide\]. In Section \[app: comparing\], we show that this is indeed the case, and we give a graphical characterization of how this refinement occurs. While finer ${\mathcal{I}}$-Markov equivalence classes is of course desirable from a causal learning perspective, if the controlled assumption is too restrictive for the application at hand, one can now use the slightly larger ${\mathcal{I}}$-MECs characterized by Theorem \[thm: coincide\].

Theorem \[thm: coincide\] also shows that ${\mathcal{I}}$-Markov equivalence of directed AGs corresponds to invariance properties with respect to the factorization criterion in Theorem \[thm: richardson factorization\]. Therefore, these invariance properties of factorization criteria also hold for the interventional settings studied by @KJSB19. In this way, Theorem \[thm: coincide\] yields a complete theory of general interventions in directed AG models; i.e., a theory in which intervention is understood both from the perspective of Markov properties and in terms of distributional invariances with respect to the model factorization criterion. However, the specific invariances arising from the controlled assumption are not immediately visible in this factorization criterion. It would be interesting to know if controlled interventional settings admit an even more refined factorization criterion that exhibits all of their invariance properties.

It is also interesting to note that Theorem \[thm: coincide\] yields a different characterization of ${\mathcal{I}}$-Markov equivalence given any characterization of Markov equivalence of AGs. Currently, there are three known characterizations of Markov equivalence for AGs: one due to @ARS09, another due to @ZZL05, and a third by @SR97. Applying Theorem \[thm: coincide\] to the first, we see that ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$ if and only if $\overline{{\mathcal{G}}}^{\mathcal{I}}$ and $\overline{{\mathcal{H}}}^{\mathcal{I}}$ have the same adjacencies and colliders with order. Applying the second one, Theorem \[thm: coincide\] implies that ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$ if and only if $\overline{{\mathcal{G}}}^{\mathcal{I}}$ and $\overline{{\mathcal{H}}}^{\mathcal{I}}$ have the same ${\mathcal{I}}$-colliders with order and the same minimal collider paths. Applying the third recovers yet another characterization.

Comparing Alternative ${\mathcal{I}}$-Markov Properties {#app: comparing}
=======================================================

@KJSB19 recently investigated characterizations of ${\mathcal{I}}$-Markov equivalence under general interventions as well. To do so, they introduced a slightly different ${\mathcal{I}}$-Markov property than that of @YKU18 [Definition 3.6] or our generalization thereof (Definition \[def: ADMG local I-Markov properties\]). Instead, their ${\mathcal{I}}$-Markov property, which we will refer to as the *controlled ${\mathcal{I}}$-Markov property* is the following:

@KJSB19 [Definition 1] \[def: causal I-Markov property\] Let ${\mathcal{I}}$ be a collection of intervention targets and $(f^{(I)})_{I\in{\mathcal{I}}}$ a set of strictly positive distributions over $X_1,\ldots,X_p$. We say that $(f^{(I)})_{I\in{\mathcal{I}}}$ satisfies the *controlled ${\mathcal{I}}$-Markov property* with respect to an ADMG ${\mathcal{G}}= ([p],E)$ if and only if

1.  $X_A {\protect\mathpalette{\protect\independenT}{\perp}}X_B \mid X_C$ in $f^{(I)}$ for all $I\in{\mathcal{I}}$ and any $A,B,C\subset[p]$ for which $\langle A,B \mid C\rangle \in {\mathcal{J}}({\mathcal{G}})$, and

2.  $f^{(I)}(X_B\mid X_C) = f^{(J)}(X_B\mid X_C)$ for any two $I,J\in{\mathcal{I}}$ and $B,C\subset[p]$ such that $$\langle B,\{\omega_{I\triangle J} \mid C\cup W_{{\mathcal{I}}\triangle{\mathcal{I}}}\setminus\{\omega_{I\triangle J}\}\rangle\in{\mathcal{J}}({\mathcal{G}}^{{\mathcal{I}}\triangle{\mathcal{I}}}),$$ where ${\mathcal{I}}\triangle{\mathcal{I}}:=\{ I\triangle J : I,J\in{\mathcal{I}}\}$ is the set of all symmetric differences of the sets in ${\mathcal{I}}$.

We refer to Definition \[def: causal I-Markov property\] as the controlled ${\mathcal{I}}$-Markov property since it is motivated by a recent generalization of Pearl's do-calculus to the case of soft interventions @CB19. @KJSB19 [Corollary $1$] showed that property (2) of the controlled ${\mathcal{I}}$-Markov property is a combined version of the 'do-do' and 'do-see' rules from this generalized do-calculus whenever the interventions ${\mathcal{I}}$ are assumed to be controlled. In this way, the controlled ${\mathcal{I}}$-Markov property is a more restrictive version of the ${\mathcal{I}}$-Markov property presented in Definition \[def: ADMG local I-Markov properties\] since it is inherently tied to the assumption that the interventions are controlled. We note also that the phrasing of Definition \[def: causal I-Markov property\] is not the same as that of @KJSB19 [Definition $1$], but instead uses the language and notation developed in this paper. However, the equivalence of these two definitions follows immediately from @KJSB19 [Proposition $1$].

Let ${\mathcal{M}}_{\mathcal{I}}^{(c)}({\mathcal{G}})$ denote the set of all $(f^{(I)})_{I\in{\mathcal{I}}}$ satisfying the controlled ${\mathcal{I}}$-Markov property with respect to ${\mathcal{G}}$. @KJSB19 defined two graphs ${\mathcal{G}}$ and ${\mathcal{H}}$ to be ${\mathcal{I}}$-Markov equivalent whenever ${\mathcal{M}}_{\mathcal{I}}^{(c)}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}^{(c)}({\mathcal{H}})$. We will refer to this as *controlled ${\mathcal{I}}$-Markov equivalence*. The two differences between the ${\mathcal{I}}$-Markov property defined in @YKU18 [Definition 3.6] and Definition \[def: ADMG local I-Markov properties\] and the controlled ${\mathcal{I}}$-Markov property is the choice for property (2) and the fact that the controlled ${\mathcal{I}}$-Markov property does not assume $\emptyset\in{\mathcal{I}}$. As is seen in @YKU18, the assumption that $\emptyset\in{\mathcal{I}}$ can be readily dropped by treating a fixed interventional distribution as the observational distribution. So we can then assume (without loss of generality) that $\emptyset\in{\mathcal{I}}$. Then the only difference between the ${\mathcal{I}}$-Markov property studied here and the controlled ${\mathcal{I}}$-Markov property is the choice of property (2).

Property (2) of the ${\mathcal{I}}$-Markov property, as originally introduced in @YKU18 [Definition 3.6], was defined to characterize the invariances in the interventional distribution $$f^{(I)}(x) = \prod_{i\in I}f^{(I)}(x_i \mid x_{\pa_{\mathcal{G}}(i)})\prod_{i\in[p]\setminus I}f^{(\emptyset)}(x_i \mid x_{\pa_{\mathcal{G}}(i)})$$ relative to a given observational distribution $$f^{(\emptyset)}(x) = \prod_{i\in[p]}f^{(\emptyset)}(x_i \mid x_{\pa_{\mathcal{G}}(i)})$$ that is Markov to a DAG ${\mathcal{G}}= ([p],E)$. Namely, property (2) of the ${\mathcal{I}}$-Markov property characterizes the invariances $f^{(I)}(x_j \mid x_{\pa_{\mathcal{G}}(j)}) = f^{(J)}(x_j \mid x_{\pa_{\mathcal{G}}(j)})$ in the causal mechanisms that arise whenever $j\notin I\cup J$ for two interventions $I,J\in{\mathcal{I}}$. The ${\mathcal{I}}$-Markov property that we define in Defintion \[def: ADMG local I-Markov properties\] directly generalizes this, and in doing so, property (2) of Definition \[def: ADMG local I-Markov properties\] captures all invariances in the causal mechanisms identified by the factorization criterion of Theorem \[thm: richardson factorization\]; that is to say, $f^{(I)}(x_H \mid x_{\tail(H)}) = f^{(J)}(x_H \mid x_{\tail(H)})$ whenever $H\cap(I\cup J) = \emptyset$.

On the other hand, the controlled ${\mathcal{I}}$-Markov property was developed to capture the invariances in a recently introduced do-calculus for soft interventions @CB19. As noted in @KJSB19 [Corollary 1], property (2) of their controlled ${\mathcal{I}}$-Markov property corresponds to invariances that are guaranteed by the rules of this do-calculus for soft interventions when we assume that all interventions are controlled (as defined in Remark \[rmk: causal I-Markov property\]). The assumption that all interventions are controlled can be restrictive in, for example, biological contexts as described in Remark \[rmk: causal I-Markov property\]. Consequently, the controlled ${\mathcal{I}}$-Markov property is satisfied only by interventional settings $(f^{(I)})_{I\in{\mathcal{I}}}$ that satisfy (generally) more invariances than the invariances characterized by property (2) of the ${\mathcal{I}}$-Markov property studied in this paper. Since the ${\mathcal{I}}$-Markov property studied here and in @YKU18 is not tied to controlled interventions, the characterizations of ${\mathcal{I}}$-Markov equivalence given in Theorem \[thm: coincide\] apply to strictly more interventional settings than those captured by the controlled ${\mathcal{I}}$-Markov property. We summarize these observations with the following proposition. To help emphasize these differences between these two ${\mathcal{I}}$-Markov properties, we include the proof here, along with an illustrative example in Figure \[fig: minimal example\].

\[prop: comparing properties\] Let ${\mathcal{I}}$ be a collection of intervention targets and $\emptyset\in{\mathcal{I}}$. For an ADMG ${\mathcal{G}}= ([p],E)$, the ${\mathcal{I}}$-Markov property is weaker than the controlled ${\mathcal{I}}$-Markov property; that is, $${\mathcal{M}}_{\mathcal{I}}^{(c)}({\mathcal{G}}) \subset {\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}).$$ Moreover, there exists DAGs ${\mathcal{G}}$ and collections of intervention targets ${\mathcal{I}}$ for which $${\mathcal{M}}_{\mathcal{I}}^{(c)}({\mathcal{G}}) \subsetneq {\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}).$$

It is straightforward to see the containment ${\mathcal{M}}_{\mathcal{I}}^{(c)}({\mathcal{G}}) \subset {\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ by taking ${\mathcal{J}}= \emptyset$ in property (2) of Definition \[def: causal I-Markov property\]. As for seeing that there exist cases of strict containment, pick $i,j\in[p]$ and a DAG ${\mathcal{G}}= ([p],E)$ for which $i$ and $j$ are not adjacent in ${\mathcal{G}}$, $\pa_{\mathcal{G}}(i) = \pa_{\mathcal{G}}(j)$, and $\an_{\mathcal{G}}(i)\neq \pa_{\mathcal{G}}(i)$. Consider then the intervention targets $${\mathcal{I}}= \{
\emptyset, 
I := \pa_{\mathcal{G}}(i)\cup\{i\}, 
J := \pa_{\mathcal{G}}(j)\cup\{j\}
\}.$$ Then $${\mathcal{I}}\triangle{\mathcal{I}}= \{
\emptyset, 
I, 
J,
I\triangle J = \{i,j\}
\}.$$ A minimal example of such a DAG ${\mathcal{G}}$ and the set ${\mathcal{I}}$ is given in Figure \[fig: minimal example\].

Now let $v\in\an_{\mathcal{G}}(i)\setminus\pa_{\mathcal{G}}(i)$. Since $\pa_{\mathcal{G}}(i)$ is the Markov blanket of $\omega_{I\triangle J}$ in ${\mathcal{G}}^{{\mathcal{I}}\triangle{\mathcal{I}}}$, then $\langle v,\omega_{I\triangle J} \mid \pa_{\mathcal{G}}(i) \rangle \in{\mathcal{J}}({\mathcal{G}}^{{\mathcal{I}}\triangle{\mathcal{I}}})$. On the other hand, $\langle v,\omega_{I} \mid \pa_{\mathcal{G}}(i) \rangle, \langle v,\omega_{J} \mid \pa_{\mathcal{G}}(i) \rangle\notin{\mathcal{J}}({\mathcal{G}}^{{\mathcal{I}}})$. This is because $v$ is ancestor of both $i$ and $j$, and so conditioning on $\pa_{\mathcal{G}}(i) = \pa_{\mathcal{G}}(j)$ induces $d$-connecting paths between $v$ and $\omega_I$ and $v$ and $\omega_J$ in ${\mathcal{G}}^{\mathcal{I}}$ (and ${\mathcal{G}}^{{\mathcal{I}}\triangle{\mathcal{I}}}$, in fact). By applying the constructions in the proof of @KJSB19 [Lemma 4] to these $d$-connecting paths we can produce an interventional setting $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ such that $$\begin{split}
f^{(\emptyset)}(X_v \mid X_{\pa_{\mathcal{G}}(i)}) &\neq f^{(I)}(X_v \mid X_{\pa_{\mathcal{G}}(i)}),\\
f^{(\emptyset)}(X_v \mid X_{\pa_{\mathcal{G}}(i)}) &\neq f^{(J)}(X_v \mid X_{\pa_{\mathcal{G}}(i)}). \\
\end{split}$$ Moreover, by appropriately choosing the error terms as described in the proof of @KJSB19 [Lemma 4], we can ensure $$f^{(I)}(X_v \mid X_{\pa_{\mathcal{G}}(i)}) \neq f^{(I)}(X_v \mid X_{\pa_{\mathcal{G}}(i)}). \mbox{\,\,\,\,\,\,\,\,\, \,\,}$$ Hence, $(f^{(I)})_{I\in{\mathcal{I}}}\notin{\mathcal{M}}_{\mathcal{I}}^{(c)}({\mathcal{G}})$, and we conclude that ${\mathcal{M}}_{\mathcal{I}}^{(c)}({\mathcal{G}})\subsetneq{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$.

\[thick,scale=0.3\]

(h1) at (0,6) <span>$1$</span>; (h2) at (0,3) <span>$2$</span>; (h3) at (-2,0) <span>$3$</span>; (h4) at (2,0) <span>$4$</span>;

(hw14) at (-3,4) ; (hw15) at (3,4) ;

(g1) at (15,6) <span>$1$</span>; (g2) at (15,3) <span>$2$</span>; (g3) at (13,0) <span>$3$</span>; (g4) at (17,0) <span>$4$</span>;

(gw14) at (12,4) ; (gw15) at (18,4) ; (gw145) at (15,-3) ;

(h1) – (h2) ; (h2) – (h3) ; (h2) – (h4) ; (hw14) – (h2) ; (hw14) – (h3) ; (hw15) – (h2) ; (hw15) – (h4) ;

(g1) – (g2) ; (g2) – (g3) ; (g2) – (g4) ; (gw14) – (g2) ; (gw14) – (g3) ; (gw15) – (g2) ; (gw15) – (g4) ; (gw145) – (g3) ; (gw145) – (g4) ;

at (-3.75,4.5) <span>$\omega_{I}$</span>; at (3.75,4.5) <span>$\omega_{J}$</span>; at (11.25,4.5) <span>$\omega_{I}$</span>; at (18.75,4.5) <span>$\omega_{J}$</span>; at (16.75,-3.5) <span>$\omega_{I\triangle J}$</span>; at (-3,-3.5) <span>${\mathcal{G}}^{\mathcal{I}}$</span>; at (11,-3.5) <span>${\mathcal{G}}^{{\mathcal{I}}\triangle{\mathcal{I}}}$</span>;

It is well-known that given an ADMG ${\mathcal{G}}= ([p],E)$, a directed MAG $M_{\mathcal{G}}= ([p],E)$ can be constructed that maintains the independence and ancestral relations amongst the variables $[p]$. In other words, one can choose a representative of the Markov equivalence class of ${\mathcal{G}}$ that is a MAG with the same ancestral relations as ${\mathcal{G}}$. @KJSB19 [Theorem 2] gives a characterization of when two directed MAGs representing a causal graph are ${\mathcal{I}}$-Markov equivalent (with respect to the controlled ${\mathcal{I}}$-Markov property) under the assumption that the collection of interventions are controlled:

@KJSB19 [Theorem 2] \[thm: kocaoglu characterization\] Two ADMGs ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent for a set of controlled interventions ${\mathcal{I}}$ if and only if for the directed MAGs $M_{\mathcal{G}}^{{\mathcal{I}}\triangle{\mathcal{I}}}$ and $M_{\mathcal{H}}^{{\mathcal{I}}\triangle{\mathcal{I}}}$:

1.  $M_{\mathcal{G}}^{{\mathcal{I}}\triangle{\mathcal{I}}}$ and $M_{\mathcal{H}}^{{\mathcal{I}}\triangle{\mathcal{I}}}$ have the same skeleton,

2.  $M_{\mathcal{G}}^{{\mathcal{I}}\triangle{\mathcal{I}}}$ and $M_{\mathcal{H}}^{{\mathcal{I}}\triangle{\mathcal{I}}}$ have the same v-structures, and

3.  If $\pi$ is a discriminating path for a node $i$ in both $M_{\mathcal{G}}^{{\mathcal{I}}\triangle{\mathcal{I}}}$ and $M_{\mathcal{H}}^{{\mathcal{I}}\triangle{\mathcal{I}}}$ then $i$ is a collider on $\pi$ in one graph if and only if it is a collider on the other.

It then follows from Theorem \[thm: main\] and the characterization of Markov equivalence for MAGs given by @SR97 that two directed AGs ${\mathcal{G}}$ and ${\mathcal{H}}$ satisfy ${\mathcal{M}}_{\mathcal{I}}^{(c)}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}^{(c)}({\mathcal{H}})$ for a set of controlled interventions ${\mathcal{I}}$ if and only if they are ${\mathcal{I}}\triangle{\mathcal{I}}$-Markov equivalent according to Definition \[def: LMG I-Markov equivalence\]. Hence, when we are willing to assume controlled interventions, Theorem \[thm: kocaoglu characterization\] implies that we can partition the ${\mathcal{I}}$-Markov equivalence classes given by Theorem \[thm: coincide\] into finer ${\mathcal{I}}\triangle{\mathcal{I}}$-Markov equivalence classes. This, of course makes intuitive sense, since Theorem \[thm: kocaoglu characterization\] assumes the interventions are controlled, and hence imposes more invariances than needed in Theorem \[thm: coincide\]. An example of this refinement is given in Figure \[fig: refined\].

\[thick,scale=0.3\]

(h1) at (0,0) <span>$1$</span>; (h2) at (3,0) <span>$2$</span>; (h3) at (5,3) <span>$3$</span>;

(hwI) at (1,4) ; (hwJ) at (6,5.5) ;

(g1) at (13,0) <span>$1$</span>; (g2) at (16,0) <span>$2$</span>; (g3) at (18,3) <span>$3$</span>;

(gwI) at (14,4) ; (gwJ) at (19,5.5) ;

(t1) at (0,-8) <span>$1$</span>; (t2) at (3,-8) <span>$2$</span>; (t3) at (5,-5) <span>$3$</span>;

(twI) at (1,-4) ; (twJ) at (6,-2.5) ; (twIJ) at (-3,-7.8) ;

(r1) at (13,-8) <span>$1$</span>; (r2) at (16,-8) <span>$2$</span>; (r3) at (18,-5) <span>$3$</span>;

(rwI) at (14,-4) ; (rwJ) at (19,-2.5) ; (rwIJ) at (10,-7.8) ;

(h1) – (h2) ; (h2) – (h3) ; (h1) – (h3) ; (hwI) – (h1) ; (hwI) – (h3) ; (hwJ) – (h3) ;

(g1) – (g2) ; (g2) – (g3) ; (g1) – (g3) ; (gwI) – (g1) ; (gwI) – (g3) ; (gwJ) – (g3) ;

(t1) – (t2) ; (t2) – (t3) ; (t1) – (t3) ; (twI) – (t1) ; (twI) – (t3) ; (twJ) – (t3) ; (twIJ) – (t1) ;

(r1) – (r2) ; (r2) – (r3) ; (r1) – (r3) ; (rwI) – (r1) ; (rwI) – (r3) ; (rwJ) – (r3) ; (rwIJ) – (r1) ;

at (.1,3.75) <span>$\omega_{I}$</span>; at (6.75,6) <span>$\omega_{J}$</span>; at (13.1,3.75) <span>$\omega_{I}$</span>; at (19.75,6) <span>$\omega_{J}$</span>; at (.1,-4.25) <span>$\omega_{I}$</span>; at (6.75,-2) <span>$\omega_{J}$</span>; at (13.1,-4.25) <span>$\omega_{I}$</span>; at (19.75,-2) <span>$\omega_{J}$</span>; at (-4,-8.5) <span>$\omega_{I\triangle J}$</span>; at (9,-8.5) <span>$\omega_{I\triangle J}$</span>;

Discussion {#sec: discussion}
==========

Here, we generalized the notion of ${\mathcal{I}}$-Markov equivalence to all formal independence models associated to loopless mixed graphs, and we gave a combinatorial characterization of this equivalence for ancestral graphs. We also generalized the interventional settings ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ for DAGs to ADMGs via their factorization criterion, and characterized when ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$. When the ADMG is also an AG, and we have access to the observed distribution, we showed that this equality holds precisely when ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent from the perspective of formal independence models. This yields a theory for modeling interventional Markov equivalence in the presence of latent confounders via directed AGs that is applicable even when the interventions are uncontrolled. While the work here assumes access to the observational distribution, a natural follow-up project is to extend it to the purely interventional setting and then apply this theory to causal discovery algorithms that use observational and interventional data. It would also be of interest to extend this work to other families of LMGs, such as cyclic graphs.

\[thick,scale=0.45\]

(h1) at (0,0) <span>$1$</span>; (h2) at (3,0) <span>$2$</span>; (h3) at (3,3) <span>$3$</span>; (h4) at (0,3) <span>$4$</span>;

(g1) at (10,0) <span>$1$</span>; (g2) at (13,0) <span>$2$</span>; (g3) at (13,3) <span>$3$</span>; (g4) at (10,3) <span>$4$</span>;

(h1) – (h2) ; (h2) – (h3) ; (h3) – (h4) ; (h2) – (h4) ; (h3) – (h1) ;

(g1) – (g2) ; (g2) – (g3) ; (g3) – (g4) ; (g1) – (g4) ; (g2) – (g4) ; (g3) – (g1) ;

at (1.5,-1.5) <span>${\mathcal{G}}$</span>; at (11.5,-1.5) <span>$\overline{{\mathcal{G}}}$</span>;

It is further interesting to note that, while the methods presented here and in @KJSB19 [@YKU18] develop a theory for refining Markov equivalence classes by way of general interventions, in some cases, these methods are weaker than the methods applicable only to perfect interventions. For instance, if one wishes to distinguish between a given ancestral graph and the unique (Markov equivalent) MAG containing it, we cannot use any of the methods developed for general interventions. However, we can use those existing only for perfect interventions. For example, the graph on the left-hand-side of Figure \[fig: hard\] is an ancestral graph for which the graph on the right-hand-side is the unique MAG containing it.

In Figure \[fig: hard intervened\] we see on the top row that, using the methods for model interventions via ${\mathcal{I}}$-graphs studied here and in @KJSB19 [@YKU18], we cannot distinguish the two graphs. This is because their ${\mathcal{I}}$-graphs have the same ${\mathcal{I}}$-colliders with order. On the other hand, when modeling a perfect intervention, we remove all arrows pointing into the targeted node. In the bottom line, of Figure \[fig: hard intervened\], we see that by removing the arrows corresponding to the same intervention (assumed now to be perfect), we recover two ancestral graphs with different colliders with order. Hence, the methods for modeling perfect interventions can further distinguish graphs in the same Markov equivalence class. A careful investigation of what methods can be used for perfect and general interventions when attempting to distinguish between different nonmaximal elements of a Markov equivalence class would be of interest.

\[thick,scale=0.45\]

(h1) at (0,0) <span>$1$</span>; (h2) at (3,0) <span>$2$</span>; (h3) at (3,3) <span>$3$</span>; (h4) at (0,3) <span>$4$</span>;

(hw14) at (5,.4) ;

(g1) at (13,0) <span>$1$</span>; (g2) at (16,0) <span>$2$</span>; (g3) at (16,3) <span>$3$</span>; (g4) at (13,3) <span>$4$</span>;

(gw14) at (18,.4) ;

(r1) at (0,-8) <span>$1$</span>; (r2) at (3,-8) <span>$2$</span>; (r3) at (3,-5) <span>$3$</span>; (r4) at (0,-5) <span>$4$</span>;

(t1) at (13,-8) <span>$1$</span>; (t2) at (16,-8) <span>$2$</span>; (t3) at (16,-5) <span>$3$</span>; (t4) at (13,-5) <span>$4$</span>;

(h1) – (h2) ; (h2) – (h3) ; (h3) – (h4) ; (h2) – (h4) ; (h3) – (h1) ; (hw14) – (h2) ;

(g1) – (g2) ; (g2) – (g3) ; (g3) – (g4) ; (g1) – (g4) ; (g2) – (g4) ; (g3) – (g1) ; (gw14) – (g2) ;

(r3) – (r4) ; (r2) – (r4) ; (r3) – (r1) ;

(t3) – (t4) ; (t1) – (t4) ; (t2) – (t4) ; (t3) – (t1) ;

at (6,0) <span>$\omega_{\{2\}}$</span>; at (19,0) <span>$\omega_{\{2\}}$</span>; at (1.5,-1.5) <span>${\mathcal{G}}^{\mathcal{I}}$</span>; at (14.5,-1.5) <span>$\overline{{\mathcal{G}}}^{{\mathcal{I}}}$</span>;

Acknowledgements {#acknowledgements .unnumbered}
----------------

Liam Solus was supported by a Starting Grant (No. 2019-05195) from Vetenskapsrådet, and the Wallenberg Autonomous Systems and Software Program (WASP).

Preliminary Definitions and Results on LMGs
===========================================

Graph Theory Definitions
------------------------

The following is a complete dictionary of the graph theoretical terms used in the manuscript. A *mixed graph* is a graph ${\mathcal{G}}= ([p],E)$ in which the set of edges $E$ contains a mixture of *undirected* $i-j$, *bidirected* $i \leftrightarrow j$, and *directed* $i\rightarrow j$ edges. A mixed graph ${\mathcal{G}}$ is called *simple* if there exists at most one edge of any type between each pair of nodes in ${\mathcal{G}}$. For each edge-type, we call $i$ and $j$ the *endpoints* of the edge, and we say $i$ and $j$ are *adjacent* ${\mathcal{G}}$ if they are the two endpoints of any single edge in ${\mathcal{G}}$. We call $i\in[p]$ a *source* if all edges with endpoint $i$ have no arrowhead at $i$, and we call $i$ a *sink* if every edge with endpoint $i$ has an arrowhead at $i$. If it is ambiguous as to whether or not there is an arrowhead at the endpoint $i$ of an edge $e$, we will place an empty circle at the endpoint $i$; for example $i {\,\circ\!\!\! \rightarrow \! }j$. If $A\subset [p]$, the *induced subgraph of ${\mathcal{G}}$ on $A$*, denoted ${\mathcal{G}}\langle A \rangle$, is the graph with node set $A$ and all edges in $E$ which have both endpoints in $A$. A *loopless mixed graph* (LMG) is a mixed graph that does not contain any *loops*; i.e., edges which have both endpoints being the same node. For an LMG ${\mathcal{G}}= ([p],E)$, and $i\in[p]$, we say that $j\in[p]$ is a *parent* of $i$ in ${\mathcal{G}}$ if $j\rightarrow i\in E$, we say $j$ is a *spouse* of $i$ if $i\leftrightarrow j\in E$, we say $j$ is a *child* of $i$ if $i\rightarrow j\in E$, and we let $\pa_{\mathcal{G}}(i)$, $\sp_{\mathcal{G}}(i)$, and $\de_{\mathcal{G}}(i)$ denote the parents, spouses, and children of $i$ in ${\mathcal{G}}$, respectively. A *path* in ${\mathcal{G}}$ is a sequence $\pi = \langle v_1,e_1,v_2,e_2,\ldots,v_{m-1},e_{m-1},v_m\rangle$ where $v_k\in [p]$ and $e_k \in E$ for all $k$ and $e_k$ has endpoints $v_k$ and $v_{k-1}$. We call $v_1$ and $v_m$ the *endpoints* of $\pi$. If $A\subset[p]$ such that for each $a,b\in A$ there exists some path $\pi$ in ${\mathcal{G}}$ between $a$ and $b$ using only vertices in $A$, then $A$ (or the induced subgraph ${\mathcal{G}}\langle A\rangle$) is called *path-connected* in ${\mathcal{G}}$. For a path $\pi$, if $e\in E$ is an edge with endpoints $v_1$ and $v_m$ such that $e$ has an arrowhead at the endpoint $e_1$ if and only if $e_1$ has an arrowhead at $v_1$, and similarly for $e_{m-1}$ and $v_m$, then we call $e$ an *endpoint-identical edge* for $\pi$. Any subsequence of $\pi$ that is also a path is called a *subpath* of $\pi$. A path $\pi$ is called *directed* if $e_k = v_k\rightarrow v_{k+1}$ for all $k$, and it is called *anterior* if there exists $t\in [m]$ such that $e_k = v_k - v_{k+1}$ for all $k \leq t$ and $e_k = v_k \rightarrow v_{k+1}$ for all $k > t$. A *cycle* is a sequence $\pi = \langle v_1,e_1,v_2,e_2,\ldots,v_{m-1},e_{m-1},v_m\rangle$ where $v_k\in [p]$ and $e_k \in E$ for all $k$, $e_k$ has endpoints $v_k$ and $v_{k-1}$, and $v_m = v_1$. It is called *directed* if $e_k = v_k\rightarrow v_{k+1}$ for all $k$. When the edges in a path or cycle $\pi$ are understood, we will simply write $\pi$ as the sequence of vertices $\pi = \langle v_1,v_2,\ldots,v_m\rangle$. A node $j\in[p]$ is an *ancestor* of $i\in[p]$ in ${\mathcal{G}}$ if there exists a directed path $\pi$ in ${\mathcal{G}}$ with $v_1 = j$ and $v_m = i$. In this case $i$ is called a *descendant* of $j$ in ${\mathcal{G}}$. Similarly, $j$ is *anterior* to $i$ if the path $\pi$ is an anterior path. We let $\an_{\mathcal{G}}(i)$, $\de_{\mathcal{G}}(i)$, and $\ant_{\mathcal{G}}(i)$ denote the collection of nodes in ${\mathcal{G}}$ that are ancestors, descendants, or anterior to $i$, respectively.

A vertex $v$ on a path $\pi = \langle v_1,v_2,\ldots,v_m\rangle$ that is not an endpoint of $\pi$ is called a *collider* if two arrowheads point to $v$ on $\pi$. A *collider path* is a path on which every vertex is a collider except for its endpoints. A collider path on three nodes $\langle v_1,v_2,v_3\rangle$ is called a *v-structure* (or an *unshielded collider* or an *immorality*) @ARS09 [@GP01] if $v_1$ and $v_3$ are not adjacent in ${\mathcal{G}}$.

An LMG ${\mathcal{G}}$ is called *maximal* if adding any edge to ${\mathcal{G}}$ changes the collection ${\mathcal{J}}({\mathcal{G}})$ of m-separation statements. To identify the unique maximal graph containing an ancestral graph (AG), we consider its inducing paths: an *inducing path* $\pi$ between vertices $i$ and $j$ of an AG ${\mathcal{G}}$ is a path on which any non-endpoint vertex is both a collider on $\pi$ and an ancestor of at least one of $i$ or $j$ in ${\mathcal{G}}$. When discussing AGs, we will also utilize the notion of discriminating paths, whose existence in a pair of MAGs implies that a certain collider path $\langle i,j,k\rangle$ will be the same in both graphs, even though $i$ and $k$ are adjacent. A path $\pi = \langle v_0,v_1,\ldots,v_m,j,k\rangle$ is a *discriminating path* for $\langle v_m,j,k\rangle$ in a MAG ${\mathcal{G}}$ if $v_0$ is not adjacent to $k$, and for all $i\in[m]$, the vertex $v_i$ is a collider on $\pi$ and a parent of $k$. Using discriminating paths, we can also define *triples with order*. A triple $\langle i,j,k\rangle$ has *order $0$* if $i$ and $k$ are not adjacent. For $t\geq0$, if we let $\mathfrak{D}_t$ denote the set of all *triples of order $t$* in a given MAG ${\mathcal{G}}$, then $\langle i,j,k\rangle\in\mathfrak{D}_{t+1}$ if it is not a triple with order $s<t+1$, and there is a discriminating path $\langle v_0,v_1,\ldots,v_m,b,c\rangle$ with either $\langle i,j,k\rangle = \langle v_m,b,c\rangle$ or $\langle k,j,i\rangle = \langle v_m,b,c\rangle$ such that $$\langle v_0,v_1,v_2\rangle, \langle v_1,v_2,v_3\rangle, \ldots, \langle v_{m-1},v_m,b\rangle\in\bigcup_{s\leq t}\mathfrak{D}_s.$$ A graph ${\mathcal{G}}$ is called *anterior* if ${\mathcal{G}}$ contains no triples of the form $i {\,\circ\!\!\! \rightarrow \! }j - k$. Given an LMG ${\mathcal{G}}$, the *anterior graph of ${\mathcal{G}}$*, denoted ${\mathcal{G}}^\ast$, is the graph produced by consecutively removing all arrowheads pointing into nodes adjacent to an undirected edge; i.e. $i \leftrightarrow j - k$ becomes $i \leftarrow j - k$ and $i \rightarrow j - k$ becomes $i - j - k$. We will use the following lemma from @SL14 on the anterior graphs of ribbonless graphs (RGs):

@SL14 [Proposition 1] \[lem: RG anterior graph\] If ${\mathcal{G}}$ is an RG then $
{\mathcal{J}}({\mathcal{G}}) = {\mathcal{J}}({\mathcal{G}}^\ast).
$

We will also require a few lemmas about maximal graphs, the first of which is immediate:

\[lem: maximal graph\] An LMG ${\mathcal{G}}= ([p],E)$ is maximal if and only if for every pair of nonadjacent nodes $i,j\in[p]$ there exists a subset $C\subset[p]\backslash\{i,j\}$ such that $
\langle i, j\mid C\rangle \in {\mathcal{J}}({\mathcal{G}}).
$

The next lemma takes a bit more work, but is a natural extension of an observation made by @ARS09. For the sake of completeness, we give a proof here.

\[lem: maximal graphs, adjacencies, v-structures\] Let ${\mathcal{G}}$ and ${\mathcal{H}}$ be Markov equivalent maximal simple LMGs on node set $[p]$. Then ${\mathcal{G}}$ and ${\mathcal{H}}$ have the same adjacencies and v-structures.

Suppose first that $i$ and $j$ are adjacent in ${\mathcal{G}}$ but not in ${\mathcal{H}}$. Since they are not adjacent in ${\mathcal{H}}$ then, by @SL14 [Lemma 4], there exists a subset $C$ of $[p]\setminus\{i,j\}$ such that $i$ is $m$-separated from $j$ given $C$ in ${\mathcal{H}}$. Therefore, since ${\mathcal{J}}({\mathcal{G}}) = {\mathcal{J}}({\mathcal{H}})$ and $\langle i,j \mid C\rangle\in {\mathcal{J}}({\mathcal{H}})$, it follows that $i$ is $m$-separated from $j$ given $C$ in ${\mathcal{G}}$. However, this contradicts the fact that $i$ and $j$ are adjacent, since an adjacency is always an $m$-connecting path. By symmetry of this argument, we deduce that ${\mathcal{G}}$ and ${\mathcal{H}}$ have the same adjacencies.

Suppose now that $i {\,\circ\!\!\! \rightarrow \! }j{ \! \leftarrow\!\!\! \circ  \,}k$ forms a v-structure in ${\mathcal{G}}$ but not in ${\mathcal{H}}$. Since $i$ and $k$ are not adjacent, then by maximality of ${\mathcal{G}}$ we know that there exists a triple $\langle i, k \mid C\rangle\in {\mathcal{J}}({\mathcal{G}})$ for some $C\subset[p]\setminus\{i,j\}$. By Markov equivalence of ${\mathcal{G}}$ and ${\mathcal{H}}$, we know that $\langle i, k, \mid C\rangle\in{\mathcal{J}}({\mathcal{H}})$ as well. Moreover, by the previous argument, we know that $i$ and $k$ are not adjacent in ${\mathcal{H}}$. Note now that we must have $j\notin C$, since otherwise $i {\,\circ\!\!\! \rightarrow \! }j{ \! \leftarrow\!\!\! \circ  \,}k$ would form an $m$-connecting path given $C$ in ${\mathcal{G}}$. Thus, since $j\notin C$, $i$ and $k$ are not adjacent in ${\mathcal{H}}$, and the tripath $\langle i,j,k\rangle$ in ${\mathcal{H}}$ is not a collider path (since it is not a v-structure), then the path $\langle i,j,k\rangle$ must be $m$-connecting given $C$ in ${\mathcal{H}}$. However, this contradicts the fact that $\langle i, k \mid C\rangle\in {\mathcal{J}}({\mathcal{H}})$. Thus, we conclude that ${\mathcal{G}}$ and ${\mathcal{H}}$ must have the same v-structures.

\[thick,scale=.5\]

(ZAP70) at (-9,0) <span>ZAP70</span>; (LCK) at (-6,0) <span>LCK</span>; (SLP-76) at (-3,0) <span>SLP-76</span>; (PI3K) at (0,0) <span>PI3K</span>; (RAS) at (3,0) <span>RAS</span>; (Cytohesin) at (6,0) <span>Cytohesin</span>; (PKC) at (2,-2) <span>PKC</span>; (PLC) at (-3,-3) <span>PLC$\gamma$</span>; (PIP3) at (-.5,-4.5) <span>PIP3</span>; (PIP2) at (-4,-5) <span>PIP2</span>; (Akt) at (2,-4) <span>Akt</span>; (PKA) at (2.5,-6) <span>PKA</span>; (Raf) at (4.5,-6) <span>Raf</span>; (Mek$1/2$) at (7.5,-6) <span>Mek$1/2$</span>; (Erk$1/2$) at (6,-8) <span>Erk$1/2$</span>; (P38) at (2.5,-8) <span>P38</span>; (JNK) at (0,-6.5) <span>JNK</span>;

(ZAP70) – (LCK) ; (LCK) – (SLP-76) ; (SLP-76) – (PI3K) ; (PI3K) – (RAS) ; (Cytohesin) – (RAS) ; (PKC) – (RAS) ; (PKC) – (PIP2) ; (PLC) – (PKC) ; (PIP3) – (PLC) ; (PIP2) – (PIP3) ; (PIP2) edge\[&lt;-&gt;,bend left=45\] (PI3K) ; (PLC) – (PIP2) ; (PIP3) – (Akt) ; (PKA) – (Akt) ; (PKC) – (Raf) ; (RAS) – (Raf) ; (Raf) – (Mek$1/2$) ; (Mek$1/2$) – (Erk$1/2$) ; (PKA) – (P38) ; (PKC) – (JNK) ;

\(1) at (-10,-1.5) <span>$1$</span>; (2) at (1,1.25) <span>$2$</span>; (3) at (8,-1.5) <span>$3$</span>; (4) at (1.7,-.5) <span>$4$</span>; (5) at (1.5,-7) <span>$5$</span>; (6) at (1,-.9) <span>$6$</span>; (7) at (1.25,-5) <span>$7$</span>; (8) at (-5,-3.5) <span>$8$</span>; (9) at (7,-4.5) <span>$9$</span>; (10) at (-1,1) <span>$10$</span>;

\(1) – (ZAP70) ; (2) – (PI3K) ; (3) – (Cytohesin) ; (4) – (PKC) ; (5) – (PKA) ; (6) – (PKC) ; (7) – (Akt) ; (8) – (PIP2) ; (9) – (Mek$1/2$) ; (10) – (PI3K) ;

(key1) at (-8.5,-5) ; (key2) at (-8.5,-5.75) ;

Lemmata and Proofs for Section \[sec: I-Markov equivalence for MAGs\] {#app: lemmata and proofs for sec 3}
=====================================================================

We will require the following fact about the ${\mathcal{I}}$-graph produced by intervening on an AG without doubly-intervening on any selection adjacent nodes.

\[lem: ribbonless\] Let ${\mathcal{G}}= ([p],E)$ be an AG, and ${\mathcal{I}}$ a collection of intervention targets. Then ${\mathcal{I}}$ does not doubly-intervene on any selection adjacent nodes of ${\mathcal{G}}$ if and only if ${\mathcal{G}}^{\mathcal{I}}$ is ribbonless.

Suppose that ${\mathcal{G}}^{\mathcal{I}}$ contains no doubly-intervened selection adjacent nodes. If ${\mathcal{G}}^{\mathcal{I}}$ contains a ribbon then there exists a collider path $\langle i,j,k\rangle$ such that (1) $i$ and $k$ have no endpoint identical edge between them, and (2) $j$ or a descendant of $j$ is an endpoint of a line, or $j$ is in a directed cycle. Since ${\mathcal{G}}$ is an AG, it contains no directed cycle. So any ribbon $\langle i,j,k\rangle$ in ${\mathcal{G}}^{\mathcal{I}}$ must have $j$ or a descendant of $j$ as the endpoint of an undirected edge. Since ${\mathcal{G}}$ is an AG, this could only happen if $i,k\in W_{\mathcal{I}}$, meaning that $j$ must be a doubly-intervened selection adjacent node. Hence, ${\mathcal{G}}^{\mathcal{I}}$ must be ribbonless.

Conversely, suppose that ${\mathcal{G}}^{\mathcal{I}}$ is ribbonless. Let $j$ be a selection adjacent node in ${\mathcal{G}}$. If $\omega_I,\omega_J\in W_{\mathcal{I}}$ are such that $j\in I\cap J$, then the collider path $\langle \omega_I,j,\omega_J\rangle$ would be a ribbon in ${\mathcal{G}}^{\mathcal{I}}$. Hence, ${\mathcal{G}}^{\mathcal{I}}$ contains no doubly-intervened selection adjacent nodes.

To generalize Theorem \[thm: YKU characterization\] to AGs, we will work with maximal AGs, or MAGs. Our first goal is to show that this is sufficient in the sense that two AGs ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent if and only if their unique maximal extensions $\overline{{\mathcal{G}}}$ and $\overline{{\mathcal{H}}}$ are ${\mathcal{I}}$-Markov equivalent. To do so, we need the following two lemmas. Recall that, given ${\mathcal{G}}= ([p], E)$ and a subset $A\subset[p]$, we let ${\mathcal{G}}\langle A\rangle$ denote the induced subgraph of ${\mathcal{G}}$ on $A$.

\[lem: restriction\] Let ${\mathcal{G}}= ([p],E)$ be an AG, and ${\mathcal{I}}$ a collection of intervention targets that does not doubly-intervene on any selection adjacent nodes of ${\mathcal{G}}$. Then $
\overline{{\mathcal{G}}} = \overline{{\mathcal{G}}^{\mathcal{I}}}\langle [p]\rangle.
$

Note first, by Lemma \[lem: ribbonless\], $\overline{{\mathcal{G}}^{\mathcal{I}}}$ is well-defined since ${\mathcal{G}}^{\mathcal{I}}$ is ribbonless. We now show the inclusion $\overline{{\mathcal{G}}}\supseteq\overline{{\mathcal{G}}^{\mathcal{I}}}\langle[p]\rangle$. First, recall from @RS02 [Theorem 5.1] that, in an AG ${\mathcal{G}}$, if two nodes $i$ and $j$ are adjacent in $\overline{{\mathcal{G}}}$ but not in ${\mathcal{G}}$ then they are connected by a bidirected edge in $\overline{{\mathcal{G}}}$ and an inducing path containing at least two edges in ${\mathcal{G}}$. Hence, to prove the desired inclusion, we must show that if $i,j\in[p]$ are connected by a bidirected edge in $\overline{{\mathcal{G}}^{\mathcal{I}}}$ but are not adjacent in ${\mathcal{G}}^{\mathcal{I}}$, then $i$ and $j$ are connected by a bidirected edge in $\overline{{\mathcal{G}}}$. To this end, note that if $i,j\in[p]$ are adjacent in $\overline{{\mathcal{G}}^{\mathcal{I}}}$ but not in ${\mathcal{G}}^{\mathcal{I}}$ then they are connected by an inducing path in ${\mathcal{G}}^{\mathcal{I}}$ containing at least two edges, say $\pi = \langle v_0 = i, v_1,\ldots,v_{m-1},v_m = j\rangle$ where $m\geq2$. Thus, to prove that $i$ and $j$ are also connected by a bidirected edge in $\overline{{\mathcal{G}}}$, it suffices to show that $\pi$ is an inducing path in ${\mathcal{G}}$. However, by @RS02 [Lemma 4.5 (iii)], we know that every edge on $\pi$ is bidirected. Hence, since each node in $W_{\mathcal{I}}$ is a source node, we know that $v_1,\ldots, v_{m-1}\in[p]$ and $\pi$ is a path in ${\mathcal{G}}$. Similarly, since $\pi$ is an inducing path in ${\mathcal{G}}^{\mathcal{I}}$ then each $v_k$, $k = 1,\ldots, m-1$, is an ancestor of $i$ or $j$. So, without loss of generality, there exists a directed path $s = \langle v_0^\prime = v_k,v_1^\prime, \ldots, v_t^\prime = i\rangle$ from $v_k$ to $i$ in ${\mathcal{G}}^{\mathcal{I}}$. However, since all nodes in $W_{\mathcal{I}}$ are source nodes in ${\mathcal{G}}^{\mathcal{I}}$, then no vertex or edge on $s$ can be in $W_{\mathcal{I}}$ or $E_{\mathcal{I}}$, respectively. Hence, $s$ is also a directed path in ${\mathcal{G}}$. It then follows that $\pi$ is an inducing path in ${\mathcal{G}}$, and we conclude that $\overline{{\mathcal{G}}}\supseteq\overline{{\mathcal{G}}^{\mathcal{I}}}\langle[p]\rangle$.

To see the reverse inclusion, we must show that if $i,j\in[p]$ are nonadjacent in ${\mathcal{G}}$ but adjacent in $\overline{{\mathcal{G}}}$ (and therefore connected by a bidirected edge), then $i$ and $j$ are connected by a bidirected edge in $\overline{{\mathcal{G}}^{\mathcal{I}}}\langle[p]\rangle$ as well. So suppose that $i,j\in[p]$ are nonadjacent in ${\mathcal{G}}$ but adjacent in $\overline{{\mathcal{G}}}$. For the sake of contradiction, suppose now that $i$ and $j$ are not connected by a bidirected edge in $\overline{{\mathcal{G}}^{\mathcal{I}}}\langle[p]\rangle$. Then they are nonadjacent in $\overline{{\mathcal{G}}^{\mathcal{I}}}\langle[p]\rangle$. Since $i$ and $j$ are adjacent in $\overline{{\mathcal{G}}}$, then there exists an inducing path containing at least two edges in ${\mathcal{G}}$ between $i$ and $j$. Then the same inducing path must also be in ${\mathcal{G}}^{\mathcal{I}}$ and in $\overline{{\mathcal{G}}^{\mathcal{I}}}\langle[p]\rangle$. However, by @RS02 [Corollary 4.6], this contradicts the maximality of $\overline{{\mathcal{G}}^{\mathcal{I}}}$. Thus, we conclude that $\overline{{\mathcal{G}}^{\mathcal{I}}}\langle[p]\rangle\supseteq\overline{{\mathcal{G}}}$, and hence $\overline{{\mathcal{G}}^{\mathcal{I}}}\langle[p]\rangle=\overline{{\mathcal{G}}}$.

\[lem: no additional intervening\] Let ${\mathcal{G}}= ([p],E)$ be an AG, and ${\mathcal{I}}$ a collection of intervention targets that does not doubly-intervene on any selection adjacent nodes of ${\mathcal{G}}$. If $i\in W_{\mathcal{I}}$ and $j\in[p]$ such that $i$ and $j$ are not adjacent in ${\mathcal{G}}^{\mathcal{I}}$, then $i$ and $j$ are not adjacent in $\overline{{\mathcal{G}}^{\mathcal{I}}}$.

By Lemma \[lem: maximal graph\] it suffices to prove that $$i{\protect\mathpalette{\protect\independenT}{\perp}}j\mid\left(\ant(j)\cup W_{\mathcal{I}}\right)\backslash\{i,j\}.$$ Suppose on the contrary, that there exists an $m$-connecting path $\pi = \langle i,q_1,\ldots,q_m, j\rangle$ given $C= \left(\ant(j)\cup W_{\mathcal{I}}\right)\backslash\{i,j\}$ in ${\mathcal{G}}^{\mathcal{I}}$. Notice first that since $i\in W_{\mathcal{I}}$, we know that $i\rightarrow q_1$. Moreover, since all nodes in $W_{\mathcal{I}}$ are source nodes in ${\mathcal{G}}^{\mathcal{I}}$ and $W_{\mathcal{I}}\backslash\{i\}\subseteq C$, then $q_1,\ldots,q_m\in[p]$; that is, the path $\langle q_1,\ldots,q_m\rangle$ is contained in ${\mathcal{G}}$. Since $\ant(j)\backslash\{j\}\subseteq C$, we know that $\pi$ is not of the form $$i\rightarrow q_1 - q_2 - \cdots - q_{k-1} \rightarrow q_k \rightarrow q_{k+1} \rightarrow \cdots \rightarrow q_m \rightarrow j.$$ Hence, there must be some collider on $\pi$. Take the collider path $\langle q_{t-1},q_t,q_{t+1}\rangle$ on $\pi$ with $t$ maximum. Since $\pi$ is $m$-connecting then $q_t\in C\cup\an(C)$. Since every node in $W_{\mathcal{I}}$ is a source node, it must be that $q_t\in\ant(j)\backslash\{j\}$. Since $t$ is maximum, then $q_{t+1},\ldots,q_m$ are noncolliders on $\pi$, and hence not in $\ant(j)\setminus\{j\}$. Hence, the subpath $\langle q_{t+1},\ldots,q_m,j\rangle$ of $\pi$ must be of the form $$q_{t+1}\leftarrow q_{t+2}\leftarrow \cdots \leftarrow j.$$ It follows that $q_t\in\an(j)\setminus\{j\}$. This is because the node $q_t$ could only be in $\ant(j)\setminus(\an(j)\cup\{j\})$ if $q_{t+1}\in W_{\mathcal{I}}$, but this is impossible since we have already seen that $q_1,\ldots,q_m,j\in[p]$. As well, it also follows that the edge between $q_t$ and $q_{t+1}$ cannot be bidirected, as this would contradict the maximality of $t$. Therefore, the edge between $q_t$ and $q_{t+1}$ must be of the form $q_t\leftarrow q_{t+1}$. However, since $q_t\in\an(j)\setminus\{j\}$, it then follows that there is a directed cycle in ${\mathcal{G}}$, which contradicts the assumption that ${\mathcal{G}}$ is ancestral. Thus, we conclude that no such $m$-connecting path exists, completing the proof.

Using Lemmas \[lem: restriction\] and  \[lem: no additional intervening\], we get the following:

\[prop: commuting\] Let ${\mathcal{G}}= ([p],E)$ be an AG, and ${\mathcal{I}}$ a collection of intervention targets that does not doubly-intervene on any selection adjacent nodes in ${\mathcal{G}}$. Then $
\overline{{\mathcal{G}}}^{\mathcal{I}}= \overline{{\mathcal{G}}^{\mathcal{I}}}.
$

By Lemmas \[lem: restriction\] and \[lem: no additional intervening\], we know that the only possible adjacencies in $\overline{{\mathcal{G}}^{\mathcal{I}}}$ that may not be in $\overline{{\mathcal{G}}}^{\mathcal{I}}$ would be between nodes in $W_{\mathcal{I}}$. By Lemma \[lem: ribbonless\], we know ${\mathcal{G}}^{\mathcal{I}}$ is ribbonless. Hence, by @S12 [Algorithm 2.2], we know that $\overline{{\mathcal{G}}^{\mathcal{I}}}$ is produced from ${\mathcal{G}}^{\mathcal{I}}$ by adding endpoint identical edges between the endpoints of inducing paths in ${\mathcal{G}}^{\mathcal{I}}$. Since every node in $W_{\mathcal{I}}$ is a source node in ${\mathcal{G}}^{\mathcal{I}}$, we also know there are no arrowheads pointing to these nodes. Thus, by @S12 [Proposition 2.6], we know that there is no inducing path between nodes in $W_{\mathcal{I}}$. Thus, we conclude that $\overline{{\mathcal{G}}}^{\mathcal{I}}= \overline{{\mathcal{G}}^{\mathcal{I}}}.$

Proposition \[prop: commuting\] tells us that if ${\mathcal{I}}$ is a collection of intervention targets that does not doubly-intervene on any selection adjacent nodes in either of two AGs ${\mathcal{G}}$ and ${\mathcal{H}}$, then ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent if and only if $\overline{{\mathcal{G}}}$ and $\overline{{\mathcal{H}}}$ are ${\mathcal{I}}$-Markov equivalent. This is because we have $$\begin{split}
\overline{{\mathcal{H}}}^{\mathcal{I}}= \overline{{\mathcal{H}}^{\mathcal{I}}}\approx {\mathcal{H}}^{\mathcal{I}}&\approx {\mathcal{G}}^{\mathcal{I}}\approx \overline{{\mathcal{G}}^{\mathcal{I}}} = \overline{{\mathcal{G}}}^{\mathcal{I}}, \mbox{ and} \\ 
{{\mathcal{H}}}^{\mathcal{I}}\approx \overline{{\mathcal{H}}^{\mathcal{I}}} =  \overline{{\mathcal{H}}}^{\mathcal{I}}&\approx \overline{{\mathcal{G}}}^{\mathcal{I}}= \overline{{\mathcal{G}}^{\mathcal{I}}} \approx {{\mathcal{G}}}^{\mathcal{I}}.\\
\end{split}$$ Hence, it suffices to characterize ${\mathcal{I}}$-Markov equivalence when ${\mathcal{G}}$ and ${\mathcal{H}}$ are assumed to be MAGs. Another immediate consequence of Proposition \[prop: commuting\] is the following:

\[lem: anterior graphs of interventions\] Suppose ${\mathcal{G}}= ([p],E)$ is an AG and ${\mathcal{I}}$ a collection of intervention targets that does not doubly-intervene on any nodes of ${\mathcal{G}}$. Then ${\mathcal{G}}$ is maximal if and only if $({\mathcal{G}}^{\mathcal{I}})^\ast$ is a MAG that is Markov equivalent to ${\mathcal{G}}^{\mathcal{I}}$.

First assume that ${\mathcal{G}}$ is maximal; i.e., that ${\mathcal{G}}$ is a MAG. By Lemma \[lem: ribbonless\], we know that ${\mathcal{G}}^{\mathcal{I}}$ is ribbonless. By @SL14 [Proposition 1], we know that ${\mathcal{G}}^{\mathcal{I}}$ is Markov equivalent to $({\mathcal{G}}^{\mathcal{I}})^\ast$. To see that $({\mathcal{G}}^{\mathcal{I}})^\ast$ is a MAG, notice by Proposition \[prop: commuting\], ${\mathcal{G}}^{\mathcal{I}}$ is maximal since ${\mathcal{G}}= \overline{{\mathcal{G}}}$ implies ${\mathcal{G}}^{\mathcal{I}}= \overline{{\mathcal{G}}}^{\mathcal{I}}= \overline{{\mathcal{G}}^{\mathcal{I}}}$. It follows that $({\mathcal{G}}^{\mathcal{I}})^\ast$ is also maximal, since removing arrowheads pointing into selection adjacent nodes cannot generate new inducing paths. Moreover, since ${\mathcal{G}}$ is a MAG, then ${\mathcal{G}}^{\mathcal{I}}$ contains no directed cycles nor bidirected edges with a directed path between its endpoints. Hence, neither does $({\mathcal{G}}^{\mathcal{I}})^\ast$. Thus, $({\mathcal{G}}^{\mathcal{I}})^\ast$ is a MAG.

Conversely, suppose that $({\mathcal{G}}^{\mathcal{I}})^\ast$ is a MAG that is Markov equivalent to ${\mathcal{G}}^{\mathcal{I}}$. Since ${\mathcal{G}}$ is ancestral and ${\mathcal{I}}$ does not doubly-intervene on any selection adjacent nodes in ${\mathcal{G}}$, we know that ${\mathcal{G}}^{\mathcal{I}}$ is produced from $({\mathcal{G}}^{\mathcal{I}})^\ast$ by replacing undirected edges of the form $\omega_I - j$ for some $\omega_I\in W_{\mathcal{I}}$ and $j\in\sa({\mathcal{G}})$ a selection adjacent node, with directed arrows $\omega_I \rightarrow j$. Since ${\mathcal{G}}$ is ancestral and ${\mathcal{I}}$ does not doubly-intervene on any selection adjacent nodes, doing so cannot produce any new colliders, and hence ${\mathcal{G}}^{\mathcal{I}}$ does not containing any inducing paths that are not in $({\mathcal{G}}^{\mathcal{I}})^\ast$. Since, by Lemma \[lem: ribbonless\], ${\mathcal{G}}^{\mathcal{I}}$ is ribbonless, it follows from @SL14 [Theorem 2] that ${\mathcal{G}}^{\mathcal{I}}$ is maximal; i.e., $\overline{{\mathcal{G}}^{\mathcal{I}}} = {\mathcal{G}}^{\mathcal{I}}$. So by Proposition \[prop: commuting\], $
{\mathcal{G}}^{\mathcal{I}}= \overline{{\mathcal{G}}^{\mathcal{I}}} = \overline{{\mathcal{G}}}^{\mathcal{I}}.
$ Thus, ${\mathcal{G}}= \overline{{\mathcal{G}}}$; i.e., ${\mathcal{G}}$ is maximal.

Proof of Theorem \[thm: main\]
------------------------------

In order to prove Theorem \[thm: main\], we will use the following lemma.

\[lem: I-colliders with order\] Let $\langle i,j,k\rangle$ be an ${\mathcal{I}}$-collider with order $t$ in a LMG ${\mathcal{G}}$ for a collection of interventions ${\mathcal{I}}$. Then there is a discriminating path $
\pi = \langle v_0,\ldots, v_m,b,c\rangle
$ in ${\mathcal{G}}^{\mathcal{I}}$ for which

1.  $\langle i,j,k\rangle \in\{\langle v_m,b,c\rangle ,\langle c,b,v_m\rangle \}$,

2.  the subpaths $\langle v_0,v_1,v_2\rangle, \langle v_1,v_2,v_3\rangle, \ldots, \langle v_{m-1},v_m,b\rangle $ are all colliders with order less than or equal to $t$, and

3.  $\langle v_0,v_1,v_2\rangle$ is an ${\mathcal{I}}$-v-structure in ${\mathcal{G}}^{\mathcal{I}}$.

Let $\langle i,j,k\rangle$ be an ${\mathcal{I}}$-collider with order $t$ in ${\mathcal{G}}$. Then $\langle i,j,k\rangle$ is not a collider with order in ${\mathcal{G}}$. So, by @ARS09 [Definition 3.11], there does not exist a discriminating path $\pi = \langle v_0,\ldots, v_m,b,c\rangle$ in ${\mathcal{G}}$ satisfying properties (1) and (2). However, since $\langle i,j,k \rangle$ is a collider with order in ${\mathcal{G}}^{\mathcal{I}}$, it follows that there exists such a discriminating path $\pi$ in ${\mathcal{G}}^{\mathcal{I}}$. Therefore, it must be that at least one of the vertices $v_0,\ldots,v_m,b,c$ is an element of $W_{\mathcal{I}}$. Supposing that $m\neq 0$, it follows that $v_1,\ldots,v_m\notin W_{\mathcal{I}}$ since $W_{\mathcal{I}}$ contains only source nodes. Similarly, since (without loss of generality) $\langle v_m,b,c\rangle = \langle i,j,k\rangle$ , which is a collider, it follows that at least one of $v_0$ and $c$ is in $W_{\mathcal{I}}$. Since $\pi$ is a discriminating path, it follows that $v_1,\ldots, v_m$ are all parents of $c$ in the case that $m\neq0$. Since all nodes in $W_{\mathcal{I}}$ are source nodes, it follows that $c\in W_{\mathcal{I}}$ if and only if $m=0$ and $\langle i,j,k\rangle$ is an ${\mathcal{I}}$-v-structure. In this case, we have that $\langle v_0,b,c\rangle = \langle i,j,k\rangle$, as desired. On the other hand, if $c\notin W_{\mathcal{I}}$, it must be that $v_0\in W_{\mathcal{I}}$. By @ARS09 [Definition 3.11], it follows that $\langle v_0,v_1,v_2\rangle$ is a collider with order at most $t$. If $\langle v_0,v_1,v_2\rangle$ is a collider with order $0$, it is an ${\mathcal{I}}$-v-structure and we are done.

So suppose, for the sake of contradiction, that $\langle v_0,v_1,v_2\rangle$ has order $i>0$. Then, by @ARS09 [Definition 3.11], $\langle v_0,v_1,v_2\rangle$ is not a v-structure, and there exists a discriminating path $\langle q_0,\ldots, q_n,x,y\rangle$ in ${\mathcal{G}}^{\mathcal{I}}$ for which $\langle v_0,v_1,v_2\rangle\in\{ \langle q_n,x,y\rangle, \langle y,x,q_n\rangle\}$. By definition of a discriminating path, it follows that all of $q_1,\ldots, q_n$ are parents of $y$. Since, $\langle v_0,v_1,v_2\rangle$ is not a v-structure, it must be that $m\neq 0$, and thus, $y$ has at least one parent. Hence, $y\notin W_{\mathcal{I}}$, as $W_{\mathcal{I}}$ contains only source nodes. Similarly, since $m\neq0$, then, by @ARS09 [Definition 3.11], it must be that $\langle q_{n-1},q_{n}, x\rangle$ is a collider in ${\mathcal{G}}^{\mathcal{I}}$. However, this implies that $q_n$ is not a source node, and therefore $q_n\notin W_{\mathcal{I}}$. This yields a contradiction to the assumption that $i>0$. Thus, we conclude that $\langle v_0,v_1,v_2\rangle$ is a collider with order $0$, and therefore it is an ${\mathcal{I}}$-v-structure in ${\mathcal{G}}^{\mathcal{I}}$.

###  Proof of Theorem \[thm: main\]

The equivalence of (1) and (2) is an immediate consequence of Proposition \[prop: commuting\]. So it only remains to show (2) if and only if (3). For notational simplicity, in the remainder of this proof we assume ${\mathcal{G}}$ and ${\mathcal{H}}$ are MAGs. Suppose first that ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent. By Lemma \[lem: ribbonless\], we know that ${\mathcal{G}}^{\mathcal{I}}$ and ${\mathcal{H}}^{\mathcal{I}}$ are ribbonless graphs satisfying ${\mathcal{J}}({\mathcal{G}}^{\mathcal{I}}) = {\mathcal{J}}({\mathcal{H}}^{\mathcal{I}})$. Hence, ${\mathcal{J}}({\mathcal{G}}) = {\mathcal{J}}({\mathcal{H}})$, and so it only remains to show that ${\mathcal{G}}^{\mathcal{I}}$ and ${\mathcal{H}}^{\mathcal{I}}$ have the same ${\mathcal{I}}$-colliders with order.

Since ${\mathcal{G}}$ and ${\mathcal{H}}$ are maximal, by Lemma \[lem: anterior graphs of interventions\], we know that we have that $${\mathcal{J}}(({\mathcal{G}}^{\mathcal{I}})^\ast) = {\mathcal{J}}({\mathcal{G}}^{\mathcal{I}}) = {\mathcal{J}}({\mathcal{H}}^{\mathcal{I}}) = {\mathcal{J}}(({\mathcal{H}}^{\mathcal{I}})^\ast),$$ and $({\mathcal{G}}^{\mathcal{I}})^\ast$ and $({\mathcal{H}}^{\mathcal{I}})^\ast$ are MAGs. Therefore, $({\mathcal{G}}^{\mathcal{I}})^\ast$ and $({\mathcal{H}}^{\mathcal{I}})^\ast$ are Markov equivalent MAGs, and by @ARS09 [Theorem 3.7], they have the same colliders with order. Suppose now that $\langle i,j,k\rangle$ is an ${\mathcal{I}}$-collider with order $t$ in ${\mathcal{G}}^{\mathcal{I}}$. Then, by Lemma \[lem: I-colliders with order\] there is a discriminating path $\pi = \langle v_0,\ldots, v_m,b,c\rangle$ in ${\mathcal{G}}^{\mathcal{I}}$ for which $\langle i,j,k\rangle \in\{\langle v_m,b,c\rangle ,\langle c,b,v_m\rangle \}$, the subpaths $\langle v_0,v_1,v_2\rangle, \langle v_1,v_2,v_3\rangle, \ldots, \langle v_{m-1},v_m,b\rangle $ are all colliders with order less than or equal to $t$, and $\langle v_0,v_1,v_2\rangle$ is an ${\mathcal{I}}$-v-structure in ${\mathcal{G}}^{\mathcal{I}}$. It follows that $v_0 = \omega_I$ for some $I\in{\mathcal{I}}$ and $v_1\in I$. Moreover, since $\langle v_0,v_1,v_2\rangle$ is a v-structure, the edge in ${\mathcal{G}}^{\mathcal{I}}$ between $v_1$ and $v_2$ is of the form $v_1{ \! \leftarrow\!\!\! \circ  \,}v_2$. Hence, since ${\mathcal{G}}$ is an ancestral graph, it must be that there are no arrows of the form $v_1{ \! \leftarrow\!\!\! \circ  \,}v$ in ${\mathcal{G}}^{\mathcal{I}}$. Therefore, the arrow $v_0\rightarrow v_1$ is also an arrow in $({\mathcal{G}}^{\mathcal{I}})^\ast$. Since the only difference between $({\mathcal{G}}^{\mathcal{I}})^\ast$ and ${\mathcal{G}}^{\mathcal{I}}$ is that some arrows from nodes in $W_{\mathcal{I}}$ are undirected as opposed to directed, it follows that $({\mathcal{G}}^{\mathcal{I}})^\ast$ and ${\mathcal{G}}^{\mathcal{I}}$ have identical discriminating paths.

It follows that if $\langle i,j,k\rangle$ is an ${\mathcal{I}}$-collider with order $t$ in ${\mathcal{G}}^{\mathcal{I}}$, then it is a collider with order in $({\mathcal{G}}^{\mathcal{I}})^\ast$. Since $({\mathcal{G}}^{\mathcal{I}})^\ast$ and $({\mathcal{H}}^{\mathcal{I}})^\ast$ are Markov equivalent MAGs, it follows from @ARS09 [Theorem 3.7] that $\langle i,j,k\rangle$ is also a collider with order in $({\mathcal{H}}^{\mathcal{I}})^\ast$. Since, as we argued above, ${\mathcal{H}}^{\mathcal{I}}$ and $({\mathcal{H}}^{\mathcal{I}})^\ast$ have the same discriminating paths for colliders with order, we know that $\langle i,j,k\rangle$ is a collider with order in ${\mathcal{H}}^{\mathcal{I}}$. Therefore, it only remains to see that $\langle i,j,k\rangle$ is further an ${\mathcal{I}}$-collider with order in ${\mathcal{H}}^{\mathcal{I}}$.

Suppose, on the contrary, that $\langle i,j,k\rangle$ is not an ${\mathcal{I}}$-collider with order in ${\mathcal{H}}^{\mathcal{I}}$. Then $\langle i,j,k\rangle$ is a collider with order determined by a discriminating path that does not use any nodes in $W_{\mathcal{I}}$. Since ${\mathcal{G}}$ and ${\mathcal{H}}$ are Markov equivalent MAGs, it must be that $\langle i,j,k\rangle$ is also a collider with order in ${\mathcal{G}}$. However, this contradicts the assumption that $\langle i,j,k\rangle$ is an ${\mathcal{I}}$-collider with order in ${\mathcal{G}}^{\mathcal{I}}$. Hence, $\langle i,j,k\rangle$ must be a collider with order in ${\mathcal{H}}^{\mathcal{I}}$ determined only by discriminating paths that use at least one node in $W_{\mathcal{I}}$. Hence, $\langle i,j,k\rangle$ is an ${\mathcal{I}}$-collider in ${\mathcal{H}}^{\mathcal{I}}$.

To see the converse, suppose now that ${\mathcal{G}}$ and ${\mathcal{H}}$ are Markov equivalent MAGs and that ${\mathcal{G}}^{\mathcal{I}}$ and ${\mathcal{H}}^{\mathcal{I}}$ have the same ${\mathcal{I}}$-colliders with order. Since ${\mathcal{G}}$ and ${\mathcal{H}}$ are Markov equivalent MAGs, and since ${\mathcal{I}}$ does not doubly-intervene at any selection adjacent nodes in either of ${\mathcal{G}}$ or ${\mathcal{H}}$, then by Lemma \[lem: anterior graphs of interventions\], we know that $${\mathcal{J}}(({\mathcal{G}}^{\mathcal{I}})^\ast) = {\mathcal{J}}({\mathcal{G}}^{\mathcal{I}}),
\qquad
{\mathcal{J}}(({\mathcal{H}}^{\mathcal{I}})^\ast) = {\mathcal{J}}({\mathcal{H}}^{\mathcal{I}}),$$ and that $({\mathcal{G}}^{\mathcal{I}})^\ast$ and $({\mathcal{H}}^{\mathcal{I}})^\ast$ are MAGs. Hence, it suffices to show that ${\mathcal{J}}(({\mathcal{G}}^{\mathcal{I}})^\ast) = {\mathcal{J}}(({\mathcal{H}}^{\mathcal{I}})^\ast)$. Since $({\mathcal{G}}^{\mathcal{I}})^\ast$ and $({\mathcal{H}}^{\mathcal{I}})^\ast$ are MAGs, by @ARS09 [Theorem 3.7], this can be done by showing that they have the same colliders with order.

Since $({\mathcal{G}}^{\mathcal{I}})^\ast$ and ${\mathcal{G}}^{\mathcal{I}}$ differ only by replacing some undirected edges in $({\mathcal{G}}^{\mathcal{I}})^\ast$ of the form $\omega_I - i$ for some $I\in{\mathcal{I}}$ and $i\in I$ with the directed arrows $\omega_I\rightarrow i$, it follows that any discriminating path in $({\mathcal{G}}^{\mathcal{I}})^\ast$ is also a discriminating path in ${\mathcal{G}}^{\mathcal{I}}$. In particular, all colliders with order in $({\mathcal{G}}^{\mathcal{I}})^\ast$ all colliders with order in $({\mathcal{G}}^{\mathcal{I}})^\ast$ are also colliders with order in ${\mathcal{G}}^{\mathcal{I}}$.

Let $\langle i,j,k\rangle$ be a collider with order in $({\mathcal{G}}^{\mathcal{I}})^\ast$. Then it is a collider with order in ${\mathcal{G}}^{\mathcal{I}}$ and hence either a collider with order in ${\mathcal{G}}$ or an ${\mathcal{I}}$-collider with order in ${\mathcal{G}}^{\mathcal{I}}$. In the former case, since ${\mathcal{G}}$ and ${\mathcal{H}}$ are Markov equivalent MAGs, it follows that $\langle i,j,k\rangle$ is also a collider with order in ${\mathcal{H}}$. In the latter case, since ${\mathcal{G}}^{\mathcal{I}}$ and ${\mathcal{H}}^{\mathcal{I}}$ have the same ${\mathcal{I}}$-colliders with order, it follows that $\langle i,j,k\rangle$ is also an ${\mathcal{I}}$-collider with order in ${\mathcal{H}}^{\mathcal{I}}$. Since, as we saw in the proof of the forward direction, any discriminating path for a collider with order in ${\mathcal{H}}^{\mathcal{I}}$ is also a discriminating path for a collider with order in $({\mathcal{H}}^{\mathcal{I}})^\ast$, it follows that $\langle i,j,k\rangle$ is a collider with order in $({\mathcal{H}}^{\mathcal{I}})^\ast$. By symmetry of the argument, it follows that $({\mathcal{G}}^{\mathcal{I}})^\ast$ and $({\mathcal{H}}^{\mathcal{I}})^\ast$ are two MAGs with the same colliders with order. Hence, $({\mathcal{G}}^{\mathcal{I}})^\ast$ and $({\mathcal{H}}^{\mathcal{I}})^\ast$ are Markov equivalent. It follows that $${\mathcal{J}}({\mathcal{G}}^{\mathcal{I}}) = {\mathcal{J}}(({\mathcal{G}}^{\mathcal{I}})^\ast) = {\mathcal{J}}(({\mathcal{H}}^{\mathcal{I}})^\ast) = {\mathcal{J}}({\mathcal{H}}^{\mathcal{I}}),$$ and so ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent, which completes the proof. $\square$

Lemmata and Proofs for Section \[sec: factorization criteria\]
==============================================================

The following lemma demonstrates that the collection ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ constitutes all interventional settings that can arise by intervening at the the targets ${\mathcal{I}}$ in a distribution Markov to an ADMG ${\mathcal{G}}$. Its proof is analogous to that of @YKU18 [Lemma A.1].

\[lem: equating collections\] Suppose $\emptyset\in{\mathcal{I}}$ and ${\mathcal{G}}$ is an ADMG. Then $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ if and only if there exists $f^{(\emptyset)}\in{\mathcal{M}}({\mathcal{G}})$ such that for all $I\in{\mathcal{I}}$, $f^{(I)}$ factorizes according to equation <span> </span>.

Suppose first that there exists an $f^{(\emptyset)}\in{\mathcal{M}}({\mathcal{G}})$ such that for all $I\in{\mathcal{I}}$, $f^{(I)}$ factorizes according to equation <span> </span>. It is then immediate from Theorem \[thm: richardson factorization\] that $f^{(I)}\in{\mathcal{M}}({\mathcal{G}})$ for all $I\in{\mathcal{I}}$. It then remains to check that for all $A\in {\mathcal{A}}({\mathcal{G}})$ that $f^{(I)}(x_H\mid x_{\tail(H)}) = f^{(J)}(x_H \mid x_{\tail(H)})$ for all $H\in[A]_{\mathcal{G}}$ such that $H\cap(I\cup J) = \emptyset$. To see this, note that since $H\cap(I\cup J) = \emptyset$, then $H\cap I = \emptyset$ and $H\cap J = \emptyset$. So by equation <span> </span>, $$f^{(I)}(x_H\mid x_{\tail(H)}) = f^{(\emptyset)}(x_H\mid x_{\tail(H)}) = f^{(J)}(x_H\mid x_{\tail(H)}).$$ Hence, $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$.

Conversely, suppose that $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$. We need to find $f^{(\emptyset)}$ such that $f^{(\emptyset)}\in{\mathcal{M}}({\mathcal{G}})$ and for all $I\in{\mathcal{I}}$, $f^{(I)}$ factorizes according to equation <span> </span>. To this end, for $A\in{\mathcal{A}}({\mathcal{G}})$ and $H\in[A]_{\mathcal{G}}$, pick (if it exists) $I_H\in{\mathcal{I}}$ such that $I_H\cap H = \emptyset$, and set $$f^{(\emptyset)}(x_H\mid x_{\tail(H)}) := f^{(I_H)}(x_H\mid x_{\tail(H)}).$$ Note that this choice is well-defined by the second defining condition of ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ and the fact that this choice is independent of $A$. On the other hand, if no such $I_H$ exists, then set $f^{(\emptyset)}(x_H \mid x_{\tail(H)})$ equal to any strictly positive density. Since this operation is well-defined, we get a distribution with density function $f^{(\emptyset)}$ such that for all $A\in{\mathcal{A}}({\mathcal{G}})$, $$f^{(\emptyset)}(x_A) = \prod_{H\in[A]_{\mathcal{G}}}f^{(\emptyset)}(x_H \mid x_{\tail(H)}).$$ Hence, by Theorem \[thm: richardson factorization\], $f^{(\emptyset)}\in{\mathcal{M}}({\mathcal{G}})$. Moreover, for all $I\in{\mathcal{I}}$ and $A\in {\mathcal{A}}({\mathcal{G}})$, $$\begin{split}
f^{(I)}(x_A)
&= \prod_{H\in[A]_{\mathcal{G}}}f^{(I)}(x_H \mid x_{\tail(H)}), \\
&= \prod_{H\in[A]_{\mathcal{G}}: I\cap H \neq \emptyset}f^{(I)}(x_H \mid x_{\tail(H)})\prod_{H\in[A]_{\mathcal{G}}: I\cap H = \emptyset}f^{(I)}(x_H \mid x_{\tail(H)}),\\
&= \prod_{H\in[A]_{\mathcal{G}}: I\cap H \neq \emptyset}f^{(I)}(x_H \mid x_{\tail(H)})\prod_{H\in[A]_{\mathcal{G}}: I\cap H = \emptyset}f^{(\emptyset)}(x_H \mid x_{\tail(H)}).\\
\end{split}$$ Hence, $f^{(I)}$ factorizes according to equation <span> </span>.

In @YKU18 [Proposition 3.8], the authors showed that for a DAG ${\mathcal{G}}$, if $\emptyset\in{\mathcal{I}}$, then $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$ if and only if $(f^{(I)})_{I\in{\mathcal{I}}}$ satisfies the ${\mathcal{I}}$-Markov property with respect to ${\mathcal{G}}^{\mathcal{I}}$. Key to their proof is to show if $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$, then the conditional factors in $$f^{(I)} = \prod_{i\in[p]}f^{(I)}(x_i\mid x_{\pa_{\mathcal{G}}(i)})$$ can be partitioned in such a way that, upon marginalization and conditioning, we can recover property 2 of Definition \[def: ADMG local I-Markov properties\]. This argument generalizes to ADMGs with the factorization given in Theorem \[thm: richardson factorization\]. However, it requires that we take a few extra steps to account for the fact that the heads $H\in[A]_{\mathcal{G}}$ are no longer necessarily singletons. In particular, we require the following lemma.

\[lem: partitioning\] Suppose $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$, we have two sets $B,C\in[p]$, and $I\in{\mathcal{I}}$ such that $B$ is $m$-separated from $\omega_I$ given $C\cup W_{\mathcal{I}}\setminus\{\omega_I\}$ in ${\mathcal{G}}^{\mathcal{I}}$. Let $A:=\an_{\mathcal{G}}(B\cup C)\in{\mathcal{A}}({\mathcal{G}})$. Let $Z \subset A$ denote all vertices in $A$ that are $m$-connected to $\omega_I$ given $C\cup W_{\mathcal{I}}\setminus\{\omega_I\}$ in ${\mathcal{G}}^{\mathcal{I}}$, and let $B^\prime := A\setminus(Z\cup C)$. Finally, let $$\begin{split}
C^\prime &:=\{ i\in C \mid (\pa_{\mathcal{G}}(i)\cup\sp_{\mathcal{G}}(i))\cap B^\prime\neq\emptyset\}, \mbox{ and}\\
C^{\prime\prime} &:=\{ i\in C \mid (\pa_{\mathcal{G}}(i)\cup\sp_{\mathcal{G}}(i))\cap B^\prime=\emptyset\}.\\
\end{split}$$ Then

1.  No district in ${\mathcal{G}}$ contains both a node of $B^\prime$ and a node of $Z$.

2.  No district in ${\mathcal{G}}$ contains both a node of $C^\prime$ and a node of $Z$.

For statement (1), suppose on the contrary that there exists a district $D\in\dis({\mathcal{G}})$ that contains $z\in Z$ and $b^\prime\in B^\prime$. By definition of a district, since $z,b^\prime\in D$, we know that they are path-connected in ${\mathcal{G}}_{\leftrightarrow}$ by a path consisting of only bidirected arrows. Let $\pi = \langle v_0:=z,v_1,\ldots, v_m:=b^\prime\rangle$ denote such a path. Then since $z\in A\setminus(B\cup C)$, we know that $z$ is ancestral to either some $b\in B$ or $c\in C$. If $z$ is ancestral to $b\in B$, then the directed path from $z$ to $b$ must be blocked by some $c\in C$. This is because, by assumption, every $b\in B$ is $m$-separated from $\omega_I$ given $C\cup W_{\mathcal{I}}\setminus\{\omega_I\}$ in ${\mathcal{G}}^{\mathcal{I}}$. Since $z\notin C$ and $z$ is $m$-connected to $\omega_I$ given $C\cup W_{\mathcal{I}}\setminus\{\omega_I\}$ in ${\mathcal{G}}^{\mathcal{I}}$, concatenating such an $m$-connecting path from $\omega_I$ to $z$ with the directed path from $z$ to $b$ would result in an $m$-connecting path from $\omega_I$ to $b$, which would be a contradiction. Hence, $z$ is ancestral to some $c\in C$, and thus there exists some directed path from $z$ to $c$. Therefore, $v_1$ is $m$-connected to $\omega_I$ given $C\cup W_{\mathcal{I}}\setminus\{\omega_I\}$ in ${\mathcal{G}}^{\mathcal{I}}$. In other words, $v_0,v_1\in Z$. Repeating this argument in an inductive fashion demonstrates that in fact $v_0,\ldots, v_m\in Z$. However, this contradicts the assumption that $b^\prime \in B^\prime$. Thus, no node in $Z$ can be in the same district as a node in $B^\prime$.

To see statement (2) holds, we can use a similar inductive argument. Suppose on the contrary that there is a district $D\in \dis({\mathcal{G}})$ containing a node $z\in Z$ and a node $c^\prime\in C^\prime$. Since $c^\prime$ and $z$ are in $D$, a district in ${\mathcal{G}}$, then they are path-connected by a path $\pi = \langle v_0:=z,v_1,\ldots, v_m:=c^\prime\rangle$ consisting of only bidirected arrows. By the argument for statement (1), we know that $\pi$ is an $m$-connecting path given $C\cup W_{\mathcal{I}}\setminus\{\omega_I,c^\prime\}$. Since $c^\prime\in C^\prime$, then there exists $b^\prime \in B^\prime$ and a path $\pi^\prime = \langle v_0:=z,v_1,\ldots, v_m, b^\prime\rangle$ such that $v_m$ is a collider on $\pi^\prime$. Hence, $\pi^\prime$ is an $m$-connecting path given $C\cup W_{\mathcal{I}}\setminus\{\omega_I\}$ in ${\mathcal{G}}^{\mathcal{I}}$, which contradicts the fact that $b^\prime\in B^\prime$. Hence, a node of $Z$ and a node of $C^\prime$ cannot be in the same district in ${\mathcal{G}}$.

\[rmk: parents of heads\] By a similar argument as in the proof of Lemma \[lem: partitioning\] (see the appendix), we see that the parents of heads $H$ containing elements of $B^\prime$ and/or $C^\prime$ must be contained in $B^\prime\cup C$. Similarly, the parents of heads $H$ containing elements of $Z$ and/or $C^{\prime\prime}$ are contained in $Z\cup C^{\prime\prime}$.

Given Lemma \[lem: partitioning\] and Remark \[rmk: parents of heads\], we can generalize @YKU18 [Proposition 3.8] to ADMGs, as stated in Theorem \[thm: local I-Markov equivalence characterization\].

Proof of Theorem \[thm: local I-Markov equivalence characterization\] 
----------------------------------------------------------------------

Suppose first that $(f^{(I)})_{I\in{\mathcal{I}}}$ satisfies the ${\mathcal{I}}$-Markov property with respect to ${\mathcal{G}}^{\mathcal{I}}$. Since ${\mathcal{G}}$ is an ADMG, then by Theorem \[thm: richardson factorization\] and condition (1) of the ${\mathcal{I}}$-Markov property, we know that for all $A\in[A]_{\mathcal{G}}$ $$\label{eqn: proof factorization}
f^{(I)}(x_A) = \prod_{H\in[A]_{\mathcal{G}}}f^{(I)}(x_H\mid x_{\tail(H)}).$$ Consider now $H\in[A]_{\mathcal{G}}$ for which $H\cap I = \emptyset$. Note that since ${\mathcal{G}}^{\mathcal{I}}$ is also an ADMG, and since $H\cap I = \emptyset$, then $\tail_{{\mathcal{G}}^{\mathcal{I}}}(H) = \tail_{\mathcal{G}}(H)$. Since $\tail_{{\mathcal{G}}^{\mathcal{I}}}(H)$ is the Markov blanket of $H$ in ${\mathcal{G}}^{\mathcal{I}}$ @R09 [Section 3.1], then $\omega_I$ is $m$-separated from $H$ given $\tail_{\mathcal{G}}(H)\cup W_{\mathcal{I}}\setminus \{\omega_I\}$ in ${\mathcal{G}}^{\mathcal{I}}$. So by condition (2) of the ${\mathcal{I}}$-Markov property, we can replace $f^{(I)}(x_H\mid x_{\tail(H)})$ with $f^{(\emptyset)}(x_H\mid x_{\tail(H)})$ in the product in equation <span> </span>. Since this is independent of the choice of $I\in {\mathcal{I}}$, Lemma \[lem: equating collections\] implies that $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$.

Conversely, suppose that $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$. Notice first that since for all $I\in {\mathcal{I}}$, we have $f^{(I)}\in{\mathcal{M}}({\mathcal{G}})$, then $(f^{(I)})_{I\in{\mathcal{I}}}$ satisfies condition (1) of the ${\mathcal{I}}$-Markov property. So it remains to check that $(f^{(I)})_{I\in{\mathcal{I}}}$ satisfies condition (2) of the ${\mathcal{I}}$-Markov property with respect to ${\mathcal{G}}^{\mathcal{I}}$. To this end, assume that $A,B,B^\prime, C,C^\prime, C^{\prime\prime}, Z\subset[p]$ are subsets as specified in Lemma \[lem: partitioning\] and Remark \[rmk: parents of heads\], and set $\hat{{\mathcal{I}}} :=\{\emptyset,I\}$. Note, by Lemma \[lem: partitioning\] and Remark \[rmk: parents of heads\], we can partition $[A]_{\mathcal{G}}$ as $
[A]_{\mathcal{G}}= Q \sqcup Y \sqcup M \sqcup N,
$ where $$\begin{split}
Q &:=\{ H\in [A]_{\mathcal{G}}\mid B^\prime \cap H \neq \emptyset\},\\
Y &:=\{ H\in [A]_{\mathcal{G}}\mid Z \cap H \neq \emptyset\},\\
M &:=\{ H\in [A]_{\mathcal{G}}\mid B^\prime \cap H = \emptyset, C^\prime \cap H \neq \emptyset\}, \text{ and }\\
N &:=\{ H\in [A]_{\mathcal{G}}\mid Z \cap H = \emptyset, C^{\prime\prime} \cap H \neq \emptyset\}.\\
\end{split}$$ By Lemma \[lem: equating collections\], we know that for $\hat{I}\in\hat{{\mathcal{I}}}$, the marginal density $f^{(\hat{I})}(x_A)$ factors according to equation <span> </span>, and so $$\begin{split}
f^{(\hat{I})}(x_A)
&= f^{(\hat{I})}(x_{B^\prime},x_{C^\prime},x_{C^{\prime\prime}},x_Z),\\
&= \prod_{H\in Q}f^{(\hat{I})}(x_H\mid x_{\tail(H)})\prod_{H\in Y}f^{(\hat{I})}(x_H\mid x_{\tail(H)})\\
    &\hspace{1in}\times\prod_{H\in M}f^{(\hat{I})}(x_H\mid x_{\tail(H)})\prod_{H\in N}f^{(\hat{I})}(x_H\mid x_{\tail(H)}),\\
&= \prod_{H\in Q}f^{(\emptyset)}(x_H\mid x_{\tail(H)})\prod_{H\in Y}f^{(\emptyset)}(x_H\mid x_{\tail(H)})\\
&\hspace{1in}\times\prod_{H\in M}f^{(\hat{I})}(x_H\mid x_{\tail(H)})\prod_{H\in N}f^{(\hat{I})}(x_H\mid x_{\tail(H)}),\\
&= g(x_{B^\prime},x_{C^\prime})h(x_Z,x_{C^{\prime\prime}};\hat{I}), 
\end{split}$$ where $g(x_{B^\prime},x_{C^\prime})$ is the product of the conditional factors over $Q$ and $Y$, and $h(x_Z,x_{C^{\prime\prime}};\hat{I})$ is the product of the conditional factors over $M$ and $N$. From this point, we can now use an analogous argument to that used in the proof of Proposition 3.8 in @YKU18. Namely, marginalizing out the variables for nodes in $Z$ and $B^\prime\setminus B$ gives $$f^{(\hat{I})}(x_B,x_C) = \hat{g}(x_B,x_{C^\prime})\hat{h}(x_{C^{\prime\prime}};\hat{I}),$$ where $\hat{g}(x_B,x_{C^\prime}):= \int_{B^\prime\setminus B}g(x_{B^\prime},x_{C^\prime})$ and $\hat{h}(x_{C^{\prime\prime}};\hat{I}) := \int_{Z}h(x_Z,x_{C^{\prime\prime}};\hat{I})$. By conditioning on $C$, it is then straightforward to check that $f^{(\hat{I})}(x_B\mid x_C) = f^{(\emptyset)}(x_B\mid x_C)$ for $\hat{I}\in\hat{{\mathcal{I}}}$. Hence, $(f^{(I)})_{I\in{\mathcal{I}}}$ satisfies condition (2) of the ${\mathcal{I}}$-Markov property, completing the proof. $\square$

Proof of Theorem \[thm: causal alignment\]
------------------------------------------

To prove Theorem \[thm: causal alignment\], we use the following lemma.

@RERS17 [Proposition 4] \[lem: d and m-separation\] Let ${\mathcal{G}}= ([p]\sqcup L,E)$ be a DAG where $[p]\sqcup L$ is a disjoint union. For disjoint subsets $A,B,C\subset [p]$, with $C$ possibly empty, $A$ and $B$ are $d$-separated given $C$ in ${\mathcal{G}}$ if and only if $A$ and $B$ are $m$-separated given $C$ in the latent projection ${\mathcal{G}}([p])$.

Combining Lemma \[lem: d and m-separation\] with our Theorem \[thm: local I-Markov equivalence characterization\], we can prove Theorem \[thm: causal alignment\]:

### Proof of Theorem \[thm: causal alignment\]

By Theorem \[thm: local I-Markov equivalence characterization\], it suffices to show that $(\tilde{f}^{(I)})_{I\in{\mathcal{I}}}$ satisfies the ${\mathcal{I}}$-Markov property with respect to ${\mathcal{G}}^{\mathcal{I}}$. Since $f^{(I)}\in{\mathcal{M}}({\mathcal{G}})$ for all $I\in{\mathcal{I}}$ then $\tilde{f}^{(I)}$ is Markov to ${\mathcal{G}}([p])$ for all $I\in{\mathcal{I}}$ @RS02 [Theorem 7.1]. Hence, $(\tilde{f}^{(I)})_{I\in{\mathcal{I}}}$ satisfies the first condition of the ${\mathcal{I}}$-Markov property stated in Definition \[def: ADMG local I-Markov properties\]. To see that $(\tilde{f}^{(I)})_{I\in{\mathcal{I}}}$ satisfies the second condition, we must show that whenever $C\cup W_{\mathcal{I}}\setminus\{w_I\}$ $m$-separates $B$ and $w_I$ in ${\mathcal{G}}([p])^{\mathcal{I}}$ then $\tilde{f}^{(\emptyset)}(X_B\mid X_C) = \tilde{f}^{(I)}(X_B\mid X_C)$.

To this end, notice first that since $B,C\subset[p]$ we have for all $I\in{\mathcal{I}}$ that $$\begin{split}
f^{(I)}(X_B,X_C) &= \int_{L\cup[p]\setminus(B\cup C)}f^{(I)} = \int_{[p]\setminus(B\cup C)}\int_Lf^{(I)} = \tilde{f}^{(I)}(X_B,X_C),    \\
\end{split}$$ and similarly $f^{(I)}(X_C) = \tilde{f}^{(I)}(X_C)$. It then follows that $$\label{eqn: latent}
f^{(I)}(X_B\mid X_C) = \tilde{f}^{(I)}(X_B\mid X_C)$$ for all $I\in{\mathcal{I}}$. Moreover, since ${\mathcal{G}}^{\mathcal{I}}$ is a DAG and ${\mathcal{G}}^{\mathcal{I}}([p]) = {\mathcal{G}}([p])^{\mathcal{I}}$, then by Lemma \[lem: d and m-separation\] we know that $B$ is $d$-separated from $w_I$ given $C\cup W_{\mathcal{I}}\setminus\{w_I\}$ in ${\mathcal{G}}^{\mathcal{I}}$ if and only if $B$ is $m$-separated from $w_I$ given $C\cup W_{\mathcal{I}}\setminus\{w_I\}$ in ${\mathcal{G}}([p])^{\mathcal{I}}$. Since $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$, it follows from @YKU18 [Proposition 3.8] that $f^{(\emptyset)}(X_B\mid X_C) = f^{(I)}(X_B\mid X_C)$ whenever $B$ is $d$-separated from $w_I$ given $C\cup W_{\mathcal{I}}\setminus\{w_I\}$ in ${\mathcal{G}}^{\mathcal{I}}$. So by Lemma \[lem: d and m-separation\] and <span> </span>, we conclude that $\tilde{f}^{(\emptyset)}(X_B\mid X_C) = \tilde{f}^{(I)}(X_B\mid X_C)$ whenever $B$ is $d$-separated from $w_I$ given $C\cup W_{\mathcal{I}}\setminus\{w_I\}$ in ${\mathcal{G}}([p])^{\mathcal{I}}$. This completes the proof. $\square$

Proof of Theorem \[thm: coincide\]
----------------------------------

The equivalence of $(1)$ and $(2)$ was shown in Theorem \[thm: main\]. So it only remains to show the equivalence of $(1)$ and $(3)$. Suppose first that ${\mathcal{G}}$ and ${\mathcal{H}}$ are ${\mathcal{I}}$-Markov equivalent. Then ${\mathcal{G}}^{\mathcal{I}}$ and ${\mathcal{H}}^{\mathcal{I}}$ have the same set of $m$-separation statements. Hence, by Theorem \[thm: local I-Markov equivalence characterization\], ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$.

Conversely, suppose now that ${\mathcal{G}}$ and ${\mathcal{H}}$ on node set $[p]$ are not ${\mathcal{I}}$-Markov equivalent. It follows that (without loss of generality) there exists an $m$-separation statement $\langle A,B \mid C \rangle \in{\mathcal{J}}({\mathcal{G}}^{\mathcal{I}})$ that is not contained in ${\mathcal{J}}({\mathcal{H}}^{\mathcal{I}})$. By @KJSB19 [Lemma 5], it follows that at least one of the following is true:

1.  There exist $X,Y,Z\subset [p]$ such that $\langle X,Y \mid Z, W_{\mathcal{I}}\rangle \in {\mathcal{J}}({\mathcal{G}}^{\mathcal{I}})$ and $\langle X,Y \mid Z, W_{\mathcal{I}}\rangle\notin{\mathcal{J}}({\mathcal{H}}^{\mathcal{I}})$, and/or

2.  there exist $T,S\subset [p]$ and $\omega_I\in W_{\mathcal{I}}$ such that $\langle \omega_I,T \mid S,W_{\mathcal{I}}\setminus\{\omega_I\}\rangle\in{\mathcal{J}}({\mathcal{G}}^{\mathcal{I}})$ and $\langle \omega_I,T \mid S,W_{\mathcal{I}}\setminus\{\omega_I\}\rangle\notin{\mathcal{J}}({\mathcal{H}}^{\mathcal{I}})$.

It is important to note that, while the augmented graph used by @KJSB19 is different than our ${\mathcal{I}}$-graphs ${\mathcal{G}}^{\mathcal{I}}$, their proof of Lemma $5$ is independent of the choice of nodes augmenting the graph (i.e., the choice for the set $W_{\mathcal{I}}$). Thus, we can readily apply it to our situation here as well. Therefore, we can now assume that the CI relation in question $\langle A,B \mid C \rangle$ is of one of the two forms given in (1) and (2). Now, by Theorem \[thm: local I-Markov equivalence characterization\], since ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) = {\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$ is equivalent to the ${\mathcal{I}}$-Markov property holding, we would like to show that there exists an interventional setting $(f^{(I)})_{I\in{\mathcal{I}}}$ that is ${\mathcal{I}}$-Markov to ${\mathcal{H}}^{\mathcal{I}}$ but not ${\mathcal{I}}$-Markov to ${\mathcal{G}}^{\mathcal{I}}$. To do so, we can use the same construction as in the proof of @KJSB19 [Lemma 4]. For the sake of completeness, we recall some of these details now.

Namely, let us first suppose that we are in case (1), and there is a CI relation $\langle X,Y \mid Z\rangle\in{\mathcal{J}}({\mathcal{G}}^{\mathcal{I}})$ that is not in ${\mathcal{J}}({\mathcal{H}}^{\mathcal{I}})$ and that $X,Y,Z\subset [p]$. Since $W_{\mathcal{I}}$ contains only source nodes, then $\langle X,Y \mid Z\rangle\in{\mathcal{J}}({\mathcal{G}})$ and $\langle X,Y \mid Z\rangle \notin{\mathcal{J}}({\mathcal{H}})$. Since there always exist distributions faithful to a given ancestral graph (see, for instance, @S13), we can pick an observational distribution $f^{(\emptyset)}$ that is faithful to ${\mathcal{H}}$. Any sequence of interventions targeting ${\mathcal{I}}$, say $(f^{(I)})_{I\in{\mathcal{I}}}$, with respect to the observational density $f^{(\emptyset)}$ will then belong to ${\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$ but not ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$. This is because $f^{(\emptyset)}\notin{\mathcal{M}}({\mathcal{G}})$. Hence, ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}}) \neq {\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$.

Suppose now that we are in case (2). Then there exists $T,S\subset [p]$ and $\omega_{\hat{I}}\in W_{\mathcal{I}}$ such that $\langle \omega_{\hat{I}},T \mid S,W_{\mathcal{I}}\setminus\{\omega_{\hat{I}}\}\rangle\in{\mathcal{J}}({\mathcal{G}}^{\mathcal{I}})$ and $\langle \omega_{\hat{I}},T \mid S,W_{\mathcal{I}}\setminus\{\omega_{\hat{I}}\}\rangle\notin{\mathcal{J}}({\mathcal{H}}^{\mathcal{I}})$. In this case, we can use the construction from the proof of @KJSB19 [Lemma 4], which is a natural generalization of the construction used in the proof of @YKU18 [Lemma 3.10]. Here, we refer the reader to the proof of @KJSB19 [Lemma 4] for complete details, and we simply note that it is sufficient to apply their techniques with respect to $I := \hat{I}$ and $J := \emptyset$. The result is an interventional setting $(f^{(I)})_{I\in{\mathcal{I}}}\in{\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$ such that for $\hat{I}\in{\mathcal{I}}$ we have $f^{(\emptyset)}(X\mid Z) \neq f^{(\hat{I})}(X \mid Z)$. Since $\langle \omega_{\hat{I}},T \mid S,W_{\mathcal{I}}\setminus\{\omega_{\hat{I}}\}\rangle\in{\mathcal{J}}({\mathcal{G}}^{\mathcal{I}})$, it follows that $(f^{(I)})_{I\in{\mathcal{I}}}\notin{\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})$. Hence, ${\mathcal{M}}_{\mathcal{I}}({\mathcal{G}})\neq{\mathcal{M}}_{\mathcal{I}}({\mathcal{H}})$, which completes the proof. $\square$

[^1]: As in @YKU18, we treat interventions as parameters instead of random variables so as to avoid problems with faithfulness violations as discussed in @MCM16. To make this distinction in our depictions of ${\mathcal{I}}$-LMGs, we draw nodes corresponding to random variables as open circles containing labels, and we draw interventional nodes in $W_{\mathcal{I}}$ as filled, black circles.

{'source': 'arXiv_out/1911'}