A subgraph matching algorithm based on subgraph index for knowledge graph |
| |
Authors: | Yunhao SUN Guanyu LI Jingjing DU Bo NING Heng CHEN |
| |
Affiliation: | 1. Faculty of Information Science and Technology, Dalian Maritime University, Liaoning 116026, China2. Faculty of Software, Dalian University of Foreign Languages, Liaoning 116044, China |
| |
Abstract: | 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. |
| |
Keywords: | knowledge graph subgraph matching subgraph index matching tree |
|
| 点击此处可从《Frontiers of Computer Science》浏览原始摘要信息 |
|
点击此处可从《Frontiers of Computer Science》下载全文 |
|