## 3 Proposed Methodology
### Justification of Betweenness Centrality Based Training  
Let us consider a network in terms of a graph \(G(V,E)\) such that \(V\) is the set of vertices or nodes defined as \(\left\{v_{1},v_{2},\ldots,v_{n}\right\}\in V\), and \(E\) is the set of edges or links defined as \(\left\{e_{1},e_{2},\ldots,e_{k}\right\}\in E\) such that \(n\), \(k>1\). Figure 3: Instance of a path graph (\(P_{5}\)) with centrality scores based on importance. Let \(X\) be the feature matrix of order \(n\times m\) defined for each node \(v_{i}\in V\). Thus, the feature matrix's row will be given as: \(\{x_{1},x_{2},\ldots,x_{m}\}\)\(\forall\)\(x_{i}\in X\) such that \(1<i<m\). Generally, we have \(n>m\) (size of training data \(>\) size of feature vector for each node) in order to avoid the condition of overfitting during the training process. We consider total \(p\) different classes (\(\{c_{1},c_{2},\ldots,c_{p}\}\)) for the underlying node classification problem; i.e., each node \(v_{i}\) belongs to one of these \(p\) classes which is represented by its label \(l_{i}\) associated with it; \(l_{i}\in\{c_{1},c_{2},\ldots,c_{p}\}\) where \(p<<n\). Consider the optimal label set \(L\), where each node has its correct classification label; i.e., the correct class value is known for all the nodes. So far, we have defined all the basic terminologies of our proposed model. Our goal is to identify a mapping (predicted label set) that is close to the optimal set \(L\). We need to show that the classification accuracy of the GAT model improves when nodes with high betweenness centrality are chosen as training nodes for the model. For this, we need to show two things:  
1. A subset of training nodes selected based on betweenness centrality improves training efficiency. 2. The probability of selecting the same subset of nodes by a traditional GAT/GCN model (by default random selection of training nodes) is near zero. Let us consider the first statement and infer its validity. A subset of training nodes selected based on betweenness centrality improves training efficiency. For GCN and GAT as per Sections 2.1 and 2.2, we already know that the model accuracy depends on the neighborhood aggregation. In other words, neighborhood aggregation contributes to more and more availability of features for training the data. We can say that _training efficiency \(\propto\) feature availability \(\propto\) neighborhood aggregation_. Thus, the problem reduces to finding an efficient subset of nodes that can increase the availability of features. Let \(A^{\prime\prime}\) be a subset of nodes defined over the set \(V\) such that nodes are selected in order of betweenness centrality score. Let \(A^{\prime}\) be another subset of nodes from the set V such that the nodes are randomly selected. Here \(cardinality(A^{\prime})=cardinality(A^{\prime\prime})\) is maintained. Suppose the very first node (with the highest betweenness centrality) \(a\in A^{\prime\prime}\) is selected, and the first node in \(b\in A^{\prime}\) is selected. Since the nodes in \(A^{\prime\prime}\) are selected based on betweenness centrality, the following holds,  
\[\textit{betweenness centrality score}(a)>\textit{betweenness centrality score}(b)\]  
We assume that \(a\
eq b\), i.e., that the same node \(a\) is not selected by the random selection process. The reason is that the probability of the node \(a\) being selected by the random process is \(1/n\), which is close to zero for large values of \(n\). According to the definition of betweenness centrality from Section 3.1, a node with a high betweenness centrality value participates in a larger number of shortest paths between different pairs of nodes of the graph. This implies that:  
\[\textit{Number of shortest paths with membership of node }a>\textit{Number of shortest paths with membership of node }b\]  
It should be noted that node coverage up to \(q\) path length should be considered, where \(q>0\), and generally has a small value. For GAT, the neighborhood contribution is not taken into account for a path length of two hops or more.