Local Identifying Causal Relations in the Presence of Latent Variables
Authors: Zheng Li
Zeyu Liu
Feng Xie
Hao Zhang
Chunchen LIU
Zhi Geng
Venue: ICML 2025 spotlightposter (2025)
Keywords: Causal Discovery
Latent Variable
Local Method
Causal Relationship
Markov Blanket
Primary area: general_machine_learning->causality
TL;DR: We propose an efficient and theoretically complete local method for identifying causal relationships between two variables from observational data, even in the presence of latent variables.

Abstract: We tackle the problem of identifying whether a variable is the cause of a specified target using observational data. State-of-the-art causal learning algorithms that handle latent variables typically rely on identifying the global causal structure, often represented as a partial ancestral graph (PAG), to infer causal relationships. Although effective, these approaches are often redundant and computationally expensive when the focus is limited to a specific causal relationship. In this work, we introduce novel local characterizations that are necessary and sufficient for various types of causal relationships between two variables, enabling us to bypass the need for global structure learning. Leveraging these local insights, we develop efficient and fully localized algorithms that accurately identify causal relationships from observational data. We theoretically demonstrate the soundness and completeness of our approach. Extensive experiments on benchmark networks and real-world datasets further validate the effectiveness and efficiency of our method.

Local Identifying Causal Relations in the Presence of Latent Variables
Zheng Li Zeyu Liu
Feng Xie
Hao Zhang?
Chunchen Liu 3 Zhi Geng'
Abstract
Hyposia O₂
Hypossa in
Hypossia
Duct flow
Duct flow
We tackle the problem of identifying whether a variable is the cause of a specified target using ob- servational data. State-of oft-----a-hh--- causal learning algorithms that handle latent variables typically rely on identifying the global causal structure, of- ten represented as a partial ancestral graph (PAG), to infer causal relationships. Although effective. these approaches are often redundant and com- putationally expensive when the focus limited to specific causal relationship. In this work, we introduce novel local characterizations that are necessary and sufficient for various types of causal relationships between two variables, en- abling us to bypass the need for global structure learning. Leveraging these local insights, we de- velop efficient and fully localized algorithms that accurately identify causal relationships from ob- servational data. We theoretically demonstrate the soundness and completeness of our approach. Extensive experiments benchmark networks and two real-world datasets further validate the effectiveness and efficiency of our method.
Cardiac Mixing
Hyporiaa distribution
Hyposiia distribution
Hyposia distribution)
Lower body O2
Lower
Lower body
(a) Underlying graph
(b) DAG
(c) MAG
Figure 1. (a) The underlying graph from (Spiegelhalter et al., 1993) (CHILD network), where Cardiac Mixing is latent variable and the other variables are observed.
(b) A DAG over the observed variables (a). (c) A MAG characterizing the causal relations over the observed variables in (a).
opment of effective treatment plans. Such insights enable healthcare professionals to efficiently identify root causes and deliver targeted interventions.
The causal graphical model is one of the most widely used models for graphically representing causal relations among observed variables, which consists of vertices de- noting variables and edges denoting causal relations (Pearl, 2009; Spirtes et al., 2000). Directed acyelic graphs (DAGs) are widely used to represent causal relationships among observed variables under the assumption of causal suffi- ciency (Pearl, 2009; Spirtes et al., 2000), i.e., the absence of unobserved latent variables between observed variables. However, when latent variables are present, DAGs may fail to represent the causal relationships among observed vari- aRichaRino & Spirtes, 2002). As shown in Figure I (b), the DAG incorrectly depicts Hypoxia in O2 as a cause of Hypoxia distribution, but there no directed path from Hypoxia in O₂ to Hypoxia distribution in the underlying graph. Therefore, directly employing methods that do not account for the influence of latent variables (when the sys- tem contains latent variables), such as those in Fang et al. (2022); Zuo et al. (2022); Zheng et al. (2024), may result in incorrect inferences about the causal relationships among the observed variables.
1. Introduction
Identifying causal relationships, known as causal discovery, plays a crucial role in various fields, including computer sei- ence (Jonas et al., 2017; Pearl, 2018; Schölkopf, 2022), sociology (Spirtes al., 2000), epidemiology (Hernán & Robins, 2010), and neuroscience (Smith et al., 2011; Sanchez-Romert et al., 2019). A key challenge in causal discovery is determining whether one variable causes an- other (Pearl, 2009). For instance, in medical diagnosis, understanding the causal relationships between symptoms and discases is crucial for accurate diagnoses and the devel-
'Equal contribution 'Department of Applied Statistics, Beijing Technology and Business University, Beijing, China *SIAT. Chi- nese Academy of Sciences, Shenzhen, China 'Ling Lt.Ltd, Alibaba Group, Hangzhou, China. Correspondence to: Feng Xie <fengxie btb..cdu.cn...
Maximal Ancestral Graphs (MAGs), whose main advantage is that, without explicitly including latent variables, they represent conditional independence and causal relationships among observed variables (Richardson & Spirtes, 2002; Zhang, 2008). In a MAG, a vertex X is an ancestor (cause) of a vertex Y and Y is a descendant (effect) of X there is directed path from X Y (Zhang, 2006). As shown in
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Local Identifying Causal Relations in the Presence of Latent Variables
Figure (c), it correctly represents Hypoxia in O₂ does not cause Hypoxia distribution, and vice versa. However, from
for a target pair of variables as state-of-the-art global
learning approaches.
the observational data, without additional distributional as- sumptions or background knowledge, we generally learn a Markov equivalence class (MEC) of MAGs that encodes the invariant features of the underlying MAG, which can be
We conduct extensive experiments on benchmark net- work structures and real-world datasets, showcasing the effectiveness and efficiency of our method.
represented by partial ancestral graph (PAG) (Spirtes & Richardson, 1996; Zhang & Spirtes, 2005; Ali et al., 2005; Zhao et al., 2005) The undirected edges (or marks) in PAG imply that some causal relations among variables can- not be read from the graph directly. Hence, given Markov equivalent class of MAGS, there are three possible types of causal relationships 2:
2. Related Works
This paper focuses on identifying causal relationships be- tween variable pairs in the presence of latent variables. Ex- isting methods generally fall into two categories: global structure- learning and local structure- learning.
Global Structure-Bassdd Learning. This category begins by using FCI (Spirtes et al., 2000) and its variants (Colombo et al., 2012; Claassen al., 2013; Claassen & Heskes, 201 I; Ogarrio et al., 2016; Raghu et al., 2018; Tsirlis et al., 2018;
1. A variable X an invariant ancestor of variable Y if and only if there a directed path from X to Y in every equivalent MAG.
2. A variable X is an invariant non-ancestor of variable
Akbari et al., 2021; Rohekar et al., 2021; Bhattacharya et al., 2021; Claassen & Bucur, 2022) to learn the global causal PAG. Then, it infers the causal relationships based on criteria proposed by Zhang (2006) and Roumpelaki et al. (2016); Mooij & Claassen (2020) or through causal effect estimation methods, such as LV-IDA (Malinsky & Spirtes, 2016) and its extensions (Maathuis al., 2009; Nandy et al., 2017 7; Liu et al., 2020a; Fang & He, 2020; Pensar et al., 2020; Wang et al., 2023a). However, these methods rely on global causal graph, which can be computationally expensive and restrictive (Guo & Perkovic, 2021; Fang et al., 2022).
Y if and only if there is no directed path from X to Y in any equivalent MAG.
3. A variable X is a possible ancestor of variable Y if X is neither an invariant ancestor nor an invariant non- ancestor of Y.
A direct approach to identifying the causal relationship be- tween pair of variables (X, Y) is to first use methods like FCI (Spirtes et al., 2000) or RFCI (Colombo et al., 2012) to learn a PAG from observational data, and then enumerate all MAGs within this class to determine whether X is an invariant ancestor or non-am non-ancestor of Y across all equivalent MAGs. However, this approach becomes computationally inefficient when the number of MAGS in the MEC is large (Malinsky& & Spirtes, 2016). In addition, these approaches are often redundant and computationally expensive when the focus is limited to a specific causal relationship. In this paper, we address the challenge of locally identifying the causal relationship between a pair of variables with- out requiring the learning of a full PAG, the enumeration of MAGs, or the assumption of causal sufficiency. Our primary contributions are summarized as follows:
Local Structure- Learning. This category primarily focuses on identifying relationships between a target vari- able and its adjacent variables. Well-known algorithms in this line include (Yin et al., 2008; Zhou et al., 2010; Wang et al., 2014; Gao & Ji, 2015; Liu et al., 2020b; Yang et al., 2021; Liang et al., 2023). Recently, Fang et al. (2022) and its variants (Zheng et al., 2024) introduced local approaches for identifying causal relationships among arbitrary pairs of variables within a system. However, these methods require the assumption of causal sufficiency. More recently, Xie et al. (2024) proposed method for identifying local causal structures in the presence of latent variables. Nevertheless, their approach focuses on relationships between a target variable and its adjacent variables, without generalizing to arbitrary pairs of variables.
We provide both sufficient and necessary local character- izations for the invariant ancestor, invariant non-ancestor, and possible ancestor relationships, relying solely on lo- cal structure rather than the entire graph, even in the presence of latent variables.
To our knowledge, no method locally identifies the causal relationship between an arbitrary pair of variables, without assuming causal sufficiency and learning the full causal PAG.
We propose a novel algorithm, LocICR, that locally iden- tifies the causal relationship between pair of variables. We provide theoretical proof of its completeness, demon- strating that it can identify the same causal relationships
3. Preliminaries
Under the assumption of causal sufficiency, the Markov equiv- alence class (MEC) of the underlying DAG is typically represented by a completed partially directed acyelic graph (CPDAG). "One may refer to Appendix A.3 for further clarification of these causal relationships.
3.1. Terminology
A univariate variable (or vertex) is denoted by an upper- case letter (e.g., V), while sets of variables (or vertices) are
2

---

Local Identifying Causal Relations in the Presence of Latent Variables
denoted by bold uppercase letters (e.g.. V).
I
B
Graphs. A graph G = (V, E) consists of set of vertices V = (Vi...., } and set of edges E. The two ends of an edge are called marks. A graph is directed mixed if the edges in the graph are directed (-+), or bi-directed (t+). A directed mixed graph is ancestral if it doesn't t contain directed or almost directed cycle. An ancestral graph is maximal ancestral graph (MAG, denoted by M) if for any two non-adjacent vertices, there exists set of vertices that m-separates them. Two MAGS are Markov equivalent if they share the same m-separations. A class of Markov equivalent MAGS, denoted as [M], can be represented as a Partially Ancestral Graph (PAG, denoted by P), where a tail '-" or arrowhead '>' occurs if the corresponding mark tail or arrowhead in all the Markov equivalent MAGs, and circle 'o' occurs otherwise. For convenience, we use asterisk (*) to denote any possible mark of PAG (o, >, -) or a MAG (>. For two vertices Vi and V, in P, V, is a possibly parent/possibly child/neighhor of Vú if there is Vio+ V,/V; <VV a-o V3 in P. A path is a collider path if every non-endpoint vertex on it is a collider along the path. A directed path from Vú V, is a path composed of directed edges pointing towards Vj. A partially directed path from Vú to V, is a path where every edge without arrowhead at the mark near Vi. A path from V; to Vj that is not possibly causal is called non-causal path from V; to Vg. The detailed graph-related definitions are provided in Appendix A.I.
L
A
F
H
D
M
E
K
C
Figure 2. The illustrative example for MB, where X is the target of interest and the blue vertices belong MB(X.
Ne(V, P) and Cos P) as the neighbor and possible child sets of V, in a PAG P: [P] as the Markov equiva- lence class represented by PAG P. We use the notation X IL YIZ for "X is statistically independent of Y given Z", and X J. Y|Z for the negation of the same sentence. We use the (X, Y') to denote the target pair of variables, identifying whether X is an invariant non-ancestor/invaiiat ancestor/possible ancestor of Y.
3.2. Problem Definition
Our work is in the framework of causal graphical models (G, 9a), where G represents the causal structure and Og refers to the associated parameters with G (Pearl, 2009). The causal structure G = (V, E) is a directed acyelic graph (DAG) where V represents a set of vertices and E represents set of edges. The parameters OG specify a functional rela- tionship for each Vi E V, in the form V/2 = fi (Paa(V)) uz), where u, represents independent errors due to omitted fac- tors, and all error terms u5 are assumed to be mutually independent. The variable set V consists of the observed variables and the latent variables L.
Markov Blanket. The Markov blanker(MB) of a variable X is the smallest conditioned on which all other variables are statistically independent of X 3. Graphically, assuming faithfulness, in DAG, this is the set of parents, children, and children's parents of vertex X. In a MAG, the Markova blanket of a vertex X, noted as (M, consists of the set of parents, children, children's 's parents of X, as well as the district of X and of the children of X. and the parents of each vertex of these districts, where the district of vertex V is the set of all vertices reachable from V using only bidirected edges. Figure 2 specifically illustrates the Markov blanket of vertex X in a MAG. The vertices shaded in blue belong to MX).
Task. Under the standard assumptions of the causal Markov condition and the causal Faithfulness condition, our objec- tive is to characterize the local graphical features of different types of causal relationships between pair of variables X and Y, where X, Y E O. Subsequently, we aim to develop a fully local algorithm to determine the causal relationship between X and Y. Note that we do not assume causal sufficiency, allowing for latent variables between observed variables in the system.
Let P represent the MEC of M, the MB remains invariant across M and P, i.e., MB(X, .M- (X P). For sim- plicity, MB denotes MB P) when unambiguous, and MX+ denotes (MB X UX.
Notations. 4 We denote: Pa(V, 9). 9), Ad)(V,, as the parent, descendant, and adjacent vertex sets of V in G;
4. Local Characterization of Causal Relations
*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
4.1. Foundations of Local Characterization
In this section, we build on the well-established local Markov property for DAGs to introduce the local Markov property for MAGs, following the ordered local Markov
the Markov blanket refers to the minimal Markov blanket.
"The main symbols are summarized in Table I in Appendix A.
3

---

Local Identifying Causal Relations in the Presence of Latent Variables
H
D
E
D
E
(a) Underlying Graph
(b) MAG
(c) PAG
Figure 3. (a) An underlying causal graph, where L1, Lgg, and Ls are latent variables, dashed directed edge denotes directed path. (b) The MAG characterizes the causal relations over the observed variables in (a). (c) The inferred PAG from observed variables.
property described in Richardson & Spirtes (2002). Specifi- cally, the local Markov property states that a target variable independent of its non-descendants, given a particular ser of variables.
for DAGs, i.c. each variable in the DAG is independent of its non non-descendants given its parents.
Example 1. Consider the MAG M shown in Figure 3 (b), with J as the target vertex of interest. Each ver- tex V E {A, B, C, F, G) is connected to J by an arrow- collider path from J to V. Additionally, the descendant set of J in M is M) = {D, augmented parent set of J is (J, = {A, G} and Pre(J.M) {A, G, H). Therefore, the local Markov property is J 1L [C, H) (A,
To define this particular set, we first introduce particular type of collider path, as outlined in Definition 1.
F, B)B As a result, the
Definition (Arrow-Collider Path). In PAG or a MAG, a path x = (Vo....,Va, ... is called an arrow-collider path from Vo to Vn every non-endpoint vertex is a collider on n, and the edge between Vo and V1 points into Vo. i.e.
Vo <> Vy....*VV If ===1, simplifies to Vo V+V.
4.2. Local Characterization
Building on Definition 1, we define the particular sei graph- ically in Definition 2.
As outlined in the introduction, causal relationships between pairs of variables, inferred from non-experimental obser- vational data can be classified into three types: invariant non-ancestors, invariant ancestors, and possible ancestors. In this section, we present local characterizations of these causal relationships, which rely on the induced subgraph of the PAG over (X).
Definition 2 (Augmented Parent Set). Let G be a PAG or a MAG. The augmented parent set of a vertex X, denoted as Pa" (XX (K,G) G), is defined as follows: for any vertex V E O, V E (X" g) if and only if there exists an arrow-collider path क from X V such that:
(1) in MAG, X is non-ancestor of every vertex on n, including V.
We begin by presenting the local characterization of invari- and ron-ancestor relations, as shown in Theorem below.
(2) in a PAG, X is an invariant non-ancestor of all vertices on n, including V.
Theorem 1. Let P be the PAG over O. For any pair of vertices (X,Y Y) ) in P, X is an invariant non-ancestor of Y if and only if X Y Pa PX
In general, the augmented parent set of a target vertex in- cludes not only its direct parents but also vertices connected via arrow-collider paths. See Example 1 for illustrations of Definitions and 2.
Intuitively, according to the local Markov property, given PAG (the MEC of MAGs), Pa" (X, P) blocks all non- causal paths from X to Y in P. If X is not an invariant non-ancestor of Y (i.e., there exists a directed path from X to Y in a MAG M E [P]), this implies X M Y Pa PX"(,P)) P). Conversely, if X JL Y Pa" Pa"(X, K P). then there is no directed path from X to Y in any M E [P], and X is an invariant non-ancestor of Y.
Below, we introduce the local Markov property for MAGs using the concept of the augmented parent set. Notably, this result is theoretically equivalent to the ordered local Markov property for MAGs proposed by Richardson & Spirtes (2002). For details, see Theorem 7 in Appendix B. Definition 3 (Local Markov Property for MAGs). Let M be the MAG over O, and let Pre(X,M) denote the pre- treatment vertices of X in M, i.e., the vertices for which X is not ancestor. The local Markov property for the MAG states that for every variable X E O, the following property holds:
Example 2. Consider the PAG shown in Figure 3 (c), with (J, C') as the target pair of interest. Each vertex in (A, B, C, F, G} is connected to J by an arrow-collider path from to it. By Definition 2, we have Pa" (J,P) = GA. Furthermore, there no active path between J and C given {A, G). which implies J IL C. {A, G}. Consequently, J is invariant non-ancestor of C.
X LL Pre(X.M) Pa" Pap (X. Pa PX.(X.M) (1)
If no latent variables exist in the system, the local Markov property for MAGS reduces to the local Markov property
We now turn to the concept of the invariant ancestor relation. To clarify its local characterization, we define the local
4

---

Local Identifying Causal Relations in the Presence of Latent Variables
features of the invariant ancestor relation, categorized into two types: explicit invariant ancestor and implicit invariant ancestor, detailed in Definitions 4 and 5, respectively.
to Y in P. If X is not an explicit invariant ancestor of Y (i.e., no directed path from X to Y exists in P), then X IL Y Pa" (X, P) U (X, Conversely, if X yL Y Pa"(X, U (X, P), directed path from X to Y exists in P. making X an explicit invariant ancestor of Y.
Definition 4 (Explicit Invariant Ancestor). Given PAG P. vertex X is explicit invariant ancestor of another vertex Y if and only if a common directed path exists from X to Y in every MAG within [P].
Example 3. Consider the PAG shown in Figure 3 (c), with (J.B) be the target pair of interest. From Example 2, we know Pa (J,P) = {A, G}. Additionally, (J, P) = 0 as no vertex is connected to J by a circle-collider path. Furthermore, there is an active path {J, D.E.E.... E...., between J and B. conditioned on {A, G), implying J Y B | (). Thus, J is an invariant explicit ancestor of B.
Definition 5 (Implicit Invariant Ancestor). Given PAG P. vertex X is an implicit invariant ancestor of another vertex Y if and only if X is an invariant ancestor of Y, but there is no directed path from X to Y common to every MAG within [P].
......,,,, F. B)
Remark 1. We define X as an invariant ancestor of Y if there exists a directed path from X to Y in every MAG in [P]. If these directed paths are identical across all MAGs in (P), the invariant ancestor relation is explicit; otherwise, it is implicit. Furthermore, if a common directed path from X to Y exists in every MAG in [P], then directed path from X to Y must also exist in P (Zhang, 2006).
We now characterize implicit invariant ancestor relations locally based on Definition 8, as detailed in Theorem 3.
Definition 8. Let P be a PAG and let WI represent the set of maximal cliques of the induced subgraph of P over PossCh ()) U Ne(X, P)). The set of augmented undirected neighbor of a vertex X relative to a maximal clique M E M., denoted as Ne* (XM, P). For any vertex V E O, V E Ne (XM: P) if and only if there exists a circle-collide path π = (X = Vo, Vi,..., Vn = V) from X to V such that for every 2 S i S n, X is an invariant non-ancestor of V2 and (2) V1 E M.
To graphically characterize these two types of invariant ancestor relations, we define a specific type of collider path in Definition 6, analogous to the arrow-collider path, and a particular set in Definition 7, similar to the augmented parent set.
Theorem 3. Let P be the PAG over O. For any pair of vertices (X, Y) in P, X is an implicit invariant ancestor of Y if and only if
Definition (Circle-Collider Path). In a PAG, a path π (Vo....,Viy Va) is called a circle-collier path from Vu to Vn if every non-endpoint vertex is a collider on n, and the edge between Vo and V1 is undirected relative to Vo, i.e., Vn Vi ........ .V.,. If = 1, π simplifies to Vo o-+ V1.
(1) X IL PX U (x, but (2) X Y (X) (XM, P) every maximal clique M E M.
Definition 7. Let P be PAG, the augmented undirected neighbor set of a vertex X, denoted as Ne (X, P). is de- fined as follows: For any vertex V E O, V E Ne" if and only if there exists a circle-collider path π = (X- = Vo, Vi...., V,V V) from X to V such for every < i S n, X is an invariant non-ancestor of V,
The first condition implies that there is no common directed path from X to Y in any MAG within [P]. Intuitively, similar to the role of Ne P) in P, Ne (XM, P) can block all partially directed paths (excluding directed paths) from X to Y that pass through M in P. If X K. Y Pa Pat(X, P) U Ne (XM, PP) for a maximal clique M e M, this indicates the presence of partially directed paths from X to Y in P, given Pa (X, P) U Ne (XM, P). That is, in some MAGS within [P] where directed path from X to Y exists, given Pa (X, P) U Ne (XM. P). Moreover, if X J. Y Pa (X P) U Ne- Nee(MM. P) holds for every M E M. then all MAGs within [P] contain a directed path from X to Y. meaning X is an implicit invariant ancestor of Y. Conversely, if X IL Y (X, P) U Ne (XM: P) for a maximal elique M E MI, this implies that some MAGs within [P] lack a directed path from X to Y.
Remark 2. Note that in a PAG, Ne(X, P) consists of ver- tices connected to X by edges of the form o-o, Ne NX includes not only Ne(X, P) but also vertices connected by circle-collider paths.
Next, we present the local characterization of explicit invari- anf ancestor relations, as stated in Theorem 2.
Theorem 2. Let P be the PAG over O. For any pair of vertices (X, Y) in P, X is an explicit invariant ancestorof Y and only if X J Y | Pa (X,P) U Ne (X.P).
Intuitively, given a PAG, Ne Ne, P) blocks all partially directed paths(except directed paths) from X to Y in P, while Pa (X, P) blocks all non-causal paths that from X
Example 4. Consider the PAG shown in Figure 3 (c) with (G, D) as the target puir. PossCh(G, U Ne(G, = J3, and the set M = ([H), {J}). Each vertex in J,J.B,B,CC F) is connected to G by a circle-collider
'When 1, the condition becomes redundant and may be omitted.
'The definition of maximal clique is given in Appendix A.I.
5

---

Local Identifying Causal Relations in the Presence of Latent Variables
path from G to it, with G as an invariant non-uncestor of
variable V₁, denoted Lv; derived from the observed data of MB+ and is relevant for constructing P PMB (X)- Let Waitlist store variables that are potentially relevant for learning (X)+ and Donelist store variables removed from Waitlist and P store true causal information, the
(A,C). Thus, Ne. (G, P) (H For M (H).
we have Ne (GM, P) {... Similarly, for M = {J},
we have Ne (G.. P)- = [J. Observing that G IL
D A,J. G j. D (H) and G J D A).
Consequently, G is an invariant implicit ancestor of D.
basic idea is as follows:
Based on Theorems 2 and 3, we provide a sound and com- plete local characterization of invariant ancestor relations.
Learning P (x)
Corollary 1. Let P be the PAG over O, and let M denote the set of maximal cliques of the induced subgraph of P over PossCh(X (XP) PP) U Ne(X,P), For any pair of vertices (X,Y) in P. X is an invariant ancestor Y Y if and only if
1. Given target variable X, observed data O. Initialize Waitlist = (X). Donelist 0. and P = 0.
2. During each step, perform sequential iterations, focusing on the first variable V/2 in Waitlist. First, learn MB(),,, followed by the local structure Cv; over the observed data of MB* (V₂). Next, extract true edges and direction information from Lv; (by Proposition I and Proposition 2) and update P. Orient P using standard orientation criteria. Then, update Waitlist and Donlist.
(1) X L Y (X,(X,P) P) U (X, or eorevey M E M
(2) X Y
(XUN) (XM: P) every
By Theorem 1 and Corollary 1, we can identify all stable causal relationships (invariant non-ance con-ancestor and invariant ancestor). Naturally, the remaining ones (possible ancestors) are subject to change, as stated below.
3. The process ends when the stopping criteria (as defined in Proposition 3) are met.
Theorem 4. Let P be the PAG over O. For any pair of vertices (X,Y) in P, X is an possible ancestor Y if and only if neither Theorem nor Corollary applies.
We outline the technical details of the algorithm below.
Proposition 1. (Theorem I in Xie et al. (2024)) Let X be any vertex in O, and V be vertex in (X Then X and V are m-separated by subset of O \ {X, V) if and only if they are m-separated by subset of MB(X) \ (V).
5. The Local Identifying Algorithm
This section discusses how to locally learn the Conditional Sets involved in the aforementioned theoretical results and present the algorithm for locally identifying causal relations.
Proposition I ensures that the existence of an edge between X and another vertex V E .MB(X). identified in Lx, is consistent with the edge identified in the PAG learned from the observed data O.
5.1. Locally Learning Conditional Sets
Proposition 2. Let Lx be the inferred PAG over MB* + (X). Let V (1 S i S |MM((X) )) represent the vertices in MB(X). The following statements hold:
We incorporate the properties of Markov Blanket (MB) to locally learn the conditional set used in the above results of local characterizations, i.e. Pa Px*(X,)); Ne* (X, and Ne (XM, Specifically, we answer the following questions:
S1. The unshielded collider triples (V-structures) V1*
X <*12 identified in Lx are consistent with those in the ground-truth PAG.
How to discover which vertices in MB(X) are con- nected to X via arrow-collider paths circle-collider paths? This involves locally learning the induced sub- graph of P over MB* MB+(X), denoted as P PMB+(X) (X). How to determine whether X is an invariant non- ancestor of the vertices on these paths? This requires identifying all vertices in MB( for which X is an invariant non-ancestor, denoted as 1Pre (X).
S2. The uncovered collider paths X= V1 ++ ++V identified in Lx are consistent with those in the ground- truth PAG.
Proposition 2 specifies the locally identified colliders that are correct, representing the true directional information that can be retained.
Proposition 3 (Stop Rules). Let X be the target variahle of interestand Waitlist represent the collection of variables whose L will be learned. any of the following rules are satisfied, the learned P MB (xyis equivalent to the structure identified by global learning methods.
To address the first question, we extend the MMB-by-MMB algorithm proposed by Xie et al. (2024) learn P PMB+ Note that the original MMB-by-MM. solely on learning the structure involving the target variable and its adjacent variables, whereas we generalize it to apply to any variable, not limited to the target variable's 's adjacent variables. Specially, the P PMB+(Cx (x) learning process is iter- ative, with each step focusing on the local structure of
algorithm focuses
R1. The edges among the variables of (X) are all determined, i.e., no circle present in the marks. R2. The Waitlist is empty.
6

---

Local Identifying Causal Relations in the Presence of Latent Variables
R3. All paths from each veriex in MB+ MX), which include undirected edges (connected two vertices in MB* (X)), are blocked by edges *+t.
Complexity of Algorithm 2. Let denote the number of lo-
cal structures to be learned sequentially in Algorithm 1, and let n denote the size of the observed set O. The worst-case complexity is O r(2n-r=1) + +r|M + (2)] + +M
R1 and R2 indicate that all causal information of interest has been identified, or & for all variables in O has been learned. Broadly, R3 states that if all paths connecting the undirected edges between two vertices in MB* (X) are all blocked by the edge *-,, further exploration of L for the remaining variables will not contribute to determining the direction of these undirected edges.
where [M] is the number of maximal cliques of CossCh(X, ())NNe(X, P). and |MB+] is the size of MB+ The first two terms correspond to Line 1 (i.e., Algorithm 1) while the last term corresponds to Lines 2 12. The detailed calculation process is provided in Appendix F.
Algorithm 1
Local Learning Conditional Sets
We address the second question. The basic idea is as follows:
Input: Target X, observed data O
1: The local structure P (M)+(X) is obtained by invoking the Learning 'P PMB 1 (x)and Learning IPre (X) algo- rithms.
Learning IPremB X) algorithm
1. Induced the subgraph PMr+ (x) from from
P. Initialize IPre (X) with vertices adjacent to X where the edge is X < <x, and set CandSet = X (M, (x)).
2: Based (M and IBr)MB(X), we derive Pa (X,P), Ne (X,P). and Ne (XM, P) for each M E MEM.
and Ne (XM, P) for Output: Pa Pa*(X,P), Ne (X, each M E M..
2. Perform sequential iterations, focusing on the first vari- able V; in CandSet during each step. If there exists set Z S TPre MB (X) such that X II V; Z, add V; to IPre MB (X) and remove it from CandSet.
3. The process ends when no variable in CondSel. can be added in (B()).
Algorithm 2 LocICR
Input: Target variable pair (X, Y). observed data O
I: Pa" Pat(X, P), Ne" (X, and Ne*(XM: P)) for each
Proposition ensures the correctness of the above algorithm.
M E M are obtained by invoking the Algorithm 1
Proposition 4. Let P be the ground-truth PAG over O, and let PMRt (x)dentee the induced subgraph of P over MB+(X, Let (B()) be the set of invariant non-descendant of X. For a vertex V E (M) AX, PMB++()) if and only if there exists a set Z C MB) that m- separates X and V.
2: X IL Y Pa" P) then
return X is an invariant non-ancestor of Y
4: end if
5: if X JL Y (X, U (x, then
X is an invariant non aane-aneetoorooo of V
6: return X is an explicit invariant ancestor of Y
7: end if'
8: M = the set of maximal cliques of (Poss (X,
Ne(X,P))
After addressing the two main questions, we present the local learning method for conditional sets in Algorithm 1. The detailed pseudocode is provided in Algorithm 1 in Appendix D, with a complete example included in Appendix E.
exist M E MI such that X 1l Y (X,
(XM, P) then
10: return X is possible ancestor of Y
11: end if
12: return X is implicit invariant ancestor of Y
Theorem 5. Assuming oracle tests for conditional inde- pendence, the outputs of Algorithm are identical to those obtuined from the ground-truth PAG.
Output: The causal relation between X and Y.
6. Experimental Results
5.2. Local Identifying Causal Relations Algorithm
To evaluate the accuracy and efficiency of our algorithm, we apply it to synthetic datasets generated from benchmark networks, as well as to two real-world datasets. We utilize the existing implementation of the Total Conditioning (TC) discovery algorithm (Pellet & Elisseeff, 2008b) to identify the Markov Blanket (MB) of a variable. Our source code is available at https: htt///gtthaaaaa thub. com/ zheng1i0060 LocICR.
In this section, we introduce the Local Identifying Causal Relations algorithm, referred to as the LocICR algorithm.
Theorem 6. Assuming the oracle tests for conditional in- dependence. Algorithm 2 is both sound and complete for identifying invariant non-ancestor, explicit invariant ances- tor, implicit invariant ancestor, and possible ancestor causal relationships between any pair of variables in O.
7

---

Local Identifying Causal Relations in the Presence of Latent Variables
0.00
30.00
5300
Sample
Sample
Sample
(a) Performance Comparisons MILDEW.Net
(b) Performance Comparisons ALARM.Ne
1.15
35
30
0.0
2.42
1.0
0.
Sample Size
Sample Size
Sample
Sample Size
(c) Performance Comparisons on WIN95PTS.NG
(d) Performance Comparisons on ANDES. Net
LocICR
PCHITC
PC-IDA
Local-ITC
RFCI-VIDA
RECI-ZHANG
M3HC-ZHANG
ICD-ZHANG
Figure 4. Performance of eight algorithms four benchmark networks
6.1. Synthetic Data with Benchmark Networks
results are averaged across the 100 datasets.
In this section, we compare the proposed LocICR algorithm with global structure-based learning methods, including PC-
Metrics: We use the following metrics:
Weighted Precision (WP): the weighted average of per- class precision, where each precision is the ratio of true positives for the i-th class in the output to the total num- ber of predictions made by the algorithm for the i-th class.
ITC (Spirtes & Glymour, 1991; Fang et al., 2022), RFCI- Zhang (Colombo et al., 2012; Zhang, 2006), M3HC-Zhang (Tsirlis et al., 2018), ICD-Zhang (Rohekar et al., 2021) (based on criteria), and PC-IDA (Maathuis et al., 2009) as well as RECI-LVIDA (Malinsky Spirtes, 20i6n causal effect estimation methods). We also compared it with the local structure-based learning method, Local-ITC, which does not account for latent variables (Fang et al., 2022). Detailed descriptions of these methods are provided in Appendix G.I.
Weighted Recall (WR): the weighted average of per- class recall, where each recall is the ratio of true positives for the i-th class in the output to the total number true instances of the i-th class in the ground truth.
Weighted FI (WF1): the harmonic mean of WP and WR, calculated as
Experimental setup:
We use four benchmark networks vary- ing dimensionality: MILDEW, ALARM, WIN95PTS, and ANDES, containing 35, 37, 76, and 223 vertices, respec- tively. Following the convention in (Colombo et al., 2012; Malinsky & Spirtes, 2016; Fang et al., 2022), the benchmark networks are parameterized as linear Gaussian structural causal models, with the causal strengths chosen uniformly at random from the range ( and noises drawn from the standard Gaussian distribution. The number of latent variables is set to 4, 4, 6, and 10 for the respective randomly
WF1 2 WP WR
WP WR n'Test: the number of (conditional) independence tests implemented by algorithm.
Due to space limitations, we present results for two metrics in Figure 4, with complete results provided in Appendix G. As shown, our proposed LocICR algorithm out- performs other methods in Weighted FI score across all net- works and sample sizes, demonstrating its effectiveness. The number of conditional independence tests required by our method is significantly lower than that of global structure- based methods, such as PC-ITC, PC-IDA, RECI-LVIDA, RFCI-ZHANG, and ICD-Zhang. Moreover, since M3HC hybrid method rather than purely constraint-base one, we excluded from the comparison regarding the n'ess. Notably, although the nTest value of the Local-ITC method
Results:
network. For each network, 100 datasets generated, with latent variables randomly selected for each dataset. Two observed variables were then randomly chosen as the target pair (X,Y) for each dataset. The reported
Deeaills of these networks can be found https: //wpp: bnlearn. com/ / bar cpositorr.
8

---

Local Identifying Causal Relations in the Presence of Latent Variables
is lower for most networks and sample sizes, our method still outperforms Local-ITC on the other three metrics. This is likely because Local-ITC only learns the local structure of X's is adjacencies under the assumption of no latent vari- ables. Additionally, methods assuming causal sufficiency. such as PC-ITC, PC-IDA, and Local-ITC, show less satisfac- tory results, highlighting their inability to handle situations involving latent variables.
(Y), which are neither connected by direct edge nor directed path from X to Y. Our method finds the son's s income as an invariant non-ancestor of the number of siblings.
These findings align with the domain knowledge in Duncan et al. (1972).
Gene Expression Data. We applied our proposed method to the gene expression dataset from Wille et al. (2004), which contains measurements from Arabidopsis thaliana under 118 different experimental conditions, including variations in light and darkness and exposure to growth hormones. The dataset includes expression data for 33 genes. We here adopt the model presented in Wille et al. (2004) (see Figure of Wille et al. (2004)) as a baseline.
6.2. Application to Real-Worke Datasets
General Social Survey Data. We applied our method to a dataset from the General Social Survey, a sociological data repository available online https: / /gss. norc. org/ us/en/gss html. The dataset contains six observed variables: Rather's occupation, son's 's income, father's s edu- cation, son's 's occupation, son's education, and number of siblings, with a sample size of 1380. We use the hypothe- sized model from Duncan et al. (1972) as a baseline. Their graph, determined using domain knowledge and temporal orders, is shown in Figure 5.
Results:
We selected six pairs of genes as target pairs, with direct relationships and directed paths, as well as pairs with no direct relationships or directed paths.
We first selected DXR (X) and MCT (Y), as well as HMGS (X) and HMGRI (Y), as the target pairs, both of which are connected by a direct edge. Our method identifies DXR as an invariant ancestor of MCT, and similarly, HMGS as an invariant ancestor of HMGRI.
Father's Education (V3)
Son's Educution (V5)
Next, we selected AACTI (X) and FPPSI (Y), as well as DXPS3 (X) and CMK (Y), where each pair is connected by a directed path from X Y. Our method identifies AACTI as an invariant ancestor of FPPSI, and likewise. DXPS3 as invariant ancestor of CMK.
Father's Occupation (V1)
Son's Income (V2)
Son's
Occupation (V4)
Finally, we considered PPDSI (X) and DXPSI (Y), as well as DXPS/ (X) and DXPS3 (Y), neither of which connected by a direct edge or directed path from X to Y. Our method finds that PPDSI is an invariant non- ancestor of DXPSI, and similarly, DXPSI is an invariant non-ancestor of DXPS3.
Number of Siblings
(VG)
Figure 5. Status attainment model based on domain knowledge (Duncan al., 1972; Shimizu et al., 2011). A directed edge be- tween two vertices in the figure means that there could be directed edge between the two variables. A bi-directed edge hetween two vertices means that the relation is not modeled.
These findings align with Wille et al. (2004).
7. Conclusion
Results:
We selected four pairs of variables as target pairs, with direct relationships and directed paths, as well as pairs with no direct relationships or directed paths.
We addressed the problem of locally learning causal re- lations from observational data without assuming causal sufficiency. First, we provided sufficient and necessary local characterizations for identifying invariant ancestors, invariant non-ancestors, and possible ancestors. Then, we introduced LocICR, a novel algorithm for local causal dis- covery. We proved that LocICR is complete, matching the accuracy of existing methods. Experiments demonstrate its efffectiveness, efficiency, and robustness in handling latent variables in complex environments. Future work could ex- plore incorporating background knowledge. such as data generation mechanisms (Kaltenpoth & Vreeken, 2023) or expert insights (Wang et al., 2023b), to enhance causal dis- covery within local structures in LocICR
We first selected the father's occupation (X) and the son's 's education (Y) as the target variable pair, connected by a direct edge. Our method identifies the father's 's oc- cupation as an invariant ancestor of the son's 's education. Next, we selected father's occupation (X) and son's on's income (Y), as well as father's education (X) and son's income (Y) as the target variable pairs. In both cases, X and Y are connected by directed paths. Our method identifies both father's 'ss occupation and father's education as invariant ancestors of the son's 's income.
Finally, for son's 's income (X) and number of siblings

---

Local Identifying Causal Relations in the Presence of Latent Variables
Acknowledgements
Claassen, T. and Heskes, T. A logical characterization of constraint-based causal discovery. In Proceedings of the Twenty-Seventh Conference Uncertainty in Artificial Intelligence, pp. 135-144, 2011.
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.
Claassen, T., Mooij. J. M., and Heskes, T. Learning sparse causal models is not np-hard. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial In- telligence (UAI), pp. 172. Citeseer, 2013.
Colombo, D.. Maathuis, M. H., Kalisch, M., and Richard- son, T. S. Learning ligh-dimensional directed acyelic graphs with latent and selection variables. The Annals of Statistics, pp. 294-321, 2012.
Impact Statement
Discovering causal relationships from observational data is fundamental for advancing scientific knowledge in settings where experimental manipulation is not feasible. Our re- search introduces a novel approach that focuses on locally identifying relationships of interest even in the presence of latent variables, addressing a critical limitation of exist- ing methods that often assume no hidden confounders. A key strength of our work is the development of LocICR, an efficient and complete algorithm that utilizes necessary and sufficient local characterizations to accurately uncover causal relationships without requiring global structure learn- ing. This makes our method both scalable and practical for complex and large-scale datasets. Our approach is partic- ularly valuable diverse fields such as genomies, social sciences, and network analysis, where hidden variables fre- quently complicate causal inference.
Colombo, D., Maathuis, M. H., et al. Order-independent constraint-based causal structure learning. J. Mach. Learn. Res., 15(1):3741-3788 2014.
Duncan, O. D.. Featherman, D. L.,, and Duncan, B. Socioe- conomic background and achievement. Seminar Press, 1972.
Fang. Z. and He, Y. Ida with background knowledge. In Conference Uncertainty in Artificial Intelligence, pp. 270-279. PMLR, 2020.
Fang, Z., Liu, Y., Geng, Z., Zhu, S., and He, Y. A local method for identifying causal relations under markov equivalence. Artificial Intelligence, 305:103669, 2022.
References
Gao, T. and Ji, Q. Local causal discovery of direct causes and effects. Advances in Neural Information Processing Systems, 28, 2015.
Akbari, S., Mokhtarian, E., Ghassami, A., and Kiyavash, N. Recursive causal structure learning in the presence of latent variables and selection bias. Advances in Neural Information Processing Systems, 34:10119-10130, 2021.
Gao, T. and Ji, Q. Efficient markov blanket discovery and its application. IEEE transactions on Cybernetics, 47(5): 1169-11 1179, 2016.
Ali, R. A., Richardson, T., Spirtes, P., and Zhang. J. Orien- tation rules for constructing markov equivalence classes of maximal ancestral graphs. Technical report, Technical Report 476, Dept. of Statistics, University of Washington, 2005.
Guo, R. and Perkovic, E. Minimal enumeration of all possi- ble total effects in a markov equivalence class. In Interna- tional Conference on Artificial Intellignnce and Statistics, pp. 2395-2403. PMLR, 2021.
Aliferis, F., Statnikov, A., Tsamardinos, I., Mani, S., and Koutsoukos, X. D. Local causal and markov blanket induction for causal discovery and feature selection for classification part i: algorithms and empirical evaluation. Journal of Machine Learning Research, 11(1), 2010.
Guyon, I. and Elisseeff, An introduction to variable and feature selection. Journal of machine learning research, 3(Mar):1157-111 2003.
Hernán, M. A. and Robins, J. M. Causal inference, 2010.
Bhattacharya, R., Nagarajan, T., Malinsky, D., and Shpitser, Differentiable causal discovery under unmeasured con- founding. In International Conference on Artificial Intel- ligence and Statistics, pp. 2314-2322. PMLR, 2021.
Jonas, P., Dominik, J., and Schölkopf, B. Elements of Causal Inference MIT Press, 2017.
Kalisch, M., Mächler, M., Colombo, D., Maathuis, M. H., and Bühlmann, Causal inference using graphical mod- els with the r package pcalg. Journal of statistical soft- ware, 47:1 2201126,660 2012.
Claassen, T. and Bucur, I. G. Greedy equivalence search in the presence of latent confounders. In Uncertainty in Artificial Intelligence, pp. 443-455 Pmlr, 2022.
10

---

Local Identifying Causal Relations in the Presence of Latent Variables
Kaltempoth, D. and Vreeken, J. Nonlinear causal discovery with latent confounders. In International Conference Machine Learning, pp. 15639-15654. PMLR, 2023.
Pellet, J.-P. and Elisseeff, A. Finding latent causes in causal
networks: an efficient approach based markov blankets. Advances in Neural Information Processing Systems, 21, 2008a.
Liang, J., Wang, J.. Yu, G., Domeniconi, C., Zhang, X., and Guo, M. bradient-based local causal structure learning. IEEE Transactions Cybernetics, 2023.
Pellet, J.-P. and Elisseeff, A. Using markov blankets for causal structure learning. Journal of Machine Learning Research, 9(7), 2008b.
Liu, Y., Fang, Z., He, Y., and Geng, Z. Collapsible ida: Collapsing parental sets for locally estimating possible causal effects. In Conference on Uncertainty in Artificial Intelligence, pp. 290-299. PMLR, 2020a.
Pensar, J., Talvitie, T., Hyttinen, A., and Koivisto, M. A bayesian approach for estimating causal effects from ob- servational data. In Proceedings of the AAAI confer- ence on artificial intelligence, volume 34, pp. 5395-5402 2020.
Liu, Y., Fang, Z., He, Y., Geng, Z., and Liu, C. Local causal network learning for finding pairs of total and direct effects. Journal of Machine Learning Research, 21 (148):1-37, 2020b.
Raghu, V. K., Ramsey, J. D., Morris, A., Manatakis, D. V., Sprites, P., Chrysanthis, P. K., Glymour, C., and Benos, P. V. Comparison of strategies for scalable causal dis- covery of latent variable models from mixed data. Inter- national journal of data science and analytics, 6:33-45, 2018.
Maathuis, M. H. and Colombo, D. A generalized back- door criterion. The Annals of Statistics, 4363):1000-1088, 2015.
Maathuis, M. H., Kalisch, M., and Bühlmann, P. Estimating high-dimensional intervention effects from observational data. The Annals of Statistics, 3316A))3133-3166 2009.
Richardson, T. Markov properties for acyclic directed mixed graphs. Scandinavian Journal of Statistics, 30(1) 1455 157, 2003.
Malinsky, and Spirtes, P. Estimating causal effects with ancestral graph markov models. In Conference on Proba- bilistic Graphical Models, pp. 299-309. PMLR, 2016.
Richardson, T. and Spirtes, P. Ancestral graph markov models. The Annals of Statistics, 30(4))962-0030, 2002.
Mooij. J. M. and Claassen, T. Constraint-based causal discovery using partial ancestral graphs in the presence of cycles. In Conference on Uncertainty in Artificial Intelligence, pp. 1159-1168. Pmir, 2020.
Rohekar, R. Y., Nisimov, S., Gurwicz, Y., and Novik, G. Iterative causal discovery in the possible presence of la- tent confounders and selection bias. Advances in Neural Information Processing Systems, 34:2454 2465, 2021.
Nandy, P., Maathuis, M. H., and Richardson, S.S. Estimat- ing the effect of joint interventions from observational data in sparse high-dimensional settings. The Annals of Statistics, pp. 647-674, 2017.
Roumpelaki, A., Borboudakis, G., Triantafillou, S., and Tsamardinos, I. Marginal causal consistency in constraint- based causal learning. In Proceedings of the UAI 2016 Workshop on Causation: Foundation to Application, pp. 39-47, 2016.
Ogarrio, J. M., Spirtes. P., and Ramsey, J. A hybrid causal search algorithm for latent variable models. In Confer- ence probabilistic graphical models, pp. 368 368-379. PMLR, 2016.
Sanchez-Romero. R., Ramsey, J. D., Zhang, K., Glymour, M. R., Huang, B., and Glymour, C. Estimating feed- forward and feedback effective connections from fmri time series: Assessments of statistical methods. Network Neuroscience, 3(2):274 2019.
Pearl, Probabilistic reasoning in intelligent systems: ner- works of plausible inference. Morgan Kaufmann Pub- lishers Inc., San Francisco, CA, USA, 1988. ISBN
0934613737.
Schölkopf, B. Causality for machine learning. In Probu- bilistic and Causal Inference: The Works of Judea Pearl, pp. 765-804. 2022.
Pearl, Causality: Models, Reasoning, and Inference. Cambridge University Press, 2000.
Shimizu, S., Inazumi, T., Sogawa, Y., Hyvarinen, A., Kawa- hara, Y., Washio, T., Hoyer, P. O., Bollen, K., and Hoyer, P. Directlingam: A direct method for learning lin- ear non gaussiann structural equation model. Journal of Machine Learning Research-JMLB, 12(App):1255-124, 2011.
Pearl, J. Causality, Cambridge university press, 2009.
Pearl, J. Theoretical impediments to machine learning with seven sparks from the causal revolution. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 3-3, 2018

---

Local Identifying Causal Relations in the Presence of Latent Variables
Smith, S. M., Miller, K. L., Salimi-Khorshidi,, G., Webster, M., Beckmann, C. F., Nichols, T. E.,, Ramsey, J. D., and Woolrich, M. W. Network modelling methods for fmri. Neuroimage, 54(2):875 891, 2011.
Yin, J., Zhou, Y., Wang, C., He, P., Zheng, C., and Geng. Z. Partial orientation and local structural learning of causal networks for prediction. In Causation and Prediction Challenge, pp. 20-105. PMLR, 2008.
Spiegelhalter, J., Dawid, A. P., Lauritzen, S. L., and Cow- ell, R. G. Bayesian analysis in expert systems. Statistical science, pp. 219-247, 1993.
Zhang, Causal inference and reasoning in causally insuf-
ficient systems. PhD thesis, Citeseer, 2006.
Zhang. J.
On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17): 1873-1896, 2008.
Spirtes, P. and Glymour, C. An algorithm for fast recovery of sparse causal graphs. Social science computer review, 91):62-72, 1991.
Zhang. J. and Spirtes, P. A transformational characteriza- tion of markov equivalence for directed acyclic graphs with latent variables. UAr05, pp. 667-674, Arlington, Virginia, USA, 2005. AUAI Press. ISBN 0974903914,
Spirtes, P. and Richardson, T. A polynomial time algorithm for determining dag equivalence in the presence of la- tent variables and selection bias. In Proceedings of the 6th International Workshop on Artificial Intelligence and Statistics, pp. 489-500. Citeseer, 1996.
Zhao, H., Zheng, 2., and Liu, B. On the markov equivalence maximal ancestral graphs. Science in China Series A: Mathematics, 48:548-56:1 2005.
Spirtes, P., Glymour, C., and Scheines, R. Causation, Pre- diction, and Search. MIT press, 2000.
Zheng, Q. Liu, Y., and He. Y. Local causal dis-
Tsirlis, K., Lagani, V., Triantafilluu, S., and Tsamardinos, On scoring maximal ancestral graphs with the max- min hill climbing algorithm. International Journal of Approximate Reasoning, 102:74-85, 2018.
covery with background knowledge. arXiv preprint arXiv:2408.0733 2024.
Zhou, Y., Wang, C., Yin, J., and Geng, Z. Discover local
causal network around target to given depth. In Causal- ity: Objectives and Assessment, pp. 191-202. PMLR, 2010.
Wang, C., Zhou, Y., Zhao, Q., and Geng. Z. Discovering and orienting the edges connected to target variable in a dag via a sequential local learning approach. Computational Statistics & Data Analysis, 77:252-266 2014.
Zuo, A., Wei, S., Liu, T., Han, B., Zhang. K., and Gong, M. Counterfactual fairness with partially known causal graph. Advances in Neural Information Processing Systems, 35: 1238-1252, 2022.
Wang, T.-Z., Qin, T., and Zhou, Z.-H. Estimating possi- ble causal effects with latent variables via adjustment. In International Conference on Machine Learning, pp. 36308 -33385 PMLR, 2023a.
Wang, T.-Z., Qin, T., and Zhou, Z.-H. Sound and complete causal identification with latent variables given local back- ground knowledge. Artificial Intelligence, 322: 103964, 2023b.
Wille, A., Zimmermann, P., Vranová, E., Fürholz, A., Laule, O., Bleuler, S., Hennig, I.., Prelić, A., von Rohr, P., Thiele, L., et al. Sparse graphical gaussian modeling of the isoprenoid gene network in arabidopsis thaliana. Genome biology, 5:1-13, 2004.
Xie, F., Li, Z., Wu, P., Zeng, Y., Chunchen, L.., and Geng, Z. Local causal structure learning in the presence of latent variables. In International Conference on Machine Learning. PMLR, 2024.
Yang. S., Wang, H., Yu, K., Cao, F., and Wu, X. Towards ef- ficient local causal structure learning. IEEE Transactions on Big Data, 86)):1922-1609 2021.
12

---

Local Identifying Causal Relations in the Presence of Latent Variables
Appendix Contents
A More Details on Preliminaries
14
A.1 Detailed Definitions about Graph
14
A.2 More Details on Markov Blanket
15
A.3 Overview of Causal Relationships
16
Supplement Theorems
17
Proofs
18
C.I Proof of Theorem
18
C.2 Proof of Theorem 2
19
C33 Proof of Theorem
19
C.4 Proof of Corollary
20
C.5 Proof of Theorem 4
20
C.6 Proof of Proposition 2
20
C.7 Proof of Proposition
21
C.8 Proof of Proposition
22
C.9 Proof of Theorem
22
C.10 Proof of Theorem 6
23
D More Details Local Learning Conditional Sets Algorithm (in Section 5.1)
23
Illustration of Algorithms
24
F Complexity of Algorithm 2
26
More Details Experimental Results
26
G.1 Overview of Comparison Methods
26
G.2 Evaluation Metrics
26
G.3 The Markov Blanket Learning Algorithm
27
G.4 Complete Results
28
13

---

Local Identifying Causal Relations in the Presence of Latent Variables
A. More Details on Preliminaries
Table I. The list of main symbols used in this paper
Symbol
Description
G M P
directed acyelic graph (DAG)
Maximal Ancestral Graph (MAG)
A Partial Ancestral Graph (PAG)
M
A class of Markov equivalent MAGs
IP!
The Markov equivalence class represented by PAG
The set of all variables
O
The set of observed variables
L
The set of latent variables
MB(X, G)
The Markov blanket of vertex X in DAG G The Markov blanket of vertex X in MAG M
MB(X,
M)BXX)
vertex in a PAG P. we use MB(X) to denote MB P) when there is no loss in clarity The set of (M U X)
The Markov blanket
MX)(X)
IMB(X)I
Number of variables in MB(X)
A B P
A and B are not adjacent
A 4 B in P
A and B are adjacent
A B in P
B is a possible child of A, A is a possible parent of B
Ao-o B i
B is neighbor of A, A is neighbor of B
A- B i
A a parent B. is child of A
A B B i
There is latent common cause of A and B
Pa(X. P). P)(X,P)
The set of all parents (-> X) and children (+- X) of X in a PAG P, respectively The set of all variables that have direct edges connected to X
XX)
PossPa(X, P), PossCh(X, Ne(x,
The set of all possible parents (o-> X). possible children (+-oX) and neighbors
(a-oX) of X in a PAG P. respectively The augmented parent set of X in a PAG p
PX'(X,P) P) (X,P))
The augmented undirected neighhor set of X in a PAG P
M
The set of maximal eliques of the induced subgraph of P over PX) Ne(X,P) P)
M
maximal clique
Ne Ne".M, P)
The augmented undirected neighbor set of X relative to maximal clique M The induced subgraph of P over MB+ (X)
PMB+(X)
M))
The set of non-descendant variables of X a MAG M
(X)
The set of vertices in MB(X) such that X is an invariant non- non-ancestor of it
An(X, M). M)
The set of all ancestors and descendants of X in MAG M, respectively A set Z m m-separates X and Y in G X is statistically independent of Y given Z. We drop the subseript P whenever is clear from context.
XX IL YIZ)s
X IL YIZ
X K. Y
X is not statistically independent of Y given Z A is a cause of B. but B is not cause of A
A + B in G
A B in
A is not cause of B, and B is not cause of A The local structure learned over MB+ (1B+(V), (V), utilizing the test conditional independence and orientation of V-structures The algorithm used for learning MB
Lv
MBag WaitList
The list of variables be checked by Proposition I and Proposition 2 The list of variables whose local structures have been found
DoneList
A.1. Detailed Definitions about Graph
Graphs. A graph g = (V, E) consists of set of vertices V -Vi,..., Vv), denoting variables, and a set of edges E C VVx x V, representing the relationships between variables. The two ends of an edge are called murks, there are three types of marks: arrowhead '<', tail '_' and circle 'o", A graph is directed mixed if the edges in the graph are directed (+), or bi-directed (++). For two vertices Vú and V, in g, V; is a parentichildlsposee of V, if there is V; + V//V, + V,/V, + V, in G. V, and Vj are adjacent if there is an edge between them. A path from V. to V, in g is a sequence of distinct variables (Vo...., Vn) such that for 0 S i S n 1, V and V141 are adjacent in G. The length of a path equals the number of edges on
14

---

Local Identifying Causal Relations in the Presence of Latent Variables
the path. A directed path from V; to Vj is path composed of directed edges pointing towards Vj, i.e., V, -..... VJ. If exists a directed path from V to Vj. V; is an ancestor of V3 and Vj is descendant of V,. An almost directed cycle happens when V; is both a spouse and an ancestor of V A directed cycle happens when V; is both child and an ancestor of Vj, Definition 9 (m-connecting (Spirtes et al., 2000; Zhang, 2008)), In a directed mixed graph, path between vertices X and Y is m--connecting(aciint relative to a (possibly empty) set of vertices Z (X,Y & ()) (1) every non-collider on is not member of Z; (2) every collider on has descendant in Z.
X and Y are said to be m-separated by Z if there is no active path between any vertex in X and any vertex in Y relative to Z.
Definition 10 (Inducing Path). An inducing path between V₁ and Vj is a path on which every non-endpoint vertex is collider on the path and every collider is an ancestor of either V; or Vz.
Definition 11 (Maximal Ancestral Graph (Richardson & Spirtes, 2002; Zhang, 2008)). A directed mixed graph is ancestral if it doesn't I contain a directed or almost directed cycle. An ancestral graph is called maximal for any two non-adjacent vertices, there is no inducing path between them, i.e. there exists a set of vertices that m-separates them. A directed mixed graph is called a maximal ancestral graph (MAG) if it is ancestral and maximal, denoted by M.
A MAG is a Directed Acyclic Graph (DAG) if it has only directed edges. Two MAGs are Markov equivalent if they share the same m- m--eparations.
Definition 12 (Partial Ancestral Graph (Spirtes et al., 2000; Zhang, 2006)). Let [M] be the Markov equivalence class of an underlying MAG M. A partial ancestral graph (PAG, denoted by P) represents the equivalence class [M]. where a tail or arrowhead ">' occurs if the corresponding mark is tail or arrowhead every M E [M), and a circle 'o' occurs otherwise.
For convenience, we use an asterisk (+) to denote any possible mark of a PAG (o, MAG (>.-). Note that [P] represents an equivalence class of MAGs. For two vertices V; and V; in P. V42 is a possibly parent/possibly child/neighbor of Vj if there is V V//V, VVV, o-o in P. A path is a collider path if every vertex on it (except for the endpoints) is a collider along the path. A partially directed path (possibly causal path)from V; to V, is path where every edge without an arrowhead at the mark near V,, A path from V; to V that is not possibly causal is called a non-causal path from V, to Vj.
Definition 13 (Uncovered Path). A path .Vo...., Vv. is said to be uncovered for every 1 S Vi+1 are not adjacent, i.e., every consecutive triple (V:-1, Vi, Vi+1) on the path is unshielded.
1, Vi-1 and
Definition 14 (Induced Subgraph). Given graph G (V, E), where V is vertex set and E is an edge set. Given subset V of V, the induced subgraph of G over V is defined as G' = (V', E'), where E' C E contains only edges between vertices in V'.
Definition 15 (Complete Graph). In a graph, if there is an edge between any two vertices, then the graph is called complete graph.
Definition 16 (Maximal Clique). Given a graph G = (V,E), E), clique C in G is subset of vertices, where C C V, such that the induced subgraph Gc of over C is complete graph. C is called a maximal clique in G if there exists no clique C' in G such that C 5 C.
Definition 17 (Causal Markov Condition (Spirtes et al., 2000)). Given a set of variables V whose causal structure is represented by DAG G, every variable in V is probubilistically independent of its non-descendants in G given its parents in G.
Definition 18 (Causal Faithfulness Condition (Spirtes et al., 2000).. Given a set of variables V whose causal structure is represented by a DAG G. the joint probability of V, P(V), is faithful to G in the sense that P(V) implies no conditional independence relations not alreudy entailed by the causal Markov condition.
Under the above two conditions, conditional independence relations among the observed variables correspond exactly to m- m--epaaration in the MAG or PAG G. i.e., (X Y Z)p p e (X IL Y Z)
A.2. More Details on Markov Blanket
The concept of the Markov blanket was first termed by Pearl (1988) and has become a widely used technique for reducing the number of variables or features, thereby enabling more efficient and robust model construction (Guyon Elisseeff,
15

---

Local Identifying Causal Relations in the Presence of Latent Variables
2003; Pellet & Elisseeff, 2008b; Gao & Ji, 2016). More specifically, the Markov blanket of variable X is the smallest set containing all variables carrying information about X that cannot be obtained from any other variable (Aliferis al., 2010). Importantly the Markov blanket possesses unique and valuable property, which is formally described in Definition 19.
Definition 19 (Markoy Blanket). The Markov blanket of a variable X is the smallest set of variables MB(X) such that for all V E V UMB(X)U X is conditionally independent Vf given (B(X):
L MB(X).
Graphically, assuming faithfulness, the Markov blanket of vertex X in DAG is defined in Definition 20.
Definition 20 (Markov Blanket for DAGs (Pearl, 1988; 2000)). Assuming faithfulness, in DAG, the Markav blanket of vertex X is unique, denoted as (B CX G), includes the set of parents, children, and the parents of the children (spouses) of X.
The Markov blanket of one vertex in a MAG is then defined as shown in Definition 21.
Definition 21 (Markov Blanket for MAGs (Richardson, 2003; Pellet & Elisseeff, 2008a)). Assuming faithfulness, in MAG, the Markov blanket of a veriex X, noted as MB(X,M) consists of the set of parents, children, children's 's parents of X, as well as the district of X and of the children of X, and the parents of each vertex of these districts, where the district of vertex V is the set of all vertices reachable from V using only bidirected edges.
A.3. Overview of Causal Relationships
In this section, we provide an overview of the causal relationships within the Markov equivalence class of MAG, as illustrated in Figure 6. Additionally, we present an example to clarify these causal relationships, as shown in Figure 7.
Causal relations. From observed data, without additional distributional assumptions, the causal relationships between a pair of variables that can generally be identified are summarized as follows, with an overview provided in Figure
Invariant non-ancestor: a variable X is an invariant ancestor of variable Y if and only if there is no directed path from X to Y in every equivalent MAG.
Invariant ancestor: variable X is an invariant ancestor of a variable Y if and only if there is a directed path from X to
Y in every equivalent MAG.
Explicit invariant ancestor: a variable X is an explicit invariant ancestor of a variable if and only if X has a common directed path to in every equivalent MAG.
Implicit invariant ancestor: a variable X an implicit invariant ancestor of a variable Y if and only if X is an invariant ancestor of Y but there is no common directed path to Y in every equivalent MAG.
Possible ancestor: A variable X is a possible ancestor of a variable Y if X is neither invariant ancestor nor invariant non-ancestor of Y. In other words, X is possible ancestor of Y if there is a directed from X to Y in some (but not all) equivalent MAGs.
Examples. Consider the causal diagrams shown in Figure 7. We illustrate the above causal relationships with the following examples:
Invariant non-ancestor: Let X D and Y A. There is directed path from D to A in Figure (c-g), thus D qualifies as invariant non-ancestor of A.
Invariant ancestor:
Explicit invariant ancestor: Let X = D and Y = E. A common directed path D + E is present in every graph within Figure (c-g), thereby establishing D as an explicit invariant ancestor of F.
Implicit invariant ancestor: Let X = A and Y = D. There a directed path from A to D that can be observed in every graph within Figure 7 (c-g), but there is no common directed path from A to in these graphs. Therefore, considered an implicit invariant ancestor of D.
Possible ancestor: Let X B and Y C. A directed path from B to C exists in Figures 7 (f), but directed path is found from B to C' in Figures 7 (c-e) and (g). Consequently, B is regarded as a possible ancestor of C.
*Some authors the term "Markov blanket" without the notion of minimality, and "Markov boundary" denote the smallest Markov blanket. For clarity, we adopt the convention that the Markov blanker refers the minimal Markov blanket.
16

---

Local Identifying Causal Relations in the Presence of Latent Variables
Invariant non-Ancestor
Explicit Invariant Ancestor
None have
Common
Whether directed path exists from X to Y in each MAG within the MEC.
All have
Invariant Ancestor
No common
Partial have
Implicit Invariant Ancestor
Possible
Ancestor
Figure 6. Overview of Causal Relations in the Markov equivalence class (MFC) of true MAG.
B
B
C
B
D
D
D
E
E
E
(a) True MAG
(c)
(d)
(e)
A
A
B
D
(b) PAG
(8)
Figure 7. The legend illustrates the causal relationships within the equivalence class of MAG. MAG. (b) The corresponding PAG of the MAG in (a). (c-g) The Markov equivalence class of MAGs represented by the PAG in (b).
B. Supplement Theorems
In this section, we present the ordered local Markov property for MAGs as proposed by Richardson (2003). We then show Theorem 7, which states that the local Markov property in Definition 3 is consistent with the ordered local Markov property. First, we introduce the following important definitions related to the ordered local Markov property.
Definition 22 (Total ordering). Let M be the MAG over O, the total ordering < the vertices of M is defined such that for any two vertices V, E O:
V-X - X AV,)
where
denotes the set of all ancestors V M.
Definition 23 (District). In MAG M, the pulsed district of X, denoted as Dis (X,M), is the set of vertices connected to X by a path consisting entirely of bidirected edges (++), including X itself. Formally:
Dis + (X,M) = (XJUIV X
in M].
The district of X is defined as:
Dis(X,M) Dis (X,M) (X).
17

---

Local Identifying Causal Relations in the Presence of Latent Variables
The ordered local Markov property for MAGs proposed by Richardson (2003) is the following definition.
Definition 24 (Ordered local Markov property), Let M be the MAG over O, and let Pre(X, (V IV - X in M) and Pre+ (MM)) Pre(X,M) U [X]. Define M Pret as the induced subgraph of M on (re The ordered local Markov property states that for every variable X O, the following conditional independence holds;
X M) \ Mpret MMB(X,
(2)
where MB(X, Mpe)) Pa Dii (X, M )) Dis(X, M pret).
Lemma 1. Let M be the MAG over O, and let Pre Pret(X, (X
X). Let Mpre denote the induced subgraph of M on the vertex set Pret (X, For any vertex X E O, the following equivalence holds:
{V I
MB(X,MpM = MX)
Proof. Without loss of generality, we assume that
MB(X, Mprc ) & MX),
which implies that there exists a vertex V E MB(X, such that V & Pa Pa'(X, or there exists vertex V & (BB(X,Mrre such that V E Pa MX)
If there exists a vertex E MB(X,MPrert) then there one arrow-collider path from to in M. Assume that this vertex V (X, M). hence X is an ancestor of a vertex on this path (excluding X) in M. This contradicts the definition of Pret (X,M). Consequently, X is an ancestor of any vertex on this path in M, which implies V E Pa* (X, M).
Conversely, if there exists vertex V E Pa (a M), then, according to Definition 2, we have
V E Pa(Dis* (X.Mpre') 1) Dis(X, Mret).:
Thus, it follows that V E MB(XX,MMPP Mret))
This completes the proof.
Theorem Let M be the MAG over O. any vertex E O, the local Markov property in Definition is satisfied if and only if the ordered local Markov property is satisfied.
Proof. By the definitions of the ordered local Markov property and the local Markov property, as well as Lemma the equivalence is immediate.
C. Proofs
C.1. Proof of Theorem 1
Lemma (Zhang, 2006) Let be the PAG over a set of variables O representing the invariant characteristics of equivalent MAGs, X and Y are distinct vertices in P. X is an invariant non-ancestor Y if and only there is no partially directed path from X to Y in P.
Proof. Suppose that there is no partially directed path in P from X to Y, hence there cannot be any directed path from X to Y in the equivalent MAGs. Therefore, X is an invariant con-ancestor of Y. Conversely, suppose there is partially directed path from X to Y in P. This implies that there is directed path from X to Y in some equivalent MAGs M E (P). Thus, X is not an invariant non-ancestor of Y.
Lemma (A Crucial Property for PAG). (Lemma 3.3.1 Zhang (2006)) PAG, the following property holds: for any three vertices A, B, and C, if Ax B c-* C, then there is an edge between A and C with an arrowhead C, namely A+- C.
Now, we prove the Theorem based on the above Lemma 2 and Lemma 3.
18

---

Local Identifying Causal Relations in the Presence of Latent Variables
Proof. Assume that X IL Y Pa*(X,P), To begin with, assume Y E Px)(X, By the definition of Pa" Pa,(X))), Y cannot be a descendant of X in any MAG M E (P). Hence, X is an invariant non-ancestor of Y. Secondly, assume Y & Pa (X, P). Since X TL Y Pa" (X, P), X and Y are m-separated by Pa" (X, P). Moreover, by the definition of Pa" Pa"(X, P), every vertex in Pa" (X, P) does not block any directed path from X to Y for any MAG M E [P]. Therefore, there is no partially directed path from X to Y. If such a path existed, it would imply X y Y Pa" (x, P), contradicting the assumption. Thus, by Lemma 2, X is an invariant non-ancestor of Y.
Conversely, if X is an invariant non- ancestor of Y, then for every MAG M in the Markov equivalence class represented by P. X a non-ancestor of Y in every M E [P]. If there is no active path between X and Y. then we have X IL Y 0. By Definition 2, the set Pa" (X, P) does not open any active path between X and Y, X TT Y Pa" (X, P)) holds. If there is an active path = (X, Vi.... Vj, Z,... Y) between X and Y. by Lemma 2, there exists an edge V, Z on If the subpath of x between X and V, forms X <- V/1 ..... < Vg. then π is blocked by Pa Px" P). Alternatively, if the subpath of π between X and V, forms X x Vi... ... # V,, then, by Lemma 3, there exists an edge < Z between Z and {X, Vi....,Vy VV,,, then x also blocked by Pa" (X, P). Consequently, no new active path will be opened, and therefore X 1 Y Pa PX,(P holds.
C.2. Proof of Theorem 2
Before the proof begins, we quote the following lemma since it used prove Theorem 2.
Lemma (Lemma 7.2 in (Maathuis & Colombo, 2015)). Let X and Y be two distinct vertices in P, where P is PAG. If there is an uncovered partially directed path = (X Vi,..,, V2= Y) from X to Y. Moreover, if V for some i (2, k), then fー- + V3 for all, j E li.,k..,k
Now, we prove the Theorem 2.
Proof. Assume that X is an explicit invariant ancestor of Y. Then, there is a directed path π from X to Y in P. Moreover, this implies that there is directed path from X to Y in every M [P]. According to Definitions 2 and 7, none of the vertices in Pa" (X, P) U (X, are part of the path æ. Consequently, the path remains active conditional on Pa (X, U Ne X)P). This implies that X J. Y Pa (X"(X,P) U (X,
Suppose X J. Y (X, U Ne (X, P), which imply there is an active path π between X and Y conditional on Pa" (X, P) U Ne* (X, P). If the length of π is 1, then π must be one of the following forms: X ++ X o-* Y, and X-YY Further, if is one of the forms X <+ or X o-x Y, then Y E Pa (X, P) Ne P). which implies that is blocked by Pa" (X, P) U Ne (X, P) and consequently, X is not an explicit invariant ancestor of Y. If forms X - Y, then is not blocked by Pa (X, P) U (X,, P) and X is explicit invariant ancestor of Y. If the length of x is greater than 1, let = (X, V,... Y). The edge between X and V on is one of following forms: X <+V, X c- V, or X + V. If the edge between X and V on I is either X ++V or X a-x V, then π is blocked by Pa (X, P) U NX,((X P) as V E Pa (X, Ne" (X, P). If the edge between X and V on ι is either X <> or Xo-> V, a new active path x' may be created V is a collider on ~'. Let n = (X, V. W. ..... YY. according to Definitions 2 and 7, W E Pa"(X, Pe (X, P). Therefore, the new active path a' is also blocked by Pa" (Xx, P) U Ne (X, If W is a collider in another path similar to x', it will also be blocked by Pa (X, P) U Ne (X, P). If the edge between X and V on ι is either X <oV or X o-o V. according to Lemma 3, active path will be opened. Hence, the edge between X and V π is X - V, by Lemma 4, is a directed path and not blocked by Pa" (X, P) U Ne (X, P). Consequently, if X JL Y Pa Pat(X, P) U Ne (X, P), then there is directed path from X to Y in P, X is an explicit invariant ancestor of Y.
C.3. Proof of Theorem 3
Lemma 5. (Zhang, 2006; Roumpelaki et al., 2016) Let be the PAG over set of variables O representing the invariant characteristics of equivalent MAGs, X and Y are distinct vertices in P. X is an implicit invariant ancestor Y if and only if there are two uncovered partially directed paths from X to Y in P such that the vertices adjacent to X on the two paths respectively are distinct and are not adjacent.
Without loss of generality, we say the chordless partially directed path as the minimal uncovered partially directed path,
19

---

Local Identifying Causal Relations in the Presence of Latent Variables
where edge joins any two nonconsecutive vertices on the path. Hence, Lemma 5 can be stated as follows: X is implicit invariant ancestor of Y if and only if there two chordless partially directed paths from X to Y in P such that the vertices adjacent to X on the two paths respectively are distinct and are not adjacent.
Now, we prove the Theorem 3.
Proof. Assume that X is an implicit invariant ancestor of Y. This implies that while there is no directed path from X to Y in P. there exists a directed path æ from X to Y in every M E [P]. By Theorem 2, we know that X Y
Pa" (X, P) U Ne (X, P) as X is not an explicit invariant ancestor of Y. Now, according to Lemma 5, we have that [M] 2 2, where M- = (M,,,,,..... .2,..., Mpa J. For any M, E M. where 1 S i S [Ml] there a chordless partially directed path π (X, V1, V2.... : Vn, Y) from X Y such that V11 & M,. Since π is a chordless partially directed path, and by Definitions 2 and 7, it follows that none of the vertices (V2 .2..., Vn, can be invariant non-descendants of X. Consequently, these vertices do not belong to Pa" Pa"(X, (X, P) U Ne (XM, P). Moreover, it is evident that Vi & Pa (X, P) U Ne (XM,, P), Which ensures that x is active when conditioned on Pa" PX"(X P) U Ne (XM... P). Thus, for each M, E M, we conclude that X JLY Y| Pa (X, P) Ne (XM,,
Suppose X IL Y (X, (X", P), which implies X is not an explicit invariant ancestor of Y and Y & Ch(X, P). Additionally, we have X J Y Px"(X,P) P) U Ne (XM, P) for each M E M. which leads to the conclusion that Y & Pa (X, (X,P)U Ne* (XM, P). Hence, Y & AX, Now, we assume that M- {M, M2,.....
Mag}: If [M we have Ne" (XM,: P) (X, P). leading to contradiction: both X IL Y Pa (X, P) J Ne (X, P) and X + Y Pa" (X, P)U Ne"(XMo ,P) hold simultaneously. Therefore, [M] 2 2. Further, for each M, E M where 1 S < |MI, we have X JL Y (X,(X,7 PP) Ne (XM,, P), which implies that there exists an active path ι between X and Y that not blocked by Px,(X U Ne (XM, P). The length of π is greater than I, let т (X, V,.., .Y). If the edge between (.M,,))
X and V on π is X +VV, then i would be blocked by Pa" (X,P), P), implying that X f Y (X, P) U Ne (XM.. P) cannot hold, If the edge between X and V on x is X V. ग would form directed path by Lemma 4, which contradicts that X JL Y | Pa P) U Ne (X,P) P). Hence, the edge between X and V on ा must be X c-* V. Assume that the edge between X and V on π is X a-o V, and is not a partially directed path. Then there must be an edge V, + on æ. By Lemma 3, this implies that there is also an edge + between 2 and {X, V,... V which means that Z Pa P). Consequently, the assumption X J Y Pa" (X, Ne" NN"(XM,, P) would not hold. Therefore, π is an uncovered partially directed path. And [M] 2 2. we conclude that X is an implicit invariant ancestor of Y.
C.4. Proof of Corollary
Proof. The result follows directly from Theorems 2 and 3.
C.5. Proof of Theorem 4
Proof. X is an invariant non-ancestor of Y if and only if Theorem I holds, and X is an invariant ancestor of Y if and only if Corollary 1 holds. Thus, X is a possible ancestor of Y if and only if neither Theorem nor Corollary holds.
C.6. Proof of Proposition 2
Proof. For the proof of the statement S1 in Proposition 2, refer to Theorem 2 in Xie et al. (2024). We prove statement S2 in Proposition 2 below. For notational convenience, let Sx,y denote the set of vertices that m-separates X and Y. Let P be the ground-truth PAG over O.
Without loss of generality, suppose we identify an uncovered collider path in Lx: X* V1 +> +V, Here, all intermediate vertices are collider vertices, implying that every consecutive triplet forms an unshielded collider. Consider the first triplet (X, V1, V2). Since this triplet obtained over MB+ (X), the following conditions hold: (I) VS C MB(X), X y Vi S. (2) x.,1, C MB)X).A X IL V22 Sx.v2. (3) VS C MB+ V1 J. Vz S, and (4) V1 & Sx,v2 According to Proposition 1, condition (1) implies that the presence of a direct edge between X and V1 in Lx is consistent with P. And condition (2) implies that the absence of a direct edge between X and V/2 in Lx is also consistent with P. Assume that the edge between X and V1 in P is X v1. Then, combining conditions (3) and (4), we have VS S MB(X), X M. V22 S, which contradicts condition (2). Therefore, the edge between X and V1 must be X+ V in P.
20

---

Local Identifying Causal Relations in the Presence of Latent Variables
Next, assume the edge between V12 and V2 is spurious, meaning there is no direct edge between V1 and 1/2 in P but at least one active path exists between them. We denote specific set of vertices as Z Pa" (Vi) U Sx Vg. note that Pa" (V1) C M since X Vi. We analyze the active paths as follows. First, if there exists an active path of the form V1 + A1.... V2, then A1 can block that path. If A1 is a collider on a path p1 V1 .....***....... * + A1 < * V22 due to the graph being ancestral and V1= < Ai, there must exist V1 <- A2 on pl. Thus A₂ also blocks p1, and if A2 is also a collider on a path, it falls back to the case where A is a collider. Second, if there exists an active path of the form V11 ++ As -... V2. then A3 can block that path. A3 is a collider on a path p2: Ví * * +
A3 6- * *... V2, due to the graph being ancestral and A3- - ... V2, there must exist a A3 < *A1 on p2. Thus A₁ also blocks p2, and if A₁ is also collider on a path. it falls back to the case where A3 or A1 is collider. Here, all A, belong to Pa (V1). Thrid, if there exists active path of the form V - ... V22 then Sx.v, C (B) can block that path due to Xx + Vi and V1 & Sx,v. Thus, Z blocks all active paths between V1 and V22 confirming that the edge Vn= V in Lx is consistent with P.
Then, consider the second triplet (Vi, V22 Va). The following conditions hold: (1) VS S MB(X), + V/2 S. (2) ESV, S MB(X), V1 IL V/3 Sv (3) VS S MB+ (X). + V/s S, and (4) V22 & Sv. As discussed above, the direct edge between V1 and 1/2 in Lx consistent with P. and the absence of a direct edge between 1/2 and V/3 in Cx is also consistent with P. Assuming the edge between V1 and V/2 in P is V1 122,, conditions (3) and (4) lead to vS S MX(X), V12 P. V2 S, which contradicts condition (2). Therefore, the edge between X and V1 must be X++ Vi in P. Similarly, Pa (V2) C MB( since X - V12 ++ V22 Thus, the direct edge between V22 and V/3 in fxx is the same with P.
The remaining unshielded collider triples along the path are similarly confirmed by the above analysis. Thus, the uncovered ......VV +VV we identify in Lx must be consistent with those in the ground-truth PAG P.
collider paths X+ V22 + .......
C.7. Proof of Proposition 3
Rule R1 guarantees that all causal relationships among the variables in MB+ directionalitis- been fully identified. Rule R2 ensures that every variable in O has been effectively incorporated into the learning process, such that variable remains available for further sequential learning. R1 and R2 are hold by construction. Therefore, our focus shifts to verifying the validity of Rule R3. To support this, we first introduce the following lemma, which will play crucial role in proving R3 of Proposition 3.
(X))ixxiinlludin including both the edges and the
Lemma 6 (Lemma 2 in Xie et al. (2024)). In a MAG M with set of vertices O. consider K as a leaf vertex (i.e., K is not an ancestor of any vertex in O). Let M' be the new MAG obtained by removing K from M, and O' be the set of all vertices in M', then the following condition holds:
P2((O'= (O)
(3)
Lemma establishes that the joint probability distribution of the remaining vertex set O' in the modified MAG M' is identical to that in the original MAG M. In other words, the removal of the leaf vertex K from M does not alter the joint probability distribution of the vertices in O'. When considering set of vertices that only includes the above-defined leaf vertex, the following intuition can be derived.
let O be a set of observed varibles, M be the MAG graph over O and X' =0 \ Y), where Y represents the set of leaf vertices relative to X' in M. According to Lemma 6, we can deduce that (x = PMr (X'), where M' is the new MAG obtained by removing the leaf set Y from M. Then, let X" = (0 \ YUY Y'), where Y' denotes the set of leaf vertices relative to X" in M'. Subsequently, using Lemma 6, we can infer PMr = (x"",X"),, where M" is the new MAG obtained by removing Y' from M'. By iterating this process, we arrive a local MAG ML, such that (M(X)= = PMr (X) PM (X) = PM,, (X), where X fo K), and K represents the set of leaf vertices removed during the iteration. It is worth noting that if we do not stop the process, Mr will indeed become an empty graph. However, by suitably removing leaf nodes, we can derive the local subgraph M2 of interest from the global MAG M.
Intuition:
Building on the lemma above, we now proceed to prove Rule R3 of Proposition 3.
Proof. Assuming the sequential learning process terminates due to satisfying R3, the result we learned is a sub-PAG of the global P over some observed variables. Roughly speaking, the learned result is a PAG of a Mr that by suitably removing leaf nodes from the global MAG M.
21

---

Local Identifying Causal Relations in the Presence of Latent Variables
Let's provide a more detailed explanation of R3. Assuming that we have identified set O' (XB+ S O') of variables around MB+ (X) in the sequential learning process. For each vertex T E (X),X), and another vertex V E MX)... Assume that we identify there is an edge between T and Vi, and it is an undirected edge. If we identify that all paths X) connected to this undirected edge possess the following characteristics: the edges between T and V
(T. V1, .e..... v. on these path are undirected, while there is an edge form V,, - K or V- K on these paths. When the undirected edge between any two variables in MB (X) satisties this condition, then R3 is satisfied, thus we can conclude the sequential learning algorithm.
Then, We proceed demonstrate why the sequential learning algorithm can be halted when R3 satisfied. In our learning process, we identify that the edges between T and V1 on the paths are undirected, while V,, K. The edge between V, and K on these paths from T to K in underlying Mr. is either V,, ++ K or Vn, - K. Since we have identified +- K, we can infer that these K vertices belong to the Ieaf vertices of the underlying ML. Combining these K vertices into a set K, according to Lemma 6, we can deduce that PM; (O") = PM, (O"), where O" = {O') K) and M'2 is the new MAG obtained by removing K from Mr. This implies that the joint probability distribution of the remaining vertices set O" in M', is equivalent to the joint probability distribution of the same vertex set O" in the Mr. Then, through (x(X)= = (X) = PM (X) PMz (X), we can get PM2 (0") = P'M("").
Assume that we failed to identify, based the marginal distribution of O", that all paths connected to the undirected edge between any two variables in MB+ (X) are blocked by * *-+ Then, we will continue the learning process until all paths connected to the undirected edge between any two variables in MB* MB) are blocked by a- through the marginal distribution of O'. To summarize, when R3 is triggered, we can get PM, (O') = PM which implies that continuing this algorithm will not contribute to orienting the undirected edges between any two variables in MB+(X) Hence, upon satisfaction of R3, we can conclude the sequential learning P (MB-+X))
C.8. Proof of Proposition 4
Proof. By Lemma 5, for a vertex V E MB(X)) \, Adj(X, P PMB+(x)): X is an invariant non-ancestor of V if and only if there no partially directed path from X V. Assume that X is an invariant non-ancestor of V. If there no active path between X and V. then X TL V (0 C (B(e) If an active path π exists between X and V. the length of is necessarily greater than 1, and I cannot be a partially directed path. Thus, there is an edge V3 <-Z on T. If the subpath of π between X and Vj forms X <- Vi... ... t- Vg, then X and V are m-separated by V1, where V/2 E /Pre (X). If the subpath of π between X and Vg forms X x-o Vi... o Vj, then by Lemma 3, there exists an edge t Z between Z and Conversely, assume X JL V | Z, where Z C IPre (X). If = 0. then there
(X, Vi,.., V2). where Z E /Pre is no active path between X and V, and consequently, no partially directed path from X to V. If Z + 0, then there exists an active path æ between X and V. If π is partially directed path from X to V, then the subpath of it between X and some Z E Z would also be partially directed path. Hence, is not a partially directed path from X to V. This completes the proof.
C.9. Proof of Theorem 5
Proof. We first prove the learned (MB-(x) identical to the induced subgraph of the ground-trutt PAG P over MB 1BB(( To establish the consistency between P (x)+(x) P, it is imperative to demonstrate the consistency of all edges and orientations in the resulting graph PMB+ PMB+(X)) (X).
(X).
Following Proposition 1, it is established that all edges in PMB+ (x)are are accurate. Subsequently, relying on Proposition 2, it can be inferred that all colliders in P PMB+(X0 (x)are are correct. Following Zhang's s orientation methodology, the undirected edges in P PMBB-U arr oriented by checking the presence of edges and directions in PMB++(0 Ultimately, by Proposition 3, if R1 is triggered, there are no circles on the edges among the of MB+(X) in (MB+ If R2 is triggered, it means that the final Donelist is equal to O. If R3 is triggered, it means that learning the L of the remaining variables does not help determine the undirected edges among the of MB+ MB+(X) (X) in P (x)+ Consequently, the resulting graph (MM-(X) identical to the
induced subgraph of the ground-truth PAG over MB+ (X).
Given the PMB+ (x) that is identical to the induced subgraph of the ground-truth PAG over MB* (X). For any vertex + V E Adj(X, (ij, P (PMB+(X)) V E MPreMa(X) if and only if the edge between V and X X ++V in PMB++X)- For any vertex VE E (X) Adj(X, PMB (x)). according to the Proposition 4, we can completely identify whether it belongs to
22

---

Local Identifying Causal Relations in the Presence of Latent Variables
IPre MB (X).
Thus, the learned PMB (x) corresponds to the induced subgraph of the true PAG over MB+ (X). Moreover, the learned IPre MP un
(X) includes all vertices in MB(X) for which X is an invariant non ancestor. Consequently, the conditional sets obtained from Algorithm match those derived from the ground-trun PAG.
C.10. Proof of Theorem 6
Proof. According to Theorem 5, the condition set obtained by Algorithm is consistent with those derived from the true PAG. Furthermore, leveraging the sufficient and necessary local characterizations for invariant oon-ancesoors, invariant ancestors, and possible ancestors, i.e., Theorem 1, Corollary 1, and Theorem 4, Algorithm 2 ensures sound and complete identification of causal relationships between any pair of variables.
D. More Details on Local Learning Conditional Sets Algorithm (in Section 5.1)
Algorithm 1 Local Learning Conditional Sets
Input: Target X, observed data O
Step one: Local learning PMB (X) -0)
1: Initialize: Waitlist = (X). Donelist = 0, P = 01
2: repeat
3: Vi é the head node of Waitlist.
4: MB(V,) + M Vi) (See Algorithm 3).
5: if 3V, Donelist, MB+ (V,) S MB+ (V2) then
6: Lv; the substructure of Lv; over MB+
7: else if MB+(V)) S Donelist then
8: Lv, t the substructure of P over MB+ (V:);
9: else
10:
Learn Lv, over MB* (Vi).
11:
end if
< select the edges connected V;, the V-structures containing V,, and the uncovered collider paths from V,,
P < orient maximally the edge marks using the orientation rules of Zhang (2008).
14:
Add V, Donelist, and remove V; from the Waitlist.
15:
Add (MB(V)) (Waitlist U Donelist)) to Waitlist
16:
until One of the stop Rules R1 ~ R3 is met
/ Step two: Local learning IPre #-
17: (x)+(x) + induced subgraph from P
18: IPre (X) {V E MB(X) X < in PMBL(X) (x)
19: CondSet = (B (X, (x))
20: repeat
V +- -the head variable of CandSet;
22: if 3Z IPre (B()) X IL V then
23: Add V to IPre MB (X), and remove V from the CondSet.
24: end if
25: until No variable in CandSet can be added in IPre
m Step three: Obtain conditional sets =-
26: According PMr+(X) IPre MB (X), obtain Pa*(X,P) (X, P), Ne (XM, P) for each M E M. Output: Pa" PX" (X,P), Ne* P) and Ne (XM, P) for each M E M.
23

---

Local Identifying Causal Relations in the Presence of Latent Variables
E. Illustration of Algorithms
In this section, we illustrate our LocICR algorithm with the graph Figure 8(a). Here we are interested in the causal relationship between the target variable pair (J, F). We assume oracle tests for conditional independence.
H
B
H
H
B
D
E
(a) Ground-truth PAG
(b) LJ
(c) Updated after learning L.
A
B
H
F
F
(d) Lo
(e) Updated P after learning LG
(f) Lp
G
A
H
B
H
D
F
(g) Updated P after learning CF
(h) The Final local
Figure 8. The sequential process of step one in Algorithm in the example, where the red edges indicate that the current local results cannot be guaranteed to he consistent with the global learning results.
A
G
A
H
H
J
H
B
D
(a) The Final PMs+(J)
(b) The Final [Premи(J) {G, A, C,, (c) Pa) (A, Ne (J,P)
Figure 9, The process of steps two and three in Algorithm I in the example.
1. LocICR first executes the Algorithm 1, as detailed below (Line of Algorithm
Step one: Local learning (M)+
Initialize sets: Waitlist {J), Donelist 0. and P (Line of Algorithm 1).
After initialization, it runs (J) and obtain MB(J) = {A, G, F, B, C, D, H} (Lines 3 ~ of Algorithm 1).
It then learns L, over (J++ Hl Go- J A B +oC, Ho+ D toJ, and B foF o-o C. as shown in Figure 8 (b) (Line 10 of Algorithm 1).
Next, it updates P by selecting edges connected to J, V-structures involving J, and uncovered collider paths from (Line 12 Algorithm 1). According to Propositions and 2, these edges are:
Go-+ <> A <oC, Ho-> D JJJ, and F.
24

---

Local Identifying Causal Relations in the Presence of Latent Variables
Orient D t-o as D J by orientation rules (Line 13 of Algorithm 1). Consequently, it obtains P shown in
Figure (c).
Update (J]) and Waitlist = (A,,G,F,B,CD,,HH (Lines 14 ~ 15 of Algorithm 1). Sequentially, it runs atg (A) and obtain (A) = {B,C,F, G,J} Since MB+ (A) C MB)+ is induced substructure of L, over MB
MB+(A) (A). (Line 6 of Algorithm 1)
No new edges are introduced to P by LA (Lines 12 14 of Algorithm 1).
Update (Anelist=(A, J). and Waitlist (G, F, B, C, D, H). (Lines 14 ~ 15 of Algorithm 1)
Since MB+(G) C MB* MB), LG is the induced substructure of L. over MB+(G), as depicted in Figure 8 (d). (Line 6 of Algorithm 1)
Run MBuig G) obtain MB(G)
A,
Update P by selecting edges connected to G, V-structures involving G, and uncovered collider paths from G (Line 12 of Algorithm 1). According to Propositions and 2, these edges are:
H o-o Go-> J A <+ B -oC, and B toF.
Orient H as D <- H by orientation rules (Line 13 of Algorithm 1). Consequently, it obtains as shown in
Figure 8(e).
Update DJn G}, and Waitlist = {F, B, H.
It then runs MB (F) and obtain MB(F) C,G.J,J (Lines 3 ~ 4 of Algorithm
Learn Dr over MB+ (F): Go-> A ++ B +oC, B o +oC, and F <oT, as depicted in Figure 8 (f) (Line 10 Algorithm 1).
Next, it updates P by selecting the edges connected to F, the V-structures containing F, and the uncovered collider paths from F (Line 12 of Algorithm 1). According to Proposition 1 and Proposition 2, these edges are: Go-+ < A ++ B <=C,, B +oF +oC, and <ol.
Orient B F-oF as B <- Fand C t-oF as C +- F using orientation rules (Line 13 of Algorithm 1). Consequently, it obtains P as shown in Figure 8 (g).
Then, updates Donclist= A, G, F), and Waitlist = (B,C, D, H).
Finally, the repetition terminates upon reaching R3, yielding the final PAG P, as depicted in Figure 8 (h).
Step two: Local learning (B(reM(()) (X).
Obtain (x)+(x) inducced from P, as depicted Figure (a). (Line 17 of Algorithm 1) Initialize: [J)=(] A}, CandSet=(H, B, F). (Lines 18 ~ 19 of Algorithm 1)
For И: Since G)) C [[PeMMB())) (J), IL И {G}, update:
[J)=(M H), CandSet=(BB, C,F), (Lines 22 23 of Algorithm
For C: Since J 11. C 0. update:
[PremB(J)=[G,Ak H,C), C). CondSet=(B, F). (Lines 22 23 of Algorithm 1)
. No subset Z C [PremB satisfies J 1L. B Z, and J 1L. F Z, thus the iteration stops. (Line 25 of Algorithm
1)
Final result: [PremB (J) (G, A, H,C)).
Step three: Obtain conditional sets. (Line 26 of Algorithm 1)
Based on PMB I (x)- depicted in Figure 9 (a), each vertex in the set C, is connected J via an arrow-collider path from J to it. Meanwhile, no vertex is linked to J through circle-collider path, implying that no vertex satisfies Definition 7.
Among these, the vertices (A, G} satisfy Definition 2. However, B does not, as the arrow-collider path from J to B is J + A ++ B, where B & IPre (X). Similarly, C fails to satisfy Definition 2 because the arrow-collider path connecting J to C is J +> A ++ B +- C, where B & 1Pre MB (X). Likewise, F does not satisfy Definition 2 since the arrow-collide path from J to F is J ++ A + B +- F, where B, F & IPre MB MB(X). (X).
Consequently, we derive the following results: Pa" (J, P) {A, G). Ne (J, P) 0 and M 0.
2. Building upon results, i.e., (J, P) = (A, Ne (J,P) =0 and M- = 0. LocICR identifies the causal relationship between the target variable pair F).
Since J J F {A, G}, it follows that J is not invariant non-ancestor of F. (Line 2 of Algorithm 2) Since / F {A, G} U it follows that an explicit invariant ancestor F. (Lines 5 ~ of Algorithm 2)
25

---

Local Identifying Causal Relations in the Presence of Latent Variables
F. Complexity of Algorithm 2
Algorithm 2's complexity mainly consists the following two parts.
Complexity of Algorithm (Line I of Algorithm 2). The complexity of step one of the algorithm can be divided into two parts: the first part involves finding MB, and the second part involves learning the local structure. Let r denote the number of local structures to be learned sequentially in this step. We used the TC algorithm & Elisseeff, 2008b) to search for MB, the time complexity of finding MB among r variables out of total variables 0 r(2n ((2m-r-1)) where denotes the size of observed set O. When learning local structure, apply the logic of the PC algorithm identify the skeleton over MB+ (++ (V.). In the worst case, the complexity for learning local structure over variables is O 2m)) Let |MB+]
denote the size of MB+ (Vt). In the worst case, the complexity of the step
one is O r(2 rIMB 2 MB²]
the complexity of the step two is O ( M Therefore, in the worst
case, the complexity of Algorithm is
(2n-7-1) +r|
Clearly, in the worst case, the complexity of Lines 2~12 of Algorithm 2 is O ([M), where [M the number of maximal cliques of PossCh(X, P) P) U Ne(X,
In conclusion, the worst-case total complexity is given by:
O
2n r 1)
+ 11M + |M|
2
G. More Details on Experimental Results
G.1. Overview of Comparison Methods
The following provides a detailed description of the comparison methods:
This method uses the PC-stable algorithm (Colombo et al., 2014) to learn the global causal structure, followed by the global-ITC method (Fang et al., 2022) to identify the causal relationships of interest.
PC-ITC:
RFCI-Zhang, M3HC-Zhang, ICD-Zhang: The RFCI (Colombo et al., 2014), M3HC (Tsirlis et al., 2018). ICD (Rohekar et al., 2021) algorithms are employed to learn the global causal structure, and the criteria outlined in (Zhang, 2006; Roumpelaki et al., 2016) are then applied to identify the causal relations of interest.
PC-IDA: The PC-stable algorithm (Colombo et al., 2014) is first used to learn the global causal structure. Causal effects are then estimated using the IDA algorithm (Maathuis et al., 2009), followed by identification of the causal relationships of interest based on the causal effect testing framework in Fang et al. (2022).
This method utilizes the RFCI algorithm (Colombo et al., 2014) learn the global causal structure, followed by the LV-IDA algorithm (Malinsky & Spirtes, 2016) for estimating causal effects. Finally, the causal relations of interest are identified using the causal effect testing framework from Fang et al. (2022).
RFCI-LVIDA:
Local-ITC: The My-B algorithm (Wang al., 2014) is applied learn the local causal structure of the target variable X, followed by the local-ITC method (Fang al., 2022) to identify the causal relationships of interest.
For the LV-IDA algorithm, we utilized the R implementation available at ht httpbb/tttttuutt./// cww dma wwwsslinskkvvr iinrriiaa ida, along with the RFCI and PC algorithms provided in the R package pealg (Kalisch et al., 2012). The ICD algorithm was implemented using the Python code from https: : /github. com/ algorithm was implemented MATLAB using the repository at httpp:://giit com men xmachina/MMHC
lab, while the M3HC
G.2. Evaluation Metrics
We evaluate the performance of the classifier using several commonly used metrics for multi-class classification problems. These include Weighted Precision (WP), Weighted Recall (WR) and Weighted F1 Score (WF1).
26

---

Local Identifying Causal Relations in the Presence of Latent Variables
Weighted Precision (WP): The Weighted Precision calculated as the weighted average of precision across all classes, where each class's precision is weighted by the number of true instances in that class. It is defined as:
1 WP
TP: TP.
FP:
==1
where:
TP; is the number of true positives for class
F; is the number of false positives for class i,
to is the weight of class i, typically the proportion of samples belonging to that class.
Weighted Recall (WR): The Weighted Recall the weighted average of recall across all classes, where each class's recall weighted by the number of true instances in that class. It is given by:
TP.
WR
TP. FN;
where:
F,,, is the number of false negatives for class i.
Weighted F1 Score (WF1): The Weighted F1 Score is the harmonic mean of Precision and Recall, weighted by the number of true instances in each class. The formula for the Weighted F1 score is:
1 Σ 1=1
2 Precision; Recall; Precision, Recall,
WF1
where:
Precision, and Recall; are the precision and recall for class i, respectively.
G.3. The Markov Blanket Learning Algorithm
Algorithm 3 MB (Pellct & Elisseeff, 2008b)
Input: Target V,, observed data of O
1: Initialize .V)(V) == 0.
2: for each VG E O \ V, do
3: V; J. V, O \ (Vi, V2} then
4: Add V, to MV.),)
5: end if
6: end for
7: MB+(V,) = (V; MB(V))
Output: MV+(V))
In this section, we describe the procedure of the Total Conditioning (TC) algorithm (Pellet & Elisseeff, 2008b), which we used to discover the Markov Blanket (MB). Definition 25 (Total Conditioning (Pellet Elisseeff, 2008b)). the context of a faithful causal graph G, the following holds:
YX
(X E Markov blanket (V)) + (X V V
(4)
27

---

Local Identifying Causal Relations in the Presence of Latent Variables
G.4. Complete Results
All experiments were performed with Intel 2.70GHz CPU and 64 GB of memory. The complete experimental results for the four benchmark Bayesian networks presented in Figure 10. Table 2 provides detailed overview of the network statisties used in this paper :
Table 2. Statistics on the Networks.
Networks
Num.nodes
Number of arcs
Max in-degree
Avg degree
MILDEW
35
46
3
2.63
ALARM
37
46
2.49
WIN9SPTS
76
112
7
2.95
ANDES
223
338
6
3.03
Details these networks can he found https: / www bn ctwpm/...////repssitttt/o//o///.
28

---

Local Identifying Causal Relations in the Presence of Latent Variables
0.2
011
2007
3900
200
3200
165
Sample
200
1000
2507
190
(a) Performance Comparisons on MILDEW.Net
0.2
0.0
0.5
Samplc
132
Sample Size
Sample
300
Sample
(b) Performance Comparisons on ALARM.Net
212
0.0
0.5
082
060
0.99
035
Sampli
Sample
Sample
(c) Performance Comparisons WIN9SPTS.Net
3.5
0.5
3.0
0.2
034
643
Sample Size
Sample Size
Sumple Size
Sample Size
(d) Performance Comparisons on ANDES.
LocICR
PC-TTC
PC-IDA
Local-ITC
RFCI-LVIDA
RFCI-ZHANG
M3HC-ZHANG
ICD- CCD-ZHANG
Figure 10. Performance of various algorithms four benchmark networks
29


Reviews:
[{"review_id": "Y1sJVW7H7A", "reviewer": "Reviewer_DqNE", "summary": "The paper addresses the challenge of locally identifying causal relationships between arbitrary pairs of variables in a causal graph, without assuming the absence of hidden confounders. Existing methods typically rely on access to the entire graph or impose strong assumptions about latent variables or on the pair of variables of interest, making them unsuitable for many real-world settings.\nThe paper provides necessary and sufficient conditions for classifying relationships as invariant ancestor, invariant non-ancestor, or possible ancestor based purely on local structure—even when latent confounders are present.\nIt introduces LocICR, a novel local causal discovery algorithm that determines causal relationships between a given pair of variables\nThe algorithm is proven to be sound and complete.\nExtensive experiments on benchmark causal networks and real-world datasets demonstrate that LocICR is both effective and computationally efficient.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive and thoughtful feedback, as well as your recognition of the importance, clarity, and empirical rigor of our work in the field of causal inference. We hope the following responses properly address your concerns.\n\n\n**Q1** ``introducing the correct definition of Markov Blanket for MAGs in the main paper''\n\n**A1.** Following your suggestion, we have moved the definition of the Markov Blanket for MAGs from the Appendix into the main text.\n\n**Q2** ``citing the seminal paper of Chekering when they first mention PAG''\n\n**A2.** Thank you for noting this. It was indeed a citation error, which we have now corrected in the revised version. We have properly cited works specifically addressing PAGs, including [Spirtes and Richardson, 1996], [Ali et al., 2004], [Zhang and Spirtes, 2005], and [Zhao et al., 2005].\n\n**Q3** ``... without requiring the learning of a full PAG, the enumeration of MAGs, or the assumption of causal sufficiency.'' Having a redundancy.\n\n**A3.** Thank you for your thoughts. We have removed this redundancy in the revised version. Our initial aim was to emphasize that the proposed approach does not rely on the assumption of causal sufficiency.\n\n**Q4** ``Why is the performance of the proposed algorithm on MILDEW is better at small sample sizes (in WR and WP)?''\n\n**A4.** Because our algorithm reduces the number of conditional independence (CI) tests through localization, it helps avoid bias introduced by excessive testing. Consequently, even with smaller sample sizes, our method outperforms other global approaches. Notably, existing local methods often perform worse because they require the assumption of causal sufficiency, while latent variables may be present in the system.\n\n**Q5** ``Enumerating all MAGs within a class and determining that X is an invariant ancestor across all equivalent MAGs is equivalent to saying that X is an invariant ancestor in the PAG?''\n\n**A5.** You are correct! Stating that X is an invariant ancestor in  all equivalent MAGs is equivalent to saying that X is an invariant ancestor in the PAG.\n\n**Q6** ``My intuition is that PAGs represents uncertainty within a class and since in all MAGs X is an ancestor then there is no uncertainty and so this information should be visible in the PAG, assuming you are using the complete rules of FCI. ... However finding a set satisfying the back-door criterion is not the same as finding ancestors. ''\n\n**A6.** First, we would like to clarify that although $X$ may be an ancestor in all equivalent MAGs, this fact might not always be explicitly visible(i.e., by checking the directed path) in the PAG. This discrepancy arises because PAGs represent uncertainty within a class of MAGs and do not explicitly encode all ancestral relationships. For instance, as illustrated in Fig. 6, there is no directed path from $A$ to $E$ in the PAG shown in Fig. 6(b), yet $A$ is an ancestor of $E$ in all equivalent MAGs (Fig. 6(c)-(g)).\n\nFurthermore, LV-IDA enumerates all (local) MAGs, identifies adjustment sets that satisfy the generalized back-door criterion, and estimates the possible causal effects accordingly. If all such causal effects are non-zero, the method concludes an invariant ancestor (Fang et al., 2022). For instance, in Fig. 6, LV-IDA calculates the causal effect from $A$ to $E$ for every equivalent MAG (Fig. 6(c)-(g)) as non-zero, thereby concluding that $A$ is an invariant ancestor of $E$.\n\n\n**Q7** ``is it possible to reduce the faithfulness assumption into a \"local\" faithfulness?''\n\n**A7.** Thank you for your thoughtful consideration. The local learning—such as our approach—can reduce unnecessary CI tests, which may help mitigate minor violations of the faithfulness assumption [Isozaki, 2014]. We will discuss this point in our paper and plan to explore it more thoroughly in future work.\n\nIsozaki T. A robust causal discovery algorithm against faithfulness violation[J]. Information and Media Technologies, 2014, 9(1): 121-131.\n\n> Thank you again for your careful reading. We have corrected the typos in the citations and simulation table in the revised version.", "claims_and_evidence": "The authors claim that no existing method locally identifies causal relationships between arbitrary pairs of variables without assuming the absence of hidden confounders.\n\nThey provide both necessary and sufficient local characterizations for invariant ancestor, invariant non-ancestor, and possible ancestor relationships.\n\nThey introduce LocICR, a novel algorithm designed to locally infer causal relationships between variable pairs, and prove its soundness and completeness.\n\n\nThey demonstrate the effectiveness and efficiency of their approach on experimental data.", "methods_and_evaluation_criteria": "Yes. Rigorous experimentation has been made, 4 benchmarks have been used containing each 100 simulated datasets along with 2 real world applications.\nThe experimental section is clearly written, providing all the necessary details, and five other methods were used for comparison. These methods are thoroughly described.", "theoretical_claims": "I checked some proofs and they seem to be sound.", "experimental_designs_or_analyses": "The experimental section consists of both a simulation study and a real-world data application. The simulation study is extensive and demonstrates the superior performance of the proposed method in terms of the weighted F1 score, as well as weighted precision and weighted recall. The authors also provide results on two real-world datasets, explaining these favorable outcomes with clear references.", "relation_to_broader_scientific_literature": "The authors are claiming that they are proposing the first method that locally identifies causal relationships between arbitrary pairs of variables without assuming the absence of hidden confounders (To the best of my knowledge this is true). Which means this paper is making causal inference more applicable in real world settings. Especially when the true causal graph is unknown and where discovering the true entire graph can be complicated for many reasons ...", "essential_references_not_discussed": "I think most relevant citation are included. I just suggested in the comment section few additional citation which can also be relevant.", "other_strengths_and_weaknesses": "The paper presents a compelling and relevant contribution to the field of causal inference.\n\nIt is clearly written and tackles an important problem in the domain.\n\nThe theoretical framework appears sound, and the experimental evaluation is rigorous, providing strong empirical support for the proposed approach.\n\nBy relying solely on local structure, the method remains computationally efficient and scalable, making it well-suited for large graphs where access to global knowledge is impractical.\n\n\nI did not spot any major weakness other than few sentences that I found a bit confusing. More on that below.", "other_comments_or_suggestions": "I think the pape is very clear. But maybe consider introducing the correct definition of Markov Blanket for MAGs in the main paper (instead of deferring it to Appendix). This can make the paper even more accessible for readers unfamiliar with MAGs.\n\n\nThe authors are citing the seminal paper of Chekering when they first mention partial ancestral graph (PAG). I think this can be confusing since Chickering introduce a CPDAG and not a PAG (the difference between a PAG and a CPDAG substantial). At least along with this citation, cite paper truly working on PAGs such as Spirtes and Richardson, 1996; Ali et al., 2004; Zhang and Spirtes, 2005; Zhao et al., 2005.\n\n\nIn this sentence: \"In this paper, we address the challenge of locally identifying the causal relationship between a pair of variables with- out requiring the learning of a full PAG, the enumeration of MAGs, or the assumption of causal sufficiency.\" You have a redundancy, if you are focusing on PAGs and MAGs then of course you are not assuming causal sufficiency.\n\n\nMinor Typo in the citation: \"Jonas, P., Dominik, J., and Scholkopf, B. ¨ Elements of Causal Inference. MIT Press, 2017.\" You replaced the first names of the first authors with their last names.\n\n\nTypo: In the second line of the simulation table, “WP” should be replaced with “WR.” \n\n\nWhy is the performance of the proposed algorithm on MILDEW is better at small sample sizes (in WR and WP)?\n\n\n\nSuggestion: Reference Appendix G.4 When Mentioning Benchmark Networks.", "questions_for_authors": "Enumerating all MAGs within a class and determining that  X is an invariant ancestor across all equivalent MAGs is equivalent to saying that X is an invariant ancestor in the PAG. No? Am I missing something? If you disagree can you please give an example? (My intuition is that PAGs represents uncertainty within a class and since in all MAGs X is an ancestor then there is no uncertainty and so this information should be visible in the PAG, assuming you are using the complete rules of FCI).\nThat said, I totally understand that in Malinsky and Spirtes, one way to get identification of a causal effect is via enumerating all MAGs and check if there is at least one set satisfying the generalized back-door criterion in each MAG. However finding a set satisfying the back-door criterion is not the same as finding ancestors. The latter is more complicated because the information it requires is not always visible by looking at the PAG. Maybe I am missing something so please correct me if you think I am wrong. I have scored the paper assuming that I am missing something related to this, I will update my score based on the rebuttal.\n\n\nSince you are interested in Local causal discovery, is it possible to reduce the faithfulness assumption into a \"local\" faithfulness?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GiSo0R7B0W", "reviewer": "Reviewer_sAoW", "summary": "This paper provides a local causal discovery method for inferring causal relations between a pair of variables. Specifically, given any two variables $X$ and $Y$, the proposed algorithm outputs one of the following four results: $X$ is an invariant non-ancestor of $Y$, $X$ is an explicit invariant ancestor of $Y$, $X$ is an possible ancestor of $Y$, $X$ is a implicit invariant ancestor of $Y$. The authors provide both theoretical analysis and experimental results to demonstrate the soundness and effectiveness of the proposed algorithm.\n\n\n==================update after rebuttal=========================\n\nThe authors' rebuttal address most of my concerns and I have already raised my score from 2 to 3.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thorough review and insightful comments. We hope the following response properly addresses your concerns. \n\n**Q1** Regarding ``...the theoretical contribution...'':\n\n**A1.** We would like to clarify that one of our paper’s main theoretical contributions is proposing necessary and sufficient local characterizations (Theorems 1–4) that account for latent variables—an aspect not found in Xie et al. (2024). To learn these local characterizations, we extend the method proposed by Xie et al., 2024 to learn $P_{MB^+(X)}$. Unlike their method, which is restricted to the target variable and its adjacent variables, we generalize it to apply to any two variables (see lines 280–285).\n\n**Q2** Regarding Proposition 1: \n\n**A2.** We would like to clarify that we have double-checked Theorem 1 in Xie et al. (2024) and confirmed its validity. A key reason is the important fact stated in Zhang (2008): given any DAG $\\mathcal{G}$ over $\\mathbf{V} = \\mathbf{O} \\cup \\mathbf{L}$—where $\\mathbf{O}$ denotes the set of observed variables, and $\\mathbf{L}$ denotes the set of latent variables—there is a MAG over $\\mathbf{O}$ alone such that for any disjoint $\\mathbf{X}, \\mathbf{Y}, \\mathbf{Z} \\subseteq \\mathbf{O}$, $\\mathbf{X}$ and $\\mathbf{Y}$ are d-separated by $\\mathbf{Z}$ in $\\mathcal{G}$ if and only if they are m-separated by $\\mathbf{Z}$ in the MAG. We also found similar conclusions in related works [see page 6 in Akbari et al., 2021; page 6 in Pellet & Elisseeff, 2008a]. \n\n- Zhang J. Causal Reasoning with Ancestral Graphs. JMLR, 2008.\n\n**Q3** Regarding Proposition 2:\n\n**A3.** Sorry for the confusion. We would like to clarify that if $\\mathbf{S}$ contains some colliders that open inactive paths, there will exist vertices belonging to $MB(X)$ similar to $A$ that can be added to $\\mathbf{S}$ to block these newly activated paths. According to your suggestion, we can define $\\mathbf{S}$  as the specific set $Pa^*(V_1)\\cup S_{X,V_2}$. Note that when we verify how $\\mathbf{S}$ blocks the three types of active paths, any collider variables introduced are also included in $\\mathbf{S}$. Here, all $A_i$ belong to $Pa^*(V_1)$ and $Pa^*(V_1)\\subseteq MB^+(X)$, which is observable. \n\nMore specifically, the process is as follows:\n\nIf there exists an active path of the form $V_1 \\leftarrow A_1\\dots V_2$, then $A_1\\in MB(X)$ can block that path. If $A_1$ is a collider on a path $p1:$ $V_1 \\dots * \\rightarrow A_1 \\leftarrow * \\dots V_2$, due to the graph being ancestral and $V_1 \\leftarrow A_1$, there must exist $V_1 \\leftarrow A_2$ on $p1$. Thus $A_2\\in MB(X)$ also blocks $p1$, and if $A_2$ is also a collider on a path, it falls back to the case where $A_1$ is a collider.\n\nIf there exists an active path of the form $V_1 \\leftrightarrow A_3 \\rightarrow\\dots V_2$, then $A_3\\in MB(X)$ can block that path. If $A_3$ is a collider on a path $p2:$ $V_1 \\dots*\\rightarrow A_3 \\leftarrow * \\dots V_2$, due to the graph being ancestral and $A_3 \\rightarrow\\dots V_2$, there must exist a $A_3 \\leftarrow* A_4$ on $p2$ . Thus $A_4\\in MB(X)$ also blocks $p2$, and if $A_4$ is also a collider on a path, it falls back to the case where $A_3$ or $A_1$ is a collider.\n\nIf there exists an active path of the form $V_1 \\rightarrow\\dots V_2$, then $S_{X,V_2}\\subseteq MB(X)$ can block that path due to $X*\\rightarrow V_1$ and $V_1 \\notin S_{X,V_2}$. Thus, the edge $V_1-V_2$ is true.\n\nWe will incorporate the above discussion to make the proof clearer.\n\n\n**Q4** Regarding Proposition 3:\n\n**A4.** First, if we do not stop, $M_L$ will indeed become an empty graph. We would like to clarify that lines 1055–1061 illustrate the following fact: by suitably removing leaf nodes, we can derive the local subgraph $M_L$ of interest from the global MAG $M$.\n\nNext, the reason two identical marginal distributions imply that continuing the algorithm will not further orient the undirected edges is that newly added leaf nodes do not affect the joint distribution of the existing variables in $M_L$. In other words, intuitively speaking, these leaf nodes do not introduce new directional information (e.g., V-structures) that could help further orient the undirected edges in the local structure.\n\n\n**Q5** Does PAG in this paper actually refer to maximally informative PAG? \n\n**A5.** Yes, PAG refers to the maximally informative PAG.", "claims_and_evidence": "I think the proofs of some theoretical claims are potentially problematic, please refer to Theoretical Claims.", "methods_and_evaluation_criteria": "The authors provide many theoretical claims to demonstrate the soundness of the proposed method, but I think the proofs of some theoretical claims are potentially problematic, please refer to Theoretical Claims.", "theoretical_claims": "Theoretical claims in Section 5 of this paper relies heavily on theorems in Xie et al. 2024. Therefore, I have also read Xie et al. 2024 carefully, but I found some potential problems detailed in the following.\n\n- Proposition 1 in this paper is exactly Theorem 1 in Xie et al. 2024. The proof of Theorem 1 in Xie et al. 2024 relies on Theorem 1 in Xie & Geng 2008. However, Theorem 1 in Xie & Geng 2008 presents a property of **d-separation** while Xie et al. 2024 directly replace d-separation to **m-separation** without any further clarification. I think this is a non-trivial modification. Specifically, the proof of Theorem 1 in Xie & Geng 2008 relies heavily on $An(u)$ and $An(v)$. While any variable in $An(u) \\cup An(v)$ exists in the underlying DAG, some variables in $An(u) \\cup An(v)$ may not exist in the underlying MAG because they may be latent variables.\n\n- The proof of Proposition 2 is confusing. Specifically, to prove $\\exists S$ s.t. $V_ 1 \\perp V_ 2 | S$, the authors argue that there are three types of **active** paths between $V_ 1$ and $V_ 2$, the first and the second can be blocked by $A$ while the third can be blocked by $S_ {X, V_ 2}$. This is not valid. First, the authors should not only consider active paths, because some inactive paths my become active given $S$ if $S$ contains some colliders. Second, the authors should prove all paths are blocked by a **unique** set rather than prove different paths are provided by different sets.\n\n- The proof of Proposition 3 is not clear (at least for me). First, according to the definition of $M_L$, it is arrived by iteratively removing leaf nodes, but when should we stop removing leaf nodes? If we don't stop, it seems that $M_L$ will be an empty graph. Second, I cannot understand why two marginal distributions equal each other ($P_{M_L}(O') = P_M(O')$) implies continuing this algorithm will not contribute to orienting the undirected edges.\n\nAlso, I have a minor question: In Zhang, 2008, PAG and maximally informative PAG are two different concepts. Does PAG in this paper actually refer to maximally informative PAG?", "experimental_designs_or_analyses": "I have checked the experimental setup and I have no major concern.", "relation_to_broader_scientific_literature": "The authors have discussed this in Impact Statement.", "essential_references_not_discussed": "There is no related work that is essential to understanding the (context for) key contributions of the paper, but are not currently cited/discussed in the paper.", "other_strengths_and_weaknesses": "# Strengths\n\n1. This paper investigates a novel problem: how to infer causal relations between two observed variables in the presence of hidden variables.\n\n2. This paper provides examples for their definitions and theorems, which improves readability substantially.\n\n# Weakness\n\n1. Some proofs are not very clear and rigorous, please refer to Theoretical Claim.\n\n2. This paper relies heavily on Xie et al., 2024. In fact, propositions 1, 2, 3 are all from Xie et al., 2024. This makes the theoretical contribution of this paper limited.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KzBfRdjK8k", "reviewer": "Reviewer_cKp3", "summary": "The authors propose novel local characterizations that are necessary and sufficient for various types of causal relationships between two variables and bypass the need for global structure learning. Leveraging these local insights, the authors develop efficient and fully localized algorithms that accurately identify causal relationships from observational data. The authors theoretically demonstrate the soundness and completeness of the approach. Extensive experiments on benchmark networks and two real-world datasets further validate the effectiveness and efficiency of the method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the time you dedicated to reviewing our paper, as well as your insightful and encouraging comments. Below, we provide our responses to your comments.\n\n\n**Q1.** ``I encourage the authors to compare against some of more recent baselines''\n\n**A1.** Thank you for the suggestion. Within the limited time, we have added a performance comparison with M3HC [1] and ICD [2] under the same settings as in our main paper. After learning the graph using ICD and M3HC, we applied Zhang's causal identification criteria (similar to RFCI-Zhang). As shown in the table below, LocICR outperforms other methods on all evaluation metrics and significantly reduces the number of CI tests compared to ICD-Zhang, which focuses on global structure learning with latent variables. Since M3HC is a hybrid method rather than fully CI-based, we did not compare the number of CI tests.\n\n|Network|Size|Algorithm|WP↑|WR↑|WF1↑|nTest↓|\n|-|-|-|-|-|-|-|\n|**MILDEW**|1000|LocICR|**0.91**|**0.91**|**0.91**|**588.45**|\n|||M3HC-Zhang|0.83|0.82|0.80|-|\n|||ICD-Zhang|0.80|0.76|0.70|2139.98|\n||3000|LocICR|**0.96**|**0.96**|**0.96**|**745.24**|\n|||M3HC-Zhang|0.88|0.85|0.83|-|\n|||ICD-Zhang|0.82|0.75|0.68|2857.56|\n||5000|LocICR|**0.98**|**0.98**|**0.98**|**821.37**|\n|||M3HC-Zhang|0.86|0.85|0.84|-|\n|||ICD-Zhang|0.80|0.78|0.73|3369.91|\n|**ALARM**|1000|LocICR|**0.86**|**0.82**|**0.83**|**454.30**|\n|||M3HC-Zhang|0.85|0.79|0.80|-|\n|||ICD-Zhang|0.77|0.54|0.54|1821.39|\n||3000|LocICR|**0.90**|**0.88**|**0.88**|**503.15**|\n|||M3HC-Zhang|0.85|0.79|0.80|-|\n|||ICD-Zhang|0.84|0.64|0.66|2231.66|\n||5000|LocICR|**0.97**|**0.97**|**0.97**|**535.32**|\n|||M3HC-Zhang|0.88|0.82|0.83|-|\n|||ICD-Zhang|0.80|0.66|0.67|2484.25|\n|**WIN95PTS**|1000|LocICR|**0.81**|**0.77**|**0.76**|**2382.69**|\n|||M3HC-Zhang|0.77|0.70|0.69|-|\n|||ICD-Zhang|0.68|0.56|0.51|5707.26|\n||3000|LocICR|**0.86**|**0.84**|**0.84**|**3031.96**|\n|||M3HC-Zhang|0.79|0.74|0.73|-|\n|||ICD-Zhang|0.68|0.60|0.57|7008.28|\n||5000|LocICR|**0.92**|**0.91**|**0.91**|**3302.28**|\n|||M3HC-Zhang|0.82|0.78|0.77|-|\n|||ICD-Zhang|0.69|0.61|0.57|7639.69|\n|**ANDES**|1000|LocICR|**0.83**|**0.79**|**0.77**|**3980.06**|\n|||M3HC-Zhang|0.76|0.72|0.67|-|\n|||ICD-Zhang|0.80|0.71|0.65|76004.21|\n||3000|LocICR|**0.85**|**0.80**|**0.78**|**4528.61**|\n|||M3HC-Zhang|0.80|0.76|0.73|-|\n|||ICD-Zhang|0.80|0.71|0.65|107370.50|\n||5000|LocICR|**0.89**|**0.87**|**0.86**|**4931.34**|\n|||M3HC-Zhang|0.84|0.79|0.77|-|\n|||ICD-Zhang|0.81|0.72|0.67|122166.73|\n||\n\n**Q2.** ``What prevents the authors from using the default setting instead of adopting a linear Gaussian parameterization?''\n\n**A2.** Following existing studies—specifically the setups of RFCI, LV-IDA, ITC, and IDA—we adopt a linear Gaussian parameterization, which is also used by M3HC and ICD. Additionally, we tested our method on the ALARM network with its default parameters in bnlearn, keeping other settings unchanged. The results below demonstrate that our method continues to perform well.\n\n|Size|WP↑|WR↑|WF1↑|nTest↓|\n|-|-|-|-|-|\n|1000|0.89|0.86|0.86|612.70|\n|3000|0.89|0.88|0.88|674.85|\n|5000|0.94|0.94|0.94|743.23|\n||\n\n**Q3.** ``A more thorough review of the state of the art in global causal discovery with latent confounders is missing.''\n\n**A3.** Thank you for the valuable suggestion. In the revised version, we have included a more comprehensive review of state-of-the-art methods in global causal discovery with latent confounders, highlighting recent advancements (e.g., [1–4]).\n\n[1] On scoring maximal ancestral graphs with the max–min hill climbing algorithm International Journal of Approximate Reasoning 2018\n\n[2] Iterative causal discovery in the possible presence of latent confounders and selection bias NeurIPS 2021\n\n[3] Differentiable causal discovery under unmeasured confounding AISTATS 2021\n\n[4] Greedy equivalence search in the presence of latent confounders UAI 2022", "claims_and_evidence": "Overall, the paper is quite dense and would have been better suited for submission to a journal with a longer review period. The judgments below are based on my (possibly incorrect) understanding of its contributions.\n\nThe claims in the paper seem to be well-executed:\n1. The paper clearly defines the problem of local causal structure learning with latent variables and establishes the limitations of previous approaches that assume causal sufficiency.\n2. The paper provides Theorems 1-4, and proves the correctness (though I did not check them in detail). \n3. The effectiveness of the proposed method is validated using synthetic benchmarks (MILDEW, ALARM, WIN95PTS, ANDES) and real-world gene expression data. However, several important baselines are missing.", "methods_and_evaluation_criteria": "1. The method section is well-organized and supplemented with visual diagrams, which are very helpful.\n2. However, some important baselines are missing. First, the global methods are somewhat outdated, as only PC/RFCI are considered. I encourage the authors to compare against some of more recent baselines, including [1-4]. Comparing a broader range of recent methods could provide a more comprehensive perspective on the proposed solution.\n3. The benchmark datasets appear to be unconventional. If I remember correctly, bnlearn already provides a conditional probability table for forward sampling. What prevents the authors from using the default setting instead of adopting a linear Gaussian parameterization?\n\n[1] On scoring maximal ancestral graphs with the max–min hill climbing algorithm International Journal of Approximate Reasoning 2018 \n\n[2] Iterative causal discovery in the possible presence of latent confounders and selection bias NeurIPS 2021\n\n[3] Differentiable causal discovery under unmeasured confounding AISTATS 2021\n\n[4] Greedy equivalence search in the presence of latent confounders UAI 2022", "theoretical_claims": "The theoretical claim looks good to me.", "experimental_designs_or_analyses": "See comment above.", "relation_to_broader_scientific_literature": "The paper extends an existing solution from Xie et al. and addresses an important missing piece in local causal discovery: understanding the causal relationships between variables under latent confounding without requiring global causal discovery.", "essential_references_not_discussed": "Please see my comments above on more recent global causal discovery methods.", "other_strengths_and_weaknesses": "Strengths:\n- The paper is easy to follow given the provided visual diagram.\n- I enjoyed reading the paper and the notations/terms are consistent with the literature.\n- The motivation is clear and the problem studied in the paper is surely important.\n\nWeaknesses:\n- Please see my comments regarding the evaluation.\n- A more thorough review of the state of the art in global causal discovery with latent confounders is missing. Most of the cited papers were published before 2020.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please consider address my concerns above during the rebuttal.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G2nasJXEQf", "reviewer": "Reviewer_FPtp", "summary": "The paper proposes both sufficient and necessary local characterizations for the invariant ancestor, invariant non-ancestor, and possible ancestor relationships, relying solely on local structure rather than the entire graph, even in the presence of latent variables. A novel algorithm, LocICR, leverages these local characterizations to efficiently identify causal relationships. The algorithm is proven to be sound and complete. Extensive experiments on benchmark networks and two real-world datasets demonstrate the effectiveness and efficiency of LocICR compared to existing methods.\n\n## update after rebuttal\nI've decided to raise my score from 3 to 4. The authors have provided clear and detailed responses to my concerns. For Q1, they clarified the learning process of the Markov blanket and incorporated this into the revised manuscript. For Q2, they explained the technical differences between their method and existing approaches like IDA and LV-IDA, emphasizing the advantages of their approach. For Q3, they elaborated on the distinction between the MMB-by-MMB algorithm and their Algorithm 1, highlighting the extension for identifying local characterizations. For Q4, they clarified why certain edges were not preserved, emphasizing the validation process using propositions. These thorough and thoughtful responses demonstrate a strong commitment to addressing my feedback and improving the quality of the manuscript, leading me to adjust my score upward.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are deeply grateful for the time you devoted to reviewing our manuscript. We appreciate that you think our proposal is a very solid paper. We hope that the following responses adequately address your concerns.\n\n**Q1.** ``Additional details regarding the learning of $\\mathcal{L}_{V_i}$ should be provided.''\n\n**A1.** Thanks for being thoughtful. Specifically, the learning process of $\\mathcal{L}_{V_i}$ first learns the Markov blanket of $V_i$, then performs skeleton learning based on the variables in $MB^{+}(V_i)$, and finally determines the V-structures. As you suggested, we have incorporated this clarification in the revised version.\n\n**Q2.** ``Detailed technical comparisons between the proposed and compared methods (e.g., IDA, LV-IDA) are not explicitly stated in the manuscript, which should be clarified.''\n\n**A2.** Thanks for the helpful suggestion. After a PAG (or CPDAG) is learned, LV-IDA（or IDA）enumerates all corresponding MAGs (or DAGs), identifies adjustment sets that satisfy the generalized back-door criterion, and estimates causal effects. If all these estimated effects are consistently nonzero (or consistently zero), an invariant ancestor (or non-ancestor) is determined. By contrast, our method does not require global graph learning or enumeration. We will include the above discussion.\n\n**Q3.** ``More details about what is the specific difference between the MMB-by-MMB algorithm and Algorithm 1.''\n\n**A3.** Thank you for raising this point. The MMB-by-MMB algorithm focuses solely on learning the local structure involving the target variable and its adjacent variables. To identify local characterizations (Theorems 1, 2, 3, 4), we extend the MMB-by-MMB algorithm to learn the $\\mathcal{P}_{MB^+(X)}$. As a result, we can identify causal relationships between any pair of variables, no longer limited to the target variable and its adjacent variables.\n\n\n**Q4** ``The edges between G and H, C and F in Fig. 7 (b) are correct, why aren't they preserved in $\\mathcal{P}$  ?''\n\n**A4.** Thank you for your careful observation. We would like to clarify that in each iteration, from the learned $\\mathcal{L}_{V_i}$, we utilize Propositions 1 and 2 to identify valid edges and colliders and store them in $\\mathcal{P}$. Since the edges between G and H, as well as C and F, are not validated by Propositions 1 and 2, we do not include them in $\\mathcal{P}$. In other words, we only retain the information that we can confirm to be correct.", "claims_and_evidence": "Yes, the claims made in the paper are well-supported by both theoretical proofs and empirical evaluations. The authors provide solid theoretical foundations for their local characterizations (Theorems 1, 2, 3, and 4) and establish the soundness and completeness of the LocICR algorithm (Theorem 6). A comparison with several state-of-the-art methods demonstrates that LocICR outperforms these techniques in terms of accuracy and computational efficiency. Furthermore, extensive experiments on two real-world datasets further validate the practical applicability and effectiveness of the proposed approach.", "methods_and_evaluation_criteria": "Yes, the proposed local characterizations of causal relationships and the LocICR algorithm are well-suited to address the problem at hand. The proposed method focuses on the local structures to identify causal relationships, which is a practical approach for large-scale datasets with latent variables.", "theoretical_claims": "Yes, I have checked the correctness of the proofs for the main theoretical claims made in the paper.", "experimental_designs_or_analyses": "Yes, I have reviewed the soundness of the experimental designs and analyses. Extensive experiments on both synthetic and real-world datasets demonstrate that LocICR outperforms existing methods in terms of accuracy and computational efficiency.", "relation_to_broader_scientific_literature": "The key contributions of the paper are clear, and I think represent valuable research for the causal discovery community and are novel relative to the broader scientific literature on causal discovery. Prior work such as (Fang et al., 2022), and (Xie et al., 2024) also focuses on locally identifying causal relationships, however, the method proposed by (Fang et al., 2022) requires the assumption of causal sufficiency, and the method proposed by (Xie et al., 2024) focuses on relationships between a target variable and its adjacent variables, without generalizing to arbitrary pairs of variables. The proposed LocICR algorithm addresses these limitations.", "essential_references_not_discussed": "No, the related works are thoroughly summarized and appropriately referenced.", "other_strengths_and_weaknesses": "**Strengths And Weaknesses**: \n- The paper provides a novel and efficient approach to causal discovery, addressing significant limitations of existing methods. \n- The theoretical contributions are solid, and the proposed algorithm is practical. \n- The paper is well-written, with clear explanations and examples.\n- Extensive experiments on both synthetic and real-world datasets show that the LocICR algorithm outperforms baselines significantly.\n- The appendix provides helpful clarifications.", "other_comments_or_suggestions": "- Additional details regarding the learning of $\\mathcal{L}_{V_i}$ should be provided.\n- Detailed technical comparisons between the proposed and compared methods (e.g., IDA, LV-IDA) are not explicitly stated in the manuscript, which should be clarified.", "questions_for_authors": "- More details about what is the specific difference between the MMB-by-MMB algorithm and Algorithm 1.\n- The edges between G and H, C and F in Fig. 7 (b) are correct, why aren't they preserved in $\\mathcal{P}$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces LocICR, a local method for identifying causal relationships between arbitrary pairs of variables in the presence of latent confounders. Unlike prior approaches that rely on learning a global causal structure such as a PAG or MAG, the proposed method operates entirely locally, leveraging new necessary and sufficient conditions for distinguishing invariant ancestor, non-ancestor, and possible ancestor relationships. The authors demonstrate soundness and completeness of their characterizations and provide an efficient algorithm that avoids the computational overhead of global methods.

The paper is well written and makes a strong theoretical and practical contribution. Several reviewers praised the clarity of the local characterizations and the extensive experimental evaluation, which covers both simulated benchmarks and real-world datasets. The authors also responded thoroughly during the rebuttal phase, addressing theoretical concerns and clarifying their distinctions from prior work. In particular, they provided detailed explanations of their proof dependencies, clarified differences with methods like IDA and LV-IDA, and included additional baseline comparisons with more recent global discovery methods (e.g., M3HC, ICD), strengthening the empirical case.

While one reviewer questioned the novelty of some of the technical components due to their relation to Xie et al. (2024), the authors convincingly showed how their generalization to arbitrary variable pairs and local characterizations under latent confounding go beyond previous work. Other concerns about unclear proofs and experimental setup were addressed to the satisfaction of the reviewers, with several increasing their scores post-rebuttal.

Overall, this is a rigorous and impactful paper that advances the state of local causal discovery, particularly in the challenging setting where latent variables are present. It offers a practical and theoretically grounded alternative to global structure learning and is well-suited for applications where local causal queries are more relevant than recovering the full graph. Therefore, I recommend acceptance.
Decision: Accept (spotlight poster)