Tag: GNN

Graph Neural Networks (message passing, GCN, GraphSAGE, GAT, GAT, etc.)

DL0191 GCN, GraphSAGE, and GAT

How do Graph Convolutional Networks (GCN), GraphSAGE, and Graph Attention Networks (GAT) differ in their neighborhood aggregation strategies, and what are the trade-offs in transductive versus inductive settings?

Answer

All three layers do the same thing at a high level: build a new vector for node $i$ as a weighted combination of its neighbors’ vectors, then apply a linear map and a nonlinearity. The real difference is where the mixing coefficient comes from and how the neighborhood is enumerated. GCN fixes the coefficient from the graph alone as symmetric degree normalization $1/\sqrt{\tilde{d}_i \tilde{d}_j}$ , applied to the full neighborhood in one sparse matrix product over the entire graph. GraphSAGE replaces the full neighborhood with a fixed-size random sample and a permutation-invariant aggregator (mean, max-pool, or LSTM), and keeps the node’s own vector in a separate concatenated slot instead of averaging it away. GAT makes the coefficient content-dependent: a small shared scoring vector reads both endpoint features, a softmax over each node’s neighborhood turns those scores into weights $\alpha_{ij}$ , and several attention heads are run in parallel. Transductive versus inductive is then mostly a property of the training procedure and of what the coefficients depend on, not of the layer equation itself.

(1) GCN Weights Are Structural And Frozen: $c_{ij}$ depends only on the two degrees, so a high-degree hub is deliberately down-weighted and no coefficient is ever learned. This is a strong, cheap prior when features are weak and the graph is homophilous.
(2) GraphSAGE Weights Are Uniform Over A Sample: the mean aggregator gives every sampled neighbor $1/|S(i)|$ , and the sample size is the knob that bounds compute rather than the node’s true degree.
(3) Self Vector Handling Differs: GCN and GAT fold the node into the same sum through a self-loop, while GraphSAGE concatenates it and gives it its own block of the weight matrix, which preserves the node’s own signal at depth.
(4) GAT Weights Are Learned From Features: $\alpha_{ij}$ can vary across edges of identical degree, which is what lets the layer ignore a noisy neighbor. The price is $K|E|$ stored coefficients and gradients flowing through the attention scores.
(5) Transductive Is A Training Choice, Not A Law: the published GCN is trained full-batch on a single normalized adjacency, so a new node changes degrees and the normalization; GraphSAGE was designed minibatch-first so the same weights run on an unseen node by sampling its fan-out.
(6) Depth Costs Differently: full-neighborhood expansion grows as roughly $\bar{d}^{\,L}$ per target node, while sampling caps it at $\prod_l S_l$ at the cost of estimator variance.

Three side-by-side panels showing the same target node with four neighbors A, B, C, D. In the GCN panel the incoming arrow thickness follows fixed degree-based coefficients 0.32, 0.26, 0.18 and 0.15 with a self-loop coefficient 0.20. In the GraphSAGE panel only A and C are sampled with equal weight 0.50, B and D are drawn as dashed gray unsampled nodes, and the target keeps its own vector through concatenation. In the GAT panel the coefficients are learned attention values 0.09, 0.46, 0.11, 0.19 with self attention 0.15, so arrow thickness no longer tracks degree.

Figure 1: One neighborhood, three weighting rules. GCN reads its coefficients off the degrees, so the sparsest neighbor A gets the largest share and the hub D the smallest. GraphSAGE throws away two neighbors and splits the mass uniformly over what survives, keeping the self vector in a separate concatenated slot. GAT lets features decide, so neighbor B dominates with $\alpha = 0.46$ despite having a middling degree.

Mathematical Formulation:
$h_i' = \sigma\big(\textstyle\sum_{j \in \tilde{N}(i)} c_{ij} W h_j\big)$
$c_{ij} = 1 / \sqrt{\tilde{d}_i \tilde{d}_j}$
$a_i = \mathrm{AGG}(\{h_j : j \in S(i)\})$
$h_i' = \sigma(W \, [\, h_i \,\|\, a_i \,])$
$e_{ij} = \mathrm{LeakyReLU}(a^{\top}[W h_i \,\|\, W h_j])$
$\alpha_{ij} = \mathrm{softmax}_j(e_{ij})$
$h_i' = \sigma\big(\textstyle\sum_{j \in \tilde{N}(i)} \alpha_{ij} W h_j\big)$

Where:

$h_i \in \mathbb{R}^{d}$ is the incoming representation of node $i$ and $h_i'$ the layer output; $\sigma$ is the elementwise nonlinearity and $W$ the shared linear map.
$\tilde{N}(i)$ is the neighborhood including the self-loop, and $\tilde{d}_i$ is the corresponding degree, so $c_{ij}$ is the fixed GCN coefficient that never changes during training.
$S(i) \subseteq N(i)$ is the sampled fan-out of fixed size $S_l$ at layer $l$ , and $\mathrm{AGG}$ is a permutation-invariant reducer (mean, elementwise max over an MLP, or LSTM over a shuffled order).
$\|$ is concatenation, so the GraphSAGE weight matrix has shape $d' \times 2d$ and the node’s own features get an independent parameter block.
$a \in \mathbb{R}^{2d'}$ is the shared attention vector and $e_{ij}$ the raw score; the softmax is taken over $j \in \tilde{N}(i)$ so that $\sum_j \alpha_{ij} = 1$ per node.
GAT runs $K$ heads whose outputs are concatenated in hidden layers and averaged in the output layer, multiplying both parameter count and stored coefficients by $K$ .

The cost picture follows directly. A full-batch GCN layer is $O(|E| d + |V| d^2)$ and needs the whole feature matrix plus every layer’s activations resident, which is why it stops fitting long before the graph itself does. GAT adds $O(K |E|)$ scores and their gradients on top of the same sparse pattern, so its memory is edge-bound rather than node-bound. GraphSAGE instead bounds a minibatch: with batch size $B$ and fan-outs $(S_1, \ldots, S_L)$ , the computation graph holds a number of node instances that is completely independent of $|V|$ . That is the property that makes web-scale graph learning practical, and it is the mechanism behind Pinterest’s PinSage, which trains on a graph of billions of nodes by expanding only short sampled neighborhoods per target.

Minibatch Fan-Out Budget:
$N_{mb} = B \prod_{l=1}^{L} S_l$
$25 \times 10 = 250$
$N_{mb} = 512 \times 250 = 128000$

Log-scale line chart of node instances in the computation graph for a single target node versus GNN depth from 1 to 4 layers. Full-neighborhood expansion at average degree 100 rises from 100 to about 101 million, full-neighborhood expansion at average degree 20 rises from 20 to about 168 thousand, and sampled fan-out 25 then 10 per layer rises only from 25 to about 28 thousand. A dashed horizontal line marks a graph of 2.4 million nodes, which the average-degree-100 curve crosses between three and four layers.

Figure 2: Depth is what makes full-neighborhood aggregation intractable. On a graph with average degree 100, a 3-hop receptive field already touches about a million node instances per target and a 4-hop field exceeds the graph size, meaning most of the graph is re-visited for a single prediction. A fixed fan-out of 25 then 10 keeps the same depth at roughly 2,800 instances, trading exactness for a cost that no longer depends on $|V|$ .

Property	GCN	GraphSAGE	GAT
Neighbor weight	Fixed 1 / sqrt(d_i d_j)	Uniform 1 / \|S(i)\|, or max-pool / LSTM reducer	Learned alpha_ij per head, softmax over the neighborhood
Weight depends on	Graph structure only	Sample size only	Endpoint features, so it changes as the model trains
Self representation	Self-loop term inside the same sum	Concatenated, own block of the weight matrix	Self-loop with its own attention coefficient
Published training regime	Full-batch over one normalized adjacency	Minibatch with fixed per-layer fan-out sampling	Full-batch on citation graphs, sampled variants for large graphs
Unseen node at inference	Degrees and normalization must be recomputed; the transductive recipe assumes the test nodes were present during training	Designed for it: sample the fan-out and run one forward pass	Works if the new node has features, since attention is edge-local
Per-layer cost	O(\|E\| d + \|V\| d^2), memory scales with the whole graph	O(B x prod S_l x d) per batch, independent of \|V\|	K x O(\|E\| d), plus K\|E\| stored coefficients and their gradients
Dominant failure mode	Over-smoothing beyond two or three layers; hubs are dampened by construction	Sampling variance and unstable embeddings; fan-out explodes at three or more layers	Edge-bound memory; static attention ranking, which GATv2 fixes

August 20, 2026

DL0190 GNN Message Passing Paradigm

What is the Message Passing Paradigm in Graph Neural Networks, and how does it unify node, edge, and graph-level predictions through neighborhood aggregation and update functions?

Answer

Message passing is the observation that almost every graph neural network layer can be written as three functions applied in the same order: a message function that runs once per edge, a permutation-invariant aggregation over each node’s neighborhood, and an update function that mixes the aggregate with the node’s previous state. Stacking $K$ such layers gives every node a representation that summarizes its $K$ -hop neighborhood, so depth and receptive field are the same knob. GCN, GraphSAGE, GAT, and GIN differ only in how they instantiate the message and the aggregator, which is why one implementation of the scatter-gather loop covers all of them. The unification across prediction granularities is equally mechanical, because the encoder is identical in all three cases and only the readout changes: a node label reads $h_v$ directly, an edge or link score reads the pair $(h_u, h_v)$ , and a graph label reads a pooled summary of all node states. Training therefore differs in the loss and label granularity, not in the architecture.

(1) Message Function: $\phi$ runs once per directed edge and may use the source state, the target state, and the edge features, which is how bond types or relation types enter the computation.
(2) Permutation-Invariant Aggregation: the neighborhood is an unordered multiset, so $\bigoplus$ must be sum, mean, max, or attention-weighted sum; anything order-dependent makes the layer ill-defined.
(3) Update Function: $\psi$ combines the old state with the aggregate, usually a linear map plus nonlinearity, and in deep stacks a residual connection to keep the node’s own signal alive.
(4) Depth Equals Receptive Field: after $K$ rounds a node has seen exactly its $K$ -hop subgraph, so long-range tasks need either depth or a shortcut mechanism.
(5) One Encoder, Three Heads: node, edge, and graph predictions are three readouts over the same embedding matrix, which lets you pretrain on one granularity and fine-tune on another.
(6) Cost Scales With Edges: a layer is $O(|E|d + |V|d^2)$ , sparse in the graph and independent of the diameter, which is why message passing scales where dense pairwise attention does not.

Diagram of one message passing layer: a small graph on the left with a target node v receiving solid message arrows from three neighbors and dashed edges to two-hop nodes, feeding a three-box pipeline on the right labeled message function phi per edge, permutation-invariant aggregation with sum mean or max, and update function psi producing the new node state

Figure 1: One layer, three functions. Every incident edge produces a message, the messages collapse into a single vector through a permutation-invariant operator, and the update mixes that vector with the node’s previous state. The dashed two-hop nodes contribute nothing at this layer; they only reach $v$ after a second round, which is what makes depth and receptive field the same quantity.

The reason this paradigm generalizes so well is that it commits to locality and permutation equivariance and nothing else. There is no assumption of a fixed node ordering, a fixed degree, or a fixed graph size, so the same trained weights apply to a 12-atom molecule and a 40-atom molecule. The interesting design freedom sits in the aggregator. Mean pooling normalizes away degree, which helps on citation graphs where degree is a popularity artifact and hurts on tasks where the count itself is the signal. Sum pooling keeps the count and is what makes GIN as discriminative as the 1-Weisfeiler-Lehman test, the theoretical ceiling for standard message passing. Max pooling behaves like a feature detector and is robust to noisy neighbors but blind to multiplicity.

Mathematical Formulation:
$m_{uv}^{(k)} = \phi^{(k)}(h_v^{(k-1)}, h_u^{(k-1)}, e_{uv})$
$a_v^{(k)} = \bigoplus_{u \in \mathcal{N}(v)} m_{uv}^{(k)}$
$h_v^{(k)} = \psi^{(k)}(h_v^{(k-1)}, a_v^{(k)})$
$h_G = R(\{ h_v^{(K)} : v \in V \})$

Where:

$h_v^{(k)} \in \mathbb{R}^{d}$ is the state of node $v$ after $k$ rounds, with $h_v^{(0)}$ the input node features.
$m_{uv}^{(k)}$ is the message sent from neighbor $u$ to $v$ , and $a_v^{(k)}$ is the aggregated neighborhood vector.
$\phi^{(k)}$ and $\psi^{(k)}$ are the learned message and update functions, typically small MLPs or a single linear layer with a nonlinearity.
$\bigoplus$ is a permutation-invariant operator over a multiset, most often sum, mean, or max.
$\mathcal{N}(v)$ is the neighbor set of $v$ and $e_{uv}$ the optional edge feature vector.
$k \in \{1, \ldots, K\}$ indexes rounds, so $K$ is both the layer count and the hop radius of the receptive field.
$R$ is the graph readout, itself permutation invariant, producing the whole-graph vector $h_G$ .

Diagram showing an input graph feeding a stack of K message passing layers that produces a node embedding matrix, which then branches into three heads: a node head applied per node, an edge head applied to the concatenation of two endpoint embeddings, and a graph head applied after a permutation-invariant readout pooling

Figure 2: The encoder is shared and only the readout changes. Node classification consumes $h_v$ , link prediction consumes a symmetric function of the endpoint pair, and graph regression consumes a pooled summary. This is why a single library implements all three task families with one message passing loop and three thin heads.

The Three Readouts:
$\hat y_v = f_n(h_v^{(K)})$
$\hat y_{uv} = f_e([h_u^{(K)} ; h_v^{(K)}])$
$\hat y_G = f_g(h_G)$

For link prediction the pair function should be symmetric on undirected graphs, so practitioners use the Hadamard product $h_u \odot h_v$ or a dot product rather than a raw concatenation, which is order-dependent unless both orders are trained. A concrete instantiation makes the abstraction less slippery. GCN takes the message to be a degree-normalized copy of the neighbor state and folds the update into one linear map:

GCN As A Message Passing Layer:
$c_{uv} = 1 / \sqrt{d_u d_v}$
$h_v^{(k)} = \sigma \Big( W^{(k)} \sum_{u \in \tilde{\mathcal{N}}(v)} c_{uv} h_u^{(k-1)} \Big)$
$\text{cost} = O(K|E|d + K|V|d^2)$

Here $d_u$ is the degree of $u$ and $\tilde{\mathcal{N}}(v)$ includes $v$ itself through the self-loop, so GCN is a fixed-coefficient weighted mean with no learned message. GAT replaces $c_{uv}$ with a learned attention weight, GraphSAGE concatenates the self state instead of summing it in, and GIN uses a sum with an MLP update. Only the choice of $\phi$ , $\bigoplus$ , and $\psi$ changes.

Property	Sum	Mean	Max
Keeps degree information	Yes, the magnitude grows with degree	No, degree is normalized away	No, only the strongest signal survives
Distinguishes multisets	Injective with an MLP update, so 1-WL expressive (GIN)	Confuses {a, a} with {a}	Confuses {a, b} with {a, b, b}
Scale stability	Poor on heavy-tailed degrees, needs normalization	Good, activations stay bounded	Good, but gradients reach one neighbor only
Typical use	Molecular property prediction where atom counts matter	Citation and social graphs with hub nodes	Point clouds and noisy neighborhoods

Two structural limits follow directly from the paradigm rather than from any particular implementation. Over-smoothing means that repeated neighborhood averaging drives node states toward a low-dimensional, degree-dependent subspace, so accuracy on node tasks often peaks at 2 to 4 layers. Over-squashing means that a node’s $K$ -hop neighborhood can grow exponentially while its state stays a fixed $d$ -vector, so information from distant nodes is compressed through bottleneck edges and effectively lost. Both are reasons that deeper is not automatically better, and both motivate residual connections, jumping-knowledge readouts, graph rewiring, and virtual global nodes.

August 20, 2026