Revisiting Link Prediction: A Data Perspective
This work addresses the challenge of selecting and designing link prediction methods for varied domains, offering incremental insights into data-driven factors to improve evaluation and performance.
The paper tackles the problem of link prediction across diverse datasets by identifying three fundamental factors—local structural, global structural, and feature proximity—and reveals that global proximity is only effective when local proximity is deficient, and feature-structural incompatibility causes GNNs to underperform on feature-dominated edges, leading to practical guidelines for model design and dataset selection.
Link prediction, a fundamental task on graphs, has proven indispensable in various applications, e.g., friend recommendation, protein analysis, and drug interaction prediction. However, since datasets span a multitude of domains, they could have distinct underlying mechanisms of link formation. Evidence in existing literature underscores the absence of a universally best algorithm suitable for all datasets. In this paper, we endeavor to explore principles of link prediction across diverse datasets from a data-centric perspective. We recognize three fundamental factors critical to link prediction: local structural proximity, global structural proximity, and feature proximity. We then unearth relationships among those factors where (i) global structural proximity only shows effectiveness when local structural proximity is deficient. (ii) The incompatibility can be found between feature and structural proximity. Such incompatibility leads to GNNs for Link Prediction (GNN4LP) consistently underperforming on edges where the feature proximity factor dominates. Inspired by these new insights from a data perspective, we offer practical instruction for GNN4LP model design and guidelines for selecting appropriate benchmark datasets for more comprehensive evaluations.