Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposes a framework for learning combinatorial problems over graphs in which the solution can be expressed in terms of an ordered labeling of the nodes. Then, the authors propose GAT-CNL, a neural architecture leveraging the framework to learn to solve such class of problems in a greedy fashion. Empirically, the method presents better results when solving graph coloring and minimum vertex cover.
strength_and_weaknesses: --- Strength ---
a) The node labeling framework is a clear formulation of a wide class of problems and will help guide future contributions.
b) The graph coloring problem indeed never had, to the best of my knowledge, a more general ML solution.
c) Their MDP formulation allows for more than two labels and, more importantly, unknown number of labels. This is because a state is not a partial solution, but a partial labeling, which is fundamentally different.
d) Lemma 2.4 guarantees a solution in the MDP space, which is not a common result in previous literature.
e) Empirical results, especially for GC, are very promising.

--- Weaknesses ---
a) Throughout the text, the authors argue that node labeling and greedy strategies are intimately related (due to the ordering of labels). I understand that it's a natural relationship when we design heuristics, but we know that relationship does not necessarily exist in optimal solutions. I think it would be good to make this distinction more clear.
b) I find the proofs not rigorous enough (although the statements seem to be true to me). The authors try to present constructive arguments, which can result incur easily in this (without enough care). From what I see the proofs can be rewritten to use contradiction instead. A good example of this is Lemma 3.2's proof: The authors construct a solution and immediately conclude " Labeling the nodes in this order produces a minimum vertex cover of G.". I understand the lemma stands, but it reads sloppy.
c) I expected to see larger graphs in the dataset. Also, for ML in combinatorial opt, it is vital to test your solution on graphs that are larger at test time (shift in distribution).
clarity,_quality,_novelty_and_reproducibility: The paper is very well written and easy to follow. The entire training procedure, including hyperparams, is described, which results in transparency and good reproducibility. The paper is not very different from what the ML community has been doing in combinatorial optimization, so novelty is a bit limited (although it definitely exists).
summary_of_the_review: In my opinion the paper needs a little bit more of work, since the weaknesses currently outweigh the contributions. If the authors are able to test the solution on larger graphs and make the proofs more rigorous, I'm willing to raise my score.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors present a graph attention network trained using policy gradient reinforcement learning that can label nodes in an efficient way to (try to) solve hard combinatorial optimization problems. They test their method on the graph coloring and minimum vertex cover problem on different kinds of graphs , comparing the performances with greedy algorithms and different neural networks approaches proposed in the past.
strength_and_weaknesses: 
The idea to create an efficient way for node labeling in combinatorial optimization problems is new and promising. Indeed, in greedy algorithms (GA) one decides the rules to choose the next node to label. In GA these rules are chosen a-priori, and different choices are possible: taking inspiration from GA, the authors try to infer which is the best order using a Graph attention network: the resulting order for node labeling is different from the standard GA ones.

The main weakness of the paper is that the performances of the method are not extensively investigated and the comparison with existent methods to solve combinatorial optimization problems is not completely fair and exhaustive. Moreover, the weaknesses of the results are only shown in the Appendix and not in the main text.

For the graph coloring (GC), the authors compare their results with GAs and with the machine learning (ML) approach of Lemos et al (2019) (GNN-GCP). GNN-GCP is not very good for GC. In fact it acts as a classifier, with the only output being the predicted chromatic number and not a possible configuration of nodes labels. For this reason GNN-GCP can find a number of colors smaller than the correct one, that is a highly undesirable feature. I suggest to compare the results of the method proposed by the authors with other better ML approaches to GC, such as the one in Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Frontiers in artificial intelligence, 3:98, 2021 (the arXiv reference in the draft should be updated with the published one) or the recent Schuetz, Martin JA, et al. "Graph Coloring with Physics-Inspired Graph Neural Networks." arXiv preprint arXiv:2202.01606 (2022).

For GC on simple family of graphs, like wheels, trees, even/odd cycles, after a training on graphs up to 400 nodes, the proposed method finds the good chromatic number on graphs up to 1000. The author could test the performances on larger instances in this very basic examples to check if performances degrade going to larger sizes.

The runtime is shown in Fig. 6-7 for GC and Fig. 8 for MVC. In this last case, the scaling seems to be exponential with the size of the problem and not linear. However in both cases a fit should be performed to show if the scaling is linear or not. (In Fig. 6 the scaling of DSATUR seems to be not-linear too; however DSATUR is a simple greedy method that should perform in linear time, thus I have some doubt on the good implementation of it).

When tested on sparse Erdos-Renyi graphs of average connectivity c=7.5, the method proposed by the authors finds a chromatic number of almost 5 for instances with 100 nodes, and a chromatic number of almost 6 for instances with 600 nodes. However a standard message passing algorithm, or a stochastic walk-sat algorithm can find a good coloring with 4 colors up to connectivity larger than 8 for much larger graphs in linear time (see for example L Zdeborova and F Krzakala. Phase transitions in the coloring of random graphs. Physical Review E, 76(3):031131, 2007). Thus the performances of the proposed method are really poor in this case and degrade fast with growing sizes.

For MVC, following table 10 the proposed method cannot reach results obtained by other existing ML methods. Moreover no comparisons with standard algorithms is performed.

In Table 7 one notices that performances of the proposed method quite strongly depend on the training set: if trained on ER graphs, the performances on BA graphs reduce and vice-versa: the method cannot generalize well.
clarity,_quality,_novelty_and_reproducibility: The authors add their code in the supplementary material, to ensure reproducibility. However I did not test it.

For the reasons explained in the previous section, I do not think the quality of the paper is good enough. 

I list here some minor points / typos:
- Section 2.1: a node labelling is a mapping V→{0,…,n} . n, the max label, could be different from the number of nodes. Coloring is an example of that.
- Lemma 3.2: “...choosing the label 1 until every vertex in G is adjacent to a node…” replace vertex with edge
- Section 3.2, paragraph Local attention decoder: in the definition of a_v^{(t)} change h_i with h_v
- Table 9 only shows cost for ER and BA graphs, while in the caption also WS graphs are mentioned
summary_of_the_review: Summarizing while the idea of finding an efficient way for node labeling in hard combinatorial problems is new and interesting, the results obtained in the draft are not good enough: the proposed method cannot reach the performances of standard algorithms, it does not generalize well and its performances degrade going to larger sizes of the problems.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper extends S2V-DQN and enables it to cover more node-labeling-related problems. In terms of the neural network model, S2V embedding is replaced by more recent GAT embedding. Experiments are conducted on graph coloring and minimum vertex cover.
strength_and_weaknesses: **Strength**
1. This paper extends the classic S2V-DQN approach, with the purpose to fit into more general problems.
2. Learning node labels is an interesting characteristic of learning CO, which may inspire future papers.

**Weakness**
1. The overall pipeline of this proposed approach is very similar to S2V-DQN, and such a reinforcement learning pipeline is actually followed by many other papers to tackle different problems since the S2V-DQN paper was published in 2017. For example, the following papers also study graph coloring:
    * Enhancing column generation by a machine-learning-based pricing heuristic for graph coloring. AAAI 2022. 
    * Approximation ratios of graph neural networks for combinatorial problems. NeurIPS 2019.

   Considering these existing papers, the node-assignment step, which is the main technical contribution of this paper, seems incremental.

2. Adopting attention models for CO is either a new idea, for example, the highly cited paper:
    * Attention, learn to solve routing problems! ICLR 2018.

   So in this paper, replacing S2V with GAT in the model does not seem novel either.
2. Since the proposed scheme also covers "set" and "permutation" problems, it will be interesting to see the performance of the proposed method on well-studied problems such as TSP. It will be easier to position the effectiveness of this approach w.r.t. existing papers with the results on problems like TSP.
clarity,_quality,_novelty_and_reproducibility: The authors include code in the supplementary so the clarity and reproducibility are good.
summary_of_the_review: The idea of "learning node labeling" for CO is novel and interesting, however, the technical contributions of this paper seem trivial and incremental. I am suggesting a rejection in consideration of the lack of technical novelty.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a combinatorial node labeling framework, which solves CO problems by labeling the nodes. The model is based on graph attention networks and trained by reinforcement learning. Graph coloring and minimum vertex cover are studied. Experiments prove the performance of the proposed framework.
strength_and_weaknesses: Strength
- The perspective of unifying CO problems in the framework of node labeling is novel and makes sense. 
- Writing is good and the paper is easy to follow.
- Experiments are sufficient. Experimental settings (baselines, datasets, paremeter settings, etc.) are presented clearly, and results are convincing.
Weakness 
- One of the biggest concerns is whether the framework really works on the task MVC, which is usually not processed as  the node labeling problem in the main stream of literature. And in this sense, baselines are too old. To make the results more convincing, more recent baselines, e.g. [1][2], and traditional solvers should be compared. Only by comparing the sota methods and traditional ones on both running time and the results on the MVC problem, can the paper prove that node labeling works in tasks beyond graph coloring. Whether it `really' works well on MVC is the key point to judge whether the significance of unifying the CO problems into the node labeling framework is over-claimed.
-The other concern is the technical novelty of the paper, it seems to me an increment extension from binary classification to the multi-class case based on existing S2V-DQN framework.

[1] Local Search with Efficient Automatic Configuration for Minimum Vertex Cover
[2] Efficient Minimum Weight Vertex Cover Heuristics Using Graph Neural Networks
clarity,_quality,_novelty_and_reproducibility: The paper is presented in good clarity and quality. The idea is novel and the results are believed to be reproducible.
summary_of_the_review: This paper unifies a lot of CO problems into the node labeling framework. Experiments on graph coloring and MVC show the significance. The problem is that the significance of dealing CO problems as node labeling might be overclaimed. More experiments on MVC compare with stronger baselines or experiments on other tasks are recommended.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The reviewers agreed that this paper has important drawbacks. I think the reviews summarize well the strengths and weaknesses of the paper. The proposed method compares poorly to existing methods.  
justification_for_why_not_higher_score: The proposed method compares poorly to existing methods.
Decision: Reject