Graph Neural Networks

The lecture starts from where Lecture 2 ended. Slide 3 restates the goal of node embedding: learn a map \(f\) that sends every node to a point in \(\mathbb{R}^d\) so that nodes that are similar in the graph land close together. The picture shows a messy input graph on the left and a 2D scatter of node embeddings on the right, with the question "how do we learn \(f\)?".

Slide 4 recalls the encoder–decoder view: an encoder \(\mathrm{ENC}(u)=\mathbf{z}_u\) maps each node into the embedding space, and we want

where the similarity function is something we "need to define" (random walks, adjacency, and so on). Slide 5 shows the simplest encoder, the shallow one: \(\mathbf{Z}\) is a \(d\times|V|\) matrix with one column per node, and encoding a node is just looking up its column.

Slide 6 lists the three problems with this lookup table:

1. \(O(|V|d)\) parameters. Nothing is shared between nodes; every node owns its own vector. A graph with a billion nodes needs a billion vectors.
2. Inherently transductive. A node that was not present during training has no column, so it gets no embedding. You must retrain.
3. No node features. Many graphs carry rich attributes (a user's profile, a protein's sequence). The lookup table ignores them.

Slide 7 announces the fix for today: replace the lookup by a deep graph encoder, \(\mathrm{ENC}(v)=\) "multiple layers of non-linear transformations based on graph structure". Importantly, the decoder and similarity side of Lecture 2 stays the same: any of these deep encoders can be combined with the node-similarity functions from Lecture 2.

Check yourself: which of the three limits does weight sharing fix, and which does using \(\mathbf{x}_v\) as input fix?

Slide 8 sketches the architecture we are aiming for: the input graph passes through a stack of "graph convolution" layers, each followed by an activation function and regularisation (for example dropout), and the output is a node embedding for every node. The callout adds that we can also embed subgraphs and whole graphs (by pooling node embeddings).

Slide 9 lists what such embeddings let us do:

• Node classification — predict the type of a given node.
• Link prediction — predict whether two nodes are linked.
• Community detection — identify densely linked clusters of nodes.
• Network similarity — measure how similar two (sub)networks are.

Slide 10 makes the main point of the motivation: the modern deep-learning toolbox (CNNs, RNNs, Transformers) is designed for simple sequences and grids. An image is a regular 2D grid of pixels; text or speech is a 1D line of tokens.

Slide 11 explains why networks break this toolbox. The figure puts a tangled network next to a pixel grid and a text chain. Networks are far more complex:

• Arbitrary size and complex topology — there is no spatial locality like a grid; one node may have 2 neighbours, another 2,000.
• No fixed node ordering or reference point — there is no "top-left pixel" or "first word".
• Often dynamic (nodes and edges appear and disappear) and with multimodal features (text, images, numbers attached to nodes).

The second bullet is the deep one: almost the whole first half of the lecture is about how to build a network that does not depend on an arbitrary node order.

Slide 13 is a one-slide summary of deep learning (the full refresher is at the end of the deck, slides 74–88). Training means solving

where \(f\) can be a linear layer, an MLP, or another network — later, a GNN. The loop is: sample a minibatch of inputs \(\mathbf{x}\); run forward propagation to compute \(\mathcal{L}\); run back-propagation to get \(\nabla_{\Theta}\mathcal{L}\) by the chain rule; update \(\Theta\) with stochastic gradient descent; repeat for many iterations.

Slide 15 gives the plan for the "deep learning for graphs" part: first, local network neighbourhoods (aggregation strategies, computation graphs); then, stacking multiple layers (the model, its parameters, how to fit it, with simple supervised and unsupervised examples).

Slide 16 fixes notation used for the rest of the course:

• \(V\): the vertex set; \(A\): the adjacency matrix (assume binary).
• \(X\in\mathbb{R}^{|V|\times m}\): the matrix of node features (row \(v\) is the \(m\)-dimensional feature vector \(\mathbf{x}_v\)).
• \(v\): a node in \(V\); \(N(v)\): the set of neighbours of \(v\).

Examples of node features: in social networks, the user profile and user image; in biological networks, gene expression profiles and gene functional information. When a dataset has no node features, two standard choices are (a) indicator vectors (a one-hot encoding of each node) or (b) a vector of constant 1, \([1,1,\dots,1]\).

The two choices behave very differently. One-hot features make the model as expressive as a lookup table, but it becomes transductive again (a new node has no one-hot slot). Constant features keep it inductive, but then the GNN can only use graph structure to tell nodes apart.

Slide 17 tries the obvious idea. Write the 5-node example graph's adjacency matrix and append the feature column, giving one row per node of \([A, X]\). Feed these rows into a fully connected deep network. Done?

No. The slide lists three issues:

1. \(O(|V|)\) parameters. The input layer has one weight per column, and there is one column per node.
2. Not applicable to graphs of different sizes. A 6-node graph has a longer input row than the network was built for.
3. Sensitive to node ordering. Swap the labels of two nodes and the rows and columns of \(A\) move; the network sees a different input and gives a different answer, although the graph is the same.

Slide 18 recalls how a CNN works on an image: a small filter (for example \(3\times3\)) slides over the pixel grid, and the same weights are applied at every position. A stack of such layers (convolution, subsampling, more convolutions, fully connected output) builds features of growing scope. The goal stated on the slide: generalise convolutions beyond simple lattices, and leverage node features (text, images).

Slide 19 shows the obstacle: "but our graphs look like this" — irregular graphs with a box marking a would-be "window". Two facts block a direct copy of the CNN:

• There is no fixed notion of locality or sliding window on the graph: neighbourhoods differ in size and shape.
• Graphs are permutation invariant: the node labels are arbitrary, so the answer must not depend on them.

Slide 20 starts with the task of embedding an entire graph. The key observation: a graph does not have a canonical ordering of its nodes. The same graph can be written with many different node orderings, and we want the learned embedding to be the same no matter how the nodes are numbered.

Slides 21–23 make this concrete with a 6-node graph A–F. Under "Order 1" the feature matrix \(X_1\) has rows A, B, …, F (each row drawn as a coloured bar), and the adjacency matrix \(A_1\) is a \(6\times6\) grid of shaded cells. Under "Order 2" the same graph is relabelled: the node that was A is now called something else, so the rows of \(X_2\) appear in a different colour order and the shaded pattern of \(A_2\) is shuffled. Slide 23's green callout states the requirement: the learned graph representation should be the same for Order 1 and Order 2.

Slide 24 formalises it. If \(f\) maps a graph \(G=(A,X)\) to a vector in \(\mathbb{R}^d\), then we need \(f(A_1,X_1)=f(A_2,X_2)\).

Slide 25 gives the definition. Relabelling the nodes is a permutation matrix \(P\) (a shuffle of the node order; example: \((A,B,C)\to(B,C,A)\)). It reorders the rows of \(X\) to \(PX\), and both the rows and the columns of \(A\) to \(PAP^{\top}\). A graph with \(|V|\) nodes has \(|V|!\) orderings.

Here \(m\) is the feature dimension and \(d\) the output (graph-embedding) dimension.

Why \(PAP^\top\) and not \(PA\)? Entry \((i,j)\) of \(A\) says "node \(i\) links to node \(j\)". Renaming nodes must rename both the row index and the column index, so we permute rows (left multiply by \(P\)) and columns (right multiply by \(P^\top\)).

For node representations, \(f\) maps a graph to a matrix in \(\mathbb{R}^{|V|\times d}\): one \(d\)-dimensional embedding per node (slide 26). Now we cannot ask the output to stay identical under relabelling, because the rows are listed in the new order. What we want instead is shown on slides 27–28: take the brown node (called A in Order 1 and E in Order 2) — its embedding vector must be the same in both cases; likewise for the green node (C in Order 1, D in Order 2). In words: the vector of the node at the same position in the graph is the same; only its row index changes.

Slide 29 gives the definition:

Slide 30 summarises both ideas and proves three examples:

• Invariant (graph → vector): permute the input, the output stays the same.
• Equivariant (graph → matrix): permute the input, the output is permuted in the same way.
• \(f(A,X)=\mathbf{1}^{\top}X\) is invariant: \(f(PAP^\top,PX)=\mathbf{1}^\top PX=\mathbf{1}^\top X\), because \(\mathbf{1}^\top P=\mathbf{1}^\top\) (summing all rows does not care about their order).
• \(f(A,X)=X\) is equivariant: \(f(PAP^\top,PX)=PX=Pf(A,X)\).
• \(f(A,X)=AX\) is equivariant: \(f(PAP^\top,PX)=PAP^\top PX=PAX=Pf(A,X)\), using \(P^\top P=I\) (permutation matrices are orthogonal).

Slide 31 (after Bronstein's ICLR 2021 keynote) states the structural principle: graph neural networks consist of multiple permutation equivariant / invariant functions. The figure shows the graph passing through several equivariant layers (yellow labels), each producing new node vectors on the same graph, and finally an invariant layer (blue label) that collapses everything to a single point — a graph-level output.

Slide 32 asks whether other architectures, for example MLPs, have this property. Answer: no. The figure shows the same three input numbers fed into an MLP in three different orders; the outputs differ. Switching the order of the input changes the output.

Slides 33–34 connect this to the naive approach of slide 17: this is exactly why feeding \([A,X]\) into an MLP fails for graphs — the MLP is neither invariant nor equivariant, and it also has a huge number of parameters and no inductive ability. Slide 34's green box gives the plan for the rest of the lecture: design graph neural networks that are permutation invariant / equivariant by passing and aggregating information from neighbours.

Slide 36 introduces Graph Convolutional Networks (Kipf and Welling, ICLR 2017). The idea in one sentence: a node's neighbourhood defines a computation graph. The left picture shows a target node \(i\) with rings at distance \(k=1\) and \(k=2\) (step "determine node computation graph"); the right picture shows information flowing along the edges towards \(i\) through two aggregators (step "propagate and transform information"). The goal: learn how to propagate information across the graph to compute node features.

Slide 37: the key idea is to generate node embeddings based on local network neighbourhoods. In the figure, target node A has neighbours B, C, D. To compute A, we take the vectors coming from B, C and D into a grey box; each of those is itself computed from its own neighbours (for example B from A and C; C from A, B, E, F; D from A).

Slide 38: nodes aggregate information from their neighbours using neural networks — every grey box is a small neural network.

Slide 39: every node defines its own computation graph based on its neighbourhood. The figure draws six different trees, one per node of the input graph. They have different shapes because the nodes have different neighbourhoods.

Slide 40: the model can be of arbitrary depth:

• Nodes have embeddings at each layer.
• The layer-0 embedding of node \(v\) is its input feature \(\mathbf{x}_v\).
• The layer-\(k\) embedding gets information from nodes that are \(k\) hops away.

In the slide 40 tree for A: layer 2 is A itself; layer 1 is B, C, D; layer 0 holds the input features of their neighbours (\(\mathbf{x}_A,\mathbf{x}_C\) under B; \(\mathbf{x}_A,\mathbf{x}_B,\mathbf{x}_E,\mathbf{x}_F\) under C; \(\mathbf{x}_A\) under D). Note that A appears among its own leaves: the tree is an unrolling, and nodes repeat.

Depth here means the number of message-passing rounds, not the depth of the network inside each box. A 2-layer GNN sees exactly the 2-hop neighbourhood, however deep its inner MLPs are.

Slide 41: different GNN models differ mainly in how they aggregate information across layers — "what is in the box?" Slide 42 gives the basic answer: (1) average the messages from neighbours, then (2) apply a neural network.

Slide 43 writes the full model (the "deep encoder"):

The annotations: \(\mathbf{h}_v^{(k)}\) is the embedding of \(v\) at layer \(k\); the fraction is the average of the neighbours' previous-layer embeddings; \(\sigma\) is a non-linearity (for example ReLU); \(K\) is the total number of layers; \(\mathbf{z}_v\) is the embedding after \(K\) layers of neighbourhood aggregation. The slide stresses that the summation (here, the average) is a permutation-invariant aggregation: the order of the neighbours does not matter.

Slides 44–46 check the symmetry of the whole GCN:

• For one node (slide 44), the GCN that computes its embedding is invariant: the target node's tree uses shared weights, and the neighbour average does not care how the neighbours are ordered.
• Over all nodes (slide 45), GCN computation is equivariant. The figure shows Order 1 and Order 2 of the graph, with feature matrices, adjacency matrices and output embedding matrices \(H_1, H_2\); the target node's row moves, but its colour (its vector) is the same.

Slide 46 spells out the argument in three steps: (1) the rows of the input features and of the output embeddings are aligned (row \(i\) in, row \(i\) out); (2) computing one node's embedding is invariant; (3) so after a permutation, a node's input row moves to a new position, and its output embedding — unchanged by step 2 — moves to the same position. That is equivariance.

Check yourself: replace the mean by "the first neighbour in the list". Which step of the argument breaks?

Slide 47 asks: how do we train the GCN to produce embeddings \(\mathbf{z}_A\)? We need a loss function on the embeddings.

Slide 48 repeats the update rule and highlights what is learned: the trainable weight matrices \(\mathbf{W}_k\) (for neighbourhood aggregation) and \(\mathbf{B}_k\) (for transforming the node's own hidden vector). \(\mathbf{h}_v^{(k)}\) is the hidden representation of \(v\) at layer \(k\), and \(\mathbf{z}_v=\mathbf{h}_v^{(K)}\) is the final embedding. We can feed these embeddings into any loss function and run SGD to train the weights.

Slide 49 shows that many aggregations are just (sparse) matrix operations. Stack the embeddings as rows: \(H^{(k)}=[\mathbf{h}_1^{(k)}\dots\mathbf{h}_{|V|}^{(k)}]^{\top}\). Then

because row \(v\) of \(A\) has ones exactly at the neighbours of \(v\). Let \(D\) be the diagonal degree matrix, \(D_{v,v}=\deg(v)=|N(v)|\); its inverse is diagonal with \(D^{-1}_{v,v}=1/|N(v)|\). Therefore the neighbour average for all nodes at once is

Slide 50 rewrites the full update:

The red term \(\tilde A H^{(k)} W_k^\top\) is neighbourhood aggregation; the blue term \(H^{(k)}B_k^\top\) is self-transformation. The small figure shows red arrows from neighbours and a blue self-loop on the centre node. Since \(\tilde A\) is sparse, efficient sparse matrix multiplication can be used. Caveat on the slide: not all GNNs can be written in such a simple matrix form when the aggregation function is complex (for example attention or max).

Why \(W_k^\top\)? Each row of \(H\) is a row vector \(\mathbf{h}^\top\), and \((\mathbf{W}\mathbf{h})^\top=\mathbf{h}^\top\mathbf{W}^\top\).

Slide 51: the node embedding \(\mathbf{z}_v\) is a function of the input graph (and the weights). Two settings:

• Supervised: minimise \(\min_\Theta \mathcal{L}(\mathbf{y}, f_\Theta(\mathbf{z}_v))\), where \(\mathbf{y}\) is a node label. \(\mathcal{L}\) can be L2 if \(y\) is a real number, or cross entropy if \(y\) is categorical.
• Unsupervised: no node labels are available, so use the graph structure as the supervision.

Slide 52 gives one unsupervised idea: "similar" nodes should have similar embeddings,

where \(y_{u,v}=1\) when \(u\) and \(v\) are similar, \(\mathbf{z}_u=f_\Theta(u)\), and DEC is the dot product. The cross-entropy loss is \(\mathrm{CE}(\mathbf{y},f(\mathbf{x}))=-\sum_{i=1}^{C}y_i\log f_\Theta(\mathbf{x})_i\), with \(y_i\) and \(f_\Theta(\mathbf{x})_i\) the true and predicted values for class \(i\); the lower the loss, the closer the prediction is to the one-hot label. "Similar" can be anything from Lecture 2: random walks (node2vec, DeepWalk, struc2vec) or matrix factorisation. So DeepWalk with a GNN encoder is a valid model.

Slides 53–54 show the supervised case on an example: a drug–drug interaction network, where we want to classify each drug as "safe or toxic". Each drug's computation tree produces \(\mathbf{z}_v\), and the binary cross-entropy loss is

Slide 54 labels the parts: \(\mathbf{z}_v\) is the encoder output (node embedding), \(\theta\) are the classification weights, \(y_v\) is the node class label. The GNN weights and \(\theta\) are trained together, end to end.

Slides 55–57 summarise how to build and use a GNN, with a figure that grows step by step:

1. Define a neighbourhood aggregation function (what is in the box).
2. Define a loss function on the embeddings \(\mathbf{z}_A\).
3. Train on a set of nodes, i.e. a batch of compute graphs (slide 56 shows three trees inside a pink box: the training nodes).
4. Generate embeddings for nodes as needed — even for nodes we never trained on (slide 57 adds a blue box with new trees next to the training ones).

Slide 58 explains why step 4 works: the same aggregation parameters \(W_k, B_k\) are shared by all nodes. The figure shows the compute graph of node A and of node B; the boxes on the same level of both trees use the same "shared parameters". Consequence: the number of model parameters is sublinear in \(|V|\) (in fact independent of it), and we can generalise to unseen nodes.

Two kinds of inductive use:

• New graphs (slide 59): train on one graph, generalise to an entirely unseen graph. Example: train on the protein interaction graph of model organism A and compute embeddings for newly collected data about organism B.
• New nodes (slide 60): train with a snapshot; a new node arrives; compute its embedding. Reddit, YouTube and Google Scholar encounter new nodes all the time and need embeddings "on the fly", without retraining.

Slides 61–62 advertise GNN 101 (visual-intelligence-umn.github.io/GNN-101), a browser tool that visualises a GNN's inner workings at several levels of detail. Parameters are shown as heatmaps, the computation is animated, and hovering over a term in an equation highlights the matching part of the picture. Other functions: switch between GNN variants and tasks, and toggle between a node-link subgraph view and an adjacency-matrix view.

Inductive does not mean free: a new node's embedding still depends on its neighbours' features, so a node with no edges and no features gets an uninformative embedding.

Slide 64 asks how GNNs compare with Convolutional Neural Networks. Slide 65 shows a CNN layer with a \(3\times3\) filter sliding over an image (animation by Vincent Dumoulin) and writes it as

where \(N(v)\) is the set of 8 neighbour pixels of \(v\). Slide 66 draws the same pixel as a node in a graph with 8 neighbours plus a self-loop, and puts the two formulas side by side:

Slide 67 names the key difference: a CNN can learn a different weight \(\mathbf{W}_l^{\,u}\) for each neighbour \(u\) of pixel \(v\), because pixels can be put in a fixed order by their position relative to the centre: \(\{(-1,-1),(-1,0),(-1,1),\dots,(1,1)\}\). A graph has no such reference frame, so the GNN must use one shared \(\mathbf{W}_l\) and an order-free aggregation.

Slide 68 draws the conclusion:

• A CNN is a special GNN with fixed neighbour size and ordering. The size of the filter is pre-defined in a CNN; the advantage of a GNN is that it processes arbitrary graphs where each node has a different degree.
• A CNN is not permutation invariant/equivariant: switching the order of pixels leads to different outputs. On an image this is a feature, not a bug — "left of" really means something.

Slide 69 introduces the Transformer (Vaswani et al., "Attention is all you need", NeurIPS 2017), one of the most popular architectures for sequence modelling. Its key component is self-attention: every token attends to all the other tokens via matrix calculations. The figure shows the sentence "I am a Stanford student" with curved arrows from each word to every other word.

Slide 70 defines attention in general: given a set of vector values and a vector query, attention computes a weighted sum of the values, dependent on the query. Each token has a value vector (its representation) and a query vector (used to compute the attention scores, i.e. the weights in the sum). The figure shows two sentences, "The animal didn't cross the street because it was too tired" and "… too wide". In the first, the word "it" puts most attention on "animal"; in the second, on "street". The weights depend on the content, not on a fixed position.

Slide 71 gives the punchline: a Transformer layer is a special GNN that runs on a fully connected "word" graph. Since each word attends to all other words, the computation graph of a Transformer layer is identical to that of a GNN on the complete graph whose nodes are the words, with attention scores as the (learned, data-dependent) aggregation weights. A blog post explaining this is linked on the slide.

Slide 72 summarises the lecture:

• Deep learning for graphs: multiple layers of embedding transformation; at every layer, the embedding from the previous layer is the input; each layer aggregates neighbour and self embeddings.
• Graph Convolutional Network: mean aggregation; can be expressed in matrix form.
• GNN is a general architecture: a CNN can be viewed as a special GNN (and so can a Transformer).

The last part of the deck is a deep-learning refresher. Slide 74: in supervised learning we are given an input \(\mathbf{x}\) and want to predict a label \(\mathbf{y}\). The input can be a vector of real numbers, a sequence (natural language), a matrix (images), or a graph (possibly with node and edge features). We formulate the task as an optimisation problem.

Slide 75: \(\min_\Theta \mathcal{L}(\mathbf{y},f(\mathbf{x}))\) is the objective function. \(\Theta\) is the set of parameters (scalars, vectors, matrices; for example \(\Theta=\{Z\}\) in the shallow encoder). \(\mathcal{L}\) is the loss, for example the L2 loss \(\mathcal{L}(\mathbf{y},f(\mathbf{x}))=\lVert\mathbf{y}-f(\mathbf{x})\rVert_2\); others include L1, Huber, max-margin (hinge) and cross entropy.

Slide 76 works through cross entropy for classification. The label is one-hot, e.g. \(\mathbf{y}=(0,0,1,0,0)\) for class 3. The model outputs probabilities with a softmax, \(f(\mathbf{x})_i=e^{g(\mathbf{x})_i}/\sum_{j=1}^{C}e^{g(\mathbf{x})_j}\), e.g. \(f(\mathbf{x})=(0.1,0.3,0.4,0.1,0.1)\). Then

over the training set \(\mathcal{T}\). In the example only the class-3 term survives, giving \(-\log 0.4\).

Slide 77: the gradient \(\nabla_\Theta\mathcal{L}=(\partial\mathcal{L}/\partial\Theta_1,\partial\mathcal{L}/\partial\Theta_2,\dots)\) is the directional derivative in the direction of largest increase. Slide 78: gradient descent repeats \(\Theta\leftarrow\Theta-\eta\nabla_\Theta\mathcal{L}\). One step is an iteration. The learning rate \(\eta\) is a hyperparameter controlling the step size and can change during training (LR scheduling). Ideally we stop when the gradient is 0; in practice we stop when performance on a held-out validation set stops improving.

Slide 79: exact gradients need a sum over the entire dataset, which can have billions of points, so each step is very expensive. SGD instead uses a different random minibatch \(\mathcal{B}\) at each step. Slide 80 defines batch size (number of points per minibatch, e.g. number of nodes for node classification), iteration (one SGD step) and epoch (one full pass over the data; #iterations per epoch = dataset size / batch size). SGD is an unbiased estimator of the full gradient, but there is no guarantee on the rate of convergence, and the learning rate usually needs tuning. Improved optimisers: Adam, Adagrad, Adadelta, RMSprop.

Slide 81: in deep learning \(f\) can be very complex. Start simple with a linear function \(f(\mathbf{x})=W\cdot\mathbf{x}\), \(\Theta=\{W\}\). If \(f\) returns a scalar, \(W\) is a vector and \(\nabla_W f=(\partial f/\partial w_1,\partial f/\partial w_2,\dots)\). If \(f\) returns a vector, \(W\) is a matrix and \(\nabla_W f\) is the Jacobian, with entries \(\partial f_i/\partial w_{jk}\).

Slide 82: to minimise \(\mathcal{L}\) we need its gradient. Back-propagation works because \(\mathcal{L}\) is built from predefined building-block functions \(g(\cdot)\), each with a known derivative \(g'\); we evaluate these derivatives on the minibatch and combine them automatically.

Slide 83 uses the chain rule, \(\frac{df}{dx}=\frac{dg}{dh}\cdot\frac{dh}{dx}\), i.e. \(f'(x)=g'(h(x))\,h'(x)\), on \(f(\mathbf{x})=W_2(W_1\mathbf{x})\) with \(h(\mathbf{x})=W_1\mathbf{x}\) and \(g(\mathbf{z})=W_2\mathbf{z}\); for example \(\nabla_{\mathbf{x}}f=\frac{\partial f}{\partial(W_1\mathbf{x})}\cdot\frac{\partial(W_1\mathbf{x})}{\partial\mathbf{x}}\). Back-propagation = use the chain rule to propagate gradients of intermediate steps and finally get the gradient of \(\mathcal{L}\) with respect to \(\Theta\).

Slides 84–85 give the example of a 2-layer linear network with inputs \(x_1,x_2\). The loss sums the L2 loss over a minibatch: \(\mathcal{L}=\sum_{(\mathbf{x},\mathbf{y})\in\mathcal{B}}\lVert\mathbf{y}-f(\mathbf{x})\rVert_2\). The hidden layer \(h(\mathbf{x})=W_1\mathbf{x}\) is an intermediate representation, and \(f(\mathbf{x})=W_2h(\mathbf{x})\). Forward propagation goes \(\mathbf{x}\to h\) (multiply by \(W_1\)) \(\to g\) (multiply by \(W_2\)) \(\to\mathcal{L}\). Back-propagation starts from the loss and computes backwards:

(The second formula is the slide's shorthand; read it as "reuse \(\partial\mathcal{L}/\partial f\) and push it one more step back through \(W_2\) to the hidden layer, then to \(W_1\)".) The shared factor \(\partial\mathcal{L}/\partial f\) is computed once and reused — that reuse is why back-propagation is efficient.

Slide 86: \(W_2W_1\) is just another matrix, so \(f(\mathbf{x})=W_2W_1\mathbf{x}\) is still linear in \(\mathbf{x}\) no matter how many matrices we stack. We need non-linearity: ReLU \(\mathrm{ReLU}(x)=\max(x,0)\) (plot: zero for negative \(x\), the identity for positive) or the sigmoid \(\sigma(x)=1/(1+e^{-x})\) (an S-shaped curve from 0 to 1).

Slide 87: each layer of a multi-layer perceptron (MLP) combines a linear transformation and a non-linearity, \(\mathbf{x}^{(l+1)}=\sigma(W_l\mathbf{x}^{(l)}+\mathbf{b}^{l})\), where \(W_l\) maps layer \(l\) to layer \(l+1\) and \(\mathbf{b}^{l}\) is the bias. The figure: a 2-dimensional input \((x_1,x_2)\), a 3-dimensional hidden layer, a 1-dimensional output. Slide 88 repeats the full training recipe from slide 13: objective, minibatch, forward pass, back-propagation, SGD over many iterations.

Connection to the GNN: the "neural network in the box" of slide 42 is exactly one such MLP layer, \(\sigma(W\cdot\text{average}+B\cdot\text{self})\). Back-propagation flows through the computation tree of every training node, and the gradients for the shared \(W_k,B_k\) are summed over all the places where they appear.