🤖 AI

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

This paper proposes CGS, a novel configurable graph summarization framework that aggregates nodes with common neighborhoods to generate compact summaries supporting multiple graph queries with either lossless results or bounded neighborhood loss, while allowing users to customize tolerable error types and thresholds.

Original authors: Shubhadip Mitra, Sona Elza Simon, C Oswald, Arnab Bhattacharya, Arindam Pal

Published 2026-07-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Shubhadip Mitra, Sona Elza Simon, C Oswald, Arnab Bhattacharya, Arindam Pal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, chaotic city map with millions of streets and intersections. Trying to study the whole thing at once is overwhelming; it takes up too much memory, and finding a specific route is a nightmare. You want a smaller, simplified version of the map that still helps you navigate, but you don't want to lose your way.

This is exactly the problem the authors of this paper are tackling with a new tool called CGS (Configurable Graph Summarizer). They treat a complex network (like a social media friend list or a web of connections) as a giant map and try to shrink it down into a "summary map" that is easy to carry but still accurate enough to answer questions like "Who are my friends?" or "What's the fastest way to get from A to B?"

The Big Idea: Grouping Neighbors

The core trick of CGS is like grouping people at a party who know the exact same group of friends. If Alice and Bob both know Charlie, Dave, and Eve, but don't know anyone else in common, CGS says, "Hey, let's glue Alice and Bob together into a single 'Super-Person'."

When you do this, you save space because you don't need to list all those shared connections twice. However, gluing people together creates a risk: you might accidentally invent a connection that didn't exist (a "false positive," like thinking Alice knows Frank when she doesn't) or lose a connection that did exist (a "false negative," like forgetting that Bob knows Frank).

The Three Flavors of CGS

The paper argues that one size doesn't fit all. Depending on what you need, you might want to be super strict, or you might be okay with a little wiggle room. That's why they built three different versions of their tool:

CGS-E (The Perfectionist): This version is lossless. It promises that when you un-glue the Super-Persons later, you get the exact original map back. No extra streets, no missing streets. It's like a perfect photocopy that just happens to be folded up smaller.
CGS-I (The Intersection): This is a lossy version designed to avoid false positives (fake edges). It guarantees that it will never invent a connection that didn't exist in the original graph. However, to achieve this, it may omit some real connections (allowing false negatives). The amount of missing information is controlled by a "tolerance knob." Think of it as a map that might leave out a few side streets, but every road it shows is definitely real. This is great for things like route navigation, where you don't want to be sent down a road that doesn't exist.
CGS-U (The Union): This is the other lossy version designed to avoid false negatives (missing edges). It guarantees that it won't miss any real connections that existed in the original graph. However, to ensure this, it might add a few extra, fake connections (allowing false positives). It's like a map that shows every possible path, even some that are just shortcuts through a neighbor's yard. This is perfect for friend recommendations, where you'd rather be shown a potential friend you don't know than miss a real one.

The "Safety Net" (Bounded Loss)

The authors realized that sometimes you need to be flexible. They introduced a "tolerance knob" (called a neighborhood loss threshold). You can tell the tool, "It's okay if I lose up to 25% of the details for this specific person, but for that other person, I need 100% accuracy."

This allows the tool to be configurable. You can decide how much error you can tolerate. The paper shows through experiments on real-world data (like the YouTube network with over 1 million users) and synthetic data that this approach works. They found that by tuning this knob, they could shrink the map significantly while still keeping the answers to questions like "Who can I reach?" or "What's the shortest path?" very accurate.

What They Rejected

The paper is very clear about what doesn't work well for their goals. They argue against methods that:

Don't let you choose the type of error: Some old tools just give you a mix of missing and fake edges, and you can't control which one you get. CGS says, "You should be able to choose: do you want to avoid fake edges, or do you want to avoid missing edges?"
Can't answer questions without un-folding the whole map: Many compression methods force you to completely rebuild the giant original map just to ask a simple question. CGS is designed so you can ask questions (like "Is there a path between these two?") directly on the small summary map, or by only "un-folding" the tiny part you need.
Are too rigid: They reject the idea that you must always have a perfect, lossless map. Sometimes, a slightly smaller map with a tiny bit of error is much more useful.

How Sure Are They?

The authors didn't just guess; they tested this extensively.

Measured Results: They ran their code on 10 real-world datasets (like DBLP, LiveJournal, and Email-Enron) and synthetic graphs.
The Numbers: On real graphs, their lossless version (CGS-E) compressed the data better than the best existing tools by up to 27% (on the LiveJournal dataset) and 41% (on the CA-AstroPh dataset).
Accuracy: For the lossy versions, they showed that even when they allowed a 50% loss tolerance, the actual average error was often much lower (around 0.18 to 0.26 depending on the dataset).
Query Performance: They measured how fast the queries ran. They found that while looking at the small summary map is slightly slower than looking at the full map (because the computer has to do a little "local un-folding"), it's still very fast—neighborhood queries take microseconds, and shortest path queries take milliseconds.

The Trade-Off

The paper admits that CGS takes a bit longer to build the summary map than some other methods (it can take minutes to hours for huge graphs). However, they argue this is a fair trade because summarization is usually a one-time job done offline, and the resulting map is so much better at answering questions and saving space.

In short, the authors suggest that by letting users choose how they want to lose information (or not lose it at all) and by controlling how much they are willing to lose, CGS creates a smarter, more flexible way to shrink giant networks without breaking them.

Technical Summary: CGS - Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support

1. Problem Statement

The paper addresses the challenge of managing the ever-increasing size of graph datasets, which hinders scalability in storage, communication, and analysis. While existing graph summarization methods exist, they suffer from a lack of configurability and limited support for queries on the summary graph without full decompression. Specifically, prior works fail to offer a unified framework that allows users to:

Choose between lossless and lossy summarization.
Control the amount of tolerable neighborhood loss.
Specify the type of loss tolerated (False Positive edges, i.e., extra edges; or False Negative edges, i.e., missing edges) in the reconstructed graph or query answers.
Support multiple graph queries (neighborhood, reachability, and shortest path) directly on the summary graph with high accuracy.

The authors define the Configurable Graph Summarization (ConfiGS) problem: Given an undirected, unweighted graph $G$ , a summarization variant parameter, and a neighborhood loss tolerance threshold set $\Delta$ , design a scheme that minimizes the compression ratio while ensuring the reconstructed graph satisfies the neighborhood loss constraints and supports query processing.

2. Methodology: The CGS Framework

The proposed CGS (Configurable Graph Summarizer) framework is based on the aggregation of nodes that share common neighborhoods. It employs a greedy iterative approach to merge node pairs that offer the maximum compression gain, subject to safety constraints defined by the user's loss tolerance.

2.1 Summarization Variants

The framework offers three distinct variants, characterized by how they handle edge reconstruction:

CGS-E (Exact): A lossless scheme. It ensures the reconstructed graph $G_r$ is identical to the input graph $G$ ( $E_r = E$ ). No false positives or false negatives are introduced.
CGS-I (Intersection): A lossy scheme that allows only False Negative edges (missing edges). It ensures $E_r \subseteq E$ . The neighborhood of a node in the reconstructed graph is the intersection of the neighborhoods of the merged nodes.
CGS-U (Union): A lossy scheme that allows only False Positive edges (extra edges). It ensures $E_r \supseteq E$ . The neighborhood of a node in the reconstructed graph is the union of the neighborhoods of the merged nodes.

2.2 Core Algorithm

The algorithm operates in iterations:

Discovery: It identifies all pairs of nodes $(u, v)$ where $v$ is a 2-hop neighbor of $u$ (eligible for merging) and calculates the compression gain ($cg$) for each pair. The gain is derived from the reduction in space required to store the graph (nodes and edges) minus the overhead of storing parent-child relationships for supernodes.
Selection: A binary max-heap is used to select the pair with the maximum compression gain.
Safety Check: For lossy variants (CGS-I and CGS-U), the algorithm checks if merging the selected pair violates the neighborhood loss tolerance threshold ( $\delta_u$ ) for any node. This check is performed without full reconstruction by tracking the "ancestors" of supernodes and estimating the potential degree changes in the reconstructed graph.
Execution: If the merge is safe (or if using the lossless variant), the nodes are merged into a supernode, and the graph structure is updated. The process repeats until no further safe merges with positive gain exist.

2.3 Query Processing

The framework supports querying the summary graph ( $G_s$ ) via two modes:

Local Decompression: Queries are answered directly on $G_s$ by decompressing only the necessary local neighborhoods (ancestors and descendants) to compute the result. This avoids the overhead of reconstructing the entire graph.
Global Decompression: The full graph $G_r$ is reconstructed, and queries are run on it.

The paper establishes theoretical bounds for query accuracy:

CGS-E: Exact answers for all queries.
CGS-I: Neighborhoods are subsets of the original ( $N_{G_r} \subseteq N_G$ ); reachability is a subset ( $R_{G_r} \subseteq R_G$ ); shortest path distances are greater than or equal to the original ( $d_{G_r} \ge d_G$ ).
CGS-U: Neighborhoods are supersets ( $N_{G_r} \supseteq N_G$ ); reachability is preserved exactly ( $R_{G_r} = R_G$ ); shortest path distances are less than or equal to the original ( $d_{G_r} \le d_G$ ).

3. Key Contributions

Configurable Framework: Introduction of the ConfiGS problem and the CGS solution, which uniquely allows users to configure the type of loss (FP vs. FN) and the magnitude of loss (bounded by $\delta$ ).
Three Variants: The definition and implementation of CGS-E, CGS-I, and CGS-U, providing one-sided error guarantees suitable for different application needs (e.g., avoiding false positives in route navigation vs. avoiding false negatives in friend recommendations).
Bounded Neighborhood Loss: The introduction of a user-specified parameter ( $\delta$ ) that guarantees the neighborhood loss for every node remains within a specified bound, enabling bounded quality guarantees for queries.
Query Support without Full Decompression: The development of local decompression techniques to answer neighborhood, reachability, and shortest path queries directly on the summary graph.
Theoretical Analysis: Proofs of correctness regarding the reconstruction properties and time complexity analysis of the algorithms.

4. Experimental Results

The authors evaluated CGS on 10 real-world datasets (e.g., YouTube, DBLP, LiveJournal) and synthetic datasets (Barabási-Albert and Erdős-Rényi models), comparing against state-of-the-art baselines like SWeG, SLUGGER, MoSSo, GraphZip, and SSumM.

Compression Ratio:
- Lossless (CGS-E): Outperformed all lossless baselines (SLUGGER, MoSSo, SWeG, GraphZip) by up to 41% on real-world graphs, particularly on denser graphs.
- Lossy (CGS-I/CGS-U): CGS-I generally outperformed the lossy baseline SSumM on denser real-world graphs (up to 46% smaller summaries). On synthetic graphs, CGS-U often provided the best compression.
Reconstruction Error: CGS-I achieved lower or similar reconstruction errors compared to SSumM across datasets.
Query Accuracy:
- Neighborhood Queries: The average neighborhood loss was significantly lower than the maximum allowed threshold $\delta$ (e.g., at $\delta=0.5$ , average loss was often $<0.25$ ).
- Shortest Path: A high percentage of queries (>80%) returned exact shortest path lengths even with lossy summarization.
- Reachability: CGS-U maintained 100% accuracy for reachability queries. CGS-I showed high accuracy that decreased slightly as $\delta$ increased.
Scalability: The framework is practical for large-scale graphs (millions of edges), with compression times ranging from minutes to hours. While compression times are higher than some baselines, the authors note that summarization is typically an offline activity.

5. Significance and Claims

The paper claims that CGS represents a significant advancement because it is the first general-purpose framework to simultaneously offer:

High compression ratios.
Configurable loss types (FP vs. FN) and magnitudes.
Support for multiple query types on the summary graph without requiring full decompression.

The authors emphasize that no single variant (E, I, or U) is universally superior; the choice depends on the specific application's tolerance for false positives versus false negatives. For instance, a friend recommendation system might prefer CGS-U (tolerating extra edges but missing none), while a route navigation system might prefer CGS-I (tolerating missing edges but avoiding false routes). The framework's ability to adapt to these specific constraints while maintaining bounded error guarantees is its primary contribution.

The paper concludes by noting that future work will focus on extending the framework to handle dynamic and streaming graphs.