New Adaptive Matching Order and Performance Comparison for Subgraph Matching Problem

Seunghwan Min, Wonseok Shin, Chaewon Kim, Kunsoo Park

http://doi.org/10.5626/JOK.2022.49.1.1

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.