Integer Programming Based Methods and Heuristics for Causal Graph Learning

Acyclic directed mixed graphs (ADMG) - graphs that contain both directed and bidirected edges but no directed cycles - are used to model causal and conditional independence relationships between a set of random variables in the presence of latent or unmeasured variables. Bow-free ADMGs, Arid ADMGs, and Ancestral ADMGs (AADMG) are three widely studied classes of ADMGs where each class is contained in the previously mentioned class. There are a number of published methods - primarily heuristic ones - to find score-maximizing AADMGs from data. Bow-free and Arid ADMGs can model certain equality restrictions - such as Verma constraints - between observed variables that maximal AADMGs cannot. In this work, we develop the first exact methods - based on integer programming - to find score-maximizing Bow-free and Arid ADMGs. Our methods work for data that follows a continuous Gaussian distribution and for scores that linearly decompose into the sum of scores of c-components of an ADMG. To improve scaling, we develop an effective linear-programming based heuristic that yields solutions with high parent set sizes and/or large districts. We show that our proposed algorithms obtain better scores than other state-of-the-art methods and return graphs that have excellent fits to data.