Selbst-Attention Dual Embedding für Graphen mit Heterophilie

Graph Neural Networks (GNNs) haben sich für die Knotenklassifizierung als äußerst erfolgreich erwiesen. GNNs gehen typischerweise davon aus, dass Graphen homophil sind, d.h., benachbarte Knoten wahrscheinlich der gleichen Klasse angehören. Doch eine Reihe realer Graphen ist heterophil, was zu erheblich geringerer Klassifiziergenauigkeit bei Verwendung herkömmlicher GNNs führt. In dieser Arbeit entwickeln wir ein neuartiges GNN, das sowohl für heterophile als auch für homophile Graphen effektiv ist. Unser Ansatz basiert auf drei zentralen Beobachtungen. Erstens zeigen wir, dass Knotenmerkmale und Graphtopologie in verschiedenen Graphen unterschiedliche Informationsgehalte aufweisen und daher unabhängig kodiert sowie adaptiv priorisiert werden sollten. Zweitens belegen wir, dass die Zulassung negativer Aufmerksamkeitsgewichte bei der Propagation von Topologieinformationen die Genauigkeit verbessert. Drittens zeigen wir, dass asymmetrische Aufmerksamkeitsgewichte zwischen Knoten von Vorteil sind. Wir entwerfen ein GNN, das diese Erkenntnisse durch eine neuartige Selbst-Aufmerksamkeits-Mechanismus nutzt. Wir evaluieren unseren Algorithmus an realen Graphen mit Tausenden bis Millionen von Knoten und zeigen, dass wir gegenüber bestehenden GNNs Ergebnisse auf State-of-the-Art-Niveau erzielen. Zudem analysieren wir die Wirksamkeit der zentralen Komponenten unseres Designs an verschiedenen Graphen.