Parallel and Distributed Approaches for Graph Based Semi-supervised Learning

Two approaches for graph based semi-supervised learning are proposed. The first approach is based on iteration of an affine map. A key element of the affine map iteration is sparse matrix-vector multiplication, which has several very efficient parallel implementations. The second approach belongs to the class of Markov Chain Monte Carlo (MCMC) algorithms. It is based on sampling of nodes by performing a random walk on the graph. The latter approach is distributed by its nature and can be easily implemented on several processors or over the network. Both theoretical and practical evaluations are provided. It is found that the nodes are classified into their class with very small error. The sampling algorithm's ability to track new incoming nodes and to classify them is also demonstrated.