Toward Degree Bias in Embedding-Based
Knowledge Graph Completion

We first examine the effect that the degree of both the head and tail entities have on KGC performance. We perform our analysis on the FB15K-237 dataset (Toutanova and Chen, 2015), a commonly used benchmark in KGC. Since a KG is a directed graph, we postulate that the direction of an entity’s edges matters. We therefore split the degree of each entity into its in-degree and out-degree. We measure the performance using the mean reciprocal rank (MRR). Note that the degree metrics are calculated using only the training set.

Figure 2(a) displays the results of TuckER (see Section 6.1.4 for more details) on FB15K-237 split by both entities and degree type. From Figure 2(a) we observe that when varying the tail entity degree value, the resulting change in test MRR is significantly larger than when varying the degree of head entities. Furthermore, the MRR increases drastically with the increase of tail in-degree (blue line) while there is a parabolic-like relationship when varying the tail out-degree (orange line). From these observations we can conclude: (1) the degree of the tail entity (i.e. the entity we are trying to predict) has a larger impact on test performance than the degree of the head entity; (2) the tail in-degree features a more distinguishing and apparent relationship with performance than the tail out-degree. Due to the page limitation, the results of ConvE are shown in Appendix A.4, where we have similar observations. These results suggest that KGC displays a degree bias in regards to the in-degree. Next, we will examine which factors of a triple majorly contribute to such degree bias.

In the previous subsection, we have demonstrated the relationship between the entity degree and KGC performance. However, it doesn’t account for the interaction of the entities and relation. Therefore, we further study how the presence of both the relation and entities in a triple together impact the KGC performance. We begin by defining the number of edges that contains the relation $r$ and an entity $v$ as the relation-specific degree:

Based on the results in Section 3.1, we posit that the main indicator of performance is the in-degree of the tail entity. We extend this idea to our definition of relation-specific degree by only counting co-occurrences of an entity and relation when the entity occurs as the tail. For simplicity we refer to this as the tail-relation degree and define it as:

The tail-relation degree can be understood as the number of edges that an entity $v$ shares with $r$, where $v$ occupies the position we are trying to predict (i.e. the tail entity). We further refer to the number of in-edges that $v$ doesn’t share with $r$ as “Other-Tail Relation” degree. This is calculated as the difference between the in-degree of entity $v$ and the tail-relation degree of $v$ and relation $r$, i.e. ${d_{v}^{(in)}-d_{v,r}^{(tail)}}$. It is easy to verify that the in-degree of an entity $v$ is the summation of the tail-relation degree and “Other-Tail Relation” degree. We use Figure 1 as an example of the tail-relation degree. The entity Sweden co-occurs with the relation Has Country on one edge. On that edge, Sweden is the tail entity. Therefore the tail-relation degree of the pair (Sweden, Has Country) is one. We note that a special case of the tail-relation degree is relation-level semantic evidence defined by Li et al. (2022).

Figure 2(b) displays the MRR when varying the value of the tail-relation and “Other-Tail Relation” degree of the tail entity. From the results, we note that while both degree metrics correlate with performance, the performance when the other-tail-relation degree in the range $[0,3)$ is quite high. Since both metrics are highly correlated, it is difficult to determine which metric is more important for the downstream performance. Is the “Other-Tail Relation” the determining factor for performance or is it the tail-relation degree? We therefore check the performance when controlling for one another. Figure 2(c) displays the results when varying the “Other-Tail Relation” degree for specific sub-ranges of the tail-relation degree. From this figure, we see that the tail-relation degree exerts a much larger influence on the KGC performance as there is little variation between bars belonging to the same subset. Rather the tail-relation degree (i.e. the clusters of bars) has a much larger impact. Therefore, we conclude that for a single triple, the main factor of degree bias is the tail-relation degree of the tail entity.

In Section 3.2 we showed that the tail-relation degree of the tail entity strongly correlates with higher performance in KGC. As such we seek to design a method that can increase the performance of such low-degree entity-relation pairs without sacrificing the performance of high-degree pairs.

To solve this problem, we consider data augmentation. Specifically, we seek to create synthetic triples for those entity-relations pairs with a low tail-relation degree. In such a way we are creating more training triples that contain those pairs, thereby “increasing” their degree. For each entity-relation pair with a tail-relation degree less than $\eta$, we add $k$ synthetic samples, which can be formulated as follows:

where $(h,r,v)\in\mathcal{E}_{v,r}$ are the original training triples with the relation $r$ and the tail entity $v$, $(\tilde{h},\tilde{r},\tilde{t})$ is a synthetic sample, and $\tilde{\mathcal{E}}_{v,r}$ is the new set of triples to use during training.

We now present our solution for producing synthetic samples as described in Eq. (3). Inspired by the popular Mixup (Zhang et al., 2018) strategy, we strive to augment the training set by mixing the representations of triples. We draw inspiration from mixup as (1) it is an intuitive and widely used data augmentation method, (2) it is able to promote diversity in the synthetic samples via the randomly drawn value $\lambda$, and (3) it is computationally efficient (see Section 4.4).

We now briefly describe the general mixup algorithm. We denote the representations of two samples as $x_{1}$ and $x_{2}$ and their labels $y_{1}$ and $y_{2}$. Mixup creates a new sample $\tilde{x}$ and label $\tilde{y}$ by combining both the representations and labels via a random value $\lambda\in[0,1]$ drawn from $\lambda\sim\text{Beta}(\alpha,\alpha)$ such that:

We adapt this strategy to our studied problem for a triple $(h,r,t)$ where the tail-relation degree is below a degree threshold, i.e. $d_{t,r}^{(tail)}<\eta$. For such a triple we aim to augment the training set by creating $k$ synthetic samples $\{(\tilde{h},\tilde{r},\tilde{t})\}_{i=1}^{k}$. This is done by mixing the original triple with $k$ other triples $\{(h_{i},r_{i},t_{i})\}_{i=1}^{k}$.

However, directly adopting mixup to KGC leads to some problems: (1) Since each sample doesn’t contain a label (Eq. 5) we are unable to perform label mixing. (2) While standard mixup randomly selects samples to mix with, we may want to utilize a different selection criteria to better enhance those samples with a low tail-relation degree. (3) Since each sample is composed of multiple components (entities and relations) it’s unclear how to mix two samples. We go over these challenges next.

We utilize the binary cross-entropy loss when training each model. The loss is optimized using the Adam optimizer (Kingma and Ba, 2014). We also include a hyperparameter $\beta$ for weighting the loss on the synthetic samples. The loss on a model with parameters $\theta$ is therefore:

where $\mathcal{L}_{KG}$ is the loss on the original KG triples and $\mathcal{L}_{\text{Mix}}$ is the loss on the synthetic samples. The full algorithm is displayed in Algorithm 1. We note that we first pre-train the model before training with KG-Mixup, to obtain the initial entity and relation representations. This is done as it allows us to begin training with stronger entity and relation representations, thereby improving the generated synthetic samples.

We denote the algorithmic complexity of a model $f$ (e.g. ConvE (Dettmers et al., 2018a) or TuckER (Balažević et al., 2019)) for a single sample $e$ as $O(f)$. Assuming we generate $N$ negative samples per training sample, the training complexity of $f$ over a single epoch is:

where $\lvert\mathcal{E}\rvert$ is the number of training samples. In KG-Mixup, in addition to scoring both the positive and negative samples, we also score the synthetic samples created for all samples with a tail-relation degree below a threshold $\eta$. We refer to that set of samples below the degree threshold as $\mathcal{E}_{\text{thresh}}$. We create $k$ synthetic samples per $e\in\mathcal{E}_{\text{thresh}}$. As such, our algorithm scores an additional $k\cdot\lvert\mathcal{E}_{\text{thresh}}\rvert$ samples for a total of $N\cdot\lvert\mathcal{E}\rvert+k\cdot\lvert\mathcal{E}_{\text{thresh}}\rvert$ samples per epoch. Typically the number of negative samples $N>>k$. Both ConvE and TuckER use all possible negative samples per training sample while we find $k=5$ works well. Furthermore, by definition, $\mathcal{E}_{\text{thresh}}\subseteq\mathcal{E}$ rendering $\lvert\mathcal{E}\rvert>>\lvert\mathcal{E}_{\text{thresh}}\rvert$. We can thus conclude that $N\cdot\lvert\mathcal{E}\rvert>>k\cdot\lvert\mathcal{E}_{\text{thresh}}\rvert$. We can therefore express the complexity of KG-Mixup as:

This highlights the efficiency of our algorithm as its complexity is approximately equivalent to the standard training procedure.

In this subsection we evaluate KG-Mixup on multiple benchmarks, comparing its test performance against the baseline methods. We first report the overall performance of each method on the three datasets. We then report the performance for various degree bins. The top results are bolded with the second best underlined. Note that the Standard method refers to training without any additional method to alleviate bias.

Table 1 contains the overall results on each method and dataset. The performance is reported for both ConvE and TuckER. KG-Mixup achieves for the best MRR and Hits@10 on each dataset for ConvE. For TuckER, KG-Mixup further achieves the best MRR on each dataset and the top Hits@10 for two. Note that the other three baseline methods used for alleviating bias, on average, perform poorly. This may be due to their incompatibility with relational structured data where each sample contains multiple components. It suggests that we need dedicated efforts to handle the degree bias in KGC.

We further report the MRR of each method for triples of different tail-relation degree. We split the triples into four degree bins of zero, low, medium and high degree. The range of each bin is [0, 1), [1, 10], [10, 50), and [50, $\infty$), respectively. KG-Mixup achieves a notable increase in performance on low tail-relation degree triples for each dataset and embedding model. KG-Mixup increases the MRR on low degree triples by 9.8% and 5.3% for ConvE and TuckER, respectively, over the standard trained models on the three datasets. In addition to the strong increase in low degree performance, KG-Mixup is also able to retain its performance for high degree triples. The MRR on high tail-relation degree triples degrades, on average, only 1% on ConvE between our method and standard training and actually increases 1% for TuckER. Interestingly, the performance of KG-Mixup on the triples with zero tail-relation degree isn’t as strong as the low degree triples. We argue that such triples are more akin to the zero-shot learning setting and therefore different from the problem we are studying.

Lastly, we further analyzed the improvement of KG-Mixup over standard training by comparing the difference in performance between the two groups via the paired t-test. We found that for the results in Table 1, $5/6$ are statistically significant (p¡0.05). Furthermore, for the performance on low tail-relation degree triples in Table 2, all results ($6/6$) are statistically significant. This gives further justification that our method can improve both overall and low tail-relation degree performance.

In this subsection we empirically investigate the regularization effects of KG-Mixup discussed in Section 5. In Section 5 we demonstrated that KG-Mixup can be formulated as a form of regularization. We further showed that one of the quantities minimized is the difference between the head and relation embeddings of the two samples being mixed, $e_{i}$ and $e_{j}$, such that $(x_{h_{j}}-x_{h_{i}})$ and $(x_{r_{j}}-x_{r_{i}})$. Here $e_{i}$ is the low tail-relation degree sample being augmented and $e_{j}$ is another sample that shares the same tail. We deduce from this that for low tail-relation degree samples, KG-Mixup may cause their head and relation embeddings to be more similar to those of other samples that share same tail. Such a property forms a smoothing effect on the mixed samples, which facilitates a transfer of information to the embeddings of the low tail-relation degree sample.

We investigate this by comparing the head and relation embeddings of all samples that are augmented with all the head and relation embeddings that also share the same tail entity. We denote the set of all samples below some tail-relation degree threshold $\eta$ as $\mathcal{E}_{\text{thresh}}$ and all samples with tail entity $t$ as $\mathcal{E}_{t}$. Furthermore, we refer to all head entities that are connected to a tail $t$ as $\mathcal{H}_{t}=\{h_{j}\;|\;(h_{j},r_{j},t)\in\mathcal{E}_{t}\}$ and all such relations as $\mathcal{R}_{t}=\{r_{j}\>|\>(h_{j},r_{j},t)\in\mathcal{E}_{t}\}$. For each sample $(h_{i},r_{i},t)\in\mathcal{E}_{\text{thresh}}$ we compute the mean euclidean distance between the (1) head embedding $\mathbf{x}_{h_{i}}$ and all $\mathbf{x}_{h_{j}}\in\mathcal{H}_{t}$ and (2) the relation embedding $\mathbf{x}_{r_{i}}$ and all $\mathbf{x}_{r_{j}}\in\mathcal{R}_{t}$. For a single sample $e_{i}$ the mean head and relation embedding distance are given by $h_{\text{dist}}(e_{i})$ and $r_{\text{dist}}(e_{i})$, respectively. Lastly, we take the mean of both the head and relation embeddings mean distances across all $e\in\mathcal{E}_{\text{thresh}}$,

Both $D_{\text{head}}$ and $D_{\text{rel}}$ are shown in Table 3 for models fitted with and without KG-Mixup. We display the results for ConvE on FB15K-237. For both the mean head and relation distances, KG-Mixup produces smaller distances than the standardly-trained model. This aligns with our previous theoretical understanding of the regularization effect of the proposed method: for samples for which we augment during training, their head and relation embeddings are more similar to those embeddings belonging to other samples that share the same tail. This to some extent forms a smoothing effect, which is helpful for learning better representations for the low-degree triplets.

In this subsection we conduct an ablation study of our method on the FB15K-237 dataset using ConvE and TuckER. We ablate both the data augmentation strategy and the use of stochastic weight averaging (SWA) separately to ascertain their effect on performance. We report the overall test MRR and the low tail-relation degree MRR. The results of the study are shown in Table 4. KG-Mixup achieves the best overall performance on both embedding models. Using only our data augmentation strategy leads to an increase in both the low degree and overall performance. On the other hand, while the SWA-only model leads to an increase in overall performance it degrades the low degree performance. We conclude from these observations that data augmentation component of KG-Mixup is vital for improving low degree performance while SWA helps better maintain or even improve performance on the non-low degree triples.

In this subsection we study how varying the number of generated synthetic samples $k$ and the degree threshold $\eta$ affect the performance of KG-Mixup. We consider the values $k\in\{1,5,10,25\}$ and $\eta\in\{2,5,15\}$. We report the MRR for both TuckER and ConvE on the CoDEx-M dataset. Figure 3(a) displays the performance when varying the degree threshold. Both methods peak at a value of $\eta=5$ and perform worst at $\eta=15$. Figure 3(b) reports the MRR when varying the number of synthetic samples generated. Both methods peak early with ConvE actually performing best at $k=1$. Furthermore, generating too many samples harms performance as evidenced by the sharp drop in MRR occurring after $k=5$.

In this subsection we demonstrate that KG-Mixup is effective at improving the calibration of KG embedding models. Model calibration (Guo et al., 2017) is concerned with how well calibrated a models prediction probabilities are with its accuracy. Previous work (Pleiss et al., 2017) have discussed the desirability of calibration to minimize bias between different groups in the data (e.g. samples of differing degree). Other work (Wald et al., 2021) has drawn the connection between out-of-distribution generalization and model calibration, which while not directly applicable to our problem is still desirable. Relevant to our problem, Thulasidasan et al. (2019) has shown that Mixup is effective at calibrating deep models for the tasks of image and text classification. As such, we investigate if KG-Mixup is helpful at calibrating KG embedding models for KGC.

We compared the expected calibration error (see Appendix A.5 for more details) between models trained with KG-Mixup and those without on multiple datasets. We report the calibration in Table 5 for all samples and those with a low tail-relation degree. We find that in every instance KG-Mixup produces a better calibrated model for both ConvE and TuckER. These results suggest another reason for why KG-Mixup works; a well-calibrated model better minimizes the bias between different groups in the data (Pleiss et al., 2017). This is integral for our problem where certain groups of data (i.e. triples with low tail-relation degree) feature bias.