# Variable elimination, graph reduction and efficient g-formula

F. Richard Guo<EMAIL_ADDRESS>Statistical Laboratory, University of
Cambridge, Cambridge, UK  Emilija Perković<EMAIL_ADDRESS>Department of
Statistics, University of Washington, Seattle, USA  Andrea Rotnitzky
<EMAIL_ADDRESS>Department of Economics, Universidad Torcuato Di Tella,
Buenos Aires, Argentina

###### Abstract

We study efficient estimation of an interventional mean associated with a
point exposure treatment under a causal graphical model represented by a
directed acyclic graph without hidden variables. Under such a model, it may
happen that a subset of the variables are uninformative in that failure to
measure them neither precludes identification of the interventional mean nor
changes the semiparametric variance bound for regular estimators of it. We
develop a set of graphical criteria that are sound and complete for
eliminating all the uninformative variables so that the cost of measuring them
can be saved without sacrificing estimation efficiency, which could be useful
when designing a planned observational or randomized study. Further, we
construct a reduced directed acyclic graph on the set of informative variables
only. We show that the interventional mean is identified from the marginal law
by the g-formula (Robins, 1986) associated with the reduced graph, and the
semiparametric variance bounds for estimating the interventional mean under
the original and the reduced graphical model agree. This g-formula is an
irreducible, efficient identifying formula in the sense that the nonparametric
estimator of the formula, under regularity conditions, is asymptotically
efficient under the original causal graphical model, and no formula with such
property exists that only depends on a strict subset of the variables.

Keywords—Directed acyclic graph; Bayesian networks; Semiparametric efficiency;
Graphical model; Conditional independence; Average treatment effect;
Marginalization; Latent projection.

##  1 Introduction

This paper contributes to a growing literature on efficient estimation of
causal effects under causal graphical models (Rotnitzky and Smucler, 2020;
Bhattacharya et al., 2022; Smucler et al., 2021; Guo and Perković, 2022;
Henckel et al., 2022; Witte et al., 2020; Kuipers and Moffa, 2022). We
consider estimating the interventional mean of an outcome associated with a
point exposure treatment when a nonparametric causal graphical model,
represented by a directed acyclic graph, is assumed. Such a causal model
induces a semiparametric model on the factual data law known as a Bayesian
network, which associates each vertex of the graph with a random variable.
Under the Bayesian network model, every variable is conditionally independent
of its non-descendants given its parents in the graph. Further, under the
causal graphical model, the interventional mean is identified by a smooth
functional of the factual data law given by the g-formula (Robins, 1986). This
functional is the mean of the outcome taken with respect to a truncated law
which agrees with the factual law except that the probability of treatment
given its parents in the graph is replaced by a point mass at the intervened
level of the treatment. The semiparametric variance bound for this functional
under the induced Bayesian network model gives the lowest benchmark for the
asymptotic variance of any regular estimator of the functional and, as such,
it quantifies the efficiency with which, under regularity conditions, one can
hope to estimate the interventional mean under the model without posing
additional assumptions.

Rotnitzky and Smucler (2020) identified a class of directed acyclic graphs
under which the semiparametric variance bound for the interventional mean is
equal to the variance bound under a simpler causal graphical model, which is a
directed acyclic graph consisting of the treatment, the outcome and a special
set of covariates known as the optimal adjustment set (Henckel et al., 2022).
This implies that all the remaining variables in the original graph are
uninformative in that failure to measure them has no impact on the efficiency
with which one can hope to estimate the interventional mean. However, this
earlier work left unanswered the question of identifying uninformative
variables in an arbitrary directed acyclic graph that does not belong to their
special class, which is the goal of this paper.

We prove theoretical results that can guide practitioners in the design and
analysis of an observational or sequentially randomized study. First, at the
stage of designing a study, it informs which variables should be measured for
optimally estimating the effect of interest. Designers of a study often employ
directed acyclic graphs to incorporate substantive causal assumptions,
including hypotheses on potential confounders and causal paths (Hernán and
Robins, 2020, §6). Our Theorem 4.1 provides a graphical criterion that allows
the designer to read off from the graph the set of informative variables,
which is the minimal set of variables to measure that permits estimating the
effect of interest with maximum efficiency. This is useful because the cost
associated with measuring uninformative variables can be saved.

Second, for analyzing a study, our Algorithm 1 produces a reduced graph that
assists the data analyst in constructing an efficient estimator of the effect
of interest. The reduced graph is a directed acyclic graph that only contains
informative variables. As formalized in Theorem 5.1, the reduced graph encodes
all the modeling constraints required for optimally estimating the effect. In
fact, among all the possible ways to identify the effect from data, we show
that the g-formula associated with the reduced graph is the most efficient.
This leads to developing efficient estimators that involve the fewest number
of variables, and presumably, the fewest number of nuisance parameters. Even
when such an estimator is considerably simpler than an efficient estimator
constructed using the full graph and full data, there is no loss in
performance; see Appendix B for a simulation example. Finally, the whole
process of variable elimination, graph reduction and deriving the associated
g-formula is automated by our R package reduceDAG.

##  2 Motivation

To motivate the development in this paper, consider the causal agnostic
graphical model (Spirtes et al., 2000; Robins and Richardson, 2010)
represented by graph $\mathcal{G}$ in Fig. 2.1(a). Suppose $Y$ is an outcome
and $A$ is a discrete treatment whose causal effect on $Y$ we are interested
in estimating. The causal model implies the Bayesian network model on the
factual data, denoted as ${\mathcal{M}}(\mathcal{G},V),$ for the law of
$V=\\{A,Y,I_{1},O_{1},W_{1},W_{2},W_{3},W_{4}\\}$, which is defined by the
sole restriction that the joint density of $V$, with respect to some
dominating measure, factorizes as

$p(v)=p(y\mid a,o_{1})\,p(a\mid i_{1})\,p(i_{1}\mid w_{4})\,p(o_{1}\mid
w_{4})\,p(w_{4}\mid w_{2},w_{3})p(w_{3})\,p(w_{2}\mid w_{1})\,p(w_{1}).$

Each factor is either a marginal density if $V_{j}$ has no parent in
$\mathcal{G}$ or a conditional density of the form
$p\\{v_{j}\mid\operatorname{Pa}(v_{j},\mathcal{G})\\}$, where
$\operatorname{Pa}(v_{j},\mathcal{G})$ denotes the set of parents of $V_{j}$
in $\mathcal{G}$. These densities are unrestricted under model
${\mathcal{M}}(\mathcal{G},V)$ and they parameterize the model.

$A$$Y$$I_{1}$$O_{1}$$W_{4}$$W_{3}$$W_{2}$$W_{1}$(a)
$\mathcal{G}$$A$$Y$$W_{4}$$O_{1}$$W_{3}$$W_{2}$(b)
$\mathcal{G}^{\prime}$$A$$Y$$O_{1}$$W_{3}$$W_{2}$(c)
$\mathcal{G}^{\ast}$$A$$Y$$O_{1}$$W_{3}$$W_{2}$(d)$A$$Y$$I_{1}$$O_{1}$$W_{4}$$W_{3}$$W_{2}$$W_{1}$(e)
$\check{\mathcal{G}}$ Figure 2.1: Causal graphs involved in the motivating
example: (a) the original graph $\mathcal{G}$, where variables
$\\{I_{1},W_{1},W_{4}\\}$ are uninformative, among which $\\{I_{1},W_{1}\\}$
are redundant; (b) graph $\mathcal{G}^{\prime}$ is obtained by projecting out
the redundant variables $\\{I_{1},W_{1}\\}$ from $\mathcal{G}$; (c) the
reduced graph $\mathcal{G}^{\ast}$ that projects out all the uninformative
variables using Algorithm 1; (d) the latent projection (Verma and Pearl, 1990)
of $\mathcal{G}$ that marginalizes over $\\{I_{1},W_{1},W_{4}\\}$, where a
bidirected edge between $A$ and $O$ is introduced to due to confounder
$W_{4}$; (e) graph $\check{\mathcal{G}}$ is causal Markov equivalent to
$\mathcal{G}$, from which $\\{I_{1},W_{1}\\}$ can be identified as redundant
and hence uninformative.

If $p(a\mid i_{1})>0$ for all $i_{1}$ in the range of $I_{1},$ the causal
graphical model also implies that the joint density of the variables in the
graph, when $A$ is intervened and set to $a$, is given by

$p_{a}(v)=J_{a}(v)\,p(y\mid a,o_{1})\,p(i_{1}\mid w_{4})\,p(o_{1}\mid
w_{4})\,p(w_{4}\mid w_{2},w_{3})p(w_{3})\,p(w_{2}\mid w_{1})\,p(w_{1}),$

where $J_{a}(v)$ is the indicator function that the $A$ component of $V$ is
equal to $a$ when $V$ takes value $v$. In particular, the mean of the outcome
when $A$ is intervened and set to $a$, which we shall refer to throughout as
the interventional mean and denote with $\operatorname{\mathbb{E}}Y(a)$, is
given by

$\Psi_{a}(P;\mathcal{G})\equiv\sum_{y,o,i,w_{1},w_{2},w_{3},w_{4}}y\,p(y\mid
a,o_{1})\,p(i_{1}\mid w_{4})\,p(o_{1}\mid w_{4})\,p(w_{4}\mid
w_{2},w_{3})\,p(w_{3})\,\\\ \times p(w_{2}\mid w_{1})\,p(w_{1})$ (1)

if all the components of $V$ are discrete; otherwise $\Psi_{a}(P;\mathcal{G})$
is defined with the summation replaced by an integral with respect to the
dominating measure. We call Eq. 1 the g-formula associated with graph
$\mathcal{G}$ (Robins, 1986).

Our goal is to determine the variables in vector $V$ that can be disposed of
without affecting the asymptotic efficiency with which we can hope to estimate
$\Psi_{a}(P;\mathcal{G})$. With this goal in mind, we first observe that the
term $p(i_{1}\mid w_{4})$ can be summed out from the right hand side of Eq. 1
because $i_{1}$ does not appear in the conditioning set of any other
conditional densities. Writing $p(w_{2}\mid w_{1})\,p(w_{1})=p(w_{1},w_{2})$,
we also observe that we can sum out $w_{1}$ from Eq. 1 as well. We then
conclude that $\Psi_{a}(P;\mathcal{G})$ is equal to

$\sum_{y,o_{1},w_{2},w_{3},w_{4}}y\,p(y\mid a,o_{1})\,p(o_{1}\mid
w_{4})\,p(w_{4}\mid w_{2},w_{3})\,p(w_{2})\,p(w_{3}).$ (2)

Next, we notice that because both $p(w_{2}\mid w_{1})$ and $p(w_{1})$ are
unrestricted under model ${\mathcal{M}}(\mathcal{G},V)$, so is
$p\left(w_{2}\right)$. In fact, all the densities that remain in Eq. 2 are
also unconstrained under the model. Because the data on $\\{I_{1},W_{1}\\}$
does not help us estimate these densities, we conclude that we can discard
$\\{I_{1},W_{1}\\}$ without affecting the efficiency in estimating
$\Psi_{a}(P;\mathcal{G})$. We recognize that expression (2) is precisely the
g-formula $\Psi_{a}(P^{\prime};\mathcal{G}^{\prime})$, where
$\mathcal{G}^{\prime}$ is the graph in Fig. 2.1(b) and $P^{\prime}$ is the
marginal law of $V^{\prime}\equiv V\setminus\\{I_{1},W_{1}\\}$. Moreover,
under both ${\mathcal{M}}(\mathcal{G},V)$ and
${\mathcal{M}}(\mathcal{G}^{\prime},V^{\prime})$, the densities in Eq. 2 are
unrestricted. Hence, as far as the efficient estimation of
$\Psi_{a}(P;\mathcal{G})$ is concerned, we can ignore $\\{I_{1},W_{1}\\}$ and
pretend that our problem is to estimate the g-formula
$\Psi_{a}(P^{\prime};\mathcal{G}^{\prime})$ based on a random sample of
$V^{\prime}$, under the assumption that $P^{\prime}$ belongs to
${\mathcal{M}}(\mathcal{G}^{\prime},V^{\prime})$.

In Section 3.3, we will review the notion of causal Markov equivalent graphs
with respect to the effect of $A$ on $Y$. These are graphs that encode the
same Bayesian network model and their associated g-formulae coincide under the
model. For instance, graphs $\mathcal{G}$ and $\check{\mathcal{G}}$ in Fig.
2.1 are causal Markov equivalent. We will show that a variable for which there
exists some causal Markov equivalent graph in which all directed paths towards
$Y$ intersect $A$, such as $I_{1}$ in our example, is uninformative for
estimating $\Psi_{a}(P;\mathcal{G})$. Similarly, a variable that is non-
ancestral to $Y$ in some causal Markov equivalent graph, such as $W_{1}$ in
our example, is also uninformative. We refer to these two types of variables
as redundant.

Further, by traversing graphs in the causal Markov equivalent class, one can
see that $\\{I_{1},W_{1}\\}$ are the only redundant variables. One might
believe that all variables in $V^{\prime}$ are needed to construct an
asymptotically efficient estimator of $\Psi_{a}(P;\mathcal{G})$. For instance,
suppose $V$ is discrete. Consider the maximum likelihood estimator
$\Psi_{a}(\widehat{\mathbb{P}}_{n}^{\prime};\mathcal{G}^{\prime})$ with

$\widehat{\mathbb{P}}_{n}^{\prime}(a,y,o_{1},w_{4},w_{3},w_{2})\equiv\mathbb{P}_{n}(y\mid
a,o_{1})\,\mathbb{P}_{n}(a\mid w_{4})\,\mathbb{P}_{n}(w_{4}\mid
w_{2},w_{3})\,\mathbb{P}_{n}(o_{1}\mid
w_{4})\,\mathbb{P}_{n}(w_{2})\,\mathbb{P}_{n}(w_{3}),$

where $\mathbb{P}_{n}(\cdot\mid\cdot)$ and $\mathbb{P}_{n}(\cdot)$ denote,
respectively, the empirical conditional and marginal probability operators.
Law $\hat{\mathbb{P}}^{\prime}_{n}$ is the maximum likelihood estimator for
$P^{\prime}$ under ${\mathcal{M}}(\mathcal{G}^{\prime},V^{\prime})$. Clearly,
one needs every variable in $V^{\prime}$ to compute this estimator.

Surprisingly, in Section 5 we will show that, even without using the data on
$W_{4}$, we can construct an estimator with the same limiting distribution as
the maximum likelihood estimator. Specifically, let $P^{\ast}$ denote the
marginal law of $V^{\ast}\equiv V^{\prime}\setminus\\{W_{4}\\}$ for
$V^{\prime}\sim P^{\prime}$, and let $\mathcal{G}^{\ast}$ be the graph over
$V^{\ast}$ shown in Fig. 2.1(c). We will show that the maximum likelihood
estimator of the g-formula

$\Psi_{a}(P^{\ast};\mathcal{G}^{\ast})\equiv\sum_{y,o_{1},w_{2},w_{3}}y\,p(y\mid
a,o_{1})\,p(o_{1}\mid w_{2},w_{3})\,p(w_{2})\,p(w_{3})$ (3)

with respect to the Bayesian network model represented by $\mathcal{G}^{\ast}$
is asymptotically equivalent to the aforementioned
$\Psi_{a}(\widehat{\mathbb{P}}_{n}^{\prime};\mathcal{G}^{\prime})$ under every
law $P^{\prime}$ in model ${\mathcal{M}}(\mathcal{G}^{\prime},V^{\prime})$.
The estimator based on Eq. 3 does not require measuring $W_{4}$. This result
can be useful even when $W_{4}$ is already measured but incorporating it into
estimation is difficult, for example when $W_{4}$ is continuous while all the
other variables are discrete. In such cases, using the maximum likelihood
estimate of Eq. 3 circumvents estimating $p(w_{4}\mid w_{2},w_{3})$ and
$p(o\mid w_{4})$, which typically requires smoothing.

More generally, we will show that (i) when Bayesian networks are defined on a
sufficiently large state space, graph $\mathcal{G}^{\ast}$ represents the
marginal model of the law $P^{\ast}$ over $V^{\ast}$ induced by
${\mathcal{M}}(\mathcal{G}^{\prime},V^{\prime})$ or, equivalently, by the
original ${\mathcal{M}}(\mathcal{G},V)$; (ii)
$\Psi_{a}(P^{\ast};\mathcal{G}^{\ast})=\Psi_{a}(P;\mathcal{G})$ for every
$P\in{\mathcal{M}}(\mathcal{G};V)$ under a positivity condition introduced in
Section 3.3; (iii) the semiparametric variance bound for
$\Psi_{a}(P^{\ast};\mathcal{G}^{\ast})$ with respect to
${\mathcal{M}}(\mathcal{G}^{\ast},V^{\ast})$ and the bound for
$\Psi_{a}(P;\mathcal{G})$ with respect to ${\mathcal{M}}(\mathcal{G},V)$
coincide. Therefore, for estimating the interventional mean, not only is
$W_{4}$ asymptotically uninformative but, moreover, we can discard
$\mathcal{G}$ and pretend it is the graph $\mathcal{G}^{\ast}$ that we started
with. The same can be said for estimating the average treatment effect, e.g.,
$\operatorname{\mathbb{E}}Y(1)-\operatorname{\mathbb{E}}Y(0)$ when $A$ is
binary. Also, $\mathcal{G}^{\ast}$ is different from the latent projection
(Verma and Pearl, 1990) of $\mathcal{G}$ onto $V^{\ast}$, which introduces
bidirected edges when a confounder is marginalized over; compare Fig. 2.1(c)
and (d).

Conceptually, the preceding results can be interpreted as follows. It is well-
known that the Bayesian network ${\mathcal{M}}(\mathcal{G},V)$ is the set of
laws that obey the conditional independencies implied by d-separations with
respect to $\mathcal{G}$. Our results imply that estimating
$\Psi_{a}(P;\mathcal{G})$ under a supermodel $\bar{{\mathcal{M}}}$, which is
specified by those conditional independencies in
${\mathcal{M}}(\mathcal{G},V)$ that do not involve variables
$\\{I_{1},W_{1},W_{4}\\}$, is no more difficult than estimating it under
${\mathcal{M}}(\mathcal{G},V)$. In other words, ${\mathcal{M}}(\mathcal{G},V)$
is a least favorable submodel of $\bar{{\mathcal{M}}}$ (van der Vaart, 2000,
§25.3) in the sense that the extra constraints it encodes are uninformative
for the target parameter.

Furthermore, in Section 4, we show that no variable can be further eliminated
from $V^{\ast}$ without impairing efficiency at some law in
${\mathcal{M}}(\mathcal{G},V)$. It can then be argued that the g-formula
associated with $\mathcal{G}^{\ast}$, such as (3), is an irreducible,
efficient identifying formula for $\Psi_{a}(P;\mathcal{G})$. In particular,
this implies that when all components of $V$ are discrete, the plugin
estimator of any other identifying formula either depends on a strict superset
of $V^{\ast}$, as is the case with Eq. 2, or has an asymptotic variance
strictly greater than the Cramér–Rao bound under some law in
${\mathcal{M}}(\mathcal{G},V)$. As an example of the latter, consider the
class of adjustment formulae

$\Psi_{a,L}^{\mathrm{ADJ}}(P;\mathcal{G})\equiv\sum_{y,l}y\,p(y\mid
a,L=l)\,p(l),$ (4)

which agrees with $\Psi_{a}(P;\mathcal{G})$ in ${\mathcal{M}}(\mathcal{G},V)$,
where $L$ is any set of variables non-descendant to $A$ that blocks all the
back-door paths between $A$ and $Y$ in $\mathcal{G}$ (Pearl, 1993), e.g.,
$L=\\{O_{1}\\}$, $L=\\{I_{1}\\}$, $L=\\{W_{4}\\}$ or $L=\\{I_{1},W_{4}\\}$.
These formulae lead to inefficient estimators
$\Psi_{a,L}^{\mathrm{ADJ}}(\mathbb{P}_{n};\mathcal{G})$ when plugging in the
empirical measure, as is confirmed by simulations in Appendix B.

##  3 Technical background

###  3.1 Relation to optimal adjustment

Our problem is different from optimal adjustment. Our efficiency bound is
defined relative to all regular, asymptotically linear estimators of
$\Psi_{a}(P;\mathcal{G})$ under the Bayesian network model
${\mathcal{M}}(\mathcal{G},V)$. In contrast, the literature on optimal
adjustment (e.g., Kuroki and Miyakawa, 2003; Hahn, 2004; Rotnitzky and
Smucler, 2020; Henckel et al., 2022) restricts the class of estimators to
those that estimate nonparametric target Eq. 4 without imposing any
conditional independence restrictions, and seeks one with the maximum
efficiency within the class, which is called the optimal adjustment estimator.
By definition, the asymptotic variance bound we consider is smaller than or
equal to the asymptotic variance of the optimal adjustment estimator. For
cases where the optimal adjustment estimator does not achieve the asymptotic
variance bound we consider, see our motivating example in Fig. 2.1 and
Examples 3, 4 and 5 in Section 6.

As mentioned in the introduction, under a Bayesian network model, there are
certain graphs, characterized by Rotnitzky and Smucler (2020, Theorem 19),
where the optimal adjustment estimator achieves the asymptotic variance bound
considered here. In this paper we study general graphs beyond these cases.

###  3.2 Bayesian network, directed acyclic graph and vertex sets

For technical reasons that will be explained shortly, we define a Bayesian
network model on a larger state space than typically required. For every
random variable $V_{j}\in V$, let its state space be

$\mathfrak{X}_{j}=\mathbb{R}^{d_{j}}\,\dot{\cup}\,\mathbb{W},\quad d_{j}\geq
1,\quad\mathbb{W}=\\{\omega_{1},\omega_{2},\dots\\},$ (5)

where $\,\dot{\cup}\,$ denotes a disjoint union and the set $\mathbb{W}$ is a
collection of symbols isomorphic to the natural numbers. That is, the state
space $\mathfrak{X}_{j}$ allows $V_{j}$ to be potentially Euclidean or
discrete, or a mixed type of both, prior to observing the data on $V_{j}$. In
Section A.1, measure $\mu_{j}$ and $\sigma$-algebra $\mathcal{F}_{j}$ for
every $V_{j}$ are defined accordingly. The Bayesian network model is the set
of probability measures on $\left(\mathfrak{X}\equiv\times_{j:V_{j}\in
V}\mathfrak{X}_{j},\mathcal{F}\equiv\times_{j:V_{j}\in
V}\mathcal{F}_{j}\right)$ that factorize according to the graph, i.e.,

${\mathcal{M}}(\mathcal{G},V)\equiv\left\\{P:\frac{\mathop{}\\!\mathrm{d}P}{\mathop{}\\!\mathrm{d}\mu}\left(v\right)\equiv
p(v)=\prod_{j:V_{j}\in
V}p\\{v_{j}\mid\operatorname{Pa}(v_{j},\mathcal{G})\\}\right\\},$ (6)

where the density $p$ is taken with respect to the dominating measure
$\mu\equiv\times_{j:V_{j}\in V}\mu_{j}$. The symbol
$\operatorname{Pa}(v_{j},\mathcal{G})$ denotes the value taken by the set of
parents of $V_{j}$ with respect to $\mathcal{G}$ when $V=v$. By the
equivalence between factorization and the global Markov property,
${\mathcal{M}}(\mathcal{G},V)$ coincides with the set of laws that obey the
conditional independences implied by d-separations with respect to
$\mathcal{G}$; in addition, ${\mathcal{M}}(\mathcal{G},V)$ is also the set of
laws that satisfy the local Markov property, namely a variable is independent
of its non-descendants given its parents; see, e.g., Lauritzen (1996, Theorem
3.27). We also refer to ${\mathcal{M}}(\mathcal{G},V)$ as the model
represented by $\mathcal{G}$.

######  Remark 1.

We introduce Eq. 5 to ensure that the state space of every variable is
sufficiently large so that it is essentially no different from an
unconstrained state space. Consequently, the notion of an induced marginal
model in the rest of the paper aligns with the notion of a marginal model
typically used in the literature, where the state space of the marginalized
variables is unspecified or unrestricted; see, e.g., Evans (2016, Definition
6). Following the discussion in Cencov (1982, §2.11), a sufficiently large
state space can be ensured if each $\mathfrak{X}_{j}$ at least contains an
interval of the real line. We make this technical requirement on the state
space to rule out undesired, e.g., reduced-rank, constraints on the induced
model when marginalizing out a variable with a finite or small state space
(Mond et al., 2003).

######  Remark 2.

The definition above by no means precludes discrete distributions that only
put mass on vectors consisting of symbols in $\mathbb{W}$. In fact, when the
data are discrete, the maximum likelihood estimate is well-defined and
coincides with the maximum likelihood estimate under the commonly used model
with $\mathfrak{X}_{j}=\mathbb{W}$ for every $V_{j}\in V$. For technical
reasons, model ${\mathcal{M}}(\mathcal{G},V)$ considered here is larger than
the commonly used Bayesian network model, but the difference is
inconsequential in terms of data analysis.

Throughout, we use upper-case letters to denote vertices of a graph or the
random variables they represent. Lower-case letters are reserved for indices
or values taken by random variables. We use standard notation for graphical
models, summarized in Section A.2. Among others, we say that path $p$ from
$V_{1}$ to $V_{k}$ is causal if it is of the form
$V_{1}\rightarrow\dots\rightarrow V_{k}$. The notation $V_{i}\mapsto V_{j}$ is
a shorthand for $V_{i}\in\operatorname{An}(V_{j})$.

For disjoint sets $A$, $B$ and $C$, we use
$A\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}B\mid C$ to
denote conditional independence between $A$ and $B$ given $C$ under a given
law, and we use
$A\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}B\mid
C$ to denote d-separation between $A$ and $B$ given $C$ in graph
$\mathcal{G}$. For d-separation, we allow $A\cap C\neq\emptyset$ and $B\cap
C\neq\emptyset$, in which case
$A\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}B\mid
C$ is interpreted as $A\setminus
C\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}B\setminus
C\mid C$. We also use the convention that
$\emptyset\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}B\mid
C$ for any sets $B$ and $C$. Conditional independence and d-separation share
similar properties: the former satisfies semi-graphoid axioms, while the
latter satisfies the stronger compositional graphoid axioms; see Pearl (1988,
Theorem 1 and 11).

Two directed acyclic graphs $\mathcal{G}$ and $\mathcal{G}^{\prime}$ on the
same vertex set $V$ are called Markov equivalent if
${\mathcal{M}}(\mathcal{G},V)={\mathcal{M}}(\mathcal{G}^{\prime},V)$. It is
well-known that two graphs are Markov equivalent if and only if they share the
same adjacencies and unshielded colliders (Verma and Pearl, 1990; Andersson et
al., 1997). Further, a Markov equivalence class can be graphically represented
by a completed partially directed acyclic graph, also known as an essential
graph (Meek, 1995a; Andersson et al., 1997).

######  Assumption 1.

In directed acyclic graph $\mathcal{G}$, $A\mapsto Y$.

We will make this assumption throughout; otherwise the model already assumes
$A$ has no effect on $Y$. As we will see, the information carried by a
variable depends crucially on its ancestral relations with respect to
treatment $A$ and outcome $Y$. To ease the exposition, we introduce the
following taxonomy of vertices, which is illustrated in Fig. 3.1(a).

(i) Non-ancestors of $Y$: $N(\mathcal{G})\equiv
V\setminus\operatorname{An}(Y,\mathcal{G})$.

(ii) Indirect ancestors of $Y$: $I(\mathcal{G})\equiv\left\\{V_{j}\in
V:\,V_{j}\neq A,\,V_{j}\mapsto Y\text{ only through }A\right\\}$. These are
also conditional instruments given $\operatorname{Pa}(I,\mathcal{G})\setminus
I$ (Didelez and Sheehan, 2007).

(iii) Baseline covariates: non-descendants of $A$, but ancestors of $Y$ not
only through $A$, i.e.,

$W(\mathcal{G})\equiv\left\\{V_{j}\in V:\,A\not\mapsto V_{j},V_{j}\mapsto
Y,\,V_{j}\notin I(\mathcal{G})\right\\}.$ (7)

In contrast to $I(\mathcal{G})$, for each $W_{j}\in W(\mathcal{G})$ there is a
causal path from $W_{j}$ to $Y$ that does not contain $A$.

(iv) Mediators: $M(\mathcal{G})\equiv\\{V_{j}\in V:\,V_{j}\neq A,\,A\mapsto
V_{j}\mapsto Y\\}$. These are the variables that lie on the causal paths
between $A$ and $Y$. With a slight abuse of the term mediators, the set
$M(\mathcal{G})$ also contains $Y$.

It follows that the set of variables is partitioned as
$V=\\{A\\}\,\dot{\cup}\,N(\mathcal{G})\,\dot{\cup}\,I(\mathcal{G})\,\dot{\cup}\,W(\mathcal{G})\,\dot{\cup}\,M(\mathcal{G})$.
The following subset of $W$ is also important: the optimal adjustment set
(Henckel et al., 2022)

$O(\mathcal{G})\equiv\operatorname{Pa}\\{M(\mathcal{G}),\mathcal{G}\\}\setminus\left\\{M(\mathcal{G})\cup\\{A\\}\right\\}.$
(8)

The set $O(\mathcal{G})$ consists of the parents of mediators that are not
themselves mediators or the treatment; see Witte et al. (2020) for other
characterizations. By definition it can be empty. The set of baseline
covariates $W(\mathcal{G})$ is related to its subset $O(\mathcal{G})$ by the
following lemma; further properties of $O(\mathcal{G})$ can be found in the
next subsection.

######  Lemma 3.1.

Under 1, $W(\mathcal{G})=\operatorname{An}\\{O(\mathcal{G}),\mathcal{G}\\}$.

We also define the following subset of $O(\mathcal{G})$ that will be useful
later:

$O_{\min}(\mathcal{G})\,\equiv\,\text{the inclusion minimal
$O^{\prime}\subseteq O$}(\mathcal{G})\text{ such that
$A\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}O(\mathcal{G})\setminus
O^{\prime}\mid O^{\prime}$}.$

The intersection property of d-separation ensures that $O_{\min}(\mathcal{G})$
is uniquely defined; see Rotnitzky and Smucler (2020, Lemma 7, Appendix).

$A$$M_{1}$$M_{2}$$Y$$I_{2}$$O_{1}$$N_{1}$$I_{1}$$O_{3}$$M_{3}$$O_{4}$$W_{1}$$O_{2}$(a)$A$$M$$Y$$O$(b)
Figure 3.1: (a) An illustration of the taxonomy of vertices. $A$ is the
treatment and $Y$ is the outcome. Vertex $N=\\{N_{1}\\}$ is non-ancestral to
$Y$. Set $I=\\{I_{1},I_{2}\\}$ consists of indirected ancestors of $Y$, which
are conditional instruments given $\\{W_{1},O_{1}\\}$. We have
$W=\\{W_{1},O_{1},O_{2},O_{3},O_{4}\\}$, of which the subset
$O=\\{O_{1},O_{2},O_{3},O_{4}\\}$ is the optimal adjustment set; further,
$O_{\min}=\\{O_{1},O_{2},O_{3}\\}$. Finally, $M=\\{M_{1},M_{2},M_{3},Y\\}$ is
the set of mediators. (b) An example with multiple identifying formulae: the
g-formula Eq. 11, the back-door formula Eq. 12 and the front-door formula Eq.
13.

###  3.3 Causal graphical model and the g-formula

Throughout, we assume a causal agnostic graphical model (Spirtes et al., 2000;
Robins and Richardson, 2010) represented by a directed acyclic graph
$\mathcal{G}$ on vertex set $V$, where $A\in V$ is a discrete treatment and
$Y\in V$ is the outcome of interest. We also impose 1 on $\mathcal{G}$. The
causal model implies that the law $P$ of the factual variables $V$ belongs to
the Bayesian network model ${\mathcal{M}}(\mathcal{G},V)$ defined in Eq. 6.

Under 2 introduced below, the causal graphical model further posits that when
$A$ is intervened and set to level $a$, the density of the variables in the
graph is

$p_{a}\left(v\right)\equiv J_{a}(v)\prod_{V_{j}\in
V\setminus\\{A\\}}p\\{v_{j}\mid\operatorname{Pa}(v_{j},\mathcal{G})\\},$ (9)

where $J_{a}(v)$ is the indicator of the $A$ component of $V$ being equal to
$a$ when $V=v$. The right-hand side of Eq. 9 is known as the g-formula
(Robins, 1986), the manipulated distribution formula (Spirtes et al., 2000) or
the truncated factorization formula (Pearl, 2000) in the literature. Our
target of inference, the interventional mean, which we denote with
$\operatorname{\mathbb{E}}Y(a)$, is therefore given by

$\Psi_{a}(P;\mathcal{G})\equiv\sum_{y,\,v_{j}:V_{j}\in
V\setminus\\{A,Y\\}}y\prod_{j:V_{j}\in
V\setminus\\{A\\}}p\left\\{v_{j}\mid\left.\operatorname{Pa}(v_{j},\mathcal{G})\right|_{A=a}\right\\},$
(10)

if all components of $V$ are discrete; otherwise $\Psi_{a}(P;\mathcal{G})$ is
defined with the summation replaced by an integral with respect to the
dominating measure $\mu$; see also Eq. 6. The symbol
$\left.\operatorname{Pa}(v_{j},\mathcal{G})\right|_{A=a}$ indicates that if
$A\in\operatorname{Pa}(V_{j},\mathcal{G})$, then the value taken by $A$ when
$V_{j}=v_{j}$ is set to $a$. We refer to
$\Psi_{a}(\cdot;\mathcal{G}):{\mathcal{M}}(\mathcal{G},V)\rightarrow\mathbb{R}$
as the g-functional.

######  Assumption 2 (Positivity).

There exists $\varepsilon>0$, which can depend on $P$, such that the
conditional probability
$P\\{A=a\mid\operatorname{Pa}(A,\mathcal{G})\\}>\varepsilon$ $P$-almost
surely.

By the local Markov property, this assumption implies $P(A=a\mid
L)>\varepsilon$ $P$-almost surely for every $L\subset V$ that is non-
descendant to $A$.

For the rest of this paper, ${\mathcal{M}}_{0}(V)$ denotes the set of all laws
over $V$ restricted only by the inequality in 2. Accordingly, a Bayesian
network ${\mathcal{M}}(\mathcal{G};V)$ should be understood as the
intersection of the original definition Eq. 6 with such
${\mathcal{M}}_{0}(V)$. We impose 2 because otherwise the semiparametric
variance bound for the g-functional is undefined.

######  Definition 1 (Identifying formula).

Fix a model ${\mathcal{M}}(V)\subseteq{\mathcal{M}}_{0}(V)$ and a functional
$\gamma(P):{\mathcal{M}}(V)\rightarrow\mathbb{R}$. The functional
$\chi(P):{\mathcal{M}}_{0}(V)\rightarrow\mathbb{R}$ is an identifying formula
for $\gamma(P)$ if $\chi(P)=\gamma(P)$ for every $P\in{\mathcal{M}}(V)$.

By the definition above, the natural extension
$\Psi_{a}(P;\mathcal{G}):{\mathcal{M}}_{0}(V)\rightarrow\mathbb{R}$ according
to Eq. 10, called the g-formula associated with graph $\mathcal{G}$, is an
identifying formula for the g-functional. However, because of conditional
independences in a Bayesian network, one can typically derive more than one
identifying formula. As mentioned in Section 2, the adjustment
$\Psi_{a,L}^{\mathrm{ADJ}}(P;\mathcal{G})$ given in Eq. 4 based on a valid
choice of $L$ is also an identifying formula for $\Psi_{a}(P;\mathcal{G})$. In
particular, with discrete data, choosing $L=O(\mathcal{G})$ for estimator
$\Psi_{a,L}^{\mathrm{ADJ}}(\mathbb{P}_{n})$ leads to the optimal adjustment,
which achieves the smallest asymptotic variance among all valid choices of $L$
(Rotnitzky and Smucler, 2020); further, this choice is also optimal under the
subclass of linear causal graphical models (Henckel et al., 2022). Here is
another example of multiple identifying formulae.

######  Example 1.

Consider graph $\mathcal{G}$ in Fig. 3.1(b). The g-functional associated with
$\mathcal{G}$ is

$\Psi_{a}(P;\mathcal{G})=\sum_{y,m,o}y\,p(y\mid m,o)\,p(m\mid a)\,p(o).$ (11)

Under ${\mathcal{M}}(\mathcal{G},V)$, it agrees with the adjustment or back-
door formula
$\Psi^{\mathrm{ADJ}}_{a,O}(\cdot;\mathcal{G}):{\mathcal{M}}_{0}(V)\rightarrow\mathbb{R}$,

$\Psi^{\mathrm{ADJ}}_{a,O}(P;\mathcal{G})=\sum_{y,o}y\,p(y\mid a,o)\,p(o),$
(12)

and the front-door formula (Pearl, 1995a)
$\Psi^{\mathrm{FRONT}}_{a}(\cdot;\mathcal{G}):{\mathcal{M}}_{0}(V)\rightarrow\mathbb{R}$,

$\Psi^{\mathrm{FRONT}}_{a}(P;\mathcal{G})=\sum_{y,m}y\,p(m\mid
a)\sum_{a^{\prime}}p(y\mid a^{\prime},m)\,p(a^{\prime}).$ (13)

The notion of Markov equivalence is not directly applicable to our problem, as
two Markov equivalent graphs may not admit the same identifying formula for
the g-functional. This issue is fixed by the following refinement of Markov
equivalence.

######  Definition 2 (Causal Markov equivalence).

Two graphs $\mathcal{G}$ and $\mathcal{G}^{\prime}$ are causal Markov
equivalent with respect to the effect of $A$ on $Y$, denoted as
$\mathcal{G}\operatorname{\stackrel{{\scriptstyle
c}}{{\sim}}}\mathcal{G}^{\prime}$, if $\mathcal{G}$ and $\mathcal{G}^{\prime}$
are Markov equivalent and
$\Psi_{a}(P;\mathcal{G})=\Psi_{a}(P;\mathcal{G}^{\prime})$ for all
$P\in{\mathcal{M}}(\mathcal{G},V)$.

Guo and Perković (2021) showed that a causal Markov equivalence class can be
represented by a maximally oriented partially directed acyclic graph and
provided a polynomial-time algorithm to find the representation. In our
context, where $|A|=|Y|=1$, the following is an alternative characterization.

######  Proposition 1.

Let $\mathcal{G}$ and $\mathcal{G}^{\prime}$ be two directed acyclic graphs on
vertex set $V$, which contains the treatment $A$ and outcome $Y$. Suppose
$\mathcal{G}$ and $\mathcal{G}^{\prime}$ satisfy 1. Graphs $\mathcal{G}$ and
$\mathcal{G}^{\prime}$ are causal Markov equivalent with respect to the effect
of $A$ on $Y$ if and only if they are Markov equivalent and share the same
optimal adjustment set defined in Eq. 8.

For example, graphs $\mathcal{G}$ and $\check{\mathcal{G}}$ in Fig. 2.1 are
causal Markov equivalent.

###  3.4 Efficient influence function, uninformative variables and efficient
identifying formulae

We now review the elements of semiparametric theory that are relevant to our
derivations. An estimator $\widehat{\gamma}$ of a functional $\gamma(P)$ based
on $n$ independent observations $V^{(1)},\dots,V^{(n)}$ drawn from $P$ is said
to be asymptotically linear at $P$ if there exists a random variable
$\gamma_{P}^{1}(V)$, called the influence function of $\widehat{\gamma}$ at
$P$, such that $\operatorname{\mathbb{E}}_{P}\gamma_{P}^{1}(V)=0$,
$\operatorname{\mathrm{var}}_{P}\gamma_{P}^{1}(V)<\infty$ and
$n^{1/2}\left\\{\widehat{\gamma}-\gamma(P)\right\\}=n^{-1/2}\sum_{i=1}^{n}\gamma_{P}^{1}(V^{(i)})+o_{p}(1)$
as $n\rightarrow\infty$. For each asymptotically linear estimator
$\widehat{\gamma}$, there exists a unique such
$\gamma_{P}^{1}\left({V}\right)$. It follows that
$n^{1/2}\left\\{\widehat{\gamma}-\gamma\left(P\right)\right\\}$ converges in
distribution to a zero-mean normal distribution with variance
$\operatorname{\mathrm{var}}_{P}\gamma_{P}^{1}(V)$.

Given a collection of probability laws ${\mathcal{M}}(V)$ over $V$, an
estimator $\widehat{\gamma}$ of $\gamma(P)$ is said to be regular at $P$ if
its convergence to $\gamma(P)$ is locally uniform at $P$ in
${\mathcal{M}}(V)$. It is known that for a regular, i.e., pathwise-
differentiable, functional $\gamma$, there exists a random variable, denoted
by $\gamma_{P,\text{eff}}^{1}(V)$ and called the efficient influence function
of $\gamma$ at $P$ with respect to ${\mathcal{M}}(V)$, such that given any
regular asymptotically linear estimator $\widehat{\gamma}$ of $\gamma$ with
influence function $\gamma_{P}^{1}(V)$, we have
$\operatorname{\mathrm{var}}_{P}\gamma_{P}^{1}(V)\geq\operatorname{\mathrm{var}}_{P}\gamma_{P,\text{eff}}^{1}(V)$.
If equality holds, then the estimator $\widehat{\gamma}$ is said to be locally
semiparametric efficient at $P$ with respect to model ${\mathcal{M}}(V)$.
Further, it is said to be globally efficient if the equality holds for all $P$
in $\mathcal{M}(V)$. When ${\mathcal{M}}(V)$ is taken to be the nonparametric
model ${\mathcal{M}}_{0}(V)$, all regular asymptotically linear estimators
have the same influence function, which therefore coincides with the efficient
influence function with respect to ${\mathcal{M}}_{0}(V)$. For ease of
reference, we call it the nonparametric influence function and denote it by
$\gamma_{P,\text{NP}}^{1}(V)$. For more details, see van der Vaart (2000,
Chapter 25).

To define what it means for a variable to be uninformative, we need the next
result. For a law $P$ over $V$ and $V^{\prime}\subseteq V$, let
$P(V^{\prime})$ denote the marginal law over $V^{\prime}$. Similarly, for
model ${\mathcal{M}}(V)$ or ${\mathcal{M}}(\mathcal{G},V)$, we use
${\mathcal{M}}(V^{\prime})$ or ${\mathcal{M}}(\mathcal{G},V^{\prime})$ to
denote the induced marginal model over $V^{\prime}$, i.e.,
${\mathcal{M}}(V^{\prime})\equiv\\{P(V^{\prime}):P\in{\mathcal{M}}(V)\\}$ or
${\mathcal{M}}(\mathcal{G},V^{\prime})\equiv\\{P(V^{\prime}):P\in{\mathcal{M}}(\mathcal{G},V)\\}$;
see also Remark 1.

######  Lemma 3.2 (Proposition 17, Rotnitzky and Smucler, 2020).

Let ${\mathcal{M}}(V)$ be a semiparametric model for the law of a random
vector $V$. Suppose $V^{\prime}$ is a subvector of $V$. Let
${\mathcal{M}}(V^{\prime})$ be the induced marginal model over $V^{\prime}$.

Suppose $\gamma:{\mathcal{M}}(V)\rightarrow\mathbb{R}$ is a regular functional
with efficient influence function at $P$ equal to
$\gamma_{P,\text{eff}}^{1}\left({V}\right)$. Suppose there exists a regular
functional $\chi:{\mathcal{M}}(V^{\prime})\rightarrow\mathbb{R}$ such that
$\gamma(P)=\chi(P^{\prime})$ for every $P\in{\mathcal{M}}(V)$ and
$P^{\prime}\equiv P(V^{\prime})$. Suppose, furthermore, that
$\gamma_{P,\text{eff}}^{1}(V)$ depends on $V$ only through $V^{\prime}$. Let
$\chi_{P^{\prime},\text{eff}}^{1}(V^{\prime})$ be the efficient influence
function of $\chi(P^{\prime})$ in model ${\mathcal{M}}(V^{\prime})$ at
$P^{\prime}$. Then, for every law $P\in{\mathcal{M}}(V)$ over $V$ and its
corresponding marginal law $P^{\prime}\in{\mathcal{M}}(V^{\prime})$ over
$V^{\prime}$, $\gamma_{P,\text{eff}}^{1}(V)$ and
$\chi_{P^{\prime},\text{eff}}^{1}(V^{\prime})$, as functions of $V$ and
$V^{\prime}$, respectively, are identical $P$-almost everywhere.

This result tells us that to efficiently estimate $\gamma(P)$ under model
${\mathcal{M}}(V)$, we can discard the data on $V\setminus V^{\prime}$ and
recast the problem as one of efficiently estimating the functional
$\chi(P^{\prime})$ under model ${\mathcal{M}}(V^{\prime})$. This leads us to
make the following two definitions.

######  Definition 3 (Uninformative variables).

Given a model ${\mathcal{M}}(V)$ for law $P$ over $V$, we say that a subset of
variables $U\subseteq V$ is uninformative for estimating a regular functional
$\gamma(P)$ under ${\mathcal{M}}(V)$ if $V^{\prime}=V\setminus U$ satisfies
the assumptions of Lemma 3.2.

######  Definition 4 (Irreducible informative variables).

Let ${\mathcal{M}}(V)$ be a model for law $P$ over variables $V$. The set
$V^{\ast}\subseteq V$ is said to be irreducible informative for estimating a
regular functional $\gamma(P)$ under ${\mathcal{M}}(V)$ if (i) $V\setminus
V^{\ast}$ is uninformative and (ii) no proper superset of $V\setminus
V^{\ast}$ is uninformative.

######  Lemma 3.3.

Suppose ${\mathcal{M}}(V)$ is a model for law $P$ over variables $V$, and let
$\gamma:{\mathcal{M}}(V)\rightarrow\mathbb{R}$ be a regular functional. Let
$\gamma_{P,\text{eff}}^{1}(V)$ be the corresponding efficient influence
function. Suppose $V^{\ast}\subseteq V$ satisfies the following:

  1. (i)

$\gamma_{P,\text{eff}}^{1}(V)$ depends on $V$ only through $V^{\ast}$ for
every $P\in{\mathcal{M}}(V)$;

  2. (ii)

there exists a functional $\chi:{\mathcal{M}}(V^{\ast})\rightarrow\mathbb{R}$
such that $\chi(P^{\ast})=\gamma(P)$ for every $P\in{\mathcal{M}}(V)$ and
$P^{\ast}\equiv P(V^{\ast})$;

  3. (iii)

for each $V_{j}\in V^{\ast}$, there exists a nondegenerate law
$P_{j}\in{\mathcal{M}}(V)$ such that $\gamma_{P_{j},\text{eff}}^{1}(V)$ is not
a constant function of $V_{j}$ with probability one.

Then $V^{\ast}$ is the unique irreducible informative set.

From Section 3.3, in the context of causal graphs, we see that typically there
are more than one identifying formula for the g-functional. Our next two
definitions, based on considerations of efficiency and informativeness, help
us compare and choose between different identifying formulae.

Let us first look at efficiency. As before, we let ${\mathcal{M}}_{0}(V)$ be
the nonparametric model over $V$ and let ${\mathcal{M}}(V)$ be a
semiparametric submodel. Suppose $\gamma(P)$ and $\chi(P)$ are two identifying
formulae, i.e., regular real-valued functionals defined on
${\mathcal{M}}_{0}(V)$, such that they agree on ${\mathcal{M}}(V)$. As such,
they must have the same efficient influence function with respect to
${\mathcal{M}}(V)$, i.e.,
$\gamma^{1}_{P,\text{eff}}(V)=\chi^{1}_{P,\text{eff}}(V)$ for every
$P\in{\mathcal{M}}(V)$. Suppose that $V$ is discrete and consider the plugin
estimators $\gamma(\mathbb{P}_{n})$ and $\chi(\mathbb{P}_{n})$, where
$\mathbb{P}_{n}$ is the empirical measure. Then, $\gamma(\mathbb{P}_{n})$ and
$\chi(\mathbb{P}_{n})$ are regular asymptotically linear with influence
functions equal to the nonparametric influence functions
$\gamma^{1}_{P,\text{NP}}(V)$ and $\chi^{1}_{P,\text{NP}}(V)$ for every
$P\in{\mathcal{M}}_{0}(V)$. Suppose that
$\gamma^{1}_{P,\text{NP}}(V)=\gamma^{1}_{P,\text{eff}}(V)$ for every
$P\in{\mathcal{M}}(V)$ but that, in contrast,
$\chi^{1}_{P^{\prime},\text{NP}}(V)\neq\chi^{1}_{P^{\prime},\text{eff}}(V)$
for some $P^{\prime}\in{\mathcal{M}}(V)$. Then, in view of the concepts
introduced at the beginning of this subsection, with respect to the
semiparametric model ${\mathcal{M}}(V)$, the estimator
$\gamma(\mathbb{P}_{n})$ is globally efficient, but $\chi(\mathbb{P}_{n})$ is
not. Then, for estimating functional $\gamma(P)=\chi(P)$ defined on model
${\mathcal{M}}(V)$, we say $\gamma(P)$ is an efficient identifying formula,
but $\chi(P)$ is an inefficient identifying formula. This gives us a concrete
way of defining whether an identifying formula is efficient. In below, we
provide a definition for the general case where $V$ need not be discrete.

######  Definition 5 (Efficient identifying formula).

Consider a semiparametric model
${\mathcal{M}}(V)\subseteq{\mathcal{M}}_{0}(V)$ and a regular functional
$\gamma:{\mathcal{M}}(V)\rightarrow\mathbb{R}$. Let
$\gamma^{1}_{P,\text{eff}}(V)$ be its efficient influence function with
respect to ${\mathcal{M}}(V)$. An identifying formula
$\chi:{\mathcal{M}}_{0}(V)\rightarrow\mathbb{R}$ for the functional $\gamma$
is called efficient if
$\chi^{1}_{P,\text{NP}}(V)=\gamma^{1}_{P,\text{eff}}(V)$ $P$-almost everywhere
for every $P\in{\mathcal{M}}(V)$.

From Eqs. 6 and 10, when $V$ is discrete, it is clear that the maximum
likelihood estimator of $\Psi_{a}(P;\mathcal{G})$ is simply the plugin
estimator $\Psi_{a}(\mathbb{P}_{n};\mathcal{G})$. More generally, we have the
following result for an arbitrary vector $V$.

######  Lemma 3.4.

For graph $\mathcal{G}$ satisfying 1, the g-formula
$\Psi_{a}(\cdot;\mathcal{G}):{\mathcal{M}}_{0}(V)\rightarrow\mathbb{R}$ in Eq.
10 is an efficient identifying formula for the g-functional
$\Psi_{a}(\cdot;\mathcal{G}):{\mathcal{M}}(\mathcal{G},V)\rightarrow\mathbb{R}$.

As mentioned in Section 2, more than one efficient identifying formula may
exist for the same functional, such as the g-formulae associated with
$\mathcal{G}^{\ast}$ and $\mathcal{G}$ in Fig. 2.1 for our motivating example.
In this case, we argue that the g-formula associated with $\mathcal{G}^{\ast}$
should be preferred over that associated with $\mathcal{G}$, as the former
requires measuring fewer variables than the latter. This motivates our next
definition concerning informativeness.

######  Definition 6 (Irreducible identifying formula).

An identifying formula $\chi:{\mathcal{M}}_{0}(V)\rightarrow\mathbb{R}$ for a
regular functional $\gamma:{\mathcal{M}}(V)\rightarrow\mathbb{R}$ is called
irreducible if there exists $V^{\ast}\subseteq V$, which is irreducible
informative for estimating $\gamma(P)$ under ${\mathcal{M}}(V)$, such that
$P(V^{\ast})=P^{\prime}(V^{\ast})$ implies $\chi(P)=\chi(P^{\prime})$ for
every $P,P^{\prime}\in{\mathcal{M}}_{0}(V)$, i.e., $\chi(P)$ depends on $P$
only through $P(V^{\ast})$.

In what follows, we will first characterize the irreducible informative set
$V^{\ast}$ and then construct the reduced graph $\mathcal{G}^{\ast}$ to
represent the marginal model over $V^{\ast}$. In particular, our general
result would imply that the g-formula associated with $\mathcal{G}^{\ast}$ in
Fig. 2.1 is an identifying formula that is both efficient and irreducible.

##  4 Characterizing the uninformative variables

###  4.1 Efficient influence function

We now specialize the concepts and results in the preceding section to show
that for estimating the g-functional $\Psi_{a}(P;\mathcal{G})$ under the
Bayesian network model ${\mathcal{M}}(\mathcal{G},V)$, there exists a unique
set of irreducible informative variables, which we denote by $V^{\ast}\equiv
V^{\ast}(\mathcal{G})$ throughout. By Lemma 3.3, this can be established if we
can find $V^{\ast}\subseteq V$ such that (i) the efficient influence function
$\Psi_{a,P,\text{eff}}^{1}(V)$ depends on $V$ only through $V^{\ast}$ for
every $P\in{\mathcal{M}}(\mathcal{G},V)$; (ii) $\Psi_{a}(P;\mathcal{G})$
depends on $P\in{\mathcal{M}}(\mathcal{G},V)$ only through the $V^{\ast}$
margin of $P$; and (iii) for every $V_{j}\in V^{\ast}$, there exists a
nondegenerate law $P\in{\mathcal{M}}(\mathcal{G},V)$ such that
$\Psi_{a,P,\text{eff}}^{1}(V)$ depends nontrivially on $V_{j}$.

Without loss of generality, here we focus on finding the informative variables
for the g-functional, as opposed to the average treatment effects, which are
contrasts or, more generally, linear combinations of g-functionals that
correspond to different treatment levels. Indeed, as shown in Lemma F.1 of the
Appendix, the set of irreducible informative variables for these effects is
identical to $V^{\ast}(\mathcal{G})$.

We will perform these tasks invoking an expression for
$\Psi_{a,P,\text{eff}}^{1}(V;\mathcal{G})$, which is derived in Rotnitzky and
Smucler (2020) and stated in the next lemma. Let $\mathbb{I}_{a}(A)$ be the
indicator of $A$ being equal to $a$. Define
$T_{a,P}\equiv\mathbb{I}_{a}(A)Y/P\left(A=a\mid O_{\min}\right)$ and
$b_{a,P}(O)\equiv\operatorname{\mathbb{E}}_{P}\left(Y\mid A=a,O\right)$, where
$O\equiv O(\mathcal{G})$ and $O_{\min}\equiv O_{\min}(\mathcal{G})$.

######  Lemma 4.1 (Theorem 7, Rotnitzky and Smucler, 2020).

Let $\mathcal{G}$ be a directed acyclic graph on a vertex set $V$ satisfying
1. Suppose $P\in{\mathcal{M}}(\mathcal{G},V)$ and that
$W(\mathcal{G})=\\{W_{1},\dots,W_{J}\\}$ and
$M(\mathcal{G})=\\{M_{1},\dots,M_{K-1},M_{K}\equiv Y\\}$ are as defined in
Section 3.2. Then the efficient influence function for estimating
$\Psi_{a}(P;\mathcal{G})$ with respect to model ${\mathcal{M}}(\mathcal{G},V)$
is given by

$\Psi_{a,P,\text{eff}}^{1}(V;\mathcal{G})=\sum_{j=1}^{J}\big{[}\operatorname{\mathbb{E}}\left\\{b_{a,P}(O)\mid
W_{j},\operatorname{Pa}(W_{j},\mathcal{G})\right\\}-\operatorname{\mathbb{E}}\left\\{b_{a,P}(O)\mid\operatorname{Pa}(W_{j},\mathcal{G})\right\\}\big{]}\\\
+\sum_{k=1}^{K}\big{[}\operatorname{\mathbb{E}}\left\\{T_{a,P}\mid
M_{k},\operatorname{Pa}(M_{k},\mathcal{G})\right\\}-\operatorname{\mathbb{E}}\left\\{T_{a,P}\mid\operatorname{Pa}(M_{k},\mathcal{G})\right\\}\big{]}.$

In the rest of this section, we classify the uninformative variables into two
types: redundant and non-redundant. The redundant variables are those that can
be identified from causal Markov equivalent graphs. In contrast, identifying
the non-redundant, uninformative variables is less straightforward and
sometimes counterintuitive. Nevertheless, we will develop a set of graphical
criteria to characterize them both. The proofs for this section are given in
Appendix F.

###  4.2 Redundant variables

We start with the following result, which is immediate in view of Eq. 10 and
Lemma 4.1.

######  Lemma 4.2.

Given $\mathcal{G}$ satisfying 1, $N(\mathcal{G})\,\dot{\cup}\,I(\mathcal{G})$
is uninformative for estimating $\Psi_{a}(P;\mathcal{G})$ under
${\mathcal{M}}(\mathcal{G},V)$.

By Definition 3, informativeness is a property defined with respect to a model
and a functional. The notion of causal Markov equivalence leads us to the
following definition.

######  Definition 7 (Redundant variables).

Given a graph $\mathcal{G}$ satisfying 1, the set of redundant variables in
$\mathcal{G}$ for estimating $\Psi_{a}(P;\mathcal{G})$ under
${\mathcal{M}}(\mathcal{G},V)$ is

$\bigcup_{\mathcal{G}^{\prime}\operatorname{\stackrel{{\scriptstyle
c}}{{\sim}}}\mathcal{G}}N(\mathcal{G}^{\prime})\cup I(\mathcal{G}^{\prime}).$

######  Proposition 2.

Given $\mathcal{G}$ satisfying 1, the redundant variables are uninformative
for estimating $\Psi_{a}(P;\mathcal{G})$ under ${\mathcal{M}}(\mathcal{G},V)$.

Revisiting our motivating example on graph $\mathcal{G}$ in Fig. 2.1(a), the
redundant variables are $\\{I_{1},W_{1}\\}$, which can be summed out from the
g-formula; see Eq. 2. They can also be identified from the causal Markov
equivalent graph $\check{\mathcal{G}}$ shown in Fig. 2.1(e).

A surprising phenomenon in this example, as indicated earlier in Section 2, is
that $W_{4}$, despite being nonredundant, is actually uninformative for
estimating $\Psi_{a}(P;\mathcal{G})$ under the Bayesian network model
represented by $\mathcal{G}$. To see this, by Lemma 4.1, observe that
$\Psi_{a,P,\text{eff}}^{1}(V;\mathcal{G})$ could depend on $W_{4}$ only
through the sum

$\begin{split}&\quad\operatorname{\mathbb{E}}\\{b_{a,P}(O_{1})\mid
W_{4},\operatorname{Pa}(W_{4})\\}+\operatorname{\mathbb{E}}\\{b_{a,P}(O_{1})\mid
O_{1},\operatorname{Pa}(O_{1})\\}-\operatorname{\mathbb{E}}\\{b_{a,P}(O_{1})\mid\operatorname{Pa}(O_{1})\\}\\\
&=\operatorname{\mathbb{E}}\\{b_{a,P}(O_{1})\mid
W_{4},W_{2},W_{3}\\}+b_{a,P}(O_{1})-\operatorname{\mathbb{E}}\\{b_{a,P}(O_{1})\mid
W_{4}\\}.\end{split}$

However, model ${\mathcal{M}}(\mathcal{G},V)$ implies
$O_{1}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}W_{2},W_{3}\mid
W_{4}$, so the sum reduces to $b_{a,P}(O_{1})$, which does not depend on
$W_{4}$. In addition, under the model, $\Psi_{a}(P;\mathcal{G})$ coincides
with $\Psi_{a,O_{1}}^{\mathrm{ADJ}}(P;\mathcal{G})$, which depends on $P$ only
through the marginal law $P(A,Y,O_{1})$. In view of Definitions 3 and 3.2,
$\\{I_{1},W_{1},W_{4}\\}$ are uninformative. Those variables that vanish like
$W_{4}$ are called nonredundant, uninformative variables. They are more subtle
as they cannot be deduced from simple ancestral relations or causal Markov
equivalence. Next, we develop graphical results towards a complete
characterization.

###  4.3 Graphical criteria

In this subsection we will often omit $\mathcal{G}$ from the vertex sets
introduced in Section 3.2 to reduce clutter. First, we show that our search
for uninformative variables can be limited to $(W\setminus
O)\cup(M\setminus\\{Y\\})$.

######  Lemma 4.3.

Suppose that $\mathcal{G}$ is a directed acyclic graph on $V$ satisfying 1.
For any $U\subseteq V$ that is uninformative for estimating
$\Psi_{a}(P;\mathcal{G})$ under ${\mathcal{M}}(\mathcal{G},V)$, we have
$U\cap\\{\\{A,Y\\}\cup O(\mathcal{G})\\}=\emptyset$.

To proceed with our search for uninformative variables, it suffices to
identify variables from $W\setminus O$ or $M\setminus\\{Y\\}$ that vanish from
the efficient influence function at every law in the model. This follows from
Definition 3 and Lemma 3.2 given that (i) $\Psi_{a}(P;\mathcal{G})=$
$\Psi_{a,O}^{\mathrm{ADJ}}(P;\mathcal{G})$ on ${\mathcal{M}}(\mathcal{G},V)$
and (ii) $\Psi_{a,O}^{\mathrm{ADJ}}(P;\mathcal{G})$ depends on $P$ only
through the marginal law of $O\cup\\{A,Y\\}$.

Let us now identify uninformative variables in $W\setminus O$. Every $W_{j}\in
W\setminus O$ satisfies $W_{j}\mapsto O$, so $\operatorname{Ch}(W_{j})\cap
W\neq\emptyset$. Let us write $\operatorname{Ch}(W_{j})\cap
W=\\{W_{j_{1}},\dots,W_{j_{r}}\\}$, indexed topologically for
$j_{1}\leq\dots\leq j_{r}$ and $r\geq 1$, and define $W_{j_{0}}\equiv W_{j}$.
We observe that $\Psi_{a,P,\text{eff}}^{1}(V;\mathcal{G})$ in Lemma 4.1
depends on $W_{j}$ only through

$\Gamma(W_{j})\equiv\operatorname{\mathbb{E}}\left\\{b_{a}(O)\mid
W_{j},\operatorname{Pa}(W_{j})\right\\}+\sum_{t=1}^{r}\left[\operatorname{\mathbb{E}}\left\\{b_{a}(O)\mid
W_{j_{t}},\operatorname{Pa}(W_{j_{t}})\right\\}-\operatorname{\mathbb{E}}\left\\{b_{a}(O)\mid\operatorname{Pa}(W_{j_{t}})\right\\}\right].$
(14)

To analyze $\Gamma(W_{j})$, define $E^{+}_{j}$ as the smallest subset of
$\operatorname{Pa}(W_{j})\cup\\{W_{j}\\}$ such that

$\operatorname{Pa}(W_{j})\cup\\{W_{j}\\}\setminus
E^{+}_{j}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}O\mid
E^{+}_{j},$

and $E^{-}_{j}$ as the smallest subset of $\operatorname{Pa}(W_{j})$ such that

$\operatorname{Pa}(W_{j})\setminus
E^{-}_{j}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}O\mid
E^{-}_{j}.$

Sets $E^{+}_{j}$ and $E^{-}_{j}$ are uniquely defined by the graphoid
properties of d-separations. With these definitions and the corresponding
conditional independences, Eq. 14 becomes

$\begin{split}\Gamma(W_{j})=\operatorname{\mathbb{E}}\left\\{b_{a}(O)\mid
E^{+}_{j}\right\\}&+\operatorname{\mathbb{E}}\left\\{b_{a}(O)\mid
E^{+}_{j_{1}}\right\\}+\dots+\operatorname{\mathbb{E}}\left\\{b_{a}(O)\mid
E^{+}_{j_{r-1}}\right\\}+\operatorname{\mathbb{E}}\left\\{b_{a}(O)\mid
E^{+}_{j_{r}}\right\\}\\\ &-\operatorname{\mathbb{E}}\left\\{b_{a}(O)\mid
E^{-}_{j_{1}}\right\\}-\dots-\operatorname{\mathbb{E}}\left\\{b_{a}(O)\mid
E^{-}_{j_{r-1}}\right\\}-\operatorname{\mathbb{E}}\left\\{b_{a}(O)\mid
E^{-}_{j_{r}}\right\\}.\end{split}$ (15)

The following lemma contains important properties of the sets $E_{j}^{+}$ and
$E_{j}^{-}$.

######  Lemma 4.4.

The following properties hold:

  1. (i)

$W_{j}\in E^{+}_{j}$;

  2. (ii)

if $r>1$, then $W_{j}\in E^{+}_{j_{t}}$ for $t=1,\dots,r-1$;

  3. (iii)

$E^{-}_{j}=\operatorname{Pa}(W_{j})$.

The variable $W_{j}$ is uninformative if $\Gamma(W_{j})$ does not depend on
$W_{j}$; for this to happen, plausibly, in Eq. 15 each $E^{-}$ term from the
second line cancels exactly with one $E^{+}$ term from the first line, and the
remaining term in the first line does not depend on $W_{j}$. By Lemma 4.4(ii),
the remaining term must be the last term in the first line, which should
satisfy $W_{j}\notin E^{+}_{j_{r}}$. Now suppose that $E^{+}_{j_{r-1}}$
cancels with $E^{-}_{j_{t}}$ from the second line. Then, by Lemma 4.4(i) and
(ii), this implies $W_{j_{r-1}}\rightarrow W_{j_{t}}$, which requires $t=r$ to
be compatible with the topological ordering. Continuing this argument, we see
that $E^{+}_{j_{r-2}}$ cancels with $E^{-}_{j_{r-1}}$, and so forth. This is
summarized as follows.

######  Lemma 4.5.

Under 1, variable $W_{j}$ is uninformative if (i) $W_{j}\notin E^{+}_{j_{r}}$
and (ii) $E^{+}_{j_{t-1}}=E^{-}_{j_{t}}$ for $t=1,\dots,r$.

These conditions are further equivalent to the following graphical criterion.

######  Lemma 4.6 (W-criterion).

Suppose $\mathcal{G}$ satisfies 1 and that $W_{j}\in W\setminus O$ and
$\operatorname{Ch}(W_{j})\cap W=\\{W_{j_{1}},\dots,W_{j_{r}}\\}$, indexed
topologically for $r\geq 1$; define $W_{j_{0}}\equiv W_{j}$. Then the variable
$W_{j}$ is uninformative if the following conditions are satisfied:

  1. (i)

$W_{j}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}O\mid\\{W_{j_{r}}\\}\cup\operatorname{Pa}(W_{j_{r}})\setminus\\{W_{j}\\}$;

  2. (ii)

for $t=1,\dots,r$ one has

    1. (a)

$W_{j_{t-1}}\rightarrow W_{j_{t}}$;

    2. (b)

$\operatorname{Pa}(W_{j_{t}})\subseteq\operatorname{Pa}(W_{j_{t-1}})\cup\\{W_{j_{t-1}}\\}$;

    3. (c)

$\operatorname{Pa}(W_{j_{t-1}})\setminus\operatorname{Pa}(W_{j_{t}})\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}O\mid\operatorname{Pa}(W_{j_{t}})$.

As an example, let us check that $W_{4}$ in Fig. 2.1(a) satisfies the
W-criterion. Observe that $r=1$ and $W_{j_{r}}=O_{1}$. Condition (i) is
trivial: recall that
$W_{4}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}O_{1}\mid
O_{1}$ is parsed as
$W_{4}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}\emptyset\mid
O_{1}$, which is true by our convention. For condition (ii), we check that (a)
$W_{4}\rightarrow O_{1}$, (b) $W_{4}\subset\\{W_{2},W_{3},W_{4}\\}$ and (c)
$W_{2},W_{3}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}O_{1}\mid
W_{4}$. In contrast, we see that $W_{2}$ and $W_{3}$ fail the W-criterion, in
particular condition (ii)(b).

By a similar line of reasoning, we derive the corresponding criterion for the
set of mediators.

######  Lemma 4.7 (M-criterion).

Suppose $\mathcal{G}$ satisfies 1 and that $M_{i}\in M\setminus\\{Y\\}$ and
$\operatorname{Ch}(M_{i})\cap M=\\{M_{i_{1}},\dots,M_{i_{k}}\\}$, indexed
topologically for $k\geq 1$; define $M_{i_{0}}\equiv M_{i}$. Then the variable
$M_{i}$ is uninformative if the following conditions are satisfied:

  1. (i)

$M_{i}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}\\{A,Y\\}\cup
O_{\min}\mid\\{M_{i_{k}}\\}\cup\operatorname{Pa}(M_{i_{k}})\setminus\\{M_{i}\\}$;

  2. (ii)

for $t=1,\dots,k$ one has

    1. (a)

$M_{i_{t-1}}\rightarrow M_{i_{t}}$;

    2. (b)

$\operatorname{Pa}(M_{i_{t}})\subseteq\operatorname{Pa}(M_{i_{t-1}})\cup\\{M_{i_{t-1}}\\}$;

    3. (c)

$\operatorname{Pa}(M_{i_{t-1}})\setminus\operatorname{Pa}(M_{i_{t}})\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}\\{A,Y\\}\cup
O_{\min}\mid\operatorname{Pa}(M_{i_{t}})$.

We show the soundness of W- and M-criterion in Section F.6. Our first main
result shows that our graphical characterization is also complete.

######  Theorem 4.1 (Graphical criteria for irreducible, informative
variables).

Let $\mathcal{G}$ be a directed acyclic graph on a vertex set $V$ that
satisfies 1. Suppose that $A\in V$ is a discrete treatment and $Y\in V$ is the
outcome of interest. Then there exists a unique set of irreducible informative
variables for estimating $\Psi_{a}(P;\mathcal{G})$ under
${\mathcal{M}}(\mathcal{G},V)$,

$V^{\ast}(\mathcal{G})\equiv\\{A,Y\\}\cup O\cup\\{W_{j}\in W\setminus
O:\text{$W_{j}$ fails the W-criterion}\\}\\\ \cup\\{M_{i}\in
M\setminus\\{Y\\}:\text{$M_{i}$ fails the M-criterion}\\},$

where $O\equiv O(\mathcal{G})$, $W\equiv W(\mathcal{G})$ and $M\equiv
M(\mathcal{G})$ are defined in Section 3.2.

To prove Theorem 4.1, for each variable in $W\setminus O$ and
$M\setminus\\{Y\\}$ that fails the corresponding criterion, we show in
Appendices F, G and H that there exists a nondegenerate law
$P\in{\mathcal{M}}(\mathcal{G},V)$ such that
$\Psi^{1}_{a,P,\text{eff}}(V;\mathcal{G})$ depends nontrivially on the
variable.

##  5 Graph reduction and the efficient irreducible g-formula

###  5.1 Marginal model

The results of the preceding section imply that we do not lose information by
discarding the variables excluded from the set $V^{\ast}\equiv
V^{\ast}(\mathcal{G})$ in Theorem 4.1. In what follows, we will write
$P^{\ast}$ for the marginal law $P(V^{\ast})$. Also, recall from Section 3.4
that ${\mathcal{M}}(\mathcal{G};V^{\ast})$ refers to the marginal model over
$P^{\ast}$ induced by $P\in{\mathcal{M}}(\mathcal{G},V)$. In this section, we
will characterize the marginal model ${\mathcal{M}}(\mathcal{G};V^{\ast})$ and
then re-express the g-functional as a functional of $P^{\ast}$ in
${\mathcal{M}}(\mathcal{G};V^{\ast})$.

Characterizing the marginal model is nontrivial, even when the state space of
the variables that are marginalized over is unrestricted. In general, the
margin of a Bayesian network can be a complicated statistical model subject to
both equality and inequality constraints. The equalities consist of
conditional independences and their generalizations known as the nested Markov
properties; see Shpitser et al. (2014); Evans (2018). The inequalities are
related to Bell’s inequalities (Gill, 2014) and are often hard to characterize
(Pearl, 1995b; Bonet, 2001). Fortunately, we can avoid these complications
because, as will be shown later, under our definition of Bayesian networks in
Section 3.2 where the state space of each variable is sufficiently large, the
marginal model ${\mathcal{M}}(\mathcal{G};V^{\ast})$ is exactly a Bayesian
network model represented by a certain directed acyclic graph
$\mathcal{G}^{\ast}$ over vertices $V^{\ast}$. Further, the g-formula
associated with $\mathcal{G}^{\ast}$ immediately identifies the g-functional
of $P$ as a functional of $P^{\ast}$. Finally, this formula is irreducible and
efficient.

The construction of $\mathcal{G}^{\ast}$ can be viewed as iteratively
projecting out all the uninformative variables, such that each time a variable
or a set of variables are projected out, the resulting graph represents the
marginal model over the remaining variables. We will start by projecting out
variables in $N(\mathcal{G})$ and $I(\mathcal{G})$ altogether.

###  5.2 Projecting out $N(\mathcal{G})$ and $I(\mathcal{G})$

######  Lemma 5.1 (Marginalizing over $N(\mathcal{G})$ and $I(\mathcal{G})$).

Let $\mathcal{G}$ be a directed acyclic graph on a vertex set $V$ satisfying
1. Let $N(\mathcal{G})$ and $I(\mathcal{G})$ be defined as in Section 3.2 and
let $V^{0}\equiv V\setminus\\{N(\mathcal{G})\cup I(\mathcal{G})\\}$. Let graph
$\mathcal{G}^{0}$ be constructed from $\mathcal{G}$ as follows. First, for
every $V_{i},V_{j}\in V^{0}$ such that $V_{i}\mapsto V_{j}$ through a causal
path on which every non-endpoint vertex is in $I(\mathcal{G})$, add an edge
$V_{i}\rightarrow V_{j}$ if the edge is not present. Next, remove vertices in
$N(\mathcal{G})\cup I(\mathcal{G})$ and their associated edges. Call the
resulting graph $\mathcal{G}^{0}$. Then $\mathcal{G}^{0}$ is a directed
acyclic graph over $V^{0}$ and
${\mathcal{M}}(\mathcal{G},V^{0})={\mathcal{M}}(\mathcal{G}^{0},V^{0})$.

See Section D.1 for a proof. The graph $\mathcal{G}^{0}$ is a reformulation of
the graph produced by Rotnitzky and Smucler (2020, Algorithm 1). As an
example, in Fig. 2.1, projecting out $N(\check{\mathcal{G}})\cup
I(\check{\mathcal{G}})=\\{W_{1},I_{1}\\}$ from graph $\check{\mathcal{G}}$
leads to graph $\mathcal{G}^{\prime}$.

###  5.3 Projecting out the remaining uninformative variables

By exploiting the graphical structures in the W- and M-criterion and using the
results on graphs for representing margins of Bayesian networks due to Evans
(2018), we show in Section D.2 that the remaining uninformative variables in
$W(\mathcal{G})\cup M(\mathcal{G})$ can be projected out as well, one at a
time. The projection is defined as follows.

######  Definition 8.

Let $\mathcal{G}$ be a directed acyclic graph on a vertex set $V$. For
$V_{i}\in V$, suppose that $\operatorname{Ch}(V_{i},\mathcal{G})$ is
topologically ordered as $\pi=(V_{i_{1}},\dots,V_{i_{l}})$ for $l\geq 1$ and
let $V_{i_{0}}\equiv V_{i}$. Let $\mathcal{G}_{-V_{i},\pi}$ be a graph on
vertices $V\setminus\\{V_{i}\\}$, formed by adding an edge $V_{k}\rightarrow
V_{i_{j}}$ to $\mathcal{G}$ if the edge is not already present, for every
$V_{k}\in\operatorname{Pa}(V_{i},\mathcal{G})\cup\\{V_{i_{0}},\dots,V_{i_{j-1}}\\}$
and every $j=1,\dots,l$, and then removing $V_{i}$ and its associated edges.

In other words, all edges from $\operatorname{Pa}(V_{i},\mathcal{G})$ to
$\operatorname{Ch}(V_{i},\mathcal{G})$ and all edges among
$\operatorname{Ch}(V_{i},\mathcal{G})$ that are compatible with the
topological ordering $\pi$ are saturated before $V_{i}$ is removed. In
contrast to the latent projection of Verma and Pearl (1990), the projection
defined above results in a directed acyclic graph; compare Fig. 2.1(c) and
(d).

######  Lemma 5.2.

Let $\mathcal{G}$ be a directed acyclic graph on vertices $V$. Let $V_{i}\in
V$, whose children are topologically sorted as
$\pi=(V_{i_{1}},\dots,V_{i_{l}})$ for $l\geq 1$. Suppose that

$\operatorname{Pa}(V_{i_{j}},\mathcal{G})\subseteq\\{V_{i_{j-1}}\\}\cup\operatorname{Pa}(V_{i_{j-1}},\mathcal{G}),\quad
j=1,\dots,l-1,$ (16)

where $V_{i_{0}}\equiv V_{i}$. Then, $\mathcal{G}_{-V_{i},\pi}$ is a directed
acyclic graph on $V\setminus\\{V_{i}\\}$ and
${\mathcal{M}}(\mathcal{G},V\setminus\\{V_{i}\\})={\mathcal{M}}(\mathcal{G}_{-V_{i},\pi},V\setminus\\{V_{i}\\})$.

Lemma 5.2 can be specialized to any uninformative vertex in $W$ or $M$ as
follows.

######  Lemma 5.3.

Let $\mathcal{G}$ be a directed acyclic graph on a vertex set $V$. Suppose
that $\mathcal{G}$ satisfies 1 and $N(\mathcal{G})=I(\mathcal{G})=\emptyset$.
Consider a vertex $V_{i}\in V\setminus V^{\ast}(\mathcal{G})$. If $V_{i}\in
W(\mathcal{G})$, suppose $V_{i}\equiv W_{i}$ and let

$\pi=\begin{cases}(W_{i_{1}},\dots,W_{i_{l}}),\quad&A\notin\operatorname{Ch}(W_{i},\mathcal{G})\\\
(W_{i_{1}},\dots,W_{i_{l}},A),\quad&A\in\operatorname{Ch}(W_{i},\mathcal{G})\end{cases},$
(17)

where $\operatorname{Ch}(W_{i},\mathcal{G})\cap
W(\mathcal{G})=\\{W_{i_{1}},\dots,W_{i_{l}}\\}$ is uniquely topologically
sorted. Otherwise, $V_{i}\equiv M_{i}$ for some $M_{i}\in M(\mathcal{G})$ and
let

$\pi=(M_{i_{1}},\dots,M_{i_{l}})=\operatorname{Ch}(M_{i},\mathcal{G}),$ (18)

which is uniquely topologically sorted. Then

${\mathcal{M}}(\mathcal{G},V\setminus\\{V_{i}\\})={\mathcal{M}}(\mathcal{G}_{-V_{i},\pi},V\setminus\\{V_{i}\\}),\quad
V^{\ast}(\mathcal{G}_{-V_{i},\pi})=V^{\ast}(\mathcal{G}).$

In other words, by projecting out an uninformative variable $V_{i}\in W\cup M$
from a graph $\mathcal{G}$ whose $N(\mathcal{G})$ and $I(\mathcal{G})$ are
empty, the resulting graph $\mathcal{G}_{-V_{i},\pi}$ represents the marginal
model over the remaining variables, and preserves the same set of irreducible
informative variables given by Theorem 4.1.

###  5.4 Graph reduction algorithm and properties of the reduced graph

The graph reduction procedure is presented in Algorithm 1. In the algorithm
each vertex is visited once. As checking any d-separation takes a polynomial
time of $|V|$, the algorithm also finishes in a polynomial time of $|V|$. The
algorithm is implemented in the R package reduceDAG, available from
https://github.com/richardkwo/reduceDAG.

Input: Graph $\mathcal{G}$ on vertex set $V$ satisfying 1

Output: Reduced graph $\mathcal{G}^{\ast}$ that represents
${\mathcal{M}}(\mathcal{G},V^{\ast})$

$V^{\ast}\leftarrow\\{A\\}\cup W(\mathcal{G})\cup M(\mathcal{G})$

$\mathcal{G}^{\ast}\leftarrow\mathcal{G}^{0}$ defined in Lemma 5.1

for  _$V_{i}\in V^{\ast}\setminus\\{\\{A,Y\\}\cup O(\mathcal{G})\\}$_ do

if  _$V_{i}\in W$ and $V_{i}$ satisfies the W-criterion in Lemma 4.6_ then

$V^{\ast}\leftarrow V^{\ast}\setminus\\{V_{i}\\}$

$\mathcal{G}^{\ast}\leftarrow\mathcal{G}^{\ast}_{-V_{i},\pi}$ with $\pi$
defined in Eq. 17

else if  _$V_{i}\in M$ and $V_{i}$ satisfies the M-criterion in Lemma 4.7_
then

$V^{\ast}\leftarrow V^{\ast}\setminus\\{V_{i}\\}$

$\mathcal{G}^{\ast}\leftarrow\mathcal{G}^{\ast}_{-V_{i},\pi}$ with $\pi$
defined in Eq. 18

return _$\mathcal{G}^{\ast}$_

Algorithm 1 Graph reduction algorithm

The properties of the reduced graph are summarized by our next main result;
see Appendix D for its proof.

######  Theorem 5.1.

Let $\mathcal{G}$ be a directed acyclic graph on a vertex set $V$ that
satisfies 1. Suppose $A\in V$ is a discrete treatment and $Y\in V$ is the
outcome of interest. Let $\mathcal{G}^{\ast}$ be the output of Algorithm 1
resulting from input $\mathcal{G}$. Let $V^{\ast}\equiv V^{\ast}(\mathcal{G})$
be the set of irreducible informative variables given in Theorem 4.1. Also,
let $P^{\ast}\equiv P(V^{\ast})$ and define
$\Psi_{a}(P;\mathcal{G}^{\ast})\equiv\Psi_{a}(P^{\ast};\mathcal{G}^{\ast})$.
The graph $\mathcal{G}^{\ast}$ satisfies the following properties:

  1. (i)

$\mathcal{G}^{\ast}$ is a directed acyclic graph on vertices $V^{\ast}$;

  2. (ii)

$\mathcal{G}^{\ast}$ does not depend on the order in which vertices are
visited in the for-loop of Algorithm 1;

  3. (iii)

${\mathcal{M}}(\mathcal{G},V^{\ast})={\mathcal{M}}(\mathcal{G}^{\ast},V^{\ast})$;

  4. (iv)

$\Psi_{a}(P;\mathcal{G})=\Psi_{a}(P;\mathcal{G}^{\ast})$ for every
$P\in{\mathcal{M}}(\mathcal{G};V)$;

  5. (v)

for every $P\in{\mathcal{M}}(\mathcal{G},V)$, the efficient influence
functions $\Psi_{a,P,\text{eff}}^{1}(V;\mathcal{G})$ and
$\Psi_{a,P^{\ast},\text{eff}}^{1}(V^{\ast};\mathcal{G}^{\ast})$, as functions
of $V$ and $V^{\ast}$, respectively, are identical $P$-almost everywhere;

  6. (vi)

the g-formula
$\Psi_{a}(\cdot;\mathcal{G}^{\ast}):{\mathcal{M}}_{0}(V)\rightarrow\mathbb{R}$
is an irreducible, efficient identifying formula for the g-functional defined
on ${\mathcal{M}}(\mathcal{G},V)$.

######  Corollary 5.1.

Suppose the conditions in Theorem 5.1 are satisfied and that variables in $V$
are discrete. Then under every $P\in{\mathcal{M}}(\mathcal{G},V)$,

$n^{1/2}\left\\{\Psi_{a}(\mathbb{P}^{\ast}_{n};\mathcal{G}^{\ast})-\Psi_{a}(\mathbb{P}_{n};\mathcal{G})\right\\}=o_{p}(1)$

as $n\rightarrow\infty$, where $\mathbb{P}_{n}$ and $\mathbb{P}^{\ast}_{n}$
are respectively the empirical measures based on $n$ independent copies of $V$
and $V^{\ast}$.

In light of Corollary 5.1, in Appendix B we compare the two estimators for the
example in Fig. 2.1 with simulations based on discrete data; their
performances seem extremely close even for finite samples.

##  6 Examples

To ease the notation, we omit the graph from vertex sets when it is clear from
the context.

######  Example 1 (continued).

By Theorem 4.1, $V^{\ast}=V$ for Fig. 3.1(b). Hence, the graph cannot be
further reduced; g-formula Eq. 11 is efficient, while Eqs. 12 and 13 are not.

######  Example 2.

Consider graph $\mathcal{G}_{1}$ in Fig. 6.1. Note that $O_{\min}=\emptyset$.
Variable $M$ is uninformative by checking against the M-criterion: (i)
$M\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}A,Y\mid
A,Y,O$; (ii) (a) $M\rightarrow Y$, (b)
$\operatorname{Pa}(Y)\subset\\{A,O,M\\}$ and (c)
$O\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}A,Y\mid
A,M$. The graph $\mathcal{G}_{1}$ is reduced to $\mathcal{G}_{1}^{\ast}$,
which prescribes an irreducible, efficient g-formula

$\Psi_{a}(P;\mathcal{G}_{1}^{\ast})=\sum_{o}\operatorname{\mathbb{E}}(Y\mid
A=a,o)\,p(o).$ (19)

This result also follows from Rotnitzky and Smucler (2020, Theorem 19).

On the other hand, suppose we add edge $O\rightarrow A$ as in
$\mathcal{G}_{2}$. Now, we have $O_{\min}(\mathcal{G}_{2})=\\{O\\}$ and $M$
fails the M-criterion. Hence, if $A$ is randomized conditionally on $O$, then
Eq. 19 is still an identifying formula for the g-functional, but is no longer
efficient. Since $\mathcal{G}_{2}=\mathcal{G}_{2}^{\ast}$, g-formula
$\Psi_{a}(P;\mathcal{G}_{2})$ is irreducible and efficient.

Furthermore, suppose the edge between $A$ and $O$ is added in the reverse
direction, as shown in $\mathcal{G}_{3}$, where $O$ is relabeled as
$M^{\prime}$. The variables $\\{M,M^{\prime}\\}$ are uninformative by checking
against the M-criterion or, alternatively, by recognizing that they are non-
ancestors of $Y$ in a causal Markov equivalent graph
$\mathcal{G}_{3}^{\prime}$. In this case, an irreducible, efficient
identifying formula is simply

$\Psi_{a}(P;\mathcal{G}_{3}^{\ast})=\operatorname{\mathbb{E}}(Y\mid A=a).$

$A$$M$$Y$$O$(a) $\mathcal{G}_{1}$$A$$Y$$O$$\Rightarrow$(b)
$\mathcal{G}_{1}^{\ast}$$A$$M$$Y$$O$(c)
$\mathcal{G}_{2}=\mathcal{G}_{2}^{\ast}$$A$$M$$Y$$M^{\prime}$(d)
$\mathcal{G}_{3}$$A$$M$$Y$$M^{\prime}$(e)
$\mathcal{G}_{3}^{\prime}$$\operatorname{\stackrel{{\scriptstyle
c}}{{\sim}}}$$A$$Y$(f) $\mathcal{G}_{3}^{\ast}$$\Rightarrow$ Figure 6.1:
Reduction of graphs $\mathcal{G}_{1},\mathcal{G}_{2},\mathcal{G}_{3}$ in
Example 2.

######  Example 3 (optimal adjustment).

Consider the graphs in Fig. 6.2. Recall that the optimal adjustment estimator
is the sample version of Eq. 4 when $L=O$. When the optimal adjustment
estimator is efficient, such as under $\mathcal{G}_{3}$, it holds that
$V^{\ast}$ only consists of the optimal adjustment set, $A$ and $Y$. However,
the reverse need not be true. Consider the graph $\mathcal{G}_{1}$ where
$V^{\ast}(\mathcal{G}_{1})=O(\mathcal{G}_{1})\cup\\{A,Y\\}$, but the optimal
adjustment estimator is inefficient because it does not exploit the
independence between $O_{1}$ and $O_{2}$; compare with the g-formula
associated with $\mathcal{G}_{1}$.

$A$$Y$$O_{1}$$O_{2}$(a)
$\mathcal{G}_{1}=\mathcal{G}_{1}^{\ast}$$A$$Y$$O_{1}$$O_{2}$$W$(b)
$\mathcal{G}_{2}=\mathcal{G}_{2}^{\ast}$$A$$Y$$O_{1}$$O_{2}$$W$(c)
$\mathcal{G}_{3}$$A$$Y$$O_{1}$$O_{2}$(d) $\mathcal{G}_{3}^{\ast}$$\Rightarrow$
Figure 6.2: Reduction of graphs
$\mathcal{G}_{1},\mathcal{G}_{2},\mathcal{G}_{3}$ in Example 3. The optimal
adjustment estimator is inefficient for $\mathcal{G}_{1}$ even though
$V^{\ast}(\mathcal{G}_{1})=O(\mathcal{G}_{1})\cup\\{A,Y\\}$.

######  Example 4.

Consider graph $\mathcal{G}$ in Fig. 6.3. By Theorem 4.1, $A,Y,O_{1}$ and
$O_{2}$ are included in $V^{\ast}$. Note that $O_{\min}=\\{O_{1}\\}$. By
projecting out $I_{1}$, an indirect ancestor of $Y$, $\mathcal{G}$ is reduced
to $\mathcal{G}^{0}$. Now let us check the M-criterion for $M_{1}$, $M_{2}$
and $M_{3}$. First, $M_{1}$ fails the M-criterion because
$M_{1}\not\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}A,Y,O_{1}\mid
Y,M_{3}$. Second, $M_{2}$ satisfies the criterion as it can be checked that
(i)
$M_{2}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}A,Y,O_{1}\mid
M_{1},M_{3}$; (ii)(a) $M_{2}\rightarrow M_{3}$, (b)
$\operatorname{Pa}(M_{3})\subseteq\operatorname{Pa}(M_{2})\cup\\{M_{2}\\}$ and
(c) $\operatorname{Pa}(M_{2})\setminus\operatorname{Pa}(M_{3})=\emptyset$ so
the corresponding d-separation trivially holds. Third, $M_{3}$ also satisfies
the criterion: (i)
$M_{3}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}A,Y,O_{1}\mid
Y,M_{1}$; (ii) (a) $M_{3}\rightarrow Y$, (b)
$\operatorname{Pa}(Y)\subset\operatorname{Pa}(M_{3})\cup\\{M_{3}\\}$ and (c)
$M_{2}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}A,Y,O_{1}\mid
M_{1},M_{3}$. By further projecting out $M_{2}$ and $M_{3}$, we get
$\mathcal{G}^{\ast}$. Consequently, an irreducible, efficient g-formula is

$\Psi_{a}(P;\mathcal{G}^{\ast})=\sum_{m_{1}}\operatorname{\mathbb{E}}(Y\mid
m_{1})\sum_{o_{1},o_{2}}P(m_{1}\mid A=a,o_{1},o_{2})\,p(o_{1})\,p(o_{2}).$

$A$$M_{1}$$M_{2}$$M_{3}$$Y$$I_{1}$$O_{1}$$O_{2}$(a)
$\mathcal{G}$$A$$M_{1}$$M_{2}$$M_{3}$$Y$$O_{1}$$O_{2}$$\Rightarrow$(b)
$\mathcal{G}^{0}$$A$$M_{1}$$M_{3}$$Y$$O_{1}$$O_{2}$$\Rightarrow$(c)
$\mathcal{G}^{1}$$A$$M_{1}$$Y$$O_{1}$$O_{2}$$\Rightarrow$(d)
$\mathcal{G}^{\ast}$ Figure 6.3: Graph reduction for Example 4, where
$V\setminus V^{\ast}=\\{I_{1},M_{2},M_{3}\\}$.

######  Example 5.

Let $\mathcal{G}$ be the graph drawn as Fig. 6.4(a), for which
$O=\\{O_{1},O_{2},O_{3}\\}$. Again, variable $I_{1}$ is an indirect ancestor
of $Y$ and hence uninformative. It can be checked that, variables
$W_{3},W_{4},W_{5}$ fail the W-criterion, in particular its condition (i). It
can also be checked that variables $W_{1},W_{2},W_{6}$ satisfy the
W-criterion. For example, for $W_{2}$ observe that: (i)
$W_{2}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}O_{1},O_{2},O_{3}\mid
O_{1},W_{5}$; (ii)(a) $W_{2}\rightarrow O_{1}$, (b)
$\operatorname{Pa}(O_{1})\subset\operatorname{Pa}(W_{2})\cup\\{W_{2}\\}$ and
(c)
$W_{3},W_{4}\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10.0mu\perp$}}}_{\mathcal{G}}O_{1},O_{2},O_{3}\mid
W_{2},W_{5}$. By iteratively projecting out $I,W_{1},W_{2}$ and $W_{6}$, graph
$\mathcal{G}$ is reduced to $\mathcal{G}^{\ast}$, from which we can derive an
irreducible, efficient g-formula

$\Psi_{a}(P;\mathcal{G}^{\ast})=\sum_{o_{1},o_{2},o_{3}}\operatorname{\mathbb{E}}(Y\mid
A=a,o_{1},o_{2},o_{3})p(o_{3})\\\
\times\sum_{w_{3},w_{4}}p(w_{3})p(w_{4})\sum_{w_{5}}p(o_{1}\mid
w_{3},w_{4},w_{5})p(o_{2}\mid w_{5})p(w_{5}).$

$A$$Y$$I_{1}$$W_{1}$$O_{3}$$O_{1}$$W_{2}$$W_{3}$$W_{4}$$O_{2}$$W_{5}$$W_{6}$(a)
$\mathcal{G}$$A$$Y$$W_{1}$$O_{3}$$O_{1}$$W_{2}$$W_{3}$$W_{4}$$O_{2}$$W_{5}$$W_{6}$(b)
$\mathcal{G}^{0}$$\Rightarrow$$A$$Y$$O_{3}$$O_{1}$$W_{2}$$W_{3}$$W_{4}$$O_{2}$$W_{5}$$W_{6}$(c)
$\mathcal{G}^{1}$$\Rightarrow$$A$$Y$$O_{3}$$O_{1}$$W_{3}$$W_{4}$$O_{2}$$W_{5}$$W_{6}$(d)
$\mathcal{G}^{2}$$\Rightarrow$$A$$Y$$O_{3}$$O_{1}$$W_{3}$$W_{4}$$O_{2}$$W_{5}$(e)
$\mathcal{G}^{\ast}$$\Rightarrow$ Figure 6.4: Graph reduction for Example 5,
where $V\setminus V^{\ast}=\\{I_{1},W_{1},W_{2},W_{6}\\}$.

##  7 Concluding remarks

When all variables in the graph are discrete, an asymptotically efficient
estimator based on the set of irreducible informative variables is readily
available as $\Psi_{a}(\mathbb{P}_{n}^{\ast};\mathcal{G}^{\ast})$.
Unfortunately, when not all components of $V^{\ast}$ are discrete, the plug-in
estimator $\Psi_{a}(\widehat{P^{\ast}};\mathcal{G}^{\ast})$ for
$\widehat{P^{\ast}}\in{\mathcal{M}}(\mathcal{G}^{\ast},V^{\ast})$ based on
smooth nonparametric estimators of the conditional densities
$\left\\{p\\{v_{j}|\operatorname{Pa}(v_{j},\mathcal{G}^{\ast})\\}:V_{j}\in
V^{\ast}\right\\}$ will generally fail to even be root-$n$-consistent. This is
because $\Psi_{a}(\widehat{P^{\ast}};\mathcal{G}^{\ast})$ will typically
inherit the bias and thus the rate of convergence of the nonparametric density
estimators. The one-step estimator
$\widehat{\Psi}_{a}=\Psi_{a}(\widehat{P^{\ast}},\mathcal{G}^{\ast})+\mathbb{P}_{n}\left\\{\Psi^{1}_{a,\widehat{P^{\ast}},\text{eff}}(V)\right\\}$
corrects the bias, and under smoothness or complexity assumptions on the
conditional densities it converges at the root-$n$ rate and is asymptotically
efficient. However, the calculation of
$\Psi^{1}_{a,\widehat{P^{\ast}},\text{eff}}(V)$ will typically require
evaluating complicated integrals involved in the computation of each
$\mathbb{E}_{\widehat{P^{\ast}}}\left\\{b_{a,\widehat{P^{\ast}}}(O)\mid
W_{j},\operatorname{Pa}(W_{j},\mathcal{G}^{\ast})\right\\}$ and each
$\mathbb{E}_{\widehat{P^{\ast}}}\left\\{T_{a,\widehat{P^{\ast}}}\mid
M_{k},\operatorname{Pa}(M_{k},\mathcal{G}^{\ast})\right\\}$; see Lemma 4.1.
Further work exploring methods that facilitate these calculations is
warranted.

In this article we have considered estimating the mean of an outcome under an
intervention that sets a point exposure to a fixed value in the entire
population. This is just one out of the many functionals of interest in causal
inference. We hope this work sparks interest in the characterization of
informative irreducible variables for other functionals. In particular, we are
currently studying the extension of the present work to interventions that set
the treatment to a value that depends on covariates, i.e., the so-called
dynamic treatment regimes. Extensions to time-dependent interventions in
graphs with time-dependent confounding is also of interest, but appears to be
more difficult because an optimal time-dependent adjustment set does not exist
(Rotnitzky and Smucler, 2020). Other functionals of interest include the pure
direct effect and the treatment effect on the treated.

## Acknowledgement

The authors thank Thomas Richardson and James Robins for valuable comments and
discussions, as well as the referees and the associate editor for helpful
suggestions. Part of this work was done while the authors were visiting the
Simons Institute for the Theory of Computing. Rotnitzky is partially supported
by the U.S. National Institutes of Health and is also affiliated with CONICET,
Argentina.

## References

  * Andersson et al. (1997) Steen A. Andersson, David Madigan, and Michael D. Perlman.  A characterization of Markov equivalence classes for acyclic digraphs.  _The Annals of Statistics_ , 25:505–541, 1997.
  * Bhattacharya et al. (2022) Rohit Bhattacharya, Razieh Nabi, and Ilya Shpitser.  Semiparametric inference for causal effects in graphical models with hidden variables.  _Journal of Machine Learning Research_ , to appear, 2022.
  * Bonet (2001) Blai Bonet.  Instrumentality tests revisited.  In _Proceedings of the Conference on Uncertainty in Artificial Intelligence_ , pages 48–55, San Francisco, CA, USA, 2001.
  * Cencov (1982) Nikolai Nikolaevich Cencov.  _Statistical Decision Rules and Optimal Inference_.  Number 53. American Mathematical Soc., 1982.
  * Didelez and Sheehan (2007) Vanessa Didelez and Nuala Sheehan.  Mendelian randomization as an instrumental variable approach to causal inference.  _Statistical Methods in Medical Research_ , 16(4):309–330, 2007.
  * Evans (2016) Robin J. Evans.  Graphs for margins of Bayesian networks.  _Scandinavian Journal of Statistics_ , 43(3):625–648, 2016.
  * Evans (2018) Robin J Evans.  Margins of discrete Bayesian networks.  _The Annals of Statistics_ , 46(6A):2623–2656, 2018.
  * Gill (2014) Richard D. Gill.  Statistics, causality and Bell’s theorem.  _Statistical Science_ , 29(4):512–528, 2014.
  * Guo and Perković (2021) F. Richard Guo and Emilija Perković.  Minimal enumeration of all possible total effects in a Markov equivalence class.  In _Proceedings of the International Conference on Artificial Intelligence and Statistics_ , 2021.
  * Guo and Perković (2022) F. Richard Guo and Emilija Perković.  Efficient least squares for estimating total effects under linearity and causal sufficiency.  _Journal of Machine Learning Research_ , 23(104):1–41, 2022.
  * Hahn (2004) Jinyong Hahn.  Functional restriction and efficiency in causal inference.  _The Review of Economics and Statistics_ , 86(1):73–76, 2004.
  * Henckel et al. (2022) Leonard Henckel, Emilija Perković, and Marloes H. Maathuis.  Graphical criteria for efficient total effect estimation via adjustment in causal linear models.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 84(2):579–599, 2022.
  * Hernán and Robins (2020) M. A. Hernán and J. M. Robins.  _Causal Inference: What If_.  Chapman & Hall/CRC, Boca Raton, 2020.
  * Kuipers and Moffa (2022) Jack Kuipers and Giusi Moffa.  The variance of causal effect estimators for binary v-structures.  _Journal of Causal Inference_ , 10(1):90–105, 2022.
  * Kuroki and Miyakawa (2003) Manabu Kuroki and Masami Miyakawa.  Covariate selection for estimating the causal effect of control plans by using causal diagrams.  _Journal of the Royal Statistical Society. Series B. Statistical Methodology_ , 65(1):209–222, 2003.
  * Lauritzen (1996) Steffen L. Lauritzen.  _Graphical Models_.  Oxford University Press, New York, 1996.
  * Meek (1995a) Christopher Meek.  Causal inference and causal explanation with background knowledge.  In _Proceedings of the Conference on Uncertainty in Artificial Intelligence_ , pages 403–410, 1995a.
  * Meek (1995b) Christopher Meek.  Strong completeness and faithfulness in Bayesian networks.  _Proceedings of of Conference on Uncertainty in Artificial Intelligence_ , 1995b.
  * Mond et al. (2003) David Mond, Jim Smith, and Duco Van Straten.  Stochastic factorizations, sandwiched simplices and the topology of the space of explanations.  _Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences_ , 459(2039):2821–2845, 2003.
  * Pearl (1988) Judea Pearl.  _Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference_.  Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988.  ISBN 1558604790.
  * Pearl (1993) Judea Pearl.  Comment: graphical models, causality and intervention.  _Statistical Science_ , 8(3):266–269, 1993.
  * Pearl (1995a) Judea Pearl.  Causal diagrams for empirical research.  _Biometrika_ , 82(4):669–688, 1995a.
  * Pearl (1995b) Judea Pearl.  On the testability of causal models with latent and instrumental variables.  In _Proceedings of the Conference on Uncertainty in Artificial Intelligence_ , pages 435–443, San Francisco, CA, USA, 1995b.
  * Pearl (2000) Judea Pearl.  _Causality: Models, Reasoning, and Inference_.  Cambridge University Press, 1st edition, 2000.
  * Richardson (2003) Thomas S. Richardson.  Markov properties for acyclic directed mixed graphs.  _Scandinavian Journal of Statistics_ , 30(1):145–157, 2003.
  * Robins (1986) James M. Robins.  A new approach to causal inference in mortality studies with a sustained exposure period-application to control of the healthy worker survivor effect.  _Mathematical Modelling_ , 7:1393–1512, 1986.
  * Robins and Richardson (2010) James M. Robins and Thomas S. Richardson.  Alternative graphical causal models and the identification of direct effects.  _Causality and Psychopathology: Finding the Determinants of Disorders and their Cures_ , 84:103–158, 2010.
  * Rotnitzky and Smucler (2020) Andrea Rotnitzky and Ezequiel Smucler.  Efficient adjustment sets for population average causal treatment effect estimation in graphical models.  _Journal of Machine Learning Research_ , 21(188):1–86, 2020.
  * Shpitser et al. (2014) Ilya Shpitser, Robin J. Evans, Thomas S. Richardson, and James M. Robins.  Introduction to nested Markov models.  _Behaviormetrika_ , 41(1):3–39, 2014.
  * Smucler et al. (2021) Ezequiel Smucler, Facundo Sapienza, and Andrea Rotnitzky.  Efficient adjustment sets in causal graphical models with hidden variables.  _Biometrika_ , 109(1):49–65, 03 2021.
  * Spirtes et al. (2000) Peter Spirtes, Clark Glymour, and Richard Scheines.  _Causation, Prediction, and Search_.  Springer-Verlag, New York, 2000.
  * van der Vaart (2000) Aad W. van der Vaart.  _Asymptotic Statistics_.  Cambridge University Press, 2000.
  * Verma and Pearl (1990) Thomas S Verma and Judea Pearl.  Equivalence and synthesis of causal models.  In _Proceedings of the 6th Conference on Uncertainty in Artificial Intelligence (UAI-1990)_ , pages 220–227, Cambridge, MA, USA, 1990\.
  * Witte et al. (2020) Janine Witte, Leonard Henckel, Marloes H. Maathuis, and Vanessa Didelez.  On efficient adjustment in causal graphs.  _Journal of Machine Learning Research_ , 21:246, 2020.
  * Zhang (2006) Jiji Zhang.  _Causal Inference and Reasoning in Causally Insufficient Systems_.  PhD thesis, Carnegie Mellon University, 2006.

The Appendices are organized as follows. Appendix A provides additional
background on Bayesian networks and graphical models. Appendix B contains
simulation results based on the motivating example. In Appendix C, we prove
graphical results Lemmas 3.1 and 1. In Appendix D, we prove the results for
the graph reduction procedure including Theorem 5.1. In Appendix E, we
establish that the g-formula is an efficient identifying formula for the
g-functional. In Appendix F, we prove results for graphically characterizing
the irreducible informative set $V^{\ast}$, culminating in the proof of
Theorem 4.1. To prove Theorem 4.1, we construct laws in the model such that
the efficient influence function non-trivially depends on the variables should
the variable fail the corresponding W- or M-criterion; these constructions are
detailed in Appendices G and H. Further, these constructions are based on the
certain graphical configurations that must exist should the W- or M-criterion
fail, which are provided in Appendix I.

Throughout the Appendices, we will often omit the graph from the vertex sets
introduced in Section 3.2 when it is clear from the context.

##  Appendix A Bayesian network and directed acyclic graph

###  A.1 Bayesian network on a large state space

For every random variable $V_{j}\in V$, its state space $\mathfrak{X}_{j}$ is
defined in Eq. 5, which allows $V_{j}$ to be potentially continuous or
discrete or a mixed type of both. Any set $A\subseteq\mathfrak{X}_{j}$ can be
decomposed as $A=A_{C}\,\dot{\cup}\,A_{D}$ for a continuous part $A_{C}\equiv
A\cap\mathbb{R}^{d_{j}}$ and a discrete part $A_{D}\equiv A\cap\mathbb{W}$.
Let $\mathcal{F}_{j}$ be the $\sigma$-algebra generated by unions of Borel
sets on $\mathbb{R}^{d_{j}}$ and on $\mathbb{W}$. Define measure
$\mu_{j}(A)\equiv\text{Leb}(A_{C})+|A_{D}|$ for $A\in\mathcal{F}_{j}$.
Finally, the measurable space for random vector $V$ is
$(\mathfrak{X},\mathcal{F})$, where $\mathfrak{X}\equiv\bigtimes_{j:V_{j}\in
V}\mathfrak{X}_{j}$ and $\mathcal{F}\equiv\bigtimes_{j:V_{j}\in
V}\mathcal{F}_{j}$.

###  A.2 Notations for graphical models

Symbol $V_{i}\rightarrow V_{j}$ or $V_{j}\leftarrow V_{i}$ denotes a directed
edge from $V_{i}$ to $V_{j}$. In such case, we say that $V_{i}$ is a parent of
$V_{j}$, $V_{j}$ is a child of $V_{i}$ and denoted with
$V_{i}\in\operatorname{Pa}(V_{j},\mathcal{G})$,
$V_{j}\in\operatorname{Ch}(V_{i},\mathcal{G})$. We say $V_{i}$ and $V_{j}$ are
adjacent if $V_{i}\rightarrow V_{j}$ or $V_{i}\leftarrow V_{j}$. A path
$p=\langle V_{1},\dots,V_{k}\rangle$ with $k\geq 2$ is a sequence of distinct
vertices, such that $V_{i}$ and $V_{i+1}$ are adjacent in the graph for
$i=1,\dots,k-1$. When $p$ is of the form $V_{1}\rightarrow\dots\rightarrow
V_{k}$, we say that $p$ is a directed path. In a configuration
$V_{i}\rightarrow V_{k}\leftarrow V_{j}$, $V_{k}$ is said to be a collider;
further, if $V_{i}$ and $V_{j}$ are non-adjacent, then $V_{k}$ is an
unshielded collider. We say $V_{i}$ is an ancestor of $V_{j}$, or equivalently
$V_{j}$ is a descendant of $V_{i}$, if either $V_{i}=V_{j}$ or there is a
directed path from $V_{i}$ to $V_{j}$. This is denoted as $V_{i}\mapsto
V_{j}$. Symbol $V_{i}\not\mapsto V_{j}$ means $V_{i}$ is not an ancestor of
$V_{j}$. The set of ancestors of $V_{j}$ with respect to graph $\mathcal{G}$
is denoted by $\operatorname{An}(V_{j},\mathcal{G})$, and similarly, the set
of descendants of $V_{i}$ is denoted by
$\operatorname{De}(V_{i},\mathcal{G})$; by definition, we have
$V_{j}\in\operatorname{An}(V_{j},\mathcal{G})$ and
$V_{i}\in\operatorname{De}(V_{i},\mathcal{G})$. The definitions of relational
sets extend disjunctively to a set of vertices $C$, e.g.,
$\operatorname{Pa}(C,\mathcal{G})\equiv\bigcup_{V_{j}\in
C}\operatorname{Pa}(V_{j},\mathcal{G})$,
$\operatorname{Ch}(C,\mathcal{G})\equiv\bigcup_{V_{j}\in
C}\operatorname{Ch}(V_{j},\mathcal{G})$,
$\operatorname{An}(C,\mathcal{G})\equiv\bigcup_{V_{j}\in
C}\operatorname{An}(V_{j},\mathcal{G})$,
$\operatorname{De}(C,\mathcal{G})\equiv\bigcup_{V_{j}\in
C}\operatorname{De}(V_{j},\mathcal{G})$, etc. Moreover, a set $C$ is called
ancestral if $V_{j}\in C$ implies
$\operatorname{An}(V_{j},\mathcal{G})\subseteq C$. Vertices
$V_{1},\dots,V_{k}$ are topologically ordered if $V_{i}\mapsto V_{j}$ for
$i\neq j$ implies $i<j$.

##  Appendix B Simulations

We report simulation results based on the motivating example in Fig. 2.1. For
simplicity, we get rid of $I_{1}$ and $W_{1}$ and fix $\mathcal{G}^{\prime}$
as the original graph, according to which data is generated. We consider
discrete data generating mechanisms according to $\mathcal{G}^{\prime}$. Let
$A,O_{1},Y$ be binary valued, i.e. taking value from $\\{0,1\\}$. Suppose
$W_{4}$ takes value from $\\{0,\dots,k-1\\}$; while both $W_{2}$ and $W_{3}$
take value from $\\{0,\dots,m-1\\}$.

We specify the data generating mechanism as follows. First, we draw

$W_{2},W_{3}\sim\mathrm{unif}(\\{0,\dots,m-1\\})$

independently. Then, we reserve $\\{0,\dots,4\\}$ in the support of $W_{4}$ as
a special set of values and draw

$W_{4}\mid W_{2},W_{3}\sim\begin{cases}\mathrm{unif}(\\{0,\dots,4\\}),&\quad
W_{2}=W_{3}\\\ Q,&\quad W_{2}\neq W_{3}\end{cases},$

where

$Q(w_{4})\propto\begin{cases}\left[1+\exp\\{-(w_{4}+1)/5\\}\right]^{-1},\quad&w_{4}\notin\\{0,\dots,4\\}\\\
0,\quad&\text{otherwise}\end{cases}.$

Further, $O$’s distribution depends on whether $W_{4}$ takes a special value:

$P(O=1\mid W_{4}=w_{4})=\begin{cases}0.99,\quad&w_{4}\in\\{0,\dots,4\\}\\\
0.01,\quad&\text{otherwise}\end{cases}.$

We use these configurations to introduce the interaction between $W_{2}$ and
$W_{3}$, so that the marginal independence between $W_{2}$ and $W_{3}$ must be
utilized to minimize the variance. Finally, we draw $A$ and $Y$ according to

$P(A=1\mid W_{4}=w_{4})=\left[1+\exp\\{2-(w_{4}+1)/5\\}\right]^{-1}$

and

$P(Y=1\mid A=a,O_{1}=o_{1})=\left[1+\exp\\{-(o_{1}-1/2)(9a+5)\\}\right]^{-1}.$

We consider three estimators for $\Psi_{1}(P;\mathcal{G})$:

  1. 1.

Plugin g-formula $\Psi_{1}(\mathbb{P}_{n};\mathcal{G}^{\prime})$ based on the
original graph $\mathcal{G}^{\prime}$.

  2. 2.

Plugin g-formula $\Psi_{1}(\mathbb{P}_{n};\mathcal{G}^{\ast})$ based on the
reduced graph $\mathcal{G}^{\ast}$, which does not use $W_{4}$.

  3. 3.

Optimal adjustment
$\Psi_{1,O_{1}}^{\text{ADJ}}(\mathbb{P}_{n};\mathcal{G}^{\prime})=\sum_{o_{1}}\mathbb{P}_{n}(Y=1\mid
A=1,O_{1}=o_{1})\mathbb{P}_{n}(o_{1})$, which does not use
$W_{2},W_{3},W_{4}$.

We perform simulations in two settings: (a) $m=5$, $k=50$ and (b) $m=50$,
$k=10$. The results are reported in Table B.1. We select different sample
sizes in each setting; the smallest sample size is chosen such that all levels
of $(W_{2},W_{4})$ appear in the data. In both settings, while
$\Psi_{1}(\mathbb{P}_{n};\mathcal{G}^{\prime})$ and
$\Psi_{1}(\mathbb{P}_{n};\mathcal{G}^{\ast})$ achieve a significantly smaller
variance compared to
$\Psi_{1,O_{1}}^{\text{ADJ}}(\mathbb{P}_{n};\mathcal{G}^{\prime})$, there is
no discernible difference between their performances.

Table B.1: Variance of the estimator multiplied by sample size $n$. The number of replications is large enough such that the standard error is within the next significant digit. | $n$ | $\Psi_{1,O_{1}}^{\text{ADJ}}(\mathbb{P}_{n};\mathcal{G}^{\prime})$ | $\Psi_{1}(\mathbb{P}_{n};\mathcal{G}^{\prime})$ | $\Psi_{1}(\mathbb{P}_{n};\mathcal{G}^{\ast})$
---|---|---|---|---
(a) |  |  |  |
1 | 200 | 0.163 | 0.013 | 0.013
2 | 500 | 0.164 | 0.012 | 0.012
3 | 1000 | 0.164 | 0.012 | 0.012
4 | 10000 | 0.165 | 0.012 | 0.012
5 | 25000 | 0.163 | 0.012 | 0.012
6 | 50000 | 0.168 | 0.012 | 0.012
7 | 100000 | 0.161 | 0.011 | 0.011
(b) |  |  |  |
8 | 25000 | 0.031 | 0.012 | 0.013
9 | 50000 | 0.031 | 0.012 | 0.013
10 | 100000 | 0.031 | 0.012 | 0.012

##  Appendix C Various graphical results

###  C.1 Proof of Lemma 3.1

  * Proof.

First, we show that $W\subseteq\operatorname{An}(O)$. Fix any $W_{j}\in W$, we
want to show that $W_{j}\mapsto O$. By definition in Eq. 7, there exists a
causal path $p:W_{j}\rightarrow Z_{1}\rightarrow\dots\rightarrow Z_{k}=Y$ such
that $p$ does not contain $A$. By definition of set $M$, $Z_{i}\in M$ implies
$Z_{i+1}\in M$ for $i=1,\dots,k-1$. Let $l$ be the smallest index such that
$Z_{l}\in M$. If $l=1$, then $W_{j}\in O$ by definition in Eq. 8; otherwise,
$Z_{l-1}\in O$ by definition as $Z_{l-1}\rightarrow Z_{l}\in M$ but
$Z_{l-1}\notin\operatorname{De}(M)$, $Z_{l-1}\neq A$. In either case,
$W_{j}\mapsto O$.

Now we show that $\operatorname{An}(O)\subseteq W$. Pick any $V_{i}$ such that
$V_{i}\mapsto O_{k}$ for $O_{k}\in O$. Showing that $V_{i}\in W$ boils down to
showing (i) $V_{i}\mapsto Y$ not through $A$ and (ii)
$V_{i}\notin\operatorname{De}(A)$. Note (i) is follows from $V_{i}\mapsto
O_{k}\mapsto Y$, which need not go through $A$. To see (ii), suppose
$V_{i}\in\operatorname{De}(A)$. Then, it follows that
$O_{k}\in\operatorname{De}(A)$, which implies $O_{k}\in M$, contradicting the
definition of $O$. ∎

###  C.2 Proof of Proposition 1

  * Proof.

Suppose $\mathcal{G}$ and $\mathcal{G}^{\prime}$ are causal Markov equivalent.
By Definition 2, $\mathcal{G}$ and $\mathcal{G}^{\prime}$ are then Markov
equivalent and $\Psi_{a}(P;\mathcal{G})=\Psi_{a}(P;\mathcal{G}^{\prime})$ for
all $P\in{\mathcal{M}}(\mathcal{G},V)$. Given that $\mathcal{G}$ and
$\mathcal{G}^{\prime}$ satisfy 1, by Theorem 3 of Guo and Perković (2021),
$\mathcal{G}$ and $\mathcal{G}^{\prime}$ are then represented by a maximally
oriented partially directed acyclic graph $\tilde{\mathcal{G}}$, given which
the total causal effect of $A$ on $Y$ is identified. Furthermore, since
$|A|=|Y|=1$, by Corollary 2 of Guo and Perković (2021), there exists an
adjustment set with respect to the effect of $A$ on $Y$ in
$\tilde{\mathcal{G}}$. Then by Lemma E.7 of Henckel et al. (2022), the optimal
adjustment set with respect to the effect of $A$ on $Y$ is the same in
$\tilde{\mathcal{G}}$, $\mathcal{G}$, and $\mathcal{G}^{\prime}$.

Conversely, suppose that $\mathcal{G}$ and $\mathcal{G}^{\prime}$ are Markov
equivalent and that the optimal adjustment set with respect to the effect of
$A$ on $Y$ is the same in $\mathcal{G}$ and $\mathcal{G}^{\prime}$. Then using
the fact that $\Psi_{a}(P;\mathcal{G})=\Psi_{a,O}^{\text{ADJ}}(P;\mathcal{G})$
for all $P\in{\mathcal{M}}(\mathcal{G},V)$ and
$\Psi_{a,O}^{\text{ADJ}}(P;\mathcal{G}^{\prime})=\Psi_{a}(P;\mathcal{G}^{\prime})$
for all $P\in{\mathcal{M}}(\mathcal{G}^{\prime},V)$, and that $\mathcal{G}$
and $\mathcal{G}^{\prime}$ are Markov equivalent, we have,
$\Psi_{a}(P;\mathcal{G})=\Psi_{a}(P;\mathcal{G}^{\prime})$ for all
$P\in{\mathcal{M}}(\mathcal{G},V)$. ∎

##  Appendix D Graph reduction

###  D.1 Proof of Lemma 5.1

Latent projection is introduced by Verma and Pearl (1990) to represent the
marginal model of a directed acyclic graph. Recall that for $L\subseteq V$,
${\mathcal{M}}(\mathcal{G},L)$ denotes the marginal model of $L$ induced by
${\mathcal{M}}(\mathcal{G},V)$.

######  Definition 9 (Latent projection).

Let $\mathcal{G}$ be a directed acyclic graph on vertices $V\,\dot{\cup}\,U$,
where $U$ is the set of latent variables. The latent projection of
$\mathcal{G}$ on $V$, denoted by $\mathcal{G}(V)$, is a mixed graph on $V$
with directed and bidirected edges:

  1. 1.

$V_{i}\rightarrow V_{j}$ if there is a directed path $V_{i}\mapsto V_{j}$ in
$\mathcal{G}$ on which every non-endpoint vertex is in $U$,

  2. 2.

$V_{i}\leftrightarrow V_{j}$ if there exists a path of the form
$V_{i}\leftarrow\dots\rightarrow V_{j}$ in $\mathcal{G}$ on which every non-
endpoint vertex is a non-collider and contained in $U$.

For graph $\mathcal{G}$ on vertices $V$ and $V^{\prime}\subseteq V$, let
$\mathcal{G}_{V^{\prime}}$ be the subgraph induced by $V^{\prime}$.

######  Lemma D.1 (Proposition 3.22, Lauritzen, 1996).

Let $\mathcal{G}$ be a directed acyclic graph on vertices $V$. Let
$V^{\prime}$ be an ancestral subset of $V$. Then,
${\mathcal{M}}(\mathcal{G},V^{\prime})={\mathcal{M}}(\mathcal{G}_{V^{\prime}},V^{\prime})$.

The following definition and two lemmas are due to Evans (2016).

######  Definition 10 (Exogenized graph).

Let $\mathcal{G}$ be a directed acyclic graph containing vertex $U_{i}$. The
exogenized graph $\mathfrak{r}(\mathcal{G},U_{i})$ is a directed acyclic graph
transformed from $\mathcal{G}$ as follows. For each
$V_{j}\in\operatorname{Pa}(U_{i})$ and $V_{k}\in\operatorname{Ch}(U_{i})$, add
edge $V_{j}\rightarrow V_{k}$ if the edge is not already present. Then, remove
all edges between $\operatorname{Pa}(U_{i})$ and $U_{i}$.

######  Lemma D.2.

Let $\mathcal{G}$ be a directed acyclic graph on vertices $V\cup\\{U_{i}\\}$.
Let $\mathcal{G}^{\prime}=\mathfrak{r}(\mathcal{G},U_{i})$. Then,
${\mathcal{M}}(\mathcal{G},V)={\mathcal{M}}(\mathcal{G}^{\prime},V)$.

######  Lemma D.3.

Let $\mathcal{G}$ be a directed acyclic graph on vertices $V\cup\\{U_{i}\\}$,
such that $U_{i}$ has no parent and at most one child. Then,
${\mathcal{M}}(\mathcal{G},V)={\mathcal{M}}(\mathcal{G}_{-U_{i}},V)$, where
graph $\mathcal{G}_{-U_{i}}$ denotes the graph from removing vertex $U_{i}$.

  * Proof of Lemma 5.1.

It is easy to see that

$\mathcal{G}^{0}=\mathcal{G}_{V\setminus N(\mathcal{G})}(V^{0}),$

namely the graph obtained from first removing vertices $N(\mathcal{G})$ and
then projecting out $I(\mathcal{G})$ with latent projection.

First, let $\tilde{V}^{0}\equiv V\setminus\mathcal{N}(\mathcal{G})$ and
$\tilde{\mathcal{G}}^{0}\equiv\mathcal{G}_{V\setminus N(\mathcal{G})}$.
Because $\tilde{V}^{0}$ is ancestral, by Lemma D.1, we have

${\mathcal{M}}(\mathcal{G},\tilde{V}^{0})={\mathcal{M}}(\tilde{\mathcal{G}}^{0},\tilde{V}^{0}).$

Now we iteratively project out vertices in $I(\mathcal{G})$. Suppose
$I(\mathcal{G})=\\{I_{1},\dots,I_{L}\\}$ is topologically indexed. By
definition of $I$ and the fact that every vertex an ancestor of $Y$ in
$\tilde{\mathcal{G}}^{0}$, it must hold that
$\operatorname{Ch}(I_{L},\tilde{\mathcal{G}}^{0})=\\{A\\}$. Let
$\tilde{\mathcal{G}}_{e}^{1}=\mathfrak{r}(\tilde{\mathcal{G}}^{0},I_{L})$ be
the graph from exogenizing $I_{L}$. In $\tilde{\mathcal{G}}_{e}^{1}$, $A$ is
still the only child of $I_{L}$. Also, let $\tilde{\mathcal{G}}^{1}$ be the
graph by removing $I_{L}$ from $\tilde{\mathcal{G}}_{e}^{1}$. Then, with
$\tilde{V}^{1}\equiv\tilde{V}^{0}\setminus\\{I_{L}\\}$, by Lemmas D.2 and D.3,
we have

${\mathcal{M}}(\tilde{\mathcal{G}}^{0},\tilde{V}^{1})={\mathcal{M}}(\tilde{\mathcal{G}}_{e}^{1},\tilde{V}^{1})={\mathcal{M}}(\tilde{\mathcal{G}}^{1},\tilde{V}^{1}).$

Comparing Definitions 9 and 10, it is easy to see that
$\tilde{\mathcal{G}}^{1}=\tilde{\mathcal{G}}^{0}(\tilde{V}^{1})$ and
$\tilde{\mathcal{G}}^{1}$ is a directed acyclic graph. Now $I_{L-1}$ becomes
the vertex with sole child $A$ in $\tilde{\mathcal{G}}^{1}$. Continuing this
operation for $I_{L-1},\dots,I_{1}$, we arrive at graph
$\tilde{\mathcal{G}}^{L}$ on vertices
$\tilde{V}^{L}\equiv\tilde{V}^{0}\setminus I=V\setminus\\{N(\mathcal{G})\cup
I(\mathcal{G})\\}=V^{0}$. Because the marginal model is taken iteratively, we
have

${\mathcal{M}}(\mathcal{G},V^{0})={\mathcal{M}}(\tilde{\mathcal{G}}^{L},V^{0}).$

Further, because
$\tilde{\mathcal{G}}^{0}=\mathcal{G}_{\tilde{V}^{0}}=\mathcal{G}(\tilde{V}^{0}),\tilde{\mathcal{G}}^{1}=\tilde{\mathcal{G}}^{0}(\tilde{V}^{1}),\dots,\tilde{\mathcal{G}}^{L}=\tilde{\mathcal{G}}^{L-1}(\tilde{V}^{L})$
with iterative latent projections and every projection remains a directed
acyclic graph, we have

$\tilde{\mathcal{G}}^{L}=\mathcal{G}(V^{0})=\mathcal{G}_{V\setminus
N(\mathcal{G})}(V^{0})=\mathcal{G}^{0}$

by commutativity of latent projection; see Evans (2016, Theorem 1). It also
follows that $\tilde{\mathcal{G}}^{L}$ is a directed acyclic graph over
vertices $V^{0}$. ∎

###  D.2 Projecting out uninformative variables in $W(\mathcal{G})\cup
M(\mathcal{G})$

In the following, we use the mDAG representation to prove Lemma 5.2. Marginal
directed acyclic graphs, or mDAGs, are a class of hyper-graphs introduced by
Evans (2016) to represent the marginal model of directed acyclic graphs. As
opposed to the latent projection of Verma and Pearl (1990) that introduces
bidirected edges, mDAGs use hyper-edges to signify latent variables that
confound two or more observed variables. An mDAG
$\mathcal{H}=(V,\mathcal{E},\mathcal{B})$ is a hyper-graph on vertices $V$
with directed edges $\mathcal{E}$ and hyper-edges $\mathcal{B}$, where
$\mathcal{B}$ is an abstract simplicial complex. Elements of $\mathcal{B}$ are
called bidirected faces. A face is called trivial if it is a singleton set.
The inclusion maximal elements of $\mathcal{B}$ are called facets. A directed
acyclic graph is an mDAG with trivial bidirected facets.

It can be shown that if two projections lead to the same mDAG, they the
marginal models must be the same. For an mDAG $\mathcal{H}$, let
${\mathcal{M}}_{m}(\mathcal{H})$ denote the marginal model represented by
$\mathcal{H}$. More concretely, ${\mathcal{M}}_{m}(\mathcal{H})$ can be taken
as the marginal model of the canonical directed acyclic graph associated with
$\mathcal{H}$, which replaces every non-trivial facet with an exogenous latent
variable.

######  Lemma D.4 (Proposition 5, Evans, 2016).

Let $\mathcal{H}$ be an mDAG containing a bidirected facet
$B=C\,\dot{\cup}\,D$ such that

  1. (i)

every bidirected face containing any $C_{i}\in C$ is a subset of $B$; and

  2. (ii)

$\operatorname{Pa}(C,\mathcal{H})\subseteq\operatorname{Pa}(D_{j},\mathcal{H})$
for every $D_{j}\in D$.

Let $\mathcal{H}^{\prime}$ be the mDAG defined from $\mathcal{G}$ by removing
facet $B$ and replacing it with $C$ and $D$, and adding edges
$C_{i}\rightarrow D_{j}$ for each $C_{i}\in C$ and $D_{j}\in D$, if the edge
is not already present. Then,

${\mathcal{M}}_{m}(\mathcal{H})={\mathcal{M}}_{m}(\mathcal{H}^{\prime}).$

  * Proof of Lemma 5.2.

Let $\mathcal{H}^{1}$ be the mDAG from projecting out $V_{i}$; see Evans
(2016) for details. Graph $\mathcal{H}^{1}$ is a graph on $V$ consisting of
both directed edges and a bidirected facet, which represents the marginal
model of $\mathcal{G}$ when $V_{i}$ is marginalized over, as denoted by

${\mathcal{M}}_{m}(\mathcal{H}^{1})={\mathcal{M}}(\mathcal{G},V\setminus\\{V_{i}\\}).$

By construction, we have $V_{k}\rightarrow V_{i_{j}}$ in $\mathcal{H}^{1}$ for
every $V_{k}\in\operatorname{Pa}(V_{i},\mathcal{G})$ and $j=1,\dots,l$. Set
$B^{1}=\\{V_{i_{1}},\dots,V_{i_{l}}\\}$ is the only bidirected facet in
$\mathcal{H}^{1}$. Partition $B^{1}$ into $C^{1}=\\{V_{i_{1}}\\}$ and
$D^{1}=\\{V_{i_{2}},\dots,V_{i_{l}}\\}$. We observe that (i) every bidirected
face that contains $V_{i_{1}}\in C^{1}$ is a subset of $B^{1}$, which follows
trivially from $B^{1}$ being the only facet. We also observe that (ii)
$\operatorname{Pa}(C^{1},\mathcal{H}^{1})=\operatorname{Pa}(V_{i_{1}},\mathcal{H}^{1})\subseteq\operatorname{Pa}(D_{j},\mathcal{H}^{1})$
for every $D_{j}\in D^{1}$. Statement (ii) follows from

$\operatorname{Pa}(V_{i_{1}},\mathcal{H}^{1})=\operatorname{Pa}(V_{i},\mathcal{G}),$

which holds because (a)
$\operatorname{Pa}(V_{i},\mathcal{G})\subseteq\operatorname{Pa}(V_{i_{1}},\mathcal{H}^{1})$
by construction of $\mathcal{H}^{1}$ and (b)
$\operatorname{Pa}(V_{i},\mathcal{G})\supseteq\operatorname{Pa}(V_{i_{1}},\mathcal{H}^{1})$
by Eq. 16 when $j=1$. By Lemma D.4, we have

${\mathcal{M}}_{m}(\mathcal{H}^{1})={\mathcal{M}}_{m}(\mathcal{H}^{2}),$

where in $\mathcal{H}^{2}$, an mDAG on the same set of vertices, facet $B^{1}$
is replaced by facet $D^{1}$ and edges $\\{V_{i_{1}}\rightarrow D_{j}:D_{j}\in
D^{1}\\}$ are added, if not already present.

In graph $\mathcal{H}^{2}$, $B^{2}=\\{V_{i_{2}},\dots,V_{i_{l}}\\}$ is the
only bidirected facet and can partitioned into $C^{2}=\\{V_{i_{2}}\\}$ and
$D^{2}=\\{V_{i_{3}},\dots,V_{i_{l}}\\}$. We claim that

$\operatorname{Pa}(V_{i_{2}},\mathcal{H}^{2})=\\{V_{i_{1}}\\}\cup\operatorname{Pa}(V_{i},\mathcal{G}),$

which follows from (a)
$\\{V_{i_{1}}\\}\cup\operatorname{Pa}(V_{i},\mathcal{G})\subseteq\operatorname{Pa}(V_{i_{2}},\mathcal{H}^{2})$
by construction of $\mathcal{H}^{2}$, and (b)
$\\{V_{i_{1}}\\}\cup\operatorname{Pa}(V_{i},\mathcal{G})\supseteq\operatorname{Pa}(V_{i_{2}},\mathcal{H}^{2})$
by Eq. 16 and construction of $\mathcal{H}^{2}$. Therefore, we again have (i)
every bidirected face containing $V_{i_{2}}\in C^{2}$ is a subset of $B^{2}$,
and (ii)
$\operatorname{Pa}(C^{2},\mathcal{H}^{2})\subseteq\operatorname{Pa}(D_{i},\mathcal{H}^{2})$
for every $D_{j}\in D^{2}$. Applying Lemma D.4 again, we have

${\mathcal{M}}_{m}(\mathcal{H}^{2})={\mathcal{M}}_{m}(\mathcal{H}^{3}),$

where $\mathcal{H}^{3}$ is the mDAG formed by replacing facet $B^{2}$ by facet
$D^{2}$ and adding edges $\\{V_{i_{2}}\rightarrow D_{j}:D_{j}\in D^{2}\\}$ if
not already present.

Iterating this process, we get a sequence of mDAGs
$\mathcal{H}^{1},\mathcal{H}^{2},\dots,\mathcal{H}^{l}$; see Fig. D.1 for an
example. The last graph $\mathcal{H}^{l}$ contains no non-trivial bidirected
facet and it is easy to see that $\mathcal{H}^{l}$ is a directed acyclic graph
on vertices $V\setminus\\{V_{i}\\}$. Further, graph $\mathcal{H}^{l}$ is
identical to $\mathcal{G}_{-V_{i},\pi}$ described in the lemma. The proof is
complete upon noting

${\mathcal{M}}(\mathcal{G},V\setminus\\{V_{i}\\})={\mathcal{M}}_{m}(\mathcal{H}^{1})={\mathcal{M}}_{m}(\mathcal{H}^{2})=\dots={\mathcal{M}}_{m}(\mathcal{H}^{l})={\mathcal{M}}(\mathcal{H}^{l},V\setminus\\{V_{i}\\}).$

∎

$W_{j}$$W_{l}$$W_{k}$$W_{j_{1}}$$W_{j_{2}}$$W_{j_{3}}$$A$(a)
$\mathcal{G}$$W_{l}$$W_{k}$$W_{j_{1}}$$W_{j_{2}}$$W_{j_{3}}$$A$$\Rightarrow$(b)
$\mathcal{H}^{1}$$W_{l}$$W_{k}$$W_{j_{1}}$$W_{j_{2}}$$W_{j_{3}}$$A$$\Rightarrow$(c)
$\mathcal{H}^{2}$$W_{l}$$W_{k}$$W_{j_{1}}$$W_{j_{2}}$$W_{j_{3}}$$A$$\Rightarrow$(d)
$\mathcal{H}^{3}$$W_{l}$$W_{k}$$W_{j_{1}}$$W_{j_{2}}$$W_{j_{3}}$$A$$\Rightarrow$(e)
$\mathcal{H}^{4}=\mathcal{G}_{-W_{j},\pi}$ Figure D.1: Application of Lemma
5.2 to $V_{i}=W_{j}$ with $\pi=(W_{j_{1}},W_{j_{2}},W_{j_{3}},A)$.

  * Proof of Lemma 5.3.

Since $V_{i}\in V\setminus V^{\ast}(\mathcal{G})$ and
$N(\mathcal{G})=I(\mathcal{G})=\emptyset$, by Theorem 4.1, we have either (1)
$V_{i}\equiv W_{i}\in W(\mathcal{G})\setminus O(\mathcal{G})$ and $W_{i}$
satisfies the W-criterion or (2) $V_{i}\equiv M_{i}\in
M(\mathcal{G})\setminus\\{Y\\}$ and $M_{i}$ satisfies the M-criterion. We now
check that Lemma 5.2 can be applied.

In Case (1), we have
$W(\mathcal{G})\cup\\{A\\}\supset\operatorname{Ch}(W_{i},\mathcal{G})$, for
which $\pi$ is a topological ordering by W-criterion’s (ii)(a) and the fact
that $A\not\mapsto W$. Further, the implied ordering of
$\operatorname{Ch}(W_{i},\mathcal{G})\cap W(\mathcal{G})$ is unique. Condition
Eq. 16 is implied by W-criterion’s (ii)(b).

In Case (2), we have
$M(\mathcal{G})\supset\operatorname{Ch}(M_{i},\mathcal{G})$, for which $\pi$
is the unique topological ordering by M-criterion’s (ii)(a). Condition Eq. 16
is implied by M-criterion’s (ii)(b).

By Lemma 5.2, we have
${\mathcal{M}}(\mathcal{G},V\setminus\\{V_{i}\\})={\mathcal{M}}(\mathcal{G}_{-V_{i},\pi},V\setminus\\{V_{i}\\})$.
Further, for $P\in{\mathcal{M}}(\mathcal{G},V)$ under 2,
$\Psi_{a}(P;\mathcal{G})$ depends on $P$ only through
$P(V\setminus\\{V_{i}\\})$ because
$\Psi_{a}(P;\mathcal{G})=\operatorname{\mathbb{E}}[\operatorname{\mathbb{E}}\\{Y\mid
A=a,O(\mathcal{G})\\}]$ and $V_{i}\notin\\{A,Y\\}\cup O(\mathcal{G})$. By
Lemma 3.2 and Definition 4, we have
$V^{\ast}(\mathcal{G})=V^{\ast}(\mathcal{G}_{-V_{i},\pi})$. ∎

###  D.3 Commutativity of $\mathcal{G}_{-V_{i},\pi}$ projection

The following result shows that projection $\mathcal{G}_{-V_{i},\pi}$ given by
Definition 8, when applied to uninformative variables in $W(\mathcal{G})\cup
M(\mathcal{G})$, is commutative.

######  Lemma D.5.

Suppose $\mathcal{G}$ is a directed acyclic graph on vertex set $V$ that
satisfies 1. Suppose $A\in V$ is the treatment and $Y\in V$ is the outcome.
Let $V_{i},V_{j}$ be two distinct vertices in $\\{W(\mathcal{G})\cup
M(\mathcal{G})\\}\setminus(O(\mathcal{G})\cup\\{Y\\})$ such that $V_{i}$ and
$V_{j}$ satisfy Lemma 4.6 or Lemma 4.7. Let $\pi_{i}$, $\pi_{j}$ be defined
according to Eq. 17 or Eq. 18, depending which criterion is applicable. It
holds that

$(\mathcal{G}_{-V_{i},\pi_{i}})_{-V_{j},\pi_{j}}\equiv(\mathcal{G}_{-V_{j},\pi_{j}})_{-V_{i},\pi_{i}}.$

  * Proof.

For simplicity let
$\mathcal{G}_{1}\equiv(\mathcal{G}_{-V_{i},\pi_{i}})_{-V_{j},\pi_{j}}$ and let
$\mathcal{G}_{2}\equiv(\mathcal{G}_{-V_{j},\pi_{j}})_{-V_{i},\pi_{i}}$. By
construction of $\mathcal{G}_{1},\mathcal{G}_{2}$ and Lemmas 5.1 and 5.2, both
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are directed acyclic graphs on
$V\setminus\\{V_{1},V_{2}\\}$. Hence, for Lemma D.5 to hold, we only need to
show that the set of edges in $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are
identical.

The only edges that differ between $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ as
compared to $\mathcal{G}$ involve vertices $V_{i},V_{j}$,
$\operatorname{Pa}(V_{i},\mathcal{G}),\operatorname{Pa}(V_{j},\mathcal{G})$,
$\pi_{i}$ and $\pi_{j}$. Let $E^{1}$ be the set of edges in $\mathcal{G}_{1}$
and $E^{2}$ be the set of edges in $\mathcal{G}_{2}$. Without loss of
generality, we will suppose that $V_{i}$ precedes $V_{j}$ in the topological
ordering of $V$ in $\mathcal{G}$. If $V_{i}\to V_{j}$ is not in $\mathcal{G}$,
then

$\operatorname{Pa}(V_{i},\mathcal{G}_{-V_{j},\pi_{j}})=\operatorname{Pa}(V_{i},\mathcal{G}),\quad\operatorname{Ch}(V_{i},\mathcal{G}_{-V_{j},\pi_{j}})=\operatorname{Ch}(V_{i},\mathcal{G}),$

and

$\operatorname{Pa}(V_{j},\mathcal{G}_{-V_{i},\pi_{i}})=\operatorname{Pa}(V_{j},\mathcal{G}),\quad\operatorname{Ch}(V_{j},\mathcal{G}_{-V_{i},\pi_{i}})=\operatorname{Ch}(V_{j},\mathcal{G}).$

Therefore, by construction of $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$,
$E^{1}=E^{2}$.

For the rest of the proof, we suppose that $V_{i}\to V_{j}$ is in
$\mathcal{G}$. Then $V_{i},V_{j}$ are both in $W(\mathcal{G})$, or
$V_{i},V_{j}$ are both in $M$. If $V_{i},V_{j}\in W(\mathcal{G})$, let
$Q\equiv W(\mathcal{G})$, otherwise, let $Q\equiv M(\mathcal{G})$. Let
$\operatorname{Pa}(V_{i},\mathcal{G})\cap
Q=\\{V_{i}^{1},\dots,V_{j}^{l_{1}}\\}$ and
$\operatorname{Pa}(V_{j},\mathcal{G})\cap
Q=\\{V_{i}^{1},\dots,V_{j}^{l_{2}}\\}$, such that
$(V_{i}^{1},\dots,V_{j}^{l_{1}})$ and $(V_{i}^{1},\dots,V_{j}^{l_{2}})$ are
topologically ordered in $\mathcal{G}$. Additionally, suppose that
$\pi_{i}=(V_{i_{1}},\dots,V_{i_{r_{1}}})$ and
$\pi_{j}=(V_{j_{1}},\dots,V_{j_{r_{2}}})$.

Let $l(i)\in\\{1,\dots,l_{2}\\}$ such that $V_{i}=V_{j}^{l(i)}$ and let
$r(j)\in\\{1,\dots r_{1}\\}$ such that $V_{j}=V_{i_{r(j)}}$. Below, we will
tackle the most general case, that is $1\neq l(i)\neq l_{2}$ and $1\neq
r(j)\neq r_{1}$. The proof for special cases when $l(i)\in\\{1,l_{2}\\}$ or
$r(j)\in\\{1,r_{1}\\}$ follows the same logic and drops a few of the arguments
below.

Let $E$ be the set of edges in $\mathcal{G}$ and let $E^{\prime}$ be the set

$\displaystyle E^{\prime}=E\setminus\Big{(}$
$\displaystyle\big{\\{}V_{i}^{l}\to V_{i_{r}}:1\leq l\leq l_{1},0\leq r\leq
r_{1}\big{\\}}\cup\big{\\{}V_{i_{r^{\prime}}}\to
V_{i_{r^{\prime\prime}}}:0\leq r^{\prime}<r^{\prime\prime}\leq r_{1}\big{\\}}$
$\displaystyle\cup\big{\\{}V_{j}^{l}\to V_{j_{r}}:1\leq l\leq l_{2},0\leq
r\leq r_{2}\big{\\}}\cup\big{\\{}V_{j_{r^{\prime}}}\to
V_{j_{r^{\prime\prime}}}:0\leq r^{\prime}<r^{\prime\prime}\leq
r_{2}\big{\\}}\Big{)}.$

Then $E^{\prime}\subset E^{1}$ and $E^{\prime}\subset E^{2}$. Additionally,
the edges $E^{\prime}$ are also in $\mathcal{G}_{-V_{j},\pi_{j}}$ and
$\mathcal{G}_{-V_{i},\pi_{i}}$ as well as in $\mathcal{G}_{1}$ and
$\mathcal{G}_{2}$. In order to specify the edges in $E^{1}\setminus
E^{\prime}$ and $E^{2}\setminus E^{\prime}$ we need to consider edges in
$\mathcal{G}_{-V_{j},\pi_{j}}$ and $\mathcal{G}_{-V_{i},\pi_{i}}$. Hence,
consider the parents and children of $V_{i}$ and $V_{j}$ in
$\mathcal{G}_{-V_{j},\pi_{j}}$ and $\mathcal{G}_{-V_{i},\pi_{i}}$:

$\displaystyle\operatorname{Pa}(V_{i},\mathcal{G}_{-V_{j},\pi_{j}})\cap
Q=\operatorname{Pa}(V_{i},\mathcal{G})\cap
Q=\\{V_{i_{1}},\dots,V_{i_{r_{1}}}\\},$ (20)
$\displaystyle\operatorname{Ch}(V_{i},\mathcal{G}_{-V_{j},\pi_{j}})\cap(Q\cup\\{A\\})=\\{V_{i_{1}},\dots,V_{i_{r^{j}-1}},V_{i_{r^{j}+1}},\dots,V_{i_{r_{1}}}\\}\cup\\{V_{j_{1}},\dots,V_{j_{r_{2}}}\\},$
(21) $\displaystyle\operatorname{Pa}(V_{j},\mathcal{G}_{-V_{i},\pi_{i}})\cap
Q=\\{V_{j}^{1},\dots,V_{j}^{l(i)-1},V_{j}^{l(i)+1},\dots,V_{j}^{l_{2}}\\}\cup\\{V_{i}^{1},\dots,V_{i}^{l_{1}}\\}\cup\\{V_{i_{1}},\dots,V_{i_{r(j)-1}}\\},$
(22)
$\displaystyle\operatorname{Ch}(V_{j},\mathcal{G}_{-V_{i},\pi_{i}})\cap(Q\cup\\{A\\})=\\{V_{j_{1}},\dots,V_{j_{r_{2}}}\\}\cup\\{V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}}\\}.$
(23)

Since $V_{i}\in Q$ and $V_{j}\in\operatorname{Ch}(V_{i},\mathcal{G})\cap Q$
and since $V_{i}$ satisfies Lemma 4.6 or Lemma 4.7, it holds that

$\displaystyle\operatorname{Pa}(V_{j},\mathcal{G})\cap
Q\subseteq(\operatorname{Pa}(V_{i},\mathcal{G})\cap
Q)\cup\\{V_{i},V_{i_{1}},\dots,V_{i_{r(j)-1}}\\}.$ (24)

Additionally, by Eq. 22

$\displaystyle\operatorname{Pa}(V_{j},\mathcal{G}_{-V_{i},\pi_{i}})\cap
Q=\left[(\operatorname{Pa}(V_{j},\mathcal{G})\cap
Q)\setminus\\{V_{i}\\}\right]\cup(\operatorname{Pa}(V_{i},\mathcal{G})\cap
Q)\cup\\{V_{i},V_{i_{1}},\dots,V_{i_{r(j)-1}}\\},$

and Eq. 22 can be rewritten as

$\displaystyle\operatorname{Pa}(V_{j},\mathcal{G}_{-V_{i},\pi_{i}})\cap
Q=\\{V_{i}^{1},\dots,V_{i}^{l_{1}},V_{i_{1}},\dots,V_{i_{r(j)-1}}\\},$ (25)

where all the vertices are listed in a topological ordering consistent with
$\mathcal{G}$ and $\mathcal{G}_{-V_{i},\pi_{i}}$.

Next we consider how to simplify and topologically order in $\mathcal{G}$ the
set
$\\{V_{j_{1}},\dots,V_{j_{r_{2}}}\\}\cup\\{V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}}\\}$
which is contained in both
$\operatorname{Ch}(V_{j},\mathcal{G}_{-V_{i},\pi_{i}})\cap(Q\cup\\{A\\})$ and
$\operatorname{Ch}(V_{i},\mathcal{G}_{-V_{j},\pi_{j}})\cap(Q\cup\\{A\\})$; see
Eqs. 21 and 23.

Let

$\\{V_{{ij}_{1}},\dots
V_{{ij}_{r_{3}}}\\}=(\\{V_{j_{1}},\dots,V_{j_{r_{2}}}\\}\cap
Q)\setminus\\{V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}}\\}$

be a vertex set such that $(V_{{ij}_{1}},\dots V_{{ij}_{r_{3}}})$ is
topologically ordered in $\mathcal{G}$. Since the topological ordering of
$(V_{j_{1}},\dots,V_{j_{r_{2}}})$ is unique by Lemma 5.3, the ordering
$(V_{{ij}_{1}},\dots V_{{ij}_{r_{3}}})$ does not conflict with the ordering
$(V_{j_{1}},\dots,V_{j_{r_{2}}})$. Additionally, by construction of
$\mathcal{G}_{-V_{i},\pi_{i}}$ and $\mathcal{G}_{-V_{j},\pi_{j}}$ from
$\mathcal{G}$, $(V_{{ij}_{1}},\dots V_{{ij}_{r_{3}}})$ is also topologically
ordered in $\mathcal{G}_{-V_{i},\pi_{i}}$ and $\mathcal{G}_{-V_{j},\pi_{j}}$.

The proof is split into two cases.

  1. (a)

$V_{i_{r_{1}}}\neq A\neq V_{j_{r_{2}}}$.

We have $V_{i_{r_{1}}}\neq A$, $A\notin\\{V_{{ij}_{1}},\dots
V_{{ij}_{r_{3}}}\\}$ and both $(V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}})$ and
$(V_{{ij}_{1}},\dots V_{{ij}_{r_{3}}})$ are topologically ordered in
$\mathcal{G}$, $\mathcal{G}_{-V_{i},\pi_{i}}$, and
$\mathcal{G}_{-V_{j},\pi_{j}}$. Hence, for
$(V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}},V_{{ij}_{1}},\dots V_{{ij}_{r_{3}}})$ to
be topologically ordered in $\mathcal{G}$, as well as in
$\mathcal{G}_{-V_{i},\pi_{i}}$, and $\mathcal{G}_{-V_{j},\pi_{j}}$, it is
enough to prove that a vertex $B_{1}\in\\{V_{{ij}_{1}},\dots
V_{{ij}_{r_{3}}}\\}=(\\{V_{j_{1}},\dots,V_{j_{r_{2}}}\\}\cap
Q)\setminus\\{V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}}\\}$ cannot be an ancestor of
a vertex $B_{2}\in\\{V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}}\\}\cap Q$ in
$\mathcal{G}$.

Suppose for a contradiction that such a pair of vertices exists in
$\mathcal{G}$ and choose $B_{1}$ and $B_{2}$ to be a pair of such vertices
with a shortest causal path $p$ from $B_{1}$ to $B_{2}$ in $\mathcal{G}$. By
choice of $B_{1}$ and $B_{2}$, no other vertex on $p$ is in
$\\{V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}}\\}\cap Q$. Since
$B_{2}\in\operatorname{Ch}(V_{i},\mathcal{G})\cap Q$, by Lemmas 4.6 and 4.7,
$\operatorname{Pa}(B_{2},\mathcal{G})\subseteq\operatorname{Pa}(V_{i},\mathcal{G})\cup\\{V_{i},V_{i_{1}},\dots,V_{i_{r(j)}}\\}$.
This, in turn, implies that $B_{1}$ is an ancestor of a vertex in
$\operatorname{Pa}(V_{i},\mathcal{G})\cup\\{V_{i},V_{i_{1}},\dots,V_{i_{r(j)}}\\}$
through $p$, which together with
$B_{1}\in\operatorname{Ch}(V_{j},\mathcal{G})\cap Q$ and $V_{i}\to V_{j}$ in
$\mathcal{G}$, implies that a directed cycle is present in $\mathcal{G}$,
which is a contradiction.

Since $A\neq V_{i_{r_{1}}}$ and $A\neq V_{j_{r_{2}}}$, we also have that the
vertex sets on the right-hand-side of equations (26) and (27) below are listed
in a topological ordering consistent with $\mathcal{G}$,
$\mathcal{G}_{-V_{i},\pi_{i}}$, and $\mathcal{G}_{-V_{j},\pi_{j}}$.

$\displaystyle\operatorname{Ch}(V_{i},\mathcal{G}_{-V_{j},\pi_{j}})\cap(Q\cup\\{A\\})=\\{V_{i_{1}},\dots,V_{i_{r(j)-1}},V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}},V_{{ij}_{1}},\dots
V_{{ij}_{r_{3}}}\\},$ (26)
$\displaystyle\operatorname{Ch}(V_{j},\mathcal{G}_{-V_{i},\pi_{i}})\cap(Q\cup\\{A\\})=\\{V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}},V_{{ij}_{1}},\dots
V_{{ij}_{r_{3}}}\\}.$ (27)

Now consider the set of edges $E^{1}$, which can be decomposed as
$E^{1}=E^{\prime}\cup E^{1}_{i}\cup E^{2}_{j}$. Edges $E^{1}_{i}$ given by

$E^{1}_{i}=\big{\\{}V_{i}^{l}\to V_{i_{r}}:1\leq l\leq l_{1},1\leq r\leq
r_{1},r\neq r(j)\big{\\}}\\\ \cup\big{\\{}V_{i_{r^{\prime}}}\to
V_{i_{r^{\prime\prime}}}:1\leq r^{\prime}<r^{\prime\prime}\leq
r_{1},r^{\prime}\neq r(j)\neq r^{\prime\prime}\big{\\}},$ (28)

are the edges in $\mathcal{G}_{1}$ that are added by transforming
$\mathcal{G}$ into $\mathcal{G}_{-V_{i},\pi_{i}}$. Meanwhile, edges
$E^{2}_{j}$ given by

$E^{2}_{j}=\big{\\{}V_{i}^{l}\to V_{{ij}_{r}}:1\leq l\leq l_{1},1\leq r\leq
r_{3}\big{\\}}\\\ \cup\big{\\{}V_{{i}_{r^{\prime}}}\to
V_{{ij}_{r^{\prime\prime}}}:1\leq r^{\prime}<r_{1},1\leq r^{\prime\prime}\leq
r_{3},r^{\prime}\neq r(j)\big{\\}}\\\ \cup\big{\\{}V_{{ij}_{r^{\prime}}}\to
V_{{ij}_{r^{\prime\prime}}}:1\leq r^{\prime}<r^{\prime\prime}\leq
r_{3}\big{\\}}.$ (29)

are the edges added to $\mathcal{G}_{1}$, by transforming
$\mathcal{G}_{-V_{i},\pi_{i}}$ into
$\mathcal{G}_{1}=(\mathcal{G}_{-V_{i},\pi_{i}})_{-V_{j},\pi_{j}}$. Equation
Eq. 29 uses Eqs. 25 and 27.

By Eqs. 28 and 29, we have that $E^{1}_{i}\cup E^{2}_{j}=E^{1}\setminus
E^{\prime}$ is equal to

$E^{1}_{i}\cup E^{2}_{j}=\big{\\{}V_{i}^{l}\to V_{i_{r}}:1\leq l\leq
l_{1},1\leq r\leq r_{1},r\neq r(j)\big{\\}}\cup\big{\\{}V_{i}^{l}\to
V_{{ij}_{r}}:1\leq l\leq l_{1},1\leq r\leq r_{3}\big{\\}}\\\
\cup\big{\\{}V_{i_{r^{\prime}}}\to V_{i_{r^{\prime\prime}}}:1\leq
r^{\prime}<r^{\prime\prime}\leq r_{1},r^{\prime}\neq r(j)\neq
r^{\prime\prime}\big{\\}}\\\ \cup\big{\\{}V_{{i}_{r^{\prime}}}\to
V_{{ij}_{r^{\prime\prime}}}:1\leq r^{\prime}<r_{1},1\leq r^{\prime\prime}\leq
r_{3},r^{\prime}\neq r(j)\big{\\}}\\\ \cup\big{\\{}V_{{ij}_{r^{\prime}}}\to
V_{{ij}_{r^{\prime\prime}}}:1\leq r^{\prime}<r^{\prime\prime}\leq
r_{3}\big{\\}}.$ (30)

Next, consider the set of edges $E^{2}$, which can be decomposed as
$E^{2}=E^{\prime}\cup E^{1}_{j}\cup E^{2}_{i}$. Edges $E^{1}_{j}$ given by

$E^{1}_{j}=\big{\\{}V_{j}^{l}\to V_{j_{r}}:1\leq l\leq l_{2},1\leq r\leq
r_{2},l\neq l(i)\big{\\}}\cup\big{\\{}V_{j_{r^{\prime}}}\to
V_{j_{r^{\prime\prime}}}:1\leq r^{\prime}<r^{\prime\prime}\leq
r_{1}\big{\\}},$ (31)

are the edges in $\mathcal{G}_{2}$ that are added by transforming
$\mathcal{G}$ into $\mathcal{G}_{-V_{j},\pi_{j}}$. Meanwhile, edges
$E^{2}_{i}$ given by

$E^{2}_{i}=\big{\\{}V_{i}^{l}\to V_{i_{r}}:1\leq l\leq l_{1},1\leq r\leq
r_{1},r\neq r(j)\big{\\}}\cup\big{\\{}V_{i}^{l}\to V_{{ij}_{r}}:1\leq l\leq
l_{1},1\leq r\leq r_{3}\big{\\}}\\\ \cup\big{\\{}V_{i_{r^{\prime}}}\to
V_{{i}_{r^{\prime\prime}}}:1\leq r^{\prime}<r^{\prime\prime}\leq
r_{1},r^{\prime}\neq r(j)\big{\\}}\\\ \cup\big{\\{}V_{i_{r^{\prime}}}\to
V_{{ij}_{r^{\prime\prime}}}:1\leq r^{\prime}\leq r_{1},1\leq
r^{\prime\prime}\leq r_{3},r^{\prime}\neq r(j)\big{\\}}\\\
\cup\big{\\{}V_{{ij}_{r^{\prime}}}\to V_{{ij}_{r^{\prime\prime}}}:1\leq
r^{\prime}<r^{\prime\prime}\leq r_{3}\big{\\}},$ (32)

are the edges added to $\mathcal{G}_{2}$, by transforming
$\mathcal{G}_{-V_{j},\pi_{j}}$ into
$\mathcal{G}_{2}=(\mathcal{G}_{-V_{j},\pi_{j}})_{-V_{i},\pi_{i}}$. Equation
Eq. 32 uses Eqs. 20 and 26.

Based on Eqs. 31 and 32, we have that $E^{1}_{j}\cup E^{2}_{i}=E^{2}\setminus
E^{\prime}$ is equal to

$E^{1}_{j}\cup E^{2}_{i}=\big{\\{}V_{j}^{l}\to V_{j_{r}}:1\leq l\leq
l_{2},1\leq r\leq r_{2},l\neq l(i)\big{\\}}\cup\big{\\{}V_{j_{r^{\prime}}}\to
V_{j_{r^{\prime\prime}}}:1\leq r^{\prime}<r^{\prime\prime}\leq
r_{1}\big{\\}}\\\ \cup\big{\\{}V_{i}^{l}\to V_{i_{r}}:1\leq l\leq l_{1},1\leq
r\leq r_{1},r\neq r(j)\big{\\}}\cup\big{\\{}V_{i}^{l}\to V_{{ij}_{r}}:1\leq
l\leq l_{1},1\leq r\leq r_{3}\big{\\}}\\\ \cup\big{\\{}V_{i_{r^{\prime}}}\to
V_{{i}_{r^{\prime\prime}}}:1\leq r^{\prime}<r^{\prime\prime}\leq
r_{1},r^{\prime}\neq r(j)\neq r^{\prime\prime}\big{\\}}\\\
\cup\big{\\{}V_{i_{r^{\prime}}}\to V_{{ij}_{r^{\prime\prime}}}:1\leq
r^{\prime}\leq r_{1},1\leq r^{\prime\prime}\leq r_{3},r^{\prime}\neq
r(j)\big{\\}}\\\ \cup\big{\\{}V_{{ij}_{r^{\prime}}}\to
V_{{ij}_{r^{\prime\prime}}}:1\leq r^{\prime}<r^{\prime\prime}\leq
r_{3}\big{\\}}.$ (33)

By Eq. 24, we have
$\\{V_{j}^{1},\dots,V_{j}^{l_{2}}\\}\subseteq\\{V_{i}^{1},\dots,V_{i}^{l_{1}}\\}\cup\\{V_{i},V_{i_{1}},\dots,V_{i_{r(j)-1}}\\}$.
Using this property, together with the fact that

$\\{V_{{ij}_{1}},\dots,V_{{ij}_{r_{3}}}\\}=\left[\\{V_{j_{1}},\dots,V_{j_{r_{2}}}\\}\cap(Q\cup\\{A\\})\right]\setminus\\{V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}}\\},$

equation Eq. 33 simplifies to

$E^{1}_{j}\cup E^{2}_{i}=\big{\\{}V_{i}^{l}\to V_{i_{r}}:1\leq l\leq
l_{1},1\leq r\leq r_{1},r\neq r(j)\big{\\}}\cup\big{\\{}V_{i}^{l}\to
V_{{ij}_{r}}:1\leq l\leq l_{1},1\leq r\leq r_{3}\big{\\}}\\\
\cup\big{\\{}V_{i_{r^{\prime}}}\to V_{{i}_{r^{\prime\prime}}}:1\leq
r^{\prime}<r^{\prime\prime}\leq r_{1},r^{\prime}\neq r(j)\neq
r^{\prime\prime}\big{\\}}\\\ \cup\big{\\{}V_{i_{r^{\prime}}}\to
V_{{ij}_{r^{\prime\prime}}}:1\leq r^{\prime}\leq r_{1},1\leq
r^{\prime\prime}\leq r_{3},r^{\prime}\neq r(j)\big{\\}}\\\
\cup\big{\\{}V_{{ij}_{r^{\prime}}}\to V_{{ij}_{r^{\prime\prime}}}:1\leq
r^{\prime}<r^{\prime\prime}\leq r_{3}\big{\\}}.$ (34)

By Eqs. 30 and 34, we have $E^{1}_{j}\cup E^{2}_{i}=E^{1}_{i}\cup E^{2}_{j}$
and therefore $E_{1}=E_{2}$.

  2. (b)

$A=V_{i_{r_{1}}}$ or $A=V_{j_{r_{2}}}$. In this case, the same argument as
above can be used to show that
$(V_{i_{r(j)+1}},\dots,V_{i_{r_{1}-1}},V_{{ij}_{1}},\dots V_{{ij}_{r_{3}}})$
is topologically ordered in $\mathcal{G}$, $\mathcal{G}_{-V_{i},\pi_{i}}$ and
$\mathcal{G}_{-V_{j},\pi_{j}}$. Then, using the fact that $V_{i_{r_{1}}}=A$ or
$V_{j_{r_{2}}}=A$ we know that $V_{i},V_{j}\in W(\mathcal{G})$. Hence, we know
$(V_{i_{r(j)+1}},\dots,V_{i_{r_{1}-1}},V_{{ij}_{1}},\dots V_{{ij}_{r_{3}}},A)$
is a topological ordering in $\mathcal{G}$. Since $V_{i}\in
W(\mathcal{G}_{-V_{j},\pi_{j}})$ and $V_{j}\in
W(\mathcal{G}_{-V_{i},\pi_{i}})$, by Definitions 8 and 5.3,
$(V_{i_{r(j)+1}},\dots,V_{i_{r_{1}-1}},V_{{ij}_{1}},\dots V_{{ij}_{r_{3}}},A)$
is also a topological ordering in $\mathcal{G}_{-V_{i},\pi_{i}}$ and
$\mathcal{G}_{-V_{j},\pi_{j}}$.

Then let $V_{{ij}_{r_{3}+1}}\equiv A$. Equations Eqs. 26 and 27 in this case
become

$\displaystyle\operatorname{Ch}(V_{i},\mathcal{G}_{-V_{j},\pi_{j}})\cap(Q\cup\\{A\\})=\\{V_{i_{1}},\dots,V_{i_{r(j)-1}},V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}},V_{{ij}_{1}},\dots
V_{{ij}_{r_{3}+1}}\\},$
$\displaystyle\operatorname{Ch}(V_{j},\mathcal{G}_{-V_{i},\pi_{i}})\cap(Q\cup\\{A\\})=\\{V_{i_{r(j)+1}},\dots,V_{i_{r_{1}}},V_{{ij}_{1}},\dots
V_{{ij}_{r_{3}+1}}\\}.$

The rest of the argument follows in exactly the same fashion as above, except
that we replace $r_{3}$ with $r_{3}+1$ in the definition of $E_{2}^{j}$ and
$E_{2}^{i}$.

∎

###  D.4 Proof of Theorem 5.1

  * Proof.

    1. (i)

By construction, graph $\mathcal{G}^{\ast}$ has vertex set $V^{\ast}$. By
Lemmas 5.1 and 5.2, $\mathcal{G}^{\ast}$ is a directed acyclic graph.