# On the Limitations of Representing Functions on Sets

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

## Key facts

- Cited by 90 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2019.

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

- [You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks](https://mlsanity.com/paper/2106.13264/) (2021)
- [Accurate Learning of Graph Representations with Graph Multiset Pooling](https://mlsanity.com/paper/2102.11533/) (2021)
- [GENESIS-V2: Inferring Unordered Object Representations without Iterative Refinement](https://mlsanity.com/paper/2104.09958/) (2021)
- [Everything is Connected: Graph Neural Networks](https://mlsanity.com/paper/2301.08210/) (2023)
- [Reconstruction for Powerful Graph Representations](https://mlsanity.com/paper/2110.00577/) (2021)
- [Universal Approximation of Functions on Sets](https://mlsanity.com/paper/2107.01959/) (2021)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Message passing all the way up](https://mlsanity.com/paper/2202.11097/) (2022)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [You Never Cluster Alone](https://mlsanity.com/paper/2106.01908/) (2021)
- [Low Dimensional Invariant Embeddings for Universal Geometric Learning](https://mlsanity.com/paper/2205.02956/) (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)
- [Sumformer: Universal Approximation for Efficient Transformers](https://mlsanity.com/paper/2307.02301/) (2023)
- [Graph Neural Networks with Adaptive Readouts](https://mlsanity.com/paper/2211.04952/) (2022)
- [PELICAN: Permutation Equivariant and Lorentz Invariant or Covariant Aggregator Network for Particle Physics](https://mlsanity.com/paper/2211.00454/) (2022)
- [Variable-Input Deep Operator Networks](https://mlsanity.com/paper/2205.11404/) (2022)
- [The Neural Process Family: Survey, Applications and Perspectives](https://mlsanity.com/paper/2209.00517/) (2022)
- [Learning Prototype-oriented Set Representations for Meta-Learning](https://mlsanity.com/paper/2110.09140/) (2021)
- [Multiset-Equivariant Set Prediction with Approximate Implicit Differentiation](https://mlsanity.com/paper/2111.12193/) (2021)
- [Set Norm and Equivariant Skip Connections: Putting the Deep in Deep Sets](https://mlsanity.com/paper/2206.11925/) (2022)
- [ZZ-Net: A Universal Rotation Equivariant Architecture for 2D Point Clouds](https://mlsanity.com/paper/2111.15341/) (2021)
- [Learnable Commutative Monoids for Graph Neural Networks](https://mlsanity.com/paper/2212.08541/) (2022)
- [Practical Equivariances via Relational Conditional Neural Processes](https://mlsanity.com/paper/2306.10915/) (2023)
- [An end-to-end attention-based approach for learning on graphs](https://mlsanity.com/paper/2402.10793/) (2024)
- [Exponential Separations in Symmetric Neural Networks](https://mlsanity.com/paper/2206.01266/) (2022)
- [On permutation-invariant neural networks](https://mlsanity.com/paper/2403.17410/) (2024)
- [SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddings](https://mlsanity.com/paper/2112.05872/) (2021)
- [Task-Adaptive Neural Network Search with Meta-Contrastive Learning](https://mlsanity.com/paper/2103.01495/) (2021)
- [Graph Ordering Attention Networks](https://mlsanity.com/paper/2204.05351/) (2022)

## Abstract (arXiv)

Recent work on the representation of functions on sets has considered the use of summation in a latent space to enforce permutation invariance. In particular, it has been conjectured that the dimension of this latent space may remain fixed as the cardinality of the sets under consideration increases. However, we demonstrate that the analysis leading to this conjecture requires mappings which are highly discontinuous and argue that this is only of limited practical use. Motivated by this observation, we prove that an implementation of this model via continuous mappings (as provided by e.g. neural networks or Gaussian processes) actually imposes a constraint on the dimensionality of the latent space. Practical universal function representation for set inputs can only be achieved with a latent dimension at least the size of the maximum number of input elements.