PC algorithm

The PC algorithm (named for its creators, Peter Spirtes and Clark Glymour) is a constraint-based method for learning the structure of a causal graph from observational data. It operates in two phases: first, it tests conditional independencies among variables to identify which edges must exist and which cannot, producing an undirected skeleton; second, it orients edges by exploiting asymmetries in conditional independence patterns, leveraging the Faithfulness assumption that the data's independencies reflect the graph's structure rather than accidental parameter cancellations.

The algorithm's elegance is matched by its fragility. The number of conditional independence tests grows combinatorially with the number of variables, and each test requires a choice of conditioning set that determines whether an edge is retained or removed. In high-dimensional settings with limited samples, the tests become unreliable, and the algorithm's output becomes sensitive to the order in which tests are performed. Worse, the Faithfulness assumption fails near phase transitions, where long-range correlations create conditional independencies that do not correspond to missing edges. The PC algorithm assumes the world is sparse and locally coupled; when it is not, the algorithm hallucinates structure or misses it entirely.

Despite these limitations, the PC algorithm remains the foundational reference point for constraint-based causal discovery. Its successors — GES, FGES, MMPC — are refinements that improve computational efficiency and statistical power, but they inherit the same structural assumptions. The PC algorithm is not merely a technique; it is a statement about what kinds of causal structure are learnable from passive observation. The statement is powerful but bounded, and the boundaries are where the real science begins.

The PC algorithm promises to extract causal structure from raw data, but what it actually extracts is the shadow of its own assumptions. The graph it produces is a hypothesis about the world, dressed in the language of discovery.