Skalierungstransformatoren für graphisch strukturierte Daten

Grafikenbei denen Objekte und ihre Beziehungen als Knoten (oder Eckpunkte) und Kanten (oder Verbindungen) zwischen Knotenpaaren dargestellt werden, sind in der Informatik und im maschinellen Lernen (ML) allgegenwärtig. Beispielsweise sind soziale Netzwerke, Straßennetze sowie molekulare Strukturen und Interaktionen allesamt Bereiche, in denen zugrunde liegende Datensätze eine natürliche Graphenstruktur aufweisen. ML kann verwendet werden, um die Eigenschaften von Knoten, Kanten oder ganzen Graphen zu erlernen.

Ein gängiger Ansatz zum Lernen anhand von Graphen ist Graph neuronale Netzwerke (GNNs), die auf Graphendaten arbeiten, indem sie eine optimierbare Transformation auf Knoten-, Kanten- und globale Attribute anwenden. Die typischste Klasse von GNNs arbeitet über ein Nachrichtenübermittlung Framework, bei dem jede Schicht die Darstellung eines Knotens mit denen seiner unmittelbaren Nachbarn aggregiert.

Kürzlich, Graph-Transformator-Modelle haben sich als beliebte Various zu Message-Passing-GNNs herauskristallisiert. Diese Modelle bauen auf dem Erfolg von Transformatorarchitekturen in der Verarbeitung natürlicher Sprache (NLP), indem sie an graphisch strukturierte Daten angepasst werden. Der Aufmerksamkeitsmechanismus in Graphtransformatoren kann durch einen Interaktionsgraphen modelliert werden, in dem Kanten Knotenpaare darstellen, die sich gegenseitig beachten. Im Gegensatz zu Nachrichtenübermittlungsarchitekturen haben Graphtransformatoren einen Interaktionsgraphen, der vom Eingabegraphen getrennt ist. Der typische Interaktionsgraph ist ein vollständiger Graph, was einen vollständigen Aufmerksamkeitsmechanismus bedeutet das direkte Interaktionen zwischen allen Knotenpaaren modelliert. Dies führt jedoch zu quadratischen Rechen- und Speicherengpässen, die die Anwendbarkeit von Graphtransformatoren auf Datensätze in kleinen Graphen mit höchstens einigen tausend Knoten einschränken. Die Skalierbarkeit von Graphtransformatoren gilt als eine der wichtigsten Forschungsrichtungen auf diesem Gebiet (siehe das erste offene Drawback hier).

Ein natürliches Heilmittel ist die Verwendung eines spärlich Interaktionsgraph mit weniger Kanten. Es wurden viele spärliche und effiziente Transformatoren vorgeschlagen um den quadratischen Engpass für Folgen zu beseitigen, lassen sie sich jedoch im Allgemeinen nicht prinzipiell auf Graphen erweitern.

In „Exphormer: Sparse Transformers für Graphen“, präsentiert bei ICML 2023Wir begegnen der Skalierbarkeitsherausforderung, indem wir ein Sparse-Consideration-Framework für Transformatoren einführen, das speziell für Graphendaten entwickelt wurde. Das Exphormer-Framework verwendet Expander-Graphen, ein leistungsstarkes Software aus Spektralgraphentheorieund ist in der Lage, starke empirische Ergebnisse auf einer Vielzahl von Datensätzen zu erzielen. Unsere Implementierung von Exphormer ist jetzt verfügbar auf GitHub.

Expander-Diagramme

Eine zentrale Idee von Exphormer ist die Verwendung von Expander-Diagrammedas sind dünne, aber intestine verbundene Graphen mit einigen nützlichen Eigenschaften – 1) die Matrixdarstellung der Graphen hat ähnliche linear-algebraische Eigenschaften wie ein vollständiger Graph und 2) sie weisen eine schnelle Mischung von Zufallswegen auf, d. h. eine kleine Anzahl von Schritten in einem Zufallsweg von einem beliebigen Startknoten aus reicht aus, um die Konvergenz zu einer „stabilen“ Verteilung auf den Knoten des Graphen sicherzustellen. Expander werden in verschiedenen Bereichen eingesetzt, beispielsweise in Algorithmen, Pseudozufälligkeit, Komplexitätstheorie und Fehlerkorrekturcodes.

Eine häufige Klasse von Expandergraphen sind D-reguläre Expander, in denen es D Kanten von jedem Knoten (d. h. jeder Knoten hat Grad D). Die Qualität eines Expandergraphen wird gemessen an seiner Spektrallückeeine algebraische Eigenschaft seiner Adjazenzmatrix (eine Matrixdarstellung des Graphen, in der Zeilen und Spalten durch Knoten indiziert werden und Einträge angeben, ob Knotenpaare durch eine Kante verbunden sind). Diejenigen, die die spektrale Lücke maximieren, werden als Ramanujan-Grafiken — Sie erreichen eine Lücke von D – 2*√(D-1), was im Wesentlichen die beste Möglichkeit unter D-reguläre Graphen. Im Laufe der Jahre wurden eine Reihe deterministischer und randomisierter Konstruktionen von Ramanujan-Graphen für verschiedene Werte von D. Wir benutzen ein randomisierte Expanderkonstruktion nach Friedmandas nahezu Ramanujan-ähnliche Graphen erzeugt.

Expander-Graphen sind das Herzstück von Exphormer. Ein guter Expander ist spärlich, weist aber dennoch eine schnelle Mischung von Zufallspfaden auf, wodurch seine globale Konnektivität für einen Interaktionsgraphen in einem Graph-Transformer-Modell geeignet ist.

Exphormer ersetzt den dichten, vollständig verbundenen Interaktionsgraphen eines Commonplace-Transformers durch Kanten eines dünnen D-regulärer Expandergraph. Intuitiv ermöglichen die spektralen Approximations- und Mischeigenschaften eines Expandergraphen entfernten Knoten, miteinander zu kommunizieren, nachdem man mehrere Aufmerksamkeitsschichten in einer Graph-Transformer-Architektur gestapelt hat, auch wenn die Knoten sich möglicherweise nicht direkt gegenseitig beachten. Darüber hinaus wird sichergestellt, dass D konstant ist (unabhängig von der Größe der Knotenanzahl), erhalten wir eine lineare Anzahl von Kanten im resultierenden Interaktionsgraphen.

Exphormer: Erstellen eines spärlichen Interaktionsgraphen

Exphormer kombiniert Expanderkanten mit dem Eingabegraphen und virtuellen Knoten. Genauer gesagt erstellt der Sparse-Consideration-Mechanismus von Exphormer einen Interaktionsgraphen, der aus drei Arten von Kanten besteht:

• Kanten aus dem Eingabegraphen (lokale Aufmerksamkeit)
• Kanten aus einem Expandergraphen mit konstantem Grad (Expander Aufmerksamkeit)
• Kanten von jedem Knoten zu einer kleinen Menge virtueller Knoten (weltweite Aufmerksamkeit)

Exphormer erstellt einen Interaktionsgraphen durch die Kombination von drei Kantentypen. Der resultierende Graph weist gute Konnektivitätseigenschaften auf und behält die induktive Tendenz des Graphen des Eingabedatensatzes bei, bleibt aber dennoch dünn besetzt.

Jede Komponente dient einem bestimmten Zweck: Die Kanten des Eingabegraphen behalten die induktive Verzerrung der Eingabegraphenstruktur bei (die in einem vollständig verbundenen Aufmerksamkeitsmodul normalerweise verloren geht). Expanderkanten ermöglichen unterdessen eine gute globale Konnektivität und Random-Stroll-Mixing-Eigenschaften (die den vollständigen Graphen mit weitaus weniger Kanten spektral annähern). Schließlich dienen virtuelle Knoten als globale „Speichersenken“, die direkt mit jedem Knoten kommunizieren können. Dies führt zwar zu zusätzlichen Kanten von jedem virtuellen Knoten, die der Anzahl der Knoten im Eingabegraphen entsprechen, der resultierende Graph ist jedoch immer noch dünn besetzt. Der Grad des Expandergraphen und die Anzahl der virtuellen Knoten sind Hyperparameter, die zur Verbesserung der Qualitätsmetriken angepasst werden müssen.

Da wir außerdem einen Expandergraphen mit konstantem Grad und eine kleine, konstante Anzahl virtueller Knoten für die globale Aufmerksamkeit verwenden, ist der resultierende Mechanismus der spärlichen Aufmerksamkeit linear in der Größe des ursprünglichen Eingabegraphen, d. h. er modelliert eine Anzahl direkter Interaktionen in der Größenordnung der Gesamtzahl der Knoten und Kanten.

Wir zeigen zusätzlich, dass Exphormer genauso ausdrucksstark ist wie der dichte Transformator und universellen Approximationseigenschaften gehorcht. Insbesondere wenn der spärliche Aufmerksamkeitsgraph von Exphormer mit Selbstschleifen (Kanten, die einen Knoten mit sich selbst verbinden) erweitert wird, kann er kontinuierliche Funktionen universell approximieren (1, 2).

Beziehung zu spärlichen Transformatoren für Sequenzen

Es ist interessant, Exphormer mit spärlichen Aufmerksamkeitsmethoden für Sequenzen zu vergleichen. Die Architektur, die unserem Ansatz konzeptionell am ähnlichsten ist, ist vielleicht Großer Vogeldas durch die Kombination verschiedener Komponenten einen Interaktionsgraphen erstellt. BigBird verwendet ebenfalls virtuelle Knoten, aber im Gegensatz zu Exphormer verwendet es Fensteraufmerksamkeit und zufällige Aufmerksamkeit von einem Erdős-Rényi Zufallsgraphenmodell für die verbleibenden Komponenten.

Die Fensteraufmerksamkeit in BigBird betrachtet die Token, die ein Token in einer Sequenz umgeben – die lokale Nachbarschaftsaufmerksamkeit in Exphormer kann als Verallgemeinerung der Fensteraufmerksamkeit auf Graphen betrachtet werden.

Der Erdős-Rényi-Graph auf N Knoten, G(n, p)die jedes Knotenpaar unabhängig mit der Wahrscheinlichkeit verbindet Pfungiert auch als Expander-Graph für entsprechend hohe P. Eine superlineare Anzahl von Kanten (Ω(N Protokoll N)) ist erforderlich, um sicherzustellen, dass ein Erdős-Rényi-Graph zusammenhängend ist, ganz zu schweigen von einem guten Expander. Andererseits haben die in Exphormer verwendeten Expander nur eine linear Anzahl der Kanten.

Experimentelle Ergebnisse

Frühere Arbeiten haben die Verwendung von vollständigen Graph-Transformer-basierten Modellen auf Datensätzen mit Graphen von bis zu 5.000 Knoten gezeigt. Um die Leistung von Exphormer zu bewerten, bauen wir auf dem gefeierten GraphGPS-Framework (3), das sowohl Nachrichtenübermittlung als auch Graphentransformatoren kombiniert und bei einer Reihe von Datensätzen eine Leistung auf dem neuesten Stand der Technik erreicht. Wir zeigen, dass das Ersetzen von dichter Aufmerksamkeit durch Exphormer für die Graphenaufmerksamkeitskomponente im GraphGPS-Framework es ermöglicht, Modelle mit vergleichbarer oder besserer Leistung zu erzielen, oft mit weniger trainierbaren Parametern.

Darüber hinaus ermöglicht Exphormer insbesondere die Skalierung von Graph-Transformer-Architekturen weit über die oben genannten üblichen Graphgrößengrenzen hinaus. Exphormer kann bis zu Datensätzen mit mehr als 10.000 Knotengraphen skaliert werden, wie zum Beispiel Co-Creator-Datensatzund sogar darüber hinaus zu größeren Graphen wie dem bekannten ogbn-arxiv-Datensatzein Zitierungsnetzwerk, das aus 170.000 Knoten und 1,1 Millionen Kanten besteht.

Ergebnisse beim Vergleich von Exphormer mit Commonplace-GraphGPS auf den fünf Benchmark für Langstreckendiagramme Datensätze. Wir weisen darauf hin, dass Exphormer zum Zeitpunkt der Veröffentlichung des Artikels bei vier der fünf Datensätze (PascalVOC-SP, COCO-SP, Peptides-Struct, PCQM-Contact) hochmoderne Ergebnisse erzielte.

Schließlich stellen wir fest, dass Exphormer, das über Expander einen Overlay-Graphen mit kleinem Durchmesser erstellt, die Fähigkeit aufweist, Abhängigkeiten mit großer Reichweite effektiv zu lernen. Benchmark für Langstreckendiagramme ist eine Suite aus fünf Graph-Studying-Datensätzen, die die Fähigkeit von Modellen messen sollen, Interaktionen über große Entfernungen zu erfassen. Die Ergebnisse zeigen, dass auf Exphormer basierende Modelle Commonplace-GraphGPS-Modelle übertreffen (die zum Zeitpunkt der Veröffentlichung bei vier von fünf Datensätzen den neuesten Stand der Technik darstellten).

Abschluss

Graphtransformatoren haben sich als wichtige Architektur für ML herausgestellt, die die sehr erfolgreichen sequenzbasierten Transformatoren, die in NLP verwendet werden, an graphenstrukturierte Daten anpasst. Die Skalierbarkeit hat sich jedoch als große Herausforderung erwiesen, wenn es darum geht, die Verwendung von Graphtransformatoren auf Datensätzen mit großen Graphen zu ermöglichen. In diesem Beitrag haben wir Exphormer vorgestellt, ein Sparse-Consideration-Framework, das Expander-Graphen verwendet, um die Skalierbarkeit von Graphtransformatoren zu verbessern. Exphormer weist wichtige theoretische Eigenschaften auf und zeigt eine starke empirische Leistung, insbesondere bei Datensätzen, bei denen es entscheidend ist, Abhängigkeiten mit großer Reichweite zu lernen. Für weitere Informationen verweisen wir den Leser auf eine kurze Präsentation Video von ICML 2023.

Danksagung

Wir danken unseren Forschungsmitarbeitern Hamed Shirzad und Danica J. Sutherland von der College of British Columbia sowie Ali Kemal Sinop von Google Analysis. Besonderer Dank geht an Tom Small für die Erstellung der in diesem Beitrag verwendeten Animation.