Amélioration des Graph Transformers grâce à une Encodage Hiérarchique de la Distance Structurale

Les transformateurs de graphes nécessitent des biais inductifs puissants pour produire des scores d’attention significatifs. Toutefois, les méthodes actuelles peinent souvent à capturer des distances étendues, des structures hiérarchiques ou des structures communautaires, qui sont fréquentes dans divers types de graphes tels que les molécules, les réseaux sociaux ou les réseaux de citations. Ce papier présente une méthode de codage structural hiérarchique de distance (HDSE, Hierarchical Distance Structural Encoding) visant à modéliser les distances entre nœuds dans un graphe en mettant l’accent sur sa nature multi-niveaux et hiérarchique. Nous proposons un cadre novateur permettant d’intégrer de manière fluide HDSE dans le mécanisme d’attention des transformateurs de graphes existants, autorisant ainsi son application simultanée avec d’autres encodages de position. Pour appliquer les transformateurs de graphes avec HDSE à des graphes à grande échelle, nous introduisons également une version de haut niveau de HDSE, qui biaise efficacement les transformateurs linéaires vers les hiérarchies du graphe. Nous prouvons théoriquement que HDSE excelle sur les distances de plus court chemin en termes d’expressivité et de généralisation. Expérimentalement, nous démontrons que les transformateurs de graphes intégrant HDSE surpassent les méthodes existantes dans des tâches de classification de graphes, de régression sur 7 jeux de données à niveau de graphe, ainsi que de classification de nœuds sur 11 graphes à grande échelle, y compris des graphes comptant jusqu’à un milliard de nœuds.