Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 73 ยท Generative and Other Models

Graph Neural Networks

Learn how graph neural networks work: message passing, the GCN layer, node classification, over-smoothing and readouts, all built from scratch in NumPy.

Images are grids and sentences are sequences, and the networks in this course exploit that structure: convolutions slide over grids, recurrent layers walk along sequences. A lot of important data is neither. A social network is people connected by friendships. A molecule is atoms connected by bonds. A road map, a citation network and a web of products bought together are all graphs: a set of nodes joined by edges, with no fixed order and no fixed number of neighbors.

A graph neural network (GNN) is a network designed for such data. Its central idea is simple and you already know the ingredients: each node builds its representation by collecting information from its neighbors, then transforming it with a learned weight matrix. Repeating this a few times lets information travel across the graph. In this lesson you will build the classic graph convolutional network (GCN) layer in NumPy, train it on a small two-community graph, and see why it beats a model that ignores the edges.

Graphs in the wild

Social networks People are nodes, friendships are edges.
Molecules Atoms are nodes, bonds are edges.
Road maps Junctions are nodes, roads are edges.
Citations Papers are nodes, references are edges.

Same math, very different domains.

1 / 2

Describing a graph to a network

A graph with n nodes is stored as two arrays:

  • the adjacency matrix A, an n by n matrix with A[i, j] = 1 if there is an edge between nodes i and j (and 0 otherwise); for an undirected graph it is symmetric;
  • the feature matrix X, with one row of d numbers per node (for example, the properties of an atom, or the words in a paper).

The key property a GNN must have is that the node order carries no meaning. If you renumber the nodes, the answer for each node must stay the same; it just moves to a new row. This is called permutation equivariance, and it is why you cannot simply flatten A and feed it to a dense network.

Message passing

Most GNNs follow the same three-step pattern, called message passing. For every node v:

  1. Message: each neighbor u sends something about itself, usually its current feature vector.
  2. Aggregate: v combines the incoming messages with an operation that does not depend on their order: sum, mean or max.
  3. Update: v combines the aggregate with its own state, using a small neural network.

After one round, a node knows about its direct neighbors. After two rounds, it knows about neighbors of neighbors (two hops), and so on. The number of layers is therefore the radius of the neighborhood a node can see, much like the receptive field in a CNN.

With the adjacency matrix, the aggregation step for all nodes at once is a single matrix product: row v of A @ X is the sum of the feature vectors of v's neighbors.

The GCN layer

The graph convolutional network of Kipf and Welling (2017) is the simplest widely used version. One layer computes

TEXT
H_next = ReLU( A_hat @ H @ W )      with   A_hat = D^(-1/2) (A + I) D^(-1/2)

Taking it apart:

  • A + I adds a self-loop, so each node also includes its own features in the sum (otherwise a node would forget itself).
  • D is the diagonal degree matrix of A + I: the number of neighbors of each node, counting itself. Multiplying by D^(-1/2) on both sides normalizes the sum, so that a node with 50 neighbors does not get a vector 50 times larger than a node with 2.
  • W is a learned weight matrix, shared by all nodes (just like a convolution kernel is shared by all positions).
  • ReLU is the nonlinearity.

Notice the resemblance to layers in a dense network: A_hat @ H is a fixed averaging step, and @ W is the usual linear layer. The only new piece is the averaging over neighbors.

Python Building A_hat and watching features spread

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Row 0 of A_hat has three nonzero entries: the node itself and its two neighbors, each weighted by 1 / sqrt(deg_i * deg_j). Now look at the table. Each round of averaging shrinks the spread of features inside a group fast (0.309 down to 0.147 after two rounds), because the noise of neighbors cancels. The gap between the group means shrinks too, but more slowly (1.323 to 0.963), since only the two bridge edges mix the groups. The ratio of gap to spread is best after about two rounds (roughly 4.3 at the start, 6.5 at round 2), then it falls again as the groups blur together. Remember this pattern: a little smoothing helps, a lot hurts.

Training a GCN to classify nodes

The classic benchmark is semi-supervised node classification: the graph is known, but only a few nodes have labels. The task is to predict the labels of the rest. This works because of homophily: connected nodes tend to share a label (friends share interests, a paper cites related papers).

The next program builds a 24-node graph with two communities and gives each node 4 features that are deliberately only weakly informative (the signal is small compared with the noise). Only two nodes, one per community, are labeled. It trains a two-layer GCN with backpropagation written by hand, and compares it with a logistic regression that sees only the node's own features and ignores the edges.

For two GCN layers the forward pass is Z1 = A_hat X W0, H1 = ReLU(Z1), Z2 = A_hat H1 W1, followed by a softmax per node. The loss is cross-entropy over the labeled nodes only. The gradients follow the usual chain rule, and A_hat being symmetric simplifies the backward step: dH1 = A_hat dZ2 W1^T.

Python A two-layer GCN versus a graph-blind baseline

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The graph has 51 edges inside the communities and only 6 between them. With just two labels, the GCN classifies all 22 unlabeled nodes correctly (accuracy 1.00), while the same network without edges reaches only 0.50, which is chance for two classes.

The "no edges" model is the same network with A_hat = I, so nodes cannot communicate and each one is classified from its noisy features alone. From two labeled points it has almost nothing to learn from. The GCN gets far more out of the same labels, because averaging over neighbors cancels much of each node's feature noise (as the previous experiment showed) and because the two labeled nodes "spread" their influence along the edges of their communities.

Over-smoothing and other limits

The first experiment hides a trap. Averaging over neighbors keeps going: after many rounds, every node's vector approaches the same value (in a connected graph the repeated product with A_hat converges toward a dominant eigenvector), and the difference between communities disappears. This is over-smoothing, and it is why GNNs are usually shallow (2 to 4 layers), unlike the 50- or 100-layer CNNs of CNN Architectures. Residual connections, normalization, and jumping-knowledge schemes that combine the outputs of several layers all help a little.

Other limits to know about:

  • Large graphs. Multiplying by the full adjacency matrix is too expensive for a graph with millions of nodes, so methods like GraphSAGE sample a fixed number of neighbors per node and train on mini-batches.
  • Uneven neighbors. A GCN weights neighbors by degree only. Graph attention networks (GAT) learn a weight per edge, using the same idea as attention: neighbors that matter more get a larger share.
  • Expressive power. Standard message passing cannot tell apart some graphs that differ only in subtle structure (it is bounded by the Weisfeiler-Leman test), which has led to more expressive designs.
  • Heterophily. If neighbors tend to have different labels, plain averaging hurts, and models need other aggregation schemes.

Graph-level tasks and readout

Sometimes the answer is for the whole graph, such as "is this molecule toxic?". A readout layer collapses the node vectors into one graph vector with an order-independent operation: the sum, the mean or the max over nodes. A normal classifier then works on that vector. The two properties that matter can be checked directly:

Python Permutation equivariance and sum readout

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Renumbering the nodes only reorders the output rows (equivariance), and the summed readout is unchanged (invariance). That is exactly the behavior that a graph model needs and that a dense network on a flattened adjacency matrix does not have.

GNNs in a framework

You rarely write the matrix algebra yourself. The PyTorch Geometric library supplies GCN, GAT, GraphSAGE and many more layers, plus tools for sparse graphs and mini-batching:

Python
# Read-only: PyTorch Geometric is not available in the in-browser runner.
import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv

class GCN(torch.nn.Module):
    def __init__(self, in_dim, hidden, classes):
        super().__init__()
        self.conv1 = GCNConv(in_dim, hidden)
        self.conv2 = GCNConv(hidden, classes)

    def forward(self, x, edge_index):                 # edge_index: (2, num_edges) list of node pairs
        x = F.relu(self.conv1(x, edge_index))
        x = F.dropout(x, p=0.5, training=self.training)
        return self.conv2(x, edge_index)              # one row of class scores per node

# training uses cross-entropy on the labeled nodes only:
# loss = F.cross_entropy(model(data.x, data.edge_index)[data.train_mask], data.y[data.train_mask])

Notice that graphs are stored as an edge_index list of pairs instead of a dense matrix, which is how sparse real-world graphs fit in memory. Everything else is the same recipe you used for CNNs: stack layers, add dropout, train with cross-entropy.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a GCN layer, why do we add the identity matrix to the adjacency matrix (A + I)?

    Without self-loops, a node's new vector would be built only from its neighbors and it would forget its own features.
  2. 2. What does multiplying by D^(-1/2) on both sides of A + I accomplish?

    Dividing by the square roots of the degrees keeps the scale of the aggregated features comparable between nodes with few and many neighbors.
  3. 3. A GNN with k message-passing layers lets a node use information from which nodes?

    Each round moves information one edge further, so after k rounds the node has seen its k-hop neighborhood.
  4. 4. What is over-smoothing?

    Repeated neighbor averaging blends all features together, so deep GCNs lose the distinctions the task needs. That is why GNNs are usually shallow.
  5. 5. Which readout makes a graph-level prediction independent of node numbering?

    Sum, mean and max do not depend on the order of the nodes, so the graph vector is the same for any renumbering.

Summary

  • A graph is nodes plus edges; it is stored as an adjacency matrix (or edge list) and a node feature matrix, and a GNN must not depend on node order.
  • Message passing has three steps: collect messages from neighbors, aggregate them with an order-independent operation, and update with a learned transformation.
  • A GCN layer is ReLU(A_hat H W), where A_hat = D^(-1/2)(A + I)D^(-1/2) averages each node with its neighbors.
  • With k layers, a node sees its k-hop neighborhood; averaging also denoises features, which makes few labels go a long way when neighbors share labels (homophily).
  • Too many layers cause over-smoothing, so GNNs stay shallow; GraphSAGE handles large graphs and GAT learns neighbor weights.
  • Graph-level predictions use a sum, mean or max readout, and PyTorch Geometric provides ready-made layers.

Next: Deep Learning Frameworks Compared.