In the second step of neural message passing, the update function $$\text{UPDATE}$$ combines the aggregated message $$m^{(k)}_{N(u)}$$ with the previous embedding $$h^{(k-1)}_u$$ of node $$u$$ to generate the updated embedding $$h^{(k)}_u$$ for the current iteration $$k$$. The initial embeddings at $$k = 0$$ are set to the input features for all nodes, such that $$h^{(0)}_u = \mathbf{x}_u$$ for all $$u \in V$$.

Neural Message Passing: Update Step

In the first step of neural message passing, at each iteration $$k$$ of the Graph Neural Network (GNN), the $$\text{AGGREGATE}$$ function takes as input the set of embeddings of the nodes in node $$u$$'s graph neighborhood $$N(u)$$ and generates a message $$m^{(k)}_{N(u)}$$ based on this aggregated neighborhood information.

Neural Message Passing: Aggregation Step

After running $$K$$ iterations of the GNN message passing, we can use the output of the final layer to define the embeddings for each node, i.e., $$z_u = h^{(K)}_u, \forall u \in V$$.

Neural Message Passing: Final Output Step

Neural Message Passing can be broken down into three steps

Carleton College

One of the defining features of a GNN is that it uses a form of *neural message passing* in which vector messages are exchanged between nodes and updated using neural networks

Neural Message Passing

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

Steps of Neural Message Passing

There are several ways of generalizing or improving the “AGGREGATE” operator:

1)	Neighborhood Normalization

2)	Set Aggregators

3)	Neighborhood Attention


Generalized Neighborhood Aggregation

To use mini-batch training, one can work with a subset of nodes during message passing.

Subsampling of Graph-level Message Passing

The GNN message passing approach can also be generalized to leverage edge and graph-level information at each stage of message passing. One of the most important in the generalized message passing framework is that we generate hidden embeddings for each edge in the graph, as well as an embedding corresponding to the entire graph during message passing.

Generalized Message Passing

During each message-passing iteration in a Graph Neural Network (GNN), a hidden embedding $$h^{(k)}_u$$ corresponding to each node $$u \in V$$ is updated according to information aggregated from $$u$$’s graph neighborhood $$N(u)$$. The message-passing update can be expressed by: $$h^{(k+1)}_u = UPDATE^{(k)}(h^{(k)}_u, AGGREGATE^{(k)}(\{h^{(k)}_v, \forall v \in N(u)\}))$$ or alternatively as: $$h^{(k+1)}_u = UPDATE^{(k)}(h^{(k)}_u, m^{(k)}_{N(u)})$$ where $$UPDATE$$ and $$AGGREGATE$$ are arbitrary differentiable functions (neural networks) and $$m_{N(u)}$$ is the "message" that is aggregated from $$u$$'s graph neighborhood $$N(u)$$.

Learn Before

Related

Learn After