Minimax Sample Complexity of Graph Neural Networks: Lower Bounds and Structural Effects
Authors: Ahmad Ghasemi
Hossein Pishro-Nik
Venue: ICLR 2026 Poster (2026)
Keywords: Graph Neural Networks (GNNs)
sample complexity
lower bounds
Primary area: learning theory
TL;DR: We prove tight minimax lower bounds on the sample complexity of GNNs, showing their generalization depends critically on graph structure and is often as slow as 1/log n.

Abstract: Graph Neural Networks (GNNs) achieve strong empirical performance across domains, yet their fundamental statistical behavior remains poorly understood. This paper develops a minimax analysis of ReLU message-passing GNNs with explicit architectural assumptions, in  both inductive (graph-level) and transductive (node-level) settings. For arbitrary graphs without structural constraints, we show that the worst-case generalization error scales as $\sqrt{\log d / n}$ with sample size $n$ and input dimension $d$, matching the $1/\sqrt{n}$ behavior of feed-forward networks. Under a spectral--homophily condition combining strong label homophily and bounded spectral expansion, we prove a stronger minimax lower bound of $d/\log n$ for transductive node prediction. We complement these results with a systematic empirical study on three large-scale benchmarks (ogbn\_arxiv, ogbn\_products\_50k, Reddit\_50k) and two controlled synthetic datasets representing the worst-case and structured regimes of our theory. All benchmark graphs we study fall in the slow-mixing, bottlenecked regime captured by our spectral-homophily condition, and ratio-based scaling tests show error decay consistent with the $d/\log n$ rate in real and structured settings, while the worst-case synthetic dataset follows the $\sqrt{\log d / n}$ curve. Together, these results indicate that practical GNN tasks often operate in the spectral-homophily regime, where our lower bound $d/\log n$ is tight and effective sample complexity is driven by graph topology rather than universal $1/\sqrt{n}$ behavior.

Published as a conference paper at ICLR 2026
MINIMAX SAMPLE COMPLEXITY OF GRAPH NEURAL NETWORKS: LOWER BOUNDS AND STRUCTURAL EF- FECTS
Ahmad Ghasemi & Hossein Pishro-Nik
Department of Electrical and Computer Engineering University of Massachusetts Amherst. MA 01003, USA
(aghasemi, pishro @umass edu
ABSTRACT
Graph Neural Networks (GNNs) achieve strong empirical performance across domains, yet their fundamental statistical behavior remains poorly understood. This paper develops a minimax analysis of ReLU message-passinggg GNNs with explicit architectural assumptions, in both inductive (graph-level) and transductive (node-level) settings. For arbitrary graphs without structural constraints, we show that the worst-case generalization error scales as /log with sample size n and input dimension d, matching the 1/Vn behavior of feed-forward networks. Under a bounded spectral expansion, we prove a stronger minimax lower bound of d/ log n for transductive node prediction. We complement these results with systematic empirical study on three large-scale benchmarks (ogbn_arxx) __aaxivvv, ogbn_ products__sa _0k,, Reddit 50k) and two controlled synthetic datasets representing the worst-case and structured regimes of our theory. All benchmark graphs we study fall in the slow-mixing, bottlenecked regime captured by our ppectra-hhoophiin condition, and ratio-based scaling tests show error decay consistent with the d/ log n rate in real and structured settings, while the worst-case synthetic dataset follows the Vlog d/n curve. Together, these results indicate that practical GNN tasks often operate in the and effective sample complexity driven by graph topology rather than universal 1/vn behavior.
condition combining strong label homophily and
regime, where our lower bound d/ log n is tight
INTRODUCTION
Graph Neural Networks (GNNs) have become a standard tool for learning from structured data, powering state-of-theeart systems in social networks, molecular property prediction, recommendation. and community analysis (Sen et al. 2008 Ruddigkeit et al.) [0012] Ramakrishnan et al.) (2014). Their success stems from message passing: node representations are iteratively updated using features from local neighborhoods. Despite this broad empirical impact, the statistical foundations of GNNs remain poorly understood. In particular, a fundamental open question persists: How many training samples are needed for GNN to generalize on a given graph, and how does graph structure shape this requirement?
For classical feed- feed-forward networks, minimax analyses show that ReLU architectures achieve gen- eralization error scaling as 1/ with i.i.d. samples (Golestaneh et al. 2024), contrasting with the simpler 1 1/n rate in parametric models. GNNs, however, break the independence assumptions underlying these results: node samples are correlated through edges, message passing couples distant regions of the graph, and the effective number of statistically independent observations can differ dramatically from the number of labeled nodes. As result, the sample complexity of GNNs cannot be inferred from standard leap-len theory, and must instead reflect the interplay between archi- tecture and graph topology. This raises a central question for modern GNN practice: What are the minimax limits for GNNs, and under what structural conditions do they arise?

---

Published as a conference paper at ICLR 2026
Most prior theoretical work addresses only the inductive graph-level regime, where each training ex- ample is an independent graph. In contrast, many widely used benchmarks, including ogbn_aaa arxiv, ogion products, and Reddit, operate in the transductive node-level setting: a single fixed graph is observed, a subset of nodes is labeled, and the model must generalize across the same graph structure. These two regimes differ sharply in their statistical difficulty. Independent graphs behave like classical samples, whereas node labels collected on a single slowly mixing graph may exhibit substantial redundancy. A principled minimax analysis of both regimes is therefore needed to understand when GNNs follow classical 1/ v behavior and when structural properties of the graph impose stricter limits.
This paper develops such an analysis. First, we establish worst-case minimax lower bound for ReLU pressage-passingg GNNs in the inductive setting, showing that no estimator can achieve error better than !2 Vlog d/n where d is the input dimension. This rate matches the 1/vni behavior of classical deep networks and holds on adversarially chosen graphs, such as path graphs, where minimal connectivity forces message passing to propagate information slowly.
Second, we prove a sharper, structure-aware minimax lower bound for the transductive node-level regime. Under a natural hompphily condition-reqirring strong label homophily together with weak spectral expansion, formalized as a small Laplacian spectral gap 22 S k/ log newe show that the effective sample size collapses from n to (log n) due to highly overlapping neighborhoods. In this regime, the minimax risk cannot decay faster than Q2d/ log n.), significantly slower rate than 1/ Vn. This result reveals that graph topology and mixing geometry, rather than neural architecture alone, can fundamentally constrain the statistical efficiency of GNNs.
anessage-passingg
Our empirical studies complement these theoretical findings using both controlled synthetic datasets and three large-scale real benchmarks. Synthetic worst-case graphs constructed to instantiate The- orem 1 follow the Vlog d/n rate exactly, while synthetic bottlenecked graphs satisfying spectral- homophily follow the d/ log n rate, confirming tightness of both bounds. Crucially, the three bench- mark graphs study satisfy the structural (slow-mixing) spectral- homophily condition required by our transductive lower bound (formalized in Section 33. Ratio-based scaling diagnostics then show that their empirical error curves remain stable when normalized by d/ log n, and diverge when normalized by vlog d/n,, indicating that practical GNN learning problems consistently operate in the structure- -imited regime predicted by Theorem 2.
The contributions are as follows.
1. We analyze both inductive (graph-level) and transductive (node-level) prediction settings, provid- ing minimax lower bounds tailored to each regime.
2. For arbitrary graphs without structural assumptions, we prove a lower bound of R.
2 logd
matching the classical 1/vn rate for ReLU networks.
3. Under the spectral homophily condition 2 I k// log n, show that the minimax risk tightens
to R = 2 logm reflecting the collapse of effective sample size on slowly mixing graphs.
4. Using three real benchmarks and two controlled synthetic datasets, combine structural diagnostics, ratio-based scaling tests, and stress tests to demonstrate that real graphs lie in the structural regime and empirically follow the d/ log n scaling predicted by Theorem 2.
Our results show that the effective sample complexity of GNNs is governed not only by ar- chitecture but by graph topology-particn time highligitgg the need for structure-aware generalization theory.
homophily, spectral expansion, and mixing
2 RELATED WORK
The sample complexity of deep neural networks is well studied. For fully connected and convolutional architectures, the minimax risk is known to scale 1/vn, reflecting the higher data requirements of deep learning models compared to classical parametric methods (Golestaneh et al. 2204)). Nonpara- metric regression under smoothness assumptions also yields convergence guarantees (Schmidt-Hieheri 2020), though these results differ substantially from those for modern deep architectures.
All logarithms are natural unless stated otherwise.
2

---

Published as a conference paper at ICLR 2026
In contrast, the theoretical understanding of generalization in Graph Neural Networks (GNNs) remains underdeveloped. Early efforts analyzed the VC-dimension of GNNs (Scarselli et al. 2009), but obtained bounds that scale poorly with depth and width. PAC-Bayesian approaches provided stability- alternatives (Liao et al. 2020p, yet sharp sample complexity characterizations are still lacking. Other lines of work investigate representational limits (Garg et al., 2020), or connect graph
topology to training dynamics (Oono & Suzuki 2021] Nikolentzos et al. 2022) However, lower
bounds on generalization, critical for understanding statistical limitations, remain scarce.
Expressivity and generalization of MPNNs. Franks et al. study message-passing GNNs from an perspective, establishing upper generalization bounds via VC/covering- number analyses, showing how node individualization and positional encodings boost expressivity while preserving learnability (Franks et al. 2024). Their guarantees depend on architectural size and the chosen individualization scheme. Our work is complementary: we establish minimax lower bounds for standard ReLU MPNNs with input-independent local aggregation (Assumption (AI)), exposing how graph structure shapes learnability through the spectral ppeetral-homophily condition (The- orem 2 In short, |ranks et al. (2024) characterize what is achievable (upper bounds), while our results certify the fundamental obstacles that remain for richer hypothesis classes.
Recently, Pellizzoni et al. analyzed GNNs with node individualization schemes, showing that such modifications reduce sample complexity by enhancing expressivity while controlling VC-dimension and covering numbers (Pellizzoni et al. 2024). Together with (Franks et al. 2024), these works chart the upper-bound landscape under expressivity positional encodings). Our focus is orthogonal: we establish lower bounds for standard message- passing GNNs without such augmentations, exposing an unavoidable dependence on graph structure.
augmentations (e.g., individualization or
Our work extends the minimax framework from feedforward networks (Golestaneh et al., 2024) to GNNs with arbitrary graph inputs, without relying on strong smoothness or independence as- sumptions. By incorporating graph topology directly, we derive intrinsic lower bounds on GNN sample complexity that align closely with empirical trends. Unlike our general bound (Theorem [[]. the structure-awan bound (Theorem 2 accommodates adjacency-masee attention by relying on mixing/locality rather than inputinndepeneent aggregation.
Taken together, these strands bracket the problem:
expressivity-drrs driven upper bounds (Pellizzoni et al. Franks et al. 2024) and structure-aware lower bounds (this work).
2024
PROBLEM FORMULATION AND MAIN RESULT
We consider a GNN operating on a graph G = EV with [V] nodes, A, and node features X,, E R for v E V.
E edges, adjacency matrix
Graphs and terminology. Throughout, (path graph Pm. on m nodes) has edges {(1, 2), (2, 3)..... members of our graph family and instantiate the hard distribution in the proof of Theorem D
allow arbitrary simple, undirected graphs. A chain graph
, (m - 1, m)). Chain graphs are admissible
Task settings. We study two prediction regimes with Y the output of GNN S. and q 2 its output dimension: (i) Graph-level (inductive): Each example is a graph G with features X, and the model outputs X() = Ý E R (ii) Node-level (transductive): A single graph G is observed; training/test examples are nodes v E V. The model outputs f(G, = Ý RVVx,, with the e-th row &e predicting node v.
Unless stated otherwise, losses are squared error for regression and cross-entropy for classification. Theorem I concerns graph-level (inductive) risk, and Theorem 2 node-level (transductive) risk.
ReLU Graph Neural Networks. A ReLU-based GNN with L message-passing layers realizes function f: G + Y, where G is graph with node features X, and Ý is the predicted output. Each layer updates hidden node representations as:
h (e+1) = = (w(() Agg h/0 + (() ddz) max 2), l e=
(1)
Here, W(O) E Redes xd, acts the aggregated neighbor messages AgsjeN()) h h/? and B(O Rdexixdl xde is the solf mixing matrix applied to n! Additive biases g(0) E Rde+s may be
3

---

Published as a conference paper at ICLR 2026
included but do not affect the minimax bounds. Agg is permutation invariant, input-independent aggregator (e.g., sum or mean). Node representations are initialized h Z/i-
Architectural scope and assumptions. Our lower bound in Theorem ! applies to message-passiaen ppsssigg GNNs that satisfy: (A1) input-independent, I-hop permutation-invariat aggregation (e-g., SUM, MEAN, normalized adjacency), and (A2) uniform layerwise Lipschitz/variation control, instantiated the f -ormr budget Ez= (IW( + || S Us. which promotes sparsity and is consistent with recent theoretical results on over-parameterized networks [Lederer] [0022] Taheri et al. 2020).
(Any equivalent operator-norm bound yields the same rates up to constants.)
Transformers and attention-basee GNNs violate (A1) and are therefore excluded from Theorem] | By contrast, Theorem 2 to adjacency-masked attention under suitable norm bounds (see Remarks 2
requires only adjacency locality and bounded layer operators, and thus extends
We assume ReLU activations, standard in GCNs, GATs, and GraphSAGE; the minimax bounds also hold for any larger class formed by replacing ReLU with more expressive or injective MLPs.
We define FONN (V,, L) the class of L-layer ReLU GNNs satisfying this constraint. For simplicity, we fix (v,, L) and write FANN.
Norms. We use the following norms throughout. For matrix R=*n, the entrywise & norm is ||Al|| = Ei, AAgl used for weight and bias constraints. For a vector v E R., ||ll2
denotes the Euclidean norm ||la|2 (Ein uf)
For matrix A, ||Al|2 denotes the spectral norm (largest singular value). For functions ʃ X - I. the L2 norm under P is ||/ = (B(G.x)~PP[(G. ()), 1/2
1/2
Risk notions. We quantify generalization error via minimax risks. Here f E FaNN denotes target function (ground truth), and f learned estimator depending on training data.
For readers less familiar with minimax theory, we provide a short primer explaining the general formulation and its specialization regression in Appendix A
Graph-level (inductive) risk: Let (G,, Y be i.dd training samples, where each G, is an independent graph. Define
R grapph (FONN) == inf sup
Eunna [f(G)
(2)
where Erain is over the training graphs (G,, X,,Y, ~ p and the inner expectation is over an independent test graph G ~ Pa-
Nove-level (transductive) risk: Given a fixed connected graph G = (V, E) with features X, let S C V be uniformly random set of labeled nodes and let f f(:; G, X,S) be the learned predictor. We define
1 M -(0))(()))
R.dde R (FONN) inf sup Es JTET
where the expectation is over the random labeled set S. Here, n denotes the number of labeled nodes.
These risks correspond to the inductive (graph-level) and transductive (node-level) settings. We will state explicitly which risk each theorem concerns.
Our first theoretical contribution yields a lower bound on the graph-level (inductive) risk.
Theorem (Graph-level Minimax Lower Bound (Inductive)). Let FGNN be the class of L-layer ReLU GNNs with weights satisfying Ehz ([) + [[B(')11) I Us. with L 2 1 and U, > Assume (G X4, Y are i.i.d. samples with Y, = f X,) Ug iid. N((,,²), fr FGNN-
Then there exists constant Knew such that, for all n 2 1 and d > 2,
oUs log
Rraaph (FGNN) 2 Knew
(4)
L
n
4

---

Published as a conference paper at ICLR 2026
Interpretation of Theorem 1 The risk decays faster than 1/vm, matching classical results for fully connected ReLU networks (Golestanch et al. 2024).
Sample-size implication. To guarantee error most e², one must have
2
2
K new
JV
log
K new
o o²0 logd
(5)
L
Compared to classical finite-dimensional parametric estimators (e.g., linear regression, where n > o² o2/e), GNNs require substantially more data to achieve comparable generalization guarantees.
Proof Sketch. We apply Fano's inequality (Fano & Hawkins, 1961) and construct packing set M C FONN by varying the first-layer weights W on path (chain) graphs. The information-hhen -thooretic tools underlying this argument (packing sets, the Varshamov Gilbert bound, and the KL formula for Gaussian regression) are recalled in Appendix [C) while the fixed-radius form of Fano's 's inequality appears in Appendix D Exhibiting hardness on one such family suffices to establish a minimax lower bound for the unrestricted graph class. Node features sampled X, (O, Ia), and labels follow Y, = (G, X,) ) + U, with U, ~ ~N(000²)
Packing step. The bound relies on Lemmal 2 which constructs a constant VarshamovGGllbet code realized by first-layer coordinate selectors and shows
CAU logd
M(2e, |I (1xa) 2
L22²
Applying Fano's inequality with KL divergence bounded by KL (I((P)1Pk)) S 2 yields
2² 2nc² /o2 2
2 CAu log (oggd/1222 1,263
Optimizing over e² gives the desired bound. The complete proof is provided in Appendix E
Remark 1 (Worst-case graphs). Theorem is established path graphs (chain graphs), where each node has degree at most two. This minimal connectivity creates bottlenecks that slow message passing, making depth the dominant factor. factor. Path graphs thus serve canonical worst-case instances: hardness on this sparse structure certifies the lower bound for all admissible graphs. Although denser graphs may empirically converge faster, the path graph ensures the universal worst-case rale.
Remark 2 (Exclusion of attention in Theorem D.. The packing construction for Theorem I exploits assumption (AI), i.e. input- innupdddddeenentt local aggregation. Architectures with attention violate (Al) because their mixing weights depend on hidden features; hence the theorem does not apply graph transformers or attention-bans GNNs. This does not contradict the lower bound: by monotonicity of minimax risk, enlarging the hypothesis class cannot reduce the bound.
Theorem establishes / loud scaling, whereas our empirical results (Section 4) indicate //lgg scaling in practice. This motivates a refined lower bound under structural graph assumptions, formalized in Theorem? 2 We first define the notion of pnectral-homophe
used therein.
1/2 1D2 consideration and let (2( be its second-smallest eigenvalue. We assume (2(C) < x/ log for constant K > This is distinct from sabel-homophily assumptions (see Appendix G
pnectral-homophiie Let C = 1 1-2
1/2 be the normalized Laplacian of the graph under
Spectral gap, homophily, and bottleneckedness. A small (2 indicates weak expansion and slow mixing (e.g.. via Cheeger-type relations), creating bottleneck satleneck-sparse cuts separating dense communities-than limit how much independent label information message passing can extract. Such structure prevents information injected one region from propagating globally, as strong homophily (nodes tightly connected within communities) and weak expansion (few inter-community edges) cause messages to "get stuck" within communitics. The condition X2 S k/ log n captures this effect: the smaller the gap, the fewer effectively independent samples GNN receives. Thus, pnectral-hoopphee quantifies the bottleneckedness underlying the 2(d/ log n) lower bound in Theorem 2
Why the transductive setting amplifies this difficulty. In the node-level transductive regime, all node features are observed but only a subset of labels. When the graph mixes slowly, these labeled nodes become highly correlated: message-passing neighborhoods overlap, and nearby labels offer
5

---

Published as a conference paper at ICLR 2026
nearly redundant information. Consequently, the setting provides far fewer effectively independent signals than the raw label count suggests-ont about one in every O(logn) labels contributes genuinely new information. This reduction in independence, driven by the interaction between message passing and slow graph mixing (rather than the number of labels alone), underlies the (log n) effective sample size and yields the Qt(d/ log n) minimax rate in Theorem
Together, these observations motivate fundamentally different minimax regime for node-level prediction. When structural bottlenecks force mixing to occur over ((og n) steps, the n labeled nodes provide far fewer than n effectively independent constraints. Theorem 2 formalizes this intuition by showing that under spectral hoomoriily. every renmaatle-rearrlssss of architecture or training procedure- faces minimax barrier that decays only as s/lon..
Theorem 2 (Structured- Graph Graph Minimax Lower Bound (Node-Lever Transductive)), Let L 2 1, v, O, and let G (V, E) satisfy the peectral-homohiile condition X²( S k/ log n for some universal K. >> O, where n is the number of labeled training nodes and L. is the normalized Laplacian. Then there exists universal constant > such that
d
(FONN)
(8)
TI2
log n
As discussed in Appendix G and formally shown in Lemma 3 the structural condition A2 k/log is asymptotically non-vacuous and excludes all graph families with nonvanishing spectral gap.
Interpretation of Theorem This bound decays more slowly than 1/Vī, making it tighter whenever the spectral-homoppily condition holds. Extensions to adjacency-masker attention (e.g., GAT) are discussed in Appendices [H and practical guidance on improving constants without changing the (d/ log rate is in Appendix K If larger, indicating strong expansion), the independence argument breaks down and the analysis reverts to Theorem 1 yielding the O /log d/ni rate.
condition fails (e.g.. X2 is
Sample-size implication. To achieve generalization error e², the following must hold:
o²u²? I 2
o'udd 2 n 2 exp 11
(9)
L logn
implying exponential sample complexity in 1/c², far worse than polynomial rates.
Proof Sketch. The proof formalizes the idea that under ppetral-homoophe (A2 S K/ log n). the n labeled nodes do not act as independent samples. Slow mixing causes message-passien -passiga neighborhoods to overlap heavily, making nearby labels largely redundant. Consequently, the number of statistically independent labels collapses to K = (log
The argument proceeds by identifying K well-separated nodes whose receptive fields interact only weakly under the dow-mixing condition. On these K nodes, we construct packing set of GNN functions using wenstant-weight codewords, ensuring that functions differ one "block" yet remain within the allowed & norm budget. Two functions that differ in one block achieve separation of order (u,/LK)² A, while the Gaussian noise model keeps the KL divergence between their induced distributions of order 1/ K. Applying the fixed-radius version of Fano's 's inequality this K-block packing yields a minimax risk lower bound proportional to d K = d/ log n. Thus the slow-mixing structure limits the amount of independent information available to any algorithm, leading to the stated ((d/ logn) n) rate. The complete construction and technical details are given in Appendix
4 EMPIRICAL STUDIES
In this section, we present proof-of-concept experiments illustrating how the minimax bounds appear in practice. We evaluate three real benchmark datasets, ogbn_arxiv, arxivv ggbn_produuts. 15kk, and Reddit 50k, alongside two synthetic settings designed to isolate the behaviors predicted by our theory. The first, Synthetic-Fand WorstCase (Thm-1), directly instantiates the worst-case error curve Vlog d/n from Theorem The second, WorstCase Botteeneottkekkkk 20k (Thm-2), is a controlled coamumity--bottlnnee graph dataset satisfying the spectral homophily condition Xa S K/ log
Wynntetti-FanooorssCCeee
Experiments use three representative GNNs: GCN (iipf & Welling 2017), GAT (Veličković et al. 2018), and GraphSAGH AGE (Hamilton al. 2017a). Full dataset descriptions, preprocessing. and

---

Published as a conference paper at ICLR 2026
Dataset
Spectral Gap (A2)
150
Homophily
ogbn_arxiv
0,2112
2.5428
0.6551
ogbn_products__55 products_50k
ogbn_
0,9201
9.9557
0.7956
Reddit_50n
0,9683
10.4769
0.7748
WorstCase Bottleneck 20k
1.0359
10.2586
0.3164
Table 1: Graph Structural Properties Relevant to Theorem 2
Figure I: Stability comparison of scaling-law ratios for Synthetic S (Thm-1).
1.0
04
Rato
0.2
040
(sample 2.20)
licensing appear in Appendix M Details of the synthetic constructions for Theorems and 2 are provided in Appendices 0 and respectively.
Methodology. All experiments were implemented in PyTorch Geometric using a unified protocol across datasets. For each dataset, we trained GCN, GAT, and GraphSAGE on a log-spaced grid of sam- ple sizes {49..... Rmax J. where Rmax is the size of the training pool: 169,343 for ogbn_arxivv v, 50,000 for sesin_products. __0kk and Reddit_5t __0k,, and 20,000 for the synthetic settings (Synthetin c-anoooo Case (Thm-1) and WorstCase Bott w 20k). For each n, models were trained under 20 independent seeds (random initialization and random subsampling). To compare empirical behavior with Theorems I and 2, we computed the theory-aligne diagnostics Err(n)/ / /lo d/n and Err(n)/(d/ log n). We then aggregated test losses across seeds and fit four é_.
candidate scaling laws, C1 + -. C2 C3 + log and 64 + n n² using nonlinear least squares (curve_ffl fit) with inverse-variance weighting. Fit quality was evaluated via residual sum of squares (RSS), mean squared error (MSE), R2, and log-log slopes of the error curves.
Structural Verification of Theorem 2 Conditions. To test whether each dataset falls in the structural regime of Theorem 2 we compute X2 (C), homophily, and single dataset-level constant Ko that certi- fies the condition uniformly over the training-size grid N. We set == max,e >₂ log and verify (2) < Ko/ logn for all n N. Table [ reports (2()), Ko, and homophily, confirming that real-world graphs lie in the regime where Theorem 2's d/ log bound ap- plies. Worst bottleneck_2u0 satisfies the inequality tightly by construction, while Senthetic-FanoWozseee
violates it, yielding genuine Theorem- 1-type worst case. These trends match later results: more homophilic graphs with small spectral gaps mix more slowly, consistent with Theorem 2's d/ log convergence. Details for computing (2(L) are in Appendix
Direct Scaling Diagnostics via Error-Ratio Plots (Primary Evidence). We treat ratio diagnostics the primary empirical test of our theoretical claims. For each mataset-model pair, we compute Ratio (n) Err(n) / / Vlg d/n (Theorem form) and Ratio (n) Far(()) / (d/ log n) (Theo- rem 2 form). A ratio that remains approximately constant across n indicates empirical consistency with the corresponding theoretical rate.
Synthetic-Fann Fano Farhheeii-FFoooossSCCCCCC WorstCase (Thm-l). As expected, Figure shows that Ratio, (n) stays essentially constant and near one, confirming that the synthetic construction follows Vlgg d/n. In contrast, Ratio (n) decreases steadily with n, indicating that the d/ log n scaling does not fit the Theorem-1 instance. This behavior verifies the correctness of the construction. Additional controlled tests isolating the n 1/2 and Vlog dependencies appear in Appendix
World Datasets. Figures 2 3 and 4 show that across all three datasets and architectures, Ratio (n) Err(n)/(d) log n) stays nearly flat over two to three orders of magnitude n,, while Ratio, (n) = Exr(n)/ / /log d/r increases steadily, often sharply. This highlights a clear pattern: real
GNN datasets empirically follow the d/ log scaling predicted by Theorem 2.
7

---

Published as a conference paper at ICLR 2026
sicipee
113
ogbn_arxiv Figure 2: Stability comparison of scaling-law ratios for ogbn arxiv (left: GAT, middle: GCN, right: GraphSAGE)..
Pork
Figure 3: Stability comparison of scaling-law ratios for ogbn gebn__products_000 monduccts550kk (left: GAT, middle:
GCN, right: GraphSAGE).
Stress- Stress-Testing the Bounds with Synthetic Worst-Case Graphs. To demonstrate that both minimax bounds are tight in their respective structural regimes, we evaluate the synthetic graph satisfying Theorem 2 assumptions: WorstCase BetettBotttteeeeeeeeeeeeeeeeeeee Photteeneche leneck_20000
As shown in Figure 5 Ratio2 (n) remains stable across n while Ratio, (n) increases sharply, mirroring the behavior observed in real datasets. This confirms that the d/ log n rate is tight under the spectral-homophne structure.
Estimating the Empirical Constant C*. To further quantify the tightness of the minimax lower bounds, we estimate the empirical constant C** associated with the structured- -ancuured-grahh rate. For each dataset and architecture, we compute C* Rs Frr(n))
d/logn" the plateau value of the ratio diagnostic
Err(n)/(d/ log n). Across real datasets ogbn_arxiv, arxiv, berbb__prduutts.mmm __kk Reddit_ 50k, C* remains stable over several orders of magnitude in n, with dataset-specific ranges: approximately and 10-20 for Reddit_500 For the synthetic WorstCase Bottl 20kk benchmark, C* is in the range 8-12, consistent with sharper bottleneck structure. This stability supports the conclusion that the empirical error scales proportionally to d/ log n within controlled constant factor, as predicted by Theorem 2.
15-25 for ogbn_arxiv 18-22 for agiot_products_______
Supplementary Curve-Fit Analysis. Curve fitting is only secondary evidence in our empirical study, since fits can conflate noise, architecture bias, and optimization variance and thus, they are not a reliable basis for testing minimax rates. In our experiments, 1/ log is the best-fit model in only combinations, so curve fits alone do not reliably reveal the scaling law. For
(3/13) architecture transparency. Appendix (erinndxxxxssoo shows curve-fit plots for ogbn_ arxiv and Reddit ___5000 50k and provides complete raw-error tables (mean + standard deviation over seeds) for each dataset, architecture, and training size; Table reports the corresponding fit metrics.
Daase:
Maki
RS8
MSE
R0
RSS
MSE
R5S
MSE
30
RSS
MIE
Bot.
19006:04
2 2.3000006
11053407
1 04
5/002
45175-03
K1099-05
6 6467
4.4007-05
OKN
175054-11
21993-09 53
53589
171606-11
3.4955- 50
23045
417382-011
5.985x-3
65080
205-46440
259832422
17U5
cyda antr
QupkkAre
13000.01
54301e-09
10011-01
59the-09
50015
10530-000
13213-02
4200e-00
41854.m
0300
1
ogen prolecs 36
OCN
6330c-00
84395-40 63
17163-001
2 14500 01
5.605
47000-000
59360-03
0.641
60513-00
15442-01
01606
1/lag=
135164401
189K5.
53877
187554440
54000444
117364-01
k15-44401
B1413
1/lano
Retdi SU6
OCN
016014-01
122002-02
53610
33071641
411364-00 00
33631
1.3076400
14304-03
67736
3A355-40
454 45415640
0370
3/m
Oup45X0E
203811
41401c100
1.827663
11175440
1/n
GAT
1.577e400
24119-40
01387
WacaCaal Bortiwes 2I
OCN
24388-01
4.3067-00
437984422
8.177 04
DMIIT
$3400-01
3-83806-33
0.866
43115-400
7 10000-40
0.00%
1/n
Wankllne Beskonek
Oxp45X0E
4.625601
33051c01
53903669
1005ec401
18637-00
6.079
Table Comparison of Fit Metrics Across All Models and Datasets (Updated Results)
Unlike the ratio diagnostics, which unambiguously favor Theorem 2, the curve fits show mixed behavior: httrob__prduuts_____ 50k the best fits tend to favor 1/ log n, whereas ogbn_arxix arxiv and Reddit- -50k the fits sometimes prefer 1/n or 1/v/. This is expected and does not contradict theory: Curve-fit comparisons reflect finite-sample interpolation accuracy, not asymptotic minimax
8

---

Published as a conference paper at ICLR 2026
307
-0-
Figure 4: Stability comparison of scaling-law ratios for Reddit_50k (left: GAT, middle: GCN, right: GraphSAGE).
Brictine
Lake
1
8-0
Figure 5: Stability comparison of scaling-law ratios for middle: GCN, right: GraphSAGE).
20k (left: GAT,
behavior, Ratio diagnostics directly test asymptotic structure and therefore earry higher evidential weight. Thus, curve fits serve useful supporting evidence but are not the primary validation method.
Summary. By integrating structural verification, ratio-based scaling diagnostics, synthetic stress tests, curve fits, and raw-result tables, our empirical analysis consistently reveals that: (1) all real- world graph datasets lie inside the structural regime required for Theorem 2 (2) ratio diagnostics unambiguously select the d/ log n rate over / /log d across architectures and datasets; (3) synthetic graphs constructed to satisfy Theorem behave like real datasets, while the Theorem-1 synthetic graph behaves in the opposite way; and (4) curve fits do not contradict this conelusion.
Across real benchmarks with weak spectral gaps and moderate-to-high homophily, empirical conver- gence often decays far more slowly than the classical 1/ / rate, frequently approaching 1/ 1/log n. This slower decay matches the structural constraints captured by Theorem 2 indicating that GNNs may need larger training sets to generalize reliably on graphs with long mixing times or bottle- necked communities. These trends highlight the importance of structure-aware generalization theory: effective rates depend on graph topology and mixing geometry rather than universal assumptions.
Taken together, the evidence shows that practical GNN learning problems operate in a spectral- homophily regime where Theorem 2 provides the correct characterization of sample complexity.
CONCLUSION
This paper establishes the first minimax characterization of GNN sample complexity across both inductive and transductive regimes. We show that the familiar /log d/n n rate arises only in adversarial graph settings, while realistic graphs with slow mixing and strong community bottlenecks obey a fundamentally harder limit: a structure-driven M(d/ log n) minimax rate. This reveals that graph topology, not architecture, dictates the effective sample size available to GNNs.
Our empirical results deliver a clear message. Theorem-1 synthetic graphs follow the /log d/n n curve exactly, but all real benchmarks and the Theorem-2 synthetic construction show stable d/ log behavior across architectures and multiple orders of magnitude n. Structural diagnostics further confirm that real graphs lie squarely within the spectral-homoppe
regime where Theorem 2 is tight.
These findings overturn the assumption that GNNs inherit classical 1/ /n-tttp generalization and instead demonstrate that practical GNN learning is typically structure-limited. Future work should develop architectures, sampling schemes, or pre-training strategies that counteract slow mixing, and extend structure-await analyses to attention based and higher-order models. Our results chart clearer theoretical roadmap: generalization on graphs is governed by mixing geometry, and any scalable GNN methodology must contend with this structural barrier.
9

---

Published as a conference paper at ICLR 2026
6 REPRODUCIBILITY STATEMENT
We have taken several steps to ensure the reproducibility of our work. All theoretical assumptions, theorems, and the proof sketch of Theorems 2 proofs of Theorems [ and 2 are provided in Appendix Eland Appendix respectively. Supporting technical components, including primer on minimax risk (Appendix (A). degenerate GNN realizations (Appendix(B). information theorretcc tools (Appendix C Fano's s inequality (Appendix D spectral and
andd are explicitly stated in Section The complete
homophily assumptions (Appendix G). operator-norm control for attention (Appendices D synthetic worst-case construction of Theorem (Appendix [D), and synthetic structured bottleneck dataset for Theorem (Appendix P) are all provided for completeness. Experimental protocols are described in Section 4 while dataset descriptions, training procedures, and infrastructure details appear in Appendix M To further support verification, we provide the full source code as supplementary material, including implementations for data loading, model training, evaluation, and error analysis. The package also contains scripts to reproduce all experimental results, regenerate ETEX tables, and visualize learning curves. Together, these resources ensure that both the theoretical and empirical results reported in this paper can be independently reproduced and validated.
7
ACKNOWLEDGMENT
This work was supported by NSF under Grant CNS-2150832 and Grant CNS-2528914.
REFERENCES
Afonso S Bandeira, Amit Singer, and Daniel A Spielman. A cheeger incquality for the graph connection laplacian. SIAM Journal on Matrix Analysis and Applications, 34(4):1611-1630, 2013.
Robert M Fano and David Hawkins. Transmission of information: A statistical theory of communica- tions. American Journal of Physics, 29(11):793-794, 1961.
Billy Joe Franks, Christopher Morris, Ameya Velingker, and Floris Geerts. Weisfeiler-leman at the margin: When more expressivity matters. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.). Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings Machine Learning Research, pp. 13885-1333 13926. PMLR, 21-27 Jul 2024. URL httpttts///ccceedin.eg mlr. wttppp//s///raaaeeeeeepeee .4.22ml...mmmm.mmm
Vikas K. Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks, 2020. UtLhtttss://adt //tp:vv///aivvea/aa http://wwwwppaaaaaaa.////a wwtpabs./....2 06157
Edgar N Gilbert. A comparison of signalling alphabets. The Bell system technical journal, 31(3): 504-522, 1952.
Pegah Golestaneh, Mahsa Taheri, and Johannes Lederer. How many samples are needed to train deep neural network?, 2024. URL
16696.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning large graphs. In Guyon, U. Von Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017a URL /tsp///tspss//prrceedin....ssss wttp://1////eeeee/ee/eeee http://///0.....occc3caaaaaaaaar
cc/paper files/
patp://aeeeeeaaaaapppppp. Paper.
William Hamilton, Rex Ying, and Jure Leskovec, Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, volume 30, pp. 1024-1034, 2017b.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs, 2021. URL
hnttps://erse wwt. 20035 00687
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2017. URL httts:///aaat www.:bagg///... 609. 02907
10

---

Published as a conference paper at ICLR 2026
Johannes Lederer. Statistical guarantees for sparse deep learning, 2022. URL https://arx:: exq/abs// 2212.222.... 05427
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathemat- ical Soc., 2017.
Renjie Liao, Raquel Urtasun, and Richard Zemel. pac-bayesian approach generalization bounds for graph neural networks, 2020.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. Permute me softly: Learning soft permutations for graph representations, 2022. URL
01872
Kenta Oono and Taiji Suzuki. Graph neural networks exponnttialllll lose expressive power for node classification, 2021. UtL/hatpee///axxx...ooo////////p
Paolo Pellizzoni, Till Hendrik Schulz, Dexiong Chen, and Karsten Borgwardt. On the expressivity and sample complexity of node-individualized graph neural networks. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):1-7, 2014.
Lars Ruddigkeit, Ruud Van Deursen, Lorenz C Blum, and Jean-Louis Reymond. Enumeration of 166 billion organic small molecules in the chemical universe database gdb-17. Journal of chemical information and modeling, 52(1 1):2864-2875, 2012.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-88) 2009. doi: 10.1109/TNN.2008 2005605.
Johannes Schmidt-Hiehee Nonparametric regression using deep neural networks with relu activation function. The Annals of Statistics, 48(4), August 2020. ISSN 0090-5364. doi: (0.1214/19-aos 1875.
URL http:
doi http://xxxddooorg////// 1tt.r///....11119111111 1214/19-
Prithviraj Sen, Galileo Namata. Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. A/ Magazine, 29(3):93, Sep. 2008, doi: 10. 1609/imaa. v2913.2157. Uttsttps:: /ww.//aaaaaaaaaaaaaoaaa..aa.a.a. www.rr/ragggggnnee....a wnweeeiidxxx.emm/ php/ a gaz i article/view/211
Mahsa Taheri, Fang Xie, and Johannes Lederer. Statistical guarantees for regularized neural networks, 2020. URL /attps:// wwtp//ggggaaaoseeeee 00294
Alexandre B. Tsybakov. Introduction to Nomparametric Estimation. Springer Series in Statistics. Springer, 2009. See Lemma 2.10, Chapter 2.
Rom Rubenovich Varshamov. Estimate of the number signals in error correcting codes. Docklady Akad. Nauk, SSSR, 1177799774,, 1957.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, 2018. URL RRLltttps://axxiy wwtpa//wwww.or/////////10/ 10903
Martin J. Wainwright. High-Dimensional Statistics. Cambridge University Press, 2019a.
Martin J Wainwright. High-dimensione statistics: A non-asymptotic viewpoint, volume 48, Cam- bridge university press, 2019b.
11

---

Published as a conference paper at ICLR 2026
APPENDIX CONTENTS
Primer on Minimax Risk and Regression as Special Case
12
Degenerate GNN Realization
13
Information- Theoretie Tools
13
D Fano's Inequality (Fixed-Radius Form)
14
E Minimax Lower Bound (Proof of Theorem
14
E.1 Exact Quadratic Solution for e"
17
Structured-Graph Lower Bound (Proof of Theorem 2)
18
Interpreting the Spectral-Homophie Assumption
20
H Mixing Time and the Spectral Gap
21
Operator-Norm Control for Adjacency-Masked Attention
22
Adjaceney-Masked GAT Layers under Theorem 2
23
K Practical guidance for data-scarce graphs
23
Architectural drivers of heterogencous scaling
24
M Experimental Details and Settings
24
Structural statistics
27
Synthetic Worst-Case Construction and Numerical Validation of Theorem
28
0.1
Worst-Case Family from the Packing Construction
28
0.2
Rationale for Synthetic Instantiation of the Minimax Curve
29
0.3
Synthetic Hrror Generation
29
0.4
Implementation Summary
29
0.5
Interpretation
29
P
Synthetic Structured Bottleneck Dataset WorstCase Botteencck 20k (Thm 2)
30
P.
Graph Construction]
30
P.2
Node Features and Teacher Model
30
P3
Spectral and Homophily Diagnostics
P.4
Train/ Trainn/Vlidation// Test Split and Sample-Size Grid
31
P.5
Early stopping and evaluation Aggregation, Curve Fits, and Ratio Diagnosties
32
P.6
32
Q
Supplementary Curve-Fit Analysis and Raw Results
32
Q.1 Curve-Fit Plots
32
Q.2 Raw Error Tables for Reproducibility
33
R Synthetic Experiments Verifying the Minimax Scaling Law
39
S The Use Large Language Models (LLMs)
39
A PRIMER ON MINIMAX RISK AND REGRESSION AS A SPECIAL CASE
Minimax theory provides a principled way to quantify the best achievable performance of any estimator over given hypothesis class. Because this background may be unfamiliar to some readers in the GNN community, we provide a short overview. more complete treatment can be found in Chapter 15 of (Wainwright] 2019b).
12

---

Published as a conference paper at ICLR 2026
A.1 GENERAL MINIMAX FORMULATION
Let θ denote parameter or function class, and let Pa be the distribution of observed data under parameter 0 E ④ For a loss function L(0, 0), the minimax risk is defined
Mr, (+) = inf sup Ep, [(0,0)] 0E@
(10)
This quantity characterizes the best estimator (infimum over all measurable procedures) against the worst-case parameter è (supremum over 6). A lower bound on (e) therefore shows that no algorithm can achieve eπror smaller than this rate.
A.2 REGRESSION AS SPECIAL CASE
The supervised regression problem studied in this paper is an instance of the minimax framework. We assume the labels follow the model
Y = (G,
U ~ ~00
(11)
where f is the true target function. We restrict f* to the hypothesis class FONN, consisting of L-layer ReLU GNNs with width
The loss function is mean squared error:
L(f.f) -[
(12)
The minimax risk for the regression setting is therefore
(FGNN) inf sup f EFFGN
-(
(13)
This is the precise quantity lower-bounded in Theorem (inductive graph-level setting) and Theorem (transductive node-level setting). In our analysis, the sample size n corresponds to:
Inductive (graph-level); the number of i.i.d. labeled graphs.
Transductive (node-level): the number of labeled nodes in a single graph.
The statistical difficulty differs across these two regimes due to independence in the inductive case strong dependence induced by graph connectivity in the transductive
B DEGENERATE GNN REALIZATION
We construct lne-layer ReLU GNN on the original graph (with self-loops) using the identity aggregator, Agg identity. this case, each node aggregates only its own features a degenerate but still admissible instance of the message passing, With weights set as W3 = LK 8 and zero bias, the network output
K
(z(
((1)).
LK
j=1
which lies in FUNN(U.: 1). Although message passing here reduces to self-loops, this subclass is included in our hypothesis space. Since minimax lower bounds apply to any subclass, establishing hardness for these degenerate cases certifies hardness for the full class.
C INFORMATION
TOOLS
For completeness, we record the remaining tools used in the proofs of Theorems [ and 2 These results standard in empirical-process and information-theereiic lower bounds.
13

---

Published as a conference paper at ICLR 2026
Packing sets and packing number. Let (F, p) be metric space. A set (fi...., fua Fis 5-packing if p(fe. fu) 2 ó for every # The packing number is
M(..F, F. p) == ( M a ó-packing of size M).
This definition follows Wainwnight
2019a Def. 5.3).
Varshamoy-Gilberf bound. least d/4 and cardinality
There exists a subset C {0, with pairwise Hamming distance at
C
24/8
as established in Giibert 1952 Varshamoy 1957). This result is used to construct large packing sets for the function classes considered.
KL divergence for Gaussian regression. Consider the regression model with fixed design Xi...., X2 and i.id. noise Y, f(X,) U, Uj NN o²) independent. Let p(a) denote the joint law of (Y,...., ..) (conditional on the design). Then
(((()) o(x.))? ([ 20
1
n
If the design is random i..dd from Px, taking expectation over X yields
Ex [KL(P) (
20 Ilf gllia(Px)'
Use the proofs. These tools are invoked jointly with the fixed-radius Fano inequality (Lemma)) to obtain minimax lower bounds via the standard "packing KL Fano" argument.
D FANO'S INEQUALITY (FIXED-RADIC FORM)
We state the specific version of Fano's inequality used throughout the proofs. It is a standard corollary of Lemma 2.10 in (Tsybakov 2009).
Lemma -Fano-Tsybakov, fixed-radius form). Let (O, d) be metric space, and let (Po Q) be a family of distributions on X. Suppose there exist M 2 points oI,..., 0M E such that:
(i) Separation: d(0j. 0k) 2 2s for all j + k;
(ii) KL control: max (L(PPe PPP I 8.
Then, for any estimator 0,
E²
(1
3 + log 2 log
inf sup 0
Ee (e(
2
The bound is meaningful whenever 3 < log M - log 2.
This fixed-radius form is the one applied in all lower-bound arguments. It follows directly from Lemma 2. 10 in (Tsybakov) 2009). but is stated here for completeness and to keep the paper self- contained.
E MINIMAX LOWER BOUND (PROOF OF THEOREM
We begin with technical packing lemma, which establishes the key combinatorial bound used in Step I of the proof of Theorem] [
Lemma (Packing for ReLU under Gaussian features). Let X No La) and ((z) max (0, 2). Consider (". L), the class of L-layer ReLU GNNs with
(1]((0) 11 (l(00 s V.-
14

---

Published as a conference paper at ICLR 2026
There exist absolute constants C, CA O such that for every E (0, cvs/L]. the 2e-packing number of FGNN(Us; L.) with respect to the L2 (Px) metric satisfies
log M(2,, FONN(Us, L), (1 2 CA 2
log d.
Proof. Fix 2 and v, > O. We construct a family {fs} indexed by r-subsets S C [d], for choice of defined below, and show is 2c-packing.
(L1) Realizable subelass and budget. r E {l,...,d df and define the centered ReLU feature
((=) = ((=) - Elo(Z)] = m0, V2n
Z ~ 10,
and the functions
fs(z) == a
ΣE(zz)
Ō(1z)
with
Co
Lr
JES
where co E (0, 1/2] is an absolute constant.
We realize fs using most nontrivial layers (which is admissible long (U.: L) is interpreted as depth < L): the first layer forms the coordinates {Ø(z)) : S} and the final linear layer sums them with coefficient a. Both layers use --norm at most r|al = covs/ L, hence the total budget is
Eawwo + [IB()))) & 2r|a| =
200
U S Un:
L
since co & 1/2. Therefore ss FGNN(U,, L).
(L2) L2 separation.
Let 2 ~ N/0, 1) and Ø(2) = max(0, 2} 1/ 2T. Then B[ő(Z) = 0 and
1
Blo(z) [[((2) -[o
us (0,
2
For * k, independence and centering give (xx =
Let S,T C [d] with |8| [T] and D = SAT with m = DD. Then
fs(ø) fr(x) Σ 7 p(z,), 7 (+1.-11,
JED
and orthogonality in L2(Px) yields
|ss
fr frlll1((x)) = a² Σ E(o(())) us m.
JED
In particular, since m S 2r, we also have the diameter bound
lls fr - 2a UgT. 20²usr.
(L3) Constant-weight code. By the Varshamov-Gile exists C {S [d] |S| = r) such that for all distinct T C, |SAT] r/2 and |C] (ed/r)" for a universal E (0, 1). Combining with (L2) gives, for * TeC.
bound for wengta codes, there
Ilfs - frlle((P)) 2 a 2
(L4) Choosing to achieve 2e separation.
We want || - frlles(Px) 2 2c, i.c.
a
Us
2
> 2e.
With a = (cous)/(Lr) this is equivalent to
2 b
8 1
We take
c Us
u
and assume S Us
=
16
_
with C 0 small enough so that
d/2.
15

---

Published as a conference paper at ICLR 2026
(L5) Packing size. From (L3) and d/2 we get
log M(2e, FONN, |l (lxx()))) 2 log/ci 2 c'r logg/n) 2 d
2
rl
log d.
Substituting the choice of from (L4) and absorbing absolute constants (including co, c' and the ReLU-Gaussin factor) yields
2²
log. M2ee, FONN, llxx(Px)) 2 CA
log d
T
for a universal CΛ > O. proving the claim.
With Lemma established, now prove Theorem
Proof. The proof follows the standard Fano-packing method: we construct large packing set, control pairwise KL divergences, and apply the fixed-radius form Fano's inequality. The required cnoomationnthhoreee tools are summarized in Appendix C and the version of Fano's 's inequality used
below is stated Appendix D Step invokes Lemma whose proof appears above.
Step 1: Packing number. By Lemma (f of FGNN with
2
for every S CU./ I, there exists 2c-packing M
0. log d
log 2 Ao/e2,
Ao Ca
Step 2: KL, divergence control. Let Y + U, with U4 ~ NO, o²) i.idd and X, L.d. Px- For any hypotheses f,, fx M the n-sample laws satisfy
Ex [KL(P) 1P 2n ||I (xx))
By construction of Lemma
2 (sce the diameter bound in (L2)), all pairs in the packing satisfy
[lf, - full2, I CsapE" for a universal constant Csep 0. Hence
B max Ex [ [I(())) S jk
CSep 2
n CKL a²
e
CKI. = Csep
20
We apply Lemma with separation radius 2e and KI. bound 3:
}
nCCKLE2// /02 + log 2
sup e>u
log M
Using log M 2 Ao/e² from Step yields
nCKI, F/cr,e//o0 /022 + + log }
2
((NNND((FNNN 2 sup
1
<>0
2
Ao
Step 3: Optimizing over Let 2. The bound reads
nCKI,* 2 /02 + x log 2
g(x) 1
Ao
Choose so that the parenthesis equals 1/2:
1 nC 122/0222222 + x log
Ao
2'
which yields
nCKL o2
12 + (log 2)x An 0.
The positive root is
0²
T = 2
(llog 2 + / (log 2)2 + 2n An CkL
2nCKL
For this choice,
R(n,)VD((FNN) 2 4
16

---

Published as a conference paper at ICLR 2026
Step 4: Asymptoties and constant. the square root:
When is large enough that 2n
(log2)²
expand
AD
RL
Thus
R(n.)iD(FGNN))
1
Ao
VCCA (V2CKL)
logd n
4
v KL
n
L
Define Knew
JCA 1/2CKL. O.
Step 5: Validity for all n. The exact root expression for e² shows that the bound holds for all
1, not just asymptotically. Writing
2
o² SnCKL
(-logg
(log
2nAgCCi. 2)0 2)
o²
one checks that the bracketed term is Q2 12), hence the rate Knew (ou,/ (100/(logg (log d)/n holds uni- formly in (with smaller constant if is very small).
Step 6: Dimension condition.
Finally, d 2 ensures log > 0 so that Ao > 0.
This completes the proof of Theorem
I
E. EXACT QUADRATIC SOLUTION e2
In Step 3 of the proof of Theorem equals 1/2:
we choose c² = x. so that the parenthetical term in Fano's 's bound
nOKI, /02 log 1
Ao CΛ 2² log d
Ag
2
This yields the quadratic
nCKI. 02
Ao 0,
x²
(log2)
whose positive root is
2nAn σ²
2
log +
/ (1o +
(14)
2nCKL
Substituting Eq.
14
into the fixed-radius Fano inequality (Lemma D gives
R Vn 2
2²
o²
(logg log
(log 2)2 +
2nAACKL (15)
SnCKI.
o²
Asymptotics. square root in Eq.
When large enough that 2mA > 2)2 first-order expansion of the
144 gives
2
Ao 2CCLL
(1+0(1)),
(FNIVD(FFNN) 2
VCA 1V20KL.
log d n
(1+o(1)).
n
L
Uniform-in-n bound.
Define
2nAoCKL
((n) = log 2 + V (log 2)2 +
o²
Then {pn) is strictly increasing in n, satisfies (0) 0, and ((n) V2n as - co. From Eq. (15).
o² (m))
R (FNNN) = 8nCKL ((2) >
inf ISm
K.
SmCCi Kr
Vn
17

---

Published as a conference paper at ICLR 2026
for any fixed no E N and target rate K.
L Choosing
VCA
(mm)
K =
min
min Ismgno
4V2CKL vmAg 20,
4V22KLL
we obtain the uniform (in n 2 1) lower bound
((..ID((FGN)) 2 new
UUs
log d
L
This shows the (((vv/)))) d)) rate holds for all n 2 1 (with possibly smaller Knew for very small n),, while the asymptotic constant .Ca is recovered as n + oo.
4v2CCK
Remark (Why path graphs?). The path graph Pm minimizes connectivity and mixing: each node has degree at most two, and lazy random-walt mixing is slow, so one passagg-passing step propagates information only along single chain. This bottlenecks information flow per layer, making depth the dominant factor. More connected graphs (e.g., expanders dense random graphs) mix faster, which can only help learning. Hence, demonstrating hardness on path graphs suffices to certify minimax lower bound for all admissible graphs standard practice in worst-case lower-bound arguments.
Remark 4 (Where topology enters the proof, and why path). Graph topology influences the proof in two places:
1. Packing construction. Let (v) denote the radius-1 neighborhood. We choose set S of m nodes and vary only their first-layer weights. To avoid interference, we require (Ni E }) to be pairwise disjoint. On a path Pm, this holds if the distance between consecutive nodes in S is at least 2, giving |S| ((m). On a graph with maximum degree A, disjointness rypically forces spacing 2 A+ reducing (S] by a factor z(A) S and thus shrinking the packing number by constants.
KL-divergence control. For Gaussian noise,
fall?,
1 -0,00 20
KL(P)IPb)
20
With disjoint neighborhoods, perturbution affects only oulputs inside Ni(v). On P [w] I 2, so the KL. scales like O([S]) for fixed perturbation size. On degree- graphs, [N((v)] < A. for the same perturbation size the KL is larger by O(A). To keep KL bounded, rescale the perturbation by 1/ I/VA, which weakens the separation by the same factor. Both effects alter constants in Fano's 's inequality, not the ne-dependence
Consequence. Because paths minimize degree (A = 2) and maximize the number of disjoint radius-I neighborhoods, they yield the tightest constants and the cleanest exposition. Moreover, any graph containing an induced path of length (t(m) admits the same lower-bound rate as Theorem (up universal constants) by restricting the construction to that path.
F STRUCTURED-GRANN GRAPH LOWER BOUND (PROOF OF THEOREM
Proof. Consider the node-level transductive setting of Eq. 3 on a fixed graph G = (V, F), where each labeled example corresponds to distinct node. Assume the following spectral-homophily condition on the subgraph induced by the n labeled (training) nodes:
K
S
log n
where C, is the normalized Laplacian and 0 is universal.
Information-theoretii tools. The argument uses the same information-thhoreee toolkit as the proof of Theorem [ In particular, packing sets and the Varshamov-Giin bound are recalled in Appendix C and the fixed-radius form of Fano's 's inequality is stated in Appendix D
18

---

Published as a conference paper at ICLR 2026
Mixing-time bound (used only for interpretation). Fix (0,1), say 2- (Appendix H) yields the standard bound
Lemma
log 10g(T/(ETmmin) (P(
2 (og(1/(ETmiu)) (2(
using ) (X,(,, for the lazy walk. Under (2(,.)) S K/ log n. this places the instance in slow-mixing regime (small spectral gap). We do not require an explicit (log n) upper bound on (é) in the packing argument below; the structural assumption is used only motivate that the effective number of statistically distinct blocks grows logarithmically.
Block count and anchor set.
Set
K [cblk log ni
for universal constant Gblk > 0. Choose a subset of K labeled nodes
A = .ik.. C.V.
(Only K < n is needed; the particular choice of A is immaterial for the lower bound since we work with subclass supported on A.)
Feature model and selector coordinate (no node-indexed parameters). To avoid any node- specific parameters,
single shared parameter vector and deterministic selector feature that is part of the input. For every node v E V, define the augmented feature vector
X, = Xz. Zo) Rd+1,
Z 1= E A},
X. (a),
with {Xe]vev independent across Thus, for non-anchor nodes (Z, = 0), the first d coordinates of X, are identically zero, while for anchor nodes (Z. 1) these coordinates are i.i.d. standard Gaussians. We observe labels
Yo (*(x,) + Eo
i.i.d. 1 E.
((0,0)
independent of the features. The selector Z, gates the function through the input, node-specific weights are introduced.
realizable shared-parameter subelass. Define the odd activation vb(2) := (<> 2(-2), where ((z) max(0, 2). Then (2) z, which lets compute L2 separations exactly under X, ~ (0, Ta) without any orthonormal-feature assumption. For each E {0, 1]d, define
fo(x)
0, v(t,)
JU Σ LKK
0 Kij
(16)
LK
where zy denotes the jth coordinate of the first d entries of x Rd+1 Because Fi.d X., we have fo,) whenever Z, and (X,,,, ou, (0, X.,) for is E A.
The map in Eq. (66 is realized by one-layer shared- shared-parameter GNN with self-loops and an identity aggregator (so each node uses its own features only), since vrxr) o(x,) of -my) can be
implemented with two ReLU units per coordinate. Hence fo E FGNN (see Appendix B
Step 1: Packing set (over global parameters only). Let θ C {0, 1)dd d be constant- code
with ||@||o = d/4 for all 0 E θ and pairwise Hamming distance (0, 0') > d/8 for all distinct
0, 0' E θ. By the Gilbert- Varshamov bound /Varshamov) 1957 Gilbert 1952). there exists such set with cardinality M == (0) satisfying
log M 2 cod
(17)
for universal constant 6o 0 (for d sufficiently large).
19

---

Published as a conference paper at ICLR 2026
Step 2: L2 separation. For any 0 0' in O using Eq. (16) and the fact that fo(X.) 0 for v & A.
Ilfo - for 12, == E
Σ (fo(X,) - for (X.))
LOEV
(0 0¹ xx.
E8
0U LR
o²v2 du (0,
0U LR
10 11
L
0 d
di
(18)
L2K
Step 3: KL divergence. Let Po denote the joint distribution of the observations (Y,, k regression function is fg. Conditioned on the features, the observations are independent Gaussians with means (X, ] and variance o², Hence, for any 0 0',
f== when the
1
KL(Po)lPP)) = E
(Jo(X So -o
20
Ł=1
1
E
Σ - (X,,))
20
1
1
Ilfo
for ll
S
llfo - for 11
20²
20²
1
0²1²
v2
du (0,0)
S
d KL
(19)
20
L
2L2K
where used dn (0,0') d.
Step 4: Fano's inequality and conclusion.
Applying Lemma (Appendix
D to the packing
{ffo Leee with separation Eq. (18) and KL bound Eq. 19 yields
dB
KT
max + log
inf sup E [1 020
folli,]]
2
2
log M
Using Eq. 17 and Eq. 19 for large enough so that K = [can log n. satisfies
CD
2v
KT KTmax
equivalently
K 2
4
T,
the parenthesis is bounded below by universal constant. Combining this with Eq.
18 gives
a212
02,² d
inf sup E [1f folli,] 2 c. L2K
d
f AE
logn'
a universal e > 0 (absorbing constants from Cblkk and co). Since (Sa)aee C FANN, this lower bound applies to R (FaNK), which proves Theorem
G INTERPRETING THE OPECTRAL-HOMOPHRR ASSUMPTION
Structural, not label-based. The assumption >2(C..) S x// log n concerns the spectrum of normalized Laplacian of the subgraph induced by the labeled nodes. It constrains expansion and mixing properties the graph and is independent labels or features. In particular, the condition can hold even if labels are adversarially assigned; form of label homophily is required.
Why makes learning harder. A small A2 C..) implies low conductance and slow random- walk mixing by Cheeger-type inequalities (Bandeira et al. 2013). In this regime, message passing repeatedly reuses the same information: after O(r) hops, neighborhoods overlap substantially. Our proof shows that ((logn) n) suffices reduce block dependence below fixed constant, so only (log blocks behave "nearly independently." This effective reduction in sample size yields the ((d/ logn) lower bound.
20

---

Published as a conference paper at ICLR 2026
When the condition fails. Graphs with strong cross-cluster connectivity (i.e., good expansion) typically have Ag bounded away from 0 (often (()).. Such graphs fall outside the assumption, and the guarantee reverts to the O /log d/n) rate of Theorem
Non-vacuity for large n. Although the inequality (2( S k/ log n may hold automatically for very small n. the condition becomes increasingly restrictive grows. The following lemma formalizes this:
Lemma (Non- Vacuity the Spectral-Homophit Condition). Let 9n be any graph sequence with A2(Cn) 2 Co 0 for all sufficiently large n (e.g., expanders, small-world networks, grids of fixed dimension). Then for any fixed K. > O, the structural condition
X2(Cn) S log
fails for all n > no == exp(</co). Thus the assumption of Theorem 2 is asymptotically non-vacuous and applies only to increasingly slow-mixing, bottlenecked graph topologies.
Proof. Since Aa(L.)) 2 for all No. the condition A2(Ln) S k/ log n implies S k/ log or equivalently log S 16/Co, i.e. n S exp(x/co). Thus the condition fails for all n >> nos proving the claim.
Examples.
Paths, cycles, or chain-of-cliques: (2(C) decays with graph size. For sufficiently large n, the condition λ2 S k./ log is satisfied, often by wide margin.
Expanders: (C) @()), the condition fails and the analysis falls back to Theorem
H MIXING TIME AND THE SPECTRAL GAP
We formally record the standard spectral bound on the mixing time of lazy random walk, and relate the eigenvalues of the lazy walk to the normalized Laplacian.
Lemma (Mixing time via spectral gap). Let G (V,E) a finite, connected, undirected graph. and let
P= + -
be the lazy yandom-walk transition matrix, where the adjacency matrix and D diag (deg(v)). The stationary distribution is
(vg
π <(v) = 2
V E V,
so that
1
Tiin 2
2
2
For every e E (0, 1),
log (
2 log V + log(1/E)
mix (c)
1 1- x2
1 1->a(P)
where Xo (P) is the second largest eigenvalue of P (the spectral gap is 1 (2(P) 0). (Levin & Peres 2017 Theorem 12.4, Eq. (12.10)). Moreover, if = 1 1-1/2 AD 1/2 AD11 denotes the normalized Laplacian, then
1 1-22(P) x2(
and therefore
2(2log VV + log(1/E)
Imix (6) <
(2(L)
In particular, if (2) S x/ logn with n = [V| fixed k. > 0, then tmix (E) = O(logg)) (up to constants depending and e).
21

---

Published as a conference paper at ICLR 2026
Proof. By reversibility of P, the stationary distribution is x()) (2g()))(((
Hence
degmin
min = min (())
E
2 E
[V
since | < -
Let (P) denote the second largest eigenvalue of P. Standard spectral bounds for lazy reversible chains (Levin & Peres 2017, Theorem 12.4) yield
log( (E(Tii)))))
mix (E) -
E (0, 1).
- A2(P)
Substituting the bound on Tiin gives
log
2 log _ 2 log IV..
Thus
2log V + log 1/Ee)
mix (E)
x
1 - A2(P)
To relate Laplacian and random-walk eigenvalues, let
5 D=
I==I-5
Then S and the random-walk matrix D- A are similar and share eigenvalues. If X2(() denotes the second-smallest eigenvalue of L, then
(2(S) - A2(C.
For the lazy walk P = + A), the corresponding second eigenvalue is
A2(P) = 2 + #2(S)) = (
so the spectral gap satisfies 1 A²(P) ( Substituting into the mixing bound yields
2(2 |V + log(L/))
(m) <
x²(
Finally, if x2( S K./ log n with n VV. then the above display gives Iini (e) ((lggn)))))) (up to constants depending on K and e).
OPERATOR-NORM CONTROL FOR ADIACENCY-MASKER ATTENTION
This section provides the operator-norm analysis that underpins the applicability Theorem adjacency-masker attention layers. For the complementary GAT-specific discussion, see Appendix
Conditions for applicability. Theorem extends to attention-based GNNs provided the following hold: (i) Adjacency masking: each head attends only to (i (or, more generally, r-hop neigh- borhood); (ii) Bounded layer operators: each layer is Lipschitz with uniformly bounded operator norm (e.g., via bounding attention scores by temperature/clippnng
constraining the attention matrix norm); (iii) Finite depth L. Under (i)-(iii), the proof unchanged up to constants depending on the product of layer norms and, for r-hop masking,
Fully global (unmasked) attention is non-local and therefore outside the locality premise of Theorem 2
Norm-control derivation. Consider single masked attention head with queries Q HWQ keys K HW k, values V HWv, and adjacency mask M E (0, -o) [V|VVV restricting attention to (i) (or an r-hop pattern). With temperature > 0 and row-wise softmax,
A = softmax (QQ + M)/T),
and the layer map is + AV (plus a 1 x 1 mixing which we absorb into the operator norm). Assume ||Wlla eq. |W l|a ck, |W ||2 I cv, and rows of Q, K are bounded in norm by B
22

---

Published as a conference paper at ICLR 2026
(this holds if |||]| is controlled inductively and layer norms are bounded). Then each masked row of (QK >/TT has entries bounded by B'COok /T, so the softmax is a-Lipschitz on each row with C, and yields row-stochastic A supported the mask.
Since is row-stochastic, ||Al| = 1. A general bound is
||Al|2 I |l A|
where ||]l the maximum column sum. Under adjacency masking on graphs bounded in-degree, or if attention scores are additionally degre-normalizzddclipeed so that column sums are uniformly bounded, one has ||A||] I Cdeg. for structural constant Cáeg (c.g., Caeg I A + 1 for max degree A), hence || Σ Cdey- Therefore
||AI|22 - ||A||2 IVVIl2 $ VCaeg [IV & VCdeg IW |H]| & VCdeg Cv ||
With residual/linear projections folded in, the per-layer Lipschitz constant is bounded by a product of operator norms (one per submodule), yielding uniform bound Lop < per layer. Therefore depth-L L masked-attention stack has overall Lipschitz constant 4. The proof of Theorem uses only: (a) adjacency locality from masking, and (b) bounded layer Lipschitz constants. Both hold under the above conditions, the same packing, KL control, and Fano steps go through with constants depending on Topp (and on for r-hop masks).
The
J ADJACENCY-MASKER GAT LAYERS UNDER THEOREM 2
This section explains why standard GAT layers fit within the assumptions of Theorem 2 For the accompanying operator-norm control argument, see Appendix [
Theorem assumes (A1) and thus excludes input-dependent mixing (attention). By contrast, Theo- rem 2 requires only adjacency-man masked 1-hop receptive fields and bounded operator norms. Standard GAT layers satisfy these conditions if attention is restricted to (i) and softmax weights are bounded (e.g., via temperature or clipping).
Formally, a single GAT layer with adjacency mask can be written as
((t)) = Φ (
Σ
a
(11))
h + BOO
JEN())
where E Ejeva oi
( (-) 1, a O. and ig 0 for j & (i()). Although the coefficients depend on features (violating (A1)), they are adjacency-masked and convex.
Assume (i) the attention logits are bounded (c.g.. softmax with temperature or clipping), so that (f) < Cat and the Jacobian the mapping (a is bounded: and (ii) the linear maps satisfy the same & budget as in (A2). Then the layer is Lipschitz with operator-nome bound || Can + [[[[]]] (with the dependence on the attention logits' temperature absorbed into C.n).
max, Ejeran ai
The proof of Theorem uses only: (a) adjacency locality (receptive field confined to the graph), (b) bounded layer Lipschitz constants, and (c) the graph mixing argument yielding K O (log n) effectively independent blocks under (²( & k/ log n. Conditions (a)-(b) hold for adjacency- masked GAT with bounded logits, hence the same packing, KL control, and Fano steps go through with the constants absorbed into I' Therefore, the (2dd/ log n) lower bound applies to standard GAT under these mild norm constraints. In contrast, Theorem explicitly relies on input-independent aggregation and does not cover attention.
K PRACTICAL GUIDANCE FOR DATA-SCARCE GRAPHS
The aaruetur-awware aware lower bound (Theorem 2 implies that when only Öllggn) n) training nodes are effectively independent, naive data scaling is statistically inefficient. Constants in the bound can often be improved in practice, though the asymptotic rate Q(d/ logn) remains unchanged. The following interventions help improve constants:
23

---

Published as a conference paper at ICLR 2026
Break neighborhood homogeneity slow mixing. Add node individualization positional encodings (e.g., random/leamed IDs, Laplacian/RW features) and consider sarrophily-wwann layers; these reduce overlap of peassage-passing neighborhoods.
Reduce effective dimension before fine-tuning, Use transfer or self- pretraining on large auxiliary graphs, then freeze most layers select features shrink the effective entering the bound.
Diversify supervision. Active/coreset label selection that spreads labels across loosely con- nected regions (far in graph distance across communities) increases independence among samples.
Regularize against slow mixing over-smoothing. Use residual/JK connections, PPR/teleport propagation, DropEdge/edge sparsification, and limit depth; these shorten the mixing horizon, raising the usable information per label.
Takeaway. These choices increase the informative signal per labeled node and improve constants a²u² d_ but the qualitative log n. denominator remains the limiting factor under the spec- in T log
tral tral-hompphily condition.
L ARCHITECTURAL DRIVERS OF HETEROGENEOUS SCALING
Why different models show different scaling on the same dataset. Even on a fixed graph, architectures induce different effective sample efficiencies due to variation in receptive-field growth and information reuse. We identify two main drivers:
Smoothing and receptive-field growth. GCN's fixed, normalized adjacency (a graph- dependent but input-independent filter) resembles classical spectral filter. When the task's s signal is spectrally aligned, this can yield faster apparent decay (closer to 1/vn). By contrast, GAT and GraphSAGE adapt mixing weights and thereby emphasize homophilous neighbor- hoods; this adaptation increases overlap among message-passing neighborhoods and reduces the effective number of independent samples, exposing the slower 1/ log decay predicted by Theorem
Bias-variance tradeoffs and noise floors. Models with stronger inductive bias (e.g., GCN) can reach a bias-dominated error floor early, which makes the observed asymptotic slope appear steeper. More flexible models (GAT/GraphSAGE) reduce bias but incur higher variance, which dissipates slowly because samples are not effectively independent under overlapping neighborhoods.
This perspective helps explain the heterogeneous scaling observed in Table (e.g., GCN on Reddit favoring 1/ Vn. versus GAT and GraphSAGE favoring 1/ logn).
M EXPERIMENTAL DETAILS AND SETTINGS
This appendix details all elements of the experimental setup, training configuration, evaluation protocols, model fitting, and resource usage ensure reproducibility of results.
ENVIRONMENT AND COMPUTE RESOURCES
All experiments were conducted using PyTorch and PyTorch Geometric (PyG). We used GPU-enabled machine equipped with an NVIDIA Tesla V100 (32GB VRAM) and 64GB system RAM.
DATASET LICENSES AND CITATIONS
The following publicly available graph datasets were used in this study. All OGB datasets were accessed through the ogb nodeppopppee module, and all other datasets were obtained through standard public repositories. For reproducibility, we report the license information and cite the original sources.
24

---

Published as a conference paper at ICLR 2026
ogbn arxiv (Hu et al. 2021): A directed citation network with [V| 169,343 nodes and |E| 1,166,243 edges, where each node represents an ArXiv paper and edges represent citation links. The dataset is licensed under the MIT License and available from the Open Graph Benchmark (OGB): wtt.tttss///ttttt..ee
stanford edu/ docs/ hwwpss/ooddpoopoo
arxiv
agbn_products. 50k (Hu al. 2021): A 50,000-node sampled subgraph extracted from ogbn- products, originally a large-scale co-purchasing network with V 2,449,029 ,29 nodes and | 61,859,140 140 edges. The full dataset released under the MIT License and available via OGB: https:/ /wgb. an ford. edu/ www.://odopooooooooooooooooooooo
Our sampling
procedure detailed Subsection M
Reddit 50k (Hamilton et al.) 2017b): A 50,000-node sampled subgraph derived from the full Reddit interaction graph used in the GraphSAGE benchmark. The original Reddit dataset is available via Google Drive: https: ve. goog com open? id= 9SphV1 (eess1r87Hr5aa2nxe.. Subsection M
Beck
Sampling details for constructing Reddit_ appear in
WorstCase _oaatee_Btteeeck____ 20k (synthetic): A controlled synthetic graph constructed to approx- imate a worst-case bottleneck structure for theoretical evaluation. It contains |V| 20,000 nodes and | = 8,370 edges with K = 40 communities. As a fully synthetic dataset generated by our code, carries no external licensing restrictions.
MODELS AND ARCHITECTURE
We evaluated the following Graph Neural Network (GNN) architectures:
GCN: 2-layer Graph Convolutional Network using GCNConV, with 16 hidden units.
GAT: 2-layer Graph Attention Network with heads first layer, and a single head in the second.
GraphSAGE: 2-layer GraphSAGE model using SAGEConv, with 16 hidden units.
All models use ReLU activation after the first layer.
TasKS AND Loss FUNCTIONS
We tested two standard graph learning tasks:
Node Classification:
Cross-entropy loss on node labels.
Graph Regression: Molecular property prediction using mean squared error (MSE) on the target scalar field.
SUBSAMPLING PROCEDURE
Due to computational constraints associated with training GNNs at large grid of training sizes we construct K-node induced subgraphs from two large-scale datasets: ogbn-p roducts and Reddi t.2. Our subsampling method follows consistent pipeline across both datasets, designed to preserve connectivity, degree structure, and label distribution as faithfully as possible.
Step 1: Load full dataset. We load the complete graph (ogbn products or Reddit2) using the PygNodeP ropP redDataset or Reddit 2 interfaces, respectively. Nodes without incident edges excluded from candidate sampling to avoid trivial isolated components.
Step 2: Random candidate subsample (200 nodes). Using a fixed random seed, we draw a random subset of C' 200,000 non-isolated nodes from the full dataset. This produces large but manageable candidate subgraph while increasing the likelihood that the largest connected component (L.CC) is substantially larger than 50 K nodes.
25

---

Published as a conference paper at ICLR 2026
Step 3: Induced subgraph 200 K candidates. We construct the induced subgraph on the candidate set and compute its connected components via scipy. , sparse eagraph. connected components. This step ensures that the re- sulting 50 K-node dataset originates from a structurally coherent region the full graph.
Step 4: Extract the largest connected component (LCC). We identify the LCC of the candidate subgraph, whose size consistently exceeds 50 across datasets. Restricting to the LCC avoids pathological fragmentation and ensures meaningful GNN message passing.
Step Randomly select exactly K nodes from LCC. From the LCC, we sample exactly N = 50,000 nodes uniformly at random (with new fixed seed for reproducibility). The resulting set sorted and forms the node set the final subgraph.
Step 6: Build the final induced 50 K-node graph. We construct the induced subgraph on the selected 50 K nodes. All edges (u, v) are retained and only if both endpoints lie in the selected set. Node features and labels are inherited directly from the original dataset.
Step Preserve OGB-style dataset splits. For both datasets, we map the original train- aag/aiaiiaiioo/eettnng splits to the 50 K subgraph by checking whether each selected node belonged the original split. Any node whose original index appeared the official training, validation, or test sets is assigned to the corresponding split in the subgraph, ensuring compatibility with OGB evaluation protocol.
Reproducibility. All random operations use fixed seeds, and we save the mapping from subgraph indices to original node IDs (final dattiaalnnddd____eeeeeeee___eee_ wwdes_oriigggo mw..orrirnn...... This makes the entire subsampling pipeline deterministic and reproducible.
TrAINING PROTOCOL
Subset Sampling: For each experiment, subset of n samples randomly selected. For node tasks, subgraphs were constructed using torchhgeemettrbb ric. ut iiiis... utils..ubgraph.
Data Splits: A fixed 80%/20% train/test split was used.
Optimizer: Adam with learning rate 0.01, weight decay 10-4
Epochs: 200.
Batch Size: 32 for all tasks.
Evaluation Metries:
Misclasiification rate for classification,
MSE for regression,
STATISTICAL SIGNIFICANCE AND ERROR REPORTING
Each experiment (fixed dataset, model, and n) was repeated 5 times with different random seeds. The reported error metric includes the sample mean and standard deviation across the runs. Standard deviation is used for error bars and in weighted fitting procedures. These represent variation due to random sampling and initialization. All error bars shown in figures correspond to +1 standard deviation.
26

---

The best fitting model for each dataset and architecture was determined based on the max- imum R². Fitted parameters and metrics were summarized LaTee-formateed table tex), and model-specific figures were saved as Published as a conference paper at ICLR 2026
CURVE FITTING AND LEARNING TREND ANALYSIS
To analyze sample complexity trends, we fit the test error curves to the following models:
Model 1: C1 vn
8
Model 2:
02 +
Model 3:
03 log
Model 4: C4
nz
Fits were performed using weighted least squares with weights 1/0f. where the standard deviation of the ith data point. The power-law model was fitted using scipy aptimize.cuure_ffe with bounded parameters and robust initial guess. For each model, we computed:
Weighted Residual Sum of Squares (RSS)
Weighted Mean Squared Error (MSE)
Weighted R22 value
(Einal_compan coommarrioo___ee serisso__tteee <dataset>
< <model> sroode>_fitss.nng
VISUALIZATION AND REPRODUCIBILLIT ASSETS
All figures include error bars, and each plot overlays all fitted models for comparison. All code, including data loading, model training, evaluation, fitting, table generation, and visualization, is structured and commented for reproducibility.
CODE AND REPRODUCIIIILITY
To support verification and reproducibility, we provide the full source code as supplementary material. This includes implementations for data loading, model training, evaluation, error analysis, and curve fitting, as well as scripts to reproduce all experimental results, generate LaTeX tables, and visualize learning curves in line with reproducibility guidelines.
Every step necessary to replicate our results datasets, architectures, parameters, training and evaluation setup, fitting strategy, and visualizations-ia fully disclosed and executable by third parties with access to the same datasets and a standard GPU-enabled Python environment.
Summary:
N STRUCTURAL STATISTICS
To connect the empirical analysis with our theoretical results, we compute two structural measures for each dataset.
Homophily. It is defined as
h(G)
Σ 1f = yeh.
E
[u,D)EF
where E is the edge set and yıu denotes the ground-truth label of node
Spectral quantity (normalized Laplacian). We compute Az AZ(C,), the second-smallest eigenvalue of the normalized Laplacian
L. I 1 1/22/ A, D11122 1/2
(20)
27

---

Published as a conference paper at ICLR 2026
where An and Dn the adjacency and degree matrices of the induced subgraph the labeled nodes.
Relation to random- walk eigenvalues (for reproducibility). If one instead computes the second cigenvalue (P,) of the aundom-wlll matrix Pn == Dz A... then the quantities satisfy
)2(L.) = 1 - (P.(
(21)
We report (L,) throughout.
Empirical λ summary over the training-size grid. To summarize the condition A2(Cn) S k/ log over the experimental grid of labeled sizes N. use the dataset-level certificate
Kg == max (2(L.) log n,
(22)
nEN
so that (2( I Ko/ logn holds for all n E N.
O SYNTHETIC WORST-CASE CONSTRUCTION AND NUMERICAL VALIDATION OF THEOREM I
This appendix provides detailed description the synthetic experiment used numerically validate the minimax lower bound established in Theorem I The experiment instantiates and evaluates the minimax error rate induced by the worst-case function class constructed in the proof of the theorem. All simulation code and data are fully reproducible and included in the supplementary material.
O.1 WORST-CASE FAMILY FROM THE PACKING CONSTRUCTION
identifies a worst-case subclass ReLU GNNs defined over disjoint neighborhoods of path graph. The construction yields family of functions
The proof Theorem J
F fs(x)= = -a MI,) Sc
[4, Sc |S| =
JES
implemented by ReLU GNNs satisfying the budget constraint E/iO (11W(00)) + (1((111) S v. This family has:
controlled complexity,
pairwise separation at scale 2e in || [lxx(Px)
exponentially large cardinality:
F 2 2² log d,
log
controlled Gaussian KL divergence for the regression model.
Applying the fixed-radius form of Fano's inequality yields the minimax lower bound
JF
log d
R2 (FGNN)
2 Keew
L
Thus, the shape of the worst-case risk is fully characterized by
log d n
Errwo(n) (n) =
This functional form is the central object of study in the numerical experiment.
28

---

Published as a conference paper at ICLR 2026
O.2 RATIONALE FOR SYNTHETIC INSTANTIATION OF THE MINIMAX CURVE
Since the minimax curve analytically explicit, numerical validation can be performed by directly simulating errors at scale Ctrue V log introducing controlled stochastic perturbations, and examining how the resulting empirical enror behaves across wide range of sample sizes.
This approach offers two advantages:
Faithfulness to the theory: replicates the risk achieved by the worst-case subclass without introducing confounding effects from training dynamics, optimization choices, or architectural hyperparameters.
2. Scalability in n: Sample sizes can be extended far beyond the regime accessible in real datasets (up to 10" in our experiment), allowing clear observation of asymptotic scaling behavior.
This makes synthetic instantiation clean and principled mechanism for validating the minimax rate.
O.3 SYNTHETIC ERROR GENERATION
For prescribed dimensionality d 100, the theoretical worst-case error curve is Errwe(n)
Cirue Iog with Ctrue 1.
To emulate finite-sample variability, we introduce multiplicative noise: (n) = (nrwe(n) (1 + E,), & A o.a).
with relative noise level rrel = 0.15. Values are clipped below at 10 12 for numerical stability.
For each sample size n, draw Nocod 800 independent realizations and compute:
empirical mean (in)).
empirical standard deviation ā (n)),
95% confidence intervals.
Sample sizes range from n 200 to = 105, logarithmically spaced. This covers small-sample, mid-range, and asymptotic regimes.
0.4 IMPLEMENTATION SUMMARY
The synthetic experiment is implemented single reproducible Python script (Listing 1), which:
generates the minimax-rate errors for all ni,
2. computes empirical means, variances, and confidence intervals,
3. fits all four baseline models.
4. outputs raw data, fitted curves, and diagnostic ratios to CSV,
5. produces ioolicatiio-qualiiy plots (error curves and ratio diagnostics).
The implementation uses standard scientific Python libraries: NumPy, Pandas, SciPy, and Matplotlib.
O.5 INTERPRETATION
Simulating the analytically exact minimax rate provides direct numerical realization of the worst- case behavior derived in Theorem [ Because the constructed worst-case subclass is fully explicit, the synthetic instantiation precisely matches the theoretical risk curve achieved by GNNs graph families (e.g., path graphs) that minimize information propagation across layers.
This experiment therefore offers a clean numerical confirmation of the asymptotic /log d)/n scaling and distinguishes it from alternative decay profiles.
29

---

Published as a conference paper at ICLR 2026
P SYNTHETIC STRUCTURED BOTTLENECK DATASET (THM 2
This appendix describes the construction of the synthetic structured graph dataset WorstCase_Bar Bettt_Bttttte Bo Beeeec____2__ which we use to empirically probe the node-level mini- max lower bound of Theorem 2 The goal of this construction is instantiate large, homophilic graph with narrow inter-community bottlenecks and an estimated normalized Laplacian second eigenvalue X2 that scales on the order of 1/ log n, that the spectral-homophil condition (C) I K/ log holds for a moderate constant K.
P.1
GRAPH CONSTRUCTION
We construct an undirected graph with 20,000 nodes and communities of approximately equal size:
1. Community assignment. We partition the N nodes into K contiguous communities by assigning
community(4)
for u E {k. [N/K] (A + 1) [N/K] -1},
for k = O.... K - 1, and assigning any remaining nodes to the last community. This yields an array commun itt E (o...., 1)
2. SBM-like bottleneck edges. We generate edges in SBM-like manner, but with computationally efficient candidate sampling step. For each node u E 10...,,N-11.
(a) Draw a set of 200 candidate neighbors v Unif((O... .,, N-1)) without replacement, excluding = u.
(b) For each candidate let C. = community(w) and c, community(t).
If Cu C₂ (same community). add undirected edge (u, with probability
Pin 0.03.
Cu # cu (different communities), we add an undirected edge (u, v) with proba- bility Pout 0.0003.
Each accepted edge is inserted in both directions in the edge_ ndex tensor, so the resulting graph is treated as undirected in all downstream computations.
This construction yields stochastic block model with K 40 communities and a strong bottleneck structure, since Pout < Pin- Most edges lie within communities, while only a sparse set of edges cross between communities, creating narrow cuts and slow mixing across the graph.
P.2 NODE FEATURES AND TEACHER MODEL
Each node is equipped with d = 64-dimensional features and labels generated by a simple teacher model that combines global linear projection of features with a community-dependde bias:
1. Features. We draw node features
XE Nxd
Xu,: ~ NO
independently for all nodes u.
2. Teacher logits. We sample a global weight vector Wglobal NO, Ia) and generate real-valued logit for each node:
Zu (X,,;, Wglobal) + 0.5 community(u) Ea: Eu NN0, dolse))
with Tuoise = 0.5 our implementation.
3. Quantile-based labels. We convert the real-values logits {2u) into C 4 discrete classes via quantile binning. Let
4o S 91 S ... S 9c be empirical quantiles of { D at levels 0, d.......
1. We then assign
yn
if 2, (ges 1et1), e E (0, 1,
30

---

Published as a conference paper at ICLR 2026
The resulting labels {0, 1. have approximately balanced class frequencies and are strongly aligned with community structure due to the explicit 0.5 community (u) term in the teacher.
The combination SBM-like edges and community-ave awwre label generation yields a highly ho- mophilic structured graph, designed to instantiate the regime where graph structure significantly aids prediction.
P.3 SPECTRAL AND HOMOPIILLY DIAGNOSTICS
To connect this construction to the structured-grant assumption in Theorem 2 we compute two diagnosties:
Spectral gap of the normalized Laplacian, Given the edge ireeinndde build the symmetric adjacency matrix A (making the graph undirected), degree matrix D, and normalized adjacency
edge_ index representation, we
$ = D-1/2AD
We then approximate the top-2 eigenvalues of S by a power-iteration- based subspace method and denote them by μ1 2 f2. The second eigenvalue of the normalized Laplacian is then estimated as
A2 == 1 12
We record λ2 and the product Khat == A2 log N in metadata file, providing empirical certificate that (C) scales as O(1/ N) with moderate constant.
Label homophily. We define the homophily score as the fraction of edges connecting nodes with the same class label:
Homophily Ply yo ( E
Σ (u,j)E
1 vol.
This quantity is also recorded in the metadata. In practice, the combination of community- based labels and Pm >> Pout yields high homophily score, consistent with the structured, homophilic regime of Theorem 2
Together, these diagnostics provide empirical evidence that the constructed graphs satisfy a spectral- homophily condition of the form (2( k/ log N for moderate constant K, matching the assumptions of the theorem.
P.4 TRAINVALLIATIONTESS SPLIT AND SAMPLE-SIZE GRID
We adopt fixed random split of nodes into training, validation, and test sets, and then vary the number of labeled training nodes nurin within the training set to probe the sample-size dependence of test eтrоr.
Fixed 60/20/20 split. We draw random permutation of the N node indices and define: train full = first [0.6N] nodes, val-full = next [0.2N] nodes, test full = remaining nodes.
These three sets remain fixed for all experiments on this dataset.
2. Log-spaced training sizes. Let T |train full denote the total number of nodes in the training pool. We define a grid training sizes Rarin by taking 60 log-spaced points between 49 and min(11,000, 7) and rounding to integers:
Tetrain {
)|
exp log 49
(log T'max log 49)
O.
59
where Ramax = min T') and duplicates after rounding are removed. For each value of Purain on this grid, will train and evaluate GNN models as described below.
31

---

Published as a conference paper at ICLR 2026
P.5 EARLY STOPPING AND EVALUATION
For each configuration (model, Raain), we:
1. Sample subset of training nodes Suain C train full of size Ruain uniformly at random without replacement.
2. Initialize the model and train for up to 500 epochs with early stopping: we track the validation loss val full and retain the model parameters with the best validation performance, stopping if there is no improvement for 40 consecutive epochs.
3. After training, we evaluate the selected checkpoint on the fixed test set test test_fulll full and record:
the test cross-entropy loss, and
the test accuracy.
We repeat this procedure for random seeds for each pair (model, Reain), varying both model initialization and the subsampled training set Stain All raw runs are saved to CSV files containing per-seed test loss and accuracy for each Rarai and each architecture.
P.6 AGGREGATION, CURVE FITS, AND RATIO DIAGNOSTICS
For each model and dataset, we aggregate the raw runs by Ahrain to obtain:
mean test [oss[[]ss(n))) and std. test loss(n),
mean test_essseeee (est_acc(n),
normal-approximation 95% confidence interval for the mean loss via
std [e___est__e Lest____ssssss (oss(_)
Cl(n) mean mean_test_ (oss(]) (n) + 1.96
#seeds
then fit several candidate asymptotic shapes to the mean test loss as a function of n, as detailed in M using non-linear least squares, and compute standard goodness-of-fit metrics (RSS, MSE, It²) along with a log-log slope estimate from regressing log Err(n) on log n.
Finally, to compare directly the theoretical scaling suggested by Theorem diagnostics by dividing the empirical mean test loss by the relevant shape functions: Ratio, (alioo(n) = Err(n)/ / Vlog d/n (Theorem form) and (atio2(n) = Err(n) / (d/ log (Theorem 2 form). Here Err(n) represents mean_lest__re (essssssssssl))).. and d the input feature dimension. We track how these ratios behave as functions of log and estimate their slopes via linear regression. Along with the raw tables and curve-fit plots, these diagnostics are saved for all three architectures and used in the main text to interpret how closely the empirical performance on WorstCass BBttttttttttte Bottlened leneck_2000 aligns with the structured-gre graph minimax lower bound of Theorem
form ratio
Q SUPPLEMENTARY CURVE-FIT ANALYSIS AND RAW RESULTS
This appendix contains: (1) full curve-fit visualizations for all datasets and architectures, and (2) complete raw error tables with means and standard deviations across all training sizes and random seeds. These results provided in response reviewer requests for full transparency and reproducibility.
Q.1 CURVE-FIT PLOTS
Curve fitting is used only secondary diagnostic tool, complementing the primary aasio-based scaling analysis in the main text. Curve-fit plots for ogbn_arxee and seddit__50 and all three architectures (GAT, GCN, GraphSAGE) are shown below.
In Table 2 different architectures often show different slopes on the same dataset, a phenomenon likely influenced by smoothing, overlap, and bias- tradeoffs (Appendix L.)
32

---

Published as a conference paper at ICLR 2026
23
Figure 6: Test enror vs. sample size 7t on ogbn_ arxiv (left: GAT, middle: GCN, right: GraphSAGE).
Figure 7: Test error vs. sample size on Reddit__500 (left: GAT, middle: GCN, right: GraphSAGE).
Q.2 RAW ERROR TABLES FOR REPRODUCIBILITY
To ensure full reproducibility, we provide raw test metrics (mean = std over 20 seeds) for every dataset, every architecture, and every training size Thman- These tables enable independent verification of both the curve-fit results and the ratio-based scaling diagnostics reported in the main paper.
Table 3: Test loss and accuracy (mean + std over 20 seeds) for ogbn arxiv.
GAT
GCN
GraphSAGE
Parain
Test Loss
Test Ace
Test Loss
Test Acc
Test Loss
Test Acc
200
2.417
0.068 0.401 + 0.017
2.585 + 0.041 0.381 + 0.006
2.951 0.067 0.339 + 0.005
216
2.317 0.084
0.390 0.021
2.405 + 0.028
0.395 + 0.005
2.595
0.037 0.382 + 0.008
233
2.271 + 0.061
0.391
0.019
2.454 + 0.047
0.372 + 0.012
2,898 +
0.270 + 0.010
252
2.233 + 0.047
0.403
2.386 + 0.032
0.382 + 0.005
2.652
0.359 1 0.007
272
2.346 0.053
0.366
0.017
2.506 0.047 0.339 1 0.009
2.721 0.036 0.321 i 0.011
294
2.110
0.044
0.427
2.239 0.039 0.401 1 0.009
2.458
0.036 0.365 1 0.007
318
2.136
0.005
0.422
2.319 + 0.034
0.391 + 0.008
2.519 +.033 0.359 + 0.006
343
1.975 = 0.034
0,466
0.011
2,041 + 0.023
0.449
+ 0.005
2.232 + 0:021
0,411 0:005
371
2.040
0.042
0.425
0.021
2.113+0.00
0.406
0.005
2.271 0.029
0.395 + 0.008
401
2.008
0.037
0.458
0.014
2,072 +: 0.020
0.442
-1 0.006
2.202 1 0.029
0.422 1 0.008
433
2.081
0.054
0.433 +: 0.022
2.179 + 0.022
0.414
0.005
2.343 0.029
0.388 + 0.005
468
2.083 + 0.036
0,419 + 0.012
2.194 + 0.032
0.404
1: 0.006
2,312 4: 0.026
0.375 1 0.006
506
2.064 = 0.053
0,433
0.022
2.166 + 0.026
0.420
+ 0.006
2.238 +: 0.028
0,408 + 0.010
547
1.988
0.034
0.45
2,059
0.024 0.430
0.005
2.080 0.018
4.006
591
2,020 0.047
0.437
0.023
2.089
0.023 0.429
1 0.006
2.208
0.39 0.025
639
2.071
0.031
0.433
+ 0.015
2.138 + 0.018 0.429
+ 0.004
2.209 0.023
0.422+0.000
691
2.023 + 0.033
0,453
0.013
2.070 + 0.019
0.440 0.005
2.114 0.023
0.433
+ 0.006
747
1.940 0.031
0.471
0.011
2.022 0.444 0.022
0.005
2.072 + 0.017
0.445 + 0.006
807
1.957
0.031
0.465
0.009
2,048 0.021 0.439
1 0.005
2.116 0.021
0.435 0.005
871
1.944
0.025
0.472
0.009
2.007 1 0.018 0.455 1 0.005
2.010 1. 0.016
0.462 1 0.005
939
1.909 1 0.027
0,484
0.010
1.992 1 0.020
0.454 0.005
2.012 0.018
0.461 1 0.005
1013
1.908 - 0.026
0.000
1,991 + 0.022
2.044 0.018 0.457 + 0.005
1093
1.951
0.029
0.472
2,030
0.021
0.448
1.488
0.005
2.074
0.450 0.006
1179
1.892 0.023
00010
1.963
0.019 0.465
1.986
0.470 0.005
1272
1.888
0.025
0.489
1.964
+ 0.020
0.463
+ 0.005
2.005
0.019 0.467 1 0.005
1372
1.885 + 0.026
0.490
1.963 + 0.019 0.465
0.65++0000
1.993
4: 0.017
0.472 + 0.005
1480
1.884 0.025
0.009
1.951 + 0.018 0.469
+
1.989
+ 0.016 0.475 4 0.005
1597
1.876 0.024
0.495
1.941 + 0.017
0.470 0.005
1.981 + 0.015 0.477 + 0.005
Continued next page
33

---

Published as a conference paper at ICLR 2026
GAT
GCN
GraphSAGE
Test Loss
Test Acc
Test Loss
Test Acc
Test Loss
Test Acc
1723
1.881 0,024
0.494
0.009
1.946 1 0.018 0,470 0.005
1.974 0.015 0.478 1 0.005
1859
1.879 0.024
0.494 1 0.009
1.940 1 0.017
0.471 + 0.005
1.922 1 0.015
0.479 1 0.005
2006
1.872 + 0.021
0,498 1 0.009
1.925 1 0.016
0.475 + 0.005
1.953 0.013
0,483 1 0.004
2165
1.871 0.022
0.498 0.008
1,928 0.016
0,475 = 0.005
1.963 # 0,482 + 0.005
2338
1.873 00.02
0.498
0.008
1.930 0.011 0.475 + 0.005
1.959 0.013 0.483 : 0.004
2525
1.872 = -0.021
0.499
0.008
1.929 0.016
0.476
1.961 0.014 0.483 : 0.004
2729
1.869 + 0.021
0,499
+ 0.008
1.923 0.016
0.477 0.005
1.949 + 0.485 + 0.004
2950
1.868 0.020
0.500
0.008
1.921 0.478 0.015
0.004
1.947 0.014 0,486 + 0.005
3189
1.868 0.020
0.500
0.008
1.920 0.015 0.478 + 0.004
1.946 + 0.013 0.486 + 0.004
3448
1.865 0.019
0.501 0.008
1.917 0.015 0.479 1 0.004
1,900 0.013 0.487
0.004
3729
1.866 - 0.019
0.501
0.008
1.918 0.015 0.479 1 0.004
1.938 0.013 0.487 1 0.004
4033
1.865 + 0.019
0.501 +: 0.007
1,915 0.014 0,480 + 0.004
1.936 1 0.013
0,487 1 0.004
4363
1,863 0.018
0.502
0.007
1.913
0.480
+ 0.004
1.933 0.013 0.488 + 0.004
4722
1.862 0.018
0.502
0.007
1.912 0.014
0.481
+ 0.004
1.933 0.012
0.488 + 0.004
5111
1.861 0.018
0.503
0.007
=0011
0.481
0.004
1.930 + 0.012
0.488 + 0.004
5533
1.860 0.018 0.503
- 0.007
1.909
0.013 0.482 1 0.004
1.928 1 0.012
0.489 1 0.004
5989
1.859 0.018 0.503
+: 0.007
1,909 0.013 0,482 1 0.004
1.928 +: 0.012
0,489
1 0.004
6483
1.859
0.018
0.503
1.908
0.013 0.482 1 0.004
1.926 0.012 0.489
1 0.004
7017
1.859
0.018
0.503
- 0.007
1.907 + 0.013 0.482 1: 0.004
1.925 + 0.012 0.490 + 0.004
7596
1.858 = 0.017
0,504
0.007
1,905 + 0.013 0.483 + 0.003
1.924 + 0.490
0.004
8223
1.858 0.017
0.504
+ 0.007
1,904 + 0.013 0,483 + 0.004
1.923 0.011
0,490 : 0.003
8902
L,858 0.017
0.504
: 0.007
1,903 0.012 0.483 + 0.003
1.921 0.011 0,490 0.003
9639
1.857
0.017
0.504
0.007
1.903 0.012 0.483 + 0.003
1.920 +
0.490 01.033
10439
1.857 0.017
0.504
+ 0.007
1.902 + 0.012 0.483 + 0.003
1.919 +
0.491 + 0.003
1 1111
1.857 + 0.017
0.504
+ 0.007
1.901 0.012 0.484 + 0.003
1.918 0.011
0.491 + 0.003
12261
1.857 0.016
0.505
1: 0.006
1,901 1 0.012 0,484 1 0.003
1.918 0.011
0,491 1 0.003
132%6
1.856 0.016
0.505
1 0.006
1.900 1 0.012
0.484 T 0.003
1.917 0.010 0.491 1 0.003
14424
1.856 0.016
0.505
0.006
1.900 1 0.011
0.484 1. 0.003
19916
0.491 0.003
15653
1.856 = 0.016
0.505
0.006
1.899 + 0.011
0.484 0.003
0.010
0.491 - 0.003
16992
1.856 = 0.016
0.505
0.066
1.899 0.011
0.485
+ 0.003
0.016
0,491 + 0.003
18450
1.856 0.016
0.505
0.006
1.899 0.011
0.485 0.003
1.916
0.492 0.002
20038
1.855 0.016
0.505
0.006
1.899 + 0.011
0.485 + 0.003
0.110
0.492 1 0.003
21766
1.855 0.016
0.505
+: 0.006
1.898 + 0.011
0.485 +: 0.003
0.009
0.492 + 0.002
23642
1.855 0.016
0.506
+ 0.006
1.898 + 0.011
0.485 + 0.003
0.009
0.002 0.002
25778
1.855
0.015
0.506
0.066
1.897 + 0.011
0.485 + 0.003
0.009
0,492 0.002
28187
1.855 0.015
0.506
0.006
1.897 + 0.011
0.485 + 0.003
0.009
4.090
30883
1.855 0.015
0.506
0.006
1.897 + 0.011
0.485 1 0.003
0.009
0.492
0.002
33883
1.855 0.015
0.506
+ 0.006
1.897 + 0.011
0.485 + 0.003
0.009
0.492 + 0.002
0.002
37207
1.854 + 0.015
0.506
0.006
1.897 + 0.011
0.485
+ 0.003
0.492 0.009
0.002
40878
1.854 = 0.015
0.506
0.006
1.896 0.011
0.485
+
1.913
0.492 0.009
0.002
44922
1.854 0.015
0.506
1.896 0.011
0.485
0.003
0.492 0.009
0.002
49370
1.854 0.015
0.506
0.006
1.896 1 0.011
0.486
1 0.003
0.493 0.002 0.009
54251
1.854 1 0.015
0.506
1. 0.006
1.896
1 0.011 0.486 1 0.003
0.493 1 0.002 0.009
1.912
59599
1.854 0.015
0.506
0.006
1.896 0.011 0,486
+ 0.003
0,493 = 0.002
65453
1.854 0.014
0.506
0.006
1.896 0.010 0.486 0.003
1.912
0.493 : 0.002
71855
1.854 0.014
0.506
1.896 0.010
0.486
0.493 0.009
0.002
78850
1.854 0.014
0.506
+ 0.006
1.896
+ 0.010
+
1.912
0.493 + 0.002
86487
1.854 + 0.014
0.506
+ 0.006
1.896
+ 0.010
0.486 0.003
0.493 + 0.002 0.009
94721
1.854 0.014
0.506
0.006
1.896 0.010
+
1.912
0.493 + 0.002
103724
1.854 0.014
0.506
0.006
1.895 0.010
0.487
+487710000 0.003
0.493 + 0.002 0.009
113280
1.854 = 0.014
0.507
1.895
0.010
0.487
4.0003
1.911 0.009
0.494 1 0.002
123489
1.854 - 0.014
0.507
0.006
1.895
0.010
0.487
1.911 0:000
0.494 1
134466
1.854 - 0.014
0.507
0.006
1.895
0.010
0.003
1.911 0.009
0.494 0.002
146335
1.853 0.014
0.507
0.006
1.895 0.010
0.407
1.911 0.009
0.494 0.002
159226
1.853
0.014
0.507
0.06
1.895
0.010
0.000
1.911 + 0.009
0.494 0.002
169343
1.853 0.014
0.507
0.006
1.895
1 0.010
0.487 4
1.911 0.009
0.494 1 0.002
34

---

Published as a conference paper at ICLR 2026
Table 4: Test loss and accuracy (mean + std over 20 seeds) for
ogbn_ htcps_produut____00
GAT
GCN
GraphSAGE
Auzin
Test Loss
Test Acc
Test Loss
Test Acc
Test Loss
Test Acc
49
4.540 + 0.22 0.278 + 0.02
5.511 + 0.12 0.271 + 0.01
6,895 + 0.16
0.215 = 0.01
53
4.437 + 0.20
0.322=0.00
4.591 + 0.09
0.374=0000
5.486 + 0.11
0.317 = 0,01
56
4.196
0.333+00.0
5.145 + 0.09
0.365+0000
5.957 +
0.316 = 0.00
59
0.01 +.690:0..9
5.291 +
0.357+000
0.283 = 0.01
63
4.51440..6
0.353
0.29
0.369
6,258 0.10
0.319 = 0.01
67
4.151 0.30 0.369 1.01
5.125
0.372
5.687 1
0.336 - 0.01
71
4.150
0.377 1.01
3.981
0.397
5.552
0.350 - 0.01
76
4.164 1 0.23 0.382
4.08
0.389
5.085
1.11
0.344 0.00
81
3.898
0.01
0.77 0.07
5.77
5.717
0.352 = 0.00
87
3.978
0.01
0.09
0.392
5.732
0.349 = 0.01
93
3.942:000
0.00
0.00
0.305
5,891
0.08
0.367 = 0.00
100
3.836
+: 0.402
0.06
0.378
5.865
0.09
0.368 = 0.01
107
3.905
0.17 0.401 0.01
4.06
0.383
5.698
0.09
0.380 0.01
115
4.097
+ 0.20 0.387
+
5.121
0.384
5.710
0.349 = 0.01
123
3.714
:: 0.18 0.01
0.07
0.382
5.721 0.09
0.359 = 0.01
132
3.657
+ 0.17 0.413
4.729 1
0.390
5,434 0.08
0.366 = 0.00
142
3.675
3675::0.00
0.01
4.05
0.393
5,442 0.07
0.374 0.00
152
3.663
#.16
0.01
4.05
0.396
5.342
0.07
0.378 0.00
163
0.17
0.01
0.22
0.391
5,431 0.08
0.373 = 0.01
175
3.720
0.17 0.001
0.07
0.387 +000
5.538
0.08
0.367 = 0.01
188
3.632
0.23 0.383 0.00
4.430
0.382
5.298
1 0.08
0.351 _ 0.01
202
3.519
1.16 0.417
4.329
0.388
5.350
0.07
0.369 0.00
217
3.488
1. 0.15 0.421
4.149
0.391
5.145 1 0.07
0.376 0.00
233
3.466
= 0.15 0.01
0.080 0,392
5.100 0.07
0.380 = 0.00
251
3.477
+ 0.15 0.00
4.048 0.393
5 0.07
0.382 = 0.00
269
3.424
0.14 0.428
4.008
0.395
5,034 = 0.07
0.384 0.00
288
3.409
0.14 0.00
3.98
0.397
5.014 0.07
0.384 0.00
309
3.391
0.14 0.40
3.968 +.05
0.39
4.998 + 0.07
0.385 + 0.00
330
3.366
+ 0.14 0.00
3.953
0.39
4,980
0.06
0.386 + 0.00
353
3.349
+ 0.13 0.435
1.05
0.399
4,973 0.06
0.386 = 0.00
378
3.334
+ 0.13 1.01
1.04
0.400
4.957
0.06
0.387 0.00
403
3.310
1.10:0..33
3.916
0.401
4.943
1 0.06
0.388
431
3.013
1: 0.14 0.483
0.28
0.47
4.252
1: 0.05
0.425 = 0.00
460
3.262
+ 0.12 0.00
3.889
0.00
4.915 + 0.06
0.389 = 0.00
491
3.250
+ 0.12 0.00
3,881 0.43
4.907
0.06
0.390 0.00
524
3.240
0.12 0.00
3.875 0.00
4.899
+ 0.06
0.390 0.00
548
2.880
0.10 0.01
3.385 0.00
4.244 1 0.0S
0.445 = 0.00
582
2.746
+ 0.11 0.481 0.01
3.301
0.00
4.131 + 0.08
0.454 = 0.00
618
2.957
+ 0.10 0.498 0.01
3.438
0.487
4.521 + 0.08
0.455 = 0.00
656
2.706
0.09 0.491
3.05
0.486
3.869 = 0.04
0.447 0.00
696
2.776
0.496=00000
3,278
0.486 0.00
4.007 = 0.04
= 0.453
740
4.09
3.044
0.488
3.825
: 0.04
0.448 = 0.00
785
2.655
+ 0.08
3.016
0.489
0.00
3.797
0.04
0.449 + 0.00
834
2.647
0.08 0.448+00000
3.005
3.786
0.04
0.450 = 0.00
885
2.639
+ 0.08 0.01
2.995
0.490
3.775
0.04
0.451 = 0.00
940
2.636
0.08 0.499
2.988 1.04
0.491
3.768
1 0.04
0.451 = 0.00
997
2.630
1 0.08 0.500
1.00
2.981 0.04
0.491
3.761
17761:100 0.04
0.451 + 0.00
1058
2.624 1 0.08 0.500 0.01
2.973
1 1.04 0.492
3.753
11533-1000 0.04
0.452 + 0,00
1123
2.619 + 0.08 0.501
0.01
2.968 0.04
0.492
3.748 0.04
0.452 = 0.00
1191
2.614
0.08 0.501 0.01
2.960
0.492
3.740
0.453 = 0.00
1263
2.609
0.08 0.502
2.954
0.93
3.734
0.453 = 0.00
1339
2.604
+ 0.08 0.502 +
2.999
0.493
3.728
17728:000
0.04
0.453 = 0.00
1419
2.600
+ 0.08 0.502
2.944
0.40
3.723
0.04
0.454 + 0.00
1,503
2.595
0.08 0.50
2,937
0.04
0.00
3.716
0.04
0.454 + 0.00
1592
2.592
0.08
0.00
2.932
0.04
0.09
3.711
1011:0000 0.04
0.454 = 0.00
1686
2,588
0.08 0.01
2.927
1 0.04 0.00
3.706
1 0.03
0.455 - 0.00
1785
2.583
+ 0.08
0.00
2.922
1 0.04 0.00
3.701 + 0.03
0.455 = 0.00
Continued on next page
35

---

Published as a conference paper at ICLR 2026
GAT
GCN
GraphSAGE
Test Loss
Test Acc
Test Loss
Test Ace
Test Loss
Test Acc
1890 2.380 0.07 0.504 1 0.01
2.917 1 0.04 0.495 0.00
3.696 1 0.03
0.456 + 0.00
2001
2.577 1 0.07 0.504
0.01
2.912 1 0.03 0.495 1 0.00
3.692 1 0.03
0,456 + 0.00
2120
2.574
0.505 0.07
0.01
2.908
0.03 0.496 0.00
3.688 0.03
0.456 = 0,00
2246
2.570 0.07 0.505
0.01
2.904
#0.00
3,683 0.03
0.457 = 0.00
2379
2.567 0.07 0.505
2.899
0.496
3.679 = 0.03
0.457 = 0.00
2522
2.364 1.04 0,506
2.895
0,497
3.675 0.03
0.457 = 0.00
2674
2.561 + 0.07 0.506+0..00
2.891
0.497
3.671 + 0.03
0,458 = 0.00
2836
2.558 0.07 0.506+00.00
2.888 + 0.03
3.668 + 0.03
0.458 = 0.00
3009
2.556 + 0.07 0.507 0.01
2.884
0.497 +
3.664 + 0.03
0.458 0.00
3193
2.553 1553:000 0.07 1.507:0.00
2.881
0.09
3,661 = 0.03
0.458 = 0.00
3390
2.550 :: 0.07 0.507
0.01
2.877 0.03
0.09
3.657 + 0.03
0.459 = 0.00
3600 2.548 +: 0.07 0.507
0.01
2,874
0.03
0,498
3,654 + 0.03
0.459 = 0.00
3825
2.546 0.07
0.00
2.871
0.498
3,650 0.03
0.459 = 0.00
4065
2.543 0.07
0.01
2.868 0.03
0.09
3.647 = 0.03
0.460 = 0.00
4460
2.044
0.00
2.153
0,547
2.725 1 0.04
0.544 = 0.00
4736
2.039 + 0.03 0.00
2.150 0.02
0.54
2.666 + 0.05
0.548 + 0.00
5028 2.090
+: 0.07 0.552
2.084 0.02
0.54
2.581
+ 0.05
0.550 - 0.00
5338
2.078
0.05
2.093
0.00
2.570
0.04
0.552 0.00
5668
2.067
0.06 0.552 0.00
2.066 1 0.02 0.550 0.00
0.04 2.550
0.554 = 0.00
Table 5:
Test loss and accuracy (mean std over 20 seeds) for Reddit_50k.
GAT
GCN
GraphSAGE
Purain
Test Loss
Test Acc
Test Loss
Test Ace
Test Loss
Test Acc
200
2.775 + 0.10
2.877 = 0.05
0.397 + 0.01
4.878 = 0.32 0.312 + 0.02
213
2.717
0.14
2.689 = 0.08
0.01
3.552 # 0.12
0.331 + 0.01
227
0.114
2.588= 0.03
0.426
3.347
0.346 0.01
242
0.11
2.535 = 0.03
0.435
3.227
0.354
259
2.612
2.171 + 0.03
0.415
3.111
0.361
276
2.675
0.12
2.427 + 0.03 0.00
3.037 0.08
0.373 0.01
294
2.675
2.409 = 0.03
0.00
2.990
0.377 0.01
314
2.649
2.364 = 0.03
0.46
0.01
0.385 0.01
335
0.11
2.224 = 0.03 0.00
3.064
0,409
358
2.649
0.11
2.190 + 0.03
0.458
2.817
0.423 0.01
382
2.649
0.11
2.111 + 0.08
0.00
0.04
0.431 0.01
408
2.605
0.11
2.087 + 0.03 0.01
2.703
0.435
436
2.605
0.11
2.048 1 0.03
0.482
2.658
1.05
0.441 0.00 0.01
466
2.605
0.11
2.016 1 0.03 0.487
0.448 0.01
498
2.581
0.10
1.999 + 0.03 0.492
2.573
0.451 0.01 0.01
532
2.581
- 0.10
1.980 = 0.03
0.492
2.04
0.453 0.01
568
2.581 0.10
1.970 = 0.03
0.40
2.513
0.458
600
2.553
0.09
2.149 = 0.05
0.452 #0.02
2.965
0.427
630
2.553
+ 0.09
2.109 + 0.04
0.460
2.886
- 0.06
0.
662
2.553
+ 0.09
2.073 + 0.04
0.468
+
2.817
0.438 0.01
695
2.553
+ 0.09
2.029 + 0.04
0.476
2.763
0.00
731
2.530
0.09
2.004 + 0.04
0.08
2.719
0.448 0.01
770
2.530
0.09
1.969 = 0.04
0.488 0.02
2.680
2.680
0.452 0.01
811
2.508 + 0.08
1.949 = 0.04
0.492
0.002
2.64
0,456 0.01
855
2.508 + 0.08
1.923 : 0.04
0.497 4.00
2.607
1.05
0.461
902
2.508 + 0.08
1.908 = 0.04
0.500
2.575
+.001
952
2.508 0.08
1.894 = 0.04
0.501 0.02
2.553
0.467
1005
2.488 + 0.08
1.865 = 0.04
0.508
2.523
0.471
1062
2,488 1 0.08
1.851 + 0.04
0.509
0.002
2.507 1.05
0.473
1122
2,488 0.08
1.842 0.04
0.02
2.489
0,476
1186
2,488 0.08
1.838 + 0.04
0.02
2.170
0.477
1254
2.471 0.08
1.800
= 0.04
0.014
2.455
0,480
0.01 0.01
1326
2.471 + 0.08
1.825 = 0.04
0.01
2.443 = 0.05 0,481 + 0.01
Continued on next page
36

---

Published as a conference paper at ICLR 2026
GAT
GCN
GraphSAGE
Test Loss
Test Acc
Test Loss
Test Ace
Test Loss
Test Acc
1402
2.471 0.08
1821 + 0.04
0.517 0.02
2.426
0.05
0.484 1: 0.01
1483
2.471 1 0.08
1.819 + 0.04
0.518 1 0.02
2.415 1 0.05
0.485 1 0.01
1568
2.454 +: 0.08
1.816 + 0.04
0.518
2.401
0.05
0.486
0.01
1658
2.454 = 0.08
1.812 = 0.04
0.521
2.390
0.487 0.01
1753
2.454 = 0.08
1.810 = 0.04
0.521
2.378
1854
2.441 + 0.08
1.807 = 0.04
0.523
2.365
0.490
1960
2.411 + 0.08
1.806 + 0.04
0.321
2.356
#0001
2071
2.441 0.08
1.803 0.04
0.525
2.346
0.49
2188
2.428 + 0.08
1.802 + 0.04 0.526
0.02
2.336
0.05
0.493
2311
2.428 0.08
1.799 = 0.04
0.528 0.00
2.326
0.05
0.494
2441
2.428 + 0.08
1.796 + 0.05
0.528
2.318
1 0.05 0.495 0.01
2577
2.417 0.08
1.796 + 0.05
0.529
+
2.310
0.05
0,496
0.00
2721
2.417 0.08
1.794 0.05
2.303
0.05 0.497
2873
2.417 0.08
1.792 = 0.05
0.531
0.02
2.295 0.05
0.498
3033
2.406 + 0.08
1.790 = 0.05
0.532
2.287 0.00
0.499
3202
2.406 0.08
1.789 + 0.05
0.532
0.02
2.281 1.05
0.011 0.01
0.499
3380
2.406 1 0.08
1.787 + 0.05
0.533
0.02
2.275
0.05
0.500
0.01
3568
2.397 0.08
1.786 + 0.05
0.531
2.268
0.05
0.501
3765
2.397 0.08
1.784 + 0.05
0.534
2.262
- 0.05
0.501
3973
2.397 + 0.08
1.783 = 0.05
00003
2.256
0.05
0,502
4191
2.397 + 0.08
1.781 = 0.05
0.535
0.00
0.05
0.503
0.01
4420
2.388 + 0.07
1.780 = 0.05
0.536
2.246
0.05
0.503
0.01
4661
2.388 0.07
1.779 + 0.05
0.537
2.240
0.504 0.01
4914
2.388 + 0.07
1.778 + 0.05
0.537
+.003
2.235
0.05
0.504 0.01
5179
2.380 + 0.07
1.776 + 0.05
0.538
0.03
2:230
0.505
0.01
5457
2.380 0.07
1.776 + 0.05
0.538
0.03
2.226
0.05
0.505
0.00 0.01
5749
2.380 1 0.07
1.774 1 0.05
0.539
1 0.03
2.222
0.05
6054
2.372
0.07
1.774 1 0.05
0.539
1.00
2.218
0.05
0.506
6374
2.372 = 0.07
1.772 = 0.05
0.540
2.215
0.507
6710
2.372 + 0.07
1.771 + 0.05
0.540
2.210
0.507
7061
2.365 0.07
1.771 = 0.05
0.541
0.05
0.508
7429
2.365 0.07
1.770 + 0.05
0.511
2.203 0.05 0.508
7814
2.365
0.07
1.769 + 0.05
0.00
2.200
0.508
8217
2.359
+ 0.07
1.768 + 0.05
0.512
2.196
0.05 0.509
8639
2.359
+ 0.07
1.767 = 0.05
0.542
2.193
1193+0000
0.50
0.00
9080
2.359
= 0.07
1.766 = 0.05
0.04
2.189
0.05 0.01
9541
2.353
1.756 = 0.05
0.543
2.186 1.06:00000 0.05
0.010
10023
2.353 + 0.07
1.765 + 0.05
0.00
2.183
0.01
10527
2.353 + 0.07
1.764 + 0.05
0.05 0.03
2.179
0.511
11054
2.348 + 0.07
1.763 = 0.05
0.54
2.176
0.00
11605
2.348
0.07
1.762 0.05
0.545
2.173
0.011
12180
2.348
0.07
1.762 1 0.05
0.545
1.03
2.170 0.06
0.512 0.01
12781
2.343 1 0.07
1.761 + 0.05
0.545
1.003
0.512 0.01
13409
2.343 = 0.07
1.760 = 0.05
0.545
2.06
0.00
14064
2.343 - 0.07
1.760 = 0.05
0.546
2.162
0.01
14747
2.338
0.07
1.759 = 0.05
0.546
0.06
0.01
15459
2.338 + 0.07
1.758 + 0.05
0.546
2.158 0.06
0.01
16201
2.338 + 0.07
1.758 + 0.05
0.03
0.06 0.00
16975
2.331 0.07
1.757 + 0.05
2.153 0.04
0.01
17781
2.334 + 0.07
1.757 = 0.05
0.04
2.151
0.00
18621
2.334 + 0.07
1.756 = 0.05
0.00
2.149 0.06
0.01
19596
2.330 + 0.07
1.756 + 0.05
0.508
2.147
0.01
20607
2.330
+ 0.07
1.755 + 0.05
0.548
0.06
0.001
21656
2.330
0.07
1.755 = 0.05
0.04
2.143
0.01
22743
2.326
0.07
1.754 = 0.05
0.00
2.142
0.01
23870
2.326
0.07
1.754 1 0.05
0.549
2.140
0.06
0.00
25038
2.326
0.07
1.753 + 0.05
0.03
2.138
0.06
0.516
26249
2.322
1 0.07
1.753 + 0.06
0.04
2.137
1 0.06
0.516
27504
2.322 0.07
1.753 = 0.06
0.549
2.135
0.06
0.516
28805
2.322
0.07
1.752 = 0.06
0.549
2.134 0.06
0.516 0.01
Continued on page
37

---

Published as a conference paper at ICLR 2026
GAT
GCN
GraphSAGE
Test Loss
Test Ace
Test Loss
Test Ace
Test Loss
Test Acc
30153
2.319
0.07
1.752 + 0.06
0.550
0.03
2.133
0.06 0.516 1 0.01
31549
2.319 1 0.07
1.751 + 0.06
0.550 1 0.03
2.132 1 0.06
0.516 1 0.01
32995
2.319 +: 0.07
1.751 + 0.06
0.550
1 0.03
2.130 4: 0.06
0.517 + 0.01
33201
2.319 + 0.07
1.751 = 0.06
0.550
+ 0.03
2.130 = 0.06
0.517 0.01
Note GAT Results. The original GAT logs for Reddit_50k were not recoverable. We have relaunched all training runs and will update the tables and figures prior to the Dec 3 deadline.
Table
Test loss and accuracy (mean Worst ForstCane Laase__ottteneche
+ std over 20 seeds) for
GAT
GCN
GraphSAGE
Thrrin
Test Loss
Test Acc
Test Loss
Test Acc
Test Loss
Test Acc
300
3.208 + 0.07
0,406 + 0.00
2.077 + 0.05
0.387 + 0.00
2.511 + 0.04
0.395 + 0.01
318
3.117 + 0.08
0.401
0.00
2.122 0.06
0.414 0.00
2.566
+ 0.04
0.417
0.01
338
2.926 +: 0.05
0.404
+ 0.01
2.111 0:06
0.405
2.438
0.04
0.419
0.00
360
2.739 + 0.05
0.408
0.00
2.072
0
2.409
0.05 0.424 1 0.01
382
2.694 0.05
0,408
= 0.00
0.417
2.340
0.04
0,426 +: 0.01
407
2.546 + 0.05
0.408
= 0.00
1.911
0.411
2.289
0.04 0.425 + 0.01
432
2.452 + 0.04
0.408
- 0.00
+.05
0.416
0.04
0.426 0.00
459
2.383 + 0.04
0.410
1.78
0.414
2.177
0.430 =
488
2.351 + 0.04
0.411 + 0.01
0.421
2.116
0.434
0.01
519
2.185 1 0.04
0,412 0.00
1.715
0.426
2.052
0,437 1 0.01
552
1,990 1 0.03
0.415 1 0.00
1.663
1.05
0.432
2.030
1.000
0.440
0.01
587
1.887 1: 0.03 0.415 1: 0.00
1.05
0.435
1.986
0.443 0.00
624
1.832 = 0.04
0.412
1.63
0.435
1.900
0,443 0.01
663
1.774 + 0.04
0.00
1.613
0.42
1.900
0,441 + 0.01
705
1.763 0.07
0.418
1.579
0.44
1.93
0.443 0.00
749
1.806 + 0.09
0.426
0.01
1.530
0.449 0.00
1,901
0:00
0.448 0.00
796
1.749 + 0.03 0.430
+ 0.00
1.505
0.452
1,870
0.03
0.446 0.00
846
1.689 + 0.03
0.438
+ 0.01
1.485
+
0.453
1.824
0.03 0.448
0.00
900
1.627 + 0.03
0.438
0.00
1.437
0.456
1.795
0.03 0,449 + 0.00
956
1.586 0.03 0.441
: 0.00
1.407
0:04
0.459
1.763
0.03 0.450 1 0.01
1017
1.545 1 0.03
0.440
1.389
0.004
0.462
0.03
0.455
0.01
1081
1.531 + 0.02
0.440
0.01
1.377
0.463
0.02
0.457
0.01
1 1149
1.502 + 0.02
0.437
0.00
= 0.00
0,46
1.613
0,462 0.00
1221
1,466 0.02
0.435
1.323
0.468
1.573
0.462 =
1298
1.425 1 0.02
1.310
0.470
1.554
0.400
1379
1.389 +: 0.01
0.437 0.01
1.294
0.471
1.549
0.02
0.460
1465
1.362 + 0.02 0.02
0.433=0000
1.27
0.472
0.00
1.519
0,461 0.01
1556
1.335 = 0.01
0.435
1.258
+
0.75
1.494
0,461 0.01
1653
1.303 : 0.01
0.438
1.240
0.478
1.69
0.466 0.00
1755
1.278 = 0.01
0.438
1.38:0001
1.002
0,480
0.02
0.468 0.01
1863
1.257 + 0.01
1.02
0.482
1.40
0.470
1977
1.240 + 0.01
0.441
+ 0.00
1.198
+
0.483
1.402
0.01
0.473 + 0.01
2098
1.225 + 0.01
0.441
+ 0.00
1.186
0.484
1.382
0.474 + 0.01
2226
1.213 + 0.01
0.443+0.00
+
4.00
1.365
0.01
0.475
0.01
2362
1.201 1 0.01
0.444
0.00
1.168
1
0.489
1,351
0.01
0.477
0.01
2507
1.190 1 0.01
0.445
1 0.00
1.159
11599-0.00
0.490
0.490
1.336
0.01
0.480
1 0.01
2661
1.181 1 0.01
0.447 1.00
1.152
1
1.316
0.01
0,483 1. 0.01
2824
1.172 0.01
0.448
1.145
0.492
1.304
0.01 0.485
= 0.01
2997
1.165 + 0.01
0.449
1.138
0.494
1.290
0.01 0.485
0.01
3180
1.158 + 0.01
0.00
1.02
0.09
1.278
- 0.01 0.487
0.01
3374
1.153 + 0.01
0.451
0.00
1.127 +
0.497
1.267
+ 0.01
0.489
0.01
3579
1.148 + 0.01
0.452
1.122
0.498
1.256
+ 0.01
0.490
+ 0.01
3796
1.143 0.01
0.00
1.117
0.499
1.248
0.01
0.01
0.490
+
4025
1.139
1 0.01
0.00
1.112
0.02
0.49
1.240
0.01
0.492 0.01
4267
1.135 - 0.01
0.00
1.108
0.02
1.00
1.232
+ 0.01 0.493
0.01
Continued on next page
38

---

Published as a conference paper at ICLR 2026
GAT
GCN
GraphSAGE
Test Loss
Test Acc
Test Loss
Test Acc
Test Loss
Test Acc
4523
1.131 1 0.01
0.455
0.00
1.105
0.02
0.501 1 0.01
1.227 0.01
0.493
4793
1.128 1 0.01
0.456 1 0.00
1.101 1 0.02
0.502 1 0.01
1.219 0.01
0.494
0.01
5078
1.125 1 0.01
0,456 1: 0.00
1.097
1.01
0.502
1.214
0.495 1: 0.01
5379
1.122 = 0.01
0.457 0.00
1.094 #.01
0.503
1.210
0.496 + 0.01
5696
1.119 = 0.01
0.458
0.00
0.01
0.01
1.204
0.497 0.01
6030
1.116 0.01
0.01
0.458
= 0.00
1.088
0.00
0.504
1.200
0.01
0.497 - 0.01
6381
1.114 0.01
0.01
0.459
+ 0.00
0.504
1.196 + 0.01
0.498 + 0.01
6751
1.112 0.01
0.459
+ 0.00
1.08
0.505
1.192
0.01 0.498 + 0.01
7139
1.109 0.01
0.460
+ 0.00
1.081
0.01
0.505+0000
1.189 + 0.01 0.499
0.01
7547
1.107 -
0.460
0.00
1.079
0.01
0.01
1.186
0.01
0.499 0.01
7975
1.105 + 0.01
0.460
1 0.00
1.077 0.01
0.506
1.183 1 0.01
0,500
8424
1.104 +: 0.01
0,461
- 0.00
1.075 +
0.506
1,180 1 0.01
0.500 0.01
8895
1.102 0.01
0.461
= 0.01
1.073
0.50
1.178
0.01 0.501
0.01
9389
1.100 = 0.01
0.461
0.00
1.071
+ 0.01
0.507
1.175
0.501 0.01
0.01
11000
1.086 + 0.01
0.471 = 0.00
1.021 + 0.00
0.00
1.060
+ 0.00
0.476 0.00
R SYNTHETIC EXPERIMENTS VERIFYING THE MINIMAX SCALING LAW
This appendix provides controlled synthetic experiments validating the worst-case minimax rate established in Theorem [
We directly instantiate the least-favorable construction:
Enr(n, d) CV log d n
(1 + 7),
with small multiplicative noise term 7) mimic empirical variability.
The main text (Figure T uses the collapse test-the most sensitive diagnostic-to show that only the normalization /log d/n removes both n-- and d-dependence. For completeness, this appendix includes two orthogonal sanity-checks:
1. Error for multiple d Confirms the slope in is exactly n 1 for every fixed d, and the only effect of increasing is a vertical shift proportional to vlog d.
2. Error for multiple n Confirms the error grows in d exactly the rate Vlog d, and that larger n only rescales curves downward by the factor 1/ /n...
Together, these experiments verify both axes of the minimax law and complement the collapse-based evidence shown in the main text.
Interpretation of Figure 8 All curves follow the predicted n 112 slope on the log-log scale. Increasing produces a parallel vertical shift exactly equal to /log d, with no change in slope. This directly verifies the n-axis behavior of the minimax rate.
For each fixed n, the error grows vlog d, producing smooth monotone curves d. The family of curves for increasing n differ only by the 1/v2 scaling factor. This verifies the d-axis behavior of the minimax rate.
Interpretation of Figure 9
In combination with the collapse experiment in the main text, these two synthetic plots provide full empirical confirmation of the minimax lower bound in Theorem
THE USE OF LARGE LANGUAGE MODELS (LLMs)
In preparing this manuscript, we used Large Language Models (LLMs) solely as general-purpose assistive tools for grammar checking, language polishing, and improving clarity exposition. LLMs were not used for research ideation, theoretical development, experiment design, or analysis, and they did not contribute any scientific content. The authors take full responsibility for the contents of the paper, including any parts where L.MSs were used to improve writing style.
39

---

Published as a conference paper at ICLR 2026
Synthetic Worst Case Minimax Error for Different
de30
d+30
d=100
de300
10-1-
d-1000
10
Figure 8: Error for different d.
Error Dimension d for Different Fixed
500
0.14
10000
160000
Gro
0.08
0.04
0.02
10a
10a d (ddimensian)
10a
Figure 9: Error vs. for different fixed n.
40


Reviews:
[{"review_id": "WMfAbdfauL", "reviewer": "Reviewer_dPQV", "summary": "This paper studies the sample complexity of ReLU-based GNNs, deriving minimax lower bounds on generalization error ( $\\sqrt{\\frac{\\log d }{n}}$ for arbitrary graphs and $\\frac{\\log d }{n}$ under spectral-homophily). Experiments on standard datasets with GCN, GAT, and GraphSAGE are presented to support the scaling claims.", "questions": "(1) How do you justify the omission of  $\\kappa$ from the sharper lower bound in Theorem 2, given its role in the spectral assumption?\n\n(2) Have you considered comparing empirical errors directly to the theoretical bound (including constants) instead of curve fitting?\n\n(3) Have you conducted controlled experiments varying $n$ and $d$ on synthetic graphs to confirm the scaling laws? What is the rationale for excluding large-scale benchmarks with samples $n>10,000$ or in worst-case constructions used in the minimax proof?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "(1) Theoretical novelty is high, providing the minimax analyses for GNNs. The bounds are clearly stated, and connecting theory to practice is an important goal.  \n\n(2) The results establish a crucial baseline for the statistical efficiency of GNNs and quantify the theoretical value of graph structure.\n\n(3) The bounds are stated clearly and the paper distinguishes between the general and structured graph scenarios.", "weaknesses": "(1)  Vacuous spectral-homophily assumption: The condition $\\lambda_2(L) \\le \\kappa / \\log n$ can be trivial for small $n$, making the sharper lower bound vacuous. $\\kappa$ is absorbed as a constant in the bound, raising questions about whether the bound meaningfully captures the role of graph structure.\n\n(2) Experimental verification of bounds: Curve fitting to candidate functional forms ($1/\\sqrt{n}, 1/n, 1/\\log n, 1/n^\\gamma$) **does not rigorously validate** the minimax lower bound. A more appropriate approach would compare the empirical test error directly to the derived bound, including constants, or estimate an empirical constant $C^\\star$ to show tightness.\n\n(3) Limited sample size regime: Experiments are restricted to $100 < n < 1000$, a narrow range insufficient to assess asymptotic scaling. Asymptotic bounds should ideally be tested over broader regimes, including **very small and very large** $n$, and with graphs approaching the worst-case constructions used in the theory. I recommend more experimental verification on synthetic datasets and OGB benchmarks.\n\n(4) Tightness claims:  The current experimental evidence does not demonstrate the tightness of the bounds. Without direct comparison of the experimental test error with the theoretical minimax bound, it is unclear whether the bounds are meaningful in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eOY9mBw4kY", "reviewer": "Reviewer_MrJY", "summary": "This paper presents a theoretical foundation for the sample complexity of ReLU-based graph neural networks by using minimax analysis for lower bounds of sample complexity. The paper finds that while GNNs can in principle match the $1/\\sqrt n$ scaling of feed-forward networks, realistic structural assumptions for graphs force risk to decay much slower. The paper also includes proof-of-concept experiments.", "questions": "Can you add some discussions on the link prediction task?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper provides the first sharp sample complexity lower bounds for GNNs under realistic structures.\n- Brief implementation code is provided.\n- The problem of generalization error and sample complexity is significant.", "weaknesses": "- The proof of Theorem 2 can be put in the appendix with only a sketch of proof provided in the main text. The extra remaining space can include more motivations and/or insights.\n- Sec. 3 mentions that three prediction regimes will be studied, but no theoretical results for link prediction have been provided (just one task experiment).\n- Sec. E and Sec. F seem to be the same but with an extra section title in the appendix.\n- Raw experiment results are not shown but only an aggregated table.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hjkZHwnUZ3", "reviewer": "Reviewer_EK1v", "summary": "This paper derives lower bounds to the sample complexity/generalization of GNNs using minmax theory. The paper derives such bounds both for inductive (graph level) and transductive (node level) settings. This is achieved using Fano’s inequality and by constructing packing numbers in the two settings.", "questions": "See Weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "This paper develops nontrivial analysis to prove an important property of GNNs. Lower bounds to the sample complexity of GNNs are important and novel, and missing from the current literature on GNN generalization. Especially, analyzing node-level tasks is very novel, as most other papers analyze graph-level tasks.", "weaknesses": "This is potentially a strong theoretical paper. My main comment is about making the paper more accessible to the GNN community. Deep learning is an interdisciplinary subject, and hence good papers in deep learning should give short “tutorial-like” introductions, possibly in the appendix, to any nontrivial theoretical tool used in the paper. \n\nSince this paper is both for experts on GNNs and experts in minmax bounds, and most often there is no intersection between the two communities, I recommend writing an introduction to minmax theory in the appendix and referring to it in the main paper. Specifically, it is not direct to see how the setting of regression is a special case of the general minmax risk, so I would explicitly write the general formulation of the minmax, and then write explicitly how regression is a special case. Moreover, a reference to minmax theory is missing, e.g., Chapter 15 in [A]. \n\nYou should also explicitly recite Fano’s inequality, and all other tools required in the proofs, like packing number. As it stands, many nontrivial tools are never explicitly defined in the paper, which makes it impossible for most potential readers to follow. It is also important to define all norms in the paper, as different people have different normalization standards for the same norm.\n\nFor motivation, I would also explain how the spectral gap/spectral–homophily is related to “bottleneckedness.”\n\nOnce the authors add such a section to the revised pdf I will raise my score.\n\nThe other direction  (Explaining GNNs to the statistical learning community) is already covered in the paper - GNNs are explicitly defined.\n\n\nMy second comment is about choosing a less generic title. Since there are many papers about GNN generalization bounds, I recommend (but don’t demand) writing a title that directly expresses that you derive a minmax analysis. This will make it easier for researchers in the future to search for the paper. Moreover, I would emphasize in the abstract and introduction that you also analyze transductive learning, since most other papers focus on inductive graph-level settings.\n\n\n\n[A] Martin.J. Wainwright. High-dimensional statistics : A non-asymptotic viewpoint. Cambridge Uni. Press, 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "91gTfJElSQ", "reviewer": "Reviewer_t7Km", "summary": "This paper studies sample complexity of ReLU-based GNNs. The authors prove (i) a worst-case minimax lower bound for graph-level prediction and (ii) a structure-aware node-level lower bound. Experiments on Cora, Reddit, QM9, Facebook with GCN/GAT/GraphSAGE study test-error scaling vs. the number of nodes. The work positions itself as delivering the first sharp lower bounds that explicitly reflect graph structure, complementing expressivity-driven upper bounds.", "questions": "Q1: Can you resample Figures 1–4 with more n points (esp. between 500 and 10k where curves diverge) and more seeds to provide confidence intervals and slope diagnostics on log–log plots? This directly addresses the robustness of the scaling claims. \n\nQ2: For each dataset and n, please compute $\\lambda_2$ of the induced labeled-node subgraph and report whether the condition required by Theorem 2 holds for a reasonable K, or provide an empirical estimate of K. This would concretely validate Theorem 2’s premise.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: Strong mathematical rigor and novelty in lower bounds. Theorem 1 establishes a worst-case minimax lower bound for ReLU MPNNs with explicit architectural assumptions. Theorem 2 links spectral–homophily to a structure-dependent (node-level, transductive) lower bound.\n\nS2: The experimental section provides validation over theorem 1 and 2, as multiple datasets and architectures fit to the proposed lower-bounds.\n\nS3: The paper carefully contrasts its lower-bound focus with recent expressivity/upper-bound works, clarifying complementary scope.", "weaknesses": "W1: Experimental granularity is thin. Figures sample only a handful of n values (6 per dataset; and n lower than 1,000 for Cora/Facebook due to dataset limits), which makes distinguishing the different asymptotics fragile. More densely sampled n (especially mid-range) and more seeds would increase robustness. \n\nW2: Scope of datasets and tasks. Only four benchmarks; the link-prediction result is limited to Facebook. Adding synthetic graphs with controlled spectral gaps/homophily and additional real datasets (e.g., ogbn-* datasets) would better stress-test the structural claim. \n\nW3: Verifying the structural condition. Empirical sections do not demonstrate the inequality which Theorem 2 requires numerically. Providing this would more tightly link the assumption to observed scaling.\n\nIm inclined to raise my score once the experimental concerns above are addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)