Module pc_algorithm 

PC Algorithm for Causal Discovery

The Peter-Clark (PC) algorithm is a constraint-based method that learns the Markov equivalence class of a DAG from observational data, represented as a Completed Partially Directed Acyclic Graph (CPDAG).

Phases

1. Skeleton discovery (PC-stable variant): start with a fully connected undirected graph and iteratively remove edges when a conditional independence is found, recording separation sets.

2. V-structure orientation: for each triple X - Z - Y where X and Y are not adjacent, orient X -> Z <- Y if Z is not in sep(X, Y).

3. Meek’s rules (R1-R4): propagate orientations to avoid new v-structures and cycles.

PC-stable variant

In the standard PC algorithm, edge removals during skeleton discovery can depend on the order in which edges are tested. The PC-stable variant (Colombo & Maathuis, 2014) fixes this by computing all removals at each conditioning-set size before applying them.

References

• Spirtes, P., Glymour, C. & Scheines, R. (2000). Causation, Prediction, and Search (2nd ed.). MIT Press.
• Colombo, D. & Maathuis, M.H. (2014). Order-independent constraint-based causal structure learning. JMLR 15, 3741-3782.
• Meek, C. (1995). Causal inference and causal explanation with background knowledge. UAI 1995, pp. 403-410.

Structs

PcAlgorithm

Configuration for the PC algorithm.

PcResult

Result of the PC algorithm.

Functions

apply_meek_rules

Apply Meek’s orientation rules R1-R4 until no more orientations change.