# Exponential Separations in Symmetric Neural Networks

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 33 references that are in the map.
- First posted on arXiv 2 Jun 2022.

## Builds on (most cited first, 22 of 22)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [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)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Ab-Initio Solution of the Many-Electron Schr"odinger Equation with Deep Neural Networks](https://mlsanity.com/paper/1909.02487/) (2019)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs](https://mlsanity.com/paper/1811.01900/) (2018)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [Universal Approximation of Functions on Sets](https://mlsanity.com/paper/2107.01959/) (2021)
- [A Survey of Complex-Valued Neural Networks](https://mlsanity.com/paper/2101.12249/) (2021)
- [Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks](https://mlsanity.com/paper/1610.09887/) (2016)
- [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017)
- [On Universal Equivariant Set Networks](https://mlsanity.com/paper/1910.02421/) (2019)
- [Attend and Interact: Higher-Order Object Interactions for Video Understanding](https://mlsanity.com/paper/1711.06330/) (2017)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [Width is Less Important than Depth in ReLU Neural Networks](https://mlsanity.com/paper/2202.03841/) (2022)

## Built on by (most cited first, 10 of 10)

- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [On the Connection Between MPNN and Graph Transformer](https://mlsanity.com/paper/2301.11956/) (2023)
- [PELICAN: Permutation Equivariant and Lorentz Invariant or Covariant Aggregator Network for Particle Physics](https://mlsanity.com/paper/2211.00454/) (2022)
- [Polynomial Width is Sufficient for Set Representation with High-dimensional Features](https://mlsanity.com/paper/2307.04001/) (2023)
- [Symmetric Single Index Learning](https://mlsanity.com/paper/2310.02117/) (2023)
- [Advances in Set Function Learning: A Survey of Techniques and Applications](https://mlsanity.com/paper/2501.14991/) (2025)
- [Towards Antisymmetric Neural Ansatz Separation](https://mlsanity.com/paper/2208.03264/) (2022)
- [CheMixHub: Datasets and Benchmarks for Chemical Mixture Property Prediction](https://mlsanity.com/paper/2506.12231/) (2025)
- [On the (Non) Injectivity of Piecewise Linear Janossy Pooling](https://mlsanity.com/paper/2505.20150/) (2025)
- [Quantitative Approximation Rates for Group Equivariant Learning](https://mlsanity.com/paper/2602.20370/) (2026)

## Abstract (arXiv)

In this work we demonstrate a novel separation between symmetric neural network architectures. Specifically, we consider the Relational Network~parencitesantoro2017simple architecture as a natural generalization of the DeepSets~parencitezaheer2017deep architecture, and study their representational gap. Under the restriction to analytic activation functions, we construct a symmetric function acting on sets of size N with elements in dimension D, which can be efficiently approximated by the former architecture, but provably requires width exponential in N and D for the latter.