# 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.iitd.ac.in

ABSTRACT

1 Recently many neural models have been proposed to solve combinatorial puzzles

2 by implicitly learning underlying constraints using their solved instances, such

3 as sudoku or graph coloring (GCP). One drawback of the proposed architectures,

4 which are often based on Graph Neural Networks (GNN) (Zhou et al., 2020), is

5 that they cannot generalize across the size of the output space from which variables

6 are assigned a value, for example, set of colors in a GCP, or board-size in sudoku.

7 We call the output space for the variables as ‘value-set’. While many works have

8 demonstrated generalization of GNNs across graph size, there has been no study

9 on how to design a GNN for achieving value-set invariance for problems that

10 come from the same domain. For example, learning to solve 16 × 16 sudoku after

11 being trained on only 9 × 9 sudokus, or coloring a 7 colorable graph after training

12 on 4 colorable graphs. In this work, we propose novel methods to extend GNN

13 based architectures to achieve value-set invariance. Specifically, our model builds

14 on recently proposed Recurrent Relational Networks (RRN) (Palm et al., 2018).

15 Our first approach exploits the graph-size invariance of GNNs by converting a

16 multi-class node classification problem into a binary node classification problem.

17 Our second approach works directly with multiple classes by adding multiple

18 nodes corresponding to the values in the value-set, and then connecting variable

19 nodes to value nodes depending on the problem initialization. Our experimental

20 evaluation on three different combinatorial problems demonstrates that both our

21 models perform well on our novel problem, compared to a generic neural reasoner.

22 Between two of our models, we observe an inherent trade-off: while the binarized

23 model gives better performance when trained on smaller value-sets, multi-valued

24 model is much more memory efficient, resulting in improved performance when

25 trained on larger value-sets, where binarized model fails to train.


26 1 INTRODUCTION

27 The capability of neural models to perform symbolic reasoning is often seen as a 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 et al., 2019; Amizadeh et al., 2019a;b), neural theorem proving

32 (Rocktäschel et al., 2015), differentiable ILP (∂ILP) (Evans & Grefenstette, 2018), playing blocks

33 world (Dong et al., 2019), solving sudoku (Wang et al., 2019). Our work follows this literature for

34 solving combinatorial puzzles – in particular, the methods that implicitly incorporate the rules in their

35 weights by training over some of its solved instances, e.g. Recurrent Relational Networks (RRN)

36 (Palm et al., 2018). Such models assume a fixed value-set, i.e., the set from which variables are

37 assigned values is assumed to be constant during training and testing. This is a significant limitation,

38 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). It is also a desirable

40 goal since as humans, we often find it natural to generalize to problems of unseen variable and value

41 sizes, once we know how to solve similar problems of a different size, e.g., we may solve a 12 × 12


_∗Equal contribution. Work done while at IIT Delhi. Current email: vidit.jain@alumni.iitd.ac.in_


-----

42 sudoku after learning to solve a 9 × 9 sudoku. We note that graph based models have been shown to

43 generalize well on varying graph sizes, e.g., finding a satisfying solution of a CNF encoding of a CSP

44 with 100 Boolean-variables, after training on CNF encodings of CSPs with only 40 Boolean-variables

45 (Selsam et al., 2019). However, the model trained using CNF encoding of Boolean-CSPs cannot be

46 used directly for a non-Boolean CSP in which variables take value from a different (larger) value-set.

47 In response, we study value-set invariance in combinatorial puzzles from the same domain. To

48 formally define a similar puzzle with variables taking values from a different value-set, we make use

49 of Lifted CSP (Joslin & Roy, 1997), a (finite) first-order representation that can be ground to CSPs of

50 varying variable and value-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

52 to the constraints of the CSP, and thus neural SAT solvers like NeuroSAT (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

56 the same lifted CSP, but with a different value-set of size k[′] (typically k[′] _> k)? An example task_

57 includes training a model using data of 9 × 9 Sudoku, but testing on a 12 × 12 or a 16 × 16 Sudoku.

58 We build our solution using RRNs as the base architecture. They run GNN on the constraint graph,

59 and employ iterative message passing in a recurrent fashion – the nodes (variables) are then decoded

60 to obtain a solution. We present two ways to enhance RRNs for value-set invariance.

61 _Binarized Model: Our first model converts a multi-class classification problem into a binary classifi-_

62 cation problem by converting a multi-valued variable into multiple Boolean variables, one for each

63 value in the value-set. The binarized constraint graph gets defined as: if there is an edge between two

64 variables in original constraint graph, there are k edges between Boolean nodes corresponding to

65 the same value and the same two variables in the new graph. In addition, all k Boolean variables,

66 corresponding to a multi-valued variable, are connected with each other. This model naturally

67 achieves value-set invariance. At test time, a larger value-set just results in a larger graph size. All

68 GNN weights are tied, and because all the variables in the binarized model are Boolean, embeddings

69 for binary values ‘0’ and ‘1’, trained at training time, are directly applicable at test time.

70 _Multi-valued Model: Our second model directly operates on the given multi-valued variables and the_

71 corresponding constraint graph, but introduces a value node for every value in the value-set. Each

72 pre-assigned (unassigned) variable node is connected to that (respectively, every possible) value node.

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

76 elements across instances. During test time, k[′] of the learned embeddings are used.

77 We perform extensive experimental evaluation on puzzles generated from three different structured

78 CSPs: Graph Coloring (GCP), Futoshiki, and Sudoku. We compare two of our models with an

79 NLM (Dong et al., 2019) baseline – a generic neural reasoner, which either fails to scale or performs

80 significantly worse for most test sizes used in our experiments. We also compare our two models

81 along the axes of performance and scalability and discuss their strengths and weaknesses.

82 2 RELATED WORK


83 This paper belongs to the broad research area of neural reasoning models, in which neural models

84 learn to solve pure reasoning tasks in a data-driven fashion. Some example tasks include theorem

85 proving (Rocktäschel et al., 2015; Evans & Grefenstette, 2018), logical reasoning (Cingillioglu &

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; Bajpai et al., 2018), and our focus

88 – 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

90 for problems where the CSP constraints or SAT clauses are explicitly provided to the model. For

91 example, NeuroSAT (Selsam et al., 2019) and PDP (Amizadeh et al., 2019b) assume that the CSP

92 is expressed in a Conjunctive (or Disjunctive) Normal Form. Similarly, Circuit-SAT (Amizadeh

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 DeepProbLog (Manhaeve et al., 2018),


-----

95 and DeepLogic (Cingillioglu & Russo, 2019), which require human designed rules for reasoning. Our

96 work belongs to the second thread where the constraints or clauses are not provided explicitly, and

97 only some underlying structure (e.g., Sudoku grid cell connectivity) is given along with training data.

98 The intention is that the model not only learns to reason for the task, but also needs to learn the implicit

99 semantics of each constraint. SATNET (Wang et al., 2019) falls in this category – it formulates a

100 learnable low-rank Semi-definite Program (SDP) relaxation for a given MAXSAT problem trained

101 via solved SAT problems. Similarly, Recurrent Relational Networks (RRN) (Palm et al., 2018) use

102 recurrent message passing graph neural network to embed the variables of the unknown CSP, and the

103 relationship between them, in a latent vector space and finally assign a value to each variable based

104 on its embedding. Both these works assume a fixed number of variables that remains unchanged

105 across training and test. While we build on RRNs, we substantially extend the formalism to study

106 value-set invariance. Formally, our work can be seen as solving a (finite) first-order formulation of the

107 CSP, called Lifted CSP (Joslin & Roy, 1997), which can be grounded to CSPs with varying number

108 of variables and values. To our knowledge, there is relatively limited prior work on neural models

109 that can generalize to variable-sized instances of an underlying first order reasoning task – one related

110 approach builds neural models for First-order MDPs (Garg et al., 2020).

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). Evans &

113 Grefenstette (2018) propose differentiable neural relaxation of ILP (∂ILP). Neural Logic Machines

114 (NLM) (Dong et al., 2019) is another framework that learns lifted rules, shown to be more scalable

115 than ∂ILP. It allows learning of first-order logic rules expressed as Horn Clauses over a set of

116 predicates. Learning of first-order rules makes NLM amenable to transfer over different CSP sizes

117 (Nandwani et al., 2021), and are thus directly comparable to our work. The main challenge of such

118 approaches is that they fail to scale to the size of the problems considered in this work. In our

119 experiments, we compare our methods against both deep and shallow versions of NLM. Note that our

120 work relies on the assumption that GNNs generalize across graph sizes. Yehudai et al. (2021) study

121 the scenarios under which this assumption may not hold. We discuss the details in the appendix.

122 3 PRELIMINARIES AND PROBLEM DEFINITION


123 A combinatorial puzzle can be thought of as a grounded CSP and to formally define a puzzle from

124 the same domain but a larger value-set, we resort to the notion of ‘Lifted CSPs’ that represent an

125 abstraction over multiple ground CSPs of the same type. A lifted CSP does not include a specific

126 set of variables and values; instead, it operates in terms of variable and value references that can

127 be instantiated with all ground variables and values in a ground CSP. This makes them amenable

128 to instantiate CSPs or puzzles with varying number of variables as well as values. We define a

129 Lifted CSP LC as a three tuple ⟨P, R, C⟩. P is a set of predicates: a predicate p ∈P represents

130 a Boolean function from the set of its arguments, which are variable references. Similarly, R is

131 a set of relations over value space – a r ∈R reprents a Boolean function over arguments that

132 are value references. A predicate (or a relation) with its arguments is called an atom. C is a set

133 of lifted constraints, constructed by applying logical operators to atoms – they are interpreted as

134 universally quantified over all instantiations of variable and value references. Finally, Lifted CSP

135 uses a special unary function Value, whose argument is a variable reference and evaluates to a value

136 reference. As an example, a lifted CSP for Sudoku may have a P ={Nbr} for whether two cells are

137 in same row, column or box, R = {Neq}, representing two values are unequal, and a lifted constraint:

138 `Nbr(c1, c2)` `Neq(Value(c1), Value(c2)).`
_→_

139 A lifted CSP LC yields a ground CSP C, given a set of variables O, and a set of values V, and a

140 complete instantiation of all predicates and relations over this set (e.g., in Sudoku, the number of

141 cells, possible values, and which cells are neighbors and which are not). The ground constraints are

142 constructed by instantiating lifted constraints over all variables and values. A (satisfying) solution, y,

143 of a CSP refers to a complete specification of Value: O →V function, such that all the constraints

144 are satisfied. We are often given a partial (satisfying) solution, x – an assignment of values to a subset

145 of variables _O ⊆O[˜]_ and the goal is to output y, such that y agrees with x for the subset _O[˜]._

146 Given a ground CSP C, the Constraint Graph, GC = (NC, EC), is constructed by having each

147 variable in the CSP represent a node in the graph and introducing an edge between two nodes n[C]1 _[, n]2[C]_

148 iff the corresponding variables appear together in some constraint. The edges in the constraint graph


-----

149 are typed based on the identity of the lifted constraint from which it comes. Note that there could

150 be multiple edges between nodes n[C]1 _[, n]2[C]_ [in][ G][C][, if these nodes appear together in more than one]

151 constraint. We embed the knowledge about relations between values in V in the form of another

152 graph, called Relation Graph, GR = (NR, ER), where there is a node for every value in the set V,

153 and there is a (directed) edge between nodes corresponding to vl, vl[′] [depending on whether][ r][(][v][l][, v][l][′] [)]

154 is true or not, for every r . Similar to GC, this graph can also have multi-edges between two
_∈R_

155 pairs of nodes, if more than one relationship holds between the corresponding values.

156 **Problem Definition: To achieve value-set invariance, our goal is to train a model MΘ on training**

157 data from an unknown ground CSP C (with variables O and value-set V) obtained from an unknown

158 lifted CSP _C, and test it on an arbitrary ground CSP C_ _[′]_ from the same lifted CSP (with variables
_L_

159160 _O{(([′]_ **xand value-set[i], GCi), y[i])} Vi[M]=1[′]), where[, along with a relationship graph] |V| ̸= |V** _[′]|. Formally, we are given training data[ G][R][ encoding relations between values in the] D as a set of tuples_

161 value-set V. Here, i[th] instance denotes a partial and corresponding complete solution for C **[i]. We note**

162 that explicit form of the constraints in C **[i]** or LC are not available, only the graphs are given to the

163 model. Our goal is to learn model MΘ, such that given graphs GC′ and GR′, and a partial solution

164 **x[′]** (for CSP C _[′]) : MΘ(x[′]) = y[′], only if y[′]_ is a corresponding complete solution for x[′]. Note that in

165 one of our models, we will additionally assume that max, denoted as kmax, is known to us at
_|V_ _[′]|_

166 training time, which we argue is a benign assumption for most practical applications.

167 4 MODELS DESCRIPTION


168 We propose two models for value-set invariance: the

169 _Binarized Model, and the Multi-valued Model. In_

170 each case, we assume the training data is provided in

171 the form D = ({(x[i], GCi ), y[i]}i[M]=1[, G][R][)][ as described]

172 in Section 3. Let V and V _[′]_ denote the value-sets at

173 train and test time, with cardinality k, k[′], respectively.

174 For each model, we first present a high level intu
175 ition, followed by description of: (a) Construction of

176 Message Passing Graph (b) Message Passing Rules

177 (c) Loss Computation, and finally (d) Prediction on

178 a problem with larger value-set.

179 4.1 BINARIZED MODEL


Figure 1: An example Futoshiki Puzzle of
size 3 × 3 and the corresponding graphs. A
value of −1 indicates an unassigned variable. Black and red edges are Constraint
and Relation edges respectively. The digits
5, 7, 1 in square boxes represent a random 3permutation of kmax, used in multi-valued
model for initialization of node embeddings.


180 Intuition behind our Binarized Model comes directly able. Black and red edges are Constraint −

181 from the ‘sparse encoding’ of a discrete CSP into a and Relation edges respectively. The digits

182 SAT formula (de Kleer, 1989; Walsh, 2000), in which 5, 7, 1 in square boxes represent a random 3
183 assignment of a value v to any variable x[j] permutation of kmax, used in multi-valued
_∈V_ _∈_

184 _O is encoded by a Boolean variable that represents_ model for initialization of node embeddings.

185 **x[j] == v. Such an encoding converts a single multi-**

186 valued variable into multiple Boolean valued variables.[1] We convert a Constraint Graph (fig. 1)

187 with nodes representing multi-valued variables (yellow nodes), into a Binary Graph (fig. 1) with

188 Boolean nodes (blue nodes). This creates a _NC_ _k grid of Boolean nodes, with a row representing_
_|_ _| ×_

189 a variable, a column representing a value and a grid cell (a Boolean node) representing assignment of

190 a particular value to a particular variable. Such a graph can easily represent relationship between the

191 values as well (horizontal red edges), thereby encapsulating the information present in the Relation

192 Graph (fig. 1). We use this Binary Graph for message passing.

193 **Construction of Message Passing Graph: We denote the Message Passing Graph (MPG) by**

194 _G = (N, E) with the set of nodes N and set of edges E, constructed as follows: Nodes: For each_

195 node n[C]j

196197 denoted asof edges in[∈] n G[N]j,[C]1. The first category of edges are directly inherited from the edges of the constraint, n[ in the Constraint Graph (fig. 1, yellow nodes), we construct]j,2 · · · nj,k in N (blue nodes in Binary Graph). Edges: We construct two categories[ k][ binary valued nodes,]

198 graph GC (black vertical edges), with k copies created due to binarization. Edge type is same as in

199 the original constraint graph and is denoted by q. Formally, for every edge, e[C] (j,j′) _EC, where_
_∈_

1There is an alternative encoding scheme called ‘compact encoding’. It is discussed in the appendix


-----

200 _e[C]_ (j,j′).type = q, we introduce k edges denoted as e[q](jl,j[′]l)[, i.e., there is an edge between every pair]

201 of nodes, nj,l and nj′,l, 1 ≤ **l ≤** _k. We refer to them as Constraint Edges. The second category of_

202 edges encode the information from the Relationship Graph GR into the MPG, with |NC| copies of it

203 created, one for each variable. For every edge e[R](l,l′) _ER with edge type r, create an edge e[r](jl,jl[′])_
_∈_

204 with type r between every pair of binary nodes nj,l and nj,l′, 1 ≤ **j ≤|NC| (e.g., red edges encoding**

205 _less-than relation between value pairs (1, 2), (2, 3) and (1, 3)). We refer to them as Relational Edges._

206 **Recurrent Message Passing:** Once MPG has been constructed, we follow recurrent message

207 passing rules, with weights shared across layers, similar to RRNs (Palm et al., 2018) with some

208 differences. For each node nj,l in the graph, we maintain a hidden state ht(nj,l), which is updated at

209 each step t based on the messages received from its neighbors. This hidden state is used to compute

210 the probability of a binary node taking a value of 1. Since we use sparse encoding, only the node with

211 maximum probability amongst the k binary nodes nj,l; 1 **l** _k, corresponding to multi-valued_
_≤_ _≤_

212 variable x[j], is assigned a value 1, at the end of message passing. We give the details of message

213 passing and state update function in appendix. Next, we discuss how the nodes are initialized before

214 message passing starts, followed by the details of loss computation.

215 **Initialization: Irrespective of the size of value-set V or vertices NC**, there are 3 learnable embeddings

216 (u[0], u[1] and u[−1]) for initialization: two for binary values 0 and 1, and one for value −1 repre
217 senting unassigned nodes. All k nodes corresponding to an unassigned variable x[j] are initialized

218 with u[ 1], i.e., whenever x[j] is NULL (yellow nodes with 1), u0(nj,l) = u[ 1], _vl_, where

219 _u0 represents initial embedding function. On the other hand, if−_ _−_ **x[j] is preassigned a value−** _∀_ _∈V vˆl[, then]_

220 _u0(nj,l) = u[0], ∀vl ̸= vˆl[, and][ u][0][(][n]j,[ˆ]l[) =][ u][[1]][.][ E.g.][, variable corresponding to the binary nodes in]_

221 1st row has a preassigned value of ‘3’, consequently, binary nodes in 1st and 2nd column of the 1st

222 row are initialized with u[0], and binary node in the 3rd column of 1st row, which corresponds to

223 assignment ‘x[1] = 3’, is initialized with u[1]. Lastly, the hidden state, h0(nj,l), of each node, nj,l,

224 is initialized as a 0 vector, **j,** _vl._
_∀_ _∀_

225 **Loss Computation: The Binary Cross Entropy (BCE) loss for each node nj,l is computed w.r.t. its**

226 target, ˜y[j, l], which is defined as 1 whenever y[j] = l and 0 otherwise. At each step t ∈{1 . . . T _},_

227 we can compute the probability Pr(nj,l.v = 1; Θ) of classifying a node nj,l as 1 by passing its

228 hidden state through a learnable scoring function s, i.e., Prt(nj,l.v = 1; Θ) = σ(s(ht(nj,l))),

229 where σ is the standard Sigmoid function. Here, nj,l.v denotes the value that node nj,l can

230 take and belongs to the set 0, 1 . Loss at step t is the average BCE loss across all the nodes:

1 _{_ _}_

231 _|N_ _|_ _nj,l∈N_ **y[˜][j, l] log Prt(nj,l.v = 1; Θ) + (1 −** **y˜[j, l]) log Prt(nj,l.v = 0; Θ). Like Palm et al.**

232 (2018), we back-propagate through the loss at every step t 1 . . . T as it helps in learning a con
P _∈{_ _}_

233 vergent message passing algorithm. During training, the objective is to learn the 3 initial embeddings

234 _u[−1], u[0], u[1], functions used in message passing and state update, and the scoring function s._

235 **Prediction on a problem with larger size of value-set: While testing, let the constraint and relation**

236 graph be GC′ and GR′ with n[′] and k[′] nodes respectively. Let x[′] be a partial solution, with n[′] variables

237 **x[′][j], each taking a value from value-set V** _[′]_ of size k[′]. As described above, we create a graph G[′] with

238 _n[′]k[′]_ nodes, run message passing for T steps, and for each variable x[′][j], compute the k[′] probabilities,

239 one for each of the k[′] nodes nj,l **l** corresponding to the variable x[′][j], which is assigned the
_∀_ _∈V_ _[′]_

240 value corresponding to maximum probability, i.e., ˆy[j] = arg maxl∈V _′ PrT (nj,l.v = 1; Θ)._

241 4.2 MULTI-VALUED MODEL


242 Multi-valued model differs from the binarized model by avoiding binarization of nodes, and instead

243 explicitly adding Value Nodes in the message passing graph, one for each value in the value-set.

244 The message graph consists of two components: (a) A Graph G = (N, E) to represent constraints

245 inherited from the constraint graph GC = (NC, EC) (b) A Graph _G[˜] = ( N,[˜]_ _E[˜]) to represent relations_

246 inherited from the relationship graph GR = (NR, ER). We refer to G as Constraint Message Passing

247 _Graph (CMPG), and_ _G[˜] 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.

249 This is followed by message passing on CMPG which uses the embeddings of the value nodes

250 generated by RMPG and computes embeddings for each variable node. Finally, the variable nodes

251 are classified based on the similarity of their embedding with the embeddings of the value nodes


-----

252 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._

254 **Construction of CMPG: Nodes: For each node n[C]j**

255 a k-valued node, denoted as nj _N_ . Total number of such nodes constructed is[∈] _[N][C][ in the constraint graph, we construct]NC_ . We refer

256 to these as Variable Nodes (yellow nodes in Multi-Valued Graph in fig. 1). Additionally, for each ∈ _|_ _|_

257 value vl in the value-set, we create a node, denoted as n[v]l

258 constructed is ∈V _|V|. We refer to these as Value Nodes (orange nodes).[∈]_ _[N]_ [. Total number of such nodes]Edges: For every edge,

259 _e[C]_ (j,j′) ∈ _EC, where e[C]_ (j,j′).type = q, we introduce an edge denoted as e[q](j,j[′]) [with type][ q][. These]

260 edges are directly inherited from the constraint graph. We refer to these as Constraint Edges (black

261 edges). Additionally, to indicate the pre-assignment of values to the variables in x, we introduce new

262 edges connecting value nodes to appropriate variable nodes. Whenever x[j] = vl, add an edge, e[a](j,l)

263 between variable node nj and value node n[v]l [(blue edges). If][ x][[][j][]][ is][ NULL][,][ i.e.][, unassigned, then add]

_a_
264 _k edges, e([¯]j,l)[,][ ∀][v][l][ ∈V][, connecting the variable node][ n][j][ with all][ k][ value nodes][ n]l[v]_ [(][e.g.][, green edges]

265 connecting orange value node ‘2’ to all ‘-1’ variable nodes). We refer to them as Assignment Edges.

266 **Construction of RMPG: Nodes: For each value vl**, create a node denoted as ˜n[v]l _N (purple_

267 nodes in Relation Graph in fig. 1). Total number of such nodes constructed is ∈V _|V|. We refer to these[∈]_ [˜]

268 as Value Nodes. Edges: For every pair of value nodes, ˜n[v]l [and][ ˜]n[v]l[′] [, introduce an edge][ ˜]e[r](l,l[′]) [with type]

269 _r if r(vl, vl[′]_ ) holds based on the relationship graph GR, i.e., e[R](l,l′) _ER with edge label r (red_

270 edges). These edges are defined for relations that exist between values in the value-set. ∈

271 **Achieving Value-set Invariance: A key question arises here: why do we need to construct a separate**

272 RMPG (G[˜])? Why not embed relevant edges in CMPG (G), as done for the binarized model? The

273 answer lies in realizing that we represent each value in the value-set explicitly in the multi-valued

274 model, unlike the binarized model. Hence, our model needs to learn representation for each of them

275 in the form of value node embeddings. Further, to generalize we need to learn as many embeddings

276 as there are values in the largest test value-set, i.e., kmax = max |V _[′]|. We achieve this by randomly_

277 sub-selecting a k-sized set from 1 . . . kmax and permuting the chosen subset for each training
_{_ _}_

278 example in a given mini-batch, and then computing the ‘relationship-aware’ embeddings from this

279 permuted subset through message passing in RMPG. The ‘relationship-aware’ embeddings are then

280 used to initialize the value nodes (orange nodes) during message passing in CMPG. For instance,

281 if the permutation obtained is _w1,_ _, wl,_ _, wk_, where **l, 1** _wl_ _kmax, then embedding_
_{_ _· · ·_ _· · ·_ _}_ _∀_ _≤_ _≤_

282 for the value node ˜n[v]l [in][ ˜]G is initialized by wl[th] learnable embedding (e.g., purple nodes for values

283 ‘1’, ‘2’, and ‘3’ are initialized by the 5th, 7th, and 1st learnable embedding, respectively). After

284 message passing on _G[˜], the ‘relationship-aware’ embedding of ˜n[v]l_ [(purple node) is used to initialize]

285 the embedding for value node n[v]l [(orange node) in][ G][. This elegant process is able to train all the][ k][max]

286 embeddings by simply using the training data corresponding to V, and the corresponding relationship

287 information. Since these relationship aware embeddings need to be pre-computed before they can be

288 passed to the downstream constraint processing, we construct two different message passing graphs,

289 one for computing relationship-aware embeddings and one for constraint handling.

290 **Recurrent Message Passing on RMPG: Rules of message passing and hidden state updates at**

291 every step t are similar to RRN in Palm et al. (2018) and defined in detail in the appendix. After

292 updating the hidden states for total _T[˜] steps, the final embeddings,_ _h[˜] ˜T_ [(˜]n[v]l [)][ ∀][v][l][ ∈V][, are used as]

293 ‘relationship-aware’ embeddings for initializing the input features (embeddings) of the nodes in

294 CMPG G. We now discuss the initialization of the value nodes before message passing in RMPG.

295 **Initialization: There are a total of kmax learnable embeddings, ˜u[l[′]], 1 ≤** **l[′]** _≤_ _kmax, out of which any_

296 _k are randomly chosen for initializing the nodes in RMPG. e.g., ˜u[5], ˜u[7], ˜u[1] are chosen to initialize_

297 the purple value nodes ‘1’,‘2’, and ‘3’ in Relation Graph in fig. 1. Formally, for each input x, select

298 a k-permutation, Px, of kmax. Initialize the embedding of ˜n[v]l [in][ ˜]G with ˜u[Px[l]], ∀l ∈{1 . . . k}.

299 Initialize the hidden state, _h[˜]0(˜n[v]l_ [)][,][ ∀]n[˜][v]l _[∈]_ _N[˜] with a 0 vector._

300 **Recurrent Message Passing on CMPG: Message passing on CMPG updates the hidden state,**

301 _ht(nj), of each variable node nj for a total of T (t ≤_ _T_ ) steps using the messages received from its

302 neighbors. The details are similar to message passing in binarized model and are discussed in the

303 appendix. Below we describe the initialization of node embeddings followed by computation of loss.


-----

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**

**6** **7** **8** **9** **10** **11** **12**

**Pointwise Accuracy**

|NLM15 NLM30 MV BIN|73.37 (1.34) 56.98 (1.47) 48.71 (1.96) 44.16 (1.72) 37.54 (2.74) 32.50 (2.84) - 85.72 (0.39) 69.61 (0.57) 63.52 (1.20) 60.73 (1.29) 55.94 (0.85) - - 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) 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)|
|---|---|

|NLM15 NLM30 MV BIN|96.72 (0.16) 93.9 (0.26) 93.43 (0.26) 93.86 (0.28) 94.07 (0.29) 94.29 (0.31) - 97.88 (0.05) 95.32 (0.10) 95.09 (0.14) 95.48 (0.08) 95.68 (0.03) - - 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) 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), n[v]l** [in][ G][, using the]

305 final ‘relationship-aware’ embeddings, _h[˜] ˜T_ [(˜]n[v]l [)][, of][ ˜]n[v]l [(purple nodes) in][ ˜]G. The variable nodes

306 that are preassigned a value (non-zero yellow nodes) in x, are initialized by the embedding of

307 the corresponding value node, i.e., if x[j] = l, then nj is initialized with the ‘relationship-aware’

308 embedding, _h[˜] ˜T_ [(˜]n[v]l [)][, of][ ˜]n[v]l [. The embedding of nodes corresponding to the unassigned variables]

309 (‘-1’ yellow nodes) are initialized by the average, (1/k) _vl_ _h[˜] ˜T_ [(˜]n[v]l [)][, of all ‘relationship-aware’]
_∈V_

310 embeddings. Initialize hidden state h0(nj) of each variable node nj with a 0 vector.

311 **Loss Computation: For each variable represented by node[P]** _nj, the ground truth value y[j] acts_

312 as the target for computing standard Cross Entropy Loss. The probabilities over V are computed

313 as follows: At step t, a scoring function, s, computes a score, s(ht(nj), ht(n[v]l [))][, for assigning]

314315 a valuenodes. For each variable node, a vl ∈V to a variable nj Softmax based on the hidden state of corresponding value and variable converts these scores into probabilities over the values

316317 _vthe value that nodel ∈V, i.e., Pr(nj.v n =j can take. Loss at step vl) = Softmax(s(ht( tn is nothing but the average over variable nodes:j), ht(n[v]l_ [)))][,][ ∀][v][l][ ∈V][, where,][ n][j][.v][ ∈V][ denotes]

318 _Lt = −_ _|N[1]_ _|_ _nj∈N_ [log][ Pr][(][n][j][.v][ =][ y][[][j][])][. To ensure that the multi-valued model learns different]

319 embeddings for each value in the value-set, we add an auxiliary loss term, corresponding to the total

P

320 pairwise dot product (similarity) of any two embeddings, before and after message passing in _G[˜]. We_

321 call it Orthogonality Loss. Its weight, α, is a hyper-parameter.

322 **Prediction on a problem with larger size of value-set: For a puzzle with larger value-set, V** _[′], a_

323 bigger RMPG is created, whose k[′] nodes are initialized with the (learnt) first k[′] embeddings. Unlike

324 training, we always choose first k[′] embeddings to avoid randomness during testing. Prediction is

325 made using the probabilities at the last step T, i.e., ˆy[j] = arg maxvl∈V _′ Pr(nj.v = vl)._

326 **Relative Comparison: In the binarized model, the constructed graph G has k|NC| nodes and at**

327 least k _EC_ + _NC_ _k(k_ 1)/2 edges due to binarization. This increases the graph size by a factor of
_|_ _|_ _|_ _|_ _−_

328 at least k. As a result, we soon hit the memory limits of a GPU while training the binarized model

329 with bigger problems. The model also needs significantly more inference time due to its bigger size.

330 On the other hand, multi-valued model, while being compact in terms of its representation, needs to

331 learn additional embeddings, for a speculative size of value-set during testing. This poses additional

332 requirement on the model both in terms of representation, and learning, possibly affecting the quality

333 of generalization. While this is a simple analytical understanding of the possible merits of the two

334 models, we examine experimentally the impact of these issues on real datasets.

335 5 EXPERIMENTS


336 The goal of our experiments is to evaluate the effectiveness of our two proposed methods for achieving

337 value-set invariance. We compare our models with a generic neural constraint learner, NLM (Dong

338 et al., 2019). [2] We experiment on datasets generated from Lifted CSPs of three different puzzles, viz.,

339 Sudoku, Futoshiki, and Graph Coloring (ref. Table 5 in appendix for details). We train each model on

340 data generated from a fixed value-set, and test on instances generated from larger value-sets.

2Our aim is not to directly compete with SOTA SAT solvers, which are much more scalable than neural
methods. Refer to appendix for a discussion on comparison with them as well as neural SAT solvers.


-----

341 5.1 TASK DESCRIPTION AND DATASETS

342 **Futoshiki: This is a number puzzle in which we have to place numbers {1 . . . k} on a k × k grid,**

343 such that no two cells in a row or column contain the same number. In addition, there may be

344 an ordering constraint between two cells, which needs to be honored in the final solution. The

345 input has some of the grid cells already filled with a number and the task is to complete the grid,

346 respecting the additional ordering constraint where ever it exists. We train our model on 6 _×_ 6 puzzles,

347 with the percentage of missing cells varying uniformly between 28 − 70%. We test our models on

348 puzzles with board size ranging between 6 × 6 to 12 × 12, with the same percentage of missing cells.

349 **Graph Coloring (GCP): In this task**

350 we are given a partially colored graph Table 2: GCP: Mean (Std. dev.) of coloring and pointwise

351 along with the number of colors k, and accuracy on graphs with different chromatic number.

352 the objective is to color rest of the **Board Accuracy**

356 erated 4 colorable graphs, and test **Pointwise Accuracy**

|Col1|Board Accuracy|
|---|---|
|NLM24 MV BIN|4 5 6 7|
||81.34 (5.93) 70.78 (7.45) 71.25 (8.35) 73.20 (7.58) 97.80 (0.03) 97.72 (0.37) 94.03 (2.54) 72.21 (11.17) 99.09 (0.07) 96.69 (2.61) 95.7 (4.04) 94.35 (4.82)|



359 with graph order varying uniformly be
|NLM24 MV BIN|99.47 (0.13) 98.58 (0.34) 97.95 (0.54) 97.26 (0.68) 99.96 (0.00) 99.89 (0.00) 99.50 (0.23) 96.22 (1.55) 99.96 (0.01) 99.85 (0.03) 99.76 (0.08) 99.48 (0.16)|
|---|---|


360 tween 40 − 120, and percentage of masked nodes vary uniformly between 28 − 70%.

361 **Sudoku: We randomly select 10, 000 training queries from the 9 × 9 dataset introduced in Palm**

362 et al. (2018). Our test set has k[′] _× k[′]_ puzzles, with k[′] _∈{10, 12, 15, 16}. Data generation process is_

363 similar to Futoshiki, with the distribution of missing cells varying between 30 − 68% depending on

364 the board size. Instead of backtracking, solution validity is checked through the GSS library (Pieters,

365 2019). Please see appendix for more details on data generation process for all three tasks.


366 5.2 EXPERIMENTAL SETUP & BASELINES

367 In both our models, nodes Table 3: Sudoku: Mean (Std. dev.) of board and pointwise accuracy on

368369 are initialized with learn-able 96 dimensional em- different board-sizes. Both models trained on 9 × 9 puzzles

**Pointwise Accuracy**

|Col1|Board Accuracy|
|---|---|
|MV BIN|9 10 12 15 16|
||92.78 (0.08) 99.65 (0.15) 88.30 (6.08) 29.33 (13.71) 19.70 (14.03) 99.13 (0.14) 99.91 (0.04) 99.63 (0.10) 63.05 (45.71) 27.31 (23.81)|


373 for Futoshiki, GCP, and Su
375 passing on G in binarized

|MV BIN|98.52 (0.05) 99.96 (0.02) 99.43 (0.26) 97.03 (0.71) 96.30 (0.90) 99.87 (0.02) 99.99 (0.00) 99.96 (0.01) 95.55 (6.60) 88.39 (14.25)|
|---|---|


376 model runs for 32 steps. Message passing on RMPG, _G[˜] and CMPG, G in the multi-valued model_

377 runs for _T[˜] = 1 and T = 32 steps respectively. The message passing functions in both the models are_

378 3 layer MLPs, similar to those in RRN, with a difference that there is a separate function for each

379 edge type. In both the models, a layer normalized LSTM cell with hidden dimension 96 acts as state

380 update functions. All models are trained on K40 GPU nodes with 12GB memory. We take simple

381 average of model weights stored at multiple points (Izmailov et al., 2018). All checkpoints obtained

382 after flattening of the learning curve are selected for computing average. See appendix for details.

383 **Baseline: For Futoshiki, we train two versions of NLM by varying depth: the number of Logic**

384 Machines that are stacked on top of each other. Like (Nandwani et al., 2021), we train one 30 layer

385 deep NLM model with residual connections for Futoshiki, but unlike them, we assume access to

386 constraint graph, which we provide as a binary predicate input to the model. NLM with 30 depth

387 could not fit puzzles with board-size greater than 10 within 12GB memory of K40 GPU. Hence, we

388 train another version by reducing the depth to 15. For GCP, we train a model with depth 24. For

389 Sudoku, on increasing depth beyond 14, we could not fit even one 9 × 9 train sample within GPU

390 memory. Note that the maximum depth chosen for the graph experiments reported in (Dong et al.,

391 2019) is 8. This is because they work with much smaller graphs (up to maximum 50 nodes), whereas

392 smallest graph in Futoshiki has 6[3] = 216 binary nodes, warranting creation of much deeper models.

393 **Evaluation Metrics: We report two metrics: board accuracy and point-wise accuracy. In the former,**

394 we consider output of the model as correct only if it satisfies the underlying CSP, whereas in the later,


-----

395 we give partial credit even for assigning some of the variables correctly. See Appendix for details.

396 For each setting, we report the mean and standard deviation over three runs by varying random seed.


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- accuracy of models fine-tuned on 24 board-size

399 ent sizes of value-set for Futoshiki,

**Pointwise Accuracy**

|Col1|Board Accuracy|
|---|---|
|MV BIN|15 16 24 25|
||91.03 (3.25) 90.39 (3.49) 54.57 (21.25) 43.77 (14.42) 63.05 (45.71) 27.31 (23.81) 0.0 (0.0) 0.0 (0.0)|


403 its performance is worse than one or

405 tal settings in Futoshiki and GCP. As

|MV BIN|99.43 (0.16) 99.46 (0.15) 99.30 (0.12) 99.10 (0.09) 95.55 (6.60) 88.39 (14.25) 7.85 (0.63) 7.44 (0.43)|
|---|---|


406 expected, in Futoshiki, NLM model with depth 30 fails to run on board sizes 11 and 12 and depth

407 15 model fails to run on size 12. Note that both NLM and our binarized model work by binarizing

408 the underlying puzzle, but we observe that binarized model shows significantly better generalization

409 across value-sets. We note that NLM performs decently well for GCP even for the test graphs with

410 chromatic number k[′] = 7. We attribute this to the fact that in our test data for k[′] = 7, graphs are

411 relatively small, with max 80 graph nodes, resulting in total 560 binary objects in NLM, which is

412 similar to the max 400 binary objects that it trains over (k=4, max 100 nodes).

413 **Comparison between binarized model and multi-valued model: We first observe that both our**

414 models achieve similar performance on the value-set over which they are trained. We observe

415 that the standard deviation of the board accuracy increases significantly as the size of value-set

416 increases, whereas the pointwise accuracy is relatively stable. This is due to the high sensitivity of

417 the board accuracy to pointwise accuracy: even if a single variable is incorrectly assigned in a puzzle,

418 its contribution towards board accuracy goes to 0, whereas it still contributes positively towards

419 pointwise accuracy. When trained on small sizes, binarized model shows better generalization. But

420 as the problem size increases, the computational graph for binarized model fails to fit in the available

421 GPU memory and thus its performance degrades. On the other hand, multi-valued model being

422 memory efficient, scales much better. To demonstrate this, Table 4 reports the performance of multi
423 valued model further finetuned on sudoku puzzles of board-size 24, and tested on board-sizes varying

424 between 15 and 25. We couldn’t finetune the binarized model as its computational graph doesn’t fit in

425 the GPU. The binarized model trained on puzzles of board-size 9 gives 0.0 board accuracy on size 24

426 and 25. The performance of multi-valued model is better than binarized model not only on board-size

427 25, but also on board-sizes smaller than 24. This also demonstrates that the poor performance of the

428 same multi-valued model trained on smaller board-size is not due to any lack of representation power,

429 but due to difficulty in learning additional embeddings: when training k[′] embeddings from puzzles

430 of board-size k, multi-valued model never gets to see all k[′] value embeddings together. Moreover,

431 the different combinations of k out of k[′] embeddings increase exponentially with (k[′] _−_ _k), making_

432 it further difficult to train. To validate this, we train a multi-valued model with only 7 learnable

433 embeddings for Futoshiki and observe that the board accuracy on 7 board-size increases to 97.82%

434 (at par with binarized model) from 90.18% which is achieved when trained with 12 embeddings.


435 **Computational complexity: In fig. 2, for the two models, we com-**

436 pare the average inference time and the GPU memory occupied by

437 a batch of 32 Futoshiki puzzles over value-sets of varying sizes. As

438 expected, the multi-valued model is much more efficient, both in

439 terms of time and memory.

440 6 CONCLUSION AND FUTURE WORK


(a) Runtime

(b) Memory

Figure 2: Resource: Futoshiki


441 We have looked at the novel problem of value-set invariance in com
442 binatorial puzzles, formally defined using lifted CSPs and proposed

443 two different neural solutions extending RRNs. Our experiments

444 demonstrate the superior performance of our models compared to

445 an existing neural baseline. We discuss the relative strengths and

446 weaknesses of our proposed models. Future work includes solving

447 more complicated CSPs, and scaling to even larger sizes.


-----

448 ACKNOWLEDGEMENT

449 We thank IIT Delhi HPC facility[3] for computational resources. We thank anonymous reviewers for

450 their insightful comments and suggestions that helped in further improving our paper. Mausam is

451 supported by grants from Google, Bloomberg, 1MG and Jai Gupta chair fellowship by IIT Delhi.

452 Parag Singla is supported by the DARPA Explainable Artificial Intelligence (XAI) Program with

453 number N66001-17-2-4032. Both Mausam and Parag Singla are supported by the Visvesvaraya Young

454 Faculty Fellowships by Govt. of India and IBM SUR awards. Any opinions, findings, conclusions or

455 recommendations expressed in this paper are those of the authors and do not necessarily reflect the

456 views or official policies, either expressed or implied, of the funding agencies.


457 ETHICS STATEMENT

458 In its current form, our work is primarily a technical contribution, with no immediate ethical

459 consequences. Our work develops the line of recent research in which constraint reasoning is carried

460 out through neural architectures. We believe that neural approaches for symbolic reasoning will go a

461 long way in creating an integrated AI system. This is because an integrated system requires not only

462 perceptual, but also high-level reasoning. Neural approaches will provide a uniform vocabulary so

463 that both these forms of reasoning can interact with each other, improving performance of the overall

464 system.

465 As more AI systems start to be used in critical applications such as healthcare, law, and disaster

466 management, it is important that they honor the safety and accountability constraints set up by domain

467 experts. Their ability to perform high-level reasoning enables them to honor such constraints more

468 effectively. Thus, our line of work, in the long run, could have significant positive ethical implications.

469 We see no obvious negative implications of our work.


470 REPRODUCIBILITY STATEMENT

471 To ensure reproducibility, we have discussed the dataset creation process and provided model

472 architecture details in Section 5.1 and Section 5.2, respectively. We provide the details of the exact

473 hyper-parameters, computational resources used, and additional experimental details in the appendix.

474 We also make our code publicly available at https://github.com/dair-iitd/output-space-invariance.


475 REFERENCES

476 Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An

477 unsupervised differentiable approach. In 7th International Conference on Learning Representations,

478 _[ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019a. URL https:](https://openreview.net/forum?id=BJxgz2R9t7)_

479 [//openreview.net/forum?id=BJxgz2R9t7.](https://openreview.net/forum?id=BJxgz2R9t7)

480 Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. PDP: A general neural framework for

481 [learning constraint satisfaction solvers. CoRR, abs/1903.01969, 2019b. URL http://arxiv.](http://arxiv.org/abs/1903.01969)

482 [org/abs/1903.01969.](http://arxiv.org/abs/1903.01969)

483 Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly

484 learning to align and translate. In 3rd International Conference on Learning Representations,

485 _ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL_

486 [http://arxiv.org/abs/1409.0473.](http://arxiv.org/abs/1409.0473)

487 Aniket Bajpai, Sankalp Garg, and Mausam. Transfer of deep reactive policies for MDP planning. In

488 _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information_

489 _Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 10988–_

490 10998, 2018.

491 Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph

492 classification extrapolations. In Proceedings of the 38th International Conference on Machine


3http://supercomputing.iitd.ac.in


-----

493 _Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139, pp. 837–851, 2021. URL_

494 [http://proceedings.mlr.press/v139/bevilacqua21a.html.](http://proceedings.mlr.press/v139/bevilacqua21a.html)

495 Nuri Cingillioglu and Alessandra Russo. Deeplogic: Towards end-to-end differentiable logical

496 reasoning. In Proceedings of the AAAI 2019 Spring Symposium on Combining Machine Learning

497 _with Knowledge Engineering (AAAI-MAKE 2019) Stanford University, Palo Alto, California, USA,_

498 _March 25-27, 2019., Stanford University, Palo Alto, California, USA, March 25-27, 2019, volume_

499 [2350 of CEUR Workshop Proceedings. CEUR-WS.org, 2019. URL http://ceur-ws.org/](http://ceur-ws.org/Vol-2350/paper21.pdf)

500 [Vol-2350/paper21.pdf.](http://ceur-ws.org/Vol-2350/paper21.pdf)

501 Johan de Kleer. A comparison of ATMS and CSP techniques. In Proceedings of the 11th International

502 _Joint Conference on Artificial Intelligence. Detroit, MI, USA, August 1989, pp. 290–296, 1989._

503 [URL http://ijcai.org/Proceedings/89-1/Papers/046.pdf.](http://ijcai.org/Proceedings/89-1/Papers/046.pdf)

504 Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic

505 machines. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans,

506 _[LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https://openreview.net/forum?](https://openreview.net/forum?id=B1xY-hRctX)_

507 [id=B1xY-hRctX.](https://openreview.net/forum?id=B1xY-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, 2 Volumes, pp. 1169–1177, 1997. URL http:](http://ijcai.org/Proceedings/97-2/Papers/055.pdf)_

511 [//ijcai.org/Proceedings/97-2/Papers/055.pdf.](http://ijcai.org/Proceedings/97-2/Papers/055.pdf)

512 Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. J. Artif. Intell.

513 _[Res., 61:1–64, 2018. doi: 10.1613/jair.5714. URL https://doi.org/10.1613/jair.](https://doi.org/10.1613/jair.5714)_

514 [5714.](https://doi.org/10.1613/jair.5714)

515 Nir Friedman, Lise Getoor, Daphne Koller, and Avi Pfeffer. Learning probabilistic relational models.

516 In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99,

517 _Stockholm, Sweden, July 31 - August 6, 1999. 2 Volumes, 1450 pages, pp. 1300–1309, 1999. URL_

518 [http://ijcai.org/Proceedings/99-2/Papers/090.pdf.](http://ijcai.org/Proceedings/99-2/Papers/090.pdf)

519 Sankalp Garg, Aniket Bajpai, and Mausam. Symbolic network: Generalized neural policies for

520 relational mdps. In Proceedings of the 37th International Conference on Machine Learning, ICML

521 _2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research,_

522 pp. 3397–3407. PMLR, 2020.

523 Kazuo Iwama and Shuichi Miyazaki. Sat-variable complexity of hard combinatorial problems. In In

524 _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
526 son. Averaging weights leads to wider optima and better generalization. In Proceedings of the

527 _Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, Cali-_

528 _[fornia, USA, August 6-10, 2018, pp. 876–885, 2018. URL http://auai.org/uai2018/](http://auai.org/uai2018/proceedings/papers/313.pdf)_

529 [proceedings/papers/313.pdf.](http://auai.org/uai2018/proceedings/papers/313.pdf)

530 David Joslin and Amitabha Roy. Exploiting symmetries in lifted csps. In The 14th National

531 _Conference on Artificial Intelligence (AAAI), pp. 197–202. AAAI Press, 1997._

532 Daniel Kahneman. Thinking, fast and slow. Macmillan, 2011.


533 Nada Lavrac and Luc De Raedt. Inductive logic programming: A survey of european research.

534 _[AI Commun., 8(1):3–19, 1995. doi: 10.3233/AIC-1995-8101. URL https://doi.org/10.](https://doi.org/10.3233/AIC-1995-8101)_

535 [3233/AIC-1995-8101.](https://doi.org/10.3233/AIC-1995-8101)

536 Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De

537 Raedt. Deepproblog: Neural probabilistic logic programming. In Advances in Neu
538 _ral Information Processing Systems 31:_ _Annual Conference on Neural Information Pro-_

539 _cessing Systems 2018,_ _NeurIPS 2018,_ _December 3-8,_ _2018,_ _Montréal,_ _Canada,_ pp.

540 [3753–3763, 2018. URL https://proceedings.neurips.cc/paper/2018/hash/](https://proceedings.neurips.cc/paper/2018/hash/dc5d637ed5e62c36ecb73b654b05ba2a-Abstract.html)

541 [dc5d637ed5e62c36ecb73b654b05ba2a-Abstract.html.](https://proceedings.neurips.cc/paper/2018/hash/dc5d637ed5e62c36ecb73b654b05ba2a-Abstract.html)


-----

542 Mehrab Najafian, Mohammad Hesam Tadayon, and Morteza Esmaeili. Construction of strongly

543 mutually distinct sudoku tables and solid sudoku cubes by cyclotomic cosets. IEEE Transactions

544 _on Games, PP:1–1, 11 2018. doi: 10.1109/TG.2018.2880953._

545 Yatin Nandwani, Deepanshu Jindal, Mausam, and Parag Singla. Neural learning of one-of-many

546 solutions for combinatorial problems in structured output spaces. In International Conference on

547 _Learning Representations (ICLR), 2021._

548 Rasmus Berg Palm, Ulrich Paquet, and Ole Winther. Recurrent relational networks. In Advances in

549 _Neural Information Processing Systems 31: Annual Conference on Neural Information Processing_

550 _Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pp. 3372–3382, 2018. URL_

551 [http://papers.nips.cc/paper/7597-recurrent-relational-networks.](http://papers.nips.cc/paper/7597-recurrent-relational-networks)

552 [Laurent Perron and Vincent Furnon. Or-tools, 2019. URL https://developers.google.](https://developers.google.com/optimization/)

553 [com/optimization/.](https://developers.google.com/optimization/)

554 [Bart Pieters. Generic sudoku solver. https://github.com/bartp5/gss, 2019.](https://github.com/bartp5/gss)


555 Tim Rocktäschel, Sameer Singh, and Sebastian Riedel. Injecting logical background knowledge

556 into embeddings for relation extraction. In NAACL HLT 2015, The 2015 Conference of the

557 _North American Chapter of the Association for Computational Linguistics: Human Language_

558 _Technologies, Denver, Colorado, USA, May 31 - June 5, 2015, pp. 1119–1129, 2015. URL_

559 [http://aclweb.org/anthology/N/N15/N15-1118.pdf.](http://aclweb.org/anthology/N/N15/N15-1118.pdf)

560 Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill.

561 Learning a SAT solver from single-bit supervision. In 7th International Conference on Learning

562 _Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL_

563 [https://openreview.net/forum?id=HJMC_iA5tm.](https://openreview.net/forum?id=HJMC_iA5tm)

564 Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value iteration networks. In

565 _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI_

566 _2017, Melbourne, Australia, August 19-25, 2017, pp. 4949–4953, 2017._

567 Hao Tang, Zhiao Huang, Jiayuan Gu, Bao-Liang Lu, and Hao Su. Towards

568 scale-invariant graph-related problem solving by iterative homogeneous gnns. In

569 _NeurIPS, 2020._ [URL https://proceedings.neurips.cc/paper/2020/hash/](https://proceedings.neurips.cc/paper/2020/hash/b64a70760bb75e3ecfd1ad86d8f10c88-Abstract.html)

570 [b64a70760bb75e3ecfd1ad86d8f10c88-Abstract.html.](https://proceedings.neurips.cc/paper/2020/hash/b64a70760bb75e3ecfd1ad86d8f10c88-Abstract.html)

571 Toby Walsh. SAT v CSP. In Principles and Practice of Constraint Programming - CP 2000, 6th

572 _International Conference, Singapore, September 18-21, 2000, Proceedings, volume 1894 of Lecture_

573 _Notes in Computer Science, pp. 441–456. Springer, 2000. doi: 10.1007/3-540-45349-0\_32. URL_

574 [https://doi.org/10.1007/3-540-45349-0_32.](https://doi.org/10.1007/3-540-45349-0_32)

575 Po-Wei Wang, Priya L. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and

576 logical reasoning using a differentiable satisfiability solver. In Proceedings of the 36th International

577 _Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA,_

578 volume 97 of Proceedings of Machine Learning Research, pp. 6545–6554. PMLR, 2019. URL

579 [http://proceedings.mlr.press/v97/wang19e.html.](http://proceedings.mlr.press/v97/wang19e.html)

580 Gilad Yehudai, Ethan Fetaya, Eli A. Meirom, Gal Chechik, and Haggai Maron. From local structures

581 to size generalization in graph neural networks. In Proceedings of the 38th International Conference

582 _on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139, pp. 11975–11986,_

583 [2021. URL http://proceedings.mlr.press/v139/yehudai21a.html.](http://proceedings.mlr.press/v139/yehudai21a.html)

584 Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang,

585 Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications.

586 _AI Open, 1:57–81, 2020._


-----

587 A APPENDIX

588 2 RELATED WORKS

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

591 papers (and results) in this line of research can be broadly divided into two sub-classes. The first set

592 of results talk about the representation power of GNNs to handle various graph sizes. The second set

593 of results talk about learnability issues with GNNs under varying train/test distributions. We look at

594 some of the results below and try to explain why GNNs in our case are able to generalize well, both

595 in terms of representation power, as well as learnability.

596 _Representation Power: We hypothesize that there are two design choices that are helping us gain_

597 good representation power: 1. Ability to create a deep network without blowing up the number of

598 parameters because of weight tying across layers, and 2. Preassigned class labels to some of the

599 variables which act as node features and help in breaking the symmetry. We argue it on the basis of

600 Theorem 4.2 in Yehudai et al. (2021), which proves that there exists a (d + 3) layered GNN that can

601 distinguish between nodes having different local structure, which is quantified via d-patterns that

602 can be thought of as a generalization of node degree to d-hop neighborhood. Hence, to be able to

603 distinguish between nodes on the basis of a GNN, all we need to do is ensure that different nodes

604 have different d-patterns. This can be achieved in 2 ways: 1. By increasing d, e.g. two nodes may

605 have the same degree and hence the same 1-pattern, but their neighbors may have different degrees,

606 which will lead to different 2-pattern for these two nodes. 2. By assigning node features, e.g. two

607 nodes may have the same degree, but their neighbors may have different node features, leading to

608 a different 1-pattern for them as d-pattern also takes initial node features into account. In addition,

609 Tang et al. (2020) also argue that one way of increasing the representation power of GNNs is by

610 increasing their depth, and it achieves the same by proposing IterGNN that applies the same GNN

611 layer for an adaptive number of iterations depending on the input graph. This is equivalent to tying

612 the weights of different layers as in RRNs, as well as in our models.

613 _Learnability: With respect to learnability, Yehudai et al. (2021) prove the existence of a ‘bad’ local_

614 minima that overfits on train data but fails on test samples that have unseen d-patterns. Our test

615 dataset clearly has unseen d-patterns (e.g. nodes in 16 x 16 sudoku have different degrees than nodes

616 in 9 x 9 sudoku), but our models still generalize. We note that Yehudai et al. (2021) only talks about

617 the existence of some bad local minima, but does not rule out the possibility of the existence of other

618 good local minima, which could generalize well, despite differences in local structure between train

619 and test sets. This goes into the whole learnability argument, and whether we can find such not-so-bad

620 local minimas (which presumably exist since the possibility has not been ruled out). One aspect that

621 possibly comes to our rescue is that, unlike most GNN architectures, our design is recurrent in nature,

622 i.e., parameters are tied across different GNN layers as inspired by Palm et al. (2018). Parameter

623 tying assumption, possibly helps us in learnability, since the recurrence can be seen as a form of

624 regularization, avoiding overfitting (or getting stuck in bad local minima). Exploring this further is a

625 direction for future work.

626 In addition to Yehudai et al. (2021), Bevilacqua et al. (2021) deal with varying train/test distributions

627 by proposing a size invariant representation of graphs. Their approach focuses on graph classification

628 tasks, and is limited to creating size invariant representations for the entire graph. The theoretical

629 claims presented in their paper primarily focus on the limitation of standard GNN based formulations

630 for generalizing across sizes for graph classification tasks. On the other hand, we are interested in

631 learning representations for each node in the graph for node classification, and it is not clear how the

632 claims, as well as techniques proposed in the paper, extend to our setting.


633 4 MODELS DESCRIPTION

634 4.1 BINARIZED MODEL

635 **Recurrent Message Passing**

636 There are two categories of edges in the Message Passing Graph: Constraint Edges and Relation

637 _Edges. Each edge inherits an edge type, either from Constraint Graph, or Relation Graph. We denote_


-----

638 the set of all constraint edge types as Q, and the set of all relational edge types as R. We now describe

639 the details of message passing and hidden state update equations.

640 **Edge Dependent Message Passing: The nodes communicate their current hidden state via the**

641 messages sent to their neighbouring nodes across the edges. The message depends not only on

642 the current state of the sender and receiver, but also on the edge type across which the mes
643 sage is sent. Specifically, for each edge type, z, there is a separate message passing func
644 tion, fz, with z (Q _R) where Q and R are the set of all constraint edge types and re-_
_∈_ _∪_

645 lation edge types respectively. We compute the message for each edge e[z](j1l1,j2l2)

_[∈]_ _[E][ as:]_

646 _mt_ _e[z](j1l1,j2l2)_ = fz (ht (nj1,l1 ), ht (nj2,l2 )), _e[z](j1l1,j2l2)_
_∀_ _[∈]_ _[E, z][ ∈]_ [(][Q][ ∪] _[R][)][.]_
h i

647 **Hidden State Update: For each node, the incoming messages on the edges of the same type**

648 are aggregated by taking their weighted average. The weights, at, are computed using Bahdanau

649 Attention (Bahdanau et al., 2015) over constraint edges, whereas messages across relation edges are

650 simply averaged: mt,z[nj,l1 ] = _e[z](jl1_ _,j2_ **l2)[∈][E][ a][t][[][e]([z]jl1,j2l2)[]][m][t][[][e][z](jl1,j2l2)[]][,][ ∀][z][ ∈]** [(][Q][ ∪] _[R][)]_

651 Finally, all messages, mt,z[nj,l] _z_ (Q _R), are concatenated to create the input, mt[nj,l] for each_
_∀[P] ∈_ _∪_

652 node, nj,l. The hidden state at step t is updated by the following state update function to generate

653 the state ht+1(nj,l): ht+1(nj,l) = g (ht(nj,l), mt[nj,l], u0(nj,l)), _nj,l_ _N_ . See Figure 3 for an

654 illustration of edge dependent message passing and state update at a given step ∀ _∈_ _t._

655 4.2 MULTI-VALUED MODEL


656 There are two separate message passing graphs in multi-valued model: RMPG and CMPG. RMPG

657 contains edges encoding the relationship between the values. Each edge has an associated edge type

658 representing the relationship it encodes. We denote the set of all edge types in RMPG as R. In

659 CMPG, there are two categories of edges: Constraint Edges and Assignment Edges. Further, each

660 edge may have an associated edge type. The set of all constraint edge types is denoted as Q, and the

661 set of assignment edge types (edges from orange value nodes to yellow variable nodes in fig. 1) is

662 denoted as A. Finally, the initial embedding of a variable node nj is denoted as u0(nj).

663 We now describe the message passing rules and hidden state update equations.

664 **Recurrent Message Passing ( on RMPG)**


665 **Message Passing Update: At step t, update the hidden state,** _h[˜]t(˜n[v]l_ [)][, of each of the value nodes in]

666 _G˜, by the concatenation, mt[˜n[v]l_ []][, of average messages,][ m]t[r][[˜]n[v]l []][, received across edges of type][ r][ ∈] _[R][:]_

667 _h˜t+1(˜n[v]l_ [) = ˜]g(h[˜]t(˜n[v]l [)][, m][t][[˜]n[v]l []][,][ ˜]u[Px[l]]), where ˜g is the hidden state update function. Like (Palm

668 et al., 2018), it always takes the initial embedding, ˜u[Px[l]], of the value node ˜n[v]l [as one of the inputs.]

669670671 whereNotice that the message,T˜ steps and the final embeddings, fr is the message passing function for edge type m[r]t [[˜]n[v]l []][, is the average of the messages,]h[˜] ˜T [(˜]n[v]l [)][ ∀][v][l][ ∈V][, are used as ‘relationship-aware’ embeddings] r ∈ _R. The hidden states are updated for[ f][r][(˜]ht(˜n[v]l_ [)][,][ ˜]ht(˜n[v]l[′] [))][ ∀] _e[˜][r](l,l[′])_ _[∈]_ _E[˜],_

672 for initializing the input features (embeddings) of both variable nodes, nj, and value nodes, n[v]l [in][ G]

673 (orange and yellow nodes respectively in Multi-Valued Graph in fig. 1).

674 **Recurrent Message Passing ( on CMPG)**


675 **Message Passing Update: At step t, similar to binarized model, each variable node receives**

676 messages from its neighbors, that are aggregated based on the edge type. For each node, the

677 aggregated messages, mt,z[nj], for different edge types, z (Q _A), are stacked to create, mt[nj],_
_∈_ _∪_

678 which updates the hidden state as: ht+1(nj) = g (ht(nj), mt[nj], u0(nj)), _nj_ _N_ .

679 _∀_ _∈_

680

681 **Discussion on an alternate Encoding Scheme**


682 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

684 integer CSP into SAT, called ‘compact encoding’ (Ernst et al., 1997; Iwama & Miyazaki, 1994), in

685 which each Boolean SAT variable represents a single bit of the integer value that a CSP variable can

686 take. The final assignment of a CSP variable is given by the integer represented by the log k Boolean


-----

Figure 3: Hidden State Update at time-step t: We take a toy graph with 3 nodes, {a, b, c}, and 2
edge-types, {q, r}, to illustrate edge-dependent 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 fq and fr. Next, the incoming messages are aggregated by edge-type
(e.g., using attention based mechanism or simple averaging), and the outputs are concatenated to
obtain the final message, mt−1[b]. The hidden state of node b is updated by function g which takes
the previous hidden state h[t][−][1](b), the incoming message mt−1[b], and the initial embedding of the
node as its input.


-----

687 SAT variables corresponding to that variable. Motivated by the ‘compact encoding’, one can construct

688 another model: instead of a one-hot encoding which requires k nodes (one for each value in V) for

689 each variable, create log k binary valued nodes for each variable and assign a value v ∈V to the

690 variable based on the integer represented by log k bits corresponding to it. This results in a graph with

691 _NC_ log k nodes for a CSP with _NC_ variables and k classes, instead of _NC_ _k nodes in the binarized_
_|_ _|_ _|_ _|_ _|_ _|_

692 model, and brings it closer to the graph size of _NC_ + k created in multi-valued model. However,
_|_ _|_

693 such an approach failed to generalize across the size of the value-set in our experiments. In addition,

694 such an encoding has a limitation in its representational capability. It can not encode the relationship

695 between the values effectively. For example, in k × k Futoshiki, we have an ordinal relationship

696 between the k values representing the numerical numbers 1 to k. In our proposed approaches, we

697 encode this by adding appropriate relational edges between nodes representing different values in V.

698 In the binarized model, it is done for each variable separately, whereas, in the multi-valued model, it

699 is done in the RMPG. In absence of an explicit node for a value in this encoding scheme, it is not

700 clear how to represent such a relationship.

701 5 EXPERIMENTS


702 **Discussion on comparison with SAT Solvers: In this work, we are interested in creating (and**

703 learning) a neural solver for symbolic tasks, instead of using a symbolic algorithm like SAT solver.

704 Such an approach has many benefits, e.g., because of being differentiable, it can be used seamlessly

705 in a unified framework requiring both perception as well as reasoning, e.g. visual sudoku; neural

706 models have been shown to be resistant to varying amount of noise in the data as well, which purely

707 logical (SAT style) solvers may not be able to handle. As is the case with other papers in this line of

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

710 sizes of the value-set in train and test domains. Instead of comparing with an industrial SAT Solver,

711 perhaps a fair comparison would be with a generic state-of-the-art neural SAT solver e.g., CircuitSAT

712 (Amizadeh et al., 2019a), NeuroSAT (Selsam et al., 2019). Both of these papers observe that there is a

713 long way to go before they can compete with industrial SAT solvers. In fact, both of these approaches

714 experiment with much smaller problem instances. CircuitSAT uses a model trained on k-SAT-3-10

715 problems (k-SAT with 3 to 10 Boolean variables) for coloring graphs with number of nodes ranging

716 between 6 to 10, and achieves a meager 27% performance and NeuroSAT fails to solve any of the

717 problems in the coloring dataset used by CircuitSAT (section 5.2 in Amizadeh et al. (2019a)). On

718 the other hand, the smallest of the problems in our dataset has 40 nodes (GCP) and the largest has

719 25[3](= 25, 625) nodes (in 25 × 25 Sudoku), and hence we do not expect the generic neural SAT

720 solvers to scale up to our problem sizes.

Table 5: Dataset details

|Task|Train|Test|
|---|---|---|
||k #(Vars.) Mask (%) #(Missing Vars.)|k’ #(Vars.) Mask (%) #(Missing Vars.)|
|Futoshiki GCP Sudoku Sudoku finetune|6 36 28-70 10-25 4 40-100 28-70 12-70 9 81 58-79 47-64 24 576 30-70 173-403|{6,7,8,9,10,11,12} 36-144 28-70 10-93 {4,5,6,7} 40-150 28-70 12-105 {9,10,12,15,16} 81-256 30-68 47-148 {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,

723 Futoshiki, and Graph Coloring. In addition, we fine-tune our multi-valued model for Sudoku on 8000

724 puzzles of size 24 and test it on puzzles of different board sizes. Table 5 contains the details of both

725 train and test data for the different experiments. Below we describe the three tasks and their datasets

726 in detail.

727 **Futoshiki: We train our model on 6 × 6 puzzles, with the percentage of missing cells varying**

728 uniformly between 28 − 70%. We test our models on puzzles with board size ranging between 6 × 6

729 to 12 × 12, with the same percentage of missing cells. The number of ordering constraints is twice

730 the board size. To generate data, we first randomly generate a completely filled k × k board and then

731 randomly mask m% of the cells. We search for its all possible completions using backtracking to


-----

Table 6: Test Data statistics for all three tasks


**Futoshiki**

|k|#Puzzles #(Variables) #(Missing Variables) Mask (%)|
|---|---|



**GCP**

|6 7 8 9 10 11 12|4100 36 10-25 28-70 4091 49 14-34 29-70 3578 64 19-44 30-70 3044 81 24-56 30-70 2545 100 30-66 30-66 2203 121 36-82 30-68 1882 144 43-93 30-65|
|---|---|



**Sudoku**

|4 5 6 7|9102 40-150 12-105 28-70 9102 40-150 12-105 28-70 6642 40-120 12-84 28-70 3362 40-80 12-56 28-70|
|---|---|


|9 10 12 15 16 24 25|18000 81 47-64 58-79 2317 100 30-62 30-62 1983 144 43-84 30-58 1807 225 67-128 30-57 1748 256 76-148 30-58 1000 576 172-289 30-50 1000 625 187-314 30-50|
|---|---|



732 ensure that it has only one solution. Finally, we insert ordering constraints between 2k randomly

733 picked pairs of adjacent cells. The entire process is repeated by varying k and m to generate both the

734 test and train dataset.

735 The training data consists of 12, 300 puzzles on 6 x 6 board size with the percentage of missing

736 variables varying between 28 − 70%. The exact details of the testing data for different board sizes

737 are provided in Table 6. We note that it becomes increasingly difficult to find puzzles with unique

738 solution as the board size increases. Therefore, we are forced to reduce the maximum percentage of

739 masked (unassigned) cells with increasing board size.

740 **GCP: The training data for Graph Coloring Problem consists of around 25 thousand 4-colorable**

741 graphs with graph order varying uniformly between 40 − 120, and the percentage of unassigned

742 (masked) variables varying uniformly between 28 − 70% depending on the graph order. The exact

743 details of the testing data for different chromatic number (value-set size) are provided in Table 6.

744 To create non-trivial problems for the dataset, we always attempt to color graphs with the smallest

745 possible number of colors, i.e., the chromatic number of the graph. We follow Erd˝os–Rényi (ER)

746 model to generate random graphs. It takes number of nodes, n, and an edge probability, p, as input,

747 and adds an edge independent of the other edges with probability p. We note that to sample a graph

748 with n nodes and a given chromatic number k, we need to carefully adjust the range from which edge

749 probability p is sampled. The exact range from which p is sampled uniformly for each chromatic

750 number k and a range of nodes n is given in Table 7. We use a CSP solver (Perron & Furnon, 2019)

751 to determine the chromatic number of a given graph, which becomes a bottleneck while generating

752 graphs with higher chromatic number. As a result, we were not able to generate graphs with more

753 than 80 nodes for chromatic number 7, in a reasonable amount of time.

754 **Sudoku: The training data consists of 10 thousand 9 x 9 puzzles randomly selected from the dataset**

755 introduced in (Palm et al., 2018). For standard 9 × 9 board, we use the same test data as used in

756 RRN (Palm et al., 2018) [4]. The test data for the board-sizes between 10 and 16 is generated using

757 the methodology similar to Futoshiki. Instead of backtracking, solution validity and uniqueness is

758 checked through the GSS library (Pieters, 2019). The exact details of the testing data for different

759 board sizes are provided in Table 6. For the experiment where we fine-tune our models on 24 × 24

760 puzzles, both the train and test data for board size 24 and 25 are generated following the methodology


4Available at: https://data.dgl.ai/dataset/sudoku-hard.zip


-----

Table 7: Range for p for given k and n for GCP data generation

|a a a n a a a a a k a a|40-55 56-70 71-80 81-100 101-130 131-150|
|---|---|
|4 5 6 7|(0.1, 0.2) (0.05, 0.1) (0.05, 0.1) (0.05, 0.1) (0.02, 0.05) (0.02, 0.05) (0.2, 0.25) (0.1, 0.2) (0.1, 0.2) (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, 0.16) - (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

762 library as it doesn’t scale to such large sizes.

763 **Solution Multiplicity in GCP Dataset and larger board-size puzzles of Sudoku: An input query**

764 in GCP may have more than one solution, out of which only one is given at train time. But the

765 network may discover a new valid solution, and computing loss of the discovered solution w.r.t. the

766 given solution may unnecessarily penalize the model. To avoid this, we algorithmically verify if a

767 prediction is a valid coloring or not, and compute loss w.r.t. to this discovered solution, instead of the

768 given one. This is equivalent to solving a One-of-Many Learning problem (Nandwani et al., 2021)

769 with all possible colorings given at training time. The same phenomenon of solution multiplicity

770 exists for Sudoku puzzles of size 24 and 25, as verifying the uniqueness of puzzles on such large

771 board-size became computationally infeasible.


772 5.2 EXPERIMENTAL SETUP AND BASELINES

773 **Evaluation Metrics: We report two metrics: board accuracy and point-wise accuracy for all our**

774 experiments. In the former, we consider output of the model as correct only if it satisfies the

775 underlying CSP, whereas in the later, we give partial credit even for assigning some of the variables

776 correctly. We formally define it below:

777 **Pointwise accuracy: Let Yx be the set of possible solutions for an input x with k variables, and let ˆy**

778 be the model’s prediction. Pointwise accuracy of the prediction ˆy with respect to the solution y _Yx,_
_∈_

779 denoted as, PointAcc(y, ˆy), is defined to be the fraction of variables that match between the y and

780 **yˆ: PointAcc(y, ˆy) =** _k[1]_ _ki=1_ [1][{][y][[][i][] == ˆ]y[i], where 1 _._ is the indicator function.
_}_ _{_ _}_

781 Given above, we define pointwise accuracy for a predictionP ˆy of an input x with respect to a solution

782 set Yx to be the maximum among the pointwise accuracy with respect to each of the solutions in the

783 set Yx. Mathematically, PointAcc(Yx, ˆy) = maxy∈Yx _PointAcc(y, ˆy)._

784 For Sudoku and Futoshiki, since there is a unique solution, we can easily compute pointwise accuracy

785 as the target set Yx is singleton. For the GCP task, whenever the model returns a valid coloring,

786 pointwise accuracy is 1, otherwise, in the absence of access to complete Yx, we report a lower bound

787 by performing a local search, using Google’s OR-Tools [5], for a valid coloring closest to the model

788 prediction. Same is true for sudoku puzzles on 24 and 25 board size.

789 **Why care about point-wise accuracy? In our settings, the generalization problem can be hard,**

790 especially when there is a large difference between the sizes of the value-sets for the train and test

791 domains. Given that we are defining a novel task, and it is important to measure progress even when

792 problems are hard, we compare the two models using a simpler metric (pointwise accuracy) as well,

793 in addition to board accuracy. This additional metric can help us detect progress, and also compare

794 the relative performance of underlying models.

795 **Computational resources: All models are trained on K40 GPUs with 12 GB memory, available on**

796 an HPC cluster.

797 **Hyperparameters: The list below enumerates the various hyperparameters with a brief description**

798 and the values chosen.

799 1. Batch Size: For each task, we selected the maximum batch size that can be accommodated

800 in 12GB GPU memory. Refer to Table 8 for details.


5https://developers.google.com/optimization


-----

Table 8: Hyperparameters for different models and tasks

**Orthogonality** **Edge**
**Model** **Batch Size** **Weight Decay**
**Loss Factor** **Dropout**

**Futoshiki**

|MV BIN NLM15 NLM30|64 0.0001 0.01 0.1 16 0.0001 - 0.1 4 0.0001 - - 2 0.0001 - -|
|---|---|



**GCP**

|MV BIN NLM24|64 0.0001 0.01 0.1 16 0.0001 - 0.1 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** **Training Data** **# Gradient** **Time per** **Total Time**
**Model** **#Epochs**
**Size** **Size** **Updates** **Epoch (min)** **(Hours)**

**Futoshiki**

|MV BIN NLM15 NLM30|64 12,300 60,000 312 5 25 16 12,300 37,500 49 26 21 4 12,300 155,000 50 34 43 2 12,300 232,500 38 87 66|
|---|---|



**GCP**

|MV BIN NLM24|64 25,010 80,000 205 10 33 16 25,010 40,000 26 39 17 1 25,010 260,000 10 213 37|
|---|---|



**Sudoku**

|MV BIN|28 10,000 162,000 454 9 68 3 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

802 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
804 beddings for each value in the value-set, we add an auxiliary loss term, corresponding to

805 the total pairwise dot product of any two embeddings, before and after message passing

806 on the Relation Message Passing Graph (RMPG), _G[˜]. Its weight, α, was chosen amongst_

807 _{0.01, 0.1, 0.5} by cross validating on a devset for Futoshiki, and then fixed afterwards for_

808 all our experiments.

809 4. Edge Dropout: While collating the messages from the edges of the same type, we drop

810 10% of the messages, as done in RRN. Dropout is used in the Message Passing Graph

811 (MPG) of the binarized model, and the Constraint Message Passing Graph (CMPG) of the

812 multi-valued model.

813 **Model Averaging: As suggested in (Izmailov et al., 2018), to reduce the variance of our model**

814 performance, we take simple average of model weights stored at multiple points. All checkpoints

815 beyond a point when the learning curve flattened are selected for computing the average.

816 **Training Time: Table 9 enumerates the exact training cost, in terms of total training epochs, number**

817 of gradient updates, and clock time, for all three tasks and for both our models as well as the baseline


-----

818 NLM model. Note that while a multi-valued model may have fewer parameters, and results in a

819 much smaller graph and inference time for a given problem, its training time could still be higher,

820 especially in terms of total training epochs and number of gradient updates. However, because of its

821 memory efficiency, we can keep a much larger batch size during training, and because of its speed

822 efficiency, each update is much faster. As a result, the overall clock time comes out to be comparable

823 to the binary model for the two of our tasks, i.e. Futoshiki and Sudoku, and it is within 2x for GCP,

824 even though the number of epochs is much higher.


-----

