Entkopplung von Tiefe und Umfang von Graph Neural Networks

Aktuelle Graph Neural Networks (GNNs) weisen aufgrund der Größe des Graphen und des Modells eine begrenzte Skalierbarkeit auf. Bei großen Graphen führt eine Erhöhung der Modelltiefe oft zu einer exponentiellen Erweiterung des Rezeptionsfelds (d. h. des Umfangs der betrachteten Nachbarschaft). Ab nur wenigen Schichten treten zwei grundlegende Herausforderungen auf: 1. eine abnehmende Ausdruckskraft infolge von Oversmoothing und 2. eine hohe Rechenkosten infolge der Nachbarschaftsexplosion. Wir schlagen ein Entwurfsprinzip vor, das Tiefe und Umfang von GNNs entkoppelt: Um die Repräsentation einer Zielentität (d. h. eines Knotens oder einer Kante) zu generieren, extrahieren wir zunächst einen lokal begrenzten Teilgraphen als beschränkten Umfang und wenden anschließend ein GNN beliebiger Tiefe auf diesen Teilgraphen an. Ein sorgfältig extrahierter Teilgraph besteht aus einer geringen Anzahl kritischer Nachbarn und schließt unwichtige aus. Unabhängig von der Tiefe des GNNs glättet das Modell die lokale Nachbarschaft zu einer informativen Repräsentation, statt den gesamten Graphen zu übermäßig glätten und in „weißes Rauschen“ zu verwandeln. Theoretisch verbessert die Entkopplung die Ausdruckskraft des GNNs aus Sicht der Graphensignalverarbeitung (GCN), der Funktionsapproximation (GraphSAGE) und der topologischen Lernprozesse (GIN). Empirisch erzielt unser Ansatz auf sieben Graphen (mit bis zu 110 Millionen Knoten) und sechs grundlegenden GNN-Architekturen eine signifikante Genauigkeitssteigerung bei einer Reduktion der Rechen- und Hardwarekosten um mehrere Größenordnungen.