Knotenverbindungsvorhersage basierend auf Graph-Neuralnetzen

Die Vorhersage von Verbindungen ist ein zentrales Problem für netzwerkstrukturierte Daten. Verbindungsvorhersage-Heuristiken verwenden verschiedene Bewertungsfunktionen, wie gemeinsame Nachbarn und den Katz-Index, um die Wahrscheinlichkeit von Verbindungen zu messen. Aufgrund ihrer Einfachheit, Interpretierbarkeit und bei einigen von ihnen Skalierbarkeit haben sie eine breite praktische Anwendung gefunden. Jedoch basieren alle Heuristiken auf starken Annahmen darüber, wann zwei Knoten wahrscheinlich verbunden sind, was ihre Effektivität in Netzwerken einschränkt, in denen diese Annahmen nicht zutreffen. In diesem Zusammenhang sollte ein vernünftigerer Ansatz darin bestehen, eine geeignete Heuristik aus dem gegebenen Netzwerk zu lernen, anstatt vordefinierte Heuristiken zu verwenden. Durch das Extrahieren eines lokalen Teilgraphen um jede Zielverbindung herum streben wir danach, eine Funktion zu erlernen, die die Muster der Teilgraphen auf die Existenz von Verbindungen abbildet. Dies ermöglicht es uns, automatisch eine 'Heuristik' zu erlernen, die zum aktuellen Netzwerk passt.In dieser Arbeit untersuchen wir dieses Paradigma des Heuristiklernens für die Verbindungsvorhersage. Zunächst entwickeln wir eine neuartige $\gamma$-abklingende Heuristiktheorie. Diese Theorie vereint einen breiten Spektrum an Heuristiken in einem einzigen Rahmen und beweist, dass alle diese Heuristiken aus lokalen Teilgraphen gut angenähert werden können. Unsere Ergebnisse zeigen, dass lokale Teilgraphen reichhaltige Informationen zur Existenz von Verbindungen beinhalten. Zweitens basierend auf der $\gamma$-abklingenden Theorie schlagen wir einen neuen Algorithmus vor, um Heuristiken mit Hilfe eines Graph Neural Networks (GNN) aus lokalen Teilgraphen zu lernen. Die experimentellen Ergebnisse dieses Algorithmus zeigen außergewöhnliche Leistungsfähigkeit und arbeiten konsistent gut bei einer Vielzahl von Problemen.