Graph Convolutional Networks: A Theoretical Deep Dive
Tags: python, deeplearning, geometriclearning
Published: 2020-10-20 20:06:58

## *Prerequisites*
*Basic knowledge about graphs, linear algebra, and convolutional neural networks.*


# Introduction
In the field of Deep Learning (DL), particularly in Computer Vision (CV), Convolutional Neural Network (CNN) plays a vital part in extracting features of a given image. Structurally, images form a regular grid of integer values (0-255) divided into three channels (RGB). Therefore, one may visualize an image as a regular graph with nodes as the R, G, or B color value. For each non-edge pixel/node, there are eight edges to adjacent pixels/nodes. Taking advantage of this fixed structure, CNNs use 2D filters to perform the convolution operations. 

However, various data sources are essentially graphs but do not follow a regular structure as that of images. For example, knowledge graphs, social networks, or even 3D meshes with vertices as the nodes. So how do we use deep learning magic on these data? This blog answers the question by:
1. [Introducing the structure of a Graph Convolutional Networks(GCN).](#chapter-1) 
2. [Looking into the three underlying principles of convolutional operations in CNNs and GCNs.](#chapter-2)
3. [Finally, understanding the forward propagation rule of GCNs.](#chapter-3)

# 1. Structure of a Graph Convolutional Networks(GCN). <a name="chapter-1"></a>

<figure>
![GCN](https://dev-to-uploads.s3.amazonaws.com/i/xojuqb50pmo8qgi8h4es.png) 
  <figcaption>Fig.1 - Block diagram of a GCN. *Diagram imitates the one provided in by [(Kipf, 2016)](#ref-1).*</figcaption>
</figure>

Structurally the following components form the GCN:
1. **Input {% katex inline %}(X){% endkatex %}** is a graph (represented as {% katex inline %}
G=(V, E){% endkatex %}), where {% katex inline %}V{% endkatex %} denotes vertices and {% katex inline %}E{% endkatex %} denotes edges) in the form of adjacency list {% katex inline %}A{% endkatex %}  and a feature matrix {% katex inline %}X{% endkatex %} having the shape {% katex inline %} N\times D {% endkatex %} ({% katex inline %}N{% endkatex %} is the number of nodes/vertices and {% katex inline %}D{% endkatex %} is the number of input features).
2. **Hidden Layers {% katex inline %}(H){% endkatex %}** maintain the same graph structure. Also, their feature matrix {% katex inline %}Z{% endkatex %} is of the shape {% katex inline %}N\times F{% endkatex %} where {% katex inline %}F{% endkatex %} is the number of features of a node for that layer. 
3. **Output {% katex inline %}(Y){% endkatex %}** depends on the task at hand. For the semantic segmenting of a 3D mesh, it will be the same graph with the output matrix {% katex inline %}Y{% endkatex %} of the shape {% katex inline %}N\times C{% endkatex %} where {% katex inline %}C{% endkatex %} is the number of classes. If we want to classify the entire graph, we will have to add a linear layer at the end of the last hidden layer to get the prediction.

As evident from the output of the GCN is a function that maps an input graph to the output by learning features of the graph.

# 2. The Three Underlying Principles of Convolution Operations.<a name="chapter-2"></a>


 
In this section, we will compare the graph convolution (GC) layer with the basic convolution layer. Upon comparison, we will observe that a GC layer follows the same three principles as that of the convolution layer. After gaining this intuition, we will formulate the forward propagation rule for a GC layer in the following section.

<figure><a name="fig-2"></a>
![img-graph](https://dev-to-uploads.s3.amazonaws.com/i/56hk4qt8y095wmam9lh7.png)
  <figcaption>Fig.2 - Comparison of the principle of locality and composition in a CNN layer and a GCN layer.</figcaption>
</figure>
 
So what are the three principles on which CNNs work and how are emulated in GCNs?
1. **Locality:** It states that during the convolution operation at a given position, the neighboring positions' values contribute towards determining its new value. For example, if we choose a 3{% katex inline %}\times{% endkatex %}3 kernel, all the eight adjacent pixels contribute their values. Message passing in GCN allows it to follow the principle of locality. In [fig. 2](#fig-2), the yellow nodes denote the locality of the green node. 
2. **Aggregation:** This principle states that the local contribution of each node must be "summed-up," "meaned-over," or aggregated to get the new value. In the conventional convolution operation, it is the multiplication of adjacent pixels with the kernel weights. For graph convolution, it is the mean of the sum of values of the entire locality.
3. **Composition:** Standard convolution layers use the concept of composition (function-of-function) to increase their "field of perception." At a given instance, locality and aggregation serve to capture local features but doing this in composition allows information to pass over the area of a single convolution kernel. Consider [fig. 2](#fig-2) again. At, {% katex inline%}H^{l-1}{% endkatex %} while the green node was evaluating its new value based on adjacent nodes, so were the yellow nodes, as the kernel slid over them (for the standard convolution case). Therefore, at {% katex inline%}H^{l}{% endkatex %}, all yellow nodes hold information of the red nodes also. As we calculate the new value for the green node at {% katex inline%}H^{l}{% endkatex %}, we implicitly feed in the data of the non-adjacent red nodes; this is the true essence of message passing. For convolution layers, it is easy to observe that as we increase the size of the convolution filter, the "field of perception" increases proportionally with each step. With an expanded perception field - the networks capture more complex patterns in the data. As far as vanilla GCNs go, each composition allows the passing over of information from a node adjacent to the already established perception boundary.


# 3. The Forward Propagation Rule. <a name="chapter-3"></a>

In this section, we will finally formulate the forward propagation rule for a graph convolution layer. Let's approach this by iteratively unveiling the equation.

![The formula-Page-1](https://dev-to-uploads.s3.amazonaws.com/i/fn6x6846wy7em8dxb36p.png)

As you can see, we have seven blanks to fill. Let's get going!

![The formula-Page-2](https://dev-to-uploads.s3.amazonaws.com/i/qurbqexf0qi26153e3qy.png)

The first blank is quite simple. It's just the denotation of the {% katex inline %}(l+1)^{th}{% endkatex %} GCN layer.

![The formula-Page-3](https://dev-to-uploads.s3.amazonaws.com/i/ltdh4b8a6i9e78fgx2qu.png)

Now, we see that the {% katex inline %}(l+1)^{th}{% endkatex %} GCN layer is a non-linear function having the inputs: the current GCN layer matrix and the adjacency matrix.

![The formula-Page-4](https://dev-to-uploads.s3.amazonaws.com/i/ont6swjd3merowjmq7pw.png)

Finally, we move on to the actual function. The {% katex inline %}l^{th}{% endkatex %} layer matrix is in between two other matrices yet to be revealed. Keep note that the shape of the {% katex inline %}l^{th}{% endkatex %} layer matrix is {% katex inline %}D\times F^{(l-1)}{% endkatex %}, where {% katex inline %}D{% endkatex %} is the number of nodes, and {% katex inline %}F^{(l)}{% endkatex %} is the number of features in the {% katex inline %}l^{th}{% endkatex %} layer.

![The formula-Page-5](https://dev-to-uploads.s3.amazonaws.com/i/xxbaudosptkbt3w1dzy6.png)

Moving on, we see that the {% katex inline %}\hat{A}\ (A + I){% endkatex %} matrix is in multiplication with {% katex inline %}H^{(l)}{% endkatex %}. The first point of note: using {% katex inline %}\hat{A}{% endkatex %} ensures that only the adjacent nodes and itself are selected during the multiplication. Thus, the locality principle is maintained. Further, the summation of their activations follows the aggregation principle. Secondly, we use {% katex inline %}A + I{% endkatex %} instead of only {% katex inline %}A{% endkatex %} because we want to enforce self-loops. That is, the current node's information must contribute to future calculation.

![The formula-Page-6](https://dev-to-uploads.s3.amazonaws.com/i/vh71iqokamyh19f63g6b.png)

Summation of all the adjacent activations in a dense graph leads to an explosion of gradients, hence, the network becomes difficult to train. To mitigate this, we multiply the diagonal degree matrix of Ahat to average out the summed-up activations. In the end, {% katex inline %}D^{-1}\hat{A}H{% endkatex %} produces an {% katex inline %}N\times F^{(l-1)}{% endkatex %} matrix that has the normalized aggregated information from the locality.

![The formula-Page-7](https://dev-to-uploads.s3.amazonaws.com/i/ffimr1kz4i5p2s1oc01k.png)

Now, this matrix is multiplied by the layer's weight matrix of the shape {% katex inline %}F^{(l-1)}\times F^{(l)}.{% endkatex %} The weight matrix is trainable.

![The formula-Page-8](https://dev-to-uploads.s3.amazonaws.com/i/4oft4wc00e87adk5irzk.png)

Finally, we get the activations of the layer by passing the {% katex inline %}N\times F^{(l)}{% endkatex %} matrix through a non-linear activation function like ReLU. Basically, the network has converted a graph with nodes having features of dimension {% katex inline %}F^{(l-1)}{% endkatex %} to {% katex inline %}F^{(l)}{% endkatex %}.


The final equation in all it's glory is as follows:

![The formula-Page-9](https://dev-to-uploads.s3.amazonaws.com/i/k20g4xhbxszs95uhjdxr.png)

A final note of interest is that we technically do not take the mean of the adjacent node values; instead, we use spectral normalization as mentioned in [Kipf et. al. [2]](#ref-2).

The modified equation is as follows:

{% katex %}f(H^{(l)}, A) = \sigma\left( \hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H^{(l)}W^{(l)}\right) \{% endkatex %}


# Conclusion.

With this post, we delved deep into the theoretical foundation of a Graph Convolutional Network. The next post will show how powerful this simple setup is by semantically segmenting 3D meshes from the COSEG dataset. We will also look into how well these networks learn in a semi-supervised situation, that is when only a few labels are available per class. Stay tuned!
     
# References.
[1] Kipf, T., 2016. How Powerful Are Graph Convolutional Networks?. [online] Tkipf.github.io. Available at: <https://tkipf.github.io/graph-convolutional-networks/> [Accessed 20 October 2020].<a name="ref-1"></a>
[2] Kipf, T., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. Retrieved 20 October 2020, from https://arxiv.org/pdf/1609.02907.pdf <a name="ref-2"></a>
[3] Published in Grandjean, Martin (2014). "La connaissance est un réseau". Les Cahiers du Numérique. 10 (3): 37–54. doi:10.3166/lcn.10.3.37-54. Retrieved 20 October 2020. [Banner credits]