Graph neural networks, gently

The 2021 Distill introduction to GNNs, rebuilt five years later on a graph you can watch move — our own agent fleet — with a playground that trains a real graph neural network in your browser, no libraries, in seconds.

Every idea below lands twice: once on the classic examples, and once on the T27F Live work graph, the live record of what our agents are reading, assigned, performing, producing, verifying and blocking right now.

1 · Graphs are everywhere, including here

A graph is a set of entities — nodes — and the connections between them — edges. That definition is so permissive that most data is a graph if you squint, and the useful skill is knowing when the squinting pays off:

Images are grids: each pixel a node, each node wired to its neighbors, every node with the same neighbor count. The adjacency matrix of an image is banded, perfectly regular — which is why convolutions, not GNNs, win on images. Text is a chain: each token connected to the next, adjacency matrix a diagonal stripe; RNNs and Transformers won there. The lesson of both examples is the same: when the structure is fixed and regular, use the tool that assumes the regularity.

Molecules (atoms and bonds), social networks (people and interactions), citation networks (papers and citations) — here the neighbor count varies per node, the adjacency matrix has no pattern to exploit, and a graph stops being a squint and becomes the honest description of the data. This is GNN country.

Our running example: the work graph of a fleet of agents

The running example of the original article was molecules. Ours is a graph we produce every minute of every day: the work graph of our own agent fleet. When our agents work, the actor bus records events; a spec called specs/t27f/work_graph.t27 folds those events into one graph with five node kinds and six edge kinds:

AGENT (an actor, by pid) · TASK (an issue) · SPEC (a .t27 source file) · ACTION (a deliver: offer, result, cancel) · ARTIFACT (a receipt, a diff)
ASSIGNED (an offer assigns a task) · READS (a task reads a spec, through the feed's join) · PERFORMS (an agent performs a deliver) · PRODUCES (a result produces an artifact) · VERIFIES (whoever received a result verifies it) · BLOCKS (a cancel or crash blocks a task)

Every node and edge also carries a provenance label — EXACT when an event states the pair outright, DERIVED when a rule computed it, UNKNOWN when we only saw a bare pid — and the graph refuses to grow past its caps rather than truncate silently. The moving, real version is live here. The figure below is a small fixture that follows the same semantics, so that this page never has to fetch anything:

hover a node -- its k-hop neighborhood lights up, and the panel lists exactly which embeddings a k-layer GNN would gather into it. solid outlines are EXACT provenance, dashed are weaker (DERIVED or UNKNOWN).

2 · Three kinds of questions

Whatever the graph, prediction tasks come in three levels. The classic examples are molecule property prediction (graph), karate-club faction membership (node), and scene-graph link prediction (edge). Ours, on the work graph:

Graph-level: one property for the whole graph.

Ours: will the fleet's current pull request merge green? Every node and edge feeds one answer. Classic: does this molecule smell pungent (the 2021 playground's task, on the Leffingwell odor dataset)?

Node-level: one property per node.

Ours: which spec will this agent touch next? Which task is about to be blocked? Classic: which faction will this karate member join after the feud (the dataset our own playground trains on below)?

Edge-level: one property per pair — presence or type of an edge.

Ours: will this agent VERIFIES this artifact? Given a bare pid and an artifact, should the graph grow a VERIFIES edge (upgrading that agent from UNKNOWN)? Classic: which objects in a scene relate (link prediction).

The 2021 article's promise still holds and is still the point: all three levels are solved by one model class — a GNN — because all three are read off the same learned node, edge and global embeddings.

3 · Representing a graph

A graph carries up to four kinds of information: node attributes, edge attributes, a global (whole-graph) attribute, and connectivity. The first three stack into ordinary tensors — a node matrix of shape [n_nodes, node_dim], an edge matrix [n_edges, edge_dim], one global vector. In the work graph, a node's initial features are its kind and provenance; an edge's, its kind. Connectivity is the hard part.

The obvious encoding is the adjacency matrix: order the nodes, fill an n x n matrix with a 1 wherever two nodes share an edge. Two problems. First, sparsity: most pairs are unconnected, so you store mostly zeros — our fixture below is 17 edges in a 17x17 grid, and the real fleet caps at 8192 edges over up to 2048 nodes, which is 0.2% of a 4.2M-cell matrix. Second, and deeper: the node order is arbitrary, and a network that eats a raw matrix would have to learn that all orderings of the same graph mean the same thing. The fix is not more data; it is an architecture that cannot see the order in the first place. Click cells below to edit the graph, and watch the 2-walk matrix A^2 follow:

The memory-honest encoding is the adjacency list: for the k-th edge, a tuple (i, j). Storage O(n_edges) instead of O(n_nodes^2), and — once the network gathers neighbors by index instead of reading a matrix row — permutation invariance becomes structural rather than learned. The figure below proves it numerically: the same untrained 2-layer GNN, run on the fixture and on a shuffled copy of the fixture, produces the same logits:

4 · A GNN, built in three moves

With nodes, edges, a global vector and an adjacency list in hand, we can define the object: a GNN is an optimizable transformation on all attributes of a graph — nodes, edges, global — that preserves the graph's symmetries. It is graph-in, graph-out: same connectivity every layer, updated embeddings. We build it in three moves, the same three as the 2021 original.

Move 1 — the simplest GNN: an MLP per part

Apply a separate small fully-connected network (MLP) to every node embedding, every edge embedding, and the global vector. Nothing talks to anything yet: a SPEC node cannot see which AGENTs read it. Stacking these layers just refines each part alone. Already this is a GNN — permutation-invariant, since each node is processed independently — just not a very graph-aware one.

Move 2 — pooling: routing information to where the prediction is

To predict something about nodes when the information sits in edges (or vice versa, or into the global vector), pool: gather the relevant embeddings, aggregate them — usually sum — and feed the result to the classifier. Pooling is the plumber of the GNN world: it does not learn, it routes. The hero figure at the top is exactly a gather: hover a node and the panel lists the embeddings that would be pooled into it.

Move 3 — message passing: pooling inside the layer

The big idea: do the gather-and-aggregate inside every layer, not just at the end. Each layer, every node (1) gathers its neighbors' embeddings, (2) aggregates them — sum, mean or max — and (3) updates its own embedding with a learned function of the aggregate. This is message passing; stack k such layers and a node's embedding has absorbed everything within k hops — drag the k slider in the hero figure and watch the reachable set grow. A layer that averages (degree-normalized) neighbors and itself is GCN (Kipf & Welling, 2017); adding per-edge message functions makes an MPNN (Gilmer et al., 2017).

Edges get embeddings too

Our edge-level question — will this agent VERIFIES this artifact? — needs a representation for a pair. The standard move: concatenate the two endpoint embeddings (optionally with the edge's own embedding) and let a small MLP read the pair. Inside the layer, edges can also receive messages from their endpoints before being updated, which is what lets a VERIFIES edge know what it is verifying. (A neat fact for later: edge prediction on a graph is node prediction on its dual — the graph whose nodes are your edges.)

The global representation, a.k.a. the master node

Message passing has a built-in horizon: k layers reach k hops, and two agents on opposite sides of the work graph may never exchange information. The fix is a global vector (sometimes drawn as a master node) connected to everything, acting as a shared bottleneck: any node can read the state of the whole graph. Full GraphNets (Battaglia et al., 2018) pass messages between nodes, edges and the global in all directions. For molecules the "connect everything" trick is affordable; for a 2048-node fleet graph it is 4M edges of overhead — hold that thought for section 6, where attention renames it.

5 · The playground

The 2021 playground trained its GNN on molecules in TensorFlow.js. Ours trains on Zachary's karate club (Zachary, 1977) — 34 members, 78 friendship edges, and a club that split in two after a feud between the instructor, Mr. Hi, and the administrator, John A. The task: from the graph alone (no features but node degree), predict each member's faction. It is the classic first GNN dataset: tiny, visual, and learnable in seconds.

The engine is ~150 lines of vanilla JavaScript on this page — hand-rolled matrix ops, manual backprop, Adam, no libraries, no network. Train it, then change one dial at a time:

The 2021 design lessons, reproduced in your browser

The original article ended its playground with empirical lessons: two layers beat three or four, sum aggregation edges out mean and max, more attributes talking beats fewer. Five years later we can do something the original could not: re-run that sweep inside the article itself. The button below trains 24 tiny models (all combinations of 1–4 layers, sum/mean/max, message passing on/off) in a few seconds:

starting sweep...

What the sweep shows here (deterministic — the same seeds run every time): message passing is the whole game, 0.91 mean accuracy on versus 0.59 off; depth plateaus at two-to-three layers and sags at four (0.70 / 0.79 / 0.79 / 0.72) — the 2021 depth lesson, reproduced. The aggregation ranking does not reproduce: mean and max edge out sum (0.77 / 0.77 vs 0.71). The reason is visible in this engine: karate's degrees run to 17, and an unnormalized sum saturates the tanh, while with message passing on and two layers every aggregator reaches 100%. The original warned exactly this — "the answers are going to depend on the data" — and five years later that caveat, not the ranking, is the lasting lesson. Aggregation choice is an expressivity trade-off (sum is injective over multisets; mean and max are not — see section 7), not a leaderboard.

6 · What five years taught (the section the original could not have)

The original article ended in 2021, at the peak of pure message passing. Five more years happened. What aged well, what aged badly:

Attention ate the wheel — up to a size

GAT (Velickovic et al., 2017) had already replaced fixed sum-weights with learned attention over neighbors, and the original's "into the weeds" section noted that a Transformer is a GNN on a fully connected graph. That aside became the main story: Graphormer (Ying et al., 2021) and the GPS hybrid recipe (Rampasek et al., 2022) showed that global attention, with the right positional encodings, beats pure message passing on many small- and medium-graph benchmarks. The catch is the one baked into section 4's master-node discussion: attention is the "connect everything" graph, and its cost is O(n^2). On molecules and their tens of atoms, fine. On a citation graph with a million nodes, or a fleet graph at scale, nobody connects everything.

The depth debate settled — the original's "2 layers" held

It is now standard knowledge that stacking many message-passing layers hurts: representations over-smooth toward each other with depth, and information from expanded neighborhoods over-squashes through fixed-width bottlenecks (Alon & Yahav, 2021). The empirical plateau — two to three layers for most tasks, exactly what the 2021 playground measured and ours reproduces above — turned out not to be a small-data artifact but a property of the architecture. Depth on graphs is bought with residuals, jumping-knowledge connections or attention, not with more vanilla layers. You can watch the four-layer drop in the sweep you just ran.

GNNs met LLMs

The 2021 article predates the LLM era. The hybrid pattern since: serialize a graph (or its neighborhoods) into text and let an LLM reason over it — GraphRAG-style retrieval (Edge et al., 2024) is this idea at product scale — or let a GNN encode structure and hand embeddings to a language model. The split of labor is exactly the section 3 split: the GNN carries the connectivity the Transformer cannot afford to attend over; the LLM carries the language neither graphs nor convolutions were ever about.

Where GNNs still win

Variable, sparse, relational structure — the section 1 country, and it only grew: materials discovery (GNoME, Merchant et al., 2023), weather forecasting that beat numerical models (GraphCast, Lam et al., 2023), learned physics simulation (GNS, Sanchez-Gonzalez et al., 2020), antibiotic discovery (Stokes et al., 2020), web-scale recommendation where attention cannot reach (PinSage, Ying et al., 2018). And the newest member of the list, the reason this page exists: agent fleets. Our work graph is small enough to fit in a browser tab, structured enough that message passing means something (a VERIFIES really does depend on who performed and who received), and live at /t27f/live/ — the same schema the fixtures above follow.

7 · Into the weeds, briefly

The original's final section was a tour of open territory. The stops that matter most, updated:

Multigraphs and hierarchy.

Real graphs carry several edge types at once — ours has six, and nothing stops an agent-task pair from carrying both PERFORMS and BLOCKS over time. The fix is per-type message passing; RGCN-style relation weights are the standard cheap version. Nested graphs (a node that is itself a graph) handle hierarchy: a task's subgraph inside the fleet graph.

Sampling and batching.

Mini-batching a graph means choosing subgraphs that preserve what the loss needs — neighborhood sampling, cluster partitioning (Cluster-GCN, Chiang et al., 2019). Our own live system already practices the time-axis version: it replays a window of the event bus, and the caps in work_graph.t27 refuse growth rather than truncate.

Aggregation is an expressivity choice.

Sum is injective over multisets of embeddings (the GIN result, Xu et al., 2019: with enough dimensions, sums distinguish any two different neighborhoods); mean collapses "two weak neighbors" into "one strong one"; max keeps the strongest signal and forgets counts. The sweep's sum/mean/max panel is the toy-scale version of a theorem.

GCNs are subgraph approximators.

A k-layer GCN computes, for each node, a learned function of its k-hop subgraph. Two nodes with isomorphic neighborhoods are indistinguishable — the Weisfeiler-Lehman limit, and the reason GIN's sum matters.

Edges and duals.

Edge prediction on a graph is node prediction on its dual (the line graph). Our VERIFIES question becomes: classify nodes in the graph whose nodes are fleet events. Same math, different picture; sometimes the dual is the easier side.

Matrix powers are walks.

The A^2 panel in section 3 computed live what the original drew by hand: (A^k)[i,j] counts k-walks from i to j. Sparse matrix multiply, adjacency lists, and message passing are three views of one operation.