Graph Edit Distance with General Costs Using Neural Set Divergence

differences between 𝑞 and 𝜂

Yes, we apologize for the mistake, $q$ = 1-$\eta$. The notation was redundant; only one is needed -- we will correct it.

some related work [1] is missing.

Since NeurIPS allowed including the Appendix with the main paper, we placed the related work there. If accepted, we will use the extra page to move the related work into the main paper. We also evaluate our method against GEDGNN [1] in both equal and unequal cost setups, below.

We observe that GraphEDX outperforms GEDGNN across all datasets. GEDGNN relies on node-level alignment supervision, which is unavailable in our setup, thereby degrading its performance. Additionally, as expected, GEDGNN, which is not designed to handle unequal cost setups, performs better at minimizing MSE in equal cost setups.

technical contribution.

GraphEdX is eventually simple and intuitive to describe, yet the judicious combination of MPNN and Sinkhorn networks significantly improves inductive bias. Our work is the first neural GED model that accounts for generic costs, requiring a deep understanding of GED costs and careful design of surrogate functions. Our experiments show that our method performs particularly well in non-uniform edit cost settings, highlighting the effectiveness of our set divergence guided scoring. Additionally, our method provides clear guidance on combining embeddings and alignments (DiffAlign, AlignDiff, XOR-DiffAlign) and uniquely enforces consistency between node and edge permutations, which is a significant contribution to the community.

The size of the graphs is small.

Please refer to global response.

#parameters for the baselines

In the table below, we compare the model performances on the Mutagenicity dataset under equal cost, across the original number of parameters and our reduced parameter setting. Performance is evaluated in terms of MSE, with the numbers in parentheses indicating the number of parameters. We observe that GraphEDX outperforms all baseline models across both parameter settings. Additionally, in most cases, the baselines perform comparably across both settings, except for GREED in the equal cost setting, where there is approximately a 40% reduction in error, albeit at the cost of a 44x increase in the number of parameters. Table (B) in the global PDF provides comparisons on other baselines, for both equal and unequal costs.

Benchmarking across different baselines is challenging due to the large variation in the number of parameters (e.g., GREED has 2x more parameters than ERIC). Performance can vary with changes in the depth and width of different layers, making it difficult to create a standardized comparison platform without keeping the embedding dimensions and the number of GNN layers the same across all baselines. For example, in the restricted parameter setting, ERIC has a lower MSE than GREED, while in the original parameter setting, where GREED uses 2x the parameters of ERIC, it has a lower MSE than ERIC. This could be due to capturing spurious correlations rather than improving inductive bias.

analysis on Sinkhorn iterations

The following table shows the effect of varying the number of Sinkhorn iterations, under the equal cost setting on the Mutag dataset.

We observe that within 12 iterations, it reaches 93% of the optimal MSE reported at 20 iterations.

edit costs as initial features

In order to ensure high-quality benchmarking, we allowed all baselines to leverage the knowledge of edit costs as much as possible, as they were not primarily designed for non-uniform edit costs. We had believed that this improves their inductive bias. As suggested by the reviewer, we performed an ablation study on the initialization of different baselines. The following table shows the results for Mutag and code2 (Fig D in global-pdf shows the rest). We observed that there is no consistent winner among different type of initializations. For ERIC and SIMGNN, in majority of cases, the setting without cost initialization is very marginally better than cost based initialization. GraphEdX outperforms all baselines. In the final draft, we will take the best performance across both settings for each baseline.

inference time in Figure 26 seem illogical

We are thankful to the reviewer for spotting this. Upon closer inspection, we found that the inference times reported in Figure 26 included data batching time. Methods like GMN-Match, EMN-Embed, ISONET, and GraphEDX use numpy-CPU-based batching, while others use the PyTorch Geometric Data batching API, which is slower for our datasets. This was unfair to ERIC and possibly other baselines. To ensure a fair evaluation, we removed the data batching time and tracked only the forward pass times for each model. The updated histograms in Figure E of the global PDF show that ERIC is one of the fastest baselines. Additionally, GraphEDX is significantly faster than GMN-Match and H2MN, and comparable to ISONET.

The current model may not fully address richly attributed graphs with complex node and edge features.

We did not perform any experiments on node and edge features, but we can encode node feature and edge features in our models. Specifically, node features can be encoded during feature initialization and edge features can be encoded in the message passing step Eq. 24, page 22 as $LRL _{\theta} (x _k(u), x _k(v), \text{EdgeFeature} _{uv})$ instead of $LRL _{\theta} (x _k(u), x _k(v))$.

To show the transfer learning ability, I encourage the authors to try training on one dataset and testing on another. This would reduce concern on overfitting to one particular dataset.

In the following, we show the inference MSE of different models trained on the AIDS, Yeast, Mutag, and Molhiv datasets, when tested on the AIDS dataset. Analyzing the table column-wise, we observe the expected drop in performance across all methods when using models trained on datasets other than AIDS. Additionally, within each individual row, GraphEDX consistently outperforms all baselines, regardless of the training dataset. In Table C of the global pdf, we present comparison with all baselines.

What is the cost of training and estimation?

In Appendices F.11 and F.12, we discuss the computational cost of GED estimation. The following table presents the total training time and the amortized per-graph pair inference time (in milliseconds) for different methods on all dataset. The training time includes variations due to different numbers of training epochs for each method, under the same early stopping criteria. The inference time is averaged across all graph pairs and does not include data preprocessing times, which may vary across methods. In the global PDF, we provide the histogram of per-graph pair inference time (Figure E).

We observe that GraphEDX is generally faster in training than GMN-Match, ERIC, and H2MN, and is comparable to SimGNN and GraphSIM. In terms of inference, GraphEDX is significantly faster than GMN-Match with cost-guided distance, which outperforms all other baselines in terms of accuracy (see Table 3 vs. Table 2 in the main paper), but is slower than ERIC and EGSC. However, the efficiency of ERIC and EGSC comes at the cost of lower accuracy.