The Challenge of Unknown Causal Structures
In classical causal inference, researchers typically assume they have access to a perfectly specified causal diagram, known as a Directed Acyclic Graph (DAG). However, in real-world scenarios, the exact "true" graph is rarely known. Instead, observational data often points to multiple different graphs that are equally consistent with the data—a phenomenon known as Markov equivalence.
To handle this uncertainty, researchers use Partial Ancestral Graphs (PAGs) to represent these Markov equivalence classes, which can be learned directly from data.
While recent algorithmic advances have made it possible to identify unconditional causal effects (e.g., $P_x(y)$) across these equivalence classes, they have historically struggled with conditional effects (e.g., $P_x(y|z)$). The standard mathematical "trick" of identifying the joint distribution $P_x(y, z)$ and dividing it by the marginal distribution often fails in these uncertain graphs. There are many cases where the joint distribution is unidentifiable due to structural uncertainty, yet the conditional effect remains perfectly computable.
This paper bridges that gap, introducing a novel algorithm to evaluate conditional policies—such as "Treat the patient if their blood pressure is high"—even when the underlying causal model is uncertain.
Introducing the CIDP Algorithm
To solve this, the authors develop the CIDP (Conditional Identification in PAGs) algorithm. Its core logic relies on three main technical contributions that allow it to navigate the structural uncertainty inherent in a PAG:
- Novel Decomposition: The authors establish a recursive routine called
DECOMPOSE. This routine breaks down a complex conditional query $Q[T|Z]$ into smaller, more manageable components, isolating the identifiable parts of the causal query. - The "DO-SEE" Trick: Based on a new graphical criterion, the algorithm identifies when a variable can be safely moved from the "intervention set" (variables we actively change or "do") to the "conditioning set" (variables we merely observe or "see") without invalidating the causal estimate.
- Integration with IDP: CIDP builds upon and subsumes the previous state-of-the-art algorithm for unconditional effects (IDP). It leverages the structural invariants of a PAG—features that hold true across all possible graphs in the equivalence class—to ensure the final causal expression is valid regardless of which specific graph is the true data-generating model.
Key Insights and Results
The most significant insight from this work is proving that $P_x(y|z)$ can be identifiable even when the joint distribution $P_x(y, z)$ is not. This occurs because the specific uncertainties in the graph that obscure the joint distribution often "cancel out" or become irrelevant once we condition on $Z$. By analyzing how "buckets" (sets of nodes connected by uncertain circle edges) and "pc-components" (possible confounded components) interact, CIDP successfully navigates this uncertainty.
The authors provide a formal proof of soundness for CIDP: if the algorithm returns an expression for a causal effect, that expression is guaranteed to be correct for every graph in the Markov equivalence class. Furthermore, they prove subsumption, meaning CIDP is strictly more powerful than previous methods. If the older IDP algorithm could find an answer, CIDP will too; but CIDP also succeeds in many complex conditional scenarios where IDP fails (as illustrated in the example graph above).
Limitations and Future Directions
While CIDP represents a major theoretical leap for graphical models and causal identification, a few hurdles remain:
- Completeness Proof: The authors conjecture that CIDP is "complete" (meaning if a conditional effect is theoretically identifiable from a PAG, CIDP will find it). While it handles all known edge cases, a formal mathematical proof of completeness is left for future work.
- Computational Complexity: The paper focuses on algorithmic soundness rather than runtime efficiency. Future analyses will need to evaluate its computational complexity on very large, highly uncertain graphs.
- From Identification to Estimation: This paper solves the identification problem (deriving the correct mathematical formula). The natural next step for practitioners is estimation—developing robust statistical estimators to calculate these formulas accurately from finite, noisy real-world datasets.
Summary updated