Positive-Unlabeled Learning with Adversarial Data Augmentation for Knowledge Graph Completion

1 Introduction

Knowledge graphs (KG) are of great importance in a variety of real-world applications, such as question answering, recommender systems, and drug discovery [Rossi et al., 2021]. However, it is well-known that even the state-of-the-art KGs still suffer from incompleteness, i.e., many true facts are missing. For example, more than 66% of person entries in Freebase and DBpedia lack their birthplaces [Krompaß et al., 2015]. Such an issue limits the practical applications and has motivated considerable research efforts in the task of knowledge graph completion (KGC) that aims to predict the most plausible missing facts to complete a KG. Formally, a KG is commonly represented as a set of triples in the form of (head entity, relation, tail entity). In this work, we particularly study the problem of predicting the plausibility of each missing head (tail) entity given the relation and the tail (head) entity in a triple, and selecting the most plausible missing head (tail) entities to complete a KG.

∗Equal contributions.

†Corresponding author.

Recent years have witnessed increasing interest in the KGC task [Sun et al., 2018; Shikhar et al., 2020; Li et al., 2021]. However, there are common key issues that remain unsolved. (i) The false negative issue. Existing KGC methods require negative samples for model training, and most of them obtain negative samples from nonexistent triples in a KG [Rossi et al., 2021]. However, the nonexistent triples are not necessarily false facts, and some of the nonexistent triples would be added into a KG as true facts with knowledge graph expansion and enrichment. As the example shown in Fig. 1, (Joseph, has job, Professor) and (Joseph, has job, Data Scientist) are true facts in a KG, and it is easy to find that (Joseph, has job, Researcher) is a potential true fact; however, (Joseph, has job, Researcher) is likely to be selected as a negative sample, as it is currently a nonexistent triple. (ii) The data sparsity issue. True facts that can be leveraged as positive samples to guide the training account for only a small portion, e.g., 0.00047% of all possible triples in WN18RR [Dettmers et al., 2018] and 0.00054% in FB15k-237 [Toutanova et al., 2015]. Such extremely sparse positive training data could engender unsatisfactory generalization performance for correctly inferring the missing triples [Pujara et al., 2017].

To address the above issues, we propose a novel method resorting to positive-unlabeled learning with adversarial data augmentation (PUDA) for KGC. First, true facts in a KG can be regarded as positive triples, yet the plausibility of nonexistent triples including potential true facts and real false facts is unknown. In this work, we treat each nonexistent triple as an unlabeled triple rather than a negative triple used in the most of existing works [Rossi et al., 2021]. Inspired by positive-unlabeled (PU) learning [Bekker and Davis, 2020] that is designed for the learning scenarios where only positive and unlabeled data are given, we propose a novel KGC model resorting to PU learning to circumvent the impact of false negative issue. However, PU learning is originally designed for binary-classification that predicts the exact score of each triple, which is more difficult than necessary for the goal of ranking out the most plausible missing triples desired in KGC task. Therefore, we reformulate the PU risk estimator [Kiryo et al., 2017] and tailor the ordinary PU learning to KGC task. Second, as positive triples are extremely rare in KGs, we attempt to augment the positive triples to improve the KGC performance of generalization. Inspired by the recent progress of adversarial training [Mariani et al., 2018] and its capability of generating synthetic data, we develop an adversarial data augmentation strategy to address the data sparsity issue. However, not all the generated synthetic triples are plausible enough to be regarded as positive triples. Therefore, it is more reasonable to treat the synthetic triples as unlabeled triples, which could be potential positive or true negative triples. By unifying the adversarial training with the PU risk estimator under PU minimax game, the data sparsity issue would be well mitigated. We summarize the main contributions of this work as: 1) We propose a novel KGC method to circumvent the impact of the false negative issue by resorting to PU learning, and tailoring the ordinary PU risk estimator for KGC task; 2) We design a data augmentation strategy by unifying the idea of adversarial training and PU learning under a PU minimax game to alleviate the data sparity issue. 3) We conduct extensive experimental evaluations and provide in-depth analysis on real-world benchmark datasets to demonstrate the effectiveness and compatibility of the proposed method.

2 RelatedWork

Knowledge Graph Completion. A major line of KGC study focuses on learning distributed representations for entities and relations in KG [Zhang et al., 2020]. (i) Tensor decomposition methods assume the score of a triple can be decomposed into several tensors [Yang et al., 2014; Trouillon et al., 2017; Kazemi and Poole, 2018]; (ii) Geometric methods regard a relation as the translation from a head entity to a tail entity [Bordes et al., 2013; Zhang et al., 2019a; Sun et al., 2018]; (iii) Deep learning methods [Nguyen et al., 2018; Dettmers et al., 2018; Shikhar et al., 2020] utilize deep neural networks to embed KGs. These works mainly focus on designing and learning a scoring function to predict the plausibility of a triple. However, our primary focus is beyond the design of the scoring function, aiming at proposing a general KGC framework to address the false negative issue and data sparsity issue.

Positive-Unlabeled (PU) Learning. PU learning is a learning paradigm for the setting where a learner can only access to positive and unlabeled data, and the unlabeled data include both positive and negative samples [Bekker and Davis, 2020]. PU learning roughly includes: (1) two-step solutions [Liu et al., 2002; He et al., 2018], (2) methods that consider the unlabeled samples as negative samples with label noise [Shi et al., 2018] (3) unbiased risk estimation based methods [Du Plessis et al., 2014; Christoffel et al., 2016; Xu and Denil, 2019]. Our work is related to the unbiased risk estimator that minimize the expected classification risk to obtain an empirical risk minimizer. However, the original PU risk estimator that based on pointwise ranking loss needs to be specially tailored for our KGC task based on pairwise ranking.

Adversarial Training. The adversarial training paradigm [Goodfellow et al., 2014] that trains a generator and a discriminator by playing an adversarial minimax game is originally proposed to generate samples in a continuous space such as images. Several adversarial training methods [Mariani et al., 2018] have been proposed for data augmentation in all classes, rather than specially augmenting positive and unlabeled data. A few works [Wang et al., 2017; Cai and Wang, 2018; Wang et al., 2018] utilize adversarial training for the KGC task. These approaches focus on selecting negative samples that are more useful for model training, while our proposed method generates synthetic samples for data augmentation.

3 Preliminaries

Problem Formulation. A KG is formulated as K = {⟨h, r, t⟩} ⊆ E ×R× E, where h, r, t denote the head entity, relation, and tail entity in triple ⟨h, r, t⟩, respectively, E and R refer to the entity set and the relation set in K. |K| denotes the total number of triples in K. The KGC problem is to infer the most plausible missing triple from {⟨h, r, t⟩|t ∈ E ∧ ⟨h, r, t⟩ /∈ K} (or {⟨h, r, t⟩|h ∈ E ∧ ⟨h, r, t⟩ /∈ K}) for each incomplete triple ⟨h, r, ?⟩ (or ⟨?, r, t⟩), e.g., reporting the top-k plausible missing triples.

Scoring Function. The core of KGC is to learn a scoring function ϕ(s;Θ) to precisely estimate the plausibility of any triple s = ⟨h, r, t⟩, where Θ represents the learnable parameters of an arbitrary scoring function. The main focus of this work is to design a novel framework for KGC to solve the aforementioned two issues rather than developing a novel scoring function. Therefore, we employ the basic yet effective DistMult [Yang et al., 2014] as scoring function. Given the embedding dimension d, head entity embedding h ∈ Rd , relation embedding r ∈ Rd×d , and tail embedding t ∈ Rd , the scoring function is then computed as a bilinear product:

where symbol × denotes matrix product, r is forced to be a diagonal matrix, Θ = {Ee, Er} represents learnable parameters, Ee ∈ R|E|×d and Er ∈ R|R|×d×d denote the embedding matrices of entities and relations, respectively.

PU Triple Preparation. The widely used loss functions [Cai and Wang, 2018] in KGC always require positive triples and negative triples for optimization. The true facts in K can be naturally regarded as positive triples. To obtain negative triples, the common practice [Rossi et al., 2021] is to corrupt hp or tp in a positive triple ⟨hp , rp , tp ⟩. Here we only describe the case of tail corruption; head corruption is defined analogously. Specifically, let spi = ⟨hpi , rp i , tpi ⟩ be the ith positive triple in K. For a given spi , we can obtain N corrupted triples S u i = {⟨hpi , rp i , tuij ⟩}N by sampling N entities {tui1 , ..., tuiN } from {t|t ∈ E ∧ ⟨hpi , rp i , t⟩ /∈ K} and replacing tpi by each sampled entity tuij . Note that the corrupted triples may be potential true facts as illustrated in Fig.1 and lead to the false negative issue. Therefore, unlike previous work that treats the corrupted triples as negative [Rossi et al., 2021], we regard each triple in S u i as an unlabeled triple.

Data Augmentation. Besides the positive and unlabeled triples, we also generate a set of synthetic triples for data augmentation. Specifically, for a positive triple spi = ⟨hpi , rp i , tpi ⟩, we generate M synthetic triples S ∗ i = {⟨hpi , rp i , t∗im⟩}M by generating M synthetic entities {t∗i1 , ...., t∗iM } via adversarial training and replacing tpi by each synthetic entity t∗im, where t∗im /∈ E. Similarly, the head entity can be replaced in the same way. Note that not all the generated synthetic triples are plausible enough to be regarded as positive triples. Therefore, we treat each triple in S ∗ i as an unlabeled triple as well.

4 The ProposedMethod

As Figure 2 shown, our proposed method includes two main components. One is the positive-unlabeled (PU) learning for KGC that aims to circumvent the impact of false negative issue. The other is adversarial data augmentation for data sparsity issue. They are unified under a PU minimax game.

4.1 Positive-Unlabeled Learning for KGC

Motivated by the aforementioned false negative issue, we aim to design a learning strategy to circumvent the impact of false negative samples. Since KGs only contain true facts (positive triples), the real labels of all nonexistent triples which could be positive or negative are unknown for KGC models. Inspired by PU learning that is designed for the learning scenario where only positive data and unlabeled data are given, we denote the nonexistent triples as unlabeled triples, and propose a novel KGC model resorting to PU learning to avoid negative samples. However, prevailing PU learning methods focus on binary-classification, while the final goal of KGC is to provide an optimal ordering of missing triples and selecting the most plausible ones to complete a KG. The binary classification in fact takes a pointwise ranking loss function, which is a more difficult problem than necessary. Pairwise ranking approaches work better in practice than pointwise approaches because predicting relative order is closer to the nature of ranking than predicting class label or relevance score, especially for information retrieval and recommendation tasks [Rendle et al., 2009; Melnikov et al., 2016; Guo et al., 2020]. Therefore, PU learning methods need to be specially tailored for the KGC task with pairwise ranking loss. In this section, we first briefly introduce the PU risk estimator in the classification scenario, then we tailor the PU risk estimator for KGC task.

PU Classification Risk Estimator. In positive-negative learning, the empirical risk estimator ˆRpn(ψ) w.r.t. a positive class prior πp = 1 - πn (the percentage of positive samples in all possible samples) is defined as:

where ψ(·) is an arbitrary decision function, ˆR+p (ψ) is the expected risk of predicting positive samples as positive (+), and ˆR-n (ψ) is the expected risk of predicting negative samples as negative (-). In positive-unlabeled (PU) learning, due to the absence of negative samples, we cannot directly estimate ˆR-n (ψ). Following [Du Plessis et al., 2015], we define πn ˆR-n (ψ) as:πn ˆR-n (ψ) = ˆR-u (ψ) - πp ˆR-p (ψ), (3)

where ˆR-u (ψ) is the expected risk of predicting unlabeled samples as negative (-) and ˆR-p (ψ) is the expected risk of predicting positive samples as negative (-). By replacing the second term in Eq.(2) with Eq.(3), the empirical risk estimator can be defined as:

1/1 Most recent works on risk estimation based PU learning [Kiryo et al., 2017; Akujuobi et al., 2020] note that the model tends to suffer from overfitting on the training data when the decision function ψ is complex. Thus, a non-negative risk estimator [Kiryo et al., 2017] is proposed to alleviate the overfitting problem:

ˆR(ψ) should be minimized to learn the function ψ. Note that by introducing the PU risk estimator in Eq. (4) and Eq. (5), we can circumvent the impact of the false negative issue by using unlabeled samples instead of negative samples.

PU Risk Estimator for KGC. To define the PU risk estimator for the KGC problem, we first define the scoring function in Eq.(1) as the arbitrary decision function ψ(·) to predict the plausibility of any triple:

We replace ψ(·) by ϕ(·) in the later descriptions. In the scenario of KGC, the key challenge is to give suitable definitions to the risks ˆR+p (ϕ), ˆR-p (ϕ), and ˆR-u (ϕ). Prevailing PU learning methods [Du Plessis et al., 2014; Kiryo et al., 2017] define the above risks for binary classification as follows:

where lnσ(·) is the log-sigmoid function and is a commonly used function for risk estimator [Kiryo et al., 2017], and suij ∈ S u i denotes an unlabeled triple w.r.t. spi . The output values of the score function ϕ(s; Θ) can differentiate the positive triples from the unlabeled triples. However, it is unnecessarily hard to push σ(ϕ(s;Θ)) to be 1 (0) for all positive (unlabeled) triples in a KGC task. It is easier and more desirable to just push positive triples to be ranked higher than the unlabeled triples.

Let >spi be the optimal ordering of a given positive triple spi and unlabeled triples S u i , i.e., spi is ranked higher than every triple in S u i . Without loss of generality, we can assume that all unlabeled triples in S u i are independent given that they have the same head and relation (or the same tail and relation) from the positive triple. The optimization of Θ towards the optimal ordering >spi can then be formulated on each pair of triples (spi , suij ) [Rendle et al., 2009] as follows:

where maximizing the difference between ϕ(spi ;Θ) and ϕ(suij ;Θ) would push the positive triple spi to rank higher than all unlabeled triples in S u i .

The lack of pairwise triples in Eq.(9) hinders the introduction of pairwise comparison. It focuses only on minimizing the risk of predicting ϕ(suij ;Θ) as a too large value. To incorporate the pairwise orderings, we can replace lnσ(-ϕ(suij ;Θ)) in Eq.(9) by lnσ(ϕ(spi ;Θ) - ϕ(suij ;Θ)). That is, measuring the likelihood of suij being a small value is replaced by measuring the likelihood of suij being just smaller than its positive counterpart spi . Then, Eq.(9) becomes

where ˆ ru|i (ϕ) is the risk of obtaining a non-optimal ordering of the positive triple spi and the unlabeled triples S u i . It is worth noting that Eq.(11) makes no penalty on the ranking relations among unlabeled triples, unlike Eq.(9) which targets to score all unlabeled triples to be the same low values. Hence, Eq.(11) allows some unlabeled triples to be ranked higher than other unlabeled triples, as long as all unlabeled triples are ranked lower than the positive triple. Those higherranked unlabeled triples have the room to be promoted as positive triples. Combining Eq.(5) with Eq.(7), Eq.(8), and Eq.(11), we have the well defined ˆR(ϕ) for KGC problem, which embeds pairwise ranking objective in the PU risk estimator to deal with the false negative issue.

Further Discussion. The superiority of our proposed PU learning for KGC is that it can handle the false negative issue, which existing pairwise ranking loss based methods still suffer from, because they simply treat all unlabeled data as negative [Rossi et al., 2021]. In other words, pairwise ranking loss aims to rank positive triples ahead unlabeled triples. However, unlabeled data contain both positive and negative samples. Positive triples thus should not be ranked ahead the false negative (positive) triples within unlabeled data. Recent research shows that the bias can be canceled by particular PU optimization objectives [Kiryo et al., 2017]. Specifically, Eq.(5) is the PU objective and Eq.(8) serves as the term to cancel the bias. They reflect the motivation of using PU learning to alleviate the false negative problem.

4.2 Adversarial Data Augmentation

Inspired by the recent progress of adversarial training [Mariani et al., 2018], we aim to use adversarial data augmentation to alleviate the long-existing data sparsity issue. Since positive triples only account for a tiny portion of all possible triples, we follow the principle of adversarial training to generate synthetic triples S ∗ i for data augmentation rather than only using authentic triples {⟨h, r, t⟩|h ∈ E ∧r ∈ R∧t ∈ E}. However, not all the generated synthetic triples are plausible enough to be regarded as positive triples. A more reasonable way is to treat them as unlabeled triples. With the welldefined PU risk estimator for KGC, we can train generator G and discriminator D by playing a PU minimax game, in which G tries to generate plausible synthetic triples to fool D and D tries to distinguish if a triple is synthetic or authentic using the proposed PU risk estimator. We explain the detail of adversarial data augmentation as follows.

Minimax Game. For one positive triple spi = ⟨hpi , rp i , tpi ⟩, a synthetic triple s∗im ∈ S ∗ i can be generated using a multilayer perceptron (MLP) given a random noise zim:

where 0 is the mean of noise input with the same size as the embedding dimension d, and I ∈ Rd×d is the identity matrix whose magnitude is controlled by the deviation of the noise input δ. Ω = {W1, W2, b1, b2} includes all learnable weights and biases of the two-layer MLP.

Given a generated synthetic triple s∗im ∈ S ∗ i , the discriminator D tries to predict the plausibility of s∗im to distinguish if it is authentic or synthetic. Note that scoring function ϕ(s; Θ) also predicts the plausibility of each triple. Thus, the discriminator can be defined as calculating the scoring function:

Since positive triples only account for a tiny portion of all authentic triples, the goal is to generate synthetic triples to augment positive triples. Therefore, the adversarial objective to train G and D can be designed as the minimax game w.r.t. positive authentic triples and synthetic triples:

With a fixed G, by minimizing Eq.(14), D is trained to optimize the relative ordering of the given positive triple spi and a generated synthetic triple s∗ij , such that spi ranks higher than s∗ij . On the contrary, with a fixed D, G is trained by maximizing Eq. (14) to fool D, such that s∗ij ranks higher than or close to spi .

PUMinimax Game. Note that with the minimax game designed as Eq.(14), the generated synthetic triples are treated in the same way as the authentic unlabeled triples Eq.(11). Thus, we can rewrite the minimax game as:

where ˆ r∗|i (ϕ) denotes the risk of obtaining non-optimal ordering of positive triple spi and synthetic triples S ∗ i , and ˆR-∗ (ϕ) represents the total risk of obtaining non-optimal ordering. By designing the adversarial training objective as a minimax game upon ˆR-∗ (ϕ), we can obtain the final training objective by unifying the PU risk estimator and the adversarial training objective as:

Different from ordinary adversarial training approaches [Goodfellow et al., 2014] whose final goal is to use the generator after training, we leverage the well-trained discriminator for predicting the plausibilities of missing triples. By the minimax game defined in Eq.(16), since D(s; Θ) and ϕ(s; Θ) are interchangeable, D not only utilizes the synthetic triples as Eq.(14), but also exploits the authentic triples in the unified PU risk estimator framework. The optimization process of PUDA is outlined in Algorithm 1 in supplementary material.

5 Experiments

In this section, we conduct extensive experiments to show the superiority of our proposed PUDA by answering the following research questions. RQ1: Does PUDA perform better than the state-of-the-art KGC methods? RQ2: How does each of the designed components in PUDA contribute to solving KGC? RQ3: How do different scoring functions influence the performance of PUDA?

5.1 Experimental Settings

Datasets. We evaluate PUDA mainly on two benchmark datasets, namely FB15k-237 [Toutanova et al., 2015] and WN18RR [Dettmers et al., 2018]. In addition, we use OpenBioLink [Breit et al., 2020] to evaluate PUDA with given true negative triples. More details about datasets and the results on OpenBioLink can be found in Section A.1 and A.5 of supplementary material, respectively.

Baselines. We compare PUDA with Tensor decomposition methods including DistMult [Yang et al., 2014], ComplEx [Trouillon et al., 2017] and SimplE [Kazemi and Poole, 2018]; Geometric methods including TransE [Bordes et al., 2013], CrossE [Zhang et al., 2019a], and RotatE [Sun et al., 2018]; and Deep learning methods including ConvE [Dettmers et al., 2018], ConvKB [Nguyen et al., 2018], CompGCN [Shikhar et al., 2020], and HRAN [Li et al., 2021]; and Negative sampling methods including KBGAN [Cai and Wang, 2018], NSCaching [Zhang et al., 2019b], and SANS [Ahrabian et al., 2020]. We briefly describe each baseline method in Section A.3 of the supplementary material.

Implementation Details. In the training phase, hyperparameters are tuned by grid search. In the test phase, we use the filtered [Bordes et al., 2013] setting and report Mean Reciprocal Rank (MRR) and Hits@K (K ∈ {1, 3, 10}). More details can be found in Section A.2 of supplementary material and the source code of PUDA.

5.2 Performance Comparison (RQ1)

We compare the overall performance of PUDA with that of baselines to answer RQ1. The results are shown in Table 1. X*, Xˆ , and X indicate the results are taken from [Rossi et al., 2021], [Shikhar et al., 2020], and the original papers, respectively. Since PUDA employs the scoring function DistMult, we first compare PUDA and DistMult. The results show that PUDA consistently outperforms DistMult on all metrics with a large margin. The improvement is attributed to the proposed PU risk estimator and adversarial data augmentation. Comparing to other baselines including the latest state-of-the-art method HRAN, PUDA has better performance on most of the metrics. Although baseline methods devise sophisticated scoring functions, they still suffer from the issue of false negative and data sparsity. The performance of PUDA with different scoring functions will be reported later in RQ3.

We then compare PUDA with negative sampling baselines, though we emphasize that the proposed PUDA is not a negative sampling based method. We regard nonexistent triples as unlabeled triples, rather than negative triples. Then we tailor the PU risk estimator to circumvent the impact of false negative triples. Our PUDA is capable of learning from the whole unlabeled data. To efficiently update model parameters, we uniformly sample a batch of unlabeled data in each iteration, which is a naive unlabeled data sampling process instead of a sophisticated negative sampling strategy. Although baseline methods devise novel negative sampling strategies, they still suffer from the issue of false negative and data sparsity. As shown in Table 1, our proposed PUDA consistently outperforms negative sampling based methods by effectively resolving these two issues.

5.3 Ablation Study (RQ2)

We conduct ablation study to show the effectiveness of each component of PUDA to answer RQ2. In Table 2, PN denotes the original DistMult model trained with ordinary positivenegative training objective by regarding all unlabeled triples as negative data. PU-C and PU-R denote the ordinary binaryclassification-based PU learning (pointwise ranking) and our proposed pairwise ranking-based PU learning, respectively. DA denotes the DistMult model only incorporating the proposed adversarial data augmentation. We have the following observations from Table 2. (i) PU-R shows the consistently superior performance than PN, demonstrating the effectiveness of our proposed PU learning for KGC by regarding negative triples as unlabeled triples to circumvent the impact of false negative issue. (ii) DA achieves a substantial improvement over PN, showing that the generated synthetic triples by our proposed adversarial data augmentation play a crucial role in improving the performance of KGC. (iii) PU-R outperforms PU-C, presenting the advantage of the proposed pairwise ranking-based PU risk estimator over the ordinary binary-classification-based PU risk estimator. We believe that it is because the pointwise ranking is unnecessarily hard for KGC task and harms the performance of KGC models. In addition, PU-C performs slightly worse than PN, showing that the ordinary binary-classification-based PU learning harms the performance of KGC model and is not suitable for the KGC task, also revealing the necessity of our proposed pairwise ranking-based PU risk estimator. (iv) PUDA outperforms not only PN, but also PU-C, PU-R, and DA, demonstrating the effectiveness of unifying adversarial training objective with the PU risk estimator with the PU minimax game.

5.4 Compatibility (RQ3)

We implement PUDA upon well-established scoring functions. As Table 3 shown, our proposed method can achieve a remarkable improvement over the original scoring functions on all metrics. Note that the included scoring functions are representative methods of tensor decomposition, geometric, and deep learning based methods. Such results demonstrate that PUDA is compatible with a wide range of scoring functions and could be a plug-and-play component for existing methods and we leave the potential of PUDA upon more advanced scoring functions to be discovered.

6 Conclusion

In this paper, we proposed the novel PUDA for KGC, which utilizes PU risk estimator and adversarial data augmentation to deal with the false negative issue and data sparsity issue, respectively. In particular, we tailored the ordinary PU risk estimator for KGC task and seamlessly unified the PU risk estimator with adversarial training objective via the PU minimax game. Extensive experimental results demonstrate the effectiveness and compatibility of PUDA.

Acknowledgments

This work has been supported by funding from King Abdullah University of Science and Technology under Award No. BAS/1/1635-01-01, URF/1/4355-01-01, URF/1/4675-01-01, and FCC/1/1976-34-01.This work is also supported by the National Key Research and Development Program of China under Grant No.2021ZD0113602, the National Natural Science Foundation of China under Grant No.62176014.