Towards Completeness in Causal Discovery from Soft Interventions with Known Targets

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.