Kanten-Vorschlagsmengen für die Link-Vorhersage

Graphen sind ein verbreiteter Modellansatz für komplexe relationale Daten, wie beispielsweise soziale Netzwerke oder Proteininteraktionen, die sich im Laufe der Zeit verändern können (z. B. durch neue Freundschaften) und zudem verrauscht sein können (z. B. aufgrund unerfasster Interaktionen). Die Kantenvorhersage zielt darauf ab, zukünftige Kanten vorherzusagen oder fehlende Kanten im Graphen zu inferieren, und findet vielfältige Anwendungen in Empfehlungssystemen, experimenteller Planung sowie komplexen Systemen. Obwohl Link-Prediction-Algorithmen stark von der Menge der vorhandenen Kanten abhängen, modifizieren bestehende Ansätze typischerweise die Graphtopologie nicht, um die Leistung zu verbessern. In dieser Arbeit zeigen wir, wie die einfache Hinzufügung einer Kantenmenge – die wir als \emph{Vorschlagsmenge} bezeichnen – als Vorverarbeitungsschritt die Leistung mehrerer Link-Prediction-Algorithmen verbessern kann. Die zugrundeliegende Idee ist, dass, wenn die Kanten der Vorschlagsmenge im Allgemeinen mit der Struktur des Graphen übereinstimmen, die Algorithmen durch diese zusätzliche Information stärker in Richtung der korrekten Kantenprognose geleitet werden; anders ausgedrückt handelt es sich bei der Hinzufügung einer Vorschlagsmenge um eine Signalverstärkung durch Vorverarbeitung. Wir erläutern, wie bestehende Link-Prediction-Algorithmen genutzt werden können, um wirksame Vorschlagsmengen zu generieren, und evaluieren den Ansatz anhand verschiedener synthetischer und empirischer Datensätze. Unser Ergebnis zeigt, dass Vorschlagsmengen die Genauigkeit von Link-Prediction-Algorithmen – sowohl solchen basierend auf Nachbarschaftsheuristiken als auch solchen auf Graph Neural Networks – signifikant verbessern. Der Quellcode ist unter \url{https://github.com/CUAI/Edge-Proposal-Sets} verfügbar.