ML4C: Seeing Causality Through Latent Vicinity
Authors: Haoyue Dai
Rui Ding
Yuanyuan Jiang
Shi Han
Dongmei Zhang
Venue: NeurIPS 2021 Submitted (2021)
Keywords: causal discovery
supervised causal learning
vicinity
conditional dependency
entanglement
learnability

Abstract: Supervised Causal Learning (SCL) aims to learn causal relations from observational data by accessing previously seen datasets associated with ground truth causal relations. This paper presents a first attempt at addressing a fundamental question: What are the benefits from supervision and how does it benefit? Starting from seeing that SCL is not better than random guessing if the learning target is non-identifiable a priori, we propose a two-phase paradigm for SCL by explicitly considering structure identifiability. Following this paradigm, we tackle the problem of SCL on discrete data and propose ML4C. The core of ML4C is a binary classifier with a novel learning target: it classifies whether an Unshielded Triple (UT) is a v-structure or not. Starting from an input dataset with the corresponding skeleton provided, ML4C orients each UT once it is classified as a v-structure. These v-structures are together used to construct the final output. To address the fundamental question of SCL, we propose a principled method for ML4C featurization: we exploit the vicinity of a given UT (i.e., the neighbors of UT in skeleton), and derive features by considering the conditional dependencies and structural entanglement within the vicinity. We further prove that ML4C is asymptotically perfect. Last but foremost, thorough experiments conducted on benchmark datasets demonstrate that ML4C remarkably outperforms other state-of-the-art algorithms in terms of accuracy, robustness and transferability. In summary, ML4C shows promising results on validating the effectiveness of supervision for causal learning.

ML4C: Seeing Causality Through Latent Vicinity
Anonymous Author(s) Affiliation Address email
Abstract
Supervised Causal Learning (SCL.) aims learn causal relations from observational data by accessing previously seen datasets associated with ground truth causal relations. This paper presents first attempt at addressing fundamental question: What are the benefits from supervision and how does it benefit? Starting from sceing that SCL is not better than random guessing if the learning target is non-identifiable a priori, we propose a two-phase paradigm for SCL by explicitly considering structure identifiability. Following this paradigm, we tackle the problem of SCL on discrete data and propose ML4C. The core of ML4C is binary classifier with a novel learning target: classifies whether an Unshielded Triple (UT) a v-structure not. Starting from an input dataset with the corresponding skeleton provided, ML,4C orients each UT once is classified as v-structure. These v-structures are together used to construct the final output. To address the fundamental question of SCL,, we propose principled method for ML featurization: we exploit the vicinity of given UT (i.e., the neighbors of UT in skeleton), and derive features by considering the conditional dependencies and structural entanglement within the vicinity. We further prove that ML4C is asymptotically perfect. Last but foremost, thorough experiments conducted on benchmark datasets demonstrate that ML4C remarkably outperforms other ofate-of-the-an art algorithms in terms of accuracy, robustness and transferability. summary, ML4C shows promising results on validating the effectiveness of supervision for causal learning.
11
13
15
17
19
20
1 Introduction
21
22
The problem of causal learning is to learn causal relations from observational data 13] The learned causal relations are typically represented in the form of Directed Acyclic Graph (DAG), where each edge the DAG indicates direct cause-effect relation between the parent node and child node.
23
24
25
The methods of causal learning mostly fall into four categories: constraint-based score-based, continuous optimization method and functional causal models. Each of these methods takes a given dataset as input and outputs a DAG but with different criteria. For instance, the DAG should be consistent with conditional independencies in the data connstraint-assedy or it is optimal w.r.t. pre-defined score function under either combinatorial constraint accore-baed]] or continuous equality constraint (continuous optimization). nutshell, these methods can be viewed as unsupervised since they do not access additional datasets associated with ground truth causal relations.
26
27
28
29
30
31
32
new line of research called Supervised Causal Learning (SCL), on the other hand, aims learn causal relations in the supervised fashion: the algorithm has access to datasets associated with
33
34 ground truth causal relations, in the hope that such supervision is beneficial to learning causal
35 relations on newly unseen datasets. Despite several existing works on this direction (see Related
36 Work), a fundamental question remains unanswered: How supervised causal learning possible?
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

Cata ORSFDOUIIO
Queey
Phane
Weat the onfentationn
Unch Tiples
Maok nules
Festiraation
N 1
Irpur
OPDAG
(a)
(b)
Figure I: (a) Two-phase paradigm for supervised causal learning, (b) ML4C's workflow.
37 Specifically, compared with unsupervised causal learning methods, can we gain additional benefits from supervision? If the answer is positive, then what the benefits and how does it benefit?
38
39 We tackle the problem by first seeing crucial connection between SCL and causal structure identi- fiability. Considering the problem of causal learning discrete data, theorem in (44] states that, under standard assumptions (i.e., Markov assumption, faithfulness and causal sufficiency), we can only identify graph up to its Markov equivalence class. Markov equivalence class is the set of DAGs having same skeleton and same v-structures, which can be represented by CPDAG (Com- pleted Partially Directed Acyclic Graph). Thus, the (un)directed edges in the CPDAG indicate (non-)identin)) jidentifiable causal relations. Each non- -ddettiiiiee edge in CPDAG can be oriented by either direction to equivalently fit the observational data. Given an SCL algorithm with learning target as the orientation of an edge, we see that it is not better than random guessing (or could he worse due to sample bias in training data) to predict any non-identifiable edge since we can assign either X - Y or X + Y with same input dataset. This statement is applicable to general learning target since an SCL algorithm can take different target such as orientation of an edge, the whole DAG, or others.
41
43
45
47
49
50
Proposition 1. If the learning target is non-identifiable (i.e., every edge in the target is non- identifiable) a priori, then SCL is not better than random guessing.
52
Consequently, we propose and advocate a two-phase paradigm for SCL, as depicted in Figure [a): 54 phase one corresponds to a binary classification task, where an SCL algorithm needs to classify whether specific learning target is identifiable or not; only if it is classified as identifiable, then we
53
55
56 go to phase two to classify the specific orientation of the learning target. Following this paradigm, we tackle the problem of SCL on discrete data and propose an algorithm ML4C. The core of ML4C is a binary classifier with novel learning target: it classifies whether an Unshielded Triple (UT:
57
58
59
triple of variables T.T,Y) where X and Y are adjacent to but are not adjacent to each other) is v-structure or not. Starting from an input dataset with the corresponding skeleton provided, MLLC orients each UT once is classified as a v-structure. These v-structures are further used to construct CPDAG as output. Such a single classifier facilitates both learning tasks in the two phases, since an identifiable UT implies that is a v-structure (3] (i.e., up to the partial DAG before applying Meek rules 23 which is a standard post processing).
60
61
63
85
To address the fundamental question of SCL, we propose principled method for ML4C featurization. Specifically, we exploit the vicinity of given UT (i.c., the neighbors of UT in skeleton), and derive features by considering the conditional dependencies and structural entanglement within the vicinity.
86
67
68 We further define discriminative predicate (i.e., binary predicate function with domain as MLAC's feature set) and prove that there exist weak discriminative predicates and strong discriminative predicates (i.e., values of the predicates are one-to-one correspondence with ground truth labels).
69
70
71 We further prove that ML4C is asymptotically perfect. Last but foremost, thorough experiments on benchmark datasets demonstrate that ML4C remarkably outperforms other state-of-the-ar algorithms
73 w.r.t. accuracy, robustness and transferability. Our main contributions are summarized as follows:
74 1. We advocate the two-phase paradigm for SCL with consideration of causal structure identifiability.
75 We propose an SCL algorithm ML4C, with the following novelties: i) Learning Target: The core of ML4C is binary classifier with the orientation of a UT as its learning target to address the two-
77 phase tasks simultaneously. ii) Featurization: principled method to exploit vicinity information in terms of dependencies and entanglement of given UT. iii Learnability: We prove that ML4C

---

79
is asymptotically perfect. iv) Empirical Performance: Experiments conducted on benchmark
80
datasets demonstrate that ML4C remarkably outperforms other ttate-of-the-an art algorithms.
Related Work
81
We divide literature on causal learning into supervised and unsupervised approaches, depending on whether additional datasets (associated with ground truth causal relations) are accessed (supervised) or not (unsupervised). In the literature of unsupervised causal learning, constraint-based methods aim to identify DAG which consistent with conditional independencies. The learning procedure of constraint-based methods first identifies the corresponding skeleton and then conducts orientation
83
84
85
86
87
based on v-structure identification (4] The typical algorithm is PC [31. and there are also PC- derived algorithms such as Conservative-Pe [26], PC-stable 77] and Consistent-Per [19] which improve the robustness on v-structure identification. Score-based methods aim to find the DAG which optimal w.r.t. pre-defined score function under combinatorial constraint by specific search procedure, such as -arrurrd--awwrdddd search GES [6. hill-climbing [T6], integer programming (8) or by approximate algorithms based order search [27]. Continuous optimization methods transform the discrete search procedure into continuous equality constraint: NOTEARS (36] formulates the acyclic constraint continuous equality constraint, it is further extended by DAG-GNN 33 to support learning non-linear causal relations.
89
91
99
85
SCL emerges from the task of orienting edge in the continuous, non-linear bivariate case under Functional Causal Model (FCM) formalism. Given a collection of cause-effect samples (dataset binary label indicating whether X Y or X < Y), supervised approaches such as RCC (20). [4] and Jarfo [2] achieve better performance on predicting pairwise relations (i.c.,
97
NCC 121, D2C
99
orientation of edge) than unsupervised approaches such as ANM [4] or IGCI [15]. Differently. sets the learning target as the whole DAG structure instead of pairwise relation and it applied on
101
18
data which is generated by linear Structural Equation Model (SEM). We summarize the differences in problem space between ML4C and the other SCL approaches as follows: i) We advocate a two-phase learning paradigm and emphasize the relationship between identifiability and learnability. Specifically, presuming additive noise model [4] or linear SEM with non-Gaussian noise (29 provides license identifiability thus the aforementioned approaches
103
104
105
106
be viewed as specific tasks in phase two. ii We tackle SCL's lcarnability not only via empirical evaluation but also by theoretical analysis to
107
108
shed light on the fundamental question of learnability. iii) ML4C deals with discrete data while other approaches mainly focus on continuous data.
109
3
Background
110
111
3.1
Basic Notations
112
discrete dataset D, consists of n, records and d, categorical columns, which represents n; instances drawn i.i.d. from d; discrete variables X1, X2, Xx. by joint probability distribution P.. which entailed by an underlying data generating process, denoted as DAG G..
113
114
115
Markoy factorization property:
Given joint probability distribution P and a DAG G, P is said to
satisfy Markov factorization property w.r.t. if P := P (X,,, "., = I P (X..laa)) where paς is the parent set of X; in G.
116
118
Markoy assumption: P is said satisfy Markov assumption (or Markovian) w.r.t DAG G if X Z = X XLYIZ. Here Le denotes d-separation, and 1 denotes statistical independence. Markov assumption indicates that any d-separation in graph G implies conditional independence in distribution P. Markov assumption is equivalent to Markov factorization property [7.
119
120
122
Faithfulness: Distribution P is faithful w.r.t. a DAG if X Z = XLGYIZ.
123
Canonical dataset: We say discrete dataset canonical underlying probability distribution
P is Markovian and faithful w.r.t some DAG G.
3

---

125
3.2
Causal Structure Identifiability
126
Identifiability discusses which parts of the causal structure can in principle be inferred from the distribution. Below we present the established theory of identifiability on discrete data.
127
128
Causal sufficiency: There no latent common causes of any of the variables in the graph.
129
Definition 1 (Markov equivalence). Two graphs are Markov equivalent if and only if they have same skeleton and same v-slructures. A Markov equivalence class can be represented by a CPDAG having both directed and undirected edges. A CPDAG can be derived from a DAG G, denoted as CP). The theorem of Markov completeness in [24] states that, under causal sufficiency, we can only identify causal graph up to its Markov equivalence class on canonical data. Therefore, the (non-)idee Jddetifiablc causal relations are the (un)directed edges in the CPDAG, Formally,
130
131
132
133
134
135
Definition& 2 (ldentifiabilitty. Assuming P is Markovian and faithful w.r.l. a DAG G and causal sufficiency, then each (un)directed edge in CPDAG(G) indicates inon-jidentffabll causal relation.
136
137
3.3
MLAC Related Notations
138
Definition (Skeleton). A skeleton E defined over distribution P 1X,,X22... .Xa) is an undirected graph such that there an edge between X; and X; if and only if X; and Xj are always dependent, s.1. X,LX;IZ. Skeleton is a statistical concept, which can be obtained prior to facilitating various downstream tasks. Recently, there have been some novel skeleton learning algorithms such as [10]. In particular, skeleton can be used for causal learning:
139
i.e. AZ C X2,,X2.... _Xa}
140
142
143
theorem in [32] states that if distribution P is Markovian and faithful w.r.t. a DAG G, then skeleton
144
E' is the same as the undirected graph of G.
145
Definition& 4 (UT). triple of variables (X,T,Y) in a skeleton is an unshielded triple, or short for UT, if X and Y are adjacent to T but are not adjacent to each other. XXT.YY Y) can be further called the collider.
146
147
oriented to become a v-structure X T t- Y, in which
Definition& 5 (PC). Denote the set of parents and children of X in a skeleton as PCx, in other words, PCx are the neighbors of X in the skeleton. For convenience. if we discuss PCx in the context of a UT (X, T, Y)), we intentionally mean the set of parents and children of X but exclude T.
149
151
Definition (Vicinity). We define the vicinity of UT (X,T.Y) as ViX,T.Y) == YUUPCXU
152
PCy PCT. Vicinity is a generalized version of PC, i.e. the neighbors of {X,T, }} in the skeleton.
153
ML4C's training set: The training set is a collection of discrete datasets D1.-.. Dn, where each dataset D; is associated with ground truth DAG G, such that D, is sampled from G,. G, derives labels (depends on the chosen learning target), thus (D;, Ge, .n. form MLAC's training set.
154
155
156
We can sample graphs from DAG space and generate corresponding datasets, thus obtaining training set in our problem is straightforward.
157
Approach
158
159
4.1
Overview
180
The core of iL4C binary classifier called MLAC-Learner, which takes the orientation of UT as its learning target, i.e., it classifies whether an input UT (X, T. T) is a v-structure (orientation:
161
T Y) or not (orientation remains unknown). Figure [bb) depicts the overall workflow of X
162
163
ML4C, which is composed of ML4C-Leamer with other important inductive biases. Starting from an input dataset D, with corresponding skeleton E,, we first obtain all the UTs from E,. Featurization then conducted to represent each UT as an embedded vector, which is further fed into MLACCLearree In the inference stage, we obtain all the v-structures which are classified by MIAC-Leeame reconstruct partial DAG and then, CPDAG is output by applying Meek rules on the partial DAG. In the training stage, the label of each UT is obtained by querying from ground truth DAG G.. We collect labeled data from multiple datasets in MLAC's training set.
164
165
186
and
167
168
170
Proposition 2. If MLAC-Learner a perfect classifier, then ML4C outputs correct CPDAG of a canonical dataset (i.e,, MLLCC is perfect).
172 By Markov completeness, the set of v-structures invariant across all Markov equivalent DAGs for canonical dataset, and it can fully recover the CPDAG, provided that the skeleton is given. Thus,

---

174
besides its dedicated role in phase 2, MLAC-Learner also facilitates learning task in phase since an identifiable UT implies that is a v-structure (up the partial DAG before applying Meek rules).
175
178
4.2
Featurization
177
We propose a principled method for MLAC-Leamer's featurization, which avoids the need of hand- crafted features. More importantly, we further prove that MIAC-Learner is asymptotically perfect.
178
Our key aspect of fcaturization is to broaden focus from specifie UT (, Y) to its vicinity and seeking conditional dependencies and structural entanglement within the vicinity, to reveal reliable and robust asymmetry to distinguish v-structure and non-v-structure UTs. Specifically, conditional dependencies are the key materials for traditional causal learning methods (e.g.. condi- tional independences for constraint- based methods), and structural entanglement (e.g.. PCx PCr) are relevant to identifiability: higher entanglement makes the UT less likely to be identifiable.
Design Principles:
180
182
184
Dependencies within Vicinity
186
Denoted as X ~ YIZ, which is non-negative scalar that measures the dependence between two random variables X and Y given variable set Z. Operationally. X ~ Y composed of two parts, bivariable X ~ Y, and conditional Z. We further extend the definition to allow a set of variables in bivariable, and an ensemble (i.c., a set of set) as conditional:
Conditional dependency:
187
188
189
Extended conditional dependency: Denoted A B (X Y :X A, B,
191
2), 3.. where and are set of variables, and 2 is an ensemble. Thus, extended conditional
192
dependency is set of scalars.
195
Within the vicinity of (X,T,Y), "7... we start from measuring dependencies between {X, PCx) ) and (Y, } by conditioning on (T. PCr). Intuitively, if (X, T, ) is v-structure, conditioning on or T's descendants tends to strengthen the dependency between PCx and PCy since the paths passing X - T Y are unblocked; otherwise, conditioning on T tends weaken the dependency between PC' x and PCy because blocks the paths passing X - T Y. Therefore, such conditional dependencies reflect potential asymmetry to distinguish v-structure and non vontuustrc Formally,
195
197
Definition 7 (Domain of bivariable). Denoted
{X, PCx) x {Y, PCy} = {X ~ Y,X ~ PCx ~ PC ~ PCy}, }, here symbol x is Cartesian product.
IB
200
201
Definition (Sepsets). Denoted as == (S: XLYSS, S PCx UT, or S C PCy UT}. Under faithfulness assumption, sepsets S is an ensemble where each item is subset of variables within the vicinity that d-separates X and Y.
203
204
Definition 9 (Domain of conditional). Denoted as C =
(0,T,PCT) V (Ø =
[2. T, PCr, S, S. PC where PCr == =(I) IE PCr) which is ensemble version of PCT, and S v PCT == (SUI:S S. PCT). Here symbol V is element-wise union.
206
207
We exploit the extended conditional dependencies from B x C, i.e., we pick bivariable from B and a conditional from C, and calculate the extended conditional dependency. There are in total
208
209
B
[C| 24 extended conditional dependencies.
210
Lemma 1. Sepsets S of any UT of a canonical dataset is non-empty. All proofs are available in the supplementary material.
212
We intend to restrict the sepsets within the vicinity of (X,T,Y). Lemma 7 shows the existence of such d-separation sets within vicinity. Furthermore, searching for all d-separation sets highly time-consuming, thus the computational cost can also be saved drastically.
Remark 1.
213
214
215
Entanglement within Vicinity
216 Structural entanglement reflects complex structure within the vicinity of (X, T,YY.. Variables X, Y and T can mutually share common neighbors, and their neighbors may also overlap with sepsets S. We call such overlaps structural entanglement. Intuitively, stronger entanglement indicates denser structure of vicinity thus making the UT less likely to identifiable. Therefore, structural entanglement is an important aspect for featurization. Specifically, we exploit the overlap coefficient
217
219
221
33 to measure the entanglement:
Definition 10 (Overlap coefficient). OLP (A, B) == AA min [[A), where A and B are
222
nwo sets of variables. We extend this formula to support ensemble input:
5

---

Naturally, we consider the entanglement terms of overlap coefficient on each pair of items in domain {PCx, PCy, PCr,S) Thus, use 6 scalars to represent the entanglement within the vicinity of UT. 225
(Extended) Overlap coefficient: OLP OLP (A, E OLP (A) /|S].
227
Embedding
228
We aim to represent the dependencies and entanglement by feature vector with fixed dimensionality, which can be used train ML4C-Leamen Regarding each extended conditional dependency A ~
230
B Z A ~ B E B, 2 E C, it consists of a set of scalars with varied set size across UTs, we adopt the kernel mean embedding technique in [30] to represent each A B as a vector with
231
232
fixed dimensionality. We further modify the embedding algorithm by adding min {A ~ B 2 and
233
additional features. We directly use the 6 scalars to represent structural entanglement without further transformation. We concatenate all the embedded vectors to form the
max (A B 2)
234
235
final feature vector, as input for MLAC-Leamer.
236
4.3
Learnability
237
We have presented ML4C's featurization and started seeing that conditional dependencies and structural entanglement have potential to reveal asymmetry distinguish v-structure and non-v- structure UT's. Now we provide rigorous analysis to show that, for a canonical dataset with sufficient samples, MIAAC-Lernnr tends to a perfect classifier. To prove this, we first propose a surrogate object called discriminative predicate:
238
239
240
242
Definition 11 (Diseriminative predicate). A discriminative predicate is a binary predicate function with domain as ML4C's feature set. discriminative predicate can be viewed as a special classifier with pre-specified form of mechanism (i.e., not learned from data).
243
244
245
Definition 12 (Weak/ Strong discriminative predicate). Whenever a discriminative predicate takes the feature vector of a UT as input, weak discriminative predicate satisfies one of the following two criteria; a strong discriminative predicate satisfies both: i) it is evaluated to TRUE if the UT is vtstructure; ii) it is evaluated to FALSE if the UT is not a v-structure.
246
247
248
By definition, weak discriminative predicate exhibits discriminative power since it is evaluated false implics the UT is a non-v-structure (or true implics v-structure). A strong discriminative predicate perfect classifier. Denote {A B B ó := X ~ Y Z > 8 VX A, e B, Z E 2, then we have:
250
can be viewed
252
253
Lemma (Existence of weak discriminative predicate). For a canonical dataset with infinite samples, the following are three weak discrininative predicates: i) {X Y|T)== > 0. ii) {X ~ Y|PCT) = 0
255
iij [PCx ~ PSy|S [TT) > O. Take {X ~ Y[]] > 0 as an example, T.Y) is a v-structure
256
= T is collider = T unblocks X and Y through path X - T -T-Y = {x ~ YIT) 0
257
min X ~ Y > O, where min (X ~ Y|T} is a feature of ML4C-Learner since X Y
B. (T)
Lemma 3 (Existence of strong discriminative predicate). For canonical dataset with infinite samples, the following are three strong discriminative predicates: i) OLP(T, = 0, ii) OLP(T, < 0.5, iii) OLP(T, 8) < 1 min (X Y U S} > 0.
260
282
CPCMPC//LI-MB as special cases of MLAC-Learner: Predicate OLP (T, = < VS e S. T S. which states that the predicate is TRUE T is not in any d-separation set of and Y. Having correct skeleton provided. this is the criterion of Conservative PC algorithm (CPC) (25 for identifying v-structures. Thus, CPC can be viewed as special case of ML4C by replacing ML4C- Leamer with such pre-specified logic; OL.P (T, S) < 0.5 indicates that if more than half of the d- separation sets do not contain T, then the UT is oriented as a v-structure, which is called majority rule PC algorithm (MPC) [9]: predicate OLP ST. < 1 A min {X ~ Y > 0 = ES E S, T & S and X and Y are dependent when conditioning on T U.S, which is used for GLL-MB 2 more securely identify v-structures. These predicates are with suboptimal performance because only small portion of features are exploited and the overall loss function of training data is disregarded, thus in practice when an appropriate machine learning model is adopted, MLAC-Leamne achieves better performance.
263
284
285
266
267
268
269
271
273
274
Theorem 1. MLAC-Leamer tends to a perfect classifier on classifying a canonical datasel with
sufficient samples.

---

5
Evaluation
278
277
Benchmark Datasets We use discrete datasets sampled by all 24 networks from bnllean reposi-
278
tory [28] for evaluation. For each network, we sample 1k, 5k, 10k, 15k, 20k records for use.
ML4C's Training and Inference We generate ML4C's training data synthetically (which is also used for other SCL competitors). Specifically. 400 unique DAGs are randomly generated by two models: Erdös-Réss Rényi (ER) model [TT] and Scale-Free (SF) model [.. with the number of nodes ranging from 10 to 1,000. A standard random forward data generation process is applied to obtain 10k observational samples for each graph. We further extract UTs from the 400 DAGs, consisting of
280
282
283
284
97,01 970010 v-structures (label = 1) and 195,691 non-v-structures (label = 0). We use these instances to train ML4C-Learner which is implemented by XGBoost [5] binary classifier with default hyper- parameters and we use binary cross-entropy as the loss function. Details on our synthesis procedure, configurations and implementation of MLAC-Leamer are available in the supplementary material.
285
286
287
288
We categorize state-of of-te-of--h-harr the-art causal learning algorithms from two aspects, supervised vs. unsupervised, and can or cannot take skeleton as input. We choose Jarfo [2]. D2C [4. RCC 20),
Competitors
and NCC [21] as SCL. competitors. Same as MIAC, all these algorithms can and do require skeleton as input. All these algorithms use ML4C's training set for training but with different learning target extracted. Regarding unsupervised algorithms, we choose PC [31, Conservative-Pe (CPC) [26).
290
292
283
Majority-rule PC (MPC) 77 GLL-MB (GMB) (2). GES (6. Grow-Shrink (GS) (22], Hill-Climbing
284
(HC) [16), and Conditional Distribution Similarity (CDS) 12). which can also take skeleton as input. Lastly, we also compare with DAG-GNN (DGNN)
285
K5 BLIP (27], and GOBNILP (GNIP) [],
296
which are unsupervised algorithms but cannot take skeleton as input. All these competitors are capable of dealing with discrete data. All experiments are done in a Windows Server with 2.8GHz Intel E5-2680 CPU and 256G RAM. Details are in the supplementary material.
297
298
Our evaluation mainly consists of two parts: end-to-end comparison with competitors benchmark datasets, and in-depth experiments on ML4C's learnability. The latter is further divided into four aspects: i) Towards a perfect classifier. As stated in proposition proposition 2 ML4C- Learner is the core component and we would like to know how far it is from a perfect classifier. Reliability (against weak / strong discriminative predicates). As stated in lemma and 3 there exist weak and strong discriminative predicates, which have discriminative power and thus are helpful for ML4C-Learner. Some strong discriminative predicates are equivalent to specific logics of existing work such as CPC or GLL-MB. Thus, we would like to see how MLAC-Learner takes the advantage of machine learning, to learn a more reliable classification mechanism (which is also latent and more sophisticated) than individual weak / strong discriminative predicates. iii) Robustness (against varied sample size). It is known that many causal learning algorithms lack robustness w.r.t sample noise for finite datasets 120] especially CI tests are error-prone small samples for constraint- based algorithms. We would like to evaluate the robustness of MLAC (i.e., the latent classification mechanism) against varied sample sizes. iv) Transferability. It's important for machine learning model to generalize well to various types of testing data which are different from training data, such as different scale (#nodes), graph sparsity, different generating mechanisms, etc.
Design
300
301
302
303
304
305
308
307
308
309
311
312
313
315
Metrics We use two standard metrics for performance evaluation: Structural Hamming Distance (SHD) and F1-score. For each dataset, we measure the SHD / Fl-score of the output CPDAG (learned by a specific algorithm) against the ground truth CPDAG. Specifically, SHD is calculated at CPDAG level, which is the smallest number of edge additions, deletions, direction reversals and type changes (directed vs. undirected) to convert the output CPDAG to ground truth CPDAG. F1-score is calculated over identifiable edges. Roughly, Fl Fcore can be viewed as a normalized version of SHD. Now we present the experiment results:
316
317
319
320
321
322
End-to-End Comparison Due to page limit, we report SHD and F1-score of all algorithms on 19 large-scal scale datasets (full results including other 5 smallest and trivial datasets are available in the supplementary material), as depicted in Table
323
324
means the algorithm fails on the dataset (either out-of-memory exceeds 24 hours execution time break caused by unknown errors). ML4C significantly outperforms all other competitors. The average F1-score of MIAC is the highest (0.92, first column in Table 2 Moreover, MLAC exhibits the most stable performance across all datasets, its average ranking 1.5 + 0.7, while the second best is GLL-MB (GMB), with average ranking
325
327
7

---

Table 1: Experiment results for end-to-end comparison with SOTA causal learning algorithms benchmark datasets. Algorithm names are abbreviated. SHD and Fl-score are reported. The last two rows show statistics of rank by SHD and Fl-score for all competitors (Note: Fl-score is UT level).
Datasets #nodes//edges
supervised
unsupervised
no skeleton input
MI.4C
Jarfo
D2C
RCC NCC
PC
CPC:
MPC
GMB
GES
GS
HC
CDS
DGNN
BLIP
GNIP
child
SHD
18
16
18
20
13
9
20
15
13.
13
18
33
0
0
20/25
1.0
24
43
.12
.12
.00
.74
.12
.47
.99
.57
.34
1.0
1.0
insurance
SHID
41
30
28
36
34
21
29
34
28
19
36
35
14
27/52
F1
.89
26
44
.44
.39
.00
86
.55
.46
56
.76
.36
51
.22
water
SHD
33
43
31
0
4
60
7
8
38
27
18
18
61
65
52
32/66
F1
.44
32
.34
.56
1.0
.97
.00
91
.87
.49
.62
.46
.76
.00
20
.00
mildew
SHD
6
17
25
34
21
7
3
23
18
36
35/46
Fl
.87
.68
.33
.56
.85
.93
.80
.64
.65
.11
slam
37/46
SHD
.98
37
26
20
20
92
.64
86
3
.66
21
.62
18
46
.22
barley
SHI
5
48
55
50
0
3
8
42
34
50
87
60
42
48/84
Fl
98
.6
.38
.44
1.0
.96
.91
.59
.72
.43
.00
.48
.67
hailfinder
56/66
SHD
80
.7
41
17
.70
:
.33
111
118
hepar2
SHD
0
54
81
59
0
35
27
37
14
-66
40
35
75
123
79
61
70/123
Fl
1.0
39
.34
.54
1.0
.72
.81
.70
.89
.75
.70
.81
.39
.00
.34
.88
win95pts
SHD
65
51
0
8
21
16
50
112
103
.9
.43
.95
.97
.91
.57
.47
pathlinder
SHD
25
1.57
145
1.51
0
1.50
147
158
168
148
196
241
109/195
F1
.77
211
.29
.21
1.0
.29
.30
.29
.28
.31
.00
.07
SHD
154
777
H6
109
151
257
186/233
.97
.42
.47
.71
.58
.72
.26
andes
SHD
0
226
209
2466
0
4
83
4
5.
47
15
18
149
175
223/358
F1
1.0
.35
.41
.29
1.0
.99
.75
.99
.98
.92
.66
.92
.60
diabetes
SHD
25
220
395
237
48
0
204
146
592
368
534
413/602
F1
96
62
.38
.62
.96
1.0
.68
.77
.03
.43
433
SUD
350
263
400
400
268
316
6
4417592
1.0
.44
.35
.35
.56
1.0
.18
link
SHD
0
731
6340
638
749
737
204
324
1047
400
947
724/1125
Fl
1.0
38
.45
.45
.39
81
80
.14
.64
munin
SHD
967
790
816
0
156
458
661
1397
735
1599
1041/1397
F1
.95
.66
.48
.44
1.0
.89
.69
.2
.00
.29
munnnn?
SHD
118
554
611
646
1052
898
536
632
1240
753
1321
1001/124
.92
60
.66
.55
.19
.30
58
munin3
SHI
113
616
629
688
1048
860
544
566
1306
819
1539
1041/1306
F1
.92
38
.57
.34
.25
.37
60
.6
.00
.46
.26
munin4
SHD
126
696
658
776
1058
876
649
618
1388
812
1627
1038/1388
F1
.93
54
.56
.29
.39
.55
.64
.00
.49
.28
(ank(SHD)
stdd
mean
1.5
3.9
5.1
3.3
10.8
2.9
9.5
4.4
5.8
9.6
8.7
7.2
13.3
10.5
3.5
10.7
4.3
UTFI
mean
stdd
.13
.90
17
.40
.66
34
50
.53
33
.87
16
.32
.59
28
-54
37
22
30
.07
.09
.29
36
33
-70
Table 2: Reliability: average Fi-score of MLAC vs. 8 discriminative predicates extracted from ML4C features on benchmark datasets.
strong prodicates
weak predicates
id
MLAC
2
3
F1
.9: 20
771.31
.52+.27
384.22
66 27
.724:25
.61 29
.3++.30 55+.27
329 4.4 + 2.4. Among the competitors, NCC ranks #1 on 8 datasets (note that ML4C ranks #1 on 11 datasets), but its performance fluctuates. Overall only ranks 5.1 + 4.2. Last but not least, ML4C shows high accuracy (F1>0.9) on very large-scale datasets (e.g., medicine datasets "munin*' B while max(others) 0.6.
330
331
332
333
Towards a Perfect Classifier The last row of Table Tshows the performance of MLAC-Leamer
334
component at UT level by UT-FI (i.e., Fl-score of classifying UTs): such UT level accuracy is crucial for causal learning on discrete data, since the set of v-structures is invariant across all Markov equivalent DAGs and it can fully recover the CPDAG. The average F1-score of AC-Leerrrerr
396
0.90 + 0.13, which shows promising results towards perfect classifier.
8

---

Table 3: Robustness: ML4C is trained on synthetic datasets with sample size 10k, but tested on benchmark datasets with different sample sizes E {1k, 5k, 10k, 15k, 20k}.
size
1k
5k
10k
15k
20%
size
1k
5k
10k
15k
20k
size
1k
5k
10k
15k
20k
SHD F1
insarance
11
5
1
0
water
12
11
5
8
mildew 35/46
8
27/52
.81
.97
.89
.97
1.0
32/66
.86
.87
.94
.89
.93
.93
.98
SHD
alarm
4
0
1
5
barley 48/84
13
9
8
6
hailfinder 56/66
15
15
15
13
37/46
1.0
.98
.93
.74
.72
.72
.76
SHI F1
hepar2
2
0
1
2
win95pts 76/1 12
pathlinder 109/195
70/123
.96
.99
1.0
.99
.99
1.0
.99
.99
.99
.92
.77
.92
.99
SHD
munin1
10
15
andes 223/338
diabetes 413/602
F1
186/273
.89
-98
.97
.97
.95
.99
.99
1.0
.99
1.0
.97
.95
.99
.96
.96
SHD
0
0
0
link
88
13
munin
107
76
87
441/592
1.0
1.0
1.0
1.0
1.0
724/1125
.93
-99
1.0
1.0
1.0
1041/1397
.93
.95
.96
.94
.94
SHD
munin2
117
95
120
110
97
muninn
151
119
113
99
62
munite
165
130
123
146
133
1003/1244
.92
.93
.93
1041/1306
1038/1388
Table 4: Transferability: ML4C trains/tests both on synthetic datasets with different configurations.
train
||
lest
SHD
F1
lest
SHD
F1
lest
SHD
F1
test
SHD
F1
10
2.24
94.1.12
3.8
1_00 03
100
6.6.14.7
.9.1.02
5..6.8.4
.7..1.00
50
10
0.4
971.05
50
0.8:1.0
991
100
4.4
98:
Ik
2372:55.7
.9:+:00
10
0.0:0.0
1.0+.000
1.2+16
99
100
4.0-24.6
98+.02
21.6=4.8
99:t.0
1k
0.4:0088 10
97:1.05
50
0.8:1:10
99:
100
1.4:12.3
991.01
1k
14.8:1822
99:5.00
0.8:1.6
99+
3.4+2.9
97=
3
3.0+22.5
98+-01
11.4=399
.95+.02
spuisit
1.8
98:5.02
2.24:17
.88..01
2.2:22.0
99:5.01
8.24:2.5
.9:4.01
1.0
.98 1.02
2.2.1.33
.98 1.01
4.4.1.3.
99.1.002
4.0.13.2
.981101
2.4
97.1.03
2.2.1
98.1 01
3.2:12.7
.8-1 02
4.8:13.7
.8.1
gyye samplesize
1k
Ik 2.8+2.3
.7
5k 2.0=22.
98
10k 1.6+223
98++.02
20k
1.0
.99t.01
5k
1k 5.2-22.9
.952.03
1,0+2.
999..02
10k
2.2:1:355
.984.04
20k
0.6:2:0.8
.9+4.01
10k
1k 4.2
.9511.05
1.811.7
.981.0
10k
2.0:33.1
.981.03
20k
0.6:1.088
.991.01
20k
Ik 3.8.3.33
.9....03
5k
2.4.1.6
.9.1.02
10k 1.2.11.
.9.1.02
20k
1.3
.991..02
ER
ER 1.0:22.0
99.1.02
SF
2.2:1.66
.811.01
ER
1.69
.8.1.02
2.2.1244
.98.1.02
Reliability We manually identify 4 strong discriminative predicates and 4 weak discriminative predicates and treat each one as a replacement of ML4C-Learner. Table 2 shows the performance of these predicates. Although most predicates show value discriminating UTs (c.g.. 5/8 predicates are with >0.6 Fl-score), ML4C-Learner has higher performance (average Fl-score = 0.92) than cach learns more reliable classification mechanism, by taking advantage of machine learning techniques.
339
341
342
individual predicate (best average F1-score 0.77). Thus, it is evident that MLLCC-
343
344
Robustness
To evaluate robustness, ML.CC is trained on synthetic datasets with sample size 10k, but it is tested on benchmark datasets with different sample sizes: 1k, 5k, 10k, 15k and 20k respectively. Table that MI.C exhibits satisfactory robustness (decrease of F1-score is less than 0.1) against sample size on most datasets (17/18, except for "hailfinder'..
345
346
347
348
Transferability To evaluate whether MIAC generalizes well various types of testing data, we vary scale (#nodes), graph sparsity, generating mechanism and sample size. ML4C is trained on fixed configuration but tested with different domains (i.e., data generated under different configuration). Result is depicted in Table 4, ML4C transfers well on different domains, e.g., even if it is trained on 10 nodes but tested on 1,000 nodes (last column of the first row in Table 4). the
349
350
351
352
353
Fl score only drops 0.02.
354
6
Conclusion and Future Work
355
We have proposed a supervised causal learning algorithm ML4C, with theoretical guarantee on learnability and remarkable empirical performance. More importantly, MLAC shows promising results on validating the effectiveness of supervision. To make SCL practical in real-world scenarios, one important direction for future work is to identify reliable and accurate skeleton from data, considering ML4C requires skeleton additional input.
356
358

---

References
380
[1] Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47. 2002.
362
Constantin F Aliferis, Alexander Statnikov, Joannis Tsamardinos, Subramani Mani, and Xenofon D Koutsoukos. Local causal and markov blanket induction for causal discovery and feature selection for classification part i: algorithms and empirical evaluation. Journal of Machine Learning Research, 11(1), 2010.
364
365
386
367
[3] Steen Andreassen, Marianne Woldbye, Bjørm Falck, and Stig K Andersen. Munin: A causal probabilistic network for interpretation of eleetromyographic findings. In Proceedings of the 10th international joint conference Artificial intelligence-Vollue 1, pages 366-372, 1987.
368
[4] Gianluca Bontempi and Maxime Flauder. From dependency to causality: machine learning approach. J. Mach. Learn. Res., 16(1) (6437744722 2015.
[5] Tianqi Chen and Carlos Guestrin. Xgboost: scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785 7944,99,777 2016.
373
[6] David Maxwell Chickering. Optimal structure identification with greedy search. Journal machine learning research. 3(Nov):507-534, 2002.
375
Diego Colombo and Marloes H Maathuis. Order-independent constraint-basel causal structure learning. J. Mach. Learn. Res., 15(1):374133722 2014.
377
378
James Cussens. Bayesian network learning with cutting planes. arXiv preprint arXiv::202.3777 2012.
Colombo Diego and H. Maathuis Marloes. Order-independent constraint-baset causal structure learning. Journal of Machine Learning Research, (5(116):39213396 2014.
380
[10] Rui Ding, Yanzhi Liu, Jingjing Tian, Zhouyu Fu, Shi Han, and Dongmei Zhang. Reliable and efficient anytime skeleton learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, 2020.
382
383
384
[11] P. Erdós and Rényi A. On random graphs. Publicationes, Mathematicae, 6:290-297, 1959.
385
[12] José AR Fonollosa. Conditional distribution variability measures for causality detection. In Cause Effect Pairs in Machine Learning, pages 339-347. Springer, 2019.
386
387
[13] Clark Glymour, Kun Zhang, and Peter Spirtes. Review causal discovery methods based on graphical models. Frontiers in gemetics, 10:524, 2019.
388
389
[14] Patrik Hoyer, Dominik Janzing. Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. Advances in newral information processing systems, 21:689 6966 2008.
390
382
[15] Dominik Janzing, Joris Mooij, Kun Zhang, Jan Lemeire, Jakob Zscheischler, Povilas Daniušis. Bastian Steudel, and Bernhard Schölkopf. infornation-geometii approach to inferring causal directions. Artificial Intelligence, 182:1-31, 2012.
394
[16] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
396
397
[17] Steffen L Lauritzen. Graphical models, volume 17, Clarendon Press, 1996.
[18] Hebi Li, Qi Xiao, and Jin Tian. Supervised whole dag causal discovery. arXiv preprint 47X1v:2006.04697. 2020.
399
[19] Honghao Li, Vincent Cabeli, Nadir Sella, and Hervé Isambert. Constraint-based causal structure learning with consistent separating sets. In 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), 2019.
401
402
405
[20] David Lopez-Paz, Krikamol Muandet, and Benjamin Recht. The randomized causation coefficient. J. Mach. Learn. Res., 16:2901-2907 2015.
404
405
[21] David Lopez-Paze Paz, Robert Nishihara, Soumith Chintala, Bernhard Scholkopt, and Léon Bottou. Discovering causal signals in images. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6987,,017, 2017.
408
10

---

408
[22]
Dimitris Margaritis. Learning bayesian network model structure from data. Technical report, Carnegie- Mellon Univ Pittsburgh Pa School of Computer Science, 2003.
410
[23] Christopher Meek. Causal inference and causal explanation with background knowledge. arXiv preprint 1rXiv:1302.4972. 2013.
412
[24] Christopher Meek. Strong completeness and faithfulness in bayesian networks. arXiv preprint arXiv:1302.4973. 2013.
414
[25] Joseph Ramsey. Jiji Zhang, and Peter Spirtes. Adjacency-faithfulees and conservative causal inference. arXiv preprint (rXiv:/206.666 1206.60066.. 6843, 2012.
416
[26] Joseph Ramsey, Jiji Zhang, and Peter L Spirtes, fajicency and conservative causal inference. arXiv preprint arXiv:1206.6843, 2012.
418
[27] Mauro Scanagatta, Cassio Polpo de Campos, Giorgio Corani, and Marco Zaffalon. Learning bayesian networks with thousands of variables. In NIPS, pages 1864-1872, 2015.
420
[28]
Marco Scutari. Bayesian network repository. URI. htp:://www. bulearn. com, 2012.
421
[29] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
422
425
[30]
Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. hilbert space embedding for distributions. In International Conference on Algorithuic Learning Theory, pages 13-31. Springer, 2007.
424
425
[31] Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social science computer review, 9(1 ):62-7, 1991.
426
427
[32] Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000.
428
429
[33] M.K. Vijaymeena and K. Kavitha. A survey on similarity measures text mining. Machine Learning and Applications: An International Journal, 3(2):19-28.
430
431
[34] Kui Yu, Jiuyong Li, and Lin Liu. review on algorithms for constraint-baset causal discovery. arXiv preprint 161 1.03977, 2016.
432
439
[35] Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gun: Dag structure learning with graph neural networks. In International Conference on Machine Learning, pages 7154-7163. PMLR, 2019.
434
435
[36] Xun Zheng. Bryon Aragam, Pradeep Ravikumar, and Eric Xing. Dags with no tears: Continuous optimization for structure learning. arXiv preprint arXiv:1803.0142) 2018.
436
Checklist
438
1. For all authors...
439
(a) Do main claims made the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
410
441
(b) Did you describe the limitations of your work? [Yes] See $6 additional input, thus we put identifying reliable and accurate skeleton from data as future work.
ML4C requires skeleton as
442
443
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
444
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
445
2. If you are including thcorctical results...
446
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Details of proof' are in the supplementary material due page limit.
448
449
3. If you ran experiments...
450
(a) Did you include code, data, and instructions needed to reproduce main experimental results (either in the supplemental material or as a URL)? [Yes] We have included the main functionalities of MLAC, synthetic data generator, and MLAC's training data (include instructions) for reproducibility. Details are in the supplementary material.
451
452
454
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Ye]] Key information is in content. Details in the supplementary material.
11

---

458
(c) Did you report enror bars (e.g.. with respect to the random seed after running experiments multiple times)? [Yes] We carefully design experiments. by running experiments multiple times, including error bars in report to ensure reproducibility. For instance, Table contains error bar information.
458
499
460
(d) Did you include total amount of compute and the type resources used (e.g.. type GPUs, internal cluster, or cloud provider)? [Yes]
481
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
463
(a) If your work uses existing assets, did you cite the creators? [Yes] We compare our algorithm with 15 SOTA competitors and we have cite these work properly. We also use open source benchmark for evaluation and we also properly cite the creators.
484
466
(b) Did you mention the license of the assets? [N/A]
467
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] We share new assets, include main functionalities of our algorithm, and our training data. A private URL provided. See details the supplementary material.
469
(d) Did you discuss whether and how consent obtained from people whose data you're ing/curating? [Yes] Due to page limit, the detailed discussion available in the supplementary material.
471
472
473
(e) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A] We double-checked that the data we are using/curating contains no personally identifiable information or offensive content.
474
475
476
If you used crowdsourcing or conducted research with human subjects...
477
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
479
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
482
12


Reviews:
[{"review_id": "kVgUBv_5e3J", "reviewer": "Reviewer_fW1y", "summary": "This paper aims to tackle the supervised causal learning (SCL) problem, i.e., learning causal relationships from observational data in a supervised manner. The paper first shows that SCL is beneficial only when the learning target is identifiable. So this paper proposes a two-phase paradigm which first classifies if the target is identifiable and then orients the unshielded triple (UT). To achieve both objectives, the core of this paper is to train a classier to determine if a given UT constitutes a collider. The authors utilize the intuition that stronger entanglement implies smaller chance of identifiability and propose to make use of the overlap between the vicinties. Theoretical and empirical analysis both demonstrate the effectiveness of the proposed framework.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**: This paper proposes an interesting approach for solving the SCL problem, which breaks it down to classifying the identifiability of UTs.\n\n**Quality**: This paper is overall technically sound with strong empirical evaluation results demonstrated. Notations are clearly defined and theoretical analyses are also carried out.\n\n**Clarity**: The paper is generally well-written and organized. However, some details are not clear to me; please see the questions below.\n\n**Significance**: The target problem of this paper, SCL, is an important and fundamental task to be addressed, and it appears to me that the approach presented in this paper can advance the state of the art in solving SCL problem.\n\n**My questions**:  \n1. How are the embeddings of each UT computed? what is the dimension?  \n2. The paper utilizes the intuition that stronger entanglement implies smaller chance of identifiability, can this be proved?  \n3. If this intuition holds strictly, can we simply fit a linear regression using the overlap coefficient as mentioned in line 226 to determine the dependency? why a classifier is needed?\n4. From Table 1, it seems that NCC performs much better for smaller datasets and ML4C is significantly better for larger datasets. As both are supervised methods, what makes ML4C worse than NCC with small datasets?\n\n---\n**Post rebuttal**\nThanks for the responses from the authors. My concerns are mostly resolved. Please incorporate the responses in the new version of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please kindly see the question in the above section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "gSPHvQSrjR", "reviewer": "Reviewer_oFcS", "summary": "The paper proposes a novel way of supervised causal learning. The core of the algorithm is a binary classifier that determines if the input UT are in a v structure or not. Given the predicted structures Meek rules are applied to reconstruct the DAG. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Structure and Language: At times the paper lacks clarity and has an unorthodox organisation, for example methodological details are found in the introduction. I would suggest a bit of restructuring and an independent person to read it such that clarity is improved.\n\nProposed Method: The paper is thorough and the attention to detail is applauded. As above some explanations could be improved in some cases. Line 127 refers to established theory of identifiability, please cite this properly. \nIn line 239 the authors mention that for a canonical dataset with sufficient samples their method yet there is no mention on how to determine such a quantity, nor if it is possible to do so. It is further claimed that the featurization is not handmade. Technically speaking, even though the features are derived from elaborate heuristics I do not believe it is correct to argue complete independence of features from expert knowledge, as inputs are not derived from raw data. As such a semi-handmade featurization step would be a more appropriate description \n\nEmpirical Analysis: The paper offers a quite in depth experimentation/comparison to other methods. Three questions are raised from this analysis.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A few questions are raised as for limitations of this work: \n1) How to determine the sufficient sample size to make a good enough classifier , and if it is possible to do so.\n2) What would happen with using different choices on the featurization methods\n3) An F1 score of 1 is somewhat suspicious, could the authors please confirm the accuracy of their evaluation. Are the reported numbers the result of multiple trials or the max performance is noted ?\n4) Could the authors please put their work into context from a practical point of view? \n5) In the case of inference where ground truth is absent, are there ways to evaluate the performance of the algorithm such that checks and balances are introduced to minimize negative societal impact ? ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0mr1KTYTZXd", "reviewer": "Reviewer_JXwC", "summary": "Given a discrete dataset and a graph skeleton consistent with the underlying DAG generating the dataset, this paper proposed a new supervised causal learning (SCL) approach, called ML4C, to classify each unshielded triple in the skeleton as V structure (positive class) or not (negative class).\n\nIn the first step, a feature vector is constructed for each unshielded triple X-T-Y, where 1) some features characterize  the conditional dependency between X and Y given T since the value could vary depending on if the triple is truly a V structure; 2) some features characterizes the entanglement between the parent-children set of each node in the triple as well as the sepsets. The extracted features vector is then embedded as a fixed-dimensional vector through kernel mean embedding. In the second step, a classification model is trained to predict the V structure label given the input feature vector.\n\nExperimental results on benchmark datasets show the proposed ML4C outperforms its competing alternatives, including both supervised and unsupervised causal learning approaches, in identifying the ground truth DAG generating the dataset.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The feature construction for unshielded triple seems novel. The background work is well introduced. Empirical results show strong performance of the proposed approach.\n\nWhy does the proposed approach only apply to discrete data? Is there any problem in applying it to continuous data?\n\nSince the ground-truth skeleton is given as input, it would be useful to evaluate how the model performance changes as the input skleleton is misspecified. Furthermore, when comparing against those baseline approaches without skeleton input, it would be more appropriate to start from the same skeleton that is identified by each approach. In this way, the comparison becomes fairer to the baselines.\n\nWhen evaluating the robustness of the proposed approach, instead of running test on datasets with varying sample size, it would be more interesting to train the model with varying number of DAGs used to train the model. Specifically, what's the minimal number of input DAGs that are needed to reach the best performance?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The need to use the ground-truth skeleton is the major limitation. I didn't see any negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although reviewers found the idea intriguing, our discussions raised quite some concerns regarding sloppiness of presentation, particularly in the theory part. Just a few examples:

- Without further specification, Proposition 1 is a pretty vague statement.

- There were also the question what the non-trivial content of Proposition 2 is supposed to be

- The statement 'skeleton is a statistical concept'. If we are talking about the skeleton of the causal DAG, the skeleton is also causal. The relation between conditional independences and skeleton is  subject to faithfulness, i.e., a postulate relating statistics to causality.

[Update] Dear authors,

I understand your disappointment on the decision, given that the scores qualify this paper as close to acceptance, I also understand the feeling of unfair treatment. Before I go into a more detailed discussion, I would like to emphasize that the yes/no decision accept/reject is not a decision on good versus bad, often there is a large grey zone of close to acceptance, in which this paper definitely is. 

Since the reviewer with score 7 had low confidence, we were left with 2 times the score ‘marginally above the threshold’, which expresses some hesitation after all. After reading the paper myself, I largely agreed with these assessments, but with a *slightly* more critical opinion, and all the remarks below only justify rejection in the context of very high standards of NeurIPS (although I do know that also bad papers can make it sometimes to NeurIPS). 

- Proposition 1: it seems highly misleading to me (even without asking for mathematical rigor) for the following reason. Identifiability is a purely theoretical construction that depends on the model assumptions. While traditional causal discovery uses nothing beyond faithfulness, further model assumptions like additive noise render additional directions identifiable). I know that the authors are aware of this, but in real life we have never hard restrictions on the model class. Instead, some patterns are more likely to occur in one direction than the other. Supervised causal discovery has the potential to cope with these missing hard constraints and get evidence for one direction versus the other without a priori given hard constraints on the model classes. In other words, identifying directions without hard criteria is exactly what I would expect from the method.  
- Regarding proposition 2, I can see its justification from the context, but phrasing it as a proposition pretends mathematical rigor that I cannot see. What are the assumptions here? E.g. it assumes correctness of the skeleton in the sense of causal semantics (i.e. when faithfulness is met), right?
- I can see now the author’s viewpoint on the skeleton being ‘statistical’ in the context of how they introduced it. I’m sorry about this miss! 

As I said, I admit that all these points can justify rejection only in light of very high standards. I really encourage the authors to resubmit! I have to say that I spend quite some time with this decision because of the large grey zone of borderline papers. I should have been more explicit about this in my meta-review – also to make clear that this rejection was not based on a quick ad-hoc decision. 

There is no question that other ACs could have come to a different conclusion.  I should also say that I have no reservations per se against any methods of this paper.  

Further, I admit that I could have raised the above points during the discussion and the main justification for this miss is the work load of a bunch of other papers that deserved my attention too. I hope these remarks make it easier to just accept the decision as a result of a process with uncertainty, and without absolute truth.   

Best wishes,

Area Chair
Decision: Reject