On Causal Discovery in the Presence of Deterministic Relations

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 10:28:38

Abstract: Many causal discovery methods typically rely on the assumption of independent noise, yet real-life situations often involve deterministic relationships. In these cases, observed variables are represented as deterministic functions of their parental variables without noise.
When determinism is present, constraint-based methods encounter challenges due to the violation of the faithfulness assumption. In this paper, we find, supported by both theoretical analysis and empirical evidence, that score-based methods with exact search can naturally address the issues of deterministic relations under rather mild assumptions. Nonetheless, exact score-based methods can be computationally expensive. To enhance the efficiency and scalability, we develop a novel framework for causal discovery that can detect and handle deterministic relations, called Determinism-aware Greedy Equivalent Search (DGES). DGES comprises three phases: (1) identify minimal deterministic clusters (i.e., a minimal set of variables with deterministic relationships), (2) run modified Greedy Equivalent Search (GES) to obtain an initial graph, and (3) perform exact search exclusively on the deterministic cluster and its neighbors. The proposed DGES accommodates both linear and nonlinear causal relationships, as well as both continuous and discrete data types. Furthermore, we investigate the identifiability conditions of DGES. We conducted extensive experiments on both simulated and real-world datasets to show the efficacy of our proposed method.

Main paper: 
 introduction: 
 Causal discovery from observational data has attracted considerable attention in recent decades and has been widely applied in various fields such as machine learning (Nogueira et al., 2021) , healthcare (Shen et al., 2020) , manufacturing (Vuković & Thalmann, 2022) and neuroscience (Tu et al., 2019) . Most causal discovery methods operate under the assumption of independent noises in the probabilistic system. However, real-world scenarios frequently encounter deterministic relationships. For example, the body mass index (BMI) is defined as the body weight divided by the square of the body height, composing a deterministic relation among weight, height, and BMI.Constraint-based and score-based methods are two primary categories in causal discovery. Constraint-based methods, such as PC (Spirtes & Glymour, 1991) and FCI (Spirtes et al., 1995) , leverage conditional independence tests (CIT) to estimate the graph skeleton and then determine the orientation. Under the Markov and faithfulness assumptions (Spirtes et al., 2000) , these methods are guaranteed to asymptotically output the true Markov equivalence class (MEC). However, the faithfulness assumption is sensitive to many factors, such as the statistical errors with finite samples. Moreover, in the presence of deterministic relations, the faithfulness assumption is always violated. Take the chain structure X → Y → Z for example where Y = f (X). In this case, faithfulness is violated due to the conditional independence Z ⊥ ⊥ Y |X or Z ⊥ ⊥ f (X)|X. Several variants of constraint-based methods (Ramsey et al., 2006; Spirtes & Zhang, 2014) have been proposed to allow certain types of unfaithfulness. However, they are generally not guaranteed to obtain the true MEC.For score-based methods, the approach can vary based on the search strategy, which may involve greedy search, exact search, or continuous optimization. One typical score-based method with greedy search is Greedy Equivalent Search (GES) (Chickering, 2002) , which searches in the space of MECs greedily by maximizing a well-defined score, such as Bayesian information criterion (BIC) score (Schwarz, 1978) . Specifically, GES starts with an empty graph and consists of two phases.In the forward phase, it incrementally adds one edge at a time if it yields the maximum score improvement, continuing until no further edge can be added to enhance the score. In the backward phase, it checks all edges to eliminate some if removal further improves the score. Similar to the aforementioned constraint-based methods, GES converges to the true MEC in the large sample limit. Some exact score-based methods aim at weakening the faithfulness assumption required for asymptotic correctness of the search results, such as dynamic programming (DP) Koivisto & Sood (2004) ; Singh & Moore (2005) , A* (Yuan et al., 2011; Yuan & Malone, 2013) , and integer programming (Cussens, 2011; Bartlett & Cussens, 2017) . The DAGs estimated by these methods can be converted to their MECs for causal interpretation (Spirtes & Zhang, 2018) . Lu et al. (2021) demonstrated that these exact methods may produce correct results in cases where methods relying on faithfulness fail. Furthermore, Ng et al. (2021) proved that exact score-based search with BIC can asymptotically outputs the true MEC when the sparest Markov representation (SMR) assumption (Raskutti & Uhler, 2018) is satisfied. Note that the SMR assumption is strictly weaker than the faithfulness assumption.Deterministic relations have been considered in a few works of causal discovery. D-separation condition (Spirtes et al., 2000) is proposed for graphically determining conditional independence. Glymour (2007) proposed a heuristic procedure to learn the causal graph in a deterministic system, called DPC, where only a subset of variables will be conditioned in testing conditional independence. Daniusis et al. (2010) and Janzing et al. (2012) considered a deterministic system with only two variables, and presented the idea of independent changes to infer the causal direction. Luo (2006) and Lemeire et al. (2012) incorporated the classical PC algorithm and utilized additional independence tests to handle determinism. Mabrouk et al. (2014) combined a constraint-based approach with a greedy search that included specific rules to deterministic nodes and significantly reduce the incorrect learning. However, there is no identifiability guarantee in those related works Moreover, Zeng et al. (2021) assumes nonlinear additive noise model under high-dimensional deterministic data while Yang et al. (2022) assumes linear non-Gaussian model. Different from them, this paper aims to provide a principled framework to handle deterministic relations for arbitrary functional models. More related works are given in Appendix A2.Contributions. Firstly, we find that exact score-based methods can naturally be used to address the issues of deterministic relations when mild assumptions are fulfilled. Secondly, due to the large search space of the possible DAGs, the exact score-based methods are feasible only for small graphs, therefore, we propose a novel framework called Determinism-aware Greedy Equivalent Search (DGES), aimed at enhancing the efficiency and scalability to handle deterministic relations. Importantly, DGES is a general three-phase method, with no restricted assumption on the underlying functional causal models, i.e., it can accommodate both linear and nonlinear relationships, Gaussian and non-Gaussian data distributions, as well as continuous and discrete data types. Thirdly, we provide the identifiability conditions of DGES under general functional models. Last but not least, we conducted extensive experiments on both simulated and real-world datasets to validate our theoretical findings and show the efficacy of our proposed method.Paper organization. In Section 2, we review the common assumptions, provide a motivating example why PC fails in dealing with deterministic relations, then present our intuitive solution using exact score-based method. In Section 3, we present our proposed DGES with three phases in details. Furthermore, we provide the identifiability conditions for DGES presented in a general form in Section 4. The empirical studies in Section 5 validate our theoretical results and show the efficacy of our method. Finally, we conclude our work with further discussions in Section 6. the task of causal discovery aims at recovering the causal graph G from the data matrix V ∈ R n×d . Usually, each variable V i ∈ V with random noises can be represented by the following structural causal model (SCM):V i = f i (PA i , ϵ i ),where PA i is the set of all direct causes of V i , and ϵ i is the random noise with non-zero variance related to V i , and we assume that ϵ i 's are mutually independent. For variables with deterministic relations, the SCM becomes:V i = f i (PA i ),where there is no extra noise. Throughout this paper, we assume causal sufficiency, i.e., no latent confounder.Assumption 1 (Markov) Given a DAG G and the distribution P over the variable set V , each variable is probabilistically independent of its non-descendants given its parents in G.There are many DAGs which induce the same conditional independence relations with the distribution P, and it is said to be Markov equivalent. The Markov equivalent class (MEC) contains all the DAGs which entail the same conditional independence relations as G does.Assumption 2 (Faithfulness (Spirtes et al., 2000) ) Given a DAG G and the distribution P over the variable set V , P implies no extra CI relations which have not entailed by the Markov assumption.Assumption 3 (Non-deterministic Faithfulness (Glymour, 2007) ) Given a DAG G and the distribution P over the variable set V which contains no deterministic variable, P implies no extra CI relations which have not entailed by the Markov assumption.Faithfulness is usually assumed for the whole set of variables, while non-deterministic faithfulness only focuses on the non-deterministic variables. When the Markov and faithfulness (Spirtes et al., 2000) assumptions hold true, constraint-based methods, such as PC, have been proved to asymptotically output the correct MEC. However, in the finite sample regime, the faithfulness assumption is sensitive to statistical testing errors when inferring the CI relations, and the violations might occur often. When there are deterministic relations, faithfulness also fails. Glymour (2007) proposes the non-deterministic faithfulness regarding only non-deterministic variables. Moreover, different relaxations of faithfulness have been proposed, such as adjacency-faithfulness (Ramsey et al., 2006) and triangle-faithfulness (Spirtes & Zhang, 2014) . Another strictly weaker assumption is called Sparsest Markov Representation (SMR) (Raskutti & Uhler, 2018) , which is also known as the unique-frugality assumption (Forster et al., 2018; Lam et al., 2022) .Assumption 4 (Sparsest Markov Representation (SMR) (Raskutti & Uhler, 2018) ) Given a DAG G and the distribution P over the variable set V , the MEC of G is the unique sparsest MEC which satisfies the Markov assumption.The idea behind the SMR is to find the most parsimonious or sparsest graphical representation that still captures the essential conditional independence relationships in the data. The term "sparsest" refers to the minimal number of edges in the graphical model. Under the SMR assumption, the exact score-based methods, such as the sparsest permutation (SP) and DP, have been shown to produce asymptotically correct results for learning the true MEC. Terminologies. Consider the example with d = 4 variables, as shown in Figure 1 , where V 3 has deterministic relation with V 1 and V 2 (i.e., V 3 = V 1 +V 2 ), and V 4 is a non-deterministic variable. Here we call the set of deterministic variables as a deterministic cluster (DC), e.g., {V 1 , V 2 , V 3 } in Figure 1 . Accordingly, all the non-deterministic variables make up a non-deterministic cluster (NDC), e.g., {V 4 } in Figure 1 . Meanwhile, the edges connecting between DC and NDC compose a bridge set (BS), e.g., {V 2 →V 4 , V 3 →V 4 } in Figure 1 (a). Based on the above definitions and the motivating example in Figure 1 , we provide the following lemma. 
motivating example and intuitive solution: 
 ! ! ! " ! ! (℧) ! # ! $ ! " (℧) $ ℓ (℧) (a) (b) ! % ! & ! ! ! " ! % ! &𝑉 ! 𝑉 " 𝑉 # 𝑉 $ 𝑉 % 𝑉 & 𝑉 ' DC NDC BS 𝑉 ! 𝑉 " 𝑉 # 𝑉 $ 𝑉 % 𝑉 & 𝑉 ' DC' NDC' BS' (a) (b) Figure 2: An example graph where V 1 = f (V 2 , V 3 , V 4 ). (a) the true graph where DC = {V 1 , V 2 , V 3 , V 4 }, NDC = {V 5 , V 6 , V 7 }, and BS = {V 2 →V 5 , V 3 →V 6 , V 4 →V 6 }. (b) the estimated graph by GES, where BS' = {V 2 →V 5 , V 1 →V 6 , V 2 →V 6 , V 4 →V 6 }Lemma 1 (Conditional Independence) Any deterministic variable, given the rest deterministic variables in DC, is always conditionally independent from any non-deterministic variable in NDC.Basic idea of the proof. Again take Figure 1 as the example. Given {V 1 , V 2 }, V 3 will always be conditionally independent from V 4 , because V 3 can be perfectly determined by {V 1 , V 2 } with no extra noise term, the estimated residue for regressing V 3 on {V 1 , V 2 } will be close to 0. Therefore, V 4 ⊥ ⊥ V 3 |{V 1 , V 2 } holds true, and similarly we haveV 4 ⊥ ⊥ V 2 |{V 1 , V 3 } and V 4 ⊥ ⊥ V 1 |{V 2 , V 3 }.That is why DNES is an empty set in Figure 1 (b). The detailed proof is given in Appendix A3.Under the umbrella of Lemma 1, the faithfulness assumption is violated as long as the deterministic relations are present. The key rule of constraint-based method (e.g., PC algorithm) is that: as long as we can find at least one conditional set or an empty set, so that two variables are independent or conditionally independent, then the edge between these two variables in the graph will be removed. Therefore, we can conclude that using constraint-based methods (e.g., PC algorithm) which rely on faithfulness to deal with the deterministic relations can be problematic.However, benefiting from the recent theoretical progress on exact score-based methods, which do not explicitly rely on faithfulness assumption, it enables us to deal with deterministic relations from an intuitive view. Here, we are inspired by the lemma as follows.Lemma 2 (Linear Identifiability of Exact Search (Ng et al., 2021) ) Exact score-based search with BIC score asymptotically outputs a DAG that belongs to the MEC of the true DAG G if and only if the DAG G and distribution P satisfy the SMR assumption.According to Lemma 2, in the linear case, as long as the SMR assumption is satisfied, the exact score-based method with BIC score (Schwarz, 1978) can asymptotically obtain the true MEC. Then, we can extend the theoretical result from linear to nonlinear scenarios. The exact score-based method with generalized score (Huang et al., 2018) can also asymptotically output the true MEC.Theorem 3 (General Identifiability of Exact Search) Exact score-based search with generalized score asymptotically outputs a DAG that belongs to the MEC of the true DAG G if and only if the DAG G and distribution P satisfy the SMR assumption and some mild conditions are satisfied.Remarks: Based on the theoretical findings in Lemma 2 and Theorem 3, the exact score-based methods, which do not require faithfulness but SMR, pave a promising way to deal with the deterministic relations for causal discovery. However, one critical disadvantage of the exact methods is their low computational efficiency and poor scalability. To that end, we propose a novel framework, called DGES, which is demonstrated in section 3. The identifiability conditions for DGES are provided in section 4. 
determinism-aware greedy equivalent search (dges): 
 In this section, we will introduce our proposed DGES in detail. Throughout this paper, we consider the general case where some variables are deterministic while others are non-deterministic. There-Algorithm 1 DGES: Determinism-aware Greedy Equivalent Search Input: data matrix D ∈ R n×d Output: a causal graph G 1: (Phase 1: Run Greedy Search Globally) Run greedy equivalent search on the whole set of variables to obtain an initial graph. 2: (Phase 2: Detect Deterministic Clusters) Detect the clusters of deterministic variables, by checking whether one variable can be perfectly represented by its neighbors. 3: (Phase 3: Run Exact Search Partially) Perform the exact search exclusively on the deterministic clusters and their neighboring variables.fore, we can divide the whole causal graph into three parts: DCs, NDC, and BS. Regarding the BS part, in general, there are two scenarios. The cases, where NDC variables cause DC variables, can be trivially solved by GES, more details are given in Appendix A1. However, in the cases, where DC variables cause NDC variables, GES can be problematic. One example is given in Figure 2 . Please note that although the graph in the example is directed, our method aims to identify the MEC, which may contain undirected edges as well.Regarding NDC, the papers (Chickering, 2002; Huang et al., 2018) have shown the identifiability up to MEC of GES with BIC score or generalized score. As for DC, we cannot determine the edge directions without further assuming certain types of functional causal models, such as linear non-Gaussian model (Shimizu et al., 2006; Yang et al., 2022) and so on. Therefore, we focus on BS and aim to identify those sets of edges with mild assumptions, and we aim for a general framework where we do not assume any functional forms, as explained below.In general, DGES contains three phases: Firstly, we run GES for the whole datasets, to get the initial causal graph. As mentioned above, GES has proved to be identifiable up to MEC with the nondeterministic relations, therefore, it is not necessary to run exact search for NDC part. Meanwhile, as demonstrated by Lu et al. (2021) , GES may get sub-optimal results when the faithfulness assumption is violated, e.g., when there are deterministic relations. An example is given in Figure 2 . Therefore, we need to partially conduct exact search based on the result of GES to accurately identify BS, which motivates the following phases. Secondly, we aim to detect the DCs and their neighbors. If one variable can be perfectly represented by its neighbors, we may conclude that it is a deterministic variable, and this variable together with its neighbors compose a DC. Thirdly, we perform the exact search exclusively on the DCs and their neighbors. The general framework is given in Algorithm 1.During the phase 1 with greedy search and phase 3 with exact search, a proper score function is inevitably needed. For any scoring criterion S(G, D), we say that a score is decomposable if it can be written as a sum of local scores, where each local score is a function of only one variable and its parents. Following the property, the score of a DAG G can be represented asEQUATIONUnder the linear Gaussian model, the BIC score Schwarz (1978) is preferred, which is given asEQUATION)where L is the maximized value of the likelihood function of the model based on the observed data D related to V i and PA i , k denotes the number of edges between V i and PA i in G, n is the number of data samples in D, λ ′ is the penalty parameter, Σ is the variance of the noise term.However, in the deterministic scenarios, the estimated noise variance Σ will asymptotically get closer to 0, which leads to numerical error because of the term log | Σ|. To deal with such an issue, we provide the adjusted BIC score, formulated asEQUATIONwhere ξ is a small constant, and ξ > 0.Under the general nonlinear model, the generalized score (GS) (Huang et al., 2018) which is in a non-parametric form is favored. There are two types of likelihoods as introduced in the paper, for computational efficiency, we choose the generalized score with cross-validated (CV) likelihood.S GS (V i , PA G i ) = 1 Q Q q=1 ℓ(F (q) i |D (q)0,i ), and ℓ(EQUATIONwhereA i = K1(q) Vi ( K1(q) P A G i + n 1 λI) -1 , B i = A i I + n 1 λA T i A i -1 A T i , λ is the regularization parameter, n 1 is the sample size of each training set, n 0 is the sample size of each test set, n = n 1 + n 0 , D (q)1,i and D (q) 0,i are the corresponding data of variable V i and its parents, K1(q) Vi denotes the centralized kernel matrix of the q-th training set of V i , K0Vi denotes that of the q-th test set of V i , and similar notations are used for other kernel matrices.Terminologies. In this section, we demonstrate how to detect the DCs. First of all, we would like to introduce some terminologies for analysis. A root deterministic variable (RDV) is the variable which can be perfectly represented by others in a DC. A minimal deterministic cluster (MinDC) refers to the variable set where there is only one RDV. A maximal deterministic cluster (MaxDC) refers to the union of all the DCs if there are multiple DCs in the graph. Note that in one causal graph, there are possibly multiple DCs while there should be just one NDC, we allow different DCs to share overlapping deterministic variables. Meanwhile, there could possily be multiple MinDCs but only one MaxDC. An extended deterministic cluster (EDC), contains all the deterministic variables and their direct neighbors. For example in Figure 2 (a), the RVD is V 1 , both MinDC and MaxDC are {V 1 , V 2 , V 3 , V 4 } since there is only one DC, and the EDC is {V 1 , V 2 , V 3 , V 4 , V 5 , V 6 }.As shown in Figure 2 (b), GES may output sub-optimal solutions where the estimated BS' contains more edges than the true one. Therefore, we need to rerun an exact search in order to recover the true BS under mild assumptions. Prior to running the exact search, it is essential to detect the true DCs and obtain their neighbors, i.e., the EDC. Based on the initial graph G 0 given by GES in the first phase, we can infer that the deterministic variables in G 0 will always present as a connected graph, though the edges may be different from the true ones. In other words, GES may output a sub-optimal solution G 0 , where the skeleton and directions related to the DC and BS can be different from these in the true graph G, however, GES can always identify the correct set, which covers the true EDC. Therefore, it is reasonable and applicable to detect the true EDC by GES. Note that GES outputs a MEC which contains both directed and undirected edges. Furthermore, we provide the following theorem.Theorem 4 (Representation & Perfect Representation) Let X be a random variable in the graph and Z be the set of all direct causes and undirected neighbors of X, where X and Z are with domain X and Z, respectively. Define a RKHS H X on X with continuous feature mapping ϕ X : X → H X .Consider a regression framework in the RKHS: ϕ X (X) = F (Z) + u, where F : Z → H X and u represents the regression residue.(i) X can be represented by Z if and only ifEQUATIONwhere Σ u is the variance matrix of the residue,Σ u = R T u R u , R u = ε(K Z + εI) -1 ϕ(X), ε is a small positive regularization parameter for kernel ridge regression, and K Z is the centralized kernel matrix of Z.(ii) X can be perfectly represented by Z, if and only if 1) X can be represented by Z and, 2) X cannot be represented by any subset Z s of Z, where 0 < |Z s | < |Z|.Remark. If one variable X can be perfectly represented by its direct causes and undirected neighbors Z, we can conclude that X is a RDV, and X and Z forms a MinDC. Based on the above results, we can detect all the MinDCs and EDC, which is then fed into Phase 3 for exact search. 
identifiability conditions: 
 In this section, we provide the identifiability conditions of DGES. The conditions are presented in a general form, applicable to both linear and nonlinear causal models. As mentioned above, in a general deterministic system, the whole causal graph mainly can be divided into three parts: DCs, NDC, and BS. In this paper, we focus on the identifiability for the BS and NDC parts.Theorem 5 (Partial Identifiability) Denote a causal graph G with deterministic relations. Let V i be any non-deterministic variable in G, and PA i be the set of direct causes or undirected neighbors of V i in one MinDC. Suppose the following conditions hold  
experiments: 
 To validate our theoretical findings and show the efficacy of our method, we conducted extensive experiments on simulated and real-world datasets. For simulated datasets, we evaluate linear and nonlinear causal models, as shown in Section 5.1. For real-world datasets, we evaluate a set of variables extracted from the pharmacokinetics dataset Grzegorzewski et al. (2021) in Section 5.2.Datasets and Implementations. The true DAGs are simulated using the Erdös-Rényi model (Erdős et al., 1960) with the number of edges equal to the number of variables. The data is generated according to the functional causal model V i = Vj ∈PAi b ij f i (V j )+ϵ i , where V j ∈PA i is the j-th direct cause of V i , ϵ i is the random noise related to variable V i , and f i is causal function. For deterministic variables, the noise term is removed, then the model becomesV i = Vj ∈PAi b ij f i (V j ).For each setting, we randomly choose one RDV or two RDVs where each RDV has at least two parental nodes, in other words, there are one DC or two DCs in the generated graph. We evaluate both linear and nonlinear models. For linear Gaussian model, we let f i (V j ) = V j and ϵ i follows Gaussian distribution whose mean is zero and variance is uniformly sampled from U(1, 2). For nonlinear model, f i is randomly chosen from linear, square, sinc, and tanh functions, and ϵ i is sampled from uniform distribution U(-0.5, 0.5) or Gaussian distribution N (0, 1). For the exact method in Phase 3, we choose A* (Yuan & Malone, 2013) without the heuristic tricks. Figure 3 : Simulated results on graph with one deterministic cluster. We evaluate different functional causal models on varying number of variables and samples, respectively. For each setting, we consider SHD (↓), F 1 score (↑), precision (↑), recall (↑) and runtime (↓) as evaluation criteria.Baselines and Evaluations. We compare our DGES with other baselines, including DPC Glymour (2007) , GES Chickering (2002) , and A* Yuan & Malone (2013) . We compare the MEC of the output by all methods. For each method, we consider the structural Hamming distance (SHD), the F 1 score, the precision, the recall, and the computational time as evaluation criteria. Note that we only evaluate the BS part which we can identify in the graph under mild assumptions. We conduct the experiments on varying number of variables, varying number of samples, and some other hyperparameter studies. For linear model, we evaluate variable d ∈ {8, 10, 12, 14, 16} while fixing sample size n = 500, and evaluate sample n ∈ {100, 250, 500, 1000, 2000} while fixing variable d = 8. For nonlinear model, we evaluate variable d ∈ {6, 7, 8, 9, 10} while fixing sample size n = 100, and evaluate sample n ∈ {50, 100, 150, 200, 250} while fixing variable d = 6. We run 10 instances with different random seeds and report the means and standard deviations.The simulated results about graphs with only one DC has been shown in Figure 4 , and the results with two DCs (which may have overlapping variables) are given in Figure A3 of Appendix. Clearly, when there are more deterministic variables in the system, the runtime of our DGES will obviously increase. The reason is because there are more deterministic variables to be detected and fed into Phase 3 for exact search. According to the results, the general performance of DGES is competitive compared to other baselines. We observe that the exact method A* and our proposed DGES generally outperform the other baselines such as GES and PC across different criteria and settings. Meanwhile, score-based method GES presents better performance than constraint-based method DPC in a deterministic system. Accordingly, we can infer that scorebased methods possess a holistic view for causal discovery, which may have less influence by the issues of deterministic relations, compared to constraint-based methods. As the number of variable increasing, the runtime of A* will increase rapidly. Compared to A*, the increasing of runtime for DGES is much more steady, both in linear and nonlinear models. Due to the space limit, the implementation details and the experimental results with two DCs are provided in Appendix A4. We also evaluate our method and the baselines on a real-world dataset, namely the pharmacokinetics dataset Grzegorzewski et al. (2021) , which is an open database for pharmacokinetics information from clinical trials. It provides curated information mainly in three categories: the characteristics of the studied patients (e.g., age, height), applied records of the studied drugs (e.g., the dosing of drug, the route of application), and the measurement records (e.g., the clearance, T max , C max when one certain person takes one certain drug), and we name the three categories of variables as class "A", "B", and "C", respectively. Out of more than 200 variables and more than 200000 data samples containing missing values, we cleaned the data and finally obtained 32 important variables with 4194 data samples which may contain deterministic relations. The 32 variables contains 16, 4, and 12 variables from the class "A", "B" and "C", respectively. Considering the rather large number of graph and large sample size, we use linear BIC score instead of nonlinear generalized score to conduct the search. As shown in Figure 4 , our method can successfully detect at least three deterministic clusters: {height, weight, BMI}, {T max , C max }, {AU C inf , AU C end }. 
discussion and conclusion: 
 Discussions. While presenting a versatile framework, our paper does have certain limitations. First of all, our work provides a general framework under mild assumptions, which cannot identify the skeleton and directions in the DC part so far. Without further assumptions such as the linear non-Gaussian causal model, current information is not enough to identify the DC part. More discussion is in Appendix A1. Furthermore, inherited from the disadvantages of exact methods, our method also can be computationally slow in Phase 3 when there are a large number of deterministic variables. 
 
 Appendix: This paper dives into the challenges of causal discovery in the presence of deterministic relations. Notably, we make a compelling discovery that exact score-based methods can elegantly address the deterministic issues, provided the SMR assumption is met. In an effort to bolster efficiency and scalability in a deterministic system, we propose the novel and versatile framework called DGES, encompassing both linear and nonlinear models, as well as both continuous and discrete data types. Furthermore, we establish the identifiability conditions for DGES, which is easy to be satisfied. Hopefully, our method can help to construct a holistic view to see the deterministic relations. The extensive experiments, conducted on both synthetic and real-world datasets, validate our theoretical findings and the efficacy of our method. In the future, we will enhance our method to achieve the fully identifiability among the deterministic variables, by incorporating more assumptions. Q1: Why current method cannot identify the skeleton and directions in the DC part?A1: To achieve that goal, we usually need strong assumptions on the underlying functional causal model, i.e., Yang et al. (2022) assumed linear Non-Gaussian model. However, those assumptions are not in alignment with our goal of a general method, i.e., with no restricted assumption on the underlying functional causal model. That is why currently our method cannot identify the skeleton and directions in the DC part. However, fortunately, we can exactly find out which set of variables are in the DCs using some DC detection strategies, as shown in Section 3.3.Q2: Why the cases, where NDC variables cause DC variables, can be trivially solved by GES?A2: Let's consider this example. Three variables compose a DC (V 1 , V 2 , V 3 , andV 1 = V 2 + V 3 ),and denote another variable from NDC as V 4 . In this case, there must not be an edge from V 4 to V 1 , because V 4 will be in DC rather than NDC, if so. Then, if V 4 causes V 2 , there will be definitely an edge between them by GES, because V 4 is clearly dependent on V 2 and theoretically GES can capture this dependence based on the local consistency.Q3: Why GES can be problematic in the cases where DC variables cause NDC variables? A3: Take Figure 2 as an example, where the true edges related to V 6 include V 3 → V 6 and V 4 → V 6 . However, during the forward phase of GES, it is very likely that the edge V 1 → V 6 can be added in the beginning. Then the edges V 2 → V 6 and V 4 → V 6 are added subsequently. During the backward phase of GES, the edge V 1 → V 6 will not be deleted, because V 1 also contains information from V 3 , in other words, V 6 is represented by V 1 , V 2 and V 4 by GES, which contains more edges than the ground-true. Therefore, in this case GES can be problematic, and we need exact search under the SMR assumption for post-processing, in order to correctly identify the BS part.Q4: What the characterization of Markov equivalence class is in the context of having deterministic relations in the whole graph?A4: Regarding only the variables involved in BS and NDC (that is how Theorem 5 claimed), the characterization of Markov equivalence class (MEC) is still the same in the context of having deterministic relations or not having such relations.However, if we consider the whole graph, i.e., all of the variables in DCs are also involved, the characterization of the Markov equivalence class should be different. As shown in the example of Lemma 1 and Figure 1 , there will be "spurious CI statements" caused by the deterministic relations, therefore, we need to remove those "spurious CI statements" for the new characterization of MEC.Q5: Why use kernel regression in Theorem 4?The reason why we use kernel regression is that: we are considering the general functional causal form, particularly, this theorem can be used for both linear and nonlinear functional relationships, Gaussian and non-Gaussian data distributions, which is in alignment with the general goal of our proposed method.For more details, inspired by (Zhang et al., 2012) , the functions ϕ X and F (•) that we use are all in the infinite Hilbert spaces, and we evaluate the representation with the Hilbert-Schmidt norm of the variance operator Σ u in infinite dimension. In this case, we can exhibit a general functional causal form.In this part, we will introduce more related works in causal discovery (Spirtes & Zhang, 2016) . As we mentioned in the main paper, constraint-based and score-based methods are two primary categories in causal discovery. Constraint-based methods utilize the conditional independence test (CIT) to learn a skeleton of the directed acyclic graph (DAG), and then orient the edges upon the skeleton. Such methods contain Peter-Clark (PC) algorithm (Spirtes & Zhang, 2016) and Fast Causal Inference (FCI) algorithm (Spirtes, 2001) . Some typical CIT methods include kernel-based independent conditional test (Zhang et al., 2012) and approximate kernel-based conditional independent test (Strobl et al., 2019) .Score-based methods normally use a score function and rely on a particular search strategy to look for the intended graph. The search strategy usually involve greedy search, exact search, or continuous optimization. The first continuous-optimization based method is NOTEARS (Zheng et al., 2018) , which casts the Bayesian network structure learning task into a continuous constrained optimization problem with the least squares objective, using an algebraic characterization of directed acyclic graph (DAG). Subsequent work GOLEM (Ng et al., 2020) adopts a continuous unconstrained optimization formulation with a likelihood-based objective. NOTEARS is designed under the assumption of the linear relations between variables, therefore, another subsequent works have extended NOTEARS to handle nonlinear cases via deep neural networks, such as DAG-GNN (Yu et al., 2019) and DAG-NoCurl (Yu et al., 2021) . Moreover, ENCO (Lippe et al., 2022) presents an efficient DAG discovery method for directed acyclic causal graphs utilizing both observational and interventional data. AVCI (Lorch et al., 2022) infers causal structure by performing amortized variational inference over an arbitrary data-generating distribution. These methods might suffer from various optimization issues, including convergence (Wei et al., 2020) , sensitivity to data standardization (Reisach et al., 2021) , and nonconvexity (Ng et al., 2023) . Since they are only guaranteed to find a local optimum, therefore the quality of the solution can not be guaranteed, even in the asymptotic cases.Besides the constrain-based and score-based methods, another major category of causal discovery methods is function causal model based methods. Those methods rely on the causal asymmetry property, such as the linear non-Gaussian model (LiNGAM) (Shimizu et al., 2006) , the additive noise model (Hoyer et al., 2008) , and the post-nonlinear causal model (Zhang & Hyvarinen, 2012) . Apart from those methods, there are also some hybrid methods, such as neural conditional dependence (NCD) method, which reframes the GES algorithm to be more flexible than the standard score-based version and readily lends itself to the nonparametric setting with a general measure of conditional dependence.In this section, we provide the proofs of theorems and lemmas in the main paper, including Lemma 1, Theorem 3, Theorem 4, and Theorem 5.Proof: Assume a deterministic cluster S = {X} ∪ Y , where X is any one variable in the DC, and Y is the set of the other deterministic variables in S.By the definition of determinisic relation, we can haveEQUATIONIn other words, we may also obtain X = g(Z) or Z = h(X) without a random noise term.When we are doing conditional independent test to evaluate the null hypothesis Y ⊥ ⊥ X|Z, where Y is any one non-deterministic variable in the system, then a standard procedure is to conduct regression in RKHS (Zhang et al., 2012; Huang et al., 2018) in the following formEQUATIONwhere ϕ, F 1 and F 2 are the nonlinear feature mapping in the RHKS.Then the null hypothesis Y ⊥ ⊥ X|Z holds true, if and only if the ∥Σ u ∥ 2 HS = 0 where Σ u is the variance matrix of two residues u 1 and u 2 .Given that X and Z are deterministically related, and also X = g(Z). Therefore, the residue term after the kernel ridge regression will always be 0 (Perfectly representation! Note that X corresponds to ϕ X and g(Z) corresponds to F 1 (Z) in the Eq. 7).In other words, ∥Σ u ∥ 2 HS = 0 will always holds true. Then, the null hypothesis will also hold true: Y ⊥ ⊥ X|Z.To summarize, we can conclude: Y ⊥ ⊥ X|Z will always hold true, if X and Z deterministically related. To extend this result from one variable Y to arbitrary non-deterministic variable, and extend the result from one variable X to arbitrary deterministic variable. We can conclude that: Any deterministic variable, given the rest deterministic variables in DC, is always conditionally independent from any non-deterministic variable in NDC.Proof ends.Proof: As suggested by the generalized score (Huang et al., 2018) , with proper score functions and seach procedures, asymptotically the resulting Markov equivalence class has the same independence constraints as the data generative distribution.(i) First of all, we would like to discuss the local consistency of generalized score.For the regression problem, one can define the effective dimension of the kernel space and the complexity of the regression function according to Caponnetto & De Vito (2007) . Then under mild conditions, the CV-likelihood score is locally consistent.Lemma 6 Suppose that the sample size of each test set n 0 satisfiesn 0 → ∞, n 0 n → 0 as n → ∞,and suppose that the regularization parameter λ satisfiesλ = O(n -b bc+1), where n is the total sample size, b is a parameter of the effective dimension of the kernel space with b > 1, and c indicates the complexity of the regression function with 1 < c ≤ 2.Lemma 7 Assume that all conditions given in Lemma 6 hold. With the CV likelihood under the regression framework in RKHS as a score function and with the GES search procedure, it guarantees to find the Markov equivalence class which is consistent to the data generative distribution asymptotically.Lemma 7 ensures that, with proper score functions and seach procedures, asymptotically the resulting Markov equivalence class has the same independence constraints as the data generative distribution. For the complete proofs, please refer to the Appendix A5 of paper (Huang et al., 2018) .(ii) Then, We will provide the proof by contra-positive in both directions based on the consistency of the generalized score as shown above.Suppose that exact score-based search asymptotically outputs a DAG H (having the highest generalized score) that does not belong to the MEC of the true DAG G. Since the generalized score is known to be consistent, (H, P) must satisfy the Markov assumption, because otherwise its generalized score is lower than that of the true DAG G and exact search would not have output H. By assumption, the generalized score of H is higher than that of G, which, by the consistency of generalized, implies that |H| ≤ |G|, and therefore, (G, P) does not satisfy the SMR assumption.2) "Only if" direction: Suppose that (G, P) does not satisfy the SMR assumption. Then there exists a DAG H not in the MEC of G such that |H| ≤ |G|, and (H, P) satisfies the Markov assumption. Without loss of generality, we choose H with the least number of edges. We first consider the case in which |H| < |G|. Since both H and G satisfy the Markov assumption, by the consistency of generalized, the generalized score of H is higher than that of G, which implies that exact score-based search will not output any DAG from the MEC of G. For the case with |H| = |G|, since they are both Markov with distribution P, they have the same generalized score. Therefore, exact search will output a DAG that belongs to the MEC of either H or G, and is not guaranteed to output a DAG from the MEC of the true DAG G.Proof ends. OF THEOREM 4 𝑉 ! 𝑉 " 𝜃 𝑖 (℧) 𝑉 # 𝑉 $ 𝜃 𝑗 (℧) 𝜓 ℓ (℧) 𝑉 % (a) (b)V 3 = f (V 1 , V 2 ), V 4 = g(V 1 , V 2 ).Proof: We will divide the whole proofs into two parts. For the first part, we aim to prove the "representation" theorem, and for the second part, we aim to further prove the "perfect representation" theorem.(i) Representation: Assume there is a MEC M, which contains both directed edges and undirected edges. Let X be a random variable in M and Z be the set of all non-descendant neighbors including direct causes and undirected neighbors of X. Suppose the random variables X and Z are over measureable spaces X and Z, respectively. EQUATION3 = f (V 1 , V 2 ). (a) A non- deterministic variable V 4 connects to {V 1 , V 2 , V 3 }. (b) A non-deterministic variable V 4 connects to {V 2 , V 3 }. (c) A non-deterministic variable V 4 connects to {V 3 }.Here among the three graphs, only the graph (c) can be partially identified.need the assumptions of Markov and non-deterministic faithfulness (See Assumption 1 and 3). Then in the third phase, we need to perform the exact search exclusively on the EDC, where the Sparsest Markov Representation (SMR) assumption will be needed. Let's take an example with four variables, where three of them are deterministically related, as shown in Figure A2 . Here among the three graphs, only the graph (c) can be partially identified, and the graph (a) and (b) cannot achieve partial identifiability.We further assume a linear functional causal model, then we can formulate the deterministic relationship asEQUATIONwhere a, b, c are any linear coefficients. Based on the above formulation, the causal equation of variable V 4 in Figure A2 (a) can be represented asEQUATIONwhere ϵ is the random noise injected into V 4 . Clearly, the above four equations are all valid, in other words, V 4 can be possibly represented by different sets of variables, meaning that this case is not guaranteed to be identified.Regarding the variable V 4 in Figure A2 (b), the causal equation can be represented asEQUATIONAgain, the above three equations are all valid, in other words, V 4 can be possibly represented by different sets of variables, meaning that this case is also not guaranteed to be identified.However, in Figure A2 (c), things are different. The causal equation of variable V 4 can be represented asEQUATIONWhen the SMR assumption is satisfied, we can identify the only one case, which is V 3 → V 4 . Now, we extend the three-variable case to the general linear case where there is a MinDC with the cardinality | MinDC |. And we can easily conclude the true conditions to be:| PA i | < | MinDC | - 1.Furthermore, we extend the linear to nonlinear case, where we can also conclude that the listed conditions ensures the partial identifiability.Proof ends.We provide the implementation details of our method and other baseline methods for synthetic datasets.• DPC (Glymour, 2007) : The method is an extension for traditional PC algorithm (Spirtes et al., 2000) , the key idea is that: every time when we do the conditional independence test, we aim to remove the potential deterministic variables from the conditioning set so that the faithfulness will not be violated. Here we follow the paper, and use the covariance to measure the closeness of two variables. If the covariance between two variables are greater than 0.9, we then remove the variable from the conditioning set in conditional independence test. Meanwhile, for linear Gaussian model, we choose FisherZ test, while for nonlinear model we choose kernel-based test (Zhang et al., 2012) , and the significance level is set to α = 0.05 by default. We implement this method based on the Causal-learn package https://github.com/py-why/causal-learn (Zheng et al., 2023) . • GES (Chickering, 2002) : This method is a classical score-based method with greedy search. Our implementation is based on the code from https://github.com/ juangamella/ges. For linear Gaussian model, we use BIC score. And for general nonlinear model, we use generalized score with cross-validation likelihood (Huang et al., 2018) . The penalty parameter for controlling the sparsity is set to 1. • A* (Yuan & Malone, 2013) : A* is one of the classical exact score-based methods. Actually, there are some heuristic algorithms proposed to accelerate the search procedure. Considering in our scenarios, we do not utilize any heuristic tricks for the experiments in order to ensure the accuracy of solutions. Our experiments are based on the implementations on the Causal-learn package https://github.com/py-why/causal-learn (Zheng et al., 2023) . • DGES (ours): The first phase of our method is to run GES, as introduced above. The exact search in the third phase we incorporate is the A* as mentioned above. During the second stage, when we aim to detect the deterministic clusters and checking whether a variable can be perfectly represented by some others, we set that if the term ∥Σ u ∥ 2 HS < 1e-3, although theoretically the value should exactly be zero. Meanwhile, the regularization parameter for the kernel ridge regression is set to 1e-10.Figure 4 in the main paper presents the simulated results focused on graphs containing just a single deterministic constraint (DC). In contrast, Figure A3 in the Appendix offers insights into scenarios involving two DCs, even allowing for the possibility of overlapping variables. An evident Figure A3 : Simulated results on graph with two deterministic clusters. We evaluate different functional causal models on varying number of variables and samples, respectively. For each setting, we consider SHD (↓), F 1 score (↑), precision (↑), recall (↑) and runtime (↓) as evaluation criteria.trend emerges: as the system incorporates more deterministic variables, the runtime of our proposed DGES inevitably escalates. This phenomenon can be attributed to the increased number of deterministic variables demanding detection and inclusion in Phase 3, where an exact search is performed.It is worth noting that as the number of variables in the system increases, the runtime of A* experiences a rapid surge. In stark contrast, DGES exhibits a more stable increase in runtime, demonstrating its efficiency and suitability for both linear and nonlinear models.The outcomes gleaned from these experiments collectively indicate that DGES exhibits competitive performance compared to established baselines. Notably, the exact method A* and our proposed DGES consistently outperform other baseline methods like Greedy Equivalence Search (GES) and PC, across a spectrum of evaluation criteria and diverse settings. It is intriguing to note that in deterministic systems, the score-based method GES consistently outperforms the constraint-based method DPC. This observation suggests that score-based approaches maintain a comprehensive perspective on causal discovery, which appears to be less susceptible to the challenges posed by deterministic relationships, unlike constraint-based methods.We also conducted the experiments in a standard setting, where there is no deterministic relation at all. We consider the linear Gaussian model with a varying number of variables. We evaluate the SHD, the F 1 score, the precision, the recall, and the runtime. In this case, we evaluate based on the whole graph. 


Decision: In this manuscript, the authors study the problem of causal discovery in the presence of deterministic dependencies. The initial reviews were already quite positive, while during the rebuttal the authors convincingly addressed many questions and key concerns, leading to improved scores. The reviewers praise the clarity of the presentation, the relevance and novelty of the topic, as well as the technical treatment. Not all are equally impressed by the empirical evaluation, and I agree this could be improved upon both in terms of competing methods and data settings. All in all, this paper clears the acceptance threshold with a wide margin. I recommend the authors to use the additional page to address the questions that arose during the discussion and include additional results (such as provide presented during the discussion).

Reviews: review: paper_summary: paper_summary: Summary
In this paper, the authors develop an approach to causal discovery with deterministic casual relations. They adapt the GES algorithm to deal with common faithfulness violations due to spurious conditional independences.
strength_weakness: strength_weakness: Weaknesses
- It's not quite clear how common or relevant these deterministic relationships are, and how different the resulting output networks really are
- The theoretical results seem like they could be improved (Q6)
- The evaluation on only a single real-world dataset seems rather weak (Q8,9)
questions: questions: Questions
1. Is there any particular reason why we adapt GES specifically? Could we adapt other score-based methods in the same way?
2. Can you explain how the results you obtain differ from those obtained by other methods to deal with faithfulness violations, e.g. [1]?
3. Is there anything we can do in the low sample, high-dimensional case, where every variable's sample can be written deterministically in terms of other variables?
4. Currently you search over all subsets of DC to find the MinDC a variable belongs too. Is there any way to make this more efficient?
5. Can you explain why in (3) you need to add a small constant to the covariance, but in the corresponding terms in (4) you do not?
6. Theorem 3 seems like it could be improved. For example, if $X_{2i-1} \rightarrow X_{2i}$ for all $i$, but no other edges exist, then we should be able to say more about the independence of different MinDCs from each other?
7. In Figure 3(d), and particularly (b), why is the runtime of DGES almost as high as $A^\star$?
8. In the real-world dataset, are any of the discovered MinDCs interesting? All three of them seem to be rather simple. Are there example networks where the MinDCs would not be predictable by domain experts?
9. On a related note, does the graph obtained by specifically including these deterministic relations qualitatively differ from what we would have found without them? Is BMI a causally relevant variable in the first place, rather than a--possibly rather arbitrary--construct?

References
[1] A Weaker Faithfulness Assumption based on Triple Interactions
limitations: limitations: It's currently not clear how relevant the ability to deal with these deterministic relationships truly is
paper_summary: paper_summary: This paper focuses on the problem of deterministic dependencies in causal structure learning.  Many algorithms for causal structure learning assume faithfulness between the conditional independencies present in the data and those implied by the graph, and this assumption can be violated when deterministic dependencies are present.  The authors propose a modified version of GES, DGES, for datasets where determinism is present.  DGES adds additional steps to identify deterministic dependencies between variables, performs modified versions of the GES forward and backward passes, and then does an exact search to orient edges around the deterministic nodes.  The authors perform experiments on synthetic data, as well as a real world dataset, and find that DGES consistently performs well.
strength_weakness: strength_weakness: This paper could use some work on the motivation.  In the introduction and Section 2, the authors convincingly show that the PC-algorithm (and other constraint-based algorithms) does not work in the presence of deterministic dependencies.  The authors describe score-based methods in the introduction (though don't say either way if they generally handle determinism) and explain that some exact score-based methods are able to handle determinism just fine.  From this, the take-away seems to be "don't use constraint-based methods; use exact score-based methods."  However, the authors then go on to expand on GES, a non-exact score-based methods, proposing a modified version of it as their solution.  In Section 2.3, the authors then point out that exact score-based methods are computationally inefficient - this is good to know, but would have been helpful to also mention in the introduction.  However, to this point, I'm still left unsure about whether or not GES can handle determinism as-is, which is strange, given that it's the basis of the proposed DGES.  It in't until Section 3.3 that I think I got my answer to (1) - "As demonstrated by Lu et al. [19], GES may get sub-optimal results when the faithfulness assumption is violated".  This is important motivation and should be present in the introduction or, at the very least, Section 2.  Saving it until page 7/9 just leaves the reader unsure about the necessity of the proposed method for far too long.

I also think the explanation provided (i.e., someone else showed that it may be "sub-optimal") is a bit lacking, given that it's partially the foundation of this work. (it's clear from the experimental results that GES does not handle determinism well, but simply saying it "may" be "sub-optimal" is vague and gives no sense of the severity of the issue) Apart from the quoted line in Section 3.3, Section 3.2 says that the authors "add some extra constraints during the forward and backward steps and adjust the score function due to the deterministic relations."  The authors then go on to describe GES and their modifications, but I don't see any discussion about the motivation for those modifications.  Stronger justification would help a lot before getting into the details.

In Theorem 2, you say that exact score-based search works if the SMR assumption is satisfied and also "some mild conditions are satisfied".  "Mild conditions" could be basically anything - at the very least, allude to what type of conditions they are, even just in a footnote.

In line 204, the line "we need to traverse all the possible combination sets of DC" is odd and unclear.  What is "all the possible combination sets of deterministic cluster"?  I thought there was only one DC, so I don't know how we know have combinations of deterministic clusters... I think this is referring to all combinations of variables within the DC??

In Figure 3, I don't see the units for runtime, either in the graph or in the text.  Please add those, unless I'm just missing them somewhere.

The one real-world dataset is weak.  I don't believe there is any ground truth being compared against, correct?  As it stands, I'm not sure what I'm supposed to get out of Figure 4.  It's a very busy graph with a lot of abbreviations, so the takeaway just ends up being "DGES can output a graph".  You then call-out in the text that DGES was able to detect 3 MinDCs, but it's hard to verify this, since they're not highlighted in any way in Figure 4.  If you want to include Figure 4 here, marking the edges that are deterministic vs probabilistic separately would help a lot.  Also, the text makes it sound like DGES does great on this dataset by calling out, for example, that it got the MinDC {height, weight, BMI}.  However, this comes across a bit disingenuous.  We know the ground truth is height -> BMI <- weight.  When I located those variables in Figure 4, however, the structure I actually see is BMI -> weight -> height, which is definitely wrong.  I'd be interested to know how often other methods are able to correctly orient deterministic functions like this one in the data.  Looking at Appendix 6, GES appears to make the same mistake (BMI -> weight -> height).  However, the text in the main paper discussing these results comes across as fully positive about the performance of DGES.  Some acknowledgement that these MinDCs are not perfectly determined (and making that a lot easier to see in Figure 4 by marking the deterministic edges and maybe highlighting these specific clusters that you reference) would help a lot.

These don't affect my score, but there are a number of typos and grammatical issues.  I'd recommend another editing pass or two.  Some examples I noted:
- line 52 - sparest -> sparsest
- line 55 - [The] "d-separation condition is proposed"... (need an article)
- line 63 - missing period after "works"
- line 71 - "...graphs, therefore, we propose..." is a run-on sentence
- line 302 - "As the number of variable increasing" -> "As the number of variables increases"
questions: questions: Can you explain more about how Assumption 2 functions as an assumption, as opposed to as a definition?  I understand the idea of the "sparsest MEC which satisfies the Markov assumption", so is the idea behind the SMR assumption that we assume the algorithm will return not just the MEC but the sparsest MEC?

Did you try any experiments where you know there are no deterministic variables present?  It would be helpful to know if it's safe to just always use DGES, even if we're not 100% sure that there is determinism.
limitations: limitations: I think for the most part, the authors address the limitations of DGES.  The only pieces I think I'm missing are what the "mild conditions" are for general identifiability of exact search and how DGES performs in situations with no determinism.



Note: The authors adequately addressed my concerns, so I am increasing my score from 7 to 8.
paper_summary: paper_summary: This paper addresses the challenge of causal discovery in the presence of deterministic relationships by developing a novel framework called Determinism-aware Greedy Equivalent Search (DGES). DGES improves efficiency and scalability in detecting deterministic relations through a three-phase process and is validated with both simulated and real-world datasets.
strength_weakness: strength_weakness: 1. Even if real-world scenarios frequently encounter deterministic relations, the observed data contains noise (e.g., measurement noise) which is very difficult to control. What is the implication of such scenarios?
2. Results does not show superior performance over baselines. This is the major concern.
questions: questions: See the weaknesses section
limitations: limitations: Limitations are discussed.
paper_summary: paper_summary: The paper delves into the challenges of causal discovery from observational data, with a particular focus on deterministic relationships often found in real-world scenarios. 
Firstly, the paper demonstrates that exact score-based methods can effectively handle deterministic relationships under mild assumptions. Building on this, it introduces a novel framework called Determinism-aware Greedy Equivalent Search (DGES), which enhances the efficiency and scalability of dealing with deterministic relations and accommodating both continuous and discrete data types.
DGES operates through three key phases: detecting minimal deterministic clusters (MinDCs) in the data, running a modified version of Greedy Equivalent Search (GES) to create an initial causal graph with added constraints for deterministic relations, and performing an exact search on these deterministic clusters and their neighbors to refine the graph and ensure sparsity.
Additionally, the paper establishes partial identifiability conditions for DGES under general functional models and it provides extensive experiments on simulated and real-world datasets to validate the practical efficacy of DGES.
strength_weakness: strength_weakness: * The algorithm presented in this paper guarantees a partial identifiability of the CPDAG. Which means it is even less informative than a partially oriented DAG.

* The paper's contribution appears somewhat limited, as it addresses the low computational efficiency and poor scalability of exact methods by compromising on general identifiability.

* The paper assumes causal sufficiency which is almost never satisfied in practice.

* Limited experimental results (see questions below)
questions: questions: * DGES sacrifices general identifiability for improved computational efficiency and scalability. Could you elaborate on the specific scenarios or types of data where this trade-off might be most problematic?

* Can you at least discuss how causal sufficiency can be relaxed? Would it be possible to imagine a combination between DGES and FCI (as it was done for GES and FCI)?

* DGES is designed to accommodate both linear and nonlinear relationships, various data distributions, and both continuous and discrete data. Are there any specific types of data or relationships where DGES performs exceptionally well or poorly?

* The success of exact score-based methods in your approach relies on the SMR assumption. Can you provide more details about this assumption and its practical implications? Do you know if it is satisfied in the real-world dataset?
limitations: limitations: The paper acknowledges certain limitations, such as difficulties in identifying the skeleton and directions in the DC part with overlapping deterministic variables, and the computational expense of Phase 3 when dealing with numerous MinDCs. However, it notes that these searches can often be executed simultaneously.

Comments: title: Thank you very much for your valuable time and insightful comments
Thank you very much for your valuable time and insightful comments
Thank you so much for checking the responses and updating your recommendation
Thank you so much for checking our responses and increasing your score
Response to Reviewer zDFG
Results on A New Real-world Dataset
Responses (3/3)
Responses (2/3)
Responses (3/3)
Responses (2/3)
comment: We sincerely appreciate the time and effort you invested in carefully evaluating our paper. Your constructive and insightful feedback has greatly enhanced our work. Thank you very much!
Thank you for the detailed response!  With the proposed changes, I will update my score.
We sincerely appreciate the reviewer for carefully checking our responses and engaging in a fruitful discussion with us. Your constructive feedback has significantly improved our paper! Thanks a lot!
Thank you for your responses. I've updated my score.
We sincerely appreciate the reviewer for checking our responses and increasing your score. Thanks again for your constructive comments!
I thank the authors for their response. I've read their response and I will increase my score accordingly.
We are so glad that our responses are helpful to address your concerns. Thank you very much for your constructive feedback and valuable time!
I thank the authors for their response. I think they have addressed my concerns. Therefore I will increase my score.
Thank you so much for your valuable time and follow-up questions. Below are our responses.

``` 
“Removing X3 leaves us with a perfectly good fully identified graph.”
```

- We completely agree with you that removing $X_3$ would yield a well-identified graph for describing the joint distribution of $\{X_1, X_2, X_4\}$. 
- However, for causal discovery, we have to finally present a graph with all four variables (i.e., to add $X_3$ back into the graph) because, as mentioned above, we don't know a priori whether $X_3$ is a construct or a causal variable. Any variable may exactly be of the user's interest. We cannot delete any variable from the final result graph.
- Then, how can we add $X_3$ back into the graph? Based on the result $\{X_1 \rightarrow X_4, X_2\rightarrow X_4 \}$, one intuitive way is to reintegrate $X_3$ back as a child of the variables that determine it, leading to a graph with the edges $\{X_1 \rightarrow X_4, X_2\rightarrow X_4, X_1\rightarrow X_3, X_2\rightarrow X_3 \}$. However, this results in a denser graph than the true underlying structure (that's how we justify "sparsity" above). Even worse, the critical information that $X_1$ and $X_2$ are affecting $X_4$ through $X_3$, is not shown in this reintegrated graph.

To summarize, it is not recommended to remove and reintegrate a variable for causal discovery to deal with deterministic relations. Any variable could be of interest to the users, and we aim to discover causal relations among all variables.

``` 
"Why shouldn’t we exclude determined variables after running your method?" 
```
- We totally agree that after running our method, one can exclude any determined variables as a postprocessing step. That is totally fine.
- The core argument in our paper is that one cannot bypass our method by directly excluding determined variables and then applying standard causal discovery methods like PC on the remaining variables. The reasons are discussed above.
Thank you for your response.

You say that the three graphs are not consistent with each other, but I don't understand why this matters? Removing $X_3$ leaves us with a perfectly good fully identified graph with both fewer variables and fewer edges, making it *more sparse*. Similarly, including BMI leads to a more sparse causal graph only if it is a mediator for the causal effects of height and weight on multiple other variables.

I understand that we can't tell a priori which variable to exclude, but my question is rather why we shouldn't do so after we have run your method
We really appreciate you taking the time to share your valuable comments and questions so promptly. Our responses to these questions are given below.

First of all, we apologize for the typo in A9. The four-variable example we had in mind was: {$X_1 \rightarrow X_3 \leftarrow X_2, X_3 \rightarrow X_4$}, where {$X_1,X_2$} $\mapsto X_3$ (deterministic relation) and $X_3 \rightarrow X_4$ is a normal edge with random noise.

  - If we simply remove $X_1$ and run PC on the remainder, we will obtain {$X_2 - X_3 - X_4$};

  - If we simply remove $X_2$ and run PC on the remainder, we will obtain {$X_1 - X_3 - X_4$};

  - If we simply remove $X_3$ and run PC on the remainder, we will obtain {$X_1 \rightarrow X_4 \leftarrow X_2$};

The three resulting graphs above are not consistent with each other. This example illustrates that we can NOT simply remove determined variables so that the remainder contains no deterministic relations, then run normal causal discovery methods on the remainder, and then reintegrate the determined variables into the resulting graph as children of variables determining them -- there are many ways of removing determined variables, while the results on each may be neither consistent with each other, nor with the true graph.

Second, regarding BMI, indeed, we agree with the reviewer that BMI can sometimes be regarded as an artifact/construct which is sufficiently calculable in terms of height and weight. On the other hand, BMI can also be seen as a variable with real causal meaning, as discussed in paper [59,60] -- BMI alone is involved in the causes of lung cancer. (Of course, one might argue that {BMI $\rightarrow V_{other}$} can be equivalently represented by {weight $\rightarrow V_{other} \leftarrow$ height}; However, that will result in a denser graph representation, violating the sparsity principle.)

As noted above, we acknowledge that there is an ongoing debate about whether BMI is a variable or a construct. However, our focus here is not this specific example. **What we want to emphasize is that, usually in real-world datasets with deterministic relations, we CANNOT distinguish between the causal variables and constructs without prior knowledge.** For instance, here we tend to see BMI as a construct (and try to remove it) simply because we have the prior knowledge on its definition. However, without prior knowledge, simply from the data perspective, we cannot distinguish between weight, height, and BMI -- they hold equal status. If we choose to remove BMI, then why not remove weight or height (as they can also be calculated from the remaining two)? Removing either height or weight makes less sense (as we tend to understand them with "real causal meaning"), and will also make the resulting graph incorrect (e.g., there are many other variables only affected by height or weight); However, we cannot distinguish them from BMI. This scenario motivates the {X1,X2,X3,X4} example as discussed above.

To summarize, we are neither trying to simply remove variables to eliminate deterministic relations (which may result in inconsistent results), nor trying to distinguish between causal variables and defined constructs (which is usually impossible without prior knowledge). Instead, we aim to put all variables together and recover the whole causal relations as well as the deterministic relations (up to equivalence class).

---

[59] Eyal Shahar. "The association of body mass index with health outcomes: causal, inconsistent, or confounded?." American journal of epidemiology, 2009.

[60] Robert Carreras-Torres, et al. "The causal relevance of body mass index in different histological types of lung cancer: a Mendelian randomization study." Scientific Reports, 2016.
Thank you for your extensive response, I have only a few follow-up comments/questions.

Q8/10: You say that it is absolutely possible to determine more deterministic relationships. However, the deterministic relationships shown here exist because that is how we have defined them. E.g., BMI is not a quantity measured independently of height and weight, it is defined in terms of these two quantities.

Q9: First, I am afraid I do not understand your example here. $X_1, X_3$ are unconditionally independent since $X_2$ is a collider, and removing $X_2$ does not condition on it. Therefore the graph upon removing $X_2$ should simply contain the edge $X_3 \to X_4$? Second, your explanation as to why BMI matters is about association. However, BMI itself is unlikely to be causal for health issues, and contains no information that is not already contained in height and weight. What is the point in keeping the variable, when all predictions based on it could already be made based on height and weight?
Dear Reviewers:

Thanks a lot for your thoughtful and constructive reviews. We are encouraged by some of your positive comments and inspired by your insightful suggestions. Here, we provide more details about our experiments on the new real-world dataset.

**Description:** We use US census Public Use Microdata Sample (PUMS), and follow the data preprocessing procedure outlined in [59], which is a modern version of the UCI Adult data set [60]. Datasets based on census data are widely considered in the algorithmic fairness literature [61, 62]. Here we choose 5 important variables, i.e., **{Age, Occupation, Sex, Annual_income (AI), and Adjusted_annual_income (AAI)}**, in total there are 3000 samples. Because of the potentially different timeframe of the survey cycle, AAI (= AI * Adjusted_factor) are the adjusted dollar amounts that they have earned entirely during the calendar year. Within one calendar year, this adjusted_factor is a constant. Here, we choose the data in 2021. Therefore, AAI and AI have a deterministic relation. 

**Results:** We compare our DGES with GES and PC. 

- The result of DGES is: {Sex $\rightarrow$ Occupation $\leftarrow$ AI, AI $\leftarrow$ AAI, Sex $\rightarrow$ AAI $\leftarrow$ Age}, 5 edges. 

- The result of GES is:  {Sex $\leftarrow$ Occupation -- AAI, AI -- AAI -- Age, AI $\rightarrow$ Sex $\leftarrow$ AAI}, 6 edges. 

-  The result of PC is: {Sex $\rightarrow$ Occupation $\leftarrow$ Age, AI -- AAI}, 3 edges.

**Analysis:** Compared with GES, the result of DGES is more sparse. Particularly, we can detect that AI and AAI have a deterministic relation, and GES gives redundant edges by {AI $\rightarrow$ Sex $\leftarrow$ AAI} while our DGES only keeps one edge {Sex $\rightarrow$ AAI}. Moreover, the result of PC is totally different from the other two. Clearly, in our DGES result, AI and AAI are still connected, and we can still see the BS, i.e., {AI $\rightarrow$ Occupation, AAI -- Sex, AAI--Age}. However, as a result of PC with FisherZ test, the BS becomes empty, which is exactly due to the violation of faithfulness. 

Thanks again for the time you dedicated to carefully reviewing this paper. We hope our new experimental results can adequately address your concerns.


Sincerely, Authors of Submission 9142.

---
References:

[59] Frances Ding, et al. "Retiring adult: New datasets for fair machine learning." NeurIPS, 2021.

[60] Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996.

[61] Razieh Nabi and Ilya Shpitser. "Fair inference on outcomes." AAAI, 2018.

[62] Zeyu Tang, et al. "Procedural Fairness Through Decoupling Objectionable Data Generating Components." ICLR, 2024.
Reference:

[58] Ignavier Ng, et al. "Score-Based Causal Discovery of Latent Variable Causal Models." ICML, 2024.
**Q9**: "There are a number of typos and grammatical issues. I'd recommend another editing pass or two."

**A9**: "Thank you for your careful reading and pointing out the typos. We will correct the noted sentences as follows:

- Line 52: "When the sparsest Markov representation (SMR) is satisfied"

- Line 55: "Deterministic relations have been considered in a few works of causal discovery [22-29]. The 'D-separation' condition [7] is proposed..."
- Line 63: "However, there is no identifiability guarantee in those related works. Moreover..."
- Line 71: "the exact score-based methods are feasible only for small graphs, and can be inefficient for large graphs. To enhance the efficiency and scalability, we propose a novel framework called DGES."
- Line 302: "As the number of variables increases.."

Your comments indeed help to improve the quality of our paper. We will update the above sentences and polish our paper thoroughly in light of your comments.
 

**Q10**: "Can you explain more about how Assumption 2 functions as an assumption, as opposed to as a definition? I understand the idea of the "sparsest MEC which satisfies the Markov assumption", so is the idea behind the SMR assumption that we assume the algorithm will return not just the MEC but the sparsest MEC?"

**A10**: Thanks for your interesting question. You are totally correct that we assume the algorithm will return the unique sparsest MEC, not just the MEC. The SMR assumption demonstrates that the true DAG G* is the sparsest DAG satisfying the Markov property. The term 'sparsest' refers to the minimal number of edges in the graphical model. The SMR assumption helps in simplifying our causal models by making constraints on the number of edges, which can use the least number of edges to show all the dependence in our data distributions. 


**Q11**: "Did you try any experiments where you know there are no deterministic variables present? It would be helpful to know if it's safe to just always use DGES, even if we're not 100% sure that there is determinism."

**A11**: Thank you so much for your thoughtful question. Actually we have conducted the experiment under linear Gaussian model with no deterministic relations at all. The result is in Figure A5 and the analysis is in Appendix A5.3. Basically, the performance of DGES almost aligns with that of GES regarding SHD, $F_1$, Precision and Recall. The runtime of DGES (unit: second) is a little bit higher than that of GES, due to the detection of MinDC in the first phase. Since the DC is detected to be empty, we have no need to further detect MinDCs, therefore phase 1 would still be fast.


Should there be any further questions or concerns, please let us know and we stand ready and eager to address them. We highly value your insights and would be more than pleased to provide any additional information or clarification you may require.
**Q5**: "In line 204, the line "we need to traverse all the possible combination sets of DC" is odd and unclear. What is "all the possible combination sets of deterministic cluster"? I thought there was only one DC, so I don't know how we know have combinations of deterministic clusters... I think this is referring to all combinations of variables within the DC??"

**A5**: Thanks a lot for pointing out this question. Indeed there was only one DC, however, there could be multiple MinDCs within this DC, because there might be multiple deterministic relations, even with overlapping deterministic variables. Let's consider this overlapping example, where the DC is {$V_1, V_2, V_3, V_4, V_5$}, $\{V_1,V_2\}\mapsto V_3$, and $\{V_2,V_4\}\mapsto V_5$. In this case, once we obtained the DC, we can further detect two MinDCs by iterating all possible combination variable subset of DC. Finally we can get {$V_1, V_2, V_3$} and {$V_2, V_4, V_5$}. We rely on MinDCs to run the modified GES. More details regarding how to get DC and MinDC are given in Appendix A3.1 and Algorithm A1/A2. In light of your comments, we will incorporate this example and explanation above into Section 3.1 to make our descriptions clearer.


**Q6**: "In Figure 3, I don't see the units for runtime, either in the graph or in the text. Please add those, unless I'm just missing them somewhere."

**A6**: Thank you very much for pointing out this issue and for your careful reading. All units here are in seconds. We will update this information in our main paper.


**Q7**: "The one real-world dataset is weak. I don't believe there is any ground truth being compared against, correct? As it stands, I'm not sure what I'm supposed to get out of Figure 4. It's a very busy graph with a lot of abbreviations, so the takeaway just ends up being "DGES can output a graph". You then call-out in the text that DGES was able to detect 3 MinDCs, but it's hard to verify this, since they're not highlighted in any way in Figure 4. If you want to include Figure 4 here, marking the edges that are deterministic vs probabilistic separately would help a lot."

**A7**: Thanks a lot for sharing your concerns. Let us answer your questions one by one. (1) Yes, the real dataset we use has no ground truth. What we know is based on domain experts' knowledge, such as: BMI = $weight / height^2$, $K_{el} = Clearance / V_d$, and so on. Using this expert knowledge, we evaluate and compare the results of DGES with those of GES to see how it improves. (2) In light of your comments, we will re-draw the causal graph, highlight the MinDC variables, and update all of the graphs for real-world datasets in the revised version.


**Q8**: "Also, the text makes it sound like DGES does great on this dataset by calling out, for example, that it got the MinDC {height, weight, BMI}. However, this comes across a bit disingenuous. We know the ground truth is height -> BMI <- weight. When I located those variables in Figure 4, however, the structure I actually see is BMI -> weight -> height, which is definitely wrong. I'd be interested to know how often other methods are able to correctly orient deterministic functions like this one in the data. Looking at Appendix 6, GES appears to make the same mistake (BMI -> weight -> height). However, the text in the main paper discussing these results comes across as fully positive about the performance of DGES. Some acknowledgement that these MinDCs are not perfectly determined (and making that a lot easier to see in Figure 4 by marking the deterministic edges and maybe highlighting these specific clusters that you reference) would help a lot."

**A8**: We appreciate your thoughtful questions. Regarding the structure of MinDC {height, weight, BMI}, the true graph should be a fully connected graph because besides height -> BMI <- weight, height and weight are also dependent. As mentioned in Appendix A1(Q/A1), we did acknowledge that our method cannot perfected identify the skeleton and directions in the DC part. However, as shown in Figure 4, our DGES method can still find the dependence within the MinDC, for example, there are edges between BMI and weight, weight and height. Meanwhile, BMI and height are also dependent due to their common cause 'I_healthy'.  

We want to emphasize that our DGES method aims to give a general framework to identify the BS and NDC parts, if we want to further identify the orientations of the MinDC part, further strong assumptions on functional causal form will be needed, e.g., paper [29] assumed linear non-Gaussian model.
References:

[53] A. Hauserand and P.Bühlmann. "Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs." Journal of Machine Learning Research, 2012.

[54] J. I. Alonso-Barba, et al. "Scaling Up the Greedy Equivalence Algorithm by Constraining the Search Space of Equivalence Classes." Internat. J. Approx. Reason., 2013.

[55] Alexander Marx, et al. "A Weaker Faithfulness Assumption based on Triple Interactions." UAI, 2021.

[56] Niklas Gericke, et al. "Exploring Relationships among Belief in Genetic Determinism, Denetics Knowledge, and Social Factors." Science & Education, 2017.

[57] Attila Grandpierre, et al. "The Universal Principle of Biology: Determinism, Quantum Physics and Spontaneity." NeuroQuantology, 2014.
**Q8**: "In the real-world dataset, are any of the discovered MinDCs interesting? All three of them seem to be rather simple. Are there example networks where the MinDCs would not be predictable by domain experts?"

**A8**: We appreciate your interesting question. Yes, the discovered DC {$K_{el}$, $V_d$, Clearance, $T_{half}$} is interesting because of the overlapping variable $K_{el}$. By the Phase 1 of our method, we can successfully detect the MinDCs: {$K_{el}$, $V_d$, Clearance}, {$K_{el}$, $T_{half}$}, and {$T_{half}$, $V_d$, Clearance}. 

We learn two biology equations from domain experts: $K_{el}$ = $V_d$ / Clearance, and $T_{half}$ = $ln2$ / $K_{el}$. The two equations are consistent with what we have detected. So far, our detected MinDCs in the real-world dataset are all predictable or explainable by domain experts, because all those variables are well-studied. 

In fact, the MinDC detection phase of our DGES does NOT require any prior knowledge, which means that it is absolutely possible to discover more unknown or unpredictable deterministic relations, when given a set of unknown or new variables. 

**Q9** "On a related note, does the graph obtained by specifically including these deterministic relations qualitatively differ from what we would have found without them? Is BMI a causally relevant variable in the first place, rather than a--possibly rather arbitrary--construct?"

**A9**: Thanks for your insightful question. Regarding the first question, the graphs obtained with or without deterministic relations can be totally different. Let's use an example to see the differences. 

- Consider a four-variable graph: {$X_1 \rightarrow X_2 \leftarrow X_3, X_3 \rightarrow X_4$}, where $\{X_1, X_3\}\mapsto X_2$ and {$X_1,X_2,X_3$} makes up a MinDC.  

- If we simply remove $X_1$, we will obtain {$X_2 - X_3 - X_4$};

- If we simply remove $X_2$, we will obtain {$X_1 - X_3 - X_4$};

- If we simply remove $X_3$, we will obtain {$X_1 \rightarrow X_4 \leftarrow X_2$};

We can see that the three outputs are equally sparse, however, graphs are different from each other. Without additional information or prior knowledge, it is difficult to decide which variable from MinDC to remove and how to reconstruct the graph by putting the removed variable back. 

As for the second question, we believe that BMI is a causally relevant variable. The reasons are: BMI is strongly associated with body fat percentage in the general population; Usually high BMI values are associated with increased risk of various health conditions, such as cardiovascular disease; In Figure 4, our estimated causal graph shows the clear dependence between health condition ("I_health") and BMI value ("I_BMI"), which is reasonable.   


**Q10**: "It's not quite clear how common or relevant these deterministic relationships are, and how different the resulting output networks really are."

**A10**：We appreciate your constructive comments. Actually deterministic relations are quite common in real-world, particularly in biology science [56, 57]. Take Figure 4 in our main paper as an example, we can see that the variables within one MinDC are connected, meaning their strong relevance and dependence. More analysis about the real-world dataset has been given in Appendix A6. We also compare different output networks. At Line 888, we compare the results by DGES with that by GES; Given the detected MinDC {$K_{el}$, $V_d$, Clearance}, DGES can further refine the BS and MinDC parts by GES. At line 890, we also compare generalized score with BIC score in DGES, we can see more reasonable edges are detected by generalized score, such as {age-medication, healthy-disease, healthy-BMI}. Since the relations are more likely to be nonlinear in real datasets, it is more reasonable to use generalized score in a non-parametric way. 

**Q11**: "The theoretical results seem like they could be improved."

**A11**: Thanks for your kind suggestion. Please refer to Q6/A6 for more details about our response.

**Q12**: "The evaluation on only a single real-world dataset seems rather weak (Q8,9)."

**A12**: Thank you so much for your advice. We have conducted the experiments on another real-world dataset. Please check the global "Official Comment" above. 

Thank you very much again. We hope our responses could address your concerns. Please let us know if you have further comments. Your advice means a lot to us!