Mining for Analogous Tuples from an Entity-Relation Graph

Introduction

Analogies arise when there are one or more similar semantic relations that are shared between two different knowledge bases. Studies on cognitive science have shown that the ability to detect analogies materializes in humans at an early stage [Kotovsky and Gentner, 1996]. Although exact repetitions of past experiences are rare, we tend to compare firsttime events we encounter with our past experiences and efficiently find analogous solutions [Gentner and Gentner, 1983]. Detecting analogies has been an important research topic in Artificial Intelligence for many years. Given two knowledge bases, Structure Mapping Theory [Gentner, 1983] states that analogies arise when we can find a mapping between the semantic relations that exist among the entities in one knowledge base (source) and the other (target). For example, consider the solar system and the classical atomic system. In the solar system, the relation X revolves around Y exists between the earth and the sun, whereas in the atomic system the same relation exists between an electron and the nucleus. Although the attributes such as the mass and the size of the entities involved in the relation X revolves around Y are very different in the two systems compared, we can identify the same semantic relation in the two systems. Consequently, the solar system and the classical atomic system can be considered as analogous. However, structure mapping is an NP-hard problem [Veale and Keane, 2003] for which several sub-optimal heuristic algorithms have been proposed such as the structure mapping engine [Falkenhainer et al., 1989].

The ability to detect analogies has been used as a measure of human intelligence. For example, verbal analogies have been used for evaluating candidates applying for universities in examinations such as the Scholastic Aptitude Test (SAT) and the Graduate Record Examination (GRE) [Turney et al., 2003]. For example, given the word pair (ostrich,bird) as the question, examinees must identify the word pair that is analogous to the question frommultiple choices. In this example, (lion,cat) is a correct answer because the semantic relation X is a large Y exists between ostrich and bird, as well as between lion and cat. The two word pairs in this example form a proportional analogy.

Detecting verbal analogies is a challenging task even for humans. For example, the average score (i.e. percentage of correct answers to the total number of questions) obtained by high school students on the verbal analogy questions in SAT is as low as 57% [Turney, 2005]. Despite those challenges, the ability to detect analogies has resulted in novel applications such as the latent relational search engine [Duc et al., 2011], an information retrieval system based on verbal analogies. For example, given a query such as (Apple, iPad), (Microsoft, ?), the relational search engine first identifies the relationship between the first two entities (i.e. Apple and iPad), and then finds an entity that has a similar relation with the third entity (i.e. Microsoft). In this example, the tablet device produced by Apple is the iPad, and the tablet device produced by Microsoft, which is Surface will be the correct answer. Here, the relationship X produces tablet device Y exists between the first two entities. In social networks, identification of analogous communities might lead to more accurate friend recommendations in future.

Despite those successful applications, there are several fundamental limitations in the existing approaches proposed for detecting verbal analogies. They consider only analogies involving two pairs of words. However, in real-world we observe analogies that involve more than two entities. For example, consider the two tuples (Steve Jobs, Apple, Tim Cook) and (Bill Gates, Microsoft, Steve Balmer). Here, in each tuple between the first and second entities, second and the third entities, and first and the third entities we have respectively founderOf relation, ceoOf relation, and successorOf relation. Therefore, the triangular relational structure that exists in one tuple can be directly mapped to the other, indicating a strong analogy between the two tuples. However, if we take a pairwise approach, then we loose the rich analogical structure that exists among the three entities in each tuple. For example, given three entities X, Y , and Z and we are told that X is the CEO of company Y , and Y acquired Z, then the likelihood of X also being the CEO of Z is high. However, if we consider individual pairwise combinations of the three entities, then we loose this vital piece of information.

Prior work on relational similarity assume the word pairs between which we must compute relational similarity to be given. However, in our setting, we are given a large set of entities represented by an entity-relation graph from which we must find analogical entity tuples. Although theoretically we can first generate all possible tuples between a given set of entities, and then search for the most relationally similar ones to discover verbal analogies, this approach does not scale-up for large sets of entities. For example, the number of possible pairs between n items grows in the order of O(n2 ), whereas the problem is further aggravated when we consider tuples that contain three or more entities.

We propose a method that overcomes the above-mentioned limitations and can discover a large number of analogical tuples from an entity-relation graph. Our contributions can be summarized as follows:

• ÷ First, given an entity-relation graph, in which vertices correspond to entities and edges correspond to lexicalsyntactic patterns that represent numerous semantic relations between entities, we propose a set of efficient heuristics to identify potential analogous tuples.
• ÷ Second, we propose numerous kernel functions to measure the degree of analogy between two tuples. For this purpose, we present two types of kernel functions: Vertex-Feature Kernels and Edge-Feature Kernels. Moreover, we combine those two types of kernels to construct Composite Kernels.

We describe and evaluate the proposed method for tuples that consists of three entities. Although the proposed method can be directly extended to find analogical tuples consisting more than three entities, we leave this to future work. Experiments conducted using a large entity-relation graph that contains 749↪ 364 vertices and 3↪ 862↪ 331 edges, show that the proposed method significantly outperforms competitive baselines and Latent Relational Analysis (LRA) [Turney, 2006] - a state-of-the-art pairwise relational similarity measure extended to measure the degree of analogy between two tuples.

Related Work

The current state-of-the-art method for measuring the relational similarity between two pairs of words is the Latent Relational Analysis (LRA) [Turney, 2006]. Given a set of wordpairs, LRA first extracts n-grams of words from the contexts (sentences) in which two words co-occur. For example, given the two words ostrich and bird, lexical patterns such as X is a large Y and X is a Y are extracted. Next, a co-occurrence matrix is built in which the rows correspond to word-pairs and the columns correspond to lexical patterns. An element hij of H denotes the number of times the i-th word-pair (ai↪ bi) cooccurs with the j-th lexical pattern pj in a text corpus. Next, singular value decomposition (SVD) is performed on H to reduce the data sparseness, and the largest l left singular vectors are selected to build a matrix H0 with l columns. Finally, the relational similarity between word pairs (ai↪ bi) and (aj↪ bj) is measured by the cosine of the angle between the i-th and j-th row vectors in H0 . LRA reports an accuracy of 56▷1% on a benchmark dataset containing 374 SAT verbal analogy questions.

Veale [Veale, 2004] proposed a relational similarity measure based on the taxonomic similarity in the WordNet [Miller, 1995]. He evaluates the quality of a candidate analogy a:b::c:d by comparing the semantic relations that corresponds to the paths in the WordNet that connects a to b and c to d. This approach achieves an accuracy of 43% on SAT verbal analogies.

Bollegala et al. [Bollegala et al., 2009] proposed a supervised approach for learning a Mahalanobis distance metric between semantic relations. Similar to LRA, a word pair (a↪ b) is represented by a vector of lexical patterns that cooccur with a and b. Next, a sequential pattern clustering algorithm is used to cluster semantically similar lexical patterns. Because a single semantic relation can be expressed using multiple lexical-syntactic patterns, this clustering step groups semantically similar lexical patterns together, and reduces the data sparseness. Finally, an information-theoretic metric learning algorithm [Davis et al., 2007] is used to compute a Mahalanobis distance matrix over the clusters, reporting an accuracy of 51▷1% on the SAT verbal analogies.

Latent Relational Mapping Engine (LRME) [Turney, 2008] finds a bijective mapping between two lists of word pairs. To represent the semantic relations between two words, LRME extracts numerous lexical patterns in which those two words co-occur. Then LRA is used to measure the relational similarity between two pairs of words each taken from one of the lists. All possible pairwise combinations of word pairs are considered and the mapping that yields the highest average relational similarity is selected.

All of the above-mentioned prior work in relational similarity consider only the analogies that exist between two pairs of words, whereas the proposed method considers tuples that contain three words. Moreover, given an entityrelation graph, we extract all analogous tuple pairs, whereas the prior work on relational similarity assume that the two word pairs between which we must compute relational similarity are given.

Entity-Relation Graph

Much of the real-world knowledge that we have about named entities such as people, products, or organizations can be concisely expressed using the semantic relations that exist among those named entities. Consequently, we consider an entity-relation graph as the input for the proposed method for extracting analogous tuples of entities. In an entity-relation graph, each vertex corresponds to a unique entity, and the edge that connects two vertices represents the semantic relation that exists between the corresponding entities. Moreover, an edge can be both directional and/or weighted according to the strength of the semantic relation that is represented by that edge. Numerous entity-relation graphs that contain millions of entities have been created in prior work in information extraction such as YAGO [Suchanek et al., 2007], Freebase [Bollacker et al., 2008], WikiNet [Nastase et al., 2010], WikiTaxonomy [Ponzetto and Strube, 2007], DBpedia [Auer et al., 2007], and PATTY [Nakashole et al., 2012].

Although those work differ in the methods they use for disambiguating entities, extracting and representing relations, their outputs can be recognized as entity-relation graphs. In particular, the representations used to denote a semantic relation differs from one entity-relation graph to another. For example, one can use n-grams of words from the contexts in which two entities co-occur as lexical patterns to represent the semantic relation between those two entities [Hearst, 1992]. Lexical patterns can be generalized using part-of-speech tag sequences or extended using dependency relations [Snow et al., 2005]. Because a single semantic relation can be expressed in a text by multiple patterns, some approaches cluster the extracted patterns to group semantically similar patterns [Nakashole et al., 2012; Lin and Pantel, 2001]. Our method does not assume a particular relation representation method and can potentially extract analogous tuples from any of the entity-relation graphs created using the abovementioned prior work. Here onwards, we use the term pattern to collectively refer to any of the above-mentioned relation representation methods.

We formally define an entity-relation graph G = (V↪ P↪ w) as a labeled, weighted, and directional graph where V = ¶v1↪ v2↪ ▷ ▷ ▷ ↪ vn♦ is the set of vertices (corresponding to n unique entities), P = ¶p1↪ p2↪ ▷ ▷ ▷ ↪ pm♦ is the set of patterns, and the weight function w(v↪ u↪ p) indicates the strength of the pattern p that flows from vertex v to u (i.e. direction is v ! u). There have been numerous methods proposed for measuring the strength of a semantic relation represented by a pattern that co-occurs with two entities. For example, Turney [Turney, 2006] uses positive pointwise mutual information for this purpose in LRA. Because semantic relations are directional in general, w(v↪ u↪ p) 6= w(u↪ v↪ p). Moreover, we assume that the weight function w is non-negative.

Mining for Candidate Tuple Pairs

Given an entity-relation graph G, Algorithm 1 extracts a set of potential candidate pairs of analogous tuples. In the next Section, we propose numerous kernel functions to exactly compute the degree of analogy between two given tuples.

Algorithm 1 Candidate Tuple Pair Extraction.

Input: An entity-relation graph G = (V↪ P↪ w). Output: A set C of candidate pairs of tuples. 1: S ¶♦ 2: for vi 2 V do 3: for vj ↪ vk 2 N(vi) do 4: S S +¶(vi↪ vj↪ vk)♦ 5: end for 6: end for 7: C ¶♦ 8: for (vi↪ vj↪ vk) 2 S do 9: for p 2 g(vi↪ vj ) [ g(vj ↪ vk) [ g(vk↪ vi) do 10: for vi0 ↪ vj0 ↪ vk0 2 H(p) do 11: if (vi0 ↪ vj0 ↪ vk0 ) 2 S then 12: C C +¶(vi0 ↪ vj0 ↪ vk0)♦ 13: end if 14: end for 15: end for 16: end for 17: return C

In Lines 1-6 in Algorithm 1, for each vertext vi, we create tuples from vertices that are directly connected to vi. This step can be conducted efficiently by representing the graph as lists of neighbours N(v) for each vertex v as follows:

Next, in Lines 7-15, for each tuple (vi↪ vj↪ vk) generated in the previous step, we identify other tuples (vi0 ↪ vj 0 ↪ vk0) that share at least one pattern in common with (vi↪ vj↪ vk). We define g(v↪ u), the set of patterns that co-occur with either v or u, as follows:

Because patterns represent semantic relations we can safely filter-out tuple pairs that do not share any semantic relations in common, thus unlikely to be analogous. This filtering step reduces the number of tuples that we must compare in the subsequent processing. To speed up the computation, we build an inverted index H between patterns and entities such that H(p) returns the set of entities that co-occur with a pattern p and is defined as follows:

The time complexity of enumerating triangles is bounded by Pv2V d(v)2 , where d(v) is the degree of a vertex v. In power-law graphs, Pv2V d(v)2 is approximately equal to nd3-γ max [Boccaletti et al., 2006], where dmax is the maximum degree and γ is the power coefficient. Moreover, dmax is approximately equal to n1◁(γ-1) [Newman, 2003], for which the complexity n2◁(γ-1) follows and is linear in practice.

Tuple-Feature Kernels

To measure the degree of analogy between two tuples (A↪ B↪ C) and (X↪ Y↪ Z), we define several kernel functions. Let us denote the set of features representing the vertex A by T (A). Moreover, the weight associated with a feature x 2 T (A) is denoted by ✓(x↪ T (A)). For example, the category of an entity (e.g. musician, politician, software company etc.) can be a feature of the vertex represented by that entity. By assigning a weight to a feature representing an entity, we can represent the degree to which a certain entity belongs to a category. Moreover, let us denote the set of features that represent an edge, eAB, connecting the two vertices A and B by S(A↪B). For example, we can use the set of lexical patterns that co-occur with the two entities corresponding to vertices A and B as the features representing the edge eAB. Then, tuple kernel functions, k((A↪B↪C)↪ (X↪ Y↪Z)), between the two tuples (A↪ B↪ C) and (X↪ Y↪ Z) can be defined in several ways as will be discussed next.

Vertex-Feature Kernels

The simplest form of the tuple kernels use only the features assigned to the individual vertices of each tuple. We define a series of kernel functions based on the set of overlapping features between the disjunctions of the individual vertex feature sets as follows:

Here, to reduce the cluttering of the notation, we define the disjunction of the vertex feature sets corresponding to three vertices A, B, and C as, T ([ABC) = T (A)[T (B)[T (C).

Given, two fuzzy-sets = ¶( ↪ ✓( ↪ ))♦, and ⇤ = ¶(λ↪ ✓(λ↪ ⇤))♦, the Jaccard and Overlap coefficients between those fuzzy-sets can be computed as:

Where,

Note that it is possible to use other set overlap measures besides the above two to create kernel functions. However, some set overlap measures such as the Dice coefficient has a monotonous relationship with the Jaccard coefficient and are redundant. If there are no weights assigned to the attributes of entities in an entity-relation graph, then we can set all ✓ values to 1, in which case the above-mentioned kernel functions resort to crisp sets instead of fuzzy-sets.

Edge-Feature Kernels

We define a series of kernel functions based on the features assigned to the edges that exist between pairs of entities in a tuple. First, we define the composition S(A↪B↪C), of the three edge feature sets, S(A↪B), S(B↪C), and S(C↪A) as

Here, the operator ⊙ is defined for two fuzzy-sets and ⇤ to give ⊙⇤ as follows:

We consider addition (+), multiplication (x), minimum (min), and maximum (max) as the candidate operators for ⊙. We represent each edge-feature set as a fuzzy set in which the membership value of a pattern p 2 P that co-occurs between two entities A and B is given by,

For example, lexical patterns can be used as edge features to represent the semantic relation that exists between two entities. However, a single semantic relation can be represented using more than one lexical pattern. For example, the ACQUISITION relation that exists between two companies can be represented by X is acquired by Y as well as Y purchased X for NUM dollars, where NUM is some numerical value. On the other hand, not all lexical-syntactic patterns are equally representative of a semantic relation. In our previous example, the verb acquisition is more commonly used to describe an ACQUISITION relation between two companies than the verb purchase. Therefore, the lexical pattern, X is acquired by Y, is more representative of the ACQUISITION relation between two companies than the lexical pattern, Y purchased X for NUM dollars. Therefore, it is desirable to softly assign lexical patterns to edges as features. For example, we can set ✓(p↪ S(A↪ B)) to the number of co-occurrences of the two entities A and B with pattern p.

Once we have computed S(A↪B↪C) and S(X↪ Y↪Z) for two tuples (A↪B↪C) and (X↪ Y↪Z) using Eq. 3, we define two variants k⊙ J ((A↪ B↪ C)↪ (X↪ Y↪ Z)) and k⊙ O ((A↪B↪C)↪ (X↪ Y↪Z)) of edge-feature kernels with each ⊙ operator using the Jaccard (Eq. 1) and Overlap (Eq. 2) coefficients given respectively by Jaccard(S(A↪B↪C)↪ S(X↪ Y↪Z)) and Overlap(S(A↪ B↪ C)↪ S(X↪ Y↪ Z)).

Note that we have 8 edge-feature kernels in total with the four operator types (+↪⇥↪min↪max) for ⊙ and the two set overlap measures: Jacccard and Overlap coefficients.

Composite Kernels

When measuring the degree of analogy between two tuples, it is desirable to consider both vertex features as well as edge features. However, the above-described vertex-feature kernels and edge-feature kernels individually capture only one type of features. To incorporate both vertex-features and edgefeatures in the analogy measurement, we combine vertexfeature kernels and edge-feature kernels via kernel composition. Given a vertex-feature kernel kv and an edge-feature kernel ke, we define their composite kernel kc as the product of the two kernels as follows:

Note that the normalization requirement, k((A↪B↪C)↪ (A↪B↪C)) = 1, is satisfied by all vertexfeature kernels, edge-feature kernels as well as their composite kernels. We combine the two vertex-feature kernels with the eight edge-feature kernels to compute 16 composite kernels. Although there exist numerous other operators besides the product to construct composite kernels from two atomic kernel functions [Shawe-Taylor and Cristianni, 2004], we differ the task of conducting an exhaustive search in the composite kernel space to a future study.

Datasets

We used the PATTY dataset [Nakashole et al., 2012] to create an entity-relation graph. PATTY is a large resource of textual patterns that denote numerous binary relations between entities. In PATTY, the patterns are semantically typed based on categories and organized into a subsumption taxonomy. For example, the pattern [singer] sings [song], is typed using Wikipedia categories, singer and song.

We used the PATTY dataset created from the English edition of Wikipedia, which contains about 3▷8 million articles (as of June 21, 2011). To create an entity-relation graph from this dataset, first, we create a vertex from each unique entity that appear in the dataset. Next, we create a directional edge between two vertices, if there exists a pattern in PATTY that co-occurs with the two entities that correspond to the two vertices. We use the pattern confidence scores computed in PATTY as the weights for the edges. The entity-relation graph that we create from PATTY contains 749↪ 364 vertices, and 3↪ 862↪ 331 connections, corresponding to 350↪ 569 unique patterns. We use this entity-relation graph for the experiments described in this paper.

Algorithm 1 extracts 171↪ 607 candidate tuple pairs from this graph. Next, we use numerous kernels described in the previous sections to identify analogous pairs of tuples. On an Intel Xeon 2.9GHz 32 core 256GB RAM machine, it takes less than 10 seconds to process the entire entity-relation graph with a given kernel, which demonstrates the efficiency of our method.

Unlike for word-pair analogies, for which there exists the SAT word-analogy questions benchmark dataset, there is no gold standard benchmark for evaluating analogous tuples. Turney [Turney, 2008] proposed a dataset consisting 20 pairs of word lists, in which there exists a bijective relational mapping between each pair of lists. However, this dataset is not suitable for evaluating our task because we must evaluate whether two tuples are analogous instead of finding a bijective mapping between the tuples. Conversely, if two tuples are not analogous, then there might not exist a bijective relational mapping between those tuples.

Consequently, to evaluate the proposed method, we create a gold standard dataset of analogous tuples. First, we randomly select a source tuples from the set of extracted tuples by Algorithm 1. Next, for each source tuple, we list the candidate tuples that share at least two patterns with it. Three human annotators compared each seed tuple and its candidate list and marked the tuples that they considered to be analogous to the source tuple. In the case where the annotators were not familiar with the entities in a tuple, they are instructed to gather additional information from the Web to determine the semantic relations that exist, if any, between two entities. Finally, for each source tuple we randomly select a tuple that is marked as being analogous to the source tuple by at least two of the three annotators. The final dataset contains 30 pairs of analogous tuples.

Experiments and Results

We consider that it is appropriate to evaluate the proposed method in a retrieval task for two reasons. First, in our task, we must correctly identify the analogous tuples to a given tuple among a large number of non-analogous candidate tuples. This scenario resembles Web search, where we must identify a small number of relevant documents to a given user query among a vast number of irrelevant documents. Kernel functions that assign high similarity scores to tuples that are analogous are desirable. We enforce this condition by limiting the evaluation to the top ranked tuples by a kernel function. Second, precise measurement of recall is difficult in our task because it is labour intensive and costly to go through the entire set of tuples extracted from a large entity-relation graph to identify all pairs of analogous tuples.

For each source tuple in our gold standard, we measure the degree of analogy between it and the remainder of the tuples extracted by Algorithm 1 using a particular kernel function, and rank in the descending order of their similarity scores. We evaluate the top 10 ranked candidates using two popular evaluation measures used in the information retrieval community: Precision@10, and Mean Reciprocal Rank (MRR) [Manning et al., 2008]. Precision@10 is the ratio between the number of analogous tuples found among the top 10 ranked tuples retrieved for a source tuple. MRR is the reciprocal of the rank assigned to the most analogous tuple to a source tuple. Both of those measures are computed for each source tuple in the gold standard and then averaged. Unlike Precision@10, MRR is sensitive to the rank assigned to analogous tuples. Because in the gold standard we assign only a single analogous tuple for each source tuple, Precision@10 can be seen as a measure of accuracy indicating the percentage of source tuples for which we can find their analogous counterparts among the top 10 similar tuples.

In Table 1, we use symbols V, E, and C respectively to denote vertex-feature kernels, edge-feature kernels, and composite kernels. For edge-feature kernels, we indicate the operator ⊙ and the set overlap measure within brackets. For composite kernels, we show the two constituent kernels used for the composition. We extend LRA, a stateof-the-art method word-pair relational similarity measure, to measure the degree of analogy between two tuples as follows. Given two tuples (A↪B↪C) and (X↪ Y↪Z), using LRA we measure the relational similarity between all possible combinations of entity pairs between the two tuples: ((A↪B)↪ (X↪ Y )), ((B↪A)↪ (Y↪X)), ((B↪C)↪ (Y↪Z)), ((C↪B)↪ (Z↪ Y )), ((C↪A)↪ (Z↪X)), and ((A↪C)↪ (X↪Z)). We consider the average of those relational similarity scores as the degree of analogy between the two tuples. This baseline demonstrates the level of performance we would obtain if we use pairwise relational similarity measure for detecting analogical tuples.

From Table 1, we see that vertex-feature kernels when used alone, does not retrieve any analogous tuples. On the other hand, edge-feature kernels outperform vertex-feature kernels, except when used with ⇥ and min operators. Recall that vertex-feature kernels use attributes of entities, whereas edge-feature kernels use patterns that represent the relations that exist between entities. According to Structure Mapping Theory [Gentner, 1983], relations, not attributes, are important when finding a mapping between analogous knowledge bases. We believe our empirical results, the superior performance of edge-feature kernels over vertex-feature kernels, support the claim of Structure Mapping Theory. Among the four operators used in edge-feature kernels, max is the best, followed by +. Because ⇥ and min operators prefer the weaker features (i.e. patterns with smaller weights) over the stronger features inside a tuple, those operators fail to identify analogous tuples.

Interestingly, when we combine both types of kernels, the performance increases. The best performance is obtained by C: E(max, Jaccard), V:Jaccard, which combines the vertexfeature kernel with Jaccard coefficient as the set overlap measure, and the edge-feature kernel that uses the max operator with Jaccard coefficient as the set overlap measure. Moreover, this composite kernel significantly outperforms the LRA baseline (Binomial exact test with significance level of 0▷05).

To further study the improved performance by composite kernels, we randomly select 1000 tuples from our entityrelation graph and compute vertex and edge feature kernels between those tuples. Figure 1 shows those scores for the constituents of the best performing composite kernel (i.e. C: E(max, Jaccard), V:Jaccard). From Figure 1, we see that vertex-feature and edge-feature kernels measure very different aspects of tuples. For example, for numerous pairs of tuples for which vertex-feature kernel assigns perfect scores, we must resort to edge-feature kernels to discriminate the correct analogous tuple pairs. Moreover, the Pearson correlation coefficient between the two kernels is low at 0▷1356. Similar trends were observed between other combinations of vertex-feature and edge-feature kernels as well. Therefore, the combination of vertex-feature and edge-feature kernels can be considered as providing mutually exclusive information, which justifies our kernel composition approach.

Conclusion

Given an entity-relation graph as the input, we proposed a method to extract analogous pairs of tuples that contain three entities. First, we proposed an algorithm to efficiently generate candidate pairs of tuples. Second, we proposed two types of kernel functions based on vertex-features and edgefeatures to measure the degree of analogy between two tuples. Moreover, we derived composite kernels from vertex and edge feature kernels. Our experiments using a real-world entity-relation graph showed that the proposed kernel composition approach significantly outperforms the current stateof-the-art pairwise relational similarity measure, extended to cover tuples with three entities. Moreover, we show that edgefeatures play an important role when detecting analogous tuples. In future, we plan to extend the proposed method to handle tuples with n(> 3) entities, thereby identifying analogous subgraphs within an entity-relation graph.