EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Link prediction using low-dimensional node embeddings: The measurement problem

Nicolas Menand, C Seshadhri iD

Proceedings of the National Academy of Sciences · 20.02.2024 · 121 (8)

DOI: 10.1073/pnas.2312527121 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the National Academy of Sciences, online erschienen am 16.02.2024. Verfasst von Nicolas Menand und 1 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104. Die Arbeit wurde bisher 22-mal zitiert (Crossref) und nennt 47 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF | MPS | Division of Mathematical Sciences (DMS), NSF | CISE | Division of Computing and Communication Foundations (CCF), DOD | USA | AFC | CCDC | Army Research Office (ARO).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Graph representation learning is a fundamental technique for machine learning (ML) on complex networks. Given an input network, these methods represent the vertices by low-dimensional real-valued vectors. These vectors can be used for a multitude of downstream ML tasks. We study one of the most important such task, link prediction. Much of the recent literature on graph representation learning has shown remarkable success in link prediction. On closer investigation, we observe that the performance is measured by the AUC (area under the curve), which suffers biases. Since the ground truth in link prediction is sparse, we design a vertex-centric measure of performance, called the VCMPR@k plots. Under this measure, we show that link predictors using graph representations show poor scores. Despite having extremely high AUC scores, the predictors miss much of the ground truth. We identify a mathematical connection between this performance, the sparsity of the ground truth, and the low-dimensional geometry of the node embeddings. Under a formal theoretical framework, we prove that low-dimensional vectors cannot capture sparse ground truth using dot product similarities (the standard practice in the literature). Our results call into question existing results on link prediction and pose a significant scientific challenge for graph representation learning. The VCMPR plots identify specific scientific challenges for link prediction using low-dimensional node embeddings.

Schlagwörter

Stichwörter der Autor:innen

graph embeddingsgraph representational learninglink predictionlow-dimensional embeddingsmachine learning metrics

Autor:innen und Institutionen

  • Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104.
  • Department of Computer Science, University of California, Santa Cruz, CA 95064.

ORCID-Profile: C Seshadhri

Förderung

  • NSF | MPS | Division of Mathematical Sciences (DMS)
  • NSF | CISE | Division of Computing and Communication Foundations (CCF)
  • DOD | USA | AFC | CCDC | Army Research Office (ARO)

Zitieren

APA

Menand, N., & Seshadhri, C. (2024). Link prediction using low-dimensional node embeddings: The measurement problem. Proceedings of the National Academy of Sciences, 121(8). https://doi.org/10.1073/pnas.2312527121

Vancouver

Menand N, Seshadhri C. Link prediction using low-dimensional node embeddings: The measurement problem. Proceedings of the National Academy of Sciences. 2024;121(8). doi:10.1073/pnas.2312527121

BibTeX
@article{Menand2024,
  author = {Menand, Nicolas and Seshadhri, C},
  title = {Link prediction using low-dimensional node embeddings: The measurement problem},
  journal = {Proceedings of the National Academy of Sciences},
  year = {2024},
  volume = {121},
  number = {8},
  doi = {10.1073/pnas.2312527121}
}
Kostenlos starten →