Source-linked AI summary
A fast PC algorithm for high dimensional causal discovery with multi-core PCs
Thuc Duy Le, Tao Hoang, Jiuyong Li, Lin Liu, Huawen Liu
TL;DR
Causal discovery from observational data is important, but PC-based methods can be too slow for high-dimensional datasets and difficult for ordinary users to parallelize. The paper develops parallel-PC by distributing conditional-independence tests across personal-computer cores. On DREAM5, stable-PC exceeded 24 hours without results, while parallel-PC finished in around 12 hours on four cores and under 6 hours on eight cores, and its integration improved causal-inference efficiency and accuracy.
Problem
High-dimensional causal discovery is limited by PC's exponential worst-case runtime, while randomized experiments can be costly or infeasible.
Method
Parallel-PC distributes PC conditional-independence tests across CPU cores and integrates results at each algorithmic level.
Results
Parallel-PC finished the DREAM5 dataset in around 12 hours with 4 cores and less than 6 hours with 8 cores, whereas stable-PC exceeded 24 hours without producing results.
Takeaways & Limitations
Replacing original PC with parallel-PC improved both efficiency and accuracy in a causal-inference method for miRNA–mRNA regulatory relationships.
Takeaways & Limitations
Using the memory-efficient option involves a time–memory trade-off, and running S. cervisiae without it failed from memory exhaustion on an 8GB machine.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Causal discovery from observational data is important because experiments can be costly or infeasible, but high-dimensional PC-based discovery is computationally demanding and order-dependent. The paper introduces parallel-PC, which parallelizes conditional-independence tests on multi-core personal computers and improves practicality while preserving order-independent results.
- Observational data can support causal discovery when randomized experiments are prohibitively costly or ethically restricted.Gene knockdown experiments may require testing thousands of genes and are often impractical.
- The PC algorithm is a reliable constraint-based method that learns a skeleton by removing edges using conditional-independence decisions, then orients remaining edges.Its worst-case runtime is exponential in the number of nodes, limiting applications to high-dimensional gene-expression data.
- High-dimensional PC results can depend on variable ordering, with around 40% of edges in one real gene-expression analysis appearing in fewer than half of orderings.This instability makes knowledge inferred from the algorithm less reliable.
- Stable-PC addresses order dependence by fixing neighbors at each conditioning-set level, but its additional conditional-independence tests further increase runtime.On a DREAM5 dataset with 1643 variables and 805 samples, the order-independent version ran for more than 24 hours without finishing.
- Parallel-PC distributes conditional-independence tests across computer cores, integrates results level by level, and requires no additional user expertise or installation effort.The paper evaluates the method on synthetic and real-world datasets and applies it to miRNA–mRNA regulatory inference.
2 RELATED WORK
Related work improves causal-discovery efficiency through alternative tests, local structure learning, heuristics, and parallel methods for related algorithms. The paper positions its contribution as the first parallelization of the PC algorithm itself.
- Constraint-based causal discovery uses conditional-independence tests to remove non-causal relationships and is suitable for sparse datasets.
- Some PC modifications reduce tests or replace chi-square tests with Bayesian tests, trading computational cost or uncertain real-world efficiency gains for potential error reduction.
- Heuristic alternatives improve efficiency by targeting specific structures or local relationships, but may produce incomplete results or high false-discovery rates.
- Local causal-discovery methods focus on a target and its neighbors, including Markov-blanket approaches based on parents, children, and spouses.
- Earlier parallel methods addressed local causal discovery or Bayesian-network structure learning, whereas no existing work had parallelized the PC algorithm.
3 THE ORIGINAL-PC AND STABLE-PC ALGO-
The original-PC algorithm learns a skeleton through conditional independence tests and then orients edges, but dynamic graph updates make results variable-order dependent. Stable-PC fixes adjacency sets within each level to remove this dependence, at the cost of additional tests and runtime.
- Original-PC algorithm: The PC algorithm starts with a fully connected graph and removes edges when conditioning sets render adjacent variables independent.It organizes conditional independence tests by conditioning-set size and records separating sets when edges are removed.
- Original-PC algorithm: Under faithfulness and perfect conditional-independence information, PC returns the CPDAG representing the underlying DAG.The result relies on the stated causal Markov, faithfulness, and causal-sufficiency assumptions.
- Order dependence: Dynamic adjacency updates can make the output graph depend on the order of conditional-independence tests and input variables.Removing one edge changes later conditioning sets, so different testing orders may produce different graphs.
- Stable-PC algorithm: Stable-PC keeps every node’s adjacency set fixed during a level, making edge deletions at that level independent of variable ordering.The method queries and fixes adjacency sets before conducting the level’s tests.
- Stable-PC algorithm: Stable-PC requires more conditional-independence tests per level, increasing the algorithm’s runtime.The paper adopts stable-PC as the order-independent basis for its efficiency-focused modification.
4 PARALLEL-PC ALGORITHM
Parallel-PC parallelizes conditional-independence tests within each stable-PC level, where tests are independent because the graph is updated only after the level. It distributes work across cores while supporting batching and an optional memory-efficient mode.
- Parallelization challenge: The stable-PC bottleneck is the potentially huge number of conditional-independence tests, while dependencies across levels prevent straightforward whole-algorithm parallelization.A level’s completed tests update adjacency sets before the next level begins.
- Parallel-PC strategy: Parallel-PC executes conditional-independence tests inside each stable-PC level rather than across levels.Tests at one level are independent because the graph changes only after all tests at that level finish.
- Parallel-PC strategy: Each level uses three stages: evenly distribute tests across cores, run them in parallel, and integrate the results into the global graph.The design also permits the number of tests at each level to be known in advance for balanced distribution.
- Work distribution: Tests for the same edge are grouped together because removing that edge can make the other side’s tests unnecessary.This grouping preserves the dependency among tests associated with one edge.
- Memory management: The optional memory-efficient mode estimates available memory and distributes edges in batches, trading some additional time for lower per-core memory use.The algorithm otherwise distributes batches across P cores and can process the full edge set when memory efficiency is disabled.
5 EXPERIMENTAL EVALUATION AND APPLICA-
Experiments on five real-world and one synthetic gene-expression dataset evaluated parallel-PC against stable-PC, showing shorter runtimes, scalability with dataset size, and a memory-saving option with a time trade-off.
- Datasets: Five real-world and one synthetic gene-expression dataset were used to evaluate parallel-PC against stable-PC.The datasets covered miRNA–gene and transcription-factor–gene regulatory relationships.
- Experimental setup: Three repeated runs were averaged for each experiment.The evaluations used 4–8 CPU cores and reported average runtimes.
- Efficiency evaluations: Parallel-PC was much faster than stable-PC while producing order-independent results consistent with stable-PC.On DREAM5-Insilico, stable-PC produced no result after more than 24 hours, whereas parallel-PC finished in around 12 hours with four cores and under 6 hours with eight cores.
- Efficiency evaluations: Increasing cores reduced runtime for larger datasets, but synchronization limited gains on smaller datasets.For S. aureus, runtime fell from around eight hours with stable-PC to around two hours with four-core parallel-PC and 76.1 minutes with eight cores.
- Scalability: Runtime increased with both variables and samples, but parallel-PC scaled less sharply with variable count than stable-PC.More variables increased the number of conditional-independence tests, while more samples increased the time per test.
- Memory efficiency: The memory-efficient option reduced peak memory usage to about half, but traded memory savings for longer runtime.Running S. cerevisiae without the option failed because of memory exhaustion.
6 APPLICATION IN INFERRING MIRNA-MRNA
The paper integrates parallel-PC into IDA as efficient-IDA to infer miRNA–mRNA regulatory relationships, addressing IDA’s computational and order-dependence problems. Across three cancer datasets, efficient-IDA identified more experimentally confirmed targets than IDA.
- Efficient-IDA method: Efficient-IDA replaces IDA’s initial PC step with parallel-PC to address computational complexity and order dependence.The pipeline then estimates miRNA effects on mRNAs using do-calculus.
- Experimental evaluation: Efficient-IDA was evaluated against IDA on the NCI-60, MCC, and BR51 datasets using experimentally confirmed miRNA targets.Validation used a combination of four experimentally confirmed target databases.
- Experimental evaluation: The evaluation extracted either the top 100 predicted targets per miRNA or ranked sets of predicted interactions for validation.The ranked-interaction evaluation used the top 1000, 2000, 5000, and 10000 predictions from each method.
- Results: Efficient-IDA discovered more confirmed miRNA targets than IDA under both validation procedures across all evaluated datasets.The results suggest that efficient-IDA’s order-independent property improves IDA’s causal-inference accuracy while retaining faster runtime.
7 CONCLUSIONS AND FUTURE WORK
The paper presents parallel-PC as a more efficient parallel implementation of stable-PC for causal discovery in high-dimensional datasets. It reports improved efficiency and accuracy in miRNA–mRNA inference, while identifying job scheduling as a remaining opportunity for improvement.
- Conclusions: Parallel-PC groups conditional-independence tests and executes them in parallel, producing stable-PC-consistent causal relationships with shorter runtime.The method was evaluated on a wide range of commonly used real-world datasets.
- Conclusions: Parallel-PC improved both the efficiency and accuracy of IDA for inferring miRNA–mRNA regulatory relationships.This application demonstrates usefulness beyond the core causal-discovery algorithm.
- Future work: The current implementation divides conditional-independence tests equally across CPU cores without guaranteeing equal execution times.Uneven core workloads can leave some cores running longer than others.
- Future work: A job-weighting and scheduling scheme could further speed up parallel-PC.The paper identifies this as a direct improvement to the current workload-distribution strategy.
- Future work: Future work includes applying parallel-PC to other PC-related causal-discovery and causal-inference methods, including FCI, RFCI, and CCD.These methods use the PC algorithm directly or indirectly.