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 usedto model causal and conditional independencerelationships between a set of random vari-ables in the presence of latent or unmeasuredvariables. Bow-free ADMGs, Arid ADMGs,and Ancestral ADMGs (AADMG) are threewidely studied classes of ADMGs where eachclass is contained in the previously mentionedclass. There are a number of published meth-ods – primarily heuristic ones – to find score-maximizing AADMGs from data. Bow-freeand Arid ADMGs can model certain equal-ity restrictions – such as Verma constraints– between observed variables that maximalAADMGs cannot. In this work, we developthe first exact methods – based on integerprogramming – to find score-maximizing Bow-free and Arid ADMGs. Our methods work fordata that follows a continuous Gaussian distri-bution and for scores that linearly decomposeinto the sum of scores of c-components ofan ADMG. To improve scaling, we developan effective linear-programming based heuris-tic that yields solutions with high parent setsizes and/or large districts. We show thatour proposed algorithms obtain better scoresthan other state-of-the-art methods and re-turn graphs that have excellent fits to data.