{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T05:09:36Z","timestamp":1788584976880,"version":"build-2803163510"},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,11,15]]},"abstract":"<jats:title>Summary<\/jats:title>\n                  <jats:p>Directed acyclic graphical models are widely used to represent complex causal systems. Since the basic task of learning such a model from data is NP-hard, a standard approach is greedy search over the space of directed acyclic graphs or Markov equivalence classes of directed acyclic graphs. As the space of directed acyclic graphs on $p$ nodes and the associated space of Markov equivalence classes are both much larger than the space of permutations, it is desirable to consider permutation-based greedy searches. Here, we provide the first consistency guarantees, both uniform and high dimensional, of a greedy permutation-based search. This search corresponds to a simplex-like algorithm operating over the edge-graph of a subpolytope of the permutohedron, called a directed acyclic graph associahedron. Every vertex in this polytope is associated with a directed acyclic graph, and hence with a collection of permutations that are consistent with the directed acyclic graph ordering. A walk is performed on the edges of the polytope maximizing the sparsity of the associated directed acyclic graphs. We show via simulated and real data that this permutation search is competitive with current approaches.<\/jats:p>","DOI":"10.1093\/biomet\/asaa104","type":"journal-article","created":{"date-parts":[[2020,12,12]],"date-time":"2020-12-12T01:22:08Z","timestamp":1607736128000},"page":"795-814","source":"Crossref","is-referenced-by-count":36,"title":["Consistency guarantees for greedy permutation-based causal inference algorithms"],"prefix":"10.1093","volume":"108","author":[{"given":"L","family":"Solus","sequence":"first","affiliation":[{"name":"Institutionen f\u00f6r Matematik, KTH Royal Institute of Technology, 10044 Stockholm, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Y","family":"Wang","sequence":"additional","affiliation":[{"name":"Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C","family":"Uhler","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 77 Massachusetts Ave., Cambridge, Massachusetts 02139, U.S.A"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"key":"2021111803493885100_B1","article-title":"Ordering-based causal structure learning in the presence of latent variables","author":"Bernstein,","year":"2020"},{"key":"2021111803493885100_B2","doi-asserted-by":"crossref","DOI":"10.1016\/B978-1-4832-8287-9.50006-2","article-title":"Optimizing causal orderings for generating DAGs from data","author":"Bouckaert,","year":"1992","journal-title":"Proc. 8th Int. Conf. Uncertainty in Artificial Intelligence"},{"key":"2021111803493885100_B3","article-title":"A transformational characterization of equivalent Bayesian network structures","author":"Chickering,","year":"1995","journal-title":"Proc. 11th Conf. Uncertainty in Artificial Intelligence"},{"key":"2021111803493885100_B4","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/978-1-4612-2404-4_12","article-title":"Learning Bayesian networks is NP-complete","author":"Chickering,","year":"1996","journal-title":"Learning from Data: Artificial Intelligence and Statistics V"},{"key":"2021111803493885100_B5","first-page":"507","article-title":"Optimal structure identification with greedy search","volume":"3","author":"Chickering,","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"2021111803493885100_B6","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/BF00994110","article-title":"A Bayesian method for the induction of probabilistic networks from data","volume":"9","author":"Cooper,","year":"1992","journal-title":"Mach. Learn."},{"key":"2021111803493885100_B7","doi-asserted-by":"crossref","first-page":"1853","DOI":"10.1016\/j.cell.2016.11.038","article-title":"Perturb-seq: dissecting molecular circuits with scalable single-cell RNA profiling of pooled genetic screens","volume":"167","author":"Dixit,","year":"2016","journal-title":"Cell"},{"key":"2021111803493885100_B8","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1089\/106652700750050961","article-title":"Using Bayesian networks to analyze expression data","volume":"7","author":"Friedman,","year":"2000","journal-title":"J. Comp. Biol."},{"key":"2021111803493885100_B9","first-page":"489","article-title":"Kernel measures of conditional dependence","author":"Fukumizu,","year":"2008","journal-title":"Proc. 20th Int. Conf. Neural Information Processing Systems"},{"key":"2021111803493885100_B10","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1016\/j.molcel.2012.07.030","article-title":"A high throughput chromatin immunoprecipitation approach reveals principles of dynamic gene regulation in mammals","volume":"447","author":"Garber,","year":"2012","journal-title":"Molec. Cell."},{"key":"2021111803493885100_B11","first-page":"43","article-title":"Polymake: a framework for analyzing convex polytopes","author":"Gawrilow,","year":"1997","journal-title":"Polytopes \u2013 Combinatorics and Computation"},{"key":"2021111803493885100_B12","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/0710032","article-title":"Nested dissection of a regular finite element mesh","volume":"10","author":"George,","year":"1973","journal-title":"SIAM J. Numer. Anal."},{"key":"2021111803493885100_B13","article-title":"Enumerating Markov equivalence classes of acyclic digraph models","author":"Gillispie,","year":"2001","journal-title":"Proc. 17th Conf. Uncertainty in Artificial Intelligence"},{"key":"2021111803493885100_B14","first-page":"613","article-title":"Estimating high-dimensional DAGs with the PC-algorithm","volume":"8","author":"Kalisch,","year":"2007","journal-title":"J. Mach. Learn. Res."},{"key":"2021111803493885100_B15","first-page":"1","article-title":"Causal inference using graphical models with the R package pcalg","volume":"47","author":"Kalisch,","year":"2011","journal-title":"J. Statist. Soft."},{"key":"2021111803493885100_B16","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1109\/3468.508827","article-title":"Learning Bayesian network structures by searching for the best ordering with genetic algorithms","volume":"26","author":"Larra\u00f1aga,","year":"1996","journal-title":"IEEE Trans. Syst. Man Cyber. A"},{"key":"2021111803493885100_B17","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198522195.001.0001","author":"Lauritzen,","year":"1996","journal-title":"Graphical Models"},{"key":"2021111803493885100_B18","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1111\/j.1467-9868.2010.00740.x","article-title":"Stability selection","volume":"72","author":"Meinshausen,","year":"2010","journal-title":"J. R. Statist. Soc."},{"key":"2021111803493885100_B19","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1137\/16M107894X","article-title":"Generalized permutohedra from probabilistic graphical models","volume":"32","author":"Mohammadi,","year":"2016","journal-title":"SIAM J. Discrete Math."},{"key":"2021111803493885100_B20","doi-asserted-by":"crossref","first-page":"3151","DOI":"10.1214\/17-AOS1654","article-title":"High-dimensional consistency in score-based and hybrid structure learning","volume":"46","author":"Nandy,","year":"2018","journal-title":"Ann. Statist."},{"key":"2021111803493885100_B21","author":"Pearl,","year":"1988","journal-title":"Probabilistic Reasoning in Intelligent Systems"},{"key":"2021111803493885100_B22","author":"Pearl,","year":"2000","journal-title":"Causality: Models, Reasoning, and Inference"},{"key":"2021111803493885100_B23","year":"2021","journal-title":"R: A Language and Environment for Statistical Computing"},{"key":"2021111803493885100_B24","article-title":"Adjacency-faithfulness and conservative causal inference","author":"Ramsey,","year":"2006","journal-title":"Proc. 22nd Ann. Conf. Uncertainty in Artificial Intelligence"},{"key":"2021111803493885100_B25","doi-asserted-by":"crossref","first-page":"e183","DOI":"10.1002\/sta4.183","article-title":"Learning directed acyclic graph models based on sparsest permutations","volume":"7","author":"Raskutti,","year":"2018","journal-title":"Stat."},{"key":"2021111803493885100_B26","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1097\/00001648-200009000-00011","article-title":"Marginal structural models and causal inference in epidemiology","volume":"11","author":"Robins,","year":"2000","journal-title":"Epidemiology"},{"key":"2021111803493885100_B27","doi-asserted-by":"crossref","DOI":"10.1016\/B978-1-4832-1451-1.50036-6","article-title":"An algorithm for the construction of Bayesian network structures from data","author":"Singh,","year":"1993","journal-title":"Proc. 9th Int. Conf. Uncertainty in Artificial Intelligence"},{"key":"2021111803493885100_B28","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1754.001.0001","author":"Spirtes,","year":"2001","journal-title":"Causation, Prediction, and Search"},{"key":"2021111803493885100_B29","article-title":"Permutation-based causal structure learning with unknown intervention targets","author":"Squires,","year":"2020"},{"key":"2021111803493885100_B30","article-title":"Ordering-based search: a simple and effective algorithm for learning Bayesian networks","author":"Teyssier,","year":"2005","journal-title":"Proc. 21st Int. Conf. Uncertainty in Artificial Intelligence"},{"key":"2021111803493885100_B31","first-page":"1847","article-title":"Nonlinear directed acyclic structure learning with weakly additive noise model","author":"Tillman,","year":"2009","journal-title":"Proc. 22nd Int. Conf. Neural Information Processing Systems"},{"key":"2021111803493885100_B32","doi-asserted-by":"crossref","first-page":"1801","DOI":"10.1109\/PROC.1967.6011","article-title":"Direct solutions of sparse network equations by optimally ordered triangular factorization","volume":"55","author":"Tinney,","year":"1967","journal-title":"Proc. IEEE"},{"key":"2021111803493885100_B33","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s10994-006-6889-7","article-title":"The max-min hill-climbing Bayesian network structure learning algorithm","volume":"65","author":"Tsamardinos,","year":"2006","journal-title":"Mach. Learn."},{"key":"2021111803493885100_B34","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1214\/12-AOS1080","article-title":"Geometry of the faithfulness assumption in causal inference","volume":"41","author":"Uhler,","year":"2013","journal-title":"Ann. Statist."},{"key":"2021111803493885100_B35","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1214\/13-AOS1085","article-title":"$\\ell_0$-penalized maximum likelihood for sparse DAGs","volume":"41","author":"Van de Geer,","year":"2013","journal-title":"Ann. Statist."},{"key":"2021111803493885100_B36","first-page":"5824","article-title":"Permutation-based causal inference algorithms with interventions","author":"Wang,","year":"2017","journal-title":"Proc. 31st Int. Conf. Neural Information Processing Systems"},{"key":"2021111803493885100_B37","first-page":"5537","article-title":"Characterizing and learning equivalence classes of causal DAGs under interventions","volume":"80","author":"Yang,","year":"2018","journal-title":"Proc. Mach. Learn. Res."}],"container-title":["Biometrika"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/biomet\/advance-article-pdf\/doi\/10.1093\/biomet\/asaa104\/35387259\/asaa104.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/108\/4\/795\/41153641\/asaa104.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/108\/4\/795\/41153641\/asaa104.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,18]],"date-time":"2024-08-18T19:28:21Z","timestamp":1724009301000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/biomet\/article\/108\/4\/795\/6062392"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":37,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,1,4]]},"published-print":{"date-parts":[[2021,11,15]]}},"URL":"https:\/\/doi.org\/10.1093\/biomet\/asaa104","relation":{},"ISSN":["0006-3444","1464-3510"],"issn-type":[{"value":"0006-3444","type":"print"},{"value":"1464-3510","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,12,1]]},"published":{"date-parts":[[2021,1,4]]}}}