Graph Neural Networks from Scratch — Learning from Connections

Social networks, molecules and road maps are all built from dots and lines. This piece builds message passing up from nothing, explains why stacking layers makes every node look identical (over-smoothing), and follows the idea through to how recommenders and drug discovery actually use it.

Semi-Supervised Classification with Graph Convolutional Networks

What the class register doesn't tell you

A new student joins your class. The register lists their name, age and hometown, and none of it tells you much about who they are. A few weeks later, once you can see who they walk home with, a picture suddenly forms. Most of the information about a person lives not in their own row, but in their connections.

Textbook machine-learning data comes in tables. One row per sample, rows independent of each other. But an enormous amount of real data is the opposite: the gaps between rows are the substance. Follower relationships, paper citations, road networks, protein interactions, and molecules — atoms joined by chemical bonds. All of these are dots and lines, i.e. graphs. The vocabulary of graphs and the classical questions like shortest paths are covered in Graph Algorithms from Scratch; this article is about learning on top of them.

Try to feed a graph straight into a neural network and you hit three walls immediately.

1. The number of neighbours varies wildly. A node with one neighbour and a node with ten thousand live in the same graph. There is no fixed input length.
2. Neighbours have no order. "The first friend in the list" means nothing. Shuffling the list must not change the answer — this is permutation invariance.
3. Graphs come in different sizes. A molecule may have ten atoms or a hundred.

CNNs work on images because every pixel has neighbours above, below, left and right, in fixed positions. Graphs give you no such scaffold. A GNN (Graph Neural Network) is a network rebuilt from the ground up to satisfy all three constraints head-on.

The intuition: listen to your neighbours, then rewrite yourself

What a GNN does is an almost anticlimactically simple loop.

1. Every node sends its current state to all of its neighbours
2. Every node combines the letters it receives into one (sum them, or average them)
3. Every node builds a new state from that combination plus its own previous state

That's one round. The interesting part is round two. The letters arriving in round two carry the states your neighbours updated in round one — which already have information about their neighbours dissolved into them. Run it k times and information from k hops away reaches you. The number of layers is literally the setting for "how far do I look", and that is the first property to internalise about GNNs.

The second is that every node uses the same rule. Rather than per-node weights, one set of weight matrices is shared by all of them — exactly as a CNN filter is the same wherever you place it on the image. That sharing is why the same trained model can be applied to a graph of a different size and shape than the one it was trained on.

The mechanism: message passing

Write those three steps down as an equation and you get message passing. Almost every GNN paper can be read as swapping out one piece of this frame.

Taking the symbols one at a time: $h_v^{(k)}$ is "the state vector of node $v$ at layer $k$", where layer 0 is the raw input features (signup date and region for a user, element type for an atom). $N(v)$ is the set of $v$'s neighbours. $\psi$ is the message function, which builds the contents of the letter from the sender's and receiver's states. $\bigoplus$ is the aggregation, which folds a bundle of letters into one. $\phi$ is the update function, which produces the new state from your old state and that bundle.

In other words, the equation says nothing more than "collect letters from your neighbours, bundle them, rewrite yourself."

The catch is that $\bigoplus$ may only be an order-independent operation: sum, mean, max. You may not concatenate neighbour vectors in sequence and push them through a dense layer. Reordering the friend list would change the output, which breaks the permutation invariance from earlier. This single restriction constrains GNN design far more than it first appears.

The most famous concrete instance is the GCN (Graph Convolutional Network). Written for all nodes at once in matrix form, it fits on one line.

$H^{(k)}$ stacks every node's state into a matrix (nodes × dimensions). $\tilde{A} = A + I$ is the adjacency matrix plus the identity — the connection table with a self-loop added at every node. $\tilde{D}$ is the diagonal matrix of degrees (how many neighbours each node has), $W^{(k)}$ holds the learned weights, and $\sigma$ is a nonlinearity such as ReLU.

Put plainly: "mix the features of your neighbours and yourself, splitting the bill by degree, multiply by a weight matrix shared with everyone, and pass through a nonlinearity." That is the whole of it.

Should you trust every neighbour equally?

Averaging makes a strong assumption: that all neighbours deserve the same trust. In reality, of ten friends, perhaps two explain your taste. So the next question is how to decide the share of attention given to each neighbour. Since these are shares, they have to sum to one — which is what softmax is for.