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:
- — adjacency with self-loops, so a node keeps its own features; is its degree matrix.
- — row-normalize so each node averages (rather than sums) its neighborhood, keeping magnitudes stable.
- — a shared, learnable weight matrix (same for every node — this is the "convolution": one filter slides over all neighborhoods).
- — a nonlinearity (ReLU).
The viz shows one round of this aggregation spreading feature values across the graph.
Message passing on a graph
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:
where and is its degree matrix.
Why the √ on both sides?
Symmetric normalization down-weights messages from high-degree neighbors (a hub shouldn't dominate everyone it touches), scaling each edge by . It keeps the operator's eigenvalues bounded, which stabilizes training — better than the asymmetric row-average for most node-classification tasks.
Worked example: one GCN aggregation by hand
Take the 3-node path graph with scalar features (and , no nonlinearity, to isolate the aggregation):
Each nonzero entry of is : the self-loops give and , and each edge to the middle node gives . One aggregation step:
Node 2 sits between opposite-signed neighbors and averages to exactly ; the end nodes are pulled halfway toward their neighborhood. Note the edge weight — 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 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 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:
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
| Aggregator | Behavior | Note |
|---|---|---|
| Mean | average neighbor features | simple, smooths; the GCN default |
| Pool (max) | element-wise max of transformed neighbors | captures "is any neighbor X?" |
| Sum | total neighbor features | most expressive (distinguishes degree); basis of GIN |
| LSTM | order-sensitive over a random permutation | high 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
- Forgetting self-loops. Without , a node's update ignores its own features.
- Skipping normalization. Raw lets high-degree hubs blow up activation magnitudes; normalize by degree.
- Expecting a transductive GCN to score new nodes. Use GraphSAGE (or another inductive method) when the graph changes.
- 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: with a shared learnable — the "filter."
- Symmetric normalization 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
- Graphs as Data & Message Passing: the framework this lesson instantiates
- Graph Attention, Pooling & Over-smoothing: learning which neighbors matter, and graph-level readout
- Convolution Operation: the grid convolution a graph convolution generalizes