Neighborhood Sampling

A node's two-hop neighbourhood on a social graph can be most of the graph, so computing one node's representation exactly can mean touching millions. Sampling fixes a budget instead: take a handful of neighbours per hop, accept that the answer is an estimate, and get a model that trains on graphs too large to hold at once.

This is what makes graph learning inductive rather than transductive — the model learns an aggregator rather than an embedding per node, so it can be applied to nodes it never saw. The cost is variance: every gradient is computed from a sampled subgraph, and the fewer neighbours sampled the noisier the estimate. Sampling is also why the same node gets slightly different representations on different passes.

Sampling S neighbours per hop over L hops bounds the work per node at S super ^L  rather than the true neighbourhood size, which is what turns an intractable expectation into a Monte Carlo estimate. The estimator is unbiased for mean aggregation and the variance falls as 1/S, so doubling the sample buys a factor of √2 in noise — the same exchange rate batch size buys everywhere else.