Distinct positive minimal ANM DAGs contain a conditionally reversible edge

Use the Borel noise densities supplied in the hypotheses, or choose their positive finite Borel versions under Countable Choice by [F1]. Repeatedly delete a vertex that is a sink in both graphs and has the same parent set in both. At each deletion, its equation contributes a single shifted noise-density factor, which integrates to one by [F7]; no remaining equation uses the deleted vertex, so the remaining law still has the positive ANM product density and all remaining edges remain causally minimal. The process cannot delete every vertex, since then the graphs would be equal. It stops only when no common sink with equal parent sets remains; therefore choose a remaining sink $l$ of $G$, which either has a different parent set in $G^{\mathrm{\prime }}$ or has a child in $G^{\mathrm{\prime }}$.

Partition the incident vertices by $Z={\mathrm{pa}}_G(l)\cap {\mathrm{pa}}_{G^{\mathrm{\prime }}}(l)$, $Y={\mathrm{pa}}_G(l)\cap {\mathrm{ch}}_{G^{\mathrm{\prime }}}(l)$, $W={\mathrm{pa}}_G(l)\setminus (Z\cup Y)$, $D={\mathrm{pa}}_{G^{\mathrm{\prime }}}(l)\setminus {\mathrm{pa}}_G(l)$, and $E={\mathrm{ch}}_{G^{\mathrm{\prime }}}(l)\setminus {\mathrm{pa}}_G(l)$. These sets are pairwise disjoint, ${\mathrm{pa}}_G(l)=Z\cup Y\cup W$, ${\mathrm{pa}}_{G^{\mathrm{\prime }}}(l)=Z\cup D$, and ${\mathrm{ch}}_{G^{\mathrm{\prime }}}(l)=Y\cup E$. Put $T=Y\cup W$.

Suppose $T=\mathrm{\varnothing }$ and $D\mathrm{\ne }\mathrm{\varnothing }$, and choose $d\in D$. Since $l$ is a sink in $G$, all vertices in $D\cup Z$ are nondescendants of $l$. By [F2], $N_l$ is independent of $(X_D,X_Z)$; the equation $X_l=f_l(X_Z)+N_l$ therefore makes the conditional density of $X_l$ given $(X_D,X_Z)$ independent of $X_D$. Its density factorization gives $X_l{\perp }_d{X}_D\mid X_Z$. Weak union follows directly by writing this factorization for the split $D=\{d\}\cup (D\setminus \{d\})$ and dividing by the positive marginal density: $X_l{\perp }_d{X}_d\mid X_{Z\cup (D\setminus \{d\})}$. This conditioning set contains all other parents of $l$ in $G^{\mathrm{\prime }}$ and contains no descendant of $l$ there, contradicting [F3] for $d\to l$ in $G^{\mathrm{\prime }}$.

Suppose $T=D=\mathrm{\varnothing }$ and $E\mathrm{\ne }\mathrm{\varnothing }$. Choose $e\in E$ and put $R={\mathrm{pa}}_{G^{\mathrm{\prime }}}(e)\setminus \{l\}$. Since $l$ is a sink in $G$, every vertex of $\{e\}\cup Z\cup R$ is a nondescendant of $l$. By [F2], $N_l$ is independent of $(X_e,X_R,X_Z)$; hence the conditional density of $X_l$ given these variables depends only on $X_Z$. Splitting off $X_e$ and dividing by the positive marginal density gives $X_l{\perp }_d{X}_e\mid X_{Z\cup R}$. In $G^{\mathrm{\prime }}$, $l\to e$, the set $Z\cup R$ contains all other parents of $e$, and each $z\in Z$ is an ancestor of $e$ along $z\to l\to e$, so this set contains no descendant of $e$. This contradicts [F3] for $l\to e$. If also $E=\mathrm{\varnothing }$, then $l$ is a common sink with the same parent set and would have been deleted in step 1.1.

It remains that $T\mathrm{\ne }\mathrm{\varnothing }$. Choose $t\in T$ with no directed path in $G^{\mathrm{\prime }}$ from $t$ to any other member of $T$; such a vertex exists by taking a maximal element of the directed-reachability partial order on the finite nonempty set $T$. We show that $t\mathrm{\notin }W$. For contradiction suppose $t=w\in W$, and form ${\tilde{G}}^{\mathrm{\prime }}$ by adding arrows $y^{\mathrm{\prime }}\to w$ for all $y^{\mathrm{\prime }}\in Y$ and $w^{\mathrm{\prime }}\to w$ for all $w^{\mathrm{\prime }}\in W\setminus \{w\}$. The graph is still acyclic: a new arrow could create a cycle only if $w$ already reached its tail, contrary to the choice of $w$. Also $l$ and $w$ are nonadjacent in ${\tilde{G}}^{\mathrm{\prime }}$.

In ${\tilde{G}}^{\mathrm{\prime }}$, choose a d-separating set $S_0$ for the nonadjacent vertices $l,w$ as follows. For any vertex $v$ and nondescendant nonparent $u$, its parent set d-separates $v$ from $u$: a path starting $v\leftarrow a$ is blocked by the conditioned noncollider $a$; a path starting with an arrow out of $v$ must have a first edge traversed backward, since $u$ is not a descendant. At that first turn there is a collider reached by a directed path from $v$. Neither this collider nor any of its descendants can be a parent of $v$, since that would give a directed cycle; thus it is blocked given the parents of $v$. If $l$ is an ancestor of $w$, then $l$ is a nondescendant nonparent of $w$; apply this argument from $w$ and take $S_0={\mathrm{pa}}_{{\tilde{G}}^{\mathrm{\prime }}}(w)$. It covers paths through a child of $w$ as well as paths through a parent. Otherwise $w$ is a nondescendant nonparent of $l$; take $S_0={\mathrm{pa}}_{{\tilde{G}}^{\mathrm{\prime }}}(l)$.

Put $W_0=W\setminus \{w\}$ and $S=S_0\cup Y\cup Z\cup W_0$. Each $y^{\mathrm{\prime }}\in Y$ belongs to $S_0$, since $l\to y^{\mathrm{\prime }}\to w$ is a path with noncollider $y^{\mathrm{\prime }}$. Suppose a path $\pi$ from $l$ to $w$ is active given $S$. Its noncolliders lie outside $S_0$, and every collider with a descendant in $S_0$ is active given $S_0$. Since $S_0$ d-separates the endpoints, at least one collider on $\pi$ is not an ancestor of $S_0$; its descendant in $S$ must lie in $Z$ or $W_0$. Label every such collider by one such type, $Z$ or $W_0$. A labeled $Z$-collider $v$ has a directed path to some $z\in Z$, followed by $z\to l$; traversing this chain backward connects $l$ to $v$. The chain avoids $S_0$, since otherwise $v$ would be an ancestor of $S_0$. A labeled $W_0$-collider $u$ has a directed path to some $w^{\mathrm{\prime }}\in W_0$, followed by the added arrow $w^{\mathrm{\prime }}\to w$; this chain also avoids $S_0$. If only $Z$ labels occur, use the one nearest $w$, replace the prefix of $\pi$ by its backward chain from $l$, and retain the suffix. If only $W_0$ labels occur, use the one nearest $l$, retain the prefix, and replace the suffix by its forward chain to $w$. If both labels occur, take consecutive labeled colliders of different types; connect $l$ to the $Z$-collider by its backward chain, retain the segment between the two colliders in either direction, and connect the $W_0$-collider to $w$ by its forward chain. The resulting finite route has no conditioned noncollider: original noncolliders avoid $S_0$, connector interiors avoid $S_0$, and each selected collider becomes a noncollider at its junction. Every remaining collider has a descendant in $S_0$, because there is no differently labeled collider between the selected ones, and in the one-label cases the retained side contains no other newly opened collider. This is an active route given $S_0$, so [F5] gives an active path, contradicting the choice of $S_0$. Thus $S$ d-separates $l,w$ in ${\tilde{G}}^{\mathrm{\prime }}$, and also in its subgraph $G^{\mathrm{\prime }}$.

By [F6], $X_l{\perp }_d{X}_w\mid X_S$ in $G^{\mathrm{\prime }}$. In $G$, $w\to l$, and $S$ contains all other parents of $l$ and only nondescendants of the sink $l$. This contradicts [F3]. Therefore the selected maximal member $t$ cannot lie in $W$; it lies in $Y$.

Let the selected $y=t\in Y$, and set $Q={\mathrm{pa}}_G(l)\setminus \{y\}$, $R={\mathrm{pa}}_{G^{\mathrm{\prime }}}(y)\setminus \{l\}$, and $S=Q\cup R$. In $G$, $l$ is a sink, so every member of $S$ is a nondescendant of $l$, and $Q\subseteq S$. In $G^{\mathrm{\prime }}$, every member of $R$ is a parent of $y$. A vertex $z\in Z$ cannot be a descendant of $y$, since $z\to l\to y$ and a path $y\to \cdots \to z$ would create a directed cycle. Every vertex of $Y\setminus \{y\}\cup W$ is another member of $T$, so none is a descendant of $y$ by the choice of $t$. Hence $S$ is contained in the nondescendants of $y$ in $G^{\mathrm{\prime }}$ and contains all parents of $y$ other than $l$. A vertex deleted in step 1.1 cannot be an ancestor of a surviving vertex in either original graph: when it was deleted it had no outgoing edge to any then-remaining vertex. Consequently all original parents of surviving vertices survive, and every original directed path between surviving vertices stays in the reduced graph. The parent sets and nondescendant inclusions just proved therefore hold in the original graphs too. The edges are $y\to l$ in $G$ and $l\to y$ in $G^{\mathrm{\prime }}$, so the vertices and $S$ satisfy the Statement.