{"id":"6a9383e6-0bc8-46b4-aa66-8f113a5669af","arxiv_id":"2504.13034","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A graph compression scheme that merges inference-equivalent nodes so GNN inference can run on a smaller graph with no or little decompression, claiming 55-85% inference cost reduction with small accuracy loss.","lead":"This paper proposes a way to shrink a large graph before running a graph neural network, by merging nodes that would receive identical predictions, so inference queries run on the smaller graph. It reports large speedups on citation, product, and synthetic graphs, but the exactness guarantee for attention-based networks is conditional and the key proof has a gap.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3 relies on an aggregation invariance that structural equivalence does not guarantee for degree- or attention-weighted GNNs, so the exactness claim is unsupported as stated.","rationale":"The reader identified the same core weakness: structural equivalence lacks degree and attention invariants needed by GCN/GAT updates, and the equality premise is false. My analysis confirms this is the load-bearing issue. The paper's proofs are deferred externally, and the in-text proof sketch glosses over the coefficient mismatch. The counterexample test is straightforward and decisive, so the verdict REJECT is appropriate.","tokens_in":461,"tokens_out":757,"duration_ms":108298,"concrete_test":"Construct a minimal graph where two nodes have the same features and their neighbors are pairwise structurally equivalent, but the two nodes have different degrees, e.g., v with one neighbor a, and v' with two neighbors a and a' where a and a' are distinct but structurally equivalent. Run the paper's SPGC, apply the Table 4 rewritten GCN update with the memoized counts, and compare the exact GCN embeddings on the original graph. If the recovered embedding differs from the original GCN output at any layer, Theorem 3's inference-equivalence claim for GCN is refuted. For GAT, use any graph with structurally equivalent nodes but different attention coefficients and check if the output changes.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim is that SPGC preserves GNN inference exactly. Theorem 3 states that any structural-equivalence pair is inference-equivalent for a whole GNN class, and Lemma 2 turns this into an IFGC guarantee. The proof sketch in Section 4.1 argues inductively that a matching relation preserving intermediate embeddings suffices. This is true only if the node update function treats matched neighbors with identical weights. In GCN (Table 3), the coefficient for neighbor u of v includes 1/sqrt(deg(v)deg(u)). Structural equivalence, as defined in Section 4.1, does not require equal degrees; it only pairs neighbors one-to-one. Two equivalent nodes with different degrees will therefore receive different GCN messages even when their matched neighbors have identical embeddings. The paper's own Table 4 acknowledges this by inserting scaling factors, but those factors restore the original output only when the memoization table records, per neighbor class, the sum of coefficients. The proof of Lemma 2 asserts the node update can be rewritten as a weighted aggregation over the compressed graph with pre-stored weights, but it does not show that these weights always succeed for GCN. Concretely, for a class [u] with multiple members having distinct degrees, the term 1/sqrt(deg(v)deg(u)) factors into a node-specific and a neighbor-specific part only if the product structure holds; in general, compressing [u] into a single edge weight loses the per-neighbor degree information required for exact restoration. The same issue applies to GAT, where attention weights are learned and structure-dependent; structural equivalence says nothing about equal attention. The paper explicitly lists GCN, GAT, and GraphSAGE as target models, so Theorem 3 is false or incomplete for exactly the models in its experimental table. The approximate (alpha, r)-SPGC may still be useful, but the exactness guarantee that underpins the paper's main contribution does not follow from the stated premises.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes inference-friendly graph compression (IFGC): given a graph G and a class of GNNs M_c, a compressor C produces a smaller graph G_c and a post-processor P such that M(G) = M(P(G_c)) for every GNN M in M_c. It introduces an inference-equivalence relation, claims that structural equivalence is inference equivalence (Theorem 3), and instantiates the framework as structural-preserving compression (SPGC), a configurable (α,r)-SPGC, and anchored SPGC (ASPGC), together with memoization tables for scaling factors. Experiments on Cora, Arxiv, Yelp, Products, and billion-scale synthetic graphs report compression ratios, inference speedups, and accuracy/F1 comparisons against DSpar and FGC. The manuscript is a combined technical report containing two full-length works: an ExGIS system paper and the IFGC paper under revision.","tokens_in":51317,"tokens_out":9634,"duration_ms":108169,"significance":"If the exactness theorem were sound, the paper would offer a valuable model-agnostic, once-for-all compression scheme for GNN inference, with linear-time compression and inference cost depending on the compressed graph rather than the original graph. The algorithmic ideas are clearly presented, and the large-scale experimental study is a strength. However, the central exactness guarantee is not valid as stated: structural equivalence does not preserve degree-normalized or attention-weighted aggregation for the very GNN classes in Table 3, and the key proofs are deferred to an external full version. The contribution is therefore currently unsupported, despite the attractive framing and extensive evaluation.","major_comments":[{"comment":"","section":"Section 4.1, Theorem 3"},{"comment":"","section":"Section 3, Lemma 2 and Table 4"},{"comment":"","section":"Section 4.2 and Appendix A"},{"comment":"","section":"Section 6, Fig. 7 and Appendix C, Table 9"}],"minor_comments":[{"comment":"","section":"Overall structure"},{"comment":"","section":"Section 5.1, (α,r)-relation"},{"comment":"","section":"Table 4 and Figure 4"},{"comment":"","section":"Section 2, GNN classes"}],"recommendation":"reject","confidential_remarks":"The paper repeatedly cites its own GitHub full version [1] for the central proofs, and the exactness theorem is false as stated for the GCN and GAT classes that the experiments target. A repair would require redefining structural equivalence to include degree and attention invariants, reworking the cost analysis for the memoization structure, and adding self-contained proofs. This is a substantial revision of the theoretical core rather than a local fix; I recommend rejection, though the underlying idea of degree-aware bisimulation compression for GNNs may be worth pursuing in a future submission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: the central exactness claim doesn't hold as stated. Theorem 3 says structural equivalence is an inference equivalence for a whole GNN class, and the proof sketch asserts that matched neighbors with equal embeddings give equal aggregates. That's only true if the update coefficients are identical for matched neighbors. For GCN the coefficient is 1/sqrt(deg(v)deg(u)); structural equivalence doesn't force equal degrees or multiplicities, so two equivalent nodes can get different messages. For GAT the attention weights are learned and model-specific, so a once-for-all compression cannot cache them for every GNN in the class. The paper's Table 4 hints at scaling factors in the memoization table T, which could in principle repair the GCN case—store the sum of per-neighbor-class degree terms and multiply by the node's own degree at inference—but the proof doesn't show this, and the theorem as written is false. This is load-bearing: the paper's headline is exact inference on the compressed graph with no decompression.\n\nWhat's genuinely new: the IFGC formulation with a memoization table that supports a rewritten inference pass, and the two configurable variants, (alpha,r)-SPGC and anchored SPGC, are not in the cited Exact Compression [10] or GRAPE [51] work. The experiments are extensive and show real speed-ups (55–85% inference cost reduction) with modest accuracy loss on real benchmarks. The (alpha,r)-SPGC approximate scheme is less affected by the theorem issue and might survive as a practical method. The paper ships code and data, and the citation pattern is fine—self-citing the full version for missing proofs is annoying but not fatal.\n\nSoft spots, in proportion. The exactness proof in Appendix A is hand-waved and the detailed proofs are deferred to an external PDF. The definition of structural equivalence lacks the invariants needed for degree-normalized or attention-based updates, so Theorem 3 is at best incomplete and at worst false for GCN and GAT. Experiments have no error bars, and the claimed exactness is not reflected in any accuracy-preservation metric. The arXiv text is also a combined technical report that includes a separate demo paper (ExGIS), which makes it longer and less focused.\n\nWho this is for: people working on GNN inference systems and graph coarsening. The idea is worth a serious look, but only with the exactness claim repaired or downgraded. My recommendation: send it to peer review; it deserves referee time. The authors should either prove the scaling-factor rewrites for each architecture or reposition SPGC as an approximate method. As it stands, I'd reject until that's fixed.","headline":"Clever compression idea with a load-bearing exactness proof that doesn't hold for degree- or attention-weighted GNNs; the approximate variant might be salvageable.","tokens_in":51917,"tokens_out":5922,"would_cite":false,"duration_ms":60182,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that graph compression can be inference-friendly: merging structurally indistinguishable nodes yields a compressed graph on which any matching GNN's inference returns exactly the original output.","keywords":["graph neural networks","inference-friendly compression","inference equivalence","structural equivalence","graph coarsening","quotient graph","memoization","GNN inference acceleration"],"falsifier":"Run a fixed two-layer GCN on a graph with two nodes $u,v$ that have identical input features and bisimilar neighborhoods but different degrees (for instance, $u$ in a 2-cycle and $v$ in a 3-cycle). SPGC would merge them. Compute the exact first-layer embeddings: if $h_u^{(1)} \\neq h_v^{(1)}$ for some weight matrix, then structural equivalence is not an inference equivalence relation for the GCN class, contradicting Theorem 3.","tokens_in":50826,"feed_emoji":"🗜️","tokens_out":7339,"duration_ms":70361,"temperature":0.7,"pith_summary":"This paper tries to establish that graph compression can be made inference-friendly: instead of approximating the graph and re-running a GNN, one can merge nodes that are provably indistinguishable to a whole class of GNNs and then run inference directly on the compressed graph, recovering the original output by rescaling with cached statistics. The payoff is that one offline compression serves many inference queries and many GNNs with the same update form, and only the compressed graph is touched at query time. The paper gives three concrete schemes—SPGC with exact no-decompression inference, $(\\alpha,r)$-SPGC with a tunable compression-quality trade-off, and anchored SPGC for a designated set of nodes—and reports large speedups on real and synthetic graphs. The load-bearing claim is Theorem 3: structural equivalence is an inference equivalence relation, so the quotient graph plus a scaling-factor-restoring post-processor is an IFGC.","feed_headline":"One compression run makes GNN inference exact on a smaller graph","feed_subtitle":"Merges provably indistinguishable nodes once, so any matching GNN queries the compressed graph with no decompression.","key_machinery":"The central object is the inference equivalence relation $r_f^c$: node pairs whose embeddings coincide at every layer for every GNN in the class. The practical engine is structural equivalence $r_m$—two nodes are equivalent when features match and each neighbor of one has a matching neighbor of the other under the same relation. SPGC computes the maximum such relation with a DPP-style partition refinement, builds the quotient graph, and writes a memoization table whose entries are scaling factors (degrees, edge weights, counts) used by the rewritten update function. The theorem does the work: $r_m$ is claimed to be an inference equivalence relation, so Lemma 2 turns any quotient graph of it into an IFGC.","core_discovery":"The paper's central discovery is that inference of a whole class of GNNs can be made invariant to merging exactly the node pairs that are structurally equivalent: nodes with identical input features and neighborhoods that can be matched pairwise by the same relation. Merging those pairs yields a quotient graph $G_c$; a memoization table caches the neighbor statistics (degrees, edge weights, counts) that the update function needs, and a rewritten update function runs directly on $G_c$ and rescales embeddings to recover the original outputs. The paper claims this gives $M(G) = M(P(G_c))$ for every GNN $M$ in the class, with no decompression, and that the resulting compressed graph is the unique smallest one up to isomorphism.","pith_inferences":["Editorial extension: the exactness proof assumes matched neighbors contribute equally at the next layer, which is true for sum or average aggregation with identical coefficients but not for degree-normalized GCN or attention-based GAT; enforcing equal degrees or equal attentions inside the equivalence relation would repair the proof but shrink the compression ratio.","Editorial extension: the worst-case bound for $(\\alpha,r)$-SPGC with decompression is the same order as inference on the original graph; the practical speedup therefore lives in how often the decompression routine can stop early, which the experiments measure but the theory does not guarantee.","Editorial extension: the framework suggests a simple empirical test for graph compressibility—count nodes that are role-equivalent under structural equivalence; real-world networks like citation graphs already show large fractions, so the approach transfers to settings where role structure is strong."],"forward_implications":["If SPGC is correct, any GNN in the class can answer queries on $G_c$ alone, with outputs restored from the memoization table, so inference cost scales with the compressed graph rather than the original.","The once-for-all nature means the same compressed graph serves many GNNs that share the node-update form and many query node sets, making the compression cost amortize over large workloads.","Anchored compression gives a targeted version: outputs for a designated anchor set are preserved with cost bounded by the $L$-hop neighborhood of those anchors, so queries on a few nodes of interest compress far more aggressively.","Configurable $(\\alpha,r)$-compression trades exactness for size: larger similarity thresholds and wider hop ranges increase compression but require partial decompression at inference time.","SPGC preserves the discriminative set of the GNN class, so graph-level questions about which graphs receive the same embeddings can be answered on compressed graphs without changing the class's answer."],"supporting_citations":[{"why":"Full version containing the complete proofs of Lemma 2, Theorem 3, and the decompression algorithms that the paper's claims depend on.","marker":"[1]"},{"why":"Supplies the DPP partition-refinement algorithm that SPGC extends to compute the maximum structural equivalence relation.","marker":"[16]"},{"why":"Defines the GCN node update function whose degree normalization determines the scaling-factor form for topology-sensitive compression.","marker":"[31]"},{"why":"Defines attention-weighted aggregation, the weight-sensitive case the memoization table must cache.","marker":"[49]"},{"why":"Provides the neighborhood-aggregation update used to demonstrate the framework on GraphSAGE-style GNNs.","marker":"[24]"},{"why":"Introduces structural equivalence from social network analysis, the role-equivalence notion the paper extends to embeddings and neighborhoods.","marker":"[38]"},{"why":"Supplies the inference-query perspective and the discriminative-set criterion used to express GNN expressiveness.","marker":"[23]"},{"why":"The exact-compression color-refinement baseline compared against SPGC to show where stricter merging loses compression opportunity.","marker":"[10]"}],"fun_headline_variants":["Merge indistinguishable nodes once, get exact GNN outputs always","Exact GNN inference on compressed graph with no decompression","One-time compression yields exact GNN results on smaller graph","Structurally merging nodes gives lossless GNN inference on compressed","Compress graph to quotient, GNN inference stays exact without unpacking"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee stands on the premise that matched neighbors with equal intermediate embeddings always contribute identically to the next layer; for GCN and GAT, contributions also depend on degrees or learned attention weights, which the matching does not force to be equal.","fun_headline_variants_meta":{"raw":{"variants":["Merge indistinguishable nodes once, get exact GNN outputs always","Exact GNN inference on compressed graph with no decompression","One-time compression yields exact GNN results on smaller graph","Structurally merging nodes gives lossless GNN inference on compressed","Compress graph to quotient, GNN inference stays exact without unpacking"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000556,"raw_usage":{"total_tokens":2646,"prompt_tokens":942,"completion_tokens":1704,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":558,"completion_tokens_details":{"reasoning_tokens":1618}},"tokens_in":558,"tokens_out":1704,"duration_ms":15701,"temperature":1.0,"reasoning_tokens":1618,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T12:17:32.258110+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a fixed two-layer GCN on a graph with two nodes $u,v$ that have identical input features and bisimilar neighborhoods but different degrees (for instance, $u$ in a 2-cycle and $v$ in a 3-cycle). SPGC would merge them. Compute the exact first-layer embeddings: if $h_u^{(1)} \\neq h_v^{(1)}$ for some weight matrix, then structural equivalence is not an inference equivalence relation for the GCN class, contradicting Theorem 3.","supporting_citations":[{"cited_title":"Full version","cited_arxiv_id":null,"evidence_quote":"Full version containing the complete proofs of Lemma 2, Theorem 3, and the decompression algorithms that the paper's claims depend on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the DPP partition-refinement algorithm that SPGC extends to compute the maximum structural equivalence relation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the neighborhood-aggregation update used to demonstrate the framework on GraphSAGE-style GNNs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces structural equivalence from social network analysis, the role-equivalence notion the paper extends to embeddings and neighborhoods."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the inference-query perspective and the discriminative-set criterion used to express GNN expressiveness."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The exact-compression color-refinement baseline compared against SPGC to show where stricter merging loses compression opportunity."}],"review_version":1}