Scalable algorithms for graph-based semi-supervised learning with embedding

Mise à l'échelle des algorithmes pour l'apprentissage semi-supervisé basé sur des graphes avec le plongement De nos jours, l'apprentissage semi-supervisé basé sur les graphes (GB-SSL) est un domaine en plein essor pour classer les nœuds d'un graphe avec un nombre extrêmement faible de nœuds labélisés. Cependant, les algorithmes GB-SSL ont deux limites générales: la première est la complexité mémoire/temps qui se présente dans tous les algorithmes GB-SSL de pointe sur de larges graphes. En particulier, la forte consommation de mémoire se produit dans les réseaux de convolution de graphes et conduit à des problèmes d'OOM (Out of Memory) sur GPU ou RAM; la seconde apparaît dans tous les algorithmes GB-SSL basés sur la perte de régularisation Laplacienne. La contribution majeure de cette thèse est divisée en deux parties afin de proposer des stratégies qui garantiraient d'éviter les restrictions mentionnées ci-dessus. Dans la première partie de cette thèse, nous proposons un nouvel algorithme linéaire appelé Markov-Batch Stochastic Approximation (MBSA) pour résoudre le PageRank Personnalisé. MBSA met à jour des lots de nœuds et propose un compromis significativement meilleur que les autres modèles linéaires entre la consommation de mémoire et le taux de convergence pour un résultat de classification optimal. Ensuite, nous proposons un nouveau réseau de convolution de graphes à échelle, appelé MBSA-NN, qui intègre notre MBSA linéaire. Le MBSA-NN évite les problèmes d'OOM et réduit considérablement la consommation de temps et de mémoire sur GPU et RAM. Nous avons appliqué le MBSA-NN à plusieurs grands ensembles de données, et nous avons montré qu'il peut traiter des graphes avec plus de 10M nœuds et 2M de caractéristiques en une minute sur une machine standard, y compris le temps de prétraitement, d'apprentissage et d'inférence. De plus, nous montrons qu'il a une consommation mémoire/temps significativement améliorée et une précision compétitive par rapport aux meilleurs algorithmes de mise à l'échelle GB-SSL les plus récents.La deuxième partie de cette thèse se concentre sur les solutions aux problèmes de perte de régularisation du Laplacien. Pour cette raison, nous proposons un nouveau cadre appelé Graph Diffusion & PCA (GDPCA). Ce cadre combine une analyse en composantes principales modifiée avec la perte supervisée classique et la perte de régularisation laplacienne. GDPCA permet de traiter le cas où la matrice d'adjacence présente des Arêtes binaires et évite la Malédiction de la dimensionnalité. De plus, GDPCA peut être appliqué à des ensembles de données non graphiques, tels que des images, en construisant un graphe de similarité. En outre, nous proposons un cadre qui intègre PageRank SSL dans un modèle génératif (GenPR). GenPR joint l'entraînement de la représentation de l'espace latent des nœuds et la propagation des labels à travers la matrice d'adjacence repondérée par les similarités des nœuds dans l'espace latent. Nous démontrons qu'un modèle génératif peut améliorer la précision et réduire le nombre d'étapes d'itération pour PageRank SSL. En outre, nous montrons comment intégrer MBSA dans le cadre de GenPR pour fournir le régime de formation par lots de GenPR. Enfin, nous proposons un cadre SSL flexible basé sur l'empilement des algorithmes GDPCA et de Zoetrope Genetic Programming dans un nouveau cadre : PaZoe. Ce cadre d'auto-labélisation montre que les algorithmes basés sur les graphes et les algorithmes non basés sur les graphes améliorent conjointement la qualité des prédictions et sont plus performants que chaque composant pris séparément. Nous montrons également que PaZoe surpasse les algorithmes SSL de pointe sur des jeux de données réels. Notez que l'un des ensembles de données a été généré par nos soins, en prenant les données d'un équipement industriel classé pour imiter les moteurs à courant continu pendant leur fonctionnement.