mlsanityData to 7 Oct 2026

Variational Annealing on Graphs for Combinatorial Optimization

arXiv 2311.14156 ↗First posted 23 Nov 2023cs.LG cs.AI cs.DMcited by 21

Not on the map. Why?

Abstract (arXiv)

Several recent unsupervised learning methods use probabilistic approaches to solve combinatorial optimization (CO) problems based on the assumption of statistically independent solution variables. We demonstrate that this assumption imposes performance limitations in particular on difficult problem instances. Our results corroborate that an autoregressive approach which captures statistical dependencies among solution variables yields superior performance on many popular CO problems. We introduce subgraph tokenization in which the configuration of a set of solution variables is represented by a single token. This tokenization technique alleviates the drawback of the long sequential sampling procedure which is inherent to autoregressive methods without sacrificing expressivity. Importantly, we theoretically motivate an annealed entropy regularization and show empirically that it is essential for efficient and stable learning.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 32 of its 54 references that are in the map. First posted on arXiv 23 Nov 2023.

Builds on

32 of 54 references.

References · 32

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2016Layer Normalizationcited by 5,579
  4. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 4,993
  5. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 1,916
  6. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  7. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  8. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  9. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  10. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  11. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  12. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
20 more
  1. 2013Ising formulations of many NP problemscited by 204
  2. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  3. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  4. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  5. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  6. 2018Solving Statistical Mechanics Using Variational Autoregressive Networkscited by 99
  7. 2020Learning What to Defer for Maximum Independent Setscited by 53
  8. 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
  9. 2021Variational Neural Annealingcited by 45
  10. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  11. 2022What's Wrong with Deep Learning in Tree Search for Combinatorial Optimizationcited by 36
  12. 2022Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 33
  13. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  14. 2020It's Not What Machines Can Learn, It's What We Cannot Teachcited by 29
  15. 2022Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?cited by 25
  16. 2021Rethinking Skip Connection with Layer Normalization in Transformers and ResNetscited by 22
  17. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 19
  18. 2022Annealed Training for Combinatorial Optimization on Graphscited by 17
  19. 2022Neural Set Function Extensions: Learning with Discrete Functions in High Dimensionscited by 14
  20. 2022Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problemscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 6; 2025: 9; 2026: 6.

21 papers.

Sort:

By area:

  1. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 58
  2. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physicscited by 28
  3. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspectivecited by 16
  4. 2024Geometry-Informed Neural Networkscited by 12
  5. 2024Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and Morecited by 6
  6. 2024Moco: A Learnable Meta Optimizer for Combinatorial Optimizationcited by 5
  7. 2024GNN-VPA: A Variance-Preserving Aggregation Strategy for Graph Neural Networkscited by 5
  8. 2026Discrete Adjoint Schr"odinger Bridge Samplercited by 4
  9. 2025Lattice Protein Folding with Variational Annealingcited by 3
  10. 2025LMask: Learn to Solve Constrained Routing Problems with Lazy Maskingcited by 3
  11. 2025Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Setcited by 2
  12. 2025Learning for Dynamic Combinatorial Optimization without Training Datacited by 1
9 more
  1. 2025Nonlocal Monte Carlo via Reinforcement Learningcited by 1
  2. 2025ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule miningcited by 0
  3. 2025Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysiscited by 0
  4. 2025Towards a General Framework for Predicting and Explaining the Hardness of Graph-based Combinatorial Optimization Problems using Machine Learning and Association Rule Miningcited by 0
  5. 2026Test-Time Adaptation for Unsupervised Combinatorial Optimizationcited by 0
  6. 2026Neural Ising Machines via Unrolling and Zeroth-Order Trainingcited by 0
  7. 2026UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimizationcited by 0
  8. 2026Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimizationcited by 0
  9. 2026Fixed-point neural samplers on discrete spacescited by 0