This paper introduces a diffusion model framework for unsupervised neural combinatorial optimization (UCO). The proposed method, called Diffusion for Unsupervised Combinatorial Optimization (DiffUCO), addresses the challenge of learning to sample from intractable distributions over discrete sets without relying on corresponding training data. The key idea is to use an upper bound on the reverse Kullback-Leibler divergence as a loss function, which allows the application of highly expressive latent variable models like diffusion models in the data-free setting. The paper demonstrates that DiffUCO achieves state-of-the-art performance on a wide range of benchmark problems in combinatorial optimization. The method uses a joint variational upper bound, which is derived from an upper bound on the reverse KL divergence. This approach avoids the need for exact sample likelihoods, which is a major limitation of traditional methods in the data-free setting. The paper also proposes a more efficient version of a commonly used sampling strategy called Conditional Expectation. This method, combined with the diffusion model, allows for time-efficient generation of high-quality solutions to combinatorial optimization problems. The proposed framework is highly efficient and general, enabling the use of latent variable models like diffusion models in the ubiquitous challenge of data-free approximation of discrete distributions. The paper discusses the application of diffusion models in the discrete setting, which has been a challenge due to the intractability of exact sample likelihoods. The proposed method uses a time-conditioned diffusion model and two types of noise distributions: categorical and annealed. The annealed noise distribution is shown to be more effective in training the model. The paper also compares the performance of DiffUCO with other methods on several benchmark problems, including the Maximum Independent Set (MIS), Maximum Clique (MaxCl), Minimum Dominating Set (MDS), Maximum Cut (MaxCut), and Minimum Vertex Cover (MVC). The results show that DiffUCO outperforms other methods in terms of solution quality and efficiency. The paper concludes that the proposed framework provides a promising approach for unsupervised neural combinatorial optimization, enabling the use of highly expressive latent variable models in the data-free setting. The method is shown to be effective in a wide range of benchmark problems and has the potential to be applied to various scientific fields.This paper introduces a diffusion model framework for unsupervised neural combinatorial optimization (UCO). The proposed method, called Diffusion for Unsupervised Combinatorial Optimization (DiffUCO), addresses the challenge of learning to sample from intractable distributions over discrete sets without relying on corresponding training data. The key idea is to use an upper bound on the reverse Kullback-Leibler divergence as a loss function, which allows the application of highly expressive latent variable models like diffusion models in the data-free setting. The paper demonstrates that DiffUCO achieves state-of-the-art performance on a wide range of benchmark problems in combinatorial optimization. The method uses a joint variational upper bound, which is derived from an upper bound on the reverse KL divergence. This approach avoids the need for exact sample likelihoods, which is a major limitation of traditional methods in the data-free setting. The paper also proposes a more efficient version of a commonly used sampling strategy called Conditional Expectation. This method, combined with the diffusion model, allows for time-efficient generation of high-quality solutions to combinatorial optimization problems. The proposed framework is highly efficient and general, enabling the use of latent variable models like diffusion models in the ubiquitous challenge of data-free approximation of discrete distributions. The paper discusses the application of diffusion models in the discrete setting, which has been a challenge due to the intractability of exact sample likelihoods. The proposed method uses a time-conditioned diffusion model and two types of noise distributions: categorical and annealed. The annealed noise distribution is shown to be more effective in training the model. The paper also compares the performance of DiffUCO with other methods on several benchmark problems, including the Maximum Independent Set (MIS), Maximum Clique (MaxCl), Minimum Dominating Set (MDS), Maximum Cut (MaxCut), and Minimum Vertex Cover (MVC). The results show that DiffUCO outperforms other methods in terms of solution quality and efficiency. The paper concludes that the proposed framework provides a promising approach for unsupervised neural combinatorial optimization, enabling the use of highly expressive latent variable models in the data-free setting. The method is shown to be effective in a wide range of benchmark problems and has the potential to be applied to various scientific fields.