On Transferring Transferability: Towards a Theory for Size Generalization
Authors: Eitan Levin
Yuxin Ma
Mateo Diaz Diaz
Soledad Villar
Venue: NeurIPS 2025 spotlight ()
Keywords: transferability
size generalization
graph neural networks
equivariant machine learning
any-dimensional learning
Primary area: theory
TL;DR: We study the properties that make machine learning models generalize their performance across dimensions.

Abstract: Many modern learning tasks require models that can take inputs of varying sizes. Consequently, dimension-independent architectures have been proposed for domains where the inputs are graphs, sets, and point clouds. Recent work on graph neural networks has explored whether a model trained on low-dimensional data can transfer its performance to higher-dimensional inputs. We extend this body of work by introducing a general framework for transferability across dimensions. We show that transferability corresponds precisely to continuity in a limit space formed by identifying small problem instances with equivalent large ones. This identification is driven by the data and the learning task. We instantiate our framework on existing architectures, and implement the necessary changes to ensure their transferability. Finally, we provide design principles for designing new transferable models. Numerical experiments support our findings.

On Transferring Transferability:
Towards a Theory for Size Generalization
Eitan Levin
Yuxin Ma o
Caltech
Johns Hopkins University
Mateo Díaz Johns Hopkins University
Soledad Villar Johns Hopkins University
Abstract
Many modern learning tasks require models that can take inputs varying sizes. Consequently, dimensionninddeeeddee
architectures have been proposed for do- mains where the inputs are graphs, sets, and point clouds. Recent work on graph neural networks has explored whether model trained on low-dimensional data can transfer its performance to higher-dimensional inputs. We extend this body work by introducing general framework for transferability across dimensions. We show that transfcrability corresponds precisely continuity in a limit space formed by identifying small problem instances with equivalent large ones. This identifi- cation is driven by the data and the learning task. We instantiate our framework existing architectures, and implement the necessary changes to ensure their transferability. Finally, we provide design principles for designing new transferable models. Numerical experiments support findings.
Introduction
Modern learning problems often involve inputs arbitrary size: language has text sequences of arbitrary length, graphs encode networks with arbitrary number of nodes, and particle systems might have an arbitrary number of points. Although traditional models are typically limited to the specific input dimensions they were trained on, dimension-independeer architectures have been proposed for several domains. For instance, graph neural networks (GNN) for graphs [70]. DeepSet for sets [91], and PointNet for point clouds [66]. These models have desirable feature: they can be trained with low-dimensional samples and, then, deployed on higher-dimensional data.
A key question in this context is whether the performance of a model trained with low- www-dimensiona samples transfers across dimensions. This has been thoroughly studied in the context GNNs [70, 58, 59], where the term transferability was first coined.' In turn, the tools used to establish transferability of GNNs are, first sight, problem-specific, including the concept of graphon, and certain convergence of homomorphism densities. Thus, the analysis does not readily extend beyond GNNs, and so we ask
What properties of the model, data, and learning task ensure that the learning performance transfers well across dimensions?
These authors contributed equally this work.
'The term "transferability" is not related to transfer learning or meta-learning. It specifically refers to the phenomenon that consistency of outputs is preserved under size changes for structurally similar inputs, permitting dircct performance carryover from small to large problems.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

This question is relevant for the current pursuit of graph foundation models [53], GNN for combi- natorial optimization [12], neural PDE solvers [67, 51], and on, where pre-trained models aim to be adapted to wide range of tasks involving different-sized objects. In this paper, we answer this question by identifying assumptions on the learning problem that make a model generalize across dimensions, and give theoretical framework to understand models with such properties. Our framework requires technical notions that we develop throughout the paper, so before diving into the details, we proceed to give the high-level intuition.
Our framework considers a machine learning model parametrized by 0 E R where the number of parameters k is fixed. For any fixed f, the model can be evaluated on inputs of any size n. That is, the learned 0 defines a sequence of functions, for example, (fn: : V,, + R),, with increasingly larger imput sizes.² 2 We think of V, S Vo as a subspace of an definite-dimensinnn then amounts to asking whether for large enough n and m we have fu(#n) R Sm (x)m) when the inputs nn and I.m are close to each other in the limiting space Vo.. For example, we consider graphs of different sizes to be close if their associated step graphons are close in the cut metric, following standard practice in the GNN literature. Similarly, we view point clouds of varying sizes as close if their corresponding empirical measures are close in the Wasserstein metric.
limit space. Transferability
In a nutshell, we identify two properties that guarantee transferability; (i) the functions in the sequence are compatible with one another in precise sense, and (ti) all of them are continuous with respect to prescribed norm on Vos. Compatibility ensures that the sequence extends to a function taking
inputs fox : Vo + E, while continuity ensures that this extension is continuous. This allows us to relate model outputs on two differently-sized inputs via their extension (x,) fzx, (2x) R (Xm) = Sm (..)). Moreover, if we evaluate our models on sequence of inputs In converging in suitable sense to an infinite-dimensional input x, then the evaluations (x,),) converge to the value of the limiting model (z). Our framework parallels the ideas from the GNN literature, where graph convergence to limiting graphon is measured in cut distance- which is equivalent to homomorphism density convergence. However, this framework provides a transparent extension that allows us to analyze other models, e.g., DeepSets and PointNet.
Our contributions. Next, we summarize our three core contributions.
(A framework for transferability) We introduce a class of diyeesnnnsional models and a formal definition of transferability. We show that transferability holds whenever certain notions of compatibility and continuity hold. We further leverage transferability to establish a generalization bound across dimensions. In our theory, the notion of transferability relies on identifying low- dimensional objects with figher-dimensione ones, and measuring similarity of such objects in an appropriate metric. We illustrate how these choices have to align with the data and learning tasks.
(Transferability of existing models) We instantiate our framework on several models, including DeepSet [91], PointNet [66], standard GNNs [70], Invariant Graph Networks (IGN) [56], and DS-CI [5]. Not all of these models satisfy our assumptions. For those that do, our framework yields new and existing transferability results in a unified fashion. For those that do not, we either modify them to ensure transferability or demonstrate numerically that transferability fails and impedes the performance of these models.
(New transferable models) We provide design principles for constructing transferable models. Leveraging these ideas, we develop a variant of IGN that is provably transferable, addressing challenges highlighted in previous work [56, 35]. We also design new transferable model for point cloud tasks that is more computationally efficient than existing methods [5].
Notation,
The Kronecker product on matrices is denoted by &. We write 1, and In for the all-ones vector and the identity matrix of size respectively. Given two sequences (a,), (b,.) S IR say that an S b, if there is constant C' > 0 so that a,, I Cb,, for all n. See also Appendix A.
Outline. Section 2 introduces the theoretical framework. Section 3 defines transferability, which is used in Section 4 to derive a generalization guarantee. Section 5 instantiates our framework on concrete neural network examples, and Section 6 provides supporting experiments." Related work and limitations are discussed in the Appendix.
Thhe output size can also depend on n, which is often the case representation learning. The code is available at https: //github. cow com/yuxinma98// httt///taassfrrrreeee www.eeerriingttaaarrraiill transferability.
2

---

2 How to consistently grow: equivalence of differently sized objects
In this section, we formally introduce the setting for studying transferability. The definitions here build upon the framework introduced in [49, 50] for defining any-dimensional neural networks and optimization problems. Central to our developments the notion of compatibility between sequence of functions. Intuitively, sequence of functions is compatible when they respect the equivalence between low-dimensional objects and high-dimensional version of them. For example, sample statistics like the mean and standard deviation remain invariant when each element is repeated m times. Similarly, various graph parameters such as triangle densities and normalized max-cut values are preserved when each vertex is replaced by identical copies of itself.
To formalize these notions of equivalence of objects and compatibility between functions, we will leverage the concept of consistent sequence. Intuitively, they are nested sequences of vector spaces with growing groups acting on them, representing problem instances of different sizes. They are interconnected by embeddings that establish equivalence between smaller and larger instances.
Definition 2.1. A consistent sequence V = {(Va) (NN (Gm)neN) is a sequence of fmite-dimensiin vectors spaces Vn, maps .N and groups Gn acting linearly on Vn, indexed by directed poser' (N, such that for all n 3 N, the group G, is embedded into GN, and NNNn; Vn + VN is linear, equiivarrr embedding.
Although the definition includes a sequence of groups, it applies to situations without symmetry by setting G., = {id} for all n. While all the examples in this work involve symmetries, we believe our framework might be relevant in symmetry- settings."
Example 2.2. Here are two prototypical examples of consistent sequences. In both cases, Vn = R", with the symmetric group Sn acting via coordinate permutation. (i) the sequence indexed by N with the standard ordering S. paired with the zero-padding embedding IR.h - RNN, which maps (#I..... ,In) to (Z1,.... 0..0.... O........)) and (ii) the sequence indexed by N with the divisibility ordering (n 3 N whenever N divisible by n)) paired with the duplication embedding R" + +R sending a vector (ZI,..., to x @ 1 N/n (I1,..., 21,
N/n copies
N/n copies
Next, we define common space for objects of all sizes in a consistent sequence, in which we can compare objects of different sizes and take their limits. For example, if we identify vectors x with their duplication embeddings x @ 1//n, we can view the resulting equivalence classes as step functions on [0, 1] taking value x; on consecutive intervals of length 1/n.
Definition 2.3. Let Voc U,, where we identify E Vn with its image (v) for all n 3 N to be equivalent. Analogously, we let Go be the union of groups with equivalent identifications.
For simplicity, we will often write v E Voo for any dinenssoinnii object v E Vn to denote the
cquivalence class [u]. It is straightforward to check that Goo acts on Vo0 via g [e] = [g v]. Having established how consistent sequences define a desirable equivalence relation the space of problem instances of varying sizes, we now introduce compatible functions that respect such equivalence.
Definition 2.4. Let V = {(V,), ()) (Gx)} and U = {(Ux), ). (1bN.),, (Gx)} be two consistent sequences indexed by (N, 3). sequence of maps (fn: Vn + Un) is compatible with respect to U, if fN PN = NN.. for all n 3 N, and each fa is G, -quiivaraa.
is instructive to visualize compatible maps using the following commutative diagram, which represents a mapping between sequences while ensuring that the diagram commutes:
(Vuy Gnj)
Paginy (Vng: Png.ng (Vags Gns)
Gun)
Jmz (Un.. G..)) Voging (Unzy Gmz)
faz
Jng
for n1 1 n2 1
Una-ng (Ung: Gay)
Equivalently, compatible maps precisely those sequences (fx) that extend to equivalence classes:
"This is a partial order on N where every two elements have an upper bound, see Appendix C.I.
'The symmetric case is relevant because the theoretical setting relates to representation stability [50. 16).
3

---

A sequence of maps (fn) is compatible if, and only if. there exists a G eqquivaraat map foo: V60 + Uso such that fn = foo Iv, for all n.
See Appendix C.2 for a proof of this equivalence.
2.1 How to define distances across dimensions
Compatible maps are functions that respect the equivalence defined by consistent sequences. We now consider whether these functions further preserve proximity, mapping "nearby" objects to "nearby" outputs. This requires well-defined notion of distance between objects of different sizes that is consistent with the earlier equivalence.
Definition 2.5. For a consistent sequence V, a sequence of norms (ll llv..) on Vn are compatible if all the embeddings 'N and the Gn -actions are isometries. i.e., for all n N, Vn.g E G.. N. = ||=l],, and [[g ==llv,, ||-l|
Equivalently, compatible norms are those that extend to the limit; that is, there exists a norm || llv..
on Vo such that for any and x E Vn, ||al|,, ||=]| and the Gactin Voo is isometry with respect to || llv.. see Appendix C.3 for proof of this statement.
Example 2.6 (Example 2.2 continued). For our prototypical consistent sequences, the lop norms ||^|| < |2 ///p))// are compatible with the zero-padding embeddings. while the normalized Ep 1/9 are compatible with the duplication embeddings.
norms ||x l7 + E [mpl))
With norms in place, we can define limit space that includes not only equivalence classes of finite-dimensional objects, but also their limits. As we will see, this recovers meaningful spaces such as ([0, 1J) and the space of graphons with the cut norm. Morcover, the orbit spaces of these limits recover probability measures (with the Wasserstein distance) and equivalence classes of graphons (with the cut distance), respectively.
Definition 2.7. The limit space is the pair (Vzo: Goo) where Voo denotes the completion of Voo with respect to || ll endowed with the symmetrized metric"
dxx, y) = inf 1|g 1 allv for v, y E Voo.
gE
3 Transferability is just continuity
The notion of GNN transferability established in [70, 48]. It states that the output discrepancy [An, Xn) - fm (Am, Xm)Il between graph signals of sizes n, m sampled from the same graphon signal (W, (" vanishes n, m grow. Prior studies explore this property under various sampling schemes, norms, and GNN architectures (41, 70, 47, 11, 35).
We formalize the idea of functions "mapping close objects to close outputs" as (Lipschitz) continuity of compatible maps.
Definition 3.1. Let V, be consistent sequences endowed with norms. A sequence of equivariant maps (fn : V, U,) is continuously (respectively, L-Lipschitz, L(r)-locally Lipschitz) transfer-
able if there exists foo Vo - Uso that is continuous (respectively, L-Lipschitz. -risshictthttz the ball () {u E Voo [|ellv r for all r 0) with respect to || l|vv= Ilu such that fn = foolv, for all n. Notice that if (fn) is transferable, then must be compatible.
In Appendix D.I show that Lipschitz transferability is equivalent having compatible sequence (fw), each Lipschitz with the same constant. For linear maps, it suffices to verify that the operator norms are uniformly bounded. This simplifies the verification of transferability. Importantly, we also show that transferability with respect to the norm |lv., implies transferability with respect to the symmetrized metric d.
'It is pseudometric on V... and a metric on the space whose points are closures of orbits under the action of Goo in V (see Section 3 of [10D.

---

The following proposition shows that the output discrepancy is controlled whenever dimension- independent model is continuously or Lipschitz transferable. justifying our terminology. Thus, our framework extends transferability beyond GNNs, highlighting that transferabilityy is equivalent to continuity in the limit space. For given function R: N -> + we say that (Ix) converges to x in Voo at a rate R(x) in d d(z,, x) Σ R(n) and R(n) - O.
Proposition 3.2. Let V, U be consistent sequences and ler (fn: V, Un) be maps between them.
(Transferabilitty) For any sequence (In E Vn)) converging limiting object E Voo in d, if (fa) is continuously transferable, then ((fa((x)) Jm (((m)) - 0 as n, co. Furthermore, if (ra) converges to x at rate R(n) and (Ja) is locally Lipschitt-trunsfrrubbe then
d(f((z)) Im((m)) (2m)) S R(n)) + R(m)..
(Stability) If (fr) is L(r)-locally Lipschitz transferable, then for any two imputs 2n E Va and I' E Vm of any two sizes n. mn with [[.ullv.. (amlll S r, we have ((fn(zn), (men).f((asr (xm)) S L(r) d(zn F.
Several remarks are in order. First, the same results trivially hold when the symmetrized metric replaced by the norms on Vs Us. However, the finite inputs (Ix) are often obtained from the limiting object via random sampling, and converge only in the symmetrized metric. This is the case for all the common sampling strategies used for sets, graphs, and point clouds, which review in Appendix D.3. In the case of graphs, our framework recovers results from prior work, achieving the same or stronger rate of convergence. Second, some models are only locally Lipschitz outside of a measure-zero set. Transferability still holds for such models for almost all limit objects I E Vos. This and other extensions are deferred to Appendix D.2. Third, Lipschitz continuity of neural networks has been extensively studied in the context of model stability and robustness small input perturbations [25, 85, 43, 27]. Our results generalize the connection between stability and transferability, first established in [72], by showing that Lipschitz continuity of any-dimensional model implies not only stability, but also transferability across input sizes.
4 Transferability implies size generalization
We use transferability to derive a generalization bound for models trained on inputs of fixed-size n, and evaluate their performance as + co. It can therefore be interpreted as a size generalization bound, accounting for distributional shifts induced by size variation. We study a supervised learning task with input and output spaces modeled by consistent sequences V and U satisfying the following.
Let μ be a probability distribution supported on a product subsets X x Y g Voo X whose orbit closures compact in the symmetrized metrics. Let Sp: Xxx V XU, be a random sampling procedure such that Sn (x. y) E X x Y almost surely for (I. y) E su)p( This sampling induces a distribution Pn V, x Un by drawing (x. 1u. and then sampling (In, Mm) ~ Sn, y). A datasel s = {(Ii, ).) is drawn i.idd. from pmu. Suppose the loss function f: Uno x Uxx + R is bounded by M and cx-Lipschitz Assume training is performed using a locally Lipschitz transferable neural network model, and Ag : Vx + Ux is the hypothesis learned (given datuset 8), which is Lipsiihciitz on X x in
Assumption 4.1.
In Appendix E, we further break down these technical assumptions and provide detailed motivation to make them more accessible. We also discuss two concrete examples of sets and graphs to justify the practicality of the key assumptions. The following generalization bound follows by applying the results from [88] to our setting.
Proposition 4.2. Consider learning task with input and output spaces modeled by consistent sequences V and U satisfying Assumption 4.1. For any ö > O. with probability at least 1 - 8,
N
(A.().)) - Plaw)) ((A.(1).))
N
2 2log(1/0) s c(c, v 1) (5 (NV) + W1 + MV (2 2)5- 2)
N
5

---

where E(r) = CxtraaCvir/4) Cx(E) and Cy(E) are the E-covering numbers in à of X and Y, respectively, and W1 denotes the Wasserstein-1 distance. Moreover, if the sampling Sn has convergence rate R(n) in expectation, then W1 Wi(p, (1, S Rín) as - and the bound (1)
converges to as n, N 00. oc.
We defer the proof to Appendix E. This bound shows that generalization improves with greater model transferability (i.e., smaller Lipschitz constants) and higher-dimensional training data (i.c., large n), while it deteriorates with increasing complexity of the data space (i.e., larger covering numbers).
Transferable neural networks
now apply our general framework to the settings of sets, graphs, and point clouds. each case, we identify suitable consistent sequences, analyze the compatibility and transferability of existing neural network models with respect to these sequences, and propose a principled recipe for designing new transferable models. This analysis provides insights into the tasks for which each model is best suited, while offering provable aize-ennrralization guarantees.
A transferable neural network learns a fixed of parameters that define transferable functions (fn) for any n-dimensional normed space Vn. The compatibility conditions on (fn) and the sequence of norms || llv. describes the implicit inductive bias of the model.
Our analysis hinges on the following proposition, which observes that compatibility and transferability are preserved under composition and reduces the verification of Lipschitz continuity from the limit space to each mitee-immeniioal space. This significantly simplifies the task of establishing transferability complex neural networks. The following result is proved in Appendix E.
Proposition 5.1. Let (Vi""),, n,s (Uh)) n be consistent sequences for i I....,, D. For each i, let ) be linear maps and (6) U.()) + v1(5t1) be nonlinearities, and assume that (Wh)), (1) (t) are compatible, that supn.s ||W[("|lop llop < co, and that pr. is L(r)-Lipschitz
(W(). vi( - U(()
(6)
on balls B(0,r) in U for all 0 and all Then the sequence of neural networks (fr. W! o Pm
(D-1) .... o pn o w(")) ) -locllo Lipschitz transferable for explicit L(r).
(1)
5.1 Sets
Consistent sequence of sets. We have described in Examples 2.2 and 2.6 two consistent sequences that formalize equivalence across sets of varying sizes: the zero-padding consistent sequence Vzero and the duplication consistent sequence Väups along with norms on Rn that are compatible with each sequence. The resulting limit spaces and symmetrized metrics recover interesting mathematical structures, as summarized Table 1. Further details are provided in Appendix F. See Figure for an illustration.
Consistent Sequence
Limit space
Orbit closures of V
Orbits of Voc
Vaero Vdup
Ordered sequences in Probability measures on with Wasserstein p-metric
Ordered sequences with finitely- many nonzeros Empirical measures
(²( 1))
Table Limit spaces and their orbit spaces for consistent sequences sets.
Permutation-invarian neural networks on sets. Prominent invariant neural networks on multi- sets including DeepSet [91], normalized DeepSet [9], and PointNer [66] take the form (X)
(Agg," (xx))))) where p: Rd + RR. a: h - I& are fully-connected neural networks, both independent of n, and Agg denotes a permutation-invant
aggregation. Sum (Agg" Σnn) mean (Agg"L = 1 Er=) and max (Agg"_ == max aggregations yield DeepSet, normalized DeepSet and PointNer, respectively. Using Proposition 5. we examine the transferability of these models, demonstrating that they parameterize functions on different limit spaces, and hence are suitable for different tasks, Corollary 5.2, Table 2, and Figure 2. This is proved in Appendix F.2.

---

Zero padding Rus
Limit space
Orbit closures
permnttations
Snito indices
Opeon Og 0).....))
(92200...
[13.0.....
||
[x]
I.2.3,000 (.100.....
(0....)
(1,00.....)
distance II2.3.3 B.1O0
symmetrised
[A2220 (3000-1
(2.2.)) (22.3...)))
infinite sequences with finite non-zeros with (noorm Ixl,
Ordered infinite sequences with finite non-zeros
adc limit points
[ail
infinite sequences with finite cynorm
Ordered infinite sequences
Duplication R R
Limit space V
Orbit closures
G_ = interval permutations
(gprr 5 x
10
Ikl |1
(22,3) " (222222))))))
Lnidistance
Wasserstein p-distance
0.11 "111""000 (.333
Ve step functions [0.1]
Empirical measures
add limit
//-norm I1/l],
[to ds
points
Probability measures with finite p-th moment
functions [0.1] finite L"-nom
Figure 1: Two examples of consistent sequences sets. (top) Zero- Zero-padding consistent sequence for sets. (bottom) Duplication consistent sequence for sets.
Corollary 5.2. The transferabilityy of the three models are summarized in Table 2. Particularly, they extend to iipschitzfuncttons functions DeepSet (TR.) - IR, DeepSet. : (RR R, Point Poo (Rd) - 18 given by
DeepSet, ((x:)) = Σ p(zi)) DeepSet (n) = (ʃ mdl)) Noint =a
sup
p(x)
(Esupp(u)
Model
V zeros
|| -11
V Vuup || 11r
DeepSet
Lipschitz transferable if p(0) =0
Incompatible
DeepSet
Incompatible
Lipschitz transferable
Compatible, Lipschitz transferable if Table Transferability of invariant neural networks on sets, assuming the nonlincarities o, are Lipschitz.
PointNet
Incompatible
5.2 Graphs
Consistent sequences for graph signals. To model graph signals, we consider the sequence of vector spaces V,, 12 Raxd representing the adjacency matrix of weighted graph with nodes and node features of dimension d. The symmetric group S, acts on (A, X) E V, by g (A, = (gAg T_ .gX), capturing the invariance to node ordering.
While other embeddings are possible, in this work we focus on duplication-comsiste sequence dup for graphs, illustrated in Figure 3. Specifically, for any n|N, the embedding is defined by NN,. X) (A @ 1 N/n 11 N/n' X I//m) which corresponds to replacing each node with N/n duplicated copies. These embeddings precisely identify graph signals that induce the step graphon signal. We consider three compatible norms: the p-norm [I(A, X)I,, Il,, ( Ei, 1/
E. X II ( 1/P the operator p-norm [I(4, x) = = Alloplop.p + (2 IX 1 1/p and cut norm (1, X) ||Al|a + || Ioo In all cases, the limit space is the space of graphon signals and the symmetrized metrics recover extensively studied graphon distances in [54, 47].
7

---

50
0.12
-20-
-00-
0.0911
0.124
-40-
0122
10
10
00012
07
10
10
Sclsize
(a) DeepSet [91] output (incompatible)
(b) Normalized DeepSet [9] (c) PointNet [66] ouiput (compatible, not transferable)
Normalized DeepSet error
output
[Lipschitz transferable)
under (Vaup- -I [[T). The plots show outputs of untrained, randomly initialized models input sets of incrcasing n. Each consists of n i.i.d. samples from N(0, 1), a distribution with non-compact support. Error bars indicate one standard deviation above and below the mean over 100 random samples. (a)(b)()): Model output fo (Xx) vs. set size n. For normalized DeepSet, the dashed line represents the limiting value (u) numerical integration. While the outputs of DeepSet and PointNet diverge model, normalized DeepSet, converges the theoretical limit, i.e. f..nn(( (X,.) -> foo (j))
Figure 2: Transferability of invariant networks
(. p(æ) du(x)) for μ (0, 1), computed via increases, the transferable
(u)-(d)) (d): Convergence error f (X,) - fox (μ)] vs. set size n for normalized DeepSet (both axes in log scale), demonstrating the expected O( 1/2) convergence rate as predicted by Proposition 3.2. See Appendix F.2 for further discussion.
Duplication Reth
Limit space
Orbit closures
C,, = interval pormutations
MADV
A - & 1,17
orbit W.,
orbit of W
operasor/cut
symmerr
Mo.
min Wr We.
BEIER FIRIER 6%
step graphons
Equivalence classes of step graphons
add Imit points
with graphon operi norm
Equivalence classes of general graphons
general graphons
Figure 3: Duplication consistent sequence for graphs
Message Passing Neural Networks (MPNNs) Message-passing-basee GNNs form the most widely used and general paradigm, encompassing many existing models [31]. Instantiating Proposition 5. we analyze in Appendix G.2 the transferability of MPNNs under constraints on the message function, update function, and local aggregation, and compare our results with [70, 47].
Making Invariant Graph Networks (IGN) Transferable IGNs [56] are an alternative approach to designing GNNs by alternating linear S.u-quuivariant layers with pointwise nonlincarities. IGN is incompatible with respect to Vauu because the linear layers used in [56] are incompatible. Neverthe- less, the hypotheses in Proposition 5.1 provide a systematic approach for modifying IGN to achieve transferability, leading to two newly proposed models. We highlight this recipe for constructing transferable neural networks is general.
Generalizable Graph Neural Network (GGNN): We use compatible linear layers and message- passing-like nonlinearities of the form XA, - (A,o E
where acts *Ax,)) "==", x.).
entrywise. The GGNNs are compatible and at least as expressive as the GNNs in [70].
Continuous GGNN: We restrict the linear layers in GGNN to the subspace that has bounded operator norm on the limit space. This model is transferable in both operator 2-norm and the cut norm.
The complete description of these models and proof of their transferability are in Appendix G.3. The transferability of various GNN models with respect (VG (lop.p), is illustrated in Figure through numerical experiment.
5.3 Point clouds
Consistent sequences for point clouds. For k-dimensional point clouds, we consider a sequence of vector spaces V,, gaxk representing sets of points in I where k is fixed (typically &

---

Ealodboge F 12
Daee 1/
Senderd 02
0.00-
17
breteile 12
8.00-
3.5
8:00
0.02
23
8088
0.01
33
Omgph
Groph
Goeple
Graph
(a) GNN [70] (locally Lipschitz
(b) Normalized 2-IGN [11]
(c) GGNN (compatible, not transferable)
(d) Continuous GGNN (locally Lipschitz transferable)
(incompatible)
transferable)
Figure 4: Transfcrability of equivariant GNNs with respect to (Va || llop.2). The plots show outputs of untrained, randomly initialized models for two sequences of input graph signals (An,, (dashed lines)
Fully-connected weighted graphs A, 2 2
_=ll, X, 1n. (solid lines) A, is drawn i..d. from the Rédös-Rényi model C(n, 1/2). with X,, 1.. These two sequences represent different samplings of the same underlying constant graphon signal, where W = 1/2 and f = 1. Error bars indicate one standard deviation above and below the mean over 100 random samples. (dashed lines): For the fully connected model each finite graph signal exactly induces the underlying graphon signal. The outputs of all compatible models ((a), (c), (d)) remain constant over whereas the incompatible model (b) does not. (solid fines): The outputs of all transferable models ((a). (d)) converge the same limit as Sequence (1), while the discontinuous model (c) does not.
or 3). Unlike the sets models in Section 5.1, here we consider not only the permutation symmetry S.. which acts on the rows and ensures invariance to the ordering of points, but also the additional symmetry given by the orthogonal group Okk). which acts on the columns to capture rotational and reflectional symmetries in the Euclidean space I&* i.e. (g, h) X = =gXhT.
We consider the duplication consistent sequences of point clouds VP Specifically, for any N, the embedding is defined as nn, (X) X @ N/nn- The group embedding S,, x O(k) + SN O(k) is given by (g, h) + (g & IN/ns h). We further endow each Vn, with the normalized lp norm
||X||> ( E | O(k) of probability measures on R with finite pth moment.
1/p The orbit closures of Voc can be identified with the orbit space under
Invariant neural networks on point clouds. First, we analyze the DeepSet for Conjugation Invariance (DS-CI) proposed in [5]. In Appendix H.2, we show that the normalized variants of DS-CI is "approximately" locally Lipschitz transferable with respect to (Viup || 11p))
We also introduce more time and space-efficient model, normalized SVD-DeepSet, defined as: SVD-DS, (X) DeepSet,, (XV), where for an input point cloud X E 1=*k we compute its singu- lar value decomposition X = UVVT with ordered singular values. This model effectively applies a canonicalization step with respect to the O(k) action. We prove that it locally
transferable outside of a zero-measure set (which exists for any canonicalization [23]) in Appendix H.3. In Ap- pendix H.3, we illustrate the transferability of these models when input point clouds are i.i.d. samples from an O(k) -invaiiaa measure on R* through a numerical experiment.
6 Size generalization experiments
Our theoretical framework emphasizes understanding how solutions to small problem instances inform solutions to larger ones, i.e., whether the target function is compatible with respect to given consistent sequence, and continuous with respect to an associated norm. Under this view, size generalization can be provably achieved using neural network model that is aligned with the target function: Compatibility alignment ensures that the model is compatible with respect to the same consistent sequence the target function, and yields function on the correct limit space. Continuity alignment further requires the model to be continuously transferable with respect to the same norm as the target function, providing stronger inductive bias and asymptotic guarantees.
We evaluate the effect of these alignments through experiments where models are trained on small inputs of fixed size Meraann and tested on larger inputs Thest 2 Turain- In each experiment, all models have approximately the same number of parameters to ensure fair comparisons. In this Section we show selected set of results. See Appendix I for full discussion.

---

beple May
Dupbe ceconall i dhulitt
10
Sanddie 2. EN ineerpatiie 0LD0 canduall
10-
10"
26-3
Mol.
Tex MSG
MEL
Tex MSE
100
11P
02"1
500
1.900
100
300
100
Toat
groph (8)
puintclonal
(a) Set: Population
(b) Set: Maximal distance from the origin
(c) Graph: Weighted triangle densities
(d) Point cloud:
statistics
Gromov-Wass Wasserstein lower bound
Figure 5: Size generalization experiments: Mean Lest MSE (over 10 random runs) against test input dimensional- ity Error bars indicate the min/max range (a)()dd), and 20th /80" percentiles in (c) for legibility.
Size generalization on sets. We consider two learning tasks on sets of arbitrary size, where the target functions exhibit distinct properties, leading to different models being more suitable.
Experiment 1: Population Statistics. We tackle Task 3 from Section 4.1.1 of [91] (other tasks yield similar results). The dataset consists of N sample sets, We first randomly choose a unit vector E R-32 For each set, we sample a parameter À E [0, 1] and then generate from (AA)= = N + Ave ). The target function involves learning the mutual information. which depends on the underlying probability measure μ(A) and is continuous with respect to the Wasserstein p-distance. Based on the transferability analysis in Table 2, normalized DeepSet is well-suited for this task, as it aligns with the target function at the continuity level, whereas PointNet aligns only at the compatibility level, and DeepSet lacks alignment either level. Indeed, normalized DeepSet has the best in-distribution test performance and size generalization behavior as shown in Figure 5a.
of n points
Experiment 2: Maximal Distance from the Origin. In this task, each dataset consists of N sets where each set contains n two-dimensional points sampled as follows. First, a center is sampled from (O,, and radius is sampled from (n0 1J), which together define circle. The set then consists of n points sampled uniformly along the circumference. The goal is to learn the maximum Euclidean norm among the points in each set. The target function in this case only depends cloud via its support, and is continuous with respect to the Hausdorff distance. Consequently. for this task, PointNet is well-suited, as it aligns with the task at the level of continuity. (It was proved in [9] that PointNet extends to a function that is continuous with respect to the Hausdorff distance. We discuss the relationship between this result and ours in the PointNet part of Appendix F.2.) In contrast, normalized DeepSet aligns only at the compatibility level, while DeepSet remains unaligned. The comparison of various model's 's performance, shown in Figure 5b is expected.
point
Size Generalization on Graphs. The dataset consists of N attributed graphs x), where Au =
Aja Lid Uni 1)) for S j. and I; iid [ni 1)). (We also experimented with simple graphs; see Appendix 1.2 for details.) The task is to learn the seigal-weighted triangle density which depends on the underlying graphon and is continuous with respect to the cut norm. Figure 5c shows that our proposed continuous GGNN, which aligns with the target function at the continuity level, achieves the best test performance large graphs. Although the message- messagc-passing passing GNN is also provably transferable, it lacks sufficient expressiveness for this task [14], leading to poor performance.
y: = + Ejkeen) An,,,a
Size Generalization on Point Clouds. We follow the setup in Section 7.2 of [5], using the Model- Net10 dataset [87]. From Class 2 (chair) and Class 7 (sofa), we randomly selected 80 point clouds each, splitting them into 40 for training and 40 for testing. This results in 40 x 40 cross-class pairs. The objective is to learn the third lower bound of the Gromov- iasserseenn distance [60]. which is invariant and continuous with respect to the Wasserstein p-metric (proven in Appendix 1.4). Figure 5d shows that normalized DS-CT and normalized SVD-DS, both aligned with the target at the continuity level, achieve good test performance and size generalization. While normalized SVD-DS underperforms compared to normalized DS-CI, CI, it offers superior time and memory efficiency.
10

---

Acknowledgments and Disclosure of Funding
We thank Ben Blum-Smith, Ningyuan (Teresa) Huang, and Derek Lim for helpful discussions. EL partially supported by AFOSR FA9550-23-1-0070 and FA9550-23-1-0204 YM is funded by NSF BSF 2430292. MD is partially supported by NSF CCF 2442615 and DMS 2502377. SV is partially supported by NSF CCF 2212457, the NSF-Simons Research Collaboration the Mathematical and Scientific Foundations of Deep Learning (MoDL) (NSF DMS 2031985), NSF CAREER 2339682, NSF BSF 2430292, and ONR N00014-22-1-2126.
Bibliography
[1] Francis Bach. Learning theory from first principles. MIT press, 2024.
[2] Pablo Barceló, Egor Kostylev, Mikaël Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations (ICLR 2020), Virtual conference, Ethiopia, April 2020.
[3] Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of machine learning research, 3(Nov):463 482, 2002.
[4] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invarian graph representations for graph classification extrapolations. In International Conference on Machine Learning, pages 837-851. PMLR, 2021.
[5] Ben Blum-Smith, Marco Cuturi, Soledad Villar, al. Learning functions on symmetric matrices and point clouds via lightweight invariant features. arXiv preprint wrXiv:2405.080%9 2024.
[6] Ben Blum-Smith and Soledad Villar. Machine learning and invariant theory. Notices of the American Mathematical Society, 70(8):1205-12133 2023.
[7] Jan Böker, Ron Levie, Ningyuan Huang, Soledad Villar, and Christopher Morris. Fine-grained expressivity of graph neural networks. Advances in Neural Information Processing Systems, 36, 2024.
[8] Christian Borgs, Jennifer T Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi. Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Advances in Mathematics, (1966))1801-888 2008.
[9] Christian Bueno and Alan Hylton. On the representation power of set pooling networks. Advances in Neural Information Processing Systems, 34:17170-17182, 2021.
[10] Jameson Cahill, Joseph W Iverson, and Dustin G Mixon. Towards a bilipschitz invariant theory. Applied and Computational Harmonic Analysis, 72:10 72:101669, 2024.
[11] Chen Cai and Yusu Wang. Convergence of invariant graph networks. In International Conference on Machine Learning, pages 2457-2484. PMLR, 2022.
[12] 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.
[13) capybaralet
com/susrr/ee/////eeeeeeessssss// 14766/capybaralet), How unique are U and V in the singular value decomposition A UEVi? Mathematics Stack Exchange. (version: 2024-08-13).
[14] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383-10399 2020.
[15] Thomas Church, Jordan S Ellenberg, and Benson Farb. Representation stability in cohomology and asymptotics for families of varieties over finite fields. arXiv preprint arXiv: 309.6038. 2013.
11

---

[16] Thomas Church and Benson Farb. Representation theory and homological stability. Advances in Mathematics, 245:250-314 2013.
[17] Taco Cohen and Max Welling. Group equivariant convolutional networks. In International conference on machine learning, pages 2990-2999. PMLR, 2016.
[18] Matthieu Cordonnier, Nicolas Keriven, Nicolas Tremblay, and Samuel Vaiter. Convergence of message passing graph neural networks with generic aggregation on random graphs. In Graph Signal Processing workshop 2023, 2023.
[19] Gwendoline De Bie, Gabriel Peyré, and Marco Cuturi. Stochastic deep networks, In Interna- tional Conference on Machine Learning, pages 1556-15555 1565. PMLR, 2019.
[20] Mateo Díaz, Dmitriy Drusvyatskiy, Jack Kendrick, and Rekha R Thomas. Invariant kernels: Rank stabilization and generalization across dimensions. arXiv preprint arXiv:2502.01 2025.
[21] Jean Dieudonné. Foundations of Modern Analysis. Academic Press, New York, 1969.
[22] Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in neural information processing systems, 32, 2019.
[23] Nadav Dym, Hannah Lawrence, and Jonathan W. Siegel. Equivariant frames and the impossi- bility of continuous canonicalization. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pages 12228 12267. PMLR, 21-27 Jul 2024.
[24] Giuseppe Alessio D'Inveroo, Monica Bianchini, and Franco Scarselli. Ve dimension of graph neural networks with pfaffian activation functions. Neural Networks, 182: 106924, 2025.
[25] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in neural information processing systems, 32, 2019.
[26] Nicolas Fournier. Convergence of the empirical measure in expected wasserstein distance: non-asymptotic explicit bounds in Rd. ESAIM: Prohability and Statistics, 27:749-776 -75, 2023.
[27] Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Transactions on Signal P Processing, 68:5680-5695, 2020.
[28] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference Machine Learning, pages 3419-3430. PMLR, 2020.
[29] Mario Geiger and Tess Smidt. e3nn: arXiv:2207.09453 2022.
Euclidean neural networks.
arXiv preprint
[30] Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. A mathematical perspective on transformers. Bulletin of the American Mathematical Society, 62(3):427-479, 2025.
[31] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1262-1272. PMLR, 2017.
[32] Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
[33] Wilson G Gregory. David W Hogg, Ben Blum-Smith Maria Teresa Arias, Kaze WK Wong, and Soledad Villar. Equivariant geometric convolutions for emulation of dynamical systems. arXiv preprint arXiv:2305. /2585, 2023.
[34] Martin Grohe. The logic of graph neural networks. 202/ 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-17. IEEE, 2021.
12

---

[35] Daniel Herbst and Stefanie Jegelka. Higher-order graphon neural networks: Approximation and cut distance. arXiv preprint arXiv:2503.14338, 2025.
[36] Ningyuan Teresa Huang and Soledad Villar. A short tutorial on the Weisfeiler-Lchman test and its variants. In ICASSP 2021-202) IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4533-8537 IEEE, 2021.
[37] Svante Janson. Graphons, cut norm and distance, couplings and rearrangements. New York journal of mathematics, 2013.
[38]
Fabian Jogl. Maximilian Thiessen, and Thomas Gärtner. Expressivity sppressivity-prseevingg GNN simula- tion. Advances in Neural Information Processing Systems, 36, 2024.
[39] Haotian Ju, Dongyue Li, Aneesh Sharma, and Hongyang R Zhang. Generalization in graph neural networks: Improved pac- pac-bayesian bounds graph diffusion. In International conference on artificial intelligence and statistics, pages 6314 111-64411 PMLR, 2023.
[40] Sékou-Oumar Kaba, Arnab Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravan- bakhsh. Equivariance with learned canonicalization functions. In International Conference on Machine Learning, pages 15546-15566. PMLR, 2023.
[41] Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convo- lutional networks on large random graphs. Advances in Neural Information Processing Systems, 33:21512-215233 2020.
[42] Sammy Khalife and Josué Tonelli-Cueto. Is uniform expressivity too restrictive? towards efficient expressivity of GNNs. In The Thirteenth International Conference on Learning Representations, 2024.
[43] Hyunjik Kim, George Papamakarios, and Andriy Mnih. The lipschitz constant of self-attention. In International Conference on Machine Learning, pages 5562-5571. PMLR, 2021.
[44] Risi Kondor. N-body networks: covariant hierarchical neural network architecture for learning atomic potentials. arXiv preprint 1 0158, 2018
[45] Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution neural networks to the action of compact groups. In International conference on machine learning, pages 2747-2755. PMLR, 2018.
[46] Thien Le and Stefanie Jegelka. Limits, approximation and size transferability for GNNs on sparse graphs via graphops. Advances in Neural Information Processing Systems, 36, 2024.
[47] Ron Levie. A graphon-signe analysis of graph neural networks. Advances in Neural Information Processing Systems, 36, 2024.
[48] Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 12(272):1-59, 2021.
[49] Eitan Levin and Venkat Chandrasekaran. Free descriptions of convex sets. arXiv preprint arXiv:2307.04230. 2023.
[50] Eitan Levin and Mateo Díaz. Any mine-nmeniional equivariant neural networks. In International Conference on Artificial Intelligence and Statistics, pages 2773-2781. PMLR, 2024.
[51] Zongyi Li, Nikola Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar. Fourier neural operator for parametric partial differen- tial equations. arXiv preprint arXiv:2010.0888 008895 2020.
[52] Renjie Liao, Raquel Urtasun, and Richard Zemel. A PAC-bayesian approach to generalization bounds for graph neural networks. International Conference on Learning Representations, 2020.
13

---

[53] Jiawei Liu, Cheng Yang, Zhiyuan Lu, Junze Chen, Yibo Li, Mengmei Zhang, Ting Bai, Yuan Fang, Lichao Sun, Philip S Yu, et Towards graph foundation models: A survey and beyond. arXiv preprini arXiv:2310. 1829, 2023.
[54] László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
[55] Shaogao Lv. Generalization bounds for graph convolutional neural networks via rademacher complexity. arXiv preprini arXiv:2102. 2021.
[56] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint 11Xiv:1812.099902, 2018.
[57] Sohir Maskey, Gitta Kutyniok, and Ron Levie. Generalization bounds for message passing networks on mixture of graphons. arXiv preprint arXiv:2404.0347, 2024.
[58] Sohir Maskey, Ron Levie, and Gitta Kutyniok. Transferability of graph neural networks: an extended graphon approach. Applied and Computational Harmonic Analysis, 63:48-83, 83, 2023.
[59] Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. Advances in neural information processing systems, 35:4805-4817, 17, 2022.
[60] Facundo Mémoli. Gromov-Wassersee Wasserstein distances and the metric approach object matching. Foundations of computational mathematics, 11:417-487, 2011.
[61] L. Mirsky. Symmetric gauge functions and unitarily invariant norms. The Quarterly Journal of Mathematics, 11(1):50-59, 1960.
[62] Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe. WI meet vc. In International conference on machine learning, pages 25275-25302. PMLR, 2023.
[63] Victor M Panaretos and Yoav Zemel. An invitation to statistics in Wasserstein space. Springer Nature, 2020.
[64] Tomas Pevny and Vojtech Kovarík. Approximation capability of neural networks on spaces of probability measures and tree-structured domains. arXiv preprint arXiv: 1rXiv:/906.00764 2019.
[65] Gabriel Peyré and Marco Cuturi. Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning, 11(5-6):355-077, 2019.
[66] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 652-660, 2017.
[67] Maziar Raissi, Paris Perdikaris, and George E Karniadakis. informe- neural networks: deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational physics, 378:686-707, 2019.
[68] Levi Rauchwerger, Stefanie Jegelka, and Ron Levie. Generalization, expressivity, and universal- ity of graph neural networks on attributed graphs. In The Thirteenth International Conference on Learning Representations, 2025.
[69] Eran Rosenbluth, Jan Toenshoff, and Martin Grohe Some might say all you need is sum, arXiv preprint arX 1603, 2023.
[70] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the trans- ferability of graph neural networks. In H. Larochelle, M. Ranzato. R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1702-1712. Curran Associates, Inc., 2020.
[71] Luana Ruiz, Luiz FO Chamon, and Alejandro Ribeiro. Transferability properties of graph neural networks. IEEE Transactions on Signal Processing, 2023.
14

---

[72] Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Graph neural networks: Architectures, stability, and transferability. Proceedings of the IEEE, 109(5):660 682, 2021.
[73] Luana Ruiz, Ningyuan Teresa Huang, and Soledad Villar. spectral analysis of graph neural networks on dense and sparse graphs. In ICASSP 2024-2024 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 9936 99400 IEEE, 2024.
[74] Michael E Sander, Pierre Ablin, Mathieu Blondel, and Gabriel Peyré. Sinkformers: Transform- ers with doubly stochastic attention. In International Conference on Artificial Intelligence and Statistics, pages 3515-3530 PMLR, 2022.
[75] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The Vapnik-Chervonenki dimension of graph and recursive neural networks. Neural Networks, 108:248-259, 2018.
[76] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithmss Cambridge university press, 2014.
[77] Sashi Mohan Srivastava. A course on Borel sets. Springer, 1998.
[78] Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-an caanslaton-equivariaae neural networks for 3d point clouds. arXiv preprint arXiv:1802.082/1 2018.
[79] Antonis Vasileiou, Ben Finkelshtein, Floris Geerts, Ron Levie, and Christopher Morris. Cov- ered forest: Fine-grained generalization analysis of graph neural networks. arXiv preprint arXiv:2412.07106, 2024.
[80] Antonis Vasileiou, Stefanie Jegelka, Ron Levie, and Christopher Morris. Survey generaliza- tion theory for graph neural networks. arXiv preprint wiXiv:2503.15633 2025.
[81] Mauricio Velasco, Kaiying O'Hare, Bernardo Rychtenberg, and Soledad Villar. Graph neural networks and non-commuting operators. Advances in neural information processing systems, 17:95662-95699 2024.
[82] Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2003.
[83] Soledad Villar, David W Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars universal: Equivariant machine learning, structured like classical physics. Advances in Neural Information Processing Systems, 34:28848-2888
2021.
[84] Soledad Villar, Weichi Yao, David W Hogg, Ben Blum-Smith, and Bianca Dumitrascu. Dimen- sionless machine learning: Imposing exact units equivariance. Journal of Machine Learning Research, 24(109):1-32 2023.
[85] Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances Neural Information Processing Systems, 31, 2018.
[86] James Vuckovic, Aristide Baratin, and Remi Tachet des Combes. A mathematical theory of attention. arXiv preprini arXiv:2007.02870 2020.
[87] Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3D ShapeNets: A deep representation for volumetric shapes. PrreesssnnPrrroorooorrrrrrr Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1912 1920, 2015.
[88] Huan Xu and Shie Mannor. Robustness and generalization. Machine learning, 2012.
[89] Gilad Yehudai, Ethan Fetaya, Eli Mcirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In International Conference on Machine Learning, pages 11975-11986. PMLR, 2021.
[90] Y. Yu, Wang, and R. J. Samworth. useful variant of the Kahan theorem for statisticians. Biometrika, 102(2):315-333, 04 2014.
15

---

[91] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
[92] Aaron Zweig and Joan Bruna, functional perspective on learning symmetric functions with neural networks. In International Conference on Machine Learning, pages 13023-13032. PMLR, 2021.
A Notation
We use R and N denote the sets of real numbers and natural numbers. We use the pair (N, =) to denote a directed poset natural numbers, used for indexing. We write [n] to denote the set (1. J. The symbols and U are used for consistent sequences, and Vn, Un for the corresponding vector spaces at finite levels. General groups are denoted by G.: we use S, for the symmetric group and (lk) for the orthogonal group. We denote embeddings of vector spaces from dimension n to N by (PN., and nn. Embeddings of groups are denoted by 8N.,. We use "o" to denote the composition of functions, and id for the identity element in a group or the identity map, depending the context. Binary operations in groups denoted by "x", with subscripts such as "*," " used when clarity is needed, e.g., to indicate the operation in the group G,,- Group actions are denoted by ".", with subscripts such as ",," " when needed.
We write ~ to denote equivalence relations, and use [x]] to denote the equivalence class of æ; i.e., [x]] {y: y v). We write V and A for maximum and minimum respectively. In a metric space, we use rz) to denote the ball centered at zo with radius r, i.e. B(xo, r) = {ar d(xo, 2) < r). Given a set S. the symbol 3 denotes either completion or closure, depending on the context. Given a function f. the symbol denotes a normalized variant of that function. Given two sequences (an), (b,) S R. we write an S b,, if there exists a constant C' > 0 such that an S Cb2 for all n E N. For a given function R: : + R.,, we say a sequence (Ir,) converges to x at rate R(n) with respect to distance metric d if d( [n, .r) S R(n) and R(n) 0. For matrix X, we use X to denote the vector formed by its i-th row. This work employs several norms: || |Ip refers to the standard n,-norm (for vectors and infinite sequences) or T.P-norm (for functions). while | denotes their normalized counterparts which will be defined later. The operator norm of a linear map T' V + W between two normed spaces is denoted ||T'|op == supi|t|== ||T'']] its definition inherently depends on the specific norms chosen for V and W. Particularly, || llop.p.q denotes the operator norm when the domain is equipped with the E, no-m (or L"-norm) and the codomain with the ly norm (or L9-norm), we use || llop.p an abbreviation for || Ilop.p..-
B Related work
GNN transferability. The work on GNN transferability under the graphon framework was pioneered by [70], focusing on a variant of graph convolutional network (GCN) for deterministic graphs obtained from the same graphon. In parallel. [48] explores transferability with respect to an alternative limit space to graphon in the form of topological space, and [41] examines an arguably equivalent notion- convergence and stability- by analyzing random graphs sampled from a graphon. This line of research has since been further developed [71, 58), extending to more general message-passinn passing networks (MPNNs) [18], more general notion of graph limits [46], and other models [73, 81. 11, 35]. Our framework unifies and recovers several of the above-mentioned results, which we briefly discuss in Appendix G.2. Furthermore, we develop new insights into the transferability of Invariant Graph Networks (IGNs) [56], a topic previously examined in [11, 35]. We leverage our framework to advance this line of inquiry and elaborate on the connections between our approach and prior work in Appendix G.3.
GNN generalization. A related line of research concerns the generalization theory of GNNs. Gener- alization bounds have been derived based on various frameworks, including Rademacher complex- ity [28, 55], VC dimension [75, 62, 24], the PAC- ACC-Bayesian approach [52, 39], the neural tangent kernel [22], and covering numbers [59, 57, 47, 79, 68]. Notions of size generalization without an explicit notion of convergence have been studied in [89, 4]. For a comprehensive overview, we refer the reader to the recent survey [80]. While most research GNN generalization bounds consider
16

---

graphs of fixed or bounded size, [47, 68] explore the "uniform regime," addressing unbounded graph sizes. This perspective closely aligned with the transferability theory, as they both consider continuous extensions over suitable limit spaces. Our work formalizes this connection, showing that transferability implies generalization (Section 4, Appendix E). We derive a generalization bound via covering numbers using the same proof strategy as prior works, but it applies well beyond GNNs and offers a setting that directly connects to the notion of size generalization.
Equivariant machine learning. Our theory naturally applies to equivariant machine learning models, Le., neural networks with symmetries imposed. We particularly focus on models from [91, 56, 66, 72, 5J. There are many other equivariant machine learning models we haven't I discussed here, such as the ones expressed in terms of group convolutions [17, 45, 33], representation theory [44, 78, 29], canonicalization [40], and invariant theory [83, 6, 84), among others.
Representation stability and any-dimensional learning. As noted by [49, 50], the presence of symmetry allows functions operating on inputs of arbitrary dimension to be parameterized with a finite number of parameters, which may be partially explained by the theory of representation stability [15]. Leveraging techniques from this theory, [50] provides the first general theoretical framework for any-dimensional equivariant models. Recent work applies similar techniques to study the generalization properties across dimensions of any-dimensional regression models [20]. Our work builds on the theoretical foundation established by this line of research.
Any-dimensional expressivity and universality. Our framework naturally prompts the question of expressivity for any-dimensional neural networks on their limit spaces. While we do not pursue this direction here, related questions have been independently studied. [9] shows that normalized DeepSets and PointNet are universal for uniformly continuous functions on suitable limit spaces, closely tied "eppeetttiieexeeiiiiinneee
to our results (see Appendix F.2.1). In GNNs, the notion of "uniform logical queries without parameter dependence on input size- has been explored in [34, 2, 42, 69]. Our framework offers complementary insights despite differing foundations.
C Consistent sequences and compatible, transferable maps: details and missing proofs from Section 2
C.1 Consistent sequences and limit space
The concept of consistent sequences originated in the theory of representation stability [16]. We generalize this notion, originally considering a sequence of vector spaces, by allowing indexing over any directed poset on the natural numbers. Although we focus on natural numbers in this work, our theory generalizes to any directed poset.
Directed poset indexing. We require the indexing set (N, -) to be a directed poser on natural numbers, meaning that N is the set of natural numbers equipped with binary operation = satisfying:
(Partial order) The binary operation < a partial order; that is, it satisfies: reflexivity (a - a for all a E N), transitivity (if = and b 3 c. then a - c), and antisymmetry (if a = b and - a, then a = b).
(Upper bound condition) For every pair a, b N, there exists e N such that and b 3 c.
The directed poset indexing generalizes the notion of sequences to allow more complex and flexible way of defining how smaller problem instances are embedded into larger ones, permitting "branching" directions of growth. We will see that the upper bound condition is crucial, as it ensures that any two problem instances are comparabee-meaning they can both be embedded into third, larger problem dimension and compared there. In this work, we only consider two cases: the natural numbers with the standard ordering S, and with the divisibility ordering, where a < b if and only if a b.
Definition C.1 (Consistent sequence: detailed version of Definition 2.1). A consistent sequence of group representations over directed poset (N, 3) is V {(VW)nEN, (PN,,)=2N, (Gn)nen), where
1. (Groups) (G,, is a sequence of groups indexed by N such that whenever n 3 N. Gn is embedded into Gn via an injective group homomorphism N Gn + GN. where
0i, idc, for all E N,
0n 00,5 02,i whenever = j 3 k in N.
17

---

2. (Vector spaces) (V,) is a sequence of (finite-dimensionn real) vector spaces indexed by 1, such that each Vn is a represseenttinnn and whenever n. N, Vn embedded into Vn through linear embedding PN,, Vn - VN, where
Pi = idv; for all i N, Pk. Pj = Pk. whenever コ N. 3. (Equivariance) Every NN is G,, -eueuvrrri,,,, i.e.,
NN v) (g,( "PN,(()) for all Gny E Vn.
Given a consistent sequence, we can first "summarize" the sequence of groups (Gn) into a single limit group Goc, and likewise "summarize" the sequence of vector spaces (Vn) into single limit vector space Vo We can then consider the action of G. on Vx-
Definition C.2 (Limit group: detailed version of Definition 2.3). The limit group Goo defined as the disjoint union Lm, Gn modulo the equivalence relation that identifies each element E Gn, with its images under the transition maps N, (g) for all N 2 n, i.e.,
Go
GG///
where ~ (g. whenever n 3N N and g E G,. This construction is also known as the direct limit of groups, and is denoted by G = limg G,. For each Gn, its equivalence class in Goc is denoted by [g), representing the corresponding limiting object.
The group structure on Go inherited from the groups (Gn) as follows. For On. G, and Jm Gma define the binary operation equivalence classes by
[gn] [gm]] = (0x,((n))
ON.m (ym)],
where N E N is common upper bound of and in (N, 3), and & denotes the group operation Gn. It is straightforward to check that this operation well-defined.
Definition C.3 (Limit space of consistent sequence: detailed version of Definition 2.3), Define Voe as the disjoint union LV, modulo an equivalence relation identifying each element v V, with its images under the transition map (n for all 3 N, i.e.
Voc
Vn/~
where u ru (1) whenever n N. This construction also known as the direct limit of vector spaces, and is denoted as V lim Vn-
The vector space structure on Vo is inherited from the vector spaces (V,) as follows. For Un E Vn Um Vms the addition and scalar multiplication the equivalent classes defined by
[e,] + [um]] = (n,, + (em)) where N is an upper bound for n, in (N, =),
A(e.]= = [Av.]-
is straightforward to check that these operations are well-defined. The limit group Goo acts on Vos by
[g] [e] == [@ (g) 'N (N. (v)] for E G,, v E Vm.
where N is upper bound of m in (N, 3) and is the group action of GN on Vy- It is also easy to check that this group action well-defined, and Voo is -eereeprseettation The orbit space of Vos under the action of G. is
{Gx x x: Voch
where G. x = {g
E Gx is the orbit of point x E Voc under the G.. -ction. The orbits form a partition of V. into disjoint subsets.
Consistent sequences without symmetries. A special case of consistent sequences arises when G, {id}. the trivial group, for all N. In this case, the structure reduces to directed system of vector spaces
= ((V.) ((N,)))3N)
Hence, our theory of size generalization applies in scenarios where no intrinsic symmetries are present.
18

---

Trivial consistent sequence. Another special case arises when V2 V, fixed vector space, for all N, with embeddings given by N. idy for all n 3 N. This yields the trivial consistent sequence associated with V. which we denote by Vv. This construction is useful for modelling non-size-dependent spaces, such as the output space graph-level classification or regression tasks.
Direct sum and tensor product. Given a consistent sequence V = ((V)), (P,,,.), (G,)), we can define its direct sum and tensor product. Both of them are also consistent sequences.
Definition C.4. The d-th direct sum of 4 is defined as
((V. ( (Gn));
where Vied denotes the direct sum of d copies of Vn and 4 Vied - Vida is defined by applying N,, each component. The group Gn acts on V by simultaneously acting on every copy of Vn. Lee 9 (Ul,..., .da) == (g- v1,....
9
va).
Definition C.5. The d-th tensor product of is defined as
vrdd = ((V,
Rd (G,))
Ød where Vdd denotes the d-fold tensor product of Vn, PN, V N uniquely defined by Ed PN, (v) @ ... @ va) == (N, 000000000000))) ... Nn (va), and the group action of Gn. on V is uniquely defined by g- (e) @ ..... va) = (g v1) @ @ (g va). The universal property of tensor product guarantees that YN. and the group action mentioned are well well-defined. Similarly, also consider the d-th symmetric tensors V as
3d
SV) {(Sym"(Vv)) N, (G,)),
where Sym (V.) denotes the space of symmetric tensors of order d defined on Vn, i.e. the subspace of @d invariant under the action of the symmetric group S.-
The direct sum, yod is particularly useful for incorporating hidden channels into our analysis, as it effectively adds the extra channel dimensions helpful to extend a consistent sequence on vectors or sets to higher-order objects such as matrices graphs. For example, the duplication consistent sequences for graphs exactly arise as the 2nd symmetric tensors of the duplication consistent sequences for sets.
data. In contrast, the tensor product, 7/8d is
C.2 Compatible maps
Recall from Definition 2.4 that sequence of maps (fri Vn - Un) is compatible with respect the consistent sequences V, U if, for all n 3 N,
SN o PNN, vNN, fn:
and each f., is -n-equivariant. This condition is equivalent to the existence of an extension to the limit map fzo.
Proposition C.6 (Compatible maps and extension limit). Let V {(V.), (PN..). (Gx) and = (U (wb,,)) v. (G,)) } be two consistent sequences. A sequence of maps (fn: Vn - U.) is compatible and only if it extends to the limit; that is, there exists -ee-euvvariant map
Joc: Voo + Uno
such that fn Sox Iv, for all n.
Proof. (+) Suppose there exists Go -equivariai map fox such that fn foolv, for all n. Then for n N and Vn.
[fa(x)] foo ((x) for ([pN), [fv((N..(=))],
which implies fN o ON.. = UN.. fa. Moreover, for all n E N, E Vn, and g E G.,
[g =)] (ig = (lo [z]) [gl f ([x)) = [g] [f)(z)] [g fn(x)).
so each fr is G, -qquivarri....
19

---

Conversely, suppose (fr) are compatible. Define
fo V - So, (xx()) = [f())) i E V..
Compatibility ensures this well-defined. verify equivariance, let E Gm and x E Vns and let N be a common upper bound of n and m in (N, 3). Then,
Soo (1g [x=] = foc (m (x)))
[fN ma (g) NN,, (2))
m (g) fN (4 (x)))
N (g) WNN, (fr (x)))
= [9] foe ((x)).
Therefore, foo is -
This proposition implies that learning function on the dnfiniteddimensionn space V task that may appear difficult, reduces to learning compatible sequence of functions on the finite-dimensional vector spaces along the sequence, which is a more tractable problem.
C.3 Metries on consistent sequences
In Section 2.1, we introduced a norm on Voc so as to define distance between objects of different dimensions. In this appendix, we take a more general perspective and examine metric structures on consistent sequences, and present detailed proofs. The same proofs carry over to the norm setting with minimal modification.
Definition C.7 (Compatible metries: generalized version of Definition 2.5). Let V
{(V.), (n (G,)) be a consistent sequence. A sequence of metrics (d,) on the vector spaces Vn said to be compatible all the embeddings N, and the Gn-actions are isometries. That is, for all 3 N, K, E Vn, and g E Gn. we have;
dy dN(( (N) = (z, y), and dg b.lg-2.9. 2. y) (x,
Similar to compatible maps, this is equivalent the existence of extension to metric d on Voc Proposition C.8 (Compatible metrics and extension to the limit), A sequence of metrics (d,) on the spaces Vn is compatible if and only if extends to a metric on the limit space. That is, there exists metric dos V such that
dn(I,)) doo ([x), (vl) for all n E N. x. Vnn
and the G on Vo is an isometry with respect to doc. i.e.,
dg x. y) = (x,y) for all x, y E V 9 E G
Proof. The proof is primarily matter of bookkeeping, similar in spirit to Proposition C.6. For completeness, we present the full argument below.
(+) Suppose (dw) extends to metric das on Voc Then for all = N and a, y E Vn, we have (x. y) = dos ([x), [v]) = da (l (x)) (v),,, = d.y nn (x), (v)) Thus, the embeddings N.n are isometries. Moreover, for any g G, and w, y Vn.
(g x, 4) doc (lg r), Ig w)) doo (1g) [x], [g] [v]) doo (1r), [w]) dn (z, v),
so the group actions are isometries well.
(+) Conversely, suppose the collection (d,) is compatible. Define metric doe Voo x Voo - R as follows: for æ E V,, and y E Vm. let N be any common upper bound of n and m in (N, =), and set
do [[x], [v]) = d (z),
Compatibility of the metrics ensures that dhg well-defined. is also easy to check that dos is metric. Moreover, by construction, d,, doolv, for all n.
20

---

To verify that the Gæ-accton is isometric, take E Vn,, Vnz, and E G, for some n E N. Let N be a common upper bound of n., ni, n2 (NN 3). Then,
((g) [2)] [g] [)] = dx (g) spN,. (x), ON, (0) (N),g(
( (I)), (nN, (1))
doo (1x)
This completes the proof.
With the metric structure in place, we define the limit space via the completion of the metric space. The completion of metric space M is a complete metric space M-thht is, a space in which every Cauchy sequence converges- that contains M as a dense subset (i.e., the smallest closed subset of M containing M M itself).
Definition C.9 (Limit space: detailed version of Definition 2.7). Let V be a consistent sequence, and let Sx be equipped with the metric doc. Denote by Vou the completion of Voe with respect to dec. The -action Voc extends to well-defined action Voo as follows: for any Voo and g E Goc, choose a sequence (In) in Voo such that In + x in Voc. and define
g- === lim 9 In-
n
This limit exists because (g-In) is Cauchy sequence, as the -action Voo is isometric. The resulting action on Voc is linear and isometric. We define the limit space of the consistent sequence to be the G represersenooooonn Vas.
The set of orbit closures in Voo under the action of Goo is
{Gx 22 Voo)
where Gx ' is the closure of the orbit Goo x. Intuitively, Vo includes not only elements from minte-dimensional objects (elements in Voo,, but also additional points that are "reachable" as limits of finite-dimensional objects. We can further define symmetrized metric on the limit space. Proposition C.10 (Symmetrized metric). Let x, E Voc Define
d(z, inf dx xx,). gEGx
Then d is pseudometric on Voo and induces a metric on the space of orbit closures in Voo under the Gno-action. We refer to d as the symmetrized metric.
Proof. The non-negativity
follows directly from the non-negativity of doc
(Symmetry) Since doe (g x, y) (x, -1. y) for any Goo by isometry of the G -cction, taking the infimum over all g E Goc (equivalently over g yields
d(z, v) = x)),x)).
(Triangle inequality) Let > O. Then there exist g, h Goo such that
d(z, y) doe (g x, v) e, a(y, doe (h y,, Using the isometry of the group action:
d(z, y) + d(y, 2) > (g I, v) + doc (h y: 2) - 28 doo (hg v. h y) + doo (h y: 2s
> do (hg x, x) 25
2 d(z, 2) 25.
Since this holds for arbitrary > 0, the triangle inequality follows.
(Definiteees) We have d(z; y) = 0 and only if there exists a sequence (gn) C Goo such that dxe (gn x. x, + 0. This is precisely the condition that E Go Ir i.e, x and lie in the same orbit closure.
Therefore, d a pseudometric on V.s and descends to true metric on the space of orbit closures which completes the proof.
21

---

D Transferability: details and missing proofs from Section 3
D.1 Transferable maps
Following Definition 3.1 of continuously, I--Lipschitz and L(r)-locally Lipschitz. transferable, we further define the following notion: If (fn) sequence of equivariant maps extending foe which is locally Lipschitz at ro we say (fn) is locally Lipschitz transferable at zg. Being locally Lipschitz transferable at 2 is weaker condition than being Lrr)-loclly Lipschitz transferable, which is itself weaker than L-Lipschitz transferable. This definition is useful when studying models which are discontinuous on negligible sets of inputs, and which are therefore not L(r))locall, Lipschitz transferable. These often come up when constructing architectures based on canonicalizations [23], as commonly done for point clouds for instance (see Section 5.3).
We first show a useful property that saarinuity/L-iipchii with respect to || Ilv.. Il llu. implies the same property with respect to the symmetrized metrics, even though the converse does not hold. We will again state and prove the results for metrics instead.
Proposition D.1 (Continuity in doc implies continuity in d). Let V, be consistent sequences. If fox : V.o + & is continuous (respectively, L(r)-Lipcchizz on B r) for all r > 0, L-Lipschitz, locally Lipschitz at zo E Vxz) with respect to d% and d% then Joa satisfies the same property with respect to the symmetrized metrics dy and dy.
Proof. (Continuity) Let Fn - x Voe with respect to the symmetrized metric dy, and > 0. By continuity of for with respect to dxc, there exists 8 > 0 such that whenever doo y) < 8, doo (Joo (2), foo()) < Take N such that for all 2 N, dv(Zn, x) < 4. Moreover, for each choose In. E Gx such that dxo (9n In; x) S dv (I x) + z. Then for all n 2 N. doo (gn In,
and hence
( foc()) S (gn foo (xn) (foo =a). <E
Therefore fee (In) + (x) with respect dy.
(Lipssiips on B(0,r) r)) Suppose foe is Lir)-Lipschitz on B(0,r) for all with respect to dxc Consider x, y such that dy (0, d% (0, x) r. and (0, v) d% (0. v) Then for any g E Gx. we have d% (0, x) = d (0, x) < r. Hence,
(f). (v)) I d (g- foo (r), for (v)) = (S (g. f) < ((r) x,
Take infimum over g E Ge.. get du (f (x), (v)) s L(r) (z.
(Lipschitz) For any x, y E Voo, E Go..
())sso (v)) < doo (g) (xx) (v)) (Jo (g x), (v)) S Ld Take infimum over g E G.c. get du (Szo (I)), (v)) (x,,
(Locally Lipschitz at mn) Suppose d (f(x), I (xo)) S Ldvo (z, 2o) whenever doo xo) < Then for any such æ we have dv (z, zo) = inf G doo (a, 20) where GLd = (g E Goo dxo (z, xo) S r). Moreover, for any E G(r) we have de f < doe (f x). (xo)) S Ld x, x..), so after taking infimum over such y we conclude that de (f(x), [ ((0)) S I. (d whenever d < r, as desired. This completes the proof of the proposition.
Finally, we state and prove set of more concrete characterizations of Lipschitz transferable sequence of functions defined in Definition 3.1, which are straightforward to check.
Proposition D.2. Let V, U be consistent sequences endowed with metrics.
"We say foo is locally Lipschitz at 2o if there exists r > and L > 0 such that for all x E B(xo. r). (fo (x), foo (xx)) < Ld (x, 2o). Notice that this is slightly different from saying foo is locally Lipschitz around 20. which means that there exists > 0 and L > 0 such that foo is L-Lipschitz on B(xo.
22

---

1. (General case) A compatible sequence of functions (fn Vn - Un) is L-Lipschitz (respectively, Lipschitz) transferable if and only if for all n, fo. L-Lipschitz (respectively, Lipsship on B, (0, = {u E VV
(0, v) r)).
2. (Linear maps) When the metrics are induced by norms, compatible sequence of linear maps (Wn: Vn + Un) is continuously (respectively, L-Lipschitz) transferable if and only if sup, ||,,, llop < oc (respectively, sup,, [W S L).
Proof. We begin by deriving the result for the general case.
General case. The "=" direction again follows immediately from d, = doolvv, fn = fool for all n. We focus on proving "<"". First, by Proposition C.6, compatibility implies that the sequence (fr) extends to a function for: Vo + USo
(Lipschita) Suppose fn is L-Lipschitz for all For any Vn and y Vm. let N be common upper bound and m in (N. 3). Then:
d (foo ((x)) for (lvl)) = d' (f
S L d (pN,(())
d ([x), (y]).
Hence, for is L-Lipschitz Voo-
Since Lipschitz continuity implies Cauchy continuity, foo extends uniquely to foo : Vo - Uxo For any Cauchy sequences (xr)) and (ya) in Voo with limits x; Voo, have:
(V)) = lim (() (ox)
n-00
s lim Ld (Ins (n) L d% (I,
which shows that foo remains L-Lipschitz after extending to V.c.
(Trr)-occally Lipschitz) Suppose each fn is L(r)-Lippp (ip]chiip on (0, r) for all > 0. As above, for any x Vn, and y Vm with di (0, x), dm (0. y) r, let N be a common upper bound of m in (N, z). Then (N,, F (3) By (0, r), and by the L(r)-Lipschitz property of fN on BN (0, r), we get
(foo fox (l)) S L(r) d% ([x) [v]).
Thus, for Vo + Uno is L(r) Lipshhizz on fu Voc d% (0, v) <r).
This implies foo Cauchy continuous: any Cauchy sequence (xx,) lies within some ball of radius R, and since Joo is Lipschitz continuous there, (Joc (Tn)) is also Cauchy. Hence, Soo extends uniquely to V and it is easy to check that it is [rr)-Lipshhtzz on B(0,r) for all r.
Linear maps. We leverage the argument for the general case to derive the two stated claims.
(Lipschitz) By our argument for normed spaces, (W,) is I--Lipschitz transferable and only for all n, W,, is T-LLipschitz. By linearity of each W.. this is equivalent to |WWllopp S L. for all n.
(Continuity) It is sufficient to prove that (Wn) is continuously transferable if and only if it is L-Lipschitz transferable for some > 0. The "=" direction is immediate. To prove "=". suppose (Wn) extends to continuous function Woo V. Use Then Woo is linear on Voe because for any I E Vn E Vn, and any common upper bound N of n,, m in (N, 3), we have
W (a[x) + b(yl) = [WN(apx.n + by (v)) = a aW ([=)) + bW ([v))-
By continuity of W... it remains linear on V.. The result follows since for linear operators, Lipschitz continuity and continuity are equivalent.
Thus, the proof is finished.
23

---

D.2 Convergence, transferability and stability
Stability. The following stability result states that small perturbations of the input (e.g.. adding small number of nodes to a graph) lead to small changes in the output. It resembles the stability considered [70].
Proposition D.3 (Stability: detailed version of Proposition 3.2). If the sequence of maps (fn: Vn U,) L(r)-locall, Lipschitz transferable, then for any two inputs In E Vn and I'm E Vm of any two sizes n, with d (0, In), dm (0, Im) S, we have
&% (I (mm((m))) & Ldd [mm])- (Em))
Moreover, the same holds when replacing every d with the symmetrized metric d.
Convergence and transferability: deterministic sampling. For a sequence of inputs (Ix)) sampled (deterninistically) from the same underlying limiting object æ. the outputs of transferable function satisfy fn (rn) R fm (Im) for big m, and converge as fn foe (z). We provide examples of sampling procedures later in Appendix D.3.
Proposition D.4 (Convergence and transferability: detailed version of Proposition 3.2). Let (In VA VEN be sequence of inputs sampled from a limiting object Vxs such that [xn] + x at a rate R(n) with respect dy
1. (Asymptotic) If (Jn: Va - Un)DeN is continuously transferable, then the following holds.
(Convergence) The sequence [f (xx)) -> foo (x) (x) with respect to d (Transferability) The distance dh (lf (2,)) (mm))))))))))) - as n, m + 00.
2. (Nonasymptotic) If (fn: Vn + Un)NEN is locally Lipschitz transferable at x, then the following holds.
(Convergence) The sequence [Jn (2()))) (xx at rale R(n) with respect to d (Transferabilltyy) The distance is bounded by d% ([fn(1n)), [fm()))) & R(n) R(m).
That is, Lipschitzness provides quantitative guarantees for the convergence rate. We remark that by By Proposition D. the same holds when replacing every dos with the symmetrized metric d.
Proof. We start by noticing that both transferability results directly follows from convergence, thanks the triangle inequality
doo (F, (x,m)) s (l. doc (Im()
To show convergence in under continuous transferability, observe that if foo is continuous, then (x,)) = ((o,))
(2x) immediately follows.
Next, we establish the guarantee under local Lipschitz transferability at æ. Suppose foo locally Lipschitz at Then there exists r > 0 such that for all y E B(x, r), we have doo (Soo (2)), foo (v)) s Ld (x, y). Let N be large enough so that In E B(x,r) r) for all n 2 N. Then for all n 2 N, we have
(x), (x,))) =
((xxI) S L (x, [2a]) S R(n),
claimed; finishing the proof of the proposition.
Convergence and transferability: random sampling. Under random sampling of inputs, we need to specify the mode of convergence. In the case where 2, almost surely rate R(n). the results are identical to the deterministic case: both convergence and transferability hold almost surely. We now consider different mode of convergence convergence in expectation. As will see in Appendix D.3, many common sampling procedures satisfy this condition.
Proposition D.5 (Convergence and transferability: Random sampling). Let (x,, E Vn) be a sequence of inputs randomly sampled from a limiting object V.c. such that [xn] - in expectation at rate R()) with respect to dy Lee E Eldy ([xw), x)] S. R(n) and R(n) - O. Suppose (Jn: Vn, - Un) locally Lipschitz transferable x, ie.. Soo is L-Lipschitz on B(x,r). Further, assume that there exists M. > 0 such that
E [d>> (foc foo (z)) B(z,r)) ME |doo ([xn),
(2)
24

---

(Convergence) The function values converge in expectation
((o)s) & R(n).
(Transferability) The distance converges in expectation
Bld (d (fm((m))) S R(n) - R(m).
The assumptions in this proposition are rather mild. Indeed. (2) amounts to a localized version of uniform integrability. Simple arguments show that these assumptions are satisfied under any of the following scenarios: (i) the sequence (fn) is globally Lipschitz transferable, (it) the map foe bounded or (iit) the sequence (#n) is supported on r)) Furthermore, the same conclusion remains valid when replacing dxs with the symmetrized metric d.
Proof. Suppose for all E B(x, r), we have (z), (v)) S (r, v). Then, (1),
EE do (Sso (oo,,)) 1[ B(x,r)) + ME [d (z, [x,])] EE [do (I, [x,)) H[ ((x, + ME [dx [do
[r,]]]
2 R().
Transferability then follows by the triangle inequality.
D.3 Convergence rates under sampling
Propositions D.4 and D.5 show that for Lipschitz transferable models (f²), the convergence of fu (xr) to (x) is least fast the convergence of z.n æ; characterized by the rate R(n). This rate depends on the specific application and sampling scheme. Below, we review common sampling schemes and their associated convergence rates from the literature.
D.3.1 Random sampling
Empirical distributions and signals. Suppose p E [1, oo] and μ E (R)) for some > 2p. Suppose X E xx has rows sampled i.i.d. from μ., and let μx = 1 + 8x, the corresponding (empirical) distribution on Idd Then, we have [26]
1/2p
ifp > d/2. if = d/2,
E E,W,(H,H))1
n 1/2p log 1/p + n)
(3)
1/d 1/d
if < d/2.
Similarly, suppose f L ((0, 1]) is bounded signal sampled by x; = f(t)) where .,,..., by are i..d. uniform [0, 1]. and if fr be the step function corresponding to Noting that μ has moments of all orders and that uss, is the empirical measure obtained by sampling n iid points from μy, we conclude that Ed,(S,J,, fm) = EW, pt..)) converges at the rates (3) with d = 1, where d, is the symmetrized metric with respect the T.P norm on functions.
Point clouds. Again let p [1, oc] and μ E (TR* with q > 2p. and suppose E Raak has rows sampled i...d. from μ. Let G E O(k:) be random (or deterministic) rotation, sampled independently of X, and consider the rotated point cloud XG. Then the expected symmetrized metric between
axa and μ can be bounded by (3) since
(HEO(K) inf W,(n, (xGG-1) c
E
inf W Wy(n, (X [EE((R)
E
(4)
E[W (p, (x))]
Graphons. Let W: [0, 1 - [0, 1] and A, E Taxn be sampled as (An)i. ~ (er(W 2T)) where Z1...., Fn are i.i.d. Unif([0. 1)). Let WA,, be the step graphon associated to An.. Then, [54, $10.4] implies
(W W
Vlo((n)
'In fact, this bound holds with probability at least exp( 2log
25

---

where on is the cut distance of graphons: see [54, $8.2.2] for formal definition. Moreover, we have AA, W in cut metric almost surely [54, Cor. 11.15]. Similarly, if Tw: (20 1]) L ( 1])
is the integral operator associated with W, then by [37, Equation 4.4 and Lemma E.6].
B = E
inf orG
ITw - To-w, 1
s
x (logn) 11/
See Appendix G.I for the definitions of the symmetrized metric and norm on graphons as integral operators.
D.3.2 Deterministic sampling
Uniform grid. Suppose f: [0, + R is L-Lipschitz with respect to || llp. and consider its values on a uniform grid X, Xi.....de de = f((11 - 1) /n..... . (ix 1)/m)) E (RR") @* we extend X to step function usual by fx (Z1...., .......,,....................... kk) X [mnn] then
|| - fxllo S | fxl1
I L
sup =200
||(,),...,,,,)) .x) - ([[z]]] - 1)/n,....... "///,...[....... - 1)/n)ll
L/
for all q [1, oo). Also note that if we evaluate an L-Liscchitz graphon W: [0, 1/2 > [0, 1] on such a uniform grid, we have
LV2
[[w -T,,, lop S I|W W, <
Local averaging. For any f E [20 1] 1/n to produce values
locally average it over hypercubes of side length
fi//n
X X n
(1-11//1 f(z1...... xx)) dx ... drk.
(1/11)/n
and again extend these values to step function fx. this case,
Ilf fxllp s 2dist(f, Vn),
so, we get the optimal rate of convergence.
E
Generalization bounds: details and missing proofs from Section 4
We apply the framework connecting robustness and generalization established by [88], which is built on the idea that algorithmic robustness-that is, a model's stability to input perturbations-is fundamentally linked to its ability to generalize. We refer readers to [88] for the necessary background. This framework has also been recently employed derive generalization bounds for GNNs in [79], though their analysis is restricted to graphs with bounded size. Similar techniques are used in [47, 68].
dimediinal generalization bound from algorithmic robustness. We consider any- dimensional supervised learning task where consistent sequences model the input and output space
(V,,.,, V ((V,), (F...., (G,,) and U (UN.)., (G,)),
with associated symmetrized metrics dy and dy. The dataset s consists of input-output pairs (24, 31) E X x Y Voe U.c. where X x Y are subsets whose sequence of orbit closures compact the symmetrized metrics. More precisely, (z,, W:) are finite- dimen-iimeniionll representatives
of equivalence classes in Vac x Ux. The hypothesis class H consists of functions Vas + Un parametrized by neural networks. A learning algorithm A is mapping
A: (Voc UNO) H.
We write A, for the hypothesis learned from the dataset
26

---

Assume training is performed using neural network model that is L(r)) Lipsehitz transferable. (Recall from Proposition D.1 that this implies A, is Lloalll Lipschitz on ( for all with respect to the symmetrized metrics dy and dg-) Since X is compact, and hence bounded, there exists a constant C > such that A,: V + Us is c,-Lipschitz on X Y with respect to the symmetrized metries. Further, let the loss function L: Ux x U 7 R be bounded by M, and cy-Lipschitz with respect to the product metric d((z, y), w")) = do (2,xx' x') + dy (y, y²). By applying the framework of [88] to the limit space, we immediately obtain generalization bound for learning tasks where the data consists of inputs of varying dimensions. We note that this is not the result stated in Proposition 4.2 of the main paper; the version claimed there will be established later in Proposition E.3.
Proposition E.1 (Any-dimensional generalization bound). Assume that the training data consists of N i...d. samples (I,, 163 ~ from a measure f supported on X x Y S V. x Uso where X and Y have finite e-covering numbers Cx()), Cr(e) with respect to the symmetrized metrics for all 8 > Then, for any > O, with probubility at least 1 - ô, the generalization error satisfies
N
(A..)))) - E (A.()))))
N
(xx(1/4)Cx((//4) log + 2 log(1/6)
$ inf 730
ce(c M
(5)
N
2 (og()
s Celes 1IE + M (2log (N) +
(6)
N
where E(r) = Cx(r/4)Cy(r/44 and we set y y= ( in the second line to obtain the third.
Remark E.2. We make the following observations.
1. The bound (6) converges to 0 as N + oc. Indeed, & is strictly decreasing, and hence its inverse is well-defined and also strictly decreasing. Since E(x) -> 00 as x -> 0+,, we get (x) - as
2. The generalization bound reveals that the ability to generalize improves with greater model rranffrabilityysttabitty (i.e., smaller Lipschitz constants), and deteriorates with increasing geometric complexity of the data space (i.e., larger covering numbers).
3. We emphasize that fa is distribution Voc U... ensuring that every sample drawn from admits a finite- firite-dimensional representative, iee, (ci,y:) E Va x Un some n. This reflects the realistic selting in which data consists of fimtte-dimensional inputs. This stands in contrast to prior work on GNN generalization bounds [47, 68), which considers data distributions on "'o-the space of graphon signals [48], and the space of iterated degree measures in [68]. Such an assumption is somewhat unrealistic, as many elements in these spaces cannot be realized as finite- dintte--imessoonlll data.
4. Note that ju induces a distribution (ū(V, Un)NEE over sample dimensions in N, which inherently places less weight on larger sizes. Consequently, the generalization bound does not offer guarantees on the asymptotic performance of the model as the input dimension n oo. Next, we will derive the second generalization bound that addresses this problem.
Proof. For all (21, (22, XxY.
|e (A. - (A(()))))))) 12)1 S cr(c dv 12) (vI.
Sal(c. v
+ de (v1, v2))-
Applying [88, Theorem 14] yields that the algorithm is (Cx (CC Cy rer(c, (e,(, V1))-rooo) [88, Definition 2] for all 7 > 0. Further, applying [88, Theorem 3] gives the generalization bound (5). Finally, (6) follows by taking the as defined.
Size-generalization bound: train on finite sizes and test on the limit space. The previous general- ization bound follows the classical statistical learning setup, where both training and test data
27

---

assumed to be sampled i.idd. from the same distribution. However, in any dimensioaaa learning, we are typically concerned with a different scenario: training on data smaller sizes and testing on data of larger sizes. This motivates the need for new form of generalization bound that accounts for such settings.
We propose the following set-up (described in the main paper). Let be probability distribution supported on X Y C Vo x Us. which are subsets whose sequence of orbit closures compact in the symmetrized metrics. Consider a random sampling procedure
Sn Voo x U + Vn x Un:
such that for all and for all (a, y) E supp(u), have supp(S, (z, v)) X Y. This sampling induces a distribution pn, on Vn x Un via the sampling procedure; that is,
Pn = Law(Zns Un), where (Zn; Un) ~ (1, y) and (z, μ..
Proposition E.3 (Size-generalization bound). Suppose the training data consists of N i.i.d. samples (Iz, Vh) ~ pn- Then, for any > O, with probability at least 5, the generalization error satisfies
N ((A.(T)),,) - B(a,)) (A.(o)))))
N
+ 21og(1/0)
S colcc. (E) (1) + My
N
where W1 denotes the Wasserstein-1 distance, and E(r) = Cx(r/4) with Cx(s) and Cy denoting the e-covering numbers of X and Y, respectively, with respect to the symmetrized metrics. Moreover, assuming that the sampling procedure converges in expectation at a rate R(n), i.e.
(- [dv (z, (zxl) + dv. [M]]]] S R(n).
we have that
N
((A.(t:);
N
Scele, v 11) R(n)) + M (2 (2 + 2og((1/8)
(8)
N
Remark E.4. We make the following observations.
1. The bound (8) converges to 0 if both the training imput dimension n. and the amount of data N goes cc. Indeed, have justified in Remark E.2 that (6) converges to O as N - The only additional term in (8) is R(n) which converges to as n.
oc.
2. This new generalization bound aligns with the setup where training is performed on inputs of fixed size (also naturally extends to inputs of varying finite sizes), and testing evaluates the asymptotic performance as n. - DC. It can therefore be interpreted as a size generalization bound, accounts for distributional shifts induced by size variation. As consequence, additional term appears in the bound, reflecting the convergence rate of the sampling procedure.
Proof. By triangle inequality,
N
N ((A.(zz) v.) - ((A,
((A.(z)). v4) - ((c.)))p
S
N
N
==1
=1h E B(a (AAo(r). 4) - Be ((A.(x),))
=12
We bound the two terms separately. By the Kantonovich-Rubinste duality, we have almost surely that
Ta < celce (1(,
28

---

To bound Ti. recall that supp(S,,z,,)) v)) S X Y for all (z.y) E supp(n). It follows that supp(un) X Y. which therefore totally bounded. Its covering number is upper bounded by that of X x Y. Applying Proposition E.1 with j Mn yields (7).
Finally, to bound Wi (j,, pa), we note that the sampling procedure induces natural coupling between and Ax. Using this coupling,
W1 (H pa) - (a,,)) (a. S., [dy (zz [xm.]) + de (v. [w,))] x R(n), which yields (8); completing the proof.
Practicality of the assumptions. Finally, we reflect on the key assumptions required for the bound (8) to hold and assess their practicality in more specific settings. First, we assumed that the loss function is bounded (and, consequently, Lipschitz continuous). We note that these assumptions are relatively standard [1, 76, 3]. When the predictions and target outputs bounded, several widely- used loss functions, such as cross-entropy, L1-loss, L.2-loss, and Huber loss, are all bounded and Lipschitz continuous. Moreover, many clipped loss functions also satisfy this assumption. Second, regarding the assumption of a sampling procedure that converges in expectation at a rate R(n), we refer readers to Appendix D.3 for examples involving sets, graphs, and point clouds. Most importantly the bound critically depends on the compactness of X and Y in the symmetrized metrics, and on the sampling procedure generating finite-size samples that remain within this compact space. i.c.. supp(S, (z, y)) C X x Y for all (x,z) E sp) Below, we provide two concrete examples involving sets and graphs where these assumptions hold, and where bounds for the covering numbers are explicitly known. In these specific settings, our generalization bound applies directly.
Example E.5 (Probability measures supported on compact set). Consider Våd the duplication consistent sequence for sets endowed with the normalized la metric. See Appendix F.1 for the precise definitions. The limit space is Voo = -[, 1], R²), and the space of orbit closures of 4 is (R()), the space of probability measures on IR with finite p-th moment, endowed with the Wasserstein-p distance. Fix a compact set S R2,, and let
X x= E (P0, 1), R²): uu is supported on $2}.
Note that the sequence of orbit closures in X. namely {uy :f E x), is compact with respect to Wp. A bound on the covering number Cx is given by [63, Theorem 2.2.11]. Consider the sampling procedure Sn I.P [,, 1], Rd) -> Raxd defined by drawing 2;
iid. Unif([O, 1)), and setting Sn, [2zz) for == 1...., Then, for all f E X, each entry S,(J) lie in Ω. Hence, we have (p E X. Our generalization bound therefore applies to this setting.
Example E.6 (Graphon signals with cut distance). Consider VG dupp' the popllicatiin-coosssteee se- quence for graph signals endowed with the cut metrics. See Appendix G.I for the precise definitions. Define the space
X x= ( [0, 112 - [0. measurable: W (() = W(y, ((y,)))x(( E ((O,))) 11f1 Sr).
By [47, Theorem 3). the sequence of orbit closures in X is compact with respect to the cut metric on graphon signals. Moreover, a bound on the covering number is also provided in the same result.
Consider the sampling procedure Sn X + Rax= x ". defined as follows: draw 24 ~ Unif([0, 1]), and set SW,, = (A, X), where Aij ~ Ber(W Then, for all (W. E X. the sampled pair Sn (W. belongs to X. This is the standard sampling procedure for graphon signals, and once again our generalization bound applies.
itd.
and X, = fz.) for
1,.....7 n.
E.1 Transferable neural networks
To prove the transfcrability of neural network, we first observe that compatibility and transferability are preserved under composition. Therefore, it suffices to verify these properties for each individual layer. Moreover, by Propositions C.6 and D.2, it is enough to prove the compatibility and Lipschitz continuity of each fn on the finite space, rather than analyzing the limiting function foo directly. This idea is formalized in the following proposition, which serves as key tool in our transferability analysis of neural networks the later sections. Importantly, this provides a general and easy-to-apply proof strategy. In contrast, previous works often begin by characterizing natural limiting function Joo (e.g., a graphon neural network), and then directly prove its Lipschitz continuity in the limit space-a process that typically requires case-specific proof techniques.
29

---

Proposition E.7 (Transferable networks: detailed version of Proposition 5.1), Let (Vnl) Ins (Un"), In
be consistent sequences for i l....,, D. For each i, let (W V₁ U be linear maps and Vo vol+tl) be nonlinearities. Assume the following three properties hold.
(pn): Uh
(w()) (pr) are compatible.
1. The maps
Lw 3. The map Pa is L-(r)-iipschitz on { E U ||al|| < rr] for all n.
2. The linear maps uniformly bounded supn, [| llop
(W1"
pm o... pm wh!) is locally Lipschitz transferable,
(D-1)
Then the composition
tending to a function on Voo - Us that is Lipssh-Lipschizz on {or vol ||llll < r] where we
inductively define
D
6 (I(wr)) l+1 (L+)( LNN(F) = LW
II 4.
In particular, if Pm is LppLippchhtt, for all i, then the composition is Lipschitz transferable, extending to a fanction on Voc + Un that is Lax-Lipschitz where LNN = Lyy LD-1.
Remark E.8. By Proposition D.I, the composition is also LNN(r)- with respect to the symmetrized metrics on the same r-ball.
Proof. Note that if fi: (L) + v and f2 V - V are Li (r)- and Lo(rl-loclly Lipschitz,
33
respectively, then f2 fa is (r)))aaarrl Lipschitz. Our claim follows by an inductive application of this fact and Proposition D.2.
F Example 1 (sets): details and missing proofs from Section 5.1
In this section, we study the transferability of architectures taking sets inputs. Section F.1 introduces the consistent sequences we consider and Section F.2 presents results for three architectures: DeepSets[91], normalized DeepSets [9], and PointNet [66].
F.1 Consistent sequences on sets
We present two examples of consistent sequences on sets. See Figure in the main text for a graphical illustration.
Zero-padding consistent sequence V Wzero with Ep norm
The zero-padding consistent sequence V Vzero = (Vv).. (n.N.),, (G.)) is defined as follows: The index N (N, <) is the poset of natural numbers with the standard ordering. Let V,, _ for every n E N, and the zero-padding embedding is given by, for n < N,
1 + R (I1....,
PN,
xn. + (x
O....
(N 0's
The group of permutations S, on n letters acts on R by permuting coordinates: (g.x). == Zg-1()) for g E S,, The embedding of groups is given by, for n S N,
ONni Sn + SN
0
9
I I-
30

---

That is, view Sn as the subgroup of Sn which acts trivially on + I....,N. N. In this case, Voe can be identified with lg. i.e, the space of infinite scalar sequences with finitely many nonzero entries. The limit group Go is the group of permutations of N fixing all but finitely many indices.
We associate every infinite sequence (x:) Vo with the tuple of sequences (f =
The sequence (xT) ] comprises positive entries of (a:), ordered in descending order and extended with trailing zeros. The sequence (a, ) comprises the negative entries of (zz), ordered in ascending order and similarly extended with trailing zeros. Notice that different sequences in Voc are associated with the same tuple of sequences and only if they belong to the same orbit under the action of Go... Hence, the orbit space of Vo under the action of Go can be identified with tuples of ordered infinite sequences. Specifically, one sequence consists of non-negative entries arranged in descending order, and the other sequence consists of non-positive entries arranged in ascending order, with both sequences having finitely many non-zero entries.
The ep norm on V 2ero- We can endow each V,, with the fy-norms
(E 1/n
p E [1,
||>||
max |my|
if = 00.
is easy to check by Proposition C.8 that this induces a norm on Vx = Re, which coincides with the f--orms infinite sequences, which is also denoted
|| ||p- The limit space is then
6p {(x)))) E lx, < oo)
if p [1)
Co ((x))_ lim, |z,|| 0} if pf p=
Similarly, the space of orbit closures of V under the action of G can be identified with tuples of ordered infinite sequences. Specifically, one sequence consists of non-negative entries arranged in descending order, and the other sequence consists of non non-positive entries arranged in ascending order, with both sequences in Ep (for p [o)) or co (for p oo). This space is endowed with the yllr-
symmetrized metric dz y) min.eg... ||
The Ep norm on the direct sum yrd The direct sum Wold {(R"dd), (, (S,)) defined Definition C.4 extends the above to the case of set of vectors in Rd, endow with norm, we first fix arbitrary norm || || on Rd. Then the Ep -orm Rnxd is defined analogously with respect to || [|,a, i... for X E Raxdd
{
I 1/P
if E (L,
|
max |X
pf xc.
Analogously, in this case, V~o can be seen as the space of infinite sequences in Rd with finitely many nonzero entries, and the limit space Vo. is the corresponding l, space (if E [1, or co space (if oo). The space of orbit closures can be seen as tuples of infinite sequences in Rd, ordered in lexicographic order.
Duplication consistent sequence Vaup with normalized fp-norms
The duplication consistent sequence Vaup ((V.), (PN...) (G,)) is defined as follows. The index set (N. the set of natural numbers with divisibility partial order, where < N if and only N. Let Vn = R² for all n E N, and the duplication embeddings is given by
Ra R.V
PN
(II....,I,)
+ X N/nn
(I1...., . En:..., Zn))
N/n times
for n 3 N. The group embeddings given O
S, SN g g & IN/n:
for n J N. That is, g E S, acts on [N] by sending (i 1)N/n + to (g(1) 1)N/n + for i I,...,7 and 1,..., N/n.
31

---

In this case, Voo can be identified with step functions on [0, 1] whose discontinuity points are in Q: each x I" corresponds to fa: [0. 1] - R where f=(t) = 2 [tn]] for > 0 and f(0) 21. In other words, fo is the step function which takes value 2; on In., = (i-1 : i1 for i = 1,...,n. n. Indeed, all equivalent objects r and ,,,,, correspond to the same function in this way. Therefore, Vo can be seen as the union of step functions of this form for n E N. Under this identification, permutations S., permute the intervals It,n and act functions by g / g g 1 The limit group G is the union of such interval permutations. The orbit space of the G. on Voc can be identified with monotonically increasing step functions on [0, 1] whose discontinuity points are in Q Alternatively, the orbit space can be identified with the space of empirical measures on I: each IR" corresponds to the empirical measure Ptz = 1. and 4N,,2 are identified with the same measure; furthermore, this resulting measure is constant on orbits under the Go -cctoon.
22 Σi= 6s, Indeed, any equivalent objects
Under the identification of V.o with step functions, a step function f E V.o is identified with the probability measure μt,, defined as the distribution of fT) for T uniformly sampled from [0. 1]. Indeed, all elements in the orbit of f under the -ctiinn correspond to this same measure juy- Note that the generalized inverse CDF of [(T) is precisely the 'sorted' version of f (called its increasing rearrangement), relating the above two perspectives on the orbit space. The latter view of the orbit space as a sequence of measures generalizes readily to other consistent sequences obtained from Vdup. such as väd which we consider below, so we shall take this view from now.
Normalized Ep norm on Waup- We can endow each space Va with the normalized fp norms
( E.= |z:1)) (Z 3/p max ==1 [
if E [L,
|
if
00.
Using Proposition C.8, it is straightforward to verify that this defines a norm on Vo.. Under the identification of Voc with step functions, the induced norm on V.o coincides with the conventional I norm on measurable functions, given by
(6 150) dt at) sup [S()]
1/r
i E [1,
llfllp
if xc.
That is, for any x E R", we have ||>|| = 11f where fz is the corresponding step function. The limit space is then
[P0, 11) {f: [0, 1] + R measurable: fo (ft)) dt < c0] f is bounded and continuous on [0. 1] Q {s: 5: [0, + R with left and right limits every E [0, () }
if E (1),
p=
where the result for oo follows from [21, Chap. VII.6]. These are a subspace of so-called regulated functions, which have left and right limits at each [0, 1].
When p E oo), the space of orbit closures, equipped with the symmetric metric, can be identified with (R).. the space of probability measures on IR with finite p-th moment, endowed with the Wasserstein p-distance. In the case p = oo, the space of orbit closures corresponds to a subset of Poo (R). the space of probability measures on IR with bounded support, equipped with the Wasserstein co-distance. This is formalized and proved by the following propositions:
Proposition F.I. For any p E [1, oo) and all f.g E Vo.. the symmetrized metric ap(F.g) g) = infoeG. ||o f gllp equals the Wasserstein p-distance between the associated measures:
(p(f.g) Wp(ms,
Proof. We first prove they match on Vos. Consider vectors x E RR" y E R under the action of Sn. S,, respectively, and let N = (cm(n, m). Then, by standard results the Wasserstein distance of empirical measures [65, $2.2].
1/8 -Wy(HrrHy) if [L, min (+ EN | (x),(())()) - (N.. (v)) (N.m(v)il")
(x
min max (x),) - (2.. = W (Mr,
if p = co.
32

---

where Pe was defined above, and p is the Wasserstein p-distance. Hence under the identification with step functions, for any fig E Vo0 we have (f. Wp Mo).
Now consider the limit points. Let (fn), (9n) be two Cauchy sequences in Voc with fn - In - in Voe with respect to the L norm. Then
(p((f: - dp(f.9)) g)1 s (p. dp(en. 1lf - fuulp + l1gn 9l12 0.
Similarly, since for any -.9 E Voo.
W Wp( s (Bxxooonruun/()))331)1) (((())))-((())) 1/p
-Iff-ôll-
we also get
(Wp(un)) - Wplus, 0.
But for all n, dp(Sn, 9n) Wp Wp( (g,). so by the uniqueness of the limit, dp((.g) W,(us, Mg).
Proposition F.2. For p E 00), the space of orbit closures {uy : f E Voo coincides with (R)... For this set is subset of Poo (R).
Proof. For p E [1, oo), by definition, the space of orbit closures is the set of probability measures
{pz : f (P((,, 1]). We claim that this set is equal to (p(.). Observe that ((xx~uy | (x lpp-pp- On the one hand, this implies that if f E ([0, 1l), then J E (IR). Conversely, given any
(R), be the generalized inverse of the CDF of μ. then jf = μ and f E L" 1)). Hence
J E (IR) implies that = My for f E LP((O, 1]).
For p co, note that any E Voc is bounded, so the support of Jy is compact, implying that M E (R).
Norms dup Similarly, we fix an arbitrary norm with respect to Ilaa:
|| - ||Re Rd and define the norms Ra
C max
[x 1/P if (L,
|
(10)
X Ila.
if p oc.
For E oo), the space of orbit closures can be identified with Pp (IR.) endowed with the Wasser- stein p-distance with respect to || l|za. For p = oc, the space of orbit closures can be seen as a subset of Poo (IR)) with the Wasserstein-oo distance with respect || l/ This is because IRd is standard Borel space [77, Thm. 13], so the same arguments as in Propositions F.1-F2 apply.
F22 Invariant networks on sets
We consider three prominent permutation- -nnvariiiinnnnniannttt neural network architectures for set-structured data: DeepSets [91], normalized DeepSets [9], and PointNet [66]. These models are defined as follows:
[ DeepSet,, (X) =
E p(x.)):
1
TeepSet,(())
and
PointNet,, (X)
max p(X:))
where p: Rdd + 12th and a: g² + R are multilayer perceptrons (MLPs). In the case of PointNet, the maximum is taken entrywise over vectors in I!..
They follow the same paradigm (X) a (Ax where the three models use different permutation-invaree
aggregations Agg. We refer the reader to [9] for a comprehensive study of the expressive power of these models the any-dimensional setting. In particular, they show that normalized DeepSets (respectively, PointNet) can uniformly approximate all set functions that are uniformly continuous with respect the Wasserstein-1 distance (respectively, the Hausdorff distance). In contrast, our work focuses on transfcrability and size generalization, rather than expressive power.
33

---

F.2.1 Transferability analysis: proof of Corollary 5.2
We prove the Corollary by instantiating Proposition E.7. The invariant network is given by the following composition
Ruxd
p
BRXA
Agsi
R S R
Tow-wise
where we use Rd to denote the row-wise application of the same p IR + RR. Thus, it suffices to analyze each term this composition individually.
DeepSet. Notice that the sum aggregation is not compatible with the duplication embedding. Indeed, for any E R such that Σ; xz O. and for N, o N.
N
Σ
x @ 1N/n) (N/m)
I
24-
Therefore, DeepSet not compatible with respect to the duplication consistent sequence general. We now prove its compatibility and transferability with respect zero-padding.
Corollary F.3. Fix arbitrary norms || lIRa on I& and |1-1|R- on RR. Let Rd + R be Lo-Lipschiis with p(0) 0, and a Ihh + IR LopLichchit, with respect to the norms || || || l|R,, and 1. Then, the sequence of maps (DeepSet,,) is (Loba)-Lipschin transferable with respect to the zero-padding consistent sequence W trivial consistent sequence VR (with absolute value norm). Therefore, (DeepSet,)) extends to
zero (equipped with the E n-oor induced by || (laa) and the
00
DeepSet : { + R,
De =
Σ p(a.))
which is (L with respect to the ty-orrm on the infinite sequences.
Proof. We model each intermediate space with consistent sequences:
Bd
nxd
rüh = (Raxh) E VRa
=IR² S V. -RR).
zero
(row-wise)
ZeTO
We first check the compatibility each map.
As long as p(0) = 0, the p-map is compatible because p
ON - [x]] for all X E R=xd 0 R (N n S N,
and the row-wise application makes sure p is -quuqiiivaia
The sum aggregation Agg.. = Ex is compatible because adding zeros does not change the sum, and the summation operation is S,, -nviirriinnt.
The map is between two trivial consistent sequences. Hence it is automatically compatible.
Endow yod with the & norm induced by ||- and Vith with the & norm with induced by || I|g.. Vga, , VR are endowed with || ||æ. and respectively. Next, we check the Lipschitz transferability of each map.
The p-map is Lispichhiitz transferable map because for all n, we can prove p0n; Raxd - Raxh (applying the same row-wise) is Lp Lipschitz with respect to the l norms:
1l on (x) Sa (x(())
(I((X)) p(
Σ Lo - Y = - Y
The sum aggregation Agg. = Σn is 1-Lipschitz transferable because for all n,
Σ X
Σ
Y=
[X. YxllR= = =|I-- - Yl1..
1=1
R
1=1
We highlight that this does not necessarily hold for other lp norms for + 1.
34

---

The map a is Lo-Lisschitz transferable.
Thus, the result follows from Proposition 5.1; completing the proof.
Normalized DeepSet. The mean aggregation is not compatible with the zero-padding embedding.
Consider vector ( (n.) zero-padded to length N, we obtain
I such that Ei Iz + O, and suppose < N. When
T = (T), Tay O, 0) E ER.
Then
n
Therefore, normalized DeepSet not compatible with respect to the zero- sero-padding consistent sequence in general.
We now prove its compatibility and transferability with respect to the duplication consistent sequence with normalized lp norm.
Corollary F.4. Fix arbitrary norms I--lRa on Rd and || lRR on R.. Let petp:: P + IR be L, Lipsshhhi,,, and σ Rº + R. be La -ipschchii, with respect to the norms || I1,2,, || |RRE, and - Then, for all E [1, oo), the sequence of maps (DeepSet,,) is (L LLipschitz transferable with respect to the duplication consistent sequence Wad (equipped with the normalized lp norm induced by II l1aa)) and the trivial consistent sequence V/ (with absolute value norm). Therefore, (DeepSet,)) extends to
DeepSet (R) + R. DeepSetxx()) (0)= (f
which is ( with respect to the Wasserstein-p distance || lIR..
Proof. We model each intermediate space with consistent sequences:
(R E Vg =RR") 4 V2 (IR).
R
V
dup
(row-wise)
dup
We first consider the compatibility of each map.
The p-map is compatible because @BN (X & = 8 IN/n for all n N, and the
row-wise application makes sure p is Sn equivaaiint
The mean aggregation Agg,
E is compatible because for all
N, Rexd
1
X s 1y/nl:
(N/n)X,
Σ
n
X
72
and the mean operation is S,, S,.invariant.
The map is again automatically compatible.
Endow yydd with the normalized ép norm with respect to Ila,,, and with dup with the normalized &p norm with respect to || l|a.. The trivial consistent sequences Vgs, Va are endowed with || I| and
dup
|- respectively. Next, we check the Lipschitz transferability of each map in the composition.
The p-map is Lp Lppiiisciitz because for all n, we can prove pen Roxd + R h is Lp
Lipschitz with respect to the normalized l, norm:
1/p
(x) /O"(V)
(I()))) (l:
1/2
|p - Y1E..
35

---

The mean aggregation Agg;=1
1
Ei= is 1-Lipschitz transferable because
-
R X
X Ya - || Y11i 1|x Ylla,
n
where the last inequality follows from Hölder's inequality.
The map is L, Lipschict transferable.
The result follows from an application of Proposition 5.1; completing the proof.
Remark F.5, The same result was also proved in (9, Theorem 3.7] by directly verifying the Lipschitz property of ye for all 2 1,
DeepSet oa (px) DeepSet [uy)] S Lo / pdlux - vo))
S (Ixx,W(((x S p py))
where the second inequality follows from the Cantorovich-Ruuinssiie duality. Our methods provide an alternative proof, using a proof technique that applies more generally (Proposition 5.1).
Following this result, we can directly apply Propositions D.4 and D.5, along with the convergence rates described in Appendix D.3, which immediately yields the following transferability result.
Corollary F66 (Transferability of normalized DeepSet). We have the following transferability results for normalized DeepSet:
1. (Uniform grid sampling) Let (Xn) E Rexd be sequence of matrices sampled from the same signal f via the "uniform grid" sampling scheme, i.e., laking (Xa)i: = /( (==²) for all [n]. Suppose is Lipschitz. Then,
DeepSet, (Xn) DeepSet,, (Xm)) S Sn- +m
2. (Random signal sampling) Let (Xn) E Iaxd be sequence of matrices sampled from the same signal via the random signal sampling scheme, i.e taking (Xn)e: = (Ix)) for all
E (n), where 2 In are sampled i.idd. from Unif([o, 1)). Suppose 1,3 1], RRd).
Then,
DeepSet, (Xn) - DeepSetm (Xm))
n 1/2 + m -1/2
if = 1, if d 2, log 1/2 log(1 n) m- 1 m) if 2.
11 1/d + m ml/d
3. (Empirical distributions) Let (Xn) E Ruxd be sequence of matrices sampled from the same underlying distribution μ E Pa((R)) i.e., each Xn, has rows sampled i.i.d. from p. Then,
E DeepSet,, (X,) DeepSet, (Xm))
n 11/2 1/2 + m 1/2
if 1, if = 2,
x n 112 log(1 + n) + m 1/2 log(1 + m)
n 1/d + m 1/d
if 2.
The max aggregation is not compatible with zero-padding. Consider a vector & = (#1,..., Fn) Re where all entries 2; 0, and suppose < N. When zero-padded to length N,
PointNet.
we obtain
f (a ................................ Fns O. 0) E N.
Then, we have
max T S
0 max 15t5
Hence, unless we restrict the model to avoid all all-negative entries, PointNet is not compatible with the zero-padding consistent sequence. We now prove compatibility and transferability with respect to the duplication sequence with the foo norm.
36

---

Corollary F.7. Fix arbitrary norms II-l on R' and l1 on RR. Let p: P - IRhh be Lg Lo-Lisschizz and a IR + IR be LG Lipsschh,,,, with respect to the norms || -1.,,, || lloo on R", and Then, the sequence of maps (PointNet,,) (Lipha)-ippschitz transferable with respect to the duplication consistent sequence dup (equipped with the lo norm induced by || IIRa) and the trivial consistent sequence VR (with absolute value norm). Therefore, (PointNet,,) extends to
2o Poc R,
PointNett (1) =
sup
p(x)
*ESupp(N)
which is (LpLoa) with respect to the Wasserstein-co distance on || 11
Proof. We again consider consistent sequences
ved dup
(R (Raxd)
V
(IRw
max VRA = (R") Vx= (TR).
(row-wisc)
dup
For compatibility, it is left to check that Age max is compatible. Indeed, for any X e Raxd, n N, we have max & AN/ali: max;=1 X and the max operation is S, -nvvrrraaa Endow yod dup with the fo norm with respect to || lla,, and Vea with the foo norm with respect ||. so on R The trivial consistent sequences Vx*, Ve are endowed with || 1ls and | respectively. Next, we check Lipschitz transferability of each map.
We have proved in the proof for normalized DeepSet that p; are p, Ta Lipschitz transferable respectively.
For any E [d]. mmxx=1 Xig - max;= Yisl S max conclude
Xig Yijl. Take max over j E [d]
max
X max Yi: 1=1 =
= max j=l
max Xij max Vip
S max X - 1x:
c=
Hence, Agg"=1 max;=1 is I-Lipschitz transferable.
The result follows from Proposition 5.1; which completes the proof.
Remark F88 PointNet produces identical outputs for probubility measures with the same support. Thus, it can be viewed as a function
PointNetoo +K(RR)
Nei (X) - sup p(o)); #
where K((TR))) denotes the set of non-empty compact subsets of Rd. The Wo distance on Poo (Rd)
induces the quotient metric dy. on K((Id) via the equivalence relation μ ~ v if supp(u) = supp(v). Our results imply that PointNet.o is (Lpho)-Lipschitt with respect to dg.
A more commonly used metric on KCRR)) is the Hausdorff distance, defined by
dx(X,Y)= = max
sup inf ||: - ull. sup inf ||x - vll NEY ZEX
(11)
x BEY
19, Theorem 3.7] shows that PointNet is -Lipsshh-ipsshhtt with respect d It is easy to see that dи S dx, but we leave exploring further relations between these two metrics to future work.
Finally, we show that the sequence of maps (PointNet.,) is, in general, not transferable with respect to the duplication-based consistent sequence yiad when equipped with the normalized lp norm for any p E [1, oc). Consider the sequence of matrices (X(r) E Raxh), where the first row is the rows are zero vectors. Then,
all-one vector 1 and the remaining
(*) - Oll, - as n 00,
which implies that [X((1]] + [0] in Vo However.
max 1=1
x = 1n for all n.
This demonstrates that the max aggregation Aggi = max 1 is not continuously transferable under the normalized lp norm, and neither is the sequence (PointNet,,.
37

---

Related work. Several previous works [92, 64, 9] studied (variants of) normalized DeepSets in the dimenssoaa limit as operating in the space of probability measures, and investigated their approximation power and generalization behavior.
Moreover, while analysis primarily focused invariant neural networks on sets, it is also natural to design and analyze equivariant neural networks on sets with our theoretical framework. In particular, may consider such neural networks that are transferable with respect to duplication- consistent sequences, which parametrize measure-to-measun functions. For example, [19] proposed general framework for designing measure-to toaeresurr measure neural network architectures. Additionally, [86, 30, 74] analyzed transformers (without causal masking or positional encoding) as measure-to- measure functions in the limit space. We leave the analysis of the transferability of these models within our framework as future direction.
F.2.2 Explanation of transterability plots (Figure
Our numerical experiment in Figure 2 illustrates the second column of Table 2 for p 1: the Lipschitz transfcrability of normalized DeepSet, and non-transferability of DeepSet and PointNet, with respect to (V dup. l|.. First, applying Proposition D.5 normalized DeepSet, and recalling the convergence rate of empirical distributions given in (3) for d = 1,p = 1, we get the following corollary.
Corollary F,9 (Convergence and transferability of normalized DeepSet). Let (In IR") be itd. a sequence of imputs with entries (xn); ~ for = 1,....,h, n, where is a probability measure on R with finite expectation. Define the empirical measure Prx Si=1 on; for x RR". Then ElWi (H,,P,,) Px,)) S n 1/2, and hence
E DeepSet, (2r.) DeepSet (n]]] x 5n-1/2
DeepSot, (I.,) - DeepSet, (rm) S n 1/2 + m 1/2
Indeed, Figure 2(b) shows convergence the model outputs, and Figure 2(d) confirms that the convergence rate O(n 1/2), as predicted. Figure 2(a) illustrates the divergence of outputs from DeepSet. This occurs because the sum Σi= p(2;) unbounded, this leads to unbounded (blow-up) outputs as n increases. Figure 2(c) shows divergent outputs from PointNet. When the input distribution yu has compact support, the output of PointNet will converge, although without guarantees on the rate. However, in our experiment where μ = =V 1) has non-compact support. If in the PointNet is unbounded, the maximum value max;=1 ((x,) diverges almost surely as n + co. This again results in blow-up outputs.
(n)). If the function in DeepSet is
G Example 2 (graphs): details and missing proofs from Section 5.2
In this section, we study transferability for GNN architectures. Section G.1 introduces the consistent sequences we consider. Section G.2 studies existing architectures and Section G.3 introduces a new class of GNNs with better transferability properties.
G.1 Duplication consistent sequence for graphs
We present an examples of consistent sequences on graphs, illustrated graphically in Figure 3. Start with the duplication consistent sequence for sets Vaup defined in F. we define
dup = (Vau)) + yod
following the definition of direct sum and tensor product in Definition C.4, C.5. This gives the duplication consistent sequence for graphs. Specifically, v2 = ((V)), (Px,,), (Gn)) where V, = Raxa x Raxd for each and the embedding for n N is given by,
NN
T sym
x Ruxd < NNX Nxd
(A,X) - (A 2 (1 Ny)), 1
which can be interpreted as replacing each node in the graph with N/n duplicated copies. The symmetric group Sn acts on Vn by g XA (gAg .g)).
38

---

The space V. can be identified with the space with all step graphons (and signals) in similar way: Given (A, Rsym x R define WA A [0. 1] R. fx [0.
E2 such that ...,, n E [n], and fx takes WA takes value Ar, on the interval Inn x j.m C [0, 1]2 for i.j = I,...,
value X; the interval I,, [0. 1] for graphon from (A,X), Under this identification, permutations S, permute the n intervals I and act on (W, f) by σ (W (o W. f) (Wo-) if o o-) where W is defined by Wo (x,y) W (1) o The limit group G. is the union of such interval permutations.
......... We call (Wa. fx) the induced step
The p-norm on ve dup' Fix || ll norm on Rd We equip V,, with p-norm given by
[AA, = max ||A]] pp. ||
1/8 ) max ( Enjejn Assl)
p E [1) (12)
max jj(a AAgl max"=1 (1
00.
It is easy check by Proposition C.8 that this extends to norm on Voc Under the identification with step graphons, this norm on Vxc coincides with the standard [--norm given by
[(W, max (IIW pl
max (CS (2x 1)l de dy) 1/ ( [((())
pe [1,00)
max (supa.y (x, v) sup, (x)))
p=
That is, for any X) E Bay x Rnxd (A, X) 1/ = ([ fx) ll.. The symmetrized metric is d,( (W', ff) inf (max (|) W - a W' pelpp:1. II a a. fllp))
(13)
OEGx
Operator p-norm on yG given by
Fix || IR a norm on Fd and [o] We equip Vn with a norm
dup
(1 ||X]|p)
(I,, X) xoppppp max
(14)
where ||Allop.p is the operator norm of A with respect to the lp norm, ie.
Alloop.p max ,-
||Axlppp
and || 17 is the normalized f,-norms with respect to || || defined in (10). It is easy to check by Proposition C.8 that this extends norm on Voc.
Let Tw be the shift operator of graphon W defined by Tw((f(u = So W(u, v) Under the identification with step graphons, the norm on Vo coincides with
(IW, f)llol == max (I]Tw I[fll))
where |TT llo.. suP ||Tw (f) pl.p and the on |I llp is the L norm as before. That is,
for any (A, X)) Ra x x (I, X) = [[[ fx) lop.p. For E [1, oo), the completion with respect to this metric is
V = (W E [P 112) W(x, () = W(y x {f E LP 1], R))
the space of L L--graphon signals. We do not characterize Vo for p since requires additional technicalities. However, it contains all bounded and continuous graphon signals. The symmetrized metric
d, f), (W'. f))
inf (max ([] T To llop.p |I a. 1()
(15)
a
Cut norm on Vc dup
We can also equip V, with the cut norm (on matrices and vectors),
1 max
[A,,, X) == max (I
X
max
Σ
Aij
max 7. SE(n)
Σ X
ne
S.TC(M)
iES.JET
iES
Rd
(16)
39

---

It is easy to check by Proposition C.8 that this extends to a norm on Voc. Under the identification with step graphons, this norm on Voe coincides with the cut norm on graphons and graphon signals
IIWW max [[W
/ (xx, ydddy 0.1 SXT
1/ f(x)dx Sc[o.1]
max
sup
sup
Rd
where the supremum is taken over all measurable sets S,T. The cut norm on graphon is studied in-depth in [54]. Though hard to compute, it has strong combinatorial interpretations. Hence, has played an important role in the work of GNN transferability, and has been extended to the graphon signals in [47], which we have adopted here.
The symmetrized metric is
f), ff))
inf {max (IIW- Wo f'llo)).
oEGx
It can be proved that this exactly coincides with the cut distance below, defined on graphon signals (extending the original definition of graphon cut distance from [54], similarly the version [47]):
a((w, f). (W',f") = inf {max (I]W a W W'l.,, llf a f'lnn)}. 8E
(17)
where S(o.1) the group of measure-preservine bijections o [0, 1] - [0, 1] with measurable inverse. The proof follows analogously to [8, Lemma 3.5]. Specifically, we first verify that the definitions agree on step graphons. Then, since both definitions are continuous with respect to the cut norm ||- Iol they must also agree the limit points.
While the norm is hard to work with directly, is topologically equivalent to the operator 2-norms considered previously on bounded domain. This means that any function continuous with respect to one of these norms is also continuous with respect to the other.
Proposition G.1. If [[ < and ll < r, then
IIl s II(W. f)opp. 2 S II(W, f)lb?
Consequently, for (1), || ||I and || I| are topologically equivalent on the space {W : [0, [-r,ri measurable, ((x, v) W(y,z)) (f [0, I-r,r] measurable).
Proof. Without loss of generality, let r = 1. Consider the norm
sup 1/" [( W(u, (w)gg(d)dddd
[T llo.oo.o..
By [37, Equation 4.4], || & |owlooo.oo. S <|| Io. By [37, Lemma E.6), if || S 1,
[Twllop.oo. S |[w lop.2 S Tw /
Combining the inequalities,
|W]L < [Wwloop2 I |
Moreover, by [47, Appendix A.2]. Iffla S ||5l] s 21lffloo I| S 1, then 11l < [lf]h s l| Combining the inequalities,
M/ < |1/122 < 2 ///
Therefore, conclude that
IIWW S
claimed.
40

---

G.2 Message Passing Neural Networks (MPNNs)
Background. MPNN parametrizes sequence of functions (MPNN,, sym Raxd. - Ruxdz)
by composition of message passing layers. The I-th message passing layer
MP
x Ruxd: Raxa x Buxdet,
(A, + (A,
sym
is given by
(4+1) = 2000 (x1²) Ex, w0 (x x Ang) An)): i= ,,...,, x
(18)
where Agg is permutation-innarian aggregation function such sum, mean, max; N₁ {j As * 0} denotes the neighborhood of node i in the input graph; the message function (h(): R4 x IR IR + RR and the update function ((); R& x Rh - IRd++1 are independent of the graph size n. Composing I. message-passing layers defines an MPNN, mapping (A, ( + X
Observe that MPNN is permataaioon-equiiariatt MPNN, (g .gX) gMPNN, (A, X) for all E Sn. If we want permuration-invariant function, this is followed by read-out operation taking the form of DeepSet. In this work, we focus on the equivariant case.
MPNN is a general framework for GNNs based on local message passing: [31] formulates multiple GNNs as MPNNs with specific choices of o, v. Agg; other ofte--ofthhearr GNNs can be simulated by MPNN on a transformed graph [38]. Moreover, Φ and tb can also be parameterized with MLPs to provide good flexibility.
Transferability analysis of MPNNs. The following corollary gives sufficient conditions on the layers of MPNNs to obtain Lipschitz transferability.
Corollary G.2. Consider one message passing layer, (MP!!),, as defined in (18), with the following properties.
1. The message function s(O) takes the form (21, w) = wE(22), where & R2: - R2:, is Lę Lipschitz with respect to 11a4h11 -Il...
2. The aggregation used is the normalized sum aggregation AggjeN; == EJEN.
3. The update function (00) is Lo Lipschitz, i.e. for all (z, v), (x', ,g') 12di x Rh!,
1100 (x' Illli S Lo max (l - x' 221l lly - 3/ l1
Endow the space of cuplication-consister sequences with the operator p-norm as defined in (14), where p E (0). Then, the sequence of maps (MP!)) locally Lipschitz transferable.
Remark G.3. That is, (MPNN,), which is composition of message-passingg layers, is locally Lipschitz transferable. Consequently extends to a function MPNN on the space of graphon signals, which is -iipshitsti p-metric defined in (15)). By Proposition G.I, the sequence of maps (MPNN,) is continuously transferable with respect to the cut norm (16) on B0,,r) r). The GNN studied in [70] a special case of our MPNN considered here; meanwhile, ours is a special case of [47], which directly establishes Lipschitzess with respect the cul distance by analysis on the graphon space. While our results are not new, our proof models.
((0,r) r) for all > O with respect to the symmetrized operator
Proposition 5.1 is new and generally applicable to various
Proof. We decompose MP(!) as composition of the following maps, modelling each of the interme- diate spaces using the duplication consistent sequences endowed with compatible norms. For the metric on the product spaces, we always use the - product metric, i.c., taking the maximum over
41

---

the individual components. Consider the following three functions
R R sym
x Raxd:
Raym
x R Raxd
x R2xx
{((1=))
given by (A +
X,
[(Xm)))
f(2): Bam x Raxdi Ruxhi Baya R
Ruxhi
given by Yo) H (A, AYo).
(() R x Raxd nunh mym Ruxd
given by (A, X),
where X; (x, Y.). is straightforward to check that each of them is compatible with respect to the duplication embedding. We now check the Lipschitz transferability.
The sequence (5!h)) is Lipschitz transferable because
f1 (A, - ( (A',
(LV - (A', (A'' -4x
The sequence (f( is locally Lipschitz transferable because we can bound its Jacobian. In particular, the Jacobian acts on (H,, Hx, Hyy) via
(4,, HA Hx, Hy] = HA Hx 1 (AHy + Hay).
Hence, on ((A.X, II,A,, <r}.
D.. (A, Yo) Hx, Hy op.
- H4 pp.p. ||xl|T, n $ (1 V 2r)) Hx, Hy llo.pp
1 -
1 - A |YI1 || Hy 11
max
i..., f! (1 2r) Lipschitz on this space.
The sequence (f! is Lipschitz transferable because
(A, Y) (A', "'',',,''ll = max (1 A'llopr 11 111A-Allopp. -x'11
(
where
| - -
1 (Xi. Y.) (X), Y;)
iml
1
(1)x: Xblla4 + Vr: Yillen) )"
12200
(IIX, X. + I| Y:
n
(by Jensen's inequality (ctt)² < =="""" for all a, b)
2 |(X,)) - (X',''I,
So ((3) is (1 v Lippssii..
Finally, apply Proposition 5.1, (MP()) is locally Lipschitz transferable; completing the proof.
42

---

Following this result, we can directly apply Propositions D.4 and D.5, along with the convergence rates described in Appendix D.3, which immediately yields the following transferability result.
Corollary G.4 (Transferability of MPNN). For MPNNs satisfying the assumptions in Corollary G.2, we have the following transferabiliity results.
(Uniform grid sampling) Let (An, X,.) E Rymm Ruadd be sequence of graph signals sampled from the same graphon signal (W, f) the "uniform grid" sampling scheme, i.e., taking (An)is W ( [[=1 )=1) (Xn)s: = I (==1) for all i. E [n]. Suppose W [0,1] + [0, and f [0, + Rd are both Lipschitz. Then,
[[MPNN X.)) - [MPNN (Am, Xl) S 5n +m
2. (Graphon sampling) Let (An,Xn) Xn) E Psyym x 1axd be a sequence of graph signals sampled from the same graphon signal (W, f) via the "graphon" sampling scheme, i.e. taking (An)ss ~ Ber(W (24, 22), (Xn)x: = (xx) for all i, [n], where 21...., In are sampled ii.dd from (ni 1)). Suppose W [0, 1|2 [0, 1] is symmetric and measurable, and f L ([0, 1], R Then,
E
da (IMPNN, (An, Xn)1, IMPNN..AAM (Am;
x (log ()og)) -1/4
+ (log -1/4
The first part of the previous corollary recovers the transferability results in [70], yielding an improved convergence rate of Onn and thus strengthening the previously established bounds of O(n-1/2) The second part of the corollary resembles the setting considered in [41], although the random sampling scheme used there operates at different sparsity level, with A.y ~ Ber(a, W(I;, 2z)) and log
On
As result, our result is not directly comparable.
G.3 Constructing new transferable GNNs: GGNN and continuous GGNN
Background: Invariant Graph Networks (IGN). Invariant Graph Networks (IGN) [56] are a class of GNN architectures that alternate between linear S, -qquivarri layers and nonlinearities. They follow design paradigm that differs fundamentally from MPNNs. Specifically, a D-layer 2-IGN parameterizes Sn-equuivriaan function (R"" (R²))22 (RR))02 composition
(((D) o Pn (D-1) .... o w()
where for each we have the following.
The linear maps w! : ((R"))2)ed = Rn2xd + ((R*))2)ed: & R²² x arer S,- equivariant. Here, d; denotes the number of feature channels. [56] provides parameterization of w as a linear combination of basis maps: In the special case where d: d = 1, the linear layer ( be written linear combination of 17 basis functions (two of them biases), where the coefficients a, 3 are the learnable parameters:
( (A) A A + ogdiag(diag) (()) + A + as T A + agdiag(A1)
+ + 1 + 11 T A + agdiag( (A 11) + a1 T A1)11T
+ +on (1 A1 A1)diag(1) + 012(1 diag" (1) + +01s(1 (liag(())ddaag)
+ *14diaa" (A)1 + ons 11 (A) + 11 3.ddaag()..
(19)
For general di d,41, the number of basis terms becomes 17d,d++1-
The activations p (1R7)&200d) nonlinearity (c.g.. ReLU) eise.
pnnxxd+s - ((R") (2) ==n" xdets apply
To improve expressivity, [56] proposed extending the architecture to use higher-order tensors in the intermediate layers. When the maximum tensor order is k, the architecture is referred to as a k-IGN. While this is theoretically tractable, due to the high memory cost and implementation challenges
43

---

associated with higher-order tensors, in practice. only k-IGNs for l: < 2 have been implemented to the best of our knowledge. In this work, we focus exclusively on 2-IGNs.
The basis in (19) is inherently dimension-agnoster allowing IGN to serve as an any-dimensional neural network that parameterizes functions inputs of arbitrary size n using fixed set of parameters. This feature fundamentally relies on representation stability, which is discussed in greater detail in [50].
Incompatibility of IGN. 2-IGN is incompatible with the subspace duup' First, its basis functions are not properly normalized. and therefore cannot be extended to functions on graphons. For instance, the fourth basis function (A) A11 yields output entries of order (n), and should thus be normalized by factor of n n-1 To address this issue, [11] introduces normalized version of 2-IGN, defined by
1
1
( = an + A2 + ogdiag(diag' (A)) + A11 + 11 A + 06 diag( A1)
1
+ a7
11
+ ag 11 T A + ag diag (AT 1) - a10
(1 A1)11
n
n²a
1
+ 01 n²
(1 diadiag(1) 012 diag (A)) + 01s (1 diag" [atag"(AA di))
+ a14diag" (A)1" T + a1s (A) + 31 11 + 32diag(1).
(20)
However, the normalized 2-IGN is still not compatible. Consider the third basis function (A) = diag(diag" (A)). It fails to satisfy the compatibility condition:
la(A & m) + (a(A) @ m,, 2 2,
the left-hand side yields diagonal matrix, while the right-hand side generally does not, In fact, all basis maps that output diagonal matrices share this incompatibility.
Nonetheless, our Proposition 5.1 immediately provides a constructive recipe for making 2-IGN transferable: we start from basis for linear equivariant layers wx( whith which compatible under duplication-ant and then select only the basis elements which have finite operator norm grows. Furthermore, we use nonlinearities p!. which are compatible and Lipschitz continuous. Following this recipe, we introduce two modified versions of 2-IGN:
Generalizable Graph Neural Network (GGNN): Compatible with respect Lipschitz transferable under the co-norm.
VG Vdup= locally
Continuous GGNN: Compatible with respect to VG dup locally Lipschitz transferable under the operator 2-norm, and continuously transferable under the cut-norm.
We highlight that this a general methodology for constructing transferable equivariant networks: the framework established in [50] yields bases for compatible equivariant linear layers. We can then select only those basis elements whose operator norms do not grow with dimension, which we have shown yields transferable neural network.
GGNN architecture. D-layer GGNN parameterizes an -,,equivaria function
IR sym
x RR ->
Rays x Inndd defined via the composition
(((P) P
(D-1)
((0 o ((1))
where for the following conditions hold for
The linear map w (Raxn @de @ (R")add + (R @ ((R))0d))s is a is Sn equivariant and compatible with the duplication embedding.
The functions (8) (Raxn))dd @ ((R")dd) with respect with the duplication embedding.
(Rexa) edd (R")od; that are compatible
Here, d and d' are feature channels of A and X, respectively-wer we fix = dp 1.
44

---

For the ease of notation, we assume d, = d,+1 (i) maps W Pn are given by
(The general case follows analogously). The
1 (A, x) (A', (x))
AT
11 T + Tr(A) 11 + +04 24--(111 111A)
a 02 n
d
+ as((diag(A) 1diag (A) )
Σ
( + + + an, ans (1 x1,))
==1
+ +11111,
1 1 + A100 + diagg()) +
Tr(A)
A
10
10 +
1 10 + 13
n
n
n n²
(0 (A, = A,
4=00
(21)
where ,, are learnable parameters, and a: R + R is an arbitrary L-Lipschitz entrywise nonlin- earity.
Consider the input and output spaces as (variants of) Vaup the duplication consistent sequences for graph signals. The linear layer W,, in (21) parameterizes all linear -quuiiirri maps between these two spaces that are also compatible with the duplication embedding.
The GGNN model modification of the 2-IGN (19) with three key differences. Firstly, we treat the adjacency matrix and node features separately so that each layer has graph and signal component. Moreover, we explicitly require the matrix component to be symmetric. Secondly, we impose the compatibility with respect to the duplication embedding on the linear layers. This leads to both proper normalization of each basis function and reduction in the total number of basis functions. In particular, all basis functions that output a diagonal matrix are removed. Thirdly, for the nonlinearity Pu. instead of the entrywise nonlincarity used in IGN, we adopt a message-passing like nonlinearity. The form of the nonlinearity mirrors the GNN model studied in [70]. Particularly, in (21), if set all the a's except a = 1, and all the 0's to 0 except 1,,,, then we exactly recover the transferable GNN in [70]. Therefoe,, our model is at least as expressive the GNN in [70].
Transferability analysis of GGNN, Even though we only impose compatibility by design, we still prove that GGNN is Lipschitz transferable with respect some norm. Albeit this norm is arguably too weak.
Corollary G.5. Consider one layer of GGNN. (GGNN, (A, = (6) w:(")), as defined in (21), where the entrywise nonlinearity a is Lo Lipschitz Endow the space of duplication-come consistent sequences with the oc-oorm as defined in (12) (with respect to -1 on Rdd Then, the sequence of maps (GGNN,) is locally Lipschitz transferable. Consequently, (GGNN,) extends to function GGNN on the space of graphon signals, which L(r)- on B(0,r) with respect to the symmetrized metric defined in (13) with p
Proof. The sequence of linear maps (W:(") in (21) is Lipschitz transferable because
|| llop I max |ail |az|
loal 2/a4 2/0s Σ
(10sss |07,5)) 1)
10 + 1102,- + |101,s oo + 1102,01lo + 110 + 110 100, )
where ||0llop.1 max, Ex 10k is the max 4 norm of column.
45

---

For the nonlinearity (ph)), we consider its Fréchet derivative (since all norms are equívalent in fiite-dimeenionall vector spaces, this is independent of the norm chosen):
Xo. XH) Hsl
H, Σ
Σ A X, A211)
Hence,
(A, ...,, (..,,.... Xs) Ho. ................................ Hls]loo
All A I|ol + ||A l ))
max
| 00.
s
max
|
8r H 0o + r 12
s=0
1 1
ssr + +ra)
[I(H, Ho........ Hsx.
s=0
=:(r))
Therefore, for all n, pn is Lg (rr) on the set
(0, r) {(A, ( ||A, Xo...., Nolllo <r).
Applying Proposition 5.1, the sequence of maps (GGNN,,) is locally Lipschitz transferable, where the extension GGNN is ([ol([]Wlll)] HtllWa/llp---pshhhhii L-iischhitz on the set
((0,r) ((W.))
<r).
Continuous GGNN architecture. We aim to further restrict GGNN to construct model that is transferable with respect to the cut norm. By Proposition G.I, we consider endowing the consistent sequence with the operator 2-norm, which is easier to analyze. The Continuous GGNN is variant of GGNN with an additional constraint on the linear layers W(('), requiring them to have bounded operator norm: WWop < oo (with respect to the operator 2-norm). This constraint effectively leads to further reduction in the set of basis functions:
AT
( (A, = (A', (X)) = [1 a2
11
+
04 (A11 + A1)
n²
06 (X.,) 1 + 1x.T) + at,j (1 (X.xx))1T (22)
+
/=1
1 11 1 A100 1T n 10
X
71
Therefore, the hypothesis class of continuous GGNN forms strict subset of that of GGNN, with the additional constraint enabling improved transferability. Meanwhile, for the same reasons outlined for GGNN, the continuous GGNN is also at least as expressive as the GNN proposed in [70]. We use (cGGNN,,) denote the sequence of functions of continuous GGNN.
Transferability analysis of Continuous GGNN.
Corollary G.6. Consider one layer of the continuous GGNN, (cGGNN, (A, pm W!!") as
defined (22), where the entrywise nonlinearity Lipsschtt Endow the space of duplication- consistent sequences with the operator 2-norm as defined (14) (with respect - on Rdf Then, the sequence of mups (cGGNN,,) is locally Lipschitz transferable. Therefore, (cGGNN,) extends to a function cGGNN>. on the space of graphon signals, which is -(r)-Lipschitz on B(0,r) with respect to the symmetrized operator 2-metric defined in (15) with p 2.
46

---

Remark G.7. By Proposition G.I, the sequence of maps (cGGNN,) is continuously transferable with respect to the cut distance (17) on the space
{(W, f) II Olop.. < TI, llf <r).
Moreover, for the convergence and transferability results stated in Proposition D.4,D.5, one can additionally obtain quantitative rates of convergence with respect to the cut distance.
Proof. First, by construction, the sequence of maps (W) is Lipschitz transferable because
llop 5 max |ani + laz2l + 2 +
(00o) + la7,5)),
10o, + 2|02,a/lop.1 + 100 + 1104,ollo0 } <00.
For the nonlinearity (ph)) ( ) the action its Jacobian yields
(A, (4) Ho... Hsl = H, _
Σ H A
==0
Hence,
DD 19 (A, Xo...., [H, Hslloop.2
5
||
oopp2 || +
||Allp.2
S max
n 111111lopp2
||Hall2
n=-1
n
22
S
lop.2
< max
| H
n
2p..
8p
+
r²1
Hallz
==0
1 1v
(sr* + r²))
(1, Ho. Ho.... Hs)
=:((r)
Therefore, for all Pm (6) is T. (r)) the set
{(A,
Xs): ||A, Xo.... X. llop.22 < r).
Applying Proposition 5.1, the sequence of maps (fn) is locally Lipschitz transferable, where the extension cGGNN is (L, x[]Wnllop=)]]| ) -Lipschitz on the set
B(0,r) ((W f): f)lopp < r).
We can directly apply Propositions D.4 and D.5, together with the convergence rates established in Appendix D.3. This leads to transferability results for continuous GGNNs that are exactly the same as those for MPNNs, stated in Corollary G.4.
Related work on IGN transferability. We discuss two closely related works, [11] and [35], that address the transferability of IGNs. Interpreting their results within our theoretical framework offers better understanding of IGN transferability. As shown in our work, the normalized 2-IGN is not compatible with the ampliccationconsiistte and transferability in Proposition 3.2. At first glance, this observation may seem to contradict [11, Theorem 2]. However, this is not the case. While [1]] introduces cIGN, a "graphon analogue of IGN," and proves its continuity in the graphon space, it is crucial to note that the discrete IGN does not extend to cIGN in general:
subspace VG dup: and thus fails to satisfy the convergence
I. & cIGN([AM), [X..).
47

---

Therefore, the convergence of cIGN established in Theorem 2 of [11] does not imply the convergence or transferability of the umite-dimensione IGN model. Moreover, [11, Definition 6] introduces a constraint that resembles our compatibility condition, formulated through a restricted variant termed "IGN-smalll" Our definition of compatibility clarifies this notion and enables explicit constructions and practical implementations of compatible, transferable versions of IGNs.
In more recent work, [35] adopts an approach similar ours by imposing additional constraints on the linear layers of IGN, specifically requiring them to have bounded operator norm. This leads to the Invariant Graphon Network (IWN) model. Unlike our construction, IWN retains standard point- wise nonlinearities. As shown in [35, Proposition 5.5]. it is precisely these point-wise nonlinearity layers that cause IWN to be discontinuous with respect to the cut norm, rendering it generally won-transferable in our setting. Interestingly, [35, Appendix G.4] observes that under suitable assumptions, IWN restricted to the space of simple-graph inputs (i.e., adjacency matrices with 0/1 entries) is Lipschitz continuous with respect to the cut norm and hence admit Lipschitz extensions. This implies convergence and transferability of IWN specifically under the "graphon sampling" scheme, where edges are Bernoulliraandmmizz not align with the behavior on weighted graphs (i.e., adjacency matrices with non-binary entries). This discrepancy highlights the cost of lacking cut-norm continuity over the full space. This phenomenon may also explain Figure 4(c) in our GGNN experiments, where outputs on graphs sampled from the Erdōs-Réén Rényi model appear converge (with diminishing error bars), yet to a different limit than those on the corresponding fully connected weighted graphs derived from the same graphon.
However, the limit of this convergence result does
In the case of 2-IGN, our continuous eGGNN model provides remedy for the lack of cut-norm continuity by replacing point-wise nonlinearities with pessage-passing-aee ensuring Lipschitz continuity with respect to the cut norm and circumventing the issue. However, our construction is currently limited to 2-IGN and does not generalize to higher-order k-IGNs. As noted in [35, Section 5.1], cut-norm discontinuity is inherent to the k- WL hierarchy and is likely unavoidable for all higher-order GNNs with better expressivity.
operators, thereby
Remarks on expressive power The expressive power of GNNs has been widely studied in terms of their ability to distinguish non-isomorphic graphs, where a GNN is said to be k-WL expressive it is as powerful as k- testing [36]. While this work does not explore expressivity, we note that the standard k- expressivity is not appropriate for studying the expressive power of graphon- compatible GNNs (i.e., GNNs that are compatible with the applicatiio-consiittr sequence and thus extend graphon space). This is because different-sizee graphon are always distinguishable by WL, but are considered equivalent by any graphon-compatibl GNN. Instead, it is necessary to consider a variant of k-WL specifically designed for graphons [7, 35].
graphs corresponding to the same step
H Example 3 (point clouds): details and missing proofs from Section 5.3
In this appendix, we study the transferability of two any-dimensional architectures for point clouds. We start by presenting the consistent sequences we consider. Then, in Section H.2 study the DS-CI model proposed in [5), which is known to be very expressive but computationally expensive. Finally, in Section H.3, we introduce a novel architecture that turns out to be much cheaper to compute.
H.1 Duplication consistent sequence for point clouds
The duplication consistent sequence for point clouds VP dup ((V,), (PPN,)); (Gn)) } is defined as follows. The index set is again N- = (N, -). For each n, the vector spaces are V,, = B=* with the group G, = Sn O(k) acting on V,, by
(g. h) X = T
For any n N, the embedding is given by.
PN Rank R Nxx
X X 2 1
and the group embedding is
8 8 Sn x O(k) SN 0(k)
hg h) + (g 2 IN/n: h).
48

---

Analogous to the case of sets, we can identify each matrix X R with a step function fx [0, R², thereby interpreting V. as the space step functions with discontinuities rational points Q We also view the orbit of X as empirical probability measure 2 >E= éx,, Equivalently, this identifies the orbit of step function f Vo with μ Taw(J(T)) where T Unif(o, 1].
The orthogonal group ((k) acts on probability measures via push-forward: for g E O(k) and measure μ., the action is given by g = -==* μ., where 9* ((B) = u(g-((B) for all measurable sets C IR* The orbit space of Sc can identified with the orbit space of empirical probability measures on IR* under the action of (A:)..
Norm on VP dup' Consider Euclidean norm || ll2 on I which corresponds to the inner product preserved by elements of (Ak). We equip each Vn with the normalized lp norm:
E= (x:1)) 1/r
pe 10) p=
X
max X
By Proposition C.8, it is straightforward to verify that this extends naturally Vos, and that the limit space in this case can be identified with Vo [[O, R²) of functions f: [0, 1] I2 with
norm |l (J' ( dt)
1/v
20.
Analogous to the of sets, the corresponding space of orbit closures be identified with the space of orbit closures of probability measures on R2* (with finite p-th moments) under the ((k))-ctions The symmetrized metric is given by:
dp(sgg)
inf Wplg P.. for f.g E V sEO(k)
(23)
where W is the Wasserstein p-distance with respect to the f2-norm on R*
H.2 DeepSet for Conjugation Invariance (DS-CT)
The DS-CI model [5] is given by
DS-CI, Rank - R
DeepSett (VV)(VVT) )
V + MLP
DeepSet(2) (2) (I10(VVT) y 1 (
MLP (3) (P(VVT))).
where for symmetric matrix X Bay the invariant features are given by (x) the j-th largest of the numbers X11...., Xnns by (X) the E-th largest of the numbers X 1 < j S and by (X) = Σij X.X.y.
We define normalized DS-CI with appropriate normalization: replacing DeepSet (eepSet(2)) with their normalized version (i.e. replacing the aggregation with the mean aggregation), and replacing f* (X) with (x) mn-TJ Eijj Xxx We denote the sequence of functions of normalized DS CI by (DS-CI,).
Transferability analysis of normalized DS-CI. Normalized DS-CI is not compatible with respect to VPp To see this, observe that under duplication, we have
(V LN/²)) = (VVT) & (LN/n4
Therefore, diagonal elements of V become off-diagonal elements in (VV 3 so
DeepSet (2) (1 ((V @ (v & 1n)n) " 1/2 + DeepSet (V nnn 1)/-))
F ((V & (V & 1NYN) FF(VV)).
49

---

However, we can make some additional adjustments to ensure compatibility: we define the compatible DS-CI by modifying the inputs of DeepSet(2) to be
)= where f (X) denotes the 1-th largest value among the entries X,, for S i.j S n. Additionally, we replace (X) with
((X)= = n XuXiy
We denote the sequence of functions of compatible DS-CI by (C-DS-CI,). We prove that this model locally Lipschitz transferable.
Corollary H.1. Endow Ve dup with the normalized Ep norm with E [1, Assume that all activation functions in the MLPs used for DS-CI are Lipschitz. Then the sequence of maps (C-DS-CI,) is Lipschitz transferable on the space {f |l < r) for all r >>0 O.
Proof. By Proposition 5.1, is sufficient to verify the compatibility and Lipschitz continuity each individual layer.
The sequence of maps
(IR <R || (1pp) (I=,1I-11>) V diag" (VVT)
is (2r)-Lipschitz transferable. Indeed, is -qu-iivvaria ((k))invvriian, and diag" ((V @ LV I) diag" ((VV)) & (Im 1T))
= diag" (VVT) @ m,
Vi.12 1| 1| 1/P
"itag"(VVV) diag" (WWT) )|
i=1
1/8
IV.. We, V. + W:)l
1/p
V[Ve W (2r)²
(by Cauchy-Schwarz)
= 2r W
for V, W satisfying >|V||=> = max; V < ||]] = max [W < r.
The sequence of maps
(Baxk || (| + (R" Ill [.ll))), V vec(VVT)
is (2r)-Lipschitz transferable, where the codomain equipped with consistent sequence structure as follows: for g E Sn, define ((g) = g @ E S,,, and let act on R² by x()).. The symmetric groups (S..) are embedded into each other usual, and the vector spaces are embedded by Pum,n R== [nm)) where
Pnm,n (x) vec(reshape, (x) Lm 1T)
and reshape, : R Raxn is the inverse of maps, so is Pum.n. We then have for all V E R g E Sn, E O(k) that
matrices. Since these all linear
vec ((V & LV & Im)T) = vec ((VVT) & (1m [mi) = Prom (veo(VV vee (oVhT)) voo[gVV g v(V)vc((VVT)
50

---

Furthermore,
1/p
1
[ -vec(WW
(V VaA) - (W (w... W.:)
n1a i
1/8
1 n2a
Σ
(KVi,, Vy. - - +IVE - We, w3:1
1/p
1
Σ
20-1 p" (IIV;: w + IIVe Well3)
n2a 1.
(Using (a + 6)p - ( bi) and Cauchy-Schwarz)
2r W
for V, W satisfying ||V| = max, V|Vill r, || max, |W <
The scalar maps
(R"*k, || || I 1), V ((VVT)
is (4ps)-Lipschitz transferable. Indeed, it is S x (lk) invariant and 7C(( @
-((VT)-
1
(Ve. Vi. (W.. W.l.l
n²
25
5 1
Σ
KV.. Vi+ (W.. W 1 + KW., W lIV. |
i
< II W
(by the previous two computations)
S 4r IVV
W
WlIp:
for V. W satisfying ||V| = max; 1V < r. [| = max; W < r.
If the activation functions used are Lipschitz, then MLPs are Lipschitz. By Corollary F.4, the normalized DeepSet is Lipschitz transferable, assuming the constituent MLPs are Lipschitz.
Thus, our compatible DS-CI architecture is composition of Lipschitz layers.
Finally, we conclude that the normalized DS-CI is "approximately transferable" since it asymptoti- cally equivalent to the compatible DS-CI up to an error of O(n-1
Lemma H.2. the activations in all the MLPs used are Lipschitz, then for any sequence of inputs (a) E 1 (C-D--CL((Vnn) - (L, = O(n
Proof. Assume for R", (ee)Set(,))z) c E, P(x:)) and o. Lo, Lp Lipschitz respec- tively. Then, we have
((VVT)- -
1 n(n- 1((n-) 1)
Σ
(VV D.VVV)ll
E(VVT> =0
n²?
n²
igj
51

---

and, moreover,
DeepSet(2) (I7E(VVT) t= El.. ((..)(()-1))))))
-DeepSetor (2) ( (177(VVT)
1 n² E (e(((V) = -(n
$ Lo
n - n²
(((VV))6))=
Since every layer is Lipschitz, this leads to an overall error of
Following the analysis above, we can directly apply Propositions D.4 and D.5, together with the convergence rates established in Appendix D.3. Moreover, observe that the O(n discrepancy between normalized DS- CI and compatible DS-CI dominated by the convergence rate of interest. This immediately yields the following transferability result.
Corollary H.3 (Transferability of normalized DS-CI), Let (Xn) E Bun* be a sequence of matrices sampled from the same underlying distribution μ. E (R((R) with bounded support in the following way: first, sample Yn E TRnn with rows drawn i.i.d. from p. Then, let G O(k) be a (random or deterministic) rotation matrix, sampled independently of Yn. and define Xn Yn G. Then,
E ( DSS-CIm((X))
n 11/2 + m1112
if 1,
2
n 1/2 1/2 log(1 + n2) + m 112 log(1 + m)
if 2,
n 1/k + m 1/k
if > 2.
H.3
Constructing new transferable models: SVD-DS
We propose the SVD-DS model defined as follows:
SVD-DS, T RR X DeopSct, (XV))
where = T is the singular value decomposition (SVD) for X with ordered singular values. We proceed to show that it is locally transferable almost everywhers on its domain, and that its performance competitive with DS-CI while being more computationally efficient.
Transferability analysis of SVD-DS. We extend the SVD elements in the limit space Voc ([0 1J, RR) and analyze its continuity, yielding the following transferability result. Recall our definition of locally Lipschitz transferable point in Appendix D.I.
Corollary H.4. Endow the duplication consistent sequences with the normalized Eg norm induced by || 2l2 on RR.. Observe that
1/2
n
|
1X|E
n
where || denotes the Frobenius norm of matrix. Then, the sequence of maps (SVD-DS,) compatible and locally Lipschitz transferable at every point except for a set of measure zero, corresponding to points with non-distinct singular values.
Remark H.5. This transferability result is weaker than the "Lorlllocally Lipschitz transferability" defined in Definition 3. I, since our model may be discontinuous at points with non-distinct singular values. Therefore, in this case our transferability results in P Propositions D.4 and D.5 only apply to sequences (Ir) converging a limit x Voo with distinct singular values.
Proof. Decompose SVD-DS, as the composition
Vaup (R X-XV U= U
DrepSet
VR.
where Vp is the trivial consistent sequence over R, and the consistent sequence U consists of vector spaces Un Baak under the duplication embedding @I.. The group S,, x O(k) acts on U, by (g, h) X gX, i.c.. the action of O(k) is trivial. By Corollary F.4, the normalized DeepSet map
52

---

is Lipschitz transferable, assuming the constituent MLPs are Lipschitz. It remains to show that the SVD-based map XV extends to a function that locally Lipschitz every point with distinct singular values. We show this in Proposition H.7 below after extending the SVD all of Vo and considering its ambiguities.
Following the analysis above, we can directly apply Propositions D.4 and D.5, together with the convergence rates established in Appendix D.3. These results immediately yield transferability result for SVD-DS.
Corollary H.6 (Transferability of SVD-DS). Let (Xn) Baxk be sequence of matrices sampled from the same underlying distribution ja E Pa (TR* in the following way: First, sample Y,, E Bank with rows drawn i.i.d. from μ.. Then, let G (k)) a (random or deterministic) rotation matrix, sampled independently of y and define Xn Y, Suppose the second moment Exzgxx E l of y has & distinct eigenvalues, then
E [[JSVD-DS (X,,. SDDDDSS (Xm)
n 1/1 + m m-111
4 ifk= 4
n 1/4 log' (22 + n) + m m0/mmm///mm 1//10/"/////////////// 122(1 + m)
n 1/k +
1/k
i 4.
Note that the functional SVD is locally Lipschitz only at points where the singular values are distinct. This motivates our assumption on the distribution ls in the Corollary. To see this, observe that when 2 k. the singular values of X are the same as those of Y,, and are the square roots of the eigenvalues of Y, Yn Σi= m.p. _ where H; are the rows of Yn, sampled i.i.d. from p.. The functional singular values of X, (i.e. र of the usual matrix singular values) is then Σi= x.a. By the law of large numbers, each entry of this matrix converges almost surely:
12
E Emn for all m, n E [k).
72
7IL
where E = -Ezzyllz is the second-moment of It follows from Weyl's theorem that each eigenvalue converges almost surely to those of Σ:
A
A3 (2)
Σ + 0 for all j e [k].
Therefore, if E has distinct eigenvalues, then with probability one, the empirical matrix has distinct eigenvalues for all sufficiently large n, ensuring that the functional SVD is locally Lipschitz at this point.
Functional SVD and its local Lipschitz continuity. We can identify the space Vso [[o 1]. R+) with ( 1)), R²), the space of bounded linear maps [[2, 1]) - R endowed with the Hilbert- Schmidt norm Iss. In more detail, each X E (² 1], R can be written as sequence of rows X = (f1...., fT) where ft E ( 1)), and such X defines the bounded linear map (fk. Conversely, any bounded linear map X: [[0 1]) - TR of Xs [).,))..... the form Xf = ()..., (T) for some fk. E [ 1]) which we view as the columns of X, and || = - piecewise-constant columns fa on consecutive intervals of length 1/n.
= [| Here Vn = BRak is viewed as the subspace of Voc with
Note that X vanishes identically on V/- f1.. - while X: V/- + R is a linear map between dimen-dimeiional vector spaces and therefore admits a singular value decomposition. Thus, there exists positive numbers R& 20 orthonormal u1.... uI..... 2h R and orthonormal functions
......, Ug [[0 1)) satisfying
Σ
(24)
If X E R and X = Et= o,ú, is the usual SVD of X, then 0; 0./Vnn, ;4 0; and u. (t) Vn(ū is the functional SVD of X as in (24). Conversely, if (24) is the functional SVD
53

---

of such an X then X = right singular vectors V are the same in both SVDs.
is the usual SVD of X. Note that the
If for any X E Vn we let (x) be its (functional) singular values from (24) and (X) be its usual singular values, then
= 1 > (x) | = 1 11
-
Σ ox)x))
(25)
==1
==1
and by Mirsky's inequality [61].
(lo(X) oYY)l2 5 - 8(1)22 - //2 X Y = XX-
-Yl
(26)
vn
vn
Furthermore, whenever V E R and X E Vn we have
|XV 1
[V] S J vn
Vn |XVII=
(MV [
(27)
Note that the final bounds in all of the above inequalities are independent of n, continuous in II+ and hold for all X E Vo.. We therefore conclude that they also hold for all X E Vos, with l1 replaced with || |[
There an ambiguity in the above decomposition, since (u:), (u:) satisfy (24) then so do (s;44,, (8:0;) for any choice of signs distinct then this is the only ambiguity in (24), see [13]. To disambiguate the SVD, we therefore choose signs so that 0; -t; in lexicographic order. When the entries of the u; are all nonzero, this amounts to requiring the first row of V " Uu] to be positive. We proceed to prove that the
{+1}. Furthermore, if the singular values (a;) are
map X + (XX = (U....., Uk] with this choice of signs is locally Lipschitz continuous dense subset of Voc.
Proposition H.7. Fix Xo E Vo with distinct singular values and all-nonzero entries in its right singular vectors (v:). Let gXp, minggiss (o (x(X))²) be the minimum gap between p-th powers of (functional) singular values of Xo. and set
v8(201 (Xa) + 1) B(Xo)=
(28)
gap2 gXp)(Xp)
For any & E Vo satisfying
Xx - 1 S 1A gap (Xo)
min
[[or(Xo)lyb
2
2B(X))
15ijSk
the following two hold true.
1. The matrix X has distinct singular values, and all nonzero entries of (x) have the same sign as those of (Xo)).
2. We have
[[V(X)) 5 - R|lns:
(29)
and
(XVV(X.) - Xv I (kor + 1)] - &I
(30)
Proof. We start by establishing the first claim. If IXo 811 S we have by
gap, (Xp) then for any 2 5 i 5
k
2/k
Ti (8)));(88) 1 - (x-) + t0;-1(Xo)
(xo) (o; o8
> (oi- (0;-1(Xo) ox()))) Σ (xx(8) (Xo)
gap (Xo)
Villo(Xo)) - o (8)1l2
(Cauchy-Schwarl
gap/ (Xp)
2 > 0.
(Mirsky's 's inequality (26))
54

---

Thus, X has distinct singular values.
Let gapy (Xo) minagige for-1 - be the minimum gap between p-th powers of (usual) singular values of Xu. For Xo. X E Vn the result [90, Thm. 4] shows that for each E [kt]
min [Xa s. (1))1
#c *E(+1)
v8(28) (X)) + 516 - 8))11xo- - 811
sap2(Xo)
V8n(201 (Xo) t0 (x- - 8))[1Xo - R11E ngaap((X))
(since o,(X) = (x))
V8(201 + 01 (Xo x))]1XXo - 8112
(since | = ||
gXp)
V8(201(X)) + 1o00 - 8 [ [Xo - 811
(by (25), (25), < | = Σ (x
gap2(Xo)
V8(201(Xo) + 1) X11
(since 1 -xll I 1)
sap2(Xp)
X(X - -I
The final bound is independent of and hence applies all of Voo It is also continuous in || llz on the dense subset of Voo consisting of operators with distinct singular values, so taking closures we conclude that this bound upplies for any Xo. X E Vox such that gXp) > O. Combining the last line above with our bound on || Xullz. we get
min max sE(#1) 15)Sk
[ux(Xx)]] - 8 [ve (8)1
(x((X)) - 8 (8 11/ S min *E(1
min
(x))ll
2 151Jjs
(31)
Thus, the sign s achieving the above minimum is the one making all entries of u (x( have the same sign as those of (Xo). Since the first entries of (X(o)) and of u, (8) are positive, we conclude that 1 achieves the above minimum.
To prove the second claim, we combine the bounds above, which yields
k (1o) -v,())(((11) vx(8)112
[|V(X) - v(8)
k min [loi(Xo) - 8 (8)22 (E(1]
Σ
&B 8 ns:
8|Ins
as claimed. Finally, applying the triangle inequality gives
(xx) - [loo(V(X.) v(()) Ilu + I[Xo X))
< (X)(X))o(XX))IXo - X|| + ||Xo - -X1l
(by (27))
yielding the last claim.
SVD-DS is computationally more efficient than DS-CI. When k & n (for example, for us k = or 3), evaluate SVD-DS given input of size n x k, we need compute its SVD takes O(nk²) flops [32, Section 8.6]-and then evaluate DeepSet on the output, which takes (K)(())) where C(k) is the cost of evaluating the involved fixed-size MLPs taking inputs of size k. Moreover, during training,
can compute the SVD of the dataset once in advance. In contrast, for DS-CI we need to form VVT at a cost of O(n and this needs to be differentiated through during training. After forming VVT, we evaluate normalized DeepSets on entries at a cost of 0(n²). Thus, SVD-DS is much faster to train and deploy than DS-CI.
55

---

Transferability plots. The numerical experiments illustrating the transferability of SVD-DS and normalized and compatible DS-CI shown in Figure
Nommlizzd DSS-I1 bepeesimunlyy (mndfrnhl))
-0.090
Compuible DS-CT (rassfendhl)
0.094
0.096
10
10a
10a
102
10'
Pointeloud siac
Pointcloud size a
(a) Normalized SVD-DS
(b) Normalized DS-CI (approximately transferable) and
(transferable)
Compatible DS-CI
(transferable) [S]
Figure 6: Transferability of invariant models point clouds with respect to (V dup: II [pp). The plot shows outputs of untrained, randomly initialized models for sequence of point clouds X RT** where each point sampled i.i.d. from (0, Ix). The bars extend from the mean random samples. The figure shows that transferable models generate convergent outputs. Figure (h) shows asymptotic equivalence between the normalized DS-CT and compatible DS-CI as proved in Lemma H.2.
standard deviation
100
I Size generalization experiments: details from Section 6
In this section, we provide details of our size generalization experiments. All experiments were implemented using the PyTorch framework and trained on a single NVIDIA A5000 GPU. Specific training and model configurations are provided in the descriptions of the individual experiments. For all experiments, the training dataset consists of inputs with a fixed, small dimension Merain- For evaluation, we use series of test datasets where the input dimension Rtsst is progressively larger than Ttrain-
I.1
Size generalization on sets
We consider two dimeessiiio learning tasks on sets, where the target functions have different properties, so that different models are expected to perform better. In both experiments, we compare the size generalization of three models: DeepSet, normalized DeepSet, and PointNet as analyzed in Appendix F.2. The maps and in the model are parametrized by three fully connected layers with hidden dimension of 50 and ReLU activation functions. Training was performed by minimizing the MSE loss using AdamW with an initial learning rate of 0.001 and weight decay of 0.1. The learning rate was halved if the validation loss did not improve for 50 consecutive epochs. Each model was trained for 1000 epochs, with each run taking less than three minutes to complete.
L1.1 Experiment 1: Population statistics
We adopt the experimental setup from [91, Section 4.1.1], which comprises four distinct tasks on population statistics. In all four tasks, the datasets consist sets where each set contains i.id. samples from distribution μa, where μ itself is sampled from parameterized distribution family. The objective to learn either the entropy or the mutual information of the distribution ja.
While the original experiment in [91] focused on training and testing with set sizes Ptrrin nesst [300, 500], we instead evaluate size generalization. During the training stage, the dataset consists of N = 2048 sets, each of size Ptrain = 500. This dataset is randomly split into training, validation, and test data with proportions 50%, 25%, and 25%, respectively. During the evaluation stage, the trained model is tested sequence of datasets with set sizes Mues E (500, 1000, 1500, .,00,,..,450),, each consisting of N 512 sets. The descriptions of the four tasks, as originally presented [91], provided below:
56

---

Rotation: Generate N datasets of size M from (0, R(a)ER(a))) for random Σ and a E [0, x]. The goal is to learn the marginal entropy of the first dimension.
Correlation: Generate sets from (0 [Σ, aZ; at, 2) for random E and a E (-1, The goal is to learn the mutual information between the first 16 and last 16 dimensions.
Generate sets from (0, 1 + Xvo")) for random v E R and X E (0, 1). The goal is to learn the mutual information.
Rank I:
Generate sets from (0, Σ) for random 32 x 32 covariance matrices Σ. The goal is to learn the mutual information.
Random:
For all tasks, the target functions are scalar functions on the underlying probability measure ft, and continuous with respect to the Wasserstein p-distance. Based on Appendix F.2.1, normalized red DeepSet is well-aligned with the task from a continuity perspective and PointNet aligns from a compatibility perspective, while unnormalized DeepSet lacks alignment altogether. The results summarized in Figure 7, showing that stronger task-model alignment improves both in-distribution and gize-ggneraiization performance.
Thee Reesivm
Tedhh Combeiio
Thik Rick
Tokli Rondon
To: To/N0e
To: HIVE
Tos NORE
Eos NONE
30"
111
Doople
Trok
400
Crent aton
Resic Tlangh
Murad teberaie
Beaada Azgi
Consakks
Baal-1 Le
Seriid Indi
Figure 7: Size generalization for population statistics experiment. All models are trained set size Alminn 500 and tested on set sizes Rux E (500, 1000...., 45003. Top: MSE (log scale) vs. test set size. The solid line denotes the mean, and the error bars extend from the minimum to the maximum test MSE over 10 randomly initialized trainings. Normalized DeepSet performs better than PointNet, which in turn outperforms DeepSet. Middle: Test-set predictions of the three models vs. ground truth for Neest Titrain = 500. All models perform similarly. Bottom: Test-set predictions vs. ground truth for neesst 4500 >> Perain 500. DeepSet has blown-up outputs due to scaling. Normalized DeepSet outperforms PointNet in Task 3.
L.1. Experiment 2: Maximal distance from the origin
We consider the following data and task: each dataset consists of sets where each set contains n wwo-dimensional points sampled as follows. First, a center is sampled from (O, I2) and a radius is sampled from [n, 1)). which together define a circle. The set then consists of n points sampled uniformly along the cireumference. The goal is to learn the maximum Euclidean norm among the points in each set. Equivalently, our goal is to learn the so-called Hausdorff distance ({0), X) = supsex || see (1 Hence, the target function depends only on the support of the point cloud and is continuous with respect to the Hausdorff distance.
57

---

Once more, we evaluate size generalization. During the training stage, the dataset consists of N 5000 sets, each size Atrrinn = 20. The dataset is randomly split into training, validation, and test data with proportions 80%, 10%, and 10%, respectively. During the evaluation stage, the trained model is tested on a sequence of datasets with set sizes neest. E {20, 40..... 200). each consisting of N 1000 sets. For this task, PointNet aligns from continuity perspective, normalized DeepSet from a compatibility perspective, and DeepSet does not align with the learning task. The results are summarized in Figure 8, showing that the model performance improves with task-model alignment.
Model oulpuls on sel size Riye 20)
Model ouipuls on sel size Rour 200)
4.0
4.0
DoegSet (incoppstte))
DeepSet (inorpaanble)
DoepSet (iccoppaihie)
10
PointNet (tunstecabte
Nemedkanal Dappfet Scompalibee Innderable)
Predleted distarnce
3.5
3.0
PointNet (tnasfessaii))
(companiNee, not transéicatle)
Nomaliaad Dapp::
3.5-
30
PointNes (tundauuSSe)
Nomulizal DespSet
(composible not tranterrate)
Test MSE
10-1
2.5-
2.5
2.0-
Predicted
2.0
10-3
10-5
0.5
0.0
00
20
60
100
140
180
Test set size (n)
True distance
Troc distance
(a)
(b)
frrmoonce-roomorriiin task. All models trained set size Pimin 20 and tested on set sizes nhet E {200,4 .0......... 2003. Figure (a): Test MSE (log scale) vs. test set size. The solid line denotes the mean, the error bars extend from the minimum to the maximum test MSE over randomly initialized trainings. PointNet performs better than normalized DeepSet, which in turn outperforms DeepSet. Figure (b): Test-set predictions vs. ground truth for set size predictions for Barai 20, while the right-most figure shows predictions for nust 200. PointNet very accurate in both cases, DeepSet exhibits incorrect blown-up outputs in the latter case.
Figure 8: Size generalization
Alrain 20. The middle figure shows
1.2 Size generalization on graphs
For graphs, the task is to learn homomorphism density of degree three. To formally describe the task, we first describe its inputs. We consider dataset consisting of N attributed graphs (A, generated according to the following two procedures (the first is described and reported in the main paper):
1. Each graph is fully connected weighted graph whose adjacency matrix has entries Aij iid.
Ass ~ ([0, 1]) for S j. and node features x; ~ Unif [0, 1]).
iid.
2. First, sample the number of clusters uniformly from {10, 20), and construct a K x K symmetric probability matrix P with entries sampled uniformly from [0, 1]. The resulting stochastic block model (SBM) is used to generate an undirected, simple graph with edges sampled as Ag Aft iid. Ber(P for i S j. where 24 iid. (nif(([....,KK)) are clus- ter assignments. Node features are given by x; Yep where 7 E with i.i.d. entries Uni 1)).
The task is to learn the rooted,
homomorphism density of degree three sending via
sym
x R +RR R", (A,x) 1.
y1
n
Σ
J,KE(n)
Note that when 1, yı corresponds to normalized count of triangles centered at node i. Thus, this can be interpreted as a signal-weighted triangle density. This formulation is related to the signal- weighted homomorphism density studied in [35], which generalizes the notion of homomorphism density extensively studied in graphon theory [54].
We conduct experiments to evaluate the size generalization performance of the following models: the GNN from [70], the normalized 2-IGN [56], and our proposed GGNN and continuous GGNN. ReLU is used the entry-wise activation function in all models. We choose the number of layers
58

---

and hidden dimensions such that each model has approximately 2k parameters to ensure an arguably fair comparison. During training, we use dataset of N 5000 graphs, each with Araiin 50 nodes. This dataset is randomly split into training, validation, and test with proportions 60%, 20%, and 20%, respectively. For evaluation, we test the trained models on datasets of graph sizes nrest E (50, 200, 500, 1000, 2000), each containing N = 1000 graphs. Training is performed by minimizing the MSE loss using AdamW with an initial learning rate of 0.001 and weight decay of 0.1. Each model is trained for 500 epochs. Training single run takes less than 3 minutes for the GNN model, and approximately 6-9 minutes for the IGN, GGNN, and continuous GGNN models, which are more computationally intensive. We note that evaluation large graphs is particularly time- and memory-intensivy for these models, taking up to several hours. Memory limitations restrict the maximum graph size we can evaluate to 2000.
The results of the size generalization experiments are summarized in Figure 9, Let us elaborate on these results. Since the target function naturally extends to the graphon-level signal-weighted triangle density (W, f) + 9. given by
g(z) = 1 W(x, (wt.:///ww.ww../ff
10.11
which is continuous with respect to the cut norm, models that are continuous under this topol- ogy-Such as the GNN and continuous GGNN- are aligned with the task at the level of continuity. Our proposed continuous GGNN, which is provably transferable and possibly more expressive than the GNN, achieves the best performance. Although GGNN is not transferable under the cut norm, it transferable under a weaker topology (see Appendix G.3), enabling to perform reasonably well. In contrast, the 2-IGN model, even after proper normalization, exhibits divergent outputs for larger graph sizes, indicating a lack of compatibility with the task.
Finally, we remark that the expressive power of various GNN architectures with respect to homomor- phism densities has been extensively studied. Prior work has shown that common GNNs-including those considered in this study are generally unable to express high-degree homomorphism densi- ties [14, 35]. However, our results demonstrate that GNNs can still achieve strong performance on this task when evaluated over certain large parametric families of random graph models. This does not contradict prior theoretical findings, as our results pertain to an average-case evaluation, while the negative results in the literature are established in the worst-case setting.
1.3 Size generalization on 3D point clouds
For our final set of experiments, we follow the setup of Section 7.2 in [5], which uses ModeINet10. We select 80 point clouds from Class 2 (chair) and 80 from Class 7 (sofa), and split them into 40 training and 40 testing samples per class. Each dataset has 40 x 40 cross-class pairs. The objective is to learn the third lower bound of the Gromov- Wasserstein distance in [60] (Definition 6.3). We prove in Appendix 1.4 that it is continuous with respect to the Wasserstein p-distance.
Unlike [5], which downsampled all point clouds to 100 points, we focus size generalization: training is done on 7mmain = 20, and testing is done on Thest E (20, 100, 200, 300, 500]. We compare the size generalization of 3 models: unnormalized SVD-DS, (normalized) SVD-DS and normalized DS-CI. For each pair of inputs V, V', we predict the GW lower bound via:
GW(V, V*) allW -(V)))
where 1ank + Ef is the S,, O(k))-nvariian model, t 10, and W E R a, learnable. All DeepSet components (o. Φ) are fully connected ReLU networks. We choose the number of layers and hidden dimensions such that each model has approximately 2k parameters to ensure a fair comparison. Training is performed by minimizing the MSE loss using Adam with an initial learning rate of 0.01 and weight decay of 0.1. Each model is trained for 3000 epochs. Training a single run takes less than minutes.
E are
The experiment results are summarized in Figure 10. Normalized DS-CI and normalized SVD-DS, both aligned with the target at the continuity level, achieve good performance. While normalized SVD- DS underperforms compared to normalized DS-CI, it offers superior time and memory efficiency.
59

---

Model ouiput on praph site Roer 50
Model output on groph size fly 2000
0.08
010
10
Nirmaliaed 2-0 (icompaiite]]
Honaal 2-00 iacopaaii
hormalted coumgpatiio
GNN lntramabi))
0.02
010-
GGNN (eompiitbl (rmmfonite)
Contranni toseetttttiiii
Contrare G220 insurtialll
Test MSE
Conterous GGNN trossfaabl
0.04
0
Prociativer
Preciattin
0.02
0.00
10-
0.02
012-
0.01
0111
200
500
1000
2000
0.00
0.00
0.01
0.00
0.00 Torget
0.04
0.05
0.00
0:00
0.00
0.01
0.0
0.93 Tirget
0.44
0.05
6.5
Test graph size (n) (a)
(b)
Model outpui graph
50
Model oueput graph
2000
Nemalied I-NN
Gl0 usur dksakie
CJS taaddcclii
GObN tumppal acciaiicaaa
GGNN compartll
Test MSE
Nomaliad 2-KNN (norrspathic
Phakesim
Phoderiorn
GNX (mandonaii))
10
(ourgxiliie, not trusfaablk) Contiraees OGNN cronsooaaie)
50
200
50D
1000
2000
5001
9413
50H
5.06
Test graph size (n)
Tagael
Tieget
(c)
Figure 9: GNN size generalization results on weighted triangle density. Figures (a)-(b) show the results on fully connected weighted graphs (the first data generation procedure), and Figures (c)-(d) show the results simple graphs sampled from SBM (the second data generation procedure). Figures (a) and (c) display Test MSE vs. test graph size. The solid line denotes the mean, and the error bar extend from the 20% to 80% percentile test MSE over 10 randomly initialized trainings. Continuous GGNN performs the best for both random graph models. Figures (b) and (d) display Test-set predictions vs. ground truth. The middle columns displays results for graph size Ricst
Ptrain 50, while the right-most column displays results for Neest 2000 and Attrain 50.
Midel output on
Model output on
10a
Unsserudical SVI-DS incompailee)
pointcloud size Rou 20
pointcloud size firs
500
Unaeee find SVD DS insoepulale Now dioe 5VD 166 the deeaains
Lieeees and SVD (evoquation
Narmalorsl
Nonsilow SVD D6 doedeerdoo
10
lsppncsimanll trassientii))
Niseadloo DG C1 tappoizzado
Nansilood DS (1
Test MSE
Pecoiction
Proiiie Homm
10
10-1
10-1
20
100
200
300
500
Test pointcloud sizes (n)
Target
Target
(a)
(b)
Figure 10: Size generalization results for point clouds. solid line denotes the mean and the error bars extend from the min to max test MSE over 10 trials, each taking the best of random initializations. (b): Test-set predictions vs. ground truth for graph size Aocest Nerain 20.
(a): Test-set MSE (log scale) vs. point cloud size n. The
and nigest 500 >>
Terain 20.
1.4 Continuity of Gromov- wasser-Wasserttiin distance and its third lower bound
The following is based on [60], though these continuity results are not stated there. Let μ E (RR)) be a probability measure, and associate with it the "metric measure space" (X, u) where X' = supp(μ) and dx(x;, v) || yllp- Given two such measures μ.v E (p((t)). the
60

---

Gromov-Wassersten Wasserstein distance between their associated metric spaces is defined by
Dp(u,D)= = inf =EM(H.)
(1=xx))
(32)
(1I I'1lp lly - 3 a'llo| dr (e, y) d x/)) 1/p
-nf =EM(u,))
(33)
where (x, ./) = ||a a'Ilp lly lp and M(U is the set of couplings between jr and D. The G-W distance admits the following lower bound [60, Def. 6.3).
D 2 (L TEM(N,e)
inf
(34)
where (,
inf [T y. 5:
rEM(aM
We aim to show that both D, and TLBp are continuous with respect to the Wasserstein-p metric on Pp. More precisely, the following Lipschitz bounds hold.
Proposition I.1. Let p. u, V' E PP(*). Then
(P - D plll 1/1 W,((s)) + v/).
(35)
Proof. By the triangle inequality for Pp. which holds by [60, Thm. 5.1( we have
Dp(m,v) S Dp p²) (p(, v/) + Dp(u, W
By [60, Thm. 5.1(d),, we further have D p,, )²)= S W (1, n²) and similarly for (p(u, v/). Combin- ing these inequalities and interchanging the roles of (J4, v) and (μl ,²), we get the claim.
The above proof only used the triangle inequality and the bound D, S W for the G-W distance. Since TLB, S Dp S. W, the latter property also holds for TLB. Thus, it suffices to prove TLB, satisfies the triangle inequality, hence similarly Lipschitz Wp.
Lemma I.2 (Triangle inequality for Puee). Let μt, & E (RR)). We have (x, S (2,e( 2) (2,02, (2,y))or all v. y, z the relevant supports. Furthermore, we have TLB,(H, v) S TLB,(H, TLB,(E,
Proof. Note that the usual triangle inequality for 1pp gives "1x, .5) I 2(2, 7=,,,,z'yf y²) for any y. 2, v'. E RR For any couplings лı M(n, and n2 M(E, the Gluing Lemma [82, Lemma 7.6] guarantees the existence of a coupling स E MM,, E, v) whose corresponding marginals are 11; 72. Let æ3 MM be the marginal of on its first and third coordinates. Then
(x v²" < [T )
< (T + T(z, 3 (l ( + [[T ()l
Since this holds for all couplings 1,, #2 as above, we obtain the first claim.
The second claim is proved analogously. For couplings T1, T2, v as above, we have TLB,(u, v) S (22, = [[Q,ellzr(=) & [[4 +22 & |10uelll and taking infimums over πI, completes the proof.
Proposition I.3. Let p. M,
pl, p, (R*)))) Then
TL, TLB, Wy(m,)) + Wylu,e).
(36)
Proof. The proof now identical to that of Proposition I.I.
The above argument generalizes to measures on different abstract metric spaces, we did not use the fact that all measures involved were over *
61

---

Limitations of this work
This work provides a theoretical framework for transferability based on consistent sequences. applies to several machine learning models that use fixed number of parameters to define functions on any-dimensional inputs. However, this theory does not capture all possible ways for inputs to grow in dimension. In particular, it does not capture settings where there is no limiting space containing all finite-sized inputs, and where such inputs can be compared. For example, how do we compare natural language inputs of different lengths to each other? Furthermore, while we believe our framework may extend to settings such as images (with varying resolutions and sizes), partial differential equations (across different scales), and sequences (of varying lengths), did not explore these directions. We leave these investigations for future work. Finally, as discussed briefly the related work, we do not consider the expressive power of neural networks the limiting space. If the target function is not expressible, mere alignment in terms of compatibility and continuity-as discussed in Section 4-is insufficient to ensure good performance. Studying universal approximation theory the limiting space an important and promising direction for future research.
62

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the work are discussed Appendix J.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
63

---

Justification: All proofs are in the supplementary material due to space constraints, All the assumptions are explicitly stated.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The main contribution is theoretical. Experiments are provided to illustrate the results. In the Appendix we provide all relevant details for reproduction, including the data, training and evaluation procedures. Also, the code is available via an anonymized GitHub repository.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
64

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The code with reproduction instructions is provided via anonymized GitHub repository.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
wwm.iisssssiiyiiooioo for more details. Seapii//uudes//ooeeeeee
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ /nips. wwtpppccccggcciccccoccoooococcce gwwc//gggge///eeee /Coee//mmdeubiiia ceotmisssionn wweeinssssonoiiiiiiioioo seeinnnyicy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All these experiment details are provided in Appendix I.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The transferability experiments report the mean among 100 random inputs with error bars indicating one standard deviation. The size generalization experiments report min/max results over 10 initialized runs, and evaluations are conducted on datasets with 1000 samples.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
65

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This information is reported in Appendix I.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttt:::///eurip.... ccc htcp
Answer:
[Yes]
Justification:
The research conforms the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theory paper. We cannot think of any direct societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
66

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All resources are properly cited.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi twwode.cooo.e... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
67

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide the code for reproducing our experiments through anonymized GitHub repository.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:[NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
68

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to our LLM policy (https for what should or should not be described.
69


Reviews:
[{"review_id": "dHSYGFXG8c", "reviewer": "Reviewer_ZWs5", "summary": "This paper develops a general theoretical framework for transferability based on the notion of consistent sequences. This means modeling any-dimensional learning problems by identifying smaller instances of data with larger ones in a structured way, which results in a nested sequence of problem instances. These sequences are embedded into a common limit space, where transferability is then characterized by continuity. For graphs, using the duplication embedding recovers the classical graphon limit, which much of the prior work on GNN transferability is based on. The central goal of the paper is to generalize and unify these concepts, i.e., to simplify existing analyses and extend them beyond graphs. The authors apply their framework to sets, graphs (MPNNs/IGNs), and point clouds, showing how different architectures do or do not satisfy the conditions for transferability. A model is transferable if it defines a continuous function on the limit space and is compatible with the embeddings used. The paper also presents a size generalization theorem. The theory is supported by experiments on transferability and generalization across all modalities.", "questions": "- Re Proposition 4.2 (generalization bound): It might be helpful to elaborate a bit more on the assumptions and their practicality. As the rate crucially depends on the covering numbers $C_X(\\varepsilon), C_Y(\\varepsilon)$, what can we expect these to be for the different modalities covered in the paper? I.e., do you expect this bound to be non-vacuous in some concrete cases?\n- In line 2165, you state that your continuous GGNN (as a variant of 2-IGN) is \"likely more expressive than the GNN\". To my knowledge, the 2-IGN you consider, at least for graph-level predictions, should be exactly 2-WL (not 2-FWL) expressive, and thus no more expressive than MPNNs (see, e.g., [1] or § 2.3.3 of [2]). I'd appreciate if you could check and clarify this point.\n- Re the size generalization experiment in § I.2: Compared to the experiments for other modalities, the GNN results in Figure 7 appear slightly more noisy/inconclusive to me. Also, in line with the previous suggestion, I would not have expected any of the models you considered to be able to express this triangle density on the graph distributions you use. Some intuition at the end of § I.2 is provided, attributing this to average case instead of the worst-case setting that is often considered in the GNN expressivity literature, but it might still be interesting to find out what is actually learned. That said, I acknowledge this is only tangential to the core message of the paper.\n\n[1] Floris Geerts. *The expressive power of kth-order invariant graph networks.* arXiv:2007.12035\n\n[2] Stefanie Jegelka. *Theory of Graph Neural Networks: Representation and Learning.* arXiv:2204.07697", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- In my view, the contribution is simple, elegant, and insightful. Framing transferability as continuity in a suitably defined limit space, which could come from any any-dimensional modality, offers a principled perspective on size generalization that, to the best of my knowledge, is not present in the existing literature. Rather than providing new heavily technical results or improving existing (tight) bounds, to me the contribution stands out more in clarity and unification of prior ideas.\n- The paper is beautifully written (including the proofs) and quite easy to follow despite the theoretical depth. It really was a pleasure to read.\n- Related work is extensively discussed, and off the top of my head, I couldn't think of any relevant prior work that might be missing. The placement of the work within the literature is quite clear.\n- I do not have significant criticisms of the paper (for minor things, see Questions). Some may wish for more technical novelty, but I think that the paper succeeds in its aims.", "was_revised": true, "final_justification": "As the authors engaged meaningfully with my rebuttal (which had only raised minor points), the rebuttal has not really changed my positive view of the work. I think it will be a valuable addition to the conference and I am happy to recommend acceptance.", "rebuttal": "Thank you for the thorough review of our manuscript and your encouraging comments. It is rewarding to hear that you found the paper a pleasure to read and appreciated its clarity and theoretical insights. We also value the thoughtful questions raised, which we will address below.\n\n> Re Proposition 4.2 (generalization bound): It might be helpful to elaborate a bit more on the assumptions and their practicality. As the rate crucially depends on the covering numbers $C_X(\\varepsilon) ,C_Y(\\varepsilon)$, what can we expect these to be for the different modalities covered in the paper? I.e., do you expect this bound to be non-vacuous in some concrete cases?\n\nWe briefly discussed two concrete cases where this bound is not vacuous, in Example E.5 and Example E.6 in the Appendix (lines 1367-1384). Example E.5 concerns the case of sets endowed with the normalized $\\ell_{p}$ metric, which is related to the space of probability measures with the Wasserstein metric. Here, if $X$ is the space of probability measures supported on a fixed compact set, it is known that $X$ is compact, with an upper bound for $C_X$ provided in a cited result. Similarly, Example E.6 addresses the case of graphs endowed with the cut distance. In this context, for $X$ defined as a nice space of graphon signals, a cited result likewise determines a bound for the covering number $C_X$. \n\nWe acknowledge that this discussion is a bit hidden and buried within the technical details, which makes it easily overlooked by readers. To enhance readability, we will add pointers and remarks.\n\n> In line 2165, you state that your continuous GGNN (as a variant of 2-IGN) is \"likely more expressive than the GNN\". To my knowledge, the 2-IGN you consider, at least for graph-level predictions, should be exactly 2-WL (not 2-FWL) expressive, and thus no more expressive than MPNNs (see, e.g., [1] or § 2.3.3 of [2]). I'd appreciate if you could check and clarify this point.\n\nTo clarify, we are comparing the continuous GGNN with the GNN in [3]. Continuous GGNN is at least as expressive as GNN: in equation (20) (just below line 1860), if we set all the $\\alpha$'s to $0$ except $\\alpha_1 = 1$, and all the $\\theta$'s to $0$ except $\\Theta_{1,s}$, then we exactly recover the GNN. This result naturally follows the definition of nonlinearity (see equation (19)). We claimed that a continuous GGNN is likely more expressive than a GNN. This claim is supported by our size generalization experiment on triangle density, where continuous GGNN clearly outperforms GNN with a comparable number of parameters, both in terms of in-distribution and size generalization. We agree that the claim is not rigorous since we did not investigate the theoretical expressive power. We will change the word \"likely\" to \"possibly\".\n\nRegarding the k-WL expressivity perspective, we think there is an exciting direction to explore here.  There is a conceptual difference between the standard k-WL expressivity and the expressive power of graphon-compatible GNNs (i.e., GNNs that are compatible with the duplication-consistent sequence and thus extend to graphon space). This is because the different-sized graphs corresponding to the same step graphon are always distinguishable by WL, but considered equivalent by any graphon-compatible GNNs. Instead, it is necessary to consider a variant of k-WL specifically designed for graphons (see [4]). Similar conclusions hold: MPNNs with mean aggregation that are graphon-compatible are at most 1-WL expressive, while the graphon-compatible variant of 2-IGN achieves 2-WL expressivity [5]. These results may suggest that these architectures have equivalent expressive power in terms of k-WL graphon distinguishability. On the other hand, a more fine-grained understanding of the potential difference of their expressive power requires additional work, which we leave for future research.\n\n> Re the size generalization experiment in § I.2: Compared to the experiments for other modalities, the GNN results in Figure 7 appear slightly more noisy/inconclusive to me. Also, in line with the previous suggestion, I would not have expected any of the models you considered to be able to express this triangle density on the graph distributions you use. Some intuition at the end of § I.2 is provided, attributing this to average case instead of the worst-case setting that is often considered in the GNN expressivity literature, but it might still be interesting to find out what is actually learned. That said, I acknowledge this is only tangential to the core message of the paper.\n\nWe agree that the GNN size generalization results in Figure 7 are less conclusive than others. As you pointed out, this is partly due to an expressivity issue. While we prove that transferable GNNs extend to graphons and are continuous with respect to the cut distance, this does not imply that they can approximate **all** continuous functions with respect to the cut distance. Indeed, this is known not to be the case for GNNs. In particular, none of the models we considered could express triangle density exactly. \n\nUnfortunately, we do not have a clear explanation for this issue beyond what we included in the original manuscript. To the best of our knowledge, there is no average-case theoretical analysis that captures this expressivity, i.e., whether GNNs can **approximate** homomorphism densities with good precision in expectation under certain distributional assumptions. We believe that this would be an interesting direction for future research.\n\nReferences:\n\n[3] Ruiz, Luana, Luiz Chamon, and Alejandro Ribeiro. \"Graphon neural networks and the transferability of graph neural networks.\" Advances in Neural Information Processing Systems 33 (2020): 1702-1712.\n\n[4] Böker, J., Levie, R., Huang, N., Villar, S. and Morris, C., 2023. Fine-grained expressivity of graph neural networks. Advances in Neural Information Processing Systems, 36, pp.46658-46700.\n\n[5] Herbst, Daniel, and Stefanie Jegelka. \"Higher-order graphon neural networks: Approximation and cut distance.\" arXiv preprint arXiv:2503.14338 (2025)."}, {"review_id": "mGqGCy9WRH", "reviewer": "Reviewer_bCzQ", "summary": "This paper introduces a rigorous and mathematically elegant framework to analyze when and how machine learning models can generalize across varying input sizes—a property referred to as transferability across dimensions.", "questions": "see weaknesses", "limitations": "see weaknesses", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n- The paper makes a strong theoretical contribution, offering a unifying perspective on size generalization across different data domains.\n- It is well-written and carefully structured, with illustrative examples and multiple scenarios discussed across settings like GNNs, DeepSets, and PointNet.\n\n## Weaknesses and Questions\n\n- **Notation and Clarity:** The paper is notation-heavy and may be difficult to follow for non-specialists. Although the general framework is clear, the narrative flow can be hard to track. Additionally, while GNNs are discussed in detail, it is unclear whether the focus is on node classification, graph classification, or other tasks, which could confuse readers unfamiliar with these distinctions.\n- **Conceptual Clarification:** The distinction between transferability (as defined in this paper) and more established concepts such as transfer learning and meta-learning is not clearly articulated. Furthermore, it is unclear how this notion of transferability relates to the broader problem of distribution shift between training and test sets.\n- **Bounded Loss Assumption:** Section 4 introduces the assumption of a bounded and Lipschitz-continuous loss function, which plays a central role in the generalization bound. However, the justification for this assumption is missing and its practical relevance is not discussed.\n- **Complex Assumptions:** Assumption 4.1 is quite dense, combining multiple technical conditions. While mathematically sound, such compound assumptions reduce readability and are uncommon in theoretical learning papers without further breakdown or justification.\n- **Convergence Rate Condition:** It is stated that  $\\xi^{-1}(N)\\rightarrow 0$ for $N\\rightarrow \\infty$, but no intuition or explanation is provided. Clarifying the role of this term and its dependence on the problem setup would enhance the theoretical transparency.\n- **Proposition E.3:** Why for $n\\rightarrow \\infty$ the upper bound in (7) goes to 0?", "was_revised": true, "final_justification": "I would like to thank author for their final response. considering the current response. My final decision is to keep my score unchanged.\n\n> We respectfully disagree with the reviewer’s view that this assumption is unrealistic in practice. As we have mentioned in the previous reply, standard loss functions are bounded when the predictions and target outputs are bounded. This can usually be assumed in practice, especially since we assume a compact domain. We are not entirely sure about the precise meaning of \"heavy-tailed loss distributions\" as referenced by the reviewer. We can discuss or clarify further if the reviewer could provide references related to theoretical analysis in this context. Meanwhile, we would also like to emphasize again that the primary focus of our work is on size generalization. In our view, specific considerations related to the choice of loss function is not relevant to the contributions of our study.\n\nThere are many works on generalisation error of heavy-tailed loss function where can be applied here. please check these works [1,2,3,4].\n\n\n> We would like to emphasize that the key contribution of this paper extends beyond presenting a new generalization bound (which occupies just half a page in Section 4 of the main paper). More importantly, it lies in the theoretical framework developed in Sections 2 and 3. This unifying framework enables the comparison of objects of varying sizes within a limit space, and the construction of the limit space and the associated distance metric followed from the consistent sequence structure. Without this construction, it would not be possible to meaningfully analyze Lipschitz continuity or gain insights into generalization behaviors involving objects of different sizes. Our generalization bound formalizes the scenarios where size generalization is achievable, rather than aiming to improve upon any existing bounds.\n\nI think the contribution is incremental in this sense. The authors should clarify the main difference between their work and many works which are focused on generalization error and why it is interesting to study this problem. \n\n\n**References:**\n\n[1]: Alquier, P. and Guedj, B. Simpler PAC-Bayesian bounds for hostile data. Machine Learning, 107(5):887–902, 2018.\n\n[2]: Cortes, C., Greenberg, S., and Mohri, M. Relative deviation\nlearning bounds and generalization with unbounded loss\nfunctions. Annals of Mathematics and Artificial Intelli-\ngence, 85:45–70, 2019.\n\n[3]: Lugosi, G. and Neu, G. Generalization bounds via convex\nanalysis. In Conference on Learning Theory, pp. 3524–\n3546. PMLR, 2022.\n\n[4]: Haddouche, M. and Guedj, B. Pac-bayes generalisation\nbounds for heavy-tailed losses through supermartingales.\narXiv preprint arXiv:2210.00928, 2022.", "rebuttal": "Thank you very much for the constructive feedback. While we would like to point out that some of the aspects you mentioned are indeed addressed in the Appendix, we understand that the length of the manuscript may have made these points less visible, and we appreciate you bringing these concerns to our attention. We will make an effort to clarify and include pointers. Below, we address each of the concerns and comments you posed.\n\n> Notation and Clarity: The paper is notation-heavy and may be difficult to follow for non-specialists. Although the general framework is clear, the narrative flow can be hard to track. Additionally, while GNNs are discussed in detail, it is unclear whether the focus is on node classification, graph classification, or other tasks, which could confuse readers unfamiliar with these distinctions.\n\nOur goal was to convey the general framework ideas to non-specialists while being organized and mathematically rigorous for specialists. We appreciate that you found the framework clear. We have made significant efforts to simplify the notation and definitions in the body of the paper and provide intuitive explanations to aid understanding, while preserving the detailed and rigorous version with additional notation in the Appendix. Unfortunately, it is challenging for us to simplify the presentation further since clear definitions are essential, and precise notation is necessary to achieve that clarity. To further improve accessibility for non-specialist readers, **we will include illustrations in the Appendix** that demonstrate how the framework applies to sets and graphs. These illustrations will visualize consistent sequences and sampling from limiting objects. Due to this year's rules, we cannot include them in this rebuttal.\n\nOur theoretical framework is general enough to apply to both node classification/regression tasks and graph classification/regression tasks; therefore, we did not explicitly distinguish between the two in the main paper. This distinction is addressed in lines 1025-1028 of the Appendix, where we explain that for graph-level tasks, we can simply use a trivial consistent sequence (one that is not size-dependent) to model the output space. After this small adjustment, all the analysis is identical for both node-level and graph-level tasks, so we do not emphasize this distinction further. We can add a comment about this to the body of the paper if the reviewer would like us to.\n\n> Conceptual Clarification: The distinction between transferability (as defined in this paper) and more established concepts such as transfer learning and meta-learning is not clearly articulated. Furthermore, it is unclear how this notion of transferability relates to the broader problem of distribution shift between training and test sets.\n\nWe acknowledge the potential confusion that may arise from similar concept names. The term \"transferability\" in the paper specifically extends the concept of \"GNN transferability,\" which is a well-established concept in the context of GNNs. GNN transferability refers to the phenomenon in which a GNN produces similar outputs for two (potentially differently sized) graphs sampled from the same underlying graphon, enabling performance transfer from smaller graphs to larger graphs. For more details, see [1], which discusses this concept as a pioneering work. Additional background information is provided in our related work section (lines 912-923 in the Appendix). \n\nWe note that while GNN transferability is somewhat related to transfer learning, it is not the same. Transfer learning typically involves pretraining a model on one task and fine-tuning it for a different, new task. In contrast, GNN transferability involves training a model on smaller graphs and testing it on larger graphs---usually without any fine-tuning---and obtaining predictable outputs, provided the graphs are sampled from the same underlying graphon. To our knowledge, GNN transferability is unrelated to meta-learning since it only considers one task. **We will add a footnote to address this point.**\n\n**Our notion of transferability addresses a specific type of distribution shift (size generalization)**: we assume there exists an underlying latent distribution $\\mu$ on an infinite-dimensional limit space (e.g. graphon space). This latent distribution induces a distribution $\\mu_n$ on the space of size-$n$ objects (e.g. graphs with $n$ nodes) via sampling or discretization. When training on size-$n$ graphs distributed according to $\\mu_n$, and testing on distribution $\\mu$ on the limit space, a distribution shift occurs. However, this shift is \"similar\" enough to allow for meaningful generalization. This phenomenon is formally described in detail starting from line 1333 in Appendix E. We highlight that the explicit connection between transferability and the distribution shift underlying the generalization bounds is a novel contribution of our work. The closest work include [3,4], but they do not consider distribution shifts since the training and test are done on the same distribution. We will highlight this point in the main text. \n\n> Bounded Loss Assumption: Section 4 introduces the assumption of a bounded and Lipschitz-continuous loss function, which plays a central role in the generalization bound. However, the justification for this assumption is missing and its practical relevance is not discussed.\n\nThank you for pointing this out. We highlight that this type of assumption is relatively standard in statistical learning theory (See e.g. [5,6,7]). **We will include the following justification in the next revision.** \"We note that these assumptions are relatively standard [5,6,7]. Moreover, when the predictions and target outputs are bounded, standard loss functions, such as cross-entropy, L1-loss, L2-loss, and Huber loss, are all bounded and Lipschitz continuous. Moreover, many clipped loss functions also satisfy this assumption.\" \n\n> Complex Assumptions: Assumption 4.1 is quite dense, combining multiple technical conditions. While mathematically sound, such compound assumptions reduce readability and are uncommon in theoretical learning papers without further breakdown or justification.\n\nWe agree with the reviewer that this is a rather technical assumption. Indeed, in Appendix E, we break down this assumption and provide detailed explanations and motivation to make it more readable and accessible. The explanations in Appendix E are organized into two parts: In the first part, we describe how directly applying the classical generalization framework from [2] to our defined limit space immediately yields a generalization bound that holds across any dimensions. In the second part, we discuss the limitations of this classical setup, explaining why it is unrealistic in certain scenarios. This motivates us to slightly modify the assumptions to account for the distribution shift between the training data and the test data. These discussions in Appendix E are intended to clarify and justify the assumptions in a more detailed manner for interested readers. Unfortunately, due to space constraints, we had to write Assumption 4.1 in a dense format to ensure that Section 4 remains concise, leaving more space for our theoretical framework established in the earlier sections, which are our primary contributions. **We will add a pointer directing the interested reader to Appendix E after Assumption 4.1.**\n\n> Convergence Rate Condition: It is stated that $\\xi^{-1}(N)\\rightarrow 0$ for $N\\rightarrow \\infty$, but no intuition or explanation is provided. Clarifying the role of this term and its dependence on the problem setup would enhance the theoretical transparency.\n\nWe thank the reviewer for their comment. We realize that although we explained why $\\xi^{-1}(N) \\to 0$ in lines 1311-1313 of the Appendix, this explanation might be overlooked by readers because the generalization bound results are divided into two separate propositions, Proposition E.2 and Proposition E.3, in the Appendix. The remark appears in the earlier Proposition, where $\\xi^{-1}$ is first introduced. We will make this clearer in the next revision.\n\n> Proposition E.3: Why for $n\\rightarrow \\infty$ the upper bound in (7) goes to 0?\n\nThe upper bound in (7) does not go to $0$ as $n \\to \\infty$ alone; it goes to $0$ if **both** $n$ (the dimension of the training data) and $N$ (the number of data points in the training data) go to $\\infty$. We mentioned this in Remark E.4. The result is because every term in the upper bound in (7) converges to $0$: we justified $\\xi^{-1}(N)\\to 0$ as $N\\to\\infty$ in lines 1311-1313; Moreover, $R(n)\\to 0$ as $n\\to\\infty$ by the assumption in line 1348, and $\\frac{2\\log(1/\\delta)}{N}\\to 0$ as $N\\to\\infty$ trivially.\n \nReferences:\n\n[1] Ruiz, Luana, Luiz Chamon, and Alejandro Ribeiro. \"Graphon neural networks and the transferability of graph neural networks.\" Advances in Neural Information Processing Systems 33 (2020): 1702-1712.\n\n[2] Xu, H. and Mannor, S., 2012. Robustness and generalization. Machine learning, 86(3), pp.391-423.\n\n[3] Levie, R., 2023. A graphon-signal analysis of graph neural networks. Advances in Neural Information Processing Systems, 36, pp.64482-64525.\n\n[4] Rauchwerger, L., Jegelka, S. and Levie, R., 2024. Generalization, expressivity, and universality of graph neural networks on attributed graphs. arXiv preprint arXiv:2411.05464.\n\n[5] Bach F. Learning theory from first principles. MIT press; 2024 Dec 24.\n\n[6] Shalev-Shwartz, S. and Ben-David, S., 2014. Understanding machine learning: From theory to algorithms. Cambridge university press.\n\n[7] Bartlett, P.L. and Mendelson, S., 2002. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of machine learning research, 3(Nov), pp.463-482."}, {"review_id": "1DG1khkOyG", "reviewer": "Reviewer_o4rd", "summary": "This work presents a unified framework for analyzing the size generalization of machine learning models that process variable-sized inputs, such as sets, graphs, and point clouds. The key idea is that transferability across sizes can be characterized by a notion of model continuity within a limit space. This limit space is constructed from a sequence of spaces of different sizes, enabling a meaningful comparison of distances across varying dimensions (so-called consistent sequences). In this framework, stronger model continuity directly implies smaller size generalization errors. The paper applies this perspective to analyze the transferability of popular architectures, including DeepSets, PointNet, and various graph neural networks, thereby offering a unified explanation of their size-generalization behavior. Finally, it proposes design principles for developing new models with provable transferability guarantees.", "questions": "N/A", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- This work provides a unified framework for the size generalization problem in different domains (sets, graphs, point clouds).\n- It also provides intuition on how specific tasks may favor models with particular continuity properties. This theoretical insight is supported by experimental validation, which can offer practical guidance for selecting or designing models based on prior task knowledge.\n- Although the paper is somewhat dense in terms of formal notions, it is well-motivated, clearly presented, and successfully conveys the underlying intuition.\n\n\n**Weaknesses**\n- The empirical evaluation is largely limited to synthetic dataset and synthetic task.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback. We are glad you appreciated our unified framework, theoretical insights, and clear presentation. \n\nRegarding your comment that \"the empirical evaluation is largely limited to synthetic dataset and synthetic task,\" we acknowledge that is the case. However, we decided not to pursue real-world experiments. Because our paper is primarily a theoretical contribution, the role of our numerical examples was twofold: (1) to demonstrate that practical performance tracks our theoretical predictions and (2) to validate our conjecture that size generalization depends on the alignment between the task and the model’s inductive bias. Achieving both objectives requires settings where instance sizes grow to infinity while still satisfying our assumptions. Although we believe these assumptions can hold in practice, we are unaware of real-world datasets whose instances grow arbitrarily large. We would happily apply our framework to a real-data example if you could suggest a relevant dataset and learning task."}, {"review_id": "YP6QDzAuCi", "reviewer": "Reviewer_H5KD", "summary": "The paper addresses a key challenge: how models trained with low-dimensional samples transfer across dimension. The authors introduce a unified theoretical framework for transferability: the capacity of a model trained on low-dimensional data to maintain performance when applied to higher-dimensional inputs. It equates transferability across input sizes with continuity in a defined limit space. In this space, inputs of different sizes can be identified and compared via appropriate metrics based on the data and task. The authors propose design principles for building models with provable size-transfer guarantees. They also provide empirical experiments to support their theoretical claims.", "questions": "Please refer to questions in weaknesses.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "*Strengths*\n\nThe paper seems to provide a clear theoretical foundation for a problem of transferability in machine learning by formalizing the transferability as continuity in a limit space.\nThe paper is well-structured, beginning with intuitive motivation, followed by clear definitions, theoretical results, and practical verifications. The specific examples on sets, graphs, and point clouds as well as additional experiments are provided in appendices.\n\nThe paper supports the design principles for building models that generalize across input sizes (e.g., foundation models for graphs, GNN for combinatorial optimization, neural PDE solvers).\n\n*Weaknesses*\n\nI am not a domain expert in size generalization and I am not quite familiar with the existing theoretical literature in this area. As such, I am not in a position to assess the originality of the proposed theoretical contributions with full confidence. My comments below focus specifically on the empirical aspect of the paper.\n\nTo verify the theoretical framework, the paper includes several empirical validation. While in Section 6 and Appendix H, experiments for size generalization involving DeepSets, PointNet, and certain GNN variants (e.g., population statistics, maximal distance from the origin, learn a homomorphism density of degree three) are well-designed, the settings tend to be synthetic and controlled. I believe the work would benefit from more experiments under real-world conditions to evaluate the proposed design principles. For example, instantiate the proposed framework on popular architecture types across diverse real-world tasks and larger-scale datasets.\n\n(Minor) What does ‘id’ refer to in line 96 $G_n=\\\\{id\\\\}$?", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback. We are pleased that you found the paper well-structured and clearly presented, and that you appreciated the design of our empirical experiments. Below, we address each of the questions raised in detail.\n\n> originality of the proposed theoretical contributions\n\nWe provide an original unifying framework for transferability and size generalization that significantly extends prior work on GNN transferability and is applicable to variety of models outside GNNs. This is supported by Reviewer ZWs5's comments: \"Framing transferability as continuity in a suitably defined limit space, which could come from any any-dimensional modality, offers a principled perspective on size generalization that, to the best of my knowledge, is not present in the existing literature.\"\n\nOur additional contributions include introducing techniques to derive new transferability proofs, designing new transferable models (continuous GGNN and SVD-DS), and suggesting principled ways to modify existing models to achieve transferability. Furthermore, we point out the connection between this general form of transferability and generalization bounds, leading to a new formulation of generalization that has been missing in prior studies on GNN generalization. \nThis work also highlights and formalizes the importance of task-model alignment for achieving size generalization. Additionally, we identify general cases that offer provable size generalization for all $n$---a strong result in size generalization that, to our knowledge, is absent in previous work.\n\n> (Minor) What does ‘id’ refer to in line 96 $G_n=\\\\{id\\\\}$?\n\n'id' here refers to the identity element in a group. In this case, $G_n=\\\\{id\\\\}$ means that $G_n$ is the trivial group, containing only the identity element. This is mentioned in the Notation section (Appendix A, line 892 in the supplementary material), We will clarify this in the main paper.\n\n> I believe the work would benefit from more experiments under real-world conditions to evaluate the proposed design principles. For example, instantiate the proposed framework on popular architecture types across diverse real-world tasks and larger-scale datasets.\n\nWe thank the reviewer for the suggestion, but have respectfully elected not to pursue real-world experiments. Because our paper is primarily a theoretical contribution, the role of our numerical examples was twofold: (1) to demonstrate that practical performance tracks our theoretical predictions and (2) to validate our conjecture that size generalization depends on the alignment between the task and the model’s inductive bias. Achieving both objectives requires settings in which the instance sizes grow to infinity while the learning tasks satisfy our assumptions. Although we believe these assumptions can hold in practice, we are not aware of any real-world datasets whose instances grow arbitrarily large. We would be happy to apply our framework to a real-data example if you could suggest a relevant dataset and learning task."}]

Author rebuttal:

Meta-review: In this (theoretical) paper, the authors introduce a general framework for understanding how machine learning models trained on small inputs can generalize to larger inputs (transferability). They show that transferability is mathematically equivalent to the continuity of the model's function within a specially constructed "limit space," which allows for the comparison of objects of different sizes. Based on this theory, the paper analyzes existing models for sets, graphs, and point clouds, proposes modifications to ensure they are transferable, and provides design principles for creating new models with provable size-generalization guarantees.

Most of the reviewers praised the paper  and the proposed approach for its elegance and ease of flow (reviewers ZWs5, o4rd and H5KD). Overall, the proofs are well structured, and the approach is original and compelling --- raising very few questions during the rebuttal period. 

Only one reviewer (bCzQ) raised concerns on the novelty of the approach and its assumptions. In particular, one of the major sources of contention seems to be the fact that the authors use the fact that the loss is bounded. This concern has been addressed by the authors (who claim that the input space is bounded). The reviewer references work with heavy tail losses, but the pertinence of these references in the context of this discussion is dubious. This reviewer is also the only one who argues that: "I think the contribution is incremental in this sense. The authors should clarify the main difference between their work and many works which are focused on generalization error and why it is interesting to study this problem". Since this is a highly unspecific request and since (as per the other reviewers) the motivation of the paper is clear, we have no choice but to down-weight the significance of reviewer bCzQ's comment.
Decision: Accept (spotlight)