Node Classification in Graph Data using Augmented Random Walk

Node classification in graph data plays an importantrole in web mining applications. We classify the existing nodeclassifiers into Inductive and Transductive approaches. Amongthe Transductive methods, the Majority Rule method (MRM) hasa prominent role. This method considers only the class labels ofthe neighboring nodes, neglecting the informative connectivityinformation in the graph data. In this paper, we propose anAugmented Random Walk (ARW) based approach to resolvemain limitations of MRM. In our proposed method, first, weaugment the initial graph by adding class labels as new nodes tothe graph and then we connect each classified node to itscorresponding class label nodes. Second, we apply a RandomWalk algorithm to find the similarity score of each un-classifiednode to different class labels. Third, we predict class labels withthe highest scores for the un-classified node. Empirical resultsshow that our proposed method clearly outperforms the MajorityRule method in six graph datasets with high homophily.

Keywords:

Node Classification , Majority Rule , Graph Augmentation , Random Walk