{"id":"ce80b204-e433-4a37-82bb-df2464c40403","arxiv_id":"2412.09968","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"GraSP, a GNN architecture using positional encodings, gated residual convolutions, and multi-scale pooling, predicts graph edit distance and maximum common subgraph size more accurately and faster than ten baselines on four benchmark datasets.","lead":"GraSP is a graph neural network that predicts how different two graphs are by measuring graph edit distance and maximum common subgraph size without comparing every node of one graph to every node of the other. It reports better accuracy and faster inference than ten existing methods on four standard graph datasets.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The expressive-power claim is not established: RWPE does not separate all 1-WL-inseparable pairs (regular same-parameter graphs give identical return probabilities), and the Appendix proof's pooling step is non-injective.","rationale":"The reader's conditional verdict is appropriate, and the proof of Proposition 1 is indeed the main soft spot. My analysis agrees with the reader that the Appendix proof's move from distinct node-feature multisets to distinct graph embeddings is invalid, since summation and attention pooling are not injective readouts and the GNN layers themselves can collapse distinct multisets. However, I would locate the more fundamental problem one step earlier: RWPE is not a complete invariant, and for same-parameter strongly regular graphs, which are classic 1-WL-inseparable pairs, the initial RWPE multisets are identical for every k. The paper's own sensitivity appendix overclaims a guarantee that large k separates non-isomorphic graphs. This matters because the theoretical contribution is advertised in the abstract and contributions as 'can surpass the 1-WL test,' and a conditional theorem whose premise is not satisfied on a natural class of 1-WL-inseparable graphs cannot support that broader claim. I do not see the approximate GED labels on IMDBMulti and PTC as the most load-bearing issue: the paper discloses this clearly, all baselines are trained against the same labels, and the main empirical trend also holds on the exact-label datasets AIDS700nef and LINUX and for exact MCS labels. The empirical claim should therefore stand, but the expressive-power claim needs either a corrected proof with a genuinely distinguishing positional encoding and an injective readout, or an explicit softening. Because the reader already issued CONDITIONAL, my read does not change the verdict; it sharpens the condition the authors must satisfy.","tokens_in":20268,"tokens_out":8536,"duration_ms":107098,"concrete_test":"Run RWPE with k=1..16 on the Shrikhande graph and the 4x4 rook's graph, two non-isomorphic strongly regular graphs with parameters (16,6,2,2) that are indistinguishable by 1-WL. Compare the multisets {p_i^init} of return probabilities; if, as expected, they are identical for all k, the paper's premise that RWPE separates 1-WL-inseparable pairs fails and Proposition 1 is vacuous for these graphs. A secondary check is to feed the two graphs through the trained GraSP checkpoint and verify whether the final graph embeddings coincide despite the claimed expressiveness.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theoretical expressiveness claim rests on Proposition 1 and its Appendix proof, and two unproved steps are load-bearing. First, the paper assumes RWPE supplies different initial feature multisets for any 1-WL-inseparable pair, asserting in the sensitivity appendix that for large k this 'can be guaranteed.' This is false: for two non-isomorphic d-regular graphs with the same degree and the same closed-walk counts, e.g., the Shrikhande graph and the 4x4 rook's graph (both strongly regular with parameters (16,6,2,2), and both indistinguishable by 1-WL), every vertex has the same return-probability sequence, so the RWPE multisets are identical for every k. Thus the precondition of Proposition 1 fails for an entire family of 1-WL-inseparable graphs, and no GNN or pooling design can rescue that case. Second, even when the initial feature multisets differ, the proof's final inference is invalid: z_sum = sum_i h_i is not injective over multisets, z_att is also non-injective, the learned interpolation weight a in Eq. (5) does not restore injectivity, and the RGGC layers in Eq. (3) with ReLU and learned matrices can collapse distinct multisets. Distinct initial node features therefore do not imply distinct graph embeddings. The paper has not shown that GraSP surpasses 1-WL; at most it shows a conditional separation under unverified assumptions. The empirical SOTA claims are separate and substantially supported by exact-label datasets (AIDS, LINUX) and exact MCS labels, so the appropriate fix is to re-prove or soften the theoretical claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"GraSP is a graph-similarity prediction model for estimating graph edit distance (GED) and maximum common subgraph (MCS). The architecture enhances node features with random-walk positional encodings (RWPE), processes them through stacked ResGatedGraphConv layers, pools node representations via a learned convex combination of attention and sum pooling, and predicts GED/MCS using a weighted combination of Euclidean distance and a Neural Tensor Network interaction term. The paper reports experiments against ten baselines on AIDS700nef, IMDBMulti, LINUX, and PTC, claiming state-of-the-art MAE, rank correlation, and precision-at-k in most settings, lower inference time, and ablations supporting each component. It also claims a theoretical result (Proposition 1) that GraSP can generate different graph representations for non-isomorphic graphs that the 1-WL test cannot distinguish, with a proof in the appendix.","tokens_in":20634,"tokens_out":7118,"duration_ms":83393,"significance":"The empirical core of the paper is valuable. On the two datasets with exact GED ground truth (AIDS700nef, LINUX) and for MCS with exact MCSPLIT labels, GraSP consistently outperforms the baselines by a wide margin on most metrics, and the efficiency comparison supports the design choice of omitting cross-graph node-level interactions. The paper also provides code, hyperparameter settings, sensitivity analysis, ablations, heatmaps, and generalization experiments, which is a concrete reproducibility asset. The theoretical expressiveness claim, however, is not established by the current proof: the pooling operation is non-injective, and the RWPE precondition of Proposition 1 does not hold for all 1-WL-inseparable graph pairs. These issues do not invalidate the empirical findings, but they require the theoretical claim to be repaired or substantially weakened before the paper can be accepted.","major_comments":[{"comment":"The proof of Proposition 1 is invalid in its final inference. From the fact that the multisets of initial node representations {h_u^(0)} and {h_v^(0)} differ, the proof concludes that the final graph embeddings differ. This does not follow: the sum pooling z_sum = sum_i h_i and the attention pooling z_att defined before Eq. (5) are not injective multiset readouts, and the learned vector a in Eq. (5) does not restore injectivity. Two different multisets of node vectors can have the same sum or the same attention-weighted sum, and the RGGC layers in Eq. (3) with ReLU and learned matrices can also collapse distinct inputs. The proof needs either an injective pooling map whose injectivity is proven under the stated assumptions, or a revised claim limited to separation at the node-representation level rather than the graph-embedding level.","section":"Analysis of GRASP and Appendix: Proof of Proposition 1"},{"comment":"The precondition of Proposition 1, that the two graphs have different sets of initial RWPEs, is asserted to hold for non-isomorphic graphs when k is sufficiently large ('it can be guaranteed'), but this is false. The Shrikhande graph and the 4x4 rook's graph are non-isomorphic, 1-WL-indistinguishable strongly regular graphs with the same parameters (16,6,2,2), and every vertex in both graphs has the same Rayleigh quotient / closed-walk return sequence for every step k, so the multisets of RWPE features are identical for all k. Proposition 1 therefore does not cover an infinite family of 1-WL-inseparable pairs, and the conclusion 'GraSP can surpass the 1-WL test' is not established. The authors should either restrict the claim to graphs for which the RWPE multisets are guaranteed to differ, use a positional encoding with a proven separation guarantee, or explicitly acknowledge the limitation.","section":"Analysis of GRASP and Appendix sensitivity analysis"},{"comment":"For IMDBMulti and PTC, the ground-truth GED is not exact but is defined as the minimum of the Beam, Hungarian, and VJ approximations. All MAE, rank-correlation, and precision-at-k numbers in Tables 1-2 for these datasets are therefore computed against approximate targets, and the reported superiority on IMDBMulti and PTC is conditional on the quality of those heuristics. The main text should state this limitation clearly when the datasets are introduced, and ideally the authors should report a comparison on a subset with exact GED values or quantify the heuristic error, especially because PTC has larger graphs where the approximation gap is likely larger.","section":"Experiments: Data and ground truth"},{"comment":"The ablation claim that GraSP outperforms all ablated versions is overstated. In Table 9 on PTC under the GED metric, GRASP (w/o NTN) achieves MAE 3.367, which is lower than the full model's MAE 3.556, even though the full model has better rank-correlation and precision-at-k scores. Similarly, in Table 7 on IMDBMulti, GRASP (w/o pe) and GRASP (w/o NTN) are statistically comparable to the full model on several metrics. The text should qualify the ablation conclusions per metric and per dataset rather than stating that the full model is best on all metrics.","section":"Appendix: Additional ablation studies (Table 9)"}],"minor_comments":[{"comment":"The paper uses 'GRASP', 'GraSP', and 'G RASP' interchangeably; a single consistent spelling should be used in the title, abstract, and body.","section":"Throughout"},{"comment":"Figure 2 is difficult to read in the submitted version; the component labels, tensor shapes, and pooling symbols should be enlarged or vectorized so that the architecture can be inspected.","section":"Figure 2"},{"comment":"The notation z_1^T W_I^{[1:t]} z_2 for the NTN tensor contraction is ambiguous; the authors should define the exact contraction over the tensor slices and specify the output dimensions of each term.","section":"Eq. (7)"},{"comment":"The adaptation of Eq. (8) to MCS is described informally ('we keep the right-hand side of Eq. (8) unchanged and change the left-hand side'); the text should state explicitly that the same prediction head is trained with MCS targets and explain how the distance and interaction terms are combined for a similarity objective.","section":"Paragraph after Eq. (8)"},{"comment":"The complexity analysis states that RWPE pre-computation takes O(k|V|^2) but then excludes it as a preprocessing step; the authors should clarify whether this cost is paid once per graph, amortized over all graph pairs, and how it affects the end-to-end comparison with baselines.","section":"Complexity analysis"},{"comment":"The final paragraph says GraSP 'passes the 1-WL test', but Proposition 1 claims it surpasses the 1-WL test; the wording should be corrected to avoid implying that the model is only as expressive as 1-WL.","section":"Conclusion"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a strong empirical systems paper for a graph-similarity audience, and the exact-label experiments (AIDS700nef, LINUX for GED; all four datasets for MCS) are credible and reproducible. The theoretical expressiveness section, however, is not ready in its present form: the pooling step in the proof of Proposition 1 is non-injective, and the RWPE precondition fails on standard 1-WL-inseparable pairs such as the Shrikhande and 4x4 rook's graphs. I recommend major revision rather than rejection because the empirical contribution is solid and the theoretical claim can in principle be repaired with an injective readout and a restricted condition, or weakened to a conditional statement. The approximate GED ground truth on IMDBMulti and PTC and the ablation inconsistencies should also be disclosed in the revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about GraSP before reading further: the empirical case is genuinely strong, and the theoretical case is not. On four standard GED/MCS benchmarks the method tops or near-tops every metric, usually with larger margins than the noise, and the inference-time plot shows it is fast. The code is posted, and the exact-label datasets (AIDS, LINUX) give the MAE numbers a solid anchor. That part is worth taking seriously.\n\nWhat's actually new is the specific combination: RWPE node features, RGGC backbone, multi-scale attention+sum pooling, and no cross-graph node interactions. Each ingredient is known, and EGSC/GREED already showed you can drop the cross-graph matching. But nobody had put these pieces together for GED/MCS, and the benchmark gains are real. The paper is also clearly written, and the ablation study is unusually complete.\n\nThe soft spots are real but mostly isolated to the theory. Proposition 1 claims GraSP surpasses the 1-WL test, but the appendix proof skips from distinct initial RWPE multisets to distinct graph embeddings. That step fails: sum pooling and attention pooling are not injective over multisets, and the learned blend weight doesn't fix it. Worse, the proof's opening assumption—that RWPE distinguishes every 1-WL-inseparable pair—is false: two cospectral regular graphs like the Shrikhande graph and the 4×4 rook graph have identical return probabilities for every step, so the 'different positional encodings' precondition already fails. The paper even asserts in the sensitivity appendix that large k 'can be guaranteed' to separate non-isomorphic graphs, which is simply not true. So the expressiveness claim is unproven, and the honest fix is to re-prove it under a narrower condition or retract it.\n\nTwo smaller issues. IMDBMulti and PTC use the minimum of Beam/Hungarian/VJ as ground truth GED, so the absolute error numbers there inherit the heuristics' errors; the rank metrics are more trustworthy. And the ablation story is not as clean as the text suggests: on PTC, removing NTN improves MAE (3.367 vs 3.556), so 'all components help' is at best dataset-dependent.\n\nWho is this for? Practitioners who want a fast, strong GED/MCS estimator will get immediate value. A theorist will find the 1-WL claim not established. My recommendation: send it to review—the empirical contribution deserves referee time—but the authors should be pressed to fix or soften the theory and to be honest about the approximate labels.","headline":"GraSP's empirical results are solid and worth a referee; the 1-WL expressiveness proof does not hold up.","tokens_in":21171,"tokens_out":2899,"would_cite":true,"duration_ms":30908,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","05C60","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"GraSP predicts GED and MCS more accurately and faster than ten baselines by replacing cross-graph node matching with positional encodings and multi-scale pooling.","keywords":["graph similarity computation","graph edit distance","maximum common subgraph","graph neural networks","random walk positional encoding","1-WL test","multi-scale pooling"],"falsifier":"Feed two non-isomorphic, 1-WL-indistinguishable graphs with distinct RWPE multisets through GraSP with trained pooling; if their final graph embeddings coincide, Proposition 1 fails as stated. Separately, computing exact GED on a random subset of IMDBMulti and PTC pairs would show whether the reported MAE advantages survive replacement of the heuristic labels.","tokens_in":1817,"feed_emoji":"📊","tokens_out":1903,"duration_ms":152305,"temperature":0.7,"pith_summary":"GraSP is a graph neural network for estimating graph edit distance (GED) and maximum common subgraph (MCS), two NP-hard similarity measures used in retrieval, drug discovery, and code comparison. The paper argues that the cross-graph node-matching modules used by previous GNN methods are unnecessary: a backbone that embeds each graph independently, enriched with random-walk positional encodings and a multi-scale pooling of node representations, predicts both metrics better than ten baselines on four real-world datasets while running in time linear in the number of nodes. The paper further claims a theoretical expressiveness result: GraSP can distinguish non-isomorphic graphs that the 1-WL isomorphism test cannot, provided the graphs' random-walk positional encodings differ. If correct, this would make accurate graph similarity practical for large graph collections and simplify learned similarity models substantially.","feed_headline":"Simple GNN beats 10 graph similarity rivals without cross-graph matching","feed_subtitle":"Random-walk positional encoding plus multi-scale pooling predict GED and MCS in near-linear time.","key_machinery":"The engine of GraSP is random-walk positional encoding (RWPE) combined with residual gated graph convolution and multi-scale pooling. RWPE gives node $i$ the diagonal entries $(A D^{-1})^\\ell_{ii}$ for $\\ell=1,\\dots,k$, encoding return probabilities of random walks, and these are concatenated with learned label embeddings so initial features carry global topology. The backbone updates these features with residual gated graph convolution (RGGC) layers, where learnable gates control how much neighbor information flows in, and the representations from every layer are concatenated. Multi-scale pooling mixes attention pooling and summation pooling with a learnable per-dimension weight vector $a$, producing $z = a \\odot z_{\\text{att}} + (1-a) \\odot z_{\\text{sum}}$. The prediction head then combines the Euclidean distance of two graph embeddings with a Neural Tensor Network interaction term via a learned scalar $\\beta$. Each component is designed to keep discriminative information while avoiding pair-by-pair node matching, which is what makes the method's complexity effectively linear in graph size.","core_discovery":"GraSP's central claim is that graph similarity prediction does not need cross-graph node-level interaction. The model embeds each graph separately—node labels concatenated with random-walk positional encoding, passed through residual gated graph convolution layers, then pooled by a learnable mixture of attention and summation pooling—and predicts GED or MCS from the Euclidean distance and an NTN interaction term of the two graph embeddings. The paper reports that this design outperforms ten competitors on AIDS700nef, IMDBMulti, LINUX, and PTC, winning all reported metrics for MCS and nearly all for GED, while having the fastest inference time. Proposition 1 states that for non-isomorphic graphs that the 1-WL test cannot distinguish, GraSP produces different graph representations whenever the two graphs have different sets of initial positional encodings, which the paper argues random walks provide for sufficiently large $k$.","pith_inferences":["Beyond the paper: because GraSP embeds each graph independently, all database graphs can be embedded once and cached, so a similarity query becomes a nearest-neighbour search over precomputed vectors rather than a fresh pair-wise evaluation.","Beyond the paper: the proof of Proposition 1 would become unconditional if the pooling step were replaced by an injective aggregation such as sorted or histogram-based pooling, a small architectural change that directly tests the theoretical claim.","Beyond the paper: setting the random-walk length $k$ above the graph diameter would more reliably satisfy the precondition that non-isomorphic graphs have distinct positional-encoding multisets, and this could be validated across the four datasets as a hyperparameter principle.","Beyond the paper: the same pair-independent encoder plus distance-and-interaction head could be transferred to other NP-hard graph-pair scores such as subgraph isomorphism counts, since the method does not rely on alignment structure."],"forward_implications":["Cross-graph node-level interaction modules are not necessary for strong GED and MCS prediction, so similarity models can be built from per-graph embeddings alone.","Because positional encodings and graph embeddings can be computed once per graph and reused, online inference is fast: GraSP has the shortest inference time among all compared methods on all four datasets.","Random-walk positional encoding plus residual gated convolution gives graph embeddings that are more discriminative than standard message-passing GNNs bounded by the 1-WL test, under the conditions of Proposition 1.","The same architecture and loss serve both GED and MCS prediction, so switching the target metric requires only changing the regression label, not the model structure.","GraSP generalizes to larger unseen graphs: trained on graphs up to size 25 or 50, it keeps lower GED prediction error than GREED and H2MN on query graphs with 25-50 nodes."],"supporting_citations":[{"why":"Supplies the SimGNN baseline, the attention-pooling and NTN design elements, the benchmark datasets, and the approximate-GED protocol for IMDBMulti and PTC.","marker":"(Bai et al. 2019)"},{"why":"Defines the GraphSim baseline and the connected-MCS convention adopted for the MCS objective.","marker":"(Bai et al. 2020)"},{"why":"Establishes the equivalence between message-passing GNNs and the 1-WL test that Proposition 1 uses as its baseline.","marker":"(Xu et al. 2019)"},{"why":"Provides the random-walk positional encoding (RWPE) used to enhance node features and supports the claim that RWPE distinguishes non-isomorphic graphs for large $k$.","marker":"(Dwivedi et al. 2022)"},{"why":"Provides the residual gated graph convolution layers that form the GNN backbone of GraSP.","marker":"(Bresson and Laurent 2017)"},{"why":"Supplies the Neural Tensor Network used in the interaction term of the prediction head.","marker":"(Socher et al. 2013)"},{"why":"Supplies the GREED baseline, the pair-independent-embedding idea, and the large-unseen-graph generalization protocol.","marker":"(Ranjan et al. 2022)"},{"why":"Supplies the EGSC baseline and the first demonstration that cross-graph node interactions can be omitted, which GraSP builds on for efficiency.","marker":"(Qin et al. 2021)"},{"why":"Supplies the ERIC baseline and the NTN-based weighted cosine interaction that inspires the prediction head.","marker":"(Zhuo and Tan 2022)"},{"why":"Supplies the MCSPLIT algorithm used to compute ground-truth MCS values.","marker":"(McCreesh, Prosser, and Trimble 2017)"}],"fun_headline_variants":["Graph similarity without cross-graph matching: GraSP wins","GraSP: simple GNN beats 10 rivals for graph similarity","No cross-graph steps, yet GraSP tops graph similarity","GraSP predicts graph similarity fast and accurately"],"cache_read_input_tokens":23168,"weakest_assumption_plain":"The claim that GraSP surpasses the 1-WL test rests on the premise that distinct multisets of positional-encoding-enhanced node features must produce distinct pooled graph embeddings, which summation and attention pooling do not guarantee.","fun_headline_variants_meta":{"raw":{"variants":["Graph similarity without cross-graph matching: GraSP wins","GraSP: simple GNN beats 10 rivals for graph similarity","No cross-graph steps, yet GraSP tops graph similarity","GraSP predicts graph similarity fast and accurately"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000549,"raw_usage":{"total_tokens":2631,"prompt_tokens":961,"completion_tokens":1670,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":577,"completion_tokens_details":{"reasoning_tokens":1603}},"tokens_in":577,"tokens_out":1670,"duration_ms":13833,"temperature":1.0,"reasoning_tokens":1603,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:30:37.256056+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Feed two non-isomorphic, 1-WL-indistinguishable graphs with distinct RWPE multisets through GraSP with trained pooling; if their final graph embeddings coincide, Proposition 1 fails as stated. Separately, computing exact GED on a random subset of IMDBMulti and PTC pairs would show whether the reported MAE advantages survive replacement of the heuristic labels.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the SimGNN baseline, the attention-pooling and NTN design elements, the benchmark datasets, and the approximate-GED protocol for IMDBMulti and PTC."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the GraphSim baseline and the connected-MCS convention adopted for the MCS objective."},{"cited_title":"P.; Luu, A","cited_arxiv_id":null,"evidence_quote":"Provides the random-walk positional encoding (RWPE) used to enhance node features and supports the claim that RWPE distinguishes non-isomorphic graphs for large $k$."},{"cited_title":"D.; and Ng, A","cited_arxiv_id":null,"evidence_quote":"Supplies the Neural Tensor Network used in the interaction term of the prediction head."},{"cited_title":"T.; Sabharwal, Y.; and Ranu, S","cited_arxiv_id":null,"evidence_quote":"Supplies the GREED baseline, the pair-independent-embedding idea, and the large-unseen-graph generalization protocol."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the EGSC baseline and the first demonstration that cross-graph node interactions can be omitted, which GraSP builds on for efficiency."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the ERIC baseline and the NTN-based weighted cosine interaction that inspires the prediction head."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the MCSPLIT algorithm used to compute ground-truth MCS values."}],"review_version":1}