Research map / Image generation / Fast diffusion sampling
A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DiffUCO, a diffusion-model framework for data-free (unsupervised) neural combinatorial optimization that trains with an upper bound on the reverse KL (Joint Variational Upper Bound), avoiding exact likelihoods, and combines it with a tokenized Conditional Expectation decoding.
Problem
Data-free approximation of intractable discrete Boltzmann-type distributions for combinatorial optimization, where latent variable models like diffusion models lack exact sample likelihoods needed by reverse-KL objectives.
Approach
Upper-bound the reverse KL of the marginal model by the reverse joint KL over latent diffusion trajectories, which needs only tractable joint likelihoods, enabling diffusion models for unsupervised CO; the bound generalizes EGN (one-step case). Also introduces an annealed noise distribution and Tokenized Conditional Expectation (CE with subgraph tokens) for faster decoding.
Key results
- DiffUCO: CE achieves 38.87 MIS size on RB-large vs. 37.48 for LTFT (reported), the best neural result in that table.
- On BA-small MDS, DiffUCO: CE reaches 28.20 vs. 28.61 for LTFT (lower is better).
- DiffUCO: CE-ST8 achieves 16.30 MaxCl on RB-small, marginally above LTFT's 16.24, and 2947.53 MaxCut on BA-large, above Gurobi with 300s limit (2944.38).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply Conditional Expectation | DiffUCO · MIS RB-small | independent set size: 18.88 ± 0.06 -> 19.24 ± 0.05 | Helped |
| apply Conditional Expectation | DiffUCO · MaxCl RB-small | clique size: 14.51 ± 0.39 -> 16.22 ± 0.09 | Helped |
| use token size 8 for Conditional Expectation (ablation) | DiffUCO: CE · MIS RB-small | inference time: 0:54 -> 00:13 | Helped |
| use token size 8 for Conditional Expectation (ablation) | DiffUCO: CE · MIS RB-small | independent set size: 19.24 ± 0.05 -> 19.24 ± 0.05 | No clear effect |
| increase the number of diffusion steps during training (ablation) | DiffUCO · MIS RB-100 | relative error | Helped |
| use annealing (ablation) | DiffUCO · MIS RB-100 | relative error | Helped |
| replace Categorical Noise Distribution with Annealed Noise Distribution (ablation) | DiffUCO without annealing · MIS RB-100 | relative error | No clear effect |
| increase diffusion steps during evaluation beyond the training count (ablation) | DiffUCO · MIS RB-small | relative error | Helped |
| increase token size beyond 8 in CE-ST (ablation) | DiffUCO: CE-ST · MIS RB-100 | inference time | Hurt |
Surprising findings
- Neural UCO methods outperform Gurobi with a 300s-per-graph limit on BA-large MaxCut, while on Gset DiffUCO is second to the search method ANYCSP.
Limitations
- Learned distribution retains bias, so samples are not exactly from the target distribution.
- Memory and time costly when training on large, highly connected graphs.
- OOD generalization depends on GNN architecture and degree distribution and is not robustly designed for.
Experimental setup
Datasets: RB graphs (RB-small, RB-large, RB-100, RB-200) Barabasi-Albert graphs (BA-small, BA-large) Erdős–Rényi graphs (for Gset experiments)
Benchmarks: RB-small MIS RB-large MIS BA-small MDS BA-large MDS RB-small MaxCl BA-small MaxCut BA-large MaxCut RB-200 MVC Gset BA-huge BA-giant
Metrics: average independent set size dominating set size clique size cut size relative error approximation ratio AR* evaluation time
Baselines: Gurobi KaMIS LwtD INTEL DGL LTFT EGN EGN-Anneal
Builds on: Erdős Goes Neural Let The Flows Tell discrete diffusion models REINFORCE RAdam
Closest papers by meaning
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.91)
- Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization (NeurIPS 2024 · similarity 0.87)
- Improved Sample Complexity Bounds for Diffusion Model Training (NeurIPS 2024 · similarity 0.87)
- Efficient Combinatorial Optimization via Heat Diffusion (NeurIPS 2024 · similarity 0.87)
- Neural Flow Diffusion Models: Learnable Forward Process for Improved Diffusion Modelling (NeurIPS 2024 · similarity 0.87)
- TFG: Unified Training-Free Guidance for Diffusion Models (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.