DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization

Summary

This paper introduces DIFUSCO, a novel graph-based diffusion model for solving NP-complete combinatorial optimization problems. The authors propose two variants of the diffusion model: one with continuous Gaussian noise and one with discrete Bernoulli noise. Through extensive experiments on the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS) problems, they demonstrate that the discrete diffusion model outperforms the continuous one. The proposed DIFUSCO model achieves state-of-the-art results on TSP and MIS problems, surpassing previous probabilistic NPC solvers in both accuracy and scalability.

Strengths

Novelty: The paper introduces a new graph-based diffusion model for solving NP-complete combinatorial optimization problems, which is a novel technique to the field. Performance: The proposed DIFUSCO model outperforms previous state-of-the-art methods on TSP and MIS problems, demonstrating its effectiveness.The DIFUSCO model shows good scalability, able to handle larger problem instances that previous methods struggle with. The DIFUSCO model exhibits good generalization ability, with the model trained on TSP-50 performing well on even TSP-1000 and TSP-10000.

Weaknesses

The paper focuses on TSP and MIS problems, and it is unclear how well the proposed model would perform on other types of NP-complete problems. The DIFUSCO model, especially with discrete diffusion, does not perform well on ER graphs. The performance of the DIFUSCO model relies on 2-opt local search post-processing. Which of the model and 2-opt is the major contribution to the final performance? The proposed DIFUSCO shares similar representation with GNN-based solvers. What are the substantial advantage over the GNN-based ones?

Questions

The authors hypothesize that the poor performance due to the use of an edge-based Anisotropic GNN, whose inductive bias may not be suitable for ER graphs. Could the authors elaborate more on this issue? Are there potential modifications to the model that could improve its performance on ER graphs? Could the authors provide more details on the performance of the model without post-processing? Furthermore, are there potential improvements to the model that could reduce its dependency on post-processing?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Societal impact of the work is not discussed in this paper. Furthermore, limitations of the proposed technique need further discussions. Maybe solving a real-world application can be helpful.

Summary

This paper proposes and evaluates the use of diffusion models for solving combinatorial optimization problems on graphs. The goal is to construct a probability distribution on the solution space that puts weight on high-quality solutions. First, a dataset of optimal or near-optimal solutions is generated offline with a problem-specific solver. Then, a diffusion model is trained in a supervised manner to maximize the likelihood of these solutions. Finally, during inference, new solutions are generated from white noise, and put through a post-processing step to ensure feasibility. Since many combinatorial problems exhibit a graphical structure, the diffusion model is based on a message-passing graph neural network. To handle binary vectors, both discrete and continuous diffusion schemes are explored. An accelerated inference scheme is suggested, along with several solution decoding and improvement heuristics. An extensive set of benchmarks underlines the efficiency of the method compared to numerous alternatives from the state of the art.

Strengths

### Originality The main innovation here is the adaptation of diffusion models from image generation to combinatorial optimization. It comes with a shift from convolutional to message-passing neural architectures, as well as other design questions like choosing the best type of noise process. The combination of these known ideas is more than sufficient in terms of novelty. ### Quality It is an extremely solid study in all regards. The new methods are carefully justified and well-situated with respect to previous work. The experiments are impressive in their breadth, and they do highlight the performance and promise of graph-based diffusion models. ### Clarity I really enjoyed reading this paper. The authors are clear and honest, they do not resort to useless mathematical details to obfuscate their main contributions. The appendix is very thoughtfully designed, especially the FAQ section at the beginning which underlines the main motivations. ### Significance The change of paradigm from images to graphs in diffusion models is a great foundation for future work. While it is not a huge theoretical leap, it takes some good ideas and craftsmanship to get it right, and that's what the authors showed. I am excited to see what comes out of it.

Weaknesses

### Originality n.a. ### Quality n.a. ### Clarity It would help to specify why distribution multimodality is so important for solution generation, since that seems to be a main argument in favor of diffusion models. ### Significance The main limitation that I see is that this approach requires access to a dataset of high-quality solution, which is costly to generate. I think the method also generalizes to unsupervised learning without much additional headache, maybe that is worth discussing as a perspective?

Questions

L49: Why are non-autoregressive models limited in expressiveness? L75: For symmetry maybe you could include related work on the third avenue from the state of the art, namely iterative improvement methods? L83: Do all best-performing methods use attention nowadays? L130: Would some form of regularization help in the loss? L182: The justification of your choice of network is a bit vague, can you elaborate? L236: Is sparsification done before or after exact solving with Concorde / LKH? L244: I feel like tour length and drop are redundant, even though the averaging over instances makes them different. Why include both? Also, the combinatorial optimization world usually prefers "(optimality) gap" in terms of nomenclature. L279 (Table 2): If the runtimes are not comparable, why include them? L321: Can you elaborate on the inductive bias of your architecture for ER graphs? Appendix L40: If the runtime is not meaningful in Table 1, why report it in Table 2? Appendix L220: Which benchmark studies are you referring to?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Limitations are well discussed in the paper. Societal impact is irrelevant.

Summary

The paper, "DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization," introduces a novel methodology for solving NP-Complete combinatorial optimization problems using graph-based diffusion models, named DIFUSCO. By formulating each NP-Complete problem as a {0, 1}-valued vector with N variables that represent node or edge selection in candidate solutions, and employing a message passing-based graph neural network for instance graph encoding and variable denoising, DIFUSCO addresses the limitations of existing solution generation methods. Specifically, it performs parallel inference with fewer denoising steps, models a multimodal distribution via iterative refinements, and uses efficient, stable supervised denoising for training. The authors show DIFUSCO's superior performance over previous probabilistic solvers for two NP-complete problems, the Traveling Salesman Problem and Maximal Independent Set, using benchmark datasets.

Strengths

Novel Approach: The paper introduces DIFUSCO, a novel approach that combines discrete diffusion models with improved fast unfolding of communities for combinatorial optimization problems. This new methodology could potentially open up new research directions in the field. Thorough Experiments: The authors have conducted comprehensive experiments to validate the performance of DIFUSCO, considering different model configurations and problem scales. The experiments and the comparison with existing methods are rigorous and well-documented. Balancing Exploration and Exploitation: The authors consider the trade-off between the number of diffusion steps and the number of samples, which is a critical aspect in the field of optimization.

Weaknesses

Computational results: the numerical results on the benchmark problems don't show very significant improvement. The traditional heuristic method still performs better. Complexity: The DIFUSCO model and its components, such as the discrete diffusion and the unfolding of communities, can be quite complex. This might make it difficult for some practitioners to fully understand and implement the method. Dependency on External Solvers: The model relies on external solvers (like Concorde and LKH-3) for generating and labeling training instances, which might limit its applicability in settings where these solvers are not available or not preferred. Limited Benchmark Problems: While the TSP is a widely used benchmark, it would be helpful to see how DIFUSCO performs on other combinatorial optimization problems to demonstrate its generality. Computationally Expensive: The method seems to require substantial computational resources, especially for large-scale problems, which could limit its practical application in resource-constrained settings. Lack of Analysis on Hyperparameters: There seems to be a limited discussion about how different hyperparameters, such as the number of diffusion steps or the noise schedule, affect performance. Some more insights into these aspects would enhance the utility of the proposed method.

Questions

see the weakness

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/a

Summary

This paper proposes a new, non-autoregressive, approach to Neural Combinatorial Optimization. As in similar non-autoregressive NCO works, a heat map characterizing the likelihood of a node being part of a solution is generated. The novelty is in the use of a generative model based on diffusion, trained in a supervised way on a sample of problem instances with pre-computed solutions as ground-truth. Two standard variants of diffusion, discrete and continuous, are proposed and experimented, as well as a (standard) trick to speed up test time diffusion. Performance comparisons with a number of NCO baselines are provided, both when test and training data are from the same distribution and when test instances are an order of magnitude larger than the training ones. The approach is tested on two distinct CO problems: TSP and MIS.

Strengths

1. The paper presents a novel diffusion approach for CO, that nicely extends a previous work that was based on image diffusion [22], to better represent the generation process for CO problem solving 1. The resulting proposal is fairly original, clear, and of good quality. 1. The fact that two distinct problems can be addressed by the same architecture is a favorable indicator of the breadth of the method. 1. The comparison with prior work is fairly extensive.

Weaknesses

1. The performance on large TSP instances seems to significantly rely on the 2-opt heuristic. Indeed the addition of 2-opt allows to gain about one order of magnitude in the results of DIFUSCO: Table 2 -- e.g. for TSP10000, the opt gap drops from more than 30% with a greedy or sampling strategy to about 3% after applying a 2-opt. 1. In general the use of 2-opt in the greedy decoding (line 242) considerably biases the results of Table 2. The performance of any of the compared models would likely also be boosted if the same 2-opt were applied at the end. 1. Autoregressive models are criticized for the "quadratic complexity" in their attention mechanism (line 83). One (standard) way to mitigate it is by limiting a priori (using a mask) the number of tokens allowed to influence a token. DIFUSCO is presented as a solution to this complexity bottleneck, but it actually faces the same problem in another form and uses a similar solution (Sec 4.1, paragraph "Graph sparsification", line 238). 1. Section 3.2 and Eqs. (4)-(8) are essentially a copycat of the cited sources, in particular [5,12,28]. It is too detailed for cursory reading, but not detailed enough to really understand without going back to the source. A Bayesian network diagram specifying the class of conditional probability of each variable could be more clear.

Questions

1. Could the authors motivate the formula of line 211 to rank the edges. Is it likely to apply to other CO problems beyond TSP? 1. In Table 1, how is the optimality gap computed exactly? The reported value of -0.01% implies that the solutions are better than the optimal solutions returned by Concorde.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Technical limitations are not explicitly mentioned. Societal impact is not discussed either, but none is apparent, beyond the non-specific impact due to being part of AI research.

Summary

This paper investigates using diffusion models to solve combinatorial optimization problems. The authors propose two alternative methods to adapt diffusion models to this task: (1) a discrete diffusion model with Bernoulli noise, and (2) a more standard continuous diffusion model, where post-processing is needed to produce a discrete prediction.

Strengths

1. The paper is well-written. My background is more in combinatorial optimization, and I am familiar with standard diffusion models. The authors very clearly explain the presented methods, which is quite impressive given the space limitations. 2. The methodologies appear sound, and the design decisions are presented with accompanying rationale. 3. The computational experiments are very thorough and show the proposed algorithms give high quality solutions in low computational times. The results are discussed clearly.

Weaknesses

1. The feasibility of a solution is only treated as a Boolean (zero or infinity in eq. 1). This removes information that could be given to the solver regarding how close to feasible a particular solution is. 2. It is slightly that most implementation details (sections 3.3, 3.4, etc.) are in the appendix. It would be nice to give some summaries in the main text, especially of key components such as decoding strategies, but I understand this may not be possible given the space limitations. 3. The solution generalizability is slightly limited. In combinatorial optimization, the best solution strategy often changes depending on the graph (problem) sparsity. It would be a nice result to investigate sensitivity to problem sparsity for TS or pairwise connection probability for MIS.

Questions

1. Solution times are missing from Table 1.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Not presented, but not particularly relevant.

Thank you for the response

Thank you for the response. I see from the results even without 2-opt the proposed model can achieve the best results in many comparisons. The other concerns have also been addressed. The introduction of diffusion model in neural solvers might represent new progress in this field. One evidence is that it is able to train on 10000-dim TSPs while most previous ones can only train on 100-dim. I would like to raise my score from 4 to 7.

Thanks for the rebuttal

I thank the authors for their concise answers. After reading the rebuttal and the other reviews, I confirm that I remain supportive of the paper acceptance.