<figure><img src="image_1.png" /></figure>

HAL
open science

# Adapting Semantic Spreading Activation to Entity Linking in text

Farhad Nooralahzadeh, Cédric Lopez, Elena Cabrio, Fabien Gandon, Frederique Segond

<figure><img src="image_2.png" /></figure>

## To cite this version:

Farhad Nooralahzadeh, Cédric Lopez, Elena Cabrio, Fabien Gandon, Frederique Segond. Adapting Semantic Spreading Activation to Entity Linking in text. NLDB 2016 - 21st International Conference on Applications of Natural Language to Information Systems, Jun 2016, Manchester, United Kingdom. hal-01332626

HAL Id: hal-01332626

https://inria.hal.science/hal-01332626v1

Submitted on 27 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Adapting Semantic Spreading Activation to Entity Linking in
text*

Farhad Nooralahzadeh¹, Cédric Lopez², Elena Cabrio³, Fabien Gandon¹, and Frédérique Segond²

¹ INRIA Sophia Antipolis, France

{farhad.nooralahzadeh|fabien.gandon}@inria.fr

² Viseo Research Center, Grenoble, France

{cedric.lopez|frederique.segond}@viseo.com

³ University of Nice, France

elena.cabrio@unice.fr

**Abstract.** The extraction and the disambiguation of knowledge guided by textual resources on the web is a crucial process to advance the Web of Linked Data. The goal of our work is to semantically enrich raw data by linking the mentions of named entities in the text to the corresponding known entities in knowledge bases. In our approach multiple aspects are considered: the prior knowledge of an entity in Wikipedia (i.e. the keyphraseness and commonness features that can be precomputed by crawling the Wikipedia dump), a set of features extracted from the input text and from the knowledge base, along with the correlation/relevancy among the resources in Linked Data. More precisely, this work explores the *collective ranking approach* formalized as a weighted graph model, in which the mentions in the input text and the candidate entities from knowledge bases are linked using the local compatibility and the global relatedness measures. Experiments on the datasets of the Open Knowledge Extraction (OKE) challenge with different configurations of our approach in each phase of the linking pipeline reveal its optimum mode. We investigate the notion of semantic relatedness between two entities represented as sets of neighbours in Linked Open Data that relies on an associative retrieval algorithm, with consideration of common neighbourhood. This measure improves the performance of prior link-based models and outperforms the explicit inter-link relevancy measure among entities (mostly Wikipedia-centric). Thus, our approach is resilient to non-existent or sparse links among related entities.

**Keywords:** Entity linking, Linked data, Collective entity ranking, Semantic spreading

# 1 Introduction

The Web publishes information from many heterogeneous sources, and such data can be extremely valuable for several domains and applications as, for instance, business intelligence. A large volume of information on the Web is made of unstructured texts, and contains mentions of named entities (NE) such as people, places and organizations. Names are often ambiguous and could refer to several different named entities (i.e. homonymy) and, vice-versa, entities may have several equivalent names (i.e. synonymy). On the other hand, the recent evolution of publishing and connecting data over the Web under the name of "Linked Data" provides a machine-readable and enriched representation of the world's entities, together with their semantic characteristics. This process results in the creation of large knowledge bases (KB) from different communities, often interlinked to each other as is the case of DBpedia, i.e. the structured version of Wikipedia, Yago and FreeBase ⁴. This characteristic of the Web of data empowers both the humans and computer agents to discover more "things" by easily navigating among the datasets, and can be profitably exploited in complex tasks such as information retrieval, question answering, knowledge extraction and reasoning. The NE recognition and linking task, i.e. establishing the mapping between the NE mentions in the text to their related resources in KB is of critical importance to achieve this goal. Such mappings (i.e. links) can be used to provide semantic annotations to human readers, as well as a machine-readable representation of the pieces of knowledge in the text, exploitable to improve many

* This work has been founded by the French ANR national grant (ANR-13-LAB2-0001)

⁴ dbpedia.org; www.mpi-inf.mpg.de/yago/; www.freebase.com
Natural Language Processing (NLP) applications. The preliminary step in the entity linking task is identifying the textual boundaries of words, i.e. as a single-word or multiwords in a document such that the recognized boundary corresponds to an individual entity (e.g., person, organization, location, event) in the real world. The detection of entity mentions is currently referred as *named entity recognition*. Then, the main challenge of entity linking is to map each entity mention found in the text to the corresponding entry in a given KB(e.g. DBpedia). More precisely, the task can be described as follows: given a KB 'KB' (e.g., Wikipedia, DBpedia) and an unstructured text document *D* in which a sequence of NE mentions $\vec{M} = \{m_1, m_2, ..., m_i, ...\}$ appear in the text, the aim of entity linking is to output a sequence of entity candidates $\vec{C} = \{c^1, c^2, ..., c^i, ...\}$, where $c^i \in KB$ and corresponds to $m_i$ with a high confidence score. Here $m_i$ refers to a sequence of tokens which is recognized by NER tools as a NE. If an entity mention $m_i$ in text does not have its corresponding entity candidate $c^i$ in the *KB*, it is labeled as "NIL" [16, 31].

The state-of-the-art entity linking systems exploit various features extracted from the input text and from the knowledge base. The most important feature is the semantic relatedness among the candidate entities and the effectiveness of this function is a key-point for the accuracy of entity linking system [3]. Most of the entity linking algorithms focus on the extensive link structure of Wikipedia and they consider the overlap of the incoming/outgoing links of entity articles as a notion of their relatedness. However, this approach has a limitation for the entities that do not have explicit links. In order to deal with this limitation, in this paper we answer the following research questions:

- How can we configure an accurate entity linking pipeline?

- What is the best approach to deal with non-existent or sparse links among related entities?

- How does the Linked Data-based relatedness measure impact on the performance of the entity linking task?

Taking into account these questions, the main goals of this work are i) to investigate and compare several state-of-art approaches proposed in the literature at each phase of the entity linking pipeline; ii) to introduce and evaluate the Linked Data-based relatedness measure among the entities that we are proposing in our approach, and iii) to compare the effectiveness of this measure against other state-of-art components in entity discovering task. To address these issues, we implemented different components for each step of the entity linking task by employing the open source framework Dexter [2]. We designed the inference part as a collective ranking model by constructing the weighted graph among the named entity mentions and their potential candidates. Finally, we evaluated the performance of our approach against publicly available datasets, with TAC (Text Analysis Conference) evaluation tools for the named entity linking task. The rest of the paper is as follows: section 2 presents the related work. Section 3 introduces our approach, whose features are detailed in Section 4. In Section 5.1 the dataset is described. Section 5 details the experiments and the obtained results. Conclusions end the paper (Section 6).

## 2 Related Work

The entity linking task has been widely studied in the last decade ([6] among many others), and generally consists of 3 steps. The first step is the *mention identification*: the NLP field provides NE recognizers which are particularly efficient for persons, organizations, and locations [13]. To avoid the specification of types of mentions to be recognized, a spotting identification can consider n-grams of words to be compared to entries of a resources (for instance Wikipedia). The second step consists in *candidate generation* which have to be mapped with entities in a KB. Mapping approaches such as exact string matching and partial matching are often used based on string similarity with e.g. Dice score, skip bi-gram score, Hamming distance, Levenshtein, the Jaro similarity. Compared with exact matching, partial matching leads to higher recall, but more noise appears in the candidate entity set. In [10] the authors used also the number of Wikipedia pages linking to an entity's page.

The last step consists in selecting the relevant URI among the candidates. The candidate ranking process relies on the context information provided by a set of features. According to [9] the features can be classified into three groups: i) Extracted from the prior knowledge (Keyphraseness, Commonness, Popularity); ii) Extracted from the text of the document/articles (Local features): Mention-candidate
context similarity: use similarity measure to compare the context of the mention with the text associated with a candidate title (the text in the corresponding page); iii) Based on existing links (Global features [3]). In [3], the authors explored the various type of global features as a relatedness measure among the candidate entities. They showed that the entity linking algorithms benefit from maximizing the relatedness among the relevant entities selected as candidates in ranking process, since this minimizes errors in disambiguating entity-linking. The key role of effective relatedness function in any entity-linking algorithm encouraged us to adapt semantic spreading activation to model another relevancy feature which incorporates multiple types of entity knowledge from the knowledge base.

# 3 The Entity linking task

The task of entity discovery can be divided into a series of steps [9] (Figure 1): (i) spotting or mention identification, i.e. detecting the anchors to link, (ii) candidate generation and pruning, i.e. searching for candidate identifiers for each anchor and filtering, (iii) candidate ranking, i.e. selecting the best candidate from the results of the searching step. This section, provides a step by step description of our approach. Afterward we explain the employed feature set.

<figure><img src="image_4.png" /><figcaption>Fig. 1: Entity linking pipeline</figcaption></figure>

## 3.1 Spotting or Mention Identification

A mention is a phrase used to refer to something in the world like NEs, object, substance, event, philosophy, mental state, rule, etc. (e.g., Stanford University, Berlin, MBA, U.S.Open Tennis). To extract mentions from the text, we implement the following techniques, and then we select the most appropriate to include in our approach, based on their performances (see Section 5.3):

- **N-grams linked in lexicon (prior anchor text).** An n-gram is a contiguous sequence of n words from an input text (n represents any integer > 0). Each n-gram is a potential entity mention if it has exact or partial match in the repository. The spotting step uses a dictionary of NEs or a KB, to extract possible mentions of NE in the text. It provides the highest recall, but for large documents it becomes intractable and introduces noise in the mention extraction. We follow a standard approach [25, 16] to create an anchor repository to address this issue. The token extractor generates a list of possible spots from a given document. In the extraction phase, the tool produces all the possible n-grams of terms (up to six words in our case), afterward the spotter looks for the matching of each fragment in the spot repository. The filtering process helps us to discard the meaningless mentions, because even stop words may match the anchor text. We use the keyphraseness feature [23] to apply this filtering. Keyphraseness estimates the probability of a term to be selected as a link to the entities in the knowledge base KB, by counting the number of times where the term was already selected as a anchor, divided by the total number of times where the term appeared. These counts are collected from all Wikipedia articles, permitting to throw out spots that are rarely used as a mention of the relevant entity. In case of overlap among the fragments, we take the union of the fragments boundaries, and if one fragment contains another we consider the longest one as a mention (see Section 3.2).
- **Named Entity tagging.** To avoid the noise and have precise mentions, statistics and symbolic-based filtering could be applied. This will have negative impact on the system recall but will increase the precision. The most prominent named entity tagger for English is Stanford NER [13], which we use to detect the mentions, and segment the text accordingly, in our approach.

## 3.2 Candidate Entity Generation

At this step, for each entity mention $m_i \in \mathcal{M}$, the entity linking system aims at retrieving a candidate entity set $C(m_i) = (c_1^i, c_2^i, \dots, c_j^i, \dots)$ from $\mathcal{KB}$ which contains possible resources that the entity mention $m_i$ may refer to. To achieve this goal, we create a repository which maps strings (surface forms) to entities represented by Wikipedia articles or DBpedia resources [3, 19]. The structure of Wikipedia supplies useful features for generating candidate entities such as entity pages (articles), redirect pages, disambiguation pages, bold phrases from the first paragraphs, and hyperlinks inside the articles. Leveraging these features from Wikipedia<fnref n="5" />, we build an offline dictionary $\mathcal{D}$ as key-value map $<\mathcal{K}, \mathcal{V}>$ between various names as key ($\mathcal{K}$) and their possible mapping entities as values ($\mathcal{V}$). We exploit $\mathcal{D}$ to generate candidate entities $C(m_i)$. This dictionary compiles a vast amount of information about possible variation of named entities, like abbreviations, alternative names, ambiguous terms, misspellings, initial letters. Based on such dictionary, the simplest way to generate the candidate entity set $C(m_i)$ for mention $m_i \in \mathcal{M}$ is the exact matching between the mention name $m_i$ and the keys ($\mathcal{K}$). If a key is similar to $m_i$, the set of entities mapped to the key will be added to the candidate entity set $C(m_i)$.

Beside exact matching, we apply partial matching between the mention $m_i$, and the key ($\mathcal{K}$) in the dictionary. If the mention has a strong string similarity based on *Jaro-Winkler distance* with the name as key in dictionary, then the set of entities assigned to that key will be added to the candidate set. Compared with exact matching, partial matching leads to higher recall, but imposes more noise in the candidate entity set.

## 3.3 Candidate Entity Pruning

Since the set of candidates is quite large that contains unrelated candidates, we need to filter some of them to ensure the quality of the entity candidates. To limit the set of candidate entities $C(m_i)$ to the most meaningful ones, the *commonness* property was exploited [3]. The *commonness* of a candidate $c_j^i$ for entity mention $m_i$ is the chance of candidate $c_j^i$ being target of a link by mention $m_i$ as an anchor. It is defined as the fraction between the number of occurrences of mention $m_i$ in $\mathcal{KB}$ actually pointing to candidate $c_j^i$, and the total number of occurrences of $m_i$ in $\mathcal{KB}$ as an entity mention. Setting a threshold on minimum commonness is a simple and effective strategy to prune the number of candidates, without affecting the recall of the entity linking process [25]. Moreover, we exploit the context-based similarity feature (Section 4.3) to prune the candidates that do not have any contextual similarity compared to the context of the target mention in the input text.

## 3.4 Candidate Ranking

The objective of the ranking module is to create a ranking function $f: \{c_j^i \in C(m_i)\} \rightarrow \mathcal{R}$, such that for each entity mention $m_i$ the elements in its corresponding candidates list can be assigned relevance scores using the function, and then be ranked according to the scores. Several approaches have been studied to formulate the ranking function in recent years, and we take inspiration from the successful application of *Graph-based* model in entity linking problem (known under various names like “collective entity linking” [16], “Entity linking via random walk” [15] and “Neighborhood relevance model” [7]). Adopting a graph based model, let $G = (V, E)$ a undirected graph, in which the vertex set $V = \{\mathcal{M} \cup \mathcal{C}\}$ contains all entity mentions $m_i \in \mathcal{M}$ in a document and all possible entity candidates of these mentions $c_j^i \in C(m_i)$. The set of edges $E$ includes all the links that represent the mention-entity and entity-entity edges. Each edge between a mention and a candidate entity denotes a “local compatibility” relation; each edge between two candidate entities indicates a “global relatedness/coherence” (Figures 1 and 2).

<footnote n="5">⁵ English Wikipedia dump downloaded on 2015/07/02</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 2: Graph model for entity linking</figcaption></figure>

The goal is to find the best assignment $C$ that is contextually compatible with mentions in $M$ and has a maximum coherence as the following objective function:

$$C^* = \arg \max_{C} [\Phi(\mathcal{M}, C) + \Psi(C)]$$

where $C^*$ is the best candidate set; $\Phi(\mathcal{M}, C)$ is the local compatibility of mentions and candidates, while $\Psi(C)$ measures the global coherence of selected candidates.

The local compatibility $\Phi$ formalizes the intuition that the mention $m$ and a candidate entity $c$ are compatible when their name matches and the context surrounding $m$ has terms similar to the context of the entity candidate $c$ in $KB$; it has been applied to conventional entity linking approaches [6, 1] as discriminative features. Local features work best, when the context is rich enough to uniquely link a mention, which is not always true. Furthermore, the feature sparsity problem arises when there is no similarity between the mention and the related entity to match; therefore no similarity match is applied [15]. With global coherence $\Psi$, we rely on the idea that the best selected candidates for the neighbor mentions in the text, would be good clues to disambiguate the current mention. It takes into account the relation of the candidate with other candidates within neighbor mentions. In other words, if each neighboring mention of $m_i$ is linked to its correct entity candidate $c_j^k$, $k \neq i$, the true candidate $c_j^i$ will achieve a high score in $\Psi$ for most of the neighbors $c_j^k$. To satisfy the objective function, the disambiguation is done collectively on all mentions at the same time. In [20, 19, 16] authors seek to find a sub-graph embedded in the constructed graph, in which each mention is linked to a single candidate entity. However solving the objective function is a recursive problem [14] and is NP-hard [20], therefore all methods turn to approximate algorithms or heuristics. To solve this disambiguation problem, we design the two following methods:

**PageRank-like method:** The problem described above can be addressed by a PageRank-like algorithm [11]. In PageRank, the objective is to assign a score of the “importance” to each page. The score (PageRank) of each page depends on the score of pages linking to it. In essence, the PageRank of a page is a weighted sum of pageranks of articles linking to it. A page has a high rank if the sum of the ranks of the pages that link to it is high [27]. In the entity linking problem, we would like to rank the possible candidates associated with a certain mention in the document. So, it can be said that a candidate has a high score if the sum of the scores in the document of the candidates that typically co-occur with it is high. This is formalized as:

$$V^{t+1} = (1 - \lambda) * M * V^t + \lambda * S$$

Where $M$ is a matrix with $(n+m)^2$ dimensions, $n$ as reallocate condition, is the number of mentions and $m$ is the number of candidates. $M[i, j]$ if $i$ denotes the mention and $j$ denotes the candidate are
the local feature value $\phi(m_i, c_j)$, and when $i, j$ represent the candidates, its value will be $\psi(c_i, c_j)$, otherwise it will be 0. The $(n+m) \times 1$ vector $S$ shows the prior importance of each mention $p(m)$, and for the candidates it is 0. $V$ is the $(n+m) \times 1$ preference vector and $\lambda \in (0, 1)$ is the fraction of the reallocation condition at each iteration. To find the final preference vector $V^*$, we use the power method with $k$ iteration or until convergence condition. The $i^{th}$ value of vector $V^*$ where $i$ points to the candidate, will be the final rank of each candidate. It should be mentioned that in each iteration, since we have the preference score for each mention in previous iteration, we can update the reallocation vector $S$ with its posterior importance $p_{post}(m_i) = p_{pripr}(m_i) * V[i]$ [16].

**Naive method:** The expression that we use to select the best assignment $C$ using the maximum apos-
teriori decision rule can be formalized like :

For each $m_i \in \mathcal{M}$ the best candidate $c_i^*$ is :

$$c_i^* = \arg \max_c \left[ \alpha \cdot \sum_j \phi(m_i, c_j) + \beta \cdot \sum_{c_j^k \in C, k \neq i} \psi(c, c_j^k) \right]$$

Here we compute the local compatibility and coherence individually for each candidate and solve the problem linearly by assigning the coefficient $\alpha$ and $\beta$, where $\alpha+\beta = 1$. During the annotation process, if there is only one mention to disambiguate and no need to build a graph among the neighbours, we use naive method to find the best candidate entity for mention.

In Section 4, the local $\Phi$ and global $\Psi$ relatedness features applied in our work are explained.

# 4 Local ($\Phi$) and Global ($\Psi$) Features

In this section, we present the features used in this study. Local features rely only on compatibility of the mention and its candidates, while global ones compute the coherence among the candidates.

## 4.1 Prominence / Prior Feature $\in \Phi$

As a context-independent feature, we choose the *commonness* feature of candidates based on Wikipedia link anchors [23]. It is the popularity of the candidate entity with respect to the mention in the text, and has been found to be very useful in entity linking [31, 19]. It tells the prior probability of the appearance of a candidate entity given the mention term. For each surface form that appears as an anchor text in Wikipedia, we compute how often it refers to a particular entity:

$$Commonness(c_j^i) = \frac{x}{y}$$

where $x$ is the number of times a mention $m_i$ links to a candidate entity $c_j^i$ in Wikipedia and $y$ is the number of times a mention $m_i$ appears as anchor text in Wikipedia.

## 4.2 Feature for Name variants $\in \Phi$

Variation in entity names is a limitation for information extraction systems. Poor handling of entity name variants results in a low recall. The name string comparison between the mention and the candidate is the most direct feature that can be used. We use approximate string matching based on the *levenshtein distance* to figure out this feature between mention term and candidate's label.

## 4.3 Context-based feature $\in \Phi$

The key for mapping mentions onto candidates, is the context appearing on both sides of the mapping. For each mention inside the input text, we construct a bag-of-words excluding the mention itself in size of the window $w$ ($w = 6$ in our case) of text around the mention by removing the stop words and
punctuation marks. We compute the TF-IDF similarity of mentions context regarding to its candidates context. For each candidate, the context is represented as a bag-of-words from the whole Wikipedia entity page (content), or the first paragraph of its Wikipedia article (summary), or the outgoing to other pages in its Wikipedia page (links). We implement each of these representations in lucene<fnref n="6" />, as an option than can be selected during the linking process.

## 4.4 Neighbors coherence features ∈ Ψ

We identify a number of previous methods for estimating the coherence between two entities in a knowledge base (KB). In [29], the authors use the category overlap of two entities in Wikipedia. In [24], the authors use the incoming link structure, while [3] introduce various asymmetric and symmetric relatedness features for entity linking. State-of-the-art measures for entity relatedness that perform well in entity linking are based on the extensive link structure of Wikipedia. Most particularly, the Milne-Witten and the Pointwise mutual information are described in the following.

**Milne-Witten (MW)** It is a co-citation based similarity, that quantifies the coherence between two entities by the links that their Wikipedia articles share [24]. The intuition is that entities occurring often together in Wikipedia articles are related. It takes into account Wikipedia graph structure as its KB (KB) and computes the relatedness between two candidate entities $c_i, c_j$ as:

$$MW(c_i, c_j) = 1 - \frac{\log(\max(|in_{c_i}|, |in_{c_j}|)) - \log(|in_{c_i} \cap in_{c_j}|)}{\log(N) - \log(\min(|in_{c_i}|, |in_{c_j}|))}$$

$N$ is the number of all entities in Wikipedia, $|in_c|$ is the number of incoming links to candidate $c$.

**Pointwise mutual information (PMI)**: Another similarity metric between Wikipedia articles to consider, is based on computing the PMI between the sets of links in the articles to be compared. It is used by [30] for the link-to-Wikipedia task. It is defined between two candidates $c_i$ and $c_j$ as:

$$PMI(c_i, c_j) = \frac{|in_{c_i} \cap in_{c_j}|/N}{(|in_{c_i}|/N)(|in_{c_j}|/N)}$$

Furthermore, as indicated in [30, 3], both MW and PMI can be computed using the outgoing links ($out_c$), and both the incoming and outgoing links ($in_c \cup out_c$).

Wikipedia centric relatedness has no chance to capture the connection between the entities whose corresponding pages do not have links in common. In these cases, previous coherence measures (i.e. the milne-witten and PMI), do not properly capture the semantic relatedness between entities. In the following, we propose a new measure in order to overcome this limitation.

**Semantic Spreading (DiscoveryHub)**: A relatedness measure for link-poor entities needs to tap into linked open data that is more widely available and can be gathered with reasonable effort. The linked data semantic richness offers plenty of possibilities to retrieve, prioritize, discard, and rank the resources by using the knowledge they contain at the instance and schema levels. To exploit these possibilities, we base our relatedness function on an algorithm [21] that has proven its efficiency for information retrieval: spreading activation. We utilize the spreading activation algorithm adaptation (DiscoveryHub [21]) which leverages the graph richness thanks to semantic filtering and similarity to devise the proper relevancy measure between candidate entities.

The algorithm presented in DiscoveryHub aims to explore the graph obtained from the linked data cloud, namely from DBpedia. It identifies a meaningful subset of resources strongly related to the entity. Then these results are presented in a set of relevant entities to the target entity. The semantic graph is exploited thanks to a weight, that is function of the origin entity. It constrains the propagation to

<footnote n="6">⁶ https://lucene.apache.org/</footnote>
certain entity types based on the class-based “semantic pattern” using *rdf:type* and *rdfs:subClassOf* properties. Then, they make use of the *dct:subject* property to compute triple-based similarity measure (commontriple), because the categories constitute a topic taxonomy which is very informative on the resources. It constitutes a valuable basis for computing similarity. The entities reached by the propagation and belonging to the same categories as the origin receive a greater amount of activation. Activation and propagation features of the algorithm expose the relevancy of entities that are not linked explicitly by incoming and outgoing links.

Based on Jaccard index, we define *DiscoveryHub* relatedness measure on the top of this algorithm:

$$ \textit{DiscoveryHub}(c_i, c_j) = \frac{\textit{DiscoveryHub}(c_i) \cap \textit{DiscoveryHub}(c_j)}{\textit{DiscoveryHub}(c_i) \cup \textit{DiscoveryHub}(c_j)} $$

Where *DiscoveryHub(c)* is the set of explicit and implicit neighbours, obtained during the spreading algorithm as relevant resources for the target entity *c*.

# 5 Experiments

In the following, we describe the dataset we used in our experiments, the experimental setting itself, and the results obtained by our approach.

## 5.1 Dataset

To compare our approach with other state-of-art methods, we choose two publicly available datasets published in *NLP Interchange Format* (NIF) [17] and employed in many other systems evaluations.

**OKE**: It is provided for the Open Knowledge Extraction challenge at ESWC2015. It contains the training and evaluation datasets built by manually annotating 196 sentences. These sentences have been selected from Wikipedia articles reporting the biographies of scholars to cover NEs for people, locations, organizations and roles<fnref n="7" />. It is split into 95 sentences as training set and 101 sentences as evaluation set, by taking into account no overlap between two datasets and equal distribution of entity types within datasets (see Table 1).

**KORE50**: This small dataset was produced as a subset of the larger AIDA corpus [19], which is based on the dataset of CoNLL 2003 NER task. It aims to capture hard to disambiguate mentions of entities and it contains a large number of first names referring to persons, whose identity needs to deduced from the given context. It consists of 50 sentences from different domains, such as music, celebrities and business and is provided in a TSV (Tab-separated values) format (and converted to NIF format<fnref n="8" />) (see Table 1).

<table><caption>Table 1: OKE and KORE50 datasets overall information</caption><thead><tr><td>Parameter</td><td>OKE-training</td><td>OKE-evaluation</td><td>KORE50</td></tr></thead><tbody><tr><td>Nb. of sentences</td><td>95</td><td>101</td><td>50</td></tr><tr><td>Nb. of mentions</td><td>290</td><td>428</td><td>148</td></tr><tr><td>Nb. of mentions linked to DBpedia</td><td>255</td><td>321</td><td>148</td></tr></tbody></table>

<footnote n="7">⁷ https://github.com/anuzzolese/oke-challenge</footnote>

<footnote n="8">⁸ http://dashboard.nlp2rdf.aksw.org/</footnote>
## 5.2 Evaluation measures

For the system evaluation, we use the standard metrics of precision, recall and F1 at each phases on the pipeline, over the above described datasets. The TAC evaluation tools for NE linking, neleval<fnref n="9" />, provides a range of linking and clustering evaluation measures. This tool also provides a number of diagnostic measures available to isolate performance of system components and compare to numbers reported elsewhere in the literature. In spotting or mention identification, we consider the strong-mention-match measure to evaluate this task. Given that it takes into account all annotations together and gives more importance to documents with more annotations [5], it is called micro-averaged evaluation of entity mentions. In this measure if a span of recognized mention matches a gold mention exactly, then it will be counted as a true positive. For the linking evaluation we choose the strong-link-match measure, that is a micro-averaged evaluation of entities. A predicted entity by the system must have the same span and KB identifier as a gold entity in order to be considered as a true positive. This is equivalent to the strong annotation match presented in [5].

## 5.3 Experiments and results over the training dataset

In our experiments, we use the English Wikipedia edition (2015-07-02) as the source to mine entities, keyphrases and corresponding context. We prepared the Wikipedia data according to [2] using the core module of the open source framework Dexter and implementing extra methods to meet the requirements of our approach. We applied different configurations to investigate the effect of each option in the pipeline of our entity linking approach. The OKE-training dataset is employed to tune the best setup model for our study. In the first step, the optimum choice for spotting or mention identification (Section 3.1) was explored. As Table 2 shows, Stanford NER provided by yields better result than the wiki-dictionary based N-gram spotting. We evaluate this step applying the strong-mention-match measure described above.

<table><caption>Table 2: Evaluation of spotting phase on OKE-training</caption><thead><tr><td>Spotter</td><td>P %</td><td>R%</td><td>F1%</td></tr></thead><tbody><tr><td>Named Entity Tagging</td><td>69.9</td><td>57.2</td><td>62.9</td></tr><tr><td>N-grams linked in Lexicon</td><td>48.7</td><td>62.5</td><td>54.8</td></tr></tbody></table>

According to these results, we chose the NE Tagging method for the spotting phase inside our pipeline. Then, we study the impact of the other parameters as the ranking method (Section 3.4) and the global relatedness (Section 4.4) in our approach.

We chose the summary field of Wikipedia article representation in lucene to compute the context-based similarity feature (Section 4.3) and filter the candidate if its commonness (Section 4.1) is less than the threshold ($\theta$ = 0.05 defined by line-search). In the candidate ranking phase we define empirically $\lambda$ = 0.1, $\epsilon$ = $1e^{-6}$, $N$ = 100 (max-number-of-iteration) and $w$ = 6 (window-size) in PageRank-like method and $\alpha$ = 0.4, $\beta$ = 0.6 in naive method (Section 3.4). In Table 3, we can see that the PageRank-like method including the DiscoveryHub as global relatedness has better results than the other configurations. This result indicates that the semantic spreading nature of DiscoveryHub relatedness identifies new links among related entities and PageRank-like method takes advantage of this favor to assign proper entities to the mentions.

In this phase (see Figure 2) we are trying to find proper links among the dbr:Martti_Ahtissan as a candidate entity for mention Martti Ahtissar and the set of candidate for mention YMCA. Modeling the graph with MW and PMI relatedness returns graph without any links among these sets. However, using the DiscoveryHub coherence features unveil the implicit connection between dbr:Martti_Ahtissan and dbr:YMCA, contributing in assigning a higher score to dbr:YMCA.

<footnote n="9">⁹ https://github.com/wikilinks/neleval/wiki</footnote>
<table><caption>Table 3: Evaluation of candidate ranking on the OKE-training set</caption><thead><tr><th>Candidate Ranking</th><th>Global relatedness</th><th>P%</th><th>R%</th><th>F1 %</th></tr></thead><tbody><tr><td><strong>PageRank-like</strong></td><td><strong>DiscoveryHub</strong></td><td><strong>62.6</strong></td><td><strong>47.2</strong></td><td><strong>53.8</strong></td></tr><tr><td>Naive</td><td>DiscoveryHub</td><td>55.8</td><td>48.5</td><td>52.0</td></tr><tr><td>PageRank-like</td><td>MW</td><td>60.9</td><td>46.6</td><td>53.0</td></tr><tr><td>Naive</td><td>MW</td><td>56.6</td><td>46.0</td><td>48.6</td></tr><tr><td>PageRank-like</td><td>PMI</td><td>55.1</td><td>47.9</td><td>51.2</td></tr><tr><td>Naive</td><td>PMI</td><td>50.9</td><td>44.3</td><td>47.4</td></tr></tbody></table>

It is obvious that the performance on the candidate ranking phase depends on the result of the spotting process in our pipeline. In order to evaluate the performance of the scoring function independently, we assume that the spotting phase extracts the mentions exactly as gold spans (100% accuracy). Table 4 presents the evaluation of our approach with the most favorable setup.

<table><caption>Table 4: Evaluation of selected ranking approach</caption><thead><tr><th>Candidate Ranking</th><th>P %</th><th>R %</th><th>F1 %</th></tr></thead><tbody><tr><td>PageRank-like + DiscoveryHub</td><td>70.2</td><td>69.5</td><td>69.9</td></tr></tbody></table>

## 5.4 Comparison with state-of-the-art entity linking tools

We conduct an experiment with the final configuration of our approach on the *OKE-evaluation* dataset. We compare our results to the performances of state-of-art systems, i.e. *Adel* (winning system at the OKE challenge for the entity linking task), *AIDA*, *TagMe* and *DBpedia Spotlight* (Table 5). We use the figures which are reported in [28] for this comparison, since the authors used the public API of these tools with default setting on the *OKE-evaluation* dataset to compare their findings. Our experiment shows that the pipeline which we present in this study outperforms the other systems in the linking task in terms of precision and f1-measure in *OKE-evaluation* dataset.

<table><caption>Table 5: Comparison on OKE-evaluation dataset</caption><thead><tr><th>Method</th><th>Measure</th><th>P%</th><th>R%</th><th>F1%</th></tr></thead><tbody><tr><td rowspan="2">Adel-without pruning</td><td>Spotting</td><td>78.2</td><td><strong>65.4</strong></td><td><strong>71.2</strong></td></tr><tr><td>Linking</td><td>49.4</td><td>46.6</td><td><strong>48</strong></td></tr><tr><td rowspan="2">Adel- with pruning</td><td>Spotting</td><td>83.8</td><td>9.3</td><td>16.8</td></tr><tr><td>Linking</td><td><strong>57.9</strong></td><td>6.2</td><td>11.1</td></tr><tr><td rowspan="2">AIDA</td><td>Spotting</td><td>55.7</td><td>49.1</td><td>52.2</td></tr><tr><td>Linking</td><td>51.6</td><td>43.9</td><td>47.4</td></tr><tr><td rowspan="2">TagMe</td><td>Spotting</td><td>39.7</td><td>61.7</td><td>48.3</td></tr><tr><td>Linking</td><td>28.5</td><td><strong>54.9</strong></td><td>37.5</td></tr><tr><td rowspan="2">DBpedia Spotlight</td><td>Spotting</td><td>40.3</td><td>52.6</td><td>45.6</td></tr><tr><td>Linking</td><td>28.3</td><td>45.7</td><td>34.9</td></tr><tr><td rowspan="2"><strong>Our approach</strong></td><td>Spotting</td><td><strong>87.5</strong></td><td>57.1</td><td>69.1</td></tr><tr><td>Linking</td><td><strong>73.1</strong></td><td>46.1</td><td><strong>56.5</strong></td></tr></tbody></table>

We also compare our method by taking into account only the candidate ranking task and assuming full annotation in the mention identification phase, with respect to the same state-of-the-art entity linking systems over *KORE50* dataset. In order to make this comparison, we report the facts from [26], adding our approach's ranking performance. Over this dataset (Table 6) we classify fourth in terms of performances after *Babelfy* and the two *AIDA-KORE* systems. Based on the error analysis of the results, we found out that this differences comes from the candidate generation phase, and we plan to investigate more this aspect.
<table><caption>Table 6: State-of-the-art EL systems (Accuracy) on KORE50 dataset</caption><thead><tr><th>System</th><th>KORE50</th></tr></thead><tbody><tr><td>Babelfy [26]</td><td>71.5</td></tr><tr><td>AIDA-KORE-LSH-G [18]</td><td>64.6</td></tr><tr><td>AIDA-KORE [18]</td><td>63.9</td></tr><tr><td><strong>Our Ranking Method</strong></td><td><strong>60.6</strong></td></tr><tr><td>MW [24]</td><td>57.6</td></tr><tr><td>Tagme [12]</td><td>56.3</td></tr><tr><td>Illinois Wikifier [4]</td><td>41.7</td></tr><tr><td>DBpedia Spotlight [22]</td><td>35.4</td></tr></tbody></table>

# 6 Conclusion and Future work

In this work, we implemented and benchmarked different approaches for each step of the entity linking task to build the most accurate pipeline. We also proposed and evaluated a new collective ranking model by constructing the weighted graph among the named entity mentions and their potential candidates. We evaluated the performances of our approach against publicly available datasets, with the TAC evaluation tools. The performance of the graph-based collective entity linking system highly relies on modeling coherence among the candidate entities. Our system incorporates multiple types of entity knowledge from the KB. To deal with non-existent or sparse links among related entities we took advantage of semantic spreading approach to model the entity relatedness measure and it outperformed other Wikipedia-centric measures. Our experiments showed that the Linked-data based measure assists our graph-based model to achieve competitive performance in the target datasets compared to other well-known entity linking systems.

There are several directions for future work: we are interested in the joint inference model [8] to reduce the interdependency nature of our pipeline approach. On the other hand we want to investigate the word embedding impact in computing the contextual similarity between the mentions context and the candidate entities. Finally, we would like to use the *Wikilinks* [32] and *crossWikis* [33] corpora to enrich our repository and improve the candidate generation components.

# References

1. Adafre, S.F., de Rijke, M.: Discovering missing links in wikipedia. In: Proceedings of the 3rd International Workshop on Link Discovery. pp. 90–97. LinkKDD ’05, ACM, New York, NY, USA (2005), http://doi.acm.org/10.1145/1134271.1134284

2. Ceccarelli, D., Lucchese, C., Orlando, S., Perego, R., Trani, S.: Dexter: An open source framework for entity linking. In: Proceedings of the Sixth International Workshop on Exploiting Semantic Annotations in Information Retrieval. pp. 17–20 (2013)

3. Ceccarelli, D., Lucchese, C., Orlando, S., Perego, R., Trani, S.: Learning relatedness measures for entity linking. In: Proceedings of the 22Nd ACM International Conference on Conference on Information & # 38; Knowledge Management. pp. 139–148. CIKM ’13 (2013)

4. Cheng, X., Roth, D.: Relational inference for wikification. In: EMNLP (2013), http://cogcomp.cs.illinois.edu/papers/ChengRo13.pdf

5. Cornolti, M., Ferragina, P., Ciaramita, M.: A framework for benchmarking entity-annotation systems. In: Proceedings of the 22Nd International Conference on World Wide Web. pp. 249–260. WWW ’13 (2013)

6. Cucerzan, S.: Large-scale named entity disambiguation based on wikipedia data. In: EMNLP-CoNLL 2007, Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, June 28-30, 2007, Prague, Czech Republic. pp. 708–716 (2007)

7. Dalton, J., Dietz, L.: A neighborhood relevance model for entity linking. In: Proceedings of the 10th Conference on Open Research Areas in Information Retrieval. pp. 149–156. OAIR ’13 (2013)

8. Durrett, G., Klein, D.: A Joint Model for Entity Analysis: Coreference, Typing, and Linking. In: Proceedings of the Transactions of the Association for Computational Linguistics (2014)

9. Erbs, N., Zesch, T., Gurevych, I.: Link discovery: A comprehensive analysis. In: Semantic Computing (ICSC), 2011 Fifth IEEE International Conference on. pp. 83–86 (Sept 2011)

10. Fader, A., Soderland, S., Etzioni, O.: Scaling wikipedia-based named entity disambiguation to arbitrary web text. In: IN PROC. OF WIKIAI (2009)
11. Fernández, N., Arias Fisteus, J., Sánchez, L., López, G.: Identityrank: Named entity disambiguation in the news domain. Expert Syst. Appl. 39(10), 9207–9221 (Aug 2012)

12. Ferragina, P., Scaiella, U.: Tagme: On-the-fly annotation of short text fragments (by wikipedia entities). In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management. pp. 1625–1628. CIKM ’10 (2010)

13. Finkel, J.R., Grenager, T., Manning, C.: Incorporating non-local information into information extraction systems by gibbs sampling. In: In ACL. pp. 363–370 (2005)

14. García, N.F., Arias-Fisteus, J., Fernández, L.S., Martín, E.: Webtlab: A cooccurrence-based approach to KBP 2010 entity-linking task. In: Proceedings of the Third Text Analysis Conference, TAC 2010, Gaithersburg, Maryland, USA, November 15-16, 2010 (2010)

15. Guo, Z., Barbosa, D.: Robust entity linking via random walks. In: Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. pp. 499–508. CIKM ’14, ACM (2014), http://doi.acm.org/10.1145/2661829.2661887

16. Han, X., Sun, L., Zhao, J.: Collective entity linking in web text: A graph-based method. In: in: Proceedings of the 34th international Conference on Research and Development in Information Retrieval. pp. 765–774 (2011)

17. Hellmann, S., Lehmann, J., Auer, S., Brümmer, M.: Integrating nlp using linked data. In: 12th International Semantic Web Conference, 21-25 October 2013, Sydney, Australia (2013)

18. Hoffart, J., Seufert, S., Nguyen, D.B., Theobald, M., Weikum, G.: Kore: Keyphrase overlap relatedness for entity disambiguation. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management. pp. 545–554. CIKM ’12 (2012)

19. Hoffart, J., Yosef, M.A., Bordino, I., Fürstenau, H., Pinkal, M., Spaniol, M., Taneva, B., Thater, S., Weikum, G.: Robust disambiguation of named entities in text. In: Proceedings of the Conference on Empirical Methods in Natural Language Processing. pp. 782–792 (2011)

20. Kulkarni, S., Singh, A., Ramakrishnan, G., Chakrabarti, S.: Collective annotation of wikipedia entities in web text. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 457–466. KDD ’09, ACM, New York, NY, USA (2009)

21. Marie, N., Gandon, F.L., Giboin, A., Palagi, É.: Exploratory search on topics through different perspectives with dbpedia. In: Proceedings of the 10th International Conference on Semantic Systems, SEMANTICS 2014, Leipzig, Germany, September 4-5, 2014. pp. 45–52 (2014), http://doi.acm.org/10.1145/2660517.2660518

22. Mendes, P.N., Jakob, M., García-Silva, A., Bizer, C.: Dbpedia spotlight: Shedding light on the web of documents. In: Proceedings of the 7th International Conference on Semantic Systems. pp. 1–8. I-Semantics ’11, ACM, New York, NY, USA (2011), http://doi.acm.org/10.1145/2063518.2063519

23. Mihalcea, R., Csomai, A.: Wikify!: Linking documents to encyclopedic knowledge. In: Proceedings of the Sixteenth ACM Conference on Conference on Information and Knowledge Management. pp. 233–242 (2007)

24. Milne, D., Witten, I.H.: An effective, low-cost measure of semantic relatedness obtained from wikipedia links. In: Proceeding of AAAI Workshop on Wikipedia and Artificial Intelligence: an Evolving Synergy. pp. 25–30 (Jul 2008)

25. Milne, D., Witten, I.H.: Learning to link with wikipedia. In: Proceedings of the 17th ACM Conference on Information and Knowledge Management. pp. 509–518 (2008)

26. Moro, A., Navigli, R.: Semeval-2015 task 13: Multilingual all-words sense disambiguation and entity linking. In: Proceedings of the 9th International Workshop on Semantic Evaluation (SemEval 2015) (June 2015)

27. Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab (November 1999), http://ilpubs.stanford.edu:8090/422/

28. Plu, J., Rizzo, G., Troncy, R.: A hybrid approach for entity recognition and linking. In: ESWC 2015, 12th European Semantic Web Conference, Open Extraction Challenge, Portoroz, Slovenia, May 31-June 4, 2015. Portoroz, SLOVENIA (05 2015), http://www.eurecom.fr/publication/4613

29. Ponzetto, S.P., Strube, M.: Knowledge derived from wikipedia for computing semantic relatedness. J. Artif. Intell. Res. (JAIR) 30, 181–212 (2007)

30. Ratinov, L., Roth, D., Downey, D., Anderson, M.: Local and global algorithms for disambiguation to wikipedia. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1. pp. 1375–1384. HLT ’11 (2011)

31. Shen, W., Wang, J., Han, J.: Entity linking with a knowledge base: Issues, techniques, and solutions. Knowledge and Data Engineering, IEEE Transactions on 27(2), 443–460 (Feb 2015)

32. Singh, S., Subramanya, A., Pereira, F., McCallum, A.: Wikilinks: A large-scale cross-document coreference corpus labeled via links to Wikipedia. Tech. Rep. UM-CS-2012-015 (2012)

33. Spitkovsky, V.I., Chang, A.X.: A cross-lingual dictionary for english wikipedia concepts. In: Chair), N.C.C., Choukri, K., Declerck, T., Doan, M.U., Maegaard, B., Mariani, J., Moreno, A., Odijk, J., Piperidis, S. (eds.) Proceedings of the Eight International Conference on Language Resources and Evaluation (LREC’12). Istanbul, Turkey (may 2012)