Graph Neural Network

Graph Neural Network (GNN) is a class of neural networks designed to operate directly on graph-structured data — learning representations for nodes, edges, and entire graphs by aggregating information from neighborhoods.

What Is a GNN?

• Input: Graph G = (V, E) where V = nodes, E = edges, each with feature vectors.
• Output: Node embeddings, edge embeddings, or graph-level predictions.
• Core Idea: Iteratively update each node's representation by aggregating from its neighbors.

Message Passing Framework

At each layer $l$:
1. Message: Compute messages from neighbor $j$ to node $i$: $m_{ij} = M(h_i^l, h_j^l, e_{ij})$
2. Aggregate: Pool all incoming messages: $m_i = AGG(\{m_{ij} : j \in N(i)\})$
3. Update: $h_i^{l+1} = U(h_i^l, m_i)$

GNN Variants

• GCN (Graph Convolutional Network): Spectral convolution on graphs (Kipf & Welling, 2017).
• GraphSAGE: Inductive learning — generalizes to unseen nodes by sampling neighborhoods.
• GAT (Graph Attention Network): Learns attention weights for each neighbor.
• GIN (Graph Isomorphism Network): Maximally expressive message passing.

Applications

• Molecule design: Drug discovery, property prediction (QM9 benchmark).
• Social networks: Fraud detection, recommendation systems.
• Chip design: Routing optimization, netlist analysis.
• Knowledge graphs: Entity/relation reasoning.

Challenges

• Over-smoothing: Deep GNNs make all node representations similar.
• Scalability: Large graphs require neighbor sampling (GraphSAGE, ClusterGCN).
• Expressive power: Limited by the Weisfeiler-Leman graph isomorphism test.

GNNs are the standard approach for machine learning on relational data — essential for chemistry, biology, social science, and any domain where relationships matter as much as attributes.