Vom Weisfeiler-Leman-Hierarchie weggehen: Graphenlernen jenseits von Nachrichtenübermittlung

Wir stellen CRaWl, eine neuartige neuronale Netzarchitektur für Graphenlernen, vor. Ähnlich wie Graph-Neuronale Netze (GNNs) aktualisieren CRaWl-Schichten Knotenmerkmale auf einem Graphen und können daher frei mit GNN-Schichten kombiniert oder abwechselnd eingesetzt werden. Im Gegensatz zu Nachrichtenübertragungs-GNNs arbeitet CRaWl jedoch grundlegend anders. CRaWl-Schichten extrahieren und aggregieren Informationen aus Teilgraphen, die entlang zufälliger Wege durch einen Graphen auftreten, unter Verwendung von 1D-Faltungen. Auf diese Weise erfasst CRaWl langreichweitige Wechselwirkungen und berechnet nicht-lokale Merkmale. Als theoretische Grundlage unseres Ansatzes beweisen wir einen Satz, der besagt, dass die Ausdruckskraft von CRaWl mit der des Weisfeiler-Leman-Algorithmus und damit auch mit der von GNNs nicht vergleichbar ist. Das heißt, es gibt Funktionen, die von CRaWl, aber nicht von GNNs, und umgekehrt Funktionen, die von GNNs, aber nicht von CRaWl, ausgedrückt werden können. Dieses Ergebnis gilt auch für höhere Stufen der Weisfeiler-Leman-Hierarchie und damit für hochordentliche GNNs. Empirisch zeigen wir, dass CRaWl state-of-the-art GNN-Architekturen auf einer Vielzahl von Benchmark-Datensätzen für Klassifikation und Regression auf Graphen erreicht.