최대 이분 매칭 기반의 가지치기를 활용한 부분 그래프 동형 알고리즘 성능 향상

Abstract

대형 그래프에 대한 분석은 최근 소셜 네트워크, 생물 정보학, 화학 등 다양한 분야에서 점차 중요해지고 있다. 그래프 분석에서 가장 핵심적인 문제 중 하나로 부분 그래프 동형 문제 (subgraph isomorphism) 가 있다. 부분 동형 그래프 문제를 backtracking 활용하여 해결하는 많은 알고리즘이 제시되어왔다. 하지만 최악의 경우 지수적인 시간 복잡도를 가지는 backtracking 특성상 여전히 특정 입력에서는 답을 찾기 위해서 지나치게 긴 시간을 소모하기 때문에 여전히 실제 문제에 적용이 어려운 경우가 존재한다. 본 논문에서는 backtracking 과정에서 알고리즘 동작 시간을 길게 만들 수 있 는 요인을 탐구하고, 이를 해결함으로써 실행 시간을 획기적으로 줄일 수 있는 새로운 기법을 소개한다. 또한, 기존 알고리즘 중 state-of-the-art 인 DAF[4] 에 기법을 적용한 경우와 그렇지 않은 경우를 구현하고 실제 그래프 데이터 상에서 실험을 진행하여 제시한 기법이 문제를 효과적으로 해결하는데 도움이 될 수 있는 방법임을 입증했다.

In recent years, graphs have been playing an increasingly important role in various domains, e.g., social networks [3], bioinformatics [8], chemistry [10] etc. One of the most fundamental problems in graph analysis is subgraph isomor- phism. Many practical solutions have been suggested for subgraph isomorphism. However, those algorithms show limited response time and scalability in han- dling real-world applications because, by the nature of backtracking, there could be many redundant computations. In this paper, we develop a new technique to prune out some parts of the search space. Furthermore, we incorporate our method to one of them and show the efficacy by conducting experiments on several real-world datasets.