Node Number Awareness Representation for Graph Similarity Learning
Authors: JaX Lyu
Liang Zhang
Yi Huang
Shifeng Chen
Guangming Zhu
Mohammed Bennamoun
Syed Afaq Ali Shah
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph representation learning
graph similarity learning
graph matching

Abstract: This work aims to address two important issues in the graph similarity computation, the first one is the Node Number Awareness Issue (N$^2$AI), and the second one is how to accelerate the inference speed of graph similarity computation in downstream tasks. We found that existing Graph Neural Network based graph similarity models have a large error in predicting the similarity scores of two graphs with similar number of nodes. Our analysis shows that this is because of the global pooling function in graph neural networks that maps graphs with similar number of nodes to similar embedding distributions, reducing the separability of their embeddings, which we refer to as the N$^2$AI. Our motivation is to enhance the difference between the two embeddings to improve their separability, thus we leverage our proposed Different Attention (DiffAtt) to construct Node Number Awareness Graph Similarity Model (N$^2$AGim). In addition, we propose the Graph Similarity Learning with Landmarks (GSL$^2$) to accelerate similarity computation. GSL$^2$ uses the trained N$^2$AGim to generate the individual embedding for each graph without any additional learning, and this individual embedding can effectively help GSL$^2$ to improve its inference speed. Experiments demonstrate that our N$^2$AGim outperforms the second best approach on Mean Square Error by 24.3\%(1.170 vs 1.546), 43.1\%(0.066 vs 0.116), and 44.3\%(0.308 vs 0.553), on AIDS700nef, LINUX, and IMDBMulti datasets, respectively. Our GSL$^2$ is at most 47.7 and 1.36 times faster than N$^2$AGim and the second faster model. Our code is publicly available on https://github.com/iclr231312/N2AGim. 

Under review as a conference paper at ICLR 2023
NODE NUMBER AWARENESS REPRESENTATION FOR GRAPH SIMILARITY LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
This work aims to address two important issues in the graph similarity computa- tion, the first one is the Node Number Awareness Issue AN) and the second one is how to accelerate the inference speed of graph similarity computation in downstream tasks. We found that existing Graph Neural Network based graph similarity models have large error in predicting the similarity score of two graphs with similar number of nodes. Our analysis shows that this is because of the global pooling function in graph neural networks that maps graphs with similar number of nodes to similar embedding distributions, reducing the separability of their em- beddings, which we refer to as the N AI. Our motivation is enhance the differ- ence between the two embeddings to improve their separability, thus we leverage our proposed Different Attention (DiffAtt) construct Node Number Aware- ness Graph Similarity Model (N² AGim). In addition, we propose the Graph Similarity Learning with Landmarks (GSL3) to accelerate similarity compu- tation. GSL uses the trained N2 AGim to generate the individual embedding for each graph without any additional learning, and this individual embedding can effectively help GSL 2 to improve its inference speed. Experiments demonstrate that our AGmG outperforms the second best approach on Mean Square Error by 24.3% 77.1 vs 1.546), 43. (0.0666 vs 0.116), and 44.3%(0.308 vs 0.553), for AIDS700nef, LINUX, and IMDBMulti datasets, respectively. Our GSL2 at most 47.7 and 1.36 times faster than N AGim and the second faster model. Our code is publicly available on
INTRODUCTION
Graph similarity computation is a fundamental problem for graph-based applications, e.g., graph data mining, graph retrieval, and graph clustering (Kriege et al.) 2020: Ok & Korea| 2020). Graph Edit Distance (GED), which is defined as the least number of graph edit operators to transform graph G2 to graph Gj. is one of the most popular graph similarity metries (Gao et al. 2010 Neuhaus jet al. 2006 Bougleux et al.) 2015). The graph edit operators are insert or delete a node/edge, or relabel an edge. Unfortunately, the exact GED computation is NP-Hard in general (Zeng et al. 2009). which is too expensive to leverage in the downstream tasks.
Recently, many Graph Neural Networks (GNNs) based graph similarity computation algorithms have been proposed to compute the GED in faster manner (Bai et al. 2019 2020; Li et al. 2019 Ling al. 202T Bai & Zhao, 2021 Wang et al. 2021). The GNN-based algorithms transform the GED value to similarity score and use an end-to-end framework to learn to map the given two graphs to their similarity score. As a general framework, the Siamese neural network can be used to aggregate information on each graph, while the feature fusion module can be used to capture the similarity between them, and the Multi-layer Perceptron (MLP) is then leveraged for the regression.
However, the existing popular graph similarity models become very inaccurate in predicting the similarity of two graphs with similar number of nodes, as shown in Fig [ is clear that the MSE of all four models becomes large as the difference in the number of nodes in the two graphs becomes smaller. In order to better understand this issue, we present in Section B a theoretical analysis of the most widely used modules in the graph similarity models from statistical viewpoint. As shown in Fig[[a)-()) our conclusion is that all global pooling functions, also called graph readout functions, map graphs with similar number of nodes similar embeddings, which reduces the separability

---

Under review as a conference paper at ICLR 2023
AIDS 100xd
HEMM Roses EEBEC
LINUX
HOMN DOSCS Gracd
ITMN DOSES Grapdiii
Figure I: Histogram of the Mean Square Error (MSE) of the existing graph similarity models on three datasets at different level of SizeDiff. The SizeDiff represents the percentage difference in the number of nodes and is defined as Dieeif,f(G,.. G2) = |Ni - N21/ Na//max((N) (o,ax(,,,,, where N; is the number of nodes in Gj. is clear that all models have a larger MSE when the SizeDiff'ss is smaller, i.e. when the number of nodes in the graph pair is similar.
between embeddings and leads to large MSE for the models in predicting the similarity of two graphs with similar number of nodes. We refer to this issue of indistinguishable embeddings of graphs with similar number of nodes as the Node Number Awareness Issue (N2 AT).
Our motivation to address the N Al is to focus more on the differences between two similar embed- dings during the learning process, and we propose the Different Attention (DiffAtt) to construct our Node Number Awareness Graph Simialrity Model (N"AGim). DiffAut simple in architec- ture, and can be added as plug-and-play module to any global pooling method. Our evaluations on three datasets (Section 5) demonstrate that the models with different pooling methods achieve significant improvement after using DiffAtt. Moreover, our N AGim achieves state-of-thes the--hhrrrr performance compared to the popular GGNN-bacce graph similarity models, e.g., better about on av- erage 30.35 0.772), 50.55 1.059) on Mean Square Error (MSE) than EGSCT (Qin et al. (021) and GraphSim (Bai et al. 2020). respectively.
Ne1
(61
B3
B
Ealy-Seion Model
Tidteddal Model
Indirdaal Modal
Ams AaitBakcken
bacidaa babecdan
MtlPs
MLP
Figure 2: (a)-(d) Distributions of output from different global pooling functions with N nodes, which show that all global pooling functions map graphs with similar number of nodes to similar distributions. See Section 3 for details. (e) Illustration of the Nº i.e., the distribution of the embeddings of two graphs with similar number of nodes is indistinguishable. Region A represents where two distributions overlap, while is the opposite. Our aim is to enhance the information in B to address the N AL. (f)(g) Illustration of the Early Fusion Model (EFM) and Individual Embedding Model (IEM).
Another issue of interest in the field of graph similarity learning is to accelerate the inference speed of graph similarity models in downstream tasks. Qin et al. (2021) divided the graph similarity models into two categories, one is the Early Fusion Model (EFM), shown in Fig f which performs feature fusion at an early stage to achieve high accuracy but slow inference, and the other one is the Individ- ual Embedding Model (IEM), shown in Fig 2(g), which generates an individual embedding for each graph and then performs fusion. This model Is fast but achieves low accuracy. The existing solution (Qin et al. 2021 uses special designed Knowledge Distillation (KD) paradigm to leverage EFM teacher to improve the individual embeddings generaged by the IEM student. However, motivated by Balcan et al./ (2008), we propose faster and more accurate IEM called Graph Similarity Learn- ing with Landmarks (GSL"). In GSL?, a subset of graphs, called landmarks S, are selected, and then each graph G is represented as a vector uG = [GED G1).... GED Gm,)", where G E S. Finally, an MLP is learned to map the concatenation of the embeddings of the two graphs to their GED target. Instead of learning the embeddings on the graph data, our GSL2 uses an al- ready trained graph similarity model to directly generate an individual embedding for each graph, and this individual embedding can effectively improve the inference speed of GSL.. To sum up, the contributions of this paper can be summarized as follows:
2

---

Under review as a conference paper at ICLR 2023
We found that the existing graph similarity models have a relatively large error in predicting the actual similarity of two graphs with similar number of nodes, because the global pooling function maps graphs with similar number of nodes into two distributions that are similar, which we refer to as N AI, thus reducing the performance of the graph similarity learning. A novel GNN-based graph similarity model, named N AGim, is proposed. Our N AGim achieves excellent results in the graph similarity learning task by leverage the proposed Diff'tt to effectively address the A²
In order to speed up the inference of graph similarity models, we propose the GSL The GSL directly represents each graph as vector, where each component is the GED value between the graph and landmark. GSL 2 then learns the target GED values based on these graph representations.
Experimental results show that our AGiG achieves the state-of-the-art performance, while our GSL achieves a good accuracy and inference speed to efficiently handle down- stream tasks.
2 PRELIMINARIES
2.1 GRAPH NEURAL NETWORKS
Graph data 9 can be viewed as pair of adjacency matrix A E {0, 1)NNN and a node feature matrix X E Nx N is the number of nodes in the graph, and C is the dimension of the initial node features. Node i and node have an edge if and only if A = 1. Considering
X 12,,2, .... _N|" Message Passing Neural Network (MPNN) layer is defined as (Fey & (k) Lenssen 2019) x; = =7(h) (10 Dee (a:("11), .r5 (,, etg)), where 2,!4) RC* is an embedding of node at the htth layer, and o performs a differentiable transform on each node or edge. D is aggregate function to aggregate the transformed attributes of nodes and their neigh- bors. N(i) denotes the neighbors of node and fi is the edge feature from node to node j. 7 is a differentiable function to update the node embeddings. Following the idea of MPNN, several GNNs and their variants have been proposed to deal with graph mining tasks, c.g., Kipf & Welling (2016) and Velickovic al. (017)) One of the vital works is the Graph Isomorphism Network (GIN) (Xu et al.] (2018). which is at most as powerful as the Weisfeiler-Lehman (WL) graph isomorphism test
(Leman & Weisfeiler 1968), and it is defined as x = he ((1+ e) .r + Σjev()) z3) where
hh is an MLP. We believe that this representation ability is effective in addressing Nº Therefore, we leverage the GIN layer the backbone to construct our N AGim.
2.2 DEEP GRAPH SIMILARITY LEARNING
The graph similarity problem is defined as: given two graphs G, and Gj with their similarity metric, the graph similarity models learn function that maps the two graphs to their similarity metric. The Graph Matching Network (GMN) (Li et al.] 2019) is the first deep graph similarity model, which computes the similarity between given graphs by cross-graph attention mechanism. Bai jet al. (2019) turned the graph similarity task into a regression task. They not only proposed widely used graph similarity datasets, but also leveraged the GCN layers and self-attention-ball based fusion to design SimGNN. Further, in their later work (Bai et al. 2020), the proposed GraphSim directly learns the similarity based on the node-level interaction of the two given graphs. By leveraging a trained SimGNN to guide the search space of the A algorithm, GENN-A* * (Wang et al., 2021) achieves the best-in-clast performance, but needs too long inference time on the test data, i.e., 290.1 hours to solve the GED computation on AIDS700nef datasel (Qin el al. 2027). Considering that GENN-A* & too time-consuming in practice, we do not compare our proposed methods with it in our evaluations. In order to achieve faster speed, Qin et al. (2021) proposed Knowledge Distillation (KD) paradigm to improve the individual graph embeddings generated by the student model.
However, we found that none of these existing graph similarity models are designed to address the AL In order to address the AL our Nº AGim leverages the GIN layers and the proposed DiffAtt to enhance the differences between the embeddings of two graphs and therefore achieves the state-of-the-ang performance on benchmark datasets. Compared to EGSCS (Qin et al.) 2021). our GSL 2 directly generates individual graph representation for each graph, and the only learnable
3

---

Under review as a conference paper at ICLR 2023
Overlop probabiltt with N and Nel number of nodes
Overlap probabiilit with 5 and Sed number nedes.
GSP
GMP
GAP
Probabiity
0.50
Probabilis,
SDP
0.83
GMP
0.80
GAP
02-
SOP
00-
20
00
25
(b)
Figure 3: Overlapping probability of graph embedding with N and N + ô number of nodes. (a)
shows the overlap probabilities with different N when the is 1; (b) shows the overlap probabilities for different 5 when the N is 5.
parameter of our GSL 2 is simple MLP. Besides, the evaluation also shows that our GSL has higher accuracy and faster inference speed than EGSCS.
NODE NUMBER AWARENESS ISSUE (N²AI) ANALYSIS
Here, we provide formal theoretical analysis of Nº and reveal the reasons for its existence. GNNs usually generate the embeddings of graph by multi-layer GNN aggregation layers and global pooling methods. The GIN is known for having at most as powerful as WL-Test, that is, to distinguish whether two graphs are isomorphic, which indicates that GIN is effective in distinguish- ing graphs with similar node numbers and address the NºAL Hence, we focus on the impact of widly used different global pooling methods the AI, including the order statistical methods, i.e., Global Sum Pooling (GSP), Global Max Pooling (GMP), Global Average Pooling (GAP) and the second order statistical methods, i.e., Second Order Pooling (SOP) (Wang & Ji 2020).
Let's assume that the node feature matrix output by the graph neural network layers is X = [Vi, U2.... Vcl, where U, R.V is the feature the ith channel. We model all variables in X as i.id random variables that follow a Gaussian distribution (N,, Vu,,a²), where je > 0. The one order statistical methods F is used convert v. into single value g F(wz), which outputs fix-sized vector, and the second order statistical methods convert and 2y as single value = F(v,, vy), which outputs a fix-sized matrix. Here, we learn the AI by studying whether a pooling method F; can appropriately distinguish between X with number of nodes N and N + 6, i.e., the differenti- ation between the two distributions p(g] NN Fi) and p(g) N + 8, Fi), where ó denotes the difference between the number of nodes. We first assume that X obeys (11, 4) and show the output distri- bution of different pooling functions for different number of nodes in Fig (ig(a))(d) Intuitively, all four global pooling methods have a lot of overlap in terms of output distribution when the number of nodes is similar, and less overlap in terms of distribution when the number of nodes is very different.
We further define the probability of this overlap with the following equation:
O(F, min F.). P(g + 5,F)) max (p(g)N, P(g. + (,F)) dg.
(1)
where ((F,, NN, 8) denotes the proportion of the overlapping area that occupies the total area of F, with N and N +8 nodes. Obviously, the outputs of the GSP and GAP obey the Gaussian distributions NNN, No²) and (p, o²) respectively, but it is difficult to obtain the distributions that the GMP and the SOP satisfy. Therefore, we perform large number of randomized experiments and leverage the Kernel Density Estimation (KDE) to obtain an approximate distribution for the GMP and SOP. The overlapping probabilities of the four global pooling methods are shown in Fig 3
From Fig it is clear that most of the global pooling methods overlap more than 80% of the area of the distribution with and ++1 nodes, which means that existing graph similarity networks have difficulty distinguishing graphs with similar number of nodes in the output distribution, thus leading to the AL According to Fig b), the probability of overlap between embedding distributions decreases as the difference in node counts increases. A way to address Al is to make the graph
similarity model focus on the differences between the two embeddings. Inspired by this, we propose the DiffAtt to enhance the difference between two embeddings generated by the above four global
4

---

Under review as a conference paper at ICLR 2023
Node Number Awareness Graph Similarity Model (N-AGim)
Stndacky
GiN Acd
ERN
GEN Add PF
GBS Mi
FFN
(b) Graph Similarity Learning with Landmark (GSLF)
Exphelding
A )
GED
GEDI
Prokesal RID
GED
... GED(
Groph
Grapk Enteldãs
Figure 4: (a) N2 AGim first uses the multi-scale GIN layers to aggregate the information in the graph, then DiffAtt for feature fusion, and finally MLP to predict the similarity scores. (b) GSL generates individual embeddings for each graph by calculating the GED values between them and landmarks, and then uses MLP to map the individual embeddings of the two graphs to their GED values.
pooling methods. The evaluation on benchmark datasets demonstrates that our DiffAtt brings a huge performance improvement to the graph similarity models.
PROPOSED METHODS
4.1 NODE NUMBER AWARENESS GRAPH SIMILARITY MODEL (N
Our proposed N AGim consists of three stages: Multi-Scale GIN layers, Different Attention based feature fusion and the MLP regressor. Fig (a) shows a block diagram of our N²AGim. On the following, we provide details of our proposed N2AGim:
Multi-Scale GIN layers. Given a graph data G' = (A, where A and X are as defined in Section the GIN layers, which can effectively address N AI because it most as powerful as WL-Test to distinguish whether two graphs are isomorphic
not, are leveraged as our backbone to update node embeddings. All the MLPs in GIN have one linear layer with the Layer Normalization (Ba et al. 2016) and ReLU activation function. Besides, we apply the residual connections (He et al.) 2016 and an additional FeedForward Neural Network (FFN) to enhance the node embeddings. We stack 3 GIN layers aggregate multi-scal. information of the node's 's neighbors. After each GIN layer, a one order statistical pooling method is applied to generate the graph embeddings.
Different Attention based feature fusion. We propose Different Attention (DiffAtt) to enhance the difference between the embeddings to address the N2 and obtain a joint embedding by fusing features of the two graph-level embeddings at each layer. Given the graph embeddings h! (k) and h (k) at the kth layer, the DiffAtt is defined as:
(t) Softmar(MLPs (K) h (1) (k) GG.
(latten(Att @ Ch (0) ue, flatten @ (0)
(k)
where (/) E RC is the enhancement embeddings G., the flatten(-) denotes the flatten opera- tion, and denotes the Hadamard Product. It is evident that DiffAtt give greater weight to large differences between the two emheddings and dynamically capture the differences that really matter with learnable parameters, which can effectively increase the separability of two graph embeddings with similar or even same number of nodes, thus effectively addressing N2 AI. Next, we concatenate (k)
(k) the enhancement embeddings their joint embeddings G. concat (uu GG (A))) Fi-
5

---

Under review as a conference paper at ICLR 2023
nally, we concatenate all the joint embeddings (k)
G, different layers obtain a multi-scale joint
(0) embedding as uG,GG, = concat((u GG,G,, G.
(3)
MLP regressor. A two-layer MLP is then applied to map uG,,G to the similarity scores. In the GED(G, graph similarity task, the normalization GED is defined as nGED(G), G2) (IN,+ and the ground truth similarity score is defined as exp(-nGED(G, G,)), which is in the range of (0,1). We adopt the Mean Square Error (MSE) as the loss function to train N AGim.
4.2 GRAPH SIMILARITY LEARNING WITH LANDMARKS (GSL²)
The graph similarity task inherently requires deep fusion of the features of two graphs the early stage and then learns from the joint embeddings to predict the similarity score, as shown in Fig This makes it difficult extract the individual embedding of each graph, which leads to higher com- putational costs in practice (Qin et al. 202Tp. Qin et al. (202T) used KD-paradigm to improve the individual embeddings generated by the student IEM. In contrast, we provide a novel IEM frame- work, called Graph Similarity Learning with Landmarks (GSL²), which directly generates the individual embeddings of each graph without additional learning.
Theorem Let landmarks& S denote an infinite set containing every graph, and ug is the embedding
of graph G, defined as: uG = [GED(G, ... ,.DDG.,,GG... Ginfinity)] where G, E S. The GED value between any G1 and G2 satisfies:
GED(G), G2) = min(uG, + uG..) min (GED(G), G.) &.),,
(3)
The proof of Theorem is provided in the Appendix [A] Theorem [ Iillustrates that the GED values between two graphs can be calculated by their GED values with landmarks. However, Theorem needs to satisfy two requirements, the first one is to obtain an infinite S and the second one is a large number of calculations of the exact GED values of the graphs and landmarks, both of which are impossible to satisfy in a practical scenario. The first requirement can be approximately solved by randomly selecting M graphs from the training graph set form S. For the second requirement, the approximate GED values between graphs and landmarks can be computed quickly using a graph adding noise to
similarity model, e.g., SimGNN, GraphSim, or AGiGm,, which is equivalent the generated üg. However, in practice, we find that the direct use of min; f + uGz,) } to approximate the GED target GED(G, G2) has relatively large error due to the limited number of landmarks and the noise in üg. Therefore, we propose to use MLP to learn to map the two generated embeddings to their GED target.
An illustration of our GSL is shown in Fig (b). and the details are as follows: First, a subset of the graphs. S (G,,-.., GmM) }. named landmarks, graph set. Second, any graph similarity model can be leveraged to efficiently obtain the individual embeddings for each graph by computing their GEDs to the landmarks. However, from the above analysis, we can see that reducing the noise in üg can improve the prediction accuracy. Therefore, performance, to calculate GED values
randomly selected from the the training
leverage our N AGim, which achieves the state-of-the for all graphs with landmarks. However, we found that directly converting exponential similarity values to GED values caused significant errors, so used the ATS² similarity metric retrain AGim, see the Appendix B for details. Third, we concatenate two individual graph embeddings together in a joint embedding and learn an MLP to map the joint embedding to their GED target.
4.3 COMPARISON OF OUR N AGIM AND GSL
Accuracy. N2 AGim can effectively address N Al by fusing the features of two graphs by DiffAtt at multiple scales, and thus can achieve better performance. However, GSL uses N2 AGim to quickly generate an individual embedding with noise for each graph and learn from the noisy embeddings, so the performance will be lower than that of N2 AGim.
Inference speed. Given g query graphs, the aim is to compute the similarity between all query graphs and the p graphs which already exist in the database. Assume the time to compute the similarity of pair of graphs is Ty for N2 AGim and the time to compute the similarity of pair of embeddings is TMLP for the MLP in GSL?. Since AGim, as an EFM, requires fusion of graph pairs obtain joint embeddings each layer, it has computational time of p q x TN-

---

Under review as a conference paper at ICLR 2023
AIDS 7OOnee
IMCOMuB
3.
2.5
24
0.6
Craphben
80505
Chaptdenn
0.5
0.4
1.
1.0
0.2
0.-
(A5 0/2/S1//975
3.500
1000 6.00/19 9.NSC ZEh, 0.51 [9.8 Dudi
Figure 5: Visualisation of MSE for different models on test data with similar number of nodes. We split the test graph pairs with no more than 37.5% difference in the number of nodes into 5 bins for validation. Note that on graphs with a small number of nodes like AIDS700nef and LINUX, a difference of 7.5% SizeDiff represents difference of approximately one node.
However, 2 as IEM, first generates the individual embedding of each graph using N2 AGim and then predicts the similarity between the two embeddings using MLP, requiring computation time of (p 10+00 g) x M x Ty + P x q x TMLP, where is the number of landmarks. Since GSL" reduces the time complexity of computing joint embeddings and the inference speed of MLPs is generally lower than that of N2 AGim, i.e., TMLP < Ty, the query tasks can be addressed more efficiently by GSL Especially in industrial scenarios, graph data is usually preprocessed offline as the embedding. If all the graph embeddings are stored offline, the inference time of GSL,² is just P x q x TMLP. In summary, as an IEM, GSL can be up TN/ LP times faster than N AGim. The experimental results in Section 5.3 also demonstrate that GSL² can be up to 47.7 times faster than N AGim, which shows that GSL can effectively address the similarity computation tasks.
EXPERIMENTS
In this section, we evaluate our proposals using the AIDS700nef, LINUX and IMDBMulti datasets provided by Bai et al. (2019) for the graph similarity learning and compare our method with other state-of-the- aht methods. The statistics and details of these datasets and data processing are pro- vided in Appendix B Note that all the experiments are performed on Linux server with Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz and 8 NVIDIA GeForce RTX 2080Ti. The evaluation met- rics we adopted are Mcan Square Error (MSE) (in the format of 10 )), Spearman's 's Rank Correlation Coefficient (p) and Precision at 10 (p@ 10). All metrics with their meanings are listed in the Ap- pendix. The AGim is evaluated using the PyTorch Geometric (Fey & Lenssen 2019]. We use Adam optimizer, a learning rate of 0.001, the batch size is set to 2000, and the hidden channel is set to 64. We run 200 epochs the three datasets, and after running 150 epochs, we perform validation at the end of every epoch. Ultimately, the parameter that results in the least validation loss is chosen to perform the evaluations on the test data. We implement the GSL22 using the PyTorch (Paszke) et al. 2019), and the details can be found in our source code.
5.1 ABLATION STUDY
We perform ablation studies to show the influence of the DiffAtt A and GSL2 with different GED computation algorithms. For N2 AGimm we compare the performance of using and without using DiffAtt across the four global pooling functions mentioned. Besides, we compare our DiffAtt with the other popular attention based global pooling methods, i.e., Neural Tensor Network (NTN) Bai et af. 2019), Embedding Fusion Network (EFN) (Qin et al., 2021), Global Soft Attention (GSA) (Li et al. 2015), Set2Set (Vinyals et al. 2015). Context Based Attention (CBA) (Bai et al., 2019, and Cross Context Based Attention (C2BA), under the same architecture. It is worth noting that most of the existing graph similarity models leverage the CBA to generate graph embeddings, e.g., Li et al. (2019); Bai et al. (2019): Qin et al. (202T); Zhang et al. (202I). which is defned as (X) En' sigmoid c) where denotes the context information of the graphs. C2BA is different from CBA only in that global context information c is from another graph in the graph pair. For our GSL?" we experiment with different graph similarity models. We also provide additional ablation experiments on the hyperparameter selection of our methods, including selecting different numbers of landmarks in GSL etc. in Appendix G
Table T demonstrates that our DiffAtt effectively improves 44 metrics out of 48 metrics of the four global pooling methods, especially giving huge boost 12 metries the IMDBMulti dataset,
7

---

Under review as a conference paper at ICLR 2023
Table I: Results of the ablation study on using or without using our DiffAtt. Bold means the best. The Average denotes the average value over the three datasets. The t denotes that the larger this indicator is, the better the performance, while the I indicates the opposite.
F
DifAAu
AIDS700nef
LINUX
IMDBMuli
Average
MSE
p
P@ f
MSE
P
P@10
MSE
p
P@10 f
MSE
P
P@ 10
GAP
x
3,004
0.819
0,486
0,457
0.987
0.970
0.753
0.866
0,878
1.405
0.891
0.778
GAP
3.042
0.810
0.511
0.256
0.990
0,979
0.404
0.907
0.890
1.234
0.902
0.793
GMP
3.051
0.817
0.501
0.396
0.988
0.970
0.386
0.871
0.875
1.278
0.892
0.782
GMP
2,839
0,827
0,538
0.440
0.987
0.985
0.305
0.920
0.896
1.195
0.911
0.806
SOP
3.039
0.811
0.496
0.261
0.991
0,973
0.776
0.892
0.863
1.359
0.898
0.777
SOP
1.144
0.918
0.663
0.066
0.993
0.998
0.309
0.915
0.903
0.506
0.942
0.855
GSP GSP
1.396
0.903
0.624
0.116
0.992
0.983
0.392
0.859
0.884
0.635
0.918
0.830
1.170
0.916
0.672
0,066
0.994
0,995
0.308
0.918
0.893
0.515
0.943
0.853
Table 2: Results of the ablation study of comparing our DiffAtt with other attention methods. Bold
means the best, and means the next best.
AIDS700nef
LINUX
IMDBMuli
Average #1
MSE
P@10 1
MSE 4
P1
P@ P
MSE +
Pt
P@
MSB 4
P@
NTN
2.456
0.845
0.554
0.139
0.9931
0.987
0.463
0.891
0.874
1.019
0.910
GBA
3.224
0.814
0.499
0.754
0.982
0.961
0.368
0.869
0.881
1,449
0.888
0,780
Se12Set
3.308
0.815
0,511
0.543
0.985
0.974
0.355
0.876
0.878
1.402
0.892
0.788
CBA
1.487
0.902
0.611
0.165
0.990
0.987
0.406
0.855
0.884
0.686
0.916
0.827
C2BA
1.269
0.911
0.662
0.094
0.993
0.995
0.439
0.887
0.875
0.601
0.930
0.844
EFN
1.249
0.912
0.6444
0.0781
0.993
0.990
0.315
0.902!
0.891
0.547)
0.936
0.842
DiffAut
1.170
0,916
0.672
0.066
0.994
0,995
0,308
0,918
0.893
0,515
0.943
0.853
such as 46.3%(0..40) vs 0.753), 21 (0.355 vs 0.386), 60.2% vs 0.776) and 21 21.4% (0.308 vs 0.392) on the four MSE metrics. This shows that DiffAtt has powerful generalization to effectively solve the N Al of all pooling methods. In terms of the average results, SOP and GSP showed better results than GMP and GAP after the use of DiffAut, which is the result of the smaller percentage of overlap area and greater distribution differences. Because of the higher performance and less computational cost of GSP, we finally chose it as the global pooling function in N2 AGim.
Compared to other attention mechanisms, in Table 2 DiffAut achieves the best results on all metrics under the same experimental setup and architecture, especially better than the EFN on average on three metrics 5.8%(0.515 vs 0,547), (0794 vs 0.936) and 1.38 vs 0.842), respectively. As can be seen from the Table 3 the accuracy of GSL2 increases as the generated GEDs are closen to the true GED values, which validates our analysis in Section 4.2 and shows that the performance of GSL.2 2 can be improved by using our NaAGim.
5.2
GRAPH SIMILARITY LEARNING
We compare our N AGim and GSL 2 with a number of sfate-of-the-art methods for graph similarity learning tasks: GMN
(Li et al. 2019) SimGNN (Bai et al. 2019). H2MN (Zhang et al.) 2021).
GraphSim (Bai et al. 2020), and EGSC (Qin et al.) 202 We note discrepancies in the MSE Bai reported by various papers. For examples, the MSE reported in Bai et al. (2019), Bai et al. (2020) and
Zhang et al. 2021) is
D Een(s 8)2. but Qin et al. 2022) reported MSE as [DT D= 8)2.
To provide a consistent comparison, we use the MSE metric of the latter formula, and the results are shown in T Our N2 AGim achieves the best performance in most of the cases. On AIDS700nef, the performance is improved by about 24.3%((. (1. 170 vs 1.546 on MSE). (0.96 vs 0.898 on p) and 305667 vs 0.649 on p 10) compared EGSCS, On LINUX, our 2 AGim achieves the
Table 3: Results of the ablation study of comparing different graph similarity models used in 2 All graph similarity models were trained using ATS² and we transform the results to the exponential similarity scores and report it. The brackets represent the GED algorithm used in GSL2 and the GT represents the ground truth GED values. M is set to 60, 30 and 70 on three datasets, respectively.
AIDS700ucf
LINUX
IMDBMulti
Average
MSR 1
P1
P@ 10
MSF L
et
P@10
MSF
p²
PG 10
MSF
e1
1@ t
SimGNN
3.151
0.827
0.397
0.752
0.983
3.722
0.934
0.826
2.542
0.915
0.715
GraphSim
1,824
0.889
0.562
0.283
0.991
0.979
1.053
0.94
0.771
N²
L.84
0.917
0.675
0,071
0.994
0.989
0.341
0.973
0.9
0.532
0.961
0.855
GSL (SimGNNN)
2.187
0.873
0,518
0.402
0.987
0.9751
0.668
0.949
0.852
1.086
0.936
0.782
(Grghhhm))
1.24
0.883
0.505
0.210
0.990
0.971
1.017
0.936
0.738
GSL (NN= AGimm)
1.470'
0.9051
0.604
0.0741
0.994
0.995
0.510
0.971
0.869
0.6851
0.957
0.822
GSL)(GT)
1.258
0.915
0.633
0.068
0.995
0.995
0.512!
0.985
0.850
0.613
0.965
0.826
8

---

Under review as a conference paper at ICLR 2023
Table Results of the graph similarity learning task. Bold means the best.
AIDS700nef
LINUX
IMDBMuli
Averuge
MSE
pt
P@101
MSE 1
pt
P@10
MSE
P
P@
MSE 4
pt
P@
GMN
3.772
0.751
0.401
2.054
0.933
0.833
8.844
0.725
0.604
4,890
0.803
0.613
SimGNN
2,378
0.843
0.421
3.018
0.939
0.942
2.528
0.878
0.759
2.641
0.887
0.707
GraphSim
1.574
0.874
0.534
0.116
0.981
0.992
1,486
0.926
0.828
1.059
0.927
0.785
H2MN
1,826
0.881
0.521
0,210
0.990
0.975
1.178
0.913
0.889
1.071
0.928
0.795
FGSCT
1.601
0.901
0.658
0.163
0.988
0.994
0.553
0.938
0.872
0.772
0.942
0.841
EGSCS
1,546
0.898
0.649
0,293
0.984
0.978
0,581
0.935
0.857
0,807
0.939
0.828
N AGim
1.170
0.916
0.672
0.066
0.994
0.995
0.308
0,918
0.893
0.515
0.943
0,853
GSL.2
1,470
0.905
0.604
0.074
0.994
0.995
0,510
0.971
0.869
0.685
0.957
0.822
Table 5: Results of inference time for each model. The suffix of '-R' means that the input is the raw query graph, while the suffix of "-F" means that the embeddings of the query graph are stored offline. All times reported below are in seconds.
SimGINN
N AGim
GraphSim
EGSCS-R
EGSCS-F
GSL.2R
GSL.2-
AIDS700nef 5.106
9.245
4.383
4.383
0.975
3.874
0.718
LINUX
8,582
13.163
9.120
9.120
1.414
5.007
1.159
IMDBMulti
122.939
87.032
114.676
87.032
2.256
15.792
1.824
best performance in all three metrics, especially in MSE which is 43.1% 0.116) better than the second best model, GraphSim. On IMDBMulti, N2 AGim achieves the best MSE and p@ 10 performance, but close not perform well p (0.918 vs 0.938) than EGSCT. Although GSL does not learn embeddings directly in the graph data, it achieves the state-of- ofate-of-the-art performance on three of the nine metrics on three datasets. Compared the EGSCS, our GSL achieved better performance in eight of the nine metrics on three datasets, demonstrating the powerful expressive ability of the generated embeddings in GSL Compared GSL which learns on embeddings with noise. N2 AGim achieves better performance. especially better by about 20.4%(1.170 vs 1.470), (0.96 vs 0.905) and 11.3 (0.67 vs 0.604) on AIDS700nef. In addition, we visualised the MSE in test data with similar number of nodes for different models in Fig Compared to the other models, No AGim shows a significant improvement on graph pairs with similar number of nodes, demonstrating its effectiveness in addressing NI
5.3 INFERENCE TIME
In this section, we provide a comparison of inference times for GSL and the rest of the graph similarity models on test data. Our evaluation reflects real-world graph queries: we treat the training graph set as the graphs that already exist in the database and can be preprocessed, and the test graph set the query graph. We calculate the similarity of query graph to all graphs in the database at once to obtain the total query time, and all times are averaged over five tests. The results are shown in Table 5 By obtaining individual embeddings of the graphs offline, GSL comes out to be 12.9. 11.3 and 47.7 times faster than A2im on the three datasets, respectively. Compared to EGSCS-F, GSL is 1.36, 1.22 and 1.24 times faster, respectively. This shows the potential of GSL 2 to efficiently compute graph similarity in realistic scenarios.
6 CONCLUSION
This paper addresses two issues in graph similarity tasks, one is the NaAI and the other is the issue of improving the speed of graph similarity model inference for downstream tasks. By analysing the performance of popular graph similarity models, we show that graph similarity models have diffi- culty distinguishing the embeddings of two graphs with similar number of nodes, because the global pooling function maps graphs with similar number of nodes to similar embedding distributions, reducing the separability between embeddings. Therefore, DiffAtt is proposed to enhance the dif- ference between two similar embeddings, thus the proposed AGim achieves the state-of-the- performance. To speed up the graph similarity computation, the GSL" is proposed. Instead of learn- ing embeddings in graph data, GSL generates individual embeddings directly by trained graph similarity model. Our analysis and experiments both demonstrate that such individual embeddings have a powerful expressive ability and can efficiently handle downstream tasks.

---

Under review as a conference paper at ICLR 2023
7 ETHICS STATEMENT
This work proposes two methods to address the real-time graph similarity tasks. Our proposed methods have great potential for practical graph-based applications due to their high precision and high speed. Our methods also be applied to address any similarity problem between the graph data, e.g., the binary function similarity problem, which can be helpful for the software copyright issue. Therefore, we believe that our methods do not have any negative impact of the society but make positive impact of the society.
REPRODUCIBILITY STATEMENT
Our code is publicly available on https///gthubb.omm////22111///// els and test code in anonymous repository to help researchers quickly reproduce test results. Besides, we provide the source code for the training, including the hyperparameter settings and the fixed random seed repository.
provide trained mod-
ensure work is reproducible. Please get more details from
REFERENCES
Moez Ali. PyCaret: An open source, low-code machine learning library in Python, April 2020.
URL https: http:::t/wwwww.....t /tts:///wwwwww/ http://yyaartt..///
org PyCaret version 1.0.0.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey Hinton. Layer normalization. arXiv preprint
arXiv:1607.066 0607006450, 2016.
Jiyang Bai and Peixiang Zhao. Tagsim: type-aware graph similarity learning and computation. Proceedings of the VLDB Endowment, 15(2):335-347, 2021.
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neu- ral network approach to fast graph similarity computation. Proceedings of the Twelfth ACM International Conference Web Search and Data Mining, pp. 384-392, 2019.
Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3219-3226, 2020.
Maria-Florina Balcan, Avrim Blum, and Nathan Srebro. theory of learning with similarity func- tions. Machine Learning, 72(1):89-111 2008.
Sébastien Bougleux, Luc Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Gaüzzre, and Mario Vento. A quadratic assignment formulation of the graph edit distance. arXiv preprint 1r21v:1512.07444, 2015.
Stefan Fankhauser, Kaspar Riesen, and Horst Bunke. Speeding up graph edit distance computation through fast bipartite matching. In International Workshop Graph-Based Baaph Representations in Pattern Recognition, pp. 102-111. Springer, 2011.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprini arXiv:1903.028
2019.
Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. A survey of graph edit distance. Pattern Analysis and applications, 13(1):113-129, 2010.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Maurice G Kendall. new measure of rank correlation. Biometrika, 30(1/2):81-93, 1938.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. arXiv preprint arXiv: 0wt....09..002.. 2016.
10

---

Under review as a conference paper at ICLR 2023
Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey graph kernels. Applied Network Science, 5(1), 2020. ISSN 23648228. doi: 10. 10.0/0//s1111 109-019-0115-3.
AA Leman and Boris Weisfeiler. A reduction of graph canonical form and an algebra arising during this reduction. Yauchhoo-Tecbnicheskkyy Informatsiya, 2(9):12-16, 1968.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:1511.05490 2015.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity of graph structured objects. In International conference on machine learning, pp. 3835-3845. PMLR, 2019.
Xiang Ling, Lingfei Wu, Saizhuo Wang. Tengfei Ma, Fangli Xu, Alex X Liu, Chumming Wu, and Shouling Ji. Multilevel graph matching networks for deep graph similarity learning. IEEE Trans- actions on Neural Networks and Learning Systems, 2021.
Michel Neuhaus, Kaspar Riesen, and Horst Bunke. Fast suboptimal algorithms for the computation of graph edit distance. In Joint IAPR International Workshops on Statistical Techniques in Pat- tern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pp. 163-172. Springer, 2006.
Seongmin Ok and South Korea. A Graph Similarity for Deep Learning. (NeurIPS), 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Can Qin, Handong Zhao, Lichen Wang, Huan Wang, Yulun Zhang, and Yun Fu. Slow learning and fast inference: Efficient graph similarity computation via knowledge distillation. Advances in Neural Information Processing Systems, 34, 2021.
Kaspar Riesen and Horst Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision computing. 27(7))950 1130009999,99 2009.
Charles Spearman. The proof and measurement of association between two things. 1961.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. stat, 1050:20, 2017.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. arXiv preprini arXiv: 1.e.: 115391, 2015.
Runzhong Wang, Tianqi Zhang, Tianshu Yu, Junchi Yan, and Xiaokang Yang. Combinatorial learn- ing of graph edit distance via dynamic embedding. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5241-5250, 2021.
Xiaoli Wang, Xiaofeng Ding, Anthony KH Tung, Shanshan Ying, and Hai Jin. An efficient graph indexing method. In 2012 IEEE 28th International Conference on Datu Engineering, pp. 210- 221. IEEE, 2012.
Zhengyang Wang and Shuiwang Ji. Second-order pooling for graph neural networks. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.00826. 2018.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Zhiping Zeng, Anthony KH Tung. Jianyong Wang Jianhua Feng, and Lizhu Zhou. Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment, 2(1):25-36 36, 2009.
Zhen Zhang, Jiajun Bu, Martin Ester, Zhao Li, Chengwei Yao, Zhi Yu, and Can Wang. H2mn: Graph similarity learning with hierarchical hypergraph matching networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 2274-2284, 2021.
11

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM 1.
Here, we provide proof of Theorem 1. The GED satisfies the triangle inequality, i.e., for any G1 G2 and Gg. there must exist:
GED G2) & GED(G1, G3) + GED(G2, Gz).
(4)
In particular, when G3 is isomorphic graph on the least-cost edit path between G1 and G2, there must exist:
GED G2) GED(G,, G3) GED( G3).
(5)
Thus, assume there exists infinite set S containing every graph, any graph can be encoded as infinitely long vector as:
Ug
IGED(G, GED(G, ,.DG),,,,,,,,(,,, (nffittt),
(6)
where G E S, so that for any two graphs Gi and G2, exists:
GED(G1,G.) = min(uc,, + +uG.))
B DATASETS AND PRE-PROCESSING
We perform an evaluation of our methods on AIDS700nef, LINUX and IMDBMuli datasets pro- vided by Bai et al. 2019). Following is brief overview of benchmark datasets:
1. AIDS700nef dataset contains 700 graphs from AIDS dataset which represent antivirus screen chemical compound, and all of them have 10 or less than 10 nodes.
2. LINUX dataset contains 1000 graphs selected from Wang et al. (2012). which represent Program Dependence Graph (PDG) generated by Linux kerne..
3. IMDBMulti dataset (annsedag Vishwanathan 2015) contains ego-networks of ac- tors/actresses, where nodes represent an actor/actress and edges indicate that these two actors/actress participated the same movie.
For AIDS700nef and LINUX datasets, Bai et al. (2019) compute the GED of every graph pair using algorithm named A and for IMDB datasets, the minimum of GED computed by three algorithms: Beam (Neuhaus et al.) 2006), Hungarian (Riesen & Bunke 2009) and VJ (Fankhauser let al.) [0011) is considered as the ground truth. In order to enhance the node features of the graph, we concatenate the one-hot encoding of the node degree into its features on these three datasets. GEDG,
Note that, the GED metric is first normalized as nGED 0.5-[G,,|11,T]> where |G,| represents the number of nodes in G, and then adopted function A(z) e transform to range (0.1). We randomly split datasets into 60%, 20%, 20% as training graph set Tr, validation graph set V, and testing graph set Te, respectively. We take the Cartesian product of Tr labeled with their similarity scores as the the training set. The validation set (testing set) is defined as the Cartesian product of Tr and V (Te) labeled with the ground truth. The training set is defined {(G, 8a,80, )GG Tr, G, E Tr), where 8G,GG G. denotes the similarity score of G, and Gy, and the validation dataset and the testing dataset is ((G,, Gy. SG..G, GG,, E Tr, Gy E V). (G,,, &G.,c, E Tr, Gj Te), respectively.
However, found in 2 that directly converting the exponential similarity scores predicted by the graph similarity models to GED values can cause significant errors. Therefore, we used new similarity score train the graph similarity models, called Adaptive Transform Similarity Scores (ATS?), and transform the results back to exponential similarity score for comparison with other models at test time. The ATS?
defined as:
ATS G2) - Ig(nGED G2) 1)/ (11g/maxx +
(8)
12

---

Under review as a conference paper at ICLR 2023
Table 6: Statistics of all the datasets used in experiments.
Datasets
Graphs
Avg nodes
Avg edges
Pairs of testing graphs
Node attr
AIDS700nef 700
8.9
17.6
58,800
LINUX
1000
7.58
13.87
120,000
X
IMDBMulti
1500
13
65.94
270,000
X
C EVALUATION METRICS
The evaluation metrics that we adopted are the Mean Square Error (MSE), the Spearman's Rank Correlation Coefficient (p) (Spearman 1961). and the Precision at 10 (P@ 10) (Bai et al. 2019). Moreover, wC provide the results the T (Kendall 1938) and P@20 metrics in the experiments in Appendix. The MSE metric accurately calculate the distance between the predition results from the model and the ground truth, and and evaluate the matching between the global ranking result of the prediction results and the ground truth, while P@k is the intersection of the top results of the prediction and the ground truth.
D AI
Here, we provide a more detailed description of the Na in the popular graph similarity models. We grouped the testing set by the number of nodes in the graph and counted the MSEs. We normalized the MSEs with Min-Max Normalization, and visualized the results in Figl6] It is clearly that the large MSE are all concentrated locations with similar number of nodes, which reflects the prevalence of AI.
E A2AG WITH SECOND ORDER POOLING
Given the feature map X at the kth layer, Second Order Pooling (SOP) is defined as:
(k) ((x( (x))))T (xx(1)
(9)
where (Kk)_ RCxC is fixed size matrix. For the SOP, define the DiffAtt as
((k) = !M! -1,²²
(k(()) Softmar2D(Di/ (00 (k)) (i)) G.G., (tt(k)) @ (H H (H (2)
(10)
Where (k) G.GG, R CxC is the joint embeddings, and (k) E CCC and bias RCCC two learnable parameter. If the UG is directly flattened into a vector for regression, it will result in larger amount of parameters for the model. Therefore, motivated by the Bai et al. (2020), we apply four convolution layers with residual connections to learn the ((k) G. and flatten the feature map vector G.GG, to reduce the parameters of the model. Finally, concatenate all the joint embeddings u. different layers to obtain a multi-scale joint embedding as uG.,G, concat(lu G.,,,.))
(k)
(k)
F JOINT EMBEDDING VISUALISATION WITH DIFFATT AND WITHOUT DIFFATT
We also visualised the joint embeddings generated with and without DiffAtt with each of the three datasets using T-SNE, as shown in Fig 7 is clearly that the joint embeddings generated with AtffAtt more separable than those without DiffAtt.
13

---

Under review as a conference paper at ICLR 2023
pruts.
giople
trapilars on robeet carasee
ovylar and ddber
Number
Number chrodeii
ECROS en OSSTWme extret
DOCES USJT Seseet
D0S3 conese
viei vit prutt.
munder ctradei hat goopi
iidie did do 20 Tariel
Figure 6: Heatmap of the normalized MSE for different graph similarity models with different number nodes.
14

---

Under review as a conference paper at ICLR 2023
Figure 7: t-SNE visualisation of the joint embeddings generated models using DiffAtt and those not using DiffAtt. The colours represent the similarity ground truth of the joint embeddings. clear that the joint embeddings with DiffAtt are more separable than those without DiffAtt, for example, the similarity scores of the joint embeddings along the arrows gradually increase, and the joint embeddings with high similarity are concentrated in the elliptical region.
Table 7: Results of MSE for different models on test data with small difference in the number of nodes on the AIDS700nef dataset.
SizeDiff
H2MN
EGSCS
GraphSim
NºAGim EGSCT
0.000, 0.075)
2.880
2.265
2,485
2.272
1.661
0.075, 0.150)
2.059
1.611
1.869
1.694
1.226
0.150, 0.225)
1,442
1.260
1.555
1,428
0.898
0.225, 0.300)
1.545
1.615
2.022
2.182
0.894
00.30,, 0.375)
0.916
0.901
0.917
1,443
0.573
G ADDITIONAL EXPERIMENTS AND RESULTS
Here we provide more ablation experiments about AGiGmm and GSL.2 in the same training frame- work as Section
G.1 RESULTS ON N2 AGIM'S EFFECTIVE IMPROVEMENT NºAI
The 5 visually demonstrates that N2 AGim achieves better performance than the other models when the number of nodes is similar, showing that 2 AGim address 22 effectively. Here we provide more detailed numerical comparison results Table 7 g and 9 Note that the graphs in AIDS700nef and LINUX all have relatively small number of nodes, and 7.5% difference in node number can be seen as a difference of one node. The results demonstrate that N2 AGim achieves better performance than the other models all levels SizeDiff. especially about 26.7 (6.6%% vs 2.265). 19.4%(0..1)) 191 vs 0.237) and 35.4%(1.1) 103 vs 1.707) better than the second better performance when the difference in number of nodes less than 7.5% on the three datasets, respectively. This strong evidence that AGAGim practically improves N AI.
G.2 MORE ABLATION EXPERIMENTS ON Nº AGIM
We experimented with different settings of the backbone of N AGim on the AIDS700nef dataset. First experimented with different types of GNNs and whether nections and FFNs to enhance node embeddings, and the results are shown in Table TO It is shown that all GNNs show a significant improvement with the enhancement, especially in the MSE met- rics about 33.37(1..7) vs 1.191), 2.5%(1.254 vs 1.223) and 12.0% vs 1.170). respectively.
residual
Table 8: Results of MSE for different models on data with small differences in the number of nodes on the LINUX dataset.
SizeDiff
H2MN
EGSCS
GraphSim
EGSCT
NaAGim
0.000, 0.075)
0.709
0.474
0.258
0.237
0.191
0.075, 0.150)
0.544
0.348
0.275
0,266
0.066
0.150, 0.225)
0.317
0.241
0.184
0.254
0.035
0.225, 0.300)
0.114
0.292
0.138
0.138
0.021
0.300, 0.375)
0.205
0.170
0.118
0.163
0.026
15

---

Under review as a conference paper at ICLR 2023
Table 9: Results of MSE for different models test data with small differences in the number of nodes on the IMDBMulti dataset.
SizeDiff
H2MN
EGSCS
GraphSim
EGSCT
N²AGim
0.000, 0.075)
1.737
1.707
2.397
1.748
1.103
0.075, 0.150)
0.900
0.887
1.889
0.861
0.552
0.150, 0.225)
0.630
0.603
1.478
0.628
0.421
0.225, 0.300)
0.609
0.547
1.040
0.537
0.431
0.300, 0.375)
0.296
0.205
2.603
0,202
0.152
Table 10: Experimental results on N AGim with different GNNs and whether to residual con- nections and FFNs on the AIDS700nef dataset.
GNN
Res&FFN
MSE L
P
T
P@
P@20
GCN
x
1.375
0.898
0.756
0.615
0.686
GCN V
1.191
0.912
0.778
0.668
0.738
SAGE
X
1.254
0.914
0.780
0.652
0.721
SAGE
V
1.223
0.911
0.778
0.680
0.726
GIN
X
1.330
0.904
0.766
0.614
0.697
GIN
V
1.170
0.916
0.783
0.672
0.736
Compared to other GNNs, GIN achieved better results in most cases, especially better on MSE about 1.8%(11.170 vs 1.191) and 4.3% vs 1 1.223), making it more suitable backbone for N2AGim. We further experimented with the performance GIN layers, which is shown in Table II and found that the number of layers had little effect performance, so we chose to use layers of GIN.
N AGim using different numbers of
G.3 EXPERIMENTAL RESULTS FOR DIFFERENT NUMBERS OF LANDMARKS GSL?.
We experimented with selecting different numbers of landmarks on the performance of GSL?, and the results shown in Table 12. 13 and [4 From the experimental results, we can find that increasing the value of M can improve the accuracy of GSL but it also increases the inference time. Considering the balance of inference speed and accuracy, we finally chose M 60, 30, and 70 for three datasets, respectively.
G.4 EXPERIMENTAL RESULTS FOR GSL WITH DIFFERENT RANDOM SELECTED LANDMARKS.
We next provide experimental results of GSL under different random seeds to test the sensi- tivity of 2 to the selected landmarks, which shown in Table 15 16 and 17 respectively. From these results, we can see that the selection of different landmarks affects the performance of GSL but the effect is significant, which shows the robustness of our GSL?
Table 11: Experimental results on AGAG with different number of GIN layers on the AIDS700nef dataset.
Layers
MSE 1
p
7
P@ 10 f
P@20 20
3
1.170
0.916
0.783
0.672
0.736
4
1.199
0.917
0.785
0.673
0.723
5
1.174
0.913
0.781
0.674
0.736
16

---

Under review as a conference paper at ICLR 2023
Table 12: Experimental results for different numbers of landmarks selected on the AIDS700nef dataset. M denotes the number of landmarks, Considering the balance of inference speed and accuracy, we finally chose M 60.
M
- (s)
GSL (8)
MSE
P@ 10
P@20 1
10
2.618
0.676
2.334
0.840
0.684
0.434
0.536
20
3.157
0.805
1.699
0.884
0.739
0.544
0.635
3.134
0.738
1.559
0.896
0.755
0.577
0.668
40
3.389
0.696
1.563
0.897
0.756
0.576
0.670
3.537
0.697
1.481
0.903
0.764
0.579
0.678
60
3.874
0.718
1.470
0.905
0.767
0.604
0.688
70
4.207
0.764
1.455
0.902
0.763
0.583
0.682
80
4.495
0.737
1.621
0.895
0.753
0.566
0.655
90
4.580
0.740
1.450
0.903
0.763
0,588
0,680
100
4.900
0.785
1.765
0.890
0.746
0.533
0.636
110
4.974
0.767
1.675
0.893
0.749
0.554
0.647
120
5.346
0.749
1.557
0.898
0.757
0.574
0.663
Table 13: Experimental results for different numbers of landmarks selected on the LINUX dataset. Considering the balance of inference speed and accuracy, finally chose M 30.
M
GSL.2-R (s)
GSL (s)
MSE +
P
P@ 10 1
P@ P@20- 1
10
4.254
1,015
0.696
0.981
0,920
0.944
0.939
20
4.283
1,035
0.382
0.987
0.944
0.975
0.951
30
5.007
1.159
0.074
0.994
0.964
0.995
0.991
40
5.235
1.132
0.080
0.994
0.967
0.990
0.988
50
5,467
1.052
0.084
0.994
0.967
0.990
0.993
60
5.753
1.017
0.081
0.994
0.967
0.991
0.993
70
6.018
1,040
0.088
0.993
0.960
0.987
0.989
80
6,634
1,039
0.209
0.991
0.957
0.973
0.960
6.763
0.970
0.077
0.994
0.964
0.989
0.989
100
7.703
1.115
0.130
0.993
0.962
0.982
0.976
110
7.752
1,111
0.212
0.990
0.947
0.974
0.960
120
8.268
1,111
0.087
0.994
0.966
0.993
0.994
G.5 EXPERIMENTAL RESULTS ON THE INFERENCE SPEED OF GSL BASED ON OTHER MODELS.
We provide inference speed of GSL based on the other graph similarity models and the results are shown in Table 18. It is clear that GSL.2-F speeds up SimGNN by 7.7, 8.5, 73 times on three datasets, respectively, and speeds up GraphSim 6.1, 10.2 and 59 times. respectively.
G.6 EXPERIMENTAL RESULTS ON GSL WITHOUT USING MLPs.
We provide experiments directly using min, (ūc, üG and the results are shown in Table I9 Obviously, due to the limited number of landmarks, and the noise in the generated ug. direct of min, (UG, úGG,) } is very ineffective.
G.7 EXPERIMENTAL RESULTS ON GSL WITH DIFFERENT REGRESSION ALGORITHIMS.
We provide experiments using different regression algorithms in GSL and the results are shown in the Tab 20 21 22 respectively. The experimental setup is the same in Section 5 and we use the default parameters Pycaret (Ali (020) to train each model. In practice, the parameters of the learning algorithm be adjusted to obtain better results. It can be seen that the decision tree based regression algorithms achieve good performance this noisy embeddings. This also illustrates the strong expressive ability of generated embeddings.
17

---

Under review as a conference paper at ICLR 2023
Table 14:
Experimental results for different numbers of landmarks selected the IMDBMulti
dataset. Considering the balance of inference speed and accuracy, we finally chose M as 70.
GSL (s)
GSL - (s)
MSE
P t
P@ 10 1
P@20 1
10
6.525
1,513
0.703
0.964
0.898
0.843
0.862
20
7.773
1.458
0.687
0.974
0.929
0.854
0.872
30
8.916
1,470
0,589
0.968
0,915
0.860
0,882
10.902
1.714
0.640
0.967
0.912
0.832
0.858
50
12.312
1,786
0.536
0.969
0.918
0.852
0.890
13.142
1,524
0,582
0.972
0,920
0.856
0,871
70
15.792
1.824
0.510
0.971
0.916
0.869
0.887
80
17.720
1.912
0.499
0.974
0.932
0.868
0,878
90
18.897
1.774
0.502
0.973
0,927
0.855
0,888
100
20.914
1,806
0,508
0.971
0,924
0.863
0,890
110
24.730
1,804
0.524
0.969
0.911
0.864
0.882
120
26.778
1.830
0.520
0.970
0.919
0.865
0.887
Table 15: Experimental results on GSL
using different random seeds the AIDS700nef dataset.
Seed
MSE
p
f
P@ 10 f
P@20 f
2
1.470
0,905
0.767
0.604
0,688
3
1.499
0.904
0.765
0.599
0.681
4
1.509
0.904
0.765
0.591
0.682
5
1.477
0.902
0.763
0.574
0.667
2233
1.577
0.896
0.755
0.568
0.665
std
0.042
0.004
0.005
0.016
0.010
H LIMITATIONS AND FUTURE WORKS
GSL represents each graph as the GED values between it and the landmarks, and learns on these embeddings. However, this restricted number of landmarks and the embeddings with noise limit the performance of 2SL Moreover, the different randomly chosen landmarks can have some impact on the performance of the GSL?, which requires better landmark selection strategy to be proposed. We leave these issues for the future works. Besides, this paper also discover the 2 AI, common problem in graph similarity learning, which could inspire the future works.
18

---

Under review as a conference paper at ICLR 2023
Table 16: Experimental results on GSL using different random seeds on the LINUX dataset.
Seed
MSE
P
rf
P@ 10 f
P@20 f
2
0.074
0,994
0.964
0.995
0.991
3
0.083
0,993
0.948
0.987
0,987
4
0.098
0.992
0,947
0.983
0.982
0.090
0.992
0.947
0.992
0.990
2233
0.084
0.993
0.948
0.984
0.991
std
0.009
0.001
0.008
0.005
0.004
Table 17: Experimental results GSL
using different random seeds on the IMDBMulti dataset.
Seed
MSE
p
T
P@ 10 f
P@ f
2
0,510
0,971
0.916
0.869
0.887
3
0.532
0.965
0.890
0.852
0.883
4
0.559
0.970
0.902
0.852
0.881
5
0.553
0.970
0.902
0.866
0.874
2233
0.562
0.968
0.898
0.863
0.881
std
0.022
0,002
0.009
0.008
0,005
Table 18: Experimental results on how faster GSL can improve other graph similarity models.
SimGNN
GraphSim
N2AGim
AIDS
LINUX
IMDB
AIDS
LINUX
IMDB
AIDS
LINUX
1MDB
Original
5.106
8.582
122.939
4.383
9.12
114.676
9.245
13.163
87.032
GSL
3,019
4.171
11.64
4.353
5.19
15.428
3.874
5.007
15.792
GSL
0.665
1.013
1.684
0.713
0.896
1.946
0.718
1.159
1.824
Table 19: Experimental results on direct use of min; (ūG, + uc
Datasets
MSE
P
T
P@ 10 f
P@20 f
AIDS700nef
13.283
0.683
0.527
0.246
0.299
LINUX
3.133
0.961
0.913
0.767
0.811
IMDBMulti
1.802
0.955
0.897
0.721
0.762
19

---

Under review as a conference paper at ICLR 2023
Table 20: Experimental results on GSL.2 using different regression algorithms the AIDS700nef dataset.
Model
MSE
p
T t
P@ 10
P@20 20 t
Extra Trees
1.705
0.888
0.751
0.541
0.637
CatBoost
1.645
0.890
0.746
0.559
0.656
Random Forest
1.963
0.874
0.729
0.475
0.583
KNeighbors
1.909
0.872
0.732
0.561
0.657
XGBoost
1,870
0.874
0.724
0.524
0,618
LightGBM
2.317
0.849
0.694
0.456
0.567
Gradient Boosting
3.305
0.796
0.635
0.291
0.434
Decision Tree
4.854
0.743
0.609
0.382
0.479
Bayesian Ridge
6.108
0,504
0.383
0.066
0.139
Linear Regression
6.108
0.504
0.384
0.072
0.138
Ridge
6.108
0.504
0.384
0.071
0.138
Orthogonal Matching Pursuit
6,291
0.490
0.371
0.059
0.124
Huber
6.218
0.501
0.382
0.071
0.135
ElasticNet
6,470
0.483
0.372
0.077
0.143
Passive Aggressive Regressor
6.603
0.477
0.367
0.076
0.133
Lasso
7.325
0.432
0.333
0.076
0,143
AdaBoost
8.754
0.383
0.304
0.314
0.347
LassoLars
10.776
0.226
0.186
0,466
0,490
MLPs
1.470
0.905
0.767
0.604
0.688
Table 21: Experimental results on GSL? using different regression algorithms on the LINUX dataset.
Model
MSE
p
T
P@ 10
P@20 1
Extra Trees
0.078
0.999
0.996
0.987
0.991
Random Forest
0.103
0.998
0.994
0.981
0.981
XGBoost
0.175
0.992
0.964
0.978
0.967
KNeighbors
0.141
0.998
0.995
0.986
0.984
CatBoost
0.148
0.993
0.960
0.964
0.977
Decision Tree
0.222
0.997
0.994
0.987
0.988
LightGBM
0.980
0.979
0.921
0.951
0.949
Gradient Boosting
4,450
0.944
0.847
0.743
0.819
AdaBoost
24.366
0.591
0.472
0.298
0.300
ElasticNet
28.596
0.365
0.288
0.090
0.145
Orthogonal
Matching Pursuit
30.056
0.319
0.265
0.045
0.045
Lasso
31.502
0.317
0.265
0.090
0.145
Huber
28.490
0.395
0.310
0.090
0.145
Bayesian Ridge
26.908
0.386
0.299
0.090
0.145
Ridge
26.908
0.388
0.305
0.090
0.145
Linear Regression
26.908
0.388
0.305
0.090
0.145
MLPs
0.074
0.994
0.964
0.995
0.991
20

---

Under review as a conference paper at ICLR 2023
Table 22: Experimental results GSL using different regression algorithms the IMDBMulti
dataset.
Model
MSE +
p
T T
P@ 10 1
P@20
Extra Trees
0.585
0.971
0.935
0.875
0.890
Random Forest
0.776
0.968
0.931
0.862
0.883
XGBoost
2.901
0.951
0,884
0.754
0.803
KNeighbors
0.837
0.961
0.924
0.876
0.899
LightGBM
13.573
0.925
0.837
0.728
0.758
Decision Tree
1.275
0.954
0.914
0.841
0.875
Gradient Boosting
48.646
0.825
0.700
0.206
0.320
Bayesian Ridge
75.886
0.333
0.250
0.015
0.034
Linear Regression
75,887
0.333
0.251
0.015
0.034
ElasticNet
75.690
0.330
0.252
0.013
0.033
Lasso
75.779
0.330
0.252
0.013
0.033
Ridge
75.959
0.336
0.254
0.015
0.036
Least Angle Regression
76.013
0.333
0.247
0.015
0.036
CatBoost
2.100
0.957
0.896
0.817
0,825
Huber
90.815
0.351
0.265
0,025
0.032
Orthogonal Matching Pursuit
174.995
0.236
0.178
0.022
0.045
MLPs
0.510
0.971
0.916
0.869
0.887
21


Reviews:
[{"review_id": "tnv5T9rIsa", "reviewer": "Reviewer_ngMc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to solve Node Number Awareness Issue (N2AI) and accelerate the inference speed in graph similarity learning.\nThey argue that existing graph learning methods tend to map graphs with similar number of nodes to similar embedding distributions, reducing the separability of their embeddings. They also use (GSL2) to accelerate similarity computation. They conduct extensive experiments to demonstrate their effectiveness.\n", "summary_of_the_review": "The logic of the paper is not clear, the focus is not highlighted, and it is difficult to understand their innovation points and contributions.\nPlease refer to \"weakness\" above.", "strength_and_weaknesses": "Strength:\n1. They found the existing graph similarity models have a relatively large error in predicting the actual similarity of two graphs with similar number of nodes, because of the global pooling function, which is interesting.\n2. They propose A novel GNN-based graph similarity model, named N2AGim.\n3. They propose the GSL2 to speed up the inference of graph similarity models.\n\nWeaknesses:\n1. The writing level of the paper needs to be improved, the expression is not organized, and there are problems with the writing structure. \n2. Lack of the survey for related work.\n3. Why we need to address to accelerate similarity computation by GSL2, and what is the connection of this strategy to N2AI issue?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "qqGD09sRO6", "reviewer": "Reviewer_2mHs", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the task of learning graph similarity, i.e.graph edit distance (GED)  with Graph Neural Networks. The authors propose 2 algorithms: a) N2AGim is an adaptation of the architecture proposed in (Qin et al 2021) where the attention layer is now not anymore obtaine via concatenation but through the differences of the embedding resulting in a higher attention when differences are higher; b) GSL2 leverages the first algorithm by computing approximate GED thanks to N2AGim for a set of so-called landmarks and using these values as an embedding of the graph.\nThe paper finishes with some experiments showing that this method gives better performances.", "summary_of_the_review": "The contribution is very weak compared to (Qin et al 2021) and should be better discussed.", "strength_and_weaknesses": "The motivation in the introduction is lost in the rest of the paper. The main claim in the introduction is that GNNs are not good for predicting GED when sizes of the input graphs are close but the empirical results do not show that the current algorithm is actually improving this situation.\n\nSimilarly, theoretical results about pooling in Section 3 are useless. Indeed, pooling is not discuss anymore in Section 4 describing the architectures used. In the experimental section (section 5), pooling is studied in the ablation study and there seem to be no clear conclusion. \n\nThe performances of GSL2 will depend on the landmarks chosen and in particular on the number M of landmarks. A discussion about the impact of M would have benn nice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "cSORokfeJ7O", "reviewer": "Reviewer_w3qo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This papertargets two issues in graph similarity computation including the node number awareness issue and the inference speed issue. The authors first analyze and show that the underlying reason of the first issue is the graph pooling. Then, the Different Attention is proposed to get the model aware of the node number. Finally, Graph Similarity Learning with Landmarks is proposed to address the second issue on the computation speed. Experiments are conducted on multiple datasets and compared with multiple baselines.", "summary_of_the_review": "Overall, this paper has a clear motivation and a reasonable solution. The experiments are overall acceptable. I would recommend acceptance,", "strength_and_weaknesses": "Strengths:\n\nThis paper has a clear motivation to address the two specific problems in graph similarity computation, therefore the main logic is easy to follow.\n\nTheoretical analysis is provided.\n\nThe experimental results are promising.\n\nThe paper is well formatted.\n\n\nWeakness:\n\n1. The inference time, which is one of the two main contributions of this paper, seems not improved significantly compared to the second best method EGSCS-F. Does this means that EGSCS-F is also a highly efficient method and does not suffer from the inference time issue?\n\n2. It is not clear whether the performance is brought about by better performance on the graphs with similar numbers of nodes. It would be better to show the performance of different methods on the graph pairs with similar number of nodes.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1qSUg3KB-C", "reviewer": "Reviewer_qS53", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work found that the existing graph similarity models have a relatively large error in predicting the actual similarity of two graphs with a similar number of nodes. This phenomenon is the so-called Node Number Awareness Issue (N^2AI). This problem is addressed by a novel GNN-based method, called N2AGIM. The authors also propose using GSL^2 to speed up the inference of graph similarity models. GSL^2 can take different graph similarity learning models as backbones, while it reaches the best performance with N^2AGIM. The experiments result demonstrates the superiority of the proposed methods.", "summary_of_the_review": "This paper proposes an interesting problem (N^2AI), which means graphs with a similar number of nodes would be mapped to similar embedding distribution. The author proposes N^2AGIM to solve the found problem. In addition, the author proposes GSL^2 to speed up graph similarity learning inference and it’s plug-and-play. The experiment results validate the effectiveness of the proposed methods.\n\nHowever, the motivation of some parts of the model design is unclear, and the experiment result is inconsistent with results reported in other papers.\n", "strength_and_weaknesses": "Strength\n- This paper proposes an interesting problem (N^2AI), which means graphs with a similar number of nodes would be mapped to similar embedding distribution.\n- The author proposes N^2AGIM to solve the found problem.\n- The author proposes GSL^2 to speed up graph similarity learning inference and it’s plug-and-play.\n- The experiment results validate the effectiveness of proposed methods.\n\nWeakness\n- The motivation of some parts of the model design is unclear, e.g., why using GIN can effectively address N^2AI as mentioned in section 4.1(Multi-scale GIN layers). Have you tried using other GNN backbones? / Why do you use three GIN layers in N^2AGIM? (It seems this should be a hyperparameter.) If that is the case, then a parameter analysis regarding this parameter can be conducted.\n- More detailed inference time comparison is encouraged to be added. For example, as a plug-and-play module. How fast can it improve on the top of graph similarity learning models, e.g., SimGNN and GraphSim?\n- The experiment result is my primary concern. It seems it is not consistent with the results reported in other papers. For example, in H2MN, they show their MSE is 0.913 for AIDS, and 0.105 for LINUX respectively. Nevertheless, in your work, you show that their results for these two datasets are respectively 1.826 and 0.21. Is there any difference between your experiment setting and their experiment setting?\n- It is suggested that annotations errors and typos should be eliminated in the work. In section 3, $F_i$ and $\\mathcal F_i$ are both used for the pooling method. In addition, X and $X$ are both used for representing feature matrix. In Theorem 1, $i$ is used to denote which graph for $G_i \\in S$, while it is also used to denote $u_{G_{1i} $ (which is unclear what i means here).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject