Graph Neural Networks (GNNs)

Why Graphs?

Many real-world problems are inherently relational: entities connected by relationships.

Domain	Nodes	Edges
Social network	Users	Friendships
Molecule	Atoms	Chemical bonds
Knowledge graph	Entities	Relations
Transaction network	Accounts	Payments
Citation network	Papers	Citations
Recommendation	Users & items	Interactions

Standard deep learning fails on graphs because:

• Graphs have no fixed-size grid structure (unlike images)
• Nodes have variable neighborhoods — no notion of "left neighbor"
• Permutation invariance required — node ordering is arbitrary
• Structural information (connectivity) carries signal that feature vectors alone miss

Graph Neural Networks solve this by learning representations that capture both node features and graph topology.

The Message Passing Framework

All major GNN variants follow the message-passing neural network (MPNN) framework (Gilmer et al., 2017):

For each node $v$ at layer $k$:

$\mathbf{m}_v^{(k)} = \text{AGGREGATE}^{(k)}\left(\{\mathbf{h}_u^{(k-1)} : u \in \mathcal{N}(v)\}\right)$

$\mathbf{h}_v^{(k)} = \text{UPDATE}^{(k)}\left(\mathbf{h}_v^{(k-1)},\ \mathbf{m}_v^{(k)}\right)$

Where:

• $\mathbf{h}_v^{(0)} = \mathbf{x}_v$ (initial node features)
• $\mathcal{N}(v)$ is the neighborhood of node $v$
• $k$ indexes the layer (each layer = one hop)

After $K$ layers, $\mathbf{h}_v^{(K)}$ summarizes the $K$-hop neighborhood around $v$.

Readout (for graph-level tasks): $\mathbf{h}_G = \text{READOUT}\left(\{\mathbf{h}_v^{(K)} : v \in G\}\right)$

Different GNN variants differ in how they define AGGREGATE and UPDATE.

GCN — Graph Convolutional Network

Kipf & Welling (2017) — the seminal spectral-based GNN.

$\mathbf{H}^{(k)} = \sigma\!\left(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\mathbf{H}^{(k-1)}\mathbf{W}^{(k)}\right)$

Where:

• $\tilde{A} = A + I$ (adjacency matrix with self-loops)
• $\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$ (degree matrix)
• $\mathbf{W}^{(k)}$ — learnable weight matrix

In plain English: take each node's features + its neighbors' features, normalize by degree, linearly transform, then apply activation.

Properties & Limitations

Property	Detail
Aggregation	Mean of normalized neighbors
Complexity	$O(
Strength	Simple, effective for homophilic graphs
Weakness	Fixed equal weights to all neighbors (no attention)
Weakness	Transductive — cannot generalize to unseen nodes

GraphSAGE — Inductive Representation Learning

Hamilton et al. (2017) — enables inductive learning (generalizes to new nodes).

$\mathbf{h}_{\mathcal{N}(v)}^{(k)} = \text{AGGREGATE}_k\left(\{\mathbf{h}_u^{(k-1)} : u \in \mathcal{N}(v)\}\right)$

$\mathbf{h}_v^{(k)} = \sigma\!\left(\mathbf{W}^{(k)} \cdot \text{CONCAT}\left(\mathbf{h}_v^{(k-1)},\ \mathbf{h}_{\mathcal{N}(v)}^{(k)}\right)\right)$

AGGREGATE options: mean, max-pooling, or LSTM over sampled neighbors.

Key Advantages Over GCN

• Inductive: train on one graph, predict on new graphs / new nodes (crucial for production)
• Mini-batch training: samples a fixed-size neighborhood → scalable to millions of nodes
• Flexible aggregation: max-pooling captures the most prominent neighbor features

When to Use GraphSAGE

Large graphs where nodes arrive over time (e.g., new users in a social network, new products in a catalog). Used in Pinterest's recommendation system (PinSage) — trained on 3 billion nodes.

GAT — Graph Attention Network

Veličković et al. (2018) — learns different attention weights for different neighbors.

$\mathbf{h}_v^{(k)} = \sigma\!\left(\sum_{u \in \mathcal{N}(v) \cup \{v\}} \alpha_{vu}^{(k)} \mathbf{W}^{(k)} \mathbf{h}_u^{(k-1)}\right)$

Attention coefficient:

$\alpha_{vu} = \frac{\exp\!\left(\text{LeakyReLU}(\mathbf{a}^T [\mathbf{W}\mathbf{h}_v \| \mathbf{W}\mathbf{h}_u])\right)}{\sum_{w \in \mathcal{N}(v)} \exp\!\left(\text{LeakyReLU}(\mathbf{a}^T [\mathbf{W}\mathbf{h}_v \| \mathbf{W}\mathbf{h}_w])\right)}$

Multi-head attention applies $K$ independent attention heads and concatenates (or averages) their outputs.

Comparison of GNN Variants

Model	Aggregation	Inductive	Attention	Best For
GCN	Normalized mean	No	No	Small homophilic graphs
GraphSAGE	Mean / max / LSTM	Yes	No	Large-scale, dynamic graphs
GAT	Weighted by attention	Yes	Yes	Heterophilic graphs, interpretability
GIN	Sum (most expressive)	Yes	No	Graph classification, isomorphism

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

# --- Load Cora citation dataset ---
# 2708 nodes (papers), 5429 edges (citations), 7 classes, 1433 features
dataset = Planetoid(root='/tmp/Cora', name='Cora')
data = dataset[0]

print(f"Nodes: {data.num_nodes}, Edges: {data.num_edges}")
print(f"Node features: {data.num_node_features}, Classes: {dataset.num_classes}")
print(f"Train/Val/Test: {data.train_mask.sum()}/{data.val_mask.sum()}/{data.test_mask.sum()}")


# --- GCN Model ---
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)


# --- GAT Model ---
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)
        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)


def train_eval(model_cls, epochs=200, **kwargs):
    model = model_cls(dataset.num_node_features, 64, dataset.num_classes, **kwargs)
    optimizer = torch.optim.Adam(model.parameters(), lr=0.005, weight_decay=5e-4)

    for epoch in range(epochs):
        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()

    model.eval()
    with torch.no_grad():
        pred = model(data.x, data.edge_index).argmax(dim=1)
        acc = (pred[data.test_mask] == data.y[data.test_mask]).float().mean()
    return acc.item()

gcn_acc = train_eval(GCN)
gat_acc = train_eval(GAT)

print(f"\nGCN Test Accuracy:  {gcn_acc:.4f}")
print(f"GAT Test Accuracy:  {gat_acc:.4f}")
# Expected: GCN ~0.81, GAT ~0.83 on Cora

Real-World Applications

Fraud Detection

• Nodes: bank accounts, merchants, devices
• Edges: transactions, shared attributes
• Task: node classification — is this account fraudulent?
• GNNs catch fraud rings (coordinated groups) invisible to per-account models
• PayPal, Alibaba, and Amazon use GNN-based fraud detection in production

Drug Discovery & Molecular Property Prediction

• Nodes: atoms, Edges: bonds
• Task: graph classification — will this molecule inhibit a target protein?
• GNNs (e.g., MPNN, D-MPNN) outperform fingerprint-based methods
• Used in COVID-19 drug screening (MIT, Pfizer, DeepMind's AlphaFold context)

Recommendation Systems

• Nodes: users + items (bipartite graph)
• Edges: interactions (clicks, purchases, ratings)
• Task: link prediction — will user U interact with item I?
• LightGCN (2020): simplified GCN without feature transformation — state of the art on RecSys benchmarks
• PinSage (Pinterest): GraphSAGE at 3B nodes, serving billions of recommendations daily

Summary

• Graphs represent relational data — social networks, molecules, transactions, knowledge graphs
• All GNNs follow message passing: iteratively aggregate neighbor features → capture K-hop context
• GCN: simple, effective, normalized mean aggregation — best for small homophilic graphs
• GraphSAGE: inductive, scalable with neighbor sampling — best for large dynamic graphs
• GAT: attention-weighted aggregation — best when neighbor importance varies
• Real applications: fraud detection, drug discovery, recommendation systems, knowledge graph completion

Next: Bayesian Machine Learning — probabilistic reasoning and uncertainty quantification.