CGS Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support

Jul 16, 2026

CGS (Configurable Graph Summarizer) addresses large-scale graph summarization by producing a compact, user-configurable summary graph that supports multiple graph queries with either no loss or high-accuracy results. The framework aggregates nodes with common neighborhoods and offers variants CGS-E (lossless), CGS-I and CGS-U (lossy). A user-defined neighborhood-loss tolerance threshold bounds reconstruction loss around each node, enabling neighborhood query evaluation with no loss or controlled loss, validated via experiments on synthetic and real-world graphs with improved summarization and efficient query answering.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages44

Reading Time1 h 51 min

Introduction

Background and Motivation

arXiv :2607 . 10969v 1 [ cs .DS] 13 Jul 2026 CGS: Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support SHUBHADIP MITRA, Blue Yonder India Pvt. Ltd., India SONA ELZA SIMON, Centre for Machine Intelligence and Data Science, Indian Institute of Technology Bombay, India C OSWALD, Dept. of Computer Science and Engineering, National Institute of Technology Tiruchirappalli, India ARNAB BHATTACHARYA, Dept. of Computer Science and Engineering, Indian Institute of Technology Kanpur, India ARINDAM PAL, TechSoftX Corporation, Australia Given a large graph, how to generate a compact summary graph that is configurable by the user and supports multiple graph queries with either no loss or with high accuracy? The ever growing size of graph datasets makes the above question on graph summarization very pertinent. Although, there are several approaches, there does not exist a configurable graph summarization method that offers high compression along with support for multiple graph queries on the summary graph with high accuracy, and allows the user to configure the summarization based on: (1) lossless or lossy summarization,(2) amount of tolerable neighborhood loss,(3) the type of loss it can tolerate, in terms of false positive edges (i.e., extra edges), false negative edges (i.e., missing edges), or neither, in both the (a) reconstructed graph and the (b) query answers. To overcome these limitations, we propose a novel graph summarization framework CGS (Configurable Graph Summarizer) that builds upon the idea of aggregating nodes with common neighborhoods. The CGS framework consists of three summarization variants, CGS-E, CGS-I and CGS-U. While CGS-E is a lossless scheme, CGS-I and CGS-U are lossy schemes that allow reconstruction of the input graph with no false positive edges and no false negative edges, respectively. To bound the graph reconstruction loss, we introduce a user-specified parameter neighborhood loss tolerance threshold, that limits the maximum loss allowed in the neighborhood of each node. This allows graph reconstruction and neighborhood query evaluation with either no loss or with bounded loss guarantees. This, in turn, enables retrieval of multiple graph queries such as shortest path and reachability queries with either no loss or with fairly high accuracy. Empirical evaluation on several synthetic and real-world graphs shows that CGS offers superior summarization than the state-of-the-art methods, and can answer graph queries with fairly high accuracy and efficiency. The implementation code and the datasets are available at [https://github.com/sonaelzasimon/CGS_Configurable_Graph_Summarization](https://github.com/sonaelzasimon/CGS_Configurable_Graph_Summarization). CCS Concepts: • Information systems → Data compression; Graph-based database models. Additional Key Words and Phrases: Graph Summarization, Graph Compression, Web Graphs, Social Networks, Common Neighborhoods Authors’ Contact Information: Shubhadip Mitra, Blue Yonder India Pvt. Ltd., Bengaluru, India, shubhadip.mitra@blueyonder. com; Sona Elza Simon, Centre for Machine Intelligence and Data Science, Indian Institute of Technology Bombay, Mumbai, India, [sonasimonp@gmail.com](sonasimonp@gmail.com); C Oswald, Dept. of Computer Science and Engineering, National Institute of Technology Tiruchirappalli, Tiruchirapalli, India, [oswald@nitt.edu](oswald@nitt.edu); Arnab Bhattacharya, Dept. of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India, [arnabb@cse.iitk.ac.in](arnabb@cse.iitk.ac.in); Arindam Pal, TechSoftX Corporation, Sydney, New South Wales, Australia, [arindamp@gmail.com](arindamp@gmail.com). This work is licensed under a Creative Commons Attribution 4 .0 International License. © 2025 Copyright held by the owner/author(s) . ACM 1556-472X/2025/0-ART0 [https://doi.org/10.1145/3786788](https://doi.org/10.1145/3786788) ACM Trans. Knowl. Discov. Data., Vol. 0, No. 0, Arti

FAQs

What user-configurable choices does CGS provide for graph summarization quality?

CGS allows selecting lossless or lossy summarization, specifying a neighborhood loss tolerance threshold, and controlling the type of neighborhood reconstruction loss to tolerate with respect to false positive and false negative edges.

How does CGS-E differ from CGS-I and CGS-U?

CGS-E is a lossless scheme that reconstructs the input graph without loss. CGS-I and CGS-U are lossy variants designed so the reconstruction avoids false positive edges and false negative edges, respectively.

How does the neighborhood loss tolerance threshold affect query answering?

The threshold bounds the maximum loss allowed in each node’s neighborhood, which in turn yields either lossless neighborhood query evaluation or bounded-loss neighborhood query evaluation, enabling queries like shortest path and reachability with fairly high accuracy.

Jul 16, 2026

Upload by Genevieve