When the data is a web of relationships
A picture is a grid and a sentence is a chain. A communications network is neither: it is stations joined by contacts, each station with a different number of neighbors and no natural ordering. The relationships themselves carry the signal.
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 structure, meaning 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.
| Graph object | Station example | Social example |
|---|---|---|
| Node | Radio station | Person |
| Edge | Contact | Friendship |
| Feature | Traffic volume | Age |
Number a $24$-station graph $1$ through $24$ in a different order and it is still the same network. A plain layer treats list positions $1$ and $5$ differently, so arbitrary numbering could change its prediction. The answer must not change because we relabeled the stations, and fixing that is what this chapter is about.
Message passing: the one idea
- CollectRead neighbors’ current features.
- AggregateCombine them by sum, mean, or max.
- UpdateMix the summary with the old feature.
A graph network updates each node's description of itself from its neighbors. Every round, each node does three things in order: (1) collect a message from each neighbor, which is the neighbor's current feature vector; (2) aggregate those messages into one summary by adding or averaging them; and (3) update its own feature by combining its old value with that summary. Repeat the round a few times. This procedure is called message passing.
Use a star: station $1$ contacts stations $2$, $3$, $4$. Their starting features are $h_1^{(0)}=0$, $h_2^{(0)}=1$, $h_3^{(0)}=2$, $h_4^{(0)}=3$; the superscript $(0)$ means before message passing. These single-number traffic measurements are a teaching toy.
For hand-checkable arithmetic, average the neighbors and add the result to the old value:
$$h_v^{\text{new}} = h_v^{\text{old}} + \operatorname{mean}\big(h_u : u \text{ is a neighbor of } v\big)$$In words: a node's new value is its old value plus the average of its neighbors' values. The real, learned version comes later in the section.
Run round $1$, with every node updating at once. Node $1$'s neighbors are $2$, $3$, $4$, whose values are $1$, $2$, $3$, so their mean is $2$:
$$h_1^{(1)} = h_1^{(0)} + \operatorname{mean}(h_2^{(0)}, h_3^{(0)}, h_4^{(0)}) = 0 + \operatorname{mean}(1, 2, 3) = 0 + 2 = 2$$In words: the center station absorbed the average of its three neighbors, so it now carries information about them as well as itself.
- GatherRead the three neighbors’ values: $1,2,3$.
- Average$(1+2+3)/3=2$.
- UpdateOld center $0$ plus $2$ gives $2$.
Each outstation has only node $1$ (value $0$) as its neighbor, so its mean is $0$ and it stays unchanged: $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)$.
Round $2$ uses the previous values $(2,1,2,3)$: $h_1=2+2=4$, $h_2=1+2=3$, $h_3=2+2=4$, $h_4=3+2=5$. The result is $(4,3,4,5)$. Node $2$ now reflects nodes $3$ and $4$ through their shared center: two rounds reach two hops.
The real update is a neuron: multiply the old feature and neighbor summary by learned matrices, add a bias, then apply an activation. These weights use the same training loop. Our weights of $1$ and absent squash let us check the arithmetic.
Why the order must not matter
| Neighbor order | Sum | Mean |
|---|---|---|
| $1,2,3$ | $6$ | $2$ |
| $3,1,2$ | $6$ | $2$ |
| $2,3,1$ | $6$ | $2$ |
Back to the relabeling problem from the opening, because resolving it is the 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 that trait. It is called permutation invariance, and it is what a graph needs, because a graph's nodes have no true order. The step that computes it is the aggregation.
![Two panels split by a vertical hairline. Top panel 'a GNN — order-blind, correct': the three neighbor values listed in two different orders, order A [1,2,3] and order B [3,1,2], both feeding a 'mean' box that outputs the same center update '= 2' in mint, with a mint check 'same answer either way' and note 'mean(1,2,3) = 2 regardless of order'. Bottom panel 'a plain layer — order-sensitive, wrong': the same two orderings fed as fixed lists into three violet weight boxes w1, w2, w3, giving 1·w1 + 2·w2 + 3·w3 in one case and 3·w1 + 1·w2 + 2·w3 in the other, joined by a red 'not equal' sign, with a red cross 'answer changes when you relabel'.](media/networks-of-relationships/permutation-invariance.svg)
Mean loses neighbor count; sum can retain it; max keeps the strongest signal. All ignore ordering while the edges still decide which nodes combine.
One operation, three neighborhoods
| Architecture | What is a neighbor? | What is shared? |
|---|---|---|
| CNN | Nearby grid pixels | Filter weights at each position |
| RNN | Previous position in a chain | State-update weights |
| GNN | Nodes joined by edges | Message and update functions |
This is a common way to view the architectures, not an implementation recipe: grid convolutions exploit fixed offsets, recurrence respects sequence direction, and general graphs allow irregular connections. A CNN uses grid structure more efficiently than a generic GNN. The widget compares these connection patterns.
From nodes to an answer: reading a whole network
| Connection pattern | Neighbors | Architecture |
|---|---|---|
| Grid | Nearby pixels at fixed offsets | CNN |
| Chain | Earlier sequence state | RNN |
| Irregular graph | Nodes joined by edges | GNN |
For a whole-network prediction, pool the final node features into one vector, then feed it to a predictor. This order-independent pooling is a readout.
Work it on our net. After round $2$ the node features were $(4, 3, 4, 5)$; sum them for the graph vector:
$$\text{readout} = \sum_v h_v^{(2)} = 4 + 3 + 4 + 5 = 16 \;\longrightarrow\; \text{predictor} \;\longrightarrow\; \text{net type}$$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.
Our single-number features are a teaching toy. Real node features are vectors of dozens of numbers, including traffic volume, time-of-day pattern, band, message lengths and how long the station has been active, and the predictor is trained on networks whose type is already known. The mechanism you just ran by hand is what a real one does; the tiny integers are not. A model like this reads structure rather than content, so it sorts a pile of traffic and says nothing about who anyone is.
There are two shapes of graph task; both use the same message passing:
| Task | Final operation | Example answer |
|---|---|---|
| Graph-level | Pool node features with a readout | The whole net’s type or a document’s topic |
| Node-level | Read each node’s final feature directly | Whether each account is automated or which station runs the net |
Does this problem call for a GNN?
| Question | Yes | No |
|---|---|---|
| Entities joined by relationships? | Consider a graph. | Use the native data shape. |
| Connections change the answer? | Message passing may help. | Start with independent rows. |
| No natural node order? | Use order-independent aggregation. | Exploit the order. |
| Varying neighborhoods? | GNNs accommodate them. | A grid or chain may suffice. |
| Irregular structure carries signal? | Compare a GNN with a baseline. | Prefer a specialized model. |
The capstone applies this choice:
| Data | First family to consider |
|---|---|
| Independent rows | Trees |
| Images | CNNs |
| Text | Attention and the LLM book |
See it move
Watch two rounds on the star, then the readout of $16$.
Press “Pass messages,” change the aggregation, and compare the graph shapes.
Where you'll meet this
| Where | What it looks like | Chapter link |
|---|---|---|
| Model selection | Match tables, grids, chains, and webs to their structure. | Choosing your tool |
| Generation | Learn a data distribution to create examples. | Making things up |
| Language | Attention without a mask is message passing on a fully connected graph of words; a transformer is close kin to a graph network. For next-word prediction, the mask blocks messages from later words. | LLM book |
What you now know
- Graphs represent entities and their relationships.
- Message passing gathers, aggregates, and updates node features.
- Each round reaches one hop farther.
- Aggregation ignores arbitrary neighbor order while preserving connections.
- A readout pools node features for a graph-level prediction.
- Use a GNN when irregular relationships carry useful signal.
Where we’re headed. We can match models to data shapes. Next we generate new data instead of assigning labels.