Part III · Ch. 18 — The Graph Network (GNN)

Part III · Chapter 18 of 29

The Graph Network (GNN)

Learn by passing messages between connected nodes


What shape does it eat?

Sometimes the structure that matters is who is connected to whom, not where a pixel sits or when a measurement arrived. Can a model use those relationships directly? Start with the same four-node contact star as the sister book, then look at a model trained on a real social graph.

A graph describes entities connected by relationships. A node is an entity; an edge is a connection between nodes. An adjacency matrix records which pairs are connected. Each node can also carry a feature vector. The drawing and these arrays describe the same connectivity, and the drawing’s horizontal and vertical positions are not features given to the model.

The four-node contact star beside its adjacency matrix and its neighbor-mean matrix; a second panel draws the karate-club graph from its edge list, with training and validation nodes outlined differently.
An edge list supplies structure that a plain feature table omits.

The karate-club network in this chapter trains on the edge list of a well-known small social graph, a university karate club, with identity node features: each node starts with its own coordinate marked. The task predicts a class per node. Training uses some labels and holds others out, while the graph structure and features stay visible. That is transductive evaluation, testing unseen labels on an observed graph. Classifying nodes in an entirely new graph is a different question.

Let edges choose the neighbors

Message passing gathers neighbor values, aggregates them, then updates a node. Aggregation is a rule such as sum, mean, or max. Permutation invariance means the aggregate is unchanged when its inputs are reordered: adding 1,2,3 gives the same total as adding 3,1,2. Permutation equivariance means node outputs follow the same reordering as their input nodes.

Three identical star layouts with values (0,1,2,3), (2,1,2,3), (4,3,4,5), and the readout 16. Keep each old node value visible while showing the simultaneous update.
The same simultaneous neighbor-mean rule reaches farther on each round.

Those properties let you renumber nodes without changing the problem. Adjacency rows and columns have to move together with the matching features. Relabel the features alone and they land on different entities. Dragging a node on the page changes its display position only. A model built on the given adjacency still gathers from the same neighbors after the drawing moves.

The same contact star, every update

The hand star has center value 0 and leaf values 1,2,3. Its center connects to each leaf, with no edges between leaves. The update keeps a node’s old value and adds the mean of its neighbors. Every node reads the old values from the same round. A leaf never consumes a center value that was updated a moment earlier in the same calculation.

Two simultaneous rounds

The first center is 0+(1+2+3)/3=2. Each leaf sees the old center zero, so the leaves stay 1+0=1, 2+0=2, and 3+0=3. The new vector is (2,1,2,3). On the second round the center becomes 2+(1+2+3)/3=4. The leaves read the old center 2, giving 3,4,5. The final vector is (4,3,4,5), and its sum readout is 4+3+4+5=16.

The same update as a matrix

Let P have first row [0,1/3,1/3,1/3], with each leaf row [1,0,0,0]. Multiplying P by the feature column gathers each node’s neighbor mean. Add the identity matrix I to keep each old value too. Its first row applied to the initial feature column gives 0+(1+2+3)/3=2, matching the picture. An empty neighborhood contributes zero in the widget, so that node keeps its own value.

In the first formula, bold H collects the node features, and bold I and P perform the hand keep-plus-mean update. The karate-club network uses a different gather rule. Its A is the original adjacency, I adds self-connections, and d counts each node’s connections after that addition. A hat marks the normalized adjacency. Bold W and b are the learned weights and biases:

$$\mathbf{H}_{\mathrm{new}}=(\mathbf{I}+\mathbf{P})\mathbf{H}$$

In words: keep the node’s old feature and add its neighbors’ mean.

$$\hat A_{ij}=\frac{A_{ij}+I_{ij}}{\sqrt{d_i d_j}},\qquad d_i=\sum_j(A_{ij}+I_{ij})$$

In words: add self-connections, then scale each connection by the square root of the two endpoint degrees.

$$\mathbf{H}^{\prime}=\mathrm{ReLU}(\hat{\mathbf{A}}\mathbf{H}\mathbf{W}^{\top}+\mathbf{b})$$

In words: gather normalized neighbor features, transform them with the learned weight matrix, add bias, and apply the activation. The superscript top transposes the weight matrix: it swaps rows and columns without changing entries. Stored weights are output rows by input columns, as in chapter 3; the transpose lets these row-shaped node features multiply them.

Replay predictions on the observed graph

The first layer of the karate-club network maps 34 identity features to four hidden coordinates. Its weights and biases contribute 4×34+4=140 parameters. The second maps four coordinates to two scores, contributing 2×4+2=10. So the model has 150 trainable parameters. The normalized adjacency is part of its fixed graph computation, not another trainable weight table.

Class probabilities for every node at the first and last saved steps, on one fixed layout: the outline shows the true class and the fill the predicted one, with held-out mistakes marked. Separate panels show validation accuracy and loss.
The trained model predicts held-out labels on a graph whose structure it saw during training.

At step 300, training loss is 0.00053, validation loss is 0.274, and validation accuracy is 0.857. The training loss is near zero while the validation loss is not, so the held-out nodes are where to look, even though the training labels come out confident.

The sister book’s contact-star animation uses the same simultaneous mean-plus-old arithmetic.

Where this shows up when you train

Contact networks and road connectivity come with relationships that can guide a gather rule. A table of unrelated records doesn’t gain useful edges because a graph model happens to be available. You need a reason why each connection should help answer the task. If distance or direction matters, put those quantities in the representation; dragging the diagram into a nicer layout doesn’t supply them.

Mean aggregation loses the count of contributing neighbors, since repeated equal values share a mean. Sum keeps the count and can grow with neighborhood size. Max keeps one strongest value and discards the rest. Before stacking more message rounds, look at what one round preserves, what it loses, and how far a signal travels along real edges. A deeper graph model can’t recover a distinction its inputs or its aggregation rule already erased.

What you now know

  • A graph records entities and their connections.
  • Aggregation ignores neighbor order while preserving who is connected.
  • Holding out node labels on a visible graph tests the labels, not a new graph.

Where we’re headed

An autoencoder learns a compact representation by trying to reconstruct its input. Continue the story.