# Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 48 references that are in the map.
- First posted on arXiv 10 Jun 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [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)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [On the Expressive Power of Geometric Graph Neural Networks](https://mlsanity.com/paper/2301.09308/) (2023)
- [Deep Set Prediction Networks](https://mlsanity.com/paper/1906.06565/) (2019)
- [Universal Approximation of Functions on Sets](https://mlsanity.com/paper/2107.01959/) (2021)
- [FSPool: Learning Set Representations with Featurewise Sort Pooling](https://mlsanity.com/paper/1906.02795/) (2019)
- [On Universal Equivariant Set Networks](https://mlsanity.com/paper/1910.02421/) (2019)
- [Low Dimensional Invariant Embeddings for Universal Geometric Learning](https://mlsanity.com/paper/2205.02956/) (2022)
- [Is Distance Matrix Enough for Geometric Deep Learning?](https://mlsanity.com/paper/2302.05743/) (2023)
- [Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks](https://mlsanity.com/paper/2211.03232/) (2022)
- [Permutation Invariant Representations with Applications to Graph Deep Learning](https://mlsanity.com/paper/2203.07546/) (2022)
- [Incompleteness of graph neural networks for points clouds in three dimensions](https://mlsanity.com/paper/2201.07136/) (2022)
- [Group-invariant max filtering](https://mlsanity.com/paper/2205.14039/) (2022)
- [Complete Neural Networks for Complete Euclidean Graphs](https://mlsanity.com/paper/2301.13821/) (2023)
- [Three iterations of (d-1)-WL test distinguish non isometric clouds of d-dimensional points](https://mlsanity.com/paper/2303.12853/) (2023)

## Built on by (most cited first, 30 of 34)

- [Equivariant Frames and the Impossibility of Continuous Canonicalization](https://mlsanity.com/paper/2402.16077/) (2024)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [On the Completeness of Invariant Geometric Deep Learning Models](https://mlsanity.com/paper/2402.04836/) (2024)
- [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)
- [On the power of graph neural networks and the role of the activation function](https://mlsanity.com/paper/2307.04661/) (2023)
- [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)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [On the H"older Stability of Multiset and Graph Neural Networks](https://mlsanity.com/paper/2406.06984/) (2024)
- [Neural approximation of Wasserstein distance via a universal architecture for symmetric and factorwise group invariant functions](https://mlsanity.com/paper/2308.00273/) (2023)
- [Sequential Signal Mixing Aggregation for Message Passing Graph Neural Networks](https://mlsanity.com/paper/2409.19414/) (2024)
- [Bi-Lipschitz Ansatz for Anti-Symmetric Functions](https://mlsanity.com/paper/2503.04263/) (2025)
- [Geometric Kolmogorov-Arnold Superposition Theorem](https://mlsanity.com/paper/2502.16664/) (2025)
- [Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings](https://mlsanity.com/paper/2510.22186/) (2025)
- [A note on the VC dimension of 1-dimensional GNNs](https://mlsanity.com/paper/2410.07829/) (2024)
- [On the (Non) Injectivity of Piecewise Linear Janossy Pooling](https://mlsanity.com/paper/2505.20150/) (2025)
- [How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?](https://mlsanity.com/paper/2601.21882/) (2026)
- [Fourier Sliced-Wasserstein Embedding for Multisets and Measures](https://mlsanity.com/paper/2405.16519/) (2024)
- [Can we ease the Injectivity Bottleneck on Lorentzian Manifolds for Graph Neural Networks?](https://mlsanity.com/paper/2504.00142/) (2025)
- [On the Lipschitz Continuity of Set Aggregation Functions and Neural Networks for Sets](https://mlsanity.com/paper/2505.24403/) (2025)
- [Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win](https://mlsanity.com/paper/2506.03919/) (2025)
- [Message Passing on the Edge: Towards Scalable and Expressive GNNs](https://mlsanity.com/paper/2510.13615/) (2025)
- [Monotone and Separable Set Functions: Characterizations and Neural Models](https://mlsanity.com/paper/2510.23634/) (2025)
- [MATE: Solving Contextual Markov Decision Processes with Memory of Accumulated Transition Embeddings](https://mlsanity.com/paper/2605.17431/) (2026)
- [Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them](https://mlsanity.com/paper/2605.23446/) (2026)
- [A Unifying Relational Perspective on Expressive Lottery Tickets](https://mlsanity.com/paper/2608.18819/) (2026)

## Abstract (arXiv)

Injective multiset functions have a key role in the theoretical study of machine learning on multisets and graphs. Yet, there remains a gap between the provably injective multiset functions considered in theory, which typically rely on polynomial moments, and the multiset functions used in practice, which rely on textitneural moments unicodex2014 whose injectivity on multisets has not been studied to date. In this paper, we bridge this gap by showing that moments of neural networks do define injective multiset functions, provided that an analytic non-polynomial activation is used. The number of moments required by our theory is optimal essentially up to a multiplicative factor of two. To prove this result, we state and prove a textitfinite witness theorem, which is of independent interest. As a corollary to our main theorem, we derive new approximation results for functions on multisets and measures, and new separation results for graph neural networks. We also provide two negative results: (1) moments of piecewise-linear neural networks cannot be injective multiset functions; and (2) even when moment-based multiset functions are injective, they can never be bi-Lipschitz.