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

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

1)	Neighborhood Normalization

2)	Set Aggregators

3)	Neighborhood Attention


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.

Generalized Message Passing

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

Carleton College

GNNs are a general framework for defining deep neural networks on graph data. The goal of GNNs is to generate representations of nodes that actually depend on the structure of the graph, as well as any feature information available.

Graph Neural Networks (GNNs)

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

Given an input graph $G = (V,E)$ and a set of node features **X** $\in \mathbb{R}^{d*|V|}$, our goal is to produce a node embedding $z_u$, for all nodes in the graph.

Formal Definition of GNN

Neural Message Passing

In the context of GNNs, many of the standard regularization approaches are known to work well, including L2 regularization, dropout, and layer normalization. However, there are also regularization strategies that are somewhat specific to the GNN setting.

Regularization in GNN

GNNs had been independently developed from several distinct theoretical motivations and perspectives:
- Graph convolutions: the theory of graph signal processing, as a generalization of Euclidean convolutions to the non-Euclidean graph domain.
- Probabilistic graphical models: neural message passing approaches proposed by analogy to message passing algorithms for probabilistic inference in graphical models.
- Graph isomorphism: connection to the Weisfeiler-Lehman graph isomorphism
test.

Theoretical Motivations of GNNs

Original node-level message passing mechanism can be time-consuming.

Efficiency Concerns of GNNs

 $\mathcal{L} = \sum_{ \mathcal{G}_i \in \mathcal{T} } \| MLP( z_{\mathcal{G}_{i}} ) - y_{\mathcal{G}_{i}}  \|_{2}^{2}$

$z_{\mathcal{G}_{i}}$ is graph level embeddings

$\mathcal{T}  =  {\mathcal{G}_{1}, ..., \mathcal{G}_{n} }$ set of labeled training graphs

MLP ,densely connected feed forward neural network

$y_{\mathcal{G}_{i}  \in  {\rm I\!R} }$ is the target value for training graph $\mathcal{G}_{i}$


Definition of Loss in GNNs for Graph Classification

Pair wise node embedding loss function are deployed for applications utilizing graph relation prediction.

Loss function in GNNs for Relation Prediction

 - GNN pre-training approaches is an open and active area of research. 

 - Pretraining is an effective way   of injecting domain knowledge into a model before the actual training take place

 -  Pre-training a GNN using  neighborhood reconstruction loss  to reconstruct missing edges before a classification task does not improve the classification loss.

 -  A pre-training method called Deep Graph Infomax maximizes the mutual information between node embeddings $z_u$  and graph embeddings $ z_{\mathcal G}$.


Pretraining a GNN

The basic GNN can be derived as a neural network variation of the existing Weisfieler-Lehman (WL) isomorphism algorithm

GNNs and Graph Isomorphism

1. Given two graphs, we assign each node an initial label in each graph. 
2. We iteratively assign a new label to each node in each graph by hashing the multi-set of the current labels within the node’s neighborhood, as well as the node’s current label.
3. We repeat Step 2 until the labels for all nodes in both graphs converge.
4. Finally, we construct  multi-sets summarizing all the node labels in each graph, and we declare G1 and G2 to be isomorphic if and only if the multi-sets for both graphs are identical.

Learn Before

Related

Learn After