Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem
Authors: Tal Amir
Steven J. Gortler
Ilai Avni
Ravina Ravina
Nadav Dym
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Equivariant Neural Networks
Universal approximation
Geometric deep learning
multiset learning
injective multiset functions
learning on measures. WL test
TL;DR: We show that using analytic activations, one can construct finite-size NNs that are injective on multisets and discrete measures. As corollaries, we improve known results on approximation of multiset functions, and on equivalence of GNNs and WL tests

Abstract: Injective multiset functions have a key role in the theoretical study of machine learning on multisets and graphs. Yet, there remains a gap between the provably injective multiset functions considered in theory, which typically rely on polynomial moments, and the multiset functions used in practice, which rely on $\textit{neural moments}$ — whose injectivity on multisets has not been studied to date.

In this paper, we bridge this gap by showing that moments of neural networks do define injective multiset functions,  provided that an analytic non-polynomial activation is used. The number of moments required by our theory is optimal essentially up to a multiplicative factor of two. To prove this result, we state and prove a $\textit{finite witness theorem}$, which is of independent interest. 

As a corollary to our main theorem, we derive new approximation results for functions on multisets and measures, and new separation results for graph neural networks. We also provide two negative results: (1) moments of piecewise-linear neural networks cannot be injective multiset functions; and (2) even when moment-based multiset functions are injective, they can never be bi-Lipschitz.

Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem
Tal Amir Steven J. Gortler
Ilai Avni
Ravina Ravina'
Nadav Dym 1.3
Faculty of Mathematics, Technion Israel Institute of Technology, Haifa, Israel 2 School of Engineering and Applied Sciences, Harvard University, Cambridge, USA
3 Faculty of Computer Science, Technion - Israel Institute of Technology, Haifa, Israel.
Abstract
Injective multiset functions have a key role in the theoretical study of machine learning on multisets and graphs. Yet, there remains a gap between the prov- ably injective multiset functions considered in theory, which typically rely on polynomial moments, and the multiset functions used practice, which rely on neural moments whose injectivity multisets has not been studied to date.
In this paper, we bridge this gap by showing that moments of neural networks do define injective multiset functions, provided that analytic non-polynomial activation is used. The number of moments required by our theory is optimal essentially up to multiplicative factor of two. To prove this result, state and prove a finite witness theorem, which is of independent interest.
As corollary to our main theorem, we derive new approximation results for functions multisets and measures, and new separation results for graph neural networks. We also provide two negative results: (1) moments piecewise- neural networks cannot be injective multiset functions; and (2) even when moment- based multiset functions are injective, they can never bi-Lipschitz.
Introduction
Multisets a slight generalization of sets: like sets, they unordered collection of elements [xI...., Te }. but unlike sets, repetitions are allowed. Multisets arise naturally in many machine- learning tasks. They are the natural way to represent point clouds in IR3, neighborhoods of vertices in graphs, and any other data that has an intrinsic order that is immaterial to the task at hand.
We refer to functions and architectures whose inputs are multisets in Rd as multiset functions and multiset architectures. By definition, these functions do not depend on the order in which the multiset elements are given. This is important not only because the order is irrelevant and thus should not affect the output, but also because otherwise model may overfit the training data by making predictions based on its intrinsic order.
Multiset architectures are typically constructed using a combination of cormulatioo-invariian opera- tions such as sum- and max- max-pooling [34], attention mechanisms [23] and sorting [46]. One simple and popular approach, pioneered the seminal Deep-Sets paper [45], employs multiset functions based solely on sum- poon--pooing...... Namely, if the elements of all multisets come from some fixed alphabet
Ω any function f Ω R induces multiset function f. to which we refer as the moment of f:
(( F
(ax)
(1)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

While moment functions of the form (1) are simple, they are quite powerful. For example, in [45] it was shown that if countable, and the multisets have no repetitions (so they are just sets), then for an appropriate f + R. the induced function f maps the input sets injectively to IR
Injectivity is indeed a desired property for multiset functions. The search for such functions stems from the quest to find an architecture that can approximate all multiset functions. Clearly, if ʃ assigns the same value fS,) f(S2) to two different multisets Si & S2. then any architecture based on f will yield a poor approximation of a multiset function that assigns different values to S and S2.
The authors of [45] showed that injectivity is not only necessary for approximation, but also sufficient: Under the assumption that the alphabet f is countable, if the moment of maps multisets injectively IR.. then any multiset function can be written as a composition of the form F( F(f 2* Bb
g (Ei., fzz)) Motivated by this observation, the authors proposed neural architecture of this form, with the functions f and replaced by Multi-Layer Perceptrons (MLPs). This step was justified by the universal approximation power ML.ss
These intriguing results inspired further research, mainly focusing on seeking injective multiset functions of the form (I) for continuous alphabets such as 5 IR Preferably, such functions should (a) have a minimal embedding dimension m while ensuring that f Ω + R"' induces an injective f: and (b) be practical to compute. We next summarize some of these results:
For countable Ω2 the Deep-Sets paper as well [44] showed that embedding dimension 1 is sufficient. For Ω = TR, if the multisets contain at most n elements, and f is continuous, then an embedding dimension of 2 is necessary and sufficient for injectivity [41, 6, 42].
For Ω = IRd and multisets of size at most n, it was shown in [16] that m 2 nd is necessary for injectivity. As for an upper bound on the required m, while some polynomials discussed in the literature achieve injectivity with a rather high exponential [3, 26, 37] or polynomial [43] dimension m, recent work [9] achieved injectivity with chosen coefficients - thus achieving the lower bound essentially up to a multiplicative factor of 2.
2nd 1, using a polynomial with randomly
While the above works provide injective multiset functions with optimal or near-optimal embedding dimension, these functions are typically polynomials, and not the MLPs used in practice. As mentioned above, many papers [45, 44, 26] justify this by the fact that MLPs can approximate any function, and thus any polynomial. However, using this argument, we have no control on the number of neurons required for injectivity which in some cases may be infinite, In this paper, we address this limitation by providing practical and efficient method to construct functions of the form (1) that provably injective while having near-optimal number of neurons. We now state this formally.
show in Section 4.
1.1 Problem Statement
Let Ω Rd be set, which refer as an alphabet. Denote by S5n the collection of all multisets fæ1..... xx It with ......, 26 E Q and k S n. Any function f Ω + Rm induces a moment function f Sgn (9) + T as in (1). If f is injective, say that f is moment injective on Scn(1)) (f).
We also consider a natural generalization from multisets to measures, by identifying each multiset [ T& } with the measure μ Σ 62,, where 8 is the Dirac measure that assigns unit weight to æ. In this generalized setting, the induced multiset function f of (1) is just the integral of with respect to the measure μ. More generally, we consider signed measures μ = >i= w;dm;, with weights wy E R that can be negative, and points æ; that belong to an alphabet Ω C Rd. We denote the space' of all such measures by (9). A function f Ω + I induces a moment function f: (M) + Rmm defined by
f(w) = 1000=[1100 f(x)du(z)) = Σ wi (xx), where
w
(2)
'While we use the term space for Sz,, (22) and Mg.(9)) note that these are not vector spaces, since the sum of two measures in these spaces might be supported on more than points.

---

Domain
Mgn(144
Sgn(RR))
Mgn
S2n(29)
Sgn
Analytic activation
2n(d +1++1 +1
2nd +
2n + 1
1
Piecewise- winear activation
00
8
0
0
1
Lower bound
n(d
nd
71
1
1
The embedding dimension required for constructing injective functions of measures and multisets. R any infinite countable alphabet. First row: dimensions which our theorems guarantee injectivity when using analytic non-polynomial activations. Second row: with infinite alphabets, moments of neural network of any finite size with piecewise-linear activation cannot be injective, except in the multiset case, with some special countable alphabets such Ea,, defined in Appendix B.1. Third row: lower bounds the embedding dimension required for injectivity. These bounds show that our results from the first of the table are optimal essentially up to factor two.
Table 1:
If f is injective, we say that f is moment-injective on Mgn (Q). Naturally, injectivity on (2) implies injectivity on subsets of this space, such as the space of measures in Mgn (S2) that are probability measures, or that have only positive weights. In particular, if f is moment-injective on (gn(()))
MMn(()), then it moment-injective
To summarize, the main questions we focus on in this paper are:
Main Questions: (a) Under what conditions is an MLP f momenttinjectiin on spaces of multisets (gn(()) or measures (?) (b) How many neurons are needed achieve this injectivity?
2 Main Results
Interestingly, we find that the answers to these two questions largely depend on the activation function. Consider shallow neural networks / Rdd -> T of the form
f(x: A. b) o (Ax + b), A E gmxd b R"
(3)
with the activation function Ø E IR applied entrywise to Ax + b. Suppose that ar is analytic and non-polynomial; such activations include the sigmoid, softplus, tanh, swish and sin. In Section we show that for a large enough m, such networks f(x; A, b) with random parameters A,b are moment-injective on Mşn(12) and on Sg,, (2);; namely, their induced moment functions f of (2) are injective. This holds for various natural choices of Ω.
The embedding dimension m required in (3) depends on the dimension of Ω: For f Rd. to achieve injectivity on S5n. (2) or M.n. (S),, it suffices to take m 2nd + 1 or m 2n(d + 1) + respectively. When Ω countable, m or m 2n + are sufficient (corresponding d 0). In Appendix C we show that in all these cases, these embedding dimensions are optimal essentially up to multiplicative factor of two. These results are summarized Table 1. Appendix we also discuss examples where the optimal embedding cardinality for Mgn (R. is obtained.
At the core of our poof of moment injectivity is theorem which we name the finite witness theorem. This theorem enables reducing an infinite family of analytic equality constraints {F' (æ; = 0 0 E W) finite subset {P' (zx; 0,)
I...., m). This theorem generalizes the results in [9], where a special case of it was proved for semialgebraic domains and functions. The theorem we prove here (see Appendix A) applies much wider class of domains and functions, among which are analytic functions. In addition to our main result, we use the finite witness theorem to prove moment injectivity of Gaussian functions (Proposition 3.5) and deep MLPs (Proposition 3.6), and we believe it shall find additional applications beyond those discussed in this work.
Negative Results We also prove two negative results for moment-based multiset functions: We show that in contrast to analytic activations, with piecewise linear (PwL) activations, such as ReLU, leaky ReLU and hard arctan, moment injectivity on spaces of measures Mg. with infinite 12 is impossible. On multiset spaces Ssn, (I),, moment injectivity with PwL activations can be obtained for some irregular, countable Q, such as the alphabet Ω = Σ, defined in Appendix B, but not for infinite alphabets that arise naturally, like Ω = Rd zd or (0, 1)d. These results are summarized in the bottom row of Table 1. The second negative result is that while moments of MI.ss with analytic activations can be injective, they can never be stable in the bi-Lipschitz sense. This points possible advantage
3

---

ReLU
SiLU
Analytic
PwL.
0.3
0.25
Dim
Tanh
SiLU
Sin
HardTanh
ReLU
Leaky
17
7
10
0
0
7
50
0
0
4
5
100
0
0
(a)
(b)
Figure 1: (a) The number of failures of graph neural networks, with varying hidden dimension and activation, to achieve WL separation the 600 graphs from the TUDataset [30]. Analytic activations succeed on all graphs, as Theorem 6.3 predicts. (b) The normalized smallest singular value of multisct functions induced by piccowise-lince linear Rettoosss and analytic SiLU-networks. Piccewise-linee winear networks have singularities on squares intersecting the diagonal, Icading to non in-ieeecctiiity, Analytic networks are moment injective, but have singularities on the diagonal, which leads to non-Lipschitz inverse. See the end of Section 5 for more details.
of injective multiset functions that are not based on moments, but rather on sorting [3] or max-filters [5]. These multiset functions are not only injective but also bi-Lipschitz.
Implications for learning on multisets and graphs The result on moment injectivity of MLPs with analytic non-polynomial activation enables us to improve upon two seminal theoretical results in the study functions on multisets and graphs:
(a) Universality for multisets. In Corollaries 6.1 and 6.2, we show that any continuous function on space of multisets or measures respectively be presented a continuous vector-to-vector function composed with moment function f of an MLP the form (3). The MIP has the same embedding dimension as in Table 1. Essentially, this result replaces the moment-injective polynomials traditionally used in the characterization of multiset functions [45, 42] by MLPs.
(b) Separation power of Graph Neural Networks. Famously, the ability of most that of the Weisfeiler-Lemar (WL)
Neural Networks (MPNNs) separate distinct graphs graph isomorphism test, with equivalence taking place if the multiset functions used in the MPNN are injective [44]. Injective multiset functions are also used in generalizations of this result, such as the equivalence of high-order Graph Neural Networks (GNNs) to high-order WL tests [31, 26], and recent results on geometric GNNs and their corresponding WL tests [15, 16, 25, 33, 8].
Using the fact that an embedding dimension of one sufficient to achieve injectivity on (S2 with countable Ω2 we show in Theorem 6.3 that standard MPNNs with analytic non-pon poly-oooloiilll activations and random parameters have the separation power of WL, even when their architecture only uses a single feature per node. This be compared the one hand with the construction in [44], which also requires a single node feature but uses multiset aggregators that are not MLPs, and on the other hand with works that do consider MLPs with ReLU activations [31, 1]. but require a number of node features and parameters that depends polylogarithmically on the number of nodes. In contrast, our construction requires a single node feature and fixed number of parameters (though we have no bound on the number of bits required for achieving separation using floating-pon -oaiit arithmetic). numerical verification of these results is shown in Figure ((a), where we show that, on the 600 graphs in the TUDataset [30], MPNNs with three different analytic activations were equivalent to the WL-test even with single node feature, whereas three different PwL activations were in some cases weaker than WL when a small number of node features was used.
Independently of this work, was recently proved in [17] that MPNNs with certain analytic activations can separate all trees of depth two, while separation fails with PwL and even peacewise-ppolnoone activations. Our results here are stronger in that we show separation for all graphs separable by WL. and all analytic pol-polyno activations.
2.1 Notation
We denote vectors by boldface letters, e.g. 2c, y. and scalars by plain letters xr y. The inner product of a, x is denoted by Throughout this work, the term measure always refers to signed measures.

---

3 Moment injectivity with analytic activations
In this section, we prove moment injectivity for MLPs with analytic non-poly non-polynomial activations. We begin by showing that for any non-polynomial function R + I. measure E (f) is uniquely determined by the integrals of all functions {a(a æ + b) E RR b R}. When this holds, we say that a is discriminatory:
Definition 3.1. Let R + be a continuous function. We say that a is discriminatory for any two signed Borel measures je, jz on R= that are distinct (i.e. * μ(), finite (i.e. |1 (A)), (A)l < co for all Borel A C IRd) and compactly supported, there exist a E Rd, E R such that
f aaa x b)dp(x) # / a(a b)dx'()) (x),
(4)
The definition of discriminatory activation functions comes from² Cybenko's 's celebrated paper on the universality of MIPs [7], where it was proved that sigmoid-like activations discriminatory. This, in turn, was used to prove the universality of MLPs with such activations. In later papers [24, 32] was shown that universality can be achieved by all continuous non-polynomial activations. In the following simple proposition, we use a reverse argument to that used by Cybenko, and show that activations that allow for universality are automatically discriminatory:
Proposition 3.2. Let R R be continuous function that is not polynomial; then is discriminatory.
Proof idea. Suppose that ( x + b)dμ = fo x b)dp' for all a, b. By the universality theorem for shallow MLPs [32], all continuous functions can be approximated by linear combinations of functions of the form aa b). Thus, for any continuous function f. fdp fdp'. Since
a measure is uniquely determined by its integrals of all continuous functions, μ is equal to p².
Next, we shall prove our main result: is analytic and discriminatory, then shallow MLPs of reasonable width with as activation are moment injective.
Theorem 3.3. Let o R + R. be an analytic non-polynomial function. Let n. E N. and set m (d + 1) + Then for Lebesgue almost any A E Rmxx b E RT the shallow MLP f(x) = (AA x + b) moment injective on Mcn(R namely, the function : MMg((!)) + R. given by
f(N) = Σ wio (Ax; + b) for μ Σ wroa:
(5)
is injective.
For moment injectivity Sen (, suffices take m 2nd + 1. For Min(22) Sgn(2) with countable Σ, m = 2n and m respectively are sufficient.
Our proof of Theorem 3.3 is based on separate theorem, which name the finite witness theorem. This theorem enables us to show that, since any two measures can be discriminated by an integral la(a- x b)du(2) for some choice of parameters a,b, there exists finite number of witness parameters (a,, b)) that are sufficient for discriminating between any measures. This holds under the assumption that the number of points in both measures is bounded. We shall now state a simple version of this theorem, which suffices for proving Theorem 3.3.
Theorem 3.4. (Finite Witness Theorem, simple version) Let MI C R. be countable union of affine sets, each of which is of dimension & D. Let W C RD be open and connected. Let F (x; 0) ML x W + IR be an analytic function. Then for almost any (0(1)... (o..).... 0(2D+1)) the following set equality holds:
w22++ e (0()),..)()++))
((x, y) E x
M
F (z; 0) = (); VO E W) =
{(x, y) E x
F
x;; 00) = y: ( Vi 1,... ....... 2D 11.
'wtt minor change: we do not require that all measures considered are supported on the same fixed compact set.
5

---

Using the finite witness theorem, we are now ready to prove Theorem 3.3.
Proof of Theorem 3.3. Recall that signed measure μ M ( can be parameterized, albeit not R2 representing points in R and weight vector w (Wi,...; Wn), such that μ = Di=1 widn:: Let be the space of measure parameters
uniquely, by matrix X = (æI,.... Fn) .n.)
{(w, X) E R x Rdxa).
Similarly, let W be the space of parameters
W ((a,b) E x R).
Define F: M W- by
F(w, x;a = Σ
wPo 2; b).
(6)
==1
We now invoke the finite witness theorem. Set 2n 1) + 1, and note that m dim (M) + Recall that F is analytic. According to Theorem 3.4, for almost any choice of (a,, b;) E W,
F (w, X; a, b) = (w', X'; a, b), V (a, b) E W] [((w, ((),))). (w', X)) M M F (w, X; a, b,) (w', X'; a. b,), Vi -.....,m m)
[(w X) (w', X)) E
(7)
Let A Raad with rows a am and b (b) (bi....,buy bm.) Suppose that A.b indeed satisfy (7).
Let u.pl pl E (.n be two measures with parameters (w, X). (w X') respectively. Equation (7) implies that if the function f of (5) satisfies f (μ) = f (j(), then (w. X), (w', X') are not separated E Rd E RR. Since a is discriminatory, this in
by the entire family of functions {F (::a,b) turn implies that = p'. This concludes the proof of moment injectivity on M.n((()
If are only interested in moment injectivity Sgn (I²), it is sufficient to apply the theorem
=
U WC (0.1)"
{(w, X)
E Rdxa)
which is finite union of affine subspaces of dimension D = nd. Thus, Theorem 3.4 only requires achieve injectivity on Szn, (R'). Similarly, when considering MM.((2) (2) with
m 2nd countable Σ, the theorem can be applied to domain M. that can be written as countable union of affine spaces of dimension n, which yields m 2n Finally, Ssn, (Σ) is a countable union of points, namely zero-dimensional affine subspaces, and therefore m = is sufficient in this case. D
3.1 More on the finite witness theorem
The finite witness theorem can be used to prove moment injectivity for functions beyond the activated inner-product form of (5). As an example, we show in the following proposition that Gaussian functions with random parameters
moment injective:
Proposition 3.5. Let n.d N and set 2n(d 1) 1. Let V (3, E Rd x R, Then for Lebesgue almost any (yi, o.) E W the function
|| -ill
-
|| (-lle
y 11%)
f(x)
exp
of
exp
0²
moment injective on Mgn (IE.).
Proof idea. Any two measures with bounded support can be separated by the moment Gaussian function supported on small ball around point where the measures disagree. Thus, measure in ( uniquely defined by the continuous family of all its Gaussian moments. The finite witness theorem then shows that finite number suffices.
D

---

The full version of the finite witness theorem (Theorem A.2), discussed in Appendix A, is more general than Theorem 3.4. In this version, the class of sets admissible as M is the class of o subanalytic sets. While its definition is technically involved (see Appendix A), this class is quite vast: includes all open sets, all semialgebraic sets (including affine spaces, polygons, and closed fz-balls), and countable unions thereof. The analyticity assumption on F is also substantially relaxed to o-subanalyticityy though this requires an additional condition (13) in the theorem assumptions.
The proof of the finite witness theorem is non-trivial, and we regard it as the main technical contri- bution of this work. In essence, the proof generalizes a similar result in [9], which only applies to polynomial functions on sets defined by polynomial constraints - known as semialgebraie sets. This class of sets has several nice properties, which the proof in [9] relies on: It is closed under linear projections, finite unions, finite intersections, and complements. Moreover, any semialgebraic set is a finite union of smooth manifolds.
Our generalization from the polynomial to the analytic setting consists of two steps: First, we generalize the theorem larger class of sets, called globally subanalytic sets, which are known to be an o-minimal system - essentially, a familly of sets that has the same nice properties of semialgebraic sets mentioned above. This generalization straightforward: however, it does not allow F to be an arbitrary analytic function, and thus does not suffice even to prove the weaker version. Theorem 3.4. Our second step is then to observe that our proof carries through also when considering countable unions of globally subanalytic sets, which we name o-subanalytic sets. This, in turn. paves the way to prove the full version of the finite witness theorem.
Using the more general version of the theorem, we can prove the following proposition, which in particular implies moment injectivity of deep networks, provided that the last activation is analytie:
Proposition 3.6. Let a R R be analytic non-polynomial function. Let n, d E N and set m = (n + 1) 1. Let Rd - RR. be an injective function that is a composition of PwL functions and analytic functions. Then for Lebesgue almost any A E Rmmx , R the function (Af(#) + b) is moment injective on Mgn(
In particular, could be a neural network that has increasing widths, linear layers with full rank, and injective activations that are either PwL analytic (such as leaky ReLU or sigmoid). Therefore, Proposition 3.6 shows that increasing the network depth will not have a negative effect on its moment-injectivity. While this may seem trivial, what is not immediate in this formulation is that the embedding dimension m depends linearly on n rather than n L. The reason this is true is that the shallow neural network applied to F(z) will only 'see" inputs that originate from the set F (R.). and in Appendix A we show that this is a o-subanalytic set dimension I d.
4 Failure of moment injectivity for piecewise-linear functions
In this section, we show that moments of neural networks with piecewise-lines activations (such as ReLU, leaky ReLU and the hard hyperbolic tangent) cannot be injective when the alphabet is infinite, except for some singular cases discussed below.
Proposition 4.1. Let d, m and n 2 2 be natural numbers and Ω2 C IRd an open set. If Rd + R is piecewise linear, then it is not moment injective on Szn, (2).
Proof. There exists some open U Ed such that (xx) is of the form (xx) Ax + b in U. Let
æp E U and let d + 0 E TR. For small enough > O, we have that Tg + cd and æo cd are in U. It
follows that the multisets gf K Za and g 2o cd, xo + cd] have the same moments:
(ar) + (m)) = 2 (Aro + b) = A(ro ed) + A ( + ed) b = <b(20 - ed) + (b
This proves that 1a is not moment injective on (9).
The basic idea behind the above proof is that inside a linear region of ab. different multisets with the same center of mass have the same moments. The same idea can be used to prove failure of moment injectivity of PwI. functions on (c.( for any infinite Z and on (Zd). On the other hand, PwI. networks can moment injective on Ms,, with finite Ω as well as on Sgn somewhat pathological infinite countable alphabet. These results are described in Appendix B.
(F. when Σ is
7

---

Failure of bi-Lipschitzness for general moment functions
In Section 3 we have shown that a neural network f :Rd R with analytic non-polynomial
activation can induce an injective multiset function f Ss (RR) + R". Ideally, we wish such f to be bi- bi-Lipschitz, meaning that there exist constants 0 < C' such that
(8) where W2 S2) is the 2-Wasserstein distance between the two measures 141, #2 that assign uniform weights to the points S1, S2 respectively. Unfortunately, we find that any moment function induced by some f _ + 18 cannot be bi-Lipschitz, assuming that f is differentiable in at least one point.
c. (2 82) = (If(S)) f(S2)) C (2 S2), LSS, S2 E (R")
Proposition 5.1. Let 2 d. m E N, and let f TRd IRm be differentiable some Di E TR.. Then the induced moment function f Sg., + R.m defined in (1) is not bi-Lipschitz.
Figure ((b) illustrates the underlying reason for this failure of bi-Lipschitzness, and its relation to the non-injectivity of PwL moments: consider shallow neural network f R - R with ReLU activations. and its induced moment function f( 21, x2 f(11) fzz) on multisets S42 (R). The left-hand side visualizes the ratio 02/01 of the smallest and largest singular values of the differential matrix Df. The function is PwL, with four linear regions I,..., 14 in [0, 1]. The linear regions of f in (0, 1J2 are thus the rectangles I, T.. As seen in the figure, there are degeneracies in the rectangles that intersect the diagonal, as for small enough e, fff + c, 2y <B) = f(f zo: zy B) as in the proof of Proposition 4.1. The right-hand side visualizes the same ratio when the analytic the diagonal. Intuitively, this
SiLU activation is used instead of ReLU. We that Df is singular is because the differentiability of implies that it behaves locally like an affine function. This leads to singularities of f on the diagonal, which do not prevent it from being injective, but do prevent it from being bi-Lipschitz. proof of this phenomenon given the appendix. See also Theorem 21 in [4], which independently proved a similar result for general invariant embeddings.
6 Applications: Universal
A Approximation and Graph Separation
As mentioned in the introduction, injective multiset functions can be used construct multiset architectures with universal approximation power, and to prove separation results for graph neural networks. In this section, we present some immediate corollaries of our results for these two applications. Proofs are in Appendix D.3.
6.1 Universal approximation of functions multisets and measures
Our first approximation result focuses on multisets of fixed size n with an alphabet K C Bd that is compact. Any such multiset is determined by a choice of n vectors in K, possibly with repetitions and irrespective of order. Thus, multiset functions on this space are equivalent to permutation invariant functions on K". Using the finite witness theorem and basic topological argument, we prove:
cermutation-invariant
Corollary 6.1. Let n. E N and set m 2nd + 1. Let a RR - R be an analytic non-pol non-polynomial function. Let K C Idd be compuct set. Then there exist A E Rmxd b E T&d such that for any continuous permutation-invariue
f K + R, there exists a continuous F Rm - such that
Eo(AA (AD; +b) +D). ())
f(X) = Σ
VX =(x (æI,... Fx) E K
Combining Corollary 6.1 with the universality of MLPs, we get that any continuous permutation- invariant function on K"" can be approximated by expressions of the form (9) with F replaced by an MLP. Similar results were obtained for moments of polynomials rather than of MLPs in [45, 42, 9].
is worth noting that an analogue Corollary 6.1 cannot hold with piecewise-linear a,, assuming that K has non-empty interior. This is because by Proposition 4.1, any fixed moment function induced by a PwI. MLP will not be able to separate all multisets, whereas any two distinct multisets can be separated by some continuous Though, with PwL o, may approximate any given f to
8

---

arbitrary precision, by taking the embedding dimension m to infinity. In contrast, with an analytic we are able to specify a finite m 2nd + 1 for which exact equality (9) is guaranteed.
Since our injectivity results on multisets extend to measures, it is natural to seek an extension of the above approximation result to functions defined on measures. Denote by Psn (K) the space of probability measures supported
I n. points in K S Rd, endowed with the 2- 2-Wassesteiin metric. Corollary 6.2. Let n. d E N and set
2n(d + 1) +1 Let IR + I be analytic and non- polynomial. Let K C Rd be compact. Then there exist A E IRmxd b E In such that for any continuous (in the 2- B-Wassesstein sense) J P (K) IR, there exists a continuous F R. I such that
f(u)= F (Ax + b)du(z)) V
follows from Corollary 6.2 that any continuous function f (K) - R with com- pact K S. Idd can be approximated to arbitrary precision by functions of the form f(u) F (SEe (AA + b)du(())), with A E RRxd b RRm m = 2nd + 1, and being an ML..
6.2 Graph separation
We now discuss the implications of Theorem 3.3 for graph separation, using terminology from [44].
Let Ggn(E) (E) be the collection of all graphs G (V, E,, h()) with at most n vertices, endowed with
vertex features hn E Σ, where Σ C IR is countable alphabet. We consider GIN-like [44] MPNNs
that recursively, for 1, ...... T, calculate node features h from the previous features h (t-1) by
(c) Σ
(A(1) (1 (1 + + + b(1))
(10)
After the T iterations concluded, global feature is computed via readout function:
hg = (A(T+I) + b(T+1)).
(11)
VEV
We choose all features hG and he for 1 S. < T, to have the same dimension m. Based on the fact that MPNNs are equivalent 1-WI. when the multiset functions are injective [44], and on our injectivity results for countable alphabets, we prove that:
Theorem 6.3. Let n, d, T E N and let E. C Rd be countable. Let m 2 be any integer. Let R be analytic non-polynomial function. Then for Lebesgue almost any choice of A A b(t) and rp(t), the MPNN defined in (10) and (11) assigns different global features to any pair of graphs G1, G2 E GZ)(E) that can be separated by T iterations of 1-WL.
Graph separation with continuous features Up to now, we have discussed graphs with node features coming from countable alphabet. Since Theorem 3.3 applies multisets with continuous alphabets, it can be applied to separation of graphs with continuous node features as well. In particular, the paper [15] explains how the random semialgebraic multiset function from [9] can be used to construct architectures for graphs with continuous features, whose separation power is equivalent WL tests. Their focus is on showing that the embedding dimension their construction depends linearly on the dimension of the graph space, rather than grows exponentially with the number of message-passing iterations T. Similar results can now be obtained by using our random analytic multiset functions. We leave full description of these aspects to future work.
7 Experiments
Empirical injectivity and bi-Lipschitzness We empirically investigated the injectivity and bi- Lipschitzness of moments of shallow networks of the form (3), by randomly generating a large number of pairs of multisets of n vectors Rd, and computing the optimal constants c, C' for which (8) holds for the generated pairs. The ratio e/C for varying activations and embedding dimension m shown in Figure Here d and = 1000. Similar qualitative results were obtained for other values of d and n; Figure 4 in Appendix E.

---

We observe several interesting phenomena: First, at low embedding- dimensions, the ratio c/C for PwL networks is exactly zero, indicating that they are not injective even on the finite sam- ple set. In contrast, for analytic activations, c/C is always positive. Indeed, we expect an- alytic activations to be injective on a finite sample even with embedding dimension m = 1, since finite sample set has an intrinsic dimension of zero. Next, we observe that c/C nat- urally improves as m increases. Finally, we note that even for high m, c/C is rather small. Indeed, it were possible to consider all pairs of multisets when computing c/C, we would
get zero for all activations and all embedding dimensions, as follows from Theorem 5.1. For additional details on this experiment, Ap- pendix E.
10-2
10-3
10
Cos
10-5
Graph Separation To validate Theorem 6.3, we conducted the following experiment: we con- sidered 600 graphs from the TUDataset [30]. On each graph we ran three iterations of the WL test, and three iterations of MPNNS with the Graph Convolutional Layers from [18] with different activations and hidden dimensions. Our goal was to check in how many graphs the MPNNs returned a vertex coloring that differs from the coloring provided by the WL test. The results are shown in Figure (()). As seen in the table, with the three analytic activations tested, the vertex coloring of MPNN was always equivalent to 1-WL, even with a hidden dimension of 1. On the other hand, for the three PwL activations, there were inconsistencies in about 1 1% of the graphs, even with hidden dimension of 50.
TanH
10
Sigmoid
HardTanH
10-7
ReLU
10
10
100
1000
Embedding dimension
Figure 2
We note that while analytic activations fully succeeded in separation, in some cases the separation was rather weak: while the distance hetween features of non-equivalent nodes computed by the MPNNs was typically around 0.1, the least-separated features had a distance of 10-7 7, In future work, could be interesting to investigate whether MPNNs can be trained to yield larger distances between the features of all non-equivalent nodes. Further details on this experiment appear in Appendix E.2,
8 Conclusion
We have shown that moments of neural networks with an analytic non- non-polnoomial activation are injective on multisets and measures. We have also shown how this can be harnessed to construct universal approximators for multiset functions, as well as prove separation results for graph neural networks. A key advantage of our approach is that enables constructing proofs using real models that are used in practice, rather than idealized versions of them as done in previous works.
may seem tempting, due to our theoretical results, to conclude that analytic activations should perform on multisets better than piecewise- linear activations. We stress that we make no such claim. Indeed, while the separation results in Figure ((a) corroborate our theory, PwL. networks fail to separate only 1% of the graphs in our experiment. Furthermore, at high embedding dimensions, the empirical bi-Lipschitzness
Figure 2 does not seem to strongly depend on the analyticity of the activation function. Our claim is thus much more modest: we claim that multiset architectures with analytic activations are easier to theoretically analyze, and we hope that pursuing this analysis shall lead to fruitful theoretical and practical insights, which may ultimately benefit multiset architectures with either type of activation.
Lastly, we note that the finite witness theorem, which is presented here as tool for proving moment injectivity, may prove valuable as a general tool for reducing an infinite number of equality constraints to finite number, and we believe it will find additional applications beyond the scope of this paper.
Acknowledgements N.D. is partially funded by Horev Fellowship. T.A, R.R. and N.D. partially funded by ISF grant 272/23.
10

---

References
[1] Anders Aamand et al. "Exponentially Improving the Complexity Simulating the Weisfeiler- Lehman Test with Graph Neural Networks". In: Advances in Neural Information Processing Systems 35 (2022), pp. 27333-27346.
[2] Radu Balan, Pete Casazza, and Dan Edidin. "On signal reconstruction without phase". In: Applied and Computational Harmonic Analysis 20.3 (2006), pp. 345-356.
[3] Radu Balan, Naveed Haghani, and Maneesh Singh. "Permutation invariant representations
with applications to graph deep learning". . In: arXiv preprint arXiv:2203. 077460766 (2022).
[4] Jameson Cahill, Joseph W Iverson, and Dustin G Mixon. "Bilipschitz group invariants". In:
arXiv preprint arXiv:2305. 1724/ (2023).
[5]
Jameson Cahill et al. "Group-invariant max filtering". In: arXiv preprint arXiv:2205.14033
(2022).
[6] Gabriele Corso et al. "Principal neighbourhood aggregation for graph nets". In: Advances in Neural Information Processing Systems 33 (2020), pp. 13260-13271.
[7] George Cybenko. "Approximation by superpositions of sigmoidal function". In: Mathematics of control, signals and systems 2.4 (1989), pp. 303-314.
[8] Valentino Delle Rose et al. "Three iterations of (d 1)- test distinguish non isometric clouds of d-dimensional points". In: arXiv e-prints (2023), arXiv-2303.
[9] Nadav Dym and Steven J Gortler. "Low Dimensional Invariant Embeddings for Universal Geometric Learning" In: arXiv preprint arXiv:2205.02995 (2022).
[10] Matthias Fey and Jan E. Lenssen. "Fast Graph Representation Learning with PyTorch Geomet- ric". In: ICLR Workshop on Representation Learning on Graphs and Manifolds. 2019.
[11] Jean Feydy al. "Interpolating between Optimal Transport and MMD using Sinkhorn Diver- gences". In: The 22nd International Conference on Artificial Intelligence and Statistics. 2019, pp. 2681-2690.
[12] Hillel Furstenberg. "Ergodic fractal measures and dimension conservation". In: Ergodic Theory
and Dynamical Systems 28.2 (2008), pp. 405-422.
[13]
Allen Hatcher. Algebraic Toplogy. Cambridge University Press, 2002.
[14] Michael Hochman. "Lectures fractal geometry and dynamics". In: Unpublished lecture notes, Available online at http://math. huji. ac. hwtnhhohwmm//cuueeffccuuus2/2220 notes. j6ne-26. pdf (2012).
[15] Snir Hordan al. "Complete Neural Networks for Euclidean Graphs". In: arXiv preprint arXiv:2301.1382 (2023).
[16] Chaitanya K Joshi et al. "On the expressive power of geometric graph neural networks". In: arXiv preprint arXiv:2301 09300 (2023).
[17] Sammy Khalife and Amitabh Basu. "On the power of graph neural networks and the role of (2023).
the activation function". In: arXiv preprint arXiv:2307.0444
[18] Thomas N. Kipf and Max Welling. "Semi Superviepe Classification with Graph Convolutional Networks". In: 5th International Conference on Learning Representations, ICLR 2017. Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL: https: /ttp:://openreviii www.:eee/ffooreeee
[19] Steven G Krantz and Harold R Parks. primer of real analytic functions. Springer Science & Business Media, 2002.
[20] M. G. Krein and A. A. Nudelman. The Markov moment problem and extremal problems. Translations of mathematical monographs. American Mathematical Society, 1977.
[21] John Lee. "Smooth manifolds, Introduction to smooth manifolds". Graduate Texts in Muthematics 218 (2013).
[22] John M Lee and John M Lee. Introduction Smooth manifolds. Springer, 2003.
[23] Juho Lee al. "Set transformer: framework for attention- based cermutation-invarte neural networks". In: International conference on machine learning. PMLR. 2019, pp. 3744 37533. [24] Moshe Leshno et al. "Multilayer feedforward networks with nonpolynomial activation function can approximate any function". In: Neural networks 6.6 (1993), pp. 861-867.
[25] Zian Li et al. "Is Distance Matrix Enough for Geometric Deep Learning?" ?" In: arXiv preprint
AXXv:2302.05744 (2023).

---

[26] Haggai Maron et al. "Provably powerful graph networks". In: Advances in neural information processing systems 32 (2019).
[27]
Chris Miller. "Tameness in expansions of the real field". In: Logic Colloquium. Vol. 2005,
pp. 281-316.
[28]
Boris Samuilovich Mityagin. "The zero set of real analytic function". In: Mathematical Notes 107.3-4 (2020), pp. 529-530.
[29] Guido F Montufar et al. "On the number of linear regions of deep neural networks". In: Advances in neural information processing systems 27 (2014).
[30] Christopher Morris et al. "TUDataset: A collection of benchmark datasets for learning with
graphs". In: /CML. 2020 Workshop Graph Representation Learning and Beyond (GRL+ 2020). 2020. arv: 2007. 0006.08663. URL: www www.graphllcom eappinearnin..11. .o..
[31] Christopher Morris et al. "Weisfeiler and leman go neural: Higher-order graph neural networks". In: Proceedings of the AAAI conference on artificial intelligence. Vol. 33. 01. 2019, pp. 4602- 4609.
[32]
Allan Pinkus. "Approximation theory of the MLP model in neural networks". In: Acta numerica 8 (1999), pp. 143-195.
[33] Sergey N Pozdnyakov and Michele Ceriotti. "Incompleteness of graph neural networks for points clouds in three dimensions". In: Machine Learning: Science and Technology 3.4 (2022),
p. 045020.
[34] Charles R Qi et al. "Pointnet: Deep learning point sets for 3d classification and segmen- tation". In: Proceedings of the IEEE conference on computer vision and pattern recognition.
2017, pp. 652-660.
[35] Maithra Raghu al. "On the Expressive Power of Deep Neural Networks", In: arxiv preprint arXiv: 05336 (2017).
[36]
Walter Rudin. Real and Complex Analysis. McGraw-Hie Hilll Scienc//ininnerrnngMMat, 1986.
[37] Nimrod Segol and Yaron Lipman. "On Universal Equivariant Set Networks". In: International Conference on Learning Representations. 2019.
[38] Guillaume Valette. On subanalytic geometry. June 2023.
[39]
Lou Van den Dries and Chris Miller. "Geometric categories and o-minimal structures". In: (1996).
[40]
Cédric Villani et al. Optimal transport: old and new. Vol. 338. Springer, 2009.
[41] Edward Wagstaff et al. "On the limitations of representing functions on sets". In: International Conference on Machine Learning. PMLR. 2019, pp. 6487-6494.
[42] Edward Wagstaff et al. "Universal approximation of functions on sets". In: Journal of Machine Learning Research 23.151 (2022), pp. 1-56.
[43] Peihao Wang al. "Polynomial Width is Sufficient for Set Representation with High- dimensional Features". In: arXiv preprint arXiv:2307.0400) (2023).
[44] Keyulu Xu et al. "How Powerful are Graph Neural Networks?" In: International Conference on Learning Representations. 2018.
[45] Manzil Zaheer et al. "Deep sets". In: Advances in neural information processing systems 30 (2017).
[46] Yan Zhang, Jonathon Hare, and Adam Prügel--Bnneee "FSPool:
Learning Set Representations
with Featurewise Sort Pooling". In: International Conference on Learning Representations.
12

---

A Finite witness theorem
In this section, we state and prove the full version of the finite witness theorem (Theorem A.2), which is more general than Theorem 3,4 stated in the main text. Before laying out the formal definitions and proofs, we begin by describing the context of these results. While this section makes use of notions from algebraic geometry and real analytical functions, it is self-contained and most of it only requires knowledge of elementary calculus and some topology.
The finite witness theorem is essentially a tool for reducing an infinite, continuously parameterized family of constraints y(2; defined by random parameters 0,,- oI...., f.. the famous proof of uniqueness for phase-retrieval measurements in [2]. In that work, functions p(z,0) 0): C" x C + IR of the form p(z; 0) = (z, 0)] were considered, and it was proved that a finite number of ~ 4n random measurements O; are sufficient uniquely determine a signal, up to unavoidable global phase ambiguity. The proof in [2] achieves this result by showing that the values p(z: 0) for all possible As are sufficient determine the signal uniquely, and then uses a real
0 v0 to finite subset of constraints p(z; 0,) 0, i = 1,...y m, This general approach seems to have originated from
and dimension-coume counting argument to show that this continuous family of measurements can be replaced by finite subset, defined by m 4n random vectors (witesses)) (0, ) without losing information.
In [9), the authors provide generalization of the results in [2], by defining conditions under which continuously parameterized family of functions p(z; 0) that fully determines x up to equivalence, can be replaced by finite subset (zz; 0.). L..... m determined by random witness-vectors O,. This theorem is based on similar arguments as those used in [2], and on similar assumptions required for machinery from real algebraic geometry. Specifically, sets in [9] are assumed be semialgebraic, which means that they are finite unions of subsets of I that can be defined by polynomial equalities and inequalities. This class of sets includes, for example, finite unions of spheres, balls, and convex polyhedra. The functions in the theorem are assumed to be semialgebraic as well, which means that their graphs are semialgebraic sets. This class of functions includes polynomials, as well as rational functions and linear functions.
The main theorem in [9] can be essentially² formulated as
Theorem A.1. Let M. be semialgebraic set of dimension D, and let F : M x Ro + TE be semialgebraic function. Define the set
N f E F(; 0, 40 Po]
and assume that for all x E M. NN. we have that
dim E R Do F(2; = 0} - Do -
(12)
then for Lebesgue almost every (1), 0(D+1),
N = fa E Ml 0(z = 0, Vi -.... +
The notion of dimension used in condition (12) and throughout this section is the Hausdorff dimension, explained in Appendix A.4 below.
Theorem A.1 is similar to the simple version of the finite witness theorem (Theorem 3.4), with four notable differences: (1) The domain M. in Theorem 3.4 is a countable union of affine sets; this is
not, in general, a semialgebraic set, and thus does not qualify for the conditions of Theorem A. (2)
The function F in Theorem 3.4 analytic. Analytic functions are not necessarily semialgebraic. (3)
Theorem A. requires the extra condition (12), which does not appear in Theorem 3.4. This condition is not required in Theorem 3.4 because with analytic functions, it is always satisfied; however, it will be required in full version of the theorem, since it admits a more general class of functions. (4)
Theorem A. deals with sets of the form [x] F(z, 0) = O, vO) while Theorem 3.4 deals with sets of the form {xx 3) F(x, 0) F Fly, 0), V0). ).. This difference is not essential and can be handled by the change of variables z = (ar, 3) and F(x y, 0) F(x 0) Fly, 0).
"To obtain this theorem from the formulation [9], use the change of variables z (x, y) and F(z; 0) p( 0) - p 0). The formulation in [9] makes some additional requirements on E' which are relevant to the specific applications considered there, but going through the details of the proof shows that it is sufficient for proving Theorem A.l stated here.
13

---

The notion of dimension in (13) is the Hausdorff dimension (discussed below), and the term generic means that the set of (0(1).... ...., ( (P+1)) for which (14) fails is a subset of w whose Hausdorff dimension is strictly lower than dim (W)++). In particular, in the common case where W- = 13, with To address the first two differences, we shall generalize Theorem A.1 to support a large class of domains MI and functions F. The admissible domains shall include a vast class of sets, among which are countable unions of semialgebraic sets, as well as all open sets, and sets defined by analytie, rather than polynomial, equations. The admissible functions F shall include semialgebraic functions, analytic functions, and many other types of functions. To achieve this goal, we use results from the study of o-minimal structures (see below), which aim at finding families of sets that have the same tame properties semialgebraic sets.
good starting point to achieve this generalization is to consider the family of globally subanalytic sets (formally defined below). This family contains all semialgebraic sets and is an o-minimal system; consequently, is possible to generalize Theorem A. so that the domain M can include all globally subanalytic sets, and the function F could be any globally subanalytic function (meaning that the graph of is a globally subanalytic set). However, this still will not allow for general analytic F, nor for M. to include countable unions of affine sets.
To address this, we will show that an analogue to Theorem A.I holds even when considering countable unions of globally subanalytic sets. We call such sets o-subanalytic sets, To the best of our knowledge, such sets have not been studied date. The family of o-subanalytic sets is not an o-minimal structure, since it not closed under taking complements. However, it is closed under linear projections, countable unions, finite intersections and Cartesian products. Moreover, o-subanalytic sets are countable unions of C manifolds. We find that these properties are sufficient to generalize Theorem A.I and obtain finite witness theorem for the o-subanalytic category.
Clearly, the class of o-subanalytic sets is larger than the class of globally subanalytic sets. In particular, it includes countable unions of semialgebraic sets. This enables the domain M in the theorem statement to be a countable union of affine spaces, as in Theorem 3.4 from the main text. This also implies that any open set is o-subanalytic, since is a countable union of open balls which are semialgebraic sets.
As for the function F, our theorem admits all o-subanalytic functions: functions whose graph is o-subanalytic. This class includes all analytic functions, as well as all semialgebraic functions. Moreover, show below that it is closed under composition and other elementary operations.
We now state the full version of the finite witness theorem.
Theorem A.2 (Finite Witness Theorem, full version). Let M C R Rd be o-subanalytic sets of dimension D and De respectively. Let F: M W- + IR be a a-subanalytic function. Define the set
N = (= E M
F(z; 0) = 0, v0 E W).
Suppose that for all E W
dim(f E W F)z;0)= = 0} s Do - 1.
(13)
Then for generic (0(1), ,.... 0 ((D+1)) Wh+!
N (zEM F(z;0()) = 0, Vi = 1,,
(14)
Moreover, W is an open and connected subset of and F(z; 0) is analytic as a function of 0 for all fixed M, then condition (13) is not required, as is automatically satisfied.
is an open subset of R2 we have that the theorem holds for almost any respect to the Lebesgue measure on (D(D+))
We now begin to rigorously define the notions discussed in this section and then prove Theorem A.2. In Appendices A. 1 to A.4, we construct the theoretical framework step by step. Then, in Appendix A.5 we prove the theorem, and in Appendix A.6 we show that the simple version of the theorem (Theorem 3.4) follows from the full version. Finally, we present in Appendix A.6 several corollaries to the theorem.
14

---

A.1 Definitions and Background
A.1.1 Globally subanalytic sets: an o-minimal structure
We begin by defining analytic functions, subanalytic sets and functions, and various other related concepts that will be required for our discussion. These definitions are taken from [19] and [38]. Definition A.3 (Analytic function [19]). Let U C RRP be an open set. We say that f U - R is analytic if for all z E U, there exists an open ball V U centered at 2, and (aa) such that
f(y) = Σ
aa z)a
Ay E,
(15)
aEND
and the power series in (15) converges absolutely.
Our next goal is to define the family of globally subanalytic sets, which contains all semialgebraic sets: moreover, it an o-minimal structure, meaning that it shares the essential tame properties of semialgebraic sets. This requires some preliminary definitions:
Definition A.4 (Semianalytic sets [38]). A subset E C IR" is called semianalytic defined by finitely many real analytic equalities and inequalities. Namely, for each RR" there is neighborhood U of a, and real analytic functions fej, Pij on U, where i = I,.... and j 1 1...s,. 84 such that
is locally
Enu= U ()) > 0 and (ız(2) 0}. :=j==
(16)
Example A.5. As shown in Example 1.1.2 in [38], the graph of the analytic function f : (0, 1) - R
defined by f(x) sin (1x)) /x) is not semianalytic set. This is because there is no neighborhood of a = (0, 0) for which (16) holds. On the other hand, if C R" is closed ball and f B - R can be extended to an analytic function in an open containing B, then the graph of f (as a function defined on B) will be semianalytic.
The example above suggests that the class of semianalytic sets may be restrictive for our purposes. More importantly, linear projections of semianalytic sets may not be semianalytic [38], so the family of semianalytic sets does not form an o-minimal system. This can remedied by defining globally semianalytic sets (which don't 't form an o-minimal system) and then using these sets to define globally subanalytic sets (which do form an o-minimal system):
Definition A.6 (Globally semianalytic sets [38]). A subset Z C RD is globally semianalytic if V, (Z) a semianalytic subset of IR"", where Vn R" - 1) is the homeomorphism defined by
Vn (z = (z1,...,,x.)
21
Zn
2
VI+ 1
Globally semianalytic sets be thought of as semianalytic sets that remain semianalytic when 'compactified' by Vn. This is useful to rule out bad behaviour as = goes out to infinity. Important examples of globally semianalytic sets include all bounded semianalytic sets and all semialgebraic sets [38].
Globally semianalytic sets are still not closed under linear projection. Their projections called globally subanalytic sets:
Definition A.7 (Globally subanalytic sets [38]). A subset E C R" is globally subanalytic it can be presented as linear projection of a globally semianalytic set; more precisely, if there exists globally semianalytic set Z S TR++ such that F. (Z), with क Rn++p- - R being the projection operator that omits the last coordinates while leaving the remaining coordinates unchanged.
Globally semianalytic sets are by definition globally subanalytic. Globally subanalytic sets do form an o-minimal structure. In particular, they have the following properties:
Proposition A.8 (Properties of globally subanalytic sets [38]). Let A, B C TRD and C S R be globally subanalytic sets. Then:
1. DR \A is globally subanalytic.
15

---

2. AUB B is globally subanalytic.
3. An B is globally subanalytic.
4. A C is globally subanalytic.
5. x RP + Rh is a linear projection, then x ((A) is globally subanalytic.
6. A is a finite union of C manifolds.
The first property in Proposition A.8 is proven in Gabrielov's Complement Theorem; see Theorem 1.8.8 in [38]. The last property is a weaker version of Theorem 1.2.3 in [38]. The remaining properties are proved [38, Basic properties 1.1.8].
A.2 o-subanalytic sets
As mentioned above, the fact that globally subanalytic sets form o-minimal structure is already sufficient to prove a finite witness theorem for this class. However, this class is still too restrictive for our purposes, as it does not allow us support arbitrary analytic functions F, as the following example shows:
Example A.9. Analogously to semialgebraic functions, we say that a function is globally subanalytic if its graph is globally subanalytic. Consider the function sin(x: defined on the real line. Then by Example 1.1.7 in [38], this function is not globally subanalytic.
Fortunately, we find that finite witness theorem can be proven for larger class of sets: countable unions of globally subanalytic sets. We name such sets o-subanalytic sets. To the best of our knowledge, this class of sets has not been studied date'. The class of d-subanalytic sets is rather large: we will show below that it contains all open sets, while the classes discussed previously do not (see Example A.12 below). This is illustrated in the Venn diagram on the left-hand side of Figure 3. Correspondingly. the class of o-subanalytic functions is larger than the classes of functions considered previously, and in particular it contains any analytic function F defined on any open set. This is illustrated in the Venn diagram on the right-hand side of Figure 3, and will be discussed rigorously in Appendix A.3 below. Thus, moving to --subanalytic sets and functions is the crucial step that enables us to achieve our goal of proving finite witness theorem for analytic functions (though the theorem covers a much larger class).
We now define o-subanalytic sets and study their properties. Definition A.10 (a-subanalytic sets). We say that subset A C RPP is o-subanalytic is countable union of globally subanalytic subsets of D.
The class of o-subanalytic sets is rather large. For example, any open set in IR can be written as countable union of open balls. Since open balls are semialgebraic sets, follows that all open sets are o-subanalytic. Also, any semianalytic set is o-subanalytic, since semianalytic sets are countable union of bounded semianalytie sets, and these are globally subanalytic.
Properties of o-subanalytic sets
As the following proposition shows, o-subanalytic sets inherit most of the properties enjoyed by globally subanalytic sets, described in Proposition A.8.
Proposition A.11 (Properties of o-subanalytic sets). Assume that A, B C RR and C' C M are o-subanalytic sets, then
1. A U B is a-subanalytic. More generally, any countable union of o-subanalytic sets is o-subanalytic.
'Regarding the fifth property in Proposition A.8, note that it does not follow directly from property in [38] which only discusses special class of projections, but rather from property 4 in [38] which states that the image of globally subanalytic set under a globally subanalytic mapping is globally subanalytic. Any linear projection a semialgebraic mapping. hence globally subanalytic mapping.
"Model theorists and analytic geometers have researched other structures that are larger than o o-minimal structures and enjoy some of their tame properties; see, e.g., [39, 27].
16

---

semialgebraic functions
semialgebraic sets
analytic functions
open sets
globally subanalytic sets
globally subanalytic
functions
subanalytic sets
- subanalytic
functions
Figure 3: Left: The class of semialgebraic sets is contained in the class of globally subanalytic sets, which in turn is contained in the class of o-suaanllytic sets which focus in this paper. One of the advantages of this larger class that contains all open sets, whereas two smaller classes do not. Right: The classes of semialgebraic, globally subanalytic, and o-subanalytic functions are related in the same way. The class of o-subanalytic functions is the only one of the three that contains all analytic functions.
2. An is o-subanalytic.
3. A X C is o-subanalytic.
4. I RD + LR. is a linear projection, then x (AA) is co-subanalytic.o set.
5. A is countable union of C manifolds.
Proof. Let A, B C R be o-subanalytic sets, Then A = UnENA, and B = UmeN where each An and Bm globally subanalytic. We then have
1. A countable union of o-analytic sets, each of which being itself countable union of globally subanalytic set, is clearly countable union of globally subanalytic sets, and therefore is a o-subanalytic by definition.
2. We have that
AnB B (UnENAn) (UmeNBm) ena (An n Bm)
and An Bm is globally subanalytic as the intersection of globally subanalytic sets.
3. The set R can be presented as
A x RR (UZENA,) x R. = UnEN (A, R2"),
with Am being globally subanalytic. Since globally subanalytic sets are closed to Cartesian products, each An x M is globally subanalytic, and their countable union is o-subanalytic. Finally,
A = (A x R n (R C),
which is o-subanalytic by part 2.
4. Follows from globally subanalytic sets being closed to projections, since
(Unen A,) UnEN (I (An)))
5. A o-subanalytic set is countable union of globally subanalytic sets, each of which is finite union of C manifolds. Therefore, it is countable union of C manifolds.
17

---

In comparison to Proposition A.8, we see that we have lost two properties by moving from globally subanalytic sets countable unions thereof: Firstly, a o-subnnalytic set countable union of manifolds rather than finite one. Secondly, the complement of a o-subanalytic set may not be o-subanalytic, as our next example shows. As it turns out, the properties noted in Proposition A.11 are sufficient for our purposes.
Example A.12. The Cantor set is not o-subanalytic, since it has fractal Hausdorff dimension and thus is not countable union of manifolds. However, the complement of the Cantor set, which we denote by U, is an open set and hence is o-subanalytic. This shows that the class of o-subanalytic sets is not closed to taking complements, as well as countable intersections: this since the Cantor set is countable intersection of finite unions of intervals, which are o-subanalytic. The set U is also an example of an open set that not semialgebraic or globally subanalytic, since these classes of sets are closed to complements, and do not contain the Cantor set.
A.3 o-subanalytic functions
We now define the class of functions our theorem can admit as the function F: a-subanalytic functions.
Definition A.13 (d-subanalytic function). Let M C R. be a o-subanalytic set. We say that f M + R a o-subanalytic function if its graph a o-subanalytic subset DR+
If MMC C R is semialgebraic set and f M R is semialgebraic function, then the graph of is semialgebraic, and thus is o-subanalytic. Therefore, a semialgebraic function f defined on a semialgebraic domain M is o-subanalytic function. A similar result holds also for analytic functions defined on open sets, as shown in the following lemma:
Lemma A.14. U C R is open and f U + R is analytic, then f is o-subanalytic.
Proof. First recall that since is open, it is o-subanalytic set. Next, we can write as a countable union of closed balls B,, and then the graph of f can be written countable union of sets of the form
(ar, y) E B, x R' f()))
These subsets of U RL are compact and semianalytic, and hence they globally subanalytic.
Properties of o-subanalytic functions
The following proposition shows that the class of --ubanallytic functions is closed under composition and elementary arithmetic operations. In particular, this allows for functions that combine analytic and semialgebraic functions via compositions and elementary arithmetic operations.
Proposition A.15. Let A C RR and B R be o-subanalytic sets.
1. (Composition) if A + B and g B + IR are o-subanalytic then g f is a subanalytii function.
2. (Concatenation) f A + RT and g : A R" are a-subanalytic functions, then h: ::A > -A-R mm++ given by h (a:) = (f) (x)) is o-subanalytic function.
3. (Addition and multiplication) If f.g g A + RR are o-subanalytic functions. then f + g and I g are a-subanalytic functions.
Proof.
1. To prove that go f subaaaaayy, we need prove that its graph is s-sbbnnllytic set. Indeed, this graph is of the form
((x z) E AA g(f(x)) = =2},
which is the projection of the intersection
(a y, =) E Ax Re
f(x) = y) [(x, y, 2) Ax g(y) = =}
onto the (ar, 2) coordinates. The two sets in the intersection above are Cartesian products of the graph of (respectively g) with o-suannllytic set, and hence are o-subanalytic.
18

---

2. The graph of h is the intersection of the sets {(2, y, x) f(x) y) and {(x, y. y.z)
g(x))
z). Each of these two sets is a Cartesian product Euclidean space with the graph of
(7 T-subanaaytic function.
3. The functions f + y and f- can be presented the composition of the function R e a + (f(z). g(x)), which o-subanalltic, with the addition or multiplications functions. Thus, the claim follows.
A.4 Dimension
The proof of Theorem A.2 based on a cianeession-couniin argument. Accordingly, we will need an appropriate definition of dimension for o-subanalytie sets. It is convenient to work with the Hausdorff dimension, which defined for every subset of Euclidean space R.D, and coincides with the standard notions of dimension for vector spaces and manifolds. The definition of Hausdorff dimension can be found, e.g., in [14]. For our purposes, we will only need use some its properties, stated below. Proposition A.16 (Taken from [14]). The Hausdorff dimension has the following properties:
1. The Hausdorff dimension of k-dimensional C submanifold Rf. D is k.
2. If B1, B2.... are subsets of R then
dim (UnENBa) =max dinn (Bn). nER
3. For any RDD and Lipschitz manschitzfunction f - RC, dim (B) S dim
Recall that o-subanalytic Hausdorff dimension is just the maximal dimension of all manifolds A,. We shall now see that for such sets, the Hausdorff dimension has two nice properties that do not hold for general sets. These properties will be used in the proof of the finite witness theorem.
countable unions Un, of - manifolds. As saw, their
The first property is the dimension of Cartesian products. For two general sets A, B, it is not always true that dim(A A x B) = dim( A) + dim (see [14]). However, this does hold if A and B are countable unions of manifolds.
Lemma A.17. If A, B countable unions of sub-manifolds of R and R then
dim(A B) dim(A) dim(B).
Proof. By assumption A UnENAn and B Ume where Any Bm C manifolds. We have that
x B mNN An x Bm)
again countable union of the product manifolds A, x Bm which are known to be of dimension dim(An) + dim( B,,) (see e.g. [22]). It follows that the dimension of x B is equal to
max (dim(An) + dim (m)) = max dim(An) + max dim dim(Bm) = dim(A) + dim(B). (m,m)EN²
neN
mEN
The second nice property of the Hausdorff dimension for countable unions of manifolds, which does always hold for general sets, is dimension conservation, in the following sense.
Lemma A.18 (Dimension Conservation), Let S D1 be a countable union of t manifolds and f: Pr + DD T function. Then
dim(S) dim(f(S)) + max dim dim(J'(())) (t)))) rEf(S)
(17)
For failure of dimension conservation for general sets see, e.g., the discussion in [12].
19

---

A good intuition for the concept of dimension conservation comes from the linear case, in which f: RP. I. D2 linear transformation and S R is a linear subspace. In this case, the Rank-Nullity Theorem from elementary línear algebra states that
dim(5) (S)( + dim (f)((eerel(())ss))
(18)
dim(f(()) + (i)
The same statement also holds if we replace (0) by (t), with being any point in the image of f. Thus, for linear transformations, any loss of dimension when moving from a set S to its image, is accounted for by the dimension of the fibers above points in the image. The image conservation in Lemma A. is weaker since it is only an inequality, but it applies to the more general class of o-semianalytic functions.
Proof of Lemma 18. We know that S is a countable union of manifolds, and at least one of these, which we denote by S1, has the maximal dimension dim(S,) dim(S). This equality shall enable us to argue about (S) by arguing only about dim(S)).
Let be the maximal rank of the differential of Jis,- Fix some 81 E Si so that the differential of Jis, at 81 has rank r. The set of 8 S whose differential has rank is neighborhood V of $1, such that V n S1 is manifold of the same dimension restriction of f to n SJ has constant rank r. Consider the restriction of f to V n Sj, denoted by fivns, By the constant rank theorem [21], fivns, is projection, up to diffcomorphic change of coordinates. Since diffeomorphisms of manifolds preserve dimensions, and projections (like all linear transformations) satisfy dimension conservation in (18), this implies that locally have dimension conservation: for all t E f(V S1)
open, and so there St, and the
dim(V n {2) dim (f(V n S:)) + dim (N)V))))))
Therefore:
dim(S) = dim(S)) = dV
= dim (f(V + dim (f (()(())))) We f(V n Si)
< dim (J(S))
max dim ()-(())
tEf(VnS))
< ddm([((S) + max dim (J)))
tEf(8)
We conelude our discussion of the Hausdorff dimension with natural corollary which will be useful later on for our proof of Proposition 3.6.
Corollary A.19. Let M C RDD be a o-subanalyyic set, and let F M + IR o-ssuannulltcc Then the graph and image of F are o-subanalytic sets, and dim(F(M)) S dim(MV).
dim (graph(F))
dim(M
Proof. Note that by the definition of o-subanalytic functions, the graph of f' is o-subanalytic set. We begin by showing that it has the same dimension as M. Denote by x the projection from
graph(F) {(x, F(x)) E M}
onto the first coordinate. Firstly, since π is Lipschitz function, it cannot increase the Hausdorff dimension, so
dim (irapp(h((F) 2 dim( dim(r(graph(())) = dim(M).
In the other direction, note that for every (z, F(x)) E graph(F) we have that
π (I (æ, F (æ))) - (x) {x, F (x)))
set containing a single point, and thus has dimension zero Therefore, using Lemma A.18 we have that
(im(graph(F)) < dim dim(r((raph)) (F))) + dim(M),
and we have shown that Mi and the graph of have the same dimension. Finally, F(M)) is the projection of the graph of F onto the second coordinate and so it is a o-subanalytic set. Moreover, as projections cannot increase the Hausdorff dimension, we obtain that dim (M)) < dim(graph(()) = dim (M). which concludes the proof of the corollary.
20

---

A.5 Proof of the finite witness theorem
We are finally ready to prove the full version of the finite witness theorem.
Proof of Theorem A.2. Let m = D Let Fm M x Wm+1 + gm+1 given by
Fm (z, 0o, ,,.00...000 )m)) = (z:
(z; 0o) ....., (m)
Since Fm is concatenation of e-subanalytic functions (each such function is the composition of F with different linear projection), by Proposition A.15 it is also o-subanalytic. Therefore, the graph of F given by Am below, is o-subanalytic:
Am (zz Oo 0 ...... Om So. , Mxw xR
F(z; 0,) Sis Vi 0 0,..... m).
Next, intersect Am with the semialgebraic set defined by the equations so 0, 32
8m = obtain the o-subanalytic set
Am {(2, fo ...... Om, Foz; o.. 0) E M. x Wm++1 Rm+1 .....
F 0n) o and F(z;0.) = 0, Vi 1, ,
We then remove by projection the last coordinates and the Og coordinate, obtain the set
B,n {(z, ................................ (m)) E M x W" M \ W and F(2; 0,) 0, vi 1....... m}.
which is o-subanalytic well. Let and no denote the projections
n T=z, 0m.
To 01. 0m) (0 0m)
The set To (B..) S Wr is exactly the set of m-tuples (01.... 9m) that are not sufficient to determine
N. To prove the theorem, we thus need show that the dimension To (B is lower than dim (Wm)) mD. We do so by bounding the dimension of Bm.
Let 2p (Bm). The ग (z0) n Bm be presented as the Cartesian product
π (zu) n Bm = {zu} x O2 X Oz .... 20
(19)
m times
where
2z (0 E W
The set Oz, is also o-subanalytic: the graph of F
{(z,00 0, 8) E M
o-subanalytic by assumption; intersecting with the space 2p. 8 = 0, and projecting to the coordinate, yields the set Oz.- Since Oz, is o-subanalytic, it is countable union of manifolds. By the theorem assumption (13), the Hausdorff dimension of Oz satisfies
dim((z,) S Da
Therefore by Lemma A.17 and Equation (19),
dim ( "(zo) Bm) m dim(Ox)) mDD m.
(20)
So far, 2y is only assumed to be an arbitrary point in x (Bm). Now, fix 2n E т TBB,.) to maximizer of the left-hand side of Equation (20). By the dimension conservation Lemma A.18,
dim(Bm.) < dim(m(Bm.)) + max dim 1r-1(22) Bm)
2Ex(Bm)
dim(r(B,n) + dim (T- (zo) n B,))
(21)
IAG
dim(z(Bm)) + mD
D mDg m - mD -
21

---

where (a) holds by the choice of 2o. (b) is by Equation (20), and (c) holds since x (Bm) S M and dim (im(M) D. Since To Lipschitz, Equation (21) implies that
dim((T((B)) - dimm(m) S mD -
as required.
Now, suppose that W an open and connected subset of R We need to show that (13) holds for all M W. Fix M N and let f W + R be given by f(0) F(z; 0). Since & .N, there exists some 0 for which F(z; 0) * 0. Hence, f is an analytic function defined on an open connected domain, and is not identically zero. Therefore, its zero-set must be dimension-deficient
(see [28, Proposition 3]) and so we obtain (13).
This concludes the proof of the theorem.
A.6 Corollaries
In this subsection, present several corollaries to the finite witness theorem, and show that the simple version Theorem 3.4 follows from it as special case.
A useful application of the finite witness theorem, which often arises in invariant learning, is when wishes to assert that two points 2, y E M are indistinguishable by a parametric family of functions : 0); namely, that F(:; 0) F F3; 0) for all 0 e W. As the following corollary shows, this can be asserted almost surely by testing whether F(x; 0) = Fly: 0) on 2 dim (M) + random Os.
Corollary A.20 (Separation by Finite Witnesses). Let M S IP, W R2 be o-subanalytic sets of dimension D and Dg respectively. Let F M x W - IR be o ousuunallytic function. Define the set
N (xx,)) E M MI F(x;; 0)
Fl: 0), v0 W].
Suppose that for all (x, y) E M x M W
dim W F(x;0)= Fly:0) s De - 1.
(22)
Then for generic (0(1), ................................ 0(2D41)) E WD+1
= (xx y) E M x M
F(x;; 0 Fly (10), Vi -.... ......D.. 13.
(23)
Moreover, W is an open and connected subset of R2, , and F(:; 0) is analytic as a function of 0 for all fixed M. then condition (22) is not required, it automatically satisfied.
Proof. Set Ml M M, and define G M W + R by
G ((xz, y) 0) = F(x; 0) - F F(:: 0).
Then M. is a a-subanalytic set of dimension dim(M)) = 2D, and G is a o-subanalytic function. Moreover, if F(x: 0) is analytic function of 0 for any fixed M, then the function 0 G ((x, y): ;0) is analytic for any fixed (x, M. The result follows from applying Theorem A.2 to G.
Using Corollary A.20, we can now easily prove Theorem 3.4 and Proposition 3,6 from the main text, which we restate here for convenience:
Theorem 3.4. (Finite Wimess Theorem, simple version) Let ML C R. be a countable union of affine sets, each of which is of dimension S D. Let W C RD be open and connected. Let (æ; 0) ML x W + IR be an analytic function. Then for almost any (0(1).... 012D+1)) E w22++ the following set equality holds:
((x, y) E M x
M
F (z; 0) = (); VO E W)
{(x, y) E M x
F
1.....2. 2D + 1}. x; ( = (y: vi= 1,...
Proof of Theorem 3.4. Since affine sets semialgebraic, countable unions of affine sets are subanalytic. Therefore, Theorem 3.4 follows from Corollary A.20. Note that by Corollary A.20, the claim holds for all (0(1) (o(1)...., ..., 0(2D+1)) except for possibly a dimensionndeffcient subset of DDD+ which is slightly stronger than the 'for almost any" statement in the theorem.
22

---

We now prove Proposition 3.6 from the main text.
Proposition 3.6. Let a R + R be an analytic non-polynomial function. Let nt d E N and set m 2n(d 1) 1. Let J Rd RR- be injective function that is composition of PwL functions. Then for Lebesgue almost any A E R IRm,, the function (a) + b) is moment injective on M Mgnn (RR).
functions and analytic,unctiinss
Proof. Let (R.) C RL be the image of Since is injective, it naturally induces injective Mgn()), defined by
pushforward map measures fa MMn
(RR) Σ widx. Σ (an)(ans M))
Thus, remains to show that for Lebesgue almost any A E R b E R",, the function g = a (Ay b) is moment-injective M)). To prove this, first step bound the dimension of y. By Corollary A.19, since f is o-subanalytic function, y is a o-subanalytic set, and
dim ()) I dim [R.) = d.
Let M be the space of measure parameters over with n points:
M = ((w, Y) RD y")
and let W be the space of parameters
W = (aa E Rd R..
Then M and W are o-subanalytic sets, dim (M) I n(d + 1) and thus = 2n(d + 1) + 1 is larger or equal to 2 dim (M) We can now proceed as in the proof of Theorem 3.3:
Define F: x W + IR by
n
F(w, Y: Y:
Σ woo y: + b).
The set W open and connected, and F(w, a; is analytic function of (a, for any fixed (w, Y) E M. Therefore, by Corollary A.20, for almost any choice of (a;, b;) E W, the following equality holds:
[(w, Y), (w', Y')) e M M
F (w, Y; b) (w', Y': a, b), V (a, b) W] F (w, Y; as, bi) F (wo, Y a, bi), Vi 1,...,m) m).
(24)
((ww, Y), (w), Y")) M x M
Let A E Ru with rows ai...., ams and b (b) (bi..... bm). Suppose that A,b indeed satisfy (24). Then, using the same argument as in the proof of Theorem 3.3, we see that the function is moment-injective Mgn (D)). This concludes the proof.
23

---

B Moment Injectivity of piecewise-linear networks
In this appendix, we describe some additional results on moment injectivity of PwL networks. Our results are summarized as follows:
1. PwL. networks are not moment injective on MMn (E), when E is an infinite set.
2. PwL networks are not moment injective on Sgn(R) when = R (shown in the main text)
or f = =d
3. There exist irregular, countable infinite Σ, for which PwL networks are moment injective on (g)(E) (but not on Mgn (E) as mentioned above).
4. For finite Σ. PwL networks can be monent-injective on both Mgn(E) and Sgn (E). The number of neurons needed for injectivity depends and the size of Σ.
We now prove these results. We begin with discussing infinite alphabets.
B.1 Failure of moment-injectivity for piecewise-linean functions with infinite alphabets
We begin by showing that PwL moment injectivity is never possible spaces of measures, when the alphabet is infinite:
Proposition B.1. For all natural m, and n Z 2)/2, and S H that is not finite, if vb Rd Rm is piecewise linear, then is not moment injective on Mgn
Proof. The proof is based on the fact that if -
w;da, is supported on a single linear region of tb then, denoting the parameters of the affine function corresponding to the region T. by A E Rdxm b IR,,, we have that
Σ (ab((x))) = A Σ w
+ b
Σ
Wi
(25)
Thus it is sufficient to find two distinct measures in Men (Ω) which are supported in the same linear region, and for which the two sums Σ w, and Σi=1 w give the same value. Since has finite number of linear regions while Q is infinite, there is some linear region which contains an infinite number of points f2 Thus, we can choose d 2 distinct points 21,.... 2d+2 in this region. Since all these points are in Rd they must be affinely dependent, which means there exist weights W1....: Wd-2, not all of which are zero, such that
d+2 Σ wyz = and Σ
d+22
w/ =
j=1
We can now define k = [(d + 2)/21, and set Σ wrOm, and μ¹ = Ej=bt1 (- (-w;)
According to (25), integration of ab over and over μ1' gives the same value, while μ. + ju, and so 1b not moment injective.
If change the setup of Proposition B.1 and consider spaces of multisets rather than spaces of measures, we get a somewhat more complicate picture: the following, we give an example of irregular, infinite, countable alphabet Σa, for which even the simple identity function x is moment injective. We shall then show that for the more natural alphabet moment injectivity is not possible on Sz,, (E). We define Σ, fa, a² ......). where E R is transcendemtal number, which means that it is not the root of any polynomial with rational coefficients. Examples of such numbers include and e. In this case, we that the integral Jx xdu(()) over any non-zero measure μ Σi w:dai where wy are rational numbers, will not be zero. This implies that the identity function is moment injective on Szn Szn,2))) ) for any natural n. Note also that if n is fixed, can just take positive, we have that the simple piecewise linear MLP ReLU(x) is moment injective on Szn (Ea) as well, as ReLU(z) z on the domain E..
Zd PwL
(n + +)- as suggested in [44]. Finally, note that by choosing a be
We now consider the case Σ = zd:
24

---

Proposition B.2. Let d, 2 2 be natural numbers and E = Zd. If 2 R - R is piecewise linear, then it not moment injective on S (z))
Proof. Let first consider the case where d = 1. Since the number of linear regions is finite, there exists a linear region L that contains an infinite number of natural numbers. From the convexity of L, it follows that L contains in Proposition 4.1, we conclude that the moments of the multisets 2N,, 2N I and (N, 3N B are the same, and thus up is not moment injective. The same argument be applied in the case d > 1 using the identification of with the elements in Zd whose first - 1 coordinates are zero.
interval of the form [NV oo) where N N. Using the same argument as
B.2 Piecewise linear network moment injectivity for sets with finite alphabets
We now consider moment injectivity of PwL networks when the alphabet is finite. Recall that when the activations are analytic, moment injectivity is achievable on Sgn (E) with single output neuron. For PwL. activations, moment injectivity is also possible, but the required number of neurons depends on the cardinality of the alphabet.
Definition B.3. For given W, L, E N. we denote by (W, L, d) the maximal number of linear regions that a ReLU network f Rdd TR with maximal width W and depth I. can have.
Proposition B.4. If n., W, L, are natural numbers with n 2 (d+ + 2)/2. and Σ C R2 is a finite alphabet satisfying [E] M(W, L,d) (d + 1). then any ReLU neural network db Rdd + Rmm of depth L and maximal width W will not be injective on Mcn (E). Moreover, for large enough n, assuming that all points in E have rational coordinates, such ReLU networks will also not be moment injective on (Zn(
Proof. Since MW, L. d-1+ by the pigeonhole principle, we know that there must exist least one linear region that contains least d 2 points in N. Denote these points æ1, 22, ... Td+22 These points are affinely dependent, and so there exist weights wi,.... Wd-2, not all of which are zero, such that
d+2
d+2
Σ w.y, = and Σ
w =0
(26)
We can now define k = [(d + 2)/27, and set μ
E wrdr, and μ
Ej=k+1 (-w, )xz,
d+2
According to (25), integration of sa over μ and over p' gives the same value, while p A nl, and r/ is not moment injective on MMn
We now show that moment injectivity fails also Sçn (E) when n is large enough, under the assumption that Σ c Qdd Under this assumption, the above-mentioned points 11 B2..... F.442 are affinely dependent over Q. and there exist rational weights Wi,.... Wa42 for which (26) holds.
Now we can multiply (26) by an appropriate integer, so that the w,s are all integers. Using these new weights, suppose that n 2 Σ, wwa). Let μ = E.a. 20 wxds, and μ Eon,,oo(wwwj w., Then jr and jL are two distinct measures that assign the same moment to f- Since the weights of μ and μ are all natural numbers, these measures correspond multisets, where the weights denote the number of repetitions of each element.
Li
Number of linear regions Proposition B.4 gives a lower bound on the number of linear regions needed for moment injectivity. The relationship between a neural network's 's size and the number of its linear regions well studied [29, 35]. In particular, is known that the number of linear regions can be exponentially larger than the number of the parameters. As shown in ([1), Theorem D.6), the maximal number of linear regions M (W, L, d) of a ReLU network with maximal width W, depth L, and input dimension d, is bounded from above by CWd-I, where > 0 a constant. Joining this together with Proposition B.4, we see that we cannot have moment injectivity if
CWd (d + 1) < [Σ|
(27)
This implies that the number of neurons required for injectivity is at least logarithmic in the cardinality of the alphabet. Although this only a lower bound, we believe that this bound can be achieved using the techniques developed in [1].
25

---

We conclude this discussion by providing upper bound for the number of linear regions needed in the simple case that Σ {e < <2 < Es} is a subset R, and the depth one. In this case, our bound (27) states that one cannot attain moment injectivity on (ga(F) when 2C W < <. In the other direction, we show that moment injectivity can obtained when W =.
Proposition B.5. Let E (41 <2 ... Es), and let n S be some natural number: Then there exists shallow ReLU network of width W = S that is moment injective on Mgn(E)
Proof. Choose some ........ tg such that
t < < <2 <ts < ls.
Consider the shallow ReLU network
ReLU(x 11) ReLU - 12)
x + (x))=
ReL.U(Z - -ts)
Eim Suppose that μ Ein wgōr, and pl -'=Lim wide, are two measures such that
f (w)o)d(()== = f (bll)))) (b(r)d)
The equality of the last coordinate implies
w'g(es ts) / ReLU(x= MeLL(c=ttsddy''e
- ts)du(x) ts)d4' = ts)d((=)))dd(()) =usl)))))ssssss> ts)
and Ws w's. Next, consider the equality of the (S 1)th coordinate and show that this implies that u = w---- Continuing with this argument recursively, we see that the measures must agree.
26

---

C Optimal embedding dimension of moment-injective functions
In Appendix C.1, we prove the lower bounds on the embedding dimensions showed in Table I for (M (IR") and M2n(2.) for countable Σ. The remaining lower bounds in the table are equal to one, and thus do not require proof. For (Re), these bounds are already known [16, 6, 5,42], but here we present slightly different proof, which also applies spaces of measures that were not considered previously. As a rule, for all the spaces of measures/multiset considered, the lower bound equals to the intrinsic dimension of the space, i.c., the number of continuous parameters required to describe it. For example, Sgn (TR.) is parameterized by continuous vectors in IR with a total dimension of d, and by discrete weight vector that has no influence on the dimension, and thus the lower bound in this case is n d.
An interesting question that remains open is whether the gap between the embedding dimension achieved here with shallow neural networks, and the best lower bound, can be closed completely. For multisets with features in [0, 1]. [42] showed that the lower bound of n moments can be attained using n polynomial functions. In Appendix C.2. we show that for spaces of measures with features in F. the lower bound 2n in Table can be attained by 2n functions that form T-system (see discussion
below). Examples of T-systems include the functions 2, x² .... 2n as well as 2n univariate sigmoid neural networks with distinct parameters. Thus, for d 1, we know that the lower bounds on the embedding dimension are optimal. For d > 1, it seems that this question is still open.
C.1
Lower bounds
Our lower bounds are based the following intuitive fact, which is simple corollary to Brouwer's invariance of domain theorem:
Proposition C.1. U C DR. an open set and F R& continuous and injective, then M 2 D.
Proof. Suppose by contradiction that M < D. and let 0 E D- be a vector of all zeros. Then the function F(x) = (0, F())) is a continuous injective function of U S R D into R and by the invariance of domain theorem ([13), Theorem 2B.3) F(U) should be open. This leads to a contradiction, since arbitrarily small perturbations of the first coordinate of point (0, F(x)) in the image of / will longer be in the image.
Based on this proposition, we can prove the lower bounds in Table 1. The following lower bound holds for any alphabet Σ.
Theorem C.2. Let 2 Rd with [ Men (E). Then m 2 n.
Suppose that f E - Rm is moment injective
Proof. Fix n distinct points ......, Tn in E. The function
(Wi...., Wn) +
woon.
maps RR" injectively into the space of measures Msn (2). Since f moment injective, it follows that the continuous (in fact, linear) function
R
(WI, W.))
Σ wi (x; T
injective. Thus, by Proposition C.I we have that 2
When the alphabet is uncountable, we can obtain stronger lower bounds. We now show two lower bounds the embedding dimension required for moment injectivity of continuous function f with the alphabet Ω = d
Theorem C.3. Let f T T be a continuous function. Then
1. If f is moment injective on Mcn(Rd) then 2 n(d + 1).
27

---

2. If f is moment injective on then m 2 nd.
Proof. Choose n distinct points Dı,.... Yn E IR and let >> 0 be small enough so that the distance between any two distinct points ys yj larger than 2r. Then the function
(wi,... ....... Wn. Di. ................................ Fnn
wrom.
maps the open set
{(w1.... Wny T......, xn)) wi F 0, |c; Yal < r, I.....
injectively into Man (R Therefore, the map
Bu+dn (wi,.... Wn: I1...... F.n + Σ wxr((;)) m
injective, and since it also continuous, Proposition C.1 implies that m 2 n(d + 1).
For the second part of the theorem, where is moment injective on (RR(), we can similar argument, the only difference being that we fix w; = Namely, the map
Rnd (I1...., Inn + Σ f(x,) E R
im1
is continuous and injective the open set of (T1..... xn) with x;; Yel < r for all i, and therefore
by Proposition C.1 m 2 nd.
C.2 T-Systems
We now show how to achieve moment injectivity MMs.(R) (R) with optimal embedding dimension. Recall from Table that for this space, our lower bound on the embedding dimension of continuous cooment-injective functions is 2n, whereas the embedding dimension of the MLPs constructed using our technique is 4n + 1. We shall now show that this gap can be closed, using the moments of 2n functions that form T-system, which now define.
Definition C.4 ([20)). Let Ω C R. We say that the k functions 7; : Ω + I, i = 1,... k. form a T-system on Ω if for all pairwise-distinet æ .. Ω the square matrix
Mr = [T(3)))sssss E R
(28)
is invertible.
An example of T-system on Ω R is the standard monomial basis (()) x=-1,²__ 1, k.
With this choice, (28) is the Vandermonde matrix, which invertible, and hence the monomial basis T-system.
We know that the moments of the first n elements of the standard monomial basis are injective on Sgn (B.. The following simple proposition shows that injectivity on all of Mcn (R) can be achieved, at the cost of increasing the number moments to 2n. Moreover, this true for all T-systems.
Proposition C.5 (Trivial, based on [20]). If (Ti...., T2n) is a T-system on Ω C R. then the induced moment function
+(p) = ( (+)du((()) (2n(())u(x))
is injective Mg)(A).
Proof. Let y, pl E Mcn(2) such that +(u) = ((²²). Then T(u - nz) = O, where μ - μ denotes the difference measure. Since jt' is supported on most 2n points, can write
2n
11 - p
W wrsn.
28

---

where the points 2; are pairwise distinct, and some of the wi may be zero. Our goal is to show that the vector
v (W1, W2n)
all zero. Indeed, the fact that F(u n²) = 0 implies that M w = 0. And since by assumption M, is full rank, have that 0.
Example C.6 (Sigmoid T-systems). We've ve seen that the standard monomial basis forms a T-system. Another well-known example [20] is the family of functions
1
(x)
i= I....,k.
aq
If the numbers ,1,..., O& are pairwise distinct, then T (Th..., Th) form a T-system on Ω (a1,...,aa))
We can use these example to obtain an alternative T-system based on the sigmoid activation o(x)
(1 + e =-"= Firstly, using the injectivity of the exponent function, can deduce from the fact that T a T-system, that for any distinct b,,...,u by the functions
(x) c +
i= 1= k
form a T-system on R. It follows that the functions
I+e- - ( chi f i=
ax + b,)
form T-system well. In particular, for all pairwise-distinet b1,..., ban the function
x x a-o orx bi), == 1, 1,.... 2n
is moment injective on (K.(
Unfortunately, these results cannot be extended to Mg.(R with d > 1, as it is known that T-systems can only be defined on subsets R or S' [20].
29

---

D Proofs
In this section, provide the proofs omitted from the main text, except for the proofs of Theorem 3.4 and Proposition 3.6, which appear in Appendix A.6.
D.1 Proofs for Section
Proposition 3.2. Lel R
+ R be continuous function that is not polynomial; then or is
discriminatory.
Proof. Let a be as in the statement of the proposition, and let be signed Borel measure that is finite and is supported on compact set K - R. Furthermore, assume that fg. a aa x b)) 0.
for all a and b. We need to prove that
Note that by the linearity of p. have that J fdu for every I in the space spanned by functions of the form a (a x + b). Additionally, since functions in this space can approximate any continuous function on K uniformly ([32]). Propositions 3.3 and 3.8), and μ compactly supported, we have that f fdu = O for every continuous function. Finally, by the Riesz representation theorem ([36], Theorem 6.19) we know that signed (and more generally complex) measure on K defined uniquely by the integrals of continuous functions and thus μ = 0 as required.
Proposition 3.5. Let n, d E N and set m = 2n(d + 1) + 1. Let W- = (y. M Rd x Rt. for Lebesgue almost any (Y:, 0) T the function
||
2ı 112
|| ym 112)
f(x)
exp
exp
of
o
is moment injective on Mgg (IR".
Proof. The proof follows the proof of Theorem 3.3 with some modifications. Set m 2n(d + 1)+1 +1 measure in Mın (IR)) ) is determined (albeit not uniquely) by a matrix X (æ1, Fn.) E Rdxx
that represents points in R., and a weight vector w E=. Let MI denote the space of pairs of measure parameters
M {w,, w', X'X'
R
R
Rdxa x Rdxn],
and let
F(w, w/, X' Σ
we cxp
2| (-a
y1l3)
Σ w exp (-o 2112 y1 (29)
d=1
We prove the proposition by showing that for Lebesgue almost every y1,-.., Um and 01.... om.
((w, w', X, X') E M
Σ wrdm: = Σ w/oa
(ww, w', X, X') E M
F (w, w' X, X': y, 0) =0, Vy E R E R+}
[(w, w', X, X') E M. F (w, w', X, X': y: 0;) 0, Vi = 1....,m m}
As in the proof of Theorem 3.3, equality (**) follows from the finite witness theorem. The equality (*) follows the one hand from the fact that whenever the measures defined by (w. X) and (w', X') are the same, necessarily all integrals of functions against these measures are the same, and so F (w, w', X, X';y,000 σ) = 0 for all E d E R..
On the other hand, if the measure μ defined by (w, X) and the measure μí defined by (w', X'), not the same, then it is sufficient show that for some choice of E Rd. I4 have F(w, w' X'X'
y o) # 0. To see this is indeed the case, choose some yo E Ød which the non-zen matrix μ yl' assigns a non-zero weight wp- Then
lim F(w, w' X X': σ) wo 0. 000000
and for small enough we have that F(w, w' X,X'; yo: σ) which concludes the proof.
30

---

D.2 Proofs for Section
Proposition 5.1. Let n 2 2, d, i E N, and f I2 mR differentiable at some at E IRd. Then the induced moment function f (gn(Rd) + IR defined in (1) is not bi-Lipschitz.
Proof. We choose some arbitrary d E Rd with unit norm, and focus on multisets of two elements IR of the form S. (a + ed, 2o -d.. We note that the Wasserstein distance (2(S,, So) v /2e. Thus, it sufficient to show that
lim [[ - f(8o)) f(so)l
0,
(30)
|e|
for this implies that there is no positive e which (8) holds. Indeed, denoting the differential of at 2o by J. we have
[If( f(So)]
[1 + ed) + f(00 ed) - 2f((()))
[c]
[c]
((0 + ed) - ((x0)) - eJ + [10 - -e) - f(200) + cJd]
le|
[f ed) - f(xo) - cJdl
|1 - ed) -(x0) - (-eJd)ll =0 0,
+
|e|
[c]
where the convergence to zero of the last expression follows from the definition of differentiability at a point.
D.3 Proofs for Section
now prove Corollary 6.1:
Corollary 6.1. Let n., E N and set m 2nd + 1. Let o IR + R be an analytic non-polynomial function. Let K C Id be compuct set. Then there exist A E Rmxd b E I& such that for any
continuous permulation-invariine f K > IR, there exists a continuous F Rm - such that
f(x) = F Σ a (Ax, +b) 1 VX = _..
2x) (EEE KT.
Proof. By Proposition 1.3 in [9], is sufficient show that there exists A R.mxd b Rd such that the permutation invariant function
Fnn
+ Σ o (Ax; + b)
(31)
j=1
orbit separating. This means that any two element in K that are not related by a permutation will be separated by the function in (31). Any pair of elements not related by permutation correspond to two distinct multisets Sgn (gn( with exactly n points. By Theorem 3.3, for almost every choice of A, b the function (31) will be injective on Sgn (Rd), and thus for such choice this function indeed invariant and orbit separating.
We now prove Corollary 6.2:
Corollary 6.2. Let n. d E N and set 2n(d + 1) 1. Let 0 IR + TR be analytic and non- polynomial. Let K C pd be compact. Then there exist A E mmd E Rm such that for any continuous (in the 2- Wasserstein sense) f (K) E, there exists a continuous F mm R such that
f(w) = F (J1 oAAx + b)du(z))
31

---

Proof. Our first step is to show that (K) is compact with respect to the Wasserstein metric.
Since Pgn (K) is the image the compact set
Q :- () K"
Σ wi 1 and wi 2 0,, 1, ,,.,, n}
under the function
(w, x) 7 Σ Wrdm..
is sufficient show that this function is continuous, the image of a compact under continuous map is compact. Thus, given sequence of (w((), (k)) which converges to some
(w, X), we need to show that in Wasserstein space, the measures f4u: == Ei=1 wi (k) nn converge
to the measure μ := Ei=1 w,62. Since the Wasserstein distance metrizes the weak topology on measures ([40), Theorem 6.9), is sufficient to see that the integral of every continuous K R against the sequence of measures converge to the limit measure. Indeed:
J K s(z)du()) (x)
Σ wis((x)) / s(z)du(x))
(z)
Σ m s(x (K)
Thus we have shown that Ps (K) is compact. Next, by Theorem 3.3, for almost every choice of A, b the function
((p) = mEK
(AA + b)dp(a))
injective on MMn (IR), and so in particular on the compact subset (K). As g also continuous, and a continuous injective function defined on a compact set is homeomorphism, it follows that q-' gP (K)) - Pm (K) is continuous. We then have that f = (f a q q. We can then use Tietze's 's extension theorem to extend f o from its compact domain to continuous function F defined all of R and we then obtain
F q required.
Theorem 6.3. Let n, d, T E N and let Σ C R2 be countable. Let m 2 1 be any integer. Let
R be an analytic non-polynomial function. Then for Lebesgue almost any choice of A b(t) and ((()) the MPNN defined in (10) and (11) assigns different features to any pair of graphs G1, G2 E (E) that can be separated by T iterations of 1-WL.
Proof. The message passing iterations discussed in the theorem define new node features ( from the previous node features 1 (t-1)
h (2)
Σ o (A4
(1 + 1lll h((-1)) + 6(())
wEN(v)
This can be rewritten
m (t) 17 (1(-111)) (t-1)
((t)) = (() ((m (t) ((())))) = Σ a (A + +b()) ,t= ,I==....,;
.EN(K)
The final 'readout" step creates global graph features from the node features of the last iteration T via
ha = ((+1) ((h!7) I DEVB) = Σ (A(T+U +b(T+1)
VEV
is known [44] that every pair of graphs G, & E (E)(E) which are not be separated by T iterations of the WL test, will not be separated by message passing procedure, regardless of the choice of the parameters
= (A'),
A (+1)) (()) ...... ......((+1)) ((++)) (1)) (T.,)))))
32

---

We need to prove the opposite direction.
Since the collection of all graph-pairs from gga is countable, it is sufficient to show that any fixed pair of graphs G, G E (gn(E) that can be separated by iterations of the WL test, can be separated by almost every choice of parameters.
Let us fix such a pair G, G E Gzn (E) which can be separated by T iterations of WL. Note that the final features hg (c) and && hgg obtained from the message passing procedures are an analytic function of the parameters 0, and therefore to show separation for almost every 0 it is sufficient show existence of 0 for which hc(00) (g).
To show that a single such I exists, we choose the parameters of the functions recursively in the order (771), A b()),, (1722, ( b(2)) ).... in which they are applied in the message passing procedure. ..... When choosing the parameters (1)(*) , (t),, ((t) corressoonnn to the tth step, it is sufficient to show that, if at the previous (t 1) timestamp, for two different nodes U, w we had
(t-1) + (t-11) or [h! u E ((v) + (h a "EN(w)) h
(32)
then h and h will not be the same. Here and nodes in either G or G.
Our first goal is to choose (t) so that, for all given nodes U, u in or & such that (32) is satisfied, we have
mm 0 u E (()) + m x E [(w)]
(33)
To choose (9) in this way, note that since all previous parameters since we are only interested in a single pair of graphs, there is only a finite number of features
already determined, and
(h. ( is node in G or G}
which we are interested in. Since for fixed vectors I1, Z2, V1. V2 of the same dimension with 21 f 22, there can at most a single 1) satisfying the equation
mal yı 1j02 y/-
(34)
we conclude that all but finite number of satisfy
nh(!-1) ht F (t h (1-1) Ah (t-)) h (1-1) h (t-1), . (t-1) E ((--1) such that (t-1) * (t-1)
We choose (7()) which satisfies the inequality above. This implies that if the left-hand side in (32) indeed an inequality hn(-1) # (e then m!!) * mn(1 for all (u, E &V(v) x A(w),, which in turn implies the inequality of multisets obtained from w and ((33). On the other hand, if the
left-hand side in (32) an equality (t11 ((-1) and the multisets in the right-hand side of (32) are distinct, then clearly the multisets in (33) are distinct too. Thus, we have proved that we can choose (7(*) so that (32) implies (33).
remains to show that we can choose the parameters of f(t) so that, if (33) holds for some nodes
w of G or G, then the features h and (!) obtained from applying f()) to the multisets in (33) will be distinct. Indeed, since we are only requiring f(() to be injective on a finite collection of finite
sets, we have that all these multisets are contained in S.,,, (E) for some finite E, and therefore by
Theorem 3.3 there a choice parameters (A (t), ((0) which is injective on Szn (E), even when m 1. Thus, we obtained a recursive procedure for choosing the parameters such that G and & will be separated, which concludes our proof.
33

---

E Numerical Experiments: Additional Details
E.1 Empirical injectivity and Bi-Lipschitzness
To generate the results shown in Figure 2 (and Figure 4 below), we ran multiple independent test instances in which we generated two random matrices X1, X2 _x representing two sets of vectors in IR.. With exact details appearing below, X2 were generated such that: (1) Each entry of X1 and X2 has expectation zero and a standard deviation (STD) of 1; (2) X1 and X₂ differ in exactly n&a randomly chosen columns, with the parameter n. chosen uniformly at random from ....... n:: (3) each entry of the R& nonzero columns of AX X₂ X1 has expectation zero and STD=p, with the parameter itself drawn uniformly (once per test instance) from [pmin= : Pmax] We used Pamin = 0.02, Pmax = 1. In other words, the relative difference p between non-identical columns of X1 and X2 is chosen at each instance randomly between 2% and 100%. The motivation for this construction was to test various types and magnitudes of differences between multisets.
We then randomly generated A E I2 fnd and b E Rax1 from which we took subblocks to be used as parameters for the function (æ; A, b) of Equation (3): for various values of E [m]] we took Am bn to be the top m rows of A and b respectively, and used them to construct the embedding (X; Am, bm, o): Rdxx + IR:
"1
i (X; Am: Dm, 0) =E (Am + bm),
with 2; denoting the columns of X. The entries of A and were drawn from Gaussian distributions chosen such that for each ag of A and corresponding entry by of b, and each column v; of X1 or X2, the input to the activation 0, ag 24 + by. has expectation zero and STD=1; specifically,
E [ak- 2. E [bb]
and STD (ax sr.] STD [b&]
-2-
For various activation functions a, calculated the ratio
11 [X];:; Ane bm: o) - (X2; Ams bm, o]122
r (X1, X2)
W2 (X1
with W2 (.,-) being the 2- 2-Wasserttein distance. We used Sinkhorn approximation of W2 (+,)). calculated by the GeomLoss Python library [11]. Finally, for each activation a and embedding dimension m, we took and C to be the minimum and maximum of (X1, X2) respectively over all test instances, and recorded the ratio c/C. In each experimental setting, we ran between 500,000 and 2 million independent instances, depending on the values of d and n. The results appear in Figure 4. It can be seen that similar behaviour is exhibited across different values of d and n. In particular, all PwL activations have c/C 0 at low m and all analytic activations have positive c/C all settings tested.
Probabilistic distributions of data At each instance, as mentioned above, we first chose n& Uniform (I,.... n1]] and p ~ Uniform [Pminn P.aa]] We then randomly chose nı columns labelled
by J, at which XY, X2 should differ. Let I = [n] J. Denote by X A] the subblock of the matrix X with columns indexed by A. The entries of X1[:. I] = X21:, I were drawn i.i.d. from Normal (0, 1). For [1 J] and X2[:, .7. we generated two random matrices U, E RRdxaa, each of whose entries are i.i.d. Gaussian with expectation O, STD=STD-
T2 (pias + PraxxPri + priin) and STD=1 for
U.V respectively. We then
=U
X2lt,J]= = PVV.
Lastly, we generated the entries of À and 6 from Normal 00, (28 and Normal (0, 1/2 respectively,
We now show that: (i) each entry of i: J] and [ has expectation zero and STD=1, (ii) given p. each entry of A || expectation zero and STD=1. Let 21, Z2 be two corresponding entries of X1 J], X2(;, J], and let
[.. J] has expectation and STD=p, and (iii) All inputs the activation have
u, be their corresponding entries of U, V. Then
I22 + pv.
34

---

πt = 10
100
11
1000
10
10
10
10-3
10
10
10
d
10-5
10
10-7
10
10-8
m1
111.1
111.1
10
100
1000
100
1000
10
100
1000
mm
Cos
= 100
TanH
10
10
Sigmoid
P
10-9
10-0
HardTanH
ReLU
10 100
1000
10
100
1000
772
The empirical ratio e/C of Equation (8) as a function of the embedding dimension m. The results for different sizes of vector-sets n and ambient dimension are shown. For low m, the piecewise-lines ReLU and HardTanH have c/C' exactly zero. See Appendix E. for full description of the experimental setting.
Figure 4: Empirical injectivit and bi-Lipschitzness
We now calculate the expectation and variance of 21, T2. Since U, V and p are independent, we have that
Pmin + Pmax 0 O,
E [m]]] E [u pu] E. [x]]
1 E
2
and by similar reasoning, IE' [202] = O. The variance of æ1 is given by:
Var [21] = Var [u po Var [u] + (Var [p] + Eipl²) (Var [u] + [E()
E [p] E(]
Var [u] + 1 (Pmax Punin)
(Puax + Punin) )2
-1+0)-E(pT]
12
4
Var [w] + T2 (prnxx + PmaxxPmin + Paiin)
1
-11
1 (p + PmaxxPmin + Puinn) + 12 (p + PmaaxPmin Pinin) = 1.
1
12
By a similar argument, Var [wa] = Thus, (i) holds. Let Ax = 82 - x1 = pv. Then
E A E [x2]] E [[a]] = = -0.
Moreover, the conditional variance of Av given is
Var Ax
p]
Var [pv p] p² Var pl p² Var [v] = =p²
and thus (ii) holds. Finally, show that (iii) holds. We already have established that each entry of X1 and of X2 has zero mean and STD=1. Let ag, by be a row or A and its corresponding entry of b.
Let 24 be arbitrary column of X, or Xº. Then
d (I:),] = -0 0-00 = 0,
lax- x3)
Σ (ax); (xi),
=
Σ E (ax),
j=1
5=1
35

---

and by definition E [b&] = 0. Since each (ax), and (ax) are independent random variables with expectation zero, we have that
d Var [ax))] Var (1s) =
d
Var [ox Iz. = Var Σ j=1
(anly (2t))
22
2
1=1
j=1
and by definition Var [bx]] 2. Therefore, (iii) holds.
Computational resources memory.
All experiments were run on an NVidia A40 GPU with 48 GB of GPU
E.2 Graph separation
We ran the graph separation experiment using the PyTorch Geometric [10] implementation for WWL convolutions' and the GCN convolutions of [18], as well as their version of the TUDataset [30]. As initialization for the node features, we only took the node degree.
When moving from the abstract mathematical world to finite features that are mathematically equal h; h2 could end up having slightly different values. To deal with this, all computations
precision computing,
done in double precision. The final features computed by the MPNN were normalized to have an average norm of one, and features h4, h2 were deemed equal if h; hyl < 10-12, In Figure 5 we show
10-1
10-3
10-3
the minimum and median of the quantity ||,, - hyl over all (f.j) from all graphs for which this norm was larger than the threshold of 10-12, This is shown for the SiL.U function of the hidden dimension used. We see that the minimal non- zero distance was safely larger than the threshold in all examples. Also note that the minimal distance moderately improves the hidden dimension increases.
10-7
average feature norm
median non-2ero distance
10-9
minimal non-zero distance
threshald
activation, and the values shown
10-11
20
40
60
80
100
Figure 5: Minimal and median distance be- tween non-equivalent features function hidden feature dimension.
36


Reviews:
[{"review_id": "pqxwU5v8tt", "reviewer": "Reviewer_ezv6", "summary": "Injective functions on multisets are commonly employed in the literature for universality results on (multi)set architectures and graph neural network separation results. Usually, the assumption is that MLPs can implement moment injective functions. The paper studies whether MLP architectures are moment-injective in the space of multisets and the conditions that are required to ensure that. \n\nThe paper argues that for a (shallow) MLP to be moment injective, its activations have to be analytic and discriminatory. The paper considers a more generalized treatment that views multisets from the perspective of signed discrete measures. The goal of the proof for moment injectivity is to show that a shallow MLP separates all pairs of distinct measures in the space of measure parameters. There are two key conditions for the main theorem : \n\n- the activation of the MLP needs to be analytic and discriminatory, which are classic conditions for MLP results\n- the finite witness theorem, which is used to reduce an infinite number of equalities down to a finite one.\n\nThe finite witness theorem (and its generalized version) can be leveraged to show the moment-injectivity of various functions.\n\nThe paper then examines cases (alphabets) where moment injectivity doesn't hold for piece-wise linear activations. The stability properties (stability is studied through the lens of bi-lipschitzness) of injective multiset functions induced by moment injective MLPs are then studied and it is shown that as long as any moment injective function is differentiable at some point, then the induced multiset function won't be stable (bi-lipschitz).\n\nFinally, the paper provides a couple of applications of the technical results to function approximation and graph separation and provides some experimental evidence to back some of the technical claims up.", "questions": "We see in the second experiment a somewhat significant difference between leaky ReLU and ReLU. Could that be a matter of randomness from different initialization, or could the properties of the function that could lead to worse outcomes when it comes to matching the 1-WL? I don't see any obvious reason why the leaky activation would be much different.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper contains several interesting mathematical results which could be useful to the broader graph/set NN community.\n- The paper is well written and generally provides enough context and guidance for the results to be understandable.\n- The theoretical results are focused on architectures that are used in practice.\n- The experiments provide additional context and intuition for the applicability of the results.\n- The paper is upfront about its scope, limitations, and practical applicability.", "weaknesses": "- The initial motivation of the paper is the moment injectivity of 'practical' MLPs. While several results are ultimately established, we can see from the experiment on graph separation (and it is clearly stated in the conclusion) that even non-analytic functions just barely fail in a few cases to match 1-WL. This seems to suggest that the practical relevance of the results is a bit questionable, or maybe there are other factors that could be mitigating the non-analyticity of the activations. \n\n- A few extra explanatory lines could be included in the section of the finite witness theorem (or perhaps in the introduction), that provide context about its exact role in the proof. Currently, the theorem shows up a bit abruptly when theorem 3.3 is presented. OK, it can be inferred from the proof of 3.3 that infinitely many equalities are reduced down to a finite number, but I believe the readability of that section could improve if some of the context that is provided in the supplementary material was moved in the main text to make sure that the role of the theorem is very clearly explained and emphasized. Specifically, when explaining proof 3.3, around line 154 or perhaps right below the statement of 3.4, in subsection 3.1. Those could be good places to provide a few more sentences that restate the purpose of the theorem and explain the context around it (papers by Balan et al., and Dym and Gortler).\n\nI am skeptical about the significance of the results when it comes to practical considerations but the paper is well written and provides mathematical insights that can be relevant to modern deep learning architectures so I lean towards accepting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his/her constructive review. Below we address the weaknesses and questions raised by the reviewer.\n\n**Response to Weaknesses**\n\n1. While indeed in our experiments ReLU-based embeddings performed similarly to analytical activations when the embedding dimension was high enough, this can be contrasted by the following fact: For any moment function $\\hat{f} : \\mathcal{S}_{\\leq n} (\\mathbb{R}^d)$ based on ReLU-activated networks, there exists some $\\delta > 0$ and neighbourhood of radius $\\delta$ on which $\\hat{f}$ is not injective. In contrast, for any $\\delta>0$, any injective analytical embedding $\\hat{f}$ is guaranteed to be bi-Lipschitz on all pairs of point-sets whose distance is at least $\\delta$. Namely, assuming that the domain is compact, for any $\\delta>0$ there exist constants $c(\\delta),C(\\delta) > 0$ such that if $W_2(X_1, X_2) \\leq \\delta$, then $c(\\delta) W_2( X_1, X_2 ) \\leq \\lVert \\hat{f}(X_1) - \\hat{f}(X_2) \\rVert \\leq C(\\delta) W_2( X_1, X_2 )$. \n\n    The reason why we did not enounter pathological $\\delta$-neighborhoods for ReLU in our experiments with high $m$ is because we drew the input clouds randomly rather than explicitly looking for adversarial examples. We intend to clarify on this in the camera-ready version if our paper is accepted.\n\n2. We revised Section 3 to clarify the role of the finite witneess theorem in the proof of moment injectivity.\n  In the revised version, the theorem is gently introduced to the reader before proving Theorem 3.3, and only then it is applied to prove the result.\n  Our new proof of Theorem 3.3 is, in our opinion clearer, and places more emphasis on the essential role of the finite witness theorem.\n  \n**Response to Questions**\n\nWe conjecture that the differences in favor of Leaky ReLU over ReLU (Figure 1) result from the latter having a region where it is identically zero.\n\nAn interesting perspective on this is to compare a ReLU, a leaky ReLU and a nonpolynomial analytic activation, by regarding their restrictions to the region x < 0 as polynomials of degree 0, 1 and $\\infty$ respectively. In light of Theorem 3.3, it seems plausible that as the degree of the polynomial increases, the likelihood of getting the same output $\\hat{f}(X_1)=\\hat{f}(X_2)$ for a distinct pair of inputs $X_1,X_2$ should decrease.\n"}, {"review_id": "WBno0UHuAm", "reviewer": "Reviewer_ejpb", "summary": "In this paper, the authors study the injectivity of functions of multisets, which has garnered a lot of attention recently in the machine learning community following work on point clouds and graphs. Unlike earlier work, which prove results for generic continuous functions or polynomials, then may resort to the universality of MLPs but with unbounded width, here the authors directly focus on MLPs with finite width and prove injectivity with near-optimal width, for almost all parameters. This holds with analytic non-linearity, and on the contrary negative results are given for piecewise linear functions like ReLU. Their result relies mostly on a new \"finite witness\" theorem, which extend previous results known for semi-algebraic sets and functions to sub-analytic sets and functions. Several corollaries are presented, as well as some illustrative numerical experiments.", "questions": "Some questions/minor typos:\n- l45: nessecary\n- equation (***): missing indices $i$ on the $x$'s\n- same equations: might be clearer if the $a$ and $b$ were indexed by $i$ and the $x$'s by $j$ (or vice versa)\n- thm 3.4: co-existence of $D$ and $D_\\theta$\n- eq (6) and lines below: in your definition of Wasserstein, do you mean \"uniform\" weights instead of \"unit\"? $S_1$ and $S_2$ may have different cardinality, but the associated measure must be normalized to compute (the classical) Wasserstein\n- l 288: seleceted\n- l 298: Lipshcitz\n- the experiment on bi-Lipschitz is not really illustrative of the theory, since functions are not bi-Lipschitz. It is not uninteresting in describing another phenomenon (the \"almost\" bi-Lipschitzness on finite data, etc), but I wouldn't say that it \"corroborates Thm 5.1\"", "limitations": "Authors have focused extensively on negative results and limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This is honestly a fantastic paper, I very much enjoy the read, it is clear, pedagogical, and refreshingly honest. The results presented are of great interest for the community. Although it is an extension of a known results on semi-algebraic sets, as acknowledged by the authors, the extension seems anything but trivial. The large part dedicated to negative results and/or limitations is very much appreciated.", "weaknesses": "Minor weaknesses; maybe a tad more explanation on the difference between semi-algebraic and sub-analytic proof (I understand both lies on the same underlying proof technique initiated with works on phase retrieval, but with different tools, how would you describe the main difference if possible?), and a bit more outlooks: do you have any more insight what would be a desirable property to show on ReLU networks, since they are definitely not injective, but are used in practice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the supportive and helpful comments. Below are our responses to the questions and weaknesses.\n\n**Response to Weaknesses**\n\n1. We thank the reviewer for the suggestion. We intend to add to the text an explanation of the main challenges and ideas in this generalization. \n\n    In a nutshell, The proof of the finite witness theorem in [Dym and Gortler] relies on several nice properties of semialgebraic sets: This family is closed to linear projections, finite unions, finite intersections, and complements. Moreover, they are always a finite union of smooth manifolds. Using these properties, [Dym and Gortler] prove a finite witness theorem for semialgebraic sets and corresponding functions, called semialgebraic functions. These functions include polynomials, but do not include other analytic functions of interest.\n\n    The generalization of the finite witness theorem to the analytic setting relies on the mathematical study of o-minimal systems, which searches for larger families of sets that enjoy the same properties as semialgebraic sets. There are several known o-minimal systems, such as globally subanalytic sets, which do have the same nice properties. For these sets, the generalization of the finite witness theorem is rather straightforward. However the corresponding collection of globally subanalytic functions still does not include all analytic functions. A crucial observation in the proof is that we can make it carry through also when considering countable unions of globally subanalytic sets. Consequently, the corresponding functions we can work with include all analytic functions.  \n\n2. Although any finite-size ReLU-activated network is not moment injective, it can be shown that moments of shallow ReLU networks are universal approximators of continuous injective functions on multisets; this is due to the ReLU function being discriminatory, as commented below the statement of Corollary 6.1. Thus, taking a high enough embedding dimension, it is possible to construct invariant embeddings using ReLU activations that are practically injective. This comes with a caveat, though, as we noted in our response to Reviewer ezv6: Each such embedding has a nonzero-measure subset of the input domain on which it is provably not injective. Should the paper be accepted, we intend to comment on this in the camera-ready version.\n\n\n**Response to Questions**\n\nWe thank the reviewer for the corrections.\n\n1. In Eq. (6) and below, the term $\\text{\\emph{uniform}}$ is indeed more suitable, as the proof works well with a total mass of 1.\n\n2. We rephrased the text describing the bi-Lipschitzness experiment (Line 296) and removed the statement that the results corroborate Thm 5.1."}, {"review_id": "jcuXkjKtht", "reviewer": "Reviewer_gUtg", "summary": "This paper studies moment-injective functions defined by neural networks. A moment injective function f can be used to define injective multiset function $g(\\{\\{x_1, x_2, ..., x_n\\}\\}) = \\sum_{i = 1}^n f(x_i)$. Study of infectivity of multiset functions is motivated by recent developments in Graph neuran networks and Message-Passing Neural networks.\n\nPrior work shows that when $x_i \\in \\mathbb{R}^d$ moment injective function f should be an embedding of dimension at least nd, moreover one can construct moment-injective polynomial embedding of dimension 2nd+1.\n\nThis paper extends prior work by showing that depth 1 neural networks of width at least 2nd+1 with analytic non-polynomial activation unit defines a moment injective embedding for almost all choices of weights. Moreover, the paper shows that the result can be generalized to neural networks of higher depth (from theoretical perspective depth-1 case is the most interesting, as it involves the least amount of parameters).   ", "questions": "1) The paper shows that MLPs define injective multiset functions if activation is analytic non-polynomial, and fail to define injective multiset functions if activation is piecewise linear. What happens if activation is polynomial? Is it easy to see that such activations fail similarly to piecewise linear activations?\n\n2) I think it worth replacing \"up to a multiplicative factor of 2\" everywhere in the paper with \"up to a multiplicative factor of 2+o(1)\" to be mathematically precise. If one is pedantic, 2nd+1 is not within a factor of 2 from nd.\n\nI believe the paper contains several typos:\nL47: a Euclidean -> an Euclidean\nL129: this paper -> that paper (?)\nL456 quality -> qualify.", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper provides theoretical explanation why neural networks are successful in providing injective multiset functions that gained popularity since the seminal Deep-Sets paper. While neural networks are long-known to be universal approximations for $f: R^k -> R^n$. Much less is known about multiset functions represented by neural networks. The main result proven in this paper (Theorem 3.3) shows that depth-1 neural networks can be used to define injective multiset functions, moreover, they achieve currently best-known embedding dimension. The paper also shows that one cannot use piecewise-linear activations to construct injective multiset functions and should use analytic non-polynomial activations instead (for example, sigmoid).\n\nThe paper is well-structured and provides a clear comparison to the prior work. The proofs are rigorous and well-written and as far as I can tell are correct.", "weaknesses": "I think the paper may benefit from slightly more detailed discussion of applications of injective multiset functions. While injectivity is a natural property that proves to be useful in various setups, I believe it will be nice to include a slightly more detailed discussion of the applications in the introduction. Some example applications are presented in Section 6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his/her helpful comments. Below are our responses.\n\n**Response to Weaknesses**\n\nWe thank the reviewr for this comment. Should the paper be accepted, we intend to add to the introduction a broader explanation of the importance of injective multiset functions for practical applications.\n\n**Response to Questions**\n\n1. A possible direction to show how polynomial activations fail would be as follows: If $\\sigma : \\mathbb{R} \\to \\mathbb{R}$ is a polynomial of degree $r$, then $\\text{span} \\\\{ \\sigma(ax+b) \\\\, \\mid \\\\, a \\in \\mathbb{R}^d, b \\in \\mathbb{R} \\\\}$ is a subset of the span of all polynomials of degree up to $r$ over $\\mathbb{R}^d$. Denote the latter by $\\mathcal{P}\\_{r}$. Using the fact that $\\mathcal{P}\\_{r}$ is not dense in $\\bigcup\\_{t=0}\\^{\\infty} \\mathcal{P}\\_{t}$, show that for a large enough $n$ there exist $n$ points $x_1,\\ldots,x_n \\in \\mathbb{R}^d$ and a polynomial $q \\in \\mathcal{P}\\_{r'}$ for some $r'>r$ such that: (a) $\\sum_{i=1}^n q(x_i) p(x_i) = 0$ for any $p \\in \\mathcal{P}\\_{r}$; (b) not all of $q(x_1),\\ldots,q(x_n)$ are zero. Let $\\mu = \\sum_{i=1}^n w_i \\delta_{x_i}$ be the discrete signed measure with weights $w_i = q(x_i)$. Then (a) implies that for any embedding $\\hat{f}$ comprised of moments of $\\sigma(ax+b)$, $\\hat{f}(\\mu) = 0$, although by (b), $\\mu$ is not the zero measure, hence injectivity is violated.\n\n2. We thank the reviewer for this comment. We will replace this statement by a more accurate one."}]

Author rebuttal:

Meta-review: This paper provides analytic conditions for an MLP to be moment injective. The reviewers unanimously agreed that this is a great paper and worthy of being accepted to NeurIPS, and I concur.
Decision: Accept (spotlight)