mlsanityData to 7 Oct 2026

Universal Representation of Permutation-Invariant Functions on Vectors and Tensors

arXiv 2310.13829 ↗First posted 20 Oct 2023cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

A main object of our study is multiset functions -- that is, permutation-invariant functions over inputs of varying sizes. Deep Sets, proposed by citezaheer2017deep, provides a universal representation for continuous multiset functions on scalars via a sum-decomposable model. Restricting the domain of the functions to finite multisets of D-dimensional vectors, Deep Sets also provides a universal approximation that requires a latent space dimension of O(ND) -- where N is an upper bound on the size of input multisets. In this paper, we strengthen this result by proving that universal representation is guaranteed for continuous and discontinuous multiset functions though a latent space dimension of O(ND). We then introduce identifiable multisets for which we can uniquely label their elements using an identifier function, namely, finite-precision vectors are identifiable. Using our analysis on identifiable multisets, we prove that a sum-decomposable model for general continuous multiset functions only requires a latent dimension of 2DN. We further show that both encoder and decoder functions of the model are continuous -- our main contribution to the existing work which lack such a guarantee. Also this provides a significant improvement over the aforementioned O(ND) bound which was derived for universal representation of continuous and discontinuous multiset functions. We then extend our results and provide special sum-decomposition structures to universally represent permutation-invariant tensor functions on identifiable tensors. These families of sum-decomposition models enables us to design deep network architectures and deploy them on a variety of learning tasks on sequences, images, and graphs.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 18 of its 68 references that are in the map. First posted on arXiv 20 Oct 2023.

Builds on

18 of 68 references.

References · 18

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2020A Generalization of Transformer Networks to Graphscited by 653
  3. 2017Value-Decomposition Networks For Cooperative Multi-Agent Learningcited by 490
  4. 2018Invariant and Equivariant Graph Networkscited by 339
  5. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  6. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  7. 2021Equivariant Subgraph Aggregation Networkscited by 154
  8. 2021GraphiT: Encoding Graph Structure in Transformerscited by 146
  9. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  10. 2018Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputscited by 96
  11. 2023On the Expressive Power of Geometric Graph Neural Networkscited by 89
  12. 2019Reinforcement Learning Based Graph-to-Sequence Model for Natural Question Generationcited by 57
6 more
  1. 2019On Universal Equivariant Set Networkscited by 45
  2. 2022Low Dimensional Invariant Embeddings for Universal Geometric Learningcited by 38
  3. 2023Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theoremcited by 33
  4. 2023Complete Neural Networks for Complete Euclidean Graphscited by 10
  5. 2022What Functions Can Graph Neural Networks Generate?cited by 5
  6. 2016Deep Learning with Sets and Point Cloudscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 5; 2026: 2.

10 papers.

  1. 2025Fourier Sliced-Wasserstein Embedding for Multisets and Measurescited by 8
  2. 2024DE-HNN: An effective neural model for Circuit Netlist representationcited by 7
  3. 2024On the H"older Stability of Multiset and Graph Neural Networkscited by 6
  4. 2025A universal compression theory for lottery ticket hypothesis and neural scaling lawscited by 2
  5. 2025Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddingscited by 2
  6. 2025On the (Non) Injectivity of Piecewise Linear Janossy Poolingcited by 1
  7. 2024Fourier Sliced-Wasserstein Embedding for Multisets and Measurescited by 0
  8. 2025Contextual Scenario Generation for Two-Stage Stochastic Programmingcited by 0
  9. 2026The Illusion of Replacement: Rethinking Specialized Machine Learning Models in the Foundation Model Eracited by 0
  10. 2026Learning the Geometry of Collider Events with Metric-Aware Deep Setscited by 0