Random walk with restart on large graphs using block elimination

Abstract

대규모 그래프에서 어떻게 노드간의 유사도를 빠르고 정확하게 구할 수 있을까? Random walk with restart (RWR)은 그래프 유사도로써 랭킹, 커뮤니티 검출, 링크 예측, 이상 탐지 등 다양한 데이터마이닝 어플리케이션에 활용되어 왔다. 질의가 주어졌을 때 RWR을 처음부터 계산하는 것은 상당한 시간이 걸리기 때문에 질의 시간을 단축시키기 위하여 그래프의 인접행렬의 역행렬을 구하는 것과 관련된 여러가지 전처리 기법들이 제안되었다. 그러나 역행렬을 구하는 것과 관련된 방법들은 크고 밀집된 전처리 결과들을 만들어 내고 많은 양의 저장 공간을 요구하기 때문에 대규모 그래프를 처리하는데 적합하지 않다. 또한 기존의 전처리 방법들은 그래프가 시간에 따라 동적으로 변할 때 계산량이 많은 전처리 작업을 반복적으로 수행해야하기 때문에 동적 그래프에 적절하지 않다. 본 연구는 이러한 문제점을 개선하여 대규모 그래프에서 빠르고 정확하게 RWR을 계산할 수 있는 방법을 제안한다.본 연구에서 제안한 Bear는 두 가지 방법으로 구성되어 있다. 첫 번째 방법은 정적 그래프 기반의 전처리 방법인 BearS이며, 두 번째 방법은 동적 그래프 기반의 업데이트 방법인 BearD이다. BearS는 전처리 단계와 질의 단계로 나누어진다. 전처리 단계에서 BearS는 주어진 그래프의 노드를 재배열하여 그래프의 인접행렬의 역행렬을 쉽게 구할 수 있도록 부분 행렬들을 만들고, 부분 행렬들로 부터 질의 계산에 필요한 여러 가지 행렬들을 미리 계산한다. 질의 단계에서 BearS는 미리 계산된 행렬들과 블록 제거 방법을 이용하여 주어진 질의 노드에 대해 RWR 점수를 빠르게 계산한다. 동적 그래프에 대해서, BearD는 간선이 삽입되거나 삭제되었을 때 전처리 행렬에서 일부만 변화된다는 점을 이용하여 전처리된 행렬들의 변화된 부분을 효율적으로 업데이트한다. 여러가지 실험을 통하여 BearS가 다른 여러 가지 최신 기법 보다 전처리 및 질의 시간, 메모리 사용량, 계산된 점수의 정확도에서 뛰어남을 보인다. 또한 그래프가 변할 때 BearD가 전처리된 결과를 효율적으로 업데이트하고 질의를 빠르게 계산함을 보인다.