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 connectivity by passing messages between neighbors
  • Neighboring nodes (or edges) exchange data and influence the updated embeddings.
  • Message passing works in three steps:
      1. For each node, gather all the neighboring node embeddings (or messages)
      1. Aggregate all messages via an aggregate function (like sum).
      1. 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\).
  • 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

  1. Gilmer, Justin, et al. “Neural message passing for quantum chemistry.” International Conference on Machine Learning. PMLR, 2017.↩︎