Paper deep dive
Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation
Behrooz Tahmasebi, Melanie Weber
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is \emph{size generalization}: the ability of a model trained on inputs of one size to generalize to inputs of a different, potentially much larger, size. Classical statistical learning theory, however, primarily considers fixed input domains, and its guarantees often deteriorate with input dimension. Although extensive work has established when models on sets and graphs can be transferred across input sizes, such results do not characterize the statistical cost of doing so: the sample complexity of size generalization, and its relationship to classical in-domain learning, remain largely unknown. We develop a statistical learning theory of size generalization and establish a sharp exponential separation in sample complexity. Letting $n$ denote the number of training samples, we show that polynomial source decay is insufficient for efficient size generalization: while it yields error $n^{-\Theta(1)}$ and hence polynomial sample complexity for in-domain learning, size-generalization error decays only as $(\log n)^{-\Theta(1)}$, yielding an exponential separation. Thus, polynomial in-domain sample complexity can become exponential across sizes. We then identify an exponential source condition under which size generalization achieves error $n^{-\Theta(1)}$, recovering polynomial sample complexity. These guarantees are independent of input dimension and depend only on the number of training samples, yielding dimension-free scaling laws. We also provide matching minimax lower bounds, establishing optimality. To our knowledge, this work provides the first dimension-free minimax theory of size generalization and a rigorous characterization of when, and at what statistical cost, learning can transfer across input sizes.
Tags
Links
- Source: https://arxiv.org/abs/2610.19279v1
- Canonical: https://arxiv.org/abs/2610.19279v1
Trouble viewing inline? Open PDF directly →
Full Text
119,532 characters extracted from source content.
Expand or collapse full text
Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation Behrooz Tahmasebi & Melanie Weber Affiliation: Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS) Affiliation: Harvard University, Cambridge, MA 02138, USA Email: behrooz_tahmasebi,mweber@seas.harvard.edu Abstract Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is size generalization: the ability of a model trained on inputs of one size to generalize to inputs of a different, potentially much larger, size. Classical statistical learning theory, however, primarily considers fixed input domains, and its guarantees often deteriorate with input dimension. Although extensive work has established when models on sets and graphs can be transferred across input sizes, such results do not characterize the statistical cost of doing so: the sample complexity of size generalization, and its relationship to classical in-domain learning, remain largely unknown. We develop a statistical learning theory of size generalization and establish a sharp exponential separation in sample complexity. Letting n denote the number of training samples, we show that polynomial source decay is insufficient for efficient size generalization: while it yields error n−Θ(1)n^- (1) and hence polynomial sample complexity for in-domain learning, size-generalization error decays only as (logn)−Θ(1)( n)^- (1), yielding an exponential separation. Thus, polynomial in-domain sample complexity can become exponential across sizes. We then identify an exponential source condition under which size generalization achieves error n−Θ(1)n^- (1), recovering polynomial sample complexity. These guarantees are independent of input dimension and depend only on the number of training samples, yielding dimension-free scaling laws. We also provide matching minimax lower bounds, establishing optimality. To our knowledge, this work provides the first dimension-free minimax theory of size generalization and a rigorous characterization of when, and at what statistical cost, learning can transfer across input sizes. 1 Introduction In many geometric learning problems, the domain is not fixed once and for all. Sets vary in cardinality, graphs vary in the number of nodes, and objects encountered at test time may be larger than those observed during training. The goal is therefore not only to generalize to unseen in-domain samples but also to generalize across domains of different sizes. This desirable property is central to geometric machine learning (Bronstein et al., 2021; Weber, 2025) and is often studied as size generalization for sets and graphs (Yehudai et al., 2021; Bevilacqua et al., 2021). Recent work has made important progress toward understanding learning across sizes, but the available theory remains limited. One line studies transferability through graph limits, graphons, and related stability frameworks (Ruiz et al., 2020; Keriven et al., 2020; Levie et al., 2021; Levin et al., 2025), while another develops learning rules across dimensions using representation stability (Farb, 2014; Levin and Díaz, 2024; Levin and Chandrasekaran, 2023; Díaz et al., 2025). These works offer structural and statistical insights, but leave open a dimension-free minimax characterization of sample complexity across sizes. The ability to process variable-size inputs does not by itself close this gap. Deep Sets (Zaheer et al., 2017) and graph neural networks (Scarselli et al., 2008), for example, can be applied to sets and graphs of varying sizes and may even satisfy transferability guarantees: under suitable regularity conditions, such as Lipschitz continuity, a fixed model produces similar outputs on objects of different sizes. But such guarantees do not determine how the transferred error decreases with the number n of training samples, whether this rate is uniform over the training and test sizes, or how it compares with generalization at the training size. We therefore ask: given n samples at size d, can we control the generalization error simultaneously at every target size D≥dD≥ d, using a number of samples independent of both d and D? To address this question, we return to a classical idea. In classical learning theory, it is standard to impose a source condition on the desired task, since learning over an arbitrary space is impossible by a standard no-free-lunch argument. The source condition that enables the in-domain generalization error to decrease as n−Θ(1)n^- (1) is called polynomial source decay. Roughly speaking, it requires the Fourier coefficients of the target function to decay polynomially with their index. This condition is necessary and sufficient for efficient classical in-domain learning. Motivated by this phenomenon, we ask the following question: Do the conditions for efficient in-domain learning also enable efficient size generalization? Table 1: The statistical cost of size generalization. Source decay In-domain error Size-generalization error Polynomial n−Θ(1)n^- (1) (logn)−Θ(1)( n)^- (1) Exponential n−Θ(1)n^- (1) n−Θ(1)n^- (1) We therefore ask whether polynomial source decay remains sufficient for size generalization. Our main finding is a sharp separation: under polynomial source decay, the size-generalization error decreases only as (logn)−Θ(1)( n)^- (1). Consequently, an accuracy attainable with polynomially many samples for in-domain learning under the same condition may require exponentially many samples when the task must generalize across input sizes. Importantly, our resulting guarantees are dimension-free: they depend on the number of training samples, but not on the input size d (i.e., either the cardinality of a set or the number of nodes in a graph). In particular, classical transferability errors are typically controlled by the smaller object size, scaling as d−Θ(1)d^- (1) when D≥dD≥ d. By contrast, our generalization gap converges to zero with the number of training samples n and is uniform over both d and D, albeit at a slow rate. To overcome this limitation, we then identify when the exponential cost can be avoided. Under exponential source decay, which is stronger than polynomial source decay, we show that the size-generalization error improves from (logn)−Θ(1)( n)^- (1) to n−Θ(1)n^- (1), recovering polynomial sample complexity. Therefore, our main finding is: Efficient size generalization requires stronger regularity than in-domain learning; polynomial decay is sufficient for the latter, whereas exponential decay is needed for the former. Table 1 summarizes this contrast. Exponential decay arises naturally for heat (Gaussian) kernels, analytic functions, and local graph functions. Finally, we prove matching minimax lower bounds for both sets and graphs. The polynomial-versus-exponential separation is therefore not caused by a particular algorithmic issue. It is an inherent statistical limitation of size generalization over the corresponding source classes. Together, the upper and lower bounds provide a dimension-free minimax characterization of when learning can generalize across input sizes and at what sample cost. In short, in this paper we make the following contributions: • We develop dimension-free scaling laws for invariant learning and estimation on sets and graphs, with rates that hold uniformly across input sizes (Section 4 and Theorem 4.1). • We show that size generalization is fundamentally harder than classical in-domain statistical learning: under polynomial source decay, in-domain error is n−Θ(1)n^- (1), while size-generalization error is only (logn)−Θ(1)( n)^- (1), implying an exponential separation in sample complexity (Theorem 4.1 and Corollary 4.3). • We show that under exponential source decay, size-generalization error becomes n−Θ(1)n^- (1), recovering polynomial sample complexity independently of object size, at the cost of stronger regularity (Theorem 4.1). • We prove that the rates for both sets and graphs are minimax optimal, establishing that the separation is intrinsic rather than algorithm-dependent (Theorem 4.2). 2 Related Work Transferability and size generalization. Transferability across graph sizes has been studied through graph limits, graphons, graphops, and higher-order limits (Ruiz et al., 2020; Keriven et al., 2020; Levie et al., 2021; Ruiz et al., 2023; Maskey et al., 2023; Cai and Wang, 2022; Le and Jegelka, 2023; Herbst and Jegelka, 2025). Related work studies learning across set cardinalities and learning-theoretic formulations of graph size generalization (Zweig and Bruna, 2021; Maehara and NT, 2021). These works primarily characterize approximation, consistency, or stability across sizes. In contrast, we ask when an estimator learned at one size achieves statistical convergence rates that are uniform over all test sizes. Representation stability and any-dimensional learning. Our work builds on representation stability (Farb, 2014), which describes how structured families of representations stabilize across dimensions. Representation stability has recently been used in machine learning to design and analyze architectures for learning under symmetries (Levin and Díaz, 2024), optimization across dimensions (Levin and Chandrasekaran, 2023), graph limits (Levin and Chandrasekaran, 2026), scientific computing and PDEs (Phan et al., 2025), and finite-dimensional kernel learning under invariances (Díaz et al., 2025). The work of Levin et al. (2025), which establishes size-generalization bounds in a broad framework encompassing sets and graphs, is most closely related to ours. Although their framework provides transfer and generalization guarantees across dimensions, the resulting rates depend on dimension-dependent complexity measures, such as covering numbers of the domains. In contrast, we identify conditions under which convergence rates are independent of object size and characterize the tradeoff between invariant feature dimension growth and target approximation. To the best of our knowledge, our work is the first to establish this sharp separation between slow and fast regimes together with matching minimax optimality guarantees. For a broader discussion of related work, see the appendix. 3 Problem Statement Sets and (attributed) graphs. We study problems indexed by the object size d, the number of elements in a set or nodes in a graph, and fix a feature dimension r∈ℕr . A set is represented by X=(x1,…,xd)∈(ℝr)d≃ℝr×dX=(x_1,…,x_d)∈(R^r)^d ^r× d, while an attributed graph is represented by X∈ℝr×d×dX ^r× d× d, with r edge and/or node-feature channels. Accordingly, dX_d denotes ℝr×dR^r× d or ℝr×d×dR^r× d× d. These matrix and tensor representations are ordered, but the underlying sets and graphs are not. We equip dX_d with the standard Gaussian probability measure λd _d, under which the vectorized entries are independent (0,1)N(0,1). This measure is permutation invariant and has positive Lebesgue density everywhere, so it can serve as a reference for any distribution with a Lebesgue density; we choose it because Hermite polynomials form a convenient orthogonal basis. Statistical learning at a fixed size. We consider unsupervised density estimation and supervised regression together. Write Zi=XiZ_i=X_i in the unsupervised setting, where Xi∼i.i.d.μdX_i i.i.d. _d and dμd=fd⋆dλd _d=f_d d _d, and write Zi=(Xi,Yi)Z_i=(X_i,Y_i) in the supervised setting, where (Xi,Yi)∼i.i.d.ρd(X_i,Y_i) i.i.d. _d, Yi∈ℝY_i , the X-marginal is μd _d, and fd⋆(x)=[Y∣X=x]f_d (x)=E[Y X=x]. Let ℋd=L2(λd)H_d=L^2( _d) for density estimation and ℋd=L2(μd)H_d=L^2( _d) for regression, and assume fd⋆∈ℱd⊆ℋdf_d _d _d is the target function to estimate. For the corresponding loss ℓd(Z,f) _d(Z,f), define L^n,d(f)=1n∑i=1nℓd(Zi,f),Ld(f)=[ℓd(Z,f)]. L_n,d(f)= 1n _i=1^n _d(Z_i,f), L_d(f)=E[ _d(Z,f)]. We assume that ℓd _d identifies fd⋆f_d : the target has finite population risk and is the unique minimizer of LdL_d over ℱdF_d as an element of L2L^2. This uniqueness is functional, not parametric. Many parameter values may represent the same minimizing function, so the assumption is fully compatible with overparameterized models. For example, negative log-likelihood identifies the true density, while squared loss identifies the conditional mean whenever [Y2]<∞E[Y^2]<∞; more generally, proper losses identify their associated population targets. Because μd _d or ρd _d is unknown, LdL_d cannot be evaluated directly, and empirical risk minimization provides its data-driven counterpart. Although we state the main formulation for scalar invariant targets, the framework also covers permutation-equivariant vector-valued targets after replacing the invariant spaces and feature counts by their equivariant counterparts; Appendix B.2 gives score matching and denoising as examples. This extension is at the level of function spaces: it requires exact norm-controlled transfer, stable equivariant feature growth, and the corresponding source condition, and its rates are governed by the relevant equivariant feature counts. Permutation invariance. Let SdS_d be the symmetric group. A permutation π∈Sdπ∈ S_d acts on sets by (π⋅X):,j=X:,π−1(j)(π· X)_:,j=X_:,π^-1(j) and on graphs by (π⋅X)a,i,j=Xa,π−1(i),π−1(j)(π· X)_a,i,j=X_a,π^-1(i),π^-1(j). Because elements and nodes are unlabeled, we assume π⋅X=lawXπ· X law=X for density estimation and (π⋅X,Y)=law(X,Y)(π· X,Y) law=(X,Y) for regression. Invariance of μd _d and λd _d, together with uniqueness of the density, gives fd⋆(π⋅x)=fd⋆(x)f_d (π· x)=f_d (x) almost everywhere in the first case; invariance of the conditional law gives the same conclusion for the regression function. Thus ℱdinv≔f∈ℱd:f(π⋅x)=f(x) a.e. for every π∈SdF_d^inv \f _d:f(π· x)=f(x) a.e. for every π∈ S_d\, and the invariant empirical risk minimizer is f^n,dinv∈argminf∈ℱdinvL^n,d(f). f_n,d^inv∈ _f _d^inv L_n,d(f). Appendix B.1 provides the formal background. Exact functional transfer across sizes. Let ℋdinv⊆ℋdH_d^inv _d be the Hilbert space of invariant functions containing ℱdinvF_d^inv, with the corresponding L2L^2 norm ∥⋅∥d\|·\|_d. For d≤Dd≤ D, let Td→D:ℋdinv⟶ℋDinvT_d→ D:H_d^inv _D^inv be a linear operator satisfying Td→D(ℱdinv)⊆ℱDinvT_d→ D(F_d^inv) _D^inv. It maps an entire rule, independently of its parameterization, from size d to size D. We assume coherence, Td→d=IdT_d→ d=Id and TD→E∘Td→D=Td→ET_D→ E T_d→ D=T_d→ E for d≤D≤Ed≤ D≤ E; exact target transfer, Td→Dfd⋆=fD⋆T_d→ Df_d =f_D ; and norm preservation, ‖Td→Df−Td→Dh‖D=‖f−h‖d\|T_d→ Df-T_d→ Dh\|_D=\|f-h\|_d. Thus the targets at different sizes are realizations of a single size-consistent rule, with no transfer mismatch or approximation error between sizes. This consistency assumption is standard and essential in the size-generalization literature (Levin et al., 2025). This is the function-level abstraction of the shared rules used by Deep Sets, GNNs, invariant feature expansions, and graphon representations (Zaheer et al., 2017; Xu et al., 2019; Ruiz et al., 2020; Levin and Díaz, 2024; Levin et al., 2025). The map need not cover every function at size D; it only carries the same rule to the larger domain while preserving its error scale. Without such a connection, size-d data would contain no information about an arbitrary size-D target. Appendices B.3 and C give formal definitions and concrete constructions. A concrete picture. An invariant rule can be viewed as a weighted combination of patterns whose meaning does not change with object size. For a set, a pattern might measure an average feature or an interaction among a few elements; for a graph, it might measure a node or edge feature or the frequency of a small subgraph. Let ψd,j _d,j denote the normalized measurement of pattern j on an object of size d. The same index j refers to the same pattern at every size. A rule ∑jajψd,j _ja_j _d,j is therefore transferred to size D simply by reusing the learned weights: Td→D(∑jajψd,j)=∑jajψD,j.T_d→ D\! ( _ja_j _d,j )= _ja_j _D,j. With a suitable normalization, the squared difference between two rules is exactly the squared difference between their weights. Reusing the weights at a new size therefore preserves prediction error; formally, this is the orthonormal-basis construction and Parseval’s identity. Exact target transfer then has a simple meaning: the true task uses the same pattern weights (aj)j(a_j)_j at every size. Thus, the assumption does not identify arbitrary functions across dimensions; it only identifies the same invariant rule evaluated on different numbers of elements or nodes. Appendices B.3 and C construct these features explicitly for sets and graphs. The statistical objective: generalization across size. Training uses only n samples at size d. At any target size D≥dD≥ d, the learned function is Td→Df^n,dinvT_d→ D f_n,d^inv. Our goal is a guarantee whose sample complexity is independent of both sizes: Dimension-free size generalization. For every accuracy ε>0 >0 and confidence level 1−δ1-δ, find n=n(ε,δ)n=n( ,δ), independent of d and D, such that, with probability at least 1−δ1-δ, supD≥d‖Td→Df^n,dinv−fD⋆‖D2≤ε. _D≥ d \|T_d→ D f_n,d^inv-f_D \|_D^2≤ . The supremum is essential: a single estimator, learned at one size, must remain accurate simultaneously at every larger size. The remainder of the paper characterizes exactly when this is statistically possible and how the required number of samples scales with the regularity of the target. 4 Main Results We now give the dimension-free rates for statistical learning on sets and graphs. The result has two ingredients: representation stability determines how many invariant interactions exist at each order, while target regularity determines how much of the learning task remains beyond that order. Combining them yields a sharp phase transition between nearly parametric and logarithmic size generalization. 4.1 Invariant polynomial coordinates and representation stability Recall the domain dX_d, target class ℱdF_d, and Hilbert space ℋdH_d from Section 3. Thus, ℱd⊆ℋdinvF_d _d^inv, with ℋd=L2(λd)H_d=L^2( _d) for density estimation and ℋd=L2(μd)H_d=L^2( _d) for regression. To organize this infinite-dimensional space, let d,kV_d,k be the span of all invariant polynomials of degree at most k on dX_d. Under the standard completeness conditions stated in the appendix, polynomials are dense in ℋdH_d; averaging over relabelings then makes invariant polynomials dense in ℋdinvH_d^inv. The polynomial description therefore does not assume that the target itself is a polynomial. It supplies a complete, transfer-compatible hierarchy in which degree records interaction complexity: low degrees describe low-order interactions, while increasing k progressively resolves richer dependencies among elements or nodes. An orthonormal basis for d,kV_d,k is obtained by applying Gram–Schmidt in ℋdH_d, with inner product ⟨⋅,⋅⟩d ·,· _d. Orthogonalization changes only the coordinates, not the polynomial span or its dimension. The resulting nested spaces d,0⊆d,1⊆⋯⊆ℋdinvV_d,0 _d,1 ·s _d^inv are compatible with the exact transfer operators, and representation stability controls their complexity uniformly over object size. Specifically, for ∈set,graph X∈\set,graph\, define q(k)≔supd≥1dim(d,k).q_ X(k) _d≥ 1 (V_d,k). For every fixed k, the dimensions increase to a stable value, so the supremum equals that value and bounds every size, including the pre-stable regime (Farb, 2014). For sets X∈ℝr×dX ^r× d, these are multisymmetric polynomials. Hardy–Ramanujan and Meinardus partition asymptotics, detailed in Appendix B.5, give qset(k)=exp(Crkβ+o(kβ)),β=r+1.q_set(k)= \! (C_rk^β+o(k^β) ), β= rr+1. Here Cr=r+1r(rζ(r+1))1/(r+1)C_r= r+1r (rζ(r+1) )^1/(r+1), where ζ is the Riemann zeta function. For attributed graphs X∈ℝr×d×dX ^r× d× d with at least one edge channel, invariant polynomials are indexed by unlabeled attributed multigraph patterns. The enumeration in Appendix B.7 gives qgraph(k)=exp(klogk+Or(kloglogk)).q_graph(k)= \! (k k+O_r(k k) ). For fixed r, the graph feature dimension depends on r only through the lower-order term Or(kloglogk)O_r(k k). Consequently, r does not enter the first-order graph asymptotics or the graph rates below. Both feature counts are uniform in the number of elements or nodes, but the number of interactions grows rapidly with degree and substantially faster for graphs. 4.2 Polynomial and exponential source decay Let ℱd,k=d,kF_d,k=V_d,k for regression and ℱd,k=ℱdinv∩d,kF_d,k=F_d^inv _d,k for density estimation, so density approximants remain nonnegative and normalized. Define the best order-k approximation error and its uniform envelope by Bd(k)≔inff∈ℱd,k‖fd⋆−f‖d2,B(k)≔supd≥1Bd(k).B_d(k) _f _d,k\|f_d -f\|_d^2, B(k) _d≥ 1B_d(k). For regression, the optimizer is the orthogonal projection Πd,kfd⋆ _d,kf_d ; hence B(k)B(k) is the squared energy in coordinates of degree greater than k, uniformly over d. The density definition is its admissible analogue. In both cases, this is an invariant Fourier or spectral source condition: the basis is complete, while coefficient decay quantifies how strongly the target depends on high-order interactions. We use the two source conditions introduced in the paper: polynomial source decay:B(k)≲k−τ,τ>0,exponential source decay:B(k)≲exp(−akν),a,ν>0. array[]lpolynomial source decay:&B(k) k^-τ,&τ>0,\\[2.0pt] exponential source decay:&B(k) (-ak^ν),&a,ν>0. array Polynomial decay is the analogue of finite smoothness: increasingly complex interactions contribute progressively less, but remain present at every order. Exponential decay describes substantially stronger regularity. The exponent ν determines whether this decay is fast enough to overcome the growth of invariant interactions. 4.3 Dimension-free scaling laws For an interaction order k, let fd,k∘f_d,k minimize the population risk over ℱd,kF_d,k, and let f^n,d,kinv f_n,d,k^inv be its empirical counterpart. We impose standard, primitive regularity conditions on this finite-dimensional problem. In orthonormal coordinates on d,kV_d,k, the population approximation satisfies ‖fd,k∘−fd⋆‖d2≲Bd(k)\|f_d,k -f_d \|_d^2 B_d(k); the empirical loss has curvature at least α>0α>0 on the relevant neighborhood; and the centered empirical score at fd,k∘f_d,k is sub-Gaussian with parameter at most σ2σ^2. The constants α and σ are uniform in d and k. Here, curvature means that moving the fitted function by h increases the loss by at least α‖h‖d2/2α\|h\|_d^2/2, up to its linear term; it rules out statistically invisible directions. These conditions are directly checkable for the canonical losses in our framework. For squared-loss regression, Ld(f)−Ld(fd⋆)=‖f−fd⋆‖L2(μd)2,L_d(f)-L_d(f_d )=\|f-f_d \|_L^2( _d)^2, so approximation is exactly measured by Bd(k)B_d(k). Curvature follows from concentration of the empirical Gram matrix, and score concentration follows from sub-Gaussian regression noise and whitened invariant features. For density estimation by negative log-likelihood, the Hessian is uniformly positive and the likelihood is locally equivalent to squared L2(λd)L^2( _d) error when candidate densities are bounded above and away from zero; bounded or sub-Gaussian invariant scores then give the same concentration. Regular proper losses satisfy the analogous calibration and Hessian conditions. Appendix F derives the finite-dimensional estimation bound from these assumptions rather than postulating it. Table 2 compares our dimension-free rates with classical in-domain learning. At a fixed size d, the number of degree-at-most-k invariant polynomial features grows as krdk^rd for sets and krd2k^rd^2 for graphs under our tensor representation; invariance under the finite group SdS_d changes constants but not these exponents. Constants and lower-order factors are suppressed throughout. Table 2: Minimax-optimal in-domain and dimension-free size-generalization rates. Source decay In-domain Sets Graphs Polynomial, k−τk^-τ Sets: n−τ/(τ+rd)n^-τ/(τ+rd) Graphs: n−τ/(τ+rd2)n^-τ/(τ+rd^2) (logn)−τ(r+1)/r( n)^-τ(r+1)/r (logn/loglogn)−τ( n/ n)^-τ Exponential, e−akνe^-ak^ν Both: n−1+o(1)n^-1+o(1) n−1+o(1)n^-1+o(1) if ν>r+1ν> rr+1 n−1+o(1)n^-1+o(1) if ν>1ν>1 At and below the exponential thresholds, the rates interpolate between the two rows of the table. The exact critical and subcritical expressions are derived in Appendix D; the main distinction is whether exponential source decay is fast enough to recover a nearly parametric rate. Theorem 4.1 (Dimension-free scaling laws for sets and graphs). Assume exact isometric transfer, representation stability, compatibility Td→D(ℱd,k)⊆ℱD,kT_d→ D(F_d,k) _D,k, and the uniform loss regularity above. For any fixed confidence level, there are invariant empirical estimators, trained using only size-d data, whose squared error holds simultaneously for every D≥dD≥ d and satisfies the following rates, independently of d and D: (i) If B(k)≲k−τB(k) k^-τ, the rate is (logn)−τ(r+1)/rfor sets,(lognloglogn)−τfor graphs.( n)^-τ(r+1)/r sets, ( n n )^-τ graphs. (i) If B(k)≲e−akνB(k) e^-ak^ν, the set rate, with β=r/(r+1)β=r/(r+1), is n−1+o(1),ν>β,n−a/(a+Cr)+o(1),ν=β,exp[−aCr−ν/β(logn)ν/β(1+o(1))],0<ν<β, casesn^-1+o(1),&ν>β,\\ n^-a/(a+C_r)+o(1),&ν=β,\\ \! [-aC_r^-ν/β( n)^ν/β(1+o(1)) ],&0<ν<β, cases while the graph rate is n−1+o(1)n^-1+o(1) for ν>1ν>1 and exp[−a(lognloglogn)ν(1+o(1))]for 0<ν≤1. \! [-a ( n n )^ν(1+o(1)) ] 0<ν≤ 1. The statements apply to squared-loss regression, regular likelihood density estimation, and other proper losses satisfying the stated calibration, curvature, and score conditions. The theorem is uniform in a strong sense: one event controls the transferred estimator at every larger deployment size, without a union bound over D. Representation stability removes object size from the rate, but it does not make all invariant interactions equally easy to learn. For polynomial source classes, nonnegligible structure persists across the rapidly expanding catalogue of stable interactions, forcing logarithmic convergence. Exponential decay suppresses those high-order interactions fast enough to recover a power law, with different thresholds for sets and graphs because their invariant coordinates grow at different rates. 4.4 Why classical in-domain power laws change In classical fixed-domain nonparametric learning, the number of features up to resolution k often grows polynomially, say q(k)≍ksq(k) k^s. Polynomial source decay B(k)≍k−τB(k) k^-τ then produces the familiar power law n−τ/(τ+s)n^-τ/(τ+s). Size generalization on sets and graphs is different. Uniformity over every larger size exposes all invariant interactions, whose stable counts grow as exp(Crkr/(r+1))andexp(klogk), (C_rk^r/(r+1)) (k k), respectively. Consequently, the same polynomial source decay yields only logarithmic convergence in n. A power law is recovered only when the interaction tail has sufficiently fast exponential source decay. This is a statistical effect: it remains even when transfer is exact and optimization is ideal. To determine whether these rates reflect a particular estimator or an inherent limit of the problem, let (B) F_ X(B) contain all size-consistent targets of type ∈set,graph X∈\set,graph\ with source envelope B. We compare against every measurable procedure, including procedures that do not use polynomial truncation and are not themselves invariant. Its worst-case risk is ℜn(,B)≔inf^supd≥1sup⋆∈(B)[supD≥d‖f^D−fD⋆‖D2]. R_n( X,B) _ f _d≥ 1 _ f ∈ F_ X(B)E\! [ _D≥ d\| f_D-f_D \|_D^2 ]. For the lower bound, the source class must genuinely contain the invariant directions counted by representation stability. Concretely, at every order k, we require a stable-size regression or density submodel with q(k)q_ X(k) orthogonal local perturbations whose neighboring data distributions have quadratic KL divergence. Gaussian-noise regression and bounded local density or exponential-family perturbations satisfy this condition; Appendix E states and verifies the precise construction. Theorem 4.2 (Minimax optimality). Under the preceding local richness condition, every rate in Theorem 4.1 is minimax optimal up to constants and the displayed lower-order factors. In particular, for polynomial source decay, ℜn(set,k−τ)≍(logn)−τ(r+1)/r,ℜn(graph,k−τ)≍(lognloglogn)−τ. R_n(set,k^-τ) ( n)^-τ(r+1)/r, R_n(graph,k^-τ) ( n n )^-τ. For exponential source decay, the minimax risks have the same supercritical, critical, and subcritical regimes stated in Theorem 4.1. These lower bounds hold already at a suitable stable training size and therefore continue to hold when the loss takes a supremum over all D≥dD≥ d. The theorem rules out improvements by a different architecture, regularizer, optimization method, or transfer rule: the infimum in ℜn R_n ranges over all estimators. It also explains the role of exact transfer. Exact transfer removes cross-size mismatch, but it cannot create information about the many statistically distinguishable invariant directions that remain uncertain from n observations. The logarithmic regime is therefore not an artifact of polynomial regression or of the proof technique; it is the optimal statistical behavior of the entire source class. Corollary 4.3 (Exponential separation in sample complexity). Fix the confidence level and suppose B(k)≍k−τB(k) k^-τ. Up to constants and lower-order factors, achieving squared error at most ε at a fixed size requires nin(ε)=ε−(τ+rd)/τ,sets,ε−(τ+rd2)/τ,graphs,n_in( )= cases ^-(τ+rd)/τ,&sets,\\ ^-(τ+rd^2)/τ,&graphs, cases whereas uniform size generalization requires nsize(ε)=exp(Θ(ε−rτ(r+1))),sets,exp(Θ(ε−1/τlog(1/ε))),graphs.n_size( )= cases \! ( \! ( ^- rτ(r+1) ) ),&sets,\\[5.0pt] \! ( \! ( ^-1/τ (1/ ) ) ),&graphs. cases Thus the same polynomial source class has polynomial sample complexity in-domain but exponential sample complexity when one estimator must transfer uniformly to all larger sizes. 4.5 Discussion Our results are stated at the level of function classes rather than a particular neural parameterization. Consequently, they are compatible with permutation-equivariant graph architectures, including graph Transformers, when a permutation-invariant readout produces a graph-level prediction. Such an architecture can parameterize an estimator in our graph setting, but its symmetry alone does not imply the rates above. The cross-size target compatibility, exact norm-controlled transfer, stable feature growth, and source-decay conditions must still be verified. We therefore do not claim that every graph Transformer size-generalizes at these rates; rather, the theorems characterize the statistical behavior of those invariant graph-learning problems that satisfy the stated conditions. This distinction separates three properties that are often conflated. First, an architecture may be applicable to objects of different sizes. Second, a fixed predictor may be transferable, meaning that its outputs remain stable as size changes. Third, a predictor learned from finite data may achieve statistical size generalization, meaning that its error at unseen sizes decreases at a controlled rate as the number of training samples grows. The first two properties make cross-size prediction possible, but neither determines its sample complexity. Our results address the third property. The minimax bounds also clarify what would be required to improve the rates. In the polynomial source class, no alternative architecture, regularizer, optimizer, or transfer rule can uniformly replace the logarithmic rate by a power law. Faster rates are possible only by imposing additional structure that reduces the effective class, such as faster source decay or a smaller family of transferable interactions. Thus the exponential separation is not a statement that all individual tasks are hard; it states that polynomial source decay alone is too weak to guarantee efficient size generalization uniformly over the class. Finally, exact transfer isolates the statistical difficulty studied here by removing cross-size approximation mismatch. With approximate transfer, an additional error term would remain even with unlimited data. Likewise, problems with different symmetries require their own stable feature counts and need not exhibit the same thresholds. These are natural directions for extending the present theory, but they are distinct from the finite-sample phenomenon characterized by our results. Altogether, the main message of this paper is: Exact transfer enables size generalization, but target regularity determines its statistical efficiency. Fast exponential source decay yields nearly parametric rates, whereas polynomial decay yields minimax-optimal logarithmic rates. 5 Conclusion We developed a statistical theory of size generalization for supervised regression and unsupervised density estimation on sets and graphs. By combining exact transfer, representation stability, and source decay in invariant polynomial coordinates, we obtained rates that are uniform over both the training and deployment sizes. Polynomial source decay leads to minimax-optimal logarithmic rates, producing an exponential separation from classical in-domain power laws. Sufficiently fast exponential source decay overcomes invariant feature growth and recovers nearly parametric size generalization, with sharp thresholds that differ between sets and graphs. These results show that architectural transferability alone does not determine the statistical efficiency of size generalization. The decisive interaction is between the growth of transferable invariant representations and the decay of high-order structure in the target. The matching minimax bounds establish that this phase transition is intrinsic rather than an artifact of the estimator or analysis. AI use statement Large language model tools (ChatGPT 5.6 Sol and Claude Fable 5.1) were used primarily for copyediting, including improvements to grammar, wording, clarity, and LaTeX presentation. The research direction, core ideas, theoretical results, and experimental design are original contributions of the authors. The authors carefully reviewed and verified all technical content and take full responsibility for the final manuscript. References Atzmon et al. (2022) M. Atzmon, K. Nagano, S. Fidler, S. Khamis, and Y. Lipman Frame averaging for equivariant shape space learning. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Cited by: Appendix A. Bevilacqua et al. (2021) B. Bevilacqua, Y. Zhou, and B. Ribeiro Size-invariant graph representations for graph classification extrapolations. In Int. Conference on Machine Learning (ICML), Cited by: §1. Bloem-Reddy and Teh (2020) B. Bloem-Reddy and Y. W. Teh Probabilistic symmetries and invariant neural networks. Journal of Machine Learning Research 21 (90), p. 1–61. Cited by: Appendix A. Bogatskiy et al. (2020) A. Bogatskiy, B. Anderson, J. Offermann, M. Roussi, D. Miller, and R. Kondor Lorentz group equivariant neural network for particle physics. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Bongini et al. (2021) P. Bongini, M. Bianchini, and F. Scarselli Molecular generative graph neural networks for drug discovery. Neurocomputing 450, p. 242–252. Cited by: Appendix A. Bronstein et al. (2021) M. M. Bronstein, J. Bruna, T. Cohen, and P. Veličković Geometric deep learning: grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478. Cited by: §1. Buffelli et al. (2022) D. Buffelli, P. Liò, and F. Vandin Sizeshiftreg: a regularization method for improving size-generalization in graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: Appendix A. Cai and Wang (2022) C. Cai and Y. Wang Convergence of invariant graph networks. In Int. Conference on Machine Learning (ICML), p. 2457–2484. Cited by: §2. Caponnetto and De Vito (2007) A. Caponnetto and E. De Vito Optimal rates for the regularized least-squares algorithm. Foundations of Computational mathematics 7 (3), p. 331–368. Cited by: Appendix A. Chen et al. (2023) Z. Chen, M. Katsoulakis, L. Rey-Bellet, and W. Zhu Sample complexity of probability divergences under group symmetry. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Chu et al. (2023) X. Chu, Y. Jin, X. Wang, S. Zhang, Y. Wang, W. Zhu, and H. Mei Wasserstein barycenter matching for graph size generalization of message passing neural networks. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Chuang and Jegelka (2022) C. Chuang and S. Jegelka Tree mover’s distance: bridging graph metrics and stability of graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: Appendix A. Diaconis and Janson (2008) P. Diaconis and S. Janson Graph limits and exchangeable random graphs. Rendiconti di Matematica, Serie VII 28, p. 33–61. Cited by: §B.3. Díaz et al. (2025) M. Díaz, D. Drusvyatskiy, J. Kendrick, and R. R. Thomas Invariant kernels: rank stabilization and generalization across dimensions. arXiv preprint arXiv:2502.01886. Cited by: §1, §2. Dym et al. (2024) N. Dym, H. Lawrence, and J. W. Siegel Equivariant frames and the impossibility of continuous canonicalization. Cited by: Appendix A. Elesedy (2021) B. Elesedy Provably strict generalisation benefit for invariance in kernel methods. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: Appendix A. Farb (2014) B. Farb Representation stability. arXiv preprint arXiv:1404.4065. Cited by: §1, §2, §4.1. Garg et al. (2020) V. Garg, S. Jegelka, and T. Jaakkola Generalization and representational limits of graph neural networks. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Herbst and Jegelka (2025) D. Herbst and S. Jegelka Higher-order graphon neural networks: approximation and cut distance. In Int. Conference on Learning Representations (ICLR), Cited by: §2. Huang et al. (2024) Z. Huang, Q. Yang, D. Zhou, and Y. Yan Enhancing size generalization in graph neural networks through disentangled representation learning. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Ju et al. (2023) H. Ju, D. Li, A. Sharma, and H. R. Zhang Generalization in graph neural networks: improved pac-bayesian bounds on graph diffusion. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), Cited by: Appendix A. Kaba et al. (2023) S. Kaba, A. K. Mondal, Y. Zhang, Y. Bengio, and S. Ravanbakhsh Equivariance with learned canonicalization functions. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Keriven et al. (2020) N. Keriven, A. Bietti, and S. Vaiter Convergence and stability of graph convolutional networks on large random graphs. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 33, p. 21512–21523. Cited by: §1, §2. Le and Jegelka (2023) T. Le and S. Jegelka Limits, approximation and size transferability for gnns on sparse graphs via graphops. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. Levie et al. (2021) R. Levie, W. Huang, L. Bucci, M. Bronstein, and G. Kutyniok Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research 22 (272), p. 1–59. Cited by: §1, §2. Levie (2023) R. Levie A graphon-signal analysis of graph neural networks. Advances in Neural Information Processing Systems 36, p. 64482–64525. Cited by: Appendix A. Levin and Chandrasekaran (2023) E. Levin and V. Chandrasekaran Free descriptions of convex sets. arXiv preprint arXiv:2307.04230. Cited by: §1, §2. Levin and Chandrasekaran (2026) E. Levin and V. Chandrasekaran Limits of weighted graphs via random quotients. arXiv:2512.23149. Cited by: §2. Levin and Díaz (2024) E. Levin and M. Díaz Any-dimensional equivariant neural networks. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), Cited by: §B.3, §1, §2, §3. Levin et al. (2025) E. Levin, Y. Ma, M. Díaz, and S. Villar On transferring transferability: towards a theory for size generalization. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1, §2, §3, §3. Li et al. (2023) X. Li, L. Sun, M. Ling, and Y. Peng A survey of graph neural network based recommendation in social networks. Neurocomputing 549, p. 126441. Cited by: Appendix A. Liao et al. (2020) R. Liao, R. Urtasun, and R. Zemel A pac-bayesian approach to generalization bounds for graph neural networks. In Int. Conference on Learning Representations (ICLR), Cited by: Appendix A. Lin et al. (2024) Y. Lin, J. Helwig, S. Gui, and S. Ji Equivariance via minimal frame averaging for more symmetries and efficiency. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Ma et al. (2024) G. Ma, Y. Wang, D. Lim, S. Jegelka, and Y. Wang A canonicalization perspective on invariant and equivariant learning. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: Appendix A. Maehara and NT (2021) T. Maehara and H. NT Learning on random balls is sufficient for estimating (some) graph parameters. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. Maron et al. (2019) H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman Invariant and equivariant graph networks. In Int. Conference on Learning Representations (ICLR), Cited by: Appendix A. Maskey et al. (2025) S. Maskey, G. Kutyniok, and R. Levie Generalization bounds for message passing networks on mixture of graphons. SIAM Journal on Mathematics of Data Science 7 (2), p. 802–825. Cited by: Appendix A. Maskey et al. (2023) S. Maskey, R. Levie, and G. Kutyniok Transferability of graph neural networks: an extended graphon approach. Applied and Computational Harmonic Analysis 63, p. 48–83. Cited by: §2. Maskey et al. (2022) S. Maskey, R. Levie, Y. Lee, and G. Kutyniok Generalization analysis of message passing neural networks on large random graphs. Advances in neural information processing systems 35, p. 4805–4817. Cited by: Appendix A. Morris et al. (2023) C. Morris, F. Geerts, J. Tönshoff, and M. Grohe Wl meet vc. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Nguyen et al. (2024) Q. T. Nguyen, L. Schatzki, P. Braccia, M. Ragone, P. J. Coles, F. Sauvage, M. Larocca, and M. Cerezo Theory for equivariant quantum neural networks. PRX Quantum 5 (2), p. 020328. Cited by: Appendix A. Petrache and Trivedi (2023) M. Petrache and S. Trivedi Approximation-generalization trade-offs under (approximate) group equivariance. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: Appendix A. Phan et al. (2025) T. V. Phan, G. A. Kevrekidis, S. Villar, Y. G. Kevrekidis, and J. M. Bello-Rivas Towards coordinate-and dimension-agnostic machine learning for partial differential equations. arXiv preprint arXiv:2505.16549. Cited by: §2. Puny et al. (2022) O. Puny, M. Atzmon, E. J. Smith, I. Misra, A. Grover, H. Ben-Hamu, and Y. Lipman Frame averaging for invariant and equivariant network design. In Int. Conference on Learning Representations (ICLR), Cited by: Appendix A. Rauchwerger et al. (2025) L. Rauchwerger, S. Jegelka, and R. Levie Generalization, expressivity, and universality of graph neural networks on attributed graphs. In Int. Conference on Learning Representations (ICLR), Cited by: Appendix A. Ruiz et al. (2023) L. Ruiz, L. F. Chamon, and A. Ribeiro Transferability properties of graph neural networks. IEEE Transactions on Signal Processing 71, p. 3474–3489. Cited by: §2. Ruiz et al. (2020) L. Ruiz, L. Chamon, and A. Ribeiro Graphon neural networks and the transferability of graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 33, p. 1702–1712. Cited by: §B.3, §1, §2, §3. Satorras et al. (2021) V. G. Satorras, E. Hoogeboom, and M. Welling E(n) equivariant graph neural networks. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Scarselli et al. (2008) F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini The graph neural network model. IEEE transactions on neural networks 20 (1), p. 61–80. Cited by: §1. Scarselli et al. (2018) F. Scarselli, A. C. Tsoi, and M. Hagenbuchner The Vapnik–Chervonenkis dimension of graph and recursive neural networks. Neural Networks 108, p. 248–259. Cited by: Appendix A. Shumaylov et al. (2025) Z. Shumaylov, P. Zaika, J. Rowbottom, F. Sherry, M. Weber, and C. Schönlieb Lie algebra canonicalization: equivariant neural operators under arbitrary Lie groups. In Int. Conference on Learning Representations (ICLR), Cited by: Appendix A. Soleymani et al. (2026a) A. Soleymani, B. Tahmasebi, P. Jaillet, and S. Jegelka A unified framework for statistical testing of invariance. In The ICML 2026 Workshop on Hypothesis Testing, Cited by: Appendix A. Soleymani et al. (2026b) A. Soleymani, B. Tahmasebi, P. Jaillet, and S. Jegelka Efficient learning and symmetry discovery under exact invariances. In Conference on Learning Theory (COLT), Cited by: Appendix A. Soleymani et al. (2025a) A. Soleymani, B. Tahmasebi, S. Jegelka, and P. Jaillet A robust kernel statistical test of invariance: detecting subtle asymmetries. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), Cited by: Appendix A. Soleymani et al. (2025b) A. Soleymani, B. Tahmasebi, S. Jegelka, and P. Jaillet Learning with exact invariances in polynomial time. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Tahmasebi and Jegelka (2023) B. Tahmasebi and S. Jegelka The exact sample complexity gain from invariances for kernel regression. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: Appendix A. Tahmasebi and Jegelka (2024) B. Tahmasebi and S. Jegelka Sample complexity bounds for estimating probability divergences under invariances. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Tahmasebi and Jegelka (2025a) B. Tahmasebi and S. Jegelka Generalization bounds for canonicalization: a comparative study with group averaging. In Int. Conference on Learning Representations (ICLR), Cited by: Appendix A. Tahmasebi and Jegelka (2025b) B. Tahmasebi and S. Jegelka Regularity in canonicalized models: a theoretical perspective. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), Cited by: Appendix A. Tahmasebi et al. (2023) B. Tahmasebi, D. Lim, and S. Jegelka The power of recursion in graph neural networks for counting substructures. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), Cited by: Appendix A. Tahmasebi et al. (2026) B. Tahmasebi, M. Weber, and S. Jegelka Data augmentation: a fourier analysis perspective. In Conference on Learning Theory (COLT), Cited by: Appendix A. Tahmasebi and Weber (2026a) B. Tahmasebi and M. Weber Achieving approximate symmetry is exponentially easier than exact symmetry. In Int. Conference on Learning Representations (ICLR), Cited by: Appendix A. Tahmasebi and Weber (2026b) B. Tahmasebi and M. Weber Adaptive symmetry discovery for dynamical system identification. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Tahmasebi and Weber (2026c) B. Tahmasebi and M. Weber Sparse data augmentation for optimization with provable guarantees. In IEEE Conference on Decision and Control (CDC), Cited by: Appendix A. Vasileiou et al. (2025a) A. Vasileiou, B. Finkelshtein, F. Geerts, R. Levie, and C. Morris Covered forest: fine-grained generalization analysis of graph neural networks. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Vasileiou et al. (2025b) A. Vasileiou, S. Jegelka, R. Levie, and C. Morris Survey on generalization theory for graph neural networks. arXiv preprint arXiv:2503.15650. Cited by: Appendix A. Veličković et al. (2025) P. Veličković, C. Perivolaropoulos, F. Barbero, and R. Pascanu Softmax is not enough (for sharp size generalisation). In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Wagstaff et al. (2019) E. Wagstaff, F. Fuchs, M. Engelcke, I. Posner, and M. A. Osborne On the limitations of representing functions on sets. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Wang et al. (2022) D. Wang, R. Walters, and R. Platt SO(2)SO(2)-Equivariant reinforcement learning. In Int. Conference on Learning Representations (ICLR), Cited by: Appendix A. Wang et al. (2021) R. Wang, R. Walters, and R. Yu Incorporating symmetry into deep dynamics models for improved generalization. In Int. Conference on Learning Representations (ICLR), Cited by: Appendix A. Wang et al. (2025) Z. Wang, J. Cervino, and A. Ribeiro A manifold perspective on the statistical generalization of graph neural networks. In Int. Conference on Machine Learning (ICML), Cited by: Appendix A. Weber (2025) M. Weber Geometric machine learning. Wiley Online Library. Cited by: §1. Xu et al. (2019) K. Xu, W. Hu, J. Leskovec, and S. Jegelka How powerful are graph neural networks?. In Int. Conference on Learning Representations (ICLR), Cited by: Appendix A, §B.3, §3. Yehudai et al. (2021) G. Yehudai, E. Fetaya, E. Meirom, G. Chechik, and H. Maron From local structures to size generalization in graph neural networks. In Int. Conference on Machine Learning (ICML), Cited by: §1. Zaheer et al. (2017) M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. J. Smola Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: Appendix A, §B.3, §1, §3. Zhang et al. (2025) H. Zhang, Y. Li, W. Lu, and Q. Lin Optimal rates of kernel ridge regression under source condition in large dimensions. Journal of Machine Learning Research 26 (219), p. 1–63. Cited by: Appendix A. Zweig and Bruna (2021) A. Zweig and J. Bruna A functional perspective on learning symmetric functions with neural networks. In Int. Conference on Machine Learning (ICML), Cited by: §2. Appendix Contents 1 Introduction 2 Related Work 3 Problem Statement 4 Main Results 4.1 Invariant polynomial coordinates and representation stability 4.2 Polynomial and exponential source decay 4.3 Dimension-free scaling laws 4.4 Why classical in-domain power laws change 4.5 Discussion 5 Conclusion References A Additional Related Work B Function-Level Symmetry, Statistical Learning, and Transfer B.1 Group actions on data and functions B.2 Examples of statistical learning objectives B.3 Exact functional transfer across sizes B.4 Invariant polynomial function spaces B.5 Set-valued data and multisymmetric polynomials B.6 Hermite features for set-valued data B.7 Attributed graphs C Concrete Exact Transfers for Sets and Graphs C.1 Sets C.2 Attributed graphs C.3 What the exact-transfer assumption asserts D Proof of Theorem D.1 Finite-dimensional estimation and transfer D.2 Set rates D.3 Graph rates E Proof of Theorem E.1 Minimax risk and local invariant submodels E.2 Assouad lower bound E.3 Evaluation of the lower bound F Auxiliary finite-dimensional estimation bound F.1 Restricted gradients on the invariant model F.2 Proof of the estimation bound F.3 Proof of the transfer bound G Equivariant Field Specialization for Sets H Equivariant Field Specialization for Graphs I Experiments I.1 Subgraph counting I.2 Equivariant field transfer on weighted graphs J Notation Appendix A Additional Related Work Learning under invariances. Symmetry and invariance are central principles in geometric machine learning. Deep Sets provide a classical architecture for sets (Zaheer et al., 2017), while graph neural networks and higher-order invariant and equivariant architectures are widely used for graphs (Xu et al., 2019; Maron et al., 2019; Satorras et al., 2021). Probabilistic symmetry provides a distributional foundation for invariant and equivariant models (Bloem-Reddy and Teh, 2020), while complementary work studies limitations of set representations (Wagstaff et al., 2019) and the ability of graph networks to count substructures (Tahmasebi et al., 2023). Beyond architectures that hard-code invariance, architecture-agnostic approaches include canonicalization (Ma et al., 2024; Kaba et al., 2023; Dym et al., 2024; Shumaylov et al., 2025; Tahmasebi and Jegelka, 2025b) and frame averaging (Puny et al., 2022; Atzmon et al., 2022; Lin et al., 2024). Although symmetry must be discovered in some settings, either adaptively (Tahmasebi and Weber, 2026b) or via statistical tests (Soleymani et al., 2025a; Soleymani et al., 2026a), here we focus on the case of known symmetries. Applications of learning under invariances span reinforcement learning (Wang et al., 2022), physics (Bogatskiy et al., 2020; Nguyen et al., 2024), drug discovery (Bongini et al., 2021), and social networks (Li et al., 2023). Our work is complementary to these modeling approaches: rather than proposing a new architecture, we study when invariant statistical estimation can transfer across dimensions. Methods and limitations for size generalization. Beyond the transferability theory discussed in the main text, several works develop model-specific approaches to graph size generalization through Wasserstein barycenter matching, size-shift regularization, or disentangled representations (Chu et al., 2023; Buffelli et al., 2022; Huang et al., 2024). Graph metrics have also been used to relate structural shifts to GNN stability (Chuang and Jegelka, 2022). Other results identify architectural limitations to sharp size generalization (Veličković et al., 2025) or derive graph-size-dependent statistical guarantees from a manifold perspective (Wang et al., 2025). These works clarify mechanisms that help or hinder generalization across sizes. Our focus is instead on size-uniform sample complexity and matching minimax rates for invariant estimation. Generalization and sample complexity under symmetry. The statistical benefits of symmetry have been widely studied in learning theory. Prior work has shown that invariance can reduce sample complexity in supervised learning and related estimation problems (Tahmasebi and Jegelka, 2023; Elesedy, 2021; Wang et al., 2021; Petrache and Trivedi, 2023; Tahmasebi and Jegelka, 2025a), with extensions to estimating probability divergences (Chen et al., 2023; Tahmasebi and Jegelka, 2024). More broadly, the study of symmetry and scaling laws extends to comparisons between approximate and exact symmetry (Tahmasebi and Weber, 2026a), data augmentation via Fourier analysis on groups (Tahmasebi et al., 2026; Tahmasebi and Weber, 2026c), and statistical-computational trade-offs (Soleymani et al., 2025b; Soleymani et al., 2026b). Generalization bounds for graph neural networks have also been developed using Rademacher complexity (Garg et al., 2020), VC dimension (Scarselli et al., 2018; Morris et al., 2023), and PAC-Bayesian analysis (Liao et al., 2020; Ju et al., 2023). Further work studies GNN generalization and transfer (Maskey et al., 2022; Maskey et al., 2025; Levie, 2023; Vasileiou et al., 2025a; Rauchwerger et al., 2025); see also the survey of Vasileiou et al. (2025b). Our contribution differs by focusing on invariant estimation across changing dimensions, with explicit dimension-uniform rates and phase transitions driven by stable feature complexity. Source conditions and optimal rates. Classical analyses of regularized least squares derive optimal statistical rates under source and capacity conditions (Caponnetto and De Vito, 2007). More recent work establishes exact and minimax rates for kernel ridge regression under source conditions in large dimensions (Zhang et al., 2025). These results concern fixed domains or joint asymptotics of sample size and ambient dimension. We instead study transfer from one object size to all larger sizes and determine when the resulting rates can be uniform over both the training and deployment sizes. Appendix B Function-Level Symmetry, Statistical Learning, and Transfer This appendix formalizes the function-level framework of Section 3. It explains why unlabeled set and graph laws yield invariant density and regression targets, records representative losses under the unified observation notation, and defines exact transfer through coherent linear isometries. It then develops the stable invariant function spaces used in the rate calculations. B.1 Group actions on data and functions A group G acts on a measurable space X if e⋅x=x,g⋅(h⋅x)=(gh)⋅x,e· x=x, g·(h· x)=(gh)· x, for every g,h∈Gg,h∈ G and x∈x . This action induces a linear action on real-valued functions f:→ℝf:X by pullback: (g⋅f)(x)≔f(g−1⋅x).(g· f)(x) f(g^-1· x). A function is G-invariant when g⋅f=fg· f=f for every g∈Gg∈ G, equivalently, f(g⋅x)=f(x)for every g∈G,x∈.f(g· x)=f(x) every g∈ G,\ x . For sets and graphs of size d, the group is G=SdG=S_d, acting by relabeling elements or nodes as specified in Section 3. A probability distribution μ on X is G-invariant if g⋅X=lawXfor every g∈G.g· X law=X every g∈ G. Equivalently, μ(g−1A)=μ(A)μ(g^-1A)=μ(A) for all measurable sets A⊆A . Density targets. Suppose μ admits a density f⋆f with respect to a G-invariant reference measure λ. For every measurable A, ∫Af⋆λ=μ(A)=μ(g−1A)=∫Af⋆(g−1⋅x)λ(x). _Af \,dλ=μ(A)=μ(g^-1A)= _Af (g^-1· x)\,dλ(x). Hence f⋆(g⋅x)=f⋆(x)f (g· x)=f (x) for λ-almost every x. Thus an unlabeled set or graph distribution has an invariant density whenever its density is expressed relative to an invariant reference measure. Regression targets. Let ρ be a joint distribution on ×ℝX×R satisfying (g⋅X,Y)=law(X,Y).(g· X,Y) law=(X,Y). Then the conditional law of Y given X=xX=x agrees with that given X=g⋅xX=g· x, up to the usual almost-sure choice of a conditional version. Consequently, the regression function f⋆(x)=[Y∣X=x]f (x)=E[Y X=x] admits a G-invariant version. Invariant risk minimization. Let ℱF be a function class closed under the induced G-action. A population risk L:ℱ→ℝL:F is G-invariant if L(g⋅f)=L(f)L(g· f)=L(f). If the minimizer is unique, it is necessarily invariant. If the minimizer is not unique, ℱF is convex, and L is convex, then group averaging produces an invariant minimizer: f¯(x)≔∫G(g⋅f)(x)dηG(g), f(x) _G(g· f)(x)\,d _G(g), where ηG _G is the uniform measure for finite groups and Haar probability measure for compact groups. Indeed, Jensen’s inequality and invariance give L(f¯)≤∫GL(g⋅f)dηG(g)=L(f).L( f)≤ _GL(g· f)\,d _G(g)=L(f). This argument takes place entirely in function space and requires no action on a parameterization. Accordingly, uniqueness means uniqueness as an L2L^2 function, up to almost-everywhere equality; it is compatible with many parameter values representing that same function. B.2 Examples of statistical learning objectives Recall the unified observation Zi=XiZ_i=X_i for unsupervised learning and Zi=(Xi,Yi)Z_i=(X_i,Y_i) for supervised learning. In either case, L^n,d(f)=n−1∑i=1nℓd(Zi,f) L_n,d(f)=n^-1 _i=1^n _d(Z_i,f) estimates Ld(f)=[ℓd(Z,f)]L_d(f)=E[ _d(Z,f)]. The formulation includes the following standard tasks. Unsupervised statistical learning: density estimation. Let ℱd⊆L2(λd)F_d L^2( _d) be a class of nonnegative functions satisfying ∫fdλd=1 f\,d _d=1. Since μd=fd⋆λd _d=f_d _d, the negative log-likelihood loss ℓd(x,f)=−logf(x) _d(x,f)=- f(x) has population risk Ld(f)=X∼μd[−logf(X)].L_d(f)=E_X _d[- f(X)]. This risk is uniquely minimized by fd⋆f_d , up to λd _d-almost-everywhere equality, whenever fd⋆∈ℱdf_d _d and the risk is finite. Restricting to ℱdinvF_d^inv gives invariant maximum likelihood directly at the function level. Supervised statistical learning: regression. For real-valued labels, squared loss gives ℓd(x,y,f)=(y−f(x))2,fd⋆(x)=[Y∣X=x]. _d(x,y,f)=(y-f(x))^2, f_d (x)=E[Y X=x]. More generally, any proper supervised loss may be used when its population minimizer is the desired conditional target. If relabeling X does not change the joint law of (X,Y)(X,Y), the target is invariant. Score matching and denoising. The scalar formulation is not tied to likelihood: proper scoring rules, density-ratio objectives, and variational losses also apply whenever their population minimizer identifies fd⋆f_d . Score matching and denoising instead estimate a vector-valued field, such as ∇logfd⋆∇ f_d , in L2(λd,ℝmd)L^2( _d;R^m_d), where md=rdm_d=rd for sets and md=rd2m_d=rd^2 for graphs. Invariance of the density makes its score permutation equivariant. Replacing invariant scalar spaces by the corresponding equivariant vector spaces leaves the transfer, truncation, and estimation arguments unchanged, provided the same representation-stability and source-decay conditions hold. B.3 Exact functional transfer across sizes For density estimation let ℋd=L2(λd)H_d=L^2( _d), and for regression let ℋd=L2(μd)H_d=L^2( _d). In either case, let ℋdinvH_d^inv be its invariant subspace, with inner product ⟨⋅,⋅⟩d ·,· _d and norm ∥⋅∥d\|·\|_d. An exact transfer system is a collection of linear maps Td→D:ℋdinv⟶ℋDinv,d≤D,T_d→ D:H_d^inv _D^inv, d≤ D, satisfying the following three properties: (i) coherence: Td→d=IdT_d→ d=Id and TD→ETd→D=Td→ET_D→ ET_d→ D=T_d→ E; (i) isometry: ⟨Td→Df,Td→Dh⟩D=⟨f,h⟩d T_d→ Df,T_d→ Dh _D= f,h _d; (i) target compatibility: Td→Dfd⋆=fD⋆T_d→ Df_d =f_D . The isometry identity implies ‖Td→Df−Td→Dh‖D=‖f−h‖d.\|T_d→ Df-T_d→ Dh\|_D=\|f-h\|_d. The map need not reach every function at the larger size; it only identifies the size-stable subspace carrying the shared rule. These assumptions express the structure needed to learn at one size and make a statistical claim at another. Without target compatibility, the unseen target fD⋆f_D is not identifiable from size-d observations. Without norm control, transfer could arbitrarily amplify a small source-size error. Isometry rules out that artifact and makes errors comparable across sizes. For score matching or denoising, the same definition applies to the corresponding equivariant vector-valued spaces. Stable invariant features. Suppose ψd,jj≥1\ _d,j\_j≥ 1 and ψD,jj≥1\ _D,j\_j≥ 1 are corresponding orthonormal invariant features. Define Td→Dψd,j=ψD,jT_d→ D _d,j= _D,j and extend linearly and continuously. Then, for every square-summable sequence (aj)j(a_j)_j, Td→D(∑jajψd,j)=∑jajψD,j,‖Td→D∑jajψd,j‖D2=∑jaj2.T_d→ D\! ( _ja_j _d,j )= _ja_j _D,j, \|T_d→ D _ja_j _d,j \|_D^2= _ja_j^2. Thus transfer preserves the learned rule and its error exactly. This construction underlies the stable polynomial and Hermite classes below. It is also the function-space abstraction of weight sharing in Deep Sets and GNNs: the computation is instantiated on a new number of elements or nodes, but the rule itself is unchanged (Zaheer et al., 2017; Xu et al., 2019; Levin and Díaz, 2024). Common ambient objects. Exact transfer also arises when all finite-size functions are realizations of a single rule on a common limit object. Mean embeddings and normalized empirical measures provide such objects for sets. Graphons and normalized motif functionals provide them for dense graphs (Ruiz et al., 2020; Diaconis and Janson, 2008). Appendix C gives explicit set and graph constructions, including replication, graph blow-ups, and shared Deep Sets and GNN rules. B.4 Invariant polynomial function spaces A central example is a finite-dimensional space of polynomial functions. Let VdV_d be a finite-dimensional vector space on which GdG_d acts linearly, and let d,kP_d,k be the space of homogeneous degree-k polynomial functions on VdV_d. The induced action on functions is (g⋅f)(x)≔f(g−1⋅x).(g· f)(x) f(g^-1· x). The invariant homogeneous polynomial space is d,kGd≔f∈d,k:g⋅f=f for all g∈Gd.P_d,k^G_d \f _d,k:g· f=f for all g∈ G_d\. For density estimation, completeness follows from the Hermite basis of L2(λd)L^2( _d). For regression, we assume the standard polynomial-completeness condition in L2(μd)L^2( _d), which holds, for example, under suitable moment determinacy or exponential-moment conditions. Averaging polynomial approximants over SdS_d then proves density of invariant polynomials in ℋdinvH_d^inv. For finite groups, the dimension of the invariant subspace can be expressed using characters. If ϱd,k _d,k is the representation of GdG_d on d,kP_d,k (i.e., the collection of matrices corresponding to the action) and χd,k(g)=tr(ϱd,k(g)) _d,k(g)=tr( _d,k(g)) is its character, then dimd,kGd=1|Gd|∑g∈Gdχd,k(g). _d,k^G_d= 1|G_d| _g∈ G_d _d,k(g). Equivalently, if PGdP_G_d denotes the group-averaging projection PGdf=1|Gd|∑g∈Gdg⋅f,P_G_df= 1|G_d| _g∈ G_dg· f, then dimd,kGd=tr(PGd). _d,k^G_d=tr(P_G_d). For compact groups, the finite average is replaced by Haar integration. Representation stability is the phenomenon that these invariant function-space dimensions stabilize as d grows. This stabilization is the algebraic mechanism behind dimension-uniform learning in our setting. B.5 Set-valued data and multisymmetric polynomials Consider set-valued data with d elements in ℝrR^r. We represent the set as X=(x1,…,xd)∈(ℝr)d,xi=(xi,1,…,xi,r)∈ℝr.X=(x_1,…,x_d)∈(R^r)^d, x_i=(x_i,1,…,x_i,r) ^r. The symmetric group SdS_d acts by permuting the d elements: π⋅X=(xπ−1(1),…,xπ−1(d)).π· X=(x_π^-1(1),…,x_π^-1(d)). The corresponding invariant polynomials are called multisymmetric polynomials: they are polynomials in the drdr variables xi,ax_i,a that are invariant under permutations of the block index i. Let d,r,kSdP_d,r,k^S_d denote the space of homogeneous degree k multisymmetric polynomials. A monomial is described by a collection of multi-indices αi=(αi,1,…,αi,r)∈ℕr,1≤i≤d, _i=( _i,1,…, _i,r) ^r, 1≤ i≤ d, with total degree ∑i|αi|=k _i| _i|=k. The group SdS_d permutes the multi-indices αi _i. Therefore an invariant monomial orbit is determined by a multiset of nonzero multi-indices α(1),…,α(q),α(j)∈ℕr∖0,∑j=1q|α(j)|=k.\α^(1),…,α^(q)\, α^(j) ^r \0\, _j=1^q|α^(j)|=k. For d≥kd≥ k, every such multiset can be realized using at most k nonzero blocks, so the dimension stabilizes in d. For each m≥1m≥ 1, the number of nonzero block types of degree m is ar(m)=#α∈ℕr:|α|=m=(r+m−1m).a_r(m)=\#\α ^r:|α|=m\= r+m-1m. Hence the stable dimension of homogeneous degree k invariants is Nr(k)≔dimd,r,kSd=[tk]∏m≥1(1−tm)−ar(m)for d≥k,N_r(k) _d,r,k^S_d=[t^k] _m≥ 1(1-t^m)^-a_r(m) d≥ k, where [tk]F(t)[t^k]F(t) denotes the coefficient of tkt^k in the formal power series F(t)F(t). Equivalently, Nr(k)=[tk]∏m≥1(1−tm)−(r+m−1m).N_r(k)=[t^k] _m≥ 1(1-t^m)^- r+m-1m. For r=1r=1, this reduces to the ordinary partition number: N1(k)=p(k).N_1(k)=p(k). Thus the invariant degree-k dimension is independent of d once d≥kd≥ k, whereas the full homogeneous degree-k polynomial space in drdr variables has dimension (dr+k−1k), dr+k-1k, which grows polynomially in d of order dkd^k for fixed k. The asymptotic behavior of Nr(k)N_r(k) for fixed r and large k is subexponential: logNr(k)∼Crkrr+1, N_r(k) C_rk rr+1, where Cr=r+1r(rζ(r+1))1r+1,C_r= r+1r (rζ(r+1) ) 1r+1, and ζ(s)≔∑n=1∞n−sζ(s) _n=1^∞n^-s denotes the Riemann zeta function. Thus Nr(k)=exp(Crkrr+1+o(krr+1)).N_r(k)= (C_rk rr+1+o (k rr+1 ) ). For example, r=1r=1 recovers the Hardy–Ramanujan exponent logp(k)∼π2k3. p(k) π 2k3. For r=2r=2, logN2(k)∼32(2ζ(3))1/3k2/3, N_2(k) 32(2ζ(3))^1/3k^2/3, and for r=3r=3, logN3(k)∼43(3ζ(4))1/4k3/4. N_3(k) 43(3ζ(4))^1/4k^3/4. These formulas show that for fixed element dimension r and polynomial degree k, the invariant polynomial function-space dimension stabilizes as the set size d grows. This is the representation-stability mechanism underlying the dimension-independent rates for set-valued data. B.6 Hermite features for set-valued data For data on (ℝr)d(R^r)^d, a natural basis is given by multivariate Hermite polynomials relative to a Gaussian reference measure. Let HαH_α denote an orthonormal Hermite polynomial indexed by α∈ℕdrα ^dr. For block-structured data, we may write Hα1,…,αd(X)=∏i=1dHαi(xi),αi∈ℕr.H_ _1,…, _d(X)= _i=1^dH_ _i(x_i), _i ^r. The group SdS_d permutes the block indices αi _i. Therefore invariant Hermite features are obtained by symmetrizing Hermite monomials over SdS_d. The dimension count for homogeneous degree k invariant Hermite features is the same as for multisymmetric polynomials: dimℋd,r,kSd=Nr(k)for d≥k. _d,r,k^S_d=N_r(k) d≥ k. This construction gives a concrete hierarchy for invariant density and regression functions. For density estimation, let ϕd,j _d,j be invariant Hermite functions; for regression, let them be the corresponding invariant polynomials orthonormalized in L2(μd)L^2( _d). In either case, the scalar target admits an expansion fd⋆(X)=∑jad,j⋆ϕd,j(X).f_d (X)= _ja_d,j _d,j(X). Truncation at degree k produces a finite-dimensional invariant function class whose dimension is Nr(≤k)=∑q=0kNr(q),N_r(≤ k)= _q=0^kN_r(q), independent of d once d≥kd≥ k. For density estimation, the admissible class additionally enforces nonnegativity and unit integral. If one instead studies score matching, an invariant log-density expansion logfd⋆=∑jbd,j⋆ϕd,j f_d = _jb_d,j _d,j gives the Lebesgue score ∇Xlogdμdx(X)=−X+∑jbd,j⋆∇Xϕd,j(X). _X d _ddx(X)=-X+ _jb_d,j _X _d,j(X). Gradients of invariant scalar features are equivariant vector fields: ∇Xϕd,j(π⋅X)=π⋅∇Xϕd,j(X). _X _d,j(π· X)=π· _X _d,j(X). If the function coefficients have a controlled tail, for example, ∑j>m(ad,j⋆)2≤bm2, _j>m(a_d,j )^2≤ b_m^2, then truncating to m invariant Hermite functions incurs squared L2L^2 approximation error at most bm2b_m^2. This is a concrete instance of the approximation tail B(k)B(k) in Theorem 4.1. B.7 Attributed graphs An attributed graph with d nodes is represented, as in the main text, by X∈d=ℝr×d×d.X _d=R^r× d× d. The channel index a∈1,…,ra∈\1,…,r\ records edge and/or node features; node features may, for example, be placed on diagonal entries of designated channels. Node relabeling acts simultaneously on both node indices: (π⋅X)a,i,j=Xa,π−1(i),π−1(j).(π· X)_a,i,j=X_a,π^-1(i),π^-1(j). A homogeneous degree-k polynomial function is a linear combination of monomials ∏a=1r∏i,j=1dXa,i,jma,i,j,∑a,i,jma,i,j=k. _a=1^r _i,j=1^dX_a,i,j^m_a,i,j, _a,i,jm_a,i,j=k. Two such monomials belong to the same SdS_d-orbit precisely when their node indices differ only by a relabeling. The orbits are therefore indexed by unlabeled channel-attributed directed multigraph patterns of total degree k, with diagonal factors representing vertex decorations when node features are encoded on the diagonal. Let ℛd,r,kSdR_d,r,k^S_d be the corresponding space of invariant homogeneous polynomial functions. Any degree-k monomial involves at most 2k2k distinct node indices, so dimℛd,r,kSd=Gr(k)for every d≥2k, _d,r,k^S_d=G_r(k) every d≥ 2k, where Gr(k)G_r(k) is the number of admissible unlabeled channel-attributed multigraph patterns of degree k. Thus the function-space dimension stabilizes with respect to the number of nodes. The same dimension can be written by character theory. With Wd=ℝr×d×d,W_d=R^r× d× d, we have ℛd,r,kSd=(Symk(Wd∗))Sd,dimℛd,r,kSd=1d!∑π∈SdχSymk(Wd∗)(π).R_d,r,k^S_d= (Sym^k(W_d ) )^S_d, _d,r,k^S_d= 1d! _π∈ S_d _Sym^k(W_d )(π). Equivalently, if ϱd _d is the representation of SdS_d on Wd∗W_d , its Molien series is ∑k≥0dimℛd,r,kSdtk=1d!∑π∈Sd1det(I−tϱd(π)). _k≥ 0 _d,r,k^S_dt^k= 1d! _π∈ S_d 1 (I-t _d(π)). The asymptotic dependence on k separates node-only and edge-attributed systems. If all active channels are supported on the diagonal, the stable dimension reduces to the multisymmetric count Nr(k)=[tk]∏m≥1(1−tm)−(r+m−1m),N_r(k)=[t^k] _m≥ 1(1-t^m)^- r+m-1m, and therefore Nr(k)=exp(Crkrr+1+o(krr+1)).N_r(k)= (C_rk rr+1+o (k rr+1 ) ). In contrast, if at least one channel contains edge variables, graph-pattern complexity gives Gr(k)=exp(klogk+O(kloglogk)),k→∞.G_r(k)= \! (k k+O(k k) ), k→∞. Thus attributed-graph invariant function spaces stabilize in the number of nodes d, while their growth with interaction order k is larger than for set-valued data. Appendix C Concrete Exact Transfers for Sets and Graphs This appendix makes the transfer assumption concrete for the two domains studied in the paper. The operator Td→DT_d→ D does not match arbitrary functions across dimensions; it instantiates the same invariant rule at a new set or graph size. Shared Deep Sets, GNNs, empirical measures, and graphons motivate coherence and exact target compatibility. The stable feature constructions additionally realize the linear isometry required by the theory after normalization in the relevant L2L^2 spaces. C.1 Sets A set of d vectors is represented by X=(x1,…,xd)∈d=(ℝr)d≃ℝr×dX=(x_1,…,x_d) _d=(R^r)^d ^r× d. Because the ordering carries no information, SdS_d acts by π⋅X=(xπ−1(1),…,xπ−1(d))π· X=(x_π^-1(1),…,x_π^-1(d)). A set distribution is therefore represented by an exchangeable law, and both its density and its regression function are invariant by Appendix B.1. Shared Deep Sets rules. Let ϕ:ℝr→ℝmφ:R^r ^m be an elementwise feature map and define the normalized set summary mdϕ(X)=1d∑i=1dϕ(xi).m_d^φ(X)= 1d _i=1^dφ(x_i). For any readout F:ℝm→ℝF:R^m , the rule fd(X)=F(mdϕ(X))f_d(X)=F\! (m_d^φ(X) ) is invariant for every d. Its transfer to size D is obtained by applying the same ϕφ and F: (Td→Dfd)(X1,…,XD)=F(1D∑i=1Dϕ(Xi)).(T_d→ Df_d)(X_1,…,X_D)=F\! ( 1D _i=1^Dφ(X_i) ). This is precisely the size-shared computation of a mean-pooled Deep Sets model. Sum-pooled models admit the same construction when the task uses an extensive, rather than normalized, quantity. Exact target compatibility means that the population task is generated by this same rule at every size. Replication and empirical measures. If D=qdD=qd, repeat each element q times: Rd→D(x1,…,xd)=(x1,…,x1⏟q,…,xd,…,xd⏟q).R_d→ D(x_1,…,x_d)=( x_1,…,x_1_q,…, x_d,…,x_d_q). The normalized summary is unchanged, mDϕ(Rd→DX)=mdϕ(X).m_D^φ(R_d→ DX)=m_d^φ(X). Equivalently, replication leaves the empirical measure d−1∑iδxid^-1 _i _x_i unchanged. Hence every function of the empirical measure, including normalized moments and mean-pooled Deep Sets rules, transfers exactly. Zero padding gives another exact construction for sum-based rules whenever the added null element satisfies ϕ(0)=0φ(0)=0. Stable feature expansions. Let ψd,j _d,j be normalized multisymmetric or invariant Hermite functions, paired across sizes by their common orbit type. For fd=∑jajψd,j,f_d= _ja_j _d,j, define Td→Dfd=∑jajψD,j.T_d→ Df_d= _ja_j _D,j. If the paired features are orthonormal in their respective task spaces, Parseval’s identity gives ‖Td→Dfd‖D2=∑jaj2=‖fd‖d2.\|T_d→ Df_d\|_D^2= _ja_j^2=\|f_d\|_d^2. Thus Td→DT_d→ D is a linear isometry. A shared expansion may represent either a regression function or a density; in the latter case, the admissible coefficient class is restricted so that the expansion remains nonnegative and integrates to one. This provides the explicit transfer used by the set function classes in Appendix B.5. C.2 Attributed graphs An attributed graph with d nodes is represented by X∈d=ℝr×d×dX _d=R^r× d× d, and SdS_d acts by simultaneous relabeling: (π⋅X)a,i,j=Xa,π−1(i),π−1(j).(π· X)_a,i,j=X_a,π^-1(i),π^-1(j). Consequently, graph-level densities and regression functions depend only on the isomorphism class of the attributed graph. Normalized motif rules and graph blow-ups. For a fixed attributed pattern H, let tH(X)t_H(X) denote its normalized homomorphism density in X. These functions are invariant and are indexed by H, not by the number of nodes. If X(q)X^(q) is the q-fold blow-up obtained by replacing each node by q twins and each edge by the corresponding complete bipartite block, then tH(X(q))=tH(X).t_H(X^(q))=t_H(X). Thus graph blow-ups preserve every rule of the form fd(X)=F(tH1(X),…,tHm(X))f_d(X)=F (t_H_1(X),…,t_H_m(X) ) exactly. A step-function graphon gives the same interpretation: refining its finite partition changes the graph size but not the common graphon or its normalized motif functionals. Shared GNN rules. A message-passing GNN applies the same local aggregation and update functions at every node and every size, followed by a permutation-invariant graph readout. Holding these functions fixed while changing d therefore defines a map from the size-d function to its size-D realization. This is the architecture-level instance of Td→DT_d→ D. The transfer is exact when the target family is generated by the same shared GNN rule. Mean aggregation and normalized graph readouts prevent the numerical scale of the rule from growing merely with the number of nodes. Stable graph feature expansions. Let ψd,H _d,H be normalized invariant functions indexed by unlabeled attributed multigraph patterns H. Transfer pairs the same pattern across sizes: Td→Dψd,H=ψD,H.T_d→ D _d,H= _D,H. Extending this identification linearly gives Td→D(∑HaHψd,H)=∑HaHψD,H.T_d→ D\! ( _Ha_H _d,H )= _Ha_H _D,H. After orthonormalization in the task norms, this map is an isometry and satisfies the coherence identity. The degree-k truncations stabilize once d≥2kd≥ 2k, as shown in Appendix B.7. These expansions cover invariant graph regression and density functions without privileging a particular learning loss; for densities, admissibility again enforces nonnegativity and normalization. C.3 What the exact-transfer assumption asserts Across all of these examples, exact transfer makes two statements. First, the semantic rule is shared across sizes: the same normalized summary, architecture, motif functional, or invariant expansion is used at the training and target sizes. Second, the task family is compatible with that rule: Td→Dfd⋆=fD⋆.T_d→ Df_d =f_D . This does not claim that arbitrary set or graph tasks are related. It identifies the broad class of size-consistent problems for which learning at one size can be statistically informative at another. The isometry assumption then ensures that this semantic identification does not alter the scale of estimation error. Together, these conditions isolate the statistical question studied in the paper from a separate cross-size modeling mismatch. Appendix D Proof of Theorem 4.1 This section proves the dimension-free upper bounds and derives all rate regimes. The proof has two steps. First, exact isometric transfer converts a fixed-size estimation guarantee into a simultaneous guarantee at every larger size. Second, representation growth is balanced against the source tail. Exact transfer is defined in Section 3 and formalized in Appendix B.3; representation growth q(k)q_ X(k) and the source envelope B(k)B(k) are defined in Section 4. The loss assumptions in the main theorem are used below to derive the finite-dimensional estimation bound. The minimax theorem additionally uses the local nondegeneracy conditions equation E.1–equation E.1. D.1 Finite-dimensional estimation and transfer Fix a domain type ∈set,graph X∈\set,graph\, a training size d, and an interaction order k. Let fd,k∘f_d,k and f^n,d,kinv f_n,d,k^inv minimize the population and empirical risks over ℱd,kF_d,k, respectively. Uniform calibration gives ‖fd,k∘−fd⋆‖d2≤CappBd(k).\|f_d,k -f_d \|_d^2≤ C_appB_d(k). Apply the strong-convexity and score-concentration calculation of Appendix F in orthonormal coordinates on d,kV_d,k. Since those coordinates identify Euclidean distance with ∥⋅∥d\|·\|_d, with probability at least 1−δ1-δ, ‖f^n,d,kinv−fd,k∘‖d2≤Cσ2α2dim(d,k)+log(1/δ)n. \| f_n,d,k^inv-f_d,k \|_d^2≤ C σ^2α^2 (V_d,k)+ (1/δ)n. The squared triangle inequality and the calibration bound therefore give ‖f^n,d,kinv−fd⋆‖d2≤C0(Bd(k)+dim(d,k)+log(1/δ)n). \| f_n,d,k^inv-f_d \|_d^2≤ C_0 (B_d(k)+ (V_d,k)+ (1/δ)n ). Here C0C_0 depends on the uniform calibration, curvature, and score constants, but not on n,d,Dn,d,D, or k. Thus equation D.1 is a consequence of the primitive loss conditions, rather than an assumed rate. The two quantities on the right are uniform in size: by definition, Bd(k)≤B(k)B_d(k)≤ B(k) and dim(d,k)≤q(k) (V_d,k)≤ q_ X(k). Moreover, exact target transfer and isometry give, simultaneously for every D≥dD≥ d, ‖Td→Df^n,d,kinv−fD⋆‖D2 \|T_d→ D f_n,d,k^inv-f_D \|_D^2 =‖Td→D(f^n,d,kinv−fd⋆)‖D2 = \|T_d→ D( f_n,d,k^inv-f_d ) \|_D^2 =‖f^n,d,kinv−fd⋆‖d2. = \| f_n,d,k^inv-f_d \|_d^2. No union bound over D is needed: all target-size errors equal the same source-size error on the event in equation D.1. Taking the supremum in equation D.1 therefore yields supD≥d‖Td→Df^n,d,kinv−fD⋆‖D2≤C0(B(k)+q(k)+log(1/δ)n). _D≥ d \|T_d→ D f_n,d,k^inv-f_D \|_D^2≤ C_0 (B(k)+ q_ X(k)+ (1/δ)n ). This is the key dimension-free oracle inequality. Object sizes d and D have disappeared; only interaction order, representation growth, and target regularity remain. D.2 Set rates Write β=r/(r+1)β=r/(r+1). The stable multisymmetric count satisfies logqset(k)=Crkβ+o(kβ),Cr=r+1r(rζ(r+1))1/(r+1). q_set(k)=C_rk^β+o(k^β), C_r= r+1r (rζ(r+1) )^1/(r+1). We optimize the two leading terms in equation D.1; for a fixed confidence level, log(1/δ)/n (1/δ)/n is smaller than all rates below. Polynomial source decay. If B(k)≲k−τB(k) k^-τ, balancing the two terms in equation D.1 gives Crknβ+τlogkn=logn+o(logn)C_rk_n^β+τ k_n= n+o( n), hence kn=(logn/Cr)1/β(1+o(1))k_n=( n/C_r)^1/β(1+o(1)) and supD≥d∥Td→Df^n,d,kninv−fD⋆∥D2≲(logn)−τ/β=(logn)−τ(r+1)/r. _D≥ d \|T_d→ D f_n,d,k_n^inv-f_D \|_D^2 ( n)^-τ/β=( n)^-τ(r+1)/r. Exponential source decay. If B(k)≲e−akνB(k) e^-ak^ν, the balancing equation is aknν+Crknβ+o(knβ)=logn.ak_n^ν+C_rk_n^β+o(k_n^β)= n. Solving it in the three regimes gives the compact summary B(kn)+qset(kn)n≍n−1+o(1),ν>β,n−a/(a+Cr)+o(1),ν=β,exp[−aCr−ν/β(logn)ν/β(1+o(1))],0<ν<β.B(k_n)+ q_set(k_n)n casesn^-1+o(1),&ν>β,\\ n^-a/(a+C_r)+o(1),&ν=β,\\ \! [-aC_r^-ν/β( n)^ν/β(1+o(1)) ],&0<ν<β. cases The first line is the fast set regime in Table 2; the other two lines give the critical and subcritical interpolation. D.3 Graph rates For every fixed feature dimension r, the stable graph-pattern count satisfies logqgraph(k)=klogk+Or(kloglogk)=klogk(1+o(1)). q_graph(k)=k k+O_r(k k)=k k\,(1+o(1)). Thus r affects only the lower-order remainder and does not enter the first-order rates. Polynomial source decay. For B(k)≲k−τB(k) k^-τ, the crossing equation gives kn=(logn/loglogn)(1+o(1))k_n=( n/ n)(1+o(1)), and therefore supD≥d‖Td→Df^n,d,kninv−fD⋆‖D2≲(lognloglogn)−τ. _D≥ d \|T_d→ D f_n,d,k_n^inv-f_D \|_D^2 ( n n )^-τ. Exponential source decay. For B(k)≲e−akνB(k) e^-ak^ν, the balancing equation is aknν+knlogkn+Or(knloglogkn)=logn.ak_n^ν+k_n k_n+O_r(k_n k_n)= n. Solving it gives B(kn)+qgraph(kn)n≍n−1+o(1),ν>1,exp[−a(lognloglogn)ν(1+o(1))],0<ν≤1.B(k_n)+ q_graph(k_n)n casesn^-1+o(1),&ν>1,\\ \! [-a ( n n )^ν(1+o(1)) ],&0<ν≤ 1. cases The second line is critical at ν=1ν=1 and subcritical for 0<ν<10<ν<1. Equations equation D.2, equation D.2, equation D.3, and equation D.3 prove Theorem 4.1. Appendix E Proof of Theorem 4.2 We now show that the preceding rates cannot be improved. The lower bound is stated under the nondegeneracy condition in the theorem, which requires the invariant coordinates counted by representation stability to correspond to statistically distinguishable local perturbations. This is the standard condition that prevents the loss or data distribution from collapsing nominally different invariant directions. E.1 Minimax risk and local invariant submodels Let (B) F_ X(B) be the class of size-consistent target families on domain X satisfying exact transfer and the source envelope B. An estimator observes n samples at size d and returns functions f^D f_D for D≥dD≥ d. Define its worst-case risk by ℜn(,B)≔inf^supd≥1sup⋆∈(B)[supD≥d‖f^D−fD⋆‖D2]. R_n( X,B) _ f _d≥ 1 _ f ∈ F_ X(B)E\! [ _D≥ d\| f_D-f_D \|_D^2 ]. Minimax nondegeneracy. For every interaction order k, take a size dkd_k in the stable range: dk≥kd_k≥ k for sets and dk≥2kd_k≥ 2k for graphs. The nondegeneracy assumption provides mk≥c0q(k)m_k≥ c_0q_ X(k) orthonormal invariant directions ψ1,…,ψmk _1,…, _m_k, paired coherently across larger sizes, and an admissible baseline f0f_0 such that the hypercube fω=f0+u∑j=1mkωjψj,ω∈−1,1mk,f_ω=f_0+u _j=1^m_k _j _j, ω∈\-1,1\^m_k, belongs to the source class whenever mku2≤c1B(k)m_ku^2≤ c_1B(k). It also requires the neighboring statistical experiments to satisfy KL(Pω⊗n,Pω(j)⊗n)≤c2nu2,KL\! (P_ω n,P_ω^(j) n )≤ c_2nu^2, where ω(j)ω^(j) differs from ω only in coordinate j. For regression, one obtains equation E.1 by adding Gaussian noise to Y=fω(X)Y=f_ω(X). For density estimation, it follows from a bounded local density or exponential-family perturbation around an invariant density bounded away from zero. These constructions also ensure nonnegativity and normalization of every density in equation E.1. E.2 Assouad lower bound Set uk2=c3minB(k)mk,1n,u_k^2=c_3 \! \ B(k)m_k, 1n \, with c3c_3 sufficiently small. Then the hypercube is contained in the source class, and the KL divergence between neighboring vertices is bounded by a universal constant. Since orthonormality gives ‖fω−fω(j)‖dk2=4uk2\|f_ω-f_ω^(j)\|_d_k^2=4u_k^2, Assouad’s lemma yields inff^supω∈−1,1mkω‖f^−fω‖dk2≥c4mkuk2≥c5minB(k),q(k)n. _ f _ω∈\-1,1\^m_kE_ω\| f-f_ω\|_d_k^2≥ c_4m_ku_k^2≥ c_5 \! \B(k), q_ X(k)n \. The size-generalization loss contains the choice D=dkD=d_k, so its supremum is at least the in-domain loss in equation E.2. Consequently, ℜn(,B)≥c5supk≥1minB(k),q(k)n. R_n( X,B)≥ c_5 _k≥ 1 \! \B(k), q_ X(k)n \. This observation is important: transfer cannot remove a lower bound already present at the training size. Because B(k)B(k) decreases and q(k)q_ X(k) increases, the supremum in equation E.2 is attained, up to constants and lower-order factors, where B(k)≍q(k)/nB(k) q_ X(k)/n. Under the regular source envelopes considered here, supkminB(k),q(k)n≍infkB(k)+q(k)n. _k \! \B(k), q_ X(k)n \ _k \B(k)+ q_ X(k)n \. The right-hand side is precisely the quantity controlled by the upper oracle inequality equation D.1. E.3 Evaluation of the lower bound For polynomial source decay, substituting the set and graph representation asymptotics into the crossing condition gives, respectively, (logn)−τ(r+1)/rand(lognloglogn)−τ.( n)^-τ(r+1)/r ( n n )^-τ. For exponential source decay, the same crossing equations give exactly the three set regimes in equation D.2 and the two graph regimes in equation D.3. These lower bounds match the upper bounds in Appendix D, up to constants and lower-order factors. They apply to both regression and density estimation through the local submodels above, and they already hold at a stable training size. Therefore no estimator can uniformly improve any set or graph rate in Table 2, completing the proof of Theorem 4.2. Appendix F Auxiliary finite-dimensional estimation bound For completeness, we derive the finite-dimensional estimation term in equation D.1 from restricted curvature and score concentration. Empirical optimality and strong convexity reduce estimation error to the empirical gradient at the best population fit in the finite model; no statistical rate is assumed. F.1 Restricted gradients on the invariant model Fix d∈ℕd . Let ΘdGd _d^G_d be a finite-dimensional invariant parameter space and let θd⋆∈ΘdGd _d ∈ _d^G_d denote its population-risk minimizer. In this section, θd⋆ _d is the best fit within the finite model (the analogue of fd,k∘f_d,k ), and need not equal the unrestricted target. We write pdG=dim(ΘdGd).p_d^G= ( _d^G_d). For simplicity of notation, we identify ΘdGd _d^G_d locally with a Euclidean space of dimension pdGp_d^G. Equivalently, if ΘdGd _d^G_d is a smooth model, the gradient below is understood in any normalized local coordinate chart around θd⋆ _d . Thus, ∇GL^n,d(θd⋆) _G L_n,d( _d ) denotes the gradient of the empirical risk restricted to the invariant model. We work on the restricted-curvature event on which the empirical risk L^n,d(θ)=1n∑i=1nℓd(Zi,θ) L_n,d(θ)= 1n _i=1^n _d(Z_i,θ) is α-strongly convex on ΘdGd _d^G_d, with α independent of d. This is a primitive curvature property, not an estimation-rate assumption. For squared-loss regression in an orthonormal feature basis, the Hessian is the empirical feature Gram matrix. If the whitened feature vector is uniformly sub-Gaussian, standard covariance concentration gives this event with probability at least 1−δ1-δ once n≳pdG+log(1/δ)n p_d^G+ (1/δ). For a regular likelihood or smooth proper loss, the same conclusion follows from a uniformly positive population Hessian and concentration of the restricted empirical Hessian. Pointwise strong convexity of the loss is a stronger sufficient condition, but is not required. We will use the following standard concentration bound for the restricted empirical gradient. Lemma F.1 (Restricted score concentration). Suppose the restricted score at θd⋆ _d is sub-Gaussian with variance proxy at most σ2σ^2. That is, writing Yi≔∇Gℓd(Zi,θd⋆)∈ℝpdG,Y_i _G _d(Z_i, _d ) ^p_d^G, we have Yi=0EY_i=0 and, for every unit vector v∈ℝpdGv ^p_d^G, exp(λ⟨v,Yi⟩)≤exp(λ2σ22)∀λ∈ℝ.E (λ v,Y_i )≤ ( λ^2σ^22 ) ∀λ . Then there exists an absolute constant C0>0C_0>0 such that, for every δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, ‖∇GL^n,d(θd⋆)‖22=‖1n∑i=1nYi‖22≤C0σ2pdG+log(1/δ)n. \| _G L_n,d( _d ) \|_2^2= \| 1n _i=1^nY_i \|_2^2≤ C_0σ^2 p_d^G+ (1/δ)n. Proof. Let p=pdGp=p_d^G and define Y¯n≔1n∑i=1nYi. Y_n 1n _i=1^nY_i. Since the YiY_i’s are independent, mean-zero, and σ2σ^2-sub-Gaussian, the average Y¯n Y_n is sub-Gaussian with variance proxy σ2/nσ^2/n. Hence for every unit vector v∈ℝpv ^p, exp(λ⟨v,Y¯n⟩)≤exp(λ2σ22n).E (λ v, Y_n )≤ ( λ^2σ^22n ). Let N be a 1/21/2-net of the unit sphere p−1S^p-1 with ||≤5p|N|≤ 5^p. For every u∈ℝpu ^p, ‖u‖2≤2maxv∈⟨v,u⟩.\|u\|_2≤ 2 _v v,u . Therefore, for any t>0t>0, ℙ(‖Y¯n‖2≥2t)≤ℙ(maxv∈⟨v,Y¯n⟩≥t).P(\| Y_n\|_2≥ 2t) ( _v v, Y_n ≥ t ). By a union bound and the one-dimensional sub-Gaussian tail bound, ℙ(maxv∈⟨v,Y¯n⟩≥t)≤||exp(−nt22σ2)≤exp(plog5−nt22σ2).P ( _v v, Y_n ≥ t )≤|N| (- nt^22σ^2 )≤ (p 5- nt^22σ^2 ). Taking t=σ2(plog5+log(1/δ))n,t=σ 2(p 5+ (1/δ))n, we obtain, with probability at least 1−δ1-δ, ‖Y¯n‖2≤2σ2(plog5+log(1/δ))n.\| Y_n\|_2≤ 2σ 2(p 5+ (1/δ))n. Squaring both sides yields ‖Y¯n‖22≤8σ2plog5+log(1/δ)n.\| Y_n\|_2^2≤ 8σ^2 p 5+ (1/δ)n. Thus the claim holds with an absolute constant C0C_0. ∎ F.2 Proof of the estimation bound Let θ^n,dG∈argminθ∈ΘdGdL^n,d(θ). θ_n,d^G∈ _θ∈ _d^G_d L_n,d(θ). Since θd⋆∈ΘdGd _d ∈ _d^G_d, empirical optimality gives L^n,d(θ^n,dG)≤L^n,d(θd⋆). L_n,d( θ_n,d^G)≤ L_n,d( _d ). On the intersection of the restricted-curvature event and the score-concentration event, L^n,d L_n,d is α-strongly convex on ΘdGd _d^G_d, and hence L^n,d(θ^n,dG)≥L^n,d(θd⋆)+⟨∇GL^n,d(θd⋆),θ^n,dG−θd⋆⟩+α2‖θ^n,dG−θd⋆‖22. L_n,d( θ_n,d^G)≥ L_n,d( _d )+ _G L_n,d( _d ), θ_n,d^G- _d + α2 \| θ_n,d^G- _d \|_2^2. Combining the previous two displays gives 0≥⟨∇GL^n,d(θd⋆),θ^n,dG−θd⋆⟩+α2‖θ^n,dG−θd⋆‖22.0≥ _G L_n,d( _d ), θ_n,d^G- _d + α2 \| θ_n,d^G- _d \|_2^2. By Cauchy–Schwarz, 0≥−‖∇GL^n,d(θd⋆)‖2‖θ^n,dG−θd⋆‖2+α2‖θ^n,dG−θd⋆‖22.0≥- \| _G L_n,d( _d ) \|_2 \| θ_n,d^G- _d \|_2+ α2 \| θ_n,d^G- _d \|_2^2. If θ^n,dG=θd⋆ θ_n,d^G= _d , the desired bound is immediate. Otherwise, dividing by ‖θ^n,dG−θd⋆‖2\| θ_n,d^G- _d \|_2 gives ‖θ^n,dG−θd⋆‖2≤2α‖∇GL^n,d(θd⋆)‖2. \| θ_n,d^G- _d \|_2≤ 2α \| _G L_n,d( _d ) \|_2. Taking each event with failure probability δ/2δ/2, squaring, applying Lemma F.1, and using a union bound, we obtain with probability at least 1−δ1-δ, ‖θ^n,dG−θd⋆‖22≤4α2‖∇GL^n,d(θd⋆)‖22≤Cσ2α2pdG+log(1/δ)n, \| θ_n,d^G- _d \|_2^2≤ 4α^2 \| _G L_n,d( _d ) \|_2^2≤ C σ^2α^2 p_d^G+ (1/δ)n, for an absolute constant C>0C>0. This is the finite-dimensional estimation bound used in equation D.1. When the coordinates are orthonormal in ℋdH_d, Euclidean parameter distance equals function-space distance. If the population best fit additionally satisfies ‖fd,k∘−fd⋆‖d2≤CappBd(k)\|f_d,k -f_d \|_d^2≤ C_appB_d(k), the squared triangle inequality gives equation D.1 directly. If pG≔supdpdG<∞,p^G _dp_d^G<∞, then pdG≤pGp_d^G≤ p^G for every d, and therefore ‖θ^n,dG−θd⋆‖22≤Cσ2α2pG+log(1/δ)n. \| θ_n,d^G- _d \|_2^2≤ C σ^2α^2 p^G+ (1/δ)n. F.3 Proof of the transfer bound Fix a source dimension d. Suppose that for every D≥dD≥ d, Φd→Dθd⋆=θD⋆, _d→ D _d = _D , and that Φd→D _d→ D is distance preserving on the invariant model: ‖Φd→Dθ−Φd→Dθ′‖2=‖θ−θ′‖2∀θ,θ′∈ΘdGd. \| _d→ Dθ- _d→ Dθ \|_2= \|θ-θ \|_2 ∀θ,θ ∈ _d^G_d. Then, for every D≥dD≥ d, ‖Φd→Dθ^n,dG−θD⋆‖2 \| _d→ D θ_n,d^G- _D \|_2 =‖Φd→Dθ^n,dG−Φd→Dθd⋆‖2 = \| _d→ D θ_n,d^G- _d→ D _d \|_2 =‖θ^n,dG−θd⋆‖2. = \| θ_n,d^G- _d \|_2. Taking the supremum over D≥dD≥ d, we get supD≥d‖Φd→Dθ^n,dG−θD⋆‖22=‖θ^n,dG−θd⋆‖22. _D≥ d \| _d→ D θ_n,d^G- _D \|_2^2= \| θ_n,d^G- _d \|_2^2. Combining this identity with the estimation bound above yields supD≥d‖Φd→Dθ^n,dG−θD⋆‖22≤Cσ2α2pdG+log(1/δ)n _D≥ d \| _d→ D θ_n,d^G- _D \|_2^2≤ C σ^2α^2 p_d^G+ (1/δ)n with probability at least 1−δ1-δ. If pG=supdpdG<∞p^G= _dp_d^G<∞, the right-hand side is bounded by Cσ2α2pG+log(1/δ)n.C σ^2α^2 p^G+ (1/δ)n. This completes the auxiliary transfer calculation. Appendix G Equivariant Field Specialization for Sets Score matching and denoising replace invariant scalar functions by permutation-equivariant vector fields, but the proof is otherwise unchanged. Let ψd,jj≥1\ _d,j\_j≥ 1 be an orthonormal equivariant basis and write sd⋆=∑j≥1θd,j⋆ψd,j,‖s^d−sd⋆‖d2=∑j≥1(θ^d,j−θd,j⋆)2.s_d = _j≥ 1 _d,j _d,j, \| s_d-s_d \|_d^2= _j≥ 1( θ_d,j- _d,j )^2. If ℐd,kI_d,k contains the features of degree at most k, then its stable dimension and the omitted coefficient energy are mr(k)=|ℐd,k|=exp(Crkr/(r+1)+o(kr/(r+1))),Bd(k)=∑j∉ℐd,k(θd,j⋆)2.m_r(k)=|I_d,k|= \! (C_rk^r/(r+1)+o\! (k^r/(r+1) ) ), B_d(k)= _j _d,k( _d,j )^2. Orthogonality and the auxiliary finite-dimensional bound in Appendix F give, with probability at least 1−δ1-δ, ‖s^n,d(k)−sd⋆‖d2≤Bd(k)+Cσ2α2mr(k)+log(1/δ)n.\| s_n,d^(k)-s_d \|_d^2≤ B_d(k)+C σ^2α^2 m_r(k)+ (1/δ)n. Thus the scalar proof applies verbatim. Uniform polynomial decay Bd(k)≲k−τB_d(k) k^-τ gives (logn)−τ(r+1)/r( n)^-τ(r+1)/r. Under uniform exponential decay Bd(k)≲e−akνB_d(k) e^-ak^ν, with β=r/(r+1)β=r/(r+1), infkBd(k)+mr(k)n≍n−1+o(1),ν>β,n−a/(a+Cr)+o(1),ν=β,exp[−aCr−ν/β(logn)ν/β(1+o(1))],0<ν<β. _k \B_d(k)+ m_r(k)n \ casesn^-1+o(1),&ν>β,\\ n^-a/(a+C_r)+o(1),&ν=β,\\ \! [-aC_r^-ν/β( n)^ν/β(1+o(1)) ],&0<ν<β. cases Because the equivariant transfer operator is isometric, these bounds hold simultaneously at every target size D≥dD≥ d. Appendix H Equivariant Field Specialization for Graphs Let d,kJ_d,k contain the degree-at-most-k equivariant graph features, and write Mr(k)=|d,k|M_r(k)=|J_d,k|. For fixed channel dimension r, Mr(k)=exp(klogk+Or(kloglogk)),Bdgraph(k)=∑j∉d,k(θd,j⋆)2.M_r(k)= \! (k k+O_r(k k) ), B_d^graph(k)= _j _d,k( _d,j )^2. The same orthogonal decomposition and finite-dimensional estimate yield ‖s^n,d(k)−sd⋆‖d2≤Bdgraph(k)+Cσ2α2Mr(k)+log(1/δ)n.\| s_n,d^(k)-s_d \|_d^2≤ B_d^graph(k)+C σ^2α^2 M_r(k)+ (1/δ)n. Consequently, polynomial decay Bdgraph(k)≲k−τB_d^graph(k) k^-τ gives (logn/loglogn)−τ( n/ n)^-τ, while exponential decay Bdgraph(k)≲e−akνB_d^graph(k) e^-ak^ν gives infkBdgraph(k)+Mr(k)n≍n−1+o(1),ν>1,exp[−a(lognloglogn)ν(1+o(1))],0<ν≤1. _k \B_d^graph(k)+ M_r(k)n \ casesn^-1+o(1),&ν>1,\\ \! [-a ( n n )^ν(1+o(1)) ],&0<ν≤ 1. cases The channel dimension affects only the lower-order term in Mr(k)M_r(k), so it does not enter these first-order rates. Isometric equivariant transfer again makes every bound simultaneous over D≥dD≥ d. Appendix I Experiments The experiments isolate two complementary parts of the theory rather than attempting a broad architectural benchmark. The first asks whether an invariant representation learned at one graph size retains its meaning at larger sizes. The second asks what remains when transfer is exact but the target must be approximated by a low-degree truncation. Together they separate representation-induced transfer error from approximation error due to the source tail. I.1 Subgraph counting We include a small synthetic experiment illustrating the role of invariant low-degree structure in transfer across graph sizes. The purpose of the experiment is not to benchmark a new architecture, but to visualize the basic mechanism behind our theory: a low-degree invariant statistic has a stable meaning across graph sizes, while a non-invariant coordinate polynomial does not transfer canonically. We generate graphs from an Erdős–Rényi model with a graph-dependent edge probability. For each sample, we draw p∼Unif(0.15,0.85),A∼G(d,p),p (0.15,0.85), A G(d,p), where A∈0,1d×dA∈\0,1\^d× d is the adjacency matrix of an undirected graph with no self-loops. The response is the population triangle density y≈p3y≈ p^3. Thus, the target is a low-degree graph moment, but the learner observes only the sampled graph A, not the latent parameter p. We train all models only on graphs with d=10d=10 nodes and evaluate them on larger graphs with D∈25,30,35,40,50,60,75,100,125,150,175,200.D∈\25,30,35,40,50,60,75,100,125,150,175,200\. We compare two predictors. The first is an invariant polynomial model using normalized graph statistics ϕinv,d(A)=(Ed(A),Wd(A),Td(A)), _inv,d(A)= (E_d(A),W_d(A),T_d(A) ), where Ed(A)E_d(A) is the edge density, Wd(A)W_d(A) is the normalized wedge density, and Td(A)T_d(A) is the normalized triangle density. A linear model is fit on these features at d=10d=10, and transfer to size D is performed by evaluating the same normalized invariant statistics on the larger graph: f^inv,D(A)=β^0+β^1ED(A)+β^2WD(A)+β^3TD(A). f_inv,D(A)= β_0+ β_1E_D(A)+ β_2W_D(A)+ β_3T_D(A). This gives a direct size-transfer rule because the features are invariant graph moments whose interpretation is stable across graph sizes. The second predictor is a non-invariant degree-three polynomial baseline. At the training size d=10d=10, we use the raw triangle indicators AijAikAjk,1≤i<j<k≤10,A_ijA_ikA_jk, 1≤ i<j<k≤ 10, as features and fit a linear model. Such a model assigns separate coefficients to labeled triangles and therefore has no canonical extension to graphs with more than ten nodes. To give this baseline a favorable transfer rule, we average it over random induced subgraphs: for a test graph on D nodes, we sample subsets S1,…,SM⊆[D]S_1,…,S_M [D] of size ten and define f^raw,Davg(A)=1M∑m=1Mf^raw,10(ASm×Sm). f_raw,D^avg(A)= 1M _m=1^M f_raw,10(A_S_m× S_m). This is a Monte Carlo symmetrization of the raw non-invariant predictor. It deliberately gives the baseline an advantageous test-time correction: without averaging over induced subgraphs, its coordinates refer only to the ten training labels and do not define a predictor on a larger graph. The comparison therefore measures whether invariance is built into the learned representation or reconstructed afterwards by explicit averaging. Figure 1(a) shows the test mean-squared error as the test graph size increases. The invariant polynomial model transfers directly and improves with graph size, since its normalized moments use all available nodes and become more accurate estimates of the underlying population quantities. The raw model also improves after subgraph averaging, but remains consistently worse despite this favorable correction. Thus, low polynomial degree alone is not the operative property: transfer comes from features whose invariant meaning is stable across sizes. The experiment also clarifies that larger test graphs need not be intrinsically harder; once the representation is size-consistent, additional nodes can provide more information about the same latent graph statistics. I.2 Equivariant field transfer on weighted graphs We next illustrate equivariant field estimation in a controlled setting where the target is known analytically. Continuous weighted graphs are represented by symmetric matrices A∈ℝd×d,A ^d× d, with zero diagonal and independent standard-Gaussian upper-triangular entries. We regress onto the permutation-equivariant field sd⋆(A)=−A−∑q=28bqqd−qAq−1.s_d (A)=-A- _q=2^8b_qqd^-qA^q-1. The features qd−qAq−1qd^-qA^q-1 are gradients of normalized invariant spectral statistics d−qtr(Aq)d^-qtr(A^q). Their meaning is shared across graph sizes, and the same coefficient bqb_q therefore defines the same rule at every size. We compare a fast-decay target, bq=2exp(−0.14q2),b_q=2 (-0.14q^2), with a slow-decay target, bq=2q−1/2,b_q=2q^-1/2, for which the omitted high-order components remain substantial. For each regime, we fit the degree-three equivariant model s^d(A)=−A−∑q=24b^qqd−qAq−1 s_d(A)=-A- _q=2^4 b_qqd^-qA^q-1 by least squares on the off-diagonal field entries of 200 independently sampled graphs with d=10d=10. Transfer to size D reuses the learned coefficients b^q b_q and evaluates the corresponding normalized features qD−qAq−1qD^-qA^q-1. We test on 16 independent graphs at each D∈10,15,20,30,40,60,80.D∈\10,15,20,30,40,60,80\. Because the common linear term −A-A is represented exactly, we report error relative to the energy of the nonlinear target component: RelMSED=∑A∑i<j(s^D(A)ij−sD⋆(A)ij)2∑A∑i<j(sD⋆(A)ij+Aij)2.RelMSE_D= _A _i<j( s_D(A)_ij-s_D (A)_ij)^2 _A _i<j(s_D (A)_ij+A_ij)^2. The full procedure is repeated for ten independent seeds, and the shaded bands in Figure 1(b) report 95% confidence intervals across these repetitions. No parameters are refit or calibrated at the target sizes: the only size-dependent operation is evaluating the analytically normalized features at (D). Figure 1(b) shows that the same learned rule remains stable across all tested sizes. The absence of systematic deterioration with (D) is the empirical signature of exact equivariant transfer in this example. What remains is truncation error: fast decay makes the degree-three approximation highly accurate, whereas slow decay leaves a persistent gap roughly two to three orders of magnitude larger. This separates the two roles appearing in the theory—normalization controls size mismatch, while coefficient decay determines how much signal lies beyond the fitted degree. The experiment is illustrative rather than a test of the asymptotic minimax rates, which additionally depend on the full growth of invariant feature spaces. (a) Invariant versus symmetrized raw features. (b) Fast versus slow coefficient decay. Figure 1: Two mechanisms governing transfer across graph sizes. (a) Transfer from 10-node Erdős–Rényi graphs: normalized invariant moments transfer directly, whereas labeled triangle features require explicit subgraph averaging. (b) Exact equivariant transfer from 10-node weighted graphs using size-normalized features: curves show mean relative MSE over ten repetitions, with 95% confidence intervals. Fast coefficient decay yields uniformly smaller truncation error. Appendix J Notation Symbol Meaning d,Dd,D Training object size and target object size, with D≥dD≥ d. n Number of training samples observed at size d. r Element-feature dimension for sets or channel dimension for attributed graphs. dX_d Size-d input space: ℝr×dR^r× d for sets or ℝr×d×dR^r× d× d for graphs. ZiZ_i Unified observation: XiX_i for density estimation and (Xi,Yi)(X_i,Y_i) for regression. λd _d Standard Gaussian reference measure on dX_d. μd,ρd _d, _d Input distribution and joint distribution of (X,Y)(X,Y), respectively. fd⋆f_d Population target at size d: a density relative to λd _d or a regression function. ℋdH_d L2(λd)L^2( _d) for density estimation or L2(μd)L^2( _d) for regression. ∥⋅∥d\|·\|_d The corresponding norm on ℋdH_d. ℱd,ℱdinvF_d,F_d^inv Statistical function class and its permutation-invariant subclass. ℓd,L^n,d,Ld _d, L_n,d,L_d Pointwise loss, empirical risk, and population risk. SdS_d Symmetric group acting by relabeling set elements or graph nodes. f^n,dinv f_n,d^inv Invariant empirical risk minimizer learned at size d. Td→DT_d→ D Exact coherent isometric transfer operator from size d to size D. k Polynomial degree or interaction order. d,kV_d,k Invariant polynomials of degree at most k in ℋdH_d. ℱd,kF_d,k Order-k approximation class; it also enforces density admissibility when required. fd,k∘,f^n,d,kinvf_d,k , f_n,d,k^inv Population and empirical risk minimizers over ℱd,kF_d,k. Bd(k),B(k)B_d(k),B(k) Best order-k approximation error at size d and its supremum over sizes. q(k)q_ X(k) Stable dimension supddim(d,k) _d (V_d,k) for ∈set,graph X∈\set,graph\. Nr(k),Gr(k)N_r(k),G_r(k) Stable homogeneous degree-k invariant-feature counts for sets and graphs. τ Polynomial source-decay exponent: B(k)≲k−τB(k) k^-τ. a,νa,ν Exponential source-decay constant and exponent: B(k)≲e−akνB(k) e^-ak^ν. β Set representation-growth exponent r/(r+1)r/(r+1). CrC_r Set growth constant r+1r(rζ(r+1))1/(r+1) r+1r (rζ(r+1) )^1/(r+1). δ Failure probability in high-probability bounds. (B) F_ X(B) Size-consistent source class used in the minimax theorem. ℜn(,B) R_n( X,B) Worst-case minimax size-generalization risk. sd⋆,θd,j⋆s_d , _d,j Equivariant field target and its coefficients in the optional score or denoising specialization. ℐd,k,d,kI_d,k,J_d,k Degree-at-most-k equivariant feature indices for sets and graphs. mr(k),Mr(k)m_r(k),M_r(k) Stable dimensions of the set and graph equivariant feature spaces. α,σα,σ Uniform curvature constant and gradient-noise scale in the auxiliary estimation bound. C,c,ciC,c,c_i Positive constants independent of n,d,Dn,d,D; their values may change between displays.