PC Algorithm

The PC algorithm operates by testing conditional independence between every pair of variables, progressively conditioning on larger subsets of variables. It begins with a fully connected undirected graph and iteratively removes edges when a separating set is found that renders two variables conditionally independent.

• Skeleton identification: Removes edges between variables that are independent given any subset of other variables
• V-structure orientation: Orients colliders (X → Z ← Y) when two non-adjacent variables both cause a common effect
• Meek rules: Applies deterministic orientation rules to propagate directionality without creating cycles

The algorithm relies on the causal faithfulness assumption, which states that all conditional independencies observed in the data are entailed by the true causal graph structure, not by accidental parameter cancellations.

• Causal Markov condition: Each variable is independent of its non-descendants given its direct causes
• No accidental cancellations: The algorithm assumes positive and negative effects do not perfectly cancel each other out
• Violation example: If gene A upregulates protein B by +2 units and gene C downregulates B by -2 units, faithfulness is violated because A and C appear independent of B despite causal connections

The first phase constructs an undirected skeleton by testing independence between each pair of variables (X, Y) conditional on subsets of adjacent variables. The algorithm starts with conditioning set size 0 and increases incrementally.

• Adjacency search: For each pair, tests independence given all subsets of size k from the current adjacency set
• Separation sets (SepSet): Records the conditioning set that makes two variables independent
• Computational complexity: Worst-case exponential in the maximum degree of the graph, but efficient for sparse causal structures common in biomedicine
• Typical test: Partial correlation test for Gaussian data or G² test for discrete variables

After skeleton discovery, the algorithm identifies unshielded colliders (v-structures) where two non-adjacent parents share a common child. This is the only structural pattern that can be uniquely oriented from observational data alone.

• Collider rule: If X and Y are not adjacent but both are adjacent to Z, and Z is NOT in the separation set of X and Y, then orient X → Z ← Y
• Biological example: A genetic variant and an environmental factor may both independently cause a disease biomarker, forming a v-structure
• Critical for causal direction: V-structures provide the asymmetry needed to distinguish causation from mere correlation

The final output is a CPDAG (Completed Partially Directed Acyclic Graph) that represents the Markov equivalence class of all DAGs consistent with the observed independence patterns.

• Directed edges (→): Causally oriented with high confidence
• Undirected edges (—): Direction cannot be determined from observational data alone; multiple causal structures are equally consistent
• Equivalence class: All DAGs with the same skeleton and v-structures are observationally indistinguishable without interventional data
• Practical implication: In biomarker discovery, undirected edges indicate where follow-up perturbation experiments are needed

The PC algorithm is widely applied in molecular causal discovery to infer regulatory networks and identify potential drug targets from high-dimensional omics data.

• Gene regulatory networks: Reconstructs causal relationships between transcription factors and target genes from expression data
• Protein signaling cascades: Maps directional influence in phosphoproteomic time-course experiments
• Disease pathway reconstruction: Identifies upstream drivers versus downstream biomarkers in patient cohorts
• Integration with Mendelian randomization: PC algorithm can suggest candidate causal structures that are then validated using genetic instruments