Amélioration des réseaux neuronaux graphes par l’apprentissage de directions d’arêtes continues

Les réseaux de neurones sur graphes (GNNs) utilisent traditionnellement un mécanisme d’échange de messages qui ressemble à une diffusion sur des graphes non orientés, ce qui conduit souvent à une homogénéisation des caractéristiques des nœuds et à une perte de pouvoir discriminant dans des tâches telles que la classification des nœuds. Notre idée centrale pour surmonter cette limitation consiste à attribuer aux arêtes du graphe des directions floues — pouvant varier continûment d’un nœud $i$ vers un nœud $j$ à l’inverse — afin que les caractéristiques puissent s’écouler de préférence dans une seule direction entre deux nœuds, permettant ainsi une transmission d’informations à longue portée à travers le graphe. Nous introduisons également un nouveau laplacien à valeurs complexes pour les graphes orientés possédant des arêtes floues, dans lequel les parties réelle et imaginaire représentent respectivement le flux d’information dans des directions opposées. À l’aide de ce laplacien, nous proposons un cadre général, appelé CoED (Continuous Edge Direction) GNN, pour l’apprentissage sur des graphes à arêtes floues, et établissons ses limites d’expressivité à l’aide d’une généralisation du test d’isomorphisme de graphes de Weisfeiler-Leman (WL) aux graphes orientés avec arêtes floues. Notre architecture combine les caractéristiques des voisins pondérées par les directions d’arêtes apprises, traite séparément les messages provenant des voisins entrants et des voisins sortants, tout en tenant compte des caractéristiques propres aux nœuds. Étant donné que les directions d’arêtes continues sont différentiables, elles peuvent être apprises conjointement avec les poids du GNN via une optimisation basée sur le gradient. Le modèle CoED GNN s’avère particulièrement adapté aux données d’ensembles de graphes, où la structure du graphe reste fixe mais où plusieurs réalisations des caractéristiques des nœuds sont disponibles, comme dans les réseaux de régulation génique, les graphes de connectivité web ou les réseaux électriques. Nous démontrons, à l’aide d’expériences étendues sur des jeux de données synthétiques et réels d’ensembles de graphes, que l’apprentissage des directions d’arêtes continues améliore significativement les performances, tant pour les graphes non orientés que pour les graphes orientés, par rapport aux méthodes existantes.