Abstract: The problem of finding an ancestral acyclic directed mixed graph (ADMG) that
represents the causal relationships between a set of variables is an important
area of research for causal inference. However, most of existing score-based
structure learning methods focus on learning the directed acyclic graph (DAG)
without latent variables. A number of score-based methods have recently been
proposed for the ADMG learning, yet they are heuristic in nature and do not
guarantee an optimal solution. We propose a novel exact score-based method that
solves an integer programming (IP) formulation and returns a score-maximizing
ancestral ADMG for a set of continuous variables. In particular, we generalize
the state-of-the-art IP model for DAG learning problems and derive new classes
of valid inequalities to formalize the IP-based ADMG learning model.
Empirically our model can be solved efficiently for medium-sized problems and
achieves better accuracy than state-of-the-art score-based methods as well as
benchmark constraint-based methods.