Graph ML

01Message passing

Look at the diagram first: three boxes, and everything else on this page changes the middle one and leaves the other two alone.

A graph is a set of nodes and a set of edges. Each node $i$ carries a feature vector $h_i$. That is the entire input.

A message passing layer updates every node at once, in three steps:

• Gather. Each node reads the current vectors of the nodes it is connected to.
• Aggregate. Those vectors collapse into a single message. This step must not care about ordering.
• Update. The message is combined with the node's own vector and pushed through a learned transform.

Run the layer once and every node knows its immediate neighbours. Run it twice and information has travelled two hops. With $k$ layers, a node's output depends on everything within distance $k$. That is a receptive field, grown the same way a CNN grows one on page 05.

Gilmer et al. named this framework MPNN in 2017 and showed that most published graph networks are instances of it. Learn the loop once, and a new architecture becomes one paragraph and no longer a whole paper.

02The graph as matrices

The loop above is a for-loop over edges. Written with matrices it becomes a single line, and that line is what you implement.

Three objects describe everything. The adjacency matrix $A$ is $N \times N$ with a 1 wherever an edge exists. The degree matrix $D$ is diagonal and holds each node's neighbour count. The feature matrix $X$ is $N \times F$, one row per node.

From those you get the graph Laplacian $L = D - A$. It is the discrete analogue of a second derivative on the graph, and its eigenvectors are the graph's Fourier basis. They reappear in section 11 as positional encodings.

Two adjustments turn $A$ into something you can propagate with. Add self-loops, $\hat{A} = A + I$, or a node discards its own state every layer. Then normalise by degree:

One matrix product does the gather and the aggregate for every node simultaneously. $W^{(k)}$ is the update, and it is the only learned tensor in the layer.

Normalisation does real work. Without it, a hub with 100,000 neighbours emits a message 100,000 times larger than a leaf node's, and the activations blow up in one layer. Symmetric normalisation gives each edge the weight $1/\sqrt{d_i d_j}$, so a message from a popular node counts for less.

In practice nobody stores $A$ densely, because $N^2$ floats is hopeless past about a hundred thousand nodes. Real graphs are sparse, with $E$ only a few times $N$, so implementations keep an edge list and use scatter-add. Cost is $O(E F)$ per layer, not $O(N^2 F)$.

03GCN: the aggregator with nothing learned in it

The simplest choice for the middle box. Each neighbour's weight is fixed by degree before training starts.

Kipf and Welling derived the graph convolutional network in 2016 as a first-order approximation to a spectral filter. The derivation matters less than the result. The result is the propagation matrix above, applied once per layer, with one shared weight matrix.

Stated plainly: average your neighbours and yourself, weight each by degree, then apply a linear layer and a nonlinearity. It is worth watching that happen on real numbers rather than trusting the equation.

import numpy as np

# 6 nodes: two triangles joined by the single edge 2-3.
E = [(0,1),(0,2),(1,2),(2,3),(3,4),(3,5),(4,5)]
A = np.zeros((6, 6))
for i, j in E: A[i, j] = A[j, i] = 1

A_hat = A + np.eye(6)         # self-loop, or a node forgets itself
deg = A_hat.sum(1)
Dm = np.diag(deg ** -0.5)
S = Dm @ A_hat @ Dm           # the aggregator: fixed, nothing learned

rng = np.random.default_rng(0)
X = rng.normal(size=(6, 4))   # 4 input features per node
W = rng.normal(size=(4, 2))   # the only learned tensor in the layer
H = np.maximum(S @ X @ W, 0)  # gather + aggregate, then update

print("A", A.shape, "X", X.shape, "W", W.shape, "-> H", H.shape)
print("degrees, self-loop included:", deg)
print("node 2 mixes with weights:  ", np.round(S[2], 3))
print("same mix, done by hand:", round(float(S[2] @ X[:, 0]), 4))
print("what the layer computed:", round(float((S @ X)[2, 0]), 4))
print("two layers stacked:         ", np.round((S @ S)[2], 3))

Two properties are visible in that output and both matter later. A layer reaches exactly one hop. And the mixing weights depend only on how many edges a neighbour has, never on what the neighbour contains.

04GraphSAGE: sampling, and the inductive jump

Two changes to GCN: one makes it fit in memory, and the other lets it handle nodes it has never seen.

The first change is neighbour sampling. Instead of aggregating over every neighbour, draw a fixed number at random, say 25 in the first layer and 10 in the second. Work per node is now bounded, whatever the degree of the hub it happens to sit next to.

The second change is smaller and easy to skip past. GraphSAGE concatenates a node's own vector with the aggregated message rather than folding it in through a self-loop. The node's own state gets its own weights, so it cannot be averaged away by a crowd of neighbours.

The aggregator itself is a choice: mean, an elementwise max over a small MLP, or in the original paper an LSTM applied to a random permutation of the neighbours.

05GAT: let the weights be learned

GCN decides a neighbour's importance from degree alone. Attention makes it a function of what the neighbour says.

A graph attention network computes a coefficient per edge. Project both endpoints, concatenate, score with a shared vector, pass through a LeakyReLU, then softmax over the neighbourhood:

The denominator runs over neighbours only. The graph is the attention mask.

If that reads like the self-attention on page 08, it is. A transformer is a GNN over a complete graph, with position supplied by an encoding rather than by edges. GAT is the same operation with the mask set to the adjacency matrix. Hold on to that: section 11 becomes unsurprising.

import numpy as np
rng = np.random.default_rng(0)

E = [(0,1),(0,2),(1,2),(2,3),(3,4),(3,5),(4,5)]  # same two triangles
A = np.zeros((6, 6))
for i, j in E: A[i, j] = A[j, i] = 1
M = A + np.eye(6)                    # who is allowed to send a message
deg = M.sum(1)
gcn = M / np.sqrt(np.outer(deg, deg))   # GCN: degree decides, full stop

X = rng.normal(size=(6, 4))
W = rng.normal(size=(4, 3)) * 0.5
a_i, a_j = rng.normal(size=3), rng.normal(size=3)
Z = X @ W                            # (6, 3) projected node features
e = (Z @ a_i)[:, None] + (Z @ a_j)[None, :]
e = np.where(e > 0, e, 0.2 * e)      # LeakyReLU, as in the GAT paper
e = np.where(M > 0, e, -np.inf)      # non-neighbours cannot compete
att = np.exp(e - e.max(1, keepdims=True))
att /= att.sum(1, keepdims=True)     # softmax over each node's neighbours

print("Z", Z.shape, "e", e.shape, "att", att.shape)
print("node 2, GCN weights:", np.round(gcn[2], 3))
print("node 2, GAT weights:", np.round(att[2], 3))
print("row sums:  GCN", round(float(gcn[2].sum()), 3),
      " GAT", round(float(att[2].sum()), 3))

Attention has a cost: you store a coefficient per edge per head, so memory is $O(E H)$. It pays off when neighbours differ in relevance, which is typical of heterogeneous graphs. On a regular graph where every neighbour is alike, GAT and GCN land in much the same place.

06Nodes, edges, graphs: three levels of prediction

Message passing gives you one vector per node. What you attach to those vectors is what decides the task.

• Node level. A classifier on each row of $H$. Is this account fraudulent, what topic is this paper.
• Edge level. A decoder over a pair, either a dot product $h_u \cdot h_v$ or an MLP on the concatenation. Link prediction and recommendation live here.
• Graph level. Pool every node vector into one, then predict. Is this molecule soluble, is this program malicious.

The pooling step is called readout, and the choice between sum and mean matters. Sum preserves size, so it can count. Mean is size-invariant, which generalises better when test graphs are much larger than training ones. Xu et al. showed sum followed by an MLP is the most expressive of the simple options.

Link prediction carries a quiet difficulty. There are $N^2$ possible edges and only $E$ real ones, so most of the training signal is a choice about which non-edges to sample. Uniform corruption of one endpoint is standard. Sampling hard negatives, such as nodes two hops away, makes the task harder and the reported numbers far more honest.

07Your samples are not independent

Every other page here assumes rows can be shuffled and split. On a graph they cannot be, and that changes what a validation set means.

There are two regimes, and interviewers ask you to name them.

Transductive: the entire graph is present during training, edges and features included. Only some labels are hidden. You split the labels and leave the graph intact. Most citation-network benchmarks work this way, which is worth remembering when a published number looks high.

Inductive: the test nodes or graphs were absent during training. Separate molecules in separate splits, or one evolving graph cut at a date. This is what production looks like, because tomorrow's users were not in last night's snapshot.

Time makes it sharper: graphs grow, and a random split trains on next week to predict last week, so split by timestamp instead, with the same discipline page 17 applies to series data.

08Neighbour explosion, and why a minibatch is a subgraph

Full-batch training holds the whole graph and every layer's activations in memory. Past a few million nodes that stops working.

The arithmetic is unforgiving: with average degree $d$ and $k$ layers, one target node needs its $k$-hop neighbourhood: roughly $d^k$ nodes. At $d = 30$ and $k = 3$ that is 27,000 nodes to produce one prediction.

So you cannot take a random sample of rows. A minibatch on a graph is a subgraph, and three families of method build one:

• Node-wise sampling (GraphSAGE). Fix a fan-out per layer, such as 25 then 10. Simple and still the default. Growth is exponential in depth, just with a small base.
• Layer-wise sampling (FastGCN). Sample a fixed number of nodes per layer, importance-weighted, so total cost is linear in depth. Needs care or the sampled layers share too few edges.
• Subgraph sampling (Cluster-GCN, GraphSAINT). Partition the graph, then run full-batch on one partition. Cheap and cache-friendly. Every edge crossing a partition boundary is dropped for that step.

Sampling has a cost you feel later. Training sees a random neighbourhood each epoch and evaluation usually uses the full one, so the two are not measuring the same model. Fix the seed, and report which regime a number came from.

Serving is the other half of the problem. A prediction needs the node's $k$-hop neighbourhood, which is a database query, not a tensor. Many production systems precompute embeddings in a nightly batch job and serve them as ordinary features, trading freshness for a latency budget they can meet.

09Over-smoothing and over-squashing

Depth helps every other architecture on this site. Here it is a budget you spend, and most GNNs in production are two or three layers deep.

Over-smoothing is the first reason: averaging over neighbours is a low-pass filter, and each layer pulls connected nodes closer together. Iterate enough and every node in a connected component converges to the same representation. There is then nothing left for a classifier to separate.

You do not have to take that on trust. It is four lines of numpy.

import numpy as np

E = [(0,1),(0,2),(1,2),(2,3),(3,4),(3,5),(4,5)]  # same two triangles
A = np.zeros((6, 6))
for i, j in E: A[i, j] = A[j, i] = 1
A_hat = A + np.eye(6)
Dm = np.diag(A_hat.sum(1) ** -0.5)
S = Dm @ A_hat @ Dm

def spread(M):                 # mean distance between unit-norm rows
    U = M / np.linalg.norm(M, axis=1, keepdims=True)
    D = np.linalg.norm(U[:, None] - U[None, :], axis=-1)
    return D[np.triu_indices(6, 1)].mean()

rng = np.random.default_rng(0)
H = rng.normal(size=(6, 8))    # nodes start with unrelated features

print("layers  mean pairwise distance")
for k in range(65):
    if k in (0, 1, 2, 4, 8, 16, 32, 64):
        print(f"{k:6d}  {spread(H):.5f}")
    H = S @ H                  # one more round of message passing
lam = np.sort(np.abs(np.linalg.eigvalsh(S)))[::-1]
print("shrink factor per layer =", round(float(lam[1]), 3))

A real GNN puts a weight matrix and a ReLU between propagation steps, which slows the collapse. It does not prevent it. The standard defences all work by keeping earlier, sharper representations reachable:

• Residual connections, exactly as on page 04, so each layer adds to rather than replaces the node state.
• Jumping knowledge: concatenate every layer's output at the end, letting the model pick its own effective depth per node.
• Decoupling propagation from transformation. SGC strips the nonlinearities and applies $S^k X$ once. APPNP propagates with a restart term, which keeps a fixed share of a node's own features in play forever.

Over-squashing is the second reason, and it is the opposite complaint. Information from distant nodes must funnel through a few bottleneck edges. The number of nodes at distance $k$ grows exponentially while the vector carrying them stays a fixed width.

Squashing is fixed by changing the graph or bypassing it. Rewiring adds edges to shorten paths. A virtual node connected to everything gives every pair a two-hop route. Global attention removes the question entirely, which is section 11.

10Knowledge graphs and embeddings

A knowledge graph has typed edges, and the type is the point. The models look different because the task is different: score a fact.

The unit is a triple of head entity, relation and tail entity, such as (Paris, capital_of, France). A knowledge graph holds millions of them and is always incomplete, so the central task is link prediction. Given a head and a relation, rank every entity as the tail.

Each method is a scoring function, and each one's weakness is a fact it cannot represent:

• TransE. A relation is a translation: $h + r \approx t$. Elegant and weak. It cannot express a symmetric relation without forcing $r = 0$, and one-to-many relations collapse.
• DistMult. A bilinear score with a diagonal matrix. Cheap, but symmetric by construction, so it scores "A is the parent of B" and the reverse identically.
• ComplEx. Move the embeddings into complex space and use the conjugate on the tail. Asymmetry becomes representable at almost no extra cost.
• RotatE. A relation is a rotation in the complex plane. Symmetry, inversion and composition all fall out of one form, which is why it is the usual modern baseline.

Training corrupts one endpoint of a true triple to make negatives. Evaluation ranks the true tail against all candidates and reports MRR and Hits@k. Use the filtered version, which removes other known-true triples from the ranking. Otherwise you penalise the model for correct answers.

Message passing is still available here. R-GCN gives each relation type its own weight matrix, then shares parameters through a basis decomposition because the count explodes. The rough rule: use a GNN when node features carry information, use embeddings when the structure is all you have.

11Beyond message passing

Message passing has a ceiling, and unusually for deep learning it is a precise one.

A message-passing GNN cannot distinguish two graphs that the 1-dimensional Weisfeiler-Leman colour refinement test cannot distinguish. The reason is structural: both produce the same multiset of neighbour labels at every round, so both produce identical outputs forever.

Xu et al. proved that bound and showed GIN attains it by using sum aggregation followed by an MLP. The practical consequence is that a standard GNN cannot count triangles or tell a 6-cycle from two triangles. If your task needs that, compute it as a feature and feed it in.

Graph transformers take the other route. Let every node attend to every other node, and inject structure through positional encodings, usually Laplacian eigenvectors or random-walk landing probabilities.

Over-squashing disappears, because everything is one hop away. Cost returns to $O(N^2)$, which is fine for a molecule with 40 atoms and hopeless for a social network. GraphGPS is the common compromise: one local message-passing layer and one global attention layer per block.

Two more pieces complete the checklist.

Graph contrastive learning attacks the label scarcity. Build two views of a graph by dropping edges, masking features or sampling subgraphs, then pull the same node's two views together and push other nodes apart, using page 03's machinery. It works, but there is no ImageNet here. A model pretrained on molecules tells you nothing about a payment network.

Temporal graphs carry a timestamp on every edge. The usual design keeps a memory vector per node and updates it as events arrive, so a representation reflects the node's history rather than a static snapshot. Fraud and recommendation both need this, because the order of events is most of the signal.

12Build this

The claim worth testing yourself is that structure alone carries signal, and that depth destroys it. Both are visible in an afternoon on a laptop.

13What breaks

Graph failures are rarely the architecture. They are usually a split that leaked or an assumption about the graph that was never checked.

• Link prediction scores 0.99 AUC. The edges being predicted were still present in the adjacency matrix used for message passing. The model was reading the answer.
• A gradient-boosted tree on node features beats the GNN. This happens often and it is informative. It means the edges are not carrying signal for your task, and you have paid a large engineering cost for nothing.
• The graph is heterophilous and nobody checked. GCN assumes connected nodes share labels. In fraud, a mule connects to victims rather than to other mules, so averaging over neighbours erases exactly the contrast you need.
• Adding layers made it worse. The likely cause is over-smoothing, so measure representation spread before blaming the learning rate.
• Results will not reproduce. Neighbour sampling is random, training saw one sample and evaluation used full neighbourhoods, and nobody fixed the seed or wrote down which was which.
• One hub node blows up the batch. A celebrity account with a million edges makes a sampled subgraph enormous, and the out-of-memory error arrives hours into training.
• It trains but cannot be served. Inference needs a $k$-hop neighbourhood fetched from a database within the latency budget. Page 24 has the rest of that story.
• The model is transductive and the world is not. New nodes arrive every minute and the embedding table has no row for them.

14Where you meet this in the wild

The primitive is the same, but the graphs differ and so do the ways each one goes wrong.

15Interview questions

16Go deeper

●Now write it yourself

Reading the derivation and being able to produce it are different skills. These are Deep-ML problems that exercise what this page covers — each one is checked against real test cases, not multiple choice.

Matched to this page from Deep-ML's catalogue of 1,380 problems. More at deep-ml.com, and Where to practise covers the other platforms and what each one trains.

17Related pages

Other techniques for this problem

A scoped slice of the full Technique Map — every technique this page covers, grouped by what it solves.