Graph Neural Networks: Why Message Passing Works - and Where It Breaks

Most machine learning assumes a table. Rows are independent, columns are fixed, and shuffling the rows changes nothing except the order of the output. Graphs break all three assumptions at once. A molecule is not a row. A social network is not a fixed-size vector. A citation graph has no natural ordering of neighbours, and the number of neighbours changes from node to node.

Graph neural networks (GNNs) are the attempt to build a neural model that respects that structure. Their core idea is disarmingly simple: a node learns about itself by listening to its neighbours, then those neighbours have already listened to theirs. Repeat that a few times, and every node carries a summary of its local neighbourhood. Almost everything interesting about GNNs, including their failures, follows from that one mechanism.

The intuition: representation by neighbourhood

Think of a single paper in a citation network. Its own features might be a bag of words from its abstract. That is useful, but it says nothing about the field the paper belongs to, the methods it builds on, or the community that cites it. Its neighbours say a great deal. If most of its neighbours are about protein folding, the paper is probably about protein folding too, even if its abstract is ambiguous.

Message passing turns that intuition into computation. At each layer, every node collects messages from its neighbours, combines them into one aggregated message, and updates its own representation using that aggregate and its previous representation. After one layer, a node knows about its immediate neighbours. After two layers, it knows about neighbours of neighbours. After k layers, it knows about its k-hop neighbourhood.

Crucially, the order in which neighbours send their messages must not matter. A graph has no canonical ordering of neighbours, so aggregation must be permutation invariant: sum, mean, and max all qualify, while concatenating neighbours in a fixed order does not. This is not a cosmetic constraint. It is what makes the model a function of the graph rather than a function of an arbitrary labelling of the graph.

The formalism: one layer, written out

Let a graph have node features
$x_v$
for each node
$v$ ,
and let
$N(v)$
be the set of neighbours of
$v$ .
A general message passing layer updates the representation
$h_v$
as follows. First, each neighbour sends a message:

$$m_{uv} = \phi(h_u, h_v, e_{uv})$$

where
$e_{uv}$
is an optional edge feature and
$\phi$
is a learnable message function. Then the messages are aggregated:

$$m_v = \bigoplus_{u \in N(v)} m_{uv}$$

where
$\bigoplus$
is a permutation invariant aggregator such as sum or mean. Finally, the node updates its state:

$$h_v' = \psi(h_v, m_v)$$

where
$\psi$
is a learnable update function, usually a small neural network.

The best known special case is the graph convolutional network (GCN). In matrix form, one GCN layer is:

$$H' = \sigma(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H W)$$

Here
$H$
holds the node representations as rows,
$\tilde{A} = A + I$
is the adjacency matrix with self-loops added so a node also listens to itself,
$\tilde{D}$
is the corresponding degree matrix,
$W$
is a learnable weight matrix, and
$\sigma$
is a nonlinearity. The symmetric normalisation
$\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$
is doing real work: without it, high-degree nodes would receive messages with much larger magnitudes than low-degree nodes, and training would be dominated by hubs.

That single equation explains both the power and the limitation of the GCN. It is a form of Laplacian smoothing: each layer replaces a node representation by a weighted average of its neighbourhood. Smoothing is exactly what you want when neighbours tend to share labels, and exactly what you do not want when they do not.

A practical example

Consider node classification on a citation graph: predict the topic of each paper. A minimal GCN in PyTorch Geometric style looks like this:

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

class GCN(torch.nn.Module):
    def __init__(self, in_dim, hidden_dim, out_dim):
        super().__init__()
        self.conv1 = GCNConv(in_dim, hidden_dim)
        self.conv2 = GCNConv(hidden_dim, out_dim)

    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, p=0.5, training=self.training)
        x = self.conv2(x, edge_index)
        return F.log_softmax(x, dim=1)

Two layers are not a timid choice here. They are often the best choice, for reasons given below. Train this on a labelled subset of nodes, evaluate on held-out nodes, and on a homophilic citation graph it will usually beat a model that uses node features alone by a clear margin. The gain comes from structure, not from extra parameters: the graph itself is doing part of the work.

A common variant worth knowing is GraphSAGE, which samples a fixed number of neighbours instead of using all of them. That matters in practice because real graphs have hubs with thousands of neighbours, and a full neighbourhood aggregation at every layer quickly becomes a bottleneck. Sampling trades a little information for a model that can actually be trained on large graphs. Graph attention networks (GATs) take a different route: they learn a weight for each neighbour, so the model can decide that some neighbours matter more than others. Attention helps, but it does not remove the structural limits discussed next.

Where message passing breaks

1. Oversmoothing: depth destroys information

Each message passing layer averages a node with its neighbours. Repeat that many times and every node starts to look like every other node. Formally, repeated Laplacian smoothing drives representations toward a stationary distribution that depends mainly on node degree, not on the original features. In practice, GCN accuracy often peaks at two or three layers and then falls as depth increases.

This is counterintuitive if you come from images or text, where deeper is usually better. On graphs, depth has a different meaning: depth is receptive field size, and a large receptive field on a densely connected graph is nearly the whole graph. If every node can see the whole graph, and every node averages what it sees, then every node ends up with a similar summary.

Practical responses include residual connections, jumping knowledge networks that combine representations from all layers instead of only the last one, and normalisation schemes designed for graphs. None of these fully removes the problem. The honest rule is to treat depth as a hyperparameter to tune, not as a virtue, and to be suspicious of any graph model with many layers and no explicit mechanism against smoothing.

2. Oversquashing: long-range information is squeezed through a bottleneck

Oversmoothing is about too much mixing. Oversquashing is about too little bandwidth. Suppose a node needs information from a node ten hops away. That information must travel along paths, and at each step it is compressed into a fixed-size vector together with messages from every other neighbour. By the time it arrives, it has been diluted, overwritten, or both.

The effect is worst on graphs with bottlenecks: two dense communities connected by a single bridge edge. All cross-community information must pass through that bridge, and a fixed-size message cannot carry it all. This is a structural property of the graph, not a training failure, and adding layers makes it worse rather than better, because longer paths mean more compression steps.

Rewiring methods, which add or reweight edges to shorten important paths, and graph transformers, which allow direct attention between distant nodes, are both attempts to relieve this bottleneck. They help, but they change the inductive bias of the model: a transformer that attends to all nodes is no longer strictly a local message passing model, and that trade-off should be made deliberately.

3. Heterophily: when neighbours disagree

Message passing assumes, implicitly, that neighbours are informative about each other. On homophilic graphs, where connected nodes tend to share labels, that assumption holds. On heterophilic graphs, where connected nodes tend to differ, it fails. A classic example is a dating network or a fraud network: fraudsters deliberately connect to legitimate users, so averaging a node with its neighbours mixes the signal you are trying to detect with the noise you are trying to avoid.

The fix is not to abandon graphs, but to stop assuming that aggregation should always smooth. Models for heterophilic graphs separate a node's own features from its neighbours' features, use signed or higher-order aggregations, or learn when to listen and when to ignore. The diagnostic step comes first: measure the label agreement between connected nodes before choosing a model. If neighbours usually disagree, a plain GCN is the wrong baseline.

4. Expressivity: the Weisfeiler-Lehman limit

There is a formal ceiling on what standard message passing can distinguish. Message passing GNNs are at most as powerful as the Weisfeiler-Lehman (WL) graph isomorphism test at telling graphs apart. Two graphs that the WL test cannot distinguish will also fool a standard GNN, no matter how large it is.

Concretely, a GNN that aggregates only neighbour multisets cannot count certain structures, such as triangles in some configurations, and cannot distinguish some regular graphs whose nodes all have identical neighbourhoods. This matters less for node classification on a single large graph, where features break the symmetry, and more for graph classification, where the whole graph is the input and structure is the signal. Higher-order GNNs and subgraph-based methods push past the WL limit, at a computational cost. Know which side of that limit your task sits on before promising that a bigger GNN will solve it.

Common pitfalls in practice

• Leaking labels through the graph. In transductive node classification, the test nodes are present in the graph during training, just unlabelled. That is standard, but it means random node splits are not the same as random graph splits. If your deployment will see an entirely new graph, evaluate on a new graph, not on held-out nodes of the same graph.

• Ignoring degree. A model that sums neighbour messages without normalisation will be dominated by hubs. A model that averages will wash out the signal from a single important neighbour. Check both, and check what happens to low-degree and high-degree nodes separately, not just the average accuracy.

• Treating edges as uninformative. Many real graphs have edge types, weights, or timestamps. A model that ignores them is throwing away structure. If edges carry the signal, use a model that conditions messages on edge features, as in the general form above.

• Scaling by stacking layers. Neighbourhoods grow exponentially with depth on many graphs. A three-layer GNN on a graph with average degree ten already touches up to a thousand nodes per output. Sample neighbours, use mini-batch training, or accept a shallow model. Memory blow-ups in GNN training are usually neighbourhood explosion, not model size.

• Reporting only average accuracy. GNN failures are rarely uniform. Oversmoothing hurts minority classes first, heterophily hurts specific node types, and bottlenecks hurt specific communities. Break results down by degree, by community, and by class before concluding that the model works.

When to use a GNN, and when not to

Use a GNN when the relationships between items carry information that the items alone do not: molecules, citation and social networks, recommender systems viewed as user-item graphs, traffic networks, and knowledge graphs. Use it when the graph is available at prediction time and when the task genuinely depends on neighbourhood structure.

Do not use a GNN when the data are really tabular and the graph was constructed artificially, for example by connecting nearest neighbours in feature space. In that case the graph adds little beyond what a standard model already sees, and it adds failure modes that a standard model does not have. A GNN is not a generic upgrade to a multilayer perceptron. It is a strong inductive bias, and strong biases help only when they match the problem.

The takeaway

Message passing is a simple idea with sharp edges. A node updates itself from its neighbours, the update must not depend on neighbour order, and repeating that update builds a neighbourhood summary. That mechanism explains why GNNs work so well on homophilic graphs, why depth is a liability rather than a virtue, why long-range dependencies get squashed, and why some graphs are fundamentally beyond the reach of standard message passing.

The practical skill is not stacking more layers. It is diagnosing the graph first: how homophilic is it, where are its bottlenecks, how fast do neighbourhoods grow, and what does the task actually require a node to know? Answer those questions, and the choice of GNN, if a GNN is the right choice at all, becomes much clearer.

---

Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial