Seunghwan Min  Wonseok Shin  Chaewon Kim  Kunsoo Park

10.5626/JOK.2022.49.1.1

graph analysis subgraph matching matching order adaptive matching order

In recent years, graph analysis has been used in various applications. One of the fundamental problems in graph analysis is the subgraph matching problem. Given a data graph and a query graph, the subgraph matching problem is to find all embeddings of the query graph in the data graph. Many backtracking-based algorithms have been studied to solve this problem. In this paper, we analyzed the problems in adaptive matching order proposed by DAF, a state-of-the-art algorithm that solves this problem, and introduced an improved adaptive matching order. Furthermore, we conducted experiments with real data graphs to demonstrate that the proposed matching order was more effective than the previous matching orders if the pruning technique was not used or the elapsed time was not very short even if the pruning technique was used.