Relatedness-based Multi-Entity Summarization

1 Introduction

The task of extracting, storing, and representing entityrelated information has recently gained significant attention in academia and industry. The Linking Open Data (LOD) initiative has encouraged researchers to publish open and freely accessible entity-based structured knowledge on the Web. Similar to this, many commercial companies have started developing rich, proprietary knowledge graphs (e.g., Google knowledge graph, Microsoft Satori knowledge graph, and Amazon product graph) to support their products, services, and intelligent user interfaces. Intelligent agents like Amazon Echo, Google Now, and Microsoft Cortana utilize these structured knowledge graphs to provide a rich experience to users in the context of question answering and recommendations. Moreover, researchers have shown that knowledge graphs evolve over time by gaining more high quality knowledge [Auer et al., 2013]. As a consequence, the entity descriptions grow in size and selecting a subset of the description depending on the task at hand, referred to as Entity Summarization in the literature [Cheng et al., 2011], is necessary to avoid information overload on the data consumers.

Many flavors of techniques have been applied in creating entity summaries in the recent past. For example, the RELIN [Cheng et al., 2011] and LinkSum [Thalhammer et al., 2016] entity summarization systems have employed PageRank-based ranking mechanisms, the FACES system [Gunaratna et al., 2015] demonstrated an incremental conceptual hierarchical clustering-based approach in creating comprehensive (diverse) summaries, and [Sydow et al., 2013] investigated entity neighborhoods in the graph to generate diverse summaries. Systems such as those mentioned above focus on summarizing individual entities by giving precedence to selecting the most important facts for distinctly identifying an entity. But summarizing a collection of entities by showing related facts (retrieved from a knowledge graph) for quick understanding of the entity collection as a whole compared to individual entities in isolation is an important issue that is yet to be resolved. Such a system can help users to: (i) understand documents when browsing by presenting related facts for entities and (ii) interact with related facts and entities when searching and browsing on the Web (e.g., Google search shows related entity collections). A solution to this problem should maximize the similarity or relatedness of facts selected between the entities as it increases the understandability of the entity collection. For example, Figure 1 shows an example of such a summary creation for "Apple Computer" and "Steve Jobs". For the entity Steve Jobs, it shows more facts about computers than other topics because the majority of the entities are talking about computers or entities related to computers. Further, it shows facts related to the entire entity collection (e.g., selection of "California" for Steve Jobs). In other words, the summary generated for the entity Steve Jobs can vary from document to document depending on the other entities that appear with it. Hence, this kind of a summary is dynamic and context dependent, compared to entity summaries generated by stand-alone entity summarization systems like RELIN and FACES which are context independent and static.

Diversity is an important characteristic that makes entity summaries comprehensive subject to the length constraints. Therefore, we should try to maximize the diversity of the facts selected for each entity summary; otherwise, they may contain redundant facts that make them less in- Within one month of the iPod nano and iTunes phone special event, Apple Computer announced today another special event to be held on October 12. It is to be held at the California Theater in downtown San Jose, California. The invitation reads, "One more thing teresting and useful. We propose RElatedness-based MultiEntity Summarization (REMES) approach that facilitates the above-mentioned characteristics in creating entity summaries for an entity collection. For this purpose, we adapt and map the Quadratic Multidimensional Knapsack Problem (QMKP), which is an extension of the Quadratic Knapsack Problem (QKP) [Pisinger, 2007] and utilize graph-based relatedness and semantic similarity measures. Specifically, we:

1. Generate entity summaries for a collection of entities by: (i) maximizing inter-entity related facts, (ii) maximizing intra-entity importance of facts, and (iii) minimizing intra-entity related facts, by adapting QMKP. We modify a version of the Greedy Randomized Adaptive Search Procedures (GRASP) algorithm to compute entity summaries efficiently.
2. Utilize graph-based and semantics-based relatedness measures to create entity summaries.

We evaluate the proposed approach qualitatively and quantitatively against state-of-the-art entity summarization approaches and show that it generates satisfactory summaries.

The rest of the paper is organized as follows. First, we present related work, describe the problem, necessary notation, and the proposed approach. Next, we discuss the evaluation and results of our approach. Finally, we conclude with future directions.

2 RelatedWork

Entity summarization work can be divided mainly into two categories in relation to the context of this paper. The first set of approaches generate entity summaries for general purpose use and the others are for various specific tasks. Orthogonal to this breakdown, summaries can be generated considering one entity at a time vs. a collection of entities at once.

Several recent efforts involve generating entity summaries for single entity and for general purpose use. RELIN [Cheng et al., 2011], FACES [Gunaratna et al., 2015; 2016], LinkSum [Thalhammer et al., 2016], SUMMARUM [Thalhammer and Rettinger, 2014], diversity-based summaries [Sydow et al., 2013], and contextual entity summaries by mining query logs [Yan et al., 2016] are good examples. In these approaches, RELIN, SUMMARUM, and LinkSum approaches adapt modified random surfer models (PageRank) to rank facts and then select them for summaries. Further, LinkSum does link analysis to select important features. FACES followed a different approach by using a conceptual clustering algorithm to identify different themes of features belonging to the entity and then ranked them to pick concise and diverse entity summary. [Sydow et al., 2013] also followed a diversity based entity summarization approach but they considered filtering out syntactically similar properties when traversing the graph for the entity as improving diversity. All these systems generate summaries by processing one entity at a time and hence, they are unable to capture related facts that might exist between entities in an entity collection. In contrast, our approach REMES is specifically designed to address this problem.

Entity summaries have shown to be effective in performing specific tasks (supporting human effort) like entity linking [Cheng et al., 2015b] and entity resolution [Cheng et al., 2015a]. Unlike previously mentioned approaches, these consider more than one entity. REMES also considers multiple entities but differs by making general purpose summaries, utilizing graph and semantics-based relatedness measures, and focusing on the diversity of each entity summary. For relatedness measures, we used a graph-based path embedding model [Ristoski and Paulheim, 2016] and lexical databasebased semantic similarity computation used in [Gunaratna et al., 2015]. We enforce selecting diverse features for each entity and related features among entities. In addition to modifying the pairwise greedy ranking and profit measures in the GRASP algorithm, we altered the Restricted Candidate List (RCL) by using a threshold for each entity's feature set.

3 ProblemDescription

3.1 Preliminaries

Let E, L, and P be the sets of entities, literals, and properties, respectively, in the knowledge graph G. An entity e (e ∈ E) is described using property-value pairs (p, v) ∈ P x (E ∪ L). A property-value pair is called a feature (f) and the collection of features that belong to entity e is called the feature set FS(e). Using the above notions, an entity summary for an entity e, Summ(e), of size k is defined as selecting a subset of FS(e) such that |Summ(e)| ≤ k and |FS(e)| > k, where k is a positive integer [Cheng et al., 2011; Gunaratna et al., 2015].

3.2 Problem Statement and Description

Problem Statement: Given a collection of entities, we select features belonging to these entities maximizing interentity relatedness and intra-entity importance, and minimizing intra-entity relatedness of features.

In this problem, we consider generating entity summaries for a collection of entities together by selecting features to show the relatedness among the entities and importance and

• …", the teasing tagline of Steve Jobs.

diversity within entities. That is, for a given entity collection {e1, e2, ...en} ⊆ E, and summary length constraints k1, k2, ..kn, we want to generate corresponding entity summaries Summ(e1), Summ(e2), ...Summ(en) that has the maximum score according to the following objectives:

The function r and rank compute relatedness and importance scores in the range [0,1], as discussed in Section 4.3. α, β, γ ∈ R+ are the weights (of the objectives) to be tuned. By maximizing the similarity of facts selected to different entity summaries, we try to provide connections between the entities in their summary descriptions for the user to better understand the coherency of the content. We maximize the selection of important features as well as related ones to make good quality summaries. Further, we avoid selecting similar features for an entity (through imposing negative values) to improve diversity and coverage of features given the summary length constraints.

4 Approach

The problem described in Section 3.2 requires maximizing relatedness, importance, and diversity of features (propertyvalue pairs), controlled by the length of each entity summary for the entity collection. First, let's consider selecting features for an entity e from its feature set FS(e). Then we discuss how to extend it to process an entity collection.

4.1 Selecting Features for an Entity

The features f ∈ FS(e) are numbered from 1 to |FS(e)|. First, the important features need to be selected for the summary. For this, we utilize a tf-idf based ranking score for each feature f . Second, the selection of similar features to the summary should be discouraged to improve diversity (and hence improved coverage). To demote the selection of features that are similar to the already selected ones for the summary from the entity, we represent the relatedness between the features with the negation of the similarity value.

By defining a pairwise profit function for the features, we can map this problem as an instance of the QKP [Pisinger, 2007]. QKP is a generalization of the classical 0-1 knapsack problem where it maximizes a quadratic objective function to a linear constraint [Gallo et al., 1980; Yang et al., 2013]. We define the profit pfi,fj for selecting the feature pair fi and fj for the summary Summ(e) as in Equation 2, where α, β ∈ R+. The function rank(fi) calculates the importance of the feature fi and the function r(fi, fj) computes relatedness of the two features fi and fj. The intuition behind giving a negative value for the relatedness score when the two features belong to the same entity is to make their overall profit lower if they are more related to each other. This discourages selection of new features which are more related to the already selected features for the entity summary (increases diversity).

By introducing a series of binary variables xa for a = 1, 2, ..., |FS(e)| that indicate whether or not the feature fa is selected to the optimal summary, the selection of Summ(e) maximizing the objectives outlined above can be defined as follows in terms of QKP formulation. w(fa) is the weight of the feature of fa and pfa,fb defines the profit for the two features fa and fb.

In the QKP, the algorithm optimizes selecting items that maximizes profit computed between items. In other words, it can be used to select features to the entity summary to get maximum profit by analyzing pairwise profit of the selected features. When using both positive and negative weights as shown in Equation 2, QKP is NP-Hard, that is, it does not have a polynomial-time algorithm to generate solutions unless P = NP [Pisinger, 2007]. Therefore, an approximation algorithm like GRASP can be used to compute a solution.

4.2 Selecting Features for Multiple Entities

The mapping of QKP above refers to creating entity summaries for individual entities. An extension of this to handle multiple entities with the addition of maximizing interentity relatedness features is what we require in our problem. To achieve this objective, we consider mapping this problem to an instance of QKP with multiple constraints, namely Quadratic Multidimensional Knapsack Problem (QMKP). Given a collection of entities e1, e2, .., en, features numbered fi,1 to fi,|FS(ei)| ∈ FS(ei), and having random variables xi,a for i = 1, 2, ..., n and a = 1, 2, ..., |FS(ei)| to denote whether the features fi,a is selected for the best possible summary, the optimization goals can be formalized as follows.

ki is the capacity of knapsack belonging to entity ei. w(fi,a) is the weight of the ath feature of ei and pfi,a,fj,b is the profit for the two features fi,a and fj,b. Note that we have n constraints to satisfy (a knapsack for each entity).

In extending QKP, we adapted a memory-based GRASP [Yang et al., 2013] approach, to simply run with multiple constraints. The algorithm runs through several iterations, and in each iteration, it generates a random solution first based on a greedy ranking function and sampling from the candidate item set. The original GRASP

algorithm proposes a greedy ranking function [Yang et al., 2013] and we modify it to bias the selection of features to also consider future candidate selection. Given the already selected feature set S and candidate feature f, the modified greedy ranking function Gr(S, f) in the construction phase of the GRASP algorithm is as shown in Equation 5. The function w gives weight of each feature and τ, φ ∈ [0,1]. The component related to τ considers the current feature against already selected items and the component related to φ makes the algorithm to consider unselected items in scoring the current feature, making the initial selection of features in the algorithm less random.

Then, in the local search phase, the memory-based GRASP algorithm tries to improve the solution by further maximizing the total profit by swapping selected items with items from the unselected item list. The total profit of the selected items in the summary is calculated by Σi∈SΣj∈S,j≤i pi,j .

Since we have more than one entity to consider in the optimization approach, the profit computation is updated to reflect this need as shown in Equation 6 below. In the equation, α, β, γ > 0 and chosen empirically (tuned). The diagonal of the profit matrix contains the ranking scores (signifying the importance of each feature) and non-diagonal entries contain pairwise relatedness of features. We make profits negative for feature pairs belonging to the same entity so that highly similar feature pairs will not be selected for the same entity.

4.3 Importance, Relatedness and Diversity

Note that we want diverse features to be selected in each entity summary and related features among entities. Further, we do not want arbitrary features to be selected for the summaries but be influenced by their importance. We try to combine these characteristics as shown in Equation 6.

Importance of a feature

The diagonal of the profit matrix has the importance score for each feature f calculated by rank(f ) as shown in Equation 9. We rank features based on how informative the propertyvalue pairs are and how popular the values are [Cheng et al., 2011; Gunaratna et al., 2015]. We try to achieve a trade-off between the two measures similar to tf-idf score in Information Retrieval. Inf(f) computes the inverse logarithmic feature frequency as shown in Equation 7 where N is the total number of entities in the knowledge graph G. The popularity (frequency) of value v of the feature f is computed by Equation 8. Prop(f) and V al(f) are two functions that return the property and value of the feature f. Function rank(f) facilitates selection of important features in the GRASP based summary generation as it can add higher profits for some features which are considered to be important in addition to the pairwise feature profit computed based on relatedness.

Relatedness of a feature pair

We calculate the relatedness of a feature pair by utilizing two measures. First, we employ semantics based measurement to analyze the relatedness between two properties by computing the overlap of terms that represent the two properties. Second, we utilize a graph and co-occurrence based measure to compute relatedness between two values (entities), specifically a vector space model similar to word embedding for graphs.

For the semantics based relatedness measure, we process the property of each feature, with the help of a lexical database, namely WordNet 1 . For a given feature f, we get its property name (label of the property URL) and retrieve hypernyms from the lexical database. We also pre-process them (e.g., remove camel-case and stop words). Then we combine all the extracted terms and original terms for property label of the feature f into a Set Sf . Then the semantics based relatedness SemRelp(fi, fj) of the two features fi, fj is computed by getting the jaccard co-efficient of the two sets of the features Sfi and Sfj as shown in Equation 10. We chose to get hypernyms from the lexical database instead of synonyms or hyponyms because we need to compute the relatedness instead of strong similarity.

We consider a co-occurrence based relatedness to be computed between values of the features. Similar to word embedding models like Word2Vec, we utilize a graph based model called RDF2Vec [Ristoski and Paulheim, 2016] for this purpose. The model was developed using path based cooccurrence and showed promising results in data mining and similarity computation applications [Ristoski and Paulheim, 2016]. We employ a pre-trained model on DBpedia knowledge graph and compute cosine similarity of any given two entities over their vector representation as shown in Equation 11. Given two features fi,a and fj,b belonging to entities ei and ej and the corresponding vector representation of their values (V al(fi,a) and V al(fj,b)) shown as ⃗ V al(fi,a) and ⃗ V al(fj,b) , respectively, and the relatedness measure r(fi,a, fj,b) is defined as in Equation 12.

1 https://wordnet.princeton.edu/

Improving feature diversity in entities

We implemented the GRASP algorithm presented by [Yang et al., 2013] and adapted it to fit our problem solution. We do not provide a detailed description of the algorithm due to limited space. The GRASP approach constructs random solutions and then improves them in the local search phase, in several iterations and returns the best result found so far based on the total profit. Recall that one of our objectives in this problem is to improve diversity of features selected for each entity. In order to achieve that, in addition to the introduction of negative profits, we make changes in the candidate feature selection step. The GRASP approach keeps a candidate set and remaining set of features for the collection of entities. The remaining set contains all the unselected features from the entity collection and candidate set is a random sample of this set. By introducing a threshold value η, we filter out features belonging to the remaining set where their maximum pairwise profit value with any already selected feature is greater than η. That is, for a candidate feature f and the set of selected features S, we filter out f if max(pf,fi∈S ) > η. With this modification, we are able to introduce better diversity in the results for each entity by forcing the combinatorial optimization algorithm to not have access to similar features that have already been selected.

5 Evaluation and Results Discussion

We discuss details of our experiments and results below.

5.1 Implementation Details

In our implementation of memory-based GRASP algorithm, we set γ, β, λ, σ to 1, 3, 5, and 5, respectively (as suggested by authors of GRASP). We normalized profit values by dividing them using the maximum profit. We also added average similarity between the value of each feature and the entity collection to the diagonal of the profit matrix (to improve relatedness). In the greedy ranking function shown in Equation 5, we set τ = 1 and φ = 0.5. In the profit matrix, we used α = 2, β = 1, and γ = 1.5. We set the threshold η = 0.45. The parameter values in the greedy ranking function and profit computation needed to be tuned for this task (we used a separate document sample). Further, in this implementation, we consider feature weights to be uniform and equal to 1. Therefore, the length of the summary for each entity denotes the knapsack size for that entity. We used DBpedia (version 2016-04) encyclopedic dataset as our knowledge graph to retrieve entity descriptions and ran the RDF2Vec model on it. For the semantic relatedness measure, we used the WordNet lexical database.

5.2 Datasets and Evaluation

We evaluated our system using qualitative and quantitative measures. For the qualitative evaluation, we requested a set of judges to rank systems on the Likert scale 2 1 to 5 (1 for strongly disagree and 5 for strongly agree) for a given set of questions. For the quantitative evaluation, we evaluated REMES against other systems for their level of relatedness. We used two document samples taken from two popular entity linking benchmark datasets: (i) Wikinews 3 (20 documents) and (ii) AQUAINT 4 (10 documents).

2 https://en.wikipedia.org/wiki/Likert scale

Qualitative evaluation

We compared REMES with two state-of-the-art stand-alone entity summarization systems: FACES and RELIN. The goal of this evaluation is to measure how successful is each system in selecting summaries for each entity in a collection of entities to maximize inter-entity relatedness and intra-entity diversity and importance of features. We constructed 5 questions to evaluate on a Likert scale (1 strongly disagree and 5 strongly agree). We asked 13 judges to answer these questions for each dataset and each question had at least 5 different judges. The evaluation contains 850 question instances scored by the judges. The questions and the results are shown in Table 1. REMES achieved higher mean scores for all the questions used in the evaluation on the Likert scale. We measured its statistical significance by first performing one-way ANOVA and then using Least Significant Difference (LSD) post-hoc analysis.

Quantitative evaluation

To further evaluate the robustness of our model, we processed the summaries generated by the three systems and compared how effective they were in picking related features between entities. To measure the relatedness between features in the generated summaries, we measured semantic similarity of the entities (by processing their labels in the graph) in those features. In particular, we assessed the relatedness of these entities by employing two state-of-the-art NLP semantic similarity techniques, namely, UCI [Newman et al., 2010] and UMass [Mimno et al., 2011]. UCI was measured by a sliding window and the Point-wise Mutual Information (PMI) of all entity pairs. The entity co-occurrence counts were calculated utilizing a sliding window with the size 10. For every value pair the PMI is calculated on Wikipedia articles as shown in Equation 13.

where Wi,Wj are the labels of the entities ei, ej and the word probabilities (p(W)) are calculated by counting word co-occurrence in a sliding window over Wikipedia. On the other hand, UMass is measured based on document cooccurrence counts as shown in Equation 14.

where D(Wi,Wj) counts the number of documents containing both Wi and Wj words and D(Wi) counts the ones containing Wi, and ϵ is the smoothing factor. We used Palmetto 5 for measuring the UMass and UCI measures (using Wikipedia as the external corpus). Table 2 shows the semantic relatedness of the generated summaries for the three different systems based on above metrics.

3 http://www.newsreader-project.eu/results/data/wikinews

4 http://www.nzdl.org/wikification/docs.html

5 http://aksw.org/Projects/Palmetto.html

5.3 Discussion

In the qualitative evaluation, REMES ranked higher than the other two systems for both the datasets, except for question 2, where p-value (0.18 for Wikinews and 0.20 for AQUAINT) was not significant enough to make a decision between REMES and FACES. This is not totally unexpected because FACES has shown superior capabilities in achieving high quality diversity in generating entity summaries (by using a comprehensive hierarchical clustering approach). In all other questions, REMES outperforms the others and achieved higher mean scores, confirming its ability to generate summaries while maximizing inter-entity relatedness and intraentity importance (and comparable to FACES in diversity). Figure 2 shows summaries generated for two entities using the REMES and FACES systems. While REMES tried to make a connection between the entities (by selecting the leader for Russia), FACES could not get such relatedness. This is mainly because FACES cannot and do not consider other entities in the entity collection.

In the quantitative evaluation, we further confirmed that our approach generates summaries that maximizes relatedness of features for entity collections. We utilized an external knowledge source (Wikipedia) to capture relatedness of facts selected for the summaries. The higher the semantic similarity score, the more related facts are in the summaries generated for the entity groups. Clearly, the summaries generated by REMES are more related according to both the measures and they further confirm the achievement of our objective of creating relatedness based entity summaries for entity collections. Further, we intend to investigate more on what properties to select and similarities and alignments among the properties and entities [Gunaratna et al., 2013; 2014] in creating high quality summaries.

6 Conclusion

Summarizing a collection of entities is challenging since it involves processing all the entities in the collection simultaneously. In this paper, we proposed an approach called REMES to select related features among entities while keeping the diversity and saliency of features within each entity. The approach utilizes a graph-based RDF2Vec model to compute relatedness of two entities and semantic expansion based measure to compute relatedness of two properties. Further, we adapted a QMKP problem instance with implementation of a memory-based optimization algorithm called GRASP. The proposed approach is evaluated against two state-of-theart stand-alone entity summarization systems in two different settings: qualitative and quantitative. Extensive set of experiments using statistical tests (one-way ANOVA and LSD posthoc) on two different datasets, confirmed our model outperformed the others in generating high quality summaries for collections of entities.

In future, we plan to investigate on improving summary quality by analyzing diversity and relatedness and use REMES in real world applications like facilitating Web search and social media text and Web document understanding. The proposed approach can also be improved by deciding what features to select (importance vs. relatedness) based on the neighboring entities.

Acknowledgments

Research reported in this publication was supported in part by NIMH of the National Institutes of Health (NIH) under award number R01MH105384-01A1. Gong Cheng was supported in part by the NSFC under Grant 61572247. The content is solely the responsibility of the authors and does not necessarily represent the official views of the NIH or NSFC.