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