Towards Completeness in Causal Discovery from Soft Interventions with Known Targets

Zihan Zhou, Murat KocaogluICML 2026 · OpenReview

Introduction

Causal discovery—the process of determining "what causes what" from observational and interventional data—is notoriously difficult when unobserved variables, or latent confounders, are present. These hidden variables can influence multiple observed factors, creating "mirage" correlations that confuse standard algorithms. While interventions (such as randomized trials) help clarify these relationships, "soft" interventions—which merely perturb a variable's distribution rather than fixing it to a constant value—introduce additional complexity.

This paper identifies a critical "completeness gap" in how current algorithms learn causal structures from soft interventions with known targets. To address this, the authors introduce two novel methods: FAST, a set of efficient local orientation rules, and LIST, a theoretically complete enumeration method, designed to extract maximum causal information from interventional data.

The Completeness Gap in Current Algorithms

The current state-of-the-art algorithm for causal discovery under soft interventions with latent confounders is $\mathcal{I}$-FCI. While $\mathcal{I}$-FCI is sound (it does not make incorrect causal claims), it is incomplete. It often leaves many relationships as "ambiguous" (represented by circle endpoints in causal graphs) even when the underlying data contains enough information to resolve them.

$\mathcal{I}$-FCI treats intervention nodes similarly to generic background knowledge, failing to fully exploit their unique properties. The authors set out to close this gap, moving the field closer to a complete understanding of what can be identified from soft interventional data.

Methodology: FAST and LIST

The authors build on the framework of Augmented Maximal Ancestral Graphs ($\mathcal{I}$-MAGs), where interventions are represented as special "indicator nodes" ($F$-nodes) that point directly to their targets. To improve upon $\mathcal{I}$-FCI, they propose two distinct approaches:

1. FAST (Local Orientation Rules)

The FAST approach introduces three new orientation rules (Rules 9, 10, and 11) that exploit the specific semantics of $F$-nodes. The core logic relies on the "Transit Node" concept: because we know exactly which nodes were targeted by an intervention, any adjacency between an intervention node and a non-target node provides a massive hint about the ancestral path between them. If an intervention influences a non-target, that influence must have traveled through one of its known targets. By formalizing this logic, FAST can orient edges that $\mathcal{I}$-FCI would leave ambiguous, all without increasing the algorithm's asymptotic computational complexity.

2. LIST (Enumeration-based Completion)

For scenarios demanding maximum information extraction, the authors developed LIST, an enumeration procedure. LIST generates all possible graphs consistent with the partial graph learned by $\mathcal{I}$-FCI and uses a novel "realizability oracle" to filter out configurations that violate interventional logic. While this method is theoretically complete, its worst-case computational cost depends heavily on the number of compatible graphs.

Key Insights

  • Completeness is a Global Property: The authors demonstrate that while local rules like FAST are highly efficient, they cannot resolve every ambiguity. Some causal directions are only "compelled" because any alternative configuration would create a forbidden inducing path elsewhere in the global graph.
  • The Soundness-Completeness Tradeoff: By acknowledging the unique "source" nature of interventions rather than treating them as standard variables, algorithms can significantly tighten causal estimates and reduce ambiguity.

Experimental Results

The researchers evaluated FAST and LIST using both synthetic Acyclic Directed Mixed Graphs (ADMGs) and the classic Sachs dataset (protein-signaling measurements under chemical perturbations).

  • Better Accuracy, Same Speed: In small-scale simulations ($n=5$), FAST consistently improved the recovery of edge marks (measured by End-F1 score) and reduced the Structural Hamming Distance compared to the $\mathcal{I}$-FCI baseline, with virtually no added runtime.
  • Scaling to Large Graphs: On 100-node synthetic graphs, FAST remained as efficient as the baseline while still providing a modest improvement in edge orientation.
  • The Power and Cost of LIST: The LIST method achieved the best orientation recovery in small-scale tests, confirming its theoretical completeness. However, it timed out on the 100-node graphs, highlighting its computational intensity.
  • Real-World Validation: On the Sachs dataset, both FAST and LIST slightly improved the match against the literature-derived reference graph compared to the standard $\mathcal{I}$-FCI algorithm.

Limitations and Future Directions

The primary limitation of this work is the computational cost of the LIST method, which becomes prohibitive as the number of possible graph completions grows super-exponentially.

To advance this framework, the authors suggest several future directions:

  • Hard Interventions: Extending these rules to "hard" interventions, which sever incoming edges and change the graph structure differently than soft interventions.
  • Unknown Targets: Adapting the transit logic for cases where an intervention is known to have occurred, but its exact targets are uncertain.
  • Efficient Completeness: Designing an algorithm that achieves theoretical completeness while remaining computationally efficient, bypassing the need for full graph enumeration.

Summary updated

Abstract

We study causal discovery from soft interventions in the presence of latent confounding. Beyond within-environment conditional independences, soft interventions induce cross-environment invariances that can be encoded using an augmented graph with intervention indicator nodes ($\mathcal{I}$-AUG). Taking its maximal ancestral graph (MAG) yields the $\mathcal{I}$-MAG, which characterizes the interventional Markov equivalence class. Building on this framework, we show that the FCI-inspired learner ($\mathcal{I}$-FCI) by Kocaoglu et al. (2019) is sound but not complete: it may output circle endpoints that are nevertheless compelled by the interventional equivalence class. To exploit intervention-node semantics, we propose two complementary methods. First, we introduce an enumeration-based completion procedure that is sound and theoretically complete, but whose worst-case cost depends on the number of MAGs compatible with the partial graph learned by $\mathcal{I}$-FCI. Second, we derive a set of additional local orientation rules that provably tighten $\mathcal{I}$-FCI without increasing asymptotic complexity. Both methods refine prior outputs in the controlled soft-intervention setting with latent variables.
BibTeX
@inproceedings{zhou2026towards,
  author = {Zihan Zhou and Murat Kocaoglu},
  title = {{Towards Completeness in Causal Discovery from Soft Interventions with Known Targets}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=dVfJSLGTYm},
}
Figure