Heterophiler Graphen besser an GNN anpassen: Ein Ansatz zur Graphen-Umverkabelung

Graph Neural Networks (GNNs) sind beliebte maschinelle Lernverfahren zur Modellierung von Graphdaten. Viele GNNs erzielen auf homophilen Graphen gute Ergebnisse, zeigen jedoch unzufriedenstellende Leistung auf heterophilen Graphen. In jüngster Zeit wenden sich einige Forscher der Entwicklung von GNNs für heterophile Graphen zu, indem sie den Nachrichtenübertragungsmechanismus anpassen oder den Rezeptionsfeldumfang der Nachrichtenübertragung vergrößern. Im Gegensatz zu bestehenden Arbeiten, die die Probleme heterophiler Graphen ausschließlich aus der Perspektive des Modellentwurfs adressieren, untersuchen wir heterophile Graphen von einer orthogonalen Perspektive, indem wir die Graphstruktur umstrukturieren, um die Heterophilie zu verringern und traditionelle GNNs somit leistungsfähiger zu machen. Durch umfassende empirische Studien und Analysen bestätigen wir das Potenzial von Umstrukturierungsansätzen. Um dieses Potenzial voll auszuschöpfen, schlagen wir eine Methode namens Deep Heterophily Graph Rewiring (DHGR) vor, die Graphen durch Hinzufügen homophiler Kanten und Entfernen heterophiler Kanten umstrukturiert. Die konkrete Art der Umstrukturierung wird durch den Vergleich der Ähnlichkeit der Label-/Merkmalsverteilung benachbarter Knoten bestimmt. Darüber hinaus entwickeln wir eine skalierbare Implementierung von DHGR, um hohe Effizienz zu gewährleisten. DHGR kann einfach als Plug-in-Modul – also als Vorverarbeitungsschritt für Graphen – für beliebige GNNs, sowohl für homophile als auch für heterophile GNNs, eingesetzt werden, um deren Leistung im Task der Knotenklassifizierung zu steigern. So weit wir wissen, ist dies die erste Arbeit, die die Umstrukturierung von Graphen für heterophile Graphen untersucht. Umfangreiche Experimente auf 11 öffentlichen Graph-Datensätzen belegen die Überlegenheit unseres vorgeschlagenen Ansatzes.