Efficient Learning-based Community-Preserving Graph Generation

Abstract

Graph generation is beneficial to comprehend the creation of meaningful structures of networks in a broad spec-trum of applications such as social networks and biological net-works. Recent studies tend to leverage deep learning techniques to learn the topology structures in graphs. However, we notice that the community structure, which is one of the most unique and prominent features of the graph, cannot be well captured by the existing graph generators. Moreover, the existing advanced deep learning-based graph generators are not efficient and scalable, which can only handle small graphs. In this paper, we propose a novel community-preserving generative adversarial network (CPGAN) for effective and efficient (scalable) graph simulation. We employ graph convolution networks in the encoder and share parameters in the generation process to transmit information about community structures and preserve the permutation-invariance in CPGAN. We conducted extensive experiments on benchmark datasets, including six sets of real-life graphs. The results demonstrate that CPGAN can achieve a good trade-off between efficiency (scalability) and graph simulation quality for real-life graph simulation compared with state-of-the-art baselines.

Sheng Xiang

Ph.D. Candidate

My research interests include learning-based graph simulation for data management and spatio-temporal and uncertain data mining.