Identifying Causal Effects Under Functional Dependencies
Authors: Yizuo Chen
Adnan Darwiche
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Identifiability
Causal Effects
Functional Dependencies
Primary area: causal_inference
TL;DR: The paper studies the identifiability of causal effects under functional dependencies.

Abstract: We study the identification of causal effects, motivated by two improvements to identifiability which can be attained if one knows that some variables in a causal graph are functionally determined by their parents (without needing to know the specific functions). First, an unidentifiable causal effect may become identifiable when certain variables are functional. Second, certain functional variables can be excluded from being observed without affecting the identifiability of a causal effect, which may significantly reduce the number of needed variables in observational data. Our results are largely based on an elimination procedure which removes functional variables from a causal graph while preserving key properties in the resulting causal graph, including the identifiability of causal effects.

Identifying Causal Effects Under Functional Dependencies
Yizuo Chen
Adnan Darwiche
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90024 yizuo. wwwwchhhe.nneeeeme edu
Department of Computer Science University of California, Los Angeles
Los Angeles, CA 90024 darwiche@cs, ucla. edu
Abstract
We study the identification causal effects, motivated by two improvements to identifiability which be attained if one knows that some variables in a causal graph are functionally determined by their parents (without needing to know the specific functions). First, unidentifiable causal effect may become identifiable when certain variables are functional. Second, certain functional variables can be excluded from being observed without affecting the identifiability of causal effect, which may significantly reduce the number of needed variables in observational data. Our results are largely based on an elimination procedure which removes functional variables from a causal graph while preserving key properties in the resulting causal graph, including the identifiability of causal effects.
Introduction
A causal effect measures the impact of an intervention some events of interest, and is exemplified by the question "what is the probability that patient would recover had they taken a drug?" This type of question, also known an interventional query, belongs the second rung of Pearl's causal hierarchy [ so it ultimately requires experimental studies if is to be estimated from data. However, is well known that such interventional queries can sometimes be answered based on observational queries (first rung of the causal hierarchy) which can be estimated from observational data. This becomes very significant when experimental studies are either not available, expensive to conduct, or would entail ethical concerns. Hence, a key question in causal inference asks when and how a causal effect can be estimated from available observational data assuming a causal graph provided 2].
More precisely, given a set of treatment variables X and a set of outcome variables Y, the causal effect PYx(Y), is the marginal probability Y when intervention sets the states of variables X to x. The problem of identifying a causal effect studies whether Prx (Y) can be uniquely determined from a causal graph and distribution Pr(V)
of on Y, denoted Pr(Y Pr(Y|do(x))
variables V
in the causal graph 22. where Pr(V) is typically estimated from observational data. The casual effect guaranteed be identifiable positivity assumptions); that is, if all such variables are observed. When some variables are hidden (unobserved), possible that different parameterizations of the causal graph will induce the same distribution Pr (V) but different values for the causal effect Prx (Y) which leads to unidentifiablility. In the past few decades, significant amount effort has been devoted to studying the identifiability of causal effects; see, e.g., 3 77 Some early works include the back-door criterion 8 and the front-doo criterion 2. These criteria are sound but incomplete as they may fail to identify certain causal effects that are indeed identifiable. Complete identification methods include the do-calculus (2). the identification algorithm 19] and the ID algorithm proposed in [0]. These methods require some positivity assumptions (constraints) the observational distribution Pr(V) and can derive
correspond to all variables the causal graph (with some
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

an identifying formula that computes the causal effect based on Pr(V) when the causal effect is identifiable. Some recent works take different approach by first estimating the parameters of a causal graph to obtain fully-specified causal model which is then used to estimate causal effects through inference [1.14. Further works focus on the efficiency of estimating causal effects from finite data [15 the general identifiability of causal effects from both observational and experimental data 19. and the causal effect identification with data collected from populations [20].
A recent line of work studies the impact of additional information on identifiability, beyond causal graphs and observational data. For example, 21 showed that certain unidentifiable causal effects can become identifiable given information about context confext-specific independence. Our work in this paper follows the same direction as we consider the problem of causal effect identification in the presence of a particular type of qualitative knowledge called functional dependencies (22]. We say there is functional dependency between a variable X and its parents P in the causal graph if the distribution Pr( X (P) is deterministic but we do not know the distribution itself (i.e., the specific values of Pr(x(p)) We also say in this case that variable X is functional. Previous works have shown that functional dependencies can be exploited to improve the efficiency of Bayesian network inference [23 13 26) We complement these works by showing that functional dependencies can also be exploited for identifiability. In particular, we show that some unidentifiable causal effects may become identifiable given such dependencies, propose techniques for testing identifiability in this context, and highlight other implications of such dependencies on the practice of identifiability.
Consider the following motivational example where we are interested in how the enforcement of speed limits may affect car accidents. The Driving Age (A) is functionally determined by Country (C); Driving Age and Country are causes of Speed (X); and Speed and Driving Age are causes of Accidents (Y). The DAG on the right captures the causal relations among these variables, where variable is circled to indicate it is functional. Suppose further that variables C, Y are observed. According to classical causal-effect identification methods (e.g.. do-calculus, ID algorithm), the causal effect of X on is unidentifiable in this case. However, if we take into account that variable A is a function of C, which restricts the class of distributions under consideration, then the causal effect of X on Y becomes identifiable. This exemplifies the improvements to identifiability pursued in this paper.
Consider a causal graph G and a distribution Pr(V) over the observed variables V in G. To check the identifiability of a causal effect, it is standard to first apply the projection operation in (2 28 which constructs another causal graph G' with V as its non-root variables, and follow by applying an identification algorithm to G' like the ID algorithm [IO]. This two-stage procedure, which we will call project-ID, is applicable only under some positivity constraints (assumptions) which preclude some events from having zero probability. Since such positivity constraints may contradict functional dependencies, we formulate the notion of constrained identifability which takes positivity constraints as input (in addition to the causal graph G and distribution Pr( Pr(V)). We also formulate the notion of functional identifiaiility which further takes functional dependencies as an input. This allows us to explicitly treat the interactions between positivity constraints and functional dependencies, which is needed for combining classical methods like project-ID with the results we present in this paper.
We start with some technical preliminaries in Section 2 We formally define positivity constraints and functional dependencies in Section where we also introduce the problems of constrained and functional identifiability. Section 4 introduces two primitive operations, functional elimination and functional projection, which are needed for later treatments. Sectionss5/prsentt our core results on functional identifiability and how they can be combined with existing identifiability algorithms. We finally close with concluding remarks in Section 6 Proofs of all results are included in the Appendix.
2 Technical Preliminaries
We consider discrete variables in this work. Single variables are denoted by uppercase letters (e.g.. X) and their states are denoted by lowercase letters (e.g., æ)). Sets of variables are denoted by bold uppercase letters (c.g., X) and their instantiations are denoted by bold lowercase letters (c.g.. x).
2

---

2.1 Causal Bayesian Networks and Interventions
Causal Bayesian network (CBN) pair FG,F) where G is a causal graph in the form of a directed acyclic graph (DAG), and F is a set of conditional probability tables (CPTs). We have one CPT for each variable X with parents in G, which specifies the conditional probability distributions Pr(X (P). This CPT will often be denoted by fx(X PX so fx (x,,p) E [0 for all instantiations for every instantiation p.
3, P, and En fx (x. p)
A CBN induces a joint distribution over its variables V which is exactly the product of its CPTs, i.c. Pr(V) = IIvvv fv. Applying a treatment do(x) to the joint distribution yields a new distribution called the interventional distribution, denoted Prx Prx(V). (V). One way compute the interventional distribution is to consider the mutilated CBN (G',F") that is constructed from the original CBN FG as follows: remove from G all edges that point variables in X, then replace the CPT in F for each X E X with a CPT (x) where fx (ar) = if x is consistent with x and /x (x) = 0 otherwise. Figure Ia depicts a causal graph G and Figure [b] depicts the mutilated causal graph G' under a treatment do(x1, 22). The interventional distribution Prx is the distribution induced by the mutilated CBN (G', F'), where PYx corresponds to the causal effect Pr( Y (x) also notated by Pr(Yx).
2.2 Identifying Causal Effects
A key question in causal inference is check whether a causal effect can be (uniquely) computed given the causal graph G and a distribution Pr(V) over a subset V of its variables. If the answer is yes, we say that the causal effect is identifiable given G and Pr(V). Otherwise, the causal effect is unidentifiable. Variables V are said to be observed and the remaining variables are said to be hidden, where Pr(V) is usually estimated from observational data. We start with the general definition of identifiability (not necessarily for causal effects) from [2] Ch. 3.2.4] with a slight rephrasing.
Definition 1 (Identifiability 12)). Let Q(M) be any computable quantity of a model M. We say that Q is identifiable in a class of models if. for any pairs of models M1 and M2 from this class, (M1) ((22) whenever Prar, (V) = Pr (V) where V are the observed variables.
In the context of causal effects, the problem of identifiability is to check whether every pair of fully-specified CBNs (M₃ and M2 in Definition D that induce the same distribution Pr(V) will also produce the same value for the causal effeect. Note that Definition I does not restrict the considered models M1 and M2 based on properties of the distributions Pr (V) and Pr (VV). However, in the literature identifying causal effects, it is quite common to only consider CBNs (models) that induce distributions which satisfy some positivity constraints, such as Pr(V)= > O. We will examine such constraints more carefully in Section Dl as they may contradict functional dependencies.
is well known that under some positivity constraints (e.g., Pr(V) > 0), the identifiability of causal effects can be efficiently tested using what we shall call the project-ID algorithm. Given causal graph G, project-IID first applies the projection operation in 227-29 to yield a new causal graph G" whose hidden variables are all roots and each has exactly two children. These properties needed by the ID algorithm (I0), which is then applied to G' to yield an identifying formula if the causal effect is identifiable or FAIL otherwise. Consider the causal effect Pr (2) in Figure la where the only hidden variable is the non-root variable B. We first project the causal graph G in Figure onto its observed variables to yield the causal graph G' in Figure Ic (all hidden variables in G' are auxiliary and roots). We then run the ID algorithm on G' which returns the following (sim- plified) identifying formula: Pizızz(y) (v) = Eoed Pr(c[a)) Pr(d[21,, x2) Exjag Pr(y)lf,, 2ng a, c, d) Pr(zzl=4, a, e) Pr(x',. a). Hence, the causal effect Przzzz (v) is identifiable and can be computed using the above formula. Moreover, all quantities in the formula can be obtained from the distribution Pr(A, C, D, X1, X2, Y) over observed variables, which can be estimated from observational data. More details on the projection operation and the ID algorithm can be found in Appendix A
3 Constrained and Functional Identifiability
As mentioned earlier, Definition I of identifiability 22] Ch. 3.2.4] does not restrict the pair of consid- ered models M, and M2. However, is common the literature on causal-effect identifiaiiiity to only consider CBNs with distributions Pr(V) that satisfy some positivity constraints. Strict positivity,
3

---

(a) causal graph
(b) mutilated
(c) projected
Figure I:
Example adapted from [30]. Hidden variables are circled. A bidirected edge X a----a Y is compact notation for X <- H - Y where H is an auxiliary hidden variable.
Pr(V)= > 0, is perhaps the mostly widely used constraint 9 22 2 That is, in Definition D we only consider CBNs M1 and .M2 which induce distributions Pr., and Prı, that satisfy Pr (V)
and PrM, (V) > O. Weaker, and somewhat intricate, positivity constraints were employed by the
ID algorithm in [0] as discussed in Appendix A but we will apply this algorithm only under strict
positivity to keep things simple. See also 31 for recent discussion of positivity constraints.
Positivity constraints motivated by two considerations: technical convenience, and the fact that most causal effects would be unidentifiable without some positivity constraints (more on this later). Given the multiplicity of positivity constraints considered in the literature, and given the subtle interaction between positivity constraints and functional dependencies (which are the main focus of this work), we next provide systematic treatment of identifiability under positivity constraints.
3.1 Positivity Constraints
We will first formalize the notion of a positivity constraint and then define the notion of constrained identifiability which takes a set of positivity constraints as input (in addition to the causal graph G and distribution Pr(V Pr(V))
Definition 2. A positivity constraint on Pr(V) is inequality of the form Pr(SIZ) > 0 where SC V, Z C V and S n Z = 0. That is, for all instantiations 2, Pr(z) > 0 then Pr(s, z) > O.
When Z = 0, the positivity constraint is defined on a marginal distribution, Pr(S) > 0. We may impose multiple positivity constraints on set of variables V. We will use Cv to denote the set of positivity constraints imposed on Pr(V and use vars(Cv) to denote all the variables mentioned by Cv. The weakest set positivity constraints is Cv = O (no positivity constraints in Definition [ and the strongest positivity constraint is Cv (Pr(V) > 0}.
We next provide definition of identifiability for the causal effect of treatments X on outcomes Y in which positivity constraints are an input to the identifiability problem. We call it constrained identifiability in contrast to the (unconstrained) identifiability of Definition
Definition 3. We call (G, V, V,Cy) identifiability tuple where G is causal graph (DAG), V is its set of observed variables, and Cy is a set of positivity constraints.
Definition 4 (Constrained Identifiability). Let (G, V,Cv) be an identifiability tuple. The causal effect of X on Y said to be identifiable with respect to (G, V,Cv) Pr (y) = (y) for any pair of distributions Pr and Pr² which are induced by G and that satisfy Pr PV)(V) = (V) and that also satisfy the positivity constraints Cy.
For simplicity, we say "identifiability" to mean "constrained identifiability" in the rest of paper.
We next show that without some positivity constraints, most causal effects would not be identifiable. We say that treatment X E X is first ancestor of some outcome Y E Y if X is ancestor of Y in causal graph G, and there exists a directed path from to Y that is not intercepted by X {X). A first ancestor must exist if some treatment variable is ancestor of some outcome variable.
Proposition 5. The casual effect of X Y is not identifiable wrt identifiability tuple (G,V,CK V,Cv) if some X E X is a first ancestor of some Y E ,, and Cv does not imply Pr(X)= > O.
We are incorporating positivity constraints directly into the definition of identifiability. This is different from the analysis in [32] which derives positivity constraints from particular run of the identification algorithm.

---

Hence, identifiability is not possible without some positivity constraints if at least one treatment variable an ancestor of some outcome variable (which is common). Consider the causal graph on the right where U is the only hidden variable. By Proposition 5 the causal effect of {X1, 1, X2) on (Y1, Y2) not identifiable if the considered distributions do not satisfy Pr( Pr(X2) O as X2 is a first ancestor of Y2.
As positivity constraints become stronger, more causal effects become identifiable since the set of considered models becomes smaller. Consider the causal graph on the right in which all variables are observed,
{Xx Y, 2}. Without positivity constraints, Cv = 0. the causal effect of X on Y is not identifiable. However, it becomes identifiable given strict positivity, Cv [Pr(XX, Y, Z) 0}, leading to the identifying formula (v) = Σ Pr(y|æ, 2) Pr(z). This causal effect is also identifiable under the weaker positivity constraint Cv = (Pr(X|Z) > 0) D which implies Pr(X)= > 0, strict positivity is not necessary for identifiability even though is typically assumed for this folklore result. This is an example where strict positivity may be assumed for technical convenience only as it may facilitate the application of some identifiability techniques like the do-calculus [2].
3.2 Functional Dependencies
variable in a causal graph is said to functionally depend on its parents P its distribution is deterministic: Pr(ar pp) E (0, for every instantiation x. p. Variable X is also said to be functional in this case. In this work, we assume qualitative functional dependencies: we do not know the distribution Pr(X (P), we only know that it is deterministic
The table on the right shows two variables B and C' that both have A as their parent. Variable C' is functional but variable B is not. The CPT for variable C' will be called a functional CPT in this case. Functional CPTs are also known as (causal) mechanisms and are expressed using structural equations in structural causal models (SCMs) B3 35) By definition, in SCM, every non-root variable is assumed to be functional (when noise variables are represented explicitly in the causal graph).
A
B
C
PE(BLA)
PrIC(A)
0
0
0
0.2
0 0.6
0.4
Qualitative functional dependencies are longstanding concept. For example, they are common in relational databases, see, e.g., [36 37], and their relevance to probabilistic reasoning had been brought up early in [22] Ch. 3]. One example of (qualitative) functional dependency is that different countries have different driving ages, so we know that "Driving Age" functionally depends on "Country" even though we may not know the specific driving age for each country. Another example that a letter grade for a class is functionally dependent on the student's weighted average even though we may not know the scheme for converting weighted average to letter grade.
In this work, we assume that we are given causal graph in which some variables W have been designated as functional. The presence of functional variables further restricts the set of distributions Pr that we consider when checking identifiability. This leads to more refined problem that we call functional identifubiiity ( (F-identifuubillty). which depends on four elements.
Definition We call (G, V.Cy, Cv. W) an F-identifiability tuple when G is a DAG, V is its set of observed variables, Cy is a set of positivity constraints, and W is a set of functional variables in G.
Definition (F-Identifiability). Let (G, V,Cv, W) be an F-identifiability tuple. The causal effect of X on Y is F-identifiable wri (G, V, V,Cv, W) ( = (x) for any pair of distributions Pr and Pr² which are induced by G, and that satisfy (V) = Pr?(V) and the positivity constraints Cv. and in which variables W functionally depend on their parents.
Both Cv and W represent constraints on the models (CBNs) we consider when checking identifiabil- ity, and these two types of constraints may contradict each other. We next define two notions that characterize some important interactions between positivity constraints and functional variables.
"This weaker positivity constraint is sufficient to make the identifying formuaa well-defined since Pr(ylæ,2) Pr(x) the formula is equal to zero when Pr(z) 0, and computable when Pr(z) > 0: that is, the conditional probability Pr(y]æ, 2) well-defined Pr(a]=)) >
We assume that root variables cannot be functional such variables can be removed from the causal graph.
5

---

Definition 8.
Let (G.V.Cv. W) be an F-identifiability tuple. Then Cv and W are consistent if there exists a parameterization for G which induces distribution satisfying Cy and in which W functionally depend on their parents. Moreover, Cv and W are separable if W O (Cr)(Cv) = 0.
If Cy is inconsistent with W then the set of distributions Pr considered in Definition 7 is empty and, hence, the causal effect is not well defined (and trivially identifiable according to Definition| 7 As such, one would usually want to ensure such consistency. Here are some examples of positivity constraints that are always consistent with set of functional variables W: positivity each treatment variable, i.e., (Pr(X) > 0, X E ) positivity on the set of non-functional treatments, all non-functional variables, i.e., {Pr(V) \ W) > 0}. All these
i... (Pr(X W) > 0}, positivity examples are special cases of the following condition. For a functional variable W E W, let Hw be variables that intercept all directed paths from non-functional variables W (such Hw may not be unique). If none of the positivity constraints in Cv mentions both W and Hw, then Cv W are guaranteed be consistent (see Proposition 25 in Appendix(C).
Separability is a stronger condition and intuitively implies that the positivity constraints will not rule out any possible functions for the variables in W. We need such a condition for one of the results we present later. Some examples of positivity constraints that are separable from W are (Pr(X) \ W) > 0} and (Pr(V) () > O} Studying the interactions between positivity constraints and functional variables, as we did in this section, will prove helpful later when utilizing existing identifiability algorithms (which require positivity constraints) for testing functional identifiability.
Functional Elimination and Projection
Our approach for testing identifiability under functional dependencies will be based on eliminating functional variables from the causal graph, which may be followed by invoking the project-ID algorithm on the resulting graph. This can be subtle though since the described process will not work for every functional variable as we discuss in the next section. Moreover, one needs to handle the interaction between positivity constraints and functional variables carefully. The first step though is to formalize the process of eliminating a functional variable and to study the associated guarantees.
Eliminating variables from probabilistic model is well studied operation, also known marginal- ization; see, e.g., [38/40). When eliminating variable X from a model that represents distribution Pr(Z), the goal is to obtain a model that represents the marginal distribution Pr(Y) = Σx Pr(ær, Y) where Y = Z \ {X}. Elimination can also be applied to a DAG G that represents conditional independencies I, leading to new DAG G' that represents independencies I' that are implied by I. In fact, the projection operation of (27 28 we discussed carlier can be understood in these terms. We next propose an operation that eliminates functional variables from DAG and that comes with stronger guarantees compared to earlier elimination operations as far as preserving independencies.
Definition 9.
The functional elimination of a variable X from a DAG G yields a new DAG attained by adding an edge from each parent of X to each child of X and then removing X from G
For convenience, we sometimes say "elimination" to mean "functional elimination" when the context is clear. From the viewpoint of independence relations, functional elimination is not sound if the climinated variable is not functional. In particular, the DAG G' that results from this elimination process may satisfy independencies (identified by d-separation) that do not hold in the original DAG G. As we show later, however, every independence implied by G' must be implied by G if the eliminated variable is functional. In the context of SCMs, functional elimination may be interpreted as replacing the eliminated variable X by its function in all structural equations that contain X. Functional elimination applies in broader contexts than SCMs though. Eliminating multiple functional variables in any order yields the same DAG (see Proposition 22 in Appendix B For example, eliminating variables {C, DJ from the DAG in Figure 2a yields the DAG in Figure 2c whether we use the order क = C, D or the order T2 = D,C.
Functional elimination preserves independencies that hold in the original DAG and which not preserved by other climination methods including projection as defined in [27] (8). These independencies are captured using the notion of D-separation 41 42 which is more refined than the
classical notion of d-separation 43 (uppercase D- versus lowercase d-). The original definition
'Appendix B extends this definition Causal Bayesian networks (i.e., updating both CPTss and causal graph).

---

B
H
H
DAG
(b) proj. (a) on A. B, G. H.
(c) ellmiiate C, from
(d) peoj. (c) on A. B. G.
Figure 2: Contrasting projection with functional projection. C, are functional. Hidden variables are circled.
of D-separation can be found in 42). We provide a simpler definition next, stated as Proposition 10 as the equivalence between the two definitions is not immediate.
Proposition 10. Let X, Y, Z be disjoint variable sets and W be set of functional variables in DAG G. Then and Y are D-separated by Z in (G, W) iff X and Y are d-separated by 'z' in where Z' is obtained as follows. Initially, Z' Z. Repeat the next step until Z' stops changing: add to Z' every variable in W whose parents are in Z'
To illustrate the difference between d d-separation and D-separation, consider again the DAG in Figure 2a and assume that variables C, D are functional. Variable G and are not d-separated by A but they are D-separated by A. That is, there are distributions which are induced by the DAG in Figure 2a and in which G' and I are not independent given A. However, G and / are independent given A in every induced distribution in which the variables C, D are functionally determined by their parents. Functional elimination preserves D-separation in the following sense.
Theorem 11. Consider a DAG G with functional variables W. Let G' be the result of functionally
eliminating variables W C W from G. For any disjoint sets X, Y. Z in G', X and Y are D-separated by Z (G, W) i and Y are D-separated by Z in (G', W W.Y W")
We now define the operation of functional projection which augments the original projection operation in [27 28 in the presence of functional dependencies.
Definition 12. Let G be DAG, V be its observed variables, and W be its hidden functional variables (W n V = 0). The functional projection of G on V is a DAG obtained by functionally eliminating variables W from G then projecting the resulting DAG on variables V.
We will now contrast functional projection and classical projection using the causal graph in Figure 2a assuming that the observed variables are V B, G, H, and the functional variables are (CC (C,D). Applying classical projection to this causal graph yields the causal graph in Figure 2b
W =
To apply functional projection, we first functionally eliminate C, D from Figure 2a which yields Figure 2c then project Figure 2c on variables V which yields the causal graph in Figure 2d So we
now need to contrast Figure 2b (classical projection) with Figure 2d (functional projection). The
latter is a strict subset of the former as it is missing two bidrected edges. One implication of this
that variables G and are not d-separated by A in Figure 2b because they are not d-separated in Figure 2a However, they are D-separated in Figure 2a hence they are d-separated in Figure 2d So functional projection yielded a DAG that exhibits more independencies. Again, this is because G and / are D D-separated by A in the original DAG, fact that is not visible to projection but is visible to (and exploitable by) functional projection.
An important corollary of functional projection is the following. Suppose all functional variables are hidden, then two observed variables are D-separated in the causal graph G iff they are d-separated in the cannctional-rooecctee d-separations in G' which allows us to feed G' into existing identifiability algorithms as we show later. This is a key enabler of some results we shall present next on testing functional identifiability.
graph G'. This shows that such D-separations in G appear as classical
5 Causal Identification with Functional Dependencies
Consider the causal graph G Figure 3a and let V = (A, X, Y] be its observed variables. According to Definitin 4 of identifiability, the causal effect of X on Y is not identifiable with respect to (G, V,Cv) where Cv (Pr(A, (A, X, Y) 0}. We can show this by projecting the
(a) DAG
(b) projection
Figure 3: is functional.
7

---

(a) causal graph
(b) proj. of (a)
(c) F-proj. of (a)
(d) F-elim. F
(o) F-elim. B
Figure 4: Variables B, C, F, are observed. Variables D, E are functional (and hidden).
causal graph G on the observed variables V. which yields the causal graph G' in Figure 3b then applying the ID algorithm G" which returns FAIL. Suppose now that the hidden variable B is known to be functional. According to Definition 7 of F-identifiability, this additional knowledge reduces the number of considered models so it actually renders the causal effect identifiable the identifying formula is Pr, (v) Eg Pr(a) Pr(y) (t, x) as we show later. Hence, an unidentifiable causal effect became identifiable in light of knowledge that some variable is functional even without knowing the structural equations for this variable.
The question now is: How do we algorithmically test F-identifiallity? We will propose two techniques for this purpose, the first of which is geared towards exploiting existing algorithms for classical identifiability. This technique is based on eliminating functional variables from the causal graph while preserving F-identifiability, with the goal of getting to a point where F-identifiability becomes equivalent classical identifiability. If we reach this point, we can use existing algorithms for classical identifiability. like the ID algorithm, to test F-identifiability. This can be subtle though since hidden functional variables behave differently from observed ones. We start with the following result.
Theorem 13. Let (G, V C,Cv, W) be an F-identifiability tuple. If G' is the result of functionally eliminating the hidden functional variables (W \ V) from G, then the causal effect of X on Y is F-identifiable wrt (G, V,C,, W) iff it is F-identifiable wrt (G', N,Cv, V..VWW
An immediate corollary of this theorem is that if all functional variables are hidden, then we can reduce the question of F-identifiability to a question of identifiability since V Vn W = 0 so F-identifiability wrt (G', V,Cv, V n W = 0) collapses into identifiability wrt (G', V,Cv).
Corollary 14. Let (G, (G,VCCo V, W) be an F-identifiability tuple where Cv (Pr(V) > 0} and W are all hidden. G' the result of functionally projecting G on variables V, then the causal effect of X on Y is F-identifiable wrt (G, V, V,Cv, W) iff it is identifiable wrt (G, Vv))
This corollary suggests a method for using the ID algorithm, which is popular for testing identifiability, to establish F-identifiability by coupling ID with functional projection instead of classical projection. Consider the causal graph G in Figure 4a with observed variables V = { {A, B, C, F, XY The causal effect of X on Y is not identifiable under Pr(V)= > projecting G on observed variables V yields the causal graph G' in Figure 4b and the ID algorithm produces FAIL on G'. Suppose now that the hidden variables {D, E} are functional. To test whether the causal effect is F-identifiable using Corollary 14. we functionally project G on the observed variables V which yields the causal graph G" in Figure 4c Applying the ID algorithm to G" produces the following identifying formula: aear Pr(yle a, b,c, a.) Pr(a, b, x²) so Pr, Pr) is F-identifiable.
(v) = Σos Pr[j
We stress again that Corollary 14fand the corresponding F-identifiability algorithm apply only when all functional variables are hidden. We now treat the case when some of the functional variables are observed. The subtlety here is that, unlike hidden functional variables, eliminating an observed functional variable does not always preserve F-identifiability. However, the following result identifies conditions that guarantees the preservation of F-identifiability in this case. If all observed functional variables satisfy these conditions, then we can again reduce F-identifiability into identifiability can exploit existing methods for identifiability like the ID algorithm and do-calculus.
Theorem 15. Let (G, V Cv, W) be an F-identiiabiilit tuple. Let Z be a set of observed functional variables that are neither treatments nor outcomes, are separable from Cv, and that have observed
'ee are requiring the positivity constraint Pr(V)= > 0 as the projection operation in (8) requires it. If the projection operation only requires weaker positivity constraint Cy. can replace Cv by CV in Corollary 14
8

---

parents, If G' is the result of functionally eliminating variables Z from G. then the causal effect of X on Y is F-identifabll wrt (G, V. Cv,, W) iff it F-identifiable wTt (G', Cv. W Z).
We now have the following important corollary of Theorems 13 & 13 which subsumes Corollary 14
Corollary 16. Let (G, V. V.Cv, W) be an F-identifiability tuple where Cy = {Pr(V)) W) > 0} and every variable in W V satisfies the conditions of Theorem 75| If G' is the result of functionally
projecting G on V \ W. then the causal effect of X on Y is F-identifiable wet (G, V V.Cv, W) iff it
identifiable wrt (G', V W.Cv).
Consider again the causal effect of X on Y in graph G of Figure 4a with observed variables V= (A, B, C, F, X, Y). Suppose now that the observed variable F is also functional (in addition to the hidden functional variables D, F)) and assume Pr( A, B, C,,, > O. Using Corollary 16 functionally project G A, B, C, X,Y to yield the causal graph G' in Figure 4d which reduces F-identifiabilityy on G' to classical identifiability on G". Since strict positivity holds in G', we can apply any existing identifiability algorithm and conclude that the causal effect is not identifiable. For another scenario, suppose that the observed variable B (instead of F)) is functional and we have Pr(A, C, F. X, > O. Again, using Corollary 16, we functionally project G onto A, C, F. X, to yield the causal graph G" in Figure which reduces F-identifiability on G to classical identifiability on G". If we apply the ID algorithm to G" we get the identifying formula (which we denote as Eq. 1): (v) = Eag Pr(fla, x) Eex Pr(yla, a, c, f. f'²) Pr(a, c, c,z'). In both scenarios above, we were able to test F-identifiability using an existing algorithm for identifiability.
Corollary 16 (and Theorem 15) has yet another key application: it can help pinpoint observations that are not essential for identifiability. To illustrate, consider the second scenario above where the observed variable B is functional in the causal graph G of Figure 4a The fact that Corollary [6 allowed us to eliminate variable B from G implies that observing this variable is not needed for rendering the causal effect F-identifiable and, hence, is not needed for computing the causal effect. This can be seen by examining the identifying formula (Eq. 1) which does not contain variable B. This application of Corollary T6] be quite significant in practice, especially when some variables are expensive to measure (observe), or when they may raise privacy concerns; see, c.g., [45 46).
Theorems 13 & 15
more far-reaching than what the above discussion may suggest. In particular, even if we cannol eliminate every (observed) functional variable using these theorems, we may still be able to reduce F-identifiability to identifiability due to the following result.
Theorem 17. Let (G, V, C,Cv, W) be an F-identifiability tuple. If every functional variable has at least one hidden parent, then causal effect of X on Y is F-identifiable wrt (G, V,Cv, W) iff is identifiable wrt (G, V.Cv).
That is, if we still have functional variables in the causal graph after applying Theorems 13 & 15 and if each such variable has at least one hidden parent, then F-identifiability is equivalent to identinability.
The method we presented thus far for testing F-identifiability is based eliminating functional variables from the causal graph, followed by applying existing tools for causal effect identification such the project-IID algorithm and the do-calculus. This F-identifiability method is complete if every observed functional variable either satisfies the conditions of Theorem [5] or has at least one hidden parent that not functional. This elimination- based method not only tests identifiability but also provides an identifying formula if the causal effect turns out to be identifiable.
We next present another technique for reducing F-identifiability to identifiability. This method is more general and much more direct than the previous one, but it does not allow us to fully exploit some existing tools like the ID algorithm due to the positivity assumptions they make. The new method is based on pretending that some of the hidden functional variables are actually observed and inspired by Proposition 10 which reduces D-separation to d-separation using similar technique.
Theorem 18. Let (G, V, VyCv, W) be an F F-identifiability tuple where Cy= (Pr(X) > O. E X}. A causal effect of X on Y is F-idenifiable wrt (G, V. ,Cv, W) iff it is identifiable wrt (G, Cv. V") where V is obtained as follows. Initially, V = V. Repeat until V stops changing: add to V functional variable from W if its parents are in V'.
Consider the causal effect of X on Y in graph G of Figure 4a and suppose the observed variables are V {A, B, C,X, X, Y). the functional variables are { {D, F., F} and we have Pr(X)= > 0. By
Theorem 18 the causal effect of X on Y is F-identifiable iff it is identifiable in G while pretending

---

are all observed. In this case, the casual effect is not that variables V = EA,
identifiable but we cannot obtain this answer by applying an identifiability algorithm that requires positivity constraints which are stronger than Pr(X) > 0. If we have stronger positivity constraints that imply Pr(X) > 0, X & X, then only the if part Theorem 18 will hold, assuming Cv and W are consistent. That is, confirming identifiability wrt (G, Cv. V'y y will confirm F-identifiability wrt (G, V, Cv W) but identifiability is not confirmed then F-identifiability may still hold. This suggests that, to fully exploit the power of Theorem 18 one would need new class of identifiability algorithms that can operate under the weakest possible positivity constraints.
6 Conclusion
We studied the identification causal effects the presence a particular type of knowledge called functional dependencies. This augments earlier works that considered other types of knowledge such as context-speciing independence. Our contributions include formalizing the notion of functional identifiability; the introduction of an operation for climinating functional variables from causal graph that comes with stronger guarantees compared to carlier climination methods; and the employment (under some conditions) of existing algorithms, such the ID algorithm, for testing functional identifiability and for obtaining identifying formulas. We also provided a complete reduction of functional identifiability to classical identifiability under very weak positivity constraints, and showed how our results can be used to reduce the number of variables needed in observational data.
Acknowledgements
We wish to thank Scott Mueller, Jin Tian, and anonymous reviewers for providing valuable feed- back earlier versions of this paper. This work has been partially supported by ONR grant N000142212501.
References
[1] Judea Pearl and Dana Mackenzie. The Book of Why: The New Science of Cause and Effect. Basic Books, 2018
[2] Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, second edition, 2009.
[3] Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669-688, 1995. ISSN 00063444.
[4] Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search, Second Edition. Adaptive computation and machine learning. MIT Press, 2000. ISBN 978-0-262- 19440-2.
[5] Guido W. Imbens and Donald Rubin. Causal Inference for Statistics, Social, and Biomedical Sciences: An Introduction. Cambridge University Press, 2015.
[6] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of Causal Inference: Foundations and Learning Algorithms. MIT Press, 2017.
[7] Miguel A. Hernán and James M. Robins. Causal Inference: What If. Boca Raton: Chapman Hall/CRC, 2020.
[8] Judea Pearl. [bayesian analysis in expert systems]: Comment: Graphical models, causality and intervention. Statistical Science, 8(3):266-269, 1993.
[9] Yimin Huang and Marco Valtorta. Identifiability in causal bayesian networks: A sound and complete algorithm. In AAAI, pages 1149-1154, AAAI Press, 2006.
[10] Ilya Shpitser and Judea Pearl. Identification of joint interventional distributions in recursive semi-markovian causal models. In AAAI, pages 1219-1226. AAAI Press, 2006.
10

---

[11] Marco Zaffalon, Alessandro Antonucci, and Rafael Cabañas. Causal Expectation Maximisation. In WHY Workshop. NeurIPS, 2021. doi: 1048500ARKXV.200.00222 https///arxivoor/abs2001 1.02912.
[12] Marco Zaffalon, Alessandro Antonucci, Rafael Cabañas, and David Huber. Approximating coun- terfactual bounds while fusing observational, biased and randomised data sources. International Journal of Approximate Reasoning, 162: 162:109023, 2023.
[13] Adnan Darwiche. Causal inference with tractable circuits. In WHY Workshop, NeurIPS, 2021. https//arriv.og//bb22222..222.23
[14] David Huber, Yizuo Chen, Alessandro Antonucci, Adnan Darwiche, and Marco Zaf- falon. Tractable bounding of counterfactual queries by knowledge compilation. Sixth Workshop Tractable Probubilistic Modeling @ UAI 2023, 2023. URL https://
phattalle-prbabblistit----m higgggigiitiiimddddgiggigttibbbb github..h.............. httppp222//pppprrr
[15] Yonghan Jung, Jin Tian, and Elias Bareinboim. Estimating causal effects using weighting-base estimators. In AAAI, pages 10186-10193, AAAI Press, 2020.
[16] Yonghan Jung, Jin Tian, and Elias Bareinboim. Learning causal effects via weighted empirical risk minimization. In NewrlPS, 2020.
[17] Yonghan Jung, Jin Tian, and Elias Bareinboim. Estimating identifiable causal effects through double machine learning. In AAAI, pages 12113-12122. AAAI Press, 2021.
[18] Yonghan Jung, Jin Tian, and Elias Bareinboim. Estimating identifiable causal effects markov equivalence class through double machine learning. ICMI., volume 139 of Proceedings of Machine Learning Research, pages 5168-5179, PMLR, 2021.
[19] Sanghack Lee, Juan D. Correa, and Elias Bareinboim. Identifiability from a combination of observations and experiments. In AAAI, pages 13677-13680. AAAI Press, 2020.
[20] Amir Mohammad Abouei. Ehsan Mokhtarian, and Negar Kiyavash. s-id: Causal effect identifi- cation in a sub-population. In AAAI, pages 20302-203 10. AAAI Press, 2024.
[21] Santtu Tikka, Antti Hyttinen, and Juha Karvanen. Identifying causal effects via context-specific independence relations. In NeurlPS, pages 2800-2810, 2019.
[22] Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.
[23] Adnan Darwiche. An advance on variable elimination with applications to tensor-based com- putation. In ECAI, volume 325 of Frontiers in Artificial Intelligence and Applications, pages 2559-2568. IOS Press, 2020.
[24] Yizuo Chen, Arthur Choi, and Adnan Darwiche. Supervised learning with background knowl- edge. In 10th International Conference Probabilistic Graphical Models (PGM), 2020.
[25] Yizuo Chen and Adnan Darwiche. On the definition and computation of causal treewidth. In UAI, Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, 2022.
[26] Yunqiu Han, Yizuo Chen, and Adnan Darwiche. On the complexity of counterfactual reasoning. In IJCAL, pages 5676-5684. ijcai.org, 2023.
[27] Thomas S. Verma. Graphical aspects of causal models. Technical Report, R-191, 1993.
[28] Jin Tian and Judea Pearl. On the testable implications of causal models with hidden variables. In UAI, pages 519-527. Morgan Kaufmann, 2002.
[29] Jin Tian and Judea Pearl. On the identification of causal effects. Technical Report, R-290-I. 2003.
[30] Manabu Kuroki and Masami Miyakawa. Identifiability criteria for causal effects of joint interventions. Journal of the Japan Statistical Society, 1952):105-117, 1999.
11

---

[31] Yaroslav Kivva, Ehsan Mokhtarian, Jalal Etesami, and Negar Kiyavash. Revisiting the general identifiability problem. In UAL, volume 180 of Proceedings of Machine Learning Research, pages 1022-1030. PMLR, 2022.
[32] Inwoo Hwang, Yesong Choe, Yeahoon Kwon, and Sanghack Lee. On positivity condition for causal inference. In ICML. OpenReview.net, 2024.
[33] Alexander Balke and Judea Pearl. Counterfactuals and policy analysis in structural models. In UAI, pages 1 11-18. Morgan Kaufmann, 1995.
[34] David Galles and Judea Pearl. An axiomatic characterization of causal counterfactuals. Founda- tions of Science, 3(1):151-182, 1998.
[35] Joseph Y. Halpern. Axiomatizing causal reasoning. Journal of Artificial Intelligence Research, 12:317-337, 2000.
[36] Terry A. Halpin and Tony Morgan. Information modeling and relational databuses (2. ed.). Morgan Kaufmann, 2008.
[37] J. J. Date. Database Design and Relational Theory- Normal Forms and All That Jazz. O' O'Reilly, 2012.
[38] Nevin L. Zhang and David L. Poole. Exploiting causal independence in bayesian network inference. J. Artif. Intell. Res., 5:301-328, 1996.
[39] Rina Dechter. Bucket elimination: unifying framework for probabilistic inference. In Proceedings of the Twelfth Annual Conference on Uncertainty in Artificial Intelligence (UAI), pages 211-219, 1996.
[40] Adnan Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2009.
[41] Dan Geiger and Judea Pearl. On the logic of causal models. In UAI, pages 3-14. North-Holland 1988.
[42] Dan Geiger, Thomas Verma, and Judea Pearl. Identifying independence in bayesian networks. Networks, 20(5):507-534, 1990.
[43] Judea Pearl. Fusion, propagation, and structuring in belief networks. Artif. Intell., 29(3): 241-288, 1986.
[44] Thomas Verma and Judea Pearl. Causal networks: semantics and expressiveness. In UAI, pages 69-78. North-Holland, 1988.
[45] Santtu Tikka and Juha Karvanen. Enhancing identification of causal effects by pruning. J. Mach. Learn. Res., 18: 19::11199::23, 2017.
[46] Benito van der Zander, Maciej Liskiewicz, and Johannes Textor. Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework. Artif. Intell., 270:1-40, 2019.
[47] llya Shpitser and Judea Pearl. Complete identification methods for the causal hierarchy. Mach. Learn. Res., 9:1941-1979, 2008
[48] Adnan Darwiche. An advance variable climination with applications to tensor-based com- putation. In Proceedings of the 24th European Conference on Artificial Intelligence (ECAI), 2020.
[49] Adnan Darwiche. A differential approach to inference in Bayesian networks. J. ACM, 280-305, 2003.
12

---

A More On Projection and ID Algorithm
As mentioned in the main paper, the project-ID algorithm involves two steps: the projection operation and the ID algorithm. We will review more technical details of each step in this section.
A.1 Projection
The projection [27/29) of onto V constructs a new DAG G' over variables V as follows. Initially, DAG G" contains variables V but edges. Then for every pair of variables X, Y E V. an edge is added from X to Y to G' if X is a parent of in G, or there exists a directed path from X to Y in G' such that none of the internal nodes the path is in V. A bidirected edge X +----- Y is further added between every pair of variables X and Y in G' if there exists a divergent pati between X and Y in G such that none of the internal nodes the path is in V. For example, the projection of the DAG in Figure la onto D, D.
X2, Y yields Figure Ic A bidirected edge X <----+ + Y is compact notation for X < H + Y where H is an auxiliary hidden variable. Hence, the projected DAG in Figure Tc can be interpreted as a classical DAG but with additional, hidden root variables.
The projection operation is guaranteed to produce a DAG G' in which hidden variables are all roots and each has exactly two children. Graphs that satisfy this property are called semi-Markovian and can be fed as inputs to the ID algorithm for testing identifiability [IO). Moreover, projection preserves some properties of G. such as d-separation [27] among V, which guarantees that identifiabilty is preserved when working with G' instead of G (28
A.2 ID Algorithm
After obtaining a projected causal graph, we can apply the ID algorithm for identifying causal effects [T0 47 The algorithm returns either identifying formula if the causal effect is identifiable or FAIL otherwise. The algorithm is sound since each line of the algorithm can be proved with basic probability rules and do-calculus. The algorithm is also complete since causal graph must contain a hedge, a graphical structure that induces the unidentifiability. if the algorithm returns FAIL. The algorithm, however, is only sound and complete under certain positivity constraints, which are weaker but more subtle than strict positivity (Pr(V)= > 0).
The positivity constraints required by ID can be summarized as follows (X are the treatment variables): (I) Pr(X(P) > O where considered by the ID algorithm. The second constraint depends algorithm and can be interpreted as follows. First, if the ID algorithm returns FAIL then the causal effect is not identifiable even under the strict positivity constraint Pr(V) > O. However, if the ID algorithm returns "identifiable" then the causal effect is identifiable under the above constraints which are now well defined given particular run of the ID algorithm. We illustrate with an example next.
Parents(X) \ X, and (2) Pr(Z) > 0 for all quantities Pr(S|Z)
particular run of the ID
Consider the causal graph on the right which contains observed variables {A, B, C,X, )). Suppose are interested in the causal effect of X on Y. applying the ID algorithm returns the following identifying formula: (r, Pr(caa b, b, Pr(yla, b, Pr(a, 6, z²). The positivity constraint ex-
U
U
U
tracted from this run of the algorithm is Pr(a, b, c, x) > 0 for all a, b, c, x. That is, we can only safely declare the causal effect identifiable based on the ID algorithm if this positivity constraint is satisfied.
B Functional Elimination for CBNs
The functional elimination in Definition removes functional variables from DAG G and yields another DAG G' on the remaining variables. We have shown in the main paper that the functional elimination preserves the D-separations. Here we extend the notion of functional elimination to Causal Bayesian networks (CBNs) which contain not only a causal graph (DAG) but also CPTs. We show that the (extended) functional climination preserves the marginal distribution variables. That is, given any CBN with the causal graph G, we can construct another CBN with the causal graph G' such that the two CBNs induce a same distribution the variables in G', where G' is the result of eliminating functional variables from G. Moreover, we show that the functional
the remaining
A divergent path between X and Y is a path in the form of X t....
+Y
13

---

elimination operation further preserves the causal effects, which makes it applicable to the causal identification. This extended version of functional climination and the corresponding results will be used for the proofs in Appendix C
Recall that CBN (G contains causal graph G and set of CPTs F. We first extend the definition of functional elimination (Definition 9 from DAGs to CBNs.
Definition 19. The functional elimination of a functional variable X from a CBN (G.F) yields another CBN FG) obtained as follows. The DAG G' is obtained from G by Definition 9 For each child C of X, its CPT in F is (Ex fxfc) where fx, fc are the corresponding CPTs in F.
We first show that the new CPTs produced by Definition 19 are well-defined.
Proposition 20. Let fx and fy be the CPTs variables X and Y in a CBN, then (xx fxfr is a valid CPT for Y.
The next proposition shows that functional elimination preserves the functional dependencies. Proposition 21. Let M' be the CBN resulting from functionally eliminating a functional variable from a CBN M. Then each variable (from M') functional M' if is functional in M.
The next theorem shows that the order of functional elimination does not matter.
Proposition 22. Let M be CBN and k1, T2 be two variable orders over set of functional variables W. Then functionally eliminating W from M according to лı and TT yield the same CBN.
The next result shows that eliminating functional variables preserves the marginal distribution.
Theorem 23, Consider a CBN M which induces Pr. Let M' be the result of functionally eliminating set of functional variables W from M which induces Pr'. Then Pr' Σw Pr.
One key property of functional elimination is that it preserves the interventional distribution over the remaining variables. This property allows to eliminate functional variables from causal graph and estimate the causal effects the resulting graph.
Theorem 24. Let M' be the CBN over variables V resulting from functionally eliminating a set of functional variables W from a CBN M. Then M' and M attain the same PIx(V) for any X C V.
C Proofs
The proofs of the results will be ordered slightly different from the order they appear in the main body of the paper.
Proof of Proposition 5
Proof. Our goal is construct two different parameterizations F and JF2 that induce the same Pr(V) but different Prx(v). This is done by first creating a parameterization F which contains strictly positive CPTs for all variables, and then constructing F and J based on F.
Let P be the directed path from X = Xx to Y, denoted X + Z + ... + Y which does not contain any treatment variables other than X. Let Px x be the parents of X in G. For each node M on the path, let P M be the parents of M except for the parent that lies on P. Moreover, for each variable M on P, we will only modify the conditional probability for single state m of M, where xx E x is the treated state of X. Let be an arbitrarily small constant (close to 0), we next show the modifications for the CPTs in F
10 (xlpp))
if = x² otherwise
11/(1x1-1) -1),
1-c,
if = x² , 2* if = x² # x² if + x²
c/(1Z] - 1),
(=12,
E,
(1 <)/(1Z] 1).
if 2
14

---

For every variable T Φ {x, } which has parent Q on the path P. we assign
1-6,
if q q' t* if = ,', 1"
</(IT] 1);
(tlg,
c
q + t²=
(1 (1-6) (1(7//111111 -
i # 1" 1
We assign the same CPTs for X and all variables & (X, ] } but a different CPT for Z in F2.
6, (1 (1-))/(1Z) - 1).
if = ===="; if = #== if x² if x x ,
(z(z,
C (1 (1-6)/(12) - 1).
The two parameterizations F and F² induce the same Pr(V) where Pr(v) 0f x² and Pr(v) > 0 otherwise. We next show that the parameterization satisfies each positivity constraint Pr(S]Z) as long as it does not imply Pr(X) > O. We first show that X implies Pr(X)= > This is because Pr(S) = Ex Pr(S|z) Pr(z) and there must exist some instantiation where Pr(z) > 0 and Pr(S]z) > 0 by constraint. This implies Pr(S) > and therefore Pr(X) > 0. Hence, Cv does not contain such constraint Pr(S Z) where X E S. Suppose X E Z, then Pr(z) > 0 if and only x* $ z. Moreover, since Pr(v) > whenever x² $ v. it is guaranteed that Pr(S, 2) > when Pr(z) 0, which implies Pr(SIZ) Z O. Finally, suppose X (S U Z), then Pr(S, Z) E.Pr(S Pr(S, Z, 2²) > O. Hence, the positivity constraint is satisfied by both parameterizations. By construction, Pr and Pr² induce different values for the causal effect (r)(y) since the probability of Y = under the treatment do(X x²) will be different for the two parameterizations.
Proposition 25. Let G be causal graph and V be its observed variables. A set of functional variables W is consistent with positivity constraints Cy if no single constraint in Cy mentions both W E W and a Hw that intercepts all directed paths from non-functional variables W.
Proof of Proposition 25 We construct a parameterization F and show that the distribution Pr induced by F satisfies the Cv, which ensures the consistency. The states of each variable V are represented in the form of (sy.PI.... pi...., Pm)) where sv and p: (i E (1..... m)}) are all binary indicator (0 or 1). Specifically, each of the p; corresponds to a "functional descendant paths" of V defined follows: functional descendant path of V is a directed path that starts with V and that all variables on the path (excluding V) are functional. Suppose V does not have any functional descendant paths, then the states of V is simply represented as (sv).
We next show how to assign CPTs for each variable in the causal graph G' based whether the variable functional. For each non- conffunctional variable, we assign a uniform distribution. For each functional variable W whose parents are Ti,..., In and whose functional descendant paths are PI PI..... Pmn we assign the CPT fw as follows:
sw + P T
WI) 1 ... +..0 Th Pind(T..W)
Pi + p.. 1 ... + Pr
Pm + Pi,
+
+ phr
where [T,, W) denotes the index assigned to the path {(T,, W)} (which contains single edge) in the state of T and p?, denotes the indicator in the state of T, for the functional descendant path p' that contains the functional descendant path PJ. i... P' [[T,, W)}UP;
For simplicity, we call the set of variables Hw that satisfies the condition in the proposition "functional ancestor set" of W. We show that Pr Z) > O for each positivity constraint in the form of Pr(S) > Let W C S U Z be subset of functional variables. Since any functional ancestor set of W for each W E W, it follows that there exist directed paths from set of non-functional variables Aly to W that are unblocked by M U Z (W) and contain only functional variables (excluding Aly) ). We can further assume that AWy is chosen such that the set
does not contain
15

---

Aw = M forms valid functional ancestor set for W. We next show that for any state w of W and instantiation m of M, there exists at least one instantiation of Aly such that Pr(w, m, a)
Let pW denote the set of all directed paths from Aw to W that do not contain Aw (except for the first node on the path). Let Pl S PW be the paths that start with a variable in M, and P C PW be other paths that start with variable in Aly. Moreover, for any path P. let pathval (P) be the binary indicator (e.g.. P1) for P in the state of P(0) (first variable P). Since the value assignments for pathval(P) are independent for different P's, we can always find some instantiation a E Aw such that the following equality holds given w and m:
pathval = SW + pathval(Pi)
PLEPT
PIEP!
We next assign values for other path indicators of a such that the indicators for the functional descendant paths in the state are conrectly. In particular, for each functional descendant path P of W, let P be the set of functional descendant paths of Aw that do not contain Aw (except for the first node on the path) and that contain P sub-path. Let P1 C P be the paths that start with a variable in M, and P2 S P be other paths that start with a variable in Aw- Again, since all the indicators for paths in P are independent,
assign the indicators for E Aw such that
pathval(Ps) = pathval (P) $
pathval (Pit)
PsEP2
P1EP1
Finally, we combine the cases for each individual W E W by creating the following set Aw Uwew Aw. Since all the functional descendant paths considered for different W's s are disjoint, we can always find an assignment a for Aw that is consistent with the functional dependencies (does not produce any zero probabilities). Consequently, there must exist some full instantiation (u, v) compatible with s, z, a such that Pr(u, v) > O, which implies Pr(s, z) > 0.
Proof of Proposition 20
Proof. Suppose is not a child of X in the CBN, then Ex fxfr = fx fx) which is guaranteed to be a CPT for Y. Suppose Y is a child of X. Let Px denote the parents of X and Py denote the parents of Y excluding X. The new factor = Σx fx fy defined over P x (Y). Consider each instantiation px and py, then E, PY. v) Ey E. (x (f (ylPY,
Σ, fx (x) Σ, fy (y)py, z) 1. Henee, g is CPT for Y.
Proof of Propusition 21
Proof. Let X be the functional variables that is functionally eliminated. By definition, the elimination only affects the CPT's for the children of X. Hence, any functional variable that is not child of X remains functional. For each child C of X that is functional, the new CPT (Ex fx only contains values that are either 0 or 1 since both fx and fc are functional.
Proof of Proposition 22
Proof. First note that 72 can always be obtained from mi by a sequence of "rranspositions", where each transposition swaps two adjacent variables in the first sequence. Let be an elimination order and let n' be the climination order resulted from swapping n. = X and π4+1 = Y from the π, i.c.,
π (..., X,Y,
(..,,,,,,,......
We show functional elimination according to π and T' yield a same CBN, which can be applied inductively to conclude that elimination according to and yield a same CBN. Since π and x' agree on a same elimination order up to X, they yield same CBN before eliminating variables X, Y. It suffices to show the CBNs resulting from eliminating (X, Y) and eliminating (Y, X) are the same. Let (G, Pr) be the CBN before eliminating variables X, Y. Suppose X and Y do not belong to a same family (which contains variable and its parents), the elimination of X and Y are independent
16

---

and the order of elimination does not matter. Suppose X and Y belong to same family, then they are either parent and child or co-parents
WL.G, suppose X is a parent of Y. Eliminating (x, Y) and eliminating (Y, X) yield a same causal graph that is defined as follows. Each child C' of Y has parents Px x U Py U Pc (X, Y), and any other child C' of X has parents P x P {.}. We next consider the CPTs. For each common child C' of X and Y, its CPT resulting from eliminating (X,Y) SC Ev [x fofx)(())))))))))))) fY fx), and the CPT resulting from eliminating (Y is So Ex falv). Since X is parent of Y, we have Y & fx and
- = f6=D fxfofy fxfofy x
( fd
We next consider the case when is a child of Y but not a child of X. The CPT for C resulting from eliminating (X, Y)) is fo Ey fc(Ex fx), and the CPT resulting from eliminating (Y, is Ex fx fafy). Again, since X is parent of Y, we have Y & fx and
fö =x
f6 ΣΣ Ixfoly EExxfof fxfelv
Y
fxfr)
We finally consider the case when C' is child of X but a child of Y. Regardless of the order on X and Y, the CPT for C' resulting from eliminating X and Y is (Ex fx
We next consider the case when X and Y co- co-parents. Regardless of the order X and Y, the causal graph resulting from the elimination satisfies the following properties: (1) for each common child C of X and Y, the parents for C Px x UP PyUPP (X.Y): (2) for each C that X but not child of Y, the parents for C are Px UUC (X): for each C that a child of Y but not child of X, the parents for C are PyPPPe' (YY)). We next consider the CPTs. For each common child C of X and Y, its CPT resulting from eliminating (X, Y) is fg = Ey [y x fc)c). and the CPT resulting from eliminating (Y, X) is fe = Ex fy fc). Since X and Y are not parent and child, have X & fy. Y & fx and
child of
fa f== - fyfxfc ΣE X
X
For each C' that is child of X but not child of Y, regardless of the order on and Y. the CPT for C' resulting from eliminating variables X and Y is (Ex fxfc). ) A similar result holds for each C that is child of Y but not a child of X.
Proof of Theorem 23
Proof. It suffices to show that Pr' Ex Pr when we eliminate single variable X. Let F denote
the set of CPTs for M. Since fx is a functional CPT for X, we can replicate fx in F which yields a new CPT set (replication) J that induce same distribution as F; see details in [48] Theorem 4J. Specifically, we pair the CPT for each child C' of X with an extra copy of /x. denoted Ux,Je) which yields list of pairs (fx, X. Functionally eliminating X from F yields
Jc,),..., (/x,fc,),
(,x,,,Xx,,,, where Ci,...; Cs are the children of
Σ Pr X
Σ F = H. (IIxe)) ... Exfe)
X
(2)
48 Corollary 1]
H fc, ... ..... = Pr
where H are the CPTs in F that do not contain X and each fèc is the CPT for child C; in M'.
X and Y are co co-parents if they have same child.
17

---

Proof of Theorem 24
Lemma 26. Consider a CBN (G,F) and its mutilated CBN Fx) under do(x). Let W be functional variable not in X and let (G', and (G F be the results of functionally eliminating W from F) and (x,,xx) respectively. Then (Gxx F2) is the mutilated CBN for (G', F³).
Proof. First observe that the children of W in G and Gx can only differ by the variables in X. Let C, be the children of W in both G and Gx and let C₂ be the children of W in G but not in Gx. By the definition of mutilated CBN, W has the same set of parents and CPT in FG and (Gx Fx). Similarly, each child C C₁ has the same set of parents and CPT in (G, F) and (Gx; Hence, eliminating W yields the same set of parents and CPT for each C E C in (") and (C's F%) We next consider the set of parents and CPT for each child C E Cg. Since W is not a parent of C in Fx), variable C' has the same set of parents and CPT in (G* F The exactly same set of parents (empty) and CPT will be assigned to C' in the mutilated CBN for FG)
Proof. (Theorem 24 Consider a CBN FG and its mutilated CBN (Gx, Fx). Let Pr and Prx be the distributions induced by F and Fx over variables V. respectively. By Lemma [26] we can eliminate each W E W inductively from FG,F) and Fx) and obtain (G', ,F') and its mutilated CBN (Gxx Fx) By Theorem 23 the distribution induced by F% is exactly Ew Pix(V).
Proof of Proposition 10
Proof. First note that the extended set Z' contains Z and all variable that are functionally determined by Z. Consider any path P between some X E X and Y E Y. We show that P is blocked by Z' iff it is blocked by Z according to the definition in 44). We first show the if part Suppose there is convergent valve") for variable W that is closed when conditioned on Z. then the valve is still closed when conditioned on Z' unless the parents of W are in Z". However, the path P will be blocked in the latter case since the parents of W must have sequential/divergen valves. Suppose there is a sequential/diverrent valve that is closed when conditioned on Z according to 42,. then W must be in Z' since it is functionally determined by Z. Hence, the valve is also closed when conditioned on Z'.
We next show the only-if part. Suppose convergent valve for variable W is closed when conditioned on Z', then none of is a descendent of W since Z' is a superset of Z. Suppose a sequentiaa/ddveerennt valve for variable W is closed when conditioned on Z', then W is functionally determined by Z by the construction of Z'. Thus, the valve is closed in (2).
Proof of Theorem I1
By induction, it suffices to show that X and Y are D-separated by Z in (G. W) iff they are D-separated by Z in (G', W where G' is the result of functionally eliminating a single variable T E W from G" and W = W \ {T). We first show the contrapositive of the if-part. Suppose X and Y are not D-separated by Z in (G, W)) by the completeness of D-separation, there exists parameterization F on G such that (X M. Y|Z)=. If we eliminate T from the CBN (G,F), we obtain another CBN (G',F") where F' is the parameterization for G'. By Theorem 23 the marginal probabilities are preserved for the variables in G", which include X, Y, Z. Hence, (X Y and X and Y are not D-separated by Z in (G', W').
Proof.
Next consider the contrapositive of the only-if part. Suppose X and Y are not D-separated by Z in (G", W'), then there exists a parameterization F of G' such that (X J. Y Y r. by the completeness of D- D-separation. We construct a parameterization F for G such that F is the parameterization of G' which results from eliminating from the CBN (G, F). This is sufficient to show that X and Y are not D-separated by Z in (G, W) since the marginals are preserved by Theorem 23
Construction Method Let Pr and Cr denote the parents and children of T in G. Our construction assumes that the cardinality of I' is the number of instantiations for its parents Pr. That is, there one-to-one correspondence between the states of T' and the instantiations of Pr, and we use (t)) to denote the instantiation Pr corresponding to state t. The functional CPT for I' is assigned as fr (t) if (t) = Pr and (t P = otherwise for each instantiation pr of Pr. Now consider each child C' E Cr that has parents P (excluding T) and T in G. It immediately follows
SSe 440 Ch. 4] for more details convergent, divergent and sequential valves.
18

---

from Definition 9 that C' has parents Pr UC e in G". We next construct the CPT fc in F based on its CPT fo in F. Consider each parent instantiation (t, Pc) where is a state of T and Pc is an instantiation of Pc. If ((t)) is consistent with Pc: assign Sc(e)t, Pc) (clo)(())), Pc) for each Pc). The construction ensures
state e Otherwise, assign any functional distribution for that the constructed CPT fr for T is functional, and that the functional dependencies among other variables are preserved. In particular, for each child C' of T, the constructed CPT fc is functional iff fc is functional. This construction method will be reused later in other proofs.
We now just need to show that CBN (G',F") is the result of eliminating T from the (constructed) CBN F.. In particular, we need to check that the CPT for each child C E Cr in F is correctly computed from the constructed CPT's in F. For each instantiation (Pr, Pc) and state e of C,
(clPT pc) = Sc(cl," (p((c)(p))>>-->))) - fr (T(("((())((())) Pc)
= Σ tr(ppr))c(((
where t* is the state T' such that aelt) = PT.
Proof of Theorem 13
Proof. We prove the theorem by induction. It suffices to show the following statement: for each causal graph G with observed variables V and functional variables W, the causal effect (Y) is F-identifiable wrt (G, V,Cv, W) iff it is F-identifiable wrt (G", V,Cv W where G' is the result of functionally eliminating some hidden functional variable T E W and W = W (T3.
We first show the contrapositive of the if-part. Suppose PTx(Y) is not F-identifiable wrt (G. V.V.y. Cv. W), there exist two CBNs (G, Fi) and (G.F2) which induce distributions Prı,Prg such that Prı(V (V) Pr (V) but Prix (Y) + PY2 Let (G",Fi and (G'. be the results of eliminating T' & V from FI) and (G. the two CBNs attain the same marginal distribution on
V but different causal effects by Theorem 23 and Theorem 24 Hence, (Y) is not F-identifiable wrt (G', V.Cv; W") either.
We next show the contrapositive of the only-if part. Suppose PY) is not F-identifiable wrt
(G", V, V,Cv. W"), there exist two CBNs (G', (G',F) and (G'FF) which induce distributions Pr,, Pr, such that (V) = (V) but Pr(x(Y) * Prix(2 (Y). We can obtain (G,Fi) and (G,F2) by considering again the construction method in Theorem where we assign a one-to-one mapping for
T and adopt the CPTs from Fi and FV for the children of T. This way, (G', .F) and (G).F) become
the results of eliminating T from the constructed (G, F1) and (G.F2). Since T & V, Pr, (V)
(V) = (V) (V) by Theorem 23 and Prix ( (Y) # Prex (Y) = Pr2x Y
by Theorem 24 Hence, Prx (Y) is not F-identifiable wrt (G, V,C,V, W) either.
Proof of Theorem 15
Proof. Since we only functionally eliminate variables that have observed parents, it is guaranteed that each Z has observed parents when it is eliminated. By induction, it suffices show that Prx (Y) is F-identifiable wrt (G, V.Cv, W) iff it is F-identifiable wrt (G', V", W') where G' is the result of eliminating single functional variable and W' W] (2).
W with observed parents from G, V V (2).
We first show the contrapositive of the if-part. Suppose Prx(Y) is not F-identifiable wrt (G, V,Cv W), there exist two CBNs Fi) and (2) which induce distributions Pri,Pry Pr2 where Pri (V)= Pr2(V) but Prix (Y) of Prex(Y). Let ( and (G', FF) be the results of
eliminating Z from Fi) and (G. G2F. the two CBNs induce the same marginal distribution
Pri
Pr²(V") by Theorem 23 but different causal effects Prix (Y) o Prix(Y) (Y) by Theo-
rem
24
Hence, (Yx is not F-identifiable wrt (G', V Cv. W
We now consdier the ctrapositive of the only-if if part. Suppose Prx(Y) is not F-identifiable wrt (G', V',Cv, W'), then there exist two CBNs (G' RR) and (G.FF) which induce distributions Pr, such that Pri (V')
Pry(V" but Pr (Y) A Pr (Y). We again consider the con- struction method from the proof of Theorem 11 which produces two CBNs (G, and F2)..).
For clarity, we use the notation| to separate variable and its parents in a CPT.
19

---

Moreover, FG) and (2) are the result of eliminating Z from FG) and (G. (G. is
guaranteed that the two constructed CBNs produce different causal effects Prix YY) = (X) *
Prax( (Y) = Prax(Y) by Theorem 24 We need to show that Fi) and (G, F2) induce a same
distribution over variables V V U { Consider any instantiation (V'2) of V. Since F1 and
F3 assign the same one-to-one mapping between Z and its parents in G. it is guaranteed that the probabilities (r, 2) = Pre(v', 2) = 0 except for the single state x" where ax=²)= = P where p is the parent instantiation of Z consistent with v'. By construction, Pri(v', 2,, .. Pri(v', u) for every instantiation u of hidden variables U. Similarly, Pr2(v', u) = (v
" u) for every instanti-
ation (v', 2, u). It then follows that (v=(v'22") =Eu Pri(v', 2,, u) Eu Pr((v', u) (v'( Prş Σn Pro(v', u) E. Pro(V', 2,2", u) Pr2(v',2") This means Prx is not F-identifiable wrt (G, Cv, W) either.
Proof of Theorem 17
Lemma 27. Let G be causal graph, V be its observed variables and W be its functional variables. Let Z be a nen-descendant of W that has at least one hidden parens, then a causal effect is F- identifiable wrt (G, V.Cv, W) iff it is F-identifiable wrt VG. W U (Z}).
Proof. Let W' denote the set W U (Z). The only-if part holds immediately by the fact that every distribution that can be possibly induced from (G, W') can also be induced from (G, W). We next consider the contrapositive of the if part. Suppose a causal effect is not F-identifiable wrt (G, V. Cv. W), then there exist two CBNs (G.Fi) and (G.F2) which induce distributions Pr,, Pr. such that Pri (V) Pr2(V V) but Prix # -r2x(Y)) We next construct (G, and (G)F)) which constitute an example of unidentifiability wrt (G, V,C,V W'). In particular, the CPTss for 2 need to be funetional in the constructed CBNs.
WLG, we show the construction of FG) from Fi) which involves two steps (the construction of (G) from (2) will follow a same procedure). Let P be the parents of Z. The first step constructs a CBN (G', FF) based on the known method that transforms any (non-functional) CPT into a functional CPT. This is done by adding an auxiliary hidden root parent U for Z whose states correspond to the possible functions between P and Z. The CPTs for U and Z are assigned accordingly such that fz = Eu f' f'z where f' and fz are the constructed CPTs in Fi 10 that Fi and Fi induce the same distribution over V since Fi = Eu Fi. The causal effect is also preserved since summing out U is independent of other CPTs in the mutilated CBN for (G', Fi).
It follows
Our second step involves converting the CBN (G', Fi) (constructed from the first step) into the CBN (G, over the original graph G. Let T E P be the hidden parent of W in G. We merge the auxiliary parent U and T into a new variable T" and substitute for T in G, i.e., T" has the same parents and children as T. T' is constructed as the Cartesian product of U and T: each state of T' is represented as a pair (u, t) where u is a state of U and is a state of T. We are ready to assign new CPTs for T' and its children. For each parent instantiation p of P and each state (u, of T', we assign the CPT for T' in F as fff ((u, t) t)lp) = (w) (t|p). Next consider each child C' of T' that has parents Pc (excluding T*). For each instantiation PC of Pc and each state (u, t) of T', we assign the CPT for C in F as fe (u, t)) = (c(Pp) for each state c. Note that fö is functional iff fo is functional. Hence, the CPTs for W are all functional in F"
We need to show that (G,F") preserves the distribution on V and the causal effect from (G'Fii Let U" be the hidden variables in (G,F") and U' be the hidden variables in Fi). The dis- tribution on V preserved since there is a one-to-one correspondence between each instantia- tion (v, u") in FG) and each instantiation (v, in (G', F.) where the two instantiations agree on v and are assigned with the same probability, i.c., Pr (v, u") = Pri (v, (v,u'). Hence, (v) E (r"(v, = En Pr,( uv) = (v) for every instantiation v. The preserva- tion of causal effect can be shown similarly but on the mutilated CBNs. Thus, FG) preserves both the distribution on V and the causal effect from (G.F).. Similarly, we can construct (G.F)) which preserves the distribution on V and causal effect from (G.F.). The two CBNs (G. and (G,F)) constitute an example of unidentifiablity wrt (G. V Cv. W').
EaEahh state u of U corresponds to a function To where N/. (p) is mapped to some state of Z for each instantiation P. The variable U thus has |z| [P| states since there are total of |2| IPI possible functions from P to Z. For each instantiation (2, u. p). the functional CPT for Z is defined as (2lu. p) = =f = 7a (p), and f' (2|u, p) 0 otherwise. The CPT for U is assigned (u) Ipce fz (7 (p) p).
20

---

Proof of Theorem 17 We prove the theorem by induction. We first order all the functional variables in bottom-up order. Let W denote the ith functional variable in the order and W denote the functional variables that are ordered before W (including W It follows that we can go over each W in the order and show that causal effect is F-identifiable wrt (G, V, Cv. W(-1)) iff it is F-identifiable wrt VG,VCvv. W by Lemma 27| Since F-identifiability wrt (G, Cv W is equivalent to identifiability wrt (G,V VV),,, we conclude that the causal effect is F-identifiable wrt (G, V, Cv, W) iff it is identifiabile wrt (G, V C.)..
Proof of Theorem 18
The proof of the theorem is organized as follows. We start with a lemma (Lemma 28 that allows us to modify the CPT of a variable when the marginal probability over its parents contain zero entries. We then show a main lemma (Lemma 29] that allows to reduce F-identifiability to identifiability when all functional variables are observed or has a hidden parent. We finally prove the theorem based on the main lemma and previous theorems.
Lemma 28. Consider two CBNs that have a same causal graph and induce the distributions Pr and Pry. Suppose the CPTs of the two CBNs only differ by (X, Then Pr)(p) = 0 iff Pry(p) 0 for all instantiations p of P.
Proof. Let fy and gy denote the CPT for Y in the first and second CBN. Let An(P) be the ancestors of variables in P (including P). If we eliminate all variables other than An(P), then we obtain the factor set Fi (m)) fy for the first CBN and F2 E.AAA)(P) PY for the second CBN. Since all CPTs are the same for variables in An(P), it is guaranteed that Fi = F2. If we further eliminate
variables other than P from F1 and F2, we obtain the marginal distributions (P) = Σp and Pre (P) = EpF2, where Σp denotes the projection operation that sums out variables other than P from a factor. Hence, Pr, PP) Pry(P) which concludes the proof.
Lemma 29. If causal effect is F-identifiblle wri (G, V, Cv. W) but is not identifiable (G, V V,Cv), then there must exist at least one functiioal variable that is hidden and whose parents are all observed.
Proof. The lemma is the same as saying that if every functional variable is observed or having hidden parent, then F-identifiability is equivalent to identifiability. We go over each functional variable W; W in a bottom-up order II and show the following inductive statement: a causal effect Pra Pr,(Y) is F-identifiable wrt (G, V, Cv, W(0) iff it is F-identifiable wrt (G, C,Cv, W( where (() is a subset of variables in W that are ordered before W; (and including WD in IT. Note that W(O) = ( and F-identifiability wrt (G, V, Cv, W()) collapses into identifiability wrt (G, CVC..
The if-p follows from the definitions of identifiability and F-identifiability. We next consider the contrapositive of the only-if part. Let Z be the functional variable in W that is considered in the current inductive step. Let Fi, and (2) be the two CBNs inducing distributions Pri and Pr2 that constitute the unidentifiability, i.e., Pri (V) =Pr2(V) and Priz (Y) ) A Pr2 (Y). Our goal is to construct two CBNs (G.F and (G.FL), which induce distributions Pr Pr and contain functional CPTs for Z. such that (V) Pr. Pr. (V) and Pr"". (Y) * Pr (Y). Suppose Z has a hidden parent, directly employ Lemma t7 construct the two CBNs. We next consider the case when Z is observed and has observed parents. By default, we use fz to gz to denote the CPT for Z in F1 and Fz.
The following three steps are considered to construct an instance of unidentifiability.
First Step: we construct (G, Fi) and (G)F) by modifying the CPTs for Z. Let P be the parents of Z in G. For each instantiation p of P where Pri (p) Pry O, we modify the entries f/ (Z p) and 9'2 (Z)p) for the CPTs f'z and g'z in Fi and F₂ as follows. Since Prix (Y)
) * Prze YY. ), there
exists an instantiation y such that (rin(y) + Pr2z(y). WLG, assume Pr)x(y) > Pr2z (y). Since
Prin(y) (y) is computed as the marginal probability of in the mutilated CBN for (G,Fi). it can be expressed the form of network polynomial as shown in 49 40). If we treat the CPT entries of fz (p) as unknown, then we can write Pyie(y) follows
21

---

Pri= = a + taff2
where (oo, ..,,.... Og are constants and 21, 21,...; Fe are the states of variable Z. Similarly, we can write Prez (y) as follows
(y) = 30 + Blgz(z1lD) + .... (agz(zalp)
......,,,, 3x, our construction method assigns f'2 (2: (p) and (2 pp) 1. By construction, it guaranteed that (y) - Prex (y) 2 Priz(y) (y) Pr (y) > 0 where Pr (y). Prex (y) denote the causal effects under the updated CPTs (2 and g2 p). We repeat the above procedure for all such p where (p) = 0, which yields the new CBNs FG) and F2) in which f'Z (Z (p) and 5/2(2 (ZIp) are functional whenever Pr, (p) = O. We next show that FG and F2 (with the updated fz and gz)) constitute an example of unidentifiability. Prím (Y) + Pr (Y) since Prí > Pr (y) for the particular instantiation y. We are left to show that the distributions Pr, and Pr, induced by (G, F)) and (G, F2) are the same over the observed variables V. Consider each instantiation v of V and p of P where p is consistent with If Pr. (r)(p) 0, then (p) (r)(p) 0 by Lemma 28 and thus (r((v) (v) = (v) = O. Otherwise, Pr (v) = (v)(v) = (v) = Prz(v) since none of the CPT entries consistent with were modified.
Let a; be the maximum value among 01,..... ag and 53 be the minimum value among $1....,
Second Step:
We construct FT), (G", from (G, FG) by introducing an auxiliary root parent for Z and assigning a functional CPT for Z. We add root variable, denoted R, to be an auxiliary parent of W which specifies all possible functions from P to Z where P contains all instantiations of p' where (p") Prz(p") > 0. Each state of R corresponds to a function for where (p") ) is mapped to some state of / for each instantiation p'. The variable R thus has |Z|lP"| states since there are total of |Z| |P' possible functions from P to Z. For each instantiation (z, r. p), if p E P' we define (2 p) 1 if
(p),,, and (2 p) = 0 otherwise. p of P we define (2 p) = f2(=1p) The CPT for R is assigned as (r())) Ip==P (1pr pp). Moreover, we remove all the states of R where (x(r which ensures fK(r) >> 0 for all remaining r. We assign the CPT 9% in Fy in a similar way. Note that fK= = 9.k since (1) p) (D)))) (r)(e+(D)l))
2' (p+(p)pp) for each p P
(where Pr((p) = Pr)(p) 0).
We next show that (G) and
constitute the unidentifiability. One key observation is that (tlp) = (R) (f)p,r) and (t(p) = E, (r)g) (t) Consider each instantiation
rv.r) which contains the instantiation p of P and the state of Z. Suppose Pr' (p) = 0, then (p) 0 since the marginal over V is preserved in Pr". Hence, Pr,
Pr (v.r) = 0.
Suppose Prí # O, then rv, = ([lvevuz) fv).f((r) when (p), and (v, otherwise. Similarly, (v, = ([ IV) (r) when = (p). and (r, otherwise. In both cases, (v) Pr" since Fl and Ft assign a same function fr for each state r' of R, and fv = IV for all V E V \ (Z). To see Pr (Y) = Pr (Y) and Pr Preg (Y), note that summing-out R from Pr (V, R) and Pr (V, R) yields Priz (V) and Pr (V).
Third Step: we construct (") (G, from (G",F") (G", ,T) by merging the auxiliary root variable R with an observed parent T of z. We merge R and T into a new node T" and substitute it for T in G, i.e., T' has the same parents and children constructed as the Cartesian product of R and T: each state of T' can be represented as (r, 1) where r is state of R and is a state of T. We then assign the CPT frr PT) in F= as follows. For each parent instantiation pr and each state (r,t) of T", f (7. ()(PT)) = (f For each child C' of 1" that has parents Pc (excluding T*), the CPT for C in F is assigned as f" (r, t)) = f' t). Similarly, we assign the CPTs 9ith and g in FM The distributions over observed variables are preserved since there is an one-to-one correspondence between the instantiations over V {R} in FF") and the instantiations over V in (G,F""). We next consider the causal effect. Suppose T neither a treatment nor an outcome variable, then the merging does not affect the causal effect by the one-to-one correspondence between instantiations and Pr "
T in G. Specifically, 7" is
Pr (Y) of Przz (Y) ) = fr (Y). Suppose T an outcome variable, since Pri, # Pr 20 (Y) there exists instantiation (y' r, t) where Y' = Y \ (T) such that Pr (y', r,t) # Pr 21
r,t).
22

---

This implies Pri (y', (r,t)) * Przz (y', (r, t)) for the particular instantiation y' and the state (r, t) of Pr (Y), there exists an instantiation
T". Suppose T is the treatment variable X, since Pr (Y) of
(y.r) such that Priz (y) * P1 (y,r), r). Moreover, Pris (r) = (r) = (r)(r)
Pr (r) >> 0 (ylr). Since
(otherwise, Pr (y, (y, root in the mutilated CBN, Pri ((a)) (y) Pri (y/r) o Pr (y(r) = Pr (y). We now consider the treatment do(T" ()) on G instead of the treatment do R r, x) on G". We have (r((((:=))) (y) = Pr (r(((,,)()) (y) * Pr (r)(,.))()) = (1)()) (y) for the particular state (r,z) of TV. Moreover, Pr," ((r,()
Przy y, r) 0). This implies Pr (y(r) * (
(r, 2) = Thus, the positivity still holds for Pr," and similarly for Pr."
0 by the positivity assumption of (x).
Proof of Theorem 18 = V V be the set of hidden functional variables that are function- ally determined by V. By Theorem 13 F-identifiable wrt (G, V, Cv. W) F-identifiable wrt (G", V,Cv, W H) where G" is the result of functionally eliminating H from G. By construction, every variable in has parents V'. Hence, by Theorem 15 F-identifiable wrt (G", V, V,Cv, W H) iff F-identifiable wrt (G, V Cv. W). If consider each functional variable W E W, it is either in V or having some parent that is not in V (otherwise, W would have been added to V'). By Lemma 29 F-identifiable wrt (G, V Cv. W) iff identifiable wrt (G, V (v).
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract and introduction accurately summarize our goal of studying causal-effect identifiability with functional dependencies.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations have been discussed in the end of Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
Also proofs have been provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
25

---

Answer:
[NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
wowoooooooolloooooooollooooillll for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ lttipp.cc/pulli/guuii.e gwtcc//ggge///eee CoodeSumiiiie sesiiissinnneeeoe ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
26

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httpp//c.cc....ccccccccccccciiia
Answer:
[Yes]
Justification:
We checked the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We do any direct societal impacts of the work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
27

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not release any data model.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, snperswwthcooee com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
28

---

Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "mEHmBww89J", "reviewer": "Reviewer_uRPz", "summary": "This paper investigates the identification of causal effects in the presence of functional dependencies, where some variables are determined by their parents. The study demonstrates that unidentifiable causal effects can become identifiable and that certain functional variables can be excluded from observation without affecting identifiability. The authors introduce a new elimination procedure to remove functional variables while preserving key properties of the causal graph, and show how existing algorithms can be used to test and obtain identifying formulas. This approach can significantly reduce the number of variables needed in observational data.", "questions": "See weaknesses section", "limitations": "Limitations are not discussed", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is written well and easy to understand\n2. Theoretical aspects are explained with the help of examples which makes it easy to follow along.", "weaknesses": "1. What are the implications when the treatment/target variable is a functional variable?\n2. Assumptions need to be formally written. Currently, many assumptions are not very clear. For example, are functional variables need to be observed or they can also be unobserved?\n3. Justification for NeurIPS checklist items is not provided where necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> What are the implications when the treatment/target variable is a functional variable?\n\nIf each treatment and target variable has some hidden parent and these are the only functional variables (after perhaps eliminating other functional variables by Theorems 13 & 15), we can reduce F-identifiability to classical identifiability by Theorem 17 (we will include a note to this effect). Otherwise, our current results do not cover this case which is a subject for future work. \n\n> Assumptions need to be formally written. Currently, many assumptions are not very clear. For example, are functional variables need to be observed or they can also be unobserved?\n\nWe allow both observed and unobserved (hidden) functional variables in the causal graph. This is evident by Theorem 13 & Corollary 14 which eliminate hidden functional variables, and Theorem 15 & Corollary 16 which eliminate observed functional variables. We would really appreciate it if you could point us to any unclear assumptions so that we can clarify them further. \n\n> Justification for NeurIPS checklist items is not provided where necessary.\n\nWe did not see ambiguity in our answers to the checklist items, but we are happy to add justifications to these items. Please let us know in case any of them need particular attention and we will address them properly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "3gKMp20yBq", "reviewer": "Reviewer_bXg6", "summary": "Existing causal effect identification algorithms such as the ID algorithm, require strict positivity constraints on the observed distribution that can get violated in cases where some variables (observed or hidden) are deterministic functions of their parents. This paper takes a step towards finding conditions for when causal effects can be identified when such 'functional variables' are present (with quantitative knowledge of functional dependencies being not required). At a high-level, the approach is to eliminate functional variables followed by latent projection that enables using existing ID algorithms on the resulting causal Bayesian nets. Sound conditions for identifiability are proposed that depend on whether the functional variables are hidden or observed.", "questions": "A few questions and typos: \n1) Line 169 - the constraint is sufficient for identification under the assumption that there exists an instantiation of Z such that Pr(z)>0. This is also later used in the proof of Proposition 5. Why is this assumption justified? \n2) The footnote remark on Page 8 is ambiguous. What in Ref 25,26 point to requiring the positivity condition for projection? \n3) Proof of Proposition 5 - typo in definition of f^1(z|x,p_Z)", "limitations": "Limitations of the technical content aren't explicitly discussed. Potential negative societal impact is not applicable.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "It's quite clear that functional variables are ubiquitous in the world and hence causal modeling invariably encounters such variables. The dependence of do-calculus and ID algorithm on strict positivity is a hindrance to identify causal effects in such models that include functional variables. This is a nice first step in causal effect identification in the presence of functional variables. I like the view of identification algorithms that take as input positivity constraints which is further extended to taking the functional variables as input. The paper is clearly written overall with some minor issues mentioned in the weakness section. While, the relationship between positivity constraints and functional dependencies was not fully explored, the necessary condition for identifiability w.r.t. the positivity constraints is a nice addition. The proofs of the main theorems are correct but I have not completely checked the proofs of the intermediate lemmas.\n\nThis work also opens up multiple avenues for future research into developing complete identification algorithms and perhaps inspires work into ID-style algorithms that take in the weakest possible positivity constraints. This seems an active thread of investigation already, see for example, \"On Positivity Condition for Causal Inference\" accepted to ICML 2024.", "weaknesses": "I believe the current version is dense with results with the page restriction limiting a better style of presentation. There are multiple corollaries that deserve to be highlighted separately that appear in the middle of the text. I would also prefer adding proof sketches of the main theorems and cutting out results that don't directly impact the main message of the paper, for example, perhaps limiting the section on positivity contraints since it appears as an interlude in the current version.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I believe the current version is dense with results with the page restriction limiting a better style of presentation. There are multiple corollaries that deserve to be highlighted separately that appear in the middle of the text. I would also prefer adding proof sketches of the main theorems and cutting out results that don't directly impact the main message of the paper, for example, perhaps limiting the section on positivity contraints since it appears as an interlude in the current version.\n\nThank you for your suggestions! We will consider them.\n\n> Line 169 - the constraint is sufficient for identification under the assumption that there exists an instantiation of Z such that Pr(z)>0. This is also later used in the proof of Proposition 5. Why is this assumption justified?\n\nThis is a relaxed version of positivity from the ID algorithm [Shpitser & Pearl, 2006], which requires $Pr(X|P) > 0$, where P are the observed parents of X. In this example, we only need the assumption $Pr(X|Z) > 0$ since it is sufficient to make the identifying formula well-defined. This is because $Pr(y|x, z) Pr(z)$ in the formula is equal to zero when $Pr(z)=0$, and is computable when $Pr(z) > 0$ (the conditional probability $Pr(y|x,z)$ is well-defined if $Pr(x|z) > 0$). \n\n> The footnote remark on Page 8 is ambiguous. What in Ref 25,26 point to requiring the positivity condition for projection?\n\nRef 26 is more relevant in this case. Ref 25 mainly focuses on d-separations. We will fix this.\nThank you for pointing it out!\n\n> Proof of Proposition 5 - typo in definition of f^1(z|x,p_Z)\n\nWe will fix it. Thanks!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "7HeL5YCSR4", "reviewer": "Reviewer_3A71", "summary": "The paper addresses a novel problem in causal effect identifiability, introducing the concept of functional dependency among variables. It proposes a new elimination approach for removing redundant variables from the graph while preserving the identifiability of the target quantity. The main contribution includes proposing graph conditions that reduce the problem to classic ID settings.", "questions": "1-  I didn’t understand when your theorems fail to recognize whether a causal effect in a graph is id. Can you provide some examples where the conditions of Theorem 15 are not satisfied, but the causal effect is identifiable (or not)?\n\n\n2- Could you elaborate on corollary 14 and the positivity constraint? It’s worth rechecking the exact conditions of projection operation and stating the corollary in precise form.\n\n\n3- What about the generalization of results to other variants of the causal effect identification problem, such as c-ID, g-ID, s-ID, and so on? If there is additional space, it would be beneficial to include a brief review of these works.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1- The paper addresses a novel problem in causal effect identifiability.\n\n2- The paper is well-written, and the authors formulate the problem clearly.\n\n3-  An approach called functional elimination has been proposed to remove redundant variables while preserving identifiability.\n\n4- By leveraging functional elimination and certain graph conditions, the theorems demonstrate that F-Identifiability can be reduced to the classic ID problem.", "weaknesses": "The proposed conditions are not complete; the paper does not provide a complete condition to determine whether a causal effect is id or not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I didn’t understand when your theorems fail to recognize whether a causal effect in a graph is id. Can you provide some examples where the conditions of Theorem 15 are not satisfied, but the causal effect is identifiable (or not)?\n\nWe suspect that Theorem 15 will hold under weaker positivity constraints, but the current condition is the most succinct one we can obtain so far. The difficulty lies in how to formulate the positivity constraints $C’_V$ for the graph resulting from eliminating functional variable $Z$ if the original positivity constraints $C_V$ contain $Z$. For example, we cannot simply set $C’_V$ to be the positivity constraints in $C_V$ that do not mention $Z$. To see why, consider a causal graph with observed variables $A,Z,X,Y$ and edges $A \\rightarrow Z, Z \\rightarrow X, Z \\rightarrow Y, X \\rightarrow Y$. Assume that variable $Z$ is functional and the positivity constraint is $Pr(X|Z) > 0$. The causal effect of $X$ on $Y$ is F-identifiable. However, it is no longer F-identifiable in the graph resulting from eliminating $Z$ by Proposition 5 since $C’_V = \\emptyset$ if we only keep the positivity constraints that do not mention $Z$. \n\n> Could you elaborate on corollary 14 and the positivity constraint? It’s worth rechecking the exact conditions of projection operation and stating the corollary in precise form.\n\nIn [Tian & Pearl, 2002], the projection operation is stated under the strict positivity $Pr(V) > 0$. We are saying that if projection also operates under a weaker positivity assumption, then we can relax the positivity constraint accordingly in Corollary 14. We will clarify this further.\n\n> What about the generalization of results to other variants of the causal effect identification problem, such as c-ID, g-ID, s-ID, and so on? If there is additional space, it would be beneficial to include a brief review of these works.\n\nThank you for the suggestion! We will consider it.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "A588Crm7ti", "reviewer": "Reviewer_GMHe", "summary": "The paper studies the identifiability of causal effects in the presence of functional dependencies. Section 4 starts with an engaging discussion on the interaction between positivity constraints and functional dependencies, during which it defines the concept of F-identifiability. Then in Section 4 its introduces new concepts such as functional elimination, functional projection, and, which are pivotal for much of the subsequent discussion. Additionally, in this section, it presents several results that reduce D-separation to d-separation. In Section 5, the paper presents various results that reduce F-identifiability  to F-identifiability from a simpler graph (Theorems 13 and 15) or to identifiability (Theorems 14, 16, 17 and 18).", "questions": "Minor:\n* Can you add a new section for example titled “Motivating Example” to present a hypothetical case study where knowledge of functional variables leads to successful identification, whereas classical identification methods would have suggested unidentifiability. \n* I think the sentence at line 216 can be made clearer by avoiding a double \"if\", for example: If every positivity constraint that mentions W does not mention HW ...\n* To my knowledge, a Bayesian network is not necessarily a causal graph. Therefore, in certain places such as footnote 3, it might be more accurate to replace \"Bayesian network\" with \"causal Bayesian network\" to emphasize that the graph should be causal.", "limitations": "The authors have addressed the limitations, but I believe they could put additional effort into emphasizing them. For example, they could highlight which theorems can provide an identifying formula and which cannot. Furthermore, clearly (in conclusion or in a dedicated paragraph) discussing future work in light of these limitations would be beneficial.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I think that the paper is addressing an intriguing topic, extending identifiability results to encompass functional dependencies, which could prove valuable in numerous applications. The results are eloquently presented, with examples included in the main paper and complete proofs provided in the Appendix, making the paper comprehensible for readers acquainted with the subject matter.", "weaknesses": "* Explaining how the theoretical results of this paper can be practically applied to real-world datasets can make the theoretical results in this paper more relevant (I think the results are relevant and important for real world applications).  See Questions below.\n\n* The paper presents numerous theorems that share a similar objectives. I wonder if it's possible to consolidate them into two general, elegant rules, one one for reducing F-identifiability to F-identifiability from simpler graphs and one for reducing F-identifiability to identifiability. However, I don't believe this issue alone warrants rejection. Each theorem, although not unified under a single rule, provides unique insights in different contexts, all of which have both theoretical and practical value.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper presents numerous theorems that share a similar objectives. I wonder if it's possible to consolidate them into two general, elegant rules, one one for reducing F-identifiability to F-identifiability from simpler graphs and one for reducing F-identifiability to identifiability. However, I don't believe this issue alone warrants rejection. Each theorem, although not unified under a single rule, provides unique insights in different contexts, all of which have both theoretical and practical value.\n\nThanks for the feedback! We will see if there is a succinct way to summarize these rules.\n\n> Explaining how the theoretical results of this paper can be practically applied to real-world datasets can make the theoretical results in this paper more relevant (I think the results are relevant and important for real world applications). See Questions below.\n> Can you add a new section for example titled “Motivating Example” to present a hypothetical case study where knowledge of functional variables leads to successful identification, whereas classical identification methods would have suggested unidentifiability.\n\nThanks for the suggestion. We will add the following hypothetical example to the introduction. We want to study how the enforcement of speed limits affects the accident rate. According to our knowledge, the legal driving age (A) is functionally determined by the country (C), and both legal driving age and country are causes of driving speed (X). Moreover, the driving speed and legal driving age are causes of accidents (Y). We can construct a causal graph with edges $C \\rightarrow A, C \\rightarrow X, A \\rightarrow X, A \\rightarrow Y, X \\rightarrow Y$. Suppose we observe variables $\\{C, X, Y\\}$, the classical identification method will suggest that the causal effect of X on Y is unidentifiable. However, it is in fact F-identifiable given that A is functionally determined by C.\n\n> I think the sentence at line 216 can be made clearer by avoiding a double \"if\", for example: If every positivity constraint that mentions W does not mention HW …\n\nOK, will fix it. Thanks!\n\n> To my knowledge, a Bayesian network is not necessarily a causal graph. Therefore, in certain places such as footnote 3, it might be more accurate to replace \"Bayesian network\" with \"causal Bayesian network\" to emphasize that the graph should be causal.\n\nYes, We are aware that Bayesian networks may not be causal. We tried to save space by omitting (causal) as shown on Line 72, but we will add it back to avoid confusion.\n\n> The authors have addressed the limitations, but I believe they could put additional effort into emphasizing them. For example, they could highlight which theorems can provide an identifying formula and which cannot. Furthermore, clearly (in conclusion or in a dedicated paragraph) discussing future work in light of these limitations would be beneficial.\n\nThank you for the suggestion. Will do.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We thank the reviewers for their thoughtful comments and suggestions. Please see individual responses below.

Meta-review: This paper explores the identification of causal effects in the presence of functional dependencies, where some variables are determined by their parents, introducing an elimination procedure to handle functional variables. The study demonstrates that unidentifiable causal effects can become identifiable and proposes conditions under which existing algorithms can be adapted for this purpose. 

Reviewers unanimously recognized its novelty and theoretical contributions while some of the reviewers suggested clarifications and additional examples to better illustrate the practical implications. I recommend it for acceptance and encourage the authors to address the reviewers minor comments such as emphasizing the limitations of this work and discussing potential future research directions in light of these limitations. Additionally, please discuss how this work relates to a recent paper published at ICML, "On Positivity Condition for Causal Inference" by Hwang et al. (2024).
Decision: Accept (spotlight)