A General Perspective on GNNs

The lecture opens with a short recap of Lecture 3. Slide 4 shows the deep graph encoder: the input graph goes through graph-convolution layers, activation functions and regularisation (for example dropout), more graph convolutions, and so on; the output is a node embedding for every node (and, by pooling, embeddings of subgraphs and whole graphs).

Slide 5 restates the central idea (Kipf and Welling): a node's neighbourhood defines a computation graph. First determine the computation graph of node \(i\) (the rings of neighbours at distance 1 and 2), then propagate and transform information along it. The goal is to learn how to propagate information across the graph to compute node features.

Slide 6: nodes aggregate information from their neighbours using neural networks — each grey box in the tree of target node A is a small network that takes the vectors arriving from the children. Slide 7: every node defines its own computation graph based on its neighbourhood; the figure draws a separate tree under each node of the input graph, and the trees differ in shape.

The question for today: Lecture 3 used one specific box (average the neighbours, then a linear map and a non-linearity). What are all the reasonable choices for the box and for how boxes are wired together? This lecture builds a general vocabulary in which GCN, GraphSAGE and GAT are just three settings.

Slides 8–13 introduce the framework from You, Ying and Leskovec, "Design Space of Graph Neural Networks" (NeurIPS 2020). The figure is a two-layer computation tree, labelled with five numbered parts:

1. Message — what each node sends to its neighbours.
2. Aggregation — how a node combines the messages it receives. Slide 9: GNN layer = message + aggregation, and different choices give GCN, GraphSAGE, GAT, …
3. Layer connectivity (slide 10) — how layers are connected into a full GNN: stack them sequentially, and possibly add skip connections.
4. Graph augmentation (slide 11) — the idea that the raw input graph ≠ the computational graph. We may change the features (graph feature augmentation) or the structure (graph structure augmentation) before message passing.
5. Learning objective (slide 12) — how we train: supervised or unsupervised objectives, at the node, edge or graph level. (These are discussed later in the course.)

Slide 13 repeats the full picture as a summary. In the figure, layer 2 sits above layer 1: messages flow upward from the leaves (input features), each layer has its own message and aggregation, and the arrows between the layers are "layer connectivity". Graph augmentation acts at the bottom (on what the tree is built from), and the learning objective at the top (on the final embedding).

This lecture covers parts 1–3. Parts 4–5 are the subject of Lecture 5.

Slide 15 zooms in on parts 1 and 2. Slide 16 states the idea of a GNN layer: compress a set of vectors into a single vector. The input is the node's own previous embedding \(\mathbf{h}_v^{(l-1)}\) and the neighbours' previous embeddings \(\mathbf{h}_{u}^{(l-1)}, u\in N(v)\); the output is the new embedding \(\mathbf{h}_v^{(l)}\). It works in two steps: (1) message, (2) aggregation.

(1) Message computation (slide 17). A message function turns each node's embedding into a message:

Intuition: each node creates a message that will be sent to other nodes later. Example: a linear layer, \(\mathbf{m}_u^{(l)}=\mathbf{W}^{(l)}\mathbf{h}_u^{(l-1)}\) — multiply the node features by a weight matrix. The figure marks the message step as the small boxes just above the coloured leaf nodes.

(2) Aggregation (slide 18). Node \(v\) aggregates the messages from its neighbours:

Examples: Sum\((\cdot)\), Mean\((\cdot)\) or Max\((\cdot)\) aggregators, e.g. \(\mathbf{h}_v^{(l)}=\mathrm{Sum}(\{\mathbf{m}_u^{(l)},u\in N(v)\})\). The input is a set (more precisely a multiset), so AGG must not depend on the order of its inputs — this is what keeps the layer permutation equivariant (Lecture 3).

Slide 19 points out an issue with the aggregation above: the information from node \(v\) itself can get lost, because \(\mathbf{h}_v^{(l)}\) does not directly depend on \(\mathbf{h}_v^{(l-1)}\) — only the neighbours' messages enter.

Solution: include \(\mathbf{h}_v^{(l-1)}\) when computing \(\mathbf{h}_v^{(l)}\).

• Message: also compute a message from \(v\) itself. Usually a different computation is used for the self-message: \(\mathbf{m}_u^{(l)}=\mathbf{W}^{(l)}\mathbf{h}_u^{(l-1)}\) for neighbours, \(\mathbf{m}_v^{(l)}=\mathbf{B}^{(l)}\mathbf{h}_v^{(l-1)}\) for the node itself (the figure colours the two kinds differently).
• Aggregation: first aggregate from the neighbours, then combine with the self-message, via concatenation or summation:

Slide 20 puts it together: (1) message, \(\mathbf{m}_u^{(l)}=\mathrm{MSG}^{(l)}(\mathbf{h}_u^{(l-1)})\) for \(u\in N(v)\cup\{v\}\); (2) aggregation, \(\mathbf{h}_v^{(l)}=\mathrm{AGG}^{(l)}(\{\mathbf{m}_u^{(l)},u\in N(v)\},\mathbf{m}_v^{(l)})\); plus a non-linearity (activation) \(\sigma(\cdot)\), such as ReLU or sigmoid, that adds expressiveness. It can be applied in the message step or in the aggregation step.

Slide 21 lists activation functions, each applied to the \(i\)-th dimension of the embedding \(\mathbf{x}\) separately:

• ReLU: \(\mathrm{ReLU}(\mathbf{x}_i)=\max(\mathbf{x}_i,0)\). The most commonly used. Plot: flat at 0 for negative inputs, the line \(y=x\) for positive.
• Sigmoid: \(\sigma(\mathbf{x}_i)=1/(1+e^{-\mathbf{x}_i})\). Use it only when you want to restrict the range of the embeddings (its output lies in \((0,1)\)).
• Parametric ReLU: \(\mathrm{PReLU}(\mathbf{x}_i)=\max(\mathbf{x}_i,0)+a_i\min(\mathbf{x}_i,0)\), where \(a_i\) is a trainable slope for negative inputs (plot: \(y=x\) on the right, \(y=ax\) on the left). Empirically it performs better than ReLU.

Why concatenation and not just summation? \(\mathrm{CONCAT}(\mathbf{a},\mathbf{b})\) keeps "what my neighbours say" and "what I am" in separate coordinates, so the next linear layer can weigh them differently. Summation \(\mathbf{a}+\mathbf{b}\) mixes them into one vector — cheaper, but less flexible.

Slide 22 recalls the Graph Convolutional Network layer (Kipf and Welling, ICLR 2017):

How do we write it as message + aggregation? Move \(\mathbf{W}^{(l)}\) inside the sum (it is linear, so this changes nothing):

Slide 23 spells out the two parts:

• Message: each neighbour sends \(\mathbf{m}_u^{(l)}=\frac{1}{|N(v)|}\mathbf{W}^{(l)}\mathbf{h}_u^{(l-1)}\), i.e. its transformed embedding normalised by the node degree. (The GCN paper uses a slightly different normalisation.)
• Aggregation: sum the messages from the neighbours, then apply the activation: \(\mathbf{h}_v^{(l)}=\sigma\big(\mathrm{Sum}(\{\mathbf{m}_u^{(l)},u\in N(v)\})\big)\).

Where did the self term \(\mathbf{B}\mathbf{h}_v\) of Lecture 3 go? The slide answers: in GCN the input graph is assumed to have self-edges, which are included in the summation. So \(v\in N(v)\), and the node's own vector enters as one of the "neighbour" messages, with the same weight matrix \(\mathbf{W}^{(l)}\).

For reference, the original paper's normalisation is symmetric: the message from \(u\) to \(v\) is scaled by \(1/\sqrt{\tilde d_u\tilde d_v}\), where \(\tilde d\) counts the self-loop. Edges between two hubs get down-weighted.

Slide 24 introduces GraphSAGE (Hamilton et al., "Inductive Representation Learning on Large Graphs", NeurIPS 2017):

It is a two-stage aggregation:

1. Stage 1 — aggregate from the neighbours: \(\mathbf{h}_{N(v)}^{(l)}\leftarrow\mathrm{AGG}(\{\mathbf{h}_u^{(l-1)},\forall u\in N(v)\})\).
2. Stage 2 — further aggregate over the node itself: \(\mathbf{h}_v^{(l)}\leftarrow\sigma\big(\mathbf{W}^{(l)}\cdot\mathrm{CONCAT}(\mathbf{h}_v^{(l-1)},\mathbf{h}_{N(v)}^{(l)})\big)\).

In message + aggregation language, the message is computed inside AGG\((\cdot)\). Slide 25 lists three choices of AGG and marks, in each formula, which part is the message and which part is the aggregation:

• Mean — a weighted average of neighbours: \(\mathrm{AGG}=\sum_{u\in N(v)}\frac{\mathbf{h}_u^{(l-1)}}{|N(v)|}\). Message = \(\mathbf{h}_u/|N(v)|\); aggregation = the sum.
• Pool — transform each neighbour vector, then apply a symmetric vector function such as Mean or Max: \(\mathrm{AGG}=\mathrm{Mean}(\{\mathrm{MLP}(\mathbf{h}_u^{(l-1)}),\forall u\in N(v)\})\). Message = the MLP; aggregation = the mean (or max).
• LSTM — apply an LSTM to a reshuffled list of neighbours: \(\mathrm{AGG}=\mathrm{LSTM}([\mathbf{h}_u^{(l-1)},\forall u\in\pi(N(v))])\), where \(\pi\) is a random permutation. Here the LSTM is the whole aggregation.

Slide 26: \(\ell_2\) normalisation, optional, applied to \(\mathbf{h}_v^{(l)}\) at every layer:

Without it, embedding vectors can have very different scales (\(\ell_2\)-norms). After it, all vectors have the same norm (they lie on the unit sphere). In some cases, but not always, this improves performance.

Slide 27 writes the Graph Attention Network (GAT) layer:

where \(\alpha_{vu}\) are attention weights. Slide 28 writes the same thing in message form, \(\mathbf{h}_v^{(l)}=\sigma(\sum_{u\in N(v)}\alpha_{vu}\mathbf{m}_u^{(l)})\).

Compare with GCN and GraphSAGE (slides 27–28). There, \(\alpha_{vu}=\frac{1}{|N(v)|}\) is the weighting factor (importance) of \(u\)'s message to \(v\). Two consequences:

• \(\alpha_{vu}\) is defined explicitly, from a structural property of the graph (the node degree);
• so all neighbours \(u\in N(v)\) are equally important to node \(v\).

Slide 29 argues that this is wrong in general: not all of a node's neighbours are equally important. Attention is inspired by cognitive attention. The weight \(\alpha_{vu}\) should focus on the important parts of the input and fade out the rest. The idea: the network should devote more computing power to the small but important part of the data. Which part is important depends on the context, and it is learned through training.

Slide 30 (citing Veličković et al., ICLR 2018, and Vaswani et al., NeurIPS 2017) poses the question: can we do better than simple neighbourhood aggregation — can the weighting factors \(\alpha_{vu}\) be learned? Goal: specify an arbitrary importance for each neighbour of each node. Idea: compute each node's embedding \(\mathbf{h}_v^{(l)}\) with an attention strategy: nodes attend over their neighbourhoods' messages, which implicitly gives different weights to different nodes in a neighbourhood.

A social-network example: to predict a user's political leaning, a few close friends may tell you more than hundreds of brand accounts the user follows. Mean aggregation gives the brands most of the weight, simply because there are more of them.

Let \(\alpha_{vu}\) be a by-product of an attention mechanism \(a\).

Step 1 — attention coefficients (slides 31–32). The function \(a\) computes a raw score \(e_{vu}\) for each pair of nodes, based on their messages:

\(e_{vu}\) indicates the importance of \(u\)'s message to node \(v\). The figure shows node A and its neighbour B with the edge labelled \(e_{AB}=a(\mathbf{W}^{(l)}\mathbf{h}_A^{(l-1)},\mathbf{W}^{(l)}\mathbf{h}_B^{(l-1)})\).

Step 2 — normalise with softmax (slide 33), so that the weights over each neighbourhood sum to 1:

Step 3 — weighted sum: \(\mathbf{h}_v^{(l)}=\sigma\big(\sum_{u\in N(v)}\alpha_{vu}\mathbf{W}^{(l)}\mathbf{h}_u^{(l-1)}\big)\). For node A with neighbours B, C, D (figure):

What is \(a\)? (slide 34) The approach is agnostic to the choice. A simple option is a single-layer neural network with trainable weights: concatenate the two transformed vectors and apply a linear layer,

The parameters of \(a\) are trained jointly with the weight matrices \(\mathbf{W}^{(l)}\), end to end.

Multi-head attention (slide 35) stabilises the learning of attention. Create several attention scores, each replica with its own parameters: \(\mathbf{h}_v^{(l)}[1],\mathbf{h}_v^{(l)}[2],\mathbf{h}_v^{(l)}[3]\), each computed with its own weights \(\alpha_{vu}^{1},\alpha_{vu}^{2},\alpha_{vu}^{3}\). Then aggregate the outputs, by concatenation or summation: \(\mathbf{h}_v^{(l)}=\mathrm{AGG}(\mathbf{h}_v^{(l)}[1],\mathbf{h}_v^{(l)}[2],\mathbf{h}_v^{(l)}[3])\).

Benefits (slide 36):

• Key benefit: implicitly specifies different importance values \(\alpha_{vu}\) for different neighbours.
• Computationally efficient: attention coefficients can be computed in parallel across all edges; aggregation can be parallelised across all nodes.
• Storage efficient: sparse matrix operations need at most \(O(V+E)\) stored entries; the number of parameters is fixed, independent of graph size.
• Localised: attends only over local network neighbourhoods.
• Inductive: a shared, edge-wise mechanism that does not depend on the global graph structure.

Check yourself: raw scores \(e_{AB}=2, e_{AC}=e_{AD}=0\). Then \(\alpha_{AB}=e^2/(e^2+2)\approx0.79\), and C, D get about 0.11 each. Why does softmax over neighbours only (not over all nodes) matter for the cost?

Slide 38 (again from the Design Space paper): the classic layers are a great starting point, but we can often get better performance with a general GNN layer design that includes modern deep-learning modules proven useful in many domains. The figure shows "a suggested GNN layer" as a vertical pipeline: Linear → BatchNorm → Dropout → Activation → Attention → Aggregation. The first five boxes form the transformation (the message); the last is the aggregation.

Slide 39 lists what each module does:

• Batch normalisation — stabilises neural network training.
• Dropout — prevents overfitting.
• Attention / gating — controls the importance of a message.
• More — any other useful deep-learning module.

Slide 40 explains batch normalisation (Ioffe and Szegedy, ICML 2015). Goal: stabilise training. Idea: given a batch of inputs (node embeddings), re-centre them to zero mean and rescale them to unit variance. Input: \(\mathbf{X}\in\mathbb{R}^{N\times D}\) (\(N\) node embeddings of dimension \(D\)). Trainable parameters: \(\boldsymbol{\gamma},\boldsymbol{\beta}\in\mathbb{R}^{D}\). Output: \(\mathbf{Y}\in\mathbb{R}^{N\times D}\), the normalised embeddings.

Step 1 — mean and variance of each dimension \(j\) over the \(N\) embeddings:

Step 2 — normalise, then rescale and shift with the learned parameters:

The small \(\epsilon\) avoids division by zero. Why learn \(\boldsymbol{\gamma},\boldsymbol{\beta}\)? Forcing every dimension to mean 0 and variance 1 may remove useful information; the learned scale and shift let the network undo the normalisation where that helps.

Slide 41 explains dropout (Srivastava et al., JMLR 2014). Goal: regularise a neural network to prevent overfitting. Idea:

• During training: with some probability \(p\), randomly set neurons to zero (turn them off). The figure shows a fully connected network and, after dropout, the same network with some neurons crossed out ("removed neurons") together with their connections.
• During testing: use all neurons for the computation.

Intuition: since any neuron may disappear, the network cannot rely on one fragile combination of features; it must spread the information. This acts like training many thinned networks and averaging them.

Slide 42: in a GNN, dropout is applied to the linear layer in the message function. For the simple message \(\mathbf{m}_u^{(l)}=\mathbf{W}^{(l)}\mathbf{h}_u^{(l-1)}\), the figure visualises \(\mathbf{W}^{(l)}\) as the connections between input units \(\mathbf{h}_u^{(l-1)}\) and output units \(\mathbf{m}_u^{(l)}\), and dropout removes some of those units during training.

Slide 43 summarises: modern deep-learning modules can be included in a GNN layer for better performance (the figure repeats the Linear → BatchNorm → Dropout → Activation → Attention → Aggregation stack). Designing novel GNN layers is still an active research frontier. Suggested resource: GraphGym, where you can explore diverse GNN designs or try out your own ideas.

Implementation detail you will meet in PyTorch: frameworks use "inverted dropout", scaling the kept units by \(1/(1-p)\) during training, so nothing needs to change at test time. Remember to call model.eval() before evaluation, or dropout stays on.

Slide 45 turns to part 3, layer connectivity: how to connect GNN layers into a GNN — stack them sequentially, or add skip connections. Slide 46 gives the standard way: stack GNN layers one after another. Input: the raw node feature \(\mathbf{x}_v\), so \(\mathbf{h}_v^{(0)}=\mathbf{x}_v\). Output: the node embeddings \(\mathbf{h}_v^{(L)}\) after \(L\) GNN layers. The figure: \(\mathbf{h}^{(0)}\to\) GNN layer \(\to\mathbf{h}^{(1)}\to\) GNN layer \(\to\mathbf{h}^{(2)}\to\) GNN layer \(\to\mathbf{h}^{(3)}\).

Slide 47 names the problem with stacking many layers: over-smoothing — all node embeddings converge to the same value. This is bad because we use embeddings precisely to differentiate nodes. Why does it happen?

Slide 48 defines the receptive field: the set of nodes that determine the embedding of a node of interest. In a \(K\)-layer GNN, each node's receptive field is its \(K\)-hop neighbourhood. The figure shows one node in a random graph and its receptive field (in red) for 1, 2 and 3 layers; by 3 layers most of the graph is red.

Slide 49 looks at the overlap of the receptive fields of two nodes (yellow), with shared neighbours in red. The shared neighbours grow quickly with the number of hops:

• 1-hop overlap: only 1 node;
• 2-hop overlap: about 20 nodes;
• 3-hop overlap: almost all the nodes.

Slide 50 explains over-smoothing through this lens. The embedding of a node is determined by its receptive field. If two nodes have highly overlapping receptive fields, their embeddings are highly similar. So: stack many GNN layers → nodes have highly overlapping receptive fields → node embeddings are highly similar → over-smoothing. Next question: how to overcome it?

Check yourself: in a social network with a small diameter (say 5–6), roughly how many layers does it take before every node's receptive field is the whole graph?

Slide 51 draws the first lesson from over-smoothing: be cautious when adding GNN layers. Unlike neural networks in other domains (for example CNNs for image classification), adding more GNN layers does not always help.

1. Step 1: analyse the receptive field needed to solve your problem, for example by computing the diameter of the graph.
2. Step 2: set the number of GNN layers \(L\) to be a bit more than the receptive field you want. Do not make \(L\) unnecessarily large.

Then the question: how do we make a GNN expressive if the number of GNN layers is small? Two solutions.

Solution 1 (slide 52): increase the expressive power within each GNN layer. In the examples so far, each transformation or aggregation contained just one linear layer. We can make the aggregation and the transformation themselves deep neural networks — "if needed, each box could include a 3-layer MLP". The receptive field stays the same (it depends only on the number of message-passing rounds), but each round can compute a more complex function.

Solution 2 (slide 53): add layers that do not pass messages. A GNN need not consist only of GNN layers. We can add MLP layers, applied to each node separately, before and after the GNN layers:

• Pre-processing layers — important when encoding the node features is necessary, e.g. when nodes represent images or text.
• Post-processing layers — important when reasoning or transformation over node embeddings is needed, e.g. graph classification or knowledge graphs.

The slide's verdict: in practice, adding these layers works great.

Why do MLP layers not cause over-smoothing? They act on each node independently: they never mix information between nodes, so they cannot make different nodes more alike.

Slide 54: what if the problem still requires many GNN layers? Lesson 2: add skip connections. The observation from over-smoothing: embeddings in earlier GNN layers can sometimes differentiate nodes better. Solution: increase the impact of earlier layers on the final embeddings by adding shortcuts. The figure (from He et al., ResNets, CVPR 2015) shows the input \(\mathbf{x}\) duplicated into two branches; one goes through the layers to give \(F(\mathbf{x})\), the other skips them (identity), and the two are summed. Before the shortcut the block outputs \(F(\mathbf{x})\); after, \(F(\mathbf{x})+\mathbf{x}\).

Slide 55: why do skip connections work? Intuition: they create a mixture of models. With \(N\) skip connections there are \(2^N\) possible paths, since at each block a signal can either go through the module or skip it. Each path has up to \(N\) modules. So we automatically get a mixture of shallow and deep GNNs. The figure (Veit et al., 2016) unrolls a 3-block residual network into all \(2\cdot2\cdot2=2^3=8\) paths, from the empty path to the path through \(f_1,f_2,f_3\).

Slide 56 applies this to the GCN. The standard GCN layer is our \(F(\mathbf{x})\):

and the GCN layer with a skip connection adds \(\mathbf{x}=\mathbf{h}_v^{(l-1)}\) inside the activation:

The side figure shows where skips can go in a full model: around the GNN layers, between the pre-process and post-process MLP layers.

Slide 57 (Xu et al., "Jumping Knowledge Networks", ICML 2018) gives another option: skip directly to the last layer. The final layer aggregates from all the node embeddings of the previous layers: \(\mathbf{h}_v^{(0)}\) (input), \(\mathbf{h}_v^{(1)},\mathbf{h}_v^{(2)},\mathbf{h}_v^{(3)}\) all feed into a "layer aggregation" box (concat, pooling or LSTM), which outputs \(\mathbf{h}_v^{(\text{final})}\). Each node can then use the receptive-field size that suits it.