mlsanityData to 7 Oct 2026

Combinatorial optimization and reasoning with graph neural networks

arXiv 2102.09544 ↗First posted 18 Feb 2021cs.LG cs.DS cs.NEcited by 267

Not on the map. Why?

Abstract (arXiv)

Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolation, ignoring that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning, especially graph neural networks (GNNs), as a key building block for combinatorial tasks, either directly as solvers or by enhancing exact solvers. The inductive bias of GNNs effectively encodes combinatorial and relational input due to their invariance to permutations and awareness of input sparsity. This paper presents a conceptual review of recent key advancements in this emerging field, aiming at optimization and machine learning researchers.

Key facts. Cited by 267 papers in the map (data through 7 Oct 2026). Builds on 112 of its 276 references that are in the map. First posted on arXiv 18 Feb 2021.

Builds on

112 of 276 references.

References · 112

  1. 2020A Simple Framework for Contrastive Learning of Visual Representationscited by 11,979
  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. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  7. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  8. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  9. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  10. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  11. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  12. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
38 more
  1. 2015Pointer Networkscited by 882
  2. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  3. 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
  4. 2020Learning Mesh-Based Simulation with Graph Networkscited by 840
  5. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  6. 2020Benchmarking Graph Neural Networkscited by 672
  7. 2018Attention, Learn to Solve Routing Problems!cited by 646
  8. 2014Neural Turing Machinescited by 630
  9. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  10. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  11. 2017In-Datacenter Performance Analysis of a Tensor Processing Unitcited by 610
  12. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  13. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  14. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  15. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  16. 2019Provably Powerful Graph Networkscited by 385
  17. 2017A simple neural network module for relational reasoningcited by 345
  18. 2017Residual Gated Graph ConvNetscited by 341
  19. 2018Invariant and Equivariant Graph Networkscited by 339
  20. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  21. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  22. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  23. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
  24. 2019Differentiation of Blackbox Combinatorial Solverscited by 224
  25. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  26. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  27. 2019Graph Matching Networks for Learning the Similarity of Graph Structured Objectscited by 202
  28. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
  29. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  30. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  31. 2020Random Features Strengthen Graph Neural Networkscited by 184
  32. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  33. 2020Design Space for Graph Neural Networkscited by 182
  34. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  35. 2019SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solvercited by 173
  36. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  37. 2020Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddingscited by 169
  38. 2016Value Iteration Networkscited by 158

50 most cited of 112 All 112 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 28; 2022: 60; 2023: 40; 2024: 53; 2025: 55; 2026: 31.

267 papers.

Sort:

By area:

  1. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  2. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  3. 2021End-to-End Constrained Optimization Learning: A Surveycited by 154
  4. 2021Scalars are universal: Equivariant machine learning, structured like classical physicscited by 127
  5. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
  6. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 103
  7. 2021Neural Algorithmic Reasoningcited by 92
  8. 2022Tutorial on amortized optimizationcited by 83
  9. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 80
  10. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
  11. 2022In Defense of the Unitary Scalarization for Deep Multi-Task Learningcited by 65
  12. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 64
38 more
  1. 2021Linear algebra with transformerscited by 62
  2. 2023Compositional Generalization from First Principlescited by 62
  3. 2023Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policycited by 61
  4. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  5. 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learningcited by 58
  6. 2022A Generalist Neural Algorithmic Learnercited by 58
  7. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 58
  8. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  9. 2022Provably expressive temporal graph networkscited by 56
  10. 2022Graph Neural Networks are Dynamic Programmerscited by 55
  11. 2025Position: Graph Learning Will Lose Relevance Due To Poor Benchmarkscited by 52
  12. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 48
  13. 2021Constructions in combinatorics via neural networkscited by 46
  14. 2024Can Graph Learning Improve Planning in LLM-based Agents?cited by 42
  15. 2022Equivariant quantum circuits for learning on weighted graphscited by 41
  16. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  17. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  18. 2023OptiMUS: Optimization Modeling Using MIP Solvers and large language modelscited by 39
  19. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 39
  20. 2021On Representation Knowledge Distillation for Graph Neural Networkscited by 38
  21. 2022SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networkscited by 36
  22. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  23. 2021Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustnesscited by 35
  24. 2022Explaining the Explainers in Graph Neural Networks: a Comparative Studycited by 34
  25. 2023Equivariant Deep Weight Space Alignmentcited by 34
  26. 2022Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 33
  27. 2024Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNscited by 31
  28. 2025ALE-Bench: A Benchmark for Long-Horizon Objective-Driven Algorithm Engineeringcited by 30
  29. 2022Graph Coloring with Physics-Inspired Graph Neural Networkscited by 29
  30. 2024Simulation of Graph Algorithms with Looped Transformerscited by 29
  31. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physicscited by 28
  32. 2025CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimizationcited by 28
  33. 2021Goal-Aware Neural SAT Solvercited by 27
  34. 2022Graph Neural Networks in IoT: A Surveycited by 27
  35. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  36. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
  37. 2022Adaptive Cut Selection in Mixed-Integer Linear Programmingcited by 25
  38. 2022On the Generalization of Neural Combinatorial Optimization Heuristicscited by 24

50 most cited of 267 All 267 (JSON)