mlsanityData to 7 Oct 2026

Exponential Separations in Symmetric Neural Networks

arXiv 2206.01266 ↗First posted 2 Jun 2022cs.LGcited by 10

Not on the map. Why?

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.

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

Builds on

22 of 33 references.

References · 22

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2016PointNet: Deep Learning on Point Sets for 3D Classification and Segmentationcited by 5,223
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2017Deep Setscited by 1,394
  7. 2019Provably Powerful Graph Networkscited by 385
  8. 2017A simple neural network module for relational reasoningcited by 345
  9. 2016Benefits of depth in neural networkscited by 248
  10. 2020Can Graph Neural Networks Count Substructures?cited by 235
  11. 2019Ab-Initio Solution of the Many-Electron Schr"odinger Equation with Deep Neural Networkscited by 195
  12. 2015The Power of Depth for Feedforward Neural Networkscited by 181
10 more
  1. 2018Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputscited by 96
  2. 2019On the Limitations of Representing Functions on Setscited by 89
  3. 2021Universal Approximation of Functions on Setscited by 62
  4. 2021A Survey of Complex-Valued Neural Networkscited by 61
  5. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 58
  6. 2017Depth Separation for Neural Networkscited by 46
  7. 2019On Universal Equivariant Set Networkscited by 45
  8. 2017Attend and Interact: Higher-Order Object Interactions for Video Understandingcited by 37
  9. 2021Depth separation beyond radial functionscited by 18
  10. 2022Width is Less Important than Depth in ReLU Neural Networkscited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 4; 2024: 0; 2025: 3; 2026: 1.

10 papers.

  1. 2023Representational Strengths and Limitations of Transformerscited by 132
  2. 2023On the Connection Between MPNN and Graph Transformercited by 60
  3. 2022PELICAN: Permutation Equivariant and Lorentz Invariant or Covariant Aggregator Network for Particle Physicscited by 26
  4. 2023Polynomial Width is Sufficient for Set Representation with High-dimensional Featurescited by 6
  5. 2023Symmetric Single Index Learningcited by 5
  6. 2025Advances in Set Function Learning: A Survey of Techniques and Applicationscited by 3
  7. 2022Towards Antisymmetric Neural Ansatz Separationcited by 2
  8. 2025CheMixHub: Datasets and Benchmarks for Chemical Mixture Property Predictioncited by 2
  9. 2025On the (Non) Injectivity of Piecewise Linear Janossy Poolingcited by 1
  10. 2026Quantitative Approximation Rates for Group Equivariant Learningcited by 1