Accelerating subgraph matching by anchored relationship on labeled graph

摘要

Subgraph matching is one fundamental issue in the research area of graph analysis, which has a wild range of applications, including question answering, semantic search and community detection. Recent studies have designed some near-optimal matching orders and data indexes to reduce the unpromising redundant calculations. However, the influences of recalculation on some positive candidate vertices were ignored in the iterative process of subgraph matching. In this paper, the novel concepts of an anchored node pair and anchored relationship are proposed as the theoretical basis to solve recalculation on subgraph matching. Thus, two key aspects are considered to reduce the redundant and recalculated node pairs. The first aspect involves using the dominating relationship of the anchored node and its follower to prune the negative node pairs, and an index of matching-driven flow graph is built to minimize the positive candidate vertices by using a heuristic algorithm. The second aspect involves exploring the anchored relationship to analyze the recalculated region of a matching stream, and two novel strategies are designed to manipulate the intermediate results of the partial subgraph isomorphism to avoid revalidation in the subgraph matching process. Extensive empirical studies on real and synthetic datasets demonstrate that our techniques outperform the state-of-the-art algorithms.