Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper improves existing DRL-based CO methods in two terms. Firstly, the authors leverage a continuous probabilistic space for the solutions, leading to a REINFORCEMENT-based training method which is more efficient than previous Q-learning or Actor-Critic methods. Besides, a MAML-based meta-learning framework is proposed.
strengths_and_weaknesses: **Strengths**
1. This paper is well-motivated by several important issues in existing DRL-based CO methods.
2. The proposed REINFORCEMENT-based method and the MAML-based meta-learning method seem sound.
3. The proposed method can handle larger-sized problems than existing DRL-based CO methods.

**Weaknesses**
1. This paper aims for developing a new general framework, but the current evaluation is only for two problems. Evaluating more problems of different natures (such as covering/matching problems) will make this paper more concrete and convincing.
2. There are certain implementation details that seem unclear to me and I am expecting the authors to answer (see "Questions").

**Typos**
1. Line 45: What is "DIR"-based CO solver?
2. Repeated citations: 29/30, 34/35
questions: 1.  How many trials are configured for LKH-3? Can you decrease the number of trials so that LKH-3 can be comparatively faster than DIMES, and report the time and tour lengths?
2. In L149 the authors write: "we also no longer need costly MCMC-based sampling for optimizing our model". If sampling is not needed, how do you estimate the expected cost value after the neural network predicts q?
3. What is the application scope of the proposed method? Beyond routing and independent set, can you list some other types of problems that the proposed method can tackle and some that may be hard to handle?
4. Is there an ablation study for with/without meta-learning? 
limitations: The limitations are addressed.
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 studies a differential meta solver for CO problems and its performance is demonstrated by using TSP instances (size 500, 1000, and 10000). The difference between the proposed method in this paper and existing DRL-based methods is from the fact that DIMES focuses on a parameterized continuous space to represent solutions of CO problems. Experimental results indicate that DIMES show better performance than DRL-based solvers. Ablation studies on DIMES show that the proposed components work effectively.
strengths_and_weaknesses: [Strength]
- Focusing on the continuous space (Eq.2) could widen this research field (rather than the encoding-decoding scheme in DRL-based methods).
- Large instances (e.g., TSP-10000) are tackled by DIMES (Note that such scalability could be hard for DRL-based methods in the current status).

[Weakness]
- The generalization ability when designing auxiliary distributions is unclear.
- The discussion and background of MAML (e.g., the idea of T gradient updates) are a bit hard to follow.

questions: - I feel that the proposed concept is interesting to investigate, and I'm interested in how to design auxiliary functions (this is also noted in sec.5 by the authors). I also read proofs in the supplemental material. I wonder if we can design such functions for various CO problems. The paper proposed the answer for TSP and MIS, but defining such functions (with proofs) seems to be challenging (as many variations on objective functions and constraints). If this is not straightforward (or this requires some hand-crafted works like parameter tuning), I feel that DIMES requires us to design such functions (this is similar to us designing good encoding-decoding scheme for DRL-based methods, good heuristics in OR, better algorithms, etc.).

- In Table 1, LKH-3 with TSP-1000 requires 38.09[m] (this may be from Fu et al. [16] https://arxiv.org/pdf/2012.10658.pdf). Thus, it seems that the DIMES outperforms the famous heuristic solver. However, for example in Table 1 [https://arxiv.org/pdf/1402.4699.pdf] (Note that I do not want to say like `this paper is good/bad`, I just cite experimental results from this.), LKH-3 seems to solve TSP instances (size from 9847 to 16862) efficiently (from 381[s] to 976[s]). I wonder what is the differences between such traditional benchmark TSP instances (like ja9847) and those generated by Fu et al. [16] (TSP-1000/TSP-10000). This behavior is also seen in existing papers like AM's paper (LKH3 requires 21[m] to solve TSP-100). Such results (often reported in papers proposing learning-based solvers) seem to be strange to me. Could you please explain them?

- For datasets, the authors mentioned two sources from [35] (train) and [16] (test). The difference and similarities of datasets among them should be explained.

- Related to the previous question, I'm interested in the learned results that can be generalized to other instances. For example, TSP-1000 with MAML requires 1.7[h] learning times + 4.47[m] to generate solution (1.7[h] from supp mat and 4.47[m] from Table 1.), but LKH-3 requires 38.09[m]. So, if the learning results are not shareable with other kinds of datasets, the learning process is a bit resource-consuming trial. Do you have any ideas or findings?

- The dimension T (of MAML) is fixed. Is this tunable? (or need to be tuned to get better solutions?). In the ablation study (c), it seems that learning more by MAML produces better solutions. Is this interpretation true?

- (L.45) Instead of previous DIR-based CO sovles; what is DIR-based? sovles => solves. Some other english errors should be updated for readability.

limitations: After reading the main paper and appendix, I feel that the authors carefully discuss the negative impacts.
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 proposes a novel DIMES framework (stands for differentiable meta solver) to tackle large-scale learning-based combinatorial optimization problems. The key novelties and contributions are 1) an RL-based approach to train the widely-used GCN model to generate probability heatmap, and 2) a meta-learning approach to further finetune the solutions at inference. Experimental results show that the proposed DIMES can achieve promising performance for large-scale TSP and MIS problems with up to 10,000 nodes.

strengths_and_weaknesses: **Strengths:**

+ Learning to solve large-scale combinatorial optimization problems is crucial for many real-world applications. This work is a timely contribution to an important research topic.

+ To my understanding, the proposed RL-based approach for training GCN to obtain the probability heatmap is novel. It is quite promising to see a pure end-to-end RL-based approach can tackle TSP with up to 10,000 nodes.

+ The meta-learning based fine-tuning strategy is also new for neural combinatorial optimization.

+ The experimental results on large-scale TSP are good.

**Weaknesses:**

I cannot give a clear acceptance to the current manuscript due to the following concerns:

**1. Inaccurate Contribution:** One claimed contribution of this work is the compact continuous parameterization of the solution space. However, as discussed in the paper, DIMES directly uses the widely-used GNN models to generate the solution heatmap for TSP[1,2] and MIS[3] problems, respectively. The credit for compact continuous parameterization should be given to the previous work [1,2,3] but not this work.

For TSP, Joshi et al.[1] have systemactilly studied the effect of different solution decoding (e.g., Autoregressive Decoding (AR) v.s. Non-autoregressive decoding (NAR, the heatmap approach) and learning methods ( supversied learning (SL) v.s. reinforcement learning (RL)). To my understanding, the combination of AR + SL, AR + RL and NAR(heatmap) + SL have been investigated in Joshi et.al. and other work (e.g., PtrNet-SL, PtrNet-RL/AM, GCN), but I am not aware of othe work on NAR(heatmap) + RL. The NAR + RL combination could be the novel contribution of this work.

**2. Actual Cost of Meta-Learning:** The meta-learning (meta-update/fine-tuning) approach is crucial for the proposed method's promising performance. However, its actual cost has not been clearly discussed in the main paper. For example, Table 1 reports that DIMES only needs a few minutes to solve 128 TSP500/TSP1000 and 16 TSP10000 instances. However, at inference, DIMES actually needs extra meta-gradient update steps to adapt its model parameters to each problem instance. The costs of the meta-gradient steps are 1.5h - 10h for TSP500 to TSP10000 as reported in Appendix C.1. Since all the other heuristic/learning methods do not require such meta update step, it is unfair to report that the runtime of DIMES is only a few minutes (which should be a few hours) in Table 1.

**3. Generalization v.s. Testing Performance:** To my understanding, all the other learning-based methods in Table 1 are trained on TSP100 instances but not TSP500-TSP10000 as for DIMES. Therefore, the results reported in Table 1 are actually their out-of-distribution generalization performance. There are two important generalization gaps compared with DIMES: 1) generalization from TSP100 to TSP10000, 2) generalization to the specific TSP instances (the fine-tuning step in DIMES). I do see it is DIMES's own advantages (direct RL training for large-scale problems + meta fine-tuning) to overcome these two generalization gaps, but the difference should be clearly clarified in the paper. 

In addition, it is also interesting to see a comparison of DIMES with other methods on TSP100 (in-distribution testing performance) with/without meta-learning.

**4. Advantage of NAR(heatmap) + RL + Meta-Learning:** From Table 1&2, for TSP1000, the generalization performance of AM (G: 31.15, BS: 29.90) trained on TSP100 is not very far from the testing performance of DIMES without meta-learning (27.11) directly trained on TSP1000. It could be helpful to check whether the more powerful POMO approach[4] can have a smaller performance gap. Reporting the results for POMO and DIMES without meta-learning for all instances in Table 1 could make the advantage of the NAR(heatmap) + RL approach in DIMES much clearer.

Hottung et al.[5] shows that POMO + Efficient Active Search (EAS) can achieve promising generalization performance for larger TSP instances on TSP and CVRP. The comparison with POMO + EAS could be important to better evaluate the advantage of meta-learning in DIMES.

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

[2] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.

[3] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. NeurIPS 2018.

[4] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. NeurIPS 2020.

[5] André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. ICLR 2022.

questions: - DIMES needs to use RL to directly train deep GNN for large-scale problem instances with up to 100,000 nodes. Is there any challenge for such training? How long will DIMES take to converge for TSP500/1000/10000 (#training instances and wall-clock time)? 

- TSP/MIS is a good testbed for neural combinatorial optimization. But the real-world applications will typically have problems with various structures that can not be solved by classical solvers. This is an important motivation for learning-based solvers without domain knowledge. Can DIMES generalize to other routing problems such as those in the AM paper?

- Citation [42] and [43] in the paper are for the same AM paper but with two different years (the 2019 one is correct). 

limitations: Yes, the limitations have been adequately addressed in Section 5 Concluding Remarks. I do not see any potential negative societal impact of this work.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposed DIMES, a framework for tackling graph-based combinatorial optimisation problems with reinforcement learning.  DIMES runs a graph neural network to produce a heatmap over the candidate variables (edges for TSP, nodes for MIS) which corresponds to a policy for which variable to select next from any given position.  This approach seeks to provide more scalable CO solvers as solutions can be efficiently sampled from a generated heatmap with minimal additional overhead.  Compared to prior works, DIMES primary claims of novelty are (i) the process does not require supervised data to generate the heatmaps and (ii) that DIMES can be trained, using meta-learning, on a distribution of instances such that it can quickly and efficiently specialise during active search on a singe instance.  In experiments on TSP and MIS, DIMES is shown to perform competitively or better than the considered RL/SL baselines and remain efficient even on large problem sizes.

strengths_and_weaknesses: *Strengths*

The problem tacked — scalable RL approaches for CO — is significant and well motivated.  Improvements in performance and scalability of are of interest to the community.

As it is typically intractable to produce optimal solutions to NP-hard CO problems, the efficient sampling of candidate solutions and active search on a target instance at test time important components of many approaches.  In this context, the demonstrated efficacy meta-learning good starting points for the agent from which to fine-tune is interesting.  Whilst it was also novel to my knowledge, a quick search did show that the authors might want to consider softening their claim (line 51) that "we are the first to apply meta-learning over a collection of CO problem instances” (e.g. https://arxiv.org/abs/2105.02741).

The experimental results appear impressive, though I have some points of concern or that require clarification (see below) before I can fairly judge these.

*Weaknesses*

I am not convinced by the authors claim that DIMES “introduces a compact continuous space for parameterizing the underlying distribution of candidate solutions” is novel or significant, nor that this new approach “addresses the scalability challenge in large-scale combinatorial optimization” more so than previous works.  Ultimately, DIMES is predicting a heatmap with a single pre-processing step of the entire problem instance (graph), which then guides some search process (greedy, sampling, MCTS etc).  Whilst the paper contrasts DIMES to previous works with “we introduce a compact continuous space for parameterizing the underlying distribution of candidate solutions” — it seems to me that this is just different language for talking about a heatmap which, by the authors admission, many previous works have already used.  The authors note that previous heatmap approaches were not pure RL (relying on some labelled data), however applying RL for TSP well established and having that agent output a heatmap instead of, say, embeddings that implicitly define a heatmap via attention, or running a full inference at each step is a straightforward modification that doesn’t appear to rely on any architectural or theoretical insights.

Whilst the paper is well written from a linguistic perspective, I do feel it loses clarity in the way it presents DIMES and draws contrasts with prior work where they may not be justified.  For example, “Instead of previous DIR-based CO sovles which rely on construction or improvement heuristics, we introduce a compact continuous space for parameterizing the underlying distribution of candidate solutions which allows massively parallel on-policy sampling”.  To me, DIMES is a construction heuristic (it starts at a node/edge, and then iteratively picks the next until a solution is found).  Moreover, the scalability does not come from any breakthrough regarding the compact continuous parameterisation space, but in essence because as much processing as possible (e.g. the expensive GNN) is restricted to single preprocessing step.  However, this is not a novel idea - even the authors own RL baselines for TSP - Joshi et al [24] and Kool et al [34] - use an expensive preprocessing step followed by fast action decoding.  In this vein, another work the authors may consider relevant is that of Driori et al (https://arxiv.org/pdf/2006.03750) who use dot-product attention between graph embeddings as an alternative parameterisation of a heatmap and demonstrate impressive performance on TSP (outperforming Farthest/2-opt heuristics on most “real world” graphs of up to ~125k nodes).

I am concerned that certain more recent baselines may be missing, and that certain results may be missing from the experimental section.  Some points are listed here, but others are left as questions below where I feel I need more clarity.

- The attention model of Kool et al [34] is used as an RL baseline.  However, this approach has been significantly improved in POMO (https://arxiv.org/abs/2010.16011) and then subsequently adapted for active search at test time (https://arxiv.org/abs/2106.05126).  Driori et al (above) is also a significantly scalable RL TSP solver that would seem to be an important baseline if DIMES is justify claims that they are contributing with regards to scalability.

- The authors only rerun one of the presented baselines (Att-GCN) on their hardware, so timing results for other baselines taken from Fu et al are potentially misleading.

- In Table 3, why is LwD with sampling (RL+S) not included?  As LwD is better than DIMES in greedy mode, but DIMES is better with sampling, would LwD with sampling not be expected to be best of all?
questions: - Regarding the fine-tuning of DIMES in table 1: (i) Is the fine-tuning time included in the run time (I would have expected so, but then I am surprised how, for example, DIMES is faster the AM with equivalent settings if it has to be fine-tuned first)? (ii) Which elements of the model are fine-tuned (as four variants are show in Table 2(b) it is clear there is some choice to be made)?
- If all baselines were taken from Fu et al, can you comment on whether the training of these was a fair comparison to DIMES?  For example, DIMES is trained on the target problem sizes but it is common to present results on larger TSP instances of models trained on smaller problems.
- In the meta-learning ablations, why would training the network using meta-learning (targeted to give good performance after T steps of fine-tuning on a specific instance), give better performance when T=10 during training and T=0 at inference (i.e why is row 2 of Table 2a better than row 1?)
- Why is S2V-DQN not used as a baseline in Table 3, when it is stated to be a baseline on line 297?
limitations: Yes.
review_title: null

Meta-review: metareview: This paper proposes a differentiable meta-solver applicable to large-scale combinatorial optimization. After a thorough discussion phase, all the reviewers are on the positive side of this paper. The reviewers appreciated the novelty of this paper and the importance of scaling neural combinatorial optimization for large-scale instances. Overall, I recommend acceptance for this paper.

However, the reviewers also showed concerns about the presentation of this paper. The gap between generalization and testing performance is not clearly discussed and the connection to prior works using continuous latent space should be clearly stated. Since scalability is an important issue, it would be useful to clear up time/objective comparison and unify experimental settings as suggested by Reviewer fQdp and fe3B.



confidence: Certain
Decision: Accept