Population identifiability and RESIT correctness for restricted ANMs

Suppose another causally minimal restricted ANM on the same vertices gives the same observational law but has a different DAG $G^{\mathrm{\prime }}$. By [F1], there are vertices $y,l$ and a set $S$ such that $y\to l$ in $G$, $l\to y$ in $G^{\mathrm{\prime }}$, and $S$ contains the other parents of $l$ in $G$ and is contained in its nondescendants; also $S$ contains the other parents of $y$ in $G^{\mathrm{\prime }}$ and is contained in its nondescendants.

Consider Phase 1 on a current vertex set $J$ obtained by deleting true sinks. A deleted sink cannot be a parent of a remaining vertex, so $J$ is parent-closed and its marginal law is the ANM product over $J$ by [F4]; consequently every original directed path between vertices still in $J$ stays in $J$. A finite DAG on nonempty $J$ has a sink $j$. Every other current vertex is a nondescendant of $j$ in the original graph: if one were a descendant, its path from $j$ would remain in the parent-closed current graph, contradicting that $j$ is a sink there. Thus for $C=J\setminus \{j\}$, $\mathrm{pa}(j)\subseteq C\subseteq \mathrm{nd}(j)$.

Both models in step 1.1 are restricted ANMs. By [F3] their structural functions and noise densities are $C^3$, so the product density versions supplied by [F4] are $C^3$. Since the models have the same observational law, these continuous densities agree almost everywhere and hence everywhere; denote their common pointwise version by $p$. Define the marginal versions needed below by iterated integration of this same $p$, and define conditional-density versions at each finite positive value of $p_{X_S}$ by the corresponding ratios. Apply the restricted-model definition in $G$ to the edge $y\to l$ and this exact set $S$. It supplies $s$ with $0<p_{X_S}(s)<\mathrm{\infty }$ such that the pair $Y^{\ast }=X_y\mid X_S=s$, $L^{\ast }=X_l\mid X_S=s$, using these common density versions, is a smooth bivariate ANM satisfying Condition 19. In particular, the definition gives the forward equation $L^{\ast }=f_l(s_{\mathrm{pa}(l)\setminus \{y\}},Y^{\ast })+N_l$ with $N_l$ independent of $Y^{\ast }$.

Population consistency gives $m_{j,C}(X_C)=f_j(X_{\mathrm{pa}(j)})+c_{j,C}$ almost surely, so the tested residual is $N_j-c_{j,C}$. By [F2] it is independent of $X_C$, and the perfect oracle accepts $j$. Hence every iteration has at least one accepted candidate and cannot return failure.

In $G^{\mathrm{\prime }}$, the reverse edge is $l\to y$ and $S$ contains all other parents of $y$. Since $S\cup \{l\}\subseteq {\mathrm{nd}}_{G^{\mathrm{\prime }}}(y)$, [F2] gives $N_y^{\mathrm{\prime }}$ independent of $(X_l,X_S)$. Let $q_{N_y^{\mathrm{\prime }}}$ be its density and choose the product density version $p_{N_y^{\mathrm{\prime }},X_l,X_S}(n,l,s):=q_{N_y^{\mathrm{\prime }}}(n)p_{X_l,X_S}(l,s),$ using the common marginal version fixed in step 2.1. Because $0<p_{X_S}(s)<\mathrm{\infty }$, dividing this version by $p_{X_S}(s)$ shows that, conditional on $X_S=s$, $N_y^{\mathrm{\prime }}$ and $X_l$ are independent. The reverse structural equation at that section is $Y^{\ast }=g_y(s_{{\mathrm{pa}}_{G^{\mathrm{\prime }}}(y)\setminus \{l\}},L^{\ast })+N_y^{\mathrm{\prime }},$ and its structural slice is $C^3$ by [F3]. In the $G^{\mathrm{\prime }}$ product-density formula, the factor for $X_y$ depends only on $y,l,s$, because all other parents of $y$ lie in $S$; integrating the remaining coordinates by the same iterated-integral convention in step 2.1 gives the common section density $p_{X_y,X_l,X_S}(y,l,s)=q_{N_y^{\mathrm{\prime }}}\text{\hspace{0.17em}⁣}(y-g_y(s_{{\mathrm{pa}}_{G^{\mathrm{\prime }}}(y)\setminus \{l\}},l))p_{X_l,X_S}(l,s)\mathrm{.}$ Thus the reverse conditional pair at this exact $s$ is formed from the same density $p_{X_y,X_l,X_S}(\cdot ,\cdot ,s)\mathrm{/}{p}_{X_S}(s)$ as the forward pair in step 2.1. They have the same law, and this is a reverse representation forbidden by [F8], proving population graph identifiability.

Now suppose a candidate $y\in J$ is not a sink. By the current-set invariant in step 1.2, choose a child $z$ of $y$ in $G[J]$ with no directed path to any other child of $y$ in $G[J]$; finiteness and acyclicity give such a child. Let $D$ be the strict descendants of $z$ in $G[J]$ and put $T=J\setminus (D\cup \{y,z\})$. Every parent of $z$ other than $y$ lies in $T$, and $T\subseteq \mathrm{nd}(z)\setminus \{y,z\}$ in the original graph as well as in $G[J]$. The restricted condition for edge $y\to z$ and set $T$ supplies $t$ with $0<p_{X_T}(t)<\mathrm{\infty }$ at which the conditional bivariate forward model of $Z^{\ast }=X_z\mid X_T=t$ from $Y^{\ast }=X_y\mid X_T=t$ satisfies Condition 19.

The predictor set tested for $y$ is $C=J\setminus \{y\}=T\cup \{z\}\cup D$. Suppose the oracle accepts it, and set $R_y=X_y-m_{y,C}(X_C)$. Then $R_y$ is independent of $X_C$. The current joint density is positive $C^3$ by [F3]–[F4], and $m_{y,C}$ is $C^3$ by hypothesis, so [F6] gives a pointwise density version $p_{X_y,X_C}(u,c)=q_{R_y}(u-m_{y,C}(c))p_{X_C}(c)\mathrm{.}$ By [F5], at the exact witness $t$, for almost every $(z,d)$ the conditional density of $Y^{\ast }$ given $(Z^{\ast }=z,X_D=d,X_T=t)$ does not depend on $d$. Combining this with the pointwise factorization above shows that the probability laws of $R_y+m_{y,C}(t,z,d)$ and $R_y+m_{y,C}(t,z,d^{\mathrm{\prime }})$ are equal for almost every $z,d,d^{\mathrm{\prime }}$.

If $D\mathrm{\ne }\mathrm{\varnothing }$, [F7] forces $m_{y,C}(t,z,d)=m_{y,C}(t,z,d^{\mathrm{\prime }})$ for almost every $(z,d,d^{\mathrm{\prime }})$. Fubini supplies a fixed $d_0$ for which $m_{y,C}(t,z,d)=m_{y,C}(t,z,d_0)$ for almost every $(z,d)$. Define $g_t(z)=m_{y,C}(t,z,d_0)$; this is $C^3$ by the Phase 1 smoothness hypothesis. If $D=\mathrm{\varnothing }$, define $g_t(z)=m_{y,C}(t,z)$, which is also $C^3$. In either case the accepted residual equation yields $Y^{\ast }=g_t(Z^{\ast })+R_y$ almost surely. The pointwise factorization [F6], restricted to $X_T=t$ and integrated over $X_D$, shows that $R_y$ is independent of $Z^{\ast }$ in this conditional law. This is a reverse representation of the Condition 19 pair from step 3.2, contradicting [F8]. Therefore no nonsink candidate is accepted.

Phase 1 therefore removes only true sinks. Reversing their removal order gives a topological order: for every edge $i\to j$, $j$ must be removed before $i$ while both remain, so $i$ precedes $j$ in the reversed list. The provisional parent set of each vertex is exactly the set of vertices preceding it in that order.

Fix a vertex $j$ and consider its candidate parents in the fixed loop order. We prove by induction through that list that no true parent is deleted. At a true-parent candidate $\mathrm{\ell }$, all other true parents are still present: they were either untested or retained by the induction hypothesis. The current set $C$ contains them and is contained in the preceding vertices, hence in $\mathrm{nd}(j)\setminus \{\mathrm{\ell }\}$. If the oracle accepted deletion, the residual $U=X_j-m_{j,C}(X_C)$ would be independent of the full preceding vector, in particular of $(X_{\mathrm{\ell }},X_C)$. Since $X_j=m_{j,C}(X_C)+U$, its conditional law given $(X_{\mathrm{\ell }},X_C)$ would not depend on $X_{\mathrm{\ell }}$, yielding $X_j{\perp }_d{X}_{\mathrm{\ell }}\mid X_C$. This contradicts [F9]. Thus every true parent is retained.

If the tested candidate $\mathrm{\ell }$ is not a true parent, step 7.1 ensures that every true parent remains in the predictor set $C$ after deleting $\mathrm{\ell }$. This set is contained in $\mathrm{nd}(j)$, so [F10] makes the residual $N_j$ minus a constant; [F2] makes it independent of all vertices preceding $j$. The oracle accepts and the algorithm deletes this superfluous edge.

Steps 7.1 and 8.1 show that pruning removes exactly the superfluous preceding vertices and retains every parent. Each returned parent set is therefore the true parent set, so RESIT returns $G$.