The most basic neighborhood aggregator takes a sum of a node’s neighbors. One drawback of this is that it’s highly sensitive to the node degrees. So there’s several ways of normalizing the aggregator.

Although it solves the degree sensitivity problem, it also caused loss of information. Indeed, it has been proven that an normalized GNN is less powerful than an not normalized GNN.


Neighborhood Normalization

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

1)	Neighborhood Normalization

2)	Set Aggregators

3)	Neighborhood Attention


University of Notre Dame

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

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

Neural Message Passing can be broken down into three steps

Steps of Neural Message Passing

An simplification of message passing omit the explicit update, but simply add 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 basic GNN, it can be wriiten 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.


Message Passing with Self-loops

Generalized Neighborhood Aggregation

Implement the message passing operation based on sparse matrix multiplications.
Graph level equation for a basic GNN is:
$H^{(k)} = \sigma(AH^{(k-1)}W^{(k)}_{neigh}+H^{(k-1)}W^{(k)}_{self})$
where $H^{(t)}$ is a matrix containing the layer-k embeddings of all the nodes.
There are no redundant computations using the equations.

Graph-level Implementations of Message Passing

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.

Learn Before

Related

Learn After