Graphs as Data & Message PassingOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Graphs as Data & Message Passing

Most ML assumes data lives on a grid (images), a sequence (text), or a flat table (rows of features). But molecules, social networks, road maps, knowledge graphs, and recommendation systems are graphs: entities connected by relationships, with no fixed order and no fixed number of neighbors. Graph Neural Networks (GNNs) learn directly on this structure. This lesson sets up how a graph becomes learnable data and introduces the single idea (message passing) that nearly every GNN is built from. That message-passing design is a hypothesis-space choice with a specific inductive bias: permutation equivariance over a graph — relabel the nodes and the output follows. It's the fourth of the four architectures in the inductive-bias story (CNN/RNN/transformer/GNN as one idea, four symmetries).

Deep dive
The ML Project Loop
Includes runnable notebook

Real-world examples: predicting molecular properties for drug discovery, fraud detection on transaction graphs, friend/product recommendation, traffic forecasting on road networks, and reasoning over knowledge graphs.

What is a graph, for ML?

A graph G=(V,E)G = (V, E) is a set of nodes VV and edges EE connecting them. For learning we attach features:

  • Node features xv∈Rd\mathbf{x}_v \in \mathbb{R}^{d} — e.g. an atom's element, a user's profile vector.
  • Edge features euv\mathbf{e}_{uv} — e.g. a bond type, a transaction amount (optional).
  • Graph-level features / labels: e.g. "is this molecule toxic?".

The connectivity is captured by the adjacency matrix A∈{0,1}n×n\mathbf{A} \in \{0,1\}^{n\times n}, where Auv=1A_{uv} = 1 if there's an edge u→vu\to v. Node features stack into X∈Rn×d\mathbf{X} \in \mathbb{R}^{n\times d}.

Grids and sequences are just special graphs

An image is a graph where each pixel connects to its 4 (or 8) neighbors; a sentence is a graph where each token links to the next. CNNs and RNNs are GNNs with a fixed, regular neighborhood. GNNs generalize them to arbitrary, irregular connectivity.

The two hard constraints

A graph model must respect two properties that grids and sequences don't force on you:

  1. Permutation invariance / equivariance. There is no "first" node — relabeling the nodes must not change the prediction (for graph-level tasks) and must permute the outputs identically (for node-level tasks). Any operation over neighbors must therefore be order-independent.
  2. Variable neighborhood size. Different nodes have different numbers of neighbors, so you can't use a fixed-size weight per neighbor slot the way a CNN kernel does.

Both constraints point to the same solution: aggregate neighbor information with a permutation-invariant function (sum, mean, max) rather than a position-dependent one.

Message passing: the core framework

Nearly every GNN is an instance of message passing. Each node iteratively updates its representation by gathering ("aggregating") messages from its neighbors and combining them with its own state. One round (layer) for node vv:

hv(k)=UPDATE(hv(k−1),  AGGREGATE({hu(k−1):u∈N(v)})⏟message from neighbors)\mathbf{h}_v^{(k)} = \text{UPDATE}\Big(\mathbf{h}_v^{(k-1)},\; \underbrace{\text{AGGREGATE}\big(\{\mathbf{h}_u^{(k-1)} : u \in \mathcal{N}(v)\}\big)}_{\text{message from neighbors}}\Big)

where N(v)\mathcal{N}(v) are the neighbors of vv, and hv(0)=xv\mathbf{h}_v^{(0)} = \mathbf{x}_v. The two functions:

  • AGGREGATE: a permutation-invariant pooling over the neighbor set (sum/mean/max). This is what enforces permutation invariance and handles variable neighbor counts.
  • UPDATE: a learnable transform (typically a small neural net) combining a node's old state with the aggregated message.

A concrete simple instance — mean-aggregation with a learned linear update:

hv(k)=σ ⁣(W(k)⋅mean({hu(k−1):u∈N(v)∪{v}}))\mathbf{h}_v^{(k)} = \sigma\!\Big(\mathbf{W}^{(k)} \cdot \text{mean}\big(\{\mathbf{h}_u^{(k-1)} : u \in \mathcal{N}(v) \cup \{v\}\}\big)\Big)

Receptive field: why stack layers

After one message-passing layer, each node knows about its immediate neighbors. After kk layers, information has propagated from up to kk hops away — the node's receptive field is its kk-hop neighborhood. This is the graph analogue of stacking convolutions to grow a CNN's receptive field.

How many layers until a node sees everything

15 of 60within 3 hopsall 60nodes reached1 layer6 layers
mean degree2.40
reach at 3 layers15 of 60
share of the graph25%
layers to reach everything> 6
reach per layer4, 9, 15, 22, 33, 40

A 60-node ring plus random shortcut edges. Node colour is graph distance from the highlighted node, and the shaded nodes are those a k-layer GNN can reach. The plot is the measured k-hop reach — breadth-first search, not an estimate.

"Up to kk hops away" sounds like a slow, controllable growth. On a bare ring it is — two new nodes per layer, so 6 layers reach 13 of 60 nodes and a 3-layer GNN really is local. Then add shortcut edges:

shortcutsmean degreenodes reached after 1…6 layers
02.003, 5, 7, 9, 11, 13
122.404, 9, 15, 22, 33, 40
302.975, 14, 27, 46, 59, 60

Thirty extra edges (less than a 50% increase in mean degree) take the 5-hop reach from 11 nodes to 59 of 60. Receptive field growth is exponential in the degree, and real graphs (citation networks, social graphs, molecules with rings) all have the shortcuts.

That is the whole depth problem in one plot, and it runs the opposite way from CNNs. There, depth is how you afford a wide receptive field. Here, the receptive field arrives almost immediately and the danger is that it arrives completely — once every node aggregates the same set of nodes, every node computes the same thing.

More layers is not always better (over-smoothing)

Unlike CNNs, stacking many GNN layers often hurts: after too many rounds every node has aggregated nearly the whole graph and all node embeddings converge to the same vector — over-smoothing. Most GNNs use only 2–4 layers. (Covered in Lesson 3.)

Tasks on graphs

The same machinery serves three task levels, differing only in the final readout:

TaskPredictionExample
Node-levelone label per nodeclassify each user as fraud/not
Edge-levellabel/score per edgewill these two users connect? (link prediction)
Graph-levelone label per whole graphis this molecule toxic? (needs a readout pooling all nodes)

Exercise

Why must a graph neural network's neighbor-aggregation step use a function like sum, mean, or max rather than, say, concatenating neighbors in order?

Need a hint?

Graph nodes have no canonical ordering.

Exercise

In the message-passing framework, a GNN layer computes hᵥ = UPDATE(hᵥ, AGGREGATE({hᵤ : u ∈ neighbors})). What is the role of AGGREGATE?

Need a hint?

It combines a variable-size set of neighbor states into one message.

Exercise

After how many message-passing layers can a node's representation be influenced by another node that is exactly 3 hops away?

1layers4.50layers8layers
Need a hint?

Each layer propagates information one hop further.

Common mistakes

  1. Imposing an order on nodes. Treating a graph's adjacency or node list as if it had a meaningful sequence breaks permutation invariance — use order-independent aggregation.
  2. Using a fixed weight per neighbor. Neighbor counts vary; weights must be shared and aggregation must pool a variable-size set.
  3. Stacking deep GNNs by reflex. Beyond a few layers, over-smoothing collapses node representations.
  4. Forgetting self-information. Aggregating only neighbors (not the node itself) loses the node's own features — include a self-loop or a self-term in UPDATE.

Key takeaways

  • A graph (V,E)(V, E) with node/edge features is learnable data; the adjacency matrix encodes connectivity. Grids and sequences are regular special cases.
  • Graph models must be permutation-invariant and handle variable neighbor counts, which forces order-independent aggregation (sum/mean/max).
  • Message passing: AGGREGATE neighbor states, then UPDATE — is the framework underlying nearly all GNNs; kk layers give a kk-hop receptive field.
  • Node-, edge-, and graph-level tasks share the machinery; graph-level tasks add a readout that pools all nodes.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
Graphs as Data & Message PassingNeural NetworksGraph Convolutions & Grap…Layers & the Forward PassThe Convolution OperationInductive Bias & Equivari…The ML Project LoopGraph-Based Fraud Detecti…