Semi-Supervised Learning on Directed Graphs

Given a directed graph in which some of the nodes are labeled, we investigate the question of how to exploit the link structure of the graph to infer the labels of the remaining unlabeled nodes. To that extent we propose a
regularization framework for functions dened over nodes of a directed graph that forces the classication function to change slowly on densely linked subgraphs. A powerful, yet computationally simple classication algorithm is derived within the proposed framework. The experimental evaluation on real-world Web classication problems demonstrates encouraging results that validate our approach.