%A Yunhao SUN, Guanyu LI, Jingjing DU, Bo NING, Heng CHEN
%T A subgraph matching algorithm based on subgraph index for knowledge graph
%0 Journal Article
%D 2022
%J Front. Comput. Sci.
%J Frontiers of Computer Science
%@ 2095-2228
%R 10.1007/s11704-020-0360-y
%P 163606-${article.jieShuYe}
%V 16
%N 3
%U {https://journal.hep.com.cn/fcs/EN/10.1007/s11704-020-0360-y
%8 2022-06-15
%X
The problem of subgraph matching is one fundamental issue in graph search, which is NP-Complete problem. Recently, subgraph matching has become a popular research topic in the field of knowledge graph analysis, which has a wide range of applications including question answering and semantic search. In this paper, we study the problem of subgraph matching on knowledge graph. Specifically, given a query graph and a data graph , the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of on . Knowledge graph is formed as a directed labeled multi-graph having multiple edges between a pair of vertices and it has more dense semantic and structural features than general graph. To accelerate subgraph matching on knowledge graph, we propose a novel subgraph matching algorithm based on subgraph index for knowledge graph, called as -Match. The subgraph matching algorithm consists of two key designs. One design is a subgraph index of matching-driven flow graph ( ), which reduces redundant calculations in advance. Another design is a multi-label weight matrix, which evaluates a near-optimal matching tree for minimizing the intermediate candidates. With the aid of these two key designs, all subgraph isomorphic mappings are quickly conducted only by traversing . Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.