Since Faithfulness Fails: The Performance Limits of Neural Causal Discovery

We sincerely appreciate the reviewer’s thoughtful feedback and their positive evaluation of our work. We are especially grateful for the recognition of the strong empirical evidence supporting our claims and rigorous controlled experiments that validate our approach. It is encouraging to hear that our systematic evaluations effectively support our findings and that our methodology successfully highlights the limitations of existing neural methods.

Additionally, we appreciate the acknowledgment that the use of synthetic datasets with known ground-truth causal structures is an appropriate choice. Our goal was to ensure a clear and interpretable evaluation, and we are pleased that the reviewer found this aspect of our work well justified. Finally, we are glad that the reviewer found the paper to be generally well-written, and we thank them for their time and effort in assessing our work.

Regarding suggestions from Experimental Designs Or Analyses:

1. We agree that evaluations on real-world graphs are vital for monitoring progress in causal discovery. However, there is a very limited amount of real-world data annotated with ground-truth graphs. Thus, the only viable way to conduct a comprehensive, large-scale analysis is to resort to synthetic data. Moreover, we follow the standard practice in causal discovery research by using widely accepted synthetic benchmarks. These datasets are not designed adversarially but are generated randomly. Thus, we believe the results are generalizable to real-world datasets.

2. Further, during the rebuttal phase, we conducted additional analyses of the lambda-faithfulness property for other types of graphs (scale-free, small-world, and bipartite). The results align with the observations on ER graphs, see Figure R.1 in the rebuttal material. These results will be added to the final version of the paper. We hope the reviewer finds them interesting and reassuring.

3. During the project, we conducted multiple ablations regarding the neural network architectures. Some of them are described in the appendix. Table 9 in Appendix A analyzes the impact of the network size on the performance of our optimized algorithm introduced in Section 3. In Appendix B, we provide a detailed study of the influence of network architecture on the performance of selected neural causal discovery methods. Notably, we compared architectures with residual connections and with layer norm; see Figure 9 in Appendix B. In all the cases, we found the behavior very similar to the one presented in the main body of the paper. We add a remark stating this.

We hope that the above answers resolve the reviewer’s concern. However, we’d be happy to perform additional analysis and add clarifications should the reviewer find that something is still missing.

We sincerely appreciate the Reviewer's positive feedback and thoughtful assessment of our work. We are glad that our benchmarking of representative neural causal discovery methods was recognized as both coherent and charitable, providing a clear and systematic evaluation of their limitations. We are also pleased that our claims were found to be well-supported. Moreover, we are grateful for the acknowledgment that our findings rigorously build upon and relate to prior work.

To clarify our claims (addressing feedback from Claims And Evidence section):

1. We claim that neural networks cannot reliably detect the absence or existence of causal relationships given practically available data volumes. The strength of causal relationships plays a crucial role; we quantify it using the notion of λ-faithfulness. We show that the required sample size will be infeasible in practical scenarios.

   We thank the Reviewer for suggesting the additional experiment with artificially ‘strong influence’. For the linear case, such an analysis was performed in [Uhler2013] (see Figure 5 in their paper). They show that increasing the strength does not change the overall picture. This might seem counterintuitive at first. However, increasing the direct links does not eliminate the exponential vanishing of λ-faithful distributions due to the cancellation of paths.

   We highlight this information in the revised version of the paper. Moreover, we run an analogous simple experiment for the non-linear case. Namely, during data generation, neural network weights were initialized with values spaced from zero by a factor c∈{0.0,0.5,1.0}. Importantly (and akin to the linear case), this did not result in observable differences in the distribution of the λ-property, see Figure R.2 in the rebuttal material

2. The reviewer is completely right. Using different approximators would unlikely solve the problem, and indeed, novel score functions or an alternative causal discovery objective are needed. We are sorry for the confusion. We have improved the description so that it is now explicitly stated. During the rebuttal, we provide another piece of evidence by using kernel-based PC (i.e., a non-NN approximator), observing that the slow convergence phenomenon is present. We include this result in Figure R.3 in the rebuttal material

3. We understand the reviewer's concerns regarding the size of the evaluation graphs. We will revise the description to refer to “small and medium-sized graphs”. (We also note that in Section 5, we use graphs with 30 nodes.)

As for the questions:

1. Please see our response to Claims and Evidence 1.
2. Please see our response to Claims and Evidence 2.
3. During the rebuttal, we compared kernel-based PC to our algorithm introduced in Section 3. As expected, we observed comparable performance.
4. The referenced sentence pertains to the experiment in Section 3.1. Our intended meaning is that the number of structures outside the MEC class that receive statistically equivalent scores decreases slowly as the number of samples increases. We will clarify this in the revised version of the paper.

Again, we thank the reviewer for the constructive criticism. The new version of the manuscript includes the textual improvements announced above and several other small amendments. Moreover, it includes the new experimental results. We’d be happy to address any additional questions or concerns.

[Uhler2013] Uhler, Caroline, et al. "Geometry of the faithfulness assumption in causal inference." The Annals of Statistics (2013): 436-463

We appreciate the Reviewer's thoughtful comments and acknowledgment of our work's importance in understanding neural causal discovery limitations. We admit shortcomings in the presentation, including those pointed out by the Reviewer. We have made a substantial effort to improve the quality.

Below, we clarify the specific concerns. To be on the safe side, we start with a short general summary.

Causal graph discovery has traditionally been framed as a discrete combinatorial problem. More recently, neural network-based continuous optimization methods have been introduced, offering scalability and computational efficiency. Our study reveals the key limitations of such approaches: likelihood-based methods that utilize neural networks struggle to distinguish between true and spurious causal connections when using realistically available data volumes. We show that the problem quickly exacerbates with the graph size. From this, we draw our key takeaway: the casual discovery community needs to search for alternative objective functions.

With this in mind, we now address the Reviewer's specific concerns.

Regarding results from sec. 3. The Reviewer points out a discrepancy between the improvement reported in Section 3 and our conclusion about the fundamental limitations. The latter stems from the observation, which is key to the whole paper, that even using substantial amounts of data (e.g., 8,000 samples), our idealized method fails to identify even small causal structures (5 nodes). Subsequently, we have confirmed that the problem persists even with 80,000 samples (see Figure R.3 in the rebuttal material)

Moreover, the results shown in Sec. 4 discuss how distributions associated with larger graphs quickly become highly complex, leading to a sharp increase in data requirements. Together, these results show that the structure identification of large graphs requires unrealistically large datasets.

On the conceptual level, the difficulty of discovery (i.e., the number of required samples) is highly correlated with $\lambda^{-1}$ from the $\lambda$-faithfulness notion. In Section 4, we show that $\lambda$ is typically small and decreases with the size of the graphs.

We will provide an improved conclusion paragraph that clearly states the above in the next revision of the paper.

Regarding sections 3 and 5 showing the same thing. Both graphs convey the same message: that casual discovery is not achievable using a practically available data regime. Sec 3 & 4 (Fig. 1b) show that large graphs require impractically large datasets (as discussed above), even when using idealized methods. Sec 5 (Fig. 3b) reinforces these findings, specifically, when using a practical method, we observe slow (or lack of) convergence.

We hope this clarifies the issue and will revise Sec. 5 accordingly. Please let us know if further questions arise.

Regarding the usage of synthetic datasets. We acknowledge concerns about our reliance on synthetic datasets, a necessity due to the absence of large, real-world datasets annotated with ground-truth causal graphs. However, we follow standard causal discovery practices, using widely accepted synthetic benchmarks that are randomly generated rather than adversarially designed, as in prior works. Thus, we believe the results are generalizable to real-world datasets.

In our rebuttal, we strengthen our results by providing lambda statistics for additional graph structures (scale-free, small-world, and bipartite), ensuring broader coverage of realistic scenarios, see Figure R.1 in the rebuttal material. Given these points, we believe our methodology is well-justified, but we are open to discussing further refinements if the Reviewer has specific suggestions.

We sincerely thank the Reviewer for their careful reading and for identifying the typographical errors. We will correct these and incorporate the requested neural network details in the final version.

We hope that this rebuttal clarifies the Reviewer's concerns and highlights the significance of our findings. We believe our work provides valuable insights into the limitations of current neural causal discovery methods and motivates the need for alternative objective functions. In light of these clarifications, we respectfully ask the Reviewer to reconsider their recommendation.

While we have endeavored to address all questions thoroughly, the character limit required us to keep our responses concise. We would be happy to provide further explanations if needed.