Graph Neural Networks: Message Passing for Non-Euclidean Data
A CNN assumes your data lives on a regular grid of pixels. A Transformer assumes your data is a sequence of tokens. Both are great -- if your world actually looks like that. But proteins don't. Molecules don't. Friendship networks don't. Road maps don't. The interaction graph of every particle in a fluid simulation doesn't. For everything that lives on an irregular, variable-sized, permutation-invariant graph, we need a different architecture. Graph Neural Networks are the answer, and the central operation -- "let every node ask its neighbors what they think, then update itself" -- turns out to be the same operation that powers AlphaFold 2's protein folding, GNoME's discovery of 2.2 million new materials, GraphCast's weather forecasting, and Pinterest's recommendations for three billion images. Once you see the message-passing template, you will spot it inside every modern architecture, including CNNs and Transformers themselves.
Learning Objectives
After this lesson, you will be able to:
Explain why graphs need a different neural network architecture than grids or sequences -- permutation invariance, variable size, and heterogeneous neighborhoods are the three obstacles a vanilla MLP cannot handle
Derive the message-passing framework (AGGREGATE then COMBINE, repeated K times) and show that GCN, GraphSAGE, GAT, and Graph Transformers are all instances of this one template
Implement a 2-layer GCN in numpy on a tiny social network, normalize the adjacency the way Kipf and Welling did, and read off the K-hop receptive field of each node
Explain the over-smoothing problem (all node embeddings converge after too many layers) and the over-squashing problem (information from far away gets exponentially compressed through bottlenecks), and name the standard fixes
See that a Transformer is a GNN on a fully-connected graph and a CNN is a GNN on a regular 2D grid -- so the three big modern architectures collapse into one unified message-passing view
The fundamental insight of this lesson is simple. CNNs aggregate information from neighboring pixels using a fixed sliding filter. Transformers aggregate information from all tokens using learned attention. Graph Neural Networks aggregate information from a node's graph neighbors using a learned function. All three are the same operation -- "look at your neighbors, mix their information into your own" -- applied to different kinds of neighborhood. Once you see this, the architecture zoo collapses into one elegant idea.
Everything we have built so far has had a strong locality assumption. A CNN assumes pixel (i, j) is most related to pixels (i ± 1, j ± 1) -- the regular grid is baked into the architecture. A Transformer assumes all tokens are equally accessible in O(1), which is great for sentences and image patches but expensive once N gets large. Both architectures impose a structure on the input.
The world, unfortunately, is mostly not a grid and mostly not a sequence. Consider:
Social networks. Facebook has roughly 3 billion users. Each user has a wildly variable number of friends -- some have 5, some have 5,000. There is no natural ordering of friends. Two users connected by an edge are "neighbors"; the rest are not.
Molecules. Caffeine has 24 atoms connected by 25 chemical bonds. Aspirin has 21 atoms and 21 bonds. Each molecule is a different graph. The position of an atom in the SMILES string is not meaningful -- only the bond topology is.
Knowledge graphs. Wikidata has 100 million entities (Q-IDs) connected by typed edges (P-IDs). "Marie Curie -- nationality -- Polish-French" is a triple, an edge in a graph with 9,000+ relation types.
Citation networks. Each scientific paper cites others. Cora, Citeseer, and arXiv are standard benchmarks; a paper's class (e.g., "neural networks", "case-based reasoning") is predictable from the citation graph alone, before reading a single word.
Scene graphs. A photo can be parsed into a graph of objects (person, dog, leash, park bench) with relationship edges (holding, sitting on, next to). Visual question answering systems reason over these graphs.
Code as abstract syntax trees. Every program is a tree (a special graph). Modern code-understanding systems like Codex's static analyzers and GitHub Copilot's index treat code as a graph of definitions, calls, and data flow.
Traffic networks. Roads are a graph of intersections connected by streets. Google Maps' ETA model is a GNN that uses live traffic on edges to predict travel time -- DeepMind reported a 20-50% improvement in ETA accuracy over the previous model after the switch.
Recommender systems. Pinterest's PinSage builds a graph with 3 billion pins and 18 billion edges (boards, users, pins). The recommendation model is a GNN.
Biological pathways. Every gene in a cell interacts with thousands of others through regulatory and metabolic edges. Drug-target interaction prediction is an edge-prediction problem on this graph.
Particle physics. The LHC produces collisions with hundreds of detected particles per event. CERN's jet-tagging networks treat each event as a graph of particles -- nodes are particles, edges are spatial or kinematic relations.
Every one of these breaks the grid assumption that makes CNNs work. None of them has an obvious linear ordering, so a Transformer would need to invent one or use full self-attention with no positional inductive bias. We need an architecture that natively understands "this is a set of nodes with arbitrary connections."
Formally, a graph is G = (V, E) where V is a set of N nodes and E is a set of edges between them. We attach features to each piece:
Node features x_v ∈ R^d. Each node has a d-dimensional feature vector. For a citation network, that might be the bag-of-words representation of a paper. For a molecule, the atom's element, charge, and hybridization state.
Edge features e_{uv} ∈ R^{d_e}. Optional. For a molecule, the bond type (single, double, aromatic). For a knowledge graph, the relation type. For a social network, just a binary indicator that the edge exists.
Adjacency matrix A ∈ R^{N×N}. Entry A_{uv} = 1 if there is an edge from u to v, else 0. For weighted graphs A_{uv} is the edge weight. Almost always extremely sparse in practice (most pairs are not connected).
GNNs are typically applied to one of four task families:
Task
Output lives on
Examples
Node classification
Each node
Classify users in a social network by interest; classify papers by topic
Link prediction
Each (potential) edge
Recommend friends, products, or papers; predict drug-target interactions
Graph classification
The whole graph
Predict if a molecule is toxic; classify a protein by function
Graph generation
A new graph
Generate candidate drug molecules; design new materials
The architecture is largely the same across these tasks -- only the readout head changes. For node classification, you read out per-node embeddings. For graph classification, you pool all node embeddings into one graph embedding. For link prediction, you score pairs of node embeddings.
When we list the nodes of a graph in matrix form, we have to pick an order. But the order is arbitrary -- if we relabel "node 3" as "node 7" and vice versa (a permutation of the rows of X and the rows/columns of A), the graph is the same. Our model's output must therefore be permutation equivariant for node-level tasks (the output for node v should not depend on what number we assigned it) and permutation invariant for graph-level tasks (the prediction for the whole graph must not depend on the labeling).
A plain MLP that flattens X and treats it as a single long vector is not permutation equivariant -- if you shuffle the rows of X, the MLP sees a totally different input. So a plain MLP cannot natively process graphs.
Caffeine has 24 atoms, aspirin has 21. A friendship subgraph for one user might have 50 nodes; for another, 5,000. A neural net with a fixed input size cannot consume both. CNNs handle this for images by global pooling at the end (any-size feature map collapses to a fixed vector). Transformers handle it by treating sequence length as a soft dimension (they can process any N, just at O(N²) cost). GNNs need the same flexibility.
In a CNN, every interior pixel has exactly the same neighborhood structure -- 8 neighbors at offsets (±1, ±1), (±1, 0), (0, ±1). The filter weight at offset (+1, 0) is a single number shared across the entire image. This is what makes CNNs efficient.
In a graph, the user "Alice" might have 5 friends, the user "Bob" might have 5,000. There is no consistent "neighbor 3" across nodes. We cannot use a separate weight for the third neighbor because the third neighbor of Alice and the third neighbor of Bob are completely different and there is no meaningful "third" -- the ordering is arbitrary. The aggregation has to be a permutation-invariant function over a variable-size set: a sum, mean, max, or attention-weighted average.
What Do You Think?
You take a 5-node graph and an MLP that flattens the node feature matrix X (shape 5×3) into a 15-dim vector and predicts a class label. You then permute the rows of X by swapping rows 0 and 4. What happens to the MLP's prediction?
In 2017, Justin Gilmer and collaborators at Google Brain noticed that almost every "graph neural network" published in the previous decade -- under names like graph convolutional networks, graph attention networks, MPNN, gated graph networks, interaction networks -- was a special case of one general template. They called it the Message Passing Neural Network (MPNN), and almost every modern GNN library is built around it.
A message-passing GNN repeats two operations, K times in a row, one per layer. For every node v:
1. AGGREGATE. Look at all neighbors u in N(v). Combine the neighbors' current representations h_u (and optionally the edge features e_{uv}) into one summary vector m_v using a permutation-invariant function like sum, mean, max, or attention.
2. COMBINE. Update v's own representation using its old state and the freshly aggregated neighbor message: h_v^{new} = COMBINE(h_v^{old}, m_v).
Step through a round of message passing to watch each node aggregate its neighbors and update its own representation.
Loading visualization...
The phrase "K-hop receptive field" is the GNN analog of a CNN's receptive field. After one message-passing layer, each node knows about its immediate neighbors. After two layers, it knows about neighbors-of-neighbors. After K layers, about everything within K hops in the graph. For most real-world graphs, the diameter (longest shortest path) is small -- the famous "six degrees of separation" finding -- so 3 to 6 layers is usually enough to cover the entire connected component.
What Do You Think?
On a 5-node line graph (a chain: 0 — 1 — 2 — 3 — 4), after 2 layers of message passing, node 2 (the middle node) knows about how many other nodes?
The choice of AGGREGATE and COMBINE is what distinguishes different GNN variants. Let's tour the four most influential ones.
Thomas Kipf and Max Welling at the University of Amsterdam published one of the cleanest GNN derivations. Their AGGREGATE is a symmetric normalized sum over neighbors:
H(k+1)=σ(D^−1/2A^D^−1/2H(k)W(k))
The two key tricks: (1) add self-loops (A + I) so the layer's output for node v includes v's own previous state without a separate COMBINE step -- it's folded into the aggregate; (2) symmetric normalization (D^{-1/2} A D^{-1/2}) which softly down-weights the contributions of high-degree neighbors. Without it, a single popular node would dominate the message-passing dynamics on social or citation networks.
The Kipf-Welling GCN is the "ResNet of GNNs" -- it is the default starting point, the most-cited graph neural network paper (45,000+ citations as of 2026), and the architecture against which every new GNN benchmarks itself.
Will Hamilton, Rex Ying, and Jure Leskovec at Stanford asked: what if the graph is too big to fit in memory? The Kipf-Welling formulation requires the full adjacency matrix. For Pinterest's 3-billion-node graph, that is a nonstarter. GraphSAGE's two innovations:
Neighborhood sampling. Instead of aggregating over every neighbor of v, sample a fixed number (say 25 for layer 1, 10 for layer 2). This bounds the per-node computation regardless of degree.
Inductive design. The model learns AGGREGATE and COMBINE functions, not embeddings tied to specific nodes. So you can apply the trained model to new graphs the model never saw, including new users joining the social network in real time. The Kipf-Welling formulation is transductive -- it sees the entire graph at training time and cannot easily generalize to new nodes.
GraphSAGE offered three AGGREGATE choices: mean, LSTM (over a random ordering of neighbors), and max-pool (apply an MLP per neighbor, then element-wise max). In practice the mean aggregator is the standard default. GraphSAGE-style sampling is what makes Pinterest's PinSage feasible.
#GAT: Graph Attention Network (Veličković et al. 2018)
Petar Veličković and collaborators (DeepMind, then at the University of Cambridge) noticed that the Kipf-Welling normalization assigns the same weight to every neighbor (up to the degree correction). But not every neighbor is equally important. In a citation network, a paper's most-cited reference is probably more informative than its least. So the GAT layer learns the attention weights between connected nodes:
If you squint, GAT looks exactly like self-attention from the Transformer lesson -- it is, almost. The two differences: (1) GAT only attends to graph neighbors, not to all nodes, so it scales as O(|E|) not O(N²); (2) GAT uses additive attention (concatenate then dot with a), whereas the original Transformer used multiplicative attention (dot product of Q and K). Modern graph attention models often borrow the Transformer's scaled-dot-product form for simplicity. The point is that GAT is "Transformer attention restricted to a sparse graph" -- which is exactly why it works so well.
The most recent line of work asks the obvious follow-up: what if we just run full self-attention over the entire node set, like a Transformer, but inject the graph structure as a kind of positional encoding? The graph topology becomes the "structural prior" and attention does the rest. Common ways to encode structure:
Laplacian positional encodings. Compute the eigenvectors of the graph Laplacian (the spectral analog of sinusoidal positional encodings) and concatenate the top-k of them onto each node's features. Nodes that are close in the graph end up with similar positional encodings.
Shortest-path distance bias. Add a learned bias to attention scores based on the shortest-path distance between the two nodes in the graph. This is the trick Microsoft's Graphormer used to win the OGB-LSC molecular benchmark in 2021.
Random-walk encodings. Take statistics of short random walks starting at each node and use them as a positional signal.
Graph Transformers handle long-range dependencies better than message-passing GNNs (since every node can in principle attend to every other node), at the cost of O(N²) per layer. For molecules with a few hundred atoms this is fine; for million-node graphs you need to combine sparse message passing with attention sparingly.
A fascinating variant comes from DeepMind's work on simulating physical systems. In Sanchez-Gonzalez et al. (2020), water droplets, sand, and goo are simulated by a GNN where the nodes are particles and the edges are dynamically constructed based on spatial proximity (rebuild the graph at each timestep based on which particles are within a radius R). The message-passing layers then output force/acceleration updates for each particle. The same architecture pattern -- under the name Graph Network Simulators (GNS) -- now drives AI weather forecasting (GraphCast), AI fluid dynamics, and AI structural mechanics. The graph is no longer a static dataset; it is the geometry of the physical world.
Quick check
What is the key permutation-related property a GNN architecture must satisfy that a vanilla MLP applied to a flattened adjacency matrix does NOT?
Time to make this concrete. Let's build a small GCN, train it on Zachary's Karate Club (a 34-node friendship network from a 1977 anthropology paper that has become the "iris dataset" of graph ML), and watch it recover the social factions.
Loading visualization...
What just happened: with only 4 labeled nodes out of 34 (one per faction), the GCN propagated label information through the graph topology and correctly classified almost every node. This is the "semi-supervised node classification" setting Kipf and Welling introduced, and it is the standard demo of how powerful message passing is. The CNN equivalent would be: train an image classifier given only 4 labeled images and ask it to label 30 more. Without the graph structure, this would be hopeless. With message passing, it works.
Now let's repeat the same kind of experiment but with a single-layer GAT, so we can see the learned attention weights as a heatmap over edges. A 7-node toy graph keeps it visualizable.
Loading visualization...
A few things to notice in the heatmap. First, each row sums to 1 (it is a softmax over neighbors). Second, dense diagonals are common -- self-attention is strong because the self-loop puts the node in its own neighborhood. Third, the bridge node 3 splits its attention across both clusters, which is exactly the asymmetry GAT is designed to learn. A plain GCN would have given equal normalized weights regardless of feature similarity.
If 2 layers covers 2 hops and 6 layers covers 6 hops, why not just stack 30 layers and cover the whole graph?
Because of over-smoothing. After each message-passing layer, a node's representation becomes a weighted average of its neighbors. After K layers, every node's representation has been averaged across an ever-growing neighborhood. If the graph is connected and you keep averaging, every node's representation converges to the same vector. Empirically this happens within 4 to 8 layers for most real graphs.
The opposite failure mode is over-squashing, identified by Alon and Yahav (2021). To convey information from a faraway node to your target node, you must pass it through the chain of intermediate nodes. Each hop compresses everyone's combined input into a fixed-size vector. After K hops, information from K-hop-away has been compressed and re-compressed K times. For small K, fine. For graphs with bottleneck topology (a few "bridge" nodes connecting otherwise-disconnected regions), the compression becomes catastrophic and the model can no longer distinguish messages from different far-away sources.
Standard fixes:
Graph rewiring. Add new edges to improve connectivity. Techniques like SDRF (Stochastic Discrete Ricci Flow) precompute which edges to add to reduce bottlenecks.
Virtual / master nodes. Add a single artificial node connected to all other nodes. It can shuttle global information in one hop and acts like a learned global pooling token. This is exactly the [CLS] token from BERT, applied to graphs.
Switching to a Graph Transformer. Full attention has no bottleneck -- every node attends to every other node in one layer. The price is O(N²) cost.
Over-smoothing and over-squashing are the two sides of the depth dilemma. You generally want a modest number of layers (2-4) plus an architectural escape valve for long-range dependencies.
Quick check
Which of these is NOT a reasonable strategy when your 8-layer GCN underperforms a 3-layer GCN on the same task?
GNNs are now infrastructure for several scientific fields. A short tour, mostly drawn from 2020-2024 work, since that is when the technology became dominant in production:
AlphaFold 2 (DeepMind 2020-2021). Protein structure prediction. The Evoformer module is a graph network whose nodes are amino acid residues and whose edges are pairwise distances; attention runs along the edges. AlphaFold 2 solved CASP14 with a median GDT-TS of 92.4, comparable to experimental crystallography. AlphaFold 3 (2024) extends the same architecture to protein-ligand and protein-DNA complexes.
GNoME (DeepMind 2024). Material discovery. A graph network represents each candidate crystal as a graph of atoms, edges = chemical bonds. GNoME proposed 2.2 million new inorganic crystalline structures, ~380,000 of which are predicted to be stable. The previous total number of known stable inorganic materials was around 48,000 -- a 10x expansion of human knowledge in one project.
GraphCast (Google 2023). Weather forecasting. Treats the Earth's atmosphere as a graph of ~1 million grid points; one forward pass produces a 10-day global forecast in ~60 seconds. Beats the European Centre's HRES numerical model on 90% of variables, including hurricane tracking. Now in operational testing at major meteorological agencies.
Drug discovery. ChemProp, D-MPNN, GIN, and other MPNNs are routinely used to predict molecular properties: toxicity, solubility, binding affinity, ADMET profiles. Halicin (2020) is the most-cited example -- MIT used a GNN to discover a new antibiotic active against previously resistant strains, by screening 100 million candidate compounds in silico.
Recommender systems. Pinterest's PinSage (2018) was the first production-scale graph network: 3 billion nodes, 18 billion edges. Recommendations for "what board should this pin go on" are computed via graph attention. Uber Eats, Alibaba's Taobao, and TikTok run similar architectures.
Code understanding. A program is an abstract syntax tree (AST) plus data-flow edges between definitions and uses. Graph networks operate on this graph to perform variable misuse detection, code summarization, and program repair. Microsoft's research line under Marc Brockschmidt produced the influential (2018) paper.
Once you internalize the AGGREGATE / COMBINE template, every GNN paper becomes the same equation with three blanks to fill in:
What is AGGREGATE? Sum (GIN), mean (GCN, GraphSAGE-mean), max (GraphSAGE-pool), attention-weighted average (GAT, Graph Transformer), LSTM over neighbors (GraphSAGE-LSTM), Gaussian-kernel weighted (GraphCast).
What is COMBINE? Add neighbor message to self after linear transform (GCN), concatenate then linear (GraphSAGE), gated update (GRU, used in Gated Graph Networks), pre-norm residual (modern Graph Transformers).
What goes on the edges? Just connectivity (GCN), learned attention scores (GAT), explicit edge features (MPNN, EdgeConv), shortest-path distance bias (Graphormer), 3D coordinates and bond types (AlphaFold's Evoformer pair representation).
Every architectural innovation -- including the ones that haven't been published yet -- is one of these three slots being filled differently. That is the entire taxonomy.
What Do You Think?
You are designing a GNN for drug discovery on small molecules (typically 20-80 atoms). You want the model to be permutation invariant, to use bond-type edge features (single/double/aromatic), and to be expressive enough to distinguish isomers that have the same set of atoms but different bond patterns. Which architectural choice is BEST?
#Try It Yourself: Graph Properties From Message Passing
A small challenge to consolidate. Try predicting whether a node is part of a triangle (a cycle of length 3) using a GCN versus a GAT. Triangle detection is famously a difficult task for vanilla GCNs (they cannot count substructures beyond a certain expressive limit, by the Weisfeiler-Lehman correspondence) but doable with richer architectures. The fact that there is a theoretical ceiling on what 1-WL message passing can express is one of the deepest results in the GNN literature -- Xu et al. (2019) introduced GIN, which provably matches the WL test's expressive power, and Maron et al. (2019) showed how to go beyond it with higher-order tensor representations. But that is a rabbit hole for another lesson.
GNNs are the message-passing template AGGREGATE -> COMBINE, repeated K layers. Every modern variant -- GCN, GraphSAGE, GAT, Graph Transformer -- is the same template with different choices for those two functions, and the K-hop receptive field grows naturally with depth.
Permutation invariance is the architectural constraint that forces the design. Sum, mean, max, and attention are the only permutation-invariant operations you can build into an aggregation; combined with sparse graph structure, they are the entire toolkit.
CNNs and Transformers are special cases of GNNs. CNNs operate on a regular grid graph with offset-specific filters. Transformers operate on a fully-connected graph with attention. Once you see this, the architecture zoo collapses into a single idea.
Depth has limits: over-smoothing and over-squashing. Vanilla GNNs hit a sweet spot at 2-4 layers. Going deeper requires skip connections, normalization, attention, or graph rewiring -- the standard depth-vs-receptive-field tools transplanted from CNNs and Transformers.
The applications speak for themselves. AlphaFold 2 (protein structure), GNoME (material discovery), GraphCast (weather), PinSage (recommendations), Halicin (drug discovery), and CERN's particle reconstruction pipelines are all GNNs in production. The architecture is now infrastructure for major scientific and commercial work.
Next up: how to apply these architectures end-to-end on real problems. We have built the toolbox; now it is time to deploy.
Learning to Represent Programs with Graphs
Knowledge graphs. Wikidata's 100 million entities are embedded as low-dimensional vectors via models like TransE, RotatE, and ComplEx. Modern systems use GNNs to contextualize each entity using its neighbors, then perform link prediction (Marie Curie -- nationality -- ?).
Particle physics. CERN's jet-tagging and event reconstruction pipelines use GNNs to identify particle types and trajectories. The graph is built dynamically from detector hits; the network classifies the underlying physics event (e.g., Higgs decay) from the message-passed output. ATLAS and CMS have both moved key reconstruction stages from boosted decision trees to GNNs since 2022.
Jumper et al. (2021), AlphaFold 2 -- the killer scientific application. The Evoformer's iterative graph attention solved the 50-year open problem of protein structure prediction.
Ying et al. (2021), Graphormer -- demonstrated that Transformer-with-structural-bias beats specialized GNNs on standard molecular benchmarks, opening the Graph Transformer era.
Merchant et al. (2024), GNoME at DeepMind -- material discovery at scale, with two orders of magnitude more new stable materials than were previously known.
The arc is striking: a 2009 paper few read, slowly rediscovered through clever simplifications, fused with attention from the Transformer revolution, and then unleashed on protein folding, weather, and material discovery within five years.