{"id":"550d097f-e0e4-40d4-8c0e-3492599c0df7","arxiv_id":"2607.10969","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"CGS greedily merges nodes with common neighborhoods into three configurable summary variants that bound neighborhood loss and support exact or high-accuracy graph queries without full decompression.","lead":"CGS is a configurable graph summarizer that merges nodes sharing neighborhoods into three variants (exact, intersection-only, union-only) with a per-node neighborhood-loss bound, while answering neighborhood, reachability and shortest-path queries on the summary. It gives practitioners controllable one-sided error and better compression than prior lossless and lossy baselines on real and synthetic graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified to the central correctness or bounded-loss claims.","rationale":"The manuscript supplies explicit algorithms, local-safety lemmas, a global correctness theorem, complexity bounds, open-source code, and extensive experiments that together support the strongest claim (bounded one-sided neighborhood loss + competitive compression + query support). The greedy-order concern correctly notes that compression is not proven optimal, yet that fact is already stated by the authors and is orthogonal to the invariant that every produced summary satisfies the user-specified δ-bounds and the query inclusions of Table 2. Higher run-times and missing lossy baselines remain real but non-fatal limitations already reflected in the CONDITIONAL verdict; nothing in the proofs or the experimental design collapses under the proposed check. Hence the reader’s overall assessment stands.","tokens_in":42034,"tokens_out":552,"duration_ms":20873,"concrete_test":"Extend the running example of Table 3 with one additional nested merge (e.g., merge a supernode produced by CGS-I with a third original node that shares a proper subset of neighbors). Manually execute IsSafeMerge + UpdateDegree after each step, then run full Reconstruction (Algo. 10) and compare the resulting deg_Gr(u) values against the degrees predicted by the ancestor arithmetic. Any mismatch >0 would falsify Lemmas 1–2; agreement confirms the invariant holds independently of order.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest assumption (greedy order + local IsSafeMerge/UpdateDegree may later force near-bound or suboptimal configurations) is not load-bearing for the strongest claim. Theorem 1 and Lemmas 1–2 establish that every accepted merge preserves the exact neighborhood-loss invariant (nl(u) ≤ δ_u for all u, with the one-sided inclusions of Eq. 2) by construction: IsSafeMerge (Algo. 5) and UpdateDegree (Algo. 8) recompute potential reconstructed degrees via ancestor sets before any merge is committed, and the reconstruction (Algo. 10) simply materializes the Cartesian products of those ancestors. Order affects only which safe merges occur (hence final |Gs|), not whether the final Gr satisfies the stated bounds or the query characteristics of Table 2. The paper already disclaims optimality of compression ratio (end of Sec. 7). Empirical superiority is likewise only claimed relative to the baselines that could be run (Sec. 10.3–10.4); incomplete coverage is a limitation but does not falsify the reported numbers or the formal guarantees.","agreement_with_reader":"partial"},"referee_report":{"model":"grok-4.5","summary":"The paper introduces ConfiGS and the CGS framework for configurable summarization of undirected unweighted graphs. Nodes (or supernodes) that share common neighborhoods are greedily merged into supernodes under three variants: lossless CGS-E (exact neighborhoods), CGS-I (intersection; only false-negative edges, no false positives), and CGS-U (union; only false-positive edges, no false negatives). A per-node neighborhood-loss tolerance threshold δ_u (or uniform δ) bounds the fractional neighborhood discrepancy after reconstruction. Correctness of the one-sided inclusions, exact reconstruction for CGS-E, and the neighborhood-loss invariant are proved (Theorem 1, Lemmas 1–2); necessary/sufficient conditions for positive compression and a detailed complexity analysis (Theorem 5) are given. Local decompression supports neighborhood, reachability and shortest-path queries with the characteristics of Table 2. Experiments on ten SNAP graphs plus BA/ER families report compression ratios, reconstruction error, query accuracy and wall-clock times against SLUGGER, MoSSo, SWeG, GraphZip and SSumM, claiming superior or competitive compression and high query accuracy.","tokens_in":42382,"tokens_out":1113,"duration_ms":9296,"significance":"If the claims hold, CGS fills a genuine gap: a single framework that lets the user choose lossless versus one-sided lossy reconstruction, bound per-node neighborhood loss, and answer standard graph queries on the summary without full decompression. The formal guarantees (exact or one-sided neighborhoods with nl(u) ≤ δ_u) are stronger than most prior lossy summarizers that only report aggregate reconstruction error. The public C++ implementation and the breadth of the experimental suite (real + synthetic, compression + queries + scalability) make the contribution reproducible and practically usable. The work is therefore of clear interest to the graph-mining and data-management communities.","major_comments":[{"comment":"The experimental comparison for lossy methods is limited to SSumM (Sec. 10.2.4, Figs. 5–9). The authors correctly note that the lossy variant of SWeG and several other competitors (LDME, GraSS, etc.) were unavailable or produced negative compression after format conversion. Because the central empirical claim is “superior summarization than the state-of-the-art,” the paper should either (a) obtain or re-implement at least one additional recent lossy baseline that supports bounded error, or (b) explicitly qualify the claim as “superior to the publicly runnable baselines we could evaluate.” Without this, the strength of the empirical superiority statement remains overstated relative to the evidence presented.","section":null},{"comment":"Complexity (Theorem 5) is O(m d*^3 log n) for CGS-E and higher for the lossy variants. On the denser SNAP graphs (GF, AP, HP) and on the larger synthetic instances the reported wall-clock times already reach hours (Figs. 21–24). The paper never discusses whether the cubic dependence on maximum degree can be mitigated (sampling of candidate pairs, approximate heaps, parallelization, etc.). Given that the abstract advertises “efficiency,” a short discussion of practical scalability limits and possible algorithmic improvements is needed for the claim to be fully credible.","section":null}],"minor_comments":[{"comment":"Table 1 lists many related methods; a short paragraph explaining why the chosen baselines are the most competitive among those that support both lossless/lossy modes and query answering would help the reader.","section":null},{"comment":"Notation for reconstructed degree deg_Gr(u) is introduced in Algo. 1 and used heavily in IsSafeMerge/UpdateDegree, yet never formally defined in the main text; a one-line definition would improve readability.","section":null},{"comment":"In Sec. 10.3.1 the authors observe that denser graphs compress better under CGS-E; a brief theoretical remark linking this observation to Theorems 2–4 would strengthen the narrative.","section":null},{"comment":"Figures 2–7 would benefit from error bars or at least a statement that each bar is a single deterministic run (the algorithm is deterministic once δ is fixed).","section":null},{"comment":"A few typographical inconsistencies remain (e.g., “ConfiGS” vs. “CGS”, occasional missing spaces around mathematical operators).","section":null}],"recommendation":"minor_revision","confidential_remarks":"The formal core (correctness of the neighborhood-loss invariant under the ancestor-based degree updates) is solid and the greedy-order concern raised by the reader is correctly non-load-bearing. The main weaknesses are the incomplete lossy baseline suite and the lack of discussion of the cubic-degree complexity; both are addressable in a minor revision. I would accept after those two points are handled."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The useful thing here is a clean three-variant framework (exact / intersection / union) that gives the user explicit one-sided error control and a per-node neighborhood-loss budget δ_u, enforced without correction edges, plus local-decompression query support that inherits the same bounds. That combination is not in SWeG, SSumM, SLUGGER or MoSSo.\n\nWhat they do well: the reconstruction and loss invariants are actually proved (Thm 1 + Lemmas 1–2), complexity is derived carefully (Thm 5), and they ship code plus ten SNAP graphs plus BA/ER families. Compression numbers look better than the baselines they could run, average neighborhood loss stays well below the stated δ, and reachability/shortest-path accuracy is high (CGS-U is exact on reachability). The local-vs-global decompression trade-off is measured honestly. Table 1 and the related-work section are thorough.\n\nSoft spots, in proportion: the algorithm is greedy and they correctly disclaim optimality of the compression ratio; order can only affect which safe merges fire, not the final loss bounds, so the reader’s “weakest assumption” is not load-bearing for the strongest claim. Runtime is higher than the competitors (minutes to hours on million-edge graphs); that is a real engineering cost, not a correctness problem. A few lossy baselines could not be compared because code or formats were unavailable; the reported numbers still stand against what was runnable. No hidden free parameters beyond the user knob δ.\n\nThis is for people who already care about graph summarization / compression systems and want configurable one-sided error plus query support without full decompression. It is not a new scientific domain, but it is a careful, reproducible algorithmic contribution that a serious referee should see. I would accept it for peer review and would cite the framework when I next need one-sided neighborhood guarantees.","headline":"Solid, configurable one-sided-error graph summarizer with real proofs, open code, and competitive compression; runtime and baseline gaps are real but secondary.","tokens_in":42958,"tokens_out":509,"would_cite":true,"duration_ms":5904,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"A graph summary can be made lossless or one-sided-lossy with a per-node neighborhood-loss bound, while still answering neighborhood, reachability and shortest-path queries accurately.","keywords":["graph summarization","graph compression","common neighborhoods","bounded neighborhood loss","query support","lossless and lossy variants","supernode merge"],"falsifier":"On a graph known to contain many overlapping neighborhoods, run the algorithm with a moderate δ and measure the final neighborhood losses; if any node exceeds its prescribed δ_u, or if a different merge order yields a strictly smaller summary that still respects the same δ, the safety claim fails.","tokens_in":42985,"feed_emoji":"🗜️","tokens_out":584,"duration_ms":7537,"temperature":0.7,"pith_summary":"Large graphs are hard to store and query. Existing summarizers either give no user control over the kind or amount of error, or force a full decompression before any query can be answered. This paper shows that nodes that share many neighbors can be merged into supernodes so that the reconstructed graph either matches the original exactly, contains only missing edges, or contains only extra edges, and that a simple per-node fractional threshold keeps every neighborhood loss inside a user-chosen bound. Because the bound is maintained on neighborhoods, neighborhood queries become exact or bounded, and reachability and shortest-path answers inherit the same one-sided guarantees. Experiments on real and synthetic graphs report better compression ratios than current lossless and lossy baselines while the queries remain accurate and fast enough for practical use.","feed_headline":"Graph summaries that stay exact or one-sided-lossy","feed_subtitle":"Per-node loss bounds let neighborhood, reachability and path queries run accurately on the summary","key_machinery":"Safe greedy merge of 2-hop neighbors: at every step the pair with highest compression gain is tested against the ancestor-degree update rules; if the projected neighborhood loss stays ≤ δ_u the merge is performed and the heap is updated, otherwise it is discarded.","core_discovery":"Three merge rules—exact common-neighborhood (CGS-E), intersection (CGS-I) and union (CGS-U)—together with a safety check that never lets any node’s neighborhood deviate by more than a prescribed fraction δ_u, produce a summary whose reconstruction and query answers obey exact equality or one-sided inclusion with a hard per-node loss bound.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Exact or one-sided-lossy summaries via common-neighborhood merges","CGS-E/I/U merges with per-node δ_u caps for safe reconstruction","Neighborhood aggregation that never exceeds prescribed loss bounds","Configurable summaries guaranteeing exact or one-sided query fidelity","Bounded neighborhood loss enables accurate queries on compact graphs"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"That repeatedly accepting the single currently safest highest-gain merge never later forces a configuration that violates the global loss bound or leaves better merges unexplored.","fun_headline_variants_meta":{"raw":{"variants":["Exact or one-sided-lossy summaries via common-neighborhood merges","CGS-E/I/U merges with per-node δ_u caps for safe reconstruction","Neighborhood aggregation that never exceeds prescribed loss bounds","Configurable summaries guaranteeing exact or one-sided query fidelity","Bounded neighborhood loss enables accurate queries on compact graphs"]},"model":"grok-4.5","effort":"low","cost_usd":0.004886,"raw_usage":{"total_tokens":1471,"prompt_tokens":889,"num_sources_used":0,"completion_tokens":88,"cost_in_usd_ticks":48860000,"prompt_tokens_details":{"text_tokens":889,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":494,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":889,"tokens_out":88,"duration_ms":4827,"temperature":1.0,"reasoning_tokens":494,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T07:58:01.614155+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On a graph known to contain many overlapping neighborhoods, run the algorithm with a moderate δ and measure the final neighborhood losses; if any node exceeds its prescribed δ_u, or if a different merge order yields a strictly smaller summary that still respects the same δ, the safety claim fails.","supporting_citations":[],"review_version":1}