Zur Äquivalenz zwischen Graphenisomorphie-Test und Funktionenapproximation mit GNNs

Graph Neural Networks (GNNs) haben bei der Verarbeitung von graphstrukturierten Daten erheblichen Erfolg erzielt. Im Zuge dessen hat sich das Interesse an der Untersuchung ihrer Ausdrucksstärke stetig gesteigert. Eine Forschungsrichtung untersucht die Fähigkeit von GNNs, permutationsinvariante Funktionen auf Graphen zu approximieren, während eine andere ihre Leistung als Tests für Graphisomorphie im Fokus hat. Unsere Arbeit verbindet diese beiden Perspektiven und beweist ihre Äquivalenz. Wir entwickeln zudem ein Rahmenwerk zur Ausdrucksstärke von GNNs, das beide Ansichten unter Verwendung der Sprache der σ-Algebra (sigma-algebra) integriert, wodurch wir die Ausdrucksstärke verschiedener Arten von GNNs zusammen mit anderen Tests für Graphisomorphie vergleichen können. Insbesondere beweisen wir, dass das zweitstufige Invariante Graph Network nicht in der Lage ist, nicht-isomorphe reguläre Graphen gleichen Grades zu unterscheiden. Anschließend erweitern wir es zu einer neuen Architektur, dem Ring-GNN, die es schafft, diese Graphen zu unterscheiden und gute Ergebnisse auf realen Datensätzen erzielt.