# What is a GNN?

For the use of *IGNNITION*, we focus on one of the most basic GNN
architectures named *Message-Passing Neural Networks (MPNN)*, which is a
well-known GNN family that covers a wide range of standard GNN
architectures.

The input of a GNN is a graph *G=(V, E)* – directed or undirected –
that comprises a set of nodes \(V\) and some edges connecting them \(E\). Each node
*v* has an associated vector of a predefined size that encodes its state,
namely, the node hidden state \(h_v\). At the beginning of a GNN execution,
hidden state vectors \(h_v\) are initialized with some node-related features \(x_v\)
included in the input graph. Optionally, edges may also contain a set of
features denoted by \(e_{uv}\) where \(u,v \in V\).

Once the hidden states are initialized, a message-passing algorithm is
executed according to the connections of the input graph. In this
message-passing process, three main phases can be distinguished: *(i)
Message*, *(ii) Aggregation*, and *(iii) Update*. First, every node \(v \in V\)
sends its hidden state to all its neighbors \(u \in N(v)\). Then, each node applies
the *message function* \(M(·)\) to each of the received messages respectively, to
obtain a new more refined representation of the state of its neighbors.
After this, every node merges all the computed messages from its
neighbors into a single fixed-size vector \(m_v\) that comprises all the
information. To do this, they use a common *Aggregation function* (e.g.,
element-wise summation ). Lastly, every node applies an *Update
function* \(U(·)\) that combines its own hidden state \(h_v\) with the final aggregated
message from the neighbors to obtain its new hidden state. Finally, all
this message-passing process is repeated a number of iterations
\(T\) until the node hidden states converge to some fixed values.
Hence, in each iteration, a node potentially receives — via its direct
neighbors — some information of the nodes that are at \(k\) hops in the
graph. Formally, the message passing algorithm can be described as:

All the process is also summarized in the figure below:

After completing the *T* message-passing iterations, a *Readout
function* \(R(·)\) is used to produce the output of the GNN model. Particularly,
this function takes as input the final node hidden states \(h^t_v\) and converts
them into the output labels of the model \(\hat{y}\):

At this point, two main alternatives are possible: *(i)* produce
per-node outputs, or *(ii)* aggregate the node hidden states and
generate global graph-level outputs. In both cases, the *Readout*
function can be applied to a particular subset of nodes.

One essential aspect of GNN is that all the functions that shape its
internal architecture is *universal*. Indeed, it uses four main
functions that are replicated multiple times along the GNN architecture:
*(i)* the *Message* , *(ii)* the *Aggregation* , *(ii)* the *Update* ,
and *(iv)* the *Readout* . Typically, at least, and are modeled by
three different Neural Networks (e.g., fully-connected NN, Recurrent NN)
which approximate those functions through a process of joint
fine-tunning (training phase) of all their internal parameters. As a
result, this dynamic assembly results in the learning of these universal
functions that capture the patterns of the set of graphs seen during
training, and which allows its generalization over unseen graphs with
potentially different sizes and structures.

# Additional material

Some users may find the previous explanation too general as, for
simplicity, we focus only on the most general scenario. For this reason,
we provide some additional material to learn about *GNNs* in more depth.

## Blogs

Below we also enumerate several blogs that provide a more intuitive
overview of *GNNs*.

## Courses

Due to the fact that *GNNs* are still a very recent topic, not too many
courses have been taught covering this material. We, however, recommend
a course instructed by Standford university named Machine learning with
graphs.