Relational Classification Using Random Walks in Graphs

A novel approach to relational classification based on a Gaussian Random Field and random walks over the graph representing labeled and unlabeled examples is proposed in the paper. Additionally, a class homogeneity measure has been introduced. It can be used for pre-assessment of method applicability for particular networks. The presented experimental results on eight datasets revealed that the framework based on random walk concept possesses the promising potential to effectively classify nodes in the network. Owing to the dependencies discovered, the usefulness of the Random Walk approach to relational classification can be assessed from careful study of proposed class homogeneity distribution in the network.