Skip to Main content Skip to Navigation
Reports

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

https://hal.inria.fr/hal-01192871
Contributor : Konstantin Avrachenkov <>
Submitted on : Thursday, September 3, 2015 - 5:14:40 PM
Last modification on : Wednesday, October 14, 2020 - 3:57:25 AM
Long-term archiving on: : Friday, December 4, 2015 - 12:04:03 PM

Files

RR-8767.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

Konstantin Avrachenkov, Vivek 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⟩

Share

Metrics

Record views

284

Files downloads

183