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**.