자기 동형 사상을 활용한 Minimum Image Based Support 계산

Abstract

그래프 마이닝에서 핵심적인 문제 중 하나는 frequent subgraph mining 문제이다. Frequent subgraph mining 문제는 데이터 그래프에서 정해진 support가 가장 큰 부분 그래프들을 찾는 문제이다. 이 때, support는 그래프에서 부분 그래프가 얼마나 자주 등장하는지를 나타내는 지표이다. Minimum Image Based Support (MNI)는 frequent subgraph mining에서 자주 사용되는 support이다. 본 논문에서는 쿼리 그래프의 자기 동형 사상(Automorphism)을 이용하여 MNI의 계산을 효율적으로 계산하는 방법을 제시한다. 추가적으로, MNI 계산 중 백트래킹 과정을 병렬화 하여서 멀티코어 환경에서의 성능을 개선하였다. 또한, 실제 데이터 그래프를 통해 실험을 진행하여 자기 동형 사상과 병렬화를 사용하는 것이 기존의 방법에 비해 효율적임을 입증하였다.

One of the core problems in graph mining is the frequent subgraph mining problem. The frequent subgraph mining problem is to find subgraphs with the largest support in a data graph, where the support refers to how frequently a subgraph appears in the graph. MNI is a commonly used support measure in frequent subgraph mining. In this paper, we propose an efficient method for computing the MNI using automorphism of the query graph. Additionaly, we parallelized the backtracking process during MNI computation to improve performance in a multicore environment. Experiments conducted on real data graphs demonstrate that our method of using automorphism and parallelization is efficient for computing the MNI.