Graph Neural Networks: Message Passing, GCN, GAT, and GraphSAGE

An account’s own transaction features may not reveal that it belongs to a coordinated fraud network. Its connections to other accounts can provide additional evidence. A graph neural network (GNN) combines features with these relationships: each node updates its representation using messages from neighboring nodes.

A graph has nodes and edges. Nodes might be accounts, atoms, or road junctions; edges record transfers, bonds, or roads. The examples below use an undirected, unweighted graph: \(A_{vu}=1\) when nodes \(v\) and \(u\) are connected, and 0 otherwise. The adjacency matrix \(A\) is symmetric. With \(N\) nodes and \(F\) features per node, the feature matrix \(H\) has shape \((N,F)\): each row describes one node. Real applications may also need edge direction, weights, types, or coordinates.

Node numbers are bookkeeping. Renumbering the same graph should reorder its node predictions without changing what it predicts about each node. This article assumes familiarity with matrix multiplication and neural network layers; the new step is deciding which rows exchange information.

Message passing

In local message passing, \(h_v^{(l)}\) is node \(v\)’s feature vector after layer \(l\), and \(\mathcal N(v)\) is its neighbor set. A shared function \(\psi\) forms messages, an aggregator \(\bigoplus\) combines them, and another shared function \(\phi\) updates the node:

\[h_v^{(l+1)}=\phi\left(h_v^{(l)},\;\bigoplus_{u\in\mathcal N(v)}\psi\left(h_v^{(l)},h_u^{(l)}\right)\right).\]

Sum, mean, and elementwise max give the same aggregate when neighbors are listed in a different order. For example, scalar messages 2 and 6 have mean 4 in either order. Concatenating neighbors in an arbitrary storage order would generally change the result. Concatenating the self vector with an already aggregated neighbor vector, as GraphSAGE does below, preserves the distinction between those two roles without depending on neighbor order. Edge features can be additional inputs to the message function.

Order-independent aggregation and shared updates make node outputs permutation equivariant: relabeling nodes relabels the outputs. A graph-level prediction should instead be unchanged by relabeling. With one-hop local layers, \(L\) layers allow information from up to \(L\) hops away to influence a node. Learned updates also build new features at each layer. Greater reach is not a guarantee that distant information survives usefully.

Graph convolutional networks

A GCN uses degree-based weights to combine features. In the following formula, \(\tilde A=A+I\) adds a self-loop to every node, \(\tilde d_v=\sum_u\tilde A_{vu}\), and \(\tilde D\) places these degrees on a diagonal. The learned matrix \(W^{(l)}\) changes the feature dimension; \(\sigma\) is an activation such as ReLU.

\[H^{(l+1)}=\sigma\left(\hat A H^{(l)}W^{(l)}\right),\qquad \hat A=\tilde D^{-1/2}\tilde A\tilde D^{-1/2}.\]

An edge contributes weight \(1/\sqrt{\tilde d_v\tilde d_u}\). This controls the growth caused by repeatedly adding many messages. It is not an ordinary mean: the weights in a row need not sum to 1. On the four-node graph below, self-inclusive degrees are 3, 3, 4, and 2. For scalar features \([1,2,3,4]\), node 0 receives \(1/3+2/3+3/\sqrt{12}\approx1.866\). Node 3 does not contribute directly to node 0 because they share no edge.

import torch
import torch.nn as nn
import torch.nn.functional as F

def normalize_adjacency(A):
    if not A.is_floating_point() or A.ndim != 2 or A.shape[0] != A.shape[1]:
        raise ValueError("A must be a square floating-point matrix")
    if not torch.isfinite(A).all() or (A < 0).any():
        raise ValueError("A must be finite and nonnegative")
    if not torch.equal(A, A.T) or torch.any(A.diagonal() != 0):
        raise ValueError("This example requires undirected edges and no existing self-loops")
    At = A + torch.eye(A.shape[0], device=A.device, dtype=A.dtype)
    inv = At.sum(1).rsqrt()
    return inv[:, None] * At * inv[None, :]

class GCNLayer(nn.Module):
    def __init__(self, d_in, d_out):
        super().__init__()
        self.lin = nn.Linear(d_in, d_out, bias=False)

    def forward(self, H, A_hat):
        return A_hat @ self.lin(H)

A = torch.tensor([[0., 1., 1., 0.],
                  [1., 0., 1., 0.],
                  [1., 1., 0., 1.],
                  [0., 0., 1., 0.]])
A_hat = normalize_adjacency(A)
print("row sums", A_hat.sum(1).round(decimals=3))
print("node 0 scalar update", round((A_hat @ torch.arange(1., 5.))[0].item(), 3))
torch.manual_seed(0)
H = torch.randn(4, 8)
layer = GCNLayer(8, 16)
print("hidden shape", tuple(F.relu(layer(H, A_hat)).shape))
perm = torch.tensor([2, 0, 3, 1])
permuted = layer(H[perm], A_hat[perm][:, perm])
print("relabeling agrees", torch.allclose(permuted, layer(H, A_hat)[perm], atol=1e-6))
# row sums tensor([0.9550, 0.9550, 1.1810, 0.8540])
# node 0 scalar update 1.866
# hidden shape (4, 16)
# relabeling agrees True

The layer returns the value before activation; the example applies ReLU outside it. Because this linear transform has no bias, transforming and then aggregating gives the same result as aggregating and then transforming. The relabeling check permutes both the feature rows and the adjacency rows and columns. Shared matrix operations preserve this relationship for other relabelings as well, up to floating-point rounding.

GAT: learned neighbor weights

A graph attention network (GAT) lets endpoint features determine the aggregation weights. For receiver \(v\) and sender \(u\), it scores their transformed features, then applies softmax over the neighbors including the receiver itself. Write this set as \(\mathcal N^+(v)\); \(\Vert\) means concatenation and \(a\) is learned:

\[\alpha_{vu}=\frac{\exp(\operatorname{LeakyReLU}(a^T[Wh_v\Vert Wh_u]))}{\sum_{k\in\mathcal N^+(v)}\exp(\operatorname{LeakyReLU}(a^T[Wh_v\Vert Wh_k]))},\qquad z_v=\sum_{u\in\mathcal N^+(v)}\alpha_{vu}Wh_u.\]

class GATLayer(nn.Module):
    def __init__(self, d_in, d_out):
        super().__init__()
        self.W = nn.Linear(d_in, d_out, bias=False)
        self.receiver = nn.Linear(d_out, 1, bias=False)
        self.sender = nn.Linear(d_out, 1, bias=False)

    def forward(self, H, A):
        Wh = self.W(H)
        e = F.leaky_relu(self.receiver(Wh) + self.sender(Wh).T, negative_slope=0.2)
        mask = (A > 0) | torch.eye(A.shape[0], device=A.device, dtype=torch.bool)
        alpha = F.softmax(e.masked_fill(~mask, float("-inf")), dim=1)
        return alpha @ Wh, alpha

torch.manual_seed(1)
gat = GATLayer(8, 16)
out, alpha = gat(H, A)
print("output shape", tuple(out.shape))
print("attention row sums", alpha.sum(1).detach().round(decimals=4))
print("non-edge weight", alpha[0, 3].item())
# output shape (4, 16)
# attention row sums tensor([1., 1., 1., 1.])
# non-edge weight 0.0

The two one-column projections implement the two halves of the concatenated score. Row v contains the weights used by receiver v. Masking unavailable edges before softmax gives them zero weight, while the self-loop leaves even an isolated node with one valid entry. This is a single attention head returning a pre-activation output. Multiple heads learn separate projections and weights, and their outputs can be concatenated or averaged.

Graph-restricted attention is related to transformer attention, but the layers are not identical: this original GAT score is additive in the two projected endpoints, while standard transformer attention uses query–key dot products. Positional information, heads, and the rest of the transformer block introduce further differences. See Transformers from Scratch for that computation.

GraphSAGE and scaling

Both dense implementations above store \(N\times N\) matrices; the GAT code even scores every pair before masking. They are teaching examples for small graphs. Sparse implementations can work on stored edges, but computing a target node’s multi-layer neighborhood can still involve many nodes. GraphSAGE samples a limited number of neighbors at each layer, called the fanout.

Here is a mean-aggregation variant. It concatenates the self vector with the sampled neighbor mean, applies a learned transform and ReLU, and normalizes each nonzero output vector to unit length. Empty neighborhoods contribute a zero vector. The lists contain distinct neighbors and exclude the node itself. The sampling helper chooses up to fanout neighbors uniformly without replacement; if there are fewer, it keeps all of them.

def sample_neighbors(neighbor_lists, fanout, generator):
    if not isinstance(fanout, int) or fanout < 1:
        raise ValueError("fanout must be a positive integer")
    sampled = []
    for neighbors in neighbor_lists:
        if len(neighbors) <= fanout:
            sampled.append(list(neighbors))
        else:
            positions = torch.randperm(len(neighbors), generator=generator)[:fanout]
            sampled.append([neighbors[i] for i in positions.tolist()])
    return sampled

class SAGELayer(nn.Module):
    def __init__(self, d_in, d_out):
        super().__init__()
        self.lin = nn.Linear(2 * d_in, d_out)

    def forward(self, H, neighbor_lists):
        messages = [H[nbrs].mean(0) if nbrs else torch.zeros_like(H[v])
                    for v, nbrs in enumerate(neighbor_lists)]
        joined = torch.cat([H, torch.stack(messages)], dim=1)
        return F.normalize(F.relu(self.lin(joined)), p=2, dim=1)

neighbors = [[1, 2], [0, 2], [0, 1, 3], [2], []]
sampled = sample_neighbors(neighbors, 2, torch.Generator().manual_seed(0))
torch.manual_seed(2)
sage_features = torch.randn(5, 8)
sage = SAGELayer(8, 16)
sage_out = sage(sage_features, sampled)
print("sample counts", [len(x) for x in sampled])
print("output shape", tuple(sage_out.shape))
print("isolated output finite", bool(torch.isfinite(sage_out[4]).all()))
# sample counts [2, 2, 2, 1, 0]
# output shape (5, 16)
# isolated output finite True

The self and neighbor vectors occupy separate halves of the input to the linear layer, so it can assign them different weights. This example still updates all five nodes and keeps all their features in memory. A scalable mini-batch loader starts from target nodes, samples their required neighborhoods backward through the layers, and loads only the resulting computation subgraph. The original GraphSAGE pooling variant also transforms neighbor features before taking a maximum; raw max alone is not that variant.

Shared aggregation weights can be applied to previously unseen nodes with compatible features and available neighborhoods. This is inductive prediction. GCN and GAT layers can also be applied to new graphs; inductive versus transductive evaluation depends on what was available during training, not just the architecture’s name. A learned table of separate node embeddings needs additional handling for a new node.

Oversmoothing

Repeated aggregation can erase distinctions useful for prediction. To isolate this effect, the next experiment removes learned transforms and activations and repeatedly multiplies by the same normalized adjacency. This does not test a trained deep GNN, but it shows what its propagation operator alone retains.

For a connected undirected graph with nonnegative weights and the added self-loops, repeated symmetric propagation approaches \(qq^T H_0\), where \(q_v=\sqrt{\tilde d_v}/\sqrt{\sum_u\tilde d_u}\). All rows become multiples of one common vector, scaled by square-root degree. Their raw distances need not become zero. Dividing each row by \(\sqrt{\tilde d_v}\) removes that scale; these adjusted rows approach one another. Disconnected components have separate limits.

@torch.no_grad()
def smoothing_demo(A_hat, H, degrees):
    q = degrees.sqrt()
    q = q / q.norm()
    limit = q[:, None] @ (q[None, :] @ H)
    for depth in range(41):
        if depth in (0, 4, 8, 12, 40):
            raw = torch.cdist(H, H).mean().item()
            adjusted = torch.cdist(H / degrees.sqrt()[:, None],
                                   H / degrees.sqrt()[:, None]).mean().item()
            error = (H - limit).norm().item()
            print(f"layer {depth:2d}  raw {raw:.4f}  adjusted {adjusted:.4f}  limit error {error:.4f}")
        if depth < 40:
            H = A_hat @ H

torch.manual_seed(0)
smoothing_demo(A_hat, torch.randn(4, 16), A.sum(1) + 1)
# layer  0  raw 4.3459  adjusted 2.6572  limit error 7.2117
# layer  4  raw 0.3866  adjusted 0.1630  limit error 0.4795
# layer  8  raw 0.2725  adjusted 0.0165  limit error 0.0486
# layer 12  raw 0.2696  adjusted 0.0017  limit error 0.0049
# layer 40  raw 0.2695  adjusted 0.0000  limit error 0.0000

Distances here average all 16 ordered pairs, including four zero self-distances. The adjusted distance and the distance to the predicted limit shrink toward zero, while the raw distance levels off above zero. Node-specific information has been reduced to a degree-scaled pattern. Residual paths, access to earlier layers, and other propagation designs can help preserve information; this experiment does not establish a universal depth limit.

A different issue is oversquashing: information from many distant nodes must pass through a small number of edges and fixed-width vectors. Increasing the hop count alone may not make that information usable. Oversmoothing concerns representations becoming less distinguishable; oversquashing concerns the information bottleneck along paths. Optimization difficulties can also affect a deep GNN.

Expressiveness limits

The 1-dimensional Weisfeiler–Lehman (1-WL) test repeatedly refines a node’s label using its current label and the multiset of its neighbors’ labels (a collection that keeps duplicate labels but ignores their order). Ordinary local message-passing networks with shared updates cannot distinguish graph pairs that this test leaves identical, given the same initial features and no additional distinguishing information. A six-cycle and two disconnected triangles, both with identical node features, illustrate the limit: every node sees two neighbors in the same state at every round. An invariant graph readout receives the same six node vectors.

This pair has different triangle counts, so these networks cannot compute triangle counts correctly on every graph under that input setup. It does not mean they fail to recognize every cyclic structure. The pair is an abstract graph counterexample, not a comparison of two connected molecules. Structural features or higher-order message passing can supply distinctions that ordinary node-to-node updates miss.

GIN was designed to match 1-WL’s distinguishing power under suitable injectivity and feature-domain assumptions, using sum aggregation with learned updates. Mean and max lose multiplicity: [1] and [1, 1] have the same mean and max. Sum distinguishes those lists, but raw sums are not injective over arbitrary features: [1, 3] and [2, 2] both sum to 4. The theoretical result needs a suitable feature mapping; a finite trained GIN is not automatically a perfect 1-WL implementation.

Tasks and evaluation

For node classification, a final layer produces N rows of C class logits. Cross-entropy is computed only on training-labeled rows; gradients then flow through their message-passing computations. A graph classifier pools node vectors and applies a classifier to the pooled vector. Duplicating the entire collection of node vectors doubles its sum and leaves its mean unchanged. That choice affects whether the readout retains graph-size information. A link predictor scores pairs of node embeddings, for example with a dot product or a learned pairwise function.

A random node split is not automatically leakage. In a transductive task, the whole observed graph and all node features may legitimately be available during training, while validation and test labels stay withheld. Learning on training labels can influence neighboring node representations; that is part of this protocol. Feeding held-out labels into features or label propagation would violate it. The resulting score measures prediction on that observed graph, not necessarily on future nodes or independent graphs.

For future-node prediction, build features and edges from information available at the relevant time. For link prediction, keep held-out target edges out of the message-passing graph, including their reverse copies in an undirected graph, and specify how negative pairs are sampled: an unobserved edge is not always a known negative. Graph-level tasks need held-out graphs; splitting molecular families or time periods can test a different generalization question from a random molecule split. Choose the split to match the intended use, and keep preprocessing and model selection within its allowed data.

When to reach for a GNN

Compare with an MLP that uses the same node features but ignores edges, under the same evaluation protocol. If the graph helps, investigate which relationships provide the gain. Neighbors may have similar labels, but some graphs connect unlike roles; averaging their features can then discard a useful distinction. Edge direction, bond type, or transaction timing may matter more than an untyped connection. An application’s graph structure motivates testing a GNN; it does not establish that it will outperform a feature-only model.

Exercises

1. Compare normalization schemes. On the undirected random graph below, propagate the same features for ten rounds using the raw self-inclusive adjacency, row normalization, and symmetric normalization. Compare the final mean row norms. Which quantity does each normalization control?

import numpy as np
rng = np.random.default_rng(0)
n = 200
A = (rng.random((n, n)) < 0.05).astype(float)
A = np.triu(A, 1)
A = A + A.T
Ah = A + np.eye(n)
deg = Ah.sum(1)
print(f"self-inclusive degree min {deg.min():.0f}  max {deg.max():.0f}")
Dinv = np.diag(1.0 / deg)
Dh = np.diag(deg ** -0.5)
schemes = {"raw A+I": Ah, "row norm": Dinv @ Ah, "symmetric": Dh @ Ah @ Dh}
X0 = rng.normal(size=(n, 16))
for name, P in schemes.items():
    X = X0.copy()
    for _ in range(10):
        X = P @ X
    print(f"{name:10s} mean row norm {np.linalg.norm(X, axis=1).mean():.4e}")
# self-inclusive degree min 5  max 18
# raw A+I    mean row norm 9.4727e+09
# row norm   mean row norm 1.5628e-01
# symmetric  mean row norm 1.4635e-01

2. A triangle-count counterexample. Give a six-cycle and two disjoint triangles identical scalar node features. Run the update below, then explain why the two graphs remain indistinguishable to ordinary local message passing with an invariant readout. Compare their actual triangle counts.

import numpy as np

def adj(edges, n):
    A = np.zeros((n, n))
    for i, j in edges:
        A[i, j] = A[j, i] = 1.0
    return A

cycle6 = adj([(0,1),(1,2),(2,3),(3,4),(4,5),(5,0)], 6)
two_tri = adj([(0,1),(1,2),(2,0),(3,4),(4,5),(5,3)], 6)
for name, A in (("6-cycle", cycle6), ("2 triangles", two_tri)):
    X = np.ones((6, 1))
    for _ in range(5):
        X = A @ X + X
    triangles = int(round(np.trace(A @ A @ A) / 6))
    print(f"{name:12s} node features {X.ravel()}  triangles {triangles}")
# 6-cycle      node features [243. 243. 243. 243. 243. 243.]  triangles 0
# 2 triangles  node features [243. 243. 243. 243. 243. 243.]  triangles 2

3. Neighborhood growth and sampling. For a simple undirected graph with maximum degree 10 and 100,000 nodes, bound the number of distinct nodes within \(k\) hops for \(k=1,\ldots,5\). Compare this bound with a five-layer sampling tree of fanout 5. An average degree is not enough to give this per-node bound.

n_nodes, max_degree = 100_000, 10
total = 1
for k in range(1, 6):
    total += max_degree * (max_degree - 1) ** (k - 1)
    bound = min(n_nodes, total)
    print(f"{k} hops  at most {bound:>7,} distinct nodes  {100 * bound / n_nodes:6.2f}%")
sampled_slots = sum(5 ** k for k in range(6))
print(f"fanout 5, 5 layers: at most {sampled_slots:,} neighbor-tree slots")
# 1 hops  at most      11 distinct nodes    0.01%
# 2 hops  at most     101 distinct nodes    0.10%
# 3 hops  at most     911 distinct nodes    0.91%
# 4 hops  at most   8,201 distinct nodes    8.20%
# 5 hops  at most  73,811 distinct nodes   73.81%
# fanout 5, 5 layers: at most 3,906 neighbor-tree slots

References

Architecture definitions and the expressiveness result: Kipf and Welling, Graph Convolutional Networks; Veličković et al., Graph Attention Networks; Hamilton et al., GraphSAGE; Xu et al., How Powerful Are Graph Neural Networks?.