Integer Programming Based Methods and Heuristics for Causal Graph Learning

Acyclic directed mixed graphs (ADMG) – graphs that contain both directed and bidi- rected edges but no directed cycles – are used to model causal and conditional independence relationships between a set of random vari- ables 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 meth- ods – primarily heuristic ones – to find score- maximizing AADMGs from data. Bow-free and Arid ADMGs can model certain equal- ity 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 distri- bution 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 heuris- tic 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 re- turn graphs that have excellent fits to data.