We present a novel method for mapping unrestricted text to knowledge graph entities by framing the task as a sequence-to-sequence problem. Specifically, given the encoded state of an input text, our decoder directly predicts paths in the knowledge graph, starting from the root and ending at the target node following hypernym-hyponym relationships. In this way, and in contrast to other text-to-entity mapping systems, our model outputs hierarchically structured predictions that are fully interpretable in the context of the underlying ontology, in an end-to-end manner. We present a proof-of-concept experiment with encouraging results, comparable to those of state-of-the-art systems. Text-to-entity mapping is the task of associating a text with a concept in a knowledge graph (KG) or an ontology (we use two terms, interchange-ably). Recent works (Kartsaklis et al., 2018; Hill et al., 2015) use neural networks to project a text to a vector space where the entities of a KG are represented as continuous vectors. Despite being successful, these models have two main disadvantages. First, they rely on a predefined vector space which is used as a gold standard representation for the entities in a KG. Therefore, the quality of these algorithms depends on how well the vector space is represented. Second, these algorithms are not interpretable; hence, it is impossible to understand why a certain text was linked to a particular entity. To address these issues we propose a novel technique which first represents an ontology concept as a sequence of its ancestors in the ontology (hy-pernyms) and then maps the corresponding textual description to this unique representation. For example, given the textual description of the concept swift (small bird that resembles a swallow and is noted for its rapid flight), we map it to the hierarchical sequence of entities in a lexical ontology: animal  chordate  vertebrate  bird  apodiform bird . This sequence of nodes constitutes a path. 1 Our model is based on a sequence-to-sequence neural network (Sutskever et al., 2014) coupled with an attention mechanism (Bahdanau et al., 2014). Specifically, we use an LSTM (Hochre-iter and Schmidhuber, 1997) encoder to project the textual description into a vector space and an LSTM decoder to predict the sequence of entities that are relevant to this definition. With this framework we do not need to rely on the pre-existing vector space of the entities, since the decoder explicitly learns topological dependencies between the entities of the ontology. Furthermore, the proposed model is more interpretable for two reasons. First, instead of the closest points in a vector space, it outputs paths; therefore, we can trace all predictions the model makes. Second, the attention mechanism allows to visualise which words in a textual description the model selects while predicting a specific concept in the path. In this paper, we consider rooted tree graphs 2 only and leave the extension of the algorithm for more generic graphs to future work. We evaluate the ability of our model in generating graph paths for previously unseen textual definitions on seven ontologies (Section 3). We show that our technique either outperforms or performs on a par with a competitive multi-sense LSTM model (Kartsaklis et al., 2018) by better utilising external information in the form of word embeddings. The code and resources for the paper can 1 We only consider hypernymy relations, from the root to the parent node ( apodiform bird ) of the entity swift . 2 Only single root is allowed. If a tree has more than one root, one can create a dummy root node and connect the roots of the tree to it. be found at https://github.com/VictorProkhorov/ Text2Path. We assume that an ontology is represented as a rooted tree graph G = ( V, E, T ) , where V is a set of entities (e.g. synsets in WordNet), E is a set of hyponymy edges, and T is a set of textual descriptions such that  v  V there is a t v  T . We assume that an ontological concept can be defined by either using a textual description from a dictionary or hypernyms of the defining concept in the ontology. For example, to define the noun swift one can use the dictionary definition mentioned previously. Alternatively, the concept of swift can be understood from its hypernyms, e.g. in the trivial case one can say that swift is an animal . This definition is not very useful since animal is a hypernym for many other nouns. To provide a more specific definition, one can use a sequence of hypernyms e.g. animal  chordate  vertebrate  bird  apodiform bird starting from the most abstract node (root of an ontology) to the most specif (parent node of the noun). More formally, for each entity v (cid:54) = v root  V we create a path p v . Each p v starts from v root and ends with a hypernym of v , i.e., the hierarchical order of entities is preserved. Then the path p v is aligned with t v such that each node is defined by a textual definition and a path. This set of aligned representations is used to train the model. The path representation of an entity ends with its parent node. Therefore, a leaf node will not be present in any of the paths. This is problematic if a novel definition should be attached to a leaf. To alleviate this issue we employ the dummy source sentences technique from neural machine translation (NMT) (Sennrich et al., 2016). We create an additional set of paths from the root node to each leaf. As for the textual definition we leave it empty. We use a sequence-to-sequence model with an attention mechanism to map a textual description of a node to its path representation. Encoder. To encode a textual definition t v = ( w i ) Ni =1 , where N is sentence length, we first map each word w i to a dense embedding e w i and then use a bi-directional LSTM to project the sequence into a latent representation. The final encoding state is obtained by concatenating the forward and backward hidden states of the bi-LSTM. Decoder. Decoding the path representation of a node from the latent state of the textual description is done again with an LSTM decoder. Similarly to the encoding stage, we map each symbol in the path p v = ( s j ) Mj =1 to a dense embedding e s j , where M is the path length. To calculate the probability of the path symbol s j at time step j we first represent the path sequence as h  j = LSTM ( e js , h  j  1 ) . Then, we concatenate h  j with the context vector c j (de-fined next) and pass the concatenated representation [ h  j ; c j ] through the softmax function, i.e. s j = max ( softmax ( W [ h  j ; c j ])) , where W is a weight parameter. To calculate the context vector c j we use an attention mechanism, e ji = v T a tanh ( W a h i + U a h  j ) and c j = (cid:80) Ni softmax ( e ji ) h i , where v a , W a and U a are the weight parameters, over the words in the text description. Ontologies. We experimented with seven graphs four of which are related to the bio-medical do-main: Phenotype And Trait Ontology 3 (PATO), Human Disease Ontology (Schriml et al., 2012, HDO), Human Phenotype Ontology (Robinson et al., 2008, HPO) and Gene Ontology 4 (Ash-burner et al., 2000, GO). The other three graphs, i.e. WN animal.n.015 , WN plant.n.02 and WN entity.n.01 are subgraphs of the WordNet 3.0 (Fellbaum, 1998). We present the statistics of the graphs in Table 1. Ontology Preprocessing. All the ontologies we experimented with are represented as directed acyclic graphs (DAGs). This creates an ambiguity for node path definitions since there are multiple pathways from a root concept to other concepts. We have assumed that a single unambiguous pathway will reduce the complexity of the problem and leave the comparison with ambiguous pathways (which would inevitably involve a more complex model) to future work. To convert a DAG to a tree 3 http://www.obofoundry.org 4 After prerocessing GO we took its largest connected component. 5 The subscript in WN' indicates the name of the root node of the graph. we constrain each entity to have only one parent node. The edges between the other parent nodes are removed. 6 Path Representations. We also experiment with two path representations. Our first approach, text2nodes , uses the label of an entity (cf. Section 1) to represent a path. This is not efficient since the decoder of the model needs to select between all of the entities in an ontology and also requires more parameters in the model. Our second approach, text2edges , to reduce the number of symbols for the model to choose from, uses edges to represent the path. To do this we create an artificial vocabulary of the size ( G ) , where ( G ) corresponds to the maximum degree of a node. Each edge in the graph is labeled using the artificial vocabulary. For the example in Section 1, the path would be animal  [a]  chordate  [b]  vertebrate  [c]  bird  [d]  apodiform bird where { a,b,c,d } is the artificial vocabulary. In the resulting path we discard labels for the entities; therefore, the path reduces to: [a]  [b]  [c]  [d]. Bag-of-Words Linear Regression (BOW-LR): To represent a textual definition in a vector space we first use a pre-trained set of word embeddings (Speer et al., 2017) to represent words in the definition and then find the mean of the word embeddings. As for the ontology, we use node2vec (Grover and Leskovec, 2016), to represent each entity in a vector space. To align the two vector spaces we use linear regression. 6 The choice of an edge is performed on random basis. Multi-Sense LSTM (MS-LSTM): Kartsaklis et al. (2018) proposed a model that achieves state-of-the-art results on the text-to-entity mapping on the Snomed CT 7 dataset. The approach uses a novel multi-sense LSTM, augmented with an attention mechanism, to project the definition to the ontology vector space. Additionally, for a better alignment between the two vector spaces, the authors augmented the ontology graph with textual features. To perform evaluation of the models described above we used Ancestor-F1 score (Mao et al., 2018). This metric compares the ancestors ( is  a model ) of the predicted node with the ancestors ( is  a gold ) of the gold node in the taxonomy. P = | is  a model  is  a gold | | is  a model | , R = | is  a model  is  a gold | | is  a gold | , where P and R are precision and recall, respectively. The Ancestor-F1 is then defined as: 2  P  R P + R. 3.3 Intrinsic Evaluation To verify the reliability of our model on text-to-entity mapping we did a set of experiments on the seven graphs (Section 3) where we map a textual definition of a concept to a path. To conduct the experiments we randomly sampled 10% of leaves from the graph. From this sample, 90% are used to evaluate the model and 10% are used to tune the model. The remaining nodes in the graph are used for training. We sample leaves for two reasons: (1) to predict a leaf, the model needs to make the maximum number of (correct) predictions and (2) this way we do not change the original topology of the graph. Note that the sampled nodes and their textual definitions are not present in the training data. Both baselines predict a single entity instead of a path. To have the same evaluation framework for all the models, for each node predicted by the baselines we create 8 a path from the root of the node to the predicted node. However, we want 7 https://www.snomed.org/snomed-ct 8 We used NetworkX (https://networkx.github.io) to find a path from predicted node to the root of a graph. to emphasize that this is disadvantageous for our model, since all the symbols in the path are predicted by it and in the case of the baselines only a single node is predicted. The results are presented in Table 2. Models that are in the last three rows of Table 2 use pre-trained word embeddings (Speer et al., 2017) in the encoder. MS-LSTM and our models that are above the last three rows use randomly initialised word vectors. We had four observations: (1) without pre-trained word embeddings in the encoder our model outperforms the best MS-LSTM  = 0 . 5 only on two of the seven graphs, (2) the text2edges  model outperforms all the other models including MS-LSTM   =0 . 5 , (3) the text2edges model can better exploit pre-trained word embeddings than MS-LSTM, (4) our model performs better when the paths are represented using edges (rather than nodes). We also found that there is a strong negative correlation (Spearman:  0 . 75 , Pearson:  0 . 80 ) between A.D. (Table 3) and the Ancestor F1 score for the text2edges  model, meaning that with an increase in A.D. the Ancestor F1 score decreases. We carried out an analysis on the outputs of our best-performing model, i.e. text2edges  with pre-trained word embeddings. One factor that affects the performance is the number of invalid sequences predicted by the text2nodes and text2edges models. An invalid sequence is the path that does not exist in the original graph. This happens because at each time step the decoder outputs a distribution over all the nodes/edges and not just over possible children nodes. We therefore performed a count of the number of invalid sequences produced by the model. The percentage of invalid sequences is in the range of 1.82% -8.50% (Appendix B), which is relatively low. This analysis was also performed by J. Kusner et al. (2017). To guarantee that the model always produces valid graphs, they use a context-free grammar. A similar method can be adapted in our work. Another factor that affects the performance is the length of the generated paths which is expected to match the length of the gold path. To test this, we compared the mean length of the generated sequences with the length of the gold path (the graph on the bottom of Figure 1). Also, in the training set, we associate the length of the sequences with their frequencies (the graph on the top of Figure 1). We found that (1) the length of the generated paths are biased towards the more frequent paths in the training data, (2) if the length of a path is not frequent in the training data, the model either under-generates or over-generates the length (Ap-pendix D). Text-to-entity mapping is an essential component of many NLP tasks, e.g. fact verification (Thorne et al., 2018) or question answering (Yih et al., 2015). Previous work has approached this problem with pairwise learning-to-rank method (Lea-man et al., 2013) or phrase-based machine translation (Limsopatham and Collier, 2015). However, these methods generally ignore ontology's structure. More recent work has viewed the problem of text-to-entity mapping as a projection of a textual definition to a single point in a KG (Kartsak-lis et al., 2018; Hill et al., 2015). However, despite potential advantages, such as being more interpretable and less brittle (model predicts multiple related entities instead of one), path-based approaches have received relatively little attention. Instead of predicting a single entity, path-based models, such as the one we proposed in this paper, try to map a textual definition to multiple relevant entities in an external resource. We presented a model that maps textual definitions to interpretable ontological pathways. We evaluated the proposed technique on seven semantic graphs, showing that it can perform competitively with respect to existing state-of-the-art text-to-entity systems, while being more interpretable and self-contained. We hope this work will encourage further research on path-based text-to-entity mapping algorithms. A natural next step will be to extend our framework to DAGs. Furthermore, we plan to constrain our model to always predict paths that exist in the graph, as we discussed above. We would like to thank the anonymous reviewers for their comments. Also, we would like to thank Dimitri Kartsaklis and Ehsan Shareghi for helpful discussions and comments. This research was supported by an EPSRC Experienced Researcher Fellowship (N. Collier: EP/M005089/1) and an MRC grant (M.T. Pilehvar: MR/M025160/1). We gratefully acknowledge the donation of a GPU from the NVIDIA Grant Program.
objective method objective result method abstain abstain abstain abstain abstain objective abstain abstain abstain method abstain abstain objective abstain method method result method abstain abstain other method method abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain method method abstain method abstain abstain abstain abstain abstain method abstain abstain method abstain method abstain method abstain method abstain method other abstain method abstain abstain method method abstain method method abstain abstain method method method method abstain abstain abstain abstain method abstain abstain method method abstain abstain method abstain abstain method other method abstain abstain method method abstain method method method abstain abstain abstain method abstain abstain abstain method abstain method method method other other other other other objective method objective method objective method other other other other