Graph Neural Networks

A convolutional network 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.¹²

Graph data

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

The adjacency matrix is the algebraic handle on the structure: a single multiplication ${\left(AX\right)}_v={\sum }_{u\in N\left(v\right)}{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.

Three task levels

What the network predicts determines where its outputs come from.

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 PA{P}^{\top }$. A correct model must not depend on that arbitrary choice.³

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.

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.⁴

Because $\mathrm{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^{\left(\ell \right)}\in {\mathbb{R}}^{d_{\ell }}$ is one vector per node; stacked over all $n$ nodes it is the matrix $H^{\left(\ell \right)}\in {\mathbb{R}}^{n\times d_{\ell }}$. The aggregate reads a variable-size set of $d_{\ell }$-vectors (node $v$ contributes $\mathrm{deg}\left(v\right)$ of them) and returns a single $d_{\ell }$-vector $m_v^{\left(\ell +1\right)}\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 $\left(h_v^{\left(\ell \right)},m_v^{\left(\ell +1\right)}\right)\in {\mathbb{R}}^{d_{\ell }}\times {\mathbb{R}}^{d_{\ell }}$ through a shared weight $W^{\left(\ell \right)}\in {\mathbb{R}}^{d_{\ell }\times d_{\ell +1}}$ and produces $h_v^{\left(\ell +1\right)}\in {\mathbb{R}}^{d_{\ell +1}}$. Only the width $d_{\ell }$ changes across layers; the same $W^{\left(\ell \right)}$ is applied at every node, the parameter sharing that mirrors a convolutional kernel.

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.

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^{\left(\ell \right)}\in {\mathbb{R}}^{n\times d}$, the GCN layer is a single propagation rule.⁵

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{\mathrm{deg}\left(v\right)\mathrm{deg}\left(u\right)}$:

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 $\left(v,u\right)$,

for every $u\in N\left(v\right)\cup \left\{v\right\}$ (and $0$ off the graph), which matches the coefficient in the per-node sum above. Multiplying the propagated matrix by $W^{\left(\ell \right)}$ 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.⁶

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

Row-summing $\hat{A}$ gives the self-looped degrees $\hat{d}=\left(3,3,4,2\right)$, so $\hat{D}=\mathrm{diag}\left(3,3,4,2\right)$ and ${\hat{D}}^{-1/2}=\mathrm{diag}\left(1/\sqrt{3},1/\sqrt{3},1/2,1/\sqrt{2}\right)$. The normalized propagation matrix ${\hat{A}}^{\prime }={\hat{D}}^{-1/2}\hat{A}{\hat{D}}^{-1/2}$ has entry ${\hat{A}}_{vu}^{\prime }=1/\sqrt{{\hat{d}}_v{\hat{d}}_u}$ wherever ${\hat{A}}_{vu}=1$:

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

and doing every row gives ${\hat{A}}^{\prime }H\approx {\left(0.62,0.62,0.54,0.35\right)}^{\top }$. With a scalar weight $W=1$ and $\sigma =\mathrm{ReLU}$ (the identity here, since every entry is positive), the first layer output is $H^{\left(1\right)}\approx {\left(0.62,0.62,0.54,0.35\right)}^{\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.

The two multiplications factor cleanly: ${\hat{A}}^{\prime }$ is $n\times n$ and mixes nodes (each output row is a weighted combination of input rows), while $W^{\left(\ell \right)}$ is $d_{\ell }\times d_{\ell +1}$ and mixes features (each output column is a combination of input columns). Their order does not matter, $\left({\hat{A}}^{\prime }H\right)W={\hat{A}}^{\prime }\left(HW\right)$, 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.⁷

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:

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 scores keys, then attending only over the graph's edges.⁸

The shapes track the Transformer's, restricted to edges. With $W\in {\mathbb{R}}^{d^{\prime }\times d}$ the projected state $W{h}_v\in {\mathbb{R}}^{d^{\prime }}$, the concatenation $\left[W{h}_v\Vert W{h}_u\right]\in {\mathbb{R}}^{2d^{\prime }}$, and the attention vector $a\in {\mathbb{R}}^{2d^{\prime }}$, so each score $e_{vu}=a^{\top }\left[\cdots \right]$ 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^{\prime }$-vectors $W{h}_u$, giving $h_v^{\left(\ell +1\right)}\in {\mathbb{R}}^{d^{\prime }}$. 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.

Readout for graph-level outputs

Node-level outputs come straight off $H^{\left(L\right)}$. 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.

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.⁹

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 $\left\{a\right\}$ from $\left\{a,a\right\}$; max cannot tell $\left\{a\right\}$ from $\left\{a,b\right\}$ when $b<a$ elementwise), which is why GIN uses a sum over an MLP.

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.

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}}^{\prime }={\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$:

because every $\left|{\lambda }_i\right|<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.

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.

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^{\left(\ell +1\right)}=\mathrm{update}\left(h_v^{\left(\ell \right)},\mathrm{aggregate}\left(\left\{h_u:u\in N\left(v\right)\right\}\right)\right)$, with an order-invariant aggregate that makes the layer equivariant for free.
• GCN is a normalized-adjacency propagation $\sigma \left({\hat{D}}^{-1/2}\hat{A}{\hat{D}}^{-1/2}HW\right)$ (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.