mlsanityData to 7 Oct 2026

DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization

arXiv 2302.08224 ↗First posted 16 Feb 2023cs.LGcited by 216

On the map: Diffusion models → Diffusion foundations and sampling

Abstract (arXiv)

Neural network-based Combinatorial Optimization (CO) methods have shown promising results in solving various NP-complete (NPC) problems without relying on hand-crafted domain knowledge. This paper broadens the current scope of neural solvers for NPC problems by introducing a new graph-based diffusion framework, namely DIFUSCO. Our framework casts NPC problems as discrete {0, 1}-vector optimization problems and leverages graph-based denoising diffusion models to generate high-quality solutions. We investigate two types of diffusion models with Gaussian and Bernoulli noise, respectively, and devise an effective inference schedule to enhance the solution quality. We evaluate our methods on two well-studied NPC combinatorial optimization problems: Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). Experimental results show that DIFUSCO strongly outperforms the previous state-of-the-art neural solvers, improving the performance gap between ground-truth and neural solvers from 1.76% to 0.46% on TSP-500, from 2.46% to 1.17% on TSP-1000, and from 3.19% to 2.58% on TSP10000. For the MIS problem, DIFUSCO outperforms the previous state-of-the-art neural solver on the challenging SATLIB benchmark.

Key facts. Cited by 216 papers in the map (data through 7 Oct 2026). Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models. Builds on 94 of its 129 references that are in the map. First posted on arXiv 16 Feb 2023.

Builds on

94 of 129 references.

Closest ancestors · 19

Same direction, newest first

  1. 2022Score-based Continuous-time Discrete Diffusion Models30 Nov
  2. 2022DPM-Solver++: Fast Solver for Guided Sampling of Diffusion Probabilistic Models2 Nov
  3. 2022Analog Bits: Generating Discrete Data using Diffusion Models with Self-Conditioning8 Aug
  4. 2022Diffusion models as plug-and-play priors17 Jun
  5. 2022DPM-Solver: A Fast ODE Solver for Diffusion Probabilistic Model Sampling in Around 10 Steps2 Jun
  6. 2022Elucidating the Design Space of Diffusion-Based Generative Models1 Jun
  7. 2022A Continuous Time Framework for Discrete Denoising Models30 May
  8. 2022Pseudo Numerical Methods for Diffusion Models on Manifolds20 Feb
  9. 2021High-Resolution Image Synthesis with Latent Diffusion Models20 Dec
  10. 2021Vector Quantized Diffusion Model for Text-to-Image Synthesis29 Nov
  11. 2021Structured Denoising Diffusion Models in Discrete State-Spaces7 Jul
  12. 2021Variational Diffusion Models1 Jul
7 more
  1. 2021Cascaded Diffusion Models for High Fidelity Image Generation30 May
  2. 2021Diffusion Models Beat GANs on Image Synthesis11 May
  3. 2021Improved Denoising Diffusion Probabilistic Models18 Feb
  4. 2020Score-Based Generative Modeling through Stochastic Differential Equations26 Nov
  5. 2020Denoising Diffusion Implicit Models6 Oct
  6. 2020Denoising Diffusion Probabilistic Models19 Jun
  7. 2020Improved Techniques for Training Score-Based Generative Models16 Jun

Other references · 75

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  4. 2017Graph Attention Networkscited by 8,854
  5. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  6. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  7. 2022Hierarchical Text-Conditional Image Generation with CLIP Latentscited by 6,539
  8. 2022Photorealistic Text-to-Image Diffusion Models with Deep Language Understandingcited by 6,322
  9. 2017Inductive Representation Learning on Large Graphscited by 6,284
  10. 2018How Powerful are Graph Neural Networks?cited by 4,355
  11. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,067
  12. 2021GLIDE: Towards Photorealistic Image Generation and Editing with Text-Guided Diffusion Modelscited by 3,595
38 more
  1. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  2. 2022Video Diffusion Modelscited by 2,280
  3. 2022Imagen Video: High Definition Video Generation with Diffusion Modelscited by 1,765
  4. 2022Make-A-Video: Text-to-Video Generation without Text-Video Datacited by 1,725
  5. 2021Palette: Image-to-Image Diffusion Modelscited by 1,296
  6. 2022Scaling Autoregressive Models for Content-Rich Text-to-Image Generationcited by 1,287
  7. 2022MaskGIT: Masked Generative Image Transformercited by 1,082
  8. 2022Diffusion-LM Improves Controllable Text Generationcited by 1,006
  9. 2022Equivariant Diffusion for Molecule Generation in 3Dcited by 666
  10. 2018Attention, Learn to Solve Routing Problems!cited by 646
  11. 2020WaveGrad: Estimating Gradients for Waveform Generationcited by 620
  12. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  13. 2021Argmax Flows and Multinomial Diffusion: Learning Categorical Distributionscited by 566
  14. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  15. 2022GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generationcited by 511
  16. 2022DiGress: Discrete Denoising diffusion for graph generationcited by 503
  17. 2017Non-Autoregressive Neural Machine Translationcited by 457
  18. 2022DiffuSeq: Sequence to Sequence Text Generation with Diffusion Modelscited by 439
  19. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  20. 2022MAGVIT: Masked Generative Video Transformercited by 341
  21. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  22. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  23. 2020Permutation Invariant Graph Generation via Score-Based Generative Modelingcited by 263
  24. 2022Diffsound: Discrete Diffusion Model for Text-to-sound Generationcited by 256
  25. 2022DiffusionBERT: Improving Generative Masked Language Models with Diffusion Modelscited by 214
  26. 2022Continuous diffusion for categorical datacited by 202
  27. 2022SSD-LM: Semi-autoregressive Simplex-based Diffusion Language Model for Text Generation and Modular Controlcited by 191
  28. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  29. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  30. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  31. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
  32. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 161
  33. 2021DiffSinger: Singing Voice Synthesis via Shallow Diffusion Mechanismcited by 154
  34. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 139
  35. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  36. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 118
  37. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  38. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115

50 most cited of 75 All 75 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 16; 2024: 50; 2025: 82; 2026: 68.

216 papers.

Sort:

By area:

  1. 2024Simple and Effective Masked Diffusion Language Modelscited by 800
  2. 2024ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolutioncited by 266
  3. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 82
  4. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  5. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  6. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  7. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  8. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  9. 2023Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policycited by 61
  10. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 58
  11. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 57
  12. 2023Enhancing Deep Reinforcement Learning: A Tutorial on Generative Diffusion Models in Network Optimizationcited by 56
38 more
  1. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 54
  2. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  3. 2025Position: Graph Learning Will Lose Relevance Due To Poor Benchmarkscited by 52
  4. 2025Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithmscited by 47
  5. 2025Theoretical Benefit and Limitation of Diffusion Language Modelcited by 46
  6. 2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformercited by 43
  7. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
  8. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  9. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 39
  10. 2023Decomposing the Enigma: Subgoal-based Demonstration Learning for Formal Theorem Provingcited by 37
  11. 2024Learning Iterative Reasoning through Energy Diffusioncited by 36
  12. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  13. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  14. 2024Diffusion Models as Constrained Samplers for Optimization with Unknown Constraintscited by 33
  15. 2024Self-Improved Learning for Scalable Neural Combinatorial Optimizationcited by 29
  16. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  17. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physicscited by 28
  18. 2025CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimizationcited by 28
  19. 2024Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 24
  20. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  21. 2024DiffuSolve: Diffusion-based Solver for Non-convex Trajectory Optimizationcited by 19
  22. 2024Generative Modelling of Structurally Constrained Graphscited by 17
  23. 2024ParetoFlow: Guided Flows in Multi-Objective Optimizationcited by 17
  24. 2023Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Contextcited by 16
  25. 2025Generative Models in Decision Making: A Surveycited by 14
  26. 2025Learning to Reduce Search Space for Generalizable Neural Routing Solvercited by 14
  27. 2025BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimizationcited by 14
  28. 2024DiffSG: A Generative Solver for Network Optimization with Diffusion Modelcited by 13
  29. 2024Diffusion Models as Network Optimizers: Explorations and Analysiscited by 13
  30. 2025Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learningcited by 12
  31. 2024Constraint-Aware Diffusion Models for Trajectory Optimizationcited by 11
  32. 2025Preference Optimization for Combinatorial Optimization Problemscited by 11
  33. 2024DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problemscited by 10
  34. 2025Regularized Langevin Dynamics for Combinatorial Optimizationcited by 10
  35. 2025RRNCO: Towards Real-World Routing with Neural Combinatorial Optimizationcited by 10
  36. 2025Learning to Insert for Constructive Neural Vehicle Routing Solvercited by 10
  37. 2025FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimizationcited by 10
  38. 2024Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solvercited by 9

50 most cited of 216 All 216 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2026EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization
  2. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement
  3. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networks
  4. 2024Towards understanding Diffusion Models (on Graphs)
  5. 2022Travel the Same Path: A Novel TSP Solving Strategy
  6. 2022Denoising Diffusion for Sampling SAT Solutions
  7. 2026Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem
  8. 2026DGPO: RL-Steered Graph Diffusion for Neural Architecture Generation