EvoGraph: An Effective and Efficient Graph Upscaling Method for Preserving Graph Properties

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.

References

1. Leman Akoglu and Christos Faloutsos . 2009. RTG: a recursive realistic graph generator using random typing Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 13--28.
2. Albert-László Barabási and Réka Albert . 1999. Emergence of scaling in random networks. science, Vol. 286, 5439 (1999), 509--512.
3. Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos . 2004. R-MAT: A Recursive Model for Graph Mining.. In SDM, Vol. Vol. 4. SIAM, 442--446.
4. Avery Ching, Sergey Edunov, Maja Kabiljo, Dionysios Logothetis, and Sambavi Muthukrishnan . 2015. One trillion edges: graph processing at Facebook-scale. VLDB, Vol. 8, 12 (2015), 1804--1815.
5. Sergey Edunov, Dionysios Logothetis, Cheng Wang, Avery Ching, and Maja Kabiljo . 2016. Darwini: Generating realistic large-scale social graphs. arXiv preprint arXiv:1610.00664 (2016).
6. Nicole Eikmeier and David F Gleich . 2017. Revisiting Power-law Distributions in Spectra of Real World Networks Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 817--826.
7. Paul ErdHos and Alfréd Rényi . 1959. On random graphs. Publicationes Mathematicae Debrecen Vol. 6 (1959), 290--297.
8. Li Gao, Jia Wu, Hong Yang, Zhi Qiao, Chuan Zhou, and Yue Hu . 2016. Semi-Data-Driven Network Coarsening.. In IJCAI. 1483--1489.
9. Graph500 . 2017. Graph500 Benchmark. (2017). http://www.graph500.org/
10. Ali Hadian, Sadegh Nobari, Behrooz Minaei-Bidgoli, and Qiang Qu . 2016. ROLL: Fast in-memory generation of gigantic scale-free networks Proceedings of the 2016 International Conference on Management of Data. ACM, 1829--1842.
11. Min-Soo Kim, Kyuhyeon An, Himchan Park, Hyunseok Seo, and Jinwook Kim . 2016. GTS: A Fast and Scalable Graph Processing Method based on Streaming Topology to GPUs Proceedings of the 2016 International Conference on Management of Data. ACM, 447--461.
12. Tamara G Kolda, Ali Pinar, Todd Plantenga, and Comandur Seshadhri . 2014. A scalable generative graph model with community structure. SIAM Journal on Scientific Computing Vol. 36, 5 (2014), C424--C452.
13. Jurij Leskovec, Deepayan Chakrabarti, Jon Kleinberg, and Christos Faloutsos . 2005 a. Realistic, mathematically tractable graph generation and evolution, using Kronecker multiplication. PKDD. Springer, 133--145.
14. Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani . 2010. Kronecker graphs: An approach to modeling networks. JMLR Vol. 11 (2010), 985--1042.
15. Jure Leskovec and Christos Faloutsos . 2006. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 631--636.
16. Jure Leskovec, Jon Kleinberg, and Christos Faloutsos . 2005 b. Graphs over time: densification laws, shrinking diameters and possible explanations Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. ACM, 177--187.
17. Steffen Maass, Changwoo Min, Sanidhya Kashyap, Woonhak Kang, Mohan Kumar, and Taesoo Kim . 2017. Mosaic: Processing a trillion-edge graph on a single machine Proceedings of the Twelfth European Conference on Computer Systems. ACM, 527--543.
18. Himchan Park and Min-Soo Kim . 2017. TrillionG: A Trillion-scale Synthetic Graph Generator using a Recursive Vector Model Proceedings of the 2017 ACM International Conference on Management of Data. ACM, 913--928.
19. SNAP . 2017. Stanford Network Analysis Project. (2017). http://snap.stanford.edu/
20. Christian L Staudt, Aleksejs Sazonovs, and Henning Meyerhenke . 2014. Networkit: An interactive tool suite for high-performance network analysis. arXiv preprint arXiv:1403.3005 (2014).
21. Duncan J Watts and Steven H Strogatz . 1998. Collective dynamics of 'small-world'networks. nature, Vol. 393, 6684 (1998), 440--442.
22. Ming Wu, Fan Yang, Jilong Xue, Wencong Xiao, Youshan Miao, Lan Wei, Haoxiang Lin, Yafei Dai, and Lidong Zhou . 2015. G ra M: scaling graph computation to the trillions Proceedings of the Sixth ACM Symposium on Cloud Computing. ACM, 408--421.
23. JW Zhang, Anwesha Mal, and YC Tay . 2017. GscalerCloud: A Web-Based Graph Scaling Service. Data Engineering (ICDE), 2017 IEEE 33rd International Conference on. IEEE, 1391--1392.
24. JW Zhang and YC Tay . 2016 a. Dscaler: Synthetically scaling a given relational database. Proceedings of the VLDB Endowment Vol. 9, 14 (2016), 1671--1682.
25. JW Zhang and YC Tay . 2016 b. GSCALER: Synthetically Scaling A Given Graph.. EDBT. 53--64.
26. Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma . 2016. Gemini: A Computation-Centric Distributed Graph Processing System. OSDI. 301--316.