Polynomial Width is Sufficient for Set Representation with High-dimensional Features
Authors: Peihao Wang
Shenghao Yang
Shu Li
Zhangyang Wang
Pan Li
Venue: ICLR 2024 poster (2024)
Keywords: Set Representation; Permutation Invariance; Permutation Equivariance
Primary area: learning on graphs and other geometries & topologies
TL;DR: We prove that polynomial dimension of the embedding space are sufficient for DeepSet like architecture to represent any high-dimensional continuous permutation-invariant functions.

Abstract: Set representation has become ubiquitous in deep learning for modeling the inductive bias of neural networks that are insensitive to the input order. DeepSets is the most widely used neural network architecture for set representation. It involves embedding each set element into a latent space with dimension $L$, followed by a sum pooling to obtain a whole-set embedding, and finally mapping the whole-set embedding to the output. In this work, we investigate the impact of the dimension $L$ on the expressive power of DeepSets. Previous analyses either oversimplified high-dimensional features to be one-dimensional features or were limited to complex analytic activations, thereby diverging from practical use or resulting in $L$ that grows exponentially with the set size $N$ and feature dimension $D$. To investigate the minimal value of $L$ that achieves sufficient expressive power, we present two set-element embedding layers: (a) linear + power activation (LP) and (b) linear + exponential activations (LE). We demonstrate that $L$ being $\operatorname{poly}(N, D)$ is sufficient for set representation using both embedding layers. We also provide a lower bound of $L$ for the LP embedding layer. Furthermore, we extend our results to permutation-equivariant set functions and the complex field.

Published as a conference paper at ICLR 2024
POLYNOMIAL WIDTH IS SUFFICIENT FOR SET REPRE- SENTATION WITH HIGH-DIMENSIONAL FEATURES
Peihao Wang', Shenghao Yang 3 Shu Li + Zhangyang Wang's Pan Li
UUiiversity of Texas at Austin, GGeorgia Tech, 'University of Waterloo, PPurdue University (pe ipeihacwang, at Laswanggg @utexas. edu, panli8gate edu, shenghac. yangeuwaterloo. ca, shuli chulippurdue.edi
ABSTRACT
Set representation has become ubiquitous in deep learning for modeling the induc- tive bias of neural networks that are insensitive the input order. DeepSets is the most widely used neural network architecture for set representation. It involves embedding each set element into latent space with dimension L, followed by a sum pooling to obtain a whole-set embedding, and finally mapping the whole-set embedding to the output. In this work, we investigate the impact of the dimension L on the expressive power of DeepSets. Previous analyses either oversimplified high-dimensional features to be one-dimensional features or were limited to com- plex analytic activations, thereby diverging from practical use or resulting in L that grows exponentially with the set size N and feature dimension D. To investigate the minimal value of L that achieves sufficient expressive power, we present two set-element embedding layers: (a) linear power activation (LP) and (b) linear exponential activations (LE). We demonstrate that L. being poly(N, D) is suffi- cient for set representation using both embedding layers. We also provide a lower bound of L for the LP embedding layer. Furthermore, we extend our results permutation-cqqiiariaan set functions and the complex field.
INTRODUCTION
Enforcing invariance into neural network architectures has become a widely-used principle to design
deep learning models (LeCun et al. 1995 Cohen & Welling 2016 Bronstein et al.] [ Kondor Trivedi 2018; Maron et al.) [0088 Bogatskiy et 2020 Wang et al. 2023).. In particular, when task is learn a function with a set as the input, the architecture enforces permutation invariance that
asks the output to be invariant to the permutation of the input set elements (Qi al. 2017 Zaheer
(ct al. 2017). Neural networks to learn a set function have found a variety of applications in particle physics (Mikuni & Canelli 2021: Qu & Gouskos 2020). computer vision (Zhao et al. [202] Lee
ct al. 2019) and population statistics (Zhang et al. (0220) Grover et al., (020). and have recently become a fundamental module (the aggregation operation of neighbors' features in graph (Morris
et al. 2019 Xu et al. 2019 Corso et al.] 2020)) in graph neural networks (GNNs) (Scarselli et al.
2008
Hamilton al.
2017 that show even broader applications.
Previous works have studied the expressive power of neural network architectures to represent set functions (Qi al. 2017 Zaheer et al. 2017 Maron al. 2019 Wagstaff al., 2019 2022 Segol
& Lipman 2020 Zweig & Bruna (2022). Formally, a set with N elements can be represented as 1 x [N)} where ( in a feature space X', typically X' = RD. To represent a set
function that takes S and outputs real value, the most widely used architecture DeepSets (Zaheer
et al. 2017) follows Eq.
((S) - Σ (c((() where : X R and p: RR R are continuous functions.
DeepSets encodes each set element individually via Φ, and then maps the encoded vectors after sum pooling to the output via p. The continuity of à and p ensure that they be well approximated by fully-connected neural networks (Cybenko, 1989 Hornik et al., 1989), which has practical implications. DeepSets enforces permutation invariance because of the sum pooling, shuffling

---

Published as a conference paper at ICLR 2024
Table A comprehensive comparison among all prior works on expressiveness analysis with L. Our results achieve the tightest bound on L while being able to analyze high-dimensions set features and extend to the equivariance case.
Prior Arts
L N
D
Exact Rep.
Equivariance
DeepSets (Zaheer et al. 2017
X
Wagstaff' et al. (aassaat cl al.
2019
N
X
Segol al. (Segol & Lipman
2020
Zweig & Bruna (Zweig & Bruna
2022
explmin (v N. DY)
X
Our results
(oly(N,
the order of (+() does not change the output. However, the sum pooling compresses the whole set into T-dimension vector, which places information bottleneck in the middle of the architecture. Therefore, a core question on using DeepSets for set function representation is that given the input feature dimension D and the set size N, what the minimal L is needed that the architecture approximate any continuous set functions. The question has attracted
Eq. [ can represent/universiie
attention in many previous works (Zaheer et al. 2017; Wagstaff et al. 2019 2022 Segol & Lipman
2020
Zweig& & Bruna 2022) and is the focus of the present work.
An extensive understanding has been achieved for the case with one-dimensional features (D 1). Zaheer et al. (Zaheer et al. (017)) proved that this architecture with bottleneck dimension L = N suffices to accurately represent any continuous set functions when D = 1. Later, Wagstaff et al. proved that accurate representations cannot be achieved when L < N (Wagstaff et al., (019) and further strengthened the statement to a failure in approximation to arbitrary precision in the infinity norm when L < N (Wagstaff et al. 2022
However, for the case with high-dimensional features (D> > 1), the characterization of the minimal possible L is still missing. Most of previous works (Zaheer et al., 2017 Segol & Lipman 2020 Gui et al. 2021) proposed to generate multi-syymmetric polynomials to approximate permutation invariant functions [Bourbaki] 2007). As the algebraic basis of multi-symmetric polynomials is of
- (N+D) 1 Ryyh 2007 (exponential in min D, N) }), these works by default claim that if L L", ff in Eq. can approximate any continuous set functions, while they do not check the possibility of using smaller L. [Zweig & Bruna (2022) constructed set function that requires bottleneck dimension I. > N e===xx(O(mmnn] D, VN))) (still exponential in min D, vN)) to approximate while it relies on the condition that Φ, only adopt complex analytic activation functions. This condition overly strict, as many practical neural networks work on real numbers [] and even allow the use of non-analytic activations, such as ReLU. Zweig & Bruna thus left an open question whether the exponential dependence on N or D of L is still necessary if &. P work in the real domain and allow using oon-analyti activations.
size L'
Our Contribution. The main contribution of this work is to confirm negative response to the above question. Specifically, we present the first theoretical justification that I, being polynomial in N and sufficient for DeepSets (Eq. D like architecture to represent any real/complex continuous set functions with high-dimensional features (D > 1). To mitigate the gap to the practical use, we consider two architectures to implement & (in Eq. I and specify the bounds on accordingly:
o adopts linear layer with power mapping: The minimal L holds lower bound and upper bound, which is N 1) S L < D²D
é adopts a linear layer plus an exponential activation function: The minimal holds a tighter upper bound L < N 2
We start from the real domain and prove that if the function p could be any continuous function, the above two architectures reproduce the precise construction of any set functions for high-dimensional features D= > 1, akin to the result in Zaheer et al. (2017) for D = 1. This result contrasts with SSeool
& Lipman 2200 Zweig& & Bruna (2022) which only present approximating representations. If
'Note that for 2, y E R. the function in the complex domain fi 1v-1) x not complex analytic, while function with real variables fa([2, v)) = can simply and accurately implemented by practical neural networks. Moreover, complex analytic functions are not dense in the space of complex continuous functions, while polynomials (and thus real analytic functions) are dense in the space of real continuous functions. So, the assumption considered in (Zweig & Bruna 2022) substantially limits the space of the functions that can he approximated.
2

---

Published as a conference paper at ICLR 2024
adopts fully-connected neural network that allows approximation of any real continuous functions on a bounded input space (Cybenko 1989 Hornik et al. 1989). then the DeepSets architecture f()) approximate any set functions universally that bounded input space. We extend our theory to permutation-equivee
functions and set functions the complex field, where the minimal shares multiplicative constants.
the same bounds up to
Another comment on our contributions that Zweig & Bruna (022) leverage difference in the needed dimension L, albeit with the complex analytic assumption, illustrate the gap between DeepSets (Zaheer et al.; 2017) and Relational Network (Santoro et al. powers, where the latter encodes set elements in a pairwise manner rather than in element-wise separate manner. The gap well explains the empirical observation that Relational Network achieves better expressive power with smaller T. (Murphy et al. 2018: Wagstaff et al. 2019). Our theory does not violate such an observation while it shows that without the above strict assumption, the gap can be reduced from an exponential order in N and to polynomial order.
2017) in their expressive
Practical Implications. Many real-world applications have computation constraints where only DeepSets instead of Relational Network can be used, e.g., the neighbor aggregation operation in GNN being applied large networks (Hamilton al. 2017). and hypergraph neural diffusion operations in hypergraph neural networks (Wang et al. 2023). Our theory points out that in this case, it is sufficient use polynomial dimension embed each element, while one needs to adopt decoder network P with non-analytic activations.
PRELIMINARIES
2.1 NOTATIONS AND PROBLEM SETUP
We are interested in the approximation and representation of functions defined over sets We start with the real field and then extend the result. In convention, an N-sized set where (+) RD Vi E [ (1,) can be denoted by data matrix X (x(1)
[M)] E R-NDD Note that we use the superscript (i) to denote the i-th set element and the subscript i to denote the i-th column/feature channel of X, i.c..
(N) Let II(N) denote the set of all N-by-N permutation matrices. To characterize the unorderedness of a set, we define equivalence class over RND:
(1)
x; = 2
Definition 2.1 (Equivalence Class). If matrices X, X'' NND represent the same set X, then they are called equivalent up a row permutation, denoted as X ~ X'. Or equivalently, X ~ X' if and only if there exists a matrix P (IV) such that X PX'
Set functions can be in general considered as functions, which process the input matrices regardless of the order by which rows organized. The formal definitions of pernuration-iivvaian/eqppaaanan
or permutation cemmutatio-eqqiivriaan
functions are presented as below:
Definition 2.2. (Permutation Invariance) A function f I NXD + invariant if f(PX) = f(X) for any P II(N).
D' is called permutation-
Definition 2.3. (Permutation Equivariance) A function f NXD NxD' is called permutation- equivariant f(PX) = (X) for any P E IINN).
In this paper, we investigate the approach to designing a neural network architecture with permutation invariance/equivariance. Below we will first focus on permutation-invariie R. Then, in Sec. 5 show that we can easily extend the established results permutation- cquivariant functions through the results provided in Sannai et al. (2019); [Wang et al. (2023) and to the complex field. The obtained results for D II can also be easily extended to D 1 as
functions f N
otherwise / can be written as [fi
fo.)" and each fi has single output feature channel.
II fact, allow repeating elements in S, therefore, S should be more precisely called multiset. With slight abuse of terminology, we interchangeably terms multiset and set throughout the whole paper.
3

---

Published as a conference paper at ICLR 2024
2.2 DEEPSETS AND THE PROOF FOR THE ONE-DIMENSIONAL CASE (D
The seminal work Zaheer et al. (0177) establishes the following result which induces a neural network architecture for permutation-invariat functions.
Theorem 2.4 (DeepSets (Zaheer et al., 2017), D= 1). A continuous function f : RV - +RR is permutation iitiiionn-ivvrinnttt (i.e. a set function) and only if there exists continuous functions 6 R
and p R+ + I. such that f(X) (Ei= o(x(()) where L can be as small N. Note that,
here 20) E I. is scalar.
Remark 2.5. The original result presented in Zaheer et al. (2077) states the latent dimension should be as large as N + 1. Waagttff et al. (2019) tighten this dimension to exactly N.
Theorem 2.4 implies that as long as the latent space dimension 2 N, any permutation-invarice functions can be implemented in unified manner DeepSets (Eq[). Furthermore, DeepSets suggests a useful architecture for & at the analysis convenience and empirical utility, which is formally defined below (in DeepSets, & is set as ())):
Definition 2.6 (Power mapping). A power mapping of degree K is a function d/K R transforms scalar power series: (2)(2) = [= z²
& which
=k]T.
However, DeepSets (Zaheer et al. 2017) focuses on the case that the feature dimension of each element is one (i.e., D = 1). To demonstrate the difficulty of extending Theorem 2.4 to high- dimensional features, we reproduce the proof next, which simultaneously reveals its significance and limitation. Some intermediate results and mathematical tools will be recalled later in our proof.
We begin by defining sum-of-power mapping (of degree K) V (x) EE thx (z(1),, where thx is the power mapping following Definition [.6] Afterward, we reveal that sum-of-power mapping V k has a continuous inverse. Before stating the formal argument, we formally define the injectivity of permutation cermutation-invariiat mappings:
Definition 2.7 (Injectivity). set function f RNNDD > R² is said to be injective if and only vX, X' NRD S(X) = f(X') implies X ~ X'.
As summarized in the following lemma shown by Zaheer et al. (2017) and improved by Wagstafi NN is an injective mapping. If we further constrain the image
al. (2019), & N (i.e., when
space to be the range of v Z = { (X)): VX RN C RVV then V becomes surjective and shown to have continuous inverse. This result comes from homeomorphism between roots and coefficients of monic polynomials (Curgus & Mascioni 2006).
Lemma 2.8 (Existence of Continuous Inverse of Sum-of- -ower Zaheer et al. 2017 Wagstaff et al. 2019)). y NRN -> Z is injective, thus there exists 1p [/ Moreover, N is continuous.
K such that V N X) X.
Now we are ready to prove necessity in Theorem 2.4 as sufficiency is easy to check. By choosing
u R + N to be the power mapping (cf. Definition 2.6). and p = for For any scalar-
valued set X [x(1))
)(x())) = f o v o v x = f(P)) = (()
for some P II. The existence and continuity of v are due to Lemma 2.8
Theorem 2.4 gives the exact decomposable form (Wagstaff et al.) 2019) for crrmutation-invariin functions, which is stricter than approximation error based expressiveness analysis. In summary, the key idea is to establish a mapping @ whose glement-wise sum sum-pooling has a continuous inverse.
2.3 CURSE OF DIGGNNDIMENSONN FEATURES (D 2 2)
We argue that the proof of Theorem 2.4 is not applicable to nigh-diimesiooal set features (D 2 2). The main reason is that power mapping defined in Definition(2.6jnn) receives scalar input. It remains elusive how to extend it to multivariate version that admits injectivity and continuous inverse. A plausible idea seems to be applying power mapping for each channel 2; independently, and due to the injectivity of sum-of- mapping V v, each channel can be uniquely recovered individually via the inverse V V However, we point out that each recovered feature channel x': ~ Φ,, Vi [D], z'p) X, where the alignment of features across channels gets lost.
does not imply [x'1
4

---

Published as a conference paper at ICLR 2024
D
D
N*
D
W
W
LE
N D
N²
Figure 1: Illustration of the proposed linear + power mapping embedding layer (LP) and linear + exponential activation embedding layer (LE).
Hence, channel-wise power encoding no more composes an injective mapping. Zaheer et al. (2017)
proposed to adopt multivariate polynomials as é for high-dimensional case, which leverages the fact
that multivariate symmetric polynomials are dense in the space of permutation invariant functions (akin to Stone- Wasserstein theorem) (Bourbaki 2007). This idea later got formalized in the work of
Segol & Lipman 2020) by setting (xx()
[E (17 ... where a E ND traverses
all > [ Otj S ni and extended to permutation equivariant functions. Nevertheless, the dimension ( (N+ i.e. exponential min N, D} in this case, and unlike DeepSets (Zaheer et al. 2017
L L=
which exactly recovers for D 1, the architecture in Zaheer et al. (2017) Segol & Lipman (020
can only approximate the desired function.
3 MAIN RESULTS
In this section, we present our main result which extends Theorem 2.4 to nigh-dimensional features. Our conclusion that universally represent set function sets of length N and feature dimension D with the DeepSets architecture (Zaheer et al. 2017) (Eq. [ the minimal needed for expressing the intermediate embedding space is most polynomial in N and D.
Formally, we summarize our main result in the following theorem.
Theorem 3.1 (The main result). Suppose D 2. For any continuous permutation intiutttatiiiiivrantttt function f: R Nx D + I. there exists two continuous mappings & RR" - RR and p Z + R such that for every X E RRDD, f(X)= (E==)(x())
(x())) where 2 = E ((x(0)) vV E
RL is the image of the sum-pooling and
LE (N(D N)? when & admits linear layer power mapping (LP) architecture:
o(x) [w) x)T
(xxx
(2)
for some Wi,"", W. E R., and K L/N.
LE LND,NAD' when & admits linear layer exponential activation (LE) architecture:
b(x)= [exp(v]<))
exp(vT.x))
for some U1 UL E D.
The bounds of depend on the choice of the architecture of é, which are illustrated in Fig. 1 In the LP setting, we adopt a linear layer that maps each element into K dimension. Then we apply a channel-wise power mapping that separately transforms each value in the feature vector into an N-order power series, and concatenates all the activations together, resulting
KN dimension feature. The LP architecture is closer to DeepSets (Zaheer et al. 2017) as they share the power mapping as the main component. Theorem 3.1 guarantees the existence of p and é (in the form of Eq. 2b which satisfy Eq. without the need to set K larger than N D2 while K > D + 1 is necessary. Therefore, the total embedding size = K is bounded by N D)2 above and N + 1) below. Note that this lower bound is not trivial N D is the degree of freedom of the input X. No matter how WT WK are adopted, one cannot achieve an injective mapping by just using N ND dimension.
In the LE architecture, we investigate the utilization of the exponential activation in set representation. which is also a valid activation function to build deep neural networks (Barron 1993 Clevert et al. 2015). Each set entry will be linearly lifted into an L-dimensional space and then transformed by an element- wise exponential activation. The advantage of the exponential function is that the upper bound of L. is improved to be D2 The lower bound N ND for the LEE
group of weights
5

---

Published as a conference paper at ICLR 2024
architecture is trivial bound due to the degree of freedom of the inputs. Essentially, a linear layer followed by an exponential function is equivalent to applying monomials onto exponential activations. If monomial activations are allowed exponential function with a series of monomial mappings while yielding the same upper bound. However, in contrast to /Seool & Lipman 2020), where exponentially many monomials are required, our construction of the linear weights enables a mere reliance on bivariate monomials of degree D, thus reducing the number of needed monomials to O(N2D).
used in Segol & Lipman (2020), we also replace the
Remark 3.2. Unlike the form of p cannot be explicitly specified, it depends on the desired function f. The complexity of p remains unexplored in this paper, which may be high in practice.
Empirical Validation. In Appendix A we numerical experiments verify our argument. Fig. 2 demonstrates the polynomial dependence between the set size, feature dimension, and the minimal latent embedding dimension achieve small approximation error. See more details in Appendix
Importance of Continuity. We argue that the requirements of continuity on p and & are essential for our discussion. First, practical neural networks can only provably approximate continuous func- tions (Cybenko 1989; Hornik et al.) 1989). Moreover, set representation without such requirements can be straighttorward (but likely meaningless in practice).
known that there exists discon- tinuous bijective mapping r : R + R if D 2 2. If we let r map the gige-iimessioal features to scalars, then its inverse exists and the same proof of Theorem 2244 through, i.e. let ø = N o and p f r V However, we note both p and à lose continuity.
Comparison with Prior Results. Below we highlight the significance of Theorem overview has been listed in Table [ for illustration. The lower bound in Theorem 3. corrects natural misconception that the degree of freedom (i.e., L = ND for multi-channel cases) is not enough for representing the embedding space (Wagstaff et al. 2022). Compared with Zweig & Brunals s finding, our result significantly improves this bound on L from exponential to polynomial by allowing continuous activations that may not be complex analytic. Proof-wise, Zweig & BBunnaa proof idea is hard to extend to the real domain, while ours applies to both real and complex domains and equivariant functions. Dym & Gortler (2024); Amir al. (2024) present significant results that I, can be as small as 2N D + However, the continuity of decoder is not guaranteed when the domain of f is an open set.
3.1 A quick
4 PROOF SKETCH
In this section, we introduce the proof techniques of Theorem 3.1 while deferring a full version and all missing proofs to the appendix. The proof is constructive and mainly consists of three steps below:
For the LP architecture, we construct a group of K linear weights wi wi.... Wk E R. with < N D2 while for the LE architecture, with S 2 such that the summation over the associated embeddings $ (X) Σ i=1 ((x(1)) is injective. Moreover, if K < D for LP layer or trivially L < ND for LE layer, such weights do not exist, which induces the lower bounds.
construct group of T. linear weights 01 Uz R D
2. Given the injectivity of both LP and LE layers, we constrain the image spaces to be their ranges (x(X) X E RVDD). respectively, and thus, the inverse of the sum-pooling $ exists.
Furthermore, we show that Φ is continuous.
3. Then the proof of upper bounds can be concluded for both settings by letting p = f o $ since o + 1 ((X) f(PX) (X) for some P E II
0 ΣN ((x()))
Next, we elaborate on the construction idea which yields injectivity for both embedding layers in Sec. 4.1 with the notion of anchor. In Sec. 4.2 prove the continuity of the inverse map for LP and LE via arguments similar to Curgus& & Mascioni 2006).
4.1 INJECTIVITY
The high-level ideas of construction and proofs are illustrated in Fig. 3 in which we first construct an anchor, mathematical device introduced in Sec. 4.1.1 to induce injectivity, and then mix each

---

Published as a conference paper at ICLR 2024
feature channel with the anchor through coupling schemes specified by LP (Sec. 4.1.2 and LE (Sec.
4.1.3) layers, respectively.
4.1.1 ANCHOR
Constructing an anchor stands the core of our proof. Formally, we define anchor as below: Definition 4.1 (Anchor). Consider the data matrix X E INNxD, then a E R is called an anchor of X if a, + aj for any i.j E [N] such that (1)) + x()
In plain language, by Definition 4.1 two entries in the anchor must be distinctive if the set elements the corresponding indices not equal. As result, the union alignment property be derived: Lemma 4.2 (Union Alignment). Consider two data matrices X, X'X's E RNND E RN is an anchor of X and a' IR is an arbitrary vector. If [a Σi} |a' x' ii every E [D], then X X'.
The same anchor a will be concatenated with all channels forming a series of two-column matrices. Once the permutation orbits of each coupled pair intersect, the permutation orbits of two data matrices also intersect. Our strategy to generate an anchor is through a point-wise linear combination:
Lemma 4.3 (Anchor Construction). There exists of R where K1 = N(N D) 1)/2 + 1 such that for every data matrix X E NXD there exists j E [1], X X an anchor of X.
of weights a,,'.. , Kk in general positions
From a geometric perspective, if there are enough weights {az j E [K]] in general positions, at least one of them will not be orthogonal to the difference between any two columns.
4.1.2 INJECTIVITY OF LP
In this section, we specify e following the definition in Eq. 2 Suppose sum-of-power mapping WN(Xun v (ov(X'u ('wx;) for all [K], Lemma 2.8 guarantees ww ~ X'w, for all E [K]. The main technical challenge is to ensure the alignment among all feature columns. This step combines the construction of anchors and the following linear coupling scheme that ensures alignments between all pairwise stackings of feature channels and anchors.
Lemma 4.4 (Linear Coupling). There exists a group of coefficients "1."- "' where K₂ = N(N - 1) + 1 such that the following statement holds: Given any x, x, y,y E RN such that x ~ x' and ~ y if (x 7ky)) ~ (x' - -way') for every k E [K2), then (x y) ~ [x' y').
Construction. Our construction divides the weights {w;, [K]} into three groups: fe; : [D,, fay: ;j E [K]], and {T : E [D],] E [K,],k E [Ka]]. Each block is illustrated in Fig. 3b and outlined below:
1. Let the first group of weights e1, ee E RR buffer the original features, where e, is the i-th canonical basis.
2. Design the second group of linear weights, ".. 0x E RD for K₁ as large as N(N
I)(D - 1)/2 + 1, following the specifications Lemma 4.3 Then, we know at least one of Xay.j E [2,] forms an anchor of X.
3. Design a group of weights T for i E [D]. E [Kj] k E [K2] with K₂ = N(N - 1) +1 that mixes each original channel æ; with each Xa E [Ka by Pij. e, n.a where 7k. Ak E [K2] is the coefficient defined Lemma 4.4
Injectivity.
With such configuration, injectivity be shown by the following steps: First recalling the injectivity of power mapping (cf. Lemma 2.8). we have:
Σ ((x)(()) = Xw; ~ X'W; Vi E [K]. ==1
(4)
1=
It is equivalent to expand the RHS of Eq.
4 as: D; d',, Xa, X'a,, and XT j.j.k
x Xxy) ~ XTTi** (a', 7kk X'
C for every E [D].je [K1] E [Kg] By Lemma
we can further induce:
Xws
X' X'w, Vi E [ + Xay x.) ~ I'
a'J,Vii D [K]]
(5)
7

---

Published as a conference paper at ICLR 2024
According to Lemma 4.3 Lemma 4.2,
there must be jr [Ka] such that Xay- is anchor of X. Then by
Eq.
implies:
d'I]. Vie [D] X X'. XXy 21 ~ [Xaa
(6)
The total required number of weights K D D N D2 and the embedding length = NK I N as desired.
For completeness, only if 2 D + 1, when D 2 2.
add the following lemma which implies LP-induced sum-pooling is injective
Theorem 4.5 (Lower Bound). Consider data matrices X NxD where D 2. Kf D, then for every w1."." WK, there exists X' E NRD such that X +f X' but Xw; ~ X' Vi [K]. Remark 4.6. Theorem 4.5 is significant that with -igediimensional features, the injectivity is provably not satisfied when the embedding space has dimension equal to the degree of freedom.
4.1.3 INJECTIVITY OF LE
In this section, we consider ø follows the definition in Eq. 3 Our first observation is that instead of applying univariate monomials to each linearly mixed channel individually, we can directly employ bivariate monomials to pair channels with anchors and yield the same alignment results as in LP.
Lemma 4.7 (Monomial Coupling). For any pair of vectors æ, y, x', y E ER>, EmEne[ *
EMEIN w'l-k y for every E [N]. 0 < k S I, then [xc y) ~ [x' y'}.
The second observation is that each term in the RHS of Eq. 3 can be rewritten monomial of an exponential function:
Ki+D
exp(x x:) = =xx((u' log(exp(S)) xx))) = II exp(S2x)
where the exponential and the logarithm taken element-wisely, DX((K+ and E RK++D, Recall that K₁ is the needed dimension to construct an anchor as shown Lemma 4.3 Then, the assignment of V,,-.. Ur, amounts to specifying the exponents for D power functions within the product. Specifically, we choose v, Lt follows.
Nu for some Ω
Construction. We first reindex and rewrite {v, : E
[L]} as (Vi.j.pa = Quiji.gg : E [D],j E en On
[K]],P E [N], q E [p + 1]}, where Ω = [ei
ox.] E Dx(+Kii) and
Wiii.g E D+ are specified as below. In Fig. 3c we depict the forward pass of an LE layer.
1. The choice of weights 52 follows from the construction of the LP layer, i.e., e, E RP, Vi E [D] are canonical basis and {ar, Vj E [K]]] with K₁ N N(N 1)(D - 1)/2 are drawn according to Lemma 4.3 so that an anchor is guaranteed to be produced.
2. Design group of weights U = [... [K],pp E [N],9 E [p + 1] such that u.j.p. = (q - l)e, + (p- 9 + 1)eD+j.
Uijing . E RR (D+K, N(N for [D].j
Injectivity. Plugging Z and U into Eq. 7 can examine each output dimension of the embedding
layer:
ΣN ((x)
i.j.p. = EN exp(x;)) exp(Xa;)); 1-1 1 Then by Lemma 4.7
N Σ (()())))
N
Σ (1)) + > (exp(x;) exp(Xax)) ~ (exp(x'<) exp(X'a,)),
(8)
Tmml
Vi E D [K2]. With above implication, the proof can be concluded via the following steps: Lemma 4.3 guarantees the existence of j" [Kg] such that X w. is an anchor of X, and so is
expl Xwy. due to the strict monotonicity exp(:); Lemma 4.2 and Eq. together imply:
(exp(x:;
exp( X o. )] (exp(æ')) exp(X'aa a. )] [D] = exp exp(X'). (9)
And finally, notice that an wise function does not affect equivalence under permutation. The total number of required linear weights is == DK, (N + N/2 < N22 desired.
8

---

Published as a conference paper at ICLR 2024
4.2 CONTINUITY
In this section, we show that the LP and LE induced sum- num-pooling are both homeomorphic. We note that it is intractable obtain the closed form of their inverse maps. Notably, the following remarkable result can get rid of inversing function explicitly by merely examining the topological relationship between the domain and image space.
Lemma 4.8. (Theorem 1.2 Curgus & Mascioni 2006 Let (X, dx) and (Z, dz) be two metric spaces and f X + Z is a bijection such that (a) each bounded and closed subset of X is compact, (b) I is continuous, (c) f maps each bounded set in into a bounded set in X. Then f is continuous.
Subsequently, we show the continuity an informal but more intuitive way while deferring rigorous version to the supplementary materials. Denote क (X) EiE[N] (xx(1)) To begin with, we set
X' / with metric (X, x') = min)e || - PX loo, and Z = {x) e x C R with metric dz(z, z²) = || - 2'1l It easy to show that X' satisfies the conditions (a) and (X) satisfies (b) for both LP and LE embedding layers. Then remains to conclude the proof by verifying the condition (c) for the mapping E - X. i.e. the inverse of ((X). We visualize this mapping following the chain of implication to show injectivity:
(LP)
((X)
Eq.
[... P.X:; ,,,, [K]
Bqs
PX QX
(LE)
((X)
Eq. B
exp [Q Q Qis i ED)
E+ 7
R
for some X dependent P. Q E II(N). Here, P. INN),i E [K] and Q II(N), aj
Xay,i E [D],j E [K]]. All the weights have been specified as in Sec. 4.1 According to homeomorphism between polynomial coefficients and roots (Corollary 3.2 in Curgus & Mascioni (2006)), any bounded set in Z will be mapped into a bounded set in R. Moreover, since elements in R contain all the columns of X (up to some changes of the entry orders), a bounded set in R also corresponds to a bounded set in X. Through this line of arguments, we conclude the proof.
5 EXTENSIONS
Permutation Equivariance. Permutation-equivaret functions (ef. Definition 2.3 are considered more general family of set functions. Our main result does not lose generality to this class of functions. By Lemma 2 of Wang et (2023) Theorem [.I can be directly extended to permutation- equivariant functions with the same lower and upper bounds, stated follows:
Theorem 5.1 (Extension to Equivariance). For any permutation- -equvvvrrnniiiiiiiiinaaa function f NR.
RR,, there exists continuous functions à IR. + RR and p : IRD' x R² - E such that f(X); p (10,)) EiE(N) s(xx()) for every j (N), where I. [N(D + 1), N) when á admits L.P architecture, and L IND, N D2] when & admits LE architecture.
The upper bounds in Theorem 3.1 is also true to complex features up to constant scale. When features are defined over CNDD our primary idea is divide each channel into two real feature vectors, and recall Theorem 3.1 to conclude the arguments on an R x2D input. All of our proof strategies are still applied. This result directly contrasts to Zweig & Brunals ss work whose main arguments were established on complex numbers. We show that even moving to the complex domain, polynomial length of still sufficient for the DeepSets architecture (Zaheer et al. 2017). We state a formal version of the theorem in Appendix
Complex Domain.
6 CONCLUSION
This work investigates how many neurons are needed to model the embedding space for set represen- tation learning with the DeepSets architecture (aheer al., 2017). Our paper provides an affirmative answer that polynomial many neurons in the set size and feature dimension are sufficient. Compared with prior arts, our theory takes -igeediiensional features into consideration while significantly advancing the state-of-the-art results from exponential to polynomial.
The tightness of our bounds is not examined in this paper, and the complexity of p is uninvestigated and left for future exploration.
Linitations.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We would like thank Dr. Yusu Wang and Dr. Puoya Tabaghi for meaningful discussion. We also express our gratitude to Dr. Manolis C. Tsakiris for pointing out useful results in the topics of unlabeled sensing. P. Li supported by NSF awards PHY-2117997, IIS-2239565. Z. Wang is in part supported by US Army Research Office Young Investigator Award 1911NF2010240 and the NSF Al Institute for Foundations of Machine Learning (IFML.).
REFERENCES
Tal Amir, Steven Gortler, Ilai Avni, Ravina Ravina, and Nadav Dym. Neural injective functions for multisets, measures and graphs via finite witness theorem. Advances in Neural Information Processing Systems, 36, 2024.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. In ICLR 2021-Internatioad Conference on Learning Representations, 2021.
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3):930-945, 1993.
Alexander Bogatskiy, Brandon Anderson, Jan Offermann, Marwah Roussi, David Miller, and Risi Kondor. Lorentz group equivariant neural network for particle physics. In International Conference Machine Learning, pp. 992-1002. PMLR, 2020.
Nicolas Bourbaki. Éléments d' d'histoire des mathématiques, volume 4. Springer Science & Business Media, 2007.
Michael M Bronstein. Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-4, 2017.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems, pp. 15868-18 15876, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? volume 33, 2020.
Ziang Chen and Jianfeng Lu. Exact and efficient representation of totally anti-symmetric functions. arXiv preprint Stti::2311.00066 2023.
Djork-Aré Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint 1. 2015.
Nadav Cohen, Sharir, and Amnon Shashua. On the expressive power of deep learning: tensor analysis. In Conference learning theory, pp. 698-728. PMLR, 2016.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International conference on machine learning, pp. 2990-2999, PMLR, 2016
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighhourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260-1322 2020.
Branko Čurgus and Vania Mascioni. Roots and polynomials as homeomorphic spaces. Expositiones Mathematicae, 24(1):81-95, 2006.
George Cybenko. Approximation by superpositions a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Nadav Dym and Steven Gortler. Low-dimensional invariant embeddings for universal geometric learning. Foundations of Computational Mathematics, pp. 1-41, 2024.
10

---

Published as a conference paper at ICLR 2024
Stefan Elfwing, Eiji Uchibe, and Kenji Doya. Sigmoid-weighted linear units for neural network function approximation in reinforcement learning. Neural networks, 107:3-11, 2018.
Mohammad Fereydounian, Hamed Hassani, and Amin Karbasi. What functions can graph neural networks generate? arXiv preprint vrXiv:2222.08832 2022.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), 2017.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In International Conference on Learning Representations, 2020.
Shupeng Gui, Xiangliang Zhang, Pan Zhong, Shuang Qiu, Mingrui Wu, Jieping Ye, Zhengdao Wang. and Ji Liu. Pine: Universal deep embedding for graph nodes via partial permutation invariant set functions. IEEE Transactions on Puttern Analysis and Machine Intelligence, 44(2):770-782, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.
Kurt Hornik, Maxwell Stinchcombe, Halbert White, et al. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-366, 1989.
Daniel Hsu, Kevin Shi, and Xiaorui Sun. Linear regression without correspondence. Advances in Neural Information Processing Systems, 30, 2017.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems. pp. 7090-7099, 2019.
Joe Kileel, Matthew Trager, and Joan Bruna. On the expressive power of deep polynomial neural networks. Advances in neural information processing systems, 32, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks the action of compact groups. In International Conference on Machine Learning, pp. 2747-2755, 2018.
Yann LeCun, Yoshua Bengio, et al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, 3361(10):199,, 1995.
Juho Lee, Yoonho Lee, Jungtack Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set trans- former: A framework for attention based permutation-invantt invariant neural networks. In International conference on machine learning, pp.
PMLR, 2019.
Shiyu Liang and R Srikant. Why deep neural networks for function approximation? International Conference on Learning Representations, 2017.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2020.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph
networks. In International Conference on Learning Representutions (ICLR), 2018
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International conference on machine learning, pp. 4363-4371. PMLR, 2019.
Vinicius Mikuni and Florencia Canelli. Point cloud transformers applied to collider physics. Machine Learning: Science and Technology, 2(3):035027, 2021.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.

---

Published as a conference paper at ICLR 2024
R. L. Murphy, B. Srinivasan, V. Rao, and B. Ribeiro. Janossy pooling: Learning deep permutation- invariant functions for variable-size inputs. International Conference on Learning Representa- tions (ICLR), 2018.
Liangzu Peng and Manolis Tsakiris. Linear regression without correspondences via concave minimization. IEEE Signal Processing Letters, 27:1580-1584, 2020.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learnigg on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 652-660, 2017.
Huilin Qu and Loukas Gouskos. Jet tagging via particle clouds. Physical Review D. 101(5):05009,, 2020.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jaseha Sohl-Dickstein. On the expressive power of deep neural networks. In international conference on machine learning, pp. 2847-2854. PMLR, 2017.
David Rydh. A minimal set of generators for the ring of multisymmetric functions. In Annales de l'institut Fourier, volume 57, pp. 1741-1769, 2007.
Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permutation invariant/equivariant functions by deep neural networks. arXiv preprint 1903:01003.011 003.01939, 2019.
Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. Advances in neural information processing systems, 30, 2017.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
Nimrod Segol and Yaron Lipman. On universal equivariant set networks. In International Conference on Learning Representations (ICLR), 2020.
Puoya Tabaghi and Yusu Wang. Universal representation of permutation-invarinn functions vectors and tensors. arXiv preprint arXiv:2310.1382) 2023.
Manolis Tsakiris and Liangzu Peng. Homomorphic sensing. In International Conference on Machine Learning, pp. 8335-6344 PMLR, 2019.
Manolis C Tsakiris. Low-rank matrix completion theory via plücker coordinates. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
Manolis Tsakiris, Liangzu Peng, Aldo Conca, Laurent Kneip. Yuanming Shi, and Hayoung Choi. An algebraic-geometric approach for linear regression without correspondences. IEEE Transactions on Information Theory, 66(8):5130-514 2020.
Jayakrishnan Unnikrishnan, Sacid Haghighatshoar, and Martin Vetterli. Unlabeled sensing with random linear measurements. IEEE Transactions on Information Theory, 64(5):3237-3253, 2018.
Edward Wagstaff, Fabian Fuchs, Martin Engeleke, Ingmar Posner, and Michael A Osborne. On the limitations of representing functions on sets. In International Conference on Machine Learning, pp. 6487-6494. PMLR, 2019.
Edward Wagstaff, Fabian B Fuchs, Martin Engelcke, Michael A Osborne, and Ingmar Posner. Universal approximation of functions on sets. Journal of Machine Learning Research, 23(151): 1-56, 2022.
Peihao Wang, Shenghao Yang, Yunyu Liu, Zhangyang Wang, and Pan Li. Equivariant hypergraph diffusion neural operators. In International Conference on Learning Representations (ICLR), 2023,
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
12

---

Published as a conference paper at ICLR 2024
Yunzhen Yao, Liangzu Peng, and Manolis Tsakiris. Unlabeled principal component analysis. Ad- vances Neural Information Processing Systems, 14:30452-304644 2021.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Approximation, 55(1):407-474, 2022.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poezos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Yan Zhang, Jonathon Hare, and Adam Trugel-Bennets Deep set prediction networks. Advances in Neural Information Processing Systems, 32, 2019.
Yan Zhang, Jonathon Hare, and Adam Prügel-Bennett. Fspool: Learning set representations with featurewise sort pooling. In International Conference on Learning Representations, 2020.
Hengshuang Zhao, Li Jiang, Jiaya Jia, Philip HS Torr, and Vladlen Koltun. Point transformer. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 16259-16268, 2021.
Ding-Xuan Zhou. Universality of deep convolutional neural networks. Applied and computational harmonic analysis, 48(2):787-794, 2020.
Aaron Zweig and Joan Bruna. Exponential separations in symmetric neural networks. arXiv preprint arXiv:2206.01266, 2022.
A NUMERICAL EXPERIMENTS
To verify our theoretical claim, we conducted proof concett experiments. Similar to Wagstaff al. (2019), we train a DeepSets with and p parameterized by neural networks to fit a function that takes the median over vector-valued set according to the lexicographical order. Specifically, the input features are sampled from uniform distribution, Ø is chosen as one linear layer followed by a SiLU activation function (Elfwing et al.) 2018), and is a two-layer fully-connected network with ReLU activation. During the experiment, we vary the input size, dimension, and hidden dimension of 6, and record the final training error (RMSE) after the network converges. The critical width L is taken at the point where RMSE first reaches below 10% above the minimum value for this set size. We observe log (L*) grows linearly with log(N) (N) and log( D) instead of exponentially, which validates our theoretical claim.
The relationship between L' and N. D is plotted in Fig. 2
65
18
D-
32
3-
128
5.5
5.0-
5.0
4.0
35-
30
3.5
4.0
2.0
2.5
3.0
3.5
longth logo/0
Festure dimoriian lggt0)
Figure 2: The relationship among the critical width L, set size N, and feature dimension D. The phenomenon that log( (.) scales linearly with log(N) and log(D) validates our theory.
13

---

Published as a conference paper at ICLR 2024
B OTHER RELATED WORK
Most works on neural networks to represent set functions have been discussed extensively in Sec.
and 3 Here, highlight a few concurrent works. One breakthrough by Dym & Gortler (2024 Amir
et al. 2024) provides both upper bound 2 + and lower bound N NDD + 1) on the embedding dimension for set representation. In their construction, is chosen as linear transformation followed by an arbitrary elementwise analytic function. Their proof of moment injectivity is through extending the finite-witness theorem to a-subanalytic functions defined over o-subanalytic sets. Despite generalization to broader scope of invariant structures, their approach fails to show the continuity of p when the targeted function is defined over an open set. Tabaghi & Wang (2023) has recently improved the upper bound of I. from 2ND + 1 to 2ND considering the input feature space is compact. Whereas, our main claim (Theorem 3.1 guarantees the exact representation over the entire ambient space. The difficulty of mirroring our proof via Lemma 4.8 perhaps arises from the lack of explicit form of Φ verifying the boundedness of Φ-1 becomes less tractable. Complementary to this line of work symmetric functions, Chen & Lu (2023) demonstrates polynomial reliance on N to exactly represent anti- symmetrie functions.
We also review other related works on the expressive power analysis of neural networks. Early works studied the expressive power of feed-forward neural networks with different activations (Horiik et al.
1989 Cybenko 1989). Recent works focused characterizing the benefits of the expressive power of deep architectures to explain their empirical success (Yarotsky) 2017] Liang & Srikant [017]
Kileel al. 2019; Cohen et al.) 2016 Raghu et al. 2017). Modern neural networks often enforce some invariance properties into their architectures such as CNNs that capture spatial translation invariance. The expressive power of invariant neural networks has been analyzed recently in Yarotsky
(2022): Maron et al. (2019): Zhou (2020).
The architectures studied in the above works allow universal approximation of continuous functions defined on their inputs. However, the family of practically useful architectures that enforce permu- tation invariance often fail in achieving universal approximation. Graph Neural Networks (GNNs) enforce permutation invariance and can be viewed as an extension of set neural networks to encode a set of pair-wise relations instead a set of individual elements (Scarselli et al., 2008 Gilmer et al. 2017] Kipf & Welling 2017 Hamilton et al., 2017). GNNs suffer from limited expressive power (Xu et al. 2019 Morris et al. 2019; Maron et al. 2018)) unless they adopt exponential tensors (Keriven & Peyré 2019p. Hence, previous studies often characterized GNNs' expressive
power based on their capability of distinguishing non-isomorphic graphs. Only a few works have ever discussed the function approximation property of GNNs (Chen et al.) 2019 2020; Azizian & Lelarge| (02T) while these works still miss characterizing such dependence on the depth and width of the architectures (Loukas) 2020). As practical GNNs commonly adopt the architectures that combine feed-forward neural networks with set operations (neighborhood aggregation), we believe the characterization of the needed size for set function approximation studied in Zweig & Bruna 2022) and this work may provide useful tools to study finer grained characterizations of the expressive power of GNNs.
C SOME PRELIMINARY DEFINITIONS AND STATEMENTS
In this section, we begin by stating basic metric spaces, which will be used in the proofs later. Definition C.1 (Standard Metric). Define (XCP, doo) as the standard metric space, where do :
x xD + Rzo is the Exx -oom induced distance metric over KP:
doo dz, z²) max 2 z'cl. iE!D)
(10)
Definition C.2 (Product Metric), Consider metric space (X, dx). We denote the induced product metric over the product space (X .dk) as d% K x x + Rzo:
xx Z Z') = max dx (zi, z'1),
(11)
K
where Z
[1
2K] E K 2 X, Vi [K]
We provide rigorous definitions to specify the topology of the input space of cetpuuttttioninvvviiin functions.
14

---

Published as a conference paper at ICLR 2024
Definition C.3 (Set Metrie), Equipped KNNx with the equivalence relation (cf. Definition 2.1
we define metric space N ~ dn), where du (IC NxD) ~) x (XDDD// ~) - Rz0 is the optimal transport distance:
(') min PEI(())
|PX
X X 100000
(12)
and K can be either R or C.
Remark C.4. The Il norm takes the absolute value of the maximal entry: (NN [x,)) Other topologically equivalent matrix norms also apply.
Lemma C.5. The function du (KCxD/ m) x (KNxD/ ~) Rgo distance metric on KNXD/-.
Proof. Identity, positivity, and symmetry trivially hold for dn. It remains to show the triangle inequality as below: for arbitrary XXX' x" E (ICNxD/ ~e, du),
dm(X,X x") = min
PX - -x -xx1,,,,, S min PET((N)
(IPX Q' lo0,00 + +11 X' X 100,00
PET((N)
min PET((N)
|PX- - 1'X'1lloco + +1QQ'X' - -x 1
= dnn(x, X') + +dn(XXX"), x"),
where Q" E argmin
||QX' X" 100,,00
Also we reveal topological property for (KNxD/ ~e d,) which is essential to show continuity later. Lemma C.6. Each bounded and closed subset of (KNxD) ~e, du) is compact.
Proof Without loss of generality, the proof is done by extending Theorem 2.4 in Curgus & Mascioni
(006 to high-dimensional set elements. Let o: (KNND d + (K.Nx)) x ~ du) maps a matrix
X to set whose elements are the rows of X. We notice that @ continuous mapping due
d [X, X'). Let e (Z) Z). Define T C (KNND doo) such that e ( (Z) n T has only one element for every Z (K-N ~2 dn). One example of picking elements for T is sort every Z E ( ~, dn) in the lexicographical order. Now constraining the domain of o to be T yields a bijective mapping e/T, and its inverse e We notice that go el7 induces an identity mapping over /0xxD//,,111
to its contraction nature: d (),((),(())))) (())) < ||X - X'11
(X E (KNxD, ; doo): : e
Now consider arbitrary closed and bounded subset S C (KCxD/ ~ du). To show S is com- pact, we demonstrate every sequence {X&} in S has a convergent subsequence. First observe that {el=*(Xx)) } is also bounded in (ICNxD, ). This is because Hence, by
[X]loo.n = dnr( (X, 0). (X j. C (Xx) such that (el (X,,), } converges to some X E NXC doo). As aforementioned. since e continuous mapping, feo elT (X)} converges e(x) in (KNND/ ~ dn). Since S is closed, e(x) E S. This is 1im X, = e(x), which concludes the proof.
Theorem, there exists a subsequence
Then we can rephrase the definition of permutation-invarian function as proper function mapping between the two metric spaces: f (KN*D)/ ~. dn) - (KCD', doo)).
We also recall the definition of injectivity for cotpnnutttioiiivviiaat functions:
Definition C.7 (Injectivity). A permutation-invaaiiat function f: (KCND / ~2 ,,dn) + (KD', ,dxo) is injective if for every X, X' KN such that f(X) f(X'), then X ~ X'.
Definition C.8 (Bjjectivity/lnveeriillt.y.) A permutation-invarian function f (K ~₂ du) + (K'", doe) is bijective invertible if there exists function g (IC'', that for every X E NxD, g f(X) ~ X.
NxD ~,, dn) such
well-known and useful result in set theory connects injectivity and bijectivity:
Lemma C.9. A function is bijective if and only if it is simultaneously injective and surjective.
15

---

Published as a conference paper at ICLR 2024
We give an intuitive definition of continuity for permutatioon cermuttaiooninvariiatt invariant functions via the epsilon-delta statement:
Definition C.10 (Continuity). A permuration-invariann function f (K/NDD/ dn) + (K., doo) is continuous if for arbitrary X NN and > 0, there exists 8 such that for every X' E KNNxD dn(X, X < 6 then doe ( <.
Remark C.11. Since du is a distance metric, other equivalent definitions of continuity still applies.
D PROPERTIES OF SUM-OF-POWER MAPPING FOR REAL AND COMPLEX DOMAINS
In this section, extend the sum-of-power mapping to both real and complex domains, and explore their desirable properties that serve as prerequisites for our later proof. The proof techniques are borrowed from Curgus & Mascioni (2006). Below, I. can be either or C.
Definition D.1. Define power mapping: Vy K. + ICN, (2)(2) = [a (complex) sum-of-power mapping v (XC*) /0, ~,, + (KCN, doo), WN(Z) E (z())..
= and
Lemma D.2 (Existence of Continuous Inverse of Complex Sum-of-Power (Curgus & Mascioni 2006)). V N injective, thus the inverse V ,do)) (K.N)) ~,) exists. Moreover, V continuous.
Lemma D.3 (Corollary 3.2 (Curgus & Mascioni 2006)). Consider a function Ç (KN doo) (KN/ / ~e dn) that maps the coefficients of a polynomial to its root multi-set. Then for any bounded subset U C (KCN ). the image ((4) (<(=)= E U) is also bounded.
Remark D.4. The original proof of Lemma D.3 is done for the complex domain. However, it is naturally true for real numbers because we can constrain the domain of Ç to be real coefficients such that the corresponding polynomials can fully split over the real domain, and the image be all the real roots. Then both domain and image turn out to be subset of the complex-valued version.
Lemma D.S. Consider the N -eggre sum-of-pone power mapping: V (K.N) /,,0~~,,ppp ~,,dn) + (ICN ddsc).
where (a)) = -E N (x:4) Denote the range of v N Z C KKN and its inverse mapping IN x doo) + (KN ~, ,n, (existence guaranteed by Lemma D.2y. Then for every bounded set M C ; the image x (L1) (V (z) z E4) is also bounded.
Proof. We first show this result when K. = C, and naturally extend it to K. R. We borrow the proof technique from Zaheer al. (017)) to reveal polynomial mapping between (Zu doc) and coefficient space of complex polynomials (CN, d.oo). For every & E (C*) /~, dn, let 2 M and construct polynomial:
N
Pε(x)
II (o Ei) =x=x N. -aw .... (-1) aN- (-1) aN, 1=1
(13)
where & are the roots of (x(x) and the coefficients can be written as elementary symmetric polyno- mials, i.e.
Σ
SA .. S... Vn [N].
(14)
On the other hand, the elementary symmetric polynomials can be uniquely expressed as a function of by Newton-Gire formula:
21
0
0
07
22
21
1
0
0
an det
Q(2)(), vn [N]
(15)
2n-1
2n-2
2n-3
Zn-4
2n
2n
Zn-2
Zn-3
16

---

Published as a conference paper at ICLR 2024
where the determinant (2)) is also polynomial in 2. Now establish the mapping between (Z doo) and (C*/ ~, dn):
x doo) Q(=),
(C*) ddoo)
Lemma
DJ
/C*/~~0 1,-,, dn).
(16)
Cnefficients
Ronts
Then the proof proceeds by observing that for any bounded subset M C (Zux. doa), the resulting A = Q(2)) also bounded in (CN, dx)). Therefore, by Lemma any bounded coefficient set A will produce a bounded root multi-set in (C /~,d1)
Now we show Lemma D.3 also for real numbers. By Remark D.4 we can constrain the ambient space of A to be real coefficients whose corresponding polynomals can split over real numbers, and then the same proof proceed.
Corollary D.6. Consider channel-wise high-dimensional sum-of-power UN (KN*K) .dn) (2 doo) defined as below:
(x [x)(
[N(KK) x
(17)
where Zvx = (vr( x E KN. CKN is the range of the sum-of-power mapping. Define an associated mapping N (Z dxo) - -(KN/ (1EN/~,,1)) >>d
(Z) =1V>'(21
(zK))
(18)
= z; E BuN, , E [K]. Then the mapping N maps any bounded set in (2 dxo) to a bounded set in (K. ~₂ ,,,
where Z - [2]
Proof. Proved by noting that if do (bo(2, Zz, z < C1 for some 2;, 2' E (Zox. doo), E [K] and
a constant C1 2 0, then du (WN (z:). V/ (z't)) < C2, vi E [K] for some constant C2 2 by
Lemma D.5 Finally, we have:
dif 1 (Z), UN (2))
max dn V (2,). w Cz.
<E[K]
which is also bounded above.
E PROOFS FOR THE PROPERTIES OF ANCHOR
The main ingredient of our construction anchor defined in Definition 4.1 Two key properties of anchors restated in Lemma E.T and E.2 and proved below:
Lemma E.1. Consider the data matrix X E NxD and E R an anchor of X. Then if there exists P E IT(N) such that Pa. then Pæ; = F; for every (D).
Proof. Prove by contradiction. Suppose Px, # x, for some i [D]. then there exist some p. q [N] such that x, (p) + (9) while ap = aq- However, this contradicts the definition of an anchor (cf.
Definition
Lemma E.2 (Union Alignment, Lemma 4.2 l. Consider the data matrix X, X E ERD a E R an anchor of X and a' R an arbitrary vector. If la 2z) ~ (a' x' for every (D). then X ~ X".
Proof. According to definition of equivalence, there exists Q; E (TTNN) for every i E [D] such that la 2x Q,a' Q, Moreover, since (a x,) ~ (a' x'1), it must hold that a', i.e., there exists P II(N) such that Pa = a'. Combined together, we have that Pa a.
Next, we choose Q'; = P Q Q', a' Q' a. Due the property of anchors (Lemma E.1. have Q',x; L., I,, Notice that 2; Q', ,x, TTQ.T Q,x'; Pw',. Therefore. we can conclude the proof as we have found a permutation matrix P that simultancously aligns æ; and x'; Pxd PX'.
for every E [D] i.e., X [x]
TD P2x
n
17

---

Published as a conference paper at ICLR 2024
Next, we need to examine how many weights needed to construct anchor via linear combining all the existing channels. We restate Lemma in Lemma |E.4 with more specifications as well as a simple result from linear algebra (Lemmal E.3) prove it, as below:
Lemma E.3. Consider D linearly independent weight vectors {a1..... aD E P). Then for every P.q E [N] such that (p) + x(9), there exists aj. E [D]. such that x aj + x aj.
Proof. This is the basic fact of full-rank linear systems. Prove by contradiction. Suppose for Vj E [D] we have (()) aj = x (o)) aj. Then we form linear system: x(P) [er]
apl =
( [0]
ap). Since a1 aD are linearly independent, it yields x(P) = xl)) which reaches the contradiction.
Lemma E.4 (Anchor Construction). Consider a set of weight vectors {ai, aK, E RD) with K1_ (N 1)(D 1)/2 + L, of which every D-length subset, i.e., {az : Vj J]. VJ S
[Ki] J D, is linearly independent, then for every data matrix X E RNXD, there exists
j E [1). Xay- is an anchor of X.
Proof. Define a set of pairs which an anchor needs to distinguish: I = {(p q) : (()) + x S [NP Consider D-length subset J S [K] with [J] D. Since {ax; : Vj J] are linear independent, we assert by Lemma E.3 that for every pair (p. q) E I, there exists j E J, x(p) aj- x)()) aj.
It is equivalent to claim: for every pair (p,4) E I, at most D - many azj E [1]] satisfy
(P)T ag = (1)T Oy. Based on pigeon-hole principle, as long as K1 2 N(N 1 1)(D 1)/2 +1=
(D - ()) +12 (D 1) + 1, there must exist j [K1] such that (p)) ag. + x aj- for V(p.g) 2) T. By Definition 4.1 Xa, generates an anchor.
Proposition E.5. The linear independence condition in Lemma E.4 can be satisfied with probability one by drawing i.i.d. Gaussian random vectors 01.. KKK
b.d. N).
Proof. We first note that generating a x Ki Gaussian random matrix (D S K1) is equivalent to drawing matrix with respect to probability measure defined over M {X RD*K
rank(X) & D). Since rank-D D matrices are dense in M (Tsakiris) 2023 Yao et al. 2021), we can conclude that for VJ [K1], J D. TP( [aj j } are linearly independent) 1. By union bound, P(faa j E J} for all I E |J] = D are linearly independent) = 1.
F PROOFS FOR THE LP EMBEDDING LAYER
In this section, we complete the proof's for the LP embedding layer (Eq, 2). First constructively show an upper bound that sufficiently achieves injectivity following our discussion in See. [.1.2] and then prove Theorem 4.3 to reveal lower bound that is necessary for injectivity. Finally, show prove the continuity of the inverse of our constructed LP embedding layer with the techniques introduced in Sec. 4.2
F.1 UPPER BOUND FOR INJECTIVITY
To prove the upper bound, we construct LP embedding layer with L. S No D2 output neurons such that its induced summation is injective.
We also restate Lemma 4.4 to demonstrate the weight construction for linear coupling:
Lemma E1 (Linear Coupling, Lemma Consider group of coefficients == {n..... ........ 'K,, R) with 7/s # 0, Vi E [2). "/ + Vi, E K2), and K₂ = N(N 1) + 1 such that all 4-tuples (Te, Tis Th: 71)
I, if 76 + Tá. N * The then 7a/1 7/ + 7k/ /n. It must hold that: Given any x., x y. y E NRN such that a xt and y y', if (xc 7ky) "ww') for every k E [K2). then x y) ~ [x' y")
Remark F.2. A handy choice of I in Lemma F. are prime numbers, which are provably positive, infinitely many, and not divisible by each other.
18

---

Published as a conference paper at ICLR 2024
Lecanna
0
X
X²
Iipa Chanch
620022
Andar
12222
Lerrn
Lecana
(v)
X-xx
(X3 (x))
(a)
D- DEE
MPP D2G.))
07 +p00
M
Figure 3: (a) illustrates the overall idea to construct LP and LE embedding layers and prove their injectivity. In the forward pass, LP and LE will 1) construct an anchor with redundant non- anchor channels through a linear layer A = [on] feature channel with the both anchor and non-anchor channels with the their own coupling schemes, respectively. To prove injectivity, the implication follows the converse agenda of construction: 1) by the properties of coupling schemes specified by LP (Lemma 4.4) and LE (Lemma(4) layers, we obtain pairwise equivalence with anchors, 2) and by union alignment lemma (Lemma 4.2), recover the global equivalence. (b)(c) depict the detailed construction inside the LP and LE embedding layers, respectively. LP embedding layer utilizes linear combination plus power mapping to couple feature channels with the anchor(s) and non-anchors, while LE adopts linear combination plus an exponential mapping, which essentially an exponential function followed by a bivariate monomial. The constructed components marked in gray represent the redundant pairs between feature channels and non-anchor channels, which will not be used in the chain of implication to prove the injectivity.
Oxx, (Lemma 4.3), 2) and couple each
Proof. We note that x' and y ~ y imply that there exist Pz, P. E II(N) such that P.æ. x' and pyy = y' Also (xx 7ky) ~ (a' - -Y13') Ak E [K2] implies there exists Qs E (IN,,, Ak E [K2] such that Q=(x 7ky) x 7k.3' Substituting the former to the latter, we can obtain:
Q P.) x > (I Pt) y, Wk [K2].
(19)
where for each E [Kg]. Eq. 19 corresponds N equalities as follows. Here, we let (Z); denote the ith column of the matrix Z.
(I (1-Q QT no QT)
(20)
(I - P
We compare entries in [... Tpp ".] J and for each entry index p E [N], define set of non-zero
pairwise differences between Fp and other entries in x:: D(p) = (r, Tyg E [N], xp * s.y).
Similarly, for y. we define DGP)) {yp Bo : E [N]. Bp * 3y)- We note that for every n E [N].
either option (a) (I Q, P.),, x 0 or option (b) (I Q P.), ( for some p E [N] as (Q] P,),, is one of the entries of æ.
Then, is sufficient to show there must exist ls E [K2] such that all of equations in Eq. are are induced by the option (a) rather than the option (b), i.e.,
33"
[K2), Vp, [N] such that (I QT. P.). x D(P)
(21)
19

---

Published as a conference paper at ICLR 2024
This is because Eq. 21 implies:
(I - Qk- P2) x = 0
= a Qu- P.. Q a'
(Since Yk + vk E [K2))
(I Q: P.) I ylygy= y=
=
y Q puy Q² y'
which is (2c
y] Q k- la' y'].
To show Eq. 21 we construct N bipartite graphs g(v) = (D D." E(P) for E [N] where each E D or each 8 E D is viewed as a node and (a, 3) E {(r) gives an edge if = Yx for some & E [K2]. Then we prove the existence of k' via seeing a contradiction that does counting the
number connected pairs (av, (3) from two perspectives.
Perspective of D(P). We argue that for Vp E [N] and arbitrary 01,02 E D(P), * a2 there exists at most one D(O") such that (an, 8) E (() and (az, B) E g(e), Otherwise, suppose there exists 5r E y 3' * f such that ('). E g(r) and (a2, 8¹) E g(p), Then we have 0 = n.8, 02 7g 01 = 7x,", and 022 = nD' for some Th. Tii Ye. 71 E r, which is 7/77% = 72/ ///n. As 0i 7 02, it is obvious that %/ + 7/j. Similarly, we have 7i + 7kk Altogether, it contradicts our assumption on r. Therefore, |g(n)| S 2 max{ (D("' s 2(N - 1). And the total edge number of all bipartite graphs should be less than 2N 1).
(P))
Perspective of T. We note that if for some & E [K2] that makes (I -I- Pa) x E DD2 for some E i.e. (I V7-Q. Q P>), = 7x Q Pa) y F O, this 7 contributes at least two edges in the entire bipartite graph, i.e., there being another n' E [M). (I Q PT) = 7h Q Pa W y
Otherwise, there exists unique n' E [M] such that (I Q P. PTT E D (+ 0) and for all n j n². This cannot be true because 10 (1 Q₂ Pa) x By which,
(I- - Q Pa) 4 E [K2]. 3p, E [N] such that (I Q Pa) E D (i.c., Eq, 2 is always false), then the total number of edges is at least 2K₂ = 2N - 1) +)+
Hereby, we conclude the proof by the contradiction, in which the minimal count of edges 2K₂ by Perspective of r already surpasses the maximal number 2N 11) by Perspective of D(P) Li
We wrap off this section by formally stating and proving the injectivity statement of the LP layer. Theorem F.3. Suppose o RD D + Rd admits the form of Eq.
o [u][un]] xT)
(22)
where uN is the power mapping of degree N, L KN < D?, K D K₁ DK, K2 and
W = (ei
eD
01 aK Di.j. .... is constructed as follows:
1. Let the first group of weights e1. eD E RD buffer the original features, where e, represents the i-th canonical basis.
2. Choose the second group of linear weights, aI..... OKK R for Kı as large as N(N-1)(D - 11)(D 1)/2 + 1, such that the conditions in Lemma E.4 are satisfied.
3. Design the third group of weights I, for i [D], E [K1], & E [K2] where Dijk e; Ox
K₂ = N(N - 1) + 1, and 7kk, le E [22] are chosen such that conditions in Lemma F. are satisfied.
Then 1 (1) is injective (ef. Desinition
C.7
Proof. Suppose EN ((x(()) = MN property of sum-of-power mapping (ef. Lemma D.2
o(x (m) for some X, X' E NxD, Due to the injectivity
n=
Σ o (a()))
Xe; X'e, Vi [D] Xa; ~ X'a,, Vi [K]]
(23)
XTijA
X'T ii Vi E [D), [Ki] e [Kg]-
20

---

Published as a conference paper at ICLR 2024
By Lemma E.4 it is guaranteed that there exists [K]] such that Xay- is an anchor, and
according to Eq. 23 we have Xaj. ~ X'y. By Lemma F.I we induce:
Xe; ~ X e Vi D Xay ~ X'a XTa ~ X'T v. [D] E [i]] & E [K2]
aa ax ~ aa r'd, Vi [D].
(24)
Since Xay- is an anchor, by union alignment (Lemma we have:
Xay z ~ (X' z'1, Vi [D] X~x'.
(25)
Here K D K1 DKiK2 & D2 thus KN < No which concludes the proof.
n
F.2 CONTINUITY
Next, we show that under the construction of Theorem F.3 the inverse of Σi= ((x(1) is continuous. The main idea is to check the three conditions provided Lemma 4.8
Theorem E4. Suppose & admits the form of Eg.
22 and follows the construction in Theorem F33
then the inverse of L.P-ind -Pinduucd sum-pooling Σn ==1
N
(n))
) is continuous.
Proof. The proof done by invoking Lemma 4.8 First of all, the inverse of +(X) = =EE (xx(1))
denoted as $-1 exists due to Theorem F.3 By Lemma C.6, any closed and bounded subset of (R NRDD ~2, ~,,d1) is compact. Trivially, @ (X) is continuous. Then it remains to show the
condition (c) in Lemma 4.8 Same with Corollary D.6 while focusing on the real domain, let Eg
V wxr) x
C RR be the range of sum-of-power mapping, and define Z..
{ X E I NNDD 2
be the range of 4, which is also a subset of z We decompose
into two mappings following the similar idea of proving its existence:
(Zz. doo)
VN
R C ~ dn) 4 (R ~ v,dn)
where NN is defined in Eq. (Corollary D.6), is the image of Z under PN and exists due to union alignment (i.e., Eqs. 24 and 25 in Theorem F.3). Also according to our construction in Theorem F3 for any Z R, consider its first D columns produced by {e, e, Vi E D}. we know that 2; ~ π Z); for every i E [D]. Therefore, VZ, Z' E R such that di (Z, Z') S C' for some constant C' > 0 in terms of the product metric di (cf. Definition C.2 the inequality holds:
dn [T( Z), π (Z') I max du(z,, x S di ZZ Z') SC.
(26)
rE[D]
which implies maps every bounded set in R to bounded set in (IR NxD/ ~ dn). Now conclude the proof by the following chain of argument:
Corollary
D.6
S C (Zz, doo) is bounded
(S) is bounded
(8) is bounded.
F.3 LOWER BOUND FOR INJECTIVITY
In this section, we prove Theorem 4.5 which shows that K 2 D+1 1 is necessary for injectivity of I.P-induced sum-pooling when 2 Our argument mainly generalizes Lemma Ts'kiis &
[Png 2019) to our equivalence class. To proceed our argument, we define the linear subspace y by
vectorizing [Xw] X [wæ] as below:
X Wi
[w] & IN)]
v:=
X XERNXD
R
(27)
X Kwk
(w) @ IN)
where R(2 R(Z) denotes the column space of Z and & is the Kronecker product. > is linear subspace of N R with dimension at most R R characterized by wh. WK E RD. For the sake of notation simplicity,
denote I[(N)* fdiag( (diag(Q1.-. ..., Qx) VQI, .QK E I[(N), and Ix & (I(N)= 1x & Q AQ E I[(N)). Next, we define the notion of unique recoverability (Takkiris & Peng 2019 below:
21

---

Published as a conference paper at ICLR 2024
Definition F,5 (Unique Recoverability). The subspace V is called uniquely recoverable under Q E ( & whenever x; x' E V satisfy Qu = x', there exists P E Ix &&& [[N),, Px x'.
Subsequently, we derive a necessary condition for the unique recoverability:
Lemma F.6. A linear subspuce V C IRNK is uniquely recoverable under Q II(N)SK only if there exists P E IK @ II(N). Q(V) nv S &QPT,A=I, where EqPT,, denotes the eigenspace corresponding to the eigenvalue X.
Proof. is sufficient to prove that Q(V) S UU &QpT, ,-=1- This is because the LHS is subspace and the RHS is a union of subspaces. When a subspace is subset of union of subspaces, such a subspace must subset of one of the subspaces, i.e., Q(V)VV S UPEI ( &I(K) EQPT A=1
implies there exists P E I @ II(K) such that Q(V) &QPT A=1-
Next, prove Q(V) no S. UPELKSIIK) EQPT >== by contradiction. Suppose there exists Q(V) OO but æ & UPELRGU(K) εQPT A=1-- -=I- Or equivalently, there exists x' V and Qx', while for VP E Ix @ II(N), # QP This implies Q x' * Pæ for VP E Ix @ IINN). However, this contradicts the fact that C RNK is uniquely recoverable (cf. Definition F.5
We also introduce a useful Lemma F.7 that gets rid of the discussion on Q in the inclusion: Lemma F.7. Suppose V S N is a linear subspace, and is a linear mapping. T(Y)nVnErx = if and only & = 0.
Proof. The sufficiency is straightforward. The necessity is shown by contradiction: Suppose V n E * O, then there exists E V' Er.A such that * Then Tx Ax implies x T (V).. Hence, E T(V) n V n Er, which reaches the contradiction.
Now we are ready to present the proof of Theorem 4.5 restated below:
Theorem E8 (Lower Bound, Theorem 4.5p. Consider data matrices X E NxD where D 2
If K < D, then for every W1,""* WK, there exists X' E RNDD such that X of X' but X ~ X' X'w; for every E [K].
Proof. Proved by contrapositive. First notice that, VX. X' NXD _w;; X' E [K] X X' holds if and only if dim = ND and V is uniquely recoverable under all possible Q ((NSS By Lemma F.6 for every Q I[ there exists P I @ IT(N) such that
Q C EQPT A=1- This IS Q(V) ni E = 0 for all X * 1. By Lemma F.7 we have V VQT A 0 for all À & Then proof is concluded by discussing the dimension of ambient space NNK such that an -ddimennsonn subspace can reside. To ensure n E == for all X + 1, it is necessary that dim V < minxş4 codim TQ for every Q E [I(N) and its associated P IK @ IINN). Relaxing the dependence between Q and P. we derive the inequality:
ND = dim V < min QEN((N)SK PEIR@N(NN) X=1
max min codim EQPT S NK -
(28)
where the last inequality considers the scenario where every non-one eigenspace is mieddmmenioonl, which is achievable when K 2 2. Hence, we can bound K > (ND 1)/N, i.e., K> D+1.
G PROOFS FOR LE EMBEDDING LAYER
In this section, we present the complete proof for the LE embedding layer following Sec. 4.1.3
G.1 UPPER BOUND FOR INJECTIVITY
To prove the upper bound, we construct an LE embedding layer with < 4 output neurons such that its induced sum-poolie pooling is injective. The main construction idea is to couple every channel and anchor with the real and imaginary components of complex numbers and invoke the injectiviy of aum-of-power mapping the complex domain to show the invertibility.
22

---

Published as a conference paper at ICLR 2024
With Lemma D.2, can prove Lemma 4.7 restated and proved as below:
Lemma G.1. For any pair of vectors æ. y E FN x' y R.,, if EiE(Ny x "i th EiE[N] at, "
for every I, [M] such that 0 S I, then x y) ~ lx' yd)
Proof. If for any pair of vectors 2, E R , ,',y' y' E RN such that EiE(N] x
EIEIN] a²t yi for every k [N], k S 1, then for V/ E [N].
Σ
Nn (xt + -IV Σ a y -1V
(29)
N
N
1)* x y,
I(V-1)*
Σ
o
y
(30)
1=1 k=0
k=0
N
Σ
x
) ol
(31)
k=
k=
N
Σ
(1' a
Σ
n vv-,
(32)
in which we reorganize terms in the summation and apply the given condition to establish equality between Eq. 30 31] uy denotes the complex power mapping of degree N (cf. Definition D.1
Consider Eq. 32 for every [N]. we can yield:
v (a yV VN (w' + y -I)
where x is the sum-of-power mapping (ef. Definition D.I Then by Lemma D.2 (xr + yV-111 (a' + -1), which equivalent to the statement [xr y) xx'
we have
y'
Lemma G.2. Suppose f: IR + R is an injective function. We denote f(X) as applying f element- wisely to entries in X, i.e., f(X) i., f( [N].j E [D]. Then for any X, X' ERND f(x) ~ f(X') implies X ~ X'.
Proof. Since f(X) f(X),, there exists P E II(N) such that f(X) Pf(X'. Notice that
element-wise functions are permutation-cquivariann then f(X) f(PX). Since f is injective, we conclude the proof by applying its inverse f-1 both sides.
Lemma G.3. Suppose f IR + R is an injective function. We denote f(X) as applying f element-
wisely entries in X, i.e., f(X) f(Xi,), Vi E [N], (D). For any X E NDD if a is an anchor of X (cf. Definition 4.1 then f(a) is also an anchor of f(X).
Proof. Proved by contradiction. Suppose f(a) is not anchor of f(X). Then there exists i,j j [N], f() # f(x(1)) while f(a;) f(a,). Since is injective, then f()(f) # f(x(1)) implies + (1)) x whereas fa. = f(a;) induces a; = aj. This leads a contradiction.
Now we are ready to prove the injectiviy of the LE layer. Theorem G.4. Suppose o D - R2_ admits the form of Eq. 3
(<x) [exp(1] x)
exp(x]=))]
(33)
where L = (N,N(N + 3)/2 < N D2, V == I...
Viina ".] E R DXL
pxxiie ie [D],j
[K1],
[N]. E 1I, are constructed as follows:
Define a group of weights e eD E RRD 88, where e, the i-th canonical basis.
2. Choose another group of linear weights, ay.... aK, E R for K₁ as large as N(N 1)(D
1)/2 + 1, such that the conditions in Lemma E.4 satisfied.
23

---

Published as a conference paper at ICLR 2024
3. Design the weight matrix V..... E R for [D],j [Ki),p [M], [p 1] such that V...... = (q - 1)e; + (p 1 q 1)a..
Then E (xx(()) is injective (cf. Definition C.7
Proof. First of all, count the number of weight vectors (Vi.i.na) where i E [D],] e [Ki],p [ E p 1}: L DK1 Ep- (p DKi(N + 3)N/22 - D2 desired.
Let Q = [ei
ak, E (Dx(D+K),, and Uijip (q - 1)e; + (p
1)estD E DDKKi then we can rewrite Vij.p. Suiipp for every i E [D],] E [Kil.p
[N]. E p + 1]. Then, for x E RD, we can cast Eq. 33 into:
d(x) I.... exp(u ST xx)
[... exp(u log(exp(S1) x))) ..]] (34)
where log(-) and exp(-) operate on vectors element-wisely. By the arithmetic rule of exponential and logarithm, can rewrite for vi [D].j E [Ki],P E [N], Ip +1
D+Ki
o( = exp(u log log(exp(S2'))) x))) = II
exp (S) T x),, (uniiaa
(35)
k=
exp(e. (ro(e:"))=-1 x))==) exp(a) x)
exp(x;))== exp(ar) w0000t
(36)
Then for X, X'X E NDD, we have:
Σ d (a((1) [N[N]
Σ e (a))(e)
(37)
nE(N)
(38)
exp(x;)% exp (Xa,) 1-- exp(xx1) exp (X'a,)" 1p-9t1 NE[N]
Σ
(39)
nE[N]
Vi E [D].j [Kil.pE [N
By Lemma G.1 we obtain that
exp(x;)] ~ (xx)(X'aa) exp(x' :)] for Vi E [D.je j
[Ki]. By Lemma E.4 there exists j E [Ki] such that az. is anchor of X. By Lemma G.3 exp(X Xax,) is also an anchor of exp( X) By union alignment (Lemma E.2) we have:
[exp (Xa,)) exp(x;)] ~ [exp X X'a exp(x' () Vi [D] + eXp(X) exp(X'). (40)
Finally, we conclude the proof by Lemma G.2
exp(X) ~ (xp(X' = X ~ X'.
(41)
G.2 CONTINUITY
The proof idea of continuity for LE layer shares the similar spirit with the LP layer, but involves additional steps. This is because we cannot directly achieve the end-to-end boundedness for condition (c) in L.mma decomposing the inverse map of the sum-pooling, following the proof idea of injectivity (cf. Theorem G.4). since the last step (Eq, 41) requires taking logarithm over exp( (xp while logarithm does preserve boundedness.
Theorem G.S. Suppose é admits the form of Eq. 33 and follows the construction in Theorem G.4
then the inverse of L.-induced sum-pooling ΣN ((x(()) is continuous.
Proof. Our proof requires the following mathematical tool to help rewrite 6. First, following the construction in Theorem G.4 and by Eq. 34 we can rewrite o(x) as:
((x)= [...
exp(uT ama log(exp(S2 x))) ...]
(42)
24

---

Published as a conference paper at ICLR 2024
where f2 =2=0 [In
A]. and A |ai
axyl Define σ: R2o R as below:
x(x) = [.... exp u u.s.a log (lesp(A log(z)))
(43)
Notice that ((x) T exp(x). Recall (X)) Ei=1 (()(1) and define .b 12 R as ((X) = Ei= (xx(1) ). and then ( - ((exp( X)). The proof can be concluded by two steps:
((exp(())
1) notice that + has continuous inverse - by Lemma G.6 and G.7 and then 2) show that the
continuous inverse of & exists by letting 4 (X) log ob (X).
Lemma G.6. Consider & RbO + R. as defined in Eq. 43
Theorem
G.5 then ((X)
EM ((x()) is injective.
Proof. We use the fact that ((x)) = 1 log(ar), and borrow the same proof from Theorem G.4
Σ
T (x)
Σ δ (x)(
(44)
MEIN]
nE(NI
$
(a:))=- exp 1p-
(x(4)% exp (log( (Xa)())))
(45)
nE[N]
nE[N]
Vi E [D] (N
By Lemma
we obtain that [exp(Iog( ( x; (exp(log(X'aaa) o'd for E [D]. e
[K1]. By Lemma E.4 there exists j [K1] such that log(X)a, is an anchor of log ()) By
Lemma G.3
exp log X)xx)) is also an anchor X. By union alignment (Lemma E.2
[exp (log X a),))
ax] ~ lexp (log( (X')(a))))) 2'i].ViE
[] D
(46)
Lemma G.7. Consider T R2o - RL. and = "( as defined in Eq. Theorem
(zx(0) Let Zg (x(X) X NXD C R². Note that Z Zo (x(X) X E RNDD).
43
G.S
Then R NxD + Zg has inverse क which is continuous.
Proof. Since we constrain the image of to be the range, & becomes surjective. Then invertibility is simply induced by injectivity (Lemma
Now remains show T 1 is continuous, which done by verifying three conditions in Lemma 4.8 By Lemma C.6) any closed and bounded subset of NR ~ dn) is compact. Obviously, ((X) is continuous. And for condition (c) in Lemma 4.8 we will decompose $ into series bounded mappings following the clue of proving its existence, similar Theorem F.4. Recall each element in (XX) has the form Ene[N (x,) exp (log(X)) X)xx) (Px,))"-1 P- for some E [D].j E [K1] E [N].9 E + 1] (cf. Eq. 45 in Lemma G.6). Hence, by Eq. 30 shown in Lemma G.1 & can be transformed into sum-of-power mapping (cf.. Definition D.I via (complex-valued) linear mapping: Vp (xx
@(X,, where Yu CNXL for every Y., +
i E [D], E [K]]- Let K DK, and concatenate T, Y = I.... Yi ...) E CNXXL Recall
Zex (
) ç C denotes the range of the sum-of- -oower mapping.
Then we leverage the following decomposition to demonstrate the end-to-end boundedness:
doo) r, (Zk doc)
W
R /CN/~,,1)) d, 3 (R ,,dn)
where VN is defined in Eq. 18 (Corollary D.6 O, R are ranges of Y and VN respectively, and n exists due union alignment (cf. Eq. 46 and Lemma E.2. Therefore, for any Z R, there exists X (R-XD)) ~e, dr) such that m Z
X. We denote Z [... Zidj ..., Vi [D), E [K1].
25

---

Published as a conference paper at ICLR 2024
In the meanwhile, according to our construction of VN 1 between Z and ı ( X:
Y, T. we demonstrate the relationship
r in ~ VN [T., {() ~ (a, exp(1og( (oolog((()00) (x)
VN 2
(47)
E [D], E [Ki].
With this relationship, now consider VZ, Z' E R such that dif ZZ Z') - C' for some constant
C' > 0 and the product metric di (ef. Definition
C.2
we have inequality:
(
dn (=))))))))))))))) (Z') (z))
max dn(zz-g x jE[K]]
i Z, Z')
S C, (48)
where: i* E [D] is the column which -orm norm takes value at (cf. Definition
C.3 Eq.
48 implies '
maps every bounded set in R to bounded set in (BRNxD/ ~ dn). Now we conclude the proof by the following chain of argument:
Y ((S) is bounded Corollary D.6
S S (Zg. doo) ) is bounded
N (S) is bounded
Y(S) is bounded,
where (*) holds due to that is finite-dimensional linear mapping.
H EXTENSION TO PERMUTATION EQUIVARIANCE
In this section, we prove Theorem 5. the extension of Theorem 3.1 equivariant functions, following the similar arguments with Wang el al. (2023):
Lemma H.1 (Wagg al. 22023); Sannai equivariant function if and only if there is a fumetion T :::M IR NXD - RR that is permutation invariant to
2019 f : RND - R a permutation-
the last N -1 entries, such that f(Z); = T() (++1)
(N) x (1-1)) for any i E [N].
Proof. (Sufficiency) Define [N] + [N] be index mapping associated with the permutation matrix P E IT(N) such that PZ = [=)), (((N))]] Then we have:
f ( .... (0,,,,((((,,)))))) (T()))) = (2 (m(1)) (m(++1)) (=((N) (m((-1)))
Since T(-) is invariant to the last N - entries, it can shown that:
f(PZ); = (m() (m(++1)) , (x(())
(nli-11)) ((Z)x(()
(Necessity) Given a permutation-eqquiariiai function f NXD R N we first expand to the following form: S(Z); = Tq (2(1),.... ...),............... ((,).)))
means (a(e) (.....,())) (()) (1) .... ,..,,,(()) (V)) for any permutation mapping æ. Suppose given
commutation-quuvarrinn
an index i [N]. consider any permutation x [N] + [N] such that (1) = i. Then, we have:
x()) Ta(i) (,....... (0) x = T (=1))
z ((N)))
which implies 7; : N + must be invariant the N 1 elements other than the i-th element. Now, consider permutation π where (11) = Then we have:
To ( (1) (2) x(x) (1)) (1)
x()) ri (2(x(11), 2 (1(2))
=(((N))
2 ((+1))
z (N)
=((-1))
where the last equality is due the invariance to N- elements, stated beforehand. This implies 2 ... (N)) Vi [N] should be written in terms
two results. First, for all i, (1)), 2(2)
of 7i (2(1), ((+1), (1+1)) .... (N), .... (i-1)) Moreover, T₁ is permutation invariant to its last N - 1 entries. Therefore, we just need to set = Ti and broadcast accordingly to all entries. We conclude the proof.
26

---

Published as a conference paper at ICLR 2024
Lemma H.2. Consider continuous pewaaaatnnnnnnnnnniiiiniannnnnn f NR du - (IR ddc) and an associated (R. dro) x (R(N-1)xD, dn) -+ IR specified in Lemma H.1 i.e., f(Z);
T(2(1) (0+1) , (N), ) for any Z E (R dn)) and E [N.. Then is continuous.
Proof. Define d, (2, 22, = max do (2) 2 du (NIT, , ( []] as the
corresponding product metric of (R2 d (R(N-13 - dn). Fix arbitrary E RND and e
Since f is continuous, by Definiton C.10 there exists 5 0 such that for every Z' E RNDD
satisfying du( Z Z') < 6, we have deo (f (Z), f(Z)) < c. Then for the same 6, consider every
Z' E R but under the d metric, such that d, (Z, Z')
8. We note that:
[
=
min QET(N)
IQZ - IQZ-2'lle.. S min
Q
Z z'
= -2( < 6.
QEI((N-1)
00,00
Therefore, using the fact d
S ((2)) < 6, we conclude the proof.
The following result, restated from Theorem 5.1 can be derived from Theorem 3.1 equipped with Lemma H. and
Theorem H.3 (Extension to Equivariance, Theorem 5.1). For any permutation-equiivaat fuitiiaiiiiiiiiinnnaaiiinnnn f: R. D + RR,, there exists continuous functions Φ RD R- and p RD R- + R such
that f(X);= p (zl1), EiE[N] ((x!1)) for every j E [N], where E (N(D + 1), No D2) when ø admits LP architecture, and L E [ND, D2] when & admits LE architecture.
Proof. Sufficiency can be shown by verifying the equivariance. We conclude the proof by showing the necessity with Lemma H.l First we rewrite any permutation equivariant function / (x) ax()) N + F as:
f
c ( (z0(1) (1-1)
(0,
(2(111)
(49)
where RNDD + R is invariant the last N - elements, according to Lemma H.1 By Lemma H.2. the continuity of suggests 7 is also continuous. Given & with either LP or LE architectures, + x = Σm (()( ) E TR. is injective and has continuous inverse if:
for some E [N(D 1), No D²) when & admits LP architecture (by Theorem F3 and F.4)
for some E (ND, D2 when e admits LE architecture (by Theorem G.4 and G.5
XERNXD C R be the range of the sum-pooling $ and define mapping p: IR 24 + R taking the form of p(x, =) = r(x, 4 - d(z))). is straightforward to see that p as composition of continuous mappings, is also continuous. Finally, we show that function can be written in terms of p by its invariance to last N elements, which concludes the proof:
Let Zg = (2,
(2(0) x (6+1)
x (N)
x 1111))
a ( (i+1)
(N)) ,0 .x(-11))
x
1 (ze() ,. (...,,(())))) x(()) )(x(1))
(1)
1=1
I EXTENSION TO COMPLEX NUMBERS
In this section, we formally introduce the nature extension of our Theorem 3.1 to the complex numbers:
27

---

Published as a conference paper at ICLR 2024
Corollary 1.1 (Extension to Complex Domain). For any permataiioniivvriaan function f C 7 C, there exists continuous functions Φ : C + Rd and
R + such that
f(x) = -E b(x!))) for every j E [M], where L ( 1), D*) when & admits LP architecture, and L E [2ND, 4N D2] when & admits LE architecture.
Proof. We let first map complex features a( E CD.V [N] to real features お( [R( [xx R2D Vi E [N] by divide the real and imaginary parts into separate channels, then utilize either LP or LE embedding layer to map z(() to the latent space. The upper bounds of desired latent space dimension are scaled by 4 for both architectures due the quadratic dependence on D. Then the same proof' of Theorems F.3
G.4 and G.5 applies.
is also straightlorward to extend this result to the permutation-cquiivant Corollary L.2. For any functions é CCP - IR_ and p RD x RRL - such that [(X); = = =p(x/() EielNy $laz! for every j E [N] for every j E [N], where I, E [2N (1,4+)),4N") D²] when admits LP architecture, and L E [2ND, D when & admits LE architecture.
case:
equivariant function f: CCNx CN,, there exists continuous
Proof. Combine the proof of Corollary with Theorem
H.3
J THEORETICAL CONNECTION TO UNLABELED SENSING
Unlabeled sensing (Unnikrishnan al. 2018).
also known linear regression without correspon-
dence (Hsu et al. 2017; Tsakiris & Peng 2019 Tsakiris et al. 2020 Peng & Tsakiris 2020), solves
RR in the following linear system:
y PAx or
min y - PAx P.P
(50)
where A E MxN is a given measurement matrix, P II(M) is an unknown permutation, and y E R is the measured data. The results in Unnikrishnan et al. (2018): Tsakiris & Peng (2019)
show that as long as A is over-determinant (M > 2N), such problem is well-ppsed (i.e., has unique solution) for almost all cases. Unlabeled sensing shares the similar structure with our LP embedding
layers in which linear layer lifts the feature space to higher-dimensional ambient space, ensuring
the solvability of alignment across each channel. Specifically, as revealed in Theorem F33 showing the injectivity of the LP layer is to establish the argument:
X w. X' X'w,, Vi E [K] + X~XX X',
(51)
for arbitrary X, X' NDD, constructed weights w;, E [K] and large enough K. Whereas, to show the well-posedness of unlabeled sensing, it to show the following statement (Taakiris & Peng 2019)
Ax ~ Ax =
(52)
for sufficiently many measurements M. We note that our bijectivity defined between the set and embedding spaces, which allows change of order in the results and differs from exact recovery of unknown variables expected in unlabeled sensing.
In fact, the well- pose-posedsess of unlabeled PCA (aao et al. 2021b. studying low-rank matrix completion with shuffle perturbations, shares the identical deñnition with our set function injectivity. We rephrase it as below:
T3 x' 1, Vi E [N] X, X M
(53)
where M = EXEEMMNN rank X < r) is set of low-rank matrices, and denotes the i-th column of X. Based on Theorem in Yao al. (20II). we can obtain the following results:
Lemma J.1. Suppose M {X NxK, rank X) < r] with min(N, K). Then there exists an open dense set C M such that for every X, X E ll such that x, ~ x' ,, Vi E [K], then X X'.
28

---

Published as a conference paper at ICLR 2024
Proof. According to Theorem in Yao al. (2021), there exists Zariski- open dense set U M
such that: for every X E and P. E II(N), ) Vi E [K], rank([P|a) moreover, rank([P1a;
PR 2 r. And
PRœX])
if and only if P1 =.... Pk P II(N).
For every X E U such that z; ~ x', Vi E [K], if X o X', then either rank X) > r or rank( (X') r. This contradicts the fact that X, X' EU M.
As result, we can establish the injectivity of an LP layer restricted to a dense set. Theorem J.2 Assume D < N. Suppose @ RR + R takes the form of an LP embedding layer (Eg. 3
<(x)) [w x))
(54)
w) E ERDXK There exists open dense subset V C NxD such that for any X, x'X' EV, EnEINy p(al!)) = =mnEIN pl (x)(m)
where K = D-L, NK 1D)+)), and W |e1
implies X~ ~ X'.
Proof. Define M {X RXN raak (X) S D}. Since W has full row rank, then 7 r(X) = XW. RND - M is surjective. Let V = {X E R 7(X) E UI be the preimage of u under т. Since U is open dense in M, then V is open dense in R NxD. So far we have found an open dense set V such that for all x,'' X' V, XW, X'W E U. By Lemma D.2
EnEIN ((x(1)) = EnE(N] (a)())) implies Xw; ~ X'w; for ever E [K]. By Lemma J.1 can induce XW ~ X'W, and namely X
Theorem J.2 gives a much tighter upper bound on the dimension of the embedding space, which is bilinear in N and D. However, it is noteworthy that this result is subject to the scenario where the input feature dimension is smaller than the set length, and the feature space is restricted to a dense subset of the ambient space. Moreover, it is intractable to establish the continuity over such dense set. Our Theorem F.3 dismisses this denseness condition, serving as a stronger results considering all possible imputs. This indicates Theorem could potentially bring insights into the field of unlabeled sensing, which may be of an independent interest.
K REMARK ON AN ERROR IN PROPOSITION 3.10 IN FEREYDOUNIAN ET AL. 2022)
Fereydounian et al, examine the expressiveness of GNNs with mathematical tool summarized in Proposition 301 which in turn seems to indicate a much tighter upper bound N 2 for the size of the embedding space for set representation. However, we will show later, their proof might be deficient, or at least incomplete in the assumptions.
We rephrase their Proposition 3.10 in our language as below: Claim K.1 (An incorrect claim). Suppose Φ TR D + Re where L = N2D takes the following form:
R ((x: + 2z (T)) i>j
((x))s)=
(55)
& ((D) + +
for every i.j E [D],1 [M]. Then ΣnE(N ((x(1)) is injective.
The authors' proof technique can be illustrated via the following chain of arguments: for every X. X'X RNND
Σ (x)(1)) = Σ nE[N]
(l (m)) Lemmna
D
(x; + + ~ (0', + x MV Vi,j
Vi, j [D]
(56)
DE[N]
= [z; æ5} ~ lo's x') 2')] Vi E [D]
X X'.
(57)
While the first two steps is correct, the last implication (*) is not true in general unless one of 2, E [D] happens to be anchor of X. We formally disprove this argument below.
29

---

Published as a conference paper at ICLR 2024
Consider X, X' RXX and let P; (P II(N: p Then a mj] [ae o')
for every i.j E [D] is equivalent to saying P, nPj * 0, vi.j E [D]. While 0. It is well-known that intersection between each pair of sets is non-empty cannot necessarily imply the intersection among all sets is non-empty, i.e., P; nP3 # 0, vi, [D] / AiE(D) P: / 0, which disproves this result.
X is identical
to NEE P.
This also reveals the significance of the defined anchor. Suppose z;, for some i" [ is an
anchor of X. Then by Lemma E.2 li(()) P; = P... Thus P:- nP3 # & for every j E [ implies
P.. * 0, which essentially says (Ej Pi * 0.
Specifically, we can construct a counter-example. [0') x'2 x'al take values as below,
Suppose
X
x
02
33
X
2
2
01 0'1
2
22
x²2
1
2
(58)
2
and we can see:
17
2
1 0 0 1
0
0
2
+
[2]
Ø21 ~
|0'
0'2].
(59)
O
0
2
2
O
0 0 0
1
2
2
[
17
TO
07
[
27
1
(2)
Øz]
|x'1
x's).
(60)
2
0
0
1
2
0
2
2
[
17
0
07
[
27
2
2
0
0
0
0
0
1
2
1
1
+
222
~
[x'2
x's]
(61)
2
1
0
0
2
2
However, notice that:
17
27
1
2
2
2
1
2
7
1
=
X
[
22
033
+
X'
[x'1
8'2
x's]
(62)
2
2
1
2
2
which contradicts the implication
(*) in Claim K.1
30


Reviews:
[{"review_id": "RJuRZBt1KI", "reviewer": "Reviewer_XKbR", "summary": "## High level summary \nThis paper delves into the question of representations of sets as continuous functions in vector spaces. The work builds up on the ideas proposed in DeepSet, which shows that proves any permutation-invariant continuous function, can be restated by mapping each element to a vector, summing those vectors, and then mapping them to a scalar again. This paper addresses the unresolved question, whether sets over high-dimensional vectors can be represented efficiently, i.e., polynomially wrt to the set and feature size. \n\nMore formally, $X\\in R^{N\\times D}$ represents $N$ feature vectors of dimension $D,$ and function $f:R^{N\\times D} \\to R$ is defined to be permutation-invariant if for any permutation matrix $P$ it satisfies $f(P X) = f(X).$  The main contributions of the paper can be enumerated as\n- Thm 3.1 asserts that there $\\phi:R^D\\to R^L$ and $\\rho:R^L\\to R$ such that $f$ can be re-written as $f(X) = \\rho(\\sum_{i=1}^N \\phi(x^{(i)}))$ where $L$ is at most polynomial wrt to $N$ and $D$, with two different constructions that authors refer to as \"power mapping \" and exponential activation\". The theorem further asserts that $L$ is lower-bounded roughly by $ND$. \n- Thm 5.1 further shows that permutation equivariant functions, i.e., $f:R^{N\\times D}\\to R^{N\\times D'}$ such that  $f(P X) = P f(X),$ then there are $\\phi:R^D\\to R^L$ and $\\rho:R^D\\times R^L\\to R$ such that $f(X)_j = \\rho\\left(x^{(j)}, \\sum_i^N \\phi(x^{(i)})\\right)$ where again $L$ is polynomial in $N$ and $D$. \n\n## Technical summary \n\n*Set representation for one-dimensional elements $D=1$* The previous result proves that when $D=1$ there are $\\phi:R\\to R^L$ and $\\rho:R^L\\to R$ such that $f = \\rho(\\sum_i^N \\phi(x_i)$). This result mostly hinges on a particular function, referred to as power-mapping $\\Psi_N :R^N\\to R^N$, defined as  $\\Psi_N(X)_k = \\sum_i^N (x^{(i)} )^k.$ The paper goes on to explain that $\\Psi_N$ is \"bijective\" in a particular sense that deviates from the standard definition, in that $\\Psi_N(X) = \\Psi_N(X')$ implies rows of $X$ are a permutation of $X'.$ This allows us to introduce the mapping and its inverse as an identity and conclude $ f = f \\circ \\Psi_N^{-1} \\circ \\Psi_N  = \\rho(\\sum_i^N \\phi(X))$ where $\\rho:= f\\circ \\Psi_N^{-1}$ and $\\phi:= \\psi_N$. \n\n*The channel alignment problem in $D\\ge 2$* The first insight is explaining that the straightforward approach of representing each channel (dimension) of the high-dimensional features, will not work. This is because the mapping $\\Psi_N:R^N\\to R^N$ is permutation-invariant, meaning that while extending it to high dimension will preserve permutation invariance across each channel, these permutations are not going to be necessarily the same, referred to as alignment. This means that while we can ensure that while the naive approach ensures that each channel is preserved with permutation invariance, these permutations are not necessarily the same, and thus the vectors structure, where indices of vector do matter, may be lost. \n\n*Linearly lifting dimension to $L$ to resolve alignment* The main idea behind the proposed theory, as far as I can understand, is how to prevent this *alignment problem* by linearly lifting the $D$-dimensional elements to a much higher dimension $L$ that has lots of redundancies. Crucially, this lifting has the property channels of two different matrices after lifting can be aligned independently, then one matrix is a row-permutation of another.\n\nHere I will summarise the more detailed theoretical insights I can draw from various parts of the paper \n- *Anchor.* The main idea for the entire theoretical construction in fact develops on top of this alignment problem, suggesting a way to \"anchor\" different channels. The theoretical construct. Formally, anchor $a\\in R^N$ for data $X \\in R^{N\\times D}$, preserves the equality structure of the rows of $X$: $x^{(i)}\\neq x^{(j)}\\implies a_i\\neq a_j$.  \n- *Coupling of alignment with anchor.* If $a$ is an anchor of $X$, and $a'$ is a permutation of $a,$ and same permutation $P$ can be applied on every channel of $X$ to transform to the equivalent channel of $X'$, then rows of $X$ are a permutation of rows of $X'$. Thus, we can couple the alignment of various channels to the alignment of $a$ to $a',$ we can easily conclude that $X\\sim X'$ \n-  *Linear probes for anchors. * We can pick linear probes $w_1,\\dots, w_k\\in R^D,$ such that for any matrix $X,$ at least one of the $X w_1,\\dots, X w_k$ must be an anchor of $X$. This is achieved by picking a large enough $K$, and $w_k$'s such that every subset of size $D$ will be linearly independent, i.e., in general position, which is achievable by simply drawing from some Gaussian multivariate distribution. The claim follows from a cute pigeonhole principle. Now, if we do set representation of all $x^{(i)}$ and these linear probes $X w_k$'s, we can ensure that each of them are injective, and at least one of the $X w_k$'s is an anchor, but we still haven't coupled the alignment of the anchor to the rest of the channels. \n- *Coupling channel alignments to the anchor* Next, authors prove existence of coefficients $\\gamma_1,\\dots, \\gamma_K$ such that if$x\\sim x', y\\sim y'$ and  $x - \\gamma_k y$ is a permutation of $x' - \\gamma_k y'$ for every $k = 1, \\dots, K$, then permutation of $x\\sim x'$ and $y\\sim y'$ can be aligned. \n- *Lifting* Here, using the linear probes $w_k$ and coefficients $\\gamma_k$'s from previous step, we can define lifting operator colums  $w_{i,j,k} = e_i - \\gamma_k w_j$  for a polynomial range of $i,j,k$, and put all of them as columns of the lifting linear $W \\in R^{D\\times L}.$ Then each channel (column) of $Y = X W$ will be of the form $x^{(i)} - \\gamma_k X w_j.$ Therefore, by previous properties, if every channel (column) of $X W$ can be aligned to (is a permutation of) $X' W$, then rows of $X$ are a permutation of $X'.$ The *set representation* of each channel will follow naturally from this step.", "questions": "- The main results of this paper are obtained for a notion of permutation-invariance of $f,$ which is somewhat strictly defined over the entire input set $X.$ In real world applications, often the feature vectors $x$ represent learned or encoded features of a particular dataset. So in these cases, the \"user\" will be interested in \"relaxed set preserving properties\", in the sense that permutation invariance is only held over a subset (possibly even countable subset) of $R^{N\\times D}$. Can authors think of any interesting relaxations  on $X$ and extend their theory for those? (assuming it has certain properties or its feature vectors are chosen from a smaller/finite set)\n- Upon reading the paper, the architecture that authors propose resembles a network with depth \"2\" (perhaps this mysteriously encoded $\\rho$ , which in reality could be a highly complex $R^L\\to R$ function). In certain scenarios, there could be a hierarchical set representations, e.g., we want to embed sets of sets of sets, (or even more). Can authors comment on extendability of their theory, or in general any comments they may have for such multilevel/hierarchical sets?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Here are the main strengths I find in the appear:\n- The theory of the paper, to be best of my understanding, is sound and accurate. The statement of the theorems, lemmas, and the proofs, as much as I delved into, are sound and clearly stated. \n- The main problem that this paper focuses on, is a natural abstraction of real-world problems. \n- There are many clever and intuitive proof techniques used in this work, which may be interesting for the reader", "weaknesses": "Main issues: \n- While the paper presents a mathematically intriguing case, I am not quite sure what to draw from it from a machine learning perspective.  While theoretical contributions should certainly be welcome in the ML field, I think the theoretical works should take a few steps in demonstrating the relevance of their results for the broader community. For example, are there any concrete examples or use cases that these theoretical findings would be relevant? \n- Following up on the previous point, despite the embedding-sum decomposition, the construction of the $\\rho$ function $\\rho:R^L \\to R$ is still a complete black box. Again, these non-constructive arguments do not seem to add up to any \"practical insight.\" While this is not a 100\\% a critical point, if authors can think of ways to make it easier for the reader to imagine applications, they would broaden their audience and enhance the impact of the paper.  \n- While the paper is mathematically sound, it could benefit from more high-level idea developments both before and after the theorems. There are several places where a geometric interpretation is available, but not discussed in the main text. For example in the proof of Lemma 4.2 it becomes clear that a system of $w_k$'s in general position, if there are \"enough\" of them, at least one will be one that is not in the hyperplane orthogonal to difference between each two columns of $X$, perhaps this can even be visualised for some toy example with $D=2$ and $N=3.$ With the intuition that authors have built upon this case, if they are able to come up with more intuitive/visual depiction of these concepts, it would dramatically improve the paper's readability and accessibility.\n\n Minor issues:\n- The notion of injectivity for functions (Def 2.7), that $f(X) = f(X')$ implies rows of $X$ are a permutation of rows of $X$', slightly deviates from the standard notion that assumes \"a function f that maps distinct elements of its domain to distinct elements.\" It took me quite a few iterations to notice this slight difference. Perhaps author can caution the reader before or afterwards. Most readers will be inclined to assume the \"default\" notion which could lead to some confusions later on. \n- The notation $[a\\ x]\\sim [a'\\ x']$ which (for example used in Lemma 4.2) is somewhat ambiguous. Initially, I interpreted it as concatenating the two vectors along their main axis $[a\\ x] \\in R^{2N}$ which leads to lots of contradictions, while the authors implied stacking them along a new dimension $[a\\ x]\\in R^{2\\times N}$ which makes sense. While this might be consistent with the papers notation elsewhere, it is still good and helpful to highlight it for the readers that this implies stacking them and not concatenation.  \n- \"Comparison with Prior Arts\"? I'm guessing authors mean \"articles\" here? Is this a common shorthand for articles? While I don't want to sound authoritative, this seems like a rather informal writing style.\n- (page 17) \"pigeon-hold principle\" I'm guessing authors refer to \"pigeonhole principle\" :)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "6iTMtaxuXI", "reviewer": "Reviewer_a75R", "summary": "The authors propose a theoretical bound for the size of the embedding dimension of permutation invariant set functions which is not restricted to a single feature dimension, as some previous works.", "questions": "- Right before section 2.2, it is stated: \"The obtained results for D′ = 1 can also be easily extended to D′ > 1 as\notherwise f can be written as [f1 · · · fD′ ]⊤ and each fi has single output feature channel.\" I assume this is referring to the previous sentence and means \"the results obtained for invariance can be extended to equivariance, as..\" Is this correct?\n\nI would be curious to hear the authors opinion on the following:\n\nAccording to this and prior theoretical works, a very large embedding dimension $L$ is needed to maintain the universal function approximation ability of permutation invariant functions, however, many practical works which utilize permutation invariant set functions do not use such a large embedding dimension. Therefore, what is the practical takeaway for an implementation which wishes to utilize a permutation invariant function? There seems to be quite a large disconnect between theory and practice on this topic.  \n\n---\n\nOverall, my biggest conflict with this work is that there is no empirical experiment to corroborate the theoretical findings presented in the paper. While I cannot find issue with any of the claims made in the paper, if there is no way to empirically verify the given bounds, then it is quite difficult to understand their practical significance. Therefore, if the authors could provide an experiment or further discussion which illuminates this topic, I would be happy to revisit my current score.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem is very relevant, as many works which utilize permutation invariant functions do not consider the importance of the embedding dimension.\n- The derivation in the text appears thorough and rigorous", "weaknesses": "- It took me a while to grasp the concept of anchors. In lemma 4.2 I think it needs to be stressed that the same anchor is being applied over all the channels. Although the notation states this, it would be good to state it in plain text as well. \n- Under Lemma 4.2 there is a sentence which says \"then once each coupled pairs are aligned, two data matrices are globally aligned.\" Can you elaborate on the precise meaning of this sentence? What does \"aligned\" and \"globally aligned\" signify?\n- Why is Lemma 4.4 necesary? I do not see the reason for this, and I do not think it is explained well in the text either. At the beginning of page 8, it is stated that: \"Eq. 5 implies Eq. 6, but none of these seem to depend on Lemma 4.4 or \"Contruction point #3\" so I am not sure why it is necessary. I think this needs to be explained better in the text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "T0NDQIJe74", "reviewer": "Reviewer_jrmV", "summary": "This work concerns the expressive power of the DeepSets architecture [Zaheer et al., 2017], which is designed to model permutation invariant functions taking as input *sets* whose elements are real vectors. The basic parameters relevant for the model are N and D; N denotes the size of the input set and D denotes the dimension of its elements. The novelty of this work is in proving a poly(N,D) upper bound on the latent dimension sufficient for DeepSets to express *any* permutation-invariant function. Previously known bounds were exponential in the relevant parameters N and D.\n\nTo elaborate, the DeepSets architecture is of the form $g(x) = \\rho(\\sum_{i=1}^N \\phi(x^i))$, where $\\phi: \\mathbb{R}^D \\to \\mathbb{R}^L$ is a feature map for the set elements $x^i \\in \\mathbb{R}^D$, and $\\rho: \\mathbb{R}^L \\to \\mathbb{R}$ is an activation function. Both $\\phi$ and $\\rho$ are chosen by the model designer. Writing $\\Phi(X) = \\sum_{i=1}^N \\phi(x^i)$, where $X \\in \\mathbb{R}^{N \\times D}$ we can view $\\Phi$ a “sum-pooled” feature map for the input X. A key question for the practitioner is “How large should I set the latent dimension L to model *any* permutation-invariant target function?” This work shows that L = poly(N, D) is both sufficient and necessary (the bounds are not tight, however). Previously known upper bounds on L were exponential in N and D, thus this work represents a significant improvement over the previous state-of-the-art in theory.", "questions": "- One of the key technical proof ideas is showing that there exists some set of real numbers $\\Gamma$ s.t. for any $a,a’,b,b’ \\in \\mathbb{R}^N$, if $a \\sim a’$, $b \\sim b’$, and $(a-\\gamma b) \\sim (a’ - \\gamma b’)$ for all $\\gamma \\in \\Gamma$, then $[a, b] \\sim [a’, b’]$ (here, we view [a b] as “row $a$ stacked on top of row $b$”). Is the idea of using such linear transformations (of the form $a - \\gamma b$) to ensure alignment between the coordinates new? Or is this “linear coupling” a well-known fact in mathematics?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper presents novel ideas in designing the feature map $\\Phi : \\mathbb{R}^{N \\times D} \\to \\mathbb{R}^L$ to overcome limitations of previous work which did not generalize beyond the scalar-elements case (i.e., D=1). The combinatorial argument presented in the proof of Lemma 4.4 is particularly nice, though it is somewhat difficult to follow in the current exposition. Overall, I find the proofs insightful and quite surprising (I will elaborate on this below). Hence, I am inclined to accepting this paper.\n\nThe proof of the main result can be understood in stages. Let $\\Phi(X) = \\sum_{i=1}^N \\phi(x^i)$, where $x^i$ denotes D-dimensional vectors which are elements of the given “set” X. The ultimate goal is to design $\\Phi : \\mathbb{R}^{N \\times D}$ such that $\\Phi(X) = \\Phi(X’)$ implies $X \\sim X’$, where $A \\sim B$ means that the two matrices are equivalent up to row permutations (the opposite implication is obvious). The key difficulty is in “surviving” the sum-pooling operation $\\sum_{i=1}^N$.\n\nIdeas from previous work, such as the degree-N polynomial mapping $\\psi(z) = (z, z^2, z^3, \\ldots, z^N)$, can be applied entrywise to ensure that $\\Phi(X) = \\Phi(X’)$ implies that the rows of X and X’ are equivalent *individually*, which is a weaker implication than $X \\sim X’$. This only works only in the D=1 case and not for D > 1 since $X \\sim X’$ requires the coordinates of the rows $x^i$ be *jointly* aligned. To overcome this limitation, the authors propose novel ideas in the design of $\\Phi$ so that alignment between the coordinates of $x^i$ are ensured as well. Personally, I found this issue of coordinate-wise alignment quite challenging and was pleased to see its resolution here.", "weaknesses": "One shortcoming of this paper is that the exposition is quite hard to follow. It would help this paper reach a wider audience if the authors improved their exposition. I would suggest using less confusing notation and providing a more structured and detailed proof overview. Specific examples include:\n\n- The proof of their main theorem can be presented in stages as follows “Suppose $\\Phi(X) = \\Phi(X’)$. The polynomial mapping ensures that the *rows* of X and X’, when viewed as multi-sets, are equal. The main technical challenge is to ensure that the coordinates of the rows are aligned as well. This step combines two ideas: the “anchors” and the set $\\Gamma$, representing the additional linear mappings that ensure *pairwise* alignment …”\n- The linear projections that form the coordinates of $\\phi(x^i)$ are all represented as $w_j$’s. It would be more informative if different symbols were used for the different “types” of these mappings (standard basis, anchors, \\gamma’s …).\n- In p.7, the superscript notation for $w$ is confusing. For the samples, the superscript “(n)” was used to index elements of the set. Here it is used to denote different “types” of w. As mentioned before, simply using different symbols for different groups would avoid the use of unnecessary superscripts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "ZzgVRYT6SU", "reviewer": "Reviewer_oY1k", "summary": "The paper considers the representational powers of the permutation-invariant DeepSets architecture, which maps inputs $X \\in \\mathbb{R}^{N \\times D}$ to features $\\phi(X) \\in \\mathbb{R}^{N \\times L}$, computes a sum, and then computes an output with $\\rho: \\mathbb{R}^L \\to \\mathbb{R}$. Past results have shown that the DeepSets architecture can represent any permutation-invariant continuous function when $D = 1$ as long as $L \\geq D$, and that $L \\geq \\exp(\\Omega(\\min(\\sqrt{N}, D)))$ is necessary under certain assumptions about the $\\phi$ and $\\rho$ being implementable with analytic activation functions. This work shows that without these activation restrictions, permutation-invariant continuous functions can be exactly represented using embedding dimension $L = \\text{poly}(N, D)$. \n\nThey do so by introducing a pair of positive results in Theorem 3.1, one having a power mapping activation (where each input is mapped to its powers up to degree $N$) and another having an exponential activation. The constructions use a similar proof structure, both of which involve finding $\\phi$ that that the function $X \\mapsto \\sum_i \\phi(x_i)$ is continuous and invertible, which makes it possible to invert the mapping in $\\rho$ and then apply the permutation-invariant function directly. (Note that this means that, while $\\phi$ is a simple construction that can be made explicit, the inversion of $\\rho$ is an existential result that may correspond to a highly non-smooth function.) The feature mapping $\\phi$ is constructed carefully to ensure that inputs that are element-wise permutation-invariant but *not* vector-wise permutation-invariant map to different features; the authors do so by using *anchor* vectors to distinguish each vector. The remainder of the construction is dedicated to ensuring that some anchor exists for every possible input and that the desired constraints are enforced.\n\nThey contextualize their results by including several negative results to illuminate their design decisions, including Lemma 3.4 (why $\\rho$ and $\\phi$ must be continuous) and Theorem 4.5 (why there must be at least $D$ candidate anchor vectors for each input to have an anchor). They run brief experiments in Appendix K that train DeepSets models to compute lexicographical medians, and find that the necessary width $L$ grows polynomially in $N$ and $D$.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The contrast to the Zweig and Bruna lower bound is of theoretical interest, since it shows that requiring analytic activation functions changes the minimum width cost from polynomial in $N$ and $D$ to exponential. The work, coupled with its experimental results, suggests that an impressive amount of information can be encoded in sums of relatively low-dimensional feature embeddings, and that the functions that cannot be represented by standard DeepSets architectures are likely highly pathological or discontinuous.\n\nThe results are technically impressive, and I found no major errors in the proofs. In particular, the LP and LE constructions were clever, meticulous, and well-visualized by figures.", "weaknesses": "While I don't expect this paper to solve the problem, the non-explicitness of the construction means that $\\rho$ is likely to be a highly non-smooth function that is difficult to compactly approximate using a neural network architecture. In future works, I'd be interested in understanding whether feature dimensions that are larger polynomials in $N$ and $D$ make it possible to yield explicit (and ideally more smooth) $\\rho$ mappings. Perhaps the work could discuss possible approaches to bounding the smoothness of inversion functions? Or perhaps the authors can discuss which kinds of permutation-invariant functions $f$ are expected to have smooth features?\n\n## Minor issues\n* I was momentary confused by the conditions on $L$ in Theorem 3.1. At first, I thought $L$ *could not* be larger than $N^5D^2$ and not that this is an upper bound on the smallest $L$. Perhaps the lower bounds could be mentioned separately, for the sake of clarity? \n* Page 17 says \"pigeon-hold\" instead of \"pigeon-hole.\"\n* Lemma E.1 is much easier to parse after noting Remark E.2. Perhaps the remark could be included before the proof, or maybe the lemma could just define the $\\gamma_i$ values explicitly as prime numbers, since a generality in $\\gamma_i$ is not necessary for any of the proofs?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)