Jiyang Bai, a PhD candidate in the Computer Science department, under the guidance of Dr. Peixiang Zhao, has recently made a significant contribution to large-scale graph summarization by publishing their work in the 50th International Conference on Very Large Databases (VLDB’24), which will be held in Guangzhou China in late August, 2024. This research paper is titled “Poligras: Policy-based Graph Summarization”.
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 an effective graph simplification technique, graph summarization is aimed to reduce large graphs into concise, structure-preserving, and quality-enhanced summaries readily available for efficient and cost-effective 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 only provide non-optimal graph summaries, and are time demanding in real-world large graphs. In this work, 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. We design a probabilistic policy that is 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 than state-of-the-art graph summarization solutions in real-world large graphs.
It is worth noting that this is the second VLDB paper published by Jiyang. In 2022, his work “TaGSim: Type-aware Graph Similarity Learning and Computation” was accepted by VLDB’22, and presented in Sydney, Australia.