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: The paper proposes an unsupervised machine learning method for combinatorial optimization (CO) problems. The focus is in particular on CO problems that have an expensive cost function, necessitating a learned surrogate model. The authors extend the work by Karalias & Loukas [1] to this so called Proxy-based CO setting, while still retaining theoretical guarantees that a feasible solution with low cost can be attained. This guarantee comes with certain assumptions about the ground-truth cost function (not too high order) and limitations on the neural network for the proxy. The method outperforms learning based baselines on three different non-standard benchmarks and appears to require less resources to train.
strengths_and_weaknesses: Strength:
- Unsupervised machine learning for CO (especially PCO) is an interesting and important research area. In particular, this work is a significant extension of [1].
- The paper is well written, and the main ideas are clearly presented
- The proposed method appears sound: it is accompanied by theoretical guarantees on achieving feasible solutions with costs upper bounded by the training loss (theorem 1) and there exist relaxations fulfilling the required constraint for the proxy cost function (theorem 2)

Weaknesses:
- The experiments are extensive (multiple different baseline models and different experiments), but do not compare directly against prior work on any established benchmarks. This makes it difficult to place the work in the current literature and gauge how well it does in comparison.
- The non-learned baselines (simulated annealing and genetic algorithm) were only applied to the 2nd experiment "Resource Allocation in Circuit Design", but in light of recently pointed out shortcomings of ML based approaches compared to non-learned methods, it would be interesting to see a more extensive comparison against these non-learned baselines. This also includes applying SA/GA for more iterations, to get better results and a better sense of the complexity of the investigated problems.

questions: It would be helpful to explicitly spell out the limitations of the current method. For example: What are the computation costs associated with n-th order proxy costs? Will it fail when the ground truth cost requires higher order moments? How well does this scale to larger problem instances (>1k nodes)?

For suggestions about the experiments, see above.
limitations: Potential societal impact is addressed in the appendix. Limitations should be expanded on, as for example suggested above.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors propose an unsupervised learning framework for combinatorial optimization problems. They evaluate this framework by solving a synthetic graph optimization problem.
strengths_and_weaknesses: Overall, I found the paper quite confusing to follow .

The authors claim that they have an unsupervised learning framework, yet they seem to be using supervised and labelled data to learn proxy objectives for both cost and constraints.

> This work provides the first unsupervised framework for PCO problems

The motivation behind unsupervised algorithms for PCO is unclear since you already need supervised data to train the proxy functions.

Keeping the supervised vs unsupervised nitpicking aside, I don't follow how either AFF or CON are actually solving the problem or how the guarantees about rounding provided by the authors are valid - if the function being optimized is a proxy of the true loss function - how can rounding this solution have any guarantee on feasibility - since the learned loss function has no bound on its error?

Taking a step back, I don't fully grasp how the authors go from an instance of an edge covering problem G = (V, E) to a valid solution X \in {0, 1}^|E| that solves the edge covering - my best guess is that the authors try to train two GNNs - the first GNN is trained in a supervised fashion to predict the cost function f (and perhaps the constraint function g), and the second GNN is used to learn a Bernoulli distribution from which the authors will sample lots of X, and the X that minimizes the learned/proxy cost function will be rounded out using the procedure they described into the final solution.

Section 4.1 - Each observed configuration is paired with a solution X  - what is the methodology for picking this X for the supervised training? Did you'll sample a solution at random and evaluate its cost and constrain function for the training data?

The notation was a bit confusing at times - 
- line 216 the data configuration is denoted by C but the GNN encoding is also denoted by C in line 224.
- line 225 - 2nd order moments -  I am not familiar with this notation in this context of GNNs - did you mean the number of successive applications of the message passing layers. 

I tried going through the supplementary material but it seems that some of the READMEs are incomplete.

What problem is being solved in section 4.3? Minimize the weighted edge covering? Why do you even have to use LCO for this problem? Don't you just have to solve MNIST on the nodes' images and then solve edge covering? Why do the edge weights have to be learned? I don't understand the motivation for picking this problem to evaluate the framework proposed in the paper.

Further, 4x4 graphs are extremely tiny. While the total search space of these graphs can be huge, it doesn't necessary imply that the family of instances in the data set has a very complex combinatorial structure or that learning this problem is hard.

If this synthetic example is just for the sake of demonstration, it would have been much easier to follow were it solving just the vanilla edge covering problem.

-----

My current recommendation is a borderline reject but I remain hopeful that I fundamentally don't understand something in the paper and that the authors will clarify it.
questions: It would be really helpful if the authors can clarify my questions above.

Further, I believe it would be productive for the rebuttal, if the authors can clarify the the following question first -

Given an instance of a minimum edge covering problem [1] G = (V,E) - how would you propose to solve this with your framework?

[1] https://en.wikipedia.org/wiki/Edge_cover
limitations: I find the setup of finding solutions in binary encoding space to be quite restrictive and don't immediately see how this would generalize to any combinatorial optimization problem in a feasible way - for eg. network flow algorithms in which one has to assign a fractional amount of flow to a network arc.
review_title: null

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: The paper proposes an extension and variant to a previous paper by Karalias& Loukas, replacing the expectation based decoding strategy and probabilistic guarantee with another construction which relies on elementwise concavity+rounding of the function used to minimised the selfsupervised objective. The paper compares agains naive rounding, RL and Gumble softmax + sampling/rounding baselines on edge covering, node matching and 2 additional tasks (resource allocation and approximate programming) and finds their methods to be dominant across all considered methods.
strengths_and_weaknesses: The paper is well written and provides good experimental evidence of the improvement possible with their method, evaluated on real world problems. Originality, quality/clarity and significance are all at acceptance threshold for me.
The only nit picks I could find are in Questions and limitations.
questions: 1. Most importantly: Is your method applicable to the problems studied in Karalias&Loukas? If so, can you add those experiments as well to directly compare the most relevant Literature method?
2. I saw you ran 3 seeds, can you add std to the table (and ideally, run additional seeds and perform a statistical significance test between methods?)
limitations: Authors discuss binary embeddings of the optimization variables as an avenue for future work. I would like to have seen a discussion of which functions might lie outside the entry-wise convex framework, and about the computational complexity and scaling of their proxies when moving to large scale problems
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper extends the relax-optimize-discretize pipeline in Erdos Goes Neural. The authors believe that the sequential decoding scheme in EGN suffers from two issues, and resolve these issues by sequentially rounding over a so-called entry-wise concave principle. The proposed scheme is claimed to require fewer samples and thus faster than EGN, while still preserving the theoretical performance guarantee in EGN. The authors mainly investigate the application of the proposed approach in proxy combinatorial optimization (PCO), where the objective function is unknown or too expansive to know.
strengths_and_weaknesses: Here is my overall judgment of this paper: the ideas/insights/experiments are novel and interesting. However, this paper reads somewhat confusing, especially since the experiments seem not to match the other parts of this paper.

**Strengths**
1. (Unsupervised) learning for combinatorial optimization is an important topic worth studying. The considered PCO problem is also practical and important.
1. I enjoy the narrative of theoretical analysis and insights about learning CO. 


**Weakness**
1. Experiment for learning on pure (non-proxy) CO problems is missing, and the important baseline Erdos Goes Neural is missing. In the experiment, the authors study 3 PCO problems, which I agree to be very important and novel. However, in Section 1&2&3, this paper reads to be an improved version of Erdos Goes Neural. Since Erdos Goes Neural is focused on pure CO problems, there is no reason not to evaluate such problems and compare to EGN to support the theoretical results. Besides, the authors also discussed on how to tackle the pure CO problem in detail in Section 3. It seems confused for proposing a new method for pure CO but evaluating it.
2. This paper is titled "unsupervised" learning. However, it seems that the evaluated PCO problems are not "unsupervised", but "supervised" because the proxy should be learned from labels. For example, in application II, the authors write "the actual LUT and DSP usages of each training instance has been collected by running HLS in prior".
3. Adding a flow chart or an algorithm block for the proposed framework will make this paper clearer and easier to reimplement.
4. The implementation details on the application of PCO problems seem not clear. For example: In application II, what is the proxy model for RL/SA/GA? Do they use the same entry-wise concave GNN? It seems that we can build a conventional GNN for them and I am curious whether a conventional GNN will be more accurate?


**Other Remarks**
1. L19: Most CO problems are NP-complete -> Most CO problems are NP-complete or NP-hard.
2. Is Erdos Goes Neural missing in the discussion in Table 1? How is EGN considering these aspects?
3. I feel confused about L188: "Optimizing $\theta$ in Eq.(2) is generally hard as the gradient $dX/d\theta$ does not generally exist so the chain rule cannot be used." However, $X$ should be continuous in EGN, therefore the gradient should always exist.
4. In L128: "The two special cases in [1] on the max-clique and graph-partition problems seem to have special structures." Do you have any support for this claim?
questions: 1. Is there any reason why pure CO problems are not evaluated?
2. Are the proxy-GNNs learned by supervised learning?
3. In application II, what is the proxy model for RL/SA/GA? Do they use the same entry-wise concave GNN? It seems that we can build a conventional GNN for them and I am curious whether a conventional GNN will be more accurate?
limitations: The authors write in the checklist that the limitations are addressed in Section 5, but it is missing.
review_title: null

Meta-review: metareview: This paper proposes a new framework to train machine learning models to solve combinatorial optimization problems. Its key idea is to develop a relax-and-round solution-generating approach that allows backpropagation and enjoys theoretical guarantees for the rounding procedure. This approach generalizes the previous work (Karalia et al. 2020) to proxy CO settings where the objective function is expensive (and replaced by a proxy function). 

The reviewers are all on the positive side of this paper. While the experiments are somewhat toy-like, all the reviewers appreciated the key idea and the theoretical results of this paper. I tend to agree and recommend acceptance for this paper.

However, I would strongly encourage the authors to improve their presentation for their final manuscript. Upon reading, the paper caused confusion on (1) using the terminology "unsupervised" and (2) its relationship to the prior work (Karalia et al. 2020). Although this concern has been resolved after a thorough discussion between reviewers and authors, I would be happy to see the corrections being made for the final manuscript. 
confidence: Certain
Decision: Accept