GraphSAGE and Neighbourhood Sampling

Many early graph neural networks, like the standard graph convolutional network, effectively learn one embedding per node by operating on the entire fixed adjacency matrix at once. That has two problems: the whole graph — every node's full neighborhood — has to be processed together, which doesn't scale to graphs with millions of nodes, and the resulting model is tied to the specific nodes it was trained on, unable to handle a brand-new node (a new client, a newly listed security) appearing after training without retraining from scratch. GraphSAGE (SAmple and aggreGatE) fixes both at once: it learns a general aggregation function, not per-node embeddings, and trains it on randomly sampled slices of each node's neighborhood rather than the whole thing.

The analogy: learning a recipe, not memorising every finished dish

A model that learns one embedding per node is like memorising the finished appearance of every dish a specific kitchen has ever made — useless the moment a genuinely new dish arrives. GraphSAGE instead learns the recipe: a general rule for how to combine a small sample of ingredients (a node's own features plus a handful of its neighbors', not necessarily all of them) into a finished dish. Because it's a recipe and not a memorised photograph, it can be applied to an entirely new dish — a new node with new neighbors — without ever having seen it during training, and it can be cooked using only a manageable sample of ingredients rather than the entire pantry at once.

The mechanics: sample, aggregate, combine, repeat

For a node $v$ at layer $k$, GraphSAGE samples a fixed-size subset $\mathcal{N}_s(v)$ of $v$'s neighbors (say, up to 10, chosen at random if there are more), aggregates their layer-$(k-1)$ representations with a learned aggregator function, and combines that with $v$'s own representation:

$$h_v^{(k)} = \sigma\Big( W^{(k)} \cdot \text{CONCAT}\big[h_v^{(k-1)},\ \text{AGGREGATE}\big(\{h_u^{(k-1)} : u \in \mathcal{N}_s(v)\}\big)\big] \Big)$$

In words: take node $v$'s current representation, take some combined summary (mean, or a small learned pooling network) of a random sample of its neighbors' representations, stick the two together, and pass them through a learned linear layer and nonlinearity to get $v$'s updated representation. Stacking $K$ such layers lets information from up to $K$ hops away reach $v$, with the sampling — not the full neighborhood — happening at every hop.

Worked example 1: sampling shrinks the computation, concretely

Suppose node $v$ has 200 real neighbors, sample size $S=10$. A full-neighborhood method processes all 200 at every layer; GraphSAGE processes 10. Stacking $K=2$ layers with a full neighborhood, if each of those 200 neighbors itself has up to 200 neighbors, the second layer could in principle need up to $200 \times 200 = 40{,}000$ node representations feeding into $v$'s final embedding. With sampling ($S=10$ at each hop): $10 \times 10 = 100$ node representations reach $v$ across two hops — a 400x reduction in the second-hop computation, which is what makes GraphSAGE practical on graphs where some nodes (a large custodian bank, a heavily-traded stock) have thousands of neighbors.

Worked example 2: generalising to an unseen node at inference time

Suppose GraphSAGE was trained on a counterparty graph of 5,000 firms. A new firm, firm 5,001, is onboarded after training, forming trading links to three existing, already-embedded firms. Because GraphSAGE never memorised per-node embeddings — only the aggregation function — computing firm 5,001's embedding requires no retraining at all: sample (or, since it only has 3 neighbors, use all of) its neighbors' existing representations, run the same learned AGGREGATE and combine step used for every other node, and out comes a usable embedding for the brand-new firm immediately. A transductive method (one that learned a fixed embedding table indexed by node identity, like the original graph convolutional network setup) has no defined output for a node it never indexed during training at all.

Each training step here nudges parameters using one mini-batch, the same spirit as GraphSAGE nudging its aggregator using one randomly sampled neighborhood each pass — neither method needs to see the entire dataset (or entire neighborhood) at once to make steady progress.

What this means in practice

GraphSAGE-style inductive models are the right default whenever a graph grows over time — new counterparties, new listed instruments, new wallets in a transaction network — since a transductive model would need retraining on the whole graph every time the node set changes, while GraphSAGE only needs a forward pass through its already-trained aggregation function.