Grappa: Gradient-Only Communication for Scalable Graph Neural Network Training Chongyang Xu, Christoph Siebenbrunner, Laurent Bindschaedler Abstract . Cross - partition edges dominate the cost of distributed GNN training: fetching remote features and activations per iteration overwhelms the network as graphs deepen and partition counts grow. Grappa is a distributed GNN training framework that enforces gradient - only communication : during each iteration, partitions train in isolation and exchange only gradients for the global update. To recover accuracy lost to isolation, Grappa (i) periodically repartitions to expose new neighborhoods and (ii) applies a lightweight coverage - corrected gradient aggregation inspired by importance sampling. We present an asymptotically unbiased estimator for gradient correction, which we use to develop a minimum-distance batch-level variant that is compatible with common deep-learning packages. We also introduce a shrinkage version that improves stability in practice. Empirical results on real and synthetic graphs show that Grappa trains GNNs 4 × 4\times faster on average (up to 13 × 13\times ) than state-of-the-art systems, achieves better accuracy especially for deeper models, and sustains training at the trillion - edge scale on commodity hardware. Grappa is model - agnostic, supports full - graph and mini - batch training, and does not rely on high - bandwidth interconnects or caching. † † authors: . PVLDB Reference Format: Grappa: Gradient-Only Communication for Scalable Graph Neural Network Training. PVLDB, 19(1): XXX-XXX, 2026. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 19, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/mpi-dsg/grappa . 1. Introduction Graph Neural Networks (GNNs) are a widespread class of machine learning models that learn representations from graph-structured data. GNNs power applications in science, social networks, commerce, and finance ( 6 ; 10 ; 36 ; 19 ; 49 ; 18 ; 25 ) . However, as graphs and models grow, distributed training encounters a network communication bottleneck, creating a need for efficient, scalable, and distributed GNN training. This paper addresses that need with a training framework that drastically reduces the communication bottleneck and is model-agnostic , theory-backed , and empirically validated . Distributed GNN training partitions the sparse graph and the dense per-node feature vectors to fit memory and exploit parallelism. Training is iterative: each iteration runs a k -layer forward pass that performs message passing, where each node aggregates and transforms neighbor features into hidden activations, followed by a backward pass that computes gradients, and finally a synchronized update aggregates them across replicas. Partitioning breaks edges, so when the forward pass follows a cross-partition edge, the trainer must fetch the remote endpoint’s feature at the first layer and the neighbor’s activation at deeper layers. As partition counts or model depth increase, these per-iteration remote fetches become the dominant cost, saturate the network, and throttle scalability ( 5 ; 48 ; 23 ) . Mini-batch sampling ( 3 ; 31 ) reduces computation, but k-hop neighborhoods still span partitions, so remote feature/activation reads remain; sampling reduces volume, not the need for cross-partition fetches. High-speed interconnects, such as RDMA or NVLink, can help; however, they are costly to deploy at scale and can introduce imbalance ( 35 ; 2 ; 24 ) . Caching reduces traffic by reusing fetched data, but it increases memory pressure and complexity ( 5 ; 48 ; 33 ) . Therefore, current strategies to address this performance bottleneck remain inadequate. This paper introduces Grappa 1 1 1 Grap h pa rtitioning , a model-agnostic distributed framework for scalable GNN training on large graphs. Grappa eliminates cross-partition neighbor traffic during iterations : partitions train in isolation and exchange only gradients on the forward/backward critical path ( gradient-only communication ). Feature movement is deferred to periodic repartitioning boundaries, where it can be amortized. This approach reduces communication and synchronization overhead without specialized interconnects or caching-induced memory pressure. Moreover, partition independence within an iteration allows phase-parallel execution, which trades time for capacity by training a subset of partitions per phase. While this strategy minimizes communication costs, it introduces a new challenge: a potential decrease in model accuracy due to restricted sample diversity, as each partition only sees its local information. To recover accuracy, Grappa combines (1) dynamic repartitioning across groups of epochs (super-epochs) to expose new neighborhoods and (2) coverage-corrected gradient aggregation , a batch-level importance weighting that compensates for isolation-induced sampling bias. Intuitively, repartitioning is more cost-effective than on-the-fly neighbor fetches because the input graph is typically far smaller than the volume of per-iteration intermediate activations that would otherwise be exchanged. Formal guarantees. We derive a batch-level corrected gradient estimator and prove it is asymptotically unbiased under standard support and boundedness conditions. We also show that, among all ways to rescale a batch with a single number, our choice makes the corrected batch gradient as close as possible (on average) to the ideal importance-weighted gradient (i.e., it minimizes average squared error). We have implemented Grappa and evaluated its performance in our cluster. Across real-world and RMAT graph datasets, Grappa achieves 4\times average speedup (up to 13\times ) over state - of - the - art systems, improves test accuracy for deeper models, scales near - linearly to 64 partitions, and trains a trillion-edge graph in phase-parallel mode on a single commodity server. Terminology. We use gradient-only communication to mean that there is no cross-partition exchange of features or activations during forward or backward passes; only gradients are synchronized across participating replicas. The paper makes the following contributions: • Gradient-only communication: a data-parallel scheme where iterations involve no cross-partition feature/activation traffic; only gradients are synchronized. Halo features move at repartitioning boundaries. • Theory-backed accuracy recovery: dynamic repartitioning plus batch-level coverage-corrected aggregation. We prove an asymptotically unbiased node-level estimator and show that the batch-level variant minimizes the mean squared deviation from the ideal. • Flexible execution: phase-parallel execution mode that trades time for capacity, allowing single-machine training at the trillion-edge scale. • Implementation and evaluation: Grappa supports full-graph and mini-batch training and shows superior performance, accuracy, and scalability over current systems. 2. Background & Motivation GNNs 101 A Graph Neural Network (GNN) takes a sparse graph (vertices, edges) with dense node features and learns node (and edge/graph) representations that encode both structure and features for downstream tasks. A k -layer forward pass performs message passing, so each node aggregates and transforms information from its neighbors and reaches k hops. Two execution modes are common: full-graph (all nodes and edges participate each iteration) and mini-batch sampling (sample target nodes and their multi-hop neighborhoods). Training is iterative : every iteration runs a forward pass, computes gradients via backpropagation, and updates parameters with gradient descent. Requirements and Goals Efficient training on large graphs requires a distributed system that provides sufficient capacity (graph, features, and intermediate states in aggregate memory) and that parallelizes computation across partitions to reduce training time. Given the compute intensity of deep models, accelerators (GPUs) are essential. Our goal is a model-agnostic system that is not tied to a specific GNN architecture, and that targets ever-larger graph datasets. We summarize these requirements to motivate why we target gradient-only communication rather than more aggressive partitioning or caching. Capacity Limits Pure GPU full-graph training is often infeasible at scale due to limited High-Bandwidth Memory (HBM). For example, an H100 has 80 GB, and even an 8-GPU node offers < 640 GB for all topology, features, parameters, and activations ( 42 ; 40 ) . Several common datasets exceed this budget ( 16 ; 27 ) . Mini-batch sampling can offload graphs to CPU memory, but this merely shifts the capacity bottleneck to DRAM and I/O contention. Figure 1 . Sampling-based data-parallel GNN training. Each iteration samples multi-hop neighborhoods across partitions and aggregates gradients. Following cross-partition edges triggers remote feature/activation fetches, which dominate per - iteration cost at scale. Graph Partitioning Training a GNN on a large graph requires splitting the topology and features into partitions that are processed individually, as shown in Figure 1 . This data-parallel training approach replicates the model and aggregates gradients. However, when the graph is partitioned, message passing must follow edges that cross partitions, forcing remote feature/hidden-state fetches during each iteration. Cross-partition neighbor traffic (features/activations) grows with graph size, number of partitions, and depth, and quickly becomes a significant bottleneck ( 5 ; 48 ; 23 ) . Table 1 quantifies the magnitude for representative datasets; at 10 Gbps it implies 2–30 seconds of transfer per partition per epoch, and even at 400 Gbps the 37.7 GB case adds about 0.76 s per epoch, which is non-trivial relative to GPU compute. Moreover, computing partitions that both balance the load and reduce edge cuts is itself expensive and difficult ( 1 ) , and any imbalance further amplifies the effects of communication and stragglers. Table 1 . Per-partition neighbor traffic during a single training epoch (3-layer model) versus number of partitions. Datasets are in Table 2 . Inputs are <\!1 GB. Partition Dataset 2 parts. 4 parts. 8 parts. Random Reddit 6,106 MB 9,216 MB 10,832 MB OGBN-Pr 21,448 MB 32,160 MB 37,682 MB METIS Reddit 3,264 MB 5,180 MB 5,512 MB OGBN-Pr 5,000 MB 10,120 MB 11,072 MB Why Fixes Fall Short Existing solutions help but do not eliminate remote fetches. High-quality partitions (e.g., METIS ( 15 ) ) reduce edge cuts but add preprocessing and memory overhead. Sampling lowers compute but not remote neighbor retrieval ( 3 ; 31 ) . Fast interconnects (NVLink/RDMA) ( 35 ; 2 ; 24 ) help within a node, yet gains do not generalize: when traffic leaves NVLink islands, epoch times balloon ( >11\times on OGBN-Pa, 16\times on Reddit ( 43 ; 9 ) ). Uniform NVLink-class bandwidth across nodes demands specialized switching, which is costly. Caching ( 5 ; 48 ; 33 ) reduces traffic but consumes HBM/DRAM. Thus, while existing approaches offer partial relief, the core tension between high capacity and cross-partition network traffic remains. Therefore, we move neighbor information exchange off the iteration critical path by training partitions in isolation and synchronizing only gradients; we then restore coverage statistically via repartitioning and correction. 3. The Grappa Design We begin with an overview of the system and its design principles (Section 3.1 ). Then, we introduce Grappa’s isolated training strategy (Section 3.2 ), its approach to dynamic repartitioning (Section 3.3 ), its sampling bias correction (Section 3.4 ), the training controller along with its heuristic for switching partitions (Section 3.5 ), and its phase-parallel training mode (Section 3.6 ). 3.1. Overview Grappa aims to efficiently train GNNs on large input graphs in a distributed, data-parallel fashion. Grappa supports both full-graph and sampling-based training modes (Section 2 ), although we focus mostly on sampling-based training as it offers superior scalability. Grappa divides the input graph and its features into partitions. Each partition is stored in CPU memory and loaded into GPU for training alongside the model. In the sampling-based training mode, we use the CPU to sample from the training nodes in the local partition to form mini-batches and load each batch into the GPU. Unlike conventional GNN training, whether executing in full-graph or sampling mode, Grappa restricts graph access to the local partition only, preventing any data exchange along edges spanning multiple partitions, thereby executing training on each partition in complete isolation (Section 3.2 ). This strategy eliminates cross-partition exchange of features or activations within an iteration ; cross-partition communication is gradient-only , which yields significant performance gains. Grappa supports all GNN models compatible with other state-of-the-art systems, maintaining similar or improving accuracy but with lower training time. These speedups are primarily due to reduced communication and synchronization overheads, as we will show in Section 5 . Moreover, due to its unique approach of processing partitions independently, Grappa achieves high flexibility in managing the overall training process. Since training on each partition can be performed separately from the others, there is no longer a need for concurrent data-parallel training of all partitions. Instead, it is enough for training on partitions to occur conceptually in parallel . Within each phase, gradients are synchronized across the active replicas, and across phases, we carry optimizer state forward. As a result, depending on available resources, Grappa can train some partitions sequentially, seamlessly trading training time for capacity (Section 3.6 ). (a) Super-epoch 1 (b) Super-epoch 2 Figure 2 . Example of GNN training with Grappa for two super-epochs. Compared to Figure 1 , subgraph sampling is performed without remote neighbor fetches (gradient-only communication) in each iteration and epoch. After a few epochs, we switch to a new super-epoch, creating a new partitioning layout (repartitioning). Figure 2 illustrates the workflow of Grappa as it trains a two-layer GNN model on an example input graph in sampling mode. Training is organized in super-epochs, each consisting of multiple training epochs. The input graph and its features are partitioned at the start of each super-epoch. We keep the partitioning layout unchanged for the entire super-epoch. Training proceeds in epochs that iterate over the whole set of training nodes in steps (also referred to as iterations). Within each step, we construct mini-batches of subgraphs and associated features. The GPU then processes each mini-batch as input for model training. Finally, the gradients are accumulated across all replicated models for each partition before proceeding to the next iteration. Grappa allows each node to be exposed to its entire neighborhood despite its partition-level isolation by strategically repartitioning the input between super-epochs (Section 3.3 ). Repartitioning the input several times throughout the training to disseminate neighborhood information is more cost-effective than exchanging data across partitions. The rationale behind this design decision is that, with conventional training, the total neighbor - exchange volume scales roughly with the sum of the fanout at each layer and grows rapidly with model depth and cut edges. In contrast, repartitioning cost is linear in the input size and the number of super - epochs. Repartitioning alone is insufficient to ensure high model accuracy as, despite exposing each vertex to its entire neighborhood throughout all super-epochs, we may still introduce bias into the sampling process unwillingly. For example, during two super-epochs, a neighbor could be seen more or less frequently due to the partition structure and the presence or absence of an edge. Grappa accounts for sample bias by keeping track of how many times a vertex is seen during a super-epoch and scaling the gradients for that partition before aggregation. We introduce a low-overhead weighted aggregation scheme based on estimations to adjust for sampling bias (Section 3.4 ). We directly use this scheme in the Grappa training controller to decide when to repartition the graph, switching to the next super-epoch (Section 3.5 ). Intuitively, isolated training may act as a form of dropout in the input layer, which can improve generalization for deeper models. Repartitioning restores long - run neighbor coverage, and the coverage - corrected scaling re-centers gradients toward the full - graph objective. Together, these mechanisms preserve the convergence properties akin to conventional GNN training, enabling the model to effectively learn from the global graph structure while reducing communication overhead. 3.2. Isolated Training Strategy Unlike conventional GNN training systems that follow edges to retrieve nodes and features from other partitions, Grappa operates entirely within each local partition and uses this isolation to streamline training. Isolated Training Grappa proceeds similarly to traditional training, but considers exclusively local nodes and edges. Halo nodes are the key enabler: they cache boundary neighbors so that a partition contains all nodes within k hops of any training node, allowing k -layer message passing without remote fetches. Halos are read-only within a super-epoch and contribute to local aggregations but never trigger cross-partition communication. With halos in place, Grappa can proceed as if each partition executes message passing on its local subgraph, without remote dependencies within an iteration. In each iteration, we either feed the entire partition to the model (full-graph mode) or select a subset of the training nodes from the local partition to construct subgraphs (sampling mode). Each subgraph’s depth aligns with the number of layers in the model; for a k -layer model we sample k -hop subgraphs, and halo nodes provide k -hop closure within each partition so each mini-batch is self-contained without cross-partition reads. Overhead Reduction The primary advantage of Grappa’s approach is reducing communication overhead and synchronization delays. In traditional GNN training, resource consumption during sampling grows rapidly with graph size, model depth, and partition count. By eliminating cross-partition exchange of features or activations during a training iteration, Grappa reduces the time spent on cross-partition neighbor exchange to zero, leaving only gradient synchronization. The system still accumulates and updates gradients across partitions after each iteration to ensure the model parameters benefit from each partition. This approach enables both an accelerated training process and enhanced scalability. Isolation introduces a predictable coverage bias : a node’s gradient in a step reflects only neighbors present in the current partition. We correct this bias in aggregation using a single scalar per batch, derived from easy-to-measure degree ratios (Section 3.4 ). 3.3. Dynamic Graph Repartitioning Grappa dynamically manages graph partitions throughout training by repartitioning the graph to expose nodes to new neighborhoods over time. This differs from other GNN training systems that use static partitioning without isolation. Adapting the partitioning layout improves model quality. Terminology. We use iteration to mean one mini-batch step; an epoch is a full pass over training nodes under a fixed partition layout; a super-epoch is a contiguous group of epochs between repartitioning events. A chunk is a static unit of graph data produced once at startup. A partition is the training unit formed by combining a base chunk with a swept chunk for a super-epoch. A worker is an execution resource (GPU) responsible for one base chunk that trains one partition at a time. A phase is a scheduling unit when only a subset of partitions run concurrently (Section 3.6 ). Super-epochs Grappa structures the overall training process into super-epochs. A super-epoch is simply a contiguous span of epochs between repartitionings and is independent of the number of workers. The training controller (Section 3.5 ) makes the decision to transition to a new super-epoch where the input graph will undergo repartitioning. The new partitions must be distinct from the partitions in the previous super-epoch to ensure that each vertex is exposed to its entire neighborhood. Once the repartition is complete, we begin executing the next super-epoch. The challenge with repartitioning is that recomputing partitions and shuffling data between each super-epoch may be prohibitively expensive and negate the performance benefits of isolated training. Graph Partitioning Many graph partitioning strategies exist, such as random or METIS ( 15 ) . In random graph partitioning, nodes in the input graph are randomly assigned to different partitions without particular consideration for the underlying graph structure. In contrast, METIS graph partitioning recursively coarsens the graph to reduce its size, partitions the smaller graph, and then uncoarsens it to obtain a balanced and high-quality partition of the original graph. Upon partitioning the nodes, the edges linked to these nodes and their corresponding endpoints are also included in the respective partition. Should an endpoint not be part of the initial partition, it is incorporated as a halo node, represented with dashed lines in Figure 2 . Finally, the features associated with each node are added to the partition. Chunks and Efficient Partition Construction Repartitioning the graph introduces overhead: nodes and edges must be assigned to partitions, and feature data (typically vectors of length 128 to 1024) must be split. To reduce this overhead, Grappa uses unmodified graph partitioning strategies such as random or METIS to split the dataset into chunks , rather than final partitions. This initial partitioning is performed only once. Each partition for training is dynamically constructed by combining pairs of chunks, specifically a base chunk, m_{i} , with another variable chunk, m_{j} where i\neq j . This approach allows for quick and efficient repartitioning of the graph by sweeping through different variable chunks without recomputing a new set of partitions after each super-epoch. Each worker is responsible one chunk and sweeps one chunk from the other chunks during each repartitioning, thus only loading a small subset of the graph each time. This method effectively disseminates neighborhood information across the graph structure. Figure 3 shows a simple example of Grappa’s efficient sweeping chunk partitioning. This coverage holds for k -layer models as the locality boundary changes across super-epochs, ensuring that neighbors within graph distance \leq k appear with non-zero probability over time. Figure 3 . Example of efficient dynamic repartitioning via sweeping chunks. The example shows four workers operating in a data-parallel manner. The graph topology and feature data are divided into chunks m_{0} , m_{1} , m_{2} , m_{3} and f_{0} , f_{1} , f_{2} , f_{3} respectively. The dataset is split into chunks just once before training. The four workers then operate in parallel. Worker 0 initially loads chunks m_{0} and f_{0} , then loads m_{1} and f_{1} , groups these together as a partition, and trains the model on the resulting partition for a super-epoch. After that, we perform a repartition where worker 0 will load the next chunks m_{2} and f_{2} , grouping them with m_{0} , f_{0} to form a new partition for further training. This process repeats until all workers have seen all chunks at least once. Coverage guarantee. With M+1 chunks and W workers, each worker pins a base chunk and cycles through others across super-epochs. Over M super-epochs every cross-chunk edge co-resides in at least one partition, satisfying Theorem 3.1 ’s support requirement. When W0 whenever p_{v}(u)>0 . Asymptotically Unbiased Node-Level Estimator We cannot apply the importance sampling result ( 3 ) directly because the probability of selecting a neighbor missing from the local partition is zero, violating the support condition. We resolve this via repartitioning: as long as the long-run probability is positive, the bias can be removed entirely, at least asymptotically. The sweep schedule presented in Section 3.3 guarantees that each node will be matched with all of its neighbors already after a finite number of super-epochs, so the assumption is justified. Formally, let q_{v}^{t}(u)=\mathbb{P}\left[u\in S_{\mathcal{D}^{\text{local}}_{v}}\right] be the probability of selecting neighbor u of v in the current local partition at super-epoch t . We define the estimator: (4) \begin{split}&\nabla_{\theta}\tilde{L}^{\text{corr}}=\\ &\frac{1}{T}\sum_{t=1}^{T}\frac{1}{|S_{\mathcal{D}}^{t}|}\sum_{v\in S_{\mathcal{D}}^{t}}\frac{1}{|S_{\mathcal{D}^{\text{local}}_{v}}|}\sum_{u\in S_{\mathcal{D}^{\text{local}}_{v}}}\frac{p_{v}(u)}{q_{v}^{t}(u)}\nabla_{\theta}g_{v}(u)\end{split} where T is the number of super-epochs and |S_{\mathcal{D}}^{t}| is the local node sample in the current super-epoch. If the partitioning gives enough weight to each node such that: (5) \lim_{T\rightarrow\infty}\frac{1}{T}\sum_{t=1}^{T}\mathbb{I}_{u\in S_{\mathcal{D}_{v}^{\text{local}}}}\xrightarrow{\text{a.s.}}q_{v}(u)>0 i.e., the long-run selection probability is positive, we have: Theorem 3.1. Under assumption ( 5 ) and if \left|\frac{p_{v}(u)}{q_{v}^{t}(u)}\nabla_{\theta}g_{v}(u)\right|\leq M for some constant M and S_{\mathcal{D}}^{t} and S_{\mathcal{D}^{\text{local}}_{v}} are i.i.d. samples, (6) \lim_{T\rightarrow\infty}\mathbb{E}\left[\nabla_{\theta}\tilde{L}^{\text{corr}}\right]=\nabla_{\theta}L Proof. By i.i.d. sampling, we have: (7) \mathbb{E}\left[\nabla_{\theta}\tilde{L}^{\text{corr}}\right]=\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{v\sim\mathcal{D}}\left[\mathbb{E}_{u\sim\mathcal{D}^{\text{local}}_{v}}\left[\frac{p_{v}(u)}{q^{t}_{v}(u)}\nabla_{\theta}g_{v}(u)\right]\right] By the dominated convergence theorem and assumption ( 5 ), we have: (8) \begin{split}&\lim_{T\rightarrow\infty}\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{v\sim\mathcal{D}}\left[\mathbb{E}_{u\sim\mathcal{D}^{\text{local}}_{v}}\left[\frac{p_{v}(u)}{q^{t}_{v}(u)}\nabla_{\theta}g_{v}(u)\right]\right]=\\ &\mathbb{E}_{v\sim\mathcal{D}}\left[\mathbb{E}_{u\sim\mathcal{D}^{\text{local}}_{v}}\left[\frac{p_{v}(u)}{q_{v}(u)}\nabla_{\theta}g_{v}(u)\right]\right]\end{split} The result follows by applying the importance sampling theorem ( 3 ). ∎ That is, \nabla_{\theta}\tilde{L}^{\text{corr}} is asymptotically unbiased under mild regularity conditions. An important special case is when all neighbors have equal weight under \mathcal{D}_{v} for all v . Then p_{v}(u)=1/d_{v}^{\text{global}} , q^{t}_{v}(u)=1/d_{v}^{\text{local}} for all local neighbors u of v , where d_{v}^{\text{global}} and d_{v}^{\text{local}} are the degrees of node v in the full graph and in the local partition, respectively. So \nabla_{\theta}\tilde{L}^{\text{corr}} becomes: (9) \begin{split}&\nabla_{\theta}\tilde{L}^{\text{uniform}}=\\ &\frac{1}{T}\sum_{t=1}^{T}\frac{1}{|S_{\mathcal{D}}^{t}|}\sum_{v\in S_{\mathcal{D}}^{t}}\frac{1}{|S_{\mathcal{D}^{\text{local}}_{v}}|}\frac{d_{v}^{\text{local}}}{d_{v}^{\text{global}}}\sum_{u\in S_{\mathcal{D}^{\text{local}}_{v}}}\nabla_{\theta}g_{v}(u)\end{split} In general one may use q^{t}_{v}(u)=p_{v}(u)/\sum_{i\in\mathcal{D}^{\text{local}}_{v}}p_{v}(i) . Batch-Level Approximation Exact bias correction requires modifying gradient contributions at the level of individual nodes in a batch. Common libraries such as PyTorch ( 29 ) only provide hooks for modifying batch-level gradient objects, however. In line with the idea of being model-agnostic, it would be desirable to have a framework that can be used with PyTorch ( 29 ) and its batch-level gradient objects. We propose the following batch-level estimator and will proceed to show that it is closest (in L2-distance of expectations) to the asymptotically unbiased estimator under mild assumptions: (10) \begin{split}&\nabla_{\theta}\tilde{L}^{\text{batch}}(c)=\\ &\frac{1}{T}\sum_{t=1}^{T}\frac{c^{t}}{|S_{\mathcal{D}}^{t}|}\sum_{v\in S_{\mathcal{D}}^{t}}\frac{1}{|S_{\mathcal{D}^{\text{local}}_{v}}|}\sum_{u\in S_{\mathcal{D}^{\text{local}}_{v}}}\nabla_{\theta}g_{v}(u)\end{split} where the batch-level correction factors c\in\mathbb{R}^{T} are: (11) c^{t}=\frac{1}{|S_{\mathcal{D}}^{t}|}\sum_{v\in S_{\mathcal{D}}^{t}}\frac{1}{|S_{\mathcal{D}^{\text{local}}_{v}}|}\sum_{u\in S_{\mathcal{D}^{\text{local}}_{v}}}\frac{p_{v}(u)}{q_{v}^{t}(u)} In the case of equal selection probabilities, this simplifies to: (12) c^{t}_{\text{uniform}}=\frac{1}{|S^{t}_{\mathcal{D}}|}\sum_{v\in S^{t}_{\mathcal{D}}}\frac{d_{v}^{\text{local}}}{d_{v}^{\text{global}}} In practice, we apply the batch-level correction \nabla_{\theta}\tilde{L}^{\text{batch}}(c) before the phase’s gradient synchronization. We have (for notational convenience, we set T=1 without loss of generality and drop the t -superscript): Theorem 3.2. Assuming that gradients are independently identically distributed \nabla_{\theta}g_{v}(u)\sim\text{i.i.d} with finite mean \mu\in\mathbb{R}^{|\theta|}\setminus\mathbf{0} independent of \frac{p_{v}(u)}{q_{v}(u)} , equation ( 11 ) gives the scalar c that minimizes: (13) \left\|\mathbb{E}\left[\nabla_{\theta}\tilde{L}^{\text{corr}}\right]-c\mathbb{E}\left[\nabla_{\theta}g_{S_{\mathcal{D}}}\right]\right\|_{2} Proof. After squaring the objective function ( 13 ), standard vector calculus gives the orthogonal projection of \mathbb{E}\left[\nabla_{\theta}\tilde{L}^{\text{corr}}\right] onto \mathbb{E}\left[\nabla_{\theta}g_{S_{\mathcal{D}}}\right] : (14) \begin{split}&\frac{\partial}{\partial c}\left\|\mathbb{E}\left[\nabla_{\theta}\tilde{L}^{\text{corr}}\right]-c\mathbb{E}\left[\nabla_{\theta}g_{S_{\mathcal{D}}}\right]\right\|_{2}^{2}=0\Rightarrow c=\\ &\left(\mathbb{E}\left[\nabla_{\theta}g_{S_{\mathcal{D}}}\right]^{\intercal}\mathbb{E}\left[\nabla_{\theta}g_{S_{\mathcal{D}}}\right]\right)^{-1}\mathbb{E}\left[\nabla_{\theta}g_{S_{\mathcal{D}}}\right]^{\intercal}\mathbb{E}\left[\nabla_{\theta}\tilde{L}^{\text{corr}}\right]\end{split} By the assumptions of the theorem: (15) \displaystyle\mathbb{E}\left[\nabla_{\theta}g_{S_{\mathcal{D}}}\right] \displaystyle=\frac{1}{|S_{\mathcal{D}}|}\sum_{v\in S_{\mathcal{D}}}\frac{1}{|S_{\mathcal{D}^{\text{local}}_{v}}|}\sum_{u\in S_{\mathcal{D}^{\text{local}}_{v}}}\mu=\mu (16) \displaystyle\begin{split}\mathbb{E}\left[\nabla_{\theta}\tilde{L}^{\text{corr}}\right]&=\frac{1}{|S_{\mathcal{D}}|}\sum_{v\in S_{\mathcal{D}}}\frac{1}{|S_{\mathcal{D}^{\text{local}}_{v}}|}\sum_{u\in S_{\mathcal{D}^{\text{local}}_{v}}}\frac{p_{v}(u)}{q_{v}(u)}\mu\\ &=s_{L}\mu\end{split} where s_{L}=\frac{1}{|S_{\mathcal{D}}|}\sum_{v\in S_{\mathcal{D}}}\frac{1}{|S_{\mathcal{D}^{\text{local}}_{v}}|}\sum_{u\in S_{\mathcal{D}^{\text{local}}_{v}}}\frac{p_{v}(u)}{q_{v}(u)} . This gives: (17) \begin{split}&c=\left(\mu^{\intercal}\mu\right)^{-1}\mu^{\intercal}\mu s_{L}=s_{L}=\\ &\frac{1}{|S_{\mathcal{D}}|}\sum_{v\in S_{\mathcal{D}}}\frac{1}{|S_{\mathcal{D}^{\text{local}}_{v}}|}\sum_{u\in S_{\mathcal{D}^{\text{local}}_{v}}}\frac{p_{v}(u)}{q_{v}(u)}\end{split} ∎ That is, \nabla_{\theta}\tilde{L}^{\text{batch}} is the estimator with batch-level correction whose expectation is closest (in L^{2} -distance) to the expectation of \nabla_{\theta}\tilde{L}^{\text{corr}} under mild distributional assumptions. Shrinkage The estimators above assume idealized conditions. In practice, accepting some degree of bias to shrink coefficients can improve stability and combat overfitting ( 12 ) . We find that the following correction factor gives better accuracy than the minimally-biased version: (18) c^{t}_{\text{resampling}}=\frac{1}{\sum_{v\in S^{t}_{\mathcal{D}}}\left[\frac{d_{v}^{\text{global}}}{d_{v}^{\text{local}}}-1\right]|S_{\mathcal{D}^{\text{local}}_{v}}|} While c^{t} uses an arithmetic mean of correction factors, c^{t}_{\text{resampling}} is closer to a harmonic mean and produces lower correction factors overall. We interpret this as a form of shrinkage in gradient magnitude, similar to methods like gradient clipping and others that have been developed for deep learning applications ( 28 ; 30 ) . Intuitively, c^{t}_{\text{resampling}} weights the correction factors inversely by how often, in expectation, the global set of neighbors of a selected node would have to be resampled to get a sample consisting only of neighbors present in the local partition. 3.5. Training Controller and Partitions Switching Having established how to correct gradients within a super-epoch, we now describe how Grappa decides when to switch partitions. The training process in Grappa is managed and monitored by a training controller that collects information on the overall training progress on each machine and for each partition. The controller aggregates sampling information within each partition and initiates repartitioning when appropriate. The controller currently aims to ensure that each possible combination of chunks for a partition are explored for a fixed number of iterations, providing it with a target of e/(c-1) super-epochs where e is a fixed number of epochs to train for and c is the number of chunks in the system. The controller monitors a simple coverage deficit statistic per partition, \Delta_{t}=1-\widehat{c}_{t} , and triggers an earlier repartition when \Delta_{t} persists across several steps, prioritizing partitions with low coverage. Gradient aggregation is performed synchronously within the current phase; repartitioning only updates metadata and does not introduce neighbor traffic. We empirically verify that this simple heuristic is sufficient for our needs (Section 5 ). Therefore, we leave the implementation of more sophisticated switching heuristics for future work. 3.6. Phase-Parallel Training Gradient-only communication unlocks an additional benefit: flexible scheduling. Since partitions exchange no features or activations within an iteration, they need not run concurrently. Grappa exploits this independence to allow the sequential execution of partitions in phases. This strategy significantly amplifies training capacity, which benefits large input graphs that do not fit into the collective memory of all available machines. When accommodating concurrent training on all partitions is unfeasible, Grappa can adopt a phase-parallel training approach that divides the partitions into distinct phases, each involving the execution of only a subset of the total partitions. Each phase runs standard data-parallel SGD over its M active partitions: gradients are all-reduced within the phase, parameters are updated once, and the updated parameters and optimizer state are carried into the next phase. Over one epoch, all phases are executed so every partition contributes exactly one update per epoch, just serialized in time. Algorithm 1 details phase-parallel training. By default P=M (all partitions concurrent), but M