Prédiction de Liens Basée sur les Réseaux Neuronaux Graphiques

La prédiction de liens est un problème clé pour les données structurées en réseau. Les heuristiques de prédiction de liens utilisent certaines fonctions de score, comme les voisins communs et l'indice Katz, pour mesurer la probabilité des liens. Elles ont obtenu une utilisation pratique étendue grâce à leur simplicité, leur interprétabilité et, pour certaines d'entre elles, leur scalabilité. Cependant, chaque heuristique repose sur une forte hypothèse concernant le moment où deux nœuds sont susceptibles de se connecter, ce qui limite leur efficacité dans les réseaux où ces hypothèses échouent. À cet égard, une approche plus raisonnable serait d'apprendre une heuristique appropriée à partir d'un réseau donné plutôt que d'utiliser des heuristiques prédéfinies. En extrayant un sous-graphe local autour de chaque lien cible, nous visons à apprendre une fonction qui mappe les motifs du sous-graphe à l'existence du lien, permettant ainsi d'apprendre automatiquement une « heuristique » adaptée au réseau actuel. Dans cet article, nous étudions ce paradigme d'apprentissage heuristique pour la prédiction de liens. Premièrement, nous développons une nouvelle théorie des heuristiques à décroissance $\gamma$. Cette théorie unifie un large éventail d'heuristiques dans un cadre unique et démontre que toutes ces heuristiques peuvent être bien approximées à partir de sous-graphes locaux. Nos résultats montrent que les sous-graphes locaux conservent des informations riches liées à l'existence des liens. Deuxièmement, basés sur la théorie de la décroissance $\gamma$, nous proposons un nouvel algorithme pour apprendre des heuristiques à partir de sous-graphes locaux en utilisant un réseau neuronal graphique (GNN). Ses résultats expérimentaux montrent des performances sans précédent, fonctionnant avec cohérence sur une large gamme de problèmes.