III: Small: Revisiting Experimental Evaluation Protocols for Link Prediction in Knowledge Graphs

This project aims to advance the understanding of link prediction in knowledge graphs. Knowledge graphs connect information through links. For example, a person is linked to a movie because they acted in the movie. This allows that person to be linked to other actors in the movie or to link the movie to the actor's other movies. These links create a knowledge graph. Many services like search engines increasingly rely on knowledge graphs, resulting in millions of users interacting with these graphs daily. Knowledge graphs are typically incomplete; that is, there are many missing links between entities that are in fact related. These missing links hinder graphs' effectiveness. For example, a search engine with missing links cannot completely or accurately answer a user question. Link prediction algorithms aim to make knowledge graphs more complete and therefore more accurate. Current evaluation protocols ignore the nature of the links predicted by a link prediction algorithm (interpretability), and rely on datasets crafted using random selection and arbitrary thresholds (bias). The current understanding of benefits and drawbacks of link prediction algorithms is thus quite limited. Without such understanding, the field of link prediction in knowledge graphs cannot properly advance as there is no clear direction on how to do so. Link prediction algorithms commonly rely on machine learning, so they train link prediction models to complete knowledge graphs. There are three main issues hindering our understanding of what link prediction models can accomplish: 1) The lack of methods to interpret a set of link predictions rather than individual predictions, and to quantify model interpretability; 2) The use of random selection and arbitrary thresholds to evaluate link prediction that introduce biases; and 3) The lack of homogeneous comparisons that hinder replicability due to variations in the experimental evaluation protocol. This project proposes the following advances: 1) New methods to compute global interpretations of the link predictions that a model deems correct; 2) New methods to detect and interpret the link prediction rules a model has learned, such as "if actor A acts in movie M, then A is in M's cast;" 3) New interpretation metrics and analyses considering various strategies to generate incorrect knowledge and its expected plausibility; 4) New definitions of anomalies, a.k.a. data redundancy, to understand biases in benchmarking datasets while taking link prediction rules into account; 5) New methods to partition datasets into splits that preserve graph features with statistical guarantees; 6) New statistically sound methods to select subgraphs from real-world knowledge graphs for use as benchmarking datasets; 7) An open-source link prediction framework to reduce barriers when replicating results; and 8) A link prediction evaluation module available through Google Colab, and publicly-available link prediction models to promote open comparisons. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.