Causal Discovery via Cholesky Factorization
Authors: Xu Li
YUNFENG CAI
Mingming Sun
Ping Li
Venue: ICLR 2022 Submitted (2022)
Keywords: DAG Structure Learning
Causal Discovery

Abstract: Discovering the causal relationship via recovering the directed acyclic graph (DAG) structure from the observed data is a challenging combinatorial problem. This paper proposes an extremely fast, easy to implement, and high-performance DAG structure recovering algorithm. The algorithm is based on the Cholesky factorization of the covariance/precision matrix. The time complexity of the algorithm is $\mathcal{O}(p^2n + p^3)$, where $p$ and $n$ are the numbers of nodes and samples, respectively. Under proper assumptions, we show that our algorithm takes $\mathcal{O}(\log(p/\epsilon))$ samples to exactly recover the DAG structure with probability at least $1-\epsilon$. In both time and sample complexities, our algorithm is better than previous algorithms. On synthetic and real-world data sets, our algorithm is significantly faster than previous methods and achieves state-of-the-art performance.

Under review as a conference paper at ICLR 2022
CAUSAL DISCOVERY VIA CHOLESKY FACTORIZATION
Anonymous authors
Paper under double-blind review
ABSTRACT
Discovering the causal relationship via recovering the directed acyelic graph (DAG) structure from the observed data is challenging combinatorial problem. This paper proposes an extremely fast, casy to implement, and high-performance DAG structure recovering algorithm. The algorithm is based on the Cholesky factorization of the covariance/precision matrix. The time complexity of the algorithm Opp"n + p²), where p and are the numbers of nodes and samples, respectively. Under proper assumptions, we show that our algorithm takes (log(p)) or (pp) samples exactly recover the DAG structure under proper assumptions. In both time and sample complexities, our algorithm is better than previous algorithms. On synthetic and algorithm is significantly faster than previous methods and achieves state-of-the-ar performance.
data sets, our
INTRODUCTION
As Schelling had said: "The whole world is thoroughly to caught in reason, but the question is: how did it get caught in the network of reason in the first place?" (Kuhn, 1942; Zižek & von Schelling, 1997), people found that learning the causal inferences between the variables is a fundamental problem and has many applications in biology, machine learning, medicine, and economics. The problem usually is considered as finding directed acyclic graph (DAG) from an observational joint distribution. Unfortunately, learning the DAG structure from the observations is proved to be an NP-hard problem (Chickering, 1995; Chickering et al., 2004).
The problem is generally formulated as the structural equation model (SEM), where the variable of a child node function of its parents with additional noises. Depending on the types of functions (linear or non-linear) and noises (Gaussian, Gumbel, etc.), there are several SEM families, e.g., Spirtes et al. (2000); Geiger & Hcckerman (1994); Shimizu et al. (2006). In general, the graph can be identified from the joint distribution only up to Markov equivalence classes. Zhang & Hyvarinen (2012); Peters et al. (2014); Peters & Bühlmann (2014); Gao et al. (2020) propose several SEM forms that make the graph fully identifiable from the observed data.
Various algorithms had been proposed to deal with the problem. Search-based algorithms (Chickering. 2002; Friedman & Koller, 2003; Ramsey al., 2017; Tsamardinos et al., 2006; Aragam & Zhou, 2015; Teyssier & Koller, 2005; Ye et al., 2019; Lv et al., 2021) generally adopt a score (e.g.. BIC (Peters al., 2014) score, Cholesky score (Ye et al., 2019), remove-fill score (Squires et al., 2020)) to measure the fitness of different graphs over data and then search over the legal DAG space to find the structure that achieves the highest score. However, exhaustive search over the legal DAG space is infeasible when p is large (e.g., there are 4 DAGs for 10 (Sloane et al., 2003)). Those algorithms go quest of trade-off between the performance and the time complexity.
Since Zheng et al. (2018) proposed an approach that converts the traditional combinatorial optimization problem into a continuous program, many methods (Yu et al., 2019; Lee et al., 2019; Ng et al., 2019 Zheng et al., 2020; Lachapelle et al., 2020; Squires et al., 2020; Zhu et al., 2021) have been proposed. Those algorithms formalize the problem as a data reconstruction task with various differentiable constraints the DAG adjacent matrix and solve it via the augmented Lagrangian method. These algorithms are able to utilize neural networks to approximate the complicated relations between the features in the observed data and achieve good performances. Recently, reinforeement learning based algorithms (Zhu et al., 2020; Wang et al., 2021) also improved the performance by exploring the possible DAG structure candidates. The algorithms update the parameters of the model

---

Under review as a conference paper at ICLR 2022
via policy gradient as long as it explored better DAG structure with higher reward which measures how well an explored structure meets the requirement of DAG and the observed data.
Topology order search algorithms (TOSA) (Ghoshal & Honorio, 2017; 2018; Chen et al.. 2019; Gao et al., 2020; Park, 2020) decompose the DAG learning problem into two phases: (i) Topology order learning via conditional variance of the observed data; (ii) Graph estimation depends the learned topology order. Those algorithms reduce the computation complexity into polynomial time and are guaranteed to recover the DAG structure under some identifiable assumptions. Our method in this paper is also a topology order search algorithm and it merges the two phases in TOSA into one. In each iteration, it attempts find a child or contemporary of the current node. Meanwhile, also determines the corresponding column vector of the adjacent matrix. The mergence brings three main First, the topology order TOSA recovered purely based on the conditional variance of the observed data, whereas our method may also take the sparsity of the adjacent matrix into account; Second, the graph LASSO methods, which are commonly adopted estimate the graph in the second phase in TOSA, encourage the sparsity of the precision matrix, whereas method is able to encourage the sparsity of the adjacent matrix; Third, the time complexity reduced significantly. To be specific, the time complexity of our algorithm is O(p2n + p²), while the fastest algorithm before is Opp²n) (Park, 2020; Gao et al., 2020). Here p and n are the numbers of nodes and samples, respectively. In addition, under proper assumptions, we show that our algorithm takes (1og(p)) or O(p) samples to exactly recover the DAG structure. Compared with previous TOSA algorithms, the sample complexity of our method is much better. Experimental results on synthetic data sets, proteins data sets, and knowledge base data set demonstrate the efficiency and effectiveness of our algorithm. For synthetic data sets, compared with previous baselines, our algorithm improves the performance with a significant margin and at least tens or hundreds of times faster. For the proteins data set, we achieve state-of-the offthe--rr-tt performance. For the knowledge base data set, we can observe many reasonable structures of the discovered DAG. Our code is uploaded as supplementary material and will be open-sourced upon the acceptance of this paper.
differences:
The rest of this paper is organized as follows. In Section 2, we present our algorithm together with the theoretical analysis. In Section 3, numerical results on synthetic data sets, proteins data set, and knowledge base data set are given. Finally, the paper is concluded in Section 4.
The symbol || stands for the Euclid norm of a vector or the spectral norm of matrix. For vector [x1, D2 Øpl RP, ||2 stands for the 4--nrmm, i.e., ||>ا|| Σ [z,]-
Notations.
For a matrix X = [X,y] E Rm* || ||2, stands for the two-to-infinity norm, ie., X 12,00 =
maxigism |X,,;Il max stands for the max norm, X |maxx = max.,j [X,l--
2
CAUSAL DISCOVERY VIA CHOLESKY FACTORIZATION (CDCF)
In this section, we first present some preliminaries on DAG, then motivating our algorithm. Next, the detailed algorithm and theoretical guarantees for the exact recovery of the algorithm are given.
2.1 PRELIMINARIES
We assume the observed data is entailed by a DAG = (p. V)E,, where p is the number of nodes, V = {u).... ...,, Up} and E = {(,, vz) [p] represent the set of nodes and edges, respectively. Each node vú is corresponding to a random variable X,. The observed data matrix X [x., xp] "x where x; is consisting of i.i.d observations of the random variable X,. The joint distribution of X is P(X) = II_ P(X,|Pag(XX)) where (X,) = (Xyl(vr, uy) E E} the parents of node X..
Given X, we seek to recover the latent DAG topology structure for the joint probability distribution (Hoyer et al., 2008; Peters et al., 2017). Generally, X modeled via a structural equation model (SEM) with the form
X = ((Pag(X))) N₁, (i= l,...,),
where /3 is an arbitrary function representing the relation between X, and its parents, N₂ is the jointly independent noise variable.
In this paper, we focus on the linear SEM defined by
X; Xw; No, (i=1,...,))
2

---

Under review as a conference paper at ICLR 2022
where W; Rº is weighted column vector. Let W (Wi....,, Wpl RPx be the weighted adjacency matrix, N = mm....., ny] E Ruxp be an additive independent noise matrix, where n, is ii.d observations following the noise variable N,. Then the linear SEM model can be formulated as
X +
(1)
We assume the noise deviation of the child variable is approximately larger than that of its parents (see Theorem 2.1 for details). Following this assumption, classical identifiable form of SEM is the Ginear-Gaussian SEM, where all N, are i.i.d. and homoscedastic (Peters Bühlmann, 2014).
2.2 ALGORITHM MOTIVATION
As proposed in McKay et al. (2003); Nicholson (1975), graph DAG if and only if the corresponding weighted adjacent matrix W can be decomposed into
W = PTPT"
(2)
where permutation matrix, strict upper triangular matrix, i.e., Tiy for all S j.
We denote the scaled permuted data matrix as X
I.
X.,, the scaled permuted noise matrix as
V'
N
NP, and the permutation order [ 22 ...... [1.2 ................................ ... We can rewrite (1) as v
x= XT N.
Then it follows that
x N -T)-
(3)
Let
B(N'Ñ) = -3 ΣΣ
(4)
where E22 is the covariance matrix of the noise variables, Σ is upper triangular the Cholesky factor of Σ.. Let the diagonal entries of Σ of :...... variance of Nig-
o. We know that o? the conditional
Now using (3) and (4), we have the covariance matrix of the permuted data:
C. - = (I - Q
(5)
Let L = (1 (1-T) ST then Č LL"" which is the Cholesky factorization of the covariance matrix Č, since L is lower triangular. Furthermore, we can see that the diagonal entries L are the same as that of Σ, i.c., LEs = o the conditional variances of X and Nig are the same.
The task becomes to find the permutation i" = ig., (]] and an upper triangular matrix U such that U U is good approximation of the empirical estimation of the permuted covariance matrix Ō XT X and U satisfies some additional constraints, such as the sparsity, etc.
2.3 ALGORITHM
We iteratively find the permutation and calculate U via the Cholesky factorization. Assume that i--1 [1 [i1....,44 111] and -+ U1: 1.1k-1,1:-111 are settled, and we have
CLA-1-18-1
X X XI UU 1-11
where A > 0 is diagonal augmentation parameter which we will give detailed discussion latter. Next, we show how to find is and the last column Ug.
For the time being, let us assume is is known, we show how to compute the last column of Up. Let U
U yv then
U
Vk
T
Us =
U U.U. U. v - af+llvel?
+A XT X
0k
X
1x

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Causal Discovery via Cholesky Factorization (CDCF)
1: input: Data matrix X R Truncate Threshold w > 0, and tuning parameter "..
2: output: Adjacent Matrix A.
4: Set arg min {I]x ll. X 2,00 and log R:
3: Set 2, -............ -p]. R |
..... X ixp
5: Exchange i1 and ig in i; Set U1
| 12
6: for k 2........ ................................
do
7: for j = k k 1,...,P do
8:
Vj 1 UT XI -6--1 X
a
9:
(j V x
12 + 11,11
10:
end for
11:
(V) l = arg مS a3:
(S) = arg gisp 10-13y;l1ı
(VS) L arg min | aa - Ek=1
12:
Exchange in and it in 8; U of 13-18t
13:
Set U
end for return A [TRIU(TRUNCATE(U] (e
15:
where the last equality dues to (6). It follows that
yk
X
X
ag V
X vi +
n
And direct calculation gives rise to
U
U yk Og
U
m Uk-1Mk
(8)
By (8), once is settled, we can obtain the last column of UR- Our task remains select it from (1.... .P) {ir,..., . There are several ways to accomplish this task. We propose three criteria to select in. First, we need to compute ar and y, by (7) for all possible j (i, (1, (I....,P) (i....., 1.) Then we select is according to one of the following criteria:
(V) is = arg ming az. Under the assumption that the noise variance of the child variable is approximately larger than that of its parents, it is reasonable/natural to select the index that has the lowest estimation of the noise variance. This criterion is guaranteed to find the correct permutation i' with high probability, which is shown in Section 2.4.
(S) is arg minssisp ||U,-19,1l 1- Using (3) and (6), know that U, intends to estimate (I (T-T) --T When the adjacent matrix T is sparse and the noise variables are independent (i.e., Σ is diagonal), we would like to select the index that leading to the most sparse column of Ug. This criterion especially useful when the number of samples is small, see Tables B. B.2 and B.3 in appendix.
(VS) is
We empirically combine criterion (V) and criterion (S) together to take both aspects (variance and sparsity) into account. Numerically, we found that this criterion achieves the best performance in real-world data.
arg min |U -
The diagonal augmentation trick in (6) is commonly used for an invertible and good conditioned estimation of the covariance matrix (see e.g.. (Ledoit Wolf, 2004)). Such a trick not only ensures that our algorithm does not break down due to the singularity of the sample covariance matrix, but also stabilizes the Cholesky factorization, especially when the sample insufficient. In addition, by setting À = O (o the error bound between the population covariance matrix and the augmented sample covariance matrix does not become worse (see Lemma ?? in the appendix). This trick
4

---

Under review as a conference paper at ICLR 2022
significantly improves the ability recover the DAG, especially when the samples insufficient, see Tables B.4, B.5 and B.6 in appendix.
The detailed algorithm is summarized in Algorithm 1. Some comments and implementation details follow. Line 4, we select the very initial value & = arg min { {|,
1,,,,], |l,
(X,,, I|,,,,, |l}. Line
1F++ Lines 6 to 14, we iteratively calculate we exchange i1 and ig in and calculate U1 = | IP
UR and update permutation order until all the indices are settled. Line 15, we truncate U, take its strict upper triangular part (denoted by "TRIU") and re-permute the predicted adjacent matrix back to the original order according to the permutation order i. Specifically, the truncation is done column-wisely. By (8), the value of [Upl.k is inversely proportional org. So, for column k we set We ax. and do the truncation: [Up]a is set to zero if [U,]a < wi. On output, node connects to node j in G if A, > O.
Time Complexity Note that we do not have to re-calculate the matrix multiplication of X. 1,221 X.,,, in line 8 since we can calculate C at the cost of Oppán) at first. Besides, at step k, we have already calculate entry of yy. which is the inner product between two k dimensional vectors, at the cost of O(p) in worst case. Overall, the time complexity CDCF is Opp" + p²n). When n > p, the complexity becomes Op)r), which is equivalent the complexity of calculating the covariance matrix. Additionally, the inner loop (lines 7 to 10) of CDCF can be done in parallel, which makes the algorithm friendly to run on GPU and suitable for large scale calculations.
.i, at previous step, we only need calculate the last
2.4 EXACT DAG STRUCTURE RECOVERY
The following theorem tells that our algorithm is able to recover the DAG exactly with high probability under proper assumptions.
Theorem 2.1 Let x E RP be zero-mean random vector, C = E(xxT) E RPXP be the covariance
mairix. Let XI,..., be independent sumples, Ö Σ X1 be the sample covariance n
k=
O 2 0 is parameter. Let the Cholesky factorizations of C = Exx" and C2 be C = LL and Ò₁ = LLT, respectively, where L and L are both lower triangular. For the linear SEM model (1), assume (2) and (4), and for (J) 5 inf infkePag()) 6fk > 0, where
estimator. Assume ||C Ōll Ć S e for some e O. Denote C* = C AI, where
85k o + [3 (I T) 11)-1pm - -
oi
If 2 4(E + A) and |L1 (- + A) < 3 then CDCF-V is able to recover P exactly. In addition, holds that
[[RIU - T| max <
(T, A);
where UU) stands for the strictly upper triangular part Up. p. Up Algorithm I with criterion (V).
the output of outer loop of
know that when T is sparse, we may recover its topology structure by truncating Up-
Proposition 1 Let Nr. be independent bounded, or sub- Gabbsiansnnn, or regular polynomial-tait then for n > (c), holds IlC... Czzll I c, w.h.p. Specifically.
-T) -
((c) 2 C1 logg
for bounded class;
|1 ((--T)--0 (T) 1
N(e) 2 C2p
for the sub-Gaussian class;
[[[ (II-)) -1-11) C ( 2(1+r-1)
N(6) 2 Cap
for the regular polynomial tail class.
The proofs of are provided in the Appendix A. This theorem and proposition also indicates the sample complexity of our algorithm is Opp). This sample complexity is better than the sample complexities of previous methods, see Table 2.1 for detailed comparison.
5

---

Under review as a conference paper at ICLR 2022
Table 2.1: Sample complexity comparison. The last column represents the O complexity of the sample number n that makes the algorithm recover the DAG with probability at least 1 --6, 6, p is the nodes number, r represents the level of the graph, d is the maximum total degree, m represents the m th moment bounded noise, g(x) x/ log exists when x > 3 and g (x) > Z.
Algorithm NPVAR
Data
Function
Noise Type
Cov(X) |aample Complexity
(Non)-lineat Lip-continuous
0((rp/<)\-0/)
(Gao et al., 2020)
EV
>>p P
Linear
Amin > 0
Opg"log(P) (p)
(Chen et al., 2019)
n P
Linear
Amin >> 0
O4 Oo
LISTEN (Ghoshal & Honorio, 2018)
Linear
Sub-Gaussian
Oid log (p)
Linear
Bounded moment
Od (p²) (p"))/m
US
Amin
n > p
Linear
Gaussian
g (OOlog(p))
(Park, 2020)
Amax < oo
Sub-Gaussian Polynomial tail
CDCF
Linear
O(p)
3
EXPERIMENTS
In this section, we apply our algorithm to synthetic data sets, proteins data set and knowledge base data set, respectively, to illustrate the efficiency and effectiveness of our algorithm.
3.1 LINEAR SEM
We evaluate the proposed methods on simulated graphs from two well-known ensembles of random graph types: Frdös-Rényi (ER) (Gilbert, 1959) and Scale-free (SF) (Barabási & Albert, 1999). The average edge number per node is denoted after the graph type. For example, ER2 represents two edges per node on average. After the graph structure settled, we assign uniformly random edge weights to obtain a weight matrix W. We generate the observation data X from the linear SEM with three noise distributions: Gaussian, Gumbel, Exponential.
We chose our baseline methods as NOTEARS (Zheng et al., 2018). DAG-GNN (Yu et al., 2019), CORL (Wang et al., 2021), NPVAR (Gao al., 2020), and EQVAR (Chen al., 2019). Other methods such as PC algorithm (Spirtes et al., 2000), LiNGAM (Shimizu et al., 2006), FGS (Ramsey et al., 2017), MMHC (asammardinos et al., 2006), LIOBS (Schmidt al., 2007), CAM (Bühlmann et al., 2013), RL-BIC2 (Zhu et al., 2020), A *LASSO (Xiang & Kim, 2013), LISTEN (Ghoshal & Honorio, 2018), US (Park, 2020) perform worse than or approximately equal to the selected baselines, and the results can be found in the corresponding papers.
Table 3.1 presents the structural Hamming distance (SHD) of baseline methods and our method on 3000 samples (n 3000). Nodes number p is noted in the first column. Graph type and edge level are noted in the second column. We only report the SHD of different algorithms due to page limitation, and find that other metrics such false positive rate (FPR), and FI score have the similar comparative performance with SHD. We also test bottom-up EQVAR which is equivalent to LISTEN, the result is worse than top-down EQVAR (EV-TD) in this synthesis experiment, so we do not include the result in the table. For 1000 graphs, we only report the result of EV-TD and CDCF since other algorithms spend too much time (longer than a week) to recover a DAG. We test our algorithms with different variations according to criteria (V, S, VS) introduced in Section 2.3, and with diagonal augmentation trick noted by "+" as postfix. For example, "CDCF-V" means CDCF with V criterion and À O, and "CDCF-V+" means CDCF with V criterion and X = O 2og2). The implementation details are in the Appendix B. We report the result of CDCF-V V+ here, and the results of other CDCF variations can be found in Appendix Table B.4, We run our methods on ten randomly generated graphs and report the mean and variance in the table. Figure 3.1 plots the SHD results tested on 100 nodes graph recovering from different sample sizes. We choose EV-TD and high dimension top down (EV-HTD) as baselines when p > n and p I n, respectively. We can see from the results, CDCF-V V+ achieves significantly better performance comparing with previous baselines.
positive rate (TPR), false discovery rate (FDR),

---

Under review as a conference paper at ICLR 2022
ER2
ERS
SF2
5F5
400
1500
200
300
150
LTN
1000
400
LTN-CH
100
100
500
200
0
0
0
200
300
400 500 600
200
300
400
500
600
200
300
400
500
600
200
300
400
500
600
3000
2000
2000
CDCF-V+
1000
EV-HTD
1500
1500
LTN
2000
750
1000
500
1000
500
250
500
20
60
Sample
Sample Number
Sample
Sample Number
Figure 3.1: Performance (SHD) tested 100 nodes graph recovering from different sample number.
Table 3.1: Results of 50, 100, 1000 nodes on 3000 linear Gaussian SEM samples.
Nodes
Graph
NOTEARS
DAG-GNN
CORL-2
NPVAR
EV-TD
CDCF-V+
ER2
38.610.8
30.6g.3
17.910.6
0.4u.5
0.0o.o
0.0p.o
ER5
67.87.5
93.2109.4
64.813.1
0.6g.8
0.1g.3
0.0g.0
50
SF2
3.51.8
79.393.2
0.0p.0
1.11.0
0.0p.o
0.0p.o
SF5
20.1
89. 89.299.2
20.810.1
1.0p.9
0.0p.o
0.0g.0
HR2
72.623.5
66.2
18.65.7
2.11.
0.0g.0
0.0o.0
ER5
170.334.2
236.436.8
164.817.1
2.31.2
0.2o.4
0.10.3
100
SF2
2.31.3
156.821.2
0.0p.0
3.01.41
0.0p.0
0.0o.0
SF5
90.2x4.5
165.222.u
10.86.1
2.7u.9
0.1p.s
0.0p.o
ER2
0.4g.5
0.1o.3
ER5
21.8a.8
8.94.2
1000
SF2
0.0p.o
0.0o.0
SF5
0.3o.5
0.0o.0
Table 3.2: Running time (seconds) 30 and 100 nodes over 3000 sample.
30
100
ER2
ER5
SF2
SF5
ER2
ER5
SF2
SF5
CDCF-
0.004
0.005
0.004
0.005
0.017
0.016
0.016
0.017
EV-TD
0.19
0.16
0.12
0.12
14.42
12.88
15.04
14.78
LISTEN
0.26
0.13
0.13
0.14
13.97
13.41
13.42
15.43
EV-HTD
8.27
7.48
6.72
12.50
260.74
302.36
241.59
387.92
DAG-GNN
49.15
49.02
38.44
41.03
137.25
238.71
158.13
187.21
NPVAR
84.24
82.57
108.37
109.13
9867.96
9084.78
10667.88
10173.89
NOTEARS
78.19
597.16
51.57
306.31
3237.8
1803.30
880.19
4159.82
CORLI
17573.08
18799.21
16422.11
16588.30
Table 3.2 shows the running time which is tested on a 2.3 GHz single Intel Core i5 CPU. Besides, parallel calculation of the matrix multiplication on GPU makes the algorithm even faster. Recovering 5000 and 10000 nodes graph from 3000 samples on an A A100 Nvidia GPU is approximately 400 and 2400 seconds, respectively. For comparison, EV-TD costs approximately 100 hours to recover a 1000 nodes DAG from 3000 samples. As illustrated in the table, CDCF is approximately dozens or hundreds of times faster than EV-TD and LISTEN, and tens of thousands times faster than NOTEARS CDCF does not have update the parameters with gradients.
7

---

Under review as a conference paper at ICLR 2022
Table 3.3:
Results Proteins data
Data sets
Methods
FDR
TPR
FPR
SHD
N
P
FI
CDCF-V/V+
0.533
0.412
0.210
11
15
0.467
0.438
CDCF-S/S+
0.500
0.412
0.184
10
14
0.500
0.452
CDCF-VS/VS+
0.500
0.412
0.184
10
14
0.500
0.452
853 samples 17 edges
NOTEARS
0.588
0.412
0.263
13
0.412
0.412
NOTEARSMLP
0.733 0.235
0.290
18
15
0.267
0.250
CORL1&2
0.533
0.412
0.211
15
0.467
0.438
EV-TD
0.645
0.294
0.237
17
14
0.357
0.323
LISTEN
0.750 0.176
0.237
0.250
0.207
NPVAR
0.800
0.176
0.316
19
15
0.200
0.188
DAG-GNN
0.588
0.412
0.263
0.412
0.412
CDCF-V/V
0.667
0.400
0.457
21
24
0.333
0.364
CDCF-S/S+
0.611
0.350
0.314
17
18
0.389
0.368
CDCF-VS/VS
0.556
0.400
0.286
16
18
0.444
0.421
7466 samples 20 edges
NOTEARS
0.650
0.350
0.371
20
20
0.350
0.350
NOTEARSMLP
0.800
0.200
0.457
26
20
0.200
0.200
C
0.667
0.400
0.457
21
24
0.333
0.363
EV-TD
0.700
0.300
0.400
0.300
0.300
LISTEN
0.714
0.300
0.429
23
21
0.286
0.293
NPVAR
0.679
0.450
0.543
28
0.321
0.375
DAG-GNN
0.650
0.350
0.371
20
20
0.350
0.350
Due to the page limitation, further experiments and discussions of the ablation study (Figures B.3 to B. 14, Tables B.1 to B.6), choice of X (Tables 7 to B.10), and performances on different noise distribution (Figures B.1, 1, B.2) and deviation (Tables 111 B.12, B.13) are given in Appendix B.
3.2 PROTEINS DATA SET
We consider a bioinformatics data (Sachs al., 2005) consisting continuous measurements of expression levels of proteins and phospholipids in the human immune system cells. This is widely used data set for research on graphical models, with experimental annotations accepted by the biological research community. Following the previous algorithms setting, we noticed that different previous papers adopted different observations. To included them all, we considered the observational 853 samples from the "CD3, CD28" simulation tested by Teyssier & Koller (2005); Lachapelle et al. (2020); Zhu et al. (2020) and all 7466 samples from nine different simulations tested by Zheng et al. (2018; 2020); Yu al. (2019).
We report the experimental results on both settings in Table 3.3. The implementation codes of the baselines are introduced in the appendix, and we use the default settings of the syper-parameter provided in their codes. The evaluate metric is FDR, TPR, FPR, SHD, predicted nodes number (N), precision (P), F1 score. As the recall score is equal TPR, we do not include it in the table. In both settings, CDCF-VS+ achieves state-of oftte-of-the-art performance. Several reasons make the recovered graph not exactly the same as the expected one. The ground truth graph suggested by the paper is mixed with directed and indirect edges. Under the settings of SEM, the node "PKA" is quite similar to the leaf nodes since most of its edges are indirect while the ground truth graph notes it as the out edges. Non- would not be an impact issue here since NOTEARS and our algorithm both achieve decent results. In the meantime, we do not deny that further extension of our algorithm to non-linear representation would witness an improvement on this data set.
3.3 KNOWLEDGE BASE DATA SET
We test our algorithm on FB15K-233 data set (Toutanova et al., 2015) in which the knowledge is organized as (Subject, Predicate, Object) triplets. The data set has 15K triplets and 237 types of jump predicate between the entities, which
predicates. In this experiment, we only consider the jump
For NOTEARS-MI.L Table reported the results reproduced by the code provided in Zheng et al. (2020).
8

---

Under review as a conference paper at ICLR 2022
2.0 Parent
Child
Medicine/Discase
Peoplo/CauseOHDeall
Doddicine/Riskaacton
PropeeCaassOOfeatth
1.5
Broadcast/Artis Artist
Music/Artist
Broadcast/Artin
Music/Instrumentalits
1.0
CrPPograamCretorr
Tv/aanguages
Tv/ProgramCreator
TvOrriginounntyy
0.5
Tv/Languages
TV/OriginCountry
Tv/Genre
Film/Country
0.0
Film/Director
Media/NetfixGGmmt
Film/StoryBy
Film/Prequel
-0.5
Film/WrittenBy
Film/Genre
Risease/RRiskacttor
Disease/sympton
Sports/Colors
Sports/Teams
-1.0
Person/Nationality
Person/PlaceOOBrrth
Location/TimeZonne TimeZones
Location/Counti Country
Education/ Ccattioonn
Educattion/SchooTTyy
OlympicsCCunnries
Event/Lccations
Olympics/Counties
People/Language
Figure 3.2: The recovered weighted adjacent matrix (left) and examples of the high confidence relation pairs (right) on FB15k-237 dataset.
have 97 predicates remained. We want to discover the causal relationships between the predicates. We organize the observation data as each sample corresponds an entity with awareness of the position (Subject or Object), and each variable corresponds to predicate in this knowledge base.
In Figure 3.2, we give the adjacent weighted matrix of the generated graph and several examples with high confidence (larger than 0.5). In the left figure, the label of the axis notes the first capital letter of the domain of the relations. Some them are replaced with dot to save space. The exact domain name and the picture with the full predicate name are provided in the appendix. The domain clusters are denoted in black boxes at the diagonal the adjacent matrix. The red boxes denoted the cross-domain relations that are worth paying attention to. Consistent with the innateness of human sense, the recovered relationships inside a domain are denser than those across domains. In the cross-domain relations, domain "Film" ("F"), the domain "Broadcast" (last row) have many relations with the domain "Music" ("M"). Several cases of the predicted causal relationships are listed the right side of Figure 3.2, can see that the discovered indication relations between predicates are quite reasonable.
found that the predicate in domain "TV" ("T"") has many relations with the
4 CONCLUSION AND FUTURE WORK
In this paper, proposed topology search algorithm for the DAG structure recovery problem. Our algorithm better than the existing methods in both time and sample complexities. To be specific, the time complexity of our algorithm is O(p2n + +))), while the fastest algorithm before O(p"n) (Park, 2020; Gao et al., 2020), where and n are the numbers of nodes and samples, respectively. Under different assumptions, our algorithm takes (log(p)) or Opp) samples to exactly recover the DAG structure. Experimental results on synthetic data sets, proteins data sets, and knowledge base data set demonstrate the efficiency and effectiveness our algorithm. For synthetic data sets, compared with previous baselines, our algorithm improves the performance with significant margin and at least tens or hundreds of times faster. For the proteins data set, we achieve state-of-the-art performance. For the knowledge base data set,
observe many reasonable structures of the discovered DAG.
The proposed algorithm is under the assumption of linear SEM. Generalization of CDCF to non- linear SEM would be valuable and important research topic. Learning the representation of the observed data for better structure reconstruction via the CDCF algorithm, which requires the algorithm differentiable. is also attractive problem. To deal with the extremely large-scale problems, such as millions nodes, implementing CDCF via sparse matrix storage and calculation on the GPU is a promising way further improve computational performance.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Bryon Aragam and Qing Zhou. Concave penalized estimation of sparse gaussian bayesian networks. Mach. Learn. Res., 16:2273-2328, 2015. URL http::t////tt acm. org/ ciwation.aii....o cfm? 1d-2886822.
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Peter Bühlmann, Jonas Peters, and Jan Ernest. CAM: causal additive models, high high-dimensional order search and penalized regression. CoRR, abs/1310. 1533, 2013. http::/arxiv..rr abs/131 1310.1533. 1533.
Wenyu Chen, Mathias Drton, and Samuel Wang. On causal discovery with an equal- assumption. Biometrika, 106(4):973-88,, 2019.
David Maxwell Chickering. Learning bayesian networks is np-complete. In Doug Fisher and Hans- Joachim Lenz (eds.), Learning from Data Fifth International Workshop on Artificial Intelligence and Statistics, AISTATS 1995, Key West, Florida, USA, January, 1995. Proceedings, pp. 121-130. Springer, 1995. doi: 10. 1007/777
URL https: http://ooooooog/////// 1007/
978 1 4612 2404-4_22
David Maxwell Chickering. Optimal structure identification with greedy search. J. Mach. Learn. Res., 3:507-554, 2002. URL http: /ttt::///mlee org httpg//appsssv///e http://////cccccceccceeeeee html.
David Maxwell Chickering, David Heckerman, and Christopher Meek. Large-sample learning of bayesian networks np-hard. Mach. Learn. Res., 5:1287-1330, 2004. URL http://jjmm
ozq./papers/vollee
pdf.
Nir Friedman and Daphne Koller. Being bayesian about network structure. A bayesian approach to structure discovery bayesian networks. Mach. Learn., 50(1-))955-1555 2003. doi: 10.1023/A: 1020249912093 URL wttps:://///...... /woi./iio//////// org. 1023 1tw.::122/221122999111119
Ming Gao, Yi Ding, and Bryon Aragam. polynomial time algorithm for learning nonparametric causal graphs. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020. URL https: htttpp://proceeeeeeeeete http:////oooooeeeeeeeeeee www.diinnnnnnnnn...ooeoe.m.... neurips...pp.... wwtpccppppp/.//..... 20sh//ahh/hh////// /hash/ 85c9E9efab8 wtteefffbeeeceeeeeeeeeeee11ee
Abstract tatstra.t.htll......
Dan Geiger and David Heckerman. Learning gaussian networks. In Ramón López de Mántaras and David Poole (eds.), UAI '94: Proceedings of the Tenth Annual Conference Uncertainty in Artificial Intelligence, Seattle, Washington, USA, July 29-31, 1994, pp. 235-243. Morgan org/vai http://iisspalaa.aeeeeeeeeeeeeee Kaufmann, 1994. URL htt.aaoeeeeeeeeeeerceeeeeeeeeeee 1 saaaan--iimmmm--aattilllle
Asish Ghoshal and Jean Honorio. Learning identifiable gaussian bayesian networks in polynomial time and sample complexity. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, V. N. Vishwanathan, and Roman Garnett (cds.), Advances in Neural Information Processing Systems 30: Annual Conference Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6457-6466, 2017. URL httph: http::////cocceeeeeeeeeee www.ediinnn.nneiiinnommmmmm wwtrriss.ccpcpppe wttcc//pppppe ptte/paper22000 2appe/20117 /hash/ 907edb0aa www.ee6966222bbbbbee fbw 78859666 Abstract at html.
Neural
Asish Ghoshal and Jean Honorio. Learning linear structural equation models in polynomial time and sample complexity. In Amos J. Storkey and Fernando Pérez-Crus (eds.), International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzurote, Canary Islands, Spain, volume 84 of Proceedings of Machine Learning Research, pp. 1466-1475. PMLR. 2018. URL http: htttt:::pppccceedinge atw..ppees/////ghhcaaaaa..a.....
mir.preesseee wwwps/pssssee..ep. / 884 htt.gghhhhhhhhlaae html..
Edgar N Gilbert. Random graphs. The Annals of Mathematical Statistics, 30(4): 1141-1144, 1959.
10

---

Under review as a conference paper at ICLR 2022
Patrik O. Hoyer, Dominik Janzing, Joris M. Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou (eds.), Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008, pp- 689-696. Curran Associates, Inc., 2008. URL https: http://epocceee..seeeee..e....ee nwwrips....... cctppsccpcpppp//00///// 2wwe22occfeeeeeeeee22ee22e 944bb Abstract .tml.
Helmut Kuhn. Schelling: The ages of the world, 1942.
Sébastien Lachapelle, Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien. Gradient- based neural DAG learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https:// openreview net/ forum?
Olivier Ledoit and Michael Wolf. A well-conditioned estimator for large-dimensional covariance matrices. Journal of multivariate analysis, 88(2):365-41) -1136 2004.
Hao-Chih Lee, Matteo Danieletto, Riccardo Miotto, Sarah T Cherng, and Joel T Dudley. Scaling structural learning with no-bears to infer causal transcriptome networks. In PACIFIC SYMPOSIUM ON BIOCOMPUTING 2020. pp. 391-402 World Scientific. 2019.
Yali Lv, Junzhong Miao, Jiye Liang, Ling Chen, and Yuhua Qian. Bic-based node order learning for improving bayesian network structure learning. Frontiers Comput. Sci., 15(6): 156337, 2021. doi: 1111000/11100-00000 1077044-2200268---
URL https:
1007/
Brendan D McKay, Frédérique E Oggier, Gordon F Royle, NJA Sloane, Ian M Wanless, and Herbert Wilf. Acyclic digraphs and eigenvalues of (0, 1) 1)-matrices. arXiv preprint math/0310423, 2003.
Ignavier Ng. Zhuangyan Fang, Shengyu Zhu, and Zhitang Chen. Masked gradient-based causal structure learning. CoRR, abs/1910.08827,, 2019a. URL http:::/aaxx...og//////aa//////t 08527.
Ignavier Ng, Shengyu Zhu, Zhitang Chen, and Zhuangyan Fang. graph autoencoder approach causal structure learning. CoRR, abs/1911.07420,, 2019b. URL http:tt/aax....to/////////////// 1911.07420
Victor Nicholson. Matrices with permanent equal to one. Linear Algebra and its Applications, 12 (2):185-188) 1975.
Gunwoong Park. Identifiability of additive noise models using conditional variances. J. Mach. Learn. Res., 21:75:1-75::44, 2020. URL http: jmwr. http://ppers//eee
664 html.
Jonas Peters and Peter Bühlmann. Identifiability of gaussian structural equation models with equal error variances. Biometrika, 101(1):219-228, 2014.
Jonas Peters, Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. J. Mach. Learn. Res., 15(1):2009-2055 2014. URL http:
//dl. acm, org/citation www.wedmmmmi......m
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
Joseph D. Ramsey, Madelyn Glymour, Ruben Sanchez-Romero, and Clark Glymour. A million variables and more: the fast greedy equivalence search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images. Int. J. Data Sci. Anal., 121):12 2017. doi: 10.1007/:441000-016-00033 URL https:/ //o::///////////// org/ 10. 1007 / 10040-000000 01 6 0032-2.
Karen Sachs, Omar Perez, Dana Pe' Douglas A Lauffenburger, and Garry P Nolan. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 308(5721):523-522 2005.
11

---

Under review as a conference paper at ICLR 2022
Mark Schmidt, Alexandru Niculescu-Mizi and Kevin P. Murphy. Learning graphical model structure using 11 regulaarization paths. In Proceedings of the Twenty-Secone AAAI Conference on Artificial Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada, pp. 1278-1283 AAAI Press, 2007. URL http:////. / www.. aaai. org/ Tiiraryrrr TAt//AAA//0000 a a 07-202.p0 php.
Robert Sedgewick and Kevin Wayne. "4,2225 Unique topological ordering", Algorithms, 4th Edition. Addison- Weslle,, 2011. ISBN 978-0-321-57351-3
Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti J. Kerminen, A linear non-gaussian acyclic model for causal discovery. J. Mach. Learn. Res., 7:2003-2030, 2006. URL http: //jmlr. org/ http/sapppsss/////ee /vverrs///ie http///shiiii wwwmiiuueeeee 1att0aaahttm... html.
Neil JA Sloane et al. The on-line encyclopedia of integer sequences, 2003.
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search, Second Edition. Adaptive computation and machine learning. MIT Press, 2000. ISBN 0e..0-222211944---
Chandler Squires, Joshua Amaniampong, and Caroline Uhler. Efficient permutationn discovery in causal dags. CoRR, abs/201 1.03610, 2020. URL https: : htt//aaxivv/////////////////aavl
2ttp//2111..11..... 03610.
Nikhil Srivastava and Roman Vershynin. Covariance estimation for distributions with 2 + moments. The Annals of Probability, 41(5):3081-3111 2013.
Mare Teyssier and Daphne Koller. Ordering-basets search: A simple and effective algorithm for learning bayesian networks. In UAI '05, Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, Edinburgh, Scotland, July 26-29, 2005, pp. 548-549. AUAI Press, jsp ?mmnu=
2005. URL
http::///.ppp..t......aaaaaaaaaa 1& hammp:/2artttileeeee22peerreeeee
Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. Representing text for joint embedding of text and knowledge bases. In Lluís Mårquez, Chris Kallison-Burchh Jian Su, Daniele Pighin, and Yuval Marton (eds.), Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, EMNLP 2015, Lisbon, Portugal, September 17-21, 2015, pp. 1499-1509, The Association for Computational Linguistics, 2015. doi: 10. 10.18653/v1/d15-. 1174. URL https::////.. / / i org / 0
/d15 1174.
Ioannis Tsamardinos, Laura E. Brown, and Constantin Aliferis. The max-min hill-clmming bayesian network structure learning algorithm. Mach. Learn. 65(1)331-78, 2006. doi: 10.1007/ $10994-000-6888-7 URL https: tttp///iog/////////////.o/ooo//t /100 /0110000/1119// s10994 00000099440000888-----0
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 2010.
Xiaoqiang Wang, Yali Du, Shengyu Zhu, Liangjun Ke, Zhitang Chen, Jianye Hao, and Jun Wang. Ordering-based causal discovery with reinforcement learning. CoRR, abs/2105.06631, 2021. URL
https://arxte wwtg/bgs////eeeoooeo.oo/o..essst
06631.
Jing Xiang and Seyoung Kim. A* lasso for learning sparse bayesian network structure for continuous variables. In Christopher C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of meeting held December 5-8. 2013, Lake Tahoe, Nevada, United States, pp. 2416, 2013. URL 8ce6790cc66
mewerdiiinnnnnninns...ee..... http://sgg.iriissss.////p//////p -bbst html.
Qiaoling Ye, Arash A. Amini, and Qing Zhou. Optimizing regularized cholesky score for brder-based learning of bayesian networks. CoRR, abs//1904 12360, 2019. URL http: / /ttp/vixivvv..o// org/ abs/ 1904. 12360.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. DAG-GNN: DAG structure learning with graph neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference
Machine Learning, ICML 2019. 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 7154-7163. PMLR, 2019. URL http::/tp//ppe..tt http:::ppppcpceeiiipppppp ngs ml www.pr/ss/vvv /99////////// yul 9a html.
12

---

Under review as a conference paper at ICLR 2022
Kun Zhang and Aapo Hyvarinen. On the identifiability of the post-nonlinear causal model. arXiv preprint FrXXiv:205.25555 2012.
Xun Zheng, Bryon Aragam, Pradeep Ravikumar, and Eric P. Xing. Dags with NO TEARS: continuous optimization for structure learning. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, Pp. 9492-9503. 2018. URL htwpttttt///cc... httpss:/prrcceee ngs neurips wttccc//ppp... wccppappr/201:0 8/hahhhhhh/h// e347c5141 415554444455 fbb 300.
Abst.aatttttt..... html.
Xun Zheng, Chen Dan, Bryon Aragam, Pradeep Ravikumar, and Eric P. Xing. Learning sparse nonparametric dags. In Silvia Chiappa and Roberto Calandra (eds.). The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy), volume 108 of Proceedings of Machine Learning Research, pp. 1425-3425. PMLR, 2020. URL http:ht////// pwwpeedinceeeeeeeeoee mir www.ppresssslooeeeee zheng2 aa. html.
Rong Zhu, Andreas Pfadler, Ziniu Wu, Yuxing Han, Xiaoke Yang, Feng Ye, Zhenping Qian, Jingren Zhou, and Bin Cui. Efficient and scalable structure learning for bayesian networks: Algorithms and applications. In 37th IEEE International Conference on Data Engineering, ICDE 2021, Chania, Greece, April 19-22, 2021, pp. URL https: / /ooi org/ 10. 1109 DIE.IIDEEE11191 2021 00292.
IEEE, 2021, doi: 10.1 19110/9CE33111999022200 2021.090999922999
Shengyu Zhu, Ignavier Ng, and Zhitang Chen. Causal discovery with reinforcement learning. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: https/////ppeeeeeeeeeeee net/ forum? ddd= S1g2skStPB.
Slavoj Žižek and Friedrich Wilhelm Joseph von Schelling. The abyss of freedom. University of Michigan Press, 1997.
13

---

Under review as a conference paper at ICLR 2022
A PROOF OF THEOREM 2.1
In this section, we first give several lemmas, then prove Theorem 2.1.
Lemma A.1 Let X E Ro be zero-mean random vector; C' = E(xx") E R be the covariance matrix. Let X1,-....
Xx, -.....--,,, be independent samples, C 1 n k== X be the sample covariance
estimator. Assume - 2 for some > O. Denote Cx = Č + AI, where = ( 2 0 is
parameter. Let the Cholesky factorizations of C = Exxx and Cx be C = LL and Cx = LL
respectively, where L and L are both lower triangular. If L 112 + A) < f. then
||| | k|. k. S =(c). -
for 1 S siis p;
(9)
||L - [wl I 4 11
for
(10)
Proof.
For all S S p. we have
|| | = |C - - --- (11)
which completes the proof for (9).
Next, show (10). Let
111
=I++
(12)
We know that
-1-
(13)
= L- L-T L- CCL--
(14)
Then it follows from (13) that for >
LL lu I 'kll S F. 11-1 [I+F)) T:lll S F. 1 (15)
First, give upper bound for [[ + F)-1/| Using (12), have (I FI-I(I + F)
(I + E) It follows
( = | F) T( F) 111 = (I + E) 11
1
(16)
E
1 |-- C|I
where the last inequality uses (14). Second, we give upper bound for || Fiiiill -|-- It follows from the second equality of (12) that
(1 F2)) + F = 1+ E..
(17)
Therefore,
(a) Σ L
F F.1-111 < (11 + Fx)² -
Eg
S
15
+ En
L3
E
+ -
2,00 11
C1|
S 2|| 2 (E + A),
112.00
(18)
L
where (a) uses (12), (b) uses (9) and (14), (c) uses (15), we get
|C - õ| < c. Substituting (18) and (16) into
L 1by - 11 < 2 L 11 L
2,00 /
+
(19)
L
The conclusion follows since
||--111(E 2)
3.
14

---

Under review as a conference paper at ICLR 2022
Theorem A.2 Let E Rº be zero-mean random vector; C E(xx²) RpxP be the covariance
matrix. Let Xi...., be n independent samples, C == 1 n. Σオ X be the sample covariance
estimator. Assume ||C Ōl| S for some > 0. Denote C2 = C AI, where X O 2 0 is parameter. Let the Cholesky factorizations of C = Exxx and Cx be C = LL" and Cx = LLT, respectively, where and are both lower triangular. For the linear SEM model (1), assume (2) and (4), for & E Pag(i), d infRePag(s)) 6jk > 0, where
8jh o + 1 T)
k..-1.6 1 Dic-
f 2 4(e + A) and | (1 + X) < then CDCF-V is able to recover P exactly. In addition,
holds that
(UI) - Tl max S
where (RIU(Up) stands for the strictly upper triangular part of Up. Up is the output of outer loop of Algorithm 1 with criterion (V).
Proof. i.e,
For SEM model (1), denote C, -B X Σ B(N'N = ETE,, we have (5),
C. = -I - -I- -
-T
(20)
When the permutation 8" li.....,
. ipl is exactly recovered. then Up CDCF-V satisfies
C = x X + XI = U
(21)
Denote žÿ [i,,-.. -i,-.., for all j 1 ,....;? p Consider the kth diagonal entries of (20) and (21). By
calculations, we get
[C.1uR = =I(I - ST (I-T))
TI" = o7 ||uu 12x
(22)
[xx|xx = - X + = U2 - -1|ū211
(23)
where
U 1,1-----11--14 Tisk T1--1118-1)-11 - TT
ûn -U :8 X
(24)
Using
(C- S, we have
I[C.Jax 1Exlaul < s| -
(25)
By Lemma A.I, we have
||| || / S
(26)
Using (22), (23), (25) and (26), we get
1 2(e A))
(27)
U2
Assume that "...., (k > 1) are all correctly recovered. And without loss of generality, for E (J) we also assume T.. # (otherwise, jth and keth columns are exchangeable, and forms another equivalence topology order to the same DAG (Sedgewick & Wayne, 2011)). 10). Then
15

---

Under review as a conference paper at ICLR 2022
have for & Pj)(j) that
x 1 + + X
11
(a)
[C.lis + +Cxlss - [C.lis - [1 1:kk 1|
16 Iv
[C.l,s (c+ A) -1((u]1:--11 (c
05 + [|[ug]kgj111 2( + X)
og + 2(e A)
@ [C.]Ak |2 + 2(c A)
/ 2 + 4(c + X)
1 X 1| - Ü 2 + 4(E + A),
where (a) uses (23), (b) and (f) uses (25) and Lemma A.I, (c) uses (22), (d) dues to the assumption
0iz 2 oig for Pag(1)) (e) uses (22), (g) uses (23). Therefore, using 4(e + A), we have
Xx 1| + x 10د1
x + - ن !|
which implies that i can be correctly recovered. So, overall speaking, CDCF-V is able to recover the permutation P.
The upper bound for ||TRIU(UP)) T mmax follows from Lemma A.1. The proof is completed.
Proposition 2 Let No: be independent bounded, or tau-Gaassinn, regular polynomial-tad -ail," for n > (e), it holds ||Oze -Crell S w.h.p. Specifically,
|1( - T) -
(()) 2 C1 logp
for bounded class;
|1(I - -11 2
N(6) 2 Cap
for the sub-G Gaussian class;
|1(I - (T--))-110 | || 2(1+r-1)
2 Cap
for the regular polynomial tail class.
Proof. For SEM model (I), we have
C -Cull I [I (I- -1 Canl < (I-T) III C Ill. (28)
where C.. ExxT C.n Enn are the covariance matrices for x and respectively, Özz. Ö.. are the sample covariance matrices for x and n, respectively. The three results listed above follow from Corollary 5.52, Theorem 5.39 in Vershynin (2010), Theorem 1.I in Srivastava & Vershynin (2013), respectively.
AA random vector z is isotropic and sub-Gaussian if Ezz"T = and and there exists constant C > 0 such that P( (('"")] > f) S exp(-C* for any unit vector v. Here by "N., :. sub-Gaussian" we mean that C... NT an isotropic and sub- Gaussian random vector.
AA random vector is isotropic and regular polynomial lil EzzT = I and there exist constants such that 2|| 1) S Ct-1-r for any orthogonal projection and any t C' rrank(V). Here
by" * N.. is regular polynomial-tail" we mean that C NT. is isotropic and regular polynomial-tail random vector.
16

---

Under review as a conference paper at ICLR 2022
B ADDITIONAL EXPERIMENTS
Here we provide implementation details and additional experiment results.
Figures B.I, B.2 provide the results of Gumbel and Exponential noises, respectively. As from the result, our algorithm still performs better than Eqvar method in different noise types.
Tables B,I, B.2, B.3, B.4, B.5, B.6 give results 100 nodes over different sample sizes and variances of our CDCF methods. As noted in Algorithm 1, we have V, S, VS as different criteria to select the current column, "+" representing the sample covariance matrix augmented with the scalar matrix 1. The truncation threshold on column i is wi 3.5/a;; aa, where o; is the diagonal value of the Cholesky factor. According to the results, the algorithm "V+" achieves the best performance as the sample size is relatively large. When the sample size is small, the criterion according to sparsity shows very effective performance improvement. We also test different choices over glogp, 3 {0.0, 1.0..., 9.0), the result is given in Table B.7, B.8, B.9, B.10. Empirically, E {1.0, 2.0} achieves better results. practice, one can sample a relatively small and labeled sub-graph of the DAG to test the hyper-parameter setting then apply to large unlabeled the DAG graph.
To test the performance limitation of methods, provide the results of SHD different sample number and node number in Figures B.3 to B. 14 where the x-axis represents the sample number (in thousand), the y-axis denotes the node number, the color represents the value of log, (SHD + 1) (the brighter the better). We provide the figures for CDCF-V+, CDCF-S+, and CDCF-VS+ on variances graph and noise types. The figures are drawn on the show that the graph can be exactly recovered on 800 nodes at approximately 6000 samples. Comparing CDCF-V+ with CDCF-S+, we find that criterion (S) damages the performance when the sample number is relatively large. When sample number E {1500, 3000) and node number E (400, 800), CDCF-S+ achieves better performance. Such trend can also be demonstrated in Tables B. B.2, B.3. CDCF-VS+ alleviates the poor performance of CDCF-S when the data is sufficient and achieves good performance on real-world data set.
results ten random seeds. The figures
We also test the performance on linear SEM with monotonously increased noise variance. Concretely, assume the topology order is i {i....., ) we set the noise variance of node d + i We test the results Gaussian, Gumbel, and Exponential noise with monotonous noise variance. The results are reported Tables 11, 111,1 B.12 and 1.13. As the results indicated, even with different noise levels, our algorithms achieve good performance and are able to exactly recover the DAG structure when the data is sufficient.
In the result for knowledge base data set, the axis labels of Figure 3.2 are 'Film', 'People', 'Location', 'Music", 'Education', 'Tv', 'Medicine', 'Sports', 'Olympics', 'Award', "Time', 'Organization' 'Language', 'MediaCommon', 'Influence', 'Dataworld', 'Business', 'Broadcast' from left to right for x-axis and top to bottom for y-axis, respectively. The adjacent matrix plotted here is re-permuted make the relations in the same domain close each other. We keep the adjacent matrix inside a domain an upper triangular matrix. Such typology is equivalent to the generated matrix with the original order.
Baseline Implementations The baselines are implemented via the codes provided from the following links:
NOTEARS, NO htt.s///.../....o//////o/oo///na
N http:///tthaacccmmm/iii////////a
EQVAR, LISTEN: LLSTTEXX...nggggghnnoooo///////O
CORL: Wwt.a///s//ititoooooiioooooooooe
DAG--NN; CHGGO///////////ooooo////////oo0
17

---

Under review as a conference paper at ICLR 2022
SF5
40
20
150
CDCF-V+
100
EV-DD
SHD
100
20
10
50
50
200
300
400
500 600
200
300
600
200
300
400
500
600
200
300
400
500
600
3000
3000
CDCF-V+
3000
2000
2000
EV-HTD
2000
2000
1000
1000
1000
20
40
60
80
100
20
40
60
80
100
20
40
60
80
100
20
40
60
80
100
Sample Number
Sample Number
Sample Number
Sample Number
Figure B.I: Performance (SHD) tested on 100 nodes graph recovered from different sample numbers with gumbel noise.
ER2
ER5
SF2
SF5
CDCF-V+
30
150
20
EV-TD
SHD
20
100
10
50
10
50
200
300
400
500 600
200
300
400
500
600
200
300
400
500
600
200
300
400
500 600
2000
3000
2000
CDCF-V+
EV-HTD
SHD
2000
2000
1000
1000
1000
1000
20
100
100
100
20
40
80
100
Sample Number
Sample Number
Sample Number
Sample Number
Figure B.2: Performance (SHD) tested on 100 nodes graph recovered from different sample numbers with exponential noise.
Table B.1: SHD results on 100 nodes linear Gaussian noise SEM with low sample size.
20
40
60
80
100
V+
174.4
119.3
88.7
68.7
55.7
ER2
S+
173.4
120.4
92.2
71.2
57.4
VS+
174.7
126.6
99.8
75.1
70.7
V+
170.2
128.2
99.5
77.4
53.0
SF2
S+
170.1
129.2
99.8
79.5
52.1
VS+
168.8
133.6
103.6
83.6
52.9
V+ 427.0
356.9
284.2
223.6
194.4
ER5
S+
431.8
351.0
279.8
227.3
200.1
VS+
434.5
354.1
277.7
225.9
193.5
V+
412.6
330.0
269.2
218.2
169.5
SF5
409.8
332.9
266.8
215.3
167.1
VS+
409.5
337.7
270.9
220.5
173.5
18

---

Under review as a conference paper at ICLR 2022
Table B.2: SHD results on 100 nodes linear Gumbel noise SEM with low sample size.
40
60
80
100
V+
177.2
151.0
148.4
141.7
119.3
ER2
S+
174.8
140.5
130.6
130.2
111.7
VS+
229.0
256.2
293.5
258.2
223.3
V+
175.8
155.7
143.4
125.2
92.4
SF2
S+
171.8
144.0
125.8
102.7
78.9
VS+
202.2
208.7
187.1
152.5
100.3
V+ 437.3
372.1
340.1
286.3
242.0
ER5
S+
435.8
358.6
6
327.0
278.7
248.4
VS+
472.1
450.1
409.5
323.5
308.2
417.5
358.3
314.1
240.3
178.1
SF5
S+
414.2
349.8
292.0
217.8
160.0
VS+
443.9
424.0
342.9
258.2
181.0
Table B.3: SHD results on 100 nodes linear Exponential noise SEM with low sample size.
20
40
60
80
100
V+
171.1
132.1
104.8
90.2
80.5
ER2
S+
171.2
128.3
95.5
83.0
71.1
VS+
185.7
180.5
178.3
137.0
113.6
V+ 167.0
135.1
115.4
87.4
64.8
SF2
S+
168.4
130.2
107.5
79.1
60.1
VS+
170.7
165.0
131.3
100.4
67.0
V+
427.4
342.3
268.9
229.8
194.9
ER5
S+ 432.5
335.1
265.8
217.3
184.4
VS+
454.0
353.3
282.2
238.3
213.5
V+ 408.3
341.6
272.4
212.6
160.3
SF5
S+ 408.8
336.7
265.9
204.5
152.2
VS+
411.1
363.0
281.2
219.1
158.4
CDCF-V+
CDCF-S+
CDCF-VS+
15.0
800
700
700
700
12.5
d6 Jumber
500
500
500
10.0
400
400
400
300
300
300
7.5
200
200
200
150
150
150
100
100
100
2.5
30
30
30
2,
0.0
Sample Number(K)
Sample Number(K)
Sample Number(K)
Figure B.3: Performances (log SHD + 1)) of n as x-axis vs p as y-axis of CDCF-* on ER2 Gaussian noise.
19

---

Under review as a conference paper at ICLR 2022
Table B.4: SHD results on 100 nodes linear Gaussian SEM with different sample size.
200
300
400
500
600
700
800
900
1000
1500
2000
2500
3000
V
114.3
32.2
11.7
4.6
2.5
1.4
1.1
0.5
0.4
0.3
0.0
0.0
0.0
S
98.4
30.3
18.6
18.4
15.3
18.5
18.2
16.0
15.4
16.5
18.1
21.9
18.5
VS
141.6
38.7
32.3
6.1
8.0
12.5
2.5
8.6
0.6
0.3
1.2
0.0
1.0
ER2
V+
21.9
7.9
4.3
2.8
2.0
1.3
1.4
0.5
0.4
0.3
0.0
0.0
0.0
S+
29.1
17.6
13.5
17.2
14.6
16.3
18.5
16.3
15.3
16.5
18.1
21.8
18.5
VS+
38.6
16.0
21.3
3.0
4.3
10.4
2.1
8.1
0.4
0.3
0.8
0.0
0.9
V
37.1
7.2
1.9
2.6
0.9
0.3
0.1
0.1
0.2
0.0
0.0
0.0
0.0
S 27.3
7.5
6.9
3.8
4.2
4.9
3.9
3.3
3.6
5.3
5.7
3.4
4.8
VS
53.7
15.4
5.0
2.4
1.9
1.1
0.2
0.2
0.1
0.0
0.3
0.0
SF2
V+
8.8
3.0
1.6
0.7
1.1
0.5
0.2
0.2
0.1
0.0
0.0
0.0
0.0
S+ 11.7
4.8
7.3
3.6
4.8
5.0
4.0
3.3
4.4
5.3
5.7
3.4
4.8
VS+
10.8
4.1
2.1
0.6
1.3
0.4
1.6
0.2
0.1
0.1
0.0
0.3
0.0
368.7
139.6
73.8
33.2
21.5
14.0
9.5
7.0
5.8
1.5
0.6
0.0
0.0
S 349.0
139.0
81.2
45.7
40.7
27.6
22.1
22.7
24.7
17.6
14.0
19.1
18.0
VS
426.5
177.1
87.8
36.9
21.5
15.7
11.2
12.3
5.7
2.6
1.9
0.1
0.0
ERS
V+ 83.0
44.2
27.8
17.5
12.5
9.2
7.0
5.1
4.7
1.3
0.7
0.0
0.1
S+
95.4
56.3
40.4
30.2
32.9
23.4
19.7
18.1
22.6
17.3
13.5
19.3
18.0
VS+
88.6
47.0
27.9
18.0
11.5
8.0
7.1
5.4
1.7
2.2
0.0
0.1
V
92.6
31.9
12.6
6.0
4.9
3.9
2.5
1.8
1.6
0.3
0.4
0.0
0.0
81.2
32.1
21.8
13.4
16.9
13.5
12.6
12.3
11.4
10.1
8.9
12.3
11.6
VS
167.9
63.9
39.1
8.5
11.5
4.0
3.2
2.0
2.1
0.3
5.0
0.0
1.9
SF5
V+
40.3
21.0
15.6
8.3
7.2
5.3
4.1
2.3
2.8
0.5
0.4
0.0
0.0
S+
49.3
29.0
22.8
16.0
19.3
15.3
13.9
13.1
12.8
11.8
8.9
12.4
11.6
VS+
47.6
23.2
16.4
9.1
7.4
5.6
4.5
2.5
3.3
0.5
4.9
0.0
1.9
Table B.5: SHD results on 100 nodes linear Gumbel noise SEM with different sample size.
200
300
400
500
600
700
800
900
1000
1500
2000
2500
3000
124.7
35.1
11.8
6.5
3.6
2.2
0.8
0.6
0.9
0.4
0.0
0.1
0.0
94.2
39.8
22.3
18.2
15.7
15.4
17.4
15.7
19.7
18.0
18.6
20.9
22.3
VS
145.1
55.6
20.2
10.6
22.9
5.4
12.4
3.2
1.9
0.2
0.3
7.2
1.1
ER2
V+
39.8
15.6
7.3
4.0
3.0
1.5
1.2
0.5
0.9
0.0
0.1
0.0
S+ 38.5
28.1
19.7
16.2
16.1
14.8
19.1
15.7
20.3
17.7
19.7
21.0
22.3
VS+
68.4
30.0
13.6
6.5
17.1
4.3
12.3
0.8
1.1
0.4
0.5
7.1
1.1
V 46.9
8.6
1.9
0.8
0.6
0.3
0.2
0.3
0.1
0.0
0.0
0.0
0.0
S 27.7
11.3
3.5
5.4
3.7
3.3
2.9
4.0
4.8
5.6
5.6
5.3
5.5
VS
58.4
24.6
3.4
3.4
1.1
1.4
0.2
1.3
1.1
0.1
0.1
0.4
0.0
SF2
V+ 12.0
4.5
1.5
0.8
0.6
0.3
0.2
0.4
0.1
0.0
0.0
0.0
0.0
12.8
8.4
5.3
3.6
3.4
2.8
4.2
4.7
5.6
5.6
5.3
5.5
VS+
14.7
7.2
3.9
1.4
1.2
1.5
0.2
0.8
3.1
0.1
0.1
0.4
0.0
362.8
139.7
70.9
40.2
23.2
17.4
9.6
5.9
6.1
1.6
0.4
0.3
0.1
S 338.2
138.0
84.0
53.2
37.7
31.5
21.3
28.0
21.2
16.8
16.1
19.5
16.6
VS
448.6
199.8
93.9
58.3
26.3
21.8
13.7
44.1
22.3
1.3
0.8
0.8
3.8
ER5
V+ 119.1
64.7
35.9
21.6
13.3
10.7
6.8
5.5
4.7
1.5
0.5
0.3
0.1
S+ 128.2
72.7
49.3
36.4
28.5
27.3
19.2
24.9
18.8
17.2
16.1
17.5
16.4
VS+
133.6
82.8
37.3
29.0
14.6
14.0
6.9
41.4
20.6
1.4
0.7
0.7
3.6
V
104.4
31.9
12.0
7.6
5.2
2.9
2.4
2.1
2.7
0.5
0.2
0.1
0.0
82.8
32.2
20.3
14.6
14.5
10.7
11.7
12.3
9.4
10.3
13.5
11.2
11.1
VS
177.6
95.0
31.1
21.4
12.4
5.5
4.5
7.9
20.3
0.6
0.5
0.1
0.0
SF5
V+
47.2
20.2
11.0
8.1
5.8
3.6
3.3
2.2
1.9
0.5
0.3
0.1
0.0
S+
45.9
26.3
20.0
15.6
16.0
11.7
12.9
12.6
10.4
11.8
13.6
11.3
11.1
VS+
48.3
23.4
17.9
8.8
6.8
5.6
4.6
4.9
8.3
0.8
0.6
0.1
0.0
20

---

Under review as a conference paper at ICLR 2022
Table B.6: SHD results on
100 nodes linear Exponential noise SEM with different sample size.
200
300
400
500
600
700
800
900
1000
1500
2000
2500
3000
132. 1
39.0
15.3
5.9
3.7
2.5
1.3
0.6
0.7
0.2
0.0
0.2
0.0
S
106.8
34.4
20.3
16.4
15.0
17.7
13.9
20.5
19.0
19.9
15.3
23.5
22.2
VS
138.0
53.8
23.6
12.4
6.1
3.5
4.5
5.5
14.1
3.7
0.4
0.2
ER2
V+
31.8
10.7
7.5
3.4
2.0
2.5
1.2
0.8
0.7
0.2
0.0
0.2
0.0
S+
34.0
20.2
17.2
15.9
13.7
16.2
13.8
19.7
19.2
20.0
15.3
22.8
22.1
VS+
44.1
22.1
12.8
6.7
3.7
2.8
3.8
5.6
13.2
0.3
4.0
0.6
0.4
55.4
17.0
5.1
2.5
0.5
1.6
0.9
0.1
0.3
0.0
0.0
0.0
0.0
33.9
11.4
4.3
6.0
4.7
6.1
4.4
4.2
4.3
4.1
4.1
4.9
5.7
VS
67.5
16.2
8.9
5.0
1.5
1.0
0.6
0.7
0.3
0.1
0.7
0.0
0.0
SF2
V+
12.1
3.5
3.0
0.8
0.8
0.5
0.9
0.1
0.2
0.1
0.0
0.0
0.0
S+
14.4
10.5
4.3
5.8
5.0
6.1
4.4
5.0
4.3
4.1
4.1
4.9
5.6
VS+
17.2
5.6
3.8
2.7
2.2
1.0
0.6
0.2
0.2
0.7
0.0
0.0
V
393.8
157.8
75.7
40.5
29.6
18.4
10.2
8.9
5.2
1.6
0.9
0.2
0.0
361.2
154.7
80.5
51.2
44.3
34.6
28.3
19.3
24.3
16.2
16.8
18.1
15.7
VS 474.7
193.9
110.3
62.5
35.6
32.1
20.0
26.4
51.6
2.5
1.3
12.0
3.1
ER5
V+
96.6
56.6
32.2
19.6
15.3
12.8
8.1
7.1
5.1
1.4
1.1
0.1
0.0
S+ 95.8
66.9
41.4
33.2
32.0
27.2
23.2
20.1
21.0
14.4
16.6
19.7
14.4
VS+
103.8
55.8
40.0
26.1
15.8
15.5
10.6
19.3
48.1
2.0
1.0
7.3
3.1
108.9
34.9
23.1
7.5
11.6
3.2
2.7
1.6
0.6
0.6
0.0
0.0
84.8
34.8
21.7
13.5
16.6
11.4
13.0
12.2
8.8
11.6
12.2
8.8
11.3
203.5
80.3
35.2
11.0
5.4
10.4
9.6
3.4
0.6
0.7
4.6
2.3
0.0
SF5
V+
51.0
27.9
15.5
9.1
7.1
4.7
4.8
2.6
2.4
1.2
0.2
0.0
0.0
S+
54.4
34.0
24.8
16.3
19.5
12.3
15.4
13.1
11.0
12.1
12.3
8.8
11.3
VS+
56.9
26.3
17.2
10.5
7.2
5.5
8.1
3.5
2.4
1.1
4.7
2.0
0.0
CDCF-V
CDCF-S
CDCF-VS
800
800
800
700
700
700
12.5
Node Number
600
600
600
500
500
500
10.0
300
300
300
7.5
200
200
200
150
150
150
5.0
100
100
100
50
50
50
2.5
30
30
30
0,30
0.0
Sample Number(K)
Sample Numberlk)
Sample NumberlK)
Figure B.4: Performance (log(SHD+ 1)) upper bound of CDCF. on ER2 Gaussian.
CDCF-V
CDCF-S
CDCF-VS
15.0
700
700
700
600
600
600
Noda Number
500
500
500
10.0
400
400
400
300
7.5
200
200
200
150
150
150
5.0
50
50
50
2.5
30
30
30
9999999999999
9,999,99999
Sample Number(K)
Sample Numberik)
Sample NumberiK)
Figure B.5: Performance (log(SHD + 1)) upper bound of CDCF. on SF2 Gaussian.
21

---

Under review as a conference paper at ICLR 2022
CDCF-V+
CDCF-S+
CDCF-VS+
15.0
800
700
700
700
12.5
500
500
500
10.0
400
400
400
7.5
200
200
200
150
5.0
100
50
50
50
2.5
30
86 37 6606699
9,99
Sample Number(K)
Sample Number(K)
Sample Number(K)
Figure B.6: Performance (log(SHD + 1)) upper bound of CDCF on SF2 Gaussian.
CDCF-V
CDCF-S
CDCF-VS
15.0
800
800
800
700
12.5
600
600
600
Lode Num Sum
10.0
400
400
400
300
300
300
150
150
150
5.0
100
100
100
50
50
50
30
30
30
0.0
6
6. 3.33
Sample Numberik)
Sample Numberik)
Sample Number(K)
Figure B.7: Performance (log(SHD 1)) upper bound of CDCFL* on ER2 Exponential.
CDCF-V+
CDCF-S+
CDCF-VS+
800
800
800
700
700
12.5
Rode Number
600
600
600
500
500
500
300
300
300
7.5
200
200
200
5.0
100
100
100
50
50
50
2.5
30
30
30
3,030
0.0
Sample Number(K)
Sample Number(K)
Sample Number(K)
Figure B.8: Performance (log(SHD + 1)) upper bound of CDCF on ER2 Exponential.
22

---

Under review as a conference paper at ICLR 2022
CDCF-V
CDCF-S
CDCF-VS
15.0
800
800
800
700
700
700
12.5
Numr be
600
600
500
500
500
10.0
400
400
400
7.5
200
200
200
150
150
150
5.0
100
100
100
50
50
50
2.5
30
30
30
Sample NumberlK)
Sample NumberlK)
Sample Number(K)
Figure B.9: Performance (log(SHD + 1)) upper bound of CDCF_* on SF2 Exponential.
CDCF-V+
CDCF-S+
CDCF-VS+
15.0
800
800
800
700
12.5
600
600
600
Lode Num Sum
10.0
400
400
400
300
300
300
150
150
150
5.0
100
100
100
50
50
30
30
30
0.0
6 6.333
Sample Numberik)
Sample Numberik)
Sample Number(K)
Figure B.10: Performance (log(SHD 1)) upper bound of CDCFL* on SF2 Exponential.
CDCF-V
CDCF-S
CDCF-VS
800
800
800
700
700
12.5
Rode Numbet
600
600
600
500
500
500
300
300
300
7.5
200
200
200
5.0
100
100
100
50
50
50
2.5
30
30
30
0.0
Sample Number(K)
Sample Number(K)
Sample Number(K)
Figure B.1.: Performance (log(SHD + 1)) upper bound of CDCF on ER2 Gumbel.
23

---

Under review as a conference paper at ICLR 2022
CDCF-V+
CDCF-S+
CDCF-VS+
15.0
800
800
800
700
700
700
12.5
Number
600
600
500
500
500
10.0
400
400
400
7.5
200
200
200
150
150
150
5.0
100
100
100
50
50
50
2.5
30
30
30
1
Sample NumberlK)
Sample NumberlK)
Sample Number(K)
Figure 1.12: Performance (log(SHD + 1)) upper bound of CDCF- *+ on ER2 Gumbel.
CDCF-V
CDCF-S
CDCF-VS
15.0
800
800
800
700
12.5
600
600
600
Lode Numbe
10.0
400
400
400
300
300
300
150
150
150
5.0
100
100
100
50
50
50
30
30
30
6 6.333333 9
6. 9.3333333333
0.0
Sample Numberik)
Sample Numberik)
Sample Number(K)
Figure B.13: Performance (log(SHD 1)) upper bound of CDCFL$ SF2 Gumbel.
CDCF-V+
CDCF-S+
CDCF-VS+
800
800
800
700
700
12.5
Rode Number
600
600
600
500
500
500
300
300
300
7.5
200
200
200
5.0
100
100
100
50
50
50
2.5
30
30
30
0000000
3,030
0.0
Sample Number(K)
Sample Number(K)
Sample Number(K)
Figure B. 14: Performance (log(SHD 1)) upper bound of CDCF on SF2 Gumbel.
24

---

Under review as a conference paper at ICLR 2022
Table B.7: CDCF-V4 SHD results on different y with different sample size on 100 nodes linear
Gaussian SEM.
CDCF-V+
200
300
400
500
600
700
800
900
1000
1500
2000
2500
3000
Y = 0.0
114.3
32.2
11.7
4.6
2.5
1.4
1.1
0.5
0.4
0.3
0.0
0.0
0.0
7 = 1.0
21.9
7.9
4.3
2.8
2.0
1.3
1.4
0.5
0.4
0.3
0.0
0.0
0.0
Y 2.0
13.6
7.2
4.0
2.9
2.1
1.7
1.4
0.9
0.7
0.3
0.0
0.0
0.0
Y = 3.0
14.8
8.1
4.5
3.5
2.7
2.0
1.8
1.4
0.7
0.3
0.0
0.0
0.0
7 4.0
18.3
9.9
7.2
4.9
3.1
3.0
2.3
1.4
0.8
0.6
0.0
0.0
0.0
ER2
Y = 5.0
23.0
12.3
9.3
6.5
4.1
3.8
2.4
1.6
1.0
0.8
0.1
0.0
0.0
7 6.0
27.0
14.9
11.4
7.7
4.5
4.4
3.6
1.9
1.7
0.8
0.1
0.1
0.0
7 7.0
33.0
19.1
13.7
9.1
6.0
4.9
4.3
2.5
2.4
0.9
0.2
0.1
0.0
7 8.0
37.3
22.1
15.5
10.2
7.0
5.7
5.1
2.9
3.1
1.2
0.2
0.1
0.0
7 9.0
42.5
25.1
17.6
11.6
8.6
6.9
5.8
3.6
3.4
1.2
0.2
0.1
0.1
7 10.0
46.7
27.4
20.0
12.8
10.0
7.5
6.6
4.5
3.7
1.3
0.3
0.1
0.1
Y = 0.0
37.1
7.2
1.9
2.6
0.9
0.3
0.1
0.1
0.2
0.0
0.0
0.0
0.0
7 = 1.0
8.8
3.0
1.6
0.7
1.1
0.5
0.2
0.2
0.1
0.0
0.0
0.0
0.0
7 2.0
9.7
4.2
2.2
0.9
1.2
0.5
0.2
0.1
0.1
0.0
0.0
0.0
0.0
Y = 3.0
11.5
6.2
2.9
1.4
1.2
0.4
0.3
0.1
0.1
0.0
0.0
0.0
0.0
Y 4.0
15.4
7.5
3.5
1.8
1.6
0.8
0.4
0.3
0.2
0.0
0.0
0.0
0.0
SF2
7 5.0
18.1
8.9
4.3
2.7
2.1
1.3
0.5
0.5
0.4
0.0
0.0
0.0
0.0
7 6.0
20.9
10.8
5.4
3.3
2.5
1.7
0.8
1.0
0.6
0.0
0.0
0.0
0.0
7 = 7.0
23.5
13.1
6.7
5.2
4.9
2.7
1.5
1.3
0.7
0.0
0.0
0.0
0.0
Y 8.0
27.0
14.8
8.1
5.8
6.0
2.9
2.2
1.5
0.7
0.0
0.0
0.0
0.0
7 = 9.0
29.4
16.8
9.8
6.7
6.7
3.5
2.7
2.0
1.1
0.0
0.0
0.0
0.0
7 10.0
32.0
19.0
11.5
7.7
4.1
3.0
2.3
1.5
0.1
0.0
0.0
0.0
Y 0.0
368.7
L39.6
73.8
33.2
21.5
14.0
9.5
7.0
5.8
1.5
0.6
0.0
0.0
Y = 1.0
83.0
44.2
27.8
17.5
12.5
9.2
7.0
5.1
4.7
1.3
0.7
0.0
0.1
Y 2.0
74.1
41.7
26.2
19.8
13.4
10.7
8.4
6.6
5.7
1.3
1.1
0.0
0.3
7 3.0
82.1
52.3
33.1
23.0
18.2
14.5
11.9
8.0
7.2
2.4
1.6
0.2
0.4
7 4.0
94.8
62.1
40.1
28.6
23.9
18.1
14.3
10.3
10.3
3.9
2.1
0.4
0.3
ER5
Y = 5.0
109.7
72.3
51.4
37.6
30.1
122.617.66
14.1
12.8
5.6
2.6
0.8
0.4
7 6.0
123.3
84.2
57.9
47.8
34.7
21.2
17.4
15.4
6.7
3.2
0.9
0.5
7 = 7.0
140.3
100.2
67.9
53.1
39.9
31.2
20.2
18.2
7.8
3.7
1.0
0.7
Y 8.0
152.7
113.0
74.8
61.5
47.5
36.4
23.5
22.3
4.4
1.4
0.9
Y 9.0
162.5
122.0
83.1
67.7
51.6
34.6
28.5
25.7
10.7
4.9
1.9
1.4
7 10.0
175.5
130.2
92.6
73.8
59.0
37.7
33.2
28.7
12.5
5.7
2.4
1.8
Y 0.0
92.6
31.9
12.6
6.0
4.9
3.9
2.5
1.8
1.6
0.3
0.4
0.0
0.0
7 = 1.0
40.3
21.0
15.6
8.3
7.2
5.3
4.1
2.3
2.8
0.5
0.4
0.0
0.0
7 2.0
57.2
35.7
23.3
16.1
11.2
9.6
7.5
5.9
5.1
1.7
0.6
0.0
0.0
7 = 3.0
69.8
46.2
31.3
23.6
16.9
12.5
11.2
8.6
7.0
2.8
1.4
0.0
0.1
7 4.0
80.9
53.1
38.7
30.4
21.1
17.9
14.5
11.9
8.4
4.2
2.1
0.9
0.2
SF5
7 = 5.0
90.6
66.3
43.7
36.3
25.8
24.5
20.3
16.6
12.1
5.7
3.3
1.6
0.4
γ 6.0
103.3
73.3
49.1
42.3
34.6
28.1
25.5
19.7
14.4
8.3
4.0
2.4
1.5
7 = 7.0
110.3
79.4
55.9
45.6
38.0
31.6
29.1
24.6
19.9
10.3
5.1
3.6
2.1
7 = 8.0
118.4
86.1
63.6
50.2
41.3
35.7
33.5
27.6
21.4
12.6
5.8
4.3
2.5
7 9.0
124.0
92.8
68.7
54.1
46.5
39.4
36.3
30.2
25.0
13.9
7.2
4.7
3.2
7 = 10.0
129.5
98.6
74.3
57.8
49.6
42.2
39.3
32.6
27.1
17.5
7.7
5.9
4.0
25

---

Under review as a conference paper at ICLR 2022
Table B.8: CDCF-S+ SHD results on different with different sample size on 100 nodes linear
Gaussian SEM.
CDCT-S+
200
300
400
500
600
700
800
900
1000
1500
2000
2500
3000
0.0
98.4
30.3
18.6
18.4
15.3
18.5
18.2
16.0
15.4
16.5
18.1
21.9
18.5
= 1.0
29.1
17.6
13.5
17.2
14.6
16.3
18.5
16.3
15.3
16.5
18.1
21.8
18.5
2.0
22.8
16.8
13.0
17.4
15.3
17.0
18.0
16.4
15.4
16.6
18.2
22.3
18.5
3.0
= 3.0
26.9
18.4
15.6
17.9
15.6
18.0
18.4
16.1
16.8
17.4
18.1
21.6
18.4
4.0
32.5
21.6
17.5
18.1
15.9
19.2
19.0
15.9
17.1
17.7
18.3
22.1
18.4
ER2
= 5.0
36.1
23.9
18.8
19.1
16.5
20.6
19.5
15.9
17.0
17.6
18.1
22.3
18.6
7 6.0
39.8
26.4
20.6
21.6
17.9
21.6
20.2
16.8
17.4
17.8
18.6
22.2
18.6
7.0
43.9
28.8
22.9
22.4
19.4
22.0
21.1
17.4
19.3
18.4
18.6
22.2
18.4
8.0
48.3
32.5
24.9
25.0
19.7
22.1
22.0
18.6
19.5
18.4
19.1
21.8
18.3
9.0
52.1
34.3
27.5
25.5
20.8
22.7
23.2
19.1
20.5
18.7
18.7
21.8
18.3
7 10.0
56.1
37.7
29.7
26.4
22.2
23.3
24.1
19.7
20.5
18.7
18.8
22.5
19.0
0.0
27.3
7.5
6.9
3.8
4.2
4.9
3.9
3.3
3.6
5.3
5.7
3.4
4.8
= 1.0
11.7
4.8
7.3
3.6
4.8
5.0
4.0
3.3
4.4
5.3
5.7
3.4
4.8
2.0
13.6
5.8
8.0
4.6
5.0
5.2
3.9
3.8
4.3
5.2
5.7
3.4
4.8
3.0
14.8
6.9
7.9
4.5
5.2
5.3
4.0
3.8
4.3
5.2
5.7
3.4
4.9
SF2 4.0
17.9
8.5
8.3
5.4
6.1
5.5
4.2
4.0
4.3
5.2
5.7
3.4
4.9
5.0
20.4
9.8
9.0
6.4
6.6
5.9
4.3
3.9
5.1
5.3
5.6
3.4
4.9
6.0
24.0
11.3
10.3
7.0
6.9
6.4
4.4
4.4
5.9
5.3
5.6
3.4
4.9
7.0
26.8
13.4
11.6
7.4
7.6
6.6
5.1
5.7
6.2
5.3
5.6
3.4
4.8
7 8.0
29.9
15.0
12.3
7.9
8.5
6.8
5.8
5.9
6.2
5.3
5.6
3.4
4.8
9.0
31.9
17.2
14.0
9.2
10.3
7.5
6.3
6.4
6.5
5.3
5.6
3.4
4.8
7 10.0
34.2
19.4
15.4
9.9
11.5
8.0
7.0
6.5
7.1
5.4
5.6
4.8
0.0
349.0
139.0
81.2
45.7
40.7
27.6
22.1
22.7
24.7
17.6
14.0
19.1
18.0
= 1.0
95.4
56.3
40.4
30.2
32.9
23.4
19.7
18.1
22.6
17.3
13.5
19.3
18.0
2.0
86.1
55.9
40.8
38.6
34.0
23.5
21.6
20.2
24.7
17.3
14.8
19.1
18.2
3.0
94.2
66.0
49.6
42.9
40.4
29.4
25.5
25.6
25.5
18.1
16.1
19.3
18.2
4.0
105.8
77.2
57.8
48.0
47.5
33.7
29.2
27.1
28.0
21.8
16.9
20.2
18.1
ER5
5.0
119.9
89.8
64.9
56.1
48.1
38.5
33.1
31.9
31.2
23.3
17.9
20.5
18.2
7 6.0
132.9
100.3
74.0
64.9
53.8
44.5
39.1
35.3
36.0
24.7
19.1
20.8
19.2
7.0
147.3
110.8
80.5
71.3
57.5
49.7
42.7
40.4
39.3
26.5
22.1
25.7
20.2
8.0
159.9
121.1
88.9
77.1
64.8
54.9
46.7
44.0
42.1
29.0
23.0
26.0
20.5
9.0
171.5
129.4
98.2
83.3
69.3
60.9
50.0
48.3
45.0
30.6
23.4
26.8
21.6
7 = 10.0
185.9
138.5
105.0
87.6
73.9
64.7
54.8
52.2
48.5
31.9
23.9
27.1
23.5
0.0
81.2
32.1
21.8
13.4
16.9
13.5
12.6
12.3
11.4
10.1
8.9
12.3
11.6
1.0
49.3
29.0
22.8
16.0
19.3
15.3
13.9
13.1
12.8
11.8
8.9
12.4
11.6
7 2.0
59.6
38.5
29.3
22.3
23.1
19.5
17.5
16.9
15.4
13.2
9.3
12.1
11.6
3.0
73.4
48.9
35.9
28.2
27.6
22.3
20.6
19.6
17.5
14.3
10.5
12.1
11.7
4.0
82.7
55.6
42.9
34.1
31.4
26.3
24.2
23.6
19.0
15.6
11.2
11.7
11.9
SF5
5.0
93.2
65.0
48.2
39.2
36.2
30.3
27.4
26.6
21.2
17.0
12.4
12.4
12.1
7 6.0
102.7
71.7
53.3
44.9
41.0
34.0
30.4
28.4
23.5
18.3
14.1
13.2
13.3
7.0
109.3
78.0
60.7
48.4
44.4
37.8
33.9
32.0
25.6
20.3
16.6
14.4
13.9
= 8.0
117.5
84.3
67.3
53.3
48.6
40.7
36.7
34.9
27.0
21.1
17.4
15.1
14.3
9.0
123.2
90.9
72.2
56.9
51.6
44.2
40.4
37.5
31.0
22.4
18.8
15.6
15.0
7 = 10.0
129.8
95.9
77.6
61.0
54.4
46.9
43.4
39.8
33.2
24.0
19.4
16.8
15.8
26

---

Under review as a conference paper at ICLR 2022
Table B.9: CDCF- SHD results on different with different sample size on 100 nodes linear
Gaussian SEM.
CDCF-VS+
200
300
400
500
600
700
800
900
1000
1500
2000
2500
3000
Y 0.0
141.6
38.7
32.3
6.1
8.0
12.5
2.5
8.6
0.6
0.3
1.2
0.0
1.0
7 = 1.0
38.6
16.0
21.3
4.3
10.4
2.1
0.4
0.3
0.8
0.0
0.9
7 2.0
18.4
9.6
16.5
3.3
3.6
13.0
2.4
8.1
0.7
0.5
0.0
0.0
0.9
Y = 3.0
19.4
11.2
5.6
4.5
4.2
2.3
2.0
1.4
1.0
0.5
0.9
0.0
0.9
7 = 4.0
21.3
12.2
7.5
5.3
4.2
2.8
2.3
1.5
1.8
0.6
0.7
0.0
0.9
ER2
Y = 5.0
27.5
16.7
10.7
7.3
5.9
3.9
3.8
1.7
1.9
0.9
0.7
0.0
0.9
7 6.0
31.9
16.7
12.3
8.1
6.0
14.5
5.1
1.9
2.1
0.9
0.7
0.1
0.9
7 7.0
35.3
19.8
24.3
10.1
8.4
6.0
6.2
2.6
2.4
1.0
0.8
0.1
0.9
7 8.0
39.7
23.9
25.6
11.5
8.8
12.2
7.6
3.2
2.9
1.1
0.8
0.1
0.9
7 9.0
44.4
26.1
18.2
12.9
11.0
8.5
7.9
3.5
3.4
1.1
0.8
0.1
0.9
7 10.0
48.9
30.3
19.9
13.8
12.7
8.9
8.6
4.6
4.0
1.3
0.9
0.1
1.0
Y = 0.0
53.7
15.4
5.0
2.4
1.9
1.3
1.1
0.2
0.2
0.1
0.0
0.3
0.0
Y = 1.0
10.8
4.1
2.1
0.6
1.3
0.4
1.6
0.2
0.1
0.1
0.0
0.3
0.0
7 2.0
11.4
4.1
2.6
0.8
1.3
0.5
1.5
0.1
0.1
0.1
0.0
0.3
0.0
Y = 3.0
12.2
5.4
3.0
1.4
1.7
0.4
1.4
0.1
0.1
0.0
0.0
0.3
0.0
Y = 4.0
15.5
6.8
3.5
1.9
2.2
0.8
1.5
0.3
0.2
0.0
0.0
0.3
0.0
SF2
7 5.0
18.6
8.9
4.5
2.8
2.7
1.4
1.6
0.5
0.4
0.0
0.0
0.3
0.0
7 6.0
20.8
10.9
5.9
3.3
3.5
1.8
1.8
1.0
0.5
0.0
0.0
0.3
0.0
7 = 7.0
23.5
13.1
7.7
4.9
4.5
3.0
2.4
1.3
0.6
0.0
0.0
0.3
0.0
Y 8.0
27.6
14.7
9.0
5.4
6.3
3.2
3.0
1.5
0.6
0.0
0.0
0.3
0.0
9.0
30.1
16.9
10.7
7.0
6.8
3.7
3.5
2.0
0.9
0.0
0.0
0.3
0.0
7 10.0
32.3
19.2
13.2
7.8
4.1
3.9
2.3
1.5
0.1
0.0
0.3
0.0
T 0.0
426.5
177.
87.8
36.9
21.5
15.7
11.2
12.3
5.7
2.6
1.9
0.1
0.0
Y = 1.0
88.6
47.0
27.9
18.0
11.5
9.2
8.0
7.1
5.4
1.7
2.2
0.0
0.1
Y 2.0
73.2
44.2
26.6
20.9
13.7
10.9
10.0
8.1
6.6
2.4
2.1
0.1
0.3
7 3.0
83.6
54.4
33.7
23.4
19.0
15.0
12.4
9.7
9.1
3.3
3.5
0.2
0.4
7 4.0
94.6
63.9
43.7
31.4
24.7
18.8
15.9
12.0
11.7
4.5
4.4
0.6
0.4
ER5
Y = 5.0
110.5 75.8
51.7
39.7
31.4
24.0
19.6
16.0
13.5
6.5
4.7
1.2
0.4
7 6.0
124.9
90.0
60.2
48.0
36.4
28.7
22.7
19.1
16.5
7.9
6.2
1.3
0.4
7 = 7.0
139.1 100.4
68.2
56.9
42.1
34.4
22.6
22.6
18.8
9.7
6.9
1.4
0.7
Y 8.0
152.8
110.3
77.5
65.2
53.2
39.0
31.3
23.4
7.3
1.8
0.9
Y = 9.0
164.8 117.9
86.0
72.0
58.0
43.3
35.1
32.1
26.8
12.7
8.1
2.4
1.4
7 = 10.0
175.3 127.9
97.0
76.6
63.9
49.2
40.7
36.4
30.3
14.4
8.8
2.8
2.3
Y 0.0
167.9
63.9
39.1
8.5
11.5
4.0
3.2
2.0
2.1
0.3
5.0
0.0
1.9
7 = 1.0
47.6
23.2
16.4
9.1
7.4
5.6
4.5
2.5
3.3
0.5
4.9
0.0
1.9
7 2.0
58.3
37.0
25.7
17.7
12.8
12.8
7.8
6.2
5.6
1.7
5.1
0.0
1.9
7 = 3.0
72.0
46.1
32.1
25.4
17.2
15.6
14.2
11.6
8.9
4.1
6.1
0.0
0.1
7 4.0
82.5
53.2
38.4
31.0
24.8
21.0
17.5
16.6
13.4
5.5
6.4
0.9
2.1
SF5
γ = 5.0
91.2
62.5
45.1
36.4
29.6
24.5
22.7
19.4
15.6
8.7
7.5
1.6
2.3
Y 6.0
101.7 69.6
50.5
42.2
35.0
28.2
25.4
21.3
18.0
11.9
8.2
2.4
3.4
7 = 7.0
109.1 75.9
57.7
45.7
38.6
33.2
30.6
25.0
20.1
13.8
12.1
5.4
2.1
7 = 8.0
116.9 82.8
64.0
50.3
41.9
36.0
33.5
21.6
14.6
14.9
6.1
2.5
7 9.0
122.2
89.1
68.7
54.2
45.0
39.6
36.3
30.4
25.2
15.8
12.1
7.8
4.5
7 = 10.0
128.6 94.1
74.8
58.0
49.5
42.8
39.3
32.9
27.3
17.6
12.6
11.1
7.1
27

---

Under review as a conference paper at ICLR 2022
Table B.10: CDCF-V+ SHD results on different with different sample size on 100 nodes linear
Gumbel SEM.
CDCF-V+
200
300
400
500
600
700
800
900
1000
1500
2000
2500
3000
Y = 0.0
124.7
35.1
11.8
6.5
3.6
2.2
0.8
0.6
0.9
0.4
0.0
0.1
0.0
7 = 1.0
39.8
15.6
7.3
4.0
3.0
1.5
1.2
0.5
0.9
0.0
0.1
0.0
7 2.0
19.7
9.9
5.6
2.9
1.6
1.2
1.7
0.7
0.9
0.4
0.0
0.1
0.0
Y = 3.0
15.3
7.7
4.9
3.0
1.6
1.3
1.6
0.8
1.0
0.4
0.0
0.1
0.0
7 4.0
14.7
8.8
4.7
3.4
2.0
1.5
1.7
0.9
1.3
0.5
0.0
0.1
0.0
ER2
? = 5.0
17.7
10.0
5.7
4.1
2.2
1.7
2.0
1.1
1.5
0.5
0.0
0.1
0.0
7 6.0
19.6
12.5
6.9
4.5
3.0
2.0
2.3
1.3
1.7
0.5
0.0
0.1
0.0
7 7.0
21.9
13.8
7.8
5.7
3.0
2.7
2.4
1.5
1.7
0.5
0.1
0.1
0.0
7 8.0
24.9
14.8
9.2
6.5
4.0
3.2
3.0
2.0
2.0
0.6
0.2
0.2
0.0
7 9.0
27.5
16.4
9.9
7.7
4.3
3.8
3.1
2.2
2.4
0.6
0.1
0.2
0.0
7 10.0
30.9
17.6
11.2
8.7
4.5
4.2
3.3
2.9
3.1
0.8
0.1
0.2
0.0
Y = 0.0
46.9
8.6
1.9
0.8
0.6
0.3
0.2
0.3
0.1
0.0
0.0
0.0
0.0
7 = 1.0
12.0
4.5
1.5
0.8
0.6
0.3
0.2
0.4
0.1
0.0
0.0
0.0
0.0
7 2.0
9.5
4.3
1.5
1.1
0.6
0.4
0.2
0.5
0.1
0.0
0.0
0.0
0.0
Y = 3.0
9.8
4.3
1.8
1.4
1.7
0.6
0.2
0.7
0.1
0.0
0.0
0.0
0.0
Y 4.0
11.9
5.2
2.1
1.8
1.8
1.1
0.2
0.7
0.1
0.0
0.0
0.0
0.0
SF2
7 = 5.0
14.3
6.1
2.4
2.0
1.6
1.4
0.2
0.8
0.2
0.0
0.0
0.0
0.0
7 6.0
15.8
7.1
3.4
2.3
2.4
1.4
0.2
0.8
0.2
0.0
0.0
0.0
0.0
7 = 7.0
18.5
8.0
4.9
2.8
2.5
1.7
0.6
0.9
0.2
0.0
0.0
0.0
0.0
Y 8.0
20.9
9.4
5.4
2.8
2.9
1.8
0.8
1.1
0.2
0.0
0.0
0.0
0.0
7 = 9.0
22.9
11.6
6.4
3.4
3.0
2.0
1.0
1.3
0.3
0.0
0.0
0.0
0.0
7 10.0
24.3
13.3
6.6
3.8
3.3
2.5
1.3
1.4
0.4
0.0
0.0
0.0
Y 0.0
362.8
L39.7
70.9
40.2
23.2
17.4
9.6
5.9
6.1
1.6
0.4
0.3
0.1
Y = 1.0
119.1
64.7
35.9
21.6
13.3
10.7
6.8
5.5
4.7
1.5
0.5
0.3
0.1
Y 2.0
79.5
48.5
27.3
19.6
12.2
9.7
6.9
5.4
5.2
1.2
0.3
0.3
0.2
7 3.0
74.8
46.3
29.1
20.2
12.7
11.4
8.0
6.2
6.3
1.4
0.4
0.4
0.2
7 4.0
79.6
46.8
31.9
23.3
14.9
13.0
9.3
7.9
7.0
1.5
0.7
0.5
0.3
ER5
Y = 5.0
87.2
53.0
35.5
26.0
17.2
15.5
11.0
9.3
8.7
2.5
0.9
0.6
0.2
7 6.0
99.5
60.6
39.4
31.8
20.3
17.5
14.3
10.9
10.1
2.9
1.1
0.5
0.2
7 = 7.0
107.4
72.0
46.0
35.7
24.9
19.7
16.7
12.5
11.8
3.5
1.5
0.5
0.2
Y 8.0
116.3
78.7
51.8
39.0
30.4
18.7
15.2
13.9
4.3
2.0
0.8
0.3
Y 9.0
124.9
85.5
57.1
43.0
33.0
26.2
20.6
16.8
15.4
5.2
2.6
0.9
0.4
7 10.0
135.3
91.9
64.5
46.8
35.9
30.1
22.9
19.5
17.5
3.3
0.5
Y 0.0
104.4
31.9
12.0
7.6
5.2
2.9
2.4
2.1
2.7
0.5
0.2
0.1
0.0
7 = 1.0
47.2
20.2
11.0
8.1
5.8
3.6
3.3
2.2
1.9
0.5
0.3
0.1
0.0
7 2.0
51.7
25.5
14.3
11.9
7.7
5.4
5.0
3.6
3.8
1.2
0.4
0.1
0.0
7 = 3.0
58.4
30.3
20.0
14.8
10.4
8.4
7.1
5.3
5.3
1.4
0.6
0.1
0.0
7 4.0
65.9
38.1
26.5
19.9
14.9
10.2
8.9
6.5
6.0
2.4
0.9
0.3
0.0
SF5
7 = 5.0
72.4
44.1
31.6
24.8
17.7
13.3
11.0
9.2
7.2
2.8
1.4
0.6
0.0
Y 6.0
78.3
49.0
37.1
27.2
20.8
15.9
14.3
10.7
9.0
3.6
1.9
0.9
0.0
7 = 7.0
84.8
55.2
42.1
32.8
25.0
18.3
16.1
13.3
10.1
4.5
2.7
1.5
0.3
7 = 8.0
90.7
60.7
45.9
35.0
27.3
22.8
17.6
14.8
11.9
5.5
3.4
1.7
0.7
7 9.0
97.9
64.7
49.6
38.1
31.3
25.1
19.8
16.3
14.4
6.8
3.9
2.6
0.8
7 = 10.0
103.4
68.2
53.3
40.8
33.9
27.5
23.8
17.9
15.4
7.7
4.4
3.3
1.4
28

---

Under review as a conference paper at ICLR 2022
Table B.11: SHD results on 100 nodes linear monotonous Gaussian noise variance SEM with different sample size.
200
300
400
500
600
700
800
900
1000
1500
2000
2500
3000
V
194.9
65.3
27.9
14.9
7.4
5.6
3.2
1.8
1.8
0.8
0.0
0.0
0.1
S
167.4
59.6
30.5
20.9
15.9
14.6
15.1
14.5
11.8
11.6
12.0
15.7
14.3
VS
194.0
61.3
27.3
14.6
7.7
6.5
3.2
5.9
1.3
1.2
0.8
0.2
1.5
ER2
V+
99.2
38.1
16.6
11.3
5.7
4.9
3.0
1.6
1.3
0.8
0.0
0.0
0.1
S+
91.0
39.2
23.5
17.8
14.6
13.5
14.4
14.3
11.8
12.0
11.4
15.8
14.3
VS+
101.2
36.7
18.3
10.6
5.6
5.4
2.8
6.6
2.2
1.2
0.8
0.2
V 61.1
12.9
4.8
1.8
1.6
0.6
0.5
0.4
0.2
0.0
0.0
0.0
0.0
S 50.6
11.6
6.3
3.9
4.0
2.4
2.4
3.3
2.7
5.1
3.1
3.5
5.4
VS
58.1
11.0
4.2
2.0
1.6
0.7
2.4
0.5
0.3
0.2
0.4
1.6
0.0
SF2
V+ 30.9
9.0
3.5
1.6
1.6
0.6
0.5
0.4
0.2
0.0
0.0
0.0
0.0
S+ 28.5
9.3
5.2
3.8
3.9
2.4
2.4
3.3
2.7
5.1
3.1
3.5
5.4
VS+
29.9
8.3
3.1
1.8
1.6
0.7
2.4
0.5
0.3
0.2
0.4
1.6
0.0
527.8
246.4
159.9
95.9
58.9
42.5
30.6
21.7
19.2
5.6
0.5
S 502.4
246.8
167.3
97.1
75.8
51.4
40.0
32.8
29.7
18.2
14.9
15.3
16.3
VS 517.6
243.6
159.3
92.6
57.1
42.4
30.9
21.9
20.0
5.7
2.9
1.0
1.3
ERS
V+
252.3
141.1
95.5
61.5
43.2
30.0
21.7
16.6
15.5
4.7
2.2
0.4
0.8
S+ 259.3
150.0
103.8
65.5
61.5
39.4
32.9
27.2
25.5
16.5
14.8
14.8
16.3
VS+
250.2
135.0
96.9
58.6
41.4
31.3
21.9
16.3
16.5
4.9
2.7
0.8
1.2
V
126.4
42.8
19.8
9.3
7.6
5.9
3.7
2.8
2.5
0.5
0.4
0.0
0.0
S
116.5
44.9
25.9
14.9
13.8
14.3
11.9
11.1
10.4
8.7
7.7
10.0
8.3
VS
123.8
40.8
21.2
8.9
7.4
5.5
4.1
3.0
2.5
0.5
0.4
0.0
0.0
SF5
V+
70.2
28.4
14.8
8.8
6.8
5.9
3.8
2.3
0.7
0.0
S+
74.1
33.9
21.1
14.0
12.9
14.6
11.8
10.5
10.5
8.9
7.7
10.2
8.3
VS+
70.8
28.5
17.1
8.4
6.7
5.9
3.9
2.4
2.5
0.7
0.4
0.1
0.0
Table B.12: SHD results 100 nodes linear monotonous Gumbel noise variance SEM with
different sample size.
200
300
400
500
600
700
800
900
1000
1500
2000
2500
3000
202.5
68.8
28.3
13.9
8.6
4.7
3.5
2.0
2.0
1.0
0.0
0.2
0.0
S
172.8
65.4
28.9
18.7
15.4
18.1
14.3
11.5
15.5
16.1
13.7
14.9
16.1
VS
190.5
64.7
27.4
13.6
7.5
6.6
3.7
6.2
1.6
1.0
1.2
0.3
5.8
ER2
V+
131.8
48.5
23.0
11.0
7.2
3.9
3.0
1.5
1.9
0.9
0.0
0.2
0.0
S+
123.1
52.7
23.3
17.3
15.1
17.0
14.2
11.1
14.7
16.2
13.8
14.9
16.1
VS+
126.2
48.2
20.7
11.3
5.7
6.7
3.4
5.6
1.6
1.1
1.0
0.3
3.8
V
62.4
14.0
3.5
1.6
0.9
0.8
0.7
0.5
0.2
0.0
0.0
0.0
0.0
S 53.4
12.0
4.4
4.6
4.5
2.8
2.3
2.7
2.6
4.6
3.9
2.9
3.1
VS 59.8
13.6
3.3
1.5
0.8
0.6
0.8
0.6
0.4
0.0
0.0
0.0
0.0
SF2
V+ 41.5
10.5
2.7
1.5
0.8
0.9
0.6
0.5
0.2
0.0
0.0
0.0
0.0
S+ 37.3
9.4
3.6
4.5
4.5
3.0
2.2
2.7
2.6
4.6
3.9
2.9
3.1
VS+
39.5
10.3
2.3
1.5
0.8
0.9
0.7
0.6
0.4
0.0
0.0
0.0
0.0
V 519.8
254.2
142.4
100.4
63.9
43.3
32.8
23.7
20.7
7.3
2.8
1.3
0.5
S 501.4
246.8
152.0
107.4
77.6
52.9
40.9
33.7
35.9
20.2
17.0
12.8
14.0
VS
511.6
246.0
140.9
95.6
63.6
41.6
33.1
23.0
20.1
11.4
4.7
1.4
3.3
ER5
V+ 315.2
173.1
100.9
75.3
51.4
35.2
27.4
19.1
16.9
6.3
2.2
1.2
0.5
S+ 318.4
175.0
112.9
83.4
66.9
42.4
36.8
28.9
34.3
19.7
17.6
12.6
14.1
VS+
315.6
167.3
3
100.5
72.1
51.0
34.0
27.8
19.3
17.7
10.2
4.2
1.3
3.3
V
137.5
49.4
18.7
10.1 6.7
4.9
3.8
2.3
1.9
0.8
0.2
0.1
0.0
S
128.1
47.1
25.7
15.9
16.4
11.5
11.3
10.1
8.5
10.1
9.2
9.1
12.5
VS
132.5
44.2
19.2
10.3
8.7
5.6
4.1
2.5
1.9
0.8
0.2
0.1
0.0
SE5
V+
89.7
33.1
15.4
10.1
6.8
5.0
4.0
2.4
1.9
0.7
0.2
0.1
0.0
S+
89.3
37.1
22.6
15.9
16.9
11.5
11.6
10.2
8.5
10.0
9.2
9.0
12.5
VS+
85.0
32.2
15.5
11.3
5.8
2.6
1.9
0.7
0.2
0.1
29

---

Under review as a conference paper at ICLR 2022
Table B.1 SHD results on 100 nodes linear monotonous Exponential noise variance SEM with different sample size.
200
300
400
500
600
700
800
900
1000
1500
2000
2500
3000
210.8
67.0
31.6
13.2
11.2
6.3
3.4
2.9
1.9
0.3
0.2
0.2
0.0
S
182.6
63.5
32.8
21.4
16.0
17.0
11.1
13.2
12.1
14.6
11.1
16.9
16.7
VS
202.8
90.2
30.8
12.5
9.9
5.2
4.8
5.7
2.3
0.5
1.2
1.3
0.2
ER2
V+
108.7
42.1
20.0
9.0
7.1
4.5
3.0
2.4
1.8
0.3
0.2
0.2
0.0
S+
100.6
41.6
22.8
17.0
13.5
16.1
11.7
12.7
11.8
14.4
11.0
16.7
16.7
VS+
107.3
58.4
19.1
8.3
6.9
4.3
3.3
5.2
2.1
0.4
1.2
1.3
0.2
V
71.4
13.0
6.2
1.7
0.8
0.9
0.7
0.2
0.6
0.3
0.0
0.0
0.0
61.2
14.4
4.7
4.7
2.9
3.3
4.0
4.6
2.2
3.0
2.8
3.8
5.3
VS
76.0
14.1
3.5
2.7
0.8
0.6
0.8
0.5
0.6
0.3
0.0
0.9
0.0
SF2
V+ 38.9
8.7
3.7
1.6
1.0
0.7
0.7
0.2
0.6
0.3
0.0
0.0
0.0
S+ 37.4
10.0
4.4
4.6
3.2
4.1
4.0
4.6
2.2
3.0
2.8
3.8
5.3
VS+
43.3
8.2
2.9
2.4
1.0
0.5
0.8
0.5
0.3 0.6
0.0
0.9
0.0
563.5
267.7
149.4
97.5
67.9
45.5
33.1
23.7
18.8
2.0
1.5
0.5
S 529.5
258.8
153.8
105.1
79.8
58.6
47.4
31.5
32.2
23.4
17.0
13.9
14.9
VS
549.0
258.3
151.0
97.0
68.4
46.1
35.4
22.9
18.5
7.7
4.9
0.9
ER5
V+
268.1
150.9
90.3
61.6
48.9
32.3
23.5
19.1
14.0
5.6
1.6
1.1
0.4
S+
262.6
156.3
99.8
73.0
60.9
45.1
39.7
26.4
26.3
22.2
16.7
15.0
14.7
VS+
258.7
146.1
95.2
63.9
48.
32.3
27.2
17.9
14.4
7.3
3.8
2.5
1.0
V
147.4
45.6
29.8
11.2
11.2
4.8
3.7
2.7
2.0
1.2
0.5
0.0
0.0
122.3
48.5
26.6
16.5
12.9
12.4
12.5
10.0
12.5
12.0
13.1
8.6
13.5
VS
136.9
43.9
20.6
11.3
6.4
4.9
5.0
2.9
2.6
1.2
0.5
3.6
0.1
SF5
V+
77.7
32.2
19.3
8.7
6.6
4.7
4.1
2.7
2.5
1.4
0.3
0.0
0.0
S+
74.3
37.8
22.1
15.7
13.1
12.0
12.7
10.2
12.9
12.3
13.1
8.6
13.5
VS+
78.2
31.5
17.1
10.2
6.6
5.2
3.1
3.2
0.3
3.6
0.1
30


Reviews:
[{"review_id": "vpdKlmySdIb", "reviewer": "Reviewer_Ag69", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strength : The paper provides thorough discussion of previous studies. \nWeak: Some points of the paper are not clear. \n(1)\tThe new identifiability condition (V) on page 4 requires a clear justification. For example, suppose that a true graph is V = (1,2,3) and E = { (2,3) }. If, node 1is chosen as i_1. Then, U_{k-1} y_j = 0 for j = 2, 3. Hence, I think the condition (V) and (SV) require a mathematical proof. \n(2)\tThe require conditions for Theorem 2.1 appear to be unrealistic. The first condition is that bounded random vector \\| x\\|^2 \\leq R. In this case, it is definitely not satisfied when error variables are Gaussian and Exponential as applied in the numerical experiments. Furthermore, as the number of node increases, R increases. In addition, R clearly depends on the sparsity level. For instance, X1 ~ N(0, \\sigma^2), X2 = X1 + N(0, \\sigma^2), X3 = X1 + X2 + N(0, \\sigma^2). Then, E( X1^2 + X2^2 + X3^2 ) = \\sigma^2 + 2 \\sigma^2 + 4 \\sigma^2 = 7 \\sigma^2. However, for a sparser case, X1 ~ N(0, \\sigma^2), X2 = X1 + N(0, \\sigma^2), X3 = X1 + N(0, \\sigma^2), E( X1^2 + X2^2 + X3^2 ) = \\sigma^2 + 2 \\sigma^2 + 2 \\sigma^2 = 5 \\sigma^2. \n(3)\tThe numerical experiments do not support the theoretical findings of the paper. According to Theorem 2.1., the sample complexity does not depend on the sparsity level of a graph. Hence, the comparison of performance of the proposed method for learning ER2 and ER5 cannot be explained. In addition, it is unclear that the SHD converges to zero. Hence, it would be better to provide the empirical probability of P(TRIU(U_p) = T). \n(4)\tAs explained, the considered distributions (Gaussian, Exponential) do not satisfy the bounded random variable assumption. \n", "summary_of_the_paper": "This paper develops a new algorithm for learning linear structural equation models using cholesky factorization. This paper explains that the proposed algorithm is consistent in high dimensional settings and computational feasible. This paper thoroughly discusses the recent studies of learning linear SEMs and provide a clear motivation. Furthermore, this paper provides a lot of numerical experiments to support its theoretical findings. \n", "summary_of_the_review": "This paper has a good idea of learning linear SEMs. However, this version of paper includes some unrefined conditions and requires better simulation settings. \n\nI believe that this paper has a great potential and it would be a much better paper after modifying some points of the paper. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "jZeFI95tMo", "reviewer": "Reviewer_tZir", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The present work uses several techniques from linear model causal discovery. However, the relation to existing work is not made clear enough in my opinion. In particular, how different is the proposed method (at least the ordering part since the pruning procedure, which is done by thresholding the estimated precision matrix, also appears in [2]) from the ordering estimation using the forward stepwise section ([1], Algorithm 1) ?\n\nOn the theoretical side, the claimed improved sample complexity compared to existing results seems unfair. Indeed, Theorem 2.1 assumes that the support of the data distribution lies within a sphere of radius sqrt(R), for a constant R independent of the dimension. Table 2.1 compares this result to the one stated in [2], which only assumes that the noise involved in each equation of the SEM is sub-Gaussian, e.g., each noise is a standard Gaussian. In this scenario (which appears to be tried in the experiments), not only the boundedness assumption does not hold, but the expected value of ||x||^2 would scale at least linearly in the dimension, and even quadratically for dense graphs, involving additional dimension dependence in the sample complexity.\n\nThe required identifiability assumption (Theorem 2.1) relies on an estimate from the data, not the model parameters themselves, which is strange to me, and differs from the conditions provided in [1,2] as opposed to what is claimed.\n\nOn the practical side:\nWhat part of the algo is actually improved compared to existing order-search algorithms ? Finding the topological order ? By better estimating the covariance matrix ? Using regularisation ? Pruning the DAG ?\n\nYou mention that algorithms such as LISTEN or US perform worse (or equally) compared to the the selected baselines. I find this fact very surprising, since the corresponding papers mention much better performance than what is obtained with, e.g., NOTEARS. It would also be interesting to compare your method with LISTEN using the inverse of the empirical covariance matrix (as opposed to the CLIME estimator), so as to match the covariance estimation part more closely with yours.\n\n[1] Park, \"Identifiability of Additive Noise Models Using Conditional Variances\"\n[2] Ghoshal et al., \"Learning linear structural equation models in polynomial time and sample complexity\"", "summary_of_the_paper": "This paper proposes a method for recovering the causal graph of additive linear models from purely observational data, under some an identifiability assumption, that seems to be related to the forward step-size assumption of [1]. Their algorithm is based on iteratively identifying a root of the causal graph based on its conditional variance. Once a topological order is learned, the graph is constructed by thresholding the Cholesky factor of the permuted precision matrix. The proposed algorithm is then tested and compared on both synthetic and real-world data.", "summary_of_the_review": "I find that the improved theoretical guarantees are not well motivated, and comparison to existing algorithms not clear enough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "cuf34xrFbO0", "reviewer": "Reviewer_2cwa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is well written and the claims are well supported by the experiments and theoretical analysis of the method. The significance of the work is on the time-complexity side, which is better than the existed related works. The correctness and soundness of the method are shown by the theoretical analysis and the experimental results. My only concern is that the work is based on a quite restrictive class of SEMs, of which the extension to the nonlinear cases or the more general scenario is not so clear.", "summary_of_the_paper": "The paper works on causal discovery in the linear Gaussian case, on which the identifiability is based on (Peters & Bühlmann, 2014). The proposed method is based on Cholesky factorization and has better efficiency/time-complexity performance than the related state-of-art methods. Moreover, it also provides a theoretical analysis of the resulted graph, which is appreciated. The experiments can support the claims.", "summary_of_the_review": "The paper is well written and the contributions and claims are well supported, while the proposed method focuses on a restrictive class of SEMs.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HuQhQQvkpQp", "reviewer": "Reviewer_SYfm", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is well motivated and the contributions of the paper is clear — the authors develop the fastest algorithm for learning linear SEMs. However given that existing algorithms from Ghoshal and Honorio 2018 and Chen et al 2019 are already polynomial time and are comparable to the proposed algorithm in terms of running time I feel this is not significant. The paper doesn't contribute anything new towards identifiability of linear SEMs. The experiments are extensive and the clearly demonstrate the effectiveness of the method.\n\nHowever my main criticism is the sample complexity. The sample complexity depends on the $\\ell_2$ norm of the $p$ dimensional random vectors $X$ which can be $O(p)$ even when the underlying SEM is sparse (has degree $d$ that is constant). This is not the case with the algorithm proposed in Ghoshal and Honorio whose sample complexity grows as $O(\\mathrm{poly}(d) \\log p)$. So the improved computational complexity come at the cost of increased sample complexity and the algorithm is not applicable in high dimensional settings.\n\nIn the experiments, the authors compare the performance of their algorithm against LISTEN (Ghoshal and Honorio 2018) only at 3000 number of samples. I would have liked to see learning curves (SHD vs varying number of samples) for both the algorithms. It is likely that LISTEN outperforms the proposed algorithm when the number of samples is low.", "summary_of_the_paper": "The paper proposes a new algorithm for learning linear SEMs using Cholesky factorization of the covariance matrix induced by the SEM. While the paper essentially follows the ideas in Ghoshal and Honorio 2018 and Chen et al 2019, the main innovation is combining the order search step followed by parent set recovery into a single step through Cholesky factorization. ", "summary_of_the_review": "While the proposed algorithm improves upon existing algorithms for learning linear SEMs, it comes at the cost of increased sample complexity. Unlike existing algorithms, the proposed algorithm is not applicable in the high-dimensional regime since the sample complexity grows as $O(p \\log p)$. Given that existing algorithms are already polynomial time and the proposed algorithm doesn't improve upon them in terms of required identifiability conditions and has significantly worse sample complexity, I feel the contributions are not strong enough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "B_nGTFodhR3", "reviewer": "Reviewer_WtL4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper presents a new algorithm to discover the causal relationship in a directed acyclic graph. The authors restrict themselves to the linear SEM setting under the assumption that the conditional noise variance for child nodes is larger than that of the parent nodes which ensures that the problem is identifiable.\nOverall I believe that this is a good paper, but I need a few clarifications.\n1. The authors say that the conditional noise variance of child nodes is \"approximately\" larger than that of the parent nodes. What approximation are the authors talking about?\n2. While evaluating the algorithm, the authors generate ER graphs. How do the authors ensure that the resulting graphs are DAGs?", "summary_of_the_paper": "In this paper the authors consider the problem of learning directed graphical models in the linear SEM setting. The authors use iterative Cholesky factorization of the covariance matrix in order to learn the causal relationship from the data.", "summary_of_the_review": "Overall an efficient algorithm to learn causal relationship. The paper is held back by strong assumptions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an algorithm for learning linear SEMs via the Cholesky factorization and provides a detailed theoretical analysis of the algorithm. After an extensive discussion and clarification from the authors, there was a consensus that the theoretical results are incremental compared to existing work and many of the claims need additional context in light of existing work. In particular, I recommend the authors pay careful attention to the presentation of the sample complexity bounds, which were revealed to be substantially weaker than initially claimed, and to validate these bounds with careful experiments.
Decision: Reject