A Knowledge Graph Query Algorithm Based On Ontology And Neighborhood

Previous work on query technologies for knowledge graph has focused on the subgraph matching based on node label.However,node labels are name or properties of node which are difficult to present the semantic relationships between nodes,thus resulting in low semantic relevance for query results.Moreover,it is expensive to storage the large-scale knowledge graph.Based on those questions,in this paper,we propose a graph querying algorithm called OAN which combines both the ontology information and neighborhood information together during the search process.And the entire query process includes compression technology,indexing technology,and query technology.First of all,we introduce a Graphic data compression technology based on bidirectional relationship.The main principle of this compression technology is to divide all nodes of knowledge graph according to the ontology information of node.Meanwhile,it merges edges which have same label based on bidirectional relationship.The compression technology can reduce the size of knowledge graph and remain the structure of graph.And it is an effective solution to significantly reduce the storage space.Secondly,we propose IBS,a two-level index based on graph signature.The upper-level index is node signature lists sorted by alphabetical order of type,and it includes node id and ontology information.The lower-level index is neighborhood signature lists including 1-hop neighbor node sets and label of edge.The index is used to filter some nodes which do not match the query graph,then speeding up the similarity calculation of filtering stage.In addition,we introduce OAN,a graph querying algorithm which combines both the ontology information and neighborhood information.We identify the candidate set for query graph by measuring the node similarity and structural similarity,in this process we use random walk method to assign weight to each neighbor which can improve the precision of subgraph matching.We further propose a pruning technique that removes the mismatched candidates to prune the search space.Moreover,we verify matching results based on edge-label isomorphic and rank the top-k graph matches by their similarity.We verify the effectiveness of our algorithms on three knowledge graph.And the results show that:(1)the compression technology and index proposed in this paper have good performance;(2)OAN can significantly improve the precision of results,and outperforms the state-of-the-art graph querying methods on both flexibility and scalability.