DeltaGNN: Graph Neural Network mit Informationsflusskontrolle

Graph Neural Networks (GNNs) sind beliebte tiefgreifende Lernmodelle, die darauf ausgelegt sind, graphenstrukturierte Daten durch rekursive Nachbarschaftsaggregationen im Rahmen des Nachrichtenübertragungsprozesses zu verarbeiten. Bei der Anwendung auf semi-supervised Node Classification ermöglicht der Nachrichtenübertragungsprozess GNNs, kurzreichweitige räumliche Interaktionen zu erfassen, führt jedoch auch zu Problemen wie Over-Smoothing und Over-Squashing. Diese Herausforderungen beeinträchtigen die Ausdruckskraft des Modells und verhindern die Nutzung tieferer Architekturen zur Erfassung von langreichweitigen Knoteninteraktionen (LRIs) innerhalb des Graphen. Bekannte Lösungsansätze für die Detektion von LRIs sind entweder aufgrund hoher zeitlicher Komplexität zu kostspielig für die Verarbeitung großer Graphen oder verlieren ihre Generalisierbarkeit über unterschiedliche Graphstrukturen hinweg. Um diese Einschränkungen zu überwinden, schlagen wir eine Mechanik namens \emph{Information Flow Control} vor, die eine neuartige Zusammenhangsmessung, die sogenannte \emph{Information Flow Score}, nutzt, um Over-Smoothing und Over-Squashing mit linearer rechnerischer Overhead zu bewältigen, unterstützt durch theoretische Begründungen. Schließlich entwerfen wir DeltaGNN, den ersten skalierbaren und generalisierbaren Ansatz zur Detektion sowohl lang- als auch kurzreichweitiger Interaktionen, um die Wirksamkeit unserer Methodik zu belegen. Wir testen unser Modell an zehn realen Datensätzen, die sich in Größe, Topologie, Dichte und Homophilie-Verhältnis unterscheiden, und zeigen eine überlegene Leistung bei vergleichsweise geringer rechnerischer Komplexität. Die Implementierung der vorgeschlagenen Methoden ist öffentlich unter https://github.com/basiralab/DeltaGNN verfügbar.