Since Faithfulness Fails: The Performance Limits of Neural Causal Discovery

We thank the Reviewer for providing their review. We are happy to learn that the Reviewer found the research hypothesis interesting and that the paper is cleanly written and well presented. Below we answer specific questions:

Weaknesses:

Ad 1: Please refer to the general response for a detailed explanation and justification of the DeFaith measure. We also adjusted the description of the DeFaith measure in section 4 accordingly.

Ad 2: We use synthetic datasets for practical reasons. It allows us to have full knowledge of various properties of datasets, especially the ground true graph, which are difficult to obtain for real-world datasets. We argue that our results are representative of many real-world problems since they are based on very general set of structures and functional approximators. Additionally, this type of evaluation is very popular in the literature (used in DCDI, NOTEARS, SDCD and many others).

Ad 3: To clarify, NN-opt is a brute force technique intended to be as powerful as possible in causal discovery. The price to pay is efficiency. NN-opt is helpful as an upper-bound benchmark but is not practical to use. Please see also the discussion in the general response.

Ad 4: We are currently running the requested experiment, we will provide the results as soon as possible.

Ad. 5: Thank you for pointing this out. We fixed that in the revised version of the paper.

Questions:

Ad 1: Yes, please see Appendix C.3 for a comparison of various architectures.

Ad 2: We added specific values that summarize our main result - limitations of neural score-based methods on the ER(5,1) graph.

We greatly appreciate the Reviewer's feedback and the opportunity to respond to their comments and questions. We have carefully considered the feedback and provided detailed explanations and evidence to address any concerns or uncertainties. If the Reviewer has any more questions, we are happy to provide any necessary explanation.

We thank the Reviewer for taking the time to provide thoughtful and constructive feedback on our submission. We are glad to hear that the Reviewer acknowledges the importance of the presented research topic and that our work is well-presented and sound. Below we provide answers to specific questions raised by the Reviewer.

Ad Weakness 1: We agree that theoretical analysis is always useful. However, due to a challenging topic, we first provide experimental evidence supporting our hypothesis. We would be happy to develop a theoretical explanation in the future. In the spirit of answering the Reviewer’s second question, we provide additional justification for the DeFaith metric in the general response.

Ad Q1: We evaluate causal discovery methods based on observational data. In general, due to identifiability issues, in this setup, it is only possible to recover true DAG up to a Markov Equivalence Class, a class of graphs with the same conditional independence relationships. If we were to compare the predicted and ground true graphs using standard metrics like SHD or F1-score we would obtain distorted results - graphs from the MEC class do not generally receive these metrics' optimal values. Therefore, we modify the formulation of the metrics to account for the limitations of causal discovery from observational data. The modified metrics attain their optimal values for all DAGs from the ground truth MEC. We added this explanation in Appendix D of the revised paper.

Ad Q2: Thank you for asking this question. Please find an additional explanation on how the DeFaith measure relates to the faithfulness assumption in the general response. We also adjusted the explanation in Section 4 accordingly.

Ad Q3: To clarify, NN-opt is a brute force technique intended to be as powerful as possible in causal discovery. The price to pay is efficiency. NN-opt is helpful as an upper-bound benchmark but is not practical to use. Please see also the discussion in the general response.

Ad Q4: We argue that this selection of four methods summarizes various research directions and improvements explored in neural causal discovery over the last four years and well represents the following selection of methods: NO-TEARS, NO-BEARS, NO-CURL, SCORE, DAGMA, DCDFG, DCDI, DiBS, BayesDAG, SDCD. Please refer to the general response for a detailed explanation. If the Reviewer thinks this comparison is too narrow, we kindly ask the Reviewer to specifically name additional methods that they think it is essential to compare against.

Please let us know if the above answers the Reviewer’s comments and questions. We would also be more than happy to address any other suggestions. In case there are none, and given the Reviewer’s positive outlook on soundness, presentation, and contribution, we would gently ask the Reviewer to consider increasing the score.

We thank the Reviewer for responding to our rebuttal. We are happy to hear that we were able to clarify most of the Reviewer's concerns. As for the theoretical grounding of our work, we describe the theoretical motivation for the DeFaith measure below.

The choice of the DeFaith measure formulation is based on the work of Zhang and Sprites and our observations on the properties of NN-based synthetic data. Zhang and Sprites seek a correct stronger definition of Faithfulness to provide guarantees of uniform consistency for causal structure inference. They formulate $\lambda$-Strong-Faithfulness in the following manner:

[Zhang & Sprites]: A distribution $P$ is said to be $\lambda$-Strong-Faithful to a DAG $G$ with observed variables V if for any $a,b \in V$ and $S \subseteq V \setminus \{a, b\}$

$a \text{ is d-connected to} \space b \space \text{given} \space S \space \text{in} \space G \iff |\rho(a,b|S)| > \lambda$

where $\rho(a,b|S)$ denotes conditional correlation between variables $a$, $b$ given set $S$. Note that 0-Strong-Faithfulness is just regular Faithfulness.

Further, Zhang and Sprites prove that when $\lambda$-Strong-Faithfulness is assumed causal structure can be inferred with uniform consistency. Additionally, crucially for our work, $\lambda$ can serve as a notion of the scale of Faithfulness violation. They write “a faithful but close to unfaithful distribution may be said to be unstable in the sense that some dependence relations may be destroyed by a slight change in parameterization. In this sense, the $\lambda$ in the $\lambda$-Strong-Faithfulness serves as a rough index of stability.” [Zhang & Sprites, Section 3.2]

We first aimed at using $\lambda$-Strong-Faithfulness as a Faithfulness violation measure in our paper. However, we observed that $\lambda$-Strong-Faithful distributions are extremely rare in the non-linear setting. Note that for $\lambda$-Strong-faithfulness to be fulfilled there has to be a threshold $\lambda$ for which the correlation between d-connected nodes is higher than $\lambda$, and the correlation between d-separated nodes is lower than $\lambda$. Since we were having a hard time generating distributions that fulfill this property, we decided to use the following definition of DeFaith:

$*DeFaith*(G) = \underset{a, b \in V, S \subseteq V \setminus \{a, b\}}{\mathit{AUROC}} (1 - |\rho(a, b | S)|, a \space \text{ is d-separated from} \space b \space \text{given} \space S \space \text{in} \space G)$

This formulation scores how close the sampled distribution is to fulfilling $\lambda$-Strong-Faithfulness. Note that acquiring a score of 1 in the DeFaith metric means that a distribution is $\lambda$-Strong-Faithful.

We hope that this explanation provides a theoretical link between the DeFaith measure and the Faithfulness assumption that the Reviewer was seeking. We will include it in the camera-ready version of the paper.

[Zhang & Sprites] Jiji Zhang, Peter Spirtes: Strong Faithfulness and Uniform Consistency in Causal Inference. UAI 2003: 632-639

We would like to express our sincere gratitude to the reviewer for their thoughtful and constructive feedback. We appreciate that the reviewer agrees with the assertion that faithfulness violations may be a key limitation within the current causal discovery paradigm. We are also glad that the Reviewer found the proposed metric for assessing faithfulness violations to be a sensible approach, and the paper well-organized and easy to follow. Below, we address the reviewers' questions and concerns, providing further clarification and responses.

Ad W1: We agree that theoretical analysis is always useful. However, due to a challenging topic, we first chose to provide experimental evidence supporting our hypothesis. We would like to point out that the data we used was generated using neural networks, which can express a general class of functions and therefore cover a wide range of setups. We would be happy to further develop a theoretical explanation in the future.

Ad W2: Yes, the NN-opt method is not scalable, however, it allows us to gain some insights into causal discovery that are otherwise impossible. We included a detailed discussion about the purpose of the NN-opt method in the general response.

Ad Q1: We decided to use it to be able to compare a wide set of methods. We included a more detailed discussion and justification in the general response.

Ad Q2: In our metric, we aggregate the results of independence tests measured using Spearman correlation. It can be computed for any distribution and graph (unlike $\lambda$-faithfulness [1]). Its limitations are derived from properties of the Spearman correlation coefficient. Assuming that Spearman correlation is never 0 when nodes are correlated, when faithfulness is fulfilled the DeFaith metric will return a value of 1. For further discussion about the DeFaith metric, please refer to the section with an explanation of the DeFaith measure in the general response.

Ad Q3: While NOTEARS is indeed one of the most well-known neural causal discovery, it limits the functional model, however, we tested the DCDI method, which is its successor NOTEARS. For details, please refer to the section regarding methods selection in the general response.

Ad Q4: To address this concern, we incorporated an ensemble of neural networks to ensure more robust scoring. Additionally, we analyzed the number of graphs with better scores to evaluate the extent of the problem. This analysis demonstrated that there are many graphs with higher scores than the ground true graph.

If any questions remain unanswered or if there are further concerns, we would be happy to provide additional clarification. Otherwise, we would kindly ask the reviewer to consider revising the score in light of the responses provided. Thank you again for your valuable feedback and thoughtful review.

References:

[1] Jiji Zhang, Peter Spirtes: Strong Faithfulness and Uniform Consistency in Causal Inference. UAI 2003: 632-639

We sincerely thank the reviewer for their thoughtful review and for taking the time to evaluate our work. We are grateful that you recognized the strengths of our paper, including the importance of moving away from the faithfulness assumption, the valuable insights into how limited faithfulness impacts performance, and the clarity of the writing. Below, we provide detailed responses to the reviewer's questions and address the concerns raised.

Ad W1: We say that $V$ is a set of endogenous variables and each $V_i$ has an exogenous noise variable $U_i$. To the best of our knowledge this is a standard definition of an SCM. If anything remains unclear we kindly ask the reviewer to rephrase the question so that we can provide an explanation.

Ad W2: We decided to use it to be able to compare a wide set of methods. We included a more detailed discussion and justification in the general response.

Ad W3: We added a concrete example of a simple graph, where faithfulness can be easily violated to Appendix A2 and mention it in Section 2.

Ad W4: We added a short explanation of the F1-score metric to the main text and a more detailed description of our evaluation methodology and justification for the formulation of metrics in appendix D.

Ad W5: We added missing results to the Table 1.

Ad W6: DiffAN is indeed an interesting method, offering flexibility by not constraining the neural network architecture and scaling well with graph dimensionality. However, the pruning step relies on sparse regression and to ensure the global score optimum lies in the true MEC class, we would have to pose additional constraints, which is out of scope of this work.

Ad W7: We are grateful for the suggestion to further explore variations in the MLP architecture. To address this, we expanded our testing by adding more architectural variations. Inspired by BayesDAG, we also implemented layer normalization and residual connections to assess their impact. We conducted additional experiments on both the best-performing model ([4, 4]) and the largest model ([8, 8, 8]). Please note that in all our experiments, the size of networks was similar to the ones proposed in the literature: in DCDI it was [16, 16], for SDCD it was [10, 10], for DiBS [5, 5] and for BayesDAG it was a two layer network with a hidden size varying with dimensionality. The effects of the comparison are discussed in section 3.3 and the plot was added to Appendix C.3 of the revised paper. We show, there is no significant and consistent improvement across all networks, supporting our initial conclusion that variations in MLP architecture have minimal impact on performance.

Ad W8: We define a predictor that classifies nodes as independent if conditional Spearman’s rank correlation coefficient computed based on a dataset D is smaller than a certain threshold. We improved the measure description in the revised version of the paper and provided additional explanations in the general response. If anything remains obscure please let us know.

Ad W9: Indeed, designing neural causal discovery methods without relying on the faithfulness assumption is a challenging and interesting area of research. While we emphasize its importance, addressing this topic in detail is beyond the scope of the current paper. We consider it a promising direction for future work, and describe existing approaches in the related work section.

If any questions remain unanswered or if there are further concerns, we would be happy to provide additional clarification. Otherwise, we would kindly ask the reviewer to consider revising the score in light of the responses provided. Thank you again for your valuable feedback and thoughtful review.

I would like to thank the authors for their response. I am revising my rating.

Explanation of the DeFaith measure

We would like to thank the Reviewers YhZG and CQrC for appreciating the effectiveness of the DeFaith metric in assessing the influence of the faithfulness violation on the performance. Below, we provide a more detailed description of the metric together with examples and intuition to answer the questions raised by the Reviewers YCC2 and CV1a. We also adjusted the measure description in Section 4 of the revised paper accordingly.

The faithfulness assumption translates into the set of conditional independence statements that need to be satisfied. The proposed DeFaith metric aggregates results of those independence tests. It can be viewed as consisting of two parts: (1)measuring degree of dependence, which is done by calculating conditional Spearman correlation and (2) aggregating the results of all tests, which is done using AUROC.

The spearman correlation coefficient is commonly used to quantify dependence in the non linear data. We selected this method due to its popularity and well known limitations. We would like to point out that we do not strive for novelty in our definition of the DeFaith metric. We try to resort to common and well-tested methods. Our original contribution lies in showing a strong correlation between the DeFaith measure with the average performance of neural causal discovery methods.

Original faithfulness formulation requires all independence tests to align with d-separation statements. However, we never observe this property empirically, thus we use the AUROC to quantify the faithfulness violations on a continuous scale.

Note, that if we assume that Spearman correlation is never 0 when nodes are correlated, then when faithfulness is fulfilled the DeFaith metric will return a value of 1. When the tests do not agree with d-separation statements from the graph better than random guessing then AUROC = 0.5.

Clarification for additive noise assumption

We adopt the additive noise assumption as it is explicitly used by many causal discovery methods, including BayesDAG and DiBS, which do not work in different regimes, ensuring fair comparison across approaches. DCDI and SDCD can handle non-additive noise, employing normalizing flows for this purpose, but such methods are more complex and less common, limiting comparability.

We hope that the above points are useful in reducing the confusion, but if anything remains obscure, we kindly ask the Reviewers to point it out to us. For specific answers to the Reviewers' individual concerns, please see our individual answers posted as separate comments.