Given a large graph, how can we calculate the relevance between nodes fast and accurately? Random walk with restart (RWR) provides a good measure for this purpose and has been applied to diverse data mining applications including ranking, community detection, link prediction, and anomaly detection. Since calculating RWR from scratch takes long, various preprocessing methods, most of which are related to inverting adjacency matrices, have been proposed to speed up the calculation. However, these methods do not scale to large graphs because they usually produce large and dense matrices which do not into memory. In addition, the existing methods are inappropriate when graphs dynamically change because the expensive preprocessing task needs to be computed repeatedly.
In this paper, we propose Bear, a fast, scalable, and accurate method for computing RWR on large graphs. Bear has two versions: a preprocessing method BearS for static graphs, and an incremental update method BearD for dynamic graphs. BearS consists of the preprocessing step and the query step. In the preprocessing step, BearS reorders the adjacency matrix of a given graph so that it contains a large and easy-to-invert submatrix, and precomputes several matrices including the Schur complement of the submatrix. In the query step, BearS quickly computes the RWR scores for a given query node using a block elimination approach with the matrices computed in the preprocessing step. For dynamic graphs, BearD eciently updates the changed parts in the preprocessed matrices of BearS based on the observation that small parts of the preprocessed matrices change when few edges are inserted or deleted. Through extensive experiments, we show that BearS signi cantly outperforms other state-ofthe-art methods in terms of preprocessing and query speed, space-eciency, and accuracy. We also show that BearD quickly updates the preprocessed matrices, and immediately computes queries when the graph changes.
대규모 그래프에서 어떻게 노드간의 유사도를 빠르고 정확하게 구할 수 있을까? Random walk with restart (RWR)은 그래프 유사도로써 랭킹, 커뮤니티 검출, 링크 예측, 이상 탐지 등 다양한 데이터마이닝 어플리케이션에 활용되어 왔다. 질의가 주어졌을 때 RWR을 처음부터 계산하는 것은 상당한 시간이 걸리기 때문에 질의 시간을 단축시키기 위하여 그래프의 인접행렬의 역행렬을 구하는 것과 관련된 여러가지 전처리 기법들이 제안되었다. 그러나 역행렬을 구하는 것과 관련된 방법들은 크고 밀집된 전처리 결과들을 만들어 내고 많은 양의 저장 공간을 요구하기 때문에 대규모 그래프를 처리하는데 적합하지 않다. 또한 기존의 전처리 방법들은 그래프가 시간에 따라 동적으로 변할 때 계산량이 많은 전처리 작업을 반복적으로 수행해야하기 때문에 동적 그래프에 적절하지 않다.
본 연구는 이러한 문제점을 개선하여 대규모 그래프에서 빠르고 정확하게 RWR을 계산할 수 있는 방법을 제안한다.본 연구에서 제안한 Bear는 두 가지 방법으로 구성되어 있다. 첫 번째 방법은 정적 그래프 기반의 전처리 방법인 BearS이며, 두 번째 방법은 동적 그래프 기반의 업데이트 방법인 BearD이다.
BearS는 전처리 단계와 질의 단계로 나누어진다. 전처리 단계에서 BearS는 주어진 그래프의 노드를 재배열하여 그래프의 인접행렬의 역행렬을 쉽게 구할 수 있도록 부분 행렬들을 만들고, 부분 행렬들로 부터 질의 계산에 필요한 여러 가지 행렬들을 미리 계산한다. 질의 단계에서 BearS는 미리 계산된 행렬들과 블록 제거 방법을 이용하여 주어진 질의 노드에 대해 RWR 점수를 빠르게 계산한다. 동적 그래프에 대해서, BearD는 간선이 삽입되거나 삭제되었을 때 전처리 행렬에서 일부만 변화된다는 점을 이용하여 전처리된 행렬들의 변화된 부분을 효율적으로 업데이트한다. 여러가지 실험을 통하여 BearS가 다른 여러 가지 최신 기법 보다 전처리 및 질의 시간, 메모리 사용량, 계산된 점수의 정확도에서 뛰어남을 보인다. 또한 그래프가 변할 때 BearD가 전처리된 결과를 효율적으로 업데이트하고 질의를 빠르게 계산함을 보인다.
