Why does mini-batching a 3-layer GNN on a high-degree graph cause neighbour explosion?

## The receptive field is the batch In a feed-forward network a mini-batch is a set of independent rows. In a graph network it is not. Each message-passing layer computes a node's new representation from its own current representation plus the current representations of its direct neighbours. Stack `k` layers and a node's output depends on everything within `k` hops of it. **That k-hop neighbourhood is the batch**, no matter how few nodes you actually want predictions for. So the unit of work is not "one node", it is "one node's k-hop closure". ## The arithmetic Take a graph with average degree 100 and a 3-layer model, and start from one seed node: - hop 1: about 100 nodes - hop 2: about 100 x 100 = 10,000 nodes - hop 3: about 100 x 10,000 = 1,000,000 nodes Roughly a million nodes must be loaded, their features gathered, and messages computed over the edges between them — **to produce one prediction**. Multiply by a batch of a thousand seeds and the arithmetic stops being about tuning anything; the batch is simply the graph. Two effects make reality worse than the formula. First, real degree distributions are heavy-tailed: a single hub with a million edges sits one hop from a large fraction of the graph, so one unlucky seed drags in far more than the average predicts. Second, the growth is exponential in depth, so the fix people reach for first — "just use fewer layers" — trades away the receptive field that motivated a GNN in the first place. Deduplication helps once the frontier saturates, but saturation means you are touching most of the graph anyway, which is the same problem wearing a different hat. ## Fixed-fanout neighbour sampling The standard remedy, introduced with the GraphSAGE line of work, is to stop expanding the full neighbourhood and instead **sample a fixed number of neighbours per hop**. Choose a fanout per layer, for example 25 at the first hop, 10 at the second, 5 at the third. Then per seed node: - hop 1: 25 nodes - hop 2: 25 x 10 = 250 nodes - hop 3: 250 x 5 = 1,250 nodes about 1,525 nodes total, and the number no longer depends on the graph's degree or size at all. Batch cost becomes a product of fanouts you choose, memory per step is predictable, and training time scales with the number of seeds rather than with the graph. Fanouts usually shrink with depth because the outer hops contribute the most nodes and the least signal per node. ## What capping costs you Sampling is an estimator, and estimators have properties worth stating precisely. **Variance.** Each step sees a different random neighbourhood, so gradients are noisier than full-neighbourhood training. Small fanouts at the first hop hurt most, because that hop dominates the node's own representation. **Bias from composition.** For a mean-style aggregation, uniformly sampling `k` neighbours and averaging is an unbiased estimate of the full-neighbourhood mean *at a single layer*. But layers compose through nonlinearities, and the expectation of a nonlinear function of an estimate is not the function of the expectation — so the multi-layer sampled representation is biased relative to full-neighbourhood propagation, and the bias grows with depth. **Lost degree signal.** This is the one candidates miss. If you cap at 25 neighbours and aggregate by mean, a node with 30 neighbours and a node with 50,000 neighbours look nearly identical to the model. Where degree is predictive — a hub account, a heavily cited paper — you have deleted the feature. Sum-style aggregation is worse still, because a sum over a capped sample is not on the same scale as a sum over the true neighbourhood unless you rescale by the ratio of true degree to sample size. If degree matters, put it back as an explicit node feature. **Train/serve mismatch.** Sampling at inference makes the same node score differently on repeat calls, which is awkward for auditing and for anything cached. Inference is usually cheaper than training, so many systems use the full neighbourhood or a much larger fanout when scoring — but that means serving sees a neighbourhood distribution the model was never trained on, and the shift can move calibration. Decide deliberately, and evaluate under the fanout you will actually serve with. ## The alternative shape Fixed fanout keeps the seeds arbitrary and prunes the neighbourhood. The other family does the opposite: restrict the batch to a dense subgraph so the neighbourhood is bounded by construction, and accept that edges leaving the subgraph are dropped. Which one to reach for depends on graph size, degree distribution and how much the cut edges matter.