{"id":"b144fa32-ef83-41cd-b4d1-67461993c88d","arxiv_id":"2505.02124","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"An LLM and evolutionary prompt tuning discover a compact set of programs whose node mappings yield tight upper bounds to GED, trained without any ground-truth GED labels.","lead":"GRAIL generates small programs with an LLM, evolves them through prompts, and uses them to compute graph edit distance (GED) approximations. It claims to beat neural and non-neural baselines without needing exact GED values for training.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 and Eq. 6 invert the selection objective: since J(A) is minimized, the marginal J(A∪{P})−J(A) is non-positive, so arg max picks the least useful program.","rationale":"The reader located the weakest point in the LLM's ability to generate useful mutations. My review finds a more basic problem in the selection loop that would undo even a capable LLM. In Section 3.2, J(A) is a sum of upper bounds to be minimized; hence the marginal contribution of adding a program is always non-positive. Algorithm 1 chooses the candidate maximizing that non-positive difference, which is the candidate with the least reduction. Equation 6 uses the same expression as the fitness score, and Section 4.2 favors high scores, so the prompt would be seeded with the worst programs. If this is not a typographical slip, the method as described collapses to the trivial program and cannot produce the reported results. The released code provides a decisive check: either the implementation uses the opposite sign (making the text erroneous but the experiments valid) or it matches the paper (making the experimental numbers inexplicable). Because the resolution is a one-line inspection, the correct verdict remains conditional on that check, not an outright rejection. I therefore disagree with the reader's choice of weakest assumption, while agreeing that CONDITIONAL is the right overall verdict.","tokens_in":17913,"tokens_out":11065,"duration_ms":142244,"concrete_test":"Open the released repository (https://github.com/idea-iitd/Grail) and inspect the implementation of the greedy selection and score computation. Determine whether the code computes arg max of J(A)−J(A∪{P}) (the reduction, as required by minimization) or arg max of J(A∪{P})−J(A) as printed. Then, as an independent check, re-run the selection on the AIDS training set with both variants and compare the resulting test RMSE to Table 3's 0.57. If the as-written variant does not reproduce the reported RMSE (or produces a much worse answer set), the paper's Algorithm 1 and Eq. 6 contain a sign error that must be corrected; if the corrected variant reproduces the results, the text needs an erratum.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2 defines J(A) = Σ_t min_{P∈A} GED_{π(P)}(G_t, G'_t) and states the goal is to minimize J(A). Because the min over a larger set cannot increase, adding a program to A always yields J(A∪{P}) − J(A) ≤ 0. Algorithm 1 line 3 nevertheless chooses P* = arg max_{P} [J(A∪{P}) − J(A)], which selects the candidate with the smallest (least negative) decrease, i.e., the worst program. Equation 6 defines score(P) as this same non-positive quantity, and §4.2 says the evolutionary sampler prefers 'high scores', which would favor programs that barely reduce the upper bound. If the implementation follows the paper's description, the greedy answer set and the prompt-selection pressure are both inverted, and GRAIL cannot discover improving programs; the reported gains would be impossible. This is an internal inconsistency in the central loop, not a disagreement with external consensus. The intended correction is presumably to maximize the reduction J(A) − J(A∪{P}) and to score programs by that positive quantity, but the text as written does not state this.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GRAIL, a framework that uses an LLM in an evolutionary loop to generate executable programs that compute node similarity matrices for maximum-weight bipartite matching. The resulting node mappings yield upper bounds on the true graph edit distance, and a greedy selection chooses a bounded set of complementary programs. The authors report RMSE and exact-match-ratio results on six benchmark datasets, plus a variant (GRAIL-MIX) trained on a mixture of datasets to demonstrate cross-domain transfer. The central claim is that GRAIL achieves competitive or better approximation quality than neural and non-neural baselines without any ground-truth GED supervision during training.","tokens_in":18201,"tokens_out":9736,"duration_ms":105410,"significance":"The idea of replacing a neural regressor with an LLM-evolved program is novel and, if sound, would be a meaningful contribution to the GED approximation literature. The upper-bound formulation is elegant and genuinely avoids the need for NP-hard training labels, in contrast to most neural baselines. The paper also emphasizes interpretability of the discovered programs and releases its codebase, which is a further strength. However, the significance is heavily contingent on the correctness of the evolutionary selection loop and on the reliability of the empirical comparison; the concerns below show that both require substantial revision before the claims can be accepted.","major_comments":[{"comment":"The submodularity inequality is stated in the wrong direction. For A′ ⊆ A, the marginal decrease from adding P is larger for the smaller set; a concrete assignment shows J(A∪{P})−J(A) ≥ J(A′∪{P})−J(A′) rather than the reverse. For example, with a single graph pair and costs c_a=3, c_b=1, c_P=2, take A'={a}, A={a,b}. Then J(A')=3, J(A)=1, J(A'∪{P})=2, J(A∪{P})=1, so J(A∪{P})−J(A)=0 and J(A'∪{P})−J(A')=−1, violating the claimed inequality. The monotonicity lemma is correct, but the proof of submodularity does not go through, so the greedy selection in Algorithm 1 is not justified as a submodular greedy method. If the authors instead define the gain function G(A)=J(∅)−J(A), then G is monotone submodular, and the standard (1−1/e) guarantee applies to selecting the b programs with maximum final gain; the paper should be rewritten around that formulation.","section":"§A.1.2, Lemma 2"}],"minor_comments":[{"comment":"The empirical comparison reports a single run for each variant, with no error bars or multiple seeds. GRAIL is stochastic in two ways: the LLM is sampled at temperature 0.99, and the island/cluster selection in the evolutionary loop is randomized. Different runs can therefore produce different programs and different RMSE/EMR values. Given that several comparisons are decided by small margins (e.g., AIDS RMSE 0.57 vs 0.61; ogbg-molhiv 2.96 vs 3.02), the reported rankings and the claim that GRAIL \"consistently ranks among the top algorithms\" are not yet supported. At minimum, the authors should report the mean and standard deviation over at least several independent evolutionary runs.","section":"§5.1, Tables 3 and 4"},{"comment":"The inter-domain generalization claim is not directly supported by the experiments. Table 6 shows GRAIL models transferring across datasets, but there is no neural baseline evaluated on the same off-diagonal transfer tasks; Table 5 only compares GREED within the molecule domain, and the \"NA\" entries mean the comparison set is incomplete. Therefore the statement that this ability is \"not seen in neural approximators\" (end of §5.3) is an overreach. The authors should either include cross-domain runs of neural baselines on the same train/test combinations or restrict the claim to what the experiments show.","section":"§5.3, Tables 5 and 6"},{"comment":"The statement that GRAIL \"comprehensively outperform[s] the baselines\" is too strong, since GREED achieves lower RMSE than GRAIL on ogbg-molpcba (2.48 vs 3.18) and GEDGNN achieves lower RMSE on ogbg-molhiv (1.75 vs 2.96). The wording should be softened to \"on average\" or \"in most datasets.\"","section":"§5.2, Table 3"},{"comment":"The abstract says \"seven datasets,\" but Tables 3 and 4 benchmark only six; ogbg-ppa is used only in the scale experiment of Fig. 3a. Please correct the count.","section":"Abstract"},{"comment":"There is a typo in the sentence \"Since the programs evolve through mutations introduced by the LLM, the selection mechanism optimizes two distinct objectives.\" The comma after \"LLM\" should be removed or the sentence restructured.","section":"§4.2"}],"recommendation":"major_revision","confidential_remarks":"The sign error in the main selection loop is serious: if the implementation follows the text, the reported results are impossible. If the implementation already uses the corrected sign, the text must be aligned and the experiments should be re-run and documented with error bars. The submodularity proof is also incorrect as stated. Given the novelty of the idea, I think a major revision is worth considering, but the authors need to provide the actual code or a corrected algorithm, and re-evaluate the empirical claims with variance analysis."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read GRAIL. The core idea is good: instead of training a neural net to predict GED, evolve an LLM-written program that outputs bipartite-matching weights, and use the resulting mapping's cost as a ground-truth-free upper bound. That reformulation, the submodular map selection, and the interpretable code output are genuine additions, and the cross-domain results (IMDB, Linux, molecules) are the kind of thing that would make this a useful paper if the machinery works. Credit where due: the paper ships code, uses only 1,000 training pairs, and the upper-bound objective is a legitimate way to avoid NP-hard labels.\n\nBut there is a load-bearing flaw in the text. Section 3.2 defines J(A) to be minimized; adding a program can only decrease J, so J(A∪{P})−J(A) is never positive. Algorithm 1 line 3 nevertheless takes arg max over that non-positive quantity, which selects the program with the smallest (least negative) reduction. Equation 6 assigns that same quantity as score, and §4.2 says the sampler prefers high scores—again favoring programs that barely reduce the bound. Lemma 2's submodularity inequality is also written for the wrong sign. If the implementation follows the paper, the central evolutionary loop cannot discover improving programs, and the reported gains would be impossible. The obvious correction is to maximize J(A)−J(A∪{P}) (equivalently, work with −J), but the text as written does not say that.\n\nThe empirical section has softer problems. GEDGNN beats GRAIL on ogbg-molhiv (RMSE 1.75 vs 2.96; EMR 0.57 vs 0.20), so 'comprehensively outperforms' is wrong. There are no error bars or seeds for a stochastic LLM pipeline, Table 6 claims inter-domain generalization without comparing to any neural baseline on off-diagonal entries, and a natural unsupervised baseline like EUGENE is cited but not benchmarked. The NP-hardness reduction in A.1.1 is also too loose to verify: it constructs a bipartite graph but never connects it to a training set T.\n\nBottom line: this is a promising direction and deserves serious referee time, but the version as written is not acceptable. The authors need to confirm the code's selection sign, fix Algorithm 1/Eq. 6/Lemma 2, add variance estimates, and moderate the claims. I would not cite it until those are resolved.","headline":"GRAIL has a genuinely useful idea—LLM-evolved code for GED upper bounds—but the main selection loop as written is sign-inverted and cannot work; fix that before believing the empirical claims.","tokens_in":18699,"tokens_out":6442,"would_cite":false,"duration_ms":79694,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that an LLM can be steered by evolutionary prompt tuning to write short programs that, through maximum-weight bipartite matching, give tight upper bounds on graph edit distance and beat supervised neural and non-neural…","keywords":["graph edit distance","LLM program generation","evolutionary prompt tuning","bipartite matching","upper bound optimization","submodular selection","cross-domain generalization","interpretable heuristics"],"falsifier":"Hold the model, prompt template, and datasets fixed, but replace the evolutionary top-k feedback with a loop that always feeds the initial trivial program back to the LLM; if the resulting answer set still matches GRAIL's RMSE, then the claimed discovery process is not what carries the result.","tokens_in":17740,"feed_emoji":"⚙️","tokens_out":7075,"duration_ms":70030,"temperature":0.7,"pith_summary":"This paper claims that graph edit distance (GED), a similarity measure whose exact computation is NP-hard, can be approximated by asking a large language model to write small graph-alignment programs and then evolving those programs through prompt feedback. The key move is to measure each program not by how close its output is to a labeled GED but by how tight an upper bound its induced node mapping gives on the true GED; because every mapping produced by a program is a feasible edit path, the bound is guaranteed to be an upper bound, so minimizing it never needs ground-truth labels. On six benchmark datasets the discovered programs report lower RMSE than existing neural and non-neural baselines, and a version trained once on a mixture of datasets transfers to all tested domains. A sympathetic reader would care because this replaces the pipeline of generating NP-hard training labels and training black-box models with an interpretable, self-evolving program search.","feed_headline":"LLM-evolved programs beat supervised GNNs on graph edit distance","feed_subtitle":"No NP-hard labels needed: short interpretable code yields tighter upper bounds on six datasets.","key_machinery":"The load-bearing mechanism is the reduction of GED approximation to maximum-weight bipartite matching with LLM-generated weights, combined with an upper-bound objective. Concretely, a program maps a graph pair to a weight matrix; running a bipartite matching algorithm, here the Neighbor-biased mapper, gives a bijection between nodes, and evaluating the edit cost of that bijection gives an upper bound on the true GED. Since any single mapping is feasible, the prediction cannot undercut the true distance, which makes the training signal (the sum over training pairs of the minimum upper bound among selected programs) a surrogate for approximation error that requires no labels. The evolutionary prompt loop keeps the top-scoring short programs, asks the LLM to improve them, filters for executability and runtime, and reselects a budget of complementary programs by greedy submodular maximization.","core_discovery":"GRAIL treats GED approximation as the problem of learning a program that outputs a weight matrix for a fully connected bipartite graph between the nodes of two graphs; a maximum-weight bipartite matching on that graph yields a node mapping, and the GED of that mapping is an upper bound on the true GED. The paper claims that an LLM, prompted with the problem definition and the best programs found so far, can mutate and combine programs until the greedy submodular selection of a budget of programs stops improving the training objective, which sums over training pairs the minimum upper bound among selected programs. Because this objective is an upper bound and is monotone submodular, greedy selection yields a good answer set, and because the program pool is evolved by LLM prompt feedback, no ground-truth GED is needed. Empirically, the resulting programs outperform the neural baselines GREED, GEDGNN, ERIC, H2MN, and GRAPHEDX, as well as the leading non-neural heuristics, on the six benchmark datasets, including a trained-once mixture variant.","pith_inferences":["An implication the paper leaves implicit is that the upper-bound guarantee makes the program set usable as an admissible pruning rule in similarity search: any pair whose upper bound already exceeds a query threshold can be safely discarded.","The method's ceiling is set by the LLM's mutation diversity, which suggests a testable extension: seeding the prompt pool with human-written heuristic programs, or with programs from several different LLMs, and measuring whether the discovered answer set improves.","The interpretability claim could be quantified by measuring the shortest program length that still reaches a given RMSE, and comparing those programs against the best known hand-designed GED heuristics.","The reported ground-truth evaluation is confined to graphs of at most a few dozen nodes; an extension would test the upper-bound gap on larger graphs using exact solvers or tight lower bounds where available."],"forward_implications":["Approximating GED no longer requires NP-hard ground-truth labels; training a GRAIL-style system needs only unlabeled graph pairs and LLM calls.","The discovered programs are executable, short code, so the resulting heuristic and the node alignment it induces are open to inspection and manual improvement.","A single program set trained once on a mixture of datasets transfers across domains, graph sizes, and label sets, eliminating per-dataset retraining.","Because every predicted GED is an upper bound on the true distance, the method can never quietly underestimate similarity, a useful property for downstream search and filtering."],"supporting_citations":[{"why":"Supplies the islands-model evolutionary algorithm that GRAIL uses to select which programs the LLM mutates next.","marker":"(Romera-Paredes et al., 2024)"},{"why":"Provides the Hungarian algorithm for maximum-weight bipartite matching, the standard solver for the matching step.","marker":"(Kuhn, 1955)"},{"why":"Supplies the Neighbor-biased mapper, the bipartite-matching heuristic GRAIL actually uses to turn weight matrices into node mappings.","marker":"(He & Singh, 2006)"},{"why":"Establishes NP-hardness of GED and provides GREED, the main neural baseline GRAIL compares against.","marker":"(Ranjan et al., 2022)"},{"why":"Provides GEDGNN, a neural edit-path baseline that requires ground-truth training data, used as comparison.","marker":"(Piao et al., 2023)"},{"why":"Benchmarks non-neural GED heuristics and supplies the LP-GED-F2, COMPACT-MIP, ADJ-IP, BRANCH-TIGHT, NODE, and IPFP baselines.","marker":"(Blumenthal et al., 2020)"},{"why":"Supplies MIP-F2, the exact solver used to generate ground-truth GED for the test sets.","marker":"(Lerouge et al., 2017b)"}],"fun_headline_variants":["LLM writes code to approximate graph edit distance","No labels: LLM generates GED programs that beat GNNs","Program generation, not prediction, for graph edit distance","LLM-crafted code generalizes across graph domains for GED","GED without ground truth: LLM programs surpass neural nets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the LLM, when shown the current best programs and asked to mutate them, will keep producing new programs that improve the training objective; if the model fails to generate useful mutations, the whole loop degenerates to the trivial zero-weight program and the method collapses.","fun_headline_variants_meta":{"raw":{"variants":["LLM writes code to approximate graph edit distance","No labels: LLM generates GED programs that beat GNNs","Program generation, not prediction, for graph edit distance","LLM-crafted code generalizes across graph domains for GED","GED without ground truth: LLM programs surpass neural nets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000286,"raw_usage":{"total_tokens":1700,"prompt_tokens":982,"completion_tokens":718,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":598,"completion_tokens_details":{"reasoning_tokens":634}},"tokens_in":598,"tokens_out":718,"duration_ms":7121,"temperature":1.0,"reasoning_tokens":634,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T01:01:19.190455+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Hold the model, prompt template, and datasets fixed, but replace the evolutionary top-k feedback with a loop that always feeds the initial trivial program back to the LLM; if the resulting answer set still matches GRAIL's RMSE, then the claimed discovery process is not what carries the result.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Hungarian algorithm for maximum-weight bipartite matching, the standard solver for the matching step."},{"cited_title":"Greed: A neural framework for learning graph distance functions","cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of GED and provides GREED, the main neural baseline GRAIL compares against."},{"cited_title":"Computing graph edit distance via neural graph matching","cited_arxiv_id":null,"evidence_quote":"Provides GEDGNN, a neural edit-path baseline that requires ground-truth training data, used as comparison."}],"review_version":1}