On the Hölder Stability of Multiset and Graph Neural Networks
Authors: Yair Davidson
Nadav Dym
Venue: ICLR 2025 Oral (2025)
Keywords: graph neural networks
message passing neural networks
multiset neural networks
neural network stability
expressive power
WL tests
Primary area: learning on graphs and other geometries & topologies

Abstract: Extensive research efforts have been put into characterizing and constructing maximally separating multiset and graph neural networks. 
However, recent empirical evidence suggests the notion of separation itself doesn't capture several interesting phenomena. On the one hand, the quality of this separation may be very weak, to the extent that the embeddings of  "separable" objects might even be considered identical when using fixed finite precision. On the other hand, architectures which aren't capable of separation in theory, somehow achieve separation when taking the network to be wide enough.

In this work, we address both of these issues, by proposing a novel pair-wise separation quality analysis framework which is based on an adaptation of Lipschitz and Hölder stability to parametric functions. The proposed framework, which we name Hölder in expectation, allows for separation quality analysis, without restricting the analysis to embeddings that can separate all the input space simultaneously. We prove that common sum-based models are lower-Hölder in expectation, with an exponent
 that decays rapidly with the network's depth . Our analysis leads to adversarial examples of  graphs which can be separated by three 1-WL iterations, but cannot be separated in practice by standard maximally powerful Message Passing Neural Networks (MPNNs). To remedy this, we propose two novel MPNNs with improved separation quality, one of which is lower Lipschitz in expectation. We show these MPNNs can easily classify our adversarial examples, and compare favorably with standard MPNNs on standard graph learning tasks.

Published as a conference paper at ICLR 2025
ON THE HÖLDER STABILITY OF MULTISET AND GRAPH NEURAL NETWORKS
Yair Davidson'
Nadav Dym"
1 Department of Computer Science Technion, Haifa, Israel
2 Department of Mathematics - Technion, Haifa, Israel
ABSTRACT
Extensive research efforts have been put into characterizing and constructing maxi- mally separating multiset and graph neural networks. However, recent empirical evidence suggests the notion of separation itself doesn't 't capture several interesting phenomena. On the one hand, the quality of this separation may be very weak, the extent that the embeddings of "separable" objects might even be considered identical when using fixed finite precision. On the other hand, architectures which aren't it capable of separation in theory, somehow achieve separation when taking the network to be wide enough.
In this work, we address both of these issues, by proposing a novel pair-wise sepa- ration quality analysis framework which is based on an adaptation of Lipschitz and Hölder stability to parametric functions. The proposed framework, which we name Hölder in expectation, allows for separation quality analysis, without restricting the analysis to embeddings that can separate all the input space simultancously. We prove that common sum-based models are lower-Hölder in expectation, with an exponent that decays rapidly with the network's depth. Our analysis leads to adversarial examples of graphs which can be separated by three 1-WL iterations, but cannot be separated in practice by standard maximally powerful Message Pass- ing Neural Networks (MPNNs). To remedy this, propose two novel MPNNs with improved separation quality, one of which is lower Lipschitz in expectation. We show these MPNNs can easily classify our adversarial examples, and compare favorably with standard MPNNs on standard graph learning tasks.
INTRODUCTION
Motivated by multitude of applications, including molecular systems Gilmer et al.) (017). social networks (Borisyuk et al.] (024)), recommendation systems (Gao et al. 2023) and more, permutation invariant deep learning for both multisets and graphs have gained increasing interest in recent years. This in turn has inspired several theoretical works analyzing common permutation invariant models, and their expressive power and limitations.
For multiset data, it is known that simple commmation--asee multiset functions are injective, and as result, can approximate all continuous functions on multisets (Zaheer et al. (0077). These results have been discussed and strengthened in many different recent publications (Wagstaff et al., 2019
Amir et al. 2023 Tabaghi & Wang 2024
Wang et al.) 2024).
For graph neural networks (GNNs) the situation is more delicate, as all known graph neural networks with polynomial complexity have limited expressive power. Our focus in this paper will be on the Message Passing Neural Network (MPNN) (Gilmer et al. (017)) paradigm, which includes a variety of popular GNNs (Xu et al. 2019 Gilmer et al. 2017
| Kipf & Welling 2017). In their seminal works, Xu et al. (2019) Morris et al. (2019) analyze the separation capabilities of MPNNs, showing that an MPNN f can separate two graphs G and H (i.e., (G) + fH)) only if the Heisfeiler-Lehmaal (WL) isomorphism test /Weisfeiler & Lehman 1968) can also do so. Accordingly, maximally expressive MPNNs are those which are able to separate all graph pairs which are WL-separable. They further show that MPNNs which employ injective multiset functions are maximally expressive.

---

Published as a conference paper at ICLR 2025
The theoretical ability of permutation invariant network to separate pair of objects (multi- sets/graphs) is a necessary condition for all learning tasks which require such separation, e.g. binary classification tasks where the two objects have opposite labels. However, while current theory ensures separation, it tells us little about the separation quality, so that embeddings of "separable" objects may be extremely similar, to the extent that in some cases, graphs which be theoretically separated are completely identical on computer with fixed finite precision. This pheonomena was observed for graphs with analytic activations and very small width, see (Bravo al. 2024). figure 2 top.
In a non-parametric setting, separation quality of a function / can be studied via bi-Hölder stability guarantees: for metric spaces (X, dx) and (Y, dyy), ), a function f : X + Y is 3 upper-Hölder Hölder and a lower-Hölde if there exist some positive constants c, C' such that
cdx(x,x')) S dy((xx), f(()) s (dx(z,,')) E
The upper and lower Hölder conditions guarantee that embedding distances in Y will not be much larger, much smaller, than distances in the original space X (in case space of multisets graphs). A function ff will have higher separation quality the closer the Hölder exponents are to one. When 3 1 we say f is (upper) Lipschitz, and when a we say that f is lower Lipschitz.
Bi-Lipschitz stability analysis is a central topic in the study of frames Balan 1997 Alexeev et al.
(2012). phase retrieval Bandeira al. (2014); Cheng et al. (202T), ) and several group-invariant invariant learning scenarios Cahill et al. (2020; 2024b). For multisets, Bi Bi-Lihschitz stability results are known for
fultiset-functions based on max- max-filters Cahill et al. (024g) or sorting Balaan al. (2022). However, this is not the case for more common sum-based multiset functions: Amir et al. (223) showed that Relu-sum multiset functions, which are based on summation of point-wise applied ReL.U networks (see (I) below) are never even injective. Multiset functions which smooth activations instead, are injective but not lower-Lipschitz. Accordingly, a remaining challenge, which we will address in this paper, is characterizing the lower-Hölder stability of sum- sum-based multiset functions.
For MPNN architectures for graphs, there are even less stability results. The upper Lipschitz- ness of the MPNN GIN (Xu et al. 2019) and similar architectures
established in (Chuang & Jegelka| 2022), however lower Lipschitz or Hölder guarantees have not been addressed to date. Indeed, a recent survey (Morris al., 2024) lists bi-Lipschitz guarantees for MPNNs
of the future challenges for theoretical GNN research. We will address this challenge in this paper as well.
As first step for our stability analysis, need to establish how extend notions of Hölder stability to parametric functions. One simple approach is requiring the parametric function to be uniformly Hölder, with the same exponent and constant regardless of the parameter choice. Indeed, will show that all parameteric functions we consider in this paper are uniformly upper-Lipschitz.
In contrast, we believe the notion of uniform lower-Hölder be too stringent. For example, as mentioned above, multiset networks based on ReLU activations are never injective, and so can't 't be uniformly lower-Hölder. Nonetheless, numerical estimates of the stability of such networks show that wide ReLU networks have comparable or even better stability than injective
based multiset functions (see Amir et al. (2023) Figure 2). Accordingly, we resort to a probabilistic framework of Hölder stability in expectation, as presented in section
multisets With respect to our new relaxed notion of expected lower-Hölder, we show that ReLU-sum multiset networks have an expected Tower-Höldes expo- of 3/2. Surprisingly, while smooth activations lead to injectivity, we find that their expected Hölder ex- ponent is much worse: best is equal the maximal number of elements in the multiset data, a 2 n. This scenario summarized in Figure T For given pair of multisets, smooth activations will separate even with very small network width, but the separation quality can be very poor. In contrast, shallow Relu-sum networks may not attain separation. However, as width increases separation will be obtained (with high probability). and the expected quality of separation will surpass the quality attained with smooth activations.
Main results:
10a
10:2
Embedding distanre
10.
10
10-12
13
elu
smooth
10-18
W;
10a
10a
Wilth
Figure 1: Separation quality on single adversarial multiset-pai constructed as described in appendix G.3
2

---

Published as a conference paper at ICLR 2025
The relatively moderate exponent 3/2 of ReLU networks is guaranteed only when the range of the bias of the network contains the range of the multiset features, an assumption which may be problematic to fulfill in practice. To address this, suggest an Adaptive ReLU summation network, where the bias is adapted to the values in the multiset. This network is guaranteed the same 3/2 exponent while overcoming the range issue.
Finally, we consider multiset functions based on linear functions and column-wise sorting. These were shown to be bi-Lipschitz, when wide enough, in (Balan al. 2022). We show that they are lower Lipschitz in expectation even with a width of 1.
Main Results: MPNNs MPNNs are constructed upon mul- tiple application of multiset functions node neighborhoods. We consider four MPNNs based on the four multiset functions analyzed: SortMPNN, ReluMPNN, SPNothMPNN and AdaptMPNN. We show that SortMPNN is Lower-Lipschitz in expectation, even with a width of 1. SortMPNN thus the first MPNN with both upper and lower Lipschitz guarantees. In contrast, we show that ReluMPNN and SmoothMPNN are only löwer-Hölder, with an exponent that deteriorates as the MPNN depth grows. The exponent bounds of both the graph and multiset models appear in table TT
Table I: Summary of lower-Hölder exponent bounds for multiset (top) and graph (bottom) models.
Model
bounds
relu sum
3/2
adaptive relu
a 3/2
smooth
sort based
ReluMPNN
K+l a
SmoothMPNN
2
SortMPNN
a=1
Our analysis provides an adversarial example illustrating the deterioration of the expected lower-Hölde exponent of sum-based MPNNs the depth increases. We show in Table 2 that sum-based MPNNs fail to learn a simple binary classification task on such data, while SortMPNN and AdaptMPNN handle this task easily. We also provide experiments on several graph datasets which show that SortMPNN often outperforms standard MPNNs on non-adversarial data, and is more robust to reduction model size.
1.0.1 Notation Sd-1 denotes the unit sphere in RR The notation 'a Sd-1 and [-B, B) implies that the distribution (respectively b) is taken be uniform g (respectively [- B, BJ,, and that a and b are drawn independently. æ denotes the inner produce x,
2 GENERAL FRAMEWORK
In this section, present the framework for analyzing separation quality of parametric functions. We begin by extending the notion of Hölder stability to a family of parametric functions.
2.1 HÖLDER STABILITY FOR PARAMETRIC FUNCTIONS
Let (X, dx) and (Y,dy) be psuedo-metric spaces. Let W be some set of parameters, and let f(x; w) X x W - Y be a parametric function. We say that f(x;w) is uniformly Lipschitz with constant L 0, if for all can naturally be extended to other upper-Hölder exponents, but this will not be necessary as the parametric functions we discuss this paper will all end up being uniformly Lipschitz. Similarly, we could define notion of uniform lowderHölder, but as discussed in this introduction, this notion too stringent for the problems we are discussing, and so we introduce the alternative notion of lower-Hölder in expectation:
W. the function x + f(x; w) is L-Lipschitz. This definition
Definition 2.1. Let a > 0,P 2 1. Let (X,dx) and (Y, dy) be psuedo-metric spaces, and let (W,B, μ1) be a probability space. Let f(x; w) X x W - Y be a parametric function, so that for every fixed E X the function f f(;;) :) measurable.
We say that ff is a lower-Höldes in expectation there exists strictly positive e such that
{ dy (), ()) dx (x)
8 < Eurnge
V(c,z') X, with d(z, > 0
A psuedo metric dx differs from standard metric only in that the (x1 x2) = 0 possible even if
Ti 22.
3

---

Published as a conference paper at ICLR 2025
A few remarks this definition are in order. Firstly, note that if the set of w for which f(x; w) is a twwer-Hlddrr has positive probability, then f(x; w) will be a lower-Hölder in expectation. The opposite is not true: Relu-sum networks for multisets are never injective, and hence never lower- Hölder, but we will show that they are lower-Hölder in expectation. This possible since it is defined in pairwise sense, similar the separation analysis in Morris al. (2019).
Next, we note that our definition takes an expectation over the parameters, but requires uniform boundedness over x x' pairs. This choice was made since data distribution is unknown, while the parameter distribution at initialization can be chosen by the algorithm. Furthermore, we conjecture that bad separation at initialization will be difficult overcome during training. Supporting evidence for this claim will be shown later on (see table 2. where models with large lower-Hölder in expectation exponent, fail to learn an adversarial binary classification task.
Thirdly, we note that Hölder in expectation exponents that are closer to one will be regarded as having higher separation quality. Fourthly, p the definition refers the lp norm chosen for the feature spaces. Results stated in the introduction are for the default
2.
Finally, while the expected value across random parameters informative as is, the variance can potentially have a strong effect the separation in practice. Luckily, our analysis will typically apply for models f (a;; w) of width 1, and models with width W can be viewed as stacking of W multiple model instances. Wider models will have the same expected distortion as the width one model, but the variance will converge to zero, in a rate proportional to 1/W For more details see Appendix B.
We now proceed to analyze Hölder stability for parametric models multisets.
3 MULTISET HÖLDER STABILITY
Standing assumptions:
Throughout the rest this section, we will say that (n, d, p, Q, 2) satisfy standing assumptions, if n, d are natural numbers, p 2 1, the set Q is compact subset of Rd and x will be a point in IRd 92.
A multiset f=I....,, #
; } is collection of unordered elements where (unlike sets) repetitions allowed. We denote by (S2) and (2)) the space all multisets with at most n elements (respectively, exactly elements), which reside in f2
popular choice of metric on (=n( is the Wasserstein metric
Wi (f ... Fn B. [1i, Va B)
min TES.
Σ jay vr(i
Following (Chuang Jegelka 2022), we extend the Wasserstein metric the space Szn (S2) by the augmentation map which adds the vector to given multiset until it is of maximal size n:
P()) (f
[ Tk, Ik+1 = 2, II, =
This induces the augmented Wasserstein metric Wi on (2n,
WF(S,, (1)
S2 E (Q)
Now that we have introduced the augmented Wasserstein as the metric we will use for multisets, we turn analyze the multiset neural networks
interested in.
popular building block in architectures for multisets (Zaheer et al., (017). as well as MPNNs (Xu ctt al. 2019 Schütt al.) 20017] Gilmer al.) (001), based on summation of element-wise neural network application. For a given activation о
R, we define a parametric function m, on multisets in (S2) with parameters (a, b) E Idd R. by
mar (1x1, Bia Σ o(a -b)-
We note that we focus on m, with scalar outputs, since the variant with vector output has the same Hölder properties, as discussed in the end of Section
4

---

Published as a conference paper at ICLR 2025
3.0.1 ReLU summation We first consider the expected Hölder stability of ma. when ReLU:
Theorem 3.1. For (n, d. p, S, satisfying our standing assumptions, assume that a S and
b [- B). Then Ru (:1 a. is uniformly Lipschitz. Moreover,
1. RRLUU (:; (;a,b) b) is not a lower-Hölder in expectation for any a p+1
2. If |/]| < B for all x E Q then mRRUu( a, is p+1 lower-Hölder in expectation.
Proof idea: the 4e example. The following example, which we nickname the +e example, gives a good intuition for the Hölder behavior of MRRLU. Denote X, = {e,,e) and X2. = f , 2e }. The Wasserstein distance between these two multisets is proportional to Now, let us consider the images of these multisets under MRLLU, where we assume for simplicity that d = and 1. Note that when > 2c will get Le - b) 0 for all in either sets, and so ma.Lu( 1, b) = MBeLu(Xe: 1,,)), b). We will get a similar results when I -2.. In this case, for every 2c have RcLU(r b) = x - b. Therefore, will obtain that
MReLU (X2:: (MReLu(X2::L0 1) (-2e b) + (2c b) (-c + (e b) = (X.LL(X.; 1, vb < -2..
We conclude that |MRLLL (N2e: 1, MRELU(X, 1, b){² is zero for all b outside the inter- val (-2e, Inside this interval length 4e, we will typically have IMRRLL((2:: 1, MR....(X. (X,; 1)l" f, so that the expectation over all will be proportional to 4e e ~ eP+1 To ensure that the ratio between e and (X) ~ ePP will have a strictly positive lower bound as c + 0 we need to choose a 2 p+1 The proof that a = p+1 is actually enough, and several other details necessary to turning this argument into full proof, are given in the appendix.
P
3.0.2 Adaptive ReLU To attain the (p + 1)/p exponent theorem 3.1 we need to assume that the bias is drawn from interval [-B, B] which is large enough that ||>||| < B for all a E St This assumption may be difficult to satisfy, especially in MPNNs where the features in intermediate layers effected by previous parameter choices. Additionally, the +c example shows that when is outside the range of the multiset features, MRELU is not effective. Motivated by these observations, we propose novel parametric function for multisets, based ReL.U, where the bias automatically adapted to feature values. For multiset = [ Tr and a E Rd E [0, 1). adapt aX;a,t a, f) is defined using m = minfa Z1..... a Ir M
the adaptive ReLU function mRe. max (a .1...., a I. (1 1ym 1M and
m RRLU (X;a,)) = [r, m, M, ReLU(a x4 b)]
The output of ReLU is a four dimensional vector. The last coordinate of the vector is essentially MReLU, where the bias now only varies between the minimal and maximal value of multiset features. The first three coordinates are simple invariant features of the multisets: its cardinality and minimal and maximal value. In the appendix we prove
Theorem 3.2. For (n, d. p, S2 2) satisfying our standing assumptions, assume that a ~ Sd-1 and adapt.
I [0, 1}. Then the function MRRL (s2) x 5d x [0, + R2 is uniformly Lipschitz and p+1 lower-Hölder in expectation. Moreover, when n 2 the function MeLC is not lower-Hölder p
in expectation for any p+1
We note that while adaptive ReLU solves the te example, a similar issue can be created for adaptive ReLU with multisets such as 0,, 0, - 1 and 61,,, -1 which force the adaptive bias to cover the interval [1, 1]. Nonetheless, the delicate bias range assumption is no longer an issue.
3.0.3 Summation with smooth activation We now consider the Hölder properties of m, when the activation a is smooth (e.g., sigmoid, SiLU, tanh). To understand this scenario, it can be instructive to first return to the te example. In this example, since the elements in X, and X2. both sum to the same number, one can deduce that (for any choice of bias) the first order Taylor expansion of m (X2.) mx...) will vanish, that this difference will be of the order of e². Based on this
5

---

Published as a conference paper at ICLR 2025
example already see that for smooth activations 2. However, it turns that there adversarial examples with much worse behavior. Specifically, note that X, and X2x are "problematic' because their first moments are identical. In the same spirit, by choosing pair X, X' of distinct multisets with n elements in IR, whose first n - moments are identical, we can deduce that a 2 n: R + R has continuous
Theorem 3.3. Assume (n, d. p, 22,22) satisfy our standing assumptions, derivatives, and a ~ Sd-1, ~ B, B). If function m (:3a, a, b) is a lower-Hölder expectation, then a 2
siamold
relu
3.0.4 Sort based We now present fourth and final
1.25
d=16 detapoints
0.08
a=115
multiset parametric function. Based on ideas from
(Balan et al., 2022 Dym & Gortler 2023), we con-
1.00
0.06
sider the parametric function
0.04
Sx ax b) b sort(a (X))
(2)
Embedding distance
0.25
0.02
where X E gdxn and a, b are in Sd-1 and S respectively. Note that in contrast with our previous functions, S₂ explicitly includes the augmentation by z. On the bright side, the sort-based parametric functions are lower-Lipschitz in expectation.
0.00
0.00
0.0
0.0
adaptive relu
sort
0.015
0,20
0.15
0.010
0.10
Theorem 3.4. For (n, d, S2, satisfying our stand- ing assumptions. Assume that S Then Sz(:; a, b) is uniformly upper Lipschitz and lower Lipschitz in expectation.
0.005
S and b
0.05
0.00
0.000
0.0
0.5
1.0
0.0
0.5
1.0
Multiset
The proof of this claim is that such mappings were shown be bi-Lipschitz for all parameters, when du- plicated enough times (with independent parameters) (Balan et al. 2022). This implies bi- bi-Lipschitzness in expectation for the duplicated function, which in turn implies bi-Lipschitzzess in expectation for a single function since the relevant expectations identical.
Figure l2 vs. W22 distance on multiple ad- versarial multiset-pairs. Results are in accor- dance with our theoretical results (see Table
Summary In Figure 2 we choose a pair of distinct multisets X, X' with 16 scalar features each, which have 15 identical moments (for details how this was constructed see Subsection C.2 in the appendix). The figure plots the distance between embedding distances versus the Wasserstein distance, for pairs eX,"X', for varying values of The figure illustrates that the a 3/2 Hölder exponent of ReLU (we take = 2) and the a 2 exponent of sigmoid summation are indeed encountered in this example. The sort and adaptive ReLU methods display linear plot in this case. Recall that while sort is indeed lower-Lipschite in expectation, adaptive ReLU is not. In Remark in the Appendix, we will explain why adaptive ReL.U displays linear plot in this case, and how 3/2 slope can be obtained by slightly changing this experiment.
4 MPNN HÖLDER STABILITY
We will now analyze the expected Hölder stability of MPNNs for graphs, using the various multiset embeddings discussed previously. We begin by defining MPNNs, WL tests, and graph WL-metric.
4.1 MPNNs AND WL
We denote a graph by G (V, F, X) where V are the nodes, are the edges, and X = (xr)) are the initial node features. Throughout this section we will assume, as in the previous section, that Q a compact subset of TRdd and is some fixed point in Rd \ Ω.. We denote the neighborhood of node by N,, {u (), E}. MPNNs iteratively use the graph structure to redefine node features in the following manner: initialize (0) Feg
For k 1
AGGREGATE: c = (1() (1(2) 1) (k- N.
COMBINE: 22(A) wi(k) (z) (xo(1-11) (k)

---

Published as a conference paper at ICLR 2025
In order to achieve a final graph embedding, final READOUT step is performed
READOUT: daloball n1 E VB)
We note that different instantiations of the COMBINE, AGGREGATE, and READOUT parametric functions will lead to different architectures. We will discuss several choices, and their expected Hölder stability properties. slightly later on. Once such an instantiation is chosen, an MPNN will be a parametric model of the form f(G; w) = calobal, where wr denotes the concatenation of all parameters of the COMBINE, AGGREGATE, and READOUT functions.
The Weisfeiler-Lehmar (WL) graph isomorphism test (Weisfeiler & Lehman 1968 Huang & Villar 2021) checks whether two graphs G, H are isomorphic (identical up to node permutation) by applying an MPNN-like procedure while choosing the COMBINE, AGGREGATE and READOUT functions to hash functions, and running the procedure for at most K mar (VGl: Vu)) } (Morris et al.
2019) iterations. The WL test can separate many, but not all, pairs of non- non-isomorphic graphs.
Notably, MPNNS can only separate pairs of graphs which are WL separable, and therefore if we hope for MPNN Hölder stability in expectation, we need to choose a WL metric: pseudo- which is zero if and only if the pair of graphs cannot be separated by WL. Of the several possible choices in the recent literature for such metric (Grohe 2020: Böker Chen et al. 2022).
graphs
choose the family of Tree Mover's 's Distance ((MD()) suggested in (Chuang & Jegelka 2022).
which is described detail in Appendix T'D is a distance which is non-zero if and only two graphs can be separated by K iterations of the WL test. It is based on recursive application of the augmented Wasserstein to multisets of WL computation trees. We note that when K is large enough, (M) a WL metric as discussed above.
4.2 MPNN STABILITY ANALYSIS
We now consider the Hölder stability of MPNNs. The graph domain we consider are graphs in (2), the collection of graphs with up to n nodes, and node features in compact set Ω C IRd
It is natural to expect that the stability properties of an MPNN will be closely related the AGGRE- GATE, READOUT and COMBINE functions composing the MPNN. As COMBINE function, we will choose some parametric functions which is uniformly upper- expectation. As the COMBINE function is a cector-to-vector function, this is easy to achieve even prove the Lipschitz properties of (k) In Appendix D
and lower Lipschitz in
via linear function 2 (k) Ax + Ba(
this and three other COMBINE choices.
The AGGREGATE and READOUT functions are multiset to vector functions, and we have discussed the Hölder properties of four different such choices in Section 3 In practice, at each iteration we take We parallel copies of these functions with independent parameters (W corresponds to the width of the MPNN). As discussed in the end of Subsection 2. this maintains the same results in expectation while reducing the variance. For example, the SortMPNN architecture will be defined using the sort-based parametric functions S₂ from ② via
AGGREGATE: Co. SEN (H E. (M) (0)) i 1
(k-1) READOUT: ggoobal Sax+1
COMBINE: 22(1) 21 + ((k)
((=((K)0 E a
(K+1) , (((+t)) i= 1, WK41
Similarly, we will use the terms AdapIMPNN, ReluMPNN and SmoothMPNN to denote the MPNN adant
obtained by replacing S₂ with the appropriate functions MRLUU MncLU m, with smooth
Our first result regards the upper Lipschitz bound.
Theorem 4.1. (Uniformly Lipschitz MPNN embeddings, informal version) Let f GG) + R be an MPNN with K layers. If the functions used for the aggregation (1,,, combine ()(k), and readout all uniformly upper Lipschitz. then f is uniformly upper Lipschitz with respect to (MD(K) In particular, ReluMPNN, SmoothMPNN, AdaptMPNN and SortMPNN are all uniformly upper Lipschitz.
7

---

Published as a conference paper at ICLR 2025
It would seem natural to expect that similar results will hold for lower-Hölder in expectation guarantees: namely, that if the AGGREGATE, COMBINE and READOUT functions used in the MPNN are lower-Hölder in expectation, then the overall MPNN will be lower-Hölder in expectation as well. Unfortunately, this isn't always the case. In Appendix F22 we give an example of pair of graphs which cannot be separated by any choice of parameter of Relu-MPNN with width 1 and depth 2, even though they are separated by 2 iterations of WL.
The argument above does not rule out the possibility that a wider Relu-MPNN will be lower-Hölder in expectation. Indeed, we suspect that this will be the case for an appropriate width W = W (d, n). but we leave a formal proof of this result for future work. We do prove that, for arbitrarily wide ReluMPNN and SmoothMPNN, we cannot obtain a very good Hölder exponent, with a bound that deteriorates as the depth increases:
Theorem 4.2. Assume that ReluMPNN with depth K is a Lower-Hölder in expectation with respect to ((K),, then a 2 1 + K+1 If SSmothMPPN with depth is a lower-Hölder in expectation then a 2 2K+1
The proof of this theorem is based on an adversarial set of examples we call e-Trees. These are defined recursively, where the first set of trees are of height two, and the leaves contain the the multisets. Deeper trees are then constructed by building upon substructures from the trees in the previous step as depicted in figure aloogsidee a rigorous formulation and proof in Appendix [F3
In contrast to the previously discussed methods, SortMPNN is lower Lipschitz in expectation, even with a width o. 1.
Theorem 4.3. (informal) For any given W 2 1, K > SoMMPNN with width W and depth K is lower Lipschitz in expectation with respect to (M)(K),
While we don't formally analyze the lower-Hölder properties of AdaptMPNN, we conjecture its worst-case behavior will be similar to ReluMPNN. However, in some settings it will have better stability. For example, for our adversarial e- e-Trees example AdaptMPNN has Lipschitz-like behavior, as shown in Figure 3
EXPERIMENTS
In the following experiments, we evaluate SortMPNN, AdaptMPNN, ReluMPNN and SmoothMPNN. As the last two architectures closely resemble standard MPNN like GIN (Xu et al.) 2019) with Rel.U/smooth activation, our focus is mainly on the SortMPNN and AdaptMPNN architectures. In our experiments we consider several variations of these architectures which were omitted in the main text for brevity, and are described appendix G alongside further experiment details.
e-Tree dataset In order to show that the expected (lower) Hölder exponent indeed good indicator of separation quality, and to further validate the importance of separation quality anal- ysis, we first focus on the adversarial c-tree construction used to prove Theorem 4.2
Table 2: c-Tree binary classifica- tion results
Model
Accuracy
CIN
2019
0.5
To begin with, we show how randomly initialized MPNNs with the different multiset embeddings we analyzed distort the TMD metric on the e-trees. In figure 3 we plot the distance between the embeddings provided by the MPNNs, parameter determining the e trees (this parameter is proportional to the TMD distance between the trees). We see how the lower-Hölder exponent increases with depth for ReluMPNN and SmoothMPNN, in a manner which is consistent with the a = K+1 and
GCN Wellin 2017
0.5
GAT Velickovic et al. 2018
0.5
ReluMPNN
0.5
SmoothMPNN
0.5
function of the
SoftMPNN
1.0
AdaptMPNN
1.0
2 bounds suggested by Theorem 4.2 (for p 2). SortMPNN, in contrast, displays virtually no distortion in this example, and its behavior is consisten with the bi-Lipschitness predicted by our theory. Similar results (without theoretical justification) can be observed for AdaptMPNN.
We then proceed to train binary classifier using these MPNNs in an attempt to separate the tree pairs. Indeed, we made this claim in a previous version. We thank Soutrik Sarangi and Abir De for pointing out the error in the proof.
8

---

Published as a conference paper at ICLR 2025
Table 3: Classification accuracy on TUdatasets (Morris al.
2020).
Best in bold, second underlined.
Datasct
Mutag
Proteins
PTC
NCII
NCT109
GIN ct al. 2019
89,425.6
76.242.8
64.627
82.7#1.7
82.2=1.6
Kipt & Weiling 2017
85.6
76:13.22
64.2:1:433
80.2:+2.00
NA
GraphSago et al. 2017
85.1=7.6
75.9+332
63.9:7..7
77.7+1.5
NA
SortMPNN
90.99-16.2
76.46:13.68
6..31:16.73
83.55-11.22
82.75
AdaptMPNN
90.41=6.1
75.12+3..4
66.87
82.77=1.72
03.2
The results in Table show how SortMPNN and AdaptMPNN achieve perfect performance, while ReluMPNN and SmoothMPNN, in addition several baseline MPNNs com- pletely fail. This serves as proof to the importance of separation quality analysis, especially in light the theoretical capability of SmoothMPNN (Amir et al.)
SortMPNN
SmoothMPNN
depth=1
ReLUMPNN
0.020
q=1
a=4
a=2000
60
a=1
0.015
20
40
0.010
embredding distance
10
0.005
2
20
0.000
depth-2
SmocthMPN
SortMPNN
1--7
ReLUMPNN
AdaptMINN
40-
a-8
2.2.5
400
a=1
1.0
2023) and GIN (Xu et al. 2019 to separate these graphs.
20-
0.5
10-
0.0
0.00
TUDataset While the <-Tree dataset emphasizes the impor- tance of high separation qual- ity, validating our analysis, it is not obvious what effect this has in real world datasets. There- fore, we test SortMPNN and AdaptMPNN on subset of the TUDatasets (Morris et al. 2020), including Mutag, Proteins, PTC, NCI1 and NC1109. Table shows that SortMPNN and AdaptMPNN outperform several baseline MPNNs (results are reported using the evaluation method from (Xu et al., 2019)). Note that in all experiments only compare Vanilla MPNNs (1-WL), and not more expressive architectures which often do reach better results, at a higher computational cost.
TMD
Figure 3: la vs. TMD on e-Trees. The targeted ReluMPNN and SmoothMPNN exponents deteriorate with depth, accordance with our theory (see Table
LRGB We further evaluate our architectures
tasks from LRGB (Dwivedi al.) 2022b):
peptides-fune, which is multi-label graph classification task, and the peptides-struct regression task. Results in table show that SortMPNN and AdaptMPNN outperform other methods on peptides-fune. For peptides-struct, GCN is the best performing method with SortMPNN a close second.
Both experiments above adhere to the 500K parameter constraint as (Dwivedi al. 2022b). In addition, we reran the peptides-struct experiment with a 100K, 50K, 25K, 7K and IK parameter budget. The results in figure X in the appendix show SortMPNN and AdaptMPNN outperforming GCN for smaller models, with SortMPNN achieving the best results. We believe this is related to the fact that even SortMPNN with w is lower-Lipschitz in expectation, and accordingly when only small number of features is available, its advantage other methods is more substantial.
Table 4: LRGB results, Best in bold, Second underlined.
Dataset
peptides-fune (AP1)
peptides-struct (MAE))
GI et al. 2020
0.662110.0067
0.2473:0.0017
(ipt & Welling 2017
0.6860+000050
0.2460-10.000
Greson Laurent 2018
0.67651000047
0.2477 0.009
SortMPNN
0.6940-10.00049
0.2464-10.0022.
AdaptMPNN
0.6934+0.0009
0.2484=10.0034

---

Published as a conference paper at ICLR 2025
Subgraph aggregation networks Zine12K Finally, we experiment the of meth- ods as the backbone MPNN in more advanced equivariant subgraph aggregation network al. 2022), which has greater separation power than MPNNs. To this extent, we run the experiment from (Bevilacqua et al. 2022) on the ZINC12K dataset, where we swap the base encoder from GIN (Xu et al. 2019) to SortMPNN and AdaptMPNN. The results shown in show that SotMMPN outperforms GIN in five of the eight different scenarios. For fair comparison, the models don't ton't sur- pass the 100K parameter budget.
(ESAN) (Bevilacqua
Table 5: MAE per base encoder for ESAN on ZINC12K. Best in bold, second underlined.
Method
GIN (Xu el al 2019
SotMPPNN
AdaniMPPN
DS-GNN (ED)
0.172=00008
0.157=0.007
0.176=000008
DS-GNN (ND)
0..0110.010
0.152_0.009
1..08
Code and timing Timing for the LRGB experiment are provided in ta- ble 7 in the appendix. SortMPNN marginally slower than GCN, and AdaptMPNN is X1.87 times slower. Code is available at F
DS-GNN (EGO)
0.126::0.006
0.104=0.004
0.127=00.007
DS-GNN (EGO+)
0.116:+0.009
0.115=0.008
0.126=+0.007
DSS-GNN (ED)
0.172:+0.005
0.169=0.004
0.173+#0.007
DSS--NN (ND)
0.064
0.167=0.006
0.167++0.008
DSS-GNN (EGO)
0.107:10.005
0.115 0.010
0.006
DSS-GNN (EGO+)
0.102=0.003
0.121=0.005
0.131=0.006
RELATED WORK
Sorting Sorting based operations were used for permutation invariant networks on multisets in (Zhang al. 2019), and readout functions for MPNNs in (Balan al. 2022 Zhang al. 2018 Duvenaud et al.) 2013). To the best of our knowledge, our SortMPNN is the first network using sorting for aggregations, and the first MPNN with provable bi-Lipschitz (in expectation) guarantees.
Bi-I Bi-Lipschitz stability An alternative bi- bi-Lipschitz embedding for multisets was suggested in CChiill al. 2024a). This embedding has higher computational complexity then sort based embedding. Some additional examples of recent works on bi- bi-Lipschitz embeddings include (Balan & I'suukanis/ 2023, Cahill et al. 22244a 2020). (Upper) Lipschitz stability graph neural networks from a spectral perspective is discussed in Gama et al. 2020); Pfrommer et al. (2021).
We note that (Böker et al. 2023) does provide lower and upper stability estimates for MPNNs with respect to a WL metric. These stability estimates are in é sense, which do not rule out arbitrarily bad Hölder exponents. Moreover, they only consider graphs without node features. On the other hand, their analysis is more general in that they consider graphs of arbitrary size, and their graphon limit. In an additional recent work, Xu et al. (2023) introduced a GNN designed to be bi-Lipschitz with respect to weighted inner product space. Their approach, however, is limited to scenarios with a fixed graph topology, where only scalar node features vary. This fixed topology justifies the use of the weighted inner product space, which does not incorporate information about the graph structure.
SUMMARY AND LIMITATIONS
We presented expected Hölder stability analysis for functions based ReL.U summation, smooth activation summation, adaptive ReLU, and sorting. Our theoretical and empirical results suggest SortMPNN as a promising alternative to traditional sum-based MPNNs.
A computational limitation of SortMPNN is that it requires prior knowledge of maximal multiset sizes for augmentation. We believe that future work will reveal ways of achieving Lewer-Lipschitz architectures without augmentation. Other avenues of future work include analyzing Hölder properties with respect to other graph metrics other than TMD, and resolving some questions we left open such as upper bounds for the Hölder exponents of smooth activations.
Acknowledgements: N.D. and Y.D. are supported by Israeli Science Foundation grant no. 272/23. We thank Haggai Maron and Guy Bar-Shalom for their useful insights and assistance.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Boris Alexeev, Jameson Cahill, and Dustin G Mixon. Full spark frames. Journal of Fourier Analysis and Applications, 18:1 1s:1167-119,, 2012.
Tal Amir, Steven J. Gortle,, Ilai Avni, Ravina Ravina, and Nadav Dym. Neural injective functions for multisets, measures and graphs via finite witness theorem. In shirth- Conference on Neural Information Processing Systems, 2023. http:: httss::/oppereeveiee http:/ewwweee.ooroooeeeeee
Id=TolpgmCeMe
Radu Balan.
Stability theorems for fourier frames and wavelet riesz bases. Journal of Fourier
Analysis and applications, 3:499-504, 1997.
Radu Balan and Efstratios Tsoukanis. G-invariant representations using coorbits: Bi-lipschitz
properties, 2023.
Radu Balan, Naveed Haghani, and Maneesh Singh. Permutation invariant representations with applications to graph deep learning. arXiv preprint wrXiv:2003.07546, 2022.
Afonso S Bandeira, Jameson Cahill, Dustin G Mixon, and Aaron A Nelson. Saving phase: Injectivity and stability for phase retrieval. Applied and Computational Harmonic Analysis, 37(1):106-12) 2014.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamunugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL serum?idd-FboQaR..
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL httph: http://wwwwwanc. com/ Software available from wandb.com.
Jan Böker. Graph similarity and homomorphism densities. arXiv preprint arXiv:2104. 14213, 2021.
Jan Böker, Ron Levie, Ningyuan Teresa Huang, Soledad Villar, and Christopher Morris. Fine-grained expressivity of graph neural networks. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URLhtttst / hww.r//wwwew..eet/ou.ueeee.....
Fedor Borisyuk, Shihai He, Yunbo Ouyang, Morteza Ramezani, Peng Du, Xiaochen Hou, Chengming Jiang, Nitin Pasumarthy, Priya Bannur, Birjodh Tiwana, Ping Liu, Siddharth Dangi Daqi Sun, Zhoutao Pei, Xiao Shi, Sirou Zhu, Qianqi Shen, Kuang-Hsuan Lee, David Stein, Baolei Li, Haichao Wei, Amol Ghoting, and Souvik Ghosh. Lignn: Graph neural networks at linkedin, 2024.
César Bravo, Alexander Kozachinskiy, and Cristóbal Rojas. On dimensionality of feature vectors in mpnns. arXiv preprint 2rXiv:2402.03366, 2024.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets, 2018.
Jameson Cahill, Andres Contreras, and Andres Contreras- Complete set of translation invariant measurements with lipschitz bounds. Applied and Computational Harmonic Analysis, 49(2): 521-539, 2020.
Jameson Cahill, Joseph W. Iverson, and Dustin G. Mixon. Towards bilipschitz invariant theory, 2024a.
Jameson Cahill, Joseph W Iverson, and Dustin G Mixon. Towards a bilipschitz invariant theory. Applied and Computational Harmonic Analysis, 72:101669, 2024b.
Jameson Cahill, Joseph W Iverson. Dustin G Mixon, and Daniel Packer. Group-invariant max filtering. Foundations of Computational Mathematics, pp. 1-38, 2024c.
Samantha Chen, Sunhyuk Lim, Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Weisfeiler- lehman meets 3416. PMLR, 2022.
In International Conference on Machine Learning, pp. 3371-
11

---

Published as a conference paper at ICLR 2025
Cheng Cheng, Ingrid Daubechies, Nadav Dym, and Jianfeng Lu. Stable phase retrieval from locally stable and conditionally connected measurements. Applied and Computational Harmonic Analysis, 55:440-465, 2021.
Ching-Yao Chuang and Stefanie Jegelka. Tree mover's distance: Bridging graph metrics and stability of graph neural networks. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https
//openreview net mett/orummiddOhe 9hwiP52R
David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Ipann Iparraguire, Rafael othy Hirzel, Alán Aspuru- Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 2, NIPS' 15, pp. 2224-2232, Cambridge, MA, USA, 2015. MIT Press.
Tim-
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022a. URL
id==ITJnnGGph
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Informa- lion Processing Systems, volume 35, pp. 22326-22340. Curran Associates, Inc., 2022b.
URL
8c3 8:66682055577766654444472----e.0
and Benchmarks
pdf
Nadav Dym and Steven J. Gortler. Low dimensional invariant embeddings for universal geometric learning, 2023.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Transactions on Signal Processing, 68:5680-5695, 2020. doi: 10. 00.1109//PP.2220.302666
Chen Gao, Yu Zheng, Nian Li, Yinfeng Li, Yingrong Qin, Jinghua Piao, Yuhan Quan, Jianxin Chang, Depeng Jin, Xiangnan He, and Yong Li. survey of graph neural networks for recommender systems: Challenges, methods, and directions, 2023.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George F. Dahl. Neural message passing for quantum chemistry. International Conference on Machine Learning, 2017.
httptttts//pppt http:////ppsssaaaiiiioemma
semant iestmaaniiscchhlaa org/ wttgg//ropss::://000 96659943
Martin Grohe. word2vee, node2vec, graph2vec, x2vec: Towards theory of vector embeddings of structured data. In Proceedings of the 39th ACM SIGMOD- SIGACT-SIGAL Symposium on Principles of Database Systems, pp- 1-16, 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL
files/ files/paper /
Weihua Hu*, Bowen Liu*, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learn- ing Representations, 2020. URL U htt.:/rrwweeeeeeeeeeooooooeiiaia
Ningyuan Huang and Soledad Villar. A short tutorial on the weisfeiler-lehman test and its vari- ants. ICASSP 2021- 2021 JEEE International Conference on Acoustics, Speech and Signal Pro- cessing (ICASSP), pp. 5533,8837, 2021. URL httph:ttt//aatt semanticscholat /rg/ CorpusTD:2357805111
12

---

Published as a conference paper at ICLR 2025
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. networs.. In International Conference on Learning Representations, 2017. URLpattps://ppeeevviie
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Inno- vative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January AAAI Press, 2019. doi: 10. 1609/AAAALV3333133330144444
27 - February 1, 2019, pp. |Rt /owi org. / 10. 0. 609 aaaiiaai.... v33101 33014602
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs, 2020.
Christopher Morris, Nadav Dym, Haggai Maron, ismail Ilkan Ceylan, Fabrizio Frasca, Ron Levie, Derek Lim, Michael Bronstein, Martin Grohe, and Stefanie Jegelka. Future directions in founda- tions of graph machine learning, 2024.
Samuel Pfrommer, Alejandro Ribeiro, and Fernando Gama. Discriminability of single-layer graph neural networks. pp. 8508-8512, 06 2021. doi: 10. 10.10099/SS 2021 99944911333
Kristof T. Schütt, Farhad Arbabzadah, Stefan Chmicla, Klaus R. Müller, and Alexandre Tkatchenko. Quantum-chemics insights from deep tensor neural networks. Nature Communications, 8(1), January 2017. ISSN 2041-1723. doi: 20.1038//comms1133 URL http:://xx:: dww.orgi..rgo.ooo. 11010038 comms 3890
Puoya Tabaghi and Yusu Wang. Universal representation of commutatioo-invariinn functions on vectors and tensors. In Claire Vernade and Daniel Hsu (eds.), Proceedings of The 35th International Conference on Algorithmic Learning Theory, volume 237 Proceedings of Machine Learning mlr
Research, pp. 1134-1187, 1187. PMLR, 25-22 28 Feb 2024. URL https::/pprcceddiiii
Batass/233//abbaghhi
html
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe. Where did the gap go? reassessing the long-range graph benchmark, 2023.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL htt.ttppss/pppeeeevee...... wwt.:/peeevieeeooooo wttp::ntttttotmmmtttee...om
Edward Wagstaff, Fabian B. Fuchs, Martin Engelcke, Ingmar Posner, and Michael A. Osborne. On the limitations of representing functions on sets. International Conference on Machine Learning, 2019. AtLhttps:0 //tpi/appaaa///////// http::///aaaaaaaaaaaaaeaaaa.. www.mnannncccoolaa.. wwtp:ooraaII...1222222222222
Peihao Wang. Shenghao Yang. Shu Li, Zhangyang Wang, and Pan Li. Polynomial width is sufficient for set representation with sigh--imensional features. In The Twelfth International Conference on Learning Representatiinns, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. net/forrtee Satrrumiid=34STTseeeee
URL htt.ps:://ppeeeeiiiiiee
Boris Weisfeiler and AA Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno- Techiihe-Tehnn Informatsia, 2(9):12-16. 1968.
Charles Xu, Laney Goldman, Valentina Guo, Benjamin Ballander-Bodies Maedee Trank Benn-Greene,, Ian Adelstein, Edward De Brouwer, Rex Ying, Smita Krishnaswamy, and Michael Perlmutter. net: Classifying and analyzing signals on graphs, 2023. URL
www.://wwwwwgrraa/ao// /2310
17579
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 5453-540 5462. PMLR, 10-15 Jul 2018. URL ht..:tt:::// http:::://pppoeedippepm igs. ml www.prrsssveee verressvv0/ae 18.. html
13

---

Published as a conference paper at ICLR 2025
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. URL https
//openreview.ot net/
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, Februury 2-7, 2018, pp. 4438 4445. AAAI Press, 2018. doi: 10. N0.1609AAAAL.322..1111. URL
https:
/ /doi org.rr/// 10. a09/aaai.... v3211 11782
Yan Zhang, Jonathon Hare, and Adam Prügel-Bennett FSPool: Learning set representations with 01t.//1910000009555 02795
featurewise sort pooling. 2019. /tt./t/sss///aaxv.ooo//////////a
A DEFINITIONS AND NOTATION
The following definitions and notation are used throughout the appendices.
We use the function F(z, x', w) = p... (x, x', w) to denote
dy (f w) f(z' F(x, x', w)
dx dx
We call pair of multisets balanced, if the number of elements they contain equal, and otherwise we call them unbalanced.
B HÖLDER STABILITY IN EXPECTATION PROPERTIES
In this section we fill in the details some properties of lower-Hölder in expectation functions, which were discussed in Subsection 2.1
B.
REDUCING VARIANCE BY AVERAGING
Given N N, we can extend f(;; w) X W + Y to new parametric function fN W.N YN defined as
fN (a;; wi...., WN) = [f w1)..... f(x wN)]
where the measure W is the product measure, and the distance we take Y is
N
1/n
dyy (lvi..., uNl. W...... v'xl)
Σ n=1
d(yn: vnn
N
The function Fx corresponding this choice of SN
dyw (fN w w), (x', w))
Fz x', w)
dx dx(2, (z,
x')
N Σ n=1
d(f(z,
dx(z,x))
N
F(z,2', ww)
N
Thus Fy is the average of N independent copies of F, which implics that for all x + x' the random variable Fx x', w) has the same expectation F, and its standard deviation is uniformly bounded
14

---

Published as a conference paper at ICLR 2025
by o/ 8/VN, where is bound the standard deviation of F(x, x', w) which is uniform in x' (assuming that such a bound exists). In particular, this means that for any æ, x', not only will the expectation of Fvy (z, z', w) be bounded by from below by mP, but also N goes to infinity the probability of FN (2t, x', w) being larger than m² will go to one.
B.2 BOUNDEDNESS ASSUMPTIONS
In the scenarios we consider in this paper the metric spaces are bounded. Assume 0 < a < 8, and the distances between any two elements J., x' in metric space X are bounded by some constant B, then
d(x,=') B
d x') B
d(z, 1
I B
B
In other words, in bounded metric spaces, up constant, increasing the exponent decreases the value. It follows that a parametric functions which a lower Hölder in expectation also 3 lower Hölder in expectation.
B.3 COMPOSITION
In this section discuss what happens when compose two functions f(x; w) X W H Y and g(y; x V + Z to get new parametric function
g f(z; v) = w);
Lemma B.1. Given two parametric functions [(xw)) X x + Y and g(y X + Z which are and B lower Hölder in expectation with 3 2 1, then g is a B lower Hölder in expectation. Similarly, if f. 9 are uniformly upper Lipschitz, then f o g is uniformly upper Lipschitz.
Proof. We omit the proof for uniform upper Lipschitz, and prove only the more chal- lenging case of lower-Hölder in expectation. We have that for strictly positive my mg- Emwull ( dy (f(aaw) f(2/wo)) yol my and Em,,l de(a(u jol 2 mg. from which we con- clude
dx(2""")
E E d2 (2( (2
}rl
dx(r,r')0
independeett
dz (zlol((;;))))) g p
dx dx(x
dy (1( dx(2 dy (y(f(r;;) f(rk lr Bonyll dz(o(f(x; w), v), u) g(f U)) prld dy (f( w), f(';;
dz dxlol[(z; w) 9)) v)) dy f(r)
) dd
dx dx(xxx))
(f( f(z::))) }r mydu dx(axx')a.
mg Ew dr (f(x;;) {('; 1 (x(
my (Ewnylt dy (f(z; (( jmy
x'
2 mg m
Where (*) is true by Jensen's inequality, since (f ((2/ww)) (w)) ) is non negative, and Φ R U dx dx(x,
{0) + IR, (() = is convex for 3 2 1
15

---

Published as a conference paper at ICLR 2025
C
MULTISET EMBEDDINGS ANALYSIS PROOFS
The following are the proofs of the claims regarding the exponent of Hölder stability in expectation from section 3
Before stating and proving the relevant claims, we will present some lemmas that will be used throughout this section and those that follow.
We first state the well known property norm equivalence on finite dimensional normed spaces Lemma C.1. Ler I P.q S co and d E N. There exists Cp.q.d' > 0 s.t. for any E Rd
||ll 2 Cp.q.d" ||olla
In particular, this means that Lemma C.2. Ler S p.q S do and S R There exists Cp.g.d s.t. for any X, E (S)
w (x, Y) 2 Cp.q.d (
Proof.
1/p
W( (X,)) =
min TES..
[P(r)(z))) P(e)())rs)
==1
Cp.i,
min TESm
((())(z)) (es(()>cssle)
CA
(p())(z))) - P(o)(W)osll
Cp.1,d Cpiqid
min rES jul
C
Cp.id Cp.qid Cg.ld"
min TES,
- -
Cp.1d Cp.q.d Cg,idd' (X,)
The upper bound can be proven in the same manner.
Now that we equipped with the above lemmas, we begin by proving for smooth functions.
C.I SUMMING OVER A SMOOTII ACTIVATION
Theorem 3.3, Assume (n, d. p. 22,2) satisfy our standing assumptions, o R + has n continuous derivatives, and a ~ Srd b [-B T-B, B). the function m b) is lower-Hölder in expectation. then a 2 n.
Proof. It sufficient prove the claim in the case where
Since a is n times continuously differentiable, there exists some constant C such that
8m
at b) s C, V(, [-1, S x B).
am
Now, let f be any function with n continuous derivatives and (n) (t) < C for all t E [-1, For 1-" denote Fxx) >m fxx). (when f(t) (at + b) have F(x) = my m= b)).
By Taylor's approximation of around 0, there exists points Cj.
E (-1,1) such that
n
("(0)
(n-1) 1)
F(x) Σ
f(0) f())z
(n 1)! x
2
("(
f(n-1) (0)
=nf(0) + (0)
+
x
2
(n 1)! ==1
n!
i=1
i=
1=1
16

---

To conclude this argument, we note that there always exist æ, E IR" which are not identical to permutation, but have the same first n moments. This because is known that no mapping from (-1, 1)" to R" and in particular the mapping which takes vector of length to its first n moments, cannot be injective, up permutations (Wagstaff et al., 2019). To ensure that x, y are in Published as a conference paper at ICLR 2025
It follows that if y are two vectors which not the same, even up permutation, but their first
7 1 moments are identical, then for every e E (0, 1), the vectors ex and ey will also have the same
moments, and so there exist cI...... Cn. d1, ................................ d, in (-1, such that
f(m) (c.)
f(() (d.) 2
2n
[ex)) F(ey) e"
Ce"
n! In contrast, the Wasserstein distance between ex and ey scales like e: (ex, ey) = Wplez, ey) = p (1)
n!
nz.
follows that for all a < n, all parameters w = (a, b) E sa-1 x 1-BB, B, B), and all e E (0,
my (Ex; w) (ey w) CW, y) y)- 2n (ex, ey)
e (n-o)p
n!
Taking the expectation over the parameters w the left hand side, we get the same inequality. Taking the limit - 0, we obtain
mo (EEr; w.) mo (ey,,
CWp((,, 2n (n-a)p - 0
E
(erc cy)
n!
from which we deduce that my not lower-Hölder in expectation.
1" we can scale both vectors by sufficiently small positive number. In the next subsection we discuss constructive method for producing pairs of sets with n equal moments.
C.2 CREATING SETS WITH BQUAL MOMENTS
In the proof of theorem 3.3 we explained that for every natural there exists pairs of vectors I, I which are not identical, up to permutation, but have the same first - moments. We now give constructive algorithm to construct such pairs for n which is power of 2, that is, n = 2 for some natural This algorithm was used to produce figure in the main text.
Our algorithm operates by recursion k. For 1, our goal is to find pair of vectors x 20), ()() of length 2 = 2, whose first 2 - 1 = moments are equal. We can choose for example
|-, y ()) = [-2,
Now, assume that for a given we have pair of vectors x = (*) and y = (*) of length n = 2* which are not identical, up permutation, but whose first 2* moments identical. We then perform the following three steps:
step 1:
We translate all coordinates of ir and y by the number i, which take to be the minimum of all coordinates in r and We thus get new pair of vectors
x' [2] ,,..., Fy, (). y [ l,... Xin
whose coordinates are all non- These vectors are still distinct, even up to permutation, and have the same first n 1 2* moments.
step 2: We take the root of the non-negative entries both vectors, to get new vectors
x" = IV V IV=....... V
These two vectors distinct, up permutations, and they agree the even moments 2,4,...,24 2(n 1).
step 3: Finally, we define new pair of vectors of cardinality 2n 2k+1
(k+1) --r"",="" (l++1) "-y""," y²]
These two new vectors are still distinct up to permutations. There even moments up to order 2(n - 1) still identical. Moreover, all odd moments of both vectors zero, and hence identical. In particular, the two vectors have the same moments of order .,,, 1), 2n 1, which what wanted.
17

---

Published as a conference paper at ICLR 2025
C.3 SORTING
Our goal in this subsection is proving
Theorem 3.4. For (n, d, p, S2, z) satisfying our standing assumptions. Assume that a S and
b~5m Sm-1 Then Sz(:; a, b) is uniformly upper Lipschitz and lower Lipschitz in expectation.
Recall that Sy defined via
S. (X -b. sort(a P(=)
Once P(s) is applied, we can think of S₂ operating multisets with exactly elements, coming from the domain S2 [z). The function S. is then a composition of parametric functions Lo where
L(y;b) b-y
(4)
and
s(X: sort(a x)
(5)
By the rules of composition (Lemma B.1 is sufficient to show that both functions are uniformly Lipschitz, and lower- Lewee-Lipschiz in expectation.
We first show for
Lemma C.3. For every 2 1, the function L R" x Sn-1 + R is uniformly upper-Lipschir, and lower Lipschitz in expectation.
Proof. Uniformly upper Lipschitz For every b E S and nr x' E R we have, using Cauchy- Schwarz,
(I;:b) L(x':b) = lb (z 2'),1 || 2'|l
so for all we have a Lipschitz constant of
Lower Lipsehitz in expectation For every + x' in I we have, due to lemma appropriate e
C.1
for the
En {
L(x;; b) -((x))))( | x'
L(x; b) - L(x'; b)
P
2 cº Ep-
c x' 22
x x'
= c² E
1b.
1
|| x ||
= = En
[|b e1
0 >
where the last equality is because the distribution rotational invariant.
We now prove for s
Lemma C.4. Let d, n.P be natural numbers. Let be defined in (5), then is uniformly upper Lipschitz, and lower Lipschitz in expectation. (here, the domain of is the space (=)( of multisets with elements in compact set Q C Rdd, endowed with the W, metric. is drawn uniformly from gd-1 and the metric on the output of is the Ép distance).
Proof. Due to norm equivalence as stated in lemma C.1 it is sufficient to prove the claim when p 2.
Fix some balanced multisets X o Y. Let or be permutation which minimizes Σj= || - 9-0 112 over all S,. Then for every E Sd-1 1 we have, using Cauchy-Schwarc and norm equivalence
18

---

Published as a conference paper at ICLR 2025
[|x(:a) - s(Y;))l ||sort(a" x) sort(aa 1)
min TES
aa 2j a" wーのn
j=1
a Ij at زoiر) 1
|| yo(iill
"
SC
Σ
|,a yo( ll2
W))
Concluding s is uniformly upper Lipschitz.
In addition, we also have that for large enough N, the function sx(::o a) (concatenation of s N times. divided by 1/N) will be lower Lipschitz for Lebesgue almost every S as proved in (Balan al., 2022). In particular, it follows that sN lower Lipschitz in expectation. As discussed in Subsection B.1 this implies that is lower Lipschitz in expectation as well.
C.4 ANALYZING RELU
Theorem 3.1. For (n,
satisfying our standing assumptions, assume that St-1 and b [-B, B). Then ReLU (1,, b) is uniformly Lipschitz. Moreover.
1. mRezo(ça, is not lower-Hölder in expectation for any <
p+1 P
2. If [|]] < B for all x E Q, then mRaww a, b) is p+l lower-Hölder in expectation.
Proof. We divide the proof into three parts, in accordance with the three parts of the theorem.
Part 1: Uniform Lipschitz We first prove uniform Lipschitz bound for all balanced multisets Y, of cardinality S n. Denote X P(=) X' (Y)) Then for every permutation 7 E S.,
m (Y; Y;aab) b) MRLLU (Y': (Y';a,)) menLy (X; a. b) mNaLu (X'; a,,b) b)
ReLU(ar, -ReLU b))
(axz - 6) (aat'()) b)1
la . (x, x
||||2||>; 21
| 22
where (+) is because ReLU is Lipschitz with constant 1, and (*#) is from Cauchy-Schwards
19

---

Published as a conference paper at ICLR 2025
Since the inequality we obtain holds for all permutations permutations to obtain that
take the minimum over all
MenLu (Y; ;;, mn. & Wi (xX
X') =
To address multisets Y, Y of different sizes, we first note that since the elements the multisets are in f2 and the parameters a, come from compact set, there exists some constant M > 0 such that
RmeLL aY; a,
RELL (Y; a, b) S M.
On the other hand, for all Y, Y' of different sizes, we will always have that
WF(Y.Y) 2 dist(2, > 0
therefore
WF(Y M WI(YY')
(Y: m netu (Y'; ; M W dist(z,
Combining this with our bound for multisets of equal cardinality, we see that mRaL is uniformly Lipschitz with constant max(1, 1, aist(=,0)
Part 2: Lower bound on expected Hölder exponent
We show that M.LU is not 3 lower-Hölder in expectation for all B < (p 1)/p.
Let X be some matrix in Q" whose first two columns are the same 21 = Z2. Let g be a vector with unit norm. For every 0 define
X. = [x] eq, Ti + Eq, T3, ..n
is not difficult to see that for all small enough we have that W1 (X X) 2e. On the other hand, for every fixed E Sd-1 and b E [-B, B] we have that, denoting = a and 8 = lea g/. we have
(X;au(X;a,b) - mRcLU (X 2ReLU(a x1 - b) ReLU(a (x1 cq) b)
ReI.U(((-x)) + eq) - b)
2ReLU(y - [ReLU(y + b) + ReLU - 5 b)]
Note that i y + then the expression above will be zero because all arguments of the ReLUS
will be negative, and b < y then the expression above will also be zero because the arguments of all ReLUs will be positive so that we obtain
2ReLU(y b) [ReLU(y + 5 b) ReLU(y - --b)) 2(y b) lv 6 -
0
Thus this expression will not vanish only i E [y 6, + 5) which is an interval of diameter 28 < 2c. For each b in this interval we have, since ReLU is 1-Lipschitz, that
2ReLU(y b) - [ReLU(y + 5- 6) + ReLU(y 8 - b)] S
ReLU(y - 6) ReLU(y
6)1 + |ReLU(y - 6) ReLUUy - b)] 8-b)
26
So that in total the expectation for fixed over all b, is bounded by
1
E Ba-[-B.n mer
mR..u b)l" < (2e) 8.y 67 -
(2c)
2B
Which implies the same bound when taking the expectation over and b. Thus overall we obtain for all < (p 1)/p that
|MRLLU (X; (X;
(2e)p+2
2011
Ea,b
p+1- 3.p %
Wi(X,X.J0
2B 28/pe0p
2B2
While if MiLLLU 3 lower-Hölder in expectation this expression should have been uniformly bounded away from zero.
Part 3: lower-Hölder in expectation Next show that MELU is (p + 1)/p lower-Hölder in expectation. We first consider the restriction of MALU to the subspace of S (22 which contains only multisets of cardinality exactly We denote this subspace by S=n (2). In this case, realize
20

---

Published as a conference paper at ICLR 2025
MRLLU the composition of two functions: the functions a(X;a) sort(a" X) from Lemma C.4
and the function ((;;b) b) = E, ReLU(z; - b) Note that indeed f(X; b) = (q o s) b). Since we already know that is lower Lipschitz in expectation, it is sufficient to show that q is (p + 1)/p lower-Hölder in expectation, due to the theorem on composition B.3
Let us denote B = max{[|=|||
x E 2t. By assumption B B.
Note that the domain of is contained in
B {o R-I
B S x1 S S
In B).
Since the 2-norm and co-norm equivalent on R" C.I to address the case of balanced multisets it is sufficient to prove
Lemma C.5. Let > O,B 0 and n be natural number. Let (6(x)) q(2; b) be the function described previously, defined on the domain
SAA.B = E IR
A x1 .... In S B
There is a constant
Cn.p
8n(Be B4 A)
such that for all x, y E S4A.
(b-AA./l9(()) 96(y)p Cn yllst
Proof. Let F y be pair in [) Let s be an index for which lys v.s |1y x 3o without
loss of generality assume that ys > T., For every b E R we denote A(b) (b) (x(z). Let t be
the smallest integer such that 2; 2 ys- Note that t > s. We now have
Ayy+)
[ReLU(V - Uv) ReLUU v.)] = E(vs Ua) Σ
> (ay - yy))
j28
121
Σ (yk- Uv) + Σ (yg xz;)
=
kck<t
12
Now
A(x,) Σ
ReLU(y Iz) + (ys Iz) + Σ
1(y5 -x,) (xx x,)]
i<s
1os
2 (ye xx.) + Σ (g) - zzj)
128
(ye - x.)) +
Σ (ykk - Ua)) +
Σ
(ye - xk) + Σ
(Us xz))
sckkt
scket
12t
2 (y. - x.) + Σ (yk- - yya) +
sck<t
J2t
(y, x..) + AV++
We deduce that A(xx) (gy) 2 Vs Fas and therefore at least one of A(x,)) and |)(y)) is
larger than Ne=2, so we found some bu for which |A(bu)] > Me- Next, note that since A is sum of 2n ReLU functions which are all 1-Lipschitz, A is (2m) Lipschitz. Therefore if b is such that
lb bal Bn (y= x.)) then
ab) (bbo) < (b)) A(bo) 2nd
3/ Fs
implying that Abb) > No u0 Thus
Yo - Ie
8
Eg 9o (v) (0())) (b)A 2 p(bbll
bol < <67-
>
xzI
x
4
(B A)4
1
8n(B- ( A)4p Us x.. p+1
1 x
p+1
8n B
A)40
21

---

Published as a conference paper at ICLR 2025
Now let consider the case of unbalanced multisets Y. in (Q). Our goal will be to show that the distance between all unbalanced multisets is uniformly bounded from below away from zero.
Y and y' multiset obtained from adding elements with value - B to y until it has Y clements. Similarly, denote x' P(-B) B) (v/). Note that since y and y' don't have the same number of elements, and all entries of y/ are in B', B'), we have that
For fixed S denote y
Y'. Denote I P(- (v), that is, is the
- - x' llo 2 B B'.
For all E [-B, B] we have that ReLU(- -b = O, and therefore, according to Lemma C.5 have
we
Eg (Y; - mi aY b) p= = Egloo(v) (6('')'
= (z) -
2 CapllI x' I'l 2 -n
BB)
We deduce that
En Ee.o MRELU (Y': 2 CB-BB
WF(XYY') p+1 WT
CB B'yP
C(I((Y
For appropriate constant C, where we use the fact that Wi is bounded from above. We have obtained a (p + 1)/p lower Hölder bound for both balanced and unbalanced multisets, and so we are done.
Adaptive ReLU
Theorem 3.2. For (n, d. p, 22,22 satisfying our standing assumptions, assume that a ~ Sd-1 and edapt.
t ~ [0, 11. Then the function MRRLU (g)( x S x [0, + E is uniformly Lipschitz and p+1 lower-Hölder in expectation. Moreover, when n 2 4, the function MRLL is not lower-Hölder P
in expectation for any < p+1
Proof. To prove this theorem, first recall the definition of MRLLU
m minffa .1...., }r M = max (a 21,...,a xr) xr b b= (1 t)m + LM
T ReLL (X: (x;a (r, m, M, ReLU(a - -b]
adapt
To begin with, we note that the case of unbalanced multisets is easy to deal with. There exists constants () < ===1 < C' such that, for every pair of unbalanced multisets Y,, and every choice of parameters a, f,
1 S
adapt ReLU (X; t) mRLLU (X; a, t) S C
The lower bound follows from the fact that the first coordinate of miteUU the cardinality of the sets. The upper bound follows from compactness. Similarly, the augmented Wasserstein distance between all unbalanced multisets in ( is uniformly bounded from above and below. This can be used to obtain both uniform upper Lispchitz bounds, and lower Hölder bounds, as discussed in previous proofs.
Thus, it is sufficient to prove uniform upper Lispchitz bounds, and lower Hölder bounds in expectation, for balanced multisets. Without loss of generality we can assume the balanced multisets both have maximal cardinality n. So we need to prove the claim on the space (S,.
adapt We write ReLU restricted to S=n,
composition
adapt MRLU (X; () = Q o s(X;a.))
where a( sort(a which is the uniformly upper Lipschitz, and lower Lipschitz in expectation function defined in Lemma C.4 and Q(x; is defined via
min m2in (21...., Fn), M
b= (1 1-)m + 1M
22

---

Published as a conference paper at ICLR 2025
and
Q(2;t) = [n, m, M,
ReLU(x; b)]
T2
As is is uniformly upper Lipschitz, and lower Lipschitz in expectation, is sufficient to show that Q is upper Lipchitz, and lower Hölder in expectation.
We note that since f is bounded, there exists some such that |||||| s B, Vz Ω and for this B we have that the image of is contained in
Ω Q B.B] = (a IR
-B x1
I In S B)
We can therefore think of B) as the domain of Q.
We begin with the upper Lipschitz bound. Let æ, y be vectors in B which we identify with multisets with n elements in R. Denote the maximum and minimum by M2 and my. Define the maximum and minimum of by My and my. Denote
(s, m, = ReLU(ss - [(1 t)m + tM)
Then for all [0, 1].
[10(x;t) Q(Y; S C= Q(Y:t)l1
= = (Im, - - + MM - M₁ +
plri, L, May Ms) Σ
Hlys L, my, My)l)
< C 1/mm - myl + IM4 M₂l +
x2s V1 + t(M Ms) + (1 +) - (my)l)
C. 1(mm= myl + IM MMl
(lr: Mil IM, M₂)1 + 1(m= -my))l)
< C (||æ ylloc + ||0 - 8/1o0 +
Σ 1=1
3 || - 811
= 5C || yll S 5CC*
|| -11pp
Where C, C" are the constants obtained from norm equivalence over R".
To obtain a Hölder lower bound, the idea of the proof is that for given balanced multisets y E R", we know from the analysis MRLLU that we can get lower-Hölder bound when considering biases going between
ma min(myy my) and M = max Mg My}
and then showing that the difference between this case and the function where the bias range depends on the maximum and minimum of the individual multisets æ, y. is proportional to the different between the minimum and maximum of and y, which also appear in Q. Indeed, since ReLU Lipschitz we have for every s, m, M, m, M in E and [0, that
(o(s, m, - 6(s t, m, M²) < t(M M) - (1 -1- tm - m) $ M|M M (1 t)lm ml S | M + |m mi
(6)
Next, to bound [QQ(;;t) t) Q(y: p. due to equivalence norms, it sufficient to bound [[Q(x; t) Qu: ()] We obtain
23

---

Published as a conference paper at ICLR 2025
[[((z;)) - Q(v: 1) = =
myl + IMM -Nyy
ol l, ma, M³)
Σ Mayir i, my, My)1
n
my
Mayl 1M Mayl + |may myl + |May Mag
pl L, Ma, M
Σ
@yys My, My)l
p(x t, may: May)
Σ
(( t, M2x Mæ)
n
i=1
( L, my: M2))
Σ
Dlyis Mays May)l
p(x+, t, may Ms)
Σ
Muvi L, Myg My)l
==1
triangle ineq.
2
Σ
pl t, May. May) - Σ o(xs, t, mzz Mx)
n
n1
V My. My)
Σ
o(yr, t, Mayg Mar)
(1 t, mzz Ms)
Σ
Blvis t, my: My)1
Σ o t, mzz. May) Σ
plvi, t, may: May)l
i=1
(a(;; (1 f)mzyu - (May) - 4(25 (1 - f) + (May)]
By Lemma C.5
we deduce that
Ex-(0_]](Q(;; Quy t)l 2 B Mayl (1;;;())
a(y; 6)1"
1
x lllt 16n B4" lly xx1ttt
8n4"(M may)
by invoking the equivalence of the infinity norm and norm are done.
Finally, we will show that, when n 2 4, adaptive ReLU cannot be o-Hölder for any a >> (p + 1)/p. This argument is essentially reduction to argument in the standard ReLU summation case. For simplicity notation we prove this for the case where d 1. Extending the argument to the d' 2 1 case is straightforward
For any c >> 0, consider the sets
X 10,0,1,-13, 11. X. f(e, -, 111
and note that
Next, we note that for all a in the zero dimensional unit circle {-1,1} we have that a X X,a X. Xx, and moreover, that and X, have the same number of elements. Therefore
1 Eg Elm adapt (X2: t) metAt (X; a, l)l 1 (-.. -RAbU-----))+RLUCC-C-- -
Next, we note, in previous arguments, that
ReLUU-e - b) + ReLU(c b) - 2RcLL( 0, vb $ c
ReLUU---- b) + ReLU(c- b) 2RRLL(-b)) < (2c), v
24

---

Published as a conference paper at ICLR 2025
Thus, if is is in [-c, and otherwise will be zero. The expectation this expression over b is thus bounded by e Piecing all this together, obtain for all (p 1)/p
c). which occurs with probability c, the expression above will be at most (2c)p,
Ea,t [ (X),a,)) - MeLU (R; (X;a,
adapt
1"
2P
48 20. = -8) 5
= 0.
S
X.)
adapt This shows that m ReLU not lower-Hölder in expectation.
Remark C.6. The last part of the proof above can be used to derive adversarial examples on which Relptive-ReLLU will have bad distortion: namely,
X K0,0,1,-1
X, -,,
On these examples, adaptive-ReLi RU and ReLU summation will both encounter high distortion. In contrast, the examples discussed in the main text, like
adapt Y KO,OB,Y, Y, [cc
one can verify directly that the expectation ReLU (Y', (Y',a, m (Y,a, a, I) scales linearly in eP. This is because the bias for these examples naturally is in the range [-,, where 'it can make difference', while in the X, X. example, the bias chosen from all of [-1, and its probability to land in the domain [] where 'it can make difference' scales like E.
We believe this gives good intuition for the reason why adaptive-ReLU is successful on many of the adversarial examples illustrated in the text, and also suggests how they can be changed that adaptive ReLU will fail: we simply need to take these examples and add to all multisets considered large positive and large negative element. An example of this idea is shown in Figure / where adaptive-Rel. RelLU is initially successful in a classification task based on adversarial examples (subplot (a)), but fails completely once large positive and negative element added (subplot (b)).
D LIPSCHITZ COMBINE OPERATIONS
In this section describe how to construct COMBINE functions which are both uniformly Lipschitz, and lower-Lipschizz in expectation. The input to these functions are pair of vectors ø1 31 with the metric || I|p + Ilya ll The output will be vector (or scalar), and the metric the output space will again be the p norm.
Our analysis covers four 2-tuple embeddings, all of which uniformly upper Lipschitz, and lower Lipschitz in expectation.
Theorem D.1. Let p > the following 2-tuple embeddings are all bi- bipsschhiitz in expectation with respect to 1p and the 2-tuple metric previously defined.
1. Linear combination: Given 2-tuple (x.,) y) Rdd TR and U[- D) define
f(z,y;a) = a a
2. Linear transform and sum: Given a 2-tuple (x. v) E Rk x RR, and A E Bixk whose rows are independently and uniformly sampled from Sk define
f(z, y: A) Ax +
3. Concatenation: This embedding concatenates the tuple entries, and has no parameters
fxx
y
4. Concat and project: Given () R& R' and 0 gh+1-1
f(r 0) =
25

---

Published as a conference paper at ICLR 2025
dim=32
dim=500
1T5um
2.0
1.20
dictortion
1.8
1.15
CP
1.6
1.10
1.05
300
1000 1000
embcd dimi
20000
Figure 4: Distortion of the 2-tuple embeddings function of input and embedding dimension. LC=linear combination, LTSum=linear transform and sum, CP=concat project, C=concatenation.
We note that the last method, concat and project, is the method used in the definition of SortMPNN in the main text. We also note that the first method, linear combination, is the method used in (Xu et al. 2019). Unlike the other methods, it requires the vectors x, y be of the same dimension.
In order to compare the proposed COMBINE functions which all share the bi-Lipschitz in expectation property, one could further explore separation quality by comparing the distortion defined by M m where M (m) is the upper (lower) Lipschitz in expectation bound. A lower distortion would indicate that the function doesn't 't change the input metric as much (possibly up to multiplication by some constant), resulting in high quality separation.
In figure 4. we plot the empirical distortion of the different COMBINE functions with varying input and embedding dimensions. The embedding dimension is controlled by stacking multiple instances of the functions with independent parameters. Note that concatenation isn't parametric and therefore we only have a single output dimension for it.
The experiment is run on 1, 000 different random tuple pairs {ax, y): (z, w) for each of the four input dimensions experimented with, where y, w E R_n_dim__ All random data vectors are sampled with entries drawn from the normal distribution. The empirical distortion is then computed by taking the largest empirical ratio M between the input and output distances and dividing it by the smallest ratio y between the input and output distances.
As in the figure, all proposed functions stabilize around constant value the embedding dimension increases. This value is the expected distortion on the experiment data. We can see that concat and project maintains low expected distortion across all settings, while linear combination has a higher expected distortion but not by much. Linear transform and sum seems to have higher expected distortion for lower input dimensions, but it improves with large input dimensions, matching concal and project distortion.
Another interesting result is that we can see that concal and project seems to have the highest variance of the three for most input dimensions, since the empirical distortion for low embedding dimensions higher than other functions in most cases.
Proof of Theorem D.1
Linear combination: Let vr, = E R y. w E RC We begin by proving that ʃ lower Lipschitz in expectation.
B.-cI- - f(z, wi a) [ =
x + - (a - w + +
EEnuUI-D a (xr 2) + (v - -=)l[]]
From norm equivalence C.I 3ei s.t.
2 61 Eanu -DD (x - 2) + (y - w)
Jensen's ineq.
C Ba-D (r 2) + (y w)
Eaa ||a (x =)]l + 11 w>]l
From norm equivalence
C.I 30z s.l.
2 Ci 02 (Pa-UI-D.P(lo]] ||(= =)II, 11(y w))lp)
26

---

Published as a conference paper at ICLR 2025
D ||(x 2)|1 + 11(y - w)lb)>
cI 02
DP ) (1l =2]1p> + 11 w)lb)
C2 mån(1,
For uniform upper Lipschitz bounds we have
(1, v) - f(z, w; a)lpp = II(a x + y) - (a w + +)11p
l| w|lp |y =|1,
max(1, (I]( - 2)1k + (1 w))l))
Linear transform and sum: We prove lower- Liwchh-ipschitzness in expectation. Let a, denote the i'th
row of A. Recall that for any 1 S S I, a, is drawn uniformly from 5 Let x, R y, w e R
E Eall (a,, yi A) f(z, w; A) EAllIA(s 2) + (y w) |3]
= EA
aa (x= - =2 + Σ ر0 wyl
Σ
Bo (x - -1 + Σ 1y wyl
i=1
i=1
From lemma
C.3
36 s.t.
Eall
(2, (z, yi A) f(z, wx A)l[ 2 n. ||0 =1B + 11g w
I 2|1p [18 w
Let us denote & =
E E Then
n n-b- b- || >| + lly w I
min(1, n. b) (1|z =1ß + 11y w(b)) min(1, n. b) 1111
From norm equivalence C.I
3c > 0
2 min((1 n b) || min(1, n b) c. (1|x 211p + 1ly wl|p)
Uniform upper Lipschitzness is straightforward to prove.
Concatenation: We show that this non- non-parametric function is bi-Lipschitz. Let E IR y, R.. |
Denote as before & = 1ly w
E 2 Then the distance difference in the output space is given
w|Ip
by (1 f(z, w) w)ll ||l||p while the difference in the input space given by
a - 2 + ly - w|Ip ||t||]-
The claim follows from equivalence of p norm and norm on I
C.I
Concat and project: The claim follows from the fact that the concatenation operation is bi-Lipschitz. and Lemma
E TREE MOVER'S DISTANCE
In this appendix section review the definition of the Tree Mover's Distance (TMD) from (Chuang & Jegelka 2022), which is the way we measures distances hetween graphs this paper.
We first review Wasserstein distances. Recall that if (X, D) is metric space, Ω X is subset, and is some point in X with dist(z, R)) > 0, then we can define the Wasserstein distance on the space of multisets consisting of elements in Ω via
Wi W Fn R. Lui.....
B. ........))
Σ D(Ig.VoO) rES.
min
The augmentation map on multisets of size S is defined
P(s) (f.1,....,,, x. (x1...., Tr, Tr+1 2.... F.n =
27

---

Published as a conference paper at ICLR 2025
and the augmented distance multisets of size up to is defined via
(x, = WD, (PE
We now return to define the TMD. We consider the space of graphs (9), consisting graphs with n nodes, with node features coming from a compact domain f2 _ R We also fix some E I2d Q. The TMD is defined using the notion of computation trees:
Definition E.1. (Computation Trees). Given a graph G = (V, E) with node features f Brev, let
T be the rooted tree with single node u, which is also the root of the tree, and node features Pe- For K E N+ let { be the depth-K computation tree of node v constructed by connecting the neighbors of the leaf nodes of T! (-1) to the tree. Each node is assigned the same node feature it had in the original graph G. The multiset of depth-K computation trees defined by G is denoted by T(() [T K) B BrEV. Additionally, for a tree T, with root denote by T, the multiset of subtrees that root at the descendants of r.
Definition E.2. (Blank Tree). A blank tree Tg is a tree (graph) that contains a single node and no edge, where the node feature is the blank vector 2.
Recall that by assumption, all node features will come from the compact set Q, and & E Q.
We now define the tree distance:
Definition E.3. (Tree Distance) The distance between two trees Ta To with features from Ω and E is defined recursively as
| x + W(CC) (Ta: || - æb11z
(Ta To) if otherwise
TD Tb)
where K denotes the maximal depth of the trees Ta and Tb. Definition E.4. (Tree Mover's Distance). Given two graphs, G, H and w. 2 the tree mover's distance is defined
TMD(K) H) =
W(T TD.1 (Té (K) ((K))
where T and TH K) denote the multiset of all depth K computational trees arising from the graphs G and H. respectively. We refer the reader to (Chuang & Jegelkal (2022) where they prove this is a pseudo-metric that fails distinguish only graphs which cannot be separated by K iterations of the WL test.
F MPNN HÖLDER PROOFS
In the main text we informally stated the following theorem
Theorem 4.1. (Uniformly Lipschitz MPNN embeddings, informal version) Let f Gga( + Rm be an MPNN with layers. If the functions used for the aggregation (f()) combine 1))0)) and readout all uniformly upper Lipschitz. then f is uniformly upper Lipschitz with respect to TMD In particular, ReluMPNN, SmoothMPNN, AdaptMPNN and SorMMPNN are all uniformly upper Lipschitz.
Before stating the formal theorem and proof, we will present an important lemma alongside some assumptions and notation that will be used throughout this section.
Lemma F.1. Let C Rdd be compact set and let GS) - Th be depth K MPNN such that all the aggregation (5kk, combine (y(h) and readout 1 are continuous. Let zı. & Sry where Sy is the set of all possible feature vectors after running k & K message passing layers. Then, for any
G E Ggn(A), e VG and for any p 2 there exist C 2 c > 0 such that
CDD((T (k), T.)) 2 1| - x (10 2 c. (
'Note the difference from the original definition in (Chungg & Jegelka 2022 is due to our choice to set the
depth weight I and using the Wasserstein which is equivalent optimal transport
28

---

Published as a conference paper at ICLR 2025
Proof. We begin by showing that O2 is compact.
Since the number of nodes graphs from Ggn (S2) is bounded, the set of all possible graph topologies, ic. pairs (V, E)) with at most n nodes, is finite. Let (V, E) be such fixed topology. For every k. the function f(a ((z)) f) mapping features Ω and parameters to new parameter x/ah is continuous since the aggregation and combine functions are continuous. Accordingly the image v, is compact, and therefore
2
U
V..
(1))
(V.E).VISR
is compact well. Therefore:
= inl || - 1p > 0
d == sup || zkelp
sEily
Additionally, since Ω is compact and 2 & Ω we can show recursively, starting from 1, that for all E (0..., K} and all trees k!k) E (T(k)
(g)
b: inf T ETEN ET
TD(T2,T(h))
TD(T,,T!*)) <
sup T ET (9)
Te.y (9) denotes the set of all possible height-k computation trees from Ggn( Therefore, NG E (9), v E Vg:
Where
d ( 2 d b d 1 b
a -TD(T.,T))
To conclude define C = 6: g.
d
Assumptions and notations As stated in the main text, we consider graphs with up to n nodes. We will also make the disjointness assumption: We assume previously that the initial features of the graphs all reside a compact set fi = Go S Rd. We denote by Ω4 the space of all possible features which can be obtained by the MPNN at question after & iteration, with any choice of parameters. This set also compact (see proof of F.T The disjointness assumptions is that the 'augmentation vector' 2g is not in 2g, for all h
K.
We define for O,.... K
xs
(k)
if (v.
and (())) 6,8 = T=
= T(k) if (v, E if Fotherwise
if oohherwise
For K we denote
(K)
(K)
if V
and ((K)
T(K)
if EVEV if otherwise
2K
if othhewuise
{
T.
We will also denote
(k)
and xe (K) = [1]] ......(K)) (K)
We state the full formal statement of the theorem:
Theorem E22. (Uniformly Lipschitz MPNN embeddings. full version) Let p 2 1 and K E N, Let
f : G.n (52 + R be a continuous MPNN with K message passing layers. Under the above assumptions F and given the following holdy for all < k < K:
29

---

Published as a conference paper at ICLR 2025
1. The aggregation, (8)), is uniformly upper Lipschitz w.r.t the augmented Wasserstein distance W(sh) on (nn(())).
2. The combine fumction ( is uniformly upper Lipschitz.
3. the readout function is uniformly upper Lipschitz w.r. the augmented Wasserstein distance W1 W on (9kk)))))
Then, there exist constants C1, C2 O such that
1. The node embeddings after k message passing layers are uniformly upper Lipschitz w.r.t. TD their depth i computation trees
|1 - 2!!11 12 I -
2. The graph embeddings are uniformly upper Lipschitz w.r.t TMD(K)
||cllobal cglobal
| C2 (GG-TMD(OGGG
Proof. Since we are proving for uniformly Lipschitz, we will allow ourselves to omit the parameters for ease of notation, as the proof holds for any set of parameters.
Proof of First Claim u, G. The proof will be by induction k. for k: 0, by definition
| x | TDP (
We now assume correctness for 1 and prove for k.
1. First, using the properties of ((()) and the induction hypothesis we get:
| (N((--)) (VT 11 Wo (2
(k-1)
WP W3 (1
(k-1) (k-1)) = cΦ eı min
x (,r(s))12)) 1b,)
yes.
Co c1 Cz( min TES,
10! x
(k-1)
(k-1)
u.7(s)
ind. hypothesis
F.I
TDP (T(k)) - U.s
Co C1 C2 C(k-1)
TD(T(k-) (,)r )
C6 C1 C2 C(k-1) C3(
cWP
TD,1 (T (1-(1-1)
1) gi(k-1)
Where -* == argmin,es.. En TD(T _ C1. C22 C3 are the relevant constants from the lemmas we used and e is the multiplication of all previous constants.
2. Next, we note that
(D(T(K-1) (irrk-)),T(k))))) < (
Since the depth k computation trees subtrees of the depth & computation trees.
30

---

Published as a conference paper at ICLR 2025
3. Next, using the properties of (,()), the induction hypothesis and the above get:
||=()/ (*x 11p = || (1) (x [R- 1) (NTA 12)) w. (x) / (NN
Scp. (11=!~ - 20!h 1 11 (A (0 (A1 ))
ind hypothesis
co (o--Cc--)) (T (11) 1) + (10 (N x6
Cy (Q T 1()-1)) cW TD, (1 (I!!t-)) _o, 11)
Gp (Ck=1) (k)k + 7D, (T.t T(ll"!l))
(T
cs ( (T T((i) - WTD. (T (T(h- D) Gp (( 2" TDD )
mor
Where o₁ is the relevant constant from norm equivalence, concluding the proof of the first claim.
Proof of Second Claim Let us denote the final message passing features corresponding to the (K) and the depth-K computation trees corresponding each node of G by T!K) Similarly, we denote the features corresponding to the nodes & by a!K) and the trees by ((k
nodes of G by x
Then, using the properties of 17 and first part of the theorem get
||
-globaal 1p
[|1((x?*))
1 (K) )
S SG (K)
(K)
Gn ei (x
(K)
x {(K) Gn ei
(min 7ES
|10: - (K)) 7())]l
8=1
S Go c1 C. (T (( (())
TD(T!K) ((K)
)/ ))
Co c 02
= C (M (G, G)P
Where (*) is the first claim and lemma F. are the relevant constants from norm equivalence and 7" argmin Es=1 TD(T
() (()
r(a) concluding the proof.
F.1 SORTMPNN
In the main text stated the informal theorem
Theorem 4.3. (informal) For any given W > 1,K 0, SorIMPNN with width W and depth K is lower Lipschitz in expectation with respect to (K),
We next state the theorem formally and present the proof.
Our results in this section hold for any number of MPNN iterations K, and any choice of 'widths' Wi...., WK+1- For simplicity we prove this for the apriori hardest case, W1 = = W K++ We will call this version of SortMPNN Min-SortMPNN.
Explicitly, Min-SortMPNN is defined by:
SortMPNN: For k- 1 1..., K
AGGREGATE: ((k) sort (a(k) -(--11))
COMBINE: 2!!)) = (kk) concat(x!! (k-1) (.))
Note that we omit the second inner product in the definition of Sn as it is superfluous: this inner- product would be subsumed by the following inner product with ((0) in the COMBINE function.
31

---

Published as a conference paper at ICLR 2025
The READOUT function is given by
READOUT cillball = b(K+1). sort (a(K+1),
)
We will denote by ((k) the concatenation all network parameters up to the creation of the node features (kk)) where g(0) is just an emppy vector". We denote all network parameters, including those used by the readout function by g(k+1), The distribution on each of the parameter vectors a(*), 3(*), ((()) is taken to be uniform on the unit sphere of the relevant dimension, as discussed the main text.
We will now state our theorem on lower Lipschitzness of thin-SonMPPN.
Theorem F.3. (lower Lipschitz SorMMPNN, formal) Under the above assumptions [F and given a(8), ((k) are distributed uniformly on the appropriate unit sphere, then for thin Monn-SorMMPNN with depth K the following holds:
The node embeddings after i message passing layers are lower Lipschitz in expectation w.t.t. TD their depth ic computation trees
x [|] 2 (D"( I.
2. The graph embeddings are lower Lipschitz in expectation w.r.t. (M 25lobal
+g [|]cSlobal
|p c2 TMD G)
For the proof of the theorem we will need the following simple but useful lemma Lemma F.4. Let D, N be natural numbers and p > Then there exists a positive 5 = 8(D, N.P) such that, for all N fixed vectors .1,..., NN in IRD
P aa E BeESSD SD-1 |a æ.. 2
Vi
N) 2 1/2
Proof of Lemma F.4 Due to equivalence of norms
C.I is sufficient prove the claim when p 2.
For every E SD-1 and 8 > 0, denote
Bly, 6) {a E SD-1 la-yl <5}
We note that for any fixed positive and y, s/ E SD-1, the probability of By, 5) and Bly', 5) will be the same, due the rotation invariance the uniform measure on SD-1, and the fact that if R is a rotation taking to y', then
E Bly, 5) iff Ja vl < 5 iff Ra Ryl < 6 iff Ra E B
We can therefore denote the probability of Bly, 5) by ps, and this definition does not depend on the choice of y. Next, note that ps is non-negative seuence converging monotonely to 0 as 5 - 0. Accordingly.we can choose some ón such that ps < IN
Now, assume we are given N fixed points in R., Without loss of generality we can assume the first M points are non-zero, and the last N M points zero. We then have
{a E sP-4 la x.l 2 81|2,112, Vi L...., N} P {a E DD
2
8//21112 Vi 1, I...., M)
P { a SD-11
la
Fi
8, Vi 1, L,..., M
||, 1|2
U B
I;
.6)
||x:11
M
2
Σ
B
Et
80)
|
1=1
M
2N
N
2N
32

---

Published as a conference paper at ICLR 2025
Using the lemma, prove the theorem:
Proof of Theorem F33 In general, to show that a function f X x W + Y is lower-Lipschitz in expectation, suffices show that there exist ó, > 0 such that for all 2 22 E X, the probability of the set {w E W dx (x1 (82) > E} is larger than We will use this alternative requirement in the proof of both parts of the theorem.
Proof of First Claim For case of notation, we will use throughout this proof to denote W W and WP( = W (..)
TD11
prove the claim induction on k. For we have equality
| (0) 1 = TDP
We now assume correctness for h 1 and prove for k. Now note that
1. With probability of at least Pk-1 on g(k-1), we know that for all nodes u, v
||=!(-11 1) x 11 (T 1(ttt)))))))))
2. Once ((x is fixed, and all features x (k-1) are determined, we can use Lemma F.4 to show that with an appropriate > 0 and probability at least 1/2 on (k),
[a( (x m)1 2 8|12 vll
for all x, in the set (xt boev U Jz It follows that, with probability 1/2px-1 on (a()), o(k-1))
[co(0) c0 1/ = ||sort (a(t), x!! 1) sort (alt) 2(6._11) 11
(k) (k-1) (
min TES
min rES
[
(k-1)
0,8
x u,7(s) 11
8 CP min rES,
(k-1)
x (8-112 li
C CR
min TD" (1(k-), T(tTt)))
TES,
min TD(T(k-1) T(b-1)) 7 TES.
2 CCC
= cr.1 CP. (T.(k)) (0--1,TTkk-) (k-1))
where in the last equation we used Cx.1 to denote the product of all constants appearing previously. (*) is the induction hypothesis and lemma
(k) 3. Once (a(*), ((k-1)) determined, we know that Ce and _ for an appropriate positive 8', we know that with probability of at least 1/2 d(() and thus
(k-1) are determined. Thus,
33

---

Published as a conference paper at ICLR 2025
with probability of at least Pk Ph-1/4 on B()) = (d (a.) _.(k-11), 1),, we have
(x
1p (d concat(x!!-1) - Fa (x+-1) ddih )1
(8')² [cooncal(x) (x Ix 1)- co
(k) )|
2 (8 (Im!/- x/ 1) |b + |((( v 11
P 1T 1)) (8 ck,,)
ck W (T(l--) TT(
(8 min
Ck.1 / | + W (T (- T((k
C(8') minfa- c.,1 (1=!)) 1 + W W -()) p
=cD )
where in the last equation we used C to denote all constants incurred up to this step. In the inequality (*) we used equivalence of norms in euclidean space, with an appropriate constant C.
This concludes the proof of the first part of the theorem.
Proof of Second Claim Let us denote the final message passing features corresponding to the nodes of G by xe (K) and the depth-K computation trees corresponding each node of G by T!
Similarly, we denote the features corresponding to the nodes of G by {(k) and the trees by { By
applying the first part of the theorem (to the disjoint union of the graphs and G), we know that with probablity of least pk on the parameters 0k, have that
x(KKpp P N cx (DP((T A(K)
Once 0K is fixed, all node features zo and (k(k) are determined. By Lemma F4 we have for an appropriate 8 that, with probablity of at least 1/2 on a (K+1),
(a(K+1)_ (a/(k) {({))] 2 ō1|={K) =:{)] ll2, Vu, E [n].
It follows that for an appropriate 8', with probability of at least pz/4 on 0k41 = (b(K+1), (k++)), 0x)
latlobal cglobalpp
= (1), (sort (a(k+)). . ..(3)) -oort (a(k+)) (((++)).(k))) s!())
(al (((K+1) x (1))) soot (a(k+t), . so(1)) 1|
2 8'ol|
8 min
la (K+1) x((K) a((+1)) [(()
TES
2 (8 . 8''²" min
[1x (K)
[x lp
(K)
TES,
(C 5 8'P
[k( (K) min
Σ
x l1p
TES,
2 (C-& 8. (
where for (+) we used equivalence of norms in Euclidean spaces, and the last inequality uses the first claim and lemma
F.2 MPNN WITH HOWER-HÖLDER COMPONENTS ISN'T NECESSARILY LOWER-HÖLDER
Consider the following setting: we consider graphs in Ggn( where f = [- C R. Assume have an MPNN f with two layers, where the aggregation functions the one dimensional
34

---

Published as a conference paper at ICLR 2025
functions q (Z1,..., Tn) + E ReLU(x; - where b ~ [-3,3] We showed this type of multiset aggregation is Lower-Hölder in expectation C.4 We claim that with these mie-dimensional aggregations and for any COMBINE function, there are graphs G1, G2 (S2) which can be separated by two iterations of .W, but cannot be separated by two of our MPNN iterations, for any choice of network parameters. An illustration of these graphs is given in Figure 'hee parameter can be taken to be any fixed number in (0, 1/2). As can be seen, the depth-2 computation trees of the nodes at level 2 (children of the root, filled in red) differ between the graphs. Therefore, the 1-WL test will succeed in determining the graphs are non-isomorphic after two iterations.
We now explain why the aforementioned MPNN won't i succeed in separating the graphs in two iterations. In our analysis, we use the names of the nodes defined in the figure: a1...., e1 for the nodes of G1 and 02...., 22 for the nodes of G2. We denote that feature vector at (e.g..) an after the k-th iteration by d1
The reason for the failure of two iterations of the MPNN separate G1, G2 is that, depending on the value of b, the first aggregation will not be able to simultancously separate the multisets f e and {0, 0ß and the multisets { c, 1 E and { 11 18. In general. we can consider three options, depending on the value of b:
1. b 1-3, -c]]-e]]ee, 1-e,l- +e, In this case, the aggregation won't separate the multisets K K- and {0,0}, and it also won't separate the multisets { --6, e, 1 + e B and {1, 11. In this case, after the first message passing layer, will get equality between the corre-
sponding features of nodes a a2 q 02 b. = b.S) dlt = d=d This means the multisets {af") b1"h B and (az (1) (1) will be equal, and will the multisets Kef y It and (2) d2" Therefore, the second message passing iteration will result in (2)
the equality between the corresponding features of nodes e(? ==)=co c2 -1())= = =1²² and the graphs won't be separated.
2. b E (-c,c): c): In this case the aggregation can separate the multisets {( -c,, cf and (0,00) but not the multisets { - E, + + and { [1, 13.
In this case, after a single message passing layer, we will get equality between features of a2 c
the nodes dj (1) (1) (1) = 6/ a = 6/ = (1)) d d,"
(1)
This means the multisets [af" b and " 65 B will be equal, and so will the mul- tisets (e("), df'B and fo d,
J. result in the equality between the corresponding features of nodes ef fz²) f = 62 and the graphs won't be separated.
/B. Therefore, the second message passing iteration will
3. b b (1 and f1, B. but not the multisets { [ e) and {O,00.
1 + c): In this case the aggregation can separate the multisets I c, 1 + cB
This will lead to similar result as the previous case, just with a slight change to the equivalence classes of the nodes.
Overall, have shown that the proposed MPNN, which is composed of lower-Hölder in expectation components, fails to separate the above graphs for any choice of parameters. Therefore, it cannot be lower-Hölder in expectation w.r.t. TM (2).
We note that the graphs be separated by similar ReLUMPNN which is wider, has additional message passing layers. Our point here is just that there exists an MPNN with K message passing layers, composed of lower-Hölder in expectation components, which isn't lower Hölder in expectation w.r.t. DMDK
F.3 RELUMPNN AND SMOOTHMPNN
In the main text of the paper stated the following informal theorem
Theorem 4.2. Assume that ReluMPNN with depth K is a lower-Höldd in expectation with respect to (M))) then a 2 1 1 K+1 If Smoothh with depth is a lower- in expectation then a 2 2K+1
35

---

as shown in Published as a conference paper at ICLR 2025
4
1+c
42
D2
d
I+c
Figure 5: A pair of labeled graphs G1 (top) and G2 (bottom) used to prove that MPNNs with Hölder building blocks aren't 't necessarily Hölder
We note that the distribution on the parameters taken in this theorem the same as described throughout the text. The aggregation used for both MPNNs at hand is of the form
F.
pla I; - b)
where a and are drawn uniformly from the unit sphere and some interval [-B. B] respectively. Of course, in ReluMPNN ReLU while with smoothMPPNN is smooth function. The parameters of the linear COMBINE function are also selected uniformly in the unit sphere.
e- e-Tree dataset The proof of the theorem based on a family of adversarial example which we denote by c-trees. The recursive construction depends integer T 0, 1, This will give pair of trees (G, G) where G G(T,e),
parameters: real number c, and an G(T,c).
The recursive construction an, du, co, do which consist of single node, with feature value of c, -c, 2c and -2c, respectively. We connect ao bo via new root with feature value 0 to create the tree Go G(T = 0, <). as depicted in the left hand side of Figure 6. We do the same thing with co, dg to obtain the tree Go = G(T 0,
trees depicted in Figure 0 In the first step T 0, we define 'trees'
We now proceed recursively, again as shown in Figure g Assuming that for a given T have eT, dr, Gr, Gr, we define the corresponding trees for
defined the trees ar, br, the figure:
For example, 4r-1 is constructed by joining together two copies of or and two copies of br at common root with feature value 0 shown in the figure the right hand side. From the figure one can also infer the construction of bT+1. CT,1, dr+1 from ar, by, eT, cr. Finally, the tree GT41 is constructed by joining together CT+ dr while G is constructed by joining together
vm+1,00 bT+1
36

---

Published as a conference paper at ICLR 2025
Proof of Theorem 4.2
Denoting MPNN of depth T by fr, w). where denotes the network's ' parameters, our goal is to provide bounds of the form
Ew (f)(f
fr( - w)ll < Ce
(7)
where B depends on T and the activation used, and on the other had show that TM (M e), G(T, e)) scales linearly in This will prove that the MPNN cannot be a-lower Hölder with any a < B.
We can see that TMD" (G(T, e), e)) scales lincarly in e because the TMD is homogenous. Namely, given any G = (V, E, x) and e 0, let eG = V,E,, Then for any T we have
TMD" (cG, = c. TMD* (G, G).
We now turn to estimate the exponent 77. for smooth or ReLU activations, and different values of T. To avoid cluttered notation we will explain what occurs for low values T 0 and T = 1 in detail, and outline the argument for larger T.
When T = O, we apply an MPNN depth T to the graphs Go, Go which means that we just apply readout function to the initial features. This is exactly the +e example discussed in the main text, and so 7 will hold with 3 = (p + 1)/p with ReLU activations, and = with smooth activations.
We now consider the case 7 = 1. Here we apply we an MPNN of depth 7=
= 1 to the graphs G1, G1- Let us denote the nodes of G1 by Ví, using the natural correspondence defined by the figure (middle) we can think of Vi as the nodes of G as well. We denote the node feature values node after single MPNN iteration by Zr,w and &e,w. where denotes the network parameters as before.
Note that for the root we have that Ir, = ž,,w for any choice of parameters W.
At initialization, all leaves of the trees Go. G are assigned one of the values E, 2e, 2e (according the labeling ao, bo; Co or do). If two leaves are assigned the same value (both are denoted by, say, ag), then they will have the same node feature after a single message passing iteration, since they are only connected to their father, and all fathers have the same initial node feature.
We now consider the two remaining nodes. We denote the node connected to the root from the left by in and the node connected to the root from the right by 12-
Let us first focus on the smooth activation case. We note that the children of v1 and 12, in both graphs, have initial features of order c, and the all sum to the same value zero. By considering the Taylor approximation of the activation, as discussed in the proof of Theorem 3.3 we see that for an appropriate constant C' we have that for all small enough e,
|Co,w - d,,wl S Ce², for all parameters w
(8)
where and u could either be U1 or Uz and recall that Ca.w the output of the aggregation function, applied to the initial features of the neighbors of v in G' (and č, is defined analogously for the neighbors of in G).
Additionally, we note that for every parameter w we have that
Coraw + Co2,10 (e) + the (-e) + v.. + (-we) Eey + Gog
(9)
where ahe denotes the neural network used for aggregation. The next step in the MPNN procedure the COMBINE step, after which we will have a bound of the form (9). namely
[.e - -u,ul S Ce², for all parameters w
(10)
since the COMBINE functions we use are uniformly Lipschitz, and we will also have or every parameter wo we have that
Fe,.w w + Foz.w Eoy wo Leg
(11)
since our COMBINE function is linear.
Now, when applying the readout function, we have eleven node features in the multiset of nodes of G, and G₁- For any parameter vector w. if we remove the nodes v1, U2, we get two identical multisets. Therefore, we only need bound the difference
Mar ()) + Tho (Fog, [nw (frg,w) + Tho (Geg.
37

---

Published as a conference paper at ICLR 2025
Figure 6: e-tree dataset construction: The trees are built using basic elements as, by, Ct2 de. At step T, the basic elements are defined using subtrees from the previous step.
Since by (II) the features sum to the same value, and all the same up to e², this difference goes like e". This is what we wanted. For general T, we will be able to apply this same argument recursively T times to get the lower bound of 2T+ for the smooth exponent.
Now, let us consider what happens when we replace the smooth activation with ReLU activation. In This case too, the only features which really matter those corresponding
01, U2- Recalling our analysis of the te for ReLU activations, we note that if the bias of the network falls outside the interval [-2e, 2e]. then all node features Tor, Frgaars Frg.wy &ey.. will all be identical. If the bias does fall in that interval, then the difference between these node features can be bounded from above by Ce for an appropriate constant C. When applying readout, there is a probability of e² that the final global features will be distinct (if the parameters of aggregation, and the parameters of readout, are both well behaved). The difference in this case can again be bounded by Cc. follows that
E. (G e), w) fr(G e), w)ll < Cefe
which will lead to a lower bound on the Hölder constant a 2 (1+
For general T, will get that there is probability of ~ cT+ obtain any separation, and that, if this separation occurs, the difference between features will be < C e. As a result, the expectation
E. fz (G e), w) fr (Ō e), w)ll
will scale like e T+++,, which leads to our lower bound on the exponent for ReL.U activations.
G EXPERIMENTS
G. HARDWARE
All experiments were executed on an a cluster of nvidia A40 49GB GPUs.
G.2 ARCHITECTURE VARIATIONS
In this subsection we will lay out the architectural variations that were considered for SortMPNN and AdaptMPNN, that were omitted from the main text for brevity. We include explanations of these variations with the connection between them and the thcoretical analysis.
SortMPNN
First off, we must choose how model of the blank vector, since SortMPNN uses the blank vector explicitly in (2). We propose three options for the (blank method):
Learnable: For every multiset aggregation function there a unique learnable blank vector that is used for augmentation. Since we assume the node features are from compact subset
38

---

Published as a conference paper at ICLR 2025
of R., there exist valid augmentation vectors, and upon training expect the learnable vector to converge to a valid augmentation vector. Note that this method assumes training takes place.
2. Iterative update: In this method, the blank vector of each layer is the output of the previous MPNN layers on the blank tree, where the blank tree node feature is set to zero. This works under assumptions: (1): The nodes in the dataset don't 't have the feature
(2): The intermediate layer outputs on computation trees from the data don't clash with the same layer output on the blank tree. This seems relatively reasonable since SortMPNN is bi-Lipschitz in expectation, which in expectation should lead to injectivity.
3. Zero: simply using the zero vector as the blank vector. This works under the assumption that the zero vector is neither valid initial feature, nor a valid output of intermediate layers. This is the weakest of the three, but was experimented with nonetheless.
Given a multiset X, we experimented with two variations for the aggregation implementation. Both share step (1), but differ in step (2):
1. projection: X colsort(Ap
:= Y E Rmx", where A E R
2. collapse: In this step, we either perform (1) a matrix collapse: rowsum) Y) where O is the element-wise product and B E _ or (2) vector collapse: Yb, for b R"
Note that when choosing to use the matrix collapse, under the assumption that the blank method pro- vides valid blank vector, this is equivalent to running m separate copies of S. (2) with independent parameters (at least upon initialization), just like we proposed in the main text. W When using the vector collapse, the aggregation takes the form of multiple instances of S₂ except that that the parameter used in the inner product is shared across instances. Note the Hölder expectation doesn't 't change in this case, but the variance is likely higher. We explored this option since it reduces the number of parameters needed for the aggregation, potentially easing the optimization process.
In addition, we experimented with adding bias to the projection, and to the vector collapse.
The main detail we left out from the main text is the fact that the output of adapt MRL.U is in R-, whereas we would want it to be in IR in order to be able to stack m instances and get an output in d In order to get the desired output dimension, we compose RRLU with projection, and the aggregation on multiset X E Rdxr as follows:
AdaptMPNN
adapt
1. Stacked Adaptive ReLU:
m ReRL
adept
(X; a1,
y
E R
M (X; am tm)
2. Project: rowsum(B @ Y) where @ the element-wise product and B e Rmx4 has rows that are drawn uniformly independently from $3
As we proved previously C.3 an inner product with vector drawn uniformly from 5d-1 is bi-Hölder in expectation. From composition properties B.TI this means that the above stacking of multiple adapt
adapt independent instances of project o MRLL keeps the Hölder properties of ReLU
In addition, experimented with four optional changes to the aggregation:
Adding the sum Σ a xy a 5'th coordinate to the output of mRRttt The idea behind this choice is that the sum is an informative feature which is encountered when using the standard ReLU activations and bias smaller than the minimal feature the multiset. For adaptive ReLU, this summation will only occur when 0.
2. Note that the adaptive relu uses the parameter E [0. 1] to choose bias within the minimal and maximal multiset values. When training, we experimented with either clamping to
(0, 1] or otherwise lifting this constraint.
39

---

Published as a conference paper at ICLR 2025
3. We experimented with adding bias term to the projection step, since this potentially lead to stronger expressivity.
4. the initialization of t was optionally chosen to be linspace between [o. 1].
G.3 ADVERSARIAL MULTISET DATASET EXPERIMENTS
Figure 1 and figure 2 both made of the adversarial multiset pairs which are constructed as is described in detail in section
To produce figure 1 we Mrelu: my single adversarial pair of multisets that have 8 scalar elements, with 7 equal moments between the multisets, with 0.1.
To produce figure 2 we used 200 adversarial pairs, each containing 16 scalar elements, where each pair shares the first 15 moments. The pairs differ in the value of c, where E [0, 1]
To further strengthen the evidence of the importance of expected Hölder stability, we performed two additional experiments, where the analyzed models were trained on adversarial datasets.
First, trained the models 4 different datasets created described in C.2 The four datasets were constructed such that each consists of 100 pairs of graphs with n 1 shared moments, where n is one of 1,3,7,15 per dataset. The 100 pairs are constructed by creating the pair from from[C.2 and multiplying all the multiset elements by c, where E np.linspace (0.01, 0.1, 100). In each pair, the multiset that started the iterative construction process with the values - was assigned the label 0, and the other was assigned the label 1. Then, these 100 pairs were randomly split into train, validation and test (0.8/0.1/0.11) The per model test set accuracy results as a function of number of equal moments is presented in figure 7a We see that the better the expected Hölder exponent (depicted for this type of dataset in figure the better the post-training accuracy.
Since the first experiment makes use of a dataset that doesn't 't expose adaptive ReLU's worst-case behavior, we proceed to repeat the experiment, except that now make a slight change the dataset multisets: for each multiset from the previous experiment, we add to the multisets two more elements with the values 2 and -2. This causes the adaptive capabilities of adaptive ReLU to become useless, since the largest and smallest values in the multiset are far larger than the values needed to separate the values that are proportional to e. The results are depicted in figure 7b
0.9
Adaptive
Aecuracy
Accuragy
0.8
ReEU Smoooth
0.7
0.6
0.6
0.5
0.5
0.0
Equal Homents
15
Equal Moments
15
(a) Datasets constructed based on the multisct construction from subsection
(b) Same datasets as 7a with addi- tional features f2, -2 targeting adap- tive ReLU.
Figure 7: Test set accuracy for different configurations of datasets with equal moments.
G.4 C-TREE DATASET
Distortion experiment The experiment depicted in was run set of 1, 000 pairs of trees with
e going from 0.05 to 0.4. The first 500 trees are of height = 3 and were input to MPNNs of depth d 1. and the other 500 trees were of height h 4 and were input to MPNNs of depth d = 2. The plots in figure 3 were separated by MPNN depth in order for the phenomenon to be clearly visible. We note that the feature of all non-leaf nodes which appear with 0 in figure 6 was set to
40

---

Published as a conference paper at ICLR 2025
be 1. All the models in the experiment used linear combination the combine function, had an embedding dimension of 45, 000, except SortMPNN that used an embedding dimension of 2, 048 due to resource constraints. The large width used to show the behavior of the MPNNS the expected value over the parameters. In order to plot the curve in each subplot, the minimal ratio mmin 12/TTM D was computed for each graph pair where is the theoretical dower-Hölde exponent. Then, T'mn x was plotted. Note that T'mn was only computed for half of the pairs with the largest TMD values in order avoid the case where the embedding distance is zero leading to Tmin O.
approach
Throughout the experiment, double precision was used in order to capture the small differences as needed. The measured embedding distance was taken over the output of the readout function, without further processing.
Separation experiment For the trained graph separation experiment, 100 pairs of trees of height h = 4 with [0.1, were used. Trees corresponding to the first row in figure O were given the label 0, and trees from the second row were given the label 1. The models were trained by inputting a single pair as a batch per training iteration. All models were composed of 2 message passing layers, followed by readout and a single linear layer to obtain logit. All of [64, 128, 256, 512] were tested for the embedding dimension with results consistent regardless of the embedding dimension. The models were trained for 10 epochs using the adamw optimizer and a learning rate of 0.01.
In attempt to see the difference in quality between ReluMPNN and SmoothMPNN this dataset, we reran the above, using the 'smallest' tree hight in our adversarial construction (h = 3, d = 1), and used single message passing layer. However, even in this setting both ReluMPNN and SmoothMPNN completely failed to achieve separation.
G.5 TUDATASET
Results on datasets that appear in table 3 for GIN, GCN, GraphSage are from (Xu et al. 2019). except for GIN on NCT109 which is from (Chuang & Jegelka 2022). The reported results in 3 for the fully trained SortMPNN and AdaptMPNN were chosen out to be the best single result out of 30 random hyper-paramedt
choices from the following hyperparameters: batch sizee {32, 64), depthe [2 22-3,, 5]. embed dime {16, 32, 64). combinee [Coneat Project, SinearCombination, Lumm... dropoute {0, 0.1, 0.2).tt mlp depth E (1,2,3), weight decay E (0. 0.01, 0.1). IrE [0.0001, 0.01), optimizer [adam, adamww). #epochs= 500. addition, for SortMPNN the blank method was taken to be iterative update, and the collapse method was taken to be from (matrix, vector) without bias begin used at any stage. For AdaptMPNN, adding the sum the multiset was a hyper-parametto
the choice if to clamp the parameter to be in [0, 1). The choice of the 30 random configurations was chosen with wandb (Biewald] 2020) sweeps.
As stated in the main text, results reported in (Xu et al., 2019). Namely, report the mean and standard deviation of the validation performance over stratified 1 10-folds, where the validation curves of all 10 folds are aggregated, and the best epoch is chosen.
G.6 LRGB
In both experiments from table 4 the models adhere to the 500K parameter limit. The hyper- parameters were tuned for a single seed, and then the configuration with the best validation results was rerun for 4 different seeds. We report the mean and standard deviation on the test set in table The code from the official LRGB github repo was used run these experiments, with the only change being the addition of our architectures. The reported results for other models are taken from (Tönshoff et 2023).
Note that any theoretical result we presented that made use of a uniform distribution on the unit sphere holds also for any t-normalized unit sphere, i.e. æ|||=||| t, where E R, where only the multiplicative constants in the proofs will change. In this experiment, for SortMPNN we normalized the parameters sampled from the unit sphere as follows: (1) the parameter a was sampled from a 1 normalized sphere, (2) the parameter was sampled from I normmalized sphere. This normalization was chosen through hyper-parameter tuning on the validation set.
41

---

Published as a conference paper at ICLR 2025
peptides-func For SorMPNN, the following hyper- parammerssssssss were used to achieve the results shown in the table[4] blank method learnable, collapse method vector, bias used both projection and collapse, combine ConcatProject, embedding dimension 165, message passing layers 4. final mlp layers 3, dropout 0.05, weight decay 0.01, positional encoding RWSE (Dwivedi al. 2022a), learning rate 0.005, scheduler cosine with warmup, optimizer adam W. Number of parameters: 494865.
For AdaptMPNN the following hyper-parameters, were used: the bias parameter & was clamped to stay within [0, 1). the sum of a multiset was added as a 5'th coordinate, bias added in project, collapse method LinearCombination. embedding dimension 220, message passing layers 6, final mlp layers 3, dropout- 0,05, weight decay 0.01, positional encoding RWSE, learning rate 0.001, scheduler- - cosine with warmup, optimizer adamW. Number of parameters: 480915.
blank method learnable, collapse method - vector, bias not used both in projection collapse, combine LinearCombination, embedding dimension 200, message passing layers 6, final mlp layers 3, dropout 0, weight decay 0.01, positional encoding LapPE. (Dwivedi & Bresson 2021), learning rate 0.005, scheduler step. optimizer adamW. Number of
peptides-struct For SortMPNN:
parameters: 493858.
For :dattMPNN:the bias parameter added as a 5'th coordinate, bias added in project, collapse method LinearCombination embedding dimension 220. message passing layers final mlp layers dropout O, 0,weight decay 0.1, positional encoding- LapPE, learning rate 0.001, scheduler step. optimizer adamW. W. Number of parameters: 480973.
clamped to stay within [0, 1J. the sum of multiset was
small models Additional experiments run on peptides struct were performed by running models with the exact same hyper-parameten aside from the width. Results are shown in figure 8. Exact width and number of parameters (including for the 500K budget) appear in table
peptides-struct MAE parameters
0.350
SoftMPNN
AdaptMPNN
Table 6: [width #params] per model for each parameter budget
0.325
GCN
MAE
0.300
Budget
SonMPNN
AdapIMPNN
GCN
500K
[200] 493.8K]
[2201 478. SK]
[235 488K]
0.275
100K
[70195.9K]
195 199.6KK]
[1001 98 JK]
50K
1814333K]
149.3]]]
[68 148.888
0.250
25K
[34124.9K]
[44 [44124.3K]
[46 24..2K]
500k 100k 50k
7K
[17]
[22 16.7K]
[23 6.8K]
# Parameters(iogal
IK
[31922]
[51955]
[S 11982
Figure 8: pep-struct, #params vs. MAE
G.7 SUBGRAPH AGGREGATION NETWORKS
In this experiment, we made use of edge features. The incorporation of edge features was done via the concatenation of the edge and relevant node features, followed by a linear layer projecting the concatenated vector to the desired dimension. The projected vector was then passed through a Rel.U activation.
Test set mean and standard deviation were computed over 10 random seeds. chosen by randomly running 40 configurations with the DS edge deleted configuration, and choosing the best. the validation set was done using single seed. The code provided with (Bevilacqua et al.) 2022) was used to run these experiments, with the only change being the addition of our architectures.
were
SortMPNN Both for the DS and DSS experiments, the model consisted message passing layers, used sum Jumping Knowledge (JK) from (Xu al., 2018), Combine ConcatProject, matrix collapse, bias was added to projection, blank method learnable. The model was trained for 400 epochs with 1==0.01 and batch size of 128.
42

---

Published as a conference paper at ICLR 2025
AdaptMPNN Both for the DS and DSS experiments, the model consisted of 5 message passing layers, sum JK for DS and last for DSS, combine ConcatProject, sum wasn't added, was clapmed to [o, 11, bias was added throughout aggregation steps. The model was trained for 400 epochs, with Ir of 0.005 for DS and 0.01 for DSS.
H RUNTIME
Model
GINE GCN
SortMPNN
AdaptMPNN
Avg. time per epoch (s) 12.16
14.25
16.08
26.77
Table 7: Average time per epoch of various models on the peptides-struct dataset. Average taken over 250 epochs.
43


Reviews:
[{"review_id": "2KV40CvpIQ", "reviewer": "Reviewer_gx6Y", "summary": "The authors study stability and separability properties of multi-set and graph neural networks. They do this by establishing Holder lower bounds on the networks, which give some guarantees on separability. They argue that uniform Holder lower bounds are too restrictive, and instead propose a notion of lower Holder in expectation, which is averaged over a probability distribution on the parameters of the network. The main results in the paper are bounds on the lower Holder exponent for different types of graph and multiset neural networks. They find that common architectures have poor exponents and separability properties and propose two new message passing neural networks with better separation properties. They provide a number of numerical experiments with their newly proposed architectures, and compare against existing methods. \n\nSome typos I noticed: \"decays rapidly with the network’s depth .\", \"paces. , let W be some set of parameters\", \"function. we say that\", \"multisets (Zaheer et al., 2017) ,as well as MPNNs\"", "questions": "Holder continuity is usually used for exponents in the range [0,1]. Functions that are Holder continuous with exponents larger than 1 are trivial constant functions. It is not clear to me why the main results with \\alpha > 1 are interesting. Is it because it is only the lower bound and not the upper? \n\nThe choice of the probability measure under which Holder in expectation is taken seems to be essential. However, I don't see this appearing in the discussion or even in the proof sketches of most of the results. This was confusing to me. Even in Euclidean space, it seems it would be challenging to choose the right measure. If the data satisfied the manifold-hypothesis, for example, then a function that well-separates the data could be constant almost everywhere with respect to Lebesgue measure and thus have no lower bound with Lebesgue measure, but would have some appropriate lower bound with a measure tuned to the data.\n\nIn the definition of the Wasserstein metric on line 197 there is a p-norm on the right hand side, but it is W^1. Is this correct?\n\nThe authors give a lot of pathological adversarial examples of graphs that are difficult to separate. How practical are these examples?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Deep graph neural networks is an important area of research, and there are an enormous number of different architectures that have been proposed. This paper provides some valuable insights into which networks give better separation properties. The lower Holder estimates in expectation are novel contributions to the literature, as far as I am aware. The new MPNN architectures with better separation properties are a nice contribution.", "weaknesses": "The lower bounds may be pessimistic, relying on pathological adversarial examples. It is not clear how practical the advances are, in that the worst case graphs may not be encountered in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EgZSNEVj8U", "reviewer": "Reviewer_oS9G", "summary": "This work analyzes the abillity for multiset and graph neural networks to separate inputs. Due to the non-injectivity of ReLU networks, the authors introduce the property of a network being Holder in expectation over random weights (Holderness is just an extension of Lipschitz continuity with an exponential factor $\\alpha$). The authors then derive the lower-Holder exponents for a variety of models, and provide preliminary empirical evidence that lower Holderness is related to network performance on some synthetic tasks.", "questions": "Comments and questions\n\n1. Definition 2.1 depends on choices of $\\alpha$ and $p \\geq 1$. Shouldn't we be talking about whether functions are $\\alpha,p$ lower-Holder in expectation instead of just $\\alpha$ lower-Holder in expectation?\n2. The remarks on line 162-165 don't make sense to me. Consider: \"Firstly, we note that if the set of $w$ for which $f (x; w)$ is $\\alpha$ lower-Hölder has positive probability, then $f(x; w)$ will be $\\alpha$ lower-Hölder in expectation.\" I don't see why this is true. If we take $p=1$ and move $c^p$ in Definition 2.1 to the denominator of the RHS, then the $w$ for which $f(x; w)$ is $\\alpha$ lower-Holder produce a value inside the expectation which is $\\geq 1$. Then all we can say is that the RHS expectation is atleast the probability mass of such $w$'s that satisfy the original lower-Holder condition -- this bound cannot even be greater than $1$, which is what the LHS would become after dividing by $c^p$.\n3. Is the implication of the experiments in Figure 3 that the presented bounds are tight?\n4. Does the adaptive ReLU activation provide any experimental benefits?\n5. Am I correct in concluding from Theorem 3.3 that any smooth activation (e.g. sigmoid) cannot be $\\alpha$ lower-Holder in expectation (otherwise $\\alpha$ would have to be infinity)? This seems counterintuitive; consider an activation like $a^{-1} \\log(1 + e^{ax})$. This function is smooth and thus cannot be $\\alpha$ lower-Holder in expectation, but in the limit $a \\to \\infty$ approaches the ReLU function which is $\\alpha=3/2$ lower-Holder in expectation.\n\nMinor remarks:\n* Reading just theorem 3.1, it is unclear how $a$ and $b$ are related to the rest of the thoerem. I suggest writing $m_{ReLU}(\\ \\cdot\\ ; a,b)$ in the theorem statement.\n* Figures should be exported as pdfs or pgfs in order to avoid text blurring.\n* There is a line of work on the abillity of GNNs to discriminate signals from a spectral theory perspective which might be worth discussing:\n\n[a] Gama, Fernando, Joan Bruna, and Alejandro Ribeiro. \"Stability properties of graph neural networks.\" IEEE Transactions on Signal Processing 68 (2020): 5680-5695.\n\n[b] Pfrommer, Samuel, Alejandro Ribeiro, and Fernando Gama. \"Discriminability of single-layer graph neural networks.\" ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2021.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "Overall, this is a heavily theoretical work that I am not well-equipped to confidently review. I have given it my best effort, although I will likely defer to other reviewers' judgements.\n\n1. I really appreciate the $\\epsilon$-tree experiment. I originally had my doubts that an architecture being $\\alpha$ lower-Holder in expectation over *random weight parameters* is that meaningful for the practical ability of networks to distinguish inputs. Random-weight networks hardly reflect how trained networks ultimately behave. This experiment provides examples of networks which are and aren't $\\alpha$ lower-Holder in expectation and shows that this property is critical in a synthetic task.\n2. The theory is extensive but generally well-presented and the headline results are clear (although I did not check the proofs in detail). Proof sketches are included where appropriate.\n3. The considered problem is interesting, and I appreciate how the authors generalized their framework to both multiset analysis framework to graph neural networks.\n4. It's a surprising result to me that relu sum networks are $\\alpha=3/2$ lower-Holder in expectation. I would have originally guessed that they would be just $\\alpha=1$ lower-Holder (Lipschitz) in expectation.", "weaknesses": "1. Some of the experimental benefits are pretty marginal (especially in table 4, where the gains are smaller than the exerimental variance).\n2. While the $\\epsilon$-Tree experiment provides some evidence for the importance of $\\alpha$ lower-Holderness in expectation over random weights, it just includes a few anecdotal examples of architectures which do and don't work. A really convincing experiment would consist of a scalar-parameterized collection of function classes (which are in turn parameterized). Say this scalar smoothly varied the resulting $\\alpha$; I'd then hope to see that as $\\alpha$ increased, performance increases.\n3. The paper seems rushed, and has many typos. Consider lines 145-147 for example (there are many more such mistakes). The authors should thoroughly proofread their work.\n4. Related, the paper presentation is somewhat haphazard, with many text-wrapped figures and tables; these really should be combined appropriately and top-aligned to the page with no text wrapping.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DIikHXctd0", "reviewer": "Reviewer_aRUR", "summary": "The paper introduces a framework for quantifying the separation quality of multiset and graph neural networks (GNNs) via Hölder stability. This is motivated by recent observations that certain graph pairs, despite being theoretically distinguishable by Weisfeiler-Leman (WL)-expressive MPNNs (message passing GNNs), may have their embeddings \"squashed\" by GNNs, to the point that they are practically indistinguishable. The authors argue that strict lower Hölder continuity, which is only fulfilled for injective embeddings, is too restrictive as a concept and instead consider lower Hölder continuity in expectation over fixed parameter distributions. Starting with the multiset case, which appears as building blocks of MPNNs, they analyze the expected Hölder stability of popular architectures and introduce two new approaches, one based on bias scaling and the other on sorting, that improve the theoretical guarantees. They then employ these new multiset architectures in MPNNs and analyze their expected Hölder stabilities w.r.t. a WL distance, the tree mover's distance (TMD) (Chuang & Jegelka, 2022). Notably, the sort-based technique is shown to be lower Lipschitz in expectation w.r.t. the TMD. The new architectures AdaptMPNN and SortMPNN are empirically analyzed on toy and real-world datasets, demonstrating superior separation compared to popular MPNN baselines.", "questions": "- Regarding the weaknesses: Are there any major difficulties in a Hölder stability analysis of AdaptMPNN compared to ReluMPNN? If so, a short paragraph explaining this might be interesting.\n- I am a bit puzzled about the results for the adaptive ReLU architectures: Both in Figure 2 and Figure 3, the corresponding architectures seem to be almost perfectly lower Lipschitz on the data, behaving similarly to the sorted architectures. If I am not mistaken, however, this is not guaranteed by the theory that is derived. I am assuming that this is not a consequence of the bound from Theorem 3.2 not being tight, since it is stated in lines 308-309 that the adaptive ReLU architecture for multisets is *not* lower Lipschitz in expectation, as can be shown by some adversarial graphs. However, I couldn't find any further justification for this statement in the manuscript, as Theorem 3.2 only shows that $(p+1)/p$-lower Hölder continuity in expectation (which evaluates to $\\alpha=3/2$ for the $\\ell^2$ case), while Theorem 3.1 only refers to standard ReLU summation. Could you maybe point me to a proof/justification or add one, and generally comment a bit more on the performance of the adaptive ReLU methods in Figure 2 and 3?\n- As also mentioned in the paper (lines 344-346), there are multiple WL distances that have been suggested so far. As expected lower-Hölderness also crucially depends on the chosen distance functions, is there any particular reason why you chose the TMD?\n- An interesting question would be to analyze more quantitatively how the expected Hölder stability evolves over training, as the theory is only laid out for the initial parameters (and depends crucially on the initialization distributions). While the results of Table 2 suggest that the stability is preserved during training, I would find more quantitative empirical results concerning the evolvement of the Hölder stability with the NN weights during training very interesting to see. However, as this is very open-ended and potentially costly, I would like to emphasize that this is merely as a suggestion.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem is well-motivated and I enjoyed reading the paper. To the best of my knowledge, the idea is novel, and as part of the ongoing effort to understand the geometry of MPNN embeddings, this work is a notable step.\n- The theory is made quite accessible, and I particularly found the $\\pm \\epsilon$ example, which is used throughout the theory section, to be very instructive for a high-level understanding of the theorems.\n- The presented empirical results are strong and insightful, showing that AdaptMPNN and SortMPNN can perfectly distinguish certain pairs of adversarial WL-distinguishable graphs, a task which standard MPNNs fail entirely.", "weaknesses": "In my opinion, the main weakness of the paper in its current state is that there is no theoretical analysis of the (expected) lower-Hölder properties of AdaptMPNN. While AdaptMPNN is one of the main methodological contributions of the work, only the lower-Hölder stability of the two \"baselines\" ReluMPNN and SmoothMPNN as well as SortMPNN are analyzed in section 4. Ideally, an outline of a worst case analysis as mentioned at the end of section 4, or at least some justification if or why there is something inherently harder about the analysis of AdaptMPNN compared to ReluMPNN might be an insightful addition to the manuscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WL34xlU7zF", "reviewer": "Reviewer_TQxc", "summary": "This paper proposed a pairwise separation quality analysis framework to study the Lipschitz and Hölder stability of functions on multisets and graphs. The authors proposed the notion of lower-Hölder in expectation (Definition 2.1), relaxing the uniform Hölder stability to the pairwise fashion. The authors showed that sum-based models on multisets and graphs are lower-Hölder in expectation with different exponents, depending on the activation choices (Table 1). Motivated from the theoretical analysis, the authors proposed AdaptMPNN and SortMPNN, which can separate the adversarial graph pairs and demonstrated improved empirical performance to existing MPNNs on standard benchmark datasets.", "questions": "1. The authors claimed that \"SortMPNN is the first MPNN with both upper and lower Lipschitz guarantees\" (Line 120-121). However, BLIS-Net proposed by Xu et al. [1] is shown to be Bi-Lipschitz with respect to a weighted inner product space. Can the authors compare and comment the differences?\n\n2. Theorem 3.4 (SortMPNN is uniformly upper Lipschitz\nand lower Lipschitz in expectation): This result seems straightforward given results in Balan et al. (2022). Can the authors discuss this more explicitly?\n\n3. Connections between SortMPNNs and other related models: While sort-based aggregation function is rarely used in practice (and thus the novelty of the proposed SortMPNN), we can still see its \"shades\" in some related works. For example, in [2] the authors experimented with a sorting-based aggregation function; in [3] the authors proposed to learn a recursive aggregation function, which could in theory mimic a recursive sorting algorithm. Can the authors comment more of these related models?\n\n\nReferences:\n\n[1] Xu, Charles, et al. \"BLIS-Net: Classifying and Analyzing Signals on Graphs.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.\n\n\n[2] Duvenaud, David K., et al. \"Convolutional networks on graphs for learning molecular fingerprints.\" Advances in neural information processing systems 28 (2015).\n\n\n[3] Ong, Euan, and Petar Veličković. \"Learnable commutative monoids for graph neural networks.\" Learning on Graphs Conference. PMLR, 2022.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The study of separation power and stability of functions on multisets and graphs is of high interest to the community.\n\n2. The proposed notion of lower-Hölder in expectation is interesting and can explain practical performance.\n\n3. The proposed adversarial examples (i.e., $\\pm \\epsilon$-multisets, $\\epsilon$-trees) are instructive and very useful to illustrative the theory.", "weaknesses": "1. The proposed SortMPNN deserves more remarks and discussion; see details in the Question section.\n\n2. Empirical Comparison between AdaptMPNN, SortMPNN versus ReluMPNN and SmoothMPNN: While the authors compare these MPNN variants in Table 2 with the synthetic $\\epsilon$-Tree dataset, the authors do not include the results of ReluMPNN and SmoothMPNN on the standard benchmark datasets (e.g. TUDataset, LRGB). Including such comparison could better bridge the theoretical insights in the paper to practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)