PEPC: Parallel and Extensible PC Implementation for Causal Structure Learning

Learning the causal relationships among variables from observational data has been a significant problem in statistics and data mining, and one such algorithm is the PC algorithm. However, the existing CPU-based implementations are difficult to support Causal Structure Learning(CSL) on complex observational data due to inefficiency. In this paper, we propose an efficient CPU-based parallel implementation of the PC algorithm, called PEPC. It has an extensible framework, and some optimizations are adopted to reduce the CSL computation of the PC algorithm. Moreover, our PEPC supports efficient multi-thread parallelism. The experimental results demonstrate that PEPC outperforms existing methods in serial efficiency and multi-thread parallelism. In serial tests, our method achieves the maximum speedup ratios of 577.26, 116.74, and 134.68 over three existing approaches, Stable, Stable.fast, and Tetrad. In parallel experiments, it achieves 10.66X speedup when running the PC algorithm with 12 threads.

• Publication year

  2023

• Venue

  HP3C

• Publication date

  2023-06-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/3606043.3606054
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• GPU-Accelerated Constraint-Based Causal Structure Learning for Discrete Data

  2021cited by this paper
• Order-independent constraint-based causal structure learning for gaussian distribution models using GPUs

  2018cited by this paper
• cuPC: CUDA-Based Parallel PC Algorithm for Causal Structure Learning on GPU

  2018cited by this paper
• TETRAD - A TOOLBOX FOR CAUSAL DISCOVERY

  2018cited by this paper
• Causal discovery algorithms: A practical guide

  2018cited by this paper
• From miRNA regulation to miRNA-TF co-regulation: computational approaches and challenges

  2015cited by this paper
• A Fast PC Algorithm for High Dimensional Causal Discovery with Multi-Core PCs

  2015cited by this paper
• Order-independent constraint-based causal structure learning

  2012cited by this paper
• Wisdom of crowds for robust gene network inference

  2012cited by this paper
• Causal Inference Using Graphical Models with the R Package pcalg

  2012cited by this paper
• Matrix Computations

  2011cited by this paper
• Predicting causal effects in large-scale systems from observational data

  2010cited by this paper
• Learning Bayesian Networks with the bnlearn R Package

  2009cited by this paper
• Causation, Prediction, and Search

  2003influential reference
• Using Bayesian Networks to Analyze Expression Data

  2000cited by this paper
• A Discovery Algorithm for Directed Cyclic Graphs

  1996cited by this paper
• Causal inference and causal explanation with background knowledge

  1995cited by this paper
• Learning Bayesian Networks is

  1994cited by this paper
• Probabilistic reasoning in intelligent systems: Networks of plausible inference

  1991cited by this paper
• An Algorithm for Fast Recovery of Sparse Causal Graphs

  1991cited by this paper
• The QR Transformation - Part 2

  1962cited by this paper

• A Fast Algorithm for High-Dimensional Causal Discovery

  2025cites this paper