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

Area of Science:

• Machine Learning
• Network Science
• Data Mining

Background:

• Graph representation learning (GRL) is crucial for machine learning (ML) on complex networks, generating low-dimensional vector embeddings for vertices.
• Link prediction is a key downstream task for GRL, with recent studies reporting high performance using metrics like AUC (area under the curve).

Purpose of the Study:

• To investigate biases in standard performance metrics for graph representation learning in link prediction.
• To introduce and utilize a novel vertex-centric performance measure (VCMPR@k plots) to re-evaluate link prediction models.
• To theoretically analyze the limitations of low-dimensional embeddings in capturing sparse network structures.

Main Methods:

• Developed VCMPR@k plots as a vertex-centric evaluation metric for link prediction.
• Empirically evaluated existing graph representation learning methods using both AUC and VCMPR@k plots.
• Established a formal theoretical framework connecting embedding geometry, data sparsity, and prediction performance.

Main Results:

• Standard AUC scores for link prediction are biased and can mask poor performance on sparse ground truth data.
• Link predictors using graph representations demonstrate poor performance when evaluated with VCMPR@k plots, despite high AUC.
• Proved theoretically that low-dimensional embeddings with dot product similarities cannot effectively capture sparse ground truth.

Conclusions:

• Existing evaluations of graph representation learning for link prediction may be unreliable due to metric biases.
• The VCMPR@k plots highlight significant scientific challenges in using low-dimensional node embeddings for link prediction on sparse networks.
• Further research is needed to develop GRL methods that can effectively handle sparse network structures.