{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:41Z","timestamp":1750309361232,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,8,24]],"date-time":"2024-08-24T00:00:00Z","timestamp":1724457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Science and Technology Project of State Grid: Research on artificial intelligence analysis technology of available transmission capacity (ATC) of the key section under multiple power grid operation modes","award":["5100-202255020A-1-1-ZN"],"award-info":[{"award-number":["5100-202255020A-1-1-ZN"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,8,25]]},"DOI":"10.1145\/3637528.3671704","type":"proceedings-article","created":{"date-parts":[[2024,8,25]],"date-time":"2024-08-25T04:54:55Z","timestamp":1724561695000},"page":"1921-1932","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-0012-9624","authenticated-orcid":false,"given":"Huaiyuan","family":"Liu","sequence":"first","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-9758-976X","authenticated-orcid":false,"given":"Xianzhang","family":"Liu","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6102-1804","authenticated-orcid":false,"given":"Donghua","family":"Yang","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7521-2871","authenticated-orcid":false,"given":"Hongzhi","family":"Wang","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6622-0545","authenticated-orcid":false,"given":"Yingchi","family":"Long","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8408-4472","authenticated-orcid":false,"given":"Mengtong","family":"Ji","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9370-7088","authenticated-orcid":false,"given":"Dongjing","family":"Miao","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0083-2547","authenticated-orcid":false,"given":"Zhiyu","family":"Liang","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,24]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"International Conference on Learning Representations.","author":"Amizadeh Saeed","year":"2018","unstructured":"Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. 2018. Learning to solve circuit-sat: An unsupervised differentiable approach. In International Conference on Learning Representations."},{"key":"e_1_3_2_2_2_1","volume-title":"PDP: A general neural framework for learning constraint satisfaction solvers. arXiv preprint arXiv:1903.01969","author":"Amizadeh Saeed","year":"2019","unstructured":"Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. 2019. PDP: A general neural framework for learning constraint satisfaction solvers. arXiv preprint arXiv:1903.01969 (2019)."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i03.5612"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/21M146199X"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2012.2211477"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21895"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.67327"},{"key":"e_1_3_2_2_8_1","unstructured":"Miller R. E. and Muller D. E. 1960. A problem of maximum consistent subsets. IBM Research Report RC-240. JT Watson Research Center Yorktown Heights NY."},{"key":"e_1_3_2_2_9_1","series-title":"SIAM Journal on optimization","volume-title":"Network design using cut inequalities","author":"Barahona F.","year":"1996","unstructured":"Barahona F. 1996. Network design using cut inequalities. SIAM Journal on optimization, Vol. 6, 3 (1996), 823--837."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.36.3.493"},{"key":"e_1_3_2_2_11_1","volume-title":"Ilmenau (","author":"Der Handlungsreisende Voigt B. F.","year":"1831","unstructured":"Voigt B. F. 1831. Der Handlungsreisende, wie er sein soll und was er zu thun hat, um Auftr\u00e4ge zu erhalten und eines gl\u00fccklichen Erfolgs in seinen Gesch\u00e4ften gewiss zu sein. Commis-Voageur, Ilmenau ( 1831), 69--72."},{"key":"e_1_3_2_2_12_1","volume-title":"Dynamic Approximate Maximum Independent Set on Massive Graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE","author":"Gao Xiangyu","year":"2022","unstructured":"Xiangyu Gao, Jianzhong Li, and Dongjing Miao. 2022. Dynamic Approximate Maximum Independent Set on Massive Graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 1835--1847."},{"key":"e_1_3_2_2_13_1","volume-title":"Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems","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, Vol. 32 (2019)."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-023-00218-7"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2006.377282"},{"key":"e_1_3_2_2_16_1","volume-title":"Proceedings of the 14th International Symposiumon Parameterized and Exact Computation (IPEC","author":"Duarte G.L.","year":"2019","unstructured":"Duarte G.L., Lokshtanov D., Pedrosa L.L.C., Schouery R.C.S., and Souza U.S. 2019. Computing the largest bond of a graph. In Proceedings of the 14th International Symposiumon Parameterized and Exact Computation (IPEC 2019). 12:1--12:15."},{"key":"e_1_3_2_2_17_1","volume-title":"Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing. 422--431","author":"Williamson D. P.","year":"1994","unstructured":"Williamson D. P. Goemans M. X. 1994. . 879-approximation algorithms for max cut and max 2sat. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing. 422--431."},{"key":"e_1_3_2_2_18_1","volume-title":"Parameterized Algorithms for Maximum Cut with Connectivity Constraints. In 14th International Symposium on Parameterized and Exact Computation (IPEC","volume":"148","author":"Eto","year":"2019","unstructured":"Eto H., Hanaka T., Kobayashi K., and Kobayashi Y. 2019b. Parameterized Algorithms for Maximum Cut with Connectivity Constraints. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Vol. 148. 13:1--13:15."},{"key":"e_1_3_2_2_19_1","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR","author":"Lange J. H.","year":"2019","unstructured":"Lange J. H., Andres B., and Swoboda P. 2019a. Combinatorial persistency criteria for multicut and max-cut. In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR 2019). 6093--6102."},{"volume-title":"Matrix analysis","author":"Horn Roger A","key":"e_1_3_2_2_20_1","unstructured":"Roger A Horn and Charles R Johnson. 2012. Matrix analysis. Cambridge university press."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2017.0798"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00284-2"},{"key":"e_1_3_2_2_23_1","first-page":"6659","article-title":"Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs","volume":"33","author":"Karalias Nikolaos","year":"2020","unstructured":"Nikolaos Karalias and Andreas Loukas. 2020. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, Vol. 33 (2020), 6659--6672.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_2_24_1","unstructured":"Kristian Kersting Nils M. Kriege Christopher Morris Petra Mutzel and Marion Neumann. 2016. Benchmark Data Sets for Graph Kernels. http:\/\/graphkernels.cs.tu-dortmund.de"},{"key":"e_1_3_2_2_25_1","volume-title":"Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems","author":"Khalil Elias","year":"2017","unstructured":"Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. 2017. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, Vol. 30 (2017)."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i9.21262"},{"key":"e_1_3_2_2_27_1","unstructured":"Jon Kleinberg and Eva Tardos. 2006. Algorithm design. Pearson Education India."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00789-1"},{"key":"e_1_3_2_2_29_1","first-page":"26198","article-title":"Learning to delegate for large-scale vehicle routing","volume":"34","author":"Li Sirui","year":"2021","unstructured":"Sirui Li, Zhongxia Yan, and Cathy Wu. 2021. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, Vol. 34 (2021), 26198--26211.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_2_30_1","volume-title":"Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems","author":"Li Zhuwen","year":"2018","unstructured":"Zhuwen Li, Qifeng Chen, and Vladlen Koltun. 2018. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems, Vol. 31 (2018)."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"e_1_3_2_2_33_1","first-page":"22713","article-title":"Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem","volume":"35","author":"Min Yimeng","year":"2022","unstructured":"Yimeng Min, Frederik Wenkel, Michael Perlmutter, and Guy Wolf. 2022. Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem? Advances in Neural Information Processing Systems, Vol. 35 (2022), 22713--22724.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_2_34_1","unstructured":"Garey M.R. and Johnson D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness."},{"key":"e_1_3_2_2_35_1","volume-title":"Recurrent relational networks. Advances in neural information processing systems","author":"Palm Rasmus","year":"2018","unstructured":"Rasmus Palm, Ulrich Paquet, and Ole Winther. 2018. Recurrent relational networks. Advances in neural information processing systems, Vol. 31 (2018)."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/100348.100380"},{"key":"e_1_3_2_2_37_1","volume-title":"International Conference on Learning Representations.","author":"Poganvci\u0107 Marin Vlastelica","year":"2019","unstructured":"Marin Vlastelica Poganvci\u0107, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. 2019. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations."},{"volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"Diestel R.","key":"e_1_3_2_2_38_1","unstructured":"Diestel R. 2017. Graph Theory. Graduate Texts in Mathematics, Vol. 173. Springer-Verlag, Berlin, Germany."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1145963"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.03.020"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-022-00198-0"},{"key":"e_1_3_2_2_42_1","volume-title":"Unsupervised Learning for Combinatorial Optimization Needs Meta Learning. In The Eleventh International Conference on Learning Representations.","author":"Wang Haoyu Peter","year":"2023","unstructured":"Haoyu Peter Wang and Pan Li. 2023. Unsupervised Learning for Combinatorial Optimization Needs Meta Learning. In The Eleventh International Conference on Learning Representations."},{"key":"e_1_3_2_2_43_1","first-page":"31444","article-title":"Unsupervised learning for combinatorial optimization with principled objective relaxation","volume":"35","author":"Wang Haoyu Peter","year":"2022","unstructured":"Haoyu Peter Wang, Nan Wu, Hang Yang, Cong Hao, and Pan Li. 2022. Unsupervised learning for combinatorial optimization with principled objective relaxation. Advances in Neural Information Processing Systems, Vol. 35 (2022), 31444--31458.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_2_44_1","volume-title":"International Conference on Machine Learning. PMLR, 6545--6554","author":"Wang Po-Wei","year":"2019","unstructured":"Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. 2019. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning. PMLR, 6545--6554."},{"key":"e_1_3_2_2_45_1","first-page":"7472","article-title":"NeuroLKH: Combining deep learning model with Lin-Kernighan-Helsgaun heuristic for solving the traveling salesman problem","volume":"34","author":"Xin Liang","year":"2021","unstructured":"Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. 2021. NeuroLKH: Combining deep learning model with Lin-Kernighan-Helsgaun heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, Vol. 34 (2021), 7472--7483.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783417"},{"volume-title":"Wavelets and Sparsity XVIII","author":"Yao Weichi","key":"e_1_3_2_2_47_1","unstructured":"Weichi Yao, Afonso S Bandeira, and Soledad Villar. 2019. Experimental performance of graph neural networks on random instances of max-cut. In Wavelets and Sparsity XVIII, Vol. 11138. SPIE, 242--251."},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i12.17283"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2021.1064"},{"key":"e_1_3_2_2_50_1","volume-title":"2007 IEEE 23rd International Conference on Data Engineering. IEEE, 1247--1249","author":"Zhang Shijie","year":"2006","unstructured":"Shijie Zhang, Jiong Yang, and VenuMadhav Cheedella. 2006. Monkey: Approximate graph mining based on spanning trees. In 2007 IEEE 23rd International Conference on Data Engineering. IEEE, 1247--1249."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403154"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i14.17476"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijepes.2020.106362"}],"event":{"name":"KDD '24: The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"],"location":"Barcelona Spain","acronym":"KDD '24"},"container-title":["Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3637528.3671704","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3637528.3671704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:00Z","timestamp":1750291560000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3637528.3671704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,24]]},"references-count":52,"alternative-id":["10.1145\/3637528.3671704","10.1145\/3637528"],"URL":"https:\/\/doi.org\/10.1145\/3637528.3671704","relation":{},"subject":[],"published":{"date-parts":[[2024,8,24]]},"assertion":[{"value":"2024-08-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}