DWRank: Learning concept ranking for ontology search

2.1.1. Intra-ontology relationships

An intra-ontology relationship I a = ( ( v , v ′ ) , O ) is a directed edge ( v , v ′ ) , where ( v , v ′ ) ∈ E ( O ) for v ∈ V ( O ) and v ′ ∈ V ( O ) .

2.1.2. Inter-ontology relationships

An inter-ontology relationship I e = ( ( v , v ′ ) , O , O ′ ) is a directed edge ( O , O ′ ) , where ( v , v ′ ) ∈ E ( O ) , L ( v ) = L ( O ) , L ( v ′ ) = L ( O ′ ) and L ( v , v ′ ) = owl : imports .2

Forward link concepts C FLinks ( v , O ) is a set of concepts V ′ in an ontology O, where V ′ ⊂ V ( O ) and ∀ v i ∈ V ′ , ∃ ( v , v i ) ∈ E ( O ) .

2.1.4. Back link concepts

Back link concepts C BLinks ( v , O ) is a set of concepts V ″ in an ontology O, where V ″ ⊂ V ( O ) and ∀ v j ∈ V ″ , ∃ ( v j , v ) ∈ E ( O ) .

2.2.1. Offline learning and index construction

The framework first constructs a ConHubIdx on all concepts and an OntAuthIdx on all ontologies in the ontology corpus O. The ConHubIdx maps each concept of an ontology to its corresponding hub score. Similarly, the OntAuthIdx maps each ontology to its precomputed authority score. Finally, the ranking model for the hub and authority scores are learned using the learning to rank algorithm. The hub score, authority score and learning to rank algorithms are defined in Section 3.1

2.2.2. Online query processing

Upon receiving a query Q, the framework extracts the candidate result set C Q = { ( v 1 , O 1 ) , … , ( v i , O j ) } including all matches that are semantically similar to Q by querying the ontology repository. The hub score and authority score for all ( v , O ) ∈ C Q are extracted from the corresponding indices as lists H ( C Q ) and A ( C Q ) . A ranked list R ( C Q ) of the candidate result set is generated from H ( C Q ) and A ( C Q ) along with the text relevancy measure by applying the ranking model leant during the offline learning and index construction phase.

The hub score is a measure of the centrality of a concept within an ontology. We define a hub functionh(v,O) that calculates the hub score. The hub function is characterised by two features:

Connectivity: A concept is more central to an ontology, if there are more intra-ontology relationships starting from the concept.

According to these features, a concept accepts the centrality of another concept based on its forward link concepts (like a hub). The hub function is therefore a complete reverse of the PageRank algorithm [21] where a node accepts scores from its referent nodes i.e. back link concepts.

We adopt a Reverse-PageRank [13] as the hub function to find the centrality of a concept within the ontology. The hub function is an iterative function and at any iteration k, the hub function is defined as Eq. (1). h k ( v , O ) = (1) ∑ v i ∈ C FLinks ( v , O ) h k − 1 ( v i , O ) | C BLinks ( v i , O ) |

Within the original PageRank framework there are two types of links in a graph, strong and weak links. The links that actually exist in the graph are strong links. Weak links are artificially created links by a damping factor α, and they connect all nodes to all other nodes. Since data-type relationships of a concept do not connect it to other concepts in an ontology, most PageRank-like algorithms adopted for ontology ranking consider only object-type relationships of a concept while ignoring others. We adopt the notion of weak links and introduce ‘weak nodes’ in our hub function to be able to also consider data-type relationships along with object-type relationships for the ontology ranking. We generate a set of artificial concepts V ′ ( O ) in the ontology that act as a sink for every data-type relationship and label these concepts with the data-type relationship label, i.e. ∀ v j ∈ V ′ , L ( v j ′ ) = L ( v i , v j ′ ) . After incorporating weak links and weak nodes, Eq. (2) reflects the complete feature of our hub function. (2) h k ( v , O ) = 1 − α | V | + α ∗ ∑ v i ∈ C SFLinks ( v , O ) ∪ C WFLinks ( v , O ) h k − 1 ( v i , O ) | C BLinks ( v i , O ) |

In Eq. (2), C SFLinks ( v , O ) is a set of strong forward link concepts and C WFLinks ( v , O ) is a set of weak forward link concepts. Our hub function is similar to [29], but varies from it as we consider weak nodes and we are not considering relationships weights. The results presented in [29] also justify our choice of ReversePageRank over other algorithms to measure the centrality. We normalise the hub scores of each concept v within an ontology O through the z-score of the concept’s hub score after the last iteration of the hub function as follows: (3) h n ( v , O ) = h ( v , O ) − μ h ( O ) σ h ( O )

In Eq. (3), h n ( v , O ) is a normalised hub score of v, μ h ( O ) is an average of hub scores of all concepts in the ontology and σ h ( O ) is the standard deviation of hub scores of the concepts in the ontology.

3.1.2. AuthorityScore: The authoritativeness of a concept

The authority score is the measure of the authoritativeness of a concept within an ontology. As mentioned earlier, the authoritativeness of a concept depends upon the authoritativeness of the ontology within which it is defined. Therefore, we define the authority function a(O) to measure the authority score of an ontology. Our authority function is characterised by the following two features:

Based on these two features, an inter-ontology relationship I e ( ( v , v ′ ) , O , O ′ ) is considered as a “positive vote” for the authoritativeness of ontology O ′ from O. PageRank is adopted as the authority function, whereby each ontology is considered a node and inter-ontology relationships are considered links among nodes. Eq. (4) formalises the authority function which computes the authoritativeness of O at the kth iteration. a k ( O ) = 1 − α | O | (4) + α ∑ O i ∈ O BLinks ( O ) a k − 1 ( O i ) | O FLinks ( O i ) |

In Eq. (4), O BLinks ( O ) is a set of back link ontologies and O FLinks ( O ) is a set of forward link ontologies. The definition of O FLinks ( O ) (resp. O BLinks ( O ) ) is similar to C FLinks ( v , O ) (resp. C BLinks ( v , O ) ), however, the links are inter-ontology relationships.

Similar to the hub score, we also compute the z-score of each ontology after the last iteration of the authority function as follows: (5) a n ( O ) = a ( O ) − μ a ( O ) σ a ( O )

In Eq. (5), a n ( O ) is the normalised authority score of v, μ a ( O ) is an average of the authority scores of all ontologies in the corpus and σ a ( O ) is the standard deviation of the authority scores of ontologies in O.

3.1.3. DWRank score

Finally, we define the DWRank R ( v , O ) , as a function of the text relevancy, the normalised hub score and the normalised authority score features.

We initially described a linear ranking model with fixed weights in [4] as a quantitative metric for the overall relevance between the query Q and the concept v; and the concept hub and authority score as follows: R ( v , O ) = γ F V ( v , Q ) ∗ [ α h ( v , O ) + β a ( O ) ] (6) F V ( v , Q ) = ∑ q ∈ Q f s s ( q , ϕ ( q v ) )

In Eq. (6), α, β and γ are the weights for the hub function, the authority function and text relevancy of the concept to the query respectively. The text relevancy function F V ( v , Q ) , aggregates the contribution of all fully or partially matched words of a node v, in an ontology O, to the query keywords q ∈ Q . f s s returns a binary value : it returns 1 if q has a match ϕ ( q v ) in v, and 0 otherwise. The metric favours the nodes v that are semantically matched to more keywords of the query Q.

Learning the Ranking Model: In our current implementation of the DWRank algorithm a ranking model is learnt from the features i.e. the text relevancy, the hub score and the authority score. This way, it constructs the ranking model ‘M’ automatically in order to provide the most relevant results by automatically determining the weights of features. To combine different features in a quantitative metric DWRank automatically learns from a set of training instances. Training instances can be regarded as past query experiences, which can teach the system how to rank the results when new queries arrive. Each training instance is composed of the query, one of its relevant/irrelevant answers and a list of features. Intuitively we want to identify the model ‘M’ from features that can rank relevant answers as high as possible for a given query in the training set T. We want a model such that the log-likelihood of relevant matches is maximized.

This type of model has been extensively studied in the machine learning community. We used LambdaMART [28] as a learning to rank tool. The main reason for our choice is its ability to optimise the non-smooth cost functions (i.e. NDCG). The implementation details are provided in Section 3.3.

3.2.1. ConHubIdx

The ConHubIdx is a bi-level index where each entry in the index maps a concept of an ontology to its normalised hub score h n ( v , O ) as shown in Fig. 2 (top right). To construct the ConHubIdx for all ontologies in O, (1) the hub function is executed in an iterative way to get the hub score of all the concepts in ontology O, and (2) after the last iteration, we compute the normalised hub scores and (3) insert the concepts along with their normalised hub scores in an ontology to the index.

3.2.2. OntAuthIdx

The OntAuthIdx is an index where each entry in the index maps an ontology to its normalised authority score a n ( O ) as shown in Fig. 2 (bottom right). To construct the OntAuthIdx on the corpus O, (1) the authority function is executed to get an authority score of all the ontologies in O, (2) after the last iteration, the normalised authority scores are computed, and (3) the ontology along with its normalised authority scores is inserted as an entry to the index.

3.2.3. Inter-ontology relationships extraction

As mentioned earlier, the authority function leverages the inter-ontology relationships that are directed links among ontologies. If ontology OntA reuses the resources in ontology OntB, ontology OntA declares the reuse of resources through an OWL import property, i.e. owl:imports. Since some ontology practitioners fail to explicitly declare the reuse of ontologies, the owl:imports relationships in an ontology are often inaccurate representations of the inter-ontology relationships. We therefore identify the implicit inter-ontology relationships by considering the reused resources in the corpus. Finding the implicit inter-ontology relationships involves the following steps:

OPEN IN VIEWER

Algorithm 1.

findRel: Inter-Ontology Relationships Extraction

The inter-ontology relationship extraction process is briefly described in Algorithm 1. Firstly the namespace of each ontology is identified (line 1–3). TopNS() returns the namespace that is the namespace of most of the resources in the ontology. The SPARQL query to find the namespaces in an ontology and the count of resources defined with each namespace is shown in Listing 1. Secondly, all reused resources are identified and each resource and a corresponding list of hosting ontologies are recorded in M r o as a key value pair (line 4–9). Finally, for each resource in M r o the home ontology is identified and the resource URI is replaced with the ontology URI and all missing inter-ontology relationships for an ontology are recorded in M o o (line 10–19).

An important point to consider is that although an ontology OntA may reuse more than one resource from another ontology OntB there will only be one inter-ontology relationship from OntA to OntB according to the semantics of the owl:imports property. Therefore, independently of the number of resources that are reused in OntA from OntB, we create a single inter-ontology relationship from OntA to OntB.

Tables 1 and 2 show the top five ontologies in the benchmark ontology collection [3] and the corresponding number of inter-ontology relationships that are directed to these ontologies (i.e. reuse count) counted through explicit and implicit relationships, respectively. A detailed analysis on the effectiveness of FindRel is presented in Section 5.2.3.

4.2.1. Candidate result set selection

A keyword query evaluation starts with the selection of a candidate set C Q for Q. A candidate result set C Q is characterised by two features:

In our current implementation, we check the word sense similarity using WordNet and set the word sense similarity threshold θ = 0.85 . Each entry in a candidate list denotes a candidate concept ‘v’ and is a pair ( v , O ) (shown in Fig. 3) of v and O where v ∈ V ( O ) . Since for the reused resources there are multiple hosting ontologies, therefore ‘v’ may have multiple entries in a candidate set if it is a reused resource.

4.2.2. Concept relevance

For each entry in the candidate list, two scores are retrieved from the stored indices built during the offline ranking phase. The entry ( v , O ) is used to retrieve the hub score of concept v in ontology O from the ConHubIdx, and the authority score of ontology O from the OntAuthIdx. Along with the hub and authority score, the max_hub score and the min_hub score for each concept in the candidate list is computed from ConHubIdx, while the text relevancy F V ( v , Q ) is calculated as described in Eq. (6). Once a complete feature set for all concepts in the candidate list is retrieved, the framework generates the relevance score for the concepts using the ranking model learned in Section 3.3.

4.2.3. Top-k results

Once the relevance score for all concepts in the candidate list is computed, the framework ranks the list according to the relevance score and returns the top-k results to the user.

5.2.1. Effectiveness of DWRank

In the first set of experiments, we evaluated the effectiveness of DWRank in comparison with the eight baseline ranking models.

Experiment-1: Offline learning

In this experiment, we study the impact of the offline training on the quality of the ranking. For the evaluation we implemented two versions of DWRank:

For DWRank fixed weight linear model we ran the ten sample queries on the ontology collection and retrieved the top-k results according to the proposed linear ranking model in Eq. (6). We recorded the P@10, the MAP@10, the DCG@10 and the NDCG@10. The effectiveness measure results of this implementation of DWRank are shown in Table 3. To evaluate DWRank with learning to rank approach, the Leave-one-out Cross Validation (LOOCV) approach is adopted as follows: for n number of queries we remove the relevance judgement for the training examples of one query and train the ranking model on the training examples of the remaining n − 1 queries and then we evaluate the performance of the trained model on the n t h query. Once the process is repeated for n queries, the mean performance is computed. We applied LOOCV on the queries and the gold standard; and record the P@10, the MAP@10, the DCG@10 and the NDCG@10. The results are presented in Table 3.

The experimental results show that DWRank with the hub score, the authority score and the text relevancy combined by a model learnt through LTR performs better than the DWRank fixed weight linear model.

Experiment-2: Effectiveness of Top-k Search

Next, we compared our results with the available baseline for the sample queries. We compare the performance of the DWRank learning to rank model (so onward referred as DWRank) with the baseline algorithms. The results are shown in Fig. 4. Each graph here presents an effectiveness measure of a ranking model for all ten queries, where the x-axis is the ranking model and the y-axis is the unit of measure. Each box on a graph presents the range of effectiveness measure for 10 sample queries according to the gold standard. Figure 4 shows the maximum, minimum and average performance of DWRank in comparison to the performance of the baseline ranking models for each of the ten queries. The graph shows that DWRank performs better than the best performing ranking algorithm for most queries. For some of the queries, the P@10 and MAP@10 for DWRank is lower than the other best performing ranking models. However, the maximum average MAP@10 for DWRank on ten queries is 0.80 which is greater than the average of Tf-Idf, the best baseline ranking model, (i.e., 0.55). The box plot also shows that MAP@10 of DWRank ranges from 0.65 ~1.0 that means the performance of DWRank is more stable on the ontology collection for the sample queries than the baseline ranking models.

Similarly, the DCG@10 values in Fig. 4(c) and NDCG@10 values in Fig. 4(d) for the ranking models show that DWRank is more effective than the baseline models. The maximum and minimum measures are closer to the Betweenness Measure (BM) or the Tf-Idf model, however, the average performance of DWRank is much higher than the average performance of the BM and Tf-Idf models.

Discussion

The results show that DWRank with learning to rank model outperforms DWRank fixedweight linear model as well as the baseline ranking models. Moreover, the results presented in [4] show that DWRank fixed weight linear model is more effective as compared to the baseline ranking models. This implies that although the learning to rank approach increases the effectiveness of the base model, i.e. DWRank, the characteristics of DWRank (centrality and authoritativeness) are effective enough to produce a good ranking. The results in [3] shows that popularity (i.e. reuse of ontology concepts) or graph based analysis (i.e. coverage or centrality) alone are not an effective model for ontology ranking. However, our approach leverages both, centrality (graph based approach) and reuse (popularity based approach) together to produce a ranking much closer to human expectations than the state-of-the-art ranking algorithms.

5.2.2. Quality of HubScore – measure of the centrality of a concept

To evaluate the quality of the hub score we consider CARRank [29] as a baseline. The reason of comparing the hub score quality with the quality of CARRank is two fold: (1) CARRank uses a similar approach (i.e. ReversePage Rank), and (2) the performance results in [29] prove it a better approach than other centrality measures e.g. Betweenness Measure [1] and Density Measure [1]. Since the CARRank algorithm and the gold standard are not available online, we implemented CARRank in Java and adopted a similar evaluation strategy as presented in [29].

To evaluate the two approaches, we tried to collect ontologies and their top-10 concepts. Four representative ontologies, where members of CSIRO were part of the ontology engineering team, were selected as shown in Table 4. We asked the ontology engineers of the four ontologies to list the top 10 central concepts of the ontology they co-designed. We then compare the reference ranking produced by the ontology engineer with the top-10 ranked list generated by HubScore and CARRank. Table 5 presents the comparison on the concepts ranking for the SSN and the ABS ontology. Concepts listed in bold font are the relevant ranking results.

In Table 5HubScore ranks 8 (resp. 7) relevant answers in the top 10 ranking results for the SSN (resp. ABS) ontology in comparison to CARRank that ranks 7 (resp. 6) relevant answers for the SSN (resp. the ABS) ontology. Moreover, relatively more relevant results are ranked at the top of the list by HubScore. The quality of both these algorithms is measured in terms of P@10 for the four representative ontologies and presented in Fig. 5.

OPEN IN VIEWER

Fig. 5.

Comparison of Ranking Concepts.

Though the precision of HubScore on the representative ontologies increases by up to 20% compared to CARRank, the ranked list also seems more meaningful than CARRank. This can be seen in Table 6 that presents the top 5 concepts of the FOAF ontology ranked by HubScore and CARRank.

The Authority score calculation of DWRank in Section 3.1.2 is based on a link-based analysis (i.e. PageRank) that computes the popularity of an ontology in the ontology corpus. However, missing links among ontologies lead to wrong popularity scores [6]. We, therefore, find the missing inter-ontology links and present a graph-based analysis of the ontology corpus that shows the increased connectivity of the ontology corpus after extraction of the implicit inter-ontology links with FindRel.

Table 7 presents different statistical properties of the ontology corpus with and without considering explicit inter-ontology relationships. The Node notation represents the number of ontologies in the corpus. Sink Node is the number of ontologies that are imported (reused) by other ontologies and Source Node represents the number of ontologies that import at least one ontology. Isolated Node counts the ontologies which neither import nor are imported by any other ontology in the corpus. Similarly, Edge is the count of links in the ontology corpus and Average Degree is the number of inlinks and outlinks for each node (ontology). Highest Degree, Highest Indegree and Highest Outdegree are the maximum number of inlinks and outlinks, maximum number of inlinks and maximum number of outlinks for a node, respectively.

Three language-level vocabularies, namely RDF,5

Nodes remains the same in the explicit link ontology corpus and the implicit link ontology corpus, as only the missing links among ontologies are extracted in FindRel; however, they differ in the number of edges. As shown in Table 6, the Implicit-Link Graph contains more edges (links) than the Explicit-Link Graph. Average Degree and Isolated Node values for both the graphs represent that without implicit inter-ontology links, the ontology corpus is disconnected and most of the ontologies (i.e. isolated nodes) will end up with the same authority score that will minimise the effect of the authority score contribution towards the DWRank model. The Implicit-Link Graph statistics are more interesting, because it shows that ontologies often miss an import statement in their meta-description despite reusing some concepts of an external ontology. Therefore, it will be insufficient to only leverage meta-descriptions to perform the link analysis for carrying out tasks such as ranking.