- 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
Thank you for your clear response, Most of my concerns were cleared.
We thank the reviewer for the comments and suggestions. We have revised the manuscript, with changes highlighted in orange.
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.
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.
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.
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.
In the six compatible GELATO collections, we identify 3,386 duplicate graphs among 12,542 graphs (27.0%) using the released GED=0 relations:
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.
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.