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.