Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: Combinatorial optimization problems often have numerous symmetries. This work proposes to leverages these symmetries to improve the training of neural networks that have been proposed in other works to solve such combinatorial optimization problems.
More specifically, the paper:
  * precisely defines two types of symmetries it wants to leverage, covering both symmetries that are inherent to the formulation of these problems and symmetries that are intrinsic to the solution spaces of such problems.
  * Proposes a regularization scheme to help the neural network learn for the symmetries
  * Evaluate their approach extensively on 4 common combinatorial optimization problems.
strengths_and_weaknesses: Overall the paper is well written and fairly easy to follow. However, it's unclear how the authors came up with equation 5 and 6. It looks like the authors don't need to mathematically define Lss and Lps (which is why they never do so in the paper), but instead directly tweak the corresponding gradients in order to build two regularization gradients. The paper would be much easier to follow if that was clearly stated, and the process the authors went through in order to build these 2 gradient terms was spelled out.
  
Since I am not sure how the authors came up with equation 5 and 6, I didn't check the correctness of the maths, so at this point I cannot vouch for the theoretical soundness of the approach. That said, the experimental results look good, so I'm optimistic that the maths will check out. I am looking forward to more explanations from the authors in the rebuttal. 

The various graphs in figure 6 are drawn for varying numbers of training steps. Why not use a consistent number of steps ?

Previous work have proposed to take advantage of symmetries to improve the generalization, mainly by leveraging symmetry invariant neural networks architectures, or by leveraging problem specific symmetries. As far as i know, this is the first work that proposes a solution that can be applied to any neural network, which is a significant innovation.

The evaluation shows that Sym-NCO results in better quality of results on all 4 benchmarks the approach was evaluated on. Furthermore, it gets these results at least as fast as the fastest other approach it was compared against. This is extremely significant.


questions: Can you detail how you came up with equations 5 and 6 ? If needs be, you can add the relevant text to the supplemental material as you did for the proof of theorem 2.1. This would really help convince me of the soundness of your approach.

What does gr refers to in table 1?

In section 5.2 you mention that you applied Sym-NCO to POMO, AM, and PointerNet. Which one did you use to gather the results in Table 1 and 2 ? It would be interesting to be able to compare the 3 versions against their corresponding baselines whenever possible.

Would it be possible to extend your your comparison with EGNN to also train the EGNN model with your loss ? I'd love to see to what extend your approach is complementary to that of EGNN, in which case you should be able to improve on the performance reached by the EGNN model by training it with your loss. 

 

limitations: Nothing of note here.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work is in the area of learning to approximately solve TSP, CVPR, and the associated class of routing problems using deep reinforcement learning.

The main methodological contribution is to identify that routing problems and their solutions often contain symmetries such as **rotational symmetry** or the **cyclical nature** of the solutions. The paper proposes **new loss functions** that **softly incorporate symmetries** for the encoder-decoder architecture from AM (Kool-etal) and POMO (Kwon-etal). 

Training models via the proposed loss functions (termed 'Sym-NCO') improve over the models trained via previously proposed loss functions on random routing problem instances as well as on real-world instances from TSPLib.

==========

Post rebuttal: Thank you to the authors for partially addressing my concerns. I have updated my score based on the responses. In particular, I was not fully convinced regarding statements on the (lack of) expressive power of equivariant networks, e.g. “ENN scheme provably guarantees to trained in symmetric space; more expression power is needed for CO tasks”. I apologise that I am unable to engage actively in author discussions at this time as I have fallen ill after traveling.

==========

Post author discussions: Thank you for addressing my concerns regarding the claims on expressive power and hard vs. soft invariant learning. I believe this work demonstrably improves the performance of NCO solvers by leveraging appropriate symmetries, and these empirical findings may be of interest for the broader community working on combinatorial problems beyond routing. I have updated my score with these considerations.
strengths_and_weaknesses: Strengths:
- **Clear motivation**: The paper does a good job at presenting ideas around how routing problems and their solutions often contain symmetries such as rotational symmetry or the cyclical nature of the solutions. The figures are very instructive.

Weaknesses:
- **Unclear writing and presentation**: There are several aspects of the paper where the writing and presentation was unclear to me. I have listed this down under the **Questions** part of my review.
- **Counterintuitive results** and **lack of justification**: The results in Section 6.1 around approximate vs. exact rotation invariance are counterintuitive as they suggest to me that rotation invariance is in fact not desirable (because when it is enforced exactly, the model is unable to perform at all). However, these findings are not sufficiently justified or understood (see **Questions** section). I may have misunderstood the results or may be missing something here.
- **Insufficient discussions on related work**: There are several recent works which as based on incorporating symmetries to improve learning for routing problems, but are not discussed in this paper, e.g. [Hudson et al.](https://arxiv.org/abs/2110.05291) obtained strong results via a **rotationally invariant GNN** via converting graphs to line graphs, [Ma et al.](https://arxiv.org/abs/2110.02544) proposed positional encodings that incorporated the **cyclical nature** of routing problems, [Ouyang et al.](https://arxiv.org/abs/2110.03595) performed **preprocessing** to make the model (approximately?) invariant to rotations. The Related Work section does not do enough to contextualise present work w.r.t. recent advances in the community, which may be doing something similar or tangential to the present approach. In the best case, it would also be good to empirically compare to these techniques.
questions: Following the **Weaknesses** part of the review, there were several parts of the paper where the writing and presentation were unclear to me:
- Lines 1-3, Abstract, states that DRL has merits over traditional CO solvers because DRL does not need supervised data. To the best of my knowledge, traditional CO solvers (which include Concorde or LKH) also **do not** need supervised data. Could the authors clarify this statement?
- I was uncertain what the relationship of Eq. 4 and Eq. 5/6 were to Eq. 1. I understand that they are components of the overall loss L_sym in Eq. 3, however, **how is L_sym used to model Eq. 1**?
- In the results in Table 1 and 2, it appears as if Sym-NCO is a model by itself. On the other hand, the experimental setting states that Sym-NCO is applied to POMO, AM, and PointerNet. Could the authors clarify which of the **underlying models** were trained for each row of results highlighted as Sym-NCO? 

In addition to the questions on writing/presentation, here are additional questions regarding **approximate vs. exact rotation invariance** in Section 6.1:
- I found the results in Section 6.1 extremely counterintuitive. The results seem to suggest that provable rotation invariance is **actually undesirable**, and the authors have tried to justify this by saying that nudging the model to be approximately rotationally invariant makes it more **'flexible'** and maintain its 'representation capability'. In my opinion, the justifications are rather hand wave-y. Could the authors be more precise in defining these terms?
- As a continuation of the previous point, in my opinion, the curves in Fig. 6 show one of two things: (A) rotational symmetry is irrelevant to the problem, so EGNNs are not useful and unable to learn the task well (as seen by their fluctuating performance); or (B) the approximately rotationally invariant models are **overfitting on the data distribution** that is being used for training and validation (both are randomly generated in the same size range). Is this how one should interpret these results, or would the authors disagree? 
- Finally, could the authors provide some implementation details of the EGNN used?

Finally, I had some other minor questions or nitpicks to mention:
- Titles of Sections 3.1 and 3.2 state that the symmetries are being **'imposed'**. However, in my opinion, this may be **misleading** as the symmetries are only approximated, not imposed. E.g. the encoder model's output features are only approximately invariant to rotations (unless using models which are provably rotation invariant).
- It was unclear to me why there are no empirical comparisons to the **improvement-style NCO models**. Could the authors justify this decision?
limitations: The authors have included several technical limitations of the present work and avenues for future research. They have **not included** any sections on **potential negative social impact**, and this should at least be addressed. Is it likely that this type of research may be put in production in the logistics or transportation industry, and if so, what may be some considerations to make?

In my opinion, one major limitation of this work is the **lack of justification** or understanding of **approximate vs. exact rotation invariance** in the hidden representations of the encoder. E.g. is rotational symmetry even relevant in real world datasets beyond synthetic and random TSPs/CVPRs? As such, **real world** maps and cities have a **canonical set of coordinates** and **directions** (north, south, east, west). This is to say that, in a city where I may have many locations that I would like to navigate through, I always have an aligned or fixed set of coordinates as inputs - there doesn't seem to be a good reason to arbitrarily rotate them.  

It is worth considering whether methodological developments on synthetic tasks may be useful for the corresponding real-world applications in routing.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the problem of training neural networks to solve NP-hard CO problems. Recent works have sought to apply ML to CO, but often fall short of outperforming the state-of-the-art handcrafted heuristics; methods which neural networks have the potential to surpass in both optimality and solving time. To address this, the authors first identify that CO problems have underlying symmetries in both their problem definition and their corresponding solutions. The authors reason that explicitly learning these symmetries will implicitly aid learning to find near-optimal solutions quickly. To this end, the authors propose a new loss function which guides the network towards finding optimal solutions whilst also learning embeddings which retain these symmetries; an achievement which the authors implicitly reason makes learning to solve such CO problems more tractable for RL. Moreover, the authors claim that their loss function formulation is agnostic to the specific CO problem considered, and that it can be applied to and improve any prior neural CO solver from the literature. The authors demonstrate their proposed loss function's efficacy on four CO problems (TSP, CVRP, PCTSP, and OP), and claim to surpass all ML baselines on all four CO problems.
strengths_and_weaknesses: Strong points:
* Addresses an important and significant application area of ML, namely solving NP-hard CO problems.
* Proposes a novel and original loss function which guides the network towards learning the underlying symmetries of CO problems in addition to learning to find near-optimal solutions.
* The proposed approach is seemingly easy to integrate with existing ML-CO solvers and is therefore complimentary to a broad variety of prior work.

Weak points:
* The paper/writing is unclear in multiple areas (see below).
* The $100$ node problem sizes considered are significantly smaller than those of prior works.
* The Experiments section in general has multiple shortcomings and inconsistencies (see below).
* The Related Work section is incomplete and may not sufficiently place this work in the context of the current literature.
questions: ### Introduction & Methodology

* **'Solution symmetricity and shared features' clarification:** In the Introduction when the authors introduce the two types of CO symmetry they consider, they say: ‘Second, the solution symmetricity, which is the shared feature among solutions having identical optimal values.’ I find this sentence difficult to understand - do the authors just mean that solution symmetricity is where solutions have the same value? What is the ‘shared feature’, and why do the values necessarily need to be optimal? In Definition 2.2, the authors state that two solutions are symmetric when their total returns are equal; nothing about optimality is mentioned as far as I can tell.

* **'Pre-identified symmetricites' clarification:** In the Introduction, the authors mention that their novel learning scheme ‘imposes symmetricities by leveraging the pre-identified symmetricities’. Does ‘pre-identified symmetricities’ refer to the problem and solution symmetricities, or some pre-identification method? This jargon should be explicitly defined in my view for clarity.

* **Difficulty of solution symmetricity identification:** In the Introduction, the authors state that problem symmetricity is found in all CO problems in the form of rotational symmetricity, but that solution symmetricity cannot be identified easily as the ‘properties of the solutions are distinct for every CO problem’. What specific properties are distinct? Is solution symmetricity where two solutions result in the same return (as stated in Definition 2.2), in which case why is it not easy to evaluate whether two solutions are symmetric?

* **Overall motivation and intuition:** I think the Introduction and Discussion is missing some motivation for the overall idea. Why do the authors think it is fundamentally beneficial to account for symmetricities in the learning scheme? Are there state-of-the-art solvers which do this, or are the authors relying on some intuition that explicitly learning CO symmetricities will lead to a parameterised network more able to find solutions in fewer steps since it will have learned to find multiple policies which lead to the same near-optimal reward, and therefore have greater chance of generalisation at test time? I think a discussion of what motivated the idea and what the intuition is behind it is currently missing from the paper.  

* **Inconsistent jargon:** In the Sym-NCO Methodology, is the ‘invariant representation symmetry’ just the ‘problem symmetricity’ referred to elsewhere? If so, I think it would be good to keep jargon to a minimum by consistently referring to the various phenomena being discussed by the same names. If not, then I have misunderstood what is being discussed here.

* **Solution sampling methodology:** How exactly are the $K$ and $L$ solutions sampled from the REINFORCE policy? Is this done with some stochastic exploration policy?

* **Advantage function:** 
    * In equation 5, is $R(\pi(P))$ the greatest rewards attained by policy $\pi$ for problem $P$ across all $K$ samples? I.e. is $R(\pi(P))$ a subset of R({\pi^{k}\}^{K}{k=1}? If not, what is the difference between how $R(\pi(P))$ and R(\{\pi^{k}\}^{K}{k=1} are generated?

    * Could the authors please explain how the proposed advantage function means the advantage will be negative if a proposed solution has a worse optimality than the K solutions sampled? Will it not only be negative if it is worse than the mean of the $K$ sampled solutions, since the baseline is just the mean return of $K$ sampled solutions? Same for $L$ in Equation 6.

* **Unclear REINFORCE methodology and integration:** Where is $L_{inv}$ (and by extension $L_{sym}$) actually incorporated into training with REINFORCE? The policy gradient theorem defined in Equations 5 and 6 only seems to include the $L_{ss}$ and $L_{ps}$ terms, so where is $L_{inv}$? Where are the three symmetric loss functions combined? Furthermore, are Equations 5 and 6 separate, or does Equation 6 contain Equation 5 with the $L$ and $K$ summations? I would like to see how all of this is tied together, since at the moment I do not think it is clear.


### Related Work

* **Missing related work and context:** This section is missing some important work and fails to introduce some of the baselines considered in the later Experiments section (e.g. S2V-DQN) and the context around them. I do not think it necessary to add all prior works to the set of baseline comparisons, since the authors are showing that the Sym-NCO method can improve a range of different architectures and methods, but I think a discussion in the related work of a few more pieces of literature should be included to put the Sym-NCO work in context. In particular, the related work is missing a discussion of where Sym-NCO fits in the context of some of the key state-of-the-art non-GNN, GNN, supervised learning, and reinforcement learning works (e.g. Bello et al. 2016, Gu and Yang 2020, Dai et al. 2017, Abe et al. 2019, Li et al. 2018, Barrett et al. 2020 and 2022, Drori et al. 2020, Hottung et al. 2022).



### Experiments

* **Small CO instances:** At $100$ nodes, the CO problems considered are very small compared to those considered by e.g. Gu and Yang 2020 ($300$ nodes), Drori et al. 2020 ($1,000$ nodes), and Barrett et al. 2022 ($10,000$ nodes). Does Sym-NCO scale? Does the requirement to sample $L \times K$ solutions for the advantage function and to gain enough data to learn the symmetricities hinder scalability? This would be interesting information to include in the paper’s experiments and discussion.

* **Statistical significance of solver performance differences:** On $O(100)$ node problems of the size considered, many of the ML-CO methods in Table 1 seem to obtain similar costs (e.g. AM gets $7.94$, POMO and MDAM get $7.80$, and Sym-NCO gets $7.79$). Is this a statistically significant difference in the optimality gap? It would seem that on such small CO problems there is not much room for differing costs, and that the results of Sym-NCO can be easily made to overfit until the reported result is achieved.

* **Optimality gap calculation:** How were the optimality gaps in Table 1 calculated? E.g. If the optimal solution of TSP is $7.76$ and Sym-NCO finds a solution of $7.84$, does this not mean that Sym-NCO’s solution cost is $1.03$% higher than the optimal solution (the authors have recorded a gap of $0.94$%)?

* **Unclear Sym-NCO integration with existing ML solvers:** Table 1 and Fig 4 do not indicate which ML method(s) Sym-NCO was applied to. They just state Sym-NCO as a standalone method, but is Sym-NCO not applied to at least one of the other baselines to get the results in the table? At the beginning of the Experiments section, the authors state that they apply Sym-NCO ‘on top of POMO, AM, and PointerNet’, but it is not clear from Table 1 and Fig 4 which underlying method was used for Sym-NCO.

* **Missing experimental data:** In Table 1, why are PointerNet and S2V-DQN missing solving time values?

* **Negative optimality gaps:** In Table 1, having a negative 'optimality gap' does not make sense - how can a solution be found which is more optimal than the optimal solution?

* **Unclear and inconsistent results:** Table 1 and Figs 3 and 4 are not consistent in multiple regards:
    * Fig 3 shows PointerNet getting a minimum validation cost of $\approx9.50$ for TSP, but Table 1 shows PointerNet to have a cost of $8.30$. Also, none of the Sym-NCO validation curves in Fig 3 reach the $7.84$/$7.79$ TSP costs claimed in Table 1. Why? 
    * Fig 4a: Sym-NCO and POMO get almost exactly the same $\approx0.79$ result, yet POMO is recorded as having achieved a cost of $0.80$ in Table 1 compared to Sym-NCO’s recorded $0.79$.
    * What are the stopping criteria to stop running each solver? In Fig 4, it seems that the algorithms were still improving their solutions when they were stopped, and it also seems as though some of the other ML baselines were on track to surpass the optimality of Sym-NCO; it is important to report if Sym-NCO converges faster but to less optimal solutions.

* **Missing sensitivity analysis to the introduced hyperparameters:** What is the sensitivity of Sym-NCO to $\alpha$, $\beta$, $L$, and $K$? In the Appendix, the authors only show results for $\alpha = \{0.1, 0.2\}$, but $\alpha, \beta \in [0, 1]$. In proposing a new training scheme which introduces additional hyperparameters, the authors should have a comprehensive study of the influence of these hyperparameters on training and validation performance across different problems, since this is relevant information for practitioners who may wish to use the work.

* **Missing analysis and discussion of Sym-NCO design choices:** Which factors determine the values of $K$ and $L$ in Sym-NCO? Presumably they change as the size and nature of the CO problem changes, since some CO problems will be difficult to sample trajectories for which sufficiently encapsulate the symmetricities (e.g. some CO problems will have a vast number of possible solutions, and only a few of these might have the same objective function value; will this influence the ability with which Sym-NCO can learn the underlying solution symmetry of the problem? Is there a requirement on how many solutions with the same/similar objective value are needed to make learning solution symmetry tractable? Can solution symmetry still be imposed if no solutions with the same objective are found?)

* **Missing analysis of Sym-NCO incurred overhead:** What is the incurred training overhead of sampling the $K \times L$ solutions needed for the Sym-NCO advantage function baseline?


### Other

* **Generality claims:** The paper makes claims (in the title, abstract, and throughout the paper) to be a general neural CO solver training scheme. However, Sym-NCO has been specifically designed for policy-gradient RL and was only applied to REINFORCE. Moreover, it only considers graph-based CO problems which are variants of TSP and, for that matter, only looks at instances which can be projected onto Euclidean space. Do other ML-CO methods consider non-Euclidean problems (e.g. Dai et al. 2017, Barrett et al. 2020 & 2022, Drori et al. 2020) where graphs trained and inferred on can have differing structures? Are the authors claiming that Sym-NCO can be generalised to ML paradigms (supervised and unsupervised learning) and CO problems (non-graph-based and/or non-Euclidean graph-based) other than those considered in the paper? Can the existence of the same symmetries considered in this paper be universally assumed to exist for all CO problems? 

* **Euclidean vs. non-Euclidean problem clarification:** Was there a particular reason for only considering Euclidean problems rather than utilising the now commonplace graph neural network architectures such as those used in prior works (mentioned above) which can handle non-Euclidean inputs with varying structures? What are the limitations of only handling Euclidean CO problems in terms of applications and the state-of-the-art literature? Do the authors have to hand-pick problems to meet this Euclidean constraint?


### Miscellaneous minor issues
* Pg. 1 line 2: Introduce DRL-NCO acronym but unclear what the ‘N’ stands for (presumably ‘neural’, but should specify)

* Pg. 4 line 114: Should it not be ‘as the hidden representations of $x$ and $Q(x)$’ rather than ‘$x$ and $P(x)$’?

* Pg. 4 line 119: There seems to be unnecessary extra brackets in the $g(\cdot)$ term

* Pg. 6 line 197: You list PointerNet without saying which CO problem(s) you applied it to as you did for the other methods.

* Throughout the paper, you introduce many acronyms (e.g. S2V-DQN, AM, POMO, MDAM, etc.) without first stating what the full name of the acronyms are, which you should always give when first introducing a new acronym.

* It seems confusing to refer to the method of Nazari et al. 2018 as ‘RL’ since there are multiple other RL methods such as S2V-DQN.

* Citation [20] seems to be miss-formatted?

### References

1. Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, 2017
2. Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020
3. Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on real-world graphs in linear time. arXiv:2006.03750, 2020
4. Andre Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. International Conference on Learning Representations, 2022.
5. Thomas D. Barrett, Christopher W. F. Parsonson, and Alexandre Laterre. Learning to solve combinatorial graph partitioning problems via efficient exploration. arXiv:2205.14105, 2022
6. Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural Combinatorial Optimization with Reinforcement Learning. arXiv:1611.09940, 2016
7. Shenshen Gu and Yue Yang. A Deep Learning Algorithm for the Max-Cut Problem Based on Pointer Network Structure with Supervised Learning and Reinforcement Learning Strategies. Mathematics, 2020
8. Kenshin Abe, Zijian Xu, Issei Sato, and Masashi Sugiyama. Solving NP-Hard Problems on Graphs by Reinforcement Learning without Domain Knowledge. arXiv:1905.11623, 2019
9. Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search. In Advances in Neural Information Processing Systems, 2018
10. MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, 2018
limitations: N/A
review_title: null

Meta-review: metareview: All reviewers agree that the paper presents interesting results, hence I recommend acceptance. On the other hand there are several issues which need to be addressed in the final version of the paper:
1. The authors should add the experimental results listed in the responses, as these demonstrate more convincingly the significance of the results.
2. The mathematical formulation of the problem and the description of the solution is of extremely low quality (almost made me reject the paper). For example, nothing is defined in equation 1, neither the meaning nor the possible values of the different variables: What are the nodes? What values can features take? What is a solution? Going on to Section 2.1 and 2.2, it is again unclear what a solution is (not to mention a solution sequence), hence why we care about the corresponding MDP, what are the motivations in the definition of the MDP. What is a policy? What is a solution set? And so on. These must be written in a way which is understandable to a reader who is not already very familiar with the topic.
confidence: Less certain
Decision: Accept