Necessary and sufficient graphical conditions for optimal adjustment sets in causal graphical models with hidden variables
Year: 2022

Abstract:
The problem of selecting optimal backdoor adjustment sets to estimate causal effects in graphical models with hidden and conditioned variables is addressed. Previous work has defined optimality as achieving the smallest asymptotic estimation variance and derived an optimal set for the case without hidden variables. For the case with hidden variables there can be settings where no optimal set exists and currently only a sufficient graphical optimality criterion of limited applicability has been derived. In the present work optimality is characterized as maximizing a certain adjustment information which allows to derive a necessary and sufficient graphical criterion for the existence of an optimal adjustment set and a definition and algorithm to construct it. Further, the optimal set is valid if and only if a valid adjustment set exists and has higher (or equal) adjustment information than the Adjust-set proposed in Perković et al. [Journal of Machine Learning Research, 18: 1–62, 2018] for any graph. The results translate to minimal asymptotic estimation variance for a class of estimators whose asymptotic variance follows a certain information-theoretic relation. Numerical experiments indicate that the asymptotic results also hold for relatively small sample sizes and that the optimal adjustment set or minimized variants thereof often yield better variance also beyond that estimator class. Surprisingly, among the randomly created setups more than 90% fulfill the optimality conditions indicating that also in many real-world scenarios graphical optimality may hold.

heading: 1 Introduction
text: A standard problem setting in causal inference is to estimate the causal effect between two variables given a causal graphical model that specifies qualitative causal relations among observed variables [Pearl, 2009], including a possible presence of hidden confounding variables. The graphical model then allows to employ graphical criteria to identify valid adjustment sets, the most well-known being the backdoor criterion [Pearl, 1993] and the generalized adjustment criterion [Shpitser et al., 2010, Perković et al., 2015, 2018], providing a complete identification of all valid adjustment sets. Estimators of causal effects based on such a valid adjustment set as a covariate are then unbiased, but for different adjustment sets the estimation variance may strongly vary. An optimal adjustment set may be characterized as one that has minimal asymptotic estimation variance. In current work, following Kuroki and Cai [2004] and Kuroki and Miyakawa [2003], Henckel et al. [2019] (abbreviated
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
HPM19 in the following) showed that graphical optimality always holds for linear models in the causally sufficient case where all relevant variables are observed. In Witte et al. [2020] an alternative characterization of the optimal adjustment set is discussed and the approach was integrated into the IDA algorithm [Maathuis et al., 2009, 2010] that does not require the causal graph to be known. Rotnitzky and Smucler [2019] extended the results in HPM19 to asymptotically linear non-parametric graphical models. HPM19’s optimal adjustment set holds for the causally sufficient case (no hidden variables) and the authors gave an example with hidden variables where optimality does not hold in general, i.e., the optimal adjustment set depends on the coefficients and noise terms (more generally, the distribution), rather than just the graph. Most recently, Smucler et al. [2021] (SSR20) partially extended these results to the non-parametric hidden variables case together with dynamic treatment regimes, i.e., conditional causal effects. SSR20 provide a sufficient criterion for an optimal set to exist and a definition based on a certain undirected graph-construction using a result by van der Zander et al. [2019]. However, their sufficient criterion is very restrictive and a current major open problem is a necessary and sufficient condition for an optimal adjustment set to exist in the hidden variable case and a corresponding definition of an optimal set.
My main theoretical contribution is a solution to this problem. Optimality for conditional causal effects in the hidden variables case is fully characterized by an information-theoretic approach involving a certain difference of conditional mutual informations among the observed variables termed the adjustment information. Maximizing the adjustment information formalizes the common intuition to choose adjustment sets that maximally constrain the effect variable and minimally constrain the cause variable. This allows to derive a necessary and sufficient graphical criterion for the existence of an optimal adjustment set. The derived optimal adjustment set also has the property of minimum cardinality, i.e., no node can be removed without sacrificing optimality. Further, the optimal set is valid if and only if a valid adjustment set exists and has higher (or equal) adjustment information than the Adjust-set proposed in Perković et al. [2018] for any graph, whether graphical optimality holds or not. The results translate to minimal asymptotic estimation variance for a class of estimators whose asymptotic variance follows a certain information-theoretic relation that, at present, I could only verify theoretically for the linear case. As practical contributions the paper provides extensive numerical experiments that corroborate the theoretical results and show that the optimal adjustment set or minimized variants thereof often yield better variance also beyond the theoretically analyzed estimator class. Code is available in the python package https://github.com/jakobrunge/tigramite. More detailed preliminaries, proofs, algorithms, and further numerical experiments are given in the Supplementary Material.

heading: 1.1 Preliminaries and problem setting
text: We consider causal effects in causal graphical models over a set of variables V with a joint distribution P = P(V) that is consistent with an acyclic directed mixed graph (ADMG) G = (V, E). Two nodes can have possibly more than one edge which can be directed (←) or bi-directed (↔). See Fig. 1A for an example. Kinships are defined as usual: parents pa(X) for “•→X”, spouses sp(X) for “X↔•”, children ch(X) for “X→•”. These sets all exclude X . Correspondingly descendants des(X) and ancestors an(X) are defined, which, on the other hand, both include X . The mediator nodes on causal paths from X to Y are denoted M = M(X,Y ) and exclude X and Y . For detailed preliminaries, including the definition of open and blocked paths, see Supplementary Section A. In this work we only consider a univariate intervention variable X and effect variable Y . We simplify set notation and denote unions of variables as {W} ∪M ∪A = WMA. A (possibly empty) set of adjustment variables Z for the total causal effect of X on Y in an ADMG is called valid relative to (X,Y ) if the interventional distribution for setting do(X = x) [Pearl, 2009] factorizes as p(Y |do(X = x)) = ∫ p(Y |x, z)p(z)dz for non-empty Z and as p(Y |do(X = x)) = p(Y |x) for empty Z. Valid adjustment sets, the set of which is here denoted Z , can be read off from a given causal graph using the generalized adjustment criterion [Perković et al., 2015, 2018] which generalizes Pearl’s back-door criterion [Pearl, 2009]. To this end define
forb(X,Y ) = X ∪ des(YM) (1)
(henceforth just denoted as forb). A set Z is valid if both of the following conditions hold: (i) Z ∩ forb = ∅, and (ii) all non-causal paths from X to Y are blocked by Z. An adjustment set is called minimal if no strict subset of Z is still valid. The validity conditions can in principle be manually checked directly from the graph, but, more conveniently, Perković et al. [2018] define an
adjustment set called ‘Adjust’ that is valid if and only if a valid adjustment set exist. In our setting including conditioning variables S we call this set the valid ancestors defined as
vancs(X,Y,S) = an(XY S) \ forb (2) and refer to this set as vancs or Adjust-set.
Our quantity of interest is the average total causal effect of an intervention to set X to x vs. x′ on the effect variable Y given a set of selected (conditioned) variables S = s
∆yxx′|s = E(Y |do(x), s)− E(Y |do(x′), s) . (3)
We denote an estimator given a valid adjustment set Z as ∆̂yxx′|s.z. In the linear case ∆yxx′|s for x = x′ + 1 corresponds to the regression coefficient βY X·ZS in the regression of Y on X , Z, and S. The ordinary least squares (OLS) estimator β̂Y X·ZS is a consistent estimator of βY X·ZS.
Figure 1A illustrates the problem setting: We are interested in the total causal effect of (here univariate) X on Y (conditioned on S), which is here due to a direct link and an indirect causal path through a mediator M . There are six valid backdoor adjustment sets Z = {Z1, Z2, Z1Z2, Z2Z3, Z1Z3, Z1Z2Z3}. Z4 ∈ forb cannot be included in any set because it is a descendant of YM. Here vancs = Z1Z2S. All valid adjustment sets remove the bias due to confounding by their definition. The question is which of these valid adjustment sets is statistically optimal in that it minimizes the asymptotic estimation variance? More formally, the task is, given a graph G and (X,Y,S), to chose a valid optimal set Zoptimal ∈ Z such that the causal effect estimator’s asymptotic variance Var(∆̂yxx′|s.z) = E[(∆yxx′|s − ∆̂yxx′|s.z)2] is minimal:
Zoptimal ∈ argminZ∈ZVar(∆̂yxx′|s.z) . (4)
My proposed approach to optimal adjustment sets is based on information theory [Cover and Thomas, 2006]. The main quantity of interest there is the conditional mutual information (CMI) defined as a difference IX;Y |Z = HY |Z − HY |ZX of two (conditional) Shannon entropies HY |X = − ∫ x,y
p(x, y) ln p(y|x)dxdy. Its main properties are non-negativity, IX;Y |Z = 0 if and only if X ⊥⊥ Y |Z, and the chain rule IXW ;Y |Z = IX;Y |Z + IW ;Y |ZX . All random variables in a CMI can be multivariate.
Throughout the present paper we will assume the following. Assumptions 1 (General setting and assumptions). We assume a causal graphical model over a set of variables V with a joint distribution P = P(V) that is consistent with an ADMG G = (V, E). We assume a non-zero causal effect from X on Y , potentially through a set of mediators M, and given selected conditioned variables S, where S ∩ forb = ∅. We assume that at least one valid adjustment set (given S) exists and, hence, the causal effect is identifiable (except when stated otherwise). Finally, we assume the usual Causal Markov Condition (implicit in semi-Markovian models) and Faithfulness.

heading: 2 Optimal adjustment sets

heading: 2.1 Information-theoretic characterization
text: Figure 1B illustrates two causal effect estimates for a linear Gaussian model consistent with the graph in Fig. 1A. With Z = Z1Z2 (blue) the error is much larger than with O = Z2Z3 (orange) for two reasons: Z constrains the residual variance V ar(Y |ZS) of the effect variable Y less than O and, on the other hand, Z constrains the residual variance V ar(X|ZS) of the cause variable X more than O. Smaller estimator variance also holds for O compared to any other valid set in Z here. We information-theoretically formalize the resulting intuition to choose an adjustment set Z that maximally constrains the effect variable Y and minimally constrains the cause variable X . In terms of CMIs and given selected fixed conditions S the quantity to maximize can be stated as follows. Definition 1 (Adjustment information). Consider a causal effect of X on Y for an adjustment set Z given a condition set S. The (conditional) adjustment (set) information, abbreviated JZ, is defined as
JXY |S.Z ≡ IZ;Y |XS − IX;Z|S (5) = HY |XS −HX|S︸ ︷︷ ︸
not related to Z − (HY |XZS −HX|ZS)︸ ︷︷ ︸ adjustment entropy
(6)
JZ is not necessarily positive if the dependence between X and Z (given S) is larger than that between Z and Y given XS. Equation (6) follows from the CMI definition. Fig. 1C illustrates the two CMIs in Eq. (5) in a Venn diagram.
Before discussing the range of estimators for which maximizing the adjustment information JZ leads to a minimal asymptotic estimation variance in Sect. 2.2, we characterize graphical optimality in an information-theoretic framework. Our goal is to provide graphical criteria for optimal adjustment sets, i.e., criteria that depend only on the structure of the graph G and not on the distribution. Definition 2 (Information-theoretical graphical optimality). Given Assumptions 1 we say that (information-theoretical) graphical optimality holds if there is a Z ∈ Z such that either there is no other Z′ ̸= Z ∈ Z or for all other Z′ ̸= Z ∈ Z and all distributions P consistent with G we have JZ ≥ JZ′ .
My main result builds on the following lemma which relates graphical optimality to informationtheoretic inequalities in a necessary and sufficient comparison condition for an optimal set to exist. Lemma 1 (Necessary and sufficient comparison criterion for existence of an optimal set). Given Assumptions 1, if and only if there is a Z ∈ Z such that either there is no other Z′ ̸= Z ∈ Z or for all other Z′ ̸= Z ∈ Z and all distributions P consistent with G it holds that
IZ\Z′;Y |Z′XS︸ ︷︷ ︸ (i) ≥ IZ′\Z;Y |ZXS︸ ︷︷ ︸ (iii) and IX;Z′\Z|ZS︸ ︷︷ ︸ (ii) ≥ IX;Z\Z′|Z′S︸ ︷︷ ︸ (iv) , (7)
then graphical optimality holds and Z is optimal implying JZ ≥ JZ′ .
In SSR20 and HPM19 the corresponding conditional independence statements to the terms (iii) and (iv) in the inequalities (7) are used as a sufficient pairwise comparison criterion. However, Lemma 1 shows that for graphical optimality it is not necessary that terms (iii) and (iv) vanish, they just need to fulfill the inequalities (7) for a necessary and sufficient criterion.
In principle, Lemma 1 can be used to cross-compare all pairs of sets, but firstly, it is difficult to explicitly evaluate (7) for all distributions P consistent with G and, secondly, iterating through all valid adjustment sets is computationally prohibitive even for small graph sizes. As an example, consider a confounding path consisting of 5 nodes. Then this path can be blocked by 25 − 1 different subsets. In the main result of this work (Thm. 3) a necessary and sufficient criterion based purely on graphical properties is given.

heading: 2.2 Applicable estimator class
text: The above characterization only relates optimality of adjustment sets to the adjustment information JZ defined in Eq. (5), but not to any particular estimator. Now the question is for which class of
causal effect estimators ∆̂yxx′|s.z the intuition of maximizing the adjustment information JZ leads to a minimal asymptotic estimation variance. In its most general form this class is characterized as fulfilling
Zoptimal ∈ argmaxZ∈ZJZ ⇔ Var(∆̂yxx′|s.zoptimal) = min Z∈Z Var(∆̂yxx′|s.z) , (8)
where we assume that ∆̂yxx′|s.z is consistent due to a valid adjustment set and correct functional model specification. One can also further restrict the class to estimators whose (square-root of the) asymptotic variance can be expressed as√
Var(∆̂yxx′|s.z) = f(HY |XZS −HX|ZS) , (9)
for a real-valued, strictly monotonously increasing function of the adjustment entropy. Minimizing the adjustment entropy is by Eq. (6) equivalent to maximizing the adjustment information. The following assumption and lemma then relates JZ ≥ JZ′ to the corresponding asymptotic variances of a given estimator. Assumptions 2 (Estimator class assumption). The model class of the estimator for the causal effect (3) is correctly specified and its asymptotic variance can be expressed as in relation (9). Lemma 2 (Asymptotic variance and adjustment information). Given Assumptions 1 and an estimator fulfilling Assumptions 2, if and only if for two different adjustment sets Z,Z′ ∈ Z we have JZ ≥ JZ′ , then the adjustment set Z has a smaller or equal asymptotic variance compared to Z′.
Proof. By Equations (6) and (9) JZ ≥ JZ′ (for fixed X,Y,S) is directly related to a smaller or equal asymptotic variance for Z compared to Z′, and vice versa. □
The paper’s theoretical results currently hold for estimators fulfilling relation (9), but at least the main result on graphical optimality in Thm. 3 can also be relaxed to estimators fulfilling the less restrictive relation (8). In this work, we leave the question of which general classes of estimators fulfill either relation (8) or the more restricted relation (9) to further research and only show that it holds for the OLS estimator β̂Y X·ZS for Gaussian distributions.
For Gaussians the entropies in (9) are given by H(Y |XZS) = 12+ 1 2 ln(2πσ 2 Y |XZS) and H(X|ZS) = 1 2 + 1 2 ln(2πσ
2 X|ZS) where σ(·|·) denotes the square-root of the conditional variance. Then√
Var(∆̂yxx′|s.z) = 1√ n eHY |XZS−HX|ZS = 1√ n σY |XZS σX|ZS . (10)
This relation is also the basis of the results for the causally sufficient case in Henckel et al. [2019] where it is shown that it holds more generally for causal linear models that do not require the noise terms to be Gaussian.

heading: 2.3 Definition of O-set
text: The optimal adjustment set for the causally sufficient case is simply P = pa(YM) \ forb and was derived in HPM19 and Rotnitzky and Smucler [2019]. In Section B.2 the derivation is discussed from an information-theoretic perspective. In the case with hidden variables we need to account for bidirected edges “↔” which considerably complicate the situation. Then the parents of YM are not sufficient to block all non-causal paths. Further, just like conditioning on parents of YM leads to optimality in the sufficient case since parents constrain information in YM, in the hidden variables case also conditioning on spouses of YM constrains information about YM.
Example A. A simple graph (ADMG) to illustrate this is X→Y↔Z1 (shown with an additional S in Fig. 2A below, or Fig. 4 in SSR20). Here Z′ = ∅ = vancs is a valid set, but it is not optimal. Consider O = Z1, then term (iii) = 0 in the inequalities (7) since Z′ \O = ∅. Even though not needed to block non-causal paths (there is none), Z1 still constrains information in Y while being independent of X (hence, term (iv) = 0) which leads to JO > J∅ according to the inequalities (7).
Not only direct spouses can constrain information in Y as Fig. 2B below illustrates. Since for W ∈ YM the motif “W↔ C1 ←∗C2” (“∗” denotes either edge mark) is open, it holds that I(C1C2;W ) = I(C1;Y )+I(C2;W |C1) ≥ I(C1;Y ) and we can even further increase the first term in the adjustment
information by conditioning also on subsequent spouses. This chain of colliders only ends if we reach a tail or there is no further adjacency. However, we have to make sure that conditioning on colliders does not open non-causal paths. This leads to the notion of a valid collider path (related to the notion of a district in Evans and Richardson [2014]). Definition 3 (Valid collider paths). Given a graph G, a collider path of W for k ≥ 1 is defined by a sequence of edges W↔C1↔· · ·↔Ck. We denote the set of path nodes (excluding W ) along a path indexed by i as πiW . Using the set of valid ancestors vancs = an(XY S) \ forb for the causal effect of X on Y given S we call a collider path node set πiW for W ∈ YM valid wrt. to (X,Y,S) if for each path node C ∈ πiW both of the following conditions are fulfilled:
(1) C /∈ forb, and (2a) C ∈ vancs or (2b) C ⊥⊥ X | vancs . (11)
Condition (1) is required for any valid adjustment set. If jointly (2a) and (2b) are not fulfilled, i.e. C /∈ vancs and C ⊥⊥X | vancs, then the collider path stops before C. Our candidate optimal adjustment set is now constructed based on the parents of YM, valid collider path nodes of YM, and their parents to ‘close’ these collider paths. Definition 4 (O-set). Given Assumptions 1 and the definition of valid colliders in Def. 3, define the set O(X,Y,S) = P ∪C ∪PC where
P = pa(YM) \ forb, C = ⋓W∈YM ⋓i {πiW : πiW is valid wrt. to (X,Y,S)}, PC = pa(C) .
In the following we will abbreviate O = O(X,Y,S). Algorithm C.1 states efficient pseudo-code to construct the O-set and detect whether a valid adjustment set exists. Since none of the conditions of Def. 3 for adding collider nodes depends on previously added nodes, the algorithm is orderindependent. The statement occurring in lines 11 and 21 (“No valid adjustment set exists.”) is proven in Thm. 1. If the graph is a DAG, then lines 4-22 can be omitted. The algorithm is of low complexity and the most time-consuming part is checking for a path in line 12, Def. 3(2b) C ⊥⊥ X | vancs, which can be implemented with (bi-directional) breadth-first search as proposed in van der Zander et al. [2019].
Numerical experiments in Section 3 will show that further interesting adjustment sets are the minimized O-set Omin, where O is minimized such that no subset can be removed without making Omin invalid, and the collider-minimized O-set OCmin where only CPC \ P ⊆ O is minimized such that no collider-subset can be removed without making OCmin invalid. Both adjustment sets can be constructed with Alg. C.2 similar to the efficient algorithms in van der Zander et al. [2019]. Also the minimized sets are order-independent since the nodes are removed only after the for-loops. Based on the idea in OCmin, in the numerical experiments we also consider AdjustXmin, where only Adjust \ pa(YM) is minimized and pa(YM) is always included. Finally, we also evaluate Adjustmin where Adjust is fully minimized.
Before discussing the optimality of the O-set, we need to assure that it is a valid adjustment set. Similar to the proof given in Perković et al. [2018] for the validity of the vancs-set (for the case without S), we can state that the O-set is valid if and only if a valid adjustment set exists. Theorem 1 (Validity of O-set). Given Assumptions 1 but without a priori assuming that a valid adjustment set exists (apart from the requirement S ∩ forb = ∅). If and only if a valid backdoor adjustment set exists, then O is a valid adjustment set.

heading: 2.4 Graphical optimality
text: We now move to the question of optimality. It is known that there are graphs where no graphical criterion exists to determine optimality. Examples, discussed later, are the graphs in Figs. 2E,F.
Before stating necessary and sufficient conditions for graphical optimality, I mention that next to the O-set defined above and the Adjust set vancs [Perković et al., 2018], I am not aware of any other systematically constructed set that will yield a valid adjustment set for the case with hidden variables. van der Zander et al. [2019] provide algorithms to list all valid adjustment sets, but the question is which of these a user should choose. As mentioned above, Lemma 1 can be used to cross-compare all pairs of sets, but this is not really feasible. Hence, for automated causal effect estimation, rather than the question of whether graphical optimality holds, it is crucial to have a set with better properties than other systematically constructable sets. The following theorem states that
the adjustment informations follow JO ≥ Jvancs for any graph (whether graphical optimality holds or not). Theorem 2 (O-set vs. Adjust-set ). Given Assumptions 1 with O defined in Def. 4 and the Adjust-set defined in Eq. (2), it holds that JO ≥ Jvancs for any graph G. We have JO = Jvancs only if (1) O = vancs, or (2) O ⊆ vancs and X ⊥⊥ vancs \O |OS.
In the following the O-set is illustrated and conditions for graphical optimality are explored. SSR20 provide a sufficient condition for optimality, which states that either all nodes are observed (no bidirected edges exist) or for all observed nodes V ⊂ vancs. This is a very strict assumption and not fulfilled for any of the examples (except for Example G) discussed in the following.
Example B. Figure 2B depicts a larger example to illustrate the O-set O = PCPC with P = Z1Z2Z3Z4 (blue boxes) and CPC \ P = Z5Z6Z7Z8 (green boxes). We also have a conditioned variable S. Among P, only Z1Z2 are needed to block non-causal paths to X , Z3Z4 are only there to constrain information in Y . Here the same holds for the whole set CPC \ P which was constructed from the paths Y↔Z5↔Z6←Z7 and Y↔Z5↔Z8 which does not include Z9 since it is a descendant of YM. Including an independent variable like Z12 in O would not decrease the adjustment information JO, but then O would not be of minimum cardinality anymore (proven in Cor. B.1). Here, again, the condition of SSR20 does not hold (e.g., Z5 is not an ancestor of XY S). O is optimal here which can be seen as follows: For term (iii) in the inequalities (7) to even be non-zero, we would need a valid Z such that Z \O has a path to Y given OSX . But these are all blocked. Note that while Z10 or Z9 ∈ Z would open a path to Y , both of these are descendants of M or Y and, hence, cannot be in a valid Z. For term (iv) to even be non-zero O \ Z would need to have a path to X given ZS. But since any valid Z has to contain Z1 and Z2 (or Z11), the only nodes in O with a path to X are parents of YM and paths from these parents to X all need to be blocked for a valid Z. Hence, O is optimal here.
Example C. In Fig. 2C a case is shown where O = Z1Z5. Z2 is not part of O because none of the conditions in Def. 3(2) is fulfilled: Z2 /∈ vancs = Z1Z4Z5 and Z2 ⊥⊥X | vancs. Hence, we call Z2 an N-node. But Z2 cannot be part of any valid Z because it has a collider path to X through Z1 which is always open because it is part of vancs. Hence, term (iii) is always zero. Term (iv) is zero because O \ Z is empty for any valid Z here. Here even JO > JZ since O is minimal and term (ii) IX;Z\O|O > 0 for any Z ̸= O (generally proven in Corollary B.1). Example D. The example in Fig. 2D depicts a case with O = Z2 where Z1 is an N-node. Next to Z = ∅ another valid set is Z = Z1. Then term (iii) is non-zero and in the same way term (iv) is non-zero. The sufficient pairwise comparison criterion in SSR20 and HPM19 is, hence, not applicable. However, it holds that always term (iii) ≤ (i) because the dependence between Z1 and Y given X is
always smaller than the dependence between Z2 and Y given X and correspondingly term (iv) ≤ (ii). Hence, O is optimal here. If a link Y→Z1 exists, then the only other valid set is Z = ∅ and both terms are strictly zero.
Example E. The example in Fig. 2E (Fig. 3 in SSR20 and also discussed in HPM19) is not graphically optimal. Here O = Z1Z2. Other valid adjustment sets are Z1 or the empty set. From using Z1 ⊥⊥ Y |X and X ⊥⊥ Z2|Z1 in the inequalities (7) one can derive in information-theoretic terms that both Z1Z2 and ∅ are better than vancs = Z1, but since JZ1Z2 = J∅ + IZ2;Y |XZ1 − IX;Z1 , a superior adjustment set depends on how strong the link Z1→X vs. Z2↔Y is. The graph stays non-optimal also with a link Z1↔Z2. Example F. The example in Fig. 2F is also not graphically optimal. Here O = ∅ and Z2 is an N-node with a non-collider path to X . Other valid adjustment sets are Z1 and Z1Z2. Higher adjustment information here depends on the distribution. Also the same graph with the link Z1↔X is non-optimal. If, however, there is another link Z1→Y , then O = ∅ is optimal (then Z1 is a mediator). Example G. The example in Fig. 2G is only a slight modification of Example E with an added selected condition S. Then Z1, Z2 ∈ vancs. We still get O = Z1Z2 and this is now optimal since Z2 is always open and any valid set has to contain Z1.
The main result of this work is a set of necessary and sufficient conditions for the existence of graphical optimality and the proof of optimality of the O-set which is based on the intuition gained in the preceding examples. Theorem 3 (Necessary and sufficient graphical conditions for optimality and optimality of O-set). Given Assumptions 1 and with O = PCPC defined in Def. 4. Denote the set of N-nodes by N = sp(YMC)\ (forbOS). Finally, given an N ∈ N and a collider path N↔· · ·↔C↔· · ·↔W (including N↔W ) for C ∈ C and W ∈ YM (indexed by i) with the collider path nodes denoted by πNi (excluding N and W ), denote by OπNi = O(X,Y,S
′ = SNπNi ) the O-set for the causal effect of X on Y given S′ = S ∪ {N} ∪ πNi . If and only if exactly one valid adjustment set exists, or both of the following conditions are fulfilled, then graphical optimality holds and O is optimal:
(I) For all N ∈ N and all its collider paths i to W ∈ YM that are inside C it holds that OπNi does not block all non-causal paths from X to Y , i.e., OπNi is non-valid,
and
(II) for all E ∈ O \P with an open path to X given SO \ {E} there is a link E↔W or an extended collider path E∗→C↔· · ·↔W inside C for W ∈ YM where all colliders C ∈ vancs.
Condition (I) and (II) essentially rule out the two canonical cases in Examples F and E, respectively, on which non-optimality in any graph is based. Applied to the examples, we obtain that in Example A Cond. (I) holds since no N-node exists and Cond. (II) holds since X ⊥⊥ Z1 | S. In Example B also no N-node exists and Cond. (II) holds as X ⊥⊥ E | SO \ {E} for every E ∈ O \ P. In example C Z2 is an N-node, but there is a collider path to X through Z1 which is in vancs such that Cond. I is fulfilled. Further, while X ⊥⊥ Z5 | SO \ {Z5}, there is a link Z5↔Y such that Cond. II holds. In example D Z1 is an N-node, but it has a bidirected link with X and Cond. (II) holds since X ⊥⊥ Z2 | SO \ {Z2}. In Example E optimality does not hold, but Cond. (I) actually holds since there is no N-node. Cond. (II) is not fulfilled for E = Z1, which has a path to X given O and on the extended collider path Z1→Z2↔Y Z2 /∈ vancs. For Z′ = ∅ and a distribution P ′ where the link Z2↔Y almost vanishes we then have JO < JZ′ . Example F has an N-node Z2 and OπNi = O(X,Y,S
′ = Z2) = Z1Z2 is valid implying that Cond. (I) does not hold, while Cond. (II) is actually fulfilled with O = ∅. For Z′ = OπNi = Z1Z2 and a distribution P
′ where the link X→Z1 almost vanishes we then have JO < JZ′ . Example G is optimal since there are no N-nodes and Z2 ∈ vancs. Similar to SSR20, HPM19, and Witte et al. [2020], I also provide results regarding minimality and minimum cardinality for the hidden variables case in the Supplement.

heading: 3 Numerical experiments
text: We now investigate graphical optimality empirically to answer three questions: Firstly, whether for a linear estimator under Assumptions 2 the asymptotically optimal variance also translates into better
finite-sample variance. Secondly, how the O-set performs in non-optimal settings (according to Thm. 3). Thirdly, how the O-set and variants thereof perform for estimators not captured by the class for which the theoretical results were derived (Assumptions 2). To this end, we compare the performance of O, Adjust, OCmin, Omin, AdjustXmin, and Adjustmin (see definitions in Section 2.3) together with linear least squares estimation (LinReg) on linear models. In the Supplement we also investigate nonlinear models using nearest neighbor regression (kNN), a multilayer perceptron (MLP), random forest regression, and double machine learning for partially linear regression models (DML) [Chernozhukov et al., 2018]. The experiments are based on a generalized additive model and described in detail in Section D. Among these 12,000 randomly created configurations 93% fulfill the optimality conditions in Thm. 3.
The results in Fig. 3 confirm our first hypothesis that for linear experiments with an estimator fulfilling Assumptions 2 and in settings where graphical optimality is fulfilled (Thm. 3) the O-set either has similar RMSE or significantly outperforms all other tested variants. In particular, Omin and Adjustmin are bad choices for this setting. Adjust is intermediate and OCmin and AdjustXmin come closest to O, but may still yield significantly higher variance.
Secondly, in non-optimal settings (only 7% of configurations) the O-set still outperforms Adjust (as expected by Thm. 2). Compared to OCmin and AdjustXmin the O-set leads to worse results for about half of the studied configurations, while Omin and Adjustmin are still bad choices. Cardinality is slightly higher for O compared to all other sets. In Fig. S7 we further differentiate the results by the cardinality of the O-set and find that for small cardinalities (up to 4) the O-set has the lowest variance in a majority of cases, but for higher cardinalities either OCmin or again O have the lowest variance (slightly beating AdjustXmin). Hence, either O or OCmin performs best in non-optimal configurations. For very small sample sizes n = 30 (see Fig. S2) that become comparable to the adjustment set cardinality, there tends to be a trade-off and smaller cardinality helps. Then OCmin tends to be better than O for high cardinalities also in optimal settings, but here this effect is only present for n = 30 and for n = 50 already negligible compared to the gain in JO. In Appendix D.2 are RMSE ratios for all combinations of adjustment approaches considered here and it is shown that, in general, results are very similar for other sample sizes.
Thirdly, we investigate non-parametric estimators on linear as well as nonlinear models (implementations described in Section D, results in the figures of Section D.3) The different classes of estimators exhibit quite different behavior. For kNN (Figs. S8,S9) the O-set has the lowest variance in around 50% of the configurations followed by OCmin and Omin. More specifically (Figs. S15,S16), for small O-set cardinalities up to 2 the O-set and for higher either Omin or OCmin (the latter only in non-optimal configurations) perform best. For nonlinear experiments the results are less clear for O-set cardinalities greater than 2, but Omin is still a good choice. Regarding RMSE ratios, we see that, for the cases where O is not the best, the O-set can have considerably higher variance, while Omin seems to be most robust and may be a better choice if O is too large. MLP (Figs. S10,S11) behaves much differently. Here in optimal cases neither method outperforms any other for small
O-set cardinalities, but for higher cardinalities (Figs. S15,S16) the O-set is best in more than 50% of configurations (slightly less for nonlinear experiments) and the others share the rest (except Adjustmin). For non-optimal cases O, OCmin and AdjustXmin share the ranks. Regarding RMSE, for linear experiments the O-results are almost as optimal as for the LinReg estimator in the optimal setting. However, for non-optimal cases OCmin can have considerably smaller variance and seems to be a robust option then, similarly to AdjustXmin. Also for nonlinear experiments OCmin is more robust. The RF estimator (Figs. S12,S13) is again different. Here no method clearly is top-ranked, Omin and Adjustmin are slightly better for linear experiments and O for nonlinear experiments. OCmin and Omin are more robust regarding RMSE ratios (similar to AdjustXmin). Finally, the DML estimator (Fig. S14) was here applied only to linear experiments since its model assumption does not allow for fully nonlinear settings. For optimal settings here O is top-ranked in a majority of cases, but closely followed by OCmin and AdjustXmin. In non-optimal cases for higher O-set cardinalities these two seem like a better choice. Quantitatively, OCmin and AdjustXmin are the most robust choices.
Overall, the O-set and its variants seem to outperform or match the Adjust-variants and whether higher cardinality of the O-set reduces performance depends strongly on the estimator and data.

heading: 4 Discussion and Conclusions
text: The proposed adjustment information formalizes the common intuition to choose adjustment sets that maximally constrain the effect variable and minimally constrain the cause variable. The main theoretical contributions are a necessary and sufficient graphical criterion for the existence of an optimal adjustment set in the hidden variables case and a definition and algorithm to construct it. To emphasize, graphical optimality implies that the O-set is optimal for any distribution consistent with the graph. Note that in cases where graphical optimality does not hold, there will still be distributions for which the O-set has maximal adjustment information.
Further, the optimal set is valid if and only if a valid adjustment set exists and has smaller (or equal) asymptotic variance compared to the Adjust-set proposed in Perković et al. [2018] for any graph, whether graphical optimality holds or not. This makes the O-set a natural choice in automated causal inference analyses. Practical contributions comprise Python code to construct adjustment sets and check optimality, as well as extensive numerical experiments that demonstrate that the theoretical results also hold for relatively small sample sizes.
The theoretical optimality results are limited to estimators for which the asymptotic variance becomes minimal for adjustment sets with maximal adjustment information (relation (8)). This is fulfilled for least-squares estimators, where even the direct relation (9) holds, but it is unclear whether this also holds for more general classes. The numerical results show that the O-set or minimized variants thereof often yield smaller variance also in non-optimal settings and beyond that estimator class. I speculate that further theoretical properties of maximizing adjustment information can be shown because relation (9) for f(·) = 1√
n eHY |XZS−HX|ZS seems related to the lower bound of the
estimation variance counterpart to Fano’s inequality (Theorem 8.6.6 in Cover and Thomas [2006]). For estimators sensitive to high-dimensionality one may consider data-driven criteria or penalties to step-wisely minimize the O-set. However, estimating, for example, the adjustment information from a potentially small sample size carries considerable errors itself. Another current limitation is that relation (9) only holds for univariate singleton cause variables X . The information-theoretical results, however, also hold for multivariate X and preliminary results indicate that, while relation (9) does not hold for multivariate X, the less restrictive relation (8) still seems to hold.
The proposed information-theoretic approach can guide further research, for example, to theoretically study relations (8),(9) for other estimators and to address other types of graphs as emerge from the output of causal discovery algorithms and the setting where the graph is unknown [Witte et al., 2020, Maathuis et al., 2009, 2010]. At present, the approach only applies to ADMGs and Maximal Ancestral Graphs (MAG) [Richardson and Spirtes, 2002] without selection variables. Last, it remains an open problem to identify optimal adjustment estimands for the hidden variables case based on other criteria such as the front-door formula and Pearl’s general do-calculus [Pearl, 2009].
The results may carry considerable practical impact since, surprisingly, among the randomly created configurations more than 90% fulfill the optimality conditions indicating that also in many realworld scenarios graphical optimality may hold. Code is available in the python package https: //github.com/jakobrunge/tigramite.
Acknowledgments and Disclosure of Funding
I thank Andreas Gerhardus for very helpful comments. This work was funded by the ERC Starting Grant CausalEarth (grant no. 948112).

Review summaries:
In this paper, the authors propose a criterion to select the optimal adjustment set. The authors propose a criterion (Eq. 4 and Def. 2) based on information theory to select which adjustment set is best. And they build the connections between this criterion to the common used minimized asymptotic variance (Eq. 7) for linear Gaussian causal model. Based on these, they propose a necessary and sufficient criterion for the existence of an optimal set. However, it is inefficient due to the large number of comparisons. Hence, the authors present an algorithm to find the o-set, which could be as the optimal set under some conditions as Thm. 3.

The paper defines the optimality of a (valid) adjustment set in terms of a notion called 'adjustment information.'  Then, it focuses on estimators for which maximizing adjustment information equates to minimizing asymptotic estimation variance. The authors provide a sufficient and necessary graphical criterion for the existence of an optimal adjustment set under this notion. They also give an explicit and efficient construction of an adjustment set called the O set, which is proven to be optimal whenever graph optimality holds (the constraints in the graph are sufficient to determine an optimal adjustment set).