Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs

By Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak A. Rao, Bruno Ribeiro. 2018

214 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

Citations in the corpus

How Powerful are Graph Neural Networks? (2018, background): “There are other non-standard and complicated neighbor aggregation schemes that we do not cover in this paper, e.g. , Graph Attention Networks (Velickovic et al., 2018) and LSTM pooling (Hamilton et al., 2017a; Murphy et al., 2018).”
Neural Operator: Graph Kernel Network for Partial Differential Equations (2020, unknown): “Gilmer et al., 2017, Veliˇckovi´c et al., 2017, Murphy et al., 2018].”
Learn to Predict Sets Using Feed-Forward Neural Networks (2020, background): “Most existing approaches on set learning [7], [11], [12] have focused on the problem of encoding a set with a feed-forward neural network by using, e.”
FSPool: Learning Set Representations with Featurewise Sort Pooling (2019, methodology): “This can be a significant bottleneck in what these functions can represent efficiently, particularly when relations between elements of the set need to be modeled [17; 32].”
Probabilistic Symmetries and Invariant Neural Networks (2020, background): “Deterministic examples have appeared in the neural networks literature (Shawe-Taylor, 1989; Zaheer et al., 2017; Ravanbakhsh et al., 2017; Murphy et al., 2019), and the theory developed in here establishes the necessary and sufficient functional forms for permutation invariance and equivariance, in ”
Relational Pooling for Graph Representations (2019, methodology): “2019), the authors propose k -ary pooling wherein computational complexity is reduced from summing over all permutations of the input sequence to just subsequences of size k .”
Generalization and Representational Limits of Graph Neural Networks (2020, background): “Murphy et al. (2019) constructed new permutation-invariant functions for variable-size inputs, and suggested some approximations.”
On the Equivalence between Positional Node Embeddings and Structural Graph Representations (2019, background): “Corollary 5 is a direct consequence of Theorem 2, with Murphy et al. (2019) showing RP-GNN as a concrete method to do so.”
On Learning Sets of Symmetric Elements (2020, background): “In another related work, Murphy et al. (2018) suggested to model permutation-invariant functions as an average of permutation-sensitive functions.”
On the Limitations of Representing Functions on Sets (2019, background): “(2017), and Qi et al. (2017a) which leverage the structure illustrated in Figure 1.”
Conditional Structure Generation through Graph Variational Generative Adversarial Nets (2019, background): “Moreover, none of the existing methods really solve the fundamental challenge of graph permutation invariance [26, 42, 15, 48, 30] during their translation between graph structures and representations, due to the facts that their embedding spaces or generated graphs are essentially not permutation-i”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “This inspired a large body of research on stronger variants of GNNs [20, 91, 85, 86, 92, 93, 94] which provably overcome these limitations.”
Accurate predictions on small data with a tabular foundation model (2025, unknown): “To reduce variance from this source, we apply a permutation sampling approximation of Janossy Pooling at inference time, in which we average the outputs of N j feature permutations, with N j = 24 in our experiments 64 .”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, background): “Murphy et al. (Murphy et al., 2019b;a) and Sato et al. (Sato et al., 2020) extended the expressivity of GNNs by considering all possible permutations of a graph’s adjacency matrix, or adding random node features, respectivley.”
Multipole Graph Neural Operator for Parametric Partial Differential Equations (2020, background): “GNN and non-sparse graphs: A multitude of techniques such as graph convolution, edge convolution, attention, and graph pooling, have been developed for improving GNNs [25, 22, 19, 41, 30].”
Graph Representation Learning (2020, methodology): “To alleviate this issue, Murphy et al. [2019] propose the Relational Pooling (RP) approach, which involves marginalizing over all possible node permutations.”