Parallel and Distributed Approaches for Graph Based Semi-supervised Learning

Les Approches Parallèles et Distribués pour l'Apprentissage Semi-supervisé

Konstantin Avrachenkov (1) , Vivek S. Borkar (2) , Krishnakant Saboo (2)

1 MAESTRO - Models for the performance analysis and the control of networks
2 IIT Bombay - Indian Institute of Technology Bombay

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.

Deux approches pour l'apprentissage semi-supervisé basé sur le graphe de similarité sont proposés. La première approche est basée sur l'itération d'un opérateur affine. Un élément clé de l'itération de l'opérateur affine est la multiplication vecteur par matrice de type sparse, qui a plusieurs implémentations parallèles très efficaces. La seconde approche appartient à la classe des algorithmes de Monte-Carlo par chaînes de Markov (MCMC). Elle est basé sur un échantillonnage de noeuds en effectuant une marche aléatoire sur le graphe de similarité. Cette dernière approche est distribué par sa nature et peut être facilement mis en oeuvre sur plusieurs processeurs ou sur un réseau. Évaluations théoriques ainsi que pratiques sont fournis. On constate que les noeuds sont classés dans leurs classes avec très petite erreur. La capacité de l'algorithme MCMC de suivre les nouveaux noeuds arrivants online et de les classer est également démontré.

Mots clés: Semi-supervised learning; Graph-based learning; Distributed algorithms; Parallel algorithms

Mots clés: Apprentissage semi-supervisé; Apprentissage basé sur le graphe de similarité; Algorithmes distribués; Algorithmes parallèles

Domaines: Réseaux et télécommunications [cs.NI]

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⟩