{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T07:17:00Z","timestamp":1750835820919,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001778","name":"Deakin University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001778","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Distributional estimates in Bayesian approaches in structure learning have advantages compared to the ones performing point estimates when handling epistemic uncertainty. Differentiable methods for Bayesian structure learning have been developed to enhance the scalability of the inference process and are achieving optimistic outcomes. However, in the differentiable continuous setting, constraining the acyclicity of learned graphs emerges as another challenge. Various works utilize post-hoc penalization scores to impose this constraint which cannot assure acyclicity. The topological ordering of the variables is one type of prior knowledge that contains valuable information about the acyclicity of a directed graph. In this work, we propose a framework to guarantee the acyclicity of inferred graphs by integrating the information from the topological ordering into the inference process. Our integration framework does not interfere with the differentiable inference process while being able to strictly assure the acyclicity of learned graphs and reduce the inference complexity. Our extensive empirical experiments on both synthetic and real data have demonstrated the effectiveness of our approach with preferable results compared to related Bayesian approaches.<\/jats:p>","DOI":"10.1007\/s10115-024-02140-4","type":"journal-article","created":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T15:01:57Z","timestamp":1716994917000},"page":"5605-5630","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Constraining acyclicity of differentiable Bayesian structure learning with topological ordering"],"prefix":"10.1007","volume":"66","author":[{"given":"Quang-Duy","family":"Tran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phuoc","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bao","family":"Duong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thin","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,29]]},"reference":[{"issue":"5439","key":"2140_CR1","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509\u2013512","journal-title":"Science"},{"issue":"210","key":"2140_CR2","first-page":"1","volume":"24","author":"Y Bengio","year":"2023","unstructured":"Bengio Y, Lahlou S, Deleu T et al (2023) GFlowNet foundations. J Mach Learn Res 24(210):1\u201355","journal-title":"J Mach Learn Res"},{"key":"2140_CR3","unstructured":"Bradbury J, Frostig R, Hawkins P, et\u00a0al (2018) JAX: Composable transformations of Python+NumPy programs"},{"issue":"6","key":"2140_CR4","doi-asserted-by":"publisher","first-page":"2526","DOI":"10.1214\/14-AOS1260","volume":"42","author":"P B\u00fchlmann","year":"2014","unstructured":"B\u00fchlmann P, Peters J, Ernest J (2014) CAM: Causal additive models, high-dimensional order search and penalized regression. The Ann Stat 42(6):2526\u20132556","journal-title":"The Ann Stat"},{"key":"2140_CR5","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1186\/1471-2105-7-43","volume":"7","author":"T Van den Bulcke","year":"2006","unstructured":"Van den Bulcke T, Van Leemput K, Naudts B et al (2006) SynTReN: a generator of synthetic gene expression data for design and analysis of structure learning algorithms. BMC Bioinf 7:43","journal-title":"BMC Bioinf"},{"issue":"4","key":"2140_CR6","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1093\/biomet\/asz049","volume":"106","author":"W Chen","year":"2019","unstructured":"Chen W, Drton M, Wang YS (2019) On causal discovery with an equal-variance assumption. Biometrika 106(4):973\u2013980","journal-title":"Biometrika"},{"key":"2140_CR7","first-page":"507","volume":"3","author":"DM Chickering","year":"2002","unstructured":"Chickering DM (2002) Optimal structure identification with greedy search. J Mach Learn Res 3:507\u2013554","journal-title":"J Mach Learn Res"},{"key":"2140_CR8","first-page":"1287","volume":"5","author":"M Chickering","year":"2004","unstructured":"Chickering M, Heckerman D, Meek C (2004) Large-sample learning of Bayesian networks is NP-hard. J Mach Learn Res 5:1287\u20131330","journal-title":"J Mach Learn Res"},{"key":"2140_CR9","unstructured":"Cundy C, Grover A, Ermon S (2021) BCD Nets: Scalable variational approaches for Bayesian causal discovery. In: Advances in Neural Information Processing Systems, pp 7095\u20137110"},{"key":"2140_CR10","unstructured":"Deleu T, G\u00f3is A, Emezue C, et\u00a0al (2022) Bayesian structure learning with generative flow networks. In: Proceedings of Conference on Uncertainty in Artificial Intelligence, pp 518\u2013528"},{"key":"2140_CR11","unstructured":"Deleu T, Nishikawa-Toomey M, Subramanian J, et\u00a0al (2023) Joint bayesian inference of graphical structure and parameters with a single generative flow network. In: Advances in Neural Information Processing Systems"},{"key":"2140_CR12","unstructured":"Eggeling R, Viinikka J, Vuoksenmaa A, et\u00a0al (2019) On structure priors for learning Bayesian networks. In: Proceedings of the International Conference on Artificial Intelligence and Statistics, pp 1687\u20131695"},{"key":"2140_CR13","unstructured":"Erd\u0151s P, R\u00e9nyi A (1960) On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5"},{"key":"2140_CR14","unstructured":"Friedman N, Goldszmidt M, Wyner A (1999) Data analysis with Bayesian networks: A bootstrap approach. In: Proceedings of the Conference on Uncertainty in Artificial Intelligence, pp 196\u2013205"},{"key":"2140_CR15","unstructured":"Gao M, Ding Y, Aragam B (2020) A polynomial-time algorithm for learning nonparametric causal graphs. In: Advances in Neural Information Processing Systems, pp 11599\u201311611"},{"key":"2140_CR16","doi-asserted-by":"crossref","unstructured":"Geiger D, Heckerman D (1994) Learning Gaussian networks. In: Proceedings of the Conference on Uncertainty in Artificial Intelligence, pp 235\u2013243","DOI":"10.1016\/B978-1-55860-332-5.50035-3"},{"key":"2140_CR17","doi-asserted-by":"crossref","unstructured":"Hagberg AA, Schult DA, Swart PJ (2008) Exploring network structure, dynamics, and function using NetworkX. In: Proceedings of the Python in Science Conference, pp 11\u201315","DOI":"10.25080\/TCWV9851"},{"issue":"7825","key":"2140_CR18","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/s41586-020-2649-2","volume":"585","author":"CR Harris","year":"2020","unstructured":"Harris CR, Millman KJ, van der Walt SJ et al (2020) Array programming with NumPy. Nature 585(7825):357\u2013362","journal-title":"Nature"},{"issue":"17","key":"2140_CR19","doi-asserted-by":"publisher","first-page":"2271","DOI":"10.1093\/bioinformatics\/btg313","volume":"19","author":"D Husmeier","year":"2003","unstructured":"Husmeier D (2003) Sensitivity and specificity of inferring genetic regulatory interactions from microarray experiments with dynamic Bayesian networks. Bioinformatics 19(17):2271\u20132282","journal-title":"Bioinformatics"},{"key":"2140_CR20","unstructured":"Jang E, Gu S, Poole B (2017) Categorical reparameterization with Gumbel-softmax. In: Proceedings of the International Conference on Learning Representations"},{"key":"2140_CR21","unstructured":"Koivisto M (2006) Advances in exact Bayesian structure discovery in Bayesian networks. In: Proceedings of the Conference on Uncertainty in Artificial Intelligence, pp 241\u2013248"},{"key":"2140_CR22","volume-title":"Probabilistic graphical models: principles and techniques","author":"D Koller","year":"2009","unstructured":"Koller D, Friedman N (2009) Probabilistic graphical models: principles and techniques. The MIT Press"},{"key":"2140_CR23","unstructured":"Lachapelle S, Brouillard P, Deleu T, et\u00a0al (2020) Gradient-based neural DAG learning. In: Proceedings of the International Conference on Learning Representations"},{"key":"2140_CR24","first-page":"391","volume":"2020","author":"HC Lee","year":"2019","unstructured":"Lee HC, Danieletto M, Miotto R et al (2019) Scaling structural learning with NO-BEARS to infer causal transcriptome networks. Pac Symp Biocomput 2020:391\u2013402","journal-title":"Pac Symp Biocomput"},{"key":"2140_CR25","doi-asserted-by":"crossref","unstructured":"Lim LH (2020) Hodge Laplacians on graphs. SIAM Review 62(3)","DOI":"10.1137\/18M1223101"},{"key":"2140_CR26","unstructured":"Liu Q, Wang D (2016) Stein variational gradient descent: A general purpose Bayesian inference algorithm. In: Advances in Neural Information Processing Systems"},{"key":"2140_CR27","unstructured":"Lorch L, Rothfuss J, Sch\u00f6lkopf B, et\u00a0al (2021) DiBS: Differentiable Bayesian structure learning. In: Advances in Neural Information Processing Systems, pp 24111\u201324123"},{"key":"2140_CR28","unstructured":"Lorch L, Sussex S, Rothfuss J, et\u00a0al (2022) Amortized inference for causal structure learning. In: Advances in Neural Information Processing Systems, pp 13104\u201313118"},{"key":"2140_CR29","unstructured":"Maddison CJ, Mnih A, Teh YW (2017) The concrete distribution: A continuous relaxation of discrete random variables. In: Proceedings of the International Conference on Learning Representations"},{"issue":"2","key":"2140_CR30","doi-asserted-by":"publisher","first-page":"215","DOI":"10.2307\/1403615","volume":"63","author":"D Madigan","year":"1995","unstructured":"Madigan D, York J, Allard D (1995) Bayesian graphical models for discrete data. Int Stat Rev\/Rev Int de Stat 63(2):215\u2013232","journal-title":"Int Stat Rev\/Rev Int de Stat"},{"key":"2140_CR31","volume-title":"Introduction to algorithms: A creative approach","author":"U Manber","year":"1989","unstructured":"Manber U (1989) Introduction to algorithms: A creative approach. Addison-Wesley Longman Publishing Co., Inc"},{"key":"2140_CR32","doi-asserted-by":"crossref","unstructured":"Molnar C, Casalicchio G, Bischl B (2020) Interpretable machine learning \u2013 a brief history, state-of-the-art and challenges. In: Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases Workshops, pp 417\u2013431","DOI":"10.1007\/978-3-030-65965-3_28"},{"key":"2140_CR33","unstructured":"Montagna F, Noceti N, Rosasco L, et\u00a0al (2022) Scalable causal discovery with score matching. In: Proceedings of the Conference on Neural Information Processing Systems Workshop on Score-Based Methods"},{"key":"2140_CR34","unstructured":"Nishikawa-Toomey M, Deleu T, Subramanian J, et\u00a0al (2022) Bayesian learning of causal structure and mechanisms with GFlowNets and variational Bayes. arXiv preprint arXiv:2211.02763"},{"key":"2140_CR35","unstructured":"Paszke A, Gross S, Massa F, et\u00a0al (2019) PyTorch: An imperative style, high-performance deep learning library. In: Advances in Neural Information Processing Systems"},{"issue":"1","key":"2140_CR36","doi-asserted-by":"publisher","DOI":"10.1002\/sta4.183","volume":"7","author":"G Raskutti","year":"2018","unstructured":"Raskutti G, Uhler C (2018) Learning directed acyclic graph models based on sparsest permutations. Stat 7(1):e183","journal-title":"Stat"},{"key":"2140_CR37","unstructured":"Rolland P, Cevher V, Kleindessner M, et\u00a0al (2022) Score matching enables causal discovery of nonlinear additive noise models. In: Proceedings of the International Conference on Machine Learning, pp 18741\u201318753"},{"issue":"5721","key":"2140_CR38","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1126\/science.1105809","volume":"308","author":"K Sachs","year":"2005","unstructured":"Sachs K, Perez O, Pe\u2019er D et al (2005) Causal protein-signaling networks derived from multiparameter single-cell data. Science 308(5721):523\u2013529","journal-title":"Science"},{"key":"2140_CR39","unstructured":"Sanchez P, Liu X, O\u2019Neil AQ, et\u00a0al (2023) Diffusion models for causal discovery via topological ordering. In: Proceedings of the International Conference on Learning Representations"},{"key":"2140_CR40","unstructured":"Serv\u00e9n D, Brummitt C (2018) pyGAM: Generalized additive models in Python"},{"issue":"4","key":"2140_CR41","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1093\/biomet\/asaa104","volume":"108","author":"L Solus","year":"2021","unstructured":"Solus L, Wang Y, Uhler C (2021) Consistency guarantees for greedy permutation-based causal inference algorithms. Biometrika 108(4):795\u2013814","journal-title":"Biometrika"},{"key":"2140_CR42","volume-title":"Causation, Prediction, and Search","author":"P Spirtes","year":"2000","unstructured":"Spirtes P, Glymour C, Scheines R (2000) Causation, Prediction, and Search. The MIT Press, Adaptive Computation and Machine Learning Series"},{"key":"2140_CR43","unstructured":"Squires C, Uhler C (2022) Causal structure learning: A combinatorial perspective. Foundations of Computational Mathematics pp 1\u201335"},{"key":"2140_CR44","unstructured":"Squires C, Wang Y, Uhler C (2020) Permutation-based causal structure learning with unknown intervention targets. In: Proceedings of the Conference on Uncertainty in Artificial Intelligence, pp 1039\u20131048"},{"key":"2140_CR45","doi-asserted-by":"crossref","unstructured":"Tran QD, Nguyen P, Duong B, et\u00a0al (2023) Differentiable Bayesian structure learning with acyclicity assurance. In: Proceedings of the IEEE International Conference on Data Mining","DOI":"10.1109\/ICDM58522.2023.00069"},{"key":"2140_CR46","unstructured":"Wang Y, Solus L, Yang K, et\u00a0al (2017) Permutation-based causal inference algorithms with interventions. Advances in Neural Information Processing Systems 30"},{"key":"2140_CR47","unstructured":"Yu Y, Chen J, Gao T, et\u00a0al (2019) DAG-GNN: DAG structure learning with graph neural networks. In: Proceedings of the International Conference on Machine Learning, pp 7154\u20137163"},{"key":"2140_CR48","unstructured":"Yu Y, Gao T, Yin N, et\u00a0al (2021) DAGs with No Curl: An efficient DAG structure learning approach. In: Proceedings of the International Conference on Machine Learning, pp 12156\u201312166"},{"issue":"269","key":"2140_CR49","first-page":"1","volume":"23","author":"R Zhao","year":"2022","unstructured":"Zhao R, He X, Wang J (2022) Learning linear non-Gaussian directed acyclic graph with diverging number of nodes. J Mach Learn Res 23(269):1\u201334","journal-title":"J Mach Learn Res"},{"key":"2140_CR50","unstructured":"Zheng X, Aragam B, Ravikumar PK, et\u00a0al (2018) DAGs with NO-TEARS: Continuous optimization for structure learning. In: Advances in Neural Information Processing Systems"},{"key":"2140_CR51","unstructured":"Zheng X, Dan C, Aragam B, et\u00a0al (2020) Learning sparse nonparametric DAGs. In: Proceedings of the International Conference on Artificial Intelligence and Statistics, pp 3414\u20133425"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-024-02140-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10115-024-02140-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-024-02140-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,20]],"date-time":"2024-11-20T17:04:15Z","timestamp":1732122255000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10115-024-02140-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":51,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["2140"],"URL":"https:\/\/doi.org\/10.1007\/s10115-024-02140-4","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"type":"print","value":"0219-1377"},{"type":"electronic","value":"0219-3116"}],"subject":[],"published":{"date-parts":[[2024,5,29]]},"assertion":[{"value":"25 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}