Diese Arbeit befürwortet die Integration eines Low-Rank Global Attention (LRGA)-Moduls – einer rechen- und speichereffizienten Variante des Dot-Product-Attention (Vaswani et al., 2017) – in Graph Neural Networks (GNNs), um deren Generalisierungsfähigkeit zu verbessern. Um die durch die Integration des LRGA-Moduls erzeugten Generalisierungseigenschaften theoretisch zu quantifizieren, konzentrieren wir uns auf eine spezifische Familie ausdrucksstarker GNNs und zeigen, dass die Erweiterung mit LRGA eine algorithmische Ausrichtung auf einen leistungsfähigen Graph-Isomorphietest ermöglicht, nämlich den 2-Folklore-Weisfeiler-Lehman (2-FWL)-Algorithmus. Genauer: (i) betrachten wir den kürzlich vorgestellten Random Graph Neural Network (RGNN)-Ansatz (Sato et al., 2020) und beweisen, dass er in Wahrscheinlichkeit universell ist; (ii) zeigen wir, dass RGNN mit LRGA über polynomiale Kerne mit dem Update-Schritt des 2-FWL-Algorithmus übereinstimmt; und (iii) schätzen wir die Stichprobengröße der Merkmalsabbildung des Kerns ab, wenn diese mit einem zufällig initialisierten zweilagigen MLP gelernt wird. Aus praktischer Sicht führt die Erweiterung bestehender GNN-Schichten mit LRGA zu state-of-the-art-Ergebnissen in aktuellen GNN-Benchmarks. Schließlich stellen wir fest, dass die Erweiterung verschiedener GNN-Architekturen mit LRGA häufig die Leistungsunterschiede zwischen den Modellen verringert.