A novel dominating set and centrality based graph convolutional network for node classification

To learn and analyze graph-structured data, Graph Neural Networks (GNNs) have emerged as a powerful framework over traditional neural networks, which work well on grid-like or sequential structure data. GNNs are particularly designed to record dependencies and relations in large and complicated networks such as social networks, molecular structures, citation networks and recommendation systems. The main idea behind GNN is the message-passing mechanism that allows sharing of information between nodes and edges in a graph network, enabling the model to learn about graph structures and perform well even with limited training data. GNNs have three different architectures: Graph Convolutional Network (GCN), GraphSAGE, Graph Attention Model (GAT) and other hybrid models. In this paper, we have proposed novel GCN models namely dominating Set with Degree Centrality based GCN (DS_DC_GCN) and dominating Set with Betweenness Centrality based GCN (DS_BWC_GCN) model, for node classification task. In the traditional GNN models, training nodes are selected randomly. In our proposed models, we first identify a subset of the nodes with the help of a dominating set (D) of the underlying network. Then we consider final training nodes (say \(D'\) $D^{\prime }$ ) from set D based on the centrality scores (degree or betweenness). We give preference to nodes having high centrality scores for training. To evaluate the performance of the proposed models, we have used three standard citation network datasets - Cora, Citeseer and Pubmed. Our models obtain improved node classification performance as compared to other state-of-the-art-methods. The consideration of high centrality nodes of dominating set in training helps to improve the feature availability in the underlying computational graphs, which in turn improves learning and hence, model performance. These models also have the potential to offer better results for other network tasks, including link prediction and community detection.