본 문서에서는 SIGMOD 2017에서 발표된 "BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Jinhong Jung et al., BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart, SIGMOD 2017
Random Walk with Restart
Random Walk with Restart (RWR)는 그래프에서 두 정점 사이의 관계도 (relavance)를 측정하는 모델입니다. 하나의 정점을 기준으로 다른 모든 정점들과의 관계도를 구하면 기준 정점 (seed or query node)에 대한 개인화된 정점 랭킹을 구할 수 있고 이러한 랭킹은 그래프에서 추천 시스템, 이상 현상 탐지, 검색 등에 활용될 수 있습니다. 예를 들어서 아래 그림에서 기준 정점은 node 4가 되고 RWR의 결과는 오른쪽 표와 같이 node 4 대해 다른 정점들과의 점수를 계산합니다. 이와 같이 하나의 기준 정점에 대해 다른 모든 정점의 RWR 점수를 구하는 것을 single source RWR 문제라고도 합니다.
 |
| 그림 1. Random Walk with Restart의 예제 |
RWR은 랜덤 서퍼 (random surfer)를 이용하여 정점간의 관계도를 계산합니다. 랜덤 서퍼는 기준 정점에서 출발해서 매번 다음의 행동중 하나를 랜덤으로 선택하여 수행합니다.
- Random walk (랜덤 워크): 현재 정점의 이웃 정점중 하나를 랜덤으로 선택하여 이동합니다. 예를 들어서, 위 그림에서 현재 정점이 12번이라고 한다면 10번 또는 11번 중 하나를 랜덤으로 선택하여 이동합니다.
- Restart (재시작): 기준 정점으로 되돌아갑니다. 예를 들어서, 위 그림에서 기준 정점인 4번으로 돌아가는 것을 의미합니다.
이를 지속적으로 수행하다 보면 각 정점 별로 랜덤 서퍼가 방문하게 되는 확률이 수렴하게 되고 이 확률을 기준 정점과 해당 정점의 관계도로 활용합니다. 주기적으로 재시작을 하기 때문에 기준 (시작) 정점 주변의 이웃 정점에 점수가 많이 쌓이게 됩니다. 즉, 시작 정점과 밀접하게 연결이 되어 있을 수록 큰 점수를 받게됩니다.
Existing methods for RWR and Limitations
RWR 점수 벡터 (single source RWR)를 정확하게 구하는 방법은 크게 반복적 기법과 전처리 기법으로 나뉘어집니다. 반복적 기법은 초기 점수 벡터에서 인접 행렬에 대한 연산 (예, 행렬-벡터 곱)을 반복적으로 적용하여 최종적인 RWR 점수로 수렴하게 하는 기법을 말합니다. 이러한 반복적 기법은 별도의 전처리를 하지 않기 때문에 희소한 인접 행렬을 저장하는데 필요한 비용만을 요구하게 되어서 인접 행렬을 저장할 수 있는한 대규모 그래프를 처리할 수 있는 장점이 있습니다. 하지만 수렴을 할때까지 행렬-벡터 곱을 반복적으로 수행해야 하기 때문에 기준 정점에 대한 RWR 질의를 처리하는데 시간이 오래 걸리는 단점이 있습니다.
전처리 기법은 RWR의 계산 결과를 미리 저장해두거나 중간단계에서 관련된 데이터를 미리 전처리를 하여 RWR 질의 시간을 단축하는 것을 목표로하는 기법입니다. 그러나 모든 기준 정점에 대해서 RWR 벡터 값을 구해두는 것은 굉장히 많은 시간이 걸리고 그래프가 조금만 커져도 메모리에 저장할 수도 없습니다. 따라서, 빠르게 RWR을 구할 수 있다는 장점에도 불구하고 확장성에 문제가 있어서 대규모 그래프를 처리할 수 없습니다.
그 외에 RWR 값을 근사 (approximation)해서 빠르게 구한다거나 기준 정점으로 부터 RWR 관점에서 핵심적으로 관련 있는 top-k 개의 정점만을 찾는 기법들이 있지만, RWR 값을 정확하게 구할 수 없어서 RWR을 기반으로 하는 다양한 응용의 성능이 떨어지게 되고, top-k개 만을 구하는 경우는 모든 점수를 사용하는 응용 (예, 이상 현상 탐지, 로컬 클러스터링, 서브 그래프 마이닝)에는 사용이 제한됩니다. 그렇다면 어떻게 해야 대규모 그래프에서 RWR 점수 벡터의 모든 값을 정확하고 빠르게 구할 수 있을까요?
Proposed Method
본 논문에서는 RWR 값을 정확하게 구하는 동시에 빠르고 확장성있게 계산할 수 있는 BePI (Best of Preprocessing and Iterative approaches)를 제안합니다. BePI의 핵심적인 목표는 전처리 기법과 반복적 기법의 장점을 최대한 취하는 것으로 이를 위해 다음의 아이디어를 제안하였습니다.
- Idea 1) 전처리가 용이할 수 있도록 실세계 그래프의 구조적 특징들을 활용합니다.
- Idea 2) 계산 확장성을 높이기 위해서 전처리 구조내에 반복적 기법을 활용합니다.
- Idea 3) 반복적 기법의 성능을 최적화하여 RWR 계산 속도를 빠르게 합니다.
본 문서에서는 실세계 그래프의 구조적 특징이 RWR 계산에서 어떻게 활용되는지에 대한 핵심적인 내용에 대해서만 논의합니다. 구체적인 방법론 및 수식은 논문을 참고하시면 됩니다. 먼저, BePI에서는 실세계 그래프의 구조적 특징을 입력 그래프의 인접 행렬을 재정렬 (reorder)하는데 활용합니다. BePI에서 활용하는 구조적 특징은 deadend structure와 hub-and-spoke structure 입니다.
 |
| 그림2. Deadend 및 hub-and-spoke 구조를 통한 행렬의 재정렬 |
- Deadend structure: 실세계 그래프에서는 들어오는 간선은 있는데 나가는 간선이 없는 정점들이 다수 분포합니다. 이러한 정점을 deadend라고 부릅니다. 예를 들어서 웹 문서 그래프에서 이미지 파일같은 경우는 해당 파일로의 링크는 있지만 파일에서 나가는 링크는 존재하지 않습니다. 그래프마다 deadend 분포는 상이하지만 논문에서 사용한 그래프에서는 5~40%의 정점이 deadend 였습니다. deadend가 아닌 정점과 deadend인 정점을 나누어 인접 행렬의 행과 열을 재정렬 (permute)하면 그림 2(b)와 같이 재정렬 됩니다. 이러한 구조를 deaded structure라고 합니다.
- Hub-and-spoke structure: 실세계 그래프의 정점 연결 차수 (degree)는 멱법칙 (power-law)를 따른다고 알려져 있습니다. 즉, 연결 차수가 매우 높은 정점 (hub)은 많지 않고 대부분 연결 차수가 적은 정점 (spoke)들로 연결 차수의 분포가 정규분포와 달리 한쪽으로 쏠려있습니다 (링크). 이러한 특징을 이용해 spoke와 hub로 나누어 인접행렬을 그림 2(c)와 같이 재정렬 할 수 있습니다. 이러한 구조를 hub-and-spoke 구조라고 합니다 (자세한 방법론은 이 논문에서 확인할 수 있습니다).
BePI에서는 위 두가지 구조를 활용하여 먼저 deadend 구조를 기반으로 인접 행렬을 재정렬 한뒤 (그림 2(b)) deadend가 아닌 정점에 해당하는 부분 행렬 (Hnn)에 대해서 hub-and-spoke 구조의 재정렬을 수행합니다 (그림 2(d)). 이렇게 재정렬을 하면 0인 부분들에 해당하는 연산은 할필요가 없게 되어지고 한쪽으로 모아진 0이 아닌 부분에 대해서 연산을 집중할 수 있습니다.
조금 더 구체적으로 설명하자면 RWR 연산에서 전처리를 한다는 것은 인접 행렬과 관련된 행렬에 대해 역행렬을 구하는 연산과 동치인데 아래와 같이 재정렬이 되게 되면 전체 역행렬을 구하는 것은 부분 블록 행렬들의 역행렬을 구하는 것으로 동일하게 구할 수 있습니다 (이때 사용되는 이론이 block elimination 입니다). 재정렬된 행렬의 블록의 크기가 매우 작기 때문에 역행렬을 굉장히 빠르게 구할 수 있습니다.
 |
| 그림 3. 재정렬된 행렬에 대한 전처리 방법의 개략도 |
위와 같이 BePI에서는 재정렬과 blcok elimination을 통해 전처리의 토대를 만듭니다. 그러나 위 그림과 같이 역행렬을 구하기 용이한 부분이 있는 반면에 내부적으로 역행렬을 구하기 어려운 부분이 존재합니다. 위 그림에서 H22 행렬과 관련된 연산에 해당하는 부분인데 그래프가 커지게 되면 해당 행렬의 차원도 그에 맞게 커지게 되고, 본 논문에서 사용한 그래프의 경우 차원의 크기가 1M을 넘어가는 경우도 있습니다. 이렇게 큰 차원에서는 역행렬을 통해서 값을 구할 수 없고, 이러한 경우는 반복적 기법을 활용하여 해당 연산을 처리합니다 (Idea 2). 본 논문에서 활용하는 반복적 기법은 GMRES 입니다. 반복적 기법을 그냥 활용하게 되면 RWR 계산 속도에 도움이 되지 않으므로 반복적 기법의 수렴을 빠르게 하는 preconditioning 기법 등을 활용합니다 (Idea 3). 해당 방법들의 자세한 설명은 논문을 통해 참고하실 수 있습니다.
Experimental Results
 |
| 그림 4. BePI의 전처리 시간, 전처리된 결과의 메모리 사용량, RWR 질의 처리 시간에 대한 성능 비교 |
그림 4는 제안 방법인 BePI와 다른 경쟁 방법들의 계산 성능을 비교합니다. 먼저 그림 4(a)는 전처리 시간에 관한 비교로 다른 전처리 기법인 Bear와 LU와 비교를 수행하였습니다. 그림에서 x축은 사용한 데이터를 의미하며 크기 순으로 나열하였고 제일 큰 그래프는 Friendster로 간선수가 대략 20억개에 해당합니다. 그림 4(a)에서 볼 수 있다시피 다른 전처리 방법에 비해 매우 빠르게 전처리를 하고, 제일 큰 그래프까지 성공적으로 처리를 할 수 있습니다.
그림 4(b)는 전처리된 결과의 메모리 사용량을 의미합니다. 다른 전처리 기법인 Bear나 LU에서는 그래프가 커지면 매우 많은 메모리를 요구하게 되기 때문에 큰 그래프를 처리할 수 없게 됩니다. BePI는 성공적으로 제일 큰 그래프까지 처리할 수 있고 다른 경쟁 메소드 대비 130배 적은 메모리로 RWR을 계산 할 수 있습니다.
그림 4(c)는 RWR 질의를 처리하는데 드는 평균 시간을 의미합니다. 다른 반복적 기법인 Power와 GMRES를 추가하여 비교하였습니다. 전처리 기법은 큰 그래프를 처리할 수 없으므로 Wikipedia 데이터 까지만 RWR 값을 구할 수 있습니다. 반복적 기법은 큰 그래프를 처리할 수 있지만 BePI에 비해 RWR 계산 속도가 느린 것을 확인할 수 있습니다. BePI 는 다른 경쟁 메소드 대비 2~10배 정도 RWR을 빠르게 계산할 수 있습니다.
Conclusion
본 문서에서는 SIGMOD 2017에서 발표된 "BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart" 논문을 소개하였습니다. 해당 논문은 실세계 그래프의 구조적 특징을 활용하여 전처리 방법론과 반복적 방법론을 효과적으로 활용하여 대규모 그래프에서 RWR 계산을 정확하고 빠르게 구할 수 있는 방법인 BePI를 제안하였습니다. 실험을 통해 제안한 기법이 다른 경쟁 기법들 보다 더 확장성 있고 빠르게 RWR 값을 구하는 것을 확인하였습니다. 논문에 대한 상세 정보는 (링크)를 통해 확인할 수 있습니다.