EvoGraph: An Effective And Efficient Graph Upscaling Method For Preserving Graph Properties

Authors:
Himchan Park DGIST
Min-Soo Kim DGIST

Introduction:

This paper studies synthetic graph generation methods. The authors propose a novel graph upscaling method called EvoGraph that can upscale the original graph with preserving its properties regardless of a scale factor.

Abstract:

Nowadays, 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 BA have been developed, their output graphs tend to be quite different from real-world graphs in terms 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 this paper, 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 outperforms the state-of-the-art graph upscaling method Gscaler in terms of preserving graph properties and performance measures such as runtime, memory usage, and scalability.

You may want to know: