Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims to automatically solve combinatorial optimization by leveraging unsupervised learning, learning from historical data and 
achieving an instance-wise good solution simultaneously. In order to do so, the authors propose a methodology for warm-starting future combinatorial optimization problem instances. The methodology is based on meta-learning. The authors show that warm-staring is beneficial indeed across multiple datasets and shifts. 

strength_and_weaknesses: This is an interesting work with promising results. Would the author please comment on whether the methodology can also be casted as a multi-task learning? Moreover, what are other applications/extensions of the proposed framework? There several discrete black-box expensive potentially noise-corrupted discrete optimization applications which can benefit from this methodology. One such example is chip design and the other is NAS (amongst many other). 
clarity,_quality,_novelty_and_reproducibility: The authors have provided the code to replicate the results. Although the reviewer has not run the code, the implementation looks reasonable at a high level.

summary_of_the_review: The reviewer finds this work interesting and promising with sufficient empirical validation.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work suggests a framework of unsupervised learning for combinatorial optimization, which uses generally good initializations that determine via a meta-learning scheme. In particular, the authors propose a new objective of unsupervised learning that is capable of providing good initializations rather than direct solutions. Finally, the authors demonstrate the empirical results that show the effectiveness of the proposed method.
strength_and_weaknesses: ## Strengths

This paper is generally well-written, and the main message of this work is clear. Moreover, the proposed algorithm shows good performance in many benchmarks.

## Weaknesses

The novelty of this work is somewhat limited. However, I think that this does not degrade the quality of the paper much.

Moreover, I think the sentence

> our learning objective of a model is to make further optimization of the initialization given by this model over each of these pseudo-new instances yield good solutions

should be proved. I think that the reasoning for this statement is not provided appropriately.

Also, this work heavily relies on the recent work (Wang et al., 2022). Some parts of this work are very similar with the work (Wang et al., 2022).
clarity,_quality,_novelty_and_reproducibility: ## Questions

According to the proof of Theorem 1, $\alpha$ is assumed as $1/L$. I think that it should be stated more clearly. Also, a learning rate should be determined as $1/L$. Did you consider this value when you choose a learning rate?

Following the above question, Theorem 1 can be proved where a stochastic gradient descent is used. Could I ask which optimizer is used?

I want to ask about bold texts in the tables in this work. I think bold texts are somewhat randomly determined. Does a bold text represent the best result?

In Table 1, what is the meaning of fine-tuning timing for classical solver? Sine it does not have a training procedure, fine-tuning does not also exist, right?

## Minor issues

In Page 3, "a algorithm" should be "an algorithm" and "a NN" should be "an NN".

I think that Algorithm 1 should be separated to "train" and "test". "return" in Line 6, which is in the middle of the algorithm is very strange to me.
summary_of_the_review: Please see the above text boxes.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a meta learning framework Meta-EGN that produces a good initialization for a neural CO solver. The authors build upon the work of Karalias & Loukas, (2020) and extend it to provide a performance guarantee for Meta-EGN as well.
strength_and_weaknesses: As demonstrated in the experiments section, Meta-EGN works well compared to all relevant baselines, except for Gurobi of course, which is known to be in a league of its own compared to any neural CO solver. It is fascinating that such a general parameter $\theta$ can even exist for these problems.

The ability to extend the performance guarantees of EGN toMeta-EGN is also a good win.

One drawback is missing ablation studies about the technique - some questions that I would be interested in are

- How does Meta-EGN perform as a function of %of the training data used? i.e., if we initialize algorithm 1 with random subsets of the full training dataset of size N/2 instead N and training Meta-EGN to convergence, how does the algorithm perform?
- How does Meta-EGN generalize if it is trained on graphs with certain statistics i.e. average node degree < 3 and then evaluated on graphs with avg node degree > 3? Or similar studies.

Ablation studies like these would help answer how sensitive Meta-EGN is to the quality of the training data set, my hypothesis is that if the training data set is not diverse enough, Meta-EGN wont work as well.

>  the current framework optimizes an averaged performance over the distribution of historical problem instances, which misaligns with the actual goal of CO that looks for a good solution to every future encountered instance'

A note on this comment - in practice - we don't wont want to solve the general case problem cause often CO problems can be intractable (eg NP Hard). Instead, practitioners would develop a heuristic to try to exploit a property that is only true in the distribution of instances that they are interested. eg. TSP is hard in general but approx algos exist in a metric space -- It is unclear from the paper what a practitioner should do in this case - should they use a training dataset that matches the distribution of instances that they are interested in OR should they use a more general distribution of instances since it will allow Meta-EGN to learn general case properties about the problem which wont be visible in the specific distribution.

An excellent version of the paper would offer more direction to practitioners on how to use the framework, however this could be tackled in future work.

clarity,_quality,_novelty_and_reproducibility: There are a few typos but the paper is clear to follow and adequate information is available for reproducibility.
summary_of_the_review: Overall I found the paper interesting and it poses some fun questions for future work. The novelty is a little incremental since it builds on top of recent work but the results are interesting.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an application of Model-agnostic meta learning (MAML) (Finn et al., 2017) for the Erdos-Goes-Neural (EGN) framework (Karalias and Loukas, 2020). This will allow faster learning of novel combinatorial optimization tasks through learning better model initialization. The method is applied to several classical problems such as Max clique (MC), Minimum vertex covering (MVC) and Max independent set (MIS). The empirical result is promising.
strength_and_weaknesses: Strengths: Interesting application with a straight-forward solution. The authors provide a theoretical guarantee and obtain significant result on several classical problems.

Weaknesses: 

-- Some missing important details, please check the questions below.

-- Running time, including the pretraining time, should be thoroughly reported for fair comparison.

-- It is unclear what should be the take away insight of this paper. EGN has been shown to be a robust CO solver that can generalize. Meta learning has been shown to improve generalization in many applications. While the results in this paper are mostly positive, I feel that they only serve to confirm previous insights. 
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is generally straight forward and clearly written. I have several questions below: 

-- How does one obtain the functions $f_r$ and $g_r$ given any arbitrary $f$? 

-- Are the relaxations in Table 2 well-known? If this has been discussed in previous work, the authors should cite give a brief summary. Otherwise, please provide some intuitions regarding their constructions.

-- How is pareto-optimality defined in this paper?

-- Were EGN and Meta-EGN pretrained for the same amount of time? This is an important detail that should be in the description, but I can't seem to find any mention. One update iteration of meta learning is a generally more costly and samples a lot more data than one standard update iteration. The only way to fairly compare a model and a meta-model is to make sure that they were trained for the same amount of time and have seen roughly the same amount of samples.

-- The section title "META-EGN BOOSTS THE PERFORMANCE WITHOUT DISTRIBUTION SHIFTS" seems a bit misleading since Gurobi actually performs optimally on more than half the benchmarks. I guess the point is that Gurobi takes 4s per task, whereas it only takes <1s  for the pretrained models to do inference. This difference will eventually accumulate in repeated inference scenarios. If this is the case, the author should also discuss the break-even point where the pretrained models are per-task cheaper than Gurobi (which also means reporting the pretraining time).

Novelty: This is a direct application of MAML on EGN. While the exact problem has not been solved before, the idea is not surprising since it is subsumed by the model agnostic design of MAML.

Quality: The result for smaller graphs seems marginal. The result for generalization on larger graph is good. For the MIS case I think building on top of the DGA result is a valid strategy. However, to be fair, the DGA algorithm should be allowed to continue running from that point for the same amount of time allocated to Meta-EGN (I'm under the impression that the DGA algorithm will continue to run until the exact solution is found -- please correct me if i am wrong). This has not been discussed in the description.

Reproducibility: I'm convinced that this paper can be reproduced. The result seems to align with general trend in meta learning and previous result of EGN. 
summary_of_the_review: This paper presents an interesting application of meta-learning on the EGN framework. There are some positive results, although they are not quite surprising. I have no major concerns about the quality of the paper. Overall, I would recommend a marginal acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents an interesting application of meta-learning to combinatorial optimization problems. The work is clear and the claims are supported. The conducted benchmarks are convincing. Authors addressed the concerns raised by the reviewers in a satisfactory manner.

justification_for_why_not_higher_score: The work has some incremental aspects. Some reviewers found the results not particularly surprising (but encouraging).
justification_for_why_not_lower_score: Authors addressed the concerns raised by reviewers in a convincing manner.
Decision: Accept: poster