GraSP: Simple yet Effective Graph Similarity Predictions

We thank your insightful comments, and we have thoroughly addressed them as follows. We look forward to your reply.

W1. The presentation of the content, particularly in Section 3, lacks clarity and cohesiveness.

Response: Thanks for the suggestion. We have enhanced the overview paragraph at the beginning of Section 3 to make it clear and cohesive.

W2. The authors should consider a more nuanced exposition of the method's unique efficiencies, supplemented by robust experimental evidence, to substantiate claims of its advancement over current practices.
Q6. How does GRASP tackle the issue of efficiency, and what factors make it an efficient solution?

Response: The efficiency of the proposed GraSP is due to the following designs. First, GraSP does not need the expensive cross-graph node-level interactions that are usually adopted in existing methods. Second, the positional encoding used in GraSP to enhance node features can be precomputed and reused for the efficiency of online inference. Third, all the technical components in GraSP are designed to make the complicated simple and effective for graph similarity predictions, resulting to efficient performance. By following the literature, we report the inference time per 10K pairs in Figure 4 of the paper, where GraSP is the fastest method to predict graph similarity scores, which experimentally validates the efficiency of GraSP. As suggested, we have added the exposition above into Section 5.3 of the revised paper.

W3. The authors assert that prevailing cross-graph interaction modules contribute significantly to computational overheads. However, the delineation of how their proposed GRASP framework, which ostensibly employs similar cross-graph interactions via NTN, innovates upon or diverges from traditional methodologies is ambiguous. This lack of clarity muddles the reader's understanding of any novel contributions the paper might be making in this specific aspect of the framework. It is imperative for the authors to elucidate the nuanced operational differences, if any, introduced by GRASP that ameliorate the time-costly nature of cross-graph interactions, distinctly setting their approach apart from conventional ones. This clarification could significantly enhance the perceived value and ingenuity of their methodology.

Response: We clarify that in Eq. (7), NTN is applied to two graph embeddings $\mathbf{z}_1$ and $\mathbf{z}_2$ to get an interaction value, interaction$(\mathbf{z}_1, \mathbf{z}_2)$. The interaction value in Eq. (7) is essentially a multi-headed weighted cosine similarity score, which is efficient to compute. It is different from the cross-graph node-level interactions required in existing studies as reviewed in Section 6. Specifically, the interactions in existing studies refer to the expensive node-level matching or node-graph matching processes across graphs, which take quadratic time w.r.t. the number of nodes. As explained in the response to W2 above, our GraSP does not need such expensive cross-graph nodel-level interactions.

Q5. What sets NTN apart from existing methods of cross-graph interaction, and why is NTN a suitable option for your proposed approach?

Response: Following the response to W3 above, NTN is a powerful way to quantify the similarity between two embeddings via multi-headed weighted cosine similarity, and thus it is a suitable choice in Eq. (7). To demonstrate the suitability and effectiveness of NTN, we extend our ablation study and ablate NTN from GraSP, and report the results. We find that NTN is beneficial in GraSP to improve performance. We have included the new ablation in Table 3 of the paper.

Table A. Ablating NTN

Q1. Numerous methods exist to enhance the expressiveness of GNNs. What motivated your decision to exclusively focus on positional encoding in your approach?

Response: Positional encoding is well suited to the studied problem, because graph similarity is closely related to graph isomorphism testing (1-WL test) that determines whether two graphs are exactly the same. Therefore, we hope to enhance the expressive power of GNN to pass 1-WL, and as a result, improve the performance on graph similarity predictions, which motivates our decision to employ positional encoding.

Dear Reviewer dX6K,

We thank your recognition of the excellent soundness of our work. Your insightful comments are solvable, and we have addressed them all and improved our paper. This is a reminder for discussion. Your feedback is important to us.

Summary of responses:

• We have conducted new experiments to ablate NTN (Q5), and clarified the purpose of NTN in our method (W3).
• We have explained the efficiency of our method with experimental results (W2, Q6).
• We have provided evidence on the design of our pooling technique (Q3).
• We have improved the presentation of the paper (W1).
• We have explained the motivation of our technical designs (Q1, Q2), and explained the difference between GED and MCS, and their importance (Q4).

Best,
Authors

W2 & Q4. What are the statistics of train-validation-test sets?

Response: We split training, validation, and testing data with a ratio of 6:2:2 for all datasets and all methods, by following the same setting as SimGNN and GraphSim.

W3. The MSE scores of baselines reported in the paper do not align with the existing literature. For example, GREED outperforms other baselines such as H2MN, SIMGNN in the literature but it is not reflected in this paper. What is the source of this discrepancy? Were all methods trained on error over GED or over the similarity score. The authors need to release the version of code they used benchmarking the baselines and the exact loss function so that reproducibility and any source of discrepancy can be properly analyzed.
Q1. It's unclear whether the reported MSE scores for GRASP are a result of the loss computed using the GED or similarity scores (obtained after normalization of GED). The code, specifically Line 170 in src/trainer.py, appears to calculate the loss using GED/Similarity score based on the command line parameters.

Response: The original papers of existing methods usually adopt different data split ratios. For example, GREED paper uses "100K query-target pairs for training and 10K pairs each for validation and test". In our paper, to be consistent across all methods, we split every dataset in the ratio of 6:2:2. A method can have different results with different data split ratios, which is a main source of discrepancy. In the original paper of GREED, three datasets AIDS, Linux, and IMDBMulti are used for GED predictions. In Table A of the response to W1 above, the RMSE results of GREED on AIDS, Linux, IMDBMulti are on par with the original paper of GREED, which shows our reproducibility on baselines. Moreover, in Table 1 of our paper, GREED outperforms H2MN by 10 out of 15 metrics and SIMGNN by 12 out of 15 metrics on the three datasets, which again illustrates the reproducibility of our experiments. At Line 170 in src/trainer.py, we just provide users with the command-line options to train by either GED or similarity scores. As suggested, we have included the codes of all methods in the anonymous code repository.

W4.(a) Heatmaps on datasets with larger graphs such as PTC.

Response: As suggested, we have included the heatmaps of PTC, LINUX, and IMDBMulti in Figures 9,10,11 of Appendix A.5 in the revised paper. The new heatmaps also show that our method GraSP achieves low error, indicated by a light color.

W4(b) It is not clear how Grasp generalizes for unseen graph sizes. Given that generating ground truth for graphs with larger sizes is expensive, it is interesting to see how Grasp performs when training is done with smaller graphs and testing is done on larger unseen graphs. This aspect needs to be compared with other state-of-the-art baselines such as GREED and H2MN.
Q5. How does the accuracy vary with query size and GED on datasets with larger graphs?

Response: As suggested, we conducted new experiments by following the experimental setting in GREED to test the generalization ability of GraSP on large unseen graphs for GED predictions, compared to GREED and H2MN. Specifically, we get GraSP-25 and GraSP-50 by training GraSP on graphs with node sizes up to 25 and 50, respectively, and then test on graph pairs in which the number of nodes in the query graph is in the range [25, 50]. Table B shows the results of PTC data. Observe that (i) the performance of all methods degrades for large query sizes in [25,50], compared with the entire set in [0,50], (ii) when trained using smaller graphs from 50 to 25 size, all methods also degrade, (iii) our method GraSP-25 (resp. GraSP-50) keeps the best performance than baselines GREED and H2MN under all these generalization settings.

Table B. Generalization on large unseen graphs with RMSE results to predict GED directly.

We thank your insightful comments, and we have thoroughly addressed your comments via extensive experiments and detailed explanations. We look forward to your reply.

1. We have justified the GED training setting, and conducted new experiments to predict GED by all methods (W1, Q2, Q6).
2. We have clarified the data split ratio (W2, Q4), explained the source of discrepancy, and demonstrated the reproducibility of the experiments by experimental results and releasing all codes of baselines (W3, Q1).
3. We have provided the heatmaps of all datasets (W4(a)).
4. We have conducted new experiments to evaluate the generalizability of GraSP for unseen large graphs (W4(b), Q5).
5. As suggested, we highlighted our novelty (W6), and discussed how to extend the work to include edge relabeling (W5).
6. We have conducted a new ablation study on NTN in GraSP (Q3).

W1. The authors presented MSE on predicted similarity scores (obtained by exponentiating a normalized version of GED) instead of predicted GED. Given the task is to predict GED, results should be reported on GED itself and not its transformation to a similarity metric that distorts the true errors. While some previous works, such as SIMGNN have also followed the same methodology of reporting results on exponentiated similarity instead of true GED, there is no justification for this transformation.
Q2. Are the baseline models trained to output GED scores or similarity scores (obtained after normalization of GED)? Models such as GREED are trained to output GED, training them to output similarity scores might affect the performance.
Q6. What are the RMSE scores of GRASP and other baselines on GED?

Response: Same as GREED, our method GraSP is designed to predict the original GED directly. However, note that the majority of existing methods, except GREED, are all trained to predict a normalized version of GED. Echoing your comment in Q2 on minimizing the impact on the performance of existing methods, we wish to make the least changes to existing methods and make the evaluation metric values comparable. Therefore, in the paper (i) we trained GraSP and GREED to output GED predictions directly, and then, as stated in Section 5.1, we normalize their predictions to calculate evaluation metrics; (ii) for the other baselines, we also followed their original design of using normalized GED for training and prediction. Note that RMSE is just the square root of MSE that is used in our paper. Upon your request in W1 and Q6, here we change the official codes of all baselines to predict GED directly, and report the RMSE results below, while including the complete results in Appendix A.7. Observe that GraSP consistently achieves better RMSE than existing methods for directly predicting GED on all datasets.

Table A. The RMSE of all methods when predicting GED directly

W5. The estimated GED didn’t include costs for relabeling of edges. The authors didn’t mention how to extend this work to include edge substitution costs.

Response: As suggested, we have added the explanation on how to extend our method to include the cost of relabeling edges in Appendix A.8. Specifically, one possible way is that, instead of the gate $\eta_{i,j}$ in Eq. (3) of the paper, with reference to [1], we can modify Eq.(3) to adopt an edge gate $e^{(\ell)}_{i,j}$ :

$h_i^{(\ell)} = h_i^{(\ell - 1)} + {ReLU}(W_1 h_i^{(\ell - 1)} + {\underset{j \in \mathcal{N}(i)}{\sum}} {e_{i,j}}^{(\ell)}\odot W_2h_j^{(\ell - 1)})$, where $e_{i,j}^{(\ell)}$ is the edge gate and can be defined as: $e_{i,j}^{(\ell)} = \sigma(e_{i,j}^{(\ell - 1)} + ReLU(A h_i^{(\ell - 1)} + B h_j^{(\ell - 1)} + Ce_{i,j}^{(\ell - 1)}))$, where $A,B,C \in \mathbb{R} ^ {2d \times 2d}$ and $e^{(0)}_{i,j}$ represents the input edge features.

[1] Vijay Prakash Dwivedi et al. Benchmarking Graph Neural Networks. Journal of Machine Learning Research, Volumn 24. 2023.

W6. The novelty of GRASP is limited apart from using positional encoding. Grasp tackles the issue of cross-graph interactions, although it's important to recognize that Greed had already addressed this limitation before Grasp.

Response: We acknowledge that the issue of cross-graph interactions has been studied in the literature. Our novelty lies in the different technical designs to mitigate this issue, compared with existing methods. In the proposed GraSP, for the first time, positional encoding is introduced for the task of graph similarity prediction to enhance node features for higher expressiveness; GraSP further employs a graph neural network with gating and residual connections, and utilizes a multi-scale pooling technique to generate meaningful representation for accurate graph similarity predictions. Our theoretical analysis shows that GraSP can exceed 1-WL test. Notably, GraSP is versatile to accurately predict GED and MCS, and achieves superior performance across various datasets.

Q3. How is the Neural Tensor Network (NTN) affecting the performance of the method? Have you considered using only L2-Norm to predict GED, which will preserve the metric property as well? This analysis is not included in the ablation study.

Response: As suggested, we ablate NTN in GraSP and report the results below. Observe that NTN helps GraSP to improve performance on all datasets, since NTN can be considered as a complement to the Euclidean distance over the graph embeddings in Eq. 6,7,8 of the paper. We have included the new ablation into Table 3 of the revised paper.

Table C. Ablating NTN

Dear Reviewer NSFb,

We appreciate your willingness to revisit the rating. We have put considerable effort into addressing all your constructive comments, including experiments on reproducibility (release of baseline implementations, train-test-validation stats, loss function clarifications), performance on true GED, and more experiments in terms of generalizability to unseen, larger sizes, heatmaps, etc. We summarize the responses below. Please have a look and discuss. Thanks.

• As suggested, we have clarified the GED training setting, and conducted new experiments to predict GED by all methods (W1, Q2, Q6).
• We have provided the data split ratio (W2, Q4), explained the source of discrepancy, demonstrated the reproducibility of experimental results, and released all codes of baselines (W3, Q1).
• We have provided the heatmaps of all datasets (W4(a)).
• We have conducted new experiments to evaluate the generalizability of GraSP for unseen large graphs (W4(b), Q5).
• As suggested, we highlighted our novelty (W6), and discussed extending the work to include edge relabeling (W5).
• We have conducted a new ablation study on NTN in GraSP (Q3).

Best,
Authors

2. Why is GREED being trained on GED when the metric being measured is on the exponentiated version (for Table 2)? It's an easy change in loss function. For a fair comparison, it demands that the loss function is aligned with the metric being used. That is not the case and hence the experiments paint a wrong picture.

Response: Again, we guess it should be Table 1 in our paper, instead of Table 2. (i) As explained, to minimize the changes to baselines, GREED was trained with its original loss function on GED, while the other baselines also followed their original design to train over exponentially normalized GEDs. (ii) Upon your previous comment, we have already provided the results of GREED and all methods trained on original GED, where GREED is the top baseline, as shown in Table A above and Table 6 in the revised paper. (iii) Here, we further revise the loss function of GREED in the code to cope with similarity scores. We provide the results of GREED trained on similarity scores in Table D(1) below. We also copy the results of GREED trained on original GEDs from Table 1 in the paper to Table D(2) for comparison. Note that the MSE in Table D(2) is calculated by exponentiating the predicted GEDs as we discussed on Section 5.1 in the paper. We observe that all metrics, including the MSE, are comparable for these two versions of GREED. Therefore, we conclude that our experiments are fair and reproducible.

Table D(1). GREED, trained on similarity scores.

Table D(2). GREED, trained on original GEDs (from Table 1 of the paper).

3. I also find it surprising that while the authors report some generalizability results on graphs of unseen sizes in the openreview comments, they are not included in the revision? Why?

Response: It is included in appendix A.9 of the revised paper now.

We thank your insightful comments, and we have thoroughly addressed them as follows. We look forward to your reply.

W1. It would be interesting to know what would be the alternative to the proposed combination of summation and attention pooling, e.g. what if a simple non-learning combination is used, i.e. $\alpha * z_{sum} + (1-\alpha)* z_{att}$ where $\alpha$ is a hyperparameter scalar. This will further highlight the importance of learnable combination of the two pooling methods.

Response: As suggested, we vary a non-learning scalar value $\alpha$ from 0 to 1, with MSE results on GED prediction in Table A below, where the last row shows GraSP with the proposed learnable combination. Observe that (i) the proposed learnable combination in GraSP achieves the best performance on all datasets; (ii) the non-learning combination needs different $\alpha$ scalar values on different datasets, which is tedious to tune. These observations highlight the importance of the proposed learnable combination of the poolings.

Table A. MSE ($\times 10^{-3}$) results on learnable combination v.s. non-learning combination.

W2. The overall novelty is limited, given the adoption of random walk positional encoding and combination of existing graph pooling are not firstly proposed in this paper.

Response: Compared with existing methods for graph similarity predictions, our novelty lies in the different technical designs to achieve superior performance for predicting GED and MCS. To our knowledge, we are the first to introduce positional encoding to the graph similarity predictions to node features for higher expressiveness. Furthermore, GraSP employs a graph neural network with gating and residual connections, and utilizes a multi-scale pooling technique to generate meaningful representation for accurate graph similarity predictions. Our theoretical analysis shows that GraSP can exceed 1-WL test. Notably, GraSP achieves superior performance across various datasets.

Q1. Why the time complexity for computing the random walk positional encoding can be omitted? For each new graph pair, the inference time should include such positional encoding, since at inference time, the graph pair can be new and thus unseen by the model. Unless the authors assume a database-like setting, such overhead cannot be omitted.

Response: Note that the positional encoding is applied per graph, instead of per graph pair. During online inference, if a graph appears in multiple graph pairs, the positional encoding of the graph is computed only once, but used many times. Therefore, given a dataset of graphs, we can pre-compute and store the positional encoding of every graph. Then, during online inference, given a graph pair, we only need to retrieve the encodings of the two graphs in the pair and reuse them as the input of GraSP. This explains why the time complexity of positional encoding can be omitted for inference time.

Dear Reviewer Ytzi,

We are grateful for your appreciation on our work. This is a reminder for discussion. We have addressed all your constructive comments in the responses. Thanks.

Best,
Authors