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-attennioon-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, = EGG. 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), h3. = 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://pwtorccogggettrii..ccc wew.eerr.......eeeeeeee.........
aatasets/ged_dataeeet 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.07794. 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": "eFtBLwZYo4V", "reviewer": "Reviewer_3zgJ", "summary": "The paper studies efficient graph similarity computation and proposes two connected techniques: a complex teacher model slowly learning through the graph and a simpler student model jointly learned and proposed to be used for faster inference. The proposed technique uses well-established Fusion network structures. The joint learning through knowledge distillation enables the simpler student model to learn more accurate latent representations through the teacher network. Both accuracy and run-time results have been provided using benchmark data sets.\n", "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": "The paper studies an important graph similarity computation problem. It does not propose completely new techniques/methodologies but uses known ones in a reasonably creative way to attack an important problem. It provides a variety of results--mostly adequate with some caveats I explain below. I could easily follow the paper as a first-time reader, it is reasonably well written. \n\nIn short, the paper proposes an interesting solution to an important problem. However, the results are not convincing enough to justify such a complex solution. It is possible that there is not adequate experimentation or explanation of the results. \n\n1) Sometimes the (significantly simpler) student model beats the teacher model in terms of accuracy (e.g., mse, p). This has not been studied well. In my opinion, this is a very important matter and at the heart of the paper. The reason for the existence of the teacher model is just to help the student model but if it is often not necessary in terms of accuracy, what is the point? How common is this?  Under what conditions/problems/data sets does this happen? Could one just learn the student model and have the fast inference technique.\n\n2) The main motivation for the dual architecture is fast inference. The motivation is well explained (e.g., many online systems are ok for long offline training but require low latency in inference). However, I don’t think that the experiments (e.g., table 3) are fair enough. The difference between student-F and student-R is an implementation detail where embeddings are computed offline and stored (  a fairly important and practical technique commonly used). The shortcoming is that such similar optimizations have not been explored in other techniques. Is it possible at all for other techniques to do at least some partial offline computation and store results? Many of the baseline results are just copied from the relevant papers. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main application of the paper tries to make similarity search, or complex graph search much more convenient. This has a bunch of positive implications from search engines to bioinformatics. However, the proposed techniques could be used in a vast variety of fast retrieval/search systems in which bad actors could do an adversarial search in the complex graphs. A short description of such social/practical implications can be explained further. What could negatively happen if we have very fast graph similarity computation? For example, could hackers make faster password searches?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "dHVfjDBJzak", "reviewer": "Reviewer_wszK", "summary": "The proposed model leverages co-attention mechanisms in graph neural networks and knowledge distillation to compute the similarity between two graphs As a result, the model is able to approximate graph similarity (exact computation is an NP-hard problem) more efficiently without compromising on accuracy", "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": "Major Comments\n- I recognize the computational challenges of graph similarity computation. Given such great improvements in computational efficiency, how well would the proposed method work on larger graphs? Currently, the benchmark datasets are quite small (i.e. <2000 graphs, each with ~10 nodes)\n- What is particularly challenging about the AIDS dataset such that the proposed methods do not perform as well as existing SoTA methods despite achieving faster computational efficiency?\n- At what point does the drop in accuracy become inappropriate? Are there other ways to evaluate performance and demonstrate that the accuracy tradeoff is not too detrimental (i.e. domain-specific metrics)?\n- Why is computational efficiency measured/reported only for the AIDS dataset?\n\nMinor Comments\n- The author checklist is incomplete. There are many \"See .\" statements with missing pointers to the relevant sections in the main paper. \n- Please be consistent with MSE acronym (i.e. MSE or mse).\n- Would it be possible to define \"early fusion\" earlier in the text (even in the abstract)?\n- Why is 6,000 epochs necessary? How long does each epoch take? Is this an improvement from existing SoTA methods?\n- \"...which, however...\" is unnecessarily confusing; easy to stumble.\n- \"Multi-layer Perception (MLP)\" should be \"Multi-layer Perceptron (MLP)\"\n- Many typos, i.e. on line 126 and grammatical errors.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No, there is no broader impact statement", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "MLIsjGMhHcT", "reviewer": "Reviewer_quwN", "summary": "This paper presents a novel approach to address Graph Similarity Computation (GSC) both accurately and efficiently. From my point of view, the technique contributions of this paper can be summarized in two perspectives, i.e., feature fusion and knowledge distillation. The proposed slow learning employs multi-scale integration and attention-based feature fusion for cross-graph interaction, making it achieve cutting-edge accuracy on most datasets within a comparable computation cost. The fast inference module is the major contribution and the most attractive point of this paper. The authors apply the embedding decomposition to separate the individual features for knowledge distillation, which successfully improves efficiency by vast scale without much accuracy drop. Overall, this paper has made a solid contribution to this field with comprehensive experimental results to support it.", "questions": "", "limitations": "", "rating": 7, "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": "The detailed comments are provided below.\n\nStrengths:\n\n+ From the technique perspective, the distillation of attention-based models into separate ones is a novel direction with limited previous works [1]. The crucial challenge here is the joint feature is unfriendly for knowledge transfer. This paper presents a novel embedding decomposition method to address it successfully, which is valuable.\n\n+ The improvement in the inference speed is significant. Compared with previous co-attention-based methods, the distilled one shows the overwhelming superiority in speed (65x faster). Such high speed might be helpful for industrial usage.\n\n+ In the teacher model, the proposed embedding fusion network employs a simple stacking of an MLP and an attention layer which is slightly novel and outperforms previous approaches [2] with comparable computation time. The design of the teacher model can be regarded as a minor contribution of this paper.\n\n+ The logic of this paper is clear with detailed formulation, making it easy to understand for readers. And the discussion of related works in Sec2 covers most of the well-known literature.\n\n+ The experimental results are comprehensive. There are multiple matrices and public datasets to evaluate the performance of models. Some detailed ablation analysis and visualization are helpful as well.\n\n[1] A. Miech et al. Thinking fast and slow: Efficient text-to-visual retrieval with transformers. arXiv 21.\n[2] Y. Bai et al. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. AAAI 20.\n\n \nSuggestions and Questions:\n\n1. It seems that some of the formulations could be further simplified. I recommend authors carefully check them.\n\n2. I am slightly confused about Fig 7. What does the \\delta indicate here, and what is the different meaning compared with the ranking score.\n\n3. Do authors have any plan to release the code? I will be appreciated if doing so.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Drawbacks and societal impacts are listed below.\n\nDrawbacks:\n\n-The major concern of this paper is that some of the contents are not clear enough. For instance, since the authors mentioned that the direct distillation of joint embedding fails to transfer knowledge, there should be more explanation on this point. \n\n-Parts of experiments seem missing. For example, in Fig 5, why not providing the tsne map of the student model. And Fig 6 is not quite clear to compare the difference of baseline methods. I recommend the authors zoom in Fig 6.\n\n-There are some grammar errors or typos. For instance, “the color of dots represent the similarity score” in the caption of Fig 5 should be revised as “the colors of dots represent the similarity score”.\n\nSocietal Impact:\n\nI have not seen the negative societal impact of this paper.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper addresses the problem of speeding up the computation of accurate similarity between two graphs, which is one of the key problems in the highly active field of graph learning.
In order to mediate between time-consuming-but-detailed comparisons and fast-but-insufficient comparisons, this paper proposes a distillation approach.
The use of distillation in this context of graph comparison is new and makes much sense, and the tailed experiments also supports the effectiveness of the proposed method (although the property for very large graph is still open to investigation.)
Overall, this paper makes a solid technical contribution to this field and will be well received by the NeurIPS community.



Decision: Accept (Poster)