Semi-supervised Learning on Directed Graphs

Abstract

Given a directed graph in which some of the nodes are labeled, we\ninvestigate the question of how to exploit the link structure of\nthe graph to infer the labels of the remaining unlabeled nodes. To\nthat extent we propose a regularization framework for functions\ndefined over nodes of a directed graph that forces the\nclassification function to change slowly on densely linked\nsubgraphs. A powerful, yet computationally simple classification\nalgorithm is derived within the proposed framework. The\nexperimental evaluation on real-world Web classification problems\ndemonstrates encouraging results that validate our approach.