{'fraction_non_alphanumeric': 0.04768840092613339, 'fraction_numerical': 0.01646874299798342, 'mean_word_length': 4.26420287006094, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Recurrent One-Hop Predictions for Reasoning over Knowledge Graphs

Large scale knowledge graphs (KGs) such as Freebase are generally incomplete. Reasoning over multi-hop (mh) KG paths is thus an important capability that is needed for question answering or other NLP tasks that require knowledge about the world. mh-KG reasoning includes diverse scenarios, e.g., given a head entity and a relation path, predict the tail entity; or given two entities connected by some relation paths, predict the unknown relation between them. We present ROPs, recurrent one-hop predictors, that predict entities at each step of mh-KB paths by using recurrent neural networks and vector representations of entities and relations, with two benefits: (i) modeling mh-paths of arbitrary lengths while updating the entity and relation representations by the training signal at each step; (ii) handling different types of mh-KG reasoning in a unified framework. Our models show state-of-the-art for two important multi-hop KG reasoning tasks: Knowledge Base Completion and Path Query Answering.


Introduction
Natural language understanding (NLU) is impossible without knowledge about the world. Large scale knowledge graphs (KGs) such as Freebase (Bollacker et al., 2008) are structures that store world knowledge. Unfortunately, KGs suffer from incomplete coverage (Min et al., 2013); e.g., Freebase contains Brandon Lee, but not his ethnicity.
The knowledge in KGs needs to be expanded to cover more facts; reasoning is one way to do so. For example, we could infer that (Microsoft, ?, United States) instantiates "CountryOfHQ" given the facts (Microsoft, IsBasedIn, Seattle) and (Seattle, LocatedIn, United States); or we could infer Brandon Lee's ethnicity from his parents' ethnicity, i.e., answering the query (Brandon Lee, Ethnicity, ?) by facts (Brandon Lee, Father, Bruce Lee) and (Bruce Lee, Ethnicity, Chinese). We refer to the two reasoning examples as "knowledge base completion (KBC)" and "path query answering (PQA)", respectively.
The most successful approach for modeling KGs is the embedding approach. It embeds KG elements (entities and relations) into low-dimensional dense vectors; controlling the dimensionality of the vector space forces generalization to new facts (Nickel et al., 2011).
In this work, we are mainly interested in three issues. (i) Compared to modeling one-hop KG paths, a bigger challenge is how to model multi-hop paths, e.g., the path query (U.S.A, president→spouse→born in, ?) for the question "Where was the first lady of the United States born?" (ii) How can we address different KG reasoning problems driven by multi-hop paths in a universal paradigm rather than via different systems? (iii) How can we combine specific multi-hop KG reasoning tasks with generic KG representation learning, so that KG representation learning can either stand alone or be incorporated into diverse multi-hop KG-related NLU problems. We get inspiration from following two types of work.
First, prior work in KG reasoning. Guu et al. (2015) extend one-hop reasoning regimes such as TransE (Bordes et al., 2013) to multi-hop PQA. However, these basic one-hop models do not encode the relation order when used in compositional training schemes. For example, path query q 1 = (h, r 1 →r 2 →· · · →r k , ?) will be encoded into the same embedding as path query q 2 = (h, r 2 →r 1 →· · · →r k , ?), resulting in (often incorrect) prediction of the same tail entity. Instead, the relation order should influence the prediction. This limitation in modeling multi-hop relation paths motivates the RNN approach: using recurrent neural networks (RNN (Elman, 1990)) to model relation paths (Neelakantan et al., 2015). Das et al. (2017) further extend this approach by incorporating entity information and apply it to multi-hop KBC. Intermediate entities should influence the reasoning decision. For example, given two paths with the same relation sequence: (Donald Trump, child, Ivanka Trump, mother, Ivana Trump) and (Donald Trump, child, Barron Trump, mother, Melania Trump), even though both paths have the relation sequence [child, mother], the relation between (Donald Trump, Melania Trump) is "spouse" while it does not hold between (Donald Trump, Ivana Trump) due to the intermediate entities: "Ivanka Trump" vs. "Barron Trump". Similarly, paths (JFK, located in, NYC, located in, NY) and (Yankee Stadium, located in, NYC, located in, NY) would predict the same score for target relation "airport serves place" if we do not consider that Yankee Stadium is not an airport (Das et al., 2017).
Second, sequence labeling tasks such as POS tagging, chunking and NER have been successfully addressed by RNNs (Huang et al., 2015;Lample et al., 2016). These approaches model the mechanism in a structure of form "input 1 , tag 1 , input 2 , tag 2 , input 3 , tag 3 , · · · , input t , tag t ", which resembles the structure of multi-hop KG paths.
Inspired by this prior work, we propose ROP, Recurrent One-hop Predictor. Given a head entity, ROP encodes a multi-hop sequence of relations and predicts a sequence of entities using an RNN. More formally, given relation sequence "r 1 , r 2 , · · · , r t " and the head entity e h , ROP predicts the sequence e 1 , e 2 , · · · , e t , thus generating a complete KG path e h , r 1 , e 1 , r 2 , e 2 , · · · , r t , e t . Intuitively, our model memorizes history of path context; given a new relation, it predicts the next entity, then the memory is updated, and the process -given new relation, predicting new entity, updating memory -keeps going. Grouping step-wise updates in a chain gives our model two advantages. (i) A better vector space representation of KG entities and relations, with training signals either from in-path entities or from labels of reasoning tasks or from both. (ii) A unified approach for two different reasoning tasks (mh-KBC and mh-PQA) and state-of-the-art in each.
In summary, our contributions are: (i) ROP, a novel RNN sequence modeling of multi-hop KG paths that updates entity and relation embeddings by training signal at each step and leads to better KG embeddings; (ii) unified framework for solving different multi-hop reasoning tasks over KGs; (iii) showing the importance of modeling within-path entities in mh-PQA; (iv) state-of-the-art results for both mh-KBC and mh-PQA; (v) releasing an enhanced version of a mh-PQA dataset by adding within-path entities.

Multi-Hop Path Reasoning Tasks
We first give background on the two KG reasoning tasks we address in this work.
Knowledge Base Completion (mh-KBC). In mh-KBC, the goal is to predict new relations between entities using existing path connections. For example, (A, LivesIn, B) is implied, with some probability, from (A, CEO, X) and (X, HQIn, B). This kind of reasoning lets us infer new or missing facts from KGs. Figure 1(a) shows two paths between Microsoft and United States: (Microsoft, IsBasedIn, Seattle, Is-LocatedIn, Washington, IsLocatedIn, United States) (blue) and (Microsoft, CEO, Satya Nadella, Place-OfBirth, India, LargestTradingPartner, United States) (red). The task is then to predict the direct relation that connects Microsoft and United States; i.e., CountryOfHQ in this case. There can exist multiple long paths between two entities; the example shows that the target relation may only be inferrable from one path. The difficulty of finding the most informative path makes this task challenging.
Path Query Answering (mh-PQA). In mh-PQA, the goal is to predict missing properties of an entity, such as the earlier mentioned ethnicity of Brandon Lee. More generally, given an entity and relations of interest, predict what the target entity is, as Figure 1(b) shows. This task corresponds to answering compositional natural questions. For example, the question "Where do Brandon Lee's parents live?" can be formulated by the path query brandon lee/parents/live in. mh-PQA tries to find answers to the path queries and hence compositional questions. Unfortunately, KGs often have missing facts (edges), which makes mh-PQA a non-trivial problem.
A path query q t consists of an initial anchor entity, e h , followed by a sequence of t relations to be traversed, p = (r 1 , · · · , r t ). Following (Guu et al., 2015), the answer or denotation of the query is the set of all entities that can be reached from e h by traversing p.

Related Work
Here we focus on the multi-hop path reasoning literature. Some work (Neelakantan et al., 2015;Guu et al., 2015;Lin et al., 2015;Shen et al., 2016) does some composition over relation paths. Given relation path p = (r 1 , · · · , r t ), the composition operation is add (p = r 1 +· · ·+r t ), multiplication (p = r 1 · · · r t ) or an RNN step: p i = RNN(p i−1 , r i ), where p i is the accumulated relation information up to step i. Some work explores compositional encoding of long paths Shen et al., 2016), but still performs reasoning in one-hop scenario. Neelakantan et al. (2015) use RNNs to model multi-hop paths. Das et al. (2017) extend the RNN approaches by leveraging within-path entities into the encoding of inputs along with relations. We also include within-path entities, but we do not give them as inputs; instead, we force our RNN to predict them as outputs and do updates at each step in the path. This supports representation learning for KG entities and relations even without task-specific annotations. Toutanova et al. (2016) propose a dynamic programming algorithm to model both relation types and intermediate entities in the compositional path representations and test on WordNet and a biomedical KG. These two works address mh-KBC; for mh-PQA, there is no prior work on using within-path entities 2 , including Das et al. (2017), in which the system uses within-path entities as input, while those entities are not available for testing. So Das et al. (2017) use RNN for mh-PQA to encode the relation sequence, but it does not incorporate the intermediate entities involved. Paths are encoded by GRUs (Cho et al., 2014): where x is the input sequence with x i at position i, h is the output sequence with h i at position i. g z and g r are gates. All Us and Ws are parameters. In following, we define the whole Eqs. 1-4 as a single GRU step as: Thus, we interpret each GRU step as a composition function of two objects: h i−1 and x i . We now introduce the three architectures ROP ARC1, ROP ARC2 and ROP ARC3 that encode the context "e h , r 1 , e 1 , · · · , r i " in different ways to predict entity e i . ROP ARC1 (Figure 2(a)) models KG paths as: e 0 is initialized to the embedding of the true head entity e h . At position i, i > 0,ê i is the predicted entity embedding. ROP ARC1 is essentially a recurrent process with a pre-set starting state; the key is to use the head entity embedding e h as the initialization of the hidden state of GRU. We hope this start point guides where the path goes and what state to reach at each position. As a result, relations lie in the input space and entities lie in the hidden space. All predicted entitiesê i will be compared with the gold intermediate entities e i , then the loss (red in Figure 2) is used to train the system. ROP ARC1 only encodes head entity e h at the starting hidden state, possibly far from the tail entity e t for long paths. Thus, e h cannot provide effective guidance for prediction of e t . This motivates ROP ARC2, a modification of ROP ARC1.
In ROP ARC2, we want the head entity e h to participate in the entity prediction at each step more directly and effectively. To this end, ROP ARC2 first encodes the relation sequence as standard GRU: contains the information of the relation sequence r 1 , r 2 , · · · , r i independent of the head entity e h . To make sure the path reaches the correct state, ROP arc2 then composes each h i with e h to predict e i as:ê As composition function COMP 1 we use ADD (addition, as in TransE) or GRU (Eq 5).
In ROP ARC2, head entity e h directly participates in entity prediction at each step. Unfortunately, there is often another issue -head entity e h may not match the hidden state h i if they are far away from each other -h i mainly encodes some latest relation inputs that are less related to the head entity. Besides, there is a second information source, in addition to e h , that is clearly relevant for accurate prediction: the preceding predicted entityê i−1 . But ROP ARC2 does not make it available. Our solution is ROP ARC3. This architecture predicts the next entity e i using both e h andê i−1 , based on the intuition that e i is directly related to its predecessor e i−1 .
ROP ARC3 combines the benefits of ROP ARC1 and ROP ARC2. It encodes the relation sequence as in Eq 8 in ROP ARC2, but composes head entity e h as well as the predicted entityê i−1 with h i to predict the entity e i as:ê As composition function COMP 2 , we use ADD (addition) or an extended GRU step, defined as: where super/subscript h refers to head entity and p refers to prior predicted entityê i−1 .
In following work, we define Eqs. 11-16 as eGRU (extended GRU) step as: We extend GRU into eGRU, so that one architecture can compose three objects: a hidden state h i and two entity states e h andê i−1 .
Training. For the gold entity sequence e 1 , e 2 , · · · , e t , we define the loss function as the margin-based ranking criterion used in TransE (Bordes et al., 2013): where α is the margin, e − i a negative sample for entity e i and s() a similarity function. Discussion. The three ROP models differ in three aspects. (i) ROP ARC1 has only one composition process, i.e., GRU, to encode from head entity e h to r i ; ROP ARC2 and ROP ARC3 each have two composition processes, one composes relation sequence r 1 , · · · , r i into hidden state h i , the other composes entities (e h in ROP ARC2, e h andê i−1 in ROP ARC3) with h i to predict e i . Figure 2 shows that ROP ARC1 uses the GRU hidden states as outputs to compare with gold entities. ROP ARC2 and ROP ARC3 instead compose their hidden states with head entity or preceding predicted entity to generate a new output space, then compare with gold entities.
(ii) ROP ARC2 only uses the head entity e h along with the current hidden state h i to predict the next entity e i whereas ROP ARC1 and ROP ARC3 in addition use the preceding predicted entityê i−1 . Hence, ROP ARC3 roughly uses the combined information of ROP ARC1 and ROP ARC2 to do the prediction.
(iii) GRUs like ROP ARC2&ARC3 often zero-initialize first hidden state h 0 . Setting h 0 to the head entity in ROP ARC1 supports prediction of subsequent entities.
The ROP models are similar in three aspects.
(i) They model entities and relations in different spaces: relations are in the input space, entities are in hidden or output spaces. Our motivation is similar to SE, TransH and TransR (cf. §3).  2015) and Lin et al. (2015) (who also do some composition over relation paths), we finetune entity/relation embeddings in each step of the path. Our intuition is that many more training signals coming from each step of the sequence enable better learning of entity/relation embeddings. Das et al. (2017), as prior work that incorporates entities in the paths, only update the entity embeddings in the path once, when reaching the end of the path. We test this effect in our experiments.

Knowledge Base Completion (mh-KBC)
Dataset. We use Das et al. (2017)'s dataset, in which there are 46 query relations, each has train, dev and test files containing positive and negative entity pairs (head entity, tail entity). Each entity pair is also provided with multiple multi-hop paths connecting them. This is a binary classification task for each query relation: does the query relation hold between a pair of entities? The classifier builds a ranked list of entity pairs for corresponding query relation. Evaluation: mean average precision (MAP) across all 46 relations. Task setup. We use ROP for mh-KBC. Figure 3 shows that we extend the basic ROP architecture ( §4) by a GRU layer (bottom layer in Figure 3), denoted as GRU r , that learns the representation of the relation sequence. Finally, we use h t (the last hidden state of GRU r , shown in blue in Figure 3) to match the query relation r. 3 Thus, the training loss of this task has two parts: one comes from the loss of ROP training (l seq , Eq 18); the other is the prediction loss of query relation, denoted as l pred . Our preliminary experiments always showed worse performance of ADD, so the first loss l seq here only considers (e)GRU. The second loss is as in (Neelakantan et al., 2015); we show that our ROP part boosts the system as it enables relation paths to encode entity information with multiple updating -as opposed to a single update per path as in (Das et al., 2017). Similar to l seq , we define: where r is the embedding of a query relation in Figure 3, h i (resp. h − j ) is the representation of positive (resp. negative) path example i (resp. j), shown as h t in Figure 3. In testing, all paths are ranked in terms of the given query relation.
The target relation is often not inferrable from all paths between head and tail (see Figure 1(a)); it can be entailed by a single path or a subset of paths. Hence, given the representation of a group of paths, how to match them with the representation of the target relation is a key problem. We use max (over all paths) because we found it works well in selecting the best path for the target relation. See last paragraph of §5.1 for discussion. Model MAP PRA (Lao et al., 2011) 64.43 PRA+ Bigram (Neelakantan et al., 2015) 64.93 RNN-path (Neelakantan et al., 2015) 68.43 RNN-path-entity (Das et al., 2017) 71.74 RNN-path-types (Das et al., 2017) 73 We use AdaGrad (Duchi et al., 2011) with learning rate 0.1. Relation embedding dimension is 200, margins α and β are 0.5 , entity embedding dimension 200, batch size 20, negative sampling size 4. Longer paths are truncated to 8, the first 30 paths are kept for each entity pair.
Results. Table 1 compares our ROP systems to five baselines. RNN-path (Neelakantan et al., 2015) composes the relations occurring in a path using a vanilla RNN. It ignores all information about withinpath entities and trains separate models per relation. RNN-path-entity (Das et al., 2017) models the path entities and improves the results. RNN-path-type (Das et al., 2017) further improves the result by representing entities with the sum of their type embeddings. Thus, RNN-path-type uses extra information, the entity types. Apart from these baselines, it is also feasible to compare with the baselines based on composition of one-hop triple-based embedding models. However, the performance of these baselines is very poor for this task (Neelakantan et al., 2015) and therefore, we do not include them in our comparison.
The performance order of our architectures for mh-KBC is ROP ARC3 > ROP ARC2 > ROP ARC1. All our ROP systems are superior to the state-of-the-art. In particular, they are superior to RNN-pathtype (Das et al., 2017), the state-of-the-art, even though we do not need and do not use information about the types of entities. Comparing ROP performance to RNN-path-entity is more fair, and this makes it even clearer that our modeling is effective. Das et al. (2017) encode entities along with relations into the path representation explicitly. Their motivation is that entity incorporation prevents prediction of the same target relation when relation sequences are the same, but path entities are different. Our ROP models achieve this implicitly, as the relation sequence can predict the entity sequence; this makes sure the representation of the relation sequence is specific to the entity sequence. As a result, the same goal can be achieved as (Das et al., 2017).
In (Das et al., 2017), an entity and a relation are concatenated as a new unit in the path; both entity and relation representations are trained based on the given gold relation as label. ROP predicts intermediate entities and updates the entity/relation embeddings and other parameters in each step; the training signals can come from the in-path target entities and from the reasoning task specific annotations. Thus, ROP makes use of the in-path structures to learn good quality entity/relation embeddings, which are further employed and finetuned to solve the reasoning problem.
This can also explain why max (over all paths) works well for us while Das et al. (2017) found Log-SumExp (over all paths) works better. As their system solely relies on target relations as training signals, max selection prevents all other paths from generating gradients to update, so max tends to select randomly in the initial stage. However, in our system, the representations of entities and relations get rich training signals at each path hop, so that the path representations are more reliable. Hence, max can select the most informative path and avoid misleading paths to support the claim of target relation. In a similar vein, max pooling is widely found more effective than mean/sum pooling for classification as this task mostly relies on the dominant features.

Path Query Answering (mh-PQA)
Dataset. We use the mh-PQA dataset released by Guu et al. (2015) and refer to it as BaseKGP 4 . BaseKGP contains paths like e h , r 1 , r 2 , · · · , r t , e t , where e h and e t are head and tail entities, connected   BaseKGP is based on a Freebase subset released by Socher et al. (2013). The original subset contains a collection of Freebase triplets in form of (head, relation, tail). Guu et al. (2015) generated paths by traversing the triplet space. Paths in BaseKGP of form e h , r 1 , r 2 , · · · , r t , e t do not contain intermediate entities. We create EnhancedKGP by enhancing each BaseKGP path in train as follows. We search entities at each step of a path by traversing the subset (Socher et al., 2013) until reaching the tail entity e t . When there are multiple entity choices at a step, we randomly choose one. EnhancedKGP train has the same size as BaseKGP train, except that paths are filled by intermediate entities. Table 2 gives statistics. We release EnhancedKGP, 5 the first dataset for mh-PQA that includes within-path entities, with the code.
Task setup. We tune parameters on dev. We sample 10 negative entities for each ground truth entity in the path and use ranking loss (Eq 18) (with α=0.3, s() = cosine similarity). For testing, we ignore intermediate predicted entities and only output the tail entity. We update parameters -relation embeddings, entity embeddings (both dimension 300) and GRU parameters -using AdaGrad with learning rate 0.01 and mini-batch size 50.
We compare ROP with the three compositional training schemes Bilinear, Bilinear-Diag and TransE in (Guu et al., 2015). The compositional training of TransE, denoted as Comp-TransE in this work, is the state-of-the-art in mh-PQA. For ROP ARC2, we report the performance of using ADD and GRU for COMP 1 in Eq 9. Similarly, for ROP ARC3, we report the performance of using ADD and eGRU for COMP 2 in Eq 10.
In addition, to better investigate ROP models, we run them on both BaseKGP and EnhancedKGP. Note that since there are no intermediate entities in BaseKGP, ROP ARC3 is reduced to ROP ARC2. Hence, we report results on BaseKGP only for ROP ARC1 and ROP ARC2.
Two benchmark metrics are reported for this task (Guu et al., 2015): hits at 10 (H@10), percentage of ground truth tail entities ranked in the top 10 of all retrieved; and mean quantile (MQ), normalized version of mean rank.
Results. Comparing ROP ARC2 and ROP ARC1, we realize that forwarding head entity e h directly to predict each intermediate entity e i is better than putting e h as the start state of the GRU. We suspect this is due to the fact that the latest state of GRU is gradually less influenced by e h when the following relation path is getting longer and longer. In ROP ARC2, no matter how long the relation sequence r 1 , r 2 , · · · , r i is, we always compose its whole representation h i with the representation of e h so that e h can participate in the prediction of e i more directly.
ROP ARC3 further improves results by composing not only head entity e h , but also the preceding predicted entityê i−1 with h i to predict entity e i . The result suggests thatê i−1 provides critical information in this prediction process. This may be due to the property of RNN that latest inputs tend to be remembered better than old inputs, so the latest hidden state h i is heavily influenced by the adjacent relations of position i; employing the preceding predicted entityê i−1 hence can help the prediction of e i .
For composition, GRU/eGRU always surpass ADD -presumably due to the higher expressibility of (e)GRU's gating mechanism.
Performance vs. path lengths. Figure 4 graphs H@10 on different path lengths for our three ROP systems and the Comp-TransE baseline. We expected that H@10 should decrease gradually. However, Figure 4 shows that even-length paths are harder than odd-length ones. This surprising phenomenon is due to a large number of inverse relations, as most inverse relations in BaseKGP are 1-to-N connections.
The percentages of inverse relations in paths of length 1, 2, 3, 4, 5 are 0.0, 49.7, 38.3, 49.5 and 42.9, respectively. Spearman correlation coefficients between these percentages and system performance are always higher than 0.9. Thus, the more inverse relations, the worse performance. Unfortunately, to date there is no good way to model pairs of a relation r and its inverse * r, e.g, "gender" and "*gender", as separate, yet at the same time as systematically related. Guu et al. (2015)'s TransE implementation enforces * r+r = 0. Figure 4 shows this is not as effective as expected, perhaps because it fails for 1-to-N projections. ROP treats inverse relations as independent, but we did not observe any worse performance. Better modeling of inverse relations is an interesting challenge for future work.

Conclusion
This work presented three ROP architectures for multi-hop KG reasoning. ROP models a KG path of arbitrary length as a pair of a relation sequence and an entity sequence, using the former to predict the latter by encoding and decoding step by step. Our neural sequential modeling of KG paths enables better learning of entity/relation embeddings because there are more training signals at each multi-hop path. ROPs showed state-of-the-art in two representative KG reasoning tasks, multi-hop KBC and multi-hop PQA. Incorporating knowledge from textual sources by initializing the entity embeddings with distri-butional representation of entities (Yaghoobzadeh and Schütze, 2015) could improve our results further, which we will explore in the future.