2 Literature review

Vector space family of kernel methods (Shawe-Taylor and Cristianini Reference Shawe-Taylor and Cristianini2004), is still the most commonly used representation model in machine learning and information retrieval. The original vector space kernel neglects the semantic content. One of the most important issues is to improve the vector space representation to ensure that it is able to support the semantic content of the words (Baroni and Lenci Reference Baroni and Lenci2010). Kernel methods play an important role in incorporating a priori knowledge about both syntactic and semantic structure of terms (Bloehdorn and Moschitti Reference Bloehdorn and Moschitti2007; Mehdad, Moschitti and Zanzotto Reference Mehdad, Moschitti and Zanzotto2010). For the case of syntactic structure, tree kernels (Croce et al. Reference Croce, Moschitti and Basili2011) have been proposed as a framework for exploiting the parse trees of the input texts. For the case of lexical semantics, semantic kernels exploit background information from semantic networks such as WordNet (Basili, Cammisa and Moschitti Reference Basili, Cammisa and Moschitti2006).

The original vector space considers only the simplest case of linear transformations of the type $\ \tilde{\phi }\left(o\right)=\phi \left(o\right)K_m$, where K_m is any m × l matrix which maps each object from the original m-dimensional space into a new l-dimensional feature space. Different choices of the matrix K_m lead to different variants of vector space semantic kernels. Generalized vector space kernel (Shawe-Taylor and Cristianini Reference Shawe-Taylor and Cristianini2004) aims at capturing term-term correlations by looking at co-occurrence information. Two terms are considered semantically related if they co-occur in the same document. On the other hand, a document is represented by the embedding $\ \tilde{\phi }\left(o\right)=\phi \left(o\right)\acute{D}$, where D is the document-term matrix. This means that two documents can be seen similar even if they do not share any terms.

Latent semantic kernel, aka latent semantic analysis or LSA (Cristianini, Shawe-Taylor and Lodhi Reference Cristianini, Shawe-Taylor and Lodhi2002) provides a very effective representation of high dimensional data that is able to capture semantic information through the use of co-occurrence information. This approach leverages the singular value decomposition of the matrix $\ \acute{D}=U\Sigma \acute{V}$, where Σ is a diagonal matrix of the same dimensions as D. U and V are unitary matrices whose columns are the eigenvectors of $\ \acute{D}D$ and $\ D\acute{D}$ respectively. Latent semantic kernel represents each object in a new k-dimensional feature vector space $\ \tilde{\phi }\left(o\right)=\phi \left(o\right)U_k$, where U_k is the first k columns of the matrix U.

On the other hand, researches have been done to exploit knowledge repositories for concept-based document representation models (Jadidinejad and Mahmoudi Reference Jadidinejad and Mahmoudi2014). In particular, Wikipedia (Medelyan et al. Reference Medelyan, Milne, Legg and Witten2009) has been widely used. Gabrilovich et al. (Reference Gabrilovich and Markovitch2009) proposed a feature generation technique for text documents using Wikipedia, so-called Explicit Semantic Analysis (ESA). In contrast with generalized vector space, ESA leverages an external document space (Anderka and Stein Reference Anderka and Stein2009). In this approach, each word is represented as a vector in the high dimensional space defined by Wikipedia articles. Previous research (Liberman and Markovitch Reference Liberman and Markovitch2009) revealed that the main drawback of ESA is its flat representation where each Wikipedia concept is considered as an isolated feature.

Basili et al. (Reference Basili, Cammisa and Moschitti2006) proposed a semantic kernel to use the WordNet hierarchy in learning algorithms for document classification. Since the proposed classifier leverages more effective document similarities based on prior knowledge, it is applicable in situations when few training examples are available. Wang and Domeniconi (Reference Wang and Domeniconi2008) and Wang et al. (Reference Wang, Hu, Zeng and Chen2009) overcame the shortfalls of bag-of-words representation model by embedding background knowledge derived from Wikipedia into a semantic kernel, which is then used to enrich the representation of documents. They used a linear combination of three measures of article similarity in Wikipedia in order to extract the proximity matrix of articles. Finally, each document is represented as $\ \tilde{\phi }\left(o\right)=\phi \left(o\right)K_m$, where K_m is a semantic matrix which contains both corpus terms and Wikipedia articles.

Fodeh, Punch and Tan (Reference Fodeh, Punch and Tan2011) proposed the use of semantic features for incorporating semantic knowledge from an ontology (especially WordNet) into document clustering. They leveraged ontological semantic features to reduce the number of dimensions in the original feature space. Huang et al. (Reference Huang, Milne, Frank and Witten2012) proposed a supervised document similarity measure that leverages 17 lexical and semantic features (contains the traditional bag-of-words and the recent bag-of-concepts) to assess document similarity, and learn from human judgments how to combine them by using machine-learning techniques.

Bloehdorn et al. (Reference Bloehdorn, Basili, Cammisa and Moschitti2006) proposed semantic smoothing kernel based on super concept representation. The aim of their work is to embed the knowledge of the topological relations in their super concept expansion into the semantic networks in kernel functions. Semantic smoothing kernel can be defined as a kernel for two data items x, z is given by $\ k\left(x,\ z\right)=\ \acute{x}Qz$ where Q is a square symmetric matrix whose entries represent the semantic proximity between the dimensions of the input space.

3 Clique-based semantic kernel

One of the appeals of using clique-based semantic kernel for pattern analysis is that it can be defined on non-isolated semantic features, make it possible to extend the usefulness of the technique to many different types of applications. All that is required is some measures of similarity that capture the association between two semantic features. The proposed method uses cliques in the feature similarity graph to create more complex relations between objects.

Definition 1: The object-feature matrix (so-called data matrix in the literature (Shawe-Taylor and Cristianini Reference Shawe-Taylor and Cristianini2004)) is the matrix D _{n × m} where rows are indexed by the objects of the collection o = {o ₁, o ₂, . . ., o_n} and the columns correspond to semantic features f = {f ₁, f ₂, . . ., f_m}. This is a binary matrix which (i, j)th entry gives the existence of feature f_j in object o_i.

Using data matrix (D), an object can be represented as a vector in a high dimensional space in which each dimension is associated with one feature from the feature space (so-called vector space in the literature) (Shawe-Taylor and Cristianini Reference Shawe-Taylor and Cristianini2004). Equation 1 shows the mapping of a data object o to the corresponding feature space ϕ(o) using data matrix D:

(1) \begin{equation} \phi :o\longmapsto \phi \left(o\right)=\left({\mathcal {F}}\left(f_1,o\right),\dots ,\ {\mathcal {F}}\left(f_m,o\right)\right) , \ {\mathcal {F}}(f_j,\ o)=\left\lbrace \begin{array}{l l}1 & f_j\in o \\ 0 & otherwise \end{array} \right. \end{equation}

For example, in the different tasks of text mining, text documents are represented using words as features (so-called, bag-of-words). Therefore, the rows of matrix D correspond to documents in the collection and the columns correspond to words. Each word is represented using a high dimensional sparse feature vector. Therefore, previous researches (Kriegel et al. Reference Kriegel, Peer and Zimek2009; Assent Reference Assent2012) have noted the need for feature engineering using semantic kernels.

The main idea of kernel methods is to map the data objects into a more comparable feature space. The classical representation of objects provided by (1) ignores any semantic relation between features. One of the most important issues is to improve the representation to ensure that objects containing semantically related features are mapped to similar feature vectors. In order to address the challenge of neglecting semantic content of the features in vector space, a transformation of the type $\ \tilde{\phi }\left(o\right)=\phi \left(o\right)K_m$ is required, where K_m is a semantic matrix. $\ \tilde{\phi }\left(o\right)\$ is a less sparse vector with non-zero entries for all features that are semantically similar to those presented in the data object o. Using this transformation, the corresponding kernel representation takes the form of (2).

(2) \begin{equation} \tilde{k}\left(o_i,\ o_j\right)=\phi \left(o_i\right)K_m\acute{K_m}{\phi (\acute{o}_j)}=\tilde{\phi }(o_i)\tilde{\phi }(\acute{o}_j) \end{equation}

Different choices of the matrix K_m lead to different variants of vector space semantic kernels (Shawe-Taylor and Cristianini Reference Shawe-Taylor and Cristianini2004). As described in Section 2, building the matrix K_m maybe explicit such as Wikipedia Semantic Kernel (Wang and Domeniconi Reference Wang and Domeniconi2008) or implicit such as Latent Semantic Kernel (Cristianini et al. Reference Cristianini, Shawe-Taylor and Lodhi2002). There are a lot of applications in data mining and machine learning which have a prior knowledge about the relations between features. For the sake of simplicity, the relations between semantic features are modeled as an undirected graph, named feature similarity graph.

Definition 2: A feature similarity graph for a feature space f is an undirected graph G = (V, E), where vertices are the features in f, while a link between them represents a basic similarity between the corresponding features. Two semantically related features f_i and f_j are connected with an unweighted edge in G. For example, while representing text documents with words as features, WordNet (Finlayson Reference Finlayson2014) provides a feature similarity graph which defines different relations between words.

A clique in an undirected graph is a subset of its vertices (C⊆V) as if every two vertices in the subset are connected by an edge (a complete subgraph) (Mihalcea and Radev Reference Mihalcea and Radev2011). Every clique corresponds to an independent set in the complement graph. A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique. A maximal clique in the feature similarity graph represents a subset of highly related features which is not a part of a larger clique. The independence between cliques is reminiscent of the discrimination attribute between features in machine learning (Assent Reference Assent2012). The main idea of this paper is that these cliques can play an important role as features in comparing complex data objects (cliques as features). This means that two objects can be seen similar even if they do not share any features, but the features they contain are elements of common cliques. Accordingly, we can define a semantic matrix (K_m) which maps each concept to the corresponding cliques in the feature similarity graph.

Definition 3: A clique-based semantic kernel matrix (K) over a feature similarity graph G = (V, E) is a m × l matrix, where m is the number of semantic features and l is the number of maximal cliques in G. Each row of K maps a semantic feature to the corresponding maximal cliques in the feature similarity graph. This is a binary matrix where (i, j)th entry gives the existence of feature f_i in the vertex set of clique c_j.

The columns of this matrix correspond to maximal cliques (c ₁, c ₂, . . ., c_l) and the rows correspond to features (f ₁, f ₂, . . ., f_m). Each entry (K_ij ∈ {0, 1}) represents the existence of a feature (f_i) in a clique c_j as follows:

(3) \begin{equation} K{\rm =}\left[ \begin{array}{ccc}k_{{\rm 11}} & \cdots & k_{{\rm 1}l} \\ \vdots & \ddots & \vdots \\ k_{m{\rm 1}} & \cdots & k_{ml} \end{array} \right] \end{equation}

A general feature (f_i) is usually found in a lot of cliques and does not give enough weight to other meaningful features. It is possible to apply normalization filter to the original kernel matrix which is inspired by Inverse Document Frequency in classical information retrieval (Turney and Pantel Reference Turney and Pantel2010) as follows:

(4) \begin{equation} K_{i{\rm *}}{\rm =}K_{i{\rm *}}{\rm \times log}\left(\frac{l}{{\rm 1+}\left|c_j{\rm :}f_i\in c_j\right|}\right) \end{equation}

Where K _i* represents a row in the kernel matrix which corresponds to feature f_i. l is the total number of maximal cliques and |c_j:f_i ∈ c_j| is the number of cliques where the feature f_i appears. If a feature does not appear in any cliques, this will lead to a division-by-zero. Therefore, the denominator of (4) has been adjusted to 1 +|c_j:f_i ∈ c_j|.

We can now define a semantic kernel which leverages the semantic matrix K to map each data object to the corresponding relevant cliques in the feature similarity graph. A Clique-based Semantic Kernel represents a data object o by $\ \tilde{\phi }(o)\longmapsto \phi \left(o\right)K$, where K is a clique-based semantic matrix. The new representation model of clique-based semantic kernel $\ \tilde{\phi }(o)$ is less sparse than the original ϕ(o) that has non-zero entries for all semantic features that are semantically related to those present in ϕ(o). Equation 5 represents this process using matrix multiplication:

(5) \begin{equation} F_{nl}=D_{nm}{\rm \times }K_{ml} \end{equation}

Matrix F is the generated feature matrix based on both features and the corresponding cliques in the feature similarity graph. The columns of the feature matrix (F) correspond to maximal cliques (c ₁, c ₂, . . ., c_l) and the rows correspond to data objects (o ₁, o ₂, . . ., o_n). Each entry (f_ij) represents the relationship between clique c_j and object o_i. Finally, the new generated feature vector corresponding to object o_i is:

(6) \begin{equation} \overrightarrow{F_i}{\rm =}\left( f_{i{1}},\dots , f_{il} \right) \end{equation}

A common clique (c_j) appears in a lot of objects and does not give enough weight to other meaningful cliques. So the original feature matrix need a normalization like the kernel matrix in (4). We applied a normalization filter to the original feature matrix which is inspired by Inverse Document Frequency in classical information retrieval (Turney and Pantel Reference Turney and Pantel2010):

(7) \begin{equation} F_{{\rm *}j}{\rm =}F_{{\rm *}j}{\rm \times log}\left(\frac{n}{{\rm 1+}\left|o_i{\rm :}c_j\in {{\rm o}}_{{\rm i}}\right|}\right) \end{equation}

Where n is the total number of objects, F _*j corresponds to the jth maximal clique (c_j) and |o_i:c_j ∈ o_i| refers to the number of objects where the clique c_j appears. Finally, it’s common to use cosine similarity (Turney and Pantel Reference Turney and Pantel2010) to find the semantic relatedness of two objects o_i and o_j using the corresponding feature vectors $\ \overrightarrow{F_i}$ and $\ \overrightarrow{F_j}$:

(8) \begin{equation} sim\left(o_i,\ o_j\right)={\cos \left(\overrightarrow{F_i},\ \overrightarrow{F_j}\right)\ }=\frac{\overrightarrow{F_i}.\ \overrightarrow{F_j}}{\left|\ \overrightarrow{F_i}\right|\left|\ \overrightarrow{F_j}\right|}=\frac{\sum ^l_{k=1}{f_{ik}*f_{jk}}}{\sum ^l_{k=1}{f^2_{ik}}\ \sum ^l_{k=1}{f^2_{jk}}} \end{equation}

In the following section, the effectiveness of the proposed clique-based semantic kernel is evaluated in the application of semantic relatedness between texts and words (Zesch and Gurevych Reference Zesch and Gurevych2010; Zhang et al. Reference Zhang, Gentile and Ciravegna2013).

4 Using clique-based semantic kernel for computing text relatedness

The proposed clique-based semantic kernel is crucial in any application of machine learning which has a prior knowledge about the relatedness between features. On the other hand, emerging knowledge repositories in the field of natural language understanding, especially those that are based on collaborative knowledge repositories (Gurevych and Wolf Reference Gurevych and Wolf2010; Gurevych and Zesch Reference Gurevych and Zesch2013; Hovy, Navigli and Ponzetto Reference Hovy, Navigli and Ponzetto2013) such as Wikipedia (Medelyan et al. Reference Medelyan, Milne, Legg and Witten2009), DBpedia (Bizer et al. Reference Bizer, Lehmann, Kobilarov, Auer, Becker, Cyganiak and Hellmann2009) and BabelNet (Navigli and Ponzetto Reference Navigli and Ponzetto2012), provides a valuable prior knowledge about conceptual features (Jadidinejad and Mahmoudi Reference Jadidinejad and Mahmoudi2014). In this section, Wikipedia articles and the corresponding hyperlink graph are employed as a conceptual feature repository and it is also tried to validate the usefulness of the proposed clique-based semantic kernel in the field of computing relatedness between text documents.

Figure 1 shows the overall function of our experiments. At the first step, the corpus is mined to extract Wikipedia entities. This process is known as entity linking (Hachey et al. Reference Hachey, Radford, Nothman, Honnibal and Curran2013) in general, or Wikification (Csomai and Mihalcea Reference Csomai and Mihalcea2008) when the target knowledge base is Wikipedia. Entity extraction module provides a data matrix (D) which represents the existence of a specific concept in different documents (bag-of-concepts). After that, it is necessary to leverage the hyperlink structure in Wikipedia to mine the similarity between conceptual features. The output is a structured feature space which is defined as feature similarity graph in Section 3. Clique extraction module derives all the maximal cliques from the feature similarity graph. Each clique corresponds to a coherent subset of related conceptual features. These cliques shape the kernel matrix (K) which relates each clique to its ingredients. Finally, the new feature matrix (F) can be computed by multiplying the data matrix (D) with the kernel matrix (K).

Fig. 1.

The overall flow of the proposed clique-based semantic kernel in the task of text relatedness.

We leverage a collection of 50 text documents from the Australian Broadcasting Corporation’s news mail service (Lee, Pincombe and Welsh 2005). This corpus is well analyzed in the application of semantic relatedness (Zhang et al. Reference Zhang, Gentile and Ciravegna2013) using different document representation models (Gabrilovich and Markovitch Reference Gabrilovich and Markovitch2009; Tsatsaronis, Varlamis and Vazirgiannis Reference Tsatsaronis, Varlamis and Vazirgiannis2010; Taieb, Aouicha and Hamadou Reference Taieb, Aouicha and Hamadou2013; Yazdani and Popescu-Belis Reference Yazdani and Popescu-Belis2013). On the other hand, the limited number of text documents allows us to easily analyze different clique-based approaches in a moderate hardware configuration. Following the literature on text semantic relatedness, these documents are paired in all possible ways and compared to the average human judgments using Pearson’s product-moment correlation coefficient. 2D visualization of this data set is presented in Figure 2. Each point in the figure corresponds to a document. The position of each document represents the relative distance from others. Obviously, this data set contains four conceptual clusters.

Fig. 2.

Visualization of 50 documents of Lee data set in a 2-dimensional space using multidimensional scaling.

Entity linking (Hachey et al. Reference Hachey, Radford, Nothman, Honnibal and Curran2013) is the first step in conceptual natural language processing. Building a precise entity linking module is a hot research topic which is out of the scope of this paper. Fortunately, previous researches (Mihalcea and Csomai Reference Mihalcea and Csomai2007; Hachey et al. Reference Hachey, Radford, Nothman, Honnibal and Curran2013; Milne and Witten Reference Milne and Witten2013) in the field of Wikification are useful in this phase. Wikification is a process in which words of a textual document link to the corresponding Wikipedia Web page (Csomai and Mihalcea Reference Csomai and Mihalcea2008). We used Wikifier (Milne and Witten Reference Milne and Witten2013) to map a text fragment to the corresponding concepts in Wikipedia (s ₁, s ₂, . . ., s_m). Totally, m = 496 unique concept has been detected between 50 documents of Lee data set (Lee et al. Reference Lee, Pincombe and Welsh2005). For example, consider again two example documents from Lee data set (Lee et al. Reference Lee, Pincombe and Welsh2005) in Table 1. The most important extracted Wikipedia concepts are shown in bold. According to the provided human judgments, these documents are highly related to each other. Unfortunately, there is no exact match between the extracted concepts.

In order to build the feature similarity graph, a basic similarity measure between articles in Wikipedia is required. Despite different knowledge based and corpus based measures which have been proposed in the literature (Zesch and Gurevych Reference Zesch and Gurevych2010; Zhang et al. Reference Zhang, Gentile and Ciravegna2013), the following heuristic rules were leveraged to induce a basic similarity measure to build the feature similarity graph:

1. (1) If there is a bidirectional hyperlink between two articles u and v, these articles will be adjacent in the corresponding feature similarity graph.

2. (2) Each article in Wikipedia has at least one parent category (Medelyan et al. Reference Medelyan, Milne, Legg and Witten2009). If two articles u and v have at least one common parent category (sibling articles), these articles will be adjacent in the corresponding feature similarity graph.

Using the above wiring rules, 2, 671 edges have been shaped between m = 496 unique concepts. Totally, l = 623 maximal cliques have been discovered in the feature similarity graph. The size of the discovered cliques is varying from 2 to 32 vertices. The number of occurrences of each maximal clique is illustrated in Figure 3. This figure reveals that maximal cliques in the graph follow Power-law distribution with long tail (Steyvers and Tenenbaum Reference Steyvers and Tenenbaum2005). This means that the number of cliques with very large size is very low and a large number of cliques have small size. A large clique contains a lot of general concepts related to each other according to the structure of the background knowledge base. For example, a very large clique in our experiments on Wikipedia contains different countries. These cliques are triggered by the existence of each general concept (vertices) in the document. To solve the importance of these large cliques, a weighting formula was presented in (4) and (7).

Fig. 3.

The number of occurrences of each maximal clique in the feature similarity graph according to cliques size.

After extracting different cliques from the features similarity graph, the clique-based semantic matrix (K) can be shaped. The columns of this matrix correspond to maximal cliques (c ₁, c ₂, . . ., c_l) and the rows correspond to Wikipedia concepts (s ₁, s ₂, . . ., s_m). Each entry (K_ij ∈ {0, 1}) represents the existence of a concept in a clique. With the existence of the kernel matrix, it is possible to map documents into the new clique-based feature space using (5). Finally, the relatedness between two documents in the new clique-based feature space are computed using cosine similarity (8). Table 2 shows the Pearson’s correlation between the proposed algorithm and human judgment scores in comparison to baselines and the state-of-the-art document representation models (Dumais Reference Dumais2004; Gabrilovich and Markovitch Reference Gabrilovich and Markovitch2009). We leveraged LSA (Dumais Reference Dumais2004) and ESA (Gabrilovich and Markovitch Reference Gabrilovich and Markovitch2009) as well-known representatives of latent and explicit representation models respectively. In the bag-of-words representation model (‘BOW’), words appeared in the input document are leveraged as features. On the other hand, in the bag-of-concepts representation model (‘BOC’), each document is represented with its concepts (Wikipedia’s concepts (Jadidinejad and Mahmoudi Reference Jadidinejad and Mahmoudi2014) in our experiments). All versions of the proposed feature generation model are significantly better than the baseline bag-of-words and bag-of-concepts. The kernel matrix (K) and the generated feature matrix (F) are normalized according to (4) and (7) respectively. Normalized version of both kernel and feature matrices significantly improves the effectiveness of the original proposed method and yields the best correlation coefficient to the human scores.

Table 2.

Pearson’s correlation of text relatedness scores with human judgements on Lee data set. Correlation is significant at the 0.01 level (2-tailed). Different versions of Clique-based Semantic Kernel (CSK) have been presented

In order to determine whether the proposed clique-based semantic kernel is statistically significantly superior to baselines, we used G. Zou statistical hypothesis testing (Zou Reference Zou2007) which represents a testing method for both dependent and independent variables. The advantage of this method is the acknowledgment of the asymmetry of sample distributions for single correlations and it only requires confidence intervals (Singer et al. Reference Singer, Niebler, Strohmaier and Hotho2013). We used 0.05 and 0.95 for alpha and confidence level respectively. Statistical significance test (Zou Reference Zou2007) were calculated between the dependent Pearson correlations coefficients produced by the proposed semantic kernel and baselines (‘BOW’ and ‘BOC’) . One-tailed hypothesis test was used for assessing the difference between two paired correlations. When comparing the proposed semantic kernel with the baselines and LSA (Lee et al. Reference Lee, Pincombe and Welsh2005), null hypothesis is rejected. It means that the proposed method is not only statistically significantly better than the baseline, but also better than LSA. On the other hand, null hypothesis is retained when comparing the proposed semantic kernel with ESA (Gabrilovich and Markovitch Reference Gabrilovich and Markovitch2009), therefore the proposed clique-based semantic kernel performs as well as ESA.

Figure 4 shows the correlation between the proposed algorithm and human judgment scores compared with different document representation models presented in Table 2. As shown in Figure 4(a), the baseline bag-of-concept’s representation model leads to a lot of vocabulary mismatches between core conceptual features. There are a lot of cases in Figure 4(a), where the human judgment score is high while the baseline algorithm score is zero. For example, two documents presented in Table 1 are highly related according to the provided human judgments (r = 4.33/5) but there is no common concept between them. So, the nominator of (8) equals to zero and the bag-of-concept’s representation model can’t detect the relatedness between them (r = 0.0).

Fig. 4.

Comparison of correlation between the algorithm and human scores for different document representation models: (a) bag-of-concepts, (b) clique-based semantic kernel without normalization and (c) clique-based semantic kernel with normalization of both K and F matrices. Each point corresponds to a pair of documents in Lee data set. Horizontal and vertical axis represents the amount of semantic relatedness determined by humans and algorithms respectively. Circled regions in Figures (a) and (b) represent the noisiest decisions in each approach. It is clear that calculated semantic relatedness values in Figure (c) are highly correlated to human decisions.

On the other hand, the proposed clique-based representation model (Figure 4(b) leverages cliques-of-concepts instead of isolated bag-of-concepts. This method allows semantically related documents to be matched. For example, consider again two documents presented in Table 1, using the proposed clique-based features, these two documents have 24 features (cliques) in common and the overall similarity between them is r = 0.093. Some common clique-based features between them are as follows:

• • Natural environment: Forest

• • Earth:Natural environment: Earth Summit: Environmentalism

• • Environmentalism: Sustainability: Earth Summit: Sustainable development

• • Environmentalism: Sustainability: Earth Summit: Natural environment

Figure 4(b) reveals that there are some cases which have delusive high scores. Strict analysis of the results have shown that general concepts have high degree of feature similarity graph and naturally appear in a lot of cliques. On the other hand, common cliques appear in a lot of documents and do not give enough weight to other meaningful cliques. This problem is reminiscent of the challenge of general terms in classical information retrieval (Turney and Pantel Reference Turney and Pantel2010). Furthermore, (4) and (7) proposed an inverse frequency normalization technique for the kernel matrix (K) and the feature matrix (F) respectively. The effect of the normalization on both kernel and feature matrices is shown in Figure 4(c). As it is clearly illustrated, smoothing general concepts and cliques significantly improves the correlation coefficient (r = 0.72 in Table 2).

5 Using clique-based semantic kernel for computing concept similarity

In order to show the applicability of the proposed clique-based semantic kernel in different knowledge bases and applications, in this section WordNet (Finlayson Reference Finlayson2014) is leveraged in the task of concept similarity. Unlike Wikipedia, WordNet is an expert-built lexical database. It groups English words into sets of synonyms called‘synsets’ and records the various semantic relations between these synonym sets. In the following experiments, The MIT Java WordNet Interface (JWI) (Finlayson Reference Finlayson2014) has been used to access WordNet programmatically.

Computing semantic similarity in a network of words or concepts plays an important role in different applications of information retrieval and natural language processing (Harispe et al. Reference Harispe, Ranwez, Janaqi and Montmain2013). Assuming similarity as a specific type of relatedness, the goal of concept similarity is to measure the amount of similarity between two concepts using the defined relations in the knowledge base (Schwartz and Gomez Reference Schwartz and Gomez2011).

We leverage a collection of 97 WordNet concept pairs which is a benchmark data set in the task of concept similarity (Schwartz and Gomez Reference Schwartz and Gomez2011), so-called ‘ConceptSim’ in the following experiments. Schwartz and Gomez (Reference Schwartz and Gomez2011) created this data set by mapping each word from Agirre et al. word similarity data set (Agirre et al. Reference Agirre, Alfonseca, Hall, Kravalova, Paşca and Soroa2009) into WordNet. For example, the corresponding concept pair for the word pair (‘tiger’, ‘jaguar’) in Agirre et al. word similarity data set (Agirre et al. Reference Agirre, Alfonseca, Hall, Kravalova, Paşca and Soroa2009) is (‘tiger#n#2’, ‘jaguar#n#1’) in ConceptSim data set (Schwartz and Gomez Reference Schwartz and Gomez2011). The correlation between each algorithmic measure and the gold standard is evaluated using Spearman’s rank correlation.

ConceptSim contains 152 unique concepts (synsets of WordNet). A subgraph G was built from WordNet which contains 2,796 vertices and 3,087 edges by starting from 152 unique concepts and add all neighbors which are reached by all types of semantic relations. This feature similarity graph contains 2,812 maximal cliques.

Now, we can define a data matrix D _{n × m} where rows are indexed by the unique concepts of ConceptSim (n = 152) and the columns correspond to conceptual features (m = 2, 796) in the feature similarity graph (G). For example, ‘jaguar#n#1’ connects to ‘big_cat#n#1’ and ‘Panthera#n#1’ in the feature similarity graph (G). So, the row corresponding to ‘jaguar#n#1’ has two ones among 2,796 entries. Using this matrix, each concept is represented using its neighbors in a high dimensional feature space in which each dimension is associated with a WordNet conceptual feature. The similarity between two concepts c_i and c_j is calculated using cosine measure, so-called ‘R_overlap’ in the following experiments:

(9) \begin{equation} sim\left(c_i,\ c_j\right)={\cos \left(\overrightarrow{D_{i*}},\ \overrightarrow{D_{j*}}\right)\ } \end{equation}

After that, we can define a clique-based semantic matrix (K_m×l) over the feature similarity graph, where m = 2, 796 is the number of semantic features and l = 2, 812 is the number of maximal cliques. Each row of K represents a semantic feature with the corresponding maximal cliques in the feature similarity graph (G). This matrix is normalized according to (4).

As described in Section 3, a new clique-based representation can be defined as: F = D × K, where K is a clique-based semantic matrix and D is the original data matrix. This matrix is normalized according to (7). The columns of the feature matrix (F) correspond to maximal cliques and the rows correspond to WordNet concepts.

The new clique-based representation (F) is less sparse than the original representation (D) that has non-zero entries for all related semantic features. The similarity between two concepts c_i and c_j in the new representation is calculated using cosine measure, named ‘CSK’ in the following experiments:

(10) \begin{equation} sim\left(c_i,\ c_j\right)={\cos \left(\overrightarrow{F_{i*}},\ \overrightarrow{F_{j*}}\right)\ } \end{equation}

Table 3 shows the effectiveness of the proposed clique-based semantic kernel in comparison to the state-of-the-art path based, gloss based and information content based techniques in the field of concept similarity (Budanitsky and Hirst Reference Budanitsky and Hirst2006). Experimental results have revealed that the proposed semantic kernel is not only significantly better than baselines, but also comparable with the state-of-the-art results (Patwardhan and Pedersen Reference Patwardhan and Pedersen2006; Yang and Powers Reference Yang and Powers2006; Resnik Reference Resnik1999).

Table 3.

Spearman’s correlation of concept similarity scores with human judgements on ConceptSim data set. Correlation is significant at the 0.01 level (2-tailed)