mlsanityData to 14 Oct 2026

Universal Approximation of Functions on Sets

arXiv 2107.01959 ↗First posted 5 Jul 2021cs.LG stat.MLcited by 62

Not on the map. Why?

Abstract (arXiv)

Modelling functions of sets, or equivalently, permutation-invariant functions, is a long-standing challenge in machine learning. Deep Sets is a popular method which is known to be a universal approximator for continuous set functions. We provide a theoretical analysis of Deep Sets which shows that this universal approximation property is only guaranteed if the model's latent space is sufficiently high-dimensional. If the latent space is even one dimension lower than necessary, there exist piecewise-affine functions for which Deep Sets performs no better than a na"ive constant baseline, as judged by worst-case error. Deep Sets may be viewed as the most efficient incarnation of the Janossy pooling paradigm. We identify this paradigm as encompassing most currently popular set-learning methods. Based on this connection, we discuss the implications of our results for set learning more broadly, and identify some open questions on the universality of Janossy pooling in general.

Key facts. Cited by 62 papers in the map (data through 14 Oct 2026). Builds on 26 of its 36 references that are in the map. First posted on arXiv 5 Jul 2021.

Builds on

26 of 36 references.

References · 26

  1. 2017Attention Is All You Needcited by 60,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2016PointNet: Deep Learning on Point Sets for 3D Classification and Segmentationcited by 5,248
  4. 2017PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Spacecited by 4,401
  5. 2013Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computationcited by 2,079
  6. 2017Deep Setscited by 1,421
  7. 2020SE(3)-Transformers: 3D Roto-Translation Equivariant Attention Networkscited by 607
  8. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 509
  9. 2019Provably Powerful Graph Networkscited by 389
  10. 2017A simple neural network module for relational reasoningcited by 346
  11. 2018Invariant and Equivariant Graph Networkscited by 346
  12. 2019Understanding Straight-Through Estimator in Training Activation Quantized Neural Netscited by 231
14 more
  1. 2020Fast Differentiable Sorting and Rankingcited by 197
  2. 2021A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groupscited by 187
  3. 2018Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networkscited by 132
  4. 2018Universal approximations of invariant maps by neural networkscited by 127
  5. 2018Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputscited by 98
  6. 2020Non-Local Graph Neural Networkscited by 91
  7. 2019On the Limitations of Representing Functions on Setscited by 90
  8. 2020Group Equivariant Stand-Alone Self-Attention For Visioncited by 63
  9. 2019On Universal Equivariant Set Networkscited by 45
  10. 2020LambdaNet: Probabilistic Type Inference using Graph Neural Networkscited by 44
  11. 2020Set2Graph: Learning Graphs From Setscited by 16
  12. 2018HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphscited by 6
  13. 2019Learning Functions over Sets via Permutation Adversarial Networkscited by 4
  14. 2019End-to-end Recurrent Multi-Object Tracking and Trajectory Prediction with Relational Reasoningcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 9; 2023: 16; 2024: 13; 2025: 15; 2026: 8.

62 papers.

Sort:

By area:

  1. 2023On the Connection Between MPNN and Graph Transformercited by 61
  2. 2023Mosaic-SDF for 3D Generative Modelscited by 48
  3. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  4. 2023Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theoremcited by 34
  5. 2022Likelihood-Free Parameter Estimation with Neural Bayes Estimatorscited by 32
  6. 2023Explainable Equivariant Neural Networks for Particle Physics: PELICANcited by 24
  7. 2022The Neural Process Family: Survey, Applications and Perspectivescited by 23
  8. 2023Practical Equivariances via Relational Conditional Neural Processescited by 13
  9. 2023Neural Bayes Estimators for Irregular Spatial Data using Graph Neural Networkscited by 13
  10. 2024Translation Equivariant Transformer Neural Processescited by 13
  11. 2022Exponential Separations in Symmetric Neural Networkscited by 10
  12. 2023Complete Neural Networks for Complete Euclidean Graphscited by 10
38 more
  1. 2024On permutation-invariant neural networkscited by 10
  2. 2024On the Optimal Memorization Capacity of Transformerscited by 10
  3. 2022Deep Neural Network Approximation of Invariant Functions through Dynamical Systemscited by 9
  4. 2022Graph Ordering Attention Networkscited by 8
  5. 2025Fourier Sliced-Wasserstein Embedding for Multisets and Measurescited by 8
  6. 2023Fast computation of permutation equivariant layers with the partition algebracited by 7
  7. 2023A Unified Framework for Discovering Discrete Symmetriescited by 7
  8. 2025GradMetaNet: An Equivariant Architecture for Learning on Gradientscited by 7
  9. 2023Polynomial Width is Sufficient for Set Representation with High-dimensional Featurescited by 6
  10. 2024Recurrent Aggregators in Neural Algorithmic Reasoningcited by 6
  11. 2022Equilibrium Aggregation: Encoding Sets via Optimizationcited by 5
  12. 2025End-to-End Large Portfolio Optimization for Variance Minimization with Neural Networks through Covariance Cleaningcited by 5
  13. 2022Scalable Set Encoding with Universal Mini-Batch Consistency and Unbiased Full Set Gradient Approximationcited by 4
  14. 2023Neural approximation of Wasserstein distance via a universal architecture for symmetric and factorwise group invariant functionscited by 4
  15. 2023Learning multi-modal generative models with permutation-invariant encoders and tighter variational objectivescited by 4
  16. 2024In-Context In-Context Learning with Transformer Neural Processescited by 4
  17. 2025Generative Distribution Embeddings: Lifting autoencoders to the space of distributions for multiscale representation learningcited by 4
  18. 2025High-Dimensional Learning Dynamics of Quantized Models with Straight-Through Estimatorcited by 4
  19. 2025Advances in Set Function Learning: A Survey of Techniques and Applicationscited by 3
  20. 2025On the Relationship Between Robustness and Expressivity of Graph Neural Networkscited by 3
  21. 2025Adaptive Canonicalization with Application to Invariant Anisotropic Geometric Networkscited by 3
  22. 2021SHIFT15M: Fashion-specific dataset for set-to-set matching with several distribution shiftscited by 2
  23. 2022Towards Antisymmetric Neural Ansatz Separationcited by 2
  24. 2023Probabilistic Invariant Learning with Randomized Linear Classifierscited by 2
  25. 2023Tabular Few-Shot Generalization Across Heterogeneous Feature Spacescited by 2
  26. 2024GraphSPNs: Sum-Product Networks Benefit From Canonical Orderingscited by 2
  27. 2024SetPINNs: Set-based Physics-informed Neural Networkscited by 2
  28. 2025Beyond Discreteness: Sample Complexity Analysis of Straight-Through Estimator for 1-bit Quantizationcited by 2
  29. 2025Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddingscited by 2
  30. 2026Distribution-Conditioned Transportcited by 2
  31. 2023Stretched and measured neural predictions of complex network dynamicscited by 1
  32. 2024Consensus Learning with Deep Sets for Essential Matrix Estimationcited by 1
  33. 2025Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphscited by 1
  34. 2025On the (Non) Injectivity of Piecewise Linear Janossy Poolingcited by 1
  35. 2026How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?cited by 1
  36. 2026Quantitative Approximation Rates for Group Equivariant Learningcited by 1
  37. 2026It Just Takes Two: Scaling Amortized Inference to Large Setscited by 1
  38. 2026Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Poolingcited by 1

50 most cited of 62 All 62 (JSON)