Skip to yearly menu bar Skip to main content


Spotlight Poster

An Efficient Maximal Ancestral Graph Listing Algorithm

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

Hall C 4-9 #2008
[ ] [ Paper PDF ]
[ Poster
Tue 23 Jul 4:30 a.m. PDT — 6 a.m. PDT

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. Given observational data, only a Markov equivalence class (MEC) of MAGs is identifiable if without some additional assumptions. Due to this fact, MAG listing, listing all the MAGs in the MEC, is usually demanded in many downstream tasks. To the best of our knowledge, there are no relevant methods for MAG listing other than brute force in the literature. In this paper, we propose the first brute-force-free MAG listing method, by determining the local structures of each vertex recursively. We provide the graphical characterization for each valid local transformation of a vertex, and present 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.

Chat is not available.