Open Information Extraction systems extract (subject text, relation text, object text) triples from raw text. Some triples are textual versions of facts, i.e., non-canonicalized mentions of entities and relations. In this paper, we investigate whether it is possible to infer new facts directly from the open knowledge graph without any canonicalization or any supervision from curated knowledge. For this purpose, we propose the open link prediction task, i.e., predicting test facts by completing (sub-ject text, relation text, ?) questions. An evaluation in such a setup raises the question if a correct prediction is actually a new fact that was induced by reasoning over the open knowledge graph or if it can be trivially explained. For example, facts can appear in different paraphrased textual variants, which can lead to test leakage. To this end, we propose an evaluation protocol and a methodology for creating the open link prediction benchmark OLPBENCH . We performed experiments with a prototypical knowledge graph embedding model for open link prediction. While the task is very challenging, our results suggests that it is possible to predict genuinely new facts, which can not be trivially explained. A knowledge graph (KG) (Hayes-Roth, 1983) is a set of (subject, relation, object)-triples, where the subject and object correspond to vertices, and relations to labeled edges. In curated KGs, each triple is fully disambiguated against a fixed vocabulary of entities 1 and relations. An application for KGs, for example, is the problem of drug discovery based on bio-medical knowledge (Mohamed et al., 2019). The construction of a curated bio-medical KG, which is required for 1 For brevity, entities denotes both entities (e.g. Prince) and concepts (e.g. musician) throughout the paper. such an approach, is challenging and constrained by the available amount of human effort and domain expertise. Many tools that could assist humans in KG construction (e.g., an entity linker) need a KG to begin with. Moreover, current methods for KG construction often rely on the rich structure of Wikipedia, such as links and infoboxes, which are not available for every domain. Therefore, we ask if it is possible to make predictions about, for example, new drug applications from raw text without the intermediate step of KG construction. Open information extraction systems (OIE) (Et-zioni et al., 2011) automatically extract (sub-ject text, relation text, object text) -triples from unstructured data such as text. We can view OIE data as an open knowledge graph (OKG) (Galarraga et al., 2014), in which vertices correspond to mentions of entities and edges to open relations (see Fig. 1). Our overarching interest is whether and how we can reason over an OKG without any canonicalization and without any supervision on its latent factual knowledge. The focus of this study are the challenges of benchmarking the inference abilities of models in such a setup. A common task that requires reasoning over a Open Link Prediction Link Prediction NBC ? KG is link prediction (LP). The goal of LP is to predict missing facts in a KG. In general, LP is defined as answering questions such as (NBC, headquarterIn, ?) or (?, headquarterIn, NewYorkCity) ; see Fig. 2a. In OKGs, we define open link prediction (OLP) as follows: Given an OKG and a question consisting of an entity mention and an open relation, predict mentions as answers. A predicted mention is correct if it is a mention of the correct answer entity. For example, given the question (NBC-TV, has office in, ?) , correct answers include NYC and New York ; see Fig. 2b). To evaluate LP performance, the LP model is trained on known facts and evaluated to predict unknown facts, i.e., facts not seen during training. A simple but problematic way to transfer this approach to OKGs is to sample a set of evaluation triples from the OKG and to use the remaining part of the OKG for training. To see why this approach is problematic, consider the test triple (NBC-TV, has office in, New York) and suppose that the triple (NBC, has headquarter in, NYC) is also part of the OKG. The latter triple essentially leaks the test fact. If we do not remove such facts from the training data, a successful models only paraphrases known facts but does not perform reasoning, i.e., does not predict genuinely new facts. Furthermore, we also want to quantify if there are other trivial explanations for the prediction of an evaluation fact. For example, how much can be predicted with simple popularity statistics, i.e., only the mention, e.g. (NBC-TV, ?) , or only the relation, e.g. (has office in, ?) . Such non-relational information also does not require reasoning over the graph. To experimentally explore whether it is possible to predict new facts, we focus on knowledge graph embedding (KGE) models (Nickel et al., 2016), which have been applied successfully to LP in KGs. Such models can be easily extended to handle the surface forms of mentions and open relations. Our contributions are as follows: We propose the OLP task, an OLP evaluation protocol, and a method to create an OLP benchmark dataset. Using the latter method, we created a large OLP benchmark called OLPBENCH , which was derived from the state-of-the-art OIE corpus OPIEC (Gash-teovski et al., 2019). OLPBENCH contains 30 M open triples, 1 M distinct open relations and 2 . 5 M distinct mentions of approximately 800 K entities. We investigate the effect of paraphrasing and nonrelational information on the performance of a prototypical KGE model for OLP. We also investigate the influence of entity knowledge during model selection with different types of validation data. For training KGE models on such large datasets, we describe an efficient training method. In our experiments, we found the OLP task and OLPBENCH to be very challenging. Still, the KGE model we considered was able to predict genuinely new facts. We also show that paraphrasing and non-relational information can indeed dilute performance evaluation, but can be remedied by appropriate dataset construction and experimental settings. OKGs can be constructed in a fully automatic way. They are open in that they do not require a vocabulary of entities and relations. For this reason, they can capture more information than curated KGs. For example, different entity mentions can refer to different versions of an entity at different points of time, e.g., Senator Barack Obama and Pres-ident Barack Obama . Similarly, relations may be of varying specificity: headquarterIn may be expressed directly by open relations such as be based in or operate from but may also be implied by relocated their offices to . In contrast to KGs, OKGs contain rich conceptual knowledge. For example, the triple (a class action lawsuit, is brought by, shareholders) does not directly encode entity knowledge, although it does provide information about entities that link to a class action lawsuit or shareholders . OKGs tend to be noisier and the factual knowledge is less certain than in a KG, however. They NBC-TV Marseille Los Angeles has office in ? can not directly replace KGs. OKGs have mostly been used as a weak augmentation to KGs, e.g., to infer new unseen entities or to aid link prediction (see App. A for a comprehensive discussion of related work). Much of prior work that solely leverages OKGs without a reference KGand therein is closest to our workfocused on canonicalization and left inference as a follow-up step (Cohen et al., 2000, inter alia). In contrast, we propose to evaluate inference in OKGs with OLP directly. The open link prediction task is based on the link prediction task for KGs (Nickel et al., 2016), which we describe first. Let E be a set of entities, R be a set of relations, and T  E  R  E be a knowledge graph. Consider questions of the form q h = (? , k, j ) or q t = ( i, k, ?) , where i, j  E is a head and tail entity, respectively, and k  R is a relation. The link prediction problem is to provide answers that are correct but not yet present in T . In OKGs, only mentions of entities and open relations are observed. We model each entity mention and each open relation as a non-empty sequence of tokens from some vocabulary V (e.g., a set of words). Denote by M = V + the set of all such sequences and observe that M is unbounded. An open knowledge graph T  MMM consists of triples of form ( i, k, j ) , where i, j  M are head and tail entity mentions , resp., and k  M is an open relation . Note that we overload notation for readability: i , j , and k refer to entity mentions and open relations in OKGs, but to disambiguated entities and relations in KGs. The intended meaning will always be clear from the context. We denote by M ( E ) and M ( R ) the sets of entity and relations present in T , respectively. The open link prediction task is to predict new and correct answers to questions ( i, k, ?) or (? , k, j ) . Answers are taken from M ( E ) , whereas questions may refer to arbitrary mentions of entities and open relations from M . For example, for the question ( NBC-TV ,  has office in , ?), we expect an answer from the set of mentions { New York , NYC , . . . } of the entity NewYorkCity . Informally, an answer ( i, k, j ) is correct if there is a correct triple ( e 1 , r, e 2 ) , where e 1 and e 2 are entities and r is a relation, such that i , j , and k are mentions of e 1 , e 2 , and r , respectively. To describe our proposed evaluation protocol, we first revisit the most commonly used methodology to evaluate link prediction methods for KGs, i.e., the entity-ranking protocol (Bordes et al., 2013). Then, we discuss its adaptation to OLP, which we call the mention-ranking protocol (see Fig. 3). KGs and entity ranking. For each triple z = ( i, k, j ) in the evaluation data, a link prediction model ranks the answers for two questions, q t ( z ) = ( i, k, ?) and q h ( z ) = (? , k, j ) . The model is evaluated based on the ranks of the correct entities j and i ; this setting is called raw . When true answers for q t ( z ) and q h ( z ) other than j and i are filtered from the rankings, then the setting is called filtered . OKGs and mention ranking. In OLP, the model predicts a ranked list of mentions. But questions might have multiple equivalent true answers, i.e., answers that refer to the same entity but use different mentions. Our evaluation metrics are based on the highest rank of a correct answer mention in the ranking. For the filtered setting, the mentions of known answer entities other than the evaluated entity are filtered from the ranking. This mention-ranking protocol thus uses knowledge of alternative mentions of the entity in the evaluation triple to obtain a suitable ranking. The mention-ranking protocol therefore requires (i) ground truth annotations for the entity mentions in the head and tail of the evaluation data, and (ii) a comprehensive set of mentions for these entities. An OLP benchmark should enable us to evaluate a model's capability to predict genuinely new facts, i.e., facts can not be trivially derived. Due to the na-ture of OKGs, paraphrasing of facts may leak facts from validation and test data into training, making the prediction of such evaluation facts trivial. Nevertheless, the creation of training and validation data should require as little human effort as possible so that the methodology can be readily applied to new domains. Our mention-ranking protocol uses knowledge about entities for disambiguation (of the evaluation data, not the training data), however, which requires human effort to create. We investigate experimentally to what extent this entity knowledge is necessary for model selection and, in turn, how much manual effort is required to create a suitable validation dataset. In the following, we describe the source dataset of OLPBENCH and discuss how we addressed the points above to create evaluation and training data. OLPBENCH is based on OPIEC (Gashteovski et al., 2019), a recently published dataset of OIE triples that were extracted from the text of English Wikipedia with the state-of-the-art OIE system MinIE (Gashteovski et al., 2017). We used a subset of 30M distinct triples, comprised of 2.5M entity mentions and 1M open relations. In 1.25M of these triples, the subject and the object contained a Wikipedia link. Fig. 4 shows how a Wikipedia link is used to disambiguate a triple's subject and object mentions. Tab. 1 shows an excerpt from the unlinked and linked triples. For the evaluation protocol, we collected a dictionary, where each entity Was the second ship of the United States Navy to be named for William Conway, who distinguished himself during the Civil War. From the source dataset, we created validation and test data with the following requirements: Data quality. The evaluation data should be challenging, and noise should be limited as much as possible. We chose a pragmatic and easy heuristic: we did not consider short relations with less than three tokens as candidates for sampling evaluation data. This decision was based on the following observations: (i) Due to the OPIEC's extractions, short relationse.g. (kerry s. walters, is, professor emeritus) are often subsumed by longer relationse.g. (kerry s. walters, is professor emeritus of, philosophy) , which would always lead to leakage from the longer relation to the shorter relation. (ii) Longer relations are less likely to be easily captured by simple patterns that are already successfully used by KG construction methods, e.g. (elizabeth of hungary, is the last member of, the house of arpad) . We conjecture that long relations are more interesting for evaluation to measure progress in reasoning with OKG data. (iii) The automatically extracted entity annotations were slightly noisier for short relations; e.g., (marc anthony, is singer) had the object entity annotation SinFrenos . Human effort for data creation. The mention-ranking protocol uses knowledge about entities for disambiguation. We want to experimentally quantify the influence of this entity knowledge on model selection, i.e., whether entity knowledge is necessary to find a good model. If so, human expertise is necessary to create the validation data. While our goal is to require almost no human domain expertise to learn a good model, the size of validation data is much smaller than the size of the training data. Therefore, this effortif helpfulmay be subject relation object subject mentions object mentions U n li n ke d conway has plot henry s. Entity links are discarded, i.e., the mention-ranking protocol cannot be used for validation. To evaluate LP models for KGs, evaluation facts are generated by sampling from the KG. Given an evaluation triple ( i, k, j ) , the simplest action to avoid leakage from the training data is to remove only this evaluation triple from training. For KGs, it was observed this simple approach is not satisfactory in that evaluation answers may still leak and thus can be trivially inferred (Toutanova et al., 2015; Dettmers et al., 2018). For example, an evaluation triple ( a, siblingOf, b ) can be trivially answered with the training triple ( b, siblingOf, a ) . In OKGs, paraphrases of relations pose additional sources of leakage. For example, the relations is in and located in may contain many of the same entity pairs. For evaluation triple ( i, k, j ) , such leakage can be prevented by removing any other relation between i and j from the training data. However, individual tokens in the arguments or relations may also cause leakage. For example, information about test triple ( NBC-TV, has office in, NYC ) is leaked by triples such as ( NBC Television, has NYC offices in, Rockefeller Plaza ) even though it has different arguments. Fig. 5 visualizes this example. We use three levels of leakage removal from training: SIMPLE , BASIC , and THOROUGH . To match evaluation triple ( i, k, j ) with training triples, we ignored word order and stopwords. SIMPLE removal. Only the triple ( i, k, j ) is removed. Triples with alternative mentions for i or j are kept. THOROUGH removal. Additionally to BASIC removal, we also remove triples from training matched by the following patterns. The patterns are explained with the example (J. Smith, is defender of, Liverpool) : (a) ( i,  , j ) and ( j,  , i ) . E.g., matches (J. Smith, is player of, Liverpool) . (b) ( i, k + j,  ) and (  , k + i, j ) . 2 E.g., matches (J. Smith, is Liverpool's defender on, Satur-day) . (c) ( i + k + j,  ,  ) and (  ,  , i + k + j ) . E.g., matches (Liverpool defender J. Smith, kicked, the ball) . For OLPBENCH , THOROUGH removed 196 , 717 more triples from the OKG than BASIC . Note that this yields three different training data sets. KG embedding (KGE) models have been successfully applied for LP in KGs, and they can be easily extended to handle surface forms, i.e., mentions and open relations. We briefly describe KGE models and their extension. Knowledge Graph Embedding (KGE) model. A KGE model (Nickel et al., 2016) associates an embedding with each entity and each relation. The embeddings are dense vector representations that are learned with an LP objective. They are used to compute a KGE model-specific score s ( i, k, j ) for a triple ( i, k, j ) ; the goal is to predict high scores for true triples and low scores for wrong triples. KGE model with composition. For our experiments, we considered composition functions to create entity and relation representations from the tokens of the surface form. Such an approach has been used, for example, by Toutanova et al. (2015) to produce open relation embedding via a CNN. A model that reads the tokens of mentions and open relations can, in principle, handle any mention and open relation as long as the tokens have been observed during training. We use a general model architecture that combines a relational model and a composition func-( Jamie Carragher, is defender of, Liverpool ) mention/relation tokens token embeddings mention/relation embeddings score for triple Figure 6: KGE model with composition. tion, see Fig. 6. Formally, let V ( E ) + be the set of non-empty token sequences over the token vocabulary V ( E ) of entity mentions. We denote by d, o  N + the size of the embeddings of entities and relations. We first embed each entity mention into a continuous vector space via an entity mention embedding function f : V ( E ) +  R d . Similarly, each open relation is embedded into a continuous vector space via a relation embedding function g : V ( R ) +  R o . The embeddings are then fed into a relational scoring function RM : R d  R o  R d  R . Given a triple ( i, k, j ) , where i, j  V ( E ) + and k  V ( R ) + , our model computes the final score as s ( i, k, j ) = RM ( f ( i ) , g ( k ) , f ( j ) ) . In our experimental study, we investigated whether a simple prototypical OLP model can predict genuinely new facts or if many successful predictions can be trivially explained by leakage or nonrelational information. Our goal was to study the effectiveness and necessity of the mention-ranking protocol and leakage removal, and how much human effort is necessary to create suitable validation data. Finally, we inspected data and model quality. We first describe the models and their training, then the performance metrics, and finally the evaluation. In our experimental results, model performance dropped by  25% with THOROUGH leakage removal so that leakage due to paraphrasing is indeed a concern. We also implemented two diagnostic models that use non-relational information (only parts of a triple) to predict answers. These models reached  2025% of the prototypical model's performance, which indicates that relational modelling is important. In our quality and error analysis, we found that at least 74% of the prediction errors were not due to noisy data. A majority of incorrectly predicted entity mentions have a type similar to the one of the true entity. Prototypical model. We use COMPLEX (Trouil-lon et al., 2016) as relational model, which is an efficient bilinear model and has shown state-of-the-art results. For the composition functions f and g , we used an LSTM (Hochreiter and Schmidhuber, 1997) with one layer and the hidden size equivalent to the token embedding size. We call this model COMPLEX-LSTM. 3 Diagnostic models. To expose potential biases in the data, we employ two diagnostic models to discover how many questions can simply be answered without looking at the whole question, i.e., by exploiting non-relational information . Given question ( i, k, ?) , the model PREDICT-WITH-REL considers ( r, ?) for scoring. E.g., for question (Jamie Carragher, is defender of, ?) , we actually ask (is defender of, ?) . This is likely to work reasonably for relations that are specific about the potential answer entities; e.g., predicting popular football clubs for (is defender of, ?) . The model uses scoring functions s t : R o  R d  R and s h : R d  R o  R for questions ( i, k, ?) and (? , k, j ) respectively: s t ( k, e ) = g ( k ) T f ( j ) , s h ( i, k ) = f ( i ) T g ( k ) Likewise, the PREDICT-WITH-ENT model ignores the relation by computing a score for pair ( i, j ) . We use s e ( i, j ) = f ( i ) T f ( j ) Training. Performance metrics. For evaluating a model's predictions, we use the ranking metrics mean reciprocal rank (MRR) and HITS@k. MRR is sensitive to the top-3 ranks with rapidly decaying reward, 3 In a preliminary study, we investigated COMPLEX , ANALOGY , DISTMULT and RESCAL as relational models. COMPLEX was the most efficient and best performing model. For composition functions, we also investigated unigram pooling, bi-gram pooling with CNNs, self-attention and LSTMs. Here LSTMs worked well consistently. See App. E for additional results. while HITS@ k equally rewards correct answers in the topk ranks. See App. D for a more formal definition of MRR and HITS@k. The ranks are based on mention ranking for VALID-LINKED and TEST and on entity-ranking (treating distinct mentions as distinct entities) for VALID-ALL and VALID-MENTION . Influence of leakage. In Tab. 2, we observed that BASIC leakage removal of evaluation data lowers the performance of all models considerably in contrast to the SIMPLE leakage removal. With the THOROUGH leakage removal, performace drops further; e.g., HITS@50 performance dropped by  25% from SIMPLE . This confirms our conjecture that leakage can trivially explain some successful predictions. Most predictions, however, cannot be explained by paraphrasing leakage. Influence of non-relational information. In Tab. 2, we see that PREDICT-WITH-ENT , which essentially learns popularity statistics between entity mentions, has no success on the evaluation data. However, PREDICT-WITH-REL reaches  20  25% of HITS@50 performance of COMPLEXLSTM by simply predicting popular mentions for a relation, even in the THOROUGH setting. Effectiveness of mention-ranking. Tab. 3 shows validation results for the three types of validation data for COMPLEX-LSTM and THOROUGH removal. The evaluation protocol has access to alternative mentions only in VALID-LINKED , but not in VALID-ALL and VALID-MENTION . Clearly, using VALID-LINKED results in higher metrics when models associate different mentions to an answer entity. Influence of model selection. The THOROUGH block of Tab. 2 shows the results for model selection based on VALID-ALL , VALID-MENTION or VALID-LINKED . In VALID-ALL , many triples contain common nouns instead of entity mentions, while in VALID-MENTION or VALID-LINKED triples have entity mentions in both arguments. Model selection based on VALID-ALL clearly picked a weaker model than model selection based on VALID-LINKED , i.e., it led to a drop of  35% of HITS@50 performance. However, there is no improvement when we pick a model based on VALIDLINKED versus VALID-MENTION . Thus, computing the MRR using alternative entity mentions did not improve model selection, even thoughas Tab. 3 showsthe mention-ranking protocol gives more credit when alternative mentions are ranked higher. Our results suggest that it may suffice to use validation data that contains entity mentions but avoid costly entity disambiguation. Overall performance. In Tab. 2 we observed that performance numbers seem generally low. For comparison, the HITS@10 of COMPLEX on FB15k-237a standard evaluation dataset for LP in curated KGslies between 45% and 55%. We conjecture that this drop may be due to: (i) The Leakage Model Removal Model Selection MRR HITS@1 HITS@10 HITS@50 COMPLEX-LSTM ALL 2.9 1.8 5.0 8.9 THOROUGHCOMPLEX-LSTM MENTION 3.6 2.0 6.5 13.0 COMPLEX-LSTM LINKED 4.2 2.3 7.5 14.9 Table 3: Validation results. level of uncertainty and noise in the training data, i.e., uninformative or even misleading triples in OKGs (Gashteovski et al., 2019). (ii) Our evaluation data is mostly from the more challenging long tail. (iii) OKGs might be fragmented, thus inhibiting information flow. Also, note that the removal of evaluation data from training removes evidence for the evaluated long-tail entities. (iv) Naturally, in LP, we do not know all the true answers to questions. Thus, the filtered rank might still contain many true predictions. In OLP, we expect this effect to be even stronger, i.e., the filtered ranking metrics are lower than in the KG setting. Still, like in KG evaluation, with a large enough test set, the metrics allow for model comparisons. Model and data errors. We inspected predictions for VALID-LINKED from COMPLEX-LSTM trained on THOROUGH . We sampled 100 prediction errors, i.e., triples for which no correct predicted mention appeared in the filtered top-50 rank. We classified prediction errors by inspecting the top-3 ranks and judged their consistency. We classified triple quality judging the whole triple. We counted an error as correct sense / wrong entity , when the top-ranked mentions are semantically sensible, i.e. for (Irving Azoff, was head of, ?) the correct answer would be MCA Records , but the model predicted other record companies. We counted an error as wrong sense whenfor the same examplethe model mostly consistently predicted other companies or music bands, but not other record companies. If the predictions are inconsistent, we counted the error as noise . An additional quality assessment is the number of wrong triples caused by extraction errors in OPIEC, e.g., (Finland, is the western part of, the balkan peninsula) , (William Macaskill, is vice-president of, giving) , or errors in alternative mentions. We also looked for generic mentions in the evaluation data. Such mentions contain mostly conceptual knowledge like in (computer science, had backgrounds in, mathematics) . Other generic triples, like (Patrick E., joined the team in, the season) , have conceptual meaning, but miss context to disambiguate the season . The results in Tab. 4 suggest that the low performance in the experiments is not due to noisy evaluation data. 74% of the examined prediction errors on VALID-LINKED contained correct, nongeneric facts. The shown model errors raise the question of whether there is enough evidence in the data to make better predictions. We proposed the OLP task and a method to create an OLP benchmark. We created the large OLP benchmark OLPBENCH , which will be made publicly available 4 . We investigated the effect of leakage of evaluation facts, non-relational information, and entity-knowledge during model selection using a prototypical open link prediction model. Our results indicate that most predicted true facts are genuinely new. The first author would like to gratefully thank the NVIDIA Corporation for the donation of a TITAN Xp GPU that was used in this research.
abstain abstain objective objective abstain abstain objective method objective abstain abstain abstain abstain abstain abstain abstain objective abstain result abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain objective abstain abstain abstain abstain abstain objective method abstain abstain objective objective method result objective result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method abstain method abstain abstain abstain abstain method method abstain abstain method abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain method abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain result abstain abstain result abstain abstain result abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective method objective objective other