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

• 成果类型: Article
• 署名作者: Menand, Nicolas; Seshadhri, C.
• 署名单位: University of Pennsylvania; University of California System; University of California Santa Cruz
• 刊物名称: PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
• ISSN/ISSBN: 0027-14949
• DOI: 10.1073/pnas.2312527121
• 发表日期: 2024-02-20

摘要

Graph representation learning is a fundamental technique for machine learning (ML) 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.