Substrukturbewusste Graph Neural Networks

Trotz der erheblichen Fortschritte von Graph Neural Networks (GNNs) im Bereich des Graphenlernens stoßen herkömmliche GNNs auf eine obere Grenze hinsichtlich ihrer Ausdruckskraft, da ihr Propagationsparadigma mit dem ersten Ordnung Weisfeiler-Leman-Test auf Graphisomorphie (1-WL) konsistent ist. Ausgehend von der Erkenntnis, dass sich der ursprüngliche Graph durch Untergraphen leichter unterscheiden lässt, schlagen wir einen neuen neuronalen Netzwerkrahmen namens Substructure Aware Graph Neural Networks (SAGNN) vor, um diese Einschränkungen zu überwinden. Zunächst führen wir einen sogenannten Cut-Untergraph ein, der durch kontinuierliches und selektives Entfernen von Kanten aus dem ursprünglichen Graphen gewonnen werden kann. Anschließend erweitern wir das Random-Walk-Encoding-Paradigma auf die Rückkehrwahrscheinlichkeit eines gewurzelten Knotens im Untergraphen, um strukturelle Informationen zu erfassen, die als Knotenmerkmale verwendet werden, um die Ausdruckskraft der GNNs zu erhöhen. Theoretisch beweisen wir, dass unser Rahmenwerk mächtiger als 1-WL ist und eine überlegene Fähigkeit zur Strukturwahrnehmung aufweist. Umfangreiche Experimente belegen die Wirksamkeit unseres Ansatzes: Wir erreichen state-of-the-art-Leistungen auf einer Vielzahl gut etablierter graphenbasierter Aufgaben, und GNNs, die mit unserem Rahmenwerk ausgestattet sind, verhalten sich fehlerfrei sogar in Graphen, bei denen der 3-WL-Test versagt. Konkret erzielt unser Rahmenwerk eine maximale Leistungssteigerung von 83 % gegenüber Basismodellen und von 32 % gegenüber den vorherigen state-of-the-art-Methoden.