Raum-Spektrale Graph-Neuronale Netze

Raumliche Nachrichtenübertragung Graph Neural Networks (MPGNNs) werden häufig zur Lernverarbeitung von graphstrukturierten Daten eingesetzt. Allerdings sind die wichtigsten Einschränkungen von l-Schritt-MPGNNs, dass ihr „Rezeptivfeld“ in der Regel auf die l-Hop-Umgebung eines Knotens beschränkt ist und der Informationsaustausch zwischen entfernten Knoten durch Überkomprimierung (over-squashing) begrenzt wird. Aus diesen Einschränkungen heraus schlagen wir Spatio-Spektrale Graph Neural Networks (S$^2$GNNs) vor – ein neues Modellierungsparadigma für Graph Neural Networks (GNNs), das räumlich und spektral parametrisierte Graphfilter synergetisch kombiniert. Die teilweise Parametrisierung von Filtern im Frequenzbereich ermöglicht globale, dennoch effiziente Informationsverbreitung. Wir zeigen, dass S$^2$GNNs Überkomprimierung überwinden und strengere approximations-theoretische Fehlergrenzen als MPGNNs erzielen. Darüber hinaus öffnet das grundlegende Neudenken von Graphfaltungen neue Gestaltungsräume. Zum Beispiel ermöglichen S$^2$GNNs freie positionelle Codierungen, die sie streng ausdrucksstärker machen als den 1-Weisfeiler-Lehman (WL)-Test. Des Weiteren schlagen wir spektral parametrisierte Filter für gerichtete Graphen vor, um allgemeine S$^2$GNNs zu erhalten. S$^2$GNNs übertreffen räumliche MPGNNs, Graph-Transformers und Graph-Umschaltungen, z.B. bei den Benchmark-Aufgaben für Peptid-Langreichweiten, und sind mit dem Stand der Technik in der Sequenzmodellierung wettbewerbsfähig. Auf einer 40 GB GPU skalieren S$^2$GNNs auf Millionen von Knoten.