Node Classification in Graph Data using Augmented Random Walk

Node classification in graph data plays an important role in web mining applications. We classify the existing node classifiers into Inductive and Transductive approaches. Among the Transductive methods, the Majority Rule method (MRM) has a prominent role. This method considers only the class labels of the neighboring nodes, neglecting the informative connectivity information in the graph data. In this paper, we propose an Augmented Random Walk (ARW) based approach to resolve main limitations of MRM. In our proposed method, first, we augment the initial graph by adding class labels as new nodes to the graph and then we connect each classified node to its corresponding class label nodes. Second, we apply a Random Walk algorithm to find the similarity score of each un-classified node to different class labels. Third, we predict class labels with the highest scores for the un-classified node. Empirical results show that our proposed method clearly outperforms the Majority Rule method in six graph datasets with high homophily.