Link-Vorhersage unter Verwendung von nieder-dimensionalen Knoten-Embeddings: Das Messproblem

Das Lernen von Graphdarstellungen ist eine fundamentale Technik für maschinelles Lernen (ML) in komplexen Netzwerken. Angesichts eines Eingabennetzwerks repräsentieren diese Methoden die Knoten durch nieder-dimensionale reellwertige Vektoren. Diese Vektoren können für eine Vielzahl von nachgelagerten ML-Aufgaben verwendet werden. Wir untersuchen eine der wichtigsten solchen Aufgaben, die Link-Vorhersage. Vieler der aktuellen Literatur zum Lernen von Graphdarstellungen hat bemerkenswerte Erfolge bei der Link-Vorhersage gezeigt. Bei näherer Untersuchung stellen wir fest, dass die Leistung durch die AUC (Fläche unter der Kurve) gemessen wird, die Verzerrungen unterliegt. Da die Wahrheit bei der Link-Vorhersage spärlich ist, entwerfen wir eine knoten-zentrierte Maßzahl für die Leistung, die als VCMPR@k-Diagramme bezeichnet wird. Unter diesem Maß zeigen wir, dass Link-Vorhersager, die Graphdarstellungen verwenden, schlechte Ergebnisse zeigen. Trotz extrem hoher AUC-Werte verpassen die Vorhersager viel von der Wahrheit. Wir identifizieren eine mathematische Verbindung zwischen dieser Leistung, der Spärlichkeit der Wahrheit und der nieder-dimensionalen Geometrie der Knoten-Embeddings. Unter einem formalen theoretischen Rahmen zeigen wir, dass nieder-dimensionale Vektoren die spärliche Wahrheit nicht mit Hilfe von Skalarprodukten (der Standardpraxis in der Literatur) erfassen können. Unsere Ergebnisse stellen bestehende Ergebnisse zur Link-Vorhersage in Frage und stellen eine bedeutende wissenschaftliche Herausforderung für das Lernen von Graphdarstellungen dar. Die VCMPR-Diagramme identifizieren spezifische wissenschaftliche Herausforderungen für die Link-Vorhersage unter Verwendung nieder-dimensionaler Knoten-Embeddings.