Efficient Graph Similarity Computation with Alignment Regularization
Authors: Wei Zhuo
Guang Tan
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph neural networks
graph similarity learning
efficient model

Abstract: We consider the graph similarity computation (GSC) task based on graph edit distance (GED) estimation. State-of-the-art methods treat GSC as a learning-based prediction task using Graph Neural Networks (GNNs). To capture fine-grained interactions between pair-wise graphs, these methods mostly contain a node-level matching module in the end-to-end learning pipeline, which causes high computational costs in both the training and inference stages. We show that the expensive node-to-node matching module is not necessary for GSC, and high-quality learning can be attained with a simple yet powerful regularization technique, which we call the Alignment Regularization (AReg). In the training stage, the AReg term imposes a node-graph correspondence constraint on the GNN encoder. In the inference stage, the graph-level representations learned by the GNN encoder are directly used to compute the similarity score without using AReg again to speed up inference. We further propose a multi-scale GED discriminator to enhance the expressive ability of the learned representations. Extensive experiments on real-world datasets demonstrate the effectiveness, efficiency and transferability of our approach.


Efficient Graph Similarity Computation with Alignment Regularization
Wei Zhuo
Guang Tan
Shenzhen Campus of Sun Yat-sen University zhuow50mai12. sysu. edu. en
Shenzhen Campus of Sun Yat-sen University tanguang0mail. sysu. edu. cn
Abstract
We consider the graph similarity computation (GSC) task based on graph edit distance (GED) estimation. State-of-the-art methods treat GSC learning- based prediction task using Graph Neural Networks (GNNs). To capture fine- grained interactions between pair-wise graphs, these methods mostly contain a node-level matching module in the end-to-end learning pipeline, which causes high computational costs in both the training and inference stages. We show that the expensive node-to-node matching module not necessary for GSC, and high- quality learning be attained with a simple yet powerful regularization technique, which we call the Alignment Regularization (AReg). In the training stage, the AReg term imposes node-graph correspondence constraint on the GNN encoder. In the inference stage, the graph-level representations learned by the GNN encoder are directly used compute the similarity score without using AReg again speed up inference. We further propose multi-scale GED discriminator to enhance the expressive ability of the learned representations. Extensive experiments on real-world datasets demonstrate the effectiveness, efficiency and transferability of our approach.
Introduction
Graph similarity computation (GSC) a fundamental task in graph databases and plays critical role in many real-world applications, including drug design [14] 28 program analysis [16], and social group identification 21 27.. For example, one can search a drug database for query chemical compound, in order to identify drugs with high similarity in structures or attributes and thus similar curative effects as desired 23). To measure the similarity between pair-wise graphs, Graph Edit Distance (GED) 5 has been a major metric due to its generality, and many other graph similarity measures have been proven to be its special cases Unfortunately, computing exact GED an NP-hard problem in general [12
With the provably expressive power distinguishing graph structures 32 Networks (GNNs) have been adopted for GED approximation and shown to achieve superior per-
Graph Neural
formance on accuracy. Most state-of-the-an thett-rttrrttt CONN-based GSC models [ 3 & 18
16 contain two
sequential submodules in the end-to-end learnable pipeline (left of Fig. I (1) GNN encoder, which shared across two graphs to embed nodes into representation vectors to capture the intra-graph structure and feature information; (2) matching model, which computes cross-graphe node-level similarity, i.e., how a node in one graph relates all the nodes the other graph. The model outputs summarized vector that fuses the node-level similarities between two graphs. Then, the similarity score is predicted based on the summarized vector via regression head. The computational cost of such sequential framework mainly comes from the matching model, which requires computational and memory cost quadratic in the number of nodes and sometimes involves additional parameters such as attention weights [18 [6], leading heavy time consumption in both the training and inference
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

stages. Especially in the inference stage, we need to query every testing graph from the database. The recent approach EGSC [22] speeds up the similarity learning by dropping the matching model from SimGNN []. However, since cross-graph node-level interactions are ignored, EGSC cannot capture finer-griied similarity information, and thus results in suboptimal prediction performance. To overcome the intrinsic tension between predictive accuracy and speed, we propose separated neural structure (right of Fig. D that detaches the matching model from the sequential pipeline, where the matching model only acts regularization term in the training stage to help the GNN encoder capture ene-grained similarity information, while in the inference (testing) stage, since the latent pross-graph interactions have been learned by the GNN encoder, the final similarity score can be directly computed based on the output representations of the GNN encoder without invoking the matching model again.
We show that explicitly learning the cross-graph grass node- to-node similarity is unnecessary, as the correlation information contained in the features and graph topol-
ogy, when properly exploited, is sufficient to reflect such cross-graph interactions (see Section B) Specif- ically, the problem of GED computation is equiva- lent to finding an optimal permutation such that the adjacency matrices of the two graphs be best aligned. Hence, by analyzing the necessary condi- tions under the optimal permutation, we find that the best matching between two graphs can be inferred by minimizing the difference between the intra-graph node- grde-graph similarity and cross- prass-graph node-graph similarity. It motivates us design task-agnostic matching model based on the input data itself, with a novel regularization technique, called the Alignment Regularization (AReg). AReg obviates the need of matching model in the inference stage, thus mak- ing the model more efficient. AReg is also model-agnostic and can be applied to other GNN- GSC models.
GNN Encoder
seporate
GNN Encoder
Matching Model
<>
Mascching
Medel
Prediction
Prediction
Figure I:
Illustration of separating the match- ing model from the end-to-end GSC frame- work to achieve a fast model (right side). In the fast model, the dotted arrow means the matching model does not participate in the similarity computation in the inference stage.
On the other hand, GNN-based GSC models usually a single GED discriminator followed by regression head to fuse graph representations from pair-wise input graphs and output a final similarity prediction score. We show that single GED diseriminator does not fully capture the dissimilarity between two graphs, while diverse discriminators may provide complementary information to reflect GED more accurately. Thus, we propose multi-scale GED discriminator improve the discriminability of the learned representations. We call the overall framework ERIC: Efficient gRaph sImilarity Computation, and conduct extensive experiments verify the efficacy of our design. Results on several real-world datasets demonstrate that ERIC achieves state-of of-te-o-tthe-aeee the-hrr performance by significantly outperforming the baselines.
2 Preliminary
Problem Formulation of GSC. Given a graph database D and a set of query graphs Q, the problem of graph similarity computation is to produce a similarity score y between VG; E Q and YG, E D, i..., = s(G,, Gj)) where : D x Q + R 10.1 is a similarity estimator. A graph G E D U Q is defined as G = (V, E). where V = {erj
k= is a node set and E' E V x V is an edge set. In our setting, all the accessible graphs are unweighted and undirected. V and E jointly formulate an adjacency matrix A E IR NxN If nodes are accompanied by features (e.g., labels or attribute vectors), they are represented as X E R Nxd with dimension d.
Graph Edit Distance (GED). GED as graph similarity measure has been popularly adopted on graph search queries, due to its capacity to capture the structural and feature differences between graphs. As shown in Fig. 2 GED is defined as the number of edit operations in the optimal path that transforms G into Gj, where the possible edit operations under consideration include edge

---

deletion/insertion, node deletion finsertion, and node relabeling. To well fit the end-to-ent regression task, instead of directly estimating the GED between two graphs, we convert the GED the ground truth similarity score that the learning model aims to approximate. Following []], the normalized GED(G,,G) and the ground truth similarity score between GED is defined as nGED((,, G3)) (
G2 and Gj is defined as the normalized exponential of GED, resulting in a value ranging (0, 1], i.c.,
Sij exp( (nEDD G2)).
edge deletion
edge insertion
node
G2
relabeling
Figure 2: The optimal edit path with edit operations to transform G3 to Gy. As result, GED(G;, G2) =3.
Motivation: Analyzing GED in Embedding Space
Given two graphs G. (A;, X,) and G5 (Aj, X;) with the same number of nodes N (If they have different numbers of nodes, pad the smaller A and X with zeros to make the two graphs equal in size), π( x.)) is node index permutation that preserves the adjacency matrix. r(A) denotes the adjacency matrix after node index permuting. We divide the computation of GED between G; and Gj into two steps: (i) finding permutation for Gj. such that
min Σ (A. - n (A,)) [k, (k, x
(1)
where is the sum the absolute values of all elements in matrix A, A (AA)). We denote the optimal permutation satisfying Eq. (I) as n². (ii) counting the number of cross-graph node pairs with the same indices yet different features, denoted as m. Then GED(G, G,) graphs are topologically isomorphic, there exists π = T such that A, = π (A₂). ). i.e., c c= 0. Hence the GED only determined by distinct features. For another example, when the node permutation assigns indices to Gj as shown in Fig. [ the structure of G; and Gj can be best aligned, i.e., = 4. Then, only one pair of nodes with the same index across graphs have different features (e.g.. node 4). Thus, GED Gý) = 3. The core of this two-step method is finding the optimal permutation to best align two graphs, then m determined under such alignment. Traversing all possible permutations to find n² is also NP-hard, so we make some heuristic rules from Eq. (I) to guide the model design. Under the optimal permutation π the row similarity between A, and x (A,) is maximized, so given an injective function fo(:) R-- + I2 parameterized by to guarantee that nodes with different connectivity can be distinguished, a necessary condition is that the distance between So(A, [k) and (A,) is minimized for all l E [1....,N.. From a global view, the matrix similarity between A, and (A,, is also maximized. Given an injective function (-(-) R NNN X + Rd
m. Obviously, if two
parameterized by Φ. another necessary condition under the optimal permutation is that the distance between 9o (A:) and (o(TT" (o(T)(A))) is minimized. Thus, the optimal permutation x² in Eq. ( also
satisfies the following function,
n² arg min DIST (fo(A.))) (T)))
(go (A:).
4k E {1, ,N,
(2)
where (IST(::)) a distance metric. The two terms in Eq. 2 can reflect GED at node-level and global-level respectively. Further, we regard {fo( A, [k]
)
== U
(k)) as 2N anchors
and assume N > d. When the second term of Eq. (2) reaches minimum, indicates that (A,)
and 9 (T" (Az)) have similar distances to all anchors, l.e., the following % and 7 take the minimum value when π π
N DIST (Fo(A.()), 9.))).ss))))) (A.)) - DIST 9o
7/2
Σ
go
For node deletion, all edges connected to the deleted node are also deleted. Although editing of multiple edges is involved, it is single-time effort. Thus, node deletion is treated single graph edit operation.
3

---

1-sT layer
L-th lyper
Shared
Shared
Fred. Vilue
6NN
6NN
Figure 3: Overview of ERIC. The GNN encoder is shared across two graphs. The green lines denote AReg. The summarized graph representations Zg and Z, are combinations of graph representations learned in each layer, which are fed into the GED discriminator followed by regression function to obtain the prediction value. In the inference stage, the AReg submodule is removed.
N DIST
9o (A.)) - DIST
On the other hand, the first term of Eq. 2 is finer-grained alignment between two graphs, and x* causes the first term of Eq. (2) to reach a minimum. Since the only difference between Y and 7 is that Yj replaces fo (A, in %/ with (A) [k]), the distance between fo ((A,())) and fo (A, [R)) can be reflected by the difference between "/8 and 7y, i.e., |1 7/ll2- Hence, under the optimal permutation π x² G; and Gj are best aligned, and so Eq. is established, which is equivalent to 7í. and |/1 - -2 ||2 all taking the minimum values. These terms reflect similarities between pair-wise graphs at both node- and graph- levels, which can be inferred from the graph structure itself without consulting the ground-truth GEDs. It motivates us to separate the matching model from the end-to-end pipeline. In other words, instead of directly searching the optimal permutation π²", we derive the necessary conditions under n², which impose additional constraints on the coordinates of nodes the embedding space. These conditions are necessarily sufficient, nevertheless they can provide useful knowledge for the model to learn representations that are better tailored to the GSC task. In Appendix A, we further analyze the rationality of this approximation by analyzing the sufficiency of these conditions. Assuming Is is permutation-invet invariant function, then all permutation operators in Eq. (3) and Eq. 4 can be removed. Moreover, instead of computing prosshgraph node-to-node similarity to compute a 'soft' alignment as done in most related work, 7/2 and 7 only compute node-to-grann graph similarity, which is more efficient.
Proposed Model: ERIC
The proposed ERIC framework mainly consists of two submodules: the Alignment Regularization (AReg) module and the Multi-Scale GED Discriminator, as depicted in Fig. 3 AReg aims to train the shared GNN encoder to enable the GNN to capture underlying alignment information between pair-wise graphs. The multi-scale GED discriminator trains the same GNN encoder so that the learned representations of two graphs can accurately reflect the GED. Such a paradigm follows the intuition of the GED definition that when two graphs are best aligned, the difference between them is the GED.
4.1 Alignment Regularization
Learning the optimal alignment between graphs is crucial for GED estimation, however, most existing GSC models rely on intricate cross-graph node-to-node similarity computation to learn a 'soft' alignment. Furthermore, learning node-to-node similarity inevitably yields a dense similarity matrix, which could introduce more noise. To address this issue, we introduce A Alignment Regularization (AReg) as a part of our framework. AReg a model- and task-agnostic regularization term, which can easily be combined with existing embedding- based GSC models in plug-and manner. The design of AReg is motivated by analysis of GED in Section 3 Recall that GED is difference between two graphs when they are best aligned under the optimal permutation n² whose necessary conditions are that Yi 7 as well as 1h ? 2|2 take the minimum values. Thus, we expect that the learning-basse based model can couple with the nature of GED as much possible, i.c., the

---

(a) NTN
(b) & distance
(c) NTN & distance
Figure 4: t-SNE 29 visualization of the IMDB dataset. Each point is graph encoded by the GNN encoder of ERIC. The green cross means randomly sampled query graph; red points mean the top 50% of graph datasets that are most similar to the query graph based on ground-truth GEDs; blue points mean the remaining 50% graphs in the dataset. (a): Using NTN as the discriminator, many similar graphs do not cluster together around the query graph even if each cluster is tight. (b): Using l distance the discriminator, different clusters the cluster boundary; in addition each cluster is dispersive. (c): By adaptively combining NTN and lz distance, our model makes similar graphs closely located around the query, while dissimilar graphs are far away from the query.
separated clearly but the query graph is close to
GNN encoder can preserve the best alignment, in which case the difference between the learned graph representations can reflect the GED. To that end, we design the model based on the necessary conditions under æ*. Specifically, based on Eq. (3) and Eq. (4). we instantiate f-()) the L-layer Graph Isomorphism Network (GIN) 332, then at the l-th layer f6²) (A.( can be represented as:
H [ = (2) [k)) M ((1 (11+ (e- [M] [M] (,A
(5)
where ((9) is a learnable parameter, H R xxd)) is the feature matrix of G; at the (-th layer where d(() denotes the feature dimension, H X, On the other hand, AReg implements the readout function Is with one-layer permutation-invariann DeepSets 33 guarantee injectiveness, taking the form:
N Σ (A,
(6) 2 = 96 (A) = (M)
(6)
where MLP(() á and MLP(() 0 have the same output dimension d/0 dhi Since go (A,) = (ATT)
and we can remove all operation x--) in Eq. (3) and Eq. (4). DIST(,,)) can be defined as any distance metrics such as cosine similarity. Let 7 and 7 be the value of Fq. (3 and Eq. (4) at the f-th layer, by considering multi-scale cross-graph interactions, AReg is represented as LaReg where:
and 7/s and "/ are sums over all N nodes, hence they are permutation-invant
(e)
L Σ +70 + -1100~20111)
LAReg = 1
Since 7/2 and "/ induced from Eq. (2) integrate graph-level alignment and finer-grained node-level alignment, LaReg therefore preserves underlying cross-graph interactions without computing compli- cated node-to-node similarity, also making the training stage more efficient.
4.2 Multi-Scale GED Discriminator
Now we have L graph- level representations for G; and Gy respectively, denoted (Z(")
and (2 (1) 2 (1) We concatenate the layer-wise graph representations for G as: 2
+ ( // 1=1' where + denotes the concatenation operator along the last dimension to combine the
graph representation in each layer, i.e., 2, 2, E Rd and dms = E. (e) Then they are fed into a GED discriminator that generates score vectors as GED similarity embedding for the graph pair. Neural Tensor Network (NTN) (26) has demonstrated strong power model the relation between the
5

---

graph-level embeddings of two graphs 22 30 thanks to its capacity of exploring the element- dependence among the features. However, directly using NTN as the discriminator may be expensive when the dimension of Z; and Z, is high. Thus, we decompose the weight matrix W E dR X Xdms into two matrices W E RR xd' and W2 E Ie' Xdue where d' < dms to reduce the number of parameters. Then NTN with decomposed weight matrices used measure the similarity between Z, and Zj:
SNTN(G;,G)) = 6NTN (1
.m] + W: ① 23 2bb
(8)
where W1 R xd'xT W2 Fdd Rdd'ddus xT W3 E Rxx2d and b RT are learnable; T is hapareparameter controlling the output dimension, which is assigned as 16 for all datasets in our settings. [-] in Eq. (8) means computing (Z, ( 2 for all / E (1,... ,T. and stacking them as T-dimensional tensor. ONTN: 18 + IR (0.1) is fully-connected neural network with Sigmoid activation as regression function to project the similarity score vector to the final predicted similarity value. NTN is an expressive and general similarity discriminator because it can approximate many similarity measures. The first term of Eq. ( can be regarded as a multi-head weighted cosine similarity function. It can also approximate kernel similarity between Z; and Z, according to the universal approximation theorem [3). The second term captures the residual knowledge. However, is difficult for NTN to approximate high-order Minkowski distance between Z, and Zj. while diverse similarity discriminators may provide complementary information to reflect GED more accurately as shown in Fig. 4 Hence, we consider an additional similarity discriminator based on exponential p-order Minkowski distance:
(exp --11-12-2111))
= sp(Gi, G5)=,)))
exp
where 8, Rdw. - (0.1] is also a fully-connected neural network with Sigmoid activation. For simplicity, we uniformly set p 2 (i.e., & distance) for all datasets, and analyze the sensitivity of the hyper-paramette p in Section 5.4 After two similarity scores ANTN(G;, G,) and Sp Gj) are obtained, the final estimated similari score is given by:
(GG = aSNTN (G, + Bs, G3),
(10)
where a and 3 are trainable scalars denoting the weights of two similarity discriminators respectively, Given a graph database D. the GED discriminator is trained on set of n training pairs (Gi, Gj) E D x D. The predicted similarity is compared against the ground- -outh similarity Siy based on GEDs with Mean Squared Error (MSE) loss function as:
LGED n
Σ (GDDD
MSE (s(G,, C,)
(11)
Model training: Combining AReg and GED discriminator, the training stage aims to minimize the following overall objective function = LGED XCAReg. where À an adjustable hyper- parameer controlling the strength of the regularization term.
Model inference: Given set of query graphs Q and graph database D, in the testing stage, all pairs of graphs (G;, Gj) E Q x DD are fed into ERIC, and directly computing a similarity score for each pair based on Eq. (10) without any node-level interactions.
The time complexity of GIN in AReg is ((m) 31 where m is the number of edges. The gross mode-graph interactions have complexity O max NN, N2)).. The time complexity of the GED discriminator is O(dm,, Thus the complexity of ERIC is O(m + max( (axx(N,,.. N2) d')) in the training stage, while in the inference stage the complexity is O(m + dT).
Complexity:
Experiments
In this section, we empirically evaluate ERIC on the graph similarity computation task.

---

Table 1: Evaluation on benchmarks. Bold best.
0038
9110
04:3
3.010
pi221
CC
1922
Vi
24.153
5.30
0.345
03.85
115
0.287
0.251
Hangara:
25.296
0.310
0.375
0.50
0.592
20.51
0.835
0.303
0013
0.856
Seatbee
1.733
14833
8-11
0.40
2,29
D828
0.80
1437
0.33
0.12
6210
0.760
2367
0.36
0.25
0022
CJNO
G
2014
08899
0.803
0:01
0.40
0.30
0.53
0882
0906
0.55
1934
0835
0.31
0815
0.835
8353
0888
E383
EX3E:
04.88
01223
0.788
11314
08884
0.837
1066
0.88
03513
8.33
8328
0071
0.83
0.35
0.34
0.414
13IC
1.33
B679
0.716
14313
0394
11385
0/82
2337
0111
1/80
5.1
Datasets
We conduct experiments on four widely used GSC datasets including AIDS700, LINUX, IMDB M. and NC1109 (2] Following the same splits as [T3 i.c., 60%, 20%, and 20% of all graphs as training set, validation set, and query set, respectively. The training set together with the validation set are called the database. More details of the datasets are presented in Appendix B.1.
5.2 Experimental Settings
Baselines. We implement two groups of baselines for comparison: (1) Combinatorial search-based
Methods: Beam (00). Hungarian [13, and VJ [9; (2) GNN-based Methods: SimGNN [1) GMN [T6), GraphSim (3) MGMN [18), and EGSC [22.. We re-implemented all baselines with the same hyper- parameters as the original literature provides, or carefully tuned the parameters to get the optimal results when they are not provided. We give more implementation details of ERIC and baselines in Appendix B.2.
Evaluation Metric. To comprehensively evaluate model the similarity computation task, following I 22 five metrics are adopted to evaluate results for fair comparisons: Mean Squared Error (MSE) which measures the average squared differences between the predicted and the ground- truth similarity. Spearman's 's Rank Correlation Coeflicient (p) and Kendall's Rank Correlation Coefficient (r) which evaluates the ranking correlations between the predicted and the true ranking results. Precision @ k where k = 10, 20, which computes the interactions of the predicted and ground-truth top-k results divided by k. The smaller the MSE, the better performance of models; for T, and p&k, the larger the better.
5.3
Main Results
The results ERIC and the baselines on our benchmarks are reported Table [ For datasets with relatively small graphs whose ground-truth GEDs are exactly computed by the A* algorithm, ERIC consistently achieves state-of-the-arr performance across all evaluation metrics as shown in Table I For datasets with large graphs whose ground-truth GEDs computed approximately, ERIC still achieves the best results on NCI109, and comparable results on IMDB. The suboptimal performance of the methods based on node-to-node similarity (SimGNN, GraphSim, GMN, and MGMN) demonstrate that overly dense and fine-grained similarity computation may not always bring beneficial boost. EGSC also uses GIN the backbone and totally ignores cross-graph node-level interactions, and it achieves the best results on metrics p and 7 on the IMDB dataset. The reason that EGSC adopts intra-graph attention pooling and NTN in all layers to enhance the expression ability of representation vectors. However, the attention mechanism and full NTN need additional parameters which increase the burden of learning. Although EGSC proposed student model based on knowledge distillation to speed up the inference process, would sacrifice the prediction accuracy in most cases. The performance of ERIC over baselines illustrates the importance of fine- grained interactions and the proper design of such interactions.
5.4 Ablation Study
Effectiveness AReg and Multiple GED Discriminators. ERIC contains two key components: AReg and Multi-Scale GED Discriminator. To glean a deeper insight into how different components help ERIC to achieve highly competitive results, we conduct ablation experiments by removing individual components separately, Specifically, alter the loss by removing the AReg term to
7

---

Table Ablation study on the key components of ERIC on AIDS700 and LINUX.
Table 3: Transferability study of AReg on AIDS700 and LINUX.
AIDS700
LINUX
AIDS700
LINUX
mise
pe110
mse
p0010
mse
pR10
mise
pit0
ERIC
1,383
0.906
0.988
0.994
SimGNN
1.573
0.417
0.912
ERIC (wl AReg)
1.573
0.886
0.652
0.363
0.965
0.979
SinGGNNAKegg
1.439
0.858
0.506
1,974
0.945
0.658
ERIC (wlo
ERIC (wlo NTN)
1466
1,687
0.881
0.854
0.674
0.633
0.302
0.253
0.951
0.974
0.980
0.969
EGSC
1.676
0.888
0.604
0.214
0.984
0.967
RGSC
0.643
0.989
0.992
2.00
Table 4: Inference time (sec).
1,475
233
Datrect
SimfiNNN
CimphSim
GMN
MCIMN
BCSC
FRIC
1.400
3.16
AIDS700
10.773
14.043
23.975
11.337
X.765
6,662
LINUX
19.347
31.238
$2.489
22,574
21.575
18.969
IMDB
225,682
379.480
1253.551
357.903
133.437
48.750
230
NCTIOS
2913.17M
3463.620
10
3736.534
2097.405
1763,356
69
Ab
(a) AIDS700
(b) LINUX
Figure 5: Impact of different order p on
AIDS700 and LINUX datasets.
study the effect of the aross-graph node-graph interaction, with the results reported in ERIC (w/o AReg) of Table 2 We find that only using the MSE loss LGED will lead to a performance drop on the extracted three evaluation metrics, which confirms the necessity of AReg. In our design, the final similarity score is obtained by the weighted average of two similarity scores based on the NTN discriminator SNIN and the &g discriminator Sp respectively. To further investigate the impact of multiple GED discriminators, we remove one of SNIN and sp to study the effect of each discriminator. As shown in Table 2 both ERIC (w/o NTN) and ERIC (w/o E2) cause a decrease in effectiveness, which demonstrates both of them contribute to the final performance, while the model benefits more from NTN.
Transferability of AReg Further, since AReg is model-agnostic regularization term, we are interested in the transferability of AReg, so we evaluate the performance of applying AReg to other GSC models. We use SimGNN and EGSC as baselines. For SimGNN, we use AReg to replace the node-to-node similarity computation. For EGSC, we directly add AReg to the loss function. Table shows the effect of AReg on SimGNN and EGSC. As expected, the advantage of SimGNN+AReg over SimGNN shows that integrating the dense similarity matrix into the final similarity score may bring noise which affects performance. While the performance on EGSC proves that combining fine-grained similarity in a proper way, i.e., node-graph rather than node-node, can improve the model.
Sensitivity of Order p in 6, the multi-scale GED discriminator module, we adopt the exponential p-order Minkowski distance similarity measure further improve the separability of clusters in the graph embedding space. For simplicity, we directly use the 2-order Minkowski distance, i.e., l2 distance. Results in Table 2 show the effectiveness of considering the E distance, and Fig. 4 demonstrates the complementarity of different similarity measures. To investigate the sensitivity of in our model, we set p from [2, 4, 6, 8), and run 10 times for each value of p. Theee the results of mean square error with standard deviation are reported in Fig. 5] We can observe that the performance increases first and then the error becomes stable when p 2 shows that using the lg distance as the GED discriminator is suitable for our model and higher-order Minkowski distance would not improve the performance.
5.5 Inference Time
In ERIC, the cross-grapp graph alignment only acts as a regularization term in the training stage but is no longer used in the inference stage. To evaluate the efficiency, we compare the performance of ERIC with baselines in terms of inference time in Table In Table 5 of Appendix B.1 we list the number of graph pairs in the inference stage (#Testing pairs), and all experiments are implemented with single machine with I NVIDIA Quadro RTX 8000 GPU. As can be observed, node-to-node
8

---

query
runls 0.43
rank 0.43
0.46
rank 0.57
Jank 0.57
ranie 280
1,29
rank 559 2,40
rank 560
2.89
(a) The exact similarity ranking based on A
query
rank 0,24
rank 0.34
rank
0.43
rank 4
0.48
rank 0.51
rank 280
1.27
rank 559
2.51
rank 560
2,69
(b) The predicted similarity ranking based ERIC
Figure 6: Visualization of graph search examples the AIDS700 dataset. Nodes with different labels are assigned different colors. (a) and (b) are similarity rankings based on the normalized GEDs computed by A (exact) and ERIC (estimation) respectively.
1.0
0.4
0.2
(a) 0.167 (Ist)
(b) 0.571 (10th)
(c) 0.857 (50th)
(d) 1.067 (100th)
2.750 (last)
Figure 7: Heatmaps of cross-graph node-to-node cosine similarity based on the node representations
learned by the GNN encoder of ERIC. Y-axis means the node in randomly sampled query graph. (a)-(e) are ranked by the exact normalized GEDs between the query graph and graphs of particular ranks the database. For example, 0.571 (10th) means the nGED of the graph that ranks 10th in similarity to the query graph is 0.571. The color depth in the heatmap represents the similarity of the node pair; the deeper the color, the higher the similarity.
similarity computation more time-consuming on all datasets. Our proposed node-graph similarity computation does not incur substantial additional running time in practice. To summarize, ERIC is faster than all baseline models, while still achieving significantly higher accuracy on datasets.
5.6 Visualization of Graph Search
The goal of the graph search task is to find k graphs from the dataset that are most similar to the given query graph, which routine task in drug discovery [24]. In Fig. 6 we show a case based on the AIDS700 dataset, where each graph represents a functional group. Comparing the exact similarity ranking computed by A and the estimated one computed by ERIC. we see that the ranking of ERIC has high consistency with the exact ranking, which proves that ERIC is able to extract graphs that contain the similar substructure from around 700 graphs with varying size and structure and the top-ranked graph has high degree of isomorphism with the query. also demonstrates that ERIC can capture structural patterns shared across graphs. More results of visualization are provided in Appendix C.
5.7 Analysis Node-to-Node Similarity
In Fig. 7 we show the node-to-node similarity between query graph and the graphs at different ranking positions in terms of normalized GEDs. It can be found that for graph pairs with small GED, the node representations generated by ERIC show clear correspondence between nodes as shown in Fig. 7 (a). As the GED increases, the correspondence between nodes across the graph gradually weakens, i.e., cross-graph mode-to-node similarity reduces. Thus, the similarity matrices in Fig. 7 can guide to find better alignment between pair-wise graphs.

---

Related Work
The goal of graph similarity computation (GSC) is to quantify the similarity between graphs under specific similarity measure. Various similarity measures have been well studied in prior works, such as graph edit distance (GED) [ 25 20 and maximum common subgraph (MCS) [6] [0]. Among these, GED is the most popular one, and many other similarity measures can be proven to be its special cases [17]. However, computing the exact GED between two graphs is known to be NP-hard. In practice, the computation becomes challenging when the number of nodes is more than 16 [4] using exact GED solvers such as the A algorithm [25]. Thus, approximate algorithms have been proposed for GED-based GSC. These approximate methods can be broadly divided into two classes: (1) Combinatorial search-based methods, which aim to exploit combinatorial structures or theoretical bounds to approximate GED. Beam (0 is a GED estimator based on Beam Search; Hungarian [15] is proposed based on the famous Hungarian algorithm for weighted graph matching; Hausdorff approximation [1] provides lower bound for the GED approximation; VJ [9] uses the Volgenant and Jonker algorithm for GED approximation. However, these methods are highly heuristic-driven and run with either sub-exponential time or cubic time complexity, limiting the scalability as the graphs grow in size. Also, these methods totally ignore the node feature information, so that the underlying semantic similarity can not be captured. (2) Learning-
methods, which are data-driven and aim to learn graph similarity from the data itself, hopefully with higher accuracy and far lower time costs compared with search-based methods. GMN (16) introduces a cross-graphy attention layer that allows the nodes in the two graphs to interact with each other and predicts graph similarity using the representation vectors that fuse cross-graphe graph information. SimGNN I relies on shared GNN encoder, a neural tensor network, and pairwise node comparison module to compute the similarity between two graphs. GraphSim [3] extends SimGNN by using convolutional neural networks capture the multi-scale node-level interactions. EGSC 22 simplifies SimGNN by ignoring node-level interactions and uses knowledge distillation to accelerate the inference stage. MGMN 18 employs a node-graph matching network to capture cross-level features between nodes of a graph and the other whole graph, where the cross-graph aggregation weights are computed by no-e-to-node attention coefficients. Our proposed ERIC is also a learning-basee method. Unlike the above approaches that either discard node-level interactions entirely, or performs interactions between all node pairs, our method proposes novel node- oode-graph interaction paradigm that avoids dense similarity computation while preserving fine-grained interactions.
Conclusion
We propose ERIC, simple yet powerful GNN-based framework for the graph similarity computation task. Specifically, we first give a deep insight into the graph edit distance, and propose Alignment Regularization (AReg) which a separated structure independent of the end-to-end learning pipeline. AReg frees the model from complicated node-to-node interaction for similarity computation. Further, we propose a multi-scale GED discriminator to improve the discriminative ability of the learned representations. We show the effectiveness of our model through a comprehensive set of experiments and analyses.
Acknowledgments and Disclosure of Funding
This work is supported in part by Shenzhen Baisc JCYI2020010914221179
Research Fund
under grant
References
[1] Bai, Y., Ding, H., Bian, S., Chen, T., Sun, Y., and Wang, W. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings the Twelfth ACM International Conference Web Search and Data Mining, pp. 384-392, 2019.
[2] Bai, Y., Ding, H., Qiao, Y., Marinovic, A., Gu, K., Chen, T., Sun, Y., and Wang. W. Unsuper- vised inductive graph-level representation learning via graph-graph proximity, arXiv preprint arXiv:1904.010% 2019.
10

---

[3] Bai. Y., Ding, H., Gu, K., Sun, Y., and Wang, W. Learning based efficient graph similarity computation via multi-scale convolutional set matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3219-3226, 2020.
[4] Blumenthal, D. B. and Gamper, On the exact computation the graph edit distance. Puttern Recognition Letters, 134:46-57, 2020.
[5] Bunke, H. On a relation between graph edit distance and maximum common subgraph. Puttern recognition letters, 18(8):689-694, 1997.
[6] Bunke, H. and Shearer, K. A graph distance metric based on the maximal common subgraph. Puttern recognition letters, 19(3-4):255-25) 255-299, 1998.
[7] Chen, Z., Villar, S., Chen, L.,, and Bruna, J. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
[8] Doan, K. D., Manchanda, S., Mahapatra, S., and Reddy, C. K. Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. In Proceedings of the 44th International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 665-674, 2021.
[9] Fankhauser. S., Riesen, K., and Bunke, H. Speeding up graph edit distance computation through fast bipartite matching. In International Workshop on Graph-Based Representations in Pattern Recognition, pp. 102-111, Springer, 2011.
[10] Fernández, M.-L. and Valiente, G. A graph distance metric combining maximum common subgraph and minimum common supergraph. Pattern Recognition Letters, 22(6-7):753--58 2001.
[11] Fischer, A., Plamondon, R., Savaria, Y., Riesen, K., and Bunke, H. A hausdorff heuristic for efficient computation graph edit distance. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Puttern Recognition (SSPR), pp. 83-92. Springer, 2014.
[12] Hartmanis, J. Computers and intractability: a guide the theory of np-completeness (michael r. garey and david s. johnson). Siam Review, 24(1):90, 1982.
[13] Hornik, K., Stinchcombe, M., and White, H. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.
[14] Kriegel, H.-P., Pfeifle, M., and Schönauer, S. Similarity search in biological and engineering databases. IEEE Data Eng. Bull., 27(())37-44 2004.
[15] Kuhn, H. W. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83- 97, 1955.
[16] Li, Y., Gu, C., Dullien, T., Vinyals, O., and Kohli, Graph matching networks for learning the similarity of graph structured objects. In International conference on machine learning, pp. 3835-38- PMLR, 2019.
[17] Liang. Y. and Zhao, P. Similarity search in graph databases: A multi-layered indexing approach. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pp. 783-794. IEEE, 2017.
[18] Ling, X., Wu, L., Wang, S., Ma, T., Xu, F., Liu, A. X., Wu, C., and Ji, S. Multilevel graph matching networks for deep graph similarity learning. IEEE Transactions on Neural Networks and Learning Systems, 2021.
[19] Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 4602-4609, 2019.

---

[20] Neuhaus, M., Riesen, K., and Bunke, H. Fast suboptimal algorithms for the computation of graph edit distance. Join IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pp. 163-172. Springer, 2006.
[21] Ogaard, K., Roy, H., Kase, S., Nagi, R., Sambhoos, K., and Sudit, M. Discovering patterns in social networks with graph matching algorithms. In International Conference Social Computing, Behavioral Sehaviooal-Cultural Modeling. and Prediction, pp. 341-349. Springer, 2013.
[22] Qin, C., Zhao, H., Wang, L., Wang, H., Zhang, Y., and Fu, Y. Slow learning and fast infer- ence: Efficient graph similarity computation via knowledge distillation. Advances in Neural Information Processing Systems, 34, 2021.
[23] Qin, Z., Bai, Y., and Sun, Y. Ghashing: semantic graph hashing for approximate similarity search in graph databases. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2062-2072, 2020.
[24] Ranu, S., Calhoun, B. T., Singh, A. K., and Swamidass, S. J. Probabilistic substructure mining from small-molecule screens. Molecular Informatics, 3009):80--815, 2011.
[25] Riesen, K., Emmenegger, S., and Bunke, H. A novel software toolkit for graph edit distance com- putation. In International Workshop on Graph-Ban Based Representations in Pattern Recognition, pp. 142-151. Springer, 2013.
[26] Socher, R., Chen, D., Manning, C. D., and Ng. Reasoning with neural tensor networks for knowledge base completion. Advances in neural information processing systems, 26, 2013.
[27] Steinhaeuser, K. and Chawla, N. V. Community detection in large real-world social network. In Social computing, behavioral modeling, and prediction, pp. 168-175. Springer, 2008
[28] Tian, Mceachin, R. C., Santos, C., States, D. J., and Patel, J. M. Saga: subgraph matching tool for biological graphs. Bioinformatics, 23(2):232-239, 2007.
[29] Van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
[30] Wang, R., Zhang, T., Yu, T., Yan, J., and Yang, X. Combinatorial learning of graph edit distance via dynamic embedding. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5241-5255 2021.
[31] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S. Y. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1): 4-24, 2020.
[32] Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL htt/forrmmid=rryeee
[33] Zaheer, M., Kottur. S., Ravanbakhsh. S., Poczos, B.. Salakhutdinov, R. R., and Smola, A. J. Deep sets. Advances in neural information processing systems, 30, 2017.
[34] Zhuo, W. and Tan, G. Proximity enhanced graph neural networks with channel contrast. In Proceedings of the Thirly-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 2448-2455, 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [N/A]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
12

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 3
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as a URL)? [Yes] See Supple- mental Material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix B.2
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Section[5.4]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 5.5
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you's 're
using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "l7gDJrPutEF", "reviewer": "Reviewer_HgEJ", "summary": "This paper proposes a novel framework, named ERIC, for graph similarity computation. The first technical contribution is to analyze GED in embedding space and further approximate the ground-truth GEDs with $\\gamma_{i}$, $\\gamma_{j}$ and $\\||\\gamma_{i}-\\gamma_{j}\\||_{2}$. Based on the analysis, the authors introduce Alignment Regularization (AReg) into model training. In addition, the authors discuss the necessity of multi-scale GED discriminator when training GNN encoder. Overall, the graph similarity computation framework ERIC consists of AReg and Multi-Scale GED Discriminator as two submodules.", "questions": "As mentioned in **Weaknesses**, I suggest the authors to:\n1. Take more types of discriminators into account;\n2. Analyze the accuracy of this approximation method;", "limitations": "I think the applicability and practicality of the proposed method is not low, but the authors describe little about its social value and impact. Nor do they mention the limitations of the paper. It would be better to describe more about social impacts or limitations.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n1. This paper is well structured, clearly written and easy-to-follow. In section 3, the authors first theoretically investigate into GED in embedding space. The corresponding conclusion supports the justification of AReg in section 4.\n2. Approximating the ground-truth GEDs with $\\gamma_{i}$, $\\gamma_{j}$ and $\\||\\gamma_{i}-\\gamma_{j}\\||_{2}$ is novel and reasonable. This method not only reduces the computational and memory cost, but also simplifies the matching process and thus makes it easy to implement.\n3. Figure 4 provides an intuition that multiple similarity discriminators are likely to provide more useful information to reflect GED. It is a good practice.\n4. The authors conduct extensive experiments and illustrate the results clearly in the paper and the supplementary material.\n\n**Weaknesses**:\n1. The authors claim that *diverse similarity discriminators may provide complementary information to reflect GED more accurately*. However, they only discuss and use two kinds of similarity discriminators, i.e. NTN and $l_{2}$ distance, in the paper. \n2. It is pointed that minimizing $\\gamma_{i}$, $\\gamma_{j}$ and $\\||\\gamma_{i}-\\gamma_{j}\\||_{2}$ is the necessary condition of the optimal $\\pi$. But since it is not a sufficient condition, more evidence is required to make the approximation justified.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YgAlw7uGUFw", "reviewer": "Reviewer_AeTA", "summary": "This paper presents a novel way to compute graph similarity, in particular graph edit distance (GED). The key insight is a proposal of necessary conditions under optimal permutation (i.e., eq. (3) and eq. (4))) that lead to the computation of GED. Based on the insight, a neural model is introduced, critically reducing the computation burden from node-to-node similarity computation (quadratic w.r.t number of nodes) down to node-to-graph similarity computation (linear w.r.t. number of nodes). Experiments validate the effectiveness and efficiency of the proposed method.", "questions": "N/A", "limitations": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Under the proposed necessary conditions in Sec. 3, the computation of GED is reduced to node-to-graph level computation. It greatly reduces the traditional neural methods that take node-to-node level computation.\n- The model design is technically reasonable and correct.\n- Experiments are well designed and sufficiently show that the proposed methods establish new SOTA results while using significantly less running time. Ablation studies further validate the value of each component.\n- The paper is well structured and easy to follow.\n\nWeaknesses: One thing that is unclear is the motivation in Sec.3. Authors propose how they arrive at the necessary conditions for computing GED. However, the derivation involves multiple steps and is somehow conceptual, e.g., quoted from the paper: \"a necessary condition is that the distance between $f_θ(A_i [k])$ and $f_θ(\\pi^* (A_j )[k])$ is minimized for all $k \\in {1, \\ldots, N}$.\" It would be more convincing to include formally mathematical derivations to obtain these necessary conditions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3HoP5q16xYz", "reviewer": "Reviewer_z4ZB", "summary": "This paper studies the efficient graph similarity computation problem. The core is to compute graph edit distance, which is an NP-hard problem. Recent efforts resort to graph network for approximation. However, the existing node-level matching module is usually computationally expensive. This work shows that the node-level matching is not necessary. Instead, the authors propose a node-graph level correspondence as a regularization term, and inject it into the standard training framework. The experimental results show that the proposed regularization term performs competitively in both matching accuracy and inference speed. ", "questions": "-Line 40, it is stated that “since cross-graph interactions are ignored, …”. While EGSC seems have the early fusion layers which aim to learn the cross-graph interaction. Please clarify this sentence. \n\n-Line 209, $\\lambda$ is a trainable parameter. Please elaborate on how it is trained. If $\\lambda$ is prefixed, please provide the sensitivity analysis on it.\n\n-Table 4 in supplementary, it seems that the performance gain by AReg is limited. For instance, in AIDS700, ERIC (w/o AReg) on mse/$\\rho$/P@10 are already 1.573/0.886/0.652. And it already achieves the best performance in p@10 compared with other baselines. Why ERIC w/o AReg can beat other baselines like EGSC?\n\nAlso, ablation study is an important analysis, deserves to be put in the main text. I suggest the authors better organize the content to fit this part in the main paper.\n", "limitations": "The authors adequately addressed the limitations and potential negative social impact of their work. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n-This paper is mostly well written. I like the discussion in the motivation section, from which the proposed formulation is derived.\n\n-The proposed regularization term AReg, capturing the node-graph interaction between two graphs, is intuitive.\n\n-The experimental results suggest the proposed AReg outperforms other baselines in both accuracy and inference speed. \n\n\nWeakness \n\n-Some technical points are unclear in terms of presentation. (see questions)\n\n-Ablated results suggested that the proposed AReg has limited contribution to the final performance.\n\n-Missing key parameter analysis on $\\lambda$. It is unclear to me how $\\lambda$ is learned.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept