{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:40:08Z","timestamp":1750293608928,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,12,25]],"date-time":"2024-12-25T00:00:00Z","timestamp":1735084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JST CREST","award":["JPMJCR21D2"],"award-info":[{"award-number":["JPMJCR21D2"]}]},{"name":"JST SPRING","award":["JPMJSP2108"],"award-info":[{"award-number":["JPMJSP2108"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>A Bayesian network is a powerful tool for representing uncertainty in data, offering transparent and interpretable inference, unlike neural networks\u2019 black-box mechanisms. To fully harness the potential of Bayesian networks, it is essential to learn the graph structure that appropriately represents variable interrelations within data. Score-based structure learning, which involves constructing collections of potentially optimal parent sets for each variable, is computationally intensive, especially when dealing with high-dimensional data in discrete random variables. Our proposed novel acceleration algorithm extracts high levels of parallelism, offering significant advantages even with reduced reusability of computational results. In addition, it employs an elastic data representation tailored for parallel computation, making it FPGA-friendly and optimizing module occupancy while ensuring uniform handling of diverse problem scenarios. Demonstrated on a Xilinx Alveo U50 FPGA, our implementation significantly outperforms optimal CPU algorithms and is several times faster than GPU implementations on an NVIDIA TITAN RTX. Furthermore, the results of performance modeling for the accelerator indicate that, for sufficiently large problem instances, it is weakly scalable, meaning that it effectively utilizes increased computational resources for parallelization. To our knowledge, this is the first study to propose a comprehensive methodology for accelerating score-based structure learning, blending algorithmic and architectural considerations.<\/jats:p>","DOI":"10.1145\/3674842","type":"journal-article","created":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T20:44:31Z","timestamp":1719953071000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Scalable Accelerator for Local Score Computation of Structure Learning in Bayesian Networks"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-6732-0778","authenticated-orcid":false,"given":"Ryota","family":"Miyagi","sequence":"first","affiliation":[{"name":"The University of Tokyo, Bunkyo-ku, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2009-7105","authenticated-orcid":false,"given":"Ryota","family":"Yasudo","sequence":"additional","affiliation":[{"name":"Kyoto University, Sakyo-ku, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6681-4192","authenticated-orcid":false,"given":"Kentaro","family":"Sano","sequence":"additional","affiliation":[{"name":"RIKEN Center for Computational Science (R-CCS), Kobe, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2660-5927","authenticated-orcid":false,"given":"Hideki","family":"Takase","sequence":"additional","affiliation":[{"name":"The University of Tokyo, Bunkyo-ku, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,25]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"bnlearn - Bayesian Network Repository. Retrieved from https:\/\/www.bnlearn.com\/bnrepository\/"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/titb.2011.2119322"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jbi.2014.08.010"},{"key":"e_1_3_1_5_2","author":"Bouckaert Remco R.","year":"1995","unstructured":"Remco R. Bouckaert. 1995. Bayesian Belief Networks: From Construction to Inference. Ph. D. Dissertation.","journal-title":"Bayesian Belief Networks: From Construction to Inference"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3502289"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1044703"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2750365"},{"key":"e_1_3_1_9_2","first-page":"2709","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics","author":"Correia Alvaro H. C.","year":"2020","unstructured":"Alvaro H. C. Correia, James Cussens, and Cassio de Campos. 2020. On pruning for score-based Bayesian network structure learning. In Proceedings of the International Conference on Artificial Intelligence and Statistics. PMLR, 2709\u20132718."},{"key":"e_1_3_1_10_2","first-page":"153","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI \u201911)","author":"Cussens James","year":"2011","unstructured":"James Cussens. 2011. Bayesian network learning with cutting planes. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI \u201911). 153\u2013160."},{"key":"e_1_3_1_11_2","first-page":"29","article-title":"An upper bound for BDeu local scores","author":"Cussens James","year":"2012","unstructured":"James Cussens. 2012. An upper bound for BDeu local scores. In Proceedings of the ECAI-2012 Workshop on Algorithmic Issues for Inference in Graphical Models (AIGM \u201912), 29\u201335.","journal-title":"Proceedings of the ECAI-2012 Workshop on Algorithmic Issues for Inference in Graphical Models (AIGM \u201912)"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5203"},{"key":"e_1_3_1_13_2","first-page":"431","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"24","author":"Campos Cassio de","year":"2010","unstructured":"Cassio de Campos and Qiang Ji. 2010. Properties of Bayesian dirichlet scores to learn bayesian network structures. Proceedings of the AAAI Conference on Artificial Intelligence 24 (2010), 431\u2013436."},{"issue":"5","key":"e_1_3_1_14_2","doi-asserted-by":"crossref","first-page":"1205","DOI":"10.1109\/TBME.2010.2053540","article-title":"A boosted Bayesian multiresolution classifier for prostate cancer detection from digitized needle biopsies","volume":"59","author":"Doyle Scott","year":"2010","unstructured":"Scott Doyle, Michael Feldman, John Tomaszewski, and Anant Madabhushi. 2010. A boosted Bayesian multiresolution classifier for prostate cancer detection from digitized needle biopsies. IEEE Transactions on Biomedical Engineering 59, 5 (2010), 1205\u20131218.","journal-title":"IEEE Transactions on Biomedical Engineering"},{"key":"e_1_3_1_15_2","first-page":"1193","volume-title":"Proceedings of the 34th International Conference on Machine Learning","author":"Gao Tian","year":"2017","unstructured":"Tian Gao, Kshitij Fadnis, and Murray Campbell. 2017. Local-to-global Bayesian network structure learning. In Proceedings of the 34th International Conference on Machine Learning. PMLR, 1193\u20131202. Retrieved from https:\/\/proceedings.mlr.press\/v70\/gao17a.html ISSN: 2640-3498."},{"key":"e_1_3_1_16_2","article-title":"Local causal discovery of direct causes and effects","volume":"28","author":"Gao Tian","year":"2015","unstructured":"Tian Gao and Qiang Ji. 2015. Local causal discovery of direct causes and effects. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 28. Curran Associates, Inc. Retrieved from https:\/\/papers.nips.cc\/paper\/2015\/hash\/fcdf25d6e191893e705819b177cddea0-Abstract.html","journal-title":"Proceedings of the Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2016.2539338"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2016.09.009"},{"key":"e_1_3_1_19_2","first-page":"1685","volume-title":"Proceedings of the 35th International Conference on Machine Learning","author":"Gao Tian","year":"2018","unstructured":"Tian Gao and Dennis Wei. 2018. Parallel Bayesian network structure learning. In Proceedings of the 35th International Conference on Machine Learning. PMLR, 1685\u20131694. Retrieved from https:\/\/proceedings.mlr.press\/v80\/gao18b.html ISSN: 2640-3498."},{"key":"e_1_3_1_20_2","first-page":"12328","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"35","author":"Gr\u00fcttemeier Niels","year":"2021","unstructured":"Niels Gr\u00fcttemeier, Christian Komusiewicz, and Nils Morawietz. 2021. Efficient Bayesian network structure learning via parameterized local search on topological orderings. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 12328\u201312335."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2017.00014"},{"key":"e_1_3_1_22_2","first-page":"289","volume-title":"Proceedings of the International Conference on Computational Learning Theory","author":"Koivisto Mikko","year":"2006","unstructured":"Mikko Koivisto. 2006. Parent assignment is hard for the MDL, AIC, and NML costs. In Proceedings of the International Conference on Computational Learning Theory. Springer, 289\u2013303."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/1795555"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029459"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.537345"},{"key":"e_1_3_1_26_2","first-page":"129","volume-title":"Proceedings of the Canadian Conference on Artificial Intelligence","author":"Lee Colin","year":"2017","unstructured":"Colin Lee and Peter van Beek. 2017. Metaheuristics for score-and-search Bayesian network structure learning. In Proceedings of the Canadian Conference on Artificial Intelligence. Springer, 129\u2013141."},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2899096"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04534-4_8"},{"key":"e_1_3_1_29_2","first-page":"479","volume-title":"Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence (UAI \u201911)","author":"Malone Brandon","year":"2011","unstructured":"Brandon Malone, Changhe Yuan, Eric A. Hansen, and Susan Bridges. 2011. Improving the scalability of optimal Bayesian network learning with external-memory frontier breadth-first branch and bound search. In Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence (UAI \u201911). AUAI Press, Arlington, Virginia, 479\u2013488."},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/1622788.1622792"},{"issue":"1","key":"e_1_3_1_31_2","doi-asserted-by":"crossref","first-page":"23653","DOI":"10.1038\/s41598-021-02394-w","article-title":"Novel cancer subtyping method based on patient-specific gene regulatory network","volume":"11","author":"Nakazawa Mai A.","year":"2021","unstructured":"Mai A. Nakazawa, Yoshinori Tamada, Yoshihisa Tanaka, Marie Ikeguchi, Kako Higashihara, and Yasushi Okuno. 2021. Novel cancer subtyping method based on patient-specific gene regulatory network. Scientific Reports 11, 1 (2021), 23653.","journal-title":"Scientific Reports"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-28379-1_2"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICFPT51103.2020.00013"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1140\/epjst\/e2015-02349-9"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/52121"},{"key":"e_1_3_1_36_2","unstructured":"Yuta Shikuri. 2022. Bayesian network structure learning using digital annealer. arXiv:2006.06926 [cs stat]. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.2006.06926"},{"key":"e_1_3_1_37_2","first-page":"445","article-title":"A simple approach for finding the globally optimal Bayesian networkstructure","author":"Silander Tomi","year":"2006","unstructured":"Tomi Silander and Petri Myllym\u00e4ki. 2006. A simple approach for finding the globally optimal Bayesian networkstructure. In Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence (Cambridge, MA, USA)(UAI\u201906). AUAI Press, Arlington, Virginia, USA, 445\u2013452.","journal-title":"Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence (Cambridge, MA, USA)(UAI\u201906)"},{"issue":"2","key":"e_1_3_1_38_2","doi-asserted-by":"crossref","first-page":"306","DOI":"10.3390\/biom10020306","article-title":"System-based differential gene network analysis for characterizing a sample-specific subnetwork","volume":"10","author":"Tanaka Yoshihisa","year":"2020","unstructured":"Yoshihisa Tanaka, Yoshinori Tamada, Marie Ikeguchi, Fumiyoshi Yamashita, and Yasushi Okuno. 2020. System-based differential gene network analysis for characterizing a sample-specific subnetwork. Biomolecules 10, 2 (2020), 306.","journal-title":"Biomolecules"},{"key":"e_1_3_1_39_2","first-page":"584","volume-title":"Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI\u201905)","author":"Teyssier Marc","year":"2005","unstructured":"Marc Teyssier and Daphne Koller. 2005. Ordering-based search: A simple and effective algorithm for learning Bayesian networks. In Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI\u201905). AUAI Press, Arlington, Virginia, 584\u2013590."},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10614-020-10065-7"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3674842","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3674842","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:56Z","timestamp":1750291556000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3674842"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,25]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3674842"],"URL":"https:\/\/doi.org\/10.1145\/3674842","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2024,12,25]]},"assertion":[{"value":"2024-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}