GraphSAGE: inductive learning on graphs

Click node 1 — it has three neighbors, but only two get highlighted. That's a fixed-size sample, not the full neighborhood. Compare the two readouts: sampling and using everything don't always agree.

GraphSAGE ("SAmple and aggreGatE") changes two things about the previous chapter's GCN (short for Graph Convolutional Network). First, it aggregates a fixed-size random sample of neighbors instead of all of them — bounded work per node, no matter how high the degree gets:

• $h_v^{(k)}$ — node $v$'s feature after $k$ rounds of message passing.
• $h_v^{(k+1)}$ — node $v$'s updated feature after one more round.
• $h_u^{(k)}$ — a sampled neighbor $u$'s current feature.
• $\mathcal{N}(v)$ — node $v$'s full neighborhood, before sampling.
• SAMPLE($\mathcal{N}(v), K$) — a fixed-size random draw of $K$ neighbors from $v$'s full neighborhood.
• $K$ — the sample size: how many neighbors get aggregated, regardless of how many actually exist.
• AGGREGATE — the learned combining function, applied to any neighborhood, seen or unseen.

1. Learns a function, not a lookup table

   Second — and this is the bigger idea — it learns an aggregation function, not a per-node lookup table.

2. Transductive methods can't handle unseen nodes

   A method that memorizes one embedding vector per node (like node2vec) is transductive: it has nothing to say about a node it never saw.

3. Inductive: any neighborhood works immediately

   GraphSAGE's function takes any neighborhood as input, so it's inductive: hand it a brand-new node's neighborhood and it produces an answer immediately.

Add the new node. It was never part of the original six-node graph, never "trained on" — but the exact same aggregation function runs on it instantly, because the function only ever looked at neighbor values, never at a fixed table of node identities.

With sample size $K=2$ (always take the two lowest-numbered neighbors, standing in for a random draw):

1. A low-degree node: sampling changes nothing

   Node $0$ has exactly two neighbors, $\{1,2\}$ — sampling two out of two keeps everything. Sampled mean $=\frac{1+2+0}{3}=1.0$, identical to the full mean.

2. A high-degree node: sampling genuinely loses information

   Node $1$ has three neighbors, $\{0,2,3\}$. Sampling keeps only $\{0,2\}$, dropping neighbor $3$ (feature $3$). Sampled mean $=\frac{2+1+0}{3}=1.0$; the true full-neighborhood mean is $\frac{2+1+0+3}{4}=1.5$ — a real, measurable gap, the price of bounding the work per node.

3. A node that never existed during training

   A new node with feature $4$, connected only to node $0$ (feature $1$): its aggregate is $\frac{4+1}{2}=2.5$, using the same function as every original node — no new parameters, no retraining pass, just one more function call.