A fast score-based search algorithm for maximal ancestral graphs using entropy
This work provides a more efficient and stable method for causal discovery in the presence of latent confounders, which is incremental as it builds on existing frameworks like imsets and refined Markov properties.
The authors tackled the problem of learning maximal ancestral graphs (MAGs) from data by addressing the instability and computational issues of existing BIC score-based methods, resulting in a polynomial-time algorithm that outperforms state-of-the-art alternatives in simulations.
\emph{Maximal ancestral graph} (MAGs) is a class of graphical model that extend the famous \emph{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 \citep{studeny2006probabilistic} to score MAGs using empirical entropy estimation and the newly proposed \emph{refined Markov property} \citep{hu2023towards}. Our graphical search procedure is similar to \citet{claassen2022greedy} 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.