Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules

Tian-Zuo Wang, Wen-Bo Du, Zhi-Hua Zhou

International Conference on Machine Learning 2025 · Oral

This talk, presented by Tian-Zuo Wang from Nanjing University, delves into a critical challenge within **causal inference**: efficiently identifying all possible causal structures consistent with observational data when latent variables are present. Specifically, the research focuses on the problem of **Maximal Ancestral Graph (MAG) listing**. In scenarios where unobserved confounders or selection variables complicate direct causal discovery, **MAGs** serve as powerful graphical models to represent causal relationships among observed variables. However, from observational data alone, one can typically only identify a **Partial Ancestral Graph (PAG)**, which encapsulates a Markov equivalence class of MAGs, leaving certain causal directions ambiguous. The core task addressed in this work is to systematically enumerate all MAGs that are consistent with a given PAG.

AI review

Wang et al. present the first polynomial-delay algorithm for listing all MAGs consistent with a given PAG, a long-standing computational problem in causal inference under latent confounding. The central contribution is a set of three novel orientation rules proved to be sound and locally complete for singleton background knowledge — a precise and non-trivial property that directly unlocks the delay improvement. The theoretical guarantee is real, the problem is well-motivated, and the result closes a gap the community has known about since the recursive enumeration strategy was introduced…