Skip to yearly menu bar Skip to main content


Poster

An Efficient Maximal Ancestral Graph Listing Algorithm

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


Abstract:

Maximal ancestral graph (MAG) is a prevalent graphical model to characterize causal relations in the presence of latent variables including latent confounders and selection variables. Existing theoretical results have shown that only a Markov equivalence class (MEC) of MAGs is identifiable with observational data. Due to this fact, MAG listing, listing all the MAGs in the MEC, is usually demanded in many downstream tasks. However, there are no related methods for MAG listing other than brute force in the literature. Despite many efficient methods for graph listing under the assumption of no latent variables, they cannot cope with the challenges taken by the latent variables. In this paper, we propose the first brute-force-free MAG listing method by determining the local structure of each vertex recursively. We provide the graphical characterization for each valid local transformation, and present the sound and complete rules to incorporate the valid local transformation in the presence of latent confounders and selection variables. Based on these components, our method can efficiently output all the MAGs in the MEC with no redundance, that is, every intermediate graph in the recursive process is necessary for the MAG listing task. The empirical analysis demonstrates the superiority of our proposed method on efficiency and effectiveness.

Live content is unavailable. Log in and register to view live content