Graph Neural Network Gnn
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.