{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T18:45:42Z","timestamp":1755801942356,"version":"3.44.0"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,7,16]]},"abstract":"<jats:title>Summary<\/jats:title>\n               <jats:p>We study the problem of learning directed acyclic graphs from continuous observational data, generated according to a linear Gaussian structural equation model. State-of-the-art structure learning methods for this setting have at least one of the following shortcomings: (i) they cannot provide optimality guarantees and can suffer from learning suboptimal models; (ii) they rely on the stringent assumption that the noise is homoscedastic, and hence the underlying model is fully identifiable. We overcome these shortcomings and develop a computationally efficient mixed-integer programming framework for learning medium-sized problems that accounts for arbitrary heteroscedastic noise. We present an early stopping criterion under which we can terminate the branch-and-bound procedure to achieve an asymptotically optimal solution and establish the consistency of this approximate solution. In addition, we show via numerical experiments that our method outperforms state-of-the-art algorithms and is robust to noise heteroscedasticity, whereas the performance\u00a0of some competing methods deteriorates under strong violations of the identifiability assumption. The software implementation of our method is available as the Python package micodag.<\/jats:p>","DOI":"10.1093\/biomet\/asaf032","type":"journal-article","created":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T11:21:30Z","timestamp":1745839290000},"source":"Crossref","is-referenced-by-count":0,"title":["Integer programming for learning directed acyclic graphs from nonidentifiable Gaussian models"],"prefix":"10.1093","volume":"112","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-2654-5152","authenticated-orcid":false,"given":"Tong","family":"Xu","sequence":"first","affiliation":[{"name":"Department of Industrial Engineering and Management Sciences, Northwestern University , 2145 Sheridan Road , Evanston, Illinois 60208,","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armeen","family":"Taeb","sequence":"additional","affiliation":[{"name":"Department of Statistics, University of Washington , Box 354322 , Seattle, Washington 98195,","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simge","family":"K\u00fc\u00e7\u00fckyavuz","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering and Management Sciences, Northwestern University , 2145 Sheridan Road , Evanston, Illinois 60208,","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8846-3533","authenticated-orcid":false,"given":"Ali","family":"Shojaie","sequence":"additional","affiliation":[{"name":"Departments of Biostatistics and Statistics, University of Washington , Box 351617 , Seattle, Washington 98195,","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2025,4,28]]},"reference":[{"key":"2025082101572169100_asaf032-B1","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/j.artint.2015.03.003","article-title":"Integer linear programming for the Bayesian network structure learning problem","volume":"244","author":"Bartlett","year":"2017","journal-title":"Artif. Intel"},{"year":"2023","author":"Behdin","key":"2025082101572169100_asaf032-B3"},{"year":"2021","author":"Behdin","key":"2025082101572169100_asaf032-B2"},{"key":"2025082101572169100_asaf032-B4","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/s10107-019-01419-7","article-title":"Certifiably optimal sparse inverse covariance estimation","volume":"184","author":"Bertsimas","year":"2019","journal-title":"Math. Program."},{"key":"2025082101572169100_asaf032-B5","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1198\/jasa.2011.tm10155","article-title":"A constrained $ \\ell_{1} $ minimization approach to sparse precision matrix estimation","volume":"106","author":"Cai","year":"2011","journal-title":"J. Am. Statist. Assoc"},{"key":"2025082101572169100_asaf032-B6","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1093\/biomet\/asz049","article-title":"On causal discovery with an equal-variance assumption","volume":"106","author":"Chen","year":"2019","journal-title":"Biometrika"},{"key":"2025082101572169100_asaf032-B7","first-page":"507","article-title":"Optimal structure identification with greedy search","volume":"3","author":"Chickering","year":"2002","journal-title":"J. Mach. Learn. Res"},{"first-page":"241","year":"2020","author":"Chickering","key":"2025082101572169100_asaf032-B8"},{"key":"2025082101572169100_asaf032-B9","doi-asserted-by":"crossref","first-page":"1409","DOI":"10.1007\/s10898-012-9842-2","article-title":"Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio selection problems","volume":"56","author":"Cui","year":"2013","journal-title":"J. Glob. Optimiz"},{"key":"2025082101572169100_asaf032-B10","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/s10107-016-1087-2","article-title":"Polyhedral aspects of score equivalence in Bayesian network structure learning","volume":"164","author":"Cussens","year":"2017","journal-title":"Math. Program."},{"key":"2025082101572169100_asaf032-B11","first-page":"185","article-title":"Bayesian network structure learning with integer programming: polytopes, facets and complexity","volume":"58","author":"Cussens","year":"2017","journal-title":"J. Artif. Intel. Res"},{"key":"2025082101572169100_asaf032-B12","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF02592064","article-title":"An outer-approximation algorithm for a class of mixed-integer nonlinear programs","volume":"36","author":"Duran","year":"1986","journal-title":"Math. Program"},{"key":"2025082101572169100_asaf032-B13","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.orl.2006.03.008","article-title":"SDP diagonalizations and perspective cuts for a class of nonseparable MIQP","volume":"35","author":"Frangioni","year":"2007","journal-title":"Oper. Res.Lett"},{"key":"2025082101572169100_asaf032-B14","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1093\/biostatistics\/kxm045","article-title":"Sparse inverse covariance estimation with the graphical lasso","volume":"9","author":"Friedman","year":"2007","journal-title":"Biostatistics"},{"year":"2018","author":"Ghoshal","key":"2025082101572169100_asaf032-B15"},{"key":"2025082101572169100_asaf032-B16","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1007\/BF01582009","article-title":"On the acyclic subgraph polytope","volume":"33","author":"Gr\u00f6tschel","year":"1985","journal-title":"Math. Program"},{"key":"2025082101572169100_asaf032-B17","first-page":"613","article-title":"Estimating high-dimensional directed acyclic graphs with the PC-algorithm","volume":"8","author":"Kalisch","year":"2007","journal-title":"J. Mach. Learn. Res"},{"key":"2025082101572169100_asaf032-B18","first-page":"1","article-title":"Consistent second-order conic integer programming for learning Bayesian networks","volume":"24","author":"K\u00fc\u00e7\u00fckyavuz","year":"2023","journal-title":"J. Mach. Learn. Res"},{"key":"2025082101572169100_asaf032-B19","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1287\/ijoo.2019.0040","article-title":"Integer programming for learning directed acyclic graphs from continuous data","volume":"3","author":"Manzour","year":"2021","journal-title":"INFORMS J Optim."},{"first-page":"2888","year":"2020","author":"Misra","key":"2025082101572169100_asaf032-B20"},{"key":"2025082101572169100_asaf032-B21","first-page":"1","article-title":"Bayesian network learning via topological order","volume":"18","author":"Park","year":"2017","journal-title":"J. Mach. Learn. Res"},{"key":"2025082101572169100_asaf032-B22","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1093\/biomet\/ast043","article-title":"Identifiability of Gaussian structural equation models with equal error variances","volume":"101","author":"Peters","year":"2013","journal-title":"Biometrika"},{"year":"2025","author":"R Development Core Team","key":"2025082101572169100_asaf032-B23"},{"key":"2025082101572169100_asaf032-B24","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1093\/biomet\/asq038","article-title":"Penalized likelihood methods for estimation of sparse high-dimensional directed acyclic graphs","volume":"97","author":"Shojaie","year":"2010","journal-title":"Biometrika"},{"key":"2025082101572169100_asaf032-B25","first-page":"445","volume-title":"Proc. 22nd Int. Conf. Uncertainty Artif. Intel","author":"Silander","year":"2006"},{"key":"2025082101572169100_asaf032-B26","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1093\/biomet\/asaa104","article-title":"Consistency guarantees for greedy permutation-based causal inference algorithms","volume":"108","author":"Solus","year":"2021","journal-title":"Biometrika"},{"key":"2025082101572169100_asaf032-B27","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-2748-9","volume-title":"Causation, Prediction, and Search","author":"Spirtes","year":"1993"},{"key":"2025082101572169100_asaf032-B28","first-page":"436","article-title":"Geometry of the faithfulness assumption in causal inference","volume":"41","author":"Uhler","year":"2012","journal-title":"Ann. Statist."},{"key":"2025082101572169100_asaf032-B29","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1214\/13-AOS1085","article-title":"penalized maximum likelihood for sparse directed acyclic graphs","volume":"41","author":"van de Geer","year":"2013","journal-title":"Ann. Statist."},{"key":"2025082101572169100_asaf032-B30","first-page":"255","volume-title":"Proc. 6th Ann. Conf. Uncertainty Artif. Intel","author":"Verma","year":"1990"},{"key":"2025082101572169100_asaf032-B33","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1007\/s10107-023-01982-0","article-title":"On the convex hull of convex quadratic optimization problems with indicators","volume":"204","author":"Wei","year":"2023","journal-title":"Math. Program."},{"key":"2025082101572169100_asaf032-B31","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/978-3-030-45771-6_33","volume-title":"Integer Programming and Combinatorial Optimization","author":"Wei","year":"2020"},{"key":"2025082101572169100_asaf032-B32","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s10107-021-01734-y","article-title":"Ideal formulations for constrained convex optimization problems with indicator variables","volume":"192","author":"Wei","year":"2022","journal-title":"Math. Program."},{"volume-title":"Integer and Combinatorial Optimization","year":"1999","author":"Wolsey","key":"2025082101572169100_asaf032-B34"}],"container-title":["Biometrika"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/biomet\/advance-article-pdf\/doi\/10.1093\/biomet\/asaf032\/63021712\/asaf032.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/112\/3\/asaf032\/63021712\/asaf032.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/112\/3\/asaf032\/63021712\/asaf032.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T05:57:35Z","timestamp":1755755855000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/biomet\/article\/doi\/10.1093\/biomet\/asaf032\/8121152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,7,16]]}},"URL":"https:\/\/doi.org\/10.1093\/biomet\/asaf032","relation":{},"ISSN":["1464-3510"],"issn-type":[{"type":"electronic","value":"1464-3510"}],"subject":[],"published-other":{"date-parts":[[2025]]},"published":{"date-parts":[[2025]]},"article-number":"asaf032"}}