Deep GNNs & Limitations

1. Oversmoothing

Stack many GNN layers and all node embeddings become nearly identical - the model cannot distinguish nodes.

Math intuition: Repeated normalized adjacency multiplication is like repeated low-pass filtering. The Dirichlet energy $\mathbf{h}^T\mathbf{L}\mathbf{h}$ shrinks toward zero - embeddings become smooth (constant) across the graph.

When it hurts: node classification needing local detail, heterophilous graphs. When it helps: semi-supervised learning with very few labels (smoothness prior).

2. Over-Squashing

Paper: Topping et al. - Understanding Over-Squashing (2022)

Information from distant nodes must pass through narrow bottlenecks (low-degree edges). Messages get compressed into fixed-size vectors - exponential information loss.

Fixes: graph rewiring (add edges), virtual nodes, graph transformers (global attention), subgraph GNNs.

3. Expressiveness and 1-WL

Standard MPNNs are at most as powerful as the 1-Weisfeiler-Lehman graph isomorphism test. They cannot distinguish some non-isomorphic graphs.

GIN achieves this upper bound. To go beyond: subgraph GNNs (NGNN, ESAN), higher-order WL, simplicial complexes.

4. Fixes: JK, Residual, Normalization

• Jumping Knowledge (JK): concatenate $\mathbf{h}_i^{(1)}, \ldots, \mathbf{h}_i^{(L)}$ - keeps both local and global info
• Residual connections: $\mathbf{h}^{(l+1)} = \mathbf{h}^{(l)} + \text{MPNN}(\mathbf{h}^{(l)})$ - like ResNet for graphs
• PairNorm / GraphNorm / BatchNorm: normalize embeddings per layer to slow oversmoothing
• DropEdge: randomly drop edges during training - regularization + depth help

from torch_geometric.nn import JumpingKnowledge

class DeepGNN(torch.nn.Module):
    def __init__(self, num_layers, hidden, out_dim):
        super().__init__()
        self.convs = torch.nn.ModuleList([GCNConv(hidden, hidden) for _ in range(num_layers)])
        self.jk = JumpingKnowledge(mode='cat')
        self.lin = torch.nn.Linear(num_layers * hidden, out_dim)

    def forward(self, x, edge_index):
        hs = []
        for conv in self.convs:
            x = conv(x, edge_index).relu()
            hs.append(x)
        x = self.jk(hs)
        return self.lin(x)

5. Heterophily Architectures

When neighbors have different labels, blind aggregation fails. Solutions:

• H2GCN: combine ego features + higher-order neighbors separately
• GPR-GNN: learnable weights for each hop (can be negative - high-pass filter)
• FAGCN: signed attention - attract similar, repel dissimilar

Refer: Zhu et al. - Beyond Homophily

6. How Many Layers?