Local Learning for Covariate Selection in Nonparametric Causal Effect Estimation with Latent Variables
Authors: Zheng Li
Xichen Guo
Feng Xie
Yan Zeng
Hao Zhang
Zhi Geng
Venue: NeurIPS 2025 poster ()
Keywords: Causal Effect
Covariate Selection
Latent Variables
Local Learning
Causal Discovery
Primary area: probabilistic_methods
TL;DR: We propose a novel local learning approach for covariate selection in nonparametric causal effect estimation, which accounts for the presence of latent variables.

Abstract: Estimating causal effects from nonexperimental data is a fundamental problem in many fields of science. A key component of this task is selecting an appropriate set of covariates for confounding adjustment to avoid bias. Most existing methods for covariate selection often assume the absence of latent variables and rely on learning the global causal structure among variables. However, identifying the global structure can be unnecessary and inefficient, especially when our primary interest lies in estimating the effect of a treatment variable on an outcome variable. To address this limitation, we propose a novel local learning approach for covariate selection in nonparametric causal effect estimation, which accounts for the presence of latent variables. Our approach leverages testable independence and dependence relationships among observed variables to identify a valid adjustment set for a target causal relationship, ensuring both soundness and completeness under standard assumptions. We validate the effectiveness of our algorithm through extensive experiments on both synthetic and real-world data.

Local Learning for Covariate Selection in Nonparametric Causal Effect Estimation with Latent Variables
Zheng Li Xichen Guo', Feng Xiel.*, Yan Zeng', Hao Zhang?.*, Zhi Gengb
Department of Applied Statistics, Beijing Technology and Business University, Beijing, China SIAT, Chinese Academy of Sciences, Shenzhen, China
Abstract
Estimating causal effects from nonexperimental data a fundamental problem many fields of science. A key component of this task is selecting appropriate set of covariates for confounding adjustment to avoid bias. Most existing methods for covariate selection often assume the absence of latent variables and rely on learning the global causal structure among variables. However, identifying the global structure be unnecessary and inefficient, especially when primary interest lies in estimating the effect of a treatment variable on an outcome variable. To address this limitation, selection in nonparametric causal effect estimation, which accounts for the presence of latent variables. Our approach leverages testable independence and dependence relationships among observed variables to identify valid adjustment set for a target causal relationship, ensuring both soundness and completeness under standard assumptions. We validate the effectiveness of our algorithm through extensive experiments on both synthetic and real-world data.
propose novel local learning approach for covariate
1 Introduction
Estimating causal effects crucial in various fields such as epidemiology (Heráán and Robins 2006), social sciences [Spirtes et al., 2000). economics [Imbens and Rubin] 2015). and artificial intelligence [Peters al. 2017 Chu
202T]. these domains, understanding and accurately estimating causal relationships are vital for policy-making, clinical decisions, and scientific research. Within the framework of causal graphical models, covariate adjustment, such as the use of the back-door powerful and primary tool for estimating causal effects from observational data, since implementing idealized experiments in practice is difficult (Pearl 2009). Formally speaking, let do(x) stand for an idealized experiment intervention, where the values of X are set to æ, and o [y] denote the causal effect of X on Y. A valid covariate a set of variables Z such that f(y do(x)) J2. [y x. fz) (Pearl 2009 Shpitser al. 2010]. Consider the graph (a) in Figure. [ Z {VG) } is valid covariate set w.r.t. (with respect to) the causal relationship X K.
criterion [Pear]] 1993]. emerges
Given a causal graph, one can determine whether a set is a valid adjustment set using adjustment criteria such as the back-door criterion [Pearl 1993 2009]. The main challenge covariate ad- justment estimation is to find valid covariate set that satisfies the back-door criterion using only observational data, without prior knowledge the causal graph. To tackle this challenge, Maathuis et al. 22099 proposed the IDA (Intervention do-calculus when the DAG (Directed Acyelic Graph) is Absent) algorithm. This algorithm first learns CPDAG (Complete Partial Directed Acyelic Graph)
"Corresponding authors: Feng Xie <fengxie@ wtw.eiieeebbb..u......... Hao Zhang <h.zhang 10 ai.t.cccn>>
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

V3
V2
V2
V3
V1
Y
X
V/
(a)
(b)
(c)
Figure 1: Example MAGs with treatment X and outcome Y. Nodes shaded in green represent valid adjustment set. (a) Both global search EHS and local search CEELS methods identify the adjustment set. (b) Adapted from Cheng et al. [2022), CEELS fails to select the adjustment set despite the presence of COSO variable V12 (See Fig. 4 in Cheng et al. (2022). (c) An example without COSO
variable, where the adjustment set can still be found locally.
using the PC (Peter-Clark) algorithm [Spirtes and Glymour [,91], enumerates all Markov equivalent DAGs, and estimates all possible causal effects of a treatment on an outcome. Additionally, with domain knowledge about specific causal directions, one can further identify more precise causal effects [Perkovic et al. 2017 Fang and He, 2020). For instance, Perkovic et al. [2017) proposed the semi-local IDA algorithm, which provides a bound estimation of causal effect when some directed edge orientation information is available. To efficiently find covariates, a local method CovSel utilizes criteria from De Luna et al. [001]] for covariate selection (Häggström et al. 2015). Though these
methods have been used in range of fields, they may fail to produce convincing results in cases with latent confounders, as they do not properly take into account the influences from latent variables MMathhuis and Colombo 2015].
There exists work in the literature that attempts to select covariates and estimate the causal effect in the presence of latent variables. Malinsky and Spirtes [2017) introduced the LV-IDA (Latent Variable IDA) algorithm based on the generalized back-door criterion [Mathuiis and Colombo) 2015). This algorithm initially learns a Partial Ancestral Graph (PAG) using the FCI (Fast Causal Inference) algorithm [Spirtes et al., 2000), then enumerates all Markov equivalent Maximal Ancestral Graphs outcome. Subsequently, Hyttinen et al. [2015] proposed the CE-SAT (Causal Effect Estimation based on SATisfiability solver) method, which avoids enumerating all MAGs in the PAG. Although these algorithms are effective, learning the global causal graph is often unnecessary and wasteful when we are only interested in estimating the causal effects of specific relationships.
(MAGs), and estimates all possible causal effects of treatment
Several contributions have been developed to select covariates for estimating causal effects of interest instance,[Entner without learning global causal structure. For instance, [Entner et al. (2033) designed two inference rules
and proposed the EHS algorithm (named after the authors' names) to determine whether a treatment has causal effect adjustment set for estimating the causal effect of interest, based on the conditional independencies and dependencies among the observed variables. The EHS method has been demonstrated to be both sound and complete for this task. However, it is computationally inefficient, with time complexity of Ott 2²), where t is the number of observed covariates. It requires exhaustive search over all combinations of variables for the inference rules. More recently, by leveraging a special variable, the Cause Or Spouse of the treatment Only (COSO) variable, combined with a pattern mining strategy Agrawal et al. 1994], Cheng et al. 2022) proposed a local algorithm, called CEELS (Causal Effect Estimation by Local Search), select the adjustment set. Although the CEELS method is faster than the EHS method, it may fail to identify an adjustment set during the local search that could be found using a global search. For instance, considering the causal graphs (b) and (c) illustrated in Figure I where (12, V3. V4} and { 212, V3} are the valid adjustment sets w.r.t. the causal relationship X + Y. respectively. The CEELS algorithm fails to select these corresponding adjustment sets, whereas the EHS method is capable of identifying them.
outcome. If a causal effeet is present, these rules help identify an appropriate
It is desirable to develop sound and complete local method to select an adjustment set for causal relationship of interest. Specially, we make the following contributions:
1. We propose a novel, fully local algorithm for selecting covariates in nonparametric causal effect estimation, utilizing testable independence and dependence relationships among the observed variables, and allowing for the presence of latent variables.

---

2. We theoretically demonstrate that the proposed algorithm is both sound and complete, and can identify valid adjustment set for target causal relationship (if such a set exists) under standard assumptions, comparable to global methods. We demonstrate the efficacy of our algorithm through experiments on both synthetic and real- world datasets.
2 Preliminaries
2.1 Definitions and Notations
Graph. A graph G = (V, E) consists of a set of nodes V (Vi..... Vp} and a set of edges E. A graph G is directed mixed if the edges in the graph directed (-), or bi-directed (+>). A causal path (directed path) from V; to Vj is a path composed of directed edges pointing towards Vj, i.e., Vj. A non-causal path from V; to V, is path where at least V; ..... at the mark near V.. e.g. V; + Vi+1 + - Vj-1 colliders n. e.g. V; Vi+1 O ... + Vj v--1
edge has arrowhead Vj. path т from V; to V2 is a collider
path if all the passing nodes an ancestor of V and V, is a descendant of V; if there is a causal path from V to Vj or V, = Vj. A directed mixed graph is called ancestral graph if the graph does not contain any directed almost directed cycles. An ancestral graph is maximal ancestral graph (MAG, denoted by M) if there exists set of nodes that m-separates any two non-adjacent nodes. A MAG DAG if contains only directed edges. A directed edge X + Y in M is visible if there is a node S not adjacent to Y, such that there is an edge between S and X that into X, or there S and X that is into X and every con-ennpoint node on the path is parent of Y. See Figure 8 in Appendix B for an example. Otherwise, X means that there are no latent confounders between X and Y. All directed edges in DAGs are said to be visible. To save space, the detailed graph-related definitions are provided in Appendix B
Vj. V; is called
collider path between
is said be invisible.
visible edge X -
The Markov blanket variable the smallest set conditioned on which all other variables are probabilistically independent of Y [ Graphically, in MAG, the Markov blanket of a node Y. denoted MB (Y) is unique and comprises: 1) the adjacent nodes of Y; and 2) all the non-adjacent nodes that have a collider path in the MAG. Figure 2 specifically illustrates the Markov blanket of the node Y in the MAG. The nodes shaded in green belong to MB MY(Y).
Markov Blanket.
V2
V/3
V/
V/8
V1
V
12
V7
V/3
VO
V13
V14
Vi
V4
Vio
V1
V18
Figure 2:
The illustrative example for MB in MAG, where Y is the target of interest and the green nodes belong to MB(Y)
Notations. We use Adj( V.), Pa( V.), and De( Vi), to denote the set of adjacent, parents and descendants of node V,, respectively. We denote by (X, Y)) an ordered variable (node) pair, where X the treatment and Y the outcome. We denote X II Y "X is statistically independent of Y given Z". Similarly, X J. Y denotes that X is not statistically independent of Y given Z. The main symbols used in this paper summarized in Table i in the Appendix B
2.2 Adjustment Set
The covariate adjustment method is often used to estimate causal effects from observational data Throughout, we focus on the causal effect of a single treatment variable X on the
Pearl
2009
'See Appendix B.2 for more details of Markov blanket.

---

single outcome variable Y. We next introduce a more general graphical language to describe the covariate adjustment criterion, namely the generalized adjustment criterion [Perkovi al.) 2018]. Before providing its definition, we first introduce two important concepts in the graph, as they will be used in the description of this definition.
Definition 1 (Amenability (Van der Zander et al. 2014 Perkovi al. 2018)) ). Let (X, Y) be an ordered node pair in MAG. The MAG is said to be adjustment amenable w.n. (X, Y) if all causal paths from X to Y start with a visible directed edge out of X.
2018 ). Let (X,Y) be ordered node pair in a DAG, or MAG g. Then the forbidden set relative to (X, Y) is defined as Forb(X, Y)
Definition 2 (Forbidden set; Forb(X, Y) [Perkovi al.,
{W's EV W' E De(W). W lies on a causal path from X to Y in g).
Definition 3 (Generalized adjustment criterion Perkovi et al. 2018)). Let Y) be an ordered node pair in DAG or MAG G. A set of nodes Z _ Y satisfies the generalized adjustment criterion relative to (X, Y) in 9 ifG is adjustment amenable relative to (X,Y) Zn Forb(X, Y) = 0, and all definite status non-causal paths from X to Y are blocked by Z. If these conditions hold, then the causal effect of X on Y is idenifiable and is given by
flyl do(x)) { fly xx)
if 0,
(1)
S2 2., (z)dk otherwise.
Note that the generalized adjustment criterion is equivalent to the general- ized back-door criterion of Maathuis and Colombo (2015) when the treat- ment X is a singleton (Perkovi al.] 2018). Thus, condition 3 can be rep- resented by the requirement that all definite status back-door paths from X Y are blocked by Z in G.
V12
V1
V8
V2
V/
VE
V22
V1
X
1/S
V7
Y
V/3
V3
Example 1 (Generalized adjustment criterion). Consider the causal dia- gram shown in Figure. (bb). Accord- ing to Definition] 2 the MAG satisfies the amenability condition relative to XX Y). and Forb(X, (X, Y) {Y}
(a)
(b)
Figure 3: (a) An underlying causal DAG (adapted from Häg
gström (2018), in which U1 and U2 are unobserved variables. (b) The corresponding MAG of the DAG shown in (a).
holds true in the graph. Then, the {V1, 1/23 is a valid adjusiment set since, they can all block non-causal paths from X to Y.
2.3 Problem Definition
We consider Structural Causal Model (SCM) described by Pearl 2009 The set of variables is denoted as V = [X, YYUOU U U, with a joint distribution P(V). Here, O represents the set of observed covariates, and U denotes the set of latent covariates. Therefore, the SCM is associated with a DAG, where each node corresponds to a variable in and each edge represents a function f. Specifically, each variable V. E V is generated V/- = (<(PaaV,)) eg), where Pa(V,) denotes the parents of V. in the DAG, and E; represents errors (or "disturbances") due to omitted factors. In addition, all errors are assumed to be independent of each other. Analogous to Entner al. [2013). Cheng et al. (2022) we assume that Y is not a causal ancestor of X and that O is a set of pretreatment variables w.r.t. (X,Y), ie.. X and Y are not causal ancestors of any variables in O.
Remark 1. /t is noteworthy that existing methods commonly employ the pretreatment assumption [Cheng et al. 2022 Entner et al. 2013 De Luna et al. 2011 Vander Weele and Shpitser 2011 Wi Æt al.) 2022). This assumption is realistic it reflects how samples are obtained in many application areas, such as economics and epidemiology [[iil] 2011 Imbens and Rubin 2015 Wager and Athey
2018 For instance, every variable within the set O is measured prior the implementation of the treatment and before the outcome is observed.
We present the notation for continuous random variables. with the corresponding discrete cases being straightforward.
Note that this assumption can be checked in practice using observational data, as discussed in Section 5

---

Remark 2. Recently, Maasch et al. (2024) attempted to relax the pretreatment assumption and proposed the Local Discovery by Partitioning (LDP) method for identifying an adjustment set under set of sufficient conditions. However, the method may fail to identify valid adjustment sets in certain cases where the EHS criterion succeeds, thereby limiting its completeness. For example, the causal graph (c) of Figure [ the LDP method fails to identify an adjustment set due to the violation of its sufficient condition, even though the pretreatment assumption holds. Furthermore, experimental results demonstrate that our proposed method remains effective benchmark networks, even in scenarios where the pretreatment assumption is violated (see Section 4
Task. Under the standard assumptions of the causal Markov condition and the causal Faithfulness condition. Given an observational dataset D that consists of an ordered variable pair (X, Y), along with set of covariates O we focus on a local learning approach to tackle the challenge of determining whether a specific variable X has a causal effect on another variable Y, allowing for latent variables in the system. If such causal effect is present, aim to locally identify an appropriate adjustment set of covariates that can provide a consistent and unbiased estimator of the true effect. Our method relies on analyzing the testable (conditional) independence and dependence relationships among the observed variables.
3 Local Search Adjustment Sets
In this section, we first present the identification results for the local search adjustment set. Based on these results, we then propose a local search algorithm for identifying the valid adjustment set and show that is both sound and complete. All proofs are deferred to Appendix [D for clarity.
3.1 Local Search Theoretical Results
In this section, we provide the theoretical results for estimating the unbiased causal effect X on Y (if such an effect exists) solely from the observational dataset D. To this end, we need to locally identify the following three possible scenarios when the full causal structure is not known.
S1. X has a causal effect Y, and the causal effect is estimated by adjusting with a valid adjustment set.
S2. X has no causal effect on Y.
S3. It is unknown whether there is a causal effect of X on Y.
It should be emphasized that scenario S3 arises because, under standard assumptions, based on the (testable) independence and dependence relationships among the observed variables, one may not identify unique causal relationship between X and Y. Typically, what we obtain is Markov equivalence class encoding the same conditional independencies (Spirtes et al.] 2000 Zhang 2008b Entner et al. 2013). Thus, some of the causal relationships cannot be uniquely identified
We now address scenario S1. Before that, we define the adjustment set relative to (X, Y) within the Markov blanket of Y in a MAG, denoted as AMB K Y). This definition will help us locally identify a valid adjustment set using testable independencies and dependencies, even in the presence of latent variables.
Definition 4 (Adjustment set in Markov blanket). Let (X, Y) be an ordered node pair in a MAG M, where M is adjustment amenable w.r.l. (X,Y). A set Z is an AMn(X (X, Y) if and only if (1) Z C (BMY) Y) \ (X), (2) Z n For,(X, Y) = 0, and (3) all non-causal paths from X to Y blocked by Z.
The intuition behind the concept of AMB(X, Y) is as follows: in graph without hidden variables, the causal effect of X on Y can be estimated using a subset of Pa( Y) (X) (Pearl 2009). However, in practice, some nodes in Pa( Y) \ (X) may be unobserved. For instance, consider the MAG shown in Figure. (b), where the edge Va ++ Y indicates the presence of latent confounders. Consequently, the observed nodes do not include Pa( Y). However, MB(Y) {X, V2. V3. Va} contains the valid adjustment set (V2, Va, Va). According to Definition 4 we know (V2, V2, V4} is an AMB (X, Y).
Remark 3. Under our problem definition, since O is set of pretreatment variables w.r.t (X,Y). we have Fort(X, Y)= = } and Y not in (Y). Therefore, it is crucial to observe that the three
"See Figure.
10 in Appdenix
C.I for an example.
5

---

conditions in Definition 4 can be simplified to two: (1) Z C MB(Y) \ X, and (2) all non-causal paths from X to Y are blocked by Z.
One may raise the following question: if no subset of MB(Y) \ X qualifies as an adjustment set for (X,Y), does it follow that no adjustment set for (X, Y) exists within the covariate set O? Interestingly, we find that the answer is yes, as formally stated in the following theorem.
Theorem (Existence of AMa(X, Y)). ). Let D be an observational dataset containing an ordered variable puir (X, Y) and a set of covariates O. There exists subset of O is udjustment set w.t.. (X, Y) if and only if there exists a subset of MB Y) \ {X} is an adjustment set w.r.t (X,Y), i.e. AMB [X, Y).
Theorem 1 states that if there exists subset of O that an adjustment set relative to (X, then there exists subset of MB( \ {X} that is an adjustment set. Conversely, if no subset of MY(Y) } is an adjustment set, then no subset of O is an adjustment set relative to (X, Y).
Example 2. Consider the MAG shown in Figure. (b). We can observe MB( () from the MAG, Le. MB Y)= = (X, V1, 22, Va, V4, Vo}. According to Defimition 4 and the structure of the MAG, we can infer that any subset of MB( \ (X) that includes (V1, V2 but excluding {Vz) constitutes an AMB( (XY)).
Based on Theorem 1 and the rules in Entner et al. 2013), we next show that can locally search AMB( (X, Y) by checking certain conditional independence and dependence relationships (Rule R1), as stated in the following theorem. Meanwhile, we can locally find that X has causal effect on Y, ie.
Theorem 2 (R1 for Locally Searching Adjustment Sets). Let D be an observational dataset con- taining an ordered variable pair (X, Y) and a set of covariates O. A subset Z S MY \ {X) an A MBB( (X, Y) if there exists a variable S MB(X) \ (Y) such that (i) S V Y Z, and (ii)
S ILLY Y
Z U (X).
Intuitively speaking, condition (i) indicates that there exist active paths from S to Y given Z. Condition (ii) implies that there are no active paths from S to Y when given Z U {X}. These two rules indicate that all active paths from S to Y given Z must pass through X. Thus, adding X to the conditioning set blocks these active paths. Hence, all non-causal paths from X to Y are blocked by Z; otherwise, condition (ii) will not hold. Then, according to Definition 4 we know is an AMB Y).
V/
1/
V8
V/
V2
V2
V3
X
V
Vg
VI
V1
Example 3. Consider the causal diagram de-
V1
picted in Figure. (b). Assume that an ora- cle performs conditional independence tests on the observational dataset D. Consequently, we can determine the (B and MB Y), i.e.
(a)
(b)
Figure 4: (a) An causal DAG, where U,, =
1, 1,.... are latent variables. (b) The correspond-
MB(X) = [V1, V2 Vs. Vo. V7, Vs. Vg. Y), and MB(Y) Y) = (V1, Vy Vs, Vo, Vs. X). Ac-
ing MAG of the DAG in (a).
cording to Theorem we can infer the existence of a causal effect of X on Y. The set (Vs, Vo. Vs} serves as an AMB( Y), as VT V. Y (Vs, Vo, V/}} and V/ 11 Y (Vs, Vo, X).
Next, we provide the rule R2 that allows us to locally identify X has no causal effect on Y, i.c. S2. Theorem 3 (R2 for Locally Identifying No Causal effect). Let D be an observational dataset containing ordered variable pair (X, Y) and set of covariates O. Then, X has no causal effect on Y if there exists a subset Z C MB(Y) \ (X) and a variable S E MB X) \ (Y) such that at least one of the following conditions holds: (i) X 1L Y Z, or (ii) S J X Z and S 11 Y Z.
According to the faithfulness assumption, condition (i) implies that X and Y are m-separated by a subset of MY) \ (X]. Thus, X has zero effect on Y. Condition (ii) provides a strategy to identify a zero effect even when a latent confounder exists between X and Y. Roughly speaking, S I X Z indicates that there are active paths from S to X given Z. Therefore, if there were

---

directed edge from X to Y. it would create an active path from S to Y by connecting to the previous path, which would contradict condition S IL Y Z.
Example 4. Consider the MAG shown in the Figure] (b). Assuming that the edge from X to Y is removed, then, XLY (V1, V2). Furthermore, suppose V2 is a latent variable. Then, we can infer that there is no causal effect of X to Y by condition (ii), as V6 J. X X and Vo 1 Y [V)).
can infer that there is causal effect of X on Y by condition (i), as
[Vi]
Lastly, we show that if neither R.1 of Theorem nor R2 of Theorem Sattoorem@ppppieee applies, then one cannot identify whether there is causal effect of X on Y, based on conditional independence and dependence relationships among the observational dataset D, i.e., we are in S3.
Theorem Under the standard assumption, neither R1 of Theorem 2 nor R2 of Theorem B then it is impossible determine whether there is a causal effect of X on Y, based on conditional independence and dependence relationships.
Theorem 4 states that there may exist causal structures with and without an edge from X to Y, that induce the same dependencies and independencies among the observational dataset D. Consequently, it is not possible to uniquely infer whether there is a causal effect or not.
3.2 The LSAS Algorithm
In this section, we leverage the above theoretical results and propose the Local Search Adjustment Sets (LSAS) algorithm infer whether there is a causal effect of a variable X on another variable Y, and if so, to estimate the unbiased causal effect. Given an ordered variable pair (X, Y). the algorithm consists of the following two key steps:
(i) Learning the MBs of and Y: This involves using an MB discovery algorithm to identify the Markov Blanket members (MBs) of both X and Y. (ii) Determining Adjustment Sets: For each variable S in MB(X) \ (Y), we check whether S and the subsets Z of MB (Y) \ (X) satisfy rules R1 and R2 based on Theorems 2
The algorithm uses θ to store the estimated causal effect of X on Y. If the output + is null, suggests lack of knowledge to obtain the unbiased causal effect, i.e. S3. If Q = 0, it indicates that there is no causal effect of X on Y. i.e.  Otherwise, O provides the estimated causal effect X on Y, i... S1. The complete procedure is summarized in Algorithm I and the algorithm that used for the MB learning is in Algorithm
Algorithm Local Search Adjustment Sets (LSAS)
Input: Observational dataset D, treatment variable X, outcome variable Y
1: MX),, MB( (Y) Markov Blanket Discovery(X, D,
2: θ +
// Initialize causal effect estimate
3: for each S E MB(X) \ {Y), each Z C MB(Y) (X) do
4: if S and Z satisfy R1 (Theorem 2 then
5: Estimate causal effect 0 of X on Y given Z, θ <- 0.
// S1
6: end if
7: if S and satisfy R2 (Theorem 3 then
8: return è < 0
I/ No causal effect, i.c., S2
9: end if
10: end for
Output: Estimated causal effect +
I| 0, if scenario S3 holds.
We next demonstrate that, in the large sample limit, the LSAS algorithm is both sound and complete. Theorem 5 (The Soundness and Completeness of LSAS Algorithm). Assume Oracle tests for conditional independence tests. Under the assumptions stated in our problem definition (Section 2.3). the LSAS algorithm correctly outputs the causal effect θ whenever rule R1 or R2 applies. However, if neither rule R1 nor R2 applies, the LSAS algorithm can not determine whether there is a causal effect of X on Y, based on the testable conditional independencies and dependencies among the observed variables.
Formally, soundness means that, given an independence oracle and under the assumptions stated in our problem definition (Section 2.3). the inferences made using rule R.1 or R2 are always correct
7

---

whenever these rules apply. On the other hand, completeness implies that if neither rule R1 nor R2 applies, is impossible to determine, based solely on the conditional independencies and dependencies among the observed variables, whether X has a causal effect on Y or not.
Complexity of Algorithm. The LSAS algorithm's complexity comprises two main components:
MB discovery using the TC (Total Conditioning) algorithm (Pellet and Elisseefi 2008b] with time complexity (2n), where n is the size of O plus (X, Y) and
2. local identification using R1 and R2 (Lines 3 ~ 10) with worst-case complexity [[[MM(XX]
1) x 2|MB(Y)1-1]
Thus, the overall worst-case time complexity is ( 1) x 21MB(Y)) nl. A detailed
complexity analysis comparing LSAS with other algorithms is provided in Appendix C,3
4 Experimental Results
To demonstrate the accuracy and efficiency of our proposed method, we applied synthetic data with random graphs, specific structures, and benchmark networks, as well as to the real-world dataset. We here use the existing implementation of the TC discovery algorithm (Pellet and Elisseeff 2008b] to find the MB of target variable. Our source code is available at LSAS
Comparison Methods. We conducted comparative analysis with several established techniques that do not require prior knowledge of the causal graph. Specifically, we evaluated our method against the LV-IDA with RFCI algorithm, which requires learning global graphs (Malinsky and Spirtes) (016); the EHS algorithm, which performs global searches under the pretreatment assumption without requiring graph learning (Entner et al., [213]; the CEELS method, which conducts local searches under the pretreatment assumption [Cheng et al.] 2022]: and the LDP method, which relaxes the
pretreatment assumption for local searches |Masshh et al. 2024
Evaluation Metrics. We evaluate the performance of the algorithms using the following typical metries:
Relative Error (RE): the relative error of the estimated total causal effect (C'E) compared to the true total causal effect (CE), expressed as a percentage, formly,
RE (CE- /CE 100%
n'Tss: the number of (conditional) independence tests implemented by an algorithm.
4.1 Synthetic Data
Following the conventions outlined in Malinsky and Spirtes 2016 Entner et al. [2013), we param- eterized the random graphs, specific structures, and benchmark networks using linear Gaussian causal model. The causal strength of each edge was sampled from Uniform distribution [0.5, 1.5). with additional noise terms drawn from standard Gaussian distribution. Additionally, with linear regression, the causal effect of X on Y is calculated as the partial regression coefficient of X [Malin- sky and Spirtes 2017]. Each experiment was repeated 100 times with randomly generated data, and the results were averaged. The sample sizes were set to 1K, 5K, 10K, and 15K, where K=1000. We based our experiments on the observed variables after removing the set of latent variables for each dataset. The experiments on random graphs are provided in Appendix E.
Specific Structures. We generated synthetic data based on the DAGs shown in Figure 3(a) and Figure 4a). a). The corresponding MAGs, depicted in Figure 3) and b), exclude the latent variables (e.g. 0.). The treatment variable is X and the outcome variable is Y. Note that both DAGs exhibit M-structures adjusting for the collider V33 leads to aver-adjustment and introduces bias.
Benchmark Networks. Algorithms were evaluated on four benchmark Bayesian networks: INSUR- ANCE, MILDEW, WIN95PTS, and ANDES. These networks contain 27 nodes with 52 ares, 35 nodes
'Implementation sources: LV-IDA with RFCI algorithm httttpss//ggttuub.oo///aa//aaaat
using and LDP method /https://github..... com wttp:/uwb...oomaassccssa//e/a/aa
R-package pcalg [Kalisch al. 2012)) ): EHS algorithm publications
'The shape of the sub-graph looks like the capital letter M. See Figure 9 in Appendix B for more details.
8

---

646
0.35
0.20
6:10
6.3
15
Sample Size
Sample Sizo
Sample Size
Sample Size
(a) Performance Comparisons on Figure
(b) Performance Comparisons on Figure
L
0.7
0.480
0.5
glost
9 0.40c
aT&s
0.315
0.2
0.325
0.300
Sample
Sample
Sample Sizee
Sample Size
(c) Performance Comparisons on MILDEW.Net
(d) Performance Comparisons on WIN9SPTS.
+
LSAS
CEELS
LDP
EHS
+
LV-IDA
Figure 5: Performance of five algorithms on Specific Structures, MILDEW and WIN9SPTS.
with 46 ares, 76 nodes with 112 arcs, and 223 nodes with 338 ares, respectively"" The number of latent variables is set to 3, 5, 7, and 10 for the respective networks. In each dataset, we randomly selected latent variables and an ordered variable pair (X, Y). Notably, the selected variable pairs may have descendants, which implies that the pretreatment assumption might not be satisfied.
Results. Due to space constraints, present the results for Specific Structures, MILDEW, and WIN9SPTS in Figure while results for additional benchmark networks are provided in Appendix E.2
Note that some n'Tsst values for LV-IDA are omitted from the plots as they exceed the scale EHS results are not included in the benchmark networks plots due to excessive runtime, From these figures, we observe that our proposed LSAS algorithm outperforms other methods with almost all evaluation metrics in all structures and in all sample sizes. As expected, the nTest of our method significantly lower than that of LV-IDA and EHS, which involve learning the global structure and globally searching for adjustment sets, respectively. Notably, in Figure (b), CEELS and LDP show limited improvement with increasing sample size, which can be attributed to their lack of completeness in identifying valid adjustment sets. Additionally, LSAS outperforms other methods even when the pretreatment assumption may not be satisfied, as shown in Figure 5(c) and (d).
limits.
LDP
4.2 Real-world Dataset
-160
in Test
In this section, we apply our method to a real-world dataset, the Cattaneo2 dataset, which contains birth weights of 4642 sin-
Estimeted ACB
CEELS
-20
-220-
EHS
gleton births in Pennsylvania, USA Catta-
LSAS
neo [2110), Almond et al. 2005). We here investigate the causal effect of a mother's s smoking status during pregnancy (X) on a baby's birth weight (Y). The dataset 8 used comprises 21 covariates, such age, education, and health indicators for the mother and father, among others. Almond et al. (005) have concluded that there a strong negative effect of about 200 250 g of maternal smoking (X) on birth weight
-260
LV-IDA
50k
-280
Methods
Figure The causal effects and the number (condi- tional) independence tests estimated by different meth- ods, presented with 95% confidence intervals on the Cattaneo2 dataset. The two dotted lines represent the estimated interval provided in Almond et al. 2005
AA detailed overview of these networks is provided in Table 3 in Appendix E.2 Additional information available attttps: / //wwu. bulearn. com/ bttpboositrrry////////
'The dataset utilized in this study is available al http::/ttp::w.// www.wwww.sttaa.o...ooet.aae..... tetattt-assss.... wttp:/att/r/////ttaaaaaaaaao
dta

---

(Y) using both subclassifications on the propensity score and regression-adjuster methods. Since there is no ground-true -tunt causal graph and causal effects, we here use the negative effect of about
200 - 250 as the baseline interval given in [Almond et al. 2005). We follow Almond et al. 2005 to
estimate the effect of maternal smoking on birth weight by regression-adjuster (see Section IV.C in
Almond et al. 2005 )
Results. The results of all methods are shown in Figure 6 It should be noted that due to the large number of nTestt for EHS, the results for CEELS and LSAS are not clearly visible in the figure. In fact, the number of conditional independence tests for CEELS, LDP, and LSAS 1284, 266, and 158, respectively. From the figure, we found that the effects estimated by EHS and LSAS fall within the baseline interval, while the effects estimated by other methods do not. Although the effect estimated by the EHS algorithm also falls within the baseline interval, LSAS requires fewer conditional independence tests, which means that LSAS not only effective but also more efficient.
Limitations and Future Work
The preceding section presented how to locally search covariates solely from the observational data. Analogous to the setting studied by Entner et al. [2013] and and[Ch et al. [2022). we assume that Y is not causal ancestor of X and X and Y are not causal ancestors of any variables in O (pretreatment assumption). Regarding the first assumption, in practice, if one has no this prior knowledge, one can first use the existing local search structure algorithm allowing in the presence of latent variables, such as the HMB-by-MMBB algorithm Xie et al. (2024), to identify whether Y is not causal ancestor of X. If is, one can still use our proposed method search for the adjustment set and estimate the causal effect. Regarding the pretreatment assumption, though many application areas can be obtained, such as economics and epidemiology Hill [2011]. Im- bens and Rubin 20155, Wager and Athey (2018), it may not always hold in real-world scenarios. Notably, existing methods- such as EHS, CEELS, and ours-do not directly extend to settings where the pretreatment assumption is violated, they may select invalid adjustment sets that include descendants the treatment, leading to biased estimates. For example, in the Figure 7
we choose = 1/2 and = (V4, Vo), then (S, Z) satisfies condi- tion R1, but Z violates the generalized adjustment criterion since Ve a descendant of X. A potential workaround dants of X first, then apply R1-but this lacks completeness, and may fail to recover adjustment sets even when they exist. To the best of our knowledge, identify descendants a treatment variable locally, especially in the presence of latent variables and without recovering the full graph. Addressing this remains an open and non- an-trrivial challenge; it also deserves to explore methodologies that relax this assumption and address its violations Maasch et al., 2024].
V/
V
identify descen-
X
Y
existing method can soundly and completely
VE
Figure 7: A MAG violating the pretreatment assumption with respect to (X, Y).
Note that some causal effects cannot be identified only based on conditional independencies among observed data. Hence, leveraging background knowledge, such as data generation mechanisms Hoyer et al. 2008 and expert insights Fang and He He| [2020), to aid in identifying causal effects within local structures remains a promising research direction. In addition, obtaining data from multiple environments may also help identify the causal effect (Shi et al. 2021
De Bartolomeis et al. 20055
Conclusion
We have introduced novel local learning algorithm for covariate selection in nonparametric causal effect estimation with latent variables. Compared to existing methods, our approach does not require learning the global graph, more efficient, and remains both sound and complete, even in the presence of latent variables.
10

---

Acknowledgments and Disclosure of Funding
We appreciate the comments from anonymous reviewers, which greatly helped to improve the paper. This research was supported by the National Natural Science Foundation of China (62306019, 62472415). Feng Xie was supported by the Beijing Key Laboratory of Applied Statistics and Digital Regulation, and the BTBU Digital Business Platform Project by BMEC.
References
Rakesh Agrawal, Ramakrishnan Srikant, et al. Fast algorithms for mining association rules. In Proc. 20th int. conf. very large data bases (VLDB), volume 1215, pages 487-499. Santiago, 1994.
Douglas Almond, Kenneth Y Chay, and David S Lee. The costs of low birth weight. The Quarterly Journal of Economics, 120(3):0311-108: 2005.
Peter Bühlmann, Markus Kalisch, and Marloes H Maathuis. Variable selection in high-dimensional linear models: partially faithful distributions and the pe-simple algorithm. Biometrika, 97(2): 261-278, 2010.
Matias D Cattaneo. Efficient semiparametric estimation of multi-valued treatment effects under ignorability. Journal of Econometrics, 155(2):138-154, 2010.
Debo Cheng, Jiuyong Li, Lin Liu, Jiji Zhang, Jixue Liu, and Thue Duy Le, Local search for efficient causal effect estimation. IEEE Transactions Knowledge and Data Engineering, 2022.
Debo Cheng, Jiuyong Li, Lin Liu, Kui Yu, Thue Duy Le, and Jixue Liu. Toward unique and unbiased causal effect estimation from data with hidden variables. IEEE transactions on neural networks and learning systems, 34(9):6108-6128 2023.
Debo Cheng, Jiuyong Li, Lin Liu, Jixue Liu, and Thue Duy Le. Data-driven causal effect estimation based graphical causal modelling: A survey. ACM Computing Surveys, 56(5):1-37, 2024.
Zhixuan Chu, Stephen L Rathbun, and Sheng Li. Graph infomax adversarial learning for treatment effect estimation with networked observational data. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery Data Mining, pages 176-184, 2021.
Piersilvio De Bartolomeis, Julia Kostin, Javier Abad, Yixin Wang, and Fanny Yang. Doubly robust identification of treatment effects from multiple environments. arXiv preprint 2034:2503..4455, 2025.
Xavier De Luna, Ingeborg Waernbaum, and Thomas S Richardson. Covariate selection for the nonparametric estimation of an average treatment effect. Biometrika, 98(4):861-875, 2011.
Doris Entner, Patrik Hoyer, and Peter Spirtes. Data-driven covariate selection for nonparametric estimation of causal effects. In Artificial intelligence and statistics, pages 256-264. PMLR, 2013.
Paul Erd6s and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sei, 5:17-61, 1960.
Zhuangyan Fang and Yangbo He. Ida with background knowledge. In Conference Uncertainty in Artificial Intelligence, pages 270-279. PMLR, 2020.
Jenny Häggström. Data-driven confounder selection via markov and bayesian networks. Biometrics, 74(2):389-33 2018.
Jenny Häggström, Emma Persson, Ingehorg Waernbaum, and Xavier de Luna. Covsel: An package for covariate selection when estimating average causal effects. Journal of Statistical Software, 68: 1-20, 2015.
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.

---

Miguel A Hernán and James M Robins.
Estimating causal effects from epidemiological data. Journal of Epidemiology & Community Health, 60(7):578-586, 2006.
Jennifer Hill. Bayesian nonparametric modeling for causal inference. Journal of Computational and Graphical Statistics, 20(1):217-240, 2011.
Patrik O Hoyer, Shohei Shimizu, Antti J Kerminen, and Markus Palviainen. Estimation of causal effects using linear non-Gaussian causal models with hidden variables. International Journal of Approximate Reasoning, 49(2):362-378, 2008.
Antti Hyttinen, Frederick Eberhardt, and Matti Järvisalo. Do-calculus when the true graph is unknown. In Proceedings of the Thirty-First Conference Uncertainty in Artificial Intelligence, pages 395-404, 2015.
Guido W Imbens and Donald B Rubin. Causal inference for statistics, social, and biomedical sciences: An introduction. Cambridge University Press, 2015.
Markus Kalisch, Martin Mächler, Diego Colombo, Marloes H Maathuis, and Peter Bühlmann. Causal inference using graphical models with the package pealg, Journal of statistical software, 47:1-26, 2012.
Jacqueline Maasch, Weishen Pan, Shantanu Gupta, Volodymyr Kuleshov, Kyra Gan, and Fei Wang. Local discovery by partitioning: Polynomial-time causal discovery around exposure-outcome pairs. In Uncertainty in Artificial Intelligence, pages 2350-2382. PMLR, 2024.
Jacqueline Maasch. Kyra Gan, Violet Chen, Agni Orfanoudaki, Nil-Jana Akpinar, and Fei Wang. Local causal discovery for structural evidence of direct discrimination. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 19349-19335 2025.
Marloes H Maathuis and Diego Colombo. A generalized back-door criterion. The Annals of Statistics, 1360) 2015.
Marloes Maathuis, Markus Kalisch, and Peter Bühlmann. Estimating high-dimensional intervention effects from observational data. The Annals of Statistics, 37(6A)3313333166 2009.
Daniel Malinsky and Peter Spirtes, Estimating causal effects with ancestral graph markov models. In Conference on Probabilistic Graphical Models, pages 299-309. PMLR, 2016.
Daniel Malinsky and Peter Spirtes. Estimating bounds on causal effeets in high-dimennsooal and possibly confounded systems. International Journal of Approximate Reasoning, 88:371-384, 2017.
Judea Pearl. [bayesian analysis in expert systems]: Comment: graphical models, causality and intervention. Statistical Science, 8(3):266-269, 1993.
Judea Pearl. Causality. Cambridge university press, 2009.
Jean-Philippe Pellet and André Elisseeff. Finding latent causes in causal networks: efficient approach based on markov blankets. Advances in Neural Information Processing Systems, 21, 2008a.
dean-Philippe Pellet and André Elisseeff. Using markov blankets for causal structure learning. Journal of Machine Learning Research, 9(7), 2008b.
Emilija Perkovi, Johannes Textor, Markus Kalisch, Marloes H Maathuis, al. Complete graphical characterization and construction adjustment sets in markov equivalence classes ancestral graphs. Journal of Machine Learning Research, 18(220):1-62, 2018.
Emilija Perkovic, Markus Kalisch, and Marloes H Maathuis. Interpreting and using cpdags with background knowledge. In Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, UAI 2017. AUAI Press, 2017.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of Causal Inference. MIT Press, 2017.
12

---

Thomas Richardson. Markov properties for acyclic directed mixed graphs. Scandinavian Journal of Statistics, 30(1):145-17, 2003.
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.
Jakob Runge. Necessary and sufficient graphical conditions for optimal adjustment sets in causal graphical models with hidden variables. Advances in Neural Information Processing Systems, 34: 15762-15773, 2021.
Claudia Shi, Victor Veitch, and David M Blei. Invariant representation learning for treatment effect estimation. In Uncertainty in artificial intelligence, pages 1546-1555. PMLR, 2021.
Ilya Shpitser, Tyler VanderWeele, and James M Robins. On the validity of covariate adjustment for estimating causal effects. In Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, UAI 2010, pages 527-536. AUAT Press, 2010
Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social science computer review, 9(1):62-72, 1991.
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search. MIT press, 2000.
Johannes Textor and Maciej Liskiewiez. Adjustment criteria in causal diagrams: an algorithmic per- spective. In Proceedings the Twenty-Seventl Conference on Uncertainty in Artificial Intelligence, pages 681-688, 2011.
Benito Van der Zander, Maciej Liskiewicz, and Johannes Textor. Constructing separators and adjustment sets ancestral graphs. CI@ UAI, pages 11-24, 2014.
Tyler Vander Weele and Ilya Shpitser. A new criterion for confounder selection. Biometrics, 67(4): 1406-1413, 2011.
Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 113(523): 1228-122222--2222 2018.
Tian-Zuo Wang. Tian Qin, and Zhi-Hua Zhou. Estimating possible causal effects with latent variables via adjustment. In International Conference on Machine Learning, pages 06308-36333 PMLR, 2023.
Janine Witte, Leonard Henckel, Marloes H Maathuis, and Vanessa Didelez. On efficient adjustment in causal graphs. Journal of Machine Learning Research, 21(246):1 2020.
Anpeng Wu, Junkun Yuan, Kun Kuang, Bo Li, Runze Wu, Qiang Zhu, Yueting Zhuang, and Fei Wu. Learning decomposed representations for treatment effect estimation. IEEE Transactions Knowledge and Data Engineering, 35(55)4989-50000 2022.
Feng Xie, Zheng Li, Peng Wu, Yan Zeng, Liu Chunchen, and Zhi Geng. Local causal structure learning the presence of latent variables. In Forty-first International Conference on Machine Learning, 2024.
Xianchao Xie and Zhi Geng. A recursive method for structural learning of directed acyclic graphs. Journal of Machine Learning Research, (14):4599449) 2008
Kui Yu, Lin Liu, Jiuyong Li, and Huanhuan Chen. Mining markov blankets without causal sufficiency. IEEE transactions neural networks and learning systems, 29(12):6333 6347, 2018.
Jiji Zhang. Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 9(7), 2008a.
Jiji Zhang, On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17)1183--188) 2008b.
13

---

Appendix Contents
Related Work
15
B More Details of Notations and Definitions
15
B.1 Graph
15
B.2 Markov Blanket
17
B.3 M-structure
17
Supplement to Section
18
An example for S3
18
C.2
Markov Blanket Discovery Algorithm
18
Complexity of Algorithms
18
D Proofs
19
D.1 Proof of Theeorm
19
Proof of Theorem
20
D.3 Proof of Theeorm
20
D.4 4 Proof of Theorem
21
................................
D.5 Proof of Theorem
22
More Results on Experiments
22
E.1
Experimental Results Random Graphs
22
E.I.I
Experimental Results with Varying Numbers of Nodes
................................
22
1.2
Experimental Results with Varying Average Degree
25
E.2
Experimental Results on Benchmark Networks
25
E.2.1
Overview of Benchmark Networks
25
E.2.2
Experimental Results on the INSURANCE and ANDES Benchmark Networks
25
E.2.3
Runtime Performance Comparison
26
14

---

A Related Work
This paper focuses on covariate selection in causal effect estimation within causal graphical models Pearl (009 Spirtes et al. 2000]. Broadly speaking. the literature covariate selection can be categorized into two main lines of research: methods that assume a known causal graph and methods that do not assume the availability of causal graph. Below, we here provide brief review of these Two lines. For a comprehensive review of data-driven causal effect estimation, see Pearl (2099]
Perkovi al. (0188. Cheng et al. 2024].
Methods with Known Causal Graph. Idcally, when a causal graph is available, one can directly select an adjustment set for causal relationship using the (generalized) back-door criterion Pearl [2009] Maathuis and Colombo| 2013 or the (generalized) adjustment criterion SShiitsrr et al. 2010], Perkovi et al. [2018]. Research in this area often focuses identifying special adjustment sets, such as minimal adjustment sets or 'pptimal' valid adjustment sets that have the smallest asymptotic variance compared to other adjustment sets. For selecting minimal adjustment sets, see De Luna et al.
[2011] Textor and Liskiewiez [011]. For 'optimal' valid adjustment sets, one may refer to Henckel
et al. 2022 for semi-parametric estimators or [Rotnitkky and Smucler (2020) Witte et al. [2020], Runge [2021] for non-parametric estimators. In contrast to the aforementioned methods, this paper
Tocuses the identification of valid adjustment sets under unknown causal graphs.
Methods without Known Causal Graph. A classical framework for inferring causal effect is IDA (Intervention do-calculus when the DAG is Absent) Maathuis et al. (2009]. IDA first learns CPDAG and enumerates all Markov equivalent DAGs in the learned CPDAGs, then estimates all causal effects using the back-door criterion. Other notable developments along this line include combining prior knowledge Perkovic et al. (2017). (ang and He [2020] or employing strategies through local learning De Luna et al. [2 However, these methods often assume causal sufficiency, meaning latent confounders exist in the system, and thus do not adequately account for the influences of latent variables. To address this limitation, a version of IDA suitable for systems with latent variables, known as LV-IDA (Latent Variable IDA), was proposed Malinsky and Spirtes (017). based on the generalized back-door criterion Maathuis and Colombo 20155. Subsequently, more efficient methods were proposed by Hyttinen et al. 20155]. Wang et al. [0023], and Cheng et al. [2023]. Although these algorithms are effective, learning the global causal graph and estimating the causal effects for the entire system can be unnecessary and inefficient when the interest is solely on the causal effects of a single variable on an outcome variable.
To address this issue, Entner et al. (013)] proposed the EHS algorithm under the pretreatment as- sumption, demonstrating that the EHS method is both sound and complete for this task. However, the EHS approach is highly inefficient as it involves an exhaustive search over all possible combinations
of variables for the inference rules. To overcome this inefficiency. Cheng et al. [022] introduced local algorithm called CEELS for selecting the adjustment set. While CEELS is faster than the EHS proposed by Entner et al. [ it may miss some adjustment sets during the local search that could be identified through global search. In this paper, our work focuses on the same setting as EHS and introduces fully local method for selecting the adjustment set. Compared CEELS, our local method is both sound and complete, similar to the global learning method such as the EHS algorithm Entner al. [2013. More recently, to relax the pretreatment assumption, |Maasch et al.. (2024) proposed the Local Discovery by Partitioning (LDP) method, which identifies adjustment sets for exposure-outcome pairs under sufficient conditions. The LDP approach operates under less restrictive assumptions, and requires quadratic number of conditional independence tests w.r.t. variable set size; however, it may fail identify valid adjustment sets in cases where the EHS method is successful. In addition. Maasch et al. [2025] introduced the Local Discovery for Direct Discrimination (LD3) method, which targets the identification of adjustment sets for the weighted controlled direct effect, a specific type of causal effect, A notable limitation of LD3 is its requirement that all parents of the outcome variable be observed, a condition that may not be satisfied in some practical applications.
B
More Details of Notations and Definitions
B.1
Graph
graph G = (V, E) consists of a set of nodes V = (Vi,..., Vp} and a set of edges E. graph G is directed mixed if the edges in the graph are directed (-+), bi-directed (++). The two ends of an edge
15

---

Symbol
Description
w.r.
With respect
(X,Y)
An ordered variable pair, where X is the treatment and Y the outcome A valid adjustment set in MB (B (X) w.r.t. (X, Y)
AMB, Y)
R1
The rules in Theorem
R2
The rules in Theorem
V
The set of all variables, i.e., V V
The treatment or exposure variable
Y
The outcome or response variable
O
The set of observed covariates The set of latent variables A mix graph
9
M
Maximal Ancestral Graph (MAG)
P
A Partial Ancestral Graph (PAG)
The number of the observed covariates, i.e., 1= |0)
"
The number of the observed covariates plus the pair of nodes (X, Y). i.e.
n = [(X, Y)
Ad)(V.)
The set of adjacent nodes Vi The Markov blanket of a node V, in a MAG The set of all descendants of Vi
MB(V.)
De(V.)
PossDe Vi)
The set of all possible descendants of set Z m-separates and Y in G X statistically independent of given Z.
Y
X LL Y
X K Y
X is not statistically independent of Y given Z
Gx
The graph obtained from & by removing all visible directed edges out of X in g
Table 1:
The list of main symbols used in this paper
are called marks. graph G, nodes are said be adjacent in if there is an edge (of any kind) between them. A node V, is parent, child, or spouse of a node V, if there is Vú + Vj. V; + Vj, or V; ++ Vg. path ı in G is sequence of distinct nodes (Vo,.... V.)) such that for 0 S 1 and Vi+1 are adjacent in G. The length of a path equals the number of edges on the path. A causal path (directed path) from V; to Vi is a path composed of directed edges pointing towards Vy.ie. i.e. Vi.... Vj. A possibly causal path (possibly directed path) from Vú to V, is a path where every edge without an arrowhead at the mark near V.. A path from V, V, that called non-causal path from V. to Vj, e.g. Vú <- Vi+1 + + Vy-1 - Vj. A path from V; to V, a collider path if all the passing nodes are colliders on x. e.g. V; V++1 ++ ++ V;-1 +V, V; is called an ancestor, or possible ancestor of V; and V, is descendant, or possible descendant of Vú if there is causal path, or possibly causal path from V, to V, or V; Vj. An almost directed cycle happens when V; is both a spouse and an ancestor of Vj. A directed cycle happens when V₂ is both a child and an ancestor of Vj.
possibly causal is
Definition 5 (m-separation). In a directed mixed graph G, a path a between nodes X and Y is active (m- (n-commecting) relative to (possibly empty) set of nodes Z (X,Y & Z) if 1) every non-collider on π not a member of Z. and 2) every collider on x has descendant Z.
A set Z m-separates X and Y in G. denoted by (X IL Y Z)g. if there is no active path between any nodes in and any nodes in given Z. The criterion m-separation is generalization of Pearl's d-separation criterion in DAG to ancestral graphs.
Definition (Ancestral Graph and Maximal Ancestral Graph). A directed mixed graph is called an ancestral graph if the graph does not contain any directed or almost directed cycles (ancestral). In addition, an ancestral graph is maximal ancestral graph (MAG) for any two non adjacent nodes, there is set of nodes that m-separates them.
Definition 7 (Markov Equivalence). Two MAGs M1, M2 are Markov equivalence they share the same m-separations.
Basically Partial Ancestral Graph represents equivalence class of MAGs.
Definition 8 (Causal Markov condition). The causal markov condition says the m-separation relations among the nodes in a graph imply conditional independence in probability relations among the variables.
16

---

Definition 9 (Causal Faithfulness condition). 1Zhang 2008a| The causal faithfulness condition states that m--comection graph implies conditional dependence in the probability distribution.
Under the above two conditions, conditional independence relations among the observed variables correspond exactly to m-separation in the MAG or PAG G, i.e., (X IL Z|Z) + (X IL Y Y(Z)s.
Definition 10 (Partial Ancestral Graph). Zhang [2008b]] A Partial Ancestral Graph (PAG, denoted by P) represents [M], where tail or arrowhead ">' occurs if the corresponding mark tail or arrowhead in all the Markov equivalent MAGs, and circle 'o' occurs otherwise.
In other words, PAG contains all invariant arrowheads and tails in all the Markov equivalent MAGs. For convenience, use asterisk (+) to denote any possible mark of a PAG (o, -) MAG (>.-).
Definition 11 (Visible Edges). Zhang [2008a] Given MAG M P. directed edge X - Y in M/P is visible if there is node S not adjacent to Y, such that there an edge between S and X that is into X, or there is a collider path between S and X that is into X and every non-endpoint node on the path a parent Y. Otherwise, X Y said to be invisible. Two possible configurations of the visible edge X to Y are provided shown in Figure
A visible edge X Y means that there no latent confounders between X and Y. All directed edges in DAGs and CPDAGs are said to be visible.
S
V3
122
(a)
(b)
Figure 8: Two configurations where the edge X + Y is visible. Nodes S and Y must be nonadjacent in (a) and (b).
Definition 12 (9x Maathuis and Colombo (015)). For MAG M, let Mx denote the graph obtained from M by removing all visible directed edges out of X in M. For a PAG P, let M any MAG consistent with P that has the same number of edges into X as P. and let Px denote the graph obtuined from M by removing all directed edges out of X that are visible in M.
B.2 Markoy Blanket
Definition 13 (Markov Blanket). The Markov blanket of a variable Y, denoted as MB(Y), is the smallest set conditioned which all other variables are probabilistically independent Y formally, VV E V (MB (Y) UV} Y IL V MB(Y).
Graphically, in a DAG, the Markov blanket of node Y includes the set of parents, children, and the parents of the children of Y. The Markov blanket of one node MAG is then defined as shown in Definition 14
Definition 14 (MAG Markov Blanket RRchardson 20033 Pellet and Elisseeft [008a]. Yu al. (018)). In a MAG M, the Markov blanket of a node Y. noted as MB(Y Y), comprises 1) the set of parents, children, and children's 's parents of Y; 2) the district of Y and of the children of Y; and 3) the parents of each node of these districts. Where the district of a node V is the set of all nodes reachable from V using only bidirected edges.
B.3 M-structure
As shown in Figure 9 (a), the DAG is called M-structure (M-bias), where U3 and U2 are latent variables. This structure is very significant because it can lead to collider stratification bias, also
"Some authors use the term "Markov blanket" without the notion of minimality, and use "Markov boundary" to denote the smallest Markov blanket. For clarity, we adopt the convention that the Markov blanket refers to the minimal Markov blanket.
17

---

known as collider bias. The MAG corresponding to this DAG is shown in Fig. 2 (b). In this graph, according to the generalized adjustment criterion, if we are interested the causal effect between X and Y, we should not adjust for the variable M. Adjusting for M would open the path (X ++ [M] ++ Y), which was originally blocked. As result, adjusting for the collider M leads to over-adjustment and introduces bias.
M
M
X
Y
X
Y
a
(b)
Figure 9: The illustrative example for M-structure. (a) A causal DAG, where U1 and U2 are latent variables. (b) The corresponding MAG of the DAG in (a).
X
X
(a)
(b)
Figure 10: Three DAGs that entail the same independencies and dependencies among the observed variables (X, Y, V), where U1, U2, and Ua are latent variables.
C Supplement to Section 3
C.1 An example for S3
Consider the three graphs in Figure 10 These graphs entail the same independencies and dependencies among the observed variables (X, V,V). Consequently, it is impossible to determine, based solely on testable dependencies and independence, whether X has a causal effect on Y and whether V should be included in the adjustment set.
C.2 Markoy Blanket Discovery Algorithm
In this section, outline the procedure of the TC (Total Conditioning) algorithm Pellet and Elisseeff (0088), which we used to discover the Markov blanket.
Definition 15 (Total conditioning Pellet and Elisseeff (2008b]). the context of a faithful causal graph G, we have:
e (X E Markov blanket (Y)) + (X y V (X,Y})
C33 Complexity Algorithms
The complexity of the LSAS algorithm can be divided into two main components: the first component the MB discovery algorithm (Line 1), and the second involves locally identifying causal effects using R, and R2 (Lines 10). Let represent the size of the set O plus the ordered variable
18

---

Algorithm 2 Markov Blanket Discovery Pellet and Elisseeft [0088)
Input: Treatment variable X, outcome variable Y, observed covariates O
I: Initialize MB(X) 0, MB(Y)
2: V V= O OU[X,Y }
3: for each V; O (Y} do
4: if X L V/ V [X. ViJ then
5: Add V, to (X)
// Discover MB
6: end if
7:
end for
8: for each V; O U {X) do
9: if Y M V,
{Y. Vi} then
10: Add V, to MY)
I/ Discover MB(Y)
11: end if
12:
end for
Output: MB(X), MB(Y)
pair (X,Y Y) and seet represents the size of the set. We utilized the TC (Total Conditioning) algorithm Pellet and Elisseeff [2008)] identify the MB. Consequently, the time complexity of finding the MB for two nodes is O 3). In the worst-case scenario, the complexity of the second component is O[[IB X)1 1) x 2 2- Therefore, the overall worst-case time complexity of the LSAS algorithm is ([[MB(X) -) x MB(Y))-1 +n]. Note that the complexity of the EHS algorithm is [ - 2) x 2n,2), which is significantly higher than the complexity of our algorithm. particularly when >> [MB(Y)| in large causal networks. The CEELS algorithm Cheng et al. [2022] employs the PC.select algorithm Bühlmann et al. (2010) to search for Adj and Adj() In the worst-case scenario, the overall complexity of CEELS is O (n x 29), where YI. Adj (V) \ X1). Although in practice, the complexity of CEELS may not differ significantly from that of our proposed algorithm, it is crucial to note that CEELS might miss an adjustment set during the local search that could otherwise be identified through a global search. This issue, illustrated in Figure Tb), is not present in our proposed algorithm. We list the complexity of the algorithms in Table
q = max max((Aj((X)
Table 2: Summary of the algorithms features.
Algorithm
Learning Graph
Time-complexity
Sound Complete
LV-IDA
O n 2
Cheng el al.
2022
Malinsky and Spirtes 2016
EHS
T
2) 2"
CARLS
O (n x 2
LSAS
O((MB(X) 1) x 2 +n]
Note: + denotes sound, + denotes sound and complete, and / means graph learning is required; x means
it is not.
D Proofs
D.1 Proof of Theorem i
Before presenting the proof, we quote Theorem of Xie et al. [2024) since it is used to prove Theorem
M
Lemma 1. [Theorem I of of al. [2024)] Let Y be any node in O, and X be node in MB Y). Then Y and X are m-separated by a subset of O (Y, X} if and only if they are m-separated by subset of MB(Y) (X).
Lemma is an extended version of the result in Xie and Geng 2008
which considers the presence of latent variables. Notably, a fundamental fact is that: given any DAG g over V 0 I-here O denotes the set of observed variables, and L denotes the set of latent variables- there is MAG over O alone such that for any disjoint X, Y, C O, X and are d-separated by Z in G if and only
if they m-separated by Z in the MAG Zhang 2008a
19

---

The intuitive implications of Lemma 1 Mare as follows: given node Y and another node X, where X MY",., if there is a subset of O \ {Y, } that m-separates Y and X. then there must exist a subset of MY( {X) that m-separates Y and X. Conversely, if no subset of MV( \ (X) m-separates Y and X, then no subset of O {Y, X) can m-separate Y and X.
We now proceed to establish the proof of Theorem
|
Proof. According to Definition 3 set Z is valid adjustment w.r.t. (X, Y) in P if it satisfies all the conditions therein. When the treatment X is singleton, the generalized adjustment criterion becomes equivalent to the generalized back-door criterion proposed by Maathuis and Colombo (2015). Under our problem definition, the above conditions can be simplified: set Z S O is a valid adjustment set w.r.t. (X, Y) if P is adjustment amenable relative to (X, Y) (i.e., X and Y are connected by a visible edge, as a visible X + Y) and Z m-separates X and Y in the Px.
Equivalently, this is show that subset of O is an m-separating set w.r.t. (X, Y) in Px and only a subset of MB' ( Y) is an m-separating set w.r.t. (X, Y) in Px, where MB' denotes the MB of Y in Px. Note that MB'(Y) MB(Y), and X may not belong MB'(Y) in Px. We now analyze two cases:
Case 1: Suppose P is adjustment amenable relative to (X, with X E MB in Px, it follows that X & Adj Y). According to Lemma [ and the fact that X E (Y) in Px, Px. and Y are m-separated by subset of O if they m-separated by subset of MB'(Y) [X] in Px. If no subset of MB' (Y) {X} m-separates X and Y, then no subset of O (X,Y) can m-separate X and Y, which implies X E Adj Y) in Px. This contradicts the assumption, thus proving that P is not adjustment amenable relative to (X,Y)
Case 2: Suppose P is adjustment amenable relative to (X, Y), with X & MB in Px. it follows that X & Adj(Y) Y). Thus, and are m-separated by MB((Y),i, i.e. (X Il Y MB'(Y))xx
(X J. Y MBM(B (Y))(()) this contradicts the assumption, showing P is not adjustment amenable relative to (X,Y) XY.Y. Consequently, no subset of O {X} is valid adjustment set w.r.t. (X, Y) in P.
D.2 Proof of Theorem 2
Proof. By S M. Y Z, we can be certain that there exist active paths from S to Y given Z. In addition, S 1L Y Z {X} ensures that all such active paths must go through X, as all paths are blocked by adding X to the conditioning set.
According to the pretreatment assumption, X is not a causal ancestor of any nodes in O, and X is not included in the conditioning set for condition (i). Hence, all active paths from S to Y given Z is collider, then would need to in
must include a direct edge from X to Y. Otherwise, the conditioning set for the active paths from S to Y. Therefore, these two conditions determine that X has a causal effect on Y.
From S J Y Z and S II Y Z U (X). it follows that there exists at least one active path from to X given Z. pointing into X (by the pretreatment assumption). Suppose there exists an active non-causal path between X and Y given Z. By connecting these paths, we obtain an active path from S to Y given Z ZU {X} (by Lemma 3.3.1 of Spprrts et al. [2000], when these paths share more than one node), due to collider at X. That is, S JL Y Z {X]. However, this contradicts IL Y U {X}. Therefore, such active non-causal paths do not exist, and must block all non-causal paths from X to Y, i.e. Z is a AMB (X, Y).
D.3 Proof of Theorem 3
Proof. Under faithfulness, condition (i) infers that there is no edge between X and Y, and X is not a causal ancestor of any nodes in O, implying there is causal path from X to Y unless there is directed edge from X to Y. Hence, there is no causal effect of X on Y.
Condition (ii) implies that X and Y are connected through a latent confounder. The condition S J. X Z ensures that there are active paths from S to X given Z, and since X is not causal ancestor of any nodes in O, these active paths must point to X. Since Y of Z and Y is not causal
20

---

ancestor of any nodes in O or X, these active paths do not pass through Y. If there were directed edge from X to Y, would create active paths from S to Y. contradicting the condition 1 Y Z. Thus, there is no causal effect of X on Y.
D.4 Proof of Theorem
To prove Theorem 4 we need to analyze two scenarios:
Scenario 1: First, we will prove R1 that in Theorem is a necessary condition for identifying
the existence of causal effect of X on Y that can be inferred from DD and a set of variables Z AMB(X, Y) That is, if there exists the causal effect of X on Y that can be inferred through conditional independence tests from D, then a set Z is AMB (X, , and S J. Y Z and S II Y
ZU (X), where S E (X) \ (Y) and Z C. MB(Y) \ (X).
Suppose we are given the causal PAG P that was learned from testable (conditional) independence and dependence relationships among the observed variables. Consider the generalized adjustment criterion in Perkovi et al. (018)) which is sound and complete graphical criterion for covariate adjustment in DAGs, CPDAGs, MAGs, and PAGs. According to the amenability condition, there is a visible edge X + Y in P. According to the definition of visible edges: a directed edge X + Y in P visible if there is node V not adjacent to Y, such that:
1. There is an edge between V and X that is into X, or
2. There is collider path between V and X that is into X and every non-endpoint node on the path is a parent of Y.
Otherwise, X + Y is invisible. Treating such node V as an S, we then consider it in two cases.
Case 1: There exists an S in P that satisfies the above case (1), i... there is an edge between S and X that points to X, and S is not adjacent to Y. In other words, there exists a path that Sx-> X - Y in the G. Consequently, in this case, S V Y Z always holds because X is not included in the conditioning set. According to Theorem there at least set Z C MB(Y) \ (X) is AMB(X, Y), meaning Z block all non-causal paths from X to Y. Adding X to the condition set will block the path S S+- + X - Y, and the non-causal paths from X to are blocked by Z. Therefore, S IL Y
(X} holds.
Case 2: If there exists an S in P that satisfies the above case (2). i.c., there is a collider path between S and X that is into X and every non-endpoint node on the path is a parent of Y, and not adjacent to Y. In this case, these collider nodes all belong to MB(X) and MB Y). Assuming that there is no active path from S X, placing these collider nodes into the condition set will activate this S to X collider path. In addition, these collider nodes must be in the condition set Z for block non-causal paths that pass these nodes. Thus, S J. Z will hold. According to Theorem 1 set Z blocks all non-causal paths from X to Y. The newly activated path between S and and the path after the - Y merger are not blocked by Z. Adding X to the conditional set would then block this path, and thus S TL Y Z U {X} holds.
In summary, these two cases prove that R.1 is necessary condition for identifying the causal effect of X on Y that can be inferred through conditional independence tests.
Scenario 2: Second, will prove that R2 in Theorem B is necessary condition for identifying the absence of the causal effect of X on Y that can be inferred from the testable (conditional) independence and dependence relationships among the observed variables. That is, if the absence of the causal effect of X on Y that can be inferred from D, then X JLL Y Z, or S y X Z and S 1L Y Z, where 5 MX( \ (Y) and Z C MY) \ (X).
Assuming Oracle tests for conditional independence tests. Under our problem definition, the causal structures discovered through testable conditional independence and dependencies between observ- able variables, which can infer X has no causal effect on Y can be divided into the following two
cases:
1. There is no edge between X and Y.
2. The edge between X and Y is X + Y.
We then consider the two cases separately.
21

---

Case 1: If there is no edge between X and Y, then by Lemmal
I if E MY. there must exist a
subset Z of MY) {X] that m-separates and Y, ie.. X I Y
Z. where Z S MB {X).
If X & MY),), then by Definition 13
X
IL Y MV(
Case 2: Since Y and X are not causal ancestors of any nodes in O, and Y is not a causal ancestor
of X, then X is collider. If X is unshielded collider, then there exists node S that is adjacent
to X, but not to Y. Such 5 belong to (M( \ (Y} and MB(Y) (x). Then by Lemma [ S I1 Y Z, where Z _ MB( Y) (X). In addition, S X Z due to S is adjacent to X. If X is a shielded collider, which can be inferred by testable conditional independence and dependencies between observable variables, then there exists discriminating path p for X [Zhang (2008b). This
path includes at least three edges, X is a non-endpoint node on p and is adjacent to Y on p. The path has node S that not adjacent Y, and every node between S and X on p a collider and parent of Y. The colliders between S and X belong to both MB and MY(Y). Including these collider nodes in the set Z ensures that S IL Y Z. where Z consists of nodes from MY that m-separate S and Y. Furthermore, S V X Z holds because Z includes these colliders between X and S.
Proof. Based on the above analysis, if R1 does not apply, then we cannot infer whether there is causal effect of on Y from the independence and dependence relationships among the observed variables. If R2 does not apply, then we cannot infer that there is no causal effect of X on Y from the independence and dependence relationships among the observed variables. Consequently, neither R1 nor R2 applies, then we cannot infer whether there is causal effect of X on Y from the independence and dependence relationships among the observed variables.
D.5 Proof of Theorem 5
Proof. Assuming Oracle tests for conditional independence tests, the MB discovery algorithm finds all and only the MB nodes of target variable.
Following Theorem 2 and Theorem 4 R1 is a sufficient and necessary condition for identifying X has causal effect on Y that can be inferred by testable (conditional) independence and dependence relationships among the observational variables, and there is a set Z is AMB (X, Y). Hence, if there a causal effect of X on Y that can be inferred by observational data, then LSAS can accurately identify the causal effect of X on Y.
Subsequently, relying on Theorem 3 and Theorem R2 is sufficient and necessary condition for identifying the absence of the causal effect of X on Y that can be inferred from observational data. Thus, LSAS correctly identify that there is no causal effect of X on Y that can be inferred from observational data. Ultimately, if neither R1 nor R2 applies, then LSAS cannot infer whether there is causal effect of X Y from the independence and dependence relationships between the observations.
Hence, the soundness and completeness of the LSAS algorithm are proven.
L
E More Results on Experiments
All experiments were conducted on an Intel CPU running at 3.60 GHz, with 64 GB of memory. For all methods, the significance level for the individual conditional independence tests is set to 0.01. The maximum size of the conditioning sets considered is for Specific Structures, for the INSURANCE and MILDEW networks, and 7 for the WIN95PTS and ANDES networks.
E. Experimental Results on Random Graphs
E.1.1 Experimental Results with Varying Numbers of Nodes
We conducted experiments on random graphs generated using the Rénös-Rényi model G(n, d) [Erd6s] and Rényi 1960]. where represents the number of nodes and d denotes the average degree of each node. In our experiments, we set the number of nodes to 20, 30, 40, and 50, respectively, with an average degree of 3 for each node. The last two variables in the causal ordering were designated as the ordered variable pair (X, Y) Additionally, 10% x n nodes with two or more children were randomly selected as unobserved variables in each experiment.
22

---

Results. The experimental results on random graphs are presented in Figure 11 For clarity, some nTest values for LV-IDA are omitted from the plots as they exceed the scale limits. Similarly, the n'Test values for EHS in Figure I1 a) are excluded for the same reason. Additionally, when 20, EHS results are not shown due to excessive runtime. The results demonstrate that our proposed LSAA algorithm achieves superior performance compared to other methods across almost all evaluation metrics, network structures, and sample sizes. This superior performance validates the effectiveness and efficiency of LSAS across networks with varying numbers of nodes.
23

---

2.5 X10*
0.50
0.45
0.40
0.35
nTest
1.5
RE
0.30
0.25
1.0
0.20
0.5
0.15
0.10
0.0
1K
5k
10K
15K
IK
5K
10K
15K
Sample Size
Sample Size
(a) Performance Comparisons G(20
x10
0.40
0.35
0.30
nTest
RE
0.25
0.20
0.15
IK
SK
10K
15K
1K
5K
10K
15K
Sample Size
Sample Size
(b) Performance Comparisons on G(30, 3)
x10
0.40
0.35
0.30
nesst
RE
0.25
0.20
0.15
0.10
1K
5K
10K
15K
1K
5K
10K
15K
Sample Size
Sample
Size
(c) Performance Comparisons on G(40, 3)
1.0 x10*
0.35
0.8
0.30
RE
0.25
nTest
0.6
0.20
0.4
0.15
0.2
0.10
0.0
1K
5K
10K
15K
1K
5K
10K
15K
Sample Size
Sample Size
(d) Performance Comparisons on G(50, 3)
LSAS
CEELS
-
LDP
EHS
LV-IDA
Figure 11: Performance of five algorithms on random graphs

---

E.1.2 Experimental Results with Varying Average Degree
In this section, we conducted additional experiments random graphs with varying average degrees (3,57 7, and 9) under the same settings as Appendix E.I.I nodes, sample size 5K). Due to excessive computational cost, the global method EHS failed to terminate within hours on these denser graphs. To ensure a fair comparison, we here report its performance based on an early stopping threshold of 200 seconds.
Results. As shown Figure 12 LSAS consistently outperforms all bascline methods in terms of RE and nTesss, even as graph density increases. The only exception occurs in the (40,9) 9) network, where the local method LDP achieves lower nTest, while LSAS attains substantially lower RE. Although the performance of all methods declines with increasing density- as expected- LSAS preserves clear advantage, particularly in RE accuracy.
X 110
1.0
n
RE
0.6
4
0.4
2
0.2
5
Average Degrec
Average Degree
LSAS
CEELS
LDP
EHS
Figure 12: Performance of four algorithms on random graphs with varying average degrees
E.2
Experimental Results Benchmark Networks
E.2.1
Overview of Benchmark Networks
3 provides detailed overview of the benchmark network statistics used in this paper. "Max in-degree" refers the maximum number of edges pointing single node, while "Avg degree" denotes the average degree of all nodes.
Table 3: Statistics on the Networks.
Networks
Num.nodes
Number of ares
Max in-degree
Avg degree
INSURANCE
27
52
3.85
MILDEW
35
46
2.63
WIN95PTS
76
112
7
2.95
ANDES
223
338
3.03
E.2.2 Experimental Results on the INSURANCE and ANDES Benchmark Networks
Experimental results on the INSURANCE and ANDES benchmark Bayesian networks are provided in Figure 13
25

---

'110"
1.2
1.0
nTest
3-
RE
0.6
0.2
5K
10K
15K
1K
5K
10K
15K
Sample Size
Sample Size
(a) Performance Comparisons INSURANCE.Ner
x10*
1.50
1.2
1,25
1.0
1.00
nTest
RE
0.75
0.6
0.50
0.4
0.25
SK
10K
15K
0.00
1K
10K
15K
Sample Size
Sample Size
(b) Performance Comparisons ANDES.Net
LSAS
CEELS
- LDP
EHS
LV-IDA
Figure 13: Performance of five algorithms INSURANCE and ANDES
E.2.3 Runtime Performance Comparison
In this section, we additionally report the runtime of the algorithms on the benchmark Bayesian networks, as shown in Figure 14 LSAA consistently outperforms baselines in runtime across most graphs and sample sizes. One exception is the WIN95PTS network at large sample sizes (15K), where the local method LDP faster, however, LSAS achieves substantially higher RE accuracy (see Figures 5 and 13), due to LDP's incompleteness in identifying valid adjustment sets.
26

---

0.5
1.2
0.4
1.0
Time (s)
Time (s)
0.3
0.8
0.6
0.2
0.1
0.2
0.0
0.0
1K
5K
10K
15K
1K
5K
10K
15K
Sample Size
Sample Size
(a)
Performance Comparisons AeD
(b) Performance Comparisons WIN95PTS.Ner
0.8
0.5
0.7
0.4
0.6
Time (s)
0.3
Time
0.4
0.3-
0.2
0.2
0.1
0.1
0.0
0.0
1K
SK
10K
15K
1K
5K
10K
15K
Sample Size
Sample Size
(c) Performance Comparisons on INSURANCE.Ner
(d) Performance Comparisons on MILDEW.Net
LSAS
CEELS
LDP
EHS
LV-IDA
Figure 14: Performance of five algorithms on benchmark networks
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We thoroughly elaborate on our contributions and their relevance to specific application domains in both the abstract and introduction sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We mentioned the limitations in Appendix ??.
Guidelines:
27

---

The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
We provided detailed proofs in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We show our experimental settings well as some of the experimental results in Section and Appendix [ our supplementary materials, we provided the code for our algorithm well simple examples.
Guidelines:
The answer NA means that the paper does not include experiments.
28

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We anonymized and packaged our code and data, and put them in the supple- mentary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips.cc/publcc/eee.
www.ded/eeooeeuummmmccoo ssi ssionyolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
29

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We placed the detailed experimental settings of the experiments in Section and the Appendix of the paper, and the complete details with the code the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Our experiments included relative error (RE) for the evaluation metrics, which expresses the statistical significance of the experiment. We show it in all the figures in the paper. It is obtained by the relative error of the estimated total causal effect (C')) compared the true total causal effect (CE), expressed as a percentage, i.e., RE (CE-CE) - /CE 100%.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Answer: [Yes]
30

---

Justification: All experiments were conducted on an Intel CPU running at 3.60 GHz, with 64 GB of memory.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tte:///neuripspp wwt.rrpp..cpppppc/eeeeceet cttppulli//thiiccsuuiieelll..a.a
Answer: [Yes]
Justification: Our research complies with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our papers basic research.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
31

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The study does not address this issue.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have cited the original paper that produced the code package dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The study does not address this issue.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
32

---

14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicabll, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The study does not address this issue.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The study does not address this issue.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMss if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [No]
Justification: The core theories and methods in this paper are both important and original, without reliance on large language models (LLMs) as essential components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy auttee///aarrrppcccc////oorrersa for what should or should not be described.
33


Reviews:
[{"review_id": "gMIkbm0awP", "reviewer": "Reviewer_urL5", "summary": "This paper addresses the problem of identifying a valid adjustment set from observational data, opting to use a local, rather than global, causal discovery method. Assuming that the observed covariates O satisfy the pretreatment assumption, and additionally that Y is not a causal ancestor of X, the authors propose a local learning algorithm LSAS that identifies a valid adjustment set when possible (being both sound and complete). Their algorithm employs a two-stage procedure: first the Markov Blankets of X and Y are identified, then variables are added to the adjustment set if they satisfy the proposed rules R1 and R2. The authors then apply LSAS to both real and synthetic data, demonstrating that the VAS produced by LSAS attain the lowest relative error and lowest number of tests run when compared to some baselines.", "questions": "Q1. I find it unclear why the pretreatment assumption is maintained and what specific challenges prevent generalization to non-pretreatment settings. Can you provide:\n- A concrete explanation of what algorithmic or theoretical barriers exist in the non-pretreatment case?\n- Specific examples showing how the LSAS approach would fail without this assumption?\n- A clear characterization of what types of problematic variables (beyond m-structures) LSAS aims to exclude?\n\nQ2. I am concerned that using nTests as a proxy for computational complexity may be misleading, since conditioning set sizes could vary significantly between methods. Can you:\n- Report actual wall-clock runtime comparisons alongside nTests for all baselines?\n- Analyze whether LSAS systematically uses smaller/larger conditioning sets than competitors?\n- Provide theoretical or empirical analysis of how conditioning set sizes scale with problem dimensions\n\nQ3. The experimental evaluation primarily focuses on sparse graphs (average degree 3), but limited results on denser graphs (INSURANCE/ANDES) show LSAS performing similarly to baselines. Can you:\n- Conduct systematic experiments on synthetic dense graphs with varying average degrees (5, 7, 10+)?\n- Provide theoretical analysis of how LSAS complexity scales with graph density?\n- If performance degrades on dense graphs, acknowledge this limitation and characterize the settings where LSAS provides advantages?\n\nIf the authors adequately address my concerns, in both the Strengths and Weaknesses and Questions sections, I am open to raising my score.", "limitations": "See significance subsection of Strengths and Weaknesses section.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nQuality - The work seems to me to be technically sound - although I did not inspect the proofs in the appendix closely, the high-level explanations given for the main results (such as Theorem 2 and Theorem 3) seem correct. The strategy of searching for conditions that allow one to conclude that there does exist a VAS, or that a VAS cannot be determined is intuitive. The work is complete in the sense that Theorem 5 (soundness/completeness) shows that LSAS is effective in the maximal number of cases in this setting.\n\nOriginality - It is clear the LSAS represents a step-forward from prior VAS identification methods, as the first one to satisfy both completeness and soundness without necessarily learning the strong graph (albeit under the strong pre-treatment assumption). The authors make this clear in both the second half of the introduction, as well as explicit remarks in Section 2.3. The reasoning behind the approach, i.e., identifying the necessary conditions for identifiability of VAS, then checking for whenever these conditions are satisfied, makes intuitive sense.\n\n\nWeaknesses:\n\nClarity - It is not really clear why the authors want to keep the pretreatment assumption. Its not clear what the challenge of non-pretreatment assumption is setting is, or why their current approach cannot be generalized to the non-pretreatment setting. Even under the pretreatment assumption, it is not clear to the reader what the main difficulty is that their algorithm tries to overcome. For example, without latent confounders the entire covariate set O constitutes a VAS under the pretreatment assumption, as there are no mediators or colliders. However, with pretreatment, one issue that arises are nodes that satisfy an m-structure induce a backdoor path when conditioned on - its not clear if this is really the only variables we want to exclude or if there other types of problematic variables  to exclude. Given these issues, it is difficult to ascertain exactly what insights researchers should derive about when local discovery approach of LSAS is intuitive, what are the major blockers, perhaps in some domains how it can be overcome.\n\n\nSignificance - Although LSAS is a local (rather than global) VAS identification method that does not relax the strong pretreatment assumption, it still retains a worst-case exponential (in dimension) runtime bound common to many global methods. This severely limits its applicability in practice, as it seems likely that LSAS would fall victim to a common practioner complaint, which is that many constraint-based discovery algorithms never converge outside small toy datasets. Although the experimental evaluation of LSAS presented in the main text seems to dispel those concerns, as LSAS seems to outperform other methods by large margins in both RE accuracy and nTests, I have strong concerns about whether these results honestly represent the capabilities of LSAS.\n\nThe authors note that the global VAS identification method EHS has already been shown to be sound and complete, but with time complexity exponential in the number of covariates. This excessive runtime motivates the local search approach of LSAS, and the authors show theoretically that LSAS achieves worst time complexity exponential in the Markov Blanket of $Y$, rather than all covariates, a definitive improvement. However, in their experiments, the authors use the number of tests ran nTests, rather than the absolute runtime of the algorithms (seconds), as an empirical measure of time complexity. This can be misleading, as the number of tests can diverge from absolute runtime, when the size of conditioning sets increases. It is not clear whether LSAS is prone to using smaller conditioning set sizes, therefore it is inappropriate to use nTest as a measure of time complexity, as it could mislead readers when a method runs fewer tests, but actually runs for a much longer time. The authors should take care to report runtime metrics alongside nTests for all baselines, to ensure fair comparison.\n\nFurther, the experimental results in the appendix present some additional worries. While experiments on synthetic data with randomly generated graphs (Figure 10) with increasing dimensionality ($d= 20,30,40,50) show that LSAS outperfoming baselines significantly, all settings use only sparse causal graphs, with a constant average degree 3 for all nodes. Given that the complexity of LSAS depends largely on its first step of Markov Blanket identification, if the MB of Y is small (which would be the case for sparse graphs), LSAS would enjoy a large improvement over baseline methods. However, this leaves the performance of LSAS in denser graphs entirely uncharacterized. This worry is further supported by the experimental results on the real-world INSURANCE and ANDES datasets in Figure 11; INSURANCE and ANDES have higher average degrees than the benchmarks commented on in the main text (3.03,3.85 vs 2.63,2.95), and here LSAS performs nearly identically to CEELS with respect to RE. Given a limited empirical analysis of LSAS's performance on dense graphs, and the few relevant experiments being relegated to the end of the appendix, this obscures the significance of LSAS to the broader community.", "was_revised": true, "final_justification": "The authors thoroughly addressed the concerns I had in my review, including good clarifications about the novelty of their method, as well as adding crucial experiments that validate the significance of their approach's performance and runtime in dense settings. I recommend acceptance.", "rebuttal": "We thank you for the thoughtful feedback and appreciate the positive remarks on the soundness and originality of our work. We address your concerns below.\n\n> **W1&Q1.** the pretreatment assumption...generalization to non-pretreatment settings...fail without this assumption...beyond m-structures LSAS aims to exclude.\n\n**A1.** We would like to clarify the motivation and scope of our work as follows.\n* First, regarding the pretreatment assumption, it realistically reflects how data are collected in many fields such as economics and epidemiology  [Hill, 2011, Imbens and Rubin, 2015, Wager and Athey,2018]. We adopt this assumption to focus on **covariate selection without requiring causal sufficiency**. While the full set $\\mathbf{O}$ forms a VAS in the absence of latent confounders, conditioning on all covariates—especially in high-dimensional settings—can lead to poor performance [Luna et al., 2011; Abadie and Imbens, 2006]. Our goal is to identify the *local sufficient VAS* that enables unbiased and efficient causal effect estimation, **even in the presence of latent variables**.\n\n* Second, even under the pretreatment assumption, **selecting a VAS remains non-trivial** in the presence of latent confounders. Not all pretreatment covariates are harmless to condition on—for example, variables involved in m-structures or other types of collider paths (e.g., $X \\leftrightarrow A \\leftrightarrow B \\leftrightarrow C \\leftrightarrow Y$) may introduce bias by opening backdoor paths. Our method identifies which covariates to include or exclude based on their roles in the local causal structure, which is learned directly from data without requiring global graph recovery.\n\n* Third, existing methods-such as EHS, CEELS, and ours-**do not directly extend** to settings where the **pretreatment assumption is violated**, as they may select invalid adjustment sets that include descendants of the treatment, leading to biased estimates. For example, in the graph:\n$$\nE \\rightarrow F \\rightarrow X \\rightarrow Y, \\quad F \\leftarrow C \\leftrightarrow D \\rightarrow Y, \\quad F \\rightarrow A \\rightarrow B \\rightarrow Y, \\quad X \\rightarrow B\n$$\nif we choose $S = F$ and $\\mathbf{Z} = \\{B, D\\}$, then $(S, \\mathbf{Z})$ satisfies condition $R1$, but $\\mathbf{Z}$ violates the generalized adjustment criterion since $B$ is a descendant of $X$.\nA potential workaround is to identify descendants of $X$ first, then apply $R1$—but this lacks **completeness**, and may fail to recover adjustment sets even when they exist. To the best of our knowledge, **no existing method can soundly and completely identify descendants of a treatment variable locally**, especially in the presence of **latent variables** and without recovering the full graph. Addressing this remains an open and non-trivial challenge.\n\n* Finally, as discussed in Section 1 and Appendix A, existing global adjustment set methods are often inefficient, while existing local approaches suffer from **incompleteness**—even under the pretreatment assumption. This highlights the need for a method that is both **sound and complete**, operates **locally**, and remains valid in the presence of **latent variables**, to reliably select the VAS for specific causal queries.\n\n1. Abadie A, Imbens G W. Large sample properties of matching estimators for average treatment effects. Econometrica, 2006.\n\n\n> **W2&Q2.** ...report runtime metrics alongside nTests... Analyze conditioning sets...theoretical or empirical analysis of how conditioning set sizes scale with problem dimensions? \n\n**A2.** Thank you for the thoughtful comments.\n\nWe agree that nTests alone may not fully reflect runtime performance, especially when conditioning set sizes differ across methods. As suggested, we have now included both wall-clock runtimes and average conditioning set sizes for all benchmark networks. Due to high computational cost, EHS did not finish within 2 hours; we report its runtime and conditioning set sizes using a 200-second early stopping threshold for fair comparison.\n\nOur key observations are as follows:\n1. EHS, as a global search method, exhibits the **highest runtime and largest conditioning sets** across all settings, as expected.\n2. LSAS consistently outperforms baselines in runtime across most graphs and sample sizes. One exception is the WIN95PTS network at large sample sizes (15K), where the local method **LDP** is faster; however, **LSAS achieves substantially higher RE accuracy** (see Figures 4 and 11), due to LDP’s incompleteness in identifying valid adjustment sets.\n3. Among the three local search methods, **LSAS uses slightly larger conditioning sets on average**. This is because LSAS is designed to search for **all valid adjustment sets within $MB(Y)$**, rather than stopping after identifying the first one. **Despite this overhead**, LSAS achieves **consistently lower RE** than CEELS and LDP (see Figures 4 and 11), **highlighting the advantage of its completeness in VAS identification**.\n\nIn summary, these results suggest that LSAS offers a favorable trade-off between runtime and estimation accuracy.\n\n|Network|Size|Algorithm|Time(Seconds)|Conditioning Set Sizes(Mean ± std)\n|-|-|-|-|-|\n|ANDES|1K|LSAS|**0.035**|(2.585, 0.744)|\n|||CEELS|0.337|(1.521, 0.758)|\n|||LDP|0.307|(1.835, 1.654)|\n|||EHS|200|(3.044, 0.096)|\n||5K|LSAS|**0.048**|(2.619, 0.760)|\n|||CEELS|1.466|(1.843, 0.910)|\n|||LDP|0.456|(1.614, 1.313)|\n|||EHS|200|(3.065, 0.119)|\n||10K|LSAS|**0.059**|(2.640, 0.778)|\n|||CEELS|1.752|(2.147, 0.991)|\n|||LDP|0.477|(1.494, 1.277)|\n|||EHS|200|(3.086, 0.130)|\n||15K|LSAS|**0.068**|(2.646, 0.776)|\n|||CEELS|1.634|(2.140, 0.970)|\n|||LDP|0.563|(1.531, 1.234)|\n|||EHS|200|(3.165, 0.157)|\n|INSURANCE|1K|LSAS|**0.007**|(2.131, 0.509)|\n|||CEELS|0.253|(1.583, 0.494)|\n|||LDP|0.028|(2.25, 0.577)|\n|||EHS|200|(6.857, 0.471)|\n||5K|LSAS|**0.015**|(2.269, 0.631)|\n|||CEELS|0.442|(1.999, 0.580)|\n|||LDP|0.031|(2.305, 0.595)|\n|||EHS|200|(6.827, 0.446)|\n||10K|LSAS|**0.020**|(2.325, 0.704)|\n|||CEELS|0.540|(2.229, 0.682)|\n|||LDP|0.033|(2.263, 0.602)|\n|||EHS|200|(6.844, 0.466)|\n||15K|LSAS|**0.023**|(2.326, 0.685)|\n|||CEELS|0.687|(2.420, 0.713)|\n|||LDP|0.037|(2.315, 0.596)|\n|||EHS|200|(6.858, 0.434)|\n|MILDEW|1K|LSAS|**0.006**|(2.175, 0.409)|\n|||CEELS|0.170|(1.309, 0.554)|\n|||LDP|0.026|(1.007, 0.487)|\n|||EHS|200|(5.455, 0.436)|\n||5K|LSAS|**0.009**|(2.157, 0.443)|\n|||CEELS|0.243|(1.691, 0.849)|\n|||LDP|0.026|(0.968, 0.420)|\n|||EHS|200|(5.434, 0.398)|\n||10K|LSAS|**0.010**|(2.160, 0.454)|\n|||CEELS|0.343|(1.999, 0.816)|\n|||LDP|0.036|(1.067, 0.508)|\n|||EHS|200|(5.489, 0.409)|\n||15K|LSAS|**0.011**|(2.158, 0.459)|\n|||CEELS|0.428|(2.010, 0.719)|\n|||LDP|0.031|(1.039, 0.500)|\n|||EHS|200|(5.396, 0.395)|\n|WIN95PTS|1K|LSAS|**0.011**|(2.215, 0.913)|\n|||CEELS|0.058|(1.298, 0.421)|\n|||LDP|0.028|(0.388, 0.161)|\n|||EHS|200|(3.826, 0.086)|\n||5K|LSAS|**0.028**|(2.718, 1.095)|\n|||CEELS|0.213|(1.597, 0.43)|\n|||LDP|0.035|(0.443, 0.254)|\n|||EHS|200|(3.839, 0.161)|\n||10K|LSAS|**0.035**|(2.834, 1.139)|\n|||CEELS|0.332|(1.673, 0.382)|\n|||LDP|0.040|(0.465, 0.30)|\n|||EHS|200|(3.758, 0.162)|\n||15K|LSAS|0.041|(2.933, 1.121)|\n|||CEELS|0.406|(1.702, 0.375)|\n|||LDP|**0.038**|(0.485, 0.332)|\n|||EHS|200|(3.795, 0.163)|\n\n> **W3&Q3.** ...the performance of LSAS in denser graphs...how LSAS complexity scales with graph density?...characterize the settings where LSAS provides advantages?\n\n**A3.** Thank you for the valuable suggestion. We conducted additional experiments on random graphs with average degrees 3, 5, 7, and 9  (40 nodes, 5K samples), as in the main paper. Due to high computational cost, EHS did not finish within 2 hours; we report its runtime and conditioning set sizes using a 200-second early stopping threshold for fair comparison.\n\nOur key observations are as follows:\n\n1. As shown in the table below, **LSAS consistently outperforms all baseline methods in terms of RE and nTests**, even as graph density increases. One exception is the (40, 9) network, where the local method **LDP** has lower nTest. While performance degrades with increasing density—as expected for all methods—LSAS maintains **notable advantages**, particularly in RE accuracy.\n2. The **runtime of LSAS** is slightly higher than that of LDP in some denser settings; however, **its RE is substantially lower**, reflecting its completeness in identifying VAS. This is because we search for all adjustment sets within the Markov Blanket of $Y$. Limiting the number of valid adjustment sets found before stopping would help speed up the running time.\n3. As graph density increases, the **Markov Blanket of each node grows**, leading to increased computational complexity for LSAS. This is reflected in the observed runtimes and conditioning set sizes. Importantly, this trend affects **all methods**, not just LSAS.\n\nIn summary, while LSAS shares the worst-case exponential complexity of constraint-based methods, its **localization strategy yields strong empirical efficiency**, especially on sparse-to-moderate graphs. While performance degrades with increasing density—as with all methods—LSAS consistently delivers better RE accuracy and competitive efficiency across all settings.\n\n|Network|Algorithm|RE|nTest|Time(Seconds)|Conditioning Set Sizes(Mean ± std)|\n|-|-|-|-|-|-|\n|(40, 3)|LSAS|**0.123**|**174.63**|**0.014**|(2.089, 0.557)|\n||CEELS|0.206|1738.93|0.093|(2.327, 0.819)|\n||LDP|0.413|290.61|**0.014**|**(1.337, 0.726)**|\n||EHS|0.362|547675|200|(5.284, 0.324)|\n|(40, 5)|LSAS|**0.275**|**403.74**|0.066|(2.510, 0.693)|\n||CEELS|0.320|2459.63|0.312|(2.538, 0.825)|\n||LDP|0.496|484.94|**0.059**|**(2.067, 0.752)**|\n||EHS|0.627|412350|200|(5.217, 0.239)|\n|(40, 7)|LSAS|**0.376**|**582.62**|0.095|(2.807, 0.548)|\n||CEELS|0.475|2548.74|0.318|(2.663, 0.705)|\n||LDP|0.844|594.81|**0.072**|**(2.123, 0.487)**|\n||EHS|0.827|377688|200|(5.192, 0.185)|\n|(40, 9)|LSAS|**0.407**|791.58|0.130|(3.021, 0.496)|\n||CEELS|0.558|2594.96|0.322|(2.753, 0.527)|\n||LDP|0.962|**618.43**|**0.104**|**(2.230, 0.421)**|\n||EHS|0.812|361556|200|(5.180, 0.130)|"}, {"review_id": "G7NtQWgIxN", "reviewer": "Reviewer_4VeR", "summary": "This paper focuses on causal effect estimation with latent variables. Existing methods often rely on learning the complete global causal structure, which can be computationally inefficient and unnecessary when the interest lies in a single causal effect of $X$ on $Y$. To overcome this limitation, the authors propose a novel and fully local algorithm called Local Search Adjustment Sets (LSAS). This approach leverages testable independence and dependence relationships among observed variables, specifically focusing on the Markov Blankets of $X$ and $Y$, to identify a valid adjustment set. The efficacy of the algorithm is validated through experiments on both synthetic and real-world datasets.", "questions": "1. I still cannot understand why the pretreatment assumption is realistic from the example \"every variable within the set $O$ is measured prior to the implementation of the treatment and before the outcome is observed\". Could you please provide more specific explanations?\n\n2. While the paper mentions experimental effectiveness even when the pretreatment assumption is violated, could the authors elaborate on the theoretical implications or provide a more detailed empirical analysis of LSAS's performance in such scenarios?\n\n3. The first step of LSAS is learning the Markov Blankets. What specific MB discovery algorithms are used? What are the computational complexities and known practical limitations of these MB discovery methods that might impact the overall efficiency of LSAS?", "limitations": "This paper includes a section \"Limitations and Future Work\" in Appendix F, where they clearly state key assumptions such as the pretreatment assumption, discuss scenarios where these assumptions might be violated, and suggest future research directions to relax them, e.g., by leveraging background knowledge or data from multiple environments.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n1. This paper proposes a novel \"fully local\" learning approach for covariate selection in the presence of latent variables (i.e. LSAS), distinguishing itself from methods requiring learning a global causal structure that are computationally inefficient (e.g., EHS) or incomplete (e.g., CEELS, LDP).\n\n2. This paper proves that the proposed LSAS algorithm is both sound and complete under standard assumptions. Theorems 1, 2, 3, and 4, along with their proofs in Appendix D, establish a strong theoretical foundation for the method.\n\n3. This paper is well-structured and clearly explains complex concepts like MAGs, Markov blankets, and the generalized adjustment criterion. The examples provided (Figures 1, 2, 3) aid in understanding the theoretical concepts and the algorithm's intuition.\n\n4. This paper provides extensive experimental results on both synthetic and real-world datasets to demonstrate the effectiveness of the proposed LSAS.\n\n# Weaknesses\n\nI find no major weaknesses. Some minor questions are listed in Questions.", "was_revised": true, "final_justification": "I'm not quite familiar with the scope of this paper and I found no major weaknesses. Therefore, I decide to give a positive score with a relatively low confidence.", "rebuttal": "We sincerely thank you for your positive evaluation and thoughtful questions. We greatly appreciate your recognition of the novelty, theoretical foundation, clarity of presentation, and comprehensive experimental results in our work. We hope that the following responses adequately address your concerns.\n\n\n>**Q1.** I still cannot understand why the pretreatment assumption is realistic from the example \"every variable within the set is measured prior to the implementation of the treatment and before the outcome is observed\". Could you please provide more specific explanations?\n\n**A1.** Thank you for pointing this out. \nAs discussed in Remark 1 of the main paper, the **pretreatment assumption** is realistic as it reflects how data are collected in many fields such as economics and epidemiology [Hill, 2011, Imbens and Rubin, 2015, Wager and Athey,2018], where all covariates in $\\mathbf{O}$ are measured before treatment and outcome. This assumption is particularly common in observational studies [Cheng et al., 2022; Entner et al., 2013; De Luna et al., 2011; Vander Weele and Shpitser, 2011; Wu et al., 2022]. For example:\n* In **medical studies**, covariates such as age, gender, and past medical history are collected before administering a treatment and the outcome;\n* In **economic policy evaluation**, covariates like income, education level, and demographic data are collected before a policy is implemented or the downstream outcome of interest.\n\n\nIn such a setting, covariates are guaranteed not to be affected by the treatment or outcome, justifying the assumption. We will clarify this with concrete examples in Section 2.3 of the revised manuscript.\n\n**Reference**\n\n* Jennifer L Hill. Bayesian nonparametric modeling for causal inference. Journal of Computational and Graphical Statistics, 20(1):217–240, 2011.\n* Guido W Imbens and Donald B Rubin. Causal inference for statistics, social, and biomedical sciences: An introduction. Cambridge University Press, 2015.\n* Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 113(523):1228–1242, 2018.\n* Debo Cheng, Jiuyong Li, Lin Liu, Jiji Zhang, Jixue Liu, and Thuc Duy Le. Local search for efficient causal effect estimation. IEEE Transactions on Knowledge and Data Engineering, 2022.\n* Doris Entner, Patrik Hoyer, and Peter Spirtes. Data-driven covariate selection for nonparametric estimation of causal effects. In Artificial intelligence and statistics, pages 256–264. PMLR, 2013.\n* Xavier De Luna, Ingeborg Waernbaum, and Thomas S Richardson. Covariate selection for the nonparametric estimation of an average treatment effect. Biometrika, 98(4):861–875, 2011.\n* Tyler J Vander Weele and Ilya Shpitser. A new criterion for confounder selection. Biometrics, 67(4): 1406–1413, 2011.\n* Anpeng Wu, Junkun Yuan, Kun Kuang, Bo Li, Runze Wu, Qiang Zhu, Yueting Zhuang, and Fei Wu. Learning decomposed representations for treatment effect estimation. IEEE Transactions on Knowledge and Data Engineering, 35(5):4989–5001, 2022.\n\n\n\n>**Q2.** While the paper mentions experimental effectiveness even when the pretreatment assumption is violated, could the authors elaborate on the theoretical implications or provide a more detailed empirical analysis of LSAS's performance in such scenarios?\n\n**A2.** Thank you for the insightful question. When the **pretreatment assumption is violated**, some observed covariates may be **descendants of the treatment**, potentially lying on causal paths from $X$ to $Y$. In such cases, even if $(S, \\mathbf{Z})$ satisfies condition $R1$, adjusting for variables in $\\mathbf{Z}$ may introduce post-treatment bias and invalidate the causal estimate. For example, in the graph:\n$$\nE \\rightarrow F \\rightarrow X \\rightarrow Y, \\quad F \\leftarrow C \\leftrightarrow D \\rightarrow Y, \\quad F \\rightarrow A \\rightarrow B \\rightarrow Y, \\quad X \\rightarrow B\n$$\nif we choose $S = F$ and $\\mathbf{Z} = \\{B, D\\}$, then $(S, \\mathbf{Z})$ satisfies condition $R1$, but $\\mathbf{Z}$ violates the generalized adjustment criterion since $B$ is a descendant of $X$.\nA potential workaround is to identify descendants of $X$ first, then apply $R1$—but this lacks **completeness**, and may fail to recover adjustment sets even when they exist. To the best of our knowledge, **no existing method can soundly and completely identify descendants of a treatment variable locally**, especially in the presence of **latent variables** and without recovering the full graph. Addressing this remains an open and non-trivial challenge.\n\n\n\n\n \n>**Q3.** The first step of LSAS is learning the Markov Blankets. What specific MB discovery algorithms are used? What are the **computational complexities** and known **practical limitations** of these MB discovery methods that might impact the overall efficiency of LSAS?\n\n**A3.** Thank you for your question. In our implementation, we use the **TC (Total Conditioning)** algorithm [Pellet and Elisseeff, 2008b] to discover the MB; see Appendix C.2 for further details. The **computational complexity** of this method is $O(n)$, where $n$ is the number of observed variables, making it efficient for use as a first-stage procedure in LSAS.\n\nIt is well known that the **accuracy of MB discovery directly affects the overall performance** of MB-based causal inference methods. In our setting, if relevant variables are **omitted** from the estimated MB, LSAS may fail to identify a VAS. To **mitigate this risk**, one can adopt a conservative approach: **relaxing the inclusion criteria** to ensure that as many true MB variables as possible are retained [Wang et al., 2014; Liu et al., 2020]. This increases the chance of including extraneous variables beyond the true MB, which in turn may **increase the computational burden** in the subsequent search phase. Nonetheless, when runtime is not a primary concern, this trade-off improves robustness and helps preserve the completeness of the adjustment set search.\n\n**Reference**\n\n* Jean-Philippe Pellet and André Elisseeff. Using Markov blankets for causal structure learning. Journal of Machine Learning Research, 9(7), 2008b.\n* Wang, C., Zhou, Y., Zhao, Q., & Geng, Z. Discovering and orienting the edges connected to a target variable in a DAG via a sequential local learning approach. Computational Statistics & Data Analysis, 2014.\n* Liu, Y., Fang, Z., He, Y., Geng, Z., & Liu, C. Local causal network learning for finding pairs of total and direct effects. Journal of Machine Learning Research, 2020."}, {"review_id": "QD69jV24tn", "reviewer": "Reviewer_qAne", "summary": "* The paper seems to be placed the intersection of causal discovery and causal inference -- though more focused on causal identification. In particular, the authors focus on inferring if X has a potential causal effect on Y. To this goal, they learn an appropriate set of covariates to adjust to identify and estimate causal effect; what makes this work unique is that they do it in presence of latent features. \n* Relies on analyzing the testable conditional independence and dependence relationships", "questions": "* Can authors provide sensitivity analysis to violation of correct specification of MAG/DAG?\n* In Algorithm 1, what if R1 or R2 is satisfied for multiple different combinations of S and Z? What if they result in different estimates?\n* Typically, MB(Y) is always much larger than MB(X). In that case, their algorithm thats exponentially more time to run. How are authors claiming scalability?", "limitations": "The authors discuss limitations in appendix but I think it is worth moving to maintext. Further, it will be useful to discuss the reliance on assumptions and what happens when they are violated.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n* The paper targets a relevant theoretical question -- given the causal dependencies, can we identify the causal effect and if yes, what are the set of covariates one needs to adjust for.\n* The paper is very well written, with nice remarks, discussion and mix of formal and informal language\n\nWeakness:\n* The paper is notationally heavy. I am not sure there is much the authors can do.\n* The work realies on stronger assumption about ordering of covariates and knowledge of MAG/DAG. I am not sure if it is realistic.", "was_revised": true, "final_justification": "The response by authors is adequate to improve my assessment of the paper", "rebuttal": "We sincerely thank you for the thoughtful comments and for recognizing that our paper is well written, with clear remarks and discussion. Below, we address each point raised:\n\n>**W1.** The paper is notationally heavy. I am not sure there is much the authors can do.\n\n**A1.** We acknowledge that the notation may be dense at times. This is largely due to the technical nature of the identification problem under latent confounding. To assist readers, we have included a notation table (Table 1) in **Appendix B**. In the final version (thanks to the availability of an additional page), we will move this table to the **main text** to improve accessibility and readability.\n\n\n\n>**W2.** The work realies on stronger assumption about ordering of covariates and knowledge of MAG/DAG. I am not sure if it is realistic.\n\n**A2.** We would like to clarify that our method **does not assume access to the true MAG or DAG**. Instead, it is a **local, data-driven** approach that operates without relying on global structural knowledge. All experimental results are based solely on observed data, without any access to the underlying MAG or DAG.\n\nRegarding the **pretreatment assumption**, it realistically reflects how data are collected in many fields such as economics and epidemiology  [Hill, 2011, Imbens and Rubin, 2015, Wager and Athey,2018], where all covariates in $\\mathbf{O}$ are measured before treatment and outcome. This assumption is particularly common in observational studies [Cheng et al., 2022, Entner et al., 2013, De Luna et al., 2011, Vander Weele and Shpitser, 2011, Wu et al., 2022]. For example:\n* In **medical studies**, covariates such as age, gender, and past medical history are collected before administering a treatment and the outcome;\n* In **economic policy evaluation**, covariates like income, education level, and demographic data are collected before a policy is implemented or the downstream outcome of interest.\n\nWe adopt this assumption to focus on **covariate selection without requiring causal sufficiency**, which is a strong and often unrealistic assumption in latent variable settings.\n\nMoreover, LSAS outperforms other methods even when the pretreatment assumption may not be satisfied, as demonstrated by results on benchmark graphs (Figures 4 and 11).\n\n\n>**Q3.** Can authors provide sensitivity analysis to violation of correct specification of MAG/DAG?\n\n**A3.** We would like to clarify that our method **does not assume access to the true MAG or DAG**. LSAS is a **fully local and data-driven procedure** that identifies valid adjustment sets without requiring knowledge of the global causal structure. As such, there is **no dependency on the correct specification of the full MAG/DAG**, and hence no direct source of sensitivity to its misspecification.\n\n>**Q4.** In Algorithm 1, what if R1 or R2 is satisfied for multiple different combinations of S and Z? What if they result in different estimates?\n\n**A4.** Thank you for this valuable question. \n\nWhen multiple $(S, \\mathbf{Z})$ pairs satisfy **condition $\\mathcal{R}1$**, we follow the strategy of [Cheng et al., 2022] and **average the resulting causal effect estimates** across these valid adjustment sets. This approach helps improve stability and reduce variance.\n\nIn contrast, if any $(S, \\mathbf{Z})$ pair satisfies **condition $\\mathcal{R}2$**, this implies that **there is no causal effect from $X$ to $Y$**. In such cases, LSAS returns a null estimate, consistent with the interpretation of R2 as a test for the absence of a causal effect.\n\n**Reference**\n* Debo Cheng, Jiuyong Li, Lin Liu, Jiji Zhang, Jixue Liu, and Thuc Duy Le. Local search for efficient causal effect estimation. IEEE Transactions on Knowledge and Data Engineering, 2022.\n\n\n>**Q5.** Typically, MB(Y) is always much larger than MB(X). In that case, their algorithm thats exponentially more time to run. **How are authors claiming scalability?**\n\n**A5.** We would like to clarify that **MB(Y) is not necessarily much larger than MB(X)** in general. The relative sizes of Markov Blankets depend heavily on the structure of the underlying graph.  \n\nTo **demonstrate the empirical scalability** of LSAS, we conducted additional experiments on denser random graphs, reporting both runtime and average conditioning set sizes. Specifically, we conducted additional experiments on **random graphs with increasing average degrees (3, 5, 7, and 9)**, under the same settings as in the main paper (40 nodes, sample size = 5K). These denser graphs result in larger MBs, which present a greater computational challenge.\n\nAs shown in the table below, we find the follwing observations:\n\n1. **LSAS consistently outperforms all baseline methods in terms of RE and nTests**, even as graph density increases. One exception is the (40, 9) network, where the local method **LDP** has lower nTest. While performance degrades with increasing density—as expected for all methods—LSAS maintains **notable advantages**, particularly in RE accuracy.\n\n2. The **runtime of LSAS** is slightly higher than that of LDP in some denser settings; however, **its RE is substantially lower**, reflecting its completeness in identifying VAS. This is because we search for all adjustment sets within the Markov Blanket of $Y$. Limiting the number of valid adjustment sets found before stopping would help speed up the running time.\n\n3. As graph density increases, the **Markov Blanket of each node grows**, leading to increased computational complexity for LSAS. This is reflected in the observed runtimes and conditioning set sizes. Importantly, this trend affects **all methods**, not just LSAS.\n\nIn summary, while LSAS shares the worst-case exponential complexity inherent to constraint-based methods, its **localization strategy yields strong empirical efficiency**, especially on sparse-to-moderate graphs. We acknowledge that performance degrades with graph density, but LSAS continues to **offer better RE accuracy and competitive efficiency** compared to all baselines, even in denser settings.\n\n\n|Network|Algorithm|RE|nTest|Time (Seconds)|Conditioning Set Sizes (Mean ± std)|\n|-|-|-|-|-|-|\n|(40, 3)|LSAS|**0.123**|**174.63**|**0.014**|(2.089, 0.557)|\n||CEELS|0.206|1738.93|0.093|(2.327, 0.819)|\n||LDP|0.413|290.61|**0.014**|**(1.337, 0.726)**|\n||EHS|0.362|547675|200|(5.284, 0.324)|\n|(40, 5)|LSAS|**0.275**|**403.74**|0.066|(2.510, 0.693)|\n||CEELS|0.320|2459.63|0.312|(2.538, 0.825)|\n||LDP|0.496|484.94|**0.059**|**(2.067, 0.752)**|\n||EHS|0.627|412350|200|(5.217, 0.239)|\n|(40, 7)|LSAS|**0.376**|**582.62**|0.095|(2.807, 0.548)|\n||CEELS|0.475|2548.74|0.318|(2.663, 0.705)|\n||LDP|0.844|594.81|**0.072**|**(2.123, 0.487)**|\n||EHS|0.827|377688|200|(5.192, 0.185)|\n|(40, 9)|LSAS|**0.407**|791.58|0.130|(3.021, 0.496)|\n||CEELS|0.558|2594.96|0.322|(2.753, 0.527)|\n||LDP|0.962|**618.43**|**0.104**|**(2.230, 0.421)**|\n||EHS|0.812|361556|200|(5.180, 0.130)|\n\n\n\n> **Q6-Limitations.** The authors discuss limitations in appendix but I think it is worth moving to maintext. Further, it will be useful to discuss the reliance on assumptions and what happens when they are violated.\n\n**A6.** Thank you for the suggestion. Due to page constraints, we originally placed the discussion of limitations in the appendix, but we will move it to the main text in the final version as recommended.\n\nRegarding assumptions, our method relies on the pretreatment assumption, which, as discussed in Response A2, is widely adopted and considered realistic in many observational studies across fields such as medicine and economics.\n\nWhen the **pretreatment assumption is violated**, some observed covariates may be **descendants of the treatment**, potentially lying on causal paths from $X$ to $Y$. In such cases, even if $(S, \\mathbf{Z})$ satisfies condition $R1$, adjusting for variables in $\\mathbf{Z}$ may introduce post-treatment bias and invalidate the causal estimate. For example, in the graph:\n$$\nE \\rightarrow F \\rightarrow X \\rightarrow Y, \\quad F \\leftarrow C \\leftrightarrow D \\rightarrow Y, \\quad F \\rightarrow A \\rightarrow B \\rightarrow Y, \\quad X \\rightarrow B\n$$\nif we choose $S = F$ and $\\mathbf{Z} = \\{B, D\\}$, then $(S, \\mathbf{Z})$ satisfies condition $R1$, but $\\mathbf{Z}$ violates the generalized adjustment criterion since $B$ is a descendant of $X$.\n\nWe will incorporate this discussion into the revised version to more clearly acknowledge the method’s assumptions and limitations."}, {"review_id": "8ev2UQGTDZ", "reviewer": "Reviewer_swW2", "summary": "Causal effect estimation is a fundamental problem in many domains, such as epidemiology, economics, and political science. One popular method for causal effect estimation is known as backdoor adjustment. The challenge with backdoor adjustment, however, is that it may not always be clear which variables constitute a valid backdoor adjustment set. The authors propose a new method known as LSAS that improves upon known methods in the literature, most notably in time complexity. Through synthetic simulations and an analysis on a real-world dataset, the authors demonstrate the effectiveness and improvements of their method.", "questions": "In your definition for a maximal ancestral graph, is that the same as an acyclic directed mixed graph (ADMG)? Further, what is an “almost directed cycle” in lines 90-91?\n\nTheorems 2,3, and 4 are nearly exactly the same as the inference rules and Theorems 2 and 3 presented in Entner et al. (2013). Is there a specific reason why the authors did not cite Entner et al. (2013) when presenting these three theorems? It seems to me that the proofs of Theorems 2, 3, and 4 should follow in a fairly straightforward manner from the proofs in Entner et al. (2013) once Theorem 1 is established. I believe that it is important to cite Entner et al. (2013) when presenting these three theorems as they are, at the very least, heavily inspired by the work of EHS.\n\nIs faithfulness implicit in the theorems of this paper? Line 257 is the first mention of the faithfulness assumption in the main paper. If the authors are assuming faithfulness throughout, then they should define faithfulness and state the assumption somewhere in Section 2.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nA major strength of this paper is its clarity of writing. The literature review is comprehensive, and it is easy to follow the authors’ claims and their examples. All major claims are supported by theoretical proofs and simulation studies.\n\nThe key insight of this paper is that, for the purposes of learning a valid covariate adjustment set, one only needs to look at the Markov blankets of $X$ and $Y$ because, as the authors prove, there is a valid adjustment set amongst all of the observed variables if and only if there is a valid adjustment set amongst the Markov blankets of $X$ and $Y$. When the number of potential confounders is large, reducing the search space to just the Markov blankets can result in huge improvements in efficiency. This insight is, to the best of my knowledge, not previously known in the literature. The rest of the paper then uses this insight and known methods, most notably an efficient algorithm for learning the Markov blanket of a variable, to develop their method and algorithm.\n\nThe simulation studies clearly show how the authors’ method improves upon current methods with respect to run-time without sacrificing accuracy with respect to estimation of the causal effect.\n\nWeaknesses\n\nI have no major complaints regarding this paper.", "was_revised": true, "final_justification": "This is a well-written paper with non-trivial theoretical results that improve upon methods in the current literature. The authors show that it is possible to significantly reduce the search space of the problem without sacrificing soundness and completeness. My concerns regarding the paper only had to do with the writing style, and they have all been addressed. Therefore, I recommend acceptance of this paper.", "rebuttal": "We thank you for your thoughtful and constructive feedback. We are especially grateful for the recognition of the clarity of our writing, the novelty of our theoretical contribution, and the empirical improvements in efficiency without sacrificing accuracy. We hope the following responses properly address your concerns.\n\n\n>**Q1.** In your definition for a maximal ancestral graph, is that the same as an acyclic directed mixed graph (ADMG)? Further, what is an “almost directed cycle” in lines 90-91?\n\n**A1.** Thank you for the question.\n\nTo clarify: **maximal ancestral graphs (MAGs)** are a **subclass** of **acyclic directed mixed graphs (ADMGs)**.  MAGs are used to represent the structure of data-generating processes in the presence of latent variables [Richardson, 2003; Spirtes et al., 1997] (See the first sentence of the third paragraph of [Richardson, 2003]), and they satisfy additional constraints that ADMGs do not. For example, in MAGs, **every missing edge corresponds to a conditional independence relation**, making them maximal in that sense. \n\nRegarding the term ``almost directed cycle'', it refers to a scenario where a node $X$ is both a spouse and an ancestor of another node $Y$. Specifically, $X$ is considered a spouse of $Y$ if there exists a bi-directed edge $X \\leftrightarrow Y$, and an ancestor if there is a directed path from $X$ to $Y$. In an ancestral graph, the presence of a bi-directed edge $X \\leftrightarrow Y$ implies that neither $X$ is an ancestor of $Y$ nor $Y$ of $X$. Therefore, allowing both a bi-directed edge and a directed path between two nodes would violate the ancestral property and create an \"almost directed cycle,\" which is inconsistent with the semantics of MAGs [Richardson et al., 2002].\n\n**Reference**\n* Richardson T. Markov properties for acyclic directed mixed graphs. Scandinavian Journal of Statistics, 2003.\n* Spirtes P, Richardson T, Meek C. The dimensionality of mixed ancestral graphs. Technical Report CMU-PHIL-83, 1997.\n* Richardson T, Spirtes P. Ancestral graph Markov models. The Annals of Statistics, 2002.\n\n\n>**Q2.** Theorems 2,3, and 4 are nearly exactly the same as the inference rules and Theorems 2 and 3 presented in Entner et al. (2013). Is there a specific reason why the authors did not cite Entner et al. (2013) when presenting these three theorems? It seems to me that the proofs of Theorems 2, 3, and 4 should follow in a fairly straightforward manner from the proofs in Entner et al. (2013) once Theorem 1 is established. I believe that it is important to cite Entner et al. (2013) when presenting these three theorems as they are, at the very least, heavily inspired by the work of EHS.\n\n**A2.** Thank you for pointing this out. \n\nTheorems 2, 3, and 4 are indeed heavily inspired by the inderence rules proposed in Entner et al. (2013). In the revised version, we have added appropriate citations to Entner et al. (2013) when presenting these theorems. \n\nWe would also like to highlight a key distinction: **our formulation is fully local**, relying only on the **Markov Blankets of the treatment and outcome variables**, rather than performing an exhaustive search over all variable combinations, as in the original inference rules. Importantly, our local approach is not merely a heuristic: it is **theoretically guaranteed to be both sound and complete** under the stated assumptions. This **localization** significantly improves computational efficiency and enhances the method's applicability in **high-dimensional settings**. We believe this constitutes a **novel and meaningful extension** beyond the original work.\n\n\n\n\n>**Q3.** Is faithfulness implicit in the theorems of this paper? Line 257 is the first mention of the faithfulness assumption in the main paper. If the authors are assuming faithfulness throughout, then they should define faithfulness and state the assumption somewhere in Section 2.\n\n**A3.** Yes, the **faithfulness assumption** is implicit in our theoretical results. Following your suggestion, we have moved its **definition and formal statement** from Appendix B to **Section 2** of the main text for greater clarity.\n\nWe would also like to emphasize that **faithfulness is a standard assumption in causal discovery methods**. In fact, many classical algorithms—such as **PC**, **FCI**, and **RFCI**—**fundamentally rely on faithfulness** [Spirtes and Zhang, 2016]. Moreover, **existing covariate selection methods**, including **EHS** [Entner et al., 2013], **CEELS** [Cheng et al., 2022], and **LDP** [Maasch et al., 2024], also make use of this assumption to ensure the correctness of their independence-based inference procedures.\n\n\nFurther, earlier work shows that **reducing unnecessary conditional independence tests** can help mitigate the impact of **statistically weak violations of faithfulness** [Isozaki T, 2014]. While **faithfulness remains a theoretical requirement**, our method’s **localized design naturally reduces the number and complexity of conditional independence tests**, which empirically improves robustness to potential violations of this assumption.\n\n**Reference**\n* Peter Spirtes and Kun Zhang. Causal discovery and inference: concepts and recent methodological advances. In Applied informatics, 2016.\n* Isozaki T. A robust causal discovery algorithm against faithfulness violation. Information and Media Technologies, 2014."}]

Author rebuttal:

Meta-review: The paper proposes a local sound and complete algorithm for identifying valid adjustment sets under latent confounding. Its main strengths are rigorous theory, clear exposition, and improved efficiency over global methods together with extensive experiments. Reviewers’ concerns on assumptions, runtime, and dense graphs were addressed with additional results and clarifications in the discussion phase so that eventually all reviewers recommend acceptance and I fully agree with their assessment.
Decision: Accept (poster)