Approche hybride basée sur l'apprentissage automatique pour la réduction de graphes
Résumé
Récemment, l'arrivée de l'apprentissage profond sur les graphes a
permis d'obtenir des résultats fructueux sur plusieurs problèmes d'optimisation sur les graphes. Dans ce papier, nous nous intéressons à la réduction de graphes en utilisant des techniques d'apprentissage automatique. La réduction de graphes a pour objectif d'obtenir des graphes plus simples ou plus petits en agrégeant les noeuds ou les arêtes similaires, sans ou avec perte d'information, ou en sparsifiant le graphe en enlevant des arêtes non significatives pour l'application considérée. Nous proposons une méthode hybride qui sparsifie le graphe dans un premier temps, puis dans un second temps, groupe les noeuds, tout en préservant les distances dans le graphe. Pour cela, nous nous appuyons sur une méthode d'apprentissage automatique par renforcement. Pour valider notre approche, nous effectuons une comparaison avec les méthodes déjà existantes.