尺寸泛化的维度无关缩放定律：指数级分离

# Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation
Source: [https://arxiv.org/html/2610.19279](https://arxiv.org/html/2610.19279)
Behrooz Tahmasebi & Melanie WeberAffiliation:Harvard John A\. Paulson School of Engineering and Applied Sciences \(SEAS\)Affiliation:Harvard University, Cambridge, MA 02138, USAEmail:[\{behrooz\_tahmasebi,mweber\}@seas\.harvard\.edu](mailto:)

###### 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\. Lettingnndenote the number of training samples, we show that polynomial source decay is insufficient for efficient size generalization: while it yields errorn−Θ⁡\(1\)n^\{\-\\Theta\(1\)\}and hence polynomial sample complexity for in\-domain learning, size\-generalization error decays only as\(log⁡n\)−Θ⁡\(1\)\(\\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 errorn−Θ⁡\(1\)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\.

## 1Introduction

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](https://arxiv.org/html/2610.19279#bib.bib10);[Weber, 2025](https://arxiv.org/html/2610.19279#bib.bib22)\)and is often studied as*size generalization*for sets and graphs\([Yehudai et al\., 2021](https://arxiv.org/html/2610.19279#bib.bib35);[Bevilacqua et al\., 2021](https://arxiv.org/html/2610.19279#bib.bib36)\)\.

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](https://arxiv.org/html/2610.19279#bib.bib28);[Keriven et al\., 2020](https://arxiv.org/html/2610.19279#bib.bib30);[Levie et al\., 2021](https://arxiv.org/html/2610.19279#bib.bib29);[Levin et al\., 2025](https://arxiv.org/html/2610.19279#bib.bib27)\), while another develops learning rules across dimensions using representation stability\([Farb, 2014](https://arxiv.org/html/2610.19279#bib.bib40);[Levin and Díaz, 2024](https://arxiv.org/html/2610.19279#bib.bib38);[Levin and Chandrasekaran, 2023](https://arxiv.org/html/2610.19279#bib.bib37);[Díaz et al\., 2025](https://arxiv.org/html/2610.19279#bib.bib39)\)\. 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](https://arxiv.org/html/2610.19279#bib.bib12)\)and graph neural networks\([Scarselli et al\., 2008](https://arxiv.org/html/2610.19279#bib.bib57)\), 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 numbernnof 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: givennnsamples at sizedd, can we control the generalization error simultaneously at every target sizeD≥dD\\geq d, using a number of samples independent of bothddandDD?

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 asn−Θ⁡\(1\)n^\{\-\\Theta\(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\.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\(log⁡n\)−Θ⁡\(1\)\(\\log n\)^\{\-\\Theta\(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 sizedd\(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 asd−Θ⁡\(1\)d^\{\-\\Theta\(1\)\}whenD≥dD\\geq d\. By contrast, our generalization gap converges to zero with the number of training samplesnnand is uniform over bothddandDD, 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\(log⁡n\)−Θ⁡\(1\)\(\\log n\)^\{\-\\Theta\(1\)\}ton−Θ⁡\(1\)n^\{\-\\Theta\(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](https://arxiv.org/html/2610.19279#S1.T1)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](https://arxiv.org/html/2610.19279#S4)and Theorem[4\.1](https://arxiv.org/html/2610.19279#S4.Thmtheorem1)\)\.
- •We show that size generalization is fundamentally harder than classical in\-domain statistical learning: under polynomial source decay, in\-domain error isn−Θ⁡\(1\)n^\{\-\\Theta\(1\)\}, while size\-generalization error is only\(log⁡n\)−Θ⁡\(1\)\(\\log n\)^\{\-\\Theta\(1\)\}, implying an exponential separation in sample complexity \(Theorem[4\.1](https://arxiv.org/html/2610.19279#S4.Thmtheorem1)and Corollary[4\.3](https://arxiv.org/html/2610.19279#S4.Thmtheorem3)\)\.
- •We show that under exponential source decay, size\-generalization error becomesn−Θ⁡\(1\)n^\{\-\\Theta\(1\)\}, recovering polynomial sample complexity independently of object size, at the cost of stronger regularity \(Theorem[4\.1](https://arxiv.org/html/2610.19279#S4.Thmtheorem1)\)\.
- •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](https://arxiv.org/html/2610.19279#S4.Thmtheorem2)\)\.

## 2Related 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](https://arxiv.org/html/2610.19279#bib.bib28);[Keriven et al\., 2020](https://arxiv.org/html/2610.19279#bib.bib30);[Levie et al\., 2021](https://arxiv.org/html/2610.19279#bib.bib29);[Ruiz et al\., 2023](https://arxiv.org/html/2610.19279#bib.bib31);[Maskey et al\., 2023](https://arxiv.org/html/2610.19279#bib.bib32);[Cai and Wang, 2022](https://arxiv.org/html/2610.19279#bib.bib33);[Le and Jegelka, 2023](https://arxiv.org/html/2610.19279#bib.bib59);[Herbst and Jegelka, 2025](https://arxiv.org/html/2610.19279#bib.bib34)\)\. Related work studies learning across set cardinalities and learning\-theoretic formulations of graph size generalization\([Zweig and Bruna, 2021](https://arxiv.org/html/2610.19279#bib.bib58);[Maehara and NT, 2021](https://arxiv.org/html/2610.19279#bib.bib72)\)\. 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](https://arxiv.org/html/2610.19279#bib.bib40)\), 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](https://arxiv.org/html/2610.19279#bib.bib38)\), optimization across dimensions\([Levin and Chandrasekaran, 2023](https://arxiv.org/html/2610.19279#bib.bib37)\), graph limits\([Levin and Chandrasekaran, 2026](https://arxiv.org/html/2610.19279#bib.bib56)\), scientific computing and PDEs\([Phan et al\., 2025](https://arxiv.org/html/2610.19279#bib.bib53)\), and finite\-dimensional kernel learning under invariances\([Díaz et al\., 2025](https://arxiv.org/html/2610.19279#bib.bib39)\)\. The work of[Levin et al\. \(2025\)](https://arxiv.org/html/2610.19279#bib.bib27), 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\.

## 3Problem Statement

#### Sets and \(attributed\) graphs\.

We study problems indexed by the object sizedd, the number of elements in a set or nodes in a graph, and fix a feature dimensionr∈ℕr\\in\\mathbb\{N\}\. A set is represented byX=\(x1,…,xd\)∈\(ℝr\)d≃ℝr×dX=\(x\_\{1\},\\ldots,x\_\{d\}\)\\in\(\\mathbb\{R\}^\{r\}\)^\{d\}\\simeq\\mathbb\{R\}^\{r\\times d\}, while an attributed graph is represented byX∈ℝr×d×dX\\in\\mathbb\{R\}^\{r\\times d\\times d\}, withrredge and/or node\-feature channels\. Accordingly,𝒳d\\mathcal\{X\}\_\{d\}denotesℝr×d\\mathbb\{R\}^\{r\\times d\}orℝr×d×d\\mathbb\{R\}^\{r\\times d\\times d\}\. These matrix and tensor representations are ordered, but the underlying sets and graphs are not\. We equip𝒳d\\mathcal\{X\}\_\{d\}with the standard Gaussian probability measureλd\\lambda\_\{d\}, under which the vectorized entries are independent𝒩⁡\(0,1\)\\mathcal\{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\. WriteZi=XiZ\_\{i\}=X\_\{i\}in the unsupervised setting, whereXi​∼i\.i\.d\.​μdX\_\{i\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}\\mu\_\{d\}andd​μd=fd⋆​d​λdd\\mu\_\{d\}=f\_\{d\}^\{\\star\}d\\lambda\_\{d\}, and writeZi=\(Xi,Yi\)Z\_\{i\}=\(X\_\{i\},Y\_\{i\}\)in the supervised setting, where\(Xi,Yi\)​∼i\.i\.d\.​ρd\(X\_\{i\},Y\_\{i\}\)\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}\\rho\_\{d\},Yi∈ℝY\_\{i\}\\in\\mathbb\{R\}, theXX\-marginal isμd\\mu\_\{d\}, andfd⋆​\(x\)=𝔼⁡\[Y∣X=x\]f\_\{d\}^\{\\star\}\(x\)=\\mathbb\{E\}\[Y\\mid X=x\]\. Letℋd=L2​\(λd\)\\mathcal\{H\}\_\{d\}=L^\{2\}\(\\lambda\_\{d\}\)for density estimation andℋd=L2​\(μd\)\\mathcal\{H\}\_\{d\}=L^\{2\}\(\\mu\_\{d\}\)for regression, and assumefd⋆∈ℱd⊆ℋdf\_\{d\}^\{\\star\}\\in\\mathcal\{F\}\_\{d\}\\subseteq\\mathcal\{H\}\_\{d\}is the target function to estimate\. For the corresponding lossℓd​\(Z,f\)\\ell\_\{d\}\(Z,f\), define

L^n,d​\(f\)=1n​∑i=1nℓd​\(Zi,f\),Ld​\(f\)=𝔼⁡\[ℓd​\(Z,f\)\]\.\\widehat\{L\}\_\{n,d\}\(f\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\ell\_\{d\}\(Z\_\{i\},f\),\\qquad L\_\{d\}\(f\)=\\mathbb\{E\}\[\\ell\_\{d\}\(Z,f\)\]\.We assume thatℓd\\ell\_\{d\}identifiesfd⋆f\_\{d\}^\{\\star\}: the target has finite population risk and is the unique minimizer ofLdL\_\{d\}overℱd\\mathcal\{F\}\_\{d\}as an element ofL2L^\{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\]<∞\\mathbb\{E\}\[Y^\{2\}\]<\\infty; more generally, proper losses identify their associated population targets\. Becauseμd\\mu\_\{d\}orρd\\rho\_\{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](https://arxiv.org/html/2610.19279#A2.SS2)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\.

LetSdS\_\{d\}be the symmetric group\. A permutationπ∈Sd\\pi\\in S\_\{d\}acts on sets by\(π⋅X\):,j=X:,π−1\(j\)\(\\pi\\cdot X\)\_\{:,j\}=X\_\{:,\\pi^\{\-1\}\(j\)\}and on graphs by\(π⋅X\)a,i,j=Xa,π−1​\(i\),π−1​\(j\)\(\\pi\\cdot X\)\_\{a,i,j\}=X\_\{a,\\pi^\{\-1\}\(i\),\\pi^\{\-1\}\(j\)\}\. Because elements and nodes are unlabeled, we assumeπ⋅X​=law​X\\pi\\cdot X\\overset\{\\mathrm\{law\}\}\{=\}Xfor density estimation and\(π⋅X,Y\)​=law​\(X,Y\)\(\\pi\\cdot X,Y\)\\overset\{\\mathrm\{law\}\}\{=\}\(X,Y\)for regression\. Invariance ofμd\\mu\_\{d\}andλd\\lambda\_\{d\}, together with uniqueness of the density, givesfd⋆​\(π⋅x\)=fd⋆​\(x\)f\_\{d\}^\{\\star\}\(\\pi\\cdot x\)=f\_\{d\}^\{\\star\}\(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​π∈Sd\}\\mathcal\{F\}\_\{d\}^\{\\mathrm\{inv\}\}\\coloneqq\\\{f\\in\\mathcal\{F\}\_\{d\}:f\(\\pi\\cdot x\)=f\(x\)\\text\{ a\.e\. for every \}\\pi\\in S\_\{d\}\\\}, and the invariant empirical risk minimizer is

f^n,dinv∈arg⁡minf∈ℱdinv​L^n,d​\(f\)\.\\hat\{f\}\_\{n,d\}^\{\\mathrm\{inv\}\}\\in\\arg\\min\_\{f\\in\\mathcal\{F\}\_\{d\}^\{\\mathrm\{inv\}\}\}\\widehat\{L\}\_\{n,d\}\(f\)\.Appendix[B\.1](https://arxiv.org/html/2610.19279#A2.SS1)provides the formal background\.

#### Exact functional transfer across sizes\.

Letℋdinv⊆ℋd\\mathcal\{H\}\_\{d\}^\{\\mathrm\{inv\}\}\\subseteq\\mathcal\{H\}\_\{d\}be the Hilbert space of invariant functions containingℱdinv\\mathcal\{F\}\_\{d\}^\{\\mathrm\{inv\}\}, with the correspondingL2L^\{2\}norm∥⋅∥d\\\|\\cdot\\\|\_\{d\}\. Ford≤Dd\\leq D, let

Td→D:ℋdinv⟶ℋDinvT\_\{d\\to D\}:\\mathcal\{H\}\_\{d\}^\{\\mathrm\{inv\}\}\\longrightarrow\\mathcal\{H\}\_\{D\}^\{\\mathrm\{inv\}\}be a linear operator satisfyingTd→D​\(ℱdinv\)⊆ℱDinvT\_\{d\\to D\}\(\\mathcal\{F\}\_\{d\}^\{\\mathrm\{inv\}\}\)\\subseteq\\mathcal\{F\}\_\{D\}^\{\\mathrm\{inv\}\}\. It maps an entire rule, independently of its parameterization, from sizeddto sizeDD\. We assume coherence,Td→d=IdT\_\{d\\to d\}=\\mathrm\{Id\}andTD→E∘Td→D=Td→ET\_\{D\\to E\}\\circ T\_\{d\\to D\}=T\_\{d\\to E\}ford≤D≤Ed\\leq D\\leq E; exact target transfer,Td→D​fd⋆=fD⋆T\_\{d\\to D\}f\_\{d\}^\{\\star\}=f\_\{D\}^\{\\star\}; and norm preservation,‖Td→D​f−Td→D​h‖D=‖f−h‖d\\\|T\_\{d\\to D\}f\-T\_\{d\\to D\}h\\\|\_\{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](https://arxiv.org/html/2610.19279#bib.bib27)\)\.

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](https://arxiv.org/html/2610.19279#bib.bib12);[Xu et al\., 2019](https://arxiv.org/html/2610.19279#bib.bib26);[Ruiz et al\., 2020](https://arxiv.org/html/2610.19279#bib.bib28);[Levin and Díaz, 2024](https://arxiv.org/html/2610.19279#bib.bib38);[Levin et al\., 2025](https://arxiv.org/html/2610.19279#bib.bib27)\)\. The map need not cover every function at sizeDD; it only carries the same rule to the larger domain while preserving its error scale\. Without such a connection, size\-dddata would contain no information about an arbitrary size\-DDtarget\. Appendices[B\.3](https://arxiv.org/html/2610.19279#A2.SS3)and[C](https://arxiv.org/html/2610.19279#A3)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\\psi\_\{d,j\}denote the normalized measurement of patternjjon an object of sizedd\. The same indexjjrefers to the same pattern at every size\. A rule∑jaj​ψd,j\\sum\_\{j\}a\_\{j\}\\psi\_\{d,j\}is therefore transferred to sizeDDsimply by reusing the learned weights:

Td→D​\(∑jaj​ψd,j\)=∑jaj​ψD,j\.T\_\{d\\to D\}\\\!\\left\(\\sum\_\{j\}a\_\{j\}\\psi\_\{d,j\}\\right\)=\\sum\_\{j\}a\_\{j\}\\psi\_\{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](https://arxiv.org/html/2610.19279#A2.SS3)and[C](https://arxiv.org/html/2610.19279#A3)construct these features explicitly for sets and graphs\.

#### The statistical objective: generalization across size\.

Training uses onlynnsamples at sizedd\. At any target sizeD≥dD\\geq d, the learned function isTd→D​f^n,dinvT\_\{d\\to D\}\\hat\{f\}\_\{n,d\}^\{\\mathrm\{inv\}\}\. Our goal is a guarantee whose sample complexity is independent of both sizes:

Dimension\-free size generalization\.For every accuracyε\>0\\varepsilon\>0and confidence level1−δ1\-\\delta, findn=n⁡\(ε,δ\)n=n\(\\varepsilon,\\delta\), independent ofddandDD, such that, with probability at least1−δ1\-\\delta,supD≥d‖Td→D​f^n,dinv−fD⋆‖D2≤ε\.\\sup\_\{D\\geq d\}\\bigl\\\|T\_\{d\\to D\}\\hat\{f\}\_\{n,d\}^\{\\mathrm\{inv\}\}\-f\_\{D\}^\{\\star\}\\bigr\\\|\_\{D\}^\{2\}\\leq\\varepsilon\.

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

## 4Main 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\.1Invariant polynomial coordinates and representation stability

Recall the domain𝒳d\\mathcal\{X\}\_\{d\}, target classℱd\\mathcal\{F\}\_\{d\}, and Hilbert spaceℋd\\mathcal\{H\}\_\{d\}from Section[3](https://arxiv.org/html/2610.19279#S3)\. Thus,ℱd⊆ℋdinv\\mathcal\{F\}\_\{d\}\\subseteq\\mathcal\{H\}\_\{d\}^\{\\mathrm\{inv\}\}, withℋd=L2​\(λd\)\\mathcal\{H\}\_\{d\}=L^\{2\}\(\\lambda\_\{d\}\)for density estimation andℋd=L2​\(μd\)\\mathcal\{H\}\_\{d\}=L^\{2\}\(\\mu\_\{d\}\)for regression\.

To organize this infinite\-dimensional space, let𝒱d,k\\mathcal\{V\}\_\{d,k\}be the span of all invariant polynomials of degree at mostkkon𝒳d\\mathcal\{X\}\_\{d\}\. Under the standard completeness conditions stated in the appendix, polynomials are dense inℋd\\mathcal\{H\}\_\{d\}; averaging over relabelings then makes invariant polynomials dense inℋdinv\\mathcal\{H\}\_\{d\}^\{\\mathrm\{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 increasingkkprogressively resolves richer dependencies among elements or nodes\.

An orthonormal basis for𝒱d,k\\mathcal\{V\}\_\{d,k\}is obtained by applying Gram–Schmidt inℋd\\mathcal\{H\}\_\{d\}, with inner product⟨⋅,⋅⟩d\\langle\\cdot,\\cdot\\rangle\_\{d\}\. Orthogonalization changes only the coordinates, not the polynomial span or its dimension\. The resulting nested spaces

𝒱d,0⊆𝒱d,1⊆⋯⊆ℋdinv\\mathcal\{V\}\_\{d,0\}\\subseteq\\mathcal\{V\}\_\{d,1\}\\subseteq\\cdots\\subseteq\\mathcal\{H\}\_\{d\}^\{\\mathrm\{inv\}\}are compatible with the exact transfer operators, and representation stability controls their complexity uniformly over object size\. Specifically, for𝖷∈\{set,graph\}\\mathsf\{X\}\\in\\\{\\mathrm\{set\},\\mathrm\{graph\}\\\}, define

q𝖷​\(k\)≔supd≥1dim\(𝒱d,k\)\.q\_\{\\mathsf\{X\}\}\(k\)\\coloneqq\\sup\_\{d\\geq 1\}\\dim\(\\mathcal\{V\}\_\{d,k\}\)\.For every fixedkk, the dimensions increase to a stable value, so the supremum equals that value and bounds every size, including the pre\-stable regime\([Farb, 2014](https://arxiv.org/html/2610.19279#bib.bib40)\)\.

For setsX∈ℝr×dX\\in\\mathbb\{R\}^\{r\\times d\}, these are multisymmetric polynomials\. Hardy–Ramanujan and Meinardus partition asymptotics, detailed in Appendix[B\.5](https://arxiv.org/html/2610.19279#A2.SS5), give

qset​\(k\)=exp⁡\(Cr​kβ\+o⁡\(kβ\)\),β=rr\+1\.q\_\{\\mathrm\{set\}\}\(k\)=\\exp\\\!\\left\(C\_\{r\}k^\{\\beta\}\+o\(k^\{\\beta\}\)\\right\),\\qquad\\beta=\\frac\{r\}\{r\+1\}\.HereCr=r\+1r​\(r​ζ​\(r\+1\)\)1/\(r\+1\)C\_\{r\}=\\frac\{r\+1\}\{r\}\\bigl\(r\\zeta\(r\+1\)\\bigr\)^\{1/\(r\+1\)\}, whereζ\\zetais the Riemann zeta function\. For attributed graphsX∈ℝr×d×dX\\in\\mathbb\{R\}^\{r\\times d\\times d\}with at least one edge channel, invariant polynomials are indexed by unlabeled attributed multigraph patterns\. The enumeration in Appendix[B\.7](https://arxiv.org/html/2610.19279#A2.SS7)gives

qgraph​\(k\)=exp⁡\(k​log⁡k\+Or​\(k​log⁡log⁡k\)\)\.q\_\{\\mathrm\{graph\}\}\(k\)=\\exp\\\!\\left\(k\\log k\+O\_\{r\}\(k\\log\\log k\)\\right\)\.For fixedrr, the graph feature dimension depends onrronly through the lower\-order termOr​\(k​log⁡log​k\)O\_\{r\}\(k\\log\\log k\)\. Consequently,rrdoes 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\.2Polynomial and exponential source decay

Letℱd,k=𝒱d,k\\mathcal\{F\}\_\{d,k\}=\\mathcal\{V\}\_\{d,k\}for regression andℱd,k=ℱdinv∩𝒱d,k\\mathcal\{F\}\_\{d,k\}=\\mathcal\{F\}\_\{d\}^\{\\mathrm\{inv\}\}\\cap\\mathcal\{V\}\_\{d,k\}for density estimation, so density approximants remain nonnegative and normalized\. Define the best order\-kkapproximation error and its uniform envelope by

Bd​\(k\)≔inff∈ℱd,k‖fd⋆−f‖d2,B⁡\(k\)≔supd≥1Bd​\(k\)\.B\_\{d\}\(k\)\\coloneqq\\inf\_\{f\\in\\mathcal\{F\}\_\{d,k\}\}\\\|f\_\{d\}^\{\\star\}\-f\\\|\_\{d\}^\{2\},\\qquad B\(k\)\\coloneqq\\sup\_\{d\\geq 1\}B\_\{d\}\(k\)\.For regression, the optimizer is the orthogonal projectionΠd,k​fd⋆\\Pi\_\{d,k\}f\_\{d\}^\{\\star\}; henceB⁡\(k\)B\(k\)is the squared energy in coordinates of degree greater thankk, uniformly overdd\. 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⁡\(−a​kν\),a,ν\>0\.\\begin\{array\}\[\]\{lll\}\\textit\{polynomial source decay:\}&B\(k\)\\lesssim k^\{\-\\tau\},&\\tau\>0,\\\\\[2\.0pt\] \\textit\{exponential source decay:\}&B\(k\)\\lesssim\\exp\(\-ak^\{\\nu\}\),&a,\\nu\>0\.\\end\{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ν\\nudetermines whether this decay is fast enough to overcome the growth of invariant interactions\.

### 4\.3Dimension\-free scaling laws

For an interaction orderkk, letfd,k∘f\_\{d,k\}^\{\\circ\}minimize the population risk overℱd,k\\mathcal\{F\}\_\{d,k\}, and letf^n,d,kinv\\hat\{f\}\_\{n,d,k\}^\{\\mathrm\{inv\}\}be its empirical counterpart\. We impose standard, primitive regularity conditions on this finite\-dimensional problem\. In orthonormal coordinates on𝒱d,k\\mathcal\{V\}\_\{d,k\}, the population approximation satisfies‖fd,k∘−fd⋆‖d2≲Bd​\(k\)\\\|f\_\{d,k\}^\{\\circ\}\-f\_\{d\}^\{\\star\}\\\|\_\{d\}^\{2\}\\lesssim B\_\{d\}\(k\); the empirical loss has curvature at leastα\>0\\alpha\>0on the relevant neighborhood; and the centered empirical score atfd,k∘f\_\{d,k\}^\{\\circ\}is sub\-Gaussian with parameter at mostσ2\\sigma^\{2\}\. The constantsα\\alphaandσ\\sigmaare uniform inddandkk\. Here, curvature means that moving the fitted function byhhincreases the loss by at leastα​‖h‖d2/2\\alpha\\\|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\}^\{\\star\}\)=\\\|f\-f\_\{d\}^\{\\star\}\\\|\_\{L^\{2\}\(\\mu\_\{d\}\)\}^\{2\},so approximation is exactly measured byBd​\(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 squaredL2​\(λd\)L^\{2\}\(\\lambda\_\{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](https://arxiv.org/html/2610.19279#A6)derives the finite\-dimensional estimation bound from these assumptions rather than postulating it\.

Table[2](https://arxiv.org/html/2610.19279#S4.T2)compares our dimension\-free rates with classical in\-domain learning\. At a fixed sizedd, the number of degree\-at\-most\-kkinvariant polynomial features grows askr​dk^\{rd\}for sets andkr​d2k^\{rd^\{2\}\}for graphs under our tensor representation; invariance under the finite groupSdS\_\{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\.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](https://arxiv.org/html/2610.19279#A4); 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, compatibilityTd→D​\(ℱd,k\)⊆ℱD,kT\_\{d\\to D\}\(\\mathcal\{F\}\_\{d,k\}\)\\subseteq\\mathcal\{F\}\_\{D,k\}, and the uniform loss regularity above\. For any fixed confidence level, there are invariant empirical estimators, trained using only size\-dddata, whose squared error holds simultaneously for everyD≥dD\\geq dand satisfies the following rates, independently ofddandDD:

1. \(i\)IfB⁡\(k\)≲k−τB\(k\)\\lesssim k^\{\-\\tau\}, the rate is \(logn\)−τ\(r\+1\)/rfor sets,\(log⁡nlog⁡log⁡n\)−τfor graphs\.\(\\log n\)^\{\-\\tau\(r\+1\)/r\}\\quad\\text\{for sets\},\\qquad\\left\(\\frac\{\\log n\}\{\\log\\log n\}\\right\)^\{\-\\tau\}\\quad\\text\{for graphs\}\.
2. \(ii\)IfB⁡\(k\)≲e−a​kνB\(k\)\\lesssim e^\{\-ak^\{\\nu\}\}, the set rate, withβ=r/\(r\+1\)\\beta=r/\(r\+1\), is \{n−1\+o⁡\(1\),ν\>β,n−a/\(a\+Cr\)\+o\(1\),ν=β,exp\[−aCr−ν/β\(logn\)ν/β\(1\+o\(1\)\)\],0<ν<β,\\begin\{cases\}n^\{\-1\+o\(1\)\},&\\nu\>\\beta,\\\\ n^\{\-a/\(a\+C\_\{r\}\)\+o\(1\)\},&\\nu=\\beta,\\\\ \\exp\\\!\\left\[\-aC\_\{r\}^\{\-\\nu/\\beta\}\(\\log n\)^\{\\nu/\\beta\}\(1\+o\(1\)\)\\right\],&0<\\nu<\\beta,\\end\{cases\}while the graph rate isn−1\+o⁡\(1\)n^\{\-1\+o\(1\)\}forν\>1\\nu\>1and exp⁡\[−a​\(log⁡nlog⁡log⁡n\)ν​\(1\+o⁡\(1\)\)\]for​0<ν≤1\.\\exp\\\!\\left\[\-a\\left\(\\frac\{\\log n\}\{\\log\\log n\}\\right\)^\{\\nu\}\(1\+o\(1\)\)\\right\]\\quad\\text\{for \}0<\\nu\\leq 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 overDD\. 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\.4Why classical in\-domain power laws change

In classical fixed\-domain nonparametric learning, the number of features up to resolutionkkoften grows polynomially, sayq⁡\(k\)≍ksq\(k\)\\asymp k^\{s\}\. Polynomial source decayB⁡\(k\)≍k−τB\(k\)\\asymp k^\{\-\\tau\}then produces the familiar power lawn−τ/\(τ\+s\)n^\{\-\\tau/\(\\tau\+s\)\}\. Size generalization on sets and graphs is different\. Uniformity over every larger size exposes all invariant interactions, whose stable counts grow as

exp⁡\(Cr​kr/\(r\+1\)\)andexp⁡\(k​log⁡k\),\\exp\(C\_\{r\}k^\{r/\(r\+1\)\}\)\\quad\\text\{and\}\\quad\\exp\(k\\log k\),respectively\. Consequently, the same polynomial source decay yields only logarithmic convergence innn\. 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\)\\mathfrak\{F\}\_\{\\mathsf\{X\}\}\(B\)contain all size\-consistent targets of type𝖷∈\{set,graph\}\\mathsf\{X\}\\in\\\{\\mathrm\{set\},\\mathrm\{graph\}\\\}with source envelopeBB\. 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\]\.\\mathfrak\{R\}\_\{n\}\(\\mathsf\{X\},B\)\\coloneqq\\inf\_\{\\hat\{\\bm\{f\}\}\}\\sup\_\{d\\geq 1\}\\sup\_\{\\bm\{f\}^\{\\star\}\\in\\mathfrak\{F\}\_\{\\mathsf\{X\}\}\(B\)\}\\mathbb\{E\}\\\!\\left\[\\sup\_\{D\\geq d\}\\\|\\hat\{f\}\_\{D\}\-f\_\{D\}^\{\\star\}\\\|\_\{D\}^\{2\}\\right\]\.For the lower bound, the source class must genuinely contain the invariant directions counted by representation stability\. Concretely, at every orderkk, we require a stable\-size regression or density submodel withq𝖷​\(k\)q\_\{\\mathsf\{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](https://arxiv.org/html/2610.19279#A5)states and verifies the precise construction\.

###### Theorem 4\.2\(Minimax optimality\)\.

Under the preceding local richness condition, every rate in Theorem[4\.1](https://arxiv.org/html/2610.19279#S4.Thmtheorem1)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−τ\)≍\(log⁡nlog⁡log⁡n\)−τ\.\\mathfrak\{R\}\_\{n\}\(\\mathrm\{set\},k^\{\-\\tau\}\)\\asymp\(\\log n\)^\{\-\\tau\(r\+1\)/r\},\\qquad\\mathfrak\{R\}\_\{n\}\(\\mathrm\{graph\},k^\{\-\\tau\}\)\\asymp\\left\(\\frac\{\\log n\}\{\\log\\log n\}\\right\)^\{\-\\tau\}\.For exponential source decay, the minimax risks have the same supercritical, critical, and subcritical regimes stated in Theorem[4\.1](https://arxiv.org/html/2610.19279#S4.Thmtheorem1)\. These lower bounds hold already at a suitable stable training size and therefore continue to hold when the loss takes a supremum over allD≥dD\\geq d\.

The theorem rules out improvements by a different architecture, regularizer, optimization method, or transfer rule: the infimum inℜn\\mathfrak\{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 fromnnobservations\. 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 supposeB⁡\(k\)≍k−τB\(k\)\\asymp k^\{\-\\tau\}\. Up to constants and lower\-order factors, achieving squared error at mostε\\varepsilonat a fixed size requires

nin​\(ε\)=\{ε−\(τ\+rd\)/τ,sets,ε−\(τ\+rd2\)/τ,graphs,n\_\{\\mathrm\{in\}\}\(\\varepsilon\)=\\begin\{cases\}\\varepsilon^\{\-\(\\tau\+rd\)/\\tau\},&\\text\{sets\},\\\\ \\varepsilon^\{\-\(\\tau\+rd^\{2\}\)/\\tau\},&\\text\{graphs\},\\end\{cases\}whereas uniform size generalization requires

nsize​\(ε\)=\{exp⁡\(Θ⁡\(ε−rτ⁡\(r\+1\)\)\),sets,exp\(Θ\(ε−1/τlog\(1/ε\)\)\),graphs\.n\_\{\\mathrm\{size\}\}\(\\varepsilon\)=\\begin\{cases\}\\displaystyle\\exp\\\!\\left\(\\Theta\\\!\\left\(\\varepsilon^\{\-\\frac\{r\}\{\\tau\(r\+1\)\}\}\\right\)\\right\),&\\text\{sets\},\\\\\[5\.0pt\] \\displaystyle\\exp\\\!\\left\(\\Theta\\\!\\left\(\\varepsilon^\{\-1/\\tau\}\\log\(1/\\varepsilon\)\\right\)\\right\),&\\text\{graphs\}\.\\end\{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\.5Discussion

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

## 5Conclusion

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, andLaTeXpresentation\. 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

- M\. Atzmon, K\. Nagano, S\. Fidler, S\. Khamis, and Y\. LipmanFrame averaging for equivariant shape space learning\.InIEEE Conference on Computer Vision and Pattern Recognition \(CVPR\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Bevilacquaet al\.\(2021\)B\. Bevilacqua, Y\. Zhou, and B\. RibeiroSize\-invariant graph representations for graph classification extrapolations\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§1](https://arxiv.org/html/2610.19279#S1.p1.1)\.
- Bloem\-Reddy and Teh \(2020\)B\. Bloem\-Reddy and Y\. W\. TehProbabilistic symmetries and invariant neural networks\.Journal of Machine Learning Research21\(90\),pp\. 1–61\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Bogatskiyet al\.\(2020\)A\. Bogatskiy, B\. Anderson, J\. Offermann, M\. Roussi, D\. Miller, and R\. KondorLorentz group equivariant neural network for particle physics\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Bonginiet al\.\(2021\)P\. Bongini, M\. Bianchini, and F\. ScarselliMolecular generative graph neural networks for drug discovery\.Neurocomputing450,pp\. 242–252\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Bronsteinet 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](https://arxiv.org/html/2610.19279#S1.p1.1)\.
- Buffelliet al\.\(2022\)D\. Buffelli, P\. Liò, and F\. VandinSizeshiftreg: a regularization method for improving size\-generalization in graph neural networks\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px2.p1.1)\.
- Cai and Wang \(2022\)C\. Cai and Y\. WangConvergence of invariant graph networks\.InInt\. Conference on Machine Learning \(ICML\),pp\. 2457–2484\.Cited by:[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px1.p1.1)\.
- Caponnetto and De Vito \(2007\)A\. Caponnetto and E\. De VitoOptimal rates for the regularized least\-squares algorithm\.Foundations of Computational mathematics7\(3\),pp\. 331–368\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px4.p1.1)\.
- Chenet al\.\(2023\)Z\. Chen, M\. Katsoulakis, L\. Rey\-Bellet, and W\. ZhuSample complexity of probability divergences under group symmetry\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Chuet al\.\(2023\)X\. Chu, Y\. Jin, X\. Wang, S\. Zhang, Y\. Wang, W\. Zhu, and H\. MeiWasserstein barycenter matching for graph size generalization of message passing neural networks\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px2.p1.1)\.
- Chuang and Jegelka \(2022\)C\. Chuang and S\. JegelkaTree mover’s distance: bridging graph metrics and stability of graph neural networks\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px2.p1.1)\.
- Diaconis and Janson \(2008\)P\. Diaconis and S\. JansonGraph limits and exchangeable random graphs\.Rendiconti di Matematica, Serie VII28,pp\. 33–61\.Cited by:[§B\.3](https://arxiv.org/html/2610.19279#A2.SS3.SSS0.Px2.p1.1)\.
- Díazet al\.\(2025\)M\. Díaz, D\. Drusvyatskiy, J\. Kendrick, and R\. R\. ThomasInvariant kernels: rank stabilization and generalization across dimensions\.arXiv preprint arXiv:2502\.01886\.Cited by:[§1](https://arxiv.org/html/2610.19279#S1.p2.1),[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px2.p1.1)\.
- Dymet al\.\(2024\)N\. Dym, H\. Lawrence, and J\. W\. SiegelEquivariant frames and the impossibility of continuous canonicalization\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Elesedy \(2021\)B\. ElesedyProvably strict generalisation benefit for invariance in kernel methods\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Farb \(2014\)B\. FarbRepresentation stability\.arXiv preprint arXiv:1404\.4065\.Cited by:[§1](https://arxiv.org/html/2610.19279#S1.p2.1),[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px2.p1.1),[§4\.1](https://arxiv.org/html/2610.19279#S4.SS1.p3.3)\.
- Garget al\.\(2020\)V\. Garg, S\. Jegelka, and T\. JaakkolaGeneralization and representational limits of graph neural networks\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Herbst and Jegelka \(2025\)D\. Herbst and S\. JegelkaHigher\-order graphon neural networks: approximation and cut distance\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px1.p1.1)\.
- Huanget al\.\(2024\)Z\. Huang, Q\. Yang, D\. Zhou, and Y\. YanEnhancing size generalization in graph neural networks through disentangled representation learning\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px2.p1.1)\.
- Juet al\.\(2023\)H\. Ju, D\. Li, A\. Sharma, and H\. R\. ZhangGeneralization in graph neural networks: improved pac\-bayesian bounds on graph diffusion\.InInt\. Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Kabaet al\.\(2023\)S\. Kaba, A\. K\. Mondal, Y\. Zhang, Y\. Bengio, and S\. RavanbakhshEquivariance with learned canonicalization functions\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Kerivenet al\.\(2020\)N\. Keriven, A\. Bietti, and S\. VaiterConvergence and stability of graph convolutional networks on large random graphs\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Vol\.33,pp\. 21512–21523\.Cited by:[§1](https://arxiv.org/html/2610.19279#S1.p2.1),[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px1.p1.1)\.
- Le and Jegelka \(2023\)T\. Le and S\. JegelkaLimits, approximation and size transferability for gnns on sparse graphs via graphops\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px1.p1.1)\.
- Levieet al\.\(2021\)R\. Levie, W\. Huang, L\. Bucci, M\. Bronstein, and G\. KutyniokTransferability of spectral graph convolutional neural networks\.Journal of Machine Learning Research22\(272\),pp\. 1–59\.Cited by:[§1](https://arxiv.org/html/2610.19279#S1.p2.1),[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px1.p1.1)\.
- Levie \(2023\)R\. LevieA graphon\-signal analysis of graph neural networks\.Advances in Neural Information Processing Systems36,pp\. 64482–64525\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Levin and Chandrasekaran \(2023\)E\. Levin and V\. ChandrasekaranFree descriptions of convex sets\.arXiv preprint arXiv:2307\.04230\.Cited by:[§1](https://arxiv.org/html/2610.19279#S1.p2.1),[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px2.p1.1)\.
- Levin and Chandrasekaran \(2026\)E\. Levin and V\. ChandrasekaranLimits of weighted graphs via random quotients\.arXiv:2512\.23149\.Cited by:[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px2.p1.1)\.
- Levin and Díaz \(2024\)E\. Levin and M\. DíazAny\-dimensional equivariant neural networks\.InInt\. Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[§B\.3](https://arxiv.org/html/2610.19279#A2.SS3.SSS0.Px1.p1.3),[§1](https://arxiv.org/html/2610.19279#S1.p2.1),[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px2.p1.1),[§3](https://arxiv.org/html/2610.19279#S3.SS0.SSS0.Px4.p2.1)\.
- Levinet al\.\(2025\)E\. Levin, Y\. Ma, M\. Díaz, and S\. VillarOn transferring transferability: towards a theory for size generalization\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§1](https://arxiv.org/html/2610.19279#S1.p2.1),[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px2.p1.1),[§3](https://arxiv.org/html/2610.19279#S3.SS0.SSS0.Px4.p1.2),[§3](https://arxiv.org/html/2610.19279#S3.SS0.SSS0.Px4.p2.1)\.
- Liet al\.\(2023\)X\. Li, L\. Sun, M\. Ling, and Y\. PengA survey of graph neural network based recommendation in social networks\.Neurocomputing549,pp\. 126441\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Liaoet al\.\(2020\)R\. Liao, R\. Urtasun, and R\. ZemelA pac\-bayesian approach to generalization bounds for graph neural networks\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Linet al\.\(2024\)Y\. Lin, J\. Helwig, S\. Gui, and S\. JiEquivariance via minimal frame averaging for more symmetries and efficiency\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Maet al\.\(2024\)G\. Ma, Y\. Wang, D\. Lim, S\. Jegelka, and Y\. WangA canonicalization perspective on invariant and equivariant learning\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Maehara and NT \(2021\)T\. Maehara and H\. NTLearning on random balls is sufficient for estimating \(some\) graph parameters\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px1.p1.1)\.
- Maronet al\.\(2019\)H\. Maron, H\. Ben\-Hamu, N\. Shamir, and Y\. LipmanInvariant and equivariant graph networks\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Maskeyet al\.\(2025\)S\. Maskey, G\. Kutyniok, and R\. LevieGeneralization bounds for message passing networks on mixture of graphons\.SIAM Journal on Mathematics of Data Science7\(2\),pp\. 802–825\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Maskeyet al\.\(2023\)S\. Maskey, R\. Levie, and G\. KutyniokTransferability of graph neural networks: an extended graphon approach\.Applied and Computational Harmonic Analysis63,pp\. 48–83\.Cited by:[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px1.p1.1)\.
- Maskeyet al\.\(2022\)S\. Maskey, R\. Levie, Y\. Lee, and G\. KutyniokGeneralization analysis of message passing neural networks on large random graphs\.Advances in neural information processing systems35,pp\. 4805–4817\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Morriset al\.\(2023\)C\. Morris, F\. Geerts, J\. Tönshoff, and M\. GroheWl meet vc\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Nguyenet al\.\(2024\)Q\. T\. Nguyen, L\. Schatzki, P\. Braccia, M\. Ragone, P\. J\. Coles, F\. Sauvage, M\. Larocca, and M\. CerezoTheory for equivariant quantum neural networks\.PRX Quantum5\(2\),pp\. 020328\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Petrache and Trivedi \(2023\)M\. Petrache and S\. TrivediApproximation\-generalization trade\-offs under \(approximate\) group equivariance\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Phanet al\.\(2025\)T\. V\. Phan, G\. A\. Kevrekidis, S\. Villar, Y\. G\. Kevrekidis, and J\. M\. Bello\-RivasTowards coordinate\-and dimension\-agnostic machine learning for partial differential equations\.arXiv preprint arXiv:2505\.16549\.Cited by:[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px2.p1.1)\.
- Punyet al\.\(2022\)O\. Puny, M\. Atzmon, E\. J\. Smith, I\. Misra, A\. Grover, H\. Ben\-Hamu, and Y\. LipmanFrame averaging for invariant and equivariant network design\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Rauchwergeret al\.\(2025\)L\. Rauchwerger, S\. Jegelka, and R\. LevieGeneralization, expressivity, and universality of graph neural networks on attributed graphs\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Ruizet al\.\(2023\)L\. Ruiz, L\. F\. Chamon, and A\. RibeiroTransferability properties of graph neural networks\.IEEE Transactions on Signal Processing71,pp\. 3474–3489\.Cited by:[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px1.p1.1)\.
- Ruizet al\.\(2020\)L\. Ruiz, L\. Chamon, and A\. RibeiroGraphon neural networks and the transferability of graph neural networks\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Vol\.33,pp\. 1702–1712\.Cited by:[§B\.3](https://arxiv.org/html/2610.19279#A2.SS3.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2610.19279#S1.p2.1),[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px1.p1.1),[§3](https://arxiv.org/html/2610.19279#S3.SS0.SSS0.Px4.p2.1)\.
- Satorraset al\.\(2021\)V\. G\. Satorras, E\. Hoogeboom, and M\. WellingE\(n\) equivariant graph neural networks\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Scarselliet al\.\(2008\)F\. Scarselli, M\. Gori, A\. C\. Tsoi, M\. Hagenbuchner, and G\. MonfardiniThe graph neural network model\.IEEE transactions on neural networks20\(1\),pp\. 61–80\.Cited by:[§1](https://arxiv.org/html/2610.19279#S1.p3.1)\.
- Scarselliet al\.\(2018\)F\. Scarselli, A\. C\. Tsoi, and M\. HagenbuchnerThe Vapnik–Chervonenkis dimension of graph and recursive neural networks\.Neural Networks108,pp\. 248–259\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Shumaylovet al\.\(2025\)Z\. Shumaylov, P\. Zaika, J\. Rowbottom, F\. Sherry, M\. Weber, and C\. SchönliebLie algebra canonicalization: equivariant neural operators under arbitrary Lie groups\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Soleymaniet al\.\(2026a\)A\. Soleymani, B\. Tahmasebi, P\. Jaillet, and S\. JegelkaA unified framework for statistical testing of invariance\.InThe ICML 2026 Workshop on Hypothesis Testing,Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Soleymaniet al\.\(2026b\)A\. Soleymani, B\. Tahmasebi, P\. Jaillet, and S\. JegelkaEfficient learning and symmetry discovery under exact invariances\.InConference on Learning Theory \(COLT\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Soleymaniet al\.\(2025a\)A\. Soleymani, B\. Tahmasebi, S\. Jegelka, and P\. JailletA robust kernel statistical test of invariance: detecting subtle asymmetries\.InInt\. Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Soleymaniet al\.\(2025b\)A\. Soleymani, B\. Tahmasebi, S\. Jegelka, and P\. JailletLearning with exact invariances in polynomial time\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Tahmasebi and Jegelka \(2023\)B\. Tahmasebi and S\. JegelkaThe exact sample complexity gain from invariances for kernel regression\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Tahmasebi and Jegelka \(2024\)B\. Tahmasebi and S\. JegelkaSample complexity bounds for estimating probability divergences under invariances\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Tahmasebi and Jegelka \(2025a\)B\. Tahmasebi and S\. JegelkaGeneralization bounds for canonicalization: a comparative study with group averaging\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Tahmasebi and Jegelka \(2025b\)B\. Tahmasebi and S\. JegelkaRegularity in canonicalized models: a theoretical perspective\.InInt\. Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Tahmasebiet al\.\(2023\)B\. Tahmasebi, D\. Lim, and S\. JegelkaThe power of recursion in graph neural networks for counting substructures\.InInt\. Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Tahmasebiet al\.\(2026\)B\. Tahmasebi, M\. Weber, and S\. JegelkaData augmentation: a fourier analysis perspective\.InConference on Learning Theory \(COLT\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Tahmasebi and Weber \(2026a\)B\. Tahmasebi and M\. WeberAchieving approximate symmetry is exponentially easier than exact symmetry\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Tahmasebi and Weber \(2026b\)B\. Tahmasebi and M\. WeberAdaptive symmetry discovery for dynamical system identification\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Tahmasebi and Weber \(2026c\)B\. Tahmasebi and M\. WeberSparse data augmentation for optimization with provable guarantees\.InIEEE Conference on Decision and Control \(CDC\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Vasileiouet al\.\(2025a\)A\. Vasileiou, B\. Finkelshtein, F\. Geerts, R\. Levie, and C\. MorrisCovered forest: fine\-grained generalization analysis of graph neural networks\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Vasileiouet al\.\(2025b\)A\. Vasileiou, S\. Jegelka, R\. Levie, and C\. MorrisSurvey on generalization theory for graph neural networks\.arXiv preprint arXiv:2503\.15650\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Veličkovićet al\.\(2025\)P\. Veličković, C\. Perivolaropoulos, F\. Barbero, and R\. PascanuSoftmax is not enough \(for sharp size generalisation\)\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px2.p1.1)\.
- Wagstaffet al\.\(2019\)E\. Wagstaff, F\. Fuchs, M\. Engelcke, I\. Posner, and M\. A\. OsborneOn the limitations of representing functions on sets\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Wanget al\.\(2022\)D\. Wang, R\. Walters, and R\. PlattSO⁡\(2\)\\mathrm\{SO\}\(2\)\-Equivariant reinforcement learning\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1)\.
- Wanget al\.\(2021\)R\. Wang, R\. Walters, and R\. YuIncorporating symmetry into deep dynamics models for improved generalization\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px3.p1.1)\.
- Wanget al\.\(2025\)Z\. Wang, J\. Cervino, and A\. RibeiroA manifold perspective on the statistical generalization of graph neural networks\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px2.p1.1)\.
- Weber \(2025\)M\. WeberGeometric machine learning\.Wiley Online Library\.Cited by:[§1](https://arxiv.org/html/2610.19279#S1.p1.1)\.
- Xuet al\.\(2019\)K\. Xu, W\. Hu, J\. Leskovec, and S\. JegelkaHow powerful are graph neural networks?\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1),[§B\.3](https://arxiv.org/html/2610.19279#A2.SS3.SSS0.Px1.p1.3),[§3](https://arxiv.org/html/2610.19279#S3.SS0.SSS0.Px4.p2.1)\.
- Yehudaiet al\.\(2021\)G\. Yehudai, E\. Fetaya, E\. Meirom, G\. Chechik, and H\. MaronFrom local structures to size generalization in graph neural networks\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§1](https://arxiv.org/html/2610.19279#S1.p1.1)\.
- Zaheeret al\.\(2017\)M\. Zaheer, S\. Kottur, S\. Ravanbakhsh, B\. Poczos, R\. R\. Salakhutdinov, and A\. J\. SmolaDeep sets\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px1.p1.1),[§B\.3](https://arxiv.org/html/2610.19279#A2.SS3.SSS0.Px1.p1.3),[§1](https://arxiv.org/html/2610.19279#S1.p3.1),[§3](https://arxiv.org/html/2610.19279#S3.SS0.SSS0.Px4.p2.1)\.
- Zhanget al\.\(2025\)H\. Zhang, Y\. Li, W\. Lu, and Q\. LinOptimal rates of kernel ridge regression under source condition in large dimensions\.Journal of Machine Learning Research26\(219\),pp\. 1–63\.Cited by:[Appendix A](https://arxiv.org/html/2610.19279#A1.SS0.SSS0.Px4.p1.1)\.
- Zweig and Bruna \(2021\)A\. Zweig and J\. BrunaA functional perspective on learning symmetric functions with neural networks\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2610.19279#S2.SS0.SSS0.Px1.p1.1)\.

###### Appendix Contents

1. [1Introduction](https://arxiv.org/html/2610.19279#S1)
2. [2Related Work](https://arxiv.org/html/2610.19279#S2)
3. [3Problem Statement](https://arxiv.org/html/2610.19279#S3)
4. [4Main Results](https://arxiv.org/html/2610.19279#S4)1. [4\.1Invariant polynomial coordinates and representation stability](https://arxiv.org/html/2610.19279#S4.SS1) 2. [4\.2Polynomial and exponential source decay](https://arxiv.org/html/2610.19279#S4.SS2) 3. [4\.3Dimension\-free scaling laws](https://arxiv.org/html/2610.19279#S4.SS3) 4. [4\.4Why classical in\-domain power laws change](https://arxiv.org/html/2610.19279#S4.SS4) 5. [4\.5Discussion](https://arxiv.org/html/2610.19279#S4.SS5)
5. [5Conclusion](https://arxiv.org/html/2610.19279#S5)
6. [References](https://arxiv.org/html/2610.19279#bib)
7. [AAdditional Related Work](https://arxiv.org/html/2610.19279#A1)
8. [BFunction\-Level Symmetry, Statistical Learning, and Transfer](https://arxiv.org/html/2610.19279#A2)1. [B\.1Group actions on data and functions](https://arxiv.org/html/2610.19279#A2.SS1) 2. [B\.2Examples of statistical learning objectives](https://arxiv.org/html/2610.19279#A2.SS2) 3. [B\.3Exact functional transfer across sizes](https://arxiv.org/html/2610.19279#A2.SS3) 4. [B\.4Invariant polynomial function spaces](https://arxiv.org/html/2610.19279#A2.SS4) 5. [B\.5Set\-valued data and multisymmetric polynomials](https://arxiv.org/html/2610.19279#A2.SS5) 6. [B\.6Hermite features for set\-valued data](https://arxiv.org/html/2610.19279#A2.SS6) 7. [B\.7Attributed graphs](https://arxiv.org/html/2610.19279#A2.SS7)
9. [CConcrete Exact Transfers for Sets and Graphs](https://arxiv.org/html/2610.19279#A3)1. [C\.1Sets](https://arxiv.org/html/2610.19279#A3.SS1) 2. [C\.2Attributed graphs](https://arxiv.org/html/2610.19279#A3.SS2) 3. [C\.3What the exact\-transfer assumption asserts](https://arxiv.org/html/2610.19279#A3.SS3)
10. [DProof of Theorem](https://arxiv.org/html/2610.19279#A4)1. [D\.1Finite\-dimensional estimation and transfer](https://arxiv.org/html/2610.19279#A4.SS1) 2. [D\.2Set rates](https://arxiv.org/html/2610.19279#A4.SS2) 3. [D\.3Graph rates](https://arxiv.org/html/2610.19279#A4.SS3)
11. [EProof of Theorem](https://arxiv.org/html/2610.19279#A5)1. [E\.1Minimax risk and local invariant submodels](https://arxiv.org/html/2610.19279#A5.SS1) 2. [E\.2Assouad lower bound](https://arxiv.org/html/2610.19279#A5.SS2) 3. [E\.3Evaluation of the lower bound](https://arxiv.org/html/2610.19279#A5.SS3)
12. [FAuxiliary finite\-dimensional estimation bound](https://arxiv.org/html/2610.19279#A6)1. [F\.1Restricted gradients on the invariant model](https://arxiv.org/html/2610.19279#A6.SS1) 2. [F\.2Proof of the estimation bound](https://arxiv.org/html/2610.19279#A6.SS2) 3. [F\.3Proof of the transfer bound](https://arxiv.org/html/2610.19279#A6.SS3)
13. [GEquivariant Field Specialization for Sets](https://arxiv.org/html/2610.19279#A7)
14. [HEquivariant Field Specialization for Graphs](https://arxiv.org/html/2610.19279#A8)
15. [IExperiments](https://arxiv.org/html/2610.19279#A9)1. [I\.1Subgraph counting](https://arxiv.org/html/2610.19279#A9.SS1) 2. [I\.2Equivariant field transfer on weighted graphs](https://arxiv.org/html/2610.19279#A9.SS2)
16. [JNotation](https://arxiv.org/html/2610.19279#A10)

## Appendix AAdditional 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](https://arxiv.org/html/2610.19279#bib.bib12)\), while graph neural networks and higher\-order invariant and equivariant architectures are widely used for graphs\([Xu et al\., 2019](https://arxiv.org/html/2610.19279#bib.bib26);[Maron et al\., 2019](https://arxiv.org/html/2610.19279#bib.bib11);[Satorras et al\., 2021](https://arxiv.org/html/2610.19279#bib.bib2)\)\. Probabilistic symmetry provides a distributional foundation for invariant and equivariant models\([Bloem\-Reddy and Teh, 2020](https://arxiv.org/html/2610.19279#bib.bib61)\), while complementary work studies limitations of set representations\([Wagstaff et al\., 2019](https://arxiv.org/html/2610.19279#bib.bib73)\)and the ability of graph networks to count substructures\([Tahmasebi et al\., 2023](https://arxiv.org/html/2610.19279#bib.bib70)\)\. Beyond architectures that hard\-code invariance, architecture\-agnostic approaches include canonicalization\([Ma et al\., 2024](https://arxiv.org/html/2610.19279#bib.bib15);[Kaba et al\., 2023](https://arxiv.org/html/2610.19279#bib.bib21);[Dym et al\., 2024](https://arxiv.org/html/2610.19279#bib.bib18);[Shumaylov et al\., 2025](https://arxiv.org/html/2610.19279#bib.bib19);[Tahmasebi and Jegelka, 2025b](https://arxiv.org/html/2610.19279#bib.bib16)\)and frame averaging\([Puny et al\., 2022](https://arxiv.org/html/2610.19279#bib.bib20);[Atzmon et al\., 2022](https://arxiv.org/html/2610.19279#bib.bib24);[Lin et al\., 2024](https://arxiv.org/html/2610.19279#bib.bib14)\)\. Although symmetry must be discovered in some settings, either adaptively\([Tahmasebi and Weber, 2026b](https://arxiv.org/html/2610.19279#bib.bib69)\)or via statistical tests\([Soleymani et al\., 2025a](https://arxiv.org/html/2610.19279#bib.bib25);[Soleymani et al\., 2026a](https://arxiv.org/html/2610.19279#bib.bib68)\), here we focus on the case of known symmetries\. Applications of learning under invariances span reinforcement learning\([Wang et al\., 2022](https://arxiv.org/html/2610.19279#bib.bib3)\), physics\([Bogatskiy et al\., 2020](https://arxiv.org/html/2610.19279#bib.bib1);[Nguyen et al\., 2024](https://arxiv.org/html/2610.19279#bib.bib13)\), drug discovery\([Bongini et al\., 2021](https://arxiv.org/html/2610.19279#bib.bib54)\), and social networks\([Li et al\., 2023](https://arxiv.org/html/2610.19279#bib.bib55)\)\. 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](https://arxiv.org/html/2610.19279#bib.bib62);[Buffelli et al\., 2022](https://arxiv.org/html/2610.19279#bib.bib63);[Huang et al\., 2024](https://arxiv.org/html/2610.19279#bib.bib64)\)\. Graph metrics have also been used to relate structural shifts to GNN stability\([Chuang and Jegelka, 2022](https://arxiv.org/html/2610.19279#bib.bib77)\)\. Other results identify architectural limitations to sharp size generalization\([Veličković et al\., 2025](https://arxiv.org/html/2610.19279#bib.bib76)\)or derive graph\-size\-dependent statistical guarantees from a manifold perspective\([Wang et al\., 2025](https://arxiv.org/html/2610.19279#bib.bib74)\)\. 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](https://arxiv.org/html/2610.19279#bib.bib5);[Elesedy, 2021](https://arxiv.org/html/2610.19279#bib.bib6);[Wang et al\., 2021](https://arxiv.org/html/2610.19279#bib.bib4);[Petrache and Trivedi, 2023](https://arxiv.org/html/2610.19279#bib.bib7);[Tahmasebi and Jegelka, 2025a](https://arxiv.org/html/2610.19279#bib.bib17)\), with extensions to estimating probability divergences\([Chen et al\., 2023](https://arxiv.org/html/2610.19279#bib.bib9);[Tahmasebi and Jegelka, 2024](https://arxiv.org/html/2610.19279#bib.bib8)\)\. More broadly, the study of symmetry and scaling laws extends to comparisons between approximate and exact symmetry\([Tahmasebi and Weber, 2026a](https://arxiv.org/html/2610.19279#bib.bib71)\), data augmentation via Fourier analysis on groups\([Tahmasebi et al\., 2026](https://arxiv.org/html/2610.19279#bib.bib67);[Tahmasebi and Weber, 2026c](https://arxiv.org/html/2610.19279#bib.bib66)\), and statistical\-computational trade\-offs\([Soleymani et al\., 2025b](https://arxiv.org/html/2610.19279#bib.bib23);[Soleymani et al\., 2026b](https://arxiv.org/html/2610.19279#bib.bib65)\)\. Generalization bounds for graph neural networks have also been developed using Rademacher complexity\([Garg et al\., 2020](https://arxiv.org/html/2610.19279#bib.bib42)\), VC dimension\([Scarselli et al\., 2018](https://arxiv.org/html/2610.19279#bib.bib43);[Morris et al\., 2023](https://arxiv.org/html/2610.19279#bib.bib44)\), and PAC\-Bayesian analysis\([Liao et al\., 2020](https://arxiv.org/html/2610.19279#bib.bib45);[Ju et al\., 2023](https://arxiv.org/html/2610.19279#bib.bib46)\)\. Further work studies GNN generalization and transfer\([Maskey et al\., 2022](https://arxiv.org/html/2610.19279#bib.bib47);[Maskey et al\., 2025](https://arxiv.org/html/2610.19279#bib.bib48);[Levie, 2023](https://arxiv.org/html/2610.19279#bib.bib49);[Vasileiou et al\., 2025a](https://arxiv.org/html/2610.19279#bib.bib50);[Rauchwerger et al\., 2025](https://arxiv.org/html/2610.19279#bib.bib51)\); see also the survey of[Vasileiou et al\. \(2025b\)](https://arxiv.org/html/2610.19279#bib.bib52)\. 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](https://arxiv.org/html/2610.19279#bib.bib60)\)\. More recent work establishes exact and minimax rates for kernel ridge regression under source conditions in large dimensions\([Zhang et al\., 2025](https://arxiv.org/html/2610.19279#bib.bib75)\)\. 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 BFunction\-Level Symmetry, Statistical Learning, and Transfer

This appendix formalizes the function\-level framework of Section[3](https://arxiv.org/html/2610.19279#S3)\. 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\.1Group actions on data and functions

A groupGGacts on a measurable space𝒳\\mathcal\{X\}if

e⋅x=x,g⋅\(h⋅x\)=\(g​h\)⋅x,e\\cdot x=x,\\qquad g\\cdot\(h\\cdot x\)=\(gh\)\\cdot x,for everyg,h∈Gg,h\\in Gandx∈𝒳x\\in\\mathcal\{X\}\. This action induces a linear action on real\-valued functionsf:𝒳→ℝf:\\mathcal\{X\}\\to\\mathbb\{R\}by pullback:

\(g⋅f\)​\(x\)≔f⁡\(g−1⋅x\)\.\(g\\cdot f\)\(x\)\\coloneqq f\(g^\{\-1\}\\cdot x\)\.A function isGG\-invariant wheng⋅f=fg\\cdot f=ffor everyg∈Gg\\in G, equivalently,

f⁡\(g⋅x\)=f⁡\(x\)for every​g∈G,x∈𝒳\.f\(g\\cdot x\)=f\(x\)\\qquad\\text\{for every \}g\\in G,\\ x\\in\\mathcal\{X\}\.For sets and graphs of sizedd, the group isG=SdG=S\_\{d\}, acting by relabeling elements or nodes as specified in Section[3](https://arxiv.org/html/2610.19279#S3)\.

A probability distributionμ\\muon𝒳\\mathcal\{X\}isGG\-invariant if

g⋅X​=law​Xfor every​g∈G\.g\\cdot X\\overset\{\\mathrm\{law\}\}\{=\}X\\qquad\\text\{for every \}g\\in G\.Equivalently,μ⁡\(g−1​A\)=μ⁡\(A\)\\mu\(g^\{\-1\}A\)=\\mu\(A\)for all measurable setsA⊆𝒳A\\subseteq\\mathcal\{X\}\.

#### Density targets\.

Supposeμ\\muadmits a densityf⋆f^\{\\star\}with respect to aGG\-invariant reference measureλ\\lambda\. For every measurableAA,

∫Af⋆​𝑑λ=μ⁡\(A\)=μ⁡\(g−1​A\)=∫Af⋆​\(g−1⋅x\)​𝑑λ​\(x\)\.\\int\_\{A\}f^\{\\star\}\\,d\\lambda=\\mu\(A\)=\\mu\(g^\{\-1\}A\)=\\int\_\{A\}f^\{\\star\}\(g^\{\-1\}\\cdot x\)\\,d\\lambda\(x\)\.Hencef⋆​\(g⋅x\)=f⋆​\(x\)f^\{\\star\}\(g\\cdot x\)=f^\{\\star\}\(x\)forλ\\lambda\-almost everyxx\. 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ρ\\rhobe a joint distribution on𝒳×ℝ\\mathcal\{X\}\\times\\mathbb\{R\}satisfying

\(g⋅X,Y\)​=law​\(X,Y\)\.\(g\\cdot X,Y\)\\overset\{\\mathrm\{law\}\}\{=\}\(X,Y\)\.Then the conditional law ofYYgivenX=xX=xagrees with that givenX=g⋅xX=g\\cdot x, up to the usual almost\-sure choice of a conditional version\. Consequently, the regression function

f⋆​\(x\)=𝔼⁡\[Y∣X=x\]f^\{\\star\}\(x\)=\\mathbb\{E\}\[Y\\mid X=x\]admits aGG\-invariant version\.

#### Invariant risk minimization\.

Letℱ\\mathcal\{F\}be a function class closed under the inducedGG\-action\. A population riskL:ℱ→ℝL:\\mathcal\{F\}\\to\\mathbb\{R\}isGG\-invariant ifL⁡\(g⋅f\)=L⁡\(f\)L\(g\\cdot f\)=L\(f\)\. If the minimizer is unique, it is necessarily invariant\. If the minimizer is not unique,ℱ\\mathcal\{F\}is convex, andLLis convex, then group averaging produces an invariant minimizer:

f¯​\(x\)≔∫G\(g⋅f\)​\(x\)​d​ηG​\(g\),\\overline\{f\}\(x\)\\coloneqq\\int\_\{G\}\(g\\cdot f\)\(x\)\\,d\\eta\_\{G\}\(g\),whereηG\\eta\_\{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\(\\overline\{f\}\)\\leq\\int\_\{G\}L\(g\\cdot f\)\\,d\\eta\_\{G\}\(g\)=L\(f\)\.This argument takes place entirely in function space and requires no action on a parameterization\. Accordingly, uniqueness means uniqueness as anL2L^\{2\}function, up to almost\-everywhere equality; it is compatible with many parameter values representing that same function\.

### B\.2Examples of statistical learning objectives

Recall the unified observationZi=XiZ\_\{i\}=X\_\{i\}for unsupervised learning andZi=\(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\)\\widehat\{L\}\_\{n,d\}\(f\)=n^\{\-1\}\\sum\_\{i=1\}^\{n\}\\ell\_\{d\}\(Z\_\{i\},f\)estimatesLd​\(f\)=𝔼⁡\[ℓd​\(Z,f\)\]L\_\{d\}\(f\)=\\mathbb\{E\}\[\\ell\_\{d\}\(Z,f\)\]\. The formulation includes the following standard tasks\.

#### Unsupervised statistical learning: density estimation\.

Letℱd⊆L2​\(λd\)\\mathcal\{F\}\_\{d\}\\subseteq L^\{2\}\(\\lambda\_\{d\}\)be a class of nonnegative functions satisfying∫f​d​λd=1\\int f\\,\\mathrm\{d\}\\lambda\_\{d\}=1\. Sinceμd=fd⋆​λd\\mu\_\{d\}=f\_\{d\}^\{\\star\}\\lambda\_\{d\}, the negative log\-likelihood loss

ℓd​\(x,f\)=−log⁡f⁡\(x\)\\ell\_\{d\}\(x,f\)=\-\\log f\(x\)has population risk

Ld​\(f\)=𝔼X∼μd​\[−log⁡f⁡\(X\)\]\.L\_\{d\}\(f\)=\\mathbb\{E\}\_\{X\\sim\\mu\_\{d\}\}\[\-\\log f\(X\)\]\.This risk is uniquely minimized byfd⋆f\_\{d\}^\{\\star\}, up toλd\\lambda\_\{d\}\-almost\-everywhere equality, wheneverfd⋆∈ℱdf\_\{d\}^\{\\star\}\\in\\mathcal\{F\}\_\{d\}and the risk is finite\. Restricting toℱdinv\\mathcal\{F\}\_\{d\}^\{\\mathrm\{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\]\.\\ell\_\{d\}\(x,y,f\)=\(y\-f\(x\)\)^\{2\},\\qquad f\_\{d\}^\{\\star\}\(x\)=\\mathbb\{E\}\[Y\\mid X=x\]\.More generally, any proper supervised loss may be used when its population minimizer is the desired conditional target\. If relabelingXXdoes 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 identifiesfd⋆f\_\{d\}^\{\\star\}\. Score matching and denoising instead estimate a vector\-valued field, such as∇log⁡fd⋆\\nabla\\log f\_\{d\}^\{\\star\}, inL2​\(λd,ℝmd\)L^\{2\}\(\\lambda\_\{d\};\\mathbb\{R\}^\{m\_\{d\}\}\), wheremd=r​dm\_\{d\}=rdfor sets andmd=r​d2m\_\{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\.3Exact functional transfer across sizes

For density estimation letℋd=L2​\(λd\)\\mathcal\{H\}\_\{d\}=L^\{2\}\(\\lambda\_\{d\}\), and for regression letℋd=L2​\(μd\)\\mathcal\{H\}\_\{d\}=L^\{2\}\(\\mu\_\{d\}\)\. In either case, letℋdinv\\mathcal\{H\}\_\{d\}^\{\\mathrm\{inv\}\}be its invariant subspace, with inner product⟨⋅,⋅⟩d\\langle\\cdot,\\cdot\\rangle\_\{d\}and norm∥⋅∥d\\\|\\cdot\\\|\_\{d\}\. An exact transfer system is a collection of linear maps

Td→D:ℋdinv⟶ℋDinv,d≤D,T\_\{d\\to D\}:\\mathcal\{H\}\_\{d\}^\{\\mathrm\{inv\}\}\\longrightarrow\\mathcal\{H\}\_\{D\}^\{\\mathrm\{inv\}\},\\qquad d\\leq D,satisfying the following three properties:

1. \(i\)*coherence:*Td→d=IdT\_\{d\\to d\}=\\mathrm\{Id\}andTD→E​Td→D=Td→ET\_\{D\\to E\}T\_\{d\\to D\}=T\_\{d\\to E\};
2. \(ii\)*isometry:*⟨Td→D​f,Td→D​h⟩D=⟨f,h⟩d\\langle T\_\{d\\to D\}f,T\_\{d\\to D\}h\\rangle\_\{D\}=\\langle f,h\\rangle\_\{d\};
3. \(iii\)*target compatibility:*Td→D​fd⋆=fD⋆T\_\{d\\to D\}f\_\{d\}^\{\\star\}=f\_\{D\}^\{\\star\}\.

The isometry identity implies

‖Td→D​f−Td→D​h‖D=‖f−h‖d\.\\\|T\_\{d\\to D\}f\-T\_\{d\\to D\}h\\\|\_\{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 targetfD⋆f\_\{D\}^\{\\star\}is not identifiable from size\-ddobservations\. 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,j\}j≥1\\\{\\psi\_\{d,j\}\\\}\_\{j\\geq 1\}and\{ψD,j\}j≥1\\\{\\psi\_\{D,j\}\\\}\_\{j\\geq 1\}are corresponding orthonormal invariant features\. Define

Td→D​ψd,j=ψD,jT\_\{d\\to D\}\\psi\_\{d,j\}=\\psi\_\{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\\to D\}\\\!\\left\(\\sum\_\{j\}a\_\{j\}\\psi\_\{d,j\}\\right\)=\\sum\_\{j\}a\_\{j\}\\psi\_\{D,j\},\\qquad\\left\\\|T\_\{d\\to D\}\\sum\_\{j\}a\_\{j\}\\psi\_\{d,j\}\\right\\\|\_\{D\}^\{2\}=\\sum\_\{j\}a\_\{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](https://arxiv.org/html/2610.19279#bib.bib12);[Xu et al\., 2019](https://arxiv.org/html/2610.19279#bib.bib26);[Levin and Díaz, 2024](https://arxiv.org/html/2610.19279#bib.bib38)\)\.

#### 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](https://arxiv.org/html/2610.19279#bib.bib28);[Diaconis and Janson, 2008](https://arxiv.org/html/2610.19279#bib.bib41)\)\. Appendix[C](https://arxiv.org/html/2610.19279#A3)gives explicit set and graph constructions, including replication, graph blow\-ups, and shared Deep Sets and GNN rules\.

### B\.4Invariant polynomial function spaces

A central example is a finite\-dimensional space of polynomial functions\. LetVdV\_\{d\}be a finite\-dimensional vector space on whichGdG\_\{d\}acts linearly, and let𝒫d,k\\mathcal\{P\}\_\{d,k\}be the space of homogeneous degree\-kkpolynomial functions onVdV\_\{d\}\. The induced action on functions is

\(g⋅f\)​\(x\)≔f⁡\(g−1⋅x\)\.\(g\\cdot f\)\(x\)\\coloneqq f\(g^\{\-1\}\\cdot x\)\.The invariant homogeneous polynomial space is

𝒫d,kGd≔\{f∈𝒫d,k:g⋅f=f​for all​g∈Gd\}\.\\mathcal\{P\}\_\{d,k\}^\{G\_\{d\}\}\\coloneqq\\\{f\\in\\mathcal\{P\}\_\{d,k\}:g\\cdot f=f\\text\{ for all \}g\\in G\_\{d\}\\\}\.For density estimation, completeness follows from the Hermite basis ofL2​\(λd\)L^\{2\}\(\\lambda\_\{d\}\)\. For regression, we assume the standard polynomial\-completeness condition inL2​\(μd\)L^\{2\}\(\\mu\_\{d\}\), which holds, for example, under suitable moment determinacy or exponential\-moment conditions\. Averaging polynomial approximants overSdS\_\{d\}then proves density of invariant polynomials inℋdinv\\mathcal\{H\}\_\{d\}^\{\\mathrm\{inv\}\}\.

For finite groups, the dimension of the invariant subspace can be expressed using characters\. Ifϱd,k\\varrho\_\{d,k\}is the representation ofGdG\_\{d\}on𝒫d,k\\mathcal\{P\}\_\{d,k\}\(i\.e\., the collection of matrices corresponding to the action\) andχd,k​\(g\)=tr⁡\(ϱd,k​\(g\)\)\\chi\_\{d,k\}\(g\)=\\mathrm\{tr\}\(\\varrho\_\{d,k\}\(g\)\)is its character, then

dim𝒫d,kGd=1\|Gd\|​∑g∈Gdχd,k​\(g\)\.\\dim\\mathcal\{P\}\_\{d,k\}^\{G\_\{d\}\}=\\frac\{1\}\{\|G\_\{d\}\|\}\\sum\_\{g\\in G\_\{d\}\}\\chi\_\{d,k\}\(g\)\.Equivalently, ifPGdP\_\{G\_\{d\}\}denotes the group\-averaging projection

PGd​f=1\|Gd\|​∑g∈Gdg⋅f,P\_\{G\_\{d\}\}f=\\frac\{1\}\{\|G\_\{d\}\|\}\\sum\_\{g\\in G\_\{d\}\}g\\cdot f,then

dim𝒫d,kGd=tr⁡\(PGd\)\.\\dim\\mathcal\{P\}\_\{d,k\}^\{G\_\{d\}\}=\\mathrm\{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 asddgrows\. This stabilization is the algebraic mechanism behind dimension\-uniform learning in our setting\.

### B\.5Set\-valued data and multisymmetric polynomials

Consider set\-valued data withddelements inℝr\\mathbb\{R\}^\{r\}\. We represent the set as

X=\(x1,…,xd\)∈\(ℝr\)d,xi=\(xi,1,…,xi,r\)∈ℝr\.X=\(x\_\{1\},\\ldots,x\_\{d\}\)\\in\(\\mathbb\{R\}^\{r\}\)^\{d\},\\qquad x\_\{i\}=\(x\_\{i,1\},\\ldots,x\_\{i,r\}\)\\in\\mathbb\{R\}^\{r\}\.The symmetric groupSdS\_\{d\}acts by permuting theddelements:

π⋅X=\(xπ−1​\(1\),…,xπ−1​\(d\)\)\.\\pi\\cdot X=\(x\_\{\\pi^\{\-1\}\(1\)\},\\ldots,x\_\{\\pi^\{\-1\}\(d\)\}\)\.The corresponding invariant polynomials are called multisymmetric polynomials: they are polynomials in thed​rdrvariablesxi,ax\_\{i,a\}that are invariant under permutations of the block indexii\.

Let𝒫d,r,kSd\\mathcal\{P\}\_\{d,r,k\}^\{S\_\{d\}\}denote the space of homogeneous degreekkmultisymmetric polynomials\. A monomial is described by a collection of multi\-indices

αi=\(αi,1,…,αi,r\)∈ℕr,1≤i≤d,\\alpha\_\{i\}=\(\\alpha\_\{i,1\},\\ldots,\\alpha\_\{i,r\}\)\\in\\mathbb\{N\}^\{r\},\\qquad 1\\leq i\\leq d,with total degree∑i\|αi\|=k\\sum\_\{i\}\|\\alpha\_\{i\}\|=k\. The groupSdS\_\{d\}permutes the multi\-indicesαi\\alpha\_\{i\}\. Therefore an invariant monomial orbit is determined by a multiset of nonzero multi\-indices

\{α\(1\),…,α\(q\)\},α\(j\)∈ℕr∖\{0\},∑j=1q\|α\(j\)\|=k\.\\\{\\alpha^\{\(1\)\},\\ldots,\\alpha^\{\(q\)\}\\\},\\qquad\\alpha^\{\(j\)\}\\in\\mathbb\{N\}^\{r\}\\setminus\\\{0\\\},\\qquad\\sum\_\{j=1\}^\{q\}\|\\alpha^\{\(j\)\}\|=k\.Ford≥kd\\geq k, every such multiset can be realized using at mostkknonzero blocks, so the dimension stabilizes indd\.

For eachm≥1m\\geq 1, the number of nonzero block types of degreemmis

ar​\(m\)=\#⁡\{α∈ℕr:\|α\|=m\}=\(r\+m−1m\)\.a\_\{r\}\(m\)=\\\#\\\{\\alpha\\in\\mathbb\{N\}^\{r\}:\|\\alpha\|=m\\\}=\\binom\{r\+m\-1\}\{m\}\.Hence the stable dimension of homogeneous degreekkinvariants is

Nr​\(k\)≔dim𝒫d,r,kSd=\[tk\]​∏m≥1\(1−tm\)−ar​\(m\)for​d≥k,N\_\{r\}\(k\)\\coloneqq\\dim\\mathcal\{P\}\_\{d,r,k\}^\{S\_\{d\}\}=\[t^\{k\}\]\\prod\_\{m\\geq 1\}\(1\-t^\{m\}\)^\{\-a\_\{r\}\(m\)\}\\qquad\\text\{for \}d\\geq k,where\[tk\]​F​\(t\)\[t^\{k\}\]F\(t\)denotes the coefficient oftkt^\{k\}in the formal power seriesF⁡\(t\)F\(t\)\. Equivalently,

Nr​\(k\)=\[tk\]​∏m≥1\(1−tm\)−\(r\+m−1m\)\.N\_\{r\}\(k\)=\[t^\{k\}\]\\prod\_\{m\\geq 1\}\(1\-t^\{m\}\)^\{\-\\binom\{r\+m\-1\}\{m\}\}\.Forr=1r=1, this reduces to the ordinary partition number:

N1​\(k\)=p​\(k\)\.N\_\{1\}\(k\)=p\(k\)\.Thus the invariant degree\-kkdimension is independent ofddonced≥kd\\geq k, whereas the full homogeneous degree\-kkpolynomial space ind​rdrvariables has dimension

\(d​r\+k−1k\),\\binom\{dr\+k\-1\}\{k\},which grows polynomially inddof orderdkd^\{k\}for fixedkk\.

The asymptotic behavior ofNr​\(k\)N\_\{r\}\(k\)for fixedrrand largekkis subexponential:

log⁡Nr​\(k\)∼Cr​krr\+1,\\log N\_\{r\}\(k\)\\sim C\_\{r\}k^\{\\frac\{r\}\{r\+1\}\},where

Cr=r\+1r​\(r​ζ​\(r\+1\)\)1r\+1,C\_\{r\}=\\frac\{r\+1\}\{r\}\\big\(r\\zeta\(r\+1\)\\big\)^\{\\frac\{1\}\{r\+1\}\},andζ⁡\(s\)≔∑n=1∞n−s\\zeta\(s\)\\coloneqq\\sum\_\{n=1\}^\{\\infty\}n^\{\-s\}denotes the Riemann zeta function\. Thus

Nr​\(k\)=exp⁡\(Cr​krr\+1\+o⁡\(krr\+1\)\)\.N\_\{r\}\(k\)=\\exp\\left\(C\_\{r\}k^\{\\frac\{r\}\{r\+1\}\}\+o\\left\(k^\{\\frac\{r\}\{r\+1\}\}\\right\)\\right\)\.For example,r=1r=1recovers the Hardy–Ramanujan exponent

log⁡p⁡\(k\)∼π​2​k3\.\\log p\(k\)\\sim\\pi\\sqrt\{\\frac\{2k\}\{3\}\}\.Forr=2r=2,

log⁡N2​\(k\)∼32​\(2​ζ​\(3\)\)1/3​k2/3,\\log N\_\{2\}\(k\)\\sim\\frac\{3\}\{2\}\(2\\zeta\(3\)\)^\{1/3\}k^\{2/3\},and forr=3r=3,

log⁡N3​\(k\)∼43​\(3​ζ​\(4\)\)1/4​k3/4\.\\log N\_\{3\}\(k\)\\sim\\frac\{4\}\{3\}\(3\\zeta\(4\)\)^\{1/4\}k^\{3/4\}\.
These formulas show that for fixed element dimensionrrand polynomial degreekk, the invariant polynomial function\-space dimension stabilizes as the set sizeddgrows\. This is the representation\-stability mechanism underlying the dimension\-independent rates for set\-valued data\.

### B\.6Hermite features for set\-valued data

For data on\(ℝr\)d\(\\mathbb\{R\}^\{r\}\)^\{d\}, a natural basis is given by multivariate Hermite polynomials relative to a Gaussian reference measure\. LetHαH\_\{\\alpha\}denote an orthonormal Hermite polynomial indexed byα∈ℕd​r\\alpha\\in\\mathbb\{N\}^\{dr\}\. For block\-structured data, we may write

Hα1,…,αd​\(X\)=∏i=1dHαi​\(xi\),αi∈ℕr\.H\_\{\\alpha\_\{1\},\\ldots,\\alpha\_\{d\}\}\(X\)=\\prod\_\{i=1\}^\{d\}H\_\{\\alpha\_\{i\}\}\(x\_\{i\}\),\\qquad\\alpha\_\{i\}\\in\\mathbb\{N\}^\{r\}\.The groupSdS\_\{d\}permutes the block indicesαi\\alpha\_\{i\}\. Therefore invariant Hermite features are obtained by symmetrizing Hermite monomials overSdS\_\{d\}\. The dimension count for homogeneous degreekkinvariant Hermite features is the same as for multisymmetric polynomials:

dimℋd,r,kSd=Nr​\(k\)for​d≥k\.\\dim\\mathcal\{H\}\_\{d,r,k\}^\{S\_\{d\}\}=N\_\{r\}\(k\)\\qquad\\text\{for \}d\\geq k\.
This construction gives a concrete hierarchy for invariant density and regression functions\. For density estimation, letϕd,j\\phi\_\{d,j\}be invariant Hermite functions; for regression, let them be the corresponding invariant polynomials orthonormalized inL2​\(μd\)L^\{2\}\(\\mu\_\{d\}\)\. In either case, the scalar target admits an expansion

fd⋆​\(X\)=∑jad,j⋆​ϕd,j​\(X\)\.f\_\{d\}^\{\\star\}\(X\)=\\sum\_\{j\}a\_\{d,j\}^\{\\star\}\\phi\_\{d,j\}\(X\)\.Truncation at degreekkproduces a finite\-dimensional invariant function class whose dimension is

Nr\(≤k\)=∑q=0kNr​\(q\),N\_\{r\}\(\\leq k\)=\\sum\_\{q=0\}^\{k\}N\_\{r\}\(q\),independent ofddonced≥kd\\geq k\. For density estimation, the admissible class additionally enforces nonnegativity and unit integral\.

If one instead studies score matching, an invariant log\-density expansionlog⁡fd⋆=∑jbd,j⋆​ϕd,j\\log f\_\{d\}^\{\\star\}=\\sum\_\{j\}b\_\{d,j\}^\{\\star\}\\phi\_\{d,j\}gives the Lebesgue score

∇X​log​d​μdd​x​\(X\)=−X\+∑jbd,j⋆​∇Xϕd,j​\(X\)\.\\nabla\_\{X\}\\log\\frac\{\\mathrm\{d\}\\mu\_\{d\}\}\{\\mathrm\{d\}x\}\(X\)=\-X\+\\sum\_\{j\}b\_\{d,j\}^\{\\star\}\\nabla\_\{X\}\\phi\_\{d,j\}\(X\)\.Gradients of invariant scalar features are equivariant vector fields:

∇Xϕd,j​\(π⋅X\)=π⋅∇Xϕd,j​\(X\)\.\\nabla\_\{X\}\\phi\_\{d,j\}\(\\pi\\cdot X\)=\\pi\\cdot\\nabla\_\{X\}\\phi\_\{d,j\}\(X\)\.If the function coefficients have a controlled tail, for example,

∑j\>m\(ad,j⋆\)2≤bm2,\\sum\_\{j\>m\}\(a\_\{d,j\}^\{\\star\}\)^\{2\}\\leq b\_\{m\}^\{2\},then truncating tomminvariant Hermite functions incurs squaredL2L^\{2\}approximation error at mostbm2b\_\{m\}^\{2\}\. This is a concrete instance of the approximation tailB⁡\(k\)B\(k\)in Theorem[4\.1](https://arxiv.org/html/2610.19279#S4.Thmtheorem1)\.

### B\.7Attributed graphs

An attributed graph withddnodes is represented, as in the main text, by

X∈𝒳d=ℝr×d×d\.X\\in\\mathcal\{X\}\_\{d\}=\\mathbb\{R\}^\{r\\times d\\times d\}\.The channel indexa∈\{1,…,r\}a\\in\\\{1,\\ldots,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\)\.\(\\pi\\cdot X\)\_\{a,i,j\}=X\_\{a,\\pi^\{\-1\}\(i\),\\pi^\{\-1\}\(j\)\}\.
A homogeneous degree\-kkpolynomial function is a linear combination of monomials

∏a=1r∏i,j=1dXa,i,jma,i,j,∑a,i,jma,i,j=k\.\\prod\_\{a=1\}^\{r\}\\prod\_\{i,j=1\}^\{d\}X\_\{a,i,j\}^\{m\_\{a,i,j\}\},\\qquad\\sum\_\{a,i,j\}m\_\{a,i,j\}=k\.Two such monomials belong to the sameSdS\_\{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 degreekk, with diagonal factors representing vertex decorations when node features are encoded on the diagonal\.

Letℛd,r,kSd\\mathcal\{R\}\_\{d,r,k\}^\{S\_\{d\}\}be the corresponding space of invariant homogeneous polynomial functions\. Any degree\-kkmonomial involves at most2​k2kdistinct node indices, so

dimℛd,r,kSd=Gr​\(k\)for every​d≥2​k,\\dim\\mathcal\{R\}\_\{d,r,k\}^\{S\_\{d\}\}=G\_\{r\}\(k\)\\qquad\\text\{for every \}d\\geq 2k,whereGr​\(k\)G\_\{r\}\(k\)is the number of admissible unlabeled channel\-attributed multigraph patterns of degreekk\. 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\}=\\mathbb\{R\}^\{r\\times d\\times d\},we have

ℛd,r,kSd=\(Symk⁡\(Wd∗\)\)Sd,dimℛd,r,kSd=1d\!​∑π∈SdχSymk⁡\(Wd∗\)​\(π\)\.\\mathcal\{R\}\_\{d,r,k\}^\{S\_\{d\}\}=\\left\(\\operatorname\{Sym\}^\{k\}\(W\_\{d\}^\{\\ast\}\)\\right\)^\{S\_\{d\}\},\\qquad\\dim\\mathcal\{R\}\_\{d,r,k\}^\{S\_\{d\}\}=\\frac\{1\}\{d\!\}\\sum\_\{\\pi\\in S\_\{d\}\}\\chi\_\{\\operatorname\{Sym\}^\{k\}\(W\_\{d\}^\{\\ast\}\)\}\(\\pi\)\.Equivalently, ifϱd\\varrho\_\{d\}is the representation ofSdS\_\{d\}onWd∗W\_\{d\}^\{\\ast\}, its Molien series is

∑k≥0dimℛd,r,kSd​tk=1d\!​∑π∈Sd1det\(I−t​ϱd​\(π\)\)\.\\sum\_\{k\\geq 0\}\\dim\\mathcal\{R\}\_\{d,r,k\}^\{S\_\{d\}\}t^\{k\}=\\frac\{1\}\{d\!\}\\sum\_\{\\pi\\in S\_\{d\}\}\\frac\{1\}\{\\det\(I\-t\\varrho\_\{d\}\(\\pi\)\)\}\.
The asymptotic dependence onkkseparates 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\}\]\\prod\_\{m\\geq 1\}\(1\-t^\{m\}\)^\{\-\\binom\{r\+m\-1\}\{m\}\},and therefore

Nr​\(k\)=exp⁡\(Cr​krr\+1\+o⁡\(krr\+1\)\)\.N\_\{r\}\(k\)=\\exp\\left\(C\_\{r\}k^\{\\frac\{r\}\{r\+1\}\}\+o\\left\(k^\{\\frac\{r\}\{r\+1\}\}\\right\)\\right\)\.In contrast, if at least one channel contains edge variables, graph\-pattern complexity gives

Gr​\(k\)=exp⁡\(k​log⁡k\+O⁡\(k​log⁡log⁡k\)\),k→∞\.G\_\{r\}\(k\)=\\exp\\\!\\left\(k\\log k\+O\(k\\log\\log k\)\\right\),\\qquad k\\to\\infty\.Thus attributed\-graph invariant function spaces stabilize in the number of nodesdd, while their growth with interaction orderkkis larger than for set\-valued data\.

## Appendix CConcrete Exact Transfers for Sets and Graphs

This appendix makes the transfer assumption concrete for the two domains studied in the paper\. The operatorTd→DT\_\{d\\to 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 relevantL2L^\{2\}spaces\.

### C\.1Sets

A set ofddvectors is represented byX=\(x1,…,xd\)∈𝒳d=\(ℝr\)d≃ℝr×dX=\(x\_\{1\},\\ldots,x\_\{d\}\)\\in\\mathcal\{X\}\_\{d\}=\(\\mathbb\{R\}^\{r\}\)^\{d\}\\simeq\\mathbb\{R\}^\{r\\times d\}\. Because the ordering carries no information,SdS\_\{d\}acts byπ⋅X=\(xπ−1​\(1\),…,xπ−1​\(d\)\)\\pi\\cdot X=\(x\_\{\\pi^\{\-1\}\(1\)\},\\ldots,x\_\{\\pi^\{\-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](https://arxiv.org/html/2610.19279#A2.SS1)\.

#### Shared Deep Sets rules\.

Letϕ:ℝr→ℝm\\phi:\\mathbb\{R\}^\{r\}\\to\\mathbb\{R\}^\{m\}be an elementwise feature map and define the normalized set summary

mdϕ​\(X\)=1d​∑i=1dϕ⁡\(xi\)\.m\_\{d\}^\{\\phi\}\(X\)=\\frac\{1\}\{d\}\\sum\_\{i=1\}^\{d\}\\phi\(x\_\{i\}\)\.For any readoutF:ℝm→ℝF:\\mathbb\{R\}^\{m\}\\to\\mathbb\{R\}, the rule

fd​\(X\)=F⁡\(mdϕ​\(X\)\)f\_\{d\}\(X\)=F\\\!\\left\(m\_\{d\}^\{\\phi\}\(X\)\\right\)is invariant for everydd\. Its transfer to sizeDDis obtained by applying the sameϕ\\phiandFF:

\(Td→D​fd\)​\(X1,…,XD\)=F⁡\(1D​∑i=1Dϕ⁡\(Xi\)\)\.\(T\_\{d\\to D\}f\_\{d\}\)\(X\_\{1\},\\ldots,X\_\{D\}\)=F\\\!\\left\(\\frac\{1\}\{D\}\\sum\_\{i=1\}^\{D\}\\phi\(X\_\{i\}\)\\right\)\.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\.

IfD=q​dD=qd, repeat each elementqqtimes:

Rd→D​\(x1,…,xd\)=\(x1,…,x1⏟q,…,xd,…,xd⏟q\)\.R\_\{d\\to D\}\(x\_\{1\},\\ldots,x\_\{d\}\)=\(\\underbrace\{x\_\{1\},\\ldots,x\_\{1\}\}\_\{q\},\\ldots,\\underbrace\{x\_\{d\},\\ldots,x\_\{d\}\}\_\{q\}\)\.The normalized summary is unchanged,

mDϕ​\(Rd→D​X\)=mdϕ​\(X\)\.m\_\{D\}^\{\\phi\}\(R\_\{d\\to D\}X\)=m\_\{d\}^\{\\phi\}\(X\)\.Equivalently, replication leaves the empirical measured−1​∑iδxid^\{\-1\}\\sum\_\{i\}\\delta\_\{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\\phi\(0\)=0\.

#### Stable feature expansions\.

Letψd,j\\psi\_\{d,j\}be normalized multisymmetric or invariant Hermite functions, paired across sizes by their common orbit type\. For

fd=∑jaj​ψd,j,f\_\{d\}=\\sum\_\{j\}a\_\{j\}\\psi\_\{d,j\},define

Td→D​fd=∑jaj​ψD,j\.T\_\{d\\to D\}f\_\{d\}=\\sum\_\{j\}a\_\{j\}\\psi\_\{D,j\}\.If the paired features are orthonormal in their respective task spaces, Parseval’s identity gives

‖Td→D​fd‖D2=∑jaj2=‖fd‖d2\.\\\|T\_\{d\\to D\}f\_\{d\}\\\|\_\{D\}^\{2\}=\\sum\_\{j\}a\_\{j\}^\{2\}=\\\|f\_\{d\}\\\|\_\{d\}^\{2\}\.ThusTd→DT\_\{d\\to 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](https://arxiv.org/html/2610.19279#A2.SS5)\.

### C\.2Attributed graphs

An attributed graph withddnodes is represented byX∈𝒳d=ℝr×d×dX\\in\\mathcal\{X\}\_\{d\}=\\mathbb\{R\}^\{r\\times d\\times d\}, andSdS\_\{d\}acts by simultaneous relabeling:

\(π⋅X\)a,i,j=Xa,π−1​\(i\),π−1​\(j\)\.\(\\pi\\cdot X\)\_\{a,i,j\}=X\_\{a,\\pi^\{\-1\}\(i\),\\pi^\{\-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 patternHH, lettH​\(X\)t\_\{H\}\(X\)denote its normalized homomorphism density inXX\. These functions are invariant and are indexed byHH, not by the number of nodes\. IfX\(q\)X^\{\(q\)\}is theqq\-fold blow\-up obtained by replacing each node byqqtwins 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\\bigl\(t\_\{H\_\{1\}\}\(X\),\\ldots,t\_\{H\_\{m\}\}\(X\)\\bigr\)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 changingddtherefore defines a map from the size\-ddfunction to its size\-DDrealization\. This is the architecture\-level instance ofTd→DT\_\{d\\to 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\\psi\_\{d,H\}be normalized invariant functions indexed by unlabeled attributed multigraph patternsHH\. Transfer pairs the same pattern across sizes:

Td→D​ψd,H=ψD,H\.T\_\{d\\to D\}\\psi\_\{d,H\}=\\psi\_\{D,H\}\.Extending this identification linearly gives

Td→D​\(∑HaH​ψd,H\)=∑HaH​ψD,H\.T\_\{d\\to D\}\\\!\\left\(\\sum\_\{H\}a\_\{H\}\\psi\_\{d,H\}\\right\)=\\sum\_\{H\}a\_\{H\}\\psi\_\{D,H\}\.After orthonormalization in the task norms, this map is an isometry and satisfies the coherence identity\. The degree\-kktruncations stabilize onced≥2​kd\\geq 2k, as shown in Appendix[B\.7](https://arxiv.org/html/2610.19279#A2.SS7)\. These expansions cover invariant graph regression and density functions without privileging a particular learning loss; for densities, admissibility again enforces nonnegativity and normalization\.

### C\.3What 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→D​fd⋆=fD⋆\.T\_\{d\\to D\}f\_\{d\}^\{\\star\}=f\_\{D\}^\{\\star\}\.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 DProof of Theorem[4\.1](https://arxiv.org/html/2610.19279#S4.Thmtheorem1)

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](https://arxiv.org/html/2610.19279#S3)and formalized in Appendix[B\.3](https://arxiv.org/html/2610.19279#A2.SS3); representation growthq𝖷​\(k\)q\_\{\\mathsf\{X\}\}\(k\)and the source envelopeB⁡\(k\)B\(k\)are defined in Section[4](https://arxiv.org/html/2610.19279#S4)\. 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](https://arxiv.org/html/2610.19279#A5.Ex113)–equation[E\.1](https://arxiv.org/html/2610.19279#A5.Ex115)\.

### D\.1Finite\-dimensional estimation and transfer

Fix a domain type𝖷∈\{set,graph\}\\mathsf\{X\}\\in\\\{\\mathrm\{set\},\\mathrm\{graph\}\\\}, a training sizedd, and an interaction orderkk\. Letfd,k∘f\_\{d,k\}^\{\\circ\}andf^n,d,kinv\\hat\{f\}\_\{n,d,k\}^\{\\mathrm\{inv\}\}minimize the population and empirical risks overℱd,k\\mathcal\{F\}\_\{d,k\}, respectively\. Uniform calibration gives‖fd,k∘−fd⋆‖d2≤Capp​Bd​\(k\)\.\\\|f\_\{d,k\}^\{\\circ\}\-f\_\{d\}^\{\\star\}\\\|\_\{d\}^\{2\}\\leq C\_\{\\mathrm\{app\}\}B\_\{d\}\(k\)\.Apply the strong\-convexity and score\-concentration calculation of Appendix[F](https://arxiv.org/html/2610.19279#A6)in orthonormal coordinates on𝒱d,k\\mathcal\{V\}\_\{d,k\}\. Since those coordinates identify Euclidean distance with∥⋅∥d\\\|\\cdot\\\|\_\{d\}, with probability at least1−δ1\-\\delta,

‖f^n,d,kinv−fd,k∘‖d2≤C​σ2α2​dim\(𝒱d,k\)\+log⁡\(1/δ\)n\.\\bigl\\\|\\hat\{f\}\_\{n,d,k\}^\{\\mathrm\{inv\}\}\-f\_\{d,k\}^\{\\circ\}\\bigr\\\|\_\{d\}^\{2\}\\leq C\\frac\{\\sigma^\{2\}\}\{\\alpha^\{2\}\}\\frac\{\\dim\(\\mathcal\{V\}\_\{d,k\}\)\+\\log\(1/\\delta\)\}\{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\)\.\\bigl\\\|\\hat\{f\}\_\{n,d,k\}^\{\\mathrm\{inv\}\}\-f\_\{d\}^\{\\star\}\\bigr\\\|\_\{d\}^\{2\}\\leq C\_\{0\}\\left\(B\_\{d\}\(k\)\+\\frac\{\\dim\(\\mathcal\{V\}\_\{d,k\}\)\+\\log\(1/\\delta\)\}\{n\}\\right\)\.HereC0C\_\{0\}depends on the uniform calibration, curvature, and score constants, but not onn,d,Dn,d,D, orkk\. Thus equation[D\.1](https://arxiv.org/html/2610.19279#A4.Ex89)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\)\\leq B\(k\)anddim\(𝒱d,k\)≤q𝖷​\(k\)\\dim\(\\mathcal\{V\}\_\{d,k\}\)\\leq q\_\{\\mathsf\{X\}\}\(k\)\. Moreover, exact target transfer and isometry give, simultaneously for everyD≥dD\\geq d,

‖Td→D​f^n,d,kinv−fD⋆‖D2\\displaystyle\\bigl\\\|T\_\{d\\to D\}\\hat\{f\}\_\{n,d,k\}^\{\\mathrm\{inv\}\}\-f\_\{D\}^\{\\star\}\\bigr\\\|\_\{D\}^\{2\}=‖Td→D​\(f^n,d,kinv−fd⋆\)‖D2\\displaystyle=\\bigl\\\|T\_\{d\\to D\}\(\\hat\{f\}\_\{n,d,k\}^\{\\mathrm\{inv\}\}\-f\_\{d\}^\{\\star\}\)\\bigr\\\|\_\{D\}^\{2\}=‖f^n,d,kinv−fd⋆‖d2\.\\displaystyle=\\bigl\\\|\\hat\{f\}\_\{n,d,k\}^\{\\mathrm\{inv\}\}\-f\_\{d\}^\{\\star\}\\bigr\\\|\_\{d\}^\{2\}\.No union bound overDDis needed: all target\-size errors equal the same source\-size error on the event in equation[D\.1](https://arxiv.org/html/2610.19279#A4.Ex89)\. Taking the supremum in equation[D\.1](https://arxiv.org/html/2610.19279#A4.Ex91)therefore yields

supD≥d‖Td→D​f^n,d,kinv−fD⋆‖D2≤C0​\(B⁡\(k\)\+q𝖷​\(k\)\+log⁡\(1/δ\)n\)\.\\sup\_\{D\\geq d\}\\bigl\\\|T\_\{d\\to D\}\\hat\{f\}\_\{n,d,k\}^\{\\mathrm\{inv\}\}\-f\_\{D\}^\{\\star\}\\bigr\\\|\_\{D\}^\{2\}\\leq C\_\{0\}\\left\(B\(k\)\+\\frac\{q\_\{\\mathsf\{X\}\}\(k\)\+\\log\(1/\\delta\)\}\{n\}\\right\)\.This is the key dimension\-free oracle inequality\. Object sizesddandDDhave disappeared; only interaction order, representation growth, and target regularity remain\.

### D\.2Set rates

Writeβ=r/\(r\+1\)\\beta=r/\(r\+1\)\. The stable multisymmetric count satisfies

log⁡qset​\(k\)=Cr​kβ\+o⁡\(kβ\),Cr=r\+1r​\(r​ζ​\(r\+1\)\)1/\(r\+1\)\.\\log q\_\{\\mathrm\{set\}\}\(k\)=C\_\{r\}k^\{\\beta\}\+o\(k^\{\\beta\}\),\\qquad C\_\{r\}=\\frac\{r\+1\}\{r\}\\bigl\(r\\zeta\(r\+1\)\\bigr\)^\{1/\(r\+1\)\}\.We optimize the two leading terms in equation[D\.1](https://arxiv.org/html/2610.19279#A4.Ex93); for a fixed confidence level,log⁡\(1/δ\)/n\\log\(1/\\delta\)/nis smaller than all rates below\.

#### Polynomial source decay\.

IfB⁡\(k\)≲k−τB\(k\)\\lesssim k^\{\-\\tau\}, balancing the two terms in equation[D\.1](https://arxiv.org/html/2610.19279#A4.Ex93)givesCr​knβ\+τ​log⁡kn=log⁡n\+o⁡\(log⁡n\)C\_\{r\}k\_\{n\}^\{\\beta\}\+\\tau\\log k\_\{n\}=\\log n\+o\(\\log n\), hencekn=\(log⁡n/Cr\)1/β​\(1\+o⁡\(1\)\)k\_\{n\}=\(\\log n/C\_\{r\}\)^\{1/\\beta\}\(1\+o\(1\)\)and

supD≥d∥Td→Df^n,d,kninv−fD⋆∥D2≲\(logn\)−τ/β=\(logn\)−τ\(r\+1\)/r\.\\sup\_\{D\\geq d\}\\bigl\\\|T\_\{d\\to D\}\\hat\{f\}\_\{n,d,k\_\{n\}\}^\{\\mathrm\{inv\}\}\-f\_\{D\}^\{\\star\}\\bigr\\\|\_\{D\}^\{2\}\\lesssim\(\\log n\)^\{\-\\tau/\\beta\}=\(\\log n\)^\{\-\\tau\(r\+1\)/r\}\.

#### Exponential source decay\.

IfB⁡\(k\)≲e−a​kνB\(k\)\\lesssim e^\{\-ak^\{\\nu\}\}, the balancing equation is

a​knν\+Cr​knβ\+o⁡\(knβ\)=log⁡n\.ak\_\{n\}^\{\\nu\}\+C\_\{r\}k\_\{n\}^\{\\beta\}\+o\(k\_\{n\}^\{\\beta\}\)=\\log 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\}\)\+\\frac\{q\_\{\\mathrm\{set\}\}\(k\_\{n\}\)\}\{n\}\\asymp\\begin\{cases\}n^\{\-1\+o\(1\)\},&\\nu\>\\beta,\\\\ n^\{\-a/\(a\+C\_\{r\}\)\+o\(1\)\},&\\nu=\\beta,\\\\ \\exp\\\!\\left\[\-aC\_\{r\}^\{\-\\nu/\\beta\}\(\\log n\)^\{\\nu/\\beta\}\(1\+o\(1\)\)\\right\],&0<\\nu<\\beta\.\\end\{cases\}The first line is the fast set regime in Table[2](https://arxiv.org/html/2610.19279#S4.T2); the other two lines give the critical and subcritical interpolation\.

### D\.3Graph rates

For every fixed feature dimensionrr, the stable graph\-pattern count satisfies

log⁡qgraph​\(k\)=k​log⁡k\+Or​\(k​log⁡log⁡k\)=k​log⁡k⁡\(1\+o⁡\(1\)\)\.\\log q\_\{\\mathrm\{graph\}\}\(k\)=k\\log k\+O\_\{r\}\(k\\log\\log k\)=k\\log k\\,\(1\+o\(1\)\)\.Thusrraffects only the lower\-order remainder and does not enter the first\-order rates\.

#### Polynomial source decay\.

ForB⁡\(k\)≲k−τB\(k\)\\lesssim k^\{\-\\tau\}, the crossing equation giveskn=\(log⁡n/log⁡log⁡n\)​\(1\+o⁡\(1\)\)k\_\{n\}=\(\\log n/\\log\\log n\)\(1\+o\(1\)\), and therefore

supD≥d‖Td→D​f^n,d,kninv−fD⋆‖D2≲\(log⁡nlog⁡log⁡n\)−τ\.\\sup\_\{D\\geq d\}\\bigl\\\|T\_\{d\\to D\}\\hat\{f\}\_\{n,d,k\_\{n\}\}^\{\\mathrm\{inv\}\}\-f\_\{D\}^\{\\star\}\\bigr\\\|\_\{D\}^\{2\}\\lesssim\\left\(\\frac\{\\log n\}\{\\log\\log n\}\\right\)^\{\-\\tau\}\.

#### Exponential source decay\.

ForB⁡\(k\)≲e−a​kνB\(k\)\\lesssim e^\{\-ak^\{\\nu\}\}, the balancing equation is

a​knν\+kn​log⁡kn\+Or​\(kn​log⁡log⁡kn\)=log⁡n\.ak\_\{n\}^\{\\nu\}\+k\_\{n\}\\log k\_\{n\}\+O\_\{r\}\(k\_\{n\}\\log\\log k\_\{n\}\)=\\log n\.Solving it gives

B⁡\(kn\)\+qgraph​\(kn\)n≍\{n−1\+o⁡\(1\),ν\>1,exp⁡\[−a​\(log⁡nlog⁡log⁡n\)ν​\(1\+o⁡\(1\)\)\],0<ν≤1\.B\(k\_\{n\}\)\+\\frac\{q\_\{\\mathrm\{graph\}\}\(k\_\{n\}\)\}\{n\}\\asymp\\begin\{cases\}n^\{\-1\+o\(1\)\},&\\nu\>1,\\\\ \\exp\\\!\\left\[\-a\\left\(\\frac\{\\log n\}\{\\log\\log n\}\\right\)^\{\\nu\}\(1\+o\(1\)\)\\right\],&0<\\nu\\leq 1\.\\end\{cases\}The second line is critical atν=1\\nu=1and subcritical for0<ν<10<\\nu<1\. Equations equation[D\.2](https://arxiv.org/html/2610.19279#A4.Ex97), equation[D\.2](https://arxiv.org/html/2610.19279#A4.Ex101), equation[D\.3](https://arxiv.org/html/2610.19279#A4.Ex105), and equation[D\.3](https://arxiv.org/html/2610.19279#A4.Ex109)prove Theorem[4\.1](https://arxiv.org/html/2610.19279#S4.Thmtheorem1)\.

## Appendix EProof of Theorem[4\.2](https://arxiv.org/html/2610.19279#S4.Thmtheorem2)

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\.1Minimax risk and local invariant submodels

Let𝔉𝖷​\(B\)\\mathfrak\{F\}\_\{\\mathsf\{X\}\}\(B\)be the class of size\-consistent target families on domain𝖷\\mathsf\{X\}satisfying exact transfer and the source envelopeBB\. An estimator observesnnsamples at sizeddand returns functionsf^D\\hat\{f\}\_\{D\}forD≥dD\\geq d\. Define its worst\-case risk by

ℜn​\(𝖷,B\)≔inf𝒇^supd≥1sup𝒇⋆∈𝔉𝖷​\(B\)𝔼⁡\[supD≥d‖f^D−fD⋆‖D2\]\.\\mathfrak\{R\}\_\{n\}\(\\mathsf\{X\},B\)\\coloneqq\\inf\_\{\\hat\{\\bm\{f\}\}\}\\sup\_\{d\\geq 1\}\\sup\_\{\\bm\{f\}^\{\\star\}\\in\\mathfrak\{F\}\_\{\\mathsf\{X\}\}\(B\)\}\\mathbb\{E\}\\\!\\left\[\\sup\_\{D\\geq d\}\\\|\\hat\{f\}\_\{D\}\-f\_\{D\}^\{\\star\}\\\|\_\{D\}^\{2\}\\right\]\.
#### Minimax nondegeneracy\.

For every interaction orderkk, take a sizedkd\_\{k\}in the stable range:dk≥kd\_\{k\}\\geq kfor sets anddk≥2​kd\_\{k\}\\geq 2kfor graphs\. The nondegeneracy assumption providesmk≥c0​q𝖷​\(k\)m\_\{k\}\\geq c\_\{0\}q\_\{\\mathsf\{X\}\}\(k\)orthonormal invariant directionsψ1,…,ψmk\\psi\_\{1\},\\ldots,\\psi\_\{m\_\{k\}\}, paired coherently across larger sizes, and an admissible baselinef0f\_\{0\}such that the hypercube

fω=f0\+u​∑j=1mkωj​ψj,ω∈\{−1,1\}mk,f\_\{\\omega\}=f\_\{0\}\+u\\sum\_\{j=1\}^\{m\_\{k\}\}\\omega\_\{j\}\\psi\_\{j\},\\qquad\\omega\\in\\\{\-1,1\\\}^\{m\_\{k\}\},belongs to the source class whenevermk​u2≤c1​B​\(k\)m\_\{k\}u^\{2\}\\leq c\_\{1\}B\(k\)\. It also requires the neighboring statistical experiments to satisfy

KL⁡\(Pω⊗n,Pω\(j\)⊗n\)≤c2​n​u2,\\mathrm\{KL\}\\\!\\left\(P\_\{\\omega\}^\{\\otimes n\},P\_\{\\omega^\{\(j\)\}\}^\{\\otimes n\}\\right\)\\leq c\_\{2\}nu^\{2\},whereω\(j\)\\omega^\{\(j\)\}differs fromω\\omegaonly in coordinatejj\. For regression, one obtains equation[E\.1](https://arxiv.org/html/2610.19279#A5.Ex115)by adding Gaussian noise toY=fω​\(X\)Y=f\_\{\\omega\}\(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](https://arxiv.org/html/2610.19279#A5.Ex113)\.

### E\.2Assouad lower bound

Set

uk2=c3​min⁡\{B⁡\(k\)mk,1n\},u\_\{k\}^\{2\}=c\_\{3\}\\min\\\!\\left\\\{\\frac\{B\(k\)\}\{m\_\{k\}\},\\frac\{1\}\{n\}\\right\\\},withc3c\_\{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=4​uk2\\\|f\_\{\\omega\}\-f\_\{\\omega^\{\(j\)\}\}\\\|\_\{d\_\{k\}\}^\{2\}=4u\_\{k\}^\{2\}, Assouad’s lemma yields

inff^supω∈\{−1,1\}mk𝔼ω​‖f^−fω‖dk2≥c4​mk​uk2≥c5​min⁡\{B⁡\(k\),q𝖷​\(k\)n\}\.\\inf\_\{\\hat\{f\}\}\\sup\_\{\\omega\\in\\\{\-1,1\\\}^\{m\_\{k\}\}\}\\mathbb\{E\}\_\{\\omega\}\\\|\\hat\{f\}\-f\_\{\\omega\}\\\|\_\{d\_\{k\}\}^\{2\}\\geq c\_\{4\}m\_\{k\}u\_\{k\}^\{2\}\\geq c\_\{5\}\\min\\\!\\left\\\{B\(k\),\\frac\{q\_\{\\mathsf\{X\}\}\(k\)\}\{n\}\\right\\\}\.The size\-generalization loss contains the choiceD=dkD=d\_\{k\}, so its supremum is at least the in\-domain loss in equation[E\.2](https://arxiv.org/html/2610.19279#A5.Ex118)\. Consequently,

ℜn​\(𝖷,B\)≥c5​supk≥1min⁡\{B⁡\(k\),q𝖷​\(k\)n\}\.\\mathfrak\{R\}\_\{n\}\(\\mathsf\{X\},B\)\\geq c\_\{5\}\\sup\_\{k\\geq 1\}\\min\\\!\\left\\\{B\(k\),\\frac\{q\_\{\\mathsf\{X\}\}\(k\)\}\{n\}\\right\\\}\.This observation is important: transfer cannot remove a lower bound already present at the training size\.

BecauseB⁡\(k\)B\(k\)decreases andq𝖷​\(k\)q\_\{\\mathsf\{X\}\}\(k\)increases, the supremum in equation[E\.2](https://arxiv.org/html/2610.19279#A5.Ex120)is attained, up to constants and lower\-order factors, whereB⁡\(k\)≍q𝖷​\(k\)/nB\(k\)\\asymp q\_\{\\mathsf\{X\}\}\(k\)/n\. Under the regular source envelopes considered here,

supkmin⁡\{B⁡\(k\),q𝖷​\(k\)n\}≍infk\{B⁡\(k\)\+q𝖷​\(k\)n\}\.\\sup\_\{k\}\\min\\\!\\left\\\{B\(k\),\\frac\{q\_\{\\mathsf\{X\}\}\(k\)\}\{n\}\\right\\\}\\asymp\\inf\_\{k\}\\left\\\{B\(k\)\+\\frac\{q\_\{\\mathsf\{X\}\}\(k\)\}\{n\}\\right\\\}\.The right\-hand side is precisely the quantity controlled by the upper oracle inequality equation[D\.1](https://arxiv.org/html/2610.19279#A4.Ex93)\.

### E\.3Evaluation 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\(log⁡nlog⁡log⁡n\)−τ\.\(\\log n\)^\{\-\\tau\(r\+1\)/r\}\\qquad\\text\{and\}\\qquad\\left\(\\frac\{\\log n\}\{\\log\\log n\}\\right\)^\{\-\\tau\}\.For exponential source decay, the same crossing equations give exactly the three set regimes in equation[D\.2](https://arxiv.org/html/2610.19279#A4.Ex101)and the two graph regimes in equation[D\.3](https://arxiv.org/html/2610.19279#A4.Ex109)\.

These lower bounds match the upper bounds in Appendix[D](https://arxiv.org/html/2610.19279#A4), 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](https://arxiv.org/html/2610.19279#S4.T2), completing the proof of Theorem[4\.2](https://arxiv.org/html/2610.19279#S4.Thmtheorem2)\.

## Appendix FAuxiliary finite\-dimensional estimation bound

For completeness, we derive the finite\-dimensional estimation term in equation[D\.1](https://arxiv.org/html/2610.19279#A4.Ex89)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\.1Restricted gradients on the invariant model

Fixd∈ℕd\\in\\mathbb\{N\}\. LetΘdGd\\Theta\_\{d\}^\{G\_\{d\}\}be a finite\-dimensional invariant parameter space and letθd⋆∈ΘdGd\\theta\_\{d\}^\{\\star\}\\in\\Theta\_\{d\}^\{G\_\{d\}\}denote its population\-risk minimizer\. In this section,θd⋆\\theta\_\{d\}^\{\\star\}is the best fit within the finite model \(the analogue offd,k∘f\_\{d,k\}^\{\\circ\}\), and need not equal the unrestricted target\. We write

pdG=dim\(ΘdGd\)\.p\_\{d\}^\{G\}=\\dim\(\\Theta\_\{d\}^\{G\_\{d\}\}\)\.For simplicity of notation, we identifyΘdGd\\Theta\_\{d\}^\{G\_\{d\}\}locally with a Euclidean space of dimensionpdGp\_\{d\}^\{G\}\. Equivalently, ifΘdGd\\Theta\_\{d\}^\{G\_\{d\}\}is a smooth model, the gradient below is understood in any normalized local coordinate chart aroundθd⋆\\theta\_\{d\}^\{\\star\}\. Thus,∇GL^n,d​\(θd⋆\)\\nabla\_\{G\}\\hat\{L\}\_\{n,d\}\(\\theta\_\{d\}^\{\\star\}\)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,θ\)\\hat\{L\}\_\{n,d\}\(\\theta\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\ell\_\{d\}\(Z\_\{i\},\\theta\)isα\\alpha\-strongly convex onΘdGd\\Theta\_\{d\}^\{G\_\{d\}\}, withα\\alphaindependent ofdd\. 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 least1−δ1\-\\deltaoncen≳pdG\+log⁡\(1/δ\)n\\gtrsim p\_\{d\}^\{G\}\+\\log\(1/\\delta\)\. 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⋆\\theta\_\{d\}^\{\\star\}is sub\-Gaussian with variance proxy at mostσ2\\sigma^\{2\}\. That is, writing

Yi≔∇Gℓd​\(Zi,θd⋆\)∈ℝpdG,Y\_\{i\}\\coloneqq\\nabla\_\{G\}\\ell\_\{d\}\(Z\_\{i\},\\theta\_\{d\}^\{\\star\}\)\\in\\mathbb\{R\}^\{p\_\{d\}^\{G\}\},we have𝔼​Yi=0\\mathbb\{E\}Y\_\{i\}=0and, for every unit vectorv∈ℝpdGv\\in\\mathbb\{R\}^\{p\_\{d\}^\{G\}\},

𝔼​exp⁡\(λ⁡⟨v,Yi⟩\)≤exp⁡\(λ2​σ22\)∀λ∈ℝ\.\\mathbb\{E\}\\exp\(\\lambda\\langle v,Y\_\{i\}\\rangle\)\\leq\\exp\\left\(\\frac\{\\lambda^\{2\}\\sigma^\{2\}\}\{2\}\\right\)\\qquad\\forall\\lambda\\in\\mathbb\{R\}\.Then there exists an absolute constantC0\>0C\_\{0\}\>0such that, for everyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta,

‖∇GL^n,d​\(θd⋆\)‖22=‖1n​∑i=1nYi‖22≤C0​σ2​pdG\+log⁡\(1/δ\)n\.\\left\\\|\\nabla\_\{G\}\\hat\{L\}\_\{n,d\}\(\\theta\_\{d\}^\{\\star\}\)\\right\\\|\_\{2\}^\{2\}=\\left\\\|\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}Y\_\{i\}\\right\\\|\_\{2\}^\{2\}\\leq C\_\{0\}\\sigma^\{2\}\\frac\{p\_\{d\}^\{G\}\+\\log\(1/\\delta\)\}\{n\}\.

###### Proof\.

Letp=pdGp=p\_\{d\}^\{G\}and define

Y¯n≔1n​∑i=1nYi\.\\bar\{Y\}\_\{n\}\\coloneqq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}Y\_\{i\}\.Since theYiY\_\{i\}’s are independent, mean\-zero, andσ2\\sigma^\{2\}\-sub\-Gaussian, the averageY¯n\\bar\{Y\}\_\{n\}is sub\-Gaussian with variance proxyσ2/n\\sigma^\{2\}/n\. Hence for every unit vectorv∈ℝpv\\in\\mathbb\{R\}^\{p\},

𝔼​exp⁡\(λ⁡⟨v,Y¯n⟩\)≤exp⁡\(λ2​σ22​n\)\.\\mathbb\{E\}\\exp\(\\lambda\\langle v,\\bar\{Y\}\_\{n\}\\rangle\)\\leq\\exp\\left\(\\frac\{\\lambda^\{2\}\\sigma^\{2\}\}\{2n\}\\right\)\.
Let𝒩\\mathcal\{N\}be a1/21/2\-net of the unit sphere𝕊p−1\\mathbb\{S\}^\{p\-1\}with\|𝒩\|≤5p\|\\mathcal\{N\}\|\\leq 5^\{p\}\. For everyu∈ℝpu\\in\\mathbb\{R\}^\{p\},

‖u‖2≤2​maxv∈𝒩​⟨v,u⟩\.\\\|u\\\|\_\{2\}\\leq 2\\max\_\{v\\in\\mathcal\{N\}\}\\langle v,u\\rangle\.Therefore, for anyt\>0t\>0,

ℙ⁡\(‖Y¯n‖2≥2​t\)≤ℙ⁡\(maxv∈𝒩⁡⟨v,Y¯n⟩≥t\)\.\\mathbb\{P\}\(\\\|\\bar\{Y\}\_\{n\}\\\|\_\{2\}\\geq 2t\)\\leq\\mathbb\{P\}\\left\(\\max\_\{v\\in\\mathcal\{N\}\}\\langle v,\\bar\{Y\}\_\{n\}\\rangle\\geq t\\right\)\.By a union bound and the one\-dimensional sub\-Gaussian tail bound,

ℙ⁡\(maxv∈𝒩⁡⟨v,Y¯n⟩≥t\)≤\|𝒩\|exp⁡\(−n​t22​σ2\)≤exp⁡\(p​log​5−n​t22​σ2\)\.\\mathbb\{P\}\\left\(\\max\_\{v\\in\\mathcal\{N\}\}\\langle v,\\bar\{Y\}\_\{n\}\\rangle\\geq t\\right\)\\leq\|\\mathcal\{N\}\|\\exp\\left\(\-\\frac\{nt^\{2\}\}\{2\\sigma^\{2\}\}\\right\)\\leq\\exp\\left\(p\\log 5\-\\frac\{nt^\{2\}\}\{2\\sigma^\{2\}\}\\right\)\.Taking

t=σ​2​\(p​log⁡5\+log⁡\(1/δ\)\)n,t=\\sigma\\sqrt\{\\frac\{2\(p\\log 5\+\\log\(1/\\delta\)\)\}\{n\}\},we obtain, with probability at least1−δ1\-\\delta,

‖Y¯n‖2≤2​σ​2​\(p​log⁡5\+log⁡\(1/δ\)\)n\.\\\|\\bar\{Y\}\_\{n\}\\\|\_\{2\}\\leq 2\\sigma\\sqrt\{\\frac\{2\(p\\log 5\+\\log\(1/\\delta\)\)\}\{n\}\}\.Squaring both sides yields

‖Y¯n‖22≤8​σ2​p​log⁡5\+log⁡\(1/δ\)n\.\\\|\\bar\{Y\}\_\{n\}\\\|\_\{2\}^\{2\}\\leq 8\\sigma^\{2\}\\frac\{p\\log 5\+\\log\(1/\\delta\)\}\{n\}\.Thus the claim holds with an absolute constantC0C\_\{0\}\. ∎

### F\.2Proof of the estimation bound

Let

θ^n,dG∈arg⁡minθ∈ΘdGd​L^n,d​\(θ\)\.\\hat\{\\theta\}\_\{n,d\}^\{G\}\\in\\arg\\min\_\{\\theta\\in\\Theta\_\{d\}^\{G\_\{d\}\}\}\\hat\{L\}\_\{n,d\}\(\\theta\)\.Sinceθd⋆∈ΘdGd\\theta\_\{d\}^\{\\star\}\\in\\Theta\_\{d\}^\{G\_\{d\}\}, empirical optimality gives

L^n,d​\(θ^n,dG\)≤L^n,d​\(θd⋆\)\.\\hat\{L\}\_\{n,d\}\(\\hat\{\\theta\}\_\{n,d\}^\{G\}\)\\leq\\hat\{L\}\_\{n,d\}\(\\theta\_\{d\}^\{\\star\}\)\.On the intersection of the restricted\-curvature event and the score\-concentration event,L^n,d\\hat\{L\}\_\{n,d\}isα\\alpha\-strongly convex onΘdGd\\Theta\_\{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\.\\hat\{L\}\_\{n,d\}\(\\hat\{\\theta\}\_\{n,d\}^\{G\}\)\\geq\\hat\{L\}\_\{n,d\}\(\\theta\_\{d\}^\{\\star\}\)\+\\left\\langle\\nabla\_\{G\}\\hat\{L\}\_\{n,d\}\(\\theta\_\{d\}^\{\\star\}\),\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\right\\rangle\+\\frac\{\\alpha\}\{2\}\\left\\\|\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\right\\\|\_\{2\}^\{2\}\.Combining the previous two displays gives

0≥⟨∇GL^n,d​\(θd⋆\),θ^n,dG−θd⋆⟩\+α2​‖θ^n,dG−θd⋆‖22\.0\\geq\\left\\langle\\nabla\_\{G\}\\hat\{L\}\_\{n,d\}\(\\theta\_\{d\}^\{\\star\}\),\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\right\\rangle\+\\frac\{\\alpha\}\{2\}\\left\\\|\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\right\\\|\_\{2\}^\{2\}\.By Cauchy–Schwarz,

0≥−‖∇GL^n,d​\(θd⋆\)‖2​‖θ^n,dG−θd⋆‖2\+α2​‖θ^n,dG−θd⋆‖22\.0\\geq\-\\left\\\|\\nabla\_\{G\}\\hat\{L\}\_\{n,d\}\(\\theta\_\{d\}^\{\\star\}\)\\right\\\|\_\{2\}\\left\\\|\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\right\\\|\_\{2\}\+\\frac\{\\alpha\}\{2\}\\left\\\|\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\right\\\|\_\{2\}^\{2\}\.Ifθ^n,dG=θd⋆\\hat\{\\theta\}\_\{n,d\}^\{G\}=\\theta\_\{d\}^\{\\star\}, the desired bound is immediate\. Otherwise, dividing by‖θ^n,dG−θd⋆‖2\\\|\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\\|\_\{2\}gives

‖θ^n,dG−θd⋆‖2≤2α​‖∇GL^n,d​\(θd⋆\)‖2\.\\left\\\|\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\right\\\|\_\{2\}\\leq\\frac\{2\}\{\\alpha\}\\left\\\|\\nabla\_\{G\}\\hat\{L\}\_\{n,d\}\(\\theta\_\{d\}^\{\\star\}\)\\right\\\|\_\{2\}\.Taking each event with failure probabilityδ/2\\delta/2, squaring, applying Lemma[F\.1](https://arxiv.org/html/2610.19279#A6.Thmtheorem1), and using a union bound, we obtain with probability at least1−δ1\-\\delta,

‖θ^n,dG−θd⋆‖22≤4α2​‖∇GL^n,d​\(θd⋆\)‖22≤C​σ2α2​pdG\+log⁡\(1/δ\)n,\\left\\\|\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\right\\\|\_\{2\}^\{2\}\\leq\\frac\{4\}\{\\alpha^\{2\}\}\\left\\\|\\nabla\_\{G\}\\hat\{L\}\_\{n,d\}\(\\theta\_\{d\}^\{\\star\}\)\\right\\\|\_\{2\}^\{2\}\\leq C\\frac\{\\sigma^\{2\}\}\{\\alpha^\{2\}\}\\frac\{p\_\{d\}^\{G\}\+\\log\(1/\\delta\)\}\{n\},for an absolute constantC\>0C\>0\. This is the finite\-dimensional estimation bound used in equation[D\.1](https://arxiv.org/html/2610.19279#A4.Ex89)\. When the coordinates are orthonormal inℋd\\mathcal\{H\}\_\{d\}, Euclidean parameter distance equals function\-space distance\. If the population best fit additionally satisfies‖fd,k∘−fd⋆‖d2≤Capp​Bd​\(k\)\\\|f\_\{d,k\}^\{\\circ\}\-f\_\{d\}^\{\\star\}\\\|\_\{d\}^\{2\}\\leq C\_\{\\mathrm\{app\}\}B\_\{d\}\(k\), the squared triangle inequality gives equation[D\.1](https://arxiv.org/html/2610.19279#A4.Ex89)directly\.

If

pG≔supdpdG<∞,p^\{G\}\\coloneqq\\sup\_\{d\}p\_\{d\}^\{G\}<\\infty,thenpdG≤pGp\_\{d\}^\{G\}\\leq p^\{G\}for everydd, and therefore

‖θ^n,dG−θd⋆‖22≤C​σ2α2​pG\+log⁡\(1/δ\)n\.\\left\\\|\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\right\\\|\_\{2\}^\{2\}\\leq C\\frac\{\\sigma^\{2\}\}\{\\alpha^\{2\}\}\\frac\{p^\{G\}\+\\log\(1/\\delta\)\}\{n\}\.

### F\.3Proof of the transfer bound

Fix a source dimensiondd\. Suppose that for everyD≥dD\\geq d,

Φd→D​θd⋆=θD⋆,\\Phi\_\{d\\to D\}\\theta\_\{d\}^\{\\star\}=\\theta\_\{D\}^\{\\star\},and thatΦd→D\\Phi\_\{d\\to D\}is distance preserving on the invariant model:

‖Φd→D​θ−Φd→D​θ′‖2=‖θ−θ′‖2∀θ,θ′∈ΘdGd\.\\left\\\|\\Phi\_\{d\\to D\}\\theta\-\\Phi\_\{d\\to D\}\\theta^\{\\prime\}\\right\\\|\_\{2\}=\\left\\\|\\theta\-\\theta^\{\\prime\}\\right\\\|\_\{2\}\\qquad\\forall\\theta,\\theta^\{\\prime\}\\in\\Theta\_\{d\}^\{G\_\{d\}\}\.Then, for everyD≥dD\\geq d,

‖Φd→D​θ^n,dG−θD⋆‖2\\displaystyle\\left\\\|\\Phi\_\{d\\to D\}\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{D\}^\{\\star\}\\right\\\|\_\{2\}=‖Φd→D​θ^n,dG−Φd→D​θd⋆‖2\\displaystyle=\\left\\\|\\Phi\_\{d\\to D\}\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\Phi\_\{d\\to D\}\\theta\_\{d\}^\{\\star\}\\right\\\|\_\{2\}=‖θ^n,dG−θd⋆‖2\.\\displaystyle=\\left\\\|\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\right\\\|\_\{2\}\.Taking the supremum overD≥dD\\geq d, we get

supD≥d‖Φd→D​θ^n,dG−θD⋆‖22=‖θ^n,dG−θd⋆‖22\.\\sup\_\{D\\geq d\}\\left\\\|\\Phi\_\{d\\to D\}\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{D\}^\{\\star\}\\right\\\|\_\{2\}^\{2\}=\\left\\\|\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{d\}^\{\\star\}\\right\\\|\_\{2\}^\{2\}\.Combining this identity with the estimation bound above yields

supD≥d‖Φd→D​θ^n,dG−θD⋆‖22≤C​σ2α2​pdG\+log⁡\(1/δ\)n\\sup\_\{D\\geq d\}\\left\\\|\\Phi\_\{d\\to D\}\\hat\{\\theta\}\_\{n,d\}^\{G\}\-\\theta\_\{D\}^\{\\star\}\\right\\\|\_\{2\}^\{2\}\\leq C\\frac\{\\sigma^\{2\}\}\{\\alpha^\{2\}\}\\frac\{p\_\{d\}^\{G\}\+\\log\(1/\\delta\)\}\{n\}with probability at least1−δ1\-\\delta\. IfpG=supdpdG<∞p^\{G\}=\\sup\_\{d\}p\_\{d\}^\{G\}<\\infty, the right\-hand side is bounded by

C​σ2α2​pG\+log⁡\(1/δ\)n\.C\\frac\{\\sigma^\{2\}\}\{\\alpha^\{2\}\}\\frac\{p^\{G\}\+\\log\(1/\\delta\)\}\{n\}\.This completes the auxiliary transfer calculation\.

## Appendix GEquivariant 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,j\}j≥1\\\{\\psi\_\{d,j\}\\\}\_\{j\\geq 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\}^\{\\star\}=\\sum\_\{j\\geq 1\}\\theta\_\{d,j\}^\{\\star\}\\psi\_\{d,j\},\\qquad\\\|\\hat\{s\}\_\{d\}\-s\_\{d\}^\{\\star\}\\\|\_\{d\}^\{2\}=\\sum\_\{j\\geq 1\}\(\\hat\{\\theta\}\_\{d,j\}\-\\theta\_\{d,j\}^\{\\star\}\)^\{2\}\.Ifℐd,k\\mathcal\{I\}\_\{d,k\}contains the features of degree at mostkk, then its stable dimension and the omitted coefficient energy are

mr​\(k\)=\|ℐd,k\|=exp⁡\(Cr​kr/\(r\+1\)\+o⁡\(kr/\(r\+1\)\)\),Bd​\(k\)=∑j∉ℐd,k\(θd,j⋆\)2\.m\_\{r\}\(k\)=\|\\mathcal\{I\}\_\{d,k\}\|=\\exp\\\!\\left\(C\_\{r\}k^\{r/\(r\+1\)\}\+o\\\!\\left\(k^\{r/\(r\+1\)\}\\right\)\\right\),\\qquad B\_\{d\}\(k\)=\\sum\_\{j\\notin\\mathcal\{I\}\_\{d,k\}\}\(\\theta\_\{d,j\}^\{\\star\}\)^\{2\}\.Orthogonality and the auxiliary finite\-dimensional bound in Appendix[F](https://arxiv.org/html/2610.19279#A6)give, with probability at least1−δ1\-\\delta,

‖s^n,d\(k\)−sd⋆‖d2≤Bd​\(k\)\+C​σ2α2​mr​\(k\)\+log⁡\(1/δ\)n\.\\\|\\hat\{s\}\_\{n,d\}^\{\(k\)\}\-s\_\{d\}^\{\\star\}\\\|\_\{d\}^\{2\}\\leq B\_\{d\}\(k\)\+C\\frac\{\\sigma^\{2\}\}\{\\alpha^\{2\}\}\\frac\{m\_\{r\}\(k\)\+\\log\(1/\\delta\)\}\{n\}\.Thus the scalar proof applies verbatim\. Uniform polynomial decayBd​\(k\)≲k−τB\_\{d\}\(k\)\\lesssim k^\{\-\\tau\}gives\(logn\)−τ\(r\+1\)/r\(\\log n\)^\{\-\\tau\(r\+1\)/r\}\. Under uniform exponential decayBd​\(k\)≲e−a​kνB\_\{d\}\(k\)\\lesssim e^\{\-ak^\{\\nu\}\}, withβ=r/\(r\+1\)\\beta=r/\(r\+1\),

infk\{Bd​\(k\)\+mr​\(k\)n\}≍\{n−1\+o⁡\(1\),ν\>β,n−a/\(a\+Cr\)\+o\(1\),ν=β,exp\[−aCr−ν/β\(logn\)ν/β\(1\+o\(1\)\)\],0<ν<β\.\\inf\_\{k\}\\left\\\{B\_\{d\}\(k\)\+\\frac\{m\_\{r\}\(k\)\}\{n\}\\right\\\}\\asymp\\begin\{cases\}n^\{\-1\+o\(1\)\},&\\nu\>\\beta,\\\\ n^\{\-a/\(a\+C\_\{r\}\)\+o\(1\)\},&\\nu=\\beta,\\\\ \\exp\\\!\\left\[\-aC\_\{r\}^\{\-\\nu/\\beta\}\(\\log n\)^\{\\nu/\\beta\}\(1\+o\(1\)\)\\right\],&0<\\nu<\\beta\.\\end\{cases\}Because the equivariant transfer operator is isometric, these bounds hold simultaneously at every target sizeD≥dD\\geq d\.

## Appendix HEquivariant Field Specialization for Graphs

Let𝒥d,k\\mathcal\{J\}\_\{d,k\}contain the degree\-at\-most\-kkequivariant graph features, and writeMr​\(k\)=\|𝒥d,k\|M\_\{r\}\(k\)=\|\\mathcal\{J\}\_\{d,k\}\|\. For fixed channel dimensionrr,

Mr​\(k\)=exp⁡\(k​log⁡k\+Or​\(k​log⁡log⁡k\)\),Bdgraph​\(k\)=∑j∉𝒥d,k\(θd,j⋆\)2\.M\_\{r\}\(k\)=\\exp\\\!\\left\(k\\log k\+O\_\{r\}\(k\\log\\log k\)\\right\),\\qquad B\_\{d\}^\{\\mathrm\{graph\}\}\(k\)=\\sum\_\{j\\notin\\mathcal\{J\}\_\{d,k\}\}\(\\theta\_\{d,j\}^\{\\star\}\)^\{2\}\.The same orthogonal decomposition and finite\-dimensional estimate yield

‖s^n,d\(k\)−sd⋆‖d2≤Bdgraph​\(k\)\+C​σ2α2​Mr​\(k\)\+log⁡\(1/δ\)n\.\\\|\\hat\{s\}\_\{n,d\}^\{\(k\)\}\-s\_\{d\}^\{\\star\}\\\|\_\{d\}^\{2\}\\leq B\_\{d\}^\{\\mathrm\{graph\}\}\(k\)\+C\\frac\{\\sigma^\{2\}\}\{\\alpha^\{2\}\}\\frac\{M\_\{r\}\(k\)\+\\log\(1/\\delta\)\}\{n\}\.Consequently, polynomial decayBdgraph​\(k\)≲k−τB\_\{d\}^\{\\mathrm\{graph\}\}\(k\)\\lesssim k^\{\-\\tau\}gives\(log⁡n/log⁡log⁡n\)−τ\(\\log n/\\log\\log n\)^\{\-\\tau\}, while exponential decayBdgraph​\(k\)≲e−a​kνB\_\{d\}^\{\\mathrm\{graph\}\}\(k\)\\lesssim e^\{\-ak^\{\\nu\}\}gives

infk\{Bdgraph​\(k\)\+Mr​\(k\)n\}≍\{n−1\+o⁡\(1\),ν\>1,exp⁡\[−a​\(log⁡nlog⁡log⁡n\)ν​\(1\+o⁡\(1\)\)\],0<ν≤1\.\\inf\_\{k\}\\left\\\{B\_\{d\}^\{\\mathrm\{graph\}\}\(k\)\+\\frac\{M\_\{r\}\(k\)\}\{n\}\\right\\\}\\asymp\\begin\{cases\}n^\{\-1\+o\(1\)\},&\\nu\>1,\\\\ \\exp\\\!\\left\[\-a\\left\(\\dfrac\{\\log n\}\{\\log\\log n\}\\right\)^\{\\nu\}\(1\+o\(1\)\)\\right\],&0<\\nu\\leq 1\.\\end\{cases\}The channel dimension affects only the lower\-order term inMr​\(k\)M\_\{r\}\(k\), so it does not enter these first\-order rates\. Isometric equivariant transfer again makes every bound simultaneous overD≥dD\\geq d\.

## Appendix IExperiments

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\.1Subgraph 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\\sim\\mathrm\{Unif\}\(0\.15,0\.85\),\\qquad A\\sim G\(d,p\),whereA∈\{0,1\}d×dA\\in\\\{0,1\\\}^\{d\\times d\}is the adjacency matrix of an undirected graph with no self\-loops\. The response is the population triangle densityy≈p3y\\approx p^\{3\}\. Thus, the target is a low\-degree graph moment, but the learner observes only the sampled graphAA, not the latent parameterpp\. We train all models only on graphs withd=10d=10nodes and evaluate them on larger graphs with

D∈\{25,30,35,40,50,60,75,100,125,150,175,200\}\.D\\in\\\{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\)\),\\phi\_\{\\mathrm\{inv\},d\}\(A\)=\\big\(E\_\{d\}\(A\),W\_\{d\}\(A\),T\_\{d\}\(A\)\\big\),whereEd​\(A\)E\_\{d\}\(A\)is the edge density,Wd​\(A\)W\_\{d\}\(A\)is the normalized wedge density, andTd​\(A\)T\_\{d\}\(A\)is the normalized triangle density\. A linear model is fit on these features atd=10d=10, and transfer to sizeDDis performed by evaluating the same normalized invariant statistics on the larger graph:

f^inv,D​\(A\)=β^0\+β^1​ED​\(A\)\+β^2​WD​\(A\)\+β^3​TD​\(A\)\.\\widehat\{f\}\_\{\\mathrm\{inv\},D\}\(A\)=\\widehat\{\\beta\}\_\{0\}\+\\widehat\{\\beta\}\_\{1\}E\_\{D\}\(A\)\+\\widehat\{\\beta\}\_\{2\}W\_\{D\}\(A\)\+\\widehat\{\\beta\}\_\{3\}T\_\{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 sized=10d=10, we use the raw triangle indicators

Ai​j​Ai​k​Aj​k,1≤i<j<k≤10,A\_\{ij\}A\_\{ik\}A\_\{jk\},\\qquad 1\\leq i<j<k\\leq 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 onDDnodes, we sample subsetsS1,…,SM⊆\[D\]S\_\{1\},\\dots,S\_\{M\}\\subseteq\[D\]of size ten and define

f^raw,Davg​\(A\)=1M​∑m=1Mf^raw,10​\(ASm×Sm\)\.\\widehat\{f\}\_\{\\mathrm\{raw\},D\}^\{\\mathrm\{avg\}\}\(A\)=\\frac\{1\}\{M\}\\sum\_\{m=1\}^\{M\}\\widehat\{f\}\_\{\\mathrm\{raw\},10\}\(A\_\{S\_\{m\}\\times 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](https://arxiv.org/html/2610.19279#A9.F1)\(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\.2Equivariant 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\\in\\mathbb\{R\}^\{d\\times d\},with zero diagonal and independent standard\-Gaussian upper\-triangular entries\. We regress onto the permutation\-equivariant field

sd⋆​\(A\)=−A−∑q=28bq​q​d−q​Aq−1\.s\_\{d\}^\{\\star\}\(A\)=\-A\-\\sum\_\{q=2\}^\{8\}b\_\{q\}qd^\{\-q\}A^\{q\-1\}\.The featuresq​d−q​Aq−1qd^\{\-q\}A^\{q\-1\}are gradients of normalized invariant spectral statisticsd−q​tr⁡\(Aq\)d^\{\-q\}\\operatorname\{tr\}\(A^\{q\}\)\. Their meaning is shared across graph sizes, and the same coefficientbqb\_\{q\}therefore defines the same rule at every size\. We compare a fast\-decay target,

bq=2​exp⁡\(−0\.14​q2\),b\_\{q\}=2\\exp\(\-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^q​q​d−q​Aq−1\\widehat\{s\}\_\{d\}\(A\)=\-A\-\\sum\_\{q=2\}^\{4\}\\widehat\{b\}\_\{q\}qd^\{\-q\}A^\{q\-1\}by least squares on the off\-diagonal field entries of 200 independently sampled graphs withd=10d=10\. Transfer to sizeDDreuses the learned coefficientsb^q\\widehat\{b\}\_\{q\}and evaluates the corresponding normalized featuresq​D−q​Aq−1qD^\{\-q\}A^\{q\-1\}\. We test on 16 independent graphs at each

D∈\{10,15,20,30,40,60,80\}\.D\\in\\\{10,15,20,30,40,60,80\\\}\.Because the common linear term−A\-Ais represented exactly, we report error relative to the energy of the nonlinear target component:

RelMSED=∑A∑i<j\(s^D​\(A\)i​j−sD⋆​\(A\)i​j\)2∑A∑i<j\(sD⋆​\(A\)i​j\+Ai​j\)2\.\\operatorname\{RelMSE\}\_\{D\}=\\frac\{\\sum\_\{A\}\\sum\_\{i<j\}\(\\widehat\{s\}\_\{D\}\(A\)\_\{ij\}\-s\_\{D\}^\{\\star\}\(A\)\_\{ij\}\)^\{2\}\}\{\\sum\_\{A\}\\sum\_\{i<j\}\(s\_\{D\}^\{\\star\}\(A\)\_\{ij\}\+A\_\{ij\}\)^\{2\}\}\.The full procedure is repeated for ten independent seeds, and the shaded bands in Figure[1](https://arxiv.org/html/2610.19279#A9.F1)\(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](https://arxiv.org/html/2610.19279#A9.F1)\(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\.

![Refer to caption](https://arxiv.org/html/2610.19279v1/arXiv/graph_transfer_restyled.png)

\(a\)Invariant versus symmetrized raw features\.

![Refer to caption](https://arxiv.org/html/2610.19279v1/arXiv/weighted_graph_score_transfer_normalized.png)

\(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 JNotation