A fast PC algorithm for high dimensional causal discovery with multi-core PCs
Parallel-PC algorithm leverages multi-core processing to accelerate high-dimensional causal discovery, reducing runtime by 2-4x on gene expression datasets.
Key Findings
Methodology
This work introduces parallel-PC, a parallelized implementation of the stable-PC algorithm, designed to exploit multi-core CPUs. It divides conditional independence (CI) tests at each level into groups, distributing them across cores. After parallel execution, results are synchronized to update the adjacency sets, ensuring order-independence and stability. The core components include:β’ Task grouping of CI tests per level;β’ Parallel execution on multiple cores;β’ Synchronization and merging of results;β’ Compatibility with existing causal inference workflows. Extensive testing on synthetic and real gene expression datasets shows that parallel-PC achieves 2-4 times faster runtimes compared to the original PC algorithm, with maintained accuracy.
Key Results
- On the DREAM 5 challenge dataset (1643 variables, 805 samples), original PC failed to complete within 24 hours, while parallel-PC finished in about 12 hours on a 4-core CPU and under 6 hours on an 8-core CPU.
- Synthetic data experiments confirmed that parallel-PC maintains comparable causal structure accuracy, even with over 2000 variables, and exhibits higher stability and fewer false positives.
- Integration into miRNA-mRNA regulatory inference improved both speed and accuracy, demonstrating practical utility in biological data analysis.
Significance
This study addresses the critical bottleneck of computational cost in high-dimensional causal discovery. By harnessing multi-core hardware, it makes large-scale causal network inference feasible on standard personal computers. This democratizes access to advanced causal analysis, enabling biologists and data scientists to analyze massive datasets efficiently. The method enhances reliability and reproducibility of causal structures, fostering progress in genomics, systems biology, and beyond. It bridges the gap between theoretical algorithms and practical, scalable tools, paving the way for routine large-scale causal inference in scientific research.
Technical Contribution
The main technical innovation is the parallelization framework that combines task grouping, synchronization, and stability mechanisms. Unlike prior heuristic or order-dependent methods, this approach guarantees order-invariant results while significantly reducing runtime. It integrates the stable-PC concept with multi-core task scheduling, ensuring consistent adjacency sets across levels. The implementation is compatible with existing causal inference pipelines, providing a scalable, user-friendly solution for high-dimensional data. Theoretical guarantees include preserved correctness under perfect CI tests and stability under variable ordering.
Novelty
This is the first work to fully parallelize the PC algorithm, especially the stable-PC variant, on multi-core hardware. It uniquely combines order-independence with parallel execution, overcoming longstanding computational barriers. The approach differs from prior heuristic or partial parallelization efforts by ensuring result stability and reproducibility, making high-dimensional causal discovery practical on standard PCs. Its novelty lies in the seamless integration of parallel computing with causal structure learning, a significant step forward in scalable causal inference.
Limitations
- The method relies on accurate conditional independence testing; errors in CI tests due to limited samples can still affect results.
- Handling extremely high-dimensional data (e.g., >10,000 variables) may require further optimization or hardware support.
- Performance gains depend on available multi-core resources; limited cores reduce acceleration benefits.
Future Work
Future directions include extending the framework to nonlinear and time-series causal models, integrating GPU acceleration, and developing adaptive task scheduling for heterogeneous hardware. Additionally, exploring robust CI testing under small sample sizes and applying the approach to other causal models like FCI or PCMCI will broaden its applicability.
AI Executive Summary
Causal discovery from high-dimensional observational data is a fundamental challenge in modern science, especially in genomics and systems biology. Traditional algorithms like PC are theoretically sound but computationally prohibitive when faced with thousands of variables, often taking days or weeks to run. This bottleneck limits their practical utility, preventing timely insights into complex biological networks. To address this, we propose parallel-PC, a novel implementation that leverages multi-core CPU architectures to dramatically accelerate the process.
The core idea is to parallelize the conditional independence tests at each level of the PC algorithm, which are the main computational bottleneck. By grouping these tests and executing them simultaneously across multiple cores, the algorithm reduces runtime from days to hours without sacrificing accuracy or stability. Importantly, the approach maintains order-independence, ensuring reproducible results regardless of variable ordering. Extensive experiments on synthetic datasets and real gene expression data, including the DREAM 5 challenge, demonstrate that parallel-PC achieves 2-4 times faster performance while preserving the causal structure detection quality.
Beyond efficiency, the method enhances the accessibility of causal inference, enabling researchers with standard personal computers to analyze large-scale biological data. Its integration into miRNA-mRNA regulatory network inference showcases its practical impact, providing faster and more reliable insights into gene regulation mechanisms. Looking ahead, future work will focus on extending the framework to nonlinear and temporal models, further optimizing hardware utilization, and broadening its application scope. Overall, this work bridges the gap between theoretical causal discovery and real-world large-scale data analysis, opening new horizons for scientific discovery.
Deep Dive
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.