Random Walk-based Large Graph Mining Exploiting Real-world Graph Properties

Abstract

Numerous real-world relationships are represented as graphs such as social networks, hyperlink networks, and protein interaction networks. Analyzing those networks is important to understand the real-life phenomena. Among various graph analysis techniques, random walk has been widely used in many applications with satisfactory results. However, various real-world graphs are large and complicated with diverse labels. Traditional random walk based methods require heavy computational cost, and disregards those labels for performing random walks; thus, its utilization has been limited in such large and complicated graphs.

In this thesis, I handle the technical challenges of mining large real-world graphs based on random walk. Real-world graphs have distinct structural properties which become a basis to increase the performance of the random walk in terms of speed and quality. Based upon this idea, I develop fast, scalable, and exact methods for node ranking using random walk in large-scale plain networks. I also design accurate models using random walks for node ranking and relational reasoning in labeled graphs such as signed networks and knowledge bases.

Through extensive experiments on various real-world graphs, I demonstrate the effectiveness of the methods and models proposed by this thesis. The proposed methods process 100 times larger graphs, and require up to 130 times less memory with up to 9 times faster speed compared to other existing methods, successfully scaling to billion-scale graphs. Also, the proposed models substantially improve the predictive performance of a variety of tasks in labeled graphs such as signed networks and knowledge bases.

다양한 실세계 자연 현상에서의 관계들은 소셜 네트워크, 하이퍼링크 네트워크와 단백질 상호작용 네트워크와 같이 정점과 간서의 그래프로 표현된다. 이러한 네트워크를 분석하는 것은 실세계의 현상을 이해하는데 매우 중요하다. 다양한 그래프 분석 기법중에 랜덤 워크라는 기법이 만족스러운 성능과 함께 많은 그래프 마이닝 응용에 널리 활용되어 왔다. 그러나 대다수의 실세계 그래프는 그 규모가 굉장히 크고 다양한 라벨 정보와 함께 복잡하게 표현된다. 전통적인 랜덤 워크 기반의 기법들은 계산량이 많이 요구되고, 랜덤 워크를 하는데 있어서 다양한 라벨 정보를 전혀 고려하지 않아 라벨로 표현되는 그래프의 고유한 특성이 무시되게 된다. 그래서 이와 같이 복잡하면서 대규모 그래프에서는 랜덤 워크의 실질적 활용이 제한되어왔다.

본 학위 논문에서는 랜덤 워크 기반의 대규모 실세계 그래프 분석의 기술적 한계를 해결하고자 한다. 실세계 그래프는 고유한 구조적 특징들을 가지고 있으며 이러한 구조적 특징들은 속도와 품질의 측면에서 랜덤 워크의 성능을 향상시키는데 기반이 될 수 있다. 이러한 아이디어를 활용하여, 대규모의 라벨이 없는 일반적인 네트워크에서 랜덤 워크 기반의 개인화된 정점 랭킹 계산을 빠르고, 확장성 있고 정확하게 구하는 기법을 제안한다. 또한 부호화된 네트워크 또는 지식 베이스와 같은 라벨이 있는 그래프에서 개인화된 정점 랭킹과 관계 추론을 위한 랜덤 워크 기반의 모델을 제안한다.

다양한 실세계 그래프에서 광범위한 실험을 통해 본 학위 논문에 의해 제안된 방법과 모델의 효과성을 보인다. 제안하는 방법은 다른 경쟁 기법들과 비교했을 때 최대 100배 더 큰 그래프를 처리할 수 있고, 최대 130배 적게 메모리를 사용하면서, 최대 9배 빠른 속도를 보이며, 결과적으로 수 십억 규모의 그래프에서 랜덤 워크 기반의 개인화된 정점 랭킹을 성공적으로 구할 수 있다. 또한, 제안하는 랜덤 워크 기반의 모델들은 부호화된 네트워크와 지식 베이스와 같은 라벨이 있는 그래프에서 부호 예측, 간선 예측, 이상 현상 탐지, 관계 추론 등의 다양한 응용에서 다른 경쟁 모델들보다 더 좋은 예측 성능을 보인다.