A General Perspective on GNNs

Chapter 1: GCN as MSG + AGG

Now that we have the unified framework, let's re-read GCN through this lens. You already know GCN from Lecture 3 — but seeing it as MSG + AGG reveals the specific choices Kipf & Welling made, and makes it easy to compare with GraphSAGE and GAT.

GCN's Message Function

In GCN, the message from neighbor u to node v is a linear transformation of u's embedding, normalized by both their degrees:

This is symmetric normalization — normalize by the geometric mean of both degrees. The motivation: if u has 100 neighbors, it sends weaker messages (its influence is "diluted" across 100 targets). If v has 100 neighbors, each incoming message is weaker (v averages 100 signals). This prevents high-degree nodes from dominating.

GCN's Aggregation Function

Aggregation is a sum (which after normalization becomes a weighted mean). Self-loop is included via an augmented graph à = A + I, so node v is in its own neighborhood:

Because the messages are normalized, this sum is effectively a weighted mean where higher-degree neighbors contribute less. The self-loop means v's own previous embedding participates in the sum with weight 1/|Ñ(v)| where Ñ includes v itself.

Data Flow in GCN

Let's be precise about tensor shapes. Graph: n = 1000 nodes. Input features: d_in = 64. Two GCN layers with d_hidden = 128, d_out = 64.

What GCN Gets Wrong

GCN uses uniform weights — every neighbor contributes equally (after degree normalization). But in a citation network, a paper cited by Nature and a paper cited by an obscure blog are very different. Should they carry the same weight in a neighbor's embedding? GCN says yes. GAT will say no.

Also, GCN's normalization by degree is a hand-crafted heuristic. Why geometric mean? Why not just v's degree? Why not something learned? GraphSAGE and GAT replace this heuristic with learned components.

Chapter 2: GraphSAGE

Hamilton, Ying, and Leskovec introduced GraphSAGE (Graph SAmple and aggreGatE) at NeurIPS 2017. The motivation was inductive learning: train on one graph (e.g., a portion of Reddit), run inference on new, unseen graphs or new nodes. GCN was transductive — it needed to see the full graph adjacency matrix during training. GraphSAGE fixes this with a key architectural difference: it keeps the node's own embedding separate from its neighborhood summary, and concatenates them.

The Two-Stage Update

GraphSAGE replaces the single pooled sum of GCN with an explicit two-stage operation:

Stage 1 — Aggregate from neighbors:

Stage 2 — Concatenate self with neighborhood summary, then transform:

The symbol ∥ means concatenation. If h_v^(l-1) is d-dimensional and h_N(v)^(l) is d-dimensional, then the concatenated vector is 2d-dimensional. W^(l) maps from 2d to d.

Three AGG Options

GraphSAGE proposes three aggregation functions for Stage 1:

In practice, mean-aggregation and pool-aggregation perform similarly. LSTM is often not worth the extra complexity and broken permutation invariance. The real win of GraphSAGE over GCN comes from the concat architecture, not from fancy AGG functions.

Inductive Learning via Sampling

GraphSAGE also introduced neighbor sampling: instead of aggregating over ALL neighbors (which can be 10,000 for hub nodes in a social graph), sample a fixed-size subset S (typically 25 for layer 1, 10 for layer 2). This makes mini-batch training feasible on massive graphs. The expected gradient is still an unbiased estimate of the full gradient.

python
import torch
import torch.nn as nn

class GraphSAGELayer(nn.Module):
    def __init__(self, in_dim, out_dim):
        super().__init__()
        # W maps from concatenated [self || neighbors] to output
        self.W = nn.Linear(in_dim * 2, out_dim)
        self.activation = nn.ReLU()

    def forward(self, h, adj):
        # h: [N, in_dim] node features
        # adj: [N, N] adjacency (normalized, no self-loops)

        # Stage 1: aggregate neighbors (mean)
        deg = adj.sum(dim=1, keepdim=True).clamp(min=1)  # [N, 1]
        h_neigh = (adj @ h) / deg  # [N, in_dim] — mean of neighbors

        # Stage 2: concatenate self + neighbor, then transform
        h_cat = torch.cat([h, h_neigh], dim=-1)  # [N, 2*in_dim]
        h_out = self.activation(self.W(h_cat))    # [N, out_dim]

        # Optional: L2 normalize (common in inductive settings)
        h_out = h_out / h_out.norm(dim=-1, keepdim=True).clamp(min=1e-6)
        return h_out

PinSage: GraphSAGE at Billion Scale

GraphSAGE's neighbor-sampling design made it the foundation for PinSage, Pinterest's industrial GNN for image recommendation (Ying et al., KDD 2018). PinSage operates on a graph with 3 billion nodes (pins) and 18 billion edges — the full graph would require 100TB of memory just to store. Key adaptations:

Chapter 3: Graph Attention Networks (Showcase)

GCN and GraphSAGE both treat neighbor importance as a fixed, hand-crafted function of degree. A neighbor with degree 1 contributes more than a neighbor with degree 100, simply because of the normalization. But surely the content of a neighbor matters more than its structural position? That's the question GAT (Velickovic et al., ICLR 2018) answers.

GAT learns attention weights α_vu that tell node v how much to attend to each neighbor u. These weights depend on the features of both v and u — two nodes with very different features might warrant a small weight, while two similar nodes warrant a large weight. Crucially, these weights are learned, not hand-designed.

Step 1: Compute Raw Attention Coefficients

First, transform both node embeddings with the same weight matrix W, then score their compatibility with a small neural network parametrized by vector a:

Breaking this down: W h_v and W h_u project both embeddings into the same space. Concatenating them gives a vector of length 2d'. The learnable vector a (length 2d') scores this concatenation with a single dot product. LeakyReLU allows negative scores (unlike ReLU, which would kill half the scores). The result e_vu is a scalar — how "compatible" v and u are.

Step 2: Normalize with Softmax

Raw scores are incomparable across different nodes (different scales). Normalize them into a proper probability distribution over v's neighborhood:

Now Σ_u∈N(v) α_vu = 1, and all weights are positive. Node v's attention over its neighbors is a proper distribution — it sums to 1, and we can interpret each α_vu as "what fraction of attention v gives to u."

Step 3: Weighted Aggregation

Use the attention weights to compute a weighted sum of neighbors' transformed embeddings:

Compare to GCN: replace the uniform weight 1/|N(v)| with the learned weight α_vu. Same structure, but now the network decides which neighbors matter most — for EACH node, EACH layer, based on features.

A Concrete Worked Example

Let's trace through one step of GAT for a small graph. Say node v has features h_v = [1.0, 0.5] and has neighbors A with h_A = [0.9, 0.6] and B with h_B = [0.1, 0.8].

Setup: W = I (identity, so Wh = h), a = [1, -1, 0.5, -0.5] (first two dims = source, last two = target).

Score for v→A: [Wh_v ∥ Wh_A] = [1.0, 0.5, 0.9, 0.6].
a^T · this = 1(1.0) + (-1)(0.5) + 0.5(0.9) + (-0.5)(0.6) = 1.0 - 0.5 + 0.45 - 0.30 = 0.65.
LeakyReLU(0.65) = 0.65.

Score for v→B: [Wh_v ∥ Wh_B] = [1.0, 0.5, 0.1, 0.8].
a^T · this = 1.0 - 0.5 + 0.5(0.1) + (-0.5)(0.8) = 0.5 + 0.05 - 0.40 = 0.15.
LeakyReLU(0.15) = 0.15.

Softmax: exp(0.65) = 1.916, exp(0.15) = 1.162. Sum = 3.078. α_vA = 1.916/3.078 = 0.623, α_vB = 1.162/3.078 = 0.377.

Output: h_v^new = σ(0.623 · [0.9, 0.6] + 0.377 · [0.1, 0.8]) = σ([0.598, 0.678]) ≈ [0.645, 0.663] (with sigmoid).

Notice: node A (more similar to v) gets 62.3% of the attention, node B (less similar) gets 37.7%. The network has learned — from the parameters W and a — to prefer more compatible neighbors. And this all happened via gradient descent on the task loss, not via any manual similarity function.

Chapter 4: Multi-Head Attention

A single set of attention weights asks ONE question about each neighbor: "how important is u to v?" But importance can have multiple dimensions. In a citation network, paper v might attend to paper u because they share a topic — and simultaneously attend to paper w because they use similar methods. A single attention head can only capture one notion of importance at a time.

Multi-head attention runs K independent attention mechanisms in parallel, each with its own parameters W^k and a^k. Each head learns to attend to different aspects of the neighborhood.

The Multi-Head Formula

Run K heads, get K output embeddings per node, then concatenate:

The notation ∥ means concatenation. If each head outputs a d/K-dimensional vector, the concatenated output is d-dimensional — same total size as a single-head model. Each head^k has its own attention weights α^k_vu computed with its own parameters (W^k, a^k).

Why Multiple Heads Stabilize Training

Think of K heads as a K-model ensemble. If one head learns a bad set of attention weights early in training, the other K-1 heads can compensate. The gradient signal averaged across heads is lower-variance than a single head — similar to why mini-batch SGD is more stable than single-sample gradient estimates.

Empirically, GAT with K=8 heads consistently outperforms K=1. The improvement plateaus around K=8; more heads add parameters but not much accuracy. In the original paper: K=8 for all but the last layer (where K=1 averaging is used).

Parameter Count

One GAT layer with d_in input dimensions, d_out output dimensions, K heads:

Vs GCN one layer: d_in × d_out = 64 × 64 = 4096 parameters. GAT adds only 128 extra parameters (the attention vectors a^k) over GCN — a tiny cost for learned attention weights.

Implementing Multi-Head GAT in PyTorch Geometric

python
import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.nn import GATConv

class TwoLayerGAT(nn.Module):
    def __init__(self, d_in, d_hid, d_out, K=8):
        super().__init__()
        # Layer 1: K=8 heads, each head outputs d_hid//K → concat = d_hid
        self.gat1 = GATConv(d_in, d_hid // K, heads=K, concat=True,
                            dropout=0.6, negative_slope=0.2)
        # Layer 2: K=1 (or average K=8), outputs d_out
        self.gat2 = GATConv(d_hid, d_out, heads=1, concat=False,
                            dropout=0.6, negative_slope=0.2)
        self.dropout = nn.Dropout(p=0.6)

    def forward(self, x, edge_index):
        x = self.dropout(x)
        x = F.elu(self.gat1(x, edge_index))  # [N, d_hid]
        x = self.dropout(x)
        x = self.gat2(x, edge_index)          # [N, d_out] — averaged heads
        return F.log_softmax(x, dim=-1)

# The exact architecture from the GAT paper (Cora: 8-head hidden, 1-head output)
model = TwoLayerGAT(d_in=1433, d_hid=64, d_out=7, K=8)
# d_in=1433 (Cora bag-of-words), d_out=7 (7 classes), K=8 heads in hidden layer

Chapter 5: GCN vs GraphSAGE vs GAT

Now we can make the comparison crisp. All three operate within the MSG + AGG framework — they're just different choices. The table below is the one mental model you should carry forward from this lecture.

Code Comparison: One Forward Pass

Here are the three models side by side in PyTorch Geometric. Notice how the aggregation step is the only thing that changes.

python
from torch_geometric.nn import GCNConv, SAGEConv, GATConv

# GCN: symmetric normalization, single W matrix
gcn_layer = GCNConv(in_channels=64, out_channels=128)
h_gcn = gcn_layer(x, edge_index)  # x: [N, 64] → [N, 128]

# GraphSAGE: mean AGG, concat self+neigh, 2× input to W
sage_layer = SAGEConv(in_channels=64, out_channels=128)
h_sage = sage_layer(x, edge_index)  # x: [N, 64] → [N, 128]

# GAT: learned attention, K=8 heads, concat output
gat_layer = GATConv(in_channels=64, out_channels=16, heads=8, concat=True)
h_gat = gat_layer(x, edge_index)  # x: [N, 64] → [N, 128] (16 × 8 heads)

# All produce [N, 128] — same shape, different computation inside

Chapter 6: Stacking GNN Layers

With one GNN layer, each node "sees" its 1-hop neighborhood. With K layers, it sees its K-hop neighborhood. More layers should mean richer representations, right? In practice, deeper GNNs often perform WORSE than shallow ones — a phenomenon called over-smoothing.

What Over-Smoothing Is

Let's think about what repeated mean aggregation does. After 1 layer: each node's embedding is the average of its neighbors' features. After 2 layers: it's the average of averages. After K layers: the embedding is a weighted average over the K-hop neighborhood — and as K grows, this neighborhood covers more and more of the graph.

In an Erdős-Rényi random graph with average degree d, after O(log_d n) layers, the K-hop neighborhood covers the entire graph. At that point, EVERY node's embedding is a weighted average over ALL nodes — they all converge to the same vector. The embeddings are fully mixed. This is over-smoothing.

A Spectral View

From a signal processing perspective, GCN applies a low-pass filter to the graph signal. The graph Laplacian L = D - A has eigenvalues in [0, 2d] where d is max degree. GCN corresponds to multiplying the graph signal by (I - D^-1/2 A D^-1/2) — a filter that attenuates high-frequency components (nodes that differ from their neighbors). After K layers, this filter is applied K times, suppressing high-frequency information exponentially. The NODES THAT DIFFER FROM THEIR NEIGHBORHOOD are exactly the ones you want to distinguish — and GCN erases them with enough layers.

How Deep Should You Go?

In practice: 2-3 layers for most tasks. If you need a 7-hop receptive field, don't use 7 GNN layers — use the graph structure more cleverly (multi-hop connections, virtual nodes). This is different from CNNs and Transformers, where going deeper almost always helps.

Chapter 7: Skip Connections

You hit a wall: shallow GNNs can't see far enough, deep GNNs over-smooth. The solution comes from an unlikely source — ResNets. He et al. (2015) showed that adding a skip connection (identity shortcut) from layer l to layer l+1 prevents degradation in very deep CNNs. The same trick works for GNNs.

Residual GNN

The residual update adds the previous layer's embedding directly:

This ensures that even if the GNN layer "messes up" (e.g., over-smooths), the skip connection passes through the pre-smoothed embedding unchanged. The network can learn to use the skip connection when aggregation hurts (set GNN_layer output ≈ 0) and to use the GNN output when aggregation helps.

Jumping Knowledge Networks (JK-Net)

Xu et al. (2018) proposed a more aggressive version: instead of adding consecutive layers, concatenate embeddings from ALL K layers and aggregate them at the end. This is called a JK-Net (Jumping Knowledge):

Where AGG is typically max-pooling or LSTM over the layer sequence. Each layer h_v^(l) captures a different scale: layer 1 sees 1-hop, layer 2 sees 2-hop, etc. JK-Net lets each node adaptively select which scale of neighborhood information is most useful for its task.

Comparison of Approaches

python
class ResidualGNN(nn.Module):
    def __init__(self, d, K):
        super().__init__()
        self.layers = nn.ModuleList([GCNConv(d, d) for _ in range(K)])

    def forward(self, x, edge_index):
        h = x
        for layer in self.layers:
            h = F.relu(layer(h, edge_index)) + h  # skip connection
        return h

class JKNet(nn.Module):
    def __init__(self, d, K):
        super().__init__()
        self.layers = nn.ModuleList([GCNConv(d, d) for _ in range(K)])

    def forward(self, x, edge_index):
        h = x
        all_hs = []
        for layer in self.layers:
            h = F.relu(layer(h, edge_index))
            all_hs.append(h)
        # Max-pool across all layer embeddings
        return torch.stack(all_hs, dim=0).max(dim=0).values

Chapter 8: Practical GNN Design

Theory tells you what's possible. Practice tells you what actually works. You, Ying, and Leskovec (NeurIPS 2020) ran a massive systematic evaluation across 12 graph datasets and over 300,000 GNN configurations. Their key finding: there's no universally best GNN design, but there are reliable rules of thumb.

What You et al. (2020) Found

The Practical Recipe

Dropout Placement in GNNs

Where you place dropout in a GNN matters more than in standard DNNs. Three options:

Batch Normalization for GNNs

Apply BatchNorm after each GNN layer, before the activation. This normalizes node embeddings across the batch of nodes — analogous to normalizing across the batch in standard DNNs. For mini-batch training (where batch = subgraph), use the mini-batch statistics (standard PyTorch BatchNorm works). Empirically, BatchNorm is especially important for K≥3 layers.

python
class PracticalGNN(nn.Module):
    def __init__(self, d_in, d_hid, d_out, K=3):
        super().__init__()
        dims = [d_in] + [d_hid] * (K - 1) + [d_out]
        self.convs = nn.ModuleList(
            [GCNConv(dims[i], dims[i+1]) for i in range(K)]
        )
        self.bns = nn.ModuleList(
            [nn.BatchNorm1d(dims[i+1]) for i in range(K - 1)]
        )
        self.dropout = nn.Dropout(p=0.5)

    def forward(self, x, edge_index):
        for i, conv in enumerate(self.convs):
            x = conv(x, edge_index)
            if i < len(self.bns):
                x = F.relu(self.bns[i](x))  # BN then ReLU
                x = self.dropout(x)
        return x  # final layer: no BN, no ReLU, no dropout

When to Use Each Architecture: Decision Guide

Chapter 9: Connections

You now understand the GNN design space: MSG + AGG, with GCN / GraphSAGE / GAT as three points in it. You understand over-smoothing and how skip connections address it. Here's where this knowledge connects to the broader landscape.

Where We've Been

Where GAT Lives in the Broader Picture

GAT replaces the graph Laplacian with a learned, input-dependent filter. This makes it structurally similar to Transformers — in fact, a Transformer is just GAT on a fully-connected graph (every token attends to every other token). The GAT attention mechanism (concat then LeakyReLU) is the "additive attention" variant; Transformers use "scaled dot-product attention." Both are valid choices in the same design space.

Read the original GAT paper in full detail:

Graph Attention Networks — Velickovic et al., ICLR 2018 →

Where GraphSAGE Lives

GraphSAGE's inductive formulation was the foundation for PinSage (Ying et al., KDD 2018) — Pinterest's production GNN that ran on 3 billion nodes. The key insight was that neighbor sampling + mini-batch training + inductive inference made billion-scale GNNs feasible. No full adjacency matrix ever fits in memory.

GNN Expressiveness and the WL Test

All the GNNs we've covered have a fundamental expressiveness limit: they are at most as powerful as the 1-Weisfeiler-Lehman graph isomorphism test. This means there exist pairs of non-isomorphic graphs that all MSG + AGG GNNs map to the same embedding. GIN (Graph Isomorphism Network, Xu et al. 2019) characterizes exactly when a GNN IS as powerful as 1-WL: it uses SUM aggregation (not mean or max) and applies an MLP with sufficient capacity. Mean and max aggregation are strictly less expressive. This is coming in CS224W Lecture 5.

Hyperparameter Grid for GNN Experiments

Before changing architecture, sweep these hyperparameters first (in order of typical impact):

Graph Augmentation: Beyond Architecture

Sometimes the best way to improve GNN performance is not to change the architecture but to change the GRAPH. Graph augmentation adds or removes edges/nodes to make the structure more amenable to message passing:

• Virtual nodes: Add one super-node connected to ALL real nodes. After K layers, any real node can communicate with any other through the virtual node in just 2 hops. Dramatically reduces over-squashing without adding GNN layers. Simple and often very effective.
• Position encodings: Compute Laplacian eigenvectors (global structural positions) and concatenate them to node features. Nodes with similar eigenvector entries have similar global roles. Gives GNNs "global awareness" at layer 0.
• Edge dropout (DropEdge): Randomly remove edges during training. Prevents over-smoothing by reducing the number of paths information can travel. Equivalent to edge-level data augmentation.

The GNN Design Space as Transfer Learning

One underappreciated benefit of the design space framework: the same trained GNN can transfer across similar graph domains. If you train GraphSAGE on a social network recommendation task and want to apply it to a protein interaction network, the architecture is the same — only the input features and output labels differ. The message function (W h_u) and the concat-then-transform aggregation are domain-agnostic operations. You can fine-tune a pretrained GNN on a new graph domain with far less data than training from scratch.

This is analogous to how CNNs trained on ImageNet transfer to medical imaging — the low-level pattern detectors (edges, textures) are domain-general. In GNNs, the message-passing pattern (aggregate-and-combine) is domain-general; the learned weights encode domain-specific notions of what makes a "good" neighborhood summary.

The 1-WL Test and GNN Expressiveness

All the GNNs in this lecture — GCN, GraphSAGE, GAT — have a shared theoretical ceiling on expressiveness: they are at most as powerful as the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test. This test is an efficient algorithm that decides whether two graphs are isomorphic by iteratively relabeling nodes with their sorted neighbor label multisets. If two graphs produce the same 1-WL coloring, the test fails to distinguish them.

Xu et al. (2019) proved: any MSG + AGG GNN is at most as expressive as 1-WL. Moreover, if AGG is SUM and MSG is any injective function, the GNN is exactly as expressive as 1-WL. This gives us a concrete design target: use SUM aggregation for maximum expressiveness. Mean and Max are strictly less expressive — they lose count information (mean can't distinguish "two neighbors with value 1" from "one neighbor with value 2").

GIN (Graph Isomorphism Network, Xu et al. 2019) instantiates the maximally expressive GNN: uses SUM aggregation with an MLP, and includes the center node's own embedding: h_v^(k) = MLP((1+ε) h_v^(k-1) + Σ_u∈N(v) h_u^(k-1)). The (1+ε) weight distinguishes the center from its neighbors. This is the theoretical optimal within the MSG + AGG framework.

What's Next

CS224W Lecture 5: GNN Augmentation — how to make GNNs more expressive by augmenting the graph (virtual nodes, position encodings, subgraph features). The lesson also covers GNN expressiveness theory (1-WL test, GIN). Stay tuned.

Software Ecosystem

All three architectures (GCN, GraphSAGE, GAT) are available as drop-in layers in modern graph ML libraries:

• PyTorch Geometric (PyG): GCNConv, SAGEConv, GATConv, GATv2Conv. Each implements the paper's algorithm exactly. The MessagePassing base class lets you implement your own MSG+AGG GNN in ~20 lines.
• Deep Graph Library (DGL): Similar set with slightly different API. DGL's built-in functions (fn.copy_u, fn.mean, etc.) map directly to the MSG+AGG framework — reading DGL code IS reading MSG+AGG code.
• GraphNets / JAX-based: Jraph (DeepMind) and graph_nets express GNNs as graphs with node, edge, and global features — the most general MSG+AGG formulation, naturally handling edge features and global readouts.
• Benchmarks: Open Graph Benchmark (OGB) provides standardized splits and evaluations for 10+ graph tasks across multiple domains. Always compare on OGB if publishing — Cora/Citeseer are saturated and have reproducibility issues with different data splits.

"The most important insight in GNN design is that there is no universally optimal architecture. The choice of MSG and AGG functions should be guided by the structure of your problem — specifically, by whether neighbor importance is uniform, structure-dependent, or content-dependent."
— You, Ying, Leskovec, NeurIPS 2020