Code
input : (5, 2) -> output: (5, 3)
We would like a Unified framework which encapsulates all of these models into an overarching theoretical formalism.
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:
connectivity by passing messages between neighborsMessage passing works in three steps:
message-passing GNN layer.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)
| 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\) |
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}}\)
Any graph convolution can be split into (1) a message-passing phase and (2) a node update phase.
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)\).
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)\).
Message-passing idea and summarizes the convolution
This abstraction is the hook everything else in the course hangs on.
This content is drawn primarily from the following sources: