## Formalized Name Moralized Ancestral Graph Criterion ## Formalized Statement Let $G=(V,E)$ be a directed acyclic graph, and let $A,B,Z\subset V$ be pairwise disjoint vertex sets. Let \begin{align*} W:=\operatorname{An}_G(A\cup B\cup Z) \end{align*} be the set of all vertices of $G$ that are ancestors of at least one vertex in $A\cup B\cup Z$, where each vertex is counted as its own ancestor. Let $G_W$ be the induced sub-DAG of $G$ on $W$, and let $H$ be the moral graph of $G_W$: thus $H$ is the undirected graph on vertex set $W$ in which two distinct vertices are adjacent if they are adjacent by a directed edge in $G_W$, or if they are both parents in $G_W$ of some common child in $G_W$. In this statement, $Z$ d-separates $A$ and $B$ in $G$ means that there is no $Z$-active route in $G$ with one endpoint in $A$ and the other endpoint in $B$, where a route is a finite vertex sequence following directed edges without regard to orientation, non-endpoint colliders have both adjacent arrowheads pointing into the vertex, non-endpoint non-colliders must avoid $Z$, and non-endpoint colliders must have a directed descendant in $Z$. Then $Z$ d-separates $A$ and $B$ in $G$ if and only if $Z$ separates $A$ and $B$ in $H$, meaning that every undirected path in $H$ with one endpoint in $A$ and the other endpoint in $B$ contains at least one vertex of $Z$. ## Proof [proofplan] We prove the equivalent contrapositive in both directions. A $Z$-active route in the DAG becomes an undirected walk in the moralized ancestral graph; vertices of $Z$ that occur on it are colliders and can be bypassed by moral edges between their parents, after which loop erasure gives a path avoiding $Z$. Conversely, from an undirected path in the moral graph avoiding $Z$, we invoke the standard route-lifting lemma for moralized ancestral graphs, prove the lemma in the precise form needed, and obtain a $Z$-active route in the original DAG. The two contrapositive implications are exactly the desired equivalence. [/proofplan] [step:Fix the route and path conventions] A route in $G$ is a finite sequence \begin{align*} \gamma=(v_0,v_1,\dots,v_m) \end{align*} of vertices in $V$ such that, for every $i\in\{0,\dots,m-1\}$, either $(v_i,v_{i+1})\in E$ or $(v_{i+1},v_i)\in E$. Repetitions of vertices and edges are allowed. A non-endpoint occurrence $v_i$, with $1\le i\le m-1$, is a collider on $\gamma$ if \begin{align*} (v_{i-1},v_i)\in E \end{align*} and \begin{align*} (v_{i+1},v_i)\in E. \end{align*} It is a non-collider otherwise. The route is $Z$-active if every non-collider occurrence is outside $Z$ and every collider occurrence has a directed descendant in $Z$, where a vertex is its own descendant. An undirected path in $H$ is a finite sequence of distinct vertices \begin{align*} \rho=(w_0,w_1,\dots,w_r) \end{align*} such that $\{w_i,w_{i+1}\}$ is an edge of $H$ for every $i\in\{0,\dots,r-1\}$. Thus $Z$ separates $A$ and $B$ in $H$ exactly when there is no such path with $w_0\in A$, $w_r\in B$, and $w_i\notin Z$ for all $i$. [/step] [step:Convert a $Z$-active route into a moral path avoiding $Z$] Assume that $Z$ does not d-separate $A$ and $B$ in $G$. Then there is a $Z$-active route \begin{align*} \gamma=(v_0,v_1,\dots,v_m) \end{align*} with $v_0\in A$ and $v_m\in B$. We first show that every vertex of $\gamma$ lies in $W$. The endpoints lie in $A\cup B\subset A\cup B\cup Z$, hence in $W$. If an interior occurrence $v_i$ is a collider, $Z$-activity gives a directed path from $v_i$ to a vertex of $Z$, so $v_i\in W$. If $v_i$ is a non-collider, at least one adjacent edge on the route has tail at $v_i$. Follow the route from $v_i$ in that outward arrow direction as long as the route continues along directed arrows. This directed segment either reaches an endpoint in $A\cup B$ or stops at the first later occurrence where the next edge points into the current vertex, which is a collider. In the latter case, that collider has a directed descendant in $Z$. Hence $v_i$ is an ancestor of a vertex of $A\cup B\cup Z$, and $v_i\in W$. Since all vertices of $\gamma$ lie in $W$, every adjacent pair of vertices in $\gamma$ is adjacent in the skeleton of $G_W$, hence adjacent in $H$. Thus $\gamma$ is an undirected walk in $H$ from $A$ to $B$. We remove every interior occurrence of a vertex of $Z$ from this walk. Let $v_i\in Z$ with $0<i<m$. Since $A$, $B$, and $Z$ are pairwise disjoint, this occurrence is not an endpoint. Since non-colliders on a $Z$-active route avoid $Z$, the occurrence $v_i$ is a collider. Therefore $v_{i-1}$ and $v_{i+1}$ are parents in $G_W$ of the common child $v_i$. If $v_{i-1}=v_{i+1}$, replace the segment $(v_{i-1},v_i,v_{i+1})$ by the single vertex $v_{i-1}$. If $v_{i-1}\ne v_{i+1}$, the moralization rule gives the edge $\{v_{i-1},v_{i+1}\}$ in $H$, and we replace that segment by this one edge. Each replacement preserves an undirected walk from $A$ to $B$ and removes one occurrence of a vertex of $Z$. Since the original route is finite, after finitely many replacements we obtain an undirected walk in $H$ from $A$ to $B$ whose vertices avoid $Z$. Finally erase closed subwalks: whenever a vertex appears more than once, delete the segment between its first and last occurrence. This preserves the endpoints and cannot introduce a vertex of $Z$. Repeating this finite deletion procedure gives an undirected path in $H$ from $A$ to $B$ avoiding $Z$. Therefore $Z$ does not separate $A$ and $B$ in $H$. [guided] Assume that $Z$ does not d-separate $A$ and $B$ in $G$. By the definition fixed in the theorem statement, there is a $Z$-active route \begin{align*} \gamma=(v_0,v_1,\dots,v_m) \end{align*} with $v_0\in A$ and $v_m\in B$. The moral graph $H$ is built only on the ancestral vertex set $W$, so the first point is to prove that the active route stays inside $W$. The endpoints are immediate: $v_0\in A$ and $v_m\in B$, so both lie in $A\cup B\cup Z$ and hence in $W$. If an interior occurrence $v_i$ is a collider, activity gives a directed path from $v_i$ to a vertex of $Z$. Thus $v_i$ is an ancestor of a vertex of $Z$, so $v_i\in W$. Now let $v_i$ be a non-collider occurrence. Since it is not a collider, the two adjacent route edges are not both directed into $v_i$. Hence at least one adjacent edge has tail at $v_i$. Choose such an edge and follow the route in the direction in which this edge points away from $v_i$. Continue along the route as long as the route edges form a directed path away from $v_i$. The directed segment either reaches an endpoint of $\gamma$, which lies in $A\cup B$, or it stops because the next route edge points into the current vertex. At that stopping point the previous edge also points into the current vertex, so the stopping occurrence is a collider. Since the route is active, that collider has a directed descendant in $Z$. In both cases, $v_i$ is an ancestor of a vertex of $A\cup B\cup Z$. Hence every vertex of $\gamma$ lies in $W$. Because every adjacent pair in $\gamma$ is joined by a directed edge of $G$ and both vertices lie in $W$, the same pair is joined by an edge in the skeleton of $G_W$. The moral graph $H$ contains every skeleton edge of $G_W$, so \begin{align*} (v_0,v_1,\dots,v_m) \end{align*} is an undirected walk in $H$ from a vertex of $A$ to a vertex of $B$. It remains to remove vertices of $Z$. Let $v_i\in Z$ be an interior occurrence. Because $A$, $B$, and $Z$ are pairwise disjoint, an endpoint of the route cannot lie in $Z$, so this occurrence is genuinely interior. A non-collider on an active route must avoid $Z$, so $v_i$ must be a collider. Thus the local directed pattern is \begin{align*} v_{i-1}\to v_i\leftarrow v_{i+1}. \end{align*} Both neighbours are parents of the common child $v_i$ inside $G_W$. If the two neighbours coincide, the segment $(v_{i-1},v_i,v_{i+1})$ is a closed two-edge detour and can be replaced by the single vertex $v_{i-1}$. If the neighbours are distinct, the moralization rule adds the undirected edge $\{v_{i-1},v_{i+1}\}$ to $H$, so the same segment can be replaced by that edge. In either case the walk remains connected from its original start in $A$ to its original end in $B$, and one occurrence of a vertex of $Z$ has been deleted. The route has finitely many entries, so finitely many such deletions remove all occurrences of $Z$. The resulting object may still repeat vertices, so it is a walk rather than a path. If a vertex appears twice, delete the closed subwalk between its first and last appearances. The endpoints remain the original endpoint in $A$ and the original endpoint in $B$, and no vertex of $Z$ is introduced because deletion only removes vertices. After finitely many loop erasures no vertex repeats, giving an undirected path in $H$ from $A$ to $B$ avoiding $Z$. Thus $Z$ does not separate $A$ and $B$ in $H$. [/guided] [/step] [step:Lift a moral path avoiding $Z$ to an active route] We use the following standard route-lifting lemma for moralized ancestral graphs. [claim:Moral path lifting lemma] Let $D$ be a directed acyclic graph, let $S$ and $T$ be disjoint vertex sets, and let $C$ be a vertex set disjoint from $S\cup T$. Let \begin{align*} U=\operatorname{An}_D(S\cup T\cup C) \end{align*} and let $M$ be the moral graph of the induced sub-DAG $D_U$. If there is an undirected path in $M$ from $S$ to $T$ whose vertices avoid $C$, then there is a $C$-active route in $D$ from $S$ to $T$. [/claim] [proof] Choose, among all undirected paths in $M$ from $S$ to $T$ avoiding $C$, a path \begin{align*} \rho=(w_0,w_1,\dots,w_r) \end{align*} with minimal length $r$. Thus $w_0\in S$, $w_r\in T$, and $w_i\notin C$ for all $i$. For each $i\in\{0,\dots,r-1\}$, choose a route segment $\sigma_i$ in $D_U$ from $w_i$ to $w_{i+1}$ as follows. If $w_i$ and $w_{i+1}$ are adjacent by a directed edge in $D_U$, let $\sigma_i$ be that one-edge segment. Otherwise, by the definition of moralization, there is a vertex $c_i\in U$ such that \begin{align*} (w_i,c_i)\in E(D) \end{align*} and \begin{align*} (w_{i+1},c_i)\in E(D). \end{align*} Choose one such $c_i$ and set \begin{align*} \sigma_i=(w_i,c_i,w_{i+1}). \end{align*} Concatenating the segments $\sigma_0,\dots,\sigma_{r-1}$ gives a route $\omega$ in $D_U$ from $S$ to $T$. We prove that every collider occurrence on $\omega$ has a descendant in $C$. Let $x$ be a collider occurrence on $\omega$. Since $x\in U$, there is a directed path in $D$ from $x$ to some vertex of $S\cup T\cup C$. Choose such a path \begin{align*} \delta=(x=d_0,d_1,\dots,d_s=d) \end{align*} whose terminal vertex $d$ is the first vertex on the path lying in $S\cup T\cup C$. Suppose, for contradiction, that $x$ has no descendant in $C$. Then $d\notin C$, so $d\in S\cup T$. If $d\in S$, then the first vertex of $\rho$ is $w_0\in S$ and $d\in S$. Since $x$ is a collider occurrence in the concatenated route, the two neighbouring vertices of $\omega$ at that occurrence are both parents of $x$ in $D_U$; call them $p$ and $q$, with $p$ appearing before $x$ and $q$ appearing after $x$ along $\omega$. The directed edge from $x$ to $d_1$ shows that $x$ is a child of $p$ and $q$ and an ancestor of $d\in S$. Hence $p$ and $q$ are ancestors of a vertex of $S$, so all vertices on the directed path from $x$ to $d$ lie in $U$. In the moral graph $M$, each consecutive pair on the directed path from $x$ to $d$ is adjacent after forgetting orientation. Also $p$ is adjacent to $q$ in $M$ because they are parents of the common child $x$. Replacing the initial part of $\rho$ from $w_0$ up to the occurrence corresponding to $p$ by the reversed directed path from $d\in S$ to $x$ followed by the edge from $x$ to $q$, and then continuing along the remaining part of $\rho$, gives an undirected walk in $M$ from $S$ to $T$. The interior vertices of the directed path from $x$ to $d$ avoid $S\cup T\cup C$ by the first-hit choice of $d$, and the original path avoids $C$. Thus this walk avoids $C$. Erasing closed subwalks gives an undirected path from $S$ to $T$ avoiding $C$ that is strictly shorter than $\rho$, because it omits at least the nonempty initial segment ending at $p$. This contradicts the minimality of $\rho$. The case $d\in T$ is symmetric in the direction of the path: replace the terminal part of $\rho$ beginning after $q$ by the directed path from $x$ to $d\in T$, with the edge from $p$ to $x$ used to reach that path. The same first-hit argument shows that the replacement walk avoids $C$, and loop erasure gives a strictly shorter $S$-$T$ path avoiding $C$, again contradicting minimality. Therefore every collider occurrence on $\omega$ has a descendant in $C$. It remains to check non-colliders. The only possible vertices of $\omega$ not already on $\rho$ are the inserted common children $c_i$. Such an inserted vertex occurs inside a segment \begin{align*} w_i\to c_i\leftarrow w_{i+1}, \end{align*} so it is a collider, not a non-collider. Hence every non-collider occurrence of $\omega$ is one of the path vertices $w_i$, and all these vertices avoid $C$ by construction. Thus $\omega$ is a $C$-active route in $D$ from $S$ to $T$. [/proof] Apply the lemma with $D=G$, $S=A$, $T=B$, and $C=Z$. The hypotheses match the present construction: $W=\operatorname{An}_G(A\cup B\cup Z)$, $H$ is the moral graph of $G_W$, and we assume an $H$-path from $A$ to $B$ avoiding $Z$. Therefore there is a $Z$-active route in $G$ from $A$ to $B$. [guided] Assume that $Z$ does not separate $A$ and $B$ in $H$. Then there is an undirected path \begin{align*} \rho=(w_0,w_1,\dots,w_r) \end{align*} in $H$ such that $w_0\in A$, $w_r\in B$, and $w_i\notin Z$ for every $i$. We use the standard moral path lifting argument, but we spell out the exact form needed. Choose $\rho$ to have minimal length among all $H$-paths from $A$ to $B$ avoiding $Z$. For each edge $\{w_i,w_{i+1}\}$ of $\rho$, there are two possible reasons it is present in the moral graph. If $w_i$ and $w_{i+1}$ are adjacent by a directed edge in $G_W$, use that one edge as a route segment. If the edge is purely moral, then there is a common child $c_i\in W$ with \begin{align*} w_i\to c_i\leftarrow w_{i+1}. \end{align*} In that case replace the moral edge by the two-edge route segment $(w_i,c_i,w_{i+1})$. Concatenating these choices gives a route $\omega$ in the skeleton of $G_W$ from $A$ to $B$. The only issue is collider activation. Non-colliders are harmless: the only inserted vertices are common children in patterns $w_i\to c_i\leftarrow w_{i+1}$, so inserted vertices are colliders. Therefore every non-collider occurrence of $\omega$ is one of the original path vertices $w_i$, and those vertices avoid $Z$ by assumption. Now let $x$ be a collider occurrence of $\omega$. Because $x\in W=\operatorname{An}_G(A\cup B\cup Z)$, there is a directed path from $x$ to $A\cup B\cup Z$. Choose such a path \begin{align*} \delta=(x=d_0,d_1,\dots,d_s=d) \end{align*} and stop at the first vertex $d$ lying in $A\cup B\cup Z$. If $d\in Z$, then $x$ has a descendant in $Z$, and this collider is active. The only dangerous alternatives are $d\in A$ and $d\in B$. Suppose first that $d\in A$. Since $x$ is a collider occurrence in $\omega$, its two neighbouring route vertices at that occurrence are parents of $x$; call them $p$ and $q$, with $p$ before $x$ and $q$ after $x$ along the route. The path from $x$ to $d\in A$ stays inside the ancestral set $W$, and its interior vertices avoid $A\cup B\cup Z$ by the first-hit choice of $d$. In the moral graph, directed edges become undirected edges, so the reversed sequence from $d$ to $x$ is an undirected path segment in $H$. Also $x$ is adjacent to $q$ because $q$ is a parent of $x$. Thus we can start at the vertex $d\in A$, follow the reversed directed path to $x$, move to $q$, and then continue along the old moral path from the position after the collider. This is an undirected walk from $A$ to $B$ avoiding $Z$. This replacement omits the original nonempty initial part of the minimal path that led to the parent $p$. After erasing any closed subwalks, we get an undirected path from $A$ to $B$ avoiding $Z$ that is strictly shorter than the chosen minimal path $\rho$. That is impossible. Hence the first hit $d$ cannot lie in $A$. The case $d\in B$ is the same argument applied to the terminal side. If the directed path from $x$ first reaches a vertex of $B$, then we keep the initial part of $\rho$ up to the parent before the collider, move through $x$, and then follow the directed path from $x$ to $d\in B$. The first-hit condition again keeps the replacement away from $Z$, and loop erasure produces a strictly shorter $A$-$B$ path in $H$ avoiding $Z$, contradicting minimality. Thus $d$ cannot lie in $B$ either. The only remaining possibility is $d\in Z$. Therefore every collider occurrence of $\omega$ has a directed descendant in $Z$. We have already checked that every non-collider occurrence avoids $Z$. Hence $\omega$ is a $Z$-active route in $G$ from $A$ to $B$. [/guided] [/step] [step:Take contrapositives to conclude the equivalence] The second step proved \begin{align*} \text{there exists a } Z\text{-active route from }A\text{ to }B\text{ in }G \implies \text{there exists an }H\text{-path from }A\text{ to }B\text{ avoiding }Z. \end{align*} The third step proved \begin{align*} \text{there exists an }H\text{-path from }A\text{ to }B\text{ avoiding }Z \implies \text{there exists a } Z\text{-active route from }A\text{ to }B\text{ in }G. \end{align*} Taking contrapositives gives that there is no $Z$-active route from $A$ to $B$ in $G$ if and only if there is no undirected path from $A$ to $B$ in $H$ avoiding $Z$. By the definitions of d-separation and undirected separation fixed in the statement, this says exactly that $Z$ d-separates $A$ and $B$ in $G$ if and only if $Z$ separates $A$ and $B$ in the moralized ancestral graph $H$. [/step]