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.

University of Michigan - Ann Arbor

Google

During each message-passing iteration in a 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)}_u, \forall v \in N(u)\})$  
...

$h^{(k+1)}_u  = UPDATE^{(k)}(h^{(k)}_u, m^{(k)}_{N(u)})$ 
		
where $UPDATE$ and $AGGREGATE$ are arbituary 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

Learn Before

Related