Apprentissage de représentations positionnelles efficaces avec des réseaux de graphes

Les encodages positionnels (PE) sont essentiels pour un apprentissage efficace des représentations de graphes, car ils apportent une conscience de position dans les architectures de transformateurs intrinsèquement indépendantes de la position, tout en augmentant la capacité expressive des réseaux de neurones sur graphes (GNN). Toutefois, concevoir des PEs puissants et efficaces pour les graphes soulève des défis majeurs en raison de l’absence d’ordre canonique des nœuds et de l’échelle des graphes. Dans ce travail, nous identifions quatre propriétés clés que doivent satisfaire les PEs sur graphes : stabilité, puissance expressive, scalabilité et généralité. Nous constatons que les méthodes existantes basées sur les vecteurs propres peinent souvent à satisfaire simultanément ces critères. Pour combler cet écart, nous introduisons PEARL, un nouveau cadre d’encodages positionnels apprenables pour les graphes. Notre principale insight réside dans le fait que les GNNs basés sur le passage de messages agissent comme des applications non linéaires des vecteurs propres, permettant ainsi la conception d’architectures GNN spécifiquement dédiées à la génération de PEs puissants et efficaces. Un défi crucial réside dans l’initialisation des caractéristiques des nœuds de manière à être à la fois expressive et équivariante aux permutations. Nous relevons ce défi en initialisant les GNN avec des entrées aléatoires ou des vecteurs de base standards, ce qui libère toute la puissance expressive des opérations de passage de messages, tout en utilisant des fonctions de pooling statistiques pour préserver l’équivariance aux permutations. Notre analyse démontre que PEARL approche des fonctions équivariantes des vecteurs propres avec une complexité linéaire, tout en établissant rigoureusement sa stabilité et sa haute puissance expressive. Les évaluations expérimentales montrent que PEARL surpasse les versions allégées des méthodes basées sur les vecteurs propres et atteint des performances comparables à celles des méthodes complètes basées sur les vecteurs propres, tout en présentant une complexité réduite d’un ou deux ordres de grandeur.