Graph Edit Distance with General Costs Using Neural Set Divergence

Summary

This paper studies the approximation of non-uniform Graph Edit Distance (GED) using graph neural networks. It considers four types of edit operations with different costs: edge deletion, edge addition, node deletion, and node addition. The paper proposes explicitly accounting for the costs assigned to each type of edit operation to adapt to both uniform and non-uniform cost settings. Moreover, it introduces node-pair embeddings for connected and disconnected node pairs within graphs as edge and non-edge embeddings. It computes the node and node-pair alignments through three types of distance functions to approximate the considered operations. Experiments on real-world datasets under a variety of edit cost settings show that the proposed method outperforms selected baselines on chosen metrics.

Strengths

* This paper studies an important task with many real-world applications. * The authors propose generating learnable embeddings for disconnected node pairs, which is new to me. * Extensive experiments have been conducted.

Weaknesses

* The clarity of the paper should be improved. For example: * What are the differences between the pad indicator $q$ and $η$? Are they inconsistent notation? * The paper is not self-contained. The related work should be in the main paper rather than in the appendix. Additionally, some related work, such as [1], which clearly highly influences this paper, is missing. * The technical contribution of this paper is somewhat limited, as it directly uses MPNNs for representing nodes and the Gumbel-Sinkhorn network to establish alignment. * The size of the graphs used in the experiments is relatively small (with at most 20 nodes) compared with the graphs used in other neural approaches. * Restricting the model parameters for the baselines does not seem fair to me, since the proposed model heavily relies on the iterative non-parameterized Gumbel-Sinkhorn refinement. * The size of the graphs used in the experiments is relatively small, so it is unclear if the proposed model can scale to graphs with, say, one or two hundred nodes. Moreover, since obtaining training data for GED is nontrivial, it is also unclear how the proposed model performs when the supervision signal is not the optimal GED value. I suggest that the authors conduct experiments on commonly used GED datasets with larger graphs, such as the IMDB dataset provided in [2], or use large synthetic graphs following [3]. Minors: * There are some typos (Line 278 Additiional -> Additional). Some sentences are missing periods, for example, in Lines 273, 551. * The caption of tables should be above the tables. Reference [1] Piao C, Xu T, Sun X, et al. Computing Graph Edit Distance via Neural Graph Matching[J]. Proceedings of the VLDB Endowment, 2023, 16(8): 1817-1829. [2] Yunsheng Bai, Haoyang Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. 2019. SimGNN: A Neural Network Approach to Fast Graph Similarity Computation. Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining (2019). [3] Roy, Indradyumna et al. “Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks. NeurIPS 2022.

Questions

* To what extent does the performance of the proposed model rely on the number of refinement iterations of the Gumbel-Sinkhorn network? Can the authors provide an analysis in this respect? * To incorporate non-uniform edit costs into baselines, the author include the edit costs as initial features in the graphs. However, most baselines such as Eric [1] and SimGNN [2] only rely on the supervision signal during training. I wonder whether such an initialization is necessary and beneficial. * The results regarding the inference time in Figure 26 seem illogical to me. Given that the complexity of Eric [1] is $\mathcal{O}(m + d_{ms}d^{′}T )$ in the inference stage (see the original paper), while the proposed method is at least $\mathcal{O}(k \cdot N^2)$, where $k$ is the number of refinement iterations, $N$ is the number of nodes. Can the authors provide the complexity analysis of the propose method? References [1] Wei Zhuo and Guang Tan. 2022. Efficient Graph Similarity Computation with Alignment Regularization. In Advances in Neural Information Processing Systems, Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (Eds.). https://openreview.net/forum?id=lblv6NGI7un [2] Yunsheng Bai, Haoyang Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. 2019. SimGNN: A Neural Network Approach to Fast Graph Similarity Computation. Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining (2019).

Rating

4

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

N/A

Summary

This paper proposes GRAPHEDX, an innovative neural model that deftly handles Graph Edit Distance (GED) calculations with customizable edit costs. By representing graphs as rich sets of node and edge embeddings and using a Gumbel-Sinkhorn permutation generator, GRAPHEDX captures the subtle nuances of graph structure that influence edit distances. Experiments across diverse datasets demonstrate GRAPHEDX's superiority, with the model consistently outperforming state-of-the-art baselines by significant margins, especially in scenarios with unequal edit costs.

Strengths

1. The handling of GED metric with unequal cost is a timely and under-explored topic. In real world, many use cases involving GED need to consider such unequal cost scenario. 2. Rigorous evaluation on both the accuracy and efficiency (runnign time) is performed, showing that the proposed method achieves high accuracy while maintaining efficiency. 3. The current model may not fully address richly attributed graphs with complex node and edge features. 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 The paper is well-written.

Weaknesses

1. The current model may not fully address richly attributed graphs with complex node and edge features. 2. 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

Questions

N/A

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

N/A

Summary

This paper proposes GRAPHEDX, a neural model that learns to estimate the graph edit distace among a pair of graphs, not only in the case of equal and symmetric costs for edit operations, but in the case of unequal costs specified for the four edit operations. The core of the proposal represents each graph as a set of node & edge embeddings, designs neural set divergence surrogates based on those embeddings, and replaces the QAP term corresponding to each operation with its surrogate. The method learns alignments to compute surrogates via a Gumbel-Sinkhorn permutation generator while also ensuring consistency between the node and edge alignments and rendering them sensitive to the presence and absence of edges between node-pairs.

Strengths

S1. Addresses a gap in the field that previous works have left open. S2. Outpeforms previous effort in both equal-cost and unequal-cost settings.

Weaknesses

W1. The cost of training and estimating is not shown.

Questions

Q: What is the cost of training and estimation?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

Yes.

Summary of Rebuttal and Thanks to Reviewers

We are grateful for the detailed feedback from the reviewers. In response, we have provided the following clarifications: **Cost of Training and Estimation:** We provided detailed information on the computational costs of GED estimation and presented the training and inference times for different datasets and methods. In particular, we appreciate Reviewer 81fW’s feedback on inference time measurements. Based on their input, we revised our estimates to exclude data batching time, resulting in more accurate comparisons. The updated results show that GraphEDX is significantly faster than GMN-Match and H2MN, and competitive with ISONET, providing a clearer picture of our method's efficiency. **Scaling to Larger Graph Sizes:** We demonstrated scalability by training under noisy ground truth for larger graphs. Our method consistently outperformed the baselines, indicating robustness in handling larger, noisier datasets with more complex graphs. **Comparison with Additional Baselines:** We compared GraphEDX with GEDGNN under both equal and unequal cost settings. GraphEDX significantly outperformed GEDGNN across all datasets, particularly in the unequal cost setups where GEDGNN is not specifically designed to excel. **Feature Initialization and Number of Parameters in Baselines:** We addressed concerns regarding the number of parameters and initial features for the baselines. We compared model performances with both original and our parameter settings and conducted an ablation study on different initialization strategies. Our results show that GraphEDX consistently outperforms all baselines across these settings. We will update the numbers in the final draft to ensure that all baselines are given the best possible advantage under these configurations. **Sensitivity to Sinkhorn Iterations:** We investigated the sensitivity of our method to the number of Sinkhorn iterations. Our results show that within 12 iterations, the method reaches 93% of the best performance earlier reported at 20 iterations, demonstrating that our approach converges efficiently, with a reliably diminishing returns profile. We appreciate the reviewers' feedback, which can be readily incorporated in the final version of the paper.