Améliorer l’adaptation des graphes hétérophiles aux GNN : une approche de réécriture de graphe

Les réseaux de neurones graphiques (GNNs) sont des méthodes d’apprentissage automatique largement utilisées pour modéliser des données graphes. De nombreux GNNs obtiennent de bons résultats sur des graphes présentant une homophilie, mais se comportent de manière insatisfaisante sur des graphes hétérophiles. Récemment, certains chercheurs se sont tournés vers la conception de GNNs adaptés aux graphes hétérophiles en ajustant le mécanisme d’échange de messages ou en élargissant le champ réceptif de cet échange. Contrairement aux travaux existants qui tentent de surmonter les limitations liées à l’hétérophilie du point de vue de la conception du modèle, nous proposons d’étudier les graphes hétérophiles sous un angle orthogonal : en réorganisant la structure du graphe afin de réduire l’hétérophilie, et ainsi permettre aux GNNs traditionnels de mieux performer. À travers des études empiriques approfondies et une analyse détaillée, nous validons le potentiel des méthodes de réorganisation. Afin d’exploiter pleinement ce potentiel, nous proposons une méthode nommée Deep Heterophily Graph Rewiring (DHGR), qui réorganise les graphes en ajoutant des arêtes homophiles et en supprimant les arêtes hétérophiles. La manière précise de réorganiser le graphe est déterminée en comparant la similarité des distributions de labels ou de caractéristiques entre les voisins des nœuds. En outre, nous avons conçu une implémentation évolutive pour DHGR afin de garantir une haute efficacité. DHGR peut être facilement intégré comme module plug-in, c’est-à-dire comme étape de prétraitement graphique, pour tout type de GNN — qu’il s’agisse de GNN conçus pour l’homophilie ou pour l’hétérophilie — afin d’améliorer leurs performances sur la tâche de classification de nœuds. À notre connaissance, il s’agit du premier travail à étudier la réorganisation de graphe spécifiquement dans le contexte des graphes hétérophiles. Des expérimentations étendues sur 11 jeux de données publics démontrent clairement l’efficacité supérieure de notre méthode.