Globale Homophilie in Graph Neural Networks bei der Begegnung mit Heterophilie finden

Wir untersuchen Graph-Neuronale Netze (Graph Neural Networks, GNNs) auf Graphen mit Heterophilie. Einige existierende Methoden erweitern die Nachbarschaft eines Knotens durch Multi-Hop-Nachbarn, um mehr Knoten mit Homophilie einzubeziehen. Allerdings stellt es eine erhebliche Herausforderung dar, personalisierte Nachbarschaftsgrößen für verschiedene Knoten festzulegen. Darüber hinaus werden andere homophile Knoten, die aus der Nachbarschaft ausgeschlossen sind, bei der Informationsaggregation ignoriert. Um diese Probleme zu lösen, schlagen wir zwei Modelle vor: GloGNN und GloGNN++. Diese Modelle generieren die Einbettung (Embedding) eines Knotens durch Aggregation von Informationen von globalen Knoten im Graphen. In jeder Schicht lernen beide Modelle eine Koeffizientenmatrix, um die Korrelationen zwischen den Knoten zu erfassen, basierend auf der dann die Nachbarschaftsaggregation durchgeführt wird. Die Koeffizientenmatrix erlaubt signierte Werte und wird aus einem Optimierungsproblem abgeleitet, das eine geschlossene Lösung hat. Wir beschleunigen zudem die Nachbarschaftsaggregation und leiten eine lineare Zeitkomplexität her. Theoretisch erklären wir die Effektivität der Modelle durch den Beweis, dass sowohl die Koeffizientenmatrix als auch die generierte Knoteneinbettungsmatrix (Node Embedding Matrix) den gewünschten Gruppierungseffekt haben. Wir führen umfangreiche Experimente durch, um unsere Modelle mit 11 anderen Konkurrenten auf 15 Benchmark-Datensätzen in verschiedenen Bereichen, Größen und Graphenheterophilien zu vergleichen. Die experimentellen Ergebnisse zeigen, dass unsere Methoden überlegene Leistung erzielen und gleichzeitig sehr effizient sind.