Können GNNs Link-Heuristiken lernen? Eine präzise Übersicht und Bewertung von Link-Vorhersagemethoden

Diese Arbeit untersucht die Fähigkeit von Graph Neural Networks (GNNs), verschiedene Arten von Informationen für die Link-Vorhersage zu lernen, und bietet zudem eine kurze Übersicht über bestehende Methoden zur Link-Vorhersage. Unsere Analyse zeigt, dass GNNs strukturelle Informationen bezüglich der Anzahl gemeinsamer Nachbarn zweier Knoten nicht effektiv erlernen können, hauptsächlich aufgrund der Natur der mengenbasierten Pooling-Strategie im Aggregationsprozess der Nachbarschaft. Zudem deuten unsere umfangreichen Experimente darauf hin, dass trainierbare Knoten-Embeddings die Leistung von GNN-basierten Modellen zur Link-Vorhersage verbessern können. Insbesondere beobachten wir, dass die Verbesserung umso größer ist, je dichter der Graph ist. Wir erklären dies mit den Eigenschaften der Knoten-Embeddings, bei denen der Zustand jedes Verbindungspaares in die Embeddings der Knoten kodiert werden kann, die an der Nachbarschaftsaggregation der beiden Knoten dieses Verbindungspaares beteiligt sind. In dichteren Graphen hat jeder Knoten mehr Gelegenheiten, an der Nachbarschaftsaggregation anderer Knoten teilzunehmen und die Zustände mehrerer Verbindungspaare in sein Embedding zu kodieren, wodurch bessere Knoten-Embeddings für die Link-Vorhersage entstehen. Abschließend zeigen wir, dass die Erkenntnisse aus unserer Forschung wichtige Implikationen für die Identifizierung der Grenzen bestehender Methoden zur Link-Vorhersage haben, was die zukünftige Entwicklung robusterer Algorithmen leiten könnte.