Graph Neural Networks

A graph G = (V, E) has nodes V (entities) and edges E (relationships). For ML, it's represented as: (1) Adjacency matrix A ∈ {0,1}^{N×N} where A_{ij}=1 if edge (i,j) exists. (2) Node feature matrix X ∈ R^{N×d} with d features per node. (3) Edge features (optional). Graphs capture relational structure lost in tabular or sequential data. Examples: molecules (atoms=nodes, bonds=edges), social networks (users=nodes, friendships=edges), knowledge graphs, citation networks, and road maps.

import torch
# N nodes, d features, E edges
A = torch.zeros(N, N)  # adjacency
X = torch.randn(N, d)  # node features

Message passing is the core GNN operation: each node aggregates information from its neighbors to update its own representation. Three steps: (1) Message: each neighbor j computes a message m_{ij} = φ(h_i, h_j, e_{ij}). (2) Aggregate: node i aggregates messages: a_i = ⊕_{j ∈ N(i)} m_{ij}, using sum, mean, or max. (3) Update: h_i' = ψ(h_i, a_i). Stacking K message-passing layers allows nodes to incorporate information from K-hop neighborhoods. This framework unifies GCN, GAT, GraphSAGE, and most GNN variants.

# Message passing pseudocode
for node i in graph:
    msgs = [phi(h[i], h[j], e[i,j]) for j in neighbors(i)]
    a[i] = aggregate(msgs)  # sum/mean/max
    h_new[i] = psi(h[i], a[i])

GCN (Kipf & Welling 2017) defines a spectral-based graph convolution simplified to: H^{(l+1)} = σ(D̃^{-1/2} à D̃^{-1/2} H^{(l)} W^{(l)}), where à = A + I (add self-loops), D̃ is the diagonal degree matrix of Ã, and W is a learnable weight matrix. The normalization D̃^{-1/2} à D̃^{-1/2} prevents scale explosion in nodes with many neighbors. Each layer spreads information one hop. GCN is simple, fast, and effective for semi-supervised node classification (e.g., classifying academic paper topics given citation graph).

# GCN layer
A_hat = A + torch.eye(N)  # add self-loops
D_hat = A_hat.sum(1).pow(-0.5).diag()
A_norm = D_hat @ A_hat @ D_hat
H_next = torch.relu(A_norm @ H @ W)

GAT (Veličković et al. 2018) extends GCN by learning attention weights over neighbors: α_{ij} = softmax_j(LeakyReLU(a^T [W h_i || W h_j])). These weights determine how much neighbor j influences node i's update: h_i' = σ(Σ_j α_{ij} W h_j). Unlike GCN's fixed normalized weights, GAT's attention weights are learned and input-dependent, allowing the model to focus on more informative neighbors. Multi-head attention is applied and concatenated or averaged. GAT achieves strong results on node classification benchmarks like Cora, Citeseer, and PubMed.

GraphSAGE (Hamilton et al. 2017) samples a fixed number of neighbors and aggregates their features: h_i' = CONCAT(h_i, AGG({h_j, j ∈ N(i)})), then apply a linear + nonlinearity. Aggregators: mean, max, LSTM. Crucially, GraphSAGE trains on a fixed subset of nodes but the learned aggregation function generalizes to unseen nodes — enabling inductive learning. Unlike GCN (which requires the full graph at training time), GraphSAGE works for dynamic graphs where new nodes appear after training. It's widely used in industrial recommender systems (Pinterest, LinkedIn).

Transductive GNNs (e.g., GCN, GAT) learn node embeddings for a fixed graph. They must retrain or re-run inference on the full graph if new nodes are added — embeddings are specific to the training graph. Inductive GNNs (e.g., GraphSAGE) learn a function that aggregates neighborhood features — applicable to any node in any graph, including new nodes unseen during training. Inductive learning is essential for dynamic graphs (social networks with new users) and generalizing across multiple graphs (molecule classification, where each molecule is a separate graph).

Over-smoothing occurs when stacking many GNN layers causes all node representations to converge to similar values — nodes become indistinguishable. Each layer averages over neighbors; after K layers, each node effectively averages its entire K-hop neighborhood. For large K, this mixes representations from the whole graph. Over-smoothing limits GNN depth in practice — most GNNs use 2–4 layers. Solutions: residual connections, DropEdge (randomly drop edges during training), PairNorm, DiffGroupNorm, or jumping knowledge networks (concatenate representations from all layers).

Graph pooling aggregates node representations into a single graph-level representation for graph classification/regression. Simple approaches: global mean/sum/max pooling over all nodes. Hierarchical pooling: DiffPool (soft clustering via learned assignment matrix), SAGPooling (select top-k nodes by score). Global pooling is simple and often competitive; hierarchical pooling captures multi-scale structure. Graph-level tasks include molecule property prediction (toxicity, solubility), protein function classification, and social network categorization. Graph pooling is the GNN equivalent of global average pooling in CNNs.

# Global mean pooling
import torch_geometric.nn as pyg_nn
pooled = pyg_nn.global_mean_pool(node_embeddings, batch_idx)

Spectral GNNs (ChebNet, GCN) define convolution via the graph Laplacian's eigenvectors — filtering in the spectral (frequency) domain. Mathematically principled but computationally expensive (eigen decomposition) and graph-dependent (can't generalize across different graphs). Spatial GNNs (GraphSAGE, GAT, MPNN) define convolution by aggregating neighbor features directly in the spatial domain — intuitive, scalable, and graph-agnostic. Modern GNNs are almost exclusively spatial. GCN is technically spectral-motivated but simplified to a first-order spatial operation, bridging both worlds.

The graph Laplacian L = D − A, where D is the degree matrix and A is the adjacency matrix. L is positive semi-definite with eigenvalues 0 ≤ λ_1 ≤ ... ≤ λ_N. The number of zero eigenvalues equals the number of connected components. High-frequency eigenvectors correspond to rapidly varying signals on the graph; low-frequency to smooth signals. The normalized Laplacian L̃ = D^{-1/2} L D^{-1/2} is used in GCN. Graph Fourier transform is defined via L's eigenvectors, enabling frequency-domain analysis of graph signals.

import numpy as np
L = np.diag(A.sum(1)) - A  # unnormalized Laplacian
eigvals, eigvecs = np.linalg.eigh(L)

Node classification assigns a label to each node using both node features and graph structure. Example: classify academic papers (nodes) as ML/CV/NLP using paper content features + citation edges. GNN procedure: (1) Propagate and aggregate neighbor features for K layers. (2) Apply linear classifier to final node embeddings. (3) For semi-supervised: only some nodes have labels; structure propagates label signal to unlabeled nodes. Benchmarks: Cora, Citeseer (citation networks). GCN, GAT, GraphSAGE all achieve strong results on these tasks.

Link prediction predicts whether an edge exists between two nodes — fundamental for recommender systems (predict user-item interactions), knowledge graph completion (predict missing facts), and drug-target interaction prediction. GNN approach: (1) Learn node embeddings via message passing. (2) Score each candidate edge (u,v) using embeddings: score(h_u, h_v) = h_u^T h_v or MLP(concat(h_u, h_v)). (3) Train with binary cross-entropy (positive edges vs. negative samples). Negative sampling (sampling non-existent edges as negatives) is crucial for scalable training.

# Link prediction score
pos_score = (h_u * h_v).sum(-1)
neg_score = (h_u * h_neg).sum(-1)
loss = F.binary_cross_entropy_with_logits(
    torch.cat([pos_score, neg_score]),
    torch.cat([torch.ones(len(pos_score)), torch.zeros(len(neg_score))]))

Molecules are naturally represented as graphs: atoms are nodes (with features like atomic number, charge, valence) and bonds are edges (with features like bond type). GNNs propagate atom-level information and pool to molecular-level embeddings for predicting properties: toxicity, solubility, binding affinity. MPNN (Message Passing Neural Network, Gilmer et al. 2017) unified this framework. Benchmarks: MoleculeNet (QM9, HIV, PCBA). GNNs outperform fingerprint-based methods and rival DFT calculations for certain properties at a fraction of the computational cost.

MPNN (Gilmer et al. 2017) is a general framework for chemistry GNNs: Message: m_{vw}^t = M_t(h_v^t, h_w^t, e_{vw}); Aggregation: m_v^t = Σ_{w∈N(v)} m_{vw}^t; Update: h_v^{t+1} = U_t(h_v^t, m_v^t); Readout: ŷ = R({h_v^T | v ∈ G}). M, U, R are learnable functions (MLPs, GRUs). MPNN subsumes GCN, GAT, Interaction Networks, and many others as special cases with specific M, U, R choices. It enables systematic comparison of GNN variants and is the standard formulation in quantum chemistry applications.

Heterogeneous graphs have multiple node types (e.g., users, movies, actors) and edge types (e.g., watched, acted_in, directed). Standard GNNs assume homogeneous graphs with one node/edge type. Extensions: HAN (Heterogeneous Attention Network) uses metapath-based aggregation — aggregate via predefined paths like user→movie→user. R-GCN (Relational GCN) uses separate weight matrices per relation type: h_i' = Σ_r Σ_{j∈N_r(i)} (1/|N_r(i)|) W_r h_j. HGT uses Transformer-style attention with type-specific transformations. Used in knowledge graphs, academic networks, and e-commerce.

The WL graph isomorphism test iteratively assigns color (label) to each node based on its current color + neighbors' colors. Two graphs are WL-non-isomorphic if they get different color histograms. Xu et al. (2019) proved that most GNNs are at most as powerful as WL test — they can't distinguish graphs that WL can't. The most powerful WL-equivalent GNN is Graph Isomorphism Network (GIN), using injective aggregation: h_i' = MLP((1+ε) h_i + Σ_{j∈N(i)} h_j). GINs are strictly more expressive than GCN/GraphSAGE for distinguishing graph structures.

GIN achieves the maximum expressiveness of message-passing GNNs (as powerful as WL test) by using a sum aggregator and MLP: h_i^{(k)} = MLP^{(k)}((1+ε^{(k)}) h_i^{(k-1)} + Σ_{j∈N(i)} h_j^{(k-1)}). Sum aggregation (not mean/max) is key: it can distinguish different multisets of neighbor features. ε is a learnable or fixed scalar. GIN is provably the most expressive among standard message-passing GNNs. For graph-level tasks, it uses sum readout: h_G = Σ_i h_i^{(K)}. GIN achieves state-of-the-art on graph classification benchmarks.

# GIN layer
h_new = mlp((1 + eps) * h + scatter_add(h[neighbors], edge_index[0], dim=0, out=torch.zeros_like(h)))

Knowledge graphs (KG) represent facts as triples (head, relation, tail) — e.g., (Paris, capital_of, France). KG embeddings learn low-dimensional vectors for entities and relations to predict missing triples (link prediction). TransE: h + r ≈ t (entities are points, relations are translations). DistMult: score = h^T diag(r) t. ComplEx: complex-valued embeddings for asymmetric relations. RotatE: r rotates h to t in complex space. GNNs extend these by incorporating multi-hop neighborhood structure. Used in question answering, recommender systems, and drug repurposing.

# TransE scoring
def transe_score(h, r, t):
    return -torch.norm(h + r - t, p=1, dim=-1)

PyTorch Geometric is the leading library for GNNs in PyTorch. Key features: (1) Sparse message passing via gather/scatter operations over edge index — scales to graphs with millions of nodes. (2) Ready-made layers: GCNConv, GATConv, SAGEConv, GINConv, etc. (3) DataLoader for batching graphs (combines multiple graphs into one large disconnected graph). (4) Benchmark datasets: Cora, QM9, ZINC, OGB. It uses edge_index (2×E tensor of source/target pairs) as the primary graph representation, avoiding dense adjacency matrices for efficiency.

from torch_geometric.nn import GCNConv
class GCN(torch.nn.Module):
    def __init__(self):
        super().__init__()
        self.conv1 = GCNConv(d_in, 64)
        self.conv2 = GCNConv(64, d_out)
    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index).relu()
        return self.conv2(x, edge_index)

Aggregation combines neighbor messages: mean (normalize by degree — good for node classification), sum (sensitive to degree — better for graph-level tasks, as proved by GIN), max (captures most prominent feature — good for detecting presence of a feature). Mean aggregation loses information about neighborhood size: a node with 3 neighbors all with feature 1 looks the same as one neighbor with feature 1. Sum preserves this multiset information. Xu et al. (2019) proved sum is strictly more expressive than mean or max for distinguishing graph structures.

Since graphs have variable sizes, they can't be naively batched into fixed tensors. PyG batches graphs by combining them into one large disconnected graph: node features are stacked; edge indices are offset by cumulative node counts; a batch vector tracks which graph each node belongs to. This enables efficient GPU batching. Global pooling uses the batch vector: global_mean_pool(x, batch) computes per-graph means. This batching trick makes GNN training on many small graphs (molecules) as efficient as standard mini-batch training on regular data.

# batch: tensor indicating graph membership
from torch_geometric.nn import global_mean_pool
graph_repr = global_mean_pool(node_embeddings, batch)

Over-squashing occurs when information from exponentially many nodes in a wide K-hop neighborhood must be compressed through a single node embedding — the bottleneck node. This is analogous to vanishing gradients: gradient from a far node goes through many aggregations and shrinks. Over-squashing limits GNNs for tasks requiring long-range communication. Solutions: graph rewiring (add edges to create shortcuts), expander graphs (high connectivity), virtual nodes (a global node connected to all others), or graph Transformer architectures with all-pairs attention.

Graph Transformers combine GNN message passing with Transformer self-attention for full graph context. Approaches: (1) Graphormer (Microsoft) uses degree centrality + spatial + edge encoding as attention bias: A_{ij} += bias(d_{ij}, e_{ij}), giving O(n²) attention over all node pairs. (2) GPS (General, Powerful, Scalable) combines local MPNN + global attention per layer. Graph Transformers overcome over-smoothing (direct all-pairs attention) and over-squashing (no bottleneck), achieving SOTA on molecular benchmarks. They scale to larger graphs with sparse or hierarchical attention.

A virtual node is an extra node added to the graph, connected to every real node. It acts as a global 'supernode' that can aggregate information from the entire graph in one hop and broadcast it back. After 1 layer, every node has received a global summary via the virtual node. This addresses both over-squashing (shortcuts path lengths) and over-smoothing (enables global information without deep stacking). Virtual nodes are simple to implement and significantly improve GNN performance on graph classification tasks, especially for molecules.

Temporal (dynamic) graphs change over time — nodes/edges appear, disappear, or change features. Two settings: (1) Discrete-time: graph snapshots G_1, G_2,...; use GNN on each snapshot + LSTM/GRU across snapshots (EvolveGCN). (2) Continuous-time: events (u,v,t) as a stream; use time-encoding of Δt + memory (TGN — Temporal Graph Network). Challenges: temporal patterns (recency, periodicity), efficient memory for large graphs, and handling irregular event timing. Applications: fraud detection (transaction graphs), traffic prediction, social network evolution.

A bipartite graph has two disjoint node sets U (users) and I (items) with edges only between sets (user-item interactions). GNNs on bipartite graphs propagate information between users and items: user embeddings aggregate interacted items; item embeddings aggregate interacted users. This collaborative filtering naturally handles sparsity and captures higher-order relationships: user→items→similar users→their items. NGCF, LightGCN (simplified GCN without feature transformation or nonlinearity) achieve state-of-the-art on recommendation tasks. Pinterest's PinSage uses GraphSAGE on a billion-scale user-pin bipartite graph.

Traffic networks are spatial graphs: nodes are sensor stations, edges are road connections with distance-based weights. Traffic speed at each node is a time series. GNNs capture spatial dependencies (nearby roads influence each other); temporal models (LSTM, TCN) capture sequential patterns. STGCN (Spatio-Temporal GCN) uses GCN for spatial + 1D conv for temporal. DCRNN uses diffusion convolution (bidirectional random walk on road graph) + seq2seq. Attention-based: ASTGCN, Graphformer. Applications: real-time navigation (Google Maps), transit planning, and congestion prediction.

In full-batch GNN training on large graphs, computing K-layer embeddings for a node requires all nodes in its K-hop neighborhood — which can be exponentially large (degree^K). For a node with degree 10 in a 3-layer GNN: up to 10³=1000 nodes. Mini-batch training naively requires loading all K-hop neighbors into memory per batch. GraphSAGE solves this by sampling a fixed number of neighbors (e.g., 25, 10) per hop. Cluster-GCN partitions the graph into clusters and batches within clusters. These sampling strategies make GNN training scalable to graphs with millions of nodes.

Unlike sequences, graphs have no canonical node ordering — nodes are permutation-invariant. Positional encodings for graphs must capture structural roles without assuming fixed positions. Approaches: (1) Laplacian eigenvectors (LapPE) — smallest k eigenvectors of L encode structural positions (sign ambiguity handled by random flip augmentation). (2) Random walk PE — r_i[k] = probability of returning to i in k steps. (3) Degree features. Good structural PE enables Graph Transformers to distinguish non-isomorphic graphs that WL-equivalent GNNs cannot. LapPE + random walk PE are used in GPS and Graphormer.

3D point clouds (from LiDAR or depth cameras) are unordered sets of 3D points — naturally represented as graphs by connecting nearby points. PointNet (not strictly GNN) processes each point independently then pools. PointNet++ adds hierarchical local grouping. Dynamic Graph CNN (DGCNN) constructs a k-NN graph in feature space and applies edge convolution: h_i' = max_j MLP(h_i || h_j − h_i). Point clouds are used in autonomous driving (object detection), robotics, and 3D modeling. GNNs capture local geometric structure missed by global pooling.

GNNs can make predictions at three granularities: (1) Node-level — predict a property for each node (e.g., node classification in citation networks, protein function for each amino acid). (2) Edge-level — predict property of each edge or whether an edge exists (link prediction, relation classification). (3) Graph-level — predict a property for the entire graph (molecule toxicity, graph classification). Different readout strategies are used: node embeddings directly (node-level), pair scoring (edge-level), global pooling (graph-level). Many real-world problems combine multiple levels.

In GCN, a self-loop (adding I to A: Ã = A + I) ensures each node includes its own features when aggregating. Without self-loops, a node's update would be entirely based on its neighbors, discarding its own current representation. Self-loops also prevent nodes with no neighbors (isolated nodes) from receiving zero aggregation. In the normalized adjacency D̃^{-1/2} Ã D̃^{-1/2}, self-loops increase degree, smoothing the propagation. Conceptually, self-loops make GCN equivalent to a node attending to itself along with its neighbors, similar to residual connections.

A_hat = A + torch.eye(A.size(0))  # add self-loops

DropEdge randomly removes edges during each training step (analogous to Dropout for neurons). Dropping edges reduces the number of neighbors sampled, limiting over-smoothing by reducing information mixing. It also acts as data augmentation — the model sees different graph views each step. DropEdge prevents over-fitting on graph structure and has been shown to allow training deeper GNNs (up to 16+ layers) without severe over-smoothing. The drop probability is a hyperparameter (typically 0.1–0.5). DropEdge is simple to implement and consistently improves GNN regularization.

def dropedge(edge_index, p=0.3):
    mask = torch.rand(edge_index.size(1)) > p
    return edge_index[:, mask]

OGB (Hu et al. 2020) is a standardized benchmark for GNNs with realistic, large-scale graphs and consistent evaluation protocols. It includes: ogbn (node classification — e.g., ogbn-arxiv: 169k nodes, 1.2M edges), ogbl (link prediction — e.g., ogbl-collab), ogbg (graph classification — e.g., ogbg-molhiv: 41k molecules). OGB provides data loaders, evaluators, and a leaderboard. Before OGB, GNN papers used small, possibly saturated benchmarks (Cora: 2.7k nodes). OGB enables fair comparison and revealed that many methods overfit on small benchmarks.

Text can be represented as graphs: syntax trees (dependency parsing — words=nodes, grammatical relations=edges), co-occurrence graphs, AMR (Abstract Meaning Representation). GNNs on dependency trees capture non-adjacent syntactic relationships better than sequence models. TextGCN constructs a word-document graph: both words and documents are nodes; edges are TF-IDF weighted. GNNs propagate label signals from labeled documents to unlabeled ones and words. Applications: relation extraction, sentiment analysis, QA over knowledge graphs. However, for most NLP tasks, Transformers (which implicitly learn graph-like attention) now outperform explicit GNNs.

Node2vec (Grover & Leskovec 2016) generates node embeddings using biased random walks + Word2Vec (Skip-gram). BFS-like walks (p low, q high) capture structural equivalence; DFS-like walks (p high, q low) capture community membership. Node2vec is transductive (embeddings don't generalize to new nodes), feature-agnostic (doesn't use node features), and shallow (not a deep model). GNNs are inductive, use node features, and learn deep, task-specific representations. Node2vec remains useful when node features are absent and induction to new nodes isn't needed.

EvolveGCN (Pareja et al. 2020) handles discrete-time dynamic graphs by evolving GCN weights over time using RNNs instead of evolving node embeddings. At each time step t, GCN weights W^t are updated by a GRU/LSTM that takes the previous weights as hidden state: W^t = GRU(W^{t-1}). Node embeddings are then computed using W^t on graph G_t. This is different from treating each snapshot independently — EvolveGCN captures how the graph's structural patterns change over time. Applicable when node sets change across snapshots (new nodes appear).

LightGCN (He et al. 2020) is a simplified GCN for collaborative filtering that removes: (1) feature transformation (no W matrices); (2) nonlinear activation. Only graph convolution (aggregation) remains: e_u^{(k+1)} = Σ_{i∈N(u)} e_i^{(k)} / √|N(u)||N(i)|. Final embedding = average of all K layers. He et al. argued that transformation and activation are unnecessary in collaborative filtering (IDs only, no features) and hurt performance. LightGCN achieves SOTA on recommendation benchmarks with less computation. It demonstrates that simpler GNNs can outperform complex ones when the inductive bias matches the task.

GNNs are transforming drug discovery: (1) Molecular property prediction — ADMET (absorption, distribution, metabolism, excretion, toxicity) properties. (2) Drug-target interaction — predict binding affinity between drug molecules and protein targets. (3) Drug-drug interactions — predict adverse interactions. (4) De novo molecular design — generate molecules with desired properties using graph generative models. (5) Protein structure (AlphaFold2 uses Evoformer, a GNN-like module). GNNs exploit the natural graph structure of molecules and protein contact maps, outperforming descriptor-based and SMILES-based methods.

GCN assigns fixed, structure-based neighbor weights: α_{ij} = 1/√(deg(i)·deg(j)) — based only on node degrees, not features. GAT assigns learned, feature-based attention weights: α_{ij} = softmax(LeakyReLU(a^T [W h_i || W h_j])) — computed from the actual node feature vectors. GCN treats all neighbors equally (after degree normalization); GAT can up-weight informative neighbors and ignore noisy ones. In practice, GAT outperforms GCN when some neighbors are more relevant than others (heterophilous graphs). GCN is simpler and faster; GAT is more expressive.

Graph generation creates new valid graphs (e.g., drug molecules) from scratch. Approaches: (1) SMILES string generation (RNN/Transformer on linearized graph). (2) One-shot: generate adjacency matrix via VAE (GraphVAE). (3) Sequential/autoregressive: add nodes/edges one at a time (GraphRNN, GCPN). (4) Flow-based (GNF). (5) Diffusion-based (GDSS). For molecules, validity is enforced via chemical valence rules. Applications: de novo drug design, material discovery. GCPN uses RL + GNN to generate molecules by optimizing a reward function (drug-likeness, binding affinity).

Homophilous graphs: connected nodes tend to have the same class (e.g., friendship graphs — friends share interests). GCN assumes homophily — aggregating neighbors improves classification. Heterophilous graphs: connected nodes have different classes (e.g., dating networks, protein interaction networks). GCN aggregation on heterophilous graphs mixes different-class features, harming performance. Solutions: (1) H2GCN — separate ego and neighbor aggregations. (2) GPRGNN — learnable propagation weights (can be negative). (3) MixHop — aggregate k-hop neighbors separately. Many real-world graphs are heterophilous, so this matters significantly in practice.

Node embeddings are dense vectors h_i ∈ R^d capturing structural and feature information. Quality is evaluated via downstream tasks: (1) Node classification accuracy (linear classifier on embeddings). (2) Link prediction AUC (dot product score). (3) Visualization (t-SNE/UMAP) — good embeddings cluster by class. (4) Graph reconstruction — can you recover the graph from embeddings? Embedding quality depends on: GNN depth (receptive field), aggregation type, and whether embeddings capture both local structure (features) and global structure (graph topology). Pre-trained GNN embeddings (like GPT for text) are increasingly used as general-purpose graph features.

Cluster-GCN (Chiang et al. 2019) makes GNN training scalable to billion-scale graphs. It partitions the graph into clusters using METIS or random partition, then batches by cluster. Within a cluster, all neighbor edges are available — no neighbor explosion. The objective approximates full-graph GCN by mixing clusters across batches to reduce bias. Training is much faster (10-100× vs full-batch) and memory-efficient. Limitation: intra-cluster edges are retained but inter-cluster edges are dropped in mini-batches, introducing bias. Stochastic batch interleaving reduces this bias. Used in training GNNs on Reddit (230k nodes), Amazon, and MAG graphs.

GNNs can learn heuristics for NP-hard combinatorial problems on graphs. S2V-DQN (Khalil et al. 2017) uses GraphSAGE + DQN to solve Minimum Vertex Cover, Maximum Cut, and TSP by learning to sequentially add nodes to the solution. The GNN encodes the partial solution state; RL selects the next node. Trained on small graphs, it generalizes to large instances. Similarly, GNNs are used for SAT solving, MILP branching (GNN-based variable selection outperforms human-designed heuristics). This shows GNNs as universal approximators of graph-structured policies.

GNNs are permutation equivariant: if you permute the node indices, the output node embeddings are permuted in the same way (not scrambled). This is because message passing only uses local neighborhood structure, which is invariant to global node ordering. Formally: if π is a permutation, then f(π(G)) = π(f(G)). This property is desirable for graphs (which have no canonical ordering). Graph-level pooling (sum/mean over all nodes) gives permutation-invariant graph representations. This inductive bias makes GNNs naturally suitable for graph data, unlike transforming graphs to fixed-size adjacency matrices.

Node-level tasks predict a property for each individual node using node embeddings — e.g., classifying academic paper topics using citation graph. The final node embedding from K GNN layers is passed to a classifier. Graph-level tasks predict a property for the entire graph (e.g., molecule toxicity) using a readout function — global mean/sum pooling over all node embeddings gives a graph-level vector. Edge-level tasks predict edge properties or existence (link prediction) using pairs of node embeddings. Many real applications combine levels: node + graph predictions simultaneously.

Residual connections add the input to the output of each GNN layer: h_i^{(l+1)} = σ(AGG(...)) + h_i^{(l)}. This creates a skip path ensuring gradients flow directly without vanishing through many aggregation steps. Residuals allow training deeper GNNs (4–8 layers) without over-smoothing dominating: the original features are preserved alongside aggregated information. They are analogous to ResNet skip connections in CNNs. Most modern GNN architectures (GraphSAGE, GIN, GAT) use residuals or initial residuals: h_i^{(l+1)} = h_i^{(l+1)}_{new} + h_i^{(0)} (always adding the original features).

# Residual GNN layer
h_new = gnn_layer(h, edge_index)
h = h_new + h  # skip connection

Neighbor sampling (used in GraphSAGE, PinSage) samples a fixed number of neighbors per node at each GNN layer instead of using all neighbors. For a 2-layer GNN with sampling [25,10]: node i samples 25 1-hop neighbors; each of those samples 10 of their own neighbors. This bounds the computational cost per mini-batch to O(batch_size × 25 × 10) regardless of actual graph degree. PyTorch Geometric's NeighborLoader implements this. The stochastic sampling introduces noise but is unbiased in expectation. Larger sampling sizes give better approximations at higher cost; typical sizes: 10–25 neighbors per hop.

from torch_geometric.loader import NeighborLoader
loader = NeighborLoader(data, num_neighbors=[25,10], batch_size=512, input_nodes=train_mask)

Modern GNNs separate two operations: (1) Aggregation: collect messages from neighbors — AGG({h_j : j ∈ N(i)}) using sum/mean/max. This gathers neighborhood information. (2) Combination: update the node's representation using both its own features and aggregated neighborhood — COMBINE(h_i, AGG) via concatenation + MLP or simple sum. GraphSAGE: COMBINE = MLP(CONCAT(h_i, AGG)). GCN: COMBINE is implicit in the normalized adjacency multiplication. GIN: COMBINE = MLP((1+ε)h_i + AGG). Separating aggregation and combination gives more design flexibility and better expressiveness.