WeaveNet for Approximating Assignment Problems
Authors: Shusaku Sone
Jiaxin Ma
Atsushi Hashimoto
Naoya Chiba
Yoshitaka Ushiku
Venue: NeurIPS 2021 Submitted (2021)
Keywords: differential solver
assignment problem
stable matching

Abstract: Assignment, a task to match a limited number of elements, is a fundamental problem in informatics. 
Many assignment problems have no exact solvers due to their NP-hardness or incomplete input, and their approximation algorithms have been studied for a long time. However, individual practical applications have various objective functions and prior assumptions, which usually differ from academic studies. This gap hinders applying the algorithms to real problems despite their theoretically ensured performance. 
In contrast, a learning-based method can be a promising solution to fill the gap. To open a new vista for real-world assignment problems, we propose a novel neural network architecture, WeaveNet. Its core module, feature weaving layer, is stacked to model frequent communication between elements in a parameter-efficient way for solving the combinatorial problem of assignment.
To evaluate the model, we approximated one of the most popular non-linear assignment problems, stable matching with two different strongly NP-hard settings. The experimental results showed its impressive performance among the learning-based baselines. Furthermore, we achieved better or comparative performance to the state-of-the-art algorithmic method, depending on the size of problem instances.

WeaveNet for Approximating Assignment Problems
Anonymous Author(s)
Affiliation Address
email
Abstract
Assignment, task match a limited number of elements, is fundamental problem in informatics. Many assignment problems have no exact solvers due their NP-hardness or incomplete input, and their approximation algorithms have been studied for a long time. However, individual practical applications have various objective functions and prior assumptions, which usually differ from academic studies. This gap hinders applying the algorithms to real problems despite their theoretically ensured performance. In contrast, learning-basse method can be a promising solution to fill the gap. To open a new vista for real-world assignment problems, we propose novel neural network architecture, WeaveNet. Its core module. feature weaving layer, is stacked to model frequent communication between elements a parameter-efffcient way for solving the combinatorial problem of assignment. To evaluate the model, we approximated one of the most popular non-linear assignment problems, stable matching with two different strongly NP uarhard settings. The experimental results showed its impressive performance among the learning-based baselines. Furthermore, we achieved better comparative performance to the state-of-the-art algorithmic method, depending on the size of problem instances.
11
13
15
17
Introduction
18
From multiple object tracking to job matching, assignment problems can represent a wide variety of 20 applications. An assignment problem is typically defined on a bipartite graph, a graph with two sets
19
21 of nodes A and B with edges E = A x B (N- = |A], M = =B], N > M.. On the graph, the task
22 to find matching m {0, Ax (a set of edges represented as binary matrix) that satisfies
23 constraints and/or maximizes objectives. Depending on real-world scenes, there must be various
24 objectives and constraints for m. typical constraint a one-to-one correspondence (i.e., every node has at most one matched partner in m) and, for simplicity, we always assume it in this paper.
25
26 Matching stability is another example of such constraints. It is non-linear constraint first introduced for a hospital-student assignment problem (Gale and Shapley 1962) based on the preferences of
27
28 hospitals among students and vice versa. We say matching m unstable when there exist E A
and 6 E B which are unmatched in m (mas = 0) but both prefer each other more than their partner 30 in m. We can obtain stable matching m in ( by the Gale-Shapley (GS) algorithm (Gale and Shapley 1962). However, when m is expected to have the minimum difference in the total
29
31
32 satisfactions between sides A and B (known as sex-equal stable matching), the problem becomes
33
strongly NP- Kato 1993. McDermid and Irving 2014).
also face difficulties to obtain the best assignment when assignment candidates may randomly disappear (e.g., multiple object tracking with occlusions (Emami el al. 35
In addition to the NP-hardness
36
2020 or joint matching in multi-person pose estimation (Cao al. (017)). In such cases, need
strongly NP-hard subclass of NP-hard and considered more complex than general NP-hard problems
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

37
to compensate for the inputs of incomplete information by its stochastic properties. The traditional methods often use sub-optimal approximations to avoid solving complex assignment problems. A differential assignment model can be future option that enables end-to-end training for such applications.
38
39
40
41
Toward such future applications, this paper aims to propose an effective and promising differential solver for assignment problems. The contribution of this paper is four-fold:
42
43
1. We proposed WeaveNet, a novel neural network architecture for assignment problems and set-encoder, novel local structure.
44
45
2. We proposed novel technique, splir batch normalization, to deal with a strong asymmetry in imput distributions for sides and B.
46
47
3. We focused on stable matching, classical non-linear assignment problem actively studied even in recent years, and proposed a novel evaluation protoco with pseudo costs, which enables us compare learning-basse basedd solvers and algorithmic solvers directly.
48
49
4. We achieved better performance with the state-of-the algorithmic baseline when = 20, and a comparative performance when N = 30. We also outperformed any learning-based baselines with large margin.
51
52
2
Related work
53
54
Despite the recent research interest in deep learning technology, we hardly have a fully differential assignment solver. As long authors know, there are two past attempts solve assignment problems by a fully differential model. (019) has tried to solve stable matching by multiple layer perceptrons (MLP). Their contribution is the proposed relaxation of the non-lineat stability constraint to differential loss function. However, the MIP is too redundant to learn the assignment strategy without overfitting. In addition, the proposed auxiliary loss maintain the output to be one-to-one matching (symmetric doubly stochastic function) overly constrains the solution search space. In this study, we propose parfmeter-efficient differential model and weaker but sufficient constraint output one-to-one matching.
56
58
59
60
61
62
The second attempt is made by Gibbons et al. (2019), where Deep Bipartite Matching (DBM) is proposed. They tested their model with the weapon- target assignment (WTA) problem. WTA is a classical Na-hard problem whose solution when N < 20 in the experiment although there is no theoretical guarantee. In this sense, can consider WTT is empirically easier than sex-equal stable matching, for which have no such efficient solvers even for N = 5. In addition, DBM is trained in a supervised manner or with reinforcement learning, which is hard to apply to larger N. Furthermore, the implementation details 70 are not completely explained, and their dataset and source codes are not publicly available. Finally, and their local structure is sub-optimal. In this 72 study, we propose a more parameter-efficien two-stream architecture, WeaveNer, with a novel local structure, set-encoder, both of which have significant impacts on the performance.
64
algorithm (Ahuja al. 2007) could find optimal
66
68
69
71 the architecture of DBM is still garameter-redundaae
73
74 In addition to the above methods, it is natural to consider using graph convolutional networks (GCNs). However, there are GCN methods for assignment problems due to the over weerssmo problem (Li layer summarizes the output with neighhoring nodes, its smoothing effect eliminates expressive power for node classification. To avoid such elimination, GIN (Xu et al. 2019), the state-of ofth--ofthheart GCN method, stacks only two layers for node classification task. Such elimination is critical for assigmment-problem solver
76 er al. 2018 Oono and Suzuki 2020). Because any grapph-oonvolttions
77
78
80 because it needs to identify any slight difference through frequent communication among nodes.
81 Unlike GIN, our model retains edge-wise features rather than node-wise summaries, which does not
82 cause the smoothing problem. Therefore, we can make the model very deep, which any traditional graph convolutional networks cannot.
83
3 Stable matching problem a benchmark task
84
85
To evaluate learning-bast based assignment solvers, we adopt two strongly NP-hard variants of stable
86
matching. They have been actively studied for long time (Kato 1993 Iwama al. 2010 Dworczaki
2 The source code and datasets are included in this submission and will be publicly available.

---

87 2016
Gupta et al. 2019) and their state-of-the artt algorithm by Tziavelis et al. (2019) must be strong baseline against learning-base based methods. Hence, we set these two variants as the benchmark task for learning-based assignment problems.
86
An instance / of stable matching problem consists of sets of agents A and B bipartite graph. Fig. D illustrates an example of I. Each agent a, in A (0 < S. NN) has preference list p, 92 which is an ordered set of elements in B and p. = rank y p is the index of by in the list p. a;
91
93 prefers by to by if p poy.. Similarly, each agent bj in B(0 j s M) has preference list p/-
matching
pf (bg. b2
agents
stable matching
agents
pf
{ag, 02 }z
Group 4
Group B
(bg. b2
b
[a ag ag)
(b2, b1}
b3 (a. a2]
"the blocking pair ofm
Figure 1: An example of assignment, where m (black edges) is not stable due to the blocking pair (the orange edge), while m' (green edges) is stable.
94 For a matching m, we say that an unmatched pair fa,, bu (mew = 0) blocks m if a, 's partner by (Muj = 1) and bwos 's partner a; (M = 1) satisfy the conditions Pow poy and p < p Here, fae, bw) is called a blocking pair (the orange edge blocks matching of black edges in the figure).
97
matching is stable if (and only if) includes no blocking pair (the green edges in the figure). Note that I always has at least one stable matching, and the Gale-Shapley (GS) algorithm can find it in O ((2). However, the GS algorithm has a biased nature, where one side prioritized and the other
98
89
100
side only gets the least preferable result among all the possibilities of stable matching.
101
To compensate for the unfairness, can introduce diverse objectives to maintain stable matching fair. Among them, the following two objectives make the stable matching problem strongly NP-hard.
102
103
The first one is Sex equality cost (SEq) (Gusfield and Irving 1989). It focuses on the unfairness brought by the gap between the two sides' satisfaction and defined by
104
SEq(m; I) =)= PPmm; A) - P(m; B)),
P(m; A)
Σ PTj
P(m;
Σ
Pj
B
(1)
far,by tmm
(a Em
105
The other is Balance cost (Bal) Feder 1995
Gupta et al. 2019), which is a compromise between
side-equality and overall satisfaction. It is defined by
Bal I) max( A), P(m; B)).
(2)
In the proposed evaluation protocol, minimize either cost while maintaining stable one-to-one matching.
108
109
Input and output data format for stable matching Learning-based approximation is realized by 110 a trainable function F' that outputs a matching r E [0, 1] Nx which is an x M matrix. As for the input, the value range of the preference rank depends on the problem size, which causes range shift of the input distribution. To avoid such shift, we linearly re-scale the rank of preference
112
Piy (* {A, B)) from [1, N] to normalized score st ranged in (0, 1] to make it invariant to N,
114 where 1 for the highest rank. Then, we obtain the input as matrices S and SB where st is the
115 8j elemmntt S
Deep-learning- based fair stable matching with WeaveNet
116
117
4.1
WeaveNet
One of the required properties of F (SAA, 8B) + ra is to take all the agents' preference into
118
account when determining the presence of each edge in the output m. Li (2019) implemented this by
'The details of this linear re-scaling are based on Li 2019 and described in A.I Note that sections numbered
with capital letters appear in the supplementary material.
3

---

Input
Feature Weaving Layers (PW Layers)
Latent Features
Matching Estimation
s* (0.1 Moue
# of FW layers:
z W
IR
continuous
odge assignment
Conv(Lx))
1 + R69
5 [0.1)
set encoder E cooss-conentcnation
shortcut paths for the residual structure
hormalized
B2 MMN
z BRONND
preference lists
WeaveNet architecture. L feature weaving layers are stacked with shortcut paths to be deep network. The encoded features are fed into Conv(1 x 1) layer obtain logits (vi'', .n.). The output in will be binarized in prediction phase to represent matching.
Figure 2:
MLPs, where S and S are destructured and concatenated into single flat vector (with the length of 2NMM and fed to the MLP. Its output (a flat vector with the length of NM) is restructured into a matrix m. The MLP model, however, would face difficulties due to the following four problems.
121
125
(a) Preference lists of multiple agents are encoded by independent parameters, though they share a format so that we could efficiently process them in the same manner. MIP only supports a fixed-size input, so training different models for different cases of N becomes mandatory.
125
128
127
(c)
F should be permutation invariant, which mcans the matching result should be unchanged even if we shuffle the order of agents in S and S but MLP does not satisfy.
128
129
d) A shallow MLP model may be insufficient to approximate an exact solver for the NP-hard problem when N is large.
130
131
To address the above weaknesses of MLP, we propose the feature weaving network (WeaveNet) which has the properties of (a) shared encoder, (b) variable-size input, (c) permutation invariance, and (d) residual structure. The WeaveNet, as shown in Fig. 2 consists of L feature weaving (FW) layers. It has two streams of and B. a symmetric manner, each stream models the agent's act of selecting the one on the opposite side while sharing weights enhance the parameter efficiency. The shortcut paths at every two FW layers make them residual blocks, which allows the model to be as deep possible. We explain its details as follows.
132
134
136
encuder
zz
car(zz PartePPaen Prea
ZA
C10.S-COnee woos--ooncieenaiio
encoddrr E
Global
Raya
Coon
Mai
cat (7, Pa
2
Figure 3: Feature weaving layer orthogonally Figure 4: Illustration the process in set en- concatenates the weftwise and warpwize com- coder Es, where 2;" (colored in white) is once ponents (Z and Z in symmetric way
encoded to D' channel features (colored in pale blue), then max- max-pooled to obtain statistics in the feature set (colored in blue). The statistics in- formation is concatenated each input feature and further encoded (color a gradation).
(cross-concatenation) Then, the concatenated tensors are separated into 2/" (or 24-) which represents set of outgoing edges from agent a, (or by), and independently fed Ee.
138
Fig. 3 iillustrates the detail of single FW layer, which is the core architecture of the proposed network. FW layer is a two-stream layer whose inputs consist of a weftwise component Z and warpwise component z which are the output of (I 1)-th layer and Zí² S and Z S for the first layer. The two components are symmetrically concatenated in each stream (cross-concatenatiio)) Then these concatenations are separated into agent-wise features, each of which is a set of outgoing- edge features of an agent (indicating the preference from that agent to every matching candidate). These features are processed by the encoder E, shared by every agent in both A and B. As for an encoder that can embed variable-size input in a permutation invariant manner, we adopted the structure inspired by DeepSet (Zaheer et al. 2017) and PointNet (Qi et al. 2017 (Fig. which
139
140
141
142
143
145

---

147
consists of two convolutional layers with kernel size 1 and a set-wise max- sax-pooning layer, followed by nonbhioormalization and PReLU activation. We refer this structure as set encoder.
148
149
Mathematical formulations Z in Fig. 3 is a third-order tensor whose dimensions, in sequence,
150
corresponding the agent, candidate, and feature dimension, with a size of (N, M, D). Similarly, 2 8
151
has size of (M, N. D). The cross-concatenation is defined as
z = eat Z PA (Z()),
(3)
152
where PA+BB swaps the first and second dimensions of the tensor, and c
[1, Z2, ...] concatenates the features of two tensors Z1. Zz. Z is then sliced into agent-wiss wint features 2 and we obtain (E )00 < S N), which is also third-order tensor (and fed to the next layer). We can calculate 2 in symmetric manner (with the same encoder Ez).
153
154
After the process of L FW layers, Zí and ž are further cross-concatenated and fed to the matching estimator (in Fig. 2 It outputs a detemittriiii edge assignment m.. In the training phase, m is input an objective function, and the loss is minimized. In the prediction phase, the matching is obtained by binarizing m. In this sense, matching estimation through a neural network can be considered as approximation by relaxing the binary assignment space {0, 1) 1 into a continuous assignment space [0, 1|NxM.
157
159
160
161
Asymmetric variant with split batch normalization WeaveNet is designed to be fully symmetric F(5 54) This condition ensures
for S and 5 Hence, it satisfies the equation F(S that the model architecture cannot distinguish the two sides A and B innately. This property is beneficial when mathematically fair treatment between A and is desirable. However, when inputs from A and B are differently biased (e.g., the two sides have different trends of preference or the objective is asymmetric for A and B), this symmetric treatment degrades the performance. To further propose to a) apply batch normalization independently for each stream (split batch normalization), and b) adding a iideiidentifiable code (e.g.. for A and 0 for B) to Zo' and Z as a (D+1)-th element of the feature. We call this variant "asymmetric".
169
165
188
187
168
eliminate the bias difference without losing the paraamter-efffciennyy,
169
170
171
172
4.2
Relaxed continuous optimization for fair stable matching
Generally, combinatorial optimization problem has discrete objective functions and conditions, which are not differentiable. To optimize the model in an end-to-end manner without inaccessible ground truth, we optimize the model by relaxing such discrete loss functions into continuous ones.
174
176
Assume we target to obtain fair stable matching that has the minimum SEq, for example. Then, we have the following three loss functions.
177
178
F. conditions the binarization of m to represent a matching.
179
L. conditions the matching to be stable.
180
C minimizing the fairness cost SF. of the matching
181
The overall loss function is defined as
1 (M.calm) + +xyf(mm)).
Ltam (m) >m +
me (9))
where m = (mf and m softmax
183 An important advantage of learning- approximation is its flexibility. We can modify the above
184
loss functions to easily obtain other variants. For example, removing C, in Eq leads to standard
185
stable matching, and replacing C, with Lb (which minimizes Bol) leads to balanced stable matching.
188 as follows:
Lum (m)(m) Am
+
1
Σ AcC,(m),
(5)
me Am S)
Lism (m- = -vn 6m +
1
Σ
(m) + AsLo(m)).
(6)
2
me ( (m B)
5

---

187
One-to-one matching constraint mn can be safely converted into a binarized matching by column- wise or row-wise argmax operation when it is symmetric doubly stochastic matrix (L 2019). To
188
satisfy this condition, we defined f. with an average of the cosine distance as
(mn mn 1
(C(m*
m) C(m
C(m A))
1 N
m
m
C(m ,,
M
Im -
where mig means the i-th row of m This formulation binds m to be a symmetriq" doubly stochastic
190
matrix when Lm (m A, m () = O. The advantage of this implementation against the original one Li
191
192
2019) is described in B. with additional experimental results.
198
Blocking pair suppression
As for Ls, we used the function proposed in Li 2219). which
C. (m: = Σ
g(ay; bw m)g(bu: au m)
(v,w)EAxB
g bw m)
Σ myy max - -Sig.
(8)
by
g(b3 au m) =
Σ
m) max(S)
ju 5 0),
0, H.zav
194
where g(a;; bw. m) is a criterion known as ex-ante justified envy, which has a positive value when
195 a, prefers by more than any by in {byli * w. myg > 0}. This the same for g(by: On, m)) Hence, {a bw) becomes (soft) blocking pair when both g(a,; bw, m) and g(bw; a. m)) are positive.
196
197
Fairness measurements
Cy. Lo minimize SEq(m; I). Bal(m; I), respectively, and are defined as 1 N
1
Ly 1) = N IS(; A) - S(mn; B)1 ( I) = min(S( A), B)),
(9)
198
where
M
M N mas S 5(m; B) = Σ
S(m; A) Σ
Maj S
(10)
i=j
j=1 i=1
Experiments
199
We evaluated WeaveNet with different sizes of N. First, with test samples of N 10, compared its performance with learning-bast based baselines and optimal solutions obtained by a brute-force search. Second, compared WeaveNet with algorithmic baselines at N 20, 30, where neither existing learning-based methods nor brute-force search work. We also demonstrated the generalization ability of WeaveNet under the mismatched training/test dataset distributions. Third, demonstrated the
201
203
204
205
performance of WeaveNet at N 100. Note that we always assume M N hereafter.
Sample generation protocol In the experiments, used the same method Tziavelis al. (019 to generate synthetic datasets that draw preference lists from the following distributions.
207
Uniform (U) Each agent's preference towards any matching candidate is totally random, defined by a uniform distribution (0, 0, 1) (larger value means prior in the preference list).
209
210
Discrete (D) Each agent has a preference (1(05,, 1) towards certain group of [0.4N] popular candidates, while (1, 0.5) towards the rest.
212
Gauss (G) Each agent's preference towards i-th candidate is defined by a Gaussian distribution
(iiN, 0.4). LibimSeTi (Lib) Simulate real rating activity on the online dating service LibimSeTi (Brozovsky and Petricek 2007 based on the 2D distribution of frequency of each rating pair (p pR)
215
'Here (possibly non-square) matrix in (N 2 M) is symmetric if and only if ris M.i, (0 < <is M).

---

216 Choosing the above preference distributions for group A and B respectively. we obtained five different dataset settings, namely UU, DD, GG, UD, and Lib. We randomly generated 1,000 test samples and 1 1,000 validation samples for each of the five distribution settings.
217
Training protocol We trained any learning-based models 200k total iterations N S 30 and 300k at N = 100, with batch size of 8. We randomly generated training samples at each iteration based on the distribution of each dataset and used the Adam optimizer (Kingma and Ba 2015). We set
220
221
222
learning rate 0.0001 and loss weights A = 0.7, Am = 1.0, A A = 0.01 based on a preliminary experiment (see A.4)
223
224
Pseudo fairness costs for comparing learning-based results with algorithmic results Note that for learning- based methods, there is trade-off between fairesss scores and stable matching rate. Hence they may violate the constraints of stable one-to-one matching and yield an SEq or Bal even lower than the ideal value. To compare the methods fairly with traditional algorithmic methods, evaluate our methods using pseudo SEq (pSEq) and pseudo Bal (pBal) cost, in which the cost of
226
227
228
229
violation cases replaced by the worst result of the GS algorithm (prioritizing each side once and
230
adopting the worse onc).
231
5.1
Comparison with searning-base methods (NV = 3, 5, 7,
232
Baselines and ablations In this experiment, we show results obtained by following baselines and WeaveNet variants. MLP is the model proposed in Li 2019). GIN is the state-of-the-ar GCN model proposed in Xu et al. (2019). We use each (normalized) preference list as node feature and bipartite edges as the graph structure. After two graph-convolution calculations, as MLP, we destructed the node-wise embeddings and concatenated them into a single vector, which fed to one Linear layer to
234
236
output m. DBM is the model in Gibbons al. (211)). SSWN is the single-stream WeaveNet, which equivalent to DBM adopting the set-encoder of WeaveNet. WN the standard WeaveNet.
238
2:00
10.5
00.
1.50
3.00
DB56-1
- 01.
S0WN-18
DBXC-15
BRM
0.4
W/C-1
W3--5
7000
0.4
SSWNN
0..00
D6354
0.00
0.0
Agret
Ageet
Agent
Figure 5: Change of the suc- cess rates of stable matching (1) according to N
Figure 6: Change of pSS ideal scores (4) according to N.
Figure 7: Change of pBal- ideal scores (L) according to N.
239
Fig.
shows the success rates of finding a stable matching, where we trained models to minimize Eq. considering only the stable matching constraints. Since MLP and GIN have size-dependency.
240
241
we trained the models independently for N = 3, 5, 7, 9. The other models were trained with
242
layers (the model names are noted as XXX-6) to have a similar number of parameters with MLP for N 5 (see A.5 while
N 10 and tested on N 3, 5, 7, We maintained models with
243
244
WN- 18 is prepared to demonstrate the full performance (with the residual blocks).
245
MLP and GIN can hardly find stable matchings when N 2 5. Note that the number of total cases for size N instances is estimated by NN Hence, when N = 3, there are only 1,296 cases at most, and the test set will fully overlap with the training set. In contrast, when N = 5, we have 4.3 16 cases, and the overlap is negligible. Therefore, we can say that methods working only with = 3, such MLP and GIN, have little generalization ability.
246
248
250
DBM performs better than MLP but obviously worse than SSWN and WN. The performance gain of SSWN-6 over DBM-6 represents the advantage of the set-encoder. Similarly, the improvement of
252
WN-6 over SSWN-6 shows the benefit of the two-stream architecture. Finally, that of WN-18 over WN-6 demonstrates the impact of stacked layers on the performance. Fig. 15 of the appendix shows
7

---

254
some additional baselines, including a performance of our Lm against the original one proposed in Li 2019).
255
256
Figs. and 7 show pSE. and pBal (their difference from the ideal values respectively. XXX-18f/b We omitted MIP and GIN due to their poor performance in Fig. 5 In the results, both SSWN and WN largely outperformed DBM, which again proved the advantage of the set-encoder. WN performed better than SSWN for larger N, owing the parameter efficiency of the two-stream architecture. Note that the performance gain of XXX-18f/b
trained to minimize Eqs. + and 6 respectivel F
258
259
280
261
from XXX-18 proved the flexibility of general learning-bat -ased methods for customized objective functions.
262
5.2
Comparison with algorithmic methods (N- 20, 30)
264
As the algorithmic methods, we prepared four baselines. GS is the better result of applying the GS algorithm to prioritize each side once, which runs in O(N2). PolyMin minimizes some alternative fairness costs (the regret and egalitarian costs, which can be solved in O(N2) and O(N*), respectively
285
266
267
Gusfield 1987 Irving al. 1987 Feder 1992)) DACC by Dworezak (2016) is approximate algorithm that runs in O(N*). ). PowerBalance is the state-of-the-ar method that runs in ((N3).
268
WN- (N-600/b(20/30) is WeaveNet with L = 60 layers trained with samples of NN 20 and N 30. Note that we used the asymmetric variant for UD and Lib. Moreover, we do not involve any traditional braming-basedd methods in this part since they scored clear performance drops with increasing N (see and the problem size of N = 20, 30 is clearly beyond their capabilities, but an ablation with WeaveNet variants is reported in B
270
272
Fig. 5
Table Average SFq (1) and success rate of stable matching (t). Bold and underlined scores shows the best and second best ones, respectively.
Agents (N x M)
20 x 20
30 x 30
Datasets (Dist. Type)
UU
DD
GG
UD
Lib
UU
DD
GG
UD
Lib
GS
41.89
18.81
19.52
70.97
19.66
94.03
43.46
36.56
163.77
39.78
PolyMin
19.93
11.83
20.57
87.08
18.47
35.52
21.21
37.37
209.62
31.85
DACC
24.34
20.13
23.07
101.75
20.40
40.87
34.35
40.59
240.48
33.88
Power Balance
16.28
8.93
17.07
71.09
15.40
18.45
11.05
27.22
163.90
21.57
WN-60F(00) (pS
12.23
6.37
15.50
71.31
14.59
25.21
11.38
29.36
172.63
23.53
Stably Matched (%)
98.90
99.50
99.40
99.60
99.30
94.60
97.30
95.70
91.30
97.70
WN-60f(30) (pSEg)
12.16
6.53
15.56
71.34
14.53
18.30
10.52
27.39
170.35
22.17
Stably Matched (%)
99.10
99.40
99.40
99.50
99.80
98
99.00
98.00
93.90
98.60
Table 2: Average Bal (4) and success rate of stable matching (f).
Agents (N x M)
20 x 20
30 x 30
Datasets (Dist. Type)
UU
DD
GG
UD
Lib
UU
DD
GG
UD
Lib
GS
89.14
146.16
108.36
140.53
68.62
184.05
322.05
225.49
312.12
137.59
PolyMin
74.19
140.99
108.04
145.28
66.94
144.48
306.28
224.13
324.54
130.79
DACC
78.49
146.71
110.06
151.34
68.75
150.71
316.18
227.52
337.43
133.59
Power Balance
73.28
140.12
106.92
140.55
65.89
138.04
302.30
220.26
312.12
126.96
WN-60b(20) (pBal)
71.89
138.79
106.20
140.84
65.85
141.49
302.73
221.92
317.60
130.58
Stably Matched (%)
98.50
98.80
99.50
99.70
98.80
96.10
96.70
95.00
88.90
93.80
WN- WN-60b(30) (pBal)
72.33
138.75
106.65
140.79
65.84
140.40
301.59
223.02
313.59
127.93
Stably Matched (%)
98.00
99.10
98.60
99.80
99.10
97.00
98.60
93.70
98.80
98.00
274 We show the results in Tables|andd When N = 20, except for UD, the proposed method constantly performed better than any algorithmic methods for both SEq and Bal. When N = 30, they are comparative. For UD, GS performed even better than PowerBalance. That means that the ideal solution constantly prioritizes one side (a kind of the strongest bias). Since designed the WeaveNet architecture to treat the sides evenly, this is the most challenging situation for WeaveNet. Nonetheless,
278
277
278
$ $1.62, 2.534, 3.746, 4.694 in SEg and 2.406, 6.478, 11.956, 18.706 in Bal for N = 3, 5, 7, 9. We stoppe the training for DBM- at 80k due to sudden overfit after the epoch.
8

---

279
the proposed split batch normalization (with the side-identifiable code) achieved similar performance to GS and PowerBalance. We show the performance drop with the fully symmetric version in mB.22 of the appendix, which is also interesting from the ethical viewpoint. It is noteworthy that the model trained with N = 20 performs well even with N 30, which indicates that the method has generalizability for size difference.
280
282
284
Generalization ability for different distributions learning-based method should have a certain generalizability for input distribution shifts. To test the ability, we evaluated the performance of models trained with UU, DD, and GG on test sets of different distributions.
286
Table 3: The generalizability of WeaveNet (trained/tested with N = 30).
Table 4: Average SEq (L) and Bal (L) at N 100.
WN-60r
test
100 x 100, UU
SEq
Bal
train
UU
DD
GG
Avg.
GS PolyMin
1259.39
1709.53
pSEy Stably Matched (%)
18.30
25.81
29.09
21.10
153.35
952.85
UU
98.10
94,90
93.60
95.53
DACC
194.65
988.02
Power Balance
49.41
909.73
pSE2
171.27
10.52
77.36
86.38
DD
Stahly Matched (%)
2.80
99.00
0.10
33.97
Hunggaran
pSEg/pBal
257.99
1145.36
GG
PSEy
21.38
12.85
27.39
20.54
SEglBal
68.36
919.75
Stably Matched (%)
97.30
98.10
98.00
97.80
Stably Matched (%)
89.4
80.8
287
Table 3 shows the results. Remarkably, there is a contrast between the model trained with DD) and the others. The model with DD could hardly satisfy the one-to-one stable matching constraint when tested on UU/GG, and resulted in poor pSLg scores. In contrast, the model with GG achieved satisfying PSE scores on UU/DD. Since GG generates preference lists based on common preference score
288
289
290
281
(i/N for i-th agent) with noise, agents in GG tend to have similar preference lists (i.c., hard to assign optimally). model trained with such hard samples works well even for the test samples drawn from
292
293
other distribution. UU has also performed well owing to its non-biased sampling strategy. On the other hand, DD worst performed due to its highly biased generation strategy. From these results, we confirmed that WeaveNet has certain robustness in the distribution shift as long as training samples are competitive enough.
294
295
296
297
5.3
Demonstration with N- = 100
298
We further demonstrate the capability of WeaveNet under a larger size of problem instances, N = 100. In this case, we found that WN-80f and WN-80b failed to yield one-to-one matchings for 13.4%
289
300
and 19.8%, respectively (see the Table 9 in B 2 for details). To compensate for this problem, we applied the Hungarian algorithm (Kuhn 1955 to surely binarize m into a one-to-one matching. Table shows WeaveNet's 's relatively good SEg and Bal scores. Even with the help of the Hungarian algorithm, they were strongly penalized in pSEq and pBal due to the poor stable matching rate. In
301
302
303
304
other words, we can potentially fill the large gap by better constraining the output.
Since this work is just a pilot study toward practical differential assignment solver, there is still lot of space for improvement. The proposed test protocol with stable matching will facilitate it since we can freely adjust the difficulty of the problem to develop and enhance the methods continuously.
306
307
Conclusion
308
309
This paper proposed a novel differential assignment solver, WeaveNer, and an evaluation protocol on two strongly NP-hard variants of stable matching. In the experiments, we demonstrated the advantage of set encoder and the two-stream architecture of Weavenet against the other learning- based methods. These techniques also achieved a better performance than the state-of-the-art algorithmic method when N = 20 and comparative performance when N = 30. Furthermore, the asymmetric variants, split batch normalization with the iide-identifiable code, enabled the method to work even with the strongly biased dataset of UD. We also confirmed that the proposed method does not work at
310
312
314
316 N 100, which will be an immediate task for this new field of differential assignment solver. We
hope that this work becomes starting point to open vista for real- world assignment problems.

---

References
318
319
Ravindra K Ahuja, Arvind Kumar, Krishna C Jha, and James Orlin. Exact and heuristic algorithms for the weapon-target assignment problem. Operations research, 55(6): 136-1 146, 2007.
Lukas Brozovsky and Vaclav Petricek. Recommender system for online dating service. In Proceedings of Conference Znalosti 2007, Ostrava, 2007.
322
323
Zhe Cao, Tomas Simon, Shih-En Wei, and Yaser Sheikh. Realtime multi-person 2d pose estimation using part affinity fields. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), July 2017.
325
326
Piotr Dworczak. Deferred acceptance with compensation chains. In Proceedings of the 2016 ACM Conference Economics and Computation, pages 65-66, 2016.
Patrick Emami, Panos M. Pardalos, Lily Elefteriadou, and Sanjay Ranka. Machine learning methods for data association in multi-object tracking. ACM Computing Surveys, 53(4), 2020.
329
330
Tomás Feder. A new fixed point approach for stable networks and stable marriages. Journal of Computer and System Sciences, 45(2):233-255 284, 1992.
Tomás Feder. Stable networks and product graphs. American Mathematical Society, 1995.
David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69)1)-9115, 1962.
334
335
Daniel Gibbons, Cheng-Chew Lim, and Peng Shi. Deep learning for bipartite assignment problems. In Proceedings of IEEE International Conference Systems, Man and Cybernetics, pages 23 188- 2325, 2019.
337
338
Sushmita Gupta, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. Balanced stable marriage: How close is close enough? In Workshop Algorithms and Data Structures, pages 423-437, 2019.
Dan Gusfield and Robert W Irving. The stable marriage problem: structure and algorithms. MIT press, 1989.
341
342
Dan Gusfield. Three fast algorithms for four problems stable marriage. SIAM Journal on Computing, 16(1):111-128, 1987.
Robert W Irving, Paul Leather, and Dan Gusfield. An efficient algorithm for the "optimal" stable marriage. Journal of the ACM, 34())5322-43,, 1987.
345
346
Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa. Approximation algorithms for the sex- equal stable marriage problem. ACM Transaction on Algorithms, 7(1), 2010.
Akiko Kato. Complexity of the sex-equal stable marriage problem. Japan Journal of Industrial and Applied Mathematics, 10(1):1, 1993.
349
350
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of International Conference Learning Representations, 2015.
352
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
353
354
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for sepi-supe learning. In Proceedings of AAAI Conference on Artificial Intelligence, pages 3538-3545, 2018
356
357
Shira Li. Deep Learning for Two-Sided Matching Markets. Bachelor's thesis, Harvard University, 2019.
Eric McDermid and Robert W Irving. Sex-equal stable matchings: Complexity and exact algorithms. Algorithmica, 6853),54,-570, 2014.
360
361
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In Proceedings of International Conference on Learning Representations, 2020.
10

---

363
Charles R. Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas. PointNet: Deep learning on point sets for 3D classification and segmentation. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, July 2017.
364
Nikolaos Tziavelis, Ioannis Giannakopoulos, Katerina Doka, Nectarios Koziris, and Panagiotis Karras. Equitable stable matchings quadratic time. Proceedings of Advances in Neural Information Processing Systems, pages 457-467 2019.
367
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In Proceedings of International Conference on Learning Representations, 2019.
370
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets, In Proceedings of Advances in Neural Information Processing Systems, volume 30, pages 3391-3401, 2017.
372

---

Checklist
374
375
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contri- butions and scope? [Yes] The experimental results Section 5 correspond to the main claims, which are summarized as the contribution list in Section II
377
379
(b) Did you describe the limitations of your work? [Yes] Our method works best among any baselines when N - 20, comparative to the state-of-the-art algorithmic baseline when N = 30, but poorly when N = 100. See Section 5.3
380
381
382
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We briefly discussed the fairness/unfairness achieved by our method in the paragraph "Asymmetric variant with split batch normalization" in Section I. Namely, the asymmetric variant can better optimize the objective than the symmetric one (which ensures mathematically equal treatment for sides A and B) but harms the equal treatment of the two sides.
384
386
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? 387
388
[Ys]]
3.92.
If you are including theoretical results...
390
(a) Did you state the full set of assumptions of all theoretical results? [N/A] We have no main
391
theoretical results. The only theoretical discussion is for the computational cost of WeaveNet in whose assumption is the network shape explained in the paper.
(b) Did you include complete proofs of all theoretical results? [N/A] We have no main theoretical results. The only theoretical discussion is for the computational cost of WeaveNet in A.2 where
394
we provided enough detailed explanation as proof.
39633
If you ran experiments...
387
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] We have included it in the supplemental material.
398
389
400
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We described the training details in Section "Training protocol" and Section
401
403
Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] We presented figures with the error bars in Section A.4 of the appendix, which demonstrated the stable behavior of the proposed method against the random seed. For
404
405
408
the other part, we have multiple settings, and we observed a stable trend in the results.
407
(d)
Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We described it in the appendix, Section C
408
4094.
If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section C in the appendix. Did you mention the license of the assets? [Yes]] See Section
412
Did you include any new assets either in the supplemental material or as URL? [Yes] We provides code to random-generate the problem instances, which contains no personal or any other sensitive information, but only the distribution parameters of the LibimSeti dataset.
414
415
(d)
Did you discuss whether and how consent was obtained from people whose data you're rre using/curating? [Yes] See Section C
417
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] See Section C
418
4195.
you used crowdsourcing or conducted research with human subjects...
420
(a) Did you include the full text of instructions given to participants and screenshots, applicable?
[N/A] We used neither crowd-sourcing nor human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB)
423
approvals, if applicable? [N/A]
424
Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
425
12


Reviews:
[{"review_id": "QJv1MT47bH", "reviewer": "Reviewer_EJfv", "summary": "This paper proposes a learning-based algorithm to tackle assignment problems, which have traditionally used approximation algorithms to solve. The paper details WeaveNet, a novel neural network architecture which includes three techniques of set-encoder, split batch normalization and feature weaving layer, to efficiently solve the NP-hard combinatorial problem. Experiments show competitive results compared to other learning-based algorithms.", "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": "Overall, the paper is clear and details the technical contributions of WeaveNet’s architecture and capabilities in handling flexible inputs. Experiments demonstrate that WeaveNet is the strongest algorithm compared to other learning-based algorithm baselines. Experiments also show the empirical improvements of each novel component of WeaveNet (set-encoder, two-stream architecture) and why these changes are necessary. WeaveNet’s deterioration in performance (in % stable matches and fairness) compared to traditional algorithm baselines for $N=100$ indicates that there could be limited scalability as $N$ increases (Table 4).\n\nMy main concern is how asymmetry (the case where $N \\neq M$) affects the fairness objectives and is not included in experimental results.  The fairness objectives (Eqn 1 and 2) seem intuitive for the case where $N = M$, but not as intuitive when inputs are not equal in size. If I am interpreting the metric correctly, for the case where $N >> M$ and preferences are uniformly generated, it is natural that all $b\\in B$, where $|B| = M$ are matched because and only highly preferred $a\\in A$ where $|A| = N$ are matched. As a result, there could be a natural \"skew\" in the metrics that arises from this asymmetry and not unfairness: $P(m; B)$ is much larger than $P(m; A)$. Related to this, the experiments only show results for the case when $N=M$. Is this a limitation of the architecture or optimization process? It would be helpful for the authors to address these two points.\n\n Specific questions:\n-\tIt seems WeaveNet consistently underperforms on the UD synthetic distribution. Is there any intuition on why this is the case?\n-\tHow long does the training procedure take to run for WeaveNet? How does this compare to the runtime of traditional algorithms?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "PTAtK1TbPD", "reviewer": "Reviewer_nn6T", "summary": "The paper is about WeaveNet, a neural architecture, specialized to solve assignment problems that are NP-hard. Feature weaving layer, the key technical contribution by WeaveNet, is stacked to model frequent communication between elements for solving the combinatorial assignment problem. In particular, set encoder and the two-stream architecture of Weavenet achieve a better performance than the state-of-the-art algorithmic method. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 essence of the paper, hence the bottomline of what WeaveNet solves, is matchmaking. Simply put, imagine there are two groups, and members in each group want to be match-made to members from the other group. The matchmaking preference is described by an MxN matrix, and for two groups, the two matrices as an input are fed into WeaveNet. The input matrices are encoded and used to solve a combinatorial optimization problem.\n\nThe key contributions are:\n1. Creation of new architecture for a neural net that solves combinatorial optimization problems (WeaveNet encodes two input matrices).\n2. It is new that assignment problem, a type of combinatorial optimization problem, is solved by deep reinforcement learning.\n \nSome technical comments are:\n- The WeaveNet neural architecture is kind of new, and it solves really well when the degree of input complexity (say, N=20,30). For larger N, WeaveNet does not really generalize better performance gain for smaller N.\n\n- Assignment problem is not solved by neural combinatorial optimization. Applying deep RL for new combinatorial optimization problems is a great attempt. The problem solved by WeaveNet, however, is limited.\n\n- It is formulaic that the two input matrices are always encoded. For more general problems that require one matrix or three matrices as an input, WeaveNet is applicable to a narrow limited class of problems.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have seemed to adequately address the limitations and societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "KuWwW7Wq9A8", "reviewer": "Reviewer_wb66", "summary": "The authors propose a learning-based fully differentiable architecture for assignment problems. The core module *feature weaving layer* consists of a *cross-concatenation* module and a *set-encoder*, modeling communication between the nodes. It can be stacked multiple times through the use of skip-connections, resulting in a deep network that is able to handle varying problem-sizes as input. The architecture is tested on two versions of the stable matching problem and compared against both learning-based and algorithmic baselines. \n", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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\n## Clarity\nThe paper has some minor issues regarding the presentation. While the visualizations are very helpful, I have the following suggestions for improvement:\n     \n- Line 94: In $m_{vw}=0$, $m$ is used as a matrix, but in the equation following line 104 it is used as a set ($\\{a_i,b_j\\}\\in m$).\n\n- line 96 \\& 97:  Using dotted and dashed lines instead of colors would resolve problems with printing in grayscale.\n\n- Line 217 \\& 2018: Potential typo: \"train\" instead of \"validation .\n\n- Equation 7: Potential typo: start index of the sum is $1$ instead of $0$.\n\n- Section 5.1: I was unable to find the specification of the dataset in this experiment.\n\n\n\n## Originality\nThe architecture design incorporates some novel ideas such as the *cross-concatenation* and *split batch normalization*, while also using known techniques (general structure of the architecture is taken from DBM, the *set-encoder* is \"inspired by DeepSet and PointNet\").\n\n## Quality\nI have multiple concerns about the quality of this paper:\n\n- Fairness with respect to baselines: \n\n  - Line 70: \"the implementation details are not completely explained\". As DBM serves as a baseline later on, is this a reimplementation of DBM based on incomplete information? What exactly is missing?\n    \n   - Line 505: Only using two layers in a graph neural network massively limits its expressivity (oversmoothing indeed can be a problem, however, there exist various new techniques to reduce this problem). An ablation using more layers for the GNN would be useful in any case.\n\n    - Line 470: Why is there a procedure for first fixing $\\lambda_m$? The hyperparameters $\\lambda_{m/s/f/b}$ only have meaning up to an arbitrary scale depending on the learning rate, so why not just immediately start out with $\\lambda_m=1$ and then finetune $\\lambda_{s/f/b}$?\n\n- Presentation of results:\n    \n    - Figure 5, 6 \\& 7:\n        - The scale in this figure (subtracting the ideal values) is misleading in my opinion, overstating the significance of the improvement. E.g. in figure 7 for an agent size of $9$x$9$ the $0.25$ performance gain is not a \"large margin\" [line 52] when compared to the ideal value of $18.706$. I would suggest not subtracting the ideal value and instead reporting the ideal values as an optimal line in the plot.\n        - Why is there a comparison to DBM-18 in Figures 6 \\& 7? It is not reported in figure 5. I would suggest reporting all methods from figure 6 \\& 7 also in figure 5 (including the XXX-18f/b), as the success rate of stable matchings is crucial in judging the meaningfulness of the pseudo-scores in figure 6 \\& 7. \n\n    - Table 10: Reporting the runtimes for the solvers as well would be important for judging the runtime o the presented architecture.\n    \n    - Random restarts: Errorbars are only reported for the hyperparameter-tuning in Fig 10-13. This would be more important for the main results (at least for the smaller problem instances), in which no statistics are reported.\n\n## Significance\nI do not think that the presented work in its current stage is very significant. While the idea of fully differentiable solvers is interesting especially in the case when the solver is part of a larger architecture (e.g. for feature extraction before the solver), this is not the focus of this paper. Instead, the main focus is training the architecture to improve upon the existing approximate solvers. While the results show that the architecture does not perform worse than the baseline solvers, by themselves they do not provide strong enough evidence that this architecture would perform much better than an algorithmic solver in a new setting, as in many of the experiments, the improvement upon the SOTA solver Power Balance is non-existing or very small.\n\nWhile I believe that this is an interesting research direction, this paper does not meet the high standards of NeurIPS.\nAs a suggestion for future research, I believe that employing this architecture in a larger end-to-end trainable pipeline could make full use of the differentiability in order to produce significant results. One potential application for this could be multi-object tracking from image input.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations as described in main review. No societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "-UAoaLrbRKI", "reviewer": "Reviewer_PXDn", "summary": "This paper provides a differential approach to solve matching problems. Since matching is a highly combinatorial problem, two main elements must be provided for approximating such an NP-hard problem: permutation invariance (PI) and variable-size inputs (VS). Both elements are borrowed from PointNet and Deep Sets as follows. In the first \"weaving\" layer,  the matching preferences of both agents (eg. men and women) are weaved so that for each row of men (women) preferences we stack the women (men) preferences. Each  men-women and women-men weaving is independently fed into a set encoder which basically relies on 1D-convolution + max-pooling. Convolution (dot product when we have 1D convolution) provides a universal space where all men-women (women-men) sample pairing will be projected so that a given test problem can be solved. Solving a problem means to map it to a solution code. In this regard, given the latent features (after L Weave-layers), the last convolution must be learnt before  softmaxing. \n\nExpermiental results show that the chosen (two-streams) architecture outperforms the state-of-the-art alternatives, including non-differtial methods for N close to 30. However, the proposed method does not scale for N=100 (even with the help of the Hungarian method for constraining the output). ", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "Originality: Are the tasks or methods new? Is the work a novel combination of well-known techniques? (This can be valuable!) Is it clear how this work differs from previous contributions? Is related work adequately cited?\n\nA bit original, what is more novel is the two-stream architecture. It is clearly the best choice for small problem sizes (N=3, 5, 7, 9) when many of the alternatives decay exponentially in performance. For N=20, 30 the proposed architecture is still competitive. \n\nQuality: Is the submission technically sound? Are claims well supported (e.g., by theoretical analysis or experimental results)? Are the methods used appropriate? Is this a complete piece of work or work in progress? Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?\n\nQuality. Moderate. Although the complementary stuff contains ablation studies etc, this reviewer does not identify a explanatory approach in terms of showing, for instance, how the weaving leads to find a code after (in general L = 2N) layers. Ok, I know that each layer is doing part of the job in terms of permutation invariance, as it happens for instance in PointNet. However, the authors should stress what are the \"critical points\" (critical lists of choices in this case). The answer to this question is partially given in the sythetic experiments (distributional choices), but the authors are loosing a golden chance to dig more in the need of more or less layers attending to how difficult is the problem in a principled way. \n\nClarity: Is the submission clearly written? Is it well organized? (If not, please make constructive suggestions for improving its clarity.) Does it adequately inform the reader? (Note that a superbly written paper provides enough information for an expert reader to reproduce its results.)\n\nNot so clear. For instance, no explanation is given about the VS inputs. Regarding the weaving process, they should remark that a row of an agent is mixed with those of the other agent in column form. \n\nSignificance: Are the results important? Are others (researchers or practitioners) likely to use the ideas or build on them? Does the submission address a difficult task in a better way than previous work? Does it advance the state of the art in a demonstrable way? Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?\n\nSignificance. They are relatively important insofar they tell the community that for moderate values of N, deep learning can deal with an NP-Hard problem. However, as it is well known that the approximation of this problem via  making it continuous suffer from plateaus in the cost function, no insight is given in terms of how good is the deep learning approach (what are its limits and, specially, why). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable. ", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours "}, "extra_text": {}}]

Author rebuttal:

Meta-review: Even though the reviewers appreciated certain aspects of this paper, they raised multiple issues such as the scalability to larger graphs and misleading figures that were not resolved by the authors' response. Due to those issues, this paper does not meet the bar for acceptance at neurips.
Decision: Reject