mlsanityData to 14 Oct 2026

A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization

arXiv 2406.01661 ↗First posted 3 Jun 2024cs.LG cs.AI cs.DMcited by 59

On the map: Diffusion models → Diffusion foundations and sampling

Abstract (arXiv)

Learning to sample from intractable distributions over discrete sets without relying on corresponding training data is a central problem in a wide range of fields, including Combinatorial Optimization. Currently, popular deep learning-based approaches rely primarily on generative models that yield exact sample likelihoods. This work introduces a method that lifts this restriction and opens the possibility to employ highly expressive latent variable models like diffusion models. Our approach is conceptually based on a loss that upper bounds the reverse Kullback-Leibler divergence and evades the requirement of exact sample likelihoods. We experimentally validate our approach in data-free Combinatorial Optimization and demonstrate that our method achieves a new state-of-the-art on a wide range of benchmark problems.

Key facts. Cited by 59 papers in the map (data through 14 Oct 2026). Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models. Builds on 43 of its 65 references that are in the map. First posted on arXiv 3 Jun 2024.

Builds on

43 of 65 references.

Closest ancestors · 7

Same direction, newest first

  1. 2023Denoising Diffusion Samplers27 Feb
  2. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization16 Feb
  3. 2022An optimal control perspective on diffusion-based generative modeling2 Nov
  4. 2021High-Resolution Image Synthesis with Latent Diffusion Models20 Dec
  5. 2021Structured Denoising Diffusion Models in Discrete State-Spaces7 Jul
  6. 2020Score-Based Generative Modeling through Stochastic Differential Equations26 Nov
  7. 2020Denoising Diffusion Probabilistic Models19 Jun

Other references · 36

  1. 2015U-Net: Convolutional Networks for Biomedical Image Segmentationcited by 19,713
  2. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,058
  3. 2016Layer Normalizationcited by 5,669
  4. 2019An Introduction to Variational Autoencoderscited by 1,000
  5. 2019On the Variance of the Adaptive Learning Rate and Beyondcited by 772
  6. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  7. 2021Flow Network based Generative Models for Non-Iterative Diverse Candidate Generationcited by 392
  8. 2021GFlowNet Foundationscited by 290
  9. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  10. 2013Ising formulations of many NP problemscited by 207
  11. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 183
  12. 2020Stochastic Normalizing Flowscited by 157
24 more
  1. 2018Neural Importance Samplingcited by 155
  2. 2020Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learningcited by 149
  3. 2024Iterated Denoising Energy Matching for Sampling from Boltzmann Densitiescited by 116
  4. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  5. 2023Improved sampling via learned diffusionscited by 104
  6. 2018Solving Statistical Mechanics Using Variational Autoregressive Networkscited by 100
  7. 2019Exploratory Combinatorial Optimization with Reinforcement Learningcited by 82
  8. 2020Limitations of Autoregressive Models and Their Alternativescited by 55
  9. 2020Learning What to Defer for Maximum Independent Setscited by 54
  10. 2021Variational Neural Annealingcited by 47
  11. 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
  12. 2022What's Wrong with Deep Learning in Tree Search for Combinatorial Optimizationcited by 37
  13. 2015Finding Near-Optimal Independent Sets at Scalecited by 33
  14. 2020It's Not What Machines Can Learn, It's What We Cannot Teachcited by 29
  15. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  16. 2023Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspectivecited by 26
  17. 2023Variational Annealing on Graphs for Combinatorial Optimizationcited by 21
  18. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 20
  19. 2022Annealed Training for Combinatorial Optimization on Graphscited by 18
  20. 2023Limits, approximation and size transferability for GNNs on sparse graphs via graphopscited by 18
  21. 2021Unbiased Monte Carlo Cluster Updates with Autoregressive Neural Networkscited by 17
  22. 2018Forward Amortized Inference for Likelihood-Free Variational Marginalizationcited by 14
  23. 2022Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Explorationcited by 14
  24. 2019Stochastic Variational Inference via Upper Boundcited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 29; 2026: 27.

59 papers.

Sort:

By area:

  1. 2025Test-time Alignment of Diffusion Models without Reward Over-optimizationcited by 93
  2. 2025LEAPS: A discrete neural sampler via locally equivariant networkscited by 31
  3. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physicscited by 29
  4. 2025MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Controlcited by 21
  5. 2025Proximal Diffusion Neural Samplercited by 16
  6. 2025Generative Models in Decision Making: A Surveycited by 15
  7. 2025Discrete Neural Flow Samplers with Locally Equivariant Transformercited by 13
  8. 2025FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimizationcited by 11
  9. 2025Regularized Langevin Dynamics for Combinatorial Optimizationcited by 10
  10. 2024Adaptive Non-uniform Timestep Sampling for Accelerating Diffusion Model Trainingcited by 9
  11. 2025Rethinking Losses for Diffusion Bridge Samplerscited by 7
  12. 2024SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groupscited by 6
38 more
  1. 2024Neural Solver Selection for Combinatorial Optimizationcited by 5
  2. 2025Diffusion-DFL: Decision-focused Diffusion Models for Stochastic Optimizationcited by 5
  3. 2025Satellite Edge Artificial Intelligence with Large Models: Architectures and Technologiescited by 4
  4. 2025Geometric Algorithms for Neural Combinatorial Optimization with Constraintscited by 4
  5. 2026Discrete Adjoint Schr"odinger Bridge Samplercited by 4
  6. 2025Lattice Protein Folding with Variational Annealingcited by 3
  7. 2025IsingFormer: Augmenting Parallel Tempering With Learned Proposalscited by 3
  8. 2025Diffusion-Augmented Markov Decision Processes for Maximum Entropy Reinforcement Learningcited by 3
  9. 2025Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Setcited by 2
  10. 2025A Generative Neural Annealer for Black-Box Combinatorial Optimizationcited by 2
  11. 2025FORGE: Foundational Optimization Representations from Graph Embeddingscited by 2
  12. 2025Visual Diffusion Models are Geometric Solverscited by 2
  13. 2026PILD: Physics-Informed Learning via Diffusioncited by 2
  14. 2026Pareto-Conditioned Diffusion Models for Offline Multi-Objective Optimizationcited by 2
  15. 2026Discrete diffusion samplers and bridges: Off-policy algorithms and applications in latent spacescited by 2
  16. 2026CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimizationcited by 2
  17. 2026Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matchingcited by 2
  18. 2025Diffusion-based learning framework for Constrained Nonconvex Optimization with Weighted Bootstrapped Refinementcited by 1
  19. 2025Boosting Cross-problem Generalization in Diffusion-Based Neural Combinatorial Solver via Inference Time Adaptationcited by 1
  20. 2025A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problemcited by 1
  21. 2025LacaDM: A Latent Causal Diffusion Model for Multiobjective Reinforcement Learningcited by 1
  22. 2026Large Neighborhood Search meets Iterative Neural Constraint Heuristicscited by 1
  23. 2026BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Designcited by 1
  24. 2025Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimizationcited by 0
  25. 2025Universal Physics Simulation: A Foundational Diffusion Approachcited by 0
  26. 2025Spatial Computing Communications for Multi-User Virtual Reality in Distributed Mobile Edge Computing Networkcited by 0
  27. 2025Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimizationcited by 0
  28. 2025Edge-wise Topological Divergence Gaps: Guiding Search in Combinatorial Optimizationcited by 0
  29. 2026Enabling Population-Based Architectures for Neural Combinatorial Optimizationcited by 0
  30. 2026GraIP: A Benchmarking Framework For Neural Graph Inverse Problemscited by 0
  31. 2026Test-Time Adaptation for Unsupervised Combinatorial Optimizationcited by 0
  32. 2026Neural Ising Machines via Unrolling and Zeroth-Order Trainingcited by 0
  33. 2026Boltzmann Reinforcement Learning for Noise resilience in Analog Ising Machinescited by 0
  34. 2026Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?cited by 0
  35. 2026UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimizationcited by 0
  36. 2026Crystal structure prediction using graph neural combinatorial optimizationcited by 0
  37. 2026Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimizationcited by 0
  38. 2026LoRe: Adaptive Interaction-Evaluation Routing with Per-Step Interaction Budgets for Iterative Graph Solverscited by 0

50 most cited of 59 All 59 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2024DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems
  2. 2022Diffusion models as plug-and-play priors
  3. 2025Latent Guided Sampling for Combinatorial Optimization
  4. 2023Accelerating Diffusion-based Combinatorial Optimization Solvers by Progressive Distillation
  5. 2024Unsupervised Training of Diffusion Models for Feasible Solution Generation in Neural Combinatorial Optimization
  6. 2025Diffusion Models: A Mathematical Introduction
  7. 2024ComboStoc: Combinatorial Stochasticity for Diffusion Generative Models
  8. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization