Combinatorial Optimization (CO) problems are often NP-hard, thereby hindering the collection of solutions for supervised learning. Probabilistic method can provide an unsupervised framework, however, inference on it is intractable in general, and the objective is typically non-convex. Our work proposes an unsupervised method to learn a variational distribution for a graphical model, from which we can efficiently sample good solutions for CO problems. We show that our designed graphical model is guaranteed to concentrate on good solutions in both constrained and unconstrained scenarios. Additionally, the graphical model naturally introduces a temperature with which we are able to ease the learning by avoiding (encouraging) local optima during the beginning (ending) of training. We demonstrate our unsupervised learning framework on three CO problems on both synthetic and real-world graphs. The results show that our method achieves performance significantly better than other unsupervised neural methods as well as classical methods and integer solvers.