Slow Learning and Fast Inference: Efficient Graph Similarity Computation via Knowledge Distillation
Authors: Can Qin
Handong Zhao
Lichen Wang
Huan Wang
Yulun Zhang
Yun Fu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Similarity Computation
Efficient Model
Knowledge Distillation

Abstract: Graph Similarity Computation (GSC) is essential to wide-ranging graph applications such as retrieval, plagiarism/anomaly detection, etc. The exact computation of graph similarity, e.g., Graph Edit Distance (GED), is an NP-hard problem that cannot be exactly solved within an adequate time given large graphs. Thanks to the strong representation power of graph neural network (GNN), a variety of GNN-based inexact methods emerged. To capture the subtle difference across graphs, the key success is designing the dense interaction with features fusion at the early stage, which, however, is a trade-off between speed and accuracy. For slow learning of graph similarity, this paper proposes a novel early-fusion approach by designing a co-attention-based feature fusion network on multilevel GNN features. To further improve the speed without much accuracy drop, we introduce an efficient GSC solution by distilling the knowledge from the slow early-fusion model to the student one for fast inference. Such a student model also enables the offline collection of individual graph embeddings, speeding up the inference time in orders. To address the instability through knowledge transfer, we decompose the dynamic joint embedding into the static pseudo individual ones for precise teacher-student alignment. The experimental analysis on the real-world datasets demonstrates the superiority of our approach over the state-of-the-art methods on both accuracy and efficiency. Particularly, we speed up the prior art by more than 10x on the benchmark AIDS data.

Slow Learning and Fast Inference: Efficient Graph Similarity Computation via Knowledge Distillation
Can Qin Handong Zhao Lichen Wang' Huan Wang' Yulun Zhang'
Yun Fu
'Department of Electrical and Computer Engineering, Northeastern University KKoorry College of Computer Science, Northeastern University
Adobe Research
Abstract
Graph Similarity Computation (GSC) is essential to wide-ranging graph appli- cations such retrieval, plagiarism/anommll detection, etc. The exact computation of graph similarity, e.g., Graph Edit Distance (GED). is an NP-hard problem that cannot be exactly solved within an adequate time given large graphs. Thanks to the strong representation power of graph neural network (GNN), variety of GNN-based inexact methods emerged. To capture the subtle difference across graphs, the key success is designing the dense interaction with features fusion at the early stage, which, however, trade-off between speed and accuracy. For Slow Learning of graph similarity, this paper proposes a novel early- early-fusion approach by designing a co-attention-bant based feature fusion network on multilevel GNN features. To further improve the speed without much accuracy drop, we introduce an efficient GSC solution by distilling the knowledge from the slow early-fusion model the student one for Fast Inference. Such student model also enables the offline collection of individual graph embeddings, speeding up the inference time orders. To address the instability through knowledge transfer, we decompose the dynamic joint embedding into the static pseudo individual ones for precise teacher-studee alignment. The experimental analysis the real- real-world datasets demonstrates the superiority of our approach over the state-of-the- art methods on both accuracy and efficiency. Particularly, we speed up the prior art by more than 10x on the benchmark AIDS data.
Introduction
Measuring the similarity across graphs, i.c., Graph Similarity Computation (GSC), is one of the core problems of graph data mining, centered around by multiple downstream tasks such graph retrieval [1, 2], aeggiarism/anomall detection [22, 41], graph clustering [39], etc. As shown Fig. 1, the graph similarity can be defined distances between graphs, such Graph Edit Distance (GED). The conventional solutions towards GSC are the exact computation of these graph distances, which, however, is NP-hard problem. Therefore, such exact solutions are less favorable when handling large-scale graphs due to the expensive computation cost. Computational time, especially run time in inference stage, is particularly important in industrial scenarios. As motivating example, in graph-structured molecules or chemical compounds query for in-silico drug screening, fast identifying similar compounds in a large database a key process [25].
Leveraging the strong representational power of graph neural network (GNN) [21, 13, 43, 42], the GNN-based approximate GSC solutions have gained increasing popularity. To adapt GNNs to the GSC task, the target similarity score (e.g., GED) is normalized into the range of (0, 1]. In this way, the
"Corresponiing Author: qin. wwwnortheasteetteo edu
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Add
Cut
Source Graph
Graph Editing Process GED =
Target Graph
Figure I:
Illustration of graph edit distance (GED), which is defined as the number of edit operations in the optimal path to transform the source graph to the target graph.
GSC can be regarded as a single-value regression problem that outputs a similarity score given two graphs as inputs. A standard design can be summarized a twin of GNNs bridged by co-attention with Multi-layer Perceptron (MLP) stacked as the regression head. Such approaches can be trained in fully supervised way using the Mean Square Error (MSE) loss computed over the ground truth similarity score. Many GNN-based GSC methods [1, 2, 22] followed such strategy, which, however, suffers from the fusion issue.
The paper presents a novel solution to both effectively and efficiently address the task of approximate GSC. Compared to the commonly used graph convolutional network the backbone [1, 2]. this paper adopts more robust network, i.e., Graph Isomorphism Network (GIN) [43]. Cross-graph fusion is essential to the model. The multi-scale features within different GIN layers are fused with new design. We have adopted an attention layer stacked over the concatenated cross-graph features for smooth feature fusion. To this end, similar features will be assigned with more weights contribute to the desired task. Moreover, to make the model easier to deploy, we take an MLP for feature learning which simple but effective to achieve cutting-edee -edge performance.
Intuitively, speed and accuracy can be considered as a trade-off. GSC naturally requires dense con- nections//nteractions between the two input graphs, which will consequently cause increasing compu- tations as the cost. This paper focuses on the effi- ciency of inference speed which can be addressed by either model compression or a faster data load- ing pipeline. Especially in industrial scenarios, the raw graph data are usually pre- rre-processdd as the em- beddings off-line that can be easily applied to the real-time downstream tasks, e.g., molecular graph retrieval. However, as shown in Fig. 2, most of the po-attenniion-base GSC solutions employ feature fusion in the early stage, which only outputs the joint embedding of pairing graphs. Inspired by [26]. we propose a lightweight model that removes all the early feature fusion modules in the encoder for efficient GSC. In this way, shown in Fig. 2, the individual embedding of each graph can be collected by a Siamese GNN. Such pairing graph embeddings will be fused with an attention layer to predict the final similarity score.
Earty-fusion
Individual Model
Individual Model
Knowledge Distillation
Figure 2: Illustration of knowledge distillation to achieve a fast model (right side) given barl slow model (left side).
To overcome the accuracy drop of such small network, we take a novel paradigm of Knowledge Distillation (KD) specifically designed for our task. As shown in Fig. 3, we propose an early-feature siamese network without
fusion network regarded as the teacher model, and the student model co-attention. It is found that the direct distillation of joint embeddings fails to work where the KD loss disturbs largely during training. of the teacher model and use them for KD by minimizing their relational distances [29]. To ensure pseudo individual embeddings fully cover the information of raw graphs, we further apply an MSE loss on the reconstructed joint embeddings concatenated from pscudo individual ones. We have verified that there is only a marginal accuracy drop compared with the original joint embeddings, which justifies the claim above. To sum up, our contributions can be summarized in three folds:
solve this, we generate the pseudo individual embeddings
We introduce new early-feature fusion model to achieve the competitive accuracy by designing a strong co-attention network and taking the GIN as the backbone.
For efficient inference and lif- embedding collection, we propose a novel Knowledge Distillation method for GSC where the joint embeddings are decomposed to distill.

---

Extensive experiments on the popular GED benchmarks demonstrate the superiority of our model over the state-of-the-art GSC methods on both accuracy and efficiency. Compared with the co-attention models, there is a more than 10 times faster in inference speed compared with the best competitor on AIDS dataset."
2 Related Works
2.1 Graph Similarity Computation (GSC)
Graph similarity computation measures the similarity of two given graphs, where similarity metrics can be defined as Graph Edit-Distance [6]. Graph Isomorphism [8], and Maximum Common Subgraph [7]. Exact computation of these metrics is generally an NP-complete problem [48]. To speed up the computation, kernel-based methods have been extensively proposed to approximate the exact solvers [44, 3, 28, 45]. Recently, inspired by the strong representation power of deep neural network, number of neural network based methods have been proposed and demonstrated a huge success [47, 1, 2, 24, 22, 41, 40J. Among them, regression- to the competitive performance in both efficiency and efficacy [1, 22, 2]. The intuition here is to learn an embedding vector using a graph neural network (GNN), and then measure the similarity of graph embeddings. While such graph-level embedding encoded by GNN alone is not sufficient to well distinguish the nuances of subgraph level structures. To integrate subgraph information for final similarity computation, several methods proposed recently, such as node-level pairwise comparison [1], cross-graph attention- based matching [22], multi-scale neighbor aggregation [2], etc. Despite the superior efficacy reported under various metrics (such Accuracy, Mean Squared Error (mse), Spearman's s Rank Correlation Coefficient), the complex subgraph matching/fusion components (termed early-fusionn' in Fig. 2) in different layers dramatically slow down the similarity measure. Moreover, early-fusion prevents pre-computing the embeddings for all candidate graphs for further reducing inference time in the graph retrieval scenario. Motivated by this, we propose a slow learning and fast inference method by leveraging the knowledge distillation idea to transfer the fine-grained but slowly learned early-fusion teach model to the fast-inference student model.
similarity learning has a great promise due
2.2 Knowledge Distillation (KD)
Knowledge distillation is general neural network training method, where (typically pretrained) teacher network is introduced to guide the learning of student network. Its idea was first pioneered by Bucilua et al. [5] to compress large machine learning models, where they proposed to transfer the knowledge of a model ensemble into a neural network by labeling unlabeled data as transfer set. This idea was later refined by Hinton et al. [16]. where they adopted softened probabilities of the teacher as a target for the student to learn and coined the term "knowledge distillation". Ever since, many methods have been proposed revolving around the central question in KD: "what is the definition of knowledge to be distilled". Popular definitions include feature distance [34], feature map attention [46], feature distribution [30], activation boundary [15], inter-sample distance structure [29, 32, 23, 36), and mutual information [35]. See [38, 11] for a more comprehensive survey. [26] is proposed distill separate models from a co-attention one. Despite the progress, they mainly focus on convolutional neural networks for vision tasks (mainly image recognition) or
recurrent neural networks for sequential data tasks (e.g., for natural language understanding [19)).
3
Approach
This section will introduce 1) the architecture of the carly-fusion network (i.c., teacher model); 2) the KD process and its interpretation. Before that, we start from the formalized problem definition.
3.1 Problem Formulation
Formally, a graph 9 is defined upon the node set and edge set as g (V, In specific, the edge linking pair of nodes including V and v E V can be denoted as the (u, v) E E. In our setting, all the accessible graphs are undirected, i.e., (w,v) E <> (v, u) E E. The quantity of nodes is represented as N [V] A convenient way to represent the graphs is the adjacency matrix
'The code is uploaded on https: /ttpps://gtthbb com hatmm//annnnn000/fffaam ctcerfiiieet__rrahhhheee Graph_Similarte Similarity. Computation
3

---

Gaph
Gojh
Enivedinn
have
Fabie
Torget
Goaph Conv
Graph Cone
Graph Cone
Figure 3: Overview early-feature fusion network (Teacher Net) which composed of a feature encoder and regression head as the whole. Within the the feature encoder, there are multiple components including GIN as the backbone, the Embedding Fusion Network (EFN) and graph pooling. The regression head is MLP which projects the joint embedding into the desired similarity.
A E | We denote the presence of edges as A [u, v) 1 if (u, v) E & and A [u, v] = 0 otherwise. Mostly, graph attributes (e.g., node labels) are available. Such node-level features be denoted real-value matrix X E | with the dimension and the order of feature matrix X is consistent with the adjacency matrix [12].
In GSC task, we have the access to pairing graphs 9; and 9j E DD where D = (Gu. G1..... is the graph set. The similarity of such two graphs can be represented as Graph Edit Distance (GED) or Maximum Common Subgraph (MCS). As shown in Fig. 1, the GED is defined as the number of edit operations in the optimal trajectory to transform the source graph to the target. The MCS is the maximum subgraph common to both two graphs. To well fit GNN, the standard GED value is normalized as G,,( the nGED, i.e., nGE 9,) = (|Gi (/G/++100 +[aa))/2 In the following, nGED should be transformed the value ranging (0, 1] as the ground truth similarity score 8ij- i.e., 8tj = (Dnn-GGGGGG E S, where S E R P x [D] indicates the similarity matrix among all the graphs [2].
3.2 Early-fusion Network (Teacher Model)
As discussed above, the key success of GSC enrich the interaction between the pairs of graphs through feature extraction. Therefore, our teacher model follows the conventional approaches [1. 2. 22] that fuse the cross- grass features in the early stage. The architecture of our proposed early-fusion (teacher) model is shown in Fig. 3. Specifically, we take the Graph Isomorphism Network (GIN) [43] as the backbone model for abstract feature extraction. The multi-level features are encoded within different convolution layers. For smooth fusion, we take an attention layer to enrich the representation ability of the embeddings and take an MLP for further feature learning. More details are given below.
3.2.1 Graph Isomorphism Network (GIN)
The isomorphism on graphs, i.c., G; ~ Gj is defined as bijection between G. and Gj: f V(G.) VG,)). Graph isomorphism is highly related to GSC where the graphs isomorphism also represents that the GED is O: Gi 9j GFD 9j) O. Therefore, the strong power of GIN in representing the graph isomorphism will be beneficial to GSC. GNN involves multiple learning steps, including message passing, node feature updating, and readout. Let A 9 -> h IR' denote general GNN. The iterative updating of node features from the (k- 1)-th to the k-th layer can be formulated as:
(k- S{ (k-1) u u. : )()))))) Φ (1(
(1)
where N(v) is the set of neighbouring nodes of node and its embedding at layer is is denoted as (/( o and f represent the different mapping functions. GIN, it has been discussed that the MLP can model the f and o very well due to the universal approximation theory [18, 17]. Therefore, the composition of (k-11 o (b()) is replaced by an MLP. The node embedding of GIN is updated as:
f
(k) ML.((k) ((1 (0)) 1 (k-1) + Σ [k M
(2)
WEN(v)

---

where e(*) can be either learnable or fix parameter. To readout the graph's global embedding, multiple order-invariant mapping functions. such as 'mean', 'max' or 'sum', are useful for information aggregation. In GIN, it has been verified that 'sum' is the most powerful one to learn and model all the labels without the constraints of node quantities. Therefore, GIN takes the 'sum' as the aggregator:
hg CONCAT ((sum) 11 E -...,k
where the features in all the layers, i.c., from layer 0 to layer K, are concatenated as the global feature. In this paper, we take K as 2 where there are 3 GIN layers in total for feature learning.
3.2.2 Embedding Fusion Network (EFN)
Feature fusion across graphs is crucial for GSC. In this paper, we have proposed novel Embedding Fusion Network (EFN) as part of the whole framework to address such a challenge. The inputs fed into EFN are graph-level embeddings, similar to [1]. In specific, given the node-level feature Immh representing the embedding of node we firstly obtain the global context E R as c tanh( W W )r,,, where W R Im is learnable matrix. Then, there is a node-wise attention to be aware of the similarity between node and global context: h = Σn=1 a cr,,,,,, where (-)) is the sigmoid function and h E R is the graph-level embedding. c)
X E V where the n-th row,
The concatenated feature of graph and j is denoted as haj = CONCAT h2) E R Since features h42 by come from different graphs, it is necessary to weigh the importance of each for the selection of useful ones. The attention mechanism can help to explore the element-wise dependence among the features of two graphs for concatenating them smoothly in the feature space. Therefore, we apply an attention layer on the concatenated feature hej to accomplish this goal as:
(WW()()))))))))) hig + h(g):
where hi E IR is regarded as the joint embedding of graph i and graph j. and (p))) and 6(-) denote the sigmoid gating and ReLU function respectively. WD D is the weight set of a NN layer, which acts as downscaling with reduction ratio assigned 4. After ReLU activation, the low-dimension signal is then increased to hi with the ratio r by a upscaling layer, whose weight set is denoted as Wo.
As shown in Fig. 3, there is an additional EFN between the feature encoder and regression head. Such EFN is applied to fusing the multi-level joint embeddings across pairing graphs. Following the similar strategy, we firstly achieve the concatenated multi-level features haji = CONCAT (1) hij A E
(2)
3dd. Then, an EFN is applied take the concatenated embedding holf for multi-level feature fusion as Eq. (4): hi = (h E RR where assigned as 16.
The whole carly-fusion network consists of two components: the encoder net and the regression net parameterized by Og and OR. As shown in Fig. the GIN and EFNs stated above can be summarized as an encoder net as hi, = E(G. gj. Og). Then, an MLP-based regression net is attached to project the joint embedding hi into the desired similarity score Siy optimized by the MSE loss as:
Greg =
Σ IJED
(R(E(S,, Og, -85) 815);
(5)
D
where R(-) denotes the regression network and D represents the set of all the training graphs.
3.3 Efficient Graph Similarity Computation
Although the proposed early-fusion network can achieve the competitive results with a similar time cost as previous co-attention-bete based methods [1, 2. 22], there are two crucial limitations on the efficiency of such methods: 1) the individual graph embeddings are unable to collect; 2) there is still room improve inference speed. In the paper, we have further taken the Knowledge Distillation (KD) and linear regularization for embedding decomposition to address such two challenges.
3.3.1 Embedding Decomposition
To decompose the joint embedding hi into the separate individual embeddings hg and h a necessary step for KD. The primary reason for embedding decomposition is that we hope to achieve
5

---

Teacher Network
Student Network
Outline of Embedding Decomposition
Teether
Staket
Share
Share
Vecii
Mosk!
A, B
A, B
16
Biar
big
A
a,
A,
KP
A,
A,
B,8
R
R
OOD
R
A,
Figure 4: Illustration of embedding decomposition and KD process between the teacher and student models. The pseudo individual embeddings, which applied for KD, are collected as the linear subtraction between joint embedding and duplicate graph embedding. More details are in Sec. 3.3.
the individual embeddings for offline storage. The other reason involves the stability of the knowledge transfer. We found that distilling the joint embeddings between the teacher and student models failed to work. More details about this point will be provided in the ablation study of Sec. 4.3. Such phenomenon indicates the necessity to separate the individual ones from the joint embedding. Then, the individual features will be aligned between the teacher and student models through the KD loss.
The detail of the proposed linear embedding decomposition shown in Fig. The basic assumption of this design is that the joint embedding might be represented as the linear combination of individual embeddings the high-dimensional feature space. Specifically, given graph A and graph B, the E Gn). Moreover, we also have access to a = E(G A. 9A) and bi = E(GB, B, (B) given duplicate inputs. Under the assumption of linear combination, the pseudo individual graph embedding will be computed as has h has where he is supposed to cover all the knowledge of graph B and parts of graph A. And the pseudo individual graph embedding of graph A is collected in the same way: hº hA hBgg To ensure the consistence with the desired task, we later concatenate the pairs pseudo individual graph embeddings as h AaBs CONCAT( Av) that redundantly covers the knowledge of joint embedding h" hABB- Another MLP-based regression network R' is applied to project it into the desired target score It' l2'( Aa O'R)) IR optimized by the MSE loss Eq. ( (4):
joint embedding can be easily achieved as h
Creg
Σ IJD
R' (Rhh - he - h4.1 Rr) 81))
2
(6)
DDI
where hisj ElG,, Gj. Oz), hi;; EGG Gi, θz), hj. = ElGj, Gj, Oz) and [ represents the operator of two features concatenation. More details and the verification of the proposed linear embedding decomposition provided in the ablation study of Sec. 4.3.
3.3.2 Knowledge Distillation (KD)
To get a fast model from a slow one, there are multiple compression solutions such as pruning, quantitation, etc. This paper adopts more practical and effective method to handle this issue by using
the knowledge distillation [26, 16). As shown in Fig. 4, with the linear embedding decomposition of the joint feature hT A could obtain pseudo individual embeddings he and hT of the teacher model. For the student model, take siamese GIN the feature encoder, i.c., h GIN O%) and h GIN O Then, the next step is to fuse the individual embeddings to achieve the joint embedding as h I(h5, h. O where I(-) is standard EFN. The pseudo individual embeddings, i.c., h and h is computed following the same strategy of the teacher network.
To enforce the student model inherit the teacher model's knowledge, it is necessary to minimize the discrepancy of the pseudo individual features. Here we apply both the first order and second order distance [26] for distillation. Therefore, the knowledge distillation (KD) loss is formulated
LKD(GA.9H) = T h ll. + IlATA h |1) + - a.)a TT & ( S h)))),
where yn (h4, by) )= = || - hy 11, is distance-wise potential function measuring the first order distance in the same domain, and (s is the Huber loss [26]. The second order distance is used to maintain the

---

Table 1: Quantitative GED results of baselines and method AIDS, LINUX, IMDB and ALKANE.
AIDS
LINUX
Methods
MSE 4
p@ 10
p@20
MSE +
T
p@
p@20 f
Beam
12.09
0.609
0.463
0,481
0,493
9.268
0.827
0.714
0.973
0.924
Hungarian
25.30
0.510
0.378
0.360
0.392
29.81
0.638
0.517
0.913
0.836
VJ
29.16
0.517
0.383
0.310
0.345
63.86
0.581
0,450
0.287
0.251
GENN-A#
0,635
0.959
0.871
0.324
0.991
0.962
SimGNN
1.189
0.843
0.690
0.421
0,514
1,509
0.939
0.830
0.942
0.933
E-SimGNN
2.096
0.869
0.699
0.534
0.641
0,469
0.982
0.892
0.971
0.968
GMN
1.886
0.751
0.401
1,027
0.933
0.833
GraphSim
0.787
0.874
0.534
0.058
0.981
0.992
FGSCCT
T.60T
0.901
0.7.9
0.658
0.729
0.163
0.988
0.908
0.994
0.998
EGSC-S
1,546
0.898
0.736
0.649
0.724
0.293
0.984
0.898
0.978
0.983
IMDB
ALKANE
Methods
MSE 4
p
p@ f
p@
MSE 4
pt
r f
p@ 10
p@20 f
SiMGNN
1.264
0.878
0.770
0.759
0.777
2,446
0.859
0.686
0.87
0.782
E-SimGNN
1.148
0.864
0.75
0.806
0.807
1.622
0.886
0.722
0.982
0.955
GMN
4.422
0.725
0.604
GraphSim
0.743
0.926
0.828
EGSC-T
0.553
0.938
0.829
0.872
0.878
0.533
0.930
0.787
0.998
0.991
EGSC-S
0.581
0.935
0.826
0.857
0.869
1.198
0.899
0.741
0.993
0.978
relational information. is a trade-off parameter assigned as 0.5. On the top of the KD layer. an MLP-based regression network will be attached over the joint embedding h Apart from the KD loss, there is supervision (i.e., MSE) loss Cyeg the student model fulfill the object of the task.
4 Experiments
Although our proposed approach can be generalized different graph distances, we pick the Graph Edit Distance (GED) as the evaluation task, which follows the standard protocol [1].
4.1 Setup
We deploy the GIN [43] as the backbone of the encoder network. The regression network is two-layer MLP with randomly initialed weights. Our proposed method includes two versions: 1) the teacher network and the 2) student network which are denoted as EGSC-T and EGSC-S, respectively. To optimize the proposed model, we take the Adam [20] as the optimizer based PyTorch Geometric (PyG) [31, 10J. The learning rate assigned as 0.001 with weight decay 0.0005. The batch size is 128, and the model will be trained over 6, 000 epochs. Our implementation depends PyG-bau ba-dde re- re-implementations of SimGNN and Sitended-SimGM.) $ All experiments are run on the machine with Intel 17-5930K CPU@3.50GHz with 64GB memory.
4.1.1 Benchmarks
Our proposed method has been evaluated over four popular datasets: AIDS, LINUX, IMDB and ALKANE. We have used the standard dataloader, i.e., 'GEDDataset', directly provided in the PyG 1
AIDS (i.e., AIDS700nef) composed of 700 chemical compound graphs which is split into 560/140 for training and test. Each graph has 10 or less nodes assigned with 29 types of labels.
LINUX dataset consists of program dependence graphs generated from the Linux kernel. Each graph represents a function, where a node represents a statement and an edge means the dependency. There are 1000 graphs in total with equal or less than 10 nodes each. The nodes have no labels.
IMDB dataset (i.e., "IMDB-MULTT") has 1,500 unlabeled graphs representing ego-networks of movie actors/actresses. There will be edge if the two actors/actresses show in the same movie.
SimGNN
/nttps://pytorch- http://pwtorccogggettr.i..ccc wew.eerr........eeeeeee.........
aatasets/ged_dataee attlaeeaattmmmmmmttttttttt..
7

---

Table 2: Ablation study results the AIDS and IMDB datasets, KD represents the knowledge distillation.
AIDS
IMDB
Methods
KD
MSE
PT
T1
p@
p@20
MSE
P.
7
p@101
p@20 1
w/o Attn
X
1.762
0.899
0.737
0.651
0.724
0.752
0.933
0.823
0,856
0.868
w/o GIN
X
2.158
0.863
0.691
0.535
0.637
0.594
0.926
0.803
0.862
0,866
Single Level
X
1.824
0.875
0.706
0.576
0.658
0.690
0.930
0.815
0.850
0.865
Student
X
1.770
0.882
0.717
0.601
0.683
0,763
0.928
0.813
0,829
0,851
Teacher
X
1601
0.901
0.739
0.658
0.729
0.553
0.938
0.829
0.872
0.878
Joint Feat
2.258
0.874
0.703
0.588
0.679
1.032
0.872
0.761
0.814
0.829
1st Order
1.604
0.894
0.731
0.614
0.715
0.548
0,934
0.824
0.856
0.865
2nd Order
1.647
0.893
0.731
0.631
0.715
0.692
0.929
0.814
0.847
0.866
w/o Crep
1.711
0.890
0.726
0.612
0.710
0.694
0.926
0.811
0.842
0,860
Student
1.546
0.736
0.649
0.857
0.869
Table 3: Inference time to solve GED computation on AIDS. Student-R means the student model with raw input graphs. Student-F denotes that the embeddings are stored offline, which can be online loaded for inference.
Model GENN-A*
SimGNN
E-SimGNN
E-SimGNN-F
Teacher
Student-R
Student-F
Time
290.1h
11.139s
9.672s
3.464s
11.139s
10.149s
0.148s
ALKANE [4] is purely structural dataset containing 120 chemical compound graphs All the graphs are acyclic (i.e., trees) without node labels. There is no split of training and testing in the PyG.
4.1.2 Evaluation Metric
Mean Squared Error (MSE) (in the format of 10-3) is the most popular matrix that measures the average squared error between the predicted scores with the ground-truth similarities. Spearman's Rank Correlation Coefficient (p) and Kendall's Rank Correlation Coefficient correlation of ranking-wisg wise computed results and ground-truth results. Precision at k (p@k) is the intersection of top predicted results with the ground -trth top k over the value k.
evaluate the
4.1.3 Baselines
Beam [27] a variant of the A algorithm [14] sub-exponential time by beam search. Hungar- ian [33] is the cubic-time algorithm based on the Hungarian Algorithm for bipartite graph matching,
and the VJ [9] algorithm
variant of Hungarian method. SimGNN [1] co-attention-biie
GSC method that directly predicts the GED score given two input graphs. Extended-SimGNNN
(i.e.,
E-SimGNN) is an improved version of SimGNN using GIN as the backbone. GraphSim [2] is multi-scale model which fuses the cross- cross-graph features in multiple GNN layers. GMN [22] is another GNN-based method. It manages to fuse the -rash information with the node-level message passing. GENN-A* [40] is the more recent work which applies the GNN to accelerate the hard GED solvers such as * Beam, Hungarian, VJ and GENN-A# are GED solvers that require to output edit path, which, however, are hard to generalize to other GSC metrics. Most of the baseline results are copied from their published papers, and we run the Extended-SimGNN for results collection.
(b)
(c)
Figure 5; t-SNE Visualization of joint embeddings IMDB. (a)-(c) SimGNN; Extended-Sim Our Teacher Model. The color of dots represent the similarity score decreasing from to 0.
4.2 Quantitative Results
The quantitative results on GED are summarized in Tab. 1. The results of SimGNN ALKANE are run by us. It easily observed that the proposed methods, including both the early-fusion model (i.e., teacher model) and student model, outperform the basclines most of the scenarios. Although ours

---

134
130
300
(a)
(b)
(c)
(d)
Figure 6:
The curve of losses through KD. (a)-(d); Training and validation MSE loss on AIDS:
Training and validation MSE loss on IMDB; KD loss AIDS; KD loss on IMDB;
are beaten by GENN-A* in some cases, the proposed approaches have the superiority in extensibility and scalability since there is no need to output the edit path step-by-step. On the IMDB and ALKANE datasets, the teacher model obviously outperforms the baseline ones with a large margin. Comparing the performance of teacher and student model, there is a slight superiority of the former one in most of the cases. While the student model beats the teacher on the MSE metric of the AIDS dataset, which means the reducing model redundancy can further improve the performance in some cases.
4.3 Ablation Study
To investigate the effects of each module, we introduce the ablation study the AIDS and IMDB datasets in Tab. 2 and provide some visualization results in the Subsection 4.5. As shown in Tab. 2, the w/o KD setting has five different components including: without attention in EFN; taking GCN as the backbone (i.e., w/o GIN) to analyze the effects of GIN; Single Level meaning only taking the final-layer GIN feature for embedding fusion; Student and Teacher. It reasonable compare the student models with or without KD. By comparing such two results, the with-KD model has a strong superiority over the latter one. And we can easily find that the teacher model should be regarded as the upper bound of the with-KD student model. Considering the process of KD, the embedding decomposition proves to be useful since the joint feature KD (i.e., Joint Feat) is largely inferior the pseudo individual one. Although there is no much difference between the first-order and second-order distances, the combination of such two distances is helpful to boost the overall performance.
4.4 Inference Time
The comparison on inference time on the whole testing set is shown in the Tab. 3 where the Hungarian and GENN-A* are copied from [40] and others are run by our own. In the Tab. of [40], whose reported time is for one pair of graphs, we have transformed such time into the whole testing set time as: PnirTiiiee x Data Number, i.e., 290. 1h- = 29.915x x 78400. The student model beats other methods in two orders in the case of embedding- based inference. Such results sufficiently indicate the high efficiency of our siamese-based student model in the GSC task, which has the potential for real-time setting.
4.5 Analysis and Visualization
Convergence Analysis. We evaluate the convergence of baseline methods as well as our proposed methods on the ablation scenarios in Fig. 6. Comparing the sub-figures (a) and (b), see that the proposed method (i.e., 'both') reaches the lower MSE loss through iteration. And the models turn converge after 5,000 - 5,500 epochs which makes 6,000 a good choice. Moreover, the Val-both loss is highly overlapped with the training loss (i.c.. 'Train-bold "), which means that there is no clear overfitting of our models. In the KD case, the second-order loss harder minimize.
clearly
Feature t-SNE Visualization. As illustrated in Fig. 5, we employ the t-SNE algorithm [37] to visualize joint embeddings obtained by the encoder given a fixed query graph. The features learned by our approach are more clustered and separable in comparison with (a) and (b).
Example Ranking Results. As shown in Fig. 7, there are no clear differences and errors in the top ranking results. While, the baselines fail to rank the correct graphs in the later sequence, which indicates the superiority of our teacher model in handling the more challenging cases.

---

Rank
2
10
15
30
50
SimGNN
44
d
A
14
E-SiGNNN
44
44
Ours-T
1-0
442
a4
Figure 7: Ranking results of SimGNN, E-SimGNN and our teacher model on IMDB. A, i.c., A [GEDpred G represents the absolute difference between the ground truth GED and the GED of predicted result.
Conclusion
This paper proposes a novel GSC approach for fast inference based on the slow learning. The slow learning involves designing co-attention-base feature fusion network multilevel GNN features that achieves cutting-edge accuracy. To further accelerate the inference speed without much accuracy drop, apply the knowledge distillation compress the proposed co-attention network, ie.. teacher model, to the student one. Moreover, such a student model also enables the offline collection of individual graph embeddings, which is beneficial for online retrieval. We decompose the joint embedding into the pseudo individual ones linearly for precise seacher-student alignment to address the instability through knowledge transfer. The experiments on four demonstrate our approach's 's superiority over the previous methods on both accuracy and efficiency.
datasets
Acknowledgments. Thanks to the grant from Adobe Research to support this project.
References
[1] Y. Bai, H. Ding. S. Bian, T. Chen, Y. Sun, and W. Wang. Simgnn: A neural network approach to fast graph similarity computation. In WSDM, 2019.
[2] Y. Bai, H. Ding, K. Gu, Y. Sun, and W. Wang. Learning-basse efficient graph similarity computation via multi-scale convolutional set matching. In AAAI, 2020.
[3] K. M. Borgwardt and H. Kriegel. Shortest-path kernels on graphs. In ICDM, 2005.
[4] Bougleux, L. Brun, Carletti, Foggia, B. Galizere, and M. Vento. A quadratic assignment formulation of the graph edit distance. arXiv preprint arXiv: urXiv:/512.077994 2015.
[5] C. Buciluã, R. Caruana, and A. Niculescu-Mizil. Model compression. In SIGKDD, 2006.
[6] H. Bunke and G. Allermann. Inexact graph matching for structural pattern recognition. Pattern Recognit. Lett., 1983.
[7] H. Bunke and K. Shearer. A graph distance metric based on the maximal common subgraph. Pattern Recognit. Lett., 1998.
[8] R. M. Dijkman, M. Dumas, and L. Gareía-Bañuelos. Graph matching algorithms for business process model similarity search. In International Conference of Business Process Management, 2009.
[9] S. Fankhauser, K. Riesen, and H. Bunke. Speeding up graph edit distance computation through fast bipartite matching. In International Workshop Graph-Based Representations in Pattern Recognition, 2011.
[10] M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLRW, 2019.
[11] J. Gou, B. Yu, S. J. Maybank, and D. Tao. Knowledge distillation: A survey. IJCV, pages 1-31, 2021.
[12] W. I.. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1-19,, 2020.
10

---

[13] W. Hamilton, R. Ying. and J. Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
[14] Hart, N. Nilsson, and Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 1968.
[15] B. Heo, M. Lee, S. Yun, and J. Y. Choi. Knowledge transfer via distillation of activation boundaries formed by hidden neurons. In AAAI, 2019.
[16] G. Hinton, O. Vinyals, and J. Dean. Distilling the knowledge in a neural network. In NeurlPSW, 2014.
[17] K. Horiik Approximation capabilities of multilayer feedforward networks. Neural networks, 1991.
[18] K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. Neural newworks, 1989.
[19] X. Jiao, Y. Yin, L. Shang. X. Jiang, X. Chen, L. Li, F. Wang. and Q. Liu. Tinybert: Distilling bert for natural language understanding. arXiv preprint 100.111 2019.
[20] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 6980, 2014.
[21] T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[22] Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli. Graph matching networks for learning the similarity of graph structured objects. In ICML, 2019.
[23] Y. Liu, J. Cao, B. Li, C. Yuan, W. Hu, Y. Li, and Y. Duan. Knowledge distillation via instance relationship graph. In CVPR, 2019.
[24] G. Ma, K. Ahmed, T. L.. Willke, D. Sengupta, M. Cole, N. B. Turk-Browne, and Yu. Deep graph similarity learning for brain data analysis. In W. Zhu, D. Tao, X. Cheng, P. Cui, E. A. Rundensteiner, D. Carmel, Q. He, and J. X. Yu, editors, CIKM, 2019.
[25] G. Ma. N. K. Ahmed, T. L. Willke, and P. S. Yu. Deep graph similarity learning: a survey, Data Mining and Knowledge Discovery, 2021.
[26] A. Miech, J.-B. Alayrac, I. Laptev, J. Sivic, and Zisserman. Thinking fast and slow: Efficient text-to-visual retrieval with transformers. arXiv preprint arXiv:2103. 16553, 2021.
[27] M. Neuhaus, K. Riesen, and H. Bunke. Fast suboptimal algorithms for the computation of graph edit distance. Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), 2006.
[28] G. Nikolentzos, P. Meladianos, and M. Vazirgiannis. Matching node embeddings for graph similarity. In S. Singh and S. Markovitch, editors, AAAI, 2017.
[29] W. Park, D. Kim, Y. Lu, and M. Cho. Relational knowledge distillation. In CVPR, 2019.
[30] N. Passalis and A. Tefas. Learning deep representations with probabilistic knowledge transfer.
In ECCV, 2018.
[31] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS. 2019.
[32] B. Peng. X. Jin, J. Liu, D. Li, Y. Wu, Y. Liu, S. Zhou, and Z. Zhang. Correlation congruence for knowledge distillation. In ICCV, 2019.
[33] K. Riesen and H. Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision computing, 2009.

---

[34] A. Romero, N. Ballas, S. E. Kahou, A. Chassang, C. Gatta, and Y. Bengio. Fitnets: Hints for thin deep nets. ICLR, 2015.
[35] Y. Tian, D. Krishnan, and P. Isola. Contrastive representation distillation. In ICLR, 2020.
[36] Tung and G. Mori. Similarity prreeervig knowledge distillation. In CVPR, 2019.
[37] L. Van der Maaten and G. Hinton. Visualizing data using t-sne. JMLR, 2008.
[38] L. Wang and K.-J. Yoon. Knowledge distillation and student-teacher learning for visual intelligence: review and new outlooks. TPAMI, 2021.
[39] L.. Wang. B. Zong, Q. Ma, W. Cheng. Ni, W. Yu, Y. Liu, Song, Chen, and Y. Fu. Inductive and unsupervised representation learning on graph structured objects. In ICLR, 2020.
[40] R. Wang, T. Zhang, T. Yu, J. Yan, and X. Yang. Combinatorial learning of graph edit distance via dynamic embedding. arXiv preprint wrXiv2001..5003 2020.
[41] S. Wang. Z. Chen, X. Yu, D. Li, J. Ni, L. Tang. J. Gui, Z. Li, H. Chen, and P. S. Yu. Heteroge- neous graph matching networks for unknown malware detection. In IJCAI, 2019.
[42] Y. Wang, Y.-Y. Chang, Y. Liu, J. Leskovec, and Li. Inductive representation learning in temporal networks via causal anonymous walks. In ICLR, 2021.
[43] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[44] X. Yan, S. Yu, and J. Han. Substructure similarity search in graph databases, In Özcan, editor, SIGMOD, 2005.
[45] T. Yoshida, I. Takeuchi, and M. Karasuyama. Learning interpretable metric between graphs: Convex formulation and computation with graph mining. In KDD, 2019.
[46] S. Zagoruyko and N. Komodakis. Paying more attention to attention: Improving the performance of convolutional neural networks via attention transfer. In ICLR, 2017.
[47] A. Zanfir and C. Sminchisescu. Deep learning of graph matching. In CVPR, 2018.
[48] Z. Zeng, A. K. H. Tung, Wang, J. Feng, and L., Zhou. Comparing stars: On approximating graph edit distance. VLDB, 2009.
12


Reviews:
[{"review_id": "uvf8qMSS50", "reviewer": "Reviewer_9hgj", "summary": "This paper tackles the problem of graph similarity computation (GSC). The key insight of this paper is that to better model the problem of GSC, early and extensive graph feature fusion is needed, which is harmful to model efficiency. To address this issue, the authors propose a knowledge distillation solution that drops all early fusions. This allows the regression models to take in only the embeddings, which can be pre-computed, and thus saves time. Experimental evaluations indicate that the proposed framework achieves good performance and is fast in inference. ", "questions": "", "limitations": "", "rating": 6, "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": "Overall I like this paper. The paper is based on insightful observations about feature fusion and efficiency, and the proposed technical solution, although not completely new, is sound. The experimental evaluations are extensive. `\n\n**Strengths**: \n- **Clarity**: The paper is in general easy to follow. \n- **Experiments are extensive**. I specifically appreciate the extensive ablation studies on the design. \n- **Sound technical solution**. The technical solutions are based on insightful and realistic observations. \n\n**Weaknesses**: \n- **Somewhat lack in novelty**: As attention, multi-level graph feature fusion, and KD are all existing techniques, the technical solution seems a little short of novelty, although indeed, it is technically sound.\n- **Unfair comparison of inference time**. Since the query graphs may come at any time and may be arbitrary new graphs, I think the comparison of inference time in Table 3 is not very fair, as for completely new query graphs, you still need to first compute its embedding. \n\n**Minor comments**: \n- Line 173, 'a node-wise attention to aware of...', to aware of -> to be aware of\n- Line 174, $h = \\sum_{n=1}^N \\sigma(x^T_ncx_n)$, should it be $\\sigma(x^T_nc) x_n$?\n- The notations through Sec. 3.2.2 are confusing. For example, $h_{ij}^{all}$ and $\\mathbf{h}_{ij}^{all}$ are interleavingly used.  Please consider unifying them. \n- Line 220-221, consider revising the notations, as the $E(\\cdot, cdot, cdot)$ repeats too many times. \n- Eqn 7, I suppose that Huber loss is a binary function, but why is $l_\\delta(\\phi_D(h_{Ab}^T, h_{aB}^T), h_{Ab}^S, h_{aB}^S)$?\n- Sec. 4.1.2, \"matrix\"->\"metric\". \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They are properly addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "No. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "lpYbJ6kwhTP", "reviewer": "Reviewer_WTSt", "summary": "The main contribution of the paper is to propose a new teacher-student framework for efficient graph similarity computation. Different from existing early-fusion models that directly output a similarity score for two input graphs, the proposed framework uses such model as a teacher to teach a student model for fast embedding training and efficient graph similarity computation.", "questions": "", "limitations": "", "rating": 6, "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": "Pros:\n\n- The teacher-student framework for graph similarity computation has several advantages. First, it can collect the individual graph embeddings from the joint embeddings of the two graphs. Second, the student model can distill knowledge from the pretrained teacher model and capture the well learned embedding distance in the teacher model. Third, the teacher-student framework prevents pre-computing the graph embeddings. Overall, the proposed framework is practical and technically sound. The student model can achieve a trade-off between speed and accuracy for graph similarity computation. \n\n- The presentation is good and the paper is easy to follow. Experiments on four benchmark datasets demonstrate the effectiveness of the proposed model.\n\n\nCons:\n\n- In my view, some contributions of this paper are over-claiming. The authors say that they \"speed up the prior art by 65x on the benchmark AIDS data.\" According to the results in Table 3,  it is 9.672/0.148 = 65.35. However, the 0.148s is only the inference time and does not include the time for pretraining the teacher net. It may not be fair to compare the inference time of the offline-stored student model against other early-fusion models. Besides, the reported data for the baselines *Hungarian* and *GENN-A* seems wrong. As reported in Table 3 of the GENN-A paper, their inference time is less than 1s rather than the reported more than ten seconds. So, I think the experimental results cannot well support the claim that the proposed model can speed up 65x. Perhaps, I have some misunderstandings here. So, I would be grateful if the authors could give more explanations to clarify this issue.\n\nTypos:\n\n- Line #126: \"In specific, the edge linking the a pair of nodes including...\" -> \"In specific, the edge linking a pair of nodes including...\"\n\n-- After rebuttal --\n\n- Thanks for the responses to address my concerns regarding the inference time. \n- I would like to leave my score unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please give more details on inference time comparison because it is a key experiment.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Y_zRHoumhlB", "reviewer": "Reviewer_zANd", "summary": "In this paper authors proposed a method to solve subgraph similarity problem using graph neural network. They proposed a knowledge distillation based technique to distill knowledge from a slow early fusion based model to a faster student model which improves the speed of the inference. \n", "questions": "", "limitations": "", "rating": 6, "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": "Originality: \n\nThe work is a novel combination of techniques like Graph Isomorphism Network, slow Early Fusion model, faster Inference model, Knowledge Distillation between the slow model and the fast model. I specially liked the design of the two models for knowledge distillation.\n\nQuality: \n\nThe submission seems technically sound. Claims are generally well supported. One analysis I missed was, why the GENN-A* outperforms this model by a lot specially in AIDS dataset. Any intuitive analysis about this outperformance would have made the paper stronger. I still feel this direction of work is important, but it would be good to know whats missing in the work to make the work better.\n\nI liked the ablation analysis of different parts of the model, \n\nAlso Inference time improvement is impressive, but can we improve the accuracy more even if we use similar times to the other methods especially GENN-A*. I feel like we need to analyze the trade off between time and accuracy in this work. Especially can we design a more accurate teacher model which can use more time/memory to be competitive with GENN-A*.\n\nClarity: \n\nThe submission is clearly written and seems well organized. There are some typo like \"graph convectional network\" in line 41. But the work was easy to read and understand.\n\nSignificance: \n\nI think this is a very important problem to solve in this area. It should be impactful work for researchers in this domain. Even though it does not beat the state-of-the-art in all cases, its still a novel way to model the problem.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Did not find the section", "review_text": "", "extra_scores": {"ethical_concerns": "no ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "QubKoj0F3RW", "reviewer": "Reviewer_Srnx", "summary": "The paper presents a new method for computing graph similarity efficiently and approximately using graph neural networks. A novel attention-based neural network is proposed for combining the embeddings for the two input graphs. A novel way to compute graph similarity faster is proposed based on embedding decomposition and applying knowledge distillation to obtain a fast model from a slow model. Experiments on four graph datasets demonstrate the effectiveness and efficiency of the proposed method.", "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": "Originality: The task addressed in the paper is graph similarity computation (GSC), which can incorporate several hard-to-compute metrics such as GED, MCS, etc. The proposed method contains a novel Embedding Fusion Network (EFN) and a novel way to apply knowledge distillation to the task of GSC. It is clear how the proposed model is different from previous works, and the important previous works are adequately cited and compared against in the experiment.\n\nQuality: The submission is technically sound with claims relatively well supported by experimental results. The authors also list several limitations of the work in the supplementary material. However, I recommend the authors testing the methods on larger graph datasets and more graph similarity metrics to better support the claims.\n\nClarity: The submission is clearly written and well organized.\n\nSignificance: The paper indeed points out a potentially very promising direction of computing graph similarity in an efficient way, ie using knowledge distillation. The idea of learning both a slow model and fast model on its own is not new but is a very interesting and promising direction, and is relatively underexplored in the graph deep learning domain. I can foresee future researchers could build upon this idea.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are several things that could further improve the quality of the work:\n\n1. The authors use four benchmark datasets, but given the high standard of NeurIPS and the relatively small sizes of the four datasets, I strongly recommend the authors using larger datasets in terms of both the number of graphs and the average number of nodes. Specifically, the authors do not mention the detailed statistics of the datasets, but by checking with previous works, it seems the largest dataset contains a few hundreds of nodes on average. Scaling to graphs of 1K, 10K, 100K, and even 1M nodes will show the strengths and potential limitations of the proposed method better. This is especially important since one key contribution is the fast model learned through embedding decomposition and knowledge distillation. \n\nThe issue of dataset being small is also seen from Section 4.4 and Table 3, where the authors show the average inference time on AIDS. AIDS only contains graphs of <= 10 nodes, and using this dataset to demonstrate how fast the student model runs is fine, but if using a very large graph dataset of more nodes on average, the speed-up gained by the fast model can be more significant.\n\n2. The authors mention several graph metrics in Section 2.1, but only GED is used in the experiments. The authors should consider testing the methods on other metrics such as MCS.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new teacher-student framework for efficient graph similarity computation. The student model decouples the interaction of two graphs learned in teacher model into two separate representation vectors, which can speed up the inference significantly. The authors’ rebuttal is general well written, and has provided new experimental results requested by the reviewer.  The reviewers have concerns on the novelty, as the main techniques are adapted from existing work. But the application of knowledge distillation for similarity computation itself is novel, and the design is smart and suits the inference need very well. The results are significant. Therefore, I recommend acceptance.
Decision: Accept (Poster)