Eine Verallgemeinerung von ViT/MLP-Mixer auf Graphen

Graph Neural Networks (GNNs) haben großes Potenzial im Bereich der Graph-Representation-Learning gezeigt. Standard-GNNs definieren ein lokales Message-Passing-Paradigma, das durch mehrfaches Stapeln von Schichten Informationen über den gesamten Graphen hinweg propagiert. Dieses Ansatz leidet jedoch unter zwei wesentlichen Einschränkungen: Über-Squashing und schlechte Langstrecken-Abhängigkeiten, die zwar durch globale Aufmerksamkeit (global attention) adressiert werden können, jedoch die Rechenkomplexität auf quadratische Ordnung erhöhen. In dieser Arbeit stellen wir einen alternativen Ansatz vor, um diese strukturellen Limitationen zu überwinden, indem wir Architekturen aus dem Bereich des Computer Vision, nämlich ViT und MLP-Mixer, nutzen. Wir führen eine neue Klasse von GNNs ein, die Graph ViT/MLP-Mixer genannt werden, und weisen drei zentrale Eigenschaften nach. Erstens erfassen sie Langstrecken-Abhängigkeiten effektiv und reduzieren das Problem des Über-Squashing, wie anhand der Benchmark-Datasets Long Range Graph Benchmark und TreeNeighbourMatch nachgewiesen wird. Zweitens bieten sie eine bessere Geschwindigkeits- und Speichereffizienz mit einer Komplexität, die linear in der Anzahl der Knoten und Kanten ist, und übertrifft damit verwandte Graph-Transformer- und ausdrucksstarke GNN-Modelle. Drittens zeichnen sie sich durch hohe Ausdruckskraft bezüglich Graph-Isomorphismus aus, da sie mindestens 3-WL-nicht-isomorphe Graphen unterscheiden können. Wir testen unsere Architektur an vier simulierten Datensätzen und sieben realen Benchmark-Datenbanken und zeigen überall konkurrenzfähige Ergebnisse. Der Quellcode ist zur Reproduzierbarkeit unter folgender URL verfügbar: \url{https://github.com/XiaoxinHe/Graph-ViT-MLPMixer}.