Von Sternen zu Subgraphen: Verbesserung jeder GNN mit lokaler Strukturbewusstheit

Nachrichtenübertragungsneuronale Netze (Message Passing Neural Networks, MPNNs) sind eine gängige Art von Graph Neural Networks (GNNs), bei denen die Darstellung jedes Knotens rekursiv durch Aggregation von Darstellungen (Nachrichten) seiner unmittelbaren Nachbarn berechnet wird – vergleichbar mit einem sternförmigen Muster. MPNNs sind aufgrund ihrer Effizienz und Skalierbarkeit besonders attraktiv; ihre Ausdruckskraft ist jedoch durch den 1. Ordnung Weisfeiler-Lehman-Isomorphismustest (1-WL) nach oben begrenzt. In Reaktion darauf haben frühere Arbeiten hochausdrucksstarke Modelle vorgeschlagen, die jedoch oft mit erheblichen Kompromissen hinsichtlich Skalierbarkeit und manchmal auch Generalisierungsleistung verbunden sind. Unser Ansatz positioniert sich zwischen diesen beiden Extremen: Wir stellen einen allgemeinen Rahmen vor, um beliebige MPNNs mit geringem Overhead an Skalierbarkeit deutlich ausdrucksstärker zu machen und gleichzeitig die praktische Leistung signifikant zu verbessern. Dies erreichen wir, indem wir die lokale Aggregation in MPNNs von sternförmigen Mustern auf allgemeine Untergraphmuster (z. B. k-Egonets) erweitern: In unserem Rahmen wird die Darstellung jedes Knotens als Kodierung eines umgebenden induzierten Untergraphen berechnet, anstatt lediglich der Nachbarn (d. h. eines Sterns). Als Untergraphenkodierer wählen wir eine GNN (hauptsächlich MPNNs, um die Skalierbarkeit zu gewährleisten), um einen allgemeinen Rahmen zu konzipieren, der als Wrapper jede GNN aufwerten kann. Wir bezeichnen unseren Ansatz als GNN-AK (GNN as Kernel), da der Rahmen einer convolutionalen neuronalen Netzwerkarchitektur ähnelt, wobei der Kernel durch GNNs ersetzt wird. Theoretisch zeigen wir, dass unser Rahmen strikt stärker als 1- und 2-WL ist und mindestens so stark wie 3-WL ist. Zudem entwickeln wir Untergraph-Sampling-Strategien, die den Speicherbedarf erheblich reduzieren und die Geschwindigkeit verbessern, ohne die Leistung zu beeinträchtigen. Unser Verfahren erreicht neue SOTA-Ergebnisse (state-of-the-art) bei mehreren etablierten graphenbasierten ML-Aufgaben mit deutlichem Abstand: 0,08 MAE auf ZINC, 74,79 % Genauigkeit auf CIFAR10 und 86,887 % auf PATTERN.