다각적 Top-k 부분 그래프 질의를 위한 효율적인 알고리즘

이선호, 박근수

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

부분 그래프 매칭은 그래프 분석에서 핵심적이고 중요한 문제로서 데이터 그래프에서 쿼리 그래프의 모든 임베딩을 찾는 문제이다. 그러나 이전에 제시된 알고리즘에서 출력한 결과들은 서로 간의 겹치는 부분이 많아 흥미로운 결과를 놓치는 경우가 많다. 이를 위해 다각적 top-k 부분 그래프 매칭 문제가 제시되었다. 다각적 top-k 부분 그래프 매칭 문제는 쿼리 그래프의 임베딩들 중 커버리지가 가장 높게 되는 k개의 임베딩을 찾는 문제이다. 본 논문에서는 해당 문제에 대한 알고리즘을 제시하고 기존 알고리즘과 비교하여 다각적인 top-k 결과를 효율적으로 찾는다는 것을 입증하였다.