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 [1]. 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 [2]. 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.

Recent years have witnessed increasing interest in the KGC task [3]–[5]. 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 [1]. 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 [6] and \(0.00054\%\) in FB15k-237 [7]. Such extremely sparse positive training data could engender unsatisfactory generalization performance for correctly inferring the missing triples [8].

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 [1]. Inspired by positive-unlabeled (PU) learning [9] 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 [10] 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 [11] 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 Related Work↩︎

2.0.0.1 Knowledge Graph Completion.

A major line of KGC study focuses on learning distributed representations for entities and relations in KG [12]. (i) Tensor decomposition methods assume the score of a triple can be decomposed into several tensors [13]–[15]; (ii) Geometric methods regard a relation as the translation from a head entity to a tail entity [3], [16], [17]; (iii) Deep learning methods [4], [6], [18] 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.

2.0.0.2 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 [9]. PU learning roughly includes: (1) two-step solutions [19], [20], (2) methods that consider the unlabeled samples as negative samples with label noise [21] (3) unbiased risk estimation based methods [22]–[24]. 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.

2.0.0.3 Adversarial Training.

The adversarial training paradigm [25] 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 [11] have been proposed for data augmentation in all classes, rather than specially augmenting positive and unlabeled data. A few works [26]–[28] 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↩︎

3.0.0.1 Problem Formulation.

A KG is formulated as \(\mathcal{K} = \{ \langle h, r, t \rangle \} \subseteq \mathcal{E} \times \mathcal{R} \times \mathcal{E}\), where \(h\), \(r\), \(t\) denote the head entity, relation, and tail entity in triple \(\langle h, r, t \rangle\), respectively, \(\mathcal{E}\) and \(\mathcal{R}\) refer to the entity set and the relation set in \(\mathcal{K}\). \(|\mathcal{K}|\) denotes the total number of triples in \(\mathcal{K}\). The KGC problem is to infer the most plausible missing triple from \(\{ \langle h, r, t \rangle | t \in \mathcal{E} \land \langle h, r, t \rangle \notin \mathcal{K} \}\) (or \(\{ \langle h, r, t \rangle | h \in \mathcal{E} \land \langle h, r, t \rangle \notin \mathcal{K} \}\)) for each incomplete triple \(\langle h, r, ? \rangle\) (or \(\langle ?, r, t \rangle\)), e.g., reporting the top-\(k\) plausible missing triples.

3.0.0.2 Scoring Function.

The core of KGC is to learn a scoring function \(\phi(s; \Theta)\) to precisely estimate the plausibility of any triple \(s = \langle h, r, t \rangle\), where \(\Theta\) 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 [13] as scoring function. Given the embedding dimension \(d\), head entity embedding \(\mathbf{h} \in \mathbb{R}^d\), relation embedding \(\mathbf{r} \in \mathbb{R}^{d \times d}\), and tail embedding \(\mathbf{t} \in \mathbb{R}^d\), the scoring function is then computed as a bilinear product: \[\phi(s; \Theta) = \mathbf{h} \times \mathbf{r} \times \mathbf{t}, \label{scoringfunc}\tag{1}\] where symbol \(\times\) denotes matrix product, \(\mathbf{r}\) is forced to be a diagonal matrix, \(\Theta = \{\mathbf{E}_e, \mathbf{E}_r \}\) represents learnable parameters, \(\mathbf{E}_e \in \mathbb{R}^{|\mathcal{E}| \times d}\) and \(\mathbf{E}_r \in \mathbb{R}^{|\mathcal{R}| \times d \times d}\) denote the embedding matrices of entities and relations, respectively.

3.0.0.3 PU Triple Preparation.

The widely used loss functions [27] in KGC always require positive triples and negative triples for optimization. The true facts in \(\mathcal{K}\) can be naturally regarded as positive triples. To obtain negative triples, the common practice [1] is to corrupt \(h^p\) or \(t^p\) in a positive triple \(\langle h^p, r^p, t^p \rangle\). Here we only describe the case of tail corruption; head corruption is defined analogously. Specifically, let \(s_i^p = \langle h_i^p, r_i^p, t_i^p \rangle\) be the \(i^{th}\) positive triple in \(\mathcal{K}\). For a given \(s_i^p\), we can obtain \(N\) corrupted triples \(\mathcal{S}^u_i = \{\langle h_i^p, r_i^p, t^u_{ij} \rangle \}^N\) by sampling \(N\) entities \(\{ t^u_{i1}, ..., t^u_{iN} \}\) from \(\{t|t \in \mathcal{E} \land \langle h_i^p, r_i^p, t \rangle \notin \mathcal{K}\}\) and replacing \(t_i^p\) by each sampled entity \(t^u_{ij}\). 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 [1], we regard each triple in \(\mathcal{S}^u_i\) as an unlabeled triple.

3.0.0.4 Data Augmentation.

Besides the positive and unlabeled triples, we also generate a set of synthetic triples for data augmentation. Specifically, for a positive triple \(s_i^p = \langle h_i^p, r_i^p, t_i^p \rangle\), we generate \(M\) synthetic triples \(\mathcal{S}^*_i = \{\langle h_i^p, r_i^p, t^*_{im} \rangle \}^M\) by generating \(M\) synthetic entities \(\{t^*_{i1}, .... ,t^*_{iM} \}\) via adversarial training and replacing \(t_i^p\) by each synthetic entity \(t^*_{im}\), where \(t^*_{im} \notin \mathcal{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 \(\mathcal{S}^*_i\) as an unlabeled triple as well.

4 The Proposed Method↩︎

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 [29]–[31]. 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.

4.1.0.1 PU Classification Risk Estimator.

In positive-negative learning, the empirical risk estimator \(\hat{\mathcal{R}}_{pn}(\psi)\) w.r.t. a positive class prior \(\pi_p = 1 - \pi_n\) (the percentage of positive samples in all possible samples) is defined as: \[\hat{\mathcal{R}}_{pn}(\psi)=\pi_{p} \hat{\mathcal{R}}_{p}^{+}(\psi)+ \pi_{n} \hat{\mathcal{R}}_{n}^{-}(\psi), \label{pnrisk}\tag{2}\] where \(\psi(\cdot)\) is an arbitrary decision function, \(\hat{\mathcal{R}}_{p}^{+}(\psi)\) is the expected risk of predicting positive samples as positive (+), and \(\hat{\mathcal{R}}_{n}^{-}(\psi)\) 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 \(\hat{\mathcal{R}}_{n}^{-}(\psi)\). Following [32], we define \(\pi_n \hat{\mathcal{R}}_{n}^{-}(\psi)\) as: \[\pi_{n} \hat{\mathcal{R}}_{n}^{-}(\psi)=\hat{\mathcal{R}}_{u}^{-}(\psi) - \pi_{p} \hat{\mathcal{R}}_{p}^{-}(\psi), \label{purisk95pre}\tag{3}\] where \(\hat{\mathcal{R}}_{u}^{-}(\psi)\) is the expected risk of predicting unlabeled samples as negative (-) and \(\hat{\mathcal{R}}_{p}^{-}(\psi)\) 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: \[\hat{\mathcal{R}}_{pu}(\psi)=\pi_{p} \hat{\mathcal{R}}_{p}^{+}(\psi)+ \hat{\mathcal{R}}_{u}^{-}(\psi) - \pi_{p} \hat{\mathcal{R}}_{p}^{-}(\psi). \label{purisk}\tag{4}\] Most recent works on risk estimation based PU learning [10], [33] note that the model tends to suffer from overfitting on the training data when the decision function \(\psi\) is complex. Thus, a non-negative risk estimator [10] is proposed to alleviate the overfitting problem: \[\hat{\mathcal{R}}(\psi)=\pi_{p} \hat{\mathcal{R}}_{p}^{+}(\psi)+ \max\{0, \hat{\mathcal{R}}_{u}^{-}(\psi) - \pi_{p} \hat{\mathcal{R}}_{p}^{-}(\psi)\}. \label{nnpurisk}\tag{5}\] \(\hat{\mathcal{R}}(\psi)\) should be minimized to learn the function \(\psi\). 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.

4.1.0.2 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 \(\psi(\cdot)\) to predict the plausibility of any triple: \[\psi(\cdot) = \phi(s;\Theta).\] We replace \(\psi(\cdot)\) by \(\phi(\cdot)\) in the later descriptions. In the scenario of KGC, the key challenge is to give suitable definitions to the risks \(\hat{\mathcal{R}}_{p}^{+}(\phi)\), \(\hat{\mathcal{R}}_{p}^{-}(\phi)\), and \(\hat{\mathcal{R}}_{u}^{-}(\phi)\). Prevailing PU learning methods [10], [22] define the above risks for binary classification as follows: \[ \hat{\mathcal{R}}_{p}^{+}(\phi) = - \frac{1}{|\mathcal{K}|} \sum_{i=1}^{|\mathcal{K}|} \ln \sigma \left(\phi(s_i^p;\Theta)\right), \label{p43}\tag{6}\] \[ \hat{\mathcal{R}}_{p}^{-}(\phi) = - \frac{1}{|\mathcal{K}|} \sum_{i=1}^{|\mathcal{K}|} \ln \sigma \left(-\phi(s_i^p;\Theta)\right), \label{p-}\tag{7}\] \[ \hat{\mathcal{R}}_{u}^{-}(\phi) = - \frac{1}{|\mathcal{K}|} \frac{1}{N}\sum_{i=1}^{|\mathcal{K}|} \sum_{j=1}^{N} \ln \sigma \left(-\phi(s_{ij}^u;\Theta)\right), \label{oldru}\tag{8}\] where \(\ln \sigma (\cdot)\) is the log-sigmoid function and is a commonly used function for risk estimator [10], and \(s_{ij}^u \in \mathcal{S}_{i}^u\) denotes an unlabeled triple w.r.t. \(s_{i}^p\). The output values of the score function \(\phi(s;\Theta)\) can differentiate the positive triples from the unlabeled triples. However, it is unnecessarily hard to push \(\sigma(\phi(s;\Theta))\) 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 \(>_{s_{i}^{p}}\) be the optimal ordering of a given positive triple \(s_{i}^{p}\) and unlabeled triples \(\mathcal{S}^u_i\), i.e., \(s_{i}^{p}\) is ranked higher than every triple in \(\mathcal{S}^u_i\). Without loss of generality, we can assume that all unlabeled triples in \(\mathcal{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 \(\Theta\) towards the optimal ordering \(>_{s_{i}^{p}}\) can then be formulated on each pair of triples (\(s_i^p\), \(s_{ij}^u\)) [29] as follows: \[\begin{align} \ln p(>_{s_{i}^{p}} \mid \Theta) =& \ln \prod_{j=1}^{N} \sigma\left(\phi(s_i^p;\Theta) - \phi(s_{ij}^u; \Theta)\right) \\ =& \sum_{j=1}^{N} \ln \sigma \underbrace{(\phi(s_i^p;\Theta) - \phi(s_{ij}^u; \Theta))}_{\text{Pairwise Ordering}} , \end{align} \label{bpr}\tag{9}\]

where maximizing the difference between \(\phi(s_i^p;\Theta)\) and \(\phi(s_{ij}^u; \Theta)\) would push the positive triple \(s_i^p\) to rank higher than all unlabeled triples in \(\mathcal{S}_i^u\).

The lack of pairwise triples in Eq.(8 ) hinders the introduction of pairwise comparison. It focuses only on minimizing the risk of predicting \(\phi(s_{ij}^u; \Theta)\) as a too large value. To incorporate the pairwise orderings, we can replace \(\ln \sigma (-\phi(s_{ij}^u;\Theta) )\) in Eq.(8 ) by \(\ln \sigma (\phi(s_i^p;\Theta) - \phi(s_{ij}^u; \Theta))\). That is, measuring the likelihood of \(s_{ij}^u\) being a small value is replaced by measuring the likelihood of \(s_{ij}^u\) being just smaller than its positive counterpart \(s_{i}^p\). Then, Eq.(8 ) becomes \[\small \hat{\mathcal{R}}_{u}^{-}(\phi) = \frac{1}{|\mathcal{K}|} \sum_{i=1}^{|\mathcal{K}|} \overbrace{- \frac{1}{N} \sum_{j=1}^{N} \ln \sigma \underbrace{(\phi(s_i^p;\Theta) -\phi(s_{ij}^u;\Theta))}_{\text{Pairwise Ordering}}}^{\hat{r}_{u|i}^{-}(\phi)}, \label{replace}\tag{10}\] where \(\hat{r}_{u|i}^{-}(\phi)\) is the risk of obtaining a non-optimal ordering of the positive triple \(s_i^p\) and the unlabeled triples \(\mathcal{S}_i^u\). It is worth noting that Eq.(10 ) makes no penalty on the ranking relations among unlabeled triples, unlike Eq.(8 ) which targets to score all unlabeled triples to be the same low values. Hence, Eq.(10 ) 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 higher-ranked unlabeled triples have the room to be promoted as positive triples. Combining Eq.(5 ) with Eq.(6 ), Eq.(7 ), and Eq.(10 ), we have the well defined \(\hat{\mathcal{R}}(\phi)\) for KGC problem, which embeds pairwise ranking objective in the PU risk estimator to deal with the false negative issue.

4.1.0.3 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 [1]. 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 [10]. Specifically, Eq.(5 ) is the PU objective and Eq.(7 ) 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 [11], 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 \(\mathcal{S}^*_i\) for data augmentation rather than only using authentic triples \(\{ \langle h, r, t \rangle| h \in \mathcal{E} \land r \in \mathcal{R} \land t \in \mathcal{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 well-defined PU risk estimator for KGC, we can train generator \(\mathbf{G}\) and discriminator \(\mathbf{D}\) by playing a PU minimax game, in which \(\mathbf{G}\) tries to generate plausible synthetic triples to fool \(\mathbf{D}\) and \(\mathbf{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.

4.2.0.1 Minimax Game.

For one positive triple \(s_i^p = \langle h_i^p, r_i^p, t_i^p \rangle\), a synthetic triple \(s_{im}^{*} \in \mathcal{S}^*_i\) can be generated using a multi-layer perceptron (MLP) given a random noise \(z_{im}\): \[\begin{align} \mathbf{G}(z; \Omega) = \operatorname{Tanh}(\mathbf{W_{2}} \cdot & \operatorname{ReLU}(\mathbf{W_{1}} \cdot z+\mathbf{b_{1}})+\mathbf{b_{2}}), \\ z_{im} \sim& \mathcal{N}(\mathbf{0}, \delta \mathbf{I}),\\ t_{im}^{*} =& \mathbf{G}(z_{im}; \Omega), \\ s_{im}^{*} =& \langle h_i^p, r_i^p, t_{im}^{*} \rangle, \end{align}\] where \(\mathbf{0}\) is the mean of noise input with the same size as the embedding dimension \(d\), and \(\mathbf{I} \in \mathbb{R}^{d \times d}\) is the identity matrix whose magnitude is controlled by the deviation of the noise input \(\delta\). \(\Omega = \{\mathbf{W_{1}}\), \(\mathbf{W_{2}}\), \(\mathbf{b_{1}}\), \(\mathbf{b_{2}}\}\) includes all learnable weights and biases of the two-layer MLP.

Given a generated synthetic triple \(s_{im}^{*} \in \mathcal{S}^*_i\), the discriminator \(\mathbf{D}\) tries to predict the plausibility of \(s_{im}^{*}\) to distinguish if it is authentic or synthetic. Note that scoring function \(\phi(s; \Theta)\) also predicts the plausibility of each triple. Thus, the discriminator can be defined as calculating the scoring function: \[\mathbf{D}(s;\Theta) = \phi(s;\Theta).\]

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 \(\mathbf{G}\) and \(\mathbf{D}\) can be designed as the minimax game w.r.t. positive authentic triples and synthetic triples: \[ \min _{\mathbf{D}} \max _{\mathbf{G}}: \frac{1}{|\mathcal{K}|} \sum_{i=1}^{|\mathcal{K}|} \overbrace{- \frac{1}{M} \sum_{m=1}^{M} \ln \sigma\underbrace{(\phi(s_i^p;\Theta) - \phi(s_{ij}^*; \Theta))}_{\text{Pairwise Ordering}}}^{\hat{r}_{*|i}^{-}(\phi)}. \label{synminimax}\tag{11}\] With a fixed \(\mathbf{G}\), by minimizing Eq.(11 ), \(\mathbf{D}\) is trained to optimize the relative ordering of the given positive triple \(s_i^p\) and a generated synthetic triple \(s_{ij}^*\), such that \(s_i^p\) ranks higher than \(s_{ij}^*\). On the contrary, with a fixed \(\mathbf{D}\), \(\mathbf{G}\) is trained by maximizing Eq. (11 ) to fool \(\mathbf{D}\), such that \(s_{ij}^*\) ranks higher than or close to \(s_i^p\).

4.2.0.2 PU Minimax Game.

Note that with the minimax game designed as Eq.(11 ), the generated synthetic triples are treated in the same way as the authentic unlabeled triples Eq.(10 ). Thus, we can rewrite the minimax game as: \[ \hat{\mathcal{R}}_{*}^{-}(\phi)= \min _{\mathbf{D}} \max _{\mathbf{G}}: \frac{1}{|\mathcal{K}|} \sum_{i=1}^{|\mathcal{K}|} \hat{r}_{*|i}^{-}(\phi),\] where \(\hat{r}_{*|i}^{-}(\phi)\) denotes the risk of obtaining non-optimal ordering of positive triple \(s_i^p\) and synthetic triples \(\mathcal{S}^*_i\), and \(\hat{\mathcal{R}}_{*}^{-}(\phi)\) represents the total risk of obtaining non-optimal ordering. By designing the adversarial training objective as a minimax game upon \(\hat{\mathcal{R}}_{*}^{-}(\phi)\), we can obtain the final training objective by unifying the PU risk estimator and the adversarial training objective as: \[ \min _{\mathbf{D}} \max _{\mathbf{G}}: \pi_{p} \hat{\mathcal{R}}_{p}^{+}(\phi)+ \max\{0, \hat{\mathcal{R}}_{u}^{-}(\phi) + \hat{\mathcal{R}}_{*}^{-}(\phi) - \pi_{p} \hat{\mathcal{R}}_{p}^{-}(\phi)\}. \label{final}\tag{12}\]

Different from ordinary adversarial training approaches [25] 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.(12 ), since \(\mathbf{D}(s;\Theta)\) and \(\phi(s;\Theta)\) are interchangeable, \(\mathbf{D}\) not only utilizes the synthetic triples as Eq.(11 ), 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↩︎

5.1.0.1 Datasets.

We evaluate PUDA mainly on two benchmark datasets, namely FB15k-237 [7] and WN18RR [6]. In addition, we use OpenBioLink [34] 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.

5.1.0.2 Baselines.

We compare PUDA with Tensor decomposition methods including DistMult [13], ComplEx [14] and SimplE [15]; Geometric methods including TransE [16], CrossE [17], and RotatE [3]; and Deep learning methods including ConvE [6], ConvKB [18], CompGCN [4], and HRAN [5]; and Negative sampling methods including KBGAN [27], NSCaching [35], and SANS [36]. We briefly describe each baseline method in Section A.3 of the supplementary material.

5.1.0.3 Implementation Details.

In the training phase, hyperparameters are tuned by grid search. In the test phase, we use the filtered [16] setting and report Mean Reciprocal Rank (MRR) and Hits@K (K \(\in\) ). 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 [1], [4], 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 positive-negative training objective by regarding all unlabeled triples as negative data. PU-C and PU-R denote the ordinary binary-classification-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.

Supplementary Materials↩︎

A.1Experimental Datasets↩︎

We evaluate PUDA on three benchmark datasets, namely FB15k-237 [7], WN18RR [6], and OpenBioLink [34]. The challenging and widely used datasets FB15k-237 and WN18RR are subsets of FB15k and WN18 [16] with reversible relations removed, respectively. And OpenBioLink is a benchmark biomedical knowledge graph dataset with explicitly annotated true negative samples. We use the default directed high-quality version of OpenBioLink to evaluate PUDA given true negative triples and provide in-depth discussion on PU learning. For all datasets, we follow the common partition of train/valid/test sets. Due to the limited computation resources, we select subsets of the original validation set and test set of OpenBioLink for validation and testing in our evaluation. The statistics of datasets are summarized in Table 4. The detailed descriptions and download sources of FB15k-237⁴, WN18RR⁵, and OpenBioLink⁶ can be found from given links.

A.2Implementation Details↩︎

We implement the proposed framework using the Python library PyTorch and conduct all the experiments on Linux server with GPUs (Nvidia RTX 3090) and CPU (Intel Xeon). The initial learning rate of the Adam [37] optimizer is tuned by grid searching within {\(1e^{-2}\), \(1e^{-3}\), \(1e^{-4}\), \(1e^{-5}\)} for both \(\mathbf{G}\) and \(\mathbf{D}\). The positive class prior \(\pi_p\), the embedding dimension \(d\), the number of unlabeled triples \(N\) for each positive triple, the number of generated synthetic triples \(M\) for each positive triple, and the L2 regularization ratio are searched within {\(2e^{-1}\), \(1e^{-1}\), \(1e^{-2}\), \(1e^{-3}\), \(1e^{-4}\), \(1e^{-5}\)}, {256, 512, 1024}, {2, 4, 8, 16, 32, 64}, {2, 4, 8, 16, 32, 64}, and {0, \(1e^{-4}\), \(1e^{-3}\), \(1e^{-2}\), \(1e^{-1}\), \(2e^{-1}\)}, respectively. We keep the ratio of replacing head and tail entities, the dropout ratio of \(\mathbf{G}\), and the hidden dimension of \(\mathbf{G}\) as 1:1, 0.5, and \(d/8\), respectively.

A.3Baselines↩︎

Tensor decomposition methods: DistMult [13] that is a popular tensor factorization model and the embeddings learned from the simple bilinear objective are particularly good at capturing relational semantics; ComplEx [14] that entends DistMult by embedding entities and relations into complex vectors; and SimplE [15] that uses doubled embeddings for entities and relations to improve the model expressiveness;

Geometric methods: TransE [16] that is the first KGC model to propose a geometric interpretation of the latent space; CrossE [17] that introduces triple-specific embeddings and dubbed interaction embeddings; and RotatE [3] that defines each relation as a rotation from the head entity to the tail entity in the complex vector space and proposes a simple yet effective negative sampling method named self-adversarial negative sampling;

Deep learning methods: ConvE [6] and ConvKB [18] that are two popular convolutional network based methods; CompGCN [4] that is a state-of-the-art method using composition-based graph convolutional networks; HRAN [5] that is one of the latest KGC methods leveraging heterogeneous relation attention networks.

Negative Sampling methods: KBGAN [27] that leverages deep reinforcement learning for negative sampling; NSCaching [35] that acts as a distilled version of previous GAN based methods and is more efficient; and SANS [36] that is an inexpensive negative sampling strategy that utilizes the rich graph structure by selecting negative samples from a node’s k-hop neighborhood.

A.4Sensitivity w.r.t. Positive Class Prior \(\pi_p\)↩︎

We analyze the sensitivity of our proposed PUDA w.r.t. the positive class prior \(\pi_p\), which is a key factor in PU learning risk estimator. Since the true facts that can be leveraged as positive triples are extremely rare in KGC task and the positive class prior \(\pi_p\) represents the percentage of positive triples in all possible triples, we search the best positive class prior within {\(1e^{-1}\), \(1e^{-2}\), ..., \(1e^{-6}\), \(1e^{-7}\)}. From the experimental results shown in Figure 3, we can see that the positive class prior has a relatively large impact on the overall performance of PUDA. However, we observe that the impact of the positive class prior on the performance of PUDA is slight when \(\pi_p\) falls into the range of {\(1e^{-4}\), \(1e^{-5}\), \(1e^{-6}\), \(1e^{-7}\)}. Therefore, although PUDA is relatively sensitive to the positive class prior \(\pi_p\), it is easy to select an appropriate \(\pi_p\) to guarantee the effectiveness of PUDA.

A.5The Impact of True Negative Triples↩︎

We conduct experiments to study the impact of true negative triples to answer RQ4 on the OpenBioLink dataset, which is one of the few datasets providing annotated true negative triples. PN+ and PUDA+ denote PN and PUDA trained with true negative triples and unlabeled triples together for each positive triple rather than only with unlabeled triples. Specifically, we sample the same size of true negative triples as the size of unlabeled triples for each positive triple. We regard the sampled true negative triples together with the unlabeled triples as negative triples to train PN+, and regard them as the unlabeled triples \(S_{i}^{u}\) w.r.t the given positive triple \(s_{i}^{p}\) to train PUDA+. From the results shown in Table 5, we have the following findings: (i) PN+ and PUDA+ outperform PN and PUDA, respectively, indicating that the true negative triple can help the model learning. We believe the reason could be that using true negative triples can reduce the involvement of false negative triples in the training phase; (ii) PUDA outperforms PN, and PUDA+ outperforms PN+, clearly demonstrating the effectiveness of PUDA on modeling positive and unlabeled data; (iii) PUDA has better performance than PN+, presenting that the adverse impact of false negative issue cannot be fully eliminated even using the true negative triples, and our proposed PUDA provides a more applicable solution. (iv) Here we emphasize that an ideal PU learning method for KGC should completely circumvent the impact of the false negative triples. In other words, using annotated true negative triples that can reduce the involvement of false negative triples should not be helpful for an ideal PU learning method for KGC. Since PUDA+ outperforms PUDA, we can see that our proposed method can be further improved towards achieving an ideal PU learning method for KGC. We leave this for future work.

References↩︎