My GCN kept underfitting on a citation graph until I realized

I was building a node classification pipeline on Cora with PyTorch Geometric last month, and my model was barely beating random chance. Accuracy hovered around 0.68 (random baseline is ~0.55 for 7-class), and I assumed it was a hyperparameter problem. Turned out the issue was in the message passing itself.

The core problem: over-smoothing through normalization

My initial setup used a standard GCNConv layer with add_self_loops=True. Here's the simplified forward pass:

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

class GCN(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels):
        super().__init__()
        self.conv1 = GCNConv(in_channels, hidden_channels)
        self.conv2 = GCNConv(hidden_channels, out_channels)

    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, training=self.training)
        x = self.conv2(x, edge_index)
        return x

The math behind GCN aggregation is:

$$H^{(l+1)} = \sigma\left(\hat{A} H^{(l)} W^{(l)}\right)$$

where $\hat{A} = D^{-1/2} A D^{-1/2}$ is the symmetrically normalized adjacency matrix with self-loops. The normalization factor $\hat{A}$ divides by $\sqrt{d_i d_j}$ for each edge — this means high-degree nodes dilute the features of their low-degree neighbors. After two layers, node features become nearly indistinguishable (the over-smoothing problem).

Debugging steps

1. Checked degree distribution — Cora nodes have degrees ranging from 2 to 994. The normalization was crushing low-degree signals.
2. Visualized embeddings — ran t-SNE on the output of layer 1, and sure enough, classes were blending together.
3. Switched to GAT — replaced GCNConv with GATConv to see if attention-based weighting helped.

from torch_geometric.nn import GATConv

class GAT(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels):
        super().__init__()
        self.conv1 = GATConv(in_channels, hidden_channels, heads=8, concat=True)
        self.conv2 = GATConv(hidden_channels * 8, out_channels, heads=1, concat=False)

    def forward(self, x, edge_index):
        x = F.elu(self.conv1(x, edge_index))
        x = F.dropout(x, training=self.training)
        x = self.conv2(x, edge_index)
        return x

With GAT, the attention mechanism learns per-edge weights, so low-degree nodes don't get drowned out. Accuracy jumped to 0.83 on the same split.

The broader lesson: MPNN isn't one trick

This whole debugging session made me reconsider the message-passing framework (MPNN) more carefully. The general form is:

$$m_e^{(t)} = \text{MESSAGE}(h_u^{(t)}, h_v^{(t)}, e_{uv})$$
$$h_v^{(t+1)} = \text{UPDATE}(h_v^{(t)}, \text{AGGREGATE}(\{m_e^{(t)}\}))$$

GCN, GAT, and GraphSAGE are all instantiations of this with different message and aggregation choices. The normalization step in GCN is what caused my issue — it's an implicit design decision that works well on some graphs but not others.

For practitioners, the takeaway: if your GNN underfits despite tuning learning rates and dropout, check whether the propagation rule is destroying information. Sometimes switching to attention (GAT) or mean-pooling (GraphSAGE) is the real fix, not more epochs.

I'm now experimenting with jumping knowledge networks (JK-Net) to combine representations from multiple layers, which should further combat over-smoothing. Has anyone else hit this wall with normalized MPNNs, and what was your workaround?