# CGS: Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support

arXiv: https://arxiv.org/abs/2607.10969 · HTML: https://mlsanity.com/paper/2607.10969/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 74 references that are in the map.
- First posted on arXiv 13 Jul 2026.

## Builds on (most cited first, 18 of 18)

- [Condensing Graphs via One-Step Gradient Matching](https://mlsanity.com/paper/2206.07746/) (2022)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Graph Coarsening with Preserved Spectral Properties](https://mlsanity.com/paper/1802.04447/) (2018)
- [Graph Sparsification via Mixture of Graphs](https://mlsanity.com/paper/2405.14260/) (2024)
- [Graph Summarization Methods and Applications: A Survey](https://mlsanity.com/paper/1612.04883/) (2016)
- [Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations](https://mlsanity.com/paper/1806.01799/) (2018)
- [Slim Graph: Practical Lossy Graph Compression for Approximate Graph Processing, Storage, and Analytics](https://mlsanity.com/paper/1912.08950/) (2019)
- [SSumM: Sparse Summarization of Massive Graphs](https://mlsanity.com/paper/2006.01060/) (2020)
- [VoG: Summarizing and Understanding Large Graphs](https://mlsanity.com/paper/1406.3411/) (2014)
- [Incremental Lossless Graph Summarization](https://mlsanity.com/paper/2006.09935/) (2020)
- [Scalable Approximation Algorithm for Graph Summarization](https://mlsanity.com/paper/1806.03936/) (2018)
- [Graph Summarization](https://mlsanity.com/paper/2004.14794/) (2020)
- [A Survey on Methods and Systems for Graph Compression](https://mlsanity.com/paper/1504.00616/) (2015)
- [Utility-Based Graph Summarization: New and Improved](https://mlsanity.com/paper/2006.08949/) (2020)
- [GraphGuess: Approximate Graph Processing System with Adaptive Correction](https://mlsanity.com/paper/2104.10039/) (2021)
- [SLUGGER: Lossless Hierarchical Summarization of Massive Graphs](https://mlsanity.com/paper/2112.05374/) (2021)
- [Sparsifying Cayley Graphs on Every Group](https://mlsanity.com/paper/2508.08078/) (2025)
- [Multi-view Graph Condensation via Tensor Decomposition](https://mlsanity.com/paper/2508.14330/) (2025)

## Abstract (arXiv)

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. 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.