Representation Learning for Measuring Entity Relatedness with Rich Information

1 Introduction

Heterogeneous text-rich networks, such as social network sites, question answering communities and knowledge graphs, consist of various types of entities as well as large amounts of textual documents [Deng et al., 2011]. They have been popularly used in the research of information retrieval and data mining [Sun and Han, 2012]. Specifically, as the largest online encyclopedia in existence, Wikipedia has been used for knowledge acquisition and semantic analysis for years [Medelyan et al., 2009]. The rich information contained in both the content of articles and the structure of linkage network makes it of great worth for incorporating crossdomain knowledge and interpreting semantic relationships.

In this paper, we aim at measuring semantic relatedness between Wikipedia entities. Former researches usually transform this task into measuring semantic similarity between word senses. Most of existing semantic relatedness measures can be divided into the following three typical types:

∗Corresponding author: Zhiyuan Liu (liuzy@tsinghua.edu.cn).

Text-theoretic measures. These measures build word representations directly from statistical information in text corpus, since related entities tends to be described by similar words. Traditional methods mainly focus on counting the occurrences of words appearing in each Wikipedia article to construct a high-dimensional semantic space [Salton et al., 1975; Gabrilovich and Markovitch, 2009]. In recent years, low-dimensional word representations have achieved great success in many natural language processing tasks [Collobert et al., 2011]. They represent the semantic meaning of word by a vector of latent continuous features.

Graph-theoretic measures. These measures usually take advantage of the hyperlink structure of entity graph. The first strategy is to find the shortest path between given entities [Leacock and Chodorow, 1998]. For instance, if the length of shortest path between stock and petroleum is short, they tend to be treated as related. The second strategy is to compare the neighbors of given entities [Witten and Milne, 2008]. For instance, if the number of common neighbors of stock and petroleum is large, they tend to be treated as related.

Information-theoretic measures. These methods usually takes advantage of the Wikipedia Category taxonomy. It mainly focuses on calculating the information content of each category [Strube and Ponzetto, 2006]. For instance, the information content value of category Fuels is lower than Finance because the former has more parent nodes. Relatedness between stock and petroleum is measured by the information content of their lowest common subsumer Economies.

However, there are two main disadvantages of these measures in practice:

Sparsity. The interactions between entities are relatively sparse compared with the total number of entity-entity pairs. Some of the description articles have even no hyperlinks to other entities. The structure of category taxonomy is even more sparse. In addition, the length of paths between two entities is always limited to a small number. It indicates that path-based measures are relatively less discriminative.

Homogeneity. Most of these measures do not consider the interactions between vertices of different types in the network. It is difficult for them to simultaneously incorporate multiple types of relations, such as entity-word and entitycategory relations, which reduces their scalability and extensibility.

In this paper, we introduce a matrix factorization framework to overcome these problems. We formulate the task of measuring entity relatedness as the completion of an entityentity association matrix, where each entry in the matrix quantifies the strength of relatedness between corresponding entities. In addition, we exploit the random walk process on graph to obtain large amounts of entity sequences, which can capture the co-occurrences between disconnected but related vertices.

In order to incorporate multiple types of relation, we propose to generate a prior association matrix for each component pair, such as entity-entity matrix, category-entity matrix and word-entity matrix. Each entry in the association matrices is modeled as the inner product of two low-dimensional component vectors, as demonstrated in Figure 1. A lowdimensional latent vector space is found for all three components of Wikipedia: entities, categories and words. The representations for all types of components are synchronously constructed in the same semantic space.

We present experiments on word similarity tasks to evaluate the performance of our model. In accordance with the original mission of measuring entities relatedness, we need to verify that each word appearing in the dataset correspond to an entity in Wikipedia. Experiment result shows that our model outperforms both traditional entity relatedness algorithms and other representation learning models.

The key contribution of our work lies in:

• We introduce the coordinate matrix factorization model to measure semantic relatedness between Wikipedia entities. It naturally overcomes the sparsity problem and ensures the relatedness value to be discriminative.
• We present a flexible framework of incorporating multiple types of relations, which can be easily extended by introducing more association matrices in consideration.
• We conducted intensive experiments on word similarity task. Results show that our model achieves a better performance compared with previous methods.

2 ProblemDefinition

In this section, we formally define the problem of learning entity representation and introduce the notations used in our model.

As a text-rich heterogeneous network with different types of components, Wikipedia can be denoted as a graph G = (χ, ξ) where χ is a set of components and ξ is a set of edges between components. Specifically, Wikipedia consists of three types of components, including an entity set E, a category set C and a vocabulary set W, hence χ = E ∪C ∪W. Meanwhile, edges in ξ can be divided into three types of relations, including internal hyperlinks between entities LE = {(ei, ej)|ei, ej ∈ E}, category labels for each entity LC = {(ci, ej)|ci ∈ C, ej ∈ E}, and the occurrences of words in the description article of each entity LW = {(wi, ej)|wi ∈ W, ej ∈ E}, hence ξ = LE ∪ LC ∪ LW .

We aim at discovering a joint latent semantic space H for all three components with common dimensionality K. We define three low-rank matrices EH ∈ R|E|×K , CH ∈ R|C|×K and WH ∈ R|W|×K referring to ensembles of vectors. Each entity ei ∈ E is associated with a continuous feature vector EHi ∈ RK , namely the i-th row vector in EH. Similarly, each category cj ∈ C and each word wl ∈ W are associated with row vectors CHj ∈ RK and WHl ∈ RK respectively.

Once we obtain a vector EHi for each entity ei, the semantic relatedness sr(ei, ej) of two entities ei and ej can be computed by the cosine similarity of corresponding vectors, which is formulated as:

Our goal is to learn an representation matrix EH that approximates the non-zero entries in an entity-entity coefficient matrix X ∈ R|E|×|E| . In the learning procedure, the representation of categories CH and words WH are obtained at the same time. In Section 5 we will show that incorporating category and word representations contributes to the performance of learning entity representation.

3 Coordinate Matrix Factorization

In our model, the procedure of learning entity representation matrix EH ∈ R|E|×K is formulated as the estimation of an entity-entity coefficient matrix X ∈ R|E|×|E| . Each entry Xij in matrix X can be generated using the entity linkage subset LE ⊆ ξ.

The quality of the estimation is evaluated using the NonZero Square Loss (NZSL), which is equivalent to minimizing the following objective function with weighted L2 regularization term:

where EL ∈ R|E|×K is the ensemble of latent constraint vectors for each entity, NX = {(i, j) : Xij ̸= 0} refers to the non zero entries in X, λ is the regularization factor and ‖·‖2F is the Frobenius norm. We will introduce the strategy of generating X in Section 4 in detail.

To incorporate the relation between entities and words, or between entities and categories, we construct two coefficient matrix for each component pair respectively: Y ∈ R|C|×|E| for entity-category relations, and Z ∈ R|W|×|E| for entityword relations. In our model, Y is estimated by the inner product of entity representation matrix EH and category representation matrix EC, while Z is estimated by the inner product of EH and word representation matrix EW. Then the overall loss function is formulated as:

.

where NY and NZ refer to the non-zero entries in Y and Z, with λ, γ, δ are the regularization factors. In the experiment we use λ = 0.01 and γ = δ = 0.005.

We adopt a coordinate stochastic gradient descent scheme to train this model. After initializing each representation matrices EH, EL, CH and WH, we iteratively update one of these matrices with all others fixed. The training procedure stops when it reaches an upper bound of iteration times or achieves an optimal rate of convergence.

During the learning process, we only consider the local loss over one entry in the training set at a time. Take the matrix X for example, when observing a non-zero entry (i, j) ∈ NX, we only update the elements EHik and ELkj in related local vectors EHi and ELj by enumerating the position k. The derivatives of the objective function with respect to each entry are as follows:

where NXi∗ is the number of non-zero entries that appear in row i of matrix X, and NX∗j is the number of non-zero entries in column j of matrix X. At each step of coordinate stochastic gradient descent, we randomly select a sample of (i, j) ∈ NX and make the following updates for each k:

where η is the learning rate. In the experiment we initialize η with 0.01 and linearly decrease it after each iteration.

In a similar manner, we can derive an alternative update for ∂JY/∂EH, ∂JY/∂CH given an entry in Y, and ∂JZ/∂EH, ∂JZ/∂WH given an entry in Z.

4 Generation of Coefficient Matrices

In the scheme of coordinate matrix factorization, the generation process of the coefficient matrices X, Y and Z significantly influences the performance. It is very challenging to directly learn the representation from observed edges in ξ ∈ G due to its sparsity. In this paper, we make use of Random Walk and Positive Pointwise Mutual Information (PPMI) to preset the non-zero entries in the coefficient matrices to overcome the sparsity problem.

4.1 RandomWalk

Random walk has been used in the task of learning representations of vertices in a network, such as DeepWalk [Perozzi et al., 2014]. Given a vertex v in a network, a random walk from root v is a stochastic process to generate an output path p = (v, v1, v2, . . . , vn), where vk+1 is a vertex chosen at random from the neighbors of vertex vk. The main idea of exploiting random walk on graph is to obtain large amounts of vertex sequences, in order to capture the co-occurrences between disconnected vertices.

As mentioned in Section 2, we consider Wikipedia as graph G = (χ, ξ), where χ = E ∪ C ∪ W and ξ = LE ∪ LC ∪ LW. To distinguish multiple types of relations for different coefficient matrices, we split G into three subgraphs: GE = (E,LE), GC = (E ∪ C,LC) and GW = (E ∪ W,LW). For each subgraph, we enumerate all of its vertices as the root of random walk paths. We set the length of a random walks to be fixed with m, and the number of output paths per vertex to be fixed with t. Hence, we obtain |E| · t random walks from GE, (|E| + |C|) · t random walks from GC and (|E| + |W|) · t random walks from GW . For each subgraph, we collect all random walk paths into a document D and treat it as a corpus of special sentences. For example, the document DE of subgraph GE is defined as:

Notice that both GC and GW are bipartite graphs, so that each bigram of vertices (ek, vk+1) or (vk, ek+1) in documents DC and DW contains one and only one entity. In the experiment we set t = 50 and m = 10.

4.2 Positive Pointwise Mutual Information

Recently, word representation models have been shown to perform well in various NLP tasks. One of the most famous training method is Skip-Gram model (SGM) [Mikolov et al., 2013]. Given a corpus of word sequences, the objective of SGM with negative sampling is to maximize:

where ⃗w and ⃗cw are vector representations for word w and its surrounding context cw, Pn(w) is a set of negative word samples, and σ(·) is the sigmoid function. Since we have collected documents DE, DC and DW for subgraphs in Wikipedia, it is intuitive to replace ⃗w and ⃗cw by representations of vertices in these documents, such as EHi and ELj . The difference is that word representation models make use of local context information within words, while we exploit relations between different types of vertices in Wikipedia.

In fact, Levy and Goldberg [2014] have proved that the objective of SGM is implicitly factorizing an coefficient matrix of words and contexts. We adopt their derivation in our task for purpose of generating coefficient matrices X, Y and Z. For example, each entry in X is measured by:

where #(ei, ej) denotes the number of times ei and ej cooccur in the sentences of DE, #(ei) = ∑l #(ei, el) and #(ej) = ∑l #(el, ej) denote the number of times ei and ej appear in DE.

Notice that when k = 0, the Equation 8 is equivalent to PMI because the probability distribution of an entity e can be interpreted as P(e) = #(e) |DE| and the probability of cooccurrence is P(ei, ej) = #(ei,ej) |DE| .

In our model, we omit those entries with negative PMI values, which tend to indicate that the corresponding vertices are not related. We use the Positive PMI value to generate the coefficient matrices:

Similarly, the entries in coefficient matrices Y and Z are approximated by PPMI(ci, ej) and PPMI(wi, ej) respectively. We finally obtain the representation for entities by implementing the coordinate matrix factorization introduced above in Section 3.

5 Experiments

In this paper, we evaluate our methodology by judging the similarity between words. We first introduce the dataset used in the experiment. Then we demonstrate that our model performs the best compared with all baseline methods.

5.1 Dataset

In accordance with the task of measuring relatedness of entities instead of words, we need to verify that each word sense appearing in the dataset corresponds to an entity in Wikipedia. We select the word similarity dataset Words-240 [Xiang et al., 2014] 1 . This dataset contains 240 pairs of Chinese words, each of which is labeled by 20 annotators, which ensures its reliability. Human ratings of pairwise similarity ranges from 0 to 10, where a high number indicates higher similarity.

To confirm that this dataset can be used for evaluating entity representations, we collect the whole Chinese Wikipedia corpus online. It consists of 291,475 entities, 156,601 categories and a vocabulary of 365,650 unique words after word segmentation and removing low-frequent words. In the dataset, we find 9 word pairs that contain words not related to Wikipedia entities. Hence, in this paper we only reserve the rest 231 word pairs for evaluation. We use the same segmented Chinese Wikipedia corpus for all methods, which ensures fair comparison.

In our experiment, we compute the semantic relatedness with entity representation using Equation 1. The result is evaluated against the human similarity ratings using Spearman's ρ correlation coefficient.

5.2 Baseline Methods

In this paper, we compare our model against the following baselines, including information-theoretic models, graphtheoretic models and text-theoretic models:

• Information Content (IC): Resnik [1995] computes the semantic relatedness of two vertices by the information content of the concepts that subsume them in the taxonomy, which is formulated as:

where c1, c2 are category labels of w1,w2 respectively, S(c1, c2) is their common subsumers in category taxonomy C, and the occurrence probability is p(c) = #(C) DC .

• Shortest Path (SP): Leacock andChodorow [1998] uses the length of the shortest path between two vertices to compute semantic relatedness, which is formulated as:

where depth stands for the length of the longest path in the undirected entity subgraph GE.

• Information Distance (ID): If we treat the Wikipedia entity linkage graph GE as a directed graph, the shortest path between e1 and e2 may not be reversible. Hence we also compare with the information distance based on

1 We did not select the famous English dataset wordsim-353 because a higher proportion of word senses in it are not entities in Wikipedia, such as defeating, focus, delay, attempt, recommendation, stupid, etc.

the conditional Kolmogorov complexity [Li and Vit´anyi, 2009]:

• Wikipedia Link-based Measure (WLM): Milne and Witten [2008] proposed a low-cost measure of semantic relatedness based on Wikipedia entity graph, inspired by Normalized Google Distance [Cilibrasi and Vitanyi, 2007]:

where E1 and E2 are the sets of all entities that link to e1 and e2 respectively.

• Skip-gramModel (SGM): Skip-Grammodel [Mikolov et al., 2013] utilizes textual information to capture latent word relationships. We use Wikipedia articles as training corpus to learn word vectors. Hyperlinks between entities are reserved and represented by unique tokens.
• DeepWalk (DW): DeepWalk [Perozzi et al., 2014] learns representations of vertices in a graph with a random walk generator and language modeling. We use the combination of random walk path documents D = DE ∪DC ∪DW to train this model.

5.3 Experiment Results

We report the experiment results of four variations of Coordinate Matrix Factorization (CMF) models and six baselines on the dataset. In the experiment, we set the dimensionality K of the vector space to be 200. We respectively collect 182,774,540, 10,199,647 and 35,926,605 non-zero entries in the coefficient matrices X, Y and Z.

Table 1 demonstrates the performances of different methods. As we can see, when we exploit all of the three coefficient matrices, CMF achieves a highest of 0.465 on Spearman's ρ correlation coefficient with human ratings, which is at least 0.023 higher compared with any of the six baselines. This result shows that our representation learning method can better predict the similarity between entities. Moreover, CMF performs better when more coefficient matrices are used. It indicates that incorporating multiple types of relations in Wikipedia contributes to the performance of learning entity representation. Specifically, we find that the performance of CMF with matrices X, Y is better than that with X, Z, even if Z contains twice more non-zero entries than Y. It indicates that entity-category relation is more beneficial for measuring entity relatedness.

We also notice that with the same types of relation used, CMF achieves the best performance in all circumstances. If we only use the entity-entity relation in X, CMF achieves 0.4413 on Spearman's ρ correlation, which is higher than the results of SP, ID and WLM. If we use additional entitycategory relation in Y, CMF significantly outperforms IC.

Surprisingly, we find that CMF with entity-entity and entity-word relations in X, Z outperforms SGM with an improvement of 0.024, even though we retain both anchor texts and referenced entities in the content of Wikipedia articles as training corpus. The reason is that SGM only captures the co-occurrences of entities and words in a limited context window, while CMF captures the relation between an entity and all words in the corresponding description article. Moreover, the number of hyperlinks in Wikipedia limited the amount of entity-word relations that SGM can access.

Finally, we find that CMF performs better than DeepWalk using the same types of relations, which confirms that unsupervised feature learning via neural language model is approximated to matrix factorization on specific coefficient matrices. It is worth mentioning that if we strictly follow the Shifted PPMI metric [Levy and Goldberg, 2014] with the same negative-sampling parameter, DeepWalk is implicitly factorizing CMF model with coefficient matrix X = EH · E⊤H instead of current X = EH · E⊤L .

5.4 Computational Cost

The validation of performance implies not only effectiveness but also efficiency. Among all the baselines, IC, SP, ID and WLM are heuristic functions with no training phrase, but during testing phrase they are thousands of times slower than vector based models. SGM and DeepWalk both utilize SkipGram model for representation learning, which traverses all co-occurrences of entity pairs. CMF model compresses the information into association matrices, so that the time cost of each iteration is smaller. However, CMF requires larger number of iterations to converge because it optimizes an overall loss function involving the whole matrices.

In the experiment, we use a computer with eight Intel Xeon 2.00GHz processors for parallel computing. It takes three hours for Skip-Gram model to converge. For CMF model, the average time cost of an iteration is 4.6 minutes and it converges after 220 iterations. It indicates that the time cost of CMF is higher than Skip-Grammodel but still feasible.

5.5 Case Study

To demonstrate the effectiveness of entity representation in CMF model, we provide an example of three entities and their top 10 nearest neighbors, as shown in Table 2. We observe that semantically related entities are closer in the vector space, which validates that our entity representation is capable of measuring semantic relatedness.

In order to gain more information on the limitation of our model, we provide some examples of severe conflicts between CMF and human ratings, as can be seen in Table 3. We find that CMF has trouble in identifying implicit relations, which is usually straight forward to humans. For instance, the correlation between movie and popcorn, physician and obligation originates from human's feeling and life experience, which is hard to infer from the link structure of entity graph or from the content of articles.

Meanwhile, some word pairs are considered as related by CMF but are assigned with low human ratings, such as future and prophecy, chemistry and atom. They tend to appear in each other's description article and provides large amounts co-occurrence information. However, these entities are usually about science or philosophy, so it is more difficult for annotators to be conscious of their relevance.

6 RelatedWork

Traditional measures of semantic relatedness build word representation directly from statistical co-occurrences in text corpus. Words are represented in a high-dimensional semantic space depending on the bag of words representation [Salton et al., 1975], but human semantic space is actually of fairly low dimension. Hence, a variety of vector-space models have been proposed to decrease the dimensionality and to interpret the latent meaning of each dimension. Latent Semantic Analysis [Landauer and Dumais, 1997] reduces the dimensionality by factorizing a word-by-document matrix. Explicit Semantic Analysis [Gabrilovich and Markovitch, 2009] interprets each dimension by concepts (i.e. entities) in Wikipedia. These methods are proved effective on constructing word representations and measuring word similarities.

With the growth of Wikipedia, more researchers have begun to focus on the structure of its article graph and category taxonomy. Ollivier and Senellart [2007] use article graph structure to find related entities. Ponzetto and Strube [2006] use category taxonomy structure to estimate semantic relatedness between entities. Chernov et al. [2006] also extract semantically related categories with the aid of category links.

West et al. [2009] aim at collecting human click statistics to help compute semantic distance.

Yeh et al. [2009] first manage to explore the use of multiple link types taken as a uniform graph in Wikipedia. They applied random walks on Wikipedia article graph with Personalized PageRank. Shirakawa et al. [2009] first introduce the idea of constructing high-dimensional concept vectors from Wikipedia category network. In contrast, neural language models can induce low-dimensional word representations [Turian et al., 2010], but the latent semantic meaning of each dimension can not be interpreted. Perozzi et al. [2014] first take advantage of neural language models in learning vector representation for vertices in the network.

Matrix factorization maps different factors to a joint latent space of the same dimensionality. It is widely used in collaborative filtering and recommender systems [Koren et al., 2009]. Levy and Goldberg et al. [2014] first introduce this technique for learning word representation. They proved that word representation model is implicitly factorizing a specific word-context matrix.

7 Conclusion

In this paper, we propose a coordinate matrix factorization based method for measuring semantic relatedness on Wikipedia, which incorporates multiple types of relation between entities, categories and words. We construct lowdimensional continuous representations of entities, and formulate the task of measuring entity relatedness as the completion of an originally sparse entity-entity association matrices. Experiment result shows that our model achieves better performance compared with traditional measures, neural word representations and other entity representations.

Acknowledgments

This research is supported by the 973 Program (No. 2014CB340501) and the National Natural Science Foundation of China (NSFC No. 61133012 & 61170196).