On the (Non) Injectivity of Piecewise Linear Janossy Pooling
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 23 of its 30 references that are in the map. First posted on arXiv 26 May 2025.
Builds on
23 of 30 references.
References · 23
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2021Convex optimizationcited by 2,479
- 2017Deep Setscited by 1,394
- 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
- 2019Provably Powerful Graph Networkscited by 385
- 2017A simple neural network module for relational reasoningcited by 345
- 2018Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputscited by 96
- 2021Universal Approximation of Functions on Setscited by 62
- 2022Low Dimensional Invariant Embeddings for Universal Geometric Learningcited by 38
- 2023Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theoremcited by 33
- 2022Permutation Invariant Representations with Applications to Graph Deep Learningcited by 20
- 2022Group-invariant max filteringcited by 18
11 more
- 2024On the Expressive Power of Spectral Invariant Graph Neural Networkscited by 15
- 2022Exponential Separations in Symmetric Neural Networkscited by 10
- 2023Complete Neural Networks for Complete Euclidean Graphscited by 10
- 2023Universal Representation of Permutation-Invariant Functions on Vectors and Tensorscited by 10
- 2024Weisfeiler Leman for Euclidean Equivariant Machine Learningcited by 10
- 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
- 2025Fourier Sliced-Wasserstein Embedding for Multisets and Measurescited by 8
- 2024On the Expressive Power of Sparse Geometric MPNNscited by 7
- 2023Polynomial Width is Sufficient for Set Representation with High-dimensional Featurescited by 6
- 2024On dimensionality of feature vectors in MPNNscited by 6
- 2024On the H"older Stability of Multiset and Graph Neural Networkscited by 6
Built on by
Citing papers per year: 2025: 1.
1 paper.