Transitivitätserhaltendes Graphrepräsentationslernen zur Brückenschlagung zwischen lokaler Verknüpfung und rollenbasierter Ähnlichkeit

Methoden des Graph Representation Learning (GRL), wie Graph Neural Networks und Graph Transformer Modelle, wurden erfolgreich zur Analyse von graphstrukturierten Daten eingesetzt, wobei der Fokus hauptsächlich auf Aufgaben der Knotenklassifizierung und Link-Vorhersage lag. Allerdings berücksichtigen die bisherigen Studien in der Regel nur lokale Verbindungen, während sie langreichweitige Verbindungen und die Rollen der Knoten vernachlässigen. In dieser Arbeit schlagen wir Unified Graph Transformer Networks (UGT) vor, die lokale und globale strukturelle Informationen effektiv in vektorbasierte Darstellungen fester Länge integrieren. Zunächst lernen UGTs lokale Strukturen durch die Identifikation lokaler Substrukturen und das Aggregieren von Merkmalen der $k$-Hops-Nachbarschaft jedes Knotens. Anschließend konstruieren wir virtuelle Kanten, die ferne Knoten mit struktureller Ähnlichkeit verbinden, um langreichweitige Abhängigkeiten zu erfassen. Drittens lernen UGTs vereinte Darstellungen durch Selbst-Aufmerksamkeit (self-attention), indem sie den strukturellen Abstand und die $p$-Schritte Übergangswahrscheinlichkeit zwischen Knotenpaaren kodieren. Des Weiteren schlagen wir eine selbstüberwachte Lernaufgabe vor, die effektiv Übergangswahrscheinlichkeiten lernt, um lokale und globale strukturelle Merkmale zu fusionieren, was dann auf andere Downstream-Aufgaben übertragen werden kann. Experimentelle Ergebnisse auf realweltlichen Benchmark-Datensätzen für verschiedene Downstream-Aufgaben zeigten, dass UGT erheblich besser abschnitt als Baseline-Modelle, die aus state-of-the-art-Modellen bestehen. Zudem erreichen UGTs die Ausdruckskraft des dritten Weisfeiler-Lehman Isomorphie-Tests (3d-WL) bei der Unterscheidung nicht-isomorpher Graphenpaare. Der Quellcode ist unter https://github.com/NSLab-CUK/Unified-Graph-Transformer verfügbar.