A fast score-based search algorithm for maximal ancestral graphs using entropy

Maximal ancestral graph (MAGs) is a class of graphical model that extend the famous directed acyclic graph in the presence of latent confounders. Most score-based approaches to learn the unknown MAG from empirical data rely on BIC score which suffers from instability and heavy computations. We propose to use the framework of imsets citepstudeny2006probabilistic to score MAGs using empirical entropy estimation and the newly proposed refined Markov property citephu2023towards. Our graphical search procedure is similar to citetclaassen2022greedy but improved from our theoretical results. We show that our search algorithm is polynomial in number of nodes by restricting degree, maximal head size and number of discriminating paths. In simulated experiment, our algorithm shows superior performance compared to other state of art MAG learning algorithms.