Contents

## Understand What GNN Is and What GNN Can Do

Graph Neural Network(GNN) recently has received a lot of attention due to its ability to analyze graph structural data. This article gives a gentle introduction to Graph Neural Network. It covers some graph theories for the ease to understand graphs and the problems in analyzing graphs. It then introduces Graph Neural Network in different forms and their principles. It also covers what GNN can do and some applications of GNN.

First, we need to know what is a graph.

A graph is a data structure consisting of two components: ** vertices, **and

**. It is used as a mathematical structure to analyze the pair-wise relationship between objects and entities. Typically, a graph is defined as**

*edges**G=(V, E),*where

*V*is a set of nodes and

*E*is the edges between them.

A graph is often represented by an Adjacency matrix, *A. *If a graph has *N *nodes, then A has a dimension of (*N*x*N*). People sometimes provide another feature matrix to describe the nodes in the graph. If each node has *F *numbers of features, then the feature matrix *X *has a dimension of (*N*x*F*).

## Why Is a Graph Difficult To Analyze?

Firstly, a graph does not exist in a Euclidean space, which means it cannot be represented by any coordinate systems that we are familiar with. This makes the interpretation of graph data much harder as compared to other types of data such as waves, images, or time-series signals(“text” can also be treated as time-series), which can be easily mapped to a 2-D or 3-D Euclidean space.

Secondly, a graph does not have a fixed form. Why? Look at the example below. Graph (A) and Graph (B) have a completely different structure and visually different. But when we convert it to adjacency matrix representation, the two graphs have the same adjacency matrix (if we don’t consider the weight of edges). So should we consider these two graphs are the same or different?

And lastly, a graph is in general hard to visualize for human interpretation. I’m not talking about small graphs like the examples above. I’m talking about giant graphs that involve hundreds or thousands of nodes. The dimension is very high and nodes are densely grouped, making it even difficult for a human to understand the graph. Therefore, it is challenging to train a machine for this task. The example below shows a graph modeling the logic gates in an integrated circuit.

## Why Use Graphs?

The reasons that people choose to work on graphs can be summarized in a few points as listed below:

- Graphs provide a better way of dealing with abstract concepts like relationships and interactions. They also offer an intuitively visual way of thinking about these concepts. Graphs also form a natural basis for analyzing relationships in a social context.
- Graphs can solve more complex problems by simplifying the problems into simpler representations or transform the problems into representations from different perspectives.
- Graph Theories and concepts are used to study and model Social Networks, Fraud patterns, Power consumption patterns, Virality and Influence in Social Media. Social Network Analysis (SNA) is probably the best-known application of Graph Theory for Data Science.

Traditional methods are mostly algorithm-based, such as :

- searching algorithms, e.g. BFS, DFS
- shortest path algorithms, e.g. Dijkstra’s algorithm, Nearest Neighbour
- spanning-tree algorithms, e.g. Prim’s algorithm
- clustering methods, e.g. Highly Connected Components, k-mean

The limitation of such algorithms is that we need to gain prior knowledge of the graph at certain confidence before we can apply the algorithm. In other words, it provides no mean for us to study the graph itself. And most importantly, there is no way to perform graph level classification.

Graph Neural Network, as how it is called, is a neural network that can directly be applied to graphs. It provides a convenient way for node level, edge level, and graph level prediction task.

There are mainly three types of graph neural networks in the literature:

- Recurrent Graph Neural Network
- Spatial Convolutional Network
- Spectral Convolutional Network

The intuition of GNN is that nodes are naturally defined by their neighbors and connections. To understand this we can simply imagine that if we remove the neighbors and connections around a node, then the node will lose all its information. Therefore, the neighbors of a node and connections to neighbors define the concept of the node.

Having this in mind, we then give every node a state *(x)* to represent its concept. We can use the node state *(x)* to produce an output *(o)*, i.e. decision about the concept. The final state *(x_n) *of the node is normally called “node embedding”. The task of all GNN is to determine the “node embedding” of each node, by looking at the information on its neighboring nodes.

We will start with the most pioneer version of Graph Neural Network, Recurrent Graph Neural Network, or *RecGNN*.

## Recurrent Graph Neural Network

As introduced in the original GNN paper, RecGNN is built with an assumption of Banach Fixed-Point Theorem. Banach Fixed-Point Theorem states that: *Let (X,d) be a complete metric space and let (T:X→X) be a contraction mapping. Then T has a unique fixed point (x∗) and for any x∈X the sequence T_n(x) for n→∞ converges to (x∗). *This means if I apply the mapping *T *on* x *for *k *times, x^k should be almost equal to x^(k-1), i.e.: