Ordering-Based Causal Discovery for Linear and Nonlinear Relations

Due to the long training time of KCIT at 50 nodes, we only report its performance with one trial in Table 4. Other results are reported with 5 trials.

Your insightful advice is greatly valued, as it can contribute to the progress of our work. We hope that the answers provided below have resolved your inquiries.

Q4.1: non-decreasing variance too strong.

A4.1: Before answering this question about assumptions, we want to highlight some facts of ANM. For an ANM $y=f(x)+\epsilon$, we have to make some assumptions on $f$ or $\epsilon$ due to the problem of backward model (see Prop.23 in ref. [9]). This paper does not make any additional assumptions on $f$ (linear or nonlinear), therefore, some assumptions on $\epsilon$ are inevitable. To the best of our knowledge, our assumptions is the weakest assumption that works well under both linear and nonlinear ANM.

Then, it is necessary to emphasise that CaPS works under (i) or (ii) in assumption 1. So, our assumption is weaker than non-decreasing variance. CaPS is able to work well using the condition (ii) if non-decreasing variance does not hold. For example, considering a variance-unsortable scenario with $\sigma^2\sim U(1,10)$ and causal effect greater than 0.9, CaPS can also work well because the the sum of parent score is greater than the given lower bound in condition (ii). In other words, non-decreasing variance is just one of the scenarios in which CaPS works well, and CaPS can also handle many variance-unsortable scenarios.

Q4.2: The primary difference between the SCORE and CaPS is assumption 1.

A4.2: We understand your concerns, but SCORE and CaPS is totally different for the following reasons:

(1) More generalized scenarios. CaPS aims to handle both linear and nonlinear and most possibly mixed relations while SCORE only handles nonlinear relations. CaPS is the first ordering-based method to deal with this scenario.

(2) Different theoretical ideas. As mentioned in A4.1, SCORE is derived through the properties of nonlinear $f$ while CaPS derives Theorem 1 by the properties of $\epsilon$, which is a totally different ideas in theoretical perspective (see details in App. A.2).

(3) New concept for identifiability and post-processing. This paper proposes a new concept of "parent score", which gives a new lower bound for identifiability with causal effect (see Corollary 1). This concept can be used to accelerate the pruning process (see Fig. 8) and correct inaccurate predictions in the pruning step (see Fig. 4 and 7).

Q4.3: independent residuals-based method work in this setting? what are the advantages of CaPS? (e.g. handing large-scale structures)

A4.3: Thanks for the kindly reminder of comparision of the conditional independence (CI) test-based methods. About the independent residuals-based method, we're not sure exactly which method you mean, but we guess it's ReCIT[1, 2]. Since the source code of ReCIT is not available for comparision, we adopt the closest CI-based baseline KCIT[3] compared with ReCIT.

Yes, as you mentioned, although these two CI test-based methods not explicitly need on linear and non-linear assumptions, they have high computional complexity. They need to search the solution on a fully connect DAG while ordering-based method only need a smaller search space with the topological ordering. This make CI test-based methods ususally has exponential complexity and hard to implement in a large-scale structures. In Table 5, we show the performance of CaPS vs KCIT and there are two conclusions we can learn from these experimental results.

(1) Although KCIT does not significantly degrade in linear and nonlinear performance, it consistently underperforms CaPS in all scenarios with different linear rate.

(2) For capablity of handling large-scale structures, CaPS is consistently better than KCIT with significantly outperforming metrics and faster training speeds (e.g. 18 seconds vs 2 hours in Table 5). In addition, even compared to the ordering-based approach, CaPS are able to better handle the large-scale structures (see Fig.3, App. C.5 and Fig. 8).

*Since KCIT and ReCIT are compatible with CaPS, KCIT and ReCIT can use CaPS to largely reduce their search space.

This comparison further shows the advantages of CaPS and we will add these discussion of ReCIT,KCIT and CaPS to our related work and experiments in the latest version.

[1] Zhang H et al. (2018) Measuring conditional independence by independent residuals: theoretical results and application in causal discovery.

[2] Zhang H et al. (2019) Measuring conditional independence by independent residuals for causal discovery.

[3] Zhang K et al. (2011) Kernel-based Conditional Independence Test and Application in Causal Discovery.

We appreciate your constructive feedback, as it can help us improve our work. We trust that the following answers have clarified your questions.

Q3.1: Results are not great on real-world datasets.

A3.1: Yes, CaPS achieves the best performance on Sachs dataset but only the second best in Syntren. We have analyzed the source of the discrepancy in Appendix C.1, the pattern of Syntren is very special containing many star networks with short topological dependency path. This pattern is not friendly to ordering-based methods (see details in Fig. 5 and lines 524-528). Despite this unfavourable dataset, CaPS achieves the second in all baseline and the best performance in all ordering-based methods. We believe, in a sense, this fact reinforces the effectiveness of CaPS.

Q3.2: Few results of topological divergence

A3.2: We already shows the order divergence of SynER1 and SynER4 in App. C.6. To further address your concerns, we show more results of this metric in different datasets in Table 4. The conclusion is CaPS consistently achieves the best order divergence under the datasets with different DAG tpye, sparsity, scale and sample sizes. We will update it to the latest version of our manuscript.

Table 4. More results of order divergence.

Thank you for your valuable suggestions, as they can aid in enhancing our work. We hope that the responses below have addressed your concerns.

Q2.1: non-decreasing variance of noise

A2.1: The first thing we need to emphasise is that CaPS works under (i) or (ii) in assumption 1. So, our assumption is weaker than non-decreasing variance. CaPS is able to work well using the condition (ii) if non-decreasing variance does not hold. For example, considering a variance-unsortable scenario with $\sigma^2\sim U(1,10)$ and causal effect greater than 0.9, CaPS can also work well because the the sum of parent score is greater than the given lower bound in condition (ii). In other words, non-decreasing variance is just one of the scenarios in which CaPS works well, and CaPS can also handle many variance-unsortable scenarios.

Q2.2: Gaussian assumption & derivations seems difficult to generalize to more general noise

A2.2: Before answering the this question about assumptions, we want to highlight some facts of ANM. Without interventional data, all ANM-based models ($y=f(x)+\epsilon$) have to make some assumptions on $f$ or $\epsilon$ due to the problem of backward model (see Prop.23 in ref. [9]). Some paper make purely linear or nonlinear assumption on $f$, e.g., SCORE and LISTEN. This paper does not make any additional assumptions on $f$ (linear or nonlinear), therefore, some assumptions on $\epsilon$ are inevitable. To the best of our knowledge, our assumptions is the weakest assumption that works well under both linear and nonlinear ANM.

Theoretically, the Gaussian assumption is necessary, which are used in Eq. 10 to prove Theorem 1. However, experimentally, the results in App. C.7 shows that CaPS performs consistently well under non-Gaussian noise (Gumbel and Laplace), which shows the potential of CaPS generalization to other noises. We are still working to find a more elegant solution to relax the $\epsilon$ to non-Gaussian noise. However, we believe that CaPS, as the first ordering-based method capable of handling both linear and nonlinear, contributes sufficiently to the field.

Q2.3: Both conditions in Theorem 1 seem impossible to verify.

A2.3: We understand your concerns and this sentiment is right, but most of conditions is unverifiable without the ground truth SEM. In synthetic data, we can easily verify our conditions since we have the real parameters of $f$ and $\epsilon$. In the real-world application, as shown in Fig. 1, we can't even verify $f$ is linear and non-linear since we do not have the ground truth SEM.

Thus, we need a method with the conditions which more likely to be close to the real-world patterns while many conditions is usually unverifiable. CaPS is able to solve this problem better than existing works based on the following reason:

(1) CaPS can work well in both linear and nonlinear and most possibly mixed cases, which is widespread in real-world data.

(2) CaPS gives a new lower bound for identifiable causal effects in Assumption 1(ii), which can be use to discovery non-weak causal relations in real-world data.

(3) Experimentally, CaPS is an outperforming ordering-based method under different tpyes of synthetic datasets and real-world datasets. Especially, our experiment results show CaPS can effectively support non-Gaussian noise (Gumbel and Laplace) in addtion to theoretically proved Gaussian noise.

Q2.4: assume equal variances in the experiments?

A2.4: We consider the scenario both equal variances and unequal variances in our manuscript. The results of unequal variances are given in App. C.7. Following the most popular settings in previous works, for each variable $x_i$, the noise $\epsilon_i\sim N(0, \sigma_i^2)$, where $\sigma_i^2$ are independently sampled uniformly in $U(0.4, 0.8)$ . Under this random variances scenario, CaPS still achieved the best or competitive performance under unequal variances noise.

Q2.5: comparing with DAGMA and TOPO.

A2.5: Thank you for sharing these two strong continuous optimization baselines. With their wonderful open source code, we successfully implemented them in our experimental scenarios. Since this paper considers both linear, non-linear and mixed scenarios, for a fair comparison, we compare the performance of CaPS and their linear (-L) and nonlinear (-N) versions, respectively, in Table 3. All parameters and settings of these two baseline follow their original manuscript or source code.

Yes, as you mentioned, DAGMA and TOPO are stronger baselines than NOTEARS and GOLEM. And, we can learn two conclusions from Table 3:

(1) Compared with DAGMA and TOPO, CaPS can consistently achieves best performance under both synthetic and real-world data with different sparsity and linear rate.

(2) Similar to other baselines, DAGMA and TOPO are also suffering significant performance loss when linear/nonlinear assumptions mismatch.

This comparison is important but does not affect any conclusions of this paper. We will update it to the latest version of our manuscript in the related work and experiment.

Table 3. Addtional baselines

Even under purely linear/nonlinear, the experimental results differ from their original manuscripts because of the different settings of synthetic data generation. One different setting is that our nonlinear function is "gp", while they are "mlp". Another different setting is DAG weights, which we set to $[-1, -0.1]\cup[0.1, 1]$ while they are $[-2, -0.5]\cup[0.5, 2]$. In our setup, it would be more difficult to identify DAGs effectively due to the weaker strength of the causal effect.

Thank you for your valuable comments and recognition of our efforts, but there seems to be some misunderstanding regarding A2.2.

What we are trying to convey is that the assumption of CaPS is the weakest assumption that can handle linear, nonlinear and even mixed relations simultaneously. As you point out, LiNGAM can work under non-Gaussian noises. However, it can only handle purely linear causal relations. To further address your concerns, we provide the comparison of CaPS and LiNGAM under SynER1 with Gumbel noise in Table 6. We can learn two conclusions from Table 6:

(1) LiNGAM suffers a significant decrease with increasing nonlinear ratio because it can only work on linear & non-Gaussian.

(2) The empirical results of CaPS is consistently better than LiNGAM under non-Gaussian settings, which show CaPS can effectively support non-Gaussian noise in addtion to theoretically proved Gaussian noise.

Table 6. CaPS vs LiNGAM under SynER1 with Gumbel noise.

Preliminaries

Thank you very much for your valuable comments. Before answering the three question about assumptions, we want to highlight some facts of ANM. Without interventional data, all ANM-based models ($y=f(x)+\epsilon$) have to make some assumptions on $f$ or $\epsilon$ due to the problem of backward model (see Prop.23 in ref. [9]). Some paper make purely linear or nonlinear assumption on $f$, e.g., SCORE and LISTEN. This paper does not make any additional assumptions on $f$ (linear or nonlinear), therefore, some assumptions on $\epsilon$ are inevitable. To the best of our knowledge, our assumptions is the weakest assumption that works well under both linear and nonlinear ANM.

Q1.1: VAR-sortability assumption are too strong.

A1.1: We need to emphasise that CaPS works under (i) or (ii) in assumption 1. So, our assumption is weaker than VAR-sortability. CaPS also can work well using the condition (ii) if VAR-sortability does not hold. For example, considering a VAR-unsortable scenario with $\sigma^2\sim U(1,10)$ and causal effect greater than 0.9, CaPS can also work well because the the sum of parent score is greater than the given lower bound in (ii). Experimentally, the results in the App. C.7 also support the conclusion that CaPS works well even without VAR-sortability.

Q1.2: Is zero-mean Gaussian utilized? testable?

A1.2: This zero-mean Gaussian is a de facto standard in all ANM-based method (see ref. [9,11,13,...]), as this setting does not lose any generalization. Any ANMs with non-zero-mean Gaussian $\epsilon_n \sim N(\mu,\sigma)$ is equivalent to a ANM with zero-mean Gaussian $\epsilon_z \sim N(0,\sigma)$, because f(x)+\epsilon_n$$=f(x)+\mu+\epsilon_z$$=F(x)+\epsilon_z. The non-zero-mean Gaussian can be considered as $f$ with different bias in ANM. As we already provided the performance under zero-mean Gaussian noise in Fig. 2, we additionally test the performance under non-zero-mean Gaussian in Table 1 and 2 to further address your concerns. The conclusion is that $\mu$ does not significantly affect the relative performance of all compared baseline and CaPS still achieves the best performance.

Q1.3: non-Gaussian proof? like Sec4.3 in the SCORE.

A1.3: As mentioned in the preliminaries of this rebuttal, SCORE can extend to non-Gaussian because they make strong assumption on $f$ (purely nonlinear) and highly rely on the nonlinear properties for the proof. This paper handles a scenario with more generalised relations without any addtional linear or nonlinear assumption, so we need to use some properties of $\epsilon$. Theoretically, the Gaussian assumption is necessary, which are used in Eq. 10 to prove Theorem 1. However, experimentally, App. C.7 shows that CaPS performs consistently well under non-Gaussian noise (Gumbel and Laplace), which shows the potential of CaPS generalization to non-Gaussian noises.

Thanks for your inspiring suggestion. We are still working to find a more elegant solution to relax the $\epsilon$ to non-Gaussian noise. However, we believe that CaPS, as the first ordering-based method capable of handling both linear and nonlinear, contributes sufficiently to the field.

Q1.4: motivation for parent score.

A1.4: Before we recall the motivation of parent score, we want to remind that parent score can be directly decoupled from the score’s Jacobian using Algorithm 1, which does not introduce additional computational complexity. The average treatment effect framework you mentioned is only used for theoretical interpretation. Here is the advantages of introducing parent score.

(1) More clear theoretical interpretation. Why condition (ii) is a lower bound of identifiable causal effects? What's the physical meaning of Theorem 1? It is hard to to explain without parent score and the given average treatment effect framework. However, we can clearly answer this questions with parent score in the Corollary 1 (see details in lines 189-201 and App. A.5), i.e., the left-hand side of condition (ii) is sum of causal effect and Theorem 1 is finding a leaf node with weakest causal effect.

(2) Better performance and speed. Parent score can help to accelerate the pruning process and correct inaccurate predictions in the pruning step. With this post-processing, the performance can be further improve in real-world dataset (12.6% of Sachs and 3.6% for Syntren in F1). More importantly, it can largely accelerate the pruning process especially when nodes are increasing (78.8% for 50 nodes and 49.41 for 20 nodes; see Fig.8). This make CaPS have better capablity of handling large-scale structures.

Therefore, parent score is not a over-complicated design.

Q1.5: lack of novelty. CaPS combine ideas from SCORE and LISTEN?

A1.5: We understand your concerns, but CaPS is totally different from SCORE and LISTEN the following reasons:

(1) More generalized scenarios. CaPS aims to handle both linear and nonlinear and most possibly mixed relations while SCORE only handles nonlinear relations and LISTEN only handles linear relations. CaPS is the first ordering-based method to deal with this scenario.

(2) Different theoretical ideas. As mentioned in the preliminaries of the rebuttal, SCORE and LISTEN is derived through the properties of nonlinear $f$ while CaPS derives Theorem 1 by the properties of $\epsilon$, which is a totally different ideas in theoretical perspective (see details in App. A.2). Therefore, although the theorem only different on "expectation" and "variance", the derivations is totally different and can not be straightforwardly extended whether from SCORE or LISTEN.

(3) New concept for identifiability and post-processing. This paper proposes a new concept of "parent score", which gives a new lower bound for identifiability with causal effect (see Corollary 1). This concept can be used to accelerate the pruning process (see Fig. 8) and correct inaccurate predictions in the pruning step (see Fig. 4 and 7).

Table 1. SynER1 with $\epsilon \sim N(1,\sigma^2)$

Table 2. SynER1 with $\epsilon \sim N(10,\sigma^2)$

Thank the authors for the detailed response.

For the assumptions, technically yes, they are slightly weaker than VAR-sortability with another condition allowed. However, the another condition, just similar to VAR-sortability, is mainly human-crafted for the framework. It lacks any natural theoretical interpretability or practical testability.

For zero-mean Gaussian, thanks for the additional experiments, but "$\mu$ does not significantly affect the relative performance" -- could the authors please confirm that whether zero-mean is needed for the asymptotic identifiability guarantee?

For Gaussian noise assumption, "it is used in Eq. 10 to prove Theorem 1" -- however, I couldn't see from the proof on where specifically a Gaussian distribution is needed. Instead, I can only see the use on general forms on means and variances, together with the assumptions. But in any way, if only Gaussian noise is allowed, it would be a further shortcoming for this work: the identifiability will be unclear, and the the method will be less practical.

For motivation of parental score, thanks for reminding me that it does not introduce additional computational complexity. Though not theoretical interesting, it indeed offers empirical gain. I have adjusted my score to reflect this point.