A simplification of neural message passing omits the explicit update step, and instead simply adds a self-loop: $$\mathbf{h}_u^{(k)}=\text{AGGREGATE}(\{\mathbf{h}_v^{(k-1)},\forall v\in \mathcal{N}(u)\cup\{u\}\})$$ where $$\mathbf{h}_u^{(k)}$$ is the $$k^{th}$$ hidden layer of node $$u$$. In the case of a basic Graph Neural Network (GNN), it can be written as the following graph-level update: $$\mathbf{H}^{(t)}=\sigma((\mathbf{A}+\mathbf{I})\mathbf{H}^{(t-1)}\mathbf{W}^{(t)})$$ where $$\mathbf{H}^{(t)}$$ is the graph-level hidden layer representation.

University of Notre Dame

Google

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)$$.

Formal Definition of 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

Neural message passing operations can be implemented efficiently using sparse matrix multiplications. The graph-level equation for a basic Graph Neural Network (GNN) is:

$$H^{(k)} = \sigma(A H^{(k-1)} W^{(k)}_{neigh} + H^{(k-1)} W^{(k)}_{self})$$

where $$H^{(k)}$$ is a matrix containing the layer-$$k$$ embeddings of all the nodes, and $$A$$ is the adjacency matrix. This formulation avoids redundant computations.

Learn Before

Related