Embedding Uncertain Knowledge Graphs

Introduction

Knowledge Graphs (KGs) provide structured representations of real-world entities and relations, which are categorized into the following two types: (i) Deterministic KGs, such as YAGO (?) and FreeBase (?), consist of deterministic relation facts that describe semantic relations between entities; (ii) Uncertain KGs including ProBase (?), ConceptNet (?) and NELL (?) associate every relation fact with a confidence score that represents the likelihood of the relation fact to be true.

KG embedding models are essential tools for incorporating the structured knowledge representations in KGs into machine learning. These models encode entities as low-dimensional vectors and relations as algebraic operations among entity vectors. They accurately capture the similarity of entities and preserve the structure of KGs in the embedding space. Hence, they have been the crucial feature models that benefit numerous knowledge-driven tasks (?; ?; ?). Recently, extensive efforts have been devoted into embedding deterministic KGs. Translational models, e.g., TransE (?) and TransH (?)), and bilinear models, e.g. DistMult (?) and ComplEx (?), have achieved promising performance in many tasks, such as link prediction (?; ?), relation extraction (?), relational learning (?), and ontology population (?).

While current embedding models focus on capturing deterministic knowledge, it is critical to incorporate uncertainty information into knowledge sources for several reasons. First, uncertainty is the nature of many forms of knowledge. An example of naturally uncertain knowledge is the interactions between proteins. Since molecular reactions are random processes, biologists label the protein interactions with their probabilities of occurrence and present them as uncertain KGs called Protein-Protein Interaction (PPI) Networks. Second, uncertainty enhances inference in knowledge-driven applications. For example, short text understanding often entails interpreting real-world concepts that are ambiguous or intrinsically vague. The probabilistic KG Probase (?) provides a prior probability distribution of concepts behind a term that has critically supported short text understanding tasks involving disambiguation (?; ?). Furthermore, uncertain knowledge representations have largely benefited various applications, such as question answering (?) and named entity recognition (?).

Capturing the uncertainty information with KG embeddings remains an unresolved problem. This is a non-trivial task for several reasons. First, compared to deterministic KG embeddings, uncertain KG embeddings need to encode additional confidence information to preserve uncertainty. Second, current KG embedding models cannot capture the subtle uncertainty of unseen relation facts, as they assume that all the unseen relation facts are false beliefs and minimize the plausibility measures of relation facts. One major challenge of learning embeddings for uncertain KGs is to properly estimate the uncertainty of unseen relation facts.

To address the above issues, we propose a new embedding model UKGE (Uncertain Knowledge Graph Embeddings), which aims to preserve both structural and uncertainty information of relation facts in the embedding space. Embeddings of entities and relations on uncertain KGs are learned according to confidence scores. Unlike previous models that characterize relation facts with binary classification techniques, UKGE learns embeddings according to the confidence scores of uncertain relation facts. To further enhance the precision of UKGE, we also introduce probabilistic soft logic to infer the confidence score for unseen relation facts during training. We propose two variants of UKGE based on different embedding-based confidence functions. We conducted extensive experiments using three real-world uncertain KGs on three tasks: (i) confidence prediction, which seeks to predict confidence scores of unseen relation facts; (ii) relation fact ranking, which focuses on retrieving tail entities for the query $(h,r,\underline{?t})$ and ranking these retrieved tails in the right order; and (iii) relation fact classification, which decides whether or not a given relation fact is a strong relation fact. Our models consistently outperform the baseline models in these experiments.

The rest of the paper is organized as follows. We first review the related work in Section 2, then provide the problem definition and propose our model UKGE in the two sections that follow. In section 5, we present our experiments. Then we conclude the paper in Section 6.

Related Work

To the best of our knowledge, there has been no previous work on learning embeddings for uncertain KGs. We hereby discuss the following three lines of work that are closely related to this topic.

Deterministic KG embeddings have been extensively explored by recent work. These models encode entities as low-dimensional vectors and relations as algebraic operations among entity vectors. There are two representative families of models, i.e. translational models and bilinear models.

Translational models share a common principle $\boldsymbol{h}_{r}+\boldsymbol{r}\approx\boldsymbol{t}_{r}$, where $\boldsymbol{h}_{r}$, $\boldsymbol{t}_{r}$ are the entity embeddings projected in a relation-specific space. The forerunner of this family, TransE (?), lays $\boldsymbol{h}_{r}$ and $\boldsymbol{t}_{r}$ in a common space as $\boldsymbol{h}$ and $\boldsymbol{t}$ with regard to any relation $r$. Variants of TransE, such as TransH (?), TransR (?), TransD (?), and TransA, (?) differentiate the translations of entity embeddings in different language-specific embedded spaces based on different forms of relation-specific projections. Despite its simplicity, translational models achieve promising performance on knowledge completion and relation extraction tasks.

Bilinear models (?) model relations as the second-order correlations between entities, using the scoring function $f(h,r,t)=\boldsymbol{h}^{T}\boldsymbol{W_{r}}\boldsymbol{t}$. This function is first adopted by RESCAL (?), a collective matrix factorization model. DistMult (?) constrains $\boldsymbol{W_{r}}$ as a diagonal matrix which reduces the computing cost and also enhances the performance. ComplEx adjusts the corresponding scoring mechanism to a complex conjugation in a complex embedding space.

There are also other models for deterministic KG embedding, such as neural models like Neural Tensor Network (NTN) (?) and ConvE (?), and the circular-correlation-based model HolE (?).

Uncertain Knowledge Graphs

Uncertain KGs provide a confidence score along with every relation fact. The development of relation extraction and crowdsourcing in recent years enabled the construction of large-scale uncertain knowledge bases. ConceptNet (?) is a multilingual uncertain KG for commonsense knowledge that is collected via crowdsourcing. The confidence scores in ConceptNet mainly come from the co-occurrence frequency of the labels in crowdsourced task results. Probase (?) is a universal probabilistic taxonomy built by relation extraction. Every fact in Probase is associated with a joint probability $P_{isA}(x,y)$. NELL (?) collects relation facts by reading web pages and learns their confidence scores from semi-supervised learning with the Expectation-Maximum (EM) algorithm. Aforementioned uncertain KGs have enabled numerous knowledge-driven applications. For example, ? (?) utilize Probase to help understand short texts.

One recent work has proposed a matrix-factorization-based approach to embed uncertain networks (?). However, it cannot be generalized to embed uncertain KGs because this model only considers the node proximity in the networks with no explicit relations and only generates node embeddings. As far as we know, we are among the first to study the uncertain KG embedding problem.

Probabilistic Soft Logic

Probabilistic soft logic (PSL) (?) is a framework for probabilistic reasoning. A PSL program consists of a set of first-order logic rules with conjunctive bodies and single literal heads. PSL takes the confidence from interval $$ as the soft truth values for every atom. It uses Lukasiewics t-norm (?) to determine to which degree a rule is satisfied. In combination with Hinge-Loss Markov Random Field (HL-MRF), PSL is widely used in probabilistic reasoning tasks, such as social-trust prediction and preference prediction (?; ?). In this paper, we adopt PSL to enhance the embedding model performance on the unseen relation facts.

Problem Definition

We define the uncertain KG embedding problem in this section by first providing the definition of uncertain KGs.

Uncertain Knowledge Graph. An uncertain KG represents knowledge as a set of relations ($\mathcal{R}$) defined over a set of entities ($\mathcal{E}$). It consists of a set of weighted triples $\mathcal{G}=\{(l,s_{l})\}$. For each pair $(l,s_{l})$, $l=(h,r,t)$ is a triple representing a relation fact where $h,t\in\mathcal{E}$ (the set of entities) and $r\in\mathcal{R}$ (the set of relations), and $s_{l}\in$ represents the confidence score for this relation fact to be true.

Note that we assume the confidence score $s_{l}\in$ and interpret it as a probability to leverage probabilistic soft logic-based inference. The range of original confidence scores for some uncertain KG (e.g., ConceptNet) may not fall in $$, and normalization will be needed in these cases. Some examples of weighted triples are listed below.

Uncertain Knowledge Graph Embedding Problem. Given an uncertain KG $\mathcal{G}$, the embedding model aims to encode each entity and relation in a low-dimensional space in which structure information and confidence scores of relation facts are preserved.

Modeling

In this section, we propose our model for uncertain KG embeddings. The proposed model UKGE encodes the KG structure according to the confidence scores for both observed and unseen relation facts, such that the embeddings of relation facts with higher confidence scores receive higher plausibility values.

We first design relation fact confidence score modeling based on embeddings of entities and relations, then introduce how probabilistic soft logic can be used to infer confidence scores for unseen relations, and lastly describe the joint model UKGE and its two variants.

Unlike deterministic KG embedding models, uncertain KG embedding models need to explicitly model the confidence score for each triple and compare the prediction with the true score. We hereby first define and model the plausibility of triples, which can be considered as a unnormalized confidence score.

Plausibility. Given a relation fact triple $l$, the plausibility $g(l)\in R$ measures how likely this relation fact holds. The higher plausibility value corresponds to the higher confidence score $s$.

Given a triple $l=(h,r,t)$ and their embeddings $\boldsymbol{h},\boldsymbol{r},\boldsymbol{t}$, we model the plausibility of $(h,r,t)$ by the following function:

where $\circ$ is the element-wise product, and $\cdot$ is the inner product. This function captures the relatedness between embeddings $\boldsymbol{h}$ and $\boldsymbol{t}$ under the condition of relation $r$ and is first adopted by DistMult (?). We employ this triple modeling technique for three reasons: (i) This technique has represented the state-of-the-art performance for modeling deterministic KGs (?), (ii) It agrees with the nature of our model to quantify the confidence of an uncertain relation fact by comparing the relation embeddings with the pair of head and tail embeddings, (iii) It does not introduce additional parameter complexity to the model like other techniques, such as TransH (?), TransR (?), ConvE (?) and ProjE (?). Nevertheless, this scoring function can be further explored in future work.

In order to transform plausibility scores to confidence scores, we consider two different mapping functions and test them in the experimental section. Formally, let a triple be $l$ and its plausibility score be $g(l)$, a transformation function $\phi(\cdot)$ maps $g(l)$ to a confidence score $f(l)$.

Two choices of mapping $\phi$ are listed below.

Logistic function. One way to map plausibility values to confidence score is a logistic function as follows:

Bounded rectifier. Another mapping is a bounded rectifier (?):

where $\mathbf{w}$ is a weight $\mathbf{b}$ is a bias.

2 PSL-based Confidence Score Reasoning for Unseen Relation Facts

In order to better estimate confidence scores, both observed and unseen relation facts in KGs should be utilized. Deterministic KG embedding methods assume that all unseen relation facts are false beliefs, and use negative sampling to add some of these false relations into training. One major challenge of learning embeddings for uncertain KGs, however, is to properly estimate the uncertainty of unseen triples, as simply treating their confidence score as can no longer capture the subtle uncertainty. For example, it is common that a Protein-Protein Interaction Network KG may have no interaction records for two proteins that can be potentially binded. Ignoring such possibility will result in information loss.

We thus introduce probabilistic soft logic (PSL) (?) to infer confidence scores for these unseen relation facts to further enhance the embedding performance. PSL is a framework for confidence reasoning that propagates confidence of existing knowledge to unseen triples using soft logic.

A PSL program consists of a set of first order logic rules that describe logical dependencies between facts (atoms). One example of logical rule is shown below:

A Logical Rule on Transitivity of Synonym Relation. (A,synonym,B) $\wedge$ (B,synonym,C) $\rightarrow$ (A,synonym,C)

This logical rule describes the transitivity of the relation synonym. In this logical rule, A, B and C are placeholders for entities, synonym is the predicate that corresponds to the relation in uncertain KGs, (A,synonym,B) $\wedge$ (B,synonym,C) is the body of the rule, and (A,synonym,C) is the head of the rule.

A logical rule serves as a template rule. By replacing the placeholders in a logical rule with concrete entities and relations, we can get rule instances, which are called ground rules. Considering Example 4.1 and uncertain relation facts from Example 3.1, we can have the following ground rule by replacing the placeholders with real relation facts in KG.

A Ground Rule on Transitivity of Synonym. (college, synonym, university) $\wedge$ (university, synonym, institute) $\rightarrow$ (college, synonym, institute)

Different from Boolean logic, PSL associates every atom, i.e., a triple $l$, with a soft truth value from the interval $$, which corresponds to the confidence score in our context and enables fuzzy reasoning. The assignment process of soft truth values is called an interpretation. We denote the soft truth value of an atom$l$assigned by the interpretation$I$as$I(l)$. Naturally, for observed relation facts, their observed confidence scores are used for assignment; and for unseen triples, the embedding-based estimated confidence scores will be assigned to them:

where $\mathcal{L}^{+}$ denotes the observed triple set, $\mathcal{L}^{-}$ denotes the unseen triples, $s_{l}$ denotes the confidence score for observed triple $l$, and $f(l)$ denotes the embedding-based confidence score function for $l$.

In PSL, Lukasiewicz t-norm is used to define the basic logical operations, including logical conjunction ($\wedge$), disjunction ($\vee$), and negation ($\neg$), as follows:

For example, according to Eq. (6) and (7), $0.8\wedge 0.3=0.1$ and $0.8\vee 0.3=1$. For a rule $\gamma\equiv\gamma_{body}\rightarrow\gamma_{head}$, as it can be written as $\neg\gamma_{body}\vee\gamma_{head}$, its value $p_{\gamma}$ can be computed as

PSL regards a rule $\gamma$ as satisfied when the truth value of its head $I(\gamma_{head})$ is the same or higher than its body $I(\gamma_{body})$, i.e., when its value is greater than or equal to 1.

Consider Example 4.2. Let (college, synonym, university) be $l_{1}$, (university, synonym, college) be $l_{2}$, and (college, synonym, institute) be $l_{3}$. Assuming that $l_{1}$ and $l_{2}$ are observed triples in KG, and $l_{3}$ is unseen, according to Equation (5), (6), and (9), the distance to satisfaction of this ground rule is calculated as below:

where $s_{l_{1}}$ and $s_{l_{2}}$ are the ground truth confidence scores of corresponding relation facts in the uncertain KG.

This equation indicates that the ground rule in Example 4.2 is completely satisfied when $f(l_{3})$, the estimated confidence score of (college, synonym institute), is above 0.85. When $f(l_{3})$ is under 0.85, the smaller $f(l_{3})$ is, the larger loss we have. In other words, a bigger confidence score is preferable. In the above example, we can see that the embedding-based confidence score for this unseen relation fact, $f(l_{3})$, will affect the loss function, and it is desirable to learn embeddings that minimize these losses. Note that if we simply treat the unseen relation $l_{3}$ as false and use MSE (Mean Squared Error) as the loss, the loss would be $f(l_{3})^{2}$, which is in favor of a lower confidence score mistakenly.

Moreover, we add a rule to penalize the predicted confidence scores of all unseen relation facts, which can be considered as a prior knowledge, i.e., any unseen relation fact has a low probability to be true. Formally, for an unseen relation fact $l=(h,r,t)\in\mathcal{L}^{-}$, we have a ground rule $\gamma_{0}$:

According to Eq. (8) and (10), its distance to satisfaction $d_{\gamma_{0}}$ is derived as:

3 Embedding Uncertain KGs

In this subsection, we present the objective function of uncertain KG embeddings.

Let $\mathcal{L}^{+}$ be the set of observed relation facts, the goal is to minimize the mean squared error (MSE) between the ground truth confidence score $s_{l}$ and our prediction $f(l)$ for each relation $l\in\mathcal{L}^{+}$:

Loss on unseen relation facts

Let $\mathcal{L}^{-}$ be the sampled set of unseen relations, and $\Gamma_{l}$ be the set of ground rules with $l$ as the rule head, the goal is to minimize the distance to rule satisfaction for each triple $l$. In particular, we choose to use the square of the distance as the following loss (?):

where $\psi_{\gamma}(f(l))$ denotes the weighted distance to satisfaction $w_{\gamma}d_{\gamma}$ of the rule $\gamma$ as a function of $f(l)$ where $w_{\gamma}$ is a hand-crafted weight for the rule $\gamma$.

Note that when $l$ is only covered by $\gamma_{0}:\neg l$, we have $\sum_{\gamma\in\Gamma_{l}}|\psi_{\gamma}(f(l))|^{2}=|f(l)|^{2}$, which is essentially the MSE loss by treating unseen relation facts as false.

The Joint Objective Function

Combining Eq. (13) and (14), we obtain the following joint objective function:

Similar to deterministic KG embedding algorithms, we sample unseen relations by corrupting the head and the tail for observed relation facts to generate $\mathcal{L}^{-}$ during training.

We give two model variants that differ in the choice of $f(l)$. We refer to the variant that adopts Equation (3) as UKGElogi and name the one using Equation (4) as UKGErect.

Experiments

In this section, we evaluate our models on three tasks: confidence prediction, relation fact ranking, and relation fact classification.

The evaluation is conducted on three datasets named as CN15k, NL27k, and PPI5k, which are extracted from ConceptNet, NELL, and the Protein-Protein Interaction Knowledge Base STRING (?) respectively. CN15k matches the number of nodes with FB15k (?) - the widely used benchmark dataset for deterministic KG embeddings (?; ?; ?), while NL27k is a larger dataset. PPI5k is a denser graph with fewer entities but more relation facts than the other two. Table 1 gives the statistics of the datasets, and more details are introduced below.

CN15k is a subgraph of the commonsense KG ConceptNet. This subgraph contains 15,000 entities and 241,158 uncertain relation facts in English. The original scores in ConceptNet vary from 0.1 to 22, where 99.6% are less than or equal to 3.0. For normalization, we first bound confidence scores to $x\in[0.1,3.0]$, and then applied the min-max normalization on $\log x$ to map them into [0.1, 1.0].

NL27

NL27k is extracted from NELL (?), an uncertain KG obtained from webpage reading. NL27k contains 27,221 entities, 404 relations, and 175,412 uncertain relation facts. In the process of min-max normalization, we search for the lower boundary from 0.1 to 0.9. We have found out that normalizing the confidence score to interval $[0.1,1]$ yields best results.

PPI5k

The Protein-Protein Interaction Knowledge Base STRING labels the interactions between proteins with the probabilities of occurrence. PPI5k is a subset of STRING that contains 271,666 uncertain relation facts for 4,999 proteins and 7 interactions.

In an uncertain KG, a relation fact is considered strong if its confidence score $s_{l}$ is above a KG-specific threshold $\tau$. Here we set $\tau=0.85$ for both CN15k and NL27k. We follow the instructions from (?) and set $\tau=0.70$ for PPI5k. Under this setting, 20.4% of relation facts in CN15k, 20.1% of those in NL27k, and $12.4\%$ of those in PPI5k are considered strong.

2 Experimental Setup

We split each dataset into three parts: 85% for training, 7% for validation, and 8% for testing. To test if our model can correctly interpret negative links, we add the same amount of negative links as existing relation facts into the test sets.

We use Adam optimizer (?) for training, for which we set the exponential decay rates $\beta_{1}=0.9$ and $\beta_{2}=0.99$. We report results for all models respectively based on their best hyperparameter settings. For each model, the setting is identified based on the validation set performance. We select among the following sets of hyper-parameter values: learning rate $lr\in$ {0.001, 0.005, 0.01}, dimensionality $k\in$ {64, 128, 256, 512}, batch size $b\in$ {128, 256, 512, 1024}, The $L_{2}$ regularization coefficient $\lambda$ is fixed as 0.005. Training was stopped using early stopping based on MSE on the validation set, computed every 10 epochs. The best hyper-parameter combinations on CN15k and NL27k are $\{lr=0.001,k=128\}$ and $b=128$ for UKGErect, $b=512$ for UKGElogi. On PPI5k they are $\{lr=0.001,k=128,b=256\}$ for both variants.

3 Logical Rule Generation

Our model requires additional input as logical rules for PSL reasoning. We heuristically create candidate logical rules by considering length-2 paths (i.e., ($E_{1}$,$R_{1}$,${E_{2}}$) $\wedge$ ($E_{2}$,$R_{2}$,${E_{3}}$) $\rightarrow$ ($E_{1}$,$R_{3}$,${E_{3}}$)) and validate them by hit ratio, i.e. the proportion of relation facts implied by the rule to be truly existent in the KG. The higher ratio implies that the rule is more convincing. When grounding out the logical rules, to guarantee the quality of the ground rules, we only adopt observed strong relation facts in our rule body. We eventually create 3 logical rules for CN15k, 4 for NL27k, and 1 for PPI5k. Table 2 gives some examples of the logical rules and their hit ratios. How to systematically create more promising logical rules will be considered as future work.

4 Baselines

Three types of baselines are considered in our comparison, which include (i) deterministic KG embedding models TransE (?), DistMult (?) and ComplEx (?), (ii) an uncertain graph embedding model URGE (?), and (iii) UKGEn- and UKGEp- that are two simplified versions of our model.

Deterministic KG Embedding Models. TransE, DistMult, and ComplEx have demonstrated high performance on deterministic KGs. Only the high-confidence relation facts from KGs are used for training. For each KG, we have a KG-specific confidence score threshold $\tau$ to distinguish the high-confidence relation facts from the low-confidence ones, which will be discussed later in Section 5.7. These models cannot predict confidence scores. We compare our methods to them only on the ranking and the classification tasks. For the same reason, the early stopping is based on mean reciprocal rank (MRR) on the validation set. We adopt the implementation given by (?) and choose the best hyper-parameters following the same grid search procedure. This implementation uses (?) for optimization. The best hyper-parameter combinations on CN15k and NL27k are $b=1024$, {$lr=0.01,k=128$} for TransE and $\{lr=0.05,k=256\}$ for DistMult and ComplEx. On PPI5k they are $lr=0.1$, {$k=128,b=512$} for DistMult and {$k=256,b=1024$} for TransE and ComplEx.

Uncertain Graph Embedding Model. URGE is proposed very recently to embed uncertain graphs. However, it cannot deal with multiple types of relations in KGs, and it only produces node embeddings. We simply ignore relation types when applying URGE to our datasets. We adopt its first-order proximity version as our tasks focus on the edge relations between nodes.

Two Simplified Versions of Our Model. To justify the use of negative links and PSL reasoning in our model, we propose two simplified versions of UKGErect , called UKGEn- and UKGEp-. In UKGEn-, we only keep the observed relation facts and remove negative sampling, and in UKGEp-, we remove PSL reasoning and use the MSE loss for unseen relation facts.

5 Confidence Prediction

The objective of this task is to predict confidence scores of unseen relation facts.

For each uncertain relation fact $(l,s_{l})$ in the test set, we predict the confidence score of $l$ and report the mean squared error (MSE) and mean absolute error (MAE).

Results

Results are reported in Table 3. Both our variants UKGErect and UKGElogi outperform the baselines URGE, UKGEn-, and UKGEp-, since URGE only takes node proximity information and cannot model the rich relations between entities, and UKGEn- does not adopt negative sampling and cannot recognize negative links. The better results of UKGErect than UKGEp- demonstrate that introducing PSL into embedding learning can enhance the model performance. Between the two model variants, UKGErect results in smaller MSE and MAE than UKGElogi. We notice that all the models achieve much smaller MSE on PPI5k than CN15k and NL27k. We hypothesize that this is because the much higher density of PPI5k facilitates embedding learning (?).

6 Relation Fact Ranking

The next task focuses on ranking tail entities in the right order for the query $(h,r,\underline{?t})$.

For a query $(h,r,\underline{?t})$, we rank all the entities in the vocabulary as tail candidates and evaluate the ranking performance using the normalized Discounted Cumulative G ain (nDCG) (?). We define the gain in retrieving a relevant tail $t_{0}$ as the ground truth confidence score $s_{(h,r,t_{0})}$. We take the mean nDCG over the test query set as our ranking metric. We report the two versions of nDCG that use linear gain and exponential gain respectively. The exponential gain version puts stronger emphasis on highly relevant results.

Results

Table 4 shows the mean nDCG over all test queries for all compared methods. Though TransE, DistMult, and ComplEx do not encode the confidence score information, they maximize the plausibility of all observed relation facts and therefore rank these existing relation facts high. We observe that DistMult and ComplEx have considerably better performance than TransE, as TransE does not handle 1-to-N relations well. ComplEx embeds entities and relations in the complex domain and handles asymmetric relations better than DistMult. It achieves the best results among the deterministic KG embedding models on this task. As UKGEn- removes negative sampling from the loss function, it cannot distinguish the negative links from existing relation facts and results in the worst performance. UKGEp- yields slightly worse performance than UKGErect. Besides ranking the existing relation facts highly, our models also preserve the order of the observed relation facts and thus achieve higher nDCG scores. Both UKGErect and UKGElogi outperform all the baselines under all settings, while UKGElogi yields higher nDCG on all three datasets than UKGErect. Considering the confidence prediction results of UKGElogi in Section 5.5, we hypothesize that the easy saturation of logistic function allows UKGElogi to better distinguish negative links from true relation facts, while this feature compromises its ability to fit confidence scores more precisely.

Case study

Table 5 gives some examples of relation fact ranking results by UKGElogi. Given a query $(h,r,\underline{?t})$, the top 4 predicted tails and true tails are given, sorted by their scores in descending order. The predictions are consistent with our common-sense. It is worth noting that some quite reasonable unseen relation facts such as hotel is used for relaxing, can be predicted correctly. In other words, our proposed approach can be potentially used to infer new knowledge from the observed ones with reasonable confidence scores, which may shed light on another line of future study.

7 Relation Fact Classification

This last task is a binary classification task to decide whether a given relation fact $l$ is a strong relation fact or not. A relation fact is considered strong if its confidence score $s_{l}$ is above a KG-specific threshold $\tau$. The embedding models need to distinguish relation facts in the KG from negative links and high-confidence relation facts from low-confidence ones.

We follow a procedure that is similar to (?). Our test set consists of relation facts from the KG and randomly sampled negative links equally. We divide the test cases into two groups, strong and weak/false, by their ground truth confidence scores. A test relation fact $l$ is strong when $l$ is in the KG and $s_{l}>\tau$, otherwise weak/false. We fit a logistic regression classifier as a downstream classifier on the predicted confidence scores.

Results

F-1 scores and accuracies are reported in Table 6. These results show that our two model variants consistently outperform all baseline models. The deterministic KG models can distinguish the existing relation facts from negative links, but they do not leverage the confidence information and cannot recognize the high-confidence ones. URGE does not encode the rich relations. Although UKGEn- fits confidence scores in the KG, it cannot correctly interpret negative links as false. Consistent with the previous two tasks, the performance of UKGEp- is worse than UKGErect.

Conclusion and Future Work

To the best of our knowledge, this paper is the first work on embedding uncertain knowledge graphs. Our model UKGE effectively preserves both the relation facts and uncertainty information in the embedding space of KG. We propose two variants of our model and conduct extensive experiments on relation fact confidence score prediction, relation fact ranking, and relation fact classification. The results are very promising. For future work, we will study how to systematically generate reasonable logical rules and test its impact on embedding quality. We are interested in extending UKGE for uncertain knowledge extraction from text.

This work is partially supported by NSF III-1705169, NSF CAREER Award 1741634, Snapchat gift funds, and PPDai gift fund.

References