Since Faithfulness Fails: The Performance Limits of Neural Causal Discovery
Authors: Mateusz Olko
Mateusz Gajewski
Joanna Wojciechowska
Mikołaj Morzy
Piotr Sankowski
Piotr Miłoś
Venue: ICML 2025 poster (2025)
Keywords: causal discovery
faithfulness assumption
neural networks
Primary area: general_machine_learning->causality
TL;DR: We show that the strong faithfulness violations limits the structure discovery accuracy of neural causal discovery method on standard benchmarks.

Abstract: Neural causal discovery methods have recently improved in terms of scalability and computational efficiency. However, our systematic evaluation highlights significant room for improvement in their accuracy when uncovering causal structures. We identify a fundamental limitation: 
\textit{unavoidable likelihood score estimation errors disallow distinguishing the true structure},
even for small graphs and relatively large sample sizes. 
Furthermore, we identify the faithfulness property as a critical bottleneck: (i) it is likely to be violated across any reasonable dataset size range, and (ii) its violation directly undermines the performance of neural penalized-likelihood discovery methods. These findings lead us to conclude that progress within the current paradigm is fundamentally constrained, necessitating a paradigm shift in this domain.

Since Faithfulness Fails: The Performance Limits of Neural Causal Discovery
Mateusz Olko 12 Mateusz Gajewski
Joanna Wojeiechowska' Mikolaj Morzy? Piotr Sankowski 245 Piotr Miloš 167
Abstract
In response to this challenge, we introduce unified bench- marking protocol for neural causal discovery methods. Specifically, we use identical datasets, tune hyperparameters consistently, and use a standardized functional approxima- tion across all methods. Through this systematic evaluation, we uncover a concerningly low level of performance. This raises fundamental question: Why do these methods strug- gle recover the ground-though causal structure even when the data is generated synthetically with all theoretical as- sumptions fulfilled and the dataset is large?
Neural causal discovery methods have recently improved in terms of scalability and compu- tational efficiency. However, our systematic evaluation highlights significant room for improvement in their accuracy when uncovering causal structures. We identify fundamental lim- itation: unavoidable likelihood score estimation errors disallow distinguishing the true siructure, even for small graphs and relatively large sample sizes. Furthermore, we identify the faithfulness property as a critical bottleneck: (i) it is likely to be violated across any reasonable dataset size range, and (ii) its violation directly undermines the performance of neural discovery methods. These findings lead us con- clude that progress within the current paradigm is fundamentally constrained, necessitating a paradigm shift in this domain.
We identify a fundamental limitation: unavoidable likeli- hood estimation errors disallow distinguishing the true struc- ture. This happens primarily due finite size of the datasets. However, we observe minimal improvements when scaling either the data the network size. At technical level, we pinpoint the faithfulness property critical bottleneck. We formalize faithfulness violations in finite datasets using the strong- strong-faithfulnee faithfulness measure. Then, we show that any strength of the faithfulness easily violated when graph size or density are increased. Even for moderate size graphs it likely to be violated across any reasonable dataset size range. We believe these limitations highlight the need for paradigm shift rather than incremental improvements in architecture or optimization techniques.
1. Introduction
Causal discovery is essential for scientific research, driving growing demand for machine learning methods support this process. Despite the development of several neural causal discovery methods in recent years (Brouillard et al., 2020; Lorch et al., 2021; Annadani et al., 2023; Nazaret et al., 2024), their performance remains insufficient for real- world applications, particularly fields such as medicine and biology (de Castro et al., 2019; Peters al., 2016). Furthermore, these methods usually evaluated using datasets, which vary between studies, obscuring the overall picture and making the assessment of advances difficult.
In more details, our contributions are as follows:
In carefully controlled experiment, we demonstrate that the likelihood loss, as used by causal discovery approaches, faces estimation errors which disallow the recovery of ground-truth causal graphs, even for small graphs and relatively large sample sizes.
"Fqual contribution 'IDEAS NCBR, Warsaw, Poland UUniversity of Warsaw, Warsaw, Poland 'Pozman University of Technology, Poznan, Poland "MIM Solutions, Warsaw, Poland 'Research Institute IDEAS, Warsaw, Poland "Institute of Mathematics, Polish Academy of Sciences, Warsaw, Poland deepsennee.i, Warsaw, Poland. Correspondence to: Ma- teusz Olko <mateuszzolkode gmail.com>,, Mateusz Gajewski <mg96272 gmmailmmmaa..........
2. We propose practical method of approximation of A-strong faithfulness property for nonlinear datasets. We experimentally demonstrate how proportion of X- unfaithfull distributions scales with the size and density of graphs from Erdos-Renyi class.
3. We provide results of unified benchmark for neural causal discovery methods and show that their perfor- mance correlates with X-strong faithfulness property of the datasets.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The Performance Limits of Neural Causal Discovery
2. Background and Related Work
et al., 2018; Lachapelle et al., 2019), improving upon the original by separating structural and functional parameters and incorporating interventional data. SDCD unifies and advances various acyclicity constraints proposed in methods like NO-BEARS (Lee et al., 2019) and DAGMA (Bello et al., 2022), demonstrating superior performance compared to SCORE (Rolland et al., 2022) and DCDFG (Lopez et al., 2022). For Bayesian approaches, we chose DiBS, which incorporates NO-TEARS regularization in its prior, and BayesDAG, which builds on NO-CURL's DAG parametriza- tion (Yu et al., 2021) using MCMC optimization.
Structural causal models (SCMs). Causal relationships are commonly formalized (Pearl, 2009) using SCMs, which represent causal dependencies through set of structural equations. For directed acyclic graph (DAG) G = (V,E), an SCM is defined by a set of equations of the form:
X = f((Pac(i), U4),
(1)
where X; is a random variable at vertex i E V.
fe: IR Pa.l++ + R is function, Pia(i) denotes the set of parents of i in G. and U, is an independent noise. In this work, we assume additive noise SCMs, also referred to additive noise models (ANM), viz.,
All these approaches use a continuous representation of the graph structure, enforcing a differentiable acyclicity con- straint to ensure the result is a DAG. The primary objective is maximize log pe (Xl9), that is the log-likelihood of the data given the graph while incorporating regularization terms to control graph complexity. Such methods are in general described as penalized likelihood causal discovery methods. The discovery procedure comprises two parts: fitting functional approximators and structure search, which are usually done in parallel.
I<(Pag()) U.) = (a(PPa()) + U,
for some g:: ((Pac(0) + R. An SCM M = (G, [fihev, kUv)ev) defines joint distibution P over the set of random variables {Xi)eev.
Causal discovery. Causal discovery aims to uncover causal structure G of SCM based on data sampled from the joint distribution P. However, in general the solution can only be identified up to a Markov Equivalence Class (MEC), the set of DAGs encoding the same conditional independencies (Verma & Pearl, 1990).
The penalized likelihood methods, are among most general class of methods. In principle they do not need any paramet- ric assumptions on functions and noises. DCDI (Brouillard et al., 2020) and SDCD (Nazaret et al., 2024) can work in non-linear setting with non-additive noise, while Bayes- Dag (Annadani et al., 2023) and DiBS (Lorch et al., 2021) make only additive noise assumption.
While there is line of classical methods like PC (Spirtes et al., 2000) or GES (Chickering, 2020), those algorithms work well for linear relationships and moderate-sized prob- lems, they struggle in more challenging scenarios. Neural causal discovery methods have emerged as a promising direction, offering class of methods that could potentially handle nonlinear relationships and provide computational efficiency, and scalability in both data size and number of variables.
Hardness of causal discovery. The so-called faithfulness property is fundamental assumption commonly used by causal discovery methods (Pearl, 2009; Brouillard et al., 2020). is formulated as follows:
Vo.MewVSEVMaass).... TL Xo|Xs - a Lg b|S.
(3)
where 1L denotes conditional independence and Lg de- notes d-separation. For more information on d-separation please refer to Appendix A.I. The faithfulness property can be violated when multiple causal paths cancel each other (see example in Appendix A.2). While the set of unfaith- ful distributions associated with given DAG has measure zero (Boeken et al., 2025), distributions may exhibit arbitrar- ily weak conditional dependencies. When dealing with final datasets, such weak dependencies become indistinguishable from independence.
Evaluating causal discovery methods presents unique chal- lenges. In real-world applications, ground truth causal struc- tures are typically unknown or can only be partially elicited from domain experts with inherent noise and bias. This fundamental limitation necessitates the use of synthetic data for evaluations, as they provide controlled environments essential for understanding the methods' capabilities and limitations.
Recent developments in neural causal discovery. We would like to highlight four recent approaches to neu- ral causal discovery: DCDI (Brouillard et al., 2020), SDCD (Nazaret et al., 2024), DiBS (Lorch et al., 2021), and BayesDAG (Annadani et al., 2023), which in our view ef- fectively represent the major developments in neural causal discovery from past years. DCDI represents the evolution of NO-TEARS-basser methods like GRAN-DAG (Zheng
This observation motivated Zhang & Spirtes, 2003 to intro- duce the X-strong faithfulness assumption. A distribution P is said to be X-strong faithful to a DAG g if:
Vusev (X/x > X = a Lg B/S,
(4)
2

---

The Performance Limits of Neural Causal Discovery
where Pp(Xa: X5 X)) denotes partial correlation coef- ficient and À E 1), For linear systems, this assump- tion ensures uniform consistency of the PC algorithm with À x 1/vn where the sample size + oo. Therefore, À can serve as a notion of the difficulty of the causal discovery task.
that separates conditionally d-separated from d-connected nodes (see equation 5). In practice, due irreducible errors in correlation estimation from finite data and the presence of small true correlation values, it is infeasible to establish the separating threshold. Instead we choose the threshold that maximizes the Fl-score of classification to d-separated and d-connected nodes.
Notably Uhler al. (2013) proved that, in case of linear SCMs, for any fixed À > 0, the fraction of X-strong faithful distributions decreases exponentially with graph size and density, suggesting fundamental limitations in causal discov- ery on large graphs. The work provides theoretical results for linear SCMs and the PC algorithm.
Effective approximation of X. Specifically, we use partial Spearman correlation, classifying node pairs d-separated if their conditional correlation coefficient, computed from the finite dataset, falls below a given threshold. We then define as the threshold that optimizes the Fl-score of this classification. Formally, for dataset 'D and associated with it DAG G: A argmax, Fi (L,,,,)))
However so far little has been shown regarding nonlinear functions and contemporary neural network approaches. We aim breach the gap with our experimental contributions, thus the remainder of the paper is structured as follows. First, we build framework that allows us to measure the difficulty of the problem, expressed by X-strong faithfulness property, and show grows quickly with the size and density of the underlying graph (Section 3.1.. Than, we demonstrate that the difficulty is connected to the number of samples required to recover the true graph (Section 3.2). Our framework mimics the linear case described above. Finally, in Section 4, we evaluate contemporary neural causal discovery methods and analyze their performance in relation to the problem difficulty measure.
(6)
(,(),
(ttt,D.)) = 2- P(t, + D,
P(L, = #(a,b, b,S S: La b|S}
P(t,D, #(a, b, S: la b|8)| < t)
2, = #,a.b, ( b[8)] < t and Le b|5}
where pD(a, bJS) denotes the partial Spearman correlation coefficient computed from dataset D, and a Lo b|S de- notes d-separation in graph G. Note, that when data size increases estimation errors in the partial Spearman corre- lation pD b|S) decrease. Thus, in the limit of the data Ả converges to A. For an experimental evaluation of the estimation accuracy and precision on finite datasets, please refer to Appendix D.
3. Estimation of Strong Faithfulness Property and Likelihood Score
For a fixed distribution P and associated with it graph G there can be multiple À that satisfy the Equation 4. There- fore, in the remainder of the paper we will denote À as the maximal threshold satisfying the equation. Additionally, as are working with nonlinear data, we use Spearman cor- relation coefficient, which we will denote pp with slight abuse of notation. Specifically, for a given distribution P associated with graphs 9 we define:
Fraction of >-strong distributions. In case of linear datasets, the relation between the fraction of sampled X- strong distribution and the graph density and number of nodes has been extensively studied by Uhler et al. (2013). was proved, for several types of connected graphs, that the fraction of X-strong faithful distributions decreases exponen- tially. Here we provide analogous experimental results for nonlinear SCMs based on connected Erdos- Renos- graphs. The details of the experimental setup and results for more graph types are provided in the Appendix B.
= max(t: Va (a.1) (pp(Xa, Xo|Xs) > + a bSS). (5)
3.1. À decreases quickly with growing graph size and density.
In Figures la and 1b we plot how fraction of A-unfaithful distributions changes with the number of nodes and the density of the graph respectively. Our experimental results align with theoretical study on linear datasets. We observe that for fixed À and number of nodes, the proportion of distributions that are not X-strong decreases with the ex- pected neighborhood size, similar observation can be made when we increase the number of nodes in a graph. Even for relatively small and sparse graphs (6 nodes and expected
We aim to measure the difficulty of causal discovery given non-linear dataset D and associated with structure ex- pressed by the parameter. Theoretically, À could be de- termined by computing partial correlations for all variable pairs across all conditioning sets and identifying threshold
When À= 0, this reduces to the standard faithfulness assumption.
3

---

Since, we need be able to compute the score for each graph G in class of DAGs over the node set density function The Performance Limits of Neural Causal Discovery
1.0
Fraction of unfakthul distiuutios
Fraction of unfaarhul distbuutions
0.8
0.8
0.7
0.6
0.5
0.4
0.3
0.3
0.03
0.03
0.3
0.01
0.2
0.01
10
0.75
1.75
2.50
Number of modes
Expected degree
(a)
(b)
Figure 1: (a) Estimated fraction of X-unfaithful distributions for Erdos-Renyl graphs with various number of nodes, (b) Estimated fraction of X-unfaithful distributions for Erdos-Renyi graphs with 6 nodes and varying density. Colored lines correspond to specific values of X.
neighborhood size 1) more than 60% of distributions are not faithful for À = 0.03 and more than 80% for 0.1. We get similar results for bipartite, small-world, and scale-free graphs. They are presented in Figure in Appendix B.
S(G) Σ -og s(x;; XPac (. (a) 7
(8)
1EV
where |G| denotes number of edges in G and y 0 is sparsity coefficient.
3.2. Lower Ả requires larger sample size
We investigate how affects convergence rate causal discovery algorithms with neural-network approximators. To be able draw conclusions about impact of data sample on the accuracy of causal discovery design conceptu- ally simple neural network based causal discovery method that minimizes approximation errors. We evaluate it in controlled setting that enables a comprehensive analysis to identify bottlenecks in the neural causal discovery process.
Further, to reduce approximation errors due to initialization, we also employ random seed bootstrapping. The training procedure is repeated times starting from different ran- dom initializations. The final formula for the score uses the average of N estimates:
N log f(x;; Xpa 0 (a) + G
S(G) = Σ
N
EV
R=1
Exhaustive estimation approach. Our goal estimate the regularized likeliidl score, common objective function in neural causal discovery. For graph G with nodes set V the log-like likelihood of the dataset D = hXv can be expressed as the sum of log-likelihoods of individual vectors X,:
This procedure drives the approximation error down negligible level, at the cost of significant computational effort, and, through bootstrap confidence intervals, lets us isolate estimation eтror from approximation error.
We summarize our efforts to minimize approximation error:
L(G) Σ
log (X,(a(a())))..
The neural network approximator and the data- generating model belong to the same class no model misspecification.
2. Additionally, evaluate multiple network architec- tures and confirm our architectural choice experimen- tally (see Table in Appendix C).
V. we train neural-network-basss
[(X;; (paa()) 0 (a)) for each variable X; and each par- ent set (ia(() C V {i}. Note, that unlike scalable NN approaches, we have a different set parameters 6;, Paçay (i) for each parent set (i). This reduces approximation error.. The penalized score can now be written as:
3.
We use an ensemble approach over multiple random initialization, which not only improves accuracy but also provides bootstrap confidence interval for the ap- proximation error.

---

The Performance Limits of Neural Causal Discovery
0.6
-0.5
0.5
-1.0
ESHO-O
between CPDAGS
-1.5
10g2o
-2.0
2.5
-3.0
0.1
-3.5
10?
10*
10
10
2.5K
0.0
Minimal sample size required for convergence
Observational sample
(a)
Figure 2: (a) Relation of sample needed to for distribution to converge and the Å. (a) Linear regression between the minimal sample size required for true structure recovery and logio(A) measure. The spearman rank correlation those measures is -0.93 and p-value for correlation is 9c-4. (b) Comparison of the performance of NN-opt method depending on data size. Averaged over 90 samples. For definition of ESHDDPDAG please refer to Section 4.
Assuming is small enough and the faithfulness assumption holds, the DAG that minimizes the score in Equation will belong to the MEC of data generating graph (Brouillard al., 2020).
timates in Figure 3. For this experiment, we generated a dataset as described above and applied our exhaustive es- timation method using 800 samples. We used bootstrap sample size of N 29. the score estimates were accurate, the structures within the Markov Equivalence Class (MEC) would consistently receive the lowest scores (highlighted in red in the figure). However, we observe that substantial number of alternative structures are assigned comparable or better scores depicted blue and green, respectively. Importantly, when the dataset size is increased to 8,000, the number of green and blue structures decreases significantly, indicating that the exact faithfulness assumption holds.
Remark 3.1. Notice that, given score estimation described above, we can discover the MEC by exhaustive evaluation of all DAGs in the given class. The method is not practically useful, but can illustrate the influence of estimation and approximation errors on causal discovery process. Since, graph search component is removed the method can also be viewed upper-bound existing differentiable approaches to causal discovery relying similar neural-network ap- proximators. The pseudocode of the method can be found in Appendix G.
The convergence rate of our causal discovery method correlates with X. We generate 90 synthetic datasets and evaluate causal discovery approach described in Remark I. We experiment with various the best performing one which happens to be identical as used to generate the data (see Appendix C). The ensemble size used this experiment N = 3. For each dataset we evaluate causal discovery on subsets of varying sizes. The size of the smallest subset required for convergence is recorded and compared to value of À of the dataset. The results are presented in Figure 2a. The experiment demon- strates that datasets with higher Á require usually fewer samples for successful recovery. The À and minimal num- ber of samples is highly correlated, the spearman correlation coefficient -0.93.
Synthetics causal data. We generate synthetic data with a known ground-truth causal structure. We consider causal DAGs with only five nodes == (1,..., We generate these DAGs using the Erdos-Renyi model with the expected number of edges. The functional relations between nodes modeled by randomly initialized MIPs with two hidden layers of size 8. Additionally, we additive Gaussian noise: U, (0, o;), where a; may depend on i E V. For more details refer to Appendix E.
sizes and select
The maximum likelihood estimator is biased. The MLE objective yields biased estimates of the score. This bias not systematic; instead, varies randomly depending on the training sample. We illustrate examplary score es-
5

---

The Performance Limits of Neural Causal Discovery
-2.0
-0.5
-2.2
-1.0
Score
Score
-2.4
-1.5
-2.6
-2.0
-2.8
Structures
Structures
Significantly better score
Significantly better score
No significant difference in score
No significant difference in score
Best graph from MEC
Best graph from MEC
(a)
(b)
Figure 3: Exemplary results of score evaluation using our robust neural network based approximation approach. In red score the target structure, in green - scores of structures with statistically significantly better scores, in blue - scores of structures with comparable scores. The error bars signify 95% confidence intervals. Note that considerable number of structures has significantly better (lower) score that the target structure. (a) Plot for 800 samples. (b) Plot for 8000 samples.
Accuracy of causal discovery improves with data size. Apart from convergence, want to quantify structural er- rors when recovery is incomplete, to assess model reliability and compare methods. Understanding how these errors de- crease with more data provides insight into the efficiency of the learning process. The results are presented in Fig- ure 2b. For very small datasets we observe relatively big ESHDcPDAG of 4, which rapidly improves with sample size. As the sample size grows, the structure discovery accuracy stabilizes. For sample sizes of 2,500 and 8,000, the average value of ESHDCPDAG is just below 2. In the dataset used for this experiment, the average number of edges in CPDAG around 8.4, meaning that on average almost 25% of the edges are predicted incorrectly.
3.3. Conclusions
In this section, we provided detailed experimental analysis of the relationship between the X-strong faithfulness prop- erty of non-linear datasets and the performance of causal discovery with neural function approximators. Our results indicate that the X-strong faithfulness property constrains causal discovery from finite data, limiting both convergence rate and accuracy. Furthermore, we demonstrate in con- trolled setting that data scarcity introduces significant errors in score assignment. Additionally, show that the pro- portion of X-strong faithful distributions in ER graphs with nonlinear functions rapidly decreases as graph density and size increase. Those findings, along with the theoretical results of Uhler al. (2013), suggests that current neural causal discovery methods may face fundamental limitations.
As previously observed, datasets vary in difficulty, and the number of correctly identified structures increases with sample size. While the average ESHDePDAG remains significantly above zero, structural recovery improves notably from 6 converged graphs at 80 samples to 26 at 250. This trend continues, though at a diminishing rate: 34 and graphs converge 2,500 and 8,000 samples, respectively, and 37 and 53 at 25,000 and 80,000. These results indicate that larger sample sizes enable more accurate structure discovery. However, the marginal gains decrease, and even with 80,000 samples, correct recovery of all structures is not achieved.
4. Evaluation of Neural Causal Discovery Methods
After linking the challenges in neural causal discovery to À strong faithfulness in Sections 3.2 and 3. in this sec- tion, investigate how this violation affects neural causal discovery methods performance in terms of structural met- rics. Additionally since these methods were constructed with scalability in mind, the experiments can be performed on graph bigger that in Section 3.
6

---

The Performance Limits of Neural Causal Discovery
ER(5,
ER(10, 2)
ER(30, 2)
Method
ESHDePDAG
F1-ScOreCPDAG
ESHDePDAG
F1-ScOreCPIAG
ESHDePDAG
F1-ScOrecPDAG
DCDI
5.7 (.7.8.)
0.60 (0:4,, 0.74)
16.9 (157,
0.52 (0.50, 0.56)
45.9
0.73 (169,
BayesDAG
3.9 (36,43)
0.78 (8.77, 081)
18.3 (169, 19.8)
0.56 (0.54, 0.59)
51.7 (48.2. 55.9)
0.59 (0.57. 061)
DiBS
(1.7.7)) 37)
0.85 (0.80, 0.90)
16.9 (142, 201)
0.61 (0.57, 0.80
68.0 (65.3 3. 70.9)
0.23 (0.22, 0.24)
SDCD
5.4 (388 6.7)
0.60 (0.35, 0.69
20.9 (19.5, 22.2)
0.54 (0.46, .2))
62.8 (88.8, 67.7)
0.55 (0.53, 0.58)
Table 1: Comparison of ESHDCPDAG and FI-ScoreCPDAG for different methods on ER(10, 2) (left) and ER(30, 2) (right) dataset. The numbers in the subseripts correspond to 95% confidence intervals. The statistics were computed based on 30 graphs.
4.1. The systematic benchmarking protocol
The Structural Hamming Distance (SHD) (Tsamardinos et al., 2006) counts edge insertions, deletions, and reversals needed to match the predicted graph to the true graph. We define Expected SHD between CPDAGs as:
We evaluate methods DiBS, DCDI, BayesDAG, and SDCD introduced in Section 2 on identical datasets, tune hyperparameters consistently, and use a common functional approximation.
Dataset generation We sample three types of graphs from the Erdös-Rényi (ER) distribution (Erdös & Rényi, 1959) as deseribed in 3.1: one with 5 nodes and the expected degree of 1, another with 10 nodes and the expected degree of 2, and the third with 30 nodes and the expected degree of 2. These datasets are referred to as ER(5, 1), ER(10, 2), and ER(30, 2), respectively. These parameter choices align with commonly studied medium-sized graphs in causal discovery research (Brouillard al., 2020; Nazaret et al., 2024).
ESHDCPDAG (G, G)
= -G (Srr>c|SSH(CCCHC (CPDAG())(() CPDAG(("))) (10)
where G is the resulting distribution of graphs, G is a graph sampled from G and 9 is the ground true graph. The F1- Score measures the harmonic mean of precision and recall for edge predictions. We compute the Expected F1-Score between the CPDAGs follows:
Hyperparameter tuning To ensure a fair comparison across all methods, we perform systematic hyperparameter tuning, selecting the berf-perfo parameters for each method We employ a grid search approach based on the parameter ranges suggested by the original authors. This process optimizes key variables such as regularization coef- ficients, sparsity controls, and kernel configurations. Details can be found in Appendix E.2.
F1-ScorecPnAG(G, G)
-Eg-a//F1- I1l-Score(CPDGG(SS CPDAG(())) (11)
For more details and justification on the selection of metries please refer to Appendix F,
Functional approximators We standardize the choice of functional approximators across all experiments, using a two-layer MLP with a hidden dimension of 4 to model each functional dependence f (see Section 2). This model size is consistent with previous work (Brouillard al., 2020; Nazaret al., 2024) and has proven perform well across all the benchmarked methods, as discussed in Appendix E.3. Additionally, we use trainable variance to allow the model to adapt to varying noise levels, in line with our dataset generation setup.
Methods comparison Table 1, summarizes the bench- mark results of neural- based causal discovery methods on graphs from ER(5, 1), ER(10, 2), and ER(30, 2) classes. We tune hyperparameters to optimize the ESHDcPDAG metric. For all classes of graphs, metrics were computed based on 30 graphs.
The results show that DiBS is particularly effective for smaller graphs (ER(5, 1) and ER(10, 2)), while DCDI able to achieve the best results for moderate-size graphs (ER(10, 2) and ER(30, 2)). The ranking of the methods changes with the size of the graphs but SDCD consistently exhibits the worst performance in terms of ESHD
Structure evaluation We evaluate graph discovery within the MEC using ESHDerDAG and F1-ScorecrDAG, where ESHDDPDAGG = 0 and F1-ScOreçPDAG predicted graph is in the same MEC as the ground truth. For Bayesian methods, we computed the expected value by sampling from the posterior distribution; for non- aa-Baaesiaan methods, we use single graph.
when the
Nevertheless, the structural metrics of all the methods re- mains unsatisfactory with all methods predicting more than half of the edges incorrectly.
7

---

The Performance Limits of Neural Causal Discovery
ESHD between CPDAGS
30
27.5
DCDI
BayesDag
ISHD between CPDAGs
25.0
DIBS
SDCD
22.5
20.0
20
17.5
15
15.0
12.5
10.0
-2
20
80
250
800
2.5K
8K
25k
1o))
Observational sample size
(a)
(h)
Figure 4: (a) Linear regression fit between the average performance of neural causal discovery methods and logio(A) (A) measure. The p-value for spearman rank correlation between \ and ESHDDePDAG and is 4e-6, signifying anti-monotonic correlation. b) Performance of benchmarked methods in terms of ESHDCPDAG with resect to dataset size for ER(10, 2) graphs, averaged over 30 samples.
4.2. À and NCD method performance
rameter tuning (as described in Section 4.1). l). For example, DiBS shows the best performance on larger datasets, but its improvements plateau after around 800 samples. Simi- larly, BayesDAG shows only marginal improvements with larger sample sizes and is unable outperform DiBS. DCDI improves up to 250 samples and then maintains consistent performance regardless of the sample size, similar to DiBS. Interestingly, SDCD's ' performance is poor on datasets with small number of observations but begins to improve once sample sizes exceed 250, though unable to reach DCDI's performance, for larger sample sizes the rate of improve- ment decreases.
To investigate the tie between Å metric and the difficulty of neural causal discovery. we generate 30 graphs from the ER(10, 2) class, introduced in Section 4.1. Based on each graph, we define three different SCMs, resulting in 90 distinct distributions. From each
generate 8,000 observational samples. We then evaluate the Ả of each dataset and compute the performance of the selected neural- based causal discovery methods.
In Figure 4a we present the relationship between average performance of all methods and the logarithm of X (for readibility) for all 90 distributions in the dataset. The perfor- mance is better (lower SHD) for distributions with higher X. The Spearman's 's rank correlation coefficient is p -0.46 and p-value for sperman correlation test is 4e 6. This result proves the strong anti-monotonicity between and average methods' performance.
Further analysis of the effect of sample size smaller graphs ER(5, 1)ís presented in Figure 14 in Appendix F. Overall, the results on smaller graphs align with the trends observed on larger graphs. Specifically, while some methods improve with increasing sample size, others show inconsis- tent or even degraded performance.
4.3. Lack of scalability
Even for the bigger sample sizes the results remains satisfactory. This confirms our observations, made in the previous sections about datasets difficulty and the amount of samples required for convergence. We conclude, that the amount of data needed to recover a graph from a true MEC with those methods out of scope for most applications.
We want to investigate the impact that the sample size has on a causal discovery methods. We expect to behave simi- lar to our findings from Section 3.2 as we hypothesize that the lack of performance is due relation between data and approximators. We would like to note that the NCD meth- ods use neural network to approximate the distribution under changing set of parents, which is harder task than the one in Section 3.2. We evaluate the benchmarked methods on datasets with varying number of observational samples, ranging from 20 to 8,000 observations.
5. Limitations and Future Work
Work of Lippe al. (2022) suggests that interventional data can replace the need for faithfulness assumption. A valuable extension of research would be to eval- uate the performance of the benchmarked methods on interventional datasets to understand their limitations and potential improvements in this context.
The results, presented in Figure 4b, reveal no consistent pattern of improvement in the ESHDePDAG metric obser- vational sample size increases, despite extensive hyperpa-
8

---

The Performance Limits of Neural Causal Discovery
Our work provides experimental evidence for the chal- lenging nature of causal discovery from non-linear data, especially when using neural networks. It would be beneficial for the community to establish theoretical bounds on the best possible performance in such cases.
deviate significantly from synthetic benchmarks based on uniformly initialized neural networks. A promising direc- tion in this regard is the recent work by Gamella et al. (2025), which uses physical simulations to generate causal datasets. This approach preserves the complexity and realism of phys- ical systems while offering ground-truth causal structures, making it a valuable resource for future benchmarking.
Neural networks are well known approximators, with well established position in Machine Learning commu- nity. It will be however interesting to investigate other classes of aproximators, that could possibly have a bet- ter suited characteristic for the task of causal discovery.
While many causal discovery methods rely on the strong faithfulness assumption, alternative frameworks have been proposed. For linear structural causal models (SCMs), Van de Geer & Büihlmann (2013) demonstrated that sparsity- based
Our conclusions are based on characteristic of distri- butions associated with Bayesian Networks provided by Uhler et al. (2013). The result says that for any fixed X, X-strong faithful distributions vanish exponen- tially with the size of the graph. It may hold, though is highly unprobable, that real- world distributions adhere to X-strong faithfulness despite large sizes of the graph. Further investigation is required.
S the sparsest Markov repre- sentation can recover causal structure without relying on strong faithfulness. Similarly, Ng et al. (2021) proposed a method that operates under a relaxed faithfulness condition, requiring fewer conditional independencies to hold. Another underexplored direction involves relaxing the discovery task itself by focusing on uncovering partial causal structures or specific conditional independencies, as explored by Amini et al. (2022).
6. Discussion
In conclusion, we believe that recognizing and addressing the limitations imposed by A-strong faithfulness is crucial for the development of more robust and generalizable causal discovery methods. Future research should explore both alternative assumptions and reformulations of the causal discovery task to better align with the complexities of real- world data.
In this work, we conducted a detailed experimental anal- ysis of the relationship between the X-strong faithfulness property in nonlinear datasets and the performance of causal discovery methods based on neural function approximators. Our findings indicate that the X-strong faithfulness assump- tion imposes significant constraint on causal discovery from finite data, adversely affecting both convergence rates and accuracy.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
We further demonstrate that the proportion of X-strongly faithful distributions in various connected graph types with nonlinear mechanisms decreases rapidly as graph density and size increase. This phenomenon implies that, in practi- cal scenarios involving large or dense graphs, the probability of encountering X-faithful data becomes vanishingly small. We also show a clear correlation between the degree of X- strong faithfulness and the performance of diffcrentiable, basre causal discovery methods, indicating that the assumption plays a central role in the tractability of these approaches.
A Acknowledgments
This work was supported by Horizon Europe Programme under GA no. 101120237, project "ELIAS: European Light- house of AI for Sustainability" and the National Science Centre (NCN) Grant no. 2020/37/BSST//4479 Piotr Mitoš's research was supported by the National Science Center (Poland) grant number 201 ht/33////S///344// We gratefully acknowledge Polish high-performance computing infrastructure PL.Grid (HPC Center: ACK Cyfronet AGH) for providing computer facilities and support within compu- tational grant no. PLGG/024/016606.
To the best of our knowledge, this is the first study to empir- ically connect X-strong faithfulness to the performance of score-based causal discovery methods, extending prior theo- retical insights which focused primarily on independence- test-based approaches (Zhang & Spirtes, 2003). Our results suggest that gains in efficiency and accuracy for neural- based causal discovery methods may be approaching funda- mental limits, driven by the intrinsic properties of the data distributions rather than algorithmic shortcomings.
References
Amini, A. A., Aragam, B., and Zhou, Q. A non non-graphical representation of conditional independence via the neigh- bourhood lattice. arXiv preprint arXiv:2206.0588 05829, 2022.
These findings highlight the importance of evaluating causal discovery algorithms on real-worle datasets, which may

---

The Performance Limits of Neural Causal Discovery
Annadani, Y., Pawlowski, N., Jennings, J., Bauer, S., Zhang, C., and Gong, W. Bayesdag: Gradient-based posterior inference for causal discovery. In Oh, A., Naumann, T., Globerson, A.. Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans,
Lorch, L., Rothfuss, J., Schölkopf, B., and Krause, A. Dibs: Differentiable bayesian structure learning. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 24111-24123, 2021.
LA, USA, December 10- 16, 2023, 2023.
Nair, V. and Hinton, G. E. Rectified linear units improve restricted boltzmann machines. In Fürnkranz, J. and Joachims, T. (eds.), Proceedings of the 27th International Conference on Machine Learning (ICML-10), June 21-24, 2010, Haifa, Israel, pp. 807-814. Omnipress, 2010.
Bello, K., Aragam, B., and Ravikumar, P. Dagma: Learn- ing dags via m- m-matrices and a log-determinatt acyclicity characterization. Advances in Neural Information Pro- cessing Systems, (188226-8239) 2022.
Boeken, P., Forré, P., and Mooij, J. M. Are bayesian net- works typically faithful?, 2025.
Nazaret, A., Hong, J., Azizi. E., and Blei, D. M. Stable dif- ferentiable causal discovery. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024.
Brouillard, P., Lachapelle, S., Lacoste, A., Lacoste-Julien, S., and Drouin, A. Differentiable causal discovery from interventional data, In Larochelle, H., Ranzato, M., Had- sell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Ng. I., Zheng, Y., Zhang, J., and Zhang, K. Reliable causal discovery with improved exact search and weaker as- sumptions. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 00308-20320, 2021.
Chickering, M. Statistically efficient greedy equivalence search. In Conference on Uncertainty in Artificial Intelli- gence, pp. 241-249. Pmir, 2020.
de Castro, D. C., Walker, I., and Glocker, B. Causality mat- ters in medical imaging. CoRR, abs/1912.081 142, 2019.
Pearl, J. Causality. Cambridge University Press, 2 edition, 2009. doi: 10. 10.1017//B09780511 00000097855111001110 1803161.
Erdös, P. and Rényi, A. On random graphs i. Publicationes Mathematicae Debrecen, 6:290-297, 1959.
Peters, J., Bühlmann. P., and Meinshausen, N. Causal in- ference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical So- ciety Series B: Statistical Methodology, 7855)9977-111,, 2016.
Gamella, J. L., Peters, J.. and Bühlmann, P. Causal cham- bers as a real-world physical testbed for ai methodology. Nature Machine Intelligence, pp. 1-12, 2025.
Rolland, P., Cevher, V., Kleindessner, M., Russell, C., Janz- ing, D., Schölkopf, B., and Locatello, F. Score matching enables causal discovery of nonlinear additive noise mod- cls. In International Conference on Machine Learning, pp. 18741-18753, PMLR, 2022.
Lachapelle, S., Brouillard, P., Deleu, T., and Lacoste-Julien, S. Gradient-based neural dag learning, arXiv preprint 1iXi::9966.02266. 2019.
Lee, H.-C., Danieletto, M., Miotto, R., Cherng, S. T., and Dudley, J. T. Scaling structural learning with no-bears to infer causal transcriptome networks. In Pacific Sympo- sium on Biocomputing 2020, pp. 391-402. World Scien- tific, 2019.
Spirtes, P., Glymour, C., and Scheines, R. Causation, Pre- diction, and Search, Second Edition. Adaptive compu- tation and machine learning. MIT Press, 2000. ISBN 778-0-262-194400
Lippe, P., Cohen, T., and Gavves, E. Efficient neural causal discovery without acyclicity constraints. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenRe- view.net, 2022.
Tsamardinos, I., Brown, L. E., and Aliferis, C. F. The max- min hill-climbing bayesian network structure learning algorithm. Mach. Learn., 65(1):31-78. 2006. doi: 10.
Lopez, R., Hütter, J.-C., Pritchard, J., and Regev, A. Large- scale differentiable causal discovery of factor graphs. Ad- vances in Neural Information Processing Systems, 35: 19290-19303, 2022.
Uhler, C., Raskutti, G., Bühlmann, P., and Yu, B. Geometry of the faithfulness assumption in causal inference. The Annals of Statistics, 41(2), April 2013. ISSN 0090-5364. doi: 10. 11.1224//2- 1080.
10

---

The Performance Limits of Neural Causal Discovery
Van de Geer, S. and Bühlmann, P. O-penalized maximum likelihood for sparse directed acyelic graphs. 2013.
Verma, and Pearl, J. Equivalence and synthesis of causal models. Bonissone, P. P., Henrion, M., Kanal, L. N., and Lemmer, J. (eds.), UAI '90: Proceedings of the Sixth Annual Conference Uncertainty in Artificial In- telligence, MIT, Cambridge, MA, USA, July 27-29, 1990, pp. 255-270. Elsevier, 1990.
Yu, Y., Gao, T., Yin, N., and Ji, Q. Dags with no curl: An efficient dag structure learning approach. In Inter- national Conference on Machine Learning, pp. 12156- 12166. Pmir, 2021.
Zhang, and Spirtes, P. Strong faithfulness and uniform consistency in causal inference. In Meek, C. and Kjærulff, U. (eds.), UAI '03, Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence, Acapulco, Mex- ico, August 7-10 2003, pp. 632-639. Morgan Kaufmann, 2003.
Zheng, X., Aragam, B., Ravikumar, P., and Xing, E. P. Dags with NO TEARS: continuous optimization for structure learning. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.). Advances in Neural Information Processing Sys- tems 31: Annual Conference on Neural Information Pro- cessing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 9492-9503, 2018.

---

The Performance Limits of Neural Causal Discovery
A. Additional background information
A.1. d-separation
Two nodes A and B in a DAG are said to be d-separated by a set of nodes Z all paths between A and B are blocked when conditioning on Z. path is considered blocked under the following conditions:
If path includes a non-collider node (a node where arrows do not converge, i.e., a chain or fork), conditioning on that node blocks the path. For example, - C - B, or A t C - B, conditioning on C' makes A and B independent.
If the path includes a collider (a node where arrows converge, i.e., A < B), the path is blocked unless either the collider itself or one of its descendants is conditioned on. For instance, in the path A - C <- B, conditioning on C' or its descendants would unblock the path, making and dependent.
If there are multiple paths connecting A and B, all paths must be blocked for A and B to be considered d-separated. Even if one path remains unblocked, A and B are d-connected, meaning they are dependent.
In causal discovery, distribution. Given causal graph G and the data distribution P, the Markov assumption states that if variables A and B are d-separated in the graph G' by some conditioning set C, then A and B are conditionally independent in the distribution P when conditioned on the same conditioning set C. Formally, this can be written as:
interested in making statements about the relationship between the causal graph and the data
A Le BIC + A Alp BJC
(12)
A.2. Example of faithfulness violation
In this subsection we will illustrate a faithfulness violation for a simple 3 nodes structural causal model with linear functions and additive Gaussian noise. Such a setup is aimed at showing example of faithfulness violation while maintaining simplicity. The example and graphics is from Uhler et al. (2013).
2
3
Figure 5: Simple 3 nodes graph G.
First lets define a structural causal model on graph G shown in graph
X1 E1,
X₂ 01 + E2,
X3 = 013Xi + X2 + N)OOI),
(E1, E3)
Since data is linear we can use covariance to measure dependency of variables. Using defined structural causal model, we can write:
12

---

The Performance Limits of Neural Causal Discovery
cov (01, = 012;
(13)
cov(X1, = 013 + 012023.
(14)
cov(X2, Xz)
aiz023 + 012013 + 023
(15)
cov (X1, X2 X3)
013023 012
(16)
cov (X1 X3 X22)
-013
(17)
cov 22, X3 X1)
= -02--
(18)
If we define 413, a23, 012 in such way that:
013 023
01, =0
then we get a situation where: nodes 1 and 2 are not d-separated given node 3 in a graph G and X1 1 X2(X3 which is a violation of faithfulness.
B. Additional strong faithfulness statistics
Experimental setup In all experiments regarding strong faithfulness statistics, including those in the main paper, we used the following approach. We sampled 100 graph structures according to each of the graph sampling methods: Erdos-Renyi, wre.eeBaaaasii-lllaooo
small world (Watts-Strogats), with layers, hidden dimension 8, and ReLU activation, to generate 1.5M samples from each SCM. Using those datasets we have been able obtain À according to Equation
and bipartite. Then we used randomly initialized neural networks
Most of the graph generation methods return graphs that are guaranteed be connected. However, Erdos-Renyi graphs can be disjoined if the density parameter is chosen incorrectly. The ER graphs have the property that when the probability of an edge exceeds (og(n)/n, where is the number of nodes, then they are almost surely connected (Erdös & Rényi, 1959). Thus, in case of ER graphs we adjust the density of the graph with its size. We use the following formula for the probability of an edge:
log(n)
p
(19)
where is the density parameter. We consider two scenarios (i) the density kept the lowest possible guarantee the graph connected 1.1 (ii) the density is tuned so that we obtain graphs with 10 nodes and expected number of edges 20, which are comprable in terms of density with graphs generated with other methods, c 1.9302. Table summarizes the densities of the ER graphs. All other types of graphs have expected numbers of edges equal to twice the number of nodes.
Number of nodes
4
6
7
10
Expected number of edges 1.1
2.29
3.54
4.93
6.42
8.01
9.67
11.40
Expected number of edges 1.9302
4.01
6.21
8.65
11.27
14.05
16.96
20.00
Table The densities of ER graphs.
The results are presented in Figures 6 & 7. In all cases we observe rapid vanishing of faithful distributions as graph size or density increases.
C. NN-opt method details
Details of experiments with NN-opt method In order test which architecture perform best, we conducted an experiment, training NN-opt method with different sizes of neural networks. The trained models were judged in terms of negative log likelihood and their performance on the task of causal discovery measured as ESHDDPDAGG For each tested architecture, we performed the search for the best regularization coefficient, the tested coefficients were: [0.1, 0.3, 1.0]. Among all models, the best results were consistently obtained for regularization coefficient = 0.3. The learning rate was set to 0.0003. The results of the experiments are shown in Table As we can see, the best, both in case of NLL and ESHDCPDAG was model with two layers and hidden dimension of size Notably this the same architecture, as was used to generate data.
13

---

The Performance Limits of Neural Causal Discovery
Erdds Rényi model:
Rrdyi medel:
Erdos-Rényi model; 1.9302
Fracton oFA unio dicthuutors
Focton of unfokhheldiiiii di-ibutions
0.9
0.8
0.8
0.6
0.6
0.4
0.5
0.1
0.2
0.1
0.1
0.03
0.03
0.03
0.3
0.50
1.25
1.50
1,75
2.00
2.25
2.50
10
Expected
Number nodes
Number
(a)
(b)
(c)
Figure 6: Summary of results of À statistics for Erdös-Rény graphs.
Bipartite
Barabési-Albert model;
Watts Strogatz model: K=4,
Fraction erA urrate disthuuttrs
ofctlmn ar uf disibuttorss
0.8
0.8
0.8
Praction unfare-d
0.6
0.8
0.1
0.1
0.1
0.03
0.03
0.03
0.0
0.0
0.0
Number
Number nodes
Number
(a)
(b)
(c)
Figure 7: Additional results of statistics for (a) bipartite graphs, (b) scale-free graphs (genrated using Barabasi- Albert model), and (c) small-world graphs (generated using Watts-Strogatz model). The results consistent with observations ER graphs. We observe rapid vanishing of X-faithful distibutions.
14

---

The Performance Limits of Neural Causal Discovery
Selected hyperparameters: Number of layers
hidden dimension 8, regularization coefficient 0.3.
Model architecture
NLL
ESHDCPDAG
[4]
0.33 0.43)
3.63/283,40 4.67)
[4,4] 4]
0.2
3. 3.15
[4, 4]
0.23 0.34)
3.03/233,4.07 4,07)
[8]
18 0.29)
2. ((143, 3.07)
[8, 8]
0.13 0.24)
1.23 (0.77, 1.87)
[8, 8]
0. 0.22 0.32)
2.77 3.67)
[16]
0.14.0.03 0.26)
1.77 2.73)
16, 16]
0.33 0.43
2.4
[16, 16, 16]
0.88.o.. 4.0x3.7..497)
Table 3: The performance NN-opt method models with different architectures. The numbers subscripts, correspond 0.95 confidence intervals. The experiments were performed on 30 graphs.
D. Errors in computation
We evaluate the quality of Á estimation. In Table 4 report the bootstrap standard error and bootstrap bias for estimates Å. We standard data generation protocol based ER graphs and randomly initialized NNs, as described in the main text. We generate datasets for 10 random SCMs and report aggregate statistics for two sample sizes: 1.5M as was used to generate plots in Section 3.1 and Appendix B and 100K as was used in Section 4. The bootstrap size was 100 due to computational constraints.
Min
Max
Mean
Median
100K samples
Bootstrap Standard Error Bootstrap Bias
2.00e-3
9.38e-3
3.93e-3
3.19e-3
4.73e-5
5.92e-3
2.84e-3
3.92e-3
1.5M samples
Bootstrap Standard Error
6.17e-4
1.15e-2
2.2c-3
7.98e-4
Bootstrap Bias
5.25e-6
1.19e-2
1.71e-3
1.81e-4
Table 4: Aggregated statistics of bootstrap standard error and bias of Å estimation.
E. Details About Benchmark and Extensions
E.1. Dataset generation details
The data generated using a fully connected MLP with two hidden layers of units each, initialized with random weights drawn from a standard normal distribution and use the ReLU (Nair Hinton, 2010) activation function introduce non-linearity. The neural network models the relationships between variables in the underlying DAG, where each node represents a variable and the edges capture dependencies between these variables. The input variables, which serve the initial causes in the graph, are sampled from normal distributions. The noise added to the system is sampled from Gaussian distribution (0, 0.1²), simulating uncertainty in the model. The dataset consists of 100,000 data points, and the data is rescaled to maintain consistency across samples.
E.2. Model hyperparameters
We performed extensive hyperparameter tuning for all methods. In addition to the MLP architecture grids described in Appendix E.4, the following hyperparameter grids were explored:
DCDI Grid search: Regularization coefficients tested: [0.1, 0.3, 1, 2]. Values below 0.001 or above 5 led to poor
performance. Selected: Regularization coefficient 1, learning rate 0.001, Augmented Lagrangian tolerance = 10-8
15

---

The Performance Limits of Neural Causal Discovery
DiBS
DCDI
BayesDAG
SDCD
30
ESHD between CPDAGs
25
20
15
10
[8] [4]
[4, 4]
[8, 8
[16, [16. 161
[8, 8, 1,
[4]
[8]
[4, 41
[8, 81
[16, 161
81
[4]
[8]
[4. 4]
[8, [8, 8]
[16, 16.
[8, 8. 81
[4]
[8]
[4, 4]
18, 8]
[16, [16.66] 16]
[8, 8. 81
(8,8.0
[8, 8
88.8.
MLP architecture
Figure 8: Comparison of ESHDDCPDAG using different MLP architectures as functional approximator for ER(10, 2) dataset and 800 observational samples, averaged over 30 samples.
DiBS Grid search: Alpha linear: [0.01, 0.02, 0.05), kernel parameters: h latent: [0.5, 2.0]. theta: [20.0, 50.0, 200.0), step size:[0.05, 0.03, 0.01, 0.005, 0.003J. Selected: Alpha linear = 0.02, h latent = 1.0, h theta = 50.0, step size 0.03.
E.3. Testing models architecture
Finally, investigate the impact of the neural model architecture, used the functional approximator, the performance of the benchmarked methods. Specifically, we assess how the capacity of different architectures influences the ability to uncover causal relationships from synthetic data. To provide a comprehensive evaluation, we explored architectures with 1, 2, and 3 layers, configured with 4, 8, and 16 hidden units.
Results, presented in Figure show the comparison of ESHDCPDAG metric for the benchmarked architectures across all methods on dataset with 800 samples. We find that the choice of neural architecture has no significant impact on performance across methods. We conclude that any of the tested MLP architectures provides sufficient capacity to model the underlying distribution effectively. Additionally for BayesDAG and SDCD implemented layer normalization and residual connections. We investigated the impact of this changes in architectures and did not found any significant differences, see Figure 13. The details and additional experimental results are in Appendix E.4.
BayesDAG Grid search: Scale noise: [0.1, 0.01], scale noise p: [0.1, 0.01, 1.0], lambda sparse: [50.0, 100.0, 300.0, 500.0]. Selected: Scale noise 0.1, scale noise p 0.01, lambda sparse 500.0.
SDCD
Grid search: Constraint modes: ["exp", "spectral radius", "matrix power"). The ESHDePDNG metric showed similar results across modes. Selected: Spectral radius was chosen for faster computation, with learning rate 0.0003.
For each of these method, all other parameters were retained from the original paper or code.
E.4. Model architecture comparision within method
16

---

The Performance Limits of Neural Causal Discovery
1 hidden layer
2 hidden layers
hidden layers
28
parameters/hid dim
28
parameters/hid _iim dim
28
parameters/hid dim
4
4
4
26
8
26
8
26
16
16
Eshd between CPDAGs
24
Eshd between CPDAGs
24
Eshd between CPDAGs
22
22
22
20
20
18
18
18
16
16
16
14
14
10
20
40
80
800
10
20
40
80
800 80000000
10
20
40
80
800 800080000
Number of train samples
Number of train samples
Number of train samples
Figure 9: Comparison of the ESHD DCDI for datasets with different observational sample size. The result is based on 10 graphs.
DCDI In Figure 9, we present the performance analysis of the DCDI across various neural network configurations. Our results reveal that the optimal performance is generally achieved by a two-layer model with hidden dimension of Interestingly, we observe that more expressive models exhibit diminished performance relative the smaller models.
Figure 10 presents the performance analysis of the DiBS method across various neural network configurations. As with the DCDI method, evaluate models with different numbers of layers and hidden dimension sizes. Consistent with DCDI, we find that the optimal performance for DiBS is achieved by two-layer model with hidden dimension of 4. However, the performance landscape for DiBS exhibits less variability across different model configurations. Single-layer models perform nearly as well as the optimal two-layer model.
DIBS
Furthermore, we observe that more expressive models do not show significant degradation in performance as was seen with DCDI. The overall differences in metric across all tested configurations are relatively small for DiBS, indicating more consistent performance across varying levels of model complexity.
BayesDAG Figure 11 compares the performance of BayesDAG across different model architectures and sample sizes. For smaller sample sizes, BayesDAG's performance remains consistent, with noticeable differences emerging only at a sample size of 800. This suggests that BayesDAG requires more data to fully leverage its model capacity, unlike what observed for DCDI and DiBS, where performance varied more significantly across sample sizes. Notably, the best-performing architecture for DiBS is two-layer MIP with a hidden dimension of 4.
Figure 12 presents similar comparison of SDCD performance across different MI.P architectures and sample sizes. Interestingly, the three-layer architectures show stagnant performance regardless of sample size, while the one-layer models exhibit significant improvement as the sample size increases. Overall, the best performance is achieved with one-layer MLP with 8 hidden units, although it remains comparable to the one-layer MLP with 4 hidden units and the two-layer MLP with 4 hidden units.
SDCD
Model architecture 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]). The size of networks was similar to the one proposed in articles introducing tested methods: in DCDI it was [16, 16), for SDCD was [10, 10], for DiBS [5. 5) and for BayesDAG was two layer network with hidden size varying
17

---

The Performance Limits of Neural Causal Discovery
1 hidden layer
hidden layers
hidden layers
24
hid dim
24
24
hid dim
22
22
22
Eshd between CPDAGs
Eshd between CPDAGs
Eshd between CPDAGs
20
20
20
18
18
18
16
16
16
hid dim
14
14
14
4
8
12
12
16
12
20
800
20
800
20
800
Number of train samples
Number of train samples
Number of train samples
Figure 10: Comparison of the performance of DiBS depending the model architecture and number of samples.
with dimensionality. The results these tests are presented Figure 13, 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.
F. Justification of evaluation metrics
We design metrics based on popular SHD, Fl-score metrics, which we explain shortly below.
The Structural Hamming Distance. SHD (Tsamardinos et al., 2006) quantifies the difference between the predicted graph and the ground truth graph by counting the number edge insertions, deletions, and reversals required to transform one into other. SHD values indicate the degree of error recovering the true causal structure: lower SHD values signify better predictions, while higher values indicate more significant discrepancies.
The Fi-score. The F1-Score measures the harmonic mean of precision and recall for edge predictions, where precision reflects the fraction of correctly predicted edges among all predicted edges, and recall reflects the fraction of correctly predicted edges among the true edges.
We evaluate causal discovery methods based on observational data. In general, in this setup. it is only possible to recover true DAG up to Markov Equivalence Class, a class of graphs with the same conditional independence relationships, due to identifiability issues TODO cite pearl?. we were to compare the predicted and ground true graphs using standard metrics like SHD or Fi-score we would obtain distorted results - graphs from MBC class do not generally receive these metrics' optimal values.
Therefore, modify the formulation of the metrics account for the limitations of causal discovery from observational data. We define ESHDcPDAG and FI-ScorecPDAG- These metrics attain their optimal values, 0 and 1 correspondingly. for all DAG from ground truth MEC. Additionally, some of the benchmarked methods are Bayesian thus return the posterior over possible solutions. For those methods, we design metrics that compute the expected value over the posterior and approximate it with the Montecarlo estimator based on sample of size 100.
We define Expected SHD between CPDAGs as:
18

---

The Performance Limits of Neural Causal Discovery
1 hidden layer
hidden layers
hidden layers
parameters/hidden size
parameters/hidden size
4
8
24
8
24
24
Eshd between CPDAGs
Eshd between CPDAGs
Eshd between CPDAGs
20
20
20
18
18
18
parameters/hidden size
16
16
16
8
20
800
20
800
20
800
Number of train samples
Number of train samples
Number of train samples
Figure 11: Comparison of the performance of DiBS depending the model architecture and number of samples.
ESHDePDAG(9, ( (SHD((CDG))(C) (PAA CPDAG(G")))
(20)
where G is the resulting distribution of graphs, 9 is graph sampled from G and is the ground true graph. Similarly, we compute the Expected F1-Score between the CPDAGs:
F1-ScorecPDAG (9. G) = Eg- [I-SScor(CCDAAG()) CPDAG
(21)
subsectionInfluence of sample samples on performance on the graph with ER(5, 1)
Figure shows the ESHDePDAG of benchmachmarked methods different sample sizes. For all observational sample sizes, SDCD and DCDI have large confidence interval. For datasets with 2,500 and 8,000 samples, BayesDAG performs better than other benchmarked methods, getting small confidence interval for 8,000 samples.
G. Al Algoritm pseudocode
Pseudocode of the method described in Sec. 3 is provided in Algorithm 1.
19

---

The Performance Limits of Neural Causal Discovery
1 hidden layer
2 hidden layers
3 hidden layers
parameters/dim hidden
parameters/dim hidden
parameters/dim hidden
35
35
35
4
4
4
16
Eshd between CPDAGs
Eshd between CPDAGs
Eshd between CPDAGs
25
25
25
20
20
20
15
15
15
800
8000
800
8000
800 Number of train samples
8000
Number of train samples
Number of train samples
Figure 12: Comparison of the performance of SDCD depending on the model architecture and number of samples.
Algorithm Overview of NN-Opt
1: Input: Set of nodes V, training data (Di)ev regularizaion coefficient X, the space of DAGs with nodes
2: # Part 1: Network fitting
3: for i E V and S V \ {i} do
> For each variable and each possible parent set b Train ensembles of 3 networks
4: 0g.r +- TRAINNETWORK(; D,T))
5: end for
6: # Part 2: Exhaustive graph search
7: for G E G do
Evaluate all possible DAGs b. Compute NLL using ensemble
8: scoreg + Eiev (D,,UTENLL(D,, Draç, P.Pp
9: scoreg t- scoreg A |G|
> Add regularizing term
10: end for
Output: arg maxose G G)
20

---

The Performance Limits of Neural Causal Discovery
BayesDag
BayesDag [8, 8, 8]
SDCD [4, 4]
SDCD [8, 8, 8]
[4, 4]
24
ESHD between CPDAGs
22
20
18
16
14
12
Norm, Residual
Norm
Residual
Vanilla
Norm, Residual
Norm
Residual
Vanilla
Norm, Residual
Norm
Residual
Vanilla
Norm, Residual
Norm
Residual
Vanilla
MLP architecture
Figure 13: Comparison the performance of SDCD depending on the model architecture and number of samples.
14
BayesDAG
DCDI
ESHD between CPDAGs
12
SDCD
10
8
6
4
2
0
20
80
250
800
2.5K
8K
Observational sample size
Figure 14: Comparision of ESHDCPPAG for benchmarked methods ER(5, 1) dataset, averaged over 10 graphs.
21


Reviews:
[{"review_id": "QRFgYvC5ay", "reviewer": "Reviewer_6UaB", "summary": "This work critically examines the limitations of neural causal discovery methods, revealing their fundamental inability to distinguish causal relationships in finite-sample regimes reliably. Through a systematic benchmarking protocol, the authors demonstrate that even state-of-the-art neural approaches struggle to recover ground-truth causal structures, attributing this failure to estimation errors and the violation of the faithfulness assumption. The study quantifies the difficulty of causal discovery using the λ-strong faithfulness property and shows that as graph size increases, the proportion of faithful distributions decreases exponentially, fundamentally constraining current methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\nAdditionally, 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.\n\n\nRegarding suggestions from *Experimental Designs Or Analyses*:\n\n1. 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.\n\n2. 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](https://drive.google.com/file/d/1m7rFfvf2_xoQorCprk6RE1MiITmYivhy/view?usp=sharing). These results will be added to the final version of the paper. We hope the reviewer finds them interesting and reassuring.\n\n3. 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.\n\nWe 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.", "claims_and_evidence": "The paper provides strong empirical evidence to support its claims, using a rigorous controlled experiments. The claim that neural causal discovery methods struggle to recover ground-truth structures is well-supported by systematic evaluations across multiple datasets and methods. Additionally, the argument that the faithfulness assumption is a key bottleneck is backed by quantitative analysis of λ-strong faithfulness.", "methods_and_evaluation_criteria": "The paper introduces a systematic benchmarking framework that standardizes datasets, hyperparameter tuning, and functional approximations, ensuring robust and fair comparisons across methods. The use of synthetic datasets with known ground-truth causal structures is an appropriate choice for evaluating structural recovery accuracy, while the incorporation of the λ-strong faithfulness property provides a theoretically grounded measure of dataset difficulty. This approach effectively demonstrates the limitations of existing neural methods. However, the inclusion of real-world datasets would further strengthen the study by assessing whether these challenges persist in practical applications.", "theoretical_claims": "This work primarily focuses on empirical contributions rather than formal theoretical proofs.", "experimental_designs_or_analyses": "- As mentioned previously, this work focuses only on synthetic data, while recommending others, in the discussion section, to use real-world datasets.\n- The graphs analyzed in this work were generated only using the Erdos-Renyi model. It would be insightful to know whether the results generalizes to other graph classes such as scale-free, small-world, etc.\n- Additionally, authors can perform ablation studies to better understand how different neural network architectures (depth, width, activation functions) affect causal graph recovery.", "relation_to_broader_scientific_literature": "While neural methods aim to improve scalability, the study empirically shows they struggle under finite samples due to faithfulness violations. By quantifying the impact of λ-strong faithfulness, the paper highlights fundamental constraints and the need for alternative causal discovery paradigms.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "The paper is generally well-written, aside from the following typos.", "other_comments_or_suggestions": "Please correct the following typos:\n- Section 1 (line 48): unfaithfull -> unfaithful\n- Section 2, the line “An SCM defines a joint distibution P over the set of random vairables {Xi}” is repeated twice.\n- Multiple occurrences of “distibution” instead of “distribution.”\n- Figure 1, last sentence has incorrect section reference.\n- Title of section 3 and 3.1 are same.\n- Section 3.2 (line 245): hat -> that\n- Section 4 (line 258) -> ot -> to", "questions_for_authors": "None", "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": "TMZWFyKkiG", "reviewer": "Reviewer_JYG6", "summary": "This paper claims that while neural causal discovery methods have become more scalable, they fundamentally struggle with accuracy when identifying true causal relationships. Neural networks are unable to reliably distinguish between real and non-existent causal connections in finite samples, and violations of the faithfulness property—which occur frequently in practice—significantly undermine their performance. The authors conclude that these limitations require a paradigm shift in the field of neural causal discovery.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nBelow, we clarify the specific concerns. To be on the safe side, we start with a short general summary. \n\nCausal 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. \nFrom this, we draw our key takeaway: the casual discovery community needs to search for alternative objective functions. \n\n\nWith this in mind, we now address the Reviewer's specific concerns.\n\n\n**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](https://drive.google.com/file/d/1m7rFfvf2_xoQorCprk6RE1MiITmYivhy/view?usp=sharing))\n\nMoreover, 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.\n\nOn 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. \n\nWe will provide an improved conclusion paragraph that clearly states the above in the next revision of the paper.\n\n**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.\n\nWe hope this clarifies the issue and will revise Sec. 5 accordingly. Please let us know if further questions arise.\n\n**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.\n\nIn 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](https://drive.google.com/file/d/1m7rFfvf2_xoQorCprk6RE1MiITmYivhy/view?usp=sharing). Given these points, we believe our methodology is well-justified, but we are open to discussing further refinements if the Reviewer has specific suggestions.\n\n***\n\n\nWe 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.\n\nWe 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.\n\nWhile 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.", "claims_and_evidence": "I feel that I don't understand section 3. It seems like section 3 shows that as sample size increases, the neural network does better and better at identifying the structure. Then the conclusion claims that methods can't identify structure consistently. The prose directly above that conclusion states that larger samples enables identification of structures in more difficult datasets. How can I reconcile these two things?\n\nThe metrics of lamba and lambda hat make sense to me, and its cool that these measures correlate with the number of samples needed for convergence.", "methods_and_evaluation_criteria": "I am not familiar with the state of the art methods in neural causal discovery, so I can't say whether the methods they chose are an appropriate spread of the state-of-the-art models.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "The experimental design of using neural networks to generate a dataset and then training neural networks to perform causal discovery on that dataset seems reasonable to me if the goal is to problematize their ability to do causal discovery.", "relation_to_broader_scientific_literature": "I think understanding how to leverage neural networks for causal discovery is broadly of huge importance, and showing their limitations can be very helpful in that process.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I feel like I might be missing the main point of this paper. Section 5 has prose that references section 3 as if section 3 showed that neural network models don't scale with the number of examples provided in training, but that is not what section 3 says at all. It says that neural models get better the more data that is provided. \n\nCould you explain how Figure 1b and Figure 3b are saying the same thing? From my perspective, they are showing very different results. \n\nSeparately, if the whole point of this paper is arguing for a paradigm shift in causal discovery away from neural networks, how can this whole paper only use artificial datasets? I don't think a field should progress by people constructing difficult datasets that show methods fail, shouldn't we be grounded out in some sort of real world dataset or phenomena?\n\n\"It may hold, though is highly unprobable, that real-world distributions adhere to λ-strong faithfulness despite large sizes of the graph. Further investigation is required\"\nThis quote from the end of section 6 is really important to me. I think making a technical point about NCD methods and where they struggle is totally a reasonable and good thing to do. However, if you want to argue that the field needs a paradigm shift, I feel you must ground out this claim in an evaluation of the real world data the field someday wants to model. Without an argument that the assumptions you made in the paper will hold in real-world setting, I feel I have to reject this paper based on how ambitious and far-reaching the introduction, title, and abstract are.", "other_comments_or_suggestions": "245 \"hat the number\" -> \"that the number\"\n\nFigure 1 caption has Section ??\n\nline 290 Faithfull", "questions_for_authors": "N/A", "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": "6RRammbRAY", "reviewer": "Reviewer_ERvU", "summary": "The paper benchmarks several representative neural causal discovery methods in a coherent and charitable way, revealing consistent shortcomings. These are attributed to faithfulness violations, even in large sample sizes and small graphs, suggesting a more fundamental flaw in the neural causal discovery paradigm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nTo clarify our claims (addressing feedback from *Claims And Evidence* section):\n\n\n1. 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. \n\n    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.\n\n    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](https://drive.google.com/file/d/1m7rFfvf2_xoQorCprk6RE1MiITmYivhy/view?usp=sharing)\n\n2. 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.\nDuring 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](https://drive.google.com/file/d/1m7rFfvf2_xoQorCprk6RE1MiITmYivhy/view?usp=sharing)\n\n3. 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.)\n\n\nAs for the questions:\n1. Please see our response to Claims and Evidence 1.\n2. Please see our response to Claims and Evidence 2.\n3. During the rebuttal, we compared kernel-based PC to our algorithm introduced in Section 3. As expected, we observed comparable performance.\n4. 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.\n\nAgain, 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.\n\n[Uhler2013] Uhler, Caroline, et al. \"Geometry of the faithfulness assumption in causal inference.\" The Annals of Statistics (2013): 436-463", "claims_and_evidence": "I generally found the claims clearly stated and well-supported, with two important exceptions:\n1. it's claimed that neural methods can't detect absence/existence of causal relationships, but it's not clear to me that randomly initialized NNs are guaranteed to have 'strong enough' influence; in linear simulations, it's common to sample weights $\\mathrm{abs}(w) > 0.5$, but it's not if clear anything similar was done here\n2. NNs are universal function approximators, so it's unclear to me how a different approximator is going to solve the problem; rather seems to me different objective functions are needed---and the paper doesn't give evidence that it's specifically a NN problem, disentangled from the similar objective functions the neural approaches are using.\n\nAnd some less important exceptions:\n3. In Section 5: \"These parameter choices align with commonly studied medium-sized graphs in causal discovery research\". I wouldn't say 5- and 10-node graphs are medium-sized, and expected degrees of 1 and 2 are quite sparse.", "methods_and_evaluation_criteria": "Yes, these all seem reasonable.", "theoretical_claims": "N/a", "experimental_designs_or_analyses": "Yes, these all seem reasonable, other than related to points 1 and 3 in _Claims and evidence_ above.", "relation_to_broader_scientific_literature": "The findings here more systematically and rigorously support and relate previous findings concerning $\\lambda$-faithfulness and poor performance of neural causal discovery methods.\n\nThe paper doesn't really make claims about non-neural causal discovery, but it would interesting to see at least some standard/state of the art non-neural methods included for comparison, such as kernel PC or GRaSP.", "essential_references_not_discussed": "Nothing missing that I'm aware of.", "other_strengths_and_weaknesses": "Already covered.", "other_comments_or_suggestions": "- second paragraph in intro: should be \"ground-truth\" instead of \"ground-though\"\n- end of paragraph after (5): should be \"bridge the gap\" instead of \"breach...\"\n- in Section 3: should be \"Synthetic\" not \"Synthetics\"\n- missing label in caption of Figure 1(b), so it appears as ??\n- __conclusion__ before Section 4: should be \"that\" instead of \"hat\"\n- Section 4.2: (twice) should be \"faithful\" instead of \"faithfull\"\n- Line 747: \"TODO cite pearl?.\"", "questions_for_authors": "1. Have the authors tried using linear or NN simulations with stronger relations, like mentioned in __Claims and evidence__ above?\n2. Likewise, do the authors have an argument against neural approaches specifically or for any other particular approaches, independent of the objective functions used?\n3. Have the authors tried comparing non-neural methods? Do they fare any better?\n4. In __Conclusion__ before Section 4, what does \"the number of equivalent graphs will reach 0\" mean?\n\nSatisfactory answers to the first 3 questions would improve my overall recommendation.", "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: The idea of this work is simple and is based on the premise that the strong assumption of faithfulness is responsible for the non-improvements in the neural causal discovery. The authors demonstrate that even state-of-the-art neural approaches struggle to recover ground-truth causal structures. To this end, a benchmark is proposed to evaluate several discovery algorithms. Additionally, a metric for measuring the degree of faithfulness is introduced to assess how faithfulness impacts the performance of these algorithms.

Overall, the paper received 3 reviews with the majority of the reviewers assessing the work positively. The critical reviewer had questions regarding the generalizability of the faithfulness assumption bottleneck along with how well the bottleneck holds when the data is scaled. The AC read the paper, and have certain questions that need to be clarified in the paper:

1. NN-Opt is a brute force method, so I have serious concerns about the efficiency of the method.

2. As reviewer 6UaB also points out, the experiments are only on synthetic data sets, but the whole motivation of the work is based on how this assumption is a problem in real-world scenarios.

3. I also agree with Reviewer JYG6, that 80k examples are not many. If the authors are focusing on synthetic examples, nothing prevents them from increasing the size of the data set. There are works such as Ribeiro-Dantas et al., Learning interpretable causal networks from very large datasets: application to 400,000 medical records of breast cancer patients, iScience 2024 and Lopez et al., Large-Scale Differentiable Causal Discovery of Factor Graphs, NeurIPS 2024

4. I also have a question regarding Fig 3 b) SDCD and Bayes DAF show a downward trend, so I think the claim that there is no improvement in the ESHD metric is a strong one. I believe the authors should conduct more evaluations on this.

Overall, I think this is a good paper, but there are several questions that are left unanswered. I recommend a weak acceptance.
Decision: Accept (poster)