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

Nicolas Menand, C. SeshadhriProceedings of the National Academy of Sciences 2024 · DOI

TL;DR

This paper reveals a critical flaw in how we evaluate link prediction performance in graph machine learning. While standard metrics like AUC show high scores, a new vertex-centric metric (VCMPR) demonstrates that current low-dimensional embedding methods often fail to capture the true structure of sparse graphs, questioning many existing research findings.

What Problem Does This Paper Address?

Graph representation learning aims to represent nodes in a network as low-dimensional vectors, which are then used for various downstream tasks, including link prediction. Link prediction is the task of predicting whether an edge will form between two nodes in a graph. Many recent studies have reported impressive results in link prediction using these embedding techniques. However, this paper questions the validity of these claims by highlighting a fundamental measurement problem. The authors argue that the commonly used Area Under the Curve (AUC) metric, while popular, is biased for sparse data and can be misleading. They propose that AUC might mask poor performance in real-world scenarios where the ground truth (actual edges) is sparse, leading to an overestimation of model capabilities.

Methods

The core of this paper's contribution lies in introducing a new evaluation metric: VCMPR@k (Vertex-Centric Max Precision Recall at k). Unlike global metrics like AUC, VCMPR@k is a local, per-vertex measure. For each vertex, it assesses how well the top k predicted neighbors align with actual ground truth neighbors. This is calculated as the maximum of precision@k and recall@k for that specific vertex. The authors then plot the distribution of these VCMPR scores across all vertices.

To explain the observed poor performance with VCMPR despite high AUC, the paper develops a formal theoretical framework. This framework connects the sparsity of the ground truth in link prediction with the limitations of low-dimensional embeddings. They mathematically prove that low-dimensional vectors, when used with standard dot product similarity for prediction, cannot effectively capture sparse ground truth. This theoretical result provides a strong foundation for their empirical findings.

Datasets

The authors evaluated their methods on several standard graph datasets, including:

  • BlogCatalog: A social network dataset.
  • Amazon, DBLP: Other social network datasets.
  • ogbl-collab, ogbl-ddi: Datasets from the Open Graph Benchmark (OGB) for link prediction.
  • SBM (Stochastic Block Model): A synthetic graph generated by the authors to create a controlled sparse network.
  • PPI (Protein-Protein Interaction) Networks: Datasets like Bioplex and HI-II-14 were used to explore different graph structures.

Key Insights and Ideas

  • AUC is a misleading metric for sparse link prediction: The paper strongly argues that AUC, while seemingly robust, can give a false sense of high performance when the ground truth is sparse. It can be high even if the model fails to identify most actual links locally.
  • VCMPR reveals hidden weaknesses: The vertex-centric VCMPR metric uncovers significant performance drops that AUC masks, showing that low-dimensional embeddings often struggle to pinpoint actual neighbors for individual nodes.
  • Low-dimensional geometry is a bottleneck: The theoretical framework establishes a mathematical link between the low dimensionality of node embeddings and the inability to capture sparse ground truth using dot products. This suggests a fundamental limitation of current approaches.
  • The "measurement problem" challenges existing research: The findings call into question the reliability of many previous link prediction results that relied solely on AUC.

Key Results

  • High AUC, Low VCMPR: Across multiple datasets and various state-of-the-art embedding methods, the paper consistently shows very high AUC scores (often > 0.8, sometimes > 0.95) alongside surprisingly low average VCMPR scores (often < 0.1, sometimes < 0.05). For example, a method with an AUC of 0.95 might have an average VCMPR@10 of 0.03, indicating that for an average vertex, only about 3% of the top 10 predicted links are actual ground truth links.
  • Theoretical Proof: The authors provide a theorem proving that low-dimensional vectors cannot capture a linear number of "significant pairs" (where two nodes mutually consider each other strong candidates) without having a near-linear rank, which contradicts the goal of low-dimensional embeddings.
  • VCMPR plots highlight vertex-level failures: Visualizing VCMPR distributions (e.g., Fig. 1B, 1C, 2B, 2C) clearly shows that a significant portion of vertices have very low VCMPR scores, indicating widespread local prediction failures.

Limitations and Future Work

  • Limitations: The authors acknowledge that their mathematical analysis might not be as applicable to settings with very low clustering coefficients, such as some protein-protein interaction networks, where AUC scores themselves tend to be lower. They also note that for dense graphs or knowledge discovery tasks where the goal is to predict any new edge rather than edges incident to a specific vertex, VCMPR might not be the most informative metric.
  • Future Work: The paper poses a "VCMPR Challenge" – to design low-dimensional node embeddings that achieve high VCMPR scores for link prediction. They suggest that new approaches might be needed, potentially involving alternative geometries or kernels over low-dimensional vectors, rather than relying solely on dot products. They also highlight the importance of developing better measurement techniques for graph representation learning.

Summary updated

Abstract

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.
BibTeX
@inproceedings{menand2024link,
  author = {Nicolas Menand and C. Seshadhri},
  title = {{Link prediction using low-dimensional node embeddings: The measurement problem}},
  booktitle = {Proceedings of the National Academy of Sciences},
  year = {2024},
  doi = {10.1073/pnas.2312527121},
}
Figure