Introduction

Traditional search systems are designed for exact matching that retains the identical keywords in the query. Such approach is often too restrictive to provide users with the information that are actually close to the query semantically. Thus there is a need for an effective querying mechanism with the help of sematic knowledge (a.k.a, Ontology). In this project, due to the prevalence of large graphs in real life, we study the problem of subgraph querying on large scale graphs with the aid of ontology.

This work extends subgraph querying to identify semantically related matches (answers) by leveraging ontology information. We introduce the ontology based subgraph querying, which revises subgraph isomorphism by mapping a query to semantically related subgraphs in terms of a given ontology graph. The metrics are proposed to measure the quality of the answers. Based on the metric, we provide an effective framework to identify top-K answers efficiently.

An example

The example illustrates a real need from a tourist, who inquires some other tourists who recommend museum tours with guide services, and favor a restaurant named “moonlight”, which in turn is close to the museum. This query can be easily demonstrated as a small graph Q (as the figure above) over a general knowledge graph G.

Traditional graph querying technique cannot find any match for Q in G with identical labels. That is there is no node in G with the same, or even textually similar labels for the labels in Q. However, there are data nodes in G which are semantically close to the query nodes, and thus should be considered as potential answers. For example, node "Royal Gallery" in G is intuitively a kind of museum in Q. This implicit information can be found by leveraging external ontology graph from Wikipedia or Yago.

Please find more details in documents