Graph Convolutions & GraphSAGEOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Graph Convolutions & GraphSAGE

The previous lesson framed every GNN as message passing. This lesson makes it concrete: the Graph Convolutional Network (GCN) packs message passing into a clean matrix operation, and GraphSAGE fixes the two things that stop a plain GCN from working at scale or on new data. Together they're the workhorses of practical graph learning.

Real-world examples: node classification on citation networks, product recommendation on huge user–item graphs (GraphSAGE was created at Pinterest for exactly this), and molecular property prediction.

From message passing to a matrix multiply

Recall the simple mean-aggregation update. If we aggregate over neighbors including a self-loop, one layer for all nodes at once is just:

H(k)=σ(D~−1A~ H(k−1) W(k))\mathbf{H}^{(k)} = \sigma\big(\tilde{\mathbf{D}}^{-1}\tilde{\mathbf{A}}\,\mathbf{H}^{(k-1)}\,\mathbf{W}^{(k)}\big)
  • A~=A+I\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I} — adjacency with self-loops, so a node keeps its own features; D~\tilde{\mathbf{D}} is its degree matrix.
  • D~−1A~\tilde{\mathbf{D}}^{-1}\tilde{\mathbf{A}} — row-normalize so each node averages (rather than sums) its neighborhood, keeping magnitudes stable.
  • W(k)\mathbf{W}^{(k)} — a shared, learnable weight matrix (same for every node — this is the "convolution": one filter slides over all neighborhoods).
  • σ\sigma — a nonlinearity (ReLU).

The viz shows one round of this aggregation spreading feature values across the graph.

Message passing on a graph

0.050.950.500.200.800.35
round0
spread0.900
selectednode 4

Each node's colour is its feature value. One step replaces every node's value with the mean of itself and its neighbours — a single GCN-style round. Click a node to highlight its incoming messages; keep stepping and watch all nodes converge to the same colour (over-smoothing).

The GCN normalization

The original GCN (Kipf & Welling) uses symmetric normalization instead of plain row-averaging:

H(k)=σ(A^ H(k−1) W(k)),A^=D~−1/2 A~ D~−1/2\mathbf{H}^{(k)} = \sigma\big(\hat{\mathbf{A}}\,\mathbf{H}^{(k-1)}\,\mathbf{W}^{(k)}\big), \qquad \hat{\mathbf{A}} = \tilde{\mathbf{D}}^{-1/2}\,\tilde{\mathbf{A}}\,\tilde{\mathbf{D}}^{-1/2}

where A~=A+I\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I} and D~\tilde{\mathbf{D}} is its degree matrix.

Why the √ on both sides?

Symmetric normalization D~−1/2A~D~−1/2\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2} down-weights messages from high-degree neighbors (a hub shouldn't dominate everyone it touches), scaling each edge by 1/dudv1/\sqrt{d_u d_v}. It keeps the operator's eigenvalues bounded, which stabilizes training — better than the asymmetric row-average D−1A\mathbf{D}^{-1}\mathbf{A} for most node-classification tasks.

Worked example: one GCN aggregation by hand

Take the 3-node path graph 1 ⁣− ⁣2 ⁣− ⁣31\!-\!2\!-\!3 with scalar features h=[1, 0, −1]\mathbf{h} = [1,\ 0,\ -1] (and W=1\mathbf{W} = 1, no nonlinearity, to isolate the aggregation):

A=(010101010),A~=A+I=(110111011),d~=(2, 3, 2).\mathbf{A} = \begin{pmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{pmatrix}, \qquad \tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I} = \begin{pmatrix} 1&1&0\\ 1&1&1\\ 0&1&1 \end{pmatrix}, \qquad \tilde{d} = (2,\ 3,\ 2).

Each nonzero entry of A^\hat{\mathbf{A}} is 1/d~ud~v1/\sqrt{\tilde{d}_u \tilde{d}_v}: the self-loops give A^11=A^33=12\hat{A}_{11} = \hat{A}_{33} = \tfrac{1}{2} and A^22=13\hat{A}_{22} = \tfrac{1}{3}, and each edge to the middle node gives A^12=A^23=12⋅3=16≈0.408\hat{A}_{12} = \hat{A}_{23} = \tfrac{1}{\sqrt{2\cdot 3}} = \tfrac{1}{\sqrt 6} \approx 0.408. One aggregation step:

(A^h)1=0.5(1)+0.408(0)=0.5,(A^h)2=0.408(1)+0.333(0)+0.408(−1)=0,(A^h)3=−0.5.(\hat{\mathbf{A}}\mathbf{h})_1 = 0.5(1) + 0.408(0) = 0.5,\quad (\hat{\mathbf{A}}\mathbf{h})_2 = 0.408(1) + 0.333(0) + 0.408(-1) = 0,\quad (\hat{\mathbf{A}}\mathbf{h})_3 = -0.5.

Node 2 sits between opposite-signed neighbors and averages to exactly 00; the end nodes are pulled halfway toward their neighborhood. Note the edge weight 0.408<0.50.408 < 0.5 — messages through the higher-degree middle node are down-weighted, exactly the hub-damping the callout describes. The notebook reproduces this matrix and one further layer.

Spectral vs. spatial: same destination

GCNs were originally derived from spectral graph theory: a convolution defined via the graph Laplacian's eigenbasis, then approximated (first-order Chebyshev) down to the simple A^HW\hat{\mathbf{A}}\mathbf{H}\mathbf{W} form above. The modern, practical view is spatial: it's just normalized neighborhood aggregation. You don't need the spectral derivation to use it, but it's why GCNs are called "convolutions."

GraphSAGE: sample and aggregate

A plain GCN has two practical problems: (1) the full A^H\hat{\mathbf{A}}\mathbf{H} multiply needs the entire graph in memory, and (2) it's transductive. It can only score nodes present at training time. GraphSAGE fixes both:

  • Sample a fixed number of neighbors per node (e.g. 25 at hop 1, 10 at hop 2) instead of using all of them — bounding compute and memory regardless of degree.
  • Aggregate the sampled neighbors with a chosen function, then concatenate with the node's own state and transform:
hv(k)=σ(W(k)⋅[ hv(k−1) ∥ AGG({hu(k−1):u∈S(v)}) ])\mathbf{h}_v^{(k)} = \sigma\Big(\mathbf{W}^{(k)} \cdot \big[\,\mathbf{h}_v^{(k-1)} \,\Vert\, \text{AGG}\big(\{\mathbf{h}_u^{(k-1)}: u \in \mathcal{S}(v)\}\big)\,\big]\Big)

Aggregators can be mean, pool (element-wise max of transformed neighbors), or even an LSTM. Because the learned aggregator and weights depend only on features, not node identity, GraphSAGE is inductive: apply it to brand-new nodes or entirely new graphs without retraining.

Transductive vs. inductive

Transductive (vanilla GCN): learns embeddings tied to the specific nodes seen in training; a new node means re-running on the whole graph. Inductive (GraphSAGE): learns how to aggregate, so it generalizes to unseen nodes and graphs — essential for production systems where the graph grows constantly.

Choosing an aggregator

AggregatorBehaviorNote
Meanaverage neighbor featuressimple, smooths; the GCN default
Pool (max)element-wise max of transformed neighborscaptures "is any neighbor X?"
Sumtotal neighbor featuresmost expressive (distinguishes degree); basis of GIN
LSTMorder-sensitive over a random permutationhigh capacity, not permutation-invariant by design

Sum is the most discriminative (the Graph Isomorphism Network result), mean and max lose some structural information but are often more stable.

Exercise

A GCN layer computes H' = σ(Â H W). What is the weight matrix W, and how does it relate to a CNN?

Need a hint?

How many distinct weight matrices does the layer use across all nodes?

Exercise

Why does the GCN use symmetric normalization  = D̃^(-1/2)(A+I)D̃^(-1/2) rather than the raw adjacency A?

Need a hint?

Think about what happens to a node connected to a very high-degree hub.

Exercise

Your user–item graph grows constantly with new users. Why is GraphSAGE a better fit than a vanilla (transductive) GCN?

Need a hint?

What does each method actually learn — embeddings, or a function?

Common mistakes

  1. Forgetting self-loops. Without A+I\mathbf{A}+\mathbf{I}, a node's update ignores its own features.
  2. Skipping normalization. Raw AH\mathbf{A}\mathbf{H} lets high-degree hubs blow up activation magnitudes; normalize by degree.
  3. Expecting a transductive GCN to score new nodes. Use GraphSAGE (or another inductive method) when the graph changes.
  4. Using all neighbors on a huge graph. Sample (GraphSAGE) to bound the per-node cost rather than aggregating millions of neighbors of a hub.

Key takeaways

  • A GCN layer is message passing as one matrix op: H(k)=σ(A^H(k−1)W(k))\mathbf{H}^{(k)} = \sigma(\hat{\mathbf{A}}\mathbf{H}^{(k-1)}\mathbf{W}^{(k)}) with a shared learnable W\mathbf{W} — the "filter."
  • Symmetric normalization A^=D~−1/2A~D~−1/2\hat{\mathbf{A}}=\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2} down-weights high-degree neighbors and stabilizes training.
  • GraphSAGE samples a fixed set of neighbors and learns an aggregator, making it scalable and inductive (works on unseen nodes/graphs).
  • The aggregator choice (mean / max-pool / sum / LSTM) trades expressiveness against stability; sum is the most discriminative.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
Graph Convolutions & GraphSAGENeural NetworksFraud Detection at ScaleGraphs as Data & Message …Graph Attention, Pooling …The Convolution OperationGraph-Based Fraud Detecti…