Graph Convolutional Network (GCN)
Introduction
Deep-learning problems are frequently associated with convolutional neural network solutions and are most commonly applied to visual imagery analysis. In this article, we highlight another powerful concept which is the graph convolutional network [1]. If we define our graph we can say it represents a set of nodes and edges which are connections between these nodes. So far, we will discuss how GCN does work taking into account each step, we will see also an example of spam and non-spam classification using GCN.
How does it work
In that perspective, we can say that the idea behind a GCN is that a node in the graph can send and receive messages (the figure below shows an example of a message, quite simply, it is a vector of data) along with its connections ‘neighbors’.
This can be thought of as happening in two steps:
The figure above shows these two steps, we focus on the red node supposing that each node has an initial state. First, it will send out a message about itself to its neighbors, and after that, the node collects the neighbor messages it receives and uses them in some way to update itself or its state. With this process, each node will understand its environment.
GCN layer
In this section, we approach the notion of the layer corresponding to GCN. For any node in the graph first, it gets all the attribute vectors of its connected nodes (including its message) and applies some aggregation function like an average as shown in the figure below assuring that every node has the same representation size. This process must be done for every single node in the graph
The averaged vector will be passed through a dense neural network which is multiplication by some matrix and applying an activation function. The output of this neural net is the new vector representation of the given node’s state. At this point, we reached a single GCN layer. The same philosophy is adopted if we want a second layer, we have to repeat the process discussed above except the input is the updated vectors from the first layer.
Example of use case
Spam and non-spam is a basic example to better understanding. Imagine we have a collection of spam and non-spam e-mail content with their addresses, so we want to use the actual content of the e-mail as a node attribute. Several techniques make a simple message into a data vector, like pre-trained word embeddings. In our classification task, let’s say we end up with a 20-dimensional vector that represents each e-mail.
We will be satisfied with one GCN layer, each node will be initialized with a 20-dimensional vector and set the output dimensionality of the dense neural net to1 and use a typical binary cross-entropy loss function with backpropagation to train all of our params. Firstly, for each node, it aggregates its content vector with all of the neighbor’s content that has the same address, the aggregation function might be a simple average. The resulting vector will be the input of the dense neural net that has a single output to decide whether it is spam content or not. Here you can find an advanced GCN example using the Planetoid dataset [2].
Conclusion
In this article, we have seen a quick tour of the graph convolutional networks and a concrete example of a use case of this tool. For instance, many aspects can be considered, such as connections can have different types. Do we just average all the neighbors together regardless of the connection type, or maybe some connections are more important than others.
References
[1]: Thomas N. Kipf and Max Welling (2017) Semi-Supervised Classification with Graph Convolutional Networks https://arxiv.org/abs/1609.02907
[2]: Planetoid dataset https://pytorch-geometric.readthedocs.io/en/latest/_modules/torch_geometric/datasets/planetoid.html
