graph neural network
**Graph Neural Networks (GNNs)** are **deep learning models that operate directly on graph-structured data by iteratively aggregating and transforming information from neighboring nodes** — enabling learning on molecular structures, social networks, knowledge graphs, and any relational data where the structure of connections carries critical information that standard neural networks cannot capture.
**Why Graphs Need Special Networks**
- Images: Fixed grid structure → CNNs exploit spatial locality.
- Text: Sequential structure → Transformers exploit positional relationships.
- Graphs: Irregular topology, variable node degrees, no fixed ordering → need permutation-invariant operations.
**Message Passing Framework**
Most GNNs follow this pattern per layer:
1. **Message**: Each node sends a message to its neighbors: $m_{ij} = MSG(h_i, h_j, e_{ij})$.
2. **Aggregate**: Each node collects messages from all neighbors: $M_i = AGG(\{m_{ij} : j \in N(i)\})$.
3. **Update**: Each node updates its representation: $h_i' = UPDATE(h_i, M_i)$.
- After K layers: Each node's representation encodes information from its K-hop neighborhood.
**GNN Architectures**
| Model | Aggregation | Key Innovation |
|-------|-----------|----------------|
| GCN (Kipf & Welling 2017) | Mean of neighbors | Spectral-inspired, simple and effective |
| GraphSAGE | Mean/Max/LSTM of sampled neighbors | Inductive learning, sampling for scale |
| GAT (Graph Attention) | Attention-weighted sum | Learnable neighbor importance |
| GIN (Graph Isomorphism Network) | Sum + MLP | Maximally expressive (WL-test equivalent) |
| MPNN | General message passing | Unified framework |
**GCN Layer**
$H^{(l+1)} = \sigma(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(l)} W^{(l)})$
- $\tilde{A} = A + I$: Adjacency matrix with self-loops.
- $\tilde{D}$: Degree matrix of $\tilde{A}$.
- W: Learnable weight matrix.
- Effectively: Weighted average of neighbor features → linear transform → nonlinearity.
**Task Types on Graphs**
| Task | Input | Output | Example |
|------|-------|--------|---------|
| Node classification | Graph | Label per node | Protein function, user type |
| Edge prediction | Graph | Edge exists/property | Drug interaction, recommendation |
| Graph classification | Graph | Label per graph | Molecule toxicity, circuit function |
| Graph generation | Noise | New graph | Drug design, material discovery |
**Applications**
- **Drug Discovery**: Molecules as graphs (atoms=nodes, bonds=edges) → predict properties.
- **Recommendation Systems**: User-item bipartite graph → predict preferences.
- **Chip Design (EDA)**: Circuit netlists as graphs → timing/congestion prediction.
- **Fraud Detection**: Transaction graphs → identify anomalous subgraphs.
Graph neural networks are **the standard approach for learning on relational and structured data** — their ability to capture complex topology-dependent patterns has made them indispensable in computational chemistry, social network analysis, and any domain where the relationships between entities are as important as the entities themselves.