graph neural network

**Graph Neural Networks (GNNs)** are the **deep learning architectures designed to operate directly on graph-structured data by iteratively aggregating feature information from each node's local neighborhood, producing learned representations that capture both the topology and the attributes of nodes, edges, and entire graphs**. **Why Graphs Need Special Architectures** Conventional CNNs assume grid structure (images) and RNNs assume sequence structure (text). Molecular structures, social networks, EDA netlists, and recommendation graphs have arbitrary connectivity that cannot be flattened into a grid without destroying critical topological information. **The Message Passing Framework** Nearly all GNNs follow the same three-step loop per layer: 1. **Message**: Each node sends its current feature vector to all neighbors. 2. **Aggregate**: Each node collects incoming messages and reduces them (mean, sum, max, or attention-weighted combination). 3. **Update**: Each node passes the aggregated neighborhood information through a learned MLP to produce its new feature vector. After $L$ layers, each node's representation encodes structural and attribute information from its $L$-hop neighborhood. **Key Variants** - **GCN (Graph Convolutional Network)**: Normalized mean aggregation — simple, fast, and effective for semi-supervised node classification on citation and social graphs. - **GAT (Graph Attention Network)**: Learns attention coefficients over neighbors, allowing the model to weight important neighbors more heavily than noisy or irrelevant ones. - **GIN (Graph Isomorphism Network)**: Sum aggregation with injective update functions, theoretically as powerful as the Weisfeiler-Lehman graph isomorphism test. - **Graph Transformers**: Replace local message passing with global self-attention over all nodes, augmented with positional encodings (Laplacian eigenvectors, random walk statistics) to inject the graph topology that attention alone cannot capture. **Fundamental Limitations** - **Over-Smoothing**: After too many layers, all node representations converge to the same vector because repeated neighborhood averaging blurs all local structure. Residual connections, DropEdge, and PairNorm mitigate but do not fully solve this. - **Over-Squashing**: Information from distant nodes must pass through narrow bottleneck connections, losing fidelity. Graph rewiring and virtual node techniques help propagate long-range interactions. Graph Neural Networks are **the foundational tool for machine learning on relational and topological data** — encoding molecular properties, chip netlist quality, social influence, and recommendation relevance into vectors that standard downstream predictors can consume.