{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T11:40:16Z","timestamp":1738669216820,"version":"3.36.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T00:00:00Z","timestamp":1725062400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T00:00:00Z","timestamp":1725062400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U20B2045"],"award-info":[{"award-number":["U20B2045"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int. J. Mach. Learn. & Cyber."],"published-print":{"date-parts":[[2025,2]]},"DOI":"10.1007\/s13042-024-02327-9","type":"journal-article","created":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T09:02:16Z","timestamp":1725094936000},"page":"1145-1156","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Graph neural network based time estimator for SAT solver"],"prefix":"10.1007","volume":"16","author":[{"given":"Jiawei","family":"Liu","sequence":"first","affiliation":[]},{"given":"Wenyi","family":"Xiao","sequence":"additional","affiliation":[]},{"given":"Hongtao","family":"Cheng","sequence":"additional","affiliation":[]},{"given":"Chuan","family":"Shi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,31]]},"reference":[{"key":"2327_CR1","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1613\/jair.2490","volume":"32","author":"L Xu","year":"2008","unstructured":"Xu L, Hutter F, Hoos HH, Leyton-Brown K (2008) Satzilla: portfolio-based algorithm selection for sat. J Artif Intell Res 32:565\u2013606","journal-title":"J Artif Intell Res"},{"key":"2327_CR2","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.artint.2013.10.003","volume":"206","author":"F Hutter","year":"2014","unstructured":"Hutter F, Xu L, Hoos HH, Leyton-Brown K (2014) Algorithm runtime prediction: methods & evaluation. Artif Intell 206:79\u2013111","journal-title":"Artif Intell"},{"key":"2327_CR3","first-page":"459","volume":"92","author":"D Mitchell","year":"1992","unstructured":"Mitchell D, Selman B, Levesque H (1992) Hard and easy distributions of sat problems. AAAI 92:459\u2013465","journal-title":"AAAI"},{"key":"2327_CR4","doi-asserted-by":"crossref","unstructured":"Nudelman E, Leyton-Brown K, Hoos HH, Devkar A, Shoham Y (2004) Understanding random sat: beyond the clauses-to-variables ratio. In: Principles and Practice of Constraint Programming\u2013CP 2004: 10th International Conference, CP 2004, Toronto, Canada, September 27\u2013October 1, 2004. Proceedings 10, pp 438\u2013452. Springer","DOI":"10.1007\/978-3-540-30201-8_33"},{"key":"2327_CR5","doi-asserted-by":"crossref","unstructured":"Alfonso EM, Manthey N (2014) New CNF features and formula classification. In: POS@ SAT, pp 57\u201371","DOI":"10.29007\/b8t1"},{"key":"2327_CR6","doi-asserted-by":"crossref","unstructured":"Dalla M, Visentin A, O\u2019Sullivan B (2021) Automated sat problem feature extraction using convolutional autoencoders. In: 2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI), pp 232\u2013239. IEEE","DOI":"10.1109\/ICTAI52525.2021.00039"},{"key":"2327_CR7","unstructured":"Xu K, Hu W, Leskovec J, Jegelka S (2019) How powerful are graph neural networks? In: International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=ryGs6iA5Km"},{"key":"2327_CR8","doi-asserted-by":"crossref","unstructured":"He X, Deng K, Wang X, Li Y, Zhang Y, Wang M (2020) Lightgcn: Simplifying and powering graph convolution network for recommendation. In: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp 639\u2013648","DOI":"10.1145\/3397271.3401063"},{"key":"2327_CR9","unstructured":"Selsam D, Lamm M, Benedikt B, Liang P, Moura L, Dill DL (2018) Learning a sat solver from single-bit supervision. In: International Conference on Learning Representations"},{"key":"2327_CR10","doi-asserted-by":"crossref","unstructured":"Liu M, Huang P, Jia F, Zhang F, Sun Y, Cai S, Ma F, Zhang J (2023) Can graph neural networks learn to solve the maxsat problem? (student abstract). In: Proceedings of the AAAI Conference on Artificial Intelligence, vol 37, pp 16264\u201316265","DOI":"10.1609\/aaai.v37i13.26992"},{"key":"2327_CR11","first-page":"9608","volume":"33","author":"V Kurin","year":"2020","unstructured":"Kurin V, Godil S, Whiteson S, Catanzaro B (2020) Can q-learning with graph networks learn a generalizable branching heuristic for a sat solver? Adv Neural Inform Process Syst 33:9608\u20139621","journal-title":"Adv Neural Inform Process Syst"},{"key":"2327_CR12","unstructured":"B\u00fcnz B, Lamm M (2017) Graph neural networks and boolean satisfiability. arXiv preprint arXiv:1702.03592"},{"key":"2327_CR13","unstructured":"Kipf TN, Welling M (2017) Semi-supervised classification with graph convolutional networks. ICLR"},{"key":"2327_CR14","unstructured":"Veli\u010dkovi\u0107 P, Cucurull G, Casanova A, Romero A, Lio P, Bengio Y (2018) Graph attention networks. ICLR"},{"key":"2327_CR15","unstructured":"Brody S, Alon U, Yahav E (2022) How attentive are graph attention networks? In: International Conference on Learning Representations"},{"key":"2327_CR16","unstructured":"Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE (2017) Neural message passing for quantum chemistry. In: International Conference on Machine Learning, pp 1263\u20131272. PMLR"},{"key":"2327_CR17","doi-asserted-by":"crossref","unstructured":"Liu Z, Chen C, Li L, Zhou J, Li X, Song L, Qi Y (2019) Geniepath: graph neural networks with adaptive receptive paths. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol 33, pp 4424\u20134431","DOI":"10.1609\/aaai.v33i01.33014424"},{"key":"2327_CR18","unstructured":"Xu K, Li C, Tian Y, Sonobe T, Kawarabayashi K-i, Jegelka S (2018) Representation learning on graphs with jumping knowledge networks. In: International Conference on Machine Learning, pp 5453\u20135462. PMLR"},{"key":"2327_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.patter.2021.100273","author":"P Veli\u010dkovi\u0107","year":"2021","unstructured":"Veli\u010dkovi\u0107 P, Blundell C (2021) Neural algorithmic reasoning. Patterns. https:\/\/doi.org\/10.1016\/j.patter.2021.100273","journal-title":"Patterns"},{"key":"2327_CR20","unstructured":"Veli\u010dkovi\u0107 P, Ying R, Padovano M, Hadsell R, Blundell C (2019) Neural execution of graph algorithms. In: International Conference on Learning Representations"},{"key":"2327_CR21","first-page":"20","volume":"2022","author":"J Zheng","year":"2022","unstructured":"Zheng J, He K, Chen Z, Zhou J, Li C-M (2022) Combining hybrid walking strategy with kissat mab, cadical, and lstech-maple. SAT Competition 2022:20","journal-title":"SAT Competition"},{"key":"2327_CR22","doi-asserted-by":"crossref","unstructured":"Selsam D, Bj\u00f8rner N (2019) Guiding high-performance sat solvers with unsat-core predictions. In: Theory and Applications of Satisfiability Testing\u2013SAT 2019: 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9\u201312, 2019, Proceedings 22, pp 336\u2013353. Springer","DOI":"10.1007\/978-3-030-24258-9_24"},{"key":"2327_CR23","doi-asserted-by":"crossref","unstructured":"Lauria M, Elffers J, Nordstr\u00f6m J, Vinyals M (2017) Cnfgen: a generator of crafted benchmarks. In: Theory and Applications of Satisfiability Testing\u2013SAT 2017: 20th International Conference, Melbourne, VIC, Australia, August 28\u2013September 1, 2017, Proceedings 20, pp 464\u2013473. Springer","DOI":"10.1007\/978-3-319-66263-3_30"},{"issue":"1\u20132","key":"2327_CR24","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0004-3702(95)00046-1","volume":"81","author":"JM Crawford","year":"1996","unstructured":"Crawford JM, Auton LD (1996) Experimental results on the crossover point in random 3-sat. Artif Intell 81(1\u20132):31\u201357","journal-title":"Artif Intell"},{"key":"2327_CR25","doi-asserted-by":"crossref","unstructured":"Brayton R, Mishchenko A (2010) Abc: an academic industrial-strength verification tool. In: Computer Aided Verification: 22nd International Conference, CAV 2010, Edinburgh, UK, July 15-19, 2010. Proceedings 22, pp. 24\u201340. Springer","DOI":"10.1007\/978-3-642-14295-6_5"},{"key":"2327_CR26","unstructured":"Veli\u010dkovi\u0107 P, Cucurull G, Casanova A, Romero A, Li\u00f2 P, Bengio Y (2018) Graph attention networks. In: International Conference on Learning Representations"},{"key":"2327_CR27","first-page":"13260","volume":"33","author":"G Corso","year":"2020","unstructured":"Corso G, Cavalleri L, Beaini D, Li\u00f2 P, Veli\u010dkovi\u0107 P (2020) Principal neighbourhood aggregation for graph nets. Adv Neural Inform Process Syst 33:13260\u201313271","journal-title":"Adv Neural Inform Process Syst"},{"key":"2327_CR28","unstructured":"Provan-Bessell B, Dalla M, Visentin A, O\u2019Sullivan B (2022) Satfeatpy\u2013a python-based feature extraction system for satisfiability. arXiv preprint arXiv:2204.14116"},{"key":"2327_CR29","unstructured":"Huang L, Jia J, Yu B, Chun B-G, Maniatis P, Naik M (2010) Predicting execution time of computer programs using sparse polynomial regression. In: Proceedings of the 23rd International Conference on Neural Information Processing Systems, vol 1, pp 883\u2013891"},{"key":"2327_CR30","doi-asserted-by":"crossref","unstructured":"Bartz-Beielstein T, Markon S (2004) Tuning search algorithms for real-world applications: A regression tree based approach. In: Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753), vol 1, pp 1111\u20131118. IEEE","DOI":"10.1109\/CEC.2004.1330986"},{"key":"2327_CR31","unstructured":"Wang MY (2019) Deep graph library: Towards efficient and scalable deep learning on graphs. In: ICLR Workshop on Representation Learning on Graphs and Manifolds"},{"issue":"2","key":"2327_CR32","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.ejor.2020.07.063","volume":"290","author":"Y Bengio","year":"2021","unstructured":"Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: a methodological tour d?horizon. Eur J Oper Res 290(2):405\u2013421","journal-title":"Eur J Oper Res"},{"key":"2327_CR33","unstructured":"Wu H, Ramanujan R (2019) Learning to generate industrial sat instances. In: Twelfth Annual Symposium on Combinatorial Search"},{"key":"2327_CR34","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1910.13445","author":"J You","year":"2019","unstructured":"You J, Wu H, Barrett C, Ramanujan R, Leskovec J (2019) G2sat: Learning to generate sat formulas. Machine Learning. https:\/\/doi.org\/10.48550\/arXiv.1910.13445","journal-title":"Machine Learning"},{"key":"2327_CR35","unstructured":"Yolcu E, P\u00f3czos B (2019) Learning local search heuristics for boolean satisfiability. Adv Neural Inform Process Syst 32:7990-8001"},{"key":"2327_CR36","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10472-011-9230-5","volume":"61","author":"K Smith-Miles","year":"2011","unstructured":"Smith-Miles K, Hemert J (2011) Discovering the suitability of optimisation algorithms by learning from evolved instances. Ann Math Artif Intell 61:87\u2013104","journal-title":"Ann Math Artif Intell"},{"key":"2327_CR37","doi-asserted-by":"crossref","unstructured":"Hutter F, Hamadi Y, Hoos HH, Leyton-Brown K (2006) Performance prediction and automated tuning of randomized and parametric algorithms. In: Principles and Practice of Constraint Programming-CP 2006: 12th International Conference, CP 2006, Nantes, France, 25\u201329 Sep 2006. Proceedings 12, pp 213\u2013228. Springer","DOI":"10.1007\/11889205_17"},{"key":"2327_CR38","doi-asserted-by":"crossref","unstructured":"Wu Z, Pan S, Long G, Jiang J, Chang X, Zhang C (2020) Connecting the dots: Multivariate time series forecasting with graph neural networks. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp 753\u2013763","DOI":"10.1145\/3394486.3403118"},{"key":"2327_CR39","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/j.ins.2020.01.043","volume":"521","author":"H Peng","year":"2020","unstructured":"Peng H, Wang H, Du B, Bhuiyan MZA, Ma H, Liu J, Wang L, Yang Z, Du L, Wang S (2020) Spatial temporal incidence dynamic graph neural networks for traffic flow forecasting. Inform Sci 521:277\u2013290","journal-title":"Inform Sci"},{"issue":"3","key":"2327_CR40","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1109\/TITS.2019.2900481","volume":"21","author":"B Du","year":"2019","unstructured":"Du B, Peng H, Wang S, Bhuiyan MZA, Wang L, Gong Q, Liu L, Li J (2019) Deep irregular convolutional residual lstm for urban traffic passenger flows prediction. IEEE Trans Intell Transp Syst 21(3):972\u2013985","journal-title":"IEEE Trans Intell Transp Syst"},{"key":"2327_CR41","doi-asserted-by":"crossref","unstructured":"Zou D, Wang S, Li X, Peng H, Wang Y, Liu C, Sheng K, Zhang B (2024) Multispans: a multi-range spatial-temporal transformer network for traffic forecast via structural entropy optimization. In: Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pp 1032\u20131041","DOI":"10.1145\/3616855.3635820"}],"container-title":["International Journal of Machine Learning and Cybernetics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13042-024-02327-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13042-024-02327-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13042-024-02327-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T10:40:41Z","timestamp":1738665641000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13042-024-02327-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,31]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["2327"],"URL":"https:\/\/doi.org\/10.1007\/s13042-024-02327-9","relation":{},"ISSN":["1868-8071","1868-808X"],"issn-type":[{"type":"print","value":"1868-8071"},{"type":"electronic","value":"1868-808X"}],"subject":[],"published":{"date-parts":[[2024,8,31]]},"assertion":[{"value":"19 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2024","order":3,"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 they have no financial interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"No organization that may gain or lose financially through publication of this manuscript.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed consent"}}]}}