Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper develops a methodology based on supervised learning (as opposed to reinforcement learning) for the purpose of neural combinatorial optimization (NCO), and in particular for the traveling salesman problem (TSP). In this direction, the authors first propose a set of four data augmentation methods (rotation, symmetry, shrink and noise), which augments the original set of data without affecting the label of the optimal solution. This allows to extract sufficient information from a small set of high-quality labeled solutions.  Subsequently, the authors introduce a new bidirectional supervised loss, which  leverages the equivalence of solutions for the TSP, e.g., a path remains an optimal solution is we reverse the directionality of all edges, or if we cyclically shift the path by any amount. The paper then builds upon these two ideas and introduces the SL-DABL algorithm for NCO training.

The authors then conduct an extensive experimental study, where they train POMO with their supervised learning framework (instead of reinforcement learning), and show that they can achieve state-of-the-art results with only 50,000 high-quality training instances. Furthermore, they provide encouraging results of better generalization performance to test instances of different sizes that the training instances.
strength_and_weaknesses: Strength
- The paper is well written and simple to follow. The various ideas are clearly stated and written down in sufficient detail.
- The motivation is interesting. RL may not necessarily be the best choice for training, as the authors argue. They provide an interesting alternative and are able to outperform POMO training with RL. Their results on TSP20, TSP50 and TSP100 are state-of-the-art compared to the surveyed approaches and thus supportive of the proposed supervised framework.
- Despite being simple, the proposed ideas are based on sound theoretical fundamentals (e.g., invariance of optimal solutions under certain transformations).
- The experimental compares to various solvers (traditional and NCO). Furthermore, the ablation study sheds light on the individual components of the proposed framework.

Weaknesses
- The paper makes a bold statement already in the title, i.e., that supervised learning is powerful for NCO. However, both the theory and the experiments are specifically tailored for the TSP problem. I am concerned that this big claim is not really supported in the paper. The scope of the paper is limited to TSP, and any evidence in favor of NCO will necessarily come from TSP only. This is not just about being precise. My main source of concern is that the proposed data augmentations and bidirectional loss are mainly meaningful for the TSP, but may not be applicable for other challenging combinatorial problems such as capacitated vehicle routing problem, or the 0-1 knapsack problem. If the authors wanted to make such a general statement, then they should have studied more problems (with possibly different sets of data augmentations and invariances/symmetries), and show that supervised learning is powerful for these problems, too.
- Related to the problem above, the scope is limited. I think the paper would have benefitted from including more problems, or alternatively, by arguing how the proposed ideas are more widely applicable to problems other than TSP. In the current exposition, it seems to me that the story is almost exclusively about TSP.
- The generalization results are somehow encouraging - indeed, compared to POMO with RL, the proposed framework achieves better results. However, I am not convinced that the proposed symmetries can inherently improve generalization to instances of varying lengths. I think they should enhance learning efficiency for instances of a fixed length, and this is aligned with the results on TSP20, TSP50, and TSP100. But I do not really see how their design can inherently lead to improved generalization. Also, note that POMO with RL suffers from poor generalization power - so, even if the proposed framework improves upon POMO with RL, this alone is not necessarily a sign of good generalization power.
- The novelty is not strong. The proposed framework is mostly based on simple properties of the TSP problem. This is not necessarily a problem by itself, but it could be an issue when coupled with the limited scope of the paper.
clarity,_quality,_novelty_and_reproducibility: - The paper is very well written and the proposed ideas and claims are clear.
- Both the theory and the experiments are generally well supported and the paper does not make unsubstantiated claims. One exception regards the bold statement about NCO. The scope of the paper is limited, and I do not personally see how it shows that NCO in general can benefit from supervised learning.
- The novelty of the work is not strong. The ideas are sound but based on rather simple invariances/symmetries of the TSP problem. That said, they seem to result in much improved optimality gaps.
- The authors have run the other algorithms by themselves with the codes and pretrained models from their official implementations. Regarding their framework, they have not released the code yet, but their results could be reproduced if they later do so, since the experimental details are provided in the appendix.
summary_of_the_review: The paper is well-written and proposes a sound framework for improving the TSP problem with supervised learning. The empirical results look good, even though I am not personally clear that the generalization power for the new framework is strong. The main reason why I am on the fence is because I feel that both the scope and the novelty are not significant, which is a concern for a top-tier venue like ICLR.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new supervised-learning method for combinatorial optimization problems. One of the main contributions of the paper is the introduction of four types of data augmentation in training (i.e., Rotation, Symmetry, Shrink, and Noise). Another contribution is a new bidirectional loss, in which given the optimal solution, the training process will only minimize the autoregressive likelihood for the starting point and direction of minimal loss. Experiments show that due to more informative gradients from the annotation, the supervised neural solver can outperform reinforcement learning methods on TSP-20/50/100 problems.
strength_and_weaknesses: Strength

1. The paper proposes to train the supervised learning (SL) method with the POMO framework, i.e., autoregressive decoding, and show that with data augmentation and a novel loss objective, SL can actually achieve better performance than reinforcement learning (RL), which overthrows the conclusion from [1].

2. The empirical results also show that the SL method trained on TSP-100 can achieve better performance on TSP-150/200/250/300 than RL (i.e., POMO) method, which again overthrows the conclusion from [1].

3. Overall, I believe the results from this paper could help the NCO community rethink the role and value of SL and RL.


Weaknesses

1. My main concern is the empirical effectiveness of data augmentation. As shown in the paper, in four types of data augmentation in training (i.e., Rotation, Symmetry, Shrink, Noise), rotation and symmetry are the most effective ones. However, in the graph neural network community, equivariant neural networks [2,3] can directly model an equivariant function without any data augmentation and significantly outperforms data augmentation methods. I am wondering if the authors have considered these equivariant neural networks.

2. The idea of minimizing the minimal loss from a set of candidates is not new in the literature of combinatorial optimization. For example, [4] applied it to the minimum independent set problem.


Typos:

Page 3: "Kwon et al. (2020) has discussed how to use the data augmentation methods to improve the inference
performance for NCO but not for RL-based training." ==> "have", "but not for *SL*-based training."


[1] Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning tsp requires rethinking generalization. arXiv preprint arXiv:2006.07054, 2020.

[2] N. Thomas, T. Smidt, Steven M. Kearnes, Lusann Yang, L. Li, Kai Kohlhoff, and P. Riley. Tensor field networks: Rotation- and translation-equivariant neural networks for 3d point clouds. ArXiv, 2018.

[3] Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E(n) equivariant graph neural networks, 2021b.

[4] Li, Zhuwen, Qifeng Chen, and Vladlen Koltun. "Combinatorial optimization with graph convolutional networks and guided tree search." Advances in neural information processing systems 31 (2018).
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and technically correct.

However, the data augmentation method and bidirectional loss proposed in the paper are not very novel in my opinion. Please see the weaknesses above.

Since the paper is mainly based on the open-source POMO, I think the reproducibility of the paper should be ok.
summary_of_the_review: The paper provides a strong empirical study of data-efficient supervised learning for NCO, and could help the NCO community rethink the role and value (e.g., generalization & convergence speed) of SL and RL. However, the data augmentation method and bidirectional loss proposed in the paper are not very novel in my opinion.

Therefore, I would recommend a score of 5 for the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a supervised learning algorithm called Supervised Learning with Data Augmentation and Bidirectional Loss (SL-DABL) for traveling salesman problems (TSP). There are two components in the approach. The data augmentation method leverages several equivalence properties of traveling TSP, e.g., the optimal solutions stay the same for problems transformed with rotation, horizontal flip, scaling, etc. The bidirectional loss leverages the fact that the same route can be represented in different ways, e.g., via starting from different nodes. They evaluate their approach in the setting where there are 50K training samples with optimal solutions, and compare their approach to several reinforcement learning and supervised learning baselines as well as the non-learning-based solvers. They demonstrate that their approach achieves better optimality gap compared to learning-based approaches, while the inference time is also much shorter than classic non-learning solvers for combinatorial optimization problems.
strength_and_weaknesses: Strengths:

1. The proposed approach is simple yet effective for solving TSP with neural networks, and it is model-agnostic.

2. Their approach achieves better generalization to larger TSP instances compared to the POMO baseline.

Weaknesses:

Overall, I think the proposed approach is specific to TSP. Both data augmentation and bidirectional loss design leverage the properties of TSP itself, and are not applicable to most other combinatorial optimization problems. To show that the approach is effective for more problems, the authors should also present results on Capacitated Vehicle Routing problems (CVRP), where there have been several works on designing learning algorithms for CVRP (e.g., [1][2][3][4]).

Meanwhile, I wonder whether the proposed SL-DABL algorithm is effective for different training data sizes. In general, the advantage of RL approaches is that they do not require optimal solutions for training. While 50K samples in the current setting is smaller than some prior works, it is not a small number either. Therefore, it is helpful to study how SL-DABL compares to other baselines when the training size is even smaller, and whether the approach can achieve better performance with more training data.

Also, the authors should study the effect of SL-DABL with different model architectures, especially those with some equivariance properties already incorporated in the architectural design. For example, the authors can evaluate on GCN and see whether their training algorithm can improve the performance.

[1] Kool et al., Attention, Learn to Solve Routing Problems! ICLR 2019.
[2] Nazari et al.,  Reinforcement Learning for Solving the Vehicle Routing Problem, NeurIPS 2018.
[3] Chen and Tian, Learning to Perform Local Rewriting for Combinatorial Optimization, NeurIPS 2019. 
[4] Kwon et al., POMO: Policy Optimization with Multiple Optima for Reinforcement Learning, NeurIPS 2020.
clarity,_quality,_novelty_and_reproducibility: The paper writing is clear, and the approach is sound. Although the code is not provided, the results should be reproducible given the simplicity of their approach.

However, in general I think the novelty of this work is limited. Data augmentation is not a new idea for general machine learning community. The proposed SL-DABL algorithm is specific to TSP, and I don't think it is extensible to general combinatorial optimization problems. Also, this work is not the first one considering equivariance properties of TSP, and there are prior works leveraging these properties at the inference time [1] and in the architecture design [2]. Thus, the technical significance is not enough.

[1] Kwon et al., POMO: Policy Optimization with Multiple Optima for Reinforcement Learning, NeurIPS 2020.
[2] Ouyang et al., Generalization in Deep RL for TSP Problems via Equivariance and Local Search.
summary_of_the_review: This work presents good empirical results for TSP compared to prior learning-based approaches. However, the proposed approach is specific to TSP, and is not generally applicable to other combinatorial optimization problems. Meanwhile, the evaluation setting is a bit restricted, and some aspects of the approach are not well-studied. Therefore, I recommend a rejection.


----------
I thank the authors for the response and new experiments. I understand that the time for revision and adding experiments is short, but I still feel that the current experiments are insufficient and the scope of this work is limited. So I keep my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Neural Combinatorial Optimization (NCO) with supervised learning suffers from data inefficiency when applied to the Traveling Salesman Problem (TSP). This paper proposes a series of data augmentations using properties such as rotation and symmetry invariance of TSP solutions in 2-D, along with a bidirectional loss function. With only 50,000 training examples, the proposed algorithm achieves SOTA on 2-D TSP.

strength_and_weaknesses: Strengths
- The overall idea is intuitive and simple. The augmentations are easy to implement and the bidirectional loss is neat.

Weaknesses
- In Algorithm 5, what is the motivation for the augmentation procedure of rotation or symmetry + shrink + noise? An intuitive augmentation procedure would be to employ random chance of rotation + random chance of symmetry + random chance of shrink + random chance of noise.
- It seems like the strategies are geared towards TSP problems, but what about other combinatorial optimization problems? Do the frameworks scale to all CO problems that can be formulated on graphs?
clarity,_quality,_novelty_and_reproducibility: The paper is clear and of high quality. The ideas are novel in the ML for CO literature, but are borrowed from concepts that are increasingly prevalent in other deep learning settings.
summary_of_the_review: Overall, the paper is interesting and presents intuitive methods. It is easy to read and the results are well-supported. My key question remains on whether it is generalizable beyond TSPs only.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper considers supervised training of neural networks for solving combinatorial optimization problems. They study the effect of data augmentations on generalization. The key finding is that data augmentations are key to successful training (and non0overfitting) of supervised training, whilst reinforcement learning based approaches to learning neural solvers do not benefit from data augmentations. 
strength_and_weaknesses: The underly idea of this work is the following: combinatorial optimization problems often have symmetries, where certain modifications to the problem do not change its solution. Since these modifications do not change the solution they make suitable data augmentations for use during training [or indeed better still the invariances are built into the model architecture]. There may also be modifications of the problem that do change the solution, but change it in a predictable, easily computed way, some of which are considered in this work. 

**Strengths**

- Paper is clearly written and easy to quickly ingest the main points and contributions.
- Observation that RL doesn't benefit from augmentations while supervised does is interesting.

**Weaknesses** 
- The paper is not suitably contextualized within the contributions of prior work. The appearance is given that augmentations have not been considered before for neural combinatorial optimization. But this is far from true - for instance this paper https://arxiv.org/pdf/2110.10942.pdf also considered data augmentations for TSP. Although I am not certain myself, I would not be surprised if another reviewer is aware of prior work on augmentations and RL for NCO - RL for NCL is a really well studied area so the idea that people do not already know that augmentations are not all that useful sounds unlikely to me [but I will wait on this last point to see if anyone actually knows a suitable reference for this].
- Contributions are stated in a more general form than they actually manifest. Specifically, the authors consistently conflate "neural combinatorial optimization" (NCO) with the TSP problem. For instance the phrase "With these two powerful methods, we propose a novel Supervised Learning with Data Augmentation and Bidirectional Loss (SL-DABL) algorithm for NCO training". This algorithm isn't a general NCO method, it is specific to TSP.
- Evaluation is limited to TSP. 

clarity,_quality,_novelty_and_reproducibility: Paper is well enough written that the ideas are easy to understand very quickly. 

Novelty is the main issue with this work: the two main points of this paper are 1) augmentations help supervised training, 2) but not RL training. The first point is well known, and the paper uses standard rotations, reflections etc. that are all very known symmetries of TSP. 

Method seems reproducible enough since hyperparmaeters are explained and the authors implementation builds on an existing implementation for POMO (Kwon et al., 2020). But not code is given and no mention of releasing code is made so it would take significant effort from any reader to attempt to reproduce the results in this paper as the new. components - augmentations etc. - would have to. be implemented from scratch.
summary_of_the_review: Whilst the authors are pursuing an important and open question of how to train more effective neural solvers for combinatorial problems, the current paper lacks novelty or conceptual contribution. I would suggest to the authors that they generalize their results to other problems, or seek more depth in their TSP studies.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies a neural combinatorial solver for the TSP problem. The main contributions lie in the diverse set of data augmentations that facilitate more data-efficient neural solver. Reviewers are in general consensus that the paper is not ready for acceptance. While the paper has its merits in studying meaningful techniques specialized to the TSP problem, the flaws are outweighing the merits. Reasons are the narrow scope of the solver to TSP problems, the narrow applicability of the augmentation tricks to other CO problems. In conclusion, the scope is so narrow that a more pronounced technical method with enhanced novelty is expected, or at least more sufficient empirical study is needed. However, we can see neither. The preliminary study on CVRP problems of very small size cannot lead to definitive conclusion that the approach is of high practical utility. Hence, the paper needs a major revision to be considered publishable at a top venue.
justification_for_why_not_higher_score: Reviewers are in general consensus that the paper in its current form is not ready for publication. AC finds no evidence to override this decision.
Decision: Reject