acceptodds
Under review as a conference paper at ICLR 2027

COST-GED: COST-VALIDATED SELF-IMPROVEMENT FOR GRAPH EDIT DISTANCE

Abstract

Graph edit distance (GED) is a fundamental measure of graph similarity, but computing it exactly is NP-hard. Although neural GED solvers improve inference efficiency, many still rely on exact GED values or optimal matchings as supervision, limiting large-scale training, especially on graphs with complex node and edge labels. We introduce COST-GED, a cost-validated self-improvement framework that requires neither exact GED values nor optimal matchings as training supervision. COST-GED exploits the fact that the edit cost of a feasible matching can be computed directly and provides an upper bound on GED. It updates pseudo-matchings using edit costs rather than model confidence: a candidate is accepted only if it strictly lowers the current cost, and the improved matching supervises an autoregressive solver. For each fixed graph pair and edit-cost function, this rule guarantees a monotonically non-increasing pseudo-matching cost. Global sampling and local perturbation-based reconstruction balance exploration with reuse of existing correspondences. Across six public small-graph GED benchmarks, COST-GED achieves performance competitive with supervised methods. On Code2-22, increasing the unlabeled training pool from 2K to 40K graph pairs improves the exact hit rate (EHR) from 84.5% to 95.8%. On the larger MolHIV-30-50 and MolHIV-50-70 benchmarks, COST-GED reduces the mean edit cost of returned feasible matchings by 16.92% and 19.26%, respectively, relative to IPFP, the best-performing traditional baseline in our comparison.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Edit Distance, Self-Improved Learning, Pseudo-Labeling, Graph Matching, Neural Combinatorial Optimization.

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_KEmNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes COST-GED, a way to train GELATO without using exact GED labels for the training pairs. starts with a feasible node matching for each pair. During training, the model generates new matchings by global sampling and local reconstruction. A new matching becomes the training target only when its edit cost is lower than the current one. The paper evaluates this method on six small-graph benchmarks and two larger MolHIV benchmarks. It reports results close to supervised GELATO on several small datasets and lower matching costs than IPFP on the larger graphs.

Critical strengths
  1. main idea is simple and practical. The edit cost of a feasible matching can be computed without knowing the exact GED. Using this cost to check proposed training labels is a reasonable way to train a matching model with less supervision.

  2. Figure 2 shows that the gap between the training pool’s pseudo-matching costs and exact GED becomes less than 1% after 25 cycles on the three datasets shown. This is useful evidence that the training labels improve during the process.

  3. The larger MolHIV experiments are relevant because exact GED labels are harder to obtain there. The reported matching costs are about 17% and 19% lower than IPFP on the two datasets. These are meaningful improvements (although the comparison is limited to traditional baselines).

Critical weaknesses
  1. I find the methodological novelty limited. The solver architecture, construction of training subproblems, and loss come from GELATO (Pellizzoni et al., ICLR 2026). Sampling several solutions, keeping a better one, and learning from it is also close to earlier self-improvement work in neural combinatorial optimization, including Pirnay and Grimm (TMLR 2024). The paper should clarify its methodological contributions beyond these established techniques.

  2. The comparison with supervised GELATO is difficult to interpret. GELATO is trained on 5,000 labeled pairs, while COST-GED regularly refreshes its active pool and can see many more pairs over training. For Code2-22, its result with a 40,000-pair active pool is compared with GELATO trained on 5,000 pairs. At test time, COST-GED uses 32 paths in each of eight decoding rounds, but GELATO’s corresponding inference budget is not stated. Can you add more analyssis and discussion about this result.

  3. In Table 1(b): Its GEDRanker row agrees with the original paper on several AIDS values, but the original paper reports LINUX MAE of 0.01 rather than 0.000, and IMDB accuracy and τ of 94% and 0.97 rather than 84.0% and 0.990. The time values also seem to be shown in milliseconds, although the column says seconds. Please review and justifiy the reason for the differences.

  4. The ablations do not isolate several important choices. There is no plain best-of-K self-training variant without the incumbent and strict acceptance rule, no local-only variant, and no separate experiment on pool refresh. Table 3 suggests that the training setup has a large effect, , but it is still unclear how much pool refresh contributes. Adding these comparisons would be helpful.

Questions for authors

Please see above weaknesses.

2 comments
AuthorsOpenReview ↗

Response to Reviewer KEmN

We thank the reviewer for recognizing the practical value of COST-GED and for the constructive comments. We address the four concerns below.

W1. Methodological novelty We acknowledge that COST-GED builds on GELATO's autoregressive architecture and is inspired by self-improvement methods such as Pirnay and Grimm and SIL. However, these methods cannot be directly transferred to GED. SIL reconstructs route segments, whereas GED solutions are node correspondences: replacing some correspondences can violate injectivity and change edge-edit costs outside the modified region. We therefore design reference-guided local correspondence replacement, conflict repair, and full edit-cost validation, combined with global sampling and autoregressive pseudo-matching feedback. GEDRanker also updates cost-based incumbents, but its main method uses a preference discriminator to guide a diffusion generator; COST-GED instead directly trains an autoregressive matcher on improved feasible matchings. Our contribution lies in this GED-specific candidate-improvement and feedback-learning design, not in claiming self-improvement itself as new.

W2. Comparison with supervised GELATO COST-GED achieves 89.9% EHR on Code2-22 with a 5K active pool of unlabeled graph pairs, rising to 95.8% with 40K. GELATO's original Code2-22 main training configuration uses 100K supervised pairs and reports 95.7% EHR. We will verify and correct the training-scale attribution in our paper. Pool refresh resamples pairings within a fixed training-graph split; it adds no external graphs, but the number of distinct pairs encountered over training may exceed the active pool size. We therefore do not claim equal cumulative data budgets. To control inference, we evaluated COST-GED and supervised GELATO on the same test pairs, with identical node-label Hungarian initialization, K=32, and 16 rounds of the same Global–Local search:

DatasetCOST-GED EHRGELATO EHR
ZINC-1698.20%99.13%
Code2-2289.30%96.23%
COST-GED approaches supervised GELATO on ZINC-16 but remains behind on Code2-22; we do not claim superiority under equal search budgets.
Crucially, Table 3 already disables pool refresh for the Fixed-Label/Updated-Label comparison: EHR rises from 2.30% to 85.30% on ZINC-16 and 25.90% to 82.80% on Code2-22. In additional controlled experiments at Cycle 25, 195,500 optimization steps, and eight identical search rounds, Updated-Label obtains 76.47%/80.37%, versus 1.73%/22.47% for Fixed-Label (ZINC-16/Code2-22). Thus, feedback gains persist without refreshing training pairs and cannot be attributed solely to more data or test-time search.

W3. GEDRanker results and timing units The GEDRanker entries in Table 1(b) come from our local reproduction rather than being copied entirely from the original paper, and the accuracy discrepancies are within the normal range. However, I agree that we should verify the metric definitions and correct the runtime units.

W4. Ablations Our ablations target two central mechanisms: pseudo-matching feedback and Global–Local candidate improvement. With refresh disabled, Updated-Label substantially outperforms Fixed-Label (Table 3); the additional matched-training-progress experiment above further supports this conclusion. Under the same neural decoding-path budget, adding local reconstruction to global sampling improves EHR by 0.6 and 1.4 percentage points on ZINC-16 and Code2-22, respectively. We agree that best-of-K without incumbent retention, local-only search, and an isolated refresh-on/off comparison would provide finer attribution. These variants have not been separately evaluated, so we do not claim that every component is indispensable. The reported ablations nevertheless support the effectiveness of the two mechanisms central to our method.

I would like to thank the authors for the response. The concerns about the novelty has been addressed. However, I still noticed that the concerns about the settings of training GELATO and the proposed COST-GED has not been addressed in the proposed paper. Meanwhile, the response states that 16 rounds are used in this experiment, however, in the original paper, only 8 rounds are used as the budget. The reason for this difference is not justified. As for the difference between the performance of GEDRanker, I would like to know the details of the reproduction. Since the reported accuracy is lower and τ is higher, more justification is required.

Therefore, at this stage, I would like to maintain my score.

Reviewer_tKvWOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes COST-GED, an autoregressive GED model that updates the current best solution, with global cost-ratio-aware sampling and local match perturbation with injectivity repair. Experiments on six datasets show competitive performance against selected baselines.

Critical strengths
  • The paper evaluates graphs with edge labels and larger numbers of nodes, and includes recent traditional methods
Critical weaknesses
  • I think the paper overstates its contributions. Cost-based self-improvement is already used in GEDRanker (Huang et al., 2025a), and the framework and training pipeline largely follow GELATO (Pellizzoni et al., 2026). The global node-pair normalization resembles GEN (Liu et al., 2026), but this connection is not discussed
  • The paper motivates its method by the difficulty of large-scale training without clearly explaining why such training is needed, leaving the motivation and additional contribution insufficiently established
  • The baselines change across experiments without sufficient explanation. For instance, the experiments on larger graphs include only Hungarian variants and IPFP, while relevant methods such as GEDRanker and FGWAlign (Tang et al., 2025) are missing. The paper should compare both solution quality and runtime with these methods on larger graphs
  • The computational cost is also a concern, as Table 1(b) reports much longer runtimes than GEDGW
  • Citation formatting is consistently incorrect throughout the paper

Huang, W., Wang, H., Wen, D., Ma, S., Zhang, W., and Lin, X. (2025a). Towards unsupervised training of matching-based graph edit distance solver via preference-aware GAN. Advances in Neural Information Processing Systems, 38, 178996–179023.

Pellizzoni, P., Schulz, T., and Borgwardt, K. (2026). Gelato: Graph edit distance via autoregressive neural combinatorial optimization. International Conference on Learning Representations.

Liu, Z., Liu, N., Chen, Y., He, J., Ma, S., and Li, D. (2026). Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance. ICDE.

Tang, J., Zhao, X., Kong, L., Zhou, X., and Li, J. (2025). Fused Gromov-Wasserstein alignment for graph edit distance computation and beyond. Proceedings of the VLDB Endowment, 18(10), 3641–3654.

Questions for authors
  • How were baselines that do not natively support edge labels adapted for the edge-labeled datasets? Were edge labels used during matching, or only when recomputing the final edit costs?
2 comments
AuthorsOpenReview ↗

Response to Reviewer tKvW

We thank the reviewer for the constructive comments. We address each concern below.

W1. Methodological novelty We acknowledge that COST-GED builds on GELATO's autoregressive matcher and prior self-improvement ideas. Our contribution is a GED-specific global–local candidate-improvement and feedback-training procedure: we sample complete matchings, use model-generated reference matchings to replace selected correspondences, repair injectivity conflicts, validate candidates using full edit costs, and train the autoregressive solver on improved feasible matchings. These operations address constraints that do not arise in the same form in route-segment reconstruction. GEDRanker also uses cost-based incumbent updates; we do not claim this rule as novel. Its main method trains a diffusion generator with a preference-aware discriminator, whereas COST-GED directly feeds improved matchings to an autoregressive solver. We also thank the reviewer for pointing out GEN. GEN uses global normalization and dependency propagation for one-step alignment; COST-GED normalizes scores over currently available node pairs to sample the next autoregressive decision. Global normalization itself is not our novelty. We will clarify these distinctions and cite GEN.

W2. Motivation and larger-graph evaluation As graph size and training-set scale increase, obtaining exact GED values and optimal matching labels becomes increasingly expensive. COST-GED instead learns from computable costs of feasible matchings without optimal-matching training labels. We first evaluate on six small-graph benchmarks with exact references to measure EHR and nMAE. To test applicability to larger graphs, we then extend evaluation to MolHIV-30-50 and MolHIV-50-70, where exact references are unavailable and solution quality is measured by feasible-matching edit cost.

W3. Missing recent larger-graph baselines We agree that the original comparison was limited and have added FGWAlign-multirel on the same 500 test pairs for each MolHIV benchmark. We use the official multi-relation implementation with Fast settings (patience=1, topk=10), incorporating both node and edge labels. All returned matchings are evaluated using our common unit edit-cost function. Four non-injective outputs on MolHIV-30-50 were repaired by Hungarian projection, with repair time included and no test pairs excluded. On MolHIV-30-50, the mean feasible-matching edit costs are 37.316 for COST-GED, 44.436 for FGWAlign, and 44.914 for IPFP. On MolHIV-50-70, the corresponding costs are 57.586, 68.458, and 71.320, respectively. Thus, COST-GED achieves 16.02% and 15.88% lower costs than the evaluated FGWAlign configuration. We note that FGWAlign's internal edge-label substitution cost differs from our unit-cost evaluation. Therefore, final scoring is unified, but the internal optimization objectives are not identical. FGWAlign takes 0.134 and 0.404 s per pair on a single CPU thread, including preprocessing, repair, and scoring. Since COST-GED's existing results were obtained on GPU, we make no cross-hardware speed claims. We have also conducted preliminary GEDRanker adaptation experiments, but their training settings and edge-cost compatibility require further verification. We therefore draw no comparative conclusions from those results.

W4. Runtime versus GEDGW We agree that COST-GED's multi-round candidate search and cost validation add inference overhead. We do not claim a general runtime advantage over GEDGW and will ensure timing units and protocols are clearly reported.

W5. Citation formatting Although we used the official ICLR LaTeX template, some in-text citation commands were used incorrectly. We acknowledge this issue and will correct citation formatting throughout.

Q. Edge-label support in baselines We use consistent node/edge label definitions and the same GED edit-cost specification for evaluation. COST-GED and GELATO encode edge labels with GINE, influencing matching generation. Our larger-graph Hungarian and IPFP adaptations incorporate edge-label costs into their optimization matrices, rather than only at final scoring; their explicit matchings are then rescored using the common full edit cost. Node-label-only Hungarian initialization intentionally ignores edges when constructing its initial matching, but full edit-cost evaluation includes them. App-BMao receives edge labels as solver input but returns a scalar cost, not an explicit matching; we do not claim to recompute its matching cost.

Thank you for the response and the additional FGWAlign experiment. Several points are now clearer, but my main concerns remain. First, after acknowledging that the autoregressive framework follows GELATO, cost-based incumbent updating is used in GEDRanker, and global normalization is not novel, the remaining methodological novelty is still not sufficiently clear. This is also reflected in the ablation, where adding local reconstruction over global sampling yields only modest gains. Second, the edge-label question is only partially answered. For several neural baselines in Table 1, it is still unclear whether edge labels are used when producing the prediction or matching, or only when the returned solution is rescored. Third, the added FGWAlign comparison is not computation-matched. COST-GED uses K=32 paths over eight decoding rounds, whereas FGWAlign is evaluated with patience=1, topk=10. Since FGWAlign supports GPU execution, a same-hardware and comparable-budget comparison would be more informative. It would also be useful to evaluate COST-GED with a stronger initialization, such as FGWAlign, rather than only the node-label-based Hungarian initialization, to better understand how sensitive the self-improvement process is to the quality of its starting solution. Based on these remaining concerns, I retain my original score.

Reviewer_6GvNOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper presents COST-GED, which builds on top of a baseline autoregressive decoding model (GELATO). First an initial matching is proposed using a hungarian solver based on node labels. Then, keeping track of the best solution at any point, a local and global solution generator proposes alternatives. The global solution is a high temperature exploration of possible mathcings by the base model. The local solution generates reference matchings and then perturbs a fraction of the node assignments to explore better alternatives in a local neighborhood. The best candidate matching is retained and is used to further train the base model.
This results in a self improvement mechanism, which avoids the need for expensice exact GED computation for supervision during training. Experiments are run on some of the common datasets used in previous works and many baselines.

Critical strengths
  • The proposed solution is intuitive. GED verificaiton is easy once a node assingment is proposed. This is used to explore the solution space, through high temperatire global eploration and local neighborhood search using perturbations, and then selecting the best cost solution as the expert trajectory to further train the autoregressive decoder. This applies the supervised imitation learning style of Pirnay and Grimm to GED setting.

  • While it builds on GELATO, which is seen to be performing in the same range as COST-GED (also outperforming in Code22), COST-GED avoids one of the major limitations of GELATO, which is its dependence on (potentially expensive) ground truth supervision.

Critical weaknesses
  • We see that in terms of performance, GELATO is comparable to COST-GED and outperforms in CODE-22. The core motivation thereby is that exact GED ground truth is too expensive. This is not a significant concern for most of the evaluated small datasets. In general for such a motivation, wall-clock time is an important axis to report on , in terms of ground truth generation time , and the training and inference times for all the (neural and non-neural) methods. Ground truth generation can be parallelized across CPU cores, so these numbers should be reported under a fixed budget of CPUs. Also, as reported in Table 7, much of the accuracy comes from test-time search. The test time budget of the baselines should be reported and the wall clock times assessed. MIP-F2 is limited to 0.1 s. Why? Is this the average inference time for neural methods? Ideally you want a prediction-quality v/s time tradeoff.

  • I would also consider the unreleased code a "critical weakness" for such an experiment-driven paper. I have no way of verifying, for instance, whether it is indeed the case that a randomly initialized GELATO model trained using COST-GED framework is outperforming/comparable to the same randomly initialized GELATO model trained using ground truth supervision.

  • Given the above, the remaining paper has limited novelty for me. We basically have here the self improvement scheme of Pirnay and Grimm applied to GELATO. Poposition 1 is trivial, that half page could be compressed to a short para. Since exact GED is used for model selection, this also reduces the proposed benefits of avoiding ground truth label generation.

Questions for authors
  • Which solver is used to generateground truth for exact hit rate?
  • Do you use a randomly initilalized GELATO model or a pretrained one?
  • Table 7 at K=32 and Table 1 numbers are inconsistent for ZINC-16 / Code2-22. Why?
  • Unlike GED, the proposed COST-GED method is not permutation invariant right ? Because of the dependence on node order during the repair step.
  • Is my understanding correct that COST-GED in general trails GELATO supervised and needs 8X larger training pool (40K vs 5K) to be comparable? In such a case, a careful wall clock time based study on large graphs is critical to evaluatet the effectiveness of the proposed method.
  • Feedback for future revisions - the image is not readable without significant zoom (250%).
2 comments
AuthorsOpenReview ↗

Response to Reviewer 6GvN (Part 1/2)

Response to Reviewer 6GvN (Part 1/2) We thank the reviewer for the constructive comments. We have checked the experimental settings and conducted additional controlled evaluations. Q1. Exact GED references and optimal matchings used for EHR were obtained with MIP-F2. The 0.1 s limit in Table 1 applies only to MIP-F2 as an evaluated baseline, not to exact-reference generation. Q2. COST-GED trains GELATO's LinkGNN architecture from random initialization, without supervised pretrained weights. Initial pseudo-matchings are produced by a node-label-based Hungarian algorithm. Q3. Table 7 used an earlier checkpoint, whereas Table 1 used the final selected checkpoint. This was an oversight when consolidating results. We will update Table 7 using consistent checkpoint weights. Q4. We agree that the complete finite-budget algorithm is not strictly permutation invariant. Although GNN embeddings are permutation equivariant, our local conflict repair processes source nodes in index order. Reindexing can therefore change repaired matchings. We will make this limitation explicit. Q5. The default COST-GED active pool contains 5K unlabeled graph pairs, yielding 89.9% EHR on Code2-22. A 40K active pool yields 95.8%. GELATO's original Code2-22 main experiment uses 100K supervised pairs and reports 95.7%. Thus, COST-GED reaches comparable quality without optimal-matching training labels. We will correct the training-scale description in our paper. Pool refresh resamples pair combinations within a fixed training-graph split; it introduces no new underlying graphs, and the active pool size remains fixed. The cumulative number of distinct graph pairs may nevertheless exceed 5K, so we do not claim equal cumulative training-pair budgets. Crucially, the feedback ablation in the original Table 3 already disables pool refresh. Updating pseudo-labels improves EHR from 2.30% to 85.30% on ZINC-16 and 25.90% to 82.80% on Code2-22. We further controlled training progress: with refresh disabled, Cycle 25, 195,500 optimizer steps, and eight inference rounds in both conditions, Updated-Label reaches 76.47%/80.37%, compared with Fixed-Label's 1.73%/22.47% (ZINC-16/Code2-22). Hence, feedback improvements persist even without newly sampled graph-pair combinations; they are not simply an effect of pool expansion. Q6. We will increase figure font sizes and improve layouts for readability at normal zoom.

AuthorsOpenReview ↗

Response to Reviewer 6GvN (Part 2/2)

W1. We acknowledge GELATO's autoregressive architecture and earlier self-improvement methods, including Pirnay and Grimm and SIL. However, their local reconstruction operators cannot be directly transferred to GED: GED solutions are node correspondences rather than route segments; replacing correspondences can violate injectivity and alter edge-edit costs beyond the modified subset. Our concrete design combines global matching sampling, model-reference-guided local replacement, conflict repair, full edit-cost validation, and feedback training. We do not claim self-improvement or strict incumbent acceptance as new in isolation. GEDRanker also uses cost-based incumbent updates, but its main method employs a preference discriminator to guide diffusion training, whereas ours feeds improved feasible matchings directly to an autoregressive solver. The contribution is this GED-specific candidate-improvement and learning pipeline.

W2. We conducted an identical-budget test using the same Global–Local inference procedure for Fixed-Label and Updated-Label models. After one round, Updated-Label reaches 63.23%/76.33% EHR on ZINC-16/Code2-22; even after 16 rounds, Fixed-Label reaches only 2.97%/29.00%. Together with the matched Cycle-25 experiment in Part 1, these results show that improvements are not merely due to additional test-time search. Each condition has one training seed; three repetitions vary inference-search seeds only.

W3. We agree that eliminating optimal-matching training labels does not imply lower total compute. Complete COST-GED training takes 2.29 h on ZINC-16 and 2.96 h on Code2-22, including training, candidate search, pool refresh, and validation. Under the same 16-round Global–Local inference procedure, runtime is: Dataset COST-GED Supervised GELATO ZINC-16 101.50 ms/pair 101.63 ms/pair Code2-22 171.56 ms/pair 171.87 ms/pair

These are matched search-time comparisons, not end-to-end training-cost comparisons. We lack directly comparable optimal-label-generation and full supervised-GELATO training times, so we do not claim a lower total computational cost.

W4. An anonymized code repository was provided at submission for inspecting and reproducing our training, candidate generation, and evaluation pipeline. We will explicitly identify the accessible repository link in the response.

W5. We agree that Proposition 1 follows directly from strict cost-decreasing acceptance. It establishes non-increasing incumbent cost for each fixed graph pair; we do not present it as an independent theoretical breakthrough and will shorten the discussion. On small graphs, exact GED values and optimal matchings are not training targets, but exact-GED-based validation is used to select checkpoints. We will therefore clarify that our claim concerns training supervision, not complete reference-free model selection. For MolHIV-30-50 and MolHIV-50-70, we instead predefine 20 training cycles and use the final model, without selecting checkpoints by exact GED or test performance. On the same 500 test pairs under a common edit-cost function, COST-GED produces feasible matchings with 16.92% and 19.26% lower mean costs than IPFP. Thus, the method is effective against the evaluated traditional baselines without exact-GED supervision or selection on these larger graphs. Due to time constraints, a separate reference-free checkpoint-selection study has not been completed. We plan to compare selecting checkpoints by mean feasible-matching edit cost on a fixed, independent validation set against selection using exact-GED validation metrics.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.