Predictive Multiplicity of Knowledge Graph Embeddings in Link Prediction (2024)

Abstract: Knowledge graph embedding (KGE) models are often used to predict missing links for knowledge graphs (KGs). However, multiple KG embeddings can perform almost equally well for link prediction yet give conflicting predictions for unseen queries. This phenomenon is termed predictive multiplicity in the literature. It poses substantial risks for KGE-based applications in high-stake domains but has been overlooked in KGE research. We define predictive multiplicity in link prediction, introduce evaluation metrics and measure predictive multiplicity for representative KGE methods on commonly used benchmark datasets. Our empirical study reveals significant predictive multiplicity in link prediction, with 8% to 39% testing queries exhibiting conflicting predictions. We address this issue by leveraging voting methods from social choice theory, significantly mitigating conflicts by 66% to 78% in our experiments.

## introduction knowledge graphs (kgs) store factual knowledge of real-world entities and their relationships in the form of triples ⟨head entity, predicate, tail entity⟩. kgs allow for logical reasoning and answering of queries. knowledge graph embeddings (kge) apply machine-learning methods on kgs to provide extra-logical reasoning capabilities exploiting similarities and analogies over knowledge structures @xcite . kge maps entities and predicates into lowdimensional vectors that preserve semantic and structural information of kgs @xcite . the learned embeddings can be applied to downstream tasks like link prediction. given queries in the form of ⟨head entity, predicate, ?⟩ or ⟨?, predicate, tail entity⟩, candidate entities are ranked based on predictive scores provided by kge models. the positive triples are expected to be ranked higher than the negative triples. ## related work although prior studies demonstrate the effectiveness of kge methods in learning complex patterns in kgs @xcite @xcite @xcite @xcite , fewer works focus on their reliability. some studies address uncertainty quantification in kge methods @xcite @xcite , and @xcite explore their adversarial robustness. however, the phenomenon of predictive multiplicity in kge methods has been overlooked. the term model multiplicity was first discussed in @xcite with the term "rashomon effect" referring specifically to the phenomenon where there are different weights learned for linear regression with the same error rate. the term pre-dictive multiplicity was first introduced by @xcite , who explored this behavior in binary classification. @xcite further investigate predictive multiplicity in probabilistic classification. recent studies also provide evidence of predictive multiplicity for deep models @xcite . we initiate an exploration into the predictive multiplicity behavior within the context of kge-based link prediction. while predictive multiplicity offers flexibility in model selection without sacrificing accuracy, diverging predictions can result in unjustifiable final choices. @xcite propose a method to provide consistent predictions. given diverging predictions, they first filter them through a specified confidence threshold and select the final prediction using a majority vote. besides classification problems, predictive multiplicity is also frequently studied for counterfactual explanations @xcite . voting methods can also be seen as ensemble methods. ensemble strategies are employed in kge methods @xcite during the training phase to increase the model performance. joshi and urbani (2022) focuses on enhancing the accuracy of the triple classification task by aggregating predictions from models trained using different kge algorithms. @xcite demonstrate that combining multiple low-dimensional models can outperform a single high-dimensional model. however, our approach aggregates rankings using social choice theory in testing time, aiming to alleviate predictive multiplicity by providing more robust rankings. ## alleviating predictive multiplicity using social choice theory the predictive multiplicity can be alleviated by improving the robustness of the rankings. here, robustness means models with similar performance should also provide similar rankings for testing queries. social choice theory provides a theoretical framework for aggregating individual preferences to determine a group's overall preference @xcite . voting methods from social choice theory can help "smooth out" the randomness in rankings by aggregating individual models @xcite . intuitively, the candidate entities that are constantly ranked high for all models should also be ranked high in final rankings. we next describe ranking aggregation using voting methods with a running example and adapt range voting @xcite to aggregate the predictive scores for the final ranking. ## experiments in this section, we measure the predictive multiplicity in link prediction and apply voting methods ## discussing other influential factors of predictive multiplicity in this section, we discuss additional factors that may influence predictive multiplicity, namely expressiveness and inference patterns. we briefly introduce these two notions and then discuss some observations regarding their relationship to predictive multiplicity. expressiveness. the expressiveness of kge models refers to the ability of modeling an arbitrary kg. following @xcite , we call a kge model fully expressive if we can find a parameter set such that the model predicts all training triples correctly. intuitively, more expressive models can represent more possible embeddings that fit the training graph, thereby allowing more "room" for multiplicity. inference patterns. inference patterns refer to the logic rules used to derive new triples from the observed facts in kgs. the generalization capabilities of kge is usually analysed based on inference patterns that kge model can capture @xcite . for instance, transe can capture inverse patterns, wherein r 1 (x, y ) implies r 2 (y, x), suggesting that the testing triple ⟨e 1 , r 2 , e 2 ⟩ can be correctly predicted with low uncertainty if ⟨e 2 , r 1 , e 1 ⟩ is present in the training graph. theoretically, if the kge method effectively captures the inference patterns for the testing triple, we would expect fewer conflicts from competing models. observations. according to wang et al. (2018, transe rotate rescal distmult complex conve models 0.0 0.1 0.2 0.3 0.4 wn18 wn18rr fb15k fb15k237 the result of transe on fb15k237 appears to be an outlier, marked by its low expressiveness but the highest ambiguity and discrepancy among all kge methods. however, in fb15k237, numerous training triples involve symmetric relations, with testing triples inferrable through symmetric patterns @xcite . since transe fails to represent symmetric triple pair (⟨e 1 , r, e 2 ⟩ and ⟨e 2 , r, e 1 ⟩) simultaneously and lacks the capability to capture symmetric patterns, it may therefore exhibit additional predictive multiplicity. ## conclusion in this paper, we define and measure the predictive multiplicity in link prediction. we measure the predictive multiplicity with empirical ambiguity and discrepancy for representative kge methods on commonly used benchmark datasets. our empirical study reveals significant predictive multiplicity in link prediction, and we demonstrate the effectiveness of applying voting methods. we also discuss several potential factors that could influence predictive multiplicity in link prediction. furthermore, according to proposition 1, predictive multiplicity depends on the accuracy of the baseline model and error tolerance (ϵ). a less accurate baseline model or larger ϵ allows for more predictive multiplicity. given the typically low accuracy in link prediction and the existence of conflicting predictions even when ϵ = 0, a considerable number of conflicting predictions may arise from competing models in practice, posing significant risks in safety-critical domains. hence, we advocate for the measurement, reporting, and mitigation of predictive multiplicity in link prediction within these domains.