Constrained Information-Theoretic Tripartite Graph Clustering to Identify Semantically Similar Relations

Introduction

A relation triplet (e1 , r, e2 ) is one popular form for knowledge representation. For example, in a knowledge base, such as Freebase 1 , a typical relation triplet contains e1 = Larry Page, e2 = Google, and r = is founder of. This means that two entities "Larry Page" and "Google" hold the relation "is founder of." With the recent development of knowledge graph and open information extraction (open IE) [Banko et al., 2007; Fader et al., 2011; Schmitz et al., 2012], there are many cases where multiple relation expressions indicate semantically similar relations. 2 The ability to group semantically similar relations into clusters would facilitate and improve many applications, including knowledge base completion, information extraction, information retrieval, and more. Consider the following examples.

1 https://www.freebase.com/

2 We use relation expression to represent the surface pattern of the relation. Sometimes they are of the same meaning.

Ex. 1: (X, wrote, Y) and (X, 's written work, Y).

These two relations are identical, since the meaning of the two expressions is the same when X and Y are instantiated. This kind of relation clustering is very useful for predicate invention [Kok and Domingos, 2007] and knowledge base completion [Socher et al., 2013; West et al., 2014], since we can easily replace the entities (e.g., X or Y) of one relation with the corresponding entities of another one, and use different relation expressions to search for more entities.

Ex. 2: (X, is founder of, Y) and (X, is CEO of, Y).

These two relations are not the same, but they are more similar than the case when compared to (X, wrote, Y). Identifying them as similar could be useful as an initial guess for textual entailment [Dagan et al., 2013]. For example, if a text contains "Larry Page founded Google on September 4, 1998," the following hypothesis is likely to be true: (Larry Page, is CEO of, Google).

This example contains a multi-hop relation, which is a conjunction of multiple relations. If we can find many entities to instantiate such relations, we can group them together. When we retrieve relations using entity pairs, we can interpret these relations interchangeably. For example, we can use "Harry Potter and the Philosopher's Stone" and "J. K. Rowling" to search the knowledge base and check the possible relation expressions between them. We can then interpret (X, written by, Y) as (X, part of, Z)∧(Y, wrote, Z), and the latter has more information (e.g., we have Z = "Harry Potter Literary Series") about the relation between X and Y. In addition, identifying the multi-hop relations allows hypothesizing possible rules for knowledge inference [Richardson and Domingos, 2006].

All of the above examples boil down to a fundamental relation clustering problem. Clustering can help us identify a lot of such useful semantically similar relation expressions. There have been several relation clustering algorithms proposed, e.g., using one dimensional clustering (e.g., Kmeans) [Bollegala et al., 2009], co-clustering [Dhillon et al., 2003; Bollegala et al., 2010], non-parametric Bayeisan modeling [Kemp et al., 2006], multi-relational clustering using Markov logic network [Kok and Domingos, 2007; 2008], and tensor decomposition based clustering [Sutskever et al., 2009; Kang et al., 2012]. However, there is a major problem in the previous work.

Previous approaches only considered clustering relation expressions based on the intersection of the associated entity sets. However, there exists important background knowledge that can be used to improve clustering. For example, in both relations (X, is founder of, Y) and (X, is CEO of, Y), the left entity X should be a person and the right entity Y should be an organization. If we can constrain the entity types, then some illegitimate relations for a relation cluster can be filtered out.

In this paper, we propose a Constrained Tripartite Graph Clustering (CTGC) algorithm to tackle this problem. We introduce side information via must-link and cannot-link constraints to improve the clustering results. Then the type information about the entities can serve as an indirect supervision for relation clustering. To verify the indirect supervision, we derive the constraints either from ground-truth of entities and relations, or based on knowledge automatically induced from the data. We use two real world datasets to evaluate the clustering results. The first dataset is based on a human annotated knowledge base, Freebase. We generate constraints based on the ground-truth types of entities and relations. This dataset is used to demonstrate the effectiveness of the algorithm. The second dataset is the data extracted by an open IE system, ReVerb 3 . For this data, we generate entity constraints based on the results from a state-of-the-art named entity recognizer [Ratinov and Roth, 2009], and the relation constraints based on the similarity between relation expressions. This dataset shows that the indirect supervision can be automatically obtained. Even the constraints are not perfect, the information can be used to improve relation clustering results. Our contributions can be summarized as twofold:

• We formulate the relation clustering problem as a constrained tripartite graph clustering problem and develop an alternating optimization algorithm to find the clusters of relations.
• We use two datasets to demonstrate our approach: a dataset with Freebase relations and a dataset with open IE relations. The two datasets both show the effectiveness of the clustering algorithm and the usability of real applications.

Related Work

In this section, we discuss the related work from both problem and algorithm perspectives.

Relation Clustering Problems

There has been a lot of work on relation extraction from text, most of which are supervised or semi-supervised methods relying on training data [Mintz et al., 2009; Chan and Roth, 2010; 2011; Li et al., 2011; Li and Ji, 2014]. Researchers also considered using clustering to perform unsupervised relation extraction [Hasegawa et al., 2004; Shinyama and Sekine, 2006; Kok and Domingos, 2008; Yao et al., 2011; Wang et al., 2013]. Some of the relation extraction algorithms tried to find clusters among relation expressions between restricted types of named entities to discover unrestricted types of relations [Hasegawa et al., 2004; Shinyama and Sekine, 2006; Riedel et al., 2013; Rockt¨aschel et al., 2015]. This is similar to our approach when ours is applied to open information extraction [Banko et al., 2007; 2008; Fader et al., 2011]. Nonetheless, there are two major differences. First, they only considered relation types between fixed types of named entities. However, most of the open domain relations are not restricted to named entities [Banko et al., 2007]. Thus, our method is more flexible and extensible because we cluster the relations from open information extraction directly based on the data statistics and only use named entities as constraints. Second, besides relation extraction, our algorithm can also be applied to knowledge bases to canonicalize different relations with clusters [Gal´arraga et al., 2014], especially with multi-hop relations (shown in Ex. 3 in the introduction). Therefore, we are trying to solve a more general problem.

3 http://reverb.cs.washington.edu/

Relation Clustering Algorithms

As we mentioned in the introduction, there have been several different formulations of the relation clustering problem resulting in different algorithms. We solve the problem by modeling the data as a tripartite graph clustering problem, which incorporates more information than onedimensional clustering and co-clustering, and uses more condensed information than tensor based clustering. Moreover, we incorporate constraints as side information into the tripartite graph clustering problem. Such side information is in the forms of must-links and cannot-links, which has been established and proven to be effective in semisupervised clustering [Basu et al., 2008]. Constraints have been applied to one-dimensional clustering [Basu et al., 2004; Lu and Leen, 2007] and co-clustering [Shi et al., 2010; Song et al., 2013; Chang et al., 2014] and tensor based clustering [Sutskever et al., 2009; Kang et al., 2012], but haven't been explored for tripartite graph clustering problem. More interestingly, we explore how to automatically generate the constraints instead of using the human annotated knowledge.

Constrained Relation Clustering

In this section, we present our problem formulation and solution to constrained relation clustering.

Problem Formulation

Each relation triplet is represented as (e1 , r, e2 ). Let the relation set be R = {r1, r2, . . . , rM}, where M is the size of R, and the entity set be E I = {eI1 , eI2 , . . . , eIVI }, where VI is the size of E I . E 1 ,w.r.t. I = 1, represents the left entity set where e1 ∈ E 1 . E 2 ,w.r.t. I = 2, represents the right entity set where e2 ∈ E 2 . We also denote three latent label sets Lr = {lr1 , lr2 , . . . , lrM }, and LeI = {leI1 , leI2 , . . . , leIV I } to indicate the clusters for relations and entities (two sets, I ∈ {1, 2}), respectively.

Fig. 1 shows an example of constrained relation clustering problem. The tripartite graph models the correlation among the left entity set E 1 , the relation set R, and the right entity set E 2 . In the figure, we illustrate four relation triplets: (Larry Page, is founder of, Google), (Bill Gates, is creator of, Microsoft), (Gone with Wind, is written by, Margaret Mitchell), and (The Kite Runner, is composed by, Khaled Hosseini). For (Larry Page, is founder of, Google), e11 = Larry Page, r1 = is founder of, and e21 = Google, the corresponding latent labels are le11 = Person ∈ Le1 , lr1 = Leadership of ∈ Lr, and le21 = Organization ∈ Le2 , respectively. Then we build a must-link between "is founder of" and "is creator of" if we know they should belong to the same cluster (Leadership of ), and build a cannot-link between "is founder of" and "is composed by" if we know they are different. Besides, we build a must-link for entities "Larry Page" and "Bill Gates" since the types are the same (Person), while we build a cannot-link for "Microsoft" and "Margaret Mitchell" since they have different types (Organization and Person). We prefer to impose soft constraints to the above relations and entities, since in practice, some constraints could be violated [Chang et al., 2012].

To formulate CTGC, we assume that the triplet joint probability can be decomposed as p(e1i , rm, e2j ) ∝ p(rm, e1i )p(rm, e2j ), where the joint probability of p(rm, eIi ) can be calculated based on the co-occurrence counts of rm and eIi . We follow Information-Theoretic Co-Clustering (ITCC) [Dhillon et al., 2003] and use

to approximate p(rm, eIi ) for the clustering problem. In Eq. (1) , ˆ rkr and ˆ eI keI are cluster indicators, kr and keI are cluster indices.

ITCC minimizes the Kullback-Leibler (KL) divergence DKL(p(R, E I )||q(R, E I )) to evaluate whether the coclustering produces a good result, where p(R, E I ) and q(R, E I ) are multinomial distributions composed by p(rm, eIi ) and q(rm, eIi ) respectively. Minimizing the KL divergence means the approximate function should be as similar as the original probabilities for co-occurrence between entities and relations. In our problem, we use a combination of two terms to evaluate our tripartite graph clustering:

Since the relation indictor ˆ rkr in q(rm, eIi ) will be optimized based on the combination of two terms, it will be affected by both left- and right-side entity clusters.

To incorporate the constraints, we design three sets of cost functions for Lr, Le1, and Le2. We take relation labels Lr as an example, and entity labels (Le1 and Le2) are similarly defined. For a label lrm , we denote the must-link set asMrm , and the cannot-link set as Crm . For must-links, the cost function is defined as

where p(E I |rm1 ) denotes a multinomial distribution based on the probabilities (p(eI1|rm1 ), . . . , p(eIVI |rm1 ))T , and Itrue = 1, Ifalse = 0. The above must-link cost function means that if the label of rm1 is not equal to the label of rm2 , then we should take into account the cost function of how dissimilar the two relations rm1 and rm2 are. The dissimilarity is computed based on the probability of entities E I given the relations rm1 and rm2 as Eq. (3). The more dissimilar the two relations are, the larger cost is imposed.

For cannot-links, the cost function is defined as

where Dmax is the maximum value for all the DKL(p(E I |rm1 )||p(E I |rm2 )). The cannot-link cost function means that if the label of rm1 is equal to the label of rm2 , then we should take into account the cost function of how similar they are. Moreover, am1,m2 and ¯am1,m2 are the tradeoff parameters.

Therefore, both must-links and cannot-links are soft constraints, which are related to the similarity between the relations themselves. If the constraints are violated, then additional costs are added to the final objective function.

Integrating all the constraints for Lr, Le1 and Le2 to Eq. (2), the objective function of CTGC is:

where Me1i1 and Ce1i1 are the must-link and cannot-link sets for entity e1i1 labeled with le1i1 . Similarly, the label of entity e2j1 also has must-link and cannot-link sets, which are denoted as Me2j1 and Ce2j1 , respectively.

Alternating Optimization

Since globally optimizing the latent labels as well as the approximating function q(rm, eIi ) is intractable, we perform an alternating optimization shown in Algorithm 1. For each set of labels, we first update the cluster labels based on the fixed

Algorithm 1 Alternating Optimization for CTGC.

Input: Tripartite graph defined on relations R, left entities E 1 and right entities E 2 ; Set maxIter and maxδ.

while t < maxIter and δ > maxδ do

• R Label Update: minimize Eq. (5) w.r.t. Lr.
• RModel Update: update parameters in Eqs. (7-9).
• E 1 Label Update: minimize Eq. (5) w.r.t. Le1 .
• E 1 Model Update: update parameters in Eqs. (7-9).
• R Label Update: minimize Eq. (5) w.r.t. Lr.
• RModel Update: update parameters in Eqs. (7-9).
• E 2 Label Update: minimize Eq. (5) w.r.t. Le2 .
• E 2 Model Update: update parameters in Eqs. (7-9).

Compute cost change δ using Eq. (5).

end while

model function q(rm, eIi ). Taking the optimizing Lr as an example, we use the iterated conditional mode (ICM) algorithm [Basu et al., 2004] to find the cluster labels. We update one label lrm at a time, and keep all the other labels fixed:

where the information of q(rm, eIi ) is incorporated into KL divergences DKL(p(E 1 |rm)||p(E 1 |ˆ rkr )) and DKL(p(E 2 |rm)||p(E 2 |ˆ rkr )). To understand why DKL (p(R, E 1 )||q(R, E 1 )) + DKL (p(R, E 2 )||q(R, E 2 )) can be re-written as DKL(p(E 1 |rm)||p(E 1 |ˆ rkr )) + DKL(p(E 2 |rm)||p(E 2 |ˆ rkr )), please refer to ITCC for more details [Dhillon et al., 2003].

Then, with the labels Lr and LeI fixed, we update the model function q(rm, eIi ). The update of q is not influenced by the must-links and cannot-links. Thus we can modify them the same as ITCC [Dhillon et al., 2003]:

Algorithm 1 summarizes the main steps in the procedure. The objective function (5) with our alternating update monotonically decreases to a local optimum. This is because the ICM algorithm decreases the non-negative objective function (5) to a local optimum given a fixed q function. Then the update of q is monotonically decreasing as guaranteed by the theorem proven in [Song et al., 2013].

The time complexity of Algorithm 1 is O((nnz + (nc ∗ iterICM)) · (Ke1 + Ke2 + Kr)) · iterAEM, where nnz is the total number of non-zero elements in the entity-relation co-occurrence matrix, nc is the constraint number, iterICM is the ICM iteration number in the E-Step, Ke1 , Ke2 and Kr are the cluster numbers, and iterAEM is the iteration number of the alternating optimization algorithm.

Experiments

In this section, we evaluate the proposed approach on two real world datasets.

Rel-KB and Constraints

Freebase is a publicly available knowledge base containing over 2 billions relation expressions between 40 millions entities. The Rel-KB dataset is constructed as follows: we select six popular one-hop relation categories in Freebase, i.e., Organization-Founder, Book-Author, Actor-Film, LocationContains, Music-Track, Person-Profession. Then, for each relation category, we randomly sample 5, 000 entity pairs. For each entity pair in the selected data, we enumerate all the l = L/2-hop relations for each entity, and combine them to generate the multi-hop relations within length-L (experimentally, L = 4). Finally, we have 16, 516 relation expressions with relation categories. 4

Then, we derive relation and entity constraints from the Rel-KB dataset. Based on Freebase, it is straightforward to design constraints for both relations and entities.

Relation constraints. (1) Must-links. If two relations are generated from the same relation category, we add a must-link. For example, (X, 's founder is, Z) ∧ (Z, is influence peer of, Y) and (X, 's founder is, Y) are generated from entity pair (Google, Larry Page) and (Microsoft, Bill Gates). Both entity pairs belong to Organization-Founder relation category. Thus a must-link can be added to the two relations. (2) Cannotlinks. If two relations are generated from entity pairs with different categories, we add a cannot-link to them.

Entity constraints. (1) Must-links. If two entities belong to the same entity category, we add a must-link. (2) Cannotlinks. If two entities belong to different entity categories, we add a cannot-link. For example, the entity categories of "Google" and "My Worlds" are Organization and Music respectively. In this case, we add a cannot-link to them.

Analysis of Clustering Results on Rel-KB

Here, we present the results on the Rel-KB dataset which has gold standard for cluster labels of relation expressions. This demonstrates the performance of our algorithm in the ideal situation, since our constraints are derived based on the gold standard provided by Freebase. We employ the widelyused normalized mutual information (NMI) [Strehl and Ghosh, 2003] as the measure. The NMI score is 1 if the clustering results match the category labels perfectly and 0 if the clusters are obtained from a random partition. In general, the larger the scores are, the better the clustering results are.

4 We assume all the relations generated with a certain entity pair being within the same category as the gold standard.

We call our algorithm Constrained Tripartite Graph Clustering (CTGC), and also denote the unconstrained version as TGC. In this experiment, we compare the performance of CTGC with that of several representative approaches such as (1) one-dimensional clustering algorithms Kmeans and constrained Kmeans (CKmeans) [Basu et al., 2004], (2) coclustering algorithms ITCC [Dhillon et al., 2003] and Constrained ITCC (CITCC) [Song et al., 2013], and (3) multirelational clustering algorithm which is Tensor Factorization based Clustering (TFBC) 5 [Sutskever et al., 2009]. In Kmeans, each relation expression is represented as an entity frequency vector. In co-clustering, the relation-entity co-occurrence (only the left entity is used) is used as the evidence of co-clustering. In three-dimensional tensor, an element in the tensor simply represents a triplet (e1 , r, e2 ) appearing in the data. In our algorithm, we treat the data as a tripartite graph, which condenses the tensor into two slices of matrices. Similar to co-clustering, each relation expression can be associated with multiple entities on both left and right sides. For relation constraints, we generate both must-links and cannot-links based on the method described before. In the following experiments, both the relation and entity cluster numbers are set to 6 (for both E 1 and E 2 ), the ground-truth number, respectively. Moreover, the trade-off parameters am1,m2 and ¯am1,m2 for constraints in Eqs. (3) and (4) are empirically set to 1/√M for relations and 1/√VI (I ∈ {1, 2}) for entities following [Song et al., 2013].

To compare the relation clustering results, we vary the number of relation and entity constraints by randomly selecting a fixed number of constraints from all possible must-links and cannot-links to investigate their impacts on clustering performance. Fig. 2 shows the experimental results. The x-axis in each sub-figure represents the number of relation constraints used in each experiment and the y-axis represents the averaged NMI value of five random trials.

As shown in Fig. 2(a), among all the methods we test, CTGC consistently performs the best. When there is no constraint, we can see that ITCC is better than Kmeans. The reason is that the co-clustering algorithm ITCC considers the information which also takes entity clusters into account. Moreover, TFBC is better than ITCC since it considers both left and right sides of entities clusters while ITCC only considers one side of entities. Furthermore, our TGC is better than TFBC. This is because we condense the tensor into two slices of matrices which represent the tripartite graph. Tensor may generate more wrong cluster assignments when the data is too sparse. The CITCC outperforms the TGC method because TGC does not use any constraints. In Fig. 2(b), we can see that CTGC significantly outperforms CITCC when we start adding more constraints to TGC. In addition, we can see that relation constraints can improve the clustering performance. In general, the more relation constraints we add, the better the clustering results are.

5 We use the standard Tensor Toolbox for Matlab: http://www. sandia.gov/∼tgkolda/TensorToolbox/.

Fig. 2(b) shows the effect of entity constraints along with the relation constraints. Besides the relation constraints which are the same as the ones in Fig. 2(a), we also add 3, 000 (i.e., 3K) and 6, 000 (i.e., 6K) entity constraints for CITCC and CTGC respectively. We can see that entity constraints are also very helpful for improving the relation clustering performance. The reason is that entity clustering information is transferred through the co-occurrence of entities and relations to the relation side. In general, with more entity constraints, the clustering results are better. Particularly, we see that when there is no relation constraint, we can even boost the NMI score from 0.69 to 0.85 with CTGC using only entity constraints. Therefore, it shows that even if we have little knowledge about relations, we can still expect better results if we know some knowledge about entities.

By looking into the clustering results, interestingly, in the Music-Track cluster, CTGC could find the four-hop relation: (X, made-1 , Person) ∧ (Person, same height, Person) ∧ (Person, perform in, Video) ∧ (Video, play in TV-1 , Y), which means the person who makes the music has the same height with the person who performs in the music video of the track. 6 It is semantically similar to the Music-Track cluster but we believe there should be very few (only one in our data) entities which could instantiate this relation. Therefore, it is very difficult to cluster this relation with the others. However, by introducing the constraints, we know the entities instantiating

6 We use entity types instead of entities in the intermediate relations of a multi-hop relation to be more easily understood.

(b) Examples generated by CTGC.

this relation are must-linked to other entities which have relation expressions in the Music-Track cluster. This relation is finally clustered in the Music-Track cluster.

Rel-OIE and Constraints

In practice, the relations, entities, and constraints derived from knowledge base are still limited. Therefore, we also develop another dataset called Rel-OIE in a more realistic scenario. We employ the open IE system, Reverb [Fader et al., 2011], to generate relation triplets fromWikipedia sentences containing at least one entity in Rel-KB. 7 We do this because Wikipedia text is cleaner compared to generic Web documents, and the sentences containing knowledge base entities may have higher possibility to have the relations of interests. In Rel-OIE, we have 137,674 unique relation expressions, 267,133 left entities, and 229,979 right entities.

Since in the open information extraction setting, we only have the sentences in free text format, we construct the constraints using the following methods.

Relation Must-links. If the similarity between two relation phrases is beyond a predefined threshold (experimentally, 0.5), we add a must-link to these relations. The similarity here is defined as the token-based Jaccard similarity between two phrases. For example, two phrases "'s founder is" and "'s founder is influence peer of" share three common tokens and thus they may both imply the same relation cluster. In this case, we add a must-link between these two phrases.

Entity Must-links. If two entities are of the same named entity type, we add a must-link to these entities. We use one of the state-of-the-art named entity recognizers [Ratinov and Roth, 2009], since it provides a larger number of types of named entities (18 types trained based on Ontonotes).

Case Study of Clustering Results on Rel-OIE

We herein present some examples from Rel-OIE dataset. We also cluster the relations into six clusters since we only extract the relations from sentences containing the entities in the RelKB dataset. In this case, it is easier for us to understand what happened after clustering.

7 We do not use Ollie [Schmitz et al., 2012] because Reverb is faster and with acceptable precision in our data.

We show the clustering results of TGC in Table 1(a) and the results of CTGC in Table 1(b). In general, the clustering results of TGC and CTGC both make sense. For example, in the Location-Contains cluster, CTGC as well as TGC find similar relations, e.g., (X, locate capital in, Y), (X, is a state of-1 , Y).

The clustering results of CTGC seem much better. For example, TGC does not cluster (X, locate capital in, Y) and (X, 's capital in, Y) together while CTGC does. By further checking the data, we found the reasons for the better results are: (1) there are relation must-links between (X, locate capital in, Y) and the other relation expressions such as (X, 's capital in, Y) in the cluster; (2) there are must-links between entities which can instantiate the expressions, e.g., a must-link between "America" and "China" (both are Geographical/Social/Political Entities (GPE)), and a must-link between "New York" and "Beijing" (both are GPE). This proves the importance of constraints for improving the clustering performance in the noisy scenario.

Conclusion

In this paper, we study the relation clustering problem. We model the relation clustering as a constrained tripartite graph clustering problem, and propose to use side information to help improve the clustering performance. We use two datasets to demonstrate the effectiveness of our approach, and show that this direction is promising.

Acknowledgments

Chenguang Wang gratefully acknowledges the support by the National Natural Science Foundation of China (NSFC Grant Number 61472006) and the National Basic Research Program (973 Program No. 2014CB340405). The research is also partially supported by the Army Research Laboratory (ARL) under agreement W911NF-09-2-0053, and by DARPA

under agreement number FA8750-13-2- 0008. The views and conclusions are those of the authors and do not necessarily reflect the view of the agencies.