Graph neural networks (GNNs) update each node by aggregating its neighbors' representations. Stacking layers makes each node depend on an exponentially growing neighborhood, a problem called neighbor explosion. When a large graph is split across GPUs, this shows up as boundary explosion: every layer of every epoch, each GPU must pull the features of remote "boundary" nodes it is connected to. BNS-GCN, which trains on the full graph across partitions and sends only a random subset of boundary nodes each epoch (each kept with probability $p$, its features scaled by $1/p$), cuts this traffic dramatically. On ogbn-papers100M, for example, epoch time falls from 554 s to 6 s at $p=0.01$ (BNS-GCN). But BNS-GCN still trains with first-order optimizers, so total traffic is the per-epoch boundary exchange multiplied by a large number of epochs. Second-order methods are the standard way to cut the number of rounds. They use curvature, meaning how the loss bends, to take larger steps that respect the geometry of the loss. Their distributed, communication-light forms (GIANT, FedNL, DP-KFAC) all assume that data points on different workers are independent. None has been run on top of sampled graph boundaries.
This note argues that the obvious combination, putting a Kronecker-factored curvature optimizer (K-FAC, which approximates each layer's curvature as the product of an input covariance and an output-gradient covariance) on BNS-GCN, is broken in a specific and fixable way. The $1/p$ rescaling keeps the aggregated features unbiased on average. Their second moments, however, are inflated by a term that grows like $1/p$. So the curvature estimate is systematically too large exactly along the directions spanned by boundary features, and the optimizer under-steps there. The fix is a closed-form correction that each GPU can compute from the boundary features it already received, with no extra communication. The core claim is that this debiased preconditioner lets partition-parallel GNN training reach a target accuracy with fewer epochs at aggressive sampling rates. Fewer epochs at small $p$ means fewer total boundary bytes, beyond what either boundary sampling or second-order optimization achieves alone.
Core Claim
Consider a graph convolution layer. Node $v$'s aggregated input is $z_v = \sum_u a_{vu} h_u$, where $a_{vu}$ is the normalized edge weight and $h_u$ is node $u$'s representation. Under boundary sampling, each remote neighbor $u \in B_v$ is kept independently with probability $p$ and scaled by $1/p$. The resulting $\tilde z_v$ has mean $z_v$. Its second moment, which is what K-FAC's input factor $A = \mathbb{E}[z z^\top]$ estimates, is
$$ \mathbb{E}[\tilde z_v \tilde z_v^\top] = z_v z_v^\top + \Big(\tfrac{1}{p}-1\Big)\sum_{u \in B_v} a_{vu}^2\, h_u h_u^\top . $$
The second term is an anisotropic inflation that lives in the span of boundary features. It is about 99 times the boundary second moment at the $p=0.01$ rate BNS-GCN uses on papers100M. The research file's Gap 2 points at this variance issue, but only loosely. The exact form above shows that the inflation is not noise to be averaged away: it is a bias that survives any number of epochs. Because only sampled neighbors are visible, the inflation can be estimated without bias from the sampled set $S_v$ itself, as $\frac{1}{p}(\frac{1}{p}-1)\sum_{u \in S_v} a_{vu}^2 h_u h_u^\top$, and subtracted. The corrected factor may not be positive semidefinite. We clip its eigenvalues at the damping level before inverting.
This plays the same role for graph sampling that the Marchenko-Pastur adjustment plays for Gaussian sketches in Newton Meets Marchenko-Pastur. That work computes a corrected regularizer so that averaged sketched inverse Hessians are unbiased. It motivates the idea that a sampling distortion of curvature can be corrected analytically rather than tuned away. Its derivation does not carry over, because our randomness sits on graph edges rather than in a projection matrix.
The output-gradient factor is also perturbed, because a node's backpropagated error passes through sampled aggregations in later layers. We do not claim a closed form there. We treat it empirically, and we report whether its distortion is small next to the input-factor inflation. If it is not, the claim narrows.
Research Program
The system builds on the BNS-GCN partition-parallel setup: METIS-style partitions, one GPU each, boundary features exchanged every layer with rate $p$.
The optimizer follows DP-KFAC (Scalable K-FAC Training with Distributed Preconditioning). DP-KFAC assigns the inversion of each layer's factors to one worker in rotation, and only preconditioned gradients are broadcast. We reuse that schedule. We depart from DP-KFAC in one honest way. DP-KFAC avoids communicating factors entirely by building them from the owning worker's local mini-batches. Under graph partitioning, that local data is non-independent and community-biased (the file's Gap 1). GNN layer factors are small, around $256 \times 256$ for typical hidden widths. So we all-reduce them every $T$ steps, which costs a negligible fraction of boundary traffic, rather than inheriting the partition bias. FedNL-style low-rank compression of factor differences is kept as an option only if this all-reduce ever shows up in profiles.
The analysis has two parts. First, we derive the inflation term for GCN and GraphSAGE-mean aggregation. We bound the error of the plug-in correction in terms of $p$ and the boundary degree distribution. Second, we measure preconditioner fidelity directly. At fixed weights, we compare factors and preconditioned gradient directions computed under sampling (naive and debiased) against those computed with $p=1$. Metrics are spectral relative error and cosine similarity. These are reported against $p$ and against the fraction of boundary nodes per partition.
Baselines
The naive reference is BNS-GCN exactly as published: Adam with boundary sampling at the same partitions and rates. Its reported numbers anchor the comparison. On Reddit it reaches 97.17% accuracy against 97.11% for full-graph training, and it cuts papers100M epoch time from 554 s to 6 s at $p=0.01$ (BNS-GCN). For ogbn-products, the Open Graph Benchmark reports GraphSAINT at 79.08% test accuracy (Open Graph Benchmark). That figure is the accuracy bar a faster-converging method must not fall below.
The strongest existing competitor is plain partition-parallel K-FAC on BNS-GCN, with factors built from the rescaled sampled features and with damping and learning rate tuned separately at each $p$. This is what a practitioner would build first. I found no reported result on Lacuna for K-FAC or any second-order optimizer applied to GNNs. The only K-FAC reference number in the file is DP-KFAC's 31.3% end-to-end speedup over KAISA for ResNet-50 on ImageNet, which belongs to a different domain.
Two ablations isolate the ingredient. The interior-only arm computes factors only from nodes with no remote neighbors. This removes the inflation but introduces structural bias. The full-boundary-factor arm computes factors with $p=1$ while still sampling for the forward and backward passes. It is an upper bound on what any correction could achieve.
Every arm gets the same partitions, the same model (3-layer GCN and GraphSAGE, hidden width 256), the same GPUs, and the same hyperparameter search budget, with the search run at each $p$. Beating the strongest baseline means reaching the target accuracy with at least 30% fewer total boundary bytes at $p \le 0.1$, with final accuracy within 0.2 points. Targets are 97.0% on Reddit and 79% on ogbn-products. It also means closing at least half the gap between the naive K-FAC arm and the full-boundary-factor upper bound.
Why not just…?
Why not just increase the damping in naive K-FAC? This is the main threat. Damping adds a multiple of the identity in every direction, whereas the inflation is concentrated in boundary-feature directions and its size differs per partition. A single damping value should therefore either under-correct boundary directions or over-damp interior ones. The per-$p$-tuned naive arm tests exactly this. If tuned damping matches the debiased arm on both fidelity and bytes-to-target, the correction adds nothing, and we will report that.
Why not just keep Adam with boundary sampling? BNS-GCN is already fast per epoch, and Adam's per-coordinate scaling is cheap. But total traffic scales with epochs. On large graphs, remote data movement can take up to 80% of training time (Global Neighbor Sampling). It is unknown whether GNN losses are ill-conditioned enough for curvature to cut epochs; the file's evidence for fewer rounds comes from convex problems in GIANT and DANE. The first experiment, run at $p=1$, settles this before anything else.
Why not just precompute propagation and train an MLP, avoiding boundaries entirely? On homophilic graphs like ogbn-products, decoupled models such as GAMLP may simply win, and we include a SIGN-style reference to show where. Decoupling falls short when propagation must be learned. Pre-propagation models trail message-passing GNNs by 11% on roman-empire, and closing that gap requires re-propagating hidden states at runtime (Revisiting Pre-Propagation GNNs). Attention models cannot be precomputed at all (FedGCN). Our target is that message-passing regime.
Why not just use historical boundary activations as control variates? Stale activations reduce sampling variance enough to train with two sampled neighbors per node (Stochastic Training of GCNs with Variance Reduction). That is a legitimate alternative, but it requires storing every boundary node's history, which works against the memory savings BNS-GCN reports. We include it as an arm on Reddit, where its memory cost fits.
Proposed Experiments
The study runs on Reddit, Yelp, ogbn-products and ogbn-papers100M, with 4 to 8 partitions, and roman-empire as a heterophily check. Each run sweeps $p \in \{1, 0.1, 0.01\}$.
The first decisive check is whether full-graph K-FAC at $p=1$ reduces epochs-to-target compared with Adam. If it does not, the line stops there, and that negative result is itself worth reporting.
The second check is whether naive K-FAC degrades as $p$ shrinks while the debiased version tracks the full-boundary-factor upper bound. We measure this both in bytes-to-target and in direct preconditioner fidelity. Fidelity should worsen with the boundary fraction for the naive arm and stay flat for the debiased one.
The third check compares against tuned damping, which the correction must beat to justify itself. We also report wall-clock time, peak memory, and the factor all-reduce cost as a share of boundary traffic.
References
- BNS-GCN: Efficient Full-Graph Training of Graph Convolutional Networks with Partition-Parallelism and Random Boundary Node Sampling
- GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
- FedNL: Making Newton-Type Methods Applicable to Federated Learning
- Scalable K-FAC Training for Deep Neural Networks With Distributed Preconditioning
- Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs
- Communication-Efficient Distributed Optimization using an Approximate Newton-type Method
- Graph Attention Multi-Layer Perceptron
- Revisiting Pre-Propagation GNNs: Robust Diffusion Operators and Hidden-State Re-Propagation
- FedGCN: Convergence-Communication Tradeoffs in Federated Training of Graph Convolutional Networks
- Stochastic Training of Graph Convolutional Networks with Variance Reduction