Exponential Separations in Symmetric Neural Networks
Authors: Aaron Zweig
Joan Bruna
Venue: NeurIPS 2022 Accept (2022)
Keywords: deepsets
relational network
self-attention
symmetric function
set-based
separation

Abstract: In this work we demonstrate a novel separation between symmetric neural network architectures.  Specifically, we consider the Relational Network~\parencite{santoro2017simple} architecture as a natural generalization of the DeepSets~\parencite{zaheer2017deep} 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. 

Exponential Separations in Symmetric Neural Networks
Aaron Zweig Courant Institute of Mathematical Sciences New York University az831@nyu. edu
Joan Bruna Center for Data Science New York University
brunaécims nyu. edu
Abstract
In this work we demonstrate novel separation between symmetric neural network architectures. Specifically, consider the Relational Network (21) architecture as a natural generalization the DeepSets [32 architecture, and study their representational gap. Under the restriction to analytic activation functions, construct a symmetric function acting on sets of size N with elements dimension D, which can be efficiently approximated by the former architecture, but provably requires width exponential in N and D for the latter.
Introduction
The modern success of deep learning can in part be attributed to architectures that enforce appropriate invariance. Invariance to permutation of the input, i.e. treating the input as an unordered set, is desirable property when learning symmetric functions in such fields as particle physics and population statistics. The simplest architectures that enforce permutation invariance treat each set element individually without allowing for interaction, captured by the popular DeepSet model [18 32
Several architectures explicitly enable interaction between set elements, the simplest being the Relational Networks [2I] that encode pairwise interaction. This may be understood as an instance of self-astention, the mechanism underlying Transformers (27), which have emerged as powerful generic neural network architectures to process a wide variety of data, from image patches to text to physical data. Specifically, Set Transformers [12] are special instantiations of Transformers, made permutation equivariant by omitting positional encoding of inputs, and using self-attention for pooling.
Both the DeepSets and Relational Networks architectures are universal approximators for the class of symmetric functions. But empirical evidence suggests inherent advantage of symmetric networks using self-attention in synthetic settings [16). on point cloud data [2] and in quantum chemistry (17). In this work, we formalize this question terms of approximation power, and explicitly construet symmetric functions which provably require exponentially-man neurons in the DeepSets model, yet efficiently approximated with self-attention.
This exponential separation bears notable differences from typical separation results. In particular, while the expressive power of vanilla neural network is characterized by depth and width, expres- siveness symmetric networks is controlled particularly by symmetric width. contrast to depth separations of vanilla neural networks [7]. in this work we observe width separations, where the weaker architectures (even with arbitrary depth) require exponential symmetric width match expressive power of stronger architectures.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Summary of Contributions In this work:
We demonstrate width separation between the DeepSets and Relational Network archi- tectures, where the former requires symmetric width > poly(N, NN D) to approximate family of analytic symmetric functions, while the latter can approximate with polynomial efficiency. This also answers an open question of high-dimensional DeepSets representation posed in Wagstaff et [30]
We introduce extension of the Hall inner product high dimensions that preserves low-degree orthogonality of multisymmetric powersum polynomials, which may be of independent interest.
2 Setup and Main Result
2.1
Symmetric Architectures
21
37
(rlae)
22g
P
P
4
6h (xrg)
25
xx
(olitw))
(a) DeepSets with symmetric width
(b) Relational Network with symmetric width L.
Figure I: Architectural diagram for Sym, (left) and Symž (right)
To introduce the symmetric architectures, we must first characterize how to treat sets as inputs. We will consider sets of size N, where each element of the set is vector of dimension D. In particular, we will represent set as a matrix X E DDxN Thus, each column vector F,, E C is an element of the set. Note that consider complex-valuee inputs because the natural inner product over symmetric polynomials integrates over the complex unit circle, see Macdonald [4] or Theorem 4.3
function f D - C is symmetric if s(X) ((XII) for any permutation matrix IT E N iee. if f is invariant permuting the columns of X. In other words, symmetric function treats the input X as an unordered set of column vectors. Given the symmetric width parameter L, we consider two primary symmetric architectures:
Definition 2.1. Let Sym, denote the class of singleton symmetric networks with symmetric width L, Le. functions f of the form:
S(X) = (1)))))))..(()))))
(X) = Σ (x())))
(2)
n=1
where (t1 CD
CHL and Ch - C are arbitrary neural networks with analytic activations.
The class Sym, is exactly the architecture of DeepSets 32
restricted to analytic activations. However, we introduce this notation to differentiate this class from the more expressive architectures that allow for pairwise interaction among set elements.
1, then é Sym, is universal approximator for any analytic symmetric function 19 Therefore we will primarily be interested in the expressive power of Sym, for L < L*
From the theory of symmetric polynomials, if L (N+D)

---

Definition 2.2. Let Sym,, denote the class of pairwise symmetric networks with symmetric width L, i.e. functions f of the form:
f(x) (((1()))...,x((())
(3)
.....
(x) E
('n Ine)
n,d!=1
where {eh CDD activations.
Cf and p Ct. C are arbitrary neural networks with analytic
Similarly, the class Symž is exactly the architecture of Relational Pooling 21 with analytic activa- tions. We note this architecture also equivalent the 2-ary instantiation of Janossy Pooling [16].
2.2
Main Result
Our main result demonstrates an exponential separation, where Sym, requires exponentially large symmetric width L to match the expressive power of the class Sym, for L = We choose norms to make this separation as prominent as possible: there is hard function that can be approximated in Symž in the infinity norm, but cannot be approximated in Sym, even in an appropriately chosen L2 norm with respect some non-trivial data distribution.
We require one activation assumption to realize the Symž, approximation:
Assumption 2.3. The activation a C > is analytic, and for fixed D, N there exist two- layer neural networks f1, J2 using both with O (D² + D ()) width and O(D log D) bounded weights, such that:
f2(E) (1 (E///A))i(DNNNT))) 5- 1/4 (
sup (f((E) -2 1
sup
Se
(5)
E/4
Essentially this assumption guarantees that networks built with the analytic activation able efficiently approximate the map g 5²_ and, a truncated form of the finite Blaschke product (8) with { = 4. We show in Lemma G.3 that the exp activation satisfies this assumption.
Theorem 2.4 (Exponential width-separation,, Fix N and D > 1, and a non-trivial data distribution I. on x N copies of the unit complex circle (SN)
Then there exists an analytic symmetric function g CDXN + C such that (ggll = 1 and:
For L < NN= (==eexp(((min(), VN)),
1
min || alli.( fESm
12
There exists Symi, with L parameterized with activation that satisfies Assumption 2.3 with width poly(N, D, 1/e), depth O(log D), and max weight O(D log D) such that over S1) DxN;
Il -l Sc
Remark 1. The lower bound is completely independent of the width and depth of the parameterized networks {11) and p. The only parameter that the theorem restricts is the symmetric width L. This is in sharp contrast to the separations of vanilla networks (7), where there is a natural trade-off between width and depth.
Remark 2. In the upper bound, consider the network J E Sym?, to have width and depth in the usual sense of vanilla neural networks, where the parameterized maps (1/1) and obey the width, depth, and weight bounds given.
3

---

Related Work
3.1 Depth Separation
Numerous works have studied the difference in expressive power between different neural network architectures. Many of these works center on the representational gap between two-layer and three- layer networks 7 In particular, recent works have focused on generalizing the family functions that realize these separations, to various radial functions 20 and non-radial functions [28).
separate line of work considers separations between networks when the depth varies polynomi- ally (24). Notably, Vardi, Yehudai, and Shamir (26) demonstrates that depth has greater impact on expressivity than width, in the case of vanilla neural networks.
3.2 Symmetric Architectures
We primarily consider the symmetric neural network parameterization as introduced in DeepSets 33] with PointNet[18 similar symmetric parameterization using different pooling function. Simple linear equivariant layers were also introduced in Zaheer et
In the context of relationships between objects an image, the first symmetric architecture enabling explicit pairwise interaction was introduced in Santoro al. (21). More complicated symmetric architectures, allowing for higher-order interaction and more substantial equivariant layers, were built top of attention primitives [12 13). And the notion of explicit high-order interactions between set elements before symmetrizing is formalized in the architecture of Janossy pooling [16].
Symmetric architectures are generalized by graph neural networks the complete graph.
10 22 under the restriction to
3.3 Symmetric Network Expressivity
The dependence of representational power on the symmetric width parameter was first demonstrated in the D = 1 case. Under the strong condition L < N, it was proven there are symmetric functions which cannot be exactly represented by DeepSets network (29), and this was later strengthened to functions which cannot be approximated in the infinity norm to arbitrary precision (30).
The work introducing Janossy pooling [16] also includes a theoretical result showing singleton networks cannot exactly represent some particular pairwise symmetric network. Crucially how- ever, this result is restricted to simplified, non-universal symmetric architecture excluding the transformation, and therefore does not characterize the real-world architectures given above.
The question of expressiveness in symmetric networks may also be generalized to graph neural networks, with a focus distinguishing non-isomorphic graphs as compared to the Weissfeler- Lehman test [3] I and calculating invariants such as substructure counting In particular, one may understand expressiveness in symmetric networks incorporating pairwise interaction as the ability to leamn functions of the complete graph decorated with edge features.
3.4 Symmetric Polynomial Theory
Our proofs rely on the technical machinery of symmetric polynomial theory. thoroughly characterized Macdonald (14). In particular, we utilize the integral representation of the product as introduced in Section A Because this integral is defined over the complex unit circle, we consequently consider complex-vaile neural networks
Hall Inner
The connection of symmetric networks to the powersum polynomials was first observed Zaheer et al. 32 and likewise the multisymmetric powersum polynomials have been applied in higher dimensional

---

symmetric problems [15 23). The algebraic properties of the multisymmetric powersum polynomials are well-studied, for example as a basis of higher dimensional symmetric polynomials (19) and through their algebraic dependencies (6] However, to the best of our knowledge this is the first work to apply the Hall inner product to symmetrie neural networks, and to extend this inner product to yield low-degree orthogonality over the multisymmetric polynomials.
Warmup: One-dimensional set elements
To begin, we consider the simpler case where D = 1, i.c. where we learn a symmetric function acting on a set of scalars. It was already observed in Zaheer al. (32) that the universality of DeepSets could be demonstrated by approximatngg the network with symmetric polynomials. We first demonstrate that through this approximation, can relate the symmetric width L to expressive power.
4.1 Symmetric Polynomials
In order to approximate symmetric networks by symmetric polynomials, we choose suitable basis. The powersum polynomials serve as the natural choice, as their structure matches that a singleton symmetric network, and they obey very nice orthogonality properties that detail below. Definition 4.1. For and x E CN,, the normalized powersum polynomial is defined as
N
(x(x) = Vk n=1
with (x) =
classical result in symmetric polynomial theory is the existence of an L2 inner product that grants orthogonality for products of powersums. To make this notion explicit and keep track of products, index products with partitions.
Definition 4.2. An integer partition X is non-increasing, finite sequence of positive integers A1 2 A2 2 Au. The weight of the partition is given by |k] Σk ) The length of partition (()) is the number of terms in the sequence.
Then we characterize product of powersums by:
(x(x) = (I())IIPA) PA (x)
PI.
(8)
This notation intentionally also allows for the empty partition, such that if X Ø then px 1. All together, we can now state the following remarkable fact:
Theorem 4.3 (14, Chapter VI (9.10)) There exists a L2(dv) inner product (for some probability measure v) such that, for partitions X, 1 with [X| S N:
(px.Pa)v = ZA 2
where: 2x is some combinatorial constant.
We index this inner product with V because it is written as expectation with respect density proportional to the squared Vandermonde polynomial (see Section A for the precise definition). This inner product may also be considered the finite-variable specialization of the Hall inner product, defined on symmetric polynomials over infinitely many variables [14] Chapter (4.5)).
It's easy to check that the degree of px is equal to [X]. So this theorem states that the powersum terms PA are "almost" an orthogonal basis, except for correlation between two nigh-degred terms.
Let us remark that we assume analytic activations for the sake of this theorem, as the orthogonality property does not hold for symmetric polynomials with negative exponents. However, in exchange for that assumption we can apply this very powerful inner product, that ultimately results in the irrelevance of network depth.
5

---

4.2 Projection Lemma
Before proceed to prove representational lower bound, need one tool to better understand E Sym,, Utilizing the orthogonality properties of the inner product -vv allows us to project any Sym, to simplified form, while keeping straightforward dependence L.
uniformly convergent power series (with constant term) ((x) Lis1 CskP& (z). We claim (P2P1, Φ0)v /v O. Indeed, expanding Φ², one exclusively gets terms the and because the partition { ka} is of different length than {2, 13, they are clearly distinct partitions so by orthogonality (P2P1, Pk, Pk.PkpPks> 0.
For example, consider
form
Motivated by this observation, we can project f to only contain products of two terms. Let us introduce P1 be the orthogonal projection onto span (pr : t N/22), and P2 to be the orthogonal projection onto spam(1pup)
S t,t' - N/2
Lemma 4,4. Given any J E Sym we may choose coefficients Vij over i S S L, and symmetric polynomials di over i L, such that:
L
Paf Σ
Uyy (1((P)))
(10)
$53
4.3 Rank Lemma
Given the reduced form of f above, we may now go about lower bounding its approximation error to a given function g.
By the properties of orthogonal projection, we have || gll? 2 1| 9)ll.. And by Parseval's theorem, the function approximation error [P2j P29 1i equals
Σ ESE
((pt.: IpiPellv/
(Pel,
PePe
(P29,
PiPe
PePe llv
Rearranging the orthogonal coefficients in the form of matrices, we have the following fact: Lemma 4.5, Given any f E Sym,, and such that P2g = 9. we have the bound
P2f - P29l1i 2 F -
(11)
where F, G E CN/2XN12 are matrices with entries Fo P Gw (P2g.PePrly: Furthermore, F has maximum rank L.
The significance of this lemma is the rank constraint: it implies that choosing symmetric width L corresponds to maximum rank L on the matrix F. From here we can use standard arguments about low-rank approximation in the Frobenius
to yield lower bound.
4.4 Separation in one-dimensional case
Our main goal in this section is construct hard symmetric function that cannot be efficiently approximated by Sym, for < N/4. is not particularly expensive for the symmetric width L to scale linearly with the set size N: however, we will use the same proof structure prove Theorem 2.4 which will require L to scale exponentially.
Theorem 4.6. For D
2L
max min I /ESm
2
(12)
In particular, for L we recover constant lower bound of

---

Proof (sketch). Choose such that P2g = g. applying Lemma 4.5
Then because P2 is an orthogonal projection and
min /eSym
| gVl 2
min f
||2// - P22llV
(13)
1
min rank( F)SL
| 1
(14)
2
We note that IIp.Pelly = ((t,t) 2, so the choice of = 1 E PiPt can be seen to obey
VN
llallv = 1, and implies that G is the scaled identity matrix 2 1 E N/2xx Then by standard
properties of the SVD:
2
min SESymy
|| -9lli 2
min F
F
VN T|?
(15)
min (F)
|| 11/
(16)
N/2
N/2 (N/2 - L)
(17)
1 2L
(18)
N
Proof Sketch of Main Result
5.1
Challenges for High-dimensional Set Elements
We'd like to strengthen this separation in several ways:
Generalize to the D case,
Realize separation where the symmetric width L must scale exponentially in N and D, showing that Sym, is infeasible,
Show the hard function g can nevertheless be efficiently approximated in Sym for L polynomial in N and
First, order to approximate via polynomials in the high-dimenionsal case, we will require the high-dimensional analogue of powersum polynomials:
Definition 5.1. For multi-index E NP,, the normalized multisymmetric powersum polynomial is defined as:
(x(
ΣI
ad dn
(19)
a
So the plan is to find high-dimensional analogue of Lemma 4.4 and Lemma 4.5 using
multisymmetric powersum polynomials, mimic the proof of the D = 1 case, and then additionally show the hard function is efficiently computable in the pairwise symmetric architecture. Note that because the algebraic basis of multisymmetric powersum polynomials is of size I.* (N+D) we can expect an exponential separation when apply a similar rank argument
We subtract one in order to discount the constant polynomial.

---

5.2 Sketch of Main result (lower bound)
Because are in high dimensions, we cannot simply apply the restricted Hall inner product introduced in Theorem 4.33] To the best of our knowledge, there is no standard generalization of the Hall inner product to multi-symmetrie polynomials that preserves the orthogonality property. For the main technical ingredient in the high-dimensional case we introduce a novel generalization, which builds two inner products.
First, we introduce new input distribution v over set inputs X CxN and induce an L2 inner product:
(f = Ex-~ [[(x)x(x]]
(20)
We use this inner product to measure the approximation егтоr of Sym,, That is, we seek lower bound minsesym, Il. All... for suitable choice of hard function g.
We can now apply an analogue of Lemma 4.4 to project f to a simplified form. But we cannot immediately apply an analogue of Lemma 4.5 as it relied on Parseval's 's theorem and the low-degree multisymmetrii powersum polynomials are not orthogonal in this inner product. Put another way, if we represent (:, A as matrix in the basis of low-degree multisymmetric powersums, it will be positive-definite but include some off-diagonal terms.
The idea to now introduce new inner product with different input distribution V/
(f.g)A, = Ex [(x))(x)]
(21)
and define the bilinear form
- (f.))
(22)
Typically positive-definitennss is lost when subtracting two inner products, but we prove that (, + an inner product when restricted particular subspace of symmetric polynomials (see Theo- rem rem[D.) D.3). Furthermore, the careful choice of y and 1/ cancels the off-diagona correlation of different
multisymmetric powersums, so they are orthogonal under this new inner product (..
By the norm domination -| 2 ||- ll.. we are able to pass from the former Lg norm to the latter norm that obeys orthogonality, and apply an analogue of the Rank Lemma 4.5) Thus we derive a lower bound using any hard function g whose corresponding matrix G (built from orthogonal coefficients) is diagonal and high-rank. And because the total number of polynomials is L", the rank argument now yields an exponential separation.
Based on this proof, we have much freedom in our choice of g. By choosing its coefficients in the basis of multisymmetric powersum polynomials, it's easy to enforce the conditions that G is diagonal and high-rank for variety of possible functions. However, ensuring that g is not pathological (i.c. that it is bounded and Lipschitz), and can be efficiently approximated in Sym?, requires more careful choice.
5.3 Sketch of Main Result (upper bound)
remains to approximate the hard function g with a network from Sym First we must make a choice of g in particular.
Based on the lower bound proof, the desiderata for g is that it is supported exclusively on terms of the form PaPa over many values of a, as this induces a diagonal and high-rank matrix G in an analogue of Lemma 4.5 Furthermore, by simple algebra one can confirm that Pa (X)p..X)) add , so g supported on these polynomials can clearly be written in the form of network in Sym?. This structure of y guarantees difficult approximation, and is akin the radial structure of the hard functions introduced in works on depth separation 7
Jo] En.n'
8

---

We must however be careful in our choice of for the matrix G to be high-rank, must be supported on exponentially many powersum polynomials. But this could make l|gllo exponentially large, and therefore challenging to approximate efficiently with a network from Sym
We handle this difficulty by defining g in a different way. We introduce a finite Blaschke product 1/14 (E()) = E74-1: a function that analytically maps the unit complex circle to itself. Then the choice
9(X)
Σ II p (ddd)
(23)
1=
ensures that ||g|lc. lIglla, and Lip(g) are polynomial in N, D. for approximation error (see Lemma E.3) Furthermore, again from simple algebra it is clear that is only supported on terms of the form Pa. So remains to show that the induced diagonal matrix G is effectively high rank, which follows from expanding the Blaschke products.
Satisfied that this choice of g will meet the desiderata for the lower bound, and has no pathological behavior, it remains to construct E Symž for I. = 1 that approximates g. That is, choose 4/1 and p so that g(X) ~ p (En, 4/1 (Zn, zw)). Clearly we may take p to be the identity, and 1/1 (I,, Fw') approximate I (dddd ). which is straightforwardly calculated in depth Oloo D) by performing successive multiplications in a binary-tree like structure (see Theorem
Ultimately, we use slight variant of this function for the formal proof. Because the orthogonality of our newly introduced inner product ) only holds for low-degree polynomials, we must truncate high-degree terms of g; we confirm in Appendix [ that this truncation nevertheless preserves the properties we care about.
Discussion
In this work, we've demonstrated how symmetric width captures more of the expressive power of symmetric networks than depth when restricted to analytic activations, by evincing an exponential separation between two of the most common architectures that enforce permutation invariance.
The most unusual property of this result is the complete independence of depth, owing to the unique orthogonality properties of the restricted Hall inner product when paired with the assumption of analyticity. This stands in contrast to the case of vanilla neural networks, for which separations beyond small depth would resolve open questions in circuit complexity suspected to be quite hard [25). Furthermore, the greater dependence on width than depth a unique property to symmetric networks, whereas the opposite is true for vanilla networks [26]
A natural extension would be to consider the simple equivariant layers introduced in Zaheer et al. (32), which we suspect will not substantially improve approximation power of Sym,, Furthermore, allowing for multiple such equivariant layers. this network becomes exactly akin to Graph Con- volutional Network [10] on complete graph, whereas Sym? corresponds to a message passing network as capable of interpreting edge features.
6.1 Limitations
The major limitation of this result is the restriction to analytic functions. Although analytic symmetric functions nevertheless appear crucially in the study of exactly solvable quantum systems (2) IT]. this assumption may be be overly strict for general problems of learning symmetric functions. We nevertheless conjecture that these bounds will still hold even allowing for non-analytic activations, and consider this an exciting question for future work. Additionally, whether the hard function can be efficiently learned with gradient descent remains unclear, and future work could touch on the learnability.

---

This work has been partially supported by the Alfred P. Sloan Foundation, NSF RI-1816753, NSF CAREER CIF-1845360, and NSF CCF-1814524.
Acknowledgements::
References
[1] Joshua Bassey, Lijun Qian, and Xianfang Li. "A survey of complex-valued neural networks". In: arXiv preprint 1rXiv:2101.2221 (2021).
[2] Mathieu Beau and Adolfo del Campo. "Parent Hamiltonians of Jastrow wavefunctions". In: SciPost Physics Core 4.4 (2021), p. 030.
[3] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. "Can graph neural networks count substructures?" In: Advances in neural information processing systems 33 (2020), pp. 10383- 10395.
[4] Amit Daniely, "Depth separation for neural networks". In: Conference Learning Theory. PMLR. 2017, pp. 690-696.
[5] Persi Diaconis and Mehrdad Shahshahani. "On the eigenvalues of random matrices". In: Journal of Applied Probability 31.A (1994), pp- 49-62.
[6] Mátyás Domokos. "Vector invariants of a class of pseudo-reflection groups and multisymmetrrc syzygies". In: arXiv preprint arXiv:0706. 2154 (2007).
[7] Ronen Eldan and Ohad Shamir. "The power of depth for feedforward neural networks", In: Conference on learning theory. PMLR. 2016, pp. 907-940.
[8] John Garnett. Bounded analytic functions. Vol. 236. Springer Science & Business Media, 2007.
[9] Justin Gilmer et al. "Neural message passing for quantum chemistry". In: International conference on machine learning. PMLR. 2017, pp. 1263-1272.
[10] Thomas N Kipf and Max Welling. "Semi- supervied classification with graph convolutional networks". In: arXiv preprint
(00:::609.00000 (2016).
[11] Edwin Langmann. "A method to derive explicit formulas for elliptic generalization of the Jack polynomials". In: arXiv preprint math-pi/he ph/0511015 (2005).
[12] Juho Lee et al. "Set transformer: A framework for attention-based
cermutation-invarinn neural networks". In: International Conference on Machine Learning. PMLR. 2019, pp. 3744-3753.
[13] Chih-Yar Ma et al. "Attend and interact: Higher-order object interactions for video understand- ing". In: Proceedings of the IEEE Conference on Computer Vision and Paltern Recognition. 2018, pp. 6790-6800.
[14] lan Grant Macdonald. Symmetric functions and Hall polynomials. Oxford university press, 1998.
[15] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. "Provably powerful graph networks". In: Advances in neural information processing systems 32 (2019).
[16] Ryan L Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. "Janossy pooling: Learning deep vermutation-invatte invariiant functions for variable-size inputs". In: arXiv preprint 181 1.01900 (2018).
[17] David Pfau, James S Spencer, Alexander GDG Matthews, and W Matthew C Foulkes. "Ab initio solution of the many-electron Schrödinger equation with deep neural networks". In: Physical Review Research 2.3 (2020), 033429.
[18) Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. "Pointnet: Deep learning on point sets for 3d classification and segmentation". In: Proceedings of the IEEE conference on computer vision and pattern recognition. 2017, pp. 652-660.
[19] David Rydh. "A minimal set of generators for the ring of multisymmetric functions".. In: Annales de l'institul Fourier. Vol. 57. 6. 2007, pp. 1741-1769.
[20] Itay Safran and Ohad Shamir. "Depth-wine wiith tradeoffs in approximating natural functions with neural networks". In: International conference on machine learning. PMLR. 2017, pp. 2979- 2987.
[21] Adam Santoro et al. "A simple neural network module for relational reasoning", " In: Advances neural information processing systems 30 (2017).
[22] Franco Scarselli et al. "The graph neural network model". In: IEEE transactions on neural networks 20.1 (2008), pp. 61-80.
10

---

[23] Nimrod Segol and Yaron Lipman. "On universal equivariant set networks". In: arXiv preprint arXiv:1910.0244 02421 (2019).
[24] Matus Telgarsky. "Benefits depth in neural networks". In: Conference on learning theory. PMLR. 2016, pp. 1517-1539.
[25] Gal Vardi, Daniel Reichman, Toniann Pitassi, and Ohad Shamir. "Size and depth separation in approximating benign functions with neural networks". In: Conference on Learning Theory.
PMLR. 2021, pp. 4195-4223.
[26] Gal Vardi, Gilad Yehudai, and Ohad Shamir. "Width Less Important than Depth in ReLU Neural Networks". In: arXiv preprint (tth:2202.03844 (2022).
[27] Ashish Vaswani al. "Attention is all you need". In: Advances in neural information process- ing systems 30 (2017).
[28) Luca Venturi, Samy Jelassi, Tristan Ozuch, and Joan Bruna. "Depth separation beyond radial functions". In: arXiv preprint arXiv:2/02.0166/ (2021).
[29] Edward Wagstaff et al. "On the limitations of representing functions on sets". In: International Conference on Machine Learning. PMLR. 2019, pp. 6487-6494.
[30] Edward Wagstaff al. "Universal approximation of functions on sets". In: Journal of Machine Learning Research 23.15 51 (2022), pp. 1-56.
[31] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. "How powerful graph neural networks?" In: arXiv preprint arXiv:1810.00823 (2018).
[32] Manzil Zaheer et al. "Deep sets". In: Advances in neural information processing systems 30
(2017).
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6.1
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "y6KENdf0wMQ", "reviewer": "Reviewer_YvXW", "summary": "The paper studies the expressive power of symmetric neural networks used to compute functions on sets, specifically Relational Networks and DeepSets architectures. An exponential separation result is given where a certain function can be represented efficiently using a Relational Network with symmetric width L=1, yet cannot be approximated by a DeepSet architecture to accuracy better than a constant unless its symmetric width is exponential in either of $N$, the size of the set; or $\\sqrt{D}$, where $D$ is the dimension of each element.", "questions": "- Can you motivate the study of this problem further? I'm curious to know if similarly to Eldan and Shamir, there are known practical problems where Relational Networks outperform DeepSets. Such examples will make the paper better motivated in my opinion.\n\n- Are complex networks used in practice in any context? This will make the assumption on using complex numbers much more justified.\n\n- In the paper, you clearly state the analyticity assumption as a weakness in your paper. You do not discuss, however, what commonly used activations satisfy your assumption. Is Assumption 2.3 satisfied by any sigmoidal activation, e.g. logistic, tanh, or arctan? Providing an example beyond the exponential activation will make this weakness much more mild.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is well-written and easy to follow.\n\n- The proof technique used bears a certain (subjective) elegance. The mathematical tools used in the proof which leverage symmetric polynomials to establish the main result seem like the natural machinery for studying the expressive power of symmetric architectures, and the proof idea seems like a clever use of these tools.\n\n\n\nWeaknesses:\n\n- It feels like the paper does not motivate the study of the problem addressed in it sufficiently. To give a concrete comparison, the separation in [1] is well-motivated since it was widely observed that deeper architectures are much more successful in many learning tasks. It is not clear if this is also the case when using Relational Networks instead of DeepSets.\n\n- The proof technique seems to make an essential use of complex numbers and analytic activations. While the authors are overall transparent about these weaknesses, it doesn't feel like they are properly discussed.\n\n- It was shown in [2] that certain functions used to separate depth cannot be learned using gradient methods. Since the construction used to approximate the target function using a Relational Network seems intricate and also uses a relatively deep architecture, I'm not sure if it can be learned efficiently. While I find the result in the paper interesting nevertheless, I think it would be appropriate to add a comment about this.\n\n\nCitations used:\n\n[1] - Eldan and Shamir: The Power of Depth for Feedforward Neural Networks\n\n[2] - Malach et al.: The Connection Between Approximation, Depth Separation and Learnability in Neural Networks", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dWJKFl5zxM", "reviewer": "Reviewer_WQz6", "summary": "This paper provides a novel result on the relative expressiveness of two popular architectures for symmetric functions, Deep Sets (pooling over individual inputs) and Relational Networks (pooling over pairs of inputs).", "questions": "The main result in this paper shows that there exists a \"hard\" function $g$ for which Deep Sets requires an exponentially greater symmetric width than Relational Networks. Is your lower bound on the symmetric width for Deep Sets the worst possible, i.e. does the symmetric width required by your function $g$ suffice for Deep Sets to model any symmetric function? Is there a known bound on the required symmetric width for Relational Networks to model any symmetric function?\n", "limitations": "I see no potential for negative societal impact. The authors briefly note a major limitation of their result. I think that this brief note is adequate, since it correctly identifies the most important possible strengthening of the result and explicitly leaves it open for future work.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a very well-written paper. The narrative is easy to follow and the key ideas are explained clearly. The key result is novel and interesting, and motivation is provided in the text. This paper will certainly be of significant interest to researchers working with symmetric neural networks.\n\nMost of the paper is devoted to setting up mathematical context or describing the mathematics of proving the main result. The mathematical content here is explained and structured very clearly, but perhaps a small amount of additional space could be given over to motivation and practical context for the result, which, although present, is currently a little lacking.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AMJhTMmmTyQ", "reviewer": "Reviewer_c2Zx", "summary": "The paper studies expressivity capabilities of neural networks that belong to the class of symmetric neural networks. Two most prominent examples that are used as motivation for the current work is the so-called DeepSets and Relational Networks. Even though these are universal approximators for representing symmetric functions, what are the depth/width tradeoffs and approximation guarantees? This question reflects the analogous questions for standard feedforward neural networks. \n\nThe main contribution of the paper is to explicitly construct symmetric functions which provably require exponentially-many neurons in the\nDeepSets model, yet are efficiently approximated with self-attention. The crucial parameter controling the expressivity of the network here, is the so-called \"symmetric width\" and this leads to a conceptually different set of results in comparison to standard depth vs width tradeoffs.\n\nThe difference in the two architectures is presented by eq. (2) vs eq. (4), where the latter allows for pairwise interactions among set elements.\n\nUnder plausible assumptions, the main result of the paper is formally Theorem 2.4 is to provide a family of analytic symmetric functions g which leads to two important properties in order to prove separation results. The first part says that \"singleton symmetric networks\" (i.e., those that don't allow for pairwise interactions) are insufficient to approximate g unless they are exponentially large in terms of their symmetric width, whereas the second part says that a simple \"pairwise symmetric network\" will incur negligible loss when trying to approximate g. The notions of error used are: for the lower bound in the first part, the authors used the notion of L2 error under a suitable data distribution, and for the second part in the upper bound they use the infinity norm error.", "questions": "-complex values vs real values? One question that comes up has to do with the fact that the input is complex-valued. How does this affect the statement of the result for real-valued neural nets? Ie does the construction break down if we only cared about real valued networks?\n\n-omissions in literature/failed to do comparisons: \n1. In Chulhee Yun et al. (\"Are Transformers universal approximators of sequence-to-sequence functions?\") the authors study sequence-to-sequence models and ask about the approximation/representation capabilities. Why did the authors fail to compare against this paper, given that Set Transformers  are special instantiations of Transformers?\n2. There are also works in expressivity that manage to show separations based on topological properties of the function-to-be-represented. These hold for feedforward neural nets and use zonotope theory (see UNDERSTANDING DEEP NEURAL NETWORKS WITH\nRECTIFIED LINEAR UNITS by Arora et al.) or fixed-point arguments in dynamical systems (see Better Depth-Width Trade-offs for Neural Networks through the lens of Dynamical Systems by Chatziafratis et al.). Is there hope to use approach taken there to show separations for symmetric nets? What is the crucial property of symmetric nets being exploited in the present paper? Is the main observation of the paper the fact that the pairwise interaction is a \"complexity\" measure of sorts, that cannot be simulated by the \"singleton symmetric net\"?\n3. Can the authors elaborate more on why the L2 error lower bound was used in eq. (6) rather than the stronger lower bound of L1? From Telgarsky's work cited (Benefits of depth in neural networks) it seems that L1 is the stronger guarantee. What is the main technical bottleneck for obtaining L2? Thank you!\n\n\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "-solid contribution for theory of expressivity in neural nets that offers new perspective and techniques to a different set of architectures. \n-conceptually interesting the fact that the result bears differences with standard results of feedforward neural nets separations\n\nWeaknesses:\n-limited literature comparisons e.g., Chulhee Yun et al. (\"Are Transformers universal approximators of sequence-to-sequence functions?\")?\n-L2 error bound instead of L1 error bound?\n-please see questions below. \n\nOverall, the reviewer thinks that the paper has to offer sth new to the much needed theory of neural nets for symmetic function representation and that the paper does so in a technically solid manner.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1R-5YyJ5y88", "reviewer": "Reviewer_Ddfp", "summary": "This paper considers the representational power of neural network functions. It considers two types of network architectures: the DeepSets architecture, which treats the inputs in a permutation invariant manner; and the Relational Network architecture, which allows for pairwise interaction among the inputs. The question considered in this paper is to compare the representation power of these two types of architectures.\n\nThe main result is a \"width separation\" between the DeepSets and the Relational Network architectures. It shows that there exists a function such that\n- for any width less than $exp(min(input\\ dimension, \\sqrt{input\\ set\\ size})$, the best function from the DeepSets family incurs a constant error.\n- on the other hand, with $poly(input\\ dimension, input\\ set\\ size)$ width, the Relational Network could represent the same function up to arbitrary small error.\n\nThe lower bound for the one-dimensional case is as follows:\n- the \"DeepSets\" networks with width $L$ restricts the space of functions to within some space of rank relating to $L$; so for a \"high\" rank function, its orthogonal projection to this rank $L$ space could still be quite large\n\nThe high-dimensional case requires using a high-dimensional powersum polynomials. However, the construction of the lower bound instance is more delicate than the above.", "questions": "- What are some examples of activation functions under the analytic assumption?\n- For the high-dimensional case, the construction of the lower bound instance (in section 5.3) seems to require much more work; A better explanation of this part would be appreciable.\n- Almost all of the references are shown in an et al. style on page 10 and 11, except a few. Is this done on purpose, e.g., should the names of all authors be properly cited there?", "limitations": "Both the limitations and the potential negative societal impact are discussed in the paper.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\n- This paper deals with an important yet technically challenging question. The proof requires sophisticated machinery from symmetric polynomial theory. However, the authors do a great job of explaining their results and building up their proofs, which is instructive for a reader.\n- The writing of the paper is a pleasure to read, with particular attention paid to the proof details.\n- The width separation between DeepSets and Relational Networks would be a significant contribution to the literature; for example, one could imagine that the machinery developed here might help separate architectures in other settings such as graph neural networks, where this sort of permutation invariance appears quite often.\n\n**Weakness**\n\n- The main result relies on a certain analytic assumption on the activation functions of the neural network (as the authors have discussed in the limitations section).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept