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) =)= PP(m; 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 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
C10.S-COnee wooss-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 wine 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-6
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 (1).
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 3548, 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": "v-GHwSPUQDn", "reviewer": "Reviewer_a437", "summary": "The paper proposes a novel neural architecture, named WeaveNet,  for solving the stable matching problem with fairness constraints such as sex-equality cost, or balance cost. \nNotably, the stable matching problem can be solved using the GS algorithm in O(N^2) time, but adding the fairness constraint makes it NP Hard.\nWeaveNet is trained in an unsupervised fashion using loss terms that approximate the stability and the fairness cost using differentiable functions and continuous relaxation of the assignment matrix.\nTo demonstrate the superiority over other neural methods (DBM, GIN, and MLP), they experiment with small problem instances (N <= 9), where exact solutions can be found easily\nTo compare with heuristics, they experiment on bigger problems (N = 20, 30) and show the competitiveness of WeaveNet.\nThe proposed architecture is not able to scale for problems with much bigger size (N>=100) whereas previous works using heuristics, such as PowerBalance, experiment with problem instances up to  N = 4000.\n\n**Contributions:**\n1.  First neural architecture, for matching problems, that is competitive with heuristics, at least for smaller instances (N<=30).\n\n2. Achieves problem size invariance by using the Permutation invariant set encoder.  GNN based architecture (GIN) fails to achieve this.\nUses unsupervised loss functions.\n\n3. Thorough experimentation, comparing with both, other neural methods, as well as heuristic-based methods.\n", "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": "**Novel combination of well known techniques for a task with only a couple of existing learning based solutions:**\n\nThe task of equitable matching is a very well studied NP Hard problem, and recently a couple of learning based methods have been proposed for it. This paper proposes a new architecture, WeaveNet, that improves upon the existing DBM architecture. Specifically, it uses 1. Set encoder to achieve permutation invariance, and 2. Cross connection, which makes the solution symmetric.\n\nThe related works section clearly places the work w.r.t the existing learning based methods.  It would be good to have a paragraph on heuristic based methods as well, discussing their pros and cons w.r.t the proposed method, e.g. scalability, speed of inference etc. \n\n\n**Quality:** The experimentation is thorough and addresses both the pros and cons of the proposed methods. The proposed architecture is an improvement over the existing neural method, which is demonstrated through proper ablation in the experiments.\n\n\n**Clarity:** It's an easy-to-read paper, even for readers who may not very well know the underlying task handled. \n\n\n**Significance:** the proposed architecture is novel, but, like other learning-based methods,  it doesn’t guarantee even a stable one-to-one matching, which can be a major bottleneck in its application. Otherwise, when compared against other learning based methods, the results are significantly better.\nAlso, it is not clear why one would use WeaveNet, when existing heuristic based methods, such as Power Balance scales much better and work even with N up to 4000.  \n\n**Questions/comments for the authors to address:**\n\n1. Even one to one matching is not guaranteed by the current architecture, unless Hungarian algorithm is used for matching. Is it possible to train the method with the Hungarian algorithm for inference while training? What would be an appropriate loss function for it?\n\n2. Even if we use Hungarian algorithm to ensure one to one matching, the stability is not guaranteed, whereas the existing algorithms ( GS or PowerBalance) at least ensure stability. Is it possible to somehow exploit the existing cheap heuristics? For example, by using the output of Powerbalance as a supervised target initially, and then minimizing the loss which assigns very high weights to L_m and L_s (so that the stability is not lost) and the fairness loss term (L_f/ L_b) is minimized further?\n\n3. Can we use gradient based inference to ensure one-to-one and stable matching? I.e. during test time, for each problem instance, further fine tune the trained network weights, (\\Theta*) by minimizing the unsupervised loss for that test instance only [Lee et al, 2020] \n\n4. Experiments are done only on toy sizes. The other heuristic based methods, work for N as large as 4000, e.g. PowerBalance. So its not clear under what circumstances one would prefer a learning based method over heuristics.\n\nI will be happy to increase the rating if my concerns/questions are addressed in the rebuttal.\n\n\nLee et al. 2020: Gradient-based Inference for Networks with Output Constraints. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "IoskuIKvrYV", "reviewer": "Reviewer_cFCG", "summary": "In the assignment problem, the task is to match groups A and B when each member of A has a preference list of candidates from B and vice versa. The paper aspires to learn fully differentiable surrogate solver (WeaveNet) for stable matching assignment (also known as ‘stable marriage’) problem minimizing either ‘Sex-equality’ or ‘Balance’ cost objectives that balance the total ‘happiness’ of both groups. This problem is known to be NP-hard, and approximate solvers are available. The authors design a network architecture and compare its performance against an MLP, one GCN, a deep bipartite matching (DBM) architecture, and an approximate solver.", "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": "The paper is difficult to read, poorly motivated, badly structured, and contains many vague or inaccurate claims. The assignment problem is not explained earlier than on page 3. The motivation comes from the claim that despite assignment problems have been studied for a long time, and approximate solvers are available, individual practical applications differ from academic studies. Unfortunately, not a single example is provided. The authors then call for filling this gap by designing a surrogate solver for ‘new, real-world assignment problems’ and show its performance on four synthetic and one real-world dataset.\n\nWe can read that “Despite the recent research interest in deep learning technology, we hardly have a fully differential assignment solver.” A possible reason is that it was not needed. Not everything has to be done only because it is viable. Also, the sub-optimality of the solvers is criticized (l37, 38) but seems inherently inevitable (see, e.g. [1, 2]), and the same applies to DNN. Incorporating solvers into NN architectures is a well-established topic in ML, though, and it should be mentioned. Classical relaxing/softening is one way; recent efforts to employ non-differentiable solvers are also notable. \nThe often-mentioned novelty of the architecture is questionable. For instance, the relation to DBM is not properly described. In the related work section, the authors claim that its implementation details are unclear, and the code is not available. However, in the experiments section (p7, l237), there is a clam “SSWN is the single-stream WeaveNet, which is equivalent to a DBM adopting the set-encoder of WeaveNet”. Does it mean that WeaveNet is basically designed as DBM and only the set-encoder is new? Also, it seems that the authors run the DBM experiment (deducing from the code in the suppl. mat.), which contradicts the earlier statement. The sentence “The performance gain of SSWN-6 over DBM-6 represents the advantage of the set-encoder” also supports my suspicion. \nNext, there are flaws in the experiments. The authors claim that they randomly generate 1,000 test and 1,000 validation samples. Assuming they mean train/test, there is no validation set inaccessible during the training mentioned. Restarts and errors are also not reported (except for a preliminary experiment in the appendix). In Fig. 6 and 7 (comparison to other learning-based methods), the differences from the ideal values are reported instead of the values, making the results looking better. In fact, the relative difference between all models for pBAL is around 3% (the absolute value is in the footnote on the next page, no error bars)! The runtimes for the baselines are missing and for WeaveNet vary from 10-111 hours on a single Tesla V100 GPU. \nDespite not being trustworthy, the comparison to the solver looks good. Under some conditions, the WeaveNet is on par with the approximate solver ‘Power Balance’ (the others are irrelevant as they optimize other costs). This does not mean that ‘WeaveNet learns assignments’ as it is sensitive to the dataset distribution and is potentially sensitive to the shift of the statistics on the test set as correctly shown in the second experiment. Thus, WeaveNet can be particularly useful (and even better) in the domain where this shift is improbable. This can be a relevant contribution but should be fairly explained without exaggerating.\n\nDespite my criticism, the work may be of interest to some specialized researchers, and I fully agree with the authors that “…there is still a lot of space for improvement” (l305). The approach to the problem is more or less standard and does not move the ML knowledge forward. Even if it works, it does not mean that it has value for the field.\n \n[1] P. Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008\n[2] J. Thapper and S. Živný. The limits of SDP relaxations for general-valued CSPs. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017\n \n \n### Questions/Suggestions\n* Consider extending the paper with various cost functions. This would cover other assignment problems, maybe more applicable, where it has applications, more related work, datasets, and may also attract a wider audience.\n* “one-to-one correspondence (i.e., every node has at most one matched partner in m)” does not seem to be correct.\n* footnote 1: No footnote is better than this vague one\n* l68, 69: “DBM is trained in a supervised manner or with reinforcement learning, which is hard to apply to a larger N” I do not understand. WeaveNet is also trained in a supervised manner.\n* l174: “end-to-end” is misused. This would mean that NN extract features (preferences) from raw data (dating site profiles, for instance) AND feeds the WeaweNet during training.\n* l119-130: In combinatorial optimization and ML, a poor generalization ability of MLP is not surprising. It is not necessary to devote so much space to it.\n* Why do you focus so much on parameter efficiency?\n* “WN performed better than SSWN for larger N, owing to the parameter efficiency of the two-stream architecture.” which experiment supports this?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "HmEAG0VTvkD", "reviewer": "Reviewer_t5vd", "summary": "The paper proposes WeaveNet, a neural network architecture to approximately find stable matchings that minimize one of two objective functions related to fairness (\"sex equality cost\" and \"balance cost\"). WeaveNet has two symmetric streams, one for each side of the matching, to model each agent's decision regarding the other side. These streams cross-concatenate at each layer and go through a shared set encoder, which allows for variable-size input and makes the model permutation invariant. The model also contains residual structure to facilitate deeper networks. In addition, the authors propose an asymmetric variant for objectives that benefit from distinguishing from both sides. The binarization, matching stability, and objective cost are handled by the loss function. Their approach performs significantly better than all other learning-based methods they compared it to, and is close to or better than the algorithmic methods compared. The paper includes experiments on generalization ability on different distributions and for a larger problem size.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper contains a significant contribution to the area of learning-based methods for stable matching and it is overall both well-written and detailed in its experimental evidence. The proposed architecture is interesting and its components make sense given the problem being solved. In particular, I appreciated how the paper points out specifically which parts were designed to address each weakness from previous architectures, which helped me understand why this architecture can perform better than previous ones. I do not have a background on stable matchings, but as far as I can tell, the paper does a decent job at addressing related work and the architecture appears to be novel.\n\nThe experimental setup is reasonable and I am glad to see that the experiments are reasonably detailed. Besides having five different distributions (one of them real-world-like) and comparisons to several baselines, it includes generalization results and a result on larger instances in which the method does not perform as well, plus a number of ablation tests in the appendix. The experimental results are sufficiently convincing for me that this method advances the state-of-the-art in learning-based methods for stable matching, even if the performance is not sustained in large instances. The appendix contains training and evaluation time, which I felt that there was little emphasis on, and the main text could at least bring it up and refer to the appendix. I would also suggest including solve times for the algorithms for comparison purposes.\n\nI have a number of minor comments, but I am otherwise satisfied with the publication of this paper in NeurIPS:\n\n1. In line 187, the paper states: \"$\\hat{m}$ can be safely converted into a binarized matching by column-wise or row-wise argmax operation when it is a symmetric doubly stochastic matrix (Li, 2019).\" This may be a basic question, but it is unclear to me why this is true. Given that Li, 2019 is a thesis, I could not quickly find an answer to this question. For example, take the matrix: [[0.3, 0.4, 0.3], [0.4, 0.6, 0.0], [0.3, 0.0, 0.7]]. In both rows 1 and 2, the argmax is 2, so the result is not one-to-one. What am I missing? Whatever is the issue with my understanding, this should be clarified in the paper.\n\n2. During most of my reading, it was not clear to me that this method does not guarantee a stable matching, and only inferred that late in the text. I suggest discussing this in the Introduction.\n\n\nThe rest are editing comments:\n\n3. Line 110: It is useful for the reader to know early how the continuous output will be converted into a matching.\n\n4. Figure 3 caption: Typo: \"warpwize\" -> \"warpwise\".\n\n5. Line 181: I suggest writing $\\mathcal{L}_m(\\hat{m})$ to make its dependence on $\\hat{m}$ clear.\n\n6. Line 191: Clarify here what happens when $\\mathcal{L}_m $is not zero.\n\n7. Line 193: Typo: $L_s$ -> $\\mathcal{L}_s$.\n\n8. Line 268: PowerBalance is missing a citation.\n\n9. Section 5.3: Could you clarify that this is trained on N = 100 as well?\n\n\nI have a final minor question: do you believe there is a way to combine this learning-based method with an algorithmic method to convert the output of the learning method into a stable matching? This would be interesting to explore.\n\n---\n\nEdit: I have decreased the score from 7 to 6. Please see my comment below.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Fairness in general was discussed in the paper in the context of matchings.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper tackles an important problem, and gets the scientific community closer to obtain an efficient deep-learning based approach for it. That being said, the reviewers feel the overall condition of the paper requires more work. The existing art should be better represented (e.g. comparison to DBM) and experiments better explained.  Although the results have potential, it seems that there is too much to be done in order for this version of the paper to be accepted to NeurIPS.
Decision: Reject