Semantic Relationship Discovery with Wikipedia Structure

1 Introduction

Discovering semantic relationship between concepts is easily handled by humans but remains a obstacle for computers. During recent years, Wikipedia, the world's largest collaborative encyclopedia, has accumulated vast amount of semistructured knowledge (e.g. 17 million concepts in total and 3 million in English), which to some extent reflects human's cognition on relationship.

Many prior researches on semantic computation with Wikipedia structure can only compute the tightness of the relationship between two concepts but not give which kind of relationship it is [Ollivier and Senellart, 2007; Adafre and de Rijke, 2005; Milne, 2007; Hu et al., 2009]. This is partly due to the fact that most of these work are originated from information retrieval in which the articles and links on wikipedia are analogous to the pages and links on the web, which do not seize the specialty of Wikipedia stucture.

In this paper, we proposed concept-category graph to model Wikipedia structure in which concepts and categories are treated as different nodes. We assume that the links between concept and category (category links) and the links between concepts (related links) present two senses of relatedness. A illustration is shown in Fig. 1. Concepts can be related in two different ways: linking to same categories or linking from each other by anchor texts. Further, the category itself can be used to interpret the relationship between the concepts linking to it because it naturally represent the general character of these concepts.

Inspired by the mutually reinforcing nature of HITS [Kleinberg, 1999], an new algorithm RCRank (joint ranking of related concepts and categories) is proposed to jointly compute concept-concept relatedness and conceptcategory relatedness base on the observation that information carried in related links and category links can reinforce each other. By RCRank, we can get top-n most relevant concepts and categories for each concept on Wikipedia. For each pair of concepts, our method can return a list of categories which best interpret the relationship between them even if they do not share common categories. Experimental results on concept recommendation and relation interpretation show that our method substantially outperforms classical methods.

The contributions of this paper are twofold. First, we are the first to discover the semantic relationship between concepts with Wikipedia, which is different from previous work on relatedness computation. Second, we present RCRank, a simple link-analysis algorithmwhich seize the semantic characteristics of Wikipedia stucture. It is also applicable to applications where two relations can reinforce each other.

2 Our methods

2.1 Intuition

Category links and related links present two senses of relatedness in Wikipedia. Usually, people link a concept to a category because they think the category is more general than the concept in some respects. Others may find more related concepts if they navigate through this link and view other concepts under the same category.

Related links are created from the content of articles in the form of anchor texts. If a user find a name entity in the article referring to another article, he can turn the name entity into an anchor text linking to corresponding article. Each article is a concise description of the corresponding concept. So if one concept is linked to from the article of another, they are likely to be related.

Now the question is: can we measure concept-concept and concept-category relatedness based on these two kinds of links?

To answer this question, we propose the following two hypotheses which characterize how concept-concept and concept-category relatedness mutually reinforce each other.

• H1: If a category is shared by many related concepts of a concept, it is likely to be related to this concept.
• H2: If two concepts share many related categories, they are likely to be related.

In the next two sections, we will formalize these heuristics by concept-category graph and RCRank.

2.2 Concept-Category Graph

In Wikipedia, we denote the set of concepts and categories by U and V. Cardinality of U and V are denoted by m and n. The concept-category graph is defined as follows.

Definition 1 A concept-category graph is defined as a 4tuple G = (U, V, EC, ER) in which EC ⊆ U × V and ER ⊆ U × U. 〈ui, vj〉 ∈ EC iff. vj is linked to from ui and 〈ui, uj〉 ∈ ER iff. uj is linked to from ui .

We define m×n matrix C = [cij ] in which cij is the relatedness between concept ui and category vj and m×mmatrix R = [rij] in which rij is the relatedness between concept ui and concept uj. Also, we require C and R to subject to the following properties.

• For each ui, we have cij ≥ 0 for each vj and there exist some vj′ satisfying cij′ > 0. (non-negative)
• For each ui and uj, we have 0 ≤ rij ≤ 1 and rii = 1. (similarity metric)
• For each ui and uj, we have rij = rji. (symmetry)

The properties of R are natural for a relatedness metric. The non-negative requirement on C is to ensure the similarity metric property of R after iterations in RCRank.

2.3 RCRank

To mutually reinforce R and C, we express H1 and H2 by the following equations.

Eq. 1 is a "voting" process. For a given concept ui, the new score of category uj is voted by all the related concepts of ui. The more related a concept is, the more important its votes are.

In eq. 2, the concepts are projected to n-dimensional category space. The ith row of C is the image of concept ui on category space and r′ij is actually the cosine similarity between ui and uj on category space.

Both eq. 1 and eq. 2 can be written into matrix form as

in which matrixMT is transposition of M and

in which diag(.) results in a diagonal matrix in which all elements are zero except the diagonal elements whose values are from the input matrix of the same positions. diag(CCT ) is invertible because of the non-negative property of C.

Given a concept-category graph G, RCRank works as follows:

1. Initialize R(0) and C(0) from the concept-category graph G.
2. For each time t, compute
3. C(t) = R(t - 1)C(t - 1)

Before initializing R(0) and C(0) from G, we first define MC and MR in which the entries are 1 if the corresponding edges belong to EC and ER respectively, or else 0.

To satisfy the non-negative property of C, we create a dummy category for each concept without categories. Formally, denote nd as the number of concepts without categories. we define

in which MdC is a m × nd matrix defined as

To satisfy the similarity metric and symmetry properties of R, we define R(0) as

, in which I is m ×m identity matrix and μG ∈ [0, 1] is a parameter depends on graph G.

Intuitively, μG weighs the influences between category links and related links. Consider the following two extreme cases:

• If μG = 0, the information carried in related links is ignored and the relatedness between two concepts is solely judged by how many common categories they share.

• If μG = 1, the categories links of a concept are submerged by the categories links of its related concepts. The relatedness between two concepts is dominated by the related concepts they share.

To balance the influences between category links of a concept and related links, for each concept i, we define

μG is defined as the geometric mean of μG(i).

From the definition we can see that μG is between 0 and 1 and it will decrease while ER getting denser and increase while ER getting sparser.

During the iteration process of RCRank, it is easy to prove that if R(0) and C(0) satisfy the basic properties, so will R(n) and C(n). Will this iteration converge and what is the stop criterion?

The convergence analysis of RCRank is given in appendix A. Intuitively, if R(0) and D(0)C(0) are regarded as human annotated data, R(∞) and D(∞)C(∞) are considered as a priori values, the iteration of RCRank is actually a process of smoothing. The time t balance the preference between posteriority and priority.

RCRank converges exponentially fast. In our experiments on small concept-category graphs in which |U| and |V| are between 10 and 50, most of them converges on t = 3 or 4. From Fig. 2 it is easy to see that R and C will be over smoothed when they converges. In this paper, we compute R(1) and C(1) for empirical evaluations.

2.4 Semantic Interpreter

Inspired by Explicit Semantic Analysis [Gabrilovich and Markovitch, 2007], we build a Semantic Interpreter(SI) that maps each pair of concepts ui and uj into weighted vector of categories. SI(ui, uj) is a vector of categories in which the weight of each category vk is defined as

. For simplicity, we write SI(ui, ui) as SI(ui).

When we compute SI(ui, uj ) with C(0), the weight of each category is determined by whether it is linked to from both ui and uj. When using C(1), SI(ui, uj) represents the contribution of each category on the semantic relatedness between ui and uj , in which the categories with non-zero weights are not necessarily linked from ui and uj.

3 Empirical Evaluation

3.1 Data Preparation

We implemented RCRank on a Wikipedia snapshot of August 22, 2009. After removing redirect pages, we got 2,997,315 concept pages and 539,527 category pages. Each concept linked to 3.262 categories and 19.914 concepts on average. To ensure the relatedness of related links, only mutual links were retained, which resulted in 3.698 concept links per concept.

A IA-64 server with 64 CPUs(1.3G) and 64 GB memory was used to compute sparse matrix multiplication. It took 30 hours to compute C(1) and R(1) on the whole data. For memory concern, we only retained top 50 largest entries for each row of R(1). For each concept ui, we recommended concepts corresponding to the top-n largest entries in row i.

3.2 Experiment: Concept Recommendation

To evaluate the quality of concept recommendation, we carried out a blind evaluation of five methods on seven different concepts, which were: (i) Donald Knuth: a short biographical article with many categories. (ii) Germany: a very large article about a country with a few categories. (iii) Dog: a medium-sized introductory article about a common concept. (iv) HiddenMarkovModel : a short technical article. (v) Romance of Three Kingdoms: a large narrative article about a Chinese literature. (vi) World War II : a very large article with many categories about a historical event. (vii) Gmail : a short article about a commercial product.

For each concept, we put the top 20 results returned by each method together and asked each evaluator to assign a recommendation score between 0 and 5 (5 being the best) to each result. Evaluators should consider both relatedness and helpfulness of each result. For example, France is semantically related to Pierre de Fermat since Fermat is Frenchman. But the information contained in France has little to do with Pierre de Fermat, so it is not helpful. The golden standard relatedness between each query and recommended concept was the average of marks from each evaluator. Cumulative Gain(CG) and Discounted Cumulative Gain(DCG), which are widely used in information retrieval, are used to evaluate the result list of each method on each concept. There has been a total of 5 evaluators and the average of pairwise Pearson correlation coefficient is 0.61.

Description of the Methods

We compared the following five methods.

COCATEGORY. A straight-forward method which evaluate the semantic relatedness between two concepts solely on the number of category links they have in common. It returns concepts which share most categories with the query concept.

COCITATION. In this method, two concepts are more related if their cocitation count, which is the number of concepts pointing to both of them, is larger. For a given concept u, COCITATION ranks all concepts by their cocitation counts with u and return the top-n concepts.

WLVM. Wikipedia Link Vector Model(WLVM) [Milne, 2007] recommends concepts by related links. Each concept is represented by a weight vector of related links. Similar to TF-IDF in information retrieval, the weight of each link ua → ub is:

, which is the link counts weighted by the probability of each link occurring. Given a concept u, WLVM ranks all concepts by their cosine similarity with u and return the top-n concepts.

TFIDF. This method represents each concept by a weight vector of related links just the same as WLVM. For a query concept, TFIDF returns the concepts corresponding to the related links with top-n largest weights.

RCRANK. For a query concept ui, we recommend concepts corresponding to top-n largest entries in the ith row of R(1).

Performance of the Methods

The performance of each method is listed on Tab. 1, from which we can see that the overall performance of RCRANK is better the others on both CG and DCG. It is worth noticing that the overall CG of TFIDF is significantly better than the other baselines but the DCG of TFIDF is only slightly better than WLVM, which shows that anchor text itself is a good source for recommendation but TFIDF is not good enough to evaluate the relatedness for each anchor text. Compared with other methods, the performance of RCRANK is more stable on different kinds of concepts, especially on the concepts with short articles such as "Donald Knuth" and "Hidden Markov Model". By mapping related links into category space, RCRANK not only evaluates the relatedness of each linked concept but also finds more related concepts by generalizing the semantic meaning of related links on highly related dimensions in category space.

3.3 Experiment: Category Selection

In preliminary experiment on concept recommendation we found that in most cases, the category that reasonably interpret the relationship between query concept and recommended concept can be found from categories linking to from the recommended concept. Therefore in this experiment, given a query concept ui and a recommended concept uj, we selected a category from the category set of uj which can best interpret the relationship between ui and uj.

The test set was constructed as follows. First, 20 query concepts were chosen for their diversity. For each concept, we randomly selected 25 concepts from the top 50 results returned by RCRANK. For each pair of concept, we asked four annotators to choose at least one category from the category set of uj which can best interpret the relationship between ui and uj. The final score of each category was the total number of times it was chosen divided by the total number of annotators. In this task, we think precision is much more important than recall as far as user experience is concerned. So for each method, we only select one category for each pair of concept and evaluate its precision. The following four methods are compared in this experiment.

Random. A baseline method which randomly select one category from the category set of recommended concept uj.

Frequency. This method select the category from the category set of recommended concept uj which is most frequently appeared in Wikipedia.

SISingle. This method select the category from the category set of recommended concept uj with largest weight in SI(uj ).

SI. This method select the category from the category set of recommended concept uj with largest weight in SI(ui, uj).

The precision of eachmethod is shown in Tab. 2. From the results we can see that SI significantly outperform the others. SISingle is inferior to SI because it does not use the information contained in query concept. The performance of Frequency is worse than Random, which shows that frequently appeared categories are too board to represent the relationship. For example, "Living people" is selected by Frequency to represent the relationship between "Steven Spielberg" and "Martin Scorcese", nevertheless "American film directors" is more preferable.

3.4 Case Study

Tab. 3 shows top 10 results from TFIDF, WLVM and RCRANK on "Gmail" and "World War II". The results on "World War II" show that no method is significant better than the others because "World War II" is a huge article with a large number of highly related concepts. The results on "Gmail" show that the concepts recommended by RCRANK is focused on different aspects of "Gmail", such as "Gmail interface" and "History of Gmail". It helps user to find more relevant information if he is interested in "Gmail". By contrast, the results fromTFIDF andWLVM are less relevant.

Fig. 3 shows the results by our method on the concept "Germany" in which top 12 recommended concept are shown. For each recommend concept u, we calculate SI(u, "Germany") and select the categories from the category set of u of which the weights are more than eighty percent of the largest weight. From the results we can see that most categories are reasonable to represent the relationship between concepts. Moreover, although many concepts in Wikipedia can be linked to dozens of categories, most of them are not suitable to interpret the reason for recommendation. Our methods can pick out the ones which are both popular and related to input concept. For example, apart from "German physicists", the concept "Max Born" is also linked to categories such as "Theoretical physicists", "Nobel laureates in Physics" and "German Lutherans". The first two categories do not give the relation between "Germany" and "Max Born" directly. The last one is related to "Germany" but is not as well-known as "German physicists".

4 RelatedWork

In the area of finding related concepts on Wikipedia, Adafre and de Rijke [2005] identified missing related links using a cocitation approach. Ollivier and Senellart [2007] recommended related concepts by Green method, which was a classical Markov chain tool. In [Hu et al., 2009], a randomwalk algorithm was proposed to propagate relatedness from seed concepts to unlabeled concepts. To our knowledge, none of these methods can give semantic relationship between query concept and recommended ones.

Another related area of our work is computing semantic relatedness using Wikipedia. WikiRelate! [Strube and Ponzetto, 2006] is the first approach one this area. Given a pair of words w1 and w2, WikiRelate! first maps them to Wikipedia titles p1 and p2 and then compute semantic relatedness using various traditional methods which rely on either the content of articles or path distances in the category hierarchy of Wikipedia. Different fromWikiRelate!, the Wikipedia Link Vector Model(WLVM) [Milne, 2007] represents each article by a weighted vector of anchor texts and the weights are given by a measure similar to tf-idf. ESA [Gabrilovich and Markovitch, 2007] is another semantic relatedness measure which achieve good results in correlation with human judgments. ESA represents each text as a weighted vector of Wikipedia-based concepts and assess the relatedness on concept space using conventional metrics.

In collaborate filtering, Breese et al.[1998] proposed a memory-based algorithm for predicting user's rating, which looks similar to RCRank if users and items are considered as concepts and categories. The rating score of a user on an item is computed from the weighted average scores of similar users. The weight of each similar user can be given by cosine similarity on their previous rating on other items. The main difference is this algorithm compute the relatedness in one relation(user-item) while RCRank mutually compute the relatedness between two relations.

5 Conclusion

We proposed a novel method RCRank to jointly compute concept-concept relatedness and concept-category relatedness with the mutually reinforcing assumption of related links and category links. Base on RCRank, we can discover the semantic relationship between concepts with Wikipedia, which is fundamentally different from previous work on relatedness computation. The empirical evaluation results on concept recommendation and relation interpretation show that our method substantially outperforms classical methods.

Acknowledgments

This work is supported by Canada's IDRC Research Chair in Information Technology program, Project Number: 104519-006, the Chinese Natural Science Foundation grant No. 60973104, the National Basic Research Program No. 2007CB311003 and China Core High-Tech Project No. 2011ZX01042-001-002. The computing platform is provided by HPC center of Tsinghua University.

A Convergence Analysis

To analysis the convergence of RCRank, we first define the connected relation between two concepts as follows.

Definition 2 Two concept nodes ui and uj are connected in G iff. there exists a sequence of nodes 〈u0 = ui, u1, ..., un = uj〉 in which either 〈uk-1, uk〉 ∈ ER or there exists a category node v such that 〈uk-1, v〉 ∈ EC and 〈uk-1, v〉 ∈ EC for k ∈ [1, n].

From definition 2 it is easy to see that connected is a equivalence relation according to which the concepts can be partitioned into equivalence classes. The following theorem shows that if ui and uj are connected, the relatedness between them will converged to 1.

Theorem 1 If C(0) and R(0) are initialized by Eq. 5 and Eq. 6 , we have

Theorem 1 can be proved by showing that in each equivalence class, during each iteration, the minimum conceptconcept relatedness is larger than or equal to the minimum relatedness on last iteration. The equality holds if and only if the minimum concept-concept relatedness in the corresponding equivalence class reaches to 1.

Theorem 2 If C(0) and R(0) are initialized by Eq. 5 and Eq. 6, D(t)C(t) will converge to a equilibrium in which row i and j are identical if ui and uj are connected.

Convergence of D(t)C(t) can be proved straightforward from theorem 1. Each entry (i, j) of the equilibrium of D(t)C(t) reflects the popularity of category vj in the equivalence class containing ui.