DiffWire: Induktives Graph-Neuverkabeln mittels der Lovász-Schranke

Graph Neural Networks (GNNs) haben sich als leistungsfähig erwiesen, um graphenbezogene Aufgaben wie Knoten- und Graphklassifikation, Link-Vorhersage sowie Knoten- und Graph-Clustering in vielfältigen Anwendungsbereichen zu lösen. Die meisten GNNs basieren auf einem Message-Passing-Paradigma und werden daher als MPNNs (Message-Passing Neural Networks) bezeichnet. Trotz ihrer vielversprechenden Ergebnisse sind MPNNs jedoch bekanntermaßen anfällig für Probleme wie Over-Smoothing, Over-Squashing und Under-Reaching. In der Literatur wurden Graph-Rewiring und Graph-Pooling als Ansätze vorgeschlagen, um diese Einschränkungen zu überwinden. Allerdings versagen die meisten state-of-the-art-Methoden zum Graph-Rewiring dabei, die globale Topologie des Graphen zu bewahren, sind weder differenzierbar noch induktiv und erfordern zudem die Feinabstimmung von Hyperparametern. In diesem Paper stellen wir DiffWire vor, einen neuartigen Rahmen für Graph-Rewiring in MPNNs, der auf dem Lovász-Schranken beruht, prinzipiengeleitet, vollständig differenzierbar und parameterfrei ist. Der vorgeschlagene Ansatz bietet eine einheitliche Theorie für Graph-Rewiring durch die Einführung zweier neuer, komplementärer Schichten in MPNNs: die CT-Schicht (Commute-Time Layer), die die Durchlaufzeiten lernt und diese als Relevanzfunktion für die Neugewichtung von Kanten nutzt; sowie die GAP-Schicht (Spectral-Gap Layer), die das Spektralintervall optimiert, abhängig von der Netzwerkstruktur und der jeweiligen Aufgabe. Wir validieren empirisch den Wert jeder dieser Schichten separat anhand etablierter Benchmark-Datensätze für Graphklassifikation. Zudem führen wir erste Studien zur Anwendung der CT-Schicht bei homophilen und heterophilen Knotenklassifikationsaufgaben durch. DiffWire verbindet die Lernbarkeit von Durchlaufzeiten mit verwandten Konzepten der Krümmung und eröffnet damit neue Möglichkeiten zur Entwicklung ausdrucksstarkerer MPNNs.