MPNNs can be expressed as graph convolutions

[[concept]]

Idea

Consider an MPNN. As long as $M_{ℓ}$ is linear, the "message" can be expressed as a graph convolution.

Example

$\begin{aligned} M_{ℓ} [(x_{ℓ})_{i}, (x_{ℓ})_{j}, A_{i j}] & = α \cdot (x_{ℓ})_{i} + β \cdot A_{i j} (x_{ℓ})_{j} \\ ⟹ m_{ℓ} & = α x_{ℓ} + β A x_{ℓ} \end{aligned}$

which is a graph convolution with $K = 2, S = A, h_{0} = α, h_{1} = β$

As long as $U_{ℓ}$ is the composition of a pointwise nonlinearity $σ$ with a linear function $M_{ℓ}$ , then $x_{ℓ}$ can be expressed as a GNN layer

Example

$\begin{aligned} U_{ℓ} [(x_{ℓ})_{i}, (m_{ℓ})_{i}] & = σ (α^{'} (x_{ℓ})_{i} + β^{'} (m_{ℓ})_{i}) \\ ⟹ x_{ℓ + 1} & = σ ([α^{'} + β^{'} α] x_{ℓ} + β^{'} β A x_{ℓ}) \end{aligned}$

Which is a graph convolution with $K = 2, S = A, h_{0} = α^{'} + β^{'} α, h_{1} = β^{'} β$

Mentions

File
2025-02-17 graphs lecture 8