On the Lipschitz Continuity of Set Aggregation Functions and Neural Networks for Sets
Authors: Giannis Nikolentzos
Konstantinos Skianis
Venue: ICLR 2026 Poster (2026)
Keywords: set aggregation functions
Lipschitz continuity
stability
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: The Lipschitz constant of a neural network is connected to several important properties of the network such as its robustness and generalization. It is thus useful in many settings to estimate the Lipschitz constant of a model. Prior work has focused mainly on estimating the Lipschitz constant of multi-layer perceptrons and convolutional neural networks. Here we focus on data modeled as sets or multisets of vectors and on neural networks that can handle such data. These models typically apply some permutation invariant aggregation function, such as the sum, mean or max operator, to the input multisets to produce a single vector for each input sample. In this paper, we investigate whether these aggregation functions, along with an attention-based aggregation function, are Lipschitz continuous with respect to three distance functions for unordered multisets, and we compute their Lipschitz constants. In the general case, we find that each aggregation function is Lipschitz continuous with respect to only one of the three distance functions, while the attention-based function is not Lipschitz continuous with respect to any of them. Then, we build on these results to derive upper bounds on the Lipschitz constant of neural networks that can process multisets of vectors, while we also study their stability to perturbations and generalization under distribution shifts. To empirically verify our theoretical analysis, we conduct a series of experiments on datasets from different domains.

Published as a conference paper at ICLR 2026
ON THE LIPSCHITZ CONTINUITY OF SET AGGREGA- TION FUNCTIONS AND NEURAL NETWORKS FOR SETS
Giannis Nikolentzos
Konstantinos Skianis
Department of Informatics and Telecommunication
Department of Computer Science & Engineering University of Ioannina loannina, 45, Greece
University of Peloponnese
Tripoli, 22131, Greece
zikolentzos@uop gr
kskiani s@ cs. uoi. gr
ABSTRACT
The Lipschitz constant of a neural network is connected to several important prop- erties of the network such as its robustness and generalization. many settings to estimate the Lipschitz constant of model. Prior work has fo- cused mainly on estimating the Lipschitz constant of multi-layer perceptrons and convolutional neural networks. Here focus on data modeled as sets multi- sets of vectors and on neural networks that can handle such data. These models typically apply some permutation invariant aggregation function, such as the sum, mean or max operator, to the input multisets to produce a single vector for each input sample. In this paper, we investigate whether these aggregation functions, along with an attention -ased aggregation function, are Lipschitz continuous with respect to three distance functions for unordered multisets, and we compute their Lipschitz constants. In the general case, we find that each aggregation function is Lipschitz continuous with respect only one of the three distance functions, while the attention- them. Then, we build on these results to derive upper bounds on the Lipschitz constant of neural networks that can process multisets of vectors, while we also study their stability to perturbations and generalization under distribution shifts. To empirically verify our theoretical analysis, conduct a series of experiments on datasets from different domains.
thus useful
function is not Lipschitz continuous with respect to any
INTRODUCTION
In the past decade, deep neural networks have been applied with great success to several problems in different machine learning domains ranging from computer vision (Krizhevsky et al. 2012 He jet al., (016)) to natural language processing (Vaswani et al. 2017 Peters et 2018). Owing to their recent success, these models now ubiquitous in machine learning applications. However, deep neural networks can be very sensitive to their input. Indeed, it is well-known that some specially designed small perturbation is applied to image, it can false prediction even though the perturbed image looks "normal" to humans (Szegedy et al., 2014 Goodfellow al. 2015).
neural network model to make
A key metric for quantifying the robustness of neural networks to small perturbations is the Lip- schitz constant. Training neural networks with bounded Lipschitz constant has been considered promising direction for producing models robust to adversarial examples (Tsuzuku et al. 2018 8 Anil al.) 2019 Trockman & Kolter 2021). However, Lipschitz constraints are imposed, neural net- works might lose a sigmificant portion of their expressive power (Zhang et al.) 2022a). Therefore, typically no constraints are imposed, and the neural network's Lipschitz constant determined once the model is trained. Unfortunately, even for two-layer neural networks, exact computation of this quantity is NP-hard (Virmaux & Scaman 2018). recent line of work has thus focused on esti- mating the Lipschitz constant of neural networks, mainly by deriving upper bounds (Virmaux &
Scaman 2018 Fazlyab et al. 20199] Latorre et al. 2020 Combettes & Pesquet 2020 Kim et al.)
202. Pabbaraju et al.) 2021| Chuang & Jegelka| 2022 Efficiency is often sacrificed for the sake
of tighter bounds (c. g.. use of semidefinite programming) which underlines the need for accurate
estimation of the Lipschitz constant.

---

Published as a conference paper at ICLR 2026
Summary of main results. Lipschitz constants of the different aggregation functions with respect to the three considered distance functions. d denotes the dimension of the vectors. The "_" symbol denotes that the function is not Lipschitz continuous with respect to a given distance function. f: all multisets have equal cardinalities (= M).
Table 1:
SUM
MEAN
MAX
EMD
L = M
==1
1, M
HAUSDORET' DIST.
L vd
MATCHING DIST.
L -=1
LL = 1/M
1 11=1
Prior work estimates mainly the Lipschitz constant of architectures composed of fully-connected and convolutional layers. However, in several domains, input data might correspond to complex objects which consist of other simpler objects. We typically model these complex objects as sets or multisets (i. e., a generalization of a set). For instance, in computer vision, a point cloud is a set of data points in the 3-dimensional space. Likewise, in natural language processing, documents may be represented by multisets of word embeddings. Neural networks for sets typically consist of series of fully- cully-connected layers followed by aggregation function which produces represen- tation for the entire multiset (Zaheer et al.] 2017 Qi et al. 2017a). For the model to be invariant to permutations of the multiset's elements, permutation invariant aggregation function needs to be employed. Common functions include the sum, mean and max operators. While previous work has studied the expressive power of neural networks that employ the aforementioned aggregation e functions (Wagstaff et al.] 2019 2022), their Lipschitz continuity and stability to perturbations re- mains underexplored. Besides those standard aggregation functions, other methods for embedding multisets have been proposed recently such as the Fourier Sliced- Wasserstein embedding which is bi-Lipschitz with respect to the Wasserstein distance (Amir & Dym 2025).
In this paper, we consider three distance functions between multisets of vectors and investigate whether the three commonly-employed aggregation functions (i. e,, sum, mean, max), along with an attention-based function, are Lipschitz continuous with respect those functions. We show that for multisets of arbitrary size, each aggregation function is Lipschitz continuous with respect to only single distance function, while the attention- based function is not Lipschitz continuous with respect to any of them. On the other hand, all multisets have equal cardinalities, each aggregation function is Lipschitz continuous with respect to other distance functions summarized in Table []] We also study the Lipschitz constant of neural networks for sets which employ the aforementioned aggregation functions. We find that for multisets of arbitrary size, the models that employ the mean and max operators are Lipschitz continuous with respect to a single metric and we provide upper bounds on their Lipschitz constants. Strikingly, we also find that there exist models that employ the sum operator which are not Lipschitz continuous with respect to any of the considered functions. We also relate the Lipschitz constant of those networks to their generalization performance under distribution shifts. We verify our theoretical results empirically on real-world datasets from different domains.
well. Our results
2
PRELIMINARIES
2.1 NOTATION
Let N denote the set of natural numbers. Then, [m] = [I,...,n) C N for n Let also {.D denote a multiset, i. e., a generalized concept of a set that allows multiple instances for its elements. Since set is also multiset, in what follows we use the term "multiset" refer to both sets and multisets. Here we focus on finite multisets whose elements are d-dimensional real vectors. Let M E N \ {1}. We denote by S. (Rd) and by SM (IR') the set of all those multisets that consist of at most M and of exactly M elements, respectively. We drop the subscript when it is clear from context. The elements of multiset do not have an inherent ordering. Therefore, the two multisets X = [ V2. v2 B and Y XX| of a multiset X is equal to the number of elements of X. Vectors are denoted by boldface lowercase letters (c. g., and u) and matrices by boldface uppercase letters (c. g., A and M). Given some vector v. we denote by [v], the i-th element of the vector. Likewise, given some matrix M, denote by [M]; the element in the i-th row and j-th column of the matrix.
{l V2, VI, v2 are equal to each other, i.e., X Y. The cardinality
2

---

Published as a conference paper at ICLR 2026
2.2 LIPSCHITZ CONTINUOUS FUNCTIONS
Definition 2.1. Given two metric spaces (x, and V,dy), function f: X + y is called Lipschitz continuous if there exists a real constant L such that, for all ,1 E X, we have that
dy (f(f(x)), fxz2) S L (x(xx1112))
The smallest such L is called the Lipschitz constant of f.
In this paper, we focus on functions f: S(RR) + Rd that map multisets of d-dimensional vectors d' o'-dimensional vectors. Therefore, X' = S(R4), while distance functions for multisets of vectors (presented in subsection 2.4 while dy is induced by the norm, i. c., dy (f(z1) = (x1 ) f(22)]12.
Red For dx, we consider three
2.3 AGGREGATION FUNCTIONS
As already discussed, consider three permutation invariant aggregation functions which are com- monly employed in deep learning architectures, namely the SUM, MEAN and MAX operators.
SUM
MEAN
MAX
fsuu (X) Σ veX
fMEAM (X)
1
Σ vEX
[Faxx()], max (I))): Vi
X
The SUM aggregator can represent a strictly larger class of functions over sets than the MEAN and MAX aggregators. If the elements of the input sets come from countable set X, then for an ap- propriate f: X + R. the function defined as g., injectively to R (Zaheer et al., 2017). Notably, it is also shown that injectivity is sufficient for ap- proximation. On the other hand, the MRAN and MAX functions are not injective set functions. These results have been also generalized to multisets (Xu et al.) 2019p. Note, however, that it has been em- pirically observed that MEAN and MAX aggregators can outperform the SUM aggregator certain
Σ f(r;) maps the input sets
applications (Zaheer et al. 2017 Cappart et al. 2023).
2.4 DISTANCE FUNCTIONS FOR UNORDERED MULTISETS
We next present the three considered functions for comparing multisets to each other. Let X Vi,.... Vn } and Y {u,,.... u, denote two multisets of vectors, i.e., X,Y S(R.). The three functions require to compute the distance between each element of the first multiset and every element of the second multiset. We the distance induced by the f--norm (i. ei. Euclidean distance) to that end. Note also that all three functions can be computed in polynomial time in the number of elements of the input multisets.
Earth Mover's Distance. The earth mover's distance (EMD) a measure of dissimilarity be- tween distributions (Rubner et al., (2000). Roughly speaking, given two distributions, the output of EMD is proportional to the minimum amount of work required to change one distribution into the other. Over probability distributions, EMD is also known as the Wasserstein metric with p (W)). We use the formulation of the EMD where the total weights of the signatures are equal to each other which known to be metric on the space sets of vectors (Rubner al. 2000) and pseudometric on S(RR))
m n
dEMD LEMD(X,M) Y) min
Fly ||: - u,12
i=1 j=1
subject to
FF 2 0,
1sis m,
isján
15ism
m
j=1
F
15j5n
7
1=1
3

---

Published as a conference paper at ICLR 2026
Hausdorff distance. The Hausdorff distance is another measure of dissimilarity between two mul- tisets of vectors (Rockatellar & Wets 1998). It represents the maximum distance of multiset the nearest point in the other multiset, and is defined as follows:
h(X, Y) max min [|v; - uyl12
The above distance function is not symmetric and thus is not metric. The bidirectional Hausdorff distance between X and Y is then defined as:
du (x, Y) max
The bidirectional Hausdorff distance is metric on the space of sets of vectors and a pseudometric on S(R.). Roughly speaking, its value is small if every point of either set is close some point of the other set.
Matching Distance. We also define a distance function for multisets of vectors, so-called match- ing distance, where elements of one multiset are assigned to elements of the other. If one of the multisets is larger than the other, some elements of the former are left unassigned. The assignments are determined by permutation of the elements of the larger multiset. Let 6,, denote the set of all permutations multiset with n elements. The matching distance between and defined as:
() m 2 X)
das (X,)
otherwise.
where
M(X,Y min #
Σ [[v((0 - uul2 +
Σ (=++1
M la
and MYY X) is defined analogously. Variants of this distance function have been introduced in prior work (Chuagg & Jegelka 2022] Davidson & Dym 2024). If the elements of the input multisets do not contain the zero vector, the matching distance IS metric.
Proposition 2.2 (Proof in Appendix B.1). The matching distance is a metric on S(Rd) \. (0}) where E N and the zero vector. It is a pseudometric on S(Rd)..
For multisets of the same size, the matching distance is related to EMD.
Proposition 2.3 (Proof in Appendix B.2). Ler X, Y E ((R)) denote two multisets of the same size, e.e. X |Y| = M. Then, we have that dm (X, Y) MdEMD Y).
LIPSCHITZ CONTINUITY OF SET AGGREGATION FUNCTIONS AND
NEURAL NETWORKS
3.1 LIPSCHITZ CONTINUITY OF AGGREGATION FUNCTIONS
We first investigate whether the three aggregation functions which are key components in several neural network architectures are Lipschitz continuous with respect to the three considered distance functions for unordered multisets.
Theorem 3.1 (Proof in Appendix B.3
1. The MEAN function defined on ScM (TR.) is Lipschite continuous with respect to EMD and its Lipschitz constant is I. = 1, but is not Lipschitz continuous with respect the Hausdorff distance and with respect to the matching distance.
2. The SUM function defined on S (Rd) is Lipschitz continuous with respect the matching distance and its Lipschitz constant is L = 1, but is not Lipschitz continuous with respect to EMD and with respect to the Hausdorff distance.
3. The MAX function defined on SeM is Lipschitz continuous with respect to the Hausdorff distance and its Lipschitz constant is L = Vd, but is not Lipschitz continuous with respect to EMD and with respect to the matching distance.
4

---

Published as a conference paper at ICLR 2026
The above theoretical result suggests that there is some correspondence between the three aggre- gation functions and the three distance functions for unordered multisets. In fact, each aggregation function seems to be closely related to single metric. We also observe that while the Lipschitz constants of the SUM and MEAN functions with respect to the matching distance and to EMD, re- spectively, is constant (equal to 1), the Lipschitz constant of the MAX function with respect to the Hausdorff distance depends on the dimension d of the vectors (which is typically larger than 1). A direct consequence of the above Theorem that no two of the considered distance functions are bi-Lipschitz equivalent.
As discussed above, the SUM function theoretically more expressive than the rest of the func- tions. However, in practice it has been observed that in certain tasks MEAN and MAX aggregators lead to higher levels of performance (Zaheer et al., 2017 Cappart et al. 2023). While this dis- crepancy hetween theory and empirical evidence may be attributed to the training procedure rather than to expressivity, it suggests that there is no single aggregation function that provides superior performance under all possible circumstances and motivates the study of all three of them.
Our previous result showed that each aggregation function is Lipschitz continuous only with respect to a single distance function for multisets. It turns out that if the multisets have fixed size, then the aggregation functions are Lipschitz continuous also with respect to other functions. This is not surprising given Proposition 2.3
Lemma 3.2 (Proof in Appendix B.4)
1. The MEAN function defined on SM (RR)) is Lipschitz continuous with respect to the matching distance and its Lipschitz constant is L T7 the Hausdorff distance.
1. but is not Lipschitz continuous with respect to
2. The SUM function defined on SM (R.) is Lipschitz continuous with respect to EMD and its Lipschitz constant I. M, but is not Lipschitz continuous with respect to the Hausdorff distance.
3. The MAX function defined on SM (Rd) is Lipschitz continuous with respect to EMD and its Lipschitz constant is T, = M, and it is also Lipschitz continuous with respect to the matching distance and Lipschitz constant is 1.
According the above Lemma, the MAX function is Lipschitz continuous with respect to all three distance functions when all multisets have the same cardinality. This suggests that in such a setting, if any of the three distance functions is insensitive to some perturbation applied to the input data, this perturbation will not result in a large variation in the output of the MAX function.
In addition to the standard aggregation functions described above, recent work has also explored neural-based approaches for aggregating multisets of vectors. Here, we consider an atlention mech- anism, which is commonly employed produce a vector from multiset of vectors. and has achieved significant success in the fields of natural language processing (Yang et al. [0166] Niko- lentzos al. 2020) and graph learning (Veličković al., 2018 Brody et al. (002)). Given multiset Vm I E ((R.),
X Vi......
), the attention mechanism is defined as follows:
m fATT (X) Σ a;v; where a; E exp (q g g( W vz))
exp (q g( (W))))
xd and E IRd denote trainable matrix and trainable vector, respectively, while g denotes some activation function. The output of the mechanism is a convex combination of the multiset's elements.
where W E Rd''dd
We next investigate whether the attention mechanism fxrr(X) is Lipschitz continuous with respect to the three considered distance functions for multisets of vectors.
Proposition 3.3 (Proof in Appendix B.5). There exist instances of fxTT(X) defined on S (I..) which are not Lipschitz continuous with respect any of the three considered distance functions.
Our result aligns with the finding of Kim et al. (2021) who showed that the standard self-attention mechanism is not Lipschitz. Note, however, that the definition of the considered attention mech- anism differs from that of self-attention. Kim et al.) (2021) also proposed alternative Eg self- attention that Lipschitz. Incorporating lg attention into the definition of (X),,,, unfortunately, does not make it I. Lipschitz (more details in Appendix B.6)
5

---

Published as a conference paper at ICLR 2026
3.2 UPPER BOUNDS OF LIPSCHITZ CONSTANTS OF NEURAL NETWORKS FOR SETS
Neural networks that are designed for multisets typically consist of a series of fully-connected layers (i.e., a multi-layer perceptron (MLP)) followed by an aggregation function which then potentially followed by further fully-connected layers. Exact computation of the Lipschitz constant of MLPs is NP-hard /Virmaux & Scaman 2018). However, as already discussed, there exist several approx- imation algorithms which compute tight upper bounds for MLPs (Virmaux & Scaman 2018 Fazlyab et al., 2019; Combettess & Pesquet 2020). An MLP that consists of K layers is actu- ally a function SMIP: IR" + IRd defined as: fM
Tx PK-1 O o P o Ti(v) where T: W.v + b; is affine function and 0s is non-linear activation function for all i [K].
Let Lip(SMLP) denote the Lipschitz constant of the MLP. Note that the Lipschitz constant depends on the choice of norm, and here we assume fn-norms for the domain and codomain of fMLP.
Given a multiset of vectors X = WV.,.... Vm H.. let NNg denote a neural network model which computes its output as (X) = fMLP22 (MLP, (vi),..., fMLP, (v)) where denotes the employed aggregation functiin c., MEAN, SUM or MAX).
Here we investigate whether NNg is Lipschitz continuous with respect to the three considered dis- tance functions for multisets of vectors. In fact, the next Theorem utilizes the Lipschitz constants for MEAN and MAX from Theorem 3.1 to upper bound the Lipschitz constants of those neural networks.
Theorem 3.4 (Proof in Appendix B.7.
1. MEAN defined on S&M (R.)) is Lipschitz continuous with respect to EMD and its Lipschitz constant is upper bounded by Lip fM(())))) -ii(fMMP.).
2. There exist instances of NN defined on Seas (RR) which are not Lipschitz. continuous with respect to the matching distance.
3. NN defined on (R4))R is Lipschitz continuous with respect to the Hausdorff distance and its Lipschitz constant is upper bounded by vd. Lip([Mur.) -ip(fsur,)
The above result suggests that if the Lipschitz constants of the MLPs are small, then the Lipschitz constant of the NNMEAN and NNMAX models with respect to EMD and Hausdorff distance, respec- tively, will also be small. Therefore, if proper weights are learned (or method is employed that restricts the Lipschitz constant of the MLPs), we can obtain models stable under perturbations of the input multisets with respect to EMD or Hausdorff distance. On the other hand, NNsuM is not neces- sarily Lipschitz continuous with respect the matching distance. This due to the bias parameters of fMLP, Interestingly, if omit the bias terms of that layer, NNsuM also becomes Lipschitz continuous with respect to the matching distance.
If the input multisets have fixed size, then we can derive upper bounds for the Lipschitz constant of NN but also of MEAN and NNMAx with respect to other metrics.
Lemma 3.5 (Proof in Appendix B.8).
1. NNsEAN defined on Sas (RR) is Lipschitz continuous with respect to the matching distance and its Lipschitz constant is upper bounded by 3 -Lip([Mur,) Lip(sMur,).
2. NN defined on (Rdd is Lipschitz continuous with respect to the matching distance and Lipschitz constant upper bounded by Lip(fMLP.) Lip.)M..)) and is also Lip- schitz, continuous with respect to EMD and its Lipschitz constant is upper bounded by
M Lip(fMLrz) -iip(
3. NN defined on Sax (Rd) is Lipschitz continuous with respect to EMD and its Lipschitz constant is upper bounded by M Lip( Lip(SMLr,)) Lip [MLr, ). and is also Lipschitz contin- uous with respect to the matching distance and its Lipschitz constant is upper bounded by Lip(fmee.) Lip(SMP,))
3.3 STABILITY OF NEURAL NETWORKS FOR SETS UNDER PERTURBATIONS
The Lipschitz constant is well-established tool for assessing the stability of neural networks to small perturbations. Due to space limitations, we only present a single perturbation, namely ele- ment addition. Other types of perturbations (e. g., element disruption) provided in Appendix C

---

Published as a conference paper at ICLR 2026
Theorem 3.4
implies that the output variation of NNMEAN and MAX under perturbations of the el- ements of an imput multiset can be bounded via the EMD and Hausdorff distance between the input and perturbed multisets, respectively. It can be combined with the following result to determine the robustness of NNMEAN and NNMAx to the addition of single element to a multiset.
Proposition 3.6 (Proof in Appendix B.9). Given a multiset of vectors X = fV1..... Vn E S&M (RR), let X' [V1,.... Vn, Vn+1 SgM((R)) be the multiset where element Vn+1 has been added to X, where n + 1 S M. Then,
1. The EMD berween X and X' is bounded as dEMD XXXX)) m(a+1) Ei= IIv; Vntill
2. The Hausdorff distance between and X' is equal to dx(X,, X') minse[m] [V, Vatill
3.4 GENERALIZATION OF NEURAL NETWORKS FOR SETS UNDER DISTRIBUTION SHIFTS
Finally, we capitalize on a prior result (Shen et al. 2018), and bound the generalization error of neural networks for sets under distribution shifts. Let X denote the set of input data and y the output space. Here we focus on binary classification tasks, i.e = {0. 13. Let μss and pr denote the distribution of source and targer instances, respectively. In domain adaptation, a single labeling function f: X' [0, 1] is associated with both the source and target domains. hypothesis class H. is set of predictor functions, e.e., vh E "H h: X' + y To estimate the adaptability of a hypothesis h, e., its generalization to the target distribution, the objective is to bound the target error (a.k.a. risk) (h) Ex-ue [1/(x)) f(x)] with respect to the source error es(h) Ez=us [+xx) f(x)]] (Ben-Dave David et al. 2010). Shen et al. (2018) show that if the hypothesis class is Lipschitz continuous, then the target error be bounded by the Wasserstein distance with p 1
for empirical measures on the source and target domain samples.
Theorem 3.7 (Shnn et al. 2018)). For all hypotheses h E H. the target error is bounded as:
(h) S eg(h) + 2 (Ps: +
where L is the Lipschitz constant of h and X is the combined error of the ideal hypothesis ht that minimizes the combined error ( + (h)).
This bound can be applied to neural networks for sets that are Lipschitz continuous with respect to a given metric. Since NNMEAN and NNMAX Lipschitz continuous for arbitrary multisets, EMD and Hausdorff distance can serve as ground metrics for these models. Specifically, for the two aforementioned models, the domain discrepancy Wi (1s, jTr) is defined as Wi (us,, (T) inf, inf J d(x, Y)dx(X, xXY, where d(X, Y) is EMD or the Hausdorff distance, respectively.
4 NUMERICAL EXPERIMENTS
We experiment with two datasets from different domains: (i) ModelNet40: it contains 12,311 3D CAD models that belong to 40 object categories (Wu et al. 2015); and (ii) Polarity: it contains 10,662 positive and negative labeled movie review snippets from Rotten Tomatoes (Pang & Leep 2.04 Note that the samples both datasets can thought of as multisets of vectors. Each sample of ModelNet40) is a multiset of 3-dimensional vectors. Polarity consists of textual documents, and each document is represented as a multiset of word vectors. The word vectors are obtained from a publicly available pre- pre-trained model (Mikolov et al. 2013).
4.1 LIPSCHITZ CONSTANT AGGREGATION FUNCTIONS
In the first set of experiments, we empirically validate the results of Theorem 3.1 and Lemma 3.2 To obtain a collection of multisets of vectors, we train three different neural network models on the ModelNet40 and Polarity datasets. The difference between the three models lies in the employed aggregation function: MEAN, SUM or MAX. More details about the different layers of those models are given in Appendix D Note that the multisets used to verify the Lipschitz constants of the ag- gregation functions could, in principle, be generated by any means. We use those models to create multisets since the objective is investigate how these functions behave in comparison to the de- rived bounds when the inputs are sampled from real distributions, rather than artificially generated data that do not occur in practice. Once the models are trained, feed the test samples to them.

---

Published as a conference paper at ICLR 2026
20-
15
1500
1000
Natedd -1
10
r=
10
15
20
10
15
2000
20
Meese Mons 1
15
1000
20
300
F- 0.59
500
1000 dulk, Y1
1500
1500
2000
200
400
600
800
6xKK Y1
4,
2000
1500
E
Pros 10
500
r- 0.89
0.89
C- 0.24
00
9.0
Figure 1: Each dot corresponds pair of point clouds from the test set of ModelNet40. Each subfigure compares the distance between the latent latent representations of pairs of point clouds computed by distance function for multisets e., EMD, Hausdorff distance or matching distance) with the Euclidean distance between the representations of the pairs obtained after applying an aggregation function (i. c., MEAN, SUM or MAX). The correlation between the two distances also computed and visualized. The Lipschitz bounds are illustrated with dashed lines.
For each test sample, we store the multiset of vectors produced by the layer of the model that pre- cedes the aggregation function, and we also store the output of the aggregation function (a vector for each multiset). We then randomly choose 100 test samples, and for each pair of those samples, we compute the EMD, Hausdorff distance and matching distance of their multisets of vectors, and also the Euclidean distance of their vector representations produced by the aggregation function. This gives rise to 9 combinations of distance functions and aggregation functions in total. Due to limited available space, we only show results for ModelNet40 Figure [ The results for Polarity can be found in Appendix E Note that there are (122) = 4,950 distinct pairs in total. Therefore, 4,950 dots are visualized in each subfigure. To quantify the relationship between the output of the distance functions for multisets and the Euclidean distances of their vector representations, we compute and report the Pearson correlation coefficient. We observe from Figure that the Lipschitz bounds (dash lines) successfully upper bound the Euclidean distance of the outputs of the aggregation functions. Note that all point clouds contained in the ModelNet40 dataset have equal cardinalities. Therefore, the conclusions both Theorem 3. land Lemma 3.2 apply to this case, and thus we can derive Lip- schitz. constants for 7 out of the 9 combinations of distance functions for multisets and aggregation functions. We can see that the bounds that are associated with the MEAN and SUM functions are tight, while those associated with the MAX function are relatively loose. We also observe that the distances of the representations produced by the MEAN and SUM functions are very correlated with the distances produced by all three considered distance functions for multisets. On the other hand, the MAX function gives rise to representations that are less correlated with the produced distances.
4.2 UPPER BOUNDS OF LIPSCHITZ CONSTANTS OF NEURAL NETWORKS FOR SETS
In the second set of experiments, we empirically validate the results of Theorem 3.4 and Lemma 3.5 on the ModelNet40 and Polarity datasets. We build neural networks that consist of three layers: (i fully-connected layer; (ii) an aggregation function; and (iii) second fully-connected layer. Therefore, those models first transform the elements of the input multisets using an affine function, then aggregate the representations of the elements of each multiset and finally they transform the aggregated representations using a another affine function. Note that the Lipschitz constant of an affine function is equal to the largest singular value of the associated weight matrix, and can be
8

---

Published as a conference paper at ICLR 2026
125
20000 3 Sp00 (onKCC)
IWas ueaed
100
660
8 3
28
r-0.9
0.82
dructK,
1000
800
125
|Meas Mownl
1000
600
8 3
400
20
200
2.05
(-0.94
100
300
200
300
100
200
500
du/x.1)
du.c.9)
4e1K, V)
100
125
80
100
New
40
0
Figure 2: Each dot corresponds to a pair of point clouds from the test set of ModelNer40. Each subfigure compares the distance between the pairs of point clouds computed by EMD, Hausdorff distance or matching distance with the Euclidean distance between the representations of the pairs that emerge the second-to-last layer of NN NN or NNMAX.
exactly computed in polynomial time. We thus denote by Lip(FCi) and Lip(FC2) the Lipschitz constants of the two fully-connected layers, respectively. Note also that the Lipschitz constant of most activation functions (c. g., ReLU, LeakyReLU, Tanh) is equal to 1. Therefore, we can compute an upper bound of the Lipschitz constant of some models using Theorem 3.4 and Lemma 3.5 To train the models, we add a final layer to them which transforms the vector representations of the multisets into class probabilities. We use the same experimental protocol as in subsection 4.1 above ei.e., we randomly choose 100 test samples). We only provide results for ModelNet40 in Figure 2 while the results for Polarity can be found in Appendix E.2 Since point clouds contained in the ModelNet40 dataset have equal cardinalities, the conclusions of both Theorem 3:4 and Lemma 3.5
apply to this setting, and thus, once again, we can derive upper bounds on the Lipschitz constants for 7 out of the 9 combinations of distance functions for multisets and aggregation functions. We observe that the dash lines (Lipschitz upper bounds from Theorem 3.4 and Lemma 3.5) indeed upper bound the Fuclidean distance of the outputs of the aggregation functions. We also that the bounds that are associated with the MEAN function are tight, while those associated with the SUM and MAX functions are relatively loose and very loose, respectively. We also observe that the distances of the representations produced by the MEAN and SUM functions are very correlated with the distances produced by EMD and matching distance. On the other hand, the MAX function gives rise to representations whose distances are less correlated with the distances produced by the distance functions for multisets.
4.3 STABILITY UNDER PERTURBATIONS OF INPUT MULTISETS
We now empirically study the stability of the two Lipschitz contin- uous models (NNMFAN and NNMxx) under perturbations of the input multisets. Our objective is to apply small perturbations to test sam- ples such that the models misclassify the perturbed samples. We con- sider two different perturbations, Pert. #1 and Pert. #2. Both pertur- bations are applied to test samples once each model has been trained, We then examine whether the perturbation leads to a decrease in the accuracy achieved on the test set. Pert. #1 is the perturbation de- scribed in Proposition 3.6 and is applied to the multisets of Model- Net40. Specifically, we add to each test sample single element. We choose to add the element that has the highest norm across the ele- ments of all samples. Pert. #2 is applied to the multisets Polarity. It adds random noise to each element of each multiset of the test set. Specifically, random vector is sampled from 2/(0, 0.2)d
Table 2: Average drop in accuracy of NN and NN after perturbations Pert. #1 and Pert. #2 ap- plied to the multisets of the test set.
Model
ModelNesti Per. #1
Polarity Per.
NN
2012 1.3)
136 7.0
NNwo
20.1 ct: 1.89
4.8 cé: 3.7)

---

Published as a conference paper at ICLR 2026
WNar AN trieed or kn
NaAA trained on
N.Namaa trained on bar 10
NINMAX trained
Drop Acouq
0.2
1.22
0.2
0.2
Day in. Acturcyy
0.
0.53
0.52
Nomrlllo V
0,50
0.3
Bi
Bm
Bis
Bm
Figure 3: Size Generalization of NNMA and NN MAX models. For illustration purposes, the Wasser- stein distances Wi are normalized to make the maximal distance equal to the greatest performance drops. The models in the left plots are trained on the first bucket, while those in the right plots are trained on the last bucket.
and is added to each element of each test sample. We selected this distribution because its mean and standard deviation closely match the empirical mean and standard deviation of the dataset's word vectors. The results are provided in Table NNMEAN appears to be insensitive to Pert. #1, while NN is insensitive to Pert. #2. The results indicate that N is more robust than NN to larger perturbation that is associated with a single or a few elements of the multiset. On the other hand, NNMAX is more robust to smaller perturbations applied to all elements of the multiset.
4.4 GENERALIZATION UNDER DISTRIBUTION SHIFTS
Finally, we investigate whether neural networks for multisets can generalize to multisets of differ- ent cardinalities. We randomly sample 2, 000 documents from the Polarity dataset, and we repre- sent them multisets of word vectors. We then sort the multisets of word vectors based on their cardinality, and construct 10 bins, each containing 200 multisets. The i-th bin contains multisets X (2000-)+2000 from the sorted list of multisets. We then train MEAN and NAMAX (which are Lipschitz continuous) on the first and the last bin and once the models are trained, we compute their accuracy on all 10 bins. We also compute the Wasserstein distance with p = 1 between domain distributions (i. e., between the first bin and the rest of the bins, and also between the last bin and the rest of the bins). We then aim to validate Theorem 3.7 which states that the error on different domains can be bounded by the Wasserstein distance between the data distri- butions. We thus compute the correlation between the accuracy drop and the Wasserstein distance between the two distributions. The results for NNMEAN and NÑMAx illustrated in Figure 3 The results are averaged over 10 runs. We observe that the Wasserstein distance between the data dis- tributions using EMD (for NNMEaN) and Hausdorff distance (for NNMAx) ground metrics highly correlates with the accuracy drop both in the case where the NNMEAN and NNMAX models are trained on small multisets and tested on larger multisets (r 0.92 and r 0.90, respectively) and also in the case where the models are trained on large multisets and tested on smaller multisets (r = 0.94 and 0.90, respectively). The correlation is slightly weaker in the case of the NNMAx model. Our results suggest that the drop in accuracy is indeed related to the Wasserstein distance between the data distributions, and that it can provide insights into the generalization performance of the models.
X X(200-0+1:
(2(00)))+ (X(o))++1XX((0)))))
CONCLUSION AND DISCUSSION
In this paper, we studied the Lipschitz continuity of multiset aggregation functions with respect to three distance functions. We also explored the Lipschitz constants of neural networks that process multisets of vectors. As a general guideline, one should choose the aggregation function that is Lipschitz continuous with respect to the distance function that best captures the distances between the multisets in the considered dataset or problem. For example, in problems where the shape of the input object matters (e. g., shapes extracted from medical images or 3D scans), Hausdorff distance is preferable to EMD and the matching distance since we would like to detect whether any part of one shape is far away from the other shape. even if the rest of the shapes are well-aligned. However, in some cases, not single distance function is suitable for single problem. For instance, consider the problem of text categorization, where documents are represented as multisets of word vectors. If two documents are considered similar when they contain similar terms, regardless of their length, the EMD is likely to best capture the distance between them. On the other hand, if similarity is determined by the presence of just one or few extreme shared words, the Hausdorff distance is more appropriate. This illustrates that selecting an aggregation function typically requires some domain knowledge. In the absence of such knowledge, choosing an aggregation function can be challenging. except in special cases, such as when multisets have the same cardinality where our results indicate that the max function is Lipschitz continuous with respect to all distance functions.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
We thank the anonymous reviewers for their helpful comments and suggestions. This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.
REFERENCES
Tal Amir and Nadav Dym. Fourier Seese--aasersteiin Embedding for Multisets and Measures. In 13th International Conference on Learning Representations, 2025.
Tal Amir, Steven Gortler, Ilai Avni, Ravina Ravina, and Nadav Dym. Neural Injective Functions for Multisets, Measures and Graphs via Finite Witness Theorem. In Advances Neural Information Processing Systems, pp. 22516-4255 2023.
Cem Anil, James Lucas, and Roger Grosse. Sorting Out Lipschitz Function Approximation. In Proceedings of the 36th International Conference on Machine Learning, pp. 291-301, 2019.
Radu Balan, Naveed Haghani, and Maneesh Singh. Permutation-invariant representations with ap- plications to graph deep learning. Applied and Computational Harmonic Analysis, pp. 101798, 2025.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine Learning, 79:151-175, 2010.
Dimitris Bertsimas and John Tsitsiklis. Introduction to Linear Optimization, volume 6. Athena Scientific, 1997.
John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman, Learning Bounds for Domain Adaptation. In Advances in Neural Information Processing Systems, pp. 129-136, 2007.
Maria Boulougouri, Pierre Vandergheynst. and Daniel Probst. Molecular set representation learning. Nature Machine Intelligence, 6(7):754-763, 2024.
Shaked Brody, Uri Alon, and Eran Yahav. How Attentive are Graph Attention Networks? 10th International Conference Learning Representations, 2022.
Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial Optimization and Reasoning with Graph Neural Networks. Journal of Machine Learning Research, 24(130):1-61) 2023.
Ching- Yao Chuang and Stefanie Jegelka. Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks. In Advances Neural Information Processing Systems, pp- 2944-2957, 2022.
Brian Clarke, Eva Holtkamp, Hakime Öztürk, Marcel Mück, Magnus Wahlberg, Kayla Meyer, Felix Munzlinger, Felix Brechtmann, Florian R Hölzlwimmer, Jonas Lindner, et al. Integration of vari- annotations using deep set networks boosts variant association testing. Nature Genetics, 56(10))2271-2288, 2024.
Patrick I. Combettes and Jean-Christophe Pesquet. Lipschitz Certificates for Layered Network Structures Driven by Averaged Activation Operators. SIAM Journal on Mathematics of Data Science, 2(2)) 2020.
Yair Davidson and Nadav Dym. On the H Hoo)leer Stability of Multiset and Graph Neural Net- works. In 13th International Conference on Learning Representations, 2024.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani. Manfred Morari, and George Pappas. Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks. In Advances in neural information processing systems, pp. 11427-11433 2019.

---

Published as a conference paper at ICLR 2026
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnsssing Adversarial Examples. In 3rd International Conference on Learning Representations, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recogni- tion, pp. 770-778, 2016.
Chaitanya K Joshi, Cristian Bodnar, Simon V Mathis, Taco Cohen, and Pietro Lio. On the Expressive Power of Geometric Graph Neural Networks. In Proceedings of the 40th International Conference on Machine Learning, pp. 15330-15355, 2023.
Hyunjik Kim, George Papamakarios, and Andriy Mnih. The Lipschitz Constant of Self-Attention. In Proceedings of the 38th International Conference on Machine Learning, pp- 5562-5571, 2021.
Masanari Kimura, Ryotaro Shimizu, Yuki Hirakawa, Ryosuke Goto, and Yuki Saito. On permutationninvaaiiat neural networks. arXiv preprint arXiv:2403. 17410, 2024.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet Classification with Deep Con- volutional Neural Networks. In Advances in Neural Information Processing Systems, pp. 1097- 1105, 2012.
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In Sth International Conference on Learning Representa- tions, 2020.
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set Transformer: A Framework for crention-based commutation-nnariiin Neural Networks. In Pro- ceedings of the 36th International Conference on Machine Learning, pp. 3744-3753, 2019.
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and Basis Invariant Networks for Spectral Graph Representation Learning, In 11th International Conference on Learning Representations, 2023.
Andrew Maas, Raymond Daly, Peter Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning Word Vectors for Sentiment Analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguisties: Human Language Technologies, pp. 142-150, 2011.
Tomas Mikolov, Nya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed Repre- sentations of Words and Phrases and their Compositionality. In Advances in Neural Information Processing Systems, pp. 3111-3119, 2013.
Ryan L Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy Pooling: Learning Deep Permutation- Innvattatoon-nvaiiaatt Functions for Variable-Size Inputs. In 7th International Conference on Learning Representations, 2019.
Giannis Nikolentzos, Antoine Tixier, and Michalis Vazirgiannis. Message Passing Attention Net- works for Document Understanding. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pp. 8544-8551, 2020.
Chirag Pabbaraju, Ezra Winston, and J Zico Kolter. Estimating Lipschitz constants of monotone deep equilibrium models. In 9th International Conference on Learning Representations, 2021.
Bo Pang and Lillian Lee. Sentimental Education: Sentiment Analysis Using Subjectivity Summa- rization Based on Minimum Cuts. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, pp. 271-278, 2004.
Giovanni Pellegrini, Alessandro Tibo, Paolo Frasconi, Andrea Passerini, and Manfred Jaeger. Learn- ing Aggregation Functions. In Proceedings of the 30th International Joint Conference on Artificial Intelligence, pp. 2892-2898, 2021.
Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep Contextualized Word Representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long Papers), pp. 2227-2237, 2018.
12

---

Published as a conference paper at ICLR 2026
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 652-660, 2017a.
Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas Guibas. PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space. In Advances in Neural Information Processing Systems, pp. 5105-5114, 2017b.
TTyrelll Rockafellar and Roger Wets. Variational Analysis. Springer, 1998.
Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas. The Earth Mover's Distance as Metric for Image Retrieval. International Journal of Computer Vision, 40:99-121, 2000.
Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein Distance Guided Representation Learning for Domain Adaptation. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 4058-4065, 2018.
Konstantinos Skianis, Giannis Nikolentzos, Stratis Limnios, and Michalis Vazirgiannis. Rep the Set: Neural Networks for Learning Set Representations. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statisties, pp. 1410-1420 2020.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing Properties of Neural Networks. In 2nd International Conference Learning Representations, 2014.
Asher Trockman and Zico Kolter. Orthogonalizing Convolutional Layers with the Cayley Trans- form. In 9th International Conference on Learning Representations, 2021.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-Margin Training: Scalable Certifi- cation of Perturbation Invariance for Deep Neural Networks. In Advances in Neural Information Processing Systems, pp. 6542-6551, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need. In Advances in Neural In- formation Processing Systems, pp. 6000-6010, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph Attention Networks. In 6th International Conference Learning Representa- tions, 2018.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order Matters: Sequence to sequence for sets. In 4th International Conference on Learning Representations, 2016.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances in Neural Information Processing Systems, pp. 3839-3848, 2018.
Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A Osborne. On the Limitations of Representing Functions Sets. In Proceedings of the 36th International Conference on Machine Learning, pp. 6487-6494, 2019.
Edward Wagstaff, Fabian B Fuchs, Martin Engelcke, Michael A Osborne, and Ingmar Posner. Uni- versal Approximation of Functions Sets. Journal of Machine Learning Research, 23(151): 1-56, 2022.
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3D ShapeNets: Deep Representation for Volumetric Shapes. Proceedings the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1912-1920, 2015.
Jiahao Xie and Guangmo Tong. Advances in Set Function Learning: A Survey of Techniques and Applications. ACM Computing Surveys, 57(7):1-37, 2025.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In 7th International Conference Learning Representations, 2019.
13

---

Published as a conference paper at ICLR 2026
Pinar Yanardag and SVN Vishwanathan. Deep Graph Kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374, 2015.
Zichao Yang, Diyi Yang, Chris Dyer, Xiaodong He, Alex Smola, and Eduard Hovy. Hierarchical Attention Networks for Document Classification. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Compulational Linguisties: Human Language Technologies, pp. 1480-1489, 2016.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbhakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J Smola. Deep Sets. In Advances in Neural Information Processing Systems, pP- 3394-3404, 2017.
Bohang Zhang, Du Jiang. Di He, and Liwei Wang. Rethinking Lipschitz Neural Networks and Certi- fied Robustness: A Boolean Function Perspective. In Advances in Neural Information Processing Systems, pp. 19398-19413, 2022a.
Jie Zhang, Chen Cai, George Kim, Yusu Wang, and Wei Chen. Composition design of high-entropy alloys with deep sets learning. npj Computational Materials, 8(1):89, 2022b.
Yan Zhang, Jonathon Hare, and Adam Prüigll-Benntt. FSPool: Learning Set Representations with Featurewise Sort Pooling. In 8th International Conference on Learning Representations, 2020.
A RELATED WORK
In recent years, there has been increasing interest in applying machine learning algorithms to set- structured data. Since sets and multisets are inherently unordered, these models need to be invariant to permutations of the elements in the input set. It has been shown that, otherwise, the ordering of inputs strongly affects performance (Vinyals et al. 2016).
The seminal work Zaheer al. (017) introduced DeepSets, model that uses the sum aggregator to produce permutation-inven invariant set representations. They showed that when the elements of the input sets come from a countable set X, then for an appropriate f X + R, the function defined as [(;;)) maps the input sets injectively to IR. This result was later extended to multisets (Xu al., 2019). In the countable case, an embedding dimension of already suffices for injectivity. When X' I., multiset cardinalities are bounded by m and f is continuous, an em- bedding dimension of at least m is both necessary and sufficient for injectivity (Wagstaff al. 2019 2022). For X = Rdd, an embedding dimension of at least md is necessary (Joshi et al. 2023). Most of these results rely on polynomial constructions to build injective multiset functions, after which the universal approximation theorem is invoked to argue that MLPs can approximate such polynomials. Amir et al. (2023) investigate whether MLP- P-baed multiset functions are actually injective. They show that injectivity depends on the activation function. Specifically, analytic non-polynomial ac- tivation functions yield injective models, while networks with piecewise linear activation functions injective only when A' is finite corresponds certain irregular, countably infinite sets.
gl (( )
Besides DeepSets, several other architectures and aggregation functions have been proposed re- cently. PointNet is another important architecture, primarily designed for point cloud data (Qi al.; 2017ab. It consists of the same components as DeepSets, but instead of a sum aggregation function. employs a max aggregator. To allow PointNet capture local structures different scales, Qi et al. (2017b) proposed PointNet++, a hierarchical model which applies PointNet recursively to nested partitions of the input set. Janossy pooling applies a neural network all permutations of the input data and averages their outputs (Murphy et al., 2019). Since computing all permutations generally intractable, the authors also propose some practical approximations. Set Transformer is variant of the Transformer architecture designed for sets (Lee et al. 2019). Due to its attention mechanism, the model can capture interactions between elements in the input set. RepSet is an- other model designed for set-structured data which generates set representations by comparing the input set against learnable latent sets using a network flow algorithm (Skianis et al. 2020). FSPool sorts each feature across the elements of the set, and then computes weighted sum of the elements where different weights can be learned for each feature dimension (Zhang et al. 2020). Pellegrini
et al. 2021) propose a learnalee aggregation function which can approximate common aggregation
14

---

Published as a conference paper at ICLR 2026
functions (e. g., mean, sum, max), but also more complex functions, Kimura et al. (2024) introduce the Hölder's Power DeepSets, a model tha generalized DeepSets by employing function known as power-mean (a.k.a. Hölder mean), controlled by an exponent p.
Recently, a line of works has studied the Lipschitz continuity of aggregation functions and has de- veloped embeddings that are bi-Lipschitz. [Amir al. (2023) showed that although DeepSets models that use analytic non-polynomial activation functions are injective, they are not bi-Lipschitz with re- spect to the 2-Wasserstein distance. Davidson & Dym (2024) investigated the Hölder continuity of neural networks for sets, a relaxation of Lipschitz continuity. They relied on a probabilistic frame- work of Hölder stability in expectation and showed that DeepSets with ReLU activation functions have an expected lower-Hölder exponent of 3/2. whereas smooth activation functions yield much worse expected oowr-Hööder exponent. [Balan et al. (2025) presented an embedding scheme based on sorting random projections of the multiset elements. The embedding is shown to be injective and (FSW) embedding another theoretically grounded method for learning representations of sets (Amir & Dym 2025). It computes random projections of the input data, and for each projection it samples the cosine transform of the corresponding quantile function. From theoretical standpoint, the FSW embedding has a significant advantage most previous methods, as it is proven to be both injective and bi- bi-Lipschitz.
bi-Lipschitz. The Fourier
Neural network models that can handle set-structured data have been applied across diverse do- mains, including biology (Clarke et al. 2024), chemistry (Boulougouri et al. 2024) and materials science (Zhang al.] 2022b). In some applications, domain knowledge is incorporated into those models. For instance, Lim et al.] (2023) introduce neural architectures specifically designed for eigenvector-based inputs, which can be viewed as variants of DeepSets, while explicitly accounting for the symmetries inherent in eigenvectors. For a recent overview of neural network models for
set-structured data, we refer the reader to the survey by Xie & Tong (2025).
B PROOFS
We next provide the proofs of the theoretical claims made in the main paper.
B. PROOF OF PROPOSITION 2.2
We will show that the matching distance is a metric on S(R.) \\ (O)). Let X, Y E S(Rd {0)).
Non-negativity and symmetry hold trivially in all cases. Furthermore, d (X,X) X) = 0, while the
distance between two distinct points is always positive. Suppose that m = X > YY = n. Then, have that:
das (X,Y) = min
V[ uil
+
Σ imn+1
II
|
Σ imn+1
|| > 0
T
since ||v for all v E Rd \ (0). |X| |Y| = m. since the two multisets are different from
each other, there exists at least one vector with E [m]] such that u, E Y, but u & X. Let TT" E G,, denote a permutation associated with d (X, Y). Then, we have that:
das (M,(X)) (1) will + V(
uil + + [IVx- (m) um 11 2 (() n; > 0
Thus, only need to prove that the triangle inequality holds. Let Z E S(R (0)). The three multisets can have different cardinalities. Let X = m, YY| = n and |Z| = k. Then, X = [vi, ..,..., Vm B. Y = {ui, ug,..., 3 and Z 2 z2, ......... Zs B. There are different cases. But it suffices to show that the triangle inequality holds when |X| 2 Y > 12). when 12| 2 Y Z
[X] and when X > Z
Z |Y] Proofs for the rest of the cases are similar.
Case 1: Suppose |X| > |Y| > IZ). Let रं denote the matching produced by the solution of the matching distance function dm (X, Z):
m
कं = arg min m
V*(1) zill+
|
15

---

Published as a conference paper at ICLR 2026
Likewise, let mz denote the matching produced by the solution of the matching distance function dy((Z
2 = arg min TE6H
(x)
2:ll +
|
Then, have:
dx(X, + dm (Z,
Vvz(())
zil+
Σ
+
|z u23(0 +
|
1=
i=1
k
k
[|v=;00 - z:ll + ||z
u
Σ
|Va +
+
Σ
x=
=
m
Vmz1(()
un2(0) +
VTz1(0)
Σ
i=k+1
m
ung())
+
V+
imn+1
m
min mE m
V+()) -u,ll
Σ
Vvaelll
d X)
Case 2: Suppose |X| 2 7 |Y). Let oī denote the matching produced by the solution of the
matching distance function das (X, Z):
.ं = arg min 66
[|v()) 2
Σ
|V=6||
i=k+1
Likewise, let m. denote the matching produced by the solution of the matching distance function dy (2,Y):
k
22 = arg min
u:
|zاا
mE6
i=++1
Then, have:
& Vaf(0)
dx,(X + du (Z,Y)
zil 2
Σ
I|
|| +
Zmz(0)
u.ll
1=1
14
+=
znz(0)| + [|x3000 uill
1=1
m Σ
Σ
[IV
Bxg(oll + |1
M
2 (o uzll +
||
Maoll
ima+1
k=++
min m m
|iz(0) u.ll +
Σ
1=1+1
das (X,Y) Y)
Case 3: Suppose 2 2 Y > X Let कर denote the matching produced by the solution of the
matching distance function dm (X, Z):
マ = arg min G
||v. 2
2
16

---

Published as a conference paper at ICLR 2026
Likewise, let mz denote the matching produced by the solution of the matching distance function dx((Z,)
|
22 = arg min T
I1
2x(0]1
im++1
Then, have:
&
(x, +d (2.))
Σ v.. 20ll+
uzll +
Σ
(=++1
For each [k], there exists single j E [k] such that (i) m2()). For each i,j Ti
[k]
with
= وे2 (j) one of the following holds:
1. VV (x) || + Zm2(0) u 2 v u. if m and j S n
2. |[: (x)(()) |1 + [x)() > v; if S m and j >
3. (z) + (zz]( uy u,y if and j S n
4. (z) [z;(ح 2 0f
and
Note that dar (X,, 2) + dm Y) can be written as a sum of k terms, where each term corresponds to one of the above 4 sums of norms. If we take pairs of terms of types 2 and 3 and we sum them, we have that:
||v:- - 2 |z + ( - u, ll 2 || I|,,11 || -1 1v,, u Note also that type 2 occurs times more than type 3. Therefore, using the inequalities for the 4 types of sums of norms above, we have:
d (x,) dm,
z min Σ
[vx())
un
Σ N 1=
#EB
dd (X
In case O can be an element of the multisets, there exist X, ((R) with X * Y such that dx,(X, = 0, e., the distance between two distinct points can be equal to 0. The rest of the properties still hold, and thus the matching distance in pseudometric on S(R4).
B.2 PROOF PROPOSITION
If X = |Y| = M, the second and third constraints of the optimization problem that needs to be solved to compute dEMD (X, Y) become as follows:
M
M
1 = M' isisM and EIF M 1 isjsM
Σ Fk
1=1
Therefore, matrix F a doubly stochastic matrix. The Birkhoff-von Neumann Theorem states that the set of M M doubly stochastic matrices forms convex polytope whose vertices the M x M permutation matrices. Furthermore, it is known that the optimal value of a linear objective in nonempty polytope attained vertex of the polytope (Bertsimas & Tsitsiklis, 1997). The optimal solution would thus be permutation matrix P E II scaled by 1/M. Let also E 6M denote the permutation that associated with that matrix. Therefore, we have that:
M M
M Md (X, X) M min
Fly IIv. uyl12
FEBx
M
M
M min Pefl
ΣΣ
P 1|, - u2l12
M
M
min xEθM
Vi(()) u:ll2
(X,
17

---

Published as a conference paper at ICLR 2026
B.3 PROOF OF THEOREM 3.1
B.3.1 THE MEAN FUNCTION IS LIPSCHITZ CONTINUOUS WITH RESPECT TO EMD
Let X fv1, V2:....... v2...., Vm and Y fu, u...... un Ht be two multisets, consisting of m and vectors of dimension d, respectively. Let also F" denote the matrix that minimizes dEMD X, Y). Then, we have that:
[MEAN(X) SMEAN
m
m
Vi
m
n
j=l
m
18
vi
Σ ==1
Σ
F" 16
Tis(1 - 115))
(v, - u
F los Hvll((,
(vv.lvv-u)) uy)ll
1=
deMD
(X,
The MEAN function is thus Lipschitz continuous with respect EMD and the Lipschitz constant is equal to 1.
B.3.2
THE MEAN FUNCTION NOT LIPSCIITZZ CONTINUOUS WITH RESPECT TO THE MATCHING DISTANCE
Suppose that the MEAN function is Lipschitz continuous with respect to the matching distance. Let > 0 be given. Let also
and > (2L + 1)e. Let X (vi, v2). Y {ui} be two multisets, consisting of 2 and 1 vectors of dimension d, respectively. Then, we set = (c.c....,c) and -(,,,...,.)) c))....,.TT. Clearly, we have that das (X, Y) ||v2|| /dc. We also have that:
|| (X) SMEAN
1
2
1=1
1
+
V2
i1
2
2 (G0
(GG...,.)) T) - [= - (
-
C-c6-6
2 9-97
[[ 666 c C...., 6 6- T
2
1
(E 2 + (e c)² + (e c)
2
times
Vdlc- -))
2
1
Vd((22 + 1)E -
2
Lvde
18

---

Published as a conference paper at ICLR 2026
=Xd)((X
Therefore, for any L > 0, there exist X,Y E S(RR) such that (X fMLAN(Y)) L (X, Y). which is contradiction. Thus, the MEAN function is not Lipschitz continuous with respect to the matching distance.
B.3.3 THE MEAN FUNCTION IS NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO THE HAUSDORFF DISTANCE
Suppose that the MEAN function is Lipschitz continuous with respect to the Hausdorff distance. Let L O be given. Let also 0 and 3Lc. Let X {vi, V2, V3), Y {u, u2} be two multisets, consisting of 3 and 2 vectors of dimension d, respectively. Then, we set Vi = i V2 u2 (c, C) and V3 (cte,tt,.... c+e) Clearly, we have that (X, m [3] min ||v: u, ||V3 u2ll Vde. We also have that:
(-c, C...,
3
2
[NNANN(X) - SMEAN(Y)
2
v.
u
3
2
i=1
j=1
1
VI
+
V2
3
V3
2
41
2 U2
1
v
1
(c+ r)2 + (c+ - + (c c)2
3
d(ct e)²
3
1
vd(c+
3
1 Vi(3Te +c)
3
> Lvde
L ddd (X,Y)
For any > O, there exist Y, E S(R") such that [I fAEAN (Y)Il > Ld (X, We have thus reached contradiction. Therefore, the MEAN function not Lipschitz continuous with respect to the Hausdorff distance.
B.3.4 THE SUM FUNCTION NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO EMD
Suppose that the SUM function is Lipschitz continuous with respect EMD. Let L be given.
Then, let m = L - 1]. Let also X = { v...... Vm B. Y [u,,... um } be two multisets, each consisting of m vectors. We construct the two multisets such that V1 u1 V2 u2, Vm Um-11 and such that +... + Vm-1
+ + un = O. Let also l|v... un = m. We already showed in subsection [B.. that the distance between the mean vectors of two multisets of vectors is a lower bound on the EMD between them. Therefore, we have that:
m
1
1
m
1 V
u
N
u
m
m
==1
1
[[V1
U1)
+ (V2 U2) +... + (Vm un,)
m
1
Vm
Um
m
m m=1
We can achieve the lower bound if we set the values of F as follows:
i-
F
m
ifi
19

---

Published as a conference paper at ICLR 2026
Therefore, the EMD between X and Y is equal 1. Then, we have that:
m
|[scu((X) - -fsuu (F)
V
uj
1=1
[[ u1) + (V2 U2) + .... (vm um)l
|/m
Um
m
m
F bolll uyll
F by lV: uy
= L dEMD (X
Therefore, for any L 0, there exist X,Y E S(R4) such that (X) SU (Y) L deMMn(X, Y). We have thus arrived at contradiction, and the SUM function is not Lipschitz continuous with respect to EMD.
B.3.5 THE SUM FUNCTION LIPSCHITZ CONTINUOUS WITH RESPECT TO THE MATCHING DISTANCE
Let X = Vv1, V2...., Vm and Y = fu, U2 ....... u₁ J be two multisets, consisting of m and vectors of dimension d, respectively. Without loss of generality, we assume that m n. Let n denote the matching produced by the solution of the matching distance function:
arg min EE
ll u.ll + || +... + ||Va())]]
Then, we have that:
[Sunn(X) -Suu
Σ Vi Σ
U1
j=1
[1(v='1) - U1 +... (V= un) + (n +... +.....+i. V=
V[ uill +... [[va)(()) unll + [+)))ll +... + [[ve=
Σ (o) u:l + | + (m)]l
Σ [1a u + || +... Ma(mm) x
min
dm (X,Y)
which concludes the proof. The SUM function is thus Lipschitz continuous with respect to the matching distance and the Lipschitz constant is equal to 1.
B.3.6 THE SUM FUNCTION NOT LIPSCHITZ CONTINUOUS WITH RESPECT THE HAUSDORFF DISTANCE
Suppose that the SUM function is Lipschitz continuous with respect to the Hausdorff distance. Let
> be given. Let also > 0 and с > Le. Let X {v1, v2J. = {uu} two multisets, consisting of 2 and 1 vectors of dimension d, respectively. Then, set and V2 = (c+E, C- ! Clearly, we have that d (X, (X,Y) Y) = max minneg[1] ||v:-u,1 ||v2 uill Vdc. We also have that:
(c.c.....)
T.
2 Σ V:
[)sua((X) - [SUN((Y)|== =
u1
1=1
20

---

Published as a conference paper at ICLR 2026
Vv1 + V2 u1l
|v2l
V(c+c)2 + (c+ + (ct
= +)(c++))
()(c+()
> vd(Le+
Lvde
= LX)
Therefore, for any L. 0, there exist X,Y E S(R)) such that (X) (Y) > Ldu(X, Y), which is contradiction. Therefore, the SUM function is also not Lipschitz contin- uous with respect to the Hausdorff distance.
B.3.7 THE MAX FUNCTION IS NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO EMD
Suppose that the MAX function is Lipschitz continuous with respect to EMD. Let L 0 be given. Yui.... , Um J be two multisets,
Then, let m = LL + 1]. Let also X = [Vi,.... VmB. each consisting of d-dimensional vectors. We construct the two such that V1 Uu V2
U2..... Vm-1 Um-11 and such that V1 +... + Vm-1 = u1 +... + Um-1 = 0. Suppose that the elements of vectors Vms Un are larger than those of all other vectors of X and Y, respectively.
Therefore, we have that [Vm]k 2 [viJA, Vi [m] and k E [d]. We also have that [um 2 [uj],
Vj E [m]] and & E [d]. Let also [/ um = 1. We already showed in subsection B.3. 1.3tt that the distance between the mean vectors of two multisets of vectors is lower bound on the EMD between them. Therefore, we have that:
m m
T
ss v
uyl
V
uj
m
m
j=1
(Vi
U1)
+ (V2 U2) +... + (Vm um))
m
1
Vm
Um
m
1
We can achieve the lower bound if we set the values of F as follows:
m if =
[
i
Therefore, the EMD between X and equal 1/m. Then, have that
[NAx(X)) - fmax
||vm umll
m
m
m
m
F by Iv.
uy
m
m
Jollv: u,ll
L (XEM)(X,Y)
Therefore, for any L 0, there exist X,Y S(R") such that [Xfxx((X fMAx(Y)) dpmp(X,, Y). which is a contradiction. Therefore, the MAX function is not Lipschitz continuous with respect to EMD.
21

---

Published as a conference paper at ICLR 2026
B.3.8 THE MAX FUNCTION IS NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO THE MATCHING DISTANCE
Let L. > be given. Let also > 0 and e > Le. Let = [v1, V2 Y = {ur} be two multisets, con- sisting of 2 and vectors of dimension d, respectively. Then, we set V1 U1 (-c, c,..., -c)....)), and V2 = (,,,,..... .T. Clearly, we have that das (X = ||v = /de. Let also Vmax and mmax denote the vectors that emerge after applying max pooling across all points of X and Y, respectively. We also have that:
[MMA((X) SMXx (
|| |mmxx Umax] ||
|| max unll
= || [ -c, c), (nnxx(
- --c,- -o)
I1(E, (((,,))..., (-c, c.... -c....,,,]]]]
(e c) + (e (e+ + c)² +... + (e 2))
d times
vd(e+e)
Va(Le+
LVde
Ld
For any > O, there exist X,y Y E ((R))) such that (X) - [Y) > Ld (x.((XY)) Y). Based
on the above inequality, the MAX function is not Lipschitz continuous with respect the matching distance.
B.3.9 THE MAX FUNCTION IS LIPSCHITZ CONTINUOUS WITH RESPECT TO THE HAUSDORFF DISTANCE
Let X = (vi, ..,..., V. B and Y I U1 U2,...: Un denote multisets of vectors. Let also
Vmax and Umux denote the vectors that emerge after applying max pooling across all points of X and Y. respectively. We will show that Vk E [d]. we have that [[Vmax] [u ]x| S du (X, Y). By contradiction, we assume that that there is some E [d] such that [V [umax | > dx, Without loss of generality, we also assume that [Vmax] 2 [umax] and therefore [Vmax lk [Umax] ]k| [Vmax]s [Umux]K-
Since [umax] 2 [uz]a- V.j E [n.]. we have that [Vmax] [ummx]a I [Vmax]e [uzJa. Vj E [n]. Since by our assumption above, [[Vmax]s [Umaxx] ]a [Vmax]] [1mmax] l > dn (X, Y), it follows that
[Vmax] li
[uyle > de (x, Vj [n]]
Note that there is at least one vector v: E X such that [vs]e [Vmaae- From equation we have for this vector that [vols - [uyla > (X Y). Vj E [n]. Then, we have ||
V ((vi) [vi]& [u,]= > (X, Y), Vj E [m]. We thus have that min ||v, 1 u, dn Y) which is contradiction since minje[n] ||v: - u,yl max minje[n] [|v, - u,حl MX, dn(X Y).
+...+ ([vs]k [uylx)² +... + ([vela (uyla)² > / ((vale [[ulk)²
Therefore, we have that [[ [aaa [umax] S (X,))
Since & was arbitrary, the above inequality holds for all ls E [d]. We thus have
[ - SMAX (Y)
= || Vmax Umax]]
([Vmax] [Mmax]] 1)²
([ Wmaa]2 ]2 - [umax]2) + +... + ( ([Vmax]e di [umax]] la)
(dy (X, 1))
(dx (X, Y)) +... (d (X,Y))
times
22

---

Published as a conference paper at ICLR 2026
- vd(dd((x)))) vā dn
which concludes the proof. Therefore, The MAX function Lipschitz continuous with respect the Hausdorff distance and the Lipschitz constant is equal to vd.
B.4 PROOF LEMMA 3.2
B.4.1 THE MEAN FUNCTION LIPSCHITZ CONTINUOUS WITH RESPECT TO THE MATCHING DISTANCE
Let N' denote set that contains multisets of vectors of equal cardinalities, i. e.c [X| = M and X SM (IR"), VX X where M N. Let X, X denote two multisets. By Proposition 2.3 we have that (x, (X,Y) MdEMD (X, Y). By Theorem 3.1 we have that:
[[MEAN(X) [YE
S dEMD (X,Y) Y)
M das (X, Y) (due to Proposition 2.3
The MEAN function restricted to inputs from set X' thus Lipschitz continuous with respect to matching distance and the Lipschitz constant is equal to N
B.4.2 THE MEAN FUNCTION IS NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO THE HAUSDORIF DISTANCE
Let X' denote set that contains multisets of vectors of equal cardinalities, i.c., |X| M and X E SMr (I2d), VX E X' where M N. Suppose that the MEAN function restricted to inputs from set X' Lipschitz continuous with respect to the Hausdorff distance. Let L > be given. Let also } be two multisets, consisting of 3
c > 0 and c > 3Lc. Let X = {V1, V2. V3), Y {ui, U2 Uz
vectors of dimension d, respectively. Then, we set V i1
5) V2 = U2
V3 ccte etc ..... ste) T and u3 have that der (X, Y) max minye:3] || uyll maxye(3] minte(3) || Uj ||va U2
(ā. .......
5) ......5))
c+c
cte) Clearly,
1|v1 usl vdde We also have that:
JMMEAN (X) FMEAN
V
1=1
i=1
(V1
u1
+
V2
U2
V33 Uz)
[/33 uall
3
1
(C c+C
c+0 -
C+ c+
c+c)
I
3
2 2
2
2
2
lllttcct.....tt
3
((e+c)+(cctt (ct 6) +... (... (c+
3
1
3
vā(c+()
3
1
Vd(3Le+ +
3
Lvde
Vde
L
2
23

---

Published as a conference paper at ICLR 2026
Ld
Therefore, for any L > O, there exist X, Y E X such that ( MYEAN(Y))l > Ldn(X, Y), which is a contradiction. Therefore, the MEAN function not Lipschitz continuous with respect to the Hausdorff distance even when it is restricted to inputs from set X.
B.4.3 THE SUM FUNCTION IS LIPSCHITZ CONTINUOUS WITH RESPECT TO EMD
Let X' denote set that contains multisets of vectors of equal cardinalities, i.e., [X] = M and X Sur (IR.), VX X where M N. Let X. X denote two multisets. By Proposition 2.3 we have that (X, Y) MdEMD X,Y, Y). By Theorem 3.1 we have that:
(X) - fsuM(Y) (Y) - dM,
d (X, Y) (due to Proposition 2.3
Therefore, the SUM function restricted to inputs from set X' is Lipschitz continuous with respect to EMD and the Lipschitz constant is equal to M.
B.4.4 THE SUM FUNCTION IS NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO THE HAUSDORFF DISTANCE
Let X' denote set that contains multisets of vectors of equal cardinalities, i.e., |X| = M and X SMr (IR"), AX e where M N. Suppose that the SUM function restricted to inputs from set X' is Lipschitz continuous with respect to the Hausdorff distance. Let L > be given. Let also
6 > and c > Le. Let X (V1, V2, V3). Y {u1, U2 Us} be two multisets, consisting of
vectors of dimension d, respectively. Then, we set V1 11 (- 2- 2..... 2
U2
(2. ...... :))= .)
V3 ( ctc
2 ..... )t0 and ug = (- 2 ctc
stc) Clearly, we
have that du (X, Y) = max minje 3) || - u,ll = maxje(3] minke[3] | - -v.-u,ll ||va Up
||v Ugl = vde
We also have that:
2
[SSUM(X) (X) SSuxi
Σ
Σ
11
1=1
1=1
|| U1 +
U2 V3 Uzl
||3 uzll
|ct c+c
c - -(- c+c c+c cto T
2 2
2
2
(lcte,cte......tt c+e
V(c+o)2 (c+ +...+ +..++(c+e)) e)²
/d(c+e)3
vd(c+e)
vd(Le+
vde L
2 (X,)
Therefore, for any L 0, there exist X, Y X' such that [X)suu(X) (Su)( > [ which a contradiction. Therefore, the SUM function is not Lipschitz continuous with respect to the Hausdorff distance even when it is restricted inputs from set X.
Ld,(X,Y),
B.4.5 THE MAX FUNCTION IS LIPSCHITZ CONTINUOUS WITH RESPECT TO THE MATCHING DISTANCE
Let X denote a set that contains multisets of vectors of equal cardinalities, i.c., X M
and X E SM (TR), VX E X' where M E N. Let X
[[1, V2,..., VM E X, and
24

---

Published as a conference paper at ICLR 2026
== fui ug..... uu B E X denote two multisets. Then, we have that:
[Xxx
([Vmax] - [1mma]]]) + ([Vmax]2 [umax]2]
([vmaxle [M (a)
(2)
Note that vk E [d]. there exists at least one E X such that [Vmnx]a = [vi]k. and also at least one u, E such that [mmax] = [uyle. Furthermore, we denote by π the matching produced by the solution of the matching distance function:
M
arg min x
Va(()) u.ll
Then, wk E [d] where [Vemu]l [Uenax] le and [Vmux] [v>(i)la> we have that:
([Vmaxls [umux lk)
(Ivor(oll [mmax]]) )
= min (IVx-(0)l [u,]k)] jE(M]
(3)
- ([Vor - [u:}k]² )
Likewise, Ak E [d] where [umax]* >> [Vmax]] la and [umax] = juilk we have that:
([Vmnx]k: [Umax]+ (x)
([Vmux]* [u:}a)]
min ([vzla [u:]s]] JE(M)
([v -u::kk)
Then, for each index pair (i), let (T)(1) {j=: [Vmax]; [Vr e [d] and S {j: [mmmx] lulli. E [d] denote the sets of coordinates at which va)(() and u, respectively, attain the coordinate-wist maximum over their corresponding multisets. Then, from equation and equation 4 we have that:
([Vmax]
lx)
+
Σ
2 [|V u,ll ([Vmaxls [Mmax])) 1x)
kESa.co
KES, (5,,()
Based on the above, we have that:
[xxx((X)- ((xx(()-xxxxx()))
v ([Ymax]i [umax]1)² + ([Nmax]2 [2max]2)² ([Vmax]at [ la)
< V[(()) - un/l + ||V=((2) u2l +...
+ || uMil
= (X,
The MAX function restricted to inputs from set X' thus Lipschitz continuous with respect to the matching distance and the Lipschitz constant is equal to 1.
B.4.6 THE MAX FUNCTION IS LIPSCHITZ CONTINUOUS WITH RESPECT TO EMD
Let X' denote set that contains multisets of vectors of equal cardinalities, e.e., |X| = M and X Sa (Rd), VX E X' where M N. Let X,Y X' denote two multisets. We have shown in subsection B B.4.5 above that:
[Suux Fn)x(()) s dx (X,Y)
By Proposition 2.3 we have that da (X,Y) = MdEMD (X, Y). Therefore, we have that:
[Mxxx(X) fMAX(()
< dd (X,Y)
M dEMD (X, Y) (due to Proposition 2.3
The MAX function restricted to inputs from set is thus Lipschitz continuous with respect to EMD and the Lipschitz constant is equal to M.
25

---

Published as a conference paper at ICLR 2026
B.5 PROOF OF PROPOSITION 3.3
B.5.1 THE ATT MECHANISM IS NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO EMD
Suppose that the ATT mechanism is Lipschitz continuous with respect to EMD. Let L > 0 be given. Let also E O and 2[++exp(de)]Le
exp(de)-1 Let X (vi, v2), Y [ui, U2] be multisets,
each consisting of 2 vectors of dimension d. Then, suppose that V1 = (e) and u2 (-c; -6, ....., _ Clearly, we have that dEarD(X (c, C, ,c.,,......) c) V2
llv - u2 =
Vdc. Let also W = -I and = 1 where I denotes the d x d identity matrix and denotes the d-dimensional vector of all ones. We define g as the ReLU function. The attention coefficients of the elements of X are equal to:
exp (1 RELU(-IVi))
exp(O)
01
Σ ブj= exp (ITRELU(-IV)
exp(0) + exp(0) 2
X exp (1 RELU(-IVE) 0
exp(0) 1
Ej=1 exp (1 RELUU-IV;))
exp(0) + exp(0)
The attention coefficients of the elements of Y are equal
at exp (1 REI.U(II::)
exp(0)
1
Σ j=1 exp (1 RELU(-Iu,) exp(0) + exp(de)
1 exp(de)
a exp (1 RELU((Ilu))
exp(de)
exp(dc)
ΣJ= exp (1 RELU(-Iu,) exp(0) + exp(de)
+ exp(de)
We then have that:
2
(Xm((X) - (NTT(V)
2
0
V
Σ
a
u
i=1
/=1
1
exp(de)
V1
+
V2
U1
I + exp(de) u2
2
1 exp(de)
exp(dc)
-1
(c, C,
T)
3 exxp(d) +1
(c, E))
2(1 + exp(de))
2(1 exp(de))
exp(de) -1 2(1 + exp(de))
(c, (,....... c,C,,....cTT
exp(de) -1
2(1 + (xp(ee)de))Le 2(1 + exp(de) exp(de) -1 exp(de) - 1 "... exp(de)
2(1 + cxx((de))
2(1 + exp(de))
L(E, [T)
2
d times
Lvde
T Iddem((XY))
We have now reached a contradiction. turns out that for any T. > 0, there exist X, Y E S(Rd), W E Rddd and q E IRd such that [X) SATT(Y) [.dEMD(X.Y). Thus, the ATT mechanism is not Lipschitz continuous with respect to EMD.
B.5.2 THE ATT MECHANISM NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO THE MATCHING DISTANCE
Suppose that the ATT mechanism is Lipschitz continuuus with respect to the matching distance. Let L >> 0 be given. Let also > 0 and 2(1+
Let X {V1, Y =(u, ug) be two
exp(de)
26

---

Published as a conference paper at ICLR 2026
multisets, each consisting of vectors of dimension d. Then, suppose that V1 u1 (c, C, ....., CT V2 = (c.,,..., <) and U2 = (-c, ......, -e)- Clearly, we have that dar (X, = V/2 U2 = 2v. Let also W = -I and = 1 where denotes the identity matrix and 1 denotes the d-dimensional vector of all ones. We choose g be the ReLU activation function. The attention coefficients of the elements of X are equal to:
at exp (1 RELU(-IVI))
exp(0) exp(0) + exp(O) 2
1
1== exp (ITRELU(-IV)))
X exp (1 RELU(-IVE)
exp(O)
Ej=1 exp (1 (1TRELU(-IV) (vy))
exp(O) +
exp(0) exp(() 2
The attention coefficients of the elements of Y are equal to:
1 exp (1 T RELU(-Iu;;)
exp(0)
Σラ= exp (1 (TTRELU(-Iu))
exp(0) + exp(dc)
1 exp(dc)
ay exp (1 RELU((Iup)
exp(de)
exp(de)
Σj=1 exp (1 (IRRLUU(-
exp(0) + exp(de)
+ exp(de)
We then have that:
[am(()) - [NTT())
Vi
u
j=1
1
exp(de)
2
Vi +
2
V2
1 exp(de)
U1
1 + exp(de)
exp(de)
-1 (c, T)T
3 exx((de +1
(E, C)
2(1 + exp(de))
2(1 + exp(de))
exp(de)
(c, (c,c,...,e)
2(1 + exp(de))
exp(de)
22 + exp(de))2Te 2(1 + exp(de))2Te exp(de) -1
2(1 + exp(de))22ee exp(de) - ...., exp(de) 1
2(1 + exp(de))
2L(c, e, c(.,,,......77 T)
2L 2 + + ......+e
d times
2L Ldd((X
Therefore, for any L > O, there exist X, Y E S(R)), w e gddd and E l such that [[fx)((X) fATT(Y)] > L dd (X, Y). Thus, the ATT mechanism is not Lipschitz continuous with respect to the matching distance.
B.5.3 THE ATT MECHANISM IS NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO THE HAUSDORFF DISTANCE
Suppose that the ATT mechanism Lipschitz continuous with respect to the Hausdorff distance. Let > be given. Let also e > and > 2(1+exm(de))2Le Let X {Vi, v2). Y = {u,, u2) be
exp(de)-1
two multisets, each consisting of vectors of dimension d. Then, we set V = u = (c, c, ,c.,,...,c))
V2 = (e,e....,E) and U2 (-e, ......, -e) Clearly, we have that d Y) < || Uz
2vde. Let also W -I and q 1 where denotes the d identity matrix and 1 denotes the
27

---

Published as a conference paper at ICLR 2026
d-dimensional vector of all ones. We choose g be the ReLU activation function. The attention coefficients of the elements of are equal to:
exp (1 PRELU(-IV))
exp(0)
2 j=1 exp (1 (ELLUU-IVV,)
exp(0) + exp(0) 2
exp (1 RELU(-IVE)
exp(O) 1
X 22
Ej=1 exp (1 RELU(-Iv,))
exp(0) + exp(0) exp(() 2
The attention coefficients of the elements of Y are equal to:
exp (1 RELU(-IU::) aY
exp(0)
2 j=1 exp DAURELLU--IUU
exp(0) + exp(de)
+ + exp(de)
Y exp (1 T RELU((IUu))
exp(de)
exp(de)
Ej=1 exp (1 RELU(-I))
exp(0) + exp(de)
+ exp(de)
We then have that:
[am((X) - fATT(Y)
Σ
Vi Σ
a uj
i=1
j=1
1
exp(dc)
V1 +
2 V2
1 + exp(de) u2
1 exp(de)
exp(de)
3 exxp(de) + (c, (T
(c,cs...,c.)
2(1 + exp(de))
2(1 + exp(de))
exp(dc) (c, (c.,...,,)
2(1 + exp(de))
exp(dc)
(2(1 exp(de))2Le 2(1 + exp(de))2Te exp(de) -1
2(1 + exp(de))2Te exp(de) 1
2(1 + exp(de))
exp(de) -
2L 2 +
times
=T
-X,x(X,
Therefore, for any L > 0, there exist X,Y S(RA). W E Raxd and q E Rdd such that [| (X) fxm (Y)Il > L Lda((X, Y), which is contradiction. Therefore, the ATT mechanism is not Lipschitz continuous with respect to the Hausdorff distance.
B.6 LIPSCHITZ CONTINUITY OF ATT,, MECHANISM
We demonstrate here that the attention mechanism is not Lipschitz continuous with respect to the considered functions, even when & attention used. Given a multiset X = [[v....., V. E S(Rd), the attention mechanism is defined follows:
fATTE, (X) = Σ a.V, where
m
exp
|| 9 W v;) l 9 W v,)
0;
TM レ exp
where W E Rdd xd and q E Rd denote a trainable matrix and trainable vector, respectively. while g denotes some activation function.
28

---

Published as a conference paper at ICLR 2026
B.6.1 THE ATT,, MECHANISM IS NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO EMD
Suppose that the ATT2, mechanism is Lipschitz continuous with respect to EMD. Let L be given. Let also 0 and 2[1+exp(-
1 1-exp[- ddr) Let X {V1, Y {u, U2) be two multisets, each consisting of vectors of dimension d. Then, suppose that V1 = uı u1 = (c, .)...,,,
V2 (c) and u2 (-c, - -e) Clearly, we have that dgMDD(X,Y)
V2
u2 = vdc. Let also W = -I and q (-c, - -e) where denotes the d x d identity matrix. We define 9 as the ReLU function. The attention coefficients of the elements of X are equal
to:
exp
(
RELUU (-Iv))
exp ( ||al))
j=1 exp
q - RELU(-IVv))
exp
|q] + +eep (
(q
exp
| RELU( (
Iv2)
exp
||q
02
Σj=1 exp
RELU(-Ivv)))
exp
| exp
( (- --|all)
2
The attention coefficients of the elements of Y are equal to:
Y
exp
-
q REL.U(-Tu))])
exp
|
exp(-vid
Σ 2j=1 exp
10 (-
exp
9 + exp((0)
1 1 exp( (ved)
exp
(-1
||q RELLU [u,)
exp(O)
02
Σラ= exp
||q RELU(-Iu;)]]
exp(0) exp ( (- 1-11
1 + exp(p-veir
We then have that:
[FATres (X) fATTe, (2)
Σ 0
Σ aj u
i=1
1
exp( - Vdd)
2 2 V2
V1 +
U1
1 ++ exp( exp(- -V
1 expp - v de)
1 - exp( - Vdc)
cxp( - dc)) +
(c.C....,C.
2(1 + (-p(--ddc)) (E, (e)))...,,)TT)
2(1 + exp( Vdc))
1 - exp( - Vde)
(c.Cc...,,.) ,c)
2 + exp( dde)
1 1 exp( (dcc)
22 + exp(- - /de(-
2(1 + exp(- /dc(-vde))LL
2(1 + exp( vdee)
- exp(-vVii
1 - exp(-v -Vde)
L(E,6, L(E,E,...,
L 2 + 2 +...+
d times
LLvde
= L (_dEM((XY))
We have now reached a contradiction. turns out that for any L L> 0, there exist X,Y Y E S(R)), W aaxd and q Idd such that [[ (X) fArT, (Y)ll > Yd) Thus, the ATT mechanism is not Lipschitz continuous with respect to EMD.
B.6.2 THE ATT,, MECHANISM IS NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO THE MATCHING DISTANCE
Suppose that the ATT, mechanism is Lipschitz continuous with respect to the matching distance.
Let L > 0 be given. Let also e > 0 and e > 2(1+ex((-Vie)22ee Let X V2), Y =
[-exp_-Vde)
29

---

Published as a conference paper at ICLR 2026
{ui, U2) be two multisets, each consisting of 2 vectors of dimension d. Then, suppose that V1 u1 = (c. (c. c) V2 = (c, c......) and U2 = (_c, - .......,,......... Clearly, we have that dx,(X,)) = 1|v اzll = 2
de. de. Let also W = and q q= (-c,- -.. -c) where I denotes the d d identity matrix. We choose g be the ReLU activation function. The attention coefficients of the elements of X are equal to:
exp
RELU( (vv))
exp
||
a1
j=1 exp
qq RELUU-IVV)]]
exp (-
| | + exp ( (- [|
exp
|q RELLU(IIvv]]
cxp
||9]))
2
Σ} exp
RELU(-Ivv)))
exp
| exp
( ||9]) 2
The attention coefficients of the elements of Y are equal to:
y
exp
-
q RELU(-IU,))
exp
exp(-v/o
== exp
|| RELUE
(II
exp
q () + exp(0)
1+ exp( -vdc)
ax exp (-
|| q- D--RELU(-TR [
exp(O)
Σ== exp
1 + exp(p exp(-vve) || Po--Ra R exp(0) + exp ( ||lll)
We then have that:
2
2
[ATTO, (X) -fATT, (n)
Σ
a V Σ
y u
i=1
j=1
expl - vde(-Vde)
2 V1 +
V2
U1
U2
2
1 exp( -Vde)
1 expl v dee
1 exp( Vde)
exp(-vde Vde) +3
(c. (GCC..... cc.,...,))
(E, (E,
2(1 + exp( Vde))
2(1 exp(- exp(-Vde))
1 exp( Vee)
(c, (e.C,..... (c,Cg...,))
2(1 + exp( Vde))
- exp( vdee
(2 + exp( - Vdde))2ee
2(1 exp( -ile))) expeexpviii -Vee
2(1 + exp( -dee)
- 1-exp( Vdee)
2L(e, T)T
2L 2 + 2+ +
d'iines
2L
(X,)
Therefore, for any L > O. there exist X,Y S(R4), w E Radd and q E Rd such that [1 (X) - fATTES (Y)Il Ld (X,Y). Y). Thus, the ATT;, mechanism is not Lipschitz continu- ous with respect to the matching distance.
B.6.3 THE ATT&, MECHANISM IS NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO THE HAUSDORFF DISTANCE
Suppose that the ATT mechanism is Lipschitz continuous with respect to the Hausdorff distance.
Let L > 0 be given. Let also e > 0 and > 211+ex((VVde)2L Let X = {V1, v2). Y =
--exp(-vde)
{u,, 32} be two multisets, each consisting of vectors of dimension d. Then, we set Vi = U1 =
(c, G, ......00 e)T V2 (e, 6)) and u2 (-c, - -e) Clearly, we have that di X Y) S
30

---

Published as a conference paper at ICLR 2026
|/2 -ull de. Let also W - and q 1 where I denotes the d x identity matrix and denotes the d-dimensional vector all ones. We choose g to be the ReLU activation function. The attention coefficients of the elements of X are equal to:
exp
RELU(-IUVI -vv))l
exp
||ll))
a1
jj=1 exp
2
qq RELU exp (-
||
+ exp ( (- (-1|a]) 2
exp ( q
exp
||a]))
1
02
Ej=1 exp
RELU(-Iv,)))
exp
||]l) exp
(- |[]]))
2
The attention coefficients of the elements of Y are equal to:
exp
RELU (I)
exp
1
exp( exp(-vde)
0
Σ 1= exp
||q RELU (-LLU 11;)
exp
[ + exp(0)
1 1+ exp( -Vdde
0i exp (-
||9 [/l--RA --RELUU-- (
exp(0)
5= exp
q RELUR (u)))
exp(O) + exp ( (- [|ql])
1 +
We then have that:
2
[aTres (X) SATTer (1)
Σ
aj Uj
i=1
1=1
1
exp( -Vde)
2 1 +
V2
111
2
1 exp(-ppppp (Vdc)
1 exp( - v dc)
1 - exp( Vdte
CC,C, (c.c....,c) [])
2(1 - exp(-vde)) (E, (c)e)...,6)T]
expl -opl-vde- +
2(1 + exp( dee)
1 - exp( Vdc)
(c.c, (c. c
2(1 + exp( vde))
1 - exp( - Vde)
2(( + expl- - exp(-vde))2Le
2(1 + exp((v exp( - ddc)
2(1 + exp( ddc)
- expl ddc)
21 2I(
2L
2 + +... +
times
2L
(XH(XX
Therefore, for any L > O. there exist X,Y E S(R4), W E Baxd and q E IRd such that f (X) JArTe (Y)ll LX, which is contradiction. Therefore, the ATT2, mech- anism is not Lipschitz continuous with respect to the Hausdorff distance.
B.7 PROOF OF THEOREM 3.4
B.7.1 THE NNMEAN MODEL IS LIPSCHITZ CONTINUOUS WITH RESPECT TO EMD
Let X (V...... V......... B. Y [u..... u, be two multisets of vectors. Let also Lip(fMLr and Lip(SMuP,) denote the Lipschitz constants of SMP,, and fMIP,, respectively. Finally, let F denote the matrix that minimizes dEMD(X; Y). Then, we have:
fMLP2
1 Σ 17
FMLP, (vi)) fMLP2
[ Σ m
fMLP, (1)) Lip(SMLPZ)
Σ m
fMLP, (v:)
Σ SMP
n
31

---

Published as a conference paper at ICLR 2026
m7
Lip(
Jeil//MPP (v.) - fMIP, (vz)]
(due to Theorem
m
n
$ Lip(f
Σ
Σ
F Lip( - -vyl
==1
Lip(/MMP, Lip((MML
Σ Jell.... -vll vyll
Lip(fMLP, Lip (MLii((MM,))da (dE
Note that whether the above hold an equality depends SMIP, and [MLP,, and therefore, the Lipschitz constant of the MEMEAN model is upper bounded by Lip(fMLP,)Lipp Lii deE Y).
B.7.2 THERE EXIST NNMuM MODELS WHICH ARE NOT LIPSCHITZ CONTINUOUS WITH RESPECT TO THE MATCHING DISTANCE
Suppose that NN is neural network model which computes its output as follows:
Vx f2 RELLU (.RRLLLU (( ((mm)))
where X = Kei..... Um is a multiset of scalars, and fi and fa are fully-connected layers, i. c., (xr 01 x + bi and f2(2) 02 b2. Furthermore, suppose that a 0, b > 0 and 02 0. Note that the Lipschitz constants of f1 and f2 are Lip(fi) = 01 and Lip(f2) = 02 respectively.
Suppose that the NN model is Lipschitz continuous with respect the matching distance. Let L > 0 be given. Let also X = {V,, 02 Y 4uiB be two multisets that contain real numbers. We construct the two sets such that 01 = V2 = #n = c where <c< by. Thus, we have that (X, Y) |c| = c. We also have that b1 L La. Then, we have:
Daj
Σ (((e)) S2 (n())
2
Rel.U(anc+bi)) - S2 [el..((r bi))
f2
f2
1=1
Ja (2( sa(aretbi)
a2 (2) + b2 as ae(arctbi) b2
lag(arc+bill
I[L+1)a2 el
(L + Li)p(( Lip((f)
Therefore, for any L > 0, there exist X, E S(R") such that (Evex
fa Euey fu( > Lip((2) Lip(f) das (X, Y). Based on the above, there exist NN mod- els which are not Lipschitz continuous with respect to the matching distance.
B.7.3 THE NNMAX MODEL IS LIPSCHITZ CONTINUOUS WITH RESPECT TO THE HAUSDORFF DISTANCE
Let X = [VI...., Vn Y fu...... un B be two multisets of vectors. Let also Lip(fMe,,) and Lip(fMLPZ) denote the Lipschitz constants of fMLP, and fMLP. respectively. Let SMPP, (X)= (vI), SMUP, (vm) } and /MIP,, (Y) {{ [MIP, (ui).... SMIP, (u.) }. Let also (JMLP, (X)) max and (SMLP, (Y) max denote the output of the max operator applied to mul- tisets SMIP, (X) and fVIP, (Y), respectively. Without loss of generality, also assume that h [MMP,, (X), SMUP,, (8) h (M) SMLP, (MLL, (X)). Then, we have:
SMLPSS (JJMLP) (8))mos)
SMIP (UMLP (V)) max) )
< Lip(JMPPz)) (JMLP, (v:)) max (JMLP, (u,)) max
32

---

Published as a conference paper at ICLR 2026
I Lip(fMee,) )V dh (fNLP, (X), fULP. (2)) (due to Theorem 3.1
VaLip(fMLP,) max min ie(m) JEInl [MLL, (v.) - SMLL,
VdLip(/MMP;
max min l|v: u,ll
ie se(m]jejy jE(n)
S VdLip( (Lp )dH (X,Y)
We have thus shown that the NNMAX model is Lipschitz continuous with respect to the Hausdorff' distance and its Lipschitz constant is upper bounded by vdLip(fMuu Lip(::))))
B.8 PROOF OF LEMMA 3.5
B.8.1 THE MEAN MODEL IS LIPSCHITZ CONTINUOUS WITH RESPECT TO THE MATCHING DISTANCE
Let X' denote set that contains multisets of vectors of equal cardinalities, i.e., |X| .M and X E S(R*), VX E X' where M E N. Let X,Y X' denote two multisets. We have shown in subsection aabove that:
SMLP2
1
SMpP, (vi)
SMIPP
1
Σ SMLP, (u;) <
X, Y)
By Proposition 2.3
we have that dr dd(XX,y (X,Y) = MdEMD Y). Therefore, we have that:
fMLP:
1 (1)
Σ fMLP, (vi))
fMLPA
Σ
fMLP, (u,)
S Lip(fMre, )ip((MLP JEMDD Y)
m
Lip(SMLP, Lip
(hip(fMLzgddd (X, (due Proposition 2.3
The NEME model is Lipschitz continuous with respect to the matching distance and its Lipschitz constant is upper bounded by Lip(fMuL, Liinr::))p((((ae)
B.8.2 THE NNsuM MODEL IS LIPSCHITZ CONTINUOUS WITH RESPECT TO THE MATCHING DISTANCE
Let X' denote a set that contains multisets of vectors equal cardinalities, i.e., |X| = M and X S(R"), VX X' where M E N. Let Y E X' denote two multisets. Let σ² denote the matching produced producedd by the solution of the matching distance function:
π arg min REGM
Vi(()) u,ll
Then, we have:
M
Σ
SMLP, (v:)) fMLP2
Σ fMLP, (u,)
< Lip(fMLPZ)
Σ fMLP, (v:) - -- fULP. (u,)
M
= -ip(fMMLP.)
(fMLP, (v= - fMPP. (ui)
==1
< Lip(fMLrz)
Σ fALLP, (v--(e) fNaP, (u.)
< Lip(fMMLe)
Σ Lip(fMur )IV u.ll
M Σ
< Lip(fMLP, (ip(fe,P)
[V u,|
i=l
33

---

Published as a conference paper at ICLR 2026
Lip(fMLP, (ip((f )d (X,Y)
which concludes the proof. The NN model is thus Lipschitz continuous with respect to the matching distance when the inputs are restricted to multisets of a fixed size, and its Lipschitz constant is upper bounded by Lip(fMLP; Lip(fMuPa):
B.8.3 THE NUM MODEL IS LIPSCHITZ CONTINUOUS WITH RESPECT TO EMD
Let X' denote set that contains multisets of vectors of equal cardinalities, e.e., |X] = M and X E S(R"), VX E where E N. Let X,Y X' denote two multisets. We have shown in subsection B.8.2lbovve that:
M Σ
FM (ve)) fMIP2 Σ faLP, (u,)) - Liip((Ar
By Proposition
2.3 we have that (xr(X,)) = M MceMD(X,X) YY. Therefore, we have that:
A
M
JMLPP
SMLP, (v:))
SMIP2
Σ
SMLP, (15))
< Lip(///an,)iip(UMnn).dd..... (X,
Maiip(/Mr,))ii((((M dEED (X, Y) (due Proposition 2.3
Therefore, the NNsuM model is Lipschitz continuous with respect to EMD and its Lipschitz constant upper bounded by MLip(/MMP, (ip((M))))((((
B.8.4 THE NNMAX MODEL IS LIPSCHITZ CONTINUOUS WITH RESPECT TO THE MATCHING DISTANCE
Let X denote set that contains multisets of vectors of equal cardinalities, i.e., |X M and X E S(RR), VX E X' where M E N. Let X, Y X' denote two multisets. Let SMLP, (X) H/MLPI (v1)...., SMLP, (vm) }} and SMLP, (Y) = {l (u,), (MM),, (u,) I/- Let also ((ML,(()) max and (JMLP, (Y)) max denote the output of the max operator applied to multisets SMIP, (X) and SMI.P, (Y), respectively. Let nT denote the matching produced by the solution of the matching distance function:
M
म arg min FEGM
Vi(()) - u,l
Then, we have:
SMPPS (JhNLes (x)) max) SMIPP (UrAL (X)) m)x)m Lip(Smee)) ||| (fMLL (X)) max (fMLP, (Y)) max
Lip(SMEP, )d (NLLP, (X)) fMLLP (X3) (due Lemma 3.2
< <Lip(Mmee)
SMLPS (Vm-co) - INLLI
A
< Lip(fMuP.)
Lip(SMur Mll.r u,ll
M
< Lip(SMu, Mip((MMP.)
Vi uill
Lip(SMe,, Mip([Napp))))) (X,Y)
We conclude that the NNMx model Lipschitz continuous with respect to the matching distance and its Lipschitz constant is upper bounded by Lip( (ip((M)))))
34

---

Published as a conference paper at ICLR 2026
B.8.5 THE NNMAX MODEL LIPSCHITZ CONTINUOUS WITH RESPECT TO EMD
Let X' denote set that contains multisets of vectors of equal cardinalities, i.c., [X] M and X E S(Rd), vX E A' where M E N. Let X,Y E X' denote two multisets. We have shown in subsection B.8. above that:
[ ( (JNLLP (v:)) max) SMLPP (JMMP), (u,)) maxx)
(x
By Proposition 2.3 we have that (X, Y) = M X, Y). Therefore, we have that:
JuLLss (FhALP (vi)) mix) fNALPa (FFNLL (u;)) (u;)) max) S Lip(SMLP, MLpp(Mu
MLip(fMLP, (LLipp/MM/p))) )dEMD (X, Y) (due Proposition 2.3
We thus have that the NNMAx model is Lipschitz continuous with respect to EMD and its Lipschitz constant is upper bounded by M Lip(SMuP, (.p(....))
B.9 PROOF OF PROPOSITION 3.6
(1) Let F R1x(a+1) be matrix. We set the elements of F equal to the following values:
i
m(n+1)
F by
if i-
otherwise
Then, we have that:
F bs > 0,
isisn, 1si$n+1
FF]
1sisn
1
>
F
1șjšn+1
1
1=1
Therefore, F is feasible solution of the EMD formulation and its value is equal to:
Fly [|: vyl n(n + 1)
1|= wolll
We thus have that:
dEMD(X,X)) < nen + 1) Σ lv. Vntill
A simple case where the inequality holds with equality is when Vi =2 Vn = Va+l.
(2) The bidirectional Hausdorff distance between X and X' is defined as:
dh (X, = max (l(X, X'), (xX,xx))
For each i E [r)], we have that minje[u+1] ||: v5l = ||v vill = 0. Therefore, we have that:
M(X,')=
max min ||v: vill 0 *E[m] jE[++1]
We thus obtain the following:
du X') X') = X)
max min |V, vill iE []
For each i [n], we have that minfe[m] ||v: - vyll = =|v, - vill = 0. Therefore, we have that:
dn(XX = h(X', (X',X)
=min V vyll JEin]
35

---

Published as a conference paper at ICLR 2026
C STABILITY OF NEURAL NETWORKS FOR SETS UNDER PERTURBATIONS
implies that the output variation of NNMEAN. NNsuM and NNMAX under perturbations of the elements of input set can be bounded via the EMD, matching distance and Hausdorff distance between the input and perturbed sets, respectively. We next investigate what are the values of EMD, matching distance and Hausdorff distance when an element of multiset is replaced by new element.
Lemma 3.5
Proposition C.I. Given multiset of vectors X (Vi...., Vi-1i Vo Vitls..., Vn E S(R*), let X" = V..,...., Vi-i,, V4 Vi+l...., Vn E S(R4) be the multiset where element Vi perturbed to v Then.
1. The EMD and matching distance between X and X' are equal
(EMD(X,X)) ||v v'll and dx(X, X') 11ve vill
2. The Hausdorff distance between X and X is bounded as:
dn(X,, X') S 1|v; v'll
Proof. (1) We set 11 V1, V2.
V/p Un = Vn- For the matching distance, we
have:
da (X))
min =
V u,ll
i=1
vill + + llv, v.,ll || v1 || V2ll +...+ + llv,
V vill
Suppose that x² E , the permutation associated with dM(XXX Then, we have:
1[ v/ll= = || + + + Vn
v/ vnll
Vn U1 -... u, u.ll - [\ - unl +...+ + ||ve-(0 - u:/l +.... + || - u
||v1 + V,
= dx,
||: v'll and that ||v: (X,(X, X') = l|v, - v/ll. Since | | n, by Proposition 2.3
We showed that dx(XXX))
dm(X,X)). Therefore, we have that dx,
dEND X, X'). The following then holds:
dEM,(X, = l|v vill
(2) We set U1 = V1, U2 V2, V...... u; v/ .... Un Vn- The Hausdorff distance equal to:
du X') max (XX,,
For each j E 1J 1...., n), we have that minke(m) ||v; uz = ||V, -vyll = 0. For each
j j - 1 ti + 1, n., we also have that minke(n] [n] [uj vxll = || - v, = 0. Therefore,
we have that:
X') = min |v: uzلl
uill = ||: vill
jEbm]
1(X, = min SEbn]
|Iu v5ll u, vell = ||: vill
Both 6(X,')) and A(X',X) are thus no greater than ||v: - v/ll. We then have that:
d (X, = max (h(X, X'), (xX' x))
< max (Ilv; - v/ll. l|v vill)
= ||v - -Vll
36

---

Published as a conference paper at ICLR 2026
We next investigate what the values of EMD, Hausdorff distance and matching distance when random vector sampled from (0, k) added to each element of a multiset.
Proposition C.2. Given a multiset of vectors X = Vv.. V2, Vn E S(RR), let X' vv + U1 V2 u2,....; Vn + Un J E ((R)) where ~ U(0, k) for all i E (m). Then,
1. The EMD and matching distance between X and X' is bounded as:
dEMD d (X, X') S kvd and
dx(X,X') S nkvd
2. The Hausdorff distance between X and X' is bounded as:
dx(X,X') S kVd
Proof. (1) Note that
||: - V. - uzll
||u:|| S
2 + + + k2 = kVd
For the matching distance, we have:
dx((X,X)) = min
Vi((s) - -.- -u,ll
VI - Vi - u1ll + 1| - V2 U2l
+ ||v +...
Vn - u,
uill + || uzll +... un!l
kv + lvd ... kVd
nkvd
Since X| | = n, by Proposition 2.3 we have that dxr(X, = n dEMD(X, X'). The
following then holds:
DEMD (X, X') LLMD(X,X)
1 -
- kVd
n
(2) The Hausdorff distance is equal to:
dh (x, max (xxX,')) x(X'x))
We have that:
M(X,'') max min |[, Vj -uil S max
V; - V; - u;| = max <E(m
- u; S kvd
sE jE(n]
iE[n
4(X',X)
max min ||, + u: vyll
max EE|n]
V + u; vall max
kvd
kE ]E(n]
<E(n)
Both h(X,')) and h(X', X) are thus no greater than kyd. We then have that:
d (X) max (h(X, X'), x()'xx)
$ max (kvd,kva
= kkd
37

---

Published as a conference paper at ICLR 2026
D EXPERIMENTAL SETUP
We next provide details about the experimental setup in the different experiments we conducted.
D.1 LIPSCHITZ CONSTANT OF AGGREGATION FUNCTIONS
ModeINet40. We produce point clouds consisting of 100 particles (I, y/ zccorddinns)))) from the mesh representation of objects. Each set is normalized by the initial layer of the deep network to have zero mean (along individual axes) and unit (global) variance. Each neural network consists of an MLP, followed by an aggregation function (i. e., SUM, MEAN or MAX) which in turn is followed by another MLP. The first MLP transforms the representations of the particles, while the aggregation function produces a single vector representation for each point cloud. The two MLPs consist of two layers and the ReLU function is applied the output of the first layer. The output of the second layer of the second MLP is followed by the softmax function which outputs class probabilities. The hidden dimension size of all layers is set 64. The model is trained by minimizing the cross-entropy loss. The minimization is performed using Adam with a learning rate equal to 0.001. The number of epochs is set to 200 and the batch size to 64. At the end of each epoch, we compute the performance our final model the one that achieved the
of the model on the validation set, and we choose smallest loss on the validation set. Note that in this set of experiments we do not compute the EMD, Hausdorff and matching distance between the input multisets, but we compute the distance of the "latent" multisets that emerge at the output of the first MLP (just before the aggregation function is applied) of each chosen model.
Polarity. We represent each document as a multiset of the embeddings of its words. The word em- beddings are obtained from a pre-traines model which contains 500-dimensiooal vectors (Mikolov et al. 2013). The embeddings are first fed to MLP, and then aggregation function (i. c., SUM, MEAN or MAX) is applied which produces a single vector representation for each document. This vector representation is passed onto another MLP. The two MLPs consist of two layers and the ReLU function is applied to the output of the first layer of each MLP. The output of the second MLP is followed by the softmax function. The hidden dimension size of all layers is set to 64. The model is trained by minimizing the cross-entropy loss. The minimization is performed using Adam with a learning rate equal to 0.001. The number of epochs is set 200 and the batch size to 64. At the end of each epoch, we compute the performance of the model on the validation set, and we choose as our final model the one that achieved the smallest loss on the validation set. As discussed ahove, in each experiment, we compute the distance of the "latent" multisets that emerge at the output of the first MLP (ust before the aggregation function is applied) of the model that achieves the lowest validation loss.
D.2 LIPSCHITZ CONSTANT OF NEURAL NETWORKS FOR SETS
ModelNet40. We produce point clouds with 100 particles (z, y, 2-coordinates) from the mesh rep- resentation of objects. The data points of the point clouds are first fed to fully-connected layer. Then, the data points of each point clouds are aggregated (i. e., SUM, MEAN MAX function is utilized) and this results into a single vector representation for each point cloud. This vector repre- sentation is then fed to another fully-connected layer. The output of this layer passes through the ReLU function and is finally fed to fully- fully-connected layer which is followed by the softmax func- tion and produces class probabilities. The output dimension of the first two fully-connected layers is set to 64. The model is trained by minimizing the cross-entropy loss. The Adam optimizer is employed with a learning rate of 0.001. The number of epochs set to 200 and the batch size to 64. At the end of each epoch, we compute the performance of the model the validation set, and we choose as our final model the one that achieved the smallest loss on the validation set. Note that the Lipschitz constant of an affine function : v + Wv + b where W E pm and b R" is the largest singular value of matrix W. Therefore, in this experiment we can exactly compute the Lipschitz constants of the two fully-connected layers.
Polarity. We represent each document multiset of the embeddings of its words. The word embeddings are obtained from a publicly available pre-trained model (Mikolov et al. (013). We randomly split the dataset into training, validation, and test sets with 80 10 10 split ratio. The
38

---

Published as a conference paper at ICLR 2026
embeddings are first fed to fully-connected layer, and then aggregation function (i. SUM, MEAN or MAX) is applied which produces a single vector representation for each document. This vector representation is passed onto another cunnecco layer. The ReLU function is applied to the emerging vector and then a final fully-connected layer followed by the softmax function outputs class probabilities. The output dimension of the first two fully-connected layers is set 64. The model is trained by minimizing the cross-entropy loss. The minimization is performed using Adam with a learning rate equal 0.001. The number of epochs is set to 200 and the batch size to 64. At the end of each epoch, we compute the performance of the model on the validation set, and we choose as our final model the one that achieved the smallest loss on the validation set. As discussed above, we can exactly compute the Lipschitz constants of the two fully-connected layers.
D.3 STABILITY UNDER PERTURBATIONS OF INPUT MULTISETS
ModeINet40. We produce point clouds with 100 particles (x, y, z-coordinates) from the mesh rep- resentation of objects. The MFAN and NN models consist of MLP which transforms the representations of the particles, an aggregation function (MEAN and MAX, respectively) and sec- ond MLP which produces the output ei. class probabilities). Both MLPs consist of two hidden layers. The ReLU function is applied to the outputs of the first layer. The hidden dimension size set to 64 for all hidden layers. The model is trained by minimizing the cross-entropy loss. The Adam optimizer is employed with learning rate of 0.001. The number of epochs is set to 200 and the batch size to 64. At the end of each epoch, we compute the performance of the model on the validation set, and we choose as our final model the one that achieved the smallest loss on the validation set.
Polarity. Each document of the Polarity dataset is represented multiset of word vectors. The word vectors are obtained from a publicly available pre-trained model (Mikolov et al. 2013). We randomly split the dataset into training, validation, and test sets with a 80 10 10 split ratio. The NNMEAN and NNMAx models consist of an MLP which transforms the representations of the words, an aggregation function (MEAN and MAX, respectively) and a second MLP which produces the output. Both MLPs consist of two hidden layers. The ReI.U function is applied to the outputs of the first layer. The hidden dimension size is set to 64 for all hidden layers. The model is trained for 20 epochs by minimizing the cross-entropy loss function with the Adam optimizer and a learning rate of 0.001. At the end of each epoch, we compute the performance of the model on the validation set, and we choose our final model the one that achieved the smallest loss the validation set.
D.4 GENERALIZATION UNDER DISTRIBUTION SHIFTS
This set of experiments is conducted on the Polarity dataset. The architecture of NNMEAN and NN and the training details are same as in subsection above.
E ADDITIONAL RESULTS
E. LIPSCUITZ CONSTANT OF AGGREGATION FUNCTIONS
We next provide some additional empirical results that validate the findings of Theorem 3.1 (i. e., Lipschitz constants of aggregation functions). We experiment with the Polarity dataset. Figure 4 visualizes the relationship between the output of the three considered distance functions and the Euclidean distance of the aggregated representations of multisets of documents from the Polarity dataset. Since the Polarity dataset consists of documents which might differ from each other in the number of terms, by Theorem 3.1 we can derive upper bounds only for 3 out of the 9 combinations of distance functions for multisets and aggregation functions. As expected, the Lipschitz bounds (dash lines) upper bound the Euclidean distance of the outputs of the aggregation functions. With regards to the tightness of the bounds, we observe that the bounds that are associated with the MEAN and SUM functions are tighter than the one associated with the MAX function. The correlations between the distances of multisets and the Euclidean distances the aggregated representations of multisets are relatively low in most of the cases. All three distance functions are mostly correlated with the aggregation functions with which they are related via Theorem The highest correlation is achieved between EMD and the MRAN function (r 0.89).
39

---

Published as a conference paper at ICLR 2026
30
125
30
r-0
1.2
30
12.5
0.36
50
200
30
12.5
10
0.m
Figure 4: Each dot corresponds a pair documents from the test of Polarity that is represented as a multiset of word vectors. Each subfigure compares the distance between the latent represen- tations of pairs of documents computed by distance function for multisets (i. e., EMD, Hausdorff distance matching distance) with the Euclidean distance between the representations of the pairs obtained after applying an aggregation function ei. MEAN, SUM or MAX). The correlation be- tween the two distances is also computed and visualized. The Lipschitz bounds are illustrated with dashed lines.
E.2 UPPER BOUNDS OF LIPSCHITZ CONSTANTS OF NEURAL NETWORKS FOR SETS
We next provide some additional empirical results that validate the findings of Theorem upper bounds of Lipschitz constants of neural networks for sets). The results are shown in Figure 5 Since the Polarity dataset consists of documents which might differ from each other in the number of terms, by Theorem 3.4 we can derive upper bounds only for 2 out of the 9 combinations of distance functions for multisets and aggregation functions. While the dash lines upper bound the Euclidean distance of the outputs the aggregation functions, both bounds are relatively loose on the Polarity dataset. The correlations between the distances of the representations produced by the neural network for the multisets and the distances produced by distance functions for multisets much lower than those of the previous experiments. The highest correlation is equal 0.55 (between the neural network that utilizes the MEAN aggregation function and EMD), while there are even negative correlations. This surprising since for most of the combinations, there no upper bounds on the Lipschitz constant of the corresponding neural networks.
(i.
We also visualize the relationship between the output of the three considered distance functions and the Euclidean distance of the multiset representations that are produced by a neural network that utilizes the attention mechanism that presented subsection 3.1 Specifically, the neural network is identical to N NN and NNMAx. but instead of the standard aggregation functions, it em- ploys the aforementioned attention mechanism. The experiments are conducted on the ModelNet40 dataset and the results are shown in Figure 6 We have shown that the attention mechanism is not Lipschitz continuous with respect to any of the three considered distance functions, and therefore the neural network models that employ this mechanism also not Lipschitz continuous. We ob- serve in 6 the correlations are indeed much lower than those illustrated in Figure which confirms theoretical result.
40

---

Published as a conference paper at ICLR 2026
30
0.0555
01
30
r-00
20
20
20
bound LIU M.
20
10
10
4.5.7
AK2 99
Figure 5: Each dot corresponds to a pair of documents from the test set of Polarity that is represented as multiset word vectors. Each subfigure compares the distance between the pairs of documents computed by distance function for multisets (i. EMD, Hausdorff distance or matching distance) with the Euclidean distance between the representations of the pairs that emerge at the second-to-lan layer of NN MEAN, NNsuM or NNMAX. The correlation between the two distances also computed and visualized. The Lipschitz bounds are illustrated with dashed lines.
7- 0.56
C- 2.56
0.00
0.0
0.5
3.0
3.0
30
100
250
2000
250
200 250
Figure 6: Each dot corresponds a pair of point clouds from the test set of ModelNer40. Each subfigure compares the distance between the pairs of point clouds computed by EMD, Hausdorff distance or matching distance with the Euclidean distance between the representations of the pairs that emerge at the second-to-last layer of neural network that consists of fully-connected layer, an attention mechanism that aggregates the representations of the elements and two more fully- connected layers. The correlation between the two distances is also computed and visualized.
E.3 STABILITY OF NEURAL NETWORKS FOR SETS UNDER PERTURBATIONS
Here we provide some further details about the experiments presented in subsection Specifically, for the experiments conducted on ModelNet40, we attribute the drop in performance of NN to the large Hausdorff distances between each test sample and its perturbed version. For each test sample X, (where E [2468), let X denote the multiset that emerges from the application of Pert. #1 to X,. Let also y denote the class label of sample X₃. We compute the Hausdorff distance between X, and X ei d (X,, We then compute the average Hausdorff distance between X, and the of the test samples that belong the same class X,. Let S: (X,: j [2468), yi y3}
41

---

Published as a conference paper at ICLR 2026
Accuracy
discreparcy Wi (ta) dear
bodss
9/61
19.2
15.6
books
0
1.90
2.08
2.07
thd
24.9
22.7
6v
1.99
2.37
ebcono
27.5
10
2.07
2.37
2.28
books
kichhn
Acnurary drop N.
Demain discrpancyy Wilps po) with du
bolis
11.2
15.9
14.3
3.83
3.92
3.88
ded
de
destvrr
17:1
kiddwn
21.5
21.5
17.0
3.03
4,1
3.92
books
dedtonka
looks
dedtanka
kiuler
Figure 7: Accuracy drop of the NNMEAN and NN models, and Wasserstein distance with = between groups when the EMD and the Hausdorff distance used ground metrics.
denote the set of all test samples that belong to the same class as X, Then, we compute di (X,, S;) as follows:
dH = |S -1
E dn(X,, YESA(X.
We then compute dH dx,,, X;) (H, this value is positive, then the distance from X, to X is greater than the average distance of X; to the other multisets that belong to the same class as X,. We calculated this value for all test samples and then computed the average value which was found to be 2. 2.63
In general, the perturbation increases the upper bound of the Lipschitz constant of NNMAX compared the upper bound for samples that belong to the same class, and thus X, and X might end up having dissimilar representations. On the other hand, for EMD, the average distance is equal to -1.18 (..1820..2) 72). For EMD the upper bound is in general tighter than the bound for pairs of multisets that belong the same class, and this explains why MEAN is robust to Pert. #1.
E.4 GENERALIZATIO UNDER DISTRIBUTION SHIFTS
To evaluate the generalization of the two Lipschitz continuous models (NNMEAN and NN NN under distribution shifts, we also experiment with the Amazon review dataset (Blitzer et al. 2007]. The dataset consists of product reviews from Amazon for four different types of products (domains), namely books, DVDs, electronics and kitchen appliances. For each domain, there exist 2, 000 la- beled reviews (positive negative) and the classes balanced. We construct 4 adaptation tasks. In each task, the MEAN and NN models are trained on reviews for a single type of products and evaluated all domains.
42

---

Published as a conference paper at ICLR 2026
Table 3: Average performance (aceuracy root mean square error) of the NN NN MEMN MEAN and
NNMAX on the four benchmark datasets.
MODEL (t)
POLARITY (1)
IMDB (1)
IMDB-BINARY (f)
NN
60.07 = 2.12
76.93 + 2.42
0.2210 + 0.0085
70.20 = 1.72
MEN
63.41 + 0.98
77.11 + 2.34
0.2159 + 0.0033
67.00 + 2.52
MN
77.21 + 1.09
78.14 + 1.94
0.2259 + 0.0017
61.40 + 2.57
Each review is represented as multiset of word vectors. The word vectors are obtained from publicly available pre-trained model (Mikolov et al. 2013). The MNME and MAX models consist of an MLP which transforms the representations of the words, aggregation function (MEAN and MAX, respectively) and a second MLP which produces the output. Both MLPs consist of two hidden layers. The ReLU function is applied the outputs of the first layer and also dropout is applied between the two layers with = 0.2. The hidden dimension size is set to 64 for all hidden layers. The model is trained for 50 epochs by minimizing the cross-entropy loss function with the Adam optimizer and a learning rate of 0.001. At the end of each epoch, we compute the performance of the model the validation set, and we choose our final model the one that achieved the smallest loss on the validation set.
Figure S iillustrates the Wasserstein distance with p between groups when the EMD (Top Right) and the Hausdorff distance (Bottom Right) are used as ground metrics. It also shows the drop in accuracy when the NNME (Top Left) and NN (Bottom Left) models are trained on one domain and evaluated on the others. Each row corresponds to one specific model, e. g., the first row represents the model trained on the reviews for books. We observe that general the drop in accuracy follows similar pattern with the distance between the source and target domains, i. e.. the higher the distance, the higher the drop in accuracy. We also computed the Pearson correlation between the drop in accuracy and the domain dicrepancies. We found that the Wasserstein distance based on EMD highly correlates with the accuracy drop of NNMEAN (r = 0.917), while there is an even higher correlation between the Wasserstein distance based Hausdorff distance and the accuracy drop of NNMAX (r = 0.941).
E.5 PREDICTIVE PERFORMANCE OF NEURAL NETWORKS FOR SETS
We next evaluate the NN NNMEAN and NNMAX models on four classification and regression datasets, namely ModeINet40, Polarity, IMDB and HLID-BIIARY, The first two datasets are de- scribed in section 4 IMDB contains movie reviews from the IMDb database (Maas et al.) 2011). The targets are the ratings that accompany the reviews (10 different values). We treat this task as a regression problem. IMDB-BINARY is a standard graph classification dataset (Yanardag & Vish- wanathan 2015), commonly used for evaluating graph kernels and graph neural networks. Each graph of the IMDB-BINARY dataset was represented as multiset of the degrees of its nodes. The results are illustrated in Table Each experiment was repeated 5 times with different random seeds, and for each dataset we report average accuracy (for ModelNet40, Polarity and BMDB-BINAR or average root mean square error (for IMDB) on the dataset's 's test set and the corresponding standard deviation.
We can see that NNMAX outperforms the other models on ModelNet40. A possible explanation that all input multisets have the same size, and such a setting the max aggregator Lipschitz continuous with respect to all three considered distance functions. Therefore, NNMAX can effectively capture the distances between the point clouds in ModeINet40.
Polarity consists of short reviews (average number of terms 20). Therefore, whether a review is positive or negative depends primarily on the presence of one or a few terms that indicate sentiment. These terms can be considered extreme elements, and the Hausdorff distance relies on such extreme elements when comparing its inputs. This distance function thus seems to be suitable for this task and potentially explains why NN MAX is the pestorerfonmig model this dataset.
The reviews contained in the IMDB dataset are much longer than those the Polarity dataset (aver- age number of terms 25-4). Due to the potential presence of outlier terms, the Hausdorff distance
43

---

Published as a conference paper at ICLR 2026
may not accurately capture document similarity. The matching distance can also be sensitive to doe- ument length. In contrast, EMD captures the overall semantic aligmment between documents, and compares documents based their overall meaning. This makes EMD more suitable for this task, which is empirically confirmed by the superior performance NNMEAN compared to the other two models.
SU is the best- pestorerforming method on the IMDB-BINARY dataset. In this dataset, capturing both the number of nodes and their degrees is essential. The matching distance is well suited for this task, and the stronger performance of the NN model, which is Lipschitz continuous with respect this distance (under certain conditions), supports this intuition.
44


Reviews:
[{"review_id": "HpqUntQhui", "reviewer": "Reviewer_ZjJJ", "summary": "The paper analyses the Lipschitz continuity of the set aggregation functions MEAN, SUM, and MAX. The EMD, Hausdorff distance, and matching distance are analysed, and Lipschitz bounds are derived for the cases of multisets having the same and different cardinalities. These results are then extended to the Lipschitz continuity of a neural network based on MLPs and an aggregation function. The authors show that a modified attention mechanism is not Lipschitz-bounded and use their results to derive bounds on stability under perturbations and distribution shifts. Numerical experiments are provided for two tasks and linked to the theory.", "questions": "- Most theorems exclude sets that contain the zero vector. Explain why, whether it could be mitigated, and its effect on practice. \n- Please better explain the usage of the analysed network structures for state of the art (SOTA) or practice in the context of transformers or GNNs (not just one sentence in line 63 and two citations from 2017).\n- Please relate your work more to the cited Fourier Sliced-Wasserstein embedding (line 70) and the importance of bi-Lipschitz continuity and injectivity of aggregation functions.\n- Please describe the theoretical advantages of the sum aggregator better (line 119).\n- Why were those three distance metrics chosen?\n- The reader would benefit from a summary of when each metric is relevant and which aggregation function should be chosen in practice. Please relate it to the initial motivation of robustness and include experimental results, such as loose bounds.\n- Please relate the attention aggregation to the mean or the max.\n- Please unify notation, e.g., activation functions in line 234 and line 284.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors provide a significant contribution to the analysis of Lipschitz continuity of aggregation functions. The paper is well structured, and the results build on each other, from the fundamental results in Table 1 to the bounds on input perturbations. A small set of benchmarks nicely accompanies the theoretical results.", "weaknesses": "The paper would benefit from explaining related literature and the connections to it better. Based on the theoretical and experimental results, the conclusions for practitioners should be better spelled out (details see below).", "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": "aQY2kJisRO", "reviewer": "Reviewer_gLAF", "summary": "It has been demonstrated that some of the key properties of neural network models (such as their generalisation or robustness to corruption) can be controlled by (a bound on) their Lipschitz constant. This article addresses the question of whether specific neural networks, designed to process collections of vectors (sets or multisets) whose order is irrelevant to the task at hand, are Lipschitz continuous with respect to a given distance. The authors examine three known possible distances between unordered multisets, the Haussdorf distance, the Earth mover distance (EMD) and the matching distance, as well as three order-independent aggregation functions at the heart of common neural architectures for multisets, namely the sum, mean and max functions. The authors then thoroughly investigate all combinations of distances and aggregation functions, determine the possible Lipschitz continuity and, if continuous, the limits of the Lipschitz constants of these aggregation functions and the neural network constructed from them. Finally, the article analyses the theoretical limits of two proof-of-concept applications, namely the classification of a point cloud representing shapes (the ModelNet40 dataset) and the classification of film reviews from a set of unordered words (the Polarity dataset).", "questions": "-   Can you provide a correction to the proof of Prop. 3.6?\n-   Can you better explain the need of neural networks to generate multisets in Sec. 3.1?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "-   The authors study the key properties of neural networks for unordered multisets, a context that appears to have been little studied to date.\n-   They provide a comprehensive study of the Lipschitz continuity of these networks and their aggregation functions with respect to three known distances (EMD, Haussdorf, matching distance), and provide new bounds on the Lipschitz constant when available. I'm not expert in this topic but the results seem novel.\n-   Where available, they show theoretically and numerically how the bounds of the Lipschitz constant can characterise the robustness of these neural networks in the face of certain data corruptions (addition of elements, perturbation of elements).\n-   Based on a result from (Shen et al., 2018), they also explain how these limits can be used to characterise the generalisation error of such a network in the event of a change in distribution.\n-   They provide a convincing numerical analysis of aggregation functions and the neural networks that rely on them. This analysis is performed on two datasets, and a comparison between the theoretical Lipschitz upper bounds and the numerical upper bounds is provided.", "weaknesses": "Overall, the article is interesting and easy to read despite its technical nature and the diversity of all the aggregation function<->distance associations considered. I have listed the following errors that the authors should correct. True weaknesses are labeled as such in the list below.\n\n-   (weakness) In Sec. 3.1, while the numerical treatment is clear and legit, I didn't get why the authors need 3 trained different neural networks to simply test the Lipschitz continuity of the aggregation function. This part should be better motivated. Is it a way to artificially generate a lot of multiset examples? Or to generate vector multiset of a fixed dimension? A priori, I don't see any connection between the way these vectors are generated and the Lipschitz continuity: these vectors could be generated by any means, the Lipschitz continuity of the aggregation function that is fed with them is independent, except if the continuity is restricted to a family of specific vector but this is nowhere considered in this work.\n-   (weakness) L1102: \"f1 and f2 are fully-connected layers\" This is part is a bit obscure. First the f1 is applied to vectors in the definition of vX and then in this line, it is defined by its application to scalars. If it is applied componentwise to vectors it must be explained. But then, the affine transformation is a bit special and seems to involve a diagonal matrix diag(a1, ..., an). This part needs improvements.\n-   (weakness/error) Proof of Prop 3.6: Section A.8, L1433-1424: The proposed matrix F does not respect the constraints in L1439 and L1442. The only matrix I see that could respect it is $F_{ij} = 1/(n\\*(n+1))$ whatever the value of i and j; but maybe I'm wrong.\n-   The 3 claims of Thm 3.1 do not use explicitly the multisets X and Y introduce at the beginning of the theorem statement; Same remark for Thm 3.3\n-   Page 4, sentence \"As discussed above, the SUM function is theoretically more powerful than the rest of the functions.\": the word \"powerful\" is a bit vague in this sentence. What was introduced earlier is rather the possibility for the aggregation to be \"injective\"; this is not directly related to a concept of powerfulness or efficiency.\n-   Page 5, line 239: \"g\" does not strictly operate on a multiset with the double-brace notation, it is rather that g is invariant under any permutation of its input and I guess the notation g({{..}}) rather means that invariance. Such a meaning could be inserted in Sec. 2.1 \"Notation\"\n-   I guess this is a bit too implicit but it should be (re)said the Lipschitz constant over $f_{MLP1}$ and $f_{MLP2}$ are associated to the standard L2-L2 continuity of these functions\n-   Page 6: while interesting, the analysis of the attention mechanism (and the negative result regarding its continuity) would deserve to be announced with a few words in the intro. As it, it looks like an extra element that comes out of the blue.\n-   L297-298: \"Incorporating l2 attention into the definition of $f_{ATT}(X), unfortunately, does not make it Lipschitz.\" -> Is it a fact or something that has been proved by the authors? Explain\n-   Proposition 3.6: there is an error in the proof of point (1), see below\n-   L356-357: \"Haudorff\"\n-   L458-459: how the value 0.2 has been determined in the width of the uniform noise? That is a magical value.\n-   L459-462: Regarding the sensitivity of NNmax vs NNmean in the different considered scenarios, could this sensitivity be backed by the previous theoretical analysis?\n-   L617: \"denote the permutation\" -> \"denote one of permutation\"; there could be several minimizing permutations with the same score.\n-   L770: \"Then, we have\" -> The fact that v1 = u1 ...; is not a consequence, but a choice to find a counterexample; adapt the sentence accordingly, here and in the other 5 other similar proofs later.\n-   L835: define $d_{ij}$ (I guess it's just $\\|v_i - u_j\\|$)\n-   L835: the inequality is in the wrong direction; the sum with the entries $F_{ij}$ is bigger than the norm of the difference of means; same error later in another proof, L926\n-   L1135: You should remove this line or place a minimum over all possible matrix F here since the next bound using F\\* is then bigger if F\\* is the matrix minimizing the EMD rather than this minimization\n-   L1458-1460: The statement and equation \"We thus obtain dH(W,X') = h(X',X) = ...\" is wrong, but it seems anyway unnecessary for the proof of point (2).\n\nMinor/cosmetic:\n-   if not already the case, everywhere avoid denoting norms with the double bar, use rather \"backslash bars\" in latex", "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": "xzAHJ58NwK", "reviewer": "Reviewer_y3oZ", "summary": "This paper systematically analyzes the Lipschitz continuity of three representative aggregation functions for multiset inputs (SUM, MEAN, MAX) with respect to three order-invariant multiset distances (EMD, Hausdorff, Matching), and provides exact constants. Based on these results, the authors derive a Lipschitz upper bound for set neural networks composed of “MLP → Aggregation → MLP”, and further discuss the applicability of existing W₁-based generalization bounds under distribution shift. Numerical experiments are conducted on ModelNet40 and Polarity, visualizing the practical validity of the derived bounds through scatter plots and correlation coefficients.", "questions": "- When Proposition 2.2’s assumption is violated in practice (e.g., zero vectors introduced by padding), how can the proposed theory be applied or extended?\n- In what kinds of practical situations would it be appropriate to use Mean, Max, or Sum, respectively? For instance, depending on conditions such as (a) a few outliers vs. widespread small noise, (b) fixed vs. variable set cardinality, or (c) small-element sets (e.g., fashion) vs. large-element sets (e.g., point clouds, documents).\n- This study explores suitable distance functions for each aggregation type (Sum, Mean, Max) under different scenarios. As a potential future direction, could this approach be further generalized by incorporating the Hölder mean (see arXiv:2403.17410)?\n\n(Other Comments)\n- Overall: It would be preferable to end mathematical expressions with a comma or period.\n- Line 41: might loose → might lose\n- Line 114: The table should include a title.\n- Line 147: Hausdorff distance → Hausdorff Distance\n- Line 356: Haudorff → Hausdorff\n- Figures 1–2: The axes are too small to read. It would also help to indicate within the figure which columns correspond to sum, mean, and max.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Presents a clear overview of which combinations of {SUM/MEAN/MAX} × {EMD, Hausdorff, Matching} are Lipschitz continuous, and additionally provides strengthened results for fixed cardinalities as lemmas.\n- Proposes a simple yet useful composition rule that allows direct derivation of Lipschitz upper bounds for set neural networks.\n- Demonstrates the effectiveness of the analysis across both image processing and natural language domains.", "weaknesses": "- The main results focus on correlation plots, but lack comparisons of task performance (accuracy) and ablation studies (e.g., classification accuracy differences among SUM/MEAN/MAX).\n- It is unclear what practical benefits this work brings to neural networks for set functions.\n- The Matching distance is a metric only when “no zero vector is included” (Proposition 2.2), which may be inconsistent with real-world preprocessing (e.g., padding).", "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": "O4bnpYoVc5", "reviewer": "Reviewer_AMSr", "summary": "This paper discusses the Lipschitz properties of aggregation functions for multisets. The main results is that each of the three common aggregations: (a) mean (b) sum and (c) max are Lipschitz with respect to only one of the three multiset metrics \n\nmean--> EMD\n\nmax--> Hausdorff\n\nsum--> matching\n\nThe explicit constants are also computed. In addition, results for attention based aggregations are provided, implications for perturbations and distribution shifts are discussed and empirical evidence for the theorems is provided.", "questions": "Honestly, these are not questions but suggestions for the next version of the paper (hopefully, the camera ready version). Feel free to ignore some or all of these points for the rebuttal. But please do take this into account when editing the next version of the paper. \n\n**Bigger comments*\n* EMD and the Hausdorff distance are not a metric on multisets of $\\leq M$ elements because for X={a,a}, Y={a}  we have EMD(X,Y)=0=Hausdorff(X,Y). This should be mentioned when these metrics are introduced. \n*  Related to this: some of your results follow from the arguments in xu et al., which are nicely summarized in figures 2-3 and in the schematic statement sum>mean>max. Mamely, it is established that mean cannot separate certain multisets (e.g., X and Y above) if they are equal as distributions, and that max cannot separate multisets which mean can, namely multisets which are different as distributions but are the same if multiplicities are ignored. It would be good to explain this, and this would also emphasize that the other direction, namely that sum is not Lipschitz with respect to the other metrics, is not known and is a truly new result.\n* It would be good to add references to support your choice of distances on multisets. Namely, to show these choices are natural and not something you invented. For example, the matching metric, perhaps the least known of the three, is used in the Chuang paper you cited in a different context, and in [1]. \n* It seems to me that an easy corollary of Theorem 3.1 is that none of these three metrics are bi-Lipschitz equivalence. Thus, no aggregation can be simultaneously Lipschtiz with respect to all of them\n* In Lemma 3.2, why don't you discuss the Hausdorff metric?\n* Bullets 1-2 of Lemma 3.2 follow immediately from proposition 3.2, I would comment on that.\n* I am missing some discussion of Theorem 3.3. Namely, what you get for mean and max is more or less the extension from theorem 3.1 which you might expect. For sum pooling you don't get this, which initially seems like a surprise. Why is this? After looking in the proof my understanding is that this is because the inner function can map non-zero elements to zero (in your proof, near zero). This too should be explained. This also seems a bit superficial to me: I would suggest to define the matching metric so that if X has $n_1$ elements and Y has $n_2$ elements, then the term $|n_2-n_1|$ would be added for the unmatched elements. Wouldn't this solve the issue?\n* What do we learn from Proposition 3.6? Could you add some discussion?\n* Section 3.4: I understand that Lipschitz results automatically lead to theoretical results on generalizaiton, still, I couldn't understand this section I think it should be rewritten. \n* Line 459-461: I think when you write \"insensitive\" you actually mean \"sensitive\". In my understanding insesnsitive=robust. \n \n\n\n**Minor comments**\n* In line 51, the sentence \"input data might correspond...\" is strange. I would say, sometimes, data is permutation invariant and should be treated as a multiset. \n* Line 119, for the sake of formal correctness, you might want to mention that sum pooling in injective when coupled with a  function applied to  each point. \n* Proposition 2.3 seems obvious to me, if you agree I would add some sort of remark about that\n* Theorem 3.3 starts with \"Let X,Y\" but X and Y do not appear elsewhere in the theorem. \n* Line 404: \"Therefore, the results of both Theorem 3.1 and Lemma 3.2 hold\". I would rephrase, the experiment corraborates the theorem, but it does not prove it is true. What proves the theoremsare true, is, well, the proofs of the theorems. \n* Line 418-420: You discuss Lipschitz constants of the affine layer, what about the activation?\n* A.3.1: In the proof, say that this if for the F for which the EMD is realized. \n*Line 771: \"Then we have\" doesn't make sense, should be \"where we choose\" or something like that\n\n[1] On the Holder Stability Of Multiset and Graph Neural Network, Davidson and Dym, ICLR 2025", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well written, and from what I checked the theoretical results seem correct. The main result should be of some impact to the 'permutation invariant learning' community. Perhaps, the take home message is this: while from the lens of pure injectivity, the well known xu et al. paper argued that sum>mean>max, from the lens of Lipschitzness, each has its own distinct advantage.", "weaknesses": "While the paper does conduct some nice experiments, there is no clear bottom line to the paper from a practical point of view. E.g., one could hope this paper would substantiate a claim that for some type of tasks, sum pooling is better, and for others, max pooling is more accurate, or more robust.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)