Pfad-Neuronale Netzwerke: Ausdrucksstarke und genaue Graph-Neuronale Netzwerke

Graph Neural Networks (GNNs) sind in letzter Zeit zum Standardansatz für das Lernen mit graphenstrukturierten Daten geworden. Vorarbeiten haben sowohl das Potenzial als auch die Grenzen dieser Modelle aufgezeigt. Leider zeigte sich, dass herkömmliche GNNs in ihrer Ausdruckskraft eingeschränkt sind: Sie sind bezüglich der Unterscheidung nicht-isomorpher Graphen nicht mächtiger als der 1-dimensionale Weisfeiler-Leman-Algorithmus (1-WL). In diesem Paper stellen wir Path Neural Networks (PathNNs) vor, ein Modell, das Knotendarstellungen durch Aggregation von von Knoten ausgehenden Pfaden aktualisiert. Wir leiten drei verschiedene Varianten des PathNN-Modells ab, die jeweils einzelne kürzeste Pfade, alle kürzesten Pfade sowie alle einfachen Pfade einer Länge bis zu K aggregieren. Wir beweisen, dass zwei dieser Varianten strikt mächtiger als der 1-WL-Algorithmus sind, und validieren unsere theoretischen Ergebnisse experimentell. Wir beobachten, dass PathNNs Paare nicht-isomorpher Graphen unterscheiden können, die vom 1-WL nicht unterscheidbar sind, wobei die ausdrucksstärkste PathNN-Variante sogar Graphenpaare unterscheiden kann, die vom 3-WL-Algorithmus nicht unterscheidbar sind. Die verschiedenen PathNN-Varianten werden zudem auf Datensätzen für Graphenklassifikation und Graphenregression evaluiert, wo sie in den meisten Fällen die Baseline-Methoden übertreffen.