A fast PC algorithm for high dimensional causal discovery with multi-core PCs

Abstract

Discovering causal relationships from observational data is a crucial problem and it has applications in many research areas. The PC algorithm is the state-of-the-art constraint based method for causal discovery. However, runtime of the PC algorithm, in the worst-case, is exponential to the number of nodes (variables), and thus it is inefficient when being applied to high dimensional data, e.g. gene expression datasets. On another note, the advancement of computer hardware in the last decade has resulted in the widespread availability of multi-core personal computers. There is a significant motivation for designing a parallelised PC algorithm that is suitable for personal computers and does not require end users' parallel computing knowledge beyond their competency in using the PC algorithm. In this paper, we develop parallel-PC, a fast and memory efficient PC algorithm using the parallel computing technique. We apply our method to a range of synthetic and real-world high dimensional datasets. Experimental results on a dataset from the DREAM 5 challenge show that the original PC algorithm could not produce any results after running more than 24 hours; meanwhile, our parallel-PC algorithm managed to finish within around 12 hours with a 4-core CPU computer, and less than 6 hours with a 8-core CPU computer. Furthermore, we integrate parallel-PC into a causal inference method for inferring miRNA-mRNA regulatory relationships. The experimental results show that parallel-PC helps improve both the efficiency and accuracy of the causal inference algorithm.

Thuc Le, Tao Hoang, Jiuyong Li, Lin Liu, Huawen Liu, Shu Hu, "A fast PC algorithm for high dimensional causal discovery with multi-core PCs", IEEE/ACM Transactions on Computational Biology and Bioinformatics, doi:10.1109/TCBB.2016.2591526

References in corpus (6)

• Estimating high-dimensional intervention effects from observational data
• A Discovery Algorithm for Directed Cyclic Graphs
• Adjacency-Faithfulness and Conservative Causal Inference
• Bayesian Network Constraint-Based Structure Learning Algorithms: Parallel and Optimised Implementations in the bnlearn R Package
• From Observational Studies to Causal Rule Mining
• A Parallel Algorithm for Exact Bayesian Structure Discovery in Bayesian Networks

Cited by in corpus (18)

• Detecting crosstalk errors in quantum information processors
• Causal Confusion in Imitation Learning
• A Survey on Causal Discovery: Theory and Practice
• cuPC: CUDA-based Parallel PC Algorithm for Causal Structure Learning on GPU
• gCastle: A Python Toolbox for Causal Discovery
• Higher-order interactions in statistical physics and machine learning: A model-independent solution to the inverse problem at equilibrium
• A Review on Algorithms for Constraint-based Causal Discovery
• Learning for Counterfactual Fairness from Observational Data
• ParaLiNGAM: Parallel Causal Structure Learning for Linear non-Gaussian Acyclic Models
• Causal Inference with Latent Variables: Recent Advances and Future Prospectives
• ParallelPC: an R package for efficient constraint based causal exploration
• Fast Parallel Bayesian Network Structure Learning
• A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy
• Causal Inference in medicine and in health policy, a summary
• Symmetric observations without symmetric causal explanations
• Data-driven discovery of interpretable causal relations for deep learning material laws with uncertainty propagation
• polyDAG: Polynomial Acyclicity Constraints for Efficient Continuous Causal Discovery in Visual Semantic Graphs
• Learning linear acyclic causal model including Gaussian noise using ancestral relationships