# GraphSAGE

> GraphSAGE learns shared aggregators, not per-node vectors, so it embeds unseen nodes: each layer samples a fixed number of neighbours (25, then 10), aggregates them by mean, LSTM or max-pool, concatenates the node's own vector and applies W.

Source: https://www.mlfoundry.in/learn/graphsage  
Section: Deep Learning › Graph Neural Networks (GNNs)  
Level: core · 8 min read · updated 2026-10-21

**GraphSAGE:** (SAmple and aggreGatE) is an inductive message-passing GNN. Each layer samples a fixed-size set of a node's neighbours, aggregates their vectors with a learned, permutation-invariant function, and combines the result with the node's own vector. Introduced by William L. Hamilton, Rex Ying and Jure Leskovec, "Inductive Representation Learning on Large Graphs" (NeurIPS 2017).

The task is to map each node of a graph to a vector $z_v$ that a classifier or a link scorer can use (see **Node classification** and **Link prediction**). Shallow methods such as DeepWalk and node2vec learn one free vector per node (see **Graph representation learning**). They are **transductive**: a node added after training has no vector until the whole optimisation is rerun. A spectral **Graph Convolutional Network (GCN)** in its original form is trained full-batch on one fixed graph, with the normalised adjacency of the whole graph in memory.

GraphSAGE is **inductive**. It learns $K$ weight matrices and aggregators, not node vectors. Any node with features and neighbours, in the training graph or in a new graph, gets an embedding by running the same $K$ layers on its local neighbourhood. The aggregator must not depend on neighbour order, because neighbours have no natural order.

## Sample, aggregate, combine

$$
\begin{aligned}h^{k}_{\mathcal N(v)}&=\operatorname{AGG}_k\big(\{h^{k-1}_u : u\in\mathcal S_k(v)\}\big)\\ h^{k}_v&=\sigma\big(W^{k}\,[\,h^{k-1}_v\,\Vert\,h^{k}_{\mathcal N(v)}\,]\big),\qquad h^{k}_v\leftarrow h^{k}_v/\lVert h^{k}_v\rVert_2\end{aligned}
$$

- $h^0_v=x_v$: input node features; after K layers, z_v = h^K_v
- $\mathcal S_k(v)$: a uniform sample of $S_k$ neighbours of $v$, redrawn every minibatch (with replacement if the degree is below $S_k$)
- $[\cdot\Vert\cdot]$: concatenation: the node's own vector is kept separate from the neighbourhood summary, a skip connection
- $W^k$: shared weight matrix of layer $k$, shape $d_k\times 2d_{k-1}$; $\sigma$ is ReLU

> Figure: GraphSAGE with K = 2 on a toy graph. Target A has 5 neighbours; with S1 = 3 it samples B, C and D, and each of those samples S2 = 2 of its own neighbours. The sampled nodes form a computation tree. Layer 1 builds h¹ for A, B, C and D from raw features, and layer 2 combines them into z_A. Each layer is aggregate, concatenate with self, multiply by W^k, ReLU and normalise. With the paper's S1 = 25 and S2 = 10, one target needs at most 1 + 25 + 250 = 276 nodes, however large its true 2-hop neighbourhood.

**Aggregators.** The paper compares four. **Mean**: the elementwise mean of the sampled $h_u$. **GCN**: the mean over $\mathcal S(v)\cup\{v\}$, followed by $W$ and $\sigma$ with no concatenation; this is an inductive form of the GCN layer. **LSTM**: a **Long short-term memory (LSTM)** network run over the neighbours. It is not permutation-invariant, so it is applied to a random permutation. **Pooling**: each neighbour goes through a one-layer MLP, then an elementwise max.

$$
\operatorname{AGG}^{\text{pool}}_k=\max_{u\in\mathcal S_k(v)}\sigma\big(W_{\text{pool}}\,h^{k-1}_u+b\big)\qquad\qquad J(z_u)=-\log\sigma(z_u^{\top}z_v)-Q\,\mathbb E_{v_n\sim P_n}\log\sigma(-z_u^{\top}z_{v_n})
$$

- $\max$: elementwise max over the transformed neighbours: each output dimension reports its strongest neighbour
- $J(z_u)$: unsupervised loss: $v$ co-occurs with $u$ on a short random walk, $v_n$ are $Q$ negative samples from $P_n$, as in **Word2Vec**

With labels, the final $z_v$ instead goes to a softmax or sigmoid layer trained with cross-entropy. The cost per target is $O(\prod_k S_k)$, independent of the graph's size or degree, because minibatches are built from samples only.

**Minibatch forward pass (Algorithm 2 of the paper)**

1. Start from the batch's target nodes: $\mathcal B^K$.
2. Sample backwards: for $k=K,\dots,1$, set $\mathcal B^{k-1}=\mathcal B^k\cup\bigcup_{v\in\mathcal B^k}\mathcal S_k(v)$. $\mathcal B^0$ holds every node whose raw features are needed.
3. Compute forwards: for $k=1,\dots,K$, compute $h^k_v$ for $v\in\mathcal B^k$ only, from $h^{k-1}$ of $v$ and its samples.
4. Output $z_v=h^K_v$ for the targets, apply the loss, backpropagate into $W^1,\dots,W^K$ and the aggregator weights.

**Paper setting (Hamilton et al., 2017)**

- **Depth and fan-out:** K = 2, S1 = 25, S2 = 10. K = 2 beat K = 1 by roughly 10–15 %; K = 3 added at most a few percent at 10–100× the runtime
- **Reddit:** 232,965 posts from September 2014, linked when the same user commented on both; average degree 492. Features: 300-d GloVe vectors of the title and comments plus post statistics (602-d in the released data). Train on the first 20 days, test on later posts
- **PPI:** 24 protein–protein interaction graphs (one per human tissue): 20 for training, 2 for validation, 2 for testing, so test graphs are entirely unseen. 121 multi-label targets, about 2,373 nodes per graph
- **Supervised micro-F1:** GraphSAGE-LSTM: 0.954 on Reddit, 0.612 on PPI. The LSTM and pooling aggregators beat mean and GCN; pooling was about as accurate as LSTM and faster
- **Later:** the **Graph Attention Network (GAT)** paper reported 0.973 micro-F1 on PPI. PinSage (Ying et al., 2018) scaled the GraphSAGE recipe to Pinterest's graph of 3 billion nodes and 18 billion edges, with neighbourhoods chosen by random-walk visit counts

## Fan-out against cost

Without sampling, $K$ layers on a node of degree $d$ touch about $d^K$ nodes. On Reddit that is $492^2\approx242{,}000$ per target for $K=2$, close to the whole graph. Sampling caps it at $S_1+S_1S_2=275$ edges. The price is variance: the sampled mean is an unbiased but noisy estimate of the full neighbourhood mean, and the noise shrinks as $S$ grows.

> Figure: A 48-node two-community graph (174 edges, 12 between communities, degrees 2–11). Each node's scalar feature is ±0.5 plus N(0, 1) noise, so sign(x) alone classifies 64.6 % correctly. Neighbours are sampled without replacement, as PyG does. Two mean layers h^k = ½ h^(k−1) + ½ mean(sampled neighbours) average the noise away. At the default S1 = 5, S2 = 3, target 0 (degree 11) uses 20 of its 105 tree edges, and its sampled h² = −0.405 against −0.433 with full neighbourhoods. Over all nodes, sign(h²) is right 83.3 % of the time (full neighbourhoods: 85.4 %) at 19.1 edges per node instead of 65.2. With S1 = S2 = 1 it falls to 60.4 %, worse than the raw feature. The sweep (5 seeds) climbs from 66.7 % at S = 1 to 77.9 % at S = 3 and 85.4 % once S reaches the maximum degree.

## Worked example

Worked example: one mean-aggregator layer on the graph A–B, A–C, A–D, B–C, D–E with features A (1, 0), B (0, 1), C (1, 1), D (0, 2), E (2, 0) and W = [[1, 0, 1, 0], [0, 1, 0, −1]], so W·[x_v ‖ h_N] = (x₁ + h₁, x₂ − h₂) (computed with numpy)

| node | neighbours used | h_N (mean) | W·[x_v ‖ h_N] | ReLU | h¹ (unit length) |
| --- | --- | --- | --- | --- | --- |
| A | B, C, D | (0.333, 1.333) | (1.333, −1.333) | (1.333, 0) | (1, 0) |
| B | A, C | (1, 0.5) | (1, 0.5) | (1, 0.5) | (0.894, 0.447) |
| C | A, B | (0.5, 0.5) | (1.5, 0.5) | (1.5, 0.5) | (0.949, 0.316) |
| D | A, E | (1.5, 0) | (1.5, 2) | (1.5, 2) | (0.6, 0.8) |
| E | D | (0, 2) | (2, −2) | (2, 0) | (1, 0) |
| A, sampled S = 2 | B, D | (0, 1.5) | (1, −1.5) | (1, 0) | (1, 0) |
| new node F, x = (1, 2) | B, E | (1, 0.5) | (2, 1.5) | (2, 1.5) | (0.8, 0.6) |

The last row is the inductive step. F joins the graph after training, attached to B and E, and gets an embedding from the same $W$ with no retraining. The sampled row for A shows the cost of sampling: a different sample, $\{B,C\}$, would give $h_{\mathcal N}=(0.5,1)$ and a different pre-activation $(1.5,-1)$. Here ReLU and normalisation hide the difference.

```python
import torch, torch.nn.functional as F
from torch_geometric.datasets import Reddit
from torch_geometric.loader import NeighborLoader
from torch_geometric.nn import SAGEConv

data = Reddit("data/Reddit")[0]                  # 232,965 nodes, 602 features, 41 classes
loader = NeighborLoader(data, num_neighbors=[25, 10],      # S1, S2 as in the paper
                        batch_size=512, input_nodes=data.train_mask, shuffle=True)

class SAGE(torch.nn.Module):
    def __init__(self, d_in, d_h, d_out):
        super().__init__()
        self.c1 = SAGEConv(d_in, d_h, aggr="mean")
        self.c2 = SAGEConv(d_h, d_out, aggr="mean")
    def forward(self, x, edge_index):
        x = F.relu(self.c1(x, edge_index))
        x = F.dropout(x, p=0.5, training=self.training)
        return self.c2(x, edge_index)

model = SAGE(data.num_features, 256, 41)
opt = torch.optim.Adam(model.parameters(), lr=0.01)
model.train()
for batch in loader:                              # one sampled 2-hop subgraph per batch
    opt.zero_grad()
    out = model(batch.x, batch.edge_index)[:batch.batch_size]   # target nodes come first
    loss = F.cross_entropy(out, batch.y[:batch.batch_size])
    loss.backward()
    opt.step()
```

Two-layer GraphSAGE on Reddit with sampled minibatches in PyTorch Geometric (not run here). PyG's SAGEConv computes W₁x_v + W₂·mean(x_u), which equals W·[x_v ‖ mean] with W = [W₁ W₂]; normalize=False by default

> **Why the concatenation matters:** A GCN layer mixes a node with its neighbours in one weighted average, so after a few layers the node's own signal is diluted (over-smoothing, see **Graph representation learning**). GraphSAGE's $[h_v\Vert h_{\mathcal N(v)}]$ gives the self part its own weights. The model can learn how much to trust the neighbours, which matters on graphs where neighbours often have different labels. In the paper, the GCN-style aggregator without concatenation was the weakest of the four.

> **Sample for training, not necessarily for evaluation:** Sampled neighbourhoods make predictions random: rerun inference and some labels flip. For evaluation, compute layer by layer over the full graph (all neighbours, one layer at a time, for all nodes), which costs about one pass over the edges per layer. Also, inductive does not mean free of distribution shift: a new graph with different degrees or feature statistics can still hurt accuracy.

**Strengths**

- Inductive: embeds new nodes and whole new graphs (PPI test graphs) without retraining
- Cost per target is bounded by the product of fan-outs, independent of graph size, so minibatch training scales to very large graphs
- Concatenating self and neighbours keeps the node's own signal

**Limitations**

- Sampling adds variance; small fan-outs lose accuracy
- The computation tree still grows exponentially with depth, so K stays at 2–3
- Mean and max aggregators cannot tell some neighbourhoods apart (see **Graph Isomorphism Network (GIN)**); the LSTM aggregator is not permutation-invariant

**Question:** A 3-layer GraphSAGE uses fan-outs S1 = 10, S2 = 5, S3 = 5. At most how many nodes does the computation tree of one target contain?

- A. 20
- B. 250
- C. 311
- D. 1,000

**Answer:** C. 311 — $1+10+10\cdot5+10\cdot5\cdot5=1+10+50+250=311$. This counts tree positions; repeated nodes make the number of distinct nodes smaller.

**Question:** Why can GraphSAGE embed a node that was added after training, while DeepWalk cannot?

- A. GraphSAGE stores a larger embedding table
- B. GraphSAGE learns functions of features and neighbourhoods (W^k and the aggregators), not one free vector per node
- C. GraphSAGE uses random walks of fixed length
- D. GraphSAGE retrains the last layer for every new node

**Answer:** B. GraphSAGE learns functions of features and neighbourhoods (W^k and the aggregators), not one free vector per node — DeepWalk's parameters are the node vectors themselves, so a new node has none. GraphSAGE's parameters are shared across nodes, so any node with features and neighbours can be run through the same layers.

**Key points**

- Layer: $h^k_v=\sigma(W^k[h^{k-1}_v\Vert\operatorname{AGG}(\{h^{k-1}_u\}_{u\in\mathcal S(v)})])$, then L2-normalise.
- Aggregators: mean, GCN (no concatenation), LSTM on a random permutation, max-pool after a one-layer MLP.
- Uniform neighbour sampling, $K=2$, $S_1=25$, $S_2=10$: at most 276 nodes per target, whatever the degree.
- Inductive: the parameters are shared functions, so unseen nodes and graphs (the PPI test graphs) are embedded without retraining.
- Supervised micro-F1: 0.954 on Reddit and 0.612 on PPI with the LSTM aggregator.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
