Integer Programming Based Methods and Heuristics for Causal Graph Learning

Sanjeeb Dash, Joao Goncalves, Tian Gao
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:1360-1368, 2025.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-dash25a, title = {Integer Programming Based Methods and Heuristics for Causal Graph Learning}, author = {Dash, Sanjeeb and Goncalves, Joao and Gao, Tian}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {1360--1368}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/dash25a/dash25a.pdf}, url = {https://proceedings.mlr.press/v258/dash25a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Integer Programming Based Methods and Heuristics for Causal Graph Learning %A Sanjeeb Dash %A Joao Goncalves %A Tian Gao %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-dash25a %I PMLR %P 1360--1368 %U https://proceedings.mlr.press/v258/dash25a.html %V 258 %X 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.
APA
Dash, S., Goncalves, J. & Gao, T.. (2025). Integer Programming Based Methods and Heuristics for Causal Graph Learning. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:1360-1368 Available from https://proceedings.mlr.press/v258/dash25a.html.

Related Material