We address the task of entity-relationship (E-R) retrieval, i.e, given a query characterizing types of two or more entities and relationships between them, retrieve the relevant tuples of related entities. Answering E-R queries requires gathering and joining evidence from multiple unstructured documents. In this work, we consider entity and relationships of any type, i.e, characterized by context terms instead of pre-de ned types or relationships. We propose a novel IR-centric approach for E-R retrieval, that builds on the basic early fusion design pattern for object retrieval, to provide extensible entity-relationship representations, suitable for complex, multi-relationships queries. We performed experiments with Wikipedia articles as entity representations combined with relationships extracted from ClueWeb-09-B with FACC1 entity linking. We obtained promising results using 3 di erent query collections comprising 469 E-R queries.
We hypothesize that it should be possible to generalize the term dependence models to represent entityrelationships and achieve e ective E-R retrieval without entity type restrictions. We propose a novel IR-centric approach using fusion-based design patterns for E-R retrieval from unstructured texts. We make the rst step in that direction by presenting an early fusion strategy that consists in creating meta-documents for entities and entity-pairs (relationships) and then apply standard retrieval models.
In order to leverage information about entities and relationships in a corpus, it is necessary to create a representation of entity related information that is amenable to E-R search. In our approach we focus on sentence level information about entities although it can be applied to more complex methods for text segmentation. We use Wikipedia entity articles and entity-pairs occurrences from ClueWeb-09-B data set with FACC1 text annotations that refer to entities found in the text, including the variances of their surface forms. Each entity is designated by its unique ID and for each unique entity instance we created entity documents comprising a collection of sentences that contain the entity. These context documents are indexed, comprising the entity index. The same is done by creating entity-pair documents and the entity-pair index. These two indices enable us to execute E-R queries using an early fusion strategy with two di erent retrieval models, Language Models and BM25. The approach was tested on a reasonably large-scale scenario, involving 4.1 million unique entities and 71.7 M of entity pairs. 2
Li et al. [
Yahya et al. [
In the scope of relational databases, keyword-based graph search has been widely studied, including ranking
[
Web documents contain term information that can be used to apply pattern heuristics and statistical analysis
often used to infer entities as investigated by [
Existing approaches to the problem of entity-relationship (E-R) search are limited by pre-de ned sets of both entity and relationship types. In this work, we generalize the problem to allow the search for entities and relationships without any restriction to a given set and we propose an IR-centric approach to address it. 3
E-R queries aim to obtain a ordered list of entity tuples TE = <Ei; Ei+1; :::; En> as a result. Contrary to entity search queries where the expected result is a ranked list of single entities, results of E-R queries should contain two or more entities. For instance, the complex information need \Silicon Valley companies founded by Harvard graduates" expects entity-pairs (2-tuples) <company, founder > as results. In turn, \European football clubs in which a Brazilian player won a trophy " expects triples (3-tuples) <club, player, trophy > as results.
Each pair of entities Ei, Ei+1 in an entity tuple is connected with a relationship R(Ei; Ei+1). A complex information need can be expressed in a relational format, which is decomposed into a set of sub-queries that specify types of entities E and types of relationships R(Ei; Ei+1) between entities. For each relationship query there is one query for each entity involved in the relationship. Thus a E-R query Q that expects 2-tuples, is mapped into a triple of queries (QEi , QRi;i+1 , QEi+1 ), where QEi and QEi+1 are the entity types for Ei and Ei+1 respectively, and QRi;i+1 is a relationship type describing R(Ei; Ei+1). For instance, \football players who dated top models" with answers such as <Cristiano Ronaldo, Irina Shayk >) is represented as three queries QEi = ffootball players g, QRi;i+1 = fdated g, QEi+1 = ftop modelsg.
Consequently, we can formalize that a query Q contains a set of sub-queries QE = fQE1 ; QE2 ; :::; QEn g and
a set of sub-queries QR = fQR1;2 ; QR2;3 ; :::; QRn 2;n 1 g. Automatic mapping of terms from a natural language
information need Q to queries QEi or QRi;i+1 is out of the scope of this work and can be seen as a problem of
query understanding [
E-R retrieval requires collecting evidence for both entities and relationships that can be spread across multiple
documents. Therefore, it is not possible to create direct term-based representations. Documents serve as bridges
between entities, relationships and queries. We propose an early fusion strategy speci c to E-R retrieval that is
inspired on the early fusion design pattern for object retrieval [
The relevance score for an entity tuple TE can then be calculated by summing the score of individual entity meta-documents and entity-pairs meta-documents using standard retrieval models. Formally, the relevance score of an entity tuple TE given a query Q is calculated by summing individual relationship and entity relevance scores for each QRi;i+1 and QEi in Q, as follows: score(TE ; Q) = n 1 X score(DRi;i+1 ; QRi;i+1 )w(Ri;i+1; D) + i=1 n X score(DEi ; QEi )w(Ei; Ri;i+1)w(Ei; D) i=1 where w(Ri;i+1; D) is the raw document-relationship association weight, w(Ei; Ri;i+1) is the entity-relationship association weight and w(Ei; D) is the raw document-entity association weight. In this work we use binary associations weights indicating the presence/absence of an entity mention in a document, or a relationship. However, other weight methods can be used. We also use a binary association weight for w(Ei; Ri;i+1) which represents the presence of a relevant entity Ei to a sub-query QEi in a relationship Ri;i+1 relevant to a sub-query QRi;i+1 .
For computing both score(DRi;i+1 ; QRi;i+1 ) and score(DEi ; QEi ) any retrieval model can be used. In this work we run experiments using Dirichlet smoothing Language Models (LM) and BM25. Considering, LM the scores can be computed as follows: scoreLM (DRi;i+1 ; QRi;i+1 ) = scoreLM (DEi ; QEi ) = jQRi;i+1 j
X j=1
0 jDEi j +
E cfqEj 1 jCEj C E A (1) (2) (3) where qj is a term of a sub-query, tfqj;DRi;i+1 or tfqj;DEi is the frequency of a term in the meta-document DRi;i+1 or DEi , Cf the frequency of the term in the entire collection of either entities or relationships (entitypairs) and is the Dirichlet prior for smoothing. Using BM25, the score is computed as summation over query terms, as follows: scoreBM25(DRi;i+1 ; QRi;i+1 ) = jQRi;i+1 j
X j=1
tfqj;DRi;i+1 (K1 + 1) tfqj;DRi;i+1 + K1(1 b + b avjgD(DRiR;ii+;i1+j1 ) scoreBM25(DEi ; QEi ) = jQEi j X
tfqj;DEi (K1 + 1) j=1 tfqj;DEi + K1(1
jEij b + b avg(DEi ) where IDF (qj ) is computed as N n(qj)+0:5 with N as the number of meta-documents on the respective n(qj)+0:5 collection and n(qj ) the number of meta-documents where the term occurs. 5 5.1
We ran experiments with a total of 469 E-R queries aiming for 2-tuples of entities as results. We leave experimentation with longer E-R queries (e.g. 3-tuples) for future work. Relevance judgments consist of pairs of entities linked to Wikipedia.
Query sets for E-R retrieval are scarse. Generally entity retrieval query sets are not relationship-centric [
ERQ consists of 28 queries that were adapted from INEX17 and OWN28 initiatives. Twenty two of the queries express relationships, but already have one entity instance named and xed in the query (e.g. \Find Eagles songs"). Only 6 queries ask for pairs of unknown entities, such as \Find lms starring Robert De Niro and please tell directors of these lms.".
COMPLEX queries were created with a semi-automatic approach. For a speci c domain in a knowledge graph, a pivot entity is selected based on prior domain popularity. A chain of 2-4 entities connected to the entity is created based on a number of facts connecting to the pivot table. A set of di erent chains from several domains was given to human editors to formulate E-R queries answered by the entities in each chain. The query set contains 70 queries from which we removed 10 that expect 3-tuples of entities. COMPLEX consists of pure relationship-centric queries for unknown pairs of entities, such as \Currency of the country whose president is James Mancham \Kings of the city which led the Peloponnesian League." and \Who starred in a movie directed by Hal Ashby? ".
RELink queries and relevance judgments were also created with a semi-automatic approach. A sample of relational tables from Wikipedia was used as input to human editors for manually creating E-R queries. Columns from selected tables represent entity types and the table structure implies one or more relationships among the entities. Relevance judgments are automatically collected from each table. RELink comprises 600 queries aiming 2-tuples and 3-tuples of entities from which we use the subset of 381 queries aiming for pairs of related entities as results. 5.2
We aim to answer E-R queries without speci c or pre-de ned entity or relationship types. Therefore we use
unstructured texts mentioning entities and relationships between entities to create our indices. We use a dump
of English Wikipedia from October 2016 and the ClueWeb-09-B1 collection combined with FACC1[
For our experiments we create two main indices: one for entity extractions and one for entity pairs
(relationships) extractions. For a given Wikipedia article representing an entity we index each sentence and consider it
as an entity occurrence extraction in the entity index. The Wikipedia dump used contains 4.1M entities. We use
ClueWeb-09-B corpus with FACC1 annotations to extract relationship occurrences using an Open Information
Extraction method like [
We adopted a two stage retrieval approach. First, queries QEi ,QEi+1 are submitted against the entity index and QRi;i+1 is submitted against the entity-pair index. Initial sets of top 20K results grouped by entity or entity-pairs, respectively, are retrieved using Lucene's default search settings. Second, the score functions of the speci c retrieval model are calculated for each set, using an in-house implementation. This process is easily parallelized. The nal ranking score for each entity-pair is then computed using the early fusion strategy equation for score(TE ; Q).
We do not optimize the Dirichlet priors E and R in language models and set them equal to the average entity and relationships extractions length, respectively. The same happens with K1 and b in BM25, set to default values of 1.2 and 0.75, respectively. Evaluation scores are reported on the top 100 entity-pair results. 6
We present the results of our experiments in Table 1. We report scores of four di erent retrieval metrics: Mean Average Precision at 100 results (MAP), precision at 10 (P@10), normalized discounted cumulative gain at 10 (NDCG@10) and mean reciprocal rank (MRR). The rst observation is concerning the retrieval model (LM vs BM25). On ERQ, LM shows higher MAP and MRR while BM25 has higher scores for metrics at top 10 results (P@10 and NDCG@10). Although results of both retrieval models are similar, LM outperforms BM25 for every metric on COMPLEX query collection. BM25 has higher MAP on RELink but it is lower on the remaining metrics.
The second observation is concerned with the RELink results which are far lower for both retrieval models on all metrics. The RELink collection is by far the largest collection from the 3, comprising a total of 381 queries. It contains several queries regarding dates. For instance, the query \Find australian lms of 1981 and their directors." returns several entity-pairs comprising australian lms and directors of those lms but not from 1981. The most common relationship query QR in this collection is \located in" which is a very frequent relationship string in our entity-pair index. We hypothesize that returning 20k entity-pairs on the rst passage might result insu cient for RELink as it reduces the search space. In the future, we will further experiment with higher number of results. 7
Work reported in this paper is concerned with expanding the scope of entity-relationship search methods to enable search over large corpora with exible entity types and complex relationships. We have presented an early fusion strategy for fusion-based E-R retrieval. We anticipate that such strategy can be used as exible baseline for further experimentation. For the sake of simplicity and clarity, we have reported on the basic E-R retrieval comprising a single relationship between two entities. In future work, we will report experiments with multiple relationships, as well as, an alternative late fusion strategy for E-R retrieval.