DPGS: Degree-Preserving Graph Summarization

Abstract

Given a large graph, how can we summarize it with fewer nodes and edges while maintaining its key properties, e.g. node degrees and graph spectrum? As a solution, graph summarization, which aims to find the compact representation for optimally describing and reconstructing a given graph, has received much attention, and numerous methods have been developed for it. However, many existing methods adopt the uniform reconstruction scheme, which is an unrealistic assumption as most real-world graphs have highly skewed node degrees, even within communities. Therefore we propose a degree-preserving graph summarization model, DPGS, with a novel reconstruction scheme based on the configuration model. To optimize the Minimum Description Length of our model, we deisgn a linearly scalable algorithm using hashing techniques. We theoretically show that the minimized reconstruction error bounds the perturbation of graph spectral information. Extensive experiments on real-world datasets show that DPGS yields more accurate summary graphs than several well-known baselines. Moreover, our reduced summary graphs can effectively train graph neural networks (GNNs) while saving computational cost.