Ensembles de propositions d'arêtes pour la prédiction de liens

Les graphes constituent un modèle courant pour représenter des données relationnelles complexes telles que les réseaux sociaux ou les interactions protéiques, et ces données peuvent évoluer au fil du temps (par exemple, de nouvelles amitiés) tout en étant bruitées (par exemple, des interactions non mesurées). La prédiction de liens vise à anticiper des arêtes futures ou à inférer des arêtes manquantes dans le graphe, et trouve des applications diverses dans les systèmes de recommandation, la conception d’expériences et les systèmes complexes. Bien que les algorithmes de prédiction de liens dépendent fortement de l’ensemble des arêtes présentes dans le graphe, les approches existantes ne modifient généralement pas la topologie du graphe pour améliorer leurs performances. Nous démontrons ici qu’il suffit d’ajouter un ensemble d’arêtes, que nous appelons un ensemble de propositions (proposal set), au graphe en étape de prétraitement afin d’améliorer les performances de plusieurs algorithmes de prédiction de liens. L’idée fondamentale repose sur le fait que si les arêtes de cet ensemble de propositions s’alignent globalement sur la structure du graphe, les algorithmes de prédiction de liens sont davantage guidés vers la prédiction des arêtes correctes ; autrement dit, l’ajout d’un ensemble de propositions constitue une étape de prétraitement renforçant le signal. Nous montrons comment utiliser des algorithmes existants de prédiction de liens pour générer des ensembles de propositions efficaces, et évaluons cette approche sur divers jeux de données synthétiques et empiriques. Nos résultats montrent que les ensembles de propositions améliorent significativement la précision des algorithmes de prédiction de liens, qu’ils reposent sur des heuristiques basées sur le voisinage ou sur des réseaux neuronaux sur graphes. Le code est disponible à l’adresse suivante : \url{https://github.com/CUAI/Edge-Proposal-Sets}.