FSPool: Learning Set Representations with Featurewise Sort Pooling
Authors: Yan Zhang
Jonathon Hare
Adam Prügel-Bennett
Venue:  (2020)
Keywords: set auto-encoder
set encoder
pooling

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

Published as a conference paper at ICLR 2020
FSPOOL: LEARNING SET REPRESENTATIONS WITH FEATUREWISE SORT POOLING
Yan Zhang
Jonathon Hare
University of Southampton Southampton, UK yz.5112ecs..
University of Southampton Southampton, UK jsh2@ecs sot on ac uk
wotssssottooo sot on. aat.tnnuuuu ackuk
Adam Prüigel-Beneett University of Southampton
Southampton, UK apbêecs woton.oc....
ABSTRACT
Traditional set prediction models can struggle with simple datasets due to issue we call the responsibility problem. We introduce a pooling method for sets of feature vectors based sorting features across elements of the set. This can be used to construct a prrmutation-equivariaan auto-encoder that avoids this responsibility problem. On toy dataset of polygons and 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 variety of datasets.
INTRODUCTION
Consider the following task: you have dataset wherein each datapoint is set of 2-d points that form the vertices of regular polygon, and the goal is to learn auto-encoder this dataset. The only variable is the rotation of this polygon around the origin, with the number of points, size, and centre of fixed. Because the inputs and outputs are sets, this problem has some unique challenges.
Encoder: This turns the set of points into latent space. The order of the elements in the set is irrelevant, so the feature vector the encoder produces should be invariant to permutations of the elements in the set. While there has been recent progress on learning such functions (Zaheer et al. 2017 Qi al., 2017), they compress a set of any size down to a single feature vector one step. This can be significant bottleneck in what these functions can represent efficiently, particularly when relations between elements of the set need to be modeled (Murphy et al. 2019: Zhang et al. 2019b).
This turns the latent space back into set. The elements in the target set have an arbitrary order, so standard reconstruction loss cannot be used naively - the decoder would have to somchow output the elements in the 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.
Decoder:
In this paper, we introduce 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 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 diffcrentiable, sorting-base pooling method for variable-size sets (section 4). By using pooling in the encoder of set auto-encoder and inverting the

---

Published as a conference paper at ICLR 2020
sorting in the decoder, we train it with the usual MSE loss for reconstruction without the need for an ussignment-baat based loss. This avoids the responsibility problem.
3. We show that our auto-encoder can learn polygon reconstructions with Glose-to-zero er- ror, 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 improved (subsection 6.2p. In further classification experiments on CLEVR (subsection 6.3) and several graph classification datasets (subsection 6.4). using FSPool in 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).
2 BACKGROUND
The problem with predicting sets is that the output order of the elements is arbitrary, so computing an clementwise mean squared еπгог does not make sense; there no guarantee that the elements in the target set happen to be in the same order as they were generated. The existing solution around this problem is an assignment-ben based loss, which assigns each predicted element its "closest" neighbour in the target set first, after which traditional pairwise loss can be computed.
We have a predicted set Y with feature vectors as elements and ground-truth set Y, and we want to measure how different the two sets are. These sets can be represented as matrices with feature vectors placed in the columns in some arbitrary order, so Y = [g(").... g(")] and Y =gy(")... (n)) with n as the set size (columns) and as the number of features per element (rows). In this work, we assume that these two sets have the same size. The usual way to produce Ý with multi-layer perceptron (MLP) that has d x outputs.
Linear assignment One way to do this assignment is to find linear assignment that minimises the total loss, which can be solved with the Hungarian algorithm in O(n²) time. With II as the space of all n-length permutations:
CH (Y min
Σ
1000 y (a(()))
xell
Chamfer loss Alternatively, we can assign each element directly to the closest element in the target set. To ensure that all points in the target set covered, term is added to the loss wherein each element in the target set is also assigned to the closest element in the predicted set. This has O(n?) time complexity and can be run efficiently GPUs.
Lo Y) = Σ min g 11 + Σ min ( 100
Both of these losses are examples of permutation of how the columns of Y and Y are permuted.
permulation-invariant invariant functions: the loss is the same regardless
RESPONSIBILITY PROBLEM
turns out that standard neural networks struggle with modeling symmetries that arise because there are n! different list representations of the same set, which we highlight here with an example. Suppose we want to train an auto-encoder on our polygon dataset and have a square (so a set points with the x-y coordinates features) with some arbitrary initial rotation (see Figure T}. Each pair in the 8 outputs of the MLP decoder is responsible for producing one of the points in this square. We mark each such pair with different colour in the figure.
we rotate the square (top left in figure) by 90 degrees (top right in figure), we simply permute the elements within the set. They are the same set, they also encode to the same latent representation
2

---

Published as a conference paper at ICLR 2020
C 90%
C 30
C
C 60%
Figure I: Discontinuity (red arrow) when rotating the set of points. The coloured points denote which output of the network is responsible for which point. In the top path, the set rotated by 90 is the same set (exactly the same shape before and after rotation) and encodes to the same feature vector, so the output responsibility (colouring) must be the same too. In this example, after 30 and further small clockwise rotation by e, the point that each output pair is responsible for has to suddenly change.
and decode to the same list representation. This means that each output is still responsible for producing the point at the same position after the rotation, i.c. the dark red output is still responsible for the top left point, the light red output responsible for the top right point, etc. However, this also means that at some point during that 90 degree rotation (bottom path in figure), there must exist discontinuous jump (red arrow in figure) in how the outputs are assigned. We know that the 90 degree rotation must start and end with the top left point being produced by the dark red output. Thus, we know that there is a rotation where the outputs must simultaneously change which point they are responsible for, that completing the rotation results in the top left point being produced by the dark red output. Even though we change the set continuously, the list representation (MLP or RNN oufputs) must change discontinuously.
This is a challenge for neural networks to learn, since they can typically only model functions without discontinuous jumps. As increase the number of vertices in the polygon (number of set elements), it must learn an increasing frequency of situations where all the outputs must discontinuously change once, which becomes very difficult model. Our experiment in subsection 6.1 confirms this.
This example highlights a more general issue: whenever there are at least two set elements that can be smoothly interchanged, these discontinuities arise. We show this more formally Anpppeddix A] For example, the set of bounding boxes in object detection can be interchanged in much the same way as the points of our square here. An MLP or RNN that tries generate these (like in Rezatofighi et al.) (2018); Stewart & Andrilukal (2066) must handle which of its outputs is responsible for what element in discontinuous way. Note that traditional object detectors like Faster R-CNN do not have this responsibility problem, because they do not treat object detection
proper set prediction task with their anchor-based approach. When the set elements come from a finite domain (often a set of labels) and not Rd. it does not make sense to interpolate set elements. Thus, the responsibility problem does not apply to methods for such problems, for example Welleck et al. (2018); Rezatofighi. et al. (2017).
4 FEATUREWISE SORT POOLING
The main idea behind our pooling method is simple: sorting each feature across the elements of the set and performing a weighted sum. The numerical sorting ensures the property of permutation- invariance. The difficulty lies in how to determine the weights for the weighted sum in way that works for variable-sized sets.
A key insight for auto-encoding is that we can store the permutation that the sorting applies in the encoder and apply the inverse of that permutation the decoder. This allows the model to restore the arbitrary order of the set element that it no longer needs assignment-basee loss for training. This avoids the problem in Figure because rotating the square by 90" also permutes the outputs of the network accordingly. Thus, there is no longer discontinuity in the outputs during this rotation. permuting the input set also
In other words, we make the auto-encoder permutes the neural network's 's output in the same way.
We describe the model for the simplest case of encoding Exed-size sets in subsection 4.1 extend it to variable-sized sets in subsection 4.2) then discuss how this in auto-encoder in subsection 4.3
3

---

Published as a conference paper at ICLR 2020
X
X
y
Mo 3 1 W)
f6.. W)
sort
product
discretise
Figure 2: Overview our FSPOOL model for variable-sized sets. In this example, the weights define piecewise linear functions with two pieces. The four dots each line correspond to the positions where f is evaluated for a set of size four.
4.1 FIXED-SIZE SETS
We are given set of n feature vectors [xx(1) =I=,(",...,,""" dimension d placed in some arbitrary order in the columns of X E Rdx=, From this, the goal is to
[()]
where each ( is a column vector of
produce single feature vector way that is invariant to permutation the columns in the matrix.
We first sort each of the d features across the elements of the set by numerically sorting within the of X to obtain the matrix of sorted features X:
X1, SORT (X..))
where X;,; is the ith row of X and S-RT(-) sorts a vector in descending order. While this may appear strange since the columns of X longer correspond to individual elements of the there good reasons for this. A transformation (such as with an MLP) prior to the pooling can ensure that the features heing sorted are mostly independent so that little information is lost treating the features independently. Also, we were to sort whole elements by one feature, there would be discontinuities whenever two elements swap order. This problem is avoided by our featurewise sorting.
Efficient parallel implementations of SORT are available in Deep Learning frameworks such as PyTorch, which uses a bitonic sort (O(log² n) parallel time, On log" n) comparisons). While the permutation that the sorting applies is not differentiable, gradients can still be propagated pathwise according to this permutation in a similar way as for max pooling.
Then, we apply a learnable weight matrix W E Rdxx to by elementwise multiplying and summing over the columns (row-wise dot products).
11
V1 Σ W Wiy X
R2d the final pooled representation of X. The weight vector allows different weightings of different ranks and is similar in spirit to the parametric version of the gather step in -xccte-Excite (Hu et al. 2018). This is a generalisation of both max and sum pooling, since max pooling can be obtained with the weight vector [1, O..... and sum pooling can be obtained with the vector. Thus, is also a maximally powerful pooling method for multi-sets (Xu et al. 2019) while being potentially more flexible (Murphy al. 2019) in what represent.
4.2 VARIABLE-SIZE SETS
When the size of sets can vary, our previous weight matrix can no longer have fixed number of columns. To deal with this, we define a continuous version of the weight vector in each row: we use fixed number of weights to parametrise piecewise linear function f [0. 1] E, also known as calibrator function (Jaderberg et al. 2015). For set of size three, this function would be evaluated at 0, 0.5, and to determine the three weights for the weighted sum. For set of size four, it would be evaluated at 0, 1/3, 2/3, and 1. This decouples the number of columns in the weight matrix from the set size that it processes, which allows be used for variable-sized sets.
4

---

Published as a conference paper at ICLR 2020
To parametrise piecewise linear function f, we have weight vector w R where & - 1 is the number of pieces defined by the k points. With the ratio r E [0, 1].
f(r. 1)
Σ max(0, 1 1-rr(k--------- 1) 1)
(5)
The max(.) term selects the two nearest points to and linearly interpolates them. For example, k = 3, choosing E [0, 0.5) interpolates between the first two points in the weight vector with (1-2r)wn + 2rw2-
We have a different t for each of the d features and place them in the rows of a weight matrix W gdxk, which longer depends on n. Using these rows with determine the weights:
n2 y1
Σ
& 72
(6)
y is now the pooled representation with potentially varying set size n as input. When n this reduces back to Equation 4 For most experiments, simply set &t 20 without tuning it.
4.3 AUTO-ENCODER
To create an auto-encoder, we need a decoder that turns the latent space back into set. Analogously to image auto-encoders, want this decoder roughly perform the operations of the encoder in reverse. The FSPool in the encoder has two parts: sorting the features, and pooling the features. Thus, the FSUnpool version should "unpool" the features, and "unsort" the features. For the former, define an unpooling version of Equution 6) that distributes information from one feature vector to variable-siz size list of feature vectors. For the latter, the idea store the permutation the sorting from the encoder and use the inverse of it in the decoder to unsort it. This allows the auto-encoder to restore the original ordering of set elements, which makes it permutation-equivariiee
With y Rd as the vector to be unpooled, we define the unpooling similarly to Equation 6
X f( W
In the non-autoencoder setting, the lack of differentiability of the permutation is not problem due to the pathwise differentiability. However, in the auto-encoder setting we make use the permutation in the decoder. While gradients still be propagated through it, introduces discontinuities whenever the sorting order in the encoder for a set changes, which we empirically observed to be a problem. To avoid this issue, need the permutation that the sort produces to be differentiable. To achieve this, we use the recently proposed sorting networks (Grover et al., 2019), which is a continuous relaxation of numerical sorting. This gives differentiable approximation of permutation matrix P. E [0, 1|nxn, E {I....,d} d} for each of the d features, which we can use in the decoder while still keeping the model fully differentiable. It comes with the trade-off of increased computation costs with (n²)) time and space complexity, so we only use the relaxed sorting in the auto-encoder setting. possible to decay the temperature of the relaxed sort throughout training to which allows the more efficient traditional sorting algorithm to be used at inference time.
Lastly, we can use the inverse of the permutation from the encoder to restore the original order.
x = (X:,
where Pf permutes the elements of the ith row in X²
Because the permutation is stored and used in the decoder, this makes our auto-encode similar to U-net architecture (Long al.] 2015) since it is possible for the network to skip the small latent space. Typically we find that this only starts to become a problem when is too big, in which case possible to only subset of the P; in the decoder to counteract this.
5

---

Published as a conference paper at ICLR 2020
5 RELATED WORK
We are proposing a differentiable function that maps set of feature vectors to a single feature vector. This has been studied in many works such as Deep Sets (Zaheer et al. 2017) and PointNet (Qi ict al., 2017). with universal approximation theorems being proven. our notation, the Deep Sets model is g(, h(X.))) where h : R IP and g R² 129, Since this is (n)) in the set size n, it is clear that while it may be able to approximate any set function, problems that depend on higher-order interactions between different elements the set will be difficult to model aside from pure memorisation. This explains the success of relation networks (RN), which simply perform this sum over all pairs of clements, and has been extended to higher orders by Murphy et al. (2019). Our work proposes an alternative operator to the sum that is intended to allow some relations between elements to be modeled through the sorting, while not incurring as large of a computational cost as the O(n?) complexity of RNs.
Sorting- based set functions The use of sorting has often been considered in the set learning literature due to its natural way of ensuring permutation-invarian elements of the set as units rather than our approach of sorting each feature individually.
The typical approach is to sort
For example, the similarly-named SortPooling (Zhang al. 2018) sorts the elements based one feature each element. However, this introduces discontinuttes into the optimisation whenever two elements swap positions after the sort. For variable-sized sets, they simply truncate (which again adds discontinuities) or pad the sorted list to a fixed length and process this with a CNN, treating the sorted vectors sequence. Similarly, Cangea al. (0088) and Gao & Jil (2019) truncate by computing a score for each element and keeping elements with the top-k scores. In contrast, our pooling handles variable set sizes without discontinuities through the featurewise sort and continuous weight space. Gao & Ji (2019) propose a graph auto-encoder where the decoder use the "inverse" of what the top-k operator does in the encoder, similar to our approach. Instead of numerically sorting, Mena et al. (2018) and Zhang et al. (2019b) learn ordering of set elements instead.
fixed-size set
Outside of the set learning literature, rank-based pooling in convolutional neural network has been used in (hi et al. (2016), where the rank is turned into a weight. Sorting within single feature vector has been used for modeling more powerful functions under a Lipschitz constraint for Wasserstein GANs (Anil et al. 2018) and improved robustness to adversarial examples (Cisse et al. 2017).
Set prediction Assignment- based losses combined with an MLP or similar are popular choice for various auto-encoding and generative tasks on point clouds (Fan et al. 2017 Yang al.] 2018 Achlioptas et al.] (2018). An interesting alternative approach is to perform the set generation sequen- tially (Stewart & Andriluka 2016 Johnson 2017: You et al. 2018). The difficulty lies in how to turn the set into one or multiple sequences, which these papers try to solve in different ways. Since the initial release of this paper, Zhang et al. (2019a) developed set prediction method which uses FSPool as a core component and motivate their work by our observations about the responsibility problem. Interestingly, their model uses the gradient of the set encoder, which involves computing the gradient of FSPool; this is closely related to the FSUnpool we proposed.
EXPERIMENTS
We start with two auto-encoder experiments, then move to tasks where we replace the pooling in an established model with FSPool. Full results can be found in the appendices, experimental details can be found in Appendix H and we provide our code for reproducibility [redacted].
6.1 ROTATING POLYGONS
We start with our simple dataset of auto-encoding regular polygons (section 3), with each point in set corresponding the x-y coordinate of vertex in that polygon. This dataset is designed to explicitly test whether the responsibility problem occurs in practice. We keep the set size the same within a training run and only vary the rotation. We try this with set sizes of increasing powers of
Model The encoder contains a 2-layer MLP applied to each set element, FSPool, and 2-layer MLP to produce the latent space. The decoder contains 2-layer MLP, FSUnpool, and 2-layer MI.P

---

Published as a conference paper at ICLR 2020
0.00
0=0001
0.01
0=00.0
000005
4/
5
S
Tarpet
4
5 5
5
0.0
4
5
S
Figure 3: MNIST as point sets with different amounts of Gaussian noise (0) and their reconstructions. The baseline uses sum pooling and an MLP decoder, which had the best quantitative results among the baselines. We used the best network for model (0.28 10* average Chamfer loss) and the best network for the baseline model (0.20 x 10 average Chamfer loss). The examples are not cherry-picked.
applied on each set element. We train this model to minimise the mean squared error. As baseline, we use a model where the decoder has been replaced with an MLP and train it with either the linear assignment or Chamfer loss (equivalent to AE-EMD and AE-CD models in AAhlioptas et al. (2018).
Results First, we verified that if the latent space is always zeroed out, the model with FSPool is unable to train, suggesting that the latent space is being used and is necessary. For our training runs with set sizes up to 128, our auto-encoder is able to reconstruct the point set close to perfectly (see Appendix Bp. Meanwhile, the baseline converges significantly slower with high reconstruction error when the number of points is 8 or fewer and outputs the same set irrespective of input above that, regardless of loss function. Even when significantly increasing the latent size, dimensionality of layers, tweaking the learning rate, and replacing FSPool in the encoder with sum, mean, or max, the baseline trained with the linear assignment or Chamfer loss fails completely at 16 points. We verified that for 4 points, the baseline shows the discontinuous jump behaviour in the outputs as predict in Figure I This experiment highlights the difficulty of learning this simple dataset with traditional approaches due to the responsibility problem, while our model is able to fit this dataset with ease.
6.2 NOISY MNIST SETS
Next, we turn to the harder task of auto- auto-encoding MNIST images turned into sets of points using a denoising auto-encoder. Each pixel that is above the mean pixel level considered to be part of the set with its x-y coordinates as feature, scaled to be within the range of [0, 1]. The set size varies between examples and 133 on average. We add Gaussian noise to the points in the set and use the set without noise training target for the denoising auto-encoder.
Model We use exactly the same architecture as on the polygon dataset. As baseline models, we combine sum/mean/max pooling encoders with ML.P/L.TT, decoders and train with the Chamfer loss. This closely corresponds to the AF-CD approach (Achlioptas et al., (2018) with the MI.P decoder and the model by Sttewart& & Andriluka 2016) with the LSTM decoder. We tried the approach by Zhang et al. (2019a), but it performs much worse than the other baselines, likely because it requires a bigger encoder (our encoder has 3000 parameters, their encoder has ~5500 parameters).
Results We show example outputs in Figure and the full results in Appendix C We focus on comparing our FSPool-FSSUnpoo model against the best baseline, which uses the sum pooling encoder and MLP decoder. In general, our model can reconstruct the digits much better than the baseline, which tends to predict too few points even though it always has 342 (the maximum set size) times 2 outputs available. Occasionally, the baseline also makes big errors such as turning 5s into 8s (first a 0.01 example), which we have not observed with model.
7

---

Published as a conference paper at ICLR 2020
Table 1: MNIST classification accuracy over runs (different pre-trained networks between runs): mean =\t stdev for o = 0.05. Frozen: training with frozen pre-trained auto-encoder weights. Unfrozen:
unfrozen auto-encoder weights (fine-tuning). Random init: auto-encoder weights not used.
1 epoch of training
10 epochs of training
Frozen
Unfrozen
Random init
Frozen
Unfrozen
Random init
ESPOOL
82.2%
86.9%+13
84.7%++19
84.3%
91.5%
91.9%+as
SUM
76.6%=11
68.7%
30.3%=a.
79.0%++1o
77.7%-22
72.7% +344%
MEAN
32.2% 25.7%
30.1 1621.
36.8%150
75.0%=27
73.0%
MAX
73.6%
73.0%
16.66
77.3%
80.4%=1.8
76.9%
6.2.1 CLASSIFICATION
Instead of auto-encoding MNIST sets, can also classify them. We the same dataset and replace the set decoder in our model and the baseline with a 2-layer MLP classifier. We consider three variants: using the trained auto-encoder weights for the encoder and freezing them, not freezing them (finetuning), and training all weights from random initialisation. This tests how informative the learned representations of the pre-trained auto-encoder and the encoder are.
Results for = 0.00 and 100 epochs are shown in Anppedxxi D Even though our model can store information the permutation that skips the latent space, our latent space contains more information to correctly classify set, even when the weights are fixed. Our model with fixed encoder weights already performs better after I epoch of training than the baseline models with unfrozen weights after 10 epochs of training. This shows the benefit of the ISPool-FSUnpoo auto-encoder to the representation. When allowing the encoder weights to change (Unfrozen and Random init), results again improve significantly baselines. Interestingly, switching the relaxed sort to the unrelaxed sort in our model when using the fixed auto-encoder weights does not hurt accuracy. Training the FSPool model takes 45 seconds per epoch on a GTX 1080 GPU, only slightly more than the baselines with 37 seconds per epoch.
Results We show our results for 0.05 in Table 1
the
6.3 CLEVR
visual question answering dataset where the task is classify an answer to question about an image. The images show scenes of 3D objects with different attributes, and the task answer reasoning questions such as "what size the sphere that is left of the green thing". Since we are interested in sets, we use this dataset with the ground-truth state description the set of objects (maximum size 10) and their attributes - as input instead of an image of the rendered scene.
CLEVR (Johnson 2017)
Model For this dataset, compare against relation networks (RN) (Santoro al. 2017]
plicitly modeling all pairwise relations Janossy pooling (Murphy et al. 2019). and regular pooling functions. While the original RN paper reports result of 96.4% for this dataset, implementation by Messina et al. (2018) with 2.6% better accuracy. For our model, we modify this to operate on pairwise relations and replace the existing sum pooling with ESPool. We the same hyperparameters for our model as the strong RN baseline without further tuning them.
tuned
Results Over 10 runs, Table shows that our FSPool model reaches the best accuracy and also reaches the listed accuracy milestones in fewer epochs than all baselines. The difference in accuracy statistically significant (two-tailed I-tests against sum, mean, RN, all with p s 0.01). Also, FSPool reaches 99% accuracy in 5.3 h, while the fastest baseline, mean pooling, reaches the same accuracy in 6.2 h. Surprisingly, RNs do not provide any benefit here, despite the hyperparameters being explicitly tuned for the RN model. We show some of the functions f(. W') that FSPool has learned in Apppendx E These confirm that FSPool uses more complex functions than just sums or maximums, which allow it to capture more information about the set than other pooling functions.
8

---

Published as a conference paper at ICLR 2020
Table 2: CLEVR results over 10 runs: mean + stdev of accuracy after 350 epochs, epochs reach an accuracy milestone, and wall time required with a 1080 Ti GPU. averages over only 8 runs because 2 runs did reach 99%. MAC (Hudson & Manning 2018) is a model specifically designed for CLEVR and the state-of-the-ee for image inputs and without program supervision.
Epochs to reach accuracy
Time for
Model
Accuracy
98.00%
98.50%
99.00%
350 epochs
ESPOOL
99.27%
141=
166 189
209
8.8
RN
98.98%1122
144 6
2268.146
15.5
JANOSSY
97.00%
11.5
SUM
99.05% +0.17
146+13
191
28 #:66
8.0 h
MEAN
98, +027
169
225+31
273 +:3
8.0 h
MAX
96.99%1100
8.0
MAC
99.0 %
6.4 GRAPH CLASSIFICATION
We perform a large number of experiments on various graph classification datasets from the TU repository (Kersting et al. 2016): 4 graph datasets from bioinformatics (for example with the graph encoding the structure of molecule) and datasets from social networks (for example with the graph encoding connectivity between people who worked with each other). The task is to classify the whole graph into one of multiple classes such as positive or negative drug response.
Model We use the state-of-the-an graph neural network GIN (Xu et al. 2019) baseline. This involves series of graph convolutions (which includes aggregation of features from each node's 's set of neighbours into the node), readout (which aggregates the of all nodes into one feature vector), and a classification with an MLP. We replace the usual sum mean pooling readout with FSPool for our model. We repeat 10-fold validaaalio on each dataset 10 times and use the same hyperparameter ranges as Xu et al. (0199) for our model and the GIN baseline.
Results We show the results in Appendix F On 6 out of 9 datasets, FSPool achieves better test accuracy. On a different datasets, it converges the best validation accuracy faster. A Wilcoxon signed-rank test shows that the difference in accuracy to the standard GIN has p = 0.07 (W 7) and the difference in convergence speed has p z 0.11 (W 9). Keep in mind that just because the results have > 0.05, it does not mean that the results are invalid.
6.5 CLEVR WITH DEEP SET PREDICTION NETWORKS
Zhang et al. (019a) build on the ideas in this paper to develop a model that can predict sets from an image. Their model requires from a set encoder that the more similar two set inputs are, the more similar their representations should be. This is harder than classification, because different inputs (of the same class) should no longer map to the same representation. the benefit of the RN + FSPool set encoder they used. We use their experimental set-up and replace FSPool with sum (this gives the normal RN model) or max pooling. We train this on CLEVR to predict the set of bounding boxes the state description (this was the input in subsection 6.3).
this experiment, we quantify
Results Appendix Glshows that for both bounding box and state prediction models, the RN encoder using FSPool much better than sum or max. This shows that it possible to improve on standard Relation Networks simply by replacing the sum with FSPool when the task is challenging enough.
7 DISCUSSION
In this paper, we identified the responsibility problem with existing approaches for predicting sets and introduced FSPool, which provides a way around this issue in auto-encoders. In experiments on two datasets of point clouds, we showed that this results in much better reconstructions. We

---

Published as a conference paper at ICLR 2020
believe that this is important step towards set prediction tasks with more complex set elements. However, because our decoder uses information from the encoder, it is not easily possible to turn into generative set model, which is the main limitation of our approach. Still, we find that using the auto-encoder to obtain better representations and pre-trained weights can be beneficial by itself. Our insights about the responsibility problem have already been successfully used create model without the limitations of our auto-encoder (Zhagg et al. 2019a).
In classification experiments, we also showed that simply replacing the pooling function in an existing model with FSPool can give us better results and faster convergence. We showed that FSPool consistently learns better set representations improved results in the downstream task. Our model thus has immediate applications in various types of set models that have traditionally used sum or max pooling. It would useful to theoretically characterise what types of relations are more easily expressed by FSPool through an analysis like in Murphy et al. (209). This may result in further insights into how to learn better set representations efficiently.
relatively small computational cost, leading to
REFERENCES
Panos Achlioptas, Olga Diamanti, Ioannis Mitliagkas, and Leonidas J Guibas. Learning represen- tations and generative models for 3D point clouds. Proceedings of the 35th International Conference Machine Learning (ICML), 2018
Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. arXiv:1811.00 S.VV:1811.0581,, 105381, 2018.
James Atwood and Don Towsley. Difftusion-convolutionnal neural networks. In Advances in Neural Information Processing Systems 29 (NeurIPS), 2016.
Cätälina Cangea, Petar Veličković, Nikola Jovanović, Thomas Kipf, and Pietro Liò. Towards sparse hierarchical graph classifiers. NeurlPS Workshop, Relational Representation Learning, 2018.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval Networks: Improving robustness to adversarial examples. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
Haoqiang Fan, Hao Su, and Leonidas J. Guibas. A point set generation network for 3D object reconstruction from single image. The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
2017.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. SplineCNN: Fast geometric deep learning with continuous B-spline kernels. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
Hongyang Gao and Shuiwang Ji. Graph U-Net, 2019. URL https::/openrervieet netn (orumm2d==JePPAAcct
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics (AISTATS), 2010.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In International Conference on Learning Representations (ICLR), 2019.
Jie Hu, Li Shen, Samuel Albanie, Gang Sun, and Andrea Vedaldi. Gather-Excite: Exploiting feature context in convolutional neural networks. In Advances in Neural Information Processing Systems 31 (NeurIPS), 2018
Drew A. Hudson and Christopher D. Manning. Compositional Attention Networks for Machine Reasoning. In International Conference on Learning Representations (ICLR), 2018.
Max Jaderberg, Karen Simonyan, Andrew Zisserman, and Koray Kavukcuoglu. Spatial transformer networks. In Advances in Neural Information Processing Systems 28 (NeurlPS), 2015.
10

---

Published as a conference paper at ICLR 2020
Daniel D. Johnson. Learning graphical state transitions. In International Conference Learning Representations (ICLR), 2017.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. URL http::://graaaaeeeeel... cs. tu-dortmund
de
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference Learning Representations (ICLR), 2015.
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In The IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2015.
Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning Latent Permutations with Gumbel-Sinkhorn Networks. In International Conference on Learning Representations (ICLR), 2018
Nicola Messina, Giuseppe Amato, Fabio Carrara, Fabrizio Falchi, and Claudio Gennaro. Learning relationship-aware visual features, 2018. URL http:///ww ocbp....r/.rr...rr
rearning-relattonnss www.:osssshhaa-aaeeeeeeee aware peeaare-reprinn pdf
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pooling: Learning deep permutationninvariinn functions for variable-size inputs. In International Conference on Learning Representations (ICLR), 2019.
Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting, Propagation kernels: Efficient graph kernels from propagated information. Machine Learning, 102(2):209-245, 2016. ISSN 0885-6125.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov, Learning convolutional neural networks for graphs. In Proceedings of the 33rd International Conference on Machine Learning (ICML), 2016.
Charles R. Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
S. Hamid Rezatofighi., Vijay Kumar B G, Anton Milan, Ehsan Abbasnejad, Anthony Dick, and Ian Reid. DeepSetNet: Predicting sets with deep neural networks. In The IEEE International Conference on Computer Vision (ICCV), 2017.
S. Hamid Rezatofighi, Roman Kaskman, Farbod T. Motlagh, Qinfeng Shi, Daniel Cremers, Laura Leal-Taixé, and Ian Reid. Deep perm-set net: Learn to predict sets with unknown permutation and cardinality using deep neural networks. arXiv:1805.00613. 2018.
Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski. Razvan Pascanu, Peter Battaglia, and Tim Lillicrap. A simple neural network module for relational reasoning. In Advances in Neural Information Processing Systems 30 (NeurIPS). 2017.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Leeuwen, Kurt Mehlhom, and Karsten M. Borgwardt. Weisfeiler- Lehman Graph Kernels. Journal of Machine Learning Research, 12: 2539-2561, 2011. ISSN 1532-4435.
Zenglin Shi, Yangdong Ye, and Yunpeng Wu. Rank-based pooling for deep convolutional neural networks. Neural Networks, 83:21 31, 2016. ISSN 0889360800.
Russell Stewart and Mykhaylo Andriluka. End-to-end people detection in crowded scenes. The IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2016.
Sean Welleck, Zixin Yao, Yu Gai. Jialin Mao, Zheng Zhang, and Kyunghyun Cho. Loss functions for multiset prediction. In Advances in Neural Information Processing Systems 3/ (NeurIPS), 2018.

---

Published as a conference paper at ICLR 2020
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations (ICLR), 2019.
Yaoqing Yang, Chen Feng, Yiru Shen, and Dong Tian. FoldingNet: Point cloud auto-encoder via deep grid deformation. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems 31 (NeurIPS), 2018.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovee. GraphRNN: Generating
realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference Machine Learning (ICML), 2018.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep Sets. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the Thirty-Second AAAI Conference Artificial Intelligence (AAAI), 2018.
Yan Zhang, Jonathon Hare, and Adam Prügel-Bennett. Deep Set Prediction Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019a
Yan Zhang, Jonathon Hare, and Adam Prügel- Learning representations of sets through optimized permutations, In International Conference on Learning Representations (ICLR), 2019b.
12

---

Published as a conference paper at ICLR 2020
A FORMAL RESPONSIBILITY PROBLEM
The following theorem a more formal treatment of the responsibility problem resulting in disconti- nuities.
Theorem 1. For any set function f S + R2*= (d 2, n 2, S is the set of all sets of size n with elements in Bd) from a set of points S = {z1, 22..... En ) to a list representation of that set L = [T())) D (2))).... [n))) with some fixed permutation a E II, there will be a discontinuity in f: there exists O such that for all 5 > O, there exist sets S1 and S2 where:
d.(Si; S2) <8 and ds( ((S)) 2
dg a measure of the distance between two sets (e.g. Chamfer loss) and de is the sum of Euclidean distances (di(A, B) E, ||, b
Figure 4: Example the set with two points.
Proof. We prove the theorem by considering mappings from set of two points in two dimensions. For larger sets or sets with more dimensions, we can isolate two points and two dimensions and ignore the remaining points and dimensions.
(see Figure 4). This is mapped to list L())= (()())) Without loss of generality, can assume that our list representation for (0) cos(0)
Let us consider the set of two points S(0) = [[
cos(
cos(O) sin(e) sin(f)
}
0 is L(0) =
0 = -1 1 1 Since the order of set elements is irrelevant and f is
(0) sin(0)
set function, S(T) S()) and therefore L(T) = L(0) = [[- This implies that for at least one value 0 0", there a change responsibility such that for s 0*,
(permutationninnarice
the list representation will be (0) - cos(O) cos(o) while for 0", the list representation will sin(0) sin(e)
cos( cos( in order satisfy ((T) L(O). For any 0, di (L, L2( 4. be (2) sin(B) - sin
Let = 3.9 and 8 be given. We can find sufficiently small so that dS(O)))), S( +a)) < and ((")) Li0" + a)) >
The reason why this does not apply our method that rather than choosing fixed a for the list representation, the -equiaaiiioe-uuuviiianeee (instead of the invariance of set functions) allows our model have L(x) # L()..
B POLYGONS
Results In Table 3 Table 4 and Table 5] we show the results of various model and training loss combinations. We include a random baseline that outputs a polygon with the correct size and centre, but random rotation.
These show that FSPool with the direct MSE training loss is clearly better than the baseline with either linear assignment Chamfer loss all the evaluation metrics. When the set size is 16 or greater, the other combinations only perform as well as the random baseline because they output the same constant set regardless of input.
13

---

Published as a conference paper at ICLR 2020
Table 3:
Direct mean squared error (in hundredths) Polygon dataset with different number of points in the set. Lower is better.
Set size
4
16
32
64
FSPOOL RANDOM
0,000
0.001
0.000
0.000
0.000
0.0001
100.323
100.134
99.367
99.951
99.438
99.523
Table 4:
Chamfer loss (in hundredths) on Polygon dataset with different number of points in the set.
Lower is better.
Set size
2
4
8
16
32
64
PSPOOL MLP + Chamfer 1.189
0.001
0.001
0.001
0.000
0.001
0.002
1.771
0.274
1.272
0.316
0.085
MLP + Hungarian
1.517
0.400
0.251
1.266
0.326
0.081
RANDOM
72.848
19.866
5.112
1.271
0.322
0.081
Table 5: Linear assignment loss (in hundredths) on Polygon dataset with different number points in the set. Lower is better.
Set size
2
4
8
16
32
64
FSPOOL
0.000
0.001
0.000
0.000
0.000
0.001
MLP + Chamfer
0.595
0.885
0.137
0.641
0.160
0.285
MLP Hungarian
0.758
0.200
0.126
0.634
0.163
0.040
RANDOM
36.424
9.933
2.556
0.635
0.161
0.041
C MNIST RECONSTRUCTION
Interestingly. the sum pooling baseline has lower Chamfer reconstruction eπror than model, despite the example outputs in Figure 3 looking clearly worse. This demonstrates a weakness of the Chamfer loss. Our model avoids this weakness by being trained with normal MSE loss (with the cost of potentially higher Chamfer loss), which is not possible with the baselines. The sum pooling baseline has a better test Chamfer loss because it trained minimise it, but is also solving easier task, since it does not need to distinguish padding from non-padding elements.
Results We show the results for the default MNIST setting Table 6
The main reason for this difference comes from the shortcoming of the Chamfer loss in distinguishing sets with duplicates or near- duplicates. For example, the Chamfer loss between [L. 1.001, 9] and [1, 9.001] close to O. Most points in an MNIST are quite close to many other points and there are many duplicate padding elements, so this problem with the Chamfer loss is certainly present on MNIST. That is why minimising MSE can lead to different results with higher Chamfer loss than minimising Chamfer loss directly, even though the qualitative results seem worse for the latter.
We can make the comparison between our model and the baselines more similar by forcing the models to predict an additional "mask feature" for each set element. This takes the value I when the point is present (non-padding element) and 0 (padding element) when not. This setting is useful for tasks where the predicted set size matters, it allows points the coordinates (0, 0) to be distinguished from padding elements. These padding elements are necessary for efficient minibatch wise training.
The results of this variant are shown in Table 7 Now, model is clearly better: even though our auto-encoder minimises an MSE loss, the test Chamfer loss is also much better than all the baselines. Having to predict this additional mask feature does not affect our model predictions much because our model structure lets our model "know" which elements are padding elements, while this is much more challenging for the baselines.
14

---

Published as a conference paper at ICLR 2020
Table 6: Test Chamfer loss (in 10 000ths) for MNIST for different input noise levels 6 runs.
Lower is better.
Noise
0.00
0.01
0.02
0.03
0.04
0.05
FSPOOL + FSUNPOOL
0.42++0.6
0.34
0.36
0.38
0.41 +0.00
0.44
SUM MLP
0.30.+0.0
0.28 +0.03
0.28 +0.00
0.28 +000
0.27 #0.01
0.31+0.04 +0.04
SUM RNN
0.76
0.58
0.57
0.54
0.64
0.78
MAX + MLP
1.29
1.37 20.28
1.23
1.74
1.27
1.43
MEAN + MLP
1.41
1.22
1.33
1.25
1.31
1.49
Table 7: Test Chamfer loss (in 10 000ths) for MNIST with additional mask features (see description in Appendix cp every element for different input noise levels over 6 runs. Lower is better.
Noise a
0.00
0.01
0.02
0.03
0.04
0.05
FSPOOL FSUNPOOL.
0.28
0.21:000
0.25 200s
0.25
0.27
0.30
SUM MIP
0.90 0.87
0.61 :0.0
0.99
0.63
0.61
SUM RNN
0.58
0.69
0.60
1.35
0.73
0.63
MAX + MLP
5.91
4.78
7.10
5,05
5.85
4.57
MEAN MLP
5.92.1310
4.55
6.84
7.11
3.04.078
6.34
Table 8: Classification accuracy (mean + stdev) MNIST 0.00 over 6 runs.
epoch of training
10 epochs of training
Frozen
Unfrozen
Random init
Frozen
Unfrozen
Random init
FSPOOL
86.3%=
92.3%+11
90.5%
88.2%
96.0%:10.
96.1%
SUM
82.3%=12 77.9%
38.3%
85.0%
84.2%
78.4% 139
MEAN
27.0%=a.
47.
31.2%
76.7%=26 42.
77.2% 87.7%
MAX
82.0%=1s
84.1 1
62.9%
86.8 299
91.9%
Table 9: Classification accuracy (mean + stdev) MNIST for 100 epochs 6 runs.
= 0.05, 100 epochs
=
0.00, 100 epochs
Frozen
Unfrozen
Random init
Frozen
Unfrozen
Random init
FSPOOL
84.9%=17
93.9%
94.0%=03
88.6%
97.4%=40
97.5% +.03
SUM
85.3% 79.8%=10
83. 16
89.5% 85.6%
88.3%
MEAN
48.
40s
84. 1%
57.0%
90.3%
91.1 10.
MAX
78.8%=ox
1o.
84.6%220
89.2 ao
95.3%
95.1 115
D MNIST CLASSIFICATION
Results Table 8 and Table 9 show the results for = 0.00 and for 100 epochs for both = 0.05 and a = 0.00 respectively. Note that these are based on pre-trained models from the default MNIST setting without mask feature. Like before, the FSPool-based models are consistently superior to all the baselines. Note that while (Qi et al. 2017) report an accuracy of ~.99% on a similar set version of MNIST, model uses noisy sets input and is much smaller and simpler: have 3820 parameters, while their model has 1.6 million parameters. Our model also does not use dropout, batch norm, branching network architecture, and stepped learning rate schedule. When try to match their model size, our accuracies for a = 0.00 increase to ~99% as well.
15

---

Published as a conference paper at ICLR 2020
E
CLEVR
mmmm
Figure 5: Shapes of piecewise linear functions learned by the FSPool model on CLEVR. These show r E [0, 1] on the x-axis and fr, w) on the y-axis for particular t of a fully-trained model. common shape among these functions are variants of max pooling: close weight for most ranks and a large non-zero weight on either the maximum or the minimum value, for example in row 2 column 2. There are many functions that simple maximums or sums can not easily represent, such variant of max pooling with the values slightly below the max receiving weight of the opposite sign (see row column 1) or the shape in the penultimate row column 5. The functions shown here may have stronger tendency towards 0 values than normal due to the use of weight decay on CLEVR.
F GRAPH CLASSIFICATION
Experimental setup The datasets and node features used are the same as in GIN; we did not cherry-pick them. Because the social network datasets are purely structural without node features,
16

---

Published as a conference paper at ICLR 2020
Table 10: Cross-validation classification results (%) various commonly-used graph classification datasets, with the mean rros-validation accuracy averaged over 10 repeats and sample standard deviations (#). Hyperparameters of entries marked with are known to be selected based on test accuracy instead of validation accuracy, so results are likely not comparable to other existing
approaches that were (hopefully) selected based on validation accuracy. Our results were selected
based on validation accuracy.
Social Network
IMDB-B
IMDB-M
RDT-B
RDT-M5K
COLLAB
Num. graphs
1000
1500
2000
5000
5000
Num. classes
5
Avg. nodes
19.8
13.0
429.6
508.5
74.5
Max. nodes
136
89
3063
2012
492
DCNN (Awoodd Towsley
2016)
49.1
33.5
52.1
PATCHY-SAN (Niepert al.
2016
71.0 423
45.2 #28
86.3 116
49.1
72.6 #22
SORTPOOL (Zhang cf al.
2018
70.0 108
47.8 1.09
73.8 1005
DUFLPOOL YYig et al. 2018)
75.5
WL* (Xu et al. 2019)
73.8
50.9
81.0
52.5
78.9
GIN-BASE" (Xu et al.
2019)
75.1
52.3
92.4
57.5
80.2
GIN-FSPOOL
72.1 #20
49.9 #1.7
89.1 #122
51.8 +:.9
80.0 #0.4
epochs
95 +70
27 4:23
124 1:64
66 +:31
124 4:56
GIN-BASE
71.3 212
48.8 #1.7
84.8 =1.7
48.1 1200
80.3 20.4
eppochs
83 273
57 130
156 455
211 1:27
204 1:
Bioinformatics
MUTAG PROTEINS
PTC
NCI1
Num. graphs
188
1113
344
4110
Num. classes
2
2
2
Avg. nodes
17.9
39.1
25.5
29.8
Max. nodes
28
620
109
111
PK Neumann al. 2016)
76.0 #2.7
73.7 10.7
59.5 12.4
82.5 20.5
DCNN (twoodd & Towsley
2016
67.0
61.3
56.6
62.6
PATCHY- SAN (Nepert et al.
2016)
92.6 #42
75.9 4:288
60.0 448
78.6 #1.
SORTPOOL (Zhang et al.
2018
85.8
75.5 +:99
58.6 425
74.4 #.05
DIFFPOOL (Ying et al., 2018)
76.3
WL (Shervashidze et al.
2011
84.1
74.7
58.0
85.5
WL* [Xu et al. 2019)
90.4
75.0
59.9
86.0
GIN-BASE* (Xu at al.
2019)
89.4
76.2
64.6
82.7
GIN-OSPOOL
85.9 #24
73.8 +:0.
59.3 +18
79.2 #0.6
epochs
299 191
69 223
214 2110
361
1:54
GIN-BASE
85.0 11.
73.2 +1.2
59.9 12.4
79.4
20.6
epochs
244
160 +:23
202 1:100
412 4:55
constant feature is used on the RDT datasets and the one-hot-encoded node degree is used on the other social network datasets. The hyperparameter sweep done based on best validation accuracy for each fold in the cross-validation individually and over the same combinations as specified in GIN.
Note that in GIN, hyperparameters are selected based on best test accuracy. This is a problem, because they consider the number of epochs hyperparameter when accuracies tend significantly vary between individual epochs. For example, our average result on the PROTEINS dataset would change from 73.8% 77.1 5% if we were to select based on best test accuracy, which would be better than their 76.2%.
While initially also used A 20 in FSPool for this experiment, found that k 5 was consistently an improvement. The & = 20 model was still better than the baseline on average by smaller margin.
17

---

Published as a conference paper at ICLR 2020
Results We show our results of GIN-FSPool and the GIN baseline averaged 10 repeats in Table 10 On the majority of datasets, FSPool has slightly better accuracies than the strong baseline and consistently takes fewer epochs to reach its highest validation accuracy. On the two RDT datasets, this improvement is large. Interestingly, these are the two datasets where the number of nodes to be pooled is by far the largest with average of 400+ nodes per graph, compared the next largest COLLAB with an average of 75 nodes. This is perhaps evidence that FSPool is helping to avoid the bottleneck problem of pooling a large of feature vectors single feature vector.
We emphasise that the main comparison to be made is between the GIN-Base and the GIN-FSPool model, since that the only comparison where the only factor of difference is the pooling method. When comparing against other models, the network architecture, training hyperparameters, and evaluation methodology can differ significantly.
Keep in mind that while GIN-Base looks much worse than the original GIN-Base", the difference is that our implementation has hyperparameters properly selected by validation accuracy, while GIN- Base* selected them by test accuracy. If we were to select based on test accuracy, our implementation frequently outperforms their results. Also, they only performed single run of 10-fold cross- validation.
G DEEP SET PREDICTION NETWORKS
Table 11: Average Precision (AP, mean + stdev) for different intersection-over--ne thresholds of the predicted bounding boxes 6 runs. DSPN-RN-FSPOol results are taken from Zhang al. (2019a).
Model
APso
AP90
AP95
AP98
AP99
ESPN-RN-FSPOOK (10 iters)
98.8+03
94.3
85.7
34.5
2.9
CUPN-RN-FSPOON (20 iters)
99.8
98.7+111
86.2+72
24.3
1,4
DSPN-RN-FSPOON (30 iters)
99.8
96.7+22
75.5+123
17.4
0.9
DSPN-RNY RENN-RN-SUM (10 iters)
88.3
43.4
10.047.
11.11
0.0
DSPN-RN RUNN-RN-UUM (20 iters)
87.2+30
42.9+119
5.7
0.0+00
0.0
ASPN-RN-SUT (30 iters)
79.0+119
32,5+124
3,4+22
0,0+a0
0.0=a.
DSPN-RN-MAX (10 iters)
68.0243
4.0+22
0.1
0.0
0.0
DSPN-RN-MAX (20 iters)
66.6245
3.3+18
0.1
0.0
0.0
(30 iters)
64. 1.50
2.3111
0.0.1.0
0.0.00
0.0
Table 12: Average Precision (AP, mean + stdev) for different distance thresholds of the predicted state descriptions over 6 runs. DSPN- results are taken from Zhang et al. (2019a).
Model
APac
APi
APo.s
APo.25
APo.125
DSPN-RNY RN-FSPOOL (10 iters)
72.8+23
59,2
39.0+44
12.4+2s
1.3404
OSPN-RN-FSPOON (20 iters)
84.0245
80.0+49
57.0+121
16,6290
1,6209
DSPN-RN-FSPOOL. (30 iters)
85.2
81.1
47.4+176
10.8
0.6207
DSPN-RN-SHI (10 iters)
44.6 6+38
21.9+48
7.1
1.04a5
0.0+ap
DSPN-RN-SUE (20 iters)
39.6+54
15,2+a4
3,0422
0.3
0.0+ap
DSPN-RN-SUM (30 iters)
30.2192
7.1
0,9408
0.1
0.0
DSPN-RN-MAX (10 iters)
3,0202
0.940.1
0.5
0.1401
0.0200
DSPN-RN-MAX (20 iters)
3.1
1.2+0.1
0.8202
0.3
0.0
DSPN- REPN-RNMAX (30 iters)
3.1
1.2
0.9402
0.3
0.0+00
Results Table II and Table 12 show that the FSPool-based RN encoder is much better than any
of the baselines. The representation of DSPN-RN-FSPOW is good enough that iterating the DSPN algorithm for more steps than the model was trained with can benefit the prediction, while for the baselines it generally just worsens.
18

---

Published as a conference paper at ICLR 2020
This is especially apparent for the harder dataset of state prediction, where more information has to be compressed into the latent space.
H EXPERIMENTAL DETAILS
We provide the code to reproduce all experiments at [redacted].
used FSPool and the unpooling version of with k 20. We guessed this value without tuning, and we did not observe any major differences when we tried to change this on CLEVR to k 5 and 40. W can be initialised in different ways, such by sampling from standard Gaussian. However, for the purposes of starting the model as similarly as possible to the sum pooling baseline on CLEVR and on the graph classification datasets, we initialise W to a matrix of all Is on them.
For almost all experiments,
H. POLYGONS
The polygons are centred on with a radius of 1. The points in the set are randomly permuted to remove any ordering in the set from the generation process that model that is not permutation- invariant or permutation-equivariant could exploit. We use a batch size of 16 for all three models and train it for 10240 steps. We use the Adam optimiser (Kingma & Ba 2015) with 0.001 learning rate and their suggested values for the other optimiser parameters (Py Torch defaults). Weights of linear and convolutional layers are initialised hidden layer is set to 16 and the latent space is set to (it should only need to store the rotation as latent variable). We have also tried much hidden and latent space sizes of 128 when tried to get better results for the baselines.
suggested in Glorot & Bengio (010). The size of every
H.2 MNIST RECONSTRUCTION
We train the training of MNIST for 10 epochs and the shown results come from the test set of MNIST. For an image, the coordinate of pixel is included if the pixel above the mean pixel level of 0.1307 (with pixel levels ranging 0-1). Again, the order of the points are randomised. We did not include results of the linear assignment loss because we did not get the model to converge to results of similar quality the direct MSE loss Chamfer loss, and training time took too long (> day) in order to find better parameters.
The latent space is increased from 1 to 16 and the size of the hidden layers is increased from 16 to 32, All other hyperparameters are the the same as for the Polygons dataset.
H.3 CLEVR
The architecture and hyperparameters come from the third-party open-source implementation avail- able at wthttps://githuu
CLEVR For the RN base- line, the set first expanded into the of all pairs by concatenating the feature vectors of the pair for all pairs of elements in the set. For the Janossy Pooling baseline, we use the model configuration from Murphy al. (2019) that appeared best in their experiments, which uses T-G with LSTM that has [ as neighbourhood size.
wttp/msnnicomm iemesnicoReeaaiinn
The question representation coming from the 256-unit LSTM, processing the question tokens in reverse with each token embedded into 32 dimensions, is concatenated to all elements in the set. Each element this new set first processed by a 4-layer MLP with 512 neurons each layer and ReLU activations. The set of feature vectors is pooled with a pooling method like sum and the output of this is processed with a 3-layer MLP (hidden sizes 512, 1024, and number of answer classes) with ReLU activations. A dropout rate of 0.05 is applied before the last layer of this MLP. Adam is used with starting learning rate of 0.000005, which doubles every 20 epochs until the maximum learning rate of 0.0005 is reached. Weight decay of 0.0001 is applied. The model is trained for 350 epochs.
19

---

Published as a conference paper at ICLR 2020
Table 13: Average of best hyperparameters 10 repeats.
IMDB-B IMDB-M RDT-B RDT-MSK COLLAB MUTAG PROTEINS PTC NCII
GIN-FSPOOL
dimensionality
64.0
64.0
64.0
64.0
64.0
28.8
19.2
28.8
30.4
butch size
66.0
100
45.6
32.0
86.4
89.6
60.8
41.6
128
dropout
0.25
0.15
0.35
0.10
0.40
0.15
0.35
0.20
0.50
GIN-BASE
dimensionality
64.0
64.0
64.0
64.0
64.0
27.2
20.8
25.6
28.8
batch size
86.4
93.2
72.8
70.4
60.8
60.8
128
dropout
0.30
0.15
0.25
0.45
0.40
0.25
0.45
0.20
0.35
H.4 GRAPH CLASSIFICATION
The GIN architecture starts with 5 sequential blocks of graph convolutions. Fach block starts with summing the feature vector of each node's neighbours into the node's own feature vector. Then, an MLP is applied to the feature vectors of all the nodes individually. The details of this MLP were somewhat unclear in Xu et al. (2019) and we chose Linear-Relae We tried Linear-BN EN-ReLL-Limme for both the baseline and the FSPool version. The outputs of each of the blocks are concatenated and pooled, either with (this is as specified in GIN), or with FSPool for both types of datasets. This is followed by BN- Rerea--ReL-Drrpouur
the end. BN- ReLU as well, which gave slightly worse validation results
Lee-Linner--R-U--LI
for the social network datasets, mean for the social network datasets
classifier with softmax output and cross-entropy loss. We used the lorch-geometric library Feey et al. 2018) to implement this model.
The starting learning rate for Adam 0.01 and reduced every 50 epochs. Weights are initialised as suggested in Glorot & Bengio (010). The hyperparameters to choose from are: dropout ratio {0, 0.5), batch size E {32, 128 if bioinformaties dataset hidden sizes of all layers {16,33 and 500 epochs, if social network dataset the hidden size is 64 and 250 epochs. Due to GPU memory limitations we used a batch size 100 instead of 128 for social network datasets. The best hyperparameters
selected based on best average validation accuracy across the 10-fold cross- validatoi,,,,,n, where one the 9 training folds is used as validation set each time. In other words, within one 10-fold tross-validation run the hyperparameters used for the test set are the same, while across the 10 repeats of this with different seeds the best hyperparameters may differ.
H.5 DEEP SET PREDICTION NETWORKS
The architecture and hyperparameters come from the third-party open-source implementation avail- able at phttps:://e //tp:::///tttte t.ub. com/ wwwm/yyamaa Cywp/gennnnnnnnnnoooooooomoo i d/ dspn| The only thing we change from this is replacing the pooling in the RN. All other hyperparameters are kept the same.
The input image is encoded with ResNet-34 with two additional convolutional layers with 512 filters and stride two to obtain a feature vector the image. This feature vector decoded into set using the DSPN algorithm, which requires encoding an intermediate set with the set encoder and performing gradient descent on it. This set encoder creates all pairs sets like in normal RNs, processes each pair with 2-layer MLP with 512 neurons with one ReLU activation in the middle, times in
then pools this into a feature vector. The intermediate set updated with the gradient training, but can be iterated different amount in evaluation. The model is trained minimise the linear assignment loss with the Adam optimiser for 100 epochs using a learning rate of 0.0003.
20


Reviews:
[{"review_id": "rJxESlkpqS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \nThe 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).\n\nSome points I would appreciate to see an improvement:\na. The intro is rough (please see minor-specifics at places that you can improve the exposition).\nb. The Figure1 is not easy to read. The 90degree rotation results in the same set, but as a 'pictorial' image, obviously not.\nc. 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.\nd. 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?\ne. The way you describe the responsibility problem (discontinuity) is very hand-wavy. It would be nice to explicitly it write it in rigorous math.\nf. 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). \n\n\nExplicit Minor Comments on writing:\n(all in introduction)\n-4rth line: \"this\" -> this problem\n-\"Methods like by\" -> Methods like those in \n-\"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.\n-\"good baselines\" -> sophisticated/non-trivial baselines\n\nAppendix. Table 9, max-pool at \\sigma=0, seems to be the best (please use boldface to indicate it).", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HylilvEkcH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors point out an interesting problem that the responsibility between target and input is not continuous and propose an FSPool method to alleviate this problem. The method is simple and easy to implement. \n\nHowever, there are still some questions the authors don't answer. \nFirstly, the authors point out that this issue also exists in some tasks like object detection, but I have no idea how to apply this method in object detection to fix this issue. \n\nSecondly, the authors make a comparison between FSPool and sum pool, average pool, and max pool, however, what about the weighted sum pool? I think it's most similar to FSPool. Maybe I misunderstand here. But please respond at my concerns and I'll change the score accordingly. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HygRLhcx5H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a new approach to representing sets of inputs and a strategy for set auto-encoders. Multiple experiments demonstrate that the new approach performs better than baseline models from recent literature around set representations. The forward encoding strategy is simple enough for a practitioner to implement, and likely to perform better (in terms of training time/gradient flow; if not also test metrics) than existing sum, min, max, mean pooling strategies. It is not substantially more expensive.\n\nThe central trick here is to use a per-feature sort across the set as the representation of the set. In cases of arbitrarily sized sets, the authors provide and use a piecewise linear interpolation strategy, and suggest other possibilities (splines, etc), to induce a uniform representation shape regardless of the input set.\n\nThe decoder uses a similar trick to expand a latent value back to input-set-size, and then leverages the argsort from the input to re-permute the expanded set. They point out that this helps to avoid discontinuities otherwise caused by the 'responsibility problem', i.e. which feature is responsible to describe which input element[s].\n\nThe experiments seem to cover a lot of ground:\n- toy polygon dataset demonstrated to be hard for existing sota in set representations\n- sets of points from mnist images\n- graph classification (competitive with a recent graph convolution approach)\n- integrate with Relation Nets for deep set prediction\n\nThe authors acknowledge (sec 7) the limitation imposed by requiring the input argsort (and size) at the decoder, but point out that even as a representational pre-training or regularization, this strategy can help to improve set prediction strategies not subject to the same constraint (like RN, as in 6.5).\n\nI found the work to be well presented, the experiments to be strong, and I think it will be interesting to the community. Recommend accepting.\n\nFYI: It seems this work has been previously shared, presumably on arxiv, judging from some amount of back-and-forth citations, building upon Zhang et al 2019.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, this paper got strong scores from the reviewers (2 accepts and 1 weak accept).  The paper proposes to address the responsibility problem, enabling encoding and decoding sets without worrying about permutations.  This is achieved using permutation-equivariant set autoencoders and an 'inverse' operation that undoes the sorting in the decoder.  The reviewers all agreed that the paper makes a meaningful contribution and should be accepted.  Some concerns regarding clarity of exposition were initially raised but were addressed during the rebuttal period.  I recommend that the paper be accepted.
Decision: Accept (Poster)