Optimization of Subgraph Matching over Knowledge Graph Based on Subgraph Indexing

Given a query graph, subgraph matching is the process of finding all the isomorphic graphs over a large data graph. Subgraph is one of the fundamental steps of many graph-based applications including recommendation system, information retrieval, social network analysis, etc. In this paper, we investigate the problem of subgraph matching over power grid knowledge graph. Since knowledge graph is a modelled as a directed, labelled, and multiple edges graph, it brings new challenges for the subgraph matching on knowledge graph. One challenge is that subgraph matching candidate calculation complexity increases with edges increase. Another challenge is that the search space of isomorphic subgraphs for a given region is huge, which needs more system resources to prune the unpromising graph candidates. To address these challenges, we propose subgraph index to accelerate the matching processing of subgraph que-ry. We use domain-specific information to construct index of power grid knowledge and maintain a small portion of search candidates in the search space. Experimental studies on real knowledge graph and synthetic graphs demonstrate that the proposed techniques are efficient compared with counterparts.