# On the (Non) Injectivity of Piecewise Linear Janossy Pooling

arXiv: https://arxiv.org/abs/2505.20150 · HTML: https://mlsanity.com/paper/2505.20150/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 30 references that are in the map.
- First posted on arXiv 26 May 2025.

## Builds on (most cited first, 23 of 23)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [A simple neural network module for relational reasoning](https://mlsanity.com/paper/1706.01427/) (2017)
- [Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs](https://mlsanity.com/paper/1811.01900/) (2018)
- [Universal Approximation of Functions on Sets](https://mlsanity.com/paper/2107.01959/) (2021)
- [Low Dimensional Invariant Embeddings for Universal Geometric Learning](https://mlsanity.com/paper/2205.02956/) (2022)
- [Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem](https://mlsanity.com/paper/2306.06529/) (2023)
- [Permutation Invariant Representations with Applications to Graph Deep Learning](https://mlsanity.com/paper/2203.07546/) (2022)
- [Group-invariant max filtering](https://mlsanity.com/paper/2205.14039/) (2022)
- [On the Expressive Power of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2406.04336/) (2024)
- [Exponential Separations in Symmetric Neural Networks](https://mlsanity.com/paper/2206.01266/) (2022)
- [Complete Neural Networks for Complete Euclidean Graphs](https://mlsanity.com/paper/2301.13821/) (2023)
- [Universal Representation of Permutation-Invariant Functions on Vectors and Tensors](https://mlsanity.com/paper/2310.13829/) (2023)
- [Weisfeiler Leman for Euclidean Equivariant Machine Learning](https://mlsanity.com/paper/2402.02484/) (2024)
- [FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network](https://mlsanity.com/paper/2410.09118/) (2024)
- [Fourier Sliced-Wasserstein Embedding for Multisets and Measures](https://mlsanity.com/paper/2504.02544/) (2025)
- [On dimensionality of feature vectors in MPNNs](https://mlsanity.com/paper/2402.03966/) (2024)
- [On the Expressive Power of Sparse Geometric MPNNs](https://mlsanity.com/paper/2407.02025/) (2024)
- [Polynomial Width is Sufficient for Set Representation with High-dimensional Features](https://mlsanity.com/paper/2307.04001/) (2023)
- [On the H"older Stability of Multiset and Graph Neural Networks](https://mlsanity.com/paper/2406.06984/) (2024)

## Built on by (most cited first, 1 of 1)

- [Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings](https://mlsanity.com/paper/2510.22186/) (2025)

## Abstract (arXiv)

Multiset functions, which are functions that map multisets to vectors, are a fundamental tool in the construction of neural networks for multisets and graphs. To guarantee that the vector representation of the multiset is faithful, it is often desirable to have multiset mappings that are both injective and bi-Lipschitz. Currently, there are several constructions of multiset functions achieving both these guarantees, leading to improved performance in some tasks but often also to higher compute time than standard constructions. Accordingly, it is natural to inquire whether simpler multiset functions achieving the same guarantees are available. In this paper, we make a large step towards giving a negative answer to this question. We consider the family of k-ary Janossy pooling, which includes many of the most popular multiset models, and prove that no piecewise linear Janossy pooling function can be injective. On the positive side, we show that when restricted to multisets without multiplicities, even simple deep-sets models suffice for injectivity and bi-Lipschitzness.