Paper deep dive
CGS: Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support
Shubhadip Mitra, Sona Elza Simon, C Oswald, Arnab Bhattacharya, Arindam Pal
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/18/2026, 1:45:07 PM
Summary
The paper introduces CGS (Configurable Graph Summarizer), a framework for generating compact, configurable graph summaries that support multiple graph queries (neighborhood, shortest path, reachability) with bounded or no loss. It offers three variants: CGS-E (lossless), CGS-I (lossy, no false positives), and CGS-U (lossy, no false negatives), utilizing a neighborhood loss tolerance threshold to control reconstruction error.
Entities (10)
Relation Signals (14)
CGS-E → istype → Lossless
confidence 98% · While CGS-E is a lossless scheme
CGS → hasvariant → CGS-I
confidence 95% · The CGS framework consists of three summarization variants, CGS-E, CGS-I and CGS-U.
CGS → hasvariant → CGS-E
confidence 95% · The CGS framework consists of three summarization variants, CGS-E, CGS-I and CGS-U.
CGS → hasvariant → CGS-U
confidence 95% · The CGS framework consists of three summarization variants, CGS-E, CGS-I and CGS-U.
CGS-I → istype → Lossy
confidence 95% · CGS-I and CGS-U are lossy schemes
CGS-U → istype → Lossy
confidence 95% · CGS-I and CGS-U are lossy schemes
CGS-U → prevents → False Negative Edges
confidence 95% · CGS-U... allows only false positive edges, but no false negative edges
CGS-I → prevents → False Positive Edges
confidence 95% · CGS-I... allows only false negative edges, but no false positive edges
CGS → usesparameter → Neighborhood Loss Tolerance Threshold
confidence 95% · we introduce a user-specified parameter neighborhood loss tolerance threshold
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2607.10969v1
- Canonical: https://arxiv.org/abs/2607.10969v1
Trouble viewing inline? Open PDF directly →
Full Text
158,533 characters extracted from source content.
Expand or collapse full text
by CGS: Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support Shubhadip Mitra 0000-0002-0444-9652 Blue Yonder India Pvt. Ltd.BengaluruIndia shubhadip.mitra@blueyonder.com , Sona Elza Simon 0000-0001-5136-7273 Centre for Machine Intelligence and Data Science, Indian Institute of Technology BombayMumbaiIndia sonasimonp@gmail.com , C Oswald 0000-0002-1251-1495 Dept. of Computer Science and Engineering, National Institute of Technology TiruchirappalliTiruchirapalliIndia oswald@nitt.edu , Arnab Bhattacharya 0000-0001-7331-0788 Dept. of Computer Science and Engineering, Indian Institute of Technology KanpurKanpurIndia arnabb@cse.iitk.ac.in and Arindam Pal 0000-0001-5710-7464 TechSoftX CorporationSydneyNew South WalesAustralia arindamp@gmail.com (24th October, 2025) Abstract. 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. Graph Summarization, Graph Compression, Web Graphs, Social Networks, Common Neighborhoods †copyright: c†journalyear: 2025†doi: 10.1145/3786788†journal: TKDD†journalvolume: 0†journalnumber: 0†article: 0†publicationmonth: 0†ccs: Information systems Data compression†ccs: Information systems Graph-based database models 1. Introduction One of the key challenges in graph data mining is the ever increasing size of the graphs that prohibits its scalability in terms of storage, communication and analysis. To address this challenge, several graph summarization schemes have been proposed (Navlakha et al., 2008; Khan et al., 2017; Lee et al., 2022; Lai et al., 2023) that generate a compact summary of a graph that allows reconstruction of the original graph with minimal or no loss. A summary graph is typically produced by aggregation of nodes and edges of the input graph. Due to its numerous applications (Liu et al., 2018), graph summarization has remained an area of active research for the past two decades. 1.1. Background and Motivation A graph summarization scheme is defined as follows. An input graph G is summarized to a graph GsG_s that is later decompressed or expanded to produce a graph GrG_r, which is referred to as the reconstructed graph. A graph summarization scheme (along with its corresponding reconstruction) is said to be lossless if and only if Gr=G_r=G; else, it is lossy. Though there are several graph summarization works, most of them lack configurability as required by the user with no or limited support for queries. They are either lossless (Lee et al., 2022; Khan et al., 2015; Fan et al., 2012; Lai et al., 2023; Berberidis et al., 2022; Ramezani et al., 2022), or lossy (Emamzadeh Esmaeili Nejad et al., 2021; Li et al., 2019; Lee et al., 2020; Anagnostopoulos et al., 2024). There are limited works that allow both lossless as well as lossy summarization (Shin et al., 2019; Navlakha et al., 2008). Moreover, majority of the lossy summarization schemes do not allow the user to control the loss (Emamzadeh Esmaeili Nejad et al., 2021; Li et al., 2019; Yong et al., 2021; Anagnostopoulos et al., 2024; Lai et al., 2023). Hence, these works fail to provide bounded quality guarantees on queries. Further, none of the existing works allow the flexibility to choose the type of loss in terms of either false positive edges (i.e., extra edges), or false negative edges (i.e., missing edges) in the reconstructed graph. Finally, there are many works that offer good summarization but provide no support for queries (Navlakha et al., 2008; Lee et al., 2022; Yong et al., 2021; Lee et al., 2020; Lai et al., 2023; Berberidis et al., 2022). In particular, through an extensive review of the prior works (Sec. 2), we observe that there does not exist a general purpose configurable graph summarization framework that offers high compression along with all the following desirable capabilities, where the user is allowed to: (1) choose between lossless and lossy summarization, (2) control the amount of neighborhood loss that it can tolerate, (3) run graph queries on the summary graph (without decompressing it) including neighborhood queries, reachability queries and shortest path queries, and (4) specify the type of loss it can tolerate—false positive edges (i.e., extra edges) or false negative edges (i.e., missing edges)—in the reconstructed graph or query answers. In this work, we introduce the ConfiGS (Configurable Graph Summarization) problem that achieves all the above desirable properties and proposes a solution framework, CGS (Configurable Graph Summarizer). The framework offers three summarization variants: (1) CGS-E (CGS-Exact): a lossless scheme that allows neither false positive edges nor false negative edges in the reconstructed graph (2) CGS-I (CGS-Intersection): a lossy scheme that allows only false negative edges, but no false positive edges (3) CGS-U (CGS-Union): a lossy scheme that allows only false positive edges, but no false negative edges Thus, the two lossy schemes in our framework have only one-sided errors. Hence, an application can judiciously select whatever fits its requirements the best. For example, a friend recommendation application may tolerate false positive answers, but not false negative answers, while a route navigation application may tolerate false negative edges, but not false positive edges in its recommended route. The CGS framework leverages the fact that several nodes in a graph share common neighbors. Hence, nodes that share common neighbors can be aggregated into a single supernode. The exact details of the schemes are described in Sec. 4. In contrast to many prior works (Navlakha et al., 2008; Khan et al., 2015; Shin et al., 2019; Ko et al., 2020; Yong et al., 2021), this work does not use correction edges to control the reconstruction loss, which avoids the space overhead to store the correction edges. This in turn, leads to superior compression ratio, as shown in Sec. 10. 1.2. Major Contributions The key contributions of this work are as follows: (1) Configurable Graph Summarization Framework: We introduce the problem of configurable graph summarization, called ConfiGS, for summarizing large, undirected, unweighted graphs, and propose a solution framework called CGS, based on the discovery of common neighbors. The CGS framework offers three summarization variants, namely CGS-E, CGS-I and CGS-U, While CGS-E is a lossless summarization scheme, CGS-I and CGS-U are lossy summarization schemes that allow reconstruction with no false positive edges and no false negative edges, respectively. (2) Support for Multiple Graph Queries: The CGS framework can handle multiple graph queries including neighborhood queries, shortest path queries and reachability queries. Without compromising on query accuracy, the CGS framework can answer queries on the summary graph without reconstructing the input graph. To this end, it uses the concept of local decompression, explained in Sec. 6. (3) Bounded Neighborhood Loss: The lossy variants of CGS, namely, CGS-I and CGS-U, offer parameterized control to bound the neighborhood loss. More specifically, we introduce a user specified parameter, the neighborhood loss tolerance threshold, that quantifies the maximum loss allowed in the neighborhood of each node in the graph. This allows graph reconstruction and neighborhood query evaluation with either no loss or with bounded loss guarantees. This, in turn, enables retrieval of other graph queries such as shortest path and reachability queries with either no loss or with fairly high accuracy. (4) Extensive Benchmarking: Empirical evaluation on multiple synthetic and real-world graphs demonstrates that CGS offers superior summarization than the state-of-the-art methods. Moreover, it also showcases the ability of CGS to answer a wide variety of graph queries with high accuracy and efficiency. 1.3. Organization of the Article The rest of the article is organized as follows. Sec. 2 discusses the related works. Sec. 3 states the preliminary concepts and formally states the configurable graph summarization problem. The CGS framework is presented in Sec. 4 and Sec. 5. Sec. 6 describes the query processing through the proposed framework. Sec. 7 establishes the correctness of CGS. In addition, the graph properties that are necessary for summarization through the CGS framework are stated in Sec. 8. The complexity of CGS is analyzed in Sec. 9. The empirical findings are presented in Sec. 10. The conclusions and future works are discussed in Sec. 11. 2. Related Work Algorithm Type of Graph Summarization Bound on Loss Type Query Support Key Metrics Type Neighborhood Loss (FP/FN) (NQ/SPQ/RQ) CGS (this work) Undirected, Unweighted Both Yes Either FP or FN or none NQ, SPQ, RQ Compression ratio cr=|Gs||G|cr= |G_s||G| SWeG (Shin et al., 2019) Undirected, Unweighted Both Yes Both NQ Size of output =|P∗|+|C+|+|C−|=|P^*|+|C^+|+|C^-| APXMDL (Navlakha et al., 2008) Undirected, Unweighted Both Yes Not stated None Compression ratio crcr GraphZip (Rossi and Zhou, 2018) Undirected, Unweighted Both No None NQ, SPQ, RQ Space savings =1−|Gs||G|=1- |G_s||G| GSQG (Riondato et al., 2017) Undirected, Unweighted Both No None NQ Compression ratio crcr SLUGGER (Lee et al., 2022) Undirected, Unweighted Lossless Not applicable Not applicable None Encoding cost =|P+|+|P−|+|H|=|P^+|+|P^-|+|H| MoSSo (Ko et al., 2020) Undirected, Unweighted Lossless Not applicable Not applicable NQ Size of output =|Pt|+|Ct+|+|Ct−|=|P_t|+|C_t^+|+|C_t^-| SAGS (Khan et al., 2015) Undirected, Unweighted Lossless Not applicable Not applicable None Compression ratio crcr compressR (Fan et al., 2012) Directed, Weighted Lossless Not applicable Not applicable RQ Compression ratio crcr optGS (Lai et al., 2023) Undirected, Unweighted Lossless No False Positive None Compactness = |P|+|C+|+|C−||E| |P|+|C^+|+|C^-||E| LM-GSUM (Berberidis et al., 2022) Directed, Weighted Lossless Not applicable Not applicable None Compression Ratio = Bits_Before−Bits_AfterBits_Before Bits\_Before-Bits\_AfterBits\_Before NQFCSN (Maserrat and Pei, 2010) Directed, Unweighted Lossless Not applicable Not applicable NQ bits per edge rate Traverse+K2T (Emamzadeh Esmaeili Nejad et al., 2021) Undirected, Unweighted Lossy No Both NQ, RQ Compression ratio crcr StarZip (Li et al., 2019) Undirected, Unweighted Lossy No Not stated SPQ vcr=|V||Vs|vcr= |V||V_s|, ecr=|E||Es|ecr= |E||E_s| GraSS (LeFevre and Terzi, 2010) Undirected, Unweighted Lossy No Not stated NQ Reconstruction error LDME (Yong et al., 2021) Undirected, Unweighted Lossy No Not stated None Compression c=1−|P|+|C+|+|C−||E|c=1- |P|+|C^+|+|C^-||E| SSumM (Lee et al., 2020) Undirected, Weighted Lossy Yes Not stated None Reconstruction error SSAG (Ali et al., 2024) Undirected, Unweighted Lossy No Not stated None Reconstruction error GPQPS (Anagnostopoulos et al., 2024) Undirected, Weighted Lossy No Not stated SPQ Relative error GRAPHGUESS (Ramezani et al., 2022) Undirected, Unweighted Not stated Not applicable Not applicable SPQ — QMG (Nabti and Seba, 2017) Undirected, Unweighted Not stated Not applicable Not applicable No specific query Compression Rate = |E(C(G))||E(G)| |E(C(G))||E(G)| Table 1. Comparison of key related works in terms of their various properties (FP = False Positive, FN = False Negative, NQ = Neighborhood Query, SPQ = Shortest Path Query, RQ = Reachability Query) The related works can be broadly classified into two categories: (1) Graph compression methods: (Boldi and Vigna, 2004; Grabowski and Bieniecki, 2010; Liakos et al., 2014; Besta et al., 2019; Besta and Hoefler, 2018; Li et al., 2019; Maneth and Peternek, 2015; Emamzadeh Esmaeili Nejad et al., 2021) (2) Graph summarization methods: (Beg et al., 2018; Li et al., 2019; Kang et al., 2022; Ko et al., 2020; Navlakha et al., 2008; Ali et al., 2024; Lai et al., 2023; Berberidis et al., 2022; Maserrat and Pei, 2010) While the former methods attempt to produce a compressed representation of the input graph by optimizing the minimum description length (MDL) using encoding techniques to compress frequently occurring subgraphs in a graph, the latter produces a summary graph of the input graph while still retaining its key structural properties, either exactly or approximately. The former methods usually do not allow querying on the compressed graph without fully decompressing it (Boldi and Vigna, 2004; Grabowski and Bieniecki, 2010; Liakos et al., 2014). On the other hand, the summary graphs produced by some of the latter methods may support queries (Riondato et al., 2017; Shin et al., 2019; Anagnostopoulos et al., 2024). Given that graph compression methods are complementary to this work that falls in the category of graph summarization methods, the related work discussion primarily focuses on graph summarization. 2.1. Comparison of Key Related Work Table 1 presents a comparison of the key related works based on their configurable capabilities and query support. More specifically, the works have been categorized based on the type of input graph, type of summarization, i.e., lossy, lossless or both, whether the neighborhood loss is bounded, type of loss, i.e., false positive edges, false negative edges or both, support for queries on the summary graph such as neighborhood queries (NQ), reachability queries (RQ) and shortest path queries (SPQ), and the key metrics evaluated. In the table, G=(V,E)G=(V,E) refers to the input graph, Gs=(Vs,Es)G_s=(V_s,E_s) refers to the summary graph, P is the set of super edges of the summary graph GsG_s, C+C^+ is the set of edges to be inserted, C−C^- is the set of edges to be deleted, and H is the set of hierarchy edges between the supernodes. For further details on the key metrics stated in the table, please refer to the respective works. The algorithms are ordered based on their similarity to CGS. SWeG (Shin et al., 2019) is a parallel graph summarization algorithm that is designed for both shared-memory and MapReduce settings. SWeG repeats two steps: (1) dividing the input graph into small subgraphs, and (2) processing the subgraphs in parallel without having to load the entire graph in main memory. SWeG is closely related to CGS and it offers both lossy as well as lossless summarization variants, in addition to bounded loss of neighborhood and support for neighborhood queries. However, the reconstructed graph can contain both false positive as well as false negative edges. In particular, it does not allow the user to configure the type of loss in terms of its tolerance to false positive edges or false negative edges in the reconstructed graph and the neighborhood queries. Navlakha et al. (Navlakha et al., 2008) considered the problem of computing the Minimum Description Length (MDL) representation of a graph. Although this method offers bounded neighborhood loss, it does not allow any control over false positive and false negative edges in the reconstructed graph. Moreover, it does not support query processing. GraphZip (Rossi and Zhou, 2018) is based on decomposing a graph into a number of cliques of varying sizes. It does not offer any bound on the neighborhood loss. Further, evaluating on just two datasets, the authors claimed that their approach competes favorably with the Layered Label Propagation (LLP) technique (Boldi et al., 2011). GSQG (Riondato et al., 2017) is based on partitioning the original set of vertices into a small number of supernodes connected by super edges to form a complete weighted graph. To quantify the dissimilarity between the original graph and a summary, the authors optimized the reconstruction error and the cut-norm error. They developed the first polynomial-time approximation algorithms to compute the best possible summary of a certain size under both measures. However, compared with CGS, this method neither offers direct control on the neighborhood loss, nor it allows any choice of either false positive or false negative edges in the reconstructed graph and neighborhood queries. SLUGGER (Lee et al., 2022) is a lossless hierarchical summarization technique that extends the work of (Navlakha et al., 2008). Although this method is effective in summarizing massive graphs, it does not support query processing. Ko et al. (Ko et al., 2020) presented MoSSo for lossless graph summarization of fully dynamic graphs. With each edge insertion or deletion, this method moves nodes among the supernodes in the summary graph. Experimental results (Sec. 10) show that the lossless scheme of CGS, i.e., CGS-E offers considerably better summarization than both, SLUGGER and MoSSo. SAGS (Khan et al., 2015) is a set-based summarization approach that summarizes naturally occurring sets of similar nodes that are identified using locality sensitive hashing. This method, however, does not support queries. CompressR (Fan et al., 2012) is a lossless compression method designed for directed and weighted graphs. However, their approach is restricted to only two specific classes of queries, reachability and graph pattern. Traverse+K2T (Emamzadeh Esmaeili Nejad et al., 2021) is based on the transitivity property often found in social networks and web graphs. However, it has neither any bound on the neighborhood loss nor any support for answering queries. StarZip (Li et al., 2019) is a lossy compression scheme for streaming graphs. It repeatedly identifies dominating sets in a graph, and represents each such dominating set by a supernode. However, there is no control over false positive and false negative edges, or any guarantee on the neighborhood loss. GraSS (LeFevre and Terzi, 2010) is based on a random world model which does not offer any bound on the neighborhood loss. Further, this method seeks to minimize the reconstruction error rather than compression ratio. LDME (Yong et al., 2021) is a correction set based graph summarization algorithm that is based on weighted locality sensitive hashing. The algorithm allows trading compression for running time. However, there is no support to answer queries and there is no guarantee on the quality of the reconstructed graph. SSumM (Lee et al., 2020) is a sparse summarization method based on the MDL principle. This method, however lacks support for queries and focuses on reducing the reconstruction error rather than the compression ratio. The technique by Maserrat et al. (Maserrat and Pei, 2010) proposes an Eulerian data structure with multi-position linearizations to compress social networks while allowing sublinear-time in-neighbor and out-neighbor queries without decompression. Although it is interesting to see that the algorithm provides a high compression ratio along with supporting both neighbor query types and provides theoretical bounds with empirical validation, it addresses only lossless versions and focuses on neighbor queries alone. It may not generalize well to other query types, and involves complex preprocessing. On the other hand, our proposed approach CGS focuses on Neighborhood query, Reachability query and Shortest-path query. Nabti et al. (Nabti and Seba, 2017) uses modular decomposition to compress both query and data graphs, enabling subgraph isomorphism search directly on compressed graphs to reduce search space. It reduces storage and computation to some extent and is scalable to massive graphs, and avoids decompression. It is best suited with a restriction to labeled graphs with structural regularities only. Moreover, the compression quality affects query accuracy, and is not optimized for highly dynamic graphs. The work by Sarwan Ali et al. SsAG, a scalable lossy summarization method for attributed graphs that merges nodes into supernodes while minimizing reconstruction error and maximizing attribute homogeneity, followed by sparsification to reduce storage (Ali et al., 2024). Though it handles large-scale graphs incorporating both topology and attributes, summaries may have slightly higher storage cost and minor quality degradation. Moreover, they consider only the lossy type with no support for query processing. optGS (Lai et al., 2023) proposes an optimized correction set–based lossless graph summarization method that improves grouping, merging, and computation efficiency through computation-oriented supernode splitting. Although it is interesting to observe that optGS maintains exact reconstruction and scalable to large graphs, it is complex and may not be suitable for scenarios tolerating lossy compression and fails to address query support whereas CGS addresses various query processing mechanisms along with a bound on reconstruction loss. LMGSUM (Berberidis et al., 2022) introduces methods for summarizing labeled multi-graphs by grouping nodes and aggregating edges while preserving label and multiplicity information. The algorithm is good in supporting multiple edge labels and parallel edges but the summaries may still be large for highly heterogeneous graphs. Moreover, the complexity increases with the number of labels and may require domain-specific tuning for optimal grouping. The technique GPQPS proposed by Aris Anagnostopoulos et al. introduces a framework to process general-purpose queries directly on summary graphs by introducing a query translation mechanism that maps queries to the summarized structure without full decompression (Anagnostopoulos et al., 2024). In some terms, though, it reduces storage and computation, it handles only shortest-path queries for which the results are not encouraging and tackles only lossy version whereas CGS handles three different types of queries namely neighborhood query, shortest-path and reachability query and addresses lossless version as well. GRAPHGUESS is a runtime adaptive approximation model for graph processing that minimizes preprocessing, deactivates low-influence edges, and uses periodic super steps for adaptive correction. Although it has minimal accuracy loss, applicable to various algorithms and avoids heavy preprocessing, it is not clearly stated as to whether it is lossless/lossy and could handle only shortest-path queries (Ramezani et al., 2022). Koutra et al. (Koutra et al., 2014) constructed a vocabulary of subgraph types that occur frequently in real graphs (e.g., stars, cliques, chains). It builds a succinct description of a graph from a set of subgraphs using this vocabulary and the MDL principle. Utility driven graph summarization (Kumar and Efstathopoulos, 2018) aims to summarize graphs such that the utility does not drop below a given threshold. Besta et al. (Besta et al., 2019) proposed a programming framework for lossy graph compression based on a novel abstraction of compression kernels. Kang et al. (Kang et al., 2022) proposed personalized graph summarization that focuses on connections closer to a given set of target nodes. Berberidis et al. (Berberidis et al., 2022) proposed a summarization framework that can handle different graph characteristics like node labels, directed edges, edge multiplicities, and self-loops. Liang et al. (Liang et al., 2020) proposed two summarization schemes to answer reachability queries on dynamic graphs. Detailed surveys on various graph summarization and compression methods are available in (Maneth and Peternek, 2015; Khan et al., 2017; Besta and Hoefler, 2018; Lab, 2024). 2.2. Difference with Existing Compression Algorithms based on Merging of Nodes We next briefly review the merging approaches employed by the existing methods how they are different from the merging approached used in the CGS framework. Navlakha et al. (Navlakha et al., 2008) used a greedy algorithm to compress a graph. The basic idea is that, any two nodes that share common neighbors can give a cost reduction. The more the number of common neighbors, the higher is the cost reduction. Suppose, v is a supernode, and the cost cvc_v of supernode v is the sum of the costs of all the super edges (v,x)(v,x) to its neighbors x∈N(v)x∈ N(v), i.e., cv=∑x∈N(v)c(v,x)c_v= _x∈ N(v)c(v,x). Suppose, two supernodes u,vu,v are merged into a new supernode w. The authors proposed a fractional cost reduction metric: s(u,v)=cu+cv−cwcu+cvs(u,v)= c_u+c_v-c_wc_u+c_v. The pair (u,v)(u,v) of supernodes for which s(u,v)s(u,v) is maximized is chosen for merging. Kumar and Efstathopoulos (Kumar and Efstathopoulos, 2018) tried to prioritize the merging of two nodes by considering edge importance. Their goal is to pick an edge e=(u,v)e=(u,v) with the lowest importance and merge the nodes u and v so as to form a supernode w. At each step, they pick the node pair (u,v)(u,v) with the lowest importance score f(nodeIS[u])+f(nodeIS[v])f(nodeIS[u])+f(nodeIS[v]). Here, f()f() is a square function, as it helps in further delaying the merging of important nodes with relatively important nodes. Lee et al. (Lee et al., 2022) developed an algorithm called Slugger, which greedily merges a root node pair among those sampled within each candidate set, which is obtained in the previous step. Simultaneously, Slugger updates p-edges and n-edges incident to the merged nodes and/or their 1-level descendants by exploiting the hierarchy between supernodes. Slugger accelerates this update through memoization. Shin et al. (Shin et al., 2019) developed an algorithm named SWeG, which merges some supernodes within each group in a greedy manner. The merging step is quite involved, and is described in detail in the paper. The merging strategy adopted in the CGS framework (detailed in Sec. 4) is different from the above approaches in multiple ways. Firstly, it carefully discovers all eligible pairs of nodes that offer positive compression gain. This compression gain is different for each of the three variants of the CGS framework (Sec. 4). This compression gain not only factors the number of common neighbors but also the number of exclusive neighbors. Then among all the eligible pairs to be merged, it identifies the pair that offers the maximum compression gain. Then, it is checked whether the given pair is safe to be merged, i.e., whether the merging would violate the neighborhood loss constraint stated in Sec. 3. Once it is confirmed to be safe, the merge is executed. Subsequently, the merging is applied to the remaining pairs of nodes and super-nodes that are formed in the process. 3. Configurable Graph Summarization, ConfiGS We consider an undirected, unweighted, simple graph G=(V,E)G=(V,E), where V and E denote the vertex set and edge set, respectively. Assuming the graph G to be stored using the adjacency list representation, the space required to store G, denoted by |G||G|, is (1) |G|=|V|+2⋅|E| |G|=|V|+2·|E| 3.1. Graph Summarization Given an undirected, unweighted, simple graph G=(V,E)G=(V,E), the goal of graph summarization is to produce a summary graph Gs=(Vs,Es)G_s=(V_s,E_s) (where VsV_s and EsE_s denote the vertex set and edge set of GsG_s respectively) with two objectives: (1) |Gs|≤|G||G_s|≤|G|, i.e., the summary graph requires lesser space than the original graph, and (2) it is possible to reconstruct the original graph G from GsG_s with no or limited loss of information. It is important to note that |Gs||G_s| must take into account the total space required to store GsG_s along with the space overhead of additional data structures (if any) that are necessary to reconstruct G from GsG_s. Thus, it may be the case that |Gs|>|Vs|+2|Es||G_s|>|V_s|+2|E_s|. This point will be elaborated later. Some prior works (Li et al., 2019), including those that offer summarization without graph reconstruction (Lee et al., 2020), do not factor this point and compute compression ratios simply based on |Vs||V_s| and/or |Es||E_s| (refer to the key metrics column in Table 1). Lossy and Lossless Summarization Let ⟨S,R⟩ S,R denote a graph summarization scheme where S:G→GsS:G→ G_s is a graph summarization algorithm that summarizes an undirected, unweighted graph G=(V,E)G=(V,E) to a summary graph Gs=(Vs,Es)G_s=(V_s,E_s), and R:Gs→GrR:G_s→ G_r is a reconstruction algorithm that takes the summary graph Gs=(Vs,Es)G_s=(V_s,E_s) as input and returns a reconstructed graph Gr=(Vr,Er)G_r=(V_r,E_r). Here, reconstruction (also referred to as decompression) refers to the process of reproducing the original graph G from GsG_s. The overall goal is that GrG_r should be a good approximation of G with respect to certain graph properties. If R is able to retrieve the original graph G from the summary graph GsG_s exactly, i.e., Gr=G_r=G, then the summarization scheme ⟨S,R⟩ S,R is said to be lossless. Otherwise, the scheme is lossy. In a lossy scheme, the set of edges Er∖E_r E are referred to as false positive edges, while E∖ErE E_r are referred to as false negative edges. Typically, the vertex set is reconstructed without loss, i.e., Vr=V_r=V. Summarization Objective Our graph summarization scheme seeks to produce a summary graph GsG_s of a given graph G that reduces the space overhead. In other words, the goal is to minimize the compression ratio, cr=|Gs|/|G|cr=|G_s|/|G| (Emamzadeh Esmaeili Nejad et al., 2021). 3.2. Configuring the Summarization Variants Our proposed ConfiGS framework allows three summarization variants, namely, CGS-E, CGS-I, and CGS-U 111As we will explain later, the variant-letters stand for exact, intersection, and union, respectively., that are characterized by the presence or absence of false positive and false negative edges in the edge set ErE_r of the reconstructed graph GrG_r. If false positives need to be avoided, i.e., Er⊆E_r E, then CGS-I can be used, while to have no false negatives, i.e., Er⊇E_r E, then CGS-U can be used. The variant CGS-E avoids both false positives and false negatives, i.e., Er=E_r=E and, thus, incurs no loss. These variants are identified using a parameter var var that assumes three values, E, I and U: (2) var=E⇒CGS-E:Er=E,i.e., ∀u∈G,NGr(u)=NG(u)I⇒CGS-I:Er⊆E,i.e., ∀u∈G,NGr(u)⊆NG(u)U⇒CGS-U:Er⊇E,i.e., ∀u∈G,NGr(u)⊇NG(u) var= casesE CGS-E:&E_r=E,i.e., ∀ u∈ G,N_G_r(u)=N_G(u)\\ I CGS-I:&E_r E,i.e., ∀ u∈ G,N_G_r(u) N_G(u)\\ U CGS-U:&E_r E,i.e., ∀ u∈ G,N_G_r(u) N_G(u)\\ cases where NG(u)N_G(u) and NGr(u)N_G_r(u) denote the 1-hop neighborhood vertex set of node u in G and GrG_r respectively. 3.3. Configuring the Neighborhood Loss The neighborhood loss nl(u)nl(u) of a node u is the loss of neighborhood information as a consequence of summarization and reconstruction. It is measured as a fraction of the neighborhood set NG(u)N_G(u) that is lost after reconstruction (Navlakha et al., 2008): (3) nl(u)=|NG(u)∖NGr(u)|+|NGr(u)∖NG(u)||NG(u)| nl(u)= |N_G(u) N_G_r(u)|+|N_G_r(u) N_G(u)||N_G(u)| The above equation is applicable for only those summarization schemes that do not permit loss/gain of nodes, i.e., Vr=V_r=V. The CGS framework satisfies this property and, hence, uses this neighborhood loss model. For the different variants, it follows that (4) var=E⇒nl(u)=0I⇒nl(u)=|NG(u)∖NGr(u)|/|NG(u)|U⇒nl(u)=|NGr(u)∖NG(u)|/|NG(u)| var= casesE &nl(u)=0\\ I &nl(u)=|N_G(u) N_G_r(u)|/|N_G(u)|\\ U &nl(u)=|N_G_r(u) N_G(u)|/|N_G(u)|\\ cases The neighborhood loss for CGS-I and CGS-U as defined in Eq. (4) is unbounded. To bound it, we define a neighborhood loss tolerance threshold parameter δu _u for each vertex u, where 0≤δu≤10≤ _u≤ 1. The threshold parameter δu _u limits the maximum neighborhood loss: (5) ∀u∈G,nl(u)≤δu ∀ u∈ G,\ nl(u)≤ _u The neighborhood loss threshold set parameter, Δ , is defined as the set of neighborhood loss tolerance threshold parameters for all vertices u in G: (6) Δ=δu|u∈G =\ _u|u∈ G\ The above definition allows the user to control the maximum neighborhood loss for each node u in an independent manner. This feature may be useful for applications that require nodes of different priorities to tolerate different levels of neighborhood loss. Hence, this flexibility to control the neighborhood loss makes this model powerful and unique. Setting δu _u to be the same value for all vertices u sets a uniform loss threshold. 3.4. Query Processing When the graph size is large, retrieving many graph queries becomes a challenge (Emamzadeh Esmaeili Nejad et al., 2021). Hence, it is desirable to build a graph summarization scheme that can support graph queries on the summary graph without necessarily reconstructing the graph (Shin et al., 2019). The queries may be answered exactly or approximately, as preferred by the user. If the user is tolerant to loss in the query answers, it is desirable to answer the queries with bounded quality guarantees or with high accuracy. 3.5. Problem Statement We next formally define the problem statement. Problem 1 (Configurable Graph Summarization, ConfiGS). Given an undirected, unweighted, simple graph G=(V,E)G=(V,E), summarization variant parameter var∈I,E,U var∈\I,E,U\, and a neighborhood loss threshold Δ , design a graph summarization scheme ⟨S,R⟩ S,R to return a summary graph GsG_s that minimizes the compression ratio cr=|Gs|/|G|cr=|G_s|/|G| such that the reconstructed graph GrG_r satisfies the neighborhood loss constraint, i.e., ∀u∈G,nl(u)≤δu∀u∈ G,\ nl(u)≤ _u, and GsG_s supports multiple graph queries such as neighborhood queries, reachability queries and shortest path queries. The CGS framework addresses the above ConfiGS problem. For evaluating any graph query on an undirected unweighted graph, it is necessary to be able to answer the neighborhood queries. This is because one can always reconstruct (part or whole of) the input graph using neighborhood queries, and then retrieve the desired query. This is why CGS is designed to answer neighborhood queries with either no loss or with bounded neighborhood loss, as desired by the user. Consequently, this enables answering other graph queries such as reachability queries and shortest path queries exactly or with high accuracy. The neighborhood query for a vertex u in G returns the 1-hop neighborhood NG(u)N_G(u), i.e., all the immediate neighbors of u. Given an ordered pair of nodes, (u,v)∈G(u,v)∈ G, the reachability query, RG(u,v)R_G(u,v), determines the existence of a path from u to v. We denote the set of nodes that are reachable from u via any path in G by RG(u)R_G(u). Thus, RG(u,v)=trueR_G(u,v)= true if and only if v∈RG(u)v∈ R_G(u). Given an ordered pair of nodes, (u,v)∈G(u,v)∈ G, the shortest path query returns the shortest path from the source node u to the destination node v along with its distance, denoted by dG(u,v)d_G(u,v), i.e., the number of edges on the shortest path from u to v. If v∉RG(u)v∉ R_G(u), d(u,v)=∞d(u,v)=∞. If G is undirected, these queries are symmetric. In other words, u∈NG(v)u∈ N_G(v) if and only if v∈NG(u)v∈ N_G(u), RG(u,v)=RG(v,u)R_G(u,v)=R_G(v,u) and dG(u,v)=dG(v,u)d_G(u,v)=d_G(v,u). The query characteristics of the three summarization variants for these three queries are summarized in Table 2. These characteristics are verified in Sec. 6. CGS Variant Neighborhood query Reachability query Shortest Path query CGS-E NGr(u)=NG(u)N_G_r(u)=N_G(u) RGr(u)=RG(u)R_G_r(u)=R_G(u) dGr(u,v)=dG(u,v)d_G_r(u,v)=d_G(u,v) CGS-I NGr(u)⊆NG(u)N_G_r(u) N_G(u), (1−δu)|NG(u)|≤|NGr(u)|≤|NG(u)|(1- _u)|N_G(u)|≤|N_G_r(u)|≤|N_G(u)| RGr(u)⊆RG(u)R_G_r(u) R_G(u) dGr(u,v)≥dG(u,v)d_G_r(u,v)≥ d_G(u,v) CGS-U NGr(u)⊇NG(u)N_G_r(u) N_G(u), |NG(u)|≤|NGr(u)|≤(1+δu)|NG(u)||N_G(u)|≤|N_G_r(u)|≤(1+ _u)|N_G(u)| RGr(u)=RG(u)R_G_r(u)=R_G(u) dGr(u,v)≤dG(u,v)d_G_r(u,v)≤ d_G(u,v) Table 2. Query characteristics of the different summarization variants of CGS 4. The CGS Framework This figure demonstrates the overall algorithm of our proposed CGS framework. The algorithm proceeds in iterations and continues till there is a pair of nodes whose merge results in a compression and is safe according to the CGS variant. Figure 1. Flowchart of the CGS framework. The algorithm proceeds in iterations and continues till there is a pair of nodes whose merge results in a compression and is safe according to the CGS variant. In this section, we describe in detail our CGS framework. We first describe the merging procedure, and then the entire compression algorithm for CGS, and decompression. 4.1. Overview of CGS The CGS framework is based on merging a pair of nodes that share a common neighborhood. Fig. 1 shows the high level flowchart of this framework. The algorithm runs in iterations. In every iteration, it finds all pairs of nodes in G that are eligible to be merged. If there exists such an eligible pair, it determines the pair that offers the maximum compression gain. If the variant is lossy, i.e., for CGS-I and CGS-U, it checks whether merging of the given pair is safe, i.e., it would not violate the neighborhood loss constraint stated in Eq. 5. If the merge is found to be safe, the given pair is merged; else, it is rejected. For the lossless variant CGS-E, it is guaranteed to be safe (we prove this later). This process terminates when there is no other eligible pair left that can be safely merged. The final summary graph GsG_s is then returned. At any stage of the algorithm, consider the graph Gs′=(Vs′,Es′)G _s=(V _s,E _s). Initially, Gs′=G _s=G. A pair of nodes (u,v)(u,v) (where u,v∈Gs′u,v∈ G _s such that v∈NGs′2(u)v∈ N^2_G _s(u), i.e., v is in the 2-hop neighborhood of u) is merged if this leads to compression gain, i.e., space savings. Suppose the graph resulting at the end of the above merge operation is referred to as Gs∗=(Vs∗,Es∗)G_s^*=(V_s^*,E_s^*). The compression gain achieved by merging the pair (u,v)(u,v) is |Gs′|−|Gs∗||G _s|-|G_s^*|. A merge operation is performed only if the compression gain is positive, i.e., |Gs∗|<|Gs′||G_s^*|<|G _s|. The following section describes the merging procedure in detail. 4.2. Merging Nodes with Common Neighborhoods Consider the graph Gs′G _s at any stage. Before merging, Gs∗G_s^* is initialized to Gs′G _s. If the nodes u and v are merged, a supernode s=sn(u,v)s=sn(u,v) is created and added to the vertex set Vs∗V_s^* of Gs∗G_s^*. The pair of nodes u,v\u,v\ form the parents of the supernode s. The supernode s is referred to as the child of both u and v. Based on the variant of CGS, the neighborhood of the merged node s is set according to the intersection or the union of the neighborhoods of u and v. The details are as follows. First, consider the CGS-I variant. For each common neighbor w, i.e., when the pair of edges, (u,w),(v,w)∈Es′(u,w),(v,w)∈ E _s, only a single edge (s,w)(s,w) is added to Es∗E_s^*. The nodes u and v are removed from Gs∗G_s^* along with all their incident edges. This, thus, corresponds to the intersection of the neighborhoods of u and v. Next, consider the CGS-U variant. Consider merging of u and v to form a supernode s=sn(u,v)s=sn(u,v). If (u,v)∈Es′(u,v)∈ E _s, it is retained in Es∗E_s^* along with its incident nodes. For every other edge of the form (u,w)∈Es′(u,w)∈ E _s (or (v,w)∈Es′(v,w)∈ E _s), the edge is removed from Es∗E_s^*, and an edge (s,w)(s,w) is added to Es∗E_s^*. If (u,v)∉Es′(u,v)∉ E _s, then the nodes u and v are removed from Gs∗G_s^*. This operation corresponds to the union of the neighborhoods of u and v. Finally, consider the CGS-E variant. For each pair of edges, (u,w),(v,w)∈Es′(u,w),(v,w)∈ E _s, a single edge (s,w)(s,w) is added to Es∗E_s^* and the former pair of edges is removed from Es∗E_s^*. However, edges corresponding to the difference of the neighborhood sets are not removed but retained. Formally, for each edge (u,w)∈Es′(u,w)∈ E _s, such that (v,w)∉Es′(v,w)∉ E _s, the edge (u,w)(u,w) is still retained in Es∗E_s^* along with its incident nodes. Similarly, every edge (v,w)∈Es′(v,w)∈ E _s, where (u,w)∉Es′(u,w)∉ E _s, is retained in Es∗E_s^* along with its incident nodes. Notably, the above merge operation is not limited to only a pair of nodes, but can be performed between any node and a supernode, or between any pair of supernodes as well. We assume that the graphs are stored using adjacency lists. Thus, |G|=|V|+2⋅|E||G|=|V|+2·|E|. If there are k merge operations, each producing a supernode having exactly two parents, the space overhead of GsG_s is |Gs|=|Vs|+2⋅|Es|+2k|G_s|=|V_s|+2·|E_s|+2k. Thus, the compression gain achieved by merging the pair u,v∈Gs′u,v∈ G _s is (7) cg(u,v)=(|Vs′|−|Vs∗|)+2(|Es′|−|Es∗|)−2 cg(u,v)=(|V _s|-|V_s^*|)+2(|E _s|-|E_s^*|)-2 var var Input graph G Subsequent merge operations in GsG_s Reconstructed graph GrG_r I (a) |G|=27|G|=27 (b) |Gs|=18|G_s|=18 (c) |Gs|=17|G_s|=17 (d) |Gr|=21|G_r|=21 U (e) |G|=27|G|=27 (f) |Gs|=24|G_s|=24 (g) |Gs|=21|G_s|=21 (h) |Gr|=29|G_r|=29 E (i) |G|=27|G|=27 (j) |Gs|=24|G_s|=24 (k) |Gr|=27|G_r|=27 Table 3. Illustration of how different variants of CGS work for the same input graph Compression Step 1 Step 2 Variant (u,v)(u,v) cg(u,v)cg(u,v) (u,v)(u,v) cg(u,v)cg(u,v) CGS-I (δ=1/2δ=1/2) (2,5)(2,5) 99 (1,6)(1,6) 11 CGS-U (δ=3/5δ=3/5) (1,3)(1,3) 33 (4,5)(4,5) 33 CGS-E (2,4)(2,4) 33 - - Table 4. Working of CGS algorithm for the examples in Table 3, where cg(u,v)cg(u,v) is the compression gain achieved by merging (u,v)(u,v). 4.3. Example We illustrate the merge operation for different variants of CGS with an example shown in Table 3. The size of the graph is shown below each figure. First, consider CGS-I. Consider the merging of the node pair (2,5)(2,5) in the input graph G shown in Fig. (a). The resulting graph is shown in Fig. (b). The pair (2,5)(2,5) are merged to form the supernode s=S2,5s=S_2,5. The common neighbors (i.e., intersection) 3,4\3,4\ form the neighborhood of s. The parents of s, i.e., 2,5\2,5\ are removed along with their incident edges. Consequently, edges (2,1)(2,1) and (5,6)(5,6) get deleted. Fig. (c) shows the merging of the node pair (1,6)(1,6). Note that formation of the supernode S1,6S_1,6 does not lose any edge. Next, consider CGS-U. Consider the merging of the node pair (1,3)(1,3) in the input graph G shown in Fig. (e). The resulting graph is shown in Fig. (f). The pair (1,3)(1,3) is merged to form the supernode s=S1,3s=S_1,3. The union of neighbors of 11 and 33 is 2,4,5\2,4,5\, which form the neighborhood of s. Similar to CGS-I, the parents of s, i.e., 1,3\1,3\ are removed along with their incident edges. Fig. (g) shows the merging step for the node pair (4,5)(4,5). Finally, consider CGS-E. Consider the merging of the node pair (2,4)(2,4) in the input graph G shown in Fig. (i). The resulting graph is shown in Fig. (j). The pair (2,4)(2,4) are merged to form the supernode s=S2,4s=S_2,4. The common neighborhood of 22 and 44 is 1,3,5\1,3,5\. Once the common neighbors of 22 and 44 are absorbed by s, the neighborhood sets of 22 and 44 reduce to 4\4\ and 2,6\2,6\ respectively. Unlike var=I var=I, these two nodes are retained with their updated neighborhood sets. The compression gain achieved for each merge operation in the example in Table 3 is shown in Table 4. The key difference between the three summarization variants lies in the way the nodes are merged which, in turn, influences the compression ratio and the neighborhood loss. 5. The CGS Algorithm This section presents the proposed graph summarization scheme, CGS, that is based on the idea of merging nodes with common neighborhoods (described in Sec. 4.2). The CGS algorithm (pseudo code shown in Algo. 1) is parameterized with the summarization variant parameter var var. It acts as CGS-I or CGS-E or CGS-U, corresponding to var=I var=I or var=E var=E or var=U var=U respectively. Given a graph G and a neighborhood loss tolerance threshold parameter set Δ , it returns a summary graph GsG_s. The CGS procedure (Algo. 1) is based on the greedy paradigm. It iteratively merges a pair of nodes that offer the maximum compression gain. First, it initializes GsG_s to G. Next, through the DiscoverCN procedure, it discovers all pairs of nodes (u,v)(u,v) (where v∈NG2(u)v∈ N^2_G(u)) that can be merged potentially (line 6). The details of this procedure are described next. Input: An undirected, unweighted graph G=(V,E)G=(V,E), the summarization variant parameter var var and a set of neighborhood loss tolerance thresholds Δ . Output: A summary graph Gs∗G^*_s that is an approximate solution to the ConfiGS problem for the given graph G. 1 Function CGS (G,var,ΔG, var, ) 2 Gs←G_s← G 3 for each u∈Gsu∈ G_s do 4 PGs(u)←∅P_G_s(u)← 5 degGr(u)←|NG(u)| _G_r(u)←|N_G(u)| 6 7 H←H← DiscoverCN (G,var)(G, var) 8 while H is non-empty do 9 h←h← Extract-Max (H)(H) 10 if key(h)≤0key(h)≤ 0 then 11 return GsG_s 12 13 (u∗,v∗)←value(h)(u^*,v^*)← value(h) 14 if (var=E var=E) ∨ (IsSafeMerge(Gs,var,u∗,v∗,Δ)(G_s, var,u^*,v^*, ) is true) then 15 MergeNodes (Gs,var,H,u∗,v∗)(G_s, var,H,u^*,v^*) 16 17 18 return GsG_s 19 Algorithm 1 CGS 5.1. The DiscoverCN Procedure The DiscoverCN procedure (Algo. 2) discovers the pairs of nodes that are eligible to be merged, i.e., all pairs of nodes (u,v)(u,v) where v is a 2-hop neighbor of u, such that their compression gain cg(u,v)>0cg(u,v)>0. To this end, the CGS algorithm, computes the the size of the intersection as ic(u,v)=|NG(u)∩NG(v)|ic(u,v)=|N_G(u)∩ N_G(v)| through the ComputeNIC procedure (Algo. 3). Then, it computes the compression gain using the ComputeCG procedure (Algo. 4). Based on the value of the compression variant var∈I,E,U var∈\I,E,U\, this procedure returns the appropriate compression gain (as detailed in Sec. 4.2). It computes the size of the union uc(u,v)=|NG(u∪NG(v))|uc(u,v)=|N_G(u∪ N_G(v))| using the degrees of the nodes u and v and ic(u,v)ic(u,v), as stated in line 3. Once the compression gain is computed, and it is found to be positive, it is added to a binary max-heap where the compression gain of the pair acts as its key. The reason we choose binary max-heap is because the algorithm needs to iteratively update the compression gain of one or more pairs. and retrieve the pair that offers the maximum compression gain. Since each of these operations can be performed in logarithmic time in a binary max-heap, it is the best data structure for this purpose. 1Function DiscoverCN (G,varG, var) 2 Create an empty binary max-heap H. 3 for each u∈Gu∈ G do 4 ComputeNIC (G,u) 5 for each v∈NG(u)v∈ N_G(u) do 6 for each w∈NG(v)w∈ N_G(v) do 7 if u<wu<w then 8 cg←cg← ComputeCG (G,var var,u,w) 9 if cg>0cg>0 then Insert-Key (H,u,w,cgH,u,w,cg) // inserts a node into the heap H with key=cgkey=cg and value=(u,w)value=(u,w) 10 11 12 return H 13 Algorithm 2 DiscoverCN 1Function ComputeNIC (G,uG,u) 2 for each v∈NG(u)v∈ N_G(u) do 3 for each w∈NG(v)w∈ N_G(v) do 4 if u<wu<w then 5 ic(u,w)←0ic(u,w)← 0 6 7 for each v∈NG(u)v∈ N_G(u) do 8 for each w∈NG(v)w∈ N_G(v) do 9 if u<wu<w then 10 ic(u,w)←ic(u,w)+1ic(u,w)← ic(u,w)+1 11 Algorithm 3 ComputeNIC 5.2. The ComputeCG Procedure 1Function ComputeCG (Gs,var,u,vG_s, var,u,v) 2 if var=I var=I then 3 uc(u,v)←degGs(u)+degGs(v)−ic(u,v)uc(u,v)← _G_s(u)+ _G_s(v)-ic(u,v) 4 cg←2uc(u,v)−3cg← 2uc(u,v)-3 5 if v∈NGs(u)v∈ N_G_s(u) then 6 cg←cg−2cg← cg-2 7 8 else if var=E∨var=U var=E var=U then 9 cg←2ic(u,v)−3cg← 2ic(u,v)-3 10 for each w∈u,vw∈\u,v\ do 11 if |PGs(w)|=0|P_G_s(w)|=0 then 12 if var=I var=I then 13 cg←cg+1cg← cg+1 14 else if var=U∧v∉NGs(u) var=U v∉ N_G_s(u) then 15 cg←cg+1cg← cg+1 16 else if var=E var=E then 17 w′←u,v−ww ←\u,v\-\w\ 18 W←NGs(w)−NGs(w′)W← N_G_s(w)-N_G_s(w ) 19 if |W|=0|W|=0 then 20 cg←cg+1cg← cg+1 21 return cgcg Algorithm 4 ComputeCG The CGS procedure maintains those pairs (u,v)(u,v) that offer positive compression gain, i.e., cg(u,v)>0cg(u,v)>0 using the binary max-heap H that is generated by the DiscoverCN procedure, as discussed above. Then, the algorithm proceeds in iterations. In each iteration, it selects a pair of nodes (u∗,v∗)(u^*,v^*) that offers the maximal compression gain (line 8). However, if var=I var=I or var=U var=U, it is not necessary that a merge operation is safe, i.e., it does not violate the neighborhood loss constraint (Eq. (5)). Hence, the algorithm runs the procedure IsSafeMerge (line 12) to check that. If the merge is found to be safe, the algorithm executes the merge operation through the MergeNodes procedure (Algo. 7). The algorithm terminates when there are no more pairs that offer positive compression gain. 5.3. The IsSafeMerge Procedure The IsSafeMerge procedure (Algo. 5) validates whether merging a given pair (u,v)(u,v) is safe, i.e., it would not violate the neighborhood loss constraint (Eq. (5)). To realize this, this procedure correctly computes the degree degGr(u) _G_r(u) of each node u in the reconstructed graph GrG_r, without performing the actual reconstruction. Using this, checking the neighborhood loss constraint simplifies to checking whether |degGr(u)−degG(u)|/degG(u)≤δu| _G_r(u)- _G(u)|/ _G(u)≤ _u for all u∈Gu∈ G. This check is performed based on the notion of ancestors defined as follows. 1Function IsSafeMerge (Gs,var,u∗,v∗,ΔG_s, var,u^*,v^*, ) 2 if var=E var=E then 3 return true 4 5 U∗←Anc(Gs,u∗)U^*← Anc(G_s,u^*) 6 V∗←Anc(Gs,v∗)V^*← Anc(G_s,v^*) 7 if var=I var=I then 8 U′←u′∈Anc(Gs,u′)|u′∈(NGs(u∗)−NGs(v∗))U ←\u ∈ Anc(G_s,u )|u ∈(N_G_s(u^*)-N_G_s(v^*))\ 9 V′←v′∈Anc(Gs,v′)|v′∈(NGs(v∗)−NGs(u∗))V ←\v ∈ Anc(G_s,v )|v ∈(N_G_s(v^*)-N_G_s(u^*))\ 10 for each u∈U∗u∈ U^* do 11 if degGr(u)−|U′|degG(u)<1−δu _G_r(u)-|U | _G(u)<1- _u then 12 return false 13 for each v∈V∗v∈ V^* do 14 if degGr(v)−|V′|degG(v)<1−δv _G_r(v)-|V | _G(v)<1- _v then 15 return false 16 for each u∈U′−V∗u∈ U -V^* do 17 if degGr(u)−|U∗|degG(u)<1−δu _G_r(u)-|U^*| _G(u)<1- _u then 18 return false 19 for each v∈V′−U∗v∈ V -U^* do 20 if degGr(v)−|V∗|degG(v)<1−δv _G_r(v)-|V^*| _G(v)<1- _v then 21 return false 22 return true 23 24 else if var=U var=U then 25 U′←u′∈Anc(Gs,u′)|u′∈(NGs(u∗)−v∗−NGs(v∗))U ←\u ∈ Anc(G_s,u )|u ∈(N_G_s(u^*)-\v^*\-N_G_s(v^*))\ 26 V′←v′∈Anc(Gs,v′)|v′∈(NGs(v∗)−u∗−NGs(u∗))V ←\v ∈ Anc(G_s,v )|v ∈(N_G_s(v^*)-\u^*\-N_G_s(u^*))\ 27 for each u∈U∗u∈ U^* do 28 if degGr(u)+|V′|degG(u)>1+δu _G_r(u)+|V | _G(u)>1+ _u then 29 return false 30 for each v∈V∗v∈ V^* do 31 if degGr(v)+|U′|degG(v)>1+δv _G_r(v)+|U | _G(v)>1+ _v then 32 return false 33 for each u∈U′u∈ U do 34 if degGr(u)+|V∗|degG(u)>1+δu _G_r(u)+|V^*| _G(u)>1+ _u then 35 return false 36 for each v∈V′v∈ V do 37 if degGr(v)+|U∗|degG(v)>1+δv _G_r(v)+|U^*| _G(v)>1+ _v then 38 return false 39 return true 40 Algorithm 5 IsSafeMerge 1Function Anc (Gs,sG_s,s) 2 Nodes←∅Nodes← 3 Let StackStack be an empty stack. 4 Stack.push(s)Stack.push(s) 5 while StackStack is non-empty do 6 u=Stack.pop()u=Stack.pop() 7 if u∉Gs∨PGs(u)=∅u∉ G_s P_G_s(u)= then // u is a simple node. 8 Nodes←Nodes∪uNodes← Nodes∪\u\ 9 else // u is a super-node. 10 for each v∈PGs(u)v∈ P_G_s(u) do 11 Stack.push(v)Stack.push(v) 12 return NodesNodes 13 Algorithm 6 Anc 1Function MergeNodes (Gs,var,H,u∗,v∗G_s, var,H,u^*,v^*) 2 Add supernode s=sn(u∗,v∗)s=sn(u^*,v^*) to VsV_s 3 PGs(s)←u∗,v∗P_G_s(s)←\u^*,v^*\ 4 if var=I∨var=E var=I var=E then 5 NGs(s)←NGs(u∗)∩NGs(v∗)N_G_s(s)← N_G_s(u^*)∩ N_G_s(v^*) 6 7 else if var=U var=U then 8 NGs(s)←NGs(u∗)∪NGs(v∗)−u∗,v∗N_G_s(s)← N_G_s(u^*)∪ N_G_s(v^*)-\u^*,v^*\ 9 10 if var=I∨var=U var=I var=U then 11 UpdateDegree (Gs,var,u∗,v∗G_s, var,u^*,v^*) 12 13 UpdateCG (Gs,var,H,s,u∗,v∗G_s, var,H,s,u^*,v^*) 14 for each w∈NGs(s)w∈ N_G_s(s) do 15 NGs(w)←NGs(w)−u∗,v∗∪sN_G_s(w)← N_G_s(w)-\u^*,v^*\∪\s\ 16 if var=I var=I then 17 for each w∈NGs(u∗)−NGs(s)w∈ N_G_s(u^*)-N_G_s(s) do 18 NGs(w)←NGs(w)−u∗N_G_s(w)← N_G_s(w)-\u^*\ 19 20 for each w∈NGs(v∗)−NGs(s)w∈ N_G_s(v^*)-N_G_s(s) do 21 NGs(w)←NGs(w)−v∗N_G_s(w)← N_G_s(w)-\v^*\ 22 23 NGs(u∗)←∅N_G_s(u^*)← , NGs(v∗)←∅N_G_s(v^*)← 24 25 else if var=E∨var=U var=E var=U then 26 NGs(u∗)←NGs(u∗)−NGs(s)N_G_s(u^*)← N_G_s(u^*)-N_G_s(s) 27 NGs(v∗)←NGs(v∗)−NGs(s)N_G_s(v^*)← N_G_s(v^*)-N_G_s(s) 28 29 for each node w∈u∗,v∗w∈\u^*,v^*\ do 30 if |NGs(w)|=0∧|PGs(w)|=0|N_G_s(w)|=0 |P_G_s(w)|=0 then 31 Remove node w from GsG_s Algorithm 7 MergeNodes A node u1∈Gu_1∈ G in the original graph is said to be an ancestor of a node ul∈Gsu_l∈ G_s in the summary graph, if there exist a sequence of nodes u1,…,ulu_1,…,u_l in the interim summary graphs such that for each i=1,…,l−1i=1,…,l-1, uiu_i is a parent of ui+1u_i+1. As a special case, if l=1l=1, i.e., a node u1∈Gu_1∈ G has no child, then u1u_1 is its own ancestor as well. For any node u∗∈Gsu^*∈ G_s, let AncGs(u∗)Anc_G_s(u^*) denote the set of ancestors of u∗u^*. For computing the set of ancestors, the algorithm employs the Anc procedure (Algo. 6). To realize these ancestor sets, the algorithm maintains the parents of each super-node snsn as they get produced after each merge operation, denoted by PGs(sn)P_G_s(sn). If a node u∈Gsu∈ G_s did not undergo any merge operation, its parent set is deemed to be empty. Subsequently, the procedure evaluates all the cases applicable to each of the lossy variants var∈I,U var∈\I,U\ where the degree of a node in the reconstructed graph can potentially get altered due to a subsequent merge operation. For this purpose, it computes the potential neighborhood loss for each node in the graph G and correctly computes the altered degree of each node in the potential reconstructed graph.If none of the nodes violate the neighborhood loss constraint, the procedure returns true. Otherwise, it returns false. 5.4. The Anc Procedure The Anc procedure (Algo. 6) computes the ancestors of a node u∈Gsu∈ G_s, where the ancestors are defined in Sec. 5.3. The procedure successively pushes the parents of the super-node u into a stack. It iteratively pops out a node, and pushes its parents, in turn. Finally, when the stack becomes empty, it returns the ancestor set. 5.5. The MergeNodes Procedure The MergeNodes procedure (Algo. 7) performs the merge operation on a pair of nodes (u,v)(u,v), after it is confirmed that the given pair is safe to be merged. Given the choice of the CGS variant, i.e., var∈I,E,U var∈\I,E,U\, this merge operation is carried out based on the details stated in Sec. 4.2. Once the nodes (u,v)(u,v) are merged to a super-node sn(u,v)sn(u,v), the parent set of sn(u,v)sn(u,v)is set to contain the nodes u,v\u,v\. Then, the neighborhoods of u and v are updated, along with that of the super-node sn(u,v)sn(u,v). 1Function UpdateDegree (Gs,var,u∗,v∗G_s, var,u^*,v^*) 2 U∗←Anc(Gs,u∗)U^*← Anc(G_s,u^*) 3 V∗←Anc(Gs,v∗)V^*← Anc(G_s,v^*) 4 if var=I var=I then 5 U′←u′∈Anc(Gs,u′)|u′∈(NGs(u∗)−NGs(v∗))U ←\u ∈ Anc(G_s,u )|u ∈(N_G_s(u^*)-N_G_s(v^*))\ 6 V′←v′∈Anc(Gs,v′)|v′∈(NGs(v∗)−NGs(u∗))V ←\v ∈ Anc(G_s,v )|v ∈(N_G_s(v^*)-N_G_s(u^*))\ 7 for each u∈U∗u∈ U^* do 8 degGr(u)←degGr(u)−|U′| _G_r(u)← _G_r(u)-|U | 9 for each v∈V∗v∈ V^* do 10 degGr(v)←degGr(v)−|V′| _G_r(v)← _G_r(v)-|V | 11 for each u∈U′−V∗u∈ U -V^* do 12 degGr(u)←degGr(u)−|U∗| _G_r(u)← _G_r(u)-|U^*| 13 for each v∈V′−U∗v∈ V -U^* do 14 degGr(v)←degGr(v)−|V∗| _G_r(v)← _G_r(v)-|V^*| 15 else if var=U var=U then 16 U′←u′∈Anc(Gs,u′)|u′∈(NGs(u∗)−v∗−NGs(v∗))U ←\u ∈ Anc(G_s,u )|u ∈(N_G_s(u^*)-\v^*\-N_G_s(v^*))\ 17 V′←v′∈Anc(Gs,v′)|v′∈(NGs(v∗)−u∗−NGs(u∗))V ←\v ∈ Anc(G_s,v )|v ∈(N_G_s(v^*)-\u^*\-N_G_s(u^*))\ 18 for each u∈U∗u∈ U^* do 19 degGr(u)←degGr(u)+|V′| _G_r(u)← _G_r(u)+|V | 20 for each v∈V∗v∈ V^* do 21 degGr(v)←degGr(v)+|U′| _G_r(v)← _G_r(v)+|U | 22 for each u∈U′u∈ U do 23 degGr(u)←degGr(u)+|V∗| _G_r(u)← _G_r(u)+|V^*| 24 for each v∈V′v∈ V do 25 degGr(v)←degGr(v)+|U∗| _G_r(v)← _G_r(v)+|U^*| Algorithm 8 UpdateDegree 5.6. The UpdateDegree Procedure Once a given pair is merged, the UpdateDegree procedure (Algo. 8) updates the degree of each node u∈Gru∈ G_r, given by degGr(u) _G_r(u).As in the case of IsSafeMerge procedure, this procedure evaluates the neighborhood loss for each node in the reconstructed graph, and updates its degree accordingly. 5.7. The UpdateCG Procedure The UpdateCG procedure (Algo. 9) is responsible for updating the heap H after a given pair of nodes is merged. As a consequence of a merge operation of a pair of nodes (u,v)(u,v), the compression gain of other pairs may get affected. To this end, this procedure not only identifies the relevant pairs whose compression gain can potentially be affected due to the previous merge operation, but it also computes the change in the compression gain for all such pairs. It evaluates all possible scenarios for each of the three variants of the CGS framework. For efficiency, the above updates are performed in a manner that avoids accessing nodes whose neighborhoods do not change. The details are stated in Algo. 9. 1Function UpdateCG (Gs,var,H,s,u∗,v∗G_s, var,H,s,u^*,v^*) 2 ComputeNIC(Gs,s)ComputeNIC(G_s,s) 3 for each pair (s,u)(s,u) such that u∈NGs2(s)u∈ N^2_G_s(s) do 4 cg←cg← ComputeCG (Gs,var,s,uG_s, var,s,u) 5 if cg>0cg>0 then 6 Insert-Key (H,s,u,cgH,s,u,cg) 7 8 if var=I∨var=U var=I var=U then 9 for each pair (u,v∗)∈H(u,v^*)∈ H do 10 Decrease-Key (H,u,v∗,∞H,u,v^*,∞) 11 for each pair (u∗,v)∈H(u^*,v)∈ H do 12 Decrease-Key (H,u∗,v,∞H,u^*,v,∞) 13 if var=I var=I then 14 for each pair (u,v)∈H(u,v)∈ H, such that either u or v or both lie in NGs(u∗)∪NGs(v∗)N_G_s(u^*)∪ N_G_s(v^*) do 15 Decrease-Key (H,u,v,2H,u,v,2) 16 else if var=U var=U then 17 for each pair (u,v)∈H(u,v)∈ H, such that u∈(NGs(u∗)−NGs(v∗))u∈(N_G_s(u^*)-N_G_s(v^*)), v∈(NGs(v∗)−NGs(u∗))v∈(N_G_s(v^*)-N_G_s(u^*)) do 18 Increase-Key (H,u,v,2H,u,v,2) 19 for each pair (u,v)∈H(u,v)∈ H, such that both u,v∈(NGs(u∗)∩NGs(v∗))u,v∈(N_G_s(u^*)∩ N_G_s(v^*)) do 20 Decrease-Key (H,u,v,2H,u,v,2) 21 else if var=E var=E then 22 for each pair (u,v∗)∈H(u,v^*)∈ H do 23 value←2|NGs(u∗)∩NGs(v∗)∩NGs(u)|value← 2|N_G_s(u^*)∩ N_G_s(v^*)∩ N_G_s(u)| 24 Decrease-Key (H,u,v∗,valueH,u,v^*,value) 25 for each pair (u∗,v)∈H(u^*,v)∈ H do 26 value←2|NGs(u∗)∩NGs(v∗)∩NGs(v)|value← 2|N_G_s(u^*)∩ N_G_s(v^*)∩ N_G_s(v)| 27 Decrease-Key (H,u∗,v,valueH,u^*,v,value) 28 for each pair (u,v)(u,v) such that either u or v or both lie in NGs(u∗)∩NGs(v∗)N_G_s(u^*)∩ N_G_s(v^*) do 29 Decrease-Key (H,u,v,2H,u,v,2) Algorithm 9 UpdateCG 5.8. Working Example The working of the CGS algorithm on the example stated in Table 3 is shown in Table 4. Fig. (a), (e) and (i) show the input graphs for var=I,U,E var=I,U,E respectively. For var=I,U,E var=I,U,E, there are 2, 2 and 1 merge operations respectively. The compression gains achieved in each merge operation is stated in Table 4. The final summary graphs for var=I,E var=I,E and U are shown in Fig. (c), (g) and (j) respectively. For example, the compression gain in the first (and only) step of CGS-E is |G|−|Gs||G|-|G_s|. Using Eq. (1), |G|=7+2×10=27|G|=7+2× 10=27. Similarly, |Gs|=8+2×7+2×1=24|G_s|=8+2× 7+2× 1=24 (22 is added for 11 supernode). Hence, the compression gain is 27−24=327-24=3. 1Function Reconstruction (GsG_s) 2 Vr←∅V_r← , Er←∅E_r← 3 for each node u∈Vsu∈ V_s do 4 U←Anc(Gs,u)U← Anc(G_s,u), Vr←Vr∪UV_r← V_r∪ U 5 for each edge (u,v)∈Es(u,v)∈ E_s do 6 U←Anc(Gs,u),V←Anc(Gs,v)U← Anc(G_s,u),V← Anc(G_s,v) 7 Er←Er∪(U×V)E_r← E_r∪(U× V) 8 9 return Gr=(Vr,Er)G_r=(V_r,E_r) 10 Algorithm 10 Reconstruction 5.9. The Reconstruction Algorithm The decompression (or reconstruction) algorithm (Algo. 10) takes as input a given summary graph Gs=(Vs,Es)G_s=(V_s,E_s) that is generated by the CGS framework, and computes the reconstructed graph Gr=(Vr,Er)G_r=(V_r,E_r). For each node u∗∈Gsu^*∈ G_s, the algorithm computes the ancestors AncGs(u∗)Anc_G_s(u^*) using the parent relationships. The set of nodes VrV_r is the union of all such ancestor nodes, i.e., Vr=u|u∈AncGs(u∗)|u∗∈GsV_r=\u|u∈ Anc_G_s(u^*)|u^*∈ G_s\. The edge set ErE_r is the union of all edges formed by taking the Cartesian product of the ancestors of the end-vertices corresponding to each edge in the summary graph. Formally, Er=(u,v)|(u∗,v∗)∈Es,u∈AncGs(u∗),v∈AncGs(v∗)E_r=\(u,v)|(u^*,v^*)∈ E_s,u∈ Anc_G_s(u^*),v∈ Anc_G_s(v^*)\. Referring to the example stated in Table 3, the reconstructed graphs returned for var=I,E,U var=I,E,U are shown in Fig. (d), (g) and (k) respectively. The vertex set Vr=V_r=V for var=I,E,U var=I,E,U. For var=I var=I, the edge set Er⊆E_r E; for var=E var=E, Er=E_r=E; and, for var=U var=U, Er⊇E_r E. The neighborhood loss for each u∈Gu∈ G is rl(u)≤δrl(u)≤δ, for var=I,E,U var=I,E,U. 6. Query Processing through CGS 6.1. Local versus Global Decompression The CGS framework can process the queries in two ways: (1) Querying with local decompression, (2) Querying with global decompression. The former case is applicable when it is not possible to reconstruct the full graph due to space constraints or the query workload is sufficiently small. In this scenario, the queries are run on the summary graph GsG_s directly without reconstructing the graph GrG_r. More specifically, it performs local decompression, i.e., decompressing only those nodes that are necessary to answer the given query. The latter case is applicable when there is no space constraint to prohibit the reconstruction of the graph GrG_r and the query workload is sufficiently large. In this scenario, it is better to reconstruct the graph GrG_r, and then run the queries on GrG_r, since each query runs faster on GrG_r than GsG_s due to no requirement of local decompression. It should be noted that local decompression and global decompression yield the same query answer. This is because the local decompression steps essentially mimic the global decompression, but only at a per-neighborhood (i.e., local) level. The global decompression runs the steps for all neighborhoods. 6.2. Query Processing Given that the CGS framework allows reconstruction of the input graph, and evaluation of neighborhood queries with either no loss, or with bounded loss guarantees depending on the choice of the summarization variant, the proposed framework can be used to retrieve multiple graph queries with either no loss or with fairly high accuracy, as demonstrated in Sec. 10. As examples of graph queries, we chose to evaluate the neighborhood queries, reachability queries and shortest path queries. Next, we describe the processing of these queries. 1Function NeighborhoodQuery (Gs,uG_s,u) 2 NGr(u)←∅N_G_r(u)← 3 Desc←Desc← Desc (Gs,u)(G_s,u) 4 for each node v∈Descv∈ Desc do 5 for each node w∈NGs(v)w∈ N_G_s(v) do 6 NGr(u)←NGr(u)∪Anc(Gs,w)N_G_r(u)← N_G_r(u)∪ Anc(G_s,w) 7 8 return NGr(u)N_G_r(u) 9 Algorithm 11 NeighborhoodQuery 1Function Desc (Gs,uG_s,u) 2 Nodes←∅Nodes← 3 Let StackStack be an empty stack. 4 Stack.push(u)Stack.push(u) 5 while StackStack is non-empty do 6 v=Stack.pop()v=Stack.pop() 7 for each w∈ChildGs(v)w∈ Child_G_s(v) do 8 Nodes←Nodes∪wNodes← Nodes∪\w\ 9 Stack.push(w)Stack.push(w) 10 return NodesNodes 11 Algorithm 12 Desc 6.2.1. Neighborhood Query To answer the neighborhood query NG(u)N_G(u) posed on a node u∈Gu∈ G, we report its neighborhood NGr(u)N_G_r(u) in the reconstructed graph GrG_r. First, the Child sets are computed using parent relationships: if u∈PGs(v)u∈ P_G_s(v), then v∈ChildGs(u)v∈ Child_G_s(u). Next, for the given query node u, its descendants are computed by enumerating the Child sets in a depth-first manner. A node v is said to be a descendant of u, if u is an ancestor of v. Subsequently, for each descendant v of u, its neighborhood NGs(v)N_G_s(v) is computed. For each w∈NGs(v)w∈ N_G_s(v), the ancestors of w are reported as the answer NGr(u)N_G_r(u). The detailed procedures are given in Algo. 11 and Algo. 12. 6.2.2. Reachability Query and Shortest Path Query We answer the reachability query RG(u,v)R_G(u,v) and the distance query dG(u,v)d_G(u,v) on a node pair u,v∈Gu,v∈ G, by its corresponding queries RGr(u,v)R_G_r(u,v) and dGr(u,v)d_G_r(u,v) respectively in the reconstructed graph GrG_r. The reachability query is solved by a breadth-first search on the reconstructed graph GrG_r using the neighborhood querying procedure, discussed above. The search begins at node u and terminates when it finds the node v or when it has discovered all the nodes in the underlying connected component of GrG_r. The shortest path query is solved using the standard Dijkstra’s algorithm (Cormen et al., 2022). 6.3. Query Characteristics We next verify the query characteristics of the three summarization variants of CGS, as stated in Table 2. Since CGS-E is a lossless scheme, it retrieves all the queries exactly. Let us next consider CGS-I. From Eq. (2), Eq. (4) and Eq. (5), it follows that for any node u, NGr(u)⊆NG(u)N_G_r(u) N_G(u), 1−δu)|NG(u)|≤|NGr(u)|≤|NG(u)|1- _u)|N_G(u)|≤|N_G_r(u)|≤|N_G(u)|. To prove that RGr(u)⊆RG(u)R_G_r(u) R_G(u), it is sufficient to show that RGr(u)∖RG(u)=∅R_G_r(u) R_G(u)= . Since no new edge is added in GrG_r with respect to G, if v is not reachable from a given node u in G, then it continues to remain unreachable in GrG_r. However, since GrG_r loses edges present in G, it may happen that v that was originally reachable from u in G, now becomes unreachable in GrG_r. Thus, RGr(u)⊆RG(u)R_G_r(u) R_G(u). Following the same logic, since Er⊆E_r E, the shortest path length between any pair of nodes u,vu,v can only get increased in GrG_r. Hence, dGr(u,v)≥dG(u,v)d_G_r(u,v)≥ d_G(u,v). Next, let us consider CGS-U. From Eq. (2), Eq. (4) and Eq. (5), it follows that for any node u, NGr(u)⊇NG(u)N_G_r(u) N_G(u), |NG(u)|≤|NGr(u)|≤(1+δu)|NG(u)||N_G(u)|≤|N_G_r(u)|≤(1+ _u)|N_G(u)|. Next, consider the reachability query. Since no edge is lost in GrG_r that is present in G, if u is reachable from any given node v in G, then they continue to be so in GrG_r, as well. Thus, RG(u)⊆RGr(u)R_G(u) R_G_r(u). Although the reconstructed graph GrG_r generated by CGS-U may contain extra edges with respect to the original graph G, the extra edges are always between the 2-hop neighbors. This indicates that nodes that remain in separate connected components in G, continue to remain in separated connected components in GrG_r. In other words, the connected components remain unaltered. Thus, RGr(u)⊆RG(u)R_G_r(u) R_G(u). Together, RGr(u)=RG(u)R_G_r(u)=R_G(u). Since Er⊇E_r E, i.e., extra edges are possibly added, lengths of paths can get reduced. Hence, dGr(u,v)≤dG(u,v)d_G_r(u,v)≤ d_G(u,v). 7. Correctness of CGS The following result helps to establish the correctness of the CGS algorithm. The correctness of the CGS algorithm is established through the correctness of the procedures: UpdateDegree and IsSafeMerge, that are established as follows Lemma 1. The procedure UpdateDegree (Algo. 8) is correct. Proof. To prove the correctness of the procedure UpdateDegree, we need to show that after each merge operation, the procedure correctly computes the degree degGr(u) _G_r(u) for each node u∈Gru∈ G_r. Note that this procedure is executed only for var∈I,U var∈\I,U\. For var=E var=E, the degree degGr(u)=degG(u) _G_r(u)= _G(u) for each node u∈Gu∈ G. Hence there is no necessity to update the degrees. Next, consider var∈I,U var∈\I,U\. Firstly, we note that the given procedure correctly computes the set of all the nodes in GrG_r (the sets U∗,V∗,U′U^*,V^*,U and V′V , as stated in Algorithm 8) whose degrees are possibly altered as a result of the given merge operation. In other words, the procedure does not miss any node u∈Gru∈ G_r whose degree gets altered due to the given merge operation. Next, it is noted that the procedure correctly computes the new degree for each such node u∈Gru∈ G_r whose degree gets altered due to the given merge operation. This can be shown inductively. ∎ Lemma 2. The procedure IsSafeMerge (Algo. 5) is correct. Proof. To prove the correctness of the IsSafeMerge procedure, it is sufficient to show that the procedure returns true if and only if it is safe to merge any pair of nodes, u∗,v∗∈Gsu^*,v^*∈ G_s, i.e., it would not violate the neighborhood loss constraint (Eq. (5)). If var=E var=E, this fact is trivially true. If var∈I,U var∈\I,U\, the algorithm carefully scans each node u∈Gru∈ G_r, whose degree may get changed due to the given merge operation. To this end, the given procedure computes the sets U∗,V∗,U′U^*,V^*,U and V′V , as stated in Algorithm 5, that contain all the nodes whose degree may get altered due to a merge operation. From Lem. 1, it is clear that the CGS algorithm correctly keeps track of degGr(u) _G_r(u) for each node u∈Gru∈ G_r. Using these degree value degGr(u) _G_r(u), the IsSafeMerge procedure computes the possible updated degree of u (considering realization of the given potential merge operation) and checks if the new degree values would violate the neighborhood loss constraint (Eq. (5)). The algorithm returns true if and only if each such node u passes this test. ∎ Theorem 1. Given an input graph G=(V,E)G=(V,E) that is summarized by the CGS algorithm to produce the summary graph Gs=(Vs,Es)G_s=(V_s,E_s) that is later decompressed to produce the reconstructed graph Gr=(Vr,Er)G_r=(V_r,E_r). Then, Vr=V_r=V. Also, CGS-U, CGS-E and CGS-I respectively guarantee that Er⊇E_r E, Er=E_r=E and Er⊆E_r E. Additionally, GrG_r respects the neighborhood loss constraint stated in Eq. (5). Proof. Suppose there is a node u∈Gu∈ G, such that u∉Gru∉ G_r. Since the CGS algorithm does not remove a node unless it merges with another node, there must exist a node u∗u^* such that u is an ancestor of u∗u^*. If u did not undergo any merge operation, then u∗=u^*=u. From the reconstruction algorithm, it follows that u∈Gru∈ G_r. This is a contradiction. Hence, V⊆VrV V_r. Similarly, it can be proved that Vr⊆V_r V. Hence, V=VrV=V_r. Next, consider var=U var=U. Suppose there exists an edge (u,v)∈E(u,v)∈ E such that (u,v)∉Er(u,v)∉ E_r. Referring to the merge operation for var=U var=U (Sec. 4.2), there must exist at least a pair of nodes, u∗,v∗∈Vsu^*,v^*∈ V_s, (where u∗≠v∗u^*≠ v^*) such that u and v are ancestors of u∗u^* and v∗v^*, respectively, and (u∗,v∗)∈Es(u^*,v^*)∈ E_s. Using the reconstruction algorithm, since (u∗,v∗)∈Es(u^*,v^*)∈ E_s, therefore, (u,v)∈Er(u,v)∈ E_r, which is a contradiction. Hence, CGS-U ensures that Er⊇E_r E. Similarly, CGS-I ensures that Er⊆E_r E, and CGS-E ensures that Er=E_r=E. Next, consider var∈I,U var∈\I,U\. In either case, from Lem. 2, it follows that a merge operation is realized only after it is confirmed that it would not violate the neighborhood loss constraint (Eq. (5)). Therefore, when the algorithm terminates, it is guaranteed that the given constraint remains satisfied. The reconstruction algorithm also respects the neighborhood loss constraint. ∎ From the above discussion, it follows that the summary graph GsG_s generated by the Configurable Graph Summarizer (CGS) framework need not necessarily have the optimal compression ratio but the reconstructed graph GrG_r and the query answers satisfy all the constraints stated in the ConfiGS problem (Problem 1). 8. Graph Properties that Guarantee Compression by the CGS Framework The following results analyze the necessary and sufficient conditions to guarantee that |Gs|<|G||G_s|<|G|, i.e., cr<1cr<1, for each of the three algorithms, namely, CGS-E, CGS-I and CGS-U. Theorem 2. Let GsG_s be the summary graph of G as produced by the CGS-E algorithm. Then, |Gs|<|G||G_s|<|G| if and only if there exists at least a pair of nodes u,v∈Gu,v∈ G such that either |NG(u)∩NG(v)|≥2|N_G(u)∩ N_G(v)|≥ 2 or |NG(u)∩NG(v)|=1∧NG(u)=NG(v)|N_G(u)∩ N_G(v)|=1\ N_G(u)=N_G(v). Proof. Suppose the graph G has a pair of nodes u,v∈Gu,v∈ G such that |NG(u)∩NG(v)|≥2|N_G(u)∩ N_G(v)|≥ 2. It is sufficient to show that the CGS-E algorithm executes at least one MergeNodes operation, and eventually produces a graph GsG_s such that |Gs|<|G||G_s|<|G|. For this to happen, it is sufficient to show that the heap H has at least one pair of nodes that offer positive compression gain. If such a pair exists, the CGS-E algorithm would eventually extract and merge such a pair. We show that the pair (u,v)(u,v) satisfies the above requirement. From the ComputeCG algorithm (Algo. 4), we observe that for the given pair (u,v)(u,v), cg(u,v)≥2|NG(u)∩NG(v)|−3+xcg(u,v)≥ 2|N_G(u)∩ N_G(v)|-3+x where x is given as follows: (8) x=0 if |NG(u)−NG(v)|≥1∧|NG(v)−NG(u)|≥11 if either NG(u)⊂NG(v) or NG(v)⊂NG(u)2 if NG(u)=NG(v) x= cases0& if |N_G(u)-N_G(v)|≥ 1 |N_G(v)-N_G(u)|≥ 1\\ 1& if either N_G(u)⊂ N_G(v) or N_G(v)⊂ N_G(u)\\ 2& if N_G(u)=N_G(v) cases If |NG(u)∩NG(v)|≥2|N_G(u)∩ N_G(v)|≥ 2 then cg(u,v)≥1cg(u,v)≥ 1. If |NG(u)∩NG(v)|=1|N_G(u)∩ N_G(v)|=1 and NG(u)=NG(v)N_G(u)=N_G(v), then x=2x=2. Consequently, cg(u,v)=1cg(u,v)=1. Thus, in either of the above cases, cg(u,v)>0cg(u,v)>0. It follows that the CGS-E algorithm would have executed at least one merge operation, thereby producing a graph GsG_s such that |Gs|<|G||G_s|<|G|. Next consider the case |Gs|<|G||G_s|<|G|. This is only possible if the graph G undergoes at least one iteration of MergeNodes. This can only happen if there exists at least a pair of nodes u,v∈Gu,v∈ G such that cg(u,v)>0cg(u,v)>0. From the ComputeCG algorithm (Algo. 4), we know that cg(u,v)≥2|NG(u)∩NG(v)|−3+xcg(u,v)≥ 2|N_G(u)∩ N_G(v)|-3+x where x is given in Eq. (8). Thus, if cg(u,v)>0cg(u,v)>0, it implies that G has a pair of nodes u,v∈Gu,v∈ G such that |NG(u)∩NG(v)|≥2|N_G(u)∩ N_G(v)|≥ 2 or |NG(u)∩NG(v)|=1∧NG(u)=NG(v)|N_G(u)∩ N_G(v)|=1\ N_G(u)=N_G(v). ∎ Theorem 3. Let GsG_s be the summary graph of G as produced by the CGS-I algorithm. Then, |Gs|<|G||G_s|<|G| if and only if there exists at least a pair of nodes u,v∈Gu,v∈ G such that v∈NG2(u)v∈ N^2_G(u), |NG(u)|≤|NG(u)∩NG(v)|/(1−δu)|N_G(u)|≤|N_G(u)∩ N_G(v)|/(1- _u) and |NG(v)|≤|NG(u)∩NG(v)|/(1−δv)|N_G(v)|≤|N_G(u)∩ N_G(v)|/(1- _v). Proof. Suppose the graph G has a pair of nodes u,v∈Gu,v∈ G such that v∈NG2(u)v∈ N^2_G(u), |NG(u)∪NG(v)|≥2|N_G(u)∪ N_G(v)|≥ 2, |NG(u)|≤|NG(u)∩NG(v)|/(1−δu)|N_G(u)|≤|N_G(u)∩ N_G(v)|/(1- _u) and |NG(v)|≤|NG(u)∩NG(v)|/(1−δv)|N_G(v)|≤|N_G(u)∩ N_G(v)|/(1- _v). It is sufficient to show that the CGS-I algorithm executes at least one MergeNodes operation, and eventually produces a graph GsG_s such that |Gs|<|G||G_s|<|G|. For this to happen, it is sufficient to show that the heap H has at least one pair of nodes that offer positive compression gain and their merging does not violate the neighborhood loss constraint. If such a pair exists, the CGS-I algorithm would eventually extract and merge such a pair. We show that the pair (u,v)(u,v) satisfies the above requirement. Firstly, from the ComputeCG algorithm (Algo. 4), we observe that for a given pair u,v∈Gu,v∈ G, cg(u,v)≥2|NG(u)∪NG(v)|−3+ycg(u,v)≥ 2|N_G(u)∪ N_G(v)|-3+y where y is given as follows: (9) y=0 if (u,v)∈E2 otherwise y= cases0& if (u,v)∈ E\\ 2& otherwise cases Since v∈NG2(u)v∈ N^2_G(u), therefore, it follows that |NG(u)∪NG(v)|≥1|N_G(u)∪ N_G(v)|≥ 1. Moreover, if (u,v)∈E(u,v)∈ E, then, |NG(u)∪NG(v)|≥2|N_G(u)∪ N_G(v)|≥ 2. Hence, for either of the cases: (u,v)∈E(u,v)∈ E or (u,v)∉E(u,v)∉ E, cg(u,v)>0cg(u,v)>0. Next, we note that rl(u)=|NG(u)−NGr(u)|/|NG(u)|=(|NG(u)−(NG(u)∩NG(v))|)/|NG(u)|rl(u)=|N_G(u)-N_G_r(u)|/|N_G(u)|=(|N_G(u)-(N_G(u)∩ N_G(v))|)/|N_G(u)|. Since (NG(u)∩NG(v))⊆NG(u)(N_G(u)∩ N_G(v)) N_G(u), therefore, the above expression simplifies to rl(u)=1−|NG(u)∩NG(v)|/|NG(u)|rl(u)=1-|N_G(u)∩ N_G(v)|/|N_G(u)|. From the condition stated above, |NG(u)∩NG(v)|≥(1−δu)|NG(u)||N_G(u)∩ N_G(v)|≥(1- _u)|N_G(u)|. Hence, rl(u)≤δurl(u)≤ _u. In a similar manner, it can be shown that rl(v)≤δvrl(v)≤ _v. Therefore, if the pair of nodes (u,v)(u,v) is merged, it does not violate the neighborhood loss constraint. It follows that the CGS-I algorithm would have executed at least one merge operation, thereby producing a graph GsG_s such that |Gs|<|G||G_s|<|G|. Next consider the case |Gs|<|G||G_s|<|G|. This is only possible if the graph G undergoes at least one iteration of MergeNodes. This can only happen if there exists at least a pair of nodes u,v∈Gu,v∈ G such that cg(u,v)>0cg(u,v)>0 and their merging does not violate the neighborhood loss constraint. From the ComputeCG algorithm (Algo. 4), we know that cg(u,v)≥2|NG(u)∪NG(v)|−3+ycg(u,v)≥ 2|N_G(u)∪ N_G(v)|-3+y where y is given by Eq. (9). Thus, if cg(u,v)>0cg(u,v)>0, then it implies that v∈NG2(u)v∈ N^2_G(u). Further, if the merging of the pair (u,v)(u,v) does not violate the neighborhood loss constraint, then, rl(u)≤δurl(u)≤ _u and rl(v)≤δvrl(v)≤ _v. It follows that the graph G has a pair of nodes u,v∈Gu,v∈ G such that v∈NG2(u)v∈ N^2_G(u), |NG(u)|≤|NG(u)∩NG(v)|/(1−δu)|N_G(u)|≤|N_G(u)∩ N_G(v)|/(1- _u) and |NG(v)|≤|NG(u)∩NG(v)|/(1−δv)|N_G(v)|≤|N_G(u)∩ N_G(v)|/(1- _v). ∎ Theorem 4. Let GsG_s be the summary graph of G as produced by the CGS-U algorithm. Then, |Gs|<|G||G_s|<|G| if and only if there exists at least a pair of nodes u,v∈Gu,v∈ G such that either |NG(u)∩NG(v)|≥2|N_G(u)∩ N_G(v)|≥ 2 or |NG(u)∩NG(v)|=1∧(u,v)∉E|N_G(u)∩ N_G(v)|=1 (u,v)∉ E; |NG(u)|≥|NG(u)∪NG(v)|/(1+δu)|N_G(u)|≥|N_G(u)∪ N_G(v)|/(1+ _u) and |NG(v)|≥|NG(u)∪NG(v)|/(1+δv)|N_G(v)|≥|N_G(u)∪ N_G(v)|/(1+ _v). Proof. Suppose the graph G has a pair of nodes u,v∈Gu,v∈ G such that |NG(u)∩NG(v)|≥2|N_G(u)∩ N_G(v)|≥ 2, |NG(u)|≥|NG(u)∪NG(v)|/(1+δu)|N_G(u)|≥|N_G(u)∪ N_G(v)|/(1+ _u) and |NG(v)|≥|NG(u)∪NG(v)|/(1+δv)|N_G(v)|≥|N_G(u)∪ N_G(v)|/(1+ _v). It is sufficient to show that the CGS-U algorithm executes at least one MergeNodes operation, and eventually produces a graph GsG_s such that |Gs|<|G||G_s|<|G|. For this to happen, it is sufficient to show that the heap H has at least one pair of nodes that offer positive compression gain and their merging does not violate the neighborhood loss constraint. If such a pair exists, the CGS-U algorithm would eventually extract and merge such a pair. We show that the pair (u,v)(u,v) satisfies the above requirement. Firstly, from the ComputeCG algorithm (Algo. 4), we observe that for a given pair (u,v)(u,v), cg(u,v)≥2|NG(u)∩NG(v)|−3+zcg(u,v)≥ 2|N_G(u)∩ N_G(v)|-3+z where z is given as follows: (10) z=0 if (u,v)∈E2 otherwise z= cases0& if (u,v)∈ E\\ 2& otherwise cases Since v∈NG2(u)v∈ N^2_G(u), therefore, |NG(u)∩NG(v)|≥1|N_G(u)∩ N_G(v)|≥ 1. Note that if (u,v)∉E(u,v)∉ E, then z=2z=2. Consequently, cg(u,v)>0cg(u,v)>0. Else, if |NG(u)∩NG(v)|≥2|N_G(u)∩ N_G(v)|≥ 2, then cg(u,v)>0cg(u,v)>0. Next, we note that rl(u)=|NGr(u)−NG(u)|/|NG(u)|=(|(NG(u)∪NG(v)−NG(u))|)/|NG(u)|rl(u)=|N_G_r(u)-N_G(u)|/|N_G(u)|=(|(N_G(u)∪ N_G(v)-N_G(u))|)/|N_G(u)|. Since NG(u)⊆(NG(u)∪NG(v))N_G(u) (N_G(u)∪ N_G(v)), therefore, the above expression simplifies to rl(u)=|NG(u)∪NG(v)|/|NG(u)|−1rl(u)=|N_G(u)∪ N_G(v)|/|N_G(u)|-1. From the condition stated above, |NG(u)∪NG(v)|≤(1+δu)|NG(u)||N_G(u)∪ N_G(v)|≤(1+ _u)|N_G(u)|. Hence, rl(u)≤δurl(u)≤ _u. In a similar manner, it can be shown that rl(v)≤δvrl(v)≤ _v. Therefore, if the pair of nodes (u,v)(u,v) is merged, it does not violate the neighborhood loss constraint. It follows that the CGS-U algorithm would have executed at least one merge operation, thereby producing a graph GsG_s such that |Gs|<|G||G_s|<|G|. Next consider the case |Gs|<|G||G_s|<|G|. This is only possible if the graph G undergoes at least one iteration of MergeNodes. This can only happen if there exists at least a pair of nodes u,v∈Gu,v∈ G such that cg(u,v)>0cg(u,v)>0 and their merging does not violate the neighborhood loss constraint. From the ComputeCG algorithm (Algo. 4), we know that cg(u,v)≥2|NG(u)∩NG(v)|−3+zcg(u,v)≥ 2|N_G(u)∩ N_G(v)|-3+z where z is given in Eq. (10). Thus, if cg(u,v)>0cg(u,v)>0, then it implies that either (u,v)∉E(u,v)∉ E or |NG(u)∩NG(v)|≥2|N_G(u)∩ N_G(v)|≥ 2. Further, if the merging of the pair (u,v)(u,v) does not violate the neighborhood loss constraint, then, rl(u)≤δurl(u)≤ _u and rl(v)≤δvrl(v)≤ _v. It follows that the graph G has a pair of nodes u,v∈Gu,v∈ G such that either |NG(u)∩NG(v)|≥2|N_G(u)∩ N_G(v)|≥ 2 or |NG(u)∩NG(v)|=1∧(u,v)∉E|N_G(u)∩ N_G(v)|=1 (u,v)∉ E; |NG(u)|≥|NG(u)∪NG(v)|/(1+δu)|N_G(u)|≥|N_G(u)∪ N_G(v)|/(1+ _u) and |NG(v)|≥|NG(u)∪NG(v)|/(1+δv)|N_G(v)|≥|N_G(u)∪ N_G(v)|/(1+ _v). ∎ 9. Complexity of CGS In this section, we analyze the time complexity of the CGS algorithm. Suppose the maximum degree of any node u∈Gu∈ G is d∗d^*, i.e., |NG(u)|≤d∗|N_G(u)|≤d^*. Assume the neighborhood sets NG(u),NGs(u)N_G(u),N_G_s(u) are maintained as hash-sets for each node u. Thus, neighborhood checks such asv∈NG(u)v∈ N_G(u) are answered in O(1)O(1) time. Further, let |V|=n|V|=n, and |E|=m|E|=m. Let δ=maxδu|u∈Gδ= \ _u|u∈ G\. The complexity of the CGS algorithm is established through the following series of results. Lemma 3. Given a graph G of n nodes, the number of pairs of nodes that are eligible to be merged is O(min(md∗,(n2)))O( (md^*, n2)). Proof. A pair of nodes u,v∈Gu,v∈ G is eligible to be merged if v∈NG2(u)v∈ N_G^2(u). The number of 2-hop neighbors of u∈Gu∈ G, is |NG2(u)|=∑v∈NG(u)(degG(v)−1)|N_G^2(u)|= _v∈ N_G(u)( _G(v)-1). Thus, the total number of pairs of nodes that are eligible to be merged is at most ∑u∈G|NG2(u)|≤∑u∈G∑v∈NG(u)(degG(v)−1)≤∑u∈GdegG(u)(degG(u)−1)≤2md∗ _u∈ G|N_G^2(u)|≤ _u∈ G _v∈ N_G(u)( _G(v)-1)≤ _u∈ G _G(u)( _G(u)-1)≤ 2md^*. Given that the graph G has n nodes, the total number of possible pairs of nodes is (n2) n2. Therefore, the number of eligible pairs is O(min(md∗,(n2)))O( (md^*, n2)). ∎ Lemma 4. The DiscoverCN procedure creates a binary max-heap H, whose size, i.e., the number of nodes in H, is |H|=O(md∗)|H|=O(md^*). Proof. From Lem. 3, the number of pairs eligible to be merged is O(md∗)O(md^*). Note that the DiscoverCN procedure inserts one node h into the heap H for each such pair (u,v)(u,v) whose cg(u,v)>0cg(u,v)>0. Thus, the total number of nodes inserted by the DiscoverCN procedure is |H|=O(md∗)|H|=O(md^*). ∎ Lemma 5. The DiscoverCN procedure runs in O(md∗)O(md^*) time. Proof. The ComputeNIC procedure, when invoked with parameters (G,u)(G,u), runs in O(degG(u)d∗)O( _G(u)d^*) time. The ComputeNIC procedure computes the value ic(u,v)ic(u,v) for each pair (u,v)(u,v) such that v∈NG2(u)v∈ N_G^2(u), where ic(u,v)=|NG(u)∩NG(v)|ic(u,v)=|N_G(u)∩ N_G(v)|. Using these icic values, the ComputeCG procedure runs in O(1)O(1) time. From Lem. 3, the number of pairs eligible to be merged is O(md∗)O(md^*). Since ComputeCG is called for each such pair, the DiscoverCN procedure requires O(md∗)O(md^*) time. ∎ Lemma 6. Let S be the set of super-nodes in the summary graph GsG_s. Then, (11) |S|≤m if var∈E,Un−1 if var=I |S|≤ casesm& if var∈\E,U\\\ n-1& if var=I cases Proof. Consider the case var∈E,U var∈\E,U\. A given pair (u,v)(u,v) is merged to form exactly one super-node if cg(u,v)>0cg(u,v)>0. For this to happen, referring to Eq. (7), it follows that the number of edges in GsG_s must reduce by at least 11 after the merging of (u,v)(u,v). Given that GsG_s is initialized to G which has m edges, the number of super-nodes that are added into GsG_s is at most m−|Es|≤m-|E_s|≤ m. Now suppose var=I var=I. In this scenario, each super-node has exactly 2 parents, and more importantly, each node has at most one child. In view of this fact, the evolution of super-nodes during the course of the CGS algorithm, can be modeled as a binary tree where the nodes in the input graph G form the leaf nodes, and the super-nodes are represented by the internal nodes. Since a binary tree with n leaf nodes has at most n−1n-1 internal nodes, therefore, the number of super-nodes produced by the CGS algorithm is at most n−1n-1. ∎ Lemma 7. At any stage of the CGS algorithm, the size of the 1-hop neighborhood of any node u∈Gsu∈ G_s is bounded as follows: (12) |NGs(u)| |N_G_s(u)| ≤d∗if var∈I,Ed∗(1+δ)if var=U ≤ casesd^*&if var∈\I,E\\\ d^*(1+δ)&if var=U cases Proof. At the beginning of the CGS algorithm, the CGS procedure is invoked that initializes the graph GsG_s to G. At this stage, the neighborhood of any node u∈Gsu∈ G_s ia bounded as follows: |NGs(u)|≤|NG(u)|≤d∗|N_G_s(u)|≤|N_G(u)|≤d^*. Next consider any subsequent stage of the algorithm. Consider any node u∈Gsu∈ G_s which could either be a simple node or a super-node. Firstly, suppose u is a simple node. Referring to the MergeNodes procedure (Algorithm 7), one finds that during the course of the algorithm, the size of the neighborhood set NGs(u)N_G_s(u) either shrinks or remains unchanged. If a new neighbor is added, simultaneously, one or more existing neighbors are removed. Thus, for any such node, |NGs(u)|≤d∗|N_G_s(u)|≤d^*. Next, suppose u is a super-node and v is one of its ancestors, i.e., v∈Anc(Gs,u)v∈ Anc(G_s,u). Consider the case var∈I,E var∈\I,E\. From the MergeNodes procedure, it is clear that NGs(u)⊆NG(v)N_G_s(u) N_G(v). Thus, it follows that |NGs(u)|≤|NG(v)|≤d∗|N_G_s(u)|≤|N_G(v)|≤d^*. Further, during the course of the algorithm, the size of the neighborhood |NGs(u)||N_G_s(u)| never increases. Thus, at each stage of the algorithm, |NGs(u)|≤d∗|N_G_s(u)|≤d^*. Next, consider var=U var=U. Suppose |NGs(u)|>d∗(1+δ)|N_G_s(u)|>d^*(1+δ). At this stage, suppose GsG_s is decompressed. From the Reconstruction procedure, it follows that |NGr(v)|≥|NGs(u)|>d∗(1+δ)|N_G_r(v)|≥|N_G_s(u)|>d^*(1+δ). This violates the neighborhood loss constraint stated in Eq. (5). This contradicts the correctness of the CGS algorithm, established in Th. 1. ∎ Lemma 8. At any stage of the CGS algorithm, the maximum size of the heap H is given as follows: (13) |H|=O(md∗+nd∗2) if var=IO(md∗2) if var∈E,U |H|= casesO(md^*+nd^*^2)& if var=I\\ O(md^*^2)& if var∈\E,U\ cases Proof. From Lem. 4, it follows that at the end of the DiscoverCN procedure, the size of the heap H is O(md∗)O(md^*). Subsequently, suppose the algorithm produces k super-nodes. From Lem. 6, it follows that if var=I var=I, k=O(n)k=O(n); and if var∈E,u var∈\E,u\, then k=O(m)k=O(m). For each such super-node s, and for each u∈NGs2(s)u∈ N^2_G_s(s), the UpdateCG procedure inserts a node into the heap H. From Lem. 7, and using the fact δ≤1δ≤ 1, it follows that |NGs2(s)|=O(d∗2)|N^2_G_s(s)|=O(d^*^2). Combining these facts, lead to the above result. ∎ Lemma 9. The number of iterations of the while loop stated in line 1 of the CGS procedure is given as follows: O(|H|) O(|H|) for var∈I,U for var∈\I,U\ O(m) O(m) for var=E for var=E where |H||H| is given in Eq. (13). Proof. Consider the case var∈I,U var∈\I,U\. The iterative phase of the CGS procedure (starting from line 1) continues as long as there exists a pair (u,v)∈H(u,v)∈ H such that cg(u,v)>0cg(u,v)>0. Therefore, the number of iterations of the while loop (stated in line 1) of the CGS procedure is at most the maximum size of the heap H that is stated in Eq. (13). Next, consider the case var=E var=E. In each iteration, the CGS procedure extracts a pair of nodes and merges them. Since each merge operation produces exactly one super-node, and the number of super-nodes is at most m (Lem. 6), hence the number of iterations is at most O(m)O(m). ∎ Lemma 10. The IsSafeMerge procedure and the UpdateDegree procedure run in O(n)O(n) time. Proof. Firstly, we show that the Anc procedure runs in O(n)O(n) time. Referring to the Anc procedure, one finds that if s is a super-node that has k ancestors, then Anc(Gs,sAnc(G_s,s takes O(k)O(k) time. Since k≤nk≤ n, hence, the Anc procedure runs in O(n)O(n) time. Next, referring to the IsSafeMerge procedure and the UpdateDegree procedure, it is clear that the size of each of the sets U∗,V∗,U′U^*,V^*,U and V′V is at most n and their computation takes O(n)O(n) time. The remaining steps of these procedures run in O(n)O(n) time. This leads to the above result. ∎ Lemma 11. The UpdateCG procedure runs in O(d∗3logn)O(d^*^3 n) time. Proof. The UpdateCG procedure begins by calling the ComputeNIC procedure with the parameters (Gs,s)(G_s,s). From Lem. 7, it follows that |NGs2(s)|=O(d∗2)|N^2_G_s(s)|=O(d^*^2). Thus, the number of pairs (s,u)(s,u) is O(d∗2)O(d^*^2). Thus, the ComputeNIC procedure runs in O(d∗2)O(d^*^2) time. for each pair of nodes (s,u)(s,u) where u∈NGs2u∈ N_G_s^2, the ComputeCG procedure runs in O(1)O(1) time using the icic values computed by the ComputeNIC procedure. The total time spent in computation of cg(s,u)cg(s,u) for each pair (s,u)(s,u) is thus, O(d∗2)O(d^*^2). For each pair (s,u)(s,u) if cg(s,u)>0cg(s,u)>0, then the pair (s,u)(s,u) is inserted into the heap H. This insertion step takes O(log|H|)O( |H|) for a given pair. Using Eq. (13), and the relations: m=O(n2)m=O(n^2) and d∗=O(n)d^*=O(n), it follows that O(log|H|)=O(logn)O( |H|)=O( n). In the subsequent steps, the UpdateCG procedure scans at most O(d∗3)O(d^*^3) nodes in the heap H, and for each such node, it invokes a Decrease-Key or an Increase-Key operation that takes O(log|H|)=O(logn)O( |H|)=O( n) time. Additionally, there are neighborhood set operations such as union, intersection and set difference, each of which requires O(d∗)O(d^*) time. Summing up all these computation costs lead to the above lemma. ∎ Lemma 12. The MergeNodes procedure runs in: O(n+d∗3logn) O(n+d^*^3 n) for var∈I,U for var∈\I,U\ O(d∗3logn) O(d^*^3 n) for var=E for var=E Proof. The most expensive step of the MergeNodes procedure that is common to all the three variants of the CGS algorithm is the UpdateCG procedure. From Lem. 11, this step runs in O(d∗3logn)O(d^*^3 n) time. For var∈I,U var∈\I,U\, there is an additional expensive step in the form of the UpdateDegree procedure. From Lem. 10, this step runs in O(n)O(n) time. For var∈E var∈ E, this step is not required. This leads to the stated result. ∎ Using the above results, the following theorem, finally, establishes the time complexity of the CGS summarization scheme. Theorem 5. The CGS procedure runs in: O(md∗3logn) O(md^*^3 n) for var=E for var=E O(mnd∗+n2d∗2+(md∗+n2+nd∗3)logn) O(mnd^*+n^2d^*^2+(md^*+n^2+nd^*^3) n) for var=I for var=I O(mnd∗2+md∗3logn) O(mnd^*^2+md^*^3 n) for var=U for var=U Proof. The CGS procedure invokes the DiscoverCN procedure that takes O(md∗)O(md^*) time (Lem. 5). Next, the procedure invokes the iterative stage from line 1. Next consider the case var=E var=E. Following Lem. 9, the number of iterations is O(m)O(m). In each iteration, the procedure extracts a pair (u,v)∈H(u,v)∈ H. This takes O(logn)O( n) time. Subsequently, the pair is merged by calling the MergeNodes procedure. Following Lem. 6, the number of super-nodes produced is at most O(m)O(m). From Lem. 12, it follows that the total computation cost of MergeNodes procedure across all the iterations, is O(md∗+3logn)O(md^*+^3 n). Finally, summing up all the above computation costs leads to O(md∗+3logn)O(md^*+^3 n). Consider the case var=I var=I. From Lem. 9, the number of iterations is O(md∗+nd∗2)O(md^*+nd^*^2). In each iteration, the procedure extracts a pair (u,v)∈H(u,v)∈ H. This takes O(logn)O( n) time. Further, if cg(u,v)>0cg(u,v)>0, then it is checked whether the merging of the pair (u,v)(u,v) is safe, using the IsSafeMerge procedure. Since the IsSafeMerge procedure runs in O(n)O(n) time (Lem. 10), the total computation cost of IsSafeMerge across all the iterations, is O(mnd∗+n2d∗2)O(mnd^*+n^2d^*^2). If it is safe to merge (u,v)(u,v), the pair is merged by calling the MergeNodes procedure. Following Lem. 6, the number of super-nodes produced is at most O(n)O(n). From Lem. 12, it follows that the total computation cost of MergeNodes procedure across all the iterations, is O(n2+nd∗3logn)O(n^2+nd^*^3 n). Finally, summing up all the above computation costs leads to O(mnd∗+n2d∗2+(md∗+n2+nd∗3)logn)O(mnd^*+n^2d^*^2+(md^*+n^2+nd^*^3) n). Next, consider the case var=U var=U. From Lem. 9, the number of iterations is O(md∗2)O(md^*^2). In each iteration, the procedure extracts a pair (u,v)∈H(u,v)∈ H. This takes O(logn)O( n) time. Further, if cg(u,v)>0cg(u,v)>0, then it is checked whether the merging of the pair (u,v)(u,v) is safe, using the IsSafeMerge procedure. Since the IsSafeMerge procedure runs in O(n)O(n) time (Lem. 10), the total computation cost of IsSafeMerge across all the iterations, is O(mnd∗2)O(mnd^*^2). If it is safe to merge (u,v)(u,v), the pair is merged by calling the MergeNodes procedure. Following Lem. 6, the number of super-nodes produced is at most O(m)O(m). From Lem. 12, it follows that the total computation cost of MergeNodes procedure across all the iterations, is O(mn+md∗3logn)O(mn+md^*^3 n). Finally, summing up all the above computation costs leads to O(mnd∗2+md∗3logn)O(mnd^*^2+md^*^3 n). ∎ 10. Experimental Results In this section, we evaluate the summarization and the query processing capabilities of CGS. It is organized as follows. Sec. 10.1 lists the key research questions addressed in this work. Sec. 10.2 describes the methodology adopted for conducting the experimental evaluation. Sec. 10.3 and Sec. 10.4 present the comparison of compression ratio and reconstruction error respectively with existing baseline summarization techniques. Sec. 10.5 assesses the effect of the neighborhood loss tolerance threshold. Sec. 10.6 evaluates the query processing performance. The scalability results are discussed in Sec. 10.7. Finally, the key take aways of the experimental findings are summarized in Sec. 10.8. Graph # Vertices # Edges Avg. Degree Max. Degree Density |V||V| |E||E| 2|E||V| 2|E||V| d 2|E||V|(|V|−1) 2|E||V|(|V|-1) Youtube (YT) 1,134,890 2,987,624 5.27 28754 4.64E-06 DBLP (DB) 317,080 1,049,866 6.62 343 2.09E-05 Live-Journal (LJ) 119,685 400,000 6.68 15232 5.58E-05 soc-Epinions1 (SE) 75,879 405,740 10.70 3044 1.41E-04 Slashdot0811 (SD) 77,360 469,180 12.12 2539 1.57E-04 Email-Enron (E) 36,692 183,831 10.02 1383 2.73E-04 CA-CondMat (CM) 23,133 93,439 8.08 279 3.49E-04 Gemsec-Facebook (GF) 50,515 819,090 32.42 1469 6.42E-04 CA-AstroPh (AP) 18,772 198,050 21.10 504 1.12E-03 CA-HepPh (HP) 12,008 118,489 19.74 491 1.64E-03 Table 5. Summary of real graph datasets used in this study. The datasets are sorted based on their density. 10.1. Research Questions and Objectives The primary goal of this work is to propose a general-purpose configurable graph summarization framework that offers high compression and good query support. To this end, we strive to address the following pertinent research questions: • RQ1: How does the proposed CGS framework perform against the existing summarization methods in terms of configurability and query support capabilities? • RQ2: How does the compression achieved by the CGS framework perform against the existing baseline schemes? • RQ3: With respect to the lossy variants of the CGS framework, how does the reconstruction error compare against the existing baseline methods? • RQ4: How does the neighborhood loss tolerance threshold Δ impact the compression achieved by the lossy variants of the CGS framework? • RQ5: How is the performance of neighborhood queries, reachability queries and shortest path queries achieved by the CGS framework? • RQ6: Is the CGS framework scalable for large graphs? Based on the qualitative comparison of the configurable summarization properties listed in Table 1 and the literature review in Sec. 2, it is clear that CGS offers better configurability and query support than the existing summarization methods. This addresses the research question RQ1. The remaining research questions, namely, RQ2, RQ3, RQ4, RQ5, and RQ6, are addressed in Sec. 10.3, Sec. 10.4, Sec. 10.5, Sec. 10.6 and Sec. 10.7, respectively. 10.2. Experimental Methodology This section describes the experimental methodology used to probe the research questions. 10.2.1. Experimental Setup The proposed CGS framework is implemented in C++. The implementation code and the datasets are available at: https://github.com/sonaelzasimon/CGS˙Configurable˙Graph˙Summarization The experiments are evaluated on a 2.6 GHz Intel 56-core machine equipped with 504 GB RAM running Ubuntu 24.04 Linux. 10.2.2. Datasets CGS is evaluated on 1010 real-world graph datasets (Table 5) obtained from Stanford Large Network Dataset Collection (SNAP) (Leskovec and Krevl, 2014). The datasets are sorted based on their density, where the density of a graph G(V,E)G(V,E) is defined as 2|E||V|(|V|−1) 2|E||V|(|V|-1). We selected these datasets because many of the prior works (MoSSo (Ko et al., 2020), SLUGGER (Lee et al., 2022), SWeG (Shin et al., 2019), GraphZip (Rossi and Zhou, 2018), SSumM (Lee et al., 2020) and (Navlakha et al., 2008)) chose these datasets to benchmark their summarization schemes. Additionally, the performance is also evaluated over synthetic datasets that are based on two widely used graph models, namely, Barabási-Albert (BA) model (Barabási and Albert, 1999) and Erdös-Rényi (ER) model (Erdös and Rényi, 1959). For the BA model, we use the G(n,p)G(n,p) model where n denotes the number of nodes and p denotes the number of new edges that gets attached to each incremental node. For the ER model, we use the G(n,m)G(n,m) variant that generates a graph that is chosen uniformly from all possible random graphs of n nodes and m edges. The number of nodes vary from 10410^4 to 10610^6 and the number of edges vary from 10610^6 to 1.8×1071.8× 10^7 for the synthetic graphs. 10.2.3. Lossless Baselines For benchmarking of lossless summarization schemes, we consider four state-of-the-art techniques, namely, SLUGGER (Lee et al., 2022), MoSSo (Ko et al., 2020), SWeG (Shin et al., 2019), and GraphZip (Rossi and Zhou, 2018). The choice of these schemes as baselines is justified as follows. SLUGGER yielded up to 29.6% smaller summaries than SWeG with similar execution times. MoSSo and SWeG claim to achieve better compression than SAGS (Khan et al., 2015). GraphZip is shown to offer better compression than the Layered Label Propagation (LLP) scheme (Boldi et al., 2011). Results for all the baselines are reported according to the parameter values that offer the best compression, as indicated in the respective papers. 10.2.4. Lossy Baselines For benchmarking of lossy summarization schemes, we chose SSumM (Lee et al., 2020) that is shown to offer better summarization than (Beg et al., 2018; Riondato et al., 2017; LeFevre and Terzi, 2010). Though there exist several other competing techniques, as listed in Table 1, we could not compare with them due to the following reasons: (1) In spite of multiple requests, the source codes are not available. (2) Though the lossless variant of SweG is available, their lossy variant is not publicly available as confirmed by the authors themselves. (3) Few works such as LDME (Yong et al., 2021) use Web Graph format to input graph datasets. However, when the chosen SNAP graph datasets are converted to the Web Graph format, they reported negative compression, i.e., instead of compression, the graphs expanded. 10.2.5. Evaluation Metrics The performance of CGS is evaluated using compression ratio cr=|Gs|/|G|cr=|G_s|/|G|, reconstruction error rere, neighborhood query loss, error in shortest path, reachability query accuracy, query response time and compression time ctct. The reconstruction error is measured using the L1L_1 error norm stated in (Lee et al., 2020): (14) re=|E∖Er|+|Er∖E|(|V|2) re= |E E_r|+|E_r E||V| 2 where V is the set of vertices, and E and ErE_r are the set of edges of the original and reconstructed graphs, respectively. 10.2.6. CGS Framework Parameters The lossy schemes of CGS, namely, CGS-I and CGS-U, are parameterized by the set of neighborhood loss tolerance thresholds, denoted by Δ=δu|u∈V =\ _u|u∈ V\, where 0<δu<10< _u<1 is a user-specified parameter that controls the maximum neighborhood loss of node u, given by rl(u)rl(u), as stated in Eq. (4). To evaluate the impact of Δ , we assume δu=δ _u=δ for each node u∈Vu∈ V, where 0<δ<10<δ<1 is a parameter specified by the user. Though the experiments are evaluated on multiple thresholds in the range 0<δ<10<δ<1, three representative values δ∈0.25,0.50,0.75δ∈\0.25,0.50,0.75\ are chosen. Note that δ only represents the maximum possible neighborhood loss; the actual average neighborhood losses are much smaller, as shown in Table 6. 10.3. Comparison of Compression Ratio with Existing Baselines This section addresses the research question RQ2. Firstly, we compare the compression performance of CGS with lossless baselines, followed by the lossy baselines. This figure shows the compression ratios $cr$ of various lossless schemes on the real graphs stated in Table tab:datasets where lower $cr$ is preferred. CGS-E offers the best compression CGS-E offers the best compression than all the baseline schemes on all the real graphs. As graphs become denser, the compression achieved by CGS-E is usually higher. Figure 2. Compression ratios crcr of lossless schemes on real graphs listed in Table 5 (lower crcr is better). CGS-E offers the best compression. This figure shows the compression ratios $cr$ of various lossless schemes on the synthetic BA graphs with $n=100,000$ nodes and the number of edges $m$ is shown in million (M) where lower $cr$ is preferred. CGS-E offers the best compression. CGS-E offers the best compression than all the baseline schemes on all the real graphs. As graphs become denser, the compression achieved byCGS-E is usually higher. Figure 3. Compression ratios crcr of lossless schemes on synthetic BA graphs with n=100,000n=100,000 nodes and the number of edges m is shown in million (M) (lower crcr is better). CGS-E offers better compression with increasing density. This figure shows the compression ratios $cr$ of various lossless schemes on the synthetic ER graphs with $n=100,000$ nodes and the number of edges $m$ is shown in million (M) where lower $cr$ is preferred. CGS-E offers smaller summaries. CGS-E offers the smaller summaries than all the baseline schemes on all the real graphs. As graphs become denser, CGS-E offers smaller summaries. Figure 4. Compression ratios crcr of lossless schemes on synthetic ER graphs with n=100,000n=100,000 nodes and the number of edges m is shown in million (M) (lower crcr is better). CGS-E offers smaller summaries with increasing density. 10.3.1. Lossless Schemes Fig. 2 shows the compression ratio obtained by the lossless summarization schemes on the real datasets. CGS-E scheme offers the best compression ratio on all the graphs. More specifically, CGS-E achieves better compression than: SLUGGER by up to 27%27\% (on LJ dataset), MoSSo by up to 26%26\% (on AP dataset), SWeG by up to 20%20\% (on GF dataset) and GraphZip by up to 41%41\% (on AP dataset). Since the source code of GraphZip is not available222Despite multiple requests to the authors, we could not get their source codes., we show the results for only those datasets whose results are reported in (Rossi and Zhou, 2018). In the figure, the graphs are ranked based on their density (lower to higher). We observe that as the graphs become denser, the compression achieved by CGS-E is usually higher. This is because as the density increases, the probability that any pair of nodes (u,v)(u,v) in a graph (where v is a 2-hop neighbor of u) has high number of common neighbors, increases. This results in higher compression. Fig. 4 and Fig. 4 show the compression results for the lossless schemes on synthetically generated BA graphs and ER graphs, respectively. For these experiments, the number of nodes is fixed to 10510^5, and the density is varied from 2.50×10−42.50× 10^-4 to 1.50×10−31.50× 10^-3. As in the case of real world SNAP data sets shown earlier, the CGS-E scheme is a clear winner for the synthetic datasets, as well. Notably, in both scenarios, ie., real and synthetic datasets, we observe that as the density of the graph increases, CGS-E generally yields better compression. For some datasets such as GF and AP, the compression ratio of SSumM exceeds 11. This is because cr=|Gs|/|G|cr=|G_s|/|G|, and as stated in Sec. 3, |Gs||G_s| takes into account the space overhead of storing the super-node mappings in addition to the nodes and edges of the summary graph. Comparing the compression performance of CGS-E and CGS-I on the real world SNAP graphs, it appears that CGS-E offers better compression on majority of the datasets. However, it must be accounted that this comparison is for the chosen value of the reconstruction error rere (or corresponding value of the neighborhood loss tolerance threshold δ) that is chosen for fair comparison with SSumM. In fact, we shall shortly see that with higher values of δ, CGS-I outperforms CGS-E (Sec. 10.5). Moreover, even for the chosen value of rere, CGS-I offers better compression than CGS-E on CM and DB graphs. 10.3.2. Lossy Schemes Fig. 6 shows the compression ratios obtained by the lossy summarization schemes on different real graph datasets. Since the reconstruction error rere is an output parameter for SSumM, we cannot directly control it. Therefore, for uniform comparison, rere is chosen close to 10−410^-4. Except for SE and YT datasets, CGS-I offers better or similar compression than SSumM on all the 88 other datasets. In particular, CGS-I achieves up to 46%46\% smaller summaries than SSumM, as reported for HP dataset. The two graphs, YT and SE, where SSumM outperforms CGS-E, are relatively sparse. While YT is the least dense graph, SE is the fourth lowest dense graph. Therefore, based on the above observation, we can conclude that CGS-I outperforms SSumM on the relatively denser graphs. Among CGS-I and CGS-U, CGS-I invariably offers better compression on all the considered real graphs. Fig. 6 and Fig. 8 show the compression results for the lossy schemes on synthetically generated BA graphs and ER graphs, respectively. For experiments, we fix the number of nodes to 100,000100,000. For fair comparison, both CGS and SSumM are evaluated at the similar reconstruction error rere. CGS-U outperforms CGS-I and SSumM for both BA and ER graphs. This is in contrast to the behaviour seen on the real graphs earlier, where CGS-I outperformed CGS-U on all the datasets. Although CGS-I provides reasonable compression for BA graphs, it yields no significant compression for ER graphs. This is because, in case of a merge operation for a given pair of nodes executed by the CGS-I, the exclusive neighors are lost. In ER graphs, the neighborhoods are uniformly distributed; hence, for a given pair of nodes (u,v)(u,v) where v is a 2-hop neighbor of u, the number of exclusive neighbors is sufficiently high that prohibits meeting the neighborhood loss constraint. For both BA and ER graphs at lower densities, CGS-I achieve better compression than the SSumM baseline. As density increases, SSumM outperforms CGS-I. From the above we observe that there is no clear winner among CGS-I and CGS-U. Nevertheless, one of the lossy variants of CGS usually offers better compression than SSumM. The superior performance of CGS over the compared baselines is largely owing to its summarization approach that carefully examines the compression gains of all eligible pairs of nodes/supernodes that can be merged, and the greedy strategy to iteratively choose the pair that offers the maximum compression gain. The figure shows the compression ratios $cr$ of various lossy schemes on the real graphs mentioned in Table tab:datasets where lower $cr$ is preferred. CGS-I outperforms SSumM CGS-I outperperforms SSumM on all the real graphs at $re 10^-4$. As graphs become denser, CGS-I performs better than SSumM. Figure 5. Compression ratios crcr of lossy schemes on real graphs listed in Table 5 at re∼10−4re 10^-4 (lower crcr is better). CGS-I outperforms SSumM on the relatively denser graphs. This figure shows the compression ratios $cr$ of various lossy schemes on the synthetic BA graphs with $n=100,000$ nodes and the number of edges $m$ is shown in million (M) where lower $cr$ is preferred. CGS-U offers smaller summaries. CGS-U offers the smaller summaries than SSumM and CGS-I on the BA graphs. As number of edges increases, CGS-U offers smaller summaries. Figure 6. Compression ratios crcr of lossy schemes on synthetic BA graphs with n=100,000n=100,000 nodes and the number of edges m is shown in million (M) (lower crcr is better). Overall, CGS-U offers smaller summaries. This figure shows the compression ratios $cr$ of various lossy schemes on the synthetic ER graphs with $n=100,000$ nodes and the number of edges $m$ is shown in million (M) where lower $cr$ is preferred. CGS-U offers better compression. CGS-U offers better compression than SSumM and CGS-I on the ER graphs. As number of edges increases, CGS-U offers better compression. Figure 7. Compression ratios crcr of lossy schemes on synthetic ER graphs with n=100,000n=100,000 nodes and the number of edges m is shown in million (M) (lower crcr is better). Overall, CGS-U offers better compression. This figure shows the reconstruction error $re$ of various lossy schemes on all the real graphs stated in Table tab:datasets. where lower $re$ is better. CGS-I offers the lowest errors. $re$ results are evalauted for $cr$ close to 0.5. CGS-I provides the lowest reconstruction errors than SSumM and CGS-U on all the real graphs. Figure 8. Reconstruction error rere of lossy schemes at cr∼0.5cr 0.5 (lower rere is better): Overall, CGS-I offers lowest reconstruction errors. This figure shows the performance of Compression ratio $cr$ vs. reconstruction error $re$ for the AP dataset. CGS-I shows good $cr$. CGS-I offers the best compression than SSumM and CGS-U on the AP dataset. As $re$ increases, compression ratio decreases. (a) AP dataset This figure shows the performance of Compression ratio $cr$ vs. reconstruction error $re$ for the GF dataset. CGS-I shows good $cr$. CGS-I offers the best compression than SSumM and CGS-U on the GF dataset. As $re$ increases, compression ratio decreases. (b) GF dataset Figure 9. Compression ratio crcr vs. reconstruction error rere: At practical low reconstruction error rates, CGS-I shows good compression ratio. 10.4. Comparison of Reconstruction Error with Existing Baselines We next consider the research question RQ3. Fig. 8 shows the reconstruction error rere obtained by the lossy summarization schemes. Since crcr is an output parameter, we cannot directly control it. Hence, the reconstruction error results are evaluated for crcr close to 0.50.5. CGS-I achieves lower or similar reconstruction errors than SSumM on all datasets. The reconstruction error of CGS-U is, however, worse than SSumM on all the datasets other than HP. Fig. 9 shows the variation of compression ratio crcr with respect to the reconstruction error rere for the lossy schemes on two representative datasets, AP and GF. The compression ratio crcr monotonically decreases (becomes better) as the reconstruction error rere increases, since more error allows more compression. For lower reconstruction errors, i.e., 10−6≤re≤10−410^-6≤ re≤ 10^-4, both CGS-I and CGS-U offer considerably better compression ratios than SSumM. This gap reduces as rere exceeds 10−410^-4. The results for other datasets are similar. This figure demonstrates the effect of neighborhood loss threshold $δ$ on compression ratio on the AP, GF and E graphs. CGS-E offers smaller summaries. CGS-E shows smaller summaries than CGS-U and CGS-I on the AP, GF and E graphs. As $δ$ increases, the compression ratios of both CGS-I and CGS-U show a steady decline. For lower $δ$, CGS-E offer smaller summaries. (a) Compression ratio This figure demonstrates the effect of neighborhood loss threshold $δ$ on compression time (seconds) on the AP, GF and E graphs. CGS-E shows least compression time. As $δ$ increases, CGS-E shows least compression time than CGS-U and CGS-I on the AP, GF and E graphs. (b) Compression time Figure 10. Effect of neighborhood loss threshold δ on compression ratio and compression time on real graphs. For lower loss thresholds, CGS-E offers smaller summaries. CGS-E takes least compression time. 10.5. Effect of Neighborhood Loss Tolerance Threshold δ Next, the research question RQ4 is probed. Fig. 10 shows the effect of neighborhood loss tolerance threshold δ for the lossy variants of CGS, namely CGS-I and CGS-U, on 3 representative datasets, E, GF and AP. These datasets are chosen based on their average degrees, as stated in Table 5. As δ increases, the compression ratios of both CGS-I and CGS-U show a steady decline. This is expected, since as δ increases, it allows more compression at the cost of higher neighborhood loss. The results on other datasets are similar. For comparison with CGS-E, the compression ratio of CGS-E is also shown. For lower values of δ (0≤δ≤0.60≤δ≤ 0.6), CGS-E outperforms the lossy schemes. However, for higher values of δ (δ≥0.75δ≥ 0.75), CGS-I outperforms CGS-E. Fig. 10b shows that CGS-E has lower compression times than both the lossy variants of CGS. Refering to 10a, CGS-I gives more compression than CGS-U on the chosen datasets. This behavior is in line with that seen in Fig. 6. Fig. 10b shows that there is no significant effect of δ on the running time of either CGS-I or CGS-U. This figure demonstrates the effect of neighborhood loss threshold $δ$ on compression ratio on the synthetic BA graphs with $n=10,000$ nodes and the number of edges. CGS-U offers better compression. CGS-U offers better compression than CGS-I. As $δ$ increases, the compression ratio decreases, since larger $δ$ values allow greater compression. For BA graph, denser graphs undergo more compression, leading to a lower compression ratio. (a) BA graphs This figure demonstrates the effect of neighborhood loss threshold $δ$ on compression ratio on the synthetic ER graphs with $n=10,000$ nodes and the number of edges. CGS-U offers better compression. CGS-U offers better compression than CGS-I. As $δ$ increases, the compression ratio decreases, since larger $δ$ values allow greater compression. For ER graph, significant compression occurs only beyond a higher $δ$ threshold and primarily for dense graphs. (b) ER graphs Figure 11. Effect of neighborhood loss threshold δ on compression ratio for the synthetic graphs with n=10,000n=10,000 nodes and the number of edges as shown. Higher compression is achieved at higher loss thresholds. This figure demonstrates the effect of neighborhood loss threshold $δ$ on compression time(seconds) on the synthetic BA graphs with $n=10,000$ nodes and the number of edges. Compression time increases with density. For all the three CGS variants, the compression time increases as graphs become larger and denser, due to the greater number of eligible node pairs with positive compression gain. (a) BA graphs This figure demonstrates the effect of neighborhood loss threshold $δ$ on compression time(seconds) on the synthetic ER graphs with $n=10,000$ nodes and the number of edges. Compression time increases with density. For all the three CGS variants, the compression time increases as graphs become larger and denser, due to the greater number of eligible node pairs with positive compression gain. (b) ER graphs Figure 12. Effect of neighborhood loss threshold δ on compression time for the synthetic graphs with n=10,000n=10,000 nodes and the number of edges as shown. Compression time increases with density. This figure demonstrates the effect of neighborhood loss threshold $δ$ on reconstruction time(seconds) on the synthetic BA graphs with $n=10,000$ nodes and the number of edges. CGS-I has the lowest reconstruction time. The reconstruction time increases as the graphs become larger and denser. Among the three CGS variants, CGS-I has the lowest reconstruction time. (a) BA graphs This figure demonstrates the effect of neighborhood loss threshold $δ$ on reconstruction time(seconds) on the synthetic ER graphs with $n=10,000$ nodes and the number of edges. CGS-I has the lowest reconstruction time. The reconstruction time increases as the graphs become larger and denser. Among the three CGS variants, CGS-I has the lowest reconstruction time. (b) ER graphs Figure 13. Effect of neighborhood loss tolerance threshold δ on reconstruction time for the synthetic graphs with n=10,000n=10,000 nodes and the number of edges as shown. CGS-I has the lowest reconstruction time. Fig. 11 shows the effect of δ on the compression ratio of synthetic graphs, BA and ER. As δ increases, the compression ratio decreases, since larger δ values allow greater compression. For BA graphs (Fig.11a), denser graphs undergo more compression, leading to a lower compression ratio. For ER graphs (Fig. 11b), significant compression occurs only beyond a higher δ threshold and primarily for dense graphs. For both BA graphs and ER graphs, CGS-U offers better compression than CGS-I. Interestingly, CGS-U outperforms CGS-E as the δ increases. The poor performance of CGS-I in case of ER graphs is similar to what we observed in Sec. 10.3.2 and the explanation for the same is already presented there. Next, we analyze the effect of δ on the compression time and the reconstruction times of synthetic BA and ER graphs. Fig. 12 shows the compression time results for BA and ER graphs. For all the three CGS variants, the compression time increases as graphs become larger and denser, due to the greater number of eligible node pairs with positive compression gain. Fig. 13 shows that the reconstruction time increases as the graphs become larger and denser. Among the three CGS variants, CGS-I has the lowest reconstruction time. This is because during reconstruction, CGS-I regenerates a subgraph of the original graph, while producing the same node set. On the other hand, CGS-E reconstructs the original graph exactly and CGS-U produces the original graph along with additional false positive edges. This effect gets more pronounced with higher loss thresholds. Comparing the three variants of CGS in terms of compression, it is important to note that while the loss of the lossy schemes is configurable (both in terms of loss type as well as maximum tolerable neighborhood loss), the lossless scheme CGS-E is not configurable. Interestingly, as shown in Sec. 10.3, there are graphs where CGS-E outperforms CGS-I; then, there are graphs where CGS-I outperforms CGS-U; and, there are graphs where CGS-U outperforms CGS-I and CGS-E. Therefore, none of the three variants is universally the best or universally the worst. This is an important finding since this shows why the configurability offered by the CGS framework (in terms of CGS-I, CGS-U and CGS-E) is necessary for graph summarization. 10.6. Query Processing through CGS The next set of experiments evaluates the query performance and the query response times of CGS (research question RQ5). Since CGS-E is lossless, it answers all the queries exactly with no loss. Thus, for evaluation of query performance, we only consider the lossy variants of CGS, i.e., CGS-I and CGS-U. Given that the chosen lossy baseline scheme, SSumM (Lee et al., 2020) does not support queries, and the source codes of other lossy baseline schemes that support queries are not available, it is not possible to compare the query processing results against any existing baseline. As stated in Sec. 6, though the CGS framework can be employed to answer arbitrary graph queries, we evaluate its query performance on 3 representative graph queries, namely, the neighborhood queries, the shortest path queries, and the reachability queries. 10.6.1. Neighborhood Queries To evaluate the neighborhood queries, we measure the neighborhood loss nl(u)nl(u) (stated in Eq. (4)) for each node u in the reconstructed graph GrG_r, and then compute the average neighborhood loss, denoted by anlanl. The anlanl values along with the standard deviation are shown against the maximum possible neighborhood loss δ in Table 6. The average neighborhood loss anlanl (of either CGS-I or CGS-U) is typically much lower than δ. For example, when δ=0.5δ=0.5, the average loss for CGS-I for the three datasets are 0.090.09, 0.250.25 and 0.180.18, i.e., at most half of the threshold. CGS-U also shows an average loss of only at most 0.260.26 for the threshold 0.50.5. The maximum value of the loss (values not shown in the table) actually reaches the limit δ for the three datasets and the two variants. This indicates that both CGS-I and CGS-U strive to offer the best compression at the cost of maximum neighborhood loss that is bounded by δ. δ Average neighborhood loss anlanl CGS-I E CGS-U E CGS-I GF CGS-U GF CGS-I AP CGS-U AP 0.10 0.00±0.000.00± 0.00 0.00±0.000.00± 0.00 0.00±0.010.00± 0.01 0.00±0.010.00± 0.01 0.01±0.020.01± 0.02 0.00±0.010.00± 0.01 0.20 0.00±0.030.00± 0.03 0.00±0.020.00± 0.02 0.00±0.020.00± 0.02 0.00±0.020.00± 0.02 0.02±0.050.02± 0.05 0.01±0.030.01± 0.03 0.25 0.02±0.070.02± 0.07 0.02±0.060.02± 0.06 0.01±0.030.01± 0.03 0.01±0.040.01± 0.04 0.05±0.080.05± 0.08 0.04±0.070.04± 0.07 0.30 0.02±0.070.02± 0.07 0.03±0.070.03± 0.07 0.01±0.040.01± 0.04 0.02±0.050.02± 0.05 0.06±0.090.06± 0.09 0.06±0.080.06± 0.08 0.40 0.07±0.120.07± 0.12 0.09±0.130.09± 0.13 0.02±0.060.02± 0.06 0.09±0.120.09± 0.12 0.12±0.130.12± 0.13 0.14±0.120.14± 0.12 0.50 0.18±0.200.18± 0.20 0.26±0.200.26± 0.20 0.09±0.150.09± 0.15 0.26±0.150.26± 0.15 0.25±0.180.25± 0.18 0.26±0.160.26± 0.16 0.60 0.22±0.220.22± 0.22 0.34±0.210.34± 0.21 0.16±0.180.16± 0.18 0.37±0.160.37± 0.16 0.32±0.190.32± 0.19 0.34±0.180.34± 0.18 0.70 0.31±0.260.31± 0.26 0.41±0.240.41± 0.24 0.27±0.220.27± 0.22 0.46±0.170.46± 0.17 0.42±0.210.42± 0.21 0.43±0.200.43± 0.20 0.75 0.37±0.290.37± 0.29 0.47±0.260.47± 0.26 0.37±0.250.37± 0.25 0.51±0.180.51± 0.18 0.49±0.220.49± 0.22 0.48±0.210.48± 0.21 0.80 0.41±0.310.41± 0.31 0.51±0.270.51± 0.27 0.46±0.250.46± 0.25 0.56±0.180.56± 0.18 0.53±0.230.53± 0.23 0.53±0.210.53± 0.21 0.90 0.47±0.350.47± 0.35 0.62±0.310.62± 0.31 0.65±0.250.65± 0.25 0.69±0.190.69± 0.19 0.63±0.260.63± 0.26 0.65±0.230.65± 0.23 Table 6. Average neighborhood loss anlanl vs. δ: Average neighborhood losses are much lower than the maximum allowed neighborhood loss threshold. This figure shows the effect of Neighborhood query loss and the Query Distribution (in percentage) for CGS-I. The $x$-axis bins the different values of loss $ _u$ (Eq. eq:nlt) for the vertices, while the $y$-axis shows the percentage of queries that show the corresponding error. A high percentage of queries exhibit zero error (the first set of bars). CGS-I generally performs better or equivalent to CGS-U. (a) CGS-I This figure shows the effect of Neighborhood query loss and the Query Distribution (in percentage) for CGS-U. The $x$-axis bins the different values of loss $ _u$ (Eq. eq:nlt) for the vertices, while the $y$-axis shows the percentage of queries that show the corresponding error. A high percentage of queries exhibit zero error (the first set of bars). CGS-I generally performs better or equivalent to CGS-U. (b) CGS-U Figure 14. Neighborhood query loss, E: Most queries are answered with zero loss. Fig. 14 shows the neighborhood query loss of CGS-I and CGS-U for three different values of δ. The x-axis bins the different values of loss δu _u (Eq. 6) for the vertices, while the y-axis shows the percentage of queries that show the corresponding error. A high percentage of queries exhibit zero error (the first set of bars). CGS-I generally performs better or equivalent to CGS-U. When δ increases, the loss increases and hence, the number of queries with larger errors also increases. For instance, for δ=0.25δ=0.25, both CGS-I and CGS-U retrieve more than 85%85\% of neighborhood queries without any error, and ∼10% 10\% of queries with error <0.25<0.25. This figure demonstrates the average errors in shortest path query for CGS-I and CGS-U on all the real graphs. CGS-I performs better than CGS-U. For $δ=0.5$, error in most datasets $<0.2$. Figure 15. Average error in shortest path query: Overall, CGS-I performs better than CGS-U. This figure shows the error in shortest path at $δ=0.5$ for the E dataset for the CGS-I version. Most queries return the exact shortest path length. A very high percentage of queries (more than 80% for both CGS-I and CGS-U) are evaluated exactly. Moreover, error in shorter path lengths are less. (a) CGS-I This figure shows the error in shortest path at $δ=0.5$ for the E dataset for the CGS-U version. Most queries return the exact shortest path length. A very high percentage of queries (more than 80% for both CGS-I and CGS-U) are evaluated exactly. Moreover, error in shorter path lengths are less. (b) CGS-U Figure 16. Error in shortest path, δ=0.5δ=0.5, E: Most queries return the exact shortest path length. This figure shows the percentage of reachability queries that are reported correctly over a set of 100,000 random reachability queries for the E, GF and AP datasets. CGS-I is accurate at low error thresholds while CGS-U is always accurate. The accuracy of CGS-U is always $100\%$ for all values of $δ$ and all datasets.The accuracy of CGS-I declines as $δ$ increases. Figure 17. Reachability query accuracy: CGS-I is accurate at low error thresholds while CGS-U is always accurate. This figure demonstrates the query response time for the neighborhood query in microseconds for all the real graphs. This is done for all the three variants using local decompression i.e. when the queries are run directly on the summary graph. (a) Neighborhood query This figure demonstrates the query response time for the shortest path query for all the real graphs. This is done for all the three variants using local decompression i.e. when the queries are run directly on the summary graph. While the neighborhood queries took microseconds to run, the shortest path queries finish in milliseconds. (b) Shortest path query Figure 18. Query response times: Queries on the summary graphs are slower due to local decompression. This figure demonstrates the time required for varying number of shortest path queries in seconds for the Local Decompression(LD) vs. Global Decompression(GD) for all the three variants. When the number of queries is large, global decompression is better than local decompression. For CGS-E, the savings in global decompression starts only when 50,000 queries are run. The cutoff points for CGS-U and CGS-I are around 40,000 and 65,000, respectively. Figure 19. Local (LD) vs. global decompression (GD), E: When the number of queries is large, global decompression is better than local decompression. 10.6.2. Shortest Path Queries To evaluate shortest path queries, 100,000 random pairs of nodes are chosen for each graph dataset. For each chosen pair (u,v)∈G(u,v)∈ G, the error in shortest path is computed as error(u,v)=|dG(u,v)−dGr(u,v)|/dG(u,v)error(u,v)=|d_G(u,v)-d_G_r(u,v)|/d_G(u,v), where dGd_G is the (actual) shortest path distance in G, and dGrd_G_r is the (approximate) shortest path in the reconstructed graph GrG_r. Fig. 15 shows the average errors for CGS-I and CGS-U on all the graphs. For δ=0.5δ=0.5, error in most datasets <0.2<0.2. Fig. 16 shows that a very high percentage of queries (more than 80% for both CGS-I and CGS-U) are evaluated exactly. Moreover, error in shorter path lengths are less. This shows the effectiveness of query processing of CGS. 10.6.3. Reachability queries Fig. 17 shows the percentage of reachability queries that are reported correctly over a set of 100,000 random reachability queries. These queries are constructed by selecting 100,000 random and unique node pairs (u,v)(u,v) from the graph, ensuring u≠vu≠ v. For each pair, reachability is evaluated on both the original and the reconstructed graph. The results are then compared to obtain the accuracy of reachability preservation in the summary graph. The reachability query accuracy measures how often the summary graph correctly preserves the reachability compared to the original graph for node pairs that are actually reachable. The accuracy of CGS-U is always 100%100\% for all values of δ and datasets. This follows from Table 2. On the other hand, the accuracy of CGS-I declines as δ increases, since it leads to more disconnected components, as explained in Sec. 6.3. Nevertheless, CGS-I offers fairly high accuracy for all values of δ. 10.6.4. Query Response Times Fig. 18 shows the response times of the different queries using local decompression, i.e., when the queries are run directly on the summary graph. (Times for reachability queries are not shown as they are similar to those for the shortest path queries.) While the neighborhood queries take microseconds to run, the shortest path queries finish in milliseconds. The queries run faster on the original graph, since they do not require local decompression. 10.6.5. Local versus Global Decompression The next set of experiments seeks to answer the question: which decompression method to use – local or global. While local decompression does not require reconstructing the entire graph; if, however, the graph is reconstructed, the queries run faster, since local decompression operations are not needed. There is, thus, a trade-off. Fig. 19 shows the times required for varying number of shortest path queries. For CGS-E, the savings in global decompression starts only when 50,000 queries are run. Assuming, the time taken for running a query on the locally decompressed graph is tlt_l, that in the reconstructed graph is tgt_g and the time to reconstruct the graph is trt_r, we get 50000×tl≈tr+50000×tg50000× t_l≈ t_r+50000× t_g. The cutoff points for CGS-U and CGS-I are around 40,000 and 65,000, respectively. This figure shows the scalability performance of CGS-E in terms of compression ratio on BA graphs of varying sizes of nodes. Compression is better for denser graphs where the number of edges $m$ is shown above each bar, where $M$ denotes one million). For a given number of nodes such as $10^5$, the compression improves as the number of edges increases. As mentioned earlier, CGS offers better compression for denser graphs. Figure 20. Scalability evaluation of CGS-E in terms of compression ratio on synthetic BA graphs: Compression is better for denser graphs (The number of edges m is shown above each bar, where M denotes one million). This figure demonstrates the compression time(in seconds) results of CGS-E on the BA graphs. As the graphs become larger and denser, the compression time increases. The compression time increases owing to larger number of eligible pairs of nodes with positive compression gain. Figure 21. Scalability evaluation of CGS-E in terms of compression time on synthetic BA graphs: More time is required to compress the denser graphs. This figure demonstrates the scalability evaluation of lossy schemes - CGS-U and CGS-I in terms of compression time (in seconds) on synthetic BA graphs. Denser graphs take more time to compress. As the number of edges increases, the compression time increases. Overall, the cost of CGS framework on million scale graph varies from few minutes to few hours. Figure 22. Scalability evaluation of lossy schemes in terms of compression time on synthetic BA graphs: Denser graphs take more time to compress. This figure demonstrates the scalability evaluation of lossy schemes - CGS-U and CGS-I in terms of compression time (in seconds) on synthetic ER graphs. Denser graphs take more time to compress. As the number of edges increases, the compression time increases. Overall, the cost of CGS framework on million scale graph varies from few minutes to few hours. Figure 23. Scalability evaluation of lossy schemes in terms of compression time on synthetic ER graphs: Denser graphs take more time to compress. This figure shows the compression time(in seconds) for lossless schemes on 4 real datasets i.e. YT, E, GF and AP. The results on other datasets are similar. The compression times of the CGS variants are higher than its competitors i.e. MoSSo, SLUGGER and SWeG. Though the compression times are higher, the absolute times are practical. Since summarization is typically an offline and infrequent activity, the higher running time of CGS does not reduce its practical applicability. (a) Lossless schemes This figure shows the compression time(in seconds) for lossy schemes on 4 real datasets i.e. YT, E, GF and AP. The results on other datasets are similar. The compression times of the CGS variants are higher than its competitor i.e. SSumM. Though the compression times are higher, the absolute times are practical. Since summarization is typically an offline and infrequent activity, the higher running time of CGS does not reduce its practical applicability. For the lossy schemes, higher compression, i.e., lower compression ratio typically comes at a cost of higher compression time. (b) Lossy schemes Figure 24. Scalability evaluation in terms of compression time on real graphs: CGS algorithms are slower but practical for real graphs. 10.7. Scalability Results This section addresses the research question RQ6. To assess the scalability of the CGS framework, we evaluate on both synthetic as well as real world graphs. For evaluation on synthetic datasets, we consider the BA graphs and the ER graphs of different sizes. Fig. 21 shows the scalability performance of CGS-E in terms of compression ratio on BA graphs of varying sizes. For a given number of nodes such as 10510^5, the compression improves as the number of edges increases. On the other hand, for a given number of edges such as 10610^6, the compression decreases as the number of nodes increases. This agrees with our earlier observation in Sec. 10.3, that CGS offers better compression for denser graphs. Fig. 21 shows the compression time results of CGS-E on the same BA graphs. As the graphs become larger and denser, the compression time increases owing to larger number of eligible pairs of nodes with positive compression gain. Fig. 23 and Fig. 23 shows the compression time results for the lossy variants on BA and ER graphs, respectively. The number of nodes is fixed to 10,00010,000 and number of edges varies from 2.5×1062.5× 10^6 to 12.5×10612.5× 10^6. Overall, the cost of CGS framework on million scale graph varies from few minutes to few hours. Fig. 24 shows the compression time results for lossless schemes and lossy schemes on 4 representative real datasets. The results on other datasets are similar. While the compression times of the CGS variants are higher than its competitors, the absolute times are practical. Given that CGS offers high configurability, along with superior compression and support for arbitrary queries with fairly high accuracy, its high compression time comes as a trade-off. Moreover, since summarization is typically an offline and infrequent activity, the higher running time of CGS does not reduce its practical applicability. For the lossy schemes, higher compression, i.e., lower compression ratio typically comes at a cost of higher compression time. This figure shows the reconstruction time(in seconds) for the YT, E, GF and AP graphs for all the three variants. Among the three CGS variants, CGS-U has the highest reconstruction time, followed by CGS-E, and CGS-I has the lowest. This behavior is justified in Sec. sec:exp effect of neighborhood loss tolerance threshold. Figure 25. Reconstruction time results: CGS reconstruction times are practical. Fig. 25 shows the reconstruction time for the same graphs. Among the three CGS variants, CGS-U has the highest reconstruction time, followed by CGS-E, and CGS-I has the lowest. This behavior is justified in Sec. 10.5. 10.8. Summary of the Experiments We conclude the section by listing the key takeaways. CGS-E offers superior summarization on both real and synthetic graphs than all the state-of-the-art lossless schemes. For denser graphs, the compression is usually more. Among the lossy variants, CGS-I usually offers smaller summaries (by up to 46%46\%) and lower reconstruction errors (by up to 44%44\%) than SSumM (Lee et al., 2020) on real graphs. However, on synthetic BA and ER graphs, CGS-U offers the best compression. Queries for CGS-E, by nature, are exact. For neighborhood queries, while CGS-I is usually better than CGS-U, for shortest path queries, CGS-U is usually better than CGS-I. For reachability queries, CGS-U is 100% accurate, while CGS-I has a fairly high accuracy. Though compression times of CGS are higher than its competitors, they are practical. Evaluation on several synthetic and real world graph datasets show that the CGS framework is scalable. Further, CGS-I and CGS-U cannot substitute each other because of their distinct summarization and query characteristics, as stated in Sec. 3. Finally, as observed in Sec. 10.5, among the three variants of CGS, there is no scheme that universally offers the most compressed summaries on all graphs. Therefore, each variant uniquely contributes towards the goal of configurable graph summarization. 11. Conclusions In this paper, we proposed a configurable graph summarization framework CGS, based upon the common neighborhood of nodes. The framework offers three summarization variants. While CGS-I and CGS-U avoid false positive and false negative edges respectively, CGS-E is a lossless scheme. The lossy variants of CGS, CGS-I and CGS-U, allow a parameterized control over the neighborhood loss, by using a maximum loss tolerance threshold. This enables the lossy schemes to reconstruct the input graph with bounded neighborhood loss. Moreover, CGS can answer neighborhood queries with bounded quality guarantees, and other graph queries such as, shortest path queries and reachability queries with fairly high accuracy. Empirical evaluation on several real-world graphs confirm the efficacy and efficiency of CGS. In future, we plan to extend this framework to handle dynamic graphs and streaming graphs. References S. Ali, M. Ahmad, M. A. Beg, I. U. Khan, S. Faizullah, and M. A. Khan (2024) Ssag: summarization and sparsification of attributed graphs. ACM Transactions on Knowledge Discovery from Data 18 (6), p. 1–22. Cited by: item 2, §2.1, Table 1. A. Anagnostopoulos, V. Arrigoni, F. Gullo, G. Salvatori, and L. Severini (2024) General-purpose query processing on summary graphs. Social Network Analysis and Mining 14 (1), p. 157. Cited by: §1.1, §2.1, Table 1, §2. A. Barabási and R. Albert (1999) Emergence of Scaling in Random Networks. Science 286 (5439), p. 509–512. Cited by: §10.2.2. M. A. Beg, M. Ahmad, A. Zaman, and I. Khan (2018) Scalable approximation algorithm for graph summarization. In Advances in Knowledge Discovery and Data Mining: 22nd Pacific-Asia Conference, PAKDD 2018, Melbourne, VIC, Australia, June 3-6, 2018, Proceedings, Part I 22, p. 502–514. External Links: Document Cited by: §10.2.4, item 2. D. Berberidis, P. J. Liang, and L. Akoglu (2022) Summarizing labeled multi-graphs. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, p. 53–68. Cited by: §1.1, item 2, §2.1, §2.1, Table 1. M. Besta and T. Hoefler (2018) Survey and taxonomy of lossless graph compression and space-efficient graph representations. Note: arXiv preprint arXiv:1806.01799 External Links: Document Cited by: item 1, §2.1. M. Besta, S. Weber, L. Gianinazzi, R. Gerstenberger, A. Ivanov, Y. Oltchik, and T. Hoefler (2019) Slim graph: practical lossy graph compression for approximate graph processing, storage, and analytics. In HPCNSA, p. 1–25. External Links: Document Cited by: item 1, §2.1. P. Boldi, M. Rosa, M. Santini, and S. Vigna (2011) Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. In Proceedings of the 20th International Conference on World Wide Web, W ’11, New York, NY, USA, p. 587–596. External Links: ISBN 9781450306324, Link, Document Cited by: §10.2.3, §2.1. P. Boldi and S. Vigna (2004) The webgraph framework i: compression techniques. In Proceedings of the 13th international conference on World Wide Web, p. 595–602. External Links: Document Cited by: item 1, §2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (2022) Introduction to algorithms. MIT press. Cited by: §6.2.2. A. Emamzadeh Esmaeili Nejad, M. Zolghadri Jahromi, and M. Taheri (2021) Graph compression based on transitivity for neighborhood query. Information Sciences 576, p. 312–328. External Links: ISSN 0020-0255, Document, Link Cited by: §1.1, item 1, §2.1, Table 1, §3.1, §3.4. P. Erdös and A. Rényi (1959) On random graphs, I. Publicationes Mathematicae (Debrecen) 6, p. 290–297. Cited by: §10.2.2. W. Fan, J. Li, X. Wang, and Y. Wu (2012) Query preserving graph compression. In Proceedings of the 2012 ACM SIGMOD international conference on management of data, p. 157–168. External Links: Document Cited by: §1.1, §2.1, Table 1. S. Grabowski and W. Bieniecki (2010) Tight and simple web graph compression. Note: arXiv preprint arXiv:1006.0809 External Links: Document Cited by: item 1, §2. S. Kang, K. Lee, and K. Shin (2022) Personalized graph summarization: formulation, scalable algorithms, and applications. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), p. 2319–2332. External Links: Document Cited by: item 2, §2.1. A. Khan, S. S. Bhowmick, and F. Bonchi (2017) Summarizing static and dynamic big graphs. Proceedings of the VLDB Endowment 10 (12), p. 1981–1984. External Links: Document Cited by: §1, §2.1. K. U. Khan, W. Nawaz, and Y. Lee (2015) Set-based approximate approach for lossless graph summarization. Computing 97, p. 1185–1207. External Links: Document Cited by: §1.1, §1.1, §10.2.3, §2.1, Table 1. J. Ko, Y. Kook, and K. Shin (2020) Incremental lossless graph summarization. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, p. 317–327. External Links: Document Cited by: §1.1, §10.2.2, §10.2.3, item 2, §2.1, Table 1. D. Koutra, U. Kang, J. Vreeken, and C. Faloutsos (2014) Vog: summarizing and understanding large graphs. In Proceedings of the 2014 SIAM international conference on data mining, p. 91–99. External Links: Document Cited by: §2.1. K. A. Kumar and P. Efstathopoulos (2018) Utility-driven graph summarization. Proceedings of the VLDB Endowment 12 (4), p. 335–347. External Links: Document Cited by: §2.1, §2.2. E. M. Lab (2024) Graph reduction / summarization / simplification. Note: GitHub repository Cited by: §2.1. M. Lai, Y. Huang, Z. Liu, and K. Wu (2023) An optimized lossless graph summarization for large-scale graphs. In 2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS), p. 355–362. Cited by: §1.1, §1, item 2, §2.1, Table 1. K. Lee, H. Jo, J. Ko, S. Lim, and K. Shin (2020) SsumM: sparse summarization of massive graphs. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, p. 144–154. External Links: Document Cited by: §1.1, §10.2.2, §10.2.4, §10.2.5, §10.6, §10.8, §2.1, Table 1, §3.1. K. Lee, J. Ko, and K. Shin (2022) Slugger: lossless hierarchical summarization of massive graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), p. 472–484. External Links: Document Cited by: §1.1, §1, §10.2.2, §10.2.3, §2.1, §2.2, Table 1. K. LeFevre and E. Terzi (2010) GraSS: graph structure summarization. In Proceedings of the 2010 SIAM International Conference on Data Mining, p. 454–465. External Links: Document Cited by: §10.2.4, §2.1, Table 1. J. Leskovec and A. Krevl (2014) SNAP Datasets: Stanford large network dataset collection. Note: http://snap.stanford.edu/data Cited by: §10.2.2. F. Li, Z. Zou, J. Li, and Y. Li (2019) Graph compression with stars. In Advances in Knowledge Discovery and Data Mining: 23rd Pacific-Asia Conference, PAKDD 2019, Macau, China, April 14-17, 2019, Proceedings, Part I 23, p. 449–461. External Links: Document Cited by: §1.1, item 1, item 2, §2.1, Table 1, §3.1. P. Liakos, K. Papakonstantinopoulou, and M. Sioutis (2014) On the effect of locality in compressing social networks. In European Conference on Information Retrieval, p. 650–655. External Links: Document Cited by: item 1, §2. Y. Liang, C. Chen, Y. Wang, K. Lei, M. Yang, and Z. Lyu (2020) Reachability preserving compression for dynamic graph. Information Sciences 520 (C), p. 232–249. External Links: Document Cited by: §2.1. Y. Liu, T. Safavi, A. Dighe, and D. Koutra (2018) Graph summarization methods and applications: a survey. ACM computing surveys (CSUR) 51 (3), p. 1–34. External Links: Document Cited by: §1. S. Maneth and F. Peternek (2015) A survey on methods and systems for graph compression. Note: arXiv preprint arXiv:1504.00616 External Links: Document Cited by: item 1, §2.1. H. Maserrat and J. Pei (2010) Neighbor query friendly compression of social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, p. 533–542. Cited by: item 2, §2.1, Table 1. C. Nabti and H. Seba (2017) Querying massive graph data: a compress and search approach. Future Generation Computer Systems 74, p. 63–75. Cited by: §2.1, Table 1. S. Navlakha, R. Rastogi, and N. Shrivastava (2008) Graph summarization with bounded error. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, p. 419–432. External Links: Document Cited by: §1.1, §1.1, §1, §10.2.2, item 2, §2.1, §2.1, §2.2, Table 1, §3.3. M. Ramezani, M. T. Kandemir, and A. Sivasubramaniam (2022) GraphGuess: approximate graph processing system with adaptive correction. In European Conference on Parallel Processing, p. 285–300. Cited by: §1.1, §2.1, Table 1. M. Riondato, D. García-Soriano, and F. Bonchi (2017) Graph summarization with quality guarantees. Data mining and knowledge discovery 31, p. 314–349. External Links: Document Cited by: §10.2.4, §2.1, Table 1, §2. R. A. Rossi and R. Zhou (2018) Graphzip: a clique-based sparse graph compression method. Journal of Big Data 5 (1), p. 10. External Links: Document Cited by: §10.2.2, §10.2.3, §10.3.1, §2.1, Table 1. K. Shin, A. Ghoting, M. Kim, and H. Raghavan (2019) Sweg: lossless and lossy summarization of web-scale graphs. In The World Wide Web Conference, p. 1679–1690. External Links: Document Cited by: §1.1, §1.1, §10.2.2, §10.2.3, §2.1, §2.2, Table 1, §2, §3.4. Q. Yong, M. Hajiabadi, V. Srinivasan, and A. Thomo (2021) Efficient graph summarization using weighted lsh at billion-scale. In Proceedings of the 2021 International Conference on Management of Data, p. 2357–2365. External Links: Document Cited by: §1.1, §1.1, §10.2.4, §2.1, Table 1.