An efficient and effective method for generating trillion-scale synthetic graphs

Abstract

As many applications encounter exponential growth in graph sizes, a fast and scalable graph generator has become more important than ever before due to lack of large-scale realistic graphs for evaluating the performance of graph processing methods. Although there have been proposed a number of methods to generate synthetic graphs, they are not very efficient in terMaster of space and time complexities, and so, cannot generate even trillion-scale graphs using a moderate size cluster of commodity machines. In this dissertation, we propose an efficient and effective new method that overcomes these drawbacks.

In the first part of this dissertation, we propose an efficient and scalable disk-based graph generator, TrillionG that can generate massive graphs in a short time only using a small amount of memory. It can generate a graph of a trillion edges following the Recursive MATrix (RMAT) or Kronecker graph models within two hours only using 10 PCs. We first generalize existing graph generation models to the scope-based generation model, where RMAT and Kronecker correspond to two extremes. Then, we propose a new graph generation model called the recursive vector model, which compromises two extremes, and so, solves the space and time complexity probleMaster existing in RMAT and Kronecker. We also extend the recursive vector model so as to generate a semantically richer graph database. Through extensive experiments, we have demonstrated that TrillionG outperforMaster the state-of-the-art graph generators by up to orders of magnitude.

Many researchers and industry groups often suffer from the lack of a variety of large-scale real graphs. Although a lot of synthetic graph generation methods (or models) such as RMAT and Barabasi-Albert (BA) model have been developed, their output graphs tend to be quite different from real-world graphs in terMaster of graph properties. There are a few graph upscaling methods such as Gscaler

they still fail to preserve important properties of the original graph and fail to upscale due to out of memory or too long runtime.

In the second part of this dissertation, we propose a novel graph upscaling method called EvoGraph that can upscale the original graph with preserving its properties regardless of a scale factor. It determines and attaches new edges to the real graph using the preferential attachment mechanism in an effective and efficient way. Through extensive experiments, we have demonstrated that EvoGraph significantly outperforMaster the state-of-the-art graph upscaling method Gscaler in terMaster of preserving graph properties and performance measures such as runtime, memory usage, and scalability.

In summary, we have proposed new methods for synthesizing graph database that overcomes most of drawbacks of existing methods. For the synthetic graph generation, i.e., RMAT and Kronecker, we have proposed TrillionG that can generate even a trillion-scale graph only using several commodity machines. For the graph upscaling from a given real graph, we propose a novel graph upscaling method EvoGraph that can preserve major structural properties of the original graph. We believe that the proposed methods can solve a challenging issue with the lack of large-scale graph datasets in terMaster of size and properties.|많은 응용 프로그램이 그래프 크기의 기하 급수적인 증가를 마주하면서, 그래프 처리 방법들의 성능을 측정을 위한 빠르면서 규모확장성있는 그래프 생성 방법이 매우 중요해지고 있다. 합성 그래프들을 생성하는 많은 방법들이 제안되었지만, 이들은 공간 및 시간 복잡도 측면에서 매우 효율적이지 못하고, 통상의 머신들로 구성된 보통 크기의 클러스터를 사용해서 조 단위 그래프를 생성하지 못한다. 이에 본 학위논문에서는 기존의 방법들의 단점을 극복한 효율적이고 효과적인 새로운 방법을 제한한다.

본 학위논문의 첫 번째 부분에서는 적은 메모리만을 사용해서 짧은 시간안에 대규모의 그래프를 생성할 수 있는 효율적이고 규모확장성있는 디스크 기반의 그래프 생성 방법인 TrillionG를 제안하였다. 본 방법은 RMAT 모델이나 Kronecker 모델을 따르는 1 조개의 간선을 가지는 그래프를 단 10대의 PC만을 사용하여 2시간 안에 생성할 수 있다. 먼저 기존의 그래프 생성 모델인 RMAT와 Kronecker가 두 가지 극단에 해당하도록 스코프 기반 생성 모델로 일반화했다. 그런다음 두 극단의 중간지점에 위치한 재귀적 벡터 모델 이라는 새로운 그래프 생성 모델을 제안하고, 기존의 RMAT 및 Kronecker에서의 공간 및 시간 복잡도 문제를 해결하였다. 또한 시멘틱이 풍부한 그래프 데이터베이스를 생성하 기위해 재귀적 벡터 모델을 확장했다. 광범위한 실험을 통해 TrillionG가 최신의 그래프 생성기보다 최대 수백배 이상 성능을 능가 함을 보였다.

많은 연구자 및 산업 그룹은 다양하면서도 대규모인 실제 그래프의 부족으로 많 은 어려움을 겪고 있다. RMAT 및 BA 모델같은 많은 그래프 생성 방법이 개발되었지만, 이들의 결과 그래프는 그래프 특성 측면에서 실제 그래프들과 상당히 다른 경향을 보인다. Gscaler같은 몇 몇의 그래프 증폭 방법이 있지만, 이들은 원본 그래프의 중요한 특성들을 보존하지 못하고, 메모리 초과나 매우 긴 실행시간으로 인해 실패한다.

본 학위논문의 두 번째 부분에서는 규모 증폭 수치에 상관없이 원본 그래프의 특성을 보존하면서 원본 그래프를 증폭할 수 있는 새로운 그래프 증폭 방법 EvoGraph 을 제안했다. 이 방법은 선호적 연결 메커니즘을 사용하여 효과적이고 효율적으로 실제 그래프에 새로운 간선을 결정하고 연결한다. 광범위한 실험을 통해 EvoGraph는 런타임, 그래프 특성 보존 측면과 메모리 사용 및 확장성같은 성능 측면 모두에서 최신의 그래프 증폭 방법인 Gscaler보다 월등히 뛰어나다는 것을 입증했다.

요약하여, 본 학위논문에서는 기존 방법들의 단점의 대부분을 극복한 그래프 데 이터베이스 합성 방법에 대한 새로운 방법들을 제안하였다. RMAT과 Kronecker같은 합성 그래프 생성 방법에 대해서, 단 몇대의 통상적인 머신을 이용하여 조 단위 규모까지도 생 성할 수 있는 TrillionG를 제안했다. 주어진 실제 그래프로부터 그래프 증폭하는 방법에 대해서, 원본 그래프의 주요 구조적 특성들을 유지할 수 있는 새로운 그래프 증폭 방법인 EvoGraph를 제안했다. 제안된 방법은 크기와 특성면에서 큰 규모의 그래프 데이터셋들의 부족에 관한 도전적인 문제들을 해결할 수 있을 것이라고 사료된다.