Graph Neural Networks

Why Standard Neural Networks Fail on Graphs

Standard deep learning assumes grid structured inputs:

• Images have 2D pixel grids.
• Text has 1D sequential token chains.

Many real world domains exist as Non Euclidean Graphs $G = (V, E)$ with variable node connections:

• Social Networks: Users (nodes) connected by friendships (edges).
• Molecules (AlphaFold): Atoms (nodes) connected by chemical bonds (edges).
• Recommendation Systems: Users and products connected by purchase histories.

Flattening a graph into a matrix destroys connectivity topology and depends arbitrarily on node ordering.

Graph Neural Networks (GNNs) process graph topologies directly regardless of node ordering (Permutation Equivariance).

  Graph Topology (Nodes V, Edges E) ──► [ MESSAGE PASSING GNN ] ──► Node Embeddings h_v
                                         (Aggregate Neighbor Features!)

The Message Passing Framework (Gilmer et al., 2017)

Every GNN layer executes a 3-step Message Passing operation:

┌──────────────────────────┬──────────────────────────┬──────────────────────────┐
│ 1. MESSAGE STEP          │ 2. AGGREGATE STEP        │ 3. UPDATE STEP           │
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ Each node v computes a   │ Aggregates incoming      │ Combines current node    │
│ message m_uv from every  │ neighbor messages using  │ state h_v with aggregated│
│ connected neighbor u.    │ PERMUTATION INVARIANT    │ message vector using a   │
│ m_uv = Message(h_u, h_v) │ sum, mean, or max pooling│ neural network layer.    │
└──────────────────────────┴──────────────────────────┴──────────────────────────┘

                       MESSAGE PASSING AT NODE V
                            (Node U1)
                               │  m_{u1, v}
                               ▼
     (Node U2) ──► m_{u2, v} ──► [ NODE V ] ◄── m_{u3, v} ── (Node U3)
                               ▲
                      Aggregate (Sum / Mean / Max) ──► Update Node State h_v^(l+1)

1-hop message passing gathers immediate neighbors. Stacking $L$ GNN layers allows node $v$ to gather information from neighbors $L$ hops away (Receptive Field).

Key GNN Architectures

1. Graph Convolutional Networks (GCN - Kipf & Welling, 2017)

Computes normalized mean aggregation over 1-hop neighbors:

$$h_v^{(l+1)} = \sigma \left( \sum_{u \in \mathcal{N}(v) \cup {v}} \frac{1}{\sqrt{\tilde{d}_v \tilde{d}_u}} W^{(l)} h_u^{(l)} \right)$$

Uses symmetric degree normalization $\frac{1}{\sqrt{\tilde{d}_v \tilde{d}_u}}$ to scale high degree hub nodes.

2. Graph Attention Networks (GAT - Veličković et al., 2018)

Replaces fixed degree normalization with Self Attention Weights ($\alpha_{uv}$):

$$h_v^{(l+1)} = \sigma \left( \sum_{u \in \mathcal{N}(v)} \alpha_{uv} W^{(l)} h_u^{(l)} \right)$$

Nodes assign higher attention weights $\alpha_{uv}$ to relevant neighbors while ignoring noisy connections.

3. GraphSAGE (Hamilton et al., 2017)

Designed for large scale dynamic graphs (Pinterest, Twitter). Instead of using full graph adjacency matrices, GraphSAGE samples a fixed size neighborhood (e.g. 10 random neighbors) for each node, supporting mini batch training.

Common GNN Failure Modes

1. Over Smoothing: Stacking more than 4 to 6 GNN layers repeatedly averages features across the graph, causing all node embeddings to converge to identical vectors. (Fixed by DropEdge or Residual Connections).
2. Over Squashing: Compressing information from exponentially growing multi hop neighborhood subgraphs into a single fixed size node vector.

Say this out loud

Graph Neural Networks process non Euclidean graph topologies using Message Passing. Each node gathers feature messages from connected neighbors, aggregates them using permutation invariant functions like sum or mean, and updates its node embedding. GCN uses degree normalized convolution, GAT adds self attention neighbor weights, and GraphSAGE samples local neighborhoods for mini batch scaling.

Followups to expect

1. What tasks can GNNs perform? Node Classification (predicting user properties), Edge Prediction (link prediction for friend recommendations), and Graph Classification (predicting toxicity of a whole molecule).
2. What is the Weisfeiler-Lehman (1-WL) Test? A graph isomorphism algorithm representing the theoretical upper bound on expressive power for standard Message Passing GNNs. Standard GNNs cannot distinguish certain non isomorphic graph pairs.