{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,27]],"date-time":"2025-09-27T13:54:51Z","timestamp":1758981291483,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,10,21]],"date-time":"2024-10-21T00:00:00Z","timestamp":1729468800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,10,21]]},"DOI":"10.1145\/3627673.3679813","type":"proceedings-article","created":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T19:34:11Z","timestamp":1729452851000},"page":"953-961","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Understanding GNNs for Boolean Satisfiability through Approximation Algorithms"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7639-864X","authenticated-orcid":false,"given":"Jan","family":"H\u016fla","sequence":"first","affiliation":[{"name":"University of Ostrava, Ostrava, Czech Republic"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3867-644X","authenticated-orcid":false,"given":"David","family":"Moj\u009e\u00ed\u009aek","sequence":"additional","affiliation":[{"name":"University of Ostrava, Ostrava, Czech Republic"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3487-784X","authenticated-orcid":false,"given":"Mikol\u00e1\u009a","family":"Janota","sequence":"additional","affiliation":[{"name":"Czech Technical University in Prague, Prague, Czech Republic"}]}],"member":"320","published-online":{"date-parts":[[2024,10,21]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.07.063"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.3233\/FAIA200993"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1077450.1077456"},{"key":"e_1_3_2_1_4_1","volume-title":"Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478","author":"Bronstein Michael M","year":"2021","unstructured":"Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Velickovic. 2021. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478 (2021)."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5733"},{"key":"e_1_3_2_1_6_1","first-page":"130","article-title":"Combinatorial optimization and reasoning with graph neural networks","volume":"24","author":"Cappart Quentin","year":"2023","unstructured":"Quentin Cappart, Didier Ch\u00e9telat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Velickovic. 2023. Combinatorial optimization and reasoning with graph neural networks. J. Mach. Learn. Res. 24 (2023), 130--1.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_7_1","volume-title":"Denoising Diffusion for Sampling SAT Solutions. arXiv preprint arXiv:2212.00121","author":"Freivalds Karlis","year":"2022","unstructured":"Karlis Freivalds and Sergejs Kozlovics. 2022. Denoising Diffusion for Sampling SAT Solutions. arXiv preprint arXiv:2212.00121 (2022)."},{"key":"e_1_3_2_1_8_1","first-page":"30583","article-title":"What can transformers learn in-context? A case study of simple function classes","volume":"35","author":"Garg Shivam","year":"2022","unstructured":"Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant. 2022. What can transformers learn in-context? A case study of simple function classes. Advances in Neural Information Processing Systems 35 (2022), 30583--30598.","journal-title":"Advances in Neural Information Processing Systems"},{"volume-title":"Approximation algorithms and semidefinite programming","author":"G\u00e4rtner Bernd","key":"e_1_3_2_1_9_1","unstructured":"Bernd G\u00e4rtner and Jiri Matousek. 2012. Approximation algorithms and semidefinite programming. Springer Science & Business Media."},{"key":"e_1_3_2_1_10_1","volume-title":"Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems 32","author":"Gasse Maxime","year":"2019","unstructured":"Maxime Gasse, Didier Ch\u00e9telat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. 2019. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems 32 (2019)."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11757375_10"},{"key":"e_1_3_2_1_13_1","first-page":"3988","article-title":"Deep declarative networks","volume":"44","author":"Gould Stephen","year":"2021","unstructured":"Stephen Gould, Richard Hartley, and Dylan Campbell. 2021. Deep declarative networks. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 8 (2021), 3988--4004.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_3_2_1_14_1","volume-title":"Survey propagation revisited. arXiv preprint arXiv:1206.5273","author":"Kroc Lukas","year":"2012","unstructured":"Lukas Kroc, Ashish Sabharwal, and Bart Selman. 2012. Survey propagation revisited. arXiv preprint arXiv:1206.5273 (2012)."},{"key":"e_1_3_2_1_15_1","first-page":"667","article-title":"Belief propagation neural networks","volume":"33","author":"Kuck Jonathan","year":"2020","unstructured":"Jonathan Kuck, Shuvam Chakraborty, Hao Tang, Rachel Luo, Jiaming Song, Ashish Sabharwal, and Stefano Ermon. 2020. Belief propagation neural networks. Advances in Neural Information Processing Systems 33 (2020), 667--678.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_16_1","first-page":"9608","article-title":"Can Q-learning with graph networks learn a generalizable branching heuristic for a SAT solver","volume":"33","author":"Kurin Vitaly","year":"2020","unstructured":"Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro. 2020. Can Q-learning with graph networks learn a generalizable branching heuristic for a SAT solver? Advances in Neural Information Processing Systems 33 (2020), 9608--9621.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"34","author":"Kyrillidis Anastasios","year":"2021","unstructured":"Anastasios Kyrillidis, Anshumali Shrivastava, Moshe Vardi, and Zhiwei Zhang. 2021. FourierSAT: A Fourier expansion-based algebraic framework for solving hybrid boolean constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 1552--1560."},{"key":"e_1_3_2_1_18_1","volume-title":"Graph neural networks meet neural-symbolic computing: A survey and perspective. arXiv preprint arXiv:2003.00330","author":"Lamb Lu\u00eds C","year":"2020","unstructured":"Lu\u00eds C Lamb, Artur Garcez, Marco Gori, Marcelo Prates, Pedro Avelar, and Moshe Vardi. 2020. Graph neural networks meet neural-symbolic computing: A survey and perspective. arXiv preprint arXiv:2003.00330 (2020)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255445"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN55064.2022.9892733"},{"volume-title":"Computational complexity","author":"Papadimitriou Christos H","key":"e_1_3_2_1_21_1","unstructured":"Christos H Papadimitriou. 1994. Computational complexity. Addison-Wesley."},{"key":"e_1_3_2_1_22_1","volume-title":"Conference on Uncertainty in Artificial Intelligence. https:\/\/api.semanticscholar.org\/CorpusID:15136373","author":"Park Sejun","year":"2014","unstructured":"Sejun Park and Jinwoo Shin. 2014. Max-Product Belief Propagation for Linear Programming: Applications to Combinatorial Optimization. In Conference on Uncertainty in Artificial Intelligence. https:\/\/api.semanticscholar.org\/CorpusID:15136373"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2018.10.045"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01100204"},{"key":"e_1_3_2_1_25_1","volume-title":"Pretraining task diversity and the emergence of non-Bayesian in-context learning for regression. arXiv preprint arXiv:2306.15063","author":"Ravent\u00f3s Allan","year":"2023","unstructured":"Allan Ravent\u00f3s, Mansheej Paul, Feng Chen, and Surya Ganguli. 2023. Pretraining task diversity and the emergence of non-Bayesian in-context learning for regression. arXiv preprint arXiv:2306.15063 (2023)."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(87)90125-7"},{"key":"e_1_3_2_1_27_1","volume-title":"SAT 2019, Lisbon, Portugal, July 9--12, 2019, Proceedings 22","author":"Selsam Daniel","year":"2019","unstructured":"Daniel Selsam and Nikolaj Bj\u00f8rner. 2019. Guiding high-performance SAT solvers with unsat-core predictions. In Theory and Applications of Satisfiability Testing--SAT 2019: 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9--12, 2019, Proceedings 22. Springer, 336--353."},{"key":"e_1_3_2_1_28_1","volume-title":"7th International Conference on Learning Representations, ICLR 2019","author":"Selsam Daniel","year":"2019","unstructured":"Daniel Selsam, Matthew Lamm, Benedikt B\u00fcnz, Percy Liang, Leonardo de Moura, and David L. Dill. 2019. Learning a SAT Solver from Single-Bit Supervision. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6--9, 2019. OpenReview.net. https:\/\/openreview.net\/forum?id=HJMC_iA5tm"},{"key":"e_1_3_2_1_29_1","volume-title":"Satformer: Transformers for SAT solving. arXiv preprint arXiv:2209.00953","author":"Shi Zhengyuan","year":"2022","unstructured":"Zhengyuan Shi, Min Li, Sadaf Khan, Hui-Ling Zhen, Mingxuan Yuan, and Qiang Xu. 2022. Satformer: Transformers for SAT solving. arXiv preprint arXiv:2209.00953 (2022)."},{"key":"e_1_3_2_1_30_1","volume-title":"Neural algorithmic reasoning. Patterns 2, 7","author":"Velickovic Petar","year":"2021","unstructured":"Petar Velickovic and Charles Blundell. 2021. Neural algorithmic reasoning. Patterns 2, 7 (2021)."},{"key":"e_1_3_2_1_31_1","volume-title":"NeuroComb: Improving SAT solving with graph neural networks. arXiv preprint arXiv:2110.14053","author":"Wang Wenxi","year":"2021","unstructured":"Wenxi Wang, Yang Hu, Mohit Tiwari, Sarfraz Khurshid, Kenneth McMillan, and Risto Miikkulainen. 2021. NeuroComb: Improving SAT solving with graph neural networks. arXiv preprint arXiv:2110.14053 (2021)."},{"key":"e_1_3_2_1_32_1","volume-title":"Learning local search heuristics for boolean satisfiability. Advances in Neural Information Processing Systems 32","author":"Yolcu Emre","year":"2019","unstructured":"Emre Yolcu and Barnab\u00e1s P\u00f3czos. 2019. Learning local search heuristics for boolean satisfiability. Advances in Neural Information Processing Systems 32 (2019)."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1080\/00018732.2016.1211393"},{"key":"e_1_3_2_1_34_1","volume-title":"NLocalSAT: Boosting local search with solution prediction. arXiv preprint arXiv:2001.09398","author":"Zhang Wenjie","year":"2020","unstructured":"Wenjie Zhang, Zeyu Sun, Qihao Zhu, Ge Li, Shaowei Cai, Yingfei Xiong, and Lu Zhang. 2020. NLocalSAT: Boosting local search with solution prediction. arXiv preprint arXiv:2001.09398 (2020)."}],"event":{"name":"CIKM '24: The 33rd ACM International Conference on Information and Knowledge Management","sponsor":["SIGIR ACM Special Interest Group on Information Retrieval"],"location":"Boise ID USA","acronym":"CIKM '24"},"container-title":["Proceedings of the 33rd ACM International Conference on Information and Knowledge Management"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627673.3679813","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3627673.3679813","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:07Z","timestamp":1750294687000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627673.3679813"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,21]]},"references-count":34,"alternative-id":["10.1145\/3627673.3679813","10.1145\/3627673"],"URL":"https:\/\/doi.org\/10.1145\/3627673.3679813","relation":{},"subject":[],"published":{"date-parts":[[2024,10,21]]},"assertion":[{"value":"2024-10-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}