Skip to content
mlmentorship

Graph neural networks: message passing as A·X·W

Neighbors carry signal. A graph neural network averages each node's neighborhood and projects with a learned matrix. The same matmul as a CNN, on irregular structure.

Published · 6 min read ·Core ·Intermediate

Visual quick review

Visual first · depth when needed

Connect a target node's graph neighborhood to the corresponding row of normalized adjacency, then trace how that row aggregates node features before the shared linear transform and activation.

Preparing the visual…

Summary

A graph neural network (GNN) updates each node’s features by aggregating its neighbors’ features and applying a learned transformation. The simplest variant is one matmul: , where is a normalized adjacency matrix and stacks node features.

A CNN exploits regular grid structure with shared local filters. A GNN applies shared parameters and local aggregation to neighborhoods defined by graph edges. This supports models for social networks, molecules, knowledge graphs, code ASTs, and recommender bipartite graphs.

GNNs power drug-discovery pipelines (AlphaFold’s Evoformer, DeepMind’s GNoME), large-scale recommenders (Pinterest’s PinSAGE, Uber’s GraphSAGE), and protein structure prediction. Modern transformers are arguably a special case (complete graph with attention as edge weighting).

The mechanism: GCN

The graph convolutional network (Kipf & Welling, 2017) is the canonical GNN:

where is the symmetrically normalized adjacency with self-loops.

Decompose:

  1. Aggregate: forms a degree-normalized weighted sum of each node’s neighbors and itself (via the self-loop).
  2. Transform: multiply by to mix features.
  3. Activate: ReLU or similar.

After layers, each node has aggregated information from its -hop neighborhood. The network is a sequence of matmuls, the same operation as any other deep learning model. The graph structure shows up only in .

Learning objective

Connect one node's neighborhood to one row of A-hat H W.

One GCN update shown as a graph neighborhood and a matrix row Four nodes form a cycle. Target node B is connected to A and C, while D is not its neighbor. Self-loops give every node degree three, so row B of normalized adjacency is one third, one third, one third, zero in A, B, C, D order. Multiplying by scalar node features three, zero, six, nine aggregates three at B. Multiplying by weights two and negative one gives six and negative three, and ReLU produces B's new two-feature vector six, zero. 1 - READ THE TARGET NODE'S NEIGHBORHOOD A B C D neighbor neighbor self-loop B receives from A, B, C D is connected in the graph, but not in B's one-hop set. 2 - THE B ROW SELECTS AND WEIGHTS THOSE FEATURES node order ABCD A-hat row B 1/3 1/3 1/3 0 x H 3 0 6 9 All self-added degrees are 3, so each included weight is 1/3. 3 - AGGREGATE, TRANSFORM, ACTIVATE A-hat H at B 1 + 0 + 2 = 3 x W [2, -1] [6, -3] [6, 0] linear transform ReLU
Read it this way: choose target B, then read across row B of A-hat. Nonzero entries align exactly with B's two neighbors plus B's self-loop; multiplying that row by H forms B's degree-normalized aggregate. The shared matrix W mixes that aggregate into new feature channels, and ReLU yields B's next representation. Here the cycle's self-added degrees are all 3, so symmetric normalization reduces to an exact one-third mean. Original worked example checked against Kipf and Welling (2017) and the PyTorch Geometric message-passing documentation.

Variants by aggregator

  • GraphSAGE (Hamilton et al., 2017). Sample a fixed number of neighbors per node; aggregate with mean, max, or LSTM. Practical for large graphs where full-neighbor aggregation is infeasible.
  • GAT (Veličković et al., 2018). Replace uniform averaging with learned attention weights per edge: . Same form as transformer attention, restricted to graph neighbors.
  • GIN (Xu et al., 2019). Use sum aggregation and a learnable epsilon. Provably as expressive as the Weisfeiler-Lehman graph isomorphism test.
  • Message-passing neural networks (Gilmer et al., 2017). General framework: edges carry messages, nodes aggregate, both can be parametrized.

What the message-passing framework looks like

Most GNNs fit:

Aggregate is permutation-invariant (sum, mean, max, attention). Different choices give different GNN families.

Where GNNs hit walls

  • Over-smoothing. After many layers, all nodes converge to similar representations. Practical depth: 2 to 5 layers for most graphs. Workarounds: residual connections, gating, jumping-knowledge networks.
  • Over-squashing. Information from distant nodes gets compressed through narrow bottlenecks. Long-range dependencies are hard.
  • Scalability. Full-graph training is per layer; sampling (GraphSAGE) or graph clustering (Cluster-GCN) is needed for large graphs.
  • Expressiveness. Standard GNNs cannot distinguish graphs that the Weisfeiler-Lehman test cannot distinguish. More expressive variants (k-GNN, subgraph GNN) are slower.

Transformers as graphs

A standard transformer is a GNN on the complete graph with attention as the edge function. This is why graph transformers (Graphormer, GraphGPS) work: take a transformer, restrict the attention pattern to edges (or weight by graph distance), get a GNN with strong expressiveness.

Common pitfalls

  • Treating GNNs as deep. They go shallow (2 to 5 layers) for over-smoothing reasons.
  • Forgetting self-loops. Without them, a node loses its own features after one aggregation step.
  • Using sum without normalization on heterogeneous-degree graphs. High-degree nodes dominate; normalize by degree or use mean/attention.
  • Reporting accuracy without specifying the data split. Transductive vs inductive performance differ dramatically; many papers fudge this.

Found an error or stale claim? Report a correction or send a private note.