On Causal Discovery in the Presence of Deterministic Relations
Authors: Loka Li
Haoyue Dai
Hanin Al Ghothani
Biwei Huang
Jiji Zhang
Shahar Harel
Isaac Bentwich
Guangyi Chen
Kun Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: causal discovery
deterministic relations
Primary area: causal_inference
TL;DR: This paper proposes a novel method called DGES to conduct causal discovery with deterministic relations.

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.

On Causal Discovery in the Presence of Deterministic Relations
Loka Li Haoyue D Hanin Al Ghothani', Biwei Huang
Jiji Zhang', Shahar Harel Isaac Bentwich", Guangyi Chen Kun Zhang
Mohamed bin Zayed University of Artificial Intelligence
Cameeiie Mellon University, University of California San Diego
The Chinese University of Hong Kong, 5 Quris Al flongkang. 1i, kun. woan.zhnghhe www.zaaaannnaaaaaaa Ambzuai. ac.ae
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 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 deterministic relations under rather mild assumptions. Nonetheless, exact score- based methods can be computationally expensive. To enhance the efficiency and scalability, develop novel framework for causal discovery that detect and handle deterministic relations, called Determinism-awann Greedy Equivalent Search (DGES). DGES comprises three phases: (I) identify minimal deterministic clusters (i.e., a minimal set of variables with deterministic relationships), (2) run modified Greedy Equivalent Search (GES) to obtain 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 both simulated and real-world datasets to show the efficacy of our proposed method. The code is available at https:: pettp://githube www/Lokali/DGES
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 [. healthcare 2], manufacturing 3 and neuroscience [4]. 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 weight divided by the square of the body height, composing a deterministic relation among weight, height, and BMI.
manstraint-based and score-based methods two primary categories in causal discovery. Constraint- based methods, such as PC [5] and FCI [6. leverage conditional independence tests (CIT) to estimate the graph skeleton and then determine the orientation. Under the Markov and faithfulness assumptions 7. these methods are guaranteed to asymptotically output the true Markov equivalence class (MEC). However, the faithfulness assumption is sensitive to many factors, such the statistical errors with finite samples. Moreover, in the presence of deterministic relations, the faithfulness assumption is
Equal contributions.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

always violated. Take the chain structure X Y + Z for example where Y Y= fX)). In this case, faithfulness is violated due to the conditional independence Z YJ i... when X is given. Y degenerates to a constant that is independent to any variables. Several variants of constraint- methods g have been proposed to accommodate certain types of unfaithfulness. However, they generally provide practical flexibility but do not guarantee the identification to 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) [0], which searches in the space of MECs greedily by maximizing well-defined score, such as Bayesian information criterion (BIC) score [T]] 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 asymp- totic correctness of the search results, such as dynamic programming (DP) 12 [
A*
[4] 5 and
integer programming [6 17] The DAGs estimated by these methods can be converted to their MECs for causal interpretation 18 Lu al. [19] demonstrated that these exact methods may produce
correct results in cases where methods relying on faithfulness fail. Furthermore, Ng et al. [20] proved that exact score-based search with BIC can asymptotically outputs the true MEC when the sparsest Markov representation (SMR) assumption 21 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 7 is proposed for graphically determining conditional independence. Glymour [22] proposed heuristic procedure to learn the causal graph in deterministic system, called DPC, where only a subset of variables will be conditioned in testing conditional independence. Daniusis al.
[23 and Janzing et al. [24] considered a deterministic system with only two variables, and presented the idea of independent changes to infer the causal direction. Luo [25] and (26) incorporated the classical PC algorithm and utilized additional independence tests to handle determinism. Mabrouk et al. 27 combined a constraint-bar 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. (28 assumes nonlinear additive noise model under high-dimensional deterministic data while Yang et al. 22 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 and can be inefficient for large graphs. To enhance the efficiency and scalability, we propose a novel framework called Determinism-awaz 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.
Greedy Equivalent Search (DGES), aimed at enhancing the
Paper organization. In Section 2 we review the common assumptions, provide motivating example why PC fails in dealing with deterministic relations, then present our intuitive solution using exact score-based method. In Section we present our proposed DGES with three phases in details. Furthermore, we provide the identifiability conditions for DGES presented in 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
2

---

2 Causal Discovery with Deterministic Relations
In this section, we first review the preliminaries of causal discovery, especially with deterministic relations, and then we provide some common assumptions that are related to our further analysis, as presented in section 2. Furthermore, we display two scenarios with deterministic relations where faithfulness can be violated in section 2.2 explaining why using constraint- PC algorithm can be problematic in addressing deterministic issues. Lastly, provide intuitive solution to handle the deterministic issues by exact score-based methods, as shown in section 2.3
methods such as the
2.1 Causal Discovery and Common Assumptions
Let G - (V. E) be DAG with the vertex set V and edge set E. Consider d observable variables denoted by V (V1 .g..., Va), and denote IP as its probability distribution. From a statistical view, X XL Y denotes that X and Y are conditionally independent given Z. Moreover, from graph view, X La Y| 2 denotes that X and Y are d-separated by Z. Given n data samples, the task of causal discovery aims at recovering the causal graph from the data matrix V Rx Usually, each variable V; E V with random noises can be represented by the following structural causal model (SCM): 1 =
G,), where PA, is the set of all direct causes of Vi, and c; is the random noise with non-zero variance related to V. and we assume that c,' are mutually independent. For variables with deterministic relations, the SCM becomes: V (PA,). where there is no extra noise. The relation can also be denoted as PA; >VV, where ~ is the deterministic function mapping, showing PA; determines V. Throughout this paper, we assume causal sufficiency, i.e., no latent confounder.
Terminologies. Consider Figure a as an example, where V3 has deterministic relation with V/ and V2, i.c., V/3 Vi + V/2. and V1 a non-deterministic variable. Here we call the set of deterministic variables as a deterministic cluster (DC), e.g., {V1, V22 VaJ. Accordingly, all the non-deterministic variables make up non-deteriinistic cluster (NDC), e.g., {V1). Meanwhile, the edges connecting between DC and NDC compose bridge set (BS), e.g., (V2 VV, V3
Assumption (Markov) Given a DAG G and the distribution IP over the variable set V, each variable is probabilisticaly independent of its non non-descendants given its parents in G.
There are many DAGs that induce the same conditional independence relations with the distribution P. and it is said to be Markov equivalent. The Markov equivalent class (MBC) contains all the DAGs which entail the same conditional independence relations as G does.
Another widely used assumption is faithfulness (7]. It states that any conditional independence that holds in the probability distribution must correspond to a d- separation in the causal graph. When the Markov and faithfulness assumptions hold true, constraint-baase based methods, such as PC, have been proven to output the correct MEC asymptotically. However, in the finite sample regime, the faithfulness assumption is sensi- tive to statistical testing errors when inferring the CI relations, and the violations might occur often. When there are deterministic relations, faithfulness also fails. Glymour [22) proposes the non-deterministic faithfulness regarding only nondetteriiiistic vari- ables. Moreover, relaxations of faithfulness have been proposed, such as adjacency-faithfuuess faithfulness [8] and triangle-faithfulnee [ Another strictly weaker assumption called Sparsest Markov Representation
V
VA
(a)
(b)
Figure 1: Two examples of causal graphs
where faithfulness violated. The gray nodes
are deterministic variables. (a) {Vi, V2] +
Vg. Violation reason is V42 1 V/l(V/, V2J but Va La ValVV, V2). (b) V1 + Vz. Violation reason is V38 1 Vi but V A V2
(SMR) 211, which is also known the unique-frugality assumption
30 31
Assumption (Sparsest Markov Representation (SMR) 21 tion P over the variable set V, the MEC of G is the unique sparsest MEC which satisfies the Markov assumption.
Given a DAG G and the distribu-
The idea behind SMR is to find the sparsest graphical representation that captures the essential conditional independence relationships in the data. The term "sparsest" refers to the minimal number
3

---

of edges in the graphical model. Under the SMR assumption, the exact score- based methods, such as A [T and DP [3]. can produce asymptotically correct results for learning the true MEC.
2.2 Faithfulness Violation by Deterministic Relations
Glymour [22] pointed out two and only two scenarios in the presence of deterministic relations where faithfulness can be violated. We summarize the two conditions and present the following assumption.
Assumption (Non-deterministic Faithfulness (22)) Define a DAG G and the distribution P over the variable set V. V.,YY Y and S in V. X 1 YIS in P and none of the following conditions holds:
i. 8 + X SHY,
ii. 38' s.t. X Ia Y/S' and S + S",
then X La Y in G.
Remarks: It assumes there no other coincidental independence besides the two conditions. In other words, the two conditions are the only two cases leading to faithfulness violation due to deterministic relations. fact, this assumption equivalent the completeness D-separation criteria Spirtes al. 77]. We will use two graph examples, as shown in Figure I explain the above two conditions.
Firstly, given condition (i) and Figure [a] a)), we can assign S = {Vi, V/2 and X V3, where S + X. Given [V1, V2 V/3 will always be conditionally independent from V4, because V3 can be determined by [V1, V23 with no extra noise term, the estimated residue for regressing V/3 on {V1, V2) will be close to O. Therefore, V1 TL V/ [Vi }2 holds true from statistical view. However, V Ld Val(V1, V/} from graph view. Therefore, in this case, faithfulness is violated.
The key rule of constraint-base set empty set so that two variables conditionally independent, then the edge between these two variables in the graph will be removed. Therefore, we can conclude that using constraint-base methods which rely on faithfulness deal with deterministic relations can be problematic.
method (e.g.. PC algorithm) is that we find at least one conditional
Secondly, given condition (ii) and Figure [b), we can assign = V1, S' = V22 Y = Va. where S + S'. From the graph, we can see that V/3 La Va V22 and V3 La Va V1. However, from a statistical view V3 1 V22V,, since 122 = V1, we also have Va3 I V1 1/1 Here, conditional independence does not imply d- d-separation. Therefore, faithfulness is also violated.
V/ and
2.3 Intuitive Solution: Exact Search
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 (Linear Identifiability of Exact Search (20) Exact score- based search with BIC score asymptotically outputs 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] T in the linear case, as long the SMR assumption is satisfied, the exact score-based method with BIC score [ can asymptotically obtain the true MEC. Then, we can extend the theoretical result from linear to nonlinear scenarios. The exact score-base method with generalized score 32 can also asymptotically output the true MEC.
Theorem 2 (General Identifiability of Exact Search) Exact score-based search with generalized score usymptotically outputs a DAG that belongs to the MEC of the true DAG G if and only if the DAG G and distribution IP satisfy the SMR assumption and some mild conditions are satisfied.
The complete proof is given in Appendix A4.1 Based on the theoretical findings in Lemma I and Theorem 2 the exact score-based methods, which do not specifically require faithfulness but SMR, pave a promising way 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 demonstrated in section 3 The identifiability conditions for DGES are provided in section
Remarks:

---

Algorithm DGES: Deterninism-aware Greedy Equivalent Search
Input: data matrix E 1axd
Output: causal graph G
1:
(Phase I: Detect Minimal Deterministic Clusters) Detect the minimal deterministic clusters, by checking whether one variable can be minimally determined by some other variables.
2:
(Phase 2: Run Modified Greedy Search Globally) Run modified greedy equivalent search on the
whole set of variables to obtain initial graph.
3: (Phase 3: Run Exact Search Partially) Perform the exact search exclusively on the deterministic clusters and their neighboring variables, post-processing.
3 Determinism-awand Greedy Equivalent Search (DGES)
In this section, we will introduce our proposed DGES in detail. Throughout this paper, we consider the general case without assuming any functional causal models. general, DGES contains three phases: Firstly, we need to detect all the minimal deterministic clusters. If one variable can be deterministically represented by some other variables, we may conclude that it is a deterministic variable. Secondly, based on the DC information, Thirdly we perform the exact search exclusively on the DC and their neighbors, as post-processing, The general framework is given in Algorithm [ The contents organized as follows. The details of deterministic cluster detection in Phase 1 are discussed in section 3.1 More information about our modified GES in Phase 2 is introduced in section 3.2 Finally, we discuss exact search in section 3.3
run modified GES to get the initial causal graph.
3.1 Minimal Deterministic Clusters Detection
A minimal deterministic cluster (MinDC) refers to minimal set of variables involved in a determin- istic relation. DC can be seen as a union of all MinDCs in the graph. For example, V ++ V/2 and Vi2 + V3, then (V1, V/) and (Vi, V3} are two MinDCs, while (Vi V2, V3} composes a DC.
First of all, we need to obtain the DC, which contains all the deterministic variables. For each variable V1, E {1, ..., d). if this variable can be deterministically represented by all the other variables, i.e., (V\V. + V,, then this variable must be in DC. After traversing all d variables, we obtain the DC.
However, within the DC, there may be multiple deterministic relations, even some overlapping deterministic variables. Therefore, out of the DC, we need to get set of MinDCs. For each variable VI, we try to detect whether there exists a minimal set S such that S + V,, where V,2 E DC, S C DC and V; é S. Here, we need traverse all the possible combination sets of DC, and see whether one deterministic variable can be minimally represented by some other variables. If so, then those variables compose MinDC. In the end, detection, MinDC detection, and how to check S + Vi, are given in Appendix A331
obtain list of MinDCs. More details about DC
3.2 Modified Greedy Equivalent Search
The modified GES is based on the standard GES 10.
We add some extra constraints during the forward and backward steps and adjust the score functions due to the deterministic relations. When using score functions for causal discovery, we aim for the underlying causal graph or its equivalent class to give the optimal score. Specifically, we desire that the score of a DAG model (1) increases as the result of adding any edge that eliminates an independence constraint that does not hold in the generative distribution, and (2) decreases as a result of adding any edge that does not eliminate such constraint. More formally, we have the following definition of score local consistency.
Definition 1 (Score Local Consistency (10) Let G be any DAG, and let G' be the DAG that results from adding the edge V₂ + V, on G. Let D be the dataset from the distribution P. A score function S(g; D) is locally consistent if the following two properties hold as the sample size n. 0o:
1. Vf I VyIPAS, then S('': S(G: D).
2. V, 1 V, PAS then S(''; D) < S(G:
5

---

BS
NDC
V2
BS
NDC
DC
5
DC
V5
V2
3
V1
V1
V3
V7
V6
V6
4
V4
(a)
(b)
Figure 2: An example graph where V = [(V, V2, Va). (a) the true graph where DC =
(Vi, V2, Va, Vaj, NDC = (Va, Va, V7), and BS (V2-> V/5 1/ Vo, V4 Vo (b) one possible
DAG from the estimated CPDAG by GES, where BS' = (V2-VV V, Vi - Ve, 1/2 Vo, V4 Vo
Modification 1: Edge Adding and Deleting, During the forward phase, at each step with a DAG G in the equivalence class, an edge V; + Vj is added when 1) V A. Vji VJIPAY, and 2) PAY does not determine any of Vs, V,, until no edge can be added. However, when PAς determines V; V,, we always have Vi I. V PAA. In this case, always ignore such independence, directly regard it as dependent, and add such an edge to the graph. The motivation behind the modification to ensure that no false independence due deterministic relations is introduced, and in the end, the output graph is guaranteed to be Markovian.
During the backward phase, at each step with a DAG G in the equivalence class, an edge V; + VG is removed when both 1) V; JL VAIPAJ. and 2) PAf does not determine any of V,, Vj. until no edge can be removed. Similar to the modification in the forward phase, when PAY determines V; or V,, still trust the dependency and keep the edge Vú - Vj. Although the resulting equivalence class will be Markovian to the ground truth, redundant edges will exist.
Fortunately, we have Phase 3 exact search as prot-processing, which will be introduced next in Section 3.3 Under the SMR assumption, we can obtain a more sparse graph. the end, the exact search will remove all those redundant edges. A motivating example showing the advantages of our modified forward and backward phases is provided in Appendix A3.2 and Figure A2
Modification 2: Score Function. 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 can be written as sum of local scores, where each local score is function of only one variable and its parents. Following the property, the score of a DAG G can be represented as
S(G; D) = Σ S(V, PAS).
1=1
Under the linear Gaussian model, the BIC score
is preferred, which is given as
SBIC log I + X log n, log [|),
(2)
and log L
where L is the maximized value of the likelihood function of the model based on the observed data D related to V; and PA,, denotes the number of edges between V/2 and PA, G, n is the number of data samples in D. X' is the penalty parameter, Σ is the variance of the noise term.
However, in the deterministic scenarios, the estimated noise variance E will asymptotically get closer to O, which leads to numerical error because of the term log [Σ. To deal with such an issue, we provide the adjusted BIC score, formulated as
S' (V,
log L' X log n. and log L'
(3)
3/ (1 log | El),
where & is a small constant, and & 0.

---

Under the general nonlinear model, the generalized score (GS) [32 which is in non non- con-aaametric
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.
Σ Sas(V, So,(V,,AA)) - Q
( (
and
( (
no
log(21) (TT)
120
log n
(K 2k 22) ()
PA + +1jdr) 2 "KV
2
trace {
K Kv.
A. A minkin ku
A, A, A, kl
À PAY
PAT
PAY
PA
+2m Kv, B:A, K
2(64))
1.0(g)
2 R
A,K Ro(a)
B.K R0(4) }.
PA
X
(4)
PA where A, = ( (K + 11A1)=1, B, = A, + m)AAAA) "AT is the regularization
parameter, n the sample size of each training set, no is the sample size of each test set, n = ni +
D[? and D are the corresponding data of variable V; and its parents, k-1(g) denotes the centralized v; kernel matrix of the g-th training set of V, V. denotes that of the q-th test set of V, and similar notations are used for other kernel matrices.
3.3 Exact Search as Post-processing
As demonstrated by Lu et al. [19,, GES may get sub-optimal results when the faithfulness assumption violated, e.g., when there are deterministic relations. An example is given Figure 2 In this example, the DC is [V1, V2, V3, V1). The true incoming edges to Vo should be (V3. V4). however, the estimated graph by GES may have {V1, V2, Va pointing an exact search based on the GES result to identify BS, under the SMR assumption. Therefore, in Phase 3, we perform the exact search exclusively on the DC and their neighbors. Benefiting from the recent theoretical progress on exact score- score-based methods, which do not explicitly rely on faithfulness assumption, enables us to deal with deterministic relations from an intuitive view.
Vi.- We need to partially conduct
Identifiability Conditions
In this section, provide the identifiability conditions of DGES. The conditions presented in a general form, applicable to both linear and nonlinear causal models. As mentioned above, in general deterministic system, the whole causal graph mainly be divided into three parts: DC, NDC, and BS. In this paper, we focus on the identifiability for the BS and NDC parts.
Theorem (Partial Identifiability) Denote a causal graph & with deterministic relations. Let V be any non-deterministic variable in G, and PA; be the set of direct causes or undirected neighbors of V in one MinDC. Suppose the following conditions hold
Assumptions 1, 2, and 3 hold,
ii. PA: MinnDC|
where | denotes the cardinality of a set. Then, when the sample size n - oo, we can identify the BS and NDC parts of the causal graph & to their true Markov equivalent class.
Experiments
To validate our theoretical findings and show the efficacy of our method, we conducted extensive experiments on simulated and real-world datasets. Specifically, for simulated datasets, we evaluate both linear and general nonlinear functional models.
7

---

1.00
1.00
SEID
Prosision
0.75-
Runtime
(a) Linear Gaussian model, varying number variables
0.7
1.00
1.00
Loo
S10
0.75
Precision
Recall
6.75
Runtime
0.50
0.25
0.4
1000
2000
1000
2002
1000
2000
1000
2003
1000
2000
(b) Linear Gaussian model, varying number of samples
1.0
200-
SHD
Precision
Recall
Ranlime
50-
(c) General nonlinear model with mixed functions, varylng number of variables
46-
Precision
Rantime
SHD
0.4
(d) General nonlinear model with mixed functions, varying number of samples n.
60-
S1D
Precision
Recall
60-
0.6
6:41
10
(e) General nonlinear model with MIP, varying number variables
DPC
GES
A"
DGES
Figure 3: Results on the simulated datasets with one MinDC. We evaluate different functional causal models on varying number variables and samples, respectively. For each setting, we consider SHD (L), Fi score (f), precision (f), recall (1) and runtime (1) as evaluation criteria.
Simulated Datasets. The true DAGs are simulated using the Erdös-Rényi model 33 with the number of edges equal to the number of variables. We evaluate linear Gaussian model and general nonlinear model with mixed functions, each with varying number of variables and samples. Moreover, we also evaluate general nonlinear model generated by MLP on varying number of variables. For each setting, we randomly choose one MinDC or two MinDCs where each MinDC has at least three variables. For the exact method in Phase 3, we choose A [5] without the heuristic tricks. We compare our DGES with other baselines, including DPC 22 GES 10), and A
[5]. We compare
MEC of the output by methods. Note that we only evaluate the BS part which we aim to identify. We consider the structural Hamming distance (SHD), the Fi score, the precision, the recall, and the computational time as evaluation criteria. For each setting, we run 10 different random seeds and report the mean and standard deviation. More implementation details are in Appendix A5.
The simulated results about graphs with only one DC has been shown in Figure B and the results with two DCs (which may have overlapping variables) are given in Figure A4 of Appendix. Clearly, when there are more deterministic variables the system, 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 DPC across different criteria and settings. Meanwhile, score- based method GES presents better performance than constraint-bast method DPC in deterministic

---

Lenkitee
Labedd)
Lownrgte
Figure 4: Results on the real-world dataset with deterministic relations by DGES with Generalized score.
system. As the number of variable increases, 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. More results about two MinDCs, non-deterministic scenarios, and relaxed exact search such GRaSP 31, are provided in Appendix(Ax. (A5]
Real-world Datasets. We also evaluate method and the baselines on two real-world datasets. One the pharmacokinetics dataset (44] which an open database for pharmacokinetics information from clinical trials. It provides curated information mainly in two categories: the characteristics of the studied individuals (c.g., age, height) and the measurement records (c.g., the clearance, Tmaz. Cmoz when one certain individual takes certain drug), and name the two categories of variables as class "I" (individual) and "M" (measurement), respectively. Out more than 200 variables and more than 200000 data samples containing missing values, cleaned the data and finally obtained 32 important variables with 4194 data samples which may contain deterministic relations. The 32 variables contains 18 and 14 variables from the class "I" and "M". respectively. We prepend the class label to each variable name as prefix. We use linear BIC score and nonlinear generalized score conduct the search. Figure 4 gives the DGES result with generalized score, where we can successfully detect at least three MinDCs: (height, weight, BMI), (kat Va, Clearance), (kia. Thalf }. Compared with the linear DGES result with BIC score, we can see more reasonable edges existing in the nonlinear DGES result with the generalized score, for example, (age medication, healthy + discase, healthy BMIJ. More results and analysis are provided in Appendix A6
A6
The other one the US census Public Use Microdata Sample (PUMS). We follow the data preprocess-
ing procedure outlined in (35, which is modern version of the UCI Adult data 36 Datasets
based on census data are widely considered in the algorithmic fairness literature 37.41
Here we
choose 5 important variables, i.e., Age, Occupation, Sex, Annual income (AI), and Adjusted annual income (AAT), in total there are 3000 samples. Because of the potentially different timeframe of the survey cycle, AAI (= AI Adjusted factor) 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. The result of DGES is: {Sex - Occupation + AI, AI + AAL, Sex + AAI + Age), 5 edges. The result of GES is: (Sex + Occupation AAAI, AI AAI Age, AI + Sex AAI), 6 edges. The result of PC is: [Sex > Occupation + Age, AI - AAI), 3 edges. 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 - Sex +- AAI) while our DGES only keeps one edge |Sex - AAI Moreover, the result of PC totally different from the other two. Clearly, in our DGES result, and AAI are still connected, and we can still see the BS, i.e., (Al + Occupation, AAI Sex, AAI-Age). However, as a result of PC with FisherZ. test, the BS becomes empty, which exactly due the violation of faithfulness.

---

6 Discussions and Conclusion
Limitations. While presenting a versatile framework, our paper does have certain limitations. Firstly, in some cases, e.g., with overlapping deterministic variables, our method cannot identify the skeleton and directions in the DC part so far. We display two graphs that we can identify up to MEC and the other two that we cannot identify in Figure A1 More discussion is in Appendix AA Secondly, inherited from the disadvantages of exact methods, our method can be somewhat computationally expensive in Phase 3 when there are a large number of MinDCs. Fortunately, each MinDC is usually not too large, and we may execute the exact search for different MinDCs simultancously.
Broader Impacts. The overarching aim of our proposed method is to learn the causal structures from any general functional causal models in the presence of deterministic relations. This a fundamental and critical task with wide-ranging applications in practical life, and we firmly believe that our method will serve beneficial purposes without engendering negative societal impacts.
This paper dives into the challenges of causal discovery in the presence of deterministic relations. Notably, 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 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 partial identifiability conditions for DGES, Hopefully, our method can help to construct a holistic view to see the deterministic relations. The extensive experiments on simulated and world datasets, validate our theoretical findings and the efficacy of our method.
Conclusion.
Acknowledgement
This material is based upon work supported by NSF Award No. 2229881, AI Institute for Societal Decision Making (AI-SDM), the National Institutes of Health (NIH) under Contract R01HL159805. and grants from Salesforce, Apple Inc., Quris AI, and Florin Court Capital.
References
[1] Ana Rita Nogueira, João Gama, and Carlos Abreu Ferreira. Causal discovery in machine learning: Theories and applications. Journal of Dynamics & Games, 8(3):203, 2021.
[2] Xinpeng Shen, Sisi Ma, Prashanthi Vemuri, and Gyorgy Simon. Challenges and opportunities with causal discovery algorithms: application to alzheimer's pathophysiology. Scientific reports, 10(1):1-12, 2020.
[3] Matej Vuković and Stefan Thalmann. Causal discovery manufacturing: A structured literature review, Journal of Manufacturing and Materials Processing, 6(1):10, 2022.
[4] Ruibo Tu, Kun Zhang, Bo Bertilson, Hedvig Kjellstrom, and Cheng Zhang. Neuropathic pain diagnosis simulator for causal discovery algorithm evaluation. Advances in Neural Information Processing Systems, 32, 2019.
[5] Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social science computer review, 922: 1991.
[6] Peter L Spirtes, Christopher Meek, and Thomas Richardson. Causal inference in the presence of latent variables and selection bias. Conference on Uncertainty in Artificial Intelligence, 1995.
[7] Peter Spirtes, Clark Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000.
[8] Joseph Ramsey, Peter Spirtes, and Jiji Zhang. Adjacency-faitffuness faithfulness and conservative causal inference. In Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelli- gence, pages 401-408, 2006.
[9] Peter Spirtes and Jiji Zhang. A uniformly consistent estimator of causal effects under the suriangle-faithfuhne assumption. Statistical Science, pages 662-678, 2014.
10

---

[10] David Maxwell Chickering. Optimal structure identification with greedy search, Journal of machine learning research, 3(Nov):507-554, 2002.
[11] Gideon Schwarz. Estimating the dimension of model. The annals of statistics, pages 461-4644 4644, 1978.
[12]
Mikko Koivisto and Kismat Sood. Exact bayesian structure discovery in bayesian networks. The Journal of Machine Learning Research, 5:549-577 573, 2004.
[13] Ajit P Singh and Andrew W Moore. Finding optimal Bayesian networks by dynamic program- ming. Carnegie Mellon University. Center for Automated Learning and Discovery. 2005.
[14] Changhe Yuan, Brandon Malone, and Xiaojian Wu. Learning optimal bayesian networks using a* search. In Twenty-second international joint conference on artificial intelligence, 2011.
[15] Changhe Yuan and Brandon Malone. Learning optimal bayesian networks: shortest path perspective. Journal of Artificial Intelligence Research, 48:23 65, 2013.
[16] James Cussens. Bayesian network learning with cutting planes. In Proceedings of the Twenty- Seventh Conference on Uncertainty in Artificial Intelligence, pages 153-160, 2011.
[17] Mark Bartlett and James Cussens. Integer linear programming for the bayesian network structure learning problem. Artificial Intelligence, 244:258-2 221,, 2017.
[18] Peter Spirtes and Kun Zhang, Search for causal models. Handbook of graphical models, pages 457-488, 2018
[19] Ni Y Lu, Kun Zhang, and Changhe Yuan. Improving causal discovery by optimal bayesian network learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8741-8748, 2021.
[20] Ignavier Ng, Yujia Zheng, Jiji Zhang, and Kun Zhang. Reliable causal discovery with improved exact search and weaker assumptions, Advances in Neural Information Processing Systems, 34: 11308-20320, 2021.
[21] Garvesh Raskutti and Caroline Uhler. Learning directed acyelic graph models based on sparsest permutations. Stat, 7(1):e183, 2018.
[22] Clark Glymour. Learning the structure of deterministic systems. Causal learning. Psychology, philosophy, and computation, pages 231-240, 2007.
[23] Daniusis, D Janzing. Mooij. Zscheischler, Steudel, Zhang, and Schölkopf. Inferring deterministic causal relations. In 26th Conference on Uncertainty in Artificial Intelligence (UAl 2010), pages 143-150. AUAI Press, 2010.
[24] Dominik Janzing, Joris Mooij, Kun Zhang, Jan Lemeire, Jakob Zscheischler, Povilas Daniušis. Bastian Steudel, and Bernhard Schölkopf. Information directions. Artificial Intelligence, 182:1-31, 2012.
infommation-gommetti geometric approach to inferring causal
[25] Wei Luo. Learning bayesian networks in semi deterministic systems. Advances in Artificial Intelligence: 19th Conference of the Canadian Society for Computational Studies of Intelligence, Canadian Al 2006, Québec City, Québec, Canada, June 7-9, 2006. Proceedings 19, pages 230-241. Springer, 2006.
[26] Jan Lemeire, Stijn Meganck, Francesco Cartella, and Tingting Liu. Conservative independence- based causal structure learning absence of adjacency faithfulness. International Journal of Approximate Reasoning, 1305):335 2012.
[27] Ahmed Mabrouk, Christophe Gonzales, Karine labet-Chevalien and Eric Chojnacki. An efficient bayesian network structure learning algorithm in the presence of deterministic relations. In ECAI 2014, pages 567-572. IOS Press, 2014.
[28] Yan Zeng, Zhifeng Hao, Ruichu Cai, Feng Xie, Libo Huang, and Shohei Shimizu. Nonlin- ear causal discovery for high-dimensional deterministic data. IEEE Transactions on Neural Networks and Learning Systems, 2021.

---

[29] Yuqin Yang. Mohamed S Nafea, AmirEmad Ghassami. and Negar Kiyavash. Causal discovery in linear structural causal models with deterministic relations. In Conference on Causal Learning and Reasoning, pages 944-993. PMLR, 2022.
[30] Malcolm Forster, Garvesh Raskutti, Reuben Stem, and Naftali Weinberger. The frugal inference of causal relations. The British Journal for the Philosophy of Science, 2018.
[31] Wai-Yin Yin Lam, Bryan Andrews, and Joseph Ramsey, Greedy relaxations of the sparsest permuta- tion algorithm. In Uncertainty in Artificial Intelligence, pages 1052-1062. PMLR, 2022.
[32] Biwei Huang, Kun Zhang, Yizhu Lin, Bernhard Schölkopf, and Clark Glymour. Generalized score functions for causal discovery. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1551-1560, 2018.
[33] Paul Erdós, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
[34] Jan Grzegorzewski, Janosch Brandhorst, Kathleen Green, Dimitra Eleftheriadou, Yannick Duport, Florian Barthorscht, Adrian Köller, Danny Yu Jia Ke, Sara De Angelis, and Matthias König. Pk-db: pharmacokinetics database for individualized and stratified computational modeling. Nucleic acids research, (11D):DD338-DD36 2021.
[35] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34:6478-6490, 2021.
[36] Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 10:C5XW20, 1996.
[37] Razieh Nabi and Ilya Shpitser. Fair inference outcomes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
[38] Zeyu Tang, Jialu Wang, Yang Liu, Peter Spirtes, and Kun Zhang. Procedural fairness through decoupling objectionable data generating components. arXiv preprint arXiv:2311.14688 2023.
[39] Zeyu Tang, Jiji Zhang. and Kun Zhang. What-is and how-to for fairness in machine learning: survey, reflection, and perspective. ACM Computing Surveys, 55(13s):1-37, 2023.
[40] Zeyu Tang, Yatong Chen, Yang Liu, and Kun Zhang. Tier balancing: Towards dynamic faimness over underlying causal factors. arXiv preprint arXiv:2301.08957 2023.
[41] Zeyu Tang and Kun Zhang. Attainability and optimality: The equalized odds fairness revisited. In Conference on Causal Learning and Reasoning, pages 754-786. PMLR, 2022.
[42] Peter Spirtes and Kun Zhang. Causal discovery and inference: concepts and recent methodolog- ical advances. In Applied informatics, volume 3, pages 1-28. SpringerOpen, 2016
[43] Peter Spirtes. An anytime algorithm for causal inference. In International Workshop on Artificial Intelligence and Statistics, pages 278-285. PMLR, 2001.
[44] Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. arXiv preprint arXiv:/202.3775. 2012.
[45] Eric V Strobl, Kun Zhang, and Shyam Visweswaran. Approximate kernel-based conditional independence tests for fast non poraamemttri causal discovery. Journal of Causal Inference, 7(1), 2019.
[46] Loka Li, Ignavier Ng, Gongxu Luo, Biwei Huang, Guangyi Chen, Tongliang Liu, Bin Gu, and Kun Zhang. Federated causal discovery from heterogeneous data. arXiv preprint 1022v 2024.
[47] Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with no tears: Continuous optimization for structure learning. Advances Neural Information Processing Systems, 31, 2018
12

---

[48] Klea Ziu, Slavomír Hanzely, Loka Li, Kun Zhang, Martin Takáč, and Dmitry Kamzolov. vi dag: Projected stochastic approximation iteration for dag structure learning. arXiv preprint WiXiv:2410233866 2024.
[49] Ignavier Ng, AmirEmad Ghassami, and Kun Zhang. On the role of sparsity and dag constraints for learning linear dags. Advances in Neural Information Processing Systems, 33:17943-17955 2020.
[50] Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gnn: Dag structure learning with graph neural networks. In International Conference on Machine Learning, pages 7154-7163. PMLR, 2019.
[51] Yue Yu, Tian Gao, Naiyu Yin, and Qiang Ji. Dags with no curl: An efficient dag structure learning approach. In International Conference on Machine Learning, pages 12156-12166. PMLR, 2021.
[52] Phillip Lippe, Taco Cohen, and Efstratios Gavves. Efficient neural causal discovery without acyelicity constraints. International Conference on Learning Representations, 2022.
[53] Lars Lorch, Scott Sussex, Jonas Rothfuss, Andreas Krause, and Bernhard Schölkopf. Amortized inference for causal structure learning. Advances in Neural Information Processing Systems, 35: 13104-13118, 2022.
[54] Dennis Wei, Tian Gao, and Yue Yu. DAGs with no fears: A closer look at continuous optimiza- tion for learning Bayesian networks. In Advances in Neural Information Processing Systems, 2020.
[55] Alexander Reisach, Christof Seiler, and Sebastian Weichwald, Beware of the simulated DAG! causal discovery benchmarks may be easy game. In Advances in Neural Information Processing Systems, 2021.
[56] Ignavier Ng. Biwei Huang, and Kun Zhang. Structure learning with continuous optimization: A sober look and beyond. arXiv preprint arXiv:2304.02. 021444 2023.
[57] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Anti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
[58] Patrik Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models, Advances in neural information processing systems, 21, 2008.
[59] Kun Zhang and Aapo Hyvarinen. On the identifiability of the post-nonlinear causal model. arXiv preprint arXiv: 205.2599, 2012.
[60] Alexander Marx, Arthur Gretton, and Joris M Mooij. A weaker faithfulness assumption based on triple interactions. In Uncertainty in Artificial Intelligence, pages 451-460. PMLR, 2021.
[61] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331-366 2007.
[62] Yujia Zheng, Biwei Huang, Wei Chen, Joseph Ramsey, Mingming Gong, Ruichu Cai, Shohei Shimizu, Peter Spirtes, and Kun Zhang. Causal-learn: Causal discovery in python. arXiv preprint arXiv:2307.164000 2023.
13

---

Appendix for
"On Causal Discovery in the Presence of Deterministic Relations"
Table of Contents:
AI More Discussions
14
A2 Related Works
15
A3 Method Details
16
A3.1 Phase I: Minimal Deterministic Clusters Detection
16
A3.2 Phase 2: Modified Greedy Equivalent Search
18
A4 Proofs
18
A4.J Proof of Theorem 2
18
Proof of Theorem
20
A5 More Details about the Simulated Experiments
22
A5.1
Implementation Details
22
A5.2 Evaluation on Two MinDCS
23
A5.3 Evaluation on Non-deterministic Scenario
24
A5,4 Evaluation on Relaxed Exact Search
25
A6 More Details about the Real-world Experiments
25
A6. Results of GES with BIC Score
25
A6.2 Results of DGES with BIC Score
25
A6.3 Results of GES with Generalized Score
26
A6.4 Analysis of DGES with Generalized Score
26
A1 More Discussions
Q1: Why current method cannot identify the skeleton and directions the DC part?
A1: To achieve that goal, we usually need strong assumptions on the underlying functional causal model, i.e., Yang et al. (29 assumed linear non-Gaussian model. However, those assumptions are not in alignment with our goal of general method, i.e., with restricted assumption the underlying functional causal model. That is why currently our method cannot identify the skeleton and directions exactly find out which set of variables are in the
in the DC part. However, fortunately, DC/MinDCs using some DC detection strategies, as shown Section 3.T
Figure A1 gives three example graphs where two of them can be identified up to the true MEC while the other one cannot. In graph (a). V12 + V2, after DGES, we can capture the dependence between Vi and V2, therefore, we can identify in this case. Similarly, in the graph (b), (Vi. V/} + V2, since Vi and V/3 are independent, GES can still capture this v-structure. Therefore, we can identify this case. However, things are different in the two examples at right. In graph (c), Vi + V2, V + V/. after running GES, we may get fully-connected graph. Obviously, this fully-connected graph has different skeleton and directions than the true one.
14

---

1
1/2
(a)
V2
1/2
V3
(c)
V
V/3
X
V2
(b)
Figure A1: Some graphs where DGES can (Left) or cannot (Right) identify the MEC: (a) Vi + V2.
(b) [V1, V33 22, (c) Vi 122 V2 V/.
Q2: Why GES can problematic the cases where DC variables cause NDC variables?
A2: Take Figure as an example, where the true edges related to Vg include V/3 + Vo and V4 + Ve. However, during the forward phase of GES, it is very likely that the edge Ví Vo can be added in the beginning. Then the edges 1/2 + V/8 and 142 + V6 are added subsequently. During the backward phase of GES, the edge Ví V6 will not be deleted, because V also contains information from V3, in other words, Ve is represented by V1, V2 and V/ 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.
Q3: How GES performs in the cases where NDC variables cause DC variables?
A3: Let's consider this example. Three variables compose a DC (V1, V2, V3, and V1 = 1/2 + V/),, and denote another variable from NDC V4. In this case, there must not be edge from V42 to Vi, because V4 will be DC rather than NDC, if so. Then, if V4 causes V2, there will definitely be edge between them by GES because V4 is clearly dependent on V2, and theoretically, GES can capture this dependence based on the local consistency.
Q4: What the characterization of Markov equivalence class is in the context with deterministic relations?
A4: Regarding only the variables involved in BS and NDC (that is how Theorem claimed), the characterization of Markov equivalence class (MEC) with deterministic relations is still the same as the context of not having deterministic 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 different. As shown in the condition (i) of Assumption 3 and Figure [] there will be "constant independence" caused by the deterministic relations. Therefore, we need to remove those "constant independence" for the new characterization of MEC.
A2 Related Works
As we mentioned in the main paper, constraint baased and score- based methods are two primary categories causal discovery. Constraint-basse methods utilize the conditional independence test (CIT) to learn a skeleton of the directed acyclic graph (DAG), and then orient edges upon the skeleton. Such methods contain Peter-Clark (PC) algorithm [2] and Fast Causal Inference (FCI) algorithm 43 Some typical
In this part, we will introduce more related works in causal discovery 42
CTT methods include kernel-based independent conditional test 44 and approximate kernel-based conditional independent test [45 46).
15

---

Algorithm A1 Detecting Deterministic Cluster (DC)
Input: variable set V E Rd
Output: DC
1: DC < 0
2: for = 1 to d do
3: if [V) + V; then
4: DC DC (V)
5: end if'
6: end for
Score-based methods normally use score function and rely on a particular search strategy to look for the intended graph. The search strategy usually involve greedy search, exact search, continuous optimization. The first pontinuous-optimizati
based method NOTEARS [47], which casts the Bayesian network structure learning task into continuous constrained optimization problem with the least squares objective, using an algebraic characterization of directed acyclic graph (DAG) [48). Subsequent work GOLEM [49] adopts continuous unconstrained optimization formulation with a likelihood-basee objective. NOTEARS designed under the assumption of the linear relations between variables, therefore, another subsequent works have extended NOTEARS handle nonlinear cases via deep neural networks, such as DAG-GNN [50) and DAG-NoCur! [51]. Moreover, ENCO [52] presents an efficient DAG discovery method for directed acyclic causal graphs utilizing both observational and interventional data. AVCI (53] infers causal structure by performing amortized variational inference over an arbitrary data-generating distribution. These methods might suffer from various optimization issues, including convergence (54), sensitivity to data standardization (55). and nonconvexity (56). Since they are only guaranteed to find 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 the linear -on-Gaussian model (LiNGAM) (57), the additive noise model [58]. and the post-nonlinear causal model [59]. 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 general measure of conditional dependence.
deterministic relations and faithfulness violation. It is interesting to discuss the relationships between deterministic relations and faithfulness violation. These faithfulness relaxation methods such as (60] work on general faithfulness violation and propose some weaker faithfulness assump- tions. They usually focus on certain types of structure, such as canceling path, XOR-type, triangle faithfulness, etc. However, to the best of our knowledge, deterministic relations will break all those relaxed faithfulness assumptions, as the distribution is even not graphoid. Therefore, we need to develop specific algorithms to handle determinism.
A.3 Method Details
A3.1 Phase 1: Minimal Deterministic Clusters Detection
DC Detection. In order to detect the DC, which contains all the deterministic variables, we need to traverse all d variables. If (V V.) + V; holds true, then this variable V,, must be in DC. The general
pseudocode stated in Algorithm AI
MinDCs Detection. We aim to get a set of MinDCs from the DC obtained above. Given the DC, for each variable V,, we try to detect whether there exists a minimal set S such that S + V2, S C DC. As shown in the Algorithm A2] we need to traverse all the possible sets for S with increasing cardinality k. |S| = k ()- means the cardinality of a set). we find that S + V; and meanwhile (S U V.) is not superset of any MinDC in current MinDCs, then we can conclude that S U Vú composes one MinDC. Otherwise, if we find that {S U V.3 a superset of one MinDC M in current MinDCs, we may conclude that {S U Vi} is not minimal DC because U Vil > MM).
16

---

Algorithm A2 Detecting Minimal Deterministic Clusters (MinDCs)
Input: DC
Output: MinDCs
I: MinDCs 0
2: for = to DCI-1de
3: for 1 to DC do
4:
for each S in Combinaliin (DC Vi, k) do
5: if S - V, then
6:
MinDC + SU(
7:
if E MinDCs s.t. M & MinDC then MinDCs + MinDCs U (MinDC)
8:
end if 10: end if
9:
end for
12: end for
13:
end for
How to Evaluate S ++ X? Here regression and evaluate the variance term of residue to decide whether there is a deterministic relation or not. Please note that DGES does not assume any functional causal model. Therefore, we also evaluate it in a general form. Specifically, we provide two versions: one assumes a linear model and is based on linear regression as shown in Lemma and another based on general non-linear model as exhibited in Lemma
Lemma 4 (Representation in Linear Model) Lei X be random variable and S be a set of random variables, where X S. Define X and S are with domain X and S, rexpectively. Consider a linear regression framework: (XX) residue, respectively.
S + where and represent the regression coefficient and
X can be represented by S if and only if
Var(u) 0,
where Var(u) is the variance of the residue u.
Lemma 5 (Representation in General Nonlinear Model) Let X be random variable and S be a set of random variables, where X & S. Define X and S are with domain X and S, respectively. Define RKHS Hx X with continuous feature mapping Φx X Hx. Consider regression framework in the RKHS: (xx = Fe(S)) (SS)++ + u, where Psg. S Hx and represents the regression residue.
X can be represented by if and only if
(6) where E,, is the variance matrix of the residue, E,, R., R., e(Ks + +eI)-l(()), is small positive regularization parameter for kernel ridge regression, and Kg is the centralized kernel matrix of S.
EEaliss =
Discussion: Why consider kernel regression in Lemma
considering the general functional causal form. Particularly, this Lemma be used for both linear and nonlinear functional relationships, Gaussian and non-Gaussian data distributions, which is in aligmment with the general goal of our proposed method. For more details, inspired by [44], 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 Σ, in infinite dimension. In this case, we can exhibit general functional causal form.
Because
Proof of Lemma 5
Assume there is a MEC M, which contains both directed edges and undirected edges. Let X random variable in M and S be the set of all non-descendant neighbors, including direct causes and undirected neighbors of X. Suppose the random variables and are over measurable spaces X' and S, respectively.
17

---

Without assuming particular functional causal form, we usually exploit regression framework in the RKHS, encode general dependence relations between two random variables. Define RKHS Hx on A' with continuous feature mapping 6x X Hx. Here, we consider
x F(S) +.
where F S + H.x and represents the regression residue or noise. When applying the kernel ridge regression, we can obtain the estimated residue
= <(2 + +
(8)
where is small positive regularization parameter for kernel ridge regression, and K2 is the centralized kernel matrix of Z. To evaluate whether such residue exists, one may consider the Hilbert-Schmidt norm of the variance matrix
En liss 1
HS 0,
the above equation holds true, then we may conclude that there no noise term the relationship between X and S, in other words, X can be represented by S (without extra noise term).
Vice versa.
A3..2 Phase 2: Modified Greedy Equivalent Search
Figure AaleeeAeeeeeeenn presents an example comparing our modified GES with traditional GES. From this example, we can that: in the backward phase, if we the "constant independence" information C Jl A A then the result graph will become totally wrong where A and B will be connected. In our modifies GES, indifferently ignore such "constant independence" information. In the end, some other information will be considered as priority. For example, as shown on the right side, B JL A and the edge between A and B will be removed first. the end, can obtain more correct graph than the one on the left side.
However, the result of the modified GES is still not perfect; existing, such as A + D. Therefore, we need the Phase 3 exact search for post- post-processing. Under the SMR assumption, can obtain more sparse graph, where either edge - C edge + D will be deleted.
there are redundant edges
A4 Proofs
In this section, we provide the proofs Theorem and Theorem 3
in the main paper.
A4.1 Proof of Theorem 2
Proof: As suggested by the generalized score 322, with proper score functions and search procedures, asymptotically, the resulting Markov equivalence class has the same independence constraints the data generative distribution.
(i) First of all, we would like to discuss the local consistency of the 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 [6].. Then under mild conditions, the CV- likelihood score is locally consistent.
Lemma 6 Suppose that the sample size of each test set nn satisfies
nu
no
oo,
0 as
oo,
and suppose that the regularization parameter À satisfies
À O(n bct1
18

---

Ground-truth Graph:
(C,D) is deterministic cluster.
Modified GES Forward Phase: (- added edge)
AYDIC
Information:
A A,C
C
AIDIC
C
A A/BICC
B
A
B
B
Example DAG:
D
D
D
B
B
B
B
CPDAG:
D
D
D
D
GES Backward Phase: (- removed edge)
Modified GES Backward Phase: (- removed edge)
Information:
C_LAIDD
Information:
BL
Example DAG:
Example DAG:
B
CPDAG:
X
CPDAG:
Figure A2: An Example: Original GES vs. Modified GES.
where n is the total sample size, is parameter of the effective dimension of the kernel space with b > L, and indicates the complexity of the regression function with S
Lemma 7 Assume that all conditions given in Lemma D hold. With the CV likelihood under the regression framework in RKHS as score function and with the GES search procedure, guaran- tees to find the Markov equivalence class which is consistent to the data generative distribution asymptotically.
Lemma ensures that, with proper score functions and search procedures, asymptotically, the resulting Markov equivalence class has the same independence constraints as the data generative distribution. For the complete proofs, please refer the Appendix A5 of paper 33
(ii) Then, We will provide the proof by contra-positive both directions based on the consistency of the generalized score shown above.
19

---

V
2/2
V
V22
V1
V2
V3
V3
V3
V+
(a)
(b)
(c)
Figure A3: An example graph with determinisic relation where V3
f(V. 122). (a) A non- deterministic variable V connects to (V1 V2, V3}- (b) A non-deterministic variable Va connects to {V2, VaJ. (c) A non-deterministic variable V44 connects to (Va). Here among the three graphs, only the graph (c) can be partially identified.
1) "If" direction:
Suppose that an exact score-based search asymptotically outputs DAG H (having the highest generalized score) that does not belong to the MEC of the true DAG G. Since the generalized score known be consistent, (H, 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 [ < [ and therefore, (9, PP) does not satisfy the SMR assumption.
2) "Only if" direction:
Suppose that (G.P) does not satisfy the SMR assumption. Then there exists DAG H not in the MEC of G such that [H| S (9), and (H, P) satisfies the Markov assumption. Without loss of generality, we choose with the least number of edges. We first consider the case in which [H] < | Since both H and G satisfy the Markov assumption, by the consistency generalized, the generalized score of H. is higher than that of G. which implics that exact score-based search will not output any DAG from the MEC of G. For the case with H|| = [9], since they are both Markov with distribution IP, they have the same generalized score. Therefore, exact search will output DAG that belongs the MEC of either H or G and not guaranteed to output a DAG from the MEC of the true DAG g.
Proof ends.
A4.2 Proof of Theorem 3
Proof:
First, we will explain why we need the three assumptions listed. Secondly, we will explain why we need have constraint PA, MinDCC 1. Thirdly, we will give the complete proof based on the conditions.
(i) Why do we need the listed three assumptions?
As mentioned our main paper, there are three phases of our proposed DGES. During the second phase, we need to run GES. To ensure the accuracy of output (particularly on the NDC part), we need the assumptions Markov and non-deterministic faithfulness (See Assumptions and 3). Then in the third phase, need to perform the exact search exclusively on the EDC, where the Sparsest Markov Representation (SMR) assumption (See Assumption 2) will be needed.
(ii) Why do we assume PA: MinDC - 1?
As for why need to condition on PA, MinDC 1.
start with explaining why PA2 = MinDC and PA, = MinDC 1 will fail the provided identifiability.
Let's take an example with four variables, where three of them are deterministically related, as shown in Figure A3 Here among the three graphs, only the graph (c) can partially identified, and the graph (a) and (b) cannot achieve partial identifiability.
20

---

We further assume linear functional causal model, then we can formulate the deterministic relation- ship as
V + BV2 cV3 0,
(10)
where o, b, e are any linear coefficients. Based on the above formulation, the causal equation of variable V4 in Figure A3 a) be represented
V4 dV + + fV33 te
= dVi + +e2 (aVi + bV2) +
d + 1 + + <V1) + 1V/3 +
(11)
-d= dbV2 cV/) + eV22 + VV3 +
a
where is the random noise injected into V4, Clearly, the above four equations are all valid, in other words, V4 can be possibly represented by different sets of variables, meaning that this case is not guaranteed to be identified.
Regarding the variable V1 in Figure b3).), the causal equation can be represented as
144 eV22 JV3
1
cV22 (aV1 + bV2) te
(12)
1 c (aVi cVs) fVs +c.
Again, the above three equations are valid, in other words, Va can be possibly represented by different sets of variables, meaning that this case is also not guaranteed to be identified.
However, in Figure A3),), things are different. The causal equation of variable Va can be represented as
V4 = IV3 + 1 - (V2) + 6.
(13)
=
When the SMR assumption is satisfied, identify the only one case, which is V33 - V4.
Now, we extend the three-variable case the general linear case where there is MinDC with the cardinality MinDC : And we can easily conclude the true conditions to be: PA, < MinnC| -
Furthermore, extend the linear the nonlinear case, where also conclude that the listed conditions ensure partial identifiability.
(iii) The complete proof:
Part
Benefiting from the local consistency of BIC score (See Lemma of paper (10) and generalized score (See Proposition of paper (32)) the NDC part is guaranteed to find the true Markov equivalence class which is consistent to the data generative distribution asymptotically.
The proof contains two parts: the forward phase and the backward phase of GES. In the forward phase, the resulting equivalence class E contains underlying distribution P; i.e., all independence constraints holding in E, hold in P. It has been proved by making use of local consistency of score functions
[0] Here we focus on showing that the backward phase guaranteed find a perfect
map of IP.
21

---

Let & denote the equivalence class resulting from the backward phase of GES, and let E be the perfect map of P: i.e., all independence constraints 8 are in P. and vice versa. Here we aim to show that as the sample size - co, Eb- = =
1) First, we show that the equivalence class & results from each step in the backward phase contains P. Consider a move from to E (E) by applying Delete(X; X,. H) (see the definition in [TO), where & contains P and E (E) does not contain IP. Let E & and G' < E (E) with the difference in X; + Xj. From the fact that the score functions are locally consistent, the local score change AS < O, so S(G; D) > S(g'; D). The attempted move from & to (E) will be rejected.
2) Second, we show that the backward phase will not terminate with some suboptimal equivalence class E that is, there are no independence constraints which containing in P are not in E. Suppose that the backward phase terminates with some suboptimal equivalence class E, and there is one more edge X; - X; or X; X; & than E According to local consistency, and the calculation of local score change with Delete operator, AS from E to E" positive; that is, the score of Ex is larger than that of &. Hence will move to E It contradicts with the assumption that the backward phase terminates with some suboptimal equivalence class. Therefore, the resulting equivalence class in the backward phase is a perfect map of I..
Part II:
However, the BS part will not be guaranteed to find the true Markov equivalence class so far by GES. Due to the deterministic relations, more dependent edges will be added during the forward phase, e.g., (Vi + Vi in Figure ( and {A + D} in Figure A2 However, during the backward phase, all "constant independencies" (i.e.. Vi L V₁iS with S + V. or S + Vÿ) are ignored indifferently, e.g., V1 V2, V3, V4 in Figure 2 b) and C A in Figure A2 the end, the edges V1 + V6 and C - A will be kept.
Lemma 8 (Sparsity (10) Let G and H. be any two DAGs that contain the generative distribution and for which G has fewer parameters than H. and let S be any consistent (DAG) scoring criterion. If all DAGs in an equivalence class have the same number of parameters, then for every G' = =G and for every H' H. S(G'; S(H': D).
Fortunately, have Phase 3 exact search post-processing. Under the SMR assumption, perform the exact search exclusively on the DC and their neighbors. Benefiting from the Lemma 8 a more sparse graph with smaller BS will be selected out of all possible sets. For example, VV3-V.. V/ will be favoured over {V1 [V.VV, V2 V/-+V V., V in Figure 2 and {A + C} will be favoured over {A > C, -> D} in Figure A2
Given the condition PA, | < MinDC - 1, the sparsest graph is unique. Therefore, we can identify the BS in such a scenario, e.g., Figure However, when the condition is violated, e.g., Figure A2] [2]] we can not uniquely obtain the BS, because both {A + C} and {A + D) can be acceptable BS after executing Phase exact search.
In summary, when the two conditions are satisfied by our DGES, the BS and NDC parts of the causal graph G are guaranteed to find their true Markov equivalent class, which is consistent with the data generative distribution asymptotically.
Proof ends.
A5
More Details about the Simulated Experiments
A5.1 Implementation Details
We provide the implementation details of our method and other baseline methods for synthetic datasets.
The true DAGs are simulated using the Erdös-Rényi model 33 with the number of edges equal to the number of variables. The data is generated according the functional causal model V-= EvE (VV) where VjEPA, is the j-th direct cause of V,, c is the random noise related to variable V. and fa is causal function. For deterministic variables, the noise term is removed,
Datasets.
22

---

then the model becomes Vi= EVSEPA, bigf((y)), We evaluate both linear and nonlinear models. For the linear Gaussian model, we let f:(V,) =V, and e, follow Gaussian distribution whose mean is zero and variance is uniformly sampled from (1,
For the general nonlinear model, we try two different types. One is by mixed functions, where fi is randomly chosen from linear, square, sinc, and tanh functions, and e, is sampled from uniform distribution (0.0 0.5) Gaussian distribution (00, 1). The other is generated by MLP, where we consider two hidden layers and each hidden layer has 100 hidden dimensions. We use Sigmiod as the activation function. All the weights randomly generated from the uniform distribution ((0.552) 2). For each setting, we also run 10 different random seeds and report the mean and standard deviation.
Hyperparameters. During the first phase, when we aim to detect the DC and MinDCs and check whether variable can be deterministically represented by some others, we set that if the term 1 < 1e-3, although theoretically the value should exactly be zero. Meanwhile, the regularization parameter for the kernel ridge regression is set to 1e-10. The second phase of our method is to run modified GES, and the setting is by default. The penalty parameter for controlling the sparsity is set to 1. The exact search in the third phase incorporate is the A We run method and the other baseline methods in Ubuntu 20.04 LTS 64-bit System with Intel(R) Xeon(R) Silver 4214 2.20GHz x64 CPU.
Baselines and Evaluations. We compare our DGES with other baselines, including DPC [22]. GES [1). and A [15). We compare the MEC of the output by all methods. For each method, we consider the structural Hamming distance (SHD), the Fi score, the precision, the recall, and the computational time evaluation criteria. Note that we only evaluate the BS part which we can identify the graph under mild assumptions. We conduct the experiments on varying num- ber of variables, varying number of samples, and some other hyperparameter studies. For linear model, we evaluate variable d E {8, 10, 12, 14, 16) while fixing sample size n = 500, and eval- uate sample n {100, 250, 500, 1000, 2000} while fixing variable d = 8. For nonlinear model, we evaluate variable E {6, 7, 8, 9. 10] while fixing sample size n = 100, and evaluate sample {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.
Furthermore, we provide more implementation details for the baseline methods.
The method is an extension for traditional PC algorithm [71, 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-base test [44) and the significance level is set to a = 0.05 by default. We implement this method based on the Causal-leara package https://gi cwm. why/ httph//aasallleeaarr (62)
DPC [2
This method is a classical bcore-based method with greedy search. Our im- com/juangamella.. /as/ For linear Gaussian model, we use BIC score. And for general nonlinear model, we use general- ized score with cross-validation likelihood 32]. The penalty parameter for controlling the sparsity is set to 1.
GES [10] plementation is based on the code from httpss//gitth:ii
A* [15] A is one of the classical exact score- based methods. Actually, there are some heuristic algorithms proposed 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-loarn package htt.:///...pp.......ooooooooeeoe learn 62
A5.2 Evaluation on Two MinDCs
Figure 3 in the main paper presents the simulated results focused on graphs containing just a single deterministic constraint (DC). In contrast, Figure i4 the Appendix offers insights into scenarios involving two DCs, even allowing for the possibility of overlapping variables. An evident trend
23

---

Precision
Runtims
SHDD
0.6
9.6-
0.0-2
021
(a) Linear Gaussian model with varying number of variables
SHD
Precision
88-
Runtime
0.5
1990
1000
2000
1000
2003
1980
2000
(b) Linear Gaussian model with verying number samples n.
303
SHD
9.8
Precision
Roail
Runtimo
200
0.6
103
34
(c) Nonlinear model with varying number of variables d.
1.0
Precieton
Rocall
Runtime
3300
36
0.4
041
100
200
100
200
100
200
103
200
100
200
(d) Nonlinear model varying number of samples n.
DPC
GES
A
DGES
Figure A4: Results on the simulated datasets with two MinDCs. We evaluate different functional causal models on varying number of variables and samples, respectively. For each setting, we consider SHD (L), F1 score (1), precision (1), recall (1) and runtime (() as evaluation criteria.
emerges: as the system incorporates more deterministic variables, the runtime of our proposed DGES inevitably escalates. This phenomenon can attributed the increased number of deterministic variables demanding detection and inclusion in Phase 3, where exact search is performed.
It 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 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 established baselines. Notably, the exact method A* and proposed DGES consistently outperform other baseline methods like Greedy Equivalence Search (GES) and PC, across spectrum of evaluation criteria and diverse settings. It is intriguing note that in deterministic systems, the score-based method GES consistently outperforms the constraint-hased 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.
A5..3 Evaluation Non-deterministic Scenario
We also conducted experiments in a standard setting, where there no deterministic relation at all. We consider the linear Gaussian model with varying number of variables. We evaluate the SHD, the Fj score, the precision, the recall, and the runtime. We run 10 instances with different random seeds and report the means and standard deviations.

---

1.50
1.00
SHD
Recall
Rantinee
20
0,50
0.25
0.25
M.25
10.0
12.5
15.0
15.0
15.0
1860
125
1500
10.0
12.5
150
1000
12.5
156
Number variables
Number of variables of
Number of variables d
Number of variables d
Number of variables df
GES
DGES
Figure A5: Results of non-deterministic scenarios on linear Gaussian model.
1.00
200
SHD
1.0
2.50
0.25
10.0
12.5
15.0
15.0
12.5
15.0
100
125
15.0
10.0
125
150
10.0
12.5
150
Number variables
Number variables
Number of variables
Number of variables
Number variables
DPC
GES
DGES
GRaSP
Figure A6: Results of GRaSP 31 on linear Gaussian model.
The results have been shown in Figure A5 proposed DGES method present the same performance regarding the SHD, the Fi score, the precision, and the recall. However, the runtime of DGES a bit more than GES, because DGES runs 2 phases. It is understandable that when there is no deterministic relation, DGES will be reduced to GES. In Phase 1, DGES will not find any deterministic clusters, then will terminate and output the result of GES in Phase 2.
According the results, we can see that GES and our
A5.4 Evaluation on Relaxed Exact Search
GRaSP 31 greedy relaxation of the sparsest permutation algorithm. We follow the same setting as mentioned in Section [3] Here we consider the linear Gaussian model with varying number of variables, and within the generated dataset there is one MinDC. We evaluate the SHD, the Fi score, the precision, the recall, and the runtime. In this case, we evaluate based on only the BS part.
The results have been shown in Figure A6 According the results, and our proposed DGES still outperform other baselines. GRaSP performs slightly better than GES regarding the SHD, the Fi score, the precision, and the recall. However, according to our data record, the runtime of GRaSP is bit more than GES.
that: in general, A*
A6 More Details about the Real-world Experiments
Due to the comparative poor performance of DPC and the expensive computation of exact search such as A* here for the large real dataset, we mainly compare our DGES with GES, in both linear (using BIC score) and nonlinear (generalized score) settings.
A6.1 Results of GES with BIC Score
In this case, we run GES with BIC score, assuming the model is following linear Gaussian. The causal graph result is given in Figure A7 And in this graph, can clearly some deterministic variables are reasonably connected, such as BMI - weight - height.
A6.2 Results of DGES with BIC Score
We run proposed DGES with BIC score. The first phase is to identify all the MinDCs. Here, we can detect some MinDCs, such as: (BMI, weight, height.), (liet, Va. Clearance). The final result given in Figure A8
25

---

LoN DorrEseAn
Ualli
Lata
Figure A7: Results of real-world dataset with deterministic relations by GES with BIC Score.
Lebaaay
Lond betnospon
Lyekd
Lewnige Bat
Hodel
Laggi
Lopoöt plaazops
Made
Mand
Figure A8: Results of real-world dataset with deterministic relations by DGES with BIC Score.
A6.3 Results of GES with Generalized Score
BIC score assumes linear Gaussian model; here, using generalized score can present general functional models. The GES result with generalized score is given in Figure A9 this graph, we can still see some deterministic variables are reasonably connected, such as BMI weight - height.
A6.4 Analysis of DGES with Generalized Score
This graph presented in Fn the main paper. In phase I, we can detect the following MinDCs: (BMI, weight, height), (ke,, Thatf) ), (ket, Va. Clearance), which are all correct.
Specifically, the ground touth functions are
BMT weight
(14)
height 2>
26

---

Labi4
Figure A9; Results of real-world dataset with deterministic relations by GES with Generalized Score.
In2
ligt
(15)
Thats
Clearance
kit Va
(16)
Take this MinDC (height, weight, BMI) example for further analysis. As all know, BMI is defined as the body weight divided by the square the body height, which composes deterministic relation among the three variables. By applying the GES method, the three variables connected like a cluster comprising a MinDC. At the same time, many other non-deterministic variables still connect with least one of the three deterministic variables, as usual. Imagine if based method to deal with it, there should be no edge connecting from the three variables to any others. Furthermore, according to our common knowledge, the true arrows should be [wegght++BMI height->BMI, height-weiihht, but now our graph just presents (weight- weight->height/ As discussed in Appendix (QI), because currently our method cannot identify the skeleton and directions in MinDC without further assumptions, and in this case, there are common causes behind BMI and height, which are Healthy and Medication.
constraint-
Compared with the GES result with the generalized score, we can see some edges are corrected in the DGES result. For example, the MinDC (ket, Va. Clearance] ) is clustered together.
Compared with the DGES result with BIC score, we can see more reasonable edges existing in the nonlinear DGES result with the generalized score, for example, (age medication, healthy disease, healthy BMI).
27

---

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:
This paper is about causal discovery with deterministic relations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitation in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

Justification: We provide assumption 1,3,4 for the proof of Theorem 4. The complete proof is given in Appendix [? J.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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 properly referenced.
4. Experimental Result Reproducibility
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 of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
Implementation details are presented in Appendix A5.1
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, 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 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 it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
29

---

The rest Answer: [Yes]
Justification:
Our source code has been put in the supplementary files.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.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 Cooeeeoodeesssseeeeee //nips.com htte://alllllgiiiee////eeeuaaasl ssiniioisciy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The general details of experiment setting are presented in Section 5 of the details are included in the Appendix A5
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
The standard deviation has been reported in Figure 3 and Figure A4
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, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
30

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables 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 the text how they were calculated and reference the corresponding figures 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: [Yes]
Justification:
The computation details are given in Appendix A5.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 as well as 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 it 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
Answer: [Yes]
Justification:
The research follows the ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there 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: [Yes]
Justification:
The discussion about broader impacts is given in Section 6
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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.
31

---

The conference expects that many papers will be foundational research and not tied 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 an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
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: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses 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 usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or 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: [Yes]
Justification: The generated linear or nonlinear models are discussed in Appendix A5.1
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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, paperswi thcode. com 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 it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The data generation details for simulated datasets given in Appendix A5.1
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is 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 details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in 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 in the main paper.
According the NeurIPS Code of Ethies, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS 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.
33


Reviews:
[{"review_id": "lDIleoB0s9", "reviewer": "Reviewer_zDFG", "summary": "Summary\nIn 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.", "questions": "Questions\n1. Is there any particular reason why we adapt GES specifically? Could we adapt other score-based methods in the same way?\n2. Can you explain how the results you obtain differ from those obtained by other methods to deal with faithfulness violations, e.g. [1]?\n3. 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?\n4. 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?\n5. 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?\n6. 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?\n7. In Figure 3(d), and particularly (b), why is the runtime of DGES almost as high as $A^\\star$?\n8. 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?\n9. 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?\n\nReferences\n[1] A Weaker Faithfulness Assumption based on Triple Interactions", "limitations": "It's currently not clear how relevant the ability to deal with these deterministic relationships truly is", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Strengths\n- The paper is well-written and the ideas are clearly presented\n- The proposed method seems like it should be possible to adapt to other causal discovery algorithms\n- Assumptions made in causal discovery are generally very strong, and finding approaches to alleviate these is an important topic", "weaknesses": "Weaknesses\n- It's not quite clear how common or relevant these deterministic relationships are, and how different the resulting output networks really are\n- The theoretical results seem like they could be improved (Q6)\n- The evaluation on only a single real-world dataset seems rather weak (Q8,9)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s time and constructive suggestions. With the help of such valuable feedback, we believe that our manuscript could be improved a lot. Please find the point-by-point responses below. Q1-Q9 correspond to the points in \"Questions\", while Q10-Q12 correspond to the points in “Weaknesses”.\n\n**Q1**: “Is there any particular reason why we adapt GES specifically? Could we adapt other score-based methods in the same way?”\n\n**A1**: Thanks a lot for your interesting questions. (1) Yes. This paper mainly focuses on score-based causal discovery methods, and GES is one of the most typical and well-known methods in this category with theoretical guarantee, that is why we adapt GES specifically. (2) It depends on which type of score-based methods to consider. For example, for those greedy score-based methods such as GIES [53] and GES-mod [54], we can adapt them in the same way. However, for those continuous-optimization score-based methods such as NOTEARS [39], we cannot directly adapt them. \n \n**Q2**: \"Can you explain how the results you obtain differ from those obtained by other methods to deal with faithfulness violations, e.g. [55]?\"\n\n**A2**: We appreciate you pointing out the relationships between deterministic relations and faithfulness violation. To tell the difference of the two outputs, we can provide a simple example with deterministic relations where our DGES method can work while the 2-Adjacency faithfulness assumption is still violated, and thus paper [55] doesn't work. The example is: $X_2 \\leftarrow X_1 \\rightarrow X_3$ where $X_1 \\mapsto X_2$. DGES can find the edges {$X_2-X_1, X_1-X_3$}. However, for the adjacent pair $X_1$, $X_3$, the MB of $X_1$ cannot form any two variables to render 2-Adjacency faithfulness, as $X_1 \\perp X_3 | X_2$. \n\nTo sum up, those faithfulness relaxation methods such as [55] work on general faithfulness violation and propose some weaker faithfulness assumptions. They usually focus on certain types of structure, such as canceling path, XOR-type, triangle faithfulness, etc. However, to the best of our knowledge, deterministic relations will break all those relaxed faithfulness assumptions, as the distribution is even not a graphoid. Therefore, we need to develop specific algorithms to handle determinism.\n\nIn light of your comments, we will add more discussions in the relate work section, to tell the relationshipa between ours and faithfulness relaxation methods including paper [55].\n\n\n**Q3**: \"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?\"\n\n**A3**: Thanks for your insightful questions. In the low sample and high-dimensional case, basically all variables belong to the DC, and the NDC and BS will be empty set. In such a case, our DGES will be invalid, because DGES mainly aims to identify the BS and NDC parts. \n\n**Q4**: \"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?\"\n\n**A4**: Thanks a lot for your thoughtful question. One possible way to make it efficient is to conduct the pruning process to decrease the search space. For example, once we obtain one MinDC, we can directly eliminate all the superset of this MinDC.    \n\n**Q5**: \"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?\"\n\n**A5**: Thank you very much for your careful reading. When dealing with deterministic relations using BIC score in Eq.(3), the estimated variance of the noise term $|\\Sigma|$ will get close to 0, then $\\log|\\Sigma|$ will encounter with arithmetic error because of $\\log0$, here we add a small constant to avoid such an issue. However, in Eq.(4), due to the ridge kernel regression with postive regularization parameter $\\lambda$, the estimated covariance matrix is already positive-definite, therefore, we do not need extra small positive constant.\n\n**Q6**: \"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?\"\n\n**A6**: Thank you for your constructive comments. You are totally correct that Theorem 3 can be further improved. Actually we had more discussion on Theorem 3 in Appendix A1, particularly discussing when we can identity the DC part. In Figure A1, we presented the two cases where the whole causal graph can be identified up to their Markov equivalent class (MEC). The first case in Figure 1A(a) is $V_1\\rightarrow V_2$ where $V_1$ and $V_2$ have a deterministic relation, which is exactly a simplified version of what you described ($X_{2i-1} \\rightarrow X_{2i}$ for all $i$). In this case, our DGES can indeed achieve full identifiability up to true MEC over all DC, NDC and BS parts.\n\n**Q7**: \"In Figure 3(d), and particularly (b), why is the runtime of DGES almost as high as A*?\"\n\n**A7**: Thanks for your careful reading and raising this concern. In Figure 3(b) and 3(d), we fixed the number of variable in a rather small value ($d=8$ in linear model and $d=6$ in nonlinear model) and evaluated how increasing sample size effected the performance. In a small variable number, A* can perform accurately and efficiently. Meanwhile, we want to emphasize that the time costs of our DGES method include three parts: detect MinDC, run modified GES, and run exact search as postprocessing. Therefore, when summing time costs of all three phases together, particularly in a rather small variable case, the runtime of DGES is comparable with A*.", "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": "DjuGrpbr84", "reviewer": "Reviewer_Nu91", "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.", "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?\n\nDid 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": "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.\n\n\n\nNote: The authors adequately addressed my concerns, so I am increasing my score from 7 to 8.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I really like this paper.  Determinism is present in many real-world datasets, but simply removing variables that participate in deterministic relationships may not be practical or may result in other issues.  DGES is well-described and, while a relatively simple modification to an existing algorithm, the authors provide a strong theoretical basis and detailed algorithmic description, helping it stand as a solid contribution.  The synthetic experimental results are interesting and well-done, comparing across multiple parameter settings and against relevant comparison algorithms.  Overall, i think this is a valuable paper.", "weaknesses": "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.\n\nI 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.\n\nIn 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.\n\nIn 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??\n\nIn 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.\n\nThe 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.\n\nThese 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:\n- line 52 - sparest -> sparsest\n- line 55 - [The] \"d-separation condition is proposed\"... (need an article)\n- line 63 - missing period after \"works\"\n- line 71 - \"...graphs, therefore, we propose...\" is a run-on sentence\n- line 302 - \"As the number of variable increasing\" -> \"As the number of variables increases\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the reviewer for your time dedicated to reviewing our paper, encouraging words and constructive suggestions. In light of your valuable feedbacks, we have carefully modified the structure and narrative of our manuscript. Please find the responses to all your comments point-by-point below.\n\n-----------------------\n\n**Q1**: \"This paper could use some work on the motivation ... 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.\" \n\n**A1**: Thank you for your constructive suggestions. In light of your comments, we would like to add a few more sentences at the end of Line 54, to clarify our motivation. Below is the content: \n\n\"Under SMR assumption [21], we can use exact score-based methods such as DP [12] and A* [14] to handle deterministic relations. Even though faithfulness is violated, we can still get reliable result as long as SMR is satisfied. However, due to the large search space of possible DAGs, exact score-based methods should be inefficient. GES is an efficient score-based method in a greedy manner. As demonstrated by Lu et al. [19], GES may get sub-optimal results when the faithfulness assumption is violated, e.g., when there are deterministic relations. To tell the difference between sub-optimal and optimal results, we provide an example in Figure 2 where the optimal graph (ground truth graph) is on the left and the sub-optimal result is on the right (graph by GES). Based on the sub-optimal result by GES, we can identify those problematic edges and further correct them. To that end, in this paper, we propose an efficient three-phase method for dealing with determinism.\"  \n\n\n**Q2**: \"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. (... simply saying it 'may' be 'sub-optimal' is vague and gives no sense of the severity of the issue).\"\n\n**A2**: Thanks a lot for raising this point. Actually, as shown in Figure 2, we have provided an example to explain the difference between the optimal result (ground truth graph) and the sub-optimal result (graph by GES). In this example, GES may get some edges {$V_1, V_2, V_4$} $\\rightarrow V_6$. However, the ground truth exhibits a more sparse graph by {$V_3, V_4$} $\\rightarrow V_6$. In light of your comments, we will incorporate the statement above into Section 3.3 to make our motivation clearer.\n\n\n**Q3**: \"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.\"\n\n**A3**:  Thank you very much for sharing your concerns. Actually as mentioned in Line 236, we have discussed our motivations with a detailed example in Appendix A3.2 and Figure A2. We totally agree with you that motivations should be discussed before we get into details. Therefore, we will add more contents at the beginning of Section 3.2 to clarify our motivations. The added contents are: \n\n\"We modify the standard GES [10] in the forward and backward phases, and adjust the score function due to the deterministic relations. The key modification in the forward and backward phases is that we always regard the relations to be dependent whenever there is deterministic relation. That is to say, we always assume $V_i \\not\\perp V_j | PA_{j}$, when $PA_{j}$ determines $V_i$ or $V_j$. The motivations are in the following. During the forward phase, we want to preserve as much dependent edges as possible, so that the BS will not be empty due to determinism, as shown in Figure 1(a). During the backward phase, ignoring the dependence in deterministic relations can lead to wrong edges in the NDC part; A motivating example is given in Appendix Figure A2. After the forward and backward phases, we can guarantee that output equivalent class will be Markovian to the ground truth, although some redundant edges may exist. Fortunately, we have Phase 3 exact search as post-processing, which will be introduced in Section 3.3.\"\n\n**Q4**: \"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.\"\n\n**A4**: \"Thank you so much for your constructive advice. Here, mild assumptions are used to ensure that the generalized score is locally consistent. Specifically, these assumptions include constraints on the infinite sample size and the value of the regularization parameter $\\lambda$. More details are provided in Appendix Lemma 6, which is adapted from Lemma 2 of paper [32]. In light of your comments, we will add the explanations above to our main paper.\"", "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": "79dpSRz0Ja", "reviewer": "Reviewer_j5ZZ", "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.", "questions": "See the weaknesses section", "limitations": "Limitations are discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is written well and easy to understand.\n2. Proposed method is motivated well with theoretical analysis.\n3. Experiments are thorough and cover all theoretical insights.", "weaknesses": "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?\n2. Results does not show superior performance over baselines. This is the major concern.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer’s time and constructive comments. With the help of such valuable feedback, we believe that our manuscript could be improved significantly. Please find the point-by-point responses below.\n\n**Q1**: \"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?\" \n\n**A1**: Thank you very much for your insightful question. We totally agree with you that the observed data may contains some noises such as measurement error. In our implementation, we particularly set a threshold to control such noise. When evaluating whether two variables have deterministic relation, we use regression and see if the covariance of noise term is 0, the 0 noise means there exists deterministic relation, as described in Lemma 4 and Lemma 5 in Appendix. Due to the measurement error and so on, the noise covariance will be non-zero even when there is deterministic relation, therefore, we use a small constant as a threshold for evaluation. As mentioned at Line 782 in Appendix, we set such threshold to be $1e{-}3$. In other words, if the noise covariance after regression is smaller than $1e{-}3$, we believe there is a deterministic relation.       \n\n\n**Q2**: \"Results does not show superior performance over baselines. This is the major concern.\"\n\n**A2**: Thanks a lot for sharing your concern. In our experiments, we mainly compare our DGES with three baselines: DPC, GES, and A*. We want to emphasize that the the motivation of DGES is to enhance the efficiency and scalability of using exact search (such as A*) to handle deterministic relations. Therefore, our goal is to approximate the accuracy of DGES to that of A*, while improving the time efficiency. \n\n - As for the comparison with A*, our DGES achieves comparable performance with A* regarding SHD, $F_1$ score, precision and recall, while the runtime of DGES is significantly shorter than that of A*. \n\n- From the results across different sample size, variable size, and different functional causal forms, we can see that our DGES significantly outperforms DPC and GES. \n\n\n---\n\nThank 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!", "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": "O361rHf540", "reviewer": "Reviewer_Wfp4", "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. \nFirstly, 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.\nDGES 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.\nAdditionally, 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.", "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?\n\n* 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)?\n\n* 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?\n\n* 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": "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper demonstrates that exact score-based methods can effectively handle deterministic relationships under mild assumptions.\n\n* A novel framework called DGES is introduced, which enhances the efficiency and scalability of handling deterministic relations.\n\n* The paper provides conditions under which DGES can achieve partial identifiability for general functional models.\n\n* The theoretical findings and efficacy of DGES are validated through extensive experiments on both simulated and real-world datasets.", "weaknesses": "* 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.\n\n* 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.\n\n* The paper assumes causal sufficiency which is almost never satisfied in practice.\n\n* Limited experimental results (see questions below)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s time and constructive suggestions. With the help of such valuable feedback, we believe that our manuscript could be improved significantly. Please find the point-by-point responses below.\n\n\n**Q1**: \"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.\"\n\n**A1**: Thanks a lot for sharing your concerns. We have discussed the reasons why our method cannot identify the DC part in Appendix A1(Q/A1): to achieve this goal, we usually need strong assumptions on the underlying functional causal model, i.e., linear non-Gaussian model [29]. However, those assumptions are aligned with our goal of a general method.\n\nFortunately, in some cases, our DGES can still fully identify the DC part up to their CPDAG, such as v-structure, as shown in Figure A1(a/b). \n\n**Q2**: \"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.\"\n\n**A2**: Thank you so much for pointing it out. As you mentioned, we proposed DGES. Besides that, we want to emphasize two more major contributions. First, we find that exact score-based methods can naturally be used to address the issues of deterministic relations; Importantly, we support our claim with theoretical analysis as presented in Theorem 2.\n\nSecondly, we also provide partial identifiability conditions for our proposed DGES, strengthening our method with theoretical guarantee in Theorem 3. In the appendix A1, we also discussed some cases where we can further identify the DC up to the MEC.\n\n**Q3**: \"The paper assumes causal sufficiency which is almost never satisfied in practice. 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)?\"\n\n**A3**: We appreciate your insightful question. In fact, causal sufficiency assumption is commonly used in causal discovery, even in some of the most classical methods such as PC [20] and GES [26]. In any case, we agree with you that latent variable or confounder is a significant issues to consider. \n\nTo relax causal sufficiency, we can incorporate our DGES framework to those methods which can handle latent variables. Since FCI is constraint-based method relying on conditional independent test while our DGES framework is score-based, it can be challenging to directly combine them.  \n\nHowever, thanks to the recent progress in score-based causal discovery with latent variables, such as SALAD [58], it is absolutely possible to combine our DGES with it, so that we can achieve our goal, i.e., causal discovery in the presence of both deterministic relations and latent variables. As far as we known, SALAD is a exact score-based method assuming linear functional model. In this case, we may incorporate our modification on BIC score as shown in Eq.(3) to SALAD to achieve our goal. \n\n\n**Q4**: \"Limited experimental results (see questions below)\"\n\n**A4**: We appreciate your constructive comments. We have added one more experiments on a new real dataset. Please check the extra PDF file for more details.\n\n**Q5**: \"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?\"\n\n**A5**: Thanks a lot for your insightful question. When there are overlapping deterministic relations, our DGES indeed cannot identify the skeleton and directions in DC. In this case, the identifiability of DC part comes to the worst situation. However, there are still some cases, such as v-structure, where our DGES can still fully identify the DC part up to their CPDAG. More discussions can be found in Appendix A1(Q/A1) and Figure A1.\n\n**Q7**: \"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?\"\n\n**A7**: Thank you so much for your interesting question. According to our experimental results, we found that in linear Gaussian model, our DGES performs quite well, where the $F_1$ score can achieve nearly 95% across different number of variables ranging from 8 to 16 variables. Contrastingly, in the general nonlinear model DGES only achieve nearly 88% $F_1$ score.\n\n**Q8**: \"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?\"\n\n**A8**: Thanks a lot for your constructive question. \n\nMore details: 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. Without additional information, the SMR assumption is a necessary condition for any algorithm that uses the CI relations to infer the graph G [21].\n\nPractical implications: 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. With no doubt, SMR assumption is much weaker than faithfulness assumption. \n\nSatisfaction in read dataset: Yes, SMR is satisfiable in real-world. We can provide two examples here: in financial markets, stock price changes are often primarily influenced by recent prices and trading volumes, while older data have less impact; and in biological Systems: Gene expression and neural activities are typically driven by a few key genes or neurons, with most other variables having limited influence.", "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:

Meta-review: 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).
Decision: Accept (poster)