spb/artificial-neural-networks-book Public
Artificial Neural Networks — Methods, Equations and Graphical Representations: a complete book, every method with rigorous equations, pseudocode and native TikZ figures.
TeX 100%
1% ============================================================================2% Artificial Neural Networks — Methods, Equations and Graphical3% Representations4% Author : Simon-Pierre Boucher — contact@spboucher.ai5% Chapter 8 : Graph Neural Networks (chapters/08-gnn.tex)6% ============================================================================7\chapter{Graph Neural Networks}\label{chap:gnn}89The architectures of the preceding chapters assume that data live on a10regular lattice: images are grids, sequences are chains. A vast portion of11real-world data, however, is naturally \emph{relational} — molecules,12social networks, citation graphs, road networks, protein--protein13interaction maps. Graph neural networks (GNNs) extend deep learning to14this irregular domain. The central design problem is invariance: the15prediction for a node must not depend on the arbitrary order in which its16neighbours are listed. This chapter develops the message-passing framework17that solves this problem, then derives the four canonical instantiations —18the graph convolutional network (GCN)~\cite{kipf2017}, the inductive19sample-and-aggregate network GraphSAGE~\cite{hamilton2017}, the graph20attention network (GAT)~\cite{velickovic2018}, and the graph isomorphism21network (GIN)~\cite{xu2019} — each with its propagation equations, its22estimation algorithm and its graphical representation.2324% ----------------------------------------------------------------------------25\section{Graphs, Notation and the Message-Passing Framework}26\label{sec:gnn-mp}27% ----------------------------------------------------------------------------2829Let $G = (V, E)$ be a graph with $n = |V|$ nodes. Each node $v \in V$30carries a feature vector $\vect{x}_v \in \R^{d}$, collected row-wise in31the matrix $\mat{X} \in \R^{n \times d}$; an edge $(u,v) \in E$ may carry32a feature vector $\vect{e}_{uv}$. The connectivity is encoded by the33adjacency matrix and the diagonal degree matrix,34\begin{equation}35 \mat{A} \in \{0,1\}^{n \times n}, \quad36 A_{uv} = \begin{cases} 1 & \text{if } (u,v) \in E,\\37 0 & \text{otherwise,} \end{cases}38 \qquad39 \mat{D} = \operatorname{diag}(d_1, \dots, d_n), \quad40 d_v = \sum_{u} A_{vu},41 \label{eq:gnn-adj}42\end{equation}43and the neighbourhood of $v$ is $\mathcal{N}(v) = \{u : (u,v) \in E\}$.44Because a graph has no canonical node ordering, any layer that maps node45states to node states must be \emph{permutation-equivariant}: relabelling46the nodes must merely relabel the outputs. The message-passing framework47achieves this by construction.4849\begin{definition}[Message-passing layer]\label{def:gnn-mpnn}50A message-passing layer updates the state $\vect{h}_v^{(k-1)}$ of every51node $v$ in three steps: a \emph{message} computed on each incoming edge52and summed,53\begin{equation}54 \vect{m}_v^{(k)}55 = \sum_{u \in \mathcal{N}(v)}56 M_k\bigl(\vect{h}_v^{(k-1)}, \vect{h}_u^{(k-1)}, \vect{e}_{uv}\bigr),57 \label{eq:gnn-message}58\end{equation}59an \emph{update} that combines the aggregated message with the node's own60state,61\begin{equation}62 \vect{h}_v^{(k)} = U_k\bigl(\vect{h}_v^{(k-1)}, \vect{m}_v^{(k)}\bigr),63 \label{eq:gnn-update}64\end{equation}65where $M_k$ and $U_k$ are learned functions (typically small MLPs or66gated units), and, for graph-level tasks after $K$ layers, a67permutation-\emph{invariant} \emph{readout}68\begin{equation}69 \hat{\vect{y}}_G = R\bigl(\{\vect{h}_v^{(K)} : v \in V\}\bigr).70 \label{eq:gnn-readout}71\end{equation}72The initial state is $\vect{h}_v^{(0)} = \vect{x}_v$.73\end{definition}7475Modern practice separates the neighbourhood \emph{aggregation} from the76self-\emph{combination}, a form to which every architecture in this77chapter reduces:78\begin{equation}79 \vect{a}_v^{(k)}80 = \operatorname{AGG}^{(k)}81 \bigl(\{\!\!\{\vect{h}_u^{(k-1)} : u \in \mathcal{N}(v)\}\!\!\}\bigr),82 \qquad83 \vect{h}_v^{(k)}84 = \operatorname{COMB}^{(k)}85 \bigl(\vect{h}_v^{(k-1)}, \vect{a}_v^{(k)}\bigr),86 \label{eq:gnn-aggcomb}87\end{equation}88where $\{\!\!\{\cdot\}\!\!\}$ denotes a \emph{multiset} — neighbours may89carry identical states, and their multiplicity matters. The aggregator90must be invariant under permutations of its multiset argument; the91standard choices are the sum, the mean, the element-wise maximum, and the92attention-weighted sum. The choice among them is not cosmetic: it93determines the discriminative power of the whole network, as94Section~\ref{sec:gnn-gin} makes precise. After $k$ layers, the state95$\vect{h}_v^{(k)}$ is a function of the subgraph within $k$ hops of $v$ —96the graph analogue of the receptive field of a convolutional network.97Figure~\ref{fig:gnn-mp} depicts one application of98\eqref{eq:gnn-message}--\eqref{eq:gnn-update}, and99Algorithm~\ref{alg:gnn-forward} summarizes the full forward pass.100101\begin{figure}[htbp]102 \centering103 \begin{tikzpicture}[scale=1.0]104 % ---- left panel: the graph ----105 \node[noutput] (v) at (0,0) {$v$};106 \node[ninput] (u1) at (-1.9,1.4) {$u_1$};107 \node[ninput] (u2) at (-2.3,-0.4){$u_2$};108 \node[ninput] (u3) at (-0.6,-1.9){$u_3$};109 \node[ninput] (u4) at (1.4,1.6) {$u_4$};110 \node[neuron] (w1) at (-3.6,1.9) {$w_1$};111 \node[neuron] (w2) at (-3.9,-1.2){$w_2$};112 \node[neuron] (w3) at (0.9,-2.6) {$w_3$};113 % plain graph edges (2-hop)114 \draw[black!45, semithick] (u1) -- (w1);115 \draw[black!45, semithick] (u2) -- (w1);116 \draw[black!45, semithick] (u2) -- (w2);117 \draw[black!45, semithick] (u3) -- (w3);118 % message arrows into v119 \draw[fleche, cinput!80!black] (u1) to[bend left=12]120 node[etiquette, above right=-1pt] {$\vect{m}_{u_1 \to v}$} (v);121 \draw[fleche, cinput!80!black] (u2) to[bend right=12] (v);122 \draw[fleche, cinput!80!black] (u3) to[bend right=12] (v);123 \draw[fleche, cinput!80!black] (u4) to[bend left=12] (v);124 % ---- right panel: aggregate / combine pipeline ----125 \node[etiquette, align=center] (ms) at (5.4,1.9)126 {$\{\!\!\{\vect{h}_{u}^{(k-1)} : u \in \mathcal{N}(v)\}\!\!\}$};127 \node[gate, minimum width=2.6cm] (agg) at (5.4,0.9)128 {$\operatorname{AGG}^{(k)}$};129 \node[blochidden, minimum width=2.6cm] (comb) at (5.4,-0.7)130 {$\operatorname{COMB}^{(k)}$};131 \node[etiquette] (hout) at (5.4,-1.9) {$\vect{h}_v^{(k)}$};132 \draw[fleche] (ms) -- (agg);133 \draw[fleche] (agg) -- node[etiquette, right]134 {$\vect{a}_v^{(k)}$} (comb);135 \draw[fleche] (comb) -- (hout);136 % self state feeding the combine step137 \node[etiquette] (hself) at (8.1,-0.7) {$\vect{h}_v^{(k-1)}$};138 \draw[fleche] (hself) -- (comb);139 % dashed link from the graph to the pipeline140 \draw[flechep, black!55] (v.east) to[bend left=10] (agg.west);141 \end{tikzpicture}142 \caption{One message-passing layer at node $v$143 (Definition~\ref{def:gnn-mpnn}). Left: the neighbours144 $u_1, \dots, u_4$ (blue) send messages along the edges into the145 target node $v$ (red); the nodes $w_i$ are two hops away and will146 only influence $v$ at the next layer. Right: the received multiset is147 reduced by a permutation-invariant aggregator, then combined with the148 node's previous state to produce $\vect{h}_v^{(k)}$, following149 \eqref{eq:gnn-aggcomb}.}150 \label{fig:gnn-mp}151\end{figure}152153\begin{algorithm}[htbp]154 \caption{Generic message-passing forward pass (MPNN)}155 \label{alg:gnn-forward}156 \begin{algorithmic}[1]157 \Require graph $G=(V,E)$, features $\{\vect{x}_v\}$, depth $K$,158 layers $\{(M_k, U_k)\}_{k=1}^{K}$, readout $R$159 \For{$v \in V$}160 \State $\vect{h}_v^{(0)} \gets \vect{x}_v$161 \EndFor162 \For{$k = 1, \dots, K$}163 \For{$v \in V$}164 \State $\vect{m}_v^{(k)} \gets165 \sum_{u \in \mathcal{N}(v)}166 M_k\bigl(\vect{h}_v^{(k-1)}, \vect{h}_u^{(k-1)},167 \vect{e}_{uv}\bigr)$168 \Comment{messages, Eq.~\eqref{eq:gnn-message}}169 \EndFor170 \For{$v \in V$}171 \State $\vect{h}_v^{(k)} \gets172 U_k\bigl(\vect{h}_v^{(k-1)}, \vect{m}_v^{(k)}\bigr)$173 \Comment{update, Eq.~\eqref{eq:gnn-update}}174 \EndFor175 \EndFor176 \State \Return node states $\{\vect{h}_v^{(K)}\}$, or177 $\hat{\vect{y}}_G = R\bigl(\{\vect{h}_v^{(K)}\}\bigr)$ for178 graph-level tasks179 \end{algorithmic}180\end{algorithm}181182\begin{remark}183The two inner loops of Algorithm~\ref{alg:gnn-forward} are never executed184node by node in practice: with sum or mean aggregation the whole layer185collapses into a pair of sparse--dense matrix products (cf.\186\eqref{eq:gnn-gcnlayer}), so a full propagation step costs187$\mathcal{O}(|E| \cdot d)$ — linear in the number of edges.188\end{remark}189190% ----------------------------------------------------------------------------191\section{Graph Convolutional Networks}\label{sec:gnn-gcn}192% ----------------------------------------------------------------------------193194The GCN of Kipf and Welling~\cite{kipf2017} descends from spectral graph195theory. On a graph, the Fourier basis is provided by the eigenvectors of196the normalized graph Laplacian197$\mat{L} = \mat{I} - \mat{D}^{-1/2}\mat{A}\mat{D}^{-1/2}198= \mat{U}\mat{\Lambda}\mat{U}\transp$, and a spectral convolution with199filter $g_\theta$ acts on a signal $\vect{x} \in \R^n$ as200\begin{equation}201 g_\theta \star \vect{x}202 = \mat{U}\, g_\theta(\mat{\Lambda})\, \mat{U}\transp \vect{x}.203 \label{eq:gnn-spectral}204\end{equation}205Evaluating \eqref{eq:gnn-spectral} exactly requires the full206eigendecomposition — $\mathcal{O}(n^3)$, prohibitive beyond small graphs.207Truncating a Chebyshev expansion of $g_\theta$ at first order, and tying208its two remaining coefficients, collapses the filter to a strictly local209operation:210\begin{equation}211 g_\theta \star \vect{x}212 \;\approx\;213 \theta \bigl(\mat{I} + \mat{D}^{-1/2}\mat{A}\mat{D}^{-1/2}\bigr)\,214 \vect{x}.215 \label{eq:gnn-cheby}216\end{equation}217The operator in \eqref{eq:gnn-cheby} has eigenvalues in $[0,2]$; stacking218many such layers can therefore amplify or shrink signals. The219\emph{renormalization trick} restores stability by adding self-loops220\emph{before} normalizing:221\begin{equation}222 \tilde{\mat{A}} = \mat{A} + \mat{I},223 \qquad224 \tilde{D}_{ii} = \sum_j \tilde{A}_{ij},225 \qquad226 \hat{\mat{A}}227 = \tilde{\mat{D}}^{-1/2}\, \tilde{\mat{A}}\, \tilde{\mat{D}}^{-1/2}.228 \label{eq:gnn-ahat}229\end{equation}230With $\mat{H}^{(0)} = \mat{X}$, the celebrated layer-wise propagation231rule reads232\begin{equation}233 \mat{H}^{(\ell+1)}234 = \varphi\bigl(\hat{\mat{A}}\, \mat{H}^{(\ell)}\, \mat{W}^{(\ell)}\bigr),235 \label{eq:gnn-gcnlayer}236\end{equation}237with $\mat{W}^{(\ell)}$ the trainable weights and $\varphi$ typically the238ReLU. Equation~\eqref{eq:gnn-gcnlayer} is an instance of239\eqref{eq:gnn-aggcomb}: written for a single node it becomes a240degree-weighted mean over the closed neighbourhood,241\begin{equation}242 \vect{h}_v^{(\ell+1)}243 = \varphi\Biggl(244 \sum_{u \in \mathcal{N}(v) \cup \{v\}}245 \frac{1}{\sqrt{\tilde{d}_v\, \tilde{d}_u}}\,246 \mat{W}^{(\ell)} \vect{h}_u^{(\ell)}247 \Biggr).248 \label{eq:gnn-gcnnode}249\end{equation}250The symmetric normalization $1/\sqrt{\tilde d_v \tilde d_u}$ downweights251messages that either \emph{leave} or \emph{enter} a high-degree hub, and252keeps the propagation operator symmetric, hence with a real spectrum.253254For semi-supervised node classification — the task that made the GCN255famous — a two-layer network suffices:256\begin{equation}257 \mat{Z} = \softmax\Bigl(258 \hat{\mat{A}}\,259 \operatorname{ReLU}\bigl(\hat{\mat{A}} \mat{X} \mat{W}^{(0)}\bigr)\,260 \mat{W}^{(1)}261 \Bigr),262 \label{eq:gnn-gcntwo}263\end{equation}264trained by minimizing the cross-entropy over the (small) labelled subset265$V_L \subset V$ only,266\begin{equation}267 \Loss(\theta)268 = -\sum_{v \in V_L} \sum_{c=1}^{C} Y_{vc} \ln Z_{vc},269 \label{eq:gnn-gcnloss}270\end{equation}271while the propagation through $\hat{\mat{A}}$ spreads label information272to the unlabelled nodes — the graph structure itself acts as the273regularizer.274275\begin{remark}[Over-smoothing and transductivity]\label{rem:gnn-oversmooth}276Repeated multiplication by $\hat{\mat{A}}$ is a low-pass filter on the277graph: as depth grows, all node states converge towards a278degree-dependent stationary vector and become indistinguishable. Deep279GCNs therefore \emph{lose} discriminative power; in practice two or three280layers are optimal, and deeper stacks require residual connections or281normalization to remain trainable. A second limitation is that282\eqref{eq:gnn-gcntwo} needs the full matrix $\hat{\mat{A}}$ at training283time: the vanilla GCN is \emph{transductive} and cannot embed nodes284unseen during training.285\end{remark}286287% ----------------------------------------------------------------------------288\section{GraphSAGE: Inductive Learning by Sampled Aggregation}289\label{sec:gnn-sage}290% ----------------------------------------------------------------------------291292GraphSAGE~\cite{hamilton2017} removes both limitations of293Remark~\ref{rem:gnn-oversmooth} at once: it learns \emph{aggregator294functions} rather than per-node embeddings, and it evaluates them on295\emph{sampled} fixed-size neighbourhoods $\mathcal{S}(v) \subseteq296\mathcal{N}(v)$ with $|\mathcal{S}(v)| = s$, so that the cost per node is297bounded regardless of the degree distribution. One layer performs298\begin{align}299 \vect{h}_{\mathcal{N}(v)}^{(k)}300 &= \operatorname{AGG}_k\bigl(301 \{\!\!\{\vect{h}_u^{(k-1)} : u \in \mathcal{S}(v)\}\!\!\}\bigr),302 \label{eq:gnn-sageagg}\\303 \vect{h}_v^{(k)}304 &= \varphi\Bigl(\mat{W}^{(k)}305 \bigl[\vect{h}_v^{(k-1)} \,\Vert\, \vect{h}_{\mathcal{N}(v)}^{(k)}306 \bigr]\Bigr),307 \qquad308 \vect{h}_v^{(k)} \leftarrow309 \frac{\vect{h}_v^{(k)}}{\bigl\lVert \vect{h}_v^{(k)} \bigr\rVert_2},310 \label{eq:gnn-sageupd}311\end{align}312where $\Vert$ denotes concatenation. Concatenating — rather than summing313— the self-state with the neighbourhood summary acts as a skip314connection that preserves the node's own identity through depth. Two of315the proposed aggregators are the mean and the max-pooling aggregator,316\begin{equation}317 \operatorname{AGG}^{\text{mean}}318 = \frac{1}{|\mathcal{S}(v)|} \sum_{u \in \mathcal{S}(v)}319 \vect{h}_u^{(k-1)},320 \label{eq:gnn-sagemean}321\end{equation}322\begin{equation}323 \operatorname{AGG}^{\text{pool}}324 = \max_{u \in \mathcal{S}(v)}325 \varphi\bigl(\mat{W}_{\text{pool}}\, \vect{h}_u^{(k-1)}326 + \vect{b}\bigr),327 \label{eq:gnn-sagepool}328\end{equation}329the max taken element-wise (a third variant applies an LSTM to a random330permutation of the neighbours — expressive, but not331permutation-invariant). Because the aggregators are shared functions of332local structure, a trained GraphSAGE model embeds \emph{previously unseen333nodes} — and even entirely new graphs — by simply running334\eqref{eq:gnn-sageagg}--\eqref{eq:gnn-sageupd} on their neighbourhoods:335this is what \emph{inductive} means here.336337When no labels are available, GraphSAGE is trained with a random-walk338co-occurrence loss with negative sampling,339\begin{equation}340 J(\vect{z}_u)341 = -\ln \sigma\bigl(\vect{z}_u\transp \vect{z}_v\bigr)342 - Q \cdot \E_{v_n \sim P_n}343 \bigl[\ln \sigma\bigl(-\vect{z}_u\transp \vect{z}_{v_n}\bigr)\bigr],344 \label{eq:gnn-sageloss}345\end{equation}346which pulls together the embeddings of nodes $u, v$ that co-occur on347short random walks and pushes $\vect{z}_u$ away from $Q$ negative348samples $v_n$ drawn from a noise distribution $P_n$; here $\sigma$ is the349logistic sigmoid. The supervised variant simply replaces350\eqref{eq:gnn-sageloss} with the cross-entropy \eqref{eq:gnn-gcnloss} on351the batch. Algorithm~\ref{alg:gnn-sage} gives the complete minibatch352estimation procedure; the unrolled sampling it induces is visualized in353Figure~\ref{fig:gnn-tree}.354355\begin{algorithm}[htbp]356 \caption{GraphSAGE minibatch training with neighbour sampling357 (supervised)}358 \label{alg:gnn-sage}359 \begin{algorithmic}[1]360 \Require graph $G$, features $\{\vect{x}_v\}$, labels on $V_L$,361 depth $K$, sample sizes $s_1, \dots, s_K$,362 learning rate $\eta$363 \While{not converged}364 \State sample a batch $B \subseteq V_L$;\quad $B^{(K)} \gets B$365 \For{$k = K, \dots, 1$}366 \Comment{backward neighbourhood expansion}367 \State $B^{(k-1)} \gets B^{(k)} \cup368 \bigcup_{v \in B^{(k)}} \mathcal{S}_k(v)$,369 \quad $|\mathcal{S}_k(v)| = s_k$370 \EndFor371 \State $\vect{h}_v^{(0)} \gets \vect{x}_v$372 for all $v \in B^{(0)}$373 \For{$k = 1, \dots, K$}374 \For{$v \in B^{(k)}$}375 \State $\vect{h}_{\mathcal{N}(v)}^{(k)} \gets$376 aggregate over $\mathcal{S}_k(v)$ by \eqref{eq:gnn-sageagg}377 \State $\vect{h}_v^{(k)} \gets$ combine and normalize by378 \eqref{eq:gnn-sageupd}379 \EndFor380 \EndFor381 \State $\Loss \gets -\frac{1}{|B|} \sum_{v \in B}382 \sum_{c} Y_{vc} \ln383 \softmax\bigl(\mat{W}_{\text{out}}\vect{h}_v^{(K)}\bigr)_c$384 \State $\theta \gets \theta - \eta\, \nabla_\theta \Loss$385 \Comment{SGD or Adam step}386 \EndWhile387 \end{algorithmic}388\end{algorithm}389390\begin{figure}[htbp]391 \centering392 \begin{tikzpicture}[scale=1.0]393 % root394 \node[noutput] (r) at (0,0) {$v$};395 % level 1396 \node[nhidden] (a1) at (-3.0,-1.9) {$u_1$};397 \node[nhidden] (a2) at (0,-1.9) {$u_2$};398 \node[nhidden] (a3) at (3.0,-1.9) {$u_3$};399 % level 2400 \node[ninput] (b1) at (-4.4,-3.8) {$w_1$};401 \node[ninput] (b2) at (-3.0,-3.8) {$w_2$};402 \node[ninput] (b3) at (-1.6,-3.8) {$w_3$};403 \node[ninput] (b4) at (0.0,-3.8) {$w_4$};404 \node[ninput] (b5) at (1.6,-3.8) {$w_5$};405 \node[ninput] (b6) at (3.0,-3.8) {$w_6$};406 \node[ninput] (b7) at (4.4,-3.8) {$w_7$};407 % arrows upward (aggregation direction)408 \draw[fleche, chidden!85!black] (a1) -- (r);409 \draw[fleche, chidden!85!black] (a2) -- (r);410 \draw[fleche, chidden!85!black] (a3) -- (r);411 \draw[fleche, cinput!80!black] (b1) -- (a1);412 \draw[fleche, cinput!80!black] (b2) -- (a1);413 \draw[fleche, cinput!80!black] (b3) -- (a2);414 \draw[fleche, cinput!80!black] (b4) -- (a2);415 \draw[fleche, cinput!80!black] (b5) -- (a3);416 \draw[fleche, cinput!80!black] (b6) -- (a3);417 \draw[fleche, cinput!80!black] (b7) -- (a3);418 % depth annotations on the right419 \node[etiquette, anchor=west] at (5.4,0)420 {layer $k=2$: $\vect{h}_v^{(2)}$};421 \node[etiquette, anchor=west] at (5.4,-1.9)422 {layer $k=1$: $\vect{h}_{u_i}^{(1)}$};423 \node[etiquette, anchor=west] at (5.4,-3.8)424 {layer $k=0$: $\vect{h}_{w_j}^{(0)} = \vect{x}_{w_j}$};425 % brace for sampled neighbourhoods426 \draw[decorate, decoration={brace, mirror, amplitude=5pt},427 black!60]428 (-4.9,-4.5) -- (4.9,-4.5)429 node[etiquette, midway, below=7pt]430 {sampled two-hop neighbourhood:431 $w_j \in \mathcal{S}_1(u_i)$, $u_i \in \mathcal{S}_2(v)$};432 \end{tikzpicture}433 \caption{The computation tree unrolled by a depth-2 GraphSAGE forward434 pass at node $v$ (Algorithm~\ref{alg:gnn-sage}). Layer-0 states of435 the sampled two-hop nodes (blue) are aggregated into layer-1 states436 of the sampled one-hop neighbours (orange), which are in turn437 aggregated into the final state of $v$ (red). Sampling fixes the438 branching factor of the tree, bounding the cost independently of the439 node degrees.}440 \label{fig:gnn-tree}441\end{figure}442443% ----------------------------------------------------------------------------444\section{Graph Attention Networks}\label{sec:gnn-gat}445% ----------------------------------------------------------------------------446447The GCN weighs the message from $u$ to $v$ by the purely structural448coefficient $1/\sqrt{\tilde d_v \tilde d_u}$ of449\eqref{eq:gnn-gcnnode}: two neighbours with equal degrees are equally450important, whatever their features. Graph attention451networks~\cite{velickovic2018} replace this fixed coefficient with a452\emph{learned}, feature-dependent one, importing the attention mechanism453into message passing. With a shared projection454$\mat{W} \in \R^{F' \times F}$ and an attention vector455$\vect{a} \in \R^{2F'}$, the unnormalized score of edge $(j \to i)$ is456\begin{equation}457 e_{ij}458 = \operatorname{LeakyReLU}\Bigl(459 \vect{a}\transp460 \bigl[\mat{W}\vect{h}_i \,\Vert\, \mat{W}\vect{h}_j\bigr]461 \Bigr),462 \label{eq:gnn-gatlogit}463\end{equation}464normalized by a softmax masked to the neighbourhood (including $i$465itself),466\begin{equation}467 \alpha_{ij}468 = \frac{\exp(e_{ij})}469 {\sum_{k \in \mathcal{N}(i) \cup \{i\}} \exp(e_{ik})},470 \label{eq:gnn-gatalpha}471\end{equation}472and the node update is the attention-weighted aggregation473\begin{equation}474 \vect{h}_i'475 = \varphi\Biggl(476 \sum_{j \in \mathcal{N}(i) \cup \{i\}}477 \alpha_{ij}\, \mat{W} \vect{h}_j478 \Biggr).479 \label{eq:gnn-gatupd}480\end{equation}481As in the Transformer, several attention heads stabilize learning and482attend to different relational patterns; hidden layers concatenate the483heads while the final prediction layer averages them:484\begin{equation}485 \vect{h}_i'486 = \bigl\Vert_{k=1}^{K} \varphi\Bigl(487 \textstyle\sum_{j} \alpha_{ij}^{k}\, \mat{W}^{k} \vect{h}_j488 \Bigr),489 \qquad490 \vect{h}_i'491 = \varphi\Bigl(492 \tfrac{1}{K} \textstyle\sum_{k=1}^{K} \sum_{j}493 \alpha_{ij}^{k}\, \mat{W}^{k} \vect{h}_j494 \Bigr)495 \quad \text{(final layer)}.496 \label{eq:gnn-gatmulti}497\end{equation}498Figure~\ref{fig:gnn-gat} shows the resulting anisotropic aggregation:499unlike in the GCN, the incoming edges of a node carry \emph{different}500weights, and those weights change with the node features rather than501being frozen by the topology. GAT is inductive for the same reason502GraphSAGE is — all parameters ($\mat{W}$, $\vect{a}$) are shared503functions, none is tied to a node identity — and the attention504coefficients offer a degree of built-in interpretability: inspecting505$\alpha_{ij}$ reveals which neighbours drove a prediction.506507\begin{remark}508The scoring function \eqref{eq:gnn-gatlogit} applies its nonlinearity509\emph{after} the inner product with $\vect{a}$; the neighbour ranking it510induces is therefore shared by all query nodes (\emph{static}511attention). Moving the nonlinearity inside,512$e_{ij} = \vect{a}\transp \operatorname{LeakyReLU}513(\mat{W}[\vect{h}_i \Vert \vect{h}_j])$, yields the strictly more514expressive dynamic variant known as GATv2.515\end{remark}516517\begin{figure}[htbp]518 \centering519 \begin{tikzpicture}[scale=1.0]520 \node[noutput] (v) at (0,0) {$i$};521 \node[ninput] (u1) at (-2.3,1.6) {$j_1$};522 \node[ninput] (u2) at (-2.7,-0.6){$j_2$};523 \node[ninput] (u3) at (-0.4,-2.3){$j_3$};524 \node[ninput] (u4) at (2.1,1.6) {$j_4$};525 % head 1 (blue, thickness ~ alpha), arcs on one side of each chord526 \draw[fleche, cinput!80!black, line width=1.8pt]527 (u1) to[bend left=16] (v);528 \draw[fleche, cinput!80!black, line width=0.6pt]529 (u2) to[bend left=16] (v);530 \draw[fleche, cinput!80!black, line width=1.1pt]531 (u3) to[bend left=16] (v);532 \draw[fleche, cinput!80!black, line width=1.1pt]533 (u4) to[bend right=16] (v);534 % head 2 (orange), arcs on the other side535 \draw[fleche, chidden!85!black, line width=0.7pt]536 (u1) to[bend right=16] (v);537 \draw[fleche, chidden!85!black, line width=1.7pt]538 (u2) to[bend right=16] (v);539 \draw[fleche, chidden!85!black, line width=0.8pt]540 (u3) to[bend right=16] (v);541 \draw[fleche, chidden!85!black, line width=1.2pt]542 (u4) to[bend left=16] (v);543 % coefficient labels, colour-coded by head, pinned off the arcs544 \node[etiquette, text=cinput!80!black] at (-0.85, 1.30) {$0.42$};545 \node[etiquette, text=chidden!85!black] at (-2.05, 0.55) {$0.15$};546 \node[etiquette, text=cinput!80!black] at (-1.55, 0.10) {$0.11$};547 \node[etiquette, text=chidden!85!black] at (-1.75,-1.10) {$0.39$};548 \node[etiquette, text=cinput!80!black] at (-0.95,-1.35) {$0.23$};549 \node[etiquette, text=chidden!85!black] at ( 0.55,-1.45) {$0.18$};550 \node[etiquette, text=cinput!80!black] at ( 1.05, 1.30) {$0.24$};551 \node[etiquette, text=chidden!85!black] at ( 1.90, 0.55) {$0.28$};552 % legend553 \node[etiquette, anchor=west, text=cinput!80!black]554 at (4.0,0.7) {head $k=1$: coefficients $\alpha_{ij}^{1}$};555 \node[etiquette, anchor=west, text=chidden!85!black]556 at (4.0,0.1) {head $k=2$: coefficients $\alpha_{ij}^{2}$};557 \node[etiquette, anchor=west, align=left] at (4.0,-0.9)558 {line width $\propto \alpha_{ij}^{k}$;\\559 each head sums to $1$ over\\560 $\mathcal{N}(i)\cup\{i\}$ (self-loop\\561 omitted for clarity)};562 \end{tikzpicture}563 \caption{Graph attention at node $i$,564 equations~\eqref{eq:gnn-gatlogit}--\eqref{eq:gnn-gatmulti}. Each of565 the two heads (blue, orange) computes its own normalized566 coefficients $\alpha_{ij}^{k}$ over the same neighbourhood; the567 thickness of each arrow is proportional to the learned coefficient.568 Structurally identical neighbours may thus receive very different569 weights, in contrast with the degree-based coefficients of the GCN570 in \eqref{eq:gnn-gcnnode}.}571 \label{fig:gnn-gat}572\end{figure}573574% ----------------------------------------------------------------------------575\section{How Powerful Are GNNs? The Graph Isomorphism Network}576\label{sec:gnn-gin}577% ----------------------------------------------------------------------------578579The freedom in choosing $\operatorname{AGG}$ in \eqref{eq:gnn-aggcomb}580raises a theoretical question: which graphs can a message-passing network581tell apart at all? Xu et al.~\cite{xu2019} answered it by relating GNNs582to the classical one-dimensional Weisfeiler--Lehman (1-WL) colour583refinement test, which iteratively re-hashes each node's colour together584with the multiset of its neighbours' colours.585586\begin{theorem}[Expressive power of message passing]587\label{thm:gnn-wl}588Any GNN of the form \eqref{eq:gnn-aggcomb} maps two non-isomorphic graphs589to different embeddings only if the 1-WL test also distinguishes them:590message passing is \emph{at most} as discriminative as 1-WL. This upper591bound is attained if the aggregation, combination and readout functions592are all \emph{injective} on multisets~\cite{xu2019}.593\end{theorem}594595Injectivity is where the common aggregators part ways. The mean loses596multiplicities — it cannot distinguish597$\{\!\!\{\vect{a}, \vect{a}, \vect{b}, \vect{b}\}\!\!\}$ from598$\{\!\!\{\vect{a}, \vect{b}\}\!\!\}$ — and the max loses everything but599the support; the \emph{sum} preserves both, and over countable feature600spaces sum-based aggregation composed with an MLP can represent any601multiset function.602603\begin{property}[Aggregator ranking]\label{prop:gnn-agg}604In discriminative power over multisets,605$\mathrm{sum} \succ \mathrm{mean} \succ \mathrm{max}$: the mean captures606the distribution of neighbour features but not their multiplicities; the607max captures only the underlying set.608\end{property}609610The graph isomorphism network makes the injective choice concrete, with611a learnable scalar $\epsilon^{(k)}$ that disambiguates the node's own612state from the neighbour sum, and an MLP as a universal approximator on613top:614\begin{equation}615 \vect{h}_v^{(k)}616 = \operatorname{MLP}^{(k)}\Bigl(617 \bigl(1 + \epsilon^{(k)}\bigr)\, \vect{h}_v^{(k-1)}618 + \sum_{u \in \mathcal{N}(v)} \vect{h}_u^{(k-1)}619 \Bigr).620 \label{eq:gnn-gin}621\end{equation}622For graph-level prediction, GIN concatenates a summed readout of623\emph{every} depth, retaining both local and global structure:624\begin{equation}625 \vect{h}_G626 = \bigl\Vert_{k=0}^{K}\,627 \sum_{v \in V} \vect{h}_v^{(k)}.628 \label{eq:gnn-ginread}629\end{equation}630By Theorem~\ref{thm:gnn-wl}, the network631\eqref{eq:gnn-gin}--\eqref{eq:gnn-ginread} is a \emph{maximally632powerful} message-passing GNN: whatever 1-WL can distinguish, GIN can633learn to distinguish.634635\begin{remark}636The 1-WL ceiling is a genuine ceiling: no network of the form637\eqref{eq:gnn-aggcomb} can, for instance, count triangles or separate638certain pairs of regular graphs. Escaping it requires strictly more639machinery — higher-order message passing over node tuples, random node640identifiers, or positional and structural encodings appended to the641input features $\vect{x}_v$.642\end{remark}643644% ----------------------------------------------------------------------------645\section{Prediction Heads and Training Objectives}\label{sec:gnn-heads}646% ----------------------------------------------------------------------------647648The message-passing trunk of649Sections~\ref{sec:gnn-mp}--\ref{sec:gnn-gin} is shared by three families650of tasks, which differ only in the head applied to the final states651$\vect{z}_v = \vect{h}_v^{(K)}$:652\begin{align}653 \hat{\vect{y}}_v654 &= \softmax\bigl(\mat{W}_{\text{out}}\, \vect{z}_v\bigr)655 && \text{(node classification)},656 \label{eq:gnn-nodehead}\\657 s_{uv}658 &= \sigma\bigl(\vect{z}_u\transp \vect{z}_v\bigr)659 && \text{(link prediction)},660 \label{eq:gnn-linkhead}\\661 \hat{\vect{y}}_G662 &= \softmax\bigl(\mat{W}_G\, \vect{h}_G\bigr),663 \qquad \vect{h}_G \text{ from } \eqref{eq:gnn-ginread}664 && \text{(graph classification)}.665 \label{eq:gnn-graphhead}666\end{align}667Node and graph heads are trained with the cross-entropy668\eqref{eq:gnn-gcnloss}; the link-prediction head with the logistic loss669of \eqref{eq:gnn-sageloss}, treating observed edges as positives and670sampled non-edges as negatives. All four architectures of this chapter671slot into this scheme unchanged — the choice among GCN, GraphSAGE, GAT672and GIN is a choice of aggregation rule673(\eqref{eq:gnn-gcnnode}, \eqref{eq:gnn-sageagg},674\eqref{eq:gnn-gatupd}, \eqref{eq:gnn-gin}), not a choice of task.675676These models power a remarkable range of applications: semi-supervised677classification of citation networks, molecular property prediction and678drug discovery (message passing over atoms and bonds), billion-node679recommender systems built on sampled aggregation, learned physics680simulation, traffic forecasting and protein structure prediction, where681attention over residue-pair graphs is a central ingredient. In every682case the inductive bias is the same: what a node \emph{is} should be683computable from what its neighbourhood \emph{looks like} — the684graph-structured analogue of the translation equivariance that motivated685convolutional networks.686