Traitement de l'hétérophylie dans la classification des nœuds avec les réseaux d'état écho graphiques

Les tâches de classification de nœuds dans les graphes sont abordées à l'aide de modèles de passage de messages profonds entièrement entraînés, qui apprennent une hiérarchie de représentations de nœuds par le biais d'aggrégations multiples du voisinage d'un nœud. Bien que cette approche soit efficace sur des graphes présentant un taux élevé d'arêtes intra-classes, elle pose des défis dans le cas inverse, c'est-à-dire l'hétérophilie, où les nœuds appartenant à la même classe sont généralement plus éloignés. Dans les graphes à forte hétérophilie, les représentations lissées basées sur les voisins proches calculées par les modèles convolutifs ne sont plus efficaces. Jusqu'à présent, des variations architecturales dans les modèles de passage de messages pour réduire le lissage excessif ou pour réécrire le graphe d'entrée afin d'améliorer le passage de messages à longue portée ont été proposées. Dans cet article, nous abordons les défis posés par les graphes hétérophiles avec le réseau d'état écho pour graphes (Graph Echo State Network, GESN) pour la classification des nœuds. Le GESN est un modèle de calcul réservoir pour les graphes, où les plongements (embeddings) des nœuds sont calculés récursivement par une fonction de passage de messages non entraînée. Nos expériences montrent que les modèles réservoir peuvent atteindre une meilleure ou une précision comparable par rapport aux modèles profonds entièrement entraînés qui implémentent des variations ad hoc dans le biais architectural ou effectuent une réécriture en tant qu'étape préalable sur le graphe d'entrée, avec une amélioration en termes de compromis entre efficacité et précision. De plus, notre analyse montre que le GESN est capable d'encoder efficacement les relations structurelles d'un nœud du graphe, en montrant une corrélation entre les itérations de la fonction d'emboîtement (embedding) récursive et la distribution des plus courts chemins dans un graphe.