Graph Neural Networks: Foundations

Most ML engineers learn to think in matrices and sequences. Graphs are the structure you reach for when neither works — when the data has irregular connectivity, variable-degree neighborhoods, and semantics that live on edges, not just nodes. This file builds the core message-passing abstraction, three concrete GNN architectures (GCN, GraphSAGE, GAT), and grounds every concept in production deployment evidence before you touch PyTorch Geometric.

---

1. Why Graphs? The Structural Argument

Standard deep learning assumes:

• CNNs: regular grid, fixed-size receptive field, translation equivariance

• Transformers: sequence of uniform tokens, O(n²) all-pairs attention

• MLPs: independent i.i.d. samples, no structural relationship

None of these fit:

Domain	Graph Structure	Why Standard Arch Fails
Molecules	Atoms = nodes, bonds = edges	Variable atom count, bond type encodes chemistry, no canonical ordering
Social networks	Users = nodes, follows = edges	3B+ nodes, sparse, node degree varies 1–10M
Knowledge graphs	Entities = nodes, relations = edges	Heterogeneous edge types, multi-hop reasoning required
Protein structures	Residues = nodes, spatial proximity = edges	AlphaFold2 (arXiv:2021.07611) uses this — solved 200M protein structures
Road networks	Intersections = nodes, roads = edges	Variable topology, ETA depends on graph structure
Code ASTs	Tokens = nodes, syntactic dependencies = edges	Tree structure that a sequence model flattens incorrectly

The defining property of graphs: permutation invariance. The prediction for a node should not depend on the arbitrary integer index assigned to that node or its neighbors. GNNs are built to satisfy this by construction.

---

2. The Message Passing Framework

Every GNN variant from 2016–2024 is a specialization of this single framework (Gilmer et al., arXiv:1704.01212):

Step 1: Message

For each directed edge (u → v), compute a message from neighbor u to node v:

m_{u→v}^{(k)} = φ^{(k)}(h_u^{(k)}, h_v^{(k)}, e_{uv})

• h_u^{(k)}: feature vector of node u at layer k

• e_{uv}: edge feature (if present)

• φ: any differentiable function (MLP, dot product, etc.)

Step 2: Aggregate

Collect all incoming messages for node v:

M_v^{(k)} = ρ({m_{u→v}^{(k)} : u ∈ N(v)})

• ρ must be permutation invariant (order of neighbors must not matter)

• Common choices: sum, mean, max. Sum preserves count information, mean normalizes by degree, max captures the “loudest” neighbor.

Step 3: Update

Produce the new node representation:

h_v^{(k+1)} = σ(W^{(k)} · CONCAT(h_v^{(k)}, M_v^{(k)}) + b^{(k)})

After K layers, h_v encodes information from the K-hop neighborhood of v. This is the receptive field of a GNN.

---

3. GCN — Graph Convolutional Network (Kipf & Welling, arXiv:1609.02907)

The workhorse. Simple, well-understood, often adequate.

The spectral-to-spatial approximation produces a clean layer rule:

H^{(k+1)} = σ(D̂^{-1/2} Â D̂^{-1/2} H^{(k)} W^{(k)})

Where:

• Â = A + I (adjacency matrix with self-loops added)

• D̂ = degree matrix of Â

• D̂^{-1/2} Â D̂^{-1/2}: symmetric normalization — divides by √(degree_u × degree_v) for each edge

Why symmetric normalization? Without it, high-degree nodes receive massive aggregated signals; the scale of features depends on node degree rather than node content. Normalization makes the aggregation degree-invariant.

Limitation: All neighbors weighted equally. The model has no mechanism to distinguish which neighbor is relevant.

import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv
from torch_geometric.datasets import Planetoid

# Load Cora: 2708 nodes, 10556 edges, 7 classes, 1433 features
dataset = Planetoid(root='./data/Cora', name='Cora')
data = dataset[0]  # Single graph

class GCN(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels):
        super().__init__()
        self.conv1 = GCNConv(in_channels, hidden_channels)
        self.conv2 = GCNConv(hidden_channels, out_channels)

    def forward(self, x, edge_index):
        x = F.relu(self.conv1(x, edge_index))
        x = F.dropout(x, p=0.5, training=self.training)
        return self.conv2(x, edge_index)

model = GCN(dataset.num_features, 64, dataset.num_classes)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

def train():
    model.train()
    optimizer.zero_grad()
    out = model(data.x, data.edge_index)
    loss = F.cross_entropy(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()
    return loss.item()

@torch.no_grad()
def test():
    model.eval()
    out = model(data.x, data.edge_index).argmax(dim=1)
    accs = []
    for mask in [data.train_mask, data.val_mask, data.test_mask]:
        accs.append(float((out[mask] == data.y[mask]).sum()) / mask.sum())
    return accs

for epoch in range(200):
    loss = train()

train_acc, val_acc, test_acc = test()
print(f"Train: {train_acc:.3f} | Val: {val_acc:.3f} | Test: {test_acc:.3f}")
# Expected: Test accuracy ~81%

---

4. GraphSAGE — Inductive Learning (Hamilton et al., arXiv:1706.02216)

The production workhorse. GCN requires the full graph adjacency matrix during training — it’s transductive (cannot handle new nodes at inference). GraphSAGE fixes this.

Key changes:

1. Neighborhood sampling: instead of aggregating all neighbors, sample a fixed-size subset (e.g., 25 neighbors for layer 1, 10 for layer 2). This makes mini-batch training tractable on billion-node graphs.

2. CONCAT instead of only aggregate: the node’s own representation is concatenated with the aggregated neighborhood, then linearly projected. The node retains its identity.

3. Inductive: learned parameters are aggregation functions and weight matrices, not node-specific embeddings. A new node with features can be immediately embedded without retraining.

h_v^{k+1} = σ(W · CONCAT(h_v^k, MEAN({h_u^k : u ∈ SAMPLE(N(v))})))

Production deployment evidence: Pinterest deployed GraphSAGE on a graph of 3 billion nodes and 18 billion edges for pin recommendation (PinSage, Ying et al. 2018). The system serves live recommendations at Pinterest scale — this is the most validated GNN production deployment on record.

from torch_geometric.nn import SAGEConv

class GraphSAGE(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels):
        super().__init__()
        self.conv1 = SAGEConv(in_channels, hidden_channels, aggr='mean')
        self.conv2 = SAGEConv(hidden_channels, out_channels, aggr='mean')

    def forward(self, x, edge_index):
        x = F.relu(self.conv1(x, edge_index))
        x = F.dropout(x, p=0.5, training=self.training)
        return self.conv2(x, edge_index)

---

5. GAT — Graph Attention Network (Veličković et al., arXiv:1710.10903)

The expressive option. GAT learns per-edge attention weights instead of using fixed normalized weights. High-degree nodes stop dominating; the model learns which neighbors are actually informative.

The attention coefficient between node i and neighbor j:

e_{ij} = LeakyReLU(a^T [W h_i || W h_j])
α_{ij} = softmax_j(e_{ij}) = exp(e_{ij}) / Σ_{k ∈ N(i)} exp(e_{ik})
h_i' = σ(Σ_{j ∈ N(i)} α_{ij} W h_j)

Multi-head: run K independent attention heads, concatenate (or average at the final layer).

When GAT wins over GCN: when neighbor importance is heterogeneous — e.g., in citation networks where some references are highly relevant and others are boilerplate. On Cora, GAT achieves ~83% vs. GCN’s ~81%.

from torch_geometric.nn import GATConv

class GAT(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels, heads=8):
        super().__init__()
        self.conv1 = GATConv(in_channels, hidden_channels, heads=heads, dropout=0.6)
        # output: hidden_channels * heads
        self.conv2 = GATConv(hidden_channels * heads, out_channels, heads=1,
                             concat=False, dropout=0.6)

    def forward(self, x, edge_index):
        x = F.dropout(x, p=0.6, training=self.training)
        x = F.elu(self.conv1(x, edge_index))
        x = F.dropout(x, p=0.6, training=self.training)
        return self.conv2(x, edge_index)

---

6. Benchmark: Cora Node Classification

Run all three on the same dataset to build calibrated intuition:

Model	Cora Test Acc	Parameters	Key Hyperparams
GCN	~81.5%	~92K	lr=0.01, wd=5e-4, dropout=0.5
GraphSAGE	~81.7%	~92K	lr=0.01, aggr=mean
GAT	~83.0%	~365K	heads=8, lr=0.005, dropout=0.6
GAT (GATv2, arXiv:2105.14491)	~83.7%	~365K	Fixes static attention issue in original GAT

These numbers are from the original papers and community benchmarks. Your run will vary ±0.5% due to random splits.

---

7. Over-Smoothing: The Fundamental GNN Failure Mode

With K message-passing layers, each node aggregates information from its K-hop neighborhood. As K increases:

1. K=1: each node sees its immediate neighbors

2. K=2: each node sees 2-hop neighbors

3. K=6: in a small-world graph (most real networks), each node sees almost every other node

4. K=∞: all node representations converge to the same vector (the principal eigenvector of the diffusion operator)

This is over-smoothing — a mathematical property of iterated graph diffusion, not a training failure. It cannot be fixed by adding more parameters or better regularization.

Empirical consequence: 2-layer GNNs routinely outperform 6-layer GNNs on standard benchmarks. Adding a 7th layer often hurts performance.

Partial mitigations (not complete fixes):

• Residual connections: GCNII (arXiv:2007.02133) adds residual connections back to the original features, achieving competitive performance up to 64 layers

• Jumping Knowledge Networks (JK-Net, arXiv:1806.03536): concatenate representations from all layers, let the model select the best depth per node

• PairNorm (arXiv:1909.12223): normalizes features to prevent collapse

The practical rule: start with 2 layers. Add a 3rd only if you have evidence it helps on your validation set. Never go above 4 without a strong reason.

---

8. GNNs in Production

Deployment	Organization	Scale	Architecture
Pin recommendation	Pinterest	3B nodes, 18B edges	GraphSAGE (PinSage)
ETA prediction	Uber	Road network graphs	Custom GNN
Protein structure	DeepMind (AlphaFold2)	200M+ proteins solved	IPA (Invariant Point Attention)
Drug discovery	Pfizer, AstraZeneca	Molecular graphs	MPNN, SchNet, DimeNet
Fraud detection	PayPal, Amazon	Transaction graphs	GCN, GAT variants
Knowledge graph	Google (Knowledge Graph)	Billions of entities	TransE, RotatE

AlphaFold2 (arXiv:2021.07611) is the most consequential GNN deployment in history. Its Evoformer module uses triangle-multiplicative updates and invariant point attention on protein residue graphs. Before AlphaFold2, the protein folding problem was 50 years unsolved. Two years after release: 200 million protein structures predicted, impacting drug discovery across virtually every major pharmaceutical company.

---

9. PyTorch Geometric Essentials

PyG is the standard library. The key objects:

from torch_geometric.data import Data
import torch

# A simple graph: 4 nodes, 4 edges (undirected → 8 directed edges in COO format)
# Nodes have 3 features each
x = torch.randn(4, 3)          # [num_nodes, num_features]
edge_index = torch.tensor([    # [2, num_edges] COO format
    [0, 1, 1, 2, 2, 3, 0, 3],  # source nodes
    [1, 0, 2, 1, 3, 2, 3, 0]   # target nodes
], dtype=torch.long)
y = torch.tensor([0, 1, 0, 1]) # node labels

data = Data(x=x, edge_index=edge_index, y=y)
print(data)
# Data(x=[4, 3], edge_index=[2, 8], y=[4])

# For batching multiple graphs (graph classification):
from torch_geometric.data import DataLoader
from torch_geometric.data import Batch

# PyG DataLoader handles variable-size graphs by creating a disconnected
# union graph. The 'batch' tensor tracks which node belongs to which graph.

Common pitfall: edge_index must be in COO format (2 × num_edges), not adjacency matrix. Forgetting to add self-loops when the model expects them (GCNConv can add them automatically: add_self_loops=True).

---

10. What Most People Get Wrong

Over-smoothing is not a bug — it’s a theorem. People try to fix it with dropout, batch norm, more parameters, different activations. None of these address the root cause, which is that repeated graph diffusion is a low-pass filter. The fix is architectural (residual connections back to initial features, or adaptive depth selection). Do not spend time debugging what is actually a mathematical limit of the paradigm.

Node classification ≠ graph classification. These require completely different architectures. Node classification uses the full graph context; each node gets a label. Graph classification uses a readout function (global mean/max/sum pooling or hierarchical pooling like DiffPool) to produce a single graph-level representation. Confusing the two is the most common mistake when adapting GNN code from papers to new problems.

Message passing has a limited expressivity ceiling. The Weisfeiler-Leman isomorphism test (WL test) is the exact expressive power of 1-layer GNNs: two graphs that look identical to the WL test look identical to any GNN with the standard message passing. For tasks requiring counting triangles, detecting cycles, or distinguishing certain graph structures, standard GNNs provably fail. Higher-order GNNs (k-GNNs, arXiv:1907.03199) exist but are rarely needed in practice — most real-world tasks don’t hit this ceiling.

---

Key Papers

Paper	arXiv	Year	What It Contributes
GCN	1609.02907	2016	Semi-supervised node classification, spectral→spatial
GraphSAGE	1706.02216	2017	Inductive learning, mini-batch training, neighborhood sampling
GAT	1710.10903	2017	Attention weights on edges, heterogeneous neighbor importance
MPNN	1704.01212	2017	Unified message passing framework
JK-Net	1806.03536	2018	Multi-scale representation, adaptive depth
PinSage	1806.01973	2018	GraphSAGE at Pinterest scale (3B nodes)
GATv2	2105.14491	2021	Fixed static attention in original GAT
AlphaFold2	2021.07611	2021	IPA on protein graphs, solved protein folding

---

Return to [README.md] · Previous: [04_diffusion_models_foundations.md] · Next: [06_phase_projects.md]