ML4C: Seeing Causality Through Latent Vicinity
Year: 2021

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

Supervised Causal Learning (SCL) aims to learn causal relations from observational1 data by accessing previously seen datasets associated with ground truth causal2 relations. This paper presents a first attempt at addressing a fundamental question:3 What are the benefits from supervision and how does it benefit? Starting from seeing4 that SCL is not better than random guessing if the learning target is non-identifiable5 a priori, we propose a two-phase paradigm for SCL by explicitly considering6 structure identifiability. Following this paradigm, we tackle the problem of SCL on7 discrete data and propose ML4C. The core of ML4C is a binary classifier with a8 novel learning target: it classifies whether an Unshielded Triple (UT) is a v-structure9 or not. Starting from an input dataset with the corresponding skeleton provided,10 ML4C orients each UT once it is classified as a v-structure. These v-structures are11 together used to construct the final output. To address the fundamental question12 of SCL, we propose a principled method for ML4C featurization: we exploit the13 vicinity of a given UT (i.e., the neighbors of UT in skeleton), and derive features by14 considering the conditional dependencies and structural entanglement within the15 vicinity. We further prove that ML4C is asymptotically perfect. Last but foremost,16 thorough experiments conducted on benchmark datasets demonstrate that ML4C17 remarkably outperforms other state-of-the-art algorithms in terms of accuracy,18 robustness and transferability. In summary, ML4C shows promising results on19 validating the effectiveness of supervision for causal learning.20
1 Introduction21
The problem of causal learning is to learn causal relations from observational data [13]. The learned22 causal relations are typically represented in the form of a Directed Acyclic Graph (DAG), where each23 edge in the DAG indicates direct cause-effect relation between the parent node and child node.24
The methods of causal learning mostly fall into four categories: constraint-based, score-based,25 continuous optimization method and functional causal models. Each of these methods takes a given26 dataset as input and outputs a DAG but with different criteria. For instance, the DAG should be27 consistent with conditional independencies in the data (constraint-based); or it is optimal w.r.t. a28 pre-defined score function under either combinatorial constraint (score-based) or continuous equality29 constraint (continuous optimization). In a nutshell, these methods can be viewed as unsupervised30 since they do not access additional datasets associated with ground truth causal relations.31
A new line of research called Supervised Causal Learning (SCL), on the other hand, aims to learn32 causal relations in the supervised fashion: the algorithm has access to datasets associated with33 ground truth causal relations, in the hope that such supervision is beneficial to learning causal34 relations on newly unseen datasets. Despite several existing works on this direction (see Related35 Work), a fundamental question remains unanswered: How is supervised causal learning possible?36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
Specifically, compared with unsupervised causal learning methods, can we gain additional benefits37 from supervision? If the answer is positive, then what are the benefits and how does it benefit?38
We tackle the problem by first seeing crucial connection between SCL and causal structure identi-39 fiability. Considering the problem of causal learning on discrete data, theorem in [24] states that,40 under standard assumptions (i.e., Markov assumption, faithfulness and causal sufficiency), we can41 only identify a graph up to its Markov equivalence class. Markov equivalence class is the set of42 DAGs having same skeleton and same v-structures, which can be represented by CPDAG (Com-43 pleted Partially Directed Acyclic Graph). Thus, the (un)directed edges in the CPDAG indicate44 (non-)identifiable causal relations. Each non-identifiable edge in CPDAG can be oriented by either45 direction to equivalently fit the observational data. Given an SCL algorithm with learning target as46 the orientation of an edge, we see that it is not better than random guessing (or could be worse due to47 sample bias in training data) to predict any non-identifiable edge since we can assign either X → Y48 or X ← Y with same input dataset. This statement is applicable to general learning target since an49 SCL algorithm can take different target such as orientation of an edge, the whole DAG, or others.50
Proposition 1. If the learning target is non-identifiable (i.e., every edge in the target is non-51 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 1(a):53 phase one corresponds to a binary classification task, where an SCL algorithm needs to classify54 whether a specific learning target is identifiable or not; only if it is classified as identifiable, then we55 go to phase two to classify the specific orientation of the learning target. Following this paradigm,56 we tackle the problem of SCL on discrete data and propose an algorithm ML4C. The core of ML4C57 is a binary classifier with a novel learning target: it classifies whether an Unshielded Triple (UT: a58 triple of variables 〈X,T, Y 〉 where X and Y are adjacent to T but are not adjacent to each other) is a59 v-structure or not. Starting from an input dataset with the corresponding skeleton provided, ML4C60 orients each UT once it is classified as a v-structure. These v-structures are further used to construct61 a CPDAG as output. Such a single classifier facilitates both learning tasks in the two phases, since an62 identifiable UT implies that it is a v-structure [32] (i.e., up to the partial DAG before applying Meek63 rules [23] which is a standard post processing).64
To address the fundamental question of SCL, we propose a principled method for ML4C featurization.65 Specifically, we exploit the vicinity of a given UT (i.e., the neighbors of UT in skeleton), and derive66 features by considering the conditional dependencies and structural entanglement within the vicinity.67 We further define discriminative predicate (i.e., a binary predicate function with domain as ML4C’s68 feature set) and prove that there exist weak discriminative predicates and strong discriminative69 predicates (i.e., values of the predicates are one-to-one correspondence with ground truth labels).70 We further prove that ML4C is asymptotically perfect. Last but foremost, thorough experiments on71 benchmark datasets demonstrate that ML4C remarkably outperforms other state-of-the-art algorithms72 w.r.t. accuracy, robustness and transferability. Our main contributions are summarized as follows:73
1. We advocate the two-phase paradigm for SCL with consideration of causal structure identifiability.74
2. We propose an SCL algorithm ML4C, with the following novelties: i) Learning Target: The core75 of ML4C is a binary classifier with the orientation of a UT as its learning target to address the two-76 phase tasks simultaneously. ii) Featurization: A principled method to exploit vicinity information77 in terms of dependencies and entanglement of a given UT. iii) Learnability: We prove that ML4C78
is asymptotically perfect. iv) Empirical Performance: Experiments conducted on benchmark79 datasets demonstrate that ML4C remarkably outperforms other state-of-the-art algorithms.80
2 Related Work81
We divide literature on causal learning into supervised and unsupervised approaches, depending on82 whether additional datasets (associated with ground truth causal relations) are accessed (supervised)83 or not (unsupervised). In the literature of unsupervised causal learning, constraint-based methods aim84 to identify a DAG which is consistent with conditional independencies. The learning procedure of85 constraint-based methods first identifies the corresponding skeleton and then conducts orientation86 based on v-structure identification [34]. The typical algorithm is PC [31], and there are also PC-87 derived algorithms such as Conservative-PC [26], PC-stable [7] and Consistent-PC [19] which88 improve the robustness on v-structure identification. Score-based methods aim to find the DAG which89 is optimal w.r.t. a pre-defined score function under combinatorial constraint by a specific search90 procedure, such as forward-backward search GES [6], hill-climbing [16], integer programming [8], or91 by approximate algorithms based on order search [27]. Continuous optimization methods transform92 the discrete search procedure into continuous equality constraint: NOTEARS [36] formulates the93 acyclic constraint as a continuous equality constraint, it is further extended by DAG-GNN [35] to94 support learning non-linear causal relations.95
SCL emerges from the task of orienting edge in the continuous, non-linear bivariate case under96 Functional Causal Model (FCM) formalism. Given a collection of cause-effect samples (dataset97 ∼ binary label indicating whether X → Y or X ← Y ), supervised approaches such as RCC [20],98 NCC [21], D2C [4] and Jarfo [12] achieve better performance on predicting pairwise relations (i.e.,99 orientation of an edge) than unsupervised approaches such as ANM [14] or IGCI [15]. Differently,100 [18] sets the learning target as the whole DAG structure instead of pairwise relation and it is applied on101 data which is generated by linear Structural Equation Model (SEM). We summarize the differences in102 problem space between ML4C and the other SCL approaches as follows: i) We advocate a two-phase103 learning paradigm and emphasize the relationship between identifiability and learnability. Specifically,104 presuming additive noise model [14] or linear SEM with non-Gaussian noise [29] provides license105 to identifiability thus the aforementioned approaches can be viewed as specific tasks in phase two.106 ii) We tackle SCL’s learnability not only via empirical evaluation but also by theoretical analysis to107 shed light on the fundamental question of learnability. iii) ML4C deals with discrete data while other108 approaches mainly focus on continuous data.109
3 Background110
3.1 Basic Notations111
A discrete dataset Di consists of ni records and di categorical columns, which represents ni instances112 drawn i.i.d. from di discrete variables X1, X2, · · · , Xdi by a joint probability distribution Pi, which113 is entailed by an underlying data generating process, denoted as DAG Gi.114
Markov factorization property: Given a joint probability distribution P and a DAG G, P is said to115 satisfy Markov factorization property w.r.t. G if P := P (X1, X2, · · · , Xd) = ∏d i=1 P ( Xi|paGi ) ,116 where paGi is the parent set of Xi in G.117
Markov assumption: P is said to satisfy Markov assumption (or Markovian) w.r.t. a DAG G if118 X⊥GY |Z ⇒ X⊥Y |Z. Here ⊥G denotes d-separation, and ⊥ denotes statistical independence.119 Markov assumption indicates that any d-separation in graph G implies conditional independence in120 distribution P . Markov assumption is equivalent to Markov factorization property [17].121
Faithfulness: Distribution P is faithful w.r.t. a DAG G if X⊥Y |Z ⇒ X⊥GY |Z.122 Canonical dataset: We say a discrete dataset D is canonical if its underlying probability distribution123 P is Markovian and faithful w.r.t. some DAG G.124
3.2 Causal Structure Identifiability125
Identifiability discusses which parts of the causal structure can in principle be inferred from the126 distribution. Below we present the established theory of identifiability on discrete data.127
Causal sufficiency: There are no latent common causes of any of the variables in the graph.128 Definition 1 (Markov equivalence). Two graphs are Markov equivalent if and only if they have129 same skeleton and same v-structures. A Markov equivalence class can be represented by a CPDAG130 having both directed and undirected edges. A CPDAG can be derived from a DAG G, denoted as131 CPDAG(G). The theorem of Markov completeness in [24] states that, under causal sufficiency, we132 can only identify a causal graph up to its Markov equivalence class on canonical data. Therefore, the133 (non-)identifiable causal relations are the (un)directed edges in the CPDAG. Formally,134 Definition 2 (Identifiability). Assuming P is Markovian and faithful w.r.t. a DAG G and causal135 sufficiency, then each (un)directed edge in CPDAG(G) indicates (non-)identifiable causal relation.136
3.3 ML4C Related Notations137
Definition 3 (Skeleton). A skeletonE defined over distribution P (X1, X2, · · · , Xd) is an undirected138 graph such that there is an edge between Xi and Xj if and only if Xi and Xj are always dependent,139 i.e., @Z ⊆ {X1, X2, · · · , Xd} s.t. Xi⊥Xj |Z. Skeleton is a statistical concept, which can be140 obtained prior to facilitating various downstream tasks. Recently, there have been some novel141 skeleton learning algorithms such as [10]. In particular, skeleton can be used for causal learning:142 theorem in [32] states that if distribution P is Markovian and faithful w.r.t. a DAG G, then skeleton143 E is the same as the undirected graph of G.144 Definition 4 (UT). A triple of variables 〈X,T, Y 〉 in a skeleton is an unshielded triple, or short145 for UT, if X and Y are adjacent to T but are not adjacent to each other. 〈X,T, Y 〉 can be further146 oriented to become a v-structure X → T ← Y , in which T is called the collider.147 Definition 5 (PC). Denote the set of parents and children of X in a skeleton as PCX , in other words,148 PCX are the neighbors of X in the skeleton. For convenience, if we discuss PCX in the context of a149 UT 〈X,T, Y 〉, we intentionally mean the set of parents and children of X but exclude T .150 Definition 6 (Vicinity). We define the vicinity of a UT 〈X,T, Y 〉 as V〈X,T,Y 〉 := {X,T, Y }∪PCX∪151 PCY ∪PCT . Vicinity is a generalized version of PC, i.e., the neighbors of {X,T, Y } in the skeleton.152
ML4C’s training set: The training set is a collection of discrete datasets D1, · · · , Dn, where each153 dataset Di is associated with a ground truth DAG Gi, such that Di is sampled from Gi. Gi derives154 labels (depends on the chosen learning target), thus {Di, Gi}i∈{1,··· ,n} form ML4C’s training set.155 We can sample graphs from DAG space and generate corresponding datasets, thus obtaining training156 set in our problem is straightforward.157
4 Approach158
4.1 Overview159
The core of ML4C is a binary classifier called ML4C-Learner, which takes the orientation of a UT160 as its learning target, i.e., it classifies whether an input UT 〈X,T, Y 〉 is a v-structure (orientation:161 X → T ← Y ) or not (orientation remains unknown). Figure 1(b) depicts the overall workflow of162 ML4C, which is composed of ML4C-Learner with other important inductive biases. Starting from an163 input dataset Di with corresponding skeleton Ei, we first obtain all the UTs from Ei. Featurization is164 then conducted to represent each UT as an embedded vector, which is further fed into ML4C-Learner.165 In the inference stage, we obtain all the v-structures which are classified by ML4C-Learner and166 reconstruct a partial DAG and then, a CPDAG is output by applying Meek rules on the partial DAG.167 In the training stage, the label of each UT is obtained by querying from ground truth DAG Gi. We168 collect labeled data from multiple datasets in ML4C’s training set.169 Proposition 2. If ML4C-Learner is a perfect classifier, then ML4C outputs correct CPDAG of a170 canonical dataset (i.e., ML4C is perfect).171
By Markov completeness, the set of v-structures is invariant across all Markov equivalent DAGs for172 a canonical dataset, and it can fully recover the CPDAG, provided that the skeleton is given. Thus,173
besides its dedicated role in phase 2, ML4C-Learner also facilitates learning task in phase 1 since an174 identifiable UT implies that it is a v-structure (up to the partial DAG before applying Meek rules).175
4.2 Featurization176
We propose a principled method for ML4C-Learner’s featurization, which avoids the need of hand-177 crafted features. More importantly, we further prove that ML4C-Learner is asymptotically perfect.178
Design Principles: Our key aspect of featurization is to broaden focus from a specific UT 〈X,T, Y 〉179 to its vicinity and seeking conditional dependencies and structural entanglement within the vicinity, to180 reveal reliable and robust asymmetry to distinguish v-structure and non-v-structure UTs. Specifically,181 conditional dependencies are the key materials for traditional causal learning methods (e.g., condi-182 tional independences for constraint-based methods), and structural entanglement (e.g., PCX = PCT )183 are relevant to identifiability: higher entanglement makes the UT less likely to be identifiable.184
• Dependencies within Vicinity185 Conditional dependency: Denoted as X ∼ Y |Z , which is a non-negative scalar that measures the186 dependence between two random variables X and Y given variable set Z. Operationally, X ∼ Y |Z187 is composed of two parts, bivariable X ∼ Y , and conditional Z. We further extend the definition to188 allow a set of variables in bivariable, and an ensemble (i.e., a set of set) as conditional:189
Extended conditional dependency: Denoted as A ∼ B|Z:= {X ∼ Y |Z :X ∈ A, Y ∈ B,Z ∈190 Z}, where A and B are set of variables, and Z is an ensemble. Thus, extended conditional191 dependency is a set of scalars.192
Within the vicinity of 〈X,T, Y 〉, we start from measuring dependencies between {X, PCX} and193 {Y, PCY } by conditioning on {T, PCT }. Intuitively, if 〈X,T, Y 〉 is a v-structure, conditioning on194 T or T ’s descendants tends to strengthen the dependency between PCX and PCY since the paths195 passing X − T − Y are unblocked; otherwise, conditioning on T tends to weaken the dependency196 between PCX and PCY because T blocks the paths passingX−T −Y . Therefore, such conditional197 dependencies reflect potential asymmetry to distinguish v-structure and non-v-structure. Formally,198
Definition 7 (Domain of bivariable). Denoted as B := {X, PCX} × {Y, PCY } ≡199 {X ∼ Y,X ∼ PCY , PCX ∼ Y, PCX ∼ PCY }, here symbol × is Cartesian product.200 Definition 8 (Sepsets). Denoted as S := {S : X⊥Y |S, S ⊂ PCX ∪ T, or S ⊂ PCY ∪ T}. Under201 faithfulness assumption, sepsets S is an ensemble where each item is a subset of variables within the202 vicinity that d-separates X and Y .203
Definition 9 (Domain of conditional). Denoted as C := {∅, T,PCT } ∨ {∅, S} ≡204 {∅, T,PCT ,S,S ∨ T,S ∨ PCT }, where PCT := {{I} : I ∈ PCT } which is an ensemble version205 of PCT , and S ∨ PCT := {S ∪ I : S ∈ S, I ∈ PCT }. Here symbol ∨ is element-wise union.206
We exploit the extended conditional dependencies from B × C, i.e., we pick a bivariable from B207 and a conditional from C, and calculate the extended conditional dependency. There are in total208 |B| × |C| = 24 extended conditional dependencies.209 Lemma 1. Sepsets S of any UT of a canonical dataset is non-empty. All proofs are available in the210 supplementary material.211
Remark 1. We intend to restrict the sepsets within the vicinity of 〈X,T, Y 〉. Lemma 1 shows the212 existence of such d-separation sets within vicinity. Furthermore, searching for all d-separation sets is213 highly time-consuming, thus the computational cost can also be saved drastically.214
• Entanglement within Vicinity215 Structural entanglement reflects complex structure within the vicinity of 〈X,T, Y 〉. Variables X , Y216 and T can mutually share common neighbors, and their neighbors may also overlap with sepsets217 S. We call such overlaps structural entanglement. Intuitively, stronger entanglement indicates218 denser structure of vicinity thus making the UT less likely to be identifiable. Therefore, structural219 entanglement is an important aspect for featurization. Specifically, we exploit the overlap coefficient220 [33] to measure the entanglement:221
Definition 10 (Overlap coefficient). OLP (A,B) := |A ∩B|/min (|A|, |B|), where A and B are222 two sets of variables. We extend this formula to support ensemble as input:223
(Extended) Overlap coefficient: OLP (A,S) := ∑|S|
i=1 OLP (A, Si) /|S|. Naturally, we consider the224 entanglement in terms of overlap coefficient on each pair of items in domain {PCX , PCY , PCT ,S}.225 Thus, we use 6 scalars to represent the entanglement within the vicinity of a UT.226
• Embedding227 We aim to represent the dependencies and entanglement by a feature vector with fixed dimensionality,228 which can be used to train ML4C-Learner. Regarding each extended conditional dependency A ∼229 B|Z : A ∼ B ∈ B,Z ∈ C, it consists of a set of scalars with varied set size across UTs, we230 adopt the kernel mean embedding technique in [30] to represent each A ∼ B|Z as a vector with231 fixed dimensionality. We further modify the embedding algorithm by adding min {A ∼ B|Z} and232 max {A ∼ B|Z} as two additional features. We directly use the 6 scalars to represent structural233 entanglement without further transformation. We concatenate all the embedded vectors to form the234 final feature vector, as input for ML4C-Learner.235
4.3 Learnability236
We have presented ML4C’s featurization and started seeing that conditional dependencies and237 structural entanglement have potential to reveal asymmetry to distinguish v-structure and non-v-238 structure UTs. Now we provide rigorous analysis to show that, for a canonical dataset with sufficient239 samples, ML4C-Learner tends to a perfect classifier. To prove this, we first propose a surrogate object240 called discriminative predicate:241
Definition 11 (Discriminative predicate). A discriminative predicate is a binary predicate function242 with domain as ML4C’s feature set. A discriminative predicate can be viewed as a special classifier243 with pre-specified form of mechanism (i.e., not learned from data).244
Definition 12 (Weak / Strong discriminative predicate). Whenever a discriminative predicate takes245 the feature vector of a UT as input, a weak discriminative predicate satisfies one of the following246 two criteria; a strong discriminative predicate satisfies both: i) it is evaluated to TRUE if the UT is a247 v-structure; ii) it is evaluated to FALSE if the UT is not a v-structure.248
By definition, a weak discriminative predicate exhibits discriminative power since it is evaluated false249 implies the UT is a non-v-structure (or true implies v-structure). A strong discriminative predicate250 can be viewed as a perfect classifier. Denote {A ∼ B|Z} > δ := X ∼ Y |Z > δ : ∀X ∈ A, Y ∈251 B,Z ∈ Z , then we have:252 Lemma 2 (Existence of weak discriminative predicate). For a canonical dataset with infinite samples,253 the following are three weak discriminative predicates: i) {X ∼ Y |T} > 0, ii) {X ∼ Y |PCT } = 0254 , iii) {PCX ∼ PCY |S ∪ T} > 0.Take {X ∼ Y |T} > 0 as an example, 〈X,T, Y 〉 is a v-structure255 ⇒ T is a collider ⇒ T unblocks X and Y through path X − T − Y ⇒ {X ∼ Y |T} > 0 ⇒256 min {X ∼ Y |T} > 0, where min {X ∼ Y |T} is a feature of ML4C-Learner since X ∼ Y ∈257 B, {T} ∈ C.258 Lemma 3 (Existence of strong discriminative predicate). For a canonical dataset with infinite259 samples, the following are three strong discriminative predicates: i) OLP(T,S) = 0, ii) OLP(T,S) <260 0.5, iii) OLP(T,S) < 1 ∧min {X ∼ Y |T ∪ S} > 0.261
CPC/MPC/GLL-MB as special cases of ML4C-Learner: Predicate OLP (T,S) = 0 ⇐⇒ ∀S ∈262 S, T /∈ S, which states that the predicate is TRUE if T is not in any d-separation set of X and Y .263 Having correct skeleton provided, this is the criterion of Conservative PC algorithm (CPC) [25] for264 identifying v-structures. Thus, CPC can be viewed as a special case of ML4C by replacing ML4C-265 Learner with such a pre-specified logic; OLP (T,S) < 0.5 indicates that if more than half of the d-266 separation sets do not contain T , then the UT is oriented as a v-structure, which is called majority rule267 PC algorithm (MPC) [9]; predicate OLP (T,S) < 1∧min {X ∼ Y |T ∪ S} > 0⇒ ∃S ∈ S, T /∈ S268 and X and Y are dependent when conditioning on T ∪ S, which is used for GLL-MB [2] to more269 securely identify v-structures. These predicates are with suboptimal performance because only a270 small portion of features are exploited and the overall loss function of training data is disregarded,271 thus in practice when an appropriate machine learning model is adopted, ML4C-Learner achieves272 better performance.273
Theorem 1. ML4C-Learner tends to a perfect classifier on classifying a canonical dataset with274 sufficient samples.275
5 Evaluation276
Benchmark Datasets We use discrete datasets sampled by all 24 networks from bnlearn reposi-277 tory [28] for evaluation. For each network, we sample 1k, 5k, 10k, 15k, 20k records for use.278
ML4C’s Training and Inference We generate ML4C’s training data synthetically (which is also279 used for other SCL competitors). Specifically, 400 unique DAGs are randomly generated by two280 models: Erdős-Rényi (ER) model [11] and Scale-Free (SF) model [1], with the number of nodes281 ranging from 10 to 1,000. A standard random forward data generation process is applied to obtain282 10k observational samples for each graph. We further extract UTs from the 400 DAGs, consisting of283 97,010 v-structures (label = 1) and 195,691 non-v-structures (label = 0). We use these instances to284 train ML4C-Learner, which is implemented by a XGBoost [5] binary classifier with default hyper-285 parameters and we use binary cross-entropy as the loss function. Details on our synthesis procedure,286 configurations and implementation of ML4C-Learner are available in the supplementary material.287
Competitors We categorize state-of-the-art causal learning algorithms from two aspects, supervised288 vs. unsupervised, and can or cannot take skeleton as input. We choose Jarfo [12], D2C [4], RCC [20],289 and NCC [21] as SCL competitors. Same as ML4C, all these algorithms can and do require skeleton290 as input. All these algorithms use ML4C’s training set for training but with different learning target291 extracted. Regarding unsupervised algorithms, we choose PC [31], Conservative-PC (CPC) [26],292 Majority-rule PC (MPC) [7], GLL-MB (GMB) [2], GES [6], Grow-Shrink (GS) [22], Hill-Climbing293 (HC) [16], and Conditional Distribution Similarity (CDS) [12]. which can also take skeleton as input.294 Lastly, we also compare with DAG-GNN (DGNN) [35], BLIP [27], and GOBNILP (GNIP) [8],295 which are unsupervised algorithms but cannot take skeleton as input. All these competitors are296 capable of dealing with discrete data. All experiments are done in a Windows Server with 2.8GHz297 Intel E5-2680 CPU and 256G RAM. Details are in the supplementary material.298
Design Our evaluation mainly consists of two parts: end-to-end comparison with competitors on299 benchmark datasets, and in-depth experiments on ML4C’s learnability. The latter is further divided300 into four aspects: i) Towards a perfect classifier. As stated in proposition proposition 2, ML4C-301 Learner is the core component and we would like to know how far it is from a perfect classifier.302 ii) Reliability (against weak / strong discriminative predicates). As stated in lemma 2 and 3, there303 exist weak and strong discriminative predicates, which have discriminative power and thus are helpful304 for ML4C-Learner. Some strong discriminative predicates are equivalent to specific logics of existing305 work such as CPC or GLL-MB. Thus, we would like to see how ML4C-Learner takes the advantage306 of machine learning, to learn a more reliable classification mechanism (which is also latent and307 more sophisticated) than individual weak / strong discriminative predicates. iii) Robustness (against308 varied sample size). It is known that many causal learning algorithms lack robustness w.r.t sample309 noise for finite datasets [20], especially CI tests are error-prone on small samples for constraint-310 based algorithms. We would like to evaluate the robustness of ML4C (i.e., the latent classification311 mechanism) against varied sample sizes. iv) Transferability. It’s important for a machine learning312 model to generalize well to various types of testing data which are different from training data, such313 as different scale (#nodes), graph sparsity, different generating mechanisms, etc.314
Metrics We use two standard metrics for performance evaluation: Structural Hamming Distance315 (SHD) and F1-score. For each dataset, we measure the SHD / F1-score of the output CPDAG (learned316 by a specific algorithm) against the ground truth CPDAG. Specifically, SHD is calculated at CPDAG317 level, which is the smallest number of edge additions, deletions, direction reversals and type changes318 (directed vs. undirected) to convert the output CPDAG to ground truth CPDAG. F1-score is calculated319 over identifiable edges. Roughly, F1-score can be viewed as a normalized version of SHD. Now we320 present the experiment results:321
End-to-End Comparison Due to page limit, we report SHD and F1-score of all algorithms on322 19 large-scale datasets (full results including other 5 smallest and trivial datasets are available in323 the supplementary material), as depicted in Table 1. ‘-’ means the algorithm fails on the dataset324 (either out-of-memory / exceeds 24 hours execution time / break caused by unknown errors). ML4C325 significantly outperforms all other competitors. The average F1-score of ML4C is the highest (0.92,326 first column in Table 2). Moreover, ML4C exhibits the most stable performance across all datasets,327 its average ranking is 1.5 ± 0.7, while the second best is GLL-MB (GMB), with average ranking328
4.4 ± 2.4. Among the competitors, NCC ranks #1 on 8 datasets (note that ML4C ranks #1 on 11329 datasets), but its performance fluctuates. Overall it only ranks 5.1± 4.2. Last but not least, ML4C330 shows high accuracy (F1>0.9) on very large-scale datasets (e.g., medicine datasets ‘munin*’ [3])331 while max(others) ∼ 0.6.332
Towards a Perfect Classifier The last row of Table 1 shows the performance of ML4C-Learner333 component at UT level by UT-F1 (i.e., F1-score of classifying UTs): such UT level accuracy is334 crucial for causal learning on discrete data, since the set of v-structures is invariant across all Markov335 equivalent DAGs and it can fully recover the CPDAG. The average F1-score of ML4C-Learner is336 0.90± 0.13, which shows promising results towards a perfect classifier.337
Reliability We manually identify 4 strong discriminative predicates and 4 weak discriminative338 predicates and treat each one as a replacement of ML4C-Learner. Table 2 shows the performance of339 these predicates. Although most predicates show value on discriminating UTs (e.g., 5/8 predicates340 are with >0.6 F1-score), ML4C-Learner has higher performance (average F1-score = 0.92) than each341 individual predicate (best average F1-score = 0.77). Thus, it is evident that ML4C-Learner learns a342 more reliable classification mechanism, by taking advantage of machine learning techniques.343 Robustness To evaluate robustness, ML4C is trained on synthetic datasets with sample size =344 10k, but it is tested on benchmark datasets with different sample sizes: 1k, 5k, 10k, 15k and 20k345 respectively. Table 3 shows that ML4C exhibits satisfactory robustness (decrease of F1-score is less346 than 0.1) against sample size on most datasets (17/18, except for ‘hailfinder’).347 Transferability To evaluate whether ML4C generalizes well to various types of testing data, we348 vary scale (#nodes), graph sparsity, generating mechanism and sample size. ML4C is trained on349 a fixed configuration but it is tested with different domains (i.e., data generated under different350 configuration). Result is depicted in Table 4, ML4C transfers well on different domains, e.g., even351 if it is trained on 10 nodes but tested on 1,000 nodes (last column of the first row in Table 4), the352 F1-score only drops 0.02.353
6 Conclusion and Future Work354
We have proposed a supervised causal learning algorithm ML4C, with theoretical guarantee on355 learnability and remarkable empirical performance. More importantly, ML4C shows promising356 results on validating the effectiveness of supervision. To make SCL practical in real-world scenarios,357 one important direction for future work is to identify reliable and accurate skeleton from data,358 considering ML4C requires skeleton as additional input.359
References360 [1] Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern361 physics, 74(1):47, 2002.362
[2] Constantin F Aliferis, Alexander Statnikov, Ioannis Tsamardinos, Subramani Mani, and Xenofon D363 Koutsoukos. Local causal and markov blanket induction for causal discovery and feature selection for364 classification part i: algorithms and empirical evaluation. Journal of Machine Learning Research, 11(1),365 2010.366
[3] Steen Andreassen, Marianne Woldbye, Bjørn Falck, and Stig K Andersen. Munin: A causal probabilistic367 network for interpretation of electromyographic findings. In Proceedings of the 10th international joint368 conference on Artificial intelligence-Volume 1, pages 366–372, 1987.369
[4] Gianluca Bontempi and Maxime Flauder. From dependency to causality: a machine learning approach. J.370 Mach. Learn. Res., 16(1):2437–2457, 2015.371
[5] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd372 acm sigkdd international conference on knowledge discovery and data mining, pages 785–794, 2016.373
[6] David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine374 learning research, 3(Nov):507–554, 2002.375
[7] Diego Colombo and Marloes H Maathuis. Order-independent constraint-based causal structure learning. J.376 Mach. Learn. Res., 15(1):3741–3782, 2014.377
[8] James Cussens. Bayesian network learning with cutting planes. arXiv preprint arXiv:1202.3713, 2012.378
[9] Colombo Diego and H. Maathuis Marloes. Order-independent constraint-based causal structure learning.379 Journal of Machine Learning Research, 15(116):3921–3962, 2014.380
[10] Rui Ding, Yanzhi Liu, Jingjing Tian, Zhouyu Fu, Shi Han, and Dongmei Zhang. Reliable and efficient381 anytime skeleton learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34,382 2020.383
[11] P. Erdős and Rényi A. On random graphs. Publicationes, Mathematicae, 6:290–297, 1959.384
[12] José AR Fonollosa. Conditional distribution variability measures for causality detection. In Cause Effect385 Pairs in Machine Learning, pages 339–347. Springer, 2019.386
[13] Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical387 models. Frontiers in genetics, 10:524, 2019.388
[14] Patrik Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal389 discovery with additive noise models. Advances in neural information processing systems, 21:689–696,390 2008.391
[15] Dominik Janzing, Joris Mooij, Kun Zhang, Jan Lemeire, Jakob Zscheischler, Povilas Daniušis, Bastian392 Steudel, and Bernhard Schölkopf. Information-geometric approach to inferring causal directions. Artificial393 Intelligence, 182:1–31, 2012.394
[16] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press,395 2009.396
[17] Steffen L Lauritzen. Graphical models, volume 17. Clarendon Press, 1996.397
[18] Hebi Li, Qi Xiao, and Jin Tian. Supervised whole dag causal discovery. arXiv preprint arXiv:2006.04697,398 2020.399
[19] Honghao Li, Vincent Cabeli, Nadir Sella, and Hervé Isambert. Constraint-based causal structure learning400 with consistent separating sets. In 33rd Conference on Neural Information Processing Systems (NeurIPS401 2019), 2019.402
[20] David Lopez-Paz, Krikamol Muandet, and Benjamin Recht. The randomized causation coefficient. J.403 Mach. Learn. Res., 16:2901–2907, 2015.404
[21] David Lopez-Paz, Robert Nishihara, Soumith Chintala, Bernhard Scholkopf, and Léon Bottou. Discovering405 causal signals in images. In Proceedings of the IEEE Conference on Computer Vision and Pattern406 Recognition, pages 6979–6987, 2017.407
[22] Dimitris Margaritis. Learning bayesian network model structure from data. Technical report, Carnegie-408 Mellon Univ Pittsburgh Pa School of Computer Science, 2003.409
[23] Christopher Meek. Causal inference and causal explanation with background knowledge. arXiv preprint410 arXiv:1302.4972, 2013.411
[24] Christopher Meek. Strong completeness and faithfulness in bayesian networks. arXiv preprint412 arXiv:1302.4973, 2013.413
[25] Joseph Ramsey, Jiji Zhang, and Peter Spirtes. Adjacency-faithfulness and conservative causal inference.414 arXiv preprint arXiv:1206.6843, 2012.415
[26] Joseph Ramsey, Jiji Zhang, and Peter L Spirtes. Adjacency-faithfulness and conservative causal inference.416 arXiv preprint arXiv:1206.6843, 2012.417
[27] Mauro Scanagatta, Cassio Polpo de Campos, Giorgio Corani, and Marco Zaffalon. Learning bayesian418 networks with thousands of variables. In NIPS, pages 1864–1872, 2015.419
[28] Marco Scutari. Bayesian network repository. URL http://www. bnlearn. com, 2012.420
[29] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear421 non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.422
[30] Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A hilbert space embedding for distributions.423 In International Conference on Algorithmic Learning Theory, pages 13–31. Springer, 2007.424
[31] Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social science425 computer review, 9(1):62–72, 1991.426
[32] Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and427 search. MIT press, 2000.428
[33] M.K. Vijaymeena and K. Kavitha. A survey on similarity measures in text mining. Machine Learning and429 Applications: An International Journal, 3(2):19–28.430
[34] Kui Yu, Jiuyong Li, and Lin Liu. A review on algorithms for constraint-based causal discovery. arXiv431 preprint arXiv:1611.03977, 2016.432
[35] Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gnn: Dag structure learning with graph neural networks. In433 International Conference on Machine Learning, pages 7154–7163. PMLR, 2019.434
[36] Xun Zheng, Bryon Aragam, Pradeep Ravikumar, and Eric P Xing. Dags with no tears: Continuous435 optimization for structure learning. arXiv preprint arXiv:1803.01422, 2018.436
Checklist437 1. For all authors...438
(a) Do the main claims made in the abstract and introduction accurately reflect the paper’s contribu-439 tions and scope? [Yes]440
(b) Did you describe the limitations of your work? [Yes] See §6. ML4C requires skeleton as441 additional input, thus we put identifying reliable and accurate skeleton from data as future work.442
(c) Did you discuss any potential negative societal impacts of your work? [N/A]443 (d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]444
2. If you are including theoretical results...445
(a) Did you state the full set of assumptions of all theoretical results? [Yes]446 (b) Did you include complete proofs of all theoretical results? [Yes] Details of proofs are in the447 supplementary material due to page limit.448
3. If you ran experiments...449
(a) Did you include the code, data, and instructions needed to reproduce the main experimental450 results (either in the supplemental material or as a URL)? [Yes] We have included the main451 functionalities of ML4C, synthetic data generator, and ML4C’s training data (include instructions)452 for reproducibility. Details are in the supplementary material.453
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?454 [Yes] Key information is in content. Details are in the supplementary material.455
(c) Did you report error bars (e.g., with respect to the random seed after running experiments456 multiple times)? [Yes] We carefully design experiments, by running experiments multiple times,457 including error bars in report to ensure reproducibility. For instance, Table 4 contains error bar458 information.459
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs,460 internal cluster, or cloud provider)? [Yes]461
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...462
(a) If your work uses existing assets, did you cite the creators? [Yes] We compare our algorithm with463 15 SOTA competitors and we have cite these work properly. We also use open source benchmark464 for evaluation and we also properly cite the creators.465
(b) Did you mention the license of the assets? [N/A]466 (c) Did you include any new assets either in the supplemental material or as a URL? [Yes] We share467 new assets, include main functionalities of our algorithm, and our training data. A private URL468 is provided. See details in the supplementary material.469
(d) Did you discuss whether and how consent was obtained from people whose data you’re us-470 ing/curating? [Yes] Due to page limit, the detailed discussion is available in the supplementary471 material.472
(e) Did you discuss whether the data you are using/curating contains personally identifiable informa-473 tion or offensive content? [N/A] We double-checked that the data we are using/curating contains474 no personally identifiable information or offensive content.475
5. If you used crowdsourcing or conducted research with human subjects...476
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?477 [N/A]478
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB)479 approvals, if applicable? [N/A]480
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on481 participant compensation? [N/A]482

Review summaries:
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.

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).  In 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.  Experimental 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.

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.