# A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization

arXiv: https://arxiv.org/abs/2406.01661 · HTML: https://mlsanity.com/paper/2406.01661/

## 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.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 30 of 43)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [An Introduction to Variational Autoencoders](https://mlsanity.com/paper/1906.02691/) (2019)
- [On the Variance of the Adaptive Learning Rate and Beyond](https://mlsanity.com/paper/1908.03265/) (2019)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation](https://mlsanity.com/paper/2106.04399/) (2021)
- [GFlowNet Foundations](https://mlsanity.com/paper/2111.09266/) (2021)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Stochastic Normalizing Flows](https://mlsanity.com/paper/2002.06707/) (2020)
- [Neural Importance Sampling](https://mlsanity.com/paper/1808.03856/) (2018)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Denoising Diffusion Samplers](https://mlsanity.com/paper/2302.13834/) (2023)
- [An optimal control perspective on diffusion-based generative modeling](https://mlsanity.com/paper/2211.01364/) (2022)
- [Iterated Denoising Energy Matching for Sampling from Boltzmann Densities](https://mlsanity.com/paper/2402.06121/) (2024)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Improved sampling via learned diffusions](https://mlsanity.com/paper/2307.01198/) (2023)
- [Solving Statistical Mechanics Using Variational Autoregressive Networks](https://mlsanity.com/paper/1809.10606/) (2018)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Limitations of Autoregressive Models and Their Alternatives](https://mlsanity.com/paper/2010.11939/) (2020)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)
- [Variational Neural Annealing](https://mlsanity.com/paper/2101.10154/) (2021)
- [Graph Neural Networks for Maximum Constraint Satisfaction](https://mlsanity.com/paper/1909.08387/) (2019)

## Built on by (most cited first, 30 of 59)

- [Test-time Alignment of Diffusion Models without Reward Over-optimization](https://mlsanity.com/paper/2501.05803/) (2025)
- [LEAPS: A discrete neural sampler via locally equivariant networks](https://mlsanity.com/paper/2502.10843/) (2025)
- [Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics](https://mlsanity.com/paper/2502.08696/) (2025)
- [MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Control](https://mlsanity.com/paper/2508.10684/) (2025)
- [Proximal Diffusion Neural Sampler](https://mlsanity.com/paper/2510.03824/) (2025)
- [Generative Models in Decision Making: A Survey](https://mlsanity.com/paper/2502.17100/) (2025)
- [Discrete Neural Flow Samplers with Locally Equivariant Transformer](https://mlsanity.com/paper/2505.17741/) (2025)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [Regularized Langevin Dynamics for Combinatorial Optimization](https://mlsanity.com/paper/2502.00277/) (2025)
- [Adaptive Non-uniform Timestep Sampling for Accelerating Diffusion Model Training](https://mlsanity.com/paper/2411.09998/) (2024)
- [Rethinking Losses for Diffusion Bridge Samplers](https://mlsanity.com/paper/2506.10982/) (2025)
- [SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups](https://mlsanity.com/paper/2410.02942/) (2024)
- [Neural Solver Selection for Combinatorial Optimization](https://mlsanity.com/paper/2410.09693/) (2024)
- [Diffusion-DFL: Decision-focused Diffusion Models for Stochastic Optimization](https://mlsanity.com/paper/2510.11590/) (2025)
- [Satellite Edge Artificial Intelligence with Large Models: Architectures and Technologies](https://mlsanity.com/paper/2504.01676/) (2025)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [Discrete Adjoint Schr"odinger Bridge Sampler](https://mlsanity.com/paper/2602.08243/) (2026)
- [Lattice Protein Folding with Variational Annealing](https://mlsanity.com/paper/2502.20632/) (2025)
- [IsingFormer: Augmenting Parallel Tempering With Learned Proposals](https://mlsanity.com/paper/2509.23043/) (2025)
- [Diffusion-Augmented Markov Decision Processes for Maximum Entropy Reinforcement Learning](https://mlsanity.com/paper/2512.02019/) (2025)
- [Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set](https://mlsanity.com/paper/2502.03669/) (2025)
- [A Generative Neural Annealer for Black-Box Combinatorial Optimization](https://mlsanity.com/paper/2505.09742/) (2025)
- [FORGE: Foundational Optimization Representations from Graph Embeddings](https://mlsanity.com/paper/2508.20330/) (2025)
- [Visual Diffusion Models are Geometric Solvers](https://mlsanity.com/paper/2510.21697/) (2025)
- [PILD: Physics-Informed Learning via Diffusion](https://mlsanity.com/paper/2601.21284/) (2026)
- [Pareto-Conditioned Diffusion Models for Offline Multi-Objective Optimization](https://mlsanity.com/paper/2602.00737/) (2026)
- [Discrete diffusion samplers and bridges: Off-policy algorithms and applications in latent spaces](https://mlsanity.com/paper/2602.05961/) (2026)
- [CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization](https://mlsanity.com/paper/2602.08210/) (2026)
- [Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching](https://mlsanity.com/paper/2605.30920/) (2026)
- [Diffusion-based learning framework for Constrained Nonconvex Optimization with Weighted Bootstrapped Refinement](https://mlsanity.com/paper/2502.10330/) (2025)

## 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.