---
title: Graph Neural Networks
module: Architectures
moduleNumber: 5
lessonNumber: 8
order: 508
summary: >
  A graph neural network learns on data with no grid and no canonical ordering:
  atoms in a molecule, users in a social network, road segments in a map. The
  unifying idea is message passing — each node repeatedly aggregates its
  neighbors' states and updates its own — built to respect the one symmetry
  graphs demand, permutation equivariance. We derive the message-passing
  framework, specialize it into GCN, GraphSAGE, GAT, and GIN, read off graph-level
  outputs, and bound what message passing can and cannot tell apart.
topics: [Architectures]
sources:
  - book: Goodfellow
    ref: "Ch. 9 — generalizing convolution beyond grids (GNNs postdate the 2016 text)"
---

A [convolutional network](/deep-learning/architectures/convolutional-networks)
exploits one fact: an image is a grid, so every pixel has the same number of
neighbors in the same fixed positions, and one shared kernel can slide across all
of them. A molecule, a citation network, a road map has no such regularity. Nodes
have different degrees, there is no "up" or "left", and relabeling the vertices
must not change the prediction. A **graph neural network** generalizes the
convolutional idea to this setting by replacing the fixed spatial stencil with a
node's _neighborhood_: each node aggregates information from the nodes it is
connected to, and reuses one shared transformation everywhere, exactly as a kernel
is reused at every position.[^gf-conv][^scarselli]

## Graph data

A graph fixes a set of entities and the relations between them, and attaches a
feature vector to each entity.

> **Definition (Attributed graph).** A graph $G = \parens{V, E}$ with node set $V$
> of size $n$ and edge set $E \subseteq V \times V$, equipped with node features
> $X \in \mathbb{R}^{n \times d}$ whose row $x_v$ describes node $v$, and an
> **adjacency matrix** $A \in \braces{0,1}^{n \times n}$ with $A_{uv} = 1$ iff
> $\parens{u,v} \in E$. The **neighborhood** of $v$ is $N\parens{v} = \set{u :
> A_{uv} = 1}$ and its **degree** is $\deg\parens{v} = \abs{N\parens{v}}$.

The adjacency matrix is the algebraic handle on the structure: a single
multiplication $\parens{AX}_v = \sum_{u \in N\parens{v}} x_u$ sums each node's
neighbors, which is the primitive every layer below is built from. Edges may
themselves carry features $e_{uv}$, and graphs may be directed or weighted, but
the unweighted undirected case covers every idea below.

$$
% caption: A small attributed graph: five nodes with feature vectors $x_v$, undirected edges,
% and the neighborhood $N(c) = \braces{a, b, d}$ highlighted around node $c$.
\begin{tikzpicture}[font=\small, >=stealth,
  nd/.style={circle, draw, black, thick, minimum size=8mm, inner sep=0pt},
  hi/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=8mm, inner sep=0pt, text=acc}]
  \definecolor{acc}{HTML}{2348F2}
  \node[hi]  (c) at (0,0)       {c};
  \node[nd]  (a) at (-1.9,1.1)  {a};
  \node[nd]  (b) at (-2.1,-1.1) {b};
  \node[nd]  (d) at (1.9,1.1)   {d};
  \node[nd]  (e) at (2.1,-1.1)  {e};
  % edges incident to c (accent)
  \draw[acc, thick] (c) -- (a);
  \draw[acc, thick] (c) -- (b);
  \draw[acc, thick] (c) -- (d);
  % other edges (black)
  \draw[black, thick] (a) -- (b);
  \draw[black, thick] (d) -- (e);
  % feature tags
  \node[font=\scriptsize, anchor=south east] at (-1.9,1.45) {$x_a$};
  \node[font=\scriptsize, anchor=north east] at (-2.1,-1.45) {$x_b$};
  \node[font=\scriptsize, anchor=south west] at (1.9,1.45)  {$x_d$};
  \node[font=\scriptsize, anchor=north west] at (2.1,-1.45) {$x_e$};
  \node[font=\scriptsize, text=acc, anchor=south] at (0,0.6) {$x_c$};
  \node[font=\footnotesize, text=acc, anchor=north] at (0,-1.9) {\texttt{neighbors of c: a, b, d}};
\end{tikzpicture}
$$

### Three task levels

What the network predicts determines where its outputs come from.

| Level | Output | Examples |
| --- | --- | --- |
| Node | one label per node | role in a social network, atom property |
| Edge | one label per pair | link prediction, relation type |
| Graph | one label per graph | molecule toxicity, solubility |

Node- and edge-level tasks read off the per-node representations directly; a
graph-level task must first pool the node representations into a single vector, the
**readout** step covered below.

### The symmetry that defines the problem

A graph carries no node ordering. We can store its nodes in any order we like, and
a permutation matrix $P$ relabels them: $X \mapsto PX$, $A \mapsto PAP^{\top}$. A
correct model must not depend on that arbitrary choice.[^bronstein]

> **Definition (Permutation invariance and equivariance).** A graph-level function
> $f\parens{X, A}$ is **permutation invariant** if $f\parens{PX, PAP^{\top}} =
> f\parens{X, A}$ for every permutation matrix $P$. A node-level function $F$ is
> **permutation equivariant** if $F\parens{PX, PAP^{\top}} = P\, F\parens{X, A}$:
> relabel the input and the outputs are relabeled the same way, nothing else
> changes.

Equivariance is the right constraint for the per-node layers (a node's new state
should follow it under relabeling), and invariance is the right constraint for the
final graph-level readout (the molecule is the same molecule however we number its
atoms). Every GNN layer below is built to be equivariant by construction, and the
readout to be invariant, because the symmetry is not a nicety: a model that lacked
it would have to learn the same fact $n!$ times over.

> **Theorem (Equivariant layers compose to an invariant network).** If each layer
> $F^{\parens{\ell}}$ is permutation equivariant and the readout $R$ is permutation
> invariant, then $R \circ F^{\parens{L}} \circ \cdots \circ F^{\parens{1}}$ is
> permutation invariant.

> **Proof.** Equivariance composes: $F^{\parens{2}}\parens{F^{\parens{1}}\parens{PX,
> PAP^{\top}}} = F^{\parens{2}}\parens{P\,F^{\parens{1}}\parens{X,A},\, PAP^{\top}} =
> P\,F^{\parens{2}}\parens{F^{\parens{1}}\parens{X,A}, A}$, and by induction the
> stack of $L$ layers is equivariant, producing $P\,H^{\parens{L}}$. Applying the
> invariant readout, $R\parens{P\,H^{\parens{L}}} = R\parens{H^{\parens{L}}}$, so the
> composite is invariant. $\qed$

## The message-passing framework

Almost every GNN is one template. A layer updates each node by collecting
**messages** from its neighbors, combining them with a permutation-invariant
**aggregate**, then mixing the result with the node's own state through an
**update**.[^gilmer]

> **Definition (Message passing).** Write $h_v^{\parens{\ell}}$ for the
> representation of node $v$ after $\ell$ layers, with $h_v^{\parens{0}} = x_v$.
> One layer computes
> $$
> m_v^{\parens{\ell+1}} = \aggregate\parens{\set{ h_u^{\parens{\ell}} :
>   u \in N\parens{v} }},
> $$
> $$
> h_v^{\parens{\ell+1}} = \update\parens{ h_v^{\parens{\ell}},\,
>   m_v^{\parens{\ell+1}} },
> $$
> where $\aggregate$ is a permutation-invariant set function (sum,
> mean, max) and $\update$ is a learnable map, typically a linear
> layer followed by a nonlinearity.

Because $\aggregate$ takes a _set_ and ignores order, the layer is
permutation equivariant for free — the property the previous theorem
demands. The aggregate is where the entire design space lives: the variants below
differ only in how they weight and combine the neighbor states.

Consider the shapes. A hidden state $h_v^{\parens{\ell}} \in
\mathbb{R}^{d_\ell}$ is one vector per node; stacked over all $n$ nodes it is the
matrix $H^{\parens{\ell}} \in \mathbb{R}^{n \times d_\ell}$. The aggregate reads a
variable-size set of $d_\ell$-vectors (node $v$ contributes $\deg\parens{v}$ of
them) and returns a single $d_\ell$-vector $m_v^{\parens{\ell+1}} \in
\mathbb{R}^{d_\ell}$; a set of any size in, one fixed vector out, which is what lets
one layer serve nodes of every degree. The update takes the pair
$\parens{h_v^{\parens{\ell}}, m_v^{\parens{\ell+1}}} \in \mathbb{R}^{d_\ell} \times
\mathbb{R}^{d_\ell}$ through a shared weight $W^{\parens{\ell}} \in
\mathbb{R}^{d_\ell \times d_{\ell+1}}$ and produces $h_v^{\parens{\ell+1}} \in
\mathbb{R}^{d_{\ell+1}}$. Only the width $d_\ell$ changes across layers; the same
$W^{\parens{\ell}}$ is applied at every node, the parameter sharing that mirrors a
convolutional kernel.

$$
% caption: One message-passing layer at node $v$: each neighbor sends a message, an order-invariant aggregate combines them, and an update mixes the result with $h_v$.
\begin{tikzpicture}[font=\small, >=stealth,
  nd/.style={circle, draw, black, thick, minimum size=8mm, inner sep=0pt, font=\scriptsize},
  vv/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=9mm, inner sep=0pt, font=\scriptsize, text=acc},
  agg/.style={draw, black, thick, minimum width=14mm, minimum height=8mm, font=\scriptsize, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % neighbors on the left
  \node[nd] (u1) at (0,1.5)  {$h_{u_1}$};
  \node[nd] (u2) at (0,0)    {$h_{u_2}$};
  \node[nd] (u3) at (0,-1.5) {$h_{u_3}$};
  % aggregate box
  \node[agg] (ag) at (3.0,0) {aggregate\\(sum/mean/max)};
  % update box
  \node[agg, draw=green, text=green] (up) at (6.4,0) {\texttt{update}};
  % node v new state
  \node[vv] (v) at (9.2,0) {$h_v^{+}$};
  % old v feeding update
  \node[nd, draw=acc, text=acc] (vold) at (6.4,1.9) {$h_v$};
  % messages
  \draw[->, black, thick] (u1) -- (ag) node[midway, above, font=\scriptsize, sloped] {msg};
  \draw[->, black, thick] (u2) -- (ag);
  \draw[->, black, thick] (u3) -- (ag) node[midway, below, font=\scriptsize, sloped] {msg};
  \draw[->, black, thick] (ag) -- (up);
  \draw[->, acc, thick] (vold) -- (up);
  \draw[->, green, thick] (up) -- (v);
\end{tikzpicture}
$$

The algorithm is the template run for $L$ rounds. After round $\ell$, a node's
state depends on its $\ell$-hop neighborhood, so depth controls how far information
travels, the graph analogue of a receptive field.

```algorithm
caption: $\textsc{MessagePassing}(X, A, L)$ — $L$ rounds of neighbor aggregation
$h_v^{(0)} \gets x_v$ for each $v \in V$ // initialize with input features
for $\ell \gets 0$ to $L - 1$ do
  for each node $v \in V$ do
    $m_v \gets \textsc{Aggregate}(\{ h_u^{(\ell)} : u \in N(v) \})$ // order-invariant
    $h_v^{(\ell+1)} \gets \textsc{Update}(h_v^{(\ell)}, m_v)$ // learnable, e.g. $\sigma(W \cdot)$
return $\{ h_v^{(L)} : v \in V \}$ // final node representations
```

## Graph convolutional network (GCN)

The simplest useful instance fixes the aggregate to a _normalized neighbor sum_ and
the update to one shared linear map plus a nonlinearity. Collecting all nodes into
the matrix $H^{\parens{\ell}} \in \mathbb{R}^{n \times d}$, the GCN layer is a
single propagation rule.[^kipf]

> **Definition (GCN layer).** Let $\hat A = A + I$ add self-loops so a node keeps
> its own state, and let $\hat D = \diag\parens{\sum_u \hat A_{vu}}$
> be the degree matrix of $\hat A$. The graph convolutional layer is
> $$
> H^{\parens{\ell+1}} = \sigma\parens{ \hat D^{-1/2}\, \hat A\, \hat D^{-1/2}\,
>   H^{\parens{\ell}}\, W^{\parens{\ell}} },
> $$
> with shared weights $W^{\parens{\ell}} \in \mathbb{R}^{d \times d'}$ and an
> elementwise nonlinearity $\sigma$ (typically $\ReLU$).

### Why symmetric normalization

A raw sum $\hat A H$ lets high-degree nodes dominate, since their messages add up
over many neighbors and blow up the activation scale. Per node $v$, the symmetric
normalization weights the message from neighbor $u$ by $1/\sqrt{\deg\parens{v}
\deg\parens{u}}$:

$$
h_v^{\parens{\ell+1}} = \sigma\parens{ \sum_{u \in N\parens{v} \cup \set{v}}
  \frac{1}{\sqrt{\hat d_v\, \hat d_u}}\, W^{\parens{\ell}\top} h_u^{\parens{\ell}} },
\qquad \hat d_v = \deg\parens{v} + 1.
$$

To see where the $\hat D^{-1/2}\hat A\hat D^{-1/2}$ factor comes from, start from
the raw propagation $\hat A H$ and ask for the least destructive way to control its
scale. Row-normalizing, $\hat D^{-1}\hat A H$, replaces the neighbor sum by a
neighbor _mean_ and fixes the scale, but it treats the message asymmetrically: the
weight node $v$ puts on neighbor $u$ is $1/\hat d_v$, which ignores $u$'s own
degree entirely. The symmetric split $\hat D^{-1/2}\hat A\hat D^{-1/2}$ takes half
the normalization from each end. Reading off entry $\parens{v,u}$,

$$
\parens{\hat D^{-1/2}\hat A\hat D^{-1/2}}_{vu}
  = \hat D^{-1/2}_{vv}\, \hat A_{vu}\, \hat D^{-1/2}_{uu}
  = \frac{1}{\sqrt{\hat d_v}} \cdot 1 \cdot \frac{1}{\sqrt{\hat d_u}}
  = \frac{1}{\sqrt{\hat d_v\, \hat d_u}}
  \;=\; c_{vu},
$$

for every $u \in N\parens{v} \cup \set{v}$ (and $0$ off the graph), which matches
the coefficient in the per-node sum above. Multiplying the propagated matrix by
$W^{\parens{\ell}}$ and applying $\sigma$ recovers the layer definition; writing the
$vu$ entry out and summing over $u$ turns the matrix form into the per-node form and
back. The symmetric factor keeps activation magnitudes stable across nodes of widely
different degree, and discounts messages from popular neighbors (high $\hat d_u$)
that are informative about everyone and therefore about no one in particular. The
choice is not arbitrary: $\hat D^{-1/2}\hat A \hat D^{-1/2}$ is a first-order
approximation to a spectral graph convolution, the localized filter that drops out
of a Chebyshev expansion of the graph Laplacian's eigenbasis.[^bruna]

$$
% caption: A GCN layer at node $v$: self-loop included, neighbor states scaled by
% $c_{vu} = 1/\sqrt{\hat d_v \hat d_u}$, summed, projected by $W$, then passed through ReLU.
\begin{tikzpicture}[font=\small, >=stealth,
  nd/.style={circle, draw, black, thick, minimum size=7mm, inner sep=0pt, font=\scriptsize},
  vv/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=8mm, inner sep=0pt, font=\scriptsize, text=acc},
  op/.style={draw, black, thick, minimum width=11mm, minimum height=7mm, font=\scriptsize, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \node[nd] (u1) at (0,1.7)  {$h_{u_1}$};
  \node[vv] (v0) at (0,0)    {$h_v$};
  \node[nd] (u2) at (0,-1.7) {$h_{u_2}$};
  % scaling labels on edges
  \node[op] (sum) at (3.3,0) {\texttt{weighted}\\\texttt{sum}};
  \node[op, draw=acc, text=acc] (W) at (6.0,0) {$W$};
  \node[op, draw=green, text=green] (sig) at (8.3,0) {ReLU};
  \node[vv] (vout) at (10.6,0) {$h_v^{+}$};
  \draw[->, black, thick] (u1) -- (sum) node[midway, above, font=\scriptsize, sloped] {scale $c_{v u_1}$};
  \draw[->, acc, thick]   (v0) -- (sum) node[midway, above, font=\scriptsize] {self};
  \draw[->, black, thick] (u2) -- (sum) node[midway, below, font=\scriptsize, sloped] {scale $c_{v u_2}$};
  \draw[->, acc, thick]   (sum) -- (W);
  \draw[->, green, thick] (W) -- (sig);
  \draw[->, green, thick] (sig) -- (vout);
\end{tikzpicture}
$$

### A GCN layer on four nodes, by hand

One numeric pass fixes every symbol. Take a four-node graph: a triangle on nodes
$1,2,3$ with a pendant node $4$ hanging off node $3$. Its adjacency matrix, and the
self-looped $\hat A = A + I$, are

$$
A = \begin{pmatrix} 0&1&1&0 \\ 1&0&1&0 \\ 1&1&0&1 \\ 0&0&1&0 \end{pmatrix},
\qquad
\hat A = \begin{pmatrix} 1&1&1&0 \\ 1&1&1&0 \\ 1&1&1&1 \\ 0&0&1&1 \end{pmatrix}.
$$

Row-summing $\hat A$ gives the self-looped degrees $\hat d = \parens{3,3,4,2}$, so
$\hat D = \diag\parens{3,3,4,2}$ and $\hat D^{-1/2} =
\diag\parens{1/\sqrt 3,\, 1/\sqrt 3,\, 1/2,\, 1/\sqrt 2}$. The
normalized propagation matrix $\hat A' = \hat D^{-1/2}\hat A\hat D^{-1/2}$ has entry
$\hat A'_{vu} = 1/\sqrt{\hat d_v \hat d_u}$ wherever $\hat A_{vu} = 1$:

$$
\hat A' =
\begin{pmatrix}
\tfrac{1}{3} & \tfrac{1}{3} & \tfrac{1}{\sqrt{12}} & 0 \\[2pt]
\tfrac{1}{3} & \tfrac{1}{3} & \tfrac{1}{\sqrt{12}} & 0 \\[2pt]
\tfrac{1}{\sqrt{12}} & \tfrac{1}{\sqrt{12}} & \tfrac{1}{4} & \tfrac{1}{\sqrt{8}} \\[2pt]
0 & 0 & \tfrac{1}{\sqrt{8}} & \tfrac{1}{2}
\end{pmatrix}
\approx
\begin{pmatrix}
0.33 & 0.33 & 0.29 & 0 \\
0.33 & 0.33 & 0.29 & 0 \\
0.29 & 0.29 & 0.25 & 0.35 \\
0 & 0 & 0.35 & 0.50
\end{pmatrix}.
$$

Give each node a scalar feature ($d_\ell = 1$) $H = \parens{1, 0, 1, 0}^{\top}$ and
run the propagation. Node $3$ (self-degree $4$, neighbors $1,2,4$) mixes

$$
\parens{\hat A' H}_3 = \underbrace{0.29}_{c_{31}} \cdot 1 + \underbrace{0.29}_{c_{32}}
  \cdot 0 + \underbrace{0.25}_{c_{33}} \cdot 1 + \underbrace{0.35}_{c_{34}} \cdot 0
  = 0.54,
$$

and doing every row gives $\hat A' H \approx \parens{0.62,\, 0.62,\, 0.54,\,
0.35}^{\top}$. With a scalar weight $W = 1$ and $\sigma = \ReLU$
(the identity here, since every entry is positive), the first layer output is
$H^{\parens{1}} \approx \parens{0.62, 0.62, 0.54, 0.35}^{\top}$. Two facts read
straight off the numbers: nodes $1$ and $2$ end up identical because the graph is
symmetric under swapping them (permutation equivariance in action), and the isolated
feature at node $4$ has bled outward from $0$ toward its neighbors, a single step of
the smoothing that, iterated, becomes over-smoothing.

$$
% caption: The worked four-node graph: a triangle on nodes $1,2,3$ with pendant node $4$.
% Self-looped degrees $\hat d = (3,3,4,2)$ set the GCN coefficients $c_{vu} = 1/\sqrt{\hat d_v \hat d_u}$.
\begin{tikzpicture}[font=\small, >=stealth,
  nd/.style={circle, draw, black, thick, minimum size=8mm, inner sep=0pt},
  hi/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=8mm, inner sep=0pt, text=acc}]
  \definecolor{acc}{HTML}{2348F2}
  \node[nd] (n1) at (0,2)    {1};
  \node[nd] (n2) at (0,0)    {2};
  \node[hi] (n3) at (2.4,1)  {3};
  \node[nd] (n4) at (4.8,1)  {4};
  \draw[black, thick] (n1) -- (n2);
  \draw[acc, thick]   (n1) -- (n3);
  \draw[acc, thick]   (n2) -- (n3);
  \draw[acc, thick]   (n3) -- (n4);
  \node[font=\footnotesize, anchor=south, text=acc] at (2.4,1.5) {\texttt{deg 3}};
  \node[font=\footnotesize, anchor=east]  at (-0.6,2)  {\texttt{x=1}};
  \node[font=\footnotesize, anchor=east]  at (-0.6,0)  {\texttt{x=0}};
  \node[font=\footnotesize, anchor=west]  at (5.4,1)   {\texttt{x=0}};
\end{tikzpicture}
$$

$$
% caption: GCN layer as a matrix pipeline. The $n\times n$ propagation $\hat A' = \hat D^{-1/2}\hat A\hat D^{-1/2}$
% mixes rows (nodes) but not columns; the $d_\ell\times d_{\ell+1}$ weight $W$ mixes columns (features) but not rows.
\begin{tikzpicture}[font=\small, >=stealth,
  mat/.style={draw, black, thick, minimum width=15mm, minimum height=11mm, font=\scriptsize, align=center},
  op/.style={draw, black, thick, minimum width=10mm, minimum height=8mm, font=\scriptsize, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \node[mat] (H) at (0,0) {\texttt{H (l)}\\\texttt{n x d}};
  \node[op, draw=acc, text=acc] (P) at (2.9,0) {\texttt{A' norm}\\\texttt{n x n}};
  \node[mat] (M) at (5.6,0) {\texttt{A' H}\\\texttt{n x d}};
  \node[op, draw=acc, text=acc] (W) at (8.3,0) {\texttt{W (l)}\\\texttt{d x d'}};
  \node[op, draw=green, text=green] (S) at (10.7,0) {\texttt{ReLU}};
  \node[mat] (Ho) at (13.0,0) {\texttt{H (l+1)}\\\texttt{n x d'}};
  \draw[->, acc, thick] (H) -- (P);
  \draw[->, black, thick] (P) -- (M);
  \draw[->, acc, thick] (M) -- (W);
  \draw[->, green, thick] (W) -- (S);
  \draw[->, green, thick] (S) -- (Ho);
  \node[font=\footnotesize, anchor=north, text=acc] at (2.9,-0.85) {\texttt{mixes nodes}};
  \node[font=\footnotesize, anchor=north, text=acc] at (8.3,-0.85) {\texttt{mixes features}};
\end{tikzpicture}
$$

The two multiplications factor cleanly: $\hat A'$ is $n \times n$ and mixes _nodes_
(each output row is a weighted combination of input rows), while $W^{\parens{\ell}}$
is $d_\ell \times d_{\ell+1}$ and mixes _features_ (each output column is a
combination of input columns). Their order does not matter, $\parens{\hat A' H} W =
\hat A' \parens{H W}$, and the second grouping is cheaper when $d_{\ell+1} < n$:
project first, propagate the smaller matrix.

GCN is **transductive** as usually trained: it learns embeddings for the one fixed
graph in front of it, using the full $\hat A$ at every layer. It does not directly
produce embeddings for a node it has never seen, which is the limitation the next
model removes.

## GraphSAGE

GraphSAGE trades GCN's whole-graph propagation for an **inductive** recipe that
generalizes to unseen nodes and graphs. Two changes make this work: it _samples_ a
fixed-size subset of neighbors rather than using all of them, and it keeps the node
and aggregated-neighbor terms separate by concatenating before projecting.[^hamilton]

> **Definition (GraphSAGE layer).** Sample a fixed-size set $S\parens{v} \subseteq
> N\parens{v}$ of neighbors. With a permutation-invariant aggregator
> $\agg$,
> $$
> m_v^{\parens{\ell+1}} = \agg\parens{\set{ h_u^{\parens{\ell}} : u
>   \in S\parens{v} }},
> $$
> $$
> h_v^{\parens{\ell+1}} = \sigma\parens{ W^{\parens{\ell}} \cdot \brackets{
>   h_v^{\parens{\ell}} \,\Vert\, m_v^{\parens{\ell+1}} } },
> \qquad h_v^{\parens{\ell+1}} \gets \frac{h_v^{\parens{\ell+1}}}{\norm{h_v^{\parens{\ell+1}}}_2},
> $$
> where $\Vert$ is concatenation and the final $\ell_2$ normalization keeps scales
> stable across layers.

Sampling caps the cost per node at a constant independent of degree, so a fixed
GraphSAGE model runs on a billion-node graph it never saw at training time, the
property that makes it inductive. The aggregator is a pluggable design choice:

| Aggregator | Definition | Notes |
| --- | --- | --- |
| Mean | $\frac{1}{\abs{S\parens{v}}}\sum_{u} h_u$ | cheap; close to GCN's averaging |
| Pool | $\max_{u}\, \sigma\parens{W_{\text{pool}} h_u + b}$ | elementwise max after a shared MLP |
| LSTM | LSTM over a random neighbor order | most expressive, but not order-invariant |

The LSTM aggregator is the telling case: an LSTM reads a _sequence_, so to apply it
to an orderless neighbor set GraphSAGE feeds the neighbors in a random permutation.
It sacrifices strict permutation invariance for capacity, a trade the mean and pool
aggregators do not make.

## Graph attention network (GAT)

GCN fixes the neighbor weights by degree alone; the structural coefficient
$1/\sqrt{\hat d_v \hat d_u}$ knows nothing about the features. A **graph attention
network** learns the weights instead, scoring each neighbor by content the way
[self-attention](/deep-learning/architectures/attention-and-transformers) scores
keys, then attending only over the graph's edges.[^velickovic]

> **Definition (Graph attention layer).** Project states with a shared $W$, score
> each edge $\parens{u,v}$ with a learnable attention vector $a$, and normalize over
> $v$'s neighbors with a softmax:
> $$
> e_{vu} = \LeakyReLU\parens{ a^{\top} \brackets{ W h_v \,\Vert\, W h_u } },
> \qquad
> \alpha_{vu} = \frac{\exp\parens{e_{vu}}}{\sum_{w \in N\parens{v} \cup \set{v}}
>   \exp\parens{e_{vw}}}.
> $$
> The update is the attention-weighted neighbor sum,
> $$
> h_v^{\parens{\ell+1}} = \sigma\parens{ \sum_{u \in N\parens{v} \cup \set{v}}
>   \alpha_{vu}\, W h_u }.
> $$

The shapes track the Transformer's, restricted to edges. With $W \in
\mathbb{R}^{d' \times d}$ the projected state $W h_v \in \mathbb{R}^{d'}$, the
concatenation $\brackets{W h_v \Vert W h_u} \in \mathbb{R}^{2d'}$, and the attention
vector $a \in \mathbb{R}^{2d'}$, so each score $e_{vu} = a^{\top}\brackets{\cdots}$
is a scalar. The softmax normalizes those scalars over $v$'s neighbors into weights
$\alpha_{vu}$ summing to $1$, and the update is their weighted sum of the $d'$-vectors
$W h_u$, giving $h_v^{\parens{\ell+1}} \in \mathbb{R}^{d'}$. The softmax runs only
over $v$'s neighbors, so attention is sparse and local (unlike a Transformer's
all-pairs matrix), respecting the graph structure while letting the model decide
which neighbors matter. As with the Transformer, GAT uses
several **attention heads** in parallel and concatenates (or, at the last layer,
averages) their outputs, so the network holds multiple relational patterns at once.

$$
% caption: A GAT layer at node $v$: each edge gets a learned coefficient $\alpha_{vu}$ from a
% softmax over neighbors; the update is the attention-weighted sum of projected states.
\begin{tikzpicture}[font=\small, >=stealth,
  nd/.style={circle, draw, black, thick, minimum size=8mm, inner sep=0pt, font=\scriptsize},
  vv/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=9mm, inner sep=0pt, font=\scriptsize, text=acc}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \node[vv] (v) at (0,0)        {$h_v$};
  \node[nd] (u1) at (-2.4,1.6)  {$h_{u_1}$};
  \node[nd] (u2) at (2.4,1.6)   {$h_{u_2}$};
  \node[nd] (u3) at (-2.4,-1.6) {$h_{u_3}$};
  \node[nd] (u4) at (2.4,-1.6)  {$h_{u_4}$};
  % edges with attention weights, thicker = larger alpha
  \draw[acc, line width=1.6pt] (u1) -- (v) node[pos=0.62, above, font=\scriptsize, text=acc, sloped] {weight 0.50};
  \draw[acc, line width=0.7pt] (u2) -- (v) node[pos=0.62, above, font=\scriptsize, text=acc, sloped] {0.10};
  \draw[acc, line width=1.1pt] (u3) -- (v) node[pos=0.62, below, font=\scriptsize, text=acc, sloped] {0.25};
  \draw[acc, line width=0.7pt] (u4) -- (v) node[pos=0.62, below, font=\scriptsize, text=acc, sloped] {0.15};
  \node[font=\scriptsize, text=green, anchor=north] at (0,-2.4) {output: weighted sum of $W h_u$};
\end{tikzpicture}
$$

## Readout for graph-level outputs

Node-level outputs come straight off $H^{\parens{L}}$. A graph-level prediction
needs to collapse the $n$ node vectors into one, with a function that ignores their
order so the answer is permutation invariant.

> **Definition (Readout / graph pooling).** A permutation-invariant map from the
> node representations to a single graph vector,
> $$
> h_G = \readout\parens{\set{ h_v^{\parens{L}} : v \in V }} \in
>   \mathbb{R}^{d},
> $$
> commonly sum, mean, or max over nodes. A classifier head then reads $h_G$.

| Readout | Form | Keeps | Caveat |
| --- | --- | --- | --- |
| Sum | $\sum_v h_v$ | size and counts | scale grows with $n$ |
| Mean | $\frac{1}{n}\sum_v h_v$ | average profile | blind to graph size |
| Max | $\max_v h_v$ (elementwise) | strongest feature | discards multiplicity |

The flat readouts throw away all coarse structure in one step. **Hierarchical
pooling** instead coarsens the graph in stages, merging clusters of nodes into
supernodes and repeating, so the readout reflects communities and motifs rather
than a single global average. As the expressivity results below show, the choice of
aggregator is not cosmetic: sum strictly dominates mean and max in what it can
distinguish.

## Expressivity: what message passing can tell apart

Message passing is expressive but provably limited. Its ceiling is a classical graph
algorithm, the Weisfeiler-Lehman isomorphism test, which colors nodes by iteratively
hashing the multiset of neighbor colors, exactly the shape of a GNN layer.[^xu]

> **Theorem (WL upper bound).** Any message-passing GNN is at most as powerful as
> the 1-dimensional Weisfeiler-Lehman test at distinguishing non-isomorphic graphs:
> if 1-WL assigns two nodes the same color at every round, no message-passing GNN
> can give them different representations.

> **Proof (sketch).** Both procedures update a node from its own state and the
> multiset of neighbor states. By induction on the round $\ell$: if two nodes share
> a WL color after $\ell$ rounds, their rooted $\ell$-hop neighborhoods are
> identical as multisets, so the GNN's $\aggregate$ (a function of
> exactly that multiset) receives identical input and returns identical output.
> Hence equal WL color at every round forces equal GNN representation. $\qed$

The bound is tight, and reaching it requires care. A GNN matches 1-WL only when its
aggregate is **injective** on multisets, so distinct neighbor multisets always map
to distinct messages. Mean and max aggregators fail this (mean cannot tell
$\set{a}$ from $\set{a,a}$; max cannot tell $\set{a}$ from $\set{a,b}$ when $b<a$
elementwise), which is why **GIN** uses a _sum_ over an MLP.

> **Definition (Graph Isomorphism Network, GIN).** The GIN layer uses a summing
> aggregate and an MLP update with a learnable self-weight $\epsilon$:
> $$
> h_v^{\parens{\ell+1}} = \MLP^{\parens{\ell}}\!\parens{
>   \parens{1 + \epsilon^{\parens{\ell}}}\, h_v^{\parens{\ell}} +
>   \sum_{u \in N\parens{v}} h_u^{\parens{\ell}} }.
> $$
> A sum is injective on multisets of bounded size, and a sufficiently wide MLP can
> realize any injective function, so GIN is as discriminative as 1-WL.

$$
% caption: Mean and max cannot tell these neighborhoods apart, both giving $1$; only the sum
% ($1$ vs $2$) sees the repeated feature, which is why GIN aggregates by summing.
\begin{tikzpicture}[font=\small, >=stealth,
  nd/.style={circle, draw, black, thick, minimum size=7mm, inner sep=0pt, font=\scriptsize},
  cc/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=8mm, inner sep=0pt, font=\scriptsize, text=acc}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % left graph: center v with one neighbor valued 1
  \node[cc] (c1) at (0,0) {$v$};
  \node[nd] (a1) at (-1.7,1.2) {1};
  \draw[acc, thick] (c1) -- (a1);
  \node[font=\scriptsize, anchor=north, align=center] at (0,-0.7)
    {sum $=1$, mean $=1$, max $=1$};
  % right graph: center w with two neighbors each valued 1
  \begin{scope}[xshift=6.4cm]
    \node[cc] (c2) at (0,0) {$w$};
    \node[nd] (b1) at (-1.7,1.2) {1};
    \node[nd] (b2) at (1.7,1.2)  {1};
    \draw[acc, thick] (c2) -- (b1);
    \draw[acc, thick] (c2) -- (b2);
    \node[font=\scriptsize, anchor=north, align=center] at (0,-0.7)
      {sum $=2$, mean $=1$, max $=1$};
  \end{scope}
  % verdict
  \node[font=\scriptsize, text=green, anchor=south] at (3.2,2.2) {sum separates them};
  \node[font=\scriptsize, text=red, anchor=south] at (3.2,1.7) {mean and max cannot};
\end{tikzpicture}
$$

### Over-smoothing and over-squashing

Stacking many layers, the natural way to widen a node's receptive field, runs into
two failure modes that cap practical depth.

> **Definition (Over-smoothing).** As GNN depth grows, repeated neighbor averaging
> drives node representations toward a common vector, so distinct nodes become
> indistinguishable. A GCN-style layer is a smoothing operator: its repeated
> application converges to the dominant eigenvector of the normalized adjacency,
> erasing the very differences a node classifier needs.

The convergence is power iteration in disguise. Strip the learnable pieces (set
$W = I$ and $\sigma$ to the identity) and a GCN layer is just left-multiplication by
$\hat A' = \hat D^{-1/2}\hat A\hat D^{-1/2}$. This matrix is symmetric with
eigenvalues in $[-1, 1]$, and its top eigenvalue is exactly $1$ with eigenvector
$\hat d^{1/2}$ (entries $\sqrt{\hat d_v}$). Expanding any feature column in the
eigenbasis $H = \sum_i \gamma_i q_i$, applying $L$ layers scales component $i$ by
$\lambda_i^L$:

$$
\parens{\hat A'}^L H = \sum_i \gamma_i\, \lambda_i^L\, q_i \;\xrightarrow{L \to
\infty}\; \gamma_1\, q_1,
$$

because every $\abs{\lambda_i} < 1$ term decays geometrically and only the
$\lambda_1 = 1$ component survives. Every node collapses onto the same direction
$q_1 = \hat d^{1/2}$, scaled only by its degree, so all feature information beyond
degree is gone. The worked example already showed the first step of this: after one
layer, node $4$'s value had moved from $0$ toward its neighbors; iterate and it
reaches the common limit.

$$
% caption: Over-smoothing: node features (here a 1-D value per node, two classes) start separated
% and collapse toward one value as depth grows, until the two classes are inseparable.
\begin{tikzpicture}[font=\small, >=stealth, x=1.55cm, y=1.0cm]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, thick] (-0.2,0) -- (4.4,0) node[right, font=\scriptsize] {depth $L$};
  \draw[->, thick] (0,-0.2) -- (0,3.2) node[above, font=\scriptsize] {feature value};
  \foreach \x/\t in {0/0,1/2,2/4,3/6,4/8}
    \node[font=\scriptsize, anchor=north] at (\x,0) {\t};
  % class A (acc): high, decays toward 1.5
  \draw[acc, very thick] plot[domain=0:4, samples=60]
    (\x, {1.5 + 1.4*exp(-0.85*\x)});
  % class B (red): low, rises toward 1.5
  \draw[red, very thick] plot[domain=0:4, samples=60]
    (\x, {1.5 - 1.4*exp(-0.85*\x)});
  % convergence line
  \draw[black, dashed] (0,1.5) -- (4.2,1.5);
  \node[font=\scriptsize, text=acc, anchor=west] at (0.15,3.0) {class A};
  \node[font=\scriptsize, text=red, anchor=west] at (0.15,0.35) {class B};
  \node[font=\scriptsize, anchor=west] at (3.05,1.7) {collapse};
\end{tikzpicture}
$$

> **Definition (Over-squashing).** Information from an exponentially growing
> $\ell$-hop neighborhood is compressed into a fixed-size node vector. Across a
> graph bottleneck, the number of source nodes whose signal must pass through one
> edge grows exponentially with distance, so long-range messages are squashed and
> effectively lost.

The two are distinct: over-smoothing is too _much_ mixing (everything looks the
same), over-squashing is too _little_ throughput (distant signal cannot get
through a narrow cut). Residual connections, normalization, and architectural
rewiring mitigate both, but they bound how deep a plain message-passing stack is
useful, in sharp contrast to the hundred-layer convolutional and Transformer stacks
of the earlier lessons.

## Comparing the four models

The four canonical layers are one template with four aggregates.

| Model | Aggregator | Neighbor weighting | Inductive? | Attention? |
| --- | --- | --- | --- | --- |
| GCN | normalized sum | fixed, $1/\sqrt{\hat d_v \hat d_u}$ | no (transductive) | no |
| GraphSAGE | mean / pool / LSTM | uniform over a sample | yes | no |
| GAT | weighted sum | learned $\alpha_{vu}$ from features | yes | yes |
| GIN | sum + MLP | uniform (with $1+\epsilon$ self) | yes | no |

## Extending the GNN framework

GNNs postdate Goodfellow, Chollet, and Stevens, so the framework here rests on the primary
literature cited in the footnotes. Two developments extend it past the four
canonical layers.

- **Graph Transformers.** The over-smoothing and over-squashing limits both come
  from restricting each layer to the _local_ neighborhood. Treat the graph as a set
  of tokens and let every node attend to every other — full self-attention, with the
  graph structure injected as a positional or structural encoding rather than a hard
  adjacency mask — and both pathologies ease, because information no longer has to
  pass through many hops. Graphormer (Ying et al., NeurIPS 2021) won the OGB
  large-scale-challenge with exactly this, encoding shortest-path distance and node
  degree as attention biases. This is the same move ViT made for images: drop the
  hard-coded locality prior once there is enough data and compute to learn it.
- **Structural and positional encodings.** A plain message-passing GNN cannot tell
  two nodes apart if their neighborhoods look identical (the Weisfeiler-Lehman
  ceiling). Adding features that break the symmetry — Laplacian eigenvectors as
  positional encodings, or random-walk landing probabilities — provably lifts the
  network above that ceiling, a graph analogue of the Transformer's positional
  encoding.

The applied payoff is the reason the field grew: message passing over molecular
graphs underlies **AlphaFold**'s structure module (Jumper et al., Nature 2021) and
production drug-discovery and materials pipelines, where the permutation symmetry a
GNN respects coincides with the symmetry a molecule has.

## Takeaways

- A **graph neural network** generalizes convolution to irregular data by replacing
  the spatial stencil with a node's neighborhood and reusing one shared
  transformation everywhere, respecting the only symmetry graphs admit:
  **permutation equivariance** for node layers, **invariance** for the readout.
- Nearly every GNN is one **message-passing** template: $h_v^{\parens{\ell+1}} =
  \update\parens{h_v^{\parens{\ell}}, \aggregate\parens{
  \set{h_u : u \in N\parens{v}}}}$, with an order-invariant aggregate that makes
  the layer equivariant for free.
- **GCN** is a normalized-adjacency propagation $\sigma\parens{\hat D^{-1/2}\hat A
  \hat D^{-1/2} H W}$ (a first-order spectral filter); **GraphSAGE** samples
  neighbors and concatenates to learn _inductively_; **GAT** replaces fixed weights
  with learned attention $\alpha_{vu}$ over edges.
- **Readout** (sum / mean / max, or hierarchical pooling) collapses node vectors
  into one graph vector for graph-level tasks; sum retains the most information.
- Message passing is capped by the **Weisfeiler-Lehman** test; reaching that ceiling
  needs an injective aggregate, which is why **GIN** sums over an MLP, and mean/max
  fall short.
- Depth is limited by **over-smoothing** (features collapse to a common vector) and
  **over-squashing** (exponential neighborhoods crushed through bottlenecks), so
  GNNs stay shallow where CNNs and Transformers go deep.

[^gf-conv]: **Goodfellow**, _Deep Learning_, §9.2 — Motivation: sparse interactions and parameter sharing as the levers convolution pulls; a GNN reuses the same levers with a neighborhood in place of a grid patch (GNNs postdate the 2016 text).
[^scarselli]: **Scarselli, Gori, Tsoi, Hagenbuchner & Monfardini** (IEEE TNN 2009), _The Graph Neural Network Model_ — the original GNN: a contraction-map state update iterated to a fixed point over the graph.
[^gilmer]: **Gilmer, Schoenholz, Riley, Vinyals & Dahl** (ICML 2017), _Neural Message Passing for Quantum Chemistry_ — unifies GNN variants under the aggregate-then-update message-passing framework.
[^kipf]: **Kipf & Welling** (ICLR 2017), _Semi-Supervised Classification with Graph Convolutional Networks_ — the symmetric-normalized propagation $\hat D^{-1/2}\hat A\hat D^{-1/2}HW$ as a first-order spectral convolution.
[^bruna]: **Bruna, Zaremba, Szlam & LeCun** (ICLR 2014), _Spectral Networks and Locally Connected Networks on Graphs_ — the spectral-domain origin of graph convolution via the graph Laplacian eigenbasis.
[^hamilton]: **Hamilton, Ying & Leskovec** (NeurIPS 2017), _Inductive Representation Learning on Large Graphs_ — GraphSAGE: neighbor sampling and trainable aggregators for inductive embeddings on unseen nodes.
[^velickovic]: **Veličković, Cucurull, Casanova, Romero, Liò & Bengio** (ICLR 2018), _Graph Attention Networks_ — masked self-attention over edges, with learned per-neighbor coefficients $\alpha_{vu}$ and multiple heads.
[^xu]: **Xu, Hu, Leskovec & Jegelka** (ICLR 2019), _How Powerful are Graph Neural Networks?_ — the Weisfeiler-Lehman bound on message-passing expressivity and the maximally powerful GIN aggregate.
[^bronstein]: **Bronstein, Bruna, Cohen & Veličković** (2021), _Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges_ — symmetry and invariance as the organizing principle behind GNNs and convolution alike.