Traditional set prediction models can struggle with simple datasets due to an issue we call the responsibility problem. We introduce a pooling method for sets of feature vectors based on sorting features across elements of the set. This can be used to construct a permutation-equivariant auto-encoder that avoids this responsibility problem. On a toy dataset of polygons and a set version of MNIST, we show that such an auto-encoder produces considerably better reconstructions and representations. Replacing the pooling function in existing set encoders with FSPool improves accuracy and convergence speed on a variety of datasets.
Decoder: This turns the latent space back into a set. The elements in the target set have an arbitrary order, so a standard reconstruction loss cannot be used naïvely -the decoder would have to somehow output the elements in the same arbitrary order. Methods like those in Achlioptas et al. (2018) therefore use an assignment mechanism to match up elements (section 2), after which a usual reconstruction loss can be computed. Surprisingly, their model is still unable to solve the polygon reconstruction task with close-to-zero reconstruction error, despite the apparent simplicity of the dataset.
In this paper, we introduce a set pooling method for neural networks that addresses both the encoding bottleneck issue and the decoding failure issue. We make the following contributions:
1. We identify the responsibility problem (section 3). This is a fundamental issue with existing set prediction models that has not been considered in the literature before, explaining why these models struggle to model even the simple polygon dataset. 2. We introduce FSPOOL: a differentiable, sorting-based pooling method for variable-size sets (section 4). By using our pooling in the encoder of a set auto-encoder and inverting the sorting in the decoder, we can train it with the usual MSE loss for reconstruction without the need for an assignment-based loss. This avoids the responsibility problem. 3. We show that our auto-encoder can learn polygon reconstructions with close-to-zero error, which is not possible with existing set auto-encoders (subsection 6.1). This benefit transfers over to a set version of MNIST, where the quality of reconstruction and learned representation is improved (subsection 6.2). In further classification experiments on CLEVR (subsection 6.3) and several graph classification datasets (subsection 6.4), using FSPool in a set encoder improves over many non-trivial baselines. Lastly, we show that combining FSPool with Relation Networks significantly improves over standard Relation Networks in a model that heavily relies on the quality of the representation (subsection 6.5).
This paper proposes to make permutation-equivariant set autoencoders, by introducing a permutation invariant encoder (based on feature-wise sorting) and at the same time an 'inverse' operation (that undoes the sorting) in the decoder. The achieved equivariance allows the autoencoders to be trained end-2-end without a matching-based loss (like Chamfer) which I think is a very neat result. Also, to address potentially variable-sized sets as inputs/outputs, the authors propose to use a calibrator function that effectively 'samples' the produced features on the set's elements in fixed intervals, that are auto-adaptable in the (variable) set size. 
The results shown are well placed in the current literature and form an important novelty that should have non-trivial impact in the sub-field. Also, the experiments done are well executed, with ample variability in the nature of the datasets used and I expect them to also be easily reproducible (given the authors' provided code).
Some points I would appreciate to see an improvement:
a. The intro is rough (please see minor-specifics at places that you can improve the exposition).
b. The Figure1 is not easy to read. The 90degree rotation results in the same set, but as a 'pictorial' image, obviously not.
c. The "responsibility problem" is already very well explained in the Zhang19a. I would appreciate to tone-down in this paper, the "discovery" of it as a main contribution.
d. Experiments 6.2. it appears that the FSPool/unpool model is better *only* when the mask features are been considered. What are these mask-features? Why do they matter?
e. The way you describe the responsibility problem (discontinuity) is very hand-wavy. It would be nice to explicitly it write it in rigorous math.
f. Why using the relaxation of Grover et al. helped you to avoid the discontinuity that would be otherwise introduced via standard sorting? (I am not familiar with their exact relaxation, but intuitively, their method been a good proxy for sorting, should suffer from it as well). 
Explicit Minor Comments on writing:
(all in introduction)
-4rth line: "this" -> this problem
-"Methods like by" -> Methods like those in 
-"In this paper, we introduce a set pooling method for neural networks that addresses both issues" -> which issues? the encoder's collapse and the decoder's inneficiency in matching? Please explain.
-"good baselines" -> sophisticated/non-trivial baselines
Appendix. Table 9, max-pool at \sigma=0, seems to be the best (please use boldface to indicate it).