Échelle des transformateurs pour les données structurées graphiques

Graphiquesdans lequel les objets et leurs relations sont représentés comme des nœuds (ou des sommets) et des bords (ou des liens) entre des paires de nœuds, sont omniprésents dans l’informatique et l’apprentissage automatique (ML). Par exemple, les réseaux sociaux, les réseaux routiers et la structure moléculaire et les interactions sont tous des domaines dans lesquels les ensembles de données sous-jacents ont une structure de graphe naturelle. ML peut être utilisé pour apprendre les propriétés des nœuds, des bords ou des graphiques entiers.

Une approche courante de l’apprentissage sur les graphiques est graphique des réseaux de neurones (GNNS), qui fonctionne sur les données du graphique en appliquant une transformation optimisable sur le nœud, le bord et les attributs globaux. La classe la plus typique de GNNS fonctionne via un transfert de messages Framework, par lequel chaque couche agrége la représentation d’un nœud avec celles de ses voisins immédiats.

Récemment, Modèles de transformateur graphique ont émergé comme une alternative populaire aux GNN qui cassent les messages. Ces modèles s’appuient sur le succès de Architectures de transformateur Dans le traitement du langage naturel (PNL), les adaptant aux données structurées des graphiques. Le mécanisme d’attention dans les transformateurs de graphiques peut être modélisé par un graphique d’interaction, dans lequel les bords représentent des paires de nœuds qui s’occupent les uns des autres. Contrairement aux architectures de passage de messages, les transformateurs de graphiques ont un graphique d’interaction séparé du graphique d’entrée. Le graphique d’interaction typique est un graphique complet, ce qui signifie un mécanisme d’attention complet Cela modélise les interactions directes entre toutes les paires de nœuds. Cependant, cela crée des goulots d’étranglement quadratiques de calcul et de mémoire qui limitent l’applicabilité des transformateurs de graphiques en ensembles de données sur de petits graphiques avec au plus quelques milliers de nœuds. Rendre les transformateurs de graphes évolutifs a été considéré comme l’une des directions de recherche les plus importantes dans le domaine (voir Le premier problème ouvert ici).

Un remède naturel consiste à utiliser un clairsemé Graphique d’interaction avec moins d’arêtes. De nombreux transformateurs clairsemés et efficaces ont été proposés Pour éliminer le goulot d’étranglement quadratique pour les séquences, ils ne s’étendent généralement pas aux graphiques de manière fondée.

Dans « EXPHORMER: Transformers clairsemés pour les graphiques», Présenté à ICML 2023nous relevons le défi d’évolutivité en introduisant un cadre d’attention clairsemé pour les transformateurs conçus spécifiquement pour les données du graphique. Le framework Exhormer utilise des graphiques d’expander, un outil puissant de théorie des graphiques spectrauxet est capable d’obtenir de forts résultats empiriques sur une grande variété d’ensembles de données. Notre implémentation d’Exphormer est maintenant disponible sur Github.

Graphiques d’expander

Une idée clé au cœur de l’exphormer est l’utilisation de graphiques d’expanderqui sont des graphiques clairsemés mais bien connectés qui ont des propriétés utiles – 1) La représentation matricielle des graphiques a des propriétés linéaires-algégiques similaires en tant que graphique complet, et 2) ils présentent un mélange rapide de promenades aléatoires, c’est-à-dire un petit nombre d’étapes dans une marche aléatoire à partir de tout nœud de départ. Les expanseurs ont trouvé des applications à divers domaines, tels que les algorithmes, la pseudorandomness, la théorie de la complexité et les codes de correction des erreurs.

Une classe commune de graphiques d’expander est d– Extendants réguliers, dans lesquels il y a d bords de chaque nœud (c’est-à-dire que chaque nœud a un degré d). La qualité d’un graphique d’expander est mesurée par son écart spectralune propriété algébrique de son matrice d’adjacence (Une représentation matricielle du graphique dans lequel les lignes et les colonnes sont indexées par les nœuds et les entrées indiquent si des paires de nœuds sont connectées par un bord). Ceux qui maximisent l’écart spectral sont connus sous le nom Graphiques Ramanujan – ils atteignent une lacune de d – 2 * √ (d-1), qui est essentiellement le meilleur possible parmi d– graphiques réguliers. Un certain nombre de constructions déterministes et randomisées de graphiques Ramanujan ont été proposées au fil des ans pour diverses valeurs de d. Nous utilisons un Construction randomisée de l’expanneur de Friedmanqui produit des graphiques proches-Ramanujan.

Les graphiques de l’expanseur sont au cœur de l’exphormer. Un bon expander est clairsemé mais présente un mélange rapide de promenades aléatoires, ce qui rend sa connectivité globale adaptée à un graphique d’interaction dans un modèle de transformateur de graphe.

Exhormer remplace le graphique d’interaction dense et entièrement connecté d’un transformateur standard avec des bords d’un clairsemé d– Graphique d’expanseur régulier. Intuitivement, les propriétés spectrales d’approximation et de mélange d’un graphique d’expander permettent aux nœuds distants de communiquer entre eux après que l’on empile plusieurs couches d’attention dans une architecture de transformateur de graphe, même si les nœuds peuvent ne pas s’occuper directement les uns des autres. De plus, en veillant à ce que d est constant (indépendamment de la taille du nombre de nœuds), nous obtenons un nombre linéaire de bords dans le graphique d’interaction résultant.

EXPHORMER: Construire un graphique d’interaction clairsemée

Exhormer combine les bords d’expanneur avec le graphique d’entrée et les nœuds virtuels. Plus précisément, le mécanisme d’attention clairsemé d’Exphormer construit un graphique d’interaction composé de trois types de bords:

• Bords du graphique d’entrée (attention locale)
• Bords d’un graphique d’expanneur à degré constant (Expanseur)
• Bords de chaque nœud à un petit ensemble de nœuds virtuels (Attention mondiale)

Exhormer construit un graphique d’interaction en combinant trois types d’arêtes. Le graphique résultant a de bonnes propriétés de connectivité et conserve le biais inductif du graphique de jeu de données d’entrée tout en restant clairsemé.

Chaque composant sert un objectif spécifique: les bords du graphique d’entrée conservent le biais inductif de la structure du graphique d’entrée (qui se perd généralement dans un module d’attention entièrement connecté). Pendant ce temps, les bords d’expanseur permettent une bonne connectivité globale et des propriétés de mélange de marche aléatoires (qui approximativement le graphique complet avec beaucoup moins de bords). Enfin, les nœuds virtuels servent de «puits de mémoire» globaux qui peuvent communiquer directement avec chaque nœud. Bien que cela se traduit par des bords supplémentaires de chaque nœud virtuel égal au nombre de nœuds dans le graphique d’entrée, le graphique résultant est toujours clairsemé. Le degré du graphique d’expanseur et le nombre de nœuds virtuels sont des hyperparamètres à régler pour améliorer les mesures de qualité.

De plus, comme nous utilisons un graphique d’expanseur de degré constant et un petit nombre constant de nœuds virtuels pour l’attention globale, le mécanisme d’attention clairsemé résultant est linéaire dans la taille du graphique d’entrée d’origine, c’est-à-dire qu’il modélise un certain nombre d’interactions directes à l’ordre du nombre total de nœuds et de bords.

Nous montrons en outre qu’Exphormer est aussi expressif que le transformateur dense et obéit aux propriétés d’approximation universelle. En particulier, lorsque le graphique d’attention clairsemé d’Exphormer est augmenté de boucles auto-autonomes (bords reliant un nœud à lui-même), il peut universellement approximativement des fonctions continues (1, 2).

Relation avec les transformateurs clairsemés pour les séquences

Il est intéressant de comparer Exhormer aux méthodes d’attention clairsemées pour les séquences. Peut-être que l’architecture la plus conceptuellement similaire à notre approche est Bigbirdqui construit un graphique d’interaction en combinant différents composants. Bigbird utilise également Erdős-Rényi Modèle de graphique aléatoire pour les composants restants.

L’attention des fenêtres dans Bigbird regarde les jetons entourant un jeton dans une séquence – l’attention locale du quartier à Exhormer peut être considérée comme une généralisation de l’attention des fenêtres sur les graphiques.

Le graphique Erdős-Rényi sur n nœuds, G (n, p)qui relie chaque paire de nœuds indépendamment à la probabilité pfonctionne également comme un graphique d’expander pour p. Cependant, un nombre superlinéaire d’arêtes (ω (n enregistrer n)) est nécessaire pour s’assurer qu’un graphique Erdős-Rényi est connecté, sans parler d’un bon expanseur. D’un autre côté, les expanseurs utilisés dans l’exphormer n’ont qu’un linéaire nombre d’arêtes.

Résultats expérimentaux

Des travaux antérieurs ont montré l’utilisation de modèles complets basés sur des transformateurs de graphes sur des ensembles de données avec des graphiques de taille jusqu’à 5 000 nœuds. Pour évaluer la performance de l’exphormer, nous nous appuyons sur le célèbre Framework GraphGPS (3), qui combine à la fois les transformateurs de passage des messages et les transformateurs de graphiques et réalise des performances de pointe sur un certain nombre d’ensembles de données. Nous montrons que le remplacement de l’attention dense par exphormer pour le composant d’attention du graphique dans le cadre GraphGPS permet d’obtenir des modèles avec des performances comparables ou meilleures, souvent avec moins de paramètres formables.

En outre, Exhormer permet notamment aux architectures de transformateur de graphe de s’étendre bien au-delà des limites de taille de graphique habituelles mentionnées ci-dessus. Exphormer peut évoluer jusqu’à des ensembles de données de plus de 10 000 graphiques de nœuds, tels que le Ensemble de données de coauteuret même au-delà à des graphiques plus grands tels que le bien connu ensemble de données ogbn-arxivun réseau de citations, qui se compose de nœuds de 170 000 et de 1,1 million d’arêtes.

Résultats comparant l’exphormer aux graphgps standard sur les cinq Benchmark graphique à longue portée ensembles de données. Nous notons qu’Exphormer a obtenu des résultats de pointe sur quatre des cinq ensembles de données (Pascalvoc-Sp, Coco-Sp, Peptides-Strucy, PCQM-Contact) au moment de la publication du journal.

Enfin, nous observons que Exphormer, qui crée un graphique de superposition de petit diamètre via des expanseurs, présente la capacité d’apprendre efficacement les dépendances à longue portée. Le Benchmark graphique à longue portée est une suite de cinq ensembles de données d’apprentissage des graphiques conçus pour mesurer la capacité des modèles à capturer des interactions à long terme. Les résultats montrent que les modèles basés sur Exphormer surpassent les modèles GraphGPS standard (qui étaient auparavant à l’état de l’art sur quatre ensembles de données sur cinq au moment de la publication).

Conclusion

Les transformateurs de graphiques sont devenus une architecture importante pour ML qui adapte les transformateurs basés sur des séquences très réussis utilisés dans la PNL pour les données structurées des graphiques. L’évolutivité s’est cependant avérée être un défi majeur pour permettre l’utilisation de transformateurs de graphiques sur des ensembles de données avec de grands graphiques. Dans cet article, nous avons présenté Exphormer, un cadre d’attention clairsemé qui utilise des graphiques d’expander pour améliorer l’évolutivité des transformateurs de graphiques. Il est démontré que l’Exphormer a des propriétés théoriques importantes et présentent de fortes performances empiriques, en particulier sur les ensembles de données où il est crucial d’apprendre des dépendances à longue portée. Pour plus d’informations, nous indiquons le lecteur vers une courte présentation vidéo de ICML 2023.

Remerciements

Nous remercions nos collaborateurs de recherche Hamed Shirzad et Danica J. Sutherland de l’Université de la Colombie-Britannique ainsi que Ali Kemal Sinop de Google Research. Un merci spécial à Tom Small d’avoir créé l’animation utilisée dans ce post.