A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks

Yaochu Jin , Xueming Yan , Shiqing Liu , Xiangyu Wang

Engineering ›› : 202506047

PDF (1820KB)
Engineering ›› :202506047 DOI: 10.1016/j.eng.2025.06.047
research-article
A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks
Author information +
History +
PDF (1820KB)

Abstract

Graph neural networks (GNNs) have emerged as powerful tools for solving combinatorial optimization problems (COPs), exhibiting state-of-the-art performance in both graph-structured and non-graph-structured domains. However, existing approaches lack a unified framework capable of addressing a wide range of COPs. After presenting a summary of representative COPs and a brief review of recent advancements in GNNs for solving COPs, this paper proposes a unified framework for solving COPs based on GNNs, including graph representation of COPs, the equivalent conversion of non-graph-structured COPs to graph-structured COPs, graph decomposition, and graph simplification. The proposed framework leverages the ability of GNNs to effectively capture relational information and extract features from graph representations of COPs, offering a generic solution to COPs that can address the limitations of the state of the art in solving non-graph-structured and highly complex graph-structured COPs.

Keywords

Combinatorial optimization / Graph representation / Equivalent conversion / Graph decomposition / Graph simplification

Cite this article

Download citation ▾
Yaochu Jin, Xueming Yan, Shiqing Liu, Xiangyu Wang. A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks. Engineering 202506047 DOI:10.1016/j.eng.2025.06.047

登录浏览全文

4963

注册一个新账户 忘记密码

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]

Bengio Y, Lodi A, Prouvost A . Machine learning for combinatorial optimization: a methodological tour d’horizon. Eur J Oper Res 2021; 290(2): 405-21.
[2]

Jiang M, Shan K, He C, Li C . Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar. Nat Commun 2023; 14: 5927.
[3]

Yin X, Qian Y, Vardar A, Günther M, Müller F, Laleni N, et al. Ferroelectric compute-in-memory annealer for combinatorial optimization problems. Nat Commun 2024; 15: 2419.
[4]

Cautereels C, Smets J, Bircham P, De Ruysscher D, Zimmermann A, De Rijk P, et al. Combinatorial optimization of gene expression through recombinase-mediated promoter and terminator shuffling in yeast. Nat Commun 2024; 15: 1112.
[5]

Ising machines offer an optimized solution. Nat Electron 2023; 6(10): 717.
[6]

Si J, Yang S, Cen Y, Chen J, Huang Y, Yao Z, et al. Energy-efficient superparamagnetic Ising machine and its application to traveling salesman problems. Nat Commun 2024; 15: 3457.
[7]

Wang R, Wang G, Sun J, Deng F, Chen J. Flexible job shop scheduling via dual attention network-based reinforcement learning. IEEE Trans Neural Netw Learn Syst 2023; 35(3): 3091-102.
[8]

Min Y, Bai Y, Gomes CP . Unsupervised learning for solving the travelling salesman problem. In: Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, editors. Proceedings of the 37th International Conference on Neural Information Processing Systems; 2023 Dec 10-16; New Orleans, LA, USA. Red Hook: Curran Associates, Inc.; 2023. p. 47264-78.
[9]

Jiang Y, Zhan ZH, Tan KC, Zhang J . A bi-objective knowledge transfer framework for evolutionary many-task optimization. IEEE Trans Evol Comput 2022; 27(9): 1514-28.
[10]

Zhang X, Liu S, Zhao Z, Yang S . A decomposition-based evolutionary algorithm with clustering and hierarchical estimation for multi-objective fuzzy flexible jobshop scheduling. IEEE Trans Evol Comput 2026; 30(1): 2-15.
[11]

Sato R. A survey on the expressive power of graph neural networks. 2020. arXiv:2003.04078.
[12]

Zhou J, Cui G, Hu S, Zhang Z, Yang C, Liu Z, et al. Graph neural networks: a review of methods and applications. AI Open 2020; 1: 57-81.
[13]

Asif NA, Sarker Y, Chakrabortty RK, Ryan MJ, Ahamed MH, Saha DK, et al. Graph neural network: a comprehensive review on non-Euclidean space. IEEE Access 2021; 9: 60588-606.
[14]

Vesselinova N, Steinert R, Perez-Ramirez DF, Boman M . Learning combinatorial optimization on graphs: a survey with applications to networking. IEEE Access 2020; 8: 120388-416.
[15]

Huang T, Ma Y, Zhou Y, Huang H, Chen D, Gong Z, et al. A review of combinatorial optimization with graph neural networks. In: Proceedings of 2019 5th International Conference on Big Data and Information Analytics; 2019 Jul 8-10; Kunming, China. Piscataway: IEEE; 2019. p. 72-7.
[16]

Peng Y, Choi B, Xu J . Graph learning for combinatorial optimization: a survey of state-of-the-art. Data Sci Eng 2021; 6(2): 119-41.
[17]

Meyer U, Sanders P . δ-stepping: a parallel single source shortest path algorithm. In: Bilardi G, Italiano GF, Pietracaprina A, Pucci G, editors. Algorithms-ESA’98. Proceedings of the 6th Annual European Symposium; 1998 Aug 24-26; Venice, Italy. Berlin: Springer; 1998. p. 393-404.
[18]

Seidel R. On the all-pairs-shortest-path problem in unweighted undirected graphs. J Comput Syst Sci 1995; 51(3): 400- 3.
[19]

Katoh N, Ibaraki T, Mine H . An algorithm for finding K minimum spanning trees. SIAM J Comput 1981; 10(2): 247-55.
[20]

Eppstein D. Offline algorithms for dynamic minimum spanning tree problems. J Algorithms 1994; 17(2): 237-50.
[21]

Manerba D, Mansini R, Riera-Ledesma J . The traveling purchaser problem and its variants. Eur J Oper Res 2017; 259(1): 1-18.
[22]

Lin C. A vehicle routing problem with pickup and delivery time windows, and coordination of transportable resources. Comput Oper Res 2011; 38(11): 1596-609.
[23]

Mazzeo S, Loiseau I . An ant colony algorithm for the capacitated vehicle routing. Electron Notes Discrete Math 2004; 18: 181-6.
[24]

Yan X, Huang H, Hao Z, Wang J . A graph-based fuzzy evolutionary algorithm for solving two-echelon vehicle routing problems. IEEE Trans Evol Comput 2020; 24(1): 129-41.
[25]

Yan X, Jin Y, Ke X, Hao Z . Multi-task evolutionary optimization of multi-echelon location routing problems via a hierarchical fuzzy graph. Complex Intell Syst 2023; 9(6): 6845-62.
[26]

Sering L, Skutella M . Multi-source multi-sink Nash flows over time. 2018. arXiv:1807.01098.
[27]

Lahn N, Raghvendra S . A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings. 2019. arXiv:1903.10445.
[28]

Sotirov R. An efficient semidefinite programming relaxation for the graph partition problem. INFORMS J Comput 2014; 26(1): 16-30.
[29]

Yan X, Zhong G, Jin Y, Ke X, Xie F, Huang G . Binary spectral clustering for multi-view data. Inf Sci 2024; 677: 120899.
[30]

Hu X, Li J . Circular coloring and fractional coloring in planar graphs. J Graph Theory 2022; 99(2): 312-43.
[31]

Fomin FV, Golovach PA, Lokshtanov D, Saurabh S, Zehavi M . Clique-width III: Hamiltonian cycle and the odd case of graph coloring. ACM Trans Algorithms 2018; 15: 9.
[32]

Karp RM, Vazirani UV, Vazirani VV . An optimal algorithm for on-line bipartite matching. In: Ortiz H, editor. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing; 1990 May 13-17; Baltimore, MD, USA. New York City: Association for Computing Machinery; 1990. p. 352-8.
[33]

Iwama K, Miyazaki S . A survey of the stable marriage problem and its variants. In: Kurohashi S, editor. International Conference on Informatics Education and Research for Knowledge-Circulating Society (ICKS 2008); 2008 Jan 17; Kyoto, Japan. Piscataway: IEEE; 2008. p. 131-6.
[34]

Minieka E. The Chinese postman problem for mixed networks. Manage Sci 1979; 25(7): 643-8.
[35]

Tarjan RE, Trojanowski AE . Finding a maximum independent set. SIAM J Comput 1977; 6(3): 537-46.
[36]

Bomze IM, Budinich M, Pardalos PM, Pelillo M. The maximum clique problem. In: Du DZ, Pardalos PM, editors. Handbook of combinatorial optimization. Boston: Springer; 1999. p. 1-74.
[37]

Henning MA, Löwenstein C, Rautenbach D, Southey J . Disjoint dominating and total dominating sets in graphs. Discrete Appl Math 2010; 158(15): 1615-23.
[38]

Sunil Chandran L, Das A, Rajendraprasad D, Varma NM . Rainbow connection number and connected dominating sets. J Graph Theory 2012; 71(2): 206-18.
[39]

Zhou Z, Das S, Gupta H . Connected K-coverage problem in sensor networks. In: Proceedings of the 13th International Conference on Computer Communications and Networks; 2004 Oct 11-13; Chicago, IL, USA. Piscataway: IEEE; 2004. p. 373-8.
[40]

Chekuri C, Kumar A . Maximum coverage problem with group budget constraints and applications. In: Jansen K, Khanna S, Rolim JDP, Ron D, editors. Approximation, randomization and combinatorial optimization. Algorithms and techniques. Berlin: Springer; 2004. p. 72-83.
[41]

Liu S, Yan X, Jin Y. End-to-end Pareto set prediction with graph neural networks for multi-objective facility location. In: Emmerich M, Deutz A, Wang H, Kononova AV, Naujoks B, Li K, et al., editors. Evolutionary multi-criterion optimization: 12th international conference; 2023 Mar 20-24; Leiden, the Netherlands. Berlin: Springer; 2023. p. 147-61.
[42]

Heydaribeni N, Anastasopoulos A . Distributed mechanism design for network resource allocation problems. IEEE Trans Netw Sci Eng 2020; 7(2): 621-36.
[43]

Mohamaddiah MH, Abdullah A, Subramaniam S, Hussin M . A survey on resource allocation and monitoring in cloud computing. Int J Mach Learn Comput 2014; 4: 31-8.
[44]

Xie J, Gao L, Peng K, Li X, Li H . Review on flexible job shop scheduling. IET Coll Intel Manuf. 2019; 1(3): 67-77.
[45]

Dhiflaoui M, Nouri HE, Driss OB . Dual-resource constraints in classical and flexible job shop problems: a state-of-the-art review. Procedia Comput Sci 2018; 126: 1507-15.
[46]

Lodi A, Martello S, Monaci M, Vigo D . Two-dimensional bin packing problems. In: Paschos VT, editors. Paradigms of combinatorial optimization: problems and new approaches. Hoboken: John Wiley & Sons, Inc.; 2014. p. 107-29.
[47]

Martello S, Pisinger D, Vigo D. The three-dimensional bin packing problem. Oper Res 2000; 48(2): 256-67.
[48]

Kang J, Park S . Algorithms for the variable sized bin packing problem. Eur J Oper Res 2003; 147(2): 365-72.
[49]

Kellerer H, Pferschy U, Pisinger D . The bounded knapsack problem. In: Knapsack problems. Berlin: Springer; 2004. p. 185-209.
[50]

Andonov R, Poirriez V, Rajopadhye S . Unbounded knapsack problem: dynamic programming revisited. Eur J Oper Res 2000; 123(2): 394-407.
[51]

Cherri AC, Arenales MN, Yanasse HH, Poldi KC, Vianna ACG . The one-dimensional cutting stock problem with usable leftovers-a survey. Eur J Oper Res 2014; 236(2): 395-402.
[52]

Oliveira Ó, Gamboa D, Silva E . An introduction to the two-dimensional rectangular cutting and packing problem. Int Trans Oper Res 2023; 30(6): 3238-66.
[53]

Wu F, Duan J, Ai P, Chen Z, Yang Z, Zou X . Rachis detection and three-dimensional localization of cut off point for vision-based banana robot. Comput Electron Agric 2022; 198: 107079.
[54]

Golab L, Korn F, Li F, Saha B, Srivastava D . Size-constrained weighted set cover. In: Proceedings of 2015 IEEE 31st International Conference on Data Engineering; 2015 Apr 13-17; Seoul, Republic of Korea. Piscataway: IEEE; 2015. p. 879-90.
[55]

Indyk P, Mahabadi S, Rubinfeld R, Ullman J, Vakilian A, Yodpinyanee A. Fractional set cover in the streaming model. In: Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Wadern: Dagstuhl Publishing; 2017. p. 12.
[56]

De Moura L, Bjørner N . Satisfiability modulo theories: introduction and applications. Commun ACM 2011; 54(9): 69-77.
[57]

Narodytska N, Bacchus F . Maximum satisfiability using core-guided MaxSAT resolution. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence; 2014 Jul 27-31; Québec City, QC, Canada. Palo Alto: AAAI Press; 2014. p. 2717-23.
[58]

Beyersdorff O, Janota M, Lonsing F, Seidl M . Quantified Boolean formulas. In: Biere A, Heule M, van Maaren H, Walsh T, editors. Handbook of satisfiability. 2nd ed. Amsterdam: IOS Press; 2021. p. 1177-1221.
[59]

Galbrun E, Pelechrinis K, Terzi E . Urban navigation beyond shortest route: the case of safe paths. Inf Syst 2016; 57: 160-71.
[60]

Dang T, Mascarich F, Khattak S, Papachristos C, Alexis K . Graph-based path planning for autonomous robotic exploration in subterranean environments. In: Proceedings of 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems; 2019 Nov 3-8; Macao, China. Piscataway: IEEE; 2019. p. 3105-12.
[61]

Lu H, Li J, Guizani M . Secure and efficient data transmission for cluster-based wireless sensor networks. IEEE Trans Parallel Distrib Syst 2013; 25: 750-61.
[62]

Kumar K. Technology for supporting supply chain management: introduction. Commun ACM 2001; 44(6): 58-61.
[63]

Zetina CA, Contreras I, Fernández E, Luna-Mota C . Solving the optimum communication spanning tree problem. Eur J Oper Res 2019; 273(1): 108-17.
[64]

Gamayanti N, Alkaff A, Mangatas R . Optimisasi multi depot vehicle routing problem (MDVRP) dengan variabel travel time menggunakan algoritma particle swarm optimization. JAVA J Electr Electron Eng 2015; 13(1): 18-22. Indonesian.
[65]

Kucukoglu I, Dewil R, Cattrysse D . The electric vehicle routing problem and its variations: a literature review. Comput Ind Eng 2021; 161: 107650.
[66]

Schrijver A. On the history of the transportation and maximum flow problems. Math Program 2002; 91(3): 437-45.
[67]

Ciciriello P, Mottola L, Picco GP . Efficient routing from multiple sources to multiple sinks in wireless sensor networks. In: Langendoen K, Voigt T, editors. Wireless sensor networks. EWSN 2007. Berlin: Springer; 2007. p. 34-50.
[68]

Azad A, Buluç A, Pothen A . Computing maximum cardinality matchings in parallel on bipartite graphs via tree-grafting. IEEE Trans Parallel Distrib Syst 2017; 28(1): 44-59.
[69]

Ma X, Yan X, Liu J, Zhong G . Simultaneous multi-graph learning and clustering for multiview data. Inf Sci 2022; 593: 472-87.
[70]

Zhong G, Shu T, Huang G, Yan X. Multi-view spectral clustering by simultaneous consensus graph learning and discretization. Knowl Base Syst 2022; 235: 107632.
[71]

Maus Y. Distributed graph coloring made easy. ACM Trans Parallel C 2023; 10(4): 21.
[72]

Kierstead HA . A simple competitive graph coloring algorithm. J Comb Theory Ser B 2000; 78(1): 57-68.
[73]

Marx D. Complexity of clique coloring and related problems. Theor Comput Sci 2011; 412(29): 3487-500.
[74]

Rossi RA, Ahmed NK . Coloring large complex networks. Soc Netw Anal Min 2014; 4(1): 228.
[75]

Hajiaghayi M, Wijting C, Ribeiro C, Hajiaghayi MT . Efficient and practical resource block allocation for LTE-based D2D network via graph coloring. Wirel Netw 2014; 20(4): 611-24.
[76]

Bodlaender HL, Kolay S, Pieterse A . Parameterized complexity of conflict-free graph coloring. SIAM J Discrete Math 2021; 35(3): 2003-38.
[77]

Mohar B. Circular colorings of edge-weighted graphs. J Graph Theory 2003; 43(2): 107-16.
[78]

Jothiraj R, Jayakumar S, Venugopal P . Cyclic open shop scheduling in a paired triple connected dominator coloring of circular-arc graph. J Appl Sci Comput. 2019; 6: 675-80.
[79]

Tabi Z, El-Safty KH, Kallus Z, Hága P, Kozsik T, Glos A, et al. Quantum optimization for the graph coloring problem with space-efficient embedding. In: Proceedings of 2020 IEEE International Conference on Quantum Computing and Engineering; 2020 Oct 12-16; Denver, CO, USA. Piscataway: IEEE; 2020. p. 56-62.
[80]

Szachniuk M, Cristina De Cola M, Felici G, Blazewicz J . The orderly colored longest path problem-a survey of applications and new algorithms. RAIRO-Oper Res 2014; 48(1): 25-51.
[81]

Wang R, Yan J, Yang X . Neural graph matching network: learning Lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching. IEEE Trans Pattern Anal Mach Intell 2021; 44: 5261-79.
[82]

Gaspars-Wieloch H. The assignment problem in human resource project management under uncertainty. Risks 2021; 9(1): 25.
[83]

Xu X, Hao J, Yu L, Deng Y . Fuzzy optimal allocation model for task-resource assignment problem in a collaborative logistics network. IEEE Trans Fuzzy Syst 2019; 27(5): 1112-25.
[84]

Grötschel M, Yuan YX. Euler, Mei-ko Kwan, Königsberg, and a Chinese postman. In: Grötschel M, editor. Optimization stories: 21st International Symposium on Mathematical Programming; 2012 Aug 19-24; Berlin, Germany. Berlin: EMS Press; 2012. p. 43-50.
[85]

Çomaklı Sökmen Ö, Emeç Ş, Yilmaz M, Akkaya G . An overview of Chinese postman problem. In: Proceedings of the 3rd International Conference on Advanced Engineering Technologies; 2019 Sep 19-21; Erzurum, Turkey. Bayburt: Bayburt University; 2019. p. 1219-28.
[86]

Jiang H, Talebi AA, Shao Z, Sadati SH, Rashmanlou H . New concepts of vertex covering in cubic graphs with its applications. Mathematics 2022; 10(3): 307.
[87]

Hedar AR, Ismail R, El-Sayed GA, Khayyat KMJ . Two meta-heuristics designed to solve the minimum connected dominating set problem for wireless networks design and management. J Netw Syst Manage 2019; 27(3): 647-87.
[88]

Yu J, Wang N, Wang G, Yu D . Connected dominating sets in wireless ad hoc and sensor networks-a comprehensive survey. Comput Commun 2013; 36(2): 121-34.
[89]

Fagerholt K, Christiansen M . A combined ship scheduling and allocation problem. J Oper Res Soc 2000; 51(7): 834-42.
[90]

Bouajaja S, Dridi N . A survey on human resource allocation problem and its applications. Oper Res 2017; 17: 339-69.
[91]

Applegate D, Cook W . A computational study of the job-shop scheduling problem. ORSA J Comput 1991; 3(2): 149-56.
[92]

Katoh N, Ibaraki T . Resource allocation problems. In: Du DZ, Pardalos PM, editors. Handbook of combinatorial optimization. Boston: Springer; 1998. p. 905-1006.
[93]

Monma CL, Schrijver A, Todd MJ, Wei VK . Convex resource allocation problems on directed acyclic graphs: duality, complexity, special cases, and extensions. Math Oper Res 1990; 15(4): 736-48.
[94]

Destouet C, Tlahig H, Bettayeb B, Mazari B . Flexible job shop scheduling problem under Industry 5.0: a survey on human reintegration, environmental consideration and resilience improvement. J Manuf Syst 2023; 67: 155-73.
[95]

Leao AA, Toledo FM, Oliveira JF, Carravilla MA, Alvarez-Valdés R . Irregular packing problems: a review of mathematical models. Eur J Oper Res 2020; 282(3): 803-22.
[96]

Lodi A, Martello S, Vigo D . Recent advances on two-dimensional bin packing problems. Discrete Appl Math 2002; 123(1-3): 379-96.
[97]

Chu PC, Beasley JE . A genetic algorithm for the multidimensional knapsack problem. J Heuristics 1998; 4(1): 63-86.
[98]

Munien C, Ezugwu AE . Metaheuristic algorithms for one-dimensional bin-packing problems: a survey of recent advances and applications. J Intell Inf Syst 2021; 30(1): 636-63.
[99]

Seiden SS. On the online bin packing problem. J Assoc Comput Mach 2002; 49(5): 640-71.
[100]

Ross KW, Tsang DH . The stochastic knapsack problem. IEEE Trans Commun 1989; 37(7): 740- 7.
[101]

Fréville A. The multidimensional 0-1 knapsack problem: an overview. Eur J Oper Res 2004; 155(1): 1-21.
[102]

Liu J, Zhang K, Yan X, Zhang Q . A configuration space evolutionary algorithm with local minimizer for weighted circles packing problem. Expert Syst Appl 2024; 238: 121768.
[103]

Chen Y, Song X, Ouelhadj D, Cui Y . A heuristic for the skiving and cutting stock problem in paper and plastic film industries. Int Trans Oper Res 2019; 26(1): 157-79.
[104]

Delorme M, Iori M . Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS J Comput 2020; 32(1): 101-19.
[105]

Caprara A, Toth P, Fischetti M . Algorithms for the set covering problem. Ann Oper Res 2000; 98(1-4): 353-71.
[106]

Marchiori E, Steenbeek A. An evolutionary algorithm for large scale set covering problems with application to airline crew scheduling. In: Cagnoni S, editor. Real-world applications of evolutionary computing. EvoWorkshops 2000. Berlin: Springer; 2000. p. 370-84.
[107]

Liu H, Xing K, Zhou M, Han L, Wang F. Transition cover-based design of Petri net controllers for automated manufacturing systems. IEEE Trans Syst Man Cybern Syst 2014; 44(2): 196-208.
[108]

Owais M, Osman MK, Moussa G . Multi-objective transit route network design as set covering problem. IEEE Trans Intell Transp Syst 2016; 17(3): 670-9.
[109]

Zamani H, Dumais S, Craswell N, Bennett P, Lueck G. Generating clarifying questions for information retrieval. In: Huang Y, King I, Liu TY, van Steen M, editors. Proceedings of the Web Conference 2020; 2020 Apr 20-24; Taipei, China. New York City: Association for Computing Machinery; 2020. p. 418-28.
[110]

Marques-Silva J. Practical applications of Boolean Satisfiability. In: Proceedings of 2008 9th International Workshop on Discrete Event Systems; 2008 May 28-30; Gothenburg, Sweden. Piscataway: IEEE; 2008. p. 74-80.
[111]

Nguyen AHN, Aono M, Hara-Azumi Y . FPGA-based hardware/software co-design of a bio-inspired SAT solver. IEEE Access 2020; 8: 49053-65.
[112]

Lynce I, Marques-Silva J . SAT in bioinformatics: making the case with haplotype inference. In: Biere A, Gomes CP, editors. Theory and applications of satisfiability testing-SAT 2006. Berlin: Springer; 2006. p. 136-41.
[113]

Cambria E, White B . Jumping NLP curves: a review of natural language processing research. IEEE Comput Intell Mag 2014; 9(2): 48-57.
[114]

Li Z, Liu F, Yang W, Peng S, Zhou J . A survey of convolutional neural networks: analysis, applications, and prospects. IEEE Trans Neural Netw Learn Syst 2021; 33(12): 6999-7019.
[115]

Park J, Chun J, Kim SH, Kim Y, Park J . Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. Int J Prod Res 2021; 59(11): 3360-77.
[116]

Wang X, Huang T, Wang D, Yuan Y, Liu Z, He X, et al. Learning intents behind interactions with knowledge graph for recommendation. In: Proceedings of the Web Conference 2021; 2021 Apr 19-23; Ljubljana, Slovenia. New York City: Association for Computing Machinery; 2021. p. 878-87.
[117]

La Gatta V, Moscato V, Postiglione M, Sperli G . An epidemiological neural network exploiting dynamic graph structured data applied to the COVID-19 outbreak. IEEE Trans Big Data 2021; 7(1): 45-55.
[118]

Cui P, Wang X, Pei J, Zhu W. A survey on network embedding. IEEE Trans Knowl Data Eng 2019; 31(5): 833-52.
[119]

Zhang D, Yin J, Zhu X, Zhang C . Network representation learning: a survey. IEEE Trans Big Data 2020; 6(1): 3-28.
[120]

Perozzi B, Al-Rfou R, Skiena S . DeepWalk: online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2014 Aug 24-27; New York City, NY, USA. New York City: Association for Computing Machinery; 2014. p. 701-10.
[121]

Mikolov T, Chen K, Corrado G, Dean J . Efficient estimation of word representations in vector space. 2013. arXiv:1301.3781
[122]

Grover A, Leskovec J . node2vec: scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2016 Aug 13-17; San Francisco, CA, USA. New York City: Association for Computing Machinery; 2016. p. 855-64.
[123]

Li J, Zhu J, Zhang B . Discriminative deep random walk for network classification. In: Erk K, Smith NA, editors. Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics; 2016 Aug 7-12; Berlin, Germany. Kerrville: Association for Computational Linguistics; 2016. p. 1004-13.
[124]

Chen J, Zhang Q, Huang X . Incorporate group information to enhance network embedding. In: Proceedings of the 25th ACM International Conference on Information and Knowledge Management; 2016 Oct 24-28; Indianapolis, IN, USA. New York City: Association for Computing Machinery; 2016. p. 1901-4.
[125]

Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q . LINE: large-scale information network embedding. In: Proceedings of the 24th International Conference on World Wide Web; 2015 May 18-22; Florence, Italy. New York City: Association for Computing Machinery; 2015. p. 1067-77.
[126]

Zhang D, Yin J, Zhu X, Zhang C . Collective classification via discriminative matrix factorization on sparsely labeled networks. In: Proceedings of the 25th ACM International Conference on Information and Knowledge Management; 2016 Oct 24-28; Indianapolis, IN, USA. New York City: Association for Computing Machinery; 2016. p. 1563-72.
[127]

Lü L, Zhou T. Link prediction in complex networks: a survey. Physica A 2011; 390(6): 1150-70.
[128]

Zhang C, Zhang K, Yuan Q, Peng H, Zheng Y, Hanratty T, et al. Regions, periods, activities: uncovering urban dynamics via cross-modal representation learning. In: Proceedings of the 26th International Conference on World Wide Web; 2017 Apr 3-7; Perth, WA, Australia. New York City: Association for Computing Machinery; 2017. p. 361-70.
[129]

Tang J, Liu J, Zhang M, Mei Q . Visualizing large-scale and high-dimensional data. In: Proceedings of the 25th International Conference on World Wide Web; 2016 Apr 11-15; Montréal, QC, Canada. New York City: Association for Computing Machinery; 2016. p. 287-97.
[130]

Scarselli F, Gori M, Tsoi AC, Hagenbuchner M, Monfardini G . The graph neural network model. IEEE Trans Neural Netw 2009; 20(1): 61-80.
[131]

Micheli A. Neural network for graphs: a contextual constructive approach. IEEE Trans Neural Netw 2009; 20(3): 498-511.
[132]

Gallicchio C, Micheli A . Graph Echo State Networks. In: Proceedings of the 2010 International Joint Conference on Neural Networks; 2010 Jul 18-23; Barcelona, Spain. Piscataway: IEEE; 2010. p. 1-8.
[133]

Li Y, Tarlow D, Brockschmidt M, Zemel R . Gated graph sequence neural networks. 2015. arXiv:1511.05493.
[134]

Kipf TN, Welling M . Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th International Conference on Learning Representations; 2017.
[135]

Defferrard M, Bresson X, Vandergheynst P . Convolutional neural networks on graphs with fast localized spectral filtering. In: Lee DD, von Luxburg U, Garnett R, Sugiyama M, Guyon I, editors. Proceedings of the 30th International Conference on Neural Information Processing Systems; 2016 Dec 5-10; Barcelona, Spain. Red Hook: Curran Associates, Inc.; 2016. p. 3844-52.
[136]

Hamilton W, Ying Z, Leskovec J . Inductive representation learning on large graphs. In: von Luxburg U, Guyon I, Bengio S, Wallach H, Fergus R, editors. Proceedings of the 31st International Conference on Neural Information Processing Systems; 2017 Dec 4-9; Long Beach, CA, USA. Red Hook: Curran Associates, Inc.; 2017. p. 1025-35.
[137]

Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE . Neural message passing for quantum chemistry. In: Precup D, Teh YW, editors. Proceedings of the 34th International Conference on Machine Learning; 2017 Aug 6-11; Sydney, NSW, Australia. New York City: PMLR; 2017. p. 1263-72.
[138]

Veli?kovi? P, Cucurull G, Casanova A, Romero A, Lio P, Bengio Y. Graph attention networks. 2018. arXiv:1710.10903.
[139]

Levie R, Monti F, Bresson X, Bronstein MM . CayleyNets: graph convolutional neural networks with complex rational spectral filters. IEEE Trans Signal Process 2019; 67(1): 97-109.
[140]

Chami I, Ying Z, Ré C, Leskovec J . Hyperbolic graph convolutional neural networks. In: Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, editors. Proceedings of the 33rd International Conference on Neural Information Processing Systems; 2019 Dec 8-14; Vancouver, BC, Canada; Red Hook: Curran Associates, Inc.; 2019. p. 4868-79.
[141]

Xu K, Hu W, Leskovec J, Jegelka S. How powerful are graph neural networks? 2019. arXiv:1810.00826.
[142]

Bianchi FM, Grattarola D, Livi L, Alippi C . Graph neural networks with convolutional ARMA filters. IEEE Trans Pattern Anal Mach Intell 2021; 44: 3496-507.
[143]

Veličković P, Fedus W, Hamilton WL, Liò P, Bengio Y, Hjelm RD . Deep graph infomax. 2018. arXiv:1809.10341.
[144]

Gao H, Ji S . Graph U-Nets. In: Proceedings of the 36th International Conference on Machine Learning; 2019 Jun 9-15; Long Beach, CA, USA. New York City: PMLR; 2019. p. 2083-92.
[145]

Zeng H, Zhou H, Srivastava A, Kannan R, Prasanna V. GraphSAINT: graph sampling based inductive learning method. 2019. arXiv:1907.04931.
[146]

Liu M, Wang Z, Ji S . Non-local graph neural networks. IEEE Trans Pattern Anal Mach Intell. 2022; 44(12): 10270-6.
[147]

Zhong Z, Li CT, Pang J . Hierarchical message-passing graph neural networks. Data Min Knowl Discov 2023; 37(1): 381-408.
[148]

Zhu Z, Zhang Z, Xhonneux LP, Tang J . Neural Bellman-Ford networks: a general graph neural network framework for link prediction. Adv Neural Inf Process Syst 2021; 34: 29476-90.
[149]

Fan S, Wang X, Shi C, Cui P, Wang B . Generalizing graph neural networks on out-of-distribution graphs. IEEE Trans Pattern Anal Mach Intell 2023; 46(1): 322-37.
[150]

Luan S, Hua C, Lu Q, Zhu J, Zhao M, Zhang S, et al. Revisiting heterophily for graph neural networks. Adv Neural Inf Process Syst 2022; 35: 1362-75.
[151]

Feng J, Chen Y, Li F, Sarkar A, Zhang M . How powerful are K-hop message passing graph neural networks. Adv Neural Inf Process Syst 2022; 35: 4776-90.
[152]

Bouritsas G, Frasca F, Zafeiriou S, Bronstein MM . Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Trans Pattern Anal Mach Intell 2023; 45(1): 657-68.
[153]

Wu Z, Pan S, Long G, Jiang J, Chang X, Zhang C . Connecting the dots: multivariate time series forecasting with graph neural networks. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2020 Aug 23-27; San Diego, CA, USA. New York City: Association for Computing Machinery; 2020. p. 753-63.
[154]

Li M, Zhu Z . Spatial-temporal fusion graph neural networks for traffic flow forecasting. Proc Conf AAAI Artif Intell 2021; 35(5): 4189-96.
[155]

Chen J, Zheng L, Hu Y, Wang W, Zhang H, Hu X . Traffic flow matrix-based graph neural network with attention mechanism for traffic flow prediction. Inf Fusion 2024; 104: 102146.
[156]

Jin W, Ma Y, Liu X, Tang X, Wang S, Tang J . Graph structure learning for robust graph neural networks. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2020 Aug 23-27; San Diego, CA, USA. New York City: Association for Computing Machinery; 2020. p. 66-74.
[157]

Gasteiger J, Becker F, Günnemann S . GemNet: universal directional graph neural networks for molecules. Adv Neural Inf Process Syst 2021; 34: 6790-802.
[158]

Réau M, Renaud N, Xue LC, Bonvin AM . DeepRank-GNN: a graph neural network framework to learn patterns in protein-protein interfaces. Bioinformatics 2023; 39(1): btac759.
[159]

Truong-Quoc C, Lee JY, Kim KS, Kim DN . Prediction of DNA origami shape using graph neural network. Nat Mater 2024; 23(7): 984-2.
[160]

Chen H, Bei Y, Shen Q, Xu Y, Zhou S, Huang W, et al. Macro graph neural networks for online billion-scale recommender system. 2024. arXiv:2401.14939.
[161]

Gu Y, Peng S, Li Y, Gao L, Dong Y . FC-HGNN: a heterogeneous graph neural network based on brain functional connectivity for mental disorder identification. Inf Fusion 2025; 113: 102619.
[162]

Chen LY, Li YP . Uncertainty quantification with graph neural networks for efficient molecular design. Nat Commun 2025; 16: 3262.
[163]

Chen S, Liu Y, Zhang Q, Shao Z, Wang Z . Multi-distance spatial-temporal graph neural network for anomaly detection in blockchain transactions. Adv Intell Syst 2025; 7(8): 2400898.
[164]

Simonovsky M, Komodakis N . GraphVAE: towards generation of small graphs using variational autoencoders. In: Kůrková V, Manolopoulos Y, Hammer B, Iliadis L, Maglogiannis I, editors. Artificial neural networks and machine learning-ICANN 2018. Cham: Springer; 2018. p. 412-22.
[165]

You J, Ying R, Ren X, Hamilton W, Leskovec J . GraphRNN: generating realistic graphs with deep auto-regressive models. In: Proceedings of the 35th International Conference on Machine Learning; 2018 Jul 10-15; Stockholm, Sweden. New York City: PMLR; 2018. p. 5708-17.
[166]

Chen Z, Mao H, Li H, Jin W, Wen H, Wei X, et al. Exploring the potential of large language models (LLMs) in learning on graphs. SIGKDD Explor 2024; 25(2): 42-61.
[167]

Zhu J, Rossi RA, Rao A, Mai T, Lipka N, Ahmed NK, et al. Graph neural networks with heterophily. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence; 2021 Feb 2-9; online conference. Palo Alto: AAAI Press; 2021. p. 11168-76.
[168]

Yang X, Yan M, Pan S, Ye X, Fan D . Simple and efficient heterogeneous graph neural network. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence; 2023 Feb 7-14; Washington, DC, USA. Palo Alto: AAAI Press; 2023. p. 10816-24.
[169]

Fu C, Zheng G, Huang C, Yu Y, Dong J . Multiplex heterogeneous graph neural network with behavior pattern modeling. In: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining; 2023 Aug 6-10; Long Beach, CA, USA. New York City: Association for Computing Machinery; 2023. p. 482-94.
[170]

Melton J, Krishnan S . muxGNN: multiplex graph neural network for heterogeneous graphs. IEEE Trans Pattern Anal Mach Intell 2023; 45(9): 11067-78.
[171]

Wang S, Li Y, Wang D, Zhang W, Chen X, Dong D, et al. Echo state graph neural networks with analogue random resistive memory arrays. Nat Mach Intell 2023; 5(2): 104-13.
[172]

Xue J, Jiang N, Liang S, Pang Q, Yabe T, Ukkusuri SV, et al. Quantifying the spatial homogeneity of urban road networks via graph neural networks. Nat Mach Intell 2022; 4(3): 246-57.
[173]

Wang Y, Wang J, Cao Z, Barati Farimani A . Molecular contrastive learning of representations via graph neural networks. Nat Mach Intell 2022; 4(3): 279-87.
[174]

Longa A, Azzolin S, Santin G, Cencetti G, Liò P, Lepri B, et al. Explaining the explainers in graph neural networks: a comparative study. ACM Comput Surv 2024; 57(5): 1-37.
[175]

Wang X, Yan X, Jin Y . A graph neural network with negative message passing and uniformity maximization for graph coloring. Complex Intell Syst 2024; 10(3): 4445-55.
[176]

Li X, Sun L, Ling M, Peng Y . A survey of graph neural network based recommendation in social networks. Neurocomputing 2023; 549: 126441.
[177]

Jiang W, Luo J . Graph neural network for traffic forecasting: a survey. Expert Syst Appl 2022; 207: 117921.
[178]

Zheng X, Liu Y, Pan S, Zhang M, Jin D, Yu PS . Graph neural networks for graphs with heterophily: a survey. 2022. arXiv:2202.07082.
[179]

Wu Z, Pan S, Chen F, Long G, Zhang C, Philip SY . A comprehensive survey on graph neural networks. IEEE Trans Neural Netw Learn Syst 2021; 32(1): 4-24.
[180]

Wu F, Souza A, Zhang T, Fifty C, Yu T, Weinberger K . Simplifying graph convolutional networks. In: Proceedings of the 36th International Conference on Machine Learning; 2019 Jun 9-15; Long Beach, CA, USA. New York City: PMLR; 2019. p. 6861-71.
[181]

Bo D, Wang X, Shi C, Shen H . Beyond low-frequency information in graph convolutional networks. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence; 2021 Feb 2-9; online conference. Palo Alto: AAAI Press; 2021. p. 3950-57.
[182]

Wei L, Zhao H, He Z . Learn layer-wise connections in graph neural networks. 2021. arXiv:2112.13585.
[183]

Pei H, Wei B, Chang KCC, Lei Y, Yang B . Geom-GCN: geometric graph convolutional networks. 2020. arXiv:2002.05287.
[184]

Chen Z, Wu Z, Lin Z, Wang S, Plant C, Guo W . AGNN: alternating graph-regularized neural networks to alleviate over-smoothing. IEEE Trans Neural Netw Learn Syst 2024; 35(10): 13764-76.
[185]

Wu Z, Jain P, Wright M, Mirhoseini A, Gonzalez JE, Stoica I . Representing long-range context for graph neural networks with global attention. Adv Neural Inf Process Syst 2021; 34: 13266-79.
[186]

Lin D, Lin J, Zhao L, Wang ZJ, Chen Z . Multilabel aerial image classification with a concept attention graph neural network. IEEE Trans Geosci Remote Sens 2021; 60: 1-12.
[187]

Zhang H, Bai L . Few-shot link prediction for temporal knowledge graphs based on time-aware translation and attention mechanism. Neural Netw 2023; 161: 371-81.
[188]

Wu W, Song C, Zhao J, Xu Z. Physics-informed gated recurrent graph attention unit network for anomaly detection in industrial cyber-physical systems. Inf Sci 2023; 629: 618-33.
[189]

Kong Z, Jin X, Xu Z, Zhang B . Spatio-temporal fusion attention: a novel approach for remaining useful life prediction based on graph neural network. IEEE Trans Instrum Meas 2022; 71: 1-12.
[190]

Sun Z, Yang Y . DIFUSCO: graph-based diffusion solvers for combinatorial optimization. Adv Neural Inf Process Syst 2024; 36: 3706-31.
[191]

Lemos H, Prates M, Avelar P, Lamb L. Graph colouring meets deep learning: effective graph neural network models for combinatorial problems. In: Proceedings of 2019 IEEE 31st International Conference on Tools with Artificial Intelligence; 2019 Nov 4-6; Portland, OR, USA. Piscataway: IEEE; 2019. p. 879-85.
[192]

Prates M, Avelar PH, Lemos H, Lamb LC, Vardi MY . Learning to solve NP-complete problems: a graph neural network for decision TSP. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence; 2019 Jan 27-Feb 1; Honolulu, HI, USA. Palo Alto: AAAI Press; 2019. p. 4731-8.
[193]

Li Y, Gu C, Dullien T, Vinyals O, Kohli P . Graph matching networks for learning the similarity of graph structured objects. In: Proceedings of the 36th International Conference on Machine Learning; 2019 Jun 9-15; Long Beach, CA, USA. New York City: PMLR; 2019. p. 3835-45.
[194]

Fey M, Lenssen JE, Morris C, Masci J, Kriege NM . Deep graph matching consensus. 2020. arXiv:2001.09621.
[195]

Bai Y, Ding H, Gu K, Sun Y, Wang W . Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence; 2020 Feb 7-12; New York City, NY, USA. Palo Alto, CA: AAAI Press; 2020. p. 3219-26.
[196]

Joshi CK, Laurent T, Bresson X . An efficient graph convolutional network technique for the travelling salesman problem. 2019. arXiv:1906.01227.
[197]

Xie Y, Xu Z, Zhang J, Wang Z, Ji S . Self-supervised learning of graph neural networks: a unified review. IEEE Trans Pattern Anal Mach Intell 2023; 45(2): 2412-29.
[198]

Mitton J, Senn HM, Wynne K, Murray-Smith R . A graph VAE and graph transformer approach to generating molecular graphs. 2021. arXiv:2104.04345.
[199]

Samanta B, De A, Jana G, Gómez V, Chattaraj PK, Ganguly N, et al. NEVAE: a deep generative model for molecular graphs. J Mach Learn Res 2020; 21(114): 4556-88.
[200]

Wang C, Pan S, Long G, Zhu X, Jiang J . MGAE: marginalized graph autoencoder for graph clustering. In: Proceedings of the 2017 ACM Conference on Information and Knowledge Management; 2017 Nov 6-10; Singapore, Singapore. New York City: Association for Computing Machinery; 2017. p. 889-98.
[201]

Park J, Lee M, Chang HJ, Lee K, Choi JY . Symmetric graph convolutional autoencoder for unsupervised graph representation learning. In: Proceedings of the IEEE/CVF International Conference on Computer Vision; 2019 Oct 27-Nov 2; Seoul, Republic of Korea. Piscataway: IEEE; 2019. p. 6519-28.
[202]

Li W, Li R, Ma Y, Chan SO, Pan D, Yu B . Rethinking graph neural networks for the graph coloring problem. 2022. arXiv:2208.06975.
[203]

Schuetz MJ, Brubaker JK, Zhu Z, Katzgraber HG . Graph coloring with physics-inspired graph neural networks. Phys Rev Res 2022; 4(4): 043131.
[204]

Wang X, Yan X, Jin Y . A graph neural network with negative message passing for graph coloring. 2023. arXiv:2301.11164.
[205]

Schuetz MJ, Brubaker JK, Katzgraber HG . Combinatorial optimization with physics-inspired graph neural networks. Nat Mach Intell 2022; 4(4): 367-77.
[206]

Tönshoff J, Ritzert M, Wolf H, Grohe M . Graph neural networks for maximum constraint satisfaction. Front Artif Intell 2021; 3: 580607.
[207]

Duan H, Vaezipoor P, Paulus MB, Ruan Y, Maddison C . Augment with care: contrastive learning for combinatorial problems. In: Proceedings of the 39th International Conference on Machine Learning; 2022 Jul 17-23; Baltimore, MD, USA. New York City: PMLR; 2022. p. 5627-42.
[208]

Xu H, Hui KH, Fu CW, Zhang H . TilinGNN: learning to tile with self-supervised graph neural network. ACM Tran Graphic 2020; 39(4): 129.
[209]

Kool W, Van Hoof H, Welling M . Attention, learn to solve routing problems! 2018. arXiv:1803.08475.
[210]

Nazari M, Oroojlooy A, Takác M, Snyder LV . Reinforcement learning for solving the vehicle routing problem. In: Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, editors. Proceedings of the 32nd International Conference on Neural Information Processing Systems; 2018 Dec 3-8; Montréal, QC, Canada. Red Hook: Curran Associates, Inc.; 2018. p. 9861-71.
[211]

Dai H, Khalil EB, Zhang Y, Dilkina B, Song L. Learning combinatorial optimization algorithms over graphs. In: von Luxburg U, Guyon I, Bengio S, Wallach H, Fergus R, editors. Proceedings of the 31st International Conference on Neural Information Processing Systems; 2017 Dec 4-9; Long Beach, CA, USA. Red Hook: Curran Associates, Inc.; 2017. p. 6351-61.
[212]

Tönshoff J, Kisin B, Lindner J, Grohe M . One model, Any CSP: graph neural networks as fast global search heuristics for constraint satisfaction. 2022. arXiv:2208.10227.
[213]

Blum C, Puchinger J, Raidl GR, Roli A . Hybrid metaheuristics in combinatorial optimization: a survey. Appl Soft Comput 2011; 11(6): 4135-51.
[214]

Dantzig G, Fulkerson R, Johnson S . Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 1954; 2(4): 393-410.
[215]

Savelsbergh M. A branch-and-price algorithm for the generalized assignment problem. Oper Res 1997; 45(6): 831-41.
[216]

Applegate DL, Bixby R E, Chvatál V, Cook WJ . The traveling salesman problem: a computational study. Princeton: Princeton University Press; 2011.
[217]

Helsgaun K. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University; 2017.
[218]

Helsgaun K. General k-opt submoves for the Lin-Kernighan TSP heuristic. Math Program Comput 2009; 1(2-3): 119-63.
[219]

Colorni A, Dorigo M, Maffioli F, Maniezzo V, Righini G, Trubian M . Heuristics from nature for hard combinatorial optimization problems. Int Trans Oper Res 1996; 3(1): 1-21.
[220]

Lawler EL, Wood DE . Branch-and-bound methods: a survey. Oper Res 1966; 14(4): 699-719.
[221]

Gauvin C, Desaulniers G, Gendreau M . A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands. Comput Oper Res 2014; 50: 141-53.
[222]

Reinelt G. TSPLIB-a traveling salesman problem library. ORSA J Comput 1991; 3(4): 376-84.
[223]

Gonçalves JF, Resende MG . Biased random-key genetic algorithms for combinatorial optimization. J Heuristics 2011; 17(5): 487-525.
[224]

Bertsimas D, Tsitsiklis J . Simulated annealing. Stat Sci 1993; 8(1): 10-5.
[225]

Slavík P. A tight analysis of the greedy algorithm for set cover. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing; 1996 May 22-24; Philadelphia, PA, USA. New York City: Association for Computing Machinery; 1996. p. 435-41.
[226]

Johnson DS . Local optimization and the traveling salesman problem. In: Paterson MS, editor. Automata, languages and programming. ICALP 1990. Berlin: Springer; 1990. p. 446-61.
[227]

Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur J Oper Res 2000; 126(1): 106-30.
[228]

Vinyals O, Fortunato M, Jaitly N . Pointer networks. In: Cortes C, Lee DD, Sugiyama M, Garnett R, editors. Proceedings of the 29th International Conference on Neural Information Processing Systems; 2015 Dec 7-12; Montréal, QC, Canada. Cambridge: MIT Press; 2015. p. 2692-700.
[229]

Bello I, Pham H, Le QV, Norouzi M, Bengio S . Neural combinatorial optimization with reinforcement learning. 2016. arXiv:1611.09940.
[230]

Ma Q, Ge S, He D, Thaker D, Drori I . Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. 2019. arXiv:1911.04936.
[231]

Wu Y, Song W, Cao Z, Zhang J, Lim A . Learning improvement heuristics for solving routing problems. IEEE Trans Neural Netw Learn Syst 2022; 33(9): 5057-69.
[232]

Grinsztajn N, Furelos-Blanco D, Surana S, Bonnet C, Barrett TD . Winner takes it all: training performant RL populations for combinatorial optimization. In: Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, editors. Proceedings of the 37th International Conference on Neural Information Processing Systems; 2023 Dec 10-16; New Orleans, LA, USA. Red Hook: Curran Associates, Inc.; 2023. p. 48485-509.
[233]

Selsam D, Lamm M, Bünz B, Liang P, de Moura L, Dill DL . Learning a SAT solver from single-bit supervision. 2018. arXiv:1802.03685.
[234]

Ireland D, Montana G . LeNSE: learning to navigate subgraph embeddings for large-scale combinatorial optimisation. In: Proceedings of the 39th International Conference on Machine Learning; 2022 Jul 17-23; Baltimore, MD, USA. New York City: PMLR; 2022. p. 9622-38.
[235]

Li Z, Chen Q, Koltun V . Combinatorial optimization with graph convolutional networks and guided tree search. In: Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, editors. Proceedings of the 32nd International Conference on Neural Information Processing Systems; 2018 Dec 3-8; Montréal, QC, Canada. Red Hook: Curran Associates, Inc.; 2018. p. 537-46.
[236]

Nowak A, Villar S, Bandeira AS, Bruna J. Revised note on learning quadratic assignment with graph neural networks. In: Proceedings of 2018 IEEE Data Science Workshop; 2018 Jun 4-6; Lausanne, Switzerland. Piscataway: IEEE; 2018. p. 1-5.
[237]

Manchanda S, Mittal A, Dhawan A, Medya S, Ranu S, Singh A . Learning heuristics over large graphs via deep reinforcement learning. 2019. arXiv:1903.03332.
[238]

Fu ZH, Qiu KB, Zha H . Generalize a small pre-trained model to arbitrarily large TSP instances. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence; 2021 Feb 2-9; online conference. Palo Alto: AAAI Press; 2021. p. 7474-82.
[239]

Deudon M, Cournut P, Lacoste A, Adulyasak Y, Rousseau LM . Learning heuristics for the TSP by policy gradient. In: van Hoeve WJ, editor. Integration of constraint programming, artificial intelligence, and operations research. CPAIOR 2018. Cham: Springer; 2018. p. 170-81.
[240]

Joshi CK, Cappart Q, Rousseau LM, Laurent T . Learning the travelling salesperson problem requires rethinking generalization. 2020. arXiv:2006.07054.
[241]

Dwivedi VP, Joshi CK, Luu AT, Laurent T, Bengio Y, Bresson X . Benchmarking graph neural networks. J Mach Learn Res 2023; 24: 1-48.
[242]

Hudson B, Li Q, Malencia M, Prorok A. Graph neural network guided local search for the traveling salesperson problem. 2021. arXiv:2110.05291.
[243]

Abe K, Xu Z, Sato I, Sugiyama M . Solving NP-hard problems on graphs with extended AlphaGo zero. 2019. arXiv:1905.11623.
[244]

Barrett T, Clements W, Foerster J, Lvovsky A. Exploratory combinatorial optimization with reinforcement learning. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence; 2020 Feb 7-12; New York City, NY, USA. Palo Alto: AAAI Press; 2020. p. 3243-50.
[245]

Ye H, Wang J, Cao Z, Liang H, Li Y. DeepACO: neural-enhanced ant systems for combinatorial optimization. In: Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, editors. Proceedings of the 37th International Conference on Neural Information Processing Systems; 2023 Dec 10-16; New Orleans, LA, USA. Red Hook: Curran Associates, Inc.; 2023. p. 43706-28.
[246]

Drakulic D, Michel S, Mai F, Sors A, Andreoli JM . BQ-NCO: Bisimulation Quotienting for efficient neural combinatorial optimization. In: Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, editors. Proceedings of the 37th International Conference on Neural Information Processing Systems; 2023 Dec 10-16; New Orleans, LA, USA. Red Hook: Curran Associates, Inc.; 2023. p. 77416-29.
[247]

You J, Wu H, Barrett C, Ramanujan R, Leskovec J . G2SAT: learning to generate SAT formulas. In: Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, editors. Proceedings of the 33rd International Conference on Neural Information Processing Systems; 2019 Dec 8-14; Vancouver, BC, Canada. Red Hook: Curran Associates, Inc.; 2019. p. 10553-10564
[248]

Li Z, Si X . NSNet: a general neural probabilistic framework for satisfiability problems. Adv Neural Inf Process Syst 2022; 35: 25573-85.
[249]

Sutskever I, Vinyals O, Le QV . Sequence to sequence learning with neural networks. Adv Neural Inf Process Syst 2014; 2: 3104-12.
[250]

Khoshraftar S, An A . A survey on graph representation learning methods. ACM Trans Intell Syst Technol 2024; 15(1): 19.
[251]

Guzman-Rivera A, Batra D, Kohli P . Multiple choice learning: learning to produce multiple structured outputs. Adv Neural Inf Process Syst 2012; 2: 1799-807.
[252]

Bresson X, Laurent T . Residual gated graph convnets. 2017. arXiv:1711.07553.
[253]

Dai H, Dai B, Song L . Discriminative embeddings of latent variable models for structured data. In: Balcan MF, Weinberger KQ, editors. Proceedings of the 33rd International Conference on International Conference on Machine Learning; 2016 Jun 19-24; New York City, NY, USA. New York City: PMLR; 2016. p. 2702-11.
[254]

Vaswani A, Shazeer N, Parmar N, Uszkoreit J, Jones L, Gomez AN, et al. Attention is all you need. In: von Luxburg U, Guyon I, Bengio S, Wallach H, Fergus R, editors. Proceedings of the 31st International Conference on Neural Information Processing Systems; 2017 Dec 4-9; Long Beach, CA, USA. Red Hook: Curran Associates, Inc.; 2017. p. 6000-8.
[255]

Karalias N, Loukas A . Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. Adv Neural Inf Process Syst 2020; 33: 6659-72.
[256]

Wang HP, Wu N, Yang H, Hao C, Li P . Unsupervised learning for combinatorial optimization with principled objective relaxation. Adv Neural Inf Process Syst 2022; 35: 31444-58.
[257]

Saunshi N, Plevrakis O, Arora S, Khodak M, Khandeparkar H. A theoretical analysis of contrastive unsupervised representation learning. In: Chaudhuri K, Salakhutdinov R, editors. Proceedings of the 36th International Conference on Machine Learning; 2019 Jun 9-15; Long Beach, CA, USA. New York City: PMLR; 2019. p. 5628-37.
[258]

Tosh C, Krishnamurthy A, Hsu D . Contrastive learning, multi-view redundancy, and linear models. In: Abernethy J, Agarwal S, editors. Proceedings of the 32nd International Conference on Algorithmic Learning Theory; 2021 Mar 15-17; online conference. New York City: PMLR; 2021. p. 1179-206.
[259]

You Y, Chen T, Sui Y, Chen T, Wang Z, Shen Y . Graph contrastive learning with augmentations. Adv Neural Inf Process Syst 2020; 33: 5812-23.
[260]

Hassani K, Khasahmadi AH. Contrastive multi-view representation learning on graphs. In: Daumé, H, Singh A, editors. Proceedings of the 37th International Conference on Machine Learning; 2020 Jul 13-18; online conference. New York City: PMLR; 2020. p. 4116-26.
[261]

Jing M, Zhu Y, Zang T, Yu J, Tang F . Graph contrastive learning with adaptive augmentation for recommendation. In: Amini MR, Canu S, Fischer A, Guns T, Kralj Novak P, Tsoumakas G, editors. Machine learning and knowledge discovery in databases. ECML PKDD 2022. Cham: Springer; 2022. p. 590-605.
[262]

Jiang Y, Huang C, Huang L . Adaptive graph contrastive learning for recommendation. In: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining; 2023 Aug 6-10; Long Beach, CA, USA. New York City: Association for Computing Machinery; 2023. p. 4252-61.
[263]

Maurya SK, Liu X, Murata T . Graph neural networks for fast node ranking approximation. ACM Trans Knowl Discov Data 2021; 15(5): 1-32.
[264]

Ahmed R, Turja MA, Sahneh FD, Ghosh M, Hamm K, Kobourov S . Computing Steiner trees using graph neural networks. 2021. arXiv:2108.08368.
[265]

Chen W, Yao X, Zhang X, Yu B . Efficient deep space filling curve. In: Proceedings of 2023 IEEE/CVF International Conference on Computer Vision; 2023 Oct 1-6; Paris, France. Piscataway: IEEE; 2023. p. 17525-34.
[266]

Abboud R, Dimitrov R, Ceylan II . Shortest path networks for graph property prediction. In: Chien I, Chen J, Zhao L, editors. Proceedings of the 1st Learning on Graphs Conference; 2022 Dec 9-12; online conference. New York City: PMLR; 2022. p. 5.
[267]

Chen H, Luo Z, Zhang J, Zhou L, Bai X, Hu Z, et al. Learning to match features with seeded graph matching network. In: Proceedings of 2021 IEEE/CVF International Conference on Computer Vision; 2021 Oct 11-17; Montréal, QC, Canada. Piscataway: IEEE; 2021. p. 6301-10.
[268]

Huoh TL, Luo Y, Li P, Zhang T . Flow-based encrypted network traffic classification with graph neural networks. IEEE Trans Netw Serv Manag 2022; 20(2): 1224-37.
[269]

Hope O, Yoneki E . GDDR: GNN-based data-driven routing. In: Proceedings of 2021 IEEE 41st International Conference on Distributed Computing Systems; 2021 Jul 7-10; Washington, DC, USA. Piscataway: IEEE; 2021. p. 517-27.
[270]

Yang Y, Zou D, He X . Graph neural network-based node deployment for throughput enhancement. IEEE Trans Neural Netw Learn Syst 2023; 35(10): 14810-24.
[271]

Eisen M, Ribeiro A . Optimal wireless resource allocation with random edge graph neural networks. IEEE Trans Signal Process 2020; 68: 2977-91.
[272]

He Z, Wang L, Ye H, Li GY, Juang BHF . Resource allocation based on graph neural networks in vehicular communications. In: Proceedings of 2020 IEEE Global Communications Conference; 2020 Dec 7-11; Taipei, China. Piscataway: IEEE; 2020. p. 1-5.
[273]

Zhang C, Song W, Cao Z, Zhang J, Tan PS, Chi X . Learning to dispatch for job shop scheduling via deep reinforcement learning. Adv Neural Inf Process Syst 2020; 33: 1621-32.
[274]

Song W, Chen X, Li Q, Cao Z . Flexible job-shop scheduling via graph neural network and deep reinforcement learning. IEEE Trans Industr Inform 2023; 19(2): 1600-10.
[275]

Sato R, Yamada M, Kashima H . Approximation ratios of graph neural networks for combinatorial problems. In: Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, editors. Proceedings of the 33rd International Conference on Neural Information Processing Systems; 2019 Dec 8-14; Vancouver, BC, Canada. Red Hook: Curran Associates, Inc.; 2019. p. 4081-90.
[276]

Wu Y, Song W, Cao Z, Zhang J, Gupta A, Lin M . Graph learning assisted multi-objective integer programming. Adv Neural Inf Process Syst 2022; 35: 17774-87.
[277]

Wan X, Xu K, Liao X, Jin Y, Chen K, Jin X . Scalable and efficient full-graph GNN training for large graphs. Proc ACM Manag Data 2023; 1(2): 143.
[278]

Kwon S, Choi H, Park S . Solving bilevel knapsack problem using graph neural networks. 2022. arXiv:2211.13436.
[279]

Butti S, Dalmau V . The complexity of the distributed constraint satisfaction problem. Theory Comput Syst 2024; 68(4): 838-67.
[280]

Liu Y, Zhang P, Gao Y, Zhou C, Li Z, Chen H . Combinatorial optimization with automated graph neural networks. 2024. arXiv:2406.02872.
[281]

Chi C, Aboussalah A, Khalil EB, Wang J, Sherkat-Masoumi Z. A deep reinforcement learning framework for column generation. Adv Neural Inf Process Syst 2022; 35: 9633-44.
[282]

Shafi Z, Miller BA, Eliassi-Rad T, Caceres RS . Graph-SCP: accelerating set cover problems with graph neural networks. 2023. arXiv:2310.07979.
[283]

Yuan H, Jiang P, Song S . The neural-prediction based acceleration algorithm of column generation for graph-based set covering problems. In: Proceedings of 2022 IEEE International Conference on Systems, Man, and Cybernetics; 2022 Oct 9-12; Prague, Czech Republic. Piscataway: IEEE; 2022. p. 1115-20.
[284]

Yolcu E, Póczos B . Learning local search heuristics for boolean satisfiability. In: Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, editors. Proceedings of the 33rd International Conference on Neural Information Processing Systems; 2019 Dec 8-14; Vancouver, BC, Canada. Red Hook: Curran Associates, Inc.; 2019. p. 7992-8003.
[285]

Bünz B, Lamm M . Graph neural networks and boolean satisfiability. 2017. arXiv:1702.03592.
[286]

Yan Z, Li M, Shi Z, Zhang W, Chen Y, Zhang H . Addressing variable dependency in GNN-based SAT solving. 2023. arXiv:2304.08738.
[287]

Goh YL, Cao Z, Ma Y, Dong Y, Dupty MH, Lee WS . Hierarchical neural constructive solver for real-world TSP scenarios. In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining; 2024 Aug 25-29; Los Angeles, CA, USA. New York City: Association for Computing Machinery; 2024. p. 884-95.
[288]

Li M, Tu S, Xu L. Generalizing graph network models for the traveling salesman problem with Lin-Kernighan-Helsgaun heuristics. In: Luo B, Cheng L, Wu ZG, Li H, Li C, editors. Neural information processing. ICONIP 2023. Singapore: Springer; 2024. p. 528-39.
[289]

Chen T, Zhang X, You M, Zheng G, Lambotharan S . A GNN-based supervised learning framework for resource allocation in wireless IoT networks. IEEE Internet Things J 2022; 9(3): 1712-24.
[290]

Cai C, Wang D, Wang Y. Graph coarsening with neural networks. 2021. arXiv:2102.01350.
[291]

Awasthi P, Das A, Gollapudi S . Beyond GNNs: an efficient architecture for graph problems. In: Proceedings of the AAAI Conference on Artificial Intelligence; 2022 Feb 22-March 1; Vancouver, BC, Canada. Palo Alto: AAAI Press; 2022. p. 6019-27.
[292]

Fan M, Wu Y, Cao Z, Song W, Sartoretti G, Liu H, et al. Conditional neural heuristic for multiobjective vehicle routing problems. IEEE Trans Neural Netw Learn Syst 2025; 36(3): 4677-89.
[293]

Lin X, Yang Z, Zhang Q . Pareto set learning for neural multi-objective combinatorial optimization. In: Proceedings of the 10th International Conference on Learning Representations; 2022 Apr 25-29; online conference; 2022.
[294]

Boulesnane A. Evolutionary dynamic optimization and machine learning. In: Valadi J, Singh KP, Ojha M, Siarry P, editors. Advanced machine learning with evolutionary and metaheuristic techniques. Singapore: Springer; 2024. p. 67-85.
[295]

Lu H, Li Z, Wang R, Ren Q, Li X, Yuan M, et al. ROCO: a general framework for evaluating robustness of combinatorial optimization solvers on graphs. In: Proceedings of the 11th International Conference on Learning Representations; 2023 May 1-5; Kigali, Rwanda; 2023.
[296]

Liu F, Tong X, Yuan M, Lin X, Luo F, Wang Z, et al. Evolution of heuristics: towards efficient automatic algorithm design using large language model. In: Salakhutdinov R, Kolter Z, Heller K, Weller A, Oliver N, Scarlett J, et al., editors. Proceedings of the 41st International Conference on Machine Learning; 2024 Jul 21-27; Vienna, Austria. New York City: PMLR; 2024. p. 32201-23.
[297]

Ju W, Fang Z, Gu Y, Liu Z, Long Q, Qiao Z, et al. A comprehensive survey on deep graph representation learning. Neural Netw 2024; 173: 106207.
[298]

Yan X, Zhong G, Jin Y, Ke X, Xie F, Huang G . Binary spectral clustering for multi-view data. Inf Sci 2024; 677: 120899.
[299]

Yan X, Wang Z, Jin Y . Heterogeneity-aware federated graph neural networks for incomplete multi-view clustering. IEEE Trans Em Top Comput Intell 2026; 10(1): 369-81.
[300]

Qiu H, Hancock ER . Graph simplification and matching using commute times. Pattern Recognit 2007; 40(10): 2874-89.
[301]

Zhang T, Shan HR, Little MA . Causal GraphSAGE: a robust graph method for classification based on causal sampling. Pattern Recognit 2022; 128: 108696.
[302]

Chen J, Ma T, Xiao C . FastGCN: fast learning with graph convolutional networks via importance sampling. 2018. arXiv:1801.10247.
[303]

Bai Y, Li C, Lin Z, Wu Y, Miao Y, Liu Y, et al. Efficient data loader for fast sampling-based GNN training on large graphs. IEEE Trans Parallel Distrib Syst 2021; 32(10): 2541-56.
[304]

Besta M, Hoefler T . Parallel and distributed graph neural networks: an in-depth concurrency analysis. IEEE Trans Pattern Anal Mach Intell 2024; 46(5): 2584-606.
[305]

Liu S, Yan X, Jin Y . An edge-aware graph autoencoder trained on scale-imbalanced data for traveling salesman problems. Knowl Base Syst 2024; 291: 111559.
[306]

Heydaribeni N, Zhan X, Zhang R, Eliassi-Rad T, Koushanfar F. Distributed constrained combinatorial optimization leveraging hypergraph neural networks. Nat Mach Intell 2024; 6(6): 664-72.
[307]

Yan X, Huang H, Jin Y, Chen L, Liang Z, Hao Z . Neural architecture search via multi-hashing embedding and graph tensor networks for multilingual text classification. IEEE Trans Em Top Comput Intell 2023; 8(1): 350-63.
[308]

Wang Z, Yan X, Jin Y . Fairness-oriented vertical federated GNNs with incomplete sensitive attributes. Inf Fusion 2026; 127(Pt B): 103871.
[309]

Zhu H, Wang X, Jin Y . Federated many-task Bayesian optimization. IEEE Trans Evol Comput 2024; 28(4): 980-93.
PDF (1820KB)

0

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉