## Formalized Name Verma-Pearl Markov Equivalence Characterization ## Formalized Statement Let $G_1=(V,E_1)$ and $G_2=(V,E_2)$ be directed acyclic graphs on the same finite vertex set $V$, where $E_i\subset V\times V$ and no edge has the form $(v,v)$. For a directed acyclic graph $G=(V,E)$, write $x\sim_G y$ when either $(x,y)\in E$ or $(y,x)\in E$; the skeleton of $G$ is the undirected graph on $V$ with edge set $\{\{x,y\}:x\neq y\text{ and }x\sim_G y\}$. A vertex $u$ is a parent of $v$ in $G$ if $(u,v)\in E$, and a vertex $w$ is a descendant of $v$ if there is a directed path in $G$ from $v$ to $w$, with the path of length zero allowed. An unshielded collider, equivalently a v-structure, is an ordered triple $(a,b,c)$ of distinct vertices such that $a\sim_G b$, $b\sim_G c$, $a\not\sim_G c$, and $(a,b),(c,b)\in E$. A path $(v_0,\dots,v_m)$ in the skeleton of $G$ is d-connecting given $C\subset V$ if every internal noncollider on the path is outside $C$ and every internal collider on the path has a descendant in $C$. Two subsets $A,B\subset V$ are d-separated by $C\subset V$ if there is no d-connecting path given $C$ from a vertex of $A$ to a vertex of $B$. For $i\in\{1,2\}$, let $\mathcal I(G_i)$ be the d-separation model of $G_i$, namely the collection of all triples $(A,B,C)$ of pairwise disjoint subsets of $V$ such that $A$ and $B$ are d-separated by $C$ in $G_i$. Then the following are equivalent: 1. $G_1$ and $G_2$ are Markov equivalent, that is, \begin{align*} \mathcal I(G_1)=\mathcal I(G_2). \end{align*} 2. $G_1$ and $G_2$ have the same skeleton and the same unshielded colliders. Equivalently, $G_1$ and $G_2$ are Markov equivalent if and only if they have the same skeleton and the same v-structures. ## Proof [proofplan] We first show that the d-separation model determines the skeleton: two distinct vertices are adjacent exactly when no conditioning set disjoint from them d-separates them. We then show that the d-separation model determines whether an unshielded triple is a collider by comparing conditioning sets that contain the middle vertex. For the converse, assume the skeletons and unshielded colliders agree, and compare an arbitrary path in the common skeleton under a fixed conditioning set. If the path were active in one graph but inactive in the other, a shortest counterexample contains a triple whose collider status changes; minimality forces that triple to be unshielded, contradicting equality of unshielded colliders. [/proofplan] [step:Fix the path terminology used throughout the proof] For a finite directed acyclic graph $G=(V,E)$, a path means a finite sequence $(v_0,\dots,v_m)$ such that $v_{r-1}\sim_G v_r$ for every $r\in\{1,\dots,m\}$. An internal vertex $v_r$, with $1\leq r\leq m-1$, is a collider on the path if both incident path edges have arrowheads pointing into $v_r$; otherwise it is a noncollider. Given $C\subset V$, the path is d-connecting given $C$ if every internal noncollider is outside $C$ and every internal collider has a descendant in $C$, where a descendant is reached by a directed path of length at least zero. A path that is not d-connecting given $C$ is blocked by $C$. [/step] [step:Recover the skeleton from the d-separation model] Let $G=(V,E)$ be a finite directed acyclic graph. For distinct vertices $x,y\in V$, write $x\sim_G y$ when either $(x,y)\in E$ or $(y,x)\in E$. We claim that \begin{align*} x\sim_G y \end{align*} if and only if there is no subset $C\subset V\setminus\{x,y\}$ such that $x$ and $y$ are d-separated by $C$ in $G$. If $x\sim_G y$, then the one-edge path between $x$ and $y$ has no internal vertices. Hence it has no noncollider in $C$ and no collider whose descendant condition must be checked. Therefore the path is d-connecting given every $C\subset V\setminus\{x,y\}$, so $x$ and $y$ are not d-separated by such a $C$. Conversely, suppose $x$ and $y$ are not adjacent. Since $G$ is acyclic, at least one of $x$ and $y$ is not a descendant of the other. Relabel the two vertices, if necessary, so that $y$ is not a descendant of $x$. Let $\operatorname{pa}_G(x)$ denote the set of parents of $x$ in $G$. Because $x$ and $y$ are not adjacent, $y\notin \operatorname{pa}_G(x)$; also $x\notin \operatorname{pa}_G(x)$ since no edge has the form $(x,x)$. Hence $\operatorname{pa}_G(x)\subset V\setminus\{x,y\}$ is an admissible conditioning set. We prove that $\operatorname{pa}_G(x)$ d-separates $x$ and $y$. Consider any path \begin{align*} \pi=(v_0,\dots,v_m) \end{align*} in the skeleton of $G$ from $v_0=x$ to $v_m=y$. Since $x$ and $y$ are not adjacent, $m\geq 2$. If the first edge on $\pi$ is oriented $v_1\to x$, then $v_1\in \operatorname{pa}_G(x)$ and $v_1$ is a noncollider on $\pi$, because the edge incident to $x$ has an arrowhead pointing into $x$, not into $v_1$. Thus $\pi$ is blocked by $\operatorname{pa}_G(x)$. It remains to consider the case in which the first edge is oriented $x\to v_1$. Since $y$ is not a descendant of $x$, the path cannot be directed all the way from $x$ to $y$. Hence there is a least index $j\in\{1,\dots,m-1\}$ such that the edge between $v_j$ and $v_{j+1}$ is not oriented $v_j\to v_{j+1}$. By minimality, the edge between $v_{j-1}$ and $v_j$ is oriented $v_{j-1}\to v_j$, and the edge between $v_j$ and $v_{j+1}$ is oriented $v_{j+1}\to v_j$. Thus $v_j$ is a collider on $\pi$. The vertices $v_1,\dots,v_j$ are descendants of $x$, while every vertex in $\operatorname{pa}_G(x)$ is a parent of $x$. No parent of $x$ can be a descendant of $x$, because that would form a directed cycle. Moreover, if some descendant $q$ of $v_j$ belonged to $\operatorname{pa}_G(x)$, then the directed segment $x\to v_1\to\cdots\to v_j$, followed by a directed path from $v_j$ to $q$, followed by the edge $q\to x$, would form a directed cycle. Since $G$ is acyclic, $v_j$ has no descendant in $\operatorname{pa}_G(x)$. Thus $\pi$ is blocked by the collider $v_j$. Thus every path from $x$ to $y$ is blocked by $\operatorname{pa}_G(x)$, and $x$ and $y$ are d-separated by $\operatorname{pa}_G(x)$. The claim follows. Therefore equality of d-separation models implies equality of skeletons. [/step] [step:Recover unshielded colliders from the d-separation model] Let $G=(V,E)$ be a finite directed acyclic graph, and let $a,b,c\in V$ be distinct vertices such that $a\sim_G b$, $b\sim_G c$, and $a\not\sim_G c$. We claim that the triple $(a,b,c)$ is an unshielded collider, meaning \begin{align*} a\to b\leftarrow c, \end{align*} if and only if $a$ and $c$ are not d-separated by every conditioning set $C\subset V\setminus\{a,c\}$ containing $b$. First suppose $a\to b\leftarrow c$. For every $C\subset V\setminus\{a,c\}$ with $b\in C$, the path $(a,b,c)$ is d-connecting given $C$: its only internal vertex is $b$, it is a collider, and the collider itself belongs to $C$, hence has a descendant in $C$ by the length-zero directed path from $b$ to itself. Therefore $a$ and $c$ are not d-separated by any such $C$. Conversely, suppose the triple is not a collider. By the skeleton recovery step, since $a$ and $c$ are not adjacent, there exists a set $S\subset V\setminus\{a,c\}$ such that $a$ and $c$ are d-separated by $S$. We prove that $b\in S$. If $b\notin S$, then the length-two path $(a,b,c)$ is d-connecting given $S$: its only internal vertex is $b$, and because the triple is not a collider, $b$ is a noncollider on this path; since $b\notin S$, the noncollider condition is satisfied, and there are no collider conditions to check. This contradicts the fact that $S$ d-separates $a$ and $c$. Hence every separating set $S\subset V\setminus\{a,c\}$ contains $b$, and in particular there exists a separating set containing $b$. This proves the claimed characterization of unshielded colliders. [guided] The goal is to decide whether the middle vertex $b$ is a collider using only which conditioning sets separate $a$ and $c$. Fix distinct vertices $a,b,c\in V$ such that $a$ is adjacent to $b$, $b$ is adjacent to $c$, and $a$ is not adjacent to $c$. Suppose first that the local orientation is \begin{align*} a\to b\leftarrow c. \end{align*} Let $C\subset V\setminus\{a,c\}$ be any conditioning set with $b\in C$. The path $(a,b,c)$ has exactly one internal vertex, namely $b$. Both arrows on the path point into $b$, so $b$ is a collider. A collider is active when it has a descendant in the conditioning set; here $b$ itself is a descendant of $b$ by the directed path of length zero, and $b\in C$. Therefore the path $(a,b,c)$ is d-connecting given $C$. Since one d-connecting path is enough to prevent d-separation, $a$ and $c$ are not d-separated by any conditioning set containing $b$. Now suppose that the local orientation is not a collider. We must prove existence of a separating set that contains $b$; it is not enough to assert that $\{b\}$ works, because other active paths may exist. Instead, use the skeleton characterization already proved. Since $a$ and $c$ are not adjacent, there exists a conditioning set $S\subset V\setminus\{a,c\}$ such that $a$ and $c$ are d-separated by $S$. We show that this particular separating set must contain $b$. Assume for contradiction that $b\notin S$. Then inspect the short path $(a,b,c)$. Its only internal vertex is $b$. Because the triple is not a collider, $b$ is a noncollider on this path. The d-connection rule for a noncollider requires that the noncollider be outside the conditioning set, and this holds because $b\notin S$. There are no internal colliders on the path, so there is no descendant condition to verify. Hence $(a,b,c)$ is d-connecting given $S$, contradicting that $S$ d-separates $a$ and $c$. Thus $b\in S$. We have found a conditioning set $S\subset V\setminus\{a,c\}$ containing $b$ that d-separates $a$ and $c$. Therefore the condition that no conditioning set containing $b$ separates $a$ and $c$ holds exactly in the collider case. [/guided] Consequently, if $\mathcal I(G_1)=\mathcal I(G_2)$, then $G_1$ and $G_2$ have the same skeleton by the preceding step, and every unshielded triple has the same collider status in both graphs. Hence Markov equivalent DAGs have the same skeleton and the same unshielded colliders. [/step] [step:Compare separations using the moralized ancestral graph criterion] Assume now that $G_1$ and $G_2$ have the same skeleton and the same unshielded colliders. Let $A,B,C\subset V$ be pairwise disjoint. We compare d-separation through the [Moralized Ancestral Graph Criterion][citetheorem:TEMP-18], applied separately to $G_1$ and $G_2$. Its hypotheses hold because each $G_i$ is a directed acyclic graph and $A,B,C$ are pairwise disjoint. For $i\in\{1,2\}$, define \begin{align*} W_i:=\operatorname{An}_{G_i}(A\cup B\cup C), \end{align*} where $\operatorname{An}_{G_i}(R)$ denotes the set of vertices having a directed path to some vertex of $R$, with paths of length zero allowed. Let $H_i$ be the moral graph of the induced sub-DAG $G_i[W_i]$: thus $H_i$ has the undirected skeleton edges of $G_i[W_i]$ and, for each pair of distinct parents of a common child in $W_i$, an additional undirected edge joining those parents. We claim that, for every $A,B,C$, the undirected separation of $A$ and $B$ by $C$ in $H_1$ is equivalent to the undirected separation of $A$ and $B$ by $C$ in $H_2$. Indeed, an undirected path in $H_i$ from $A$ to $B$ avoiding $C$ can be expanded into a path in the common skeleton whose nonconsecutive shortcuts are exactly moral edges. Each moral edge records a collider pattern $p\to q\leftarrow r$ with $q\in W_i$ and $p,r\in W_i$. If $p$ and $r$ are nonadjacent in the common skeleton, this is an unshielded collider, so the same moral edge is present in the other graph by hypothesis. If $p$ and $r$ are adjacent in the common skeleton, the moral edge can be replaced by the ordinary skeleton edge $p-r$, which is present in both graphs. Since $q\in W_i$, there is a directed path from $q$ to some vertex of $A\cup B\cup C$; if that terminal vertex lies in $A\cup B$, truncate at the first point where the expanded route reaches $A\cup B$, and if it lies in $C$, the collider is activated by a descendant in $C$. Thus every moralized route avoiding $C$ corresponds to a d-connecting route given $C$ in the original DAG, and the same reconstruction uses only common skeleton edges and common unshielded colliders. Applying the same argument with $G_1$ and $G_2$ interchanged gives equality of the undirected separation relation in $H_1$ and $H_2$. By the Moralized Ancestral Graph Criterion, $A$ and $B$ are d-separated by $C$ in $G_i$ if and only if $C$ separates $A$ and $B$ in $H_i$. The preceding paragraph shows that this undirected separation statement has the same truth value for $i=1$ and $i=2$. Hence $A$ and $B$ are d-separated by $C$ in $G_1$ if and only if they are d-separated by $C$ in $G_2$. [/step] [step:Conclude equality of the d-separation models] Let $A,B,C\subset V$ be pairwise disjoint. By definition, $A$ and $B$ are d-separated by $C$ in $G_i$ if and only if there is no d-connecting path given $C$ in $G_i$ from any vertex of $A$ to any vertex of $B$. The preceding step proves that, for every pair of endpoint sets and every conditioning set $C$, the d-separation relation has the same truth value in $G_1$ and $G_2$. Hence \begin{align*} (A,B,C)\in \mathcal I(G_1) \end{align*} if and only if \begin{align*} (A,B,C)\in \mathcal I(G_2). \end{align*} Since the triple $(A,B,C)$ was arbitrary, $\mathcal I(G_1)=\mathcal I(G_2)$. Combining this converse implication with the skeleton and unshielded-collider recovery proved above establishes the equivalence. Since a v-structure is precisely an unshielded collider, the final equivalent formulation follows as well. [/step]