Skip to Main content Skip to Navigation

Parallel and Distributed Approaches for Graph Based Semi-supervised Learning

Abstract : 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.
Complete list of metadata
Contributor : Konstantin Avrachenkov Connect in order to contact the contributor
Submitted on : Thursday, September 3, 2015 - 5:14:40 PM
Last modification on : Thursday, January 20, 2022 - 4:17:38 PM
Long-term archiving on: : Friday, December 4, 2015 - 12:04:03 PM


Files produced by the author(s)


  • HAL Id : hal-01192871, version 1
  • ARXIV : 1509.01349



Konstantin Avrachenkov, Vivek S. Borkar, Krishnakant Saboo. Parallel and Distributed Approaches for Graph Based Semi-supervised Learning. [Research Report] RR-8767, Inria Sophia Antipolis. 2015, pp.24. ⟨hal-01192871⟩



Record views


Files downloads