# Universal Approximation of Functions on Sets

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

## 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 (most cited first, 26 of 26)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space](https://mlsanity.com/paper/1706.02413/) (2017)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [SE(3)-Transformers: 3D Roto-Translation Equivariant Attention Networks](https://mlsanity.com/paper/2006.10503/) (2020)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [A simple neural network module for relational reasoning](https://mlsanity.com/paper/1706.01427/) (2017)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets](https://mlsanity.com/paper/1903.05662/) (2019)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups](https://mlsanity.com/paper/2104.09459/) (2021)
- [Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks](https://mlsanity.com/paper/1810.00825/) (2018)
- [Universal approximations of invariant maps by neural networks](https://mlsanity.com/paper/1804.10306/) (2018)
- [Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs](https://mlsanity.com/paper/1811.01900/) (2018)
- [Non-Local Graph Neural Networks](https://mlsanity.com/paper/2005.14612/) (2020)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [Group Equivariant Stand-Alone Self-Attention For Vision](https://mlsanity.com/paper/2010.00977/) (2020)
- [On Universal Equivariant Set Networks](https://mlsanity.com/paper/1910.02421/) (2019)
- [LambdaNet: Probabilistic Type Inference using Graph Neural Networks](https://mlsanity.com/paper/2005.02161/) (2020)
- [Set2Graph: Learning Graphs From Sets](https://mlsanity.com/paper/2002.08772/) (2020)
- [HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs](https://mlsanity.com/paper/1809.02589/) (2018)
- [Learning Functions over Sets via Permutation Adversarial Networks](https://mlsanity.com/paper/1907.05638/) (2019)
- [End-to-end Recurrent Multi-Object Tracking and Trajectory Prediction with Relational Reasoning](https://mlsanity.com/paper/1907.12887/) (2019)

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

- [On the Connection Between MPNN and Graph Transformer](https://mlsanity.com/paper/2301.11956/) (2023)
- [Mosaic-SDF for 3D Generative Models](https://mlsanity.com/paper/2312.09222/) (2023)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem](https://mlsanity.com/paper/2306.06529/) (2023)
- [Likelihood-Free Parameter Estimation with Neural Bayes Estimators](https://mlsanity.com/paper/2208.12942/) (2022)
- [Explainable Equivariant Neural Networks for Particle Physics: PELICAN](https://mlsanity.com/paper/2307.16506/) (2023)
- [The Neural Process Family: Survey, Applications and Perspectives](https://mlsanity.com/paper/2209.00517/) (2022)
- [Practical Equivariances via Relational Conditional Neural Processes](https://mlsanity.com/paper/2306.10915/) (2023)
- [Neural Bayes Estimators for Irregular Spatial Data using Graph Neural Networks](https://mlsanity.com/paper/2310.02600/) (2023)
- [Translation Equivariant Transformer Neural Processes](https://mlsanity.com/paper/2406.12409/) (2024)
- [Exponential Separations in Symmetric Neural Networks](https://mlsanity.com/paper/2206.01266/) (2022)
- [Complete Neural Networks for Complete Euclidean Graphs](https://mlsanity.com/paper/2301.13821/) (2023)
- [On permutation-invariant neural networks](https://mlsanity.com/paper/2403.17410/) (2024)
- [On the Optimal Memorization Capacity of Transformers](https://mlsanity.com/paper/2409.17677/) (2024)
- [Deep Neural Network Approximation of Invariant Functions through Dynamical Systems](https://mlsanity.com/paper/2208.08707/) (2022)
- [Graph Ordering Attention Networks](https://mlsanity.com/paper/2204.05351/) (2022)
- [Fourier Sliced-Wasserstein Embedding for Multisets and Measures](https://mlsanity.com/paper/2504.02544/) (2025)
- [Fast computation of permutation equivariant layers with the partition algebra](https://mlsanity.com/paper/2303.06208/) (2023)
- [A Unified Framework for Discovering Discrete Symmetries](https://mlsanity.com/paper/2309.02898/) (2023)
- [GradMetaNet: An Equivariant Architecture for Learning on Gradients](https://mlsanity.com/paper/2507.01649/) (2025)
- [Polynomial Width is Sufficient for Set Representation with High-dimensional Features](https://mlsanity.com/paper/2307.04001/) (2023)
- [Recurrent Aggregators in Neural Algorithmic Reasoning](https://mlsanity.com/paper/2409.07154/) (2024)
- [Equilibrium Aggregation: Encoding Sets via Optimization](https://mlsanity.com/paper/2202.12795/) (2022)
- [End-to-End Large Portfolio Optimization for Variance Minimization with Neural Networks through Covariance Cleaning](https://mlsanity.com/paper/2507.01918/) (2025)
- [Scalable Set Encoding with Universal Mini-Batch Consistency and Unbiased Full Set Gradient Approximation](https://mlsanity.com/paper/2208.12401/) (2022)
- [Neural approximation of Wasserstein distance via a universal architecture for symmetric and factorwise group invariant functions](https://mlsanity.com/paper/2308.00273/) (2023)
- [Learning multi-modal generative models with permutation-invariant encoders and tighter variational objectives](https://mlsanity.com/paper/2309.00380/) (2023)
- [In-Context In-Context Learning with Transformer Neural Processes](https://mlsanity.com/paper/2406.13493/) (2024)
- [Generative Distribution Embeddings: Lifting autoencoders to the space of distributions for multiscale representation learning](https://mlsanity.com/paper/2505.18150/) (2025)
- [High-Dimensional Learning Dynamics of Quantized Models with Straight-Through Estimator](https://mlsanity.com/paper/2510.10693/) (2025)

## 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.