acceptodds
Under review as a conference paper at ICLR 2027

How Far Does Graph Edit Distance Learning Travel? A Cross-Dataset Benchmark of Neural Models

Abstract

Graph Edit Distance (GED) provides a domain-agnostic measure of structural dissimilarity, yet neural GED methods are typically developed and evaluated within a single graph collection. Whether the knowledge learned from exact GED supervision transfers across collections remains largely unexplored. To study this question, we introduce an open benchmark containing 5,523 graphs and 1,903,452 exact graph pairs from 11 collections, with node alignments and a unified evaluation framework covering 20 representative learning-based methods. Our experiments reveal a strong dependence on the collections used for training. Among the evaluated methods, 18 outperform the best approximation results on their source collections, yet none retains this advantage when directly transferred to other collections. Exposing the same methods to multiple source collections substantially improves performance on unseen targets, and the resulting models also provide a better starting point when limited target supervision becomes available. These results show that conventional within-collection evaluation provides an incomplete view of neural GED generalization. We expect this benchmark to support future research on neural GED methods with stronger cross-collection generalization.

Primary area:
datasets and benchmarks
Keywords:
Graph Similarity Learning, Graph Representation Leraning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_tmHFOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper introduce a new benchmark/collection of benchmarks for neural GED computation. This benchmark is build in a principled way: same exact algorithm for computing the exact GED as well as same time budget. They then use this benchmark to assess wether or not different algorithms trained on one dataset transfer to the other datasets. They answer negatively to this question, but show that training on several of these datasets improve the results on held out graph collections.

The paper is well written and the experiment are exhaustive, my main concern is how this benchmark really differ from the other existing datasets. See my questions for more information.

Critical strengths

1- The dataset construction is sound and reproducible. They provide a exhaustive picture of the different statistics and the datasets that comprise their benchmark, showing that indeed, we can expect models trained on one dataset to generalize poorly to the other datasets. Section 3.3-Data analysis is also very interesting as it pinpoints to what simple graph statistic correlates most to the GED.

2- The experiments are well defined and explained. They compare a big part of the different models in the litterature on their benchmark and consistently show what they claim: GED models generalize poorly to new graph collections, training on multiple datasets increase the performance on the held out collections.

Critical weaknesses

The main weakness of this paper is the fact that they do not prove enough in my opinion how they differentiate themselves from the other benchmarks. They claim that their benchmark differentiate itself for having bigger graphs yet in Figure 1 we see that appart from three small datasets the majority of graph pairs do not have more nodes than the existing benchmarks. Similarly, for exact pair coverage, Figure 1 does not show a higher pair coverage.

While less important, i think that their paper would greatly benefit from an analysis of the datasets they chose for the multi-source generalization experiment. While we see each dataset statistics, the same is not done the union of training dataset, it would be interesting to see how the simple graph statistics work there. We do not know if the algorithms generalize better because they learn something more expressive or if they still learn a simple baseline that is just shared between the train set and the held out set.

Questions for authors

1- why does having denser exact pair coverage is necessary/a metric we care about ?

2- can you explain what you mean by "Yet collection shift has so far been studied mainly as an evaluation setting for individual methods, leaving its broader effect on neural GED learning unclear." l-052

3- You differentiate yourself from GELATO by:

  • removing isomorphism: do you have any metrics quantifying the the leakage ? is it significant ? what portion of graphs are isomorphic accros the whole benchmark ?
  • having the runtime: why is it meaningful ? if it include a bias can you show it ?

Minor: "resources" -> "ressources" l-55

2 comments

We thank the reviewer for the comments and suggestions. We have revised the manuscript, with changes highlighted in orange.

The main weakness of this paper is the fact that they do not prove enough in my opinion how they differentiate themselves from the other benchmarks. ... Similarly, for exact pair coverage, Figure 1 does not show a higher pair coverage.

We agree that Figure 1 may be misleading. We replaced it with a direct comparison of exact supervision as graph size increases. For pairs where both graphs contain at least 30, 40, and 50 nodes, GSCBench contains 193,034, 52,837, and 1,663 exact pairs, compared with 643, 126, and 1 for GRAIL.

We report exact-pair coverage in the text: 80.1% for GSCBench, compared with 64.0% for Classic, 57.8% for Gelato, 44.1% for GraphEdX, and 2.0% for GRAIL.

Graph size is not how we distinguish GSCBench. Existing resources do not support controlled cross-collection comparison because data source, supervision, and method are often entangled. GSCBench instead makes training and test collections explicit evaluation dimensions under common supervision and a unified framework.

While less important, i think that their paper would greatly benefit from an analysis of the datasets they chose for the multi-source generalization experiment. ... We do not know if the algorithms generalize better because they learn something more expressive or if they still learn a simple baseline that is just shared between the train set and the held out set.

Appendix E.2 adds an analysis using the same graph-level statistics as Figure 2. Joint coverage, defined as the share of target graphs within the central 95% source ranges for all three statistics, is 0% for IMDB-BINARY, 36.3% for PROTEINS, 52.6% for DHFR, 70.3% for COX2, and 100% for ogbg-code2.

The pattern in Figure 6 is not monotonic. IMDB-BINARY generally shows weaker and less consistent gains, while COX2 and DHFR show more consistent improvements. However, ogbg-code2 has the highest coverage but not the largest gains, and methods respond differently on the same target despite the same statistical overlap. Thus, simple overlap may contribute to transfer but cannot explain the gains alone.

1- why does having denser exact pair coverage is necessary/a metric we care about ?

GED is widely used in graph search, where queries are compared with database graphs for ranking [1]. Denser exact-pair coverage better reflects this setting and stabilizes ranking evaluation. This matters because ranking performance and value errors such as MAE do not necessarily agree [1]. We added this explanation in Section 3.1.

2- can you explain what you mean by "Yet collection shift has so far been studied mainly as an evaluation setting for individual methods, leaving its broader effect on neural GED learning unclear." l-052

Previous studies mainly used cross-collection transfer to evaluate individual methods. It remains unclear whether methods degrade similarly, whether their rankings change, and whether multi-source training or limited target supervision improves transfer. Our benchmark studies these questions under the same source-target protocol.

3- You differentiate yourself from GELATO by:

  • removing isomorphism: do you have any metrics quantifying the the leakage ? is it significant ? what portion of graphs are isomorphic accros the whole benchmark ?
  • having the runtime: why is it meaningful ? if it include a bias can you show it ?

In the six compatible GELATO collections, we identify 3,386 duplicate graphs among 12,542 graphs (27.0%) using the released GED=0 relations:

CollectionDuplicate graphsFraction
aids33 / 7004.7%
code2-221,302 / 2,08762.4%
imdb-161,018 / 1,18585.9%
linux911 / 1,00091.1%
molhiv-16-noel121 / 6,7341.8%
zinc-16-noel1 / 8360.1%

GELATO avoids direct train-test leakage by keeping isomorphic copies within the same training split. However, this guarantee depends on preserving that split. Repartitioning without grouping these copies can place identical graphs on both sides. GSCBench removes them before graph-level splitting. We added this explanation in Section 3.1.

Runtime is not treated as an advantage or evaluation metric, but only as solver metadata. Since exact pairs are retained only when AStar-LSa finishes within 300 seconds, runtime helps inspect timeout-induced selection. We therefore note that the exact-covered population is not a random sample of all pairs.

Minor: "resources" -> "ressources" l-55

We checked standard English dictionaries and confirmed that “resources” is the correct English spelling.

[1] Y. Bai et al., “SimGNN: A Neural Network Approach to Fast Graph Similarity Computation,” WSDM, 2019.

Thank you for your clear response, Most of my concerns were cleared.

Reviewer_F2d7OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces GSC Bench, a benchmark with exact GED values and node alignments across 11 graph collections. Its main contribution is a unified evaluation of 20 neural GED methods, examining cross-collection generalization, multi-source training, and adaptation with limited target supervision.

Critical strengths
  1. A systematically organized benchmark for cross-collection generalization in neural GED learning.
  2. Consistent supervision through exact GED values and optimal node alignments across 11 collections
  3. Broad evalution of 20 methods, covering single-source transfer, multi-source training, and limited-target adaptation.
  4. Removing isomorphic duplicate graphs and using graph-level splits help reduce train-test leakage
Critical weaknesses

major meakness:

  1. Although the paper uses validation-based early stopping and five runs for the single-source experiments, sensitivity to training and model-selection choices remains insufficiently characterized. In particular, it is unclear whether the transfer gaps, and especially the relative method rankings, persist under comparable source-validation-only tuning budgets. A targeted sensitivity study on representative methods would strengthen these conclusions; learning curves would additionally help distinguish source-domain overfitting from degradation under collection shift
  2. The headline comparison should more explicitly identify its reference as a per-pair best-of-four approximation baseline rather than an individual algorithm. Although Tables 6–7 report the individual approximation results, the main text does not summarize whether the neural methods retain an advantage over those individual baselines after transfer. Please distinguish these comparisons, clarify whether the per-pair reference is a ground-truth-free minimum-upper-bound ensemble, and report its inference cost.

minor weakness:

  1. Section 3.3 incorrectly cites Figure 3 for graphlet-specific correlations; the corresponding results appear in Figure 8
  2. Figure 1 shows only ten distinguishable “Ours” bubbles for eleven collections.
  3. Please reconcile the bubble-size legend in Figure 1 (“Exact pairs”) with Appendix A.2, which defines bubble size as the number of graphs covered by exact supervision
Questions for authors
  1. Could you provide training-loss and source-validation/source-test error curves for representative methods with large transfer degradation, together with target-test errors evaluated retrospectively at fixed checkpoints? Please mark the source-validation-selected checkpoint and do not use target-test results for model selection.
  2. Do the transfer gaps and method rankings persist under comparable tuning budgets for learning rate, regularization, and early stopping, using source validation only?
  3. Does the “none retains this advantage” conclusion hold against each individual approximation method? Can the oracle be reproduced by taking the minimum of valid upper bounds, and what is its combined inference cost?
2 comments

We thank the reviewer for the careful comments and constructive suggestions. We have revised the manuscript accordingly, with changes highlighted in violet.

Although the paper uses validation-based early stopping and five runs for the single-source experiments ...learning curves would additionally help distinguish source-domain overfitting from degradation under collection shift & 1. Could you provide training-loss and source-validation/source-test error curves for representative methods with large transfer degradation, together with target-test errors evaluated retrospectively at fixed checkpoints? Please mark the source-validation-selected checkpoint and do not use target-test results for model selection. & 2. Do the transfer gaps and method rankings persist under comparable tuning budgets for learning rate, regularization, and early stopping, using source validation only?

We added a targeted analysis of training dynamics and hyperparameter sensitivity using GEN, Graph2Region, GMN-emb, and GMN-match on MUTAG, ENZYMES, and ogbg-code2. The four methods span substantial degradation (GEN), milder degradation (Graph2Region), and improvements after transfer (GMN-emb and GMN-match), while the three sources cover molecular, biological, and program graphs.

  • For the training-dynamics analysis, each run is continued for 500 epochs with three training seeds. We record training loss and validation error and retrospectively evaluate the source and six other collections at fixed checkpoints. The source-validation-selected checkpoints are explicitly marked. For example, when GEN is trained on ogbg-code2, its median source-test MAE decreases from 1.85 at epoch 10 to 0.85 at epoch 500, while its MAE on COX2 and DHFR increases from 7.06 to 214.58 and from 12.79 to 214.67. Thus, cross-collection degradation can occur while source performance improves. See Appendix J.1 and Figure 18.
  • For the hyperparameter-sensitivity analysis, we apply the same seven configurations to every method and source, varying learning rate (svg, svg, svg), weight decay (svg, svg, svg), and early-stopping patience (20, 50, 100). The ranking pattern remains similar. GEN consistently ranks better in-collection than cross-collection, GMN-emb shows the opposite behavior, and GMN-match remains among the strongest methods. See Appendix J.2 and Figure 19.

The headline comparison should more explicitly identify its reference as a per-pair best-of-four approximation baseline rather than an individual algorithm. ... Please distinguish these comparisons, clarify whether the per-pair reference is a ground-truth-free minimum-upper-bound ensemble, and report its inference cost. & 3. Does the “none retains this advantage” conclusion hold against each individual approximation method? Can the oracle be reproduced by taking the minimum of valid upper bounds, and what is its combined inference cost?

We apologize for the misleading terminology. Each of the four approximation methods returns the cost of a valid edit solution and therefore an upper bound on exact GED. Consequently, selecting the approximation with the smallest absolute error is equivalent to taking the minimum of the four returned upper bounds and does not require exact GED. This construction is also used by SimGNN [1] for IMDB, where the minimum of Beam, Hungarian, and VJ is taken. We now describe this reference as the \emph{best-of-four approximation} and remove the misleading term "oracle" and wording implying that exact GED is required for selection.

The "none retains this advantage" conclusion applies specifically to this best-of-four reference. After transfer, 13/20 methods still outperform VJ, 10/20 outperform Hungarian, and 2/18 outperform Beam (GMN-emb and GMN-match), whereas 0/18 outperform FGWAlign or the best-of-four reference. Since obtaining the best-of-four value requires running all four methods, its serial inference cost is their sum. The pooled mean runtimes are 0.00045 s/pair for VJ, 0.00638 for Hungarian, 0.19483 for FGWAlign, and 1.83746 for Beam, giving 2.03912 s/pair in total. This cost ranges from approximately 0.239 s/pair on AIDS to 14.307 s/pair on DHFR.

  1. Section 3.3 incorrectly cites Figure 3 for graphlet-specific correlations; the corresponding results appear in Figure 8. & 2. Figure 1 shows only ten distinguishable “Ours” bubbles for eleven collections. & 3. Please reconcile the bubble-size legend in Figure 1 (“Exact pairs”) with Appendix A.2, which defines bubble size as the number of graphs covered by exact supervision.

Thank you for these observations. We moved the graphlet-specific discussion to the appendix with its corresponding figure. Following another reviewer’s suggestion, we also replaced Figure 1 with a clearer resource-comparison figure, resolving both the indistinguishable collection and bubble-size inconsistency.

Reviewer_F2d7OpenReview ↗

Official Comment by Reviewer F2d7

Thanks to authors for the detailed responses and addition experiments as well as new results and conclusions in the revised version. My concerns have been addressed. Also, I read the comments from the other reviewers and the AC, along with the authors' replies. I now lean toword weak accept and will update my score accordingly.

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

Summary: The submitted manuscript presents GSCBench, a new benchmark comprising graphs and exact graph edit distances (GED) between graph pairs across 11 collections (domains), along with node alignments, so that 20 neural GED methods can be compared on identical data. The results show that advantages of learning-based GED methods vanish under domain transfer (none of the 18 methods that beat the best approximation in-collection do so after a transfer), and that in-collection performance rank does not predict cross-collection rank. Training on several collections improves performance on unseen ones. Models trained on several collections are a better starting point when limited supervision is available from a new target domain.

Critical strengths

Strengths:

  1. Useful resource, prepared with a uniform solver, with isomorphic duplicates removed. Allows for fair benchmarking.
  2. Extensive evaluation over 20 methods, 121 source-target tasks, five runs, split-balanced medians and equal weight per collection. Consistent and stable observations.
  3. Useful lessons for GED: In-collection rank does not predict cross-collection rank (GEN falls from 3.16 to 12.67, GMN-emb rises from 10.20 to 4.02). Pre-training on multiple domains helps on unseen target domains, and pretraining helps with few target pairs (42.9% median MAE reduction at 100 pairs).
Critical weaknesses

Weaknesses and limitations:

  1. The authors do not report on control experiments that are matched for data volume or computation cost. Therefore, it is possible that the multi-source and few-shot claims are confounded.
  2. Labels are one-hot IDs with no cross-collection meaning. There is no label-agnostic ablation.
  3. No plausible explanation of the rank inversion is provided.
  4. The claim that "no neural method beats [the best approximation] after transfer" is hard to interpret, because the "best approximation" picks the best heuristic per domain pair using exact GED, so it can’t be deployed.
  5. Edit costs are unit, node labels are categorical (and meaningless across domains) and edges are unlabeled. ogbg-code2 loses most of its features.
  6. The 300-second timeout leaves only about half the possible pairs in BZR, DHFR and IMDB-Binary. The exact subsets retained may differ in difficulty across collections.
  7. Outside GED, such domain transfer phenomena are widely known, but have not been discussed or cited.
Questions for authors

Closely related domain transfer work outside GED

While I recognize that I have seen no previous study of domain transfer in the context of GED, the authors should position their work against the backdrop of a large volume of similar work and observations for problems other than GED. I am listing some works below. I am not asking the authors to cite all of these. I believe reading these papers carefully will give additional rich context to their understanding of the problem they undertook to solve, leave along writing a better-rounded manuscript. (I believe none of these have been cited, but please double-check.)

In-domain beats cross-domain

This effect is, expectedly, widely reported in many problems outside GED.

Multi-domain training helps on unseen or target domains

In-domain performance rank contradicts out-of-domain rank

Correlated (but depressed) OOD vs ID performance is of course the norm.

  • Do ImageNet Classifiers Generalize to ImageNet?
  • Accuracy on the Line
  • ImageNot: A contrast with ImageNet preserves model rankings https://arxiv.org/abs/2404.02112

However, the revese effect reported in this submission is also known.

  • Assaying Out-Of-Distribution Generalization in Transfer Learning https://arxiv.org/abs/2207.09239 (ID–OOD relationship ranges from linear to uncorrelated depending on the dataset pair)
  • Does Robustness on ImageNet Transfer to Downstream Tasks? https://arxiv.org/abs/2204.03934 (robustness gains on ImageNet don’t carry over to downstream tasks)
  • GOOD: A Graph Out-of-Distribution Benchmark https://arxiv.org/abs/2206.08452 (reports large ID–OOD gaps for graph models and different method trends under covariate versus concept shift)
  • Accuracy on the wrong line https://arxiv.org/abs/2406.19049 (label noise and nuisance features can make ID and OOD accuracy negatively correlated ― authors should ensure this effect is not at work)
  • Aggregation Hides Out-of-Distribution Generalization Failures from Spurious Correlations https://arxiv.org/abs/2510.24884 (mining subsets where higher ID accuracy predicts lower OOD accuracy)

Pretraining on multiple domains helps few-shot fine-tuning on a new one

This effect is well documented in few-shot vision, multi-task NLP and graph pretraining. However, the effect may be conditional: naive pooling can cause negative transfer on graphs, and in NLP pre-finetuning on only a few tasks can hurt, with gains appearing above roughly 15 tasks.

Limitations of the data set

  • Section 2 restricts GED to undirected graphs with categorical node labels and unlabeled edges. The limitations paragraph in Section 5 adds unit edit costs.
  • In Appendix A.1 (about ogbg-code2), original node features are multi-dimensional. The authors keep only the first dimension as a categorical label and discard edge attributes. IMDB-Binary has no node labels, so GED is computed on unlabeled graphs.
  • Table 1 reports only the number of node labels per collection, from 3 up to 32. There is no statistic on edge or continuous attributes.
  • Label encoding (Section 4.1): Node features are one-hot vectors sized by the maximum label value across all collections. Label IDs are therefore just per-collection integers, and nothing aligns their meaning across collections.
  • Label 3 in AIDS and label 3 in BZR are different atoms but share an input slot. The intro calls GED "domain-agnostic" because it ignores label semantics, but the models still consume those labels. That seems relevant to the transfer results.
  • Authors should check how drastically their data preparation code discards rich edge (bond) labels or node attributes (PROTEINS and ENZYMES, for example).

Edit costs informed by rich features

Support of the described data set for rich node and edge features is thin. Here are some papers where incorporating these into edit or match scores seems important to the application.

6 comments

We thank the reviewer for the constructive comments. We have revised the manuscript accordingly, with changes highlighted in blue.

There is no data- or compute-matched single-source control experiment. Therefore, it is possible that the multi-source and few-shot claims are confounded.

We clarify the multi-source and few-shot settings separately.

  • Multi-source training. We add a data-matched control for four representative methods using three source collections and five unseen target collections. Each single-source model is trained on 4,000 pairs from one source collection, while the corresponding multi-source model uses the same 4,000-pair budget drawn from all three sources. In the original experiment, multi-source training reduces MAE in all 20 unseen cases. After data matching, it still improves 17 of the 20 cases, while the median MAE reduction changes only from 49.2% to 43.7%. To probe why the gain persists, we repeat the comparison with seven linear GED predictors built from the structural factors in the Data Analysis section. Multi-source fitting improves 29 of the 35 unseen cases, consistent with the neural results. Since the relationship between these factors and GED varies across collections, we hypothesize that fitting multiple collections reduces reliance on source-specific relationships and therefore generalizes better to unseen collections. See Appendix G.
  • Few-shot training. This experiment serves a different purpose: it tests whether source pretraining provides a better initialization when target supervision is limited. The pretrained and scratch models use exactly the same target pairs. As shown in Figure 13, training from scratch generally requires more epochs than fine-tuning under the same target-data budget, so the fine-tuned models do not receive more target-side computation.

Labels are one-hot IDs with no cross-collection meaning. There is no label-agnostic ablation.

We recognize that distribution shifts induced by arbitrary attribute IDs may affect the observed transfer degradation. Since recomputing exact GED after removing node labels would require reconstructing the supervision itself, we address this concern from two perspectives.

  • Sensitivity to attribute encoding. We test whether arbitrary node-label encoding affects neural GED models by permuting label IDs while keeping graph structure and exact GED unchanged. Within the same collection, permutation substantially increases MAE for most methods, with many cases exceeding (2\times) or even (5\times) the original error. Under cross-collection transfer, permutation can either improve or degrade prediction, showing that incidental source--target encoding correspondence can materially change individual transfer outcomes. Multi-source training reduces this sensitivity for 18 of the 19 methods on seen collections, although the effect remains method-dependent on unseen collections. See Section 4.5.
  • Label-agnostic structural transfer. We then exclude node attributes using seven structure-only linear predictors built from graph size and structural factors. Because these predictors are independent of node-label IDs, this provides a label-agnostic control while retaining the original exact GED supervision. Cross-collection MAE is (1.49\times)--(3.36\times) the corresponding in-collection MAE at the median, and 753 of the 770 transfer settings have higher MAE than their in-collection counterparts. The same pattern holds across all 11 targets, where the median ratio ranges from (1.41\times) to (3.78\times) and at least 90% of the transfer settings degrade for every target. See Appendix H.

There is no plausible explanation of the rank inversion.

We did not find a consistent pattern across all methods. Figure 3 shows that the same structural factors, such as Count Difference, can relate to GED very differently across collections. We therefore fit simple linear predictors using these factors. Table 10 in Appendix I shows that factors performing well in-collection do not necessarily transfer well. Pair-count and Full-factor rank highly in-collection but degrade substantially cross-collection, whereas Count Difference is more stable. We then compare neural methods with these predictors over the same source--target tasks and find different factor profiles. For example, GEN is most strongly associated with Pair-count and Full-factor, whose predictive relationships deteriorate substantially after transfer, while GMN-emb is less concentrated on these two factors and remains associated with several structural factors that transfer more stably.

This suggests that rank inversion may partly arise from method-specific structural biases under collection shift. However, we do not find a consistent relationship between these biases and rank changes across all methods. We have added this direction to the limitations. See Appendix I.

The claim that "no neural method beats [the best approximation] after transfer" is hard to interpret, because the "best approximation" picks the best heuristic per domain pair using exact GED, so it can’t be deployed.

We apologize for the misleading terminology. The "best approximation" does not require exact GED for selection. Each of the four approximation methods returns the cost of a valid edit solution and therefore an upper bound on the exact GED. Consequently, selecting the approximation with the smallest absolute error to exact GED is equivalent to simply taking the minimum of the four returned upper bounds. This minimum-upper-bound construction is also used by SimGNN [1] for its IMDB data, where the minimum of Beam, Hungarian, and VJ is taken because all three return GED upper bounds. We have revised the manuscript to describe this reference as the best-of-four approximation and removed the misleading terms “oracle” and wording that implies exact GED is required for selection.

Edit costs are unit, node labels are categorical (and meaningless across domains) and edges are unlabeled. ogbg-code2 loses most of its features. & Limitations of the data set & Edit costs informed by rich features

We acknowledge that our benchmark uses unit edit costs, categorical node labels, and unlabeled edges. We adopted this setting to enable a unified comparison across the 20 evaluated methods, most of which do not support richer graph attributes or edit-cost settings. For ogbg-code2, we follow GELATO [2], retaining one categorical node attribute and ignoring edge attributes. We have clarified this limitation in the manuscript and identified richer graph attributes and feature-informed edit costs as important directions for future extension.

The 300-second timeout leaves only about half the possible pairs in BZR, DHFR and IMDB-Binary. The exact subsets retained may differ in difficulty across collections.

We argue that whether the retained pairs are “easier” is not straightforward to define. For traditional GED computation, graph size may be one notion of difficulty, but graph pairs of similar size can require very different search effort. More generally, difficulty depends on the solver, search strategy, and heuristics. For neural methods, prediction error further depends on the model and its training.

To make this concern measurable, we directly examine whether pairs requiring longer AStar-LSa computation also incur larger neural prediction errors. We use AStar-LSa runtime as an observable proxy for computational difficulty and compute its Spearman correlation with prediction error for each neural method. To account for graph size, we additionally normalize the error by the mean number of nodes in each pair. Representative size-normalized results are shown below. The results show that, the association is weak or even changes direction across neural methods, and the same qualitative pattern holds without size normalization. Thus, among the observable exact pairs, longer AStar-LSa runtime does not indicate consistently higher neural prediction error.

MethodBZRDHFRIMDB-Binary
GEN0.160.040.19
GEDIOT0.360.040.04
GOTSim−0.28−0.20−0.24
SimGNN−0.06−0.070.06

Outside GED, such domain transfer phenomena are widely known, but have not been reviewed or cited. & Closely related domain transfer work outside GED

We have added a new paragraph on Cross-domain Generalization in Section II (Background), reviewing related findings in general machine learning and graph learning, and positioning cross-collection GED evaluation against this literature.

[1] Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM ’19, pp. 384–392, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450359405. doi:10.1145/3289600.3290967. URL https://doi.org/10.1145/3289600.3290967.

[2] Paolo Pellizzoni, Till Hendrik Schulz, and Karsten Borgwardt. Gelato: Graph edit distance via autoregressive neural combinatorial optimization. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=6ZTcLNmguc.

Dear authors, thank you for your rebuttal. I agree with reviewer fN2V that "Labels are one-hot IDs with no cross-collection meaning" and "node labels are meaningless across domains". Your experiments confirm that the models depend on the encodings of labels, and permuting them substantially changes performance. To me, the results seem to confirm that the structural generalization claims might be confounded by sensitivity to arbitrary label encodings across different datasets. The experiments should involve datasets either with no node/edge labels, or where the meaning of labels is shared when transferring from one dataset to the other (for example all ogb molecular datasets share the same AtomEncoder).

Moreover, the In-collection Single-Source results rank the recent SOTA methods (GEDGNN, MATA∗, GELATO) well below much older methods. Since here no cross-domain generalization is necessary, these results raise a separate question about reproduction fidelity of these recent methods, which cannot be assessed since code is not provided.

Best, AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.