mlsanityData to 14 Oct 2026

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

arXiv 2306.06529 ↗First posted 10 Jun 2023cs.LGcited by 34

Not on the map. Why?

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.

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

25 of 48 references.

References · 25

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2016PointNet: Deep Learning on Point Sets for 3D Classification and Segmentationcited by 5,248
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  5. 2017Deep Setscited by 1,421
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  7. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  8. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  9. 2019Provably Powerful Graph Networkscited by 389
  10. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  11. 2016On the Expressive Power of Deep Neural Networkscited by 306
  12. 2019On the Limitations of Representing Functions on Setscited by 90
13 more
  1. 2023On the Expressive Power of Geometric Graph Neural Networkscited by 90
  2. 2019Deep Set Prediction Networkscited by 71
  3. 2021Universal Approximation of Functions on Setscited by 62
  4. 2019FSPool: Learning Set Representations with Featurewise Sort Poolingcited by 53
  5. 2019On Universal Equivariant Set Networkscited by 45
  6. 2022Low Dimensional Invariant Embeddings for Universal Geometric Learningcited by 38
  7. 2023Is Distance Matrix Enough for Geometric Deep Learning?cited by 22
  8. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 21
  9. 2022Permutation Invariant Representations with Applications to Graph Deep Learningcited by 20
  10. 2022Incompleteness of graph neural networks for points clouds in three dimensionscited by 19
  11. 2022Group-invariant max filteringcited by 18
  12. 2023Complete Neural Networks for Complete Euclidean Graphscited by 10
  13. 2023Three iterations of (d-1)-WL test distinguish non isometric clouds of d-dimensional pointscited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 4; 2024: 12; 2025: 10; 2026: 8.

34 papers.

Sort:

  1. 2024Equivariant Frames and the Impossibility of Continuous Canonicalizationcited by 43
  2. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  3. 2024On the Completeness of Invariant Geometric Deep Learning Modelscited by 11
  4. 2023Universal Representation of Permutation-Invariant Functions on Vectors and Tensorscited by 10
  5. 2024Weisfeiler Leman for Euclidean Equivariant Machine Learningcited by 10
  6. 2023On the power of graph neural networks and the role of the activation functioncited by 8
  7. 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
  8. 2025Fourier Sliced-Wasserstein Embedding for Multisets and Measurescited by 8
  9. 2024On dimensionality of feature vectors in MPNNscited by 7
  10. 2024On the Expressive Power of Sparse Geometric MPNNscited by 7
  11. 2023Polynomial Width is Sufficient for Set Representation with High-dimensional Featurescited by 6
  12. 2024Future Directions in the Theory of Graph Machine Learningcited by 6
22 more
  1. 2024On the H"older Stability of Multiset and Graph Neural Networkscited by 6
  2. 2023Neural approximation of Wasserstein distance via a universal architecture for symmetric and factorwise group invariant functionscited by 4
  3. 2024Sequential Signal Mixing Aggregation for Message Passing Graph Neural Networkscited by 3
  4. 2025Bi-Lipschitz Ansatz for Anti-Symmetric Functionscited by 3
  5. 2025Geometric Kolmogorov-Arnold Superposition Theoremcited by 2
  6. 2025Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddingscited by 2
  7. 2024A note on the VC dimension of 1-dimensional GNNscited by 1
  8. 2025On the (Non) Injectivity of Piecewise Linear Janossy Poolingcited by 1
  9. 2026How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?cited by 1
  10. 2024Fourier Sliced-Wasserstein Embedding for Multisets and Measurescited by 0
  11. 2025Can we ease the Injectivity Bottleneck on Lorentzian Manifolds for Graph Neural Networks?cited by 0
  12. 2025On the Lipschitz Continuity of Set Aggregation Functions and Neural Networks for Setscited by 0
  13. 2025Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Wincited by 0
  14. 2025Message Passing on the Edge: Towards Scalable and Expressive GNNscited by 0
  15. 2025Monotone and Separable Set Functions: Characterizations and Neural Modelscited by 0
  16. 2026MATE: Solving Contextual Markov Decision Processes with Memory of Accumulated Transition Embeddingscited by 0
  17. 2026Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Themcited by 0
  18. 2026A Unifying Relational Perspective on Expressive Lottery Ticketscited by 0
  19. 2026Finite Probes Suffice: Identifiability and Universality for Weight-Space Learningcited by 0
  20. 2026Generative sequence modeling for infinite memory processes via predictive statescited by 0
  21. 2026Universal interpolation for deep residual self-attention networkscited by 0
  22. 2026Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecturecited by 0