Wie mächtig sind Graph-Neuronale Netze?

Graph Neural Networks (GNNs) bilden einen effektiven Rahmen für das Lernen von Graphrepräsentationen. GNNs folgen einem Schema der Nachbarschaftsaggregation, bei dem der Repräsentationsvektor eines Knotens durch rekursive Aggregation und Transformation der Repräsentationsvektoren seiner benachbarten Knoten berechnet wird. Es wurden zahlreiche GNN-Varianten vorgeschlagen, die sowohl in Aufgaben zur Klassifikation von Knoten als auch von Graphen stand der Technik entsprechen. Dennoch ist das Verständnis ihrer repräsentativen Eigenschaften und Grenzen begrenzt, obwohl GNNs die Graphrepräsentationslernen revolutioniert haben. In diesem Beitrag stellen wir ein theoretisches Framework vor, um die Ausdrucksstärke von GNNs bei der Erfassung verschiedener Graphstrukturen zu analysieren. Unsere Ergebnisse charakterisieren die diskriminierende Leistungsfähigkeit beliebter GNN-Varianten wie Graph Convolutional Networks und GraphSAGE und zeigen, dass sie bestimmte einfache Graphstrukturen nicht unterscheiden können. Wir entwickeln daraufhin eine einfache Architektur, die beweisbar die ausdrucksstärkste im Bereich der GNNs ist und gleichwertig mächtig wie der Weisfeiler-Lehman-Isomorphietest für Graphen. Wir validieren unsere theoretischen Erkenntnisse empirisch anhand mehrerer Benchmarks zur Graphklassifikation und demonstrieren, dass unser Modell stand der Technik entspricht.