mlsanityData to 14 Oct 2026

Polynomial Width is Sufficient for Set Representation with High-dimensional Features

arXiv 2307.04001 ↗First posted 8 Jul 2023cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

Set representation has become ubiquitous in deep learning for modeling the inductive bias of neural networks that are insensitive to the input order. DeepSets is the most widely used neural network architecture for set representation. It involves embedding each set element into a latent space with dimension L, followed by a sum pooling to obtain a whole-set embedding, and finally mapping the whole-set embedding to the output. In this work, we investigate the impact of the dimension L on the expressive power of DeepSets. Previous analyses either oversimplified high-dimensional features to be one-dimensional features or were limited to analytic activations, thereby diverging from practical use or resulting in L that grows exponentially with the set size N and feature dimension D. To investigate the minimal value of L that achieves sufficient expressive power, we present two set-element embedding layers: (a) linear + power activation (LP) and (b) linear + exponential activations (LE). We demonstrate that L being poly(N, D) is sufficient for set representation using both embedding layers. We also provide a lower bound of L for the LP embedding layer. Furthermore, we extend our results to permutation-equivariant set functions and the complex field.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 49 of its 69 references that are in the map. First posted on arXiv 8 Jul 2023.

Builds on

49 of 69 references.

References · 49

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Inductive Representation Learning on Large Graphscited by 6,320
  3. 2016PointNet: Deep Learning on Point Sets for 3D Classification and Segmentationcited by 5,248
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2020Point Transformercited by 1,470
  7. 2017Deep Setscited by 1,421
  8. 2016Group Equivariant Convolutional Networkscited by 1,165
  9. 2015Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)cited by 1,070
  10. 2016Geometric deep learning: going beyond Euclidean datacited by 1,048
  11. 2017Sigmoid-Weighted Linear Units for Neural Network Function Approximation in Reinforcement Learningcited by 950
  12. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
37 more
  1. 2016Error bounds for approximations with deep ReLU networkscited by 574
  2. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  3. 2017A simple neural network module for relational reasoningcited by 346
  4. 2018Invariant and Equivariant Graph Networkscited by 346
  5. 2016On the Expressive Power of Deep Neural Networkscited by 306
  6. 2018On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groupscited by 300
  7. 2020Can Graph Neural Networks Count Substructures?cited by 236
  8. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  9. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 183
  10. 2018Universality of Deep Convolutional Neural Networkscited by 176
  11. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  12. 2019On the Universality of Invariant Networkscited by 152
  13. 2018Universal approximations of invariant maps by neural networkscited by 127
  14. 2020Lorentz Group Equivariant Neural Network for Particle Physicscited by 121
  15. 2019Stochastic Optimization of Sorting Networks via Continuous Relaxationscited by 111
  16. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  17. 2018Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputscited by 98
  18. 2015On the Expressive Power of Deep Learning: A Tensor Analysiscited by 97
  19. 2019On the Limitations of Representing Functions on Setscited by 90
  20. 2016Why Deep Neural Networks for Function Approximation?cited by 82
  21. 2019Deep Set Prediction Networkscited by 71
  22. 2019On the Expressive Power of Deep Polynomial Neural Networkscited by 66
  23. 2021Universal Approximation of Functions on Setscited by 62
  24. 2019FSPool: Learning Set Representations with Featurewise Sort Poolingcited by 53
  25. 2022Equivariant Hypergraph Diffusion Neural Operatorscited by 47
  26. 2019On Universal Equivariant Set Networkscited by 45
  27. 2022Low Dimensional Invariant Embeddings for Universal Geometric Learningcited by 38
  28. 2023Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theoremcited by 34
  29. 2019Universal approximations of permutation invariant/equivariant functions by deep neural networkscited by 29
  30. 2021Point Cloud Transformers applied to Collider Physicscited by 23
  31. 2017Linear regression without correspondencecited by 16
  32. 2020Linear Regression without Correspondences via Concave Minimizationcited by 11
  33. 2022Exponential Separations in Symmetric Neural Networkscited by 10
  34. 2019PINE: Universal Deep Embedding for Graph Nodes via Partial Permutation Invariant Set Functionscited by 9
  35. 2021Unlabeled Principal Component Analysis and Matrix Completioncited by 5
  36. 2022What Functions Can Graph Neural Networks Generate?cited by 5
  37. 2020Low-rank matrix completion theory via Plucker coordinatescited by 4

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 5.

6 papers.

  1. 2024On the H"older Stability of Multiset and Graph Neural Networkscited by 6
  2. 2025Advances in Set Function Learning: A Survey of Techniques and Applicationscited by 3
  3. 2025Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddingscited by 2
  4. 2025On the (Non) Injectivity of Piecewise Linear Janossy Poolingcited by 1
  5. 2025Why Neural Network Can Discover Symbolic Structures with Gradient-based Training: An Algebraic and Geometric Foundation for Neurosymbolic Reasoningcited by 1
  6. 2025Monotone and Separable Set Functions: Characterizations and Neural Modelscited by 0