Neural Models for Output-Space Invariance in Combinatorial Problems
Authors: Yatin Nandwani
Vidit Jain
Mausam .
Parag Singla
Venue: ICLR 2022 Poster (2022)
Keywords: neural reasoning
output space invariance

Abstract: Recently many neural models have been proposed to solve combinatorial puzzles by implicitly learning underlying constraints using their solved instances, such as sudoku or graph coloring (GCP). One drawback of the proposed architectures, which are often based on Graph Neural Networks (GNN) (Zhou et al., 2020), is that they cannot generalize across the size of the output space from which variables are assigned a value, for example, set of colors in a GCP, or board-size in sudoku. We call the output space for the variables as ‘value-set’. While many works have demonstrated generalization of GNNs across graph size, there has been no study on how to design a GNN for achieving value-set invariance for problems that come from the same domain. For example, learning to solve 16 x 16 sudoku after being trained on only 9 x 9 sudokus, or coloring a 7 colorable graph after training on 4 colorable graphs.  In this work, we propose novel methods to extend GNN based architectures to achieve value-set invariance. Specifically, our model builds on recently proposed Recurrent Relational Networks (RRN) (Palm et al., 2018). Our first approach exploits the graph-size invariance of GNNs by converting a multi-class node classification problem into a binary node classification problem. Our second approach works directly with multiple classes by adding multiple nodes corresponding to the values in the value-set, and then connecting variable nodes to value nodes depending on the problem initialization. Our experimental evaluation on three different combinatorial problems demonstrates that both our models perform well on our novel problem, compared to a generic neural reasoner. Between two of our models, we observe an inherent trade-off: while the binarized model gives better performance when trained on smaller value-sets, multi-valued model is much more memory efficient, resulting in improved performance when trained on larger value-sets, where binarized model fails to train.

Published as a conference paper at ICLR 2022
NEURAL MODELS FOR OUTPUT-SPACE INVARIANCE IN COMBINATORIAL PROBLEMS
Yatin Nandwani, Vidit Jain; Mausam & Parag Singla
Department of Computer Science, Indian Institute of Technology Delhi, INDIA (yatin. nandwani, vidit. jain cs117, mausam, parags @cse. witd.ac.................. ac.inn in
ABSTRACT
Recently many neural models have been proposed to solve combinatorial puzzles by implicitly learning underlying constraints using their solved instances, such as sudoku or graph coloring (GCP). One drawback of the proposed architectures, which are often based Graph Neural Networks (GNN) (Zhou al., (2220), is that they cannot generalize across the size of the output space from which variables are assigned value, for example, We call the output space for the variables as 'value-set'. While many works have demonstrated generalization of GNNs across graph size, there has been no study on how to design a GNN for achieving value-set invariance for problems that come from the same domain. For example, learning to solve x 16 sudoku after being trained on only 9 x 9 sudokus, or coloring colorable graph after training on 4 colorable graphs. In this work, we propose novel methods to extend GNN based architectures to achieve value-set invariance. Specifically, our model builds on recently proposed Recurrent Relational Networks (RRN) (Palm et al. 2018 Our first approach exploits the graph-size invariance of GNNs by converting multi-class node classification problem into a binary node classification problem. Our second approach works directly with multiple classes by adding multiple nodes corresponding to the values in the value-set, and then connecting variable nodes to value nodes depending on the problem initialization. Our experimental evaluation on three different combinatorial problems demonstrates that both our models perform well on our novel problem, compared to generic neural reasoner. Between two of our models, we observe an inherent trade-off: while the binarized model gives better performance when trained on smaller value-sets. multi-valued model is much more memory efficient, resulting in improved performance when trained on larger value-sets, where binarized model fails to train.
3
5
of colors in GCP, board-size in sudoku.
10
11
12
14
16
18
19
20
21
22
23
24
25
26
INTRODUCTION
The capability of neural models to perform symbolic reasoning is often
step towards the
28
framework for unified AI, i.e., building end-to-end trainable system for tasks, which need to combine
29 low level perception with high level cognitive reasoning (Kahneman) 2011). While neural networks
30 are naturally excellent at perception, they are increasingly being developed for high-level reasoning
31 tasks, e.g., solving SAT (Selsam al. 2019 Amizadeh al.) 2019a b), neural theorem proving (Rocktäschel et al. 2015). differentiable ILP (dILP) (Evans & Grefenstette 2018), playing blocks
32
33 world (Dong et al. 2019), solving sudoku (Wang al. 2019).. Our work follows this literature for
34 solving combinatorial puzzles- in particular, the methods that implicitly incorporate the rules in their weights by training over some of its solved instances, e.g. Recurrent Relational Networks (RRN) PPam et al.] (2018). Such models assume a fixed value-set, i.e., the set from which variables are
35
37 assigned values is assumed to constant during training and testing. This a significant limitation.
since it may not always be possible to generate sufficient training data for similar large problems 39 in which variables take values from a bigger value-set (Najafian et al.) 2018). 8). It is also a desirable goal since humans, we often find it natural to generalize problems of unseen variable and value sizes, once we know how to solve similar problems different size, e.g., we may solve a 12 x 12
41
Equul contribution. Work done while IIT Delhi. Current email: vidit.jain @ aluumii. iit..ac.it

---

Published as a conference paper at ICLR 2022
sudoku after learning to solve a 9 x 9 sudoku. We note that graph based models have been shown to generalize well on varying graph sizes, e.g., finding a satisfying solution of CNF encoding of a CSP after training
43
with 100 Boolean-variable
CNF encodings of CSPs with only 40 Boolean- varriaa-variables (Selsam et al. 2 However, the model trained using CNF encoding of Boolean-CSPs cannot be used directly for non-Boolean CSP in which variables take value from different (larger) value-set.
45
46
47
In response, we study value-set invariance in combinatorial puzzles from the same domain. To formally define similar puzzle with variables taking values from a different value-set, we make use of Lifted CSP (Joslin & Roy 1997). (finite) first-order representation that can be ground to CSPs of varying variable and value-set set sizes. We note that even though we use Lifted CSPs to define value-set 51 invariance, its complete specification is assumed to be unknown. Specifically, we do not have access
48
49
50
52 to the constraints of the CSP, and thus neural SAT solvers like AT (Selsam et al. 2019) can not
53 be used. While training, we only assume access to solved instances along with their constraint graph.
54 We define our problem as: given solved instances and corresponding constraint graph of an unknown
55 ground CSP with a value-set of size k. can we learn neural models that generalize to instances of the same lifted CSP, but with different value-set of size k' (typically k/ > k)? An example task includes training model using data of 9 9 Sudoku, but testing
56
12 X 12 or 16 16 Sudoku. We build our solution using RRNs as the base architecture. They run GNN on the constraint graph, and employ iterative message passing in recurrent fashion the nodes (variables) are then decoded to obtain a solution. We present two ways to enhance RRNs for value-set invariance.
58
59
60
61
Binarized Model: Our first model converts multi-class classification problem into binary classifi- cation problem by converting a multi-valued variable into multiple Boolean variables, one for each value in the value-set. The binarized constraint graph gets defined as: if there is an edge between two variables in original constraint graph, there are k edges between Boolean nodes corresponding to the same value and the same two variables in the new graph. In addition, all & Boolean variables, corresponding to a multi-valuee
62
63
64
65
68
variable, are connected with each other. This model naturally achieves value-set invariance. At test time, a larger value-set just results in a larger graph size. All GNN weights are tied, and because all the variables in the binarized model are Boolean, embeddings for binary values '0' and '1', trained at training time, are directly applicable at test time.
67
68
69
Multi-valued Model: Our second model directly operates on the given multi-valued variables and the corresponding constraint graph, but introduces a value node for every value in the value-set. Each 72 pre- rrsiassg (unassigned) variable node is connected to that (respectively, every possible) value node.
71
73 The challenge in this model is initializing value nodes at test time when k' > k. We circumvent
74 this problem by training upfront k' or more value embeddings by randomly sub-selecting a k sized
75 subset during each learning iteration. This random sub-selection exploits the symmetry of value-set elements across instances. During test time, k' of the learned embeddings are used.
76
77 We perform extensive experimental evaluation on puzzles generated from three different structured CSPs: Graph Coloring (GCP), Futoshiki, and Sudoku. We compare two of our models with an NLM (Dong et al. 2019) baseline generic neural reasoner, which either fails to scale or performs significantly worse for most test sizes used in our experiments. We also compare our two models along the axes of performance and scalability and discuss their strengths and weaknesses.
78
79
80
81
2 RELATED WORK
82
83
This paper belongs the broad research area of neural reasoning models, in which neural models learn to solve pure reasoning tasks in data-driven fashion. Some example tasks include theorem proving (Rocktäschel al., 2015 Evans & Grefenstette| [018)). logical reasoning (Cingillioglu &
84
a5
86
Russo 2019), probabilistic logic reasoning (Manhaeve et al. 2018), classical planning (Dong et al.
87
2019). probabilistic planning in a known MDP (Tamar et al. 2017] [Bjjaai et al. 2018), and our focus combinatorial problems that are instances of an unknown constraint satisfaction problem.
89
There are two main research threads within neural CSPs and SAT. First thread builds neural models for problems where the CSP constraints SAT clauses are explicitly provided to the model. For example, NeuroSAT (Selsam et al. 2019) and PDP (Amizadeh et al. (209bb) assume that the CSP is expressed in Conjunctive (or Disjunctive) Normal Form. Similarly, Circuit-SAT (Amizadehl
91
93 et al. 2019a) uses the knowledge of exact constraints to convert a CSP into a Boolean Circuit. This
94 research has similarities with logical reasoning models like DeepProbLogg (Manhaeve et al. 2018).
2

---

Published as a conference paper at ICLR 2022
95
and DeepLogic (Cingillioglu & Russo 2019), which require human designed rules for reasoning. Our work belongs to the second thread where the constraints or clauses are not provided explicitly, and only some underlying structure (e.g., Sudoku grid cell connectivity) is given along with training data. The intention is that the model not only learns to reason for the task, but also needs to learn the implicit semantics of each constraint. SATNET (Wang et al., 2019) falls in this category it formulates learnable low-rank Semi-definite Program (SDP) relaxation for a given MAXSAT problem trained
96
97
98
99
100
101
via solved SAT problems. Similarly, Recurrent Relational Networks (RRN) (Palm et al. 2018 use recurrent message passing graph neural network to embed the variables of the unknown CSP, and the relationship between them, in a latent vector space and finally assign a value to each variable based on its embedding. Both these works assume fixed number of variables that remains unchanged across training and test. While we build on RRNs, we substantially extend the formalism to study value-set invariance. Formally, our work can be seen as solving (finite) first-order formulation of the CSP, called Lifted CSP (Joslin & Roy 1997). which can be grounded to CSPs with varying number of variables and values. To our knowled ledge there is relatively limited prior work neural models that can generalize to variable-sized instances of an underlying first order reasoning task - one related approach builds neural models for First-order MDPs (Garg et al.) 2020
102
103
104
105
106
107
109
110
111
Finally, there has been a long history of work dedicated to learning rules or constraints from training
112
data using Inductive Logic Programming (Lavrac & Raedt 1995 Friedman et al.
1999). |vvan &
Grefenstette (2018) propose differentiable neural relaxation of II. (JILP). Neural Logic Machines
113
114
(NLM) (Dong et al. 2019) is another framework that learns lifted rules. shown be more scalable
115
than ÖILP It allows learning of first-order logic rules expressed as Horn Clauses over a set of predicates. Learning of first-order rules makes NLM amenable to transfer over different CSP sizes
118
117
Nandwani et al. 2021), and are thus directly comparable to our work. The main challenge of such approaches that they fail to scale to the size of the problems considered in this work. In our experiments, we compare our methods against both deep and shallow versions of NLM. Note that our work relies on the assumption that GNNs generalize across graph sizes. Yehudai et al. (202T) study the scenarios under which this assumption may not hold. We discuss the details in the appendix.
118
120
122
3 PRELIMINARIES AND PROBLEM DEFINITION
123
combinatorial puzzle can be thought of as grounded CSP and to formally define a puzzle from the same domain but larger value-set, we resort to the notion of LLifted CSPs' that represent an abstraction over multiple ground CSPs of the same type. A lifted CSP does not include a specific set of variables and values; instead, it operates in terms of variable and value references that can be instantiated with all ground variables and values in a ground CSP. This makes them amenable well as values. We define Lifted CSP Le as a three tuple (P, R, C). P is a set of predicates: a predicate E P represents Boolean function from the set of its arguments, which are variable references. Similarly, R is a set of relations over value space a a E R reprents a Boolean function over arguments that are value references. A predicate (or relation) with its arguments is called an atom. C is a set of lifted constraints, constructed by applying logical operators to atoms - they are interpreted as universally quantified over all instantiations of variable and value references. Finally, Lifted CSP uses special unary function Value, whose argument is a variable reference and evaluates to a value reference. As an example, a lifted CSP for Sudoku may have a P = [Nbrr } for whether two cells are in same row, column or box, R = (Neq), representing two values are unequal, and lifted constraint: Nbr(c1, 02) + Neq(Value (c1) ), Value(C2)).
124
125
126
127
to instantiate CSPs or puzzles with varying number of variables
129
130
131
132
133
134
135
196
137
138
139 A lifted CSP Le yields a ground CSP C, given a set of variables O, and a set of values V. and complete instantiation of all predicates and relations over this set (e.g.. in Sudoku, the number of cells, possible values, and which cells are neighbors and which are not). The ground constraints are constructed by instantiating lifted constraints over all variables and values. A (satisfying) solution, y, of CSP refers to complete specification of Value: O + V function, such that all the constraints are satisfied. We are often given a partial (satisfying) solution, x an assignment of values to a subset of variables Ô C O and the goal is to output y, such that y agrees with x for the subset Ó.
140
142
144
145
146
Given a ground CSP C, the Constraint Graph, Gc (Nc, Ec), is constructed by having, each variable in the CSP represent a node in the graph and introducing an edge between two nodes nif n& iff the corresponding variables appear together in some constraint. The edges in the constraint graph
147
148
3

---

Published as a conference paper at ICLR 2022
typed based on the identity of the lifted constraint from which it comes. Note that there could be multiple edges between nodes nf ny in Gc, if these nodes appear together in more than one constraint. We embed the knowledge about relations between values in V in the form of another graph, called Relation Graph, GR = ( RN En), where there is a node for every value in the set V. and there is (directed) edge between nodes corresponding vi; 1/f depending on whether r(1z, vy) is true or not, for every E R. Similar to Gc. this graph can also have multi-edges between two pairs of nodes, if more than one relationship holds between the corresponding values.
150
152
153
154
155
156
Problem Definition: To achieve value-set invariance, our goal is to train model Me on training data from an unknown ground CSP C (with variables O and value-set V) obtained from an unknown lifted CSP Lc. and test it on an arbitrary ground CSP C" from the same lifted CSP (with variables
157
158
O' and value-set )*), where |V] # |V' Formally, we are given training data D as a set of tuples L.M ii= along with relationship graph Gn encoding re relations between values in the value-set V. Here, 1t instance denotes partial and corresponding complete solution for C². We note that explicit form of the constraints in C* or Le are not available, only the graphs are given to the model. Our goal is to learn model Me. such that given graphs Ge and GRe, and partial solution (for CSP C') : (x') = y', only if y' is corresponding complete solution for x'. Note that in one of our models, we will additionally assume that max [V',, denoted kmax, is known to at training time, which we argue is a benign assumption for most practical applications.
159
[((x), Gc)), y')
160
161
162
164
166
4 MODELS DESCRIPTION
167
168
We propose two models for value-set invariance: the Binarized Model, and the Multi-valued Model. In each case, we assume the training data is provided in
169
Input Puzzle
170
the form D= (((x), Gcs).y" f1=1 GR) ) as described in Section 3 Let V and V denote the value-sets at train and test time, with cardinality k, K' respectively.
171
172
175
174
For each model, we first present a high level intu- ition, followed by description of: (a) Construction of Message Passing Graph (b) Message Passing Rules
Solution
175
t
177
(c) Loss Computation, and finally (d) Prediction on problem with larger value-set.
Relation
Constraint Graph
Multi-Valued Graph
Graph
Binary Graph
178
Figure 1: An example Futoshiki Puzzle of
179
4.1
BINARIZED MODEL
size 3 3 and the corresponding graphs. A value of -1 indicates an unassigned vari- able. Black and red edges Constraint and Relation edges respectively. The digits 5, 7, 1 in square boxes represent a random 3- permutation of kimax, used in multi-valued model for initialization of node embeddings.
180
Intuition behind our Binarized Model comes directly from the 'sparse encoding" of a discrete CSP into a SAT formula dd Kleer 1989 Walsh 2000), in which value v E V to any variable x[i] E assignment
181
represenn
185
O is encoded by Boolean variable that represents
185
xjj == V. Such an encoding converts a single multi-
valued variable into multiple Boolean valued variables ! We convert a Constraint Graph (fig. 1
186
187
with nodes representing multi-valued variables (yellow nodes), into a Binary Graph (fig. D with Boolean nodes (blue nodes). This creates a |.Nc| l grid of Boolean nodes, with a row representing a variable, a column representing a value and a grid cell (a Boolean node) representing assignment of a particular value to a particular variable. Such a graph can easily represent relationship between the values as well (horizontal red edges), thereby encapsulating the information present in the Relation Graph (fig. [T. We use this Binary Graph for message passing.
188
189
190
191
192
193
Construction of Message Passing Graph: We denote the Message Passing Graph (MPG) by G G= (N, E) with the set of nodes N and set of edges F,, constructed as follows: Nodes: For each C node ny E No in the Constraint Graph (fig. [ yellow nodes), we construct & binary valued nodes, denoted as 1j.1. n22.2 ",jk in N (blue nodes in Binary Graph). Edges: We construct two categories of edges in G. The first category of edges are directly inherited from the edges of the constraint graph Ge (black vertical edges), with At copies created due to binarization. Edge type is same as in the original constraint graph and denoted by q. Formally, for every edge, e. (J') E Ec,, where
194
195
196
197
199
There is an alternative encoding scheme called 'compact encoding'. It discussed in the appendix
4

---

Published as a conference paper at ICLR 2022
ec "y'' = 9. we introduce A edges denoted as Eig,,1) i.e., there is edge between every pair of nodes, ny,1 and ny,,. S 1 S k. We refer to them as Constraint Edges. The second category of edges encode the information from the Relationship Graph GR into the MPG, with |Nel copies of it created, one for each variable. For every edge c (1,1") E En with edge type r. create an edge (i.rrr
201
202
203
204
with type r between every pair of binary nodes 7j.1 and 33.r. 1 J I Ncc (e.g., red edges encoding less- than relation between value pairs (1, 2). (2, 3) and (1,3)). We refer to them Relational Edges.
205
206
Recurrent Message Passing: Once MPG has been constructed, we follow recurrent message
207
passing rules, with weights shared across layers, similar RRNs (Palm et al.) 2018) with some differences. For each node U111 in the graph, we maintain hidden state hig (1j.), which is updated at each step based on the messages received from its neighbors. This hidden state used to compute the probability of a binary node taking value of 1. Since we use sparse encoding, only the node with maximum probability amongst the binary nodes "j.;; S 1 S k, corresponding to multi-valued variable x[i], is assigned a value 1, at the end of message passing. We give the details of message passing and state update function in appendix. Next, we discuss how the nodes are initialized before message passing starts, followed by the details of loss computation.
208
209
210
211
212
213
215
Irrespective of the size of value-set V or vertices Ne, there are learnable embeddings (u : x|]] and u[-1)) for initialization: two for binary values 0 and 1, and one for value -1 repre- senting unassigned nodes. All nodes corresponding to an unassigned variable x(j] are initialized with u| -1, i.e., whenever x[j] is NULL (yellow nodes with - 11). un (n2.a) = ul u[-1]. Ve, V, where up represents initial embedding function. On the other hand, if x(j) is preassigned a value 1i then un (1j,1 = u (0) Vn F 11. and (n(2,,)) = u(1]. E.g., variable corresponding to the binary nodes in 1st row has preassigned value of '3', consequently, binary nodes in 1st and 2nd column of the 1st row are initialized with u/ v(O), and binary node in the 3rd column of 1st row, which corresponds to assignment x[1] 3', is initialized with v[1]. Lastly, the hidden state, ho (n1,1), of each node, nJ,1- is initialized as a O vector, Vj. Vuj.
Initialization:
217
219
220
221
222
223
224
225
Loss Computation: The Binary Cross Entropy (BCE) loss for each node nj,1 computed w.r.t. its target, yij, 1j. which is defined as 1 whenever y/j] = 1 and 0 otherwise. At each step E {1... 7T, we can compute the probability Pr(mj..v = 1; θ) of classifying a node nj.1 as by passing its hidden state through a learnable scoring function s, i.e., (re = 1: 1:0) (ss(h
226
227
228
229
where a is the standard Sigmoid function. Here, 'j,1-U denotes the value that node nj.1 can take and belongs to the set 1). Loss at step is the average BCE loss across all the nodes: EmSIEN yii 1] log (ry = 1;0) + (1 - -i.. log (r. = 0). Like Palm et al. 2018), we back-propager through the loss at every step / E (1... T) as it helps in learning con- vergent message passing algorithm. During training, the objective is to learn the initial embeddings
231
233
1], u/ (0], u [1). functions used in message passing and state update, and the scoring function
235
Prediction on problem with larger size of value-set: While testing, let the constraint and relation graph be Go and GR with n' and k' nodes respectively. Let be partial solution, with ní' variables x' (ij,. each taking a value from value-set V' of size k'. As described above, we create a graph G" with
237
n' k nodes, run message passing for T steps, and for each variable x'j], compute the K' probabilities,
238
one for each of the 1'' nodes ny.ivl E V corresponding to the variable x' x'ij,, which is assigned the
239
value corresponding maximum probability, i.e., []] arg maxiey Prr (1g.1.0 1. 1; O).
240
241
4.2
MULTI-VALUED MODEL
Multi-valued model differs from the binarized model by avoiding binarization of nodes, and instead explicitly adding Value Nodes in the message passing graph. one for each value in the value-set. The message graph consists of two components: (a) A Graph G = (N, E) to represent constraints inherited from the constraint graph Gc = (Ne, Fe)) (b) A Graph G (N, F.) to represent relations inherited from the relationship graph Gn = (Nn. Fn). We refer to G as Constraint Message Passing
243
244
245
246
Graph (CMPG), and & as Relationship Message Passing Graph (RMPG). Message passing on
248
RMPG first generates desired number of embeddings (upto kmax), one for each of the value nodes.
This is followed by message passing CMPG which uses the embeddings of the value nodes generated by RMPG and computes embeddings for each variable node. Finally, the variable nodes classified based the similarity of their embedding with the embeddings of the value nodes
250
5

---

Published as a conference paper at ICLR 2022
computed by RMPG. Learning to generate upto kmax embeddings from training samples with only
253
k( < kmax) values in the value-set is the main technical challenge that we address in this model.
Construction of CMPG: Nodes: For each node nf .Nc in the constraint graph, construct k- valued node, denoted as n E N. Total number of such nodes constructed is |Ne)). We refer to these as Variable Nodes (yellow nodes in Multi-Valued Graph in fig. Additionally, for each value un E V in the value-set, we create node, denoted as ni N. Total number of such nodes constructed is [V] We refer to these as Value Nodes (orange nodes). Edges: For every edge, ec (iJ') E Ec. where e" "type = q. we introduce an edge denoted as c'33n with type q. These 259
256
257
258
260
edges are directly inherited from the constraint graph. We refer to these as Constraint Edges (black edges). Additionally, to indicate the pre-assignment of values to the variables in x, we introduce new edges connecting value nodes to appropriate variable nodes. Whenever x[j] = vn add an edge, (J.)) between variable node nj and value node ni (blue edges). If x(j) is NULL, i.e., unassigned, then add k edges, (.,; Vey E V. connecting the variable node n, with all lo value nodes ni (e.g., green edges connecting orange value node '2' to all '-1' variable nodes). We refer to them as Assignment Edges.
262
263
264
285
Construction of RMPG: Nodes: For each value 1n V, create node denoted as ñj E Ñ (purple 267
266
nodes in Relation Graph in fig. D.. Total number of such nodes constructed is [V]. We refer to these as Value Nodes, Edges: For every pair of value nodes, nij and 7i.. introduce an edge (..)) with type if r(n, vv) holds based on the relationship graph GR. i.e., e (L.1) E ER with edge label (red edges). These edges are defined for relations that exist between values in the value-set.
268
270
Achieving Value-set Invariance: A key question arises here: why do we need to construct separate RMPG (G)? Why not embed relevant edges in CMPG (G), as done for the binarized model? The answer lies in realizing that we represent each value in the value-set explicitly in the multi-valued model, unlike the binarized model. Hence, our model needs to learn representation for each of them in the form of value node embeddings. Further, to generalize we need to learn as many embeddings as there are values in the largest test value-set, i.e., Kmax max (V) We achieve this by randomly sub-se selectie a k-sized set from {1. Amax] and permuting the chosen subset for each training example in given mini-batch, and then computing the 'relationship-wware" embeddings from this permuted subset through message passing in RMPG The 'relationship-awarr' embeddings are then
272
273
275
276
277
278
279
280
used to initialize the value nodes (orange nodes) during message passing in CMPG. For instance, if the permutation obtained is (wI,.... wi,- ... w,}. where vl, 1 < wi S kmaax. then embedding for the value node ni in G is initialized by with learnable embedding (e.g., purple nodes for values '1,, 22, and '3' are initialized by the 5th, 7th, and 1st learnable embedding, respectively). After embedding of ūj (purple node) is used to initialize the embedding for value node nf (orange node) in G. This elegant process is able to train all the kmaxx embeddings by simply using the training data corresponding to V. and the corresponding relationship informatinn. Since these relationship aware embeddings need to be pre-computed before they can be passed to the downstream constraint processing, we construct two different message passing graphs, one for computing relationship- aware embeddings and one for constraint handling.
281
282
283
message passing on G, the 'relationship-wware
284
286
288
290
Recurrent Message Passing on RMPG: Rules of message passing and hidden state updates at every step are similar to RRN in Palm et al. (2018) and defined in detail in the appendix. After updating the hidden states for total T steps, the final embeddings, hy (m,") Yo E V, are used as telationship-aware embeddings for initializing the input features (embeddings) of the nodes in CMPG G. We now discuss the initialization of the value nodes before message passing in RMPG.
292
293
294
285
Initialization:
There are a total of kmax learnable embeddings, ú 1), 1, < I' < kimax, out of which any k are randomly chosen for initializing the nodes in RMPG. e.g., 5 ū[[] [[[] are chosen to initialize
296
297
the purple value nodes $1' 22, and '3' in Relation Graph in fig. D Formally, for each input x, select
a k-permutation, Px. of kmax- Initialize the embedding of ñj in G with [I],, VI E k1.
298
Initialize the hidden state, ho ho(r, Vn E N with a 0 vector.
300
Recurrent Message Passing on CMPG: Message passing on CMPG updates the hidden state, he (nj). of each variable node ny for a total of (t < T) steps using the messages received from its neighbors. The details are similar to message passing in binarized model and are discussed in the appendix. Below we describe the initialization of node embeddings followed by computation of loss.
302

---

Published as a conference paper at ICLR 2022
Table 1:
Futoshiki: Mean (Std. dev.) of Board and Pointwise accuracy on different board sizes. MV and BIN correspond to Multi-valued Model and Binarized Model, respectively.
Board Accuracy
7
8
9
10
11
12
NLMIS
73.37 (1.34)
56,98 (1.47)
48.71 (1.96)
44.16 (1.72)
31.54 (2.74)
32.50 (2.84)
NLM30
85.72 (0.39)
69.61 (0.57)
63.52 (1.20)
60.73 (1.29)
55.94 (0.85)
MY
99,62 (0.18)
90.18 (2.38)
71.58 (4.66)
54.85 (6.89)
38.51 (5.62)
24.18 (4.49)
11.97 (5.54)
BIN
99.86 (0.01)
97.92 (1.27)
93.39 (4.08)
89,39 (6.03)
83,48 (10.7)
76,14 (15.83)
68.15 (22.08)
Pointwise Accuracy
NLMI5
96.72 (0.16)
93.9 (0.26)
93.43 (0.26) 93.86 (0.28)
94.07 (0.29)
94.29 (0.31)
NLM30
97.88 (0.05)
95.32 (0.10)
95.09 (0.14)
95.48 (0.08)
95.68 (0.03)
MV
99.91 (0.03)
98.84 (0.24)
97.09 (0.46)
96.07 (0.60)
95.17 (0.53)
94.52 (0.41)
93.99 (0.60)
BIN
99.97 (0.00)
99.63 (0.13)
99.02 (0.37) 98.60 (0.47)
98.23 (0.68)
97.85 (0.98)
97.66 (1.31)
304
Initialization: We initialize the embedding of value nodes (orange nodes), ni in G, using the final trelatonship-aware" embeddings, (ff), of nj (purple nodes) in G. The variable nodes that are preassigned a value (non-7ero yellow nodes) in x, are initialized by the embedding of the corresponding value node, i.e., if x(j = 1, then ny is initialized with the 'relationship-aware embedding, (mf), of vn.. The embedding of nodes corresponding to the unassigned variables
305
306
307
308
309
('-1' yellow nodes) are initialized by the average. (1/k) (7)), of all 'relationship-wwar embeddings. Initialize hidden state (nz) of each variable node ny with a 0 vector.
310
For each variable represented by node nj. the ground truth value yij] acts as the target for computing standard Cross Entropy Loss. The probabilities over V are computed as follows: At step scoring function, s. computes score, (ng) hn(n))) (n((()))),,,(()) for assigning
Loss Computation:
312
314 a value in E V to a variable nj based on the hidden state of corresponding value and variable nodes. For each variable node, a Sofftaas converts these scores into probabilities over the values v) = fofttaazss(hhh
316
h, (n())))), Ven E V, where, Ny.V E V denotes the value that node nj can take. Loss at step L nothing but the average over variable nodes: I = - E log Pr(ng.v yjj). To ensure that the multi-valued model learns different embeddings for each value in the value-set, we add an auxiliary loss term, corresponding to the total pairwise dot product (similarity) of any two embeddings, before and after message passing in G. We call it Orthogonality Loss. Its weight, a, is a seyper-parameter.
on E V. i.e., Pr(nj.v
317
318
319
320
322
Prediction on a problem with larger size of value-set: For a puzzle with larger value-set, V", a bigger RMPG is created, whose 1 nodes are initialized with the (learnt) first k' embeddings. Unlike training, we always choose first k'' embeddings to avoid randomness during testing. Prediction is made using the probabilities at the last step T, i.e. [ arg max,,ev' Pr(ni.0 17).
323
324
328
Relative Comparison: In the binarized model, the constructed graph G' has k|NNel nodes and at least & Fel + (k(k 1)/2 edges due to binarization. This increases the graph size by a factor of at least k. As a result, we soon hit the memory limits of GPU while training the binarized model with bigger problems. The model also needs significantly more inference time due to its bigger size.
327
328
329
On the other hand, multi-valued model, while being compact in terms of its representation, needs to learn additional embeddings, for a speculative size of value-set during testing. This poses additional requirement on the model both in terms of representation, and learning, possibly affecting the quality of generalization. While this is a simple analytical understanding of the possible merits of the two models, we examine experimentally the impact of these issues on real datasets.
331
332
333
334
335
EXPERIMENTS
336
The goal of our experiments is evaluate the effectiveness of our two proposed methods for achieving value-set set invariance. We compare our models with a generic neural constraint learner, NLM (Dong ct al. 2019 We experiment on datasets generated from Lifted CSPs of three different puzzles, viz., Sudoku, Futoshiki, and Graph Coloring (ref. Table 5 in appendix for details). We train each model on data generated from a fixed value-set, and test on instances generated from larger value-sets.
337
338
339
340
2 Our aim is not to directly compete with SOTA SAT solvers, which are much more scalable than neural methods. Refer appendix for a discussion on comparison with them as well neural SAT solvers.
7

---

Published as a conference paper at ICLR 2022
5.1
TASK DESCRIPTION AND DATASETS
342
Futoshiki: This a number puzzle in which we have to place numbers {1.. {1...k, k} on k x k grid. such that no two cells in row or column contain the same number. In addition, there may be an ordering constraint between two cells, which needs to be honored in the final solution. The imput has some of the grid cells already filled with a number and the task is to complete the grid, respecting the additional ordering constraint where ever it exists. We train our model on 6 6 puzzles, with the percentage of missing cells varying uniformly between 28 70%. We test our models on puzzles with board size ranging between x 6 to 12 x 12, with the same percentage of missing cells.
343
344
346
348
Graph Coloring (GCP): In this task
350
we are given a partially colored graph
Table 2: GCP: Mean (Std. dev.) of coloring and pointwise accuracy on graphs with different chromatic number.
351
along with the number of colors k and
352
the objective is to color rest of the
Board Accuracy
353
nodes using & colors such that no two adjacent nodes have the same color.
5
NLM24
70.78 (5.3)
71.25
73.20 (7.58)
354
MV
97.80 (0.03)
97.72 (0.37)
94.03 (2.54)
72.21 (11.17)
355
We train our model on randomly gen- erated 4-colorable graphs, and test
BIN
99.09 (0.07)
96.69 (2.61)
95.7 (4.04)
94.35 (4.82)
Pointwise Accuracy
357
on coloolaee graphs, with k' E {4, 5, 6, 7}. Training data has graphs with graph order varying uniformly be- tween 40- 120, and percentage of masked nodes vary uniformly between 28- - 70%.
MV
NLM24
99,96 (0.00)
99.47 (0.13)
99,89 (0.00)
98.58 (0.34) 97.95 (0.54)
99.50 (0.23)
96.22 (1.55)
97.26 (0.68)
BIN
99.96 (0.01)
99.85 (0.03)
99.76 (0.08)
99.48 (0.16)
359
361
Sudoku: We randomly select 10, 000 training queries from the 9 x 9 dataset introduced in Palm
362
al. 2018). Our test set has K' x k puzzles, with K' E {10, 12, 15, 16). Data generation process is similar to Futoshiki, with the distribution of missing cells varying between 30 - 68% depending on the board size. Instead of backtracking, solution validity is checked through the GSS library (Pieters)
363
384
385
2019
Please see appendix for more details on data generation process for all three tasks.
366
5.2
EXPERIMENTAL SETUP & BASELINES
387
In both our models, nodes are initialized with learn- able 96 dimensional em- beddings. In multi-vllued model, kimax = 12, 7, and 16 embeddings are learnt for Futoshiki, GCP, and Su- doku respectively. Message passing on G in binarized
Table 3: Sudoku: Mean (Std. dev.) of board and pointwise accuracy on different board-sizes. Both models trained on 9 x 9 puzzles
368
369
Board Accuracy
370
9
10
12
MV
92.78 (0.08)
99.65 (0.15) 88 30.30 (6.08)
29.33 (13.71)
19.70 (14.03)
372
BIN
99.13 (0.14)
99.91 (0.04)
99.63 (0.10)
63.05 (45.71)
27.31 (23.81)
Pointwise Accuracy
MV
98.5 (0.05)
99.96 (0.02)
99.43 (0.26)
97.03 (0.71)
96.30 (0.90)
374
BIN
99.87 (0.02)
99.99 (0.00)
99.96 (0.01)
95.55 (6.60)
88.39 (14.25)
375
model runs for 32 steps. Message passing on RMPG, Õ and CMPG, G in the multi-valued model
376
runs for T = and T = 32 steps respectively. The message passing functions in both the models are 3 layer MLPs, similar to those in RRN, with a difference that there is a separate function for each edge type. In both the models, layer normalized LSTM cell with hidden dimension 96 acts state update functions. All models are trained on K40 GPU nodes with 12GB memory. We take simple average of model weights stored at multiple points (Izmailov et al. 2018 All checkpoints obtained after flattening of the learning curve are selected for computing average. See appendix for details.
378
379
380
381
382
383
Baseline: For Futoshiki, we train two versions of NLM by varying depth: the number of Logic Machines that are stacked on top of each other. Like (Nandwani et al., 2021), we train one 30 layer deep NLM model with residual connections for Futoshiki, but unlike them, we assume access to constraint graph, which we provide as a binary predicate input to the model. NLM with 30 depth could not fit puzzles with board-size greater than 10 within 12GB memory of K40 GPU. Hence, we train another version by reducing the depth to 15. For GCP, we train model with depth 24. For Sudoku, on increasing depth beyond 14, we could not fit even one x 9 train sample within GPU memory. Note that the maximum depth chosen for the graph experiments reported in (Dong et al. 2019) is 8. This is because they work with much smaller graphs (up to maximum 50 nodes), whereas smallest graph in Futoshiki has 63 216 binary nodes, warranting creation of much deeper models.
384
385
387
389
390
391
392
393
Evaluation Metrics: We report two metrics: board accuracy and point-wise accuracy. In the former, we consider output of the model as correct only if it satisfies the underlying CSP, whereas in the later,
394
8

---

Published as a conference paper at ICLR 2022
give partial credit even for assigning some of the variables correctly. See Appendix for details. For each setting, we report the mean and standard deviation over three runs by varying random seed.
396
397
5.3
RESULTS AND DISCUSSION
Table 4: Sudoku: Mean (Std. dev.) of board and pointwise accuracy of models fine-tuned on 24 board-size
398
We report the accuracies over differ- ent sizes of value-set for Futoshiki, GCP and Sudoku in Table 1 2 and respectively. We first observe that NLM fails to train on Sudoku, and its performance is worse than one or both of our models for all experimen- tal settings in Futoshiki and GCP. As expected, in Futoshiki, NLM model with depth 30 fails to run on board sizes 11 and 12 and depth 15 model fails to run on size 12. Note that both NLM and our binarized model work by binarizing the underlying puzzle, but we observe that binarized model shows significantly better generalization across value-sets. We note that NLM performs decently well for GCP even for the test graphs with chromatic number k' 7. We attribute this to the fact that in our test data for k' = 7, graphs are relatively small, with max 80 graph nodes, resulting in total 560 binary objects in NLM, which is similar to the max 400 binary objects that it trains over (k=4, max 100 nodes).
Board Accuracy
400
MV
91.03 (3.25)
(3.49
54.57 (21.25)
43.77 (14,42)
BIN
63.05 (45.71)
27.31 (23.81)
(.00)
0.0 (0.0)
402
Pointwise Accuracy
403
MV
99.43 (0.16)
99,46 (0.15)
99.30 (0.12)
99.10 (0.09)
404
BIN
95.55 (6.60)
88,39 (14.25)
7.85 (0.63)
7.44 (0.43)
405
407
409
411
412
413
Comparison between binarized model and multi-valued model: We first observe that both our models achieve similar performance on the value-set over which they are trained. We observe that the standard deviation of the board accuracy increases significantly as the size of value-set increases, whereas the pointwise accuracy relatively stable. This is due to the high sensitivity of the board accuracy to pointwise accuracy: even if single variable is incorrectly assigned in puzzle, its contribution towards board accuracy goes to O, whereas it still contributes positively towards pointwise accuracy. When trained on small sizes, binarized model shows better generalization. But as the problem size increases, the computational graph for binarized model fails fit in the available GPU memory and thus its performance degrades. On the other hand, multi-valued model being memory efficient, scales much better. To demonstrate this, Table reports the performance of multi- valued model further finetuned on sudoku puzzles of board-size 24, and tested on board-sizes varying between 15 and 25. We couldn't finetune the binarized model as its computational graph doesn' 't fit in the GPU. The binarized model trained on puzzles of board-size 9 gives 0.0 board accuracy on size 24 and 25. The performance of multi-valued model is better than binarized model not only on board-size 25, but also board-sizes smaller than 24. This also demonstrates that the poor performance of the same multi-valued model trained on smaller board-size is not due to any lack of representation power, but due to difficulty in learning additional embeddings: when training k' embeddings from puzzles of board-size size k. multi-valued model never gets to see all k' value embeddings together. Moreover, the different combinations of k out of k embeddings increase exponentially with (k' k). making it further difficult to train. To validate this, we train multi-valued model with only 7 learnable embeddings for Futoshiki and observe that the board accuracy on board-size increases to 97.82% (at par with binarized model) from 10% which is achieved when trained with 12 embeddings.
414
415
416
417
418
419
420
422
424
426
428
429
430
431
433
435
Computational complexity: In fig. 2 for the two models, we com- pare the average inference time and the GPU memory occupied by a batch of 32 Futoshiki puzzles over value-sets of varying sizes. As expected, the
Time in (s)
20
Binary
437
10
model is much more efficient, both in
439
terms of time and memory.
10 11 12 size of value-set
6 CONCLUSION AND FUTURE WORK
(a) Runtime
Memory in (GB)
Multi-Value Binary
441 We have looked at the novel problem of value-set invariance in com- binatorial puzzles, formally defined using lifted CSPs and proposed two different neural solutions extending RRNs. Our experiments demonstrate the superior performance of our models compared to an existing neural baseline. We discuss the relative strengths and weaknesses of our proposed models. Future work includes solving more complicated CSPs, and scaling even larger sizes.
442
444
10
size of value-set
446
(b) Memory
Figure 2: Resource: Futoshiki

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
449
We thank ITT Delhi HPC facility for computational resources. We thank anonymous reviewers for their insightful comments and suggestions that helped in further improving our paper. Mausam is supported by grants from Google, Bloomberg, IMG and Jai Gupta chair fellowship by II Delhi. Parag Singla is supported by the DARPA Explainable Artificial Intelligence (XAI) Program with number N66001-17-2-4000
450
451
452
453
Both Mausam and Parag Singla are supported by the Visvesvaraya Young Faculty Fellowships by Govt. of India and IBM SUR awards. Any opinions, findings, conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views or official policies, either expressed implied, of the funding agencies.
454
456
457
ETHICS STATEMENT
458
In its current form, our work is primarily technical contribution, with no immediate ethical consequences. Our work develops the line of recent research in which constraint reasoning is carried out through neural architectures. We believe that neural approaches for symbolic reasoning will go a long way in creating an integrated AI system. This is because integrated system requires not only perceptual, but also high-level reasoning. Neural approaches will provide uniform vocabulary so that both these forms of reasoning can interact with each other, improving performance of the overall system.
460
462
464
As AI systems start be used in critical applications such healthcare, law, and disaster management, it is important that they honor the safety and accountability constraints set up by domain experts. Their ability to perform high-level reasoning enables them honor such constraints more effectively. Thus, our line of work, in the long run, could have significant positive ethical implications. We see no obvious negative implications of our work.
486
467
468
469
REPRODUCIBILITY STATEMENT 470
To ensure reproducibility, we have discussed the dataset creation process and provided model architecture details in Section 5.1 and Section 5.2 respectively. We provide the details of the exact
473
hyper-parametery computational resources used, and additional experimental details in the appendix. We also make our code publicly available at
474
sww.pppi---aaa----aaaaeeeee invariance.
475
REFERENCES
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An unsupervised differentiable approach. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019a. URL https
477
479
/ /oopenevveww..o http://wwwwwweeteeeeeeeeeeeeeeee for 1d=
480
Saced Amizadeh, Sergiy Matusevych, and Markus Weimer. PDP: A general neural framework for learning constraint satisfaction solvers. CoRR, abs/1903.01969, 2019b. URL RtLhhtt:: buttp://arxe //arxiv arg/abs. 9033... 01969
482
Dzmitry Bahdanau. Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA May 7-9, 2015, Conference Track Proceedings, 2015. URL htttp://axiv. wwwp:/voorg/abb.....
484
486
0473
487
Aniket Bajpai, Sankalp Garg, and Mausam. Transfer of deep reactive policies for MDP planning. In Advances Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 10988- 10998, 2018
488
489
490
491
Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classification extrapolations. In Proceedings of the 38th International Conference Machine
http://sopprrooopptttggiiit....
10

---

Published as a conference paper at ICLR 2022
Learning, ICML 2021, 24 July 2021, Virtual Event, volume 139, pp. 837- 857, 2021. URL http::/ppoocediing www.mml...sss.e... pttpp/ee//11///vvaaaaaaaaaaa..a httm
494
495
Nuri Cingillioglu and Alessandra Russo. Deeplogic: Towards end-to-end differentiable logical reasoning. In Proceedings of the AAAI 2019 Spring Symposium on Combining Machine Learning with Knowledge Engineering (AAAI-MAKE 2019) Stanford University, Palo Alto, California, USA, March 25-27, 2019., Stanford University, Palo Alto, California, USA, March 25-27, 2019, volume
496
498
2350 of CEUR Workshop Proceedings. CEUR-WS.org 2019. URL http: /eur ws. org/
500
Vol- Vo1-2350/paper22 pdf
Johan de Kleer. A comparison of ATMS and CSP techniques. In Proceedings of the 11th International Joint Conference on Artificial Intelligence. Detroit, MI, USA, August 1989, pp. 290-296, 1989.
502
URL http://ijcai. org /P www.eeoregggggooooooo..o.......e 89 1/ httppaasa/////eeeeeeee 046.. pdf
504
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL
505
506
net. formm?
id BIxy hRctX
508
Michael D. Ernst, Todd D. Millstein, and Daniel S. Weld. Automatic sat-compilation of planning
509
problems. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence.
510
IJCAI 97, Nagoya, Japan, August 23-29, 1997, Volumes, pp. 1169-1177 1177, 1997. URL http:
511
//ijcal wwwgg/roceeeding
97 www.///--/////// Papers 00550055..00 pdf
512
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. J. Artif. Intell. Res., 61:1-64, 2018. doi: 10.16133jairr57144 URL
513
514
5714
515 Nir Friedman, Lise Getoor, Daphne Koller, and Avi Pfeffer. Learning probabilistic relational models. In Proceedings of the Sixteenth International Joint Conference Artificial Intelligence, IJCAI 99, Stockholm, Sweden, July 31- August 6, 1999. 2 Volumes, 1450 pages, pp. 1300-1309, 1999. URL http::/ijcai.ont www.orggggooeeinggg...o.. 199- 100322/Paae 2ttpa//PPPP///eee 090 pdd]
517
518
519
Sankalp Garg, Aniket Bajpai, and Mausam. Symbolic network:
Generalized neural policies for relational mdps. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 3397-3407. PMLR, 2020.
521
522
523
Kazuo Iwama and Shuichi Miyazaki. Sat-variable complexity of hard combinatorial problems. In Proceedings of the World Computer Congress of the IFIP, pp. 253 258, 1994.
525
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry P. Vetrov, and Andrew Gordon Wil- son. Averaging weights leads to wider optima and better generalization. In Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, Cali- forniu, USA, August 6-10, 2018, pp. 876-885, 2018. URL http: / auai hwtgg//aaiii81111 pIoceedingss/pppee///33 pdf
527
529
530
David Joslin and Amitabha Roy. Exploiting symmetries in lifted esps. In The 14th National Conference on Artificial Intelligence (AAAI), pp. 197-202. AAAI Press, 1997.
531
532
Daniel Kahneman. Thinking, fast and slow. Macmillan, 2011.
Nada Lavrac and Lue De Raedt. Inductive logic programming: A survey of european research. Al Commun., 8 -11 1995. doi: 11.223//ACC-1995-811 URL URL/jttpss///b..rq//// B233/AIC-1995-8100
534
536
Robin Manhaeve, Sebastijan Dumancie, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. In Advances in Neu- ral Information Processing Systems 31: Annual Conference on Neural Information Pro- cessing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp.
538
540
3753 7753,3763, 2018 URL URLAttpp::/pprccediii http::::////oeeedddnnn..oo.ppep newriinissiiinnnns.o..e.m......e httpps.cccppeeee http:/cpppppp..///aaaaaaaa

---

Published as a conference paper at ICLR 2022
Mchrab Najafian, Mohammad Hesam Tadayon, and Morteza Esmaeili. Construction of strongly mutually distinct sudoku tables and solid sudoku cubes by cyclotomic cosets. IEEE Transactions on Games, PP:1-1, 11 2018. doi: 10.1109/TG.21182889995
543
545
Yatin Nandwani, Deepanshu Jindal, Mausam, and Parag Singla. Neural learning of one-of-many solutions for combinatorial problems in structured output spaces. In International Conference on Learning Representations (ICLR), 2021.
546
547
548
Rasmus Berg Palm, UIrich Paquet, and Ole Winther. Recurrent relational networks. Advances in
549
Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, 3-8 December 2018, Montréal, Canada, pp. 3372 -3822 2018. URL securrent-relationna networks.
550
http://papers.. nips wccppppp/7599.777
552
Laurent Perron and Vincent Furnon. Or-tools, 2019. URL httpp:::/ddeeeeoprrsss..ggg comm/pptmizztiion
654
Bart Pieters. Generic sudoku solver. http:///////ttta////aatooooo///a
2019.
Tim Rocktäschel, Sameer Singh, and Sebastian Riedel. Injecting logical background knowledge into embeddings for relation extraction. In NAACL HLT 2015, The 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Denver, Colorado, USA, May 31- June 5, 2015, pp. 1119-1129, 2015. URL
556
557
558
559
560
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learning a SAT solver from single-bit supervision, In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL
561
563
net forum? feerummid-iat -idiidddMM HJMC 1A5tm
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value iteration networks. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pp. 4949 4953, 2017.
565
567
Hao Tang, Zhiao Huang, Jiayuan Gu, Bao-Liang Lu, and Hao Su. Towards scale-invariant graph-related problem solving by iterative homogeneous gnns. In NeurlPS, 2020. URL htttps:/ nwwrips...... cc/ppper//2// /hash/
568
589
570
Abstract .hmml
571
Toby Walsh. SAT v CSP. In Principles and Practice of Constraint Programming CP 2000, 6th International Conference, Singapore, September 18-21, 2000, Proceedings, volume 1894 of Lecture Notes in Computer Science, pp. 441 456. Springer, 2000. doi: 10. 10.100773-540-45349-00 URL
572
574
https: oro/oogg///.o /1. 1007 540 45349-0 0 32
Po- Po-Wei Wang, Priya L. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019. Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6555-6554. PMLR, 2019. URL http:://procee ngs r. wrwps/ss///...... / / www.aaaggg...................w 9e.. html
576
578
579
580
Gilad Yehudai, Ethan Fetaya, Eli A. Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks, In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139, pp. 11986, www.pprsssvvvv wat.s///v///yyeeudes 22a html
581
582
583
2021. URL
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: review of methods and applications.
585
AI Open, 1:57-81, 2020.
12

---

Published as a conference paper at ICLR 2022
A
APPENDIX
2 RELATED WORKS
586
589
Generalization of GNNs across graph size: Our work relies heavily on the assumption that GNNs
590
generalize across size. Here we briefly discuss the works that question the same. The existing set of papers (and results) in this line of research can be broadly divided into two sub-classes. The first set of results talk about the representation power of GNNs to handle various graph sizes. The second set of results talk about learnability issues with GNNs under varying train/test distributions. We look at some of the results below and try to explain why GNNs in our case are able to generalize well, both in terms of representation power, as well as learnability.
592
694
585
596
Representation Power: We hypothesize that there are two design choices that are helping us gain good representation power: 1. Ability to create deep network without blowing up the number of parameters because of weight tying across layers, and 2. Preassigned class labels to some of the
597
598
599
variables which act as node features and help in breaking the symmetry. We argue it on the basis of Theorem 4.2 in Yehudai et al. (2021), which proves that there exists a (d + 3) layered GNN that can distinguish between nodes having different local structure, which quantified via d-patterns that
600
601
602
can be thought of as generalization of node degree to d-hop neighborhood. Hence. to be able to distinguish between nodes on the basis of a GNN, all we need to do ensure that different nodes have different d- d-patterns. This can be achieved in 2 ways: 1. By increasing d, e-g. two nodes may have the same degree and hence the same 1- l-pattern, but their neighbors may have different degrees, which will lead to different 2-pattern for these two nodes. 2. By assigning node features, e.g. two nodes may have the same degree, but their neighbors may have different node features, leading to different 1-pattern for them as d- d-pattern also takes initial node features into account. In addition, Tang et al. (2020) also argue that one way of increasing the representation power of GNNs is by increasing their depth, and it achieves the same by proposing IterGNN that applies the same GNN layer for an adaptive number of iterations depending on the input graph. This is equivalent to tying the weights of different layers as RRNs, as well as in our models.
603
604
605
607
609
610
611
612
613
Learnability: With respect to learnability, Yehudai et al. (2021) prove the existence of a 'bad' local minima that overfits on train data but fails on test samples that have unseen d-patterns. Our test dataset clearly has unseen d- d-patterns (e.g. nodes in 16 16 sudoku have different degrees than nodes in x sudoku), but our models still generalize. We note that Yehudai et al. (202T) only talks about the existence of some bad local minima, but does not rule out the possibility of the existence of other good local minima, which could generalize well, despite differences in local structure between train and test sets. This goes into the whole learnability argument, and whether we can find such not-so-bad local minimas (which presumably exist since the possibility has not been ruled out). One aspect that possibly comes to our rescue is that, unlike most GNN architectures, our design is recurrent in nature, ie., parameters are tied across different GNN layers as inspired by Palm et al. (2018). Parameter tying assumption, possibly helps us in learnability, since the recurrence can be seen form of regularization, avoiding overfitting (or getting stuck in bad local minima). Exploring this further is a direction for future work.
614
615
616
617
618
619
620
622
623
624
625
626
In addition to Yehudai et al. 20221. Bevilacqua et al. (202)) deal with varying train/test distributions by proposing size invariant representation of graphs. Their approach focuses on graph classification tasks, and is limited to creating size invariant representations for the entire graph. The theoretical claims presented in their paper primarily focus on the limitation of standard GNN based formulations
627
628
629
630
for generalizing across sizes for graph classification tasks. On the other hand, we are interested in learning representations for each node in the graph for node classification, and it not clear how the
631
claims, as well as techniques proposed in the paper, extend to our setting.
4 MODELS DESCRIPTION
634
4. 1 BINARIZED MODEL
Recurrent Message Passing
Constraint Edges and Relation 637 Edges. Each edge inherits edge type, either from Constraint Graph, Relation Graph. We denote
636 There are two categories of edges in the Message Passing Graph:
13

---

Published as a conference paper at ICLR 2022
the set of all constraint edge types as Q. and the set of all relational edge types R. We now describe the details of message passing and hidden state update equations.
639
Edge Dependent Message Passing: The nodes communicate their current hidden state via the messages sent to their neighbouring nodes across the edges. The message depends not only on the current state of the sender and receiver, but also the edge rype across which the mes- sage is sent. Specifically, for each edge type, 2, there is a separate message passing func- tion, Sa. with 2 E (Q U R) where Q and R are the set of all constraint edge types and re- lation edge types respectively. We compute the message for each edge Jah)) E E as:
641
643
644
645
646
mh (. = J= (h, (15).)) he (Mia.))) Ve Jola) E E, 2 E (QUR).
647
Hidden State Update: For each node, the incoming messages on the edges of the same type are aggregated by taking their weighted average. The weights, de are computed using Bahdanau Attention (Bahdanau et al. 2015) over constraint edges, whereas messages across relation edges are
648
650
simply averaged: m4, Rj.
LE 324)) E2 at (elei (ot) Jaba) Vz E (QUR)
651
Finally, all messages, m4, m VVz E (Q (QUIQ Rt), are concatenated to create the input, my my[ri,.]] for each node, 7j.1- The hidden state at step is updated by the following state update function to generate the state h (ms,.): h4t1 (7j.1) = g (he (ng,a), my [mj.]], uo (ng.)))) Vnn. E N. See Figure for an illustration of edge dependent message passing and state update given step
652
653
654
4.2 MULTI- VALUED MODEL
There are two separate message passing graphs in multi-valued model: RMPG and CMPG. RMPG contains edges encoding the relationship between the values. Each edge has an associated edge type representing the relationship it encodes. We denote the set of all edge types in RMPG R. In CMPG, there are two categories of edges: Constraini Edges and Assignment Edges. Further, each edge may have an associated edge type. The set of all constraint edge types is denoted as Q, and the set of assignment edge types (edges from orange value nodes to yellow variable nodes in fig. is
657
659
660
681
682
denoted as A. Finally, the initial embedding of a variable node nj denoted as un (nz).
683
We now describe the message passing rules and hidden state update equations.
664
Recurrent Message Passing RMPG)
Message Passing Update: At step update the hidden state, hef)), of each of the value nodes in
G. by the concatenation, my m.[ of average messages, m mf] received across edges of type r R: - (p)) = (xf)) m [+t], ū [[[x(1]]). where ğ is the hidden state update function. Like (Palm al. 2018), it always takes the initial embedding, ū x [1], of the value node ño as one of the inputs.
686
667
668
Notice that the message, m [n is the average of the messages, (h, (ep)) Y Vii E É,
689
670
where fr is the message passing function for edge type r E R. The hidden states are updated for
T steps and the final embeddings, (np) Yoj V. are used as 'relationship-aveer awarre embeddings
671
672
for initializing the input features (embeddings) of both variable nodes, nj. and value nodes, n² in G
673
(orange and yellow nodes respectively in Multi-Valued Graph in fig.
674
Recurrent Message Passing on CMPG)
675
Message Passing Update: At step f, similar to binarized model, each variable node receives messages from its neighbors, that are aggregated based on the edge type. For each node, the aggregated messages, My [ry]. for different edge types, z E (Q U A), are stacked to create, m/(rg), which updates the hidden state as: h (nz) = y (he())), m. [rj], mo(g)) Vng E N.
676
677
879
681 Discussion on an alternate Encoding Scheme
As discussed in section 4.1 the main intuition for our binarized modelcomes from 'sparse encoding' 683 of an integer CSP to a SAT. In addition to 'sparse encoding'. there is another way of converting integer CSP into SAT, called "compact encoding' (Ernst et al.) 1997; Iwama & Miyazaki| 1994), in which each Boolean SAT variable represents a single bit of the integer value that a CSP variable can take. The final assignment of CSP variable is given by the integer represented by the log k Boolean
685
686
14

---

Published as a conference paper at ICLR 2022
Q = {q}
Concatenation:
=
R = (1}
Aggregation:
h((b)
g
uo(b)
mt-1(b]
m(t-1,q)(b]
m(t-1,r)lb]
m(t-1)le9abl
((t-1)(e9cbl
m (tt-))e'adl abl
m(t-1)le<cb)
q
((--1)
((-1)(())h
h(t-1)(a)
h(t-1)(b)
h(t-1)(c)
hn-1((a)
h((a)
h(-1)(b)
b
h₂(b)
he-1/(c)
hy(c)
Figure 3: Hidden State Update at time-step t: We take a toy graph with nodes, {a, b, c), and edge-types, {q,r), to illustrate edge-dependen message passing and hidden state update of node b. First, messages along the four edges are calculated as an edge-type dependent function of the sender and receiver hidden state using J and fr. Next, the incoming messages aggregated by edge-type (e.g., using attention based mechanism or simple averaging), and the outputs are concatenated to obtain the final message, [b)1 The hidden state of node is updated by function g which takes the previous hidden state h² h--1(b) (b), the incoming message m4-1 [b), and the initial embedding of the node as input.
(b).
15

---

Published as a conference paper at ICLR 2022
SAT variables corresponding to that variable. Motivated by the "compact encoding', one can construct another model: instead of a one-hot encoding which requires k nodes (one for each value in V) for each variable, create log k binary valued nodes for each variable and assign a value
688
V to the variable based on the integer represented by log l bits corresponding to it. This results in graph with Ne log & nodes for CSP with Ncl variables and k classes, instead of |Nc lk nodes in the binarized model, and brings it closer to the graph size of NNc + k created in multi-valued model. However, such an approach failed to generalize across the size of the value-set in our experiments. In addition, such an encoding has a limitation in its representational capability. It can not encode the relationship between the values effectively. For example, in & x k Futoshiki, we have an ordinal relationship between the k values representing the numerical numbers 1 to k. In our proposed approaches, we encode this by adding appropriate relational edges between nodes representing different values in V. In the binarized model, it is done for each variable separately, whereas, in the multi-valued model, it
680
892
693
694
695
697
is done in the RMPG. In absence of an explicit node for a value in this encoding scheme, it is not 699
clear how to represent such a relationship.
701
EXPERIMENTS
702
Discussion on comparison with SAT Solvers: In this work, we are interested in creating (and learning) neural solver for symbolic tasks, instead of using symbolic algorithm like SAT solver. Such an approach has many benefits, e.g. because of being differentiable, it can be used seamlessly in unified framework requiring both perception as well reasoning, e.g. visual sudoku; neural models have been shown to be resistant to varying amount of noise in the data as well, which purely logical (SAT style) solvers may not be able handle. As the case with other papers in this line of
704
705
708
707
708
work e.g (Selsam et al. 2019, Amizadeh et al. 2019a), at this point our main motivation is scientific.
709
We are interested in understanding to what extent neural reasoners can generalize across varying sizes of the value-set in train and test domains. Instead of comparing with an industrial SAT Solver, perhaps a fair comparison would be with generic sfae-off-the-ar neural SAT solver e.g., CircuitS AT AAmizadeh et al. 2019a), NeuroSAT (Selsam et al. 2019). Both of these papers observe that there is long way to go before they can compete with industrial SAT solvers. In fact, both of these approaches experiment with much smaller problem instances. CircuitSAT uses model trained on k- k-SAT-3-10 problems (k-SAT with 3 to 10 Boolean variables) for coloring graphs with number of nodes ranging between 6 to 10, and achieves meager 27% performance and NeuroSAT fails solve any of the problems in the coloring dataset used by CircuitSAT (section 5.2 in Amizadeh et al. (2019)). On the other hand, the smallest of the problems in our dataset has 40 nodes (GCP) and the largest has
710
711
712
713
715
717
718
(= 25, 625) nodes (in 25 x 25 Sudoku), and hence we do not expect the generic neural SAT
719
720
solvers scale up to our problem sizes.
Table 5: Dataset details
Train Mask (%)
Test
Task
A(Vars.)
#MMissing Vars.)
K'
#(aass))
Mask
#iMissing Vars.)
Pütoshiki
36
28-70
10-25
16.18.9.10.111122
36-144
28-10
10-93
GCP
40-100
28-70
12-70
[4.5.6.7]
40-150
28-70
12-105
Sudoku
81
58-79
47-64
(9.10,12.15.16]
81-256
30-68
47-148
Sudoku finetune
24
576
30-70
173-403
(15.16.24.25)
225-625
30-70
68-314
721
5.1 TASK DESCRIPTION AND DATASETS
722
We experiment on datasets generated from Lifted CSPs of three different puzzles, viz.. Sudoku, Futoshiki, and Graph Coloring. In addition, we fine-tune our multi-valued model for Sudoku on 8000 puzzles of size 24 and test it on puzzles of different board sizes. SableeScontain the details of both train and test data for the different experiments. Below we describe the three tasks and their datasets in detail.
724
726
We train our model on 6 x 6 puzzles, with the percentage of missing cells varying uniformly between 28- - 70%. We test our models on puzzles with board size ranging between 6 x 6 to 12 x 12, with the same percentage of missing cells. The number of ordering constraints is twice the board size. To generate data, we first randomly generate a completely filled k x & board and then randomly mask m% of the cells. We search for its all possible completions using backtracking to
Futoshiki:
728
730
16

---

Published as a conference paper at ICLR 2022
Table 6: Test Data statistics for all three tasks
k #Puzzles
#(Variables)
#(Missing Variables)
Mask (%)
Futoshiki
4100
36
10-25
28-70
7 4091
49
14-34
29-70
3578
64
19-44
30-70
9
3044
81
24-56
30-70
2545
100
30-66
30-66
11
2203
121
36-82
30-68
12
1882
144
43-93
30-65
GCP
4
9102
40-150
12-105
28-70
9102
40-150
12-105
28-70
6
6642
40-120
12-84
28-70
7
3362
40-80
12-56
28-70
Sudoku
9
18000
81
47-64
58-79
2317
100
30-62
30-62
12
1983
144
43-84
30-58
15
1807
225
67-128
30-57
16
1748
256
76- 148
30-58
1000
576
172-289
30-50
25
1000
625
187-314
30-50
732
ensure that has only one solution. Finally, we insert ordering constraints between 2k randomly picked pairs of adjacent cells. The entire process is repeated by varying k and m generate both the test and train dataset.
734
The training data consists of 12, 300 puzzles on 6 6 board size with the percentage of missing variables varying between 28 - 70%. The exact details the testing data for different board sizes provided in Table We note that it becomes increasingly difficult to find puzzles with unique solution as the board size increases. Therefore, we are forced to reduce the maximum percentage of masked (unassigned) cells with increasing board size.
736
738
739
740
GCP: The training data for Graph Coloring Problem consists of around 25 thousand 4-colorable graphs with graph order varying uniformly between 40 120, and the percentage of unassigned (masked) variables varying uniformly between 28 70% depending on the graph order. The exact
741
742
743
details of the testing data for different chromatic number (value-set size) are provided in Table o To create non-trivial problems for the dataset, we always attempt to color graphs with the smallest possible number of colors, i.e., the chromatic number of the graph. We follow Erdós Rényi (ER) model to generate random graphs. It takes number of nodes, and edge probability, p, as input, and adds an edge independent of the other edges with probability p. We note that to sample graph with nodes and given chromatic number k need to carefully adjust the range from which edge probability is sampled. The exact range from which p is sampled uniformly for each chromatic number i and range of nodes is given in Table We use CSP solver (Perron & Furnon (019)) to determine the chromatic number of a given graph, which becomes a bottleneck while generating not able generate graphs with more
744
745
747
749
751
graphs with higher chromatic number. As result, than 80 nodes for chromatic number 7, in reasonable amount of time.
753
Sudoku:
The training data consists of 10 thousand 9 9 puzzles randomly selected from the dataset introduced in (Palm et al. 2018). For standard 9 x 9 board, we use the same test data as used in RRN PPlm et al., 2018) The data for the board-sizes between 10 and 16 is generated using the methodology similar to Futoshiki. Instead of backtracking, solution validity and uniqueness is checked through the GSS library (Pieters 2019). The exact details of the testing data for different board sizes are provided in Table 6] For the experiment where we fine-tune our models on 24 x 24 puzzles, both the train and test data for board size 24 and 25 are generated following the methodology
755
756
757
758
780
Available
17

---

Published as a conference paper at ICLR 2022
Table Range for p for given k and n for GCP data generation
40-55
56-70
71-80
81-100
101-130
131-150
(.21.
(0.05, 0.1)
(0.05, 0.1)
(0.05, 0.1)
(0.02, 0.05)
(0.02, 0.03)
(0.2, 0.25)
(..)
(0.1,
(0.075, 0.12)
(0.075, 0.1)
(0.05, 0.075)
(0.2, 0.25)
(0.15, 0.25)
(0.17, 0.2)
(0.15, 0.18)
(0.12,
7
(0.325, 0.375)
(0.275, 0.325)
(0.22, 0.3)
761
similar to Futoshiki. In this setup, we were not able to verify the uniqueness of solution through GSS library as it doesn't it scale to such large sizes.
762
783
Solution Multiplicity in GCP Dataset and larger board-size puzzles of Sudoku: An input query in GCP may have more than one solution, out of which only one is given at train time. But the network may discover new valid solution, and computing loss of the discovered solution w.r.t. the
765
766
given solution may unnecessarily penalize the model. To avoid this, we algorithmically verify if prediction is a valid coloring or not, and compute loss w.r.t. to this discovered solution, instead of the
767
given one. This is equivalent to solving One-of-Many Learning problem (Nandwani et al. 2021 with all possible colorings given at training time. The same phenomenon of solution multiplicity exists for Sudoku puzzles of size 24 and 25, as verifying the uniqueness of puzzles such large board-size became computationally infeasible.
789
771
772
5.2 EXPERIMENTAL SETUP AND BASELINES
773
We report two metries: board accuracy and point-wise accuracy for our experiments. In the former, we consider output of the model correct only if it satisfies the underlying CSP, whereas in the later, we give partial credit even for assigning some of the variables correctly. We formally define it below:
Evaluation Metries:
775
777
Pointwise accuracy: Let Yx be the set of possible solutions for an input x with & variables, and let ý be the model's prediction. Pointwise accuracy of the prediction ý with respect to the solution Yx. denoted as, Foint,Accly,. y), is defined to be the fraction of variables that match between the y and = Σ 1 [y y [i]). where 1 {-} is the indicator function.
779
y: Point,Accyy:
781
Given above, we define pointwise accuracy for prediction ý of an input x with respect to a solution set Yx to be the maximum among the pointwise accuracy with respect to each of the solutions in the set Yx. Mathematically, PointAAc((Y::3 = mazyey, Poointtcccyy..... )).
782
785
For Sudoku and Futoshiki, since there is unique solution, we can easily compute pointwise accuracy as the target set Yx is singleton. For the GCP task, whenever the model returns a valid coloring, pointwise accuracy is 1, otherwise. in the absence of access to complete Yx, report a lower bound by performing a local search, using Google's s OR- Tools for a valid coloring closest to the model prediction. Same is true for sudoku puzzles 24 and 25 board size.
785
787
789
Why care about point-wise accuracy? In our settings, the generalization problem can be hard, especially when there is large difference between the sizes of the value-sets for the train and test domains. Given that we are defining a novel task, and it is important to measure progress even when problems are hard, we compare the models using simpler metric (pointwise accuracy) well, in addition to board accuracy. This additional metric can help us detect progress, and also compare the relative performance of underlying models.
781
782
793
794
785
Computational resources: All models are trained on K40 GPUs with 12 GB memory, available on an HPC cluster.
796
797
Hyp Hyperparameters: The list below enumerates the various hyperparameters with a brief description and the values chosen.
798
799
Batch Size: For each task, we selected the maximum batch size that can be accommodated in 12GB GPU memory. Refer to Table for details.
800
18

---

Published as a conference paper at ICLR 2022
Table 8: Hyperparameters for different models and tasks
Orthogonality Loss Factor
Edge Dropout
Model
Batch Size
Weight Decay
Futoshíki
MV
64
0.0001
0.01
0.1
BIN
16
0.0001
0.1
NLM15
0.0001
NLM30
2
0.0001
GCP
MV
64
0.0001
0.01
0.1
BIN
16
0,0001
0.1
NLM24
1
0.0001
Sudoku
MV BIN
28
0,0001
0.01
0.1
3
0.0001
0.1
Table 9: Training cost of different models in terms of number of epochs, gradient updates and clock time
Batch Size
Training Data Size
# Gradient Updates
Time per Epoch (min)
Total Time (Hours)
Model
#Epochs
Futoshiki
MV
12,300
60,000
312
25
BIN
12,300
37,500
49
21
NLM15
12,300
155,000
50
34
43
NLM30
12,300
232,500
38
87
66
GCP
MV
64
25,010
80,000
205
10
33
BIN
16
25,010
40,000
26
39
17
NLM24
25,010
260,000
10
213
37
Sudoku
MV BIN
28
10,000
162,000
454
68
10,000
168,000
50
74
63
801
2. Optimizer: To minimize the loss, we use Adam optimizer with learning rate 0.0002. As in the original RRN paper, we chose a weight decay factor of 1E-4.
803
3. Orthogonality Loss Factor: To ensure that the multi-valued model learns different em- beddings for each value in the value-set, add auxiliary loss term, corresponding to the total pairwise dot product of any two embeddings, before and after message passing on the Relation Message Passing Graph (RMPG), G. Its weight, a, was chosen amongst (0.01, 0.1, 0.5) by cross validating devset for Futoshiki, and then fixed afterwards for all our experiments.
805
806
808
809
4. Edge Dropout:
While collating the messages from the edges of the same type, we drop 10% of the messages, done in RRN. Dropout is used in the Message Passing Graph (MPG) of the binarized model, and the Constraint Message Passing Graph (CMPG) of the multi-valued model.
811
Model Averaging: As suggested in (Izmailov et al. 2018). to reduce the variance of model performance, we take simple average model weights stored at multiple points. All checkpoints beyond point when the learning curve flattened are selected for computing the average.
814
816
Training Time: Table Pable?eenu enumerates the exact training cost, in terms of total training epochs, number of gradient updates, and clock time, for all three tasks and for both models well as the baseline
19

---

Published as a conference paper at ICLR 2022
NLM model. Note that while multi-valued model may have fewer parameters, and results in much smaller graph and inference time for a given problem, its training time could still be higher, especially in terms of total training epochs and number of gradient updates. However, because of its memory efficiency, we can keep a much larger batch size during training, and because of its speed efficiency, each update is much faster. As result, the overall clock time comes out to be comparable
819
821
823
to the binary model for the two of our tasks, i.c. Futoshiki and Sudoku, and it is within 2x for GCP,
even though the number of epochs much higher.
20


Reviews:
[{"review_id": "lRnsBLlfZI", "reviewer": "Reviewer_FY1P", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n1. 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.\n2. 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). \n3. The training method of the multi-valued method is elegant. \n\nCons:\n\n1. 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). \n2. 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.\n\nMinors:\n\n1. For generating the Sudoku larger than 9. It would be better if you make sure all the data are permutation invariant.", "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. \n\nBased on RRN, the authors propose two methods: The binarized method and the Multi-value method. \n\nFor the binarized method: the output value space is binarized, i.e., the model will score each candidate individually and the parameters are shared.\n\nFor 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. \n\n", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WDYlKDC2aVd", "reviewer": "Reviewer_XpUt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n**Strengths:**\n- An interesting problem that was not studied before\n- The suggested ways of encoding the values in the graph make sense and are elegant.\n- Empirical results seem good \n\n**Weaknesses**\n\n- 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. \n- 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.\n- 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. \n\n\n", "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. \nThe 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. \nIn the final section, the authors present results on 4 different combinatorial puzzles, where their method is shown to outperform a generic neural reasoner.\n", "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. \n  \n**More comments**\n- Intro: define CSP CNF  constraint graph\n- figure 1 - add more details about the problems, constraints, and representation. Currently, it is difficult to understand.  \n- 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? \n- Description of networks and message passing: too dense. Difficult to read. Visualization must be added.\n\n\n**Post rebuttal:**\nI 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. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SwTLKHPy_Kn", "reviewer": "Reviewer_VvZR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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).\nOther 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).\nOn 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?\n\n", "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.\n", "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).\nFurther, the results of the algorithm are not particularly impressive, if we consider \"board accuracy\" (pointwise accuracy feels like the wrong metric for combinatorial problems). \nOn the pro side, this paper does address a problem that I've not seen tackled before and that seems to be important. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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)