A subgraph matching algorithm based on subgraph index for knowledge graph

doi:10.1007/s11704-020-0360-y

2021-09-27

PRE

DOI：10.1007/s11704-020-0360-y

原文链接

原文求助

摘要

En 中文

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 q and a data graph G, the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of q on G. 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 FGq(T)-Match. The subgraph matching algorithm consists of two key designs. One design is a subgraph index of matching-driven flow graph (FGq(T)), 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 FGq(T). Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.

Keyword:

knowledge graph

subgraph matching

subgraph index

matching tree