mlsanityData to 7 Oct 2026

Annealed Training for Combinatorial Optimization on Graphs

arXiv 2207.11542 ↗First posted 23 Jul 2022cs.LGcited by 17

Not on the map. Why?

Abstract (arXiv)

The hardness of combinatorial optimization (CO) problems hinders collecting solutions for supervised learning. However, learning neural networks for CO problems is notoriously difficult in lack of the labeled data as the training is easily trapped at local optima. In this work, we propose a simple but effective annealed training framework for CO problems. In particular, we transform CO problems into unbiased energy-based models (EBMs). We carefully selected the penalties terms so as to make the EBMs as smooth as possible. Then we train graph neural networks to approximate the EBMs. To prevent the training from being stuck at local optima near the initialization, we introduce an annealed loss function. An experimental evaluation demonstrates that our annealed training framework obtains substantial improvements. In four types of CO problems, our method achieves performance substantially better than other unsupervised neural methods on both synthetic and real-world graphs.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 26 of its 66 references that are in the map. First posted on arXiv 23 Jul 2022.

Builds on

26 of 66 references.

References · 26

  1. 2017Graph Attention Networkscited by 8,854
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2015Pointer Networkscited by 882
  4. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 866
  5. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  6. 2020Benchmarking Graph Neural Networkscited by 672
  7. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  8. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  9. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  10. 2016#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learningcited by 307
  11. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  12. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
14 more
  1. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  2. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  3. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  4. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  5. 2019Learning Combinatorial Embedding Networks for Deep Graph Matchingcited by 98
  6. 2020Compositional Generalization via Neural-Symbolic Stack Machinescited by 80
  7. 2018Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSPcited by 58
  8. 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
  9. 2019Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problemscited by 40
  10. 2020It's Not What Machines Can Learn, It's What We Cannot Teachcited by 29
  11. 2017Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networkscited by 28
  12. 2019Experimental performance of graph neural networks on random instances of max-cutcited by 15
  13. 2017Capacity Releasing Diffusion for Speed and Localitycited by 10
  14. 2016A Simple and Strongly-Local Flow-Based Method for Cut Improvementcited by 4

Built on by

Cited by year (2026 to 7 Oct)

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

17 papers.

Sort:

By area:

  1. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 58
  2. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  3. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physicscited by 28
  4. 2023Variational Annealing on Graphs for Combinatorial Optimizationcited by 21
  5. 2023Controlling Continuous Relaxation for Combinatorial Optimizationcited by 16
  6. 2025Proximal Diffusion Neural Samplercited by 16
  7. 2025Discrete Neural Flow Samplers with Locally Equivariant Transformercited by 13
  8. 2023Are Graph Neural Networks Optimal Approximation Algorithms?cited by 10
  9. 2024Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Samplingcited by 6
  10. 2024Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Updatecited by 4
  11. 2025Geometric Algorithms for Neural Combinatorial Optimization with Constraintscited by 4
  12. 2024A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimizationcited by 3
5 more
  1. 2025Lattice Protein Folding with Variational Annealingcited by 3
  2. 2025Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Setcited by 2
  3. 2025Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimizationcited by 0
  4. 2026Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfecited by 0
  5. 2026Parallel Tempering for Diffusion-Based Combinatorial Optimizationcited by 0