## 2 Literature Survey
### Graph Convolutional Neural Networks (GCNs)  
Graph Convolutional Networks are the type of neural networks that work directly with graphs. The idea of Graph Convolution is analogous to Convolutional Neural Networks (CNNs) for images. The main difference between CNNs and GCNs is that CNNs work with regular Euclidean (structured) data, while GCNs work with data in non-Euclidean space. This is due to the irregularities in the network structure caused by the different neighborhood connections and alignments. Therefore, the operational feature extraction method is different from the one used for CNNs. Therefore, we need a mathematical model formulation based on spectral graph theory to solve the problem. The convolution operation defined for an image using CNNs introduces hidden convolution and pooling layers to identify spatially localized features via a set of receptive fields in kernel form. We slide the convolutional operator window across a two-dimensional image, and we compute some function over that sliding window. Then, we pass it through many layers. Convolution takes a little sub-patch of the image (a little rectangular part of the image), applies a function to it, and produces a new part (a new pixel). The center node of that center pixel aggregates information from its neighbors, as well as from itself, to produce a new value. However, the same strategy cannot be utilized for GCNs due to the arbitrary size of the graph and the complex topology, which means there is no spatial locality. The structural differences are depicted in Figure 1. In addition, the convolution operation must be invariant to node order. For GCNs, the challenging task is to identify an encoding function which can encode the nodes of a graph in a d-dimensional space preserving the proximity of nodes as in the original graph (local network neighborhoods). Based on this, the computational graph for each node is defined, and aggregation of information is performed for a particular node. Thus, we have convoluted information aggregated over each node of the network. Here, we consider the problem of node classification by GCN. The general idea of GCN is to collect information about the neighborhood of a node for which the class is to be predicted. This includes both the local neighborhood information and the characteristics of the individual node, which serve as input to the model. Let us build the model based on this information. Let \(G\) be an undirected graph with \(V\) a set of nodes such that \(v_{i}eV\) and let \(E\) be the set of edges such that \((v_{i},v_{j})eE\). Furthermore, let \(X\) be the feature vector corresponding to each node in \(N\). From this, the aggregation function can be defined as follows:  
\[Z=f(A,X)=A\times X \tag{1}\]  
in which \(A\) is an adjacency matrix, such that \(A\epsilon R^{NXN}\), \(X\) is the feature vector matrix, such that \(XeR^{NXC}\), \(N\) is the number of nodes in the network, \(C\) is the dimensions of the feature vector, and \(\lambda\) is \(Scalar(\lambda>0)\). Equation (1) represents the sum of all neighborhood vectors except itself. For this purpose, consider a self-loop for each node:  
\[\hat{A}=A+\lambda I_{N} \tag{2}\]  
Thus, the final aggregated function becomes:  
\[Z=\hat{A}\times X \tag{3}\]  
To prevent the dominance of feature vectors, the function is normalized using the degree matrix. The degree matrix over the graph '\(G\)' with adjacency matrix '\(A\)' is defined as: \(D_{i,i}=\sum_{j}A_{ij}\). Using this information, the aggregate convolution function is defined as [2]:  
\[Z=f(A,X)=D^{-1/2}\hat{A}D^{-1/2}\times X \tag{4}\]  
The adjacency matrix is scaled over both rows and columns. This provides the weighted average scaled uniformly both for low and high degree nodes.