Graph Neural Networks (GNNs) are neural architectures that operate on graph-structured data by passing messages between connected nodes — learning node, edge, and graph-level representations through iterative neighborhood aggregation, enabling machine learning on non-Euclidean data structures such as social networks, molecular graphs, and knowledge graphs.

Message Passing Framework:

• Neighborhood Aggregation: each node collects feature vectors from its neighbors, aggregates them (sum, mean, max), and updates its own representation; after K layers, each node's representation captures information from its K-hop neighborhood
• Message Function: computes messages from neighbor features; simplest form: m_ij = W·h_j (linear transform of neighbor j's features); more expressive variants include edge features: m_ij = W·[h_j || e_ij] or attention-weighted messages
• Update Function: combines aggregated messages with the node's current features to produce the updated representation; GRU-style or MLP-based updates provide nonlinear combination: h_i' = σ(W_self·h_i + W_agg·AGG({m_ij : j ∈ N(i)}))
• Readout: for graph-level prediction, aggregate all node representations into a single graph vector using sum, mean, or attention pooling; hierarchical pooling (DiffPool, Top-K pooling) progressively coarsens the graph for multi-scale representation

Architecture Variants:

• GCN (Graph Convolutional Network): spectral-inspired convolution using normalized adjacency matrix; h' = σ(D^(-½)·Â·D^(-½)·H·W) where  = A+I (self-loops), D is degree matrix; simple, efficient, widely used for semi-supervised node classification
• GAT (Graph Attention Network): learns attention coefficients between nodes; α_ij = softmax(LeakyReLU(a^T·[W·h_i || W·h_j])); attention enables different importance weights for different neighbors — crucial for heterogeneous neighborhoods where not all neighbors are equally relevant
• GraphSAGE: samples fixed-size neighborhoods and aggregates using learnable functions (mean, LSTM, pooling); enables inductive learning on unseen nodes by learning aggregation functions rather than node-specific embeddings
• GIN (Graph Isomorphism Network): maximally powerful GNN under the message passing framework; provably as expressive as the Weisfeiler-Lehman graph isomorphism test; uses sum aggregation with injective update: h' = MLP((1+ε)·h_i + Σ h_j)

Tasks and Applications:

• Node Classification: predict labels for individual nodes (user categorization in social networks, paper topic classification in citation graphs); semi-supervised setting uses few labeled nodes and many unlabeled
• Link Prediction: predict missing or future edges (recommendation systems, drug-target interaction, knowledge graph completion); encodes node pairs and scores edge likelihood
• Graph Classification: predict properties of entire graphs (molecular property prediction, protein function classification); requires effective graph-level pooling/readout to aggregate node features
• Molecular Graphs: atoms as nodes, bonds as edges; GNNs predict molecular properties (toxicity, solubility, binding affinity) achieving state-of-the-art on MoleculeNet benchmarks; SchNet, DimeNet add 3D spatial information

Challenges and Limitations:

• Over-Smoothing: deep GNNs (>5-10 layers) cause node representations to converge to similar vectors, losing discriminative power; mitigation: residual connections, jumping knowledge, dropping edges during training
• Over-Squashing: information from distant nodes is exponentially compressed through narrow graph bottlenecks; manifests as poor performance on tasks requiring long-range dependencies; graph rewiring and virtual nodes address this
• Scalability: full-batch GCN on large graphs (millions of nodes) requires materializing the dense multiplication; mini-batch training with neighborhood sampling (GraphSAGE) or cluster-based approaches (ClusterGCN) enable billion-edge graphs
• Expressivity: standard MPNNs cannot distinguish certain non-isomorphic graphs (limited by 1-WL test); higher-order GNNs (k-WL), subgraph GNNs, and positional encodings increase expressivity at computational cost

Graph neural networks are the essential deep learning framework for structured and relational data — enabling AI applications on the vast landscape of real-world data that naturally forms graphs, from molecular drug discovery to social network analysis to recommendation engines and beyond.