Subgraph matching is to find all subgraphs isomorphic to a query graph in a database graph. Since subgraph matching problem is NP-complete, most conventional works use a filter-and-verification frame-work. In this framework, they reduce the number of candidate vertices to be used as input to subgraph isomorphism test by comparing vertex signatures. After that, they verify whether candidate subgraphs are isomorphic to the query graph by checking connections between candidate vertices. Connectivity information between vertices can reduce the cost of the query process. We propose a connection-based framework for efficient subgraph matching in a large graph. It maintains connectivity information as well as vertex signatures of the database graph. Both candidate vertex and connection checking operations in the verification phase can be reduced. The experimental result shows that our method significantly outperforms existing approaches for subgraph matching in a large graph.
그래프데이터베이스에서 주어진 쿼리 그래프와 동일한 모든 서브그래프를 찾는 연산을 서브그래프 매칭이라고 한다. 이러한 문제는 NP-Complete이기 때문에 일반적으로 연산 비용을 줄이기 위해 filter-and-verification 프레임워크와 휴리스틱에 기반한 검증 알고리즘을 사용한다. Filter-and-verification 프레임워크는 쿼리 그래프 정점에 대응되기 위한 필요조건을 검사해서 후보의 수를 줄인 후에 검증 알고리즘을 적용하는 방식이다. 기존 연구들은 정점 기반의 인덱스를 활용해 필터링 단계에서 효과적으로 후보의 수를 줄이는 데에 초점을 두었다. 하지만 전체 과정에서 검증 단계에서 발생하는 비용이 가장 큰 비중을 차지하기 때문에 보다 효율적으로 검증할 수 있는 방법이 필요하다. 검증 단계에서는 정점 간의 연결을 확인하는 연산이 가장 큰 비중을 차지한다. 검증 단계에서 발생하는 연결 검사의 수를 줄이기 위해 정점 간의 연결 정보를 활용할 수 있다. 본 연구에서는 서브그래프 매칭을 효율적으로 처리하기 위한 연결정보 기반의 프레임워크를 제안한다. 제안 방식은 정점 간의 연결 정보를 활용하기 위해 에지 기반의 인덱스를 사용한다. 필터링 단계에서는 필요 조건을 만족하는 정점과 직접적으로 연결된 정점만을 찾기 때문에 후보의 수를 줄일 수 있고, 검증 단계에서는 연결 정보를 활용해 연결 검사의 수를 효과적으로 줄일 수 있다. 제안 방식의 효율성과 효과를 보이기 위해 실험을 수행하였고, 실험 결과는 제안 방식이 기존 방식들보다 우수한 성능을 보였다.
