Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a (actually two) solution for solving combinatorial puzzles (such as Sudoku or graph coloring) by learning implicit constraints, using only solved instances in a way that generalizes across the size of the output space from which the variables are assigned. They exploit the graph size invariance of GNNs and convert a multi class node classification problem into a binary node classification problem, and use a generalization of the message passing approach of Palm et al. They show experimental results for their two solutions, and discuss the reasons for the accuracy / scalability tradeoff across the two.

main_review: The problem of generalizing across the size of the output space (the value-set) seems important. However, I'm not sure that the authors succeed in their stated goal of "implicitly learning underlying constraints using only solved instances". In fact the Constraint Graph $G_C$ and the Relation Graph $G_R$ (defined in section 3), derived from lifted CSP $\mathcal{C}_L$ seems to be going a long way towards explicitly describing the underlying constraints. At this point, the amount of effort in describing the graph seems comparable to the amount of effort that would have to be put in to actually creating a SAT instance of the problem (which could be solved by a SAT solver).
Other than this, the paper is reasonable well written, and the approach that they are taking seems reasonable if the goal is to understand how much we can push GNNs to solve combinatorial problems (even if it does not meet the stated goal of not explicitly specying the constraints).
On the experimentation front, it feels like the the only real metric for a combinatorial problem is "board accuracy", and I did not completely understand the "pointwise accuracy" metric - how does one decide if a variable is correct if the overall solution is incorrect for say graph coloring? How is this defined in situations where the values could be permuted (like the colors) or when there are multiple correct solutions?


summary_of_the_review: The paper is well written, the approach makes sense, but it does not feel like they are actually accomplishing their goal of not explicitly encoding the constraints (and learning purely from the solved instances). Given how much they are actually encoding the constraints into the graph, it feels like they should at least compare it with other solutions which would require an equal amount of constraint encoding (such as using a SAT solver).
Further, the results of the algorithm are not particularly impressive, if we consider "board accuracy" (pointwise accuracy feels like the wrong metric for combinatorial problems). 
On the pro side, this paper does address a problem that I've not seen tackled before and that seems to be important.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper raises an overlooked problem when using GNNs to solve combinatorial puzzles such as Soduku and graph coloring. The problem is as follows: when given larger instances of the problem, the GNN will have to predict values from a larger value set. The question is how can we train on small instances and generalize to large instances with different output labels. It is important to note that the paper does not study the standard size-generalization problem (can GNNs generalize to larger graphs) but rather to a different related problem when the larger problem has more output labels. 
The authors first formulate combinatorial puzzles as constraint satisfaction problems (CSP) and then suggest two ways of encoding these CSPs as graphs and process these graphs with GNNs. The idea is to encode the variable set of values in the graph structure. The first encoding is binarization - duplicating node variables for each possible output value. In the suggested encoding, called multiple values, they construct a graph with special nodes that represent the different possible values. Prediction is done by considering both variable and value node features together. 
In the final section, the authors present results on 4 different combinatorial puzzles, where their method is shown to outperform a generic neural reasoner.

main_review: 
**Strengths:**
- An interesting problem that was not studied before
- The suggested ways of encoding the values in the graph make sense and are elegant.
- Empirical results seem good 

**Weaknesses**

- The “size generalization works” assumption - the method assumes that GNNs can naturally generalize to larger graph sized. This is not necessarily true as was pointed out by several recent papers [“Size-Invariant Graph Representations for Graph Classification Extrapolations”, “From local structures to size generalization in graph neural networks”]. It would strengthen the paper if the authors could explain why this assumption works in their case. 
- Choice of graph connectivity - I am missing a discussion on the different choices of encoding CSPs as graphs. It seems like the authors come up with these two formulations and I am wondering whether there are other choices of encoding this which are better. A discussion on this design space can help.
- Writing style - the main technical part of the paper, in which the graph constructions and the message passing are described, is written in a very dense way and is difficult to read. I think that a revision to these sections can improve the paper. Moreover, more illustrations can definitely help (for example illustrating the message passing schemes). The current figure is nice but not enough. 



summary_of_the_review: The paper targets a new interesting problem and suggests two elegant ways to solve it. There are, however, several aspects in which the paper can improve, including explaining the underlying assumptions and the design choices better. 
  
**More comments**
- Intro: define CSP CNF  constraint graph
- figure 1 - add more details about the problems, constraints, and representation. Currently, it is difficult to understand.  
- Lifted CSP formulation is difficult to understand. What do you mean by reference? After reading it several times I think I understand what you mean but I think this part can benefit from a revision. Perhaps add an illustration? 
- Description of networks and message passing: too dense. Difficult to read. Visualization must be added.


**Post rebuttal:**
I would like to thank the authors for addressing my concerns. The paper has definitely improved, but I would like to maintain my score of 6 for now.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper intends to develop a learning framework (based on the recurrent relational neural network (RRN) ) that can handle output-space invariance issue.  Output-space invariance means that the model trained on smaller size data (like 9 by 9 Sudoku) can be generalized to larger size data (16 by 16) without any further modification. The entire problem formulation is done by lifted CSP. 

Based on RRN, the authors propose two methods: The binarized method and the Multi-value method. 

For the binarized method: the output value space is binarized, i.e., the model will score each candidate individually and the parameters are shared.

For the multi-value model, the value nodes are added to the architecture and the nodes connected to value k mean that the node can be assigned value k or it is already assigned value k.  A decent method is proposed to help the model learn a meaningful representation for all the possible values. 


main_review: Pros:

1. The problem itself is very essential since fixed output space does harm the generalization ability of the current neural solver. So a method that potentially can be applied to most neural solvers (based on message passing) is important.
2. The performance looks great to me. The multi-valued method largely outperforms the baseline and can generalize to big problem instances (like 24 by 24 Sudoku). 
3. The training method of the multi-valued method is elegant. 

Cons:

1. It would be better if the authors can try their method on the routing problems or other graph problems. Sudoku and Futoshiki are very similar. Moreover, graph coloring shares a similar property to Sudoku (basically all heavily rely on the All-Diff constraints). 
2. I am wondering what's the training time/cost compared between the two methods. The binarized model should have more parameters but it should learn faster while the multi-valued model is hard to train especially when the target output space is very large. When the size of the problem goes very high, I feel the converge of the multi-valued model could be a problem.

Minors:

1. For generating the Sudoku larger than 9. It would be better if you make sure all the data are permutation invariant.
summary_of_the_review: This paper proposes two methods for the output-invariance issue based on the RRN framework. An elegant training method for one of the methods (the multi-valued method) is proposed. The authors tested their methods on three problems and achieve very good performance. Though the three test problems are similar, the problem itself is very novel and essential. So I would recommend for accpet.
review_title: null

Meta-review: The reviewers were split about this paper: on one hand they would have liked to see more experiments on different problem settings on the other they appreciated the elegance of graph encoding methods and current results. After going through the paper and discussion I have voted to accept for the following reason:  the additional experiments and discussion posted during the rebuttal phase have addressed many of the main concerns of the reviewers (i.e., training time, message passing figure, discussion on encoding and SAT solvers). The only remaining one I see is the request for additional experiments which I don't think is grounds for rejection: current results are comprehensive and an additional experiment I think would not alter the main conclusions. I urge the authors to take all of the reviewers changes into account (if not already done so).
Decision: Accept (Poster)