Graph Neural Networks: Message Passing and Theory

Module: Machine Learning | Difficulty: Advanced

Message Passing Neural Network

GCN (Kipf & Welling, 2017)

Over-Squashing

Long-range interactions are exponentially attenuated.

WL Test Connection

GNNs cannot distinguish graphs that the Weisfeiler-Leman test cannot.

import torch
import torch.nn as nn
from torch_geometric.nn import GCNConv

class GCN(nn.Module):
    def __init__(self, in_dim, hidden, out_dim):
        super().__init__()
        self.conv1 = GCNConv(in_dim, hidden)
        self.conv2 = GCNConv(hidden, out_dim)
    def forward(self, x, edge_index):
        x = torch.relu(self.conv1(x, edge_index))
        x = self.conv2(x, edge_index)
        return x

Research Insight: Over-squashing is a fundamental limitation of MPNNs. Solutions include: graph transformers (full attention), graph rewiring (adding long-range edges), and k-hop message passing.