Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 

main_review: 

## Clarity
The paper has some minor issues regarding the presentation. While the visualizations are very helpful, I have the following suggestions for improvement:
     
- 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$).

- line 96 \& 97:  Using dotted and dashed lines instead of colors would resolve problems with printing in grayscale.

- Line 217 \& 2018: Potential typo: "train" instead of "validation .

- Equation 7: Potential typo: start index of the sum is $1$ instead of $0$.

- Section 5.1: I was unable to find the specification of the dataset in this experiment.



## Originality
The 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").

## Quality
I have multiple concerns about the quality of this paper:

- Fairness with respect to baselines: 

  - 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?
    
   - 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.

    - 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}$?

- Presentation of results:
    
    - Figure 5, 6 \& 7:
        - 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.
        - 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. 

    - Table 10: Reporting the runtimes for the solvers as well would be important for judging the runtime o the presented architecture.
    
    - 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.

## Significance
I 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.

While I believe that this is an interesting research direction, this paper does not meet the high standards of NeurIPS.
As 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.
limitations_and_societal_impact: Limitations as described in main review. No societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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.

The key contributions are:
1. Creation of new architecture for a neural net that solves combinatorial optimization problems (WeaveNet encodes two input matrices).
2. It is new that assignment problem, a type of combinatorial optimization problem, is solved by deep reinforcement learning.
 
Some technical comments are:
- 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.

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

- 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.
limitations_and_societal_impact: Yes, the authors have seemed to adequately address the limitations and societal impact of their work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 

Expermiental 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). 
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?

A 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. 

Quality: 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?

Quality. 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. 

Clarity: 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.)

Not 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. 

Significance: 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?

Significance. 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). 
limitations_and_societal_impact: Not applicable.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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).

My 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.

 Specific questions:
-	It seems WeaveNet consistently underperforms on the UD synthetic distribution. Is there any intuition on why this is the case?
-	How long does the training procedure take to run for WeaveNet? How does this compare to the runtime of traditional algorithms?


limitations_and_societal_impact: N/A
review_title: null

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