On the Hölder Stability of Multiset and Graph Neural Networks

Dear reviewer, thank you for the review! Below we address the questions you raised. We hope we were able to answer your concerns. Please let us know if you would like any further clarifications.

Questions:

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?

This is a very interesting paper, thank you for pointing it out. We added the following to the related work, which we believe explains the differences: “In an additional recent work, \citet{xu2023blisnet} introduced a GNN designed to be bi-Lipschitz with respect to a 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.”

Theorem 3.4 (SortMPNN is uniformly upper Lipschitz and lower Lipschitz in expectation): This result seems straightforward given results in Balan et al. (2022). Can the authors discuss this more explicitly?

Our bi-LIpschitz proof for multisets, namely Theorem 3.4, is indeed based on Balan’s work as discussed directly after the statement of the theorem.

Regarding SortMPNN which targets graphs: firstly, Balan did not discuss this scenario at all. Secondly, our proof does not employ ideas from Balan’s proof. In fact, the lower-Lipschitz in expectation bound we show holds even when the network has width 1, a fact which certainly does not hold w.r.t the standard notion of Lower-Lipschitz, since lower-lipschitz implies injectivity.

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?

Thanks for suggesting these references. We already had a paragraph in the related work section describing other models for GNNs and multisets which used sorting. We added a reference to [2] in this section.

Weaknesses:

The proposed SortMPNN deserves more remarks and discussion; see details in the Question section.

We hope we were able to address your concerns. If there is something that is missing, please let us know.

Empirical Comparison between AdaptMPNN, SortMPNN versus ReluMPNN and SmoothMPNN: While the authors compare these MPNN variants in Table 2 with the synthetic -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.

The reason we didn’t include ReluMPNN and SmoothMPNN in the standard benchmarks is that we consider them as simplified models for standard MPNN, which are based on similar building blocks. For example, the formulation of GIN is basically using such an aggregation. See corollary 6 and the paragraph after it in “How powerful are graph neural networks?". In our first experiment, the $\epsilon$-tree experiment (Table 2), we see that indeed standard MPNN architectures behave similarly to ReluMPNN and SmoothMPNN in terms of Holder exponents. In the later experiments, our goal was to see whether the improved worst case stability of SortMPNN and AdaptMPNN, which we regard originally as our core models, translates into improved performance on real data.

Dear reviewer, thank you for the review! Below we address the questions you raised. We hope we were able to answer your concerns. Please let us know if you would like any further clarifications.

Questions:

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 -lower Hölder continuity in expectation (which evaluates to for the 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?

We agree with these remarks, thanks. To address this we made the following improvements in the revised version of the submission:

1. We added to Theorem 3.2 the statement that the exponent of (p+1)/p is tight, and updated the proof accordingly.

2. In Remark C.6 we explained intuitively why adaptive ReLU performs in a bi-Lipschitz like fashion in the adversarial examples used for Figures 2 and Figure 3. We also explained how to modify these examples so that the Holder behavior of adaptive ReLU is apparent.

3. In Figure 7 which we now added to the paper, we show how adaptive ReLU, which performs well on our vanilla adversarial example Figure 7(a), fails once they are modified as we suggest in Figure 7(b).

In general, the idea is as follows: ReLU-summation can separate multisets {$-\epsilon,\epsilon$} and {$-2\epsilon,2\epsilon$} only when the bias is in the range (-2\epsilon,2\epsilon\) . The probability of the bias falling in this range is small, and this causes the non-lower-Lipschitzness of ReLU-Summation.

The idea behind Adapt-MPNN is to choose the bias to lie between maximal and minimal features. In the example discussed above, this will automatically lead to the bias lying in the correct regime where it can separate the two multisets. Thus, on this example, Adapt-MPNN will behave like a lower-Lipschitz function, in expectation. However, if we add the same large positive and negative feature to both multisets, to obtain {$-1,1,-\epsilon,\epsilon$} and {$-1,1,-2\epsilon,2\epsilon$}, then the bias will be selected in the regime $(-1,1)$, and so the probability of the bias lying in the correct regime will be very low as in the standard ReLU case, and we will get a behavior consistent with the worst case (p+1)/p exponent.

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.

We believe the same ideas used to prove Theorem 4.2 for ReluMPNN will apply to AdaptMPNN, but this would require modifying the epsilon tree example by adding leave to the trees with fixed features valued 1 and -1, similar to what is discussed above for the multisets.

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?

We believe there are several points presented in the original TMD paper that indicate its relevance for MPNN analysis: (1) Table 1 in their paper shows that a simple SVM based on TMD is competitive on some graph benchmarks. (2) Figure 4 in their paper shows the nice correlation between TMD and MPNN embeddings (in contrast to another WL-metric they compare to).

In any case, we conjecture that many WL-metrics are equivalent (in a “bi-Lipschitz” sense). In research we are currently working on we have encouraging preliminary results regarding this conjecture.

An interesting question would be to analyze more quantitatively how the expected Hölder stability evolves over training… However, as this is very open-ended and potentially costly, I would like to emphasize that this is merely as a suggestion.

This is definitely an interesting experiment. However, due to time and resource limitations we don’t believe we will be able to add this within the discussion period. We hope to address this in future work.

Weaknesses:

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.

Thanks for this suggestion. We took two steps to address this concern:

1. In an attempt to see the difference in quality between ReluMPNN and SmoothMPNN on the epsilon-tree dataset, we reran the above, using the 'smallest' tree height in our adversarial construction ($h=3,d=1$ as opposed to $h=4,d=2$ shown in the main text), and used a single message passing layer. However, even in this setting both ReluMPNN and SmoothMPNN completely failed to achieve separation. We added a paragraph discussing this in appendix G.4. This is consistent with our theory, since even when $d=1$ ReLU MPNN has a lower Holder exponent of at least 2, and SmoothMPNN has a much higher exponent. In contrast, SortMPNN which is bi-Lipschitz (exponent of 1), achieves perfect accuracy on these tasks.

2. We also added a new experiment: we took pairs of multisets with n elements and n-1 identical moments, and used them to construct a binary classification task. We then examined the success of the various multiset architectures as a function of n. In this scenario, the sort based function is bi-Lipschtiz, the ReLU-summation and adaptive-ReLU have an exponent of 3/2, and the smooth-summation multiset functions have a high exponent of at least n. The results we obtain are again consistent with our theory, where sortMPNN achieves perfect performance, ReLU-summation and adaptive-ReLU outperforming smoothMPNN, and the performance of smoothMPNN deteriorating as n increases. This experiment is visualized in Figure 7 and described in Appendix G.3.

Typos...

Sorry about this. We fixed lines 145-147 and made an additional effort to fix typos throughout the text.

Regarding text-wrapped figures and tables

This was done due to the constraint on the number of pages. To solve this issue, we moved a figure into the appendix (in the revised version this is figure 8), which allowed us to top-align tables 3 and 4. We hope this makes the presentation more friendly.

Dear reviewer, thank you for the review! Below we address the questions you raised. We hope we were able to answer your concerns. Please let us know if you would like any further clarifications.

Questions:

Definition 2.1 depends on choices of $\alpha$ and p>=1. Shouldn't we be talking about whether functions are $\alpha,p$ lower-Holder in expectation instead of just lower-Holder in expectation?

You are correct. Indeed for ReLU-summation the lower Holder exponent depends on p. Nonetheless we choose to drop p from the notation to avoid cumbersome notation.

regarding the comment starting with “the remarks on line 162-165…”

What we mean is that it will be lower-Holder in expectation with the same exponent, but not necessarily with the same constant. Specifically, what you are saying is correct, the constant can be “corrected” by multiplying with the probability mass of said w’s (to the power of p). If you feel this is confusing we would happily add a clarification.

Is the implication of the experiments in Figure 3 that the presented bounds are tight?

As we write in 428-434, figure 3 mainly illustrates that the expected lower Holder exponents of ReluMPNN and SmoothMPNN behave at least as bad as our analysis dictates: the exponent grows at least as the lower bound provided in table 1 (this lower bound is illustrated by the blue solid line). Note that Figure 3 is evaluated on the adversarial examples used to prove these lower bounds. It is certainly possible that there are more extreme adversarial examples, which we are not yet aware of, that will lead to even worse behavior.

Does the adaptive ReLU activation provide any experimental benefits?

The main benefits of adaptive ReLU are theoretical. However, it provides good results on the synthetic $\epsilon$-trees (table 2), and competitive results on the datasets from TUDatasets (table 3) and peptides-func (table 4).

Am I correct in concluding from Theorem 3.3 that any smooth activation (e.g. sigmoid) cannot be lower-Holder in expectation (otherwise would have to be infinity)? This seems counterintuitive; consider an activation like… This function is smooth and thus cannot be lower-Holder in expectation, but in the limit approaches the ReLU function which is lower-Holder in expectation.

Our analysis is conducted on spaces of multisets with at most n elements. In this setting, Theorem 3.3 doesn’t imply that a smooth activation will result in a non lower-Holder in expectation parametric function, but only that if the function is in fact $\alpha$ lower-Holder in expectation, then $\alpha \ge n$ where $n$ is the maximal size of a multiset. However, your argument seems correct if one were to consider multisets with unbounded cardinality.

Regarding the provided example, it indeed can be used to show that the lower-Holder in expectation property doesn’t behave “continuously” with respect to limits in function spaces. This is true also for the standard lower-Holder property.

To see this, we can look at the function $f_{\epsilon}(x)=x^2-\epsilon\cdot x$ on $[0,1]$ with $\epsilon\in [0,1]$. When $\epsilon\rightarrow 0$ the function $f_{\epsilon}$ converges to the function $x^2$, which is lower-Holder with an exponent of $2$: $|x^2-y^2|=|x-y||x+y|\geq |x-y|^2$. However, $f_\epsilon$ is not injective on this domain, as it assigns $x=0$ and $x=\epsilon$ the same value. Therefore, it is not $\alpha$ lower Holder for any $\alpha$.

regarding “Minor Remarks”

Thanks! We changed the theorem statement as you suggested, and added the works you mentioned to the related work section.

Dear reviewer, thank you for the review! Below we address the questions you raised. We hope we were able to answer your concerns. Please let us know if you would like any further clarifications.

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?

Indeed, you are correct. The term Holder continuity usually refers to the upper bound, in which case an exponent greater than 1 indicates a constant function. However, our main results regard the lower bound, in which case the interesting exponents are $[1,\infty)$. A simple way to see this is by noting that for every function $f$ that is $\alpha$ upper-Holder, the inverse function $f^{-1}$ is $1/\alpha$ lower-Holder: let $s=f(x), t=f(y)$, then $|f^{-1}(s)-f^{-1}(t)|=|x-y|\ge |f(x)-f(y)|^{1/\alpha}=|s-t|^{1/\alpha}$.

The 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.

we hope we understand the question correctly, but could it be you misunderstood the expectation to be taken over the data? When defining the notion of Holder in expectation in 2.1, we state that the expectation is taken over some distribution over the parameters, whereas the analysis should hold for any pair of fixed data points. This means the analysis we provide is a worst-case analysis with respect to the data, as is further explained in lines 167-172. We specify the parameter distribution for each function in the respective theorem. For example, in theorem 3.1 we state that $a$ is distributed uniformly on the unit sphere, and $b$ is distributed uniformly on the interval $[-B,B]$ (also recall our notation for uniformly distributed defined in Section 1.0.1)

In 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?

Thanks for catching this mistake. The p-norm was changed to the 1-norm in the revised version of the submission.

The authors give a lot of pathological adversarial examples of graphs that are difficult to separate. How practical are these examples?

This is a good question. Given we are interested in constructing an architecture that is well-behaved for any dataset, for which we don't know the data distribution ahead of time, we resorted to the worst-case analysis. Accordingly, we expect architectures with better expected Holder exponents to be more “robust”. Moreover, our experiments imply that good expected exponents often translate to good performance on real datasets.

General: Thank you for catching the typos, we fixed these.