Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules

Tian-Zuo Wang, Wen-Bo Du, Zhi-Hua Zhou
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:62804-62824, 2025.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-wang25y, title = {Polynomial-Delay {MAG} Listing with Novel Locally Complete Orientation Rules}, author = {Wang, Tian-Zuo and Du, Wen-Bo and Zhou, Zhi-Hua}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {62804--62824}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/wang25y/wang25y.pdf}, url = {https://proceedings.mlr.press/v267/wang25y.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules %A Tian-Zuo Wang %A Wen-Bo Du %A Zhi-Hua Zhou %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-wang25y %I PMLR %P 62804--62824 %U https://proceedings.mlr.press/v267/wang25y.html %V 267 %X 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.
APA
Wang, T., Du, W. & Zhou, Z.. (2025). Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:62804-62824 Available from https://proceedings.mlr.press/v267/wang25y.html.

Related Material