Stochastic Training of Graph Convolutional Networks with Variance Reduction

1. Introduction

• GCN representations recursively aggregate neighbors, causing a node’s receptive field to grow exponentially with the number of layers and making batch training difficult at scale.The paper notes batch training’s slow convergence and GPU-memory requirements.Source: §1 · p. 1
• Neighbor sampling reduces receptive-field size, but lacks a convergence guarantee and uses D(1)=10 and D(2)=25 in the cited two-layer setup.That setup has time complexity 250 times that of MLP training.Source: §1 · p. 1
• Control variate-based algorithms use historical node activations to reduce estimator variance and provide convergence to a local optimum regardless of neighbor sampling size.Their estimator variance depends on the difference between current activations and historical values, rather than activation magnitude.Source: §1 · p. 1
• With D(l)=2, the algorithms achieve the exact algorithm’s predictive performance in a comparable number of epochs across the tested datasets; Reddit training is 7 times shorter than the best-performing competitor.The competitor comparison covers the exact, neighbor-sampling, and importance-sampling algorithms.Source: §1 · p. 2

2. Backgrounds

• The section reviews graph convolutional networks, stochastic training, neighbor sampling, and importance sampling as approaches to graph learning and its computational costs.The paper frames its algorithm as applicable beyond semi-supervised node classification to models and tasks that compute average neighbor activations.Source: §2 · p. 2, §2.1 · p. 2

2.1. Graph Convolutional Networks

• A GCN layer averages neighboring activations, then applies a shared fully connected transformation; stacking layers lets representations use information from distant neighbors.The background defines a node’s receptive field as its L-hop neighbors.Source: §2.1 · p. 2

2.2. Stochastic Training

• A minibatch stochastic gradient avoids iterating over all labeled nodes, but large receptive fields can still make computing it expensive.On NELL, a node has an average of 1,597 two-hop neighbors, about 2.4% of the graph’s nodes.Source: §2.2 · pp. 2–3

2.3. Neighbor Sampling

• Neighbor sampling reduces the receptive field by choosing D(l) neighbors per node, but its predictions and gradients are biased and SGD convergence is not guaranteed unless D(l) tends to infinity.For a two-layer GCN, the cited D(1)×D(2)=250 receptive field remains larger than MLP’s size of 1.Source: §2.3 · p. 3

2.4. Importance Sampling

• Importance sampling subsamples nodes across a layer rather than sampling neighbors per node, but convergence is guaranteed only as sample size S goes to infinity.The authors report that IS can allocate many samples to some nodes and none to others, leaving the latter with zero activations.Source: §2.4 · p. 3

3.1. Control Variate Based Estimator

• Historical activations serve as control variates, replacing recursively computed neighbor activations with an affordable approximation.The history is updated whenever a node’s activation is computed.Source: §3 · p. 3, §3.1 · p. 3
• With fixed model weights, histories eventually match current activations, making the control-variate estimator exact and zero-variance.The estimator’s variance depends on the difference between current and historical activations, which converges to zero during training.Source: §3.1 · p. 4, §3.2 · p. 4

3.2. Variance Analysis

• The CV estimator has smaller variance than neighbor sampling, and its variance vanishes as histories approach current activations.The analysis also characterizes neighbor-sampling variance using differences among weighted neighbor activations.Source: §3.2 · p. 4

3.3. Implementation Details and Time Complexity

• Each iteration samples a minibatch, builds its computation graph by sampling neighbors, computes predictions and gradients, updates parameters, and refreshes activation histories.The sampled receptive field is built from the minibatch outward, with each node selected as its own neighbor.Source: §3.3 · p. 4

4. Theoretical Results

• The convergence analysis considers epochs that scan all nodes so every node’s activation history is updated at least once per epoch.At training time weights change by SGD; at testing time they remain fixed.Source: §4 · p. 5

4.1. Exact Testing

• With fixed model weights, CV activations become exact after L epochs, yielding exact test predictions without loading the entire graph into memory.The paper contrasts this with neighbor sampling, which cannot recover exact predictions unless sample size goes to infinity.Source: §4.1 · p. 5

4.2. Convergence Guarantee

• As the iteration limit grows, the expected squared gradient norm tends to zero, establishing convergence toward a local optimum for arbitrary neighbor-sampling sizes.The theorem assumes Lipschitz activation and loss-gradient functions, bounded gradients, and a smooth loss.Source: §4.2 · p. 5

5. Handling Dropout of Features

• The method treats dropout masks as an additional source of randomness and seeks a cheap estimator for the randomly activated neighbor average.The ideal estimator would match that neighbor average’s distribution, but the paper instead targets matching its mean and variance.Source: §5 · p. 5

5.1. Control Variate for Dropout

• The dropout control-variate estimator is designed to match the neighbor average’s mean and variance, since an estimator with the same full distribution is difficult to construct.The method separates the mean and variance using a historical mean activation and a model copy without dropout.Source: §5 · p. 5, §5.1 · p. 6

5.2. Variance Analysis

• Under the analysis, CVD is the only stochastic estimator besides the exact estimator with the correct dropout variance; CV and CVD neighbor-sampling variance depends on Δμ and converges to zero.The analysis assumes activations of different nodes are uncorrelated.Source: §5.2 · p. 6

5.3. Preprocessing Strategy

• The preprocessing strategy places dropout after neighbor averaging, allowing PX to be precomputed and reducing the number of graph-convolution layers by one.The authors state that the two dropout placements perform similarly in practice; most GCNs have two graph-convolution layers.Source: §5.3 · p. 6

6. Experiments

• The experiments assess variance and convergence on six datasets, using Micro-F1 for PPI and accuracy for the other five.The study uses GCN on four datasets and GraphSAGE on Reddit and PPI.Source: §6 · pp. 6–7

6.1. Impact of Preprocessing

• The three preprocessing settings perform similarly, so the experiments use the fastest, preprocessed M1+PP setting as the exact baseline.The settings are M0, M1, and M1+PP.Source: §6.1 · p. 7

6.2. Convergence Results

• With dropout, CVD+PP alone reaches validation accuracy comparable to the exact algorithm on all datasets, with epoch-wise convergence comparable to M1+PP.CV+PP is also comparable except on PPI; without dropout, CV+PP reaches the same training loss as M1+PP, while NS, NS+PP, and IS+PP have higher losses.Source: §6.2 · pp. 7–8, Figure 2 · p. 7

6.3. Further Analysis on Time Complexity, Testing Accuracy and Variance

• CVD+PP is about 7 times faster than M1+PP to reach 96% validation accuracy on Reddit; NS and IS+PP do not reach that threshold.The comparison reports average epochs and time to the threshold.Source: §6.3 · p. 8, Table 4 · p. 8
• Using the same M1+PP-trained model, CV matches the exact algorithm's test accuracy, while NS and NS+PP perform much worse.For gradients, CV+PP is almost unbiased without dropout; with dropout, CV+PP and CVD+PP usually have lower bias and variance than NS and NS+PP.Source: §6.3 · p. 8

• Control-variate algorithms achieve convergence speed comparable to the exact algorithm with D(l) = 2, making per-epoch cost comparable to MLP training while retaining guarantees of exact prediction and convergence to a local optimum.Source: §7 · p. 8

A Derivation of the variance

• The variance derivation uses a variance decomposition when the conditional expectation of f(X, Y) over X is zero, separating the f and g contributions.Source: A Derivation of the variance · p. 12

B Proof of Theorem 1

• For fixed model weights, CV activations become exact after L epochs.Source: B Proof of Theorem 1 · p. 15

C Proof of Theorem 2

• The convergence proof proceeds through activation approximation, gradient-bias control, and a theorem that SGD changes weights slowly enough for the bias to vanish.Source: C Proof of Theorem 2 · p. 16

C.1 Single layer GCN

• For a single layer, bounded changes in inputs, weights, and stochastic propagation yield outputs that change slowly and remain close to exact outputs.Source: §C.1 · pp. 16–17

C.2 Lemma 1: Activation of Multi-layer GCN

• For multiple layers, CV activation approximation error is bounded by the rate of change of model weights, regardless of the stochastic propagation matrix.Source: §C.2 · p. 18

C.3 Lemma 2: Gradient of Multi-layer GCN

• With slowly changing weights, the expected CV gradient over propagation sampling and minibatches is close to the exact full-batch gradient.Source: §C.3 · pp. 19–20

C.4 Proof of Theorem 2

• After a warm-up of LI steps, the proof adapts an SGD analysis to biased stochastic gradients and derives an asymptotic unbiasedness result.The theorem states that, under its assumptions, SGD converges to a local optimum; the supplied passages do not include its explicit bound.Source: §C.4 · pp. 22–23

D Pseudocode

• Each iteration builds a minibatch-specific computation graph, propagates predictions, computes gradients, updates parameters, and refreshes historical activations.The algorithm constructs receptive fields and stochastic propagation matrices for the minibatch.Source: D Pseudocode · p. 24

D.1 Training with the CV estimator

• The CV estimator trains with stochastic propagation and updates historical activations for nodes in the receptive fields.Its gradients are computed by backpropagation through the forward pass.Source: §D.1 · p. 24, D Pseudocode · p. 24

D.2 Training with the CVD estimator

• The CVD estimator runs two network versions, with and without dropout, to compute activation samples and their mean.It otherwise follows the CV estimator’s training procedure.Source: §D.2 · p. 25

E Experiment setup

• The Citeseer, Cora, PubMed, and NELL experiments use two graph-convolution layers, with dataset-specific hidden widths, dropout rates, and weight decay.Citeseer, Cora, and PubMed use 32 hidden units; NELL uses 64.Source: E Experiment setup · p. 25
• PPI and Reddit use GraphSAGEmean with two linear layers per graph-convolution layer, layer normalization, and dataset-specific hidden widths.The setup uses 20% dropout and no weight decay.Source: E Experiment setup · p. 25
• The PPI architecture reaches 97.8% testing micro-F1, while the reported architecture improvement over [3] is attributed to wider hidden layers, dropout, and layer normalization.The supplied passages do not identify the metric associated with the truncated comparison to 59.8%.Source: E Experiment setup · pp. 25–26

F Experiment for 3-layer GCNs

• In the three-layer Reddit experiment, among approximate algorithms CVD+PP performs best, followed by CV+PP, then NS+PP and NS; the graph is subsampled to maximum degree 10.Table 1 reports time to reach 0.94 testing accuracy.Source: F Experiment for 3-layer GCNs · p. 26

G Correlation between node activations

• For two-layer GCNs, node activations are independent; for deeper GCNs, correlations remain weak, which the authors attribute to sparsity of the sampled graph.The analysis assumes uncorrelated node activations for the CVD estimator.Source: G Correlation between node activations · p. 27

G.1 Results for 2-layer GCNs

• For two-layer GCNs with a pre-processed first layer, the paper argues that first-layer node activations are independent because their dropout masks are independent.The text generalizes independence to deeper models when two nodes’ receptive fields do not overlap.Source: §G.1 · p. 27

G.2 Empirical results for deeper GCNs

• Across Citeseer, Cora, PubMed, and PPI, feature and neighbor correlations in 10-layer GCNs remain much smaller than one and show no strong increase after layer three.Average neighbor correlation is close to zero in the first layer; the authors report that both correlation measures remain on the same order of magnitude.Source: Figure 2 · p. 28, §G.2 · p. 29