Slow Learning and Fast Inference: Efficient Graph Similarity Computation via Knowledge Distillation
Year: 2022

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.

heading: 1 Introduction
text: Measuring the similarity across graphs, i.e., Graph Similarity Computation (GSC), is one of the core problems of graph data mining, centered around by multiple downstream tasks such as graph retrieval [1, 2], plagiarism/anomaly detection [22, 41], graph clustering [39], etc. As shown in Fig. 1, the graph similarity can be defined as distances between graphs, such as Graph Edit Distance (GED). The conventional solutions towards GSC are the exact computation of these graph distances, which, however, is an 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 a motivating example, in graph-structured molecules or chemical compounds query for in-silico drug screening, fast identifying similar compounds in a large database is 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
∗Corresponding Author: qin.ca@northeastern.edu
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
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 as a twin of GNNs bridged by a co-attention with a Multi-layer Perceptron (MLP) stacked as the regression head. Such approaches can be trained in a 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 as the backbone [1, 2], this paper adopts a 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 a 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 to contribute to the desired task. Moreover, to make the model easier to deploy, we take an MLP for feature learning which is simple but effective to achieve cutting-edge performance.
Intuitively, speed and accuracy can be considered as a trade-off. GSC naturally requires dense connections/interactions between the two input graphs, which will consequently cause increasing computations as the cost. This paper focuses on the efficiency of inference speed which can be addressed by either model compression or a faster data loading pipeline. Especially in industrial scenarios, the raw graph data are usually pre-processed as the embeddings 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 co-attention-based 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, as 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.
To overcome the accuracy drop of such a 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 fusion network regarded as the teacher model, and the student model is a siamese network without co-attention. It is found that the direct distillation of joint embeddings fails to work where the KD loss disturbs largely during training. To solve this, we generate the pseudo individual embeddings 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 pseudo 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:
• We introduce a 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 off-line 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. †

heading: 2 Related Works

heading: 2.1 Graph Similarity Computation (GSC)
text: 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, a number of neural network based methods have been proposed and demonstrated a huge success [47, 1, 2, 24, 22, 41, 40]. Among them, regression-based similarity learning has a great promise due 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 a 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 are 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 as Accuracy, Mean Squared Error (mse), Spearman’s Rank Correlation Coefficient), the complex subgraph matching/fusion components (termed ‘early-fusion’ 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.

heading: 2.2 Knowledge Distillation (KD)
text: Knowledge distillation is a general neural network training method, where a (typically pretrained) teacher network is introduced to guide the learning of a 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 to 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]).

heading: 3 Approach
text: This section will introduce 1) the architecture of the early-fusion network (i.e., teacher model); 2) the KD process and its interpretation. Before that, we start from the formalized problem definition.

heading: 3.1 Problem Formulation
text: Formally, a graph G is defined upon the node set V and edge set E as G = (V, E). In specific, the edge linking a pair of nodes including u ∈ V and v ∈ V can be denoted as the (u, v) ∈ E . In our setting, all the accessible graphs are undirected, i.e., (u, v) ∈ E ↔ (v, u) ∈ 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://github.com/canqin001/Efficient_Graph_Similarity_ Computation
A ∈ R|V|×|V|. 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 can be denoted as a real-value matrix X ∈ R|V|×m with the m 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 Gi and Gj ∈ D, whereD = {G0,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 the nGED, i.e., nGED(Gi,Gj) = GED(Gi,Gj)(|G1|+|G2|)/2 . In the following, nGED should be transformed to the value ranging (0, 1] as the ground truth similarity score sij , i.e., sij = exp(−nGED(Gi,Gj)) ∈ S, where S ∈ R|D|×|D| indicates the similarity matrix among all the graphs [2] .

heading: 3.2 Early-fusion Network (Teacher Model)
text: As discussed above, the key success of GSC is to 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-graph 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.

heading: 3.2.1 Graph Isomorphism Network (GIN)
text: The isomorphism on graphs, i.e., Gi ' Gj , is defined as a bijection between Gi and Gj : f : V (Gi)→ V (Gj). Graph isomorphism is highly related to GSC where the graphs isomorphism also represents that the GED is 0: Gi ' Gj ↔ GED(Gi,Gj) = 0. 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 : G → h ∈ Rd denote a general GNN. The iterative updating of node features from the (k − 1)-th to the k-th layer can be formulated as:
h(k)v = φ ( h(k−1)v , f( { h(k−1)u : u ∈ N (v) } ) ) , (1)
where N (v) is the set of neighbouring nodes of node v and its embedding at layer k is denoted as h (k) v . φ and f represent the different mapping functions. In GIN, it has been discussed that the MLP can model the f and φ very well due to the universal approximation theory [18, 17]. Therefore, the composition of f (k+1) ◦ φ(k) is replaced by an MLP. The node embedding of GIN is updated as:
h(k)v = MLP (k) ( (1 + (k)) · h(k−1)v + ∑
u∈N (v)
h(k−1)u
) , (2)
where (k) 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( { h(k)v |v ∈ G } )|k = 0, ...,K ) , (3)
where the features in all the layers, i.e., 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.

heading: 3.2.2 Embedding Fusion Network (EFN)
text: Feature fusion across graphs is crucial for GSC. In this paper, we have proposed a 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 X ∈ R|V|×m where the n-th row, xn ∈ Rm representing the embedding of node n, we firstly obtain the global context c ∈ Rm as c = tanh( 1NW ∑N n=1 xn), where W ∈ Rm×m is a learnable matrix. Then, there is a node-wise attention to be aware of the similarity between node and global context: h = ∑N n=1 σ(x T n c)xn where σ(·) is the sigmoid function and h ∈ Rm is the graph-level embedding.
The concatenated feature of graph i and j is denoted as hij = CONCAT(hi, hj) ∈ R2m. Since features hi, hj 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 hij to accomplish this goal as:
h∗ij = MLP(ϕ(WUδ(WDhij)) · hij + hij), (4)
where h∗ij ∈ Rd is regarded as the joint embedding of graph i and graph j, and ϕ(·) and δ(·) denote the sigmoid gating and ReLU function respectively. WD is the weight set of a NN layer, which acts as downscaling with reduction ratio r assigned as 4. After ReLU activation, the low-dimension signal is then increased to hij with the ratio r by a upscaling layer, whose weight set is denoted as WU .
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 hallij = CONCAT(h (1) ij , h (2) ij , h (3) ij ) ∈ R3d. Then, an EFN is applied to take the concatenated embedding hallij for multi-level feature fusion as Eq. (4): h∗ij = EFN(h all ij ) ∈ RD, where D is assigned as 16.
The whole early-fusion network consists of two components: the encoder net and the regression net parameterized by ΘE and ΘR. As shown in Fig. 3, the GIN and EFNs stated above can be summarized as an encoder net as h∗ij = E(Gi,Gj ,ΘE). Then, an MLP-based regression net is attached to project the joint embedding h∗ij into the desired similarity score sij optimized by the MSE loss as:
Lreg = 1 |D| ∑ i,j∈D ( R(E(Gi,Gj ,ΘE),ΘR)− sij )2 , (5)
where R(·) denotes the regression network and D represents the set of all the training graphs.

heading: 3.3 Efficient Graph Similarity Computation
text: Although the proposed early-fusion network can achieve the competitive results with a similar time cost as previous co-attention-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 a room to 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.

heading: 3.3.1 Embedding Decomposition
text: To decompose the joint embedding h∗ij into the separate individual embeddings h ∗ i and h ∗ j is a necessary step for KD. The primary reason for embedding decomposition is that we hope to achieve
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 a 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 is shown in Fig. 4. The basic assumption of this design is that the joint embedding might be represented as the linear combination of individual embeddings in the high-dimensional feature space. Specifically, given graph A and graph B, the joint embedding can be easily achieved as h∗AB = E(GA,GB). Moreover, we also have access to the h∗AA = E(GA,GA) and h∗BB = E(GB ,GB) given duplicate inputs. Under the assumption of linear combination, the pseudo individual graph embedding will be computed as h∗aB = h ∗ AB − h∗AA where h∗aB 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∗Ab = h ∗ AB − h∗BB . To ensure the consistence with the desired task, we later concatenate the pairs of pseudo individual graph embeddings as h∗AaBb = CONCAT(h ∗ aB , h ∗ Ab) that redundantly covers the knowledge of joint embedding h∗AB . Another MLP-based regression network R ′ is applied to project it into the desired target score R′(h∗AaBb,Θ ′ R) ∈ R optimized by the MSE loss as Eq. ( 4):
L ′ reg = 1 |D| ∑ i,j∈D ( R′([hi,j − hi,i;hi,j − hj,j ],ΘR′)− sij )2 , (6)
where hi,j = E(Gi,Gj ,ΘE), hi,i = E(Gi,Gi,ΘE), hj,j = E(Gj ,Gj ,ΘE) and [ · ; · ] represents the operator of two features concatenation. More details and the verification of the proposed linear embedding decomposition are provided in the ablation study of Sec. 4.3.

heading: 3.3.2 Knowledge Distillation (KD)
text: To get a fast model from a slow one, there are multiple compression solutions such as pruning, quantitation, etc. This paper adopts a 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 hTAB , we could obtain pseudo individual embeddings h T aB and h T Ab of the teacher model. For the student model, we take a siamese GIN as the feature encoder, i.e., hSA = GIN(GA,ΘSE) and hSB = GIN(GB ,ΘSE). Then, the next step is to fuse the individual embeddings to achieve the joint embedding as hSAB = I(h S A, h S B ,Θ S I ), where I(·) is a standard EFN. The pseudo individual embeddings, i.e., hSAb and h S aB , is computed following the same strategy of the teacher network.
To enforce the student model to 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 as:
LKD(GA,GB) = α2 ( ∥∥hTAb − hSAb∥∥1 + ∥∥hTaA − hSaB∥∥1) + (1− α)lδ(ψD(hTAb, hTaB), ψD(hSAb, hSaB)),
(7)
where ψD(hi, hj) = ‖hi − hj‖1 is distance-wise potential function measuring the first order distance in the same domain, and lδ is the Huber loss [26]. The second order distance is used to maintain the
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 hSAB . Apart from the KD loss, there is a supervision (i.e., MSE) loss LSreg on the student model to fulfill the object of the task.

heading: 4 Experiments
text: Although our proposed approach can be generalized to different graph distances, we pick the Graph Edit Distance (GED) as the evaluation task, which follows the standard protocol [1].

heading: 4.1 Setup
text: We deploy the GIN [43] as the backbone of the encoder network. The regression network is a 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 on PyTorch Geometric (PyG) [31, 10]. The learning rate is 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 on PyG-based re-implementations of SimGNN ‡ and Extended-SimGNN §. All experiments are run on the machine with Intel i7-5930K CPU@3.50GHz with 64GB memory.

heading: 4.1.1 Benchmarks
text: 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 ¶.
• AIDS (i.e., AIDS700nef) is 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-MULTI”) has 1,500 unlabeled graphs representing ego-networks of movie actors/actresses. There will be an edge if the two actors/actresses show in the same movie.
‡https://github.com/benedekrozemberczki/SimGNN §https://github.com/gospodima/Extended-SimGNN ¶https://pytorch-geometric.readthedocs.io/en/latest/_modules/torch_geometric/
datasets/ged_dataset.html#GEDDataset
• ALKANE [4] is a 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.

heading: 4.1.2 Evaluation Metric
text: 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 (ρ) and Kendall’s Rank Correlation Coefficient (τ ) evaluate the correlation of ranking-wise computed results and ground-truth results. Precision at k (p@k) is the intersection of top k predicted results with the ground-truth top k over the value k.

heading: 4.1.3 Baselines
text: Beam [27] is a variant of the A* algorithm [14] in sub-exponential time by beam search. Hungarian [33] is the cubic-time algorithm based on the Hungarian Algorithm for bipartite graph matching, and the VJ [9] algorithm is a variant of Hungarian method. SimGNN [1] is a co-attention-based GSC method that directly predicts the GED score given two input graphs. Extended-SimGNN§ (i.e., E-SimGNN) is an improved version of SimGNN using GIN as the backbone. GraphSim [2] is a multi-scale model which fuses the cross-graph features in multiple GNN layers. GMN [22] is another GNN-based method. It manages to fuse the cross-graph 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 A*. Beam, Hungarian, VJ and GENN-A* are the 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.

heading: 4.2 Quantitative Results
text: The quantitative results on GED are summarized in Tab. 1. The results of SimGNN on ALKANE are run by us. It is easily observed that the proposed methods, including both the early-fusion model (i.e., teacher model) and student model, outperform the baselines on most of the scenarios. Although ours
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.

heading: 4.3 Ablation Study
text: To investigate the effects of each module, we introduce the ablation study on 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 is reasonable to 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 to 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.

heading: 4.4 Inference Time
text: 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. 2 of [40], whose reported time is for one pair of graphs, we have transformed such a time into the whole testing set time as: OnePairT ime × DataNumber, i.e., 290.1h = 29.915s × 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.

heading: 4.5 Analysis and Visualization
text: 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), we can clearly see that the proposed method (i.e., ‘both’) reaches the lower MSE loss through iteration. And the models turn to 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.e., ‘Train-both’), which means that there is no clear overfitting of our models. In the KD case, the second-order loss is harder to minimize.
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 5 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.

heading: 10 15 30 501 2 3 4 5Rank

heading: 5 Conclusion
text: This paper proposes a novel GSC approach for fast inference based on the slow learning. The slow learning involves designing a co-attention-based feature fusion network on multilevel GNN features that achieves cutting-edge accuracy. To further accelerate the inference speed without much accuracy drop, we apply the knowledge distillation to compress the proposed co-attention network, i.e., 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 teacher-student alignment to address the instability through knowledge transfer. The experiments on four real-world datasets demonstrate our approach’s superiority over the previous methods on both accuracy and efficiency.
Acknowledgments. Thanks to the grant from Adobe Research to support this project.

Review summaries:
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.

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. 

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. 

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.