This paper, authored by researchers at Caltech, introduces a new approach to causal discovery that prioritizes a rigorous control of false positive errors. By relaxing the standard "faithfulness" assumptions and providing finite-sample guarantees, the authors offer a more reliable tool for scientific fields where a false causal claim is far more damaging than a missed one.
TL;DR
The authors present the $m$-conservative PC algorithm, a causal discovery method that provides provable False Discovery Rate (FDR) control in linear Gaussian settings. It achieves this by utilizing a new, weaker version of the faithfulness assumption and outputting "e-patterns" that explicitly mark ambiguous causal orientations rather than forcing potentially incorrect conclusions.
What Problem Does This Paper Address?
Causal discovery—the process of inferring cause-and-effect relationships from observational data—is notoriously difficult. Most classic algorithms, like the PC algorithm, rely on the faithfulness assumption: the idea that every statistical independence observed in the data corresponds to the absence of a causal link.
In practice, faithfulness is often violated. For example, two causal paths might "cancel each other out," making two variables appear independent even though one causes the other. When these assumptions fail, standard algorithms produce false positives—claiming a causal link exists when it doesn't, or misidentifying the direction of the cause. Furthermore, most existing error guarantees are "asymptotic," meaning they only hold true if you have an infinite amount of data. This paper addresses the need for reliable error control in real-world, finite-sample scenarios.
Methods
The core contribution is the $m$-conservative PC algorithm. It differs from standard approaches in three key ways:
- $m$-connected-collider faithfulness: The authors introduce a new family of increasingly weak faithfulness conditions. The parameter $m$ acts as a "knob": as $m$ increases, the assumption becomes weaker (more realistic), but the computational complexity grows.
- FDR Control via Benjamini-Yekutieli: Instead of testing every possible conditional independence, the algorithm uses an undirected graph learning step to narrow the search. It then applies a modified Benjamini-Yekutieli procedure to control the False Discovery Rate across multiple hypothesis tests, even when those tests are dependent.
- Conservative Orientation (e-patterns): Rather than outputting a single graph, the algorithm produces an e-pattern. If the data suggests conflicting or unresolved edge directions, the algorithm marks them as "ambiguous" (represented by blue arcs in the figures).
Datasets
The authors evaluated their algorithm using both synthetic and real-world data:
- Synthetic Linear Gaussian SEMs: Specifically designed to include faithfulness violations (near-zero coefficients that cancel out) to test the limits of standard algorithms.
- Causal Chamber: A real-world physical dataset from a light tunnel system with 11 variables and a known ground-truth causal structure.
Key Insights and Ideas
- Ambiguity as a Feature: The algorithm’s willingness to say "I don't know" is its greatest strength. By marking triples as ambiguous, it avoids the orientation errors that plague standard PC and Greedy Equivalence Search (GES) methods.
- The Complexity Trade-off: The parameter $m$ quantifies the trade-off between how much you trust the faithfulness assumption and how much compute you are willing to spend. A higher $m$ handles more complex faithfulness violations but increases runtime exponentially.
- Finite-Sample Reliability: Unlike many theoretical proofs in this field, the authors prove that their FDR control holds in finite-sample settings, making it much more applicable to actual experimental data.
Key Results
- Theoretical Guarantee: The authors prove (Theorem 1) that the expected FDR of their algorithm is bounded by $(\Delta + 1)\alpha + p$, where $\Delta$ is the maximum degree of the graph, $\alpha$ is the significance level, and $p$ is the failure probability of the initial undirected graph learning.
- Empirical Performance: In simulations involving faithfulness violations, the $m$-conservative PC algorithm maintained a False Discovery Rate near zero, while baseline algorithms (PC, CPC, and GES) saw their error rates spike as sample sizes increased.
- Precision-Recall: The algorithm remains competitive in terms of Area Under the Curve (AUC) compared to standard methods but provides much more reliable precision in the high-recall regime.
Limitations and Future Work
- Computational Scalability: The orientation step scales exponentially with the number of ambiguities. For very dense or high-dimensional graphs with many faithfulness violations, the algorithm can become computationally intractable (timing out after 300s in some tests).
- Linear Gaussian Assumption: The current proof of FDR control relies on the linear Gaussian setting. While the authors suggest the combinatorial orientation step could be generalized, the link between faithfulness and the undirected graph currently depends on this specific model class.
- Informative vs. Unique: Because the algorithm is conservative, the output e-patterns can sometimes be very ambiguous. The authors suggest this is a "starting point" for experimental design, where targeted interventions could then be used to resolve the remaining ambiguities.
Summary updated