Causal Discovery with False Positive Error Control

Erik Jahn, Venkat Chandrasekaran, Frederick Eberhardt, Leonard SchulmanarXiv 2026 · arXiv

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:

  1. $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.
  2. 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.
  3. 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).
Figure 1: The ambiguous unshielded triples in the e-pattern to the left are marked with blue arcs. To the right are the 7 DAGs represented by the e-pattern.

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.
Figure 5: Experimental results showing that the m-conservative PC algorithm (mCPC) maintains lower False Discovery (FD) and FDR compared to baselines across various sample sizes.
  • 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.
Figure 6: Precision-Recall curves showing mCPC is competitive with baselines while providing better error control.

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

Abstract

Causal discovery methods produce data-driven hypotheses about causal relationships, which may become new scientific findings or inform decisions about downstream interventions. In such settings, false positive causal claims can be more consequential than false negatives. Yet few methods target false positive error control in causal discovery, and existing error guarantees are often asymptotic and require strong versions of the faithfulness assumption. We introduce the $m$-conservative PC algorithm and prove that it controls false discovery rate in the linear Gaussian setting under an extremely weak version of the faithfulness assumption. In our framework, false positive error for causal graphs is defined based on the conditional-independence information they entail, yielding a metric that penalizes both false adjacencies and incorrect edge orientations. The parameter $m$ quantifies a trade-off between algorithmic complexity and the strength of the required faithfulness assumption. The $m$-conservative PC algorithm combines undirected graph learning, a Benjamini-Yekutieli-style procedure for conditional independence testing, and a conservative orientation step that marks unresolved or contradictory edge directions as ambiguous. Our algorithm produces valid outputs and retains error guarantees even in the finite-sample setting, despite possible random errors in the conditional independence tests.
BibTeX
@misc{jahn2026causal,
  author = {Erik Jahn and Venkat Chandrasekaran and Frederick Eberhardt and Leonard Schulman},
  title = {{Causal Discovery with False Positive Error Control}},
  year = {2026},
  eprint = {2611.25376},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.25376},
}
Figure