Research Of Subgraph Query On Knowledge Graph

With the development of informartion technology,the data has grown with explosive speed.These data from the Internet and life are often closely related.As a widely used data structure,graph is suitable to decribe these data.These data are organized into knowledge map using graph,and knowledge map has important applications in social networks,protein networks and road traffic systems,and so on.how to deal with large-scale graph data in knowledge graph is an important research work.Subgraph query problem as the basic problem of graph data processing,has received widespread attention from industry and academia.In the field of information retrieval,there are always some deviations between user's real information needs and the submitted requests.In the field of subgraph query,there will also exist this problem,because the user does not understand the knowledge of the graph data,which may lead to incomplete information of the input query graph.In order to better meet the query requirements,a algorithm based on distance and similarity expansion is proposed.Before the subgraph query,the query graph needs to be expanded,and then use the extended query graph for subgraph matching in the data graph.A subgraph matching algorithm named LCF based on backtracking is proposed.The algorithm is based on the traditional subgraph matching algorithm named VF2,the main improvements inculde the edge matching order,vertex matching order and pruning rule.The query graph is decomposed based on the minimum spanning tree,and the edges with strong filtering capability are selected on the basis of keeping the basic structure of the query graph,so that the mismatched edges are filtered out as soon as possible.In the matching order of the vertices,in order to filter out mismatched vertices as soon as possible,the vertices that have large degree are selected first.Meanwhile,if a vertex lable appears more frequently in data graph,the vertex is selected first.In the pruning rule,from the angle of vertex degree,vertex lable and edge lable,pruning rules with stronger pruning ability are proposed.Compared with the pruning rules of the VF2 algorithm,the search space is effectively reduced.After experimental verification,the query graph expansion can reasonably improve the user's query intention.The subgraph matching algorithm named LCF is more efficient than the VF2 algorithm.