Graph neural networks

The CS224W territory. Reach for a GNN when the edges carry information a feature vector cannot — a fraud ring, a molecule, a citation network, a social graph. If the relationships are incidental, a gradient-boosted tree on flat features will beat it and take an afternoon.

Message passing is the whole idea

Every GNN layer does the same three things: each node collects messages from its neighbours, aggregates them, and updates itself.

h_v^(k) = UPDATE( h_v^(k-1),  AGGREGATE({ h_u^(k-1) : u ∈ N(v) }) )

def layer(H, A, W):
    # A: adjacency (normalised). One matmul = one hop of messages.
    return relu(A @ H @ W)

k layers means information travels k hops. That is the mental model for depth here, and it is different from a CNN: two layers is often plenty, because three hops on a social graph can already reach most of it.

The variants differ only in how they aggregate:

GraphSAGE is the one that made GNNs practical at scale: sampling a fixed number of neighbours makes the cost per node constant, and it generalises to nodes never seen in training.

The three task levels

Graph-level needs a readout — pooling all node embeddings into one vector — and the pooling must be permutation-invariant, because a graph has no canonical node order.

Oversmoothing is the failure that defines the field

Stack many message-passing layers and every node’s representation converges to the same value. After enough rounds of averaging with your neighbours, everyone holds the graph’s average.

That is why GNNs are shallow — typically 2 to 4 layers — where CNNs are deep. It is a real structural limit, not a tuning problem, and the mitigations are residual connections, jumping-knowledge (concatenate every layer’s output), and simply not going deep.

Gotcha: the standard benchmarks are small and homophilous — connected nodes share labels. On a heterophilous graph, where neighbours tend to differ, plain GCN can lose to a model that ignores the graph entirely. Checking homophily before reaching for a GNN is the practical move.

Getting it into production

The training-versus-serving gap is bigger here than anywhere else in ML, and it is where an interview goes if the interviewer has shipped one.

• Neighbour explosion. Two hops on a graph with high-degree nodes touches a huge fraction of it. Sampling (GraphSAGE) or subgraph batching (Cluster-GCN) is not an optimisation, it is what makes training finish.
• The graph must exist at inference. Scoring one account means fetching its neighbourhood in milliseconds — so the serving story is a graph store or a precomputed neighbour table, not just a model artefact.
• Precompute where you can. For node classification on a slow-changing graph, run inference in batch and serve embeddings from a key-value store. That turns a graph fetch into a lookup and is what most production systems actually do.
• Dynamic graphs drift. A model trained on last quarter’s graph structure decays as the structure changes, independently of feature drift — see Monitoring and drift.

The cheaper thing to try first

Often the win is not a GNN at all: compute graph features — degree, PageRank, clustering coefficient, triangle count, community id — and feed them to gradient boosting. It captures much of the signal, trains in minutes, and is explainable to a fraud analyst.

Reach for a GNN when that plateaus and the structure is genuinely the signal. Same reasoning as When not to use ML.

Related

• Knowledge Graphs and GraphRAG — graphs in a RAG pipeline
• Recommender systems — link prediction as recommendation
• Design: a fraud detection system — where fraud rings show up
• NoSQL Decision Guide — Which Store, and When — when a graph database earns its place