Laplacian Powers for Graph-Based Semi-Supervised Learning

La thèse

Les techniques d’apprentissage semi-supervisé basées sur des graphes (G-SSL) permettent d’exploiter des données étiquetées et non étiquetées pour construire de meilleurs classifiers. Malgré de nombreuses réussites, leur performances peuvent encore être améliorées, en particulier dans des situations ou` les graphes ont une faible séparabilité de classes ou quand le nombres de sujets supervisés par l’expert est déséquilibrés. Pour aborder ces limitations on introduit une nouvelle méthode pour G-SSL, appel´ee Lγ -PageRank, qui constitue la principal contribution de cette th`ese. Il s’agit d’une g´en´eralisation de l’algorithme PageRank ´a partir de l’utilisation de puissances positives γ de la matrice Laplacienne du graphe. L’étude théorique de Lγ -PageRank montre que (i) pour γ < 1, cela correspond `a une extension de l’algorithme PageRank aux processus de vol de L´evy: ou` les marcheurs aléatoires peuvent désormais relier, en un seul saut, des nœuds distants du graphe; et (ii) pour γ > 1, la classification est effectué sur des graphes signés: ou` les nœuds appartenant `a une même classe ont plus de chances de partager des liens positifs, tandis que les nœuds de classes différentes ont plus de chances d’être connectés avec des arêtes négatifs. Nous montrons l’existence d’une puissance optimale γ qui maximise la performance de classification, pour laquelle une méthode d’estimation automatique est conçue et évaluée. Des expériences sur plusieurs jeux de données montrent que les marcheurs aléatoires de vols de Lévy peuvent améliorer la détection des classes ayant des structures locales complexes, tandis que les graphes signés permet d’améliorer considérablement la séparabilité des données et de surpasser le problème des données étiquetées non équilibrées. Dans un second temps, nous étudions des implémentations efficaces de Lγ -PageRank. Nous proposons des extensions de Power Iteration et Gauss-Southwell pour Lγ -PageRank, qui sont des algorithmes initialement conçues pour calculer efficacement la solution de la méthode PageRank standard. Ensuite, les versions dynamiques de ces algorithmes sont également étendues à Lγ -PageRank, permettant de mettre `a jour la solution de Lγ -PageRank en complexité sub-linéaire lorsque le graphe évolue ou que de nouvelles données arrivent. Pour terminer, nous appliquons Lγ -PageRank dans le contexte du routage Internet. Nous abordons le problème de l’identification des systèmes autonomes (AS) pour des arêtes inter-AS `a partir du réseau d’adresses IP et des registres publics des AS. Des expériences sur des mesures traceroute d’Internet montrent que Lγ -PageRank peut résoudre cette tâche sans erreurs, même lorsqu’il n’y a pas d’exemples étiquetés par l’expert pour la totalité des classes.