Ordering-Based Causal Discovery for Linear and Nonlinear Relations
Authors: Zhuopeng Xu
Yujie Li
Cheng Liu
Ning Gui
Venue: NeurIPS 2024 poster (2024)
Keywords: causal discovery; directed acyclic graph; additive noise model
Primary area: causal_inference
TL;DR: This paper propose a causal discovery method that works well in both linear and nonlinear.

Abstract: Identifying causal relations from purely observational data typically requires additional assumptions on relations and/or noise. Most current methods restrict their analysis to datasets that are assumed to have pure linear or nonlinear relations, which is often not reflective of real-world datasets that contain a combination of both. This paper presents CaPS, an ordering-based causal discovery algorithm that effectively handles linear and nonlinear relations. CaPS introduces a novel identification criterion for topological ordering and incorporates the concept of "parent score" during the post-processing optimization stage. These scores quantify the strength of the average causal effect, helping to accelerate the pruning process and correct inaccurate predictions in the pruning step. Experimental results demonstrate that our proposed solutions outperform state-of-the-art baselines on synthetic data with varying ratios of linear and nonlinear relations. The results obtained from real-world data also support the competitiveness of CaPS. Code and datasets are available at https://github.com/E2real/CaPS.

Ordering-Based Causal Discovery for Linear and Nonlinear Relations
Yujie Li Cheng Liu Ning Gui School of Computer Science and Engineering Central South University (xuzhuopeng, yujieli)@csu.edu edu. (liuchengstudy, ninggui)Ogmail.com
Zhuopeng Xu
Abstract
Identifying causal relations from purely observational data typically requires addi- tional assumptions on relations and/or noise. Most current methods restrict their analysis to datasets that are assumed to have pure linear or nonlinear relations, which is often not reflective of real-world datasets that contain combination of causal discovery algorithm
both. This paper presents CaPS, an ordering- that effectively handles linear and nonlinear relations. CaPS introduces novel identification criterion for topological ordering and incorporates the concept of "parent score" during the post-pra post-processing optimization stage. These scores quantify the strength of the average causal effect, helping to accelerate the pruning process and correct inaccurate predictions in the pruning step. Experimental results demon- strate that our proposed solutions outperform state-of-the-ar baselines on synthetic data with varying ratios of linear and nonlinear relations. The results obtained from real-world data also support the competitiveness of CaPS. Code and datasets are available httphttt://// //gt thub. com E2rsea/Caaa
Introduction
Causal discovery uncovers latent causal relationships within data by modeling Directed Acyclic Graph (DAG) connecting various variables. This field is of significant importance domains such as biology [.. epidemiology [2], and finance 3 Due to the considerable expense associated with conducting interventional experiments, the recent emphasis on causal discovery has gradually shifted to discovery solely based on observational data.
from discovery with interventional data 4 5
In general, the problem of causal discovery from observational data faces the identifiability issue. Different generative models with different causal relations might produce the same data distribution. Many recent works try have uniquely identified DAG by placing different types of assumptions on the noise and/or relations, c.g., Shimizu et al. (7) prove that linear causal relations with non- non-Gaussian additive noise can be identifiable; Peters and Bühlmann [8] prove that Gaussian linear structural equation models (SEMs) with equal variances are identifiable. For nonlinear causal relations, Peters al. relax the assumption of noise and proves the identifiability of DAG. From the discussion mentioned above, existing approaches normally limit their discussions to distributions with either pure linear or pure nonlinear relations.
However, real-world data often contain both types of causal relations and run against their basic assumptions. These approaches work well when the observational data match their prespecified (non- llnnarr or nonlinear relations while suffering significant performance loss when their assumptions mismatch. Fig. [ [illlsttatts the performance of three solutions: GOLEM [IO] for linear relations, SCORE [II] for nonlinear relations, and our proposed CaPS, on synthetic data with varying propor- tions of linear relations. The performance of SCORE decreases the linear ratio increases, while
Cooresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

DAG
X3
Leurning
Nedil
CULLMM 90066
X1
X2
X3
X4
Linear model
Nonlitear model
0.5
04
(Nonlinear)
Lincur proportion
(Linear)
Performance of different solutions under datasets with different linear proportions. Since don't 't know whether the real data is linear nonlinear, it is difficult to choose effective model. Thus, we need method that works well in both linear and nonlinear and most possibly mixed cases.
Figure I:
GOLEM performs poorly when the linear relation ratio is low. This indicates that approaches with strong restrictions on the types relations are not suitable for real-world applications. Consequently, it is necessary to find unified causal learning framework to capture both types of relations.
Ordering-based methods [12] divide the casual discovery process into two subtasks: (i) topological ordering and (ii) post-processing. It has been shown to have the capability to reduce the complexity of DAG discovery while keeping the acyclicity constraint. In addition, ordering-baaee -eased methods guide the direction of causal relations, thus avoiding the fitting of potential inverse model. However, existing ordering-basee approaches still face the same problem of relying on the assumption of linear, e.g., LISTEN or nonlinear causal relations, c.g., SCORE.
This paper introduces unified approach, Causal Discovery with Parent Score (CaPS), that does not rely on linear or nonlinear assumptions, within the scope of ordering- based casual discovery.. To determine the topological ordering, we propose novel unified criterion for distinguishing leaf nodes by utilizing the expectation of the Hessian of the data log-likelihodd. Additionally, inspired by the average treatment effect (ATE) in estimating causal effects (14), the parent score, new metric, is proposed to represent the average causal effects of all samples. No matter whether the causal relations are linear or nonlinear, this metric can be used effectively guide parent selection in post-processing.
Contributions. I) novel ordering criterion is proposed for distinguishing leaf nodes, which enables learning of topological ordering for data with both types of relations; 2) A new criterion, parent score introduced to reflects the strength the average causal effect of a given parent. Utilizing this criterion, CaPS designs pre- pre-pruning and edge supplement operations speed up the pruning process and rectify inaccurate predictions in the pruning step. 3) Extensive experiments are conducted to compare eight state-of-the-art baselines synthetic and real-world data, showing competitive results. Furthermore, various analysis simulations demonstrate the effectiveness of our proposed designs.
2
Related Work
Causal discovery for SEMs. Gaining knowledge of DAGs from observational data often necessitates additional suppositions about the distributions and/or relations. This paper discusses SEM-based studies from either the linear or nonlincar point view.
To ensure the identifiability of linear causal relations, additional noise constraints must be made, for example, Gaussian noise with equal variance [8] or conditional variance [33. Earlier work by
LiNGAM ? demonstrated the identifiability of linear causal relations with non- Gon-Gaasii noise and proposed an ICA-based method identify this SEM. NOTEARS [15] proposed a novel continuous optimization approach based on the trace exponential function, which provides new idea of continuous optimization for causal discovery. GOLEM further 110 proposed a continuous likelihood- based method with soft sparsity and DAG constraints, which improved the performance of linear causal discovery. The optimization of these works largely dependent on the linear parameterization of the weighted adjacency matrix.

---

For nonlinear SEMs, e.g., the nonlinear additive noise model (ANM) [9] is known to be identifiable with arbitrary additive noise, except in some rare cases. To discover causal relations under nonlinear SEM, many previous works [[6] 17 18 19 20 proposed different DAG learning methods with continuous acyclicity constraint. These works generally require a training model with an augmented Lagrangian approach which results in considerable computation cost.
Ordering-basee based causal discovery can partially avoid the aforementioned problems, as the order space is much smaller than the DAG space. CAM [2]] is an early ordering- based approach that uses a greedy search estimate the topological ordering and significance tests to prune the DAG. LISTEN [13] proposed a new method for distinguishing leaf nodes of linear causal relations, based on the precision matrix [22]. However, these methods are based on the connection between the precision matrix and the weight matrix, which is not unified criterion for linear and nonlinear SEMs. SCORE [1] estimated the score (the Jacobian of logarithmic probability of data, V Vlogp(a)) p(x)) using the second-order Stein gradient estimator, and then determined the leaf nodes based on the score to find the topological ordering. DifFAN
23 was proposed to estimate the score via diffusion model.
Several recent works merge the two-stage process into one step by end-to-end differentiable optimiza- tions to address the issue of error propagation, e.g VI-DP-DAG 24 with variational inference and DAGuerreotype [25] over the polytope. DAGuerreotype provides two variants specifically designed for linear/nonlinear relations. However, none of the above works provides a uniform solution that can identify DAG in datasets with both linear and nonlinear relations.
3 Preliminaries
3.1 Structural Equation Model
The structural equation model for the causal discovery can be represented as for random variable ra) Rd sampling from the real joint probability distribution p(x), we want to
(I1, { .r,,..., ...,
find a faithful causal graph G to represent the causal relationships between variables of different dimensions. The SEM is defined with equation (T]
(I) where x; E x, i 1,2, d. px,(2) denotes the parents of T;, fi denotes the causal function, and e; denotes the additive noise of ri. For each zi, the parents and the noise are independent of each other, pa.(x) IL e;, and there is no unobservable confounder. Each causal function fa can be linear and nonlinear, and the additive noise e; NO, of) is Gaussian. These the basic assumptions of ANM 19I. and we relax the linear and nonlinear conditions in our SEM.
I; (pa, +
3.2 Topological Ordering
Finding topological ordering is important subtask for sitering-bbsedd causal discovery, which can reduce the DAG search space.
Since the topological ordering of the causal graph G may not be unique, we define a set of order permutations II represent all valid topological orderings. For any order permutation π E II. a parent node must always be before a child node. i.c. T(i) < (()) if x is a descendant of x; on G. The corresponding initialized adjacency matrix A should have A.,;
Definition.
and A,,- = O.
Estimation. To identify the leaf nodes of DAG, SCORE suggests using the score s,(x), which is equal to the logarithmic gradient of the joint probability distribution p(x) with respect 2y. If Markov chain is used to represent p(x). then the score of each variable is equivalent to the logarithm gradient of the joint probability distribution.
8y(x) = Vz,
II
p(a; (pa; =V,, Σ log p(x;(pa;(x))
1=1
d
(((a )2
d
Σ 1=1
log(22o0 (2TT?))
(2)
az
2 1=1
Iy - f, (pa, (x))
Of.
(x)) Dt fo (z),
of
Ox,
of
$Ech(f)
3

---

where (i) uses the change of variables theorem with 2; f((pa;())) - and ch(j) denotes the children of 2;j in the causal graph G. According to Eq for each leaf node, it is easy to see that 0e,(2) is constant. Thus, given the nonlinear assumption of the causal function fi. SCORE dx, d
has shown that 2 is a leaf node iff the variance of [s,(2) is zero. The score 8 (z) and each element 8z,
on the diagonal of the score's Jacobian (s, can be estimated using the second-order Stein gradient
estimator [26] or the diffusion model Dey
4 Causal Discovery with Parent Score
This section first examines the limits of current baselines under con-preassumed relations. Then, the design of CaPS in both topological ordering and post-processing is introduced.
4.1 Leaf Nodes Discrimination
Previous attempts to order nodes according to a certain criterion were unsuccessful due to the lack of a unified standard to distinguish leaf nodes in datasets with mix relations. To make this point more evident, we provide examples of both linear and nonlinear cases. LISTEN [33] for linear causal relations uses the minimum value of the precision matrix's diagonal to distinguish leaf nodes. However, this approach fails because the connection between the precision matrix and the true causal graph no longer holds under nonlinear causal relations, which is detailed in Appendix A.
SCORE for nonlinear causal relations cannot differentiate leaf nodes linear causal relations. To illustrate this, consider simple linear causal case 2; ExrEpa W4,42% + c,, where f; is linear 8hs (pa,(x:) = Wxs a constant and 6 du. (x)) = Consequently, ANM. In this linear SEM, 86,
for any node, the value of each element on the diagonal of the score's Jacobian is always constant, i.e., (e,(x) dee
Wig EiEcht of making SCORE unable to differentiate leaf nodes. To address this issue, we propose a new discriminant criterion in Theorem 1 effective in both linear and nonlinear causal relations and give its sufficient conditions for identifiability Assumption
Assumption (Sufficient conditions for identifiability. The topological ordering of a causal graph is identifiable if one of the following sufficient conditions is satisfied.
(i) Non-decreasing variance of noises. For any two noises e; and Ej oj 2 ai if (()) x(])
1 Ui Dzy (ii) Non-weak causal effect. For any non-leaf nodes Zj Eieck() of
(p))))))))1 +
where min is the minimum variance for all noises. Assumption gives two conditions for identifiabil- ity which no longer depends on the linearity or nonlinearity of the causal function and relaxes previous identifiability conditions. Condition (i) is extension of the equal variance assumption 8 [3] Con- dition (ii) is a new sufficient condition, which first quantitatively gives a lower bound of identifiable causal effects. It enables CaPS to identify causal relations even in scenarios outside of non-decreasing variance. For example, considering a variance-unsortable scenario with o² ~ (0.1, 1) and causal effect greater than 3, CaPS can also work well because the the sum of parent score is greater than the given lower bound in condition (ii) The meaning of condition (ii) will be further discussed in section 4.2 Under conditions (i) or (ti). the topological ordering can be identified by Theorem 1.
Theorem 1. Let s(x) V log p(z) be the score and let diag(.) be the diagonal elements of the matrix. For any T.j in the causal graph G:
j = arg max (aiag ds(x) 1)) + D. is a leaf node dx
Proof. (Simplified version; details are in Appendix A.2
For arbitrary node sy in the causal graph G, we focus on the diagonal of the score's Jacobian.
(z)
1
Σ
1 Of dx, (pa, (x))) + o.
Σ
8 Oz7
(pa (pa,(x))
24 - ff
0r,
0
of
(3)
(Ech(G)
xEch(j)

---

Since de fl=A(pa((a) of be restated as:
4 of
NO, 7t) and pa;(2) IL in our SEM, the expectation of (z)
dxy can
(5, 1
Of: dx,
E
Σ
EI
(pa)
dzj
of
iECH()) of
Suppose that is a leaf node and is non-leaf node, we have E (0((2)
Then, E (x)(()) of
>
E Oee always holds under conditions (i) or (ii). Thus, the node in arg max da(a)) dx
Bex(m)]
1)) will
always the leaf node.
Theorem suggests that the expectation of the diagonal of the score's Jacobian can be used to identify leaf nodes. Thus, applying Theorem 1, the topological ordering is identifiable by iteratively eliminating the current leaf node (27). The detailed procedure included Algorithm where we use the second-order Stein gradient estimator to estimate the score's Jacobian da(m)
dx
4.2 Parent Score
Theorem I specifies how to identify the correct topological ordering of the graph G. However, it is not straightforward to determine the parents of each node. To identify the true causal graph G, we need information beyond permutation to guide the selection of parents. Thus, need metric that can qualitatively express the causual effects from a parent node to one of its children. Here, a new metric, "Parent Score" is proposed to approximate the average causal effect.
Definition of parent score. We define Eq express the parent score Pi, which approximates the strength of the average causal effect of all samples from xy to T.-
[ aL. (pa;( Ty E pa(())
Paj
Uzy
(5)
0, $ (x,
where P., if x, is not parent of r; and P.,j 0 zj is parent of z₁-
To illustrate the meaning of this definition, we propose a new metric of the Squared Average Treatment Effect (SATE) extended from Average Treatment Effect (ATE, (T=()==)) (T=)))). In the task of estimating causal effects [14] ATE is often used measure the average effect of a treatment intervention on an outcome variable. Since we focus only on the strength of the effect rather than on the positive negative effect, SATE is defined as follows:
SATE = [(( (T)))
(T) 00
x
where T, 1 and T indicate whether æ. are treated not. With small additive treatment, show that SATE from y. to I; can be approximated by [F[( 0f Pi. is the causal effect of the parent scaled by its variance of noise. The detailed derivation is shown in Appendix A.3
Bay (x))(.)))?}. Thus, the parent score
Computing parent score. Parent score cannot be obtained directly from the summation average causal effects on childrens in Eq thus we propose iterative decoupling process and define
J = [ (8)(2)
J. E (x)( l.....
Osa(z)) 1}
Ozi
Org
Oxx
to denote the expectation of the diagonal of the score's 's Jacobian. By removing the node F;, new vector J-, defined as follows:
2s (2)(2=1)) (82(x-1)
(1) Dx:
@sa(x-e) Ox.
J-, (E dm
..... E
E
(8)
Oxz
where x- represents the remaining data after removing the feature of i-th dimension. For the i-th element of J_1, we fill the i-th element of J. Then, each row vector of the matrix of parent score Pe = pdxd is equivalent
P,, = J_,-3
(9)
The complete can be obtained by iteratively computing parent score of each row. The specific derivation of this procedure is given in Appendix A.4 The Algorithm | describes the process of
5

---

Algorithm Ordering and Computing parent score
Input: data matirx X E R
Output: permutation x. parent score P
initialize π + removed set r 6 [], nodes
[1,2, .., d.. P+
2: estimate 0x(X) and then obtain J using Eq 7
Be 3: for = 1, 1,......d do
xx(X-.) and 0s(X-r) 4: estimate Bg
5: obtain J-i using Eggaand 8x then compute parent score Pi,, f- J_; J using Eq
6: distinguish current leaf node t nodes(arg max diag [ 0s(X
[]]] using Theorem.
dx
7: update +- [1, m]
{4}, nodest nodes {1}
8: end for
9: return N. P
finding the topological order and computing the parent score, where X-; denotes the data matrix with the i-th feature removed. Similarly, X_, denotes the data matrix with a set of removed features.
Association with leaf nodes discrimination. We can revisit the criterion to distinguish leaf nodes with parent score. According to the definition of parent score, given the node Zz. Σd Pi. can be considered as the total causal effect to its children. The sufficient condition (ii) for identifiability can be restated E Pa.j Caie oj when zj is not leaf. It means that the causal relations can be identified if the causal effect stronger than the given lower bound, which gives quantitative interpretation for an intuitive conclusion. Under this sufficient condition, the meaning of Theorem can be further explained in the following corollary.
Corollary j arg max (E (a(2) = Øz 's sum of parent score Ei Ps,g is minimal xj is a leaf node
The detailed proof is given in the Appendix A.5
Corollary 1 shows that Theorem is actually finding the minimal sum of the parent score. Then, the node with the minimal total causal effect is a leaf node. This corollary implies the association between parent score and Theorem 1. Thus, the parent score can be considered as a unified metric during topological ordering and post- post-processing.
4.3 Pre-pruning and Edge Supplement
Previous research has demonstrated that redundant edges can be successfully eliminated through CAM pruning, which applies significance testing of covariates based generalized additive models. This technique is widely used in many strong baselines [11] 23 28 However, CAM pruning is time-consuming and only utilizes the topological ordering information. The proposed metric, parent score, can further provide more information on causal effects. Thus, CaPS introduces the pre-pruning and edge supplement operations before/after CAM pruning process accelerate pruning by removing edges with low parent score and restore removed edges with strong parent score.
Pre-pruning. Before CAM pruning, use low-confidence parents pre-prune the initial graph, which can remove the low-confidence edges and reduce the searching space for CAM pruning. For each node, Specifically, for any F,; 2 E x, we mask the adjacency matrix A,,5 = 0 if Pr,j < A À is hyperparameter that represents the rigor in prepruning. This design can greatly speed up the pruning process, especially when the number of nodes is large (see Appendix CC55)
the maximum value of their parents to determine the threshold for pre-pruning.
max(P..) where
Edge supplement. After CAM pruning, we use high-confidence parents to supplement the edge, which can remedy errors in topological ordering and incorrect deletion in CAM pruning. With CAM pruning, the existing edges are likely to be the correct edges in real causal graph. Thus, the parent score current edges used automatically determine the threshold for edge supplement. For any Z4, J
we supplement the edge A,, when the following conditions are satisfied. First, Pig > X avg(PT @ A), where @ denotes the Hadamard product, and avg(-) returns the average value of matrix. Here, we use the same rigor for pre-pruning and edge supplement. Second, A is acyclic after supplementing the current edge. Note that edges added later may potentially violate

---

acyclicity, so we use greedy strategy to prioritize adding the edge with a higher parent score. The pseudocode of post-processing are released in Appendix B
4.4 Computational Complexity
For Algorithm[] [ the computational complexity is mainly related to the estimation of score's s Jacobian d times, which is O(d n²)). with for the number of samples and d for the feature dimension. For post-processing. the computational complexity is O(d + d f((.m)) + (d + e e+ s)), which can be considered as two steps. For the pruning step. the computational complexity of the original CAM pruning is Odd p(m,d),, where ((n.d) is the complexity function of training generalized additive model. With pre-pruning, the computational complexity of pruning can be reduced to Oid + d p)), where m < d is the maximum number of parents for each node. For the edge supplement step, the computational complexity is O(s (d+ e + s)) due to acyclic testing, where denotes the number candidate edges and e < d:(d-1) denotes the number of edges remaining after pruning DAG. Since we only want supplement the edges with high confidence, 8 tends be a small value in the implementation. Despite this cubic complexity of n, the actual-time growth is close to linear since many CaPS operations are GPU-friendll, which is detailed in Appendix C.3
5 Experiments
5.1 Baselines and Settings
Baselines. This paper benchmarks CaPS against eight strong state-of-the-art baselines designed for:
Linear: NOTEARS [15] and GOLEM 10 two strong linear methods with continuous optimization.
Nonlinear: GraNDAG 28 formulates neural network paths and connectivity matrix, and substitutes them into the acyclicity penalty; Five ordering- based methods (CAM, VI-DP-DAG, SCORE, DiffAN, and DAGuerreotype) are chosen for comparison. DAGuerreotype has two versions: linear one (e and a nonlinear one (DAGuerreotype-N), Both variants are evaluated in the synthetic data experiments to ensure a fair comparison.
Metrics. Three metrics in causal discovery are adopted for evaluation: the structural Hamming distance (SHD), the structural intervention distance (SID) [29], and the score. SHD evaluates the number of edges that must be altered to make the estimated causal graph match the true causal graph. SID assesses the number of interventional distributions in the true causal graph that are disrupted in the estimated causal graph. Lower values for SHD and SID are desirable. SHD favors sparser estimated causal graphs, whereas SID favors denser estimated causal graphs. Therefore, doing well in only one of these two metrics does not necessarily mean effectiveness. FI score measures the balance between precision and recall, with higher values indicating better performance.
Settings. We used the settings from the respective papers for all the baselines. For some methods that have multiple versions, such as GOLEM and DAGuerreotype, we reported the results of the version that gave the best performance on the corresponding dataset. The only hyperparameter of CaPS was rigor X, which we set to X 50 for all datasets to avoid any dataset-speeific tuning.
Synthetic data are created using the Erdös Kénisi (ER) 30 or Scale (SF) models 31 with different linear and nonlinear proportion. We set the number of nodes d = 10 and the number of samples n 2000 by default, while d = 20, 50 and n = 1000, 5000 are also given. Real dataset contains protein expression dataset Sachs (T] and pseudoreal transport network dataset Syntern 33 Details and more insights of the synthetic and the real data can be found in Appendix C.T
Datasets.
5.2 Synthetic Data
Fig shows the experiment results of eight baselines. We can observe that CaPS performs better for both sparser (SynERI) and denser (SynER4) graphs in almost all ranges, especially when the linear proportions are greater than 0.25. We also note that GOLEM's performance decreases with increasing nonlinear proportion, and SCORE's performance decreases with increasing linear proportion, which could be due to their assumptions not being met. In contrast, CaPS performs consistently well in almost all ratios. Experiments with the SynSF1 and SynSF4 datasets show similar results, and further information can be found in Appendix
7

---

GM
C0.24
4.30
0.25
6.56
0.5
100
0.08
0.25
0.50
0.75
1.80
6:30
025
8.5
6.5
L00
(a) SynERI (a sparser graph)
CPS
HOTTLRS
0/10
1Pear D7220r5on
LiWerr pioportion
Urear or3criin
(b) SynER4 denser graph)
Figure 2: Results of SynERI and SynER4 with different linear proportions, where linear proportion equal to 0.0 means all relations are nonlinear and 1.0 means all relations are linear.
5.3 Real Data
The results the real data are presented in Table CaPS achieves the highest SHD and Fl scores on Sachs, with SID coming second to VI-DP-DAG. VI-DP-DAG had the best SID but the worst SHD, as it discovers a large number of false edges. On Syntren, GraNDAG the top performer since the pattern of this dataset is not friendly to ordering-based methods (see Appendix C.I). However, CaPS achieves the best performance compared to other ordering- -baeed methods.
To investigate the impact of each component of CaPS, we replace Theorem 1 with random topologi- cal ordering (w/o Theorem I) or off the pre-pruning and edge supplement with parent score (w/o Parent Score). The results show that Theorem 1 makes a major contribution to CaPS, and the parent score can further improve it. Actually, the performance of CaPS can further improved by adjusting its hyperparameter X. The sensitivity of different À is further analyzed in Appendix
Table 1:
Results of real-world datasets, including three methods based on acyclicity constraint and five ordering- based methods. More baselines are given in Appendix C.4
Datasel
Sachs
Syntren
Metries
SHD4
SID/
SHD
SID
NOTEARS
12.0=0.00
46.020.00
0.387+0.000
33.9+4.57
192.8454.73
0.16410.085
GOLEM
17.0=0.00
44.0=0.00
0.42110.000
43.7410.72
177.4156.55
0,16340.066
GraNDAG
13.2=0.75
$4.0=1.10
0,37320.064
26.5t66.45
155.3458.1
0,344:0.104
CAM
12.0=0.00
55.0+0.00
0.444+0.000
38.066.50
178, 6+644.56
0.223+0.000 099
VI-DP-DAG
42.6=1.36
40.025.66
0.340:0.00 037
182. 624.2942
144.3+335.0
0.069 039
SCORE
12.0=0.00
45.020.00
0.4444000000
37.51-4.20
197.1163.71
0.183460.99
DiTAN
12.2=0.98
46.246.18
0.434=0.075
44.198
188. 188.7455516
0.191#0.095
DAGuereatype
17.9=0.54
51.4=0.49
0. 0.118+0.034
87.949.60
157.7448..99 90
0.12540.000 047
42.0+0.00
37.245.04
0.230&0.072
w/o Thenrem
17.0=3.50
54.0=3.40
0,257+0.061
51.6+88.8
180.0466 80
0.218+0 090
Parent Score
12.0=0.00
45.0=0.00
0.444z0.000
34.8+3.37
188.0+57.55
0.222
5.4 Analysis Experiments
Larger-scale datasets & actual-time cost. Despite cubic complexity in samples size n, the bottleneck of actual-time growth often lies in the number of nodes d in causal graph since many n-related operations are GPU-friendly. In Fig. 3 we illustrate the performance with actual-time cost for all baselines in larger-scale SynER1 (d 20 and 50) with 0.5 linear proportion. CaPS consistently achieves best performance in larger-scale causal graph while its time cost is competitive. The full

---

experimental results with actual training time of larger-scale causal graph (d = 20 and d = 50) and different samples size (n 1000 and n 5000) can be found in Appendix C.5
SysERI (d 29)
SyaER1 (0-50)
10
*
+
00-
Triting (woodds
Figure 3: Fl score and training time of SynER1 with larger-scale causal graph.
Order divergence. Reisach et.al. [33] cautioned that some synthetic datasets may be so simple that sorting with minimal variance can be successful. To demonstrate the efficacy of CaPS, a new metric called "order divergence" [ was introduced for evaluation, along with a new baseline sortnregress which orders nodes by increasing marginal variance. The results demonstrates that CaPS has a much better order divergence than sorturegress, indicating that variance is not a reliable indicator of the topological ordering in our synthetic datasets. CaPS consistently has the best or competitive order divergence in different datesets. Details can be found in Appendix C.6
Beyond our assumptions. We also explore the performance of CaPS under other settings of noise. The results show that CaPS can be effective in situations that go beyond our assumed conditions, which suggests that our approach has the potential to be applied in various other scenarios, and it is possible to consider loosening the assumptions in the future. Details can be found in Appendix C.7
Case visualization. Fig. shows the another advantage of CaPS. Compared to the second best baseline, CaPS performs better under all metrics while it provides more information causal effects. The parent score captures most of the ground around-truth edges and the estimated weights are similar to the actual values, indicating that the parent score accurately reflects the strength of causal effect
Rabe Prodecsis
SHD
SHD
SID
Fl 0.533
0.87
Time weighted DAG
Previous werk (only DAG)
CuPS (DAG & pancai
Figure 4: Visualization on SynER1 dataset. Darker colors indicate stronger causal effects.
6 Conclusion
This paper introduces CaPS that is capable of handling datasets with lincar and nonlinear relations, which is common occurrence in real-world applications. We propose a novel identification criterion for topological ordering for both types of relation, as well as a new metric, "parent score", to measure the strength of the average causal effect and used for edge removal and supplementation. Our solutions have been tested on synthetic data with varying linear and nonlinear relationship ratios and have been found to be more effective than existing order- based work and state-of-the-ar baselines.
There remain two interesting directions to be explored in future work. (1) Since the experimental results have been encouraging in some cases beyond our assumption, we are striving to broaden the identifiability conditions to more relaxed conditions. have more application scenarios. It is possible to apply as a alug-and-plas information of causality.
(2) The new metric, "parent score", is likely to

---

References
[1] Karen Sachs, Omar Perez, Dana Pe'er, Douglas Lauffenburger, and Garry P Nolan. Causal piotein-signalnng networks derived from multiparameter single-cell data. Science, 308(5721):523-555 529, 2005.
[2] James M Robins, Miguel Angel Hernan, and Babette Brumback. Marginal structural models and causal inference epidemiology. Epidemiology, pages 550-560, 2000.
[3] Andrew D Sanford and Imad Moosa. bayesian network structure for operational risk modelling in structured finance operations. Journal of the Operational Research Society, 63:431 444, 2012.
[4] Nan Rosemary Ke, Olexa Bilaniuk, Anirudh Goyal, Stefan Bauer, Hugo Larochelle, Bernhard Schölkopf, Michael C Mozer, Chris Pal, and Yoshua Bengio. Learning neural causal models from unknown interventions. arXiv preprini arXiv: 2019.
[5] Nan Rosemary Ke, Jane Wang, Jovana Mitrovic, Martin Szummer, Danilo J Rezende, et al. Amortized learning of neural causal representations. In ICLR Causal Learning for Decision Making Workshop, 2020.
[6] Mengyue Yang, Furui Liu, Zhitang Chen, Xinwei Shen, Jianye Hao, and Jun Wang. Causalvae: Disentangled representation learning via neural structural causal models. Proceedings of the IEEE/CVF conference computer vision and pailern recognition, pages 9593-9602, 2021.
[7] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
[8] Jonas Peters and Peter Bühlmann. Identifiability of gaussian structural equation models with equal error variances. Biometrika, 101(1):219-22) 2289922222222222 2014.
[9] Jonas Peters, Joris M Mooij. Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. 2014.
[10] Ignavier Ng, AmirEmad Ghassami, and Kun Zhang. On the role of sparsity and dag constraints for learning linear dags. Advances in Neural Information Processing Systems, 33:17943-17954 2020.
[11] Paul Rolland, Volkan Cevher, Matthäus Kleindessner, Chris Russell, Dominik Janzing, Bernhard Schölkopf, and Francesco Locatello. Score matching enables causal discovery of nonlinear additive noise models. In International Conference on Machine Learning, pages 18741-18753. PMIR, 2022.
[12] Mare Teyssier and Daphne Koller. Ordering- search: A simple and effective algorithm for learning bayesian networks. arXiv preprint 120. 2012.
[13] Asish Ghoshal and Jean Honorio. Learning linear structural equation models in polynomial time and sample complexity. In International Conference on Artificial Intelligence and Statistics, pages 1466- 1475. PMLR, 2018
[14] Ruocheng Guo, Lu Cheng, Jundong Li, Richard Hahn, and Huan Liu. A survey of learning causality with data: Problems and methods. ACM Computing Surveys (CSUR), 53(4):1-37, 2020.
[15] Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with no tears: Continuous optimization for structure learning. Advances in neural information processing systems, 31, 2018.
[16] Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gnn: Dag structure learning with graph neural networks. International Conference on Machine Learning, pages 7 7154-7163. PMLR, 2019.
[17] Ignavier Ng, Shengyu Zhu, Zhitang Chen, and Zhuangyan Fang. graph autoencoder approach to causal structure learning, arXiv preprint
2019.
10

---

[18] Xun Zheng, Chen Dan, Bryon Aragam, Pradeep Ravikumar, and Eric Xing. Learning sparse nonparametric dags. In International Conference on Artificial Intelligence and Statistics, pages 3414-3425. PMLR, 2020.
[19] Kevin Bello, Bryon Aragam, and Pradeep Ravikumar. Dagma: Learning dags via m-matrices and log-determinant acyclicity characterization. Advances in Neural Information Processing Systems, 35:8226-82222 2022.
[20] Chang Deng, Kevin Bello, Bryon Aragam, and Pradeep Kumar Ravikumar. Optimizing notears objectives via topological swaps. In International Conference on Machine Learning, pages 7563-7595. PMLR, 2023.
[21] Peter Bühlmann, Jonas Peters, and Jan Emesst Cam: Causal additive models, high-ddimensionl order search and penalized regression. The Annals of Statistics, 42(6))2526-25 2200:26666-256,,,, 2014.
[22] Po-Ling Loh and Peter Bühlmann. High-dimensional learning of linear causal networks via inverse covariance estimation. The Journal of Machine Learning Research, 2014.
[23] Pedro Sanchez, Xiao Liu, Alison Q''Neil, and Sotirios A Tsaftaris. Diffusson models for causal discovery via topological ordering. In International Conference on Learning Representations, 2023.
[24] Bertrand Charpentier, Simon Kibler, and Stephan Günnemann. Differentiable dag sampling. In International Conference on Learning Representations, 2022.
[25] Valentina Zantedeschi, Luca Franceschi, Jean Kaddour, Matt Kusner, and Vlad Niculae. Dag learning on the permutahedron. In International Conference on Learning Representations. 2023.
[26] Yingzhen Li and Richard E Turner. Gradient estimators for implicit models. In International Conference on Learning Representations, 2018.
[27] Arthur B Kahn. Topological sorting of large networks. Communications of the ACM, 5(11))558- 562, 1962.
[28) Sébastien Lachapelle, Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien. Gradient- based neural dag learning. In International Conference on Learning Representations, 2020.
[29] Jonas Peters and Peter Bühhmann. Structural intervention distance for evaluating causal graphs. Neural computation, 27(3):771-799 2015.
[30] Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ, math. inst. hung. acad. sci, 5(1):17-60, 1960.
[31] Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509-512 1999.
[32] Tim Van den Bulcke, Koenraad Van Leemput, Bart Naudts, Piet van Remortel, Hongwu Ma, Alain Verschoren, Bart De Moor, and Kathleen Marchal. Syntren: generator of synthetic gene expression data for design and analysis of structure learning algorithms. BMC bioinformatics, 7:1-12, 2006.
[33] Alexander Reisach, Christof Seiler, and Sehastian Weichwald. Beware of the simulated dag! causal discovery benchmarks may be easy to game. Advances in Neural Information Processing Systems, 34:27722-2: 2021.
[34] Trent Kyono, Yao Zhang, and Mihaela van der Schaar. Castle: Regularization via auxiliary causal graph discovery. Advances in Neural Information Processing Systems, 33:1501-1512. 2020.

---

Appendix
A Theoretical Analysis
A.1 Reviewing LISTEN
To show why LISTEN does not work under nonlinear causal relations, we review the derivation of precision matrix under linear relations. LISTEN uses the linear SEM X BX + N, where B is the autoregression matrix, and N = (G1, ,..., Ed) is independent Gaussian noises. Since B is a weight matrix of a DAG, (I B) is invertible. Then, the covariance matrix of X is equivalent
Σ B B[(1 B B () (ELI-))-'DCCA
B) DD( - B)
where Diag O1,, oa) is the covariance matrix of Gaussian noise. The precision matrix Q the inverse covariance matrix, where Ω (I B) DI- B). When the causal relations is nonlinear, we cannot write it directly in the form of linear weight matrix B multiplied by X. Thus, the connection between the precision matrix and the adjacency matrix of the true causal graph no longer holds under nonlinear causal relations. And we can no directly use the precision matrix to determine the leaf nodes.
A.2 The Proof of Theorem
Theorem Let s(x) = logp(z) be the score and let diag(.) be the diagonal elements of the matrix. For any Tij in the causal graph G:
j = arg max(diag()) Da(z)) 8x 1)) > xy a leaf node
Proof. For an arbitrary node zj in the causal graph G, we focus on the diagonal of the score's Jacobian. The expression of (e;(2) is derived as follows: 0z,
0sy(x) dr, of
1 0h
8 (po,(z)) Ox?
H3 fx(pa(())) of
Σ of dx,
(
(x)) +
Σ
(10)
tEch(j)
(Ech(j)
The residual æ; (x)) in the last term the RHS of Eq 10 is additive noise as stated in Equation which implies that ==-Si(pa(a)) + (0, ) Furthermore, since e, and (a,(x) are independent of each other our SÉM, the expectation of the last term can be expressed as:
0 (pa,(x))) dny
I; --((p(((x)) of
E
Σ
tEch(j)
(11)
E Σ
0 On²
EE E 1= (xa(())))
o7
(EOh(j)
With Eg 10 and Eq |1 the expectation of (s;(x) 0z, can be restated as:
(z)
Of: El(
IE|
(pa: (x)))
(12)
Ox;
d
Ox;
tECh(J)
According to Eq 12 the expectation of daş(*) is only dependent on the current node xy and its
dz,
children. Suppose that 2; is leaf node and v, is a lea-leaf node, we have @ay(ar)
of and
Dz
(m)) dzn
Eiech(n) 1 E[( 01 Bis (pa,(x)))
(i) If the sufficient condition (i) satisfied, we have non-decreasing variance of noises. For any two noises E; and Ej of different nodes, σ, o, if T(i) < x(j). Since 2 is a leaf node
12

---

and En is non-leaf node, x(n) < T(),, we have 2 on. And, Therefore, we can get
B[(
0f
[pa))))))
2 0.
of
Os((a) E
1 0
1 0f
Of Fzn
Dsn (13)
El(
(pa, (pa, (x))))
[F|
Ox
n IECh())
This equation implies that the value of the leaf node will always be greater than the non-leaf node in the diag of the expectation of score's Jacobian. And, for any causal graph, there is at least one leaf node æ1. Thus, the arg max max(diag(E)) ( [)) is the index of the leaf node, i.e.,
j = arg max max(diag( [ [e(x)) ()) = 2j is a leaf node.
(ii) If the sufficient condition (ii) is satisfied, we have non-weak causal effect of parents. For any non-leaf nodes T,j, Elecm())
oi A 0i ary ary (z))()))) z dub
_ J.y where min is the
minimum variance for all noises. Thus, the following inequality holds.
(s((2)
dzi
of
2
=
o
-
0
o
min
min
(14)
0fs
don (x) Oxn
Σ
El(
(paa())))) = E
iECh(A)
Therefore, it can be obtained in the same way that j = arg (nax((iaag(E)))) du ()) =
is
leaf node.
Thus, under the sufficient conditions (2) or (ii), we can proof that the node in arg max
max(diag( diag(B) 1e(e)))) will always be the leaf node.
A.3 Derivation of SATE and parent score
To illustrate the meaning of this definition, we propose new metric of the Squared Average Treatment Effect (SATE) extended from Average Treatment Effect (ATE, (Ty(T=1) - Y (T))))) which can be rewritten as
SATE/ E(( x.
(T;=1) (T, [7
(15)
In order to establish an association between the parent score and the causal effect, the treatment on Iy is defined as follows:
(Ty f((pa + Az)) + 6
(16)
22 (T)=0) = f(()(())) +
where A; = [0, ..., 5, ..., 0] a one-hot vector denoting an additive treatment on Ty. Here, for each j. we design the j-th value of Aj as 8 which denotes the strength of treatment, which is a very small positive value. Due to the small value of -> 0+, for each variable 2; we can use the optimal linear approximation to represent z: (T)=1) Then, for the j-th treatment, SATE is equal to:
SATE 82. E[(( Øf: dz,
(x))
(17)
For each treatment, we treat with the same strength 8. Therefore, the average causal effect can be represented by E[( Oi
Bay (z))))))) Obviously, its value is zero when 2, not parent of z;. If az a parent of .r. E[( Bay (pa; (=) indicates the influence strength from xy to 24.. Thus, scaled by the variance of the children's noise, we can use J. F 01. dir; (x)))))))² to approximately represent the strength of the average causal effect, which is called the parent score. This new metric considers both causal effect and noise variance, which can considered as the visible part of causal effect the variance of noise is close or equal. This assumption does not affect the sufficient conditions for the identifiability of topological ordering and only supposed in post-processing. which has been used frequently in previous works [8] [3].
13

---

A.4
Derivation of computing parent score
Parent score cannot be obtained directly from the summation of average causal effects of node on its children in Eq 12 thus we propose an iterative decoupling process and define
J == [E) (2)
)02(1)) 1,
Osa( (z)
1, E
E
1}
(18)
dz1
Or²
axd
to denote the expectation of the diagonal of the score's 's Jacobian. By removing the node ri, new vector J-, is defined as follows:
J-; [ 2s (2)((=))
)s2(x--)) J,... .. [ (s,(x) ..... EI
)sa(x-1) Ord
[EI
(19)
0x,
Ox²
Ox,
where x represents the remaining data after removing the feature of i-th dimension, For the i-th element of J-i. we fill the i-th element of J. To simplify the notation, define in this subsection that J(5) and = بLر are the j-th element of the corresponding vector. Then, for j-th element, we have
E[( 05 (pax (z)))
(20)
oj
T
dzy
kECh()
0hk E 0
J4
Σ
(pox (pxx))
(21)
of
Ox,
kECh(j)/=;
where Ch(j)/a; denotes the set which the element v; has been removed if it is the children of æy T; is not the children of zj. Ch(j) is equal to Ch(j)/zx According to the definition of parent score,
we have
E[( di (x),( Iy E pa,(x) 02,
P.s = JoP -
(22)
x & (x)
Then, each row vector of the matrix of parent score P E Rdxd is equivalent to:
P.. --i-J
(23)
Thus, we can obtain the parent score by iteratively removing nodes and estimating the score's Jacobian.
A.5 The Proof of Corollary
Corollary 1. = arg (E] (s(22 = xy' 's sum of parent score Ei= Pig is minimal = Tz a leaf node
dz
xy's sum of parent score Σi=o Pig is minimal. Under the sufficient condition (ii), the sum of parent score of non-leaf node has low bound have EizoPas = or dd Pijj 2 ami Jacobian, we have
Proof. We first prove that j arg max (diag( (T. (s(x) D)
Ox
Ouis aj According the definition of parent score, for any node Tj.
Thus, for an arbitrary element the diagonal score's
B0, dz, E
E
EL Paj Σd Pis 2
o
(24)
de,(()) 02
<
Obviously, - is always greater than
Therefore, given Ij with j
arg max(diagg (e(a)))) [)), its sum of parent score is minimal and Σd_ Pig 0.
Then, we prove that xy 's sum of parent score Σi= Pi, is minimal = xy is leaf node. Suppose that is leaf node and on is non-leaf node, according to the definition of parent score, we have Ei Pi, 0 Σgn Pt,. Therefore, the node with the minimal sum of the parent score leaf node.
14

---

B Pseudocode of Post-processing
CaPS introduces the pre-pruning and edge supplement process post-processing, which considers more information about causal effect by using the parent score. The complete post-processing procedure is shown Algorithm 2 where P Pmux is the matrix broadcasted with the maximum value of each row of P. For hyperparameter À selection, we set to À 50 for all datasets to avoid any dataset-specific tuning, which can be further optimized in appendix C.3
Algorithm 2 Post-processing
Input: data matirx X E IRrxd rigor X, permutation π, parent score P Output: adjacency matrix A
I: initialize A using π
2: A A @ int(P PUSs T // pre-pruning
3: A < CAM pruning(A, (A, X)
4: E int(P > A avg @ A))
5: for each edge (i. j) in & sorted by P., do
6: A + 1 if A is still acyclic edge supplement
7: end for
8: return A
C Experiments
All experiments were run on EPYC 7552*2 with 512G memory and NVIDIA RTX 4090 32GB.
C.1 Dataset Details
Synthetic data are created using the Erdös-Rényi (ER) 30 or Scale-Free (SF) models 31 The degree of each node in the ER graph is relatively even, whereas some nodes in the SF graph may have very high degrees. Each dataset has 2000 samples and 10 nodes by default, while larger-scale datasets and different samples size are also given Appendix [..] The sparsity of the graph is altered by changing the average number of edges to either d or four times d, referred to as SynER1 and SynER4. The weight of each edge is randomly chosen from the range of [-1, - (0.1, To create datasets with both linear and nonlinear relationships between variables, we set the noise distribution to be Gaussian with a mean of 0 and a variance of 1. To generate linear causal functions fi. we use weighted causal graphs. For nonlinear causal functions fi, we sample Gaussian processes with a unit bandwidth RBF kernel and multiply them by the weights in the causal graph, similar to SCORE and DiffAN. A collection of five datasets is created for SynERI I and SynER4, with range of linear and nonlinear causal connections, from 0.0 (all nonlinear) to 1.0 (all linear) with step 0.25.
Syntren:
Legal topological ordering:
Ty.
X1 X2. X3. X4
X2
72.
X1.
X2. x4. X3
X1.
Xg.
X2. X6
X4
X1
X1.
X3.
X4. X2
75g
X1.
X2.
X1.
X3.
usefal
Figure 5: Example of the Syntren dataset.
Two real datasets are adopted. Sachs [ protein signaling network based on protein expression levels and phospholipids, consists of 11 nodes, 853 observations, and 17 edges from ground-truth causal graph; Syntren [32), pseudoreal data set sampled from the Syntren generator, consists of 10 transcriptional networks, each consisting of 500 observations and a DAG consisting of d = 20 nodes and edges with E (20, ..., 25). For the two real datasets, we only have ground-truth DAG but no relation types. quantitatively give more insight into their linear and nonlinear proportion, we estimate the type of relation in the DAG with a rough metric: Pearson correlation~0.55 as linear
15

---

relation. Accordingly. Sachs has 0.18 linear ratio while Syntren averaged 0.92 for different DAGs (0.72 1.0). Although these ratios are rather rough, is evident that mix relations are widespread in realistic applications. This explains why CaPS is effective in different datasets.
Fig. [gg.5sshwss example of Syntren dataset, which is special dataset containing many networks. In this network structure, only the topological ordering of the first node 21 is meaningful, and the other nodes can be ordered randomly after æ1. This star structure is not friendly ordering- -based methods, since topological ordering provides more limited information in such a causal graph. However, among all ordering- based methods, CaPS achieves the highest performance in this dataset.
C.2 Additional Synthetic Datasets
Fig. O shows the experiments results of the SynSFI and SynSF4 datasets. We can observe that CaPS performs better for both sparser (SynSF1) and denser (SynSF4) graphs in almost all ranges, especially when the linear proportions above 0.25. The results show that CaPS performs consistently well in almost all ratios and different DAG generator (ER or SF).
0.5
Caft
8
SCIPO
DiGaeretyge
0.30
825
0.50
0.25
3.00
0.00
325
656
0.75
1.2
0.00
0.25
1.1
0.75
(a) SynSF1
24
0.3
CiPS
NOTIANS
2HD
GCAER
2.44
SCORE
DMNA
3.25
0.50
3.00
325
0.50
1.53
0.25
2.55
1.90
Uhtor S10001/05
Lreur
(b) SynSF4
Figure 6: Results of SynSF1 and SynSF4 with different linear proportions.
0.00
4G
0.53
Sachs
125
150
150
(b) Syntren
Figure 7: Performance under different hyperparameter A.
16

---

C.3 Hyperparameter Analysis
We further study in Fig. 7 the effect of different À on the performance of pre-pruning and edge supplement on the real datasets. As we mentioned in the ablation study, edge supplement is more effective on the Sachs dataset, while pre-pruning dataset, edge supplement works best under À E [40, 70), and CaPS can maintain better or competitive performance in a large range of the hyperparameter dataset for causal discovery, it could be possible to add some incorrect edges when À is too small. Pre-pruning shows more potential in the Syntern dataset, which can be further improved by selecting different hyperparameter A. Based on the results shown in Fig. 7 we can see that the performance of CaPS can be further improved by setting different hyperparameters for pre-pruning and edge supplement, e.g., À = 20 for pre- mre-pruning and À 70 for edge supplement.
more effective on the Syntren dataset. For Sachs
For Syntren dataset, since it difficult
C.4 More Baselines
We additionally consider six baselines of continuous optimization: DAG-GNN [16,, a nonlinear extension of NOTEARS that uses an evidence lower bound as score; GAE [7 autoencoder based method that further extends the NOTEARS and DAG-GNN to facilitate nonlinear relations;
NOTEARS-MLP [18 is nonlinear extension of NOTEARS; DAGMA [19] uses log-determinant
acyclicity characterization; TOPO (00 optimizes with iteratively swapping pairs of nodes within the topological ordering: CASTLE
auxiliary task to the prediction task. The results of the real data experiments on fourteen baselines are presented in Table 2 On the Syntren datasets, NOTEARS-MIE suboptimal SHD but poor SID, suggesting that their predictions are too dense or sparse. Our method achieved the highest SHD) and F1 scores Sachs, with SID second to VI-DP-DAG. VI-DP-DAG had the best SID but the worst SHD, as it discovered a large number of false edges.
34 uses causal discovery
achieves suboptimal SID but poor SHD,, and CASTLE achieves
Table 2: Results of real-world datasets.
Dataset
Sachs
Syntren
Metrics
SHIA
SID
F11
SHD.
SID,
FI1
CAM
12.040.00
55.020.00
0.444.0.00 000
38.0a5 .5
178.6 178.62444.56 556
0.223
NOTEARS
12,0+0.00
46.0+0.00
0.387=0.000
33.9:4.57
192.8454.73
0.164#0.085
DAG-GNN
14.0+0.00
45.0+0.00
0.397=0.005
32.4=4.86
191.2+52.66
0.156+00.066
GAE
17.2+1.00 1.00
50.2+2.93
0.119=0.11 112
19.7=13.13
156.3479.10
0.127+0.077
NOTEARS-MAL MLP
14.420.49
46.010.00
0.35920.005
114.7=30.50
150.4148.51
0.093100037
DAGMA
13.0+0.00
46.0#0.00 00
0,370 000
35. 35.626.70
191 8=54.
0.186 062
21.620.40
+4.0200.0
0. 0.30320.000
19.0=12.90
191.0157.20
0.227H0.115
GOLEM
17.0:0.00
44.0+0.00
0.421
43.7+10.72
177.4s.5..55
0.16340..06
CASTLE
15.8+4.12
46.8+0,98
0. 0.299=0.051
30.5=8.14
266.1211.23
0.096#0.08
GraNDAG
13.2+0.75
54.0=t1.0
0.373=0.064
26.5+6.455
155 35.33+58.11 11
0.344=00.004
VI-DP-DAG
42.6+11.36
40.0+5.66
0.340=0.037
182. (2226:44422)
144.3435.00
0.06944.03 039
SCORE
12.0:0.00
45.010.00
0.444.0.000
37.5a4.20
197.1
0.183100091
DifIAN
12.2+0.98
46.2#6.11 18
0.43420.078
44.128.29
188.7455 16
0.19120.095
DAGuerrcotyp
17.920.54
51.420.49
0.11820.034
87.929.60
157.7448.900
0.125a0.047
CaPS
11.0+0.00
42.0+0.00
0.50020.000
37.2:5.04
178.9455.58
0,230+0.072
C.5 Larger-scale datasets & actual-time cost.
Table 3 shows the experimental results of large-scale datasets and the actual-time cost. Here, we varied the settings of the synthetic dataset SynER1 to be: d = 20, d = 50, = 1000 and n = 5000. For better presentation, we abbreviate the linear proportion as prop. and the baseline DAGuerrcotype as DAGu. On different scales of datasets, CaPS consistently achieves the best performance in most linear proportions, especially in mixed scenarios (prop.=.225, 0.5, 0.75). Our method also achieves the best or competitive results even in pure linear and pure nonlinear scenarios compared to existing strong baselines. About the actual-time cost, despite cubic complexity in samples size n, the bottleneck of actual-time growth often lies in the number of nodes d in causal graph since many n-related operations are GPU-friendly, However, since CaPS uses pre- pre-pruming for acceleration in the post-processing stage, our method run with competitive actual-time cost even in large-scale datasets.
In terms of pruning time, most of the time is spent on CAM pruning. Pre-pruning can effectively remove the edges with low parent score, which can reduce the cost of fitting generalized additive
17

---

Table 3: Results of larger- scale datasets with actual-timg cost.
Metrics NOTEARS
COLEM GRINDAG
CAM
DAG SCORE
DITAN
DAGu.
DAGa.
CaPS
SynERI (d=20)
SHD
17.4+1.7
15.2+1.8
5.3+1.2
1.40.88
123.2 244.9
1.40.88
6.2+3.7
23.642.0
18.342.6
0.8+0.4
SID
81.2=16.1
81.0#22.6
18.627.7
8.466.1
33.427.3
5.413.2
31.6117.5
63.3+23.5
46.6422.8
3.4+2.8
27.0=11.1
41.3+8.9
82.026.3
95.5+2.6
96.5a2.3
79.9+11.4
44.0=10.8
66.846.6
98.1=1.0
SHD
14.8+1.6
14.2+2.0
5.3+0.9
3.4+133
118,4+744
0.4
4.6+2.0
18.0+1.6
19.3+3.2
1.2+1.1
0.25
SID
73.8=14.3
78.0=21.7
32.0=9.8
18.2+10.0
56.8+23,9
3.877.6
32.2+15.0
39.0+2.1
64.0+53.9
1.6+10.2
F1 44.1+5.7
43.9=12.7
79.846.0
87.145.4
16.4+3.1
98.621.8
81.948.5
61.543.7
52.6+10.2
96.0+3.9
SHD
10.8+1.7
10.0+1.6
9.6+2.6
5,4+2.6
125.4+8.3
4.6+3.9
6.642.6
25.3+6.6
27.0+5.0
4.243.0
13.3
53.6216.9
63.3421.6
85,2=20.0
17.2=13.3
24.2:12.5
72.3=37.0
40.649.7
17.0=114
F1 64.127.5
64.318.4
66.226.1
81.466.7
11.2+2.2
87.749.9
78.8
50.6:77.6
51.2460.
94,92-466
7.8+2.9
16.6+3.3
3.8+2.3
9.0+3.3
21.6+10.2
26.3+1.2
16+
0.75
STD
46.6+10.4
45.6+21.6
67.6+10.4
57.2+18.8
83,4+44.2
17.4+13.6
41 41.6+13.3
49.3+36.5
56,6+3.3
11.8
72.5+4.3
7.14=11.0
43.4+13.6
63.1+10,7
13.8+4.9
88.2+44
70.926.7
56.1=16.9
48.5+2.0
94,9+4.6
SHD
7.0+0.8
1.4
18.3+0.4
12.8+2.9
119.248.2
6.242.0
9.8+1.7
27.048.2
26.340.9
2.0+2.2
SID
41.8=12.
24.0#2.2
74.6#6.5
60.2+20.0
84.6=35.4
30.6#22.6
34.8+5.8
51.622577
64 64.6b6.7
12.4+12.1
78.624.6
84.123.8
40.5a8.2
55.5a12.4
14.124.7
80.4244
69.624.3
51.91866
46.340.5
93.726.0
Training time
6.720.6
36.740.7
990.1493.9
327.7a5.7
343.
29.8s1.2
80.9&1.0
33.242.6
45.4+2.6
15,8
SynER1 (d=50)
SHD
43.024.8
39. 814.7
26.627.7
5.2+2.8
795.2:295
6.6+3.0
17.0#3.4
96.3=13.9
56,3+6.2
7.2+4.4
281.2=1
173.3+77.6
25.2+7.7
198.6479.5
105.8+55.7
17.3
168.
56.6+49.0
F1 27.5+6.5
34.3+6.1
60.1+12.4
94.3+2.1
6.9=11
93.2+3.0
77.8+4.6
34.5+3.9
52.4+0.4
91.4
SHD
38.026.0
32.627.3
30.024.9
12.2+9.8
806.4:17.8
12.0=3.5
16.833.5
98.6216.7
649.2
11.4188
0.25
SID
248.0 4
254.6194.5
168.6228.7
63,2441.2
84809
79.2418.6
109.0451.9
294.01110
199.449444
68.4118.6
F1
10.7
48.5+11.4
58,4+10.2
84.7+10.5
5.745.1
84.45544
76.8+4.0
32.543.6
47 47.5+2.4
85.743.3
SHD
29 8+4.3
27.4+1.
25.6*6.9
16.4+7.9
816.6#35.5
12.0=5.5
20.8+4.7
14.0
80,349.5
11.4+4,4
0.5
SID
201
001.4:113.
186.6457.8
143.028.8
76.0146.6
231.6275.7
65.2+48.2
134.8482.8
285.
218.6+
72.8247.5
48.4
58.3+6.7
62.1+13.0
79.0=9.6
6.2+0.7
85.6#6.8
72.8+4.3
37.442.5
43, 1+5.2
86,5+5,4
SHD
26.8+2.6
23.243.3
37.6#5.7
26.428.8
789.6226.2
11.824.3
19,4=2.3
85.647.4
103.0=27.7
8.2+3.0
0.75
SID
190.6186.4
190.8477.2
267.6278.8
146.0258.3
303.62110.9
53.2+19.5
94.2240.0
224.0=104.2
165.3478.2
35.8+18.2
F1 62.747.1
64.813.7
46.2+10.5
66.027.9
5.740.7
85.4=5.0
75.942.9
41.140.8
40,4:49
90.0+3.9
SHD
18.242.9
18.8+5.5
40.0=1.6
34.0+11.8
782.8435.2
10.2+4.9
21 21.247.2
94.0=11.4
120.3+6.6
6.242.8
131 23647
139.2459.1
258.3
214.4+118.5
344.42165.1
69 8+-29
102 846.99
152.6444.7
198.6999.1
36.8+1188
F1
77.425.6
72.347.0
47.243.5
58.129.9
3.620.9
86.625.7
74.246.4
40.021.3
34.621.7
92.343.5
Training time
29.646.5
40.1+0.4
3.1kst022k
23k+1.8k
322.6218.7
1.3k38.4
1.3k559.9
71.5+2.6
89.1+
319,8+98.8
SynERI (n=1000)
6.6
6.2+2.2
3.0+1.4
39.0:1.2
0.621.2
2.641.8
12.643.3
11.0=.6
0.4+0.8
STD
21.4+12.5
14.4
7.646.2
0.6+1.2
14.6+5.6
0.6+1.2
10.8+11.9
8.6#3.6
9.2+4.2
0.6
18.9
36.3+24.2
78.8+9.5
95.9#6.1
22.244.2
96.8+6.3
79.6+13.4
48.146.3
52.7+7.4
97,8+4.4
SHD
6.621.6
6.412.1
3.3+1.8
2.622.2
39.422.5
1.621.3
2.611.8
9,342.6
9,242.4
1.0:1.2
0.25
SID
20.2+12.4
23.0=15.0
11.323.0
7.247.7
13.466.3
4,243.9
12.2412.1
9.3x4.7
12.016.0
2.242.8
1=22.3
36.0=22.7
68.826.3
79.0=15.4
20.629.2
16.6
78.8114.9
50.7210.2
$2.545.1
93.3+8.2
SHD
6.2+1.9
5.0
4.3+1.2
3.822.7
39.4a1.3
2.81166
3.840.9
11.32:16
12.2+1.6
2.0g0.8
15.848.8
13.6#2.0
16.6+14.2
12,2+4.6
11,2+8.1
3.2+1.9
F1 14.2+18.8
141.2
16.5+10.0
67,3+22,4
20.7+15.7
78.6=9.7
64.5+10.8
42,8+3.9
44,8+6.7
86.8+5.1
SHD
4.2=1.7
5.2+2.9
5,342.0
1.40044
39.622.2
2.2+1.1
3.6+2.1
9.0=2.4
11.0=1.6
14+0.8
0.75
SID
10.818.2
18.0=16.1
16.321.6
5.844.0
17.6210.9
7.616.6
10.046.9
4.3g4.1
6,012.1
6.216.2
F1
68.9=12.6
56. 1+25.6
49.5+12.1
83.514.3
19.924,9
81.1+11.1
70.3+12.5
60.546.9
50.147.6
89.346.9
4,412.6
7.34447
2.24144
3.241.9
10.623.6
13.342.0
1.210.7
SID
8.418.9
17.0s16.5
16.626.0
9.647.9
18.0=10.4
9.0&6.1
10.646.5
5.0a4.5
6.0a2.1
5.646.6
79.646.7
61.5+23.3
43.5+17.6
77.2+15.6
18.5+7.8
79.9&1
71.2+10.5
54.5+11.1
44.7+8.9
90.246.7
Training time
2.1
32.241.3
471.5233.7
9.940.4
151.1=33.9
4.0+0.9
33.3+2.0
36.5242.
34.9+3.7
3.5+0.7
SynERI (n=5000)
SHD 6.4
5.6&1.2
0.340.4
0.0k41.0
37.8
0.640.4
2.8.1.8
3.6
3.0a0.0
0.440.88
SID
19.429.2
18.029.8
1.3+18
0.0:0.0
8.47.8
2.+199
10.828.7
6.3343.8
4.3+4.7
0.6+1.2
FI 41.1=10.7
50.625.7
97.743.1
10020.0
26.625.5
93.245.5
74.1213.5
81.3133.
80.642.6
96.8 96.846.3
SHD
6.242.3
5.2+1.6
1.040.8
0.640.8
39.0=1.0
20406
3.042.5
3.0+1.6
3.042.1
0.040.0
0.25
SID
10.0
16.4&11.2
3.642.6
2.242.7
11.877.1
6.0+2.8
11,849.7
8.0:4.3
6.0A2.1
0.0+0.0
F1 39.9=28.1
$7.3=12.5
91.026.3
94.626.5
22.2+3.8
81.1
75.1
70.2=19.9
81.0=10.7
100:0.0
5.4a2.2
2,0.0.8
39.420.4
4.423.6
2.311.2
14a1.0
0.5
SID
12.8+7.3
16.4=11.4
6.3+1.2
2.2+2.7
16.6#8.D
14.0a6.4
12.4#11.1
5.3+1.6
6.6+1.2
5.4+5.7
F1 54.0=17,2
54.0=17.6
81.527.1
84.129.9
20.821.7
62.0=14.9
68.1923.9
78.348.2
73.1+10.8
87.727.6
SHD
4.251.1
4.8+330
4.641.8
6,242.9
39.8
5.412.6
6.0H2.6
5.6433.3
6.042.8
2.2+2.0
0.75
SID
11.247.6
17.2+16.1
15.0=2.1
20.8+9.5
19.4+11. 1.1
14:2669
17.2+12.1
8.0+4.9
8.047.0
4.4+2.8
09.056.7
56.8:26.9
54.8#17.9
48.6425.2
19.2#6.0
62,5+14.5
56.4422.8
65.4
64.3+11.6
84.0+10.8
SHD
3.2+0.9
4.822.4
9.013.55
6.241.6
40.421.3
6.613.7
6.242.2
5.342.8
5.613..6
3.44199
9.0s8.6
18.4a14.9
20.325.1
22.048.2
17.0#6.9
17.849.6
4.3118
4.640.9
10,2+3.5
F1
77.5+6.8
56. 1+20.4
38.3+3.7
48.5+19.3
17.0+4.7
52,3+14.D
48.6+21.5
69.348.8
69.2+14.7
74.7+10.6
Training time
3.920.6
32.740.6
551.1290.5
55.7&1.1
458.5s194.5
14.3a0.8
42.4a13.5
65.5+33.3
36.642.7
15.040.4
18

---

model. Here, we explore the speedup of pre- pre-pruning different datasets and sparsities. Fig. shows that our method effectively speeds up the pruning time on all datasets through pre-pruning. The symbols -I. and -N in the dataset denote linear and nonlinear, respectively. Comparing SynER and SynER4, we can find that acceleration is more effective in sparse causal graphs than in dense ones. This is due to the fact that in sparse graphs, there are more edges with low confidence in parent score, and pre-pruning is more efficient. Moreover, the acceleration ratio of pre-pruning becomes more significant when the number of nodes d grows, which makes major contribution to the speed advantage CaPS in larger-scale datasets.
SynERt (4-53)
78.7
SyaERI-N (d-50)
74.85%
SynERt-- (1-20)
19/415
SyaER (d-20)
46.567
SydERe (4-10)
SydERd-N (d=10)
6.43%
SyuERL-4, (d-13)
20,87%
SeaERL-N (d=13)
19.35%
Accilentiinn (56)
Figure & Percentage of acceleration using pre-pruning.
C.6 Order Divergence
Order divergence. Order divergence [ is a measure of the discrepancy between the estimated topological ordering and the adjacency matrix of the true causal graph A, which is expressed as:
Drop (T, A)
A.s
(25)
i=1 jom,,>a
Here, we compare two-stage ordering-based based methods in datasets with different linear proportions and sparsity. The results in Figure show that CaPS has a much lower order divergence than sortnregress in different linear proportions and sparsity, suggesting that variance is not a reliable measure of topologiaal ordering in our synthetic datasets. CaPS consistently achieves the best order divergence in most of settings, which reflects the effectiveness of our method in recognizing the correct permutation.
1.0
2.5
15.0
Nethod CAN
[AV cutiongger
2.0
25
3.0
0.
600
0.23
0.33
1.00
5.00
0.39
propartio
(a) SynER1
(b) SynER4
Figure 9: Order Divergence of SynERI and SynER4 with different linear proportions and sparsity.
C.7 Beyond Our Assumption
Theoretically, according to the sufficient condition (ii) of Assumption 1, our methods also has good potential for unequal variance settings. We experimentally find that CaPS performs well under both Gaussian noise with unequal variance and non-Gaussian noise, as illustrated in Figs. TO and TT More relaxed conditions for CaPS can be explored in future work.
19

---

Unequal variances noise. Beyond the equal variance noise, we generated datasets with unequal variance Gaussian noise. Specifically, following the most popular settings previous works, for each variable 2i, the corresponding 6 (0, of), where of are independently sampled uniformly in (0.4, 0.8). Fig. Thlshows the experiment results of eight baselines. We can observe that CaPS performs second only to CAM for sparser (SynERI) graphs. However, CAM does not handle dense graphs well. For denser (SynER4) graphs, our method performs similarly to the best methods SCORE in almost all ranges.
COLOH
SCORE
BiGaemstgee
0.
8.25
1.00
2.55
1sw propartien
1iner proportion
Liner aoppcttionn
(a) SynERI
1.0
CM
COLEH
DiGzeratypel
0.
13WN prosorize
Ubwr proporton
(b) SynER4
Figure 10: Results of SynERI and SynER4 with unequal variance Gaussian noise.
Non-Gaussian noise. We also experimentally explore the potential of CaPS for ANM with non- Gaussian noise. Specifically, for each variable 2;, we set the noise distribution to be Gumbel and Laplace. Fig. shoows the experiment results of eight baselines. We can observe that CaPS performs consistently well for both Gumbel and Laplace noise in almost all ranges, especially when the linear proportions are greater than 0.25.
1.0
GMR
OOLEH
14.0
DiGaeratoge
0.3
Unber propartion
Liner www.orttto
(a) SynERI (Gumbel noise)
USM
0U5
OvEEAC
0.2
Uicaemstgge 4
8.25
3.00
3.35
0.50
1.23
1.5
1,0
Lhaa procorton
Unerr 3ropartinn
Unber poppertionn
(b) SynERI (Laplace noise)
Figure 11: Results of SynER1 with different non Con-Gaussian noise.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: This paper propose a method that works well both linear and nonlinear, which has been clearly stated in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The proposed method, CaPS, works under Assumption 1. The results beyond our assumptions are given Sec. Sec. and Appendix C.7 The computational efficiency are
given in Sec. 4.4 and Appendix C.5
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
21

---

Answer: [Yes]
Justification: All assumptions and proof' are clearly stated in our manuscript and are detailed in Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The experimental settings are detailed in Sec. 5.1. and Appendix C.I All data,
code, and documentation are in the Supplementary Material. All experiments can be easily reproduced with our code.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
22

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
All data, code, and documentation are given in the Supplementary Material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://mips.ca
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips. htcp//blcc/guddeeeeeeeeeeeeeeeee
soiobiiiiisiooccccyc. for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental settings are detailed Sec. 5.1 and Appendix C.1
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
See the results with standard deviation in Table I and
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
23

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of http://pps/pppooooccc/////////ta
Answer: [Yes]
Justification: Yes, this paper conform the the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is a foundational research and has no direct negative social impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All data and methods explicitly mentioned.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
25

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: All data, code, and documentation given in the Supplementary Material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "6xdMAlPX2F", "reviewer": "Reviewer_wbDM", "summary": "This paper addresses the challenge of ordering-based causal discovery, which involves first determining the topological ordering of variables (typically by recursively identifying sub-leaf nodes) and then identifying the parent set for each variable.\n\nExisting methods often focus on either nonlinear or linear relationships. For instance, SCORE relies on a constant score Jacobian, which fails in the absence of nonlinear relationships, whereas LISTEN employs a precision matrix, which makes no sense in nonlinear contexts.\n\nThis work proposes an ordering-based method that accommodates both linear and nonlinear relationships. Specifically, it identifies the topological ordering using the expectation (instead of the variance) of the score's Jacobian, under a sortability assumption on the exogenous noise components. Subsequently, average treatment effect estimation is extended to identify the parent sets.", "questions": "My major concerns and questions are listed above in \"Weaknesses\" section.", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "1. The application of ordering-based causal discovery methods to models with both linear and nonlinear relationships is novel to me.\n\n2. The theorems and mathematical details appear to be correct, though I haven't checked all the details.\n\n3. The experimental results are comprehensive, covering various competitors, different settings, and cases where assumptions are violated (e.g., C.7).", "weaknesses": "1. **Assumptions are too strong:**\n  - For linear relationships in the ANM, additional assumptions are required for identifiability. This paper adopts assumptions similar to those in LISTEN, namely, that the variances of exogenous additive noise components follow the same topological ordering of the causal DAG, akin to VAR-sortability assumptions (Reisach et al., 2021). These assumptions are overly stringent, impractical, and lack testability. More discussions regarding this can be referred to \"Structure Learning with Continuous Optimization: A Sober Look and Beyond\".\n  - The authors also assume that all additive noise components are zero-mean Gaussian. It is unclear if this assumption is utilized throughout the paper or why it was mentioned if not. Also, are these assumptions testable?\n  - Regarding the Gaussian assumption, if it is not used for any proof, the authors might consider assuming non-Gaussian noise. This would allow the DAG to be identifiable even with linear relationships. Then, with score matching (which still works, as in Sec4.3 in the SCORE paper) and some straightforward processing (to preserve for non-Gaussianity/residual independence), the problem might still be solvable in a much more elegant way.\n\n2. **Insufficient motivation for \"parent score\":** Once the topological ordering of the DAG is identified, one could use conditional independence tests between variables and all preceding variables to determine each edge's existence (as in most permutation-based methods), or employ sparse regression, as suggested in the original CAM paper. The authors need to justify the necessity of proposing a \"parent score,\" which seems over-complicated with average treatment effect estimation framework. Are there any advantages (e.g., in terms of time complexity or finite sample guarantee, as in the LISTEN paper)?\n\n3. **Lack of technical novelty:** The technical contributions mainly combine ideas from SCORE and LISTEN, making the results and derivations (e.g., from constant variances to expected value of variances) straightforward extensions of previous work. While novelty is not a primary concern for me, it is worth noting as a minor weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Preliminaries**\n\nThank 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.\n\n**Q1.1:** VAR-sortability assumption are too strong.\n\n**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. \n\n**Q1.2:** Is zero-mean Gaussian utilized? testable?\n\n**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.\n\n**Q1.3:** non-Gaussian proof? like Sec4.3 in the SCORE.\n\n**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.\n\nThanks 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.\n\n**Q1.4:** motivation for parent score.\n\n**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.\n\n(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.\n\n(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.\n\nTherefore, parent score is not a over-complicated design.\n\n**Q1.5:** lack of novelty. CaPS combine ideas from SCORE and LISTEN?\n\n**A1.5:** We understand your concerns, but CaPS is totally different from SCORE and LISTEN the following reasons:\n\n(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.\n\n(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.\n\n(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).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Efp9nqA6Fu", "reviewer": "Reviewer_8ao9", "summary": "The authors propose an ordering-based causal discovery algorithm designed to handle both linear and nonlinear causal relations in an SEM. In contrast to existing methods that assume purely linear or nonlinear relations, CaPS introduces a unified criterion for topological ordering and a new \"parent score\" to quantify the average causal effect, which aids in pruning and correcting predictions. Experimental results show that CaPS outperforms some sota methods on synthetic data with mixed linear and nonlinear relations and demonstrates competitive performance on real-world data.", "questions": "* Looking at the derivations, the approach seems difficult to generalize to more general noises. What are your thoughts on this?\n* Both conditions in Theorem 1 seem impossible to verify, is this sentiment correct?\n* Did you assume equal variances in the experiments? I think experimenting on settings where noise variances are random might make sense in this case.\n* I think a couple of more recent methods such as DAGMA (Bello et al. 2022) and TOPO (Deng et al. 2023) are known to outperform both NOTEARS and GOLEM. I think it could be worth comparing against those methods.\n\nBello et al. (2022), \"DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization\".\n\nDeng et al. (2023), \"Optimizing NOTEARS objectives via topological swaps\"\n\n\n* Line 52: \"creterion\" should be \"criterion.\"", "limitations": "There are some limitations not \"explicitly\" stated such as assumptions on causal sufficiency and Gaussianity of noises.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* CaPS provides a new approach that can handle both linear and nonlinear causal relationships, addressing a relevant gap in current causal discovery methods.\n* The introduction of the parent score is interesting and provides a quantitative measure of causal strength, which improves the pruning process and prediction accuracy.\n* The authors present a new criterion for distinguishing leaf nodes using the expectation of the Hessian of the data log-likelihood and provides sufficient conditions for the identifiability of the causal graph, inspired by SCORE and LiSTEN.", "weaknesses": "* All noises are assumed to be Gaussian.\n* The identifiability conditions rely on assumptions such as non-decreasing variance of noises, which is hard to hold in practical scenarios.\n* Some more recent methods are not compared against.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable suggestions, as they can aid in enhancing our work. We hope that the responses below have addressed your concerns.\n\n**Q2.1:** non-decreasing variance of noise \n\n**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.\n\n**Q2.2:** Gaussian assumption & derivations seems difficult to generalize to more general noise\n\n**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.\n\nTheoretically, 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.\n\n**Q2.3:** Both conditions in Theorem 1 seem impossible to verify.\n\n**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.\n\nThus, 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:\n\n(1) CaPS can work well in both linear and nonlinear and most possibly mixed cases, which is widespread in real-world data.\n\n(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.\n\n(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.\n\n**Q2.4:** assume equal variances in the experiments?\n\n**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.\n\n**Q2.5:** comparing with DAGMA and TOPO.\n\n**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. \n\nYes, as you mentioned, DAGMA and TOPO are stronger baselines than NOTEARS and GOLEM. And, we can learn two conclusions from Table 3:\n\n(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.\n\n(2) Similar to other baselines, DAGMA and TOPO are also suffering significant performance loss when linear/nonlinear assumptions mismatch.\n\nThis 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "HzQJOoLm46", "reviewer": "Reviewer_SPoa", "summary": "This paper proposes an ordering based causal discovery method when the underlying causal model has both linear and nonlinear causal relationships. Starting with a method to iteratively find leaf nodes, this paper proposes to use parent score for better pruning. Results show that the proposed method outperforms baselines.", "questions": "Please see weaknesses section.", "limitations": "Limitations are discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Paper is written well and easy to understand.\n2. Theoretical motivations are clearly explained and the proof are adequately provided.\n3. Experiments are extensive and cover all theoretical aspects.", "weaknesses": "1. Results are not great on real-world datasets. \n2. Topological divergence is a popular metric for evaluating the topological order. Very few results are presented in supplementary on this metric.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your constructive feedback, as it can help us improve our work. We trust that the following answers have clarified your questions.\n\n**Q3.1:** Results are not great on real-world datasets.\n\n**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. \n\n**Q3.2:** Few results of topological divergence\n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "4my35STrCw", "reviewer": "Reviewer_7cyK", "summary": "This paper studies the causal discovery problem in mixed functional relations data, where both linear and non-linear relationships exist in the causal graph. The author presents a Jacobian score-based method (essentially a score-matching method) to identify leaf nodes and thereby recover the causal order. The experimental results demonstrate the efficiency of the proposed methods.", "questions": "See Weaknesses.", "limitations": "NAN", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is clearly written and well-organized.\n\n2. The setting of mixed functional relations data is interesting and may be important for real-world scenarios.\n\n3. The author proposes a Jacobian score-based method, which is an extension of the score-matching method for non-linear Additive Noise Models (ANM).", "weaknesses": "1. The non-decreasing variance of noises assumption is too strong and restrictive. Typically, in ANM, the noise term is assumed to be mutually independent.\n\n2. It appears that the primary difference between the score-matching method for ANM and the proposed method is the introduction of Assumption 1.\n\n3. If I use an independent residuals-based method, it seems to work in your setting. So, what are the advantages of the proposed method? For example, is the proposed method capable of handling large-scale structures? If so, the experimental results should demonstrate this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**Q4.1:** non-decreasing variance too strong.\n\n**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. \n\nThen, 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.\n\n**Q4.2:** The primary difference between the SCORE and CaPS is assumption 1.\n\n**A4.2:** We understand your concerns, but SCORE and CaPS is totally different for the following reasons:\n\n(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.\n\n(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).\n\n(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).\n\n**Q4.3:** independent residuals-based method work in this setting? what are the advantages of CaPS? (e.g. handing large-scale structures)\n\n**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.\n\nYes, 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.\n\n(1) Although KCIT does not significantly degrade in linear and nonlinear performance, it consistently underperforms CaPS in all scenarios with different linear rate.\n\n(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).\n\n*Since KCIT and ReCIT are compatible with CaPS, KCIT and ReCIT can use CaPS to largely reduce their search space.\n\nThis 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. \n\n[1] Zhang H et al. (2018) Measuring conditional independence by independent residuals: theoretical results and application in causal discovery.\n\n[2] Zhang H et al. (2019) Measuring conditional independence by independent residuals for causal discovery.\n\n[3] Zhang K et al. (2011) Kernel-based Conditional Independence Test and Application in Causal Discovery.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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: Reviewers agreed that the paper introduces a novel method, extending the capabilities of causal discovery. There were concerns about the assumptions necessary for the method to work, but as the authors point out, all causal discovery methods must by necessity make some difficult assumptions, and the proposed method weakens some important assumptions made in previous work. Reviewers commended the extent of the experimental validation, with the method overall achieving encouraging results.
Decision: Accept (poster)