Verbesserung von Graph Neural Networks durch das Lernen kontinuierlicher Kantenrichtungen

Graph Neural Networks (GNNs) verwenden traditionell einen Nachrichtenübertragungsmechanismus, der der Diffusion über ungerichtete Graphen ähnelt und häufig zu einer Homogenisierung der Knotenmerkmale und einer Verringerung der diskriminativen Leistungsfähigkeit bei Aufgaben wie der Knotenklassifikation führt. Unser zentrales Insight zur Überwindung dieser Einschränkung besteht darin, den Kanten eines Graphen unscharfe Richtungen zuzuweisen – wobei sich diese kontinuierlich von der Richtung von Knoten $i$ zu Knoten $j$ bis hin zur umgekehrten Richtung verändern können –, sodass Merkmale bevorzugt in einer Richtung zwischen Knoten fließen können und somit eine langreichweitige Informationsübertragung über den gesamten Graphen ermöglicht wird. Zudem führen wir einen neuartigen komplexwertigen Laplace-Operator für gerichtete Graphen mit unscharfen Kanten ein, wobei der Real- und Imaginärteil jeweils den Informationsfluss in entgegengesetzte Richtungen repräsentieren. Unter Verwendung dieses Laplace-Operators schlagen wir einen allgemeinen Rahmen, namens Continuous Edge Direction (CoED) GNN, zur Lernprozesse auf Graphen mit unscharfen Kanten vor und beweisen dessen Ausdruckskraft mittels einer Verallgemeinerung des Weisfeiler-Leman (WL)-Testes zur Graphisomorphie für gerichtete Graphen mit unscharfen Kanten. Unsere Architektur aggregiert Nachbarmerkmale, skaliert mit den gelernten Kantenrichtungen, und verarbeitet die aggregierten Nachrichten aus Eingangs- und Ausgangsnachbarn getrennt neben den Eigenmerkmalen der Knoten. Da kontinuierliche Kantenrichtungen differenzierbar sind, können sie gemeinsam mit den GNN-Parametern mittels gradientenbasierter Optimierung gelernt werden. CoED GNN eignet sich besonders gut für Graphen-Ensemble-Daten, bei denen die Graphstruktur fixiert bleibt, jedoch mehrere Realisierungen der Knotenmerkmale verfügbar sind, wie beispielsweise in Genregulationsnetzwerken, Web-Verbindungsgraphen oder Stromnetzen. Wir zeigen in umfangreichen Experimenten an synthetischen und realen Graphen-Ensemble-Datensätzen, dass das Lernen kontinuierlicher Kantenrichtungen die Leistung sowohl für ungerichtete als auch für gerichtete Graphen im Vergleich zu bestehenden Methoden signifikant verbessert.