How does cluster-based subgraph mini-batching train a GNN on a 200-million-node graph?

## Two ways to bound a batch There are only two shapes of answer to "a k-layer GNN's batch is its k-hop closure". Fixed-fanout sampling keeps arbitrary seeds and **prunes** the neighbourhood. Subgraph batching does the reverse: it **chooses a batch that is closed enough to begin with** and accepts the edges it loses at the boundary. ## The mechanism Offline, run a graph partitioner that splits 200 million nodes into a large number of parts — thousands or tens of thousands — with two objectives: parts of roughly equal size, and as few edges crossing between parts as possible. Community structure makes this achievable: real graphs are far from uniformly random, so most edges are internal to some community, and a good partition keeps them there. At training time, a mini-batch is the **induced subgraph** of one part (or of several parts sampled together): its nodes, plus exactly the edges whose endpoints are both inside. Then run ordinary full-graph-style propagation on that subgraph. Nothing outside the batch is fetched, so: - **Cost is linear in the batch's edges per layer**, not exponential in depth. You can stack more layers without the frontier growing. - **Memory is predictable** — it is the size of the part you chose, which the partitioner controls. - **Every labelled node in the part is a usable training target**, not just a designated seed. Compare with fanout sampling, where a large sampled subgraph exists to produce predictions for a handful of seeds; here the same computation is amortised over hundreds or thousands of labels. - **Locality is good**: the batch is a contiguous, dense block of the graph, which is far friendlier to whatever storage layer holds it than a scattered random frontier. ## What it costs **Dropped cut edges.** This is the defining tradeoff, and the honest framing is that the loss is *systematic*, not random. The partitioner deliberately minimises cut edges — which means the edges it does cut are the ones that were hardest to keep, the bridges between otherwise separate communities. On a payments graph those bridges carry a lot of the signal: a mule account whose whole purpose is to connect two clusters that should not be connected looks, inside its own partition, like an ordinary node. Train exclusively on within-partition edges and the model never learns from the structure you most care about. **Biased, correlated gradients.** Stochastic gradient descent assumes each batch is a roughly unbiased sample of the loss. A partition is a community: labels within it are correlated, class balance drifts from the global balance, and feature distributions are local. One part per step therefore gives a high-variance, biased gradient direction, and the model can oscillate between the characteristics of successive communities. **Partition staleness.** The partition is a preprocessing artefact computed on a snapshot. A payments graph grows daily; new nodes have no assignment, and yesterday's communities drift. Partitioning at this scale is itself a substantial job, so you cannot rerun it per epoch. ## Mitigations The standard fix for both the dropped edges and the correlated gradients is the same move: **do not use one part per batch.** Draw several parts at random and take the induced subgraph of their union. Every cut edge whose two endpoints happen to land in the chosen set comes back, so across many steps a random fraction of cut edges is seen; and a batch made of several unrelated communities is a much better sample of the global distribution. Making parts smaller and more numerous increases how many you can combine per batch, at the cost of cutting more edges in the first place. Other levers: randomised subgraph samplers that draw nodes, edges or short walks and apply normalisation coefficients to correct the resulting aggregation and loss bias — the approach the GraphSAINT line takes — and periodic re-partitioning, with new nodes assigned to the partition holding most of their neighbours until the next full run. ## When to prefer it Prefer subgraph batching when labels are dense (many labelled nodes per region, so the amortisation pays off), when the graph is large but has genuine community structure, when you want depth without a frontier, and when your storage layer rewards contiguous access. Prefer fixed-fanout sampling when labels are sparse and scattered, when the degree distribution is so heavy-tailed that no partition is balanced, or when the cross-community edges are the whole point of the task and you cannot afford to drop them systematically. ## Serving is a separate decision Cluster batching is a *training* strategy. At inference you are usually asked about one node, and there is no batch to partition. You score it from its actual neighbourhood — full or sampled. That means the neighbourhood distribution at serving differs from the one seen in training, where cut edges were missing. Measure that gap offline under the exact serving neighbourhood rather than assuming the training-time metric carries over.