Umstrukturierung von Graphen für höhere Homophilie durch adaptive spektrale Clustering

Während eine wachsende Anzahl von Arbeiten neue Graph Neural Networks (GNNs) untersucht, die sowohl auf homophilen als auch auf heterophilen Graphen funktionieren, wurde bisher wenig Forschung betrieben, um klassische GNNs an weniger homophile Graphen anzupassen. Obwohl klassische GNNs bei der Behandlung weniger homophiler Graphen eingeschränkt sind, zeichnen sie sich durch mehrere vorteilhafte Eigenschaften aus, wie Effizienz, Einfachheit und Erklärbarkeit. In dieser Arbeit stellen wir eine neuartige Methode zur Graphenrestrukturierung vor, die in beliebige GNN-Architekturen – einschließlich klassischer GNNs – integriert werden kann, um die Vorteile bestehender GNNs zu nutzen, während ihre Grenzen abgemildert werden. Unser Beitrag ist dreifach: a) Lernen der Gewichte von Pseudoeigenvektoren für eine adaptive spektrale Clusterung, die gut mit bekannten Knotenlabels übereinstimmt; b) Einführung einer neuen, dichtebeachtenden Homophilie-Metrik, die robust gegenüber Label-Unbalancen ist; c) Neukonstruktion der Adjazenzmatrix basierend auf den Ergebnissen der adaptiven spektralen Clusterung, um die Homophilie-Scores zu maximieren. Die experimentellen Ergebnisse zeigen, dass unsere Methode zur Graphenrestrukturierung die Leistung von sechs klassischen GNNs durchschnittlich um 25 % auf weniger homophilen Graphen signifikant steigert. Die verbesserte Leistung ist vergleichbar mit jener von State-of-the-Art-Methoden.