mlsanityData to 7 Oct 2026

A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks

arXiv 2406.13125 ↗First posted 19 Jun 2024cs.AIcited by 4

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) have emerged as a powerful tool 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, 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 the relational information and extract features from the graph representation of COPs, offering a generic solution to COPs that can address the limitations of state-of-the-art in solving non-graph-structured and highly complex graph-structured COPs.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 127 of its 277 references that are in the map. First posted on arXiv 19 Jun 2024.

Builds on

127 of 277 references.

References · 127

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2013Efficient Estimation of Word Representations in Vector Spacecited by 4,346
  7. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  8. 2014Sequence to Sequence Learning with Neural Networkscited by 2,974
  9. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  10. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  11. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  12. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
38 more
  1. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  2. 2019Simplifying Graph Convolutional Networkscited by 1,470
  3. 2020Graph Contrastive Learning with Augmentationscited by 1,203
  4. 2018Deep Graph Infomaxcited by 1,101
  5. 2015Pointer Networkscited by 882
  6. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  7. 2015Gated Graph Sequence Neural Networkscited by 792
  8. 2020Benchmarking Graph Neural Networkscited by 672
  9. 2020Contrastive Multi-View Representation Learning on Graphscited by 651
  10. 2018Attention, Learn to Solve Routing Problems!cited by 646
  11. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  12. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  13. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  14. 2015LINE: Large-scale Information Network Embeddingcited by 582
  15. 2020Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networkscited by 563
  16. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  17. 2019A Theoretical Analysis of Contrastive Unsupervised Representation Learningcited by 530
  18. 2019Graph U-Netscited by 489
  19. 2018GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Modelscited by 406
  20. 2019Hyperbolic Graph Convolutional Neural Networkscited by 400
  21. 2018GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoderscited by 375
  22. 2020Graph Structure Learning for Robust Graph Neural Networkscited by 368
  23. 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 361
  24. 2021GemNet: Universal Directional Graph Neural Networks for Moleculescited by 342
  25. 2017Residual Gated Graph ConvNetscited by 341
  26. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  27. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  28. 2021Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Predictioncited by 273
  29. 2023Exploring the Potential of Large Language Models (LLMs) in Learning on Graphscited by 271
  30. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  31. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 258
  32. 2020Spatial-Temporal Fusion Graph Neural Networks for Traffic Flow Forecastingcited by 212
  33. 2017CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filterscited by 203
  34. 2019Graph Matching Networks for Learning the Similarity of Graph Structured Objectscited by 202
  35. 2020Graph Neural Networks with Heterophilycited by 202
  36. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
  37. 2022Representing Long-Range Context for Graph Neural Networks with Global Attentioncited by 193
  38. 2019Graph Neural Networks with convolutional ARMA filterscited by 185

50 most cited of 127 All 127 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2025Towards graph neural networks for provably solving convex optimization problemscited by 4
  2. 2026Survey on Neural Routing Solverscited by 4
  3. 2025A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problemcited by 1
  4. 2024Ethical Challenges in Computer Vision: Ensuring Privacy and Mitigating Bias in Publicly Available Datasetscited by 0