Full-Graph vs. Mini-Batch Training: Comprehensive Analysis from a Batch Size and Fan-Out Size Perspective
Authors: Mengfan Liu
Da Zheng
Junwei Su
Chuan Wu
Venue: ICLR 2026 Poster (2026)
Keywords: Graph Neural Network
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Full-graph and mini-batch Graph Neural Network (GNN) training approaches have distinct system design demands, making it crucial to choose the appropriate approach to develop. A core challenge in comparing these two GNN training approaches lies in characterizing their model performance (i.e., convergence and generalization) and computational efficiency. While a batch size has been an effective lens in analyzing such behaviors in deep neural networks (DNNs), GNNs extends this lens by introducing a fan-out size, as full-graph training can be viewed as mini-batch training with the largest possible batch size and fan-out size. However, the impact of the batch and fan-out size for GNNs remains insufficiently explored. To this end, this paper systematically compares full-graph vs. mini-batch training of GNNs through empirical and theoretical analyses from the view of the batch size and fan-out size. Our key contributions include: 1) We provide a novel generalization analysis using the Wasserstein distance to study the impact of the graph structure, especially the fan-out size. 2) We uncover the non-isotropic effects of the batch size and the fan-out size in GNN convergence and generalization, providing practical guidance for tuning these hyperparameters under resource constraints. Finally, full-graph training does not always yield better model performance or computational efficiency than well-tuned smaller mini-batch settings. The implementation can be found in the github link: https://github.com/LIUMENGFAN-gif/GNN_fullgraph_minibatch_training.

FULL-GRAPH VS. MINI-BATCH TRAINING: COMPRE- HENSIVE ANALYSIS FROM A BATCH SIZE AND FAN- OUT SIZE PERSPECTIVE
Mengfan Liu', Da Zheng', Junwei Su Chuan Wu
The University of Hong Kong. Ant Group
m1 621 connect. hku zhengda. zweng@antgroup.coomm junweisu. cs@gmail com, cwuêcs hk
ABSTRACT
Full-graph and mini-batch Graph Neural Network (GNN) training approaches have distinct system design demands, making it crucial choose the appropriate approach to develop. A core challenge in comparing these two GNN training approaches lies in characterizing their model performance (i.e., convergence and generalization) and computational efficiency. While a batch size has been an ef- fective lens in analyzing such behaviors in deep neural networks (DNNs), GNNs extend this lens by introducing fan-out size, as full-graph training can be viewed as mini- Mani-bbtch training with the largest possible batch size and fan-out size. How- ever. the impact of the batch and fan-out size for GNNs remains insufficiently explored. To this end, this paper systematically compares full-graph vs. mini-batch training of GNNs through empirical and theoretical analyses from the view points of the batch size and fan-out size. Our key contributions include: 1) We provide a novel generalization analysis using the Wasserstein distance study the impact of the graph structure, especially the fan-out size. 2) We uncover the non-isotropic effects of the batch size and the fan-out size in GNN convergence and generaliza- tion, providing practical guidance for tuning these hyperparameters under resource constraints. Finally, full-graph training does not always yield better model per- formance or computational efficiency than well-tuned smaller mini-batch settings. thub. c LIUMENGFAN gif/ GNN fullgraph minibatch training
The implementation can be found in the github link: https: thut
INTRODUCTION
Graph neural networks (GNNs) have demonstrated exceptional performance across diverse machine learning tasks involving graph-structured data (Zhang & Chen 2018 Xu et al. 2018 Gilmer et al. 2017| Su & Wu 2025a). defining characteristic of GNNs is their reliance on the graph structure to facilitate message- cressage-passing. enabling the learning of rich node representations from both structural and feature information (Gilmer et al. 2017). Consequently, the computational patterns of GNNs depend strongly the underlying graph structure, leading to two prominent and distinct paradigms for training GNNs: full-graph and mini-batch training (Bajaj et al., 2024 Hamilton et al. 2017
Zheng et al. 2022).
Full-graph training and mini-batch training are distinct GNN training paradigms. In full-graph training, the entire graph is processed simultaneously, and each node aggregates information from its neighbors across multiple message-passin layers. In contrast, mini-batch training divides the graph into smaller subgraphs or batches, training the model iteratively on subsets of nodes and their (sampled) local neighborhoods. These paradigms exhibit fundamentally different computational patterns, each requiring distinct system designs, training pipelines, and optimization strategies. For example, full-graph training necessitates efficient communication mechanisms to synchronize aggregations over the entire graph (Md et al. 2021 Peng et al. 2022), whereas mini-batch training demands careful optimizations of CPU-GPU data loading to accommodate frequent batch processing
(Chen et al. 2018 Zhu et al. 2019
Liu al. 2023) Understanding the differences between these
"Corresponding authors.

---

two paradigns is essential for identifying suitable training methods in specific scenarios and guiding the design of optimised training systems.
Existing Gaps. To systematically investigate the differences between full-graph and mini-batch training, the hyperparameters batch size (the number of sampled nodes) and fan-out size (the number of neighbors chosen per node each hop (Hamilton et al., (017)) offer critical lenses for analyzing GNN performance and computational efficiency, as full-graph training can be viewed as a special case of mini-batch training with maximum batch and fan-out sizes. However, despite increasing attention
in the literature, the impact of these hyperparameters remains insufficiently understood. Existing studies typically focus on individual parameters (e.g,, batch size or fan-out size independently) (Hu
it al.] [ Yuan et al. 2023) or singular aspects of evaluation (e.g.. convergence (Yang et al. [023)
Awasthi et al. p. accuracy (Tang & Liu 2023; Verma & Zhang 2019) [Su Wu (024). or
system efficiency ( (Naman & Simmhan 2024)), providing limited insights into the holistic trade-
offs between the two paradigms (see Sec. for further discussions). Although recent empirical
studies, such as (Bajaj et al. 2024), have attempted comparisons between full-graph and mini-bated training, their results are largely observational and hardware- or muviromment-depeddern their generalizability. Meanwhile, most of the existing GNN analyses typically rely strong simplifications, such as infinite-wide width assumptions that average out per- gradient noise (Yadati 2022) linear models with convex losses that remove local optima (Yang et al.) 2023 Lin et al. 2023), which obscure the effects of batch sizes or fan-out sizes on training dynamics. Thus, a
limiting
critical open question remains: How do the batch size and fan-out size influence the optimization dynamics, generalization capabilities, and computational efficiency of GNN training, particularly when comparing full- -grph and mini-bateh training paradigms?
Challenges. Comparing full-graph and mini-batch GNN training paradigms presents multiple inter- twined challenges. First, while the batch size and fan-out size are useful for analyzing differences between these paradigms, their impacts on model performance and system efficiency inherently depend on the hardware environment used. Therefore, meaningful comparisons necessitate measure- ment frameworks that are hardware-agnostic and supported by rigorous theoretical analyses. Second, both the computational dynamics of GNNs and the statistical properties of graph data are intrinsically tied to the underlying graph structure, which is directly influenced by choices of batch size and fan-out size. Altering these hyperparameters thus introduces complex interactions, highlighting the need for flexible analytical frameworks that can accurately capture these dynamics. Finally, comprehensively understanding the trade-offs between full-graph and mini-batch training demands frameworks capable of jointly evaluating model efficiency and generalization, ultimately guiding the development of practically optimized systems.
Contribution. To address the aforementioned research gap, in this paper, we conduct systematic study of full-graph and mini-batch GNN training under different batch sizes and fan-out sizes on transductive node classification tasks. The contributions are highlighted as follows.
> We characterize the role of the batch size and fan-out size in GNN optimization dynamic analysis (Theorem [ and 2), extending the settings to irregular graphs and GNNs with non-linear activations. better aligning with the practice. We also provide novel GNN generalization analysis (Theorem 3) using the Wasserstein distance to investigate the impact of graph structures, especially the fan-out size, where this distance can quantify graph structure differences between training and testing datasets.
> We theoretically uncover the non-isotropic impacts of the batch size and the fan-out size in GNN convergence and generalization, where the batch size has a greater impact on GNN optimization dynamics [.. while the fan-out size more strongly affects GNN generalization (Obs These findings suggest that, under memory constraints, adjusting the batch size is preferable when general- ization is the priority, given its more stable effect on generalization. In contrast, tuning the fan-out size is preferable when convergence is the concern, given its more consistent impact on convergence compared to batch size, while setting the fan-out size to moderate values balances convergence and computational efficiency as the magnitude of its impact on convergence decreases with larger values.
> We empirically use additional perration-basedd convergence metrics for hardware-agnostee compar- isons, rather than relying solely on time-based metries. Experiments on four real-world datasets
(Hamilton et al. 2017: Hu et al. 2020) and three GNN models (Zhang et al., 2019 Hamilton et al.)
2017 Veličkovic et al. 2017) validate our theoretical findings. We recommend keeping batch size
2

---

below half of the training nodes and the fan-out size under 15 for sparse graphs (Hamilton et al. 2017
Hu et al. 2020) to balance the model performance and computational efficiency.
Our theoretical and empirical findings support that full-graph training does not always yield superior model performance or computational efficiency compared to smaller mini-batch settings. Instead, carefully tuning the batch size and fan-out size in mini-batch settings often leads better trade-offs, such as faster convergence or improved generalization under resource constraints. These findings provide practical guidance for selecting training paradigms under specific task requirements.
2
PRELIMINARIES
Graph. Given a homogeneous undirected graph with total n nodes and the maximal degree dmaa S n, set Puain nodes in the training set and feest nodes in the testing set, with n = Trrain + Tlest- We allow arbitrary subsets of nodes to be selected as the training and testing sets. Let S Ruain be the batch size and 3 S dmax be the fan-out size in mini-bated training, where uniform neighbor sampling is employed to select neighbors.
Each node is instance (x,, 94) with feature x; and label yı- Let X E Rex be the feature matrix, where x; is the i-th row of X and r is the feature size. In the transductive learning setting, our task is to predict the labels of nodes (x, [x.)== by the GNN model trained on {x;) ) 1=1 U {3x Mar We assume that node features are fixed, and node labels are independently sampled from distributions conditioned on node features, which is widely adopted in the node classification task.
Let A represent the adjacency matrix of graph. We define full E 1T XT for full-graph training,
train E b for mini-batch training, and Alest E IR Rres x for inference, where A mini is a submatrix of A Let D denote a diagonal in-degree matrix with D representing the number of incoming iii.mmii edges to node i. We define D train E "R Muuio for full-graph training, train E Ra for mini- batch training, and Din
A mini
train
for testing. Dout E TR=x denotes the respective diagonal test E IR Ree
out-degree matrix. Ā = (Din + ( (D + I) " is the respective normalized adjacency matrix with self-loops, where self-loops ensure that each node retains its own features during aggregation, improving the model's learning ability. Here å; denotes the i-th row of A.
GNN model. Motivated by recent theoretical advances in understanding GNNs (Su & Wu 2025b Awasthi et al. 202T), we analyze the training dynamics using one-layer GNN model. This model serves powerful and well-established testbed for capturing phenomena arising from finite width and nonlincarity of GNNs. Its simplicity in model depth provides the analytical flexibility necessary to precisely characterize how batch size and fan-out size affect GNN training dynamics. In Appendix H we further discuss how our analyses and results generalize to multi-layer settings. Concretely, let W E R be the learnable model parameters of the GNN model and W R be the ground truth of W, where w; is the i-th row of W and h is the finite hidden dimension. We study a one-layer GNN with the ReLU activation, and define the output immediately after the first layer as z, a (auain XWT) Vi E training set, where (z) = max (z: 0) is the ReLU activation function, and the term again, represents the embedding aggregation on node i. This first-layer output may be followed by task-specific post-processing (e.g., linear projection in binary classification). Similarly, during inference, the output of the first layer given by z, = a :Wles.WW' T). Vi E testing set.
In this paper, we use || ||2, ||- || and || || to denote the 2-norm of vector, spectral norm of matrix and Frobenius norm of vector, respectively. For two sequences {pa} } and { we use O(g)) denote that Pn. S Cign for some absolute constant C1 > The notation table is in Appendix
3 OPTIMIZATION DYNAMIC
We present our theoretical studies on the GNN optimization dynamics. First, the optimization setup is introduced, representing how to handle interactions between batch size and fan-out size in optimization dynamics (Sec. B.I. Next, we show the convergence results, answering our research question in GNN optimization dynamic. We then reveal an interesting observation, yielding actionable implications for accelerating convergence under memory constraints (Sec. 3.2
3.1 OPTIMIZATION SETUP
Optimization algorithms. We aim to minimize the empirical risk Lurin
Etraining [ IWW, Amnii,,), where 1 (.) denotes the loss function. In practice, Cross-Entropy
3

---

(CE) and Mean Squared Error (MSE) are the most commonly used losses. Under full- graph training settings, the model parameters are updated via gradient descent (GD) as Wrilll
[+1
W The V waa Lusin (Wi A where T > O is the learning rate at the t-th training itera- tion. Under mini-batch training settings, the model parameters are updated via stochastic gradient descent (SGD) as W W n, where G, = 1/2 ie nodes V Weigg / (Waii (rain,
denotes the stochastic gradient at the t-th training iteration.
Handling interactions between batch size and fan-out size in optimization dynamic. To handle these interactions, we isolate the impact of the graph structure in the loss and gradient expressions. A key challenge is that the nonlinear activation (e.g., ReLU) processes aggregated node features input, making these expressions analytically intractable. To overcome this, we decouple the aggregated node features from the activation function. For instance, we extract the aggregation from the ReLU function by reformulating squared loss terms, or rewrite the ReLU function using a position- 0/1 indicator matrix that can directly multiply the aggregated node features.
3.2 CONVERGENCE RESULTS
Building on the aforementioned setup in Sec 3.1 we study GNN convergence results under suitable assumptions on the distribution of node features as well as the boundedness of the feature matrix norm, the ground truth parameter norm and the separation between aggregated node features with different labels in the training data (see Assumptions B.] B.2 in Appendix B and Assumption E. in
Appendix D.. with detailed proof' provided in Appendix B
Theorem 1. (Convergence of Mini-batch Training with MSE) Suppose Wimnn are generated by Gaussian initialization. Under Assumptions B.1 and B.2 if the fan-out size satisfies Ciqini < 3 S Cmnini 6 for constants CT Cinini E (0, 1) to ensure a sparser adjacency than a fully connected graph, then with high probability, Limain (Wiiini A m
S c 'for any c E (0, 1), provided that the number of iterations T = Thirain 6 3 be- log 1h² under the mini-batch training.
Theorem 2. (Convergence of Mini-batch Training with CE) Suppose Wmini are generated by Gaussian initialization. Under Assumptions B. and E.I if the hidden dimension of a one-round GNN satisfies h = Ω (log (Peruin) B-1 ( (narain
I + + to ensure the finite width, then with high
probability, Txynin (Wmini A mini
Irain) S <foor any 2 provided that the number of iterations T O mriin (log (Terain) ))² a 26 3-13-2 (nemain
+)-1) under the mini-batch training.
When the fan-out size 3 reaches dmax and the batch size b reaches Ramin, the upper bound on the number of iterations to convergence mini- training matches that of full full-graph training (see Theorem B.4, under MSE in Appendix B and Theorem D.2, under CE in Appendix D).
Remark 3.1. Our theoretical results show that increasing the batch size b for a fixed fan-out size leads to more iterations to convergence under MSE (Theorem D. but fewer iterations under CE (Theorem in the mini-batch setting of one-round GNNs, different from DNN training. In contrast, increasing the fan-out size 3 under fixed batch size consistently reduces the number of iterations required for convergence under both MSE (Theorem and CE (Theorem 2p.
Remark 3.2. Our theoretical analysis reveals that the magnitude of the fan-out size's impact on GNN convergence jointly depends on the batch size and the fan-out size 3, diminishing as either b (under CE) 33 (under MSE and CE) grows. The magnitude of this impact can be characterized by the absolute slope [as of the number of iterations T for convergence with respect to the fan-out size 8, where steeper slope indicates stronger impact. Specifically, Theorem I gives | 0 3/255/2) under MSE and Theorem 2 gives |0T/a3| O 37/22-1) under CE.
Answering our research question: Remark 3.1 and Remark 3.2 represent the impact and interplay of the batch size and the fan-out size in the GNN optimization dynamic. Therefore, conclude that full-graph training does not always provide superior convergence speed than smaller mini-ban batch settings, especially under MSE
Furthermore, we present an interesting observation, providing insights into accelerating GNN conver- gence under memory constraints.
Obs.1: GNN convergence is more sensitive to batch size than to fan-out size. Remark 3.1 high- lights stronger dependence of GNN convergence batch size bo than fan-out size 8, larger
4

---

batch size b leads to opposite convergence trends under MSE and CE, while increasing the fan-out size exhibits a consistent trend. This observation cannot be fully interpreted by the popular explanation of DNNs, which posits that increasing the batch size reduces gradient variance, resulting in fewer iterations to converge (Cong et al. 2021a Liu et al., 2024). We further consider the impact of message passing on the loss and gradient, providing the interpretation of Obs T in Appendix [F]
Implication for accelerating convergence. Under memory constraints, Obs [ suggests that adjusting the fan-out size offers more reliable way accelerate GNN convergence, as the fan-out size keeps the same convergence trends under both MSE and CE. To tune the fan-out size B, Remark 3.2 highlights that a moderate value of provides practical balance between convergence and computational efficiency, as the reduction in the number of iterations for convergence becomes smaller when increasing beyond moderate values, particularly with large batches under CE.
4 GENERALIZATION OF MINI-BATCH TRAINING
We represent our theoretical study on GNN generalization. First, problem setup introduced, representing how to isolate the impacts of batch size and fan-out size in generalization by employing Wasserstein distance (Sec. [411.. Next, we show the generalization result, answering our research question in GNN generalization. We then present an interesting observation, yielding the actionable implication for improving generalization under memory constraints (Sec.
4.1 PROBLEM SETUP
Basic setup. We aim bound the generalization gap between the expected testing risk and the empirical training risk under the mini-batch training settings, where the expected testing risk is given
by Liest
Wmini
full
Eierest set (W ganinn full lest,s)
and the empirical training risk is ex-
pressed as Luaai
Wmini
mini
Σ Eigtmining set (Wminn ammin.)) Note that inference utilizes
train
all testing neighbors across the entire graph, whereas mini-batch training relies on sampled neighbors within limited hops. We then employ the Wasserstein distance (Kantorovich) 1960) to quantify the difference in graph structures between training and testing datasets, as the Wasserstein distance effectively measures differences in non-i.i.d data, particularly regarding geometric variations.
Definition (Distance between Training Set and Testing Set). Define the distance from the training set to the testing set as the Wasserstein distance given by A (3,b)
(infecelomnnaal Eigurina sea Ejeust 0i.5ō (yi, yý B. where Ptrain (9:) and Puea (Vi) denote the probability of yı appearing in training and testing sets, respectively. @[puain Prest] is the joint prob- ability of Ptrain and Prest. The infimum in the first equality is conditioned on Ej see Oig =
Prain (y:), Eiguraining set Oig Piest (uj) Ozg 2 O. 5 (y,, B,b) is the distance function of any two points from training and testing sets, respectively.
We set 8 Yy,
Csha
(5ttll + 5full-min)) with constant Cs > O, Temin min frinfninn [Murain Trest)
and 8iulll =
full lest.
full a
2
+ 2 [ealll) p² as a constant, mainly capturing the difference of distri-
|
butions between the training and testing data in full-graph training. :full-miii = | || : a 1| reflects the structural difference between full-graph and mini-batch graphs per node during training.
Isolating the impacts of batch size and fan-out size in generalization. To isolate these impacts, focus on the discrepancy U between expected training and testing losses before training, which is the only term for non-i.i.d. graph data in our generalization analysis, with detailed proof in Appendix M Since the training and testing datasets are split beforehand, U depends on the structural difference between training and testing graphs, which we quantify using the Wasserstein distance A (8, b). We show that greater similarity between training and testing graph structures leads to smaller U.
4.2 GENERALIZATION RESULT
Building the aforementioned setup in Sec we the Wasserstein distance to study the generalization result in PAC-Bayesian framework (McAllester 2003) under mini-batch GNN training with MSE, given suitable assumptions the boundedness of the Frobenius norm of the feature matrix and the parameter norm (see Assumptions G.T and G.2 and the detailed proof in Appendix G
Theorem 3. Suppose Wimin are generated by Gaussian initialization. Under Assump- tions G.I and G.2 with high probability, for the posterior distribution Q over hypothe-
5

---

sis space in the mini-batch training settings with MSE. we have Liest (Wmini full 2)
Lmnin Wiimnin
mint
②) ( (B where ((3 & A(3,b) b2) with b 2 b2. Erazin
((, & Littrainigg set Lnj E'eestiigg set Otultuuiminn Ouj (prrains Press) and &full-mini has an overall non-increasing trend as the fan-out size 33 grows but small non-monotonic fluctuations exist. The posterior distribution Q represents the distribution of model parameters after training, and the hypothesis space denotes all possible models.
Remark 4. Theorem 3 reveals that increasing either the batch size or the fan-out size / improves the GNN generalization. This is because the role of b and /3 in GNN generalization is captured by the Wasserstein distance A (3, b), where larger A (3, 2, b) leads to poorer generalization performance. In Definition 1 the Wasserstein distance A (3, b) is proportional to the weighted sum of ofull-mini (i.e., the structural difference between full-graph and mini-batch graphs per node during training) over all training nodes, where 8full-mini decreases with either the batch size b or the fan-out size 3, though slightly non-monotonic fluctuations exist when varying (3.
Answering research question: Remark 4.1 represents how the batch size and the fan-out size characterize GNN generalization via the Wasserstein distance A (8, b). While full-graph training is expected to outperform smaller mini-batch settings, remain cautious about the degradation in generalization performance at very large batch sizes or fan-out sizes, as similar issues have been observed in DNNs (You et al. 2019 2017) We conduct an empirical study for further investigation.
In addition, we interpret an interesting observation, providing the implication for improving GNN generalization under memory constraints.
Obs.2: GNN generalization is more sensitive to fan-out size than to batch size. While increasing the fan-out size 3 and the batch size both help align the mini-batch with the full graph during training, 3 has a greater impact on the generalization by directly controlling receptive field of each training node. Based on Remark 4.1 this can be interpreted using the Wasserstein distance (8, b), which increases the weighted sum of 5 gfull.mini over all training nodes. A larger 3 can include unsampled but valid edges, turning zero terms train, into non-zero values in Sfull mini potentially causing slight non-monotonic fluctuations. In contrast, increasing b does not introduce these edges, as all training nodes are included during summation of 5fulllmini, With the more complex impact of (8 in A (3, b). we conclude that GNN generalization is more sensitive to fan-out size | than to batch size (see Appendix M Mfr for the detailed proof).
Implication for improving generalization. Under memory constraints, Obs suggests that adjusting the batch size b offers a more stable way improve GNN generalization, the batch size b introduces less non-monotonic fluctuations than the fan-out size B.
5 EMPIRICAL STUDY
We first explain the rationale for using the metrics (e.g., (leration-to-accuraay) in Sec. 5.1 We validate
Remarks 3.1 3.2 and Obs [ on GNN convergence (Sec. (.2)) and Remark 4.1 and Obs 2
on GNN generalization with the discussion about performance degradation (Sec. 5.3 We compare computational efficiency across varying batch sizes and fan-out sizes, answering our research question in computational efficiency (Sec. 5.4). Finally, we present an overall comparison of generalization performance between full-graph and mini-batch training after tuning batch size and fan-out size, yielding implications for tuning these two byperparameters (Sec. (.5).
Results overview. Non-isotropic impacts of batch size and fan-out size exist in model performance (i.e., generalization and convergence) and computational efficiency. Full-graph training does not always yield superior model performance or computational efficiency compared to well-tuned smaller mini-batch settings. Carefully tuning the batch size and the fan-out size in mini-batch settings often achieves more favorable trade-offs, such as faster convergence or better generalization.
Datasets and models: We conduct experiments four real-world datasets: reddit (Hamilton et al. 2017). ogbn-arxiv (Hu et al., 2020). products (Hu et al.) (020)) and bgbn-papers 100M (Hu et al. 2020). We train three representative GNN models: GCN (Zhang al. 2011), GraphSAGE (Hamiton et al. 2017) with mean aggregation, and GAT (Veličković et al. 2017) with 2 heads for
ogbn-papersT000 100M and 4 heads for the other datasets. See more training settings in Appendix N

---

Mini-Batch
Full-Graph
Timets)
50
Timetsi
100
Timets!
Roddit
Products
Reddit
Products
Roddit
Products
(a) Time-to-ace, 1w GPU
(b) Time-to-ace, bw2, GPU
(c)
Time-to-ace, bw CPU
# Iters
200
# Iters
200
# Iters
200
0
0
Reddit
Products
Reddit
Products
Reddit
Products
(d) Iter-to-ace, bw1, GPU
(c) Iter-to-ace, bw2, GPU
(f) Iter-to-ace, bwl, CPU
Figure 1: Time-to-acc and iteration-to-ace in mini-batch and full-graph training with varying band-
widths (i.e., two inter-GPU bandwidth values: bwl 1-infinity > bw2-900GB/s) and computational capacities (i.e., GPU with 40GB of memory and CPU with 512GB of host memory )
5.1 METRIC: TTERATION-TO-ACCUR..
We evaluate convergence performance using three metrics: iteration-to-low (i.c.. the number of iterations to reach target training loss), peratiin-to-accuraae (i.e., the number of iterations reach a target validation accuracy), and Since iteration-to-loss is from the theoretical analysis in Sec. and aiee-o-accuracy commonly used in empirical studies (Bajaj et al. 2024 Hu et al. 2020), do not provide further explanation.
(i.e., the time to reach a target validation accuracy).
Rationale for using ttrratio-to-accuraacy However, time-to-accuracy highly sensitive to hard- ware differences, entangling model performance improvement per iteration (e.g., accuracy) and computational efficiency (c.g., processed nodes per second). Thus, we additionally introduce iteration- to-accuracy, a hardware-agnostic metric, to capture this performance improvement during training.
To illustrate this rationale more clearly, we provide a simple, non-rigorous mathematical derivation, with details in Appendix N Let b denote the batch size, the fan-out size, and vi the iteration-to- accuracy. Suppose we compare two training setups under the same compute capacity but different bandwidths in distributed systems: full-graph setting (b 1000, 50, in 10) and mini-batch setting (b = 10, ,3 = 10, P1 = 10000). At high bandwidths (1000 nodes/s), the full-graph setting converges faster, 5.1 x 10y seconds, compared with 1.1 10th seconds for mini-batch training. In contrast, at low bandwidths (0.1 nodes/s), mini-batch training converges faster, requiring 2.1 x 106 seconds, whereas the full- full-graph setting requires 5.6 x 10 seconds.
Empirically, Figure I illustrates time-to-accuras and dieaatinntt--ceeee accuracy with two training ap- proaches under different inter- GPU bandwidth levels (i.e., bw bii-iiiin simulated by a single GPU with no inter-device communication; bw2=900GB/s, WPO NVLink 4.0 setup) and computation capacities (i.e., GPU and CPU). Detailed settings are in Appendix N For time-to-aconn teceuurccc mini-batch training underperforms full-graph training a single GPU but outperforms it on two GPUs or single CPU. In contrast, to-acunnt- remains consistent across hardware environments, with maximum variation of 41.28%, compared 2787.05 for time-to-accuracy.
Therefore, both mathematical and empirical examples indicate that time-to-accuracy cannot reliably generalize convergence performance across hardware environments, while the iteration- cictiionntt-ccco ao-accurycy is more reliable to guide carly-stage configuration decisions. For example, in a new hardware setup, practitioners can use known ieration-to-acccuaacy trends to narrow the range of batch and fan-out size, and perform short runs to consider hardware-speciffc runtime, thereby reducing tuning overhead.
5.2 CONVERGENCE
Empirical Validation of Remarks 3.1 3.2] and Obs Remark 3.1 and Obs [ are empirically validated by Figure and Figures 10 Appendix N which illustrate iteration-to-loss for three one- layer GNNs across four real-world datasets under varying fan-out sizes or batch sizes with different learning rates. In addition, Figure 4 in more general settings (c.g.. multi-layer GraphSAGEI further confirms Remarks 3.1 3.2 and Obs using iteration-to-los (see detailed settings in Appendix N). Due to complex optimization dynamics in deeper GNNs, Figure 4 shows minor fluctuations across varying batch and fan-out sizes, where the batch size and fan-out size increase until mini-batch training transitions into full- full-graph training.
Extended experiments using deration-to-aceurae and time-to-accuracy. To study model perfor- and time-to-accuracy
mance improvement during training, Figure illustrates
7

---

D927
.AG
20
D427
33737 55055 22410 3400 04704
0471
L0447
1923
LESSE 24600 2014
15637 31.30 2011 5000
4000
132000 10072
19991 20144 09647
0.611
1001
0.001
3,0005
0,003
Learning
Learning Rate
(a) Batch size, CE
(b) Fan-out size, CE
(c) Batch size, b. MSE (d) Fan- out size, MSE
Figure 2: Iteration-to-loss of one-layer GraphSAGE under CE and MSE across varying learning rates
and batch sizes or fan-out sizes for ogbn -rooucts.
Leariing Rate
50-30
54.35
Learning Rgte
54.26
DELIR
S0
6103
Rate
03.00 mi:s5 816
56.0
0.5k
10k
50
0.5k
2b
12k
50
Betch Sirw
Fan-out Stre
Baten
Stnw
Fanout Strw
(a) Products, Batch size (b) Products, Fan-out size (c) Reddit, Batch size
(d) Reddit, Fan-out size
Figure 3: Test accuracy of one-layer GraphSAGE under MSE across varying learning rates and batch sizes or fan-out sizes for ogbn-products and reddit.
Batch SRe
1k P54674622
10k
628
:B1
338
323 320
209
12
234
734
734
734
437
73
177
184184485
48
48
100k 415 11.53192200 249
150k 41.4 512 291 256 244
Bath
50x-25
215
226
196
196 196
192
Ratch
50k
10k
450
370
430
353
4.30
336
332
A30
327
4.30
Dateh
100K
39
39
full 394.313
1u1 234 209 195 189 183
full
319
39
36
34
10 15 50 all
15 Fan Size
10 20
25 all
25
50
100 all
Fan-out Size
Fan-out Size
Fon-out
Size
(a) Products, CE
(b) Reddit, CE
(c) Arxiv, CE
(d) Papers 100M, CE
18 959 943
/a/
3k 1001199 ves w22
1k: L11/174 8/9 1032 v4a
1k
10k 1034 969
10k (0k-19901100 960 952
5k (41883302233411
Betsh
100k
150k
124 055 936
227 030 962
921 892
Batch
100k 5331237 994 961
50k 1540112490 971 958 954
L30032400 36 36:422 16
151012641
1144
Datch
100k
450
646
full 22
956
920
full 2661238000199
961
full
459 459 451
5 10
20 50 all Fanrout Size
5 10 50 100 all
5 10
20 50 all
25 50 100 all
Fan-out Size
Fan-out Size
Fan-out Size
(c) Products, MSE
(f) Reddit, MSB
(g) Arxiv, MSE
(h) Papers100M, MSE
Figure 4: Iterationtto-loss of GraphSAGE under CE and MSE across varying batch and fan-out sizes.
Batch Size
Batch Size
Batch Size
1k 15-15.1 17.5 17.5777.777 15.5
150
200
E02
5500
2.7
20.5
150
180
190
170
100
5760 7800 110 10381016501510
2.1
26
25
13.7 13.5 17.
100k
150
150
170
190
390
100k 2708 15 132000000010111
100k
18
2.0
23
27
07
100K 20.7 22.7 18:182200 90
Tull 140
163
170
170
520
Tull 7900 2100 10000000000000
full
3.9
2.6
2.6
914
Tull 26.4
28.7 27.5
15
25 50
al
20 50 100 all
15
25
50 al
20 50 100 all
Fan-out Size
Fan-out Size
Fan-out Size
Fan-out Size
(a) Iter-to-ace, CE
(b) Iter-to-ace, MSE
(c) Time-to-ace, CE
(d) Time-to-ace, MSE
Figure 5: (leration-to-accuaacy and time-to-accune acccuracy of GraphSAGE under CE and MSE across varying batch sizes and fan-out sizes for reddit.
across varying batch sizes and fan-out sizes for reddit (see more datasets in Appendix N. showing unstable convergence trends with varying batch sizes and very large fan-out sizes (explained further in Sec. 5.3) This is because these two metrics capture both convergence and generalization performance due to the dependency on validation accuracy. Moderate fan-out sizes (e.g., around 15) are shown to balance convergence speed and computational efficiency (shown in time-to-accuracy) supporting the convergence acceleration implications Sec
5.3 GENERALIZATION
Empirical Validation of Remark 4.1 and Obs Remark 4.1 and Obs 2 are empirically validated by Figure 3 and Figures 15 of one-layer GNNs in Appendix NJ which illustrate test accuracies for three lnyer GNNs across four datasets under varying fan-out sizes or batch sizes with different learning rates. In addition, Figures 6 (b) in more general settings for ogbn-productt further confirm Obs 2 (see more datasets and details in Appendix N), as the variation of fan-out size induces more frequent and diverse shifts in test accuracies. Regarding Remark[4.1 Figure b) under MSE generally aligns with our theoretical prediction, while Figure 6(a) under CE further shows that performance degradation occurs with very large fan-out sizes (typically more than 15 on these datasets) or batch sizes (exceeding half of the training nodes). This degradation is more severe with fan-out sizes than with batch sizes. We justify our answer in Sec. 4 to the research question: full-graph training
8

---

Batch Size
58
1k
17.
78
70 08
78.46
78
78 29
78
73 06
17.39
17.53
3K
75 10
23.50
73.61
73.64
73.91
10k
78. 54
78.18
78
72 6.
73 23.03
10k
73 13:34
13.58
23.63
73.60
73.79
100k
78 98
78.21
78
77 82
77.49
100K
73.42
73.60
73.96
74.03
74.07
1.5kk
78
76:11 21
77
77.58
150k
73 33
23.05
23.26
83
73.95
78 73
(a) Test accuracy,
(b) Test accuracy, MSE
+307
5100
1k: 16 85
11.
10:14
8.72
8.80
6.42
16
58.10
83.67
17.99
42.57
16:38
100k
10k
011
05.95
080
82.0
89.24
006
75.52
272 69
72.36
23 75
5.65
30k
305 73
370 28
216 72
56.00
08
8717419
P25 83
24.53
1502
087
518 48
15
25
50
20
50
81
Far-out Size
Fan-out Size
(c) Throughput, CE
(d) Throughput, MSE
Figure 6: Test accuracies and training throughput (# nodes/s) of GraphSAGE under CE and MSE across varying batch sizes and fan-out sizes for ogbn-products.
Table I:
Best test accuracies of full-graph and mini-batch training of multi-layer GraphSAGE model without dropout layers after graph-basee hyperparameter tuning.
Datasets Reddit Ogbn-arxiv Oghn-products
Ogbn-papers I 100M
Full-graph 96.13
70.96
77.92
59.54
Mini-batch
96.32
71.16
78.80
58.52
does not always outperform the smaller mini-batch settings in generalization due degradation in generalization performance.
Understanding performance degradation. This degradation under CE arises the models tend to converge to sharp minima under large batch sizes (Keskar et al.) 2016). Since gradient variance decreases with larger batch and fan-out sizes, similar issues likely occur with large fan-out sizes. This degradation is more severe with fan-out sizes than batch sizes, as aggregating information from too many neighbors causes overfitting and weakens generalization. is not obvious under MSE, which produces flatter minima due to weaker gradients near prediction boundaries (Bosman et al. 2020).
contrast, such degradation
5.4 COMPUTATIONAL EFFICIENCY
Figures 6 (d) show the training throughput as the number of target nodes processed per second on single GPU for ogbn-products (see other datasets in Appendix N
Answering our research question: Computational Efficiency improves with batch size as fixed computations (e.g.. parameter updates) are distributed across more data, but becomes worse with larger fan-out sizes due to higher computational demands in message passing. Overall, mini-batch training achieves better computational efficiency than full-graph training.
Non-isotropic impacts of batch size and fan-out size in convergence, generalization, and compu- tational efficiency. Based on the observations in Sec. 5.2 5.4 the batch size and the fan-out size exhibit distinct, non-uniform effects across different aspects of GNN training. These non-isotropic impacts highlight the need for careful tuning of both hyperparameters to balance computational efficiency, convergence, and generalization.
5.5 FULL-GRAPH VS. MINI-BATCH TRAINING AFTER HYPERPARAMETER TUNING
Table I compares the generalization performance of full-graph and mini-batch training after tuning batch size and fan-out size via grid search. For the ogbn-papers 100M dataset, two hidden layers with hidden dimension of 128 used due to resource constraints, limiting representation capacity. The best accuracy from mini-batch training is within 1. 1.74% of full-graph training, suggesting that full-graph training does not consistently outperform well-tuned mini-batch settings.
100M
Implications for tuning batch size and fan-out size 3. Based on both the theoretical and empirical observations above, recommend keeping the batch size b below half of the training nodes and the fan-out size 3 under 15 for datasets with an average degree less than 50, to avoid generalization degradation and balance the trade-offs in computational efficiency and model performance.

---

RELATED WORK
The only existing comparison work (Bjjaj et al. 2024) between full-graph and mini-batch GNN training empirically evaluates overall performance but does not investigate the impact of key hyper- parameters (e.g., batch size and fan-out size) model performance and computational efficiency, thereby overlooking the trade-offs achieved by tuning these hyperparameters. Recent efforts (Yuan al. 2023, Hu al. (021) focus on these hyperparameters but remain limited. For instance, Yuan et al. Yuan et al.) 2023) lack theoretical support, consider only limited batch sizes and fan-out values that are far smaller than those of full-graph training, and overlook the interplay of batch size and fan-out size. Hu et al. (Hu et al., 2021) rely on gradient variance to explain the role of batch size but do consider fan-out size; thus their explanation conflicts with their empirical observations. Meanwhile, existing theoretical analyses of GNN training (Yang et al. 2023 Tang & Liu 2023; Xu al.] 2021] Verma & Zhang 2019 Yadati 2022 Awasthi al. [021] overlook key graph-related factors (e.g., irregular graphs, the difference between training and testing graphs in mini-batch settings) and the impact of non-linear activation on gradients. Furthermore, due GNN's
message-passing process, performance insights from DNNs Youu et al., 2019 Smith 2017: Golmant
iet al. 2018; Zou et al.) (2020a] Bassily et al.) [2018 Nabavinejad et al. 2021 Su et al. (0224) cannot
directly transter GNNs. We provide more comprehensive related work discussion Appendix O
CONCLUSION
We provide a comprehensive empirical and theoretical study of full-graph vs. mini-batch GNN training from the view of batch size and fan-out size. We provide novel theoretical GNN generalization analysis employing the Wasserstein distance, to study the impact of batch size and fan-out size. We empirically highlight the importance of iteration-based convergence metrics for hardware- -indeeednn evaluation. Our theoretical and empirical findings reveal the non-isotropic impact of batch size and fan-out size in GNN convergence and generalization. Finally, full-graph training does not consistently outperform well-tuned mini-batch settings in model performance computational efficiency. These insights clarify the trade-off's between full-graph and mini-batch training. We further discuss the extension (e.g., link prediction tasks) and future work (e.g., different activations) in Appendix
ACKNOWLEDGEMENT
This work was supported in part by collaborative research grant from Ant Group and grants from Hong Kong RGC under the contracts 17203522 (GRF), C7004-22G (CRF), C5032-23G (CRF), and T43-513/23-N (TRS).
10

---

REPRODUCIBILITY STATEMENT
For the theoretical results, all assumptions and complete proofs are provided in Appendices A [ with additional important discussions in Appendices F. H and P For the empirical study. com/ LIUMENGFAL AN -ANNIGFAN-1--- aaigggff/NN /GNN f graph mim_mmin wwwibatchhttraaaaaaa ning. Detailed experimental con- figurations and additional experiment results represented in Appendix N and all datasets properly cited the main text.
the code is publicly available via github link provided in the abstract: https://githut:
REFERENCES
Pranjal Awasthi, Abhimanyu Das, and Sreenivas Gollapudi. A convergence analysis of gradient descent on graph neural networks. Advances in Neural Information Processing Systems, 34: 20385-20397, 2021.
Saurabh Bajaj, Hui Guan, and Marco Serafini. Graph neural network training systems: A performance comparison of full-graph and mini-batch. arXiv preprint arXiv:2406.00552 2024.
Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non-convex over-parametrized learning. arXiv preprint arXiv: 18/102554 2018.
Anna Sergeevna Bosman, Andries Engelbrecht, and Mardé Helbig. Visualising basins of attraction for the cross-entropy and the squared error neural network loss functions. Neurocomputing. 400: 113-136, 2020.
Zhenkun Cai, Xiao Yan, Yidi Wu, Kaihao Ma, James Cheng, and Fan Yu. Dgel: An efficient communication library for distributed gnn training. In Proceedings of the Sixteenth European Conference on Computer Systems, pp. 130-144, 2021.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint 1rXiv:1710.10566 2017.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling, arXiv preprint arXiv: 1024, 2018.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery data mining, pp. 257-266, 2019.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On the importance of sampling in training gens: Tighter analysis and variance reduction. arXiv preprint arXiv:2103.02696 2021a.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34:9936-9949, 2021b.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. Advances in neural information processing systems, 29, 2016.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes pwer-parameterized neural networks. arXiv preprint arx1v:1810.02054, 2018.
Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in neural information processing systems, 32, 2019.
Ran El- Yaniy and Dmitry Pechyony. Transductive rademacher complexity and its applications.
Journal of Artificial Intelligence Research, 35:193-234, 2009.

---

Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovee. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. International conference on machine learning, pp. 2294-3304 PMLR, 2021.
Vikas Garg, Stefamie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pp. 3419-3430, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272, 2017.
Noah Golmant, Nikita Vemuri, Zhewei Yao, Vladimir Feinberg, Amir Gholami, Kai Rothauge, Michael W Mahoney, and Joseph Gonzalez. On the computational inefficiency of large batch sizes for stochastic gradient descent. arXiv preprint arXiv: 129441, 2018.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Johann Hauswald, Yiping Kang, Michael A Laurenzano, Quan Chen, Cheng Li, Trevor Mudge, Ronald G Dreslinski, Jason Mars, and Lingjia Tang. Djinn and tonie: Dnn as service and its implications for future warehouse scale computers. ACM SIGARCH Computer Architecture News, 43(3S):27-40, 2015.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph henchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18 18-22133, 2020.
Yaochen Hu, Amit Levi, Ishaan Kumar, Yingxue Zhang, and Mark Coates. On batch-size selection for stochastic training for graph neural networks. 2021.
Tim Kaler, Nickolas Stathas, Anne Ouyang, Alexandros-Stavvo Iliopoulos, Tao Schardl, Charles E Leiserson, and Jie Chen. Accelerating training and inference of graph neural networks with fast sampling and pipelining. Proceedings of Machine Learning and Systems, 4: 4:172-189, 2022.
Leonid V Kantorovich. Mathematical methods of organizing and planning production. Management science, 6(4):366-422, 1960.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On butge-bacch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: (02.66699..888 2016.
Vladimir Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Transactions on Information Theory, 4705):192 2001.
Shen Li, Yanli Zhao, Rohan Varma, Omkar Salpekar, Picter Noordhuis, Teng Li, Adam Paszke, Jeff Smith, Brian Vaughan, Pritam Damania, et al. Pytorch distributed: Experiences on accelerating data parallel training. arXiv preprint arXiv:2006. 15704, 2020.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances neural information processing systems, 31, 2018.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach generalization bounds for graph neural networks. arXiv preprint arXiv:2012.07690, 2020.
Yucong Lin, Silu Li, Jiaxing Xu, Jiawei Xu, Dong Huang, Wendi Zheng, Yuan Cao, and Junwei Lu. Graph aer-parrameteiizatio:: Why the graph helps the training of deep graph convolutional network. Neurocomputing, 534:77-85, 2023.
Chaoyue Liu, Dmitriy Drusvyatskiy, Misha Belkin, Damek Davis, and Yian Ma. Aiming towards the minimizers: fast convergence of sgd for overparametrized problems. Advances neural information processing systems, 36, 2024.
12

---

Tianfeng Liu, Yangrui Chen, Dan Li, Chuan Wu, Yibo Zhu, Jun He, Yanghua Peng, Hongzheng Chen, Hongzhi Chen, and Chuanxiong Guo. Bgl:gpu-efficienn efficient gnn training by optimizing graph data i/o and preprocessing. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pp. 103-118, 2023.
Shaogao Lv. Generalization bounds for graph convolutional neural networks via rademacher com- plexity. arXiv preprint 10214 2021.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks. Advances in Neural Information Processing Systems, 34: 14:1048-1000 2021.
David McAllester. Simplified pac-bayesian margin bounds. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COI.I/Kemel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pp. 203-215, 2003.
Vasimuddin Md, Sanchit Misra, Guixiang Ma, Ramanarayan Mohanty, Evangelos Georganas, Alexxn. Alexan- der Heinecke, Dhiraj Kalamkar, Nesreen K Ahmed, and Sasikanth Avancha. Distgnn: Scalable distributed training for large-scale graph neural networks. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-14, 2021.
Hesham Mostafa. Sequential aggregation and rematerialization: Distributed full-batch training of graph neural networks on large graphs. MLSys, 2022.
Seyed Morteza Nabavinejad, Sherief Reda, and Masoumeh Ebrahimi. Batchsizer: Power- Power-performance trade-off for dnn inference. In Proceedings of the 26th Asia and South Pacific Design Automation Conference, pp. 819-824, 2021.
Pranjal Naman and Yogesh Simmhan. Performance trade-offs in gnn inference: An early study on hardware and sampling configurations. 2024 IEEE 31st International Conference on High Performance Computing, Data and Analytics Workshop (HiPCW), pp. 173-174. IEEE, 2024.
Kenta Oono and Taiji Suzuki. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. Advances in Neural Information Processing Systems, 33: 33:18917-18930, 2020.
Jingshu Peng, Zhao Chen, Yingxia Shao, Yanyan Shen, Lei Chen, and Jiannong Cao. Sancus: sta le ess-aware omm nication-avoiding full-graph decentralized training in large-scale graph neural networks. Proceedings of the VLDB Endowment, 15(9):1937-1950, 2022.
Boris Teodorovich Polyak. Gradient methods for minimizing functionals. Zhurnal vychislitel noi matematiki matematicheskoi fiziki,, 3(4):643-653, 1963.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The rapnik-chervonee dimension of graph and recursive neural networks. Neural Networks, 108:248-222 2599,229,,000 2018.
Zhihao Shi, Xize Liang, and Jie Wang. Lme: Fast training of gnns via subgraph sampling with provable convergence. arXiv preprint 4.04002300200 2023.
Zhihao Shi, Jie Wang, Zhiwei Zhuang, Xize Liang, Bin Li, and Feng Wu. Accurate and scalable graph neural networks via message invariance. arXiv preprint arXiv:2502. 19693, 2025.
SL Smith. Don't 't decay the learning rate, increase the batch size. arXiv preprint arXiv: 171::10110009 2017.
Junwei Su and Chuan Wu. On the topology awareness and generalization performance of graph neural networks. In European Conference on Computer Vision, pp. 73-89. Springer, 2024.
Junwei Su and Chuan Wu. non-asymptotic convergent analysis for acored-based graph generative model via a system of stochastic differential equations. arXiv preprint arXiv:2508. 14351, 2025a.
Junwei Su and Chuan Wu. On the interplay between graph structure and learning algorithms in graph neural networks. In Forty-second International Conference on Machine Learning, 2025b.
Junwei Su, Difan Zou, and Chuan Wu, Improving implicit regularization of sgd with preconditioning for least square problems, 2024. http:/tpsss///aaii..rr//////////
08585
13

---

Huayi Tang and Yong Liu. Towards understanding generalization of graph neural networks. In International Conference on Machine Learning. pp.
2023.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity: festschrift for alexey chervonenkis, pp- 11-30. 2015.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
Saurabh Verma and Zhi-Li Li Zhang. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1539-1548, 2019.
Cheng Wan, Youjie Li, Ang Li, Nam Sung Kim, and Yingyan Lin. Bns-gen: Efficient full-graph training of graph convolutional networks with ceriitionn-rralleliin and random boundary node sampling. Proceedings of Machine Learning and Systems,
2022a.
Cheng Wan, Youjie Li, Cameron R Wolfe, Anastasios Kyrillidis, Nam Sung Kim, and Yingyan Lin. Pipegen: Efficient full-graph training of graph convolutional networks with pipelined feature communication. arXiv preprini arXiv:2203. 10428, 2022b.
Xinchen Wan, Kaiqiang Xu, Xudong Liao, Yilun Jin, Kai Chen, and Xin Jin. Scalable and efficient full-graph gnn training for large graphs. Proceedings of the ACM on Management of Data, 1(2): 1-23, 2023.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 2018.
Keyulu Xu, Mozhi Zhang, Stefanie Jegelka, and Kenji Kawaguchi. Optimization of graph neural networks: Implicit acceleration by skip connections and more depth. In International Conference on Machine Learning, pp. 11522-11602, 2021.
Naganand Yadati. A convex formulation for graph convolutional training: Two layer case. In 2022 IEEE International Conference on Data Mining (ICDM), pp. 1281-1286 IEEE, 2022.
Chenxiao Yang, Qitian Wu, David Wipf, Ruoyu Sun, and Junchi Yan. How graph neural networks learn: Lessons from training dynamics in function space. arXiv preprint arXiv:2310.05/000 2023.
Yang You, Aydin Bulue, and James Demmel. Scaling deep learning on gpu and knights landing clusters. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-12, 2017.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint arXiv: 1904.0002, 2019.
Hao Yuan, Yajiong Liu, Yanfeng Zhang, Xin Ai, Qiange Wang, Chaoyi Chen, Yu Gu, and Ge Yu. Comprehensive evaluation of gnn training systems: A data management perspective. arXiv preprint arXiv:2311.13279, 2023.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint arXiv: /0ti:://97.099333 2019.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. Graph convolutional networks: comprehensive review. Computational Social Networks, 6(1):1-23, 2019.
Guoyi Zhao, Tian Zhou, and Lixin Gao. Cm-gen: A distributed framework for graph convolutional networks using cohesive mini-b batches. In 2021 IEEE International Conference on Big Data (Big Data), pp. 153-163. IEFR, 2021.
14

---

Da Zheng, Xiang Song, Chengru Yang. Dominique LaSalle, and George Karypis. Distributed hybrid cpu and gpu training for graph neural networks on billion-scale heterogeneous graphs. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 4582-4591, 2022.
Rong Zhu, Kun Zhao, Hongxia Yang, Wei Lin, Chang Zhou, Baole Ai, Yong Li, and Jingren Zhou. Aligraph: comprehensive graph neural network platform. arXiv preprint arXi::1902.08730 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint 1r1iv: 1008888, 2018
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. Advances in neural information processing systems, 32, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine learning, 109:467-492, 2020a.
Difan Zou, Philip M Long, and Quanquan Gu. On the global convergence of training deep linear resnets. arXiv preprint arXiv:2003. 2020b.
15

---

THE USE OF LARGE LANGUAGE MODELS (LLMS)
We used large language model (LLM) only as a general-purpee pprrpss writing assistant to aid in grammar checking and polishing the writing. The LLM did not contribute research ideas, experiment design. theoretical analysis, or result interpretation.
A NOTATIONS
Table 2: Notations Number of nodes of the entire graph
Perain
Flyst
Number of nodes in the training set / the testing set
Temin
The minimal value between training and testing sets
X/x: Xt
Node feature matrix / i-th row of node feature matrix
yi
Ground truth label of node i
Vi /
Y
Ground truth label in one-hot form / estimated outcomes of node
T
feature size
b
Batch size
B
Fan-out size
A mini
/
A
lull
Adjacency matrix in each mini-batch/ fulllgraph training iteration
train
m,anana
inlull
Diagonal in-degree matrices in each mini-batch/ / full-graph training iteration
train
main
D
mini
full
Diagonal out-degree matrices in each mini-batch full-graph training iteration
Iruin
train
A Arain / A
Tull
Normalized adjacency matrix in mini-batch/ / full-graph training iteration
Irain
a wain. 1
mini
/
ahill
i-th row of normalized adjacency matrix in mini-batch / full-graph training iteration
Agea/ &eest
Normalized adjacency matrix / i-th row of Normalized adjacency matrix in testing set
Wmin Willl
Learnable parameters of the GNN under mini-batch/ full-graph training
w w.mmm wh!ll
i-th row of parameters of the GNN under mini-batch/ full-graph training
Wmini /Will*
Ground truth of learnable parameters Wmmin Will
w
mimi w full"
i-th row of ground truth of learnable parameters Wimm Willl
h
Hidden size
K
Number of label categories
(-))
ReLU activation function
((-)
Dual activation function
Lirain /
Lernin (-)
Expected/ / empirical training risk
L
mini
/ L (-)
Expected/ / empirical training risk in a mini-
Lreat
/ Lrese (-)
Expected/ / empirical testing risk
G
Stochastic gradient in mini-batch training
1
Learning rate
P/Q
Prior Posterior distribution of model parameters
U(-)
Expected loss discrepancy between training set C and testing set Z
8(-)
Distance function
0
Covariance
To easily distinguish the training risk between full-graph and mini-batch training, we rewrite Lurin' (-)
and Lurain (.) as fill (-) and full (.) under full-graph training. Similarly, we rewrite the gradient
V L L (-) as V i full
Lirain (-) during full- training, and the stochastic gradient G as V i (-).
B PROOF OF CONVERGENCE THEOREM IN FULL-GRAPH TRAINING WITH MSE
In this section, we provide the proof of the convergence theorem in full-graph training with MSE. We consider multi-class node classification tasks using a oound GNN trained with the MSE, defined
as 1 (W, a sلull ) 11 V= The ground truth label y: is rewritten y; RR1X in the one-hot
16

---

form, where K 2 2 the number of label categories. The final output of the GNN model is given by y, = 2, a (a Irain. XWT). where the ReLU function is modified as ((x)) = / max (z, 0).
Note that 1/2 in the MSE function and 2 in the ReLU function are introduced to simplify the proof. The hidden dimension h becomes K. Note that The rows of W are initialized independently from Gaussian distribution N (0, x2I).
We decompose the analysis of GNN optimization dynamic into three steps.
Step 1: Reformulating loss and gradient expressions on irregular graphs. We decouple the activation function from the aggregated node features. For instance, extract the aggregation from the ReLU function by reformulating squared loss terms.
Bounding the norm of gradient. Based the reformulated loss and gradient expressions, aim to quantify the magnitude of optimization updates by bounding the gradient norm, facilitating convergence analysis. This can be achieved by leveraging the PPllykk 1963), where the squared norm of the gradient is lower bounded by the loss value scaled by factor.
Step 2:
(PL) inequality
Step 3: Bounding the number of iterations to Convergence. We first leverage the smoothness of the loss function derive a per-iteration inequality relating loss reduction the gradient norm, and then accumulate these iteration-win -wiee inequalities over GD updates to obtain an upper bound on the number of iterations required for convergence.
B. ASSUMPTIONS
Assumption B.1. The node feature x; is drawn i.id from N (0, I,xr) for all i in the graph, with [X| S Cz for constant C² O.
Assumption B.2.
The rows ground truth parameters satisfy || = for all i {1...., h}.
Assumption B. specifies the distribution of node features and bounds the norm of the feature matrix, and Assumption |.22limiss limits the norm of ground truth parameters for the GNN model. These assumptions also adopted in the GNN convergence analysis regular graphs (Awasthi et al.) 2021). We emphasize Assumptions B.I and B.2 are introduced to simplify the proof. Note that Assumption B.2 can be relaxed be that [|w;]] lower and upper bounded by some constants instead of fixing [w ll2 =
Definition B.3
(Dual activation (Daniely et al. 2016)) The dual activation of is the function â [-1, + IR defined as ā (0) E (z) a (v)]. where x and are jointly Gaussian random variables with mean zero, variance one, and covariance B.
Definition B.3 demonstrated that dual activations hold continuity over the interval [-1, 1] and convexity within the range [0, 1].
B.2 EXPRESSIONS FOR AND GRADIENTS.
While our ultimate training objective remains empirical risk minimization, we analyze the optimiza- tion dynamics of MSE using its expected risk formulation on node feature distribution. This done to simplify the proof, as expected risk offers cleaner mathematical structure and does not affect the graph structure. Although this approximation is more accurate in the large-sample regime, we adopt here modeling tool to study the impact of batch size and fan-out size in convergence, even when analyzing small-sample settings.
Expression for MSE loss: j E (1,...,h) as:
We first begin by writing equivalent expression of L filll (wfill) with
(w-gatt ))² 27
full
full
(E
Σ
full X
(w
+
full Armin,
X
Meemin
(1)
XX (w.Jalr) 7
2E
stull Aurasn,
X
fall
Areann
Li,
17

---

We next compute expressions for each of the three terms above.
(wo(all)
Aimin,
Menin
A X (ollll))
Pisa
a
Temin
c,k=1
Phosio
B[[
fill
Σ PEj
A
A
Train
Ydemin
2,
full aggain.
X (ww!all) T
T X (wofall)
A full
/|sofalll
A full 1 )₂ ||wffall
wrflll
Musinn
Pir
Teemin
1,8mm
full
where the penultimate equality follows Definition i A j. efull to denote the amount of common messages between node and node j at given training iteration, and we define:
B.3
We use Púj = if = j and Pi if
full eid /
[ full
Σ Pisō
Sfull
(3)
Purain
i,fm1
A train )
(A (A
(4)
Similarly, we get the second term as:
Thean
(w-fall>) ))
27 =
full 11
a agrain
X
Iulll
(5)
Terrann
We simplify the last term as:
IE
Tizaais
Pike
A
fall Prrain,
X
(w.(ul)
T
full Brrain
X
(o-fall
full
Merzin
B
w
Σ
Pur
fill unin
A
train 1)
Merain
(wofilly
(wainnn T
(6)
a Araan
Again
o
A full
/wwal||
full train
train
Teriie
(w)
T w tun
fill
Gill
Ciik
yral S.k.
w
w
Veemain
Therefore, we have the expression of full (wrllll as:
(|w
fall + ||
full
1
2
full
W
Fall
Tunis
P
full goun
(w
w
(7)
fullll
Trzain
18

---

It is easy that if whfl is the initial value of willl with j {I....,h) then each subsequent iteration will be a linear combination of w full w
j.0 and wh"l Hence we can assume that wh
Bllll full + الtي w wffll"". Then rewriting the loss in terms of &f اfull and recalling that |w]"l| 1 we get the simplified expression of fulll (wfill):
fullt, where w is a fixed unit vector (depending on the initialization) orthogonal
I Ltrain
fuuull praul)
1 2 (oout)) + ((uteut) 2 +1) paul
V(obun)) + (n5ffutt) 2ydull (
(8)
where we define:
r full
Piyō
Fflll
elyl / 6
Votag
(9)
Thrain
(ofoll) + (usfall)
Expression for gradient: with respect to o. w.
We compute the gradient of the objective with respect to or equivalently
dL mi
mm Joffull
B full yru
full full
(olin)) + (ublomt)
(alstin (ashuit) + (wotuiy)
full
full
> 5
Pso ei.jo'
23
(dramyz + (w)ma))
gill
(10)
cf fill p full
(ddhi)) (ebifili)
full
full Psy eig Snap
2i.3
Muzin
(astuit) 2 + (nstuny)
v (dffuit) + (wyra)) v goul
(uS =
= fall full
+ (absul)22 + (1
(dfmm)) (eisanly
where in the second equality o' ā' and ã¹ /21 function, and we define:
0) -sttp(()), Sstep is the step
Deran
full Pi.
sfull
full Pigei Ostep (olut)) 2 + (znsurt))
(11)
7ltrann
+==1
/ (afull
Similarly, we have:
ar. full
follll
2 full
Gfull f (offuli) 2 (usful)) 2.
full
(12)
Jullull
(dfwn)) + (sutun)
B.3 THEOREM B.
Theorem B.4. (Convergence of Full-graph Training with MSE) Suppose Whill are generated by Gaussian initialization. Under Assumptions B.
and B.2 if the maximal degree satisfies
Chill & dmax S Chilll n for some constants
(0, then with high probabil- S e, provided that the number of iterations
full
ity, the truining loss satisfies Terain (Wfell A
train
= 0 ( (1 162 di log (1i6-11) for any E (0, 1) under the full-graph GNN training.
19

---

B.4 PROOF OF THEOREM B.4
Lemma B,5
full
1 S
Pfull I
fall train
1[1, and |M S
where n maiin daii S
Irain
|| train, 1 1 I Trainn mmax-
Lemma B.6 If wfell 2.0
(0, 21) and the learning rate 1) E (0, का. then with probability at
least e0)(), it holds that for > v (difal))² (v/fal)) 2 C, and v (1oful)) + (v)fuil) 2
for all / 2 1, where C = O (KVTT is positive constant.
Lemma B.7 If wflll (O, I) and the learning rate n (0, 6 sa then for all t 2 and any
C1 E [0, 1] such that (ofill shllll = (1 - C1) (oftlll w.f.ll + C1 (of v/ we have that,
Amax
2 I Jull
ccrain ( (لسووي w s C
where Amax is the maximum eigenvalue of the population Hessian denoted by 2 22 full and C2 1 + + (KVT)) + (1))
(øfill abfull).
"rain
positive constant.
Lemma B.8 will ((0 I) and the learning rate v E (0, T. then with at least 1/h2, holds that for all constant.
C3 log (log h), (offil)) + (uifall) 2 2 o (1), where C3 > is an absolute
Lemma B.9
full 3.0 ~ ((0 I) and the learning rate 7 E (0, 6ा|
then there an absolute con-
stant C3, such that for all 2 C'3 log (log ft), either |esSall|| -
2 and / ( 2 + (wifalt - S
2h
have that
V [ull
fulll full 1|
p full full
(dhalll
2/
full
where full C4ch 2 2m Pfill and C4 is positive constant.
Proof of Theorem B.4:
We analyze an arbitrary j E (1,.... h} and the iterates of the corresponding we have from Lemma B.7 that the smoothness parameter C of the loss
whlll vector. Setting function is
dull < C²² = 4 11 / 2- + +0(1))
(13)
Hence, for any O,
(.++1)
<
Full train
Wie
Full
+ V
full urain
full
w..e)
Full
full
ww 2.c+1
j.t
T, full
/itran
(w/ii!)
r
full Arainn
(wi,e] ||²
C
V
Tram
(w
||
(14)
2
I| (1
Cull
r fill Lrrin
(w3ee)
Gill
V r
fill train
Gill
2
Chull
By Lemma B.6 we know that 17 (0, Jaा Using Lemma B.5 we first assume that 6x
< dans
S
Coda and wan
6Cc
n train
where Co < a positive constant. Then, we set e
Gxdan
We are going
Cod
Co
to prove E
is still within the range (0, )ाा and
20

---

For the right side of the range, we have 6xdan 6vi with the positive constant Cg. Moreover, we have:
due to I
dmax. For the left side of the
Cad a
range,
Codmuu
Codmas 11
6rddmax
6dmaxx
(15)
O.
6dmmn
6dlmax
Coda 8ni
With 7 E
we have:
6rdda
C
n
(16)
Greemaa
Furthermore, using Lemma B.9 we have
(w (W)++1) < Luuin
full (hit
(1 1//4 fulll)
< L (w).0) - 1732 full
(17)
Then we have:
h22 E log
(18)
where C, a positive constant.
Moreover, have:
C4 Co
C4Cadmaxe
full
(19)
nn train 2
22 112
Irain
Hence, we have T O
Aimm 22
4a log
ed
After T time steps, we either have L fullll
(w S 5, that s/!aall < and (of 2 + (wifill) 15
26 The latter implies that ||w/ whu ||wftll
full" j
< f. In addition, is easy to see that I, full
(w/full) S
irain
w 1|2. Hence, if the latter happens, then full (wfill) S f. Hence full (Wfill) S
This completes the proof.
C PROOF OF CONVERGENCE THEOREM IN MINI-BATCH TRAINING WITH MSE
In this section, provide the proof of the convergence theorem in mini-batch training with MSE of Section 3 We consider multi-class node classification tasks using a one-round GNN trained with the MSE, defined as / (W, (arin, = llý: yi 1 The ground truth label yı is rewritten as Y: TR. x in the one-hot form, where K > 2 is the number of label categories. The final output of the GNN model is given by ÿ: Z,
XWT where the ReLU function is modified
(x) V max (xx 0). Note that 1/2 in the MSE function and v2 in the ReLU function introduced to simplify the proof. The hidden dimension h becomes K. The rows of W are initialized independently from Gaussian distribution N (0, x²1).
We decompose the analysis of GNN optimization dynamic into three steps, similar to Appendix
C.1 ASSUMPTION
We still use Assumptions B.I and B.2 in mini-batch settings for training data and the ground truth.
21

---

C.2 EXPRESSIONS FOR LOSS AND GRADIENTS.
While our ultimate training objective remains empirical risk minimization, we analyze the optimiza- tion dynamies of MSE using its expected risk formulation on node feature distribution. This is done to simplify the proof, as expected risk offers a cleaner mathematical structure and does not affect the graph structure. Although this approximation is more accurate in the large-sample regime, we adopt it here as a modeling tool to study the impact of batch size and fan-out size in convergence, even when analyzing small-sample settings.
Expression for MSE loss: We first begin by writing an equivalent expression of L p (w]in)) with
j E (1....,k), kk.. We can assume that willi otmin / + e/:mini w where w is fixed unit vector (depending on the initialization) orthogonal to wittii.. Then rewriting the loss in terms of Mmini
yimini and recalling that ||wjin 1 we get the simplified expressions of L irain (w]pin) and
||
grain
(
mini train
mmins 1 ((snin))
B miii
2
(M)min) 2 +1
(dimini) 2 + (niminn Syamini r puini
(20)
2
and
L
@
miii
A Arrin
1
(( (c0 mini) + (msmmnn))
+1) fulll (asmine wp mini
Aram
2
(21)
(dmmini
(giminn 22 yptill (ommin yimin
A mini
where we simplify pfull respectively, and we define:
miiin
4/
mini
and full miiii mimi
mini A
ffull-mini and full-mini
train
train
mini Lin Famini
mini
Pijō
gmini
(22)
AJ==
I full-mini
I
full
(omini
mini
mini Agrain
piyo
gmini
(23)
Parain
gmmni
5==1
b mini
miii
Pijō
Ormini
(24)
(omini) + (usmini)
gamin
T full-mini
- (omin)
v mini
A mini
miini
(25)
Pejō
Li gmini
amini
(ominn 2
(1hmini) y2
k.) m1
0
Ammin
(A
(26)
where we use P:j = i j j and Pij = 0 if # j. o between node and node j at given training iteration
mini to denote the amount of common messages
Expression for gradient: We compute the gradient of the objective with respect to w or equivalently with respect to d. vb.
0L mini
mini
minn
Mini
miii = mini
mini mini mini
of
+
(27)
admii
(dmmin)
(zismins)
(gminn) 2
+ (simiin))
and
ar,uull full miin
z6 mini
A mini train
mimin full-mmii
(1smin)) =full-mini
mini full-miiil
+ (smini) + (1)min)) 2 (28)
aemini
V (omini 2 (v/mminii²
22

---

where we define:
mini
mnini
mini
Σ
Pij
Pi,
mini
dsee
2
(29)
(omini) 2 (vimini)
Ommii
fJ=1
minl-mini
mini
mini
A Arran
Biini
(30)
Pijlis Sssep
mini
Di.y Omiga
Thtrain
(ddminy + (elmmis))
Similarly, we have:
Ør. mini
mini
mini
etmin y-mini
Gmial 2 mmmiigmmii
mini punni
(31)
anjminn
(cimini) 2
(1)miini)
(dimin))
(gimmini)
and
OL full
mini
mini train
ey mini y full--mini
df mmin mini miniii full-mini (dmini)
mini full-miit full-mini
(32)
Oniminni
(ominn) 2 (1iamini)
(giminn)
C.3 PROOF OF THEOREM 1
Lemma C.I
75 Irain,
1
Pimini "
Dfull-mini
Á 1 tramn
|
Nguin and | S
Tfull-mini, where 62 <
mini A
1 || S 63.
f
main,
Lemma C.2 If w mini J.0
~ N(0, I and the learning rate f) E (0, Buipull, l. then with probability at
least 1 - -0(), it holds that for all t 0, v (ømini) + (1omini) s C, and / (dmini) 2 + +(1 (u.-min))
)²
0 for all t 2 1, where C = = + O (KVFF is a positive constant.
Lemma C.3 If wiiii ((, I) and the learning rate yJ (0, GrT then for all 2 1 and any
C1 [0, 1] such that (aiinni mmin
C1) miii
(iminn))
C1 (ø amiui)
) have that,
Amax 2 اuul (cimi miii A mini
)) S C21 miil
where
Amax is the maximum eigenvalue of the population Hessian denoted by 2 f (gmini miiii
mini train
and C2 4 (1
+ 1 (N)))) is positive con-
stant.
x(0 and the learning rate Th (0, 6xT then with at least 1 1/h², it holds that for all 2 C3 log (log h), / (ofinn)) + (wsmin)) o (1), where C3 > is an absolute constant.
Lemma C.4 If mini
Lemma C.5 If 5.0
(O, and the learning rate E (0, 6 J.
then there is cb
an absolute constant Cs, such that for all & C3 log (log h), either viminil < (omini) 2 + (w)mini)
and
2h
1||
24 we have that
V Lull
(omini
mini
tran
||
2 44
mini
I I
mini
mini
mini train
where y.minn Cich ffull-miii and C4 is positive constant.
23

---

Lemma C.6 [Lemma G.2 in (Du et al. 2018) Regarding n random variables u1,.... Un satisfying
Σ 4 = 0. Let E in] denote a subset of [n] and [ = b I n, the following holds,
E
E
FEB
Proof of Theorem
For any
O, taking expectation conditioning on wiiii gives:
Lemin W.r++1
A Aqain
J.t
full Lirain
Wiet
mini
A
mini Arainn
V Litrin
Wi
mini Auainn
B
mini (wi++1
5.t
Oini
mini
(33)
Caiin
+
18
w
mini
5,441
5,1
[w 3,2
Furthermore, using Lemma C.6
have:
B
W
3,
mini
mini
w
mini
y.d
1/6 E
Lirain
mini
Wie
mini
mini Auaain
3.
<n/
V
Litrain
Woit
A
mini train
Limain
(
Amiui
minn
(34)
full iraiin
L
W
mini
Anni
A minss
2
1|
V Lyain
W
mini
mim
V
Legain
w
mini
mini train
Alarainb
Sm
22imain
V
full Leuain
mini
A mini
11¹)
b
Moreover, we have:
T
tran
full
mini
3,0
A mini
train
mini
3,0+1
mini J.r
|w mini
V
wae
A
T
E W
mini 31++1
(35)
Tagain
mini
Hence, we have:
(w 3,
mini
mini
w..e
mini
Lirain
Wi.t
mini
A
TJe
V Linin
W..t
Aminn
||
Omini
Turnio
me
V full
w
A
arain
||
(36)
I| (1
Cymini
fill
(w.t""
mini
Agrai
T/
V Linin
Wi.t
mini
A mini
Agai
!/|
Onisi
By Lemma C.2
we know that 77 E (0, i Using Lemma C.1 we first assume that
S
6
Ca m
3
where Co < 8 is positive constant. Then, we set T/ E
We are
6Cc
going to prove v E
Cofta
b
is still within the range (0, 5x] and Coff3
Whamn 63 <
Kumi 1 on 0.
Bx Brimii
24

---

For the right side of the range, have 6n
due to r 1 and
Gar Magan
6xIqu
b S Munin- For the left side of the range, WhiiltZ
Oz
with the positive constant Cs- Moreover, we have:
Cofs
C
6 Sreain
Thuai 6
Meraiin
63
h
(37)
0.
7
63
68
Caf
With E
we have:
Nmmm b Gn Grr
Comin Breain
Caninii
6 1.
(38)
Furthermore, using Lemma C.5
we have
L Limin (W Wi+++
mini
A miniy
S Litain
mini jit
(1 - Ta mini A
mini Arrzin
mini
W.D
mini
Amaii
II The Hr, mini)
(39)
S I mini mini
W J.D
A mini Arain
? mi
where the last inequality can be proved: f(x) log(1 x) concave function on < we have { E x.)) 2 1. - f(z;), which can be then, for 0 < 2; < with i = {1....,n} n),
written as log(1 Σn x.) 2 1 - log(1 2;). Therefore, we have (1 1 Σm 2;)" 2 [T 2;).
Then we have:
112
T < Co
(40)
E
7r
T
where C7 is positive constant.
Moreover, we have:
1
Σ
U
mini
1
C.Cogge
(41)
T
n Remiuh h
C.Cog3e
n m b 122
2 r8
Hence, we have T -
log 4²
After time steps, we either have full
mini J.t.
À mini tain
S i. or that v.
<
< and (dmin)
2
24
(viminn)
1
The latter implies that mins
mini j.t w 112. Hence, if the latter happens, then full (w. A Amini
* || S f. In addition, it is easy to see that
2K
full
mini J.t.
A Amann
S w.
<
j.t
f. Hence full (W
qiii
S..
This completes the proof.
D PROOF OF CONVERGENCE THEOREM IN FULL-GRAPH TRAINING WITH CE
In this section, we provide the proof the convergence theorem in full- full-graph training with CE. To simplify the analysis, we focus binary node classification using one-round GNN trained with the
25

---

CE, defined as (W, a log (1 + (xp(-))))). The final output of the GNN model is given by 1/ 2,V = (rainn XWT vT, Vi E training set, where v E (-1,+1) E Rixh is the fixed output layer vector with half 1 and half -1. The rows of W are initialized independently from Gaussian distribution N (0, I2).
We decompose the analysis of GNN optimization dynamic into three steps.
Step 1: Reformulating loss and gradient expressions on irregular graphs. We represent the ReLU function implicitly using a position-wii wise 0/1 indicator matrix that can directly multiply the aggregated node features.
Bounding the norm of gradient. Based on the reformulated loss and gradient expressions, we aim to quantify the magnitude of optimization updates by bounding the gradient norm, facilitating convergence analysis. We can bound the Frobenius norm of the gradient by the average individual node-level gradients.
Step 2:
Step 3: Bounding the number of iterations to Convergence. We first leverage the smoothness of the loss function to derive a per-iteration inequality relating loss reduction to the gradient norm, and then accumulate these iteration-wiss inequalities over GD updates to obtain an upper bound on the number of iterations required for convergence.
D.1 ASSUMPTION
We still use Assumptions D.3 on the training data.
Assumption D.1. Vi, /' training set, if ys * yv, then || Brain
X
afull trin,
X
for some
> 0.
Assumption D.1 requires that aggregated node features with different labels in the training data separated by at least constant, which often satisfied in practice and can be easily verified based on the training data. A similar assumption on the non-aggregated features ||x; - X2 l| has been adopted in prior analyses of the DNN optimization dynamics without message passing (Zou et al. 22020a
2018).
D.2 EXPRESSIONS FOR GRADIENTS FOR CE LOSS.
We first provide some basic expressions regarding the gradients for the CE loss in the GNN under our setting. Note that the node classification task in this case is binary, denoted as K 2.
Output after the 1-st layer: Given an input X, the i-th column of output after the first layer of the GNN under the full-graph training
full
full Atrain,
X
(wrlll)
full Brain, X X(S) (fullll
(42)
where Dfull = Ding
> 0)) E ARA represents whether the j-th element Aurain, X (Will) T) J, is more than zero (1) or is zeroed out (0), Here slightly abuse the notation
( Prram.
X (Wiill)
and denote 1 fx 0} = [x1 > ....... 1 {xm > T for vector x E R
Output of one-round GNN for the CE loss: The output of the one-round GNN for the CE loss with input X under the full-graph training be expressed
arain x (wrfll)
))
Tioli X(Ex. w-fulll TVT
(43)
where v E (-1,+1} E Rixh corresponding to the binary classification task setting in this case.
xxh is the fixed output layer weight vector with half and half 1.
26

---

Gradient for CE loss in GNN:
The partial gradient of the training loss L (Wfill) with respect Willl under full-graph training be expressed
Legain
(w.lll)
Σ (U.D..)) (ul.f.l)))
ys V Vwnii (o!t"l)
(44)
Paraiin
where the gradient the GNN is defined as V Vwan [o]ttl]] = (v>itull)
a Aurain i. X.
D.3 THEOREM D.2
Theorem D.2. (Convergence of Full-graph Training with CE) Suppose Whili are generated by Gaussian initialization. Under Assumptions D.3 and D.1 if the hidden dimension of one- round GNN satisfies h Q (log (Memin) dynae Train
) then with high probability, the
training loss satisfies Lerain (Wi." A
S c, provided that the number of iterations T =
(orain (log (Nerain)) ))² a- 2 (nirain + +6-1) for any 2 0 under the full- full-graph training.
D.4 PROOF OF THEOREM D.2
We first provide the following lemmas.
Lemma D.3 (Bounded initial training loss) Under Assumptions D.3 and D.1 with the probability
at least - 5, at the initialization the training loss satisfies full (Will) S C where C' is an absolute constant.
/max log(Tanin TTrinn 8),
Lemma D.4 (Gradient lower and upper bound) Under Assumptions D.3 and D.I. with the probabil- ity at least cxp (-C, ho? /ntaan). there exist positive constants C₁, C2 and Ca. such that
1|2
Czhaadaa max
V Win i
(wrill)
Σ I' (V.ov
train
nirain
Czh diuss
full V Wan train
(Wrfill)
(y:of
Plrrii
Lemma D.4 (Sufficient descent) Let Wifll be generated via Gaussian random initialization. Let Wifll be the 1-th iterate in the gradient descent. If Wfflll Wffll B (Wfill 7) and s Co/ Co/(ad 2+1
then there exist constants C4, Css and Cs such that, with probability least - cxp( (O())) the following holds:
L
(WiT)) 2+1
(W!!l) & -(1 - Cadduar
( woin Lem (w.!il)
Corydtuuct
V Vwin Liall (Willll)
naain
Σ
(woth.
Thamin
first prove that gradient descent can achieve the training loss at the value of under the condition that all iterates are staying inside the perturbation region B (Whill .)
Proof Theorem D.2:
(W:
W
willl
l| < r)-
Using Lemma D.4 there exists a constant C22 such that
wann ffel
(wfill)
Czhazdan 3
(weeffll)) (e
)
(45)
train
We then the step size 77 and the radius follows:
27

---

1j
4Cadmux/1
0 (dimartt 1)
(46)
4Cg train
train
irain Amix
(47)
C2admaxx
Then we have
Lina
Lirain (W!au)
1+1
1" V wii Lemin (w.!ll) ||²
C2nh addex 4marain
V Wan Laai
(w!..l)
Musit
Σn'
(U:Di..
1" V Vwiaa full
(will) l|
+
!!
whit T
(w!.il) 1
(48)
1
V Wins full
(w!ti) ||=
2n
Czho² de
- 11-1000 2n
where the first inequality is derived from Lemma Lemma[D.4Ja and the settings of v) and т, the second inequality derived from Lemma D.4, as well as the last incquality follows the gradient lower bound in Lemma
D.4
We note that (xx) log(1 + ()) satisfies -1'(x) 1/(1 + exp(x)) > min (wo, ux(()), where up = 1/2, u1 = 12(2log(2)) This implies that:
Vinsi
Phesin
UiDVi.
full
min Σ uzl' (uoit.t) S
(49)
min
do, Turain up fulll
W
Since min () 2 1/ (1/a + 1/b),
have:
full
(W?t1)
0+1
(w!".)
C2haa dmnss
Czho dena un (Leall
(W
$ y min
uus
2n
Menain
(50)
2 Czha de di
2ntrrin
S-n
Czha uf full (Witill) 7
Rearranging terms, we have:
(full
(Ww!!l)
L (w!ell)
2narain ?ahaadaaa up
(Luill (w(t1)
f.flll (w.fall)
S -7. (51)
Cahea deaax of (fulll (Wffll))
Using (ar - w2/0²² 2 y x
-1 and taking telescope sum over é, we have:
2neeain
(iem (W
(Ltull (W
tn S Czhaa di up
2
(Liill (W!!!!
full
(w-ffit)
2 uf
2marain
(i.bill
(Wriell)
full (Wr
2 < Cahuva doaan up
fall
(willl)
Cahecad uf
(52)
Next, guarantee that, after T' gradient steps, the loss function f. full (Wfoll) ( is smaller than
28

---

Using Lemma D.3 we have train
full
(Wi O <liux (log (m)
Therefore, T satisfies:
T=
naaan (log 3
Admaxx
+ Merain (log (Murain)) (eaz (enddix)
(53)
Then we are going to verify the condition that all iterates stay inside the perturbation region (ill 7). Obviously, we have Willl E B (Willl, 7). Hence, we need to prove W f+1
B (Willl 7) under the induction hypothesis that W E B (Wi .7) holds for all / S T.
train (Wfill) /
Since we have ffllll (Wiill) full triangle inequality, we have:
(Wf
S --21
Win I full
for any S T, using
train
F
w
w
V wia Trrai (wf")) (w
wir Lull (Wrel)) ||2
k=0
(54)
2/v
full (WI"l)
(Wo4)) k+11)
kmu
2 full (Wh
Using full (Wffll) O (dhaxx (log (Feaai))) in Lemma D.3
and and settings of 77, we have:
W
Willl
2tm
i full train
(Willl
(55)
Quain (log (Remin)) a- d'mu to
Puain (log (Remin)) + ---aa-- -'mmm xt)
In addition, by Lemma D.4 and our choice of 17, we have
C' & danx Σ
V winn Lemin
(wrfil)
S
(uit fill
Thtrain
(56)
0o (log (Femia))
h d
where the second inequality is derived from the fact that -1 -11()))) Therefore, by triangle inequality, we assume that and we have:
S2 (nirain log (Perain) dm log (Merai) c- (-Idml)
win #+1
W
1
V win Eiui
(wrlill)
||2 + W-flil w. ||2
Misin (log (Farin)) & d 1- miain (log (Timin)) - - -I
=
Momin dink a -1
(57)
which is exactly the same order of 7 in our settings.
This verifies Wfull t+1 E B (Will) 7).
Proved.
29

---

E PROOF OF CONVERGENCE THEOREM IN MINI-BATCH TRAINING WITH CE AND INTERPRETATION OF THE OBS
In this section, we provide the proof of the convergence theorem in mini-batch training with CE. To simplify the analysis, we focus binary node classification using one-round GNN trained with the CE, defined as (W. amain. = log (1 + exp ( v-)))). The final output of the GNN model given by 31 V output layer vector with half 1 and half -1. The rows of W are initialized independently from Gaussian distribution N I2).
[amiii : ,XWT) vy T Vi E training set, where v E {-1, +1} Rixh is the fixed
We decompose the analysis of GNN optimization dynamic into three steps, similar to Appendix
E.
ASSUMPTION
We still use Assumptions B.1 on the training data.
Assumption E.1. Vi, i' training set, y: * Ye' then (amini
X
arainn,
X 12 2
for some
> O.
Assumption E. requires that aggregated node features with different labels in the training data are separated by at least a constant.
E.2 EXPRESSIONS FOR GRADIENTS FOR CE LOSS.
We first provide some basic expressions regarding the gradients for the CE loss in the GNN under our setting. Note that the node classification task in this case is binary, denoted as K = 2.
The i-th column of the output z after the first layer, as well as the output jimini of the one-round GNN for the CE loss under mini-batch training, are similar to those in full-graph training in Sec. with full and a auun replaced by Wmimi and a
mini respectively.
Gradient for CE loss in GNN:
The partial gradients of the training losses i mini (Wmini
mini train
and i full
(Wiini
mini train
with respect to Wimii under full-graph training can be expressed as:
train
b 1' (U.Attin)) ye Waam umini
mini
(wriini
À mini train
E'' T=
(58)
b
Viunie
full v
(Wiminn
A Aginn
mini
V
V
mini
(59)
train
VAtrain
where the gradient of the GNN is defined V
W
[amini
a X.
E.3 THEOREMES E.2
Theorem E.2. (Convergence of Mini-batch Training with CE) Suppose Wiini are generated by Gaussian initialization. Under Assumptions B. and E.1 if the hidden dimension of a one- round GNN satisfies h = Ω (n log (Narain) 8-1 + log (Merain) g-'c=)), then with high probabil- ity, the training loss satisfies Lyrain (Wiinni T
mini S c, provided that the number of iterations = ( (naae (log (Nmmm))) a 23- 22-0---- b-1 + maain (log (Mmmin)) a -2 ---3-b---e- for any e 2 under the mini-batch GNN training.
Our bound on the hidden dimension reveals an over- paramttrrizationn setting in this case, where the number of trainable parameters exceeds the number of training samples. Since the hidden dimension remains finite, our analysis is conducted in the finite-widd setting, in contrast to the infinite-widit Neural Tangent Kernel (NTK) framework (Yang al. 2023 Lin et al. 2023).
30

---

E.4 PROOF OF E.2
We first provide the following lemmas.
Lemma E.3 (Bounded initial training loss) Under Assumptions ity at least - 6, at the initialization the training loss satisfies full mam
B. E.
with the probabil-
mini train
(Wo S
CVB log (main /0), where C' an absolute constant.
Lemma E.4 (Gradient lower and upper bound) Under Assumptions B.1 E. with the probability
least 1 exp (- CCihaa/ (n.)), there exist positive constants C1, C2 and C3. such that
1|
C2haa n
V Wam train
full
(Wiini
mini
Σ
C3h
V Wain L mini
Wminni
A mini
11
train
Arain
Lemma E.5 (Sufficient descent) Let Wit be generated via Gaussian random initialization. Let Wmiti be the t-th iterate in the stochastic gradient descent. If Wammm W E B (Wiiin, ,7) and
т & Cen (a,), then there exist constants C4. CG and Cg such that, with probability at least
1 exp()O(11), the following holds:
B
i Cull
(Wrring c+
Arna
|W
L
(Wiliu
mini Arrain
A
Ca,Bhan namin
Damin
V Vyrin Legan
W
A mini
|2
V Wiit
Tull Luman
Winimi
mini train
||
Thraii
Proof of E.2 We first prove that stochastic gradient descent can achieve the training loss at the value of under the condition that all iterates are staying inside the perturbation region B (Wamim .) {W:
|| Wminni
S r-
Using Lemma E.4
there exists constant C2 such that
wis
i
train
mini
(wrmin)
A
mini train
||
Czha g na
Phiinn
Σ 1' (v.02.
(60)
We then set the step size and the radius r as follows:
b
O (b3-' -'- "mmrann)
(61)
40sn
7
CzaB
0
N 7g-2)
(62)
Then we have:
full Lyain
miiin
À mini train
Wiriini
i. full Legain
Wirmini
A
mini tiinn
3
2nemin
(63)
< 5-1 ")
+
Cahar 3a
(Luell
Wimini
where up 1/2, 11(22og(2)).
31

---

Rearranging terms, we have:
21
R
(Wiiin 6+1:
A mimi
train
[
f
Traain
(
À
mini train
Eaho2Bank
2teaann
full
Wmimni
A mini
W
Lawin
(Waini
A mini
(64)
+
S -n.
Czho² 38
W
A
Arain
Using (x - u-///² 2 y x and taking telescope sum over t, we have:
2m
byj S
Limin
(Wart
mini Arain
C2ha2 u
(65)
21eemin
E
L Lirsin
Wrii
mini A
train
full L Lrrain
Wiiin
Amiin
A
Czhaz Buh
Next, we guarantee that, after gradient steps, the loss function full "tain
(Wipinn,
A mini train
is smaller than
Using Lemma R.3 we have itull
(Wainni
Á mini
O 0 (log (+
Irain
Therefore, T satisfies:
T ==ó
δ ( (Mraain (log (Tirain)) (a? Mirain (log (Ftraii)) / (ca?
(66)
Then we are going to verify the condition that all iterates stay inside the perturbation region B Winini 7). Obviously, have Wamini E B (Wiiin -).. Hence, need prove W
B (mmia 7) under the induction hypothesis that W, B (Wiini, .r) holds for all / < T.
Since we have i (Wiinn) immin (Wrinn))
1n V Wiin i miiii (Wriini
A
mini train
| for any
C+1
t < T, using triangle inequality, we have:
W
Wimini
V
2tm f E
(iimnn
A Auain)
(67)
Using miiii
Wminn
À mini
O (t (log (Mirain)) in Lemma E.3 and our settings of y). we have:
train
W
Wmini
26m mini
26m
Wiiin
À
mmin
(68)
Phmain (log (Femsia) )) bba - 3- - + nian (log (Heminn)) bbe - -1 -1--//1 1/-
3
In addition, by Lemma E,4 and our choice of we have
V Wiici i mini Tanan
(Wrini
À mini
11
Σ
(1.07ri))
train
1=0
(69)
5O (log (Farain) 1) 1o- - 12-
where the second inequality is derived from the fact that -1 S (1)-) $ O.
Therefore, by triangle inequality, we assume that h = (ni log (Memin) 3 + log (Amain) E 11 and we have:
mimin
Wiini
<
Wam immi
(Wrill) |1 + Wmii
Wimin
(70)
0 n a 8
32

---

which is exactly the same order of 7 in settings.
This verifies Wmin Proved.
[+1 E (WB 7).
F INTERPRETATION OF THE OBS FROM CONVERGENCE THEOREMS
Understanding the impact of batch size on GNN convergence. The popular explanation posits that increasing batch size reduces gradient variance, resulting in fewer iterations to converge (Cong
al., 2021a Zou al., 2020b Liu et al.) 2024 Li & Liang| 2018 Hu al. 2021). This explanation does not fully account for the impact of batch size on GNN convergence, necessitating additional consideration of the impact of message passing on the loss and gradient.
MSE: Taking the MSE as an example, the impact of batch size on GNN convergence is explained in three steps: (1). Activation similarity: Larger batch place more sampled nodes and their neighbors into the same graph subset in single iteration, where message passing enables direct or indirect information exchange, resulting in similar activations processed by the same GNN parameters. In contrast, smaller batches spread nodes across iterations with varying graph subsets and updated parameters, reducing such similarity. (2). Gradient similarity: As MSE penalizes the numerical difference between predicted and target activations, the nodes with similar activations produce similar gradients. The GNN with larger batch sizes yields more coherent update directions after gradient averaging, capturing dominant structural patterns among nodes. (3). Bias: These updates may reduce node representational distinctiveness and overlook graph structural diversity, introducing bias and steering optimization toward suboptimal local minima. As batch size grows, convergence requires more iterations to escape these biased regions. DNNs typically assume i.i.d. training samples, enabling large batches to retain diversity and reduce gradient bias. This explains why GNN findings on MSE differ from expectations based on gradient variance alone, highlighting how the interplay between message passing and the loss function affects the impact of batch sizes on the GNN optimization dynamic, diverging from DNN behavior.
CE:CE focuses on optimizing the predicted probability of the true class, rather than minimizing the numerical differences between activations. Thus, the activation similarity does not necessarily lead to similar gradient directions under CE. This allows larger batch sizes to benefit from reduced gradient variance without introducing significant bias under CE, leading to fewer iterations to converge.
Understanding the impact of fan-out size on convergence. larger fan-out size allows each node to aggregate more neighbors. enriching the node's embedding and enhancing the effective gradient even when using MSE. This leads to the reduced gradient variance, thereby more stable updates and fewer iterations for GNN convergence.
G PROOF OF GENERALIZATION THEOREM IN MINI-BATCH TRAINING
In this section, we provide the proof of Theorem 3 in Section
We can characterize the GNN generalization under mini-batch training via the PAC-Bayesian frame- work (McAllester 2003). This framework decomposes the generalization gap into two components: (1) the divergence between the prior distribution P and the posterior distribution Q over the hypothe- sis space that includes all possible models that a learning algorithm can select, and (2) the discrepancy between expected training and testing losses over P. The first component is easily re-derived follow- ing the PAC-Bayesian framework. We mainly focus on bounding the second component, namely the discrepancy U between expected training and testing losses over P.
As the training and testing datasets are split before training, analyzing this loss discrepancy U reflects the structural difference between training and testing graphs. To isolate the impact of this structural difference on generalization, we demonstrate that the discrepancy U is bounded by the Wasserstein distance A (3, b) from the training graph to the testing graph, such that U < C. (B, b) for constant C, > O. This bound suggests that the more similar the training and testing graph structures are, the smaller the expected loss discrepancy is.
33

---

G.1 ASSUMPTIONS
We introduce assumptions on graph data and model parameters.
Assumption G.1. There exists a constant Cr > O such that |XX| / - Cr.
Assumption G.2. There exists constant C > 0 such that ||w,l12 S C. for all i.
Assumption G.T bounds the Frobenius norm of the feature matrix, and Assumption G.2 requires the
norm of parameters to be upper-bounded during mini-batch training. These assumptions are also
employed the analyses of GNN generalization (Tang & Liu 2023 Garg et al. 2020 Liao et al. 2020), which are introduced to simplify the proof.
The rows of W are initialized independently from Gaussian distribution N (0, RI))
G.2 PROOF OF THEOREM 3
Definition G.3. (Expected Loss Diserepancy (Ma et al. 2021)) For constant C₂ 0, define the
expected loss discrepancy between training and testing datasets before GNN training as:
[e
(Lue (Wmre ) Lamin
(Wrinl _A
U = wnEwii
where P represents the prior distribution over hypothesis space that includes all possible models that a learning algorithm can select.
Definition G.3 captures the difference between training and testing datasets.
Definition G.4.
(Distance between Training Set and Testing Set). Define the distance from the training set to the testing set as the Wasserstein distance given by:
A (B,
inf A [PeiPnansPtssl sElrain sut J'Eest set
Σ
Σ
Or (vs, (v.,w,,3b))
(71)
Σ f (y:) Peain (y:)
Σ
9 (U:) Pren (15)
sup ((-)a())) ketrain
where Ptrain (3:) and Prest (vi) denote the probability of appearing in training and testing sets, respectively. θ Ptrain Presa] the joint probability of Puain and Prest and f (y:) and g (ys) are func- tions of with i E V. The infimum in the first equality is conditioned on Ej set Bi,
Puain (34) Evetraining set O., Pust (yz) Os. 2 0, and the supremum in the second equality is condi- tioned on f (2:) + 9 (3/)) S (21, My 3, b). 8 (y., 3, b) is the distance function of any two points from training and testing sets, respectively.
The Wasserstein distance effectively measures differences in non-i.i.d. data, particularly regarding geometric variations. A dual representation is provided in Eq (7I).
Theorem G.5. (PAC-Bayesian Generalization Theorem). For any C. > for any "prior" distribu- tion P of the output hypothesis function of GNN that is independent of node labels from training dataset, with probability at least Ca. for the distribution Q of the output hypothesis function of GNN, we have:
1 C. C (DKz(Q11)) In 1 CG
C
Taess Wrmini
full.
2) < test
i Train
WWmin
mini. train 2)
U.-
47train
Lemma G.6 For any C, > O. assume the "prior" 'P on hypothesis space is defined by sampling the model parameters. If the in-degree of each node is 0(3) and the out-degree of each node is (bb), we have:
U C,
and,
A( Σ Σ
0 Frall mini
Σ
Σ
O
Full Buraa
A
EErrain sEt Etest
<Ctzinn set E set
F
(72)
A b.) < ( by) with by 2 bz
34

---

where Sfull-mini has overall non-inereasing trend when the fan-out size 3 increases but small non- monotonic fluctuations can exist. Note that fan-out size plays a more dominant role than batch size b in influencing generalization.
Proof of Theorem 3
Using Theorem G.5
we have
Lie
W mini
foll Trinn
2
< Luain
W Wmini
A
mini, trainn
(73)
C.
(DRl(QIP)+ In
U.
Cc
47hain
Since both P and Q are normal distributions know that
(Ma et al.
2021 assuming that ||w/rini
Cw.
F
W
Σ
minil
C
DKI(2)IP) v
(74)
2hx²
2hx²
2x²
where Cr is a positive constant. Hence,
List
W
crani
full
2)
< tull
W tini
Again 2 + (Dkl(e1)P) + In
1
1
+
C² +U 4ngai
(75)
C.
Ca
< Liirai
W
tini
A
+
1
C
+ In
1
+
C
+ C. C.A (3.6)
Cu
2x²
Cg
4Mgrain
H EXTENSION TO MULTI-LAYER GNNS
Our theoretical analysis readily extends to multi-layer GNNs, long each layer introduces only one non-linearity (e.g., ReLU activation). In such settings, the key difference is that the output of each layer recursively defined based the previous layer.
This recursive definition preserves the same peessage-passing structure at each layer. In convergence analysis, we bound the gradient norms layer by layer; in generalization analysis, the pre-training loss discrepancy propagates across layers. These recursive structures allow our convergence and generalization bounds to translate naturally to multi-layer GNNs.
Our key theoretical insights (from the view of batch size and fan-out size) are generalizable to multi-layer GNNs. This is because adding more layers simply nests the same operations, without changing the qualitative roles of batch size and fan-out size. Hence, the analytical trends observed in the one-layer case remain consistent.
Therefore, our theoretical analyses support the multi-layer GNN settings.
I PROOF OF THE MAIN LEMMAS OF CONVERGENCE THEOREMS WITH MSE
I.1 PROOF LEMMA B.5 AND
We first focus the mini-batch training. Note that ((x) Then, the bound on mini follows
whenever
Daniely et al. 2016).
PijO
eig gumini
gmini
1J=1
Piy v
guini
Σ
Pij V
mini Irain
Ä mini train
bb
mb
(76)
Ä Aman
mini
1
bb
mini
zb
tzan
35

---

To bound ry notice that j (x) I ([z1), and (-) is non-decreasing function in [0. 1].
Hence, we get |mmini s Tmin
have the normalized adjacency matrix of graph with nodes as:
@11
Oin
À mini train
db1
Chrr
(77)
Q11
O1v
V
v
di
4b1
Apn
6
where dij E {0, 1) represents whether node i connects with node j (1) not (0).
Since d.th < 3 and am < b, we have:
A train
1l1
Σ ==1
Usl
ain
Vdtt
Va
dd /ddvo /o
(as1 +... asn)
3767
(78)
min (an +... am))
81
62
35
Moreover, since 0 training iteration, know that
denotes the amount of common messages between node and node a given
< 1. Then we have:
mini
mini
Pijō
@rna mant
f,==1
(79)
mini 1
Moreover, since 1/
(Vay
d
adqut
< 1, we have:
1
A mini
...
dd Vaqu
/ /dp/ d
(80)
(an
am))
<Bb
where the last inequality holds because there exist at most 3 terms that are not equal to 0.
Similarly, for full-miiii we have:
fall-mini
A 1
TT7amain
Thrrain
A Amin
(81)
b
mini
bb
Irain
36

---

and
ffull-mini
A
mini train
(82)
b
Moreover, |
<
ffil-mmini holds.
Similarly, in the full-graph training, we can replace b and [ by Quzin and dmax, respectively. Therefore, we have:
A
S
fulll
Amin
(83)
Merain
Mirain
Train
<
||A
Lain || S
full
(84)
dmax
|
< p
(85)
This complete the proof.
1.2 PROOF LEMMA B.6 AND
Lemma I.1 In the mini-batch training, |=quii| o(Tyiin),
|=foll-mini] o (
(fTfoll-mmin) ), and, when D
6. 2 100 and (oomini) 2 + (B))mnn) 2
2 1 -1-0l o(), then Epini
2 23 and Efuillmiii > 2 the
rum
full- full-graph training, |=full| o(T and, when offull 2 TOO and V (dffall) 2 + (we 2
o(1),
then Ffull
Proof of Lemma B.G and we are going to analyze +++1
We first focus on the mini-batch training. Considering the gradient,
mini
mimii ++1
mini PE+1
mim
P1443
H mini
mini
mini
(6) mini
1//minii
mini
+
mini
Delmmin
miiii
mini
mini mini
+ The
T
+ 17+ (ormin) ) + (umminn)
mini
V (driin 2 + (usming) 2
2
whin
(86)
+
T/u th
mini minii
+
M
+ TJt (oppin
mini
(ominn y² (sbemins
gimini) )
=
=<omin))
+ (1smin))
my rmmini?
((ppin))
2
m/ rmiin
(y.minn
+ mp (omiin) )² + (algmim)
mini
2 mini
mini (A)pinn)
+ miies
+ 27/- v (osmini )² (vlrmin) Trami
2n Grmmii r
(cspinn)) + (vismini 2
Hence, By Lemma and Lemma
we have:
mini @i+1
mini 2 pe++1
(oppinl)) + (1sminn)) 1 1- 2==))²² C,
(87)
when the learning rate T/ E and positive constant. Hence, we can rewrite the range of m as me E (0, 1
Awasthi et al. 2021 , where C S
T6 is small enough
Gn mm
6ml
37

---

Then, for all t 1, we have:
v ( 2 + (s)minig
(1 1
- π
-
V ( 2 + +vagiing?
C
$
(1 0)
</ (dggint)
+ (vig
+ 2
(88)
<V (ogiin) ) (wginng ?
+
2
Moreover, with probability at least - - we will have v (dgiin) 2 + (vogini) 2
(KVTT)
Hence, we have V (dmmin) (wiquini) )² C1.
We also have that if mmii > O, then
mini 0c+1
2
mini 1/+11
2 2(0 (o!
2 + (wriin)) "xc !
2np r
(ariin) 2 + (y)mim (1 m)I r
(89)
Similarly, in the full-graph training, we can replace and 3 by Thrain and dmax respectively.
This completes the proof.
1.3 PROOF OF LEMMA B.7 AND
We first focus on the mini-batch training. From Lemma V (g 2 + (1iminii² s C, where is a positive constant.
C.2
we immediately have
Next, we analyze the upper bound of Amax
2 full mimii
mini
mini
We have:
Amax ( 2 full
( ay mini
mini
mini
82 L Liman (Ofinl mimin
Armin
8 Lirin Conini
simin (abtmin) }
A Arrain
a (
(90)
8d Leai ( mini ofr Oepriim triqiii
A mini
8 Limin (ofmini Ore degein
mini
Taking the second derivatives, we get:
mini
2/2
mini
mini
Aillminii
full-miii
miii
r foll-mini
0 @6
w wini J,t
wiiini J.t
(91)
8= d-llll-is fall-
2
mini
full-mini
worting ||
Oepmmia
W Minni
J.t
8 full mamini
mini
à (1)mini
dull-mini
mini
fullll--mini
22
mini
minii
f foll-mini
Oriamini
memini
(92)
3.t
8= 8- fill-mini
mini
(
mini
full mini
mini J.t
1
Depmini
w mini J,a
38

---

O Lurin (0) ( 4
mini
4/4
a full-miii
Øc
mini
T
mull-mini
w
minu 3.1
Sit
mini
O=fillmini
miii
0=
foll-mini
mimi
2
(93)
V
(
-full-mini
whitin Jit
@a I full
(0) m Jotmini
A Aminn
mini
g wittin
mini
full-miini
Oriamini
|
(94)
P Wiitinn
mini mini
8 falll-inniss
91
mini
(10
fillmiii
2
O
Next we have
fulll
mini
Ssaup(
Cik
mini
(g)mmin 3
mini
Menin
v (o 3 (csgpin
W mini 2.A
1,kmm
(95)
( mini
+ (wemil) 2
mall
foll
mini C
mini
mini 9/2
mini Pik Li,k drsopp
Oeiminn
Ylemin
grmin
V (ormin
wiimnni 3.8
1,
(96)
(6)
+ (15pmnn)
2
fill-mnni
= ([filllmmmm))
where we use |=]
[ffull-mini
o(1 ffull-miii in the Lemma L.1
To differentiate full mini we employ 6(0) = arccns(0)
Daniely et 2016 and arccos' (0)
0z to get:
8ffullemin
fallomini
Pik
Thrain
mimini
A
(97)
Tiprin
(Q!min)
mini
2
(Crrie Jamini
Mull-mini
Muzin
8E full-mini
(o
|/wggin pomini
ssmini uomini
Pik
Turann
i===1
2.Nk
(98)
Tirris
(of mini
+ (usuin)))
2
(e
Mull-mini
Thrain
Jamini
Therefore, have:
8 full (6
A mini Arrain
< full-mini
+ ((07mm))) (0)mi))
1
pall-miin
[
fulll-ain)
(99)
full (1 + VC +C+o(1)) = C. full
8 Legain mini (vtmin)))
mini
brain
SI t
fillmmnii
(oftin))
(m)mmm)) 2)
( ([llll-mim)
(100)
full-mini
(1 +l) = C.1 full-mini
39

---

Ee Ligain (or vi
A
train
mini
minn
2
1 Mullemin
(
or
D Drti
(101)
ST mini (VC+ +o
C2T1 P
mini
@ full (ot Depiiii Des
A
mini train
full-min
(ulll-mimm
(102)
ST. <Thallmmn
(VC+o(1)) = C mini
where C and C2 absolute constants.
Hence, we have:
Amax ( 2 T-main mini 13 mini
train
) S C3 C full-mini
(103)
where C3 = +1==(1+ ( + o()
is an absolute constant.
Similarly, in the full-graph training, we have:
Amax ( full
( v fulll)) C,r
(104)
where C4 4 (1+ + is an absolute constant.
1.4 PROOF LEMMA B.8 AND
We first focus the mini-batch training. Due to random initialization, with probability at least
1 we have that v (0b (dmini) 2 + (uimin)) o (TVTT) and dgnin 2 -On/logh h with constant
C > Furthermore, we have the following updates:
P1+1 + 1/2+1
= V (orpin)) 2 + (1/tmint) (1-1). 1. + r )² + n (ouminy + (nigunsy
))
(piminiy
(105)
mini
mimi
mini 1141
(i (1- (1-1z Dmuial N1 V (oginn)) 2 (uomini)
mini
mmini Me (ammin))
mini
(106)
+ (w:eminl)
Since Tmini
0 and is bounded by rminn and Emini (orin)) 2 + (usgnini 2
o o(Imini).
ominn
and
2 2. we have:
V (Qminn)² 2
(uumini))² 2 V (dmmini) 2 + (ummini) 2
(107)
pt+1
mini
(1
pmini
nio [mmiin))
(108)
Hence, after C₁ log(k log h)) steps, we have that Ominn
100 and (øginn)
2.
Next we show that from this point on omini and / (oginnt 2 + (slsmim)) 2 continue to be satisfied. We have:
the conditions in this Lemma
(demin) 2 + (2)-min))
(109)
2/ (0mmi))) + (abmminis²
T/ rmini
(Vrrin)) + (usminnt) (1 + m (I. pminn)
where
mini
mini
mini
mini
mini
(110)
amini
pid
gmini vi
(chmiin 12
40

---

Once oi
100 we have:
mini
mini Liny
mini
21.3
- ④
2
2
(111)
/ gmini
v (opiin))
(zsgmini)²
/ grmini
Amini
Hence, we have that dhnini 2 100 then V (dspim) (viminn))
1-)(
Next discuss that @rini continues be larger than 100 (orim)) 2 + (v)tiin) 2 2 11-- o(1) remains. Furthermore, if of
First, if apini
0, then
|-
I T0D 0), then =q is non
negative and at least 1 Ei,
ib
Zi et Pij
Hence, we have:
mini
T mini
mini St
1 V (ommini + (asminiig
r pmmini
1/t V (omini) y (usqinn)
(112)
Σ Eissettt fo Pis
(anminn 2
+ 11 (d)mini) 2 + (viginn)
1b
Using
(ominn) + (uimmini) 2
1
O(1) and the fact that if of mini
[- 100 0) and
V
(omini)) (ustmini) ?
1(1,,,) then (orin)
1,, we have that omini
Similarly, under the full-graph training, we can replace by Merain
1.5 PROOF OF LEMMA B.9 AND H.5
We first focus the full- full-graph training. We have
V
L Eill
fall
rull
|
Φt fill pmnll
fill
(wstang =
V (oofen 2 (wntuny
(113)
+
w/llll 1
T:
aiullll
4/4
=full
(offel))
-(Viogun) + ( rull
(uspan)
r
+
(=
(off
On the other hand, the loss T full
(#ifell rifflll) can be written
I Famin.
full
Jull
(
+ pull (ofoi)) + (w 2
(114)
(tt
Aull 2
(w
+1 sun
41

---

Hence, we have:
V (oftun) (*sttit) P full
V T Train (offlll whlall ||
L Jull
Pmol
Irin,
(115)
(wi!t)) (=
+ 2
(dfelt) (2)) ((ofil)² ) + 1) l
If V (ofall) 2 + (uifull))
cd 2h
then the first term above combined with M < [ leads to
V L train.
(ol &
e
cl
(116)
full irain,
(o) spt
4h2piall
4/22
V (ofal)) 2 + (vtsael) ? -1
c 2h
1 2 and
then the second term leads to 2h
V L Luzin, (ob )1
(v (=(ul)
22
L gain. (0) 1355
(of(i))² (w))))
(( (v)m)²² 2
r
22 (w 2 (=
9(9 + 1)T
(117)
2 (= 2 c
901 4h2
full
360d 4h2
Hence, we have:
v Tirunn
(ffull
full
2 full y Trtam (ot vit
(118)
where , 2 Cieh 2 2-2 pfull and C1 a positive constant.
max
Similarly, in the mini-batch training, can replace dmux by B, we have:
full V.naain
mini
A
mini train
mini full mini
mini
A mini
train
(119)
where y 2 Caeh 23 full mini and C2 is a positive constant.
Finally, going to consider the case in the full-graph training when (ofoel) + (wiffil) I
1 1 26 We can assume that T
(ooaii) + (valll) Prrall
a piull since otherwise we get the
2%
at same bound as in 1166. In this case, show that || must be least and hence the bound of (17)) can be applicable. Using o-)) is convex in [0, 11. we get
25
(Vorg
fill 2
2
( + (1sginn²)
gral
(120)
dfflll
(Gsful)) ? (w/dolliy
full eis
Full
Srapp
(oRmn)" + (wgaa))
Summing over i, j. we have
full v (dfall) (w/!all)>
full
Prain (T!Ell) - rdoll) - >
Σ
Pii 2i. Ssspp 2
(121)
(ofull) (wfall)
Votu
1
42

---

Substituting Y
V( (ofui)) +
+ 2
9rTlll
păn we have
Mexin (V (df-n)²² + (3/A -1) p
e poul
2/x
(122)
full
Σ Phser. th, dssepp
full
V (ottn)² + (anfun))
Using the bound on v ( + (wifull) 2 the above implies that
c Parain fall
(offe)) + (wof01)2 &f
Σ 2
fall Pey er o
(123)
V (ofii)) (w
/
Noticing that [ull
A
full train.t
|/1 by Lemma C.1
we have
V (o!tu)² + (wifutt ofull
||A
Tull Irain. |/:
(124)
V (ufell)
ndl 2mhh E,, Pig pise Sstopl 7
Therefore, we have
full 2 2 + (156mm)² fall
à || Aninn 1
( (155any²
Aul
2mhh Ei, Pii Pisel S
e rain. 111
(125)
2nh Ei, Pi Grepp
21.1
V
é | taan, 11/11
2hMarain
ed
2hm di
2h
where the second last inequality uses Eis Pij eii &
I Ahtain because there exist Brain
nodes that have the common messages.
Similarly, in the mini-batch training, we can replace Dhrain and dmax by b and 3, respectively.
J PROOF OF AUXILIARY LEMMAS OF CONVERGENCE THEOREMS WITH MSE
J.1 PROOF OF LEMMA
We first focus on the mini-batch training. We are going to analyze the upper bound of mmini,
mini
mini 2
=
mini
mini Piyli.j Ōstep
(126)
(dumnni) (u.mmni)
1
where each term summation is non-zero only when e. + Offi=
Hence, there are at most b non-zero terms in the summation, and Emini is upper bounded by I!mini
namely gmini o(pinn)).
43

---

Note that (2) 2 1 whenever |2|
Daniely al. 2016), which is ensured by de 2 100 and
(orini) + (e)qiin) 2 1 1 Hence, in this case, each term in the summation in the expression of mmini will non-negative. Then, for = j. each of the terms in the summation will contributed at least Awasthi et al. 2021 Therefore, in this case Eq
V
T with r S 3.
20
Similarly, we have =t
mill-mimni
mi and, when dimini
and V (drtin) + (utmmini)
100
1 - o(1), Efull-mini
2p
Similarly, under the cull-graph training, we place b and 3 by Temiin and dmaa. respectively.
K PROOF OF THE MAIN LEMMAS OF CONVERGENCE THEOREMS WITH CE
K.1 PROOF OF LEMMA D.3 AND
Lemma K.1 Let Å be the normalized adjacency matrix with self-loops. Given a mini-batch size b and fan-out size B, the following inequalities hold:
mini
1 S 3
and
full ttrinn
11/ S dmax:
for any i in the training set.
Lemma K.2 With Gaussian random initialization, for any E 10, 2 C'log (n/5) for some large enough constant C, then with probability least 1 ō, the following inequalities hold:
log (Narain/ /8)
||ا
c 3t < sci
h
and
|||2.10 112
c d
S C2/ dmux
log (Ferain 6) h
for any i in the training set, where C11 and C2 are absolute constants.
Since half of the elements of v are I's and the other half of the elements are - without loss of generality, Va/2+1 = ... = V
Proof of Lemma D.3 and E.3
assume that Vı
Va/2 and
Obviously, we have E (Drini) E (if = 0 for any in the training set.
We first focus on the mini-batcl training. Using the value of v, we have:
mini
Σ
A/2
mini Biramn
x (w.hinl) ")
mini Atrain.
X
W3th/2
mini
(127)
With the Lipschitz property of ReLU function, we have:
Prrann,
mini
X
(w.mim))
Berain
mini
X
5+h122
mini
Alyain,
(w
mini
Zkpain X
w mini
w/th//2
(128)
=mini Ekrain,
X
w
mini
mini w
Akrain.1
|X||2
W
5+
<Cah 2
44

---

for absolute constant C3. Here the last inequality follows Lemma K.I
Therefore, by Hoeffding s inequality and Lemma we have:
yi
mini
2exp
(Csh t
(129)
2u²
>u)
s 2 2exp
C3.
Taking union bound over i, we have
P
M
mini
u
Merain
Mttrain exp
C3.
2u²
(130)
(- 2a
Let 2n exp
6, have:
C33
2u
5
cep
C3B
2nemin
2u²
log
C3.
2Teerain
(131)
C
log
27hrain
5
Cap
Blog
Then IP [ggmim] >
Cap/
3
log
5 Ausin
1,
Train
S 6.
Therefore, with the probability at least
8, it holds that
mmini yi
S Ca
O log
(132)
Perain
for any i the training set.
Then substituting the above bound into the formula of loss function (yge)iin) we complete the proof Further, substituting the B with dmaxs complete the proof of Lemma D.3 for the
of Lemma E.3
full-gre full-graph training.
K.2 PROOF OF LEMMA D.4 AND E.4
Lemma K.3 There exist absolute constants C,C,, C2 > 0 such that, with the probability at least 1 exp (-Cha² (muzann(max)) for any m (m1,.... maam) E RT there exist at least
C₁ C1ha²// (maxain GNN nodes in {1,..., h}} that satisfy:
Thuis
mayso'
full a
X
(wmini)
full alrnin
X
2 C2 | &
Tarain
Lemma K.4
There exist absolute constants C3, C4, Cs > such that, with the probability at least 1 - exp (-Czha²) / (H),in))),, for any (m...... Monmn) Riiin there exist at least
Cyha?/ (Mrzin 3) GNN nodes in (1........... h} that satisfy:
m.y.o'
mmnn Berain
X (w,mini)
mini
X
2 Css || 32.
train,
Tamann
45

---

Proof of Lemma D.4 and E.4 We first focus the mini-batch training. We going to prove the
gradient upper bound. The gradient V Waml (3:01 (iin)) can be written as:
V Waiid (u:Di mini
= 1' (1.0%
Wiiin Di
mini
(133)
=1 1'' U.
(v
SiLL amnin X.
Since Em is a diagonal matrix with (Eminn) E {0, 1) for any j E (1....,h), we have -mmin
|| =
1 for any in the training set.
Hence, we have the following upper bound on |/ wail (yel) I1 Il
||- ||| / (ueD?Tm) }b
- -1' (w:Dt
|
lIvila
mini Aemn.
||
|
(134)
$ -1' (v:D mini
C h ht
where the first equality holds due to the fact that Vimal (U.0,iin) is a rank-one matrix, and the last ineuqality follows Lemma K.1 and ||v||2 11t.
Further, we have the following for V Wasin Limin
(Wiiiii
A mini main
Wain Laain
Wiin
V Wmmll yiih
mmin
Viial (Brth comde
)ll
(135)
x Cont b
Σ (U.D?ti)
where C6 positive constant.
Then, replacing b and /3 by Perain and dmmx respectively, we have:
Colt drnax
Vwia full
(wrlll)l
||
(136)
Thraii
for the full-graph training.
Next, we still focus on the mini-batch training. We are going to prove the gradient lower bound.
Given the initilization Wmini and any Wimini E
B (Wmiii,7)
where (Wainni 7) =
[W: | WWWiiini 112 < T}
We define:
Pegan
(2rotaial) yo
sminn Ptrain
X
(Wmiia))
Amain.
minni
X.
(137)
Tarain
Then, since Wo is generated via Gaussian random initialization, by Lemma K.4 4 following inequality holds for at least Cyha?/ (nemin))) GNN nodes:
we have the
|g llz 2 Co max | (v.ofmin) 8²,
(138)
where C₁ and C₁ positive absolute constants.
Further, we can rewrite V
full "taann
mini
A mini train
as follows:
Gaii full (
mini
mini Ammin
l'
y:
mini
yiv
mini agmin,
X (w.
mini
mini atmin,
X.
(139)
Téraii
46

---

Let Z.,j l' (Ue y, have:
gg) 11
V Gaginn Leiain
W
mini
Astrain
mini
||
Zigz
Birain,
miiii
X
mini (wiiin
Btrain,
mini
X
Vemin
i=1
Blamin
miii
alrain X
Tirran
(140)
Zi.t
Again,
X
)
& X
wymin
))
a
Perain
Piris
Cfe g max ('
Thrrinn
i=1
=Cr37 max 1' (u:D. )
where Cy an absolute constant.
Therefore, there are at least Cyho²/ / (Mtrain GNN nodes, satisfying:
v aigin Lill (wrinn
Amini
|1_
20s max (' (u.
13 -8---00 -C max |' (u.t.
(141)
00s max 1' (u..i
18a.
Therefore, have:
V Wran f.llll
(Wiminni A
V aagin Liun
(wrgiin
A
Arram
mini
|1.
(142)
Cahaa
(Ca max 1'' (v.37
||
|122)²
Thuainn
Cohex z
Σ (21071in)
n
Then, replacing 3 by dmax. we have:
V
full wain
(Wrfull)
Caha de
Σ 1' (M.Df )
(143)
3
for the full-graph training. Proved.
K.3
PROOF OF LEMMA D.5
Lemma K.5 For any with probability least 1 0(1,, if Wiilll B (Wi. r), holds that:
C
and
w || ك C,
for j (1....,h), where C= x (=FF++++ 8) is positive constant.
47

---

Proof of Lemma D.5:
Since / (x) is 1/4-smooth the following holds for any A and
(x + A = (() [ (1)) A²
(144)
Then we have the following upper bound on Linin
(Wi41)
i full
(W!ill):
Luain
W
fall
(!!!!
MiBlie+z)
(iiBlee) (oll
Viemin
(145)
(v.lliettr
1,441
Merai
where full 1,4+1
Vs (+i,++1
(ffull
full Vi.t
).
Therefore, going bound Afull The upper bound of | be derived as:
A
y/ arrinn
X
fuullll (2,6+1
W
r+1
Yl alainn X
Syfilll W-flll
full
X
full 2,0+1
W ++1
Saall Di,
W
T
(146)
-
C2 dmaa
fuulll pi,
Wiil
full
W!
where the last inequality follows Lemma Hence, we have:
K.I
A S C dtta
||
Wrilll
w
fuoll
Whflll
[talll
11,
+
2
S 20 dhiutt h
Wrflll
w! 1
+
(147)
S C ad 2
V
wan Till
(w!"l)
11.
+ C +
Cidăuuld
(w!"))]
C
Note that 7 has an upper bound, the third term the brackets on the right-hand side the above incquality is dominated by the first one. Then we have:
full A
S Cidiaa n V ffull (w
(148)
Then going prove the lower bound of i.t
full fلul x Since A.r focus on bounding the term 2,141
fulll Wfill i.t++
full TT y/ (2
2, v thus mainly
++1
full full
fall We define the diagonal matrix i
full w
fulll
I!ulll
3.++1
(149)
15 (w
full
wull
for any j E kJ.
Then we have:
full
2,,++1
7i,e
fill -amin..
X
(W-full t+11
w!!l)
(xl! + $t!!! T
(150)
full 77mmin
XV
Fuull wii maa (wiel) (Stt Stau
48

---

Thus, the following holds:
A fell
fall
full Zi.e
v
1r
21,
My:ammin X V whet Lam
(wi
vv
D +
T
full mmin,
X
whitt full
full !
(151)
full amin,
X
Whit L
Train
Full
(will)
full j
U (1) + +
where we define:
( my a
full XV wail Train (w!eit)
I full
(v.S
(152)
and
U 4,
=
a XV win
full train
(w.fil)
(v
(153)
For U. we notice that:
v
Stal v
||v|2 SStull
(w (.e+1))
Sha max
(2
Di.e
(wo 2.0+1 w
(154)
(w))+1) )
<h max
(witlll 3.++1
whfllt)
Using Lemma K.5 and noticing that has a upper bound, we have:
full 3,6+1
full 2,0+1
w full
3.0
C2T
(155)
(w full 3,41
w full
full 3:6+
full
where represents a positive small enough constant and C2 is positive constant.
Then
we have
full full train
C2h
thereby
we
know that
(U(1)
S
Condttanitt 71 V Vwiii
(Wiel)) ||=
Moreover, have:
(u.Di.t) u
Menin
Tirii
Full Ui..).))
full yeaumn.
XV "iitl Lill (wizil) (v
(156)
Turain
7 V Viga i.full
(w!ll) I|e
Therefore, putting everything together, we have:
full Janin
(will)
f
(w!!ll)
(+1)
Orran
Pall
+ 1 (A..+))) )
Tunia
(e (U + U(??) + Cadaartrr V wan full (w:"i)/ ||2
(157)
Tiuii
/ wan wann Ltu (willl) l
(n Cadmuntrit)
Conddaut
V wan imm (W("l)
y:
Dusin
49

---

Since we both have the condition "with the probability at least exe (-O (ha?) mas)) ))) and "with the probability at least exp (-0 (1))", we can write the condition as "with the probability least 1 - exp (1)".))
Proved.
K.4
PROOF OF LEMMA E..5
Lemma K.6 For any 8 0, with probability at least -0(),, W (Wi .7). it holds
that:
W
j,t
mini
- CT,,
and
mini w 5.0
2 C,
for j E .l....,h,, where C = H (Vr + 8) is positive constant.
Proof Lemma E.5
Since (x)) 1/ 4msoohhh the following holds for any A and xt
I (x + A (()) + (x) A²
(158)
Then have the following upper bound
i Eall
(Wmim))
i full train
(Wmini):
Train
Wiimnnn
A Araii
i
Tiain
Wiiini
A
(x:Be.e11)
mini
Peman
(159)
1 A Lett +
2,1+11
Plgrain
where Arii
= ys (orinn
gamini
Then, taking expectation conditioning Wimini gives:
B
Lowa
mini
A Aguin
|Weinu
L
( mini
omini UiViit+1
mini 6,8
Wiiini
1 E. +
(
(A,++))))
mini
Wiiini
(160)
7Agrain
Similar to the proof of Lemma D.5 we have:
| Ai,ti mini
Meeain
V wiin fulll
(armini A Amm |
17
(161)
CimBa1e 122
V wian E
Wiiini
mini A
train
Maxin
amini
Thrais
In terms of E (Amini
(,44.) ) Wanini
similar to the proof of Lemma D.5 we have:
(1t++)
mini
min
S C2
|
wrm iiiii
(Wrin
A mini
Amain
W
(162)
50

---

Furthermore, using Lemma E.6, have:
TE
Wilt
Trmin
W
A mini traan
W
TR
Whidi
f
Temin
mini
W
A
mini trainn
Wiini Ttain
Ami
||
w
fall
W
mini train
|
(163)
Waini
2
V Wyuiie Limin
Wminn
mina train
+
Waini Litrain
Wimin
A mini
train
Tlgain
2Teenin
V Whinn Leaan
fill
A
mini traa
2
b
Hence, the following holds:
E (Amii
W
Ca
Wrin l train
A
mini train
||
(164)
b
Therefore, we have:
E
L
Ball uain
W
mini
Leain
(waimi
Arain
CaMeran, Sho
Win Liall
(wiineg
mini Auaann
A
(165)
Cim
Warin
full train
Wiini
mim irain
Alyan
Since both have the condition "with the probability least exp (-0 (ha² (Mrrann)))) and "with the probability at least exp (-O (1))", write the condition as "with the probability at least 1 - exp (1))
Proved.
L PROOF OF AUXILIARY LEMMAS OF CONVERGENCE THEOREMS WITH CE
L.1 PROOF OF LEMMA K.
We first focus the mini-batch training.
The normalized adjacency matrix be expressed
an
À
train
0b1
Vag
(166)
20
Q11
Vd
Oin
Apn
where ai E {0, 1} for any node in the mini batch and j E (1,...,,7) n
Then, the following inequality holds on the Iz-norm of mini
mini Buain.
<
S 3
(167)
d yum
where the first inequality has at most 3 terms because there exist at most / terms with a; = 1, and the last inequality follows
aqaa < 1.
Similarly, under the full-graph training, we have:
full 12 aqmin.
din you dmax.
(168)
1
dia yui
This completes the proof.
51

---

L.2 PROOF OF LEMMA K.2
We first focus on the mini-batch training.
For any fixed i (1,-.., Mrminn and (1,...:h) conditioned amini X,
have:
0²
aiaain
X
(w
arninn
X
B
Araain
mini
X
(w.Jin)
a aimin,
X (169)
Burain,
mini
x
1|- n,
where the last inequality due to Brain, X (witin)
N (0,
x|| x²1) conditioned on
amini X.
Then, since z
amini
X(S, Wimini by Bernstein inequality, for any & 2 0, we have:
train,
P mini
Perain.
mini
x
$122
22
2
mini
X
El
aaain x
(170)
I eex (-Ch min E))
Taking union bound over we have:
P mini
Berain.
saini
x
|1
8 Baann
mini
x
/ 5,6 1,..., Rarin
(171)
I MMrrai exp (-Ch min {E",E))
which further implies that, if h 2 Cf log (Nrain/ /0), then with probability at least - 6, we have:
mini
mini aeaioo
| S
mini arrain x
log (Nerain /8)
(172)
for any i == 1,.... Terain where C1 is an absolute constant.
This inequality implies that:
log (munin//))
2
+ Cip
a Oquinn
X
h
2
< + Cip
log (Timin /8)
Aurain 2
2
||
(173)
h
<c 3
(1+
log (Numin/ (8)
h
where the last inequality fowllows by the fact that (1 + 2)) 11 +. for r > 0, which is applicable here. Similarly, we can also prove that:
mini
Ch (1- 1 C2C
1
llog (Frrain
(174)
h
for some absolute constant C2. Hence, we have:
2 mini
c g s &Cap
log (Narain/ /8)
(175)
h
where C3 an absolute constant.
For the full-graph training, we can replace ,3 by dmax as:
mini
C.
1 $ Ci/aa. dmma
log (Nerain/ (8)
(176)
h
where C4 an absolute constant.
This completes the proof.
52

---

L.3 PROOF OF LEMMA K.3 AND K.4
Lemma L.1 Assume that for i * j such that yr * Mj..
Tfull train, atrain.
X
sfull
x
112
2 a
and
train,
X Aminn
2
a. For any m
(m M
IR Ik
we
define
h (w
Thmin mayio'
full train,
X (woalt
train,
and (witin))
Punis Σ
1= mayao'
train,
X
(wiiin)
ammini X, where Wj is Gaussian random vector for any
j
h. There exist absolute constant C, C1, C2 C3 > such that:
[1 (w/"")), 2 C m
C1 Theaiin
and
a² Thrrain
P lb (witmi)
11 2 C2
| o0
2
C33
Proof of Lemma
K.3
and K.4
We first focus on the mini-batch training, Under the assumption,
know that for 7 and yi 7 yj.
amini X
amini
X
a. For any given j {l....,A) h3 and
m with [ loo
by Lemma L.1
we have:
PP
mayor
Birain,
mini
X (w..iin)
mini
X
C2 Thtrain
Csaa Terain
(177)
Aitrain
Let Sthnie 00.
{ (m E R4 ||m| 0o
1.. and U 2
Sthnia 0c.
C2/ (AMuran)) be a O2/ (4Muai))
net covering Stiup 1 in Loo noom. Then we have:
[2 < (Artgrain/ / (C2) Mimin
(178)
For 1,..., h, we define:
Z:j- 1
Phrin
mayor'
-ini agrain, X
(w/inn)
mini aeriin
X
C2 Alrain
(179)
AAyain
Let Pa B by Bernstein ineuqality and union bound, with probability least
Csa?
exp (-Cghpa + Marain log (4m (2)) 2 1 - exp (-Coha?) (Frrain we have:
Σ f=1
Z,
Pa
(180)
where C4 and Cs are absolute constants.
For any S there exists in ll such that:
Im milpo C2/ (4ntaii))
(181)
Therefore, have:
Thrain
mazia'
mini Elminn X
(w)
mini aumann
X
Remin
(182)
Thean
m.yio
mini a
X
miin
mini agran,
X
S Co.².
Temin
where Co an absolute constant.
It is clear that with probability 1 - exp (- (-Chha2/ (Ferain B)),, for any m E Stimi there exist at
least Czhaa (Fmmin 8) GNN nodes that satisfy:
mayso'
mini atrain
X (w.gmim))
mini Bgain,
X
2 Ca,3² Co. |m
(183)
53

---

Similarly, for the full-graph training, replace B by dmax. It is clear that with probability 1 exp (-Crha² (Mmin(max)) )) for any m E Soot -1 there exist at least Cghaa/ (Miainn GNN nodes that satisfy:
Dinie
Bcrain, X (w....))
Scrain, X 2 Cadmaxx = -Cadmax ||
full
(184)
Piruin
where C7, Cs and Cy are absolute constants.
This completes the proof.
L.4 PROOF OF L. AND K.
We first focus on the mini-batch training. Under the assumption, we know that each row of Wigin
follows / (0, k I²)). We define:
Wiini nZz
(185)
where Z Rarr with Zj RIxt CATT~N (),
Using Vershynin's 's result, we have:
P (1Z S vr vh+ 21121116 21-e-
(186)
and
/r PP ( 21-6-
(187)
Therefore, with probability at least - - we have:
mini W3.0
S x (VF
(188)
Since Wiiini E B (Wrini, 7), we have:
mini
Sx(V=+ +
(189)
Similarly, under the full-graph training, we have:
full w
S S ex((++>
(190)
and
Sx (vi + +7
(191)
L.5 PROOF OF LEMMA L.1
We first focus on the mini-batch training. Without loss of generality, assume that m, | lo..
Let ž amini X/
A
X 2 we can construct an orthonormal matrix Q
? Q']
E B=*
Let u Q w ~ N (0, 2I) be a Gaussian random vector with 0 < k < 1. Then we have:
w
mini
mini X Brain,
/||
Qu mini @irain.
X
mini Arain
X
Q'u',
(192)
where u' = (u2,
We define the following events based parameter (0, 1]:
El (7)
(Ca. |ui S 77
(193)
and
Ex(7) [/<
mini a
X
Q' u'
mini ausin
X S
(194)
for all amini
X such that
>mini
X
mini
x 2
54

---

Let {(r) = Ei() n E2(7). We first give lower bound for IP (E) I (E1) (E2).
Since u ~ N (0, x²), we have:
((E) 2P (1Ca |u|
S xx77))
y Caa
2
exp
x²
dx
(195)
2
21
TT
CzB
Moreover, by definition, for any i = 1,
Darain we have:
A
Q'u'
2
.V
0,
Bamin,
mini
X
mini Bemin,
X 1
(
miiii A
X
Barain,
mini
X
27
(196)
Let I = {i:
mini train,
X
a
Smini Irain,
X
2 a
For any i E I, we have:
mini Berain,
x
mini Brrain
X
(197)
minii Brain
X
+
mini a Panin
X
2 <
mmii gzinn
mini X,
Arain,
X
Then we have:
C28 + a
S<
mini Arain,
X,
mini A Pruin,
X >S Cz. a²
(198)
2
and if o² 2,,,9 then:
(
C2
mini 8
X
Beain, X
2
C
(199)
2
a
CC
Therefore, for any I, we have:
P
<
Btrain
mini
X Q'u', Bemn, X > 5
|| | x|| [|2]1 agini x12 ((amun x)
guuin x))
( 1
exp
- de
v
Anii |13]1 amunt
x|2
(Rmmn) x)
gain
x)
66202 ( (ssmit. x) quin x)
1 xz
/ mm
03882
quii
x)
exp
2
dx
(200)
2
C2
mini (arain,
X)
Zmini
x
agninn
/2
Taking union bound over I, we have:
2
((E)) 21
Purain YO
(201)
V
55

---

Therefore, have:
2 71²
(1 1
2v2
P (E)
Auain 7a
(202)
we C+.
Setting 7
obtain:
2 R²
VTa²
1
2v2 V
VTa
P ((E) 2
Te CaB 2 1e a2
Timiis
1v 2
(203)
8
Let T' = [Mmin]] \\ UIU (1)). Conditioning on event &, we have:
mini
Pinis
m,yio
amini X Ariin
mini
urain
X
miyio' (ur)
mini X
mayio' 111
Airain,
X, aurain. X
mini Atrain,
X
Q'u',
Deain, X
emini atran,
X
IET
(204)
myyio
mini Prain
X,
mini Arainn
mini Prain
X
Q'u',
& crain,
tiiii
X
mitiiai Brain,
X
1EZ
=m
y (uI) Blyain,
Σ m.y.o'
Reain.
X
Q
Alrain,
mayao
[1]
mmiin Birain,
X,
Brain,
mini
X
Birain.
mini
X
Q'u',
Bennnn
mimini
X
emini Benin,
X,
REZ!
where the last equality follows from the fact that conditioning event E, for all i E I, it hold that:
Brrain,
mini
x
Q' uL, mmini
arrain,
X
C2
mini Berain,
X.
mini atrain,
X >
(205)
We then consider two cases: in >> 0 and u < 0, which occur equally likely conditioning on E. Therefore, have:
h w mini 11, 2
inf >0
max
w
(1)
11-11 (w (w.rinn |1,3
2
1
(206)
where we define (1) w f
ui
mini trann
X
miii train,
X
Q'u' and w/ mini,(2)
u1
train,
mini
X
famini x11 Q'u'. By the inequality max { [|al||
|lbll2]
||a b bl2 /2, we have:
h W mini
|1B 2 inf | (w/mial.ca)))
(w/ginl.co)] /2/8
2 2'
(207)
s0.0
20
By Eq 204 we have:
h W (2) / w mimii..))
mini Braiin,
X +
mini m Mraain, X,
(208)
Zez'
where we define: m
mn (0' (u(²)
mini aggin.
X. augan,
X
aqain.
mini X
I'u',
mini
(209)
o u
a Arrain
amini
X,
mini Arain,
X
smini A
Q'u',
mini Aegain.
X >)
56

---

Note that for all i I', have ys Y1 and since u, ui
train,
mini
X,
a
rrain
X >> C2B a²/2 /2 2 0. Therefore,
(2)
have:
11
mini
mini X
Q
mini X
(210)
u1
Arain, X, Bcrain. X
arain X
Q'u', again, i > 13)2000
20.
Therefore, m 2 0 for all i E I' and
( ( (.) (. ( = yn
mini
X
Σ
m ;
mimi
X
(211)
6E2'
Then we have:
w (1) 1 (wrtim m2m) ||
91
m Aenin,
miini
X
m. Btrain
minin
X
(EZ'
(212)
my
mini
X
+
Σ
l
mini
X,
gemini Airain,
X
Atain,
mini
X
Since the inequality above holds for any u > 0 and u < O. taking infimum, we have:
1a (w..iin.c)) h (w. minim. (2)
inf " so.11 (2)
2 m.
(213)
<p
Therefore, we have:
[| ( mimi ||s 2 mi /
1
2 3
(214)
Since mi ||m|] and IP (E)
2²a= P
&CCCommins have:
I|, 2 C [|ml]
Cia² Parain 3
(215)
where C' and C₁ are absolute constants.
Similarly, for the full-graph training, we can replace by dmax as:
P ( (wr"")ll 2 C2 |mlloc]]
Csa²
(216)
Terain dmax
where C'2 and C33 are absolute constants.
Proved.
M PROOFS OF THE MAIN THEOREM AND LEMMA OF THEOREM
M.1 PROOF THEOREM G.5
Lemma M.I. (Lemma 4 in Ma et al. 2021 For any two distributions P and Q defined on the hypothesis space, and any function f(-) with domf in this hypothesis space, we have:
Ex-e S DKL (QIIP) + f(xpe
Lemma M.2. (Lemma 2 in (Ma et al.
2021
Suppose 1 22, ... Fn independent random n. Let 1 Σn Ft. Then, for any C > 0.
variables with a; I 2, S b, Vi 1,2, ..........................
2002
TP P( - (x))
C) < 2e E ur)
57

---

Lemma M.3. (Lemma in (Ma et al. 2021 If x is centered random variable, i..., E (x) and if 1C > 0, for any C2 0,
P (|x] > C2) 2e CiC
Then, for any C₂ 0,
C² E (eCu)) S Td
Proof of Theorem
G.S
We going prove the result by upper-bounding the quantity
Cu(Lrest
(Wmini lull. lests
(Wmini
A mini. First, we have:
irain
Cu Lies
(mmini A
2)
full
W
A
Araini
mini
2
EEwming
CCo (Leaa Wiiin
Avea
Lisain
Wiiiin
Agran
)]
(217)
<DxI(Q11) In EnE Exuiii wi [elLuall
(Wiiii
A.
- Laat (wirte A A
where the last inequality uses Lemma
Next, upper-bound the second term in the RHS of 217 Here the term A Ewam.p [ee (LueeeWaie A - (Wrine A is random variable with the randomness coming from the sample of node labels in training dataset, and P is independent of node labels y from train- ing dataset. Applying Markov's inequality to the term A, we have for any CG 0, with probability at least 1 - CG over from training set,
I
Ca By ty-ttinnning [A],
(218)
and hence,
A
triiiigg set [A] In
Eraiiinning set [A]
(219)
Co
Cs
Then we need to upper-bound In Ery-training set (A]. We can rewrite it as:
In Ey--nniingg set [A]
Fynmaining sei F waii (e (Wain A
Endt (Wiite mi
(220)
In Ewpin Ey mriinng ser (u (Wihi Agdl) Ema (wiste Anin)
For fixed model with model parameters Wimin we have
( (nas (Wiii
Abd)) A -Lgg (Wrie A
E trosiiiin
Wiit And)) (
- Lal ( (Wiine A Aniul) fill (Woin Anitt -Lnt (Woill Amin }}
y training sei
(221)
C (nnn (Will (ma) (
of (wrine A )
(La (Wrisi .Aii)) - Loa (Wiin _Agil)))
F www.iiiggg
=e (Enca wiriii
(weiii Anid'
Lill (wiisi Anin) ) oaan (Wain _ mini
Eyy traaining set
( (Wiin Amin)
End (Wime
A man
In the following, we wil give an upper bound on Eriiiin set
that is independent of Wriini For the entire training dataset, i,tul! WWiii
À mini train
can be written as:
i full train
miii
Arrain
Á mini
mini
2
(222)
Tiurain ietraining set
where the node labels are independently sampled. Hence, full
Wiinn
À mini is the empirical
train
mean of Parin independent Bernoulli random variables and full Irain
(Wmini
mini train
is the expectation
of i full train
Wriini
Á mini
Arain
By Lemma M.2 for any C₁ > O.
P
full Turan
miiini
mini train
full Ttaann
mini train
2 Ci) 5 2e 2mmm
(223)
58

---

and hence, by Lemma M.1
have
[e Cu (Gu(Lija Celainn(wmii (Wiin
Agan) Lise (wam Amu))
c²
Btainingg set
(224)
Therefore, we have
e (Waid ( - (waini Amii)
In A < In Bp
Trrgin
(225)
Ch
=U
4fmmin
Finally, we get
C. Cuus (Wiini A A
2) Lea Wiin
A
mini
teain 2)
<DxI(Q|P)) + In Ewainip [el [e(nual (weaaai (Wrine A
Eir (wiin A
(226)
C
<DxI(Q1P) + In
+ U.
Cc
Aruaia
Hence, we have the final result
Luest
minin
full
②
che + +0)
(227)
< <Lni
Wiiin
Againi 2)
[Kz((e)P)+
C.
Co
4Meain
M.2 PROOF LEMMA G.6
Recall that
U In Ewammp Ca a (rea (wsii (Wiis Adet) 1. (Wain A
(228)
First, we focus the term Lest
Wiimni
A full A
fall
Wiiini
A mini
Arain
Set zmini (y:)
||
yil P. Vi E train set and 'test
(y,)
||
yill Vi test set. Then we have
Luss
Wimini
A
I Lirain
Wirini
Á
mini train
Byyn sell
Lest (y:)
Byrottain
Arain (y:)
(229)
Theest
Thteain
j
sittrann
lest ( (2:))
mini
Preainn (yre)
Thest
Thrrain
setrain
Furthermore, we define Eirain,i
Diag
miin train,
X (Wminn))
> 00)
IR to represent
whether the j-th element / x. (Wrfill)
is more than (1) is zeroed out (0). Then
have:
mini Aeraaa
X
(Wrmin))
)
smini Ptrain,
X X(E [main,, Tiini
(230)
Similarly,
have
amiii X (Wmini+) 7)
minn X irain, Wiinni)?
TT
apest X (Wiinn)
full X Exest Wmini) and
ffull X (Wimini ")
full Gest
X(Er test. Wimini T
we set f(y:)
Thean train ys))
with Vi train set and 9(y;)
pamini
(yy) with Vj E test set and
Plcc
Ammin min Ferrann 11est)
59

---

Hence, we have:
f(y.) ,(y,)
1
Mess (y;)
Lran (y:)
lest (y,)
Auain (yrs)
Pmmin
Winme)) /)
(Wrmini >>
11
Besst.)
Yumin
11
Ekpann X (
aesin, X
Wiiini
Tlmin
||or
full akeett. X
W-mini
a X
full
(Wrminn
Omxin
a Irain.
mini
X
W
Arrain X
mini
(iiini
l1r
|Aaest X
full
WWrmini
Σ
full Beest
X
Wrminii
Eunn, T
(231)
mmnni X
WWrmin'
mini Pirain,
Wprmini
E'min,
11
inin
X
W
Emmin. 1 +
Wrrmin
Erain 11?
Vhmin
Wmini
Eitain.
Dieat ||
full y
Wiini
Eest. |1
full 3usse.
CF (Cw + 1)
Domin
full [best.)
mini agaan,
d
+
full 24est.
2
(F)
Cp (Cw + h)
Brest.)
Renin.
+
+
Agrain
Tlmin
Cr (Cw + h?
full
+ + gflllmminn
Almin
where the penultimate inequality follows ||Erainn p Σ Erai..
h, Ditain Eieu, p: EErain. El S 2h because E; is diagonal matrix with (Ei) E {0, 1} for any j E (l....,,h, h}. The penultimate expression is exactly the distance function
defined in Definition 1. 5full-mini = || |
irain amin [| and الاا = lest.j" ffull
.I.
+ | ||?
j.j
is a constant based on the split of training and testing.
Hence, have
Laust
Vprmini
Auest
Á Full
full Zignin
Wyrmmnn
A mini irain
(y,) (y,)
Σ
Laam (y.) Puria (y:)
21teest
Dramain
jivees
veitain sel
Airain, test (B,b) min
Σ
Σ
(232)
SEtrain &
CF (Cur + 1)
min
Σ
0,
shull
gfull-mini
Denin
Eless sot
Then mainly focus the elements of gfilllmini
Recall that full bran.i.j
full and miin irain,
mini where aflll a
mini
(0, 1) represents whether node receives message from node j (1) not (0).
60

---

Hence, we have:
full prain,
mini B
1
1
mini
(233)
do
aout.full
d.
gut.mini
where
V
We fix the batch size b. Notice that when the fan-out size / increases, de mint may increase and
we have four cases: (1). Øij mini keeps 0 given d
0, (2). aij keeps O given dij
full
(3).
mini keeps as given ag a kg
1, (4).
mini
becomes from given di
Then
bj
we have Σj=1 Vatii Vagnon i3
mini are non-increasing when / increases oj
d
mini /aam
at the first three cases. However, at the fourth case, we may both have
and
Hence, 8 mfull-mini has overall non non-increasing trend when 3 increases but small non-monotonic fluctuations exist.
We fix the fan-out size B. Notice that when the batch size increases, din.mini may increase and we
have three situations: (1). di) keeps given dلlll O, (2). ag keeps as 0 given aty = 1, (3). Then we have dfull-mini is non-increasing when increases.
mini keeps given bi
Note that fan-out size 3 plays more dominant role than batch size in influencing generalization. only increases the number of sampled neighbors
This is because the variation in fan-out size but also potentially alters the structure of the adjacency matrix of node i - by introducing new connections during mini-batch sampling (i.e., the fourth case). This structural change can lead to more significant variations in generalization performance. In contrast, changes in batch size b primarily supplement the number of sampled nodes without modifying the adjacency structure the node i.
Since Vy, b) is proporional to sfull mini
mini
Arain
full
a
arain, i
mini
|| and A b) is proporional
to K(y,,yj- B, b), have the upper bound A b) of Leest WWrinni A A
I (Wiini A mini
keeps non-increasing when b increases, and overall have the non- non-increasing trend when 3 increases but small non-monee non-monotonic fluctuations exist.
Finally, we have
[ Ca (oooo (Wiiii, - 1.ll (Wais, A A
U In E
< In Ewampp cc0(2,0)
(234)
=In(C
=C,A(B,0) b).
This completes the proof.
N EXPERIMENTS
N. TRAINING SETTINGS
Testbed: The experiments, except those on the 100M,, 100M, are conducted on a machine with 512GB of host memory and four NVIDIA A100 GPUs, each with 40GB of memory, inter-connected via 900GB/s NVLink 4.0. The experiments on ogbn-papers Smppers100M.... 100M are run on two machines without GPUs, each equipped with 1024GB of host memory and interconnect bandwidth of 50 Ghps.
61

---

Table 3: Datasets Infol.
Datasets
#Nooes
#Edges
Avg. Degree
#Classes
Features
Reddit
232,965
11,606,919
50
41
602
Ogbn-arxin
169,343
1,166,243
40
128
Oggbn-products
2,449.029
61,859,148
25
47
100
Ogbn-papers 10mperss00MM 100M
111,059,956
1,615,685,872
15
172
128
Table 4: Datasets Info2.
Datasets
Train/Val/Tess
Reddit
152,410/23,699/55.5
Ogbn-arxiv
90,941/29,799448.
Ogbn-products
955,922/48.9800222444..
Ogbn-papers 100M 1,207,179 125,265/214.338
We evaluate convergence performance using three metrics: iteration-to-loss iteration-ta too- accuracy, and time-t-accuuray. These metrics measure training progress towards target convergence point in terms training loss or validation accuracy. For all GNN models and datasets except ogbn- papers papers100M, 100M, the target training loss is defined the maximum loss observed over 100 consecutive iterations at the smallest batch size, provided that the variance of these loss values is below 5 x 10 Similarly, the target validation accuracy is defined as the minimum accuracy over 100 consecutive iterations at the smallest batch size, provided that the variance of these accuracies below 4 x 10-1 Note that the defined target training loss and the defined target validation accuracy are applied across all hyperparameter settings for the specific model and dataset. For ogbn-papers papers 1 100M, training is limited to 200 iterations due to the extremely large graph size and training time constraints. Note that using the smallest batch size as the reference is common in prior works (Bajaj et al. (2024), and serves conservative criterion: because fluctuations are most pronounced under the smallest batch size, requiring stability in this setting to prevent mistaking transient variations for convergence and to provide a uniform benchmark across batch sizes. Moreover, by enforcing a variance threshold, this definition remains unbiased toward larger smaller batch sizes and offers fair basis for comparing convergence across settings. 2). For generalization, test accuracy is used as the metric in the training iteration. For system efficiency, measure the training throughput in terms of the number of target nodes processed per second (number of nodes/s). This metric ensures that throughput reflects the rate of training examples processed.
Metries: 1).
We run all implementations using Python 3.8.10 10 and dgl>=1.0.0. The uniform neighbor sampling used for mini-batch training. Due the massive comparisons, adding error bars every figure would make them overly cluttered and difficullt to interpret. We have repeated all experiments at least three times using different seeds and observed low variance. For example, in Figure [6] the standard deviation of the final accuracy is less than 3.17%. This small variance does not affect the observed convergence trends, which remain consistent across runs.
N.2 METRICS: ITERATION-TO-LOS
Simple mathematical derivation. distributed systems with two devices, assuming:
Per-iteration calculation time leat' Leat (b 3 + b)/C, where b is batch size, 3 is fan-out size, and compute capacity (nodes/s);
Per-iteration communication time leomm Lcomm = b/ H for mini-batch training and leomm (b b)/ for full-graph training, where H the bandwidth.
time-to-accuracy n x (teal + teamm), where itcration-t--accurae
Consider two training setups:
Full-graph training: by 1000, 31 50, 10 iterations converge
Mini-batch training: b, 10, 3, 10, n. 10000 iterations converge
62

---

Under the same compute power C' 1 node/s, but different bandwidths:
High bandwidth: Нд = 1000 nodes/s
Low bandwidth: H, 0.1 nodes/s
Plugging into the formulas:
High bandwidth: 1).Full-graph: = 10 x (3000-50+1000 +
1000-50++000)
= 5.1051 x 10
1000
2). Mini-batch: 10000 x ( [10-10+10 + 1000
1.1001
10
Therefore, Full gall- training is faster.
Low bandwidth: 1). Full-graph:
10 x 1000-50++000 1000-50-
1000
5.61 10%
0.1
2). Mini-batch: = 10000 x ( (10-10+10 + 10
10
0.1 1
Therefore, Mini-batch training is faster.
This example shows that cone-to-accuree may flip conclusions depending on hardware, while iteration-to-accurayy remains stable.
Experiments. The vanilla distributed system (i.e., the standard implementation without any optimiza- tions) is used for full-graph training, and the Distributed Data Parallel (DDP) technique (Li et al. 2020) is applied for mini-batch training. We examine a three-layer GraphSAGE model on Reddit and three-layer GCN model ogbn-products. These models include normalization layers and are trained using a cross-entropy loss function and Adam optimizer with a learning rate of 0.01. The target validation accuracy is set at 0.9 for egbn-produce 2000 and the fan-out size is [5,10,15]. To simulate infinite bandwidth (i.e., bwl), we use single GPU CPU. For limited bandwidth (i.e., bw2), we use two GPUs interconnected via 900GB/s NVLink.
and 0.95 for Reddit. The total batch size is
N.3 CONVERGENCE
For experiments on one-layer GNN models, the basic setups are without drop-out or normalization layers and with ReLU activation, and SGD optimizer for both full- full-graph and mini-batch training. For experiments in more general settings, multiple-layer GNNs are adopted without dropout layers and with ReLU activation and Adam optimizer for both full-graph and mini-batch training. The SAR system MMsttaaa 2022) is used for full-graph and mini-batch training on oghn-papers Iipers0000 100M via the gloo backend, while other datasets are mainly trained on a single GPU.
Convergence of one-round GNN trained with MSE. To align with theoretical analysis, we use iteration-to-low here. The details are as follows: 1). The target training losses are 0.0226 for ogbn-arxiv, 0.0225 for reddit and rgbn-producte and [0.005, 0.0054, 0.0065] for ogbn-papers 100pers10MM 100M on GCN, GraphSAGE, GAT, respectively. 2). When varying the batch sizes, the fan-out size is 5. 3). When varying the fan-out sizes, the batch size is 500 for ogbn-arxiv, agbn-products and reddit, as well as is 10000 for for ogbn-papers 100M.
Figure 8 shows the iteration-to-loss for four datasets under GAT, GCN, and GraphSAGE trained with MSE across different learning rates and either varying batch sizes or varying fan-out sizes.
Convergence of one-round GNN trained with CE. To align with theoretical analysis, we use iteration-to-loss here. We set the original multi-class node classification task as the binary node classification task. The details are follows: 1). The target training losses are 0.51 for ogbn-arxiv, 2..32,,.325,00 for reddit on GCN, GraphSAGE, GAT, respectively, [0.08,0.051 (..0511..051 for ogbn- products on GCN, GraphSAGE, GAT, respectively, and [0.009, 0.0087, 0.0087] for ogbn-papers 100M on GCN, GraphSAGEs GAT, respectively. 2). When varying the batch sizes, the fan-out size is 5. 3). When varying the fan-out sizes, the batch size is 500 for ogbn-arxiv, ogbn-products and reddit, as well as is 10000 for for ogbn-papers 100M.
Figure I0 shows the ceration-to-loss for four datasets under GAT, GCN, and GraphS trained with MSE across different learning rates and either varying batch sizes varying fan-out sizes.
Convergence in more general settings. For the comparison at the dimension of batch size and fan- size, 3-layer GraphSAGE models with hidden dimension of 256 for reddit, ogon-products,
63

---

5000
1920
bo0nt
1350
1070
23045
2000
34R5S ST77 2305 3135
170
216
2024
6572
1000 1e3
4017
11300
(540
2220
STED 2006 24EA7 A2A 2000
176
211
2P17
0.80
Gots Learnang Rate
GAD AOEE COOS
Learning Rate
Learring Rate
(a) Reddit, GAT
(b) Products, GAT
(C) Arxiv, GAT
(d) PapersI00M. GAT
11600
10200 2006
2000
2001
07711
MANT FAITS
1010
N174 107M
2506
5135
Learning Ritt
Learning Rabe
Learring Rate
Learring Rate
(c) Reddit, GCN
(1) Products, GCN
(g) Arxiv, GCN
(b) Papers 10UM, GCN
35-05
30443 2712 3973 192 4313
S0073 77677 20132
aas 6iz os0s oda 2.003 Learning fate
882 BLa oods odi Learnang Rate
Gáa adis oá COBS
QU6C2
Learning Rate
Learring Rate
(i) Reddit, SAGE
Products, SAGE
(k) Arxiv, SAGE
(I) Papers 100M, SAGE
Figure 7: deration-to-loss for world datasets for one-round GAT, GCN, GraphSAGE across
different batch sizes and learning rates under MSE.
1929
soeet 1393
23710
33145
S1860 2001 29521
4147 (190
116
4:15
4211
103S R054
3an4
13216 3396 20721
W371
284
276
2a05
odis
6905 8825
oois 831
8825
660 ao15 8:11
60BS
0,00005
(a) Reddit, GAT
(b) Products, GAT
(c) Arxiv, GAT
(d) Papers100M. GAT
Ste
00s1 2010
2000
4442
2001
20543
2000
9996
7830
1431
M01
1959
2003
2008
Leariing Rate
Leaming Rate
Leaming Rate
Learring Rate
(e) Reddit, GCN
(f) Products, GCN
(g) Arxiv, GCN
(b) Papers 100M, GCN
12903 2007 203.0 2010
-0AC J2004 SmTR
22300 bache 200m 2043
12360 33272 20077
10011 18137 20157
3227
aais sds oois adt 2005 Leariing Rate
8825 eáa oois a21
Bals 6da aois ads 6005
0.206s5
00003
Leariing Fabe
Learrine Rube
Learring Pata
(i) Reddit, SAGE
(i) Products, SAGE
(k) Arxiv, SAGE
()) Papers SAGE
Figure 8: Iteration-to-lor for real-works datasets for one-round GAT, GCN, GraphSAGE across different fan-out sizes and learning rates under MSE.
and ogbn-arxiv, and 2-layer GraphSAGE models with hidden dimension of 128 for ogwn-papene 100M. The activation function is ReLU function. The optimizer is Adam with a learning rate of 0.001 and a weight decay of O. Due to the extremely large graph size of the rgbn-papers 100M dataset and limited computational resources, we use separate machines for full-graph and mini-batch training on this dataset, making it infeasible to compare system efficiency between the two methods.
The target losses are [0.2, 0.1, 0.8, 1.52] under CE, and [0.005, 0.005, 0.013, 0.0055] under MSE for the products, reddit, arXiv, and papers 100M datasets, respectively. The corresponding target accuracies are [0.918, 0.962, 0.708, 0.599] under CE, and [0.89, 0.946, 0.676, 0.5] under MSE for the same datasets.
Figure IT (under CE) and 12 (under MSE) illustrate tom-ttoaccuracy on GraphSAGE across varying batch sizes and fan-out sizes for
ogbn-arxiv and ogbn pate-splppssMM
Figure 14 (under MSE) and 13 (under CE) illustrate -ome-to-cccuracy on GraphSAGE across varying batch sizes and fan-out sizes for ogbn-products, ogbn-arxiv and oghn-papers11000 100..
64

---

4000
0ART- 520
2064
50355
20331
-0307
9534
20055
13806
25084
12399
10013
6026
1005
AIVE
0.00
0.00
0000 Rata
2.00
6.200
Ratt
Learning Rate
Learsing
(a) Reddit, GAT
(b) Products, GAT
(c) Arxiv, GAT
(d) 100M GAT
Bvom Rve
B400 038
1694
Ba S2
31753
36480
201224
+6022
30099
20122
13326
7821
-104
22740
7154
Leamiing Rate
Leamnngg Rata
Learning Pate
Learring Rate
(c) Reddit, GCN
( Products, GCN
(g) Arxiv, GCN
(b) Papers GCN
25272
30344
1003
5421
11227
16:25
39702
12003
3273
1534
Derm
5513
22553
Bemm
1456
3030
2564
2005
1479
5001
21477
6870
12:004
37505
20197
0.55
6:011
0.00
20005
0.003
Learinng Rata
Learning Rate
Learring Rate
Loarningg Rate
(i) Reddit, SAGE
ii) Products, SAGE
(k) Arxiv, SAGE
(I) Papers 100M, SAGE
Figure 9: Iteration-to-lur to-soss for one-round real- world datasets for GAT, GCN, GraphSAGE across
different batch sizes and learning rates under CE.
Dene Spe
31242
1163
14514
3192
51853
X315
19:51
Learning Rate
Learning Rate
Learning Rate
LAATTS nng Rate
(a) Reddit, GAT
(b) Products, GAT
(c) Arxiv, GAT
(d) Papers 100M, GAT
11:21
105:00
Pe0000 500
50615
71420
1942
11997
14535
31395
42240
215.1
30516
22429
22135
12571
0027
J01E5
2011
+1541
80:00
10.8
GA1B
0.00
1:00e
3,0000
0.000
2000
0.00
5.500
ondes
oxeet
Rate
Learring
Learring
(e) Reddit, GCN
(I) Products, GCN
(g) Arxiv, GCN
(b) PapersI00M, GCN
Spe
3272
1531
0008
0.00
ca00s
1900
0O0L
Raate
Learning Rttee
Learning Rate
Learning Rlate
(i Reddit, SAGE
i Products, SAGE
(k) Arxiv, SAGE
()) Papers 10M, SAGE
Figure 10: feration-to-lort loss for one-round real-worle datasets for GAT, GCN, GraphS across
different fan-out sizes and learning rates under CE.
1kk
730
7LD
/12
1k
350
920
8/9
880
.120
1k
155
125
10
1036:
150k
240
250
230
240
253
235
250
240
310
270
250
320
700
290
303
20k
5k-
450
.60
340
300
480
450
529
470
440
470
440
450
460
440
306
100k-
10k
116
100
100
100
150
100
175
Bull batch
230
250
250
293
full batch
66
10
15
25
50
5
10
20
25
50
5
25
50
100
nelghbors
nelgnborr
neighbors
Fen-out
Fan Size
Fan-out Size
(a) Products
(b) Arxiv
(c) Papers100M
Figure 11: Iteration-to-ace of multi-layer GraphSAGE under CE across varying batch sizes and fan-out sizes.
N.4 GENERALIZATION
Generalization of one-round GNN trained with MSE. For test accuracy, the numbder of iterations are 5 10s for GraphSAGE and GCN, or x 10s for GAT, for ogbn-arxiv, ogbn-products, and reddit.
65

---

3420
0920
1236
12.30
1190
8atcn 5120
34
1k-
2150
1620
2:80
1720
1920
1890
1830
1890
Batch Size
14-
544
514
81.
11.4
50k
1300
1315
1206
1250
1230
10k
2310
1830
2390
3250
2330
2000
860
300
150k
1230
1200
12:30
1235
batch
50k
1990
900
1720
1710
1790
1880
1030
1500
1618
1630
3000
939
20
30
30
nelghbors
nelghbors
Fen-out Size
Fan-out Size
(a) Products
(b) Arxiv
(c) Papers100M
Figure 12: Iteration- -occooc-tt-cc-oooooo-ooooo of multi-layer GraphSAGE under MSE across varying batch sizes and fan-out sizes.
0.14
0.37
12.00
354
Ik
385024
100,93
221.
25h-2
3034
394
2.96
2:20
3.54
3.00
314
4.58
541
4:3
1.54
18:51
0.53
100
506
308-
3.47
3.25
4:5
4.35
4.00
4.11
4.55
4.15
4.55
4.27
4.25
5.00
5.15
100k
242.45
119.35
545.03
5023
900.33
Iil
16000
55
20056 33
27240-72 72
10007
30
10
15
25
20
5
10
20
25
25
30
100
(a) Products
(b) Arxiv
(c) Papers Papers1OOM 100M
Figure 13: Time-to-accuracy (s) of multi-layer GraphSAGE under CE across varying batch sizes and fan-out sizes.
8900 5100
104 11:38
16: 12:22
34.
13:32
10.03
11.22
11.72
14.70
23.00
12.61
14.26
14:45
14:30
57.45
36.32
16.21
19:01
11.54
23.25
13:09
17.23
13.80
12:37
13.00
10k-
43.00
115:91
243.59
53.02
200.9
48.78
52x 13.63
15.34
1:21
24.44
18%
35.79
13.35
21.40
16.42
25:35
Battch
3024
3324
04
15:24
13:30
15.24
18:53
15.73
30.74
23.25
63:23
17.50
10.53
22.32
100k
Mi
LLaza
703510 10000100000000000000 3033066-2
20
20
50
20
20
50
50
300
(a) Products
(b) Arxiv
(c) Papers 100M
Figure 14: Time-to-accuracy (s) multi-layer GraphSAGE under MSE across varying batch sizes and fan-out sizes.
And the number of iterations 1 10 for ogbn-papers 100M across all GNN models. The learning
rates are 100.5,..0,.0.25, for ogbn-arxiv, ogbn-products, and reddit, and [0.00025, 0.0002] for 1irpperrOOO...... 100M. The batch sizes and the fan-out sizes are consistent with the settings used in the experiments measuring time-t-aaccuracy Other settings are the same as Appendix N..
ogbn-papers
Figure 15 16 shows the test accuracies for four datasets under GAT, GCN, and GraphSAGE trained with MSE across different learning rates and either varying batch sizes or varying fan-out sizes.
Generalization in more general settings. The settings are the same the general settings in Appendix N..
Figure 17 (under CE) and 18 (under MSE) illustrate test accuracies on GraphSAGE across varying batch sizes and fan-out sizes for reddit, ogbn-arxe arxiv and egbn-papers100M,
N.5 COMPUTATIONAL EFFICIENCY
The settings are the same as the general settings in Appendix N.3
Figure 17 (under CE) and 18 (under MSE) illustrate training throughput as the number of processed nodes per second on GraphSAGE across varying batch sizes and fan-out sizes for reddit, ogbn-arxiv and papepssppps0
N.6 FULL-GRAPH VS. MANI-BATCH TRAINING AFTER HYPERPARAMETER TUNING
The settings are the same as the general settings in Appendix N.3
66

---

Loaning Nate:
5.03 0222 0322
LOINIIN Rute
E015 0022 0.25
Leaming
cats 022
Lourtig
27.30
2422
0.34
11M
35t
Sinu
(a) Reddit, SAGE
(b) Products, SAGE
(c) Arxiv, SAGE
(d) TapersLOOM, SAGE
Leaning Pate
C0s 022 063
10.03
Loaning Note
1003 0,22 0823
37.37
Leaning late
000 3.00
14:71
11
75:00
15:32
74.04
51.41
34:37
14-95
14.50
14.00
32.30
23:43
12.85
01:00
19:22
54:34
$7:09
10:09
52:43
14:42
14:41
12:11
14:17
17:07
UMC
0.4
36
Loc:
35t
108c
Betch Sizw
Satch Size
Batch Size
Tottal Batch Siee
(c) Reddit, GCN
( Products, GCN
(g) Arxiv, GCN
(b) Papers 100M, GCN
Leaming Rate:
D013 0.39 C.029
6C.24
Loantra Rate:
0013 0.5 5:233
31.12
52.54
Leantrg flate
D013 0.33 5.023
35.29
15:33
15:24
Leursnng Fule
12.44
75.27
42
12:33
31.05
51.77
5222
24:70
14:50
$4.00
14.00
26:07
20:13
32.80
N6.7
NL.3
36.77
42.42
19.20
03:04
05.15
14.00
14:03
11.00
14.00
12:30
0.5x
124
14
12c
L0c
351
500k
Batch
Size
Batch Stzee
Batch Size
Total Butch
Stoo
ii Reddit, GAT
Products, GAT
kk) Arxiv, GAT
1I Papers 100M, GAT
Figure 15: Test accuracy for real-world datasets for one-round GAT, GCN, GraphSAGE across different batch sizes and learning rates under MSE
Loaiing Rote
500 022 5.05
02
03.22 8542
Loaming Rate
200 062 5.00
40
3731
Leamera Raal
2.00
20.00
53 50 5750
Lasminn Rate
02.90
0200
23.09
120
56.39 56.76 30.33
33.24
23.00 30.22
2003
Sizee
Fanerul Sioee
(a) Reddit, SAGE
(b) Products, SAGE
(c) Arxiv, SAGE
(d) SoperssO0M, SAGE
2013 022 0.00
Loambigg Rate
5003 0/2 2005
Leameng hale Rale
2003 0:3 c.09
Leariig
123
Launing/aah Pate
22.30
12:33
24.00
15:05
10
50
10
50
10
(c) Reddit, GCN
(f) Products, GCN
gg) Arxiv, GCN
(h) Papers Ceerrss000M 100M, GCN
Leaming Rate
5003 053 copc
Loarning Ratt
2013 063 2.00
Leaming Rate
5013 012 0.03
15.00 20.20
Lesmiing
20.07
24.20
20.72
14.20
32.00 29
20.39
10
35
50
10
50
30
10
50
Fen-out Size
Tat-out
Size
Far-out Size
Farwell Siae
ii) Reddit, GAT
Products, GAT
(k) Arxiv, GAT
(I) Papers GAT
Figure 16: Test accuracy for real-world datasets for one-round GAT, GCN, GraphSAGE across different fon-out and learning rates under MSE.
RELATED WORK
Koy Bushh ii @ tupiniee Megrengi literature presents conflicting empirical findings on the GNN performance (i.e., convergence and generalization) and computational efficiency:
anaerabi 5 Tark a 20R1 ( 2202 Hn
achieves higher
model accuracy and faster convergence than mini-batch training, while others (Kaler et al. 2022
Zheng et al. 2022 Zhao et al. 2021 Bajaj et al., 2024) present contrasting findings. Furthermore.
due to the message-passing process, performance insights from DNNs (Keskar al. 2016 You et al.
2019
Smith 2017] Golmant et al. 2018 Zou et al. 2020a Bassily et al. 2018:] 1018:NNabavay Nabavinejad et al.
2021
Hauswald et al. 2015) cannot directly transfer GNNs.
67

---

70:63
26.94
10:17
3k-
$3.00
55.99
56-97
$3.50
85407 5.00
54
27
224
01:14
70.70
70.44
71.55
70.23
74
70.74
3034
59k
76.70
70.13
12.76
70.02
3355
76.75
LAM
57
25
56.12
$4.00
26.20
20.11
15
20.25
10
72.16
20.37
12.37
70.22
10:22
10
25
01
25
50
100
out Size
Fan out Size
Fan out Size
(a) Reddit
(b) Arxiv
(c) Papers 100M
Figure 17: Test accuracies of multi layer GraphSAGE trained with CE across varying batch sizes and fan-out sizes.
3x-
95
FM)
3A 14-448144 cB 5006 5255.00
Sato 500
234-
53x
04.63
52
34.06
14.57
34.00 10
3Dk
60:00
07
4129
100%
10k-
23
5219-00
-300
3034
84
24.06
35
5.50
0.
41.0
Mil 34534000000 3479 ce 3081-29 5400.00
3311: Co
16
(a) Reddit
(b) Arxiv
(c) Arxiv
Figure 18: Test accuracies of multi-layer GraphSAGE trained with MSE across varying batch sizes and fan-out sizes.
13.29 4080
18
8.35
0:48
0.79
6/8
300
6
43.54
30.31
17332
Tavest Stue
fen-out
23
Peniout
130
(a) Reddit
(b) Arxiv
(c) PapersI0oM
Figure 19: Training throughput (# nodes/s) of multi-layer GraphSAGE trained with CE across varying batch sizes and fan-out sizes.
100
14
E300
173.00
43.44
00:0
69.25
54.8
18-
2.05
021.02
$17.11
faveul
170
13
2
Penoou, Sioe
330
(a) Reddit
(b) Arxiv
(c) Papers 100M
Figure 20: Training throughput (# nodes/s) of multi-layer GraphSAGE trained with MSE across
varying batch sizes and fan-out sizes.
The only existing comparison work (Bajaj ct al. 2024) between full-graph and mini-batch GNN training empirically evaluates overall performance but does not investigate the impact of key hyper- parameters (e.g., batch size and fan-out size) on model performance and computational efficiency, thereby overlooking the trade-off's achieved by tuning these hyperparameters. Recent efforts (Yuan ett al. 2023 Hu et al. (2221) focus on these hyperparameters but remain limited. For instance, Yuan al. Yuan et al. 2023) lack theoretical support, consider only limited batch sizes and fan-out values that are far smaller than those of full-grae -raph training, and overlook the interplay of the batch size and the fan-out size. Hu et al. (Hu et al. 202T] rely on gradient variance to explain the role of batch size but do not consider fan-out size, thus their explanation conflicts with their empirical observations.
Existing theoretical analyses of GNN training typically focus on singular aspects (e.g., convergence, or generalization), overlooking key graph-related factors (e.g., irregular graphs with nodes of varying degrees, the difference between training and testing graphs in mini-batch settings) and the impact of non-linear activation gradients. For convergence analysis. Yang et al. (Yang et al. 2023) and Lin et
al. (Lin et al.) 2023) apply the NTK framework by assuming infinite- width GNNs. Xu et al. (Xu et al. 2021) analyze multi-layes linear GNNs. Awasthi et al. (Awasthi et al.] (021) employ PL conditions to study one-round GNNs with ReLU activation, simplifying the analysis to regular graphs. All these convergence analyses are solely full-graph training. For generalization analysis, full-graph GNN
68

---

Table 5:
Run I for Figure
4
Test acc
= 5
8 = 10
15
50
all
1000
747
671
618
427
481
b
10000
525
356
342
283
277
5 100000
416
308
291
245
232
b 150000
409
302
283
239
238
full batch
399
303
275
242
229
Table 6:
Run 2 for Figure 4 a).
Test acc
B
15
50
all
b 1000
743
682
621
435
497
b 10000
515
355
342
291
278
b 100000
423
322
289
258
242
b 150000
417
315
287
246
240
full batch
387
306
279
232
210
training has been studied (Scarselli et al. 20188) Vapnik & Chervonenkis 2013: Garg et al. 2020 Lv
2021 EI- Yaniv P [2099] Oono Suzuki |020] Koltchinskij [001] Cong al. 2021b
et al. 2019 et al. (220)) under the well-established frameworks (e.g.. IPA--Bayesial framework
(McAllester 2003)), while the previous analyses of mini-batch training impractically assume the same graph structures used in training and testing Tang & Liu 2023 Verma & Zhang 2019). The
difference among graph structures training and testing can result in generalization performance degradation overfitting to graph structures used in training.
P EXTENSIONS AND FUTURE WORK
P.1 EXTENSIONS
Multi-layer GNN models in theoretical analysis. We focus one-layer GNN with ReLU activation theoretical analysis. We discuss the extension of theoretical results to multi-layer settings in Appendix H., and conduct experiments using multi-layer GNNs in Sec 3 and Appendix [N The results validate that our key insights remain applicable in such settings. Therefore, our theoretical and empirical analyses support the multi-layer GNN settings.
Sampling methods. We focus on uniform neighbor sampling before mini-batch training. There exist many other sampling methods (Hamilton et al,, 2017; Chen et al.) 2018 Zou et al. 2019 Chiang et al. 2019: Zeng et al. 2019) that have been proposed at the layer- subgraph-leve enhance performance. Our core insights could extend to more sampling methods.
For example, compared uniform neighbor sampling, the key difference in advanced samplers lies in introducing specific constraints on the effective fan-out size by either assigning non-uniform sampling probabilities (Chen al. 2018), or imposing layer-wise upper bounds on the number of neighbors per node (Zou et al. 2211)). These specific constraints preserve the qualitative trend of the amount aggregated information per node in the message-passing when varying fan-out sizes. In convergence analysis, following our analysis in Appendix G increasing the effective fan-out size can enrich each target node's aggregated neighbors. improving embeddings and reducing gradient variance. Therefore, the mechanism "larger fan-out size + more iterations to convergence" still holds in GNN training under these samplers. For generalization, larger fan-out size can reduce the Wasserstein distance ( b) under these constraints, which leads to improved generalization. While these advanced samplers may lessen the sensitivity of generalization to fan-out size, they cannot completely eliminate the effect of including unsampled but valid edges as fan-out increases (see Obs. 2 Consequently, generalization remains more sensitive to fan-out size than to batch size. Overall, our key insights remain applicable to these sampling methods.
On the other hand, we notice that some advanced works (Chen et al. 2017 Shi et al. 2023 Fey et al.
2021 Shi al. 2025) historical embeddings incorporate nearly full graph information each
69

---

Table 7: Run 1 for Figure 4 4(e).
Test acc
3
10
20
B 50
all
1000
1167
928
854
817
801
b
10000
1232
1028
991
907
861
5 100000
1250
1025
1005
919
902
b 150000
1256
1047
1013
928
909
full batch
1295
1035
1007
945
925
Table 8:
Run 2 for Figure 4 c).
Test
10
20
50
all
5 1000
1169
943
872
809
787
10000
1222
1016
993
923
847
b 100000
1257
943
936
929
886
b 150000
1230
1037
978
923
902
full batch
1279
998
946
938
927
iteration. Therefore, from model performance perspective, these methods reduce the variance caused by different batch sizes and behave more like full-graph training. From a system design perspective, they also rely additional memory store historical embeddings, making them closer full-graph training systems than typical mini-batch ones. In contrast, we preserve and study the effects of batch size and fan-out, rather than eliminating them. Hence, adopt the standard neighbor- aggregatnnn scheme that is commonly used in practice and do not consider these sampling methods.
Link prediction tasks. We focus on node classification tasks GNN training, which can be easily extended to graph classification. Different from node classification, link prediction tasks use node pairs (connected and unconnected) for edge prediction, which can be transformed to node classification tasks using the line graph method in the graph theory. The new line graph L(G') is constructed in the following way: for each edge in the original graph G, make a vertex in L(G); for every two edges in G that have vertex in common, make edge between their corresponding vertices in L(G). Hence, our analyses and core insights naturally carry over to link prediction tasks.
Graph classification tasks. A graph-level prediction is obtained by first learning node representa- tions and then pooling them into a single graph representation. Since the training dynamics before pooling are the same as node classification, our analyses and key insights naturally carry over.
Inductive GNN tasks. We focus transductive GNN tasks. Unlike transductive tasks, inductive tasks apply different graphs between testing and training. For convergence, our analysis can be applied to inductive tasks without considering the testing graphs. For generalization, analysis can be easily extended to inductive tasks by revising glull in the Wasserstein distance to consider graph structure differences between testing and training graphs.
P.2 FUTURE WORK
Different activations: GeLU and Tanh. Our theoretical analysis readily extends to the GeLU and Tanh functions as the activation under our settings. The key difference lies in how the activation affects the gradient norm bound. GeLU is smooth approximation of ReLU and shares similar upper bound, while Tanh is even smoother with bounded high-order derivatives that control the gradient norm. As result, both our convergence and generalization methodology naturally translate to these activation functions.
Our core insights are clearly generalizable to GeLU due to its similarity with ReLU. However, whether the same insights hold for Tanh is less certain, as its bounded and more intricate derivative structure may affect the thcoretical bounds in nontrivial way.
Heterogeneous graphs. Different from homogeneous graphs, heterogeneous graphs require spe- cialized handling to address different types of nodes and edges, involving distinct aggregation and
70

---

Table 9: Run for Figure
6
Test acc
3 3=5
Ø = 15
25
Ø 50
all
1000
0.7767
0.7832
0.7821
0.7810
0.7789
5000
0.7817
0.7846
0.7825
0.7803
0.7698
10000
0.7851
0.7818
0.7812
0.7775
0.7713
100000
0.7869
0.7823
0.7818
0.7783
0.7753
150000
0.7852
0.7818
0.7809
0.7781
0.7761
full batch
0.7868
0.7810
0.7778
0.7778
0.7803
Table
10: Run for Figure
a).
Test acc
3=
8 = 15
3 25
8 = 50
all
1000
0.7793
0.7840
0.7820
0.7818
0.7792
5000
0.7825
0.7842
0.7833
0.7817
0.7702
10000
0.7852
0.7821
0.7818
0.7771
0.7713
100000
0.7862
0.7825
0.7816
0.7780
0.7762
150000
0.7860
0.7818
0.7800
0.7768
0.7760
full batch
0.7864
0.7808
0.7778
0.7775
0.7808
transformation functions for each type, such as using separate neural networks for different edge types. This can be explored.
71

---

Table
11:
Run
for Figure 6 b).
acc
3=
y= 10
20
Ø 50
1000
0.6617
0.6891
0.7117
0.7241
0.7242
5000
0.7113
0.7207
0.7336
0.7345
0.7369
10000
0.7209
0.7292
0.7341
0.7344
0.7362
100000
0.7318
0.7348
0.7373
0.7403
0.7415
150000
0.7329
0.7357
0.7372
0.7378
0,7401
full batch
0.7345
0.7391
0.7386
0.7384
0.7385
Table 12:
Run for Figure b()..
acc
3
0 10
5 20
50
all
1000
0.7295
0.7321
0.7344
0.7345
0.7341
5000
0.7307
0.7343
0.7361
0.7364
0.7371
10000
0.7326
0.7353
0.7366
0.7365
0.7381
100000
0.7342
0.7372
0.7392
0.7400
0.7411
150000
0.7343
0.7361
0.7385
0.7393
0,7405
full batch
0.7341
0.7396
0.7391
0.7389
0.7403
72


Reviews:
[{"review_id": "8XbmTcDmhs", "reviewer": "Reviewer_DYBQ", "summary": "This paper presents a systematic empirical and theoretical analysis comparing full-graph and mini-batch training for GNNs. The authors propose using the dual lenses of batch size and fan-out size as a unified framework for this comparison, noting that full-graph training is a special case with maximal values for both parameters. The work aims to address a significant gap in the literature by providing a holistic understanding of how these hyperparameters impact optimization dynamics convergence and generalization, moving beyond isolated or purely hardware-dependent comparisons. The central, counter-intuitive claim supported by the study is that full-graph training does not always outperform well-tuned mini-batch training in terms of performance or efficiency.", "questions": "Do the same conclusions hold for other types of tasks?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper's core strength is its unified framework for analyzing full-graph and mini-batch training through batch and fan-out sizes.\n\n2. The topic is of high importance to the GNN community. As graph datasets grow larger, the question of which training paradigm to choose and how to configure it is critical. This paper provides a foundational study that can guide future research in optimized training algorithms and systems\n\n3. This paper is easy to understand.", "weaknesses": "1. While the theoretical analysis is a key contribution, the paper would be strengthened by a more explicit discussion of the assumptions made in the theorems (e.g., Theorem 1 & 2 on optimization dynamics). The claim of \"better aligning with practice\" by considering irregular graphs and non-linear activations is commendable, but the specific limitations and the gap between the theoretical model and real-world GNN training dynamics should be clarified to assess the generality of the conclusions.\n\n2. The empirical evaluation is currently focused on transductive node classification. While this is a standard and important task, the findings' applicability to other fundamental GNN tasks like inductive learning, link prediction, or graph classification remains unverified. Different tasks may exhibit different sensitivities to batch and fan-out sizes, and demonstrating the generality of the findings across tasks would significantly increase the impact.", "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": "3h4K51cehr", "reviewer": "Reviewer_wVrk", "summary": "This paper presents a comparative study between full-batch and mini-batch training in GNNs, in terms of model convergence, generalization and computatioal efficiency. Based on their theoretical analysis and by using hardware-agnostic measures, the authors aim to guide practitioners on selecting the two key parameters of mini-batch training: batch size and fan-out size (i.e. the number of neighbors to be sampled for each node in the batch).", "questions": "1. Is there likely any role of the homophily level of the input graph in determining what batch and fanout sizes would be better for training a GNN for the task?\n\n2. While the authors provide results for three GNN architectures of different natures in their experiment, could they also explicitly comment on whether the same trend was observed across them or was their any variation? For e.g. is a particular architecture (or type thereof) more suited to a training paradigm?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This work sheds light on factors such as selecting between mini and full batch training and tuning subsequent hyperparamers that are often overlooked and decided without much thought but that impact model performance in multiple ways.\n\n2. Insights stem from theoretical analysis and are backed by comprehensive experiments. \n\n3. The paper is well-organized.", "weaknesses": "1. The figures are a little difficult to read and follow. For e.g. in Fig 1, it would be better to place the legend as a single horizontal line above or below the subplots instead of repeating it in each subplot and covering the information that needs to be displayed. Also, it would make the comparison easier to read if the bar grouping is done based on dataset rather than training setting, for example blue represents mini-batch and orange represents full batch, and the each groups of bars represents a dataset. The later heatmaps are also a little overwhelming with lots of numbers thrown in. Perhaps only the numbers that reveal crucial information can be retained and the general trends can be left to be depicted by the heatmap color. This would make it easier for the reader to pick up key insights more easily than going through a lot of data. \n \n2. The number of layers of the GNNs in the experiments is restricted to 3, hardly enough to be considered 'deep', so oversmoothing does not seem to be a plausible explanation on lines 368 and 369. \n\n3. Regarding 'observed low variance' of experiment results repeated thrice, while I trust the authors on this claim, it would still be better to provide some sort of evidence for it, in table format perhaps, in the appendix atleast as standard scientific 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": "U429uOgfUH", "reviewer": "Reviewer_VT8k", "summary": "This paper aims to provide a systematic and comprehensive study on comparing the full-graph vs. mini-batch GNN training, focusing on the impact of batch size and fan-out size. Theoretical analysis shows that increasing batch size slows convergence under MSE but accelerates it under CE, while increasing fan-out size consistently improves convergence. The provided theories show batch size has a greater impact on GNN optimization dynamics, while the fan-out size more strongly affects GNN generalization. Empirical results validate these findings, using a hardware-agnostic iteration-to-accuracy metric. Experiments show that moderate fan-out size balances speed and efficiency, and overly large batch size and fan-out size degrades accuracy. Overall, well-tuned mini-batch training can match or surpass full-graph training in both performance and computational efficiency.", "questions": "1. Scope of Mini-Batch Paradigms:\nThe paper focuses on node-wise neighbor sampling when discussing mini-batch training. However, mini-batch GNNs also include subgraph-level (e.g., GraphSAINT, Cluster-GCN) and layer-wise (e.g., LADIES) sampling approaches, which may exhibit different trade-offs between variance, memory, and structural bias. Could the authors clarify whether their theoretical framework—especially the convergence and Wasserstein-based generalization analysis—can extend to graph-level or layer-wise mini-batching? Have the authors considered running at least small-scale comparisons (e.g., Cluster-GCN vs. neighbor sampling) to test whether the same sensitivity patterns still hold under these paradigms?\n\n\n2. Conceptual Contribution and Practical Value:\nThe concluding message—“full-graph training does not always outperform well-tuned mini-batch training”—has been noted in prior empirical studies (e.g., Bajaj et al., 2024). What remains unclear is the new insight or practical benefit beyond formalizing known intuitions. The two key observations (Obs.1: convergence more sensitive to batch size; Obs.2: generalization more sensitive to fan-out size) are interesting, but they seem to reaffirm what many practitioners already do during hyper-parameter tuning. Could the authors elaborate on what new guidance or algorithmic implications their framework provides? How does this work go beyond offering “interpretive understanding” and translate into actionable or theoretical advancement for future GNN training design?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Both main observations—(Obs.1) convergence is more sensitive to batch size, and (Obs.2) generalization is more sensitive to fan-out size - are consistently supported by theoretical derivations and empirical results across multiple datasets and GNN models.\n2. The paper addresses a practically important topic - understanding the differences between full-graph and mini-batch GNN training， which is beneficial to large-scale GNN training.\n3. Code is provided for reproducibility.", "weaknesses": "1. The study only covers node-wise sampling; other major mini-batch paradigms (e.g., graph-level and layer-wise sampling) are omitted, which limits the comprehensiveness of the conclusions.\n2. The main conclusion—that full-graph training does not always outperform well-tuned mini-batch training—has already been reported in prior empirical works (e.g., Bajaj et al., 2024). The novelty thus lies mainly in providing a formal theoretical framing rather than discovering a new phenomenon.", "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": "VRoP9lbhTe", "reviewer": "Reviewer_463G", "summary": "This paper investigates mini-batch training for GNNs. It provides theoretical analysis on both convergence and generalization within the mini-batch training framework, and conducts experiments to validate the proposed theory.", "questions": "Q1: May I ask what is the target loss in iteration-to-loss, the target accuracy in iteration-to-accuracy and time-to-accuracy? I try to look them in appendix N, but there is only description, not the actual value. If we change these value, will the conclusion change?\n\nQ2: What is the setting and hyperparameters of Fig. 4(a)?\n\nQ3: In the mini-batch training, different batch sizes means different amount of samples the model saw after one iteration. Is it fair to compare the number of iteration in such context? \n\nQ4: The most relevant work is [1]. Could you briefly summarize the most important new insight of your paper in comparison to [1] (except using iteration-to-accuracy to avoid hardware influence)?\n\n[1] Bajaj, Saurabh, et al. \"Graph Neural Network Training Systems: A Performance Comparison of Full-Graph and Mini-Batch.\" Proceedings of the VLDB Endowment 18.4 (2024): 1196-1209.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1: Comprehensive theoretical analysis.\n\nS2: The choice of datasets and models are reasonable.\n\nS3: Results make sense.", "weaknesses": "W1: The results are somewhat plain. The first notable conclusion is that when trained with the MSE loss, larger batch size leads to slower convergence. But empirically, this is validated using node classification datasets. The second claim is that \"mini-batch could leads to better generalization than full-graph\", but in Fig. 4, the influence of batch size seems marginal. Reducing fan-out size is useful, but to the best of my knowledge, community is already aware of that, due to those DropEdge papers.\n\nW2: Presentation could be further improved. Lots of statements in the experiments section refer to the Appendix N. If the information in the appendix is important enough, it should be presented in the main paper. Defer them to the appendix but continually mention them will not save space. For example, line 363, line 415, figures in the appendix is mentioned before figures in the main paper.", "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)