Networks of Relationships

When the data is a web of relationships

A picture is a grid. A sentence is a chain. But a communications network is neither. A month of call records is a web of stations held together by contacts — there is no left-to-right order, no rows and columns, and every station talks to a different number of others. A friendship network is the same shape, and so is a road map, and so is a citation web. For all of these, the relationships are the data, and we need a network built to learn on them.

Let us name the object precisely. A graph is a set of nodes (the entities — radios, people, cities) joined by edges (the relationships — contacts, friendships, roads). Each node can carry a feature vector (a station's traffic volume and band; a person's age and interests), and so can each edge. The single most important thing about a graph is that its structure — who connects to whom — carries the signal, and no architecture we have built so far can use it. In our running example the nodes are stations and the edges are the contacts between them, so from here on "node" and "station", "edge" and "link" mean the same thing.

Here is why a plain network — or a CNN, or an RNN — fails on a graph, because this mismatch is the whole motivation for the chapter. To feed a graph into anything we have built, you would first have to line the nodes up into a fixed list. But a graph has no natural order. Number a $24$-station contact graph $1$ through $24$ one way or a completely different way and it is the same network; the answer to "is this a coordinated net?" must not change because you relabelled the stations. A plain network handed a list treats position $1$ differently from position $5$ — so it would give different answers for the same network depending on an arbitrary choice of labels. That is a fatal flaw, and fixing it is the heart of this chapter.

So here is the plan. We will build the one operation a graph network runs — message passing — by hand on a tiny contact graph; watch it respect the graph's structure while ignoring the arbitrary labeling; discover that convolution and recurrence are secretly special cases of it; and finish with the instinct this whole site is building toward: looking at a new problem and knowing it calls for a graph network. And we pay it off on a real, high-value task: reading what kind of network this is straight from its structure.

Message passing: the one idea

A graph network updates each node's understanding of itself by listening to its neighbors. Every round, each node does three things in order: (1) collect a message from each neighbor — the neighbor's current feature vector; (2) aggregate those messages into one summary — add them up, or average them; and (3) update its own feature by combining its old value with that summary. Repeat the round a few times. That is the entire idea, and it is called message passing.

Let us make it hand-checkable. Take a central station (node $1$) in contact with three others (nodes $2$, $3$, $4$) — a little star, the shape of a net control station working three outstations. Give each node a single number as its starting feature — a stand-in for something we measured about the station, say how much traffic we saw from it, kept as a small integer so we can check every step: $h_1^{(0)} = 0$, $h_2^{(0)} = 1$, $h_3^{(0)} = 2$, $h_4^{(0)} = 3$. The superscript $(0)$ means "before any message passing." Note that the center starts at $0$ — on its own it is the quietest station on the net. What is about to make it interesting is entirely who it talks to. (One integer per station is a teaching toy — more on that honesty below.)

Now choose the simplest honest rules, so the arithmetic stays transparent — and let us say plainly that we are choosing them. Aggregate by mean (average the neighbors), and update by adding that average to the node's own value — no extra weights yet:

In words: a node's new value is its old value plus the average of its neighbors' values. We will name the real, learned version in a moment; first, watch information move.

Run round $1$, every node in the open. Node $1$'s neighbors are $2$, $3$, $4$, whose values are $1$, $2$, $3$ — their mean is $2$ — so:

In words: the center station just absorbed the average of its three neighbors — it now carries information about them, not just itself.

Each outstation has only node $1$ (value $0$) as its neighbor, so its mean is $0$ and it barely changes: $h_2 = 1 + 0 = 1$, $h_3 = 2 + 0 = 2$, $h_4 = 3 + 0 = 3$. After round $1$ the features are $(2, 1, 2, 3)$.

Now run round $2$, because this is the deep part. Using the round-$1$ values $(2, 1, 2, 3)$: node $1$'s neighbors are now $1$, $2$, $3$, mean $2$, so $h_1 = 2 + 2 = 4$; each outstation's only neighbor is node $1$, now $2$, so $h_2 = 1 + 2 = 3$, $h_3 = 2 + 2 = 4$, and $h_4 = 3 + 2 = 5$. After round $2$ the features are $(4, 3, 4, 5)$. Here is the payoff: after round $1$, node $2$ knew only about the center; after round $2$ it knows about the center which had already heard from nodes $3$ and $4$ — so node $2$'s feature now reflects the whole net, two links away. Each round reaches one hop further.

Now name the real thing, so no one thinks a graph network is merely an averager. In a real graph network the update is a neuron: it takes the node's old feature and the aggregated neighbor-summary, multiplies them by learned weight matrices, adds a bias, and squashes them through an activation — and those weights are trained by the very same loop as every other network we have built (see teaching the network). We used weights of $1$ and no squash purely so you could check the sums; swap in learned weights and a squash and the mechanism is identical. Message passing is a neuron applied over a graph's neighborhoods.

Why the order must not matter

Return to the fatal mismatch from the opening, because resolving it is the single property that makes a graph network a graph network. When node $1$ aggregates its neighbors $2$, $3$, $4$, it takes their mean — and the mean of $1$, $2$, $3$ is $2$ no matter what order you list them in. Sum, mean, and max all share this trait: they do not care about order. That is called permutation invariance, and it is exactly what a graph needs, because a graph's nodes have no true order. The step that computes it is the aggregation.

Contrast that with what would go wrong otherwise. Feed the three neighbors into a plain layer as a fixed list $[\text{neighbor-a}, \text{neighbor-b}, \text{neighbor-c}]$ and the layer's first weight multiplies whichever neighbor we happened to list first — so relabelling the stations changes the answer. A graph network dodges this by aggregating with an order-blind operation: relabel the net however you like, and the mean of a node's neighbors, and therefore the whole computation, is unchanged. The network's own shape, not our bookkeeping, drives the result. That matters in practice, because call signs and account handles are exactly the kind of label that gets reassigned, and no conclusion should turn on one.

So the one non-negotiable design rule is: the aggregation step must be permutation-invariant — sum, mean, or max — and everything else (the per-node update, the readout at the end) is built to preserve that. Choosing among the three is a real design choice with consequences. Mean washes out how many neighbors there are; sum keeps that count (useful when "a station in contact with four others" should differ from "a station in contact with two"); max grabs the single strongest signal. All three are order-blind, which is the point.

One honest subtlety, named and moved past: permutation-invariant does not mean "ignores structure." The mean forgets the order of the neighbors, but the graph still knows who the neighbors are — the edges decide who gets averaged together. Structure lives in the connections; order-blindness throws away only an arbitrary labeling we never should have imposed.

The grand unification

Here is the punchline that ties all of Part III together. A CNN and an RNN are not rivals of the graph network — they are special cases of it. A convolution is message passing on a grid graph: each pixel is a node connected to its immediate neighbors, and the filter aggregates that fixed little neighborhood — the sliding filter from seeing machines is exactly this. An RNN is message passing on a chain graph: each element is a node connected only to the one before it, and the hidden state from remembering machines is the message passed along. Same operation — gather from neighbors, aggregate, update — on three different connection patterns.

The grid and the chain are just especially regular graphs: every pixel has the same four neighbors, every sequence element has exactly one predecessor. A graph network drops those regularities and works on any connection pattern — three neighbors here, seven there, a ring, a tree, a tangled social web. That generality is the whole gift, and its price is that you can no longer rely on a fixed neighborhood or a natural order, which is precisely why aggregation had to become permutation-invariant.

Keep this as a mental model. Every architecture in this part answers one question — "how should a node combine information from its neighbors?" — and differs only in what counts as a neighbor: adjacent pixels (CNN), the previous step (RNN), or whoever the edges say (GNN). Once you see message passing as the common engine, the three chapters of Part III collapse into one idea wearing three coats. (This is a reframing, not a recipe: you would not build a CNN as a general graph network, because a CNN exploits the grid's tidiness to run far more efficiently — an efficiency gap we return to below.) The widget below lets you switch a graph between "grid," "chain," and "arbitrary" and watch the same message passing run on all three.

From nodes to an answer: reading a whole network

Now turn a graph full of updated node features into an actual prediction — the payoff this chapter has been building to. After a few rounds of message passing, every node carries a feature that reflects its whole neighborhood. To predict something about the whole net (is this a controlled hub-and-spoke command net, a flat peer-to-peer mesh, or an unrelated crowd?), pool all the node features into one graph-level vector with — what else — a permutation-invariant summary, then feed that to an ordinary predictor. This pooling step is called a readout.

Work it on our net. After round $2$ the node features were $(4, 3, 4, 5)$; sum them for the graph vector:

In words: message passing gives every station a context-aware description; the readout blends them into one description of the whole net; the predictor — a trained neuron — turns that into the answer we care about, say which kind of net this is.

One honest caveat, said once: our single-number features are a teaching toy. Real node features are vectors of dozens of numbers — traffic volume, time-of-day pattern, band, message lengths, how long the station has been active — and the predictor is trained on networks whose type is already known, not invented. The mechanism you just ran by hand is real; the tiny integers are not. And a model like this reads structure, not content: it is a way to sort a haystack, and it says nothing about who anyone is.

There are two shapes of graph task, and you will meet both. Graph-level prediction gives one answer for the whole graph (this net's type, this document's topic) and uses a readout as above. Node-level prediction gives one answer per node (is this account automated? which station is running the net?) and skips the readout, reading each node's final feature directly. Same message passing; you either pool at the end or you do not.

And here is the payoff. Sorting one network from another used to mean hand-crafting metrics — degree counts, clustering coefficients, formulas for features a human guessed might matter. A graph network learns the relevant features itself, straight from the stations-and-links structure. This is now how a great deal of network analysis works — coordinated-account detection on social platforms, fraud rings in transaction graphs, intrusion detection over traffic between hosts: triage millions of candidate clusters before a human looks at one. No hype — just the shape of the win: structure in, verdict out, features learned along the way.

Does this problem call for a GNN?

This is the instinct the whole site is building toward, so let us make it explicit and memorable — the capstone chapter, choosing your tool, will hand you problems and expect you to reach for a graph network on exactly the right one. Here is a short checklist of signals that a problem is a graph problem: (1) your data is naturally entities and relationships, not a grid, a sequence, or a flat table; (2) the connections carry meaning — who links to whom changes the answer; (3) there is no natural ordering of the entities, so any answer must be permutation-invariant; (4) entities have varying numbers of neighbors. When several of these are true, you are looking at a graph problem.

Make the signals concrete with a roll-call of problems that scream graph, so the pattern sticks: communications and transaction networks (entities and the contacts between them); social-network and fraud-ring detection (people and interactions); recommendation (users and the items they touch); traffic and delivery routing (intersections and roads); molecular property and drug-target prediction, where the same machinery reads atoms and bonds; knowledge graphs and question answering; and physics simulation on meshes. Each is entities joined by meaningful relationships with no natural order — the graph-network fingerprint.

Now the counter-signals, just as sharply, because knowing when not to reach for a graph network is half the skill and ties back to earlier chapters. A spreadsheet of independent rows and columns is tabular data — start with boosted trees from the classical toolbox, not a graph network. A photo is a grid — use a CNN from seeing machines. Plain text is a sequence — use attention (from remembering machines and the sister site). The tell is whether the relationships between entities are the signal. If your rows do not reference each other, forcing them into a graph buys nothing.

State the honest nuance once, so the instinct is calibrated rather than trigger-happy. Almost anything can be drawn as a graph — an image is a grid graph, a sentence a chain graph — but you should reach for a graph network only when the graph structure is irregular and carries the signal, when there is no grid or sequence you could have used instead. A graph network on data that was really a nice grid just throws away the CNN's efficiency. Use the most specific tool the data's shape allows; a graph network is the right answer when the shape is genuinely a web.

And to foreshadow the capstone directly: in choosing your tool at the end of the book, you will walk through six real scenarios and pick the model for each — and the one whose right answer is "a graph network" will be recognizable by exactly the signals in this section. Recognizing the graph is the skill; the message passing is the easy part.

See it move

The video runs the whole argument in one motion: watch the star network's center station gather its three neighbors ($1$, $2$, $3$), average them to $2$, and update itself to $2$; watch a second round push information one hop further so an outer station comes to reflect the whole net; then watch the readout pool the stations into one number ($16$) and predict a verdict — the same numbers you did by hand, and the reveal that a grid and a chain are just special graphs.

Now you drive it. The message-passer below drops a live graph in front of you. Press "Pass messages" to run one round — small tokens flow along the edges, nodes update, and the value on each node changes, with a color tracking each node's feature so you can watch information diffuse across the graph. Switch the aggregation between sum, mean, and max; inject a signal at one node and watch how many rounds it takes to reach the far side; and — the punchline of the chapter — switch the graph's shape between an arbitrary network, a chain (an RNN!), and a grid (a CNN!) and see the identical message passing run on all three.

Where you'll meet this

Step back to the whole field. With graphs, we have now covered every major shape of data and its matching architecture: tables (boosted trees), grids (CNNs), sequences (RNNs and attention), and webs (GNNs). That quartet is the practitioner's map — see the shape, know the tool — and it is exactly the judgement the capstone chapter turns into a decision framework.

Everything we have built so far is discriminative: data comes in, a label or a number comes out — is this a coordinated net, is this the digit $7$, what word comes next. But there is a whole other ambition: not judging data, but making it — generating a new image, a new sentence, a new structure with a property you asked for. The next chapter opens that door with generative models, and graph networks reappear there too, now used to design structures rather than just score them.

One more thread, to the sister site. The transformer that runs every large language model (see the sister site) is itself close kin to a graph network: attention lets every token attend to every other, which is message passing on a fully connected graph of words — "graph attention" is a real family of models, and this is its cousin. The reader who understands why a contact network needs a graph network understands, from a different door, why a sentence needs attention: both are learning on relationships.

Close warm and specific. You have passed messages by hand around a small net ($0, 1, 2, 3 \to 2, 1, 2, 3 \to 4, 3, 4, 5$), pooled it to a single readout of $16$, seen why the answer cannot depend on how the stations are numbered, learned that CNNs and RNNs are message passing in disguise, and — most valuable of all — collected the signals that let you look at a new problem and say "this one's a graph." That recognition is the instinct the final chapter will put to the test.