mlsanityData to 7 Oct 2026

Are Graph Neural Networks Optimal Approximation Algorithms?

arXiv 2310.00526 ↗First posted 1 Oct 2023cs.LG cs.AI cs.DMcited by 10

Not on the map. Why?

Abstract (arXiv)

In this work we design graph neural network architectures that capture optimal approximation algorithms for a large class of combinatorial optimization problems, using powerful algorithmic tools from semidefinite programming (SDP). Concretely, we prove that polynomial-sized message-passing algorithms can represent the most powerful polynomial time algorithms for Max Constraint Satisfaction Problems assuming the Unique Games Conjecture. We leverage this result to construct efficient graph neural network architectures, OptGNN, that obtain high-quality approximate solutions on landmark combinatorial optimization problems such as Max-Cut, Min-Vertex-Cover, and Max-3-SAT. Our approach achieves strong empirical results across a wide range of real-world and synthetic datasets against solvers and neural baselines. Finally, we take advantage of OptGNN's ability to capture convex relaxations to design an algorithm for producing bounds on the optimal solution from the learned embeddings of OptGNN.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 69 of its 116 references that are in the map. First posted on arXiv 1 Oct 2023.

Builds on

69 of 116 references.

References · 69

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2017Graph Attention Networkscited by 8,854
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2021Convex optimizationcited by 2,479
  6. 2015Pointer Networkscited by 882
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  8. 2015Gated Graph Sequence Neural Networkscited by 792
  9. 2020Benchmarking Graph Neural Networkscited by 672
  10. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  11. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  12. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
38 more
  1. 2019Differentiable Convex Optimization Layerscited by 458
  2. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  3. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  4. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  5. 2017How to Escape Saddle Points Efficientlycited by 284
  6. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  7. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  8. 2021Deep learning: a statistical viewpointcited by 239
  9. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
  10. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  11. 2020Random Features Strengthen Graph Neural Networkscited by 184
  12. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  13. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  14. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  15. 2019SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solvercited by 173
  16. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  17. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  18. 2019Neural Execution of Graph Algorithmscited by 118
  19. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  20. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
  21. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 103
  22. 2020Hybrid Models for Learning to Branchcited by 95
  23. 2021Neural Algorithmic Reasoningcited by 92
  24. 2019Exploratory Combinatorial Optimization with Reinforcement Learningcited by 82
  25. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
  26. 2019Guiding High-Performance SAT Solvers with Unsat-Core Predictionscited by 61
  27. 2018Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSPcited by 58
  28. 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learningcited by 58
  29. 2022A Generalist Neural Algorithmic Learnercited by 58
  30. 2020Learning What to Defer for Maximum Independent Setscited by 53
  31. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  32. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  33. 2022What's Wrong with Deep Learning in Tree Search for Combinatorial Optimizationcited by 36
  34. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  35. 2022Graph Coloring with Physics-Inspired Graph Neural Networkscited by 29
  36. 2021Goal-Aware Neural SAT Solvercited by 27
  37. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  38. 2022Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?cited by 25

50 most cited of 69 All 69 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

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

10 papers.

  1. 2025Regularized Langevin Dynamics for Combinatorial Optimizationcited by 10
  2. 2025Primal-Dual Neural Algorithmic Reasoningcited by 8
  3. 2025Geometric Algorithms for Neural Combinatorial Optimization with Constraintscited by 4
  4. 2023Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networkscited by 2
  5. 2025Neural Approaches to SAT Solving: Design Choices and Interpretabilitycited by 2
  6. 2025FORGE: Foundational Optimization Representations from Graph Embeddingscited by 2
  7. 2025Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimizationcited by 0
  8. 2025Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphscited by 0
  9. 2026UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimizationcited by 0
  10. 2026Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networkscited by 0