Causal discovery (CD) or causal structure search is an important problem in many sciences that identifies the causal relationships between variables (Glymour et al. (2019)). The outcome of causal discovery is a causal graph, particularly a directed acyclic graph (DAG) (Williams et al. (2018)) where directed edges represent the cause and effect relationships with an arrow from the cause to the effect (Pearl ( 2009)). Over the last few decades, CD has been studied widely to develop methods that try to capture the underlying causal story from observational data (Glymour et al. (2019), Vowels et al. (2021)). Also, with the ever-increasing application of artificial intelligence (AI) in healthcare, the need to build causality driven AI systems has received increased attention from clinical researchers and policy makers (Yang et al. (2013), Hernán et al. (2019)). Knowing the causal structure plays a significant role in unraveling the data generating mechanism and thereby, facilitates informed decision making. For example, to understand what factors truly influence a clinical outcome, we need to look beyond mere correlations and consider the causal relationships in them. Thus, causal discovery plays a significant role in clinical decision support systems to help researchers understand the causal structure and leverage it to investigate optimum treatment policy.
The gold standard to identify causal relationships is to perform randomized control trials (RCTs) (Hariton and Locascio (2018)). However, RCTs are increasingly considered time-consuming, costly, and often infeasible due to ethical and efficacy concerns (Cai et al. (2021)). For example, to study how the consumption of cocaine has long-term effects on brain health, it would require to conduct an experiment forcing a group of people to consume cocaine for a period of time and observe the outcome at the end. This type of experimental scenarios are risky, unethical as well as time-consuming. Hence, researchers are often left to experiment with non-manipulative observational data (OD) (Vowels et al. (2021)) collected using methods such as human observation, clinical observation, open-ended surveys, and various devices. Over the years, the adoption of computerized systems has increased in healthcare sector. Systems such as such as electronic health records (EHRs) are a great source of observational data (Pacaci et al. (2018)). Researchers have increasingly focused on developing methods to discover causal structures from purely observational data (Spirtes et al. (2000), Pearl (2009)). These methods rely on different assumptions such as causal sufficiency and causal faithfulness to infer causal relations (Spirtes et al. (2000)).
Although there exists a number of approaches for causal discovery, these methods suffer from the lack of a large number of data samples required for reliable and efficient structure search. Most of these methods can find true causal graphs in the presence of an infinite amount of data and appropriate model conditions (Ng et al. (2019)). However, the requirement of a vast amount of data is impractical for real life problems. On a brighter note, often there exists some prior knowledge about the causal relationships between the observables which can be a valuable resource to address the data scarcity problem (Sinha and Ramsey (2021)). For example, in healthcare research we often have some prior knowledge such as expert opinions, findings from prior RCTs, systematic reviews and domain knowledge (Murad et al. (2016), Burns et al. (2011), Bhargava and Bhargava (2007)) about the clinical problem. Considering prior knowledge is important as it can be used to raise the statistical power of CD algorithms to infer causal relationships (Anjum et al. (2009)). Even the consideration of a small set of causal evidence can help to significantly increase the performance of causal discovery (Borboudakis and Tsamardinos (2012)). As per Sinha and Ramsey (2021), background knowledge, such as specifying one variable as the cause of another, can further refine the set of DAGs that enhances model efficiency (Castelo and Siebes (2000)) as well as overcome data limitation.
However, to the best of our knowledge, none of the existing CD approaches have a systematic way to incorporate the available knowledge (such as literature evidence, experts opinion and prior RCTs) during the causal discovery process. Hence, the aim of this research is to propose a framework for the systematic inclusion of existing knowledge during the CD process. Our framework utilizes the existing evidence as a constraint to reward or penalize the search process. It uses a reinforcement learning (RL) based search which is a promising and emerging technique among the various recent advances in CD approaches (Vowels et al. (2021)). To summarize, we aim to impose the prior knowledge as constraints to penalize an RL agent during the structure search process. The prior knowledge constraints are basically the presence or absence of causal edges. The agent will be guided for any violation of the imposed constraints. This will significantly improve performance by reducing the search space and also, enabling a faster convergence to the optimal structure. It will also facilitate the discovery of a greater number of true causal edges. We believe the proposed approach KCRL will add a new dimension by providing a systematic way to impose existing knowledge as constraints during the causal discovery process. We demonstrate the effectiveness of the proposed method on benchmark synthetic clinical datasets namely LUCAS (Lucas et al. (2004)) and ASIA (Lauritzen and Spiegelhalter (1988)). Both datasets are related to the diagnosis, prevention, and cure of lung cancer. We further experimented on a benchmark real dataset named the SACHS (Sachs et al. (2005)) that represents a protein signalling network. Moreover, we validated the performance of our approach on a clinical application that measures the effect of oxygen therapy intervention in the intensive care unit (ICU) patients (Gani et al. (2020). Our contributions are summarized below:
• We propose a novel causal discovery framework that can be used in any domain including healthcare where some prior knowledge such as expert opinion, domain knowledge, literature evidence, prior RCTs and experimental evidence are available. Our framework is novel as it incorporates the prior knowledge as constraints during the causal search process and also, penalizes the search process for constraint violations.
• The components of our framework such as the search process and reward mechanism are modular. It means these can be adopted from different existing implementations of these modules and can be varied based on the experimental context.
• We formulate a stopping criterion for our algorithm. It based on the experimental findings and depends on the performance metrics. When these metrics exceed a certain threshold or when their values become constant with increasing epochs, the stopping point is reached.
• We validate the effectiveness of our proposed framework by conducting experiments on benchmark synthetic and real datasets with available ground truth graphs. The experimental results demonstrate that our approach outperforms the baseline approaches over different evaluation metrics in all the experiments.
• We also demonstrate its validation on a real-life clinical problem related to oxygen therapy in ICU. The clinical application entails a timely and important healthcare problem applicable in a variety of disease conditions including severe acute respiratory syndrome coronavirus-2 (SARS-CoV-2) patients.
Learning causal structures from observational data is a significant problem in machine learning. Knowing the causal graph can unravel the data generating mechanism which can have an important impact on clinical decision making. It can help clinicians understand the disease mechanism better and explore their causes. However, often the existing algorithms fail to discover the true causal relations due to lack of a large amount of observational data.
On the contrary, fortunately, we often have some prior knowledge or experimental evidence available. In healthcare domain, we have previous findings on the medical problems in different forms such as prior RCTs, domain knowledge, expert opinion and evidence from literature. These resources are not utilized by the existing approaches during the discovery process. The actual power of the algorithm and data can be harnessed only when some form of prior knowledge is used. The utilization of the existing evidence can improve the performance of the discovery process as well as provide a solution to the data limitation problem. Our framework provides a systematic way to utilize the prior findings during the structure search process. This will improve the discovery of causal graphs which are important to estimate treatment effects to help healthcare researchers make better and informed decisions. It will also optimize the search process to enable an early convergence to the optimal structure. Our approach can be used in a wide variety of healthcare problems whenever there exists some prior knowledge.
The cost ineffectiveness or ethical concerns of randomized experiments led to the consideration of causal discovery from purely observational studies with greater importance (Cai et al. (2021)). A considerable amount of studies have been developed over the past few decades to learn causal structure from observational data. A summarized discussion of these approaches is given below. Among the various approaches to find the underlying causal graph, constraint-based methods such as PC and FCI (Harris and Drton (2013), Spirtes et al. (2000)) perform conditional independence tests to check dependency between the variables. On the other hand, score-based methods generally optimize a score function (Yu et al. (2019)) and rely on local heuristics to perform the search. The most widely used score-based method Greedy Equivalence Search (GES) (Chickering ( 2002)) finds causal structures by greedily adding or deleting edges until it reaches a local maximum. Though GES is expected to work well with infinite data and appropriate model conditions, it gives much less satisfactory results with a finite amount of the data (Ng et al. (2019)). Hybrid methods such as Max-Min Hill-Climbing (MMHC) (Tsamardinos et al. (2006)) combine conditional dependency tests with a score-based approach. Another category of causal discovery approaches is based on Functional Causal Models (FCMs) (Glymour et al. (2019)). ANM (Hoyer et al. (2008)) is such a function-based approach for nonlinear causal discovery with additive noise models. Among other noteworthy function-based approaches, DirectLiNGAM (Shimizu et al. (2011)) which is a direct learning algorithm and ICALiNGAM (Shimizu et al. (2006)) which is an ICA-based learning algorithm are noteworthy both of which are linear non-Gaussian acyclic (LiNGAM) models. Recently, there have been an increasing number of methods which leverage the advantages of continuous optimization to seek the structure from data which resulted in the union of causal discovery and deep learning methods (Vowels et al. (2021)). These approaches formulate the combinatorial graph-search problem into a continuous optimization problem. DAGs with NOTEARS (Zheng et al. (2018)), first formulated the combinatorial graph search problem as a continuous optimization problem. DAG-GNN (Yu et al. (2019)) extends NOTEARS by incorporating a deep generative model known as Variational AutoEncoder (VAE) with neural network functions and providing a variant of acyclicity constraint suitable for deep learning methods. Another method GraN-DAG (Lachapelle et al. (2019)) also extends NOTEARS to identify nonlinear relationships between variables using neural networks. A more efficient version of NOTEARS is GOLEM (Ng et al. (2020)) that can reduce number of optimization iterations. It is basically a likelihood-based structure learning method with continuous unconstrained optimization. CGNN (Goudet et al. (2018)) combines continuous optimization, neural networks and a hill-climbing search algorithm to optimize and learn the structure of a DAG. MaskedNN (Ng et al. (2019)) reformulates the Structural Equation Model (SEM) in an augmented form with a binary graph adjacency matrix. CAREFL (Khemakhem et al. (2021)) combines causal discovery with normalizing flows, a deep learning framework. DEAR (Shen et al. (2020)) combines a Variational AutoEncoder (VAE) with an adversarial loss in order to infer a latent space with causal structure. RL-BIC (Zhu et al. (2019)) uses reinforcement learning (RL) to find the causal graph with the best score. In CORL, Wang et al. (2021) formulated the ordering search problem as a multi-step Markov decision process and used RL to optimize the proposed model based on the reward mechanisms designed for each ordering.
Causal discovery with prior knowledge Over the years, studies have been conducted to include existing evidence in the causal search process and see how this inclusion can benefit the discovery process. Mahony et al. (2001) proposed an approach for encoding prior knowledge into learning algorithms by imposing a Riemannian geometry on parameter space. Borboudakis et al. (2011) presented a constraint-based approach to incorporate prior knowledge in causal models by orienting the unoriented edges of a partially oriented ancestral graph (PAG) based on the available causal edges. Flores et al. (2011) considers expert elicited pairwise relations between two variables (pairwise priors) where each edge has a frequency associated with it. The model presented by Mansinghka et al. (2012) assumes that variables come in one or more classes, and the prior probability of an edge existing between two variables is a function only of their classes. Borboudakis and Tsamardinos (2012) presents algorithms for incorporating path constraints to Partial DAGs (PDAGs) and PAGs which use chronological backtracking search, with forward checking and a pruning rule. Xu et al. (2015) introduces three types of prior knowledge given by domain experts such as existence of parent node, absence of parent node, and distribution knowledge of nodes and edges into the Markov chain Monte Carlo (MCMC) algorithm. Oyen et al. (2016) presents a novel Bayesian network (BN) discovery algorithm for learning a DAG via statistical inference of conditional dependencies from observed data with an informative prior on the partial ordering of variables. Another method PKCL (Wang et al. (2020)) leverages the Markov Blanket (MB) sets learned in the local stage to learn the global BN structure, in which prior knowledge is incorporated to guide the global learning phase. Sinha and Ramsey (2021) presents an approach named Kg2Causal that uses the knowledge graph (KG) derived edges to guide the data-driven inference of a causal Bayesian network. It generates 100 random DAGs, optimizes them using Tabu search (Gendreau (2003)), extract edges present in the KG and incorporate them as a prior.
Despite the progress in causal discovery and the incorporation of the prior knowledge, there is a lack of systematic approach to reward or penalize the search algorithm for supporting or violating existing evidence. However, such an approach can help to improve the performance of the causal discovery process and also, incorporate the evidence well.
Our framework KCRL is inspired by the recent advances in continuous optimization strategies for structure search. KCRL imposes prior knowledge as constraints and uses a rewardpenalty mechanism to guide the search process. In this section, at first we provide a brief introduction to the importance of prior knowledge and how prior knowledge can be used as a constraint during causal discovery in RL-based search. Then, in the following subsections, we discuss our proposed framework in details as well as its implementation and complexity analysis.
We often have some prior knowledge available for causal modeling in many applications. For example, in medicine, most of the time we have prior knowledge about etiology, symptoms, and treatment of underlying diseases or conditions in biomedical literature or knowledge bases (Sinha and Ramsey (2021)). This gives us an ample opportunity to leverage prior knowledge to address data scarcity. A number of works highlight the importance of inclusion of background knowledge in causal structure learning. A recent work by Andrews et al. (2020) shows how the FCI algorithm is sound and complete with the incorporation of tired background knowledge. They also mention that incorporation of the available evidence while causal discovery not only causes identification of the additional causal relationships but also helps to identify unresolved causal relationships. As per Borboudakis and Tsamardinos (2012), even a few causal constraints can orient a significant number of edges. Xu et al. (2015) mentions that an algorithm can adopt prior knowledge with even very small confidence with an inherent probability and have an influence on the search process to find a better structure. In a Bayesian network discovery approach, Oyen et al. (2016) mentioned that, without expert knowledge about the ordering of the variables, many of the edges learned are the reverse of the true edges. Thus, a hybrid approach of combining the observational data with expert-backed knowledge in the form of a constraint or prior probability reduces both the search space and biases in the search, hence improving the learning efficiency (O'Donnell et al. (2006)). From the above discussion, we can see how important it is to utilize the existing evidence during CD and even a small amount of prior knowledge can have significant effect upon the causal discovery process.
Prior knowledge in RL based search Even though the use of reinforcement learning for causal discovery has not yet been fully explored, this technique has significant opportunities in finding causal structures if utilized strategically (Vowels et al. ( 2021)). Recently, RL has achieved promising results in causal discovery from observational data (Wang et al. (2021)). RL solves a problem by trial and error, and employs an iterative reward feedback 2018)). Constraints such as existing evidence, acyclity, etc. can be imposed to guide an RL agent towards an optimized policy. A feedback can be sent by rewarding or punishing the agent for following or violating the constraints, respectively. The positive or negative rewards not only ensures the enforcement of the constraints, but also ensures formalising a better search strategy for discovering the causal graph. A better feedback or reward mechanism is formed by penalizing the search process for each incorrectly identified edge or edge orientation w.r.t. the prior information. This will alert an RL agent regarding its graph formation strategy.
Our proposed framework (Figure 1) for causal discovery shows how the existing evidence (known causal edges) is used to guide the search process. Here, prior information of two types can be used. If there exists a directed edge from one node to another node, then it is denoted by 1 and if there exists no causal edge between two nodes, then it is represented with 0. At the beginning, the observational data is provided as input to the RL agent. Its task is to convert data to a causal graph (precisely an adjacency matrix of the graph). Data to adjacency matrix conversion can be done via any existing encoder-decoder architecture such as the Transformer model (Vaswani et al. (2017)), Neural Tensor Network (NTN) model (Socher et al. (2013)), etc. Next, the generated adjacency matrix is passed through a comparator. The comparator consists of information regarding the existing edges and their orientation. Task of the comparator is to compare the edges in the produced graph by the agent with the subset of the true edges and determine the total number of mismatched edges p. For each mismatched edge, it increases the penalty by one. After the comparison, it multiplies the total number of mismatched edges p with a penalty weight β and this
Causal Discovery With Prior Knowledge Constraints product is the final penalty P k for the generated graph.
The graph is then scored using a score function such as the Bayesian Information Criterion (BIC) (Equation 1
The penalty P k w.r.t evidence is then summed up with the score S and the acyclicity penalty P a to compute the total reward R (Equation 5). Here, both the penalties for violation of acyclicity and prior knowledge constraints are negative in the reward function (Equation 5). Finally, the reward R (Equation 5) is fed back to the RL agent as a summary of its performance in the present state. This feedback assists an RL agent to determine whether its search strategy is correct or needs to be updated. The entire process ends when the stopping criterion S c is reached (details in subsection 3.2). S c depends on the performance metrics P m which is also discussed in subsection 3.2. The output is the best rewarded causal graph among all the generated graphs. The step by step process of our framework is in Algorithm 1.
= S(G) + P a + P k (5)
Based on the experimental observations, we formulated some criteria which if satisfied, will be sufficient to stop the discovery process. There can be a number of conditions based on which the stopping criterion S C can rely on. During the structure discovery process, if over a period of time there is no change in the value of the performance metrics P m (False Discovery Rate (FDR), True Positive Rate (TPR) and Structural Hamming Distance (SHD)), then we can consider to stop the discovery process (details of the metrics are in Section 5). As well as, if the majority of the metrics reach a certain threshold T and the minimum number of iterations I min required for the graph discovery is reached, then the process can be stopped. may be required to have a threshold value greater than or equal to 98% whereas, in another domain the requirement can be much lower. Again it might be the case that the required threshold for a metric is reached within 1000 iterations. But, 1000 iterations might not be sufficient enough for discovering the optimal casual structure. So, there exists a trade off between the number of iterations and the threshold. It is therefore necessary to have a minimum number of iterations before deciding to stop the search process. This number can be decided by monitoring the model's performance. Equation 6 represents the stopping criteria S c where i is the iteration number and n = the total number of iterations the model runs.
S c = lim i→n ∆P m = 0 ∥ P m = T ∧ I min (6)
To implement our framework, we choose the different components in our model from the following existing works. A Self-Attention based encoder-decoder architecture (Vaswani et al. (2017)) have been used to convert data to an adjacency matrix. The encoder is fed with input data distributions and the decoder takes the encoded information from the encoder to output an adjacency matrix of the graph. For the search strategy, the RL approach in Zhu et al. (2019) has been adopted in which they have used an Actor-Critic RL algorithm for graph search and used a BIC (Neath and Cavanaugh (2012)) function (Equation 1) to score the generated graphs. To check for cycles in the graphs, the acyclity enforcing function by Zheng et al. (2018) has been used. To use prior information during the causal discovery, we implemented a comparator that compares the adjacency matrix produced by the decoder with the existing edge information stored in a prior knowledge matrix. Our framework uses the Equation 7to compute reward where its goal is to discover the causal graph with the maximum reward. In this equation, the first term calculates the score of the graph, the second term computes the penalty for acyclicity violation and the last term represents the penalty for violating the prior knowledge where, β represents the penalty weight (details in Section 5 and Appendix D).
Our approach is summarized in Algorithm 1. For the generation of adjacency matrix, it uses a Self-Attention based encoder-decoder (Vaswani et al. (2017)) which has a O(n 2 d) complexity per layer. Computational cost for the score (Equation 1) is O(dn 2 ) which is similar to RL-BIC2 (Zhu et al. (2019)). To check for acyclicity, it requires the computation of matrix exponential with O(d 3 ) cost per iteration. It is same as NOTEARS (Zheng et al. (2018)) which adopts the proximal quasi-Newton algorithm (Zhong et al. (2014)) to reduce the number of iterations (O(d 3 )) needed to converge. While the cost for P k computation is constant. However, it can be seen that computation of the rewards is most expensive due to a large cost of the acyclicity function. This can be minimized by using a different technique to compute acyclicity such as the one in Equation 4.
In this section, we describe the cohort for the Oxygen-therapy (OT) dataset (Gani et al. ( 2020)) that we used for experimentation. It is a real-life clinical application related to the causal effect estimation of oxygen therapy in the ICU patients. It closely followed the study guideline and selection criteria used in a pilot RCT (Panwar et al. (2016)
In this section, we present a comprehensive set of experiments to demonstrate the effectiveness of our proposed approach KCRL. We conduct experiments on benchmark synthetic and real datasets as well as on an important real-world clinical application. We compared the performance of KCRL against several baselines including recent gradient based CD methods such as NOTEARS (Zheng et al. (2018)), GOLEM (Ng et al. (2020)), GraN-DAG (Lachapelle et al. (2019)), RL-BIC2 (Zhu et al. (2019)), and also a couple of function based CD approaches namely ANM (Hoyer et al. (2008)), ICA-LiNGAM (Shimizu et al. (2006)) and DirectLiNGAM (Shimizu et al. (2011)). We discuss these methods and implementation details in Appendix B.
Study design We briefly discuss our experimental settings here. To use existing evidence during the causal discovery process, we consider a subset of the true causal edges (precisely 25% of the total edges) as prior knowledge. We considered multiple datasets for experiments which differ in terms of network size and edge densities. To preserve uniformity in the amount of evidence considered, we used 25% of the true causal edges for all datasets.
For the penalty weight β, we select the initial value as β = 0.1 with an upper limit 1.
After every 1000 epochs, β is increased by 0.1. We select the initial and the incremental values for β based on a grid search. For the ease of clarity, we want to specify how prior knowledge works for our approach. KCRL does not include the prior edges directly into the causal graph. Rather it compares the estimated causal edges with the true causal edges (in evidence set) and penalizes the agent for any mismatch in the edges (see subsection 3.1).
The agent is never informed directly which are the edges that are mismatched. Rather, it only receives a cumulative penalty score for all mismatched edges. Furthermore, we want to clarify that none of the baseline methods except DirectLiNGAM utilize prior knowledge at all for the causal discovery. Although DirectLiNGAM mentions that if some prior knowledge on a part of the structure is available, then the number of causal orders and connection strengths to be estimated gets smaller. However, it explicitly does not use prior knowledge for the structure search. Also, to the best of our knowledge, the other prior knowledge based methods discussed in Section 2 do not have any reproducible code implementations available to use in the comparative analysis. Nevertheless, we believe a comparison with the baseline approaches help us to understand how the absence or presence of prior knowledge during the search impacts the performance of causal discovery.
Evaluation criteria The estimated graphs were evaluated using three metrics commonly used to evaluate causal graphs: the false discovery rate (FDR), the true positive rate (TPR), and the structural hamming distance (SHD). All these metrics signify a measure of accuracy or the performance of the discovery process. FDR computes the fraction of the estimated edges that are false, which gives a numerical estimate of how enriched the discoveries are compared to the ground-truth (Benjamini and Hochberg (1995)). SHD computes the number of edge insertions, deletions or flips required to transform the estimated graph to the true causal graph (Norouzi et al. (2012)). Hence, lower the SHD and FDR, closer is the estimated graph to the true causal graph. TPR measures the model accuracy (van Ravenzwaaij and Ioannidis (2019)) by computing the probability of the estimated true edges (Wang et al. (2021)). Thus, higher the TPR, better the performance of causal discovery methods.
The performance of KCRL and the baseline methods on the benchmark synthetic datasets (LUCAS and ASIA) are shown in Table 1. Here, we present the performance metrics to compare our method against the baselines. In the following paragraphs, we discuss the experimental results in details. ASIA dataset We further experimented on another synthetic dataset named ASIA (Lauritzen and Spiegelhalter (1988)), also known as the Lung Cancer dataset. This is a small toy network that models lung cancer in patients from Asia. Precisely, it describes different lung diseases (tuberculosis, lung cancer or bronchitis) and their relations to smoking and patients visits to Asia. This is commonly used as a benchmark dataset for graphical models.
It is a small network with 8 nodes and 8 edges (see Appendix A). For experimentation, with sample size n = 1000, we used 2 ground-truth edges (25% evidence). From the empirical results reported in Table 1, it can be observed that KCRL achieved the best TPR (0.75) and SHD (3) compared to the baselines. It has the second best FDR (0.25) which is lower than the other methods except for Gran-DAG and DirectLiNGAM that have zero false discoveries. ANM and GOLEM perform quite poorly with similar FDRs and TPRs and a slightly varied SHD. NOTEARS is the worst performing method w.r.t all the metrics. RL-BIC2 seems to have an average performance compared to all the approaches. The estimated graphs compared against the ground-truth are shown in Figure 2.
We consider a well known real dataset, SACHS (Sachs et al. (2005)).
It is a widely used dataset for benchmarking causal discovery methods. It contains the Although it has both observational and interventional data, we consider the observational data with n = 853 samples as our approach only relies on observed data. KCRL achieves the best results in terms of the TPR (0.35) and SHD (11). NOTEARS has almost similar results as KCRL with slightly higher SHD and an identical TPR. However, it has a higher FDR. GraN-DAG has the best FDR 0.25 but lacks significantly in TPR. RL-BIC2 and ICA-LiNGAM both perform quite similarly with equal values of TPR and SHD. GOLEM has the second lowest TPR and the highest FDR resulting in SHD 24.
Although DirectLiNGAM has a moderate FDR and SHD, however, it does not perform well in terms of true positives and has the lowest TPR (0.12). ANM failed to discover any causal relationships and produced an empty graph for this dataset. Hence we did not report the metrics for ANM. We think that ANM focuses more on nonlinear causal discovery with additive noise models and thus, fails to identify the causal relationships in SACHS. For experimentation, we used n = 1000 samples and 16 edges (25% true edges) which were selected based on literature evidence. The performance metrics for this dataset are presented in Table 2. KCRL outperformed others in two out of the three evaluation metrics (FDR and SHD). Although, NOTEARS has the best TPR, however, its performance lacks heavily in the other two metrics. Overall, GOLEM and ANM perform the least. This could be due to the dense nature of the graph. GraN-DAG does not perform well either, as it requires the computation of a large number of optimization parameters for this dataset. ICALiNGAM and DirectLiNGAM perform moderately compared to others since they are not good at modelling nonlinear relationships.
KCRL outperformed the baseline approaches in SHD (Figure 4) for all four datasets. This signifies its reliability in estimating the minimal-distant true causal graph. Also, w.r.t. FDR (Figure 3 (a)), it has the best results for LUCAS and OT datasets and, the best TPR (Figure 3 (b)), for ASIA and SACHS datasets. Relatively, KCRL has lower false discoveries in all experiments. This is important since false discoveries can have significant impact in healthcare domain. Overall, KCRL is ahead in performance w.r.t two out of the three metrics in all of the experiments that validate the effectiveness of our proposed framework. To summarize, our experimental findings show that existing causal discovery approaches that do not consider any prior knowledge lacks behind in performance compared to KCRL.
We propose a novel approach to causal discovery that utilizes prior knowledge as constraints structure search and penalizes the search process for violation of these constraints. This technique of penalizing for constraint violation guides and restricts the search process and improves the computational efficiency of the causal discovery. Essentially, it provides a novel systematic way to utilize prior knowledge during CD. Our approach can also address the data shortage problem suffered by most of the existing causal discovery approaches. It can be used in any domain that has some prior information available. Particularly, for healthcare domain where often some prior information such as clinical domain knowledge, findings from prior RCTs, evidence from medical literature and expert opinion are available, this approach will help in efficient causal discovery through a systematic inclusion of evidence. Also, whenever RCTs are infeasible, this approach can be used to develop a causal graph and consequently, perform virtual RCTs using observational data. The experimental results on multiple benchmark datasets and a clinical application show that penalizing the search process for constraint (prior knowledge) violation can improve the performance of the CD as well as enables faster convergence to the optimal structure. We evaluated our approach on datasets with both small (8 or 12 or 17 edges graphs) and large (62 edges graph) edge densities. We also compared our approach with multiple baselines and observed that it outperforms the baselines in different metrics across all four datasets. Moreover, our framework is modular and its major components such as the score function, acyclicity function and search process can be adopted from other existing approaches based on the underlying assumptions for different application domains.
Limitations The limitations of this work are as follows. We were unable to compare our approach with some of the existing prior knowledge based methods due to the unavailability of reproducible codes online. Additionally, a more robust approach is needed for the selection of an optimal value for the penalty weight β. This can be a future work to find an efficient way to compute the penalty weight. Another limitation is that when we increase the edge densities in experiments, KCRL seems to suffer in performance w.r.t. TPR compared to its performance for sparse graphs. We believe this can be addressed using other robust score function for dense graphs. However, many real-world applications usually have smaller networks with sparse graphs such as the SACHS (Sachs et al. (2005)), and CANCER (Korb and Nicholson (2010)) datasets. As a future work, we plan to test this framework for different amount of prior information and see how the performance varies. Also, this framework can be further evaluated by adopting the modular components from other existing implementations as a future work.