
The Message-Passing Abstraction
Overview of the framework
Alternative Types of GNN convolutions
- Spectral Convolutions: Utilize the graph Laplacian’s eigendecomposition to perform convolutions in the spectral domain.
- Spatial Convolutions: Aggregate information from local neighborhoods directly, using node connections defined by the adjacency matrix.
- GraphSAGE: Generates embeddings by sampling and aggregating features from a node’s local neighborhood.
- Graph Attention Networks (GATs): Use attention mechanisms to weigh the importance of neighboring nodes differently.
- Graph Convolutional Networks (GCNs): Extend traditional convolutions to graph structures by averaging feature information from neighboring nodes.
- ChebNet: Utilizes Chebyshev polynomials for efficient spectral filtering, reducing computational complexity.
- Graph Isomorphism Network (GIN): Focuses on distinguishing graph structures by using injective aggregation functions.
- Diffusion Convolutional Neural Networks (DCNN): Models the diffusion process on graphs to capture long-range dependencies.
We would like a Unified framework which encapsulates all of these models into an overarching theoretical formalism.
Message Passing: Overview
Definition:
Message passing in GNNs is the process of exchanging and aggregating information between neighboring nodes in a graph to learn node representations.
Steps in Message Passing:
- Message Computation: Nodes compute messages to send to their neighbors based on their current features.
- Message Aggregation: Each node collects messages from its neighbors.
- Feature Update: Aggregated messages are combined with the node’s current features to update its representation.
Closer look
- We incorporate the graph
connectivityby passing messages between neighbors - Neighboring nodes (or edges) exchange data and influence the updated embeddings.
Message passing works in three steps:- For each node, gather all the neighboring node embeddings (or messages)
- Aggregate all messages via an aggregate function (like sum).
- All pooled messages are passed through an update function, usually a learned neural network.
- This sequence, applied once, forms a
message-passing GNN layer. - Message passing can occur between either nodes or edges.
- By stacking message passing GNN layers together, a node can eventually incorporate information from across the entire graph: e.g. after three layers, a node has information about the nodes three steps away from it.
The Message-Passing Abstraction
The same idea, written as equations
For node \(v\) with neighbors \(\mathcal{N}(v)\):
Message from neighbor \(u\): \[m_{u\to v} = \text{MESSAGE}\big(h_u,\, h_v,\, e_{uv}\big)\]
Aggregate over all neighbors: \[a_v = \text{AGGREGATE}\big(\{\, m_{u\to v} : u \in \mathcal{N}(v)\,\}\big)\]
Update the node state: (an example of the update step is a linear transformation, followed by a non-linear activation function) \[h_v' = \text{UPDATE}\big(h_v,\, a_v\big)\]
This template has a name: the Message-Passing Neural Network (MPNN)
One rule the aggregation must obey
- A node’s neighbors form a set, not a list \(\rightarrow\) no “first,” no “last”
- So the aggregate must give the same answer regardless of order
- This property is called permutation invariance
- Safe choices: sum, mean, max
- Unsafe: anything order-dependent (e.g. concatenation)
Another visualization of Message passing

Visualizing aggregation permutation invariance

Example GCN described in the message passing framework
The GCN layer
- Graph Convolutional Network (Kipf & Welling, 2017):the “hello world” of GNNs
- One layer, in matrix form: \[H' = \sigma\!\left(\hat{D}^{-1/2}\,\hat{A}\,\hat{D}^{-1/2}\,H\,W\right)\]
- Ingredients:
- \(\hat{A} = A + I\):adjacency with self-loops
- \(\hat{D}\):degree matrix of \(\hat{A}\)
- \(W\):the one learnable weight matrix
- \(\sigma\):a nonlinearity (e.g. ReLU)
- Looks heavy:but it is just aggregate + update in disguise
Mapping GCN onto aggregate → update
| MPNN step | GCN’s specific choice |
|---|---|
| Message from neighbor \(u\) | its feature \(h_u\), scaled by \(\tfrac{1}{\sqrt{d_u\, d_v}}\) |
| Aggregate | sum of those normalized messages |
| Update | multiply by \(W\), then apply \(\sigma\) |
- No attention, no learned message function
- GCN is the simplest useful point in the design space
GCN from scratch:the whole layer
- The entire layer is one normalized matrix multiply + \(W\) + ReLU
- A GNN layer really is just a few lines of NumPy:
import numpy as np
def gcn_layer(A_norm, H, W):
# aggregate: A_norm @ H | update: @ W then ReLU
return np.maximum(0, A_norm @ H @ W)
H_out = gcn_layer(A_norm, H, W)
print("input :", H.shape, " -> output:", H_out.shape)input : (5, 2) -> output: (5, 3)
Example from the textbook
Same example but using the convention from textbook:
We can consider general convolutions using a unifying message-passing framework 1
Node hidden state \(h_i^{(t)}\) where \(i\) is the node’s index at time step \(t\).
Initial value \(h_i^{(0)}\) is defined as \(\boldsymbol{X}_{\boldsymbol{i}}\)
- i.e. the row of \(\boldsymbol{X}\) associated with node i.
Any graph convolution can be split into (1) a message-passing phase and (2) a node update phase.
- Let \(N(i)\) be the neighbors of node \(i\).
- For directed graphs, \(N(i)\) is the set of nodes that have an edge whose endpoint is node \(i\).
- Let \(N(i)\) be the neighbors of node \(i\).
The message-passing phase with message function \(M_t\)
\[ m_i=\sum_{j \in N(i)} M_t\left(h_i^{(t)}, h_j^{(t)}, e_{i j}\right) \]
The node update phase with the update function \(U_{\boldsymbol{t}}\) is \(h_i^{(t+1)}=U_t\left(h_i^{(t)}, m_i\right)\).
Example: Convolution from the previous example
Consider the convolution from the previous example:
\[x_i^{\prime}=x_i W_1+\sum_{j \in N(i)} x_j W_2+b\]
In this case the message is \(m_i=\sum_{j \in N(i)} M_t\left(h_i^{(t)}, h_j^{(t)}, e_{i j}\right)\)
where the message function was \(M_t=h_j^{(t)} W_2\).
The node update phase with the update function \(U_{\boldsymbol{t}}\) is \(h_i^{(t+1)}=U_t\left(h_i^{(t)}, m_i\right)\).
Example
Message-passing idea and summarizes the convolution

Summary table for different models
- Swap the three functions → get a different GNN
- Every popular model below is message passing under the hood

Summary
- Every GNN layer = aggregate neighbor messages → update node state
- Aggregation is always permutation-invariant (sum / mean / max)
- Stacking layers enlarges the receptive field: \(k\) layers → \(k\)-hop view
- GCN is the simplest instance: normalized-sum message + linear/ReLU update
- Learn this one scaffold, and GraphSAGE, GAT, GIN, … are just variations on it
This abstraction is the hook everything else in the course hangs on.
Sources
This content is drawn primarily from the following sources:
- Machine Learning with PyTorch and Scikit-Learn: Develop Machine Learning and Deep Learning Models with Python Book by Liu Yuxi, Sebastian Raschka, and Vahid Mirjalili

- “A Gentle Introduction to Graph Neural Networks” https://distill.pub/2021/gnn-intro/
- “Graph neural network” https://en.wikipedia.org/wiki/Graph_neural_network
- Machine Learning with PyTorch and Scikit-Learn by Sebastian Raschka, Yuxi Liu, Vahid Mirjalili
- GPT-3.5 and GPT-4
Footnotes
Gilmer, Justin, et al. “Neural message passing for quantum chemistry.” International Conference on Machine Learning. PMLR, 2017.↩︎