POLIGRAS: Policy-based Graph Summarization

Download PDF

Abstract

Large graphs are ubiquitous. Their sizes, rates of growth, and complexity, however, have significantly outpaced human capabilities to ingest and make sense of them. As a cost-effective graph simplification technique, graph summarization is aimed to reduce large graphs into concise, structure-preserving, and quality-enhanced summaries readily available for efficient graph storage, processing, and visualization. Concretely, given a graph 𝐺 , graph summarization condenses 𝐺 into a succinct representation comprising (1) a supergraph with supernodes representing disjoint sets of vertices of 𝐺 and superedges depicting aggregate-level connections between supernodes, and (2) a set of correction edges that help reconstruct 𝐺 losslessly from the supergraph. Existing graph summarization solutions offer non-optimal graph summaries and are time-demanding in real-world large graphs. In this paper, we propose a learning-enhanced graph summarization approach, Poligras (Policy-based graph summarization), to model the most critical computational component in graph summarization: supernode selection and merging. Specifically, we design a probabilistic policy learned and optimized by neural networks for efficient optimal supernode pair selection. As the first learning-enhanced, scalable graph summarization method, Poligras achieves significantly improved performance over state-of-the-art graph summarization solutions in real-world large graphs.