Graph Neural Networks schematic: message passing, aggregate and update, receptive field growth, task heads
Algorithm 37 of 40 · Phase 8

Graph Neural Networks

Learning on data whose shape is a relationship, not a grid

🎯 Core Concept

A CNN assumes your data sits on a grid. An RNN assumes it sits on a line. A GNN drops both assumptions: it learns on arbitrary graphs, where each node has features and the edges say who is related to whom. It does this by repeatedly letting every node listen to its neighbours and rewrite its own representation from what it hears.

Mental model — the rumour network. Every round, each person updates their own opinion by pooling whatever their direct contacts currently believe, then passing it through their own bias (a learned weight matrix). After one round you know your neighbours. After two rounds you indirectly know your neighbours' neighbours. Stack k rounds and each node has absorbed its k-hop neighbourhood — without anyone ever seeing the whole graph.
hₕᵀ = σ( W · AGG({ hₖᵀ⁻¹ : u ∈ N(v) }) )

That single line is the whole family. Change AGG and you change the algorithm: mean gives GCN, learned weights give GAT, sampled neighbours give GraphSAGE.

🔑 Key Components

📩 1. Message Passing

Each edge carries a message from source to target. Nothing is global — all computation is local, which is exactly why a GNN generalises to graphs of any size or shape.

∑ 2. Aggregation

Neighbour messages are pooled by a permutation-invariant function (sum, mean, max, attention). Invariance is non-negotiable: a node's neighbours have no natural order.

⚙️ 3. Update

The pooled message plus the node's own previous state pass through a learned transform and a nonlinearity. Weights are shared across all nodes — the graph analogue of a convolution kernel.

📊 4. Readout / Pooling

For a whole-graph prediction, collapse all node embeddings into one vector (sum/mean/max or hierarchical pooling). Skip readout for node- or edge-level tasks.

⚙️ How It Works

  1. Initialise. Every node starts with its raw feature vector; edges may carry features too.
  2. Pass messages. For each node, gather the current embeddings of its direct neighbours.
  3. Aggregate. Pool those messages with an order-independent operator.
  4. Update. Combine pooled message with the node's own state, apply W and σ. One layer done — receptive field is now 1 hop.
  5. Stack. Repeat 2–4 for k layers. Receptive field grows to k hops. Typically k = 2–3.
  6. Predict. Node head (classify each node), edge head (score node pairs for link prediction), or readout then graph head.
Over-smoothing — the signature failure. Too many layers and every node has averaged in most of the graph, so all embeddings converge toward the same vector and the model loses the ability to tell nodes apart. This is why GNNs are shallow where CNNs are deep. Countermeasures: residual/skip connections, jumping knowledge, normalisation, or simply fewer layers.

🌎 Real-World Applications

RecommendationUser–item interaction graphs (Pinterest PinSage, UberEats) — link prediction at scale.
Drug discoveryMolecules are graphs: atoms as nodes, bonds as edges. Predict toxicity, binding, solubility.
Fraud & AMLTransaction networks — fraud rings are structurally visible even when each account looks normal alone.
Traffic & logisticsRoad networks (Google Maps ETA), power grids, supply chains — forecasting on a fixed topology.

🧪 Checkpoint Questions

1. Why must the aggregation function be permutation-invariant, and what breaks if you naively concatenate neighbour features instead?

Hint: a node's neighbours arrive in no particular order, and different nodes have different degrees. What would concatenation imply about both?

2. A colleague reports that their 8-layer GNN performs worse than their 2-layer one on node classification. What is the likely mechanism, and what does it tell you about depth on graphs versus depth on images?

Hint: think about what repeated neighbourhood averaging does to the variance between node embeddings as the receptive field approaches the whole graph.

3. When would you choose a GNN over simply flattening the graph into a feature table (node degree, neighbour-count stats) and running gradient boosting?

Hint: hand-engineered features fix the relational patterns you can express in advance. What does a GNN get to learn instead — and when is that worth the extra cost?
38Day streak
37/40Curriculum
70%Phase 8