# CAUSAL DISCOVERY VIA CHOLESKY FACTORIZATION

**Anonymous authors**
Paper under double-blind review

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 O(p[2]n + p[3]), where p and n are the numbers of nodes and
samples, respectively. Under proper assumptions, we show that our algorithm
takes O(log(p)) or O(p) samples to exactly recover the DAG structure under
proper assumptions. 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.

1 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; Žiž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 a 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 is a 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 & Heckerman (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 et 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 et 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.1e[18] DAGs for p = 10 (Sloane et al., 2003)). Those
algorithms go in quest of a 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., 2019a;b; 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 on 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, reinforcement
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


-----

via policy gradient as long as it explored a better DAG structure with a 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 on 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 to find a child or a contemporary of the current node. Meanwhile, it also
determines the corresponding column vector of the adjacent matrix. The mergence brings three main
differences: First, the topology order in TOSA is 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 to estimate the graph in
the second phase in TOSA, encourage the sparsity of the precision matrix, whereas our method is able
to encourage the sparsity of the adjacent matrix; Third, the time complexity is reduced significantly.
To be specific, the time complexity of our algorithm is O(p[2]n + p[3]), while the fastest algorithm
before is O(p[5]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 O(log(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-art 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.

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.

**Notations.** The symbol ∥· ∥ stands for the Euclid norm of a vector or the spectral norm of a matrix.
For a vector x = [x1, x2, . . ., xp] R[p], 1 stands for the ℓ1-norm, i.e., **_x1_** = _i=1_
For a matrix X = [Xij] R[m][×][n] ∈, 2, ∥· ∥stands for the two-to-infinity norm, i.e., ∥ _∥_ **_X_** 2, _[|][x]=[i][|][.]_
_∈_ _∥· ∥_ _∞_ _∥_ _∥_ _∞_
max1 _i_ _m_ **_Xi,:_** ; max stands for the max norm, **_X_** max = maxi,j **_Xij_** .
_≤_ _≤_ _∥_ _∥_ _∥· ∥_ _∥_ _∥_ _|_ _|_ [P][p]

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 G = (p, V, E), where p is the number of
nodes, V = _v1, ..., vp_ and E = (vi, vj) _i, j_ 1, ...p represent the set of nodes and edges,
_{_ _}_ _{_ _|_ _∈{_ _}}_
respectively. Each node vi is corresponding to a random variable Xi. The observed data matrix X =

[x1, ..., xp] ∈ R[n][×][p] where xi is consisting of n i.i.d observations of the random variable Xi. The
joint distribution of X is P (X) = _i=1_ _[P]_ [(][X][i][|][Pa][G][(][X][i][))][, where][ Pa][G][(][X][i][) :=][ {][X][j][|][(][v][i][, v][j][)][ ∈] _[E][}]_
is the parents of node Xi.

Given X, we seek to recover the latent DAG topology structure for the joint probability[Q][p]
distribution (Hoyer et al., 2008; Peters et al., 2017). Generally, X is modeled via a structural
equation model (SEM) with the form
_Xi = fi(Pa_ (Xi)) + Ni, (i = 1, ..., p),
_G_
where fi is an arbitrary function representing the relation between Xi and its parents, Ni is the jointly
independent noise variable.

In this paper, we focus on the linear SEM defined by
_Xi = Xwi + Ni,_ (i = 1, ..., p),


-----

whereadjacency matrix, wi ∈ R[p] is a weighted column vector. Let N = [n1, . . ., np] ∈ R[n][×][p] be an additive independent noise matrix, where W = [w1, . . ., wp] ∈ R[p][×][p] be the weighted ni is
_n i.i.d observations following the noise variable Ni. Then the linear SEM model can be formulated as_

**_X = XW + N_** _._ (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, a classical identifiable form of SEM is the
linear-Gaussian SEM, where all Ni are i.i.d. and homoscedastic (Peters & Bühlmann, 2014).

2.2 ALGORITHM MOTIVATION

As proposed in McKay et al. (2003); Nicholson (1975), a graph is DAG if and only if the corresponding
weighted adjacent matrix W can be decomposed into

**_W = P T P_** [T], (2)

where P is a permutation matrix, T is a strict upper triangular matrix, i.e., Tij = 0 for all i ≤ _j._

We denote the scaled permuted data matrix as **_X =_** _√1n_ **_XP, the scaled permuted noise matrix as_**
**_N =_** _√1n_ **_NP, and the permutation order [i[∗]1[, i][∗]2_** _[. . ., i]p[∗][] = [1][,][ 2][, . . ., p][]][P][ . We can rewrite (][1][) as]_

[c]
c **_X =_** **_XT +_** **_N_** _._

Then it follows that
**_Xc =_** **_N[c](I −_** **_T[c] )[−][1]._** (3)

Let

c [c]

E(N[c][T][ c]N ) = **Σ[2]** **Σ[T][ b]Σ,** (4)
_∗_ [=][ b]

where **Σ[2]** **Σ is upper triangular – the Cholesky**
_∗_ [is the covariance matrix of the noise variables,][ b]

[b]

factor of **Σ[2]∗[. Let the diagonal entries of][ b]Σ be σi[2][∗]1** _[, σ]i[2][∗]2_ _[, . . ., σ]i[2][∗]p_ [. We know that][ σ]i[2][∗]k [is the conditional]
variance of[b] _Ni[∗]k_ [.]

[b]

Now using (3) and (4), we have the covariance matrix of the permuted data:

**_C_** = E(X[c][T][ c]X) = (I **_T )[−][T]E(N[c][T][ c]N_** )(I **_T )[−][1]_** = (I **_T )[−][T][ b]Σ[T][ b]Σ(I_** **_T )[−][1]._** (5)
_∗_ _−_ _−_ _−_ _−_

Let L = (I **_T )[−][T][ b]Σ[T], then_** **_C_** = LL[T], which is the Cholesky factorization of the covariance

b _−_ _∗_

matrix **_C_** since L is lower triangular. Furthermore, we can see that the diagonal entries of L are the
_∗_
same as that of **Σ, i.e., Lkk = σ[b]i[∗]k** [, the conditional variances of][ X][i][∗]k [and][ N][i]k[∗] [are the same.]

[b]

The task becomes to find the permutation i[∗] = [i[∗]1[, i][∗]2[, . . ., i]p[∗][]][ and an upper triangular matrix][ U]

[b]

such that U _[−][T]U_ _[−][1]_ is a good approximation of the empirical estimation of the permuted covariance
matrix **_C =_** _n[1]_ **_[X]:[T],i[∗]_** **_[X][:][,][i][∗]_** [, and][ U][ satisfies some additional constraints, such as the sparsity, etc.]

2.3 A[b]LGORITHM

We iteratively find the permutation i and calculate U via the Cholesky factorization. Assume that
**_ik_** 1 = [i1, . . ., ik 1] and Uk 1 = U1:k 1,1:k 1 are settled, and we have
_−_ _−_ _−_ _−_ _−_

**_C1:k−1,1:k−1 = n[1]_** **_[X]:[T],ik−1_** **_[X][:][,][i]k−1_** [+][ λ][I][ =][ U][ −]k−[T]1[U][ −]k−[1]1[,] (6)

where λ > 0 is a diagonal augmentation parameter which we will give detailed discussion latter.
Next, we show how to find ik and the last column of Uk.

For the time being, let us assume ik is known, we show how to compute the last column of Uk. Let
**_Uk[−][1]_** = **_Uk[−]0−[1]1_** _α[y][k]k_, then
h i


T
**_Uk[−]−[1]1_** **_[y][k]_**
0 _αk_
i h


**_Uk[−]−[T]1[U][ −]k−[1]1_** **_Uk[−]−[T]1[y][k]_**
**_yk[T][U][ −]k_** [1]1 _α[2]k[+][∥][y][k][∥][2]_
_−_


= [1]


**_X:[T],ik−1_** **_[X][:][,][i]k−1_** [+][λI][ X]:[T],ik−1 **_[X][:][,i]k_**
**_X:[T],ik_** **_[X][:][,][i]k−1_** _∥X:,ik ∥[2]+λ_


**_Uk[−]−[1]1_** **_[y][k]_**
0 _αk_


-----

**Algorithm 1 Causal Discovery via Cholesky Factorization (CDCF)**

1: input: Data matrix X ∈ R[n][×][p], Truncate Threshold ω > 0, and tuning parameter γ.
2: output: Adjacent Matrix A.
3: Set i = [1, 2, . . ., p], R = ∥X∥2[2],∞ [and][ λ][ =][ γ][ log]n _[ p]_ _R;_

4: Set ℓ = arg min **_X:,i1_** _,_ **_X:,i2_** _, . . .,_ **_X:,ip_** ;

5: Exchange i1 and {∥ iℓ in i; Set∥ _∥ U1 =∥_ _∥X ∥:,iℓn∥[2]+λ∥}[;]_

6: for k = 2, 3, . . ., p do q
7: **for j = k, k + 1, . . ., p do**

8: **_yj =_** _n[1]_ **_[U][ T]k_** 1[X]:[T],ik 1 **_[X][:][,i]j_** [;]

_−_ _−_

9: _αj =_ _n1_ _[∥][X][:][,i][j]_ _[∥][2][ +][ λ][ −∥][y][j][∥][2][;]_

10: **end for** q

11: **(V) ℓ** = arg mink _j_ _p αj[2][;]_
_≤_ _≤_
**(S)(VS) ℓ ℓ= arg min= arg mink≤kj≤≤jp≤ ∥pU ∥Uk−k1−y1jy∥j1∥;1** _αj[2]_ _[−]_ _k−1_ 1 _hk−=11_ [Uk−11][2]hh ;

12: Exchange ik and iℓ in i; q P

13: Set Uk = **_Uk0−1 −_** _αℓ[1]_ **_[U]1[k][−][1][y][ℓ]_** ;

_αℓ_

 

14: end for
15: return A = [TRIU(TRUNCATE(Up, ω))]REVERSE(i),REVERSE(i).


where the last equality dues to (6). It follows that

**_yk = [1]_** _k_ 1[X]:[T],ik 1 **_[X][:][,i]k_** _[,]_ _αk =_

_n_ **_[U][ T]−_** _−_

And direct calculation gives rise to


1
(7)
_n_ _[∥][X][:][,i][k]_ _[∥][2][ +][ λ][ −∥][y][k][∥][2][.]_


**_Uk =_** **_Uk[−]0−[1]1_** _α[y][k]k_ _−1_ = **_Uk0−1 −_** _αk[1]_ **_[U]αk1[k][−][1][y][k]_** _._ (8)
h i  

By (8), once ik is settled, we can obtain the last column of Uk. Our task remains to select ik
from {1, . . ., p} \ {i1, . . ., ik−1}. There are several ways to accomplish this task. We propose
three criteria to select1, . . ., p _i1, . . ., ik ik1. First, we need to compute). Then we select ik according to one of the following criteria: αj and yj by (7) for all possible j (ij ∈_
_{_ _} \ {_ _−_ _}_

**(V)** _ik = arg mink_ _j_ _p αj[2][. 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)** _ik = arg mink_ _j_ _p_ **_Uk_** 1yj 1. Using (3) and (6), we know that Up intends to estimate
_≤_ _≤_ _∥_ _−_ _∥_
(I − **_T )Σ[b]_** _[−][1]. 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**
**_Uk. This criterion is especially useful when the number of samples is small, see Tables B.1, B.2_**
and B.3 in appendix.

[b]

**(VS) ik = arg mink≤j≤p ∥Uk−1yj∥1** _αj[2]_ _[−]_ _k−1_ 1 _hk−=11_ [Uk−11][2]hh . We empirically combine

criterion (V) and criterion (S) together to take both aspects (variance and sparsity) into account.

q P

Numerically, we found that this criterion achieves the best performance in real-world data.

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 is insufficient. In addition, by
setting λ = O( [log]n[ p] [)][, 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


-----

significantly improves the ability to recover the DAG, especially when the samples are 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 **_X:,i1_** _,_ **_X:,i2_** _, . . .,_ **_X:,ip_** . Line 5,
we exchange i1 and iℓ in i and calculate U1 = _∥X:,iℓn∥[2]+ {∥λ_ [. Lines 6 to 14, we iteratively calculate]∥ _∥_ _∥_ _∥_ _∥}_

**_Uk and update permutation order i until all the indices are settled. Line 15, we truncateq_** **_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 [Up]:,k is inversely proportional to αk. So, for column k, we set
_ωk =_ _αωk_ [, and do the truncation:][ [][U][p][]][ik][ is set to zero if][ |][[][U][p][]][ik][|][ < ω][k][. On output, node][ i][ connects to]

node j in if **_Aij_** _> 0._
_G_ _|_ _|_

**Time Complexity** Note that we do not have to re-calculate the matrix multiplication of
**_X:[T],ik_** 1 **_[X][:][,i]j_** [in line 8 since we can calculate][ C][ at the cost of][ O][(][p][2][n][)][ at first. Besides, at step]
_−_
_k, we have already calculate Uk[T]_ 2[X]:[T],ik 1 **_[X][:][,i]j_** [at previous step, we only need to calculate the last]
_−_ _−_
entry of yj, which is the inner product between two k dimensional vectors, at the cost of (p) in worst
_O_
case. Overall, the time complexity of CDCF is O(p[3] + p[2]n). When n > p, the complexity becomes
_O(p[2]n), which is equivalent to 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.

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.1matrix. Let x Let1, . . ., x x ∈nR be[p]** _nbe a zero-mean random vector, independent samples,_ **_C =_** **_Cn[1]_** =nk E=1(xx[x][k][x][T]k[T]) ∈[be the sample covariance]R[p][×][p] _be the covariance_

_estimator. Assume_ **_C_** **_C_** _ϵ for some ϵ > 0. Denote_ **_Cλ =_** **_C + λI, where λ =_** (ϵ) 0 is a
_∥_ _−_ [b]∥≤ P _O_ _≥_
_parameter. Let the Cholesky factorizations of C = E[b]xx[T]_ _and_ **_Cλ be C = LL[T]_** _and_ **_Cλ =_** **_LL[b][T],_**
_respectively, where L and_ **_L are both lower triangular. For the linear SEM model ([b]_** [b] _1), assume (2)_
_and (4), and for k ∈_ _PaG(j), δ = inf_ _k∈P aG_ (j) δjk > 0, where [b] [b] [b]

_δ[b]jk = σi[2][∗]j_ [+][ ∥]Σ[b] _n[(I −_ **_T )[−][1]]k:j−1,k∥[2]_** _−_ _σi[2][∗]k_ _[.]_

_If δ ≥_ 4(ϵ + λ) and ∥L[−][1]∥[2](ϵ + λ) < [3]4 _[, then][ CDCF][-][V][ is able to recover][ P][ exactly. In addition, it]_

_holds that_

_∥TRIU(Up) −_ **_T ∥max ≤_** 4∥Σ[b] _[−]∗_ [1][(][I][ −] **_[T][ )][T][∥]2[2],∞[∥][(][I][ −]_** **_[T][ )]Σ[b]_** _[−]∗_ [T]∥2,∞(ϵ + λ),

_where TRIU(Up) stands for the strictly upper triangular part of Up, Up is the output of outer loop of_
_Algorithm 1 with criterion (V)._

we know that when T is sparse, we may recover its topology structure by truncating Up.


**Proposition 1 Let Ni,: be independent bounded, or sub-Gaussian, or regular polynomial-tail, then**
_for n > N_ (ϵ), it holds **_Cxx_** **_Cxx_** _ϵ, w.h.p. Specifically,_
_∥([b]I_ _−T )−1_ _∥≤2_ **_Cnn_** 2

_N_ (ϵ) _C1 log p_ _∥_ _−_ _∥_ _∥_ _∥_ _,_ _for bounded class;_
_≥_ _ϵ_

(I **_T )−1_** 2 **_Cnn_** 2 
_N_ (ϵ) _C2 p_ _∥_ _−_ _∥_ _∥_ _∥_ _,_ _for the sub-Gaussian class;_
_≥_ _ϵ_
 (I **_T )−1_** 2 **_Cnn_** 2(1+r[−][1])

_N_ (ϵ) _C3 p_ _∥_ _−_ _∥_ _∥_ _∥_ _,_ _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 O(p). This sample complexity is better than the sample complexities
of previous methods, see Table 2.1 for a detailed comparison.


-----

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 − _ϵ, 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 x, g[−][1]_ exists when x > 3 and g[−][1](x) > x.

|Algorithm|Data|Function|Noise Type|Cov(X)|Sample Complexity|
|---|---|---|---|---|---|
|NPVAR (Gao et al., 2020)|-|(Non)-linear Lip-continuous|-|-|((rp/ϵ)1+p/2) O|
|EV (Chen et al., 2019)|n > p|Linear|-|λ > 0 min|(p2 log(p)) O|
||n < p|Linear|-|λ > 0 min|(q2 log(p)) O|
|LISTEN (Ghoshal & Honorio, 2018)|-|Linear|Sub-Gaussian|-|(d4 log(p)) O|
||-|Linear|Bounded moment|-|(d4(p2)1/m) O|
|US (Park, 2020)|n > p|Linear|Gaussian|λ > 0 min λ < max ∞|g−1( O(log(p)))|
|CDCF|-|Linear|Sub-Gaussian Polynomial tail|-|(p) O|



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: Erdö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 is 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 et al., 2020), and EQVAR (Chen et al., 2019). Other
methods such as PC algorithm (Spirtes et al., 2000), LiNGAM (Shimizu et al., 2006), FGS (Ramsey
et al., 2017), MMHC (Tsamardinos et al., 2006), L1OBS (Schmidt et 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 we find that other metrics such as true positive rate (TPR), false discovery rate (FDR),
false positive rate (FPR), and F1 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 p = 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 a
“+” as postfix. For example, "CDCF-V" means CDCF with V criterion and λ = 0, and "CDCF-V+"
means CDCF with V criterion and λ = O( [log]n[ p] [)][. The implementation details are in the Appendix][ B][.]

We report the result of CDCF-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 ≤ _n, respectively. We can see from the results, CDCF-V+ achieves significantly_
better performance comparing with previous baselines.


-----

ER2


ER5


SF2


SF5


200

150

100

50


400

300

200

100


1500

1000

500


600

400

200

0

200 300 400 500 600

|Col1|Col2|CDC|F-V+|
|---|---|---|---|
|||EV-T LTN|D|
|||LTN-|CH|
|||||


200 300 400 500 600

CDCF-V+
EV-TD
LTN
LTN-CH


1500

1000


200 300 400 500 600


200 300 400 500 600

1000


2000

1500

1000

500

20 40 60 80 100

Sample Number


3000

2000

1000

20 40 60 80 100

Sample Number


750

500

250

0

20 40 60 80 100

Sample Number


500

0

20 40 60 80 100

|Col1|Col2|Col3|Col4|
|---|---|---|---|
|||CDC EV-H|F-V+ TD|
|||LTN||
|||||


CDCF-V+
EV-HTD
LTN

Sample Number


Figure 3.1: Performance (SHD) tested on 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.68.3 17.910.6 0.40.5 **0.00.0** **0.00.0**

50 ER5 67.87.5 93.2109.4 64.813.1 0.60.8 0.10.3 **0.00.0**

SF2 3.51.6 79.393.2 **0.00.0** 1.11.0 **0.00.0** **0.00.0**
SF5 20.114.3 89.299.2 20.810.1 1.00.9 **0.00.0** **0.00.0**

ER2 72.623.5 66.219.2 18.65.7 2.11.2 **0.00.0** **0.00.0**

100 ER5 170.334.2 236.436.8 164.817.1 2.31.2 0.20.4 **0.10.3**

SF2 2.31.3 156.821.2 **0.00.0** 3.01.41 **0.00.0** **0.00.0**
SF5 90.234.5 165.222.0 10.86.1 2.70.9 0.10.3 **0.00.0**

ER2 -  -  -  -  0.40.5 **0.10.3**

1000 ER5 -  -  -  -  21.83.8 **8.94.2**

SF2 -  -  -  -  **0.00.0** **0.00.0**
SF5 -  -  -  -  0.30.5 **0.00.0**

Table 3.2: Running time (seconds) on 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
CORL1 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 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
as CDCF does not have to update the parameters with gradients.


-----

Table 3.3: Results on Proteins data sets.

|Data sets|Methods|FDR|TPR|FPR|SHD|N|P|F1|
|---|---|---|---|---|---|---|---|---|
|853 samples 17 edges|CDCF-V/V+ CDCF-S/S+ CDCF-VS/VS+ NOTEARS NOTEARSMLP CORL1&2 EV-TD LISTEN NPVAR DAG-GNN|0.533 0.500 0.500 0.588 0.733 0.533 0.645 0.750 0.800 0.588|0.412 0.412 0.412 0.412 0.235 0.412 0.294 0.176 0.176 0.412|0.210 0.184 0.184 0.263 0.290 0.211 0.237 0.237 0.316 0.263|11 10 10 13 18 11 17 18 19 15|15 14 14 17 15 15 14 12 15 17|0.467 0.500 0.500 0.412 0.267 0.467 0.357 0.250 0.200 0.412|0.438 0.452 0.452 0.412 0.250 0.438 0.323 0.207 0.188 0.412|
|7466 samples 20 edges|CDCF-V/V+ CDCF-S/S+ CDCF-VS/VS+ NOTEARS NOTEARSMLP CORL1&2 EV-TD LISTEN NPVAR DAG-GNN|0.667 0.611 0.556 0.650 0.800 0.667 0.700 0.714 0.679 0.650|0.400 0.350 0.400 0.350 0.200 0.400 0.300 0.300 0.450 0.350|0.457 0.314 0.286 0.371 0.457 0.457 0.400 0.429 0.543 0.371|21 17 16 20 26 21 25 23 24 20|24 18 18 20 20 24 20 21 28 20|0.333 0.389 0.444 0.350 0.200 0.333 0.300 0.286 0.321 0.350|0.364 0.368 0.421 0.350 0.200 0.363 0.300 0.293 0.375 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 λ (Tables B.7 to B.10), and performances on different noise
distribution (Figures B.1, B.2) and deviation (Tables B.11, B.12, B.13) are given in Appendix B.

3.2 PROTEINS DATA SET

We consider a bioinformatics data set (Sachs et al., 2005) consisting of continuous measurements
of expression levels of proteins and phospholipids in the human immune system cells. This is a
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 et 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 hyper-parameters
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 to TPR, we do not include it in the table. In both
settings, CDCF-VS+ achieves state-of-the-art performance. [1] 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-linear 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-237 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
predicates. In this experiment, we only consider the single jump predicate between the entities, which

1For NOTEARS-MLP, Table 3.3 reported the results reproduced by the code provided in Zheng et al. (2020).


-----

2.0 Parent Child

Medicine/Disease People/CauseOfDeath

1.5 Medicine/RiskFactors People/CauseOfDeath

Broadcast/Artist Music/Artist
Broadcast/Artist Music/Instrumentalists

1.0

Tv/ProgramCreator Tv/Languages
Tv/ProgramCreator Tv/OriginCountry

0.5 Tv/Languages Tv/OriginCountry

Tv/Genre Film/Country

0.0 Film/Director Media/NetflixGenre

Film/StoryBy Film/Prequel

0.5 Film/WrittenBy Film/Genre

Disease/RiskFactors Disease/symptom

1.0 Sports/Colors Sports/Teams

Person/Nationality Person/PlaceOfBirth
Location/TimeZones Location/Country

1.5

Education/Campuses Education/SchoolType
Olympics/Countries Event/Locations

2.0 Olympics/Countries People/Language


|F|Col2|Col3|Col4|Col5|Col6|Col7|Col8|Col9|Col10|2 1 1 0 0|
|---|---|---|---|---|---|---|---|---|---|---|
|P|||||||||||
|L|||||||||||
|M|||||||||||
|E|||||||||||
|T|||||||||||
|·|||||||||||
|·|||||||||||
|·|||||||||||
|· ·|||||||||||
|· ···|||||||||||
|···|F P L M E T · · · · · · ····|||||||||··|


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 to an entity with awareness of the
position (Subject or Object), and each variable corresponds to a 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 of them are replaced with a 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 of 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, we found that the predicate in domain "TV" ("T") has many relations with the
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 on the right side of Figure 3.2, we
can see that the discovered indication relations between predicates are quite reasonable.

4 CONCLUSION AND FUTURE WORK

In this paper, we proposed a topology search algorithm for the DAG structure recovery problem. Our
algorithm is better than the existing methods in both time and sample complexities. To be specific, the
time complexity of our algorithm is O(p[2]n + p[3]), while the fastest algorithm before is O(p[5]n) (Park,
2020; Gao et al., 2020), where p and n are the numbers of nodes and samples, respectively. Under
different assumptions, our algorithm takes O(log(p)) or O(p) 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 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-art performance.
For the knowledge base data set, we can observe many reasonable structures of the discovered DAG.

The proposed algorithm is under the assumption of linear SEM. Generalization of CDCF to nonlinear SEM would be a 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 an attractive problem. To deal with the extremely large-scale problems, such as
millions of nodes, implementing CDCF via sparse matrix storage and calculation on the GPU is a
promising way to further improve computational performance.


-----

REFERENCES

Bryon Aragam and Qing Zhou. Concave penalized estimation of sparse gaussian bayesian networks.
_[J. Mach. Learn. Res., 16:2273–2328, 2015. URL http://dl.acm.org/citation.cfm?](http://dl.acm.org/citation.cfm?id=2886822)_
[id=2886822.](http://dl.acm.org/citation.cfm?id=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-dimensional order
[search and penalized regression. CoRR, abs/1310.1533, 2013. URL http://arxiv.org/](http://arxiv.org/abs/1310.1533)
[abs/1310.1533.](http://arxiv.org/abs/1310.1533)

Wenyu Chen, Mathias Drton, and Y Samuel Wang. On causal discovery with an equal-variance
assumption. Biometrika, 106(4):973–980, 2019.

David Maxwell Chickering. Learning bayesian networks is np-complete. In Doug Fisher and HansJoachim 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/978-1-4612-2404-4\_12. URL https://doi.org/10.1007/](https://doi.org/10.1007/978-1-4612-2404-4_12)
[978-1-4612-2404-4_12.](https://doi.org/10.1007/978-1-4612-2404-4_12)

David Maxwell Chickering. Optimal structure identification with greedy search. J. Mach. Learn.
_[Res., 3:507–554, 2002. URL http://jmlr.org/papers/v3/chickering02b.html.](http://jmlr.org/papers/v3/chickering02b.html)_

David Maxwell Chickering, David Heckerman, and Christopher Meek. Large-sample learning of
[bayesian networks is np-hard. J. Mach. Learn. Res., 5:1287–1330, 2004. URL http://jmlr.](http://jmlr.org/papers/volume5/chickering04a/chickering04a.pdf)
[org/papers/volume5/chickering04a/chickering04a.pdf.](http://jmlr.org/papers/volume5/chickering04a/chickering04a.pdf)

Nir Friedman and Daphne Koller. Being bayesian about network structure. A bayesian approach to
structure discovery in bayesian networks. Mach. Learn., 50(1-2):95–125, 2003. doi: 10.1023/A:
[1020249912095. URL https://doi.org/10.1023/A:1020249912095.](https://doi.org/10.1023/A:1020249912095)

Ming Gao, Yi Ding, and Bryon Aragam. A 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 in Neural Information Processing Systems 33: Annual
_Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12,_
_[2020, virtual, 2020. URL https://proceedings.neurips.cc/paper/2020/hash/](https://proceedings.neurips.cc/paper/2020/hash/85c9f9efab89cee90a95cb98f15feacd-Abstract.html)_
[85c9f9efab89cee90a95cb98f15feacd-Abstract.html.](https://proceedings.neurips.cc/paper/2020/hash/85c9f9efab89cee90a95cb98f15feacd-Abstract.html)

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 on Uncertainty
_in Artificial Intelligence, Seattle, Washington, USA, July 29-31, 1994, pp. 235–243. Morgan_
Kaufmann, 1994. [URL https://dslpitt.org/uai/displayArticleDetails.](https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=509&proceeding_id=10)
[jsp?mmnu=1&smnu=2&article_id=509&proceeding_id=10.](https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=509&proceeding_id=10)

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, S. V. N. Vishwanathan, and Roman Garnett (eds.),
_Advances in Neural Information Processing Systems 30:_ _Annual Conference on Neural_
_Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp._
[6457–6466, 2017. URL https://proceedings.neurips.cc/paper/2017/hash/](https://proceedings.neurips.cc/paper/2017/hash/907edb0aa6986220dbffb79a788596ee-Abstract.html)
[907edb0aa6986220dbffb79a788596ee-Abstract.html.](https://proceedings.neurips.cc/paper/2017/hash/907edb0aa6986220dbffb79a788596ee-Abstract.html)

Asish Ghoshal and Jean Honorio. Learning linear structural equation models in polynomial time and
sample complexity. In Amos J. Storkey and Fernando Pérez-Cruz (eds.), International Conference
_on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote,_
_Canary Islands, Spain, volume 84 of Proceedings of Machine Learning Research, pp. 1466–1475._
[PMLR, 2018. URL http://proceedings.mlr.press/v84/ghoshal18a.html.](http://proceedings.mlr.press/v84/ghoshal18a.html)

Edgar N Gilbert. Random graphs. The Annals of Mathematical Statistics, 30(4):1141–1144, 1959.


-----

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://proceedings.neurips.cc/paper/2008/](https://proceedings.neurips.cc/paper/2008/hash/f7664060cc52bc6f3d620bcedc94a4b6-Abstract.html)
[hash/f7664060cc52bc6f3d620bcedc94a4b6-Abstract.html.](https://proceedings.neurips.cc/paper/2008/hash/f7664060cc52bc6f3d620bcedc94a4b6-Abstract.html)

Helmut Kuhn. Schelling: The ages of the world, 1942.

Sébastien Lachapelle, Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien. Gradientbased neural DAG learning. In 8th International Conference on Learning Representations, ICLR
_[2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https://](https://openreview.net/forum?id=rklbKA4YDS)_
[openreview.net/forum?id=rklbKA4YDS.](https://openreview.net/forum?id=rklbKA4YDS)

Olivier Ledoit and Michael Wolf. A well-conditioned estimator for large-dimensional covariance
matrices. Journal of multivariate analysis, 88(2):365–411, 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: 10.1007/s11704-020-0268-6. [URL https://doi.org/10.1007/](https://doi.org/10.1007/s11704-020-0268-6)
[s11704-020-0268-6.](https://doi.org/10.1007/s11704-020-0268-6)

Brendan D McKay, Frédérique E Oggier, Gordon F Royle, NJA Sloane, Ian M Wanless, and Herbert S
Wilf. Acyclic digraphs and eigenvalues of (0, 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.08527, 2019a. URL http://arxiv.org/abs/1910.](http://arxiv.org/abs/1910.08527)
[08527.](http://arxiv.org/abs/1910.08527)

Ignavier Ng, Shengyu Zhu, Zhitang Chen, and Zhuangyan Fang. A graph autoencoder approach to
[causal structure learning. CoRR, abs/1911.07420, 2019b. URL http://arxiv.org/abs/](http://arxiv.org/abs/1911.07420)
[1911.07420.](http://arxiv.org/abs/1911.07420)

Victor A 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:34, 2020. URL http://jmlr.org/papers/v21/19-664.html.](http://jmlr.org/papers/v21/19-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–2053, 2014. URL http:](http://dl.acm.org/citation.cfm?id=2670315)
[//dl.acm.org/citation.cfm?id=2670315.](http://dl.acm.org/citation.cfm?id=2670315)

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., 3(2):121–129, 2017. doi: 10.1007/s41060-016-0032-z. URL https://doi.org/](https://doi.org/10.1007/s41060-016-0032-z)_
[10.1007/s41060-016-0032-z.](https://doi.org/10.1007/s41060-016-0032-z)

Karen Sachs, Omar Perez, Dana Pe’er, Douglas A Lauffenburger, and Garry P Nolan. Causal proteinsignaling networks derived from multiparameter single-cell data. Science, 308(5721):523–529,
2005.


-----

Mark Schmidt, Alexandru Niculescu-Mizil, and Kevin P. Murphy. Learning graphical model structure
using l1-regularization paths. In Proceedings of the Twenty-Second AAAI Conference on Artificial
_Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada, pp. 1278–1283. AAAI Press,_
[2007. URL http://www.aaai.org/Library/AAAI/2007/aaai07-202.php.](http://www.aaai.org/Library/AAAI/2007/aaai07-202.php)

Robert Sedgewick and Kevin Wayne. "4,2,25 Unique topological ordering", Algorithms, 4th Edition.
Addison-Wesley, 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:](http://jmlr.org/papers/v7/shimizu06a.html)
[//jmlr.org/papers/v7/shimizu06a.html.](http://jmlr.org/papers/v7/shimizu06a.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 978-0-262-19440-2._

Chandler Squires, Joshua Amaniampong, and Caroline Uhler. Efficient permutation discovery in
[causal dags. CoRR, abs/2011.03610, 2020. URL https://arxiv.org/abs/2011.03610.](https://arxiv.org/abs/2011.03610)

Nikhil Srivastava and Roman Vershynin. Covariance estimation for distributions with 2 + ε moments.
_The Annals of Probability, 41(5):3081–3111, 2013._

Marc Teyssier and Daphne Koller. Ordering-based 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,_
2005. [URL https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=](https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=1233&proceeding_id=21)
[1&smnu=2&article_id=1233&proceeding_id=21.](https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=1233&proceeding_id=21)

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 Callison-Burch, 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.18653/v1/d15-1174. URL https://doi.org/10.18653/v1/d15-1174.](https://doi.org/10.18653/v1/d15-1174)

Ioannis Tsamardinos, Laura E. Brown, and Constantin F. Aliferis. The max-min hill-climbing
bayesian network structure learning algorithm. Mach. Learn., 65(1):31–78, 2006. doi: 10.1007/
[s10994-006-6889-7. URL https://doi.org/10.1007/s10994-006-6889-7.](https://doi.org/10.1007/s10994-006-6889-7)

Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint
_arXiv:1011.3027, 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://arxiv.org/abs/2105.06631.](https://arxiv.org/abs/2105.06631)

Jing Xiang and Seyoung Kim. A* lasso for learning a sparse bayesian network structure
for continuous variables. In Christopher J. 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 a meeting held December 5-8,_ _2013,_ _Lake Tahoe,_ _Nevada,_ _United States,_ pp.
[2418–2426, 2013. URL https://proceedings.neurips.cc/paper/2013/hash/](https://proceedings.neurips.cc/paper/2013/hash/8ce6790cc6a94e65f17f908f462fae85-Abstract.html)
[8ce6790cc6a94e65f17f908f462fae85-Abstract.html.](https://proceedings.neurips.cc/paper/2013/hash/8ce6790cc6a94e65f17f908f462fae85-Abstract.html)

Qiaoling Ye, Arash A. Amini, and Qing Zhou. Optimizing regularized cholesky score for order-based
[learning of bayesian networks. CoRR, abs/1904.12360, 2019. URL http://arxiv.org/](http://arxiv.org/abs/1904.12360)
[abs/1904.12360.](http://arxiv.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 on 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://proceedings.mlr.press/v97/yu19a.html.](http://proceedings.mlr.press/v97/yu19a.html)


-----

Kun Zhang and Aapo Hyvarinen. On the identifiability of the post-nonlinear causal model. arXiv
_preprint arXiv:1205.2599, 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 https://proceedings.neurips.cc/paper/2018/hash/](https://proceedings.neurips.cc/paper/2018/hash/e347c51419ffb23ca3fd5050202f9c3d-Abstract.html)
[e347c51419ffb23ca3fd5050202f9c3d-Abstract.html.](https://proceedings.neurips.cc/paper/2018/hash/e347c51419ffb23ca3fd5050202f9c3d-Abstract.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. 3414–3425._
[PMLR, 2020. URL http://proceedings.mlr.press/v108/zheng20a.html.](http://proceedings.mlr.press/v108/zheng20a.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. 2613–2624. IEEE, 2021. doi: 10.1109/ICDE51399.2021.00292._
[URL https://doi.org/10.1109/ICDE51399.2021.00292.](https://doi.org/10.1109/ICDE51399.2021.00292)

Shengyu Zhu, Ignavier Ng, and Zhitang Chen. Causal discovery with reinforcement 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?id=](https://openreview.net/forum?id=S1g2skStPB)_
[S1g2skStPB.](https://openreview.net/forum?id=S1g2skStPB)

Slavoj Žižek and Friedrich Wilhelm Joseph von Schelling. The abyss of freedom. University of
Michigan Press, 1997.


-----

A PROOF OF THEOREM 2.1

In this section, we first give several lemmas, then prove Theorem 2.1.


**Lemma A.1matrix. Let x Let1, . . ., x ∈ xnR be[p]** _be a zero-mean random vector, n independent samples,_ **_C =_** **_Cn[1]_** =nk E=1(xx[x][k][T][x])k[T] ∈[be the sample covariance]R[p][×][p] _be the covariance_

_estimator. Assume_ **_C_** **_C_** _ϵ for some ϵ > 0. Denote_ **_Cλ =_** **_C + λI, where λ =_** (ϵ) 0 is a
_∥_ _−_ [b]∥≤ P _O_ _≥_
_parameter. Let the Cholesky factorizations of C = E[b]xx[T]_ _and_ **_Cλ be C = LL[T]_** _and_ **_Cλ =_** **_LL[b][T],_**
_respectively, where L and_ **_L are both lower triangular. If ∥[b]L[−][1]∥[2][b](ϵ + λ) <_** 4[3] _[, then]_

[b] [b] [b]

**_Li,:_** [L[b]λ]i,: _ϵ + λ =_ (ϵ), _for 1_ _i_ _p;_ (9)
_|∥_ _∥[2]_ _−∥_ _∥[b][2]| ≤_ _O_ _≤_ _≤_

_|[L[−][1]]ij −_ [L[b][−][1]]ij| ≤ 4∥L[−][1]∥2[2],∞[∥][L][−][T][∥][2][,][∞][(][ϵ][ +][ λ][) =][ O][(][ϵ][)][,] _for i > j._ (10)

_Proof._ For all 1 ≤ _i ≤_ _p, we have_

**_Li,:_** **_Li,:_** = **_Cii_** [Cλ]ii **_C_** **_Cλ_** **_C_** **_C_** + λ _ϵ + λ,_ (11)
_|∥_ _∥[2]_ _−∥_ [b] _∥[2]|_ _|_ _−_ _| ≤∥_ _−_ [b] _∥≤∥_ _−_ [b]∥ _≤_

which completes the proof for (9).

[b]

Next, we show (10). Let

**_L[−][1][ b]L = I + F,_** (I + F )(I + F )[T] = I + E. (12)

We know that

**_L[−][1]_** _−_ **_L[−][1]_** = [(I + F )[−][1] _−_ **_I]L[−][1]_** = −F (I + F )[−][1]L[−][1], (13)

**_E = L[−][1][ b]LL[b][T]L[−][T]_** **_I = L[−][1](Cλ_** **_C)L[−][T]._** (14)

b _−_ _−_

Then it follows from (13) that for i > j

[b]

_|[L[−][1]]ij −[L[b][−][1]]ij| ≤∥Fi,1:i−1∥∥[(I_ +F )[−][1]L[−][1]]:,j∥≤∥Fi,1:i−1∥∥(I +F )[−][1]∥∥L[−][T]∥2,∞. (15)

First, we give an upper bound for ∥(I + F )[−][1]∥. Using (12), we have (I + F )[−][T](I + F )[−][1] =
(I + E)[−][1]. It follows

1 1
_∥(I + F )[−][1]∥_ = ∥(I + F )[−][T](I + F )[−][1]∥ 2 = ∥(I + E)[−][1]∥ 2


1

_,_ (16)
1 **_L[−][1]_** **_Cλ_** **_C_**
_−∥_ _∥[2]∥_ [b] _−_ _∥_


1 −∥E∥


where the last inequality uses (14).


Second, we give upper bound for ∥Fi,1:i−1∥. It follows from the second equality of (12) that

(1 + Fii)[2] + ∥Fi,1:i−1∥[2] = 1 + Eii. (17)

Therefore,


(a) **_L[2]ii_** _[−]_ **_[L]ii[2]_** + Eii
_≤_ **_L[2]ii_**
b


_∥Fi,1:i−1∥[2]_ _≤|(1 + Fii)[2]_ _−_ 1| + Eii


(b) (c)
_≤_ _[ϵ][ +]L[2]ii[ λ]_ + ∥L[−][1]∥2[2],∞[∥]C[b]λ − **_C∥_** _≤_ 2∥L[−][1]∥2[2],∞[(][ϵ][ +][ λ][)][,] (18)

where (a) uses (12), (b) uses (9) and (14), (c) uses ∥C − **_C[b]∥≤_** _ϵ. Substituting (18) and (16) into_
(15), we get

_ϵ + λ_
_|[L[−][1]]ij −_ [L[b][−][1]]ij| ≤ 2∥L[−][1]∥2[2],∞[∥][L][−][T][∥][2][,][∞] 1 **_L[−][1]_** (ϵ + λ) _._ (19)

_−∥_ _∥[2]_

The conclusion follows since ∥L[−][1]∥[2](ϵ + λ) < 4[3] [.] p □


-----

**Theorem A.2matrix. Let x1 Let, . . ., x x ∈n beR[p] nbe a zero-mean random vector, independent samples,** **_C =_** _n C[1]_ =nk E=1([x]xx[k][x][T]k[T]) ∈[be the sample covariance]R[p][×][p] _be the covariance_

_estimator. Assume_ **_C_** **_C_** _ϵ for some ϵ > 0. Denote_ **_Cλ =_** **_C + λI, where λ =_** (ϵ) 0 is a
_∥_ _−_ [b]∥≤ P _O_ _≥_
_parameter. Let the Cholesky factorizations of C = E[b]xx[T]_ _and_ **_Cλ be C = LL[T]_** _and_ **_Cλ =_** **_LL[b][T],_**
_respectively, where L and_ **_L are both lower triangular. For the linear SEM model ([b]_** [b] _1), assume (2)_
_and (4), and for k ∈_ _PaG(j), δ = inf_ _k∈P aG_ (j) δjk > 0, where [b] [b] [b]

[b]

_δjk = σi[2][∗]j_ [+][ ∥]Σ[b] _n[(I −_ **_T )[−][1]]k:j−1,k∥[2]_** _−_ _σi[2][∗]k_ _[.]_

_If δ ≥_ 4(ϵ + λ) and ∥L[−][1]∥[2](ϵ + λ) < [3]4 _[, then][ CDCF][-][V][ is able to recover][ P][ exactly. In addition, it]_

_holds that_

_∥TRIU(Up) −_ **_T ∥max ≤_** 4∥Σ[b] _[−]∗_ [1][(][I][ −] **_[T][ )][T][∥]2[2],∞[∥][(][I][ −]_** **_[T][ )]Σ[b]_** _[−]∗_ [T]∥2,∞(ϵ + λ),

_where TRIU(Up) stands for the strictly upper triangular part of Up, Up is the output of outer loop of_
_Algorithm 1 with criterion (V)._

_Proof._ For SEM model (1), denote **_C∗_** = E( _n[1]_ **_X_** [T][ c]X), **Σ[2]∗** [=][ E][(][ 1]n **_N_** [T][ c]N ) = **Σ[T]n** **Σn, we have (5),**

i.e.,

**_C∗_** = (I − **_T )[−][T][ b]Σ[2]∗[b][(][I][ −]_** **_[T][ )][−][1][c][ = (][I][ −][b][T][ )][−][T][ b]Σ[T]n_** **Σ[c]n(I −** **_T )[b][−][1].[b]_** (20)

When the permutationb **_i[∗]_** = [i[∗]1[, . . ., i]p[∗][]][ is exactly recovered, then][ U][b][p] [in][ CDCF][-][V][ satisfies]

**_Cbλ = n[1]_** **_[X]:[T],i[∗]_** **_[X][:][,][i][∗]_** [+][ λ][I][ =][ U][ −]p [T]Up[−][1][.] (21)


Denote i[∗]j [= [][i]1[∗][, . . ., i][∗]j []][ for all][ j][ = 1][, . . ., p][. Consider the][ k][th diagonal entries of (][20][) and (][21][). By]
calculations, we get



[C∗]kk = [(I − **_T )[−][1]][T]:,kΣ[T]n_** **Σn[(I −** **_T )[−][1]]:,k = σi[2][∗]k_** [+][ ∥][u][k][∥][2][,] (22)

1

[C[b]λ]kk = n[1] _[∥][X][i]k[∗]_ _[∥][2][ +][ λ][ =][b]_ **_U[b]kk[2]_** + ∥uk∥[2], (23)

[b] b


where


**_uk = [Σ[b]_** _n]1:k−1,1:k−1(Ik−1 −_ **_T1:k−1,1:k−1)[−][1]T1:k−1,k,_** **_ubk = n[1]_** **_[U][ T]k−1[X]:[T],i[∗]k−1_** **_[X][:][,i]k[∗]_** _[.]_ (24)

Using ∥C − **_C[b]∥≤_** _ϵ, we have_

_|[C∗]kk −_ [Cλ]kk| ≤∥C − **_C[b]λ∥≤∥C −_** **_C[b]∥_** + λ ≤ _ϵ + λ._ (25)

By Lemma A.1, we have

[b] [b]

**_uk_** **_uk_** _ϵ + λ._ (26)
_|∥_ _∥[2]_ _−∥_ _∥[2]| ≤_

Using (22), (23), (25) and (26), we get

b


_σi[2][∗]k_
_|_ _[−]_


1

2(ϵ + λ). (27)
**_Ukk[2]_** _| ≤_


Assume that i[∗]1[, . . ., i][∗]k 1 [(][k][ ≥] [1][) are all correctly recovered. And without loss of generality, for]
_−_
_kforms another equivalence topology order to the same DAG ( ∈_ _PaG(j), we also assume Tk:j−1,j ̸= 0 (otherwise, jth andSedgewick & Wayne kth columns are exchangeable, and, 2011)). Then we i_


-----

have for k _Pa_ (j) that
_∈_ _G_

1
_j_ **_uj]1:k_** 1 = [C ]jj + [Cλ]jj [C ]jj [uj]1:k 1
_n_ _[∥][X][i][∗]_ _[∥][2][ +][ λ][ −∥][[][b]_ _−_ _∥[2 (][a][)]_ _∗_ _−_ _∗_ _−∥_ _−_ _∥[2]_

(b)

[C[b] ]jj (ϵ[b] + λ) [b][uj]1:k 1 b (ϵ + λ)
_≥_ _∗_ _−_ _−∥_ _−_ _∥[2]_ _−_

(c)
= σi[∗]j [+][ ∥][[][u][j][]][k][:][j][−][1][∥][2][ −] [2(][ϵ][ +][ λ][)]

[b]

(d)
_≥_ _σi[∗]k_ [+][ δ][ −] [2(][ϵ][ +][ λ][)]

(e)
= [C∗]kk −∥uk∥[2] + δ − 2(ϵ + λ)

(f )

[Cλ]kk **_uk_** + δ 4(ϵ + λ)
_≥_ [b] _−∥_ _∥[2]_ _−_

(= g) [1] _k_ _[∥][2][ +][ λ][ −∥]u[b]k_ + δ 4(ϵ + λ),

_n[b][∥][X][i][∗]_ b _∥[2]_ _−_

where (a) uses (23), (b) and (f) uses (25) and Lemma A.1, (c) uses (22), (d) dues to the assumption
_σi[∗]j_ _[≥]_ _[σ][i]k[∗]_ [for][ k][ ∈] _[Pa][G][(][j][)][, (e) uses (][22][), (g) uses (][23][). Therefore, using][ δ >][ 4(][ϵ][ +][ λ][)][, we have]_

1
_n_ _[∥][X][i]j[∗]_ _[∥][2][ +][ λ][ −∥][[]u[b]j]1:k−1∥[2]_ _>_ _n[1]_ _[∥][X][i]k[∗]_ _[∥][2][ +][ λ][ −∥]u[b]k∥[2],_

which implies that i[∗]k [can be correctly recovered. So, overall speaking,][ CDCF][-][V][ is able to recover the]
permutation P .

The upper bound for ∥TRIU(Up) − **_T ∥max follows from Lemma A.1. The proof is completed._** □

**Proposition 2 Let Ni,: be independent bounded, or sub-Gaussian,** [2] _or regular polynomial-tail,_ [3]

_then for n > N_ (ϵ), it holds **_Cxx_** **_Cxx_** _ϵ, w.h.p. Specifically,_
_∥_ [b] _−_ _∥≤_

(I **_T )−1_** 2 **_Cnn_** 2
_N_ (ϵ) _C1 log p_ _∥_ _−_ _∥_ _∥_ _∥_ _,_ _for bounded class;_
_≥_ _ϵ_

(I **_T )−1_** 2 **_Cnn_** 2 
_N_ (ϵ) _C2 p_ _∥_ _−_ _∥_ _∥_ _∥_ _,_ _for the sub-Gaussian class;_
_≥_ _ϵ_
 (I **_T )−1_** 2 **_Cnn_** 2(1+r[−][1])

_N_ (ϵ) _C3 p_ _∥_ _−_ _∥_ _∥_ _∥_ _,_ _for the regular polynomial tail class._
_≥_ _ϵ_
 

_Proof._ For SEM model (1), we have

**_Cxx_** **_Cxx_** (I **_T )[−][1]_** **_Cnn_** **_Cnn_** (I **_T )[−][1]_** **_Cnn_** **_Cnn−_** 2[1] **_CnnCnn−_** 2[1]
_∥_ [b] _−_ _∥≤∥_ _−_ _∥[2]∥_ [b] _−_ _∥≤∥_ _−_ _∥[2]∥_ _∥∥_ _[−]_ **_[I][∥][,][ (28)]_**

where Cxx = Exx[T], Cnn = Enn[T] are the covariance matrices for x and n, respectively, **_Cxx,_** **_Cnn_**
are the sample covariance matrices for x and n, respectively. The three results listed above follow[b]
from Corollary 5.52, Theorem 5.39 in Vershynin (2010), Theorem 1.1 in Srivastava & Vershynin

[b] [b]
(2013), respectively. □


2A random vector z is isotropic and sub-Gaussian if EzzT = I and and there exists constant C > 0 such that

P(|v[T]z| > t) ≤ exp(−Ct[2]) for any unit vector v. Here by “Ni,: is sub-Gaussian” we mean that Cnn− [1]2 **_[N][ T]i,:_** [is]

an isotropic and sub-Gaussian random vector.
3A random vector z is isotropic and regular polynomial-tail if EzzT = I and there exist constants r > 1,
_C > 0 such that P(∥V z∥[2]_ _> t) ≤_ _Ct[−][1][−][r]_ for any orthogonal projection V and any t > C · rank(V ). Here

by “Ni,: is regular polynomial-tail” we mean that Cnn− [1]2 **_[N][ T]i,:_** [is an isotropic and regular polynomial-tail random]

vector.


-----

B ADDITIONAL EXPERIMENTS

Here we provide implementation details and additional experiment results.

Figures B.1, B.2 provide the results of Gumbel and Exponential noises, respectively. As we can see
from the result, our algorithm still performs better than Eqvar method in different noise types.

Tables B.1, B.2, B.3, B.4, B.5, B.6 give results on 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
log p

_n_ **_[I][. The truncation threshold on column][ i][ is][ ω][i][ = 3][.][5][/α][i][, where][ α][i][ 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
_λ = β_ [log]n[ p] _[, β][ ∈{][0][.][0][,][ 1][.][0][...,][ 9][.][0][}][, the result is given in Table][ B.7][,][ B.8][,][ B.9][,][ B.10][. Empirically,]_

_β ∈{1.0, 2.0} achieves better results. In 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 our methods, we provide the results of SHD on 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 log2(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 mean results over ten random seeds. The figures
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 ∈{1500, 3000} and node number ∈{400, 800},
CDCF-S+ achieves better performance. Such trend can also be demonstrated in Tables B.1, 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.

We also test the performance on linear SEM with monotonously increased noise variance. Concretely,
assume the topology order is i = {i1, ..., ip}, we set the noise variance of node k as σk = 1 + ik/p.
We test the results on Gaussian, Gumbel, and Exponential noise with monotonous noise variance. The
results are reported in Tables B.11, B.12 and B.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
to make the relations in the same domain close to 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, NOTEARS-MLP: https://github.com/xunzheng/notears](https://github.com/xunzheng/notears)

[• NPVAR: https://github.com/MingGao97/NPVAR](https://github.com/MingGao97/NPVAR)

[• EQVAR, LISTEN: https://github.com/WY-Chen/EqVarDAG](https://github.com/WY-Chen/EqVarDAG)

[• CORL: https://github.com/huawei-noah/trustworthyAI/tree/master/gcastle](https://github.com/huawei-noah/trustworthyAI/tree/master/gcastle)

[• DAG-GNN: https://github.com/fishmoon1234/DAG-GNN](https://github.com/fishmoon1234/DAG-GNN)


-----

ER2


ER5


SF2


SF5


40

20


20

10


150

100

50


100

50

|Col1|Col2|Col3|CDCF|-V+|Col6|
|---|---|---|---|---|---|
|||||||
||||EV-TD|||
|||||||
|||||||


200 300 400 500 600


200 300 400 500 600


0

200 300 400 500 600


200 300 400 500 600


CDCF-V+
EV-TD


3000

2000

1000

20 40 60 80 100

|Col1|Col2|Col3|CDCF EV-H|-V+ TD|Col6|
|---|---|---|---|---|---|
|||||||
|||||||
|||||||
|||||||


CDCF-V+
EV-HTD

Sample Number


3000

2000

1000

0

20 40 60 80 100

Sample Number


3000

2000

1000

20 40 60 80 100

Sample Number


2000

1000

0

20 40 60 80 100

Sample Number


Figure B.1: Performance (SHD) tested on 100 nodes graph recovered from different sample numbers
with gumbel noise.


ER2


ER5


SF2


SF5


150

100

50


20

10

0

200 300 400 500 600


30

20

10


100

50

|Col1|Col2|Col3|CDCF|-V+|Col6|
|---|---|---|---|---|---|
||||EV-TD|||
|||||||
|||||||


200 300 400 500 600

2000


200 300 400 500 600


200 300 400 500 600

CDCF-V+
EV-TD

2000


3000

2000

1000

20 40 60 80 100

Sample Number


3000

2000

1000

20 40 60 80 100

Sample Number


1000

0

20 40 60 80 100

Sample Number


1000

20 40 60 80 100

|Col1|Col2|Col3|CDCF EV-H|-V+ TD|Col6|
|---|---|---|---|---|---|
|||||||
|||||||
|||||||
|||||||


CDCF-V+
EV-HTD

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.


|Col1|Col2|20|40|60|80|100|
|---|---|---|---|---|---|---|
|ER2|V+ S+ VS+|174.4 173.4 174.7|119.3 120.4 126.6|88.7 92.2 99.8|68.7 71.2 75.1|55.7 57.4 70.7|
|SF2|V+ S+ VS+|170.2 170.1 168.8|128.2 129.2 133.6|99.5 99.8 103.6|77.4 79.5 83.6|53.0 52.1 52.9|
|ER5|V+ S+ VS+|427.0 431.8 434.5|356.9 351.0 354.1|284.2 279.8 277.7|223.6 227.3 225.9|194.4 200.1 193.5|
|SF5|V+ S+ VS+|412.6 409.8 409.5|330.0 332.9 337.7|269.2 266.8 270.9|218.2 215.3 220.5|169.5 167.1 173.5|


-----

Table B.2: SHD results on 100 nodes linear Gumbel noise SEM with low sample size.

|Col1|Col2|20|40|60|80|100|
|---|---|---|---|---|---|---|
|ER2|V+ S+ VS+|177.2 174.8 229.0|151.0 140.5 256.2|148.4 130.6 293.5|141.7 130.2 258.2|119.3 111.7 223.3|
|SF2|V+ S+ VS+|175.8 171.8 202.2|155.7 144.0 208.7|143.4 125.8 187.1|125.2 102.7 152.5|92.4 78.9 100.3|
|ER5|V+ S+ VS+|437.3 435.8 472.1|372.1 358.6 450.1|340.1 327.0 409.5|286.3 278.7 323.5|242.0 248.4 308.2|
|SF5|V+ S+ VS+|417.5 414.2 443.9|358.3 349.8 424.0|314.1 292.0 342.9|240.3 217.8 258.2|178.1 160.0 181.0|


Table B.3: SHD results on 100 nodes linear Exponential noise SEM with low sample size.

|Col1|Col2|20|40|60|80|100|
|---|---|---|---|---|---|---|
|ER2|V+ S+ VS+|171.1 171.2 185.7|132.1 128.3 180.5|104.8 95.5 178.3|90.2 83.0 137.0|80.5 71.1 113.6|
|SF2|V+ S+ VS+|167.0 168.4 170.7|135.1 130.2 165.0|115.4 107.5 131.3|87.4 79.1 100.4|64.8 60.1 67.0|
|ER5|V+ S+ VS+|427.4 432.5 454.0|342.3 335.1 353.3|268.9 265.8 282.2|229.8 217.3 238.3|194.9 184.4 213.5|
|SF5|V+ S+ VS+|408.3 408.8 411.1|341.6 336.7 363.0|272.4 265.9 281.2|212.6 204.5 219.1|160.3 152.2 158.4|


CDCF-V+

6.05.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-S+

5.55.04.54.03.53.02.5

Sample Number(K)


CDCF-VS+

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.3: Performances (log(SHD + 1)) of n as x-axis vs p as y-axis of CDCF-∗+ on ER2 Gaussian
noise.


-----

Table B.4: SHD results on 100 nodes linear Gaussian SEM with different sample size.

|Col1|Col2|200|300|400|500|600|700|800|900|1000|1500|2000|2500|3000|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|ER2|V S VS V+ S+ VS+|114.3 98.4 141.6 21.9 29.1 38.6|32.2 30.3 38.7 7.9 17.6 16.0|11.7 18.6 32.3 4.3 13.5 21.3|4.6 18.4 6.1 2.8 17.2 3.0|2.5 15.3 8.0 2.0 14.6 4.3|1.4 18.5 12.5 1.3 16.3 10.4|1.1 18.2 2.5 1.4 18.5 2.1|0.5 16.0 8.6 0.5 16.3 8.1|0.4 15.4 0.6 0.4 15.3 0.4|0.3 16.5 0.3 0.3 16.5 0.3|0.0 18.1 1.2 0.0 18.1 0.8|0.0 21.9 0.0 0.0 21.8 0.0|0.0 18.5 1.0 0.0 18.5 0.9|
|SF2|V S VS V+ S+ VS+|37.1 27.3 53.7 8.8 11.7 10.8|7.2 7.5 15.4 3.0 4.8 4.1|1.9 6.9 5.0 1.6 7.3 2.1|2.6 3.8 2.4 0.7 3.6 0.6|0.9 4.2 1.9 1.1 4.8 1.3|0.3 4.9 1.3 0.5 5.0 0.4|0.1 3.9 1.1 0.2 4.0 1.6|0.1 3.3 0.2 0.2 3.3 0.2|0.2 3.6 0.2 0.1 4.4 0.1|0.0 5.3 0.1 0.0 5.3 0.1|0.0 5.7 0.0 0.0 5.7 0.0|0.0 3.4 0.3 0.0 3.4 0.3|0.0 4.8 0.0 0.0 4.8 0.0|
|ER5|V S VS V+ S+ VS+|368.7 349.0 426.5 83.0 95.4 88.6|139.6 139.0 177.1 44.2 56.3 47.0|73.8 81.2 87.8 27.8 40.4 27.9|33.2 45.7 36.9 17.5 30.2 18.0|21.5 40.7 21.5 12.5 32.9 11.5|14.0 27.6 15.7 9.2 23.4 9.2|9.5 22.1 11.2 7.0 19.7 8.0|7.0 22.7 12.3 5.1 18.1 7.1|5.8 24.7 5.7 4.7 22.6 5.4|1.5 17.6 2.6 1.3 17.3 1.7|0.6 14.0 1.9 0.7 13.5 2.2|0.0 19.1 0.1 0.0 19.3 0.0|0.0 18.0 0.0 0.1 18.0 0.1|
|SF5|V S VS V+ S+ VS+|92.6 81.2 167.9 40.3 49.3 47.6|31.9 32.1 63.9 21.0 29.0 23.2|12.6 21.8 39.1 15.6 22.8 16.4|6.0 13.4 8.5 8.3 16.0 9.1|4.9 16.9 11.5 7.2 19.3 7.4|3.9 13.5 4.0 5.3 15.3 5.6|2.5 12.6 3.2 4.1 13.9 4.5|1.8 12.3 2.0 2.3 13.1 2.5|1.6 11.4 2.1 2.8 12.8 3.3|0.3 10.1 0.3 0.5 11.8 0.5|0.4 8.9 5.0 0.4 8.9 4.9|0.0 12.3 0.0 0.0 12.4 0.0|0.0 11.6 1.9 0.0 11.6 1.9|



Table B.5: SHD results on 100 nodes linear Gumbel noise SEM with different sample size.

|Col1|Col2|200|300|400|500|600|700|800|900|1000|1500|2000|2500|3000|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|ER2|V S VS V+ S+ VS+|124.7 94.2 145.1 39.8 38.5 68.4|35.1 39.8 55.6 15.6 28.1 30.0|11.8 22.3 20.2 7.3 19.7 13.6|6.5 18.2 10.6 4.0 16.2 6.5|3.6 15.7 22.9 3.0 16.1 17.1|2.2 15.4 5.4 1.5 14.8 4.3|0.8 17.4 12.4 1.2 19.1 12.3|0.6 15.7 3.2 0.5 15.7 0.8|0.9 19.7 1.9 0.9 20.3 1.1|0.4 18.0 0.2 0.4 17.7 0.4|0.0 18.6 0.3 0.0 19.7 0.5|0.1 20.9 7.2 0.1 21.0 7.1|0.0 22.3 1.1 0.0 22.3 1.1|
|SF2|V S VS V+ S+ VS+|46.9 27.7 58.4 12.0 12.8 14.7|8.6 11.3 24.6 4.5 8.4 7.2|1.9 3.5 3.4 1.5 3.2 3.9|0.8 5.4 3.4 0.8 5.3 1.4|0.6 3.7 1.1 0.6 3.6 1.2|0.3 3.3 1.4 0.3 3.4 1.5|0.2 2.9 0.2 0.2 2.8 0.2|0.3 4.0 1.3 0.4 4.2 0.8|0.1 4.8 1.1 0.1 4.7 3.1|0.0 5.6 0.1 0.0 5.6 0.1|0.0 5.6 0.1 0.0 5.6 0.1|0.0 5.3 0.4 0.0 5.3 0.4|0.0 5.5 0.0 0.0 5.5 0.0|
|ER5|V S VS V+ S+ VS+|362.8 338.2 448.6 119.1 128.2 133.6|139.7 138.0 199.8 64.7 72.7 82.8|70.9 84.0 93.9 35.9 49.3 37.3|40.2 53.2 58.3 21.6 36.4 29.0|23.2 37.7 26.3 13.3 28.5 14.6|17.4 31.5 21.8 10.7 27.3 14.0|9.6 21.3 13.7 6.8 19.2 6.9|5.9 28.0 44.1 5.5 24.9 41.4|6.1 21.2 22.3 4.7 18.8 20.6|1.6 16.8 1.3 1.5 17.2 1.4|0.4 16.1 0.8 0.5 16.1 0.7|0.3 19.5 0.8 0.3 17.5 0.7|0.1 16.6 3.8 0.1 16.4 3.6|
|SF5|V S VS V+ S+ VS+|104.4 82.8 177.6 47.2 45.9 48.3|31.9 32.2 95.0 20.2 26.3 23.4|12.0 20.3 31.1 11.0 20.0 17.9|7.6 14.6 21.4 8.1 15.6 8.8|5.2 14.5 12.4 5.8 16.0 6.8|2.9 10.7 5.5 3.6 11.7 5.6|2.4 11.7 4.5 3.3 12.9 4.6|2.1 12.3 7.9 2.2 12.6 4.9|2.7 9.4 20.3 1.9 10.4 8.5|0.5 10.3 0.6 0.5 11.8 0.8|0.2 13.5 0.5 0.3 13.6 0.6|0.1 11.2 0.1 0.1 11.3 0.1|0.0 11.1 0.0 0.0 11.1 0.0|


-----

Table B.6: SHD results on 100 nodes linear Exponential noise SEM with different sample size.

|Col1|Col2|200|300|400|500|600|700|800|900|1000|1500|2000|2500|3000|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|ER2|V S VS V+ S+ VS+|132.1 106.8 138.0 31.8 34.0 44.1|39.0 34.4 53.8 10.7 20.2 22.1|15.3 20.3 23.6 7.5 17.2 12.8|5.9 16.4 12.4 3.4 15.9 6.7|3.7 15.0 6.1 2.0 13.7 3.7|2.5 17.7 3.5 2.5 16.2 2.8|1.3 13.9 4.5 1.2 13.8 3.8|0.6 20.5 5.5 0.8 19.7 5.6|0.7 19.0 14.1 0.7 19.2 13.2|0.2 19.9 0.2 0.2 20.0 0.3|0.0 15.3 3.7 0.0 15.3 4.0|0.2 23.5 0.4 0.2 22.8 0.6|0.0 22.2 0.2 0.0 22.1 0.4|
|SF2|V S VS V+ S+ VS+|55.4 33.9 67.5 12.1 14.4 17.2|17.0 11.4 16.2 3.5 10.5 5.6|5.1 4.3 8.9 3.0 4.3 3.8|2.5 6.0 5.0 0.8 5.8 2.7|0.5 4.7 1.5 0.8 5.0 2.2|1.6 6.1 1.0 0.5 6.1 1.0|0.9 4.4 0.6 0.9 4.4 0.6|0.1 4.2 0.7 0.1 5.0 0.1|0.3 4.3 0.3 0.2 4.3 0.2|0.0 4.1 0.1 0.1 4.1 0.2|0.0 4.1 0.7 0.0 4.1 0.7|0.0 4.9 0.0 0.0 4.9 0.0|0.0 5.7 0.0 0.0 5.6 0.0|
|ER5|V S VS V+ S+ VS+|393.8 361.2 474.7 96.6 95.8 103.8|157.8 154.7 193.9 56.6 66.9 55.8|75.7 80.5 110.3 32.2 41.4 40.0|40.5 51.2 62.5 19.6 33.2 26.1|29.6 44.3 35.6 15.3 32.0 15.8|18.4 34.6 32.1 12.8 27.2 15.5|10.2 28.3 20.0 8.1 23.2 10.6|8.9 19.3 26.4 7.1 20.1 19.3|5.2 24.3 51.6 5.1 21.0 48.1|1.6 16.2 2.5 1.4 14.4 2.0|0.9 16.8 1.3 1.1 16.6 1.0|0.2 18.1 12.0 0.1 19.7 7.3|0.0 15.7 3.1 0.0 14.4 3.1|
|SF5|V S VS V+ S+ VS+|108.9 84.8 203.5 51.0 54.4 56.9|34.9 34.8 80.3 27.9 34.0 26.3|23.1 21.7 35.2 15.5 24.8 17.2|7.5 13.5 11.0 9.1 16.3 10.5|11.6 16.6 5.4 7.1 19.5 7.2|3.2 11.4 10.4 4.7 12.5 5.5|2.7 13.0 9.6 4.8 15.4 8.1|1.6 12.2 3.4 2.6 13.1 3.5|0.6 8.8 0.6 2.4 11.0 2.4|0.6 11.6 0.7 1.2 12.1 1.1|0.1 12.2 4.6 0.2 12.3 4.7|0.0 8.8 2.3 0.0 8.8 2.0|0.0 11.3 0.0 0.0 11.3 0.0|


CDCF-V

6.05.55.04.54.03.53.02.5

Sample Number(K)


CDCF-S

5.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-VS

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.4: Performance (log(SHD + 1)) upper bound of CDCF-* on ER2 Gaussian.


CDCF-V

6.05.55.04.54.03.53.02.5

Sample Number(K)


CDCF-S

5.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-VS

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.5: Performance (log(SHD + 1)) upper bound of CDCF-* on SF2 Gaussian.


-----

CDCF-V+

6.05.55.04.54.03.53.02.5

Sample Number(K)


CDCF-S+

5.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-VS+

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.6: Performance (log(SHD + 1)) upper bound of CDCF-*+ on SF2 Gaussian.


CDCF-V

6.05.55.04.54.03.53.02.5

Sample Number(K)


CDCF-S

5.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-VS

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.7: Performance (log(SHD + 1)) upper bound of CDCF-* on ER2 Exponential.


CDCF-V+

6.05.55.04.54.03.53.02.5

Sample Number(K)


CDCF-S+

5.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-VS+

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.8: Performance (log(SHD + 1)) upper bound of CDCF-*+ on ER2 Exponential.


-----

CDCF-V

6.05.55.04.54.03.53.02.5

Sample Number(K)


CDCF-S

5.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-VS

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.9: Performance (log(SHD + 1)) upper bound of CDCF-* on SF2 Exponential.


CDCF-V+

6.05.55.04.54.03.53.02.5

Sample Number(K)


CDCF-S+

5.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-VS+

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.10: Performance (log(SHD + 1)) upper bound of CDCF-*+ on SF2 Exponential.


CDCF-V

6.05.55.04.54.03.53.02.5

Sample Number(K)


CDCF-S

5.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-VS

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.11: Performance (log(SHD + 1)) upper bound of CDCF-* on ER2 Gumbel.


-----

CDCF-V+

6.05.55.04.54.03.53.02.5

Sample Number(K)


CDCF-S+

5.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-VS+

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.12: Performance (log(SHD + 1)) upper bound of CDCF-*+ on ER2 Gumbel.


CDCF-V

6.05.55.04.54.03.53.02.5

Sample Number(K)


CDCF-S

5.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-VS

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.13: Performance (log(SHD + 1)) upper bound of CDCF-* on SF2 Gumbel.


CDCF-V+

6.05.55.04.54.03.53.02.5

Sample Number(K)


CDCF-S+

5.55.04.54.03.53.02.52.0

Sample Number(K)


CDCF-VS+

6.05.55.04.54.03.53.02.5

Sample Number(K)


15.0

12.5

10.0

7.5

5.0

2.5

0.0


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


800
700
600
500
400
300
200
150
100

50
30


Figure B.14: Performance (log(SHD + 1)) upper bound of CDCF-*+ on SF2 Gumbel.


-----

Table B.7: CDCF-V+ SHD results on different γ with different sample size on 100 nodes linear
Gaussian SEM.

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


-----

Table B.8: CDCF-S+ SHD results on different γ with different sample size on 100 nodes linear
Gaussian SEM.

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


-----

Table B.9: CDCF-VS+ SHD results on different γ with different sample size on 100 nodes linear
Gaussian SEM.

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


-----

Table B.10: CDCF-V+ SHD results on different γ with different sample size on 100 nodes linear
Gumbel SEM.

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


-----

Table B.11: SHD results on 100 nodes linear monotonous Gaussian noise variance SEM with
different sample size.

|Col1|Col2|200|300|400|500|600|700|800|900|1000|1500|2000|2500|3000|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|ER2|V S VS V+ S+ VS+|194.9 167.4 194.0 99.2 91.0 101.2|65.3 59.6 61.3 38.1 39.2 36.7|27.9 30.5 27.3 16.6 23.5 18.3|14.9 20.9 14.6 11.3 17.8 10.6|7.4 15.9 7.7 5.7 14.6 5.6|5.6 14.6 6.5 4.9 13.5 5.4|3.2 15.1 3.2 3.0 14.4 2.8|1.8 14.5 5.9 1.6 14.3 6.6|1.8 11.8 1.3 1.3 11.8 2.2|0.8 11.6 1.2 0.8 12.0 1.2|0.0 12.0 0.8 0.0 11.4 0.8|0.0 15.7 0.2 0.0 15.8 0.2|0.1 14.3 1.5 0.1 14.3 1.5|
|SF2|V S VS V+ S+ VS+|61.1 50.6 58.1 30.9 28.5 29.9|12.9 11.6 11.0 9.0 9.3 8.3|4.8 6.3 4.2 3.5 5.2 3.1|1.8 3.9 2.0 1.6 3.8 1.8|1.6 4.0 1.6 1.6 3.9 1.6|0.6 2.4 0.7 0.6 2.4 0.7|0.5 2.4 2.4 0.5 2.4 2.4|0.4 3.3 0.5 0.4 3.3 0.5|0.2 2.7 0.3 0.2 2.7 0.3|0.0 5.1 0.2 0.0 5.1 0.2|0.0 3.1 0.4 0.0 3.1 0.4|0.0 3.5 1.6 0.0 3.5 1.6|0.0 5.4 0.0 0.0 5.4 0.0|
|ER5|V S VS V+ S+ VS+|527.8 502.4 517.6 252.3 259.3 250.2|246.4 246.8 243.6 141.1 150.0 135.0|159.9 167.3 159.3 95.5 103.8 96.9|95.9 97.1 92.6 61.5 65.5 58.6|58.9 75.8 57.1 43.2 61.5 41.4|42.5 51.4 42.4 30.0 39.4 31.3|30.6 40.0 30.9 21.7 32.9 21.9|21.7 32.8 21.9 16.6 27.2 16.3|19.2 29.7 20.0 15.5 25.5 16.5|5.6 18.2 5.7 4.7 16.5 4.9|3.0 14.9 2.9 2.2 14.8 2.7|0.5 15.3 1.0 0.4 14.8 0.8|0.8 16.3 1.3 0.8 16.3 1.2|
|SF5|V S VS V+ S+ VS+|126.4 116.5 123.8 70.2 74.1 70.8|42.8 44.9 40.8 28.4 33.9 28.5|19.8 25.9 21.2 14.8 21.1 17.1|9.3 14.9 8.9 8.8 14.0 8.4|7.6 13.8 7.4 6.8 12.9 6.7|5.9 14.3 5.5 5.9 14.6 5.9|3.7 11.9 4.1 3.8 11.8 3.9|2.8 11.1 3.0 2.3 10.5 2.4|2.5 10.4 2.5 2.5 10.5 2.5|0.5 8.7 0.5 0.7 8.9 0.7|0.4 7.7 0.4 0.4 7.7 0.4|0.0 10.0 0.0 0.0 10.2 0.1|0.0 8.3 0.0 0.0 8.3 0.0|



Table B.12: SHD results on 100 nodes linear monotonous Gumbel noise variance SEM with
different sample size.

|Col1|Col2|200|300|400|500|600|700|800|900|1000|1500|2000|2500|3000|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|ER2|V S VS V+ S+ VS+|202.5 172.8 190.5 131.8 123.1 126.2|68.8 65.4 64.7 48.5 52.7 48.2|28.3 28.9 27.4 23.0 23.3 20.7|13.9 18.7 13.6 11.0 17.3 11.3|8.6 15.4 7.5 7.2 15.1 5.7|4.7 18.1 6.6 3.9 17.0 6.7|3.5 14.3 3.7 3.0 14.2 3.4|2.0 11.5 6.2 1.5 11.1 5.6|2.0 15.5 1.6 1.9 14.7 1.6|1.0 16.1 1.0 0.9 16.2 1.1|0.0 13.7 1.2 0.0 13.8 1.0|0.2 14.9 0.3 0.2 14.9 0.3|0.0 16.1 5.8 0.0 16.1 5.8|
|SF2|V S VS V+ S+ VS+|62.4 53.4 59.8 41.5 37.3 39.5|14.0 12.0 13.6 10.5 9.4 10.3|3.5 4.4 3.3 2.7 3.6 2.3|1.6 4.6 1.5 1.5 4.5 1.5|0.9 4.5 0.8 0.8 4.5 0.8|0.8 2.8 0.6 0.9 3.0 0.9|0.7 2.3 0.8 0.6 2.2 0.7|0.5 2.7 0.6 0.5 2.7 0.6|0.2 2.6 0.4 0.2 2.6 0.4|0.0 4.6 0.0 0.0 4.6 0.0|0.0 3.9 0.0 0.0 3.9 0.0|0.0 2.9 0.0 0.0 2.9 0.0|0.0 3.1 0.0 0.0 3.1 0.0|
|ER5|V S VS V+ S+ VS+|519.8 501.4 511.6 315.2 318.4 315.6|254.2 246.8 246.0 173.1 175.0 167.3|142.4 152.0 140.9 100.9 112.9 100.5|100.4 107.4 95.6 75.3 83.4 72.1|63.9 77.6 63.6 51.4 66.9 51.0|43.3 52.9 41.6 35.2 42.4 34.0|32.8 40.9 33.1 27.4 36.8 27.8|23.7 33.7 23.0 19.1 28.9 19.3|20.7 35.9 20.1 16.9 34.3 17.7|7.3 20.2 11.4 6.3 19.7 10.2|2.8 17.0 4.7 2.2 17.6 4.2|1.3 12.8 1.4 1.2 12.6 1.3|0.5 14.0 3.3 0.5 14.1 3.3|
|SF5|V S VS V+ S+ VS+|137.5 128.1 132.5 89.7 89.3 85.0|49.4 47.1 44.2 33.1 37.1 32.2|18.7 25.7 19.2 15.4 22.6 15.5|10.1 15.9 10.3 10.1 15.9 11.3|6.7 16.4 8.7 6.8 16.9 8.5|4.9 11.5 5.6 5.0 11.5 5.8|3.8 11.3 4.1 4.0 11.6 4.4|2.3 10.1 2.5 2.4 10.2 2.6|1.9 8.5 1.9 1.9 8.5 1.9|0.8 10.1 0.8 0.7 10.0 0.7|0.2 9.2 0.2 0.2 9.2 0.2|0.1 9.1 0.1 0.1 9.0 0.1|0.0 12.5 0.0 0.0 12.5 0.0|


-----

Table B.13: SHD results on 100 nodes linear monotonous Exponential noise variance SEM with
different sample size.

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


-----

