JANOSSY POOLING: LEARNING DEEP PERMUTATION- INVARIANT FUNCTIONS FOR VARIABLE-SIZE INPUTS
We consider a simple and overarching representation for permutation-invariant functions of sequences (or multiset functions). Our approach, which we call Janossy pooling, expresses a permutation-invariant function as the average of a permutation-sensitive function applied to all reorderings of the input sequence. This allows us to leverage the rich and mature literature on permutation-sensitive functions to construct novel and flexible permutation-invariant functions. If carried out naively, Janossy pooling can be computationally prohibitive. To allow computational tractability, we consider three kinds of approximations: canonical orderings of sequences, functions with k-order interactions, and stochastic optimization algorithms with random permutations. Our framework unifies a variety of existing work in the literature, and suggests possible modeling and algorithmic extensions. We explore a few in our experiments, which demonstrate improved performance over current state-of-the-art methods.
I really enjoyed this paper. It takes an idea which at first glance seems to be obviously bad (if you want permutation invariance, build a model that considers all permutations) and uses it to make the important point that the universal approximation results contained in Deep Sets [Zaheer et al. 2017] are not the last word on pooling. Janossy Pooling is intractable for most problems of interest (because it sums over all n! permutations of the input set) so the authors suggest 3 tractable alternatives: canonical orderings, k-ary dependencies and SGD / sampling-based approaches. Only the latter two are explored in detail, so I’ll focus on them:
K-ary dependencies
Functions that are restricted to k-ary dependencies in Janossy Pooling require summing over only |h|! / (|h| - k)! terms - that is they sum over the permutations of subsets of h of length k. In the experimental section, the authors show that this recovers some of the performances lost by using sum / mean pooling (as in Deep Sets), but this suggests the natural question: is it the fact that you’re explicitly modelling higher-order interactions that improves performance? Or is it that you’re doing Janossy pooling over the higher order interactions (i.e. summing over permutations of non-invariant functions)? 
These two effects could be separated by comparing to invariant models that allow higher order interactions. E.g. you could compare against Santoro et al. [2017] who explicitly model pairwise interactions (or similarly any of the graph convolutional models [Kipf and Welling 2016, Hamilton et al 2017, etc.] with a fully connected graph would do the same); similarly Hartford, et al. [2018] allow for k-wise interactions by extending Deep Sets to exchangeable tensors - the permutation invariant analog of k-ary Janossy Pooling. All of these approaches model k-wise interactions through sum-pooling over permutation invariant functions so this lets you address the question - is it the permutation invariance that’s the problem (necessitating k-ary Janossy pooling) or is it the lack of higher-order interaction terms? 
SGD approaches:
I think that the point that the sampling-based approaches are bias with respect to the Janossy sum is important to make and I liked the discussion around it, but I don’t follow the relevance of Proposition 2.2? I see that it gives conditions under which we can expect \pi-SGD to converge, but we aren’t provided with any guidance about how likely those conditions are to be satisfied? Furthermore - these conditions don’t seem to be specific to \pi-SGD - any SGD algorithm with “slightly biased” gradients that satisfy these conditions would converge. The regularization idea is interesting, but it isn’t evaluated so we’re left with theory that doesn’t provide guidance and isn’t evaluated.
Summary:
There are two ways to read this paper:
 1. Janossy pooling as a framework & proposed pooling approach implemented in one of the two ways discussed above.
 2. Janossy pooling as an intractable upper bound on what we might want from a pooling method (with approximations in the form of the LSTM approaches) and a demonstration that our current invariant pooling methods are insufficient.
I liked the paper based on reading (2). Janossy pooling clearly demonstrates limitations to sum / mean pooling which is widely used in practice which shows the need for better alternatives and it is on this basis that I’m arguing for it’s acceptance. My view is that the experimental section is too limited to support reading (1) which asserts that k-ary pooling or LSTM + sampling approaches are the right solution to this problem. 
[Zaheer et al. 2017] - Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and
Alexander Smola. Deep Sets
[Santoro et al. 2017] - Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Tim Lillicrap. A simple neural network module for relational reasoning.
[Kipf and Welling 2016] - Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Net- works
[Hamilton et al 2017] - William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs
[Hartford, et al. 2018] - Jason S. Hartford, Devon R. Graham, Kevin Leyton-Brown, and Siamak Ravanbakhsh. Deep models of interactions across sets