Neural Collective Entity Linking Based on Recurrent Random Walk Network Learning

1 Introduction

Entity linking (EL) is a task to link the name mentions in a document to their referent entities within a knowledge base (KB). The great significance of the research on EL can not be neglected due to the solid foundation it helps to build for multiple natural language processing tasks, such as information extraction [Ji and Nothman, 2016], semantic search [Blanco et al., 2015] and so on. Nevertheless, this task is non-trivial because mentions are usually ambiguous, and the inherent disambiguation between mentions and their referent entities still maintains EL as a challenging task.

∗Corresponding author

The previous studies on EL are based on the statistical models, which mainly focus on artificially defined discriminative features, which mainly focus on the utilization of artificially defined discriminative features between mentions and its target entities, such as contextual information, topic information or entities type etc. [Chisholm and Hachey, 2015; Shen et al., 2015]. However, these models resolve mentions independently relying on textual context information from the surrounding words while ignoring the interdependence between different EL decisions. In order to address this problem, researches then devoted themselves to implementing collective decisions in EL, which encourages re entities of all mentions in a document to be semantically coherent [Hoffart et al., 2011; Ganea et al., 2015; Globerson et al., 2016; Guo and Barbosa, 2018].

Recently, the studies of EL have evolved from the conventional statistical models into the neural network (NN) based models thanks to their outstanding advantages in encoding semantics and dealing with data sparsity. Similarly, the studies of NN-based EL models have also experienced the development progress from models of independent decisions [He et al., 2013; Francis-Landau et al., 2016; Yamada et al., 2016] to those of collective decisions [Ganea and Hofmann, 2017; Cao et al., 2018; Le and Titov, 2018; Kolitsas et al., 2018]. For example, Ganea et al., [2017] and Le et al., [2018] solved the global training problem via truncated fitting loopy belief propagation (LBP). Cao et al., [2018] applied Graph Convolutional Network (GCN) to integrate global coherence information for EL. However, in these works, they completely depend on NNs to automatically model the semantic dependencies between different EL decisions, while little attention has been paid on the guidance from an external KB.

In this paper, we propose a novel end-to-end neural collective model named Recurrent Random Walk based EL (RRWEL) which not only implements collective EL decisions but also leverages an external KB to model the semantic dependencies between candidate entities. Given a document, we first utilize some local features to measure the conditional probability of a mention referring to a specific entity, and then introduce random-walk layers to model the interdependence between different EL decisions, where the evidence for related EL decisions are computed based on the semantic relatedness between their corresponding knowledge pages, and can be fine-tuned during training. Finally, a semantic regularizer, which aims to preserve the collective EL decision consistency, is added to supplement the conventional EL loss. In that case, both the local semantic correspondence between mentions and entities and the global interdependence between different EL decisions can be fully exploited in our model to conduct collective EL decisions.

The main contributions of our work can be summarized as follows: (1) Through the in-depth analysis, we point out the drawbacks of dominant NN-based EL models and then dedicate to the study of employing KB based global interdependence between EL decisions for collective entity disambiguation; (2) We propose a novel end-to-end graph-based NN model which incorporates the external KB to collectively infer the referent entities of all mentions in the same document. To the best of our knowledge, this is the first NN-based random walk method for collective EL to explore external KB when modeling semantic interdependence between different EL decisions; (3) We evaluate the performance of our proposed model on many large-scale public datasets. The extensive experiments and results show that our model can outperform several state-of-the-art models.

2 The ProposedModel

In this section, we give a detailed description to our proposed model. As shown in Fig. 1, our model mainly includes two components: one is used to model local mention-to-entity compatibility, the other leverages external knowledge to capture global entity-to-entity semantic interdependence.

More specifically, we first employ CNNs to learn the semantic representations of each mention and its all candidate entities, which are further fed into a linear model layer with other feature vectors to measure their local semantic compatibility. Then, we introduce random-walk layers to model the global interdependence between different EL decisions, which enable the EL evidence for related mentions to be collectively reinforced into high-probability EL decisions. In particular, during model training, in order to effectively exploit both the local mention-to-entity compatibility and the global interdependence between entities for collective ELs, we augment the conventional EL loss with a semantic regularizer.

To clearly describe our model, we first introduce some annotations which are used in our model. Let d be the input document and m(d) = {m1,m2, ...,mNmd } be the set of mentions occurring in d, for each mention mi, its candidates set Γ(mi) is identified. In addition, for all mentions {mi}, we collect all their candidate entities to form the candidate entity set e(d) = {e1, e2, ..., eNed }, where each entity ej has a corresponding KB page pj. Using EL models, we expect to correctly map each mention to its corresponding entity page of the referenced KB.

2.1 Local Mention-to-Entity Compatibility

Following Francis-Landau et al., [2016], we represent the mention mi using the semantic information at three kinds of granularities: si, ci, di, where si is the surface string of mi, ci is the immediate context within a predefined window of mi and di is the entire document contains mi. For the candidate entity page pj, we use its title tj and body content bj to represent it, pj = (tj, bj).

To correctly implement EL decisions, we first calculate the relevance score φ(mi, pj) for the candidate entity page pj, and then normalize relevance scores to obtain the conditional probability plocal(pj |mi):

where φ(mi, pj) is defined as follows:

where σ(∗) is the sigmoid function, Fsf(mi, pj) and Fcnn(mi, pj) are two feature vectors that will be concatenated to obtain the local feature vectors, andWlocal is the weight for local feature vectors. In the following, we give detail descriptions of Fsf(mi, pj) and Fcnn(mi, pj).

1). Fsf(mi, pj) denotes the statistical local feature vector proposed by Cao et al. [2018]. It contains various linguistic properties and statistics, including candidates' prior probability, string based similarities, compatibility similarities and the embeddings of contexts, all of which have been proven to be effective for EL. Due to the space limitation, we omit the detail descriptions of Fsf(mi, pj). Please refer to [Cao et al., 2018] for the details.

2). Fcnn(mi, pj) combines the cosine similarities between the representation vectors of mi and pj at multiple granularities. Formally, it is defined as follows:

where ¯ si, ¯ ci, ¯ di, ¯ tj, and ¯bj denote the distributed representations of si, ci, di, tj, and bj, respectively.

In order to obtain the representations for the context word sequences of mentions and entities, we follow FrancisLandau et al., [2016] and adopt CNNs to transform a context word sequence x∈{si, ci, di, tj, bj} into the distributed representations, where each word of x is represented by a realvalued, h-dimensional vector. The convolution operation is first performed on w, where w=[w1;w2; ...;wN]∈Rh×N is a matrix representing x. Here N is the word number of x. Then we transform the produced hidden vector sequences by a non-linear function G(∗) and use Avg function as pooling. Specifically, we employ one window size l to parameterize the convolution operation, where the window size l corresponds to a convolution matrix Ml ∈ Rv×l×h of dimensionality v. Hence, we obtain the distributed representation ¯x for x as 1 N-l ∑N-l+1 i=1 G(Mlwi:(i+l-1)). Please note that we use the same set of convolution parameters for each type of text granularity in the source document d as well as for the target entities.

At this stage, we are able to calculate plocal(pj|mi) which provides abundant information of local mention-to-entity compatibility. The next step is to propagate this information based on the global interdependence between EL decisions.

2.2 Global Interdependence Between EL Decisions

Inspired by the random walk based EL [Han et al., 2011] and the successful adaptation of random walk propagation to NN [Zhao et al., 2017], we introduce recurrent random-walk layers to propagate EL evidence for the purpose of effectively capturing the global interdependence between different EL decisions for collective entity predictions.

To implement the propagation of EL evidence based on random walk, we first need to define a transition matrix T between candidate entities, where Tij is the evidence propagation ratio from ej to ei. Intuitively, the more semantically related two entities are, the more evidence should be propagated between their EL decisions. Therefore, we calculate the semantic relevance between ei and ej, and then normalize these relevance scores by entity to generate T :

where Nei is the set of neighbor entities of entity ei. To be specific, for two considered entity pages pi = (ti, bi) and pj = (tj, bj), we use hyperlinks to compute the semantic relevance score SRlink(pi, pj):

where I and J are the sets of all entities that link to pi and pj in KB respectively, and W is the entire KB. Meanwhile, we obtain their cosine similarity SRsemantic(pi, pj) based on their CNN semantic representations. Considering that the semantic relevance score between two candidate entities relies on the relative distance of their corresponding mentions, we supplement the conventional entity page pi = (ti, bi) with the position embedding posi of its entity. Formally, SRsemantic(pi, pj) is defined as follows:

SRsemantic(pi, pj ) = cos([¯ ti; ¯ ei] + posi, [¯ tj ; ¯ ej] +posj). (7) Here we follow Vaswani et al., [2017] to define the embed-

ding posi of mention mi.

With the transition matrix T, we perform the evidence propagation of EL decisions in the recurrent random-walk layers: (See the recurrent random-walk layers of Fig. 1)

with p(k) rw(∗|mi) being the predicted entity distribution of mi at the k-th iteration. Please note that p(0) rw(∗|mi) = plocal(∗|mi) which only exploits local mention-to-entity compatibility. Obviously, by introducing K random-walk layers, we can easily propagate evidence for K times based on random walk propagation.

2.3 Model Training

Aiming at combining the global interdependence between EL decisions with the local mention-to-entity context compatibility, we propose to not only minimize the common compatibility-based EL loss but also preserve the high-order EL consistency during model training. In this way, we can significantly improve our model by embedding the global interdependence between different EL decisions into the training of CNNs for modeling mention-to-entity compatibility.

The intuition behind our implementation lies in the convergence propriety of random walk process based on Markov chain [Gilks et al., 1995]. Specifically, after multiple rounds of EL evidence propagation, the predicted entity distributions for mentions will tend to converge. If the global interdependence between different EL decisions has been well embedded into our model, we can expect that plocal(∗|mi) ≈ p(K) rw (∗|mi) = T (K) · plocal(∗|mi). To do this, we minimize the following error to preserve the the K-th order EL consistency of mi, formulated as ‖plocal(∗|mi) - T (K) · plocal(∗|mi)‖2F , where ‖ · ‖2F is the Frobenius norm.

Finally, the recurrent random walk network learning for collective EL can be mathematically formulated as

where D denotes the training corpus, K is the number of random-walk layers, and the coefficient γ is used to balance the preference between the two terms. Specifically, the first term Lc denotes the cross-entropy loss between predicted and ground truth yg , which is defined as follows:

To train the proposed model, we denote all the model parameters by θ. Therefore, the objective function in our learning process is given by

where α is the trade-off parameter between the training loss L and regularizer ‖θ‖2 . To optimize this objective function, we employ the stochastic gradient descent (SGD) with diagonal variant of AdaGrad in [Duchi et al., 2011]. Particularly, when training the model, we first use Lc to pre-train the model and then use L to fine-tune it.

3 Experiment

3.1 Setup

Datasets

We validated our proposed model on six different benchmark datasets used by previous studies:

• AIDA-CONLL: This dataset is a manually annotated EL dataset [Hoffart et al., 2011]. It consists of AIDAtrain for training, AIDA-A for validation and AIDA-B for testing and there are totally 946, 216, 231 documents respectively.
• MSNBC, AQUAINT, ACE2004: These datasets are cleaned and updated by Guo and Barbosa [2018], which contain 20, 50 and 36 documents respectively.
• WNED-WIKI (WIKI), WNED-CWEB (CWEB): These datasets are automatically extracted from ClueWeb and Wikipedia in [Guo and Barbosa, 2018; Gabrilovich et al., 2013] and are relatively large with 320 documents each.

In our experiments, we investigated the system performance with AIDA-train for training and AIDA-A for validation, and then tested on AIDA-B and other datasets. Following previous works [Ganea and Hofmann, 2017; Cao et al., 2018; Le and Titov, 2018], we only considered mentions that have candidate entities in the referenced KB.

Contrast Models

We compared our proposed RRWEL model to the following models:

• [Hoffart et al., 2011] where iterative greedy method is employed to compute a subgraph with maximum density for EL.
• [Han et al., 2011] introduces randomwalk algorithm to implement collective entity disambiguation.
• [Cheng and Roth, 2013] utilizes integer linear programming to solve global entity linking.
• [Francis-Landau et al., 2016] applies CNN to learn the semantic representations of each mention and its all candidate entities.
• [Yamada et al., 2016] proposes a novel embedding method specifically designed for NED which jointly maps words and entities into a same continuous vector space.

• [Ganea and Hofmann, 2017] solves the global training problem via truncated fitting LBP.
• [Le and Titov, 2018] encodes the relations between mentions as latent variables and applies LBP for global training problem.
• [Guo and Barbosa, 2018] proposes a greedy, global NED algorithm which utilizes the mutual information between probability distributions induced from random walk propagation on the disambiguation graph.
• [Cao et al., 2018] applies Graph Convolutional Network to integrate both local contextual features and global coherence information for EL.

Model Details

We used the latest English Wikipedia dump 1 as our referenced KB. However, please note that our proposed model can be easily applied to other KBs. To employ CNN to learn the distributed representations of inputs, we used 64 filters with the window size 3 for the convolution operation and the non-linear transformation function ReLU. Meanwhile, to learn the context representations of input mentions and target entities, we directly followed Francis-Landau [2016] to utilize the window size 10 for context, and only extracted the first 100 words in the documents for mentions and entities. Besides, the standard Word2Vec toolkit [Mikolov et al., 2013] was used with vector dimension size 300, window context size 21, negative sample number 10 and iteration number 10 to pre-train word embeddings on Wikipedia and then we fine-tuned them during model training. Particularly, following Ganea and Hofmann [2017], we kept top 7 candidates for each mention based on their prior probabilities, and while propagating the evidence, we just kept top 4 candidates for each mention mi according to plocal(∗|mi). Besides, we set α=1e-5. Finally, we adopted standard F1 score at Mention level (Micro) as measurement.

1 https://dumps.wikimedia.org/enwiki/20181101/enwiki20181101-pages-articles-multistream.xml.bz2

3.2 Effects of K and Trade-off Parameters

There are three crucial parameters in our approach, which are the number K of random-walk layers, the trade-off parameter λ for restart and the trade-off parameter γ for loss function. We tried different hyper-parameters according to the performance of our model on the validation set.

To investigate the effect of the trade-off parameter λ and γ, we kept K=5 and then tried different combinations of these two parameters with λ from 0.1 to 0.9 and γ from 0.1 to 0.9. The results are shown in Table 1. We observed that our method achieves the best performance when the trade-off parameters λ and γ are set to 0.5 and 0.1 respectively. Consequently, all the following experiments only consider the proposed model with λ=0.5 and γ=0.1.

Besides, we varied the value of K from 0 to 7 with an increment of 1 each time while keeping λ=0.5 and γ=0.1.

Please note that when K is set as 0, our model is unable to model global interdependence between different EL decisions. Fig. 2 provides the experimental results. We find that our model (K>0) obviously outperforms its variant with K=0. This results indicates that graph-based evidence propagation contributes effectively to the improvement of NN-based EL method. In particular, our model achieves the best performance when K=5, so we set K=5 for all experiments.

3.3 Overall Results

Experimental results are shown in Tables 2 and 3. We directly cited the experimental results of the state-of-the-art models reported in [Francis-Landau et al., 2016; Ganea and Hofmann, 2017; Le and Titov, 2018; Guo and Barbosa, 2018]. On average, our model achieves the highest Micro F1 scores on all out-domain datasets, expect AIDA-B test set (in-domain). It is worth noting that although our model is slightly inferior to [Le and Titov, 2018] on AIDA-B, however, its latent relations modeling can be adapted to refine our model.

3.4 Qualitative Analysis

Effects of Recurrent Random-Walk Layers

In table 4, we show a hard case (where entities of two mentions are incorrectly predicted because of their low evidence scores), which is from WNED-WIKI dataset, can be correctly solved by our random-walk layers. We can notice that RRWEL(K=0) is unable to find enough disambiguation clues from context words for the two mentions, specifically, "brown", "color". By contrast, RRWEL can effectively identify the correct entities with the help of the semantic interdependence based on KB: "Bay (horse)" and "Equine coat color" receive higher evidence scores than others.

Effects of the External KB

In order to better understand how our model benefits from the graph-based evidence propagation based on external knowledge, we consider different kinds of transition matrix T and the performances are represented in Table 5. We can see that by leveraging external knowledge to model the semantic dependencies between candidate entities, the global interdependence between different EL decisions can be more accurately captured by our model to conduct collective EL decisions.

4 RelatedWork

In early studies, the dominant EL models are mostly statistical ones exploring manually defined discriminative features to model the local context compatibility [Ji and Grishman, 2011; Mendes et al., 2011; Shen et al., 2015] and the global interdependence between EL decisions [Hoffart et al., 2011; Cheng and Roth, 2013; Ganea et al., 2015; Globerson et al., 2016; Guo and Barbosa, 2018]. With the extensive applications of deep learning in NLP, the studies of EL have marched into NN related research from resorting to conventional statistical models. Similar to the precious statistical models, the early NN-based models mainly focused on how to apply NNs to measure the local context compatibility. For example, He et al., [2013] employed Stacked Denoising Auto-encodes to learn entity representations, Francis-Landau et al., [2016] combined CNN-based representations with sparse features to model mentions and entities, while Yamada et al., [2016] proposed a NN model to learn distributed representations for texts and KB entities. Obviously, these works only focus on individual EL tasks with little attention paid on the interdependence between these target decisions. To tackle this problem, Ganea et al., [2017] utilized unrolled deep LBP network to model global information. Le and Titov [2018] treated relations between textual mentions in a document as latent variables in our neural EL model. Moreover, GCN was applied by Cao et al., [2018] for the sake of integrating global coherence information for EL. In these works, notwithstanding semantic dependencies between various entities are able to be automatically modeled by constructing a neural network, the guidance from an external KB has always been neglected.

To address the above-mentioned issue, in this work, we exploit a neural network with recurrent random-walk layers leveraging external knowledge for collective EL. The most related works to ours include [Han et al., 2011; Huu et al., 2016; Ganea and Hofmann, 2017; Guo and Barbosa, 2018; Cao et al., 2018]. Significantly different from [Han et al., 2011] and [Guo and Barbosa, 2018], we resort to NN rather than statistical models for collective EL. Compared with [Huu et al., 2016], we further adopt the mutual instead of unidirectional effects between EL decisions. Also, different from [Ganea and Hofmann, 2017; Cao et al., 2018], we explore external KB to model global semantic interdependence between different entities, which has been proved to be more effective in our experiments.

5 Conclusions and FutureWork

This paper has presented a novel end-to-end neural network with recurrent random-walk layers for collective EL, which reinforce the evidence for related EL decisions into highprobability decisions with the help of external KB. Experimental results and in-depth analysis strongly demonstrate the effectiveness of our proposed model.

Our model is generally applicable to other tasks similar to EL, such as word sense disambiguation, cross-lingual entity disambiguation, and lexical selection [Su et al., 2015]. Therefore, we will investigate the effectiveness of our approach on these tasks. Besides, we would like to fully exploit other resources of Wikipedia beyond hyperlinks to refine our model. Finally, inspired by the recent success of graph neural network in NLP [Zhang et al., 2018; Song et al., 2019], we plan to explore graph neural network based EL model in the future.

Acknowledgments

The authors were supported by Beijing Advanced Innovation Center for Language Resources, National Natural Science Foundation of China (No. 61672440), the Fundamental Research Funds for the Central Universities (Grant No. ZK1024), Scientific Research Project of National Language Committee of China (Grant No. YB135-49), National Key Research and Development Program of China (grant No. 2016QY03D0505) and Project S201910384407 supported by XMU Training Program of Innovation and Enterpreneurship for Undergraduates.