Weisfeiler und Leman gehen neuronal: Higher-order Graph Neurale Netze

In den letzten Jahren sind Graph Neural Networks (GNNs) als leistungsfähige neuronale Architekturen hervorgetreten, die Vektordarstellungen von Knoten und Graphen in einer überwachten, end-to-end Weise lernen können. Bislang wurden GNNs nur empirisch evaluiert – mit vielversprechenden Ergebnissen. Die folgende Arbeit untersucht GNNs aus theoretischer Sicht und stellt einen Zusammenhang zu der 1-dimensionalen Weisfeiler-Leman-Graph-Isomorphie-Heuristik (1-WL) her. Wir zeigen, dass GNNs dieselbe Ausdrucksstärke wie die 1-WL in Bezug auf das Unterscheiden nicht-isomorpher (Teil-)Graphen haben. Daher teilen beide Algorithmen auch die gleichen Nachteile. Auf dieser Grundlage schlagen wir eine Verallgemeinerung von GNNs vor, sogenannte k-dimensionale GNNs (k-GNNs), die höhere Ordnungsgraphstrukturen auf mehreren Skalen berücksichtigen können. Diese höheren Ordnungsstrukturen spielen eine entscheidende Rolle bei der Charakterisierung sozialer Netzwerke und Moleküle. Unsere experimentelle Auswertung bestätigt sowohl unsere theoretischen Erkenntnisse als auch, dass höhere Ordnungsinformationen für die Klassifikation und Regression von Graphen nützlich sind.