On Causal Discovery in the Presence of Deterministic Relations

We appreciate the reviewer for the time dedicated to reviewing our paper and constructive suggestions. In light of your valuable feedback, we have updated our manuscript. To make a more arbitrary functional model for synthetic datasets, we have added a new experiment using a neural network. Please find our responses to your concerns below.

Q1: "While the overall idea makes sense, my main concern is the lack of theoretical novelty. While the authors have some theoretical results, they are rather straightforward, and referring to them as "Theorems" may be an overstatement. For instance, it is clear that the residual is expected to be 0 if the functional relationship is perfectly represented."

A1: Thanks for raising those concerns. To address your concerns, we would like to respond from the following two aspects: the theoretical novelty and contributions of our paper, and the importance of those theorems.

The main theoretical novelty and contributions of our paper:

• Firstly, in the paper, we intend to provide simple and reliable perspective to solve the issues of deterministic relations for causal discovery. We found that: under some mild assumptions, the exact search methods can output the MEC where the BS and the NDC part can be correctly identified.

• Secondly, we proposed a novel method called DGES, in order to improve the efficiency of causal discovery in the presence of deterministic relations. Importantly, DGES is a general and versatile three-phase method, without restricted assumptions on the underlying functional causal models, in other words, it can accommodate both linear and nonlinear relationships, Gaussian and non-Gaussian data distributions, as well as continuous and discrete data types.

The importance of the theorems:

• Theorem 3 shows that the exact search methods can be used to solve the issues of deterministic relations when SMR and some mild assumptions hold (faithfulness is not necessary anymore). Note that here we present with generalized score in a general way, where we can handle general functional causal models.

• Theorem 4 presents the techniques of how we detect the DCs (by Representation) and MinDCs (by Perfect Representation). Detecting MinDC is so fundamental that we can handle more challenging cases where there are multiple deterministic relations, even overlapping with each other. We agree that when the functional causal model is linear the theorem is straightforward, however, when we are considering the general functional causal model the scenario is more challenging, and we solve the issues by using kernel regression and evaluating the Hilbert-Schmidt norm of the infinite variance operator $\Sigma_u$.

• Theorem 5 exhibits the identifiability conditions of our proposed DGES method. Once the conditions are satisfied, the BS and NDC parts can be identifiable up to the Markov equivalent class.

Q2: "The reference to Figure 1 in the introduction does not help in understanding the faithfulness violation with deterministic relationships. It would be clearer, for instance, to give the example of a chain X -> Y -> Z, where Y = f(X), which violates faithfulness due to the conditional independence X || Y | f(X)."

A2: Thank you so much for this constructive suggestion. More details have been included in Section 1 of our manuscript, i.e., "Take the chain structure $X \rightarrow Y \rightarrow Z$ for example where $Y=f(X)$. In this case, faithfulness is violated due to the conditional independence $Y \perp Z | X$ or $f(X) \perp Z | X$."

Q3: "The difference between Assumptions 2 and 3 could be clarified. Does Assumption 2 include the cases described in Assumption 3?"

A3: Thanks a lot for this question. We would like to clarify that: Faithfulness (Assumption) is usually used for the whole set of variables, no matter whether there is a deterministic relation or not. On the contrary, non-deterministic faithfulness (Assumption 3) is only assumed for those non-deterministic parts of the whole graph. We have included those details in Section 2 of our updated manuscript to avoid confusion.

Q4: "You mention PC requires 'faithfulness' but based on your definitions, it seems to require 'non-deterministic faithfulness'."

A4: Thanks for this question. We would like to clarify that: the PC algorithm requires "faithfulness" for the whole set of variables, which is why the faithfulness will be violated in the example of Figure 1. However, another modified PC algorithm (called DPC) assumes "non-deterministic faithfulness", as mentioned in Section 1 and Section 2.

We appreciate the reviewer for the time dedicated to reviewing our paper, constructive suggestions, and encouraging feedback. We have carefully modified the manuscript in light of your detailed suggestions. Additionally, we have conducted a new set of experiments. Please find the responses to all your comments below.

Q1: "In the proof of Theorem 3, there is a reference missing with question mark."

A1: Thanks for your careful reading and raising this issue. We have filled in the reference in Appendix A3.2.

Q2: "As acknowledged by the authors the edge directions for deterministic clusters cannot be determined without further assumptions on the functional relationships."

A2: Thank you so much for your comment. We would like to respond to the following points.

• In order to identify the skeleton and directions in the deterministic clusters (DCs), we usually need strong assumptions on the underlying functional causal model, i.e., Yang et al. [1] assumed linear Non-Gaussian model and utilized causal asymmetry to identify the graph structure with deterministic relations. However, those extra assumptions are not in alignment with our initial goal of this paper, to provide a general and versatile method to deal with deterministic relations for causal discovery. Currently, our method makes no assumption on the underlying functional causal models, in other words, it can accommodate both linear and nonlinear relationships, Gaussian and non-Gaussian data distributions, as well as continuous and discrete data types.

• Although our method cannot identify the skeleton and directions in the DCs, we proposed strategies to exactly find out which set of variables have deterministic relations, as shown in Section 3.3.

• Nevertheless, in light of your comments, we are glad to continue studying the identification in DCs with mild assumptions as future work.

We have included those details discussed above in Section 6 and Appendix 1 of our updated manuscript.

Q3: "Using exact search methods can be computationally expensive."

A3: Thanks a lot for the comment. We agree that the exact search methods are computationally expensive, which motivates us to propose our DGES method where we only need to run the exact search on a small set of variables in Phase 3, instead of all variables.

Q4: "Will algorithms that rely on SMR assumption outperform GES-based methods when deterministic relations are present? I am curious about how well GRaSP[1] will perform in the experiment given the result from Theorem 5. Can the authors include that in the experiment?"

A4: Thanks for the great suggestion. In general, the exact search-based methods (with SMR assumption) will outperform GES-based methods (with faithfulness assumption). For example, Figure 2 shows the case where GES might be problematic when there is a deterministic relation, however, the exact search methods can solve this issue.

In light of your suggestion, we have included the experiment in Appendix A4.5 to evaluate how GRaSP [2] performs in the presence of deterministic relations. According to the result, we can see that: In general, GRaSP performs slightly better than GES regarding the SHD, the $F_1$ score, the precision, and the recall. However, the runtime of GRaSP is a bit more than GES. Moreover, A* and our proposed DGES still outperform other baselines, including GRaSP. The reason could be that GRaSP is a relaxation-based method which may lose some solution accuracy compared to the exact method.

We appreciate the reviewer for the time dedicated to reviewing our paper and constructive suggestions. With the help of this valuable feedback, we believe that our manuscript could be improved a lot. We have added the new experiment for evaluating how PC performs in the real-world dataset, and updated our manuscript according to your detailed suggestions. Please find the point-by-point responses below.

Q1: "First, the authors claim that constraint-based methods suffer from deterministic relations and briefly state the reason on page 3. It would be more convincing if solid theorems or experiments were provided to show the failure of constraint-based methods. In addition, how serious is the assumption violation here? Do all constraint-based methods fail or some adjustments would fix this problem?"

A1: We appreciate your constructive comments. We would like to address your concerns one by one as follows.

• To show the failure of the constraint-based method, we have provided Lemma 1. Due to the space limit, we just gave the basic idea of the proof in the main paper and put the detailed theoretical proof in Appendix A3.1.

• The faithfulness assumption violation is quite serious. The key rule of constraint-based method (e.g., PC algorithm) is that: as long as we can find at least one conditional set or an empty set, so that two variables are independent or conditionally independent, then the edge between these two variables in the graph will be removed. Take Figure 1 as the example, where $V_3$ is deterministically determined by $V_1$ and $V_2$ while $V_4$ is dependent on $V_3$. According to Lemma 1, $V_4\perp V_3|\{V_1,V_2\}$ always holds true. Therefore, $V_4$ and $V_3$ will never have an edge in the graph using the constraint-based method, although there is an edge between them in the true graph.

• If following the original key rule, most constraint-based methods will fail. However, there are some papers attempting to fix this problem by incorporating some adjustments. For example, Glymour [1] proposed a heuristic procedure to learn the causal graph in a deterministic system, called DPC. When testing $V_1 \perp V_2|S$ in the presence of deterministic relations, DPC will remove those variables from the conditional set $S$ if they are strongly correlated to $V_1$ or $V_2$, to avoid violating faithfulness.

• In our original manuscript, we briefly introduced the idea of DPC in Section 1, and we also provided the experiments with DPC in Section 5 and Figure 3. However, the performance of DPC is not so promising.

We have included those details discussed above in Section 2.2 of our updated manuscript.

Q2: “Second, as the authors mentioned themselves, the DGES framework can not identify the skeleton and directions in the DCs, which negatively influence the utilization of DGES compared with other mature developed methods.“

A2: Thanks a lot for the insightful comments. We would like to address your concerns on the following points.

• In order to identify the skeleton and directions in the DCs, we usually need strong assumptions on the underlying functional causal model, i.e., Yang et al. [1] assumed linear Non-Gaussian model and utilized causal asymmetry to identify the graph structure with deterministic relations. However, those extra assumptions are not in alignment with our initial goal of this paper, to provide a general and versatile method to deal with deterministic relations for causal discovery. Currently, our method makes no assumption on the underlying functional causal models, in other words, it can accommodate both linear and nonlinear relationships, Gaussian and non-Gaussian data distributions, as well as continuous and discrete data types.

• Although our method cannot identify the skeleton and directions in the DCs, we proposed the DC detection strategies to exactly find out which set of variables have deterministic relations, as shown in Section 3.3.

• Nevertheless, in light of your comments, we are glad to continue studying the identification in DCs with mild assumptions as future work.

We have included those details discussed above in Section 6 and Appendix 1 of our updated manuscript.

Q3: "Thirdly, I doubt could DGES identify all possible DCs or just part of the deterministic relations. If the answer is no, how could we deal with the missing ones?"

A3: Thanks for raising this great point. With Theorem 4 (Representation and Perfect Representation), DGES can identify all possible DCs. Particularly, with the "Perfect Representation" theorem, we can identify all the minimal DCs (MinDCs). When combining all the variables in all the MinDCs, we can obtain the whole set of variables that are in the presence of deterministic relations.

We greatly appreciate the reviewer’s time, encouraging comments, and constructive suggestions. We have carefully modified the manuscript according to your detailed suggestions. Please find the responses to all your comments below. Q1-Q4 correspond to the points in “Weaknesses”, while Q5 corresponds to the point in “Questions”.

Q1: “Unless I'm missing something, the author's results are implied by the following: (1) Due to its scoring function (which penalizes unnecessary edges), GES chooses the MEC for the DC with the fewest edges; (2) When the SMR assumption is satisfied, the correct MEC is guaranteed to be the one with fewest edges; and (3) GES is known to find the MEC for the NDC.”

A1: We sincerely appreciate your summarization. The third point is true, while the first two points are not exactly true. Thus, we would like to clarify the first two points as follows: (1) With a proper score function (e.g., generalized score) and some mild assumptions (e.g., SMR), the exact search methods can output a MEC where only the NDC and BS parts can be correctly identified with fewest edges. GES could be problematic regarding the BS part (i.e., there might be more edges than the true graph, one example is given in Figure 2(b)). (2) With both the non-deterministic assumption (for the NDC part) and the SMR assumption (for the BS part), the correct MEC (regarding only the NDC and BS parts) is guaranteed to be the one with the fewest edges.

Q2: "Viewed this way, the results of the paper follow directly from what is already known about GES and the SMR assumption, and thus the contribution is fairly small. If this is incorrect, the authors should explain why in the paper. If the above is correct but there is more to it than that, the authors should clearly state the above intuition and provide more discussion of what is missing from that story."

A2: Thanks for your constructive suggestion. We would like to clarify our contributions as follows.

• Firstly, in the paper, we intend to provide a simple and reliable view to deal with the issues of deterministic relations for causal discovery. We found that: under some mild assumptions, the exact search methods can naturally used to solve the deterministic issues and output the MEC where both the BS part and the NDC part, can be correctly identified.

• Secondly, we proposed a novel method called DGES, in order to improve the efficiency of causal discovery in the presence of deterministic relations. Importantly, DGES is a general and versatile three-phase method, with no restricted assumption on the underlying functional causal models, in other words, it can accommodate both linear and nonlinear relationships, Gaussian and non-Gaussian data distributions, as well as continuous and discrete data types. Specifically, theoretical analysis and empirical evidence were provided to support our claim.

  • Theoretically, we provided the identifiability conditions for the BS part, besides the NDC part benefiting from GES.
  • Empirically, we conducted extensive experiments on both simulated and real-world datasets to show the efficacy of our proposed method.

(If you are interested, here we would like to explain why our method currently cannot identify the edges in the DC part. To achieve that goal, we usually need strong assumptions on the underlying functional causal model, i.e., Yang et al. [1] assumed the linear non-Gaussian model. However, those assumptions are not in alignment with our goal of a general method. That is why currently our method cannot identify the skeleton and directions in the DC part. However, fortunately, we can exactly find out which set of variables are in the DCs using some DC detection strategies, as shown in Section 3.3.)

We have included those details discussed above in Section 1 of our updated manuscript.

Q3: "In Section 1, the authors state that some methods 'suffer from identifiability guarantees.' It is unclear what this means."

A3: Thanks a lot for raising this concern. By "suffer from identifiability guarantees", we mean that there is no identifiability guarantee in those related works. In light of your comments, we have updated the expression to avoid confusion in the manuscript.

Q4: "In the abstract and Section 1, the authors state that they 'excitingly find' that certain methods can address the issues of deterministic relations. It is enough to state the finding, without excitement."

A4: Thank you so much for your careful reading and helpful suggestions. We have updated our expressions in the abstract and Section 1 of the manuscript, respectively.