Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules

A maximal ancestral graph (MAG) is widely used to characterize the causal relations among observable variables in the presence of latent variables. However, given observational data, only a partial ancestral graph representing a Markov equivalence class (MEC) of MAGs is identifiable, which generally contains uncertain causal relations. Due to the uncertainties, MAG listing, i.e., listing all the MAGs in the MEC, is critical for many downstream tasks. In this paper, we present the first polynomial-delay MAG listing method, where delay refers to the time for outputting each MAG, through introducing enumerated structural knowledge in the form of singleton background knowledge (BK). To incorporate such knowledge, we propose the sound and locally complete orientation rules. By recursively introducing singleton BK and applying the rules, our method can output all and only MAGs in the MEC with polynomial delay. Additionally, while the proposed novel rules enable more efficient MAG listing, for the goal of incorporating general BK, we present two counterexamples to imply that existing rules including ours, are not yet complete, which motivate two more rules. Experimental results validate the efficiency of the proposed MAG listing method.