% ============================================================================
%  Artificial Neural Networks — Methods, Equations and Graphical
%  Representations
%  Author  : Simon-Pierre Boucher — contact@spboucher.ai
%  Chapter 8 : Graph Neural Networks (chapters/08-gnn.tex)
% ============================================================================
\chapter{Graph Neural Networks}\label{chap:gnn}

The architectures of the preceding chapters assume that data live on a
regular lattice: images are grids, sequences are chains. A vast portion of
real-world data, however, is naturally \emph{relational} — molecules,
social networks, citation graphs, road networks, protein--protein
interaction maps. Graph neural networks (GNNs) extend deep learning to
this irregular domain. The central design problem is invariance: the
prediction for a node must not depend on the arbitrary order in which its
neighbours are listed. This chapter develops the message-passing framework
that solves this problem, then derives the four canonical instantiations —
the graph convolutional network (GCN)~\cite{kipf2017}, the inductive
sample-and-aggregate network GraphSAGE~\cite{hamilton2017}, the graph
attention network (GAT)~\cite{velickovic2018}, and the graph isomorphism
network (GIN)~\cite{xu2019} — each with its propagation equations, its
estimation algorithm and its graphical representation.

% ----------------------------------------------------------------------------
\section{Graphs, Notation and the Message-Passing Framework}
\label{sec:gnn-mp}
% ----------------------------------------------------------------------------

Let $G = (V, E)$ be a graph with $n = |V|$ nodes. Each node $v \in V$
carries a feature vector $\vect{x}_v \in \R^{d}$, collected row-wise in
the matrix $\mat{X} \in \R^{n \times d}$; an edge $(u,v) \in E$ may carry
a feature vector $\vect{e}_{uv}$. The connectivity is encoded by the
adjacency matrix and the diagonal degree matrix,
\begin{equation}
  \mat{A} \in \{0,1\}^{n \times n}, \quad
  A_{uv} = \begin{cases} 1 & \text{if } (u,v) \in E,\\
                          0 & \text{otherwise,} \end{cases}
  \qquad
  \mat{D} = \operatorname{diag}(d_1, \dots, d_n), \quad
  d_v = \sum_{u} A_{vu},
  \label{eq:gnn-adj}
\end{equation}
and the neighbourhood of $v$ is $\mathcal{N}(v) = \{u : (u,v) \in E\}$.
Because a graph has no canonical node ordering, any layer that maps node
states to node states must be \emph{permutation-equivariant}: relabelling
the nodes must merely relabel the outputs. The message-passing framework
achieves this by construction.

\begin{definition}[Message-passing layer]\label{def:gnn-mpnn}
A message-passing layer updates the state $\vect{h}_v^{(k-1)}$ of every
node $v$ in three steps: a \emph{message} computed on each incoming edge
and summed,
\begin{equation}
  \vect{m}_v^{(k)}
  = \sum_{u \in \mathcal{N}(v)}
    M_k\bigl(\vect{h}_v^{(k-1)}, \vect{h}_u^{(k-1)}, \vect{e}_{uv}\bigr),
  \label{eq:gnn-message}
\end{equation}
an \emph{update} that combines the aggregated message with the node's own
state,
\begin{equation}
  \vect{h}_v^{(k)} = U_k\bigl(\vect{h}_v^{(k-1)}, \vect{m}_v^{(k)}\bigr),
  \label{eq:gnn-update}
\end{equation}
where $M_k$ and $U_k$ are learned functions (typically small MLPs or
gated units), and, for graph-level tasks after $K$ layers, a
permutation-\emph{invariant} \emph{readout}
\begin{equation}
  \hat{\vect{y}}_G = R\bigl(\{\vect{h}_v^{(K)} : v \in V\}\bigr).
  \label{eq:gnn-readout}
\end{equation}
The initial state is $\vect{h}_v^{(0)} = \vect{x}_v$.
\end{definition}

Modern practice separates the neighbourhood \emph{aggregation} from the
self-\emph{combination}, a form to which every architecture in this
chapter reduces:
\begin{equation}
  \vect{a}_v^{(k)}
  = \operatorname{AGG}^{(k)}
    \bigl(\{\!\!\{\vect{h}_u^{(k-1)} : u \in \mathcal{N}(v)\}\!\!\}\bigr),
  \qquad
  \vect{h}_v^{(k)}
  = \operatorname{COMB}^{(k)}
    \bigl(\vect{h}_v^{(k-1)}, \vect{a}_v^{(k)}\bigr),
  \label{eq:gnn-aggcomb}
\end{equation}
where $\{\!\!\{\cdot\}\!\!\}$ denotes a \emph{multiset} — neighbours may
carry identical states, and their multiplicity matters. The aggregator
must be invariant under permutations of its multiset argument; the
standard choices are the sum, the mean, the element-wise maximum, and the
attention-weighted sum. The choice among them is not cosmetic: it
determines the discriminative power of the whole network, as
Section~\ref{sec:gnn-gin} makes precise. After $k$ layers, the state
$\vect{h}_v^{(k)}$ is a function of the subgraph within $k$ hops of $v$ —
the graph analogue of the receptive field of a convolutional network.
Figure~\ref{fig:gnn-mp} depicts one application of
\eqref{eq:gnn-message}--\eqref{eq:gnn-update}, and
Algorithm~\ref{alg:gnn-forward} summarizes the full forward pass.

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[scale=1.0]
    % ---- left panel: the graph ----
    \node[noutput] (v)  at (0,0)      {$v$};
    \node[ninput]  (u1) at (-1.9,1.4) {$u_1$};
    \node[ninput]  (u2) at (-2.3,-0.4){$u_2$};
    \node[ninput]  (u3) at (-0.6,-1.9){$u_3$};
    \node[ninput]  (u4) at (1.4,1.6)  {$u_4$};
    \node[neuron]  (w1) at (-3.6,1.9) {$w_1$};
    \node[neuron]  (w2) at (-3.9,-1.2){$w_2$};
    \node[neuron]  (w3) at (0.9,-2.6) {$w_3$};
    % plain graph edges (2-hop)
    \draw[black!45, semithick] (u1) -- (w1);
    \draw[black!45, semithick] (u2) -- (w1);
    \draw[black!45, semithick] (u2) -- (w2);
    \draw[black!45, semithick] (u3) -- (w3);
    % message arrows into v
    \draw[fleche, cinput!80!black] (u1) to[bend left=12]
      node[etiquette, above right=-1pt] {$\vect{m}_{u_1 \to v}$} (v);
    \draw[fleche, cinput!80!black] (u2) to[bend right=12] (v);
    \draw[fleche, cinput!80!black] (u3) to[bend right=12] (v);
    \draw[fleche, cinput!80!black] (u4) to[bend left=12] (v);
    % ---- right panel: aggregate / combine pipeline ----
    \node[etiquette, align=center] (ms) at (5.4,1.9)
      {$\{\!\!\{\vect{h}_{u}^{(k-1)} : u \in \mathcal{N}(v)\}\!\!\}$};
    \node[gate, minimum width=2.6cm] (agg) at (5.4,0.9)
      {$\operatorname{AGG}^{(k)}$};
    \node[blochidden, minimum width=2.6cm] (comb) at (5.4,-0.7)
      {$\operatorname{COMB}^{(k)}$};
    \node[etiquette] (hout) at (5.4,-1.9) {$\vect{h}_v^{(k)}$};
    \draw[fleche] (ms)  -- (agg);
    \draw[fleche] (agg) -- node[etiquette, right]
      {$\vect{a}_v^{(k)}$} (comb);
    \draw[fleche] (comb) -- (hout);
    % self state feeding the combine step
    \node[etiquette] (hself) at (8.1,-0.7) {$\vect{h}_v^{(k-1)}$};
    \draw[fleche] (hself) -- (comb);
    % dashed link from the graph to the pipeline
    \draw[flechep, black!55] (v.east) to[bend left=10] (agg.west);
  \end{tikzpicture}
  \caption{One message-passing layer at node $v$
    (Definition~\ref{def:gnn-mpnn}). Left: the neighbours
    $u_1, \dots, u_4$ (blue) send messages along the edges into the
    target node $v$ (red); the nodes $w_i$ are two hops away and will
    only influence $v$ at the next layer. Right: the received multiset is
    reduced by a permutation-invariant aggregator, then combined with the
    node's previous state to produce $\vect{h}_v^{(k)}$, following
    \eqref{eq:gnn-aggcomb}.}
  \label{fig:gnn-mp}
\end{figure}

\begin{algorithm}[htbp]
  \caption{Generic message-passing forward pass (MPNN)}
  \label{alg:gnn-forward}
  \begin{algorithmic}[1]
    \Require graph $G=(V,E)$, features $\{\vect{x}_v\}$, depth $K$,
             layers $\{(M_k, U_k)\}_{k=1}^{K}$, readout $R$
    \For{$v \in V$}
      \State $\vect{h}_v^{(0)} \gets \vect{x}_v$
    \EndFor
    \For{$k = 1, \dots, K$}
      \For{$v \in V$}
        \State $\vect{m}_v^{(k)} \gets
          \sum_{u \in \mathcal{N}(v)}
          M_k\bigl(\vect{h}_v^{(k-1)}, \vect{h}_u^{(k-1)},
                   \vect{e}_{uv}\bigr)$
          \Comment{messages, Eq.~\eqref{eq:gnn-message}}
      \EndFor
      \For{$v \in V$}
        \State $\vect{h}_v^{(k)} \gets
          U_k\bigl(\vect{h}_v^{(k-1)}, \vect{m}_v^{(k)}\bigr)$
          \Comment{update, Eq.~\eqref{eq:gnn-update}}
      \EndFor
    \EndFor
    \State \Return node states $\{\vect{h}_v^{(K)}\}$, or
      $\hat{\vect{y}}_G = R\bigl(\{\vect{h}_v^{(K)}\}\bigr)$ for
      graph-level tasks
  \end{algorithmic}
\end{algorithm}

\begin{remark}
The two inner loops of Algorithm~\ref{alg:gnn-forward} are never executed
node by node in practice: with sum or mean aggregation the whole layer
collapses into a pair of sparse--dense matrix products (cf.\
\eqref{eq:gnn-gcnlayer}), so a full propagation step costs
$\mathcal{O}(|E| \cdot d)$ — linear in the number of edges.
\end{remark}

% ----------------------------------------------------------------------------
\section{Graph Convolutional Networks}\label{sec:gnn-gcn}
% ----------------------------------------------------------------------------

The GCN of Kipf and Welling~\cite{kipf2017} descends from spectral graph
theory. On a graph, the Fourier basis is provided by the eigenvectors of
the normalized graph Laplacian
$\mat{L} = \mat{I} - \mat{D}^{-1/2}\mat{A}\mat{D}^{-1/2}
= \mat{U}\mat{\Lambda}\mat{U}\transp$, and a spectral convolution with
filter $g_\theta$ acts on a signal $\vect{x} \in \R^n$ as
\begin{equation}
  g_\theta \star \vect{x}
  = \mat{U}\, g_\theta(\mat{\Lambda})\, \mat{U}\transp \vect{x}.
  \label{eq:gnn-spectral}
\end{equation}
Evaluating \eqref{eq:gnn-spectral} exactly requires the full
eigendecomposition — $\mathcal{O}(n^3)$, prohibitive beyond small graphs.
Truncating a Chebyshev expansion of $g_\theta$ at first order, and tying
its two remaining coefficients, collapses the filter to a strictly local
operation:
\begin{equation}
  g_\theta \star \vect{x}
  \;\approx\;
  \theta \bigl(\mat{I} + \mat{D}^{-1/2}\mat{A}\mat{D}^{-1/2}\bigr)\,
  \vect{x}.
  \label{eq:gnn-cheby}
\end{equation}
The operator in \eqref{eq:gnn-cheby} has eigenvalues in $[0,2]$; stacking
many such layers can therefore amplify or shrink signals. The
\emph{renormalization trick} restores stability by adding self-loops
\emph{before} normalizing:
\begin{equation}
  \tilde{\mat{A}} = \mat{A} + \mat{I},
  \qquad
  \tilde{D}_{ii} = \sum_j \tilde{A}_{ij},
  \qquad
  \hat{\mat{A}}
  = \tilde{\mat{D}}^{-1/2}\, \tilde{\mat{A}}\, \tilde{\mat{D}}^{-1/2}.
  \label{eq:gnn-ahat}
\end{equation}
With $\mat{H}^{(0)} = \mat{X}$, the celebrated layer-wise propagation
rule reads
\begin{equation}
  \mat{H}^{(\ell+1)}
  = \varphi\bigl(\hat{\mat{A}}\, \mat{H}^{(\ell)}\, \mat{W}^{(\ell)}\bigr),
  \label{eq:gnn-gcnlayer}
\end{equation}
with $\mat{W}^{(\ell)}$ the trainable weights and $\varphi$ typically the
ReLU. Equation~\eqref{eq:gnn-gcnlayer} is an instance of
\eqref{eq:gnn-aggcomb}: written for a single node it becomes a
degree-weighted mean over the closed neighbourhood,
\begin{equation}
  \vect{h}_v^{(\ell+1)}
  = \varphi\Biggl(
      \sum_{u \in \mathcal{N}(v) \cup \{v\}}
      \frac{1}{\sqrt{\tilde{d}_v\, \tilde{d}_u}}\,
      \mat{W}^{(\ell)} \vect{h}_u^{(\ell)}
    \Biggr).
  \label{eq:gnn-gcnnode}
\end{equation}
The symmetric normalization $1/\sqrt{\tilde d_v \tilde d_u}$ downweights
messages that either \emph{leave} or \emph{enter} a high-degree hub, and
keeps the propagation operator symmetric, hence with a real spectrum.

For semi-supervised node classification — the task that made the GCN
famous — a two-layer network suffices:
\begin{equation}
  \mat{Z} = \softmax\Bigl(
    \hat{\mat{A}}\,
    \operatorname{ReLU}\bigl(\hat{\mat{A}} \mat{X} \mat{W}^{(0)}\bigr)\,
    \mat{W}^{(1)}
  \Bigr),
  \label{eq:gnn-gcntwo}
\end{equation}
trained by minimizing the cross-entropy over the (small) labelled subset
$V_L \subset V$ only,
\begin{equation}
  \Loss(\theta)
  = -\sum_{v \in V_L} \sum_{c=1}^{C} Y_{vc} \ln Z_{vc},
  \label{eq:gnn-gcnloss}
\end{equation}
while the propagation through $\hat{\mat{A}}$ spreads label information
to the unlabelled nodes — the graph structure itself acts as the
regularizer.

\begin{remark}[Over-smoothing and transductivity]\label{rem:gnn-oversmooth}
Repeated multiplication by $\hat{\mat{A}}$ is a low-pass filter on the
graph: as depth grows, all node states converge towards a
degree-dependent stationary vector and become indistinguishable. Deep
GCNs therefore \emph{lose} discriminative power; in practice two or three
layers are optimal, and deeper stacks require residual connections or
normalization to remain trainable. A second limitation is that
\eqref{eq:gnn-gcntwo} needs the full matrix $\hat{\mat{A}}$ at training
time: the vanilla GCN is \emph{transductive} and cannot embed nodes
unseen during training.
\end{remark}

% ----------------------------------------------------------------------------
\section{GraphSAGE: Inductive Learning by Sampled Aggregation}
\label{sec:gnn-sage}
% ----------------------------------------------------------------------------

GraphSAGE~\cite{hamilton2017} removes both limitations of
Remark~\ref{rem:gnn-oversmooth} at once: it learns \emph{aggregator
functions} rather than per-node embeddings, and it evaluates them on
\emph{sampled} fixed-size neighbourhoods $\mathcal{S}(v) \subseteq
\mathcal{N}(v)$ with $|\mathcal{S}(v)| = s$, so that the cost per node is
bounded regardless of the degree distribution. One layer performs
\begin{align}
  \vect{h}_{\mathcal{N}(v)}^{(k)}
  &= \operatorname{AGG}_k\bigl(
      \{\!\!\{\vect{h}_u^{(k-1)} : u \in \mathcal{S}(v)\}\!\!\}\bigr),
  \label{eq:gnn-sageagg}\\
  \vect{h}_v^{(k)}
  &= \varphi\Bigl(\mat{W}^{(k)}
      \bigl[\vect{h}_v^{(k-1)} \,\Vert\, \vect{h}_{\mathcal{N}(v)}^{(k)}
      \bigr]\Bigr),
  \qquad
  \vect{h}_v^{(k)} \leftarrow
  \frac{\vect{h}_v^{(k)}}{\bigl\lVert \vect{h}_v^{(k)} \bigr\rVert_2},
  \label{eq:gnn-sageupd}
\end{align}
where $\Vert$ denotes concatenation. Concatenating — rather than summing
— the self-state with the neighbourhood summary acts as a skip
connection that preserves the node's own identity through depth. Two of
the proposed aggregators are the mean and the max-pooling aggregator,
\begin{equation}
  \operatorname{AGG}^{\text{mean}}
  = \frac{1}{|\mathcal{S}(v)|} \sum_{u \in \mathcal{S}(v)}
    \vect{h}_u^{(k-1)},
  \label{eq:gnn-sagemean}
\end{equation}
\begin{equation}
  \operatorname{AGG}^{\text{pool}}
  = \max_{u \in \mathcal{S}(v)}
    \varphi\bigl(\mat{W}_{\text{pool}}\, \vect{h}_u^{(k-1)}
                 + \vect{b}\bigr),
  \label{eq:gnn-sagepool}
\end{equation}
the max taken element-wise (a third variant applies an LSTM to a random
permutation of the neighbours — expressive, but not
permutation-invariant). Because the aggregators are shared functions of
local structure, a trained GraphSAGE model embeds \emph{previously unseen
nodes} — and even entirely new graphs — by simply running
\eqref{eq:gnn-sageagg}--\eqref{eq:gnn-sageupd} on their neighbourhoods:
this is what \emph{inductive} means here.

When no labels are available, GraphSAGE is trained with a random-walk
co-occurrence loss with negative sampling,
\begin{equation}
  J(\vect{z}_u)
  = -\ln \sigma\bigl(\vect{z}_u\transp \vect{z}_v\bigr)
    - Q \cdot \E_{v_n \sim P_n}
      \bigl[\ln \sigma\bigl(-\vect{z}_u\transp \vect{z}_{v_n}\bigr)\bigr],
  \label{eq:gnn-sageloss}
\end{equation}
which pulls together the embeddings of nodes $u, v$ that co-occur on
short random walks and pushes $\vect{z}_u$ away from $Q$ negative
samples $v_n$ drawn from a noise distribution $P_n$; here $\sigma$ is the
logistic sigmoid. The supervised variant simply replaces
\eqref{eq:gnn-sageloss} with the cross-entropy \eqref{eq:gnn-gcnloss} on
the batch. Algorithm~\ref{alg:gnn-sage} gives the complete minibatch
estimation procedure; the unrolled sampling it induces is visualized in
Figure~\ref{fig:gnn-tree}.

\begin{algorithm}[htbp]
  \caption{GraphSAGE minibatch training with neighbour sampling
           (supervised)}
  \label{alg:gnn-sage}
  \begin{algorithmic}[1]
    \Require graph $G$, features $\{\vect{x}_v\}$, labels on $V_L$,
             depth $K$, sample sizes $s_1, \dots, s_K$,
             learning rate $\eta$
    \While{not converged}
      \State sample a batch $B \subseteq V_L$;\quad $B^{(K)} \gets B$
      \For{$k = K, \dots, 1$}
        \Comment{backward neighbourhood expansion}
        \State $B^{(k-1)} \gets B^{(k)} \cup
          \bigcup_{v \in B^{(k)}} \mathcal{S}_k(v)$,
          \quad $|\mathcal{S}_k(v)| = s_k$
      \EndFor
      \State $\vect{h}_v^{(0)} \gets \vect{x}_v$
             for all $v \in B^{(0)}$
      \For{$k = 1, \dots, K$}
        \For{$v \in B^{(k)}$}
          \State $\vect{h}_{\mathcal{N}(v)}^{(k)} \gets$
            aggregate over $\mathcal{S}_k(v)$ by \eqref{eq:gnn-sageagg}
          \State $\vect{h}_v^{(k)} \gets$ combine and normalize by
            \eqref{eq:gnn-sageupd}
        \EndFor
      \EndFor
      \State $\Loss \gets -\frac{1}{|B|} \sum_{v \in B}
        \sum_{c} Y_{vc} \ln
        \softmax\bigl(\mat{W}_{\text{out}}\vect{h}_v^{(K)}\bigr)_c$
      \State $\theta \gets \theta - \eta\, \nabla_\theta \Loss$
        \Comment{SGD or Adam step}
    \EndWhile
  \end{algorithmic}
\end{algorithm}

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[scale=1.0]
    % root
    \node[noutput] (r) at (0,0) {$v$};
    % level 1
    \node[nhidden] (a1) at (-3.0,-1.9) {$u_1$};
    \node[nhidden] (a2) at (0,-1.9)    {$u_2$};
    \node[nhidden] (a3) at (3.0,-1.9)  {$u_3$};
    % level 2
    \node[ninput] (b1) at (-4.4,-3.8) {$w_1$};
    \node[ninput] (b2) at (-3.0,-3.8) {$w_2$};
    \node[ninput] (b3) at (-1.6,-3.8) {$w_3$};
    \node[ninput] (b4) at (0.0,-3.8)  {$w_4$};
    \node[ninput] (b5) at (1.6,-3.8)  {$w_5$};
    \node[ninput] (b6) at (3.0,-3.8)  {$w_6$};
    \node[ninput] (b7) at (4.4,-3.8)  {$w_7$};
    % arrows upward (aggregation direction)
    \draw[fleche, chidden!85!black] (a1) -- (r);
    \draw[fleche, chidden!85!black] (a2) -- (r);
    \draw[fleche, chidden!85!black] (a3) -- (r);
    \draw[fleche, cinput!80!black] (b1) -- (a1);
    \draw[fleche, cinput!80!black] (b2) -- (a1);
    \draw[fleche, cinput!80!black] (b3) -- (a2);
    \draw[fleche, cinput!80!black] (b4) -- (a2);
    \draw[fleche, cinput!80!black] (b5) -- (a3);
    \draw[fleche, cinput!80!black] (b6) -- (a3);
    \draw[fleche, cinput!80!black] (b7) -- (a3);
    % depth annotations on the right
    \node[etiquette, anchor=west] at (5.4,0)
      {layer $k=2$: $\vect{h}_v^{(2)}$};
    \node[etiquette, anchor=west] at (5.4,-1.9)
      {layer $k=1$: $\vect{h}_{u_i}^{(1)}$};
    \node[etiquette, anchor=west] at (5.4,-3.8)
      {layer $k=0$: $\vect{h}_{w_j}^{(0)} = \vect{x}_{w_j}$};
    % brace for sampled neighbourhoods
    \draw[decorate, decoration={brace, mirror, amplitude=5pt},
          black!60]
      (-4.9,-4.5) -- (4.9,-4.5)
      node[etiquette, midway, below=7pt]
      {sampled two-hop neighbourhood:
       $w_j \in \mathcal{S}_1(u_i)$, $u_i \in \mathcal{S}_2(v)$};
  \end{tikzpicture}
  \caption{The computation tree unrolled by a depth-2 GraphSAGE forward
    pass at node $v$ (Algorithm~\ref{alg:gnn-sage}). Layer-0 states of
    the sampled two-hop nodes (blue) are aggregated into layer-1 states
    of the sampled one-hop neighbours (orange), which are in turn
    aggregated into the final state of $v$ (red). Sampling fixes the
    branching factor of the tree, bounding the cost independently of the
    node degrees.}
  \label{fig:gnn-tree}
\end{figure}

% ----------------------------------------------------------------------------
\section{Graph Attention Networks}\label{sec:gnn-gat}
% ----------------------------------------------------------------------------

The GCN weighs the message from $u$ to $v$ by the purely structural
coefficient $1/\sqrt{\tilde d_v \tilde d_u}$ of
\eqref{eq:gnn-gcnnode}: two neighbours with equal degrees are equally
important, whatever their features. Graph attention
networks~\cite{velickovic2018} replace this fixed coefficient with a
\emph{learned}, feature-dependent one, importing the attention mechanism
into message passing. With a shared projection
$\mat{W} \in \R^{F' \times F}$ and an attention vector
$\vect{a} \in \R^{2F'}$, the unnormalized score of edge $(j \to i)$ is
\begin{equation}
  e_{ij}
  = \operatorname{LeakyReLU}\Bigl(
      \vect{a}\transp
      \bigl[\mat{W}\vect{h}_i \,\Vert\, \mat{W}\vect{h}_j\bigr]
    \Bigr),
  \label{eq:gnn-gatlogit}
\end{equation}
normalized by a softmax masked to the neighbourhood (including $i$
itself),
\begin{equation}
  \alpha_{ij}
  = \frac{\exp(e_{ij})}
         {\sum_{k \in \mathcal{N}(i) \cup \{i\}} \exp(e_{ik})},
  \label{eq:gnn-gatalpha}
\end{equation}
and the node update is the attention-weighted aggregation
\begin{equation}
  \vect{h}_i'
  = \varphi\Biggl(
      \sum_{j \in \mathcal{N}(i) \cup \{i\}}
      \alpha_{ij}\, \mat{W} \vect{h}_j
    \Biggr).
  \label{eq:gnn-gatupd}
\end{equation}
As in the Transformer, several attention heads stabilize learning and
attend to different relational patterns; hidden layers concatenate the
heads while the final prediction layer averages them:
\begin{equation}
  \vect{h}_i'
  = \bigl\Vert_{k=1}^{K} \varphi\Bigl(
      \textstyle\sum_{j} \alpha_{ij}^{k}\, \mat{W}^{k} \vect{h}_j
    \Bigr),
  \qquad
  \vect{h}_i'
  = \varphi\Bigl(
      \tfrac{1}{K} \textstyle\sum_{k=1}^{K} \sum_{j}
      \alpha_{ij}^{k}\, \mat{W}^{k} \vect{h}_j
    \Bigr)
  \quad \text{(final layer)}.
  \label{eq:gnn-gatmulti}
\end{equation}
Figure~\ref{fig:gnn-gat} shows the resulting anisotropic aggregation:
unlike in the GCN, the incoming edges of a node carry \emph{different}
weights, and those weights change with the node features rather than
being frozen by the topology. GAT is inductive for the same reason
GraphSAGE is — all parameters ($\mat{W}$, $\vect{a}$) are shared
functions, none is tied to a node identity — and the attention
coefficients offer a degree of built-in interpretability: inspecting
$\alpha_{ij}$ reveals which neighbours drove a prediction.

\begin{remark}
The scoring function \eqref{eq:gnn-gatlogit} applies its nonlinearity
\emph{after} the inner product with $\vect{a}$; the neighbour ranking it
induces is therefore shared by all query nodes (\emph{static}
attention). Moving the nonlinearity inside,
$e_{ij} = \vect{a}\transp \operatorname{LeakyReLU}
(\mat{W}[\vect{h}_i \Vert \vect{h}_j])$, yields the strictly more
expressive dynamic variant known as GATv2.
\end{remark}

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[scale=1.0]
    \node[noutput] (v)  at (0,0)      {$i$};
    \node[ninput]  (u1) at (-2.3,1.6) {$j_1$};
    \node[ninput]  (u2) at (-2.7,-0.6){$j_2$};
    \node[ninput]  (u3) at (-0.4,-2.3){$j_3$};
    \node[ninput]  (u4) at (2.1,1.6)  {$j_4$};
    % head 1 (blue, thickness ~ alpha), arcs on one side of each chord
    \draw[fleche, cinput!80!black, line width=1.8pt]
      (u1) to[bend left=16] (v);
    \draw[fleche, cinput!80!black, line width=0.6pt]
      (u2) to[bend left=16] (v);
    \draw[fleche, cinput!80!black, line width=1.1pt]
      (u3) to[bend left=16] (v);
    \draw[fleche, cinput!80!black, line width=1.1pt]
      (u4) to[bend right=16] (v);
    % head 2 (orange), arcs on the other side
    \draw[fleche, chidden!85!black, line width=0.7pt]
      (u1) to[bend right=16] (v);
    \draw[fleche, chidden!85!black, line width=1.7pt]
      (u2) to[bend right=16] (v);
    \draw[fleche, chidden!85!black, line width=0.8pt]
      (u3) to[bend right=16] (v);
    \draw[fleche, chidden!85!black, line width=1.2pt]
      (u4) to[bend left=16] (v);
    % coefficient labels, colour-coded by head, pinned off the arcs
    \node[etiquette, text=cinput!80!black]   at (-0.85, 1.30) {$0.42$};
    \node[etiquette, text=chidden!85!black]  at (-2.05, 0.55) {$0.15$};
    \node[etiquette, text=cinput!80!black]   at (-1.55, 0.10) {$0.11$};
    \node[etiquette, text=chidden!85!black]  at (-1.75,-1.10) {$0.39$};
    \node[etiquette, text=cinput!80!black]   at (-0.95,-1.35) {$0.23$};
    \node[etiquette, text=chidden!85!black]  at ( 0.55,-1.45) {$0.18$};
    \node[etiquette, text=cinput!80!black]   at ( 1.05, 1.30) {$0.24$};
    \node[etiquette, text=chidden!85!black]  at ( 1.90, 0.55) {$0.28$};
    % legend
    \node[etiquette, anchor=west, text=cinput!80!black]
      at (4.0,0.7) {head $k=1$: coefficients $\alpha_{ij}^{1}$};
    \node[etiquette, anchor=west, text=chidden!85!black]
      at (4.0,0.1) {head $k=2$: coefficients $\alpha_{ij}^{2}$};
    \node[etiquette, anchor=west, align=left] at (4.0,-0.9)
      {line width $\propto \alpha_{ij}^{k}$;\\
       each head sums to $1$ over\\
       $\mathcal{N}(i)\cup\{i\}$ (self-loop\\
       omitted for clarity)};
  \end{tikzpicture}
  \caption{Graph attention at node $i$,
    equations~\eqref{eq:gnn-gatlogit}--\eqref{eq:gnn-gatmulti}. Each of
    the two heads (blue, orange) computes its own normalized
    coefficients $\alpha_{ij}^{k}$ over the same neighbourhood; the
    thickness of each arrow is proportional to the learned coefficient.
    Structurally identical neighbours may thus receive very different
    weights, in contrast with the degree-based coefficients of the GCN
    in \eqref{eq:gnn-gcnnode}.}
  \label{fig:gnn-gat}
\end{figure}

% ----------------------------------------------------------------------------
\section{How Powerful Are GNNs? The Graph Isomorphism Network}
\label{sec:gnn-gin}
% ----------------------------------------------------------------------------

The freedom in choosing $\operatorname{AGG}$ in \eqref{eq:gnn-aggcomb}
raises a theoretical question: which graphs can a message-passing network
tell apart at all? Xu et al.~\cite{xu2019} answered it by relating GNNs
to the classical one-dimensional Weisfeiler--Lehman (1-WL) colour
refinement test, which iteratively re-hashes each node's colour together
with the multiset of its neighbours' colours.

\begin{theorem}[Expressive power of message passing]
\label{thm:gnn-wl}
Any GNN of the form \eqref{eq:gnn-aggcomb} maps two non-isomorphic graphs
to different embeddings only if the 1-WL test also distinguishes them:
message passing is \emph{at most} as discriminative as 1-WL. This upper
bound is attained if the aggregation, combination and readout functions
are all \emph{injective} on multisets~\cite{xu2019}.
\end{theorem}

Injectivity is where the common aggregators part ways. The mean loses
multiplicities — it cannot distinguish
$\{\!\!\{\vect{a}, \vect{a}, \vect{b}, \vect{b}\}\!\!\}$ from
$\{\!\!\{\vect{a}, \vect{b}\}\!\!\}$ — and the max loses everything but
the support; the \emph{sum} preserves both, and over countable feature
spaces sum-based aggregation composed with an MLP can represent any
multiset function.

\begin{property}[Aggregator ranking]\label{prop:gnn-agg}
In discriminative power over multisets,
$\mathrm{sum} \succ \mathrm{mean} \succ \mathrm{max}$: the mean captures
the distribution of neighbour features but not their multiplicities; the
max captures only the underlying set.
\end{property}

The graph isomorphism network makes the injective choice concrete, with
a learnable scalar $\epsilon^{(k)}$ that disambiguates the node's own
state from the neighbour sum, and an MLP as a universal approximator on
top:
\begin{equation}
  \vect{h}_v^{(k)}
  = \operatorname{MLP}^{(k)}\Bigl(
      \bigl(1 + \epsilon^{(k)}\bigr)\, \vect{h}_v^{(k-1)}
      + \sum_{u \in \mathcal{N}(v)} \vect{h}_u^{(k-1)}
    \Bigr).
  \label{eq:gnn-gin}
\end{equation}
For graph-level prediction, GIN concatenates a summed readout of
\emph{every} depth, retaining both local and global structure:
\begin{equation}
  \vect{h}_G
  = \bigl\Vert_{k=0}^{K}\,
    \sum_{v \in V} \vect{h}_v^{(k)}.
  \label{eq:gnn-ginread}
\end{equation}
By Theorem~\ref{thm:gnn-wl}, the network
\eqref{eq:gnn-gin}--\eqref{eq:gnn-ginread} is a \emph{maximally
powerful} message-passing GNN: whatever 1-WL can distinguish, GIN can
learn to distinguish.

\begin{remark}
The 1-WL ceiling is a genuine ceiling: no network of the form
\eqref{eq:gnn-aggcomb} can, for instance, count triangles or separate
certain pairs of regular graphs. Escaping it requires strictly more
machinery — higher-order message passing over node tuples, random node
identifiers, or positional and structural encodings appended to the
input features $\vect{x}_v$.
\end{remark}

% ----------------------------------------------------------------------------
\section{Prediction Heads and Training Objectives}\label{sec:gnn-heads}
% ----------------------------------------------------------------------------

The message-passing trunk of
Sections~\ref{sec:gnn-mp}--\ref{sec:gnn-gin} is shared by three families
of tasks, which differ only in the head applied to the final states
$\vect{z}_v = \vect{h}_v^{(K)}$:
\begin{align}
  \hat{\vect{y}}_v
  &= \softmax\bigl(\mat{W}_{\text{out}}\, \vect{z}_v\bigr)
  && \text{(node classification)},
  \label{eq:gnn-nodehead}\\
  s_{uv}
  &= \sigma\bigl(\vect{z}_u\transp \vect{z}_v\bigr)
  && \text{(link prediction)},
  \label{eq:gnn-linkhead}\\
  \hat{\vect{y}}_G
  &= \softmax\bigl(\mat{W}_G\, \vect{h}_G\bigr),
  \qquad \vect{h}_G \text{ from } \eqref{eq:gnn-ginread}
  && \text{(graph classification)}.
  \label{eq:gnn-graphhead}
\end{align}
Node and graph heads are trained with the cross-entropy
\eqref{eq:gnn-gcnloss}; the link-prediction head with the logistic loss
of \eqref{eq:gnn-sageloss}, treating observed edges as positives and
sampled non-edges as negatives. All four architectures of this chapter
slot into this scheme unchanged — the choice among GCN, GraphSAGE, GAT
and GIN is a choice of aggregation rule
(\eqref{eq:gnn-gcnnode}, \eqref{eq:gnn-sageagg},
\eqref{eq:gnn-gatupd}, \eqref{eq:gnn-gin}), not a choice of task.

These models power a remarkable range of applications: semi-supervised
classification of citation networks, molecular property prediction and
drug discovery (message passing over atoms and bonds), billion-node
recommender systems built on sampled aggregation, learned physics
simulation, traffic forecasting and protein structure prediction, where
attention over residue-pair graphs is a central ingredient. In every
case the inductive bias is the same: what a node \emph{is} should be
computable from what its neighbourhood \emph{looks like} — the
graph-structured analogue of the translation equivariance that motivated
convolutional networks.