GREED: A Neural Framework for Learning Graph Distance Functions
Authors: Rishabh Ranjan
Siddharth Grover
Sourav Medya
Venkatesan Chakaravarthy
Yogish Sabharwal
Sayan Ranu
Venue: NeurIPS 2022 Accept (2022)
Keywords: edit distance
subgraph edit distance
learning graph distance
graph neural networks

Abstract: Similarity search in graph databases is one of the most fundamental operations in graph analytics. Among various distance functions, graph and subgraph edit distances (GED and SED respectively) are two of the most popular and expressive measures. Unfortunately, exact computations for both are NP-hard. To overcome this computational bottleneck, neural approaches to learn and predict edit distance in polynomial time have received much interest. While considerable progress has been made, there exist limitations that need to be addressed. First, the efficacy of an approximate distance function lies not only in its approximation accuracy, but also in the preservation of its properties. To elaborate, although GED is a metric, its neural approximations do not provide such a guarantee. This prohibits their usage in higher order tasks that rely on metric distance functions, such as clustering or indexing. Second, several existing frameworks for GED do not extend to SED due to SED being asymmetric. In this work, we design a novel siamese graph neural network called Greed, which through a carefully crafted inductive bias, learns GED and SED in a property-preserving manner. Through extensive experiments across $10$ real graph datasets containing up to $7$ million edges, we establish that Greed is not only more accurate than the state of the art, but also up to $3$ orders of magnitude faster. Even more significantly, due to preserving the triangle inequality, the generated embeddings are indexable and consequently, even in a CPU-only environment, Greed is up to $50$ times faster than GPU-powered computations of the closest baseline.

GREED: A Neural Framework for Learning Graph Distance Functions
Rishabh Ranjan, Siddharth Grover
Department of Computer Science & Engineering, IIT Delhi, India (rishabh. ranj an. cs118, siddharth, Sechharthggrover cs118)0cse iitd. acddaa..in
Sourav Medya
Venkat Chakravarthy, Yogish Sabharwal
Department of Computer Science University Illinois, Chicago, USA medyaQuic.ent
IBM Research
Delhi, India
{vechakra, ysabharwal) @in.iii.iiiinooo
Sayan Ranu
Department of Computer Science Engineering and Yardi School of Al (Jointly), IIT Delhi, India sayanranu@cse ii...ac.........................
Abstract
Among various distance functions for graphs, graph and subgraph edit distances (GED and SED respectively) two of the most popular and expressive mea- sures. Unfortunately, exact computations for both are NP-hard. To overcome this computational bottleneck, neural approaches learn and predict edit distance in polynomial time have received much interest. While considerable progress has been made, there exist limitations that need be addressed. First, the efficacy of an approximate distance function lies not only in its approximation accuracy, but also in the preservation of its properties. To elaborate, although GED is metric, its neural approximations do not provide such guarantee. This prohibits their usage higher order tasks that rely on metric distance functions, such as clustering or indexing. Second, several existing frameworks for GED do not extend to SED due to SED being asymmetric. this work, we design novel siamese graph neural network called GREED, which through a carefully crafted inductive bias, learns GED and SED
property-preservinn manner. Through extensive experiments across 10 real graph datasets containing up to 7 million edges, we establish that GREED not only more accurate than the state of the art, but also up to 3 orders magnitude faster. Even more significantly, due to preserving the triangle inequality, the generated embeddings are indexable and consequently, even in a CPU-only environment, GREED is up 50 times faster than GPU-powered baselines for graph subgraph retrieval.
Introduction and Related Work
A distance function on any dataset, including graphs, is a fundamental operator. Among several distance measures on graphs, edit distance one of the most powerful and popular mechanisms B0 [9] Edit distance can be posed in two forms: graph edit distance (GED) and subgraph edit distance (SED). Given two graphs G, and G2. GED G2) returns the minimum cost of edits needed to convert 9i to G2, i.e., for Gi to become isomorphic to G2- An edit can be the addition or deletion of edges and nodes, or the replacement of edge or node labels, with an associated cost. SED(G1, 92),
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

5: 16
0
6
3
9,
9,
9
9
Graph Mapping
CEO mell
SCD matri
Figure 1: A sample set of graphs (01-95), their corresponding GED and SED matrices and an example of a graph mapping from gi to 92- The dashed nodes and edges in the mapping represent dummy nodes and edges. The red arrows denote either insertion or change of label.
the goal is to identify the minimum cost of edits so that G1 is a subgraph (subgraph isomorphic) of G2. For examples, see Fig. |
GED is typically restricted to graph databases containing small graphs to facilitate distance computation with queries of similar sizes. As an example, given a repository of molecules, and a query molecule, we may want to identify the closest molecule in the repository that is similar to the query 36 20]. SED, on the other hand, is useful when the database has large graphs and the query is comparatively smaller graph. As examples, subgraph queries are used on knowledge graphs for analogy reasoning [T7]. In PPI and chemical compounds. SED is of central importance to identify 38
Unfortunately, both GED and SED NP-hard to compute [49] 200 To mitigate this computational bottleneck, several heuristics [10 [3
functional motifs and binding pockets [42 20 16
35 37
and index structures (20 49 30 [1] have been proposed. Recently, graph neural networks have been
shown to be effective in learning and predicting GED B3 45
29
4 [50 [46] 14] 2). The basic goal
in all these algorithms is learn a neural model from a training set of graph pairs and their distances,
such that, at inference time, given an unseen graph pair, we are able to predict its distance accurately, Other works seek incorporate non-neural graph matching solvers 40), or generic integer linear programming solvers [3 34 to learn the graph matching task from natural data such as images in an end-to-end trainable manner. Here, the NP-hardness of the problem is relegated to the non- non-neural component, and the neural part is only concerned with representation learning, unlike in our setting where we want the neural network to handle both. In the domain of subgraphs, NEUROMATCH ATCH [39 and ISONET [1] generate embeddings to detect subgraph isomorphism. Nsc 44 generates subgraph level embeddings that can count the number of subgraph instances of a query graph on target graph. While the progress made is impressive, there is scope to do more.
GED is a metric distance function. While SED is not metric due to being asymmetric, it satisfies the triangle inequality, non-negativity, and subgraph- identity (SED = 0 for subgraphs). Metrics (and triangle inequality) exhibit significant compu- tational advantages over non-metrics. Specifically, operations such as clustering [19), nearest neighbor search [13 [2], outlier detection I and diameter computation (23) admit efficient algorithms precisely when the objects being studied are embedded in a metric space. Existing neural approaches do not preserve these properties, which limits their usability for these higher
Preservation of theoretical properties:
order tasks.
Indexable embeddings: Given graph pair G1 and G2, neural approaches first embed them into a feature space. Next, they compute distance these feature vectors, which is an approximation of the distance in the original graph space. The literature on indexing range and N-NN queries over feature vectors is rich [8 25 [2]. Index structures typically allow sub-linear computation costs with respect to the database size. Unfortunately, none of the existing neural approaches generate indexable feature vectors since they perform pair-dependent computations. Specifically, the neural computations on 91 depend on both G1 and 92 (and same for G2). Consequently, the computations can only be done query-time and thereby negating the possibility of indexing pre-computed feature space embeddings.
Modeling SED: Prior this work, there have been no neural approaches for SED. Further, existing neural methods to learning GED cannot easily be adapted to learn SED. While GED is symmetric, SED is not. Several neural architectures for GED have the assumption of symmetry at its core and
hence modeling SED is non-trivial B 29
Exponential Search Space: Computing SED 92) conceptually requires us to compare the query graph Gi with the exponentially many subgraphs of the target graph G2. Therefore, it is imperative that the model has an efficient and effective mechanism to prune the search space without compromising on the prediction accuracy.

---

NODE FEATURE VECTORS
GRAPHS
EMBEDOING VECTORSS
Concstensla from al layers
EMBECOING VECTOR
#2 D i 1.8.
PREDCTIONN
layers
Post MLF
Shared Veligts
F7
+000
GNN
L %
Z
(a) Siamesc architecture of GREED
(b) The GNN component in GREED.
Figure 2: The architecture of GREED.
In this work, we address the above limitations through the following contributions.
Novel neural architecture: We address the above mentioned challenges through novel archi- tecture called GREED: GRaph Embeddings for Edit Distances. GREED utilizes a siamese graph pair-independent fashion. simple, but theo- retically well-characterized, function on this embedding space predicts the SED and GED. The carefully crafted prediction function serves as an inductive bias for the model, which, in addition to enabling high generalization accuracy, preserves the metric property of GED and the triangle inequality of SED the embedding space.
isomorphism network 47 embed graphs
Indexable embeddings: Owing to pair-inde gair-independent embeddings and preservation of the triangle inequality over the embedding space for both SED and GED, GREED can exploit the rich literature on index structures [8
25 12
to boost efficiency.
Accurate, Fast and Scalable: Extensive experiments on real graph datasets containing up to a million nodes establish that GREED is more accurate in both GED and SED when compared the state the art algorithms and is more than 3 orders of magnitude faster in range and k-NN queries. Furthermore, owing indexable embeddings, even in a CPU-only environment, GREED is up to 50 times faster than the closest baseline run on a GPU.
2 Preliminaries and Problem Formulation
We denote a labeled undirected graph as G = (V,E, where V is the node set, E is the edge set and C : V > is the labeling function over nodes and edges. > is the universe of all labels and contains a special empty label e. C(v) and C(e) denote the labels of node and edge respectively.
91 C G2 denotes that 91 is subgraph of G2-
The problem of learning GED and SED 20 is defined as follows.
Problem 1 (Learning GED/SED) Given a training set of tuples of the form (G1, G2. GED G2)) (or 91. G2. SED(GI, learn a neural model to predict GED Q2) (or SED(QI, 22) on unseen graphs Q and Q2.
For details the exact definition of GED and SED, we refer the appendix (App. A).
2.1 Properties of GED and SED
Theorem Let d: : 2 x E + R2 be distance function over E, where (i) d( L2) 0f = and (it) d(l,, (2) d(l,,l2) otherwise; the following holds: SED 92) GED(G,, G2). where GED denotes GED with d as the label set distance function. In simple words, the SED between two graphs is equivalent GED with a label distance functionn where we ignore insertion costs.
PROOF See App. B.I
Observation 1 GED satisfies the triangle inequality if the distance function d over label set E satisfies the triangle inequality (20]. As defined in the paragraph following Def. d satisfies the triangle inequality (20]. Furthermore, is trivial to see that GED is symmetric, non-negative and satisfies identity as long satisfies the analogues. Hence, GED with distance function is metric.
Theorem SED not metric due to violating the properties of symmetry and identity However, satisfies the triangle inequality, i.e., SED(G,, Ga) SED(G1, G2) + SED(G2, Gz).

---

PROOF:
See App. B.2 for details.
Observation 2 Computing GED and SED is NP-hard [49].
Hereon, we use GED as the illustrative distance function being modeled. The architecture trivially extends to SED. The specific places that need separate treatment will be discussed explicitly.
3 GREED: The Proposed Architecture
Fig. presents the architecture of GREED. The input to our learning framework is a pair of graphs Go (query), GT (target) along with the supervision data GED(GO, GT) (or SED(GQ, GT)). Our objective train a model that can predict GED on unseen query and target graphs. The design of model must be cognizant of the fact that computing GED is NP-hard and high quality training data is scarce. Thus, we use a Siamese architecture [T], where there are two networks with shared parameters applied to two inputs independently to compute representations.
3.1 Siamese Graph Neural Network
As depicted in Fig. 2a we use a siamese graph neural network (GNN) with shared parameters to embed both So and GT- While one could use two different GNN models for the query and the target, this design increases the model parameters and consequently. the training time. Furthermore, an architecture with higher number of parameters also requires larger amount of training data, which is difficult due to GED being NP-hard.
Fig. 2b focuses on the GNN component of GREED. We next discuss each of its individual components.
Pre-MLP: x,, in Fig. 2b one-hot encoding of the categorical node labels. The dimension of the one-hot vector increases linearly with the number of labels in graph database and hence can be very large. The primary-job of the pre-mlp is to reduce to a desirable dimension size through the operation ف MI.P (x.). Indeed, similar effect may also be obtained by directly feeding the one- hot encoding to the first layer of GIN. However, since a GIN constructs embeddings by incorporating both structure and label information, one may desire different dimensionality in the GIN layers. Hence, the pre-mlp is motivated more from a conceptual separation of its task to that of GIN rather than purely performance point of view (See App. G). We do not explicitly model edge labels in our experiments. GREED can easily be extended to edge labels by using GINE [2 instead of GIN.
Graph Isomorphism Network (GIN); GIN 447 consumes the information from the Pre-MLP to learn hidden representations that encode both the graph structure as well as the node feature information. GIN is as powerful as the Weisfeiler-I (WI.) graph isomorphism test (26) in distinguishing graph structures. Since our goal to accurately characterize graph topology and learn similarity, GIN emerges the natural choice. GIN develops its expressive power by using injective aggregation function. Specifically, in the initial layer, each node v in graph G is characterized by the representation learned by the MLP, i... h ug. Subsequently, in each hidden layer we learn an embedding through the following transformation.
h MLP (1 (1+6)-
Σ MEND(e)
(1)
Here, el is a layer-specific learnable parameter, (g( is one-hop neighbourhood of the node v, and g = u. The k-th layer embedding is h where is final hidden layer.
Concatenation, Pool and Post-MLP: Intuitively, h captures feature-space representation of the i-hop neighborhood of v. Typically, GNNS operate on node or edge level predictive tasks, such as node classification or link prediction, and hence, the node representations are passed through an MLP for the final prediction task. our problem, we need to capture graph level representation. Furthermore, the representation should be rich enough to also capture the various subgraphs within the input graph so that SED can be predicted accurately. To fulfil these requirements, we first concatenate the representation of node across all hidden layers, i.e., the final node embedding is 인 CONCAT (h Vi E 21, ..... ... ..f).. This allows us to capture multi-granuie the subgraphs centered on at different radii in the range [1, k). Next, to construct the graph-level representation, we perform a sum-pool, which adds the node representations to give a single vector. This information is then fed to the Post-MLP to enable post-proc.ssing Mathematically:
view of

---

Zg MLP(2 MLP Σ z
NEV
GED and SED Prediction: The final task is predict the GED (and SED) as function of query graph embedding Zoo and target graph embedding ZG. The natural choice would be to feed these embeddings into another MLP learn GED(Zgo ZØg): This MLP then be trained jointly with the graph embedding model in an end-to-end fashion. However, an MLP prediction does not have any theoretical guarantees with respect to the preservation of metric properties of GED and the triangle inequality of SED. We, therefore, focus on learning prediction functions Fg (Zge Zgr) and F, (Zea: Zgz) for GED and ŠED respectively, such that they are accurate and respects the desirable properties from the original graph space. As we will empirically substantiate in $ $4.55 the inductive bias injected through the prediction functions also lead to more effective learning over low volumes of training data than an MLP.
3.1.1 GED
We require the following four properties to ensure that the prediction is also metric.
Fg (Z Zer) 2 0
(3)
Fg (ZGo ZoT) 0) > Vi Zoa Z
(4)
Fg (Zoo: Zor = F, (ZGr Zgo)
(5)
Fg (Zgo Zgr S Fg (Zgo, Zgy) Fg (Zg' Zgg)
(6)
To achieve this, we establish an important connection of metrics on vector spaces to norms. Every
norm ||-I| gives metric (x,y) ||x yll- Moreover for metric, there exists norm ||-I| such
that the metric can be expressed as (x. y + ||x yll. iff the metric is translation invariant and homogeneous. Thus, we add these properties the desiderata for Fgi
Fg (Zga + k, ZGT + k) = Fg (Zoo Z0r) Vk E Rdd Fg (rZ r .ZrTZar |r|F, (Zge Zαr) ) Vr E R
(8)
Armed with these observations, we define the class of functions that may be used for Fg.
Observation 3 Fg may be defined any function (z,3) + || yll for some norm ||-I| over the vector space Rd such that Fg satisfies Eqs.
The Lp norm satisfics Obs. Hence, we define F, as:
Fg (Zga Zgy)
Zgo Zg lp
(9)
In our implementation we use the L2 norm. Finally, the parameters of the entire model are learned by minimizing the mean squared error (here T is the training set).
L
1
Σ
(F, (Zgo Z GED 9T)
(10)
VIGETTTEET
Intuition: Regardless of the graph representations generated by our model, F, ensures that the predicted distance is a metric. One the other hand, by training the model to produce embeddings ZGz and ZG, such that F, (Zoo ZGr) R GED (Zig Zgy), we enforce rich structure on embedding space such that Fg is also accurate. Thus, F injects an inductive bias satisfying the dual needs of accuracy and preservation of original space properties.
3.1.2 SED
SED satisfies non non-negate -egaaviivvy and triangle inequality. Following a similar reasoning as above, we define F. as follows:
F. (Zea. Zor) ||ReLU Zor 1l2 = ||max (0, Zoo
Zoy H|l
(11)
Intuitively, for those co-ordinates where the value of Zg is greater than ZG, a distance penalty is accounted by F, in terms of how much those values differ; otherwise F. considers 0. This follows the intuition that the SED accounts for those features of Go that are not 9r. Moreover, consistent with SED, the additional features in GT that not in Go. do not incur any cost.
5

---

Lemma 1 The following properties hold on predicted SED.
F. (Zeo Z
2. F. (Zga: Zgr = 0 - Lgo S Zog
F. (Zgo ZØn) S (Z Z0,,) + Fo Zer)
PROOF. Properties (1) and (2) follow from the definition of F itself. Property (3) follows from the fact that take the L2 norm. Formally, we state follows.
Lemma F. (Z Zg,) - Fo (Zgo zg, ) (Zg, Zgg) where Fx =|ReLU(x-)) for any monotonic norm ||-1|-
PROOF See App. B.4
3.2 Characterization of GREED
Importance of pair-independence and siamese architecture: A pair-independent siamese archi- tecture enables theoretical guarantees for GREED by constraining the model to learn a single mapping from graph space to embedding space for both query and target. Despite these restrictions, GREED outperforms prior works which freely use cross-graph information and don't t provide theoretical guarantees. This further confirms that the siamese architecture Complexity Analysis: The complexity of GED and SED inference in GREED is linear in the number of nodes and edges in the query and target graphs (See App. C for derivation). This computation cost is drastically lower than the factorial computation cost of optimal GED and SED. With respect to neural methods for graph similarity i.e. ((D))).
useful prior.
45 50
all have least quadratic computation cost,
Since the generated embeddings for both GED and SED satisfy triangle inequality, they are indexable leading to fast querying times. We develop index structure to exploit this property. Due to space limitations, the details are included in App. D In addition, we also design neighborhood decomposition scheme, which enables fast pruning of the exponential search we empirically analyze the impact of index structures on querying time.
Indexing Embeddings:
space D.4 In
4.3
Empirical Evaluation
In this section, we establish the following:
Efficacy: GREED more accurate than the state of the art approaches for both GED and SED, Efficiency: GREED is orders of magnitude faster than existing approaches and scales well to graphs with millions of nodes.
Scalability: Pair-inder independence and indexability further enhances the scalability of GREED and enables it to be run on CPU-only platforms.
Our code base and datasets are available at httpss//gthha..co//iaaaaiiiiaag
4.1 Experimental Setup
We use machine with an Intel Xeon Gold 6142 processor and GeForce GTX 1080 Ti GPU for all our experiments.
Datasets: Table A the datasets used for benchmarking. Further details on the dataset semantics are provided in the App. We include a mixture both graph databases (#graphs >1), as well as single large graphs (#graphs = 1). Linux and IMDB are unlabeled. We note that this is the first study to evaluate neural graph distance approaches on million-scale graphs.
Baselines: To evaluate performance in GED, M and GOrSIM [4]. These are the most recent neural frameworks and have shown better efficacy than other neural approaches such as SIMGNN B3, GRAPHSIM 4 and GMN 29
compare with SIMGNN 3 GENN-A* 45).
For SED, no neural approaches exist. However, M and SIMGNN can be trained by replacing GED with SED along with minor modifications in training. Nsc B1 is method for counting subgraphs using graph embeddings. Since this is a related operation, we use NsC as a baseline by changing the loss function minimize the RMSE between true and predicted SED. We also use NEUROM ATCH [39] as a baseline, which was originally designed to detect subgraph isomorphism. While NEUROMATCH cannot predict SED, it generates violation score, which can be interpreted as

---

Methods
AID8
IMDB
Methods
Dblp
Anazon
Publled
CiteSeer
Cora_XL
Protein
AIDS
GREED
0.796
0.415
6.734
GREED
0.964
0.495
0.728
0,519
0.635
0.524
0.512
GENN-A"
GOISIM
SIMGNN
HPMN
0.977
0.956
0.994
1,037
0.734
0.666
0.267
0.574
66.250
37.831
86.077
NA
SIMGNN
H-MN
Nsc
1,470
1.422
NA
2.141
2,810
1.294
1.213
1.095
1.322
1.502
1.781
1.66
1.446
1.661
1.289
0.941
0.662
1.223
0.696
0.749
0.562
Branch
3.322
2,474
6,875
Branch
2.917
4.513
2.613
3.161
3,102
2.391
1.379
MIP-F2
2,929
1,245
82.124
MTP-F2
3,477
5.595
3.399
4.474
3.871
2.249
1.537
(a) Prediction of GED
(b) Prediction of SED.
Table 1: (a) Datasets. (b-c) RMSE scores (lower is better) in (a) GED and (b) SED. GENN-A" does not scale on graphs beyond 10 nodes and hence results in IMDB are not reported. Nsc does not scale in Dblp due memory consumption.
the likelihood of the query being subgraph isomorphic to the target. The violation score can be used as a proxy for SED and used in ranking of k-NN (K-NearestNeighborr) queries. Thus, NEUROM ATCI comparisons are limited to k-NN queries SED. GMN (29], GRAPHSIM 44. GOTSIM [1]] and GENN-A* are not included since they cannot be easily adapted for SED. See App. for details.
In the non-neural category, we use mixed integer programming based method MIP-F2 (27] with a time bound of 0.1 seconds per pair for both GED and SED. MIP-F2 provides the optimal solution given infinite time. We also compare with BRANCH [5]. which achieves an excellent trade-off between accuracy and time (]. BRANCH uses linear sum assignment problem with error-correction (LSAPE) to process the search space. We use GEDLIB'S 7 implementation of these methods. Training (and Test) Data Generation: For GED, we use (query, target) graph pairs from IMDB, AIDS', and Linux. Our setup is identical to SIMGNN 3 and MºMN [50]
For SED, the target graphs are taken from datasets listed in Table For the query graph, in AIDS, we use known functional groups (38]. In the rest of the graph datasets, queries are sampled by performing a random BFS traversal (depth up 5). Table A shows the average query sizes (Vol.
(E D.We use mixed integer programming method F2 [27 implemented in GEDLIB with large time limit to generate ground-truth data.
Train-Validation Validation-Test We use 100K query-target pairs for training and 10K pairs each for vali- dation and test. All models are trained till validation loss is minimized or there is less than 0.05% change in validation loss over number of extended epochs. For GREED, we set the number of layers in GIN to 8. The hidden layer dimension is set 64. For all baselines, we use the default parameters suggested by the authors.
4.2 Prediction Accuracy of SED and GED
Tables La and Tb present the accuracy of all techniques on GED and SED in terms of Root Mean Square Error (RMSE). GREED outperforms all other techniques in 9 out of 10 settings across GED and SED. While M and Nsc are the second best performers in SED, GENN-A performs well in GED. GENN-A*, however, is extremely slow and does not scale on graphs of size beyond 10. H thus, provides the second best balance between efficacy and efficiency after GREED. The gap in accuracy is the highest in IMDB for GED, where GREED is more than 10 times better than the neural baselines. IMDB graphs are significantly denser and larger than AIDS' or Linux. Thus, computing the optimal GED is harder. While all techniques have higher errors in IMDB, the deterioration is more severe the baselines indicating that GREED scales better with graph sizes.
Impact of Query Size: We next investigate how the accuracy varies against the query size. Intuitively, the task gets harder with query size since the combinatorial space of possible maps increases exponentially. For this analysis, we compare GREED with M'MN in IMDB and Dblp for GED and SED respectively. GENN-A" fails to scale on both datasets.
In Fig. 3 we plot the heat map of RMSE against query graph size. In this plot, each dot corresponds to query graph GQ. The co-ordinate of query is (GED(Go, GT). (Vel) (analogously defined for SED). The color of dot represents the RMSE: the darker the color, the higher is the RMSE. When we compare the heat maps of GREED with M we observe that M is noticeably darker. Furthermore, the concentration of dark colors is noticeably higher on the upper-right corner indicating deterioration with larger query sizes and higher distance values. This indicates that GREED scales better with query sizes and distances.
7

---

25
Qunry Stow
20
20
Quary
SED
(a) GREED, IMDB (b) H IMDB (c) GREED, Dblp (d) H Dblp
Figure 3: Heat Map of RMSE in (a-b) GED and (c-d) SED against query size in IMDB and Dblp.
Methods
AIDS
Linux
IMDB
Publeed
CiceScer
Cora_HL
Procein
A1DS
GREED
0.80
0.89
0.87
GaRED
MºMN
0.74
0.88
0.80
01.88
0.88
0.74
0.78
0.72
GENN-A
0.75
0.90
NA
0.57
1136
0.63
0.73
SIMGNN
0.72
0.86
0.67
NEUROMATCH
0.70
0.77
0.73
0.57
(a) Ranking in GED.
(b) Ranking SED.
Table 2: Kendall's tau scores (higher is better).
Visualization: A case study to visually illustrate the efficacy of GREED is provided in App.
Range and k-NN queries: To quantify performance range and k-NN queries, we measure F1- score (Range query) and Kendalls's 's tau (k-NN) [24] of the predicted answer set, when compared against the ground truth. In Figs. 4h, we measure the performance in range queries. In SED, GREED consistently outperforms all baselines in Fl-score. In GED, the trend remains similar. Although, GENN-A* outperforms GREED for a brief region in Linux, overall, GREED has the highest F1-score. We also note the GENN-A" is not included in Fig. 4h since it fails scale IMDB. In k-NN queries (Tables and GREED outperforms all algorithms in SED. GED, similar to the trend in range queries, GREED is the dominant method and GENN-A marginally outperforms GREED in Linux.
4.3 Efficiency
Tables 3a 3b present the inference times per 10K query-target pairs. In this experiment, do not index embeddings by GREED so that the comparison unearths the raw difference in computation efficiency of solely the neural architectures. As visible, GREED is up 1800 times faster than the non-neural baselines and up to 10 to 20 times faster than H2 MN, the current state of the art in GED prediction. Also note that GENN-A" is exorbitantly slow (Table 3a). GENN-A" is slower since it only predicts the GED but also the alignment via an A search. While the alignment information is indeed useful, computing this information across all graphs in the database may generate redundant information since an user is typically interested only on small minority of graphs that are in the answer set. In App. H we discuss this issue in detail.
4.4 Pair-independence and Indexability
Here, we showcase how pair-independent embeddings, and ensuring triangle inequality leads to further boost in scalability. For this experiment, and Dblp. For each dataset, we pre-compute GREED embeddings of all database graphs by exploiting pair-independent embeddings. Such pre-computation not possible in the neural or non-neural baselines. Furthermore, since the predictions of GREED satisfy triangle inequality, we index the pre-computed embeddings of the database graphs discussed in $ $D.I Consequently, for GREED, we only need to embed the query graph and evaluate F to make predictions at query time. Table 3c presents the results on range and 10-NN queries. When computations are done on GPU, GREED more than 1000 times faster than MN. In the absence of GPU, H is practically infeasible since expensive pair-dependent computations are done at query time. In contrast, even on a CPU, through indexing, GREED is R 50 times faster than GPU-based H2 MN. Note that indexing enables up to 3-times speed-up on GREED over línear sean, which demonstrates the gain from ensuring triangle inequality. These results establish that GREED breaks new ground in scalability of neural
the three largest datasets of PubMed, Amazon

---

100
1.0
97.5
80
80
70
10
20
10 Range(%)
30
20
30
20
18
20
Range(8)
Renge(3))
Range(36)
Range(%)
(a) PubMed
(b) CiteSeer (c) Cora_ML (d) Protein
(e) AIDS
Croud Art Gread
1.
10
L.
Cored
BengeOS)
Rangecho
Rangec'i
Triining hers
Trxining Pwirs
Triiiig Pairs
AIDS'
Linux
IMDB
(i) Dblp
(i) PubMed
(k) CiteSeer
Figure 4: F1-score in range queries on SED (a-e) and GED (f-h). The range threshold is set percentage the max distance observed in the test set. The legend for Figs. (a)-(e) is provided in (a) and for (f-h) provided in (h). (i-k) Ablation study analyze the impact siamese architecture and function F. The legend for Figs. (i)-(k) is provided in (i).
Methods
AIDS'
Methods
Dblp
faazon
Publed
Citeßeer
Cora,NL
Protein
AIDS
GREED
0.49
0.70
0.63
GENN-A"
HºMN
12190
9.50
1340
8.74
8,83
NA
SIMGNN
H'MN
Nsc
44.68
NA
23.2
25.79
35.05
24.16
27.54
70.59
29.04
39.02
19:33
21
9.63
BRANCH
10.70
8.24
127.90
BRANCH
626.489
79:25
99.11
155.09
132.98
52.26
12:93
MIP-F2
593.34
191.88
1173.548
MIP-F2
1979.185
861.95
606.01
827.65
790.01
881.77
360.12
(a) GED
(b) SED
Datasets
Range (9
10-NN
CPU
GPU
CPU
GPU
H2MN
Indexed
H2MN
PubWed
0.693
0.56
0.004
26.6
1.01
0.49
0.004
27.5
Anazon
372
Dblp
48
20.9
0,070
696
50.4
18.6
0.126
698
(c) Scalability
Table 3: (a-b) Running times of all methods in seconds per 10k query-target pair. (c) Querying time (s) for SED in the three largest datasets. L-Scan indicates time taken by linear scan in GREED (times differ based on whether executed on CPU or GPU).
graph distance computations; only is faster, it overcomes the barrier of GPU-dependence and hence better suited for low-resource environments.
Ablation Study
In this study, we explore the impact of our inductive biases in learning from low-volume data. We create two variants of GREED: (1) GREED-Dual trains the parallel GNN models separately without weight-sharing. and (2) GREED-NN uses an MI. instead of F. Both have strictly better representational capacity than GREED, so are expected match the performance with infinite data. Figs. 4k present the results on SED. The results of the same experiment on GED is provided in Figs. the appendix. The RMSE of GREED is generally better than GREED-Dual, with the dif- ference being more significant at low volumes. This indicates that siamese structure helps. Compared GrEEd, GREED-NN achieves marginally better performance at larger train sizes PubMed and CiteSeer. However, in Dblp, GREED is consistently better. The number of subgraphs in a dataset grows exponentially with the node set size. Hence, an MLP needs growing training data accurately model the intricacies of this search space. In Dblp. even 100k pairs is not enough to improve upon F. Furthermore, since computing GED and SED NP-hard, generating large volumes training data not desirable. Overall, these trends indicate that F enables better generalization and scalability with

---

respect to accuracy. Furthermore, given that its performance is close to an MLP even on high- high-volume training data, and enables indexing, the benefits outweigh the marginal reduction in accuracy.
We also observe that generally, GREED-NN performs better than GREED-dual. GREED-NN retains the inductive bias imparted by the Siamese architecture, but ablates the inductive bias of the custom prediction function. The opposite happens in the case of GREED-Dual The observed phenomenon of GREED-NN generally out-performing GREED-Dual can be interpreted as evidence for the Siamese architecture providing stronger inductive bias than the custom prediction function.
More ablations studies justifying our choice of GIN and the sum-pool layer are provided in App. G
4.6 Generalization to Unseen Query Distributions in SED
We train the model by sampling queries from the graph database through BFS enumerations. How does GREED generalize to unseen distributions? Towards that end, we generate queries from the three unseen distributions of (1) Random Walks (w), (2) Random Walks with Restarts (RwR), and (3) SHAADOW 48 (See App. for details on the sampling strategies). We first note that in AIDS, we use real queries of functional groups, and thus the good performance in AIDS indicates good generalizability. In Table 4al we more exhaustively analyze this aspect. As visible, the errors remain low. Even more surprisingly. the errors on Rw and RWR are better than the train distribution of BFS itself. This indicates good generalization to unseen distributions.
4.7 Generalizability to Unseen, Larger Query Sizes:
Generating training data for learning GED and SED is expensive since optimal distance computations are NP-hard. Hence, a desirable property would be to learn from small graphs and then generalize to larger unseen graphs. We evaluate this ability for GREED and H Table 4b provides the numbers. We notice that although there some deterioration in the quality for query sizes in the range [25, 50] when compared to the entire set, is not severe (GREED-50 in Table 4b). However, if the train set only contains queries till size 25 and we deploy the learned model to infer on queries of larger unseen sizes, the drop in quality is significant (GREED-25 25 in Table 4b). This drop is more dramatic in HºMN. On the positive side, GREED remains superior to the optimal non-neural approach (MIP-F2) when run with generous time limit of 60 seconds per query. Overall, this experiment highlights one direction that needs further study and improvement.
Conclusions, Limitation, and Future Directions
The problem of learning graph distances from their embeddings has seen much interest over the last few years. This thread of research is important since it allows us to overcome the bottleneck of exponential graph alignment space. Our experiments clearly establish GREED as the state of the art for both GED and SED (See App-KKoor for preliminary results on maximum common subgraph similarity). In addition, it is significantly faster and provides better theoretical correspondence between properties of the original space and predicted space. One clear direction of future work that emerges from our experiments is that GREED, and existing methods of graph distance learning, do not generalize well to unseen larger query sizes. We hope to address this limitation next.
Sampler
PubKed
CiteeSer
Amazon
Pobiieed
CitaGeer
Ámazon
Vig 50
Viy '25, 255,40
Vig [0.500]
Vig E [25,
Vig
Vig []]
BFS
0.728
0.519
0.495
GRamD-50
1,294
1.917
0.728
0.948
0.638
D.782
Rw
0.508
0.770
0.490
GREED-22
2,824
4.999
4.240
9,052
1.152
1,234
RwR 0.545
0.754
0.299
BFMN-55
3.133
5.112
3.583
6,014
9,500
SHADOW
0.966
0.733
0.830
WMMN-25
MIP-F2
7.417
3,507
6.778
10.459
4,831
8.505
5.720
0.454
(a) Query distributions
(b) Query size
Table 4: (a) RMSE on unseen query distributions. BFS (seen) is the baseline to compare against. (b) RMSE against query sizes. GREED-50 indicates GREED trained dataset containing queries of size up to 50. GREED-25 is defined analogously.
10

---

References
[1] Fabrizio Angiulli and Clara Pizzuti. Fast outlier detection in high dimensional spaces. In Tapio Elomaa, Heikki Mannila, and Hannu Toivonen, editors, Principles of Data Mining and Knowledge Discovery, pages 15-27, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.
[2] Jiyang Bai and Peixiang Zhao. Tagsim: Type-aware graph similarity learning and computation. Proc. VLDB Endow., 15(2):335-347, 2021.
[3] Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach fast graph similarity computation. In wSDM, WSDM '19 page 384-392, 2019.
[4] Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning-based efficient graph similarity computation via multi-scale convolutional set matching, AAAI, pages 3219-3226, Apr. 2020.
[5] David Blumenthal. New techniques for graph edit distance computation. arXiv preprint urXiv:/900 /908.00265, 2019.
[6] David Blumenthal, Nicolas Boria, Johann Gamper, Sébastien Bougleux, and Luc Brun. Comparing heuristics for graph edit distance computation. The VLDB Journal, 29(1):11--453 2020.
[7] David B Blumenthal, Sébastien Bougleux, Johann Gamper, and Luc Brun. Gedlib: a c++ library for graph edit distance computation. International Workshop on Graph-Base Representations in Pattern Recognition, pages 14-24. Springer, 2019.
[8] Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian emhedding of graphs: Unsu- pervised inductive learning via ranking, arXiv preprint arXiv:1707.0388 2017.
[9] Angela Bonifati, Wim Martens, and Thomas Timm. An analytical study of large spargl query logs. Proc. VLDB Endow, 11(2):149-16) 2017.
[10] Sébastien Bougleux, Luc Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Gaüzzèee, and Mario Vento. Graph edit distance as a quadratic assignment problem. Pattern Recognition Letters, 87:38-46, 46, 2017. Advances in Graph-based Pattern Recognition.
[11] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using a" siamese" time delay neural network. Advances in neural information processing systems, 6:737-744, 1993.
[12] Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB, 1997.
[13] Évariste Daller, Sébastien Bougleux, Benoit Gaüzère, and Luc Brun. Approximate Graph Edit Distance by Several Local Searches in Parallel. In 7th International Conference on Pattern Recognition Applications and Methods, 2018.
[14] Khoa Doan, Saurav Manchanda, Suchismit Mahapatra, and Chandan K. Reddy. Interpretable graph similarity computation via diffcrentiable optimal alignment of node embeddings. In SIGIR, page 665-674, 2021.
[15] Vlastislav Dohnal, Claudio Gennaro, Pasquale Savino, and Pavel Zezula. D-index: Distance searching index for metric data sets. Multim. Tools Appl., 21(1):9-33. 2003.
[16] Chi Thang Duong, Trung Dung Hoang, Hongzhi Yin, Matthias Weidlich, Quoc Viet Hung Nguyen, and Karl Aberer. Efficient streaming subgraph isomorphism with graph neural networks. 14(5):730-742, January 2021.
[17] Christopher L. Ebsch, Joseph A. Cottam, Natalie C. Heller, Rahul D. Deshmukh, and George Chin. Using graph edit distance for noisy subgraph matching of semantic property graphs. In 2020 IEEE International Conference on Big Data (Big Data), pages 2520-2525, 2020.
11

---

[18] Charles Elkan. Using the triangle inequality to accelerate k-means. In ICML, page 147-153, 2003.
[19] Ali S. Hadi. Finding groups in data: An introduction to cluster analysis. Technometries, 34:111-112, 1991.
[20] Huahai He and Ambuj K Singh. Closure-tree: An index structure for graph queries. In ICDE, pages 38 38-38. IEEE, 2006.
[21] Gisli R. Hjaltason and Hanan Samet. Index-driven similarity search in metric spaces (survey article). ACM Trans. Database Syst., 28(4)5 2003.
[22] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint 1905. 12265, 2019.
[23] Piotr Indyk. Sublinear time algorithms for metric space problems. In Proceedings of the Thirty-Fire First Annual ACM Symposium on Theory of Computing, STOC '99, page 428 434, New York, NY, USA, 1999. Association for Computing Machinery.
[24] M. G. Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81-93, 1938.
[25] Wojciech Kwedlo and Pawel J. Czochanski. A hybrid mpi/openmp parallelization of $KS -means algorithms accelerated using the triangle inequality. IEEE Access, 0--280-442297 2019.
[26] AA Leman and B Weisfeiler. reduction of graph to a canonical form and an algehra arising during this reduction. Chuchno-Tcchhnicheskkaa Informatsiya, 12-1:22-1,, 1968.
[27] Julien Lerouge, Zeina Abu-Aisheh, Romain Raveaux, Pierre Héroux, and Sébastien Adam. New binary linear programming formulation to compute the graph edit distance. Pattern Recognition, 72:254-265, 265, 2017.
[28] Jure Leskovec and Rok Sosič. Snap: A gencral-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1, 2016.
[29] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In ICMI., pages 1835-3845, 2019.
[30] Yongjiang Liang and Peixiang Zhao. Similarity search in graph databases: A multi-layered indexing approach. In ICDE, pages 783-794, 2017.
[31] Xin Liu, Haojie Pan, Mutian He, Yangqiu Song, Xin Jiang, and Lifeng Shang. Neural subgraph isomorphism counting. KDD, page 1959-1969, 2020.
[32] Christopher Morris, Nils M. Kriege. Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML workshop on Graph Representation Learning and Beyond, 2020.
[33] Yatin Nandwani, Rishabh Ranjan, Mausam, and Parag Singla. A solver-free framework for scalable learning in neural ILP architectures. In Advances in Neural Information Processing Systems, volume 35, 2022.
[34] Anselm Paulus, Michal Rolínek, Vit Musil, Brandon Amos, and Georg Martius. Comboptnet: Fit the right np-hard problem by learning integer programming constraints. In International Conference on Machine Learning, pages 1443-8453. PMLR, 2021.
[35] Sayan Ranu, Bradley T Calhoun, Ambuj K Singh, and S Joshua Swamidass. Probabilistic substructure mining from small-molccule screens. Molecular Informatics, 30(9):809-88) 815, 201
[36] Sayan Ranu, Minh Hoang, and Ambuj Singh. Answering top-k representative queries on graph databases. Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 1163-1174, 2014.
12

---

[37] Sayan Ranu and Ambuj K Singh. Graphsig: A scalable approach to mining significant subgraphs in large graph databases. In 2009 IEEE 25th International Conference on Data Engineering. pages 844-855 IEFE, 2009.
[38] Sayan Ranu and Ambuj K Singh. Mining statistically significant molecular substructures for efficient molecular classification. Journal of chemical information and modeling, 49(1 19))5335 2550, 2009.
[39] Rex, Ying, Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, and Jure Leskovec. Neural subgraph matching, 2020.
[40] Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vit Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In European Conference on Computer Vision, pages 407-424 Springer, 2020.
[41] Indradyumna Roy. Venkata Sai Baba Reddy Velugoti, Soumen Chakrabarti, and Abir De. Inter- pretable neural subgraph matching for graph retrieval. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 11--13, 2022.
[42] Aravind Sankar, Sayan Ranu, and Karthik Raman. Predicting novel metabolic pathways through subgraph mining. Bioinformatics, 33(24))395533663 2017.
[43] Jeffrey K. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Inf. Process. Lett. 40:175-179, 1991.
[44] Lichen Wang, Bo Zong, Qianqian Ma, Wei Cheng, Jingchao Ni, Wenchao Yu, Yanchi Liu, Dongjin Song, Haifeng Chen, and Yun Fu. Inductive and unsupervised representation learning on graph structured objects. In ICLR, 2020.
[45] Runzhong Wang, Tianqi Zhang, Tianshu Yu, Junchi Yan, and Xiaokang Yang. Combinatorial learning of graph edit distance via dynamic embedding. In CVPR, pages 5241-5250, 2021.
[46] Haibo Xiu, Xiao Yan, Xiaoqiang Wang, James Cheng, and Lei Cao. Hicrarchical graph matching network for graph similarity computation, 2020.
[47] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprini arXiv: 100i::/810.00000 810.00886, 2018.
[48] Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor K. Prasanna, Long Jin, and Ren Chen. Deep graph neural networks with shallow subgraph samplers. In NeurlPS, 2021.
[49] Zhiping Zeng, Anthony K. H. Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou, Comparing stars: On approximating graph edit distance. Proc. VLDB Endow. 2(1):25-36, 2009.
[50] Zhen Zhang, Jiajun Bu, Martin Ester, Zhao Li, Chengwei Yao, Zhi Yu, and Can Wang. H2mn: Graph similarity learning with hierarchical hypergraph matching networks. In KDD, page 2274-2284. 2021.
[51] Xiang Zhao, Chuan Xiao, Xuemin Lin. Qing Liu, and Wenjie Zhang. partition-based approach to structure similarity search. VLDB, 7(3):169-18)) 2013.
13


Reviews:
[{"review_id": "jX8ADOCPjD", "reviewer": "Reviewer_r5mu", "summary": "Graph and subgraph edit distance (GED and SED) are important mechanisms to measure the distance between graph pairs. However, it is NP-hard and thus hard for scalability. This paper proposes a framework based on the graph neural networks, named GREED, to learn the graph embedding for the edit distances. \n\nUnlike the previous methods, GREED is able to preserve the essential theoretical properties (e.g., triangle inequality, non-negativity, etc.) of the MED as the metric distance function, and also can easily be adapted to SED. Therefore, the embeddings learned from the GREED are indexable, significantly improving query time. \n\nComprehensive experiments are conducted to validate the proposed method. GREED outperforms state-of-art methods across ten real-world datasets up to millions of edges and is faster than other methods. \n", "questions": "The following questions are mainly related to section 4.5:\n1. It seems that all the ablation studies are related to the SED based on the caption of Fig. 3, do you have any experiments with the GED? Those experiments can also help to test the consistency of the results. \n2. From Fig. 3(i)-(k), we can observe that the blue line (Greed-NN) has a better performance on PubMed and CiteSeer datasets. What is the possible reason for it?\n3. Does the Pre MLP matter since you use the one-hot encoding? Meanwhile, a bit larger problem is whether all the component in Figure 2(b) is necessary. In other words, can we directly use GIN (or other GCNs) to replace Figure 2(b)?\n\n\n", "limitations": "In the paper, the authors have explicitly or implicitly pointed out a couple of limitations: (1) not considering the edge labels; (2) not having well generalizability. \nFor limitation (1), I encourage the authors to explore and take advantage of some edge-related GCN models. For limitation (2), I suggest the author do more analysis of the dataset properties to find the reason for the poor generalizability. For example, is it caused by the structure domain shift (e.g., small world, scale-free property, and so on) or feature difference?\n\nTo best of my knowledge, there is no potential negative societal impact.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nFirst of all, the paper illustrates the motivation, problem, and previous works' limitations clearly. The paper's overall organization is good and easy for readers to follow. The authors open the source code, which is good for reproduction and will benefit the entire community. \nSecondly, the proposed method (GREED) can learn the theoretical properties-preserved graph embedding. And the author provides the math proof for it.\nThirdly, the learned embedding is indexable and pair-independent, which is essential for scalability and fails most of the previous works in the literature. In this aspect, the author not only provides the neural networks-based model but also details of query algorithms.\nLast but not least, lots of comprehensive experiments and discussions are conducted to validate the GREED, including prediction accuracy, method efficiency, scalability, and generalizability.\n\nWeaknesses:\n1. The main concern I have is the novelty of the design of the neural network and the corresponding ablation study (section 4.5). It seems that the second and third strengths above (i.e., preservation of GED's theoretical properties) are mainly from the last layer (i.e., GED and SED prediction functions F). In other words, the paper doesn't have theoretical insights into the choice of siamese architecture and the GNN component. In this case, the ablation study is important to support the claim. However, from Fig. 3(i)~3(k), the model component design seems not convincing (i.e., the green line is not the best). To better understand it, I raised a couple of questions in the \"Questions\" box. \n2. Meanwhile, some writing parts can also be improved. For example, \n(1) The table's index is unclear. There are two different \"table 1\" on page 7 and 15, respectively.\n(2) Figure 4d should be \"Dblp\" instead of \"IMDB\". \n(3) Try to put the figure (tables) and corresponding text on the same page for reading-friendly purposes.\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": {}}, {"review_id": "JYiOfhBLo4Z", "reviewer": "Reviewer_ap6M", "summary": "In this work, the authors design a novel siamese graph neural network GREED which can learn graph (GED) and subgraph edit distances (SED) in a property-preserving manner. The authors demonstrate the efficacy of their approach via empirical results.", "questions": "q1) Why did you not cite and compare your approach against the following state-of-the-art recent approaches i.e., GOTSim [3], NeuroMatch [4], Graph embedding network (GEN) [5], and IsoNet [6] ?\n\nq2) Did you try any other alternatives to siamese graph neural network settings i.e., non-sharing of parameters between query and target graphs to see if it helps ?\n\nq3) Did you try any alternatives to the Graph Isomorphism Network (GIN) module ? \n\nq4) Why did you use sum pool specifically ? ", "limitations": "The authors list just one limitation of their work.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Here are the main strengths of the current work :\n1) The authors focus on graph similarity measurement which is a very important problem in the graph ML community.\n2) The authors through empirical results demonstrate that the proposed approach works well as well as is significantly faster compared to the other baseline approaches.\n3) The authors via using a siamese graph neural network which utilizes shared parameters to embed both the query and target graphs respectively are able to reduce the model parameters as well as the training time significantly.\n\nHere are the main weaknesses of the current work :\n1) The proposed approach has limited novelty factor. \n2) The authors do not seem to compare their work with state-of-the-art recent approaches which could have been good baselines to compare against. More concretely, the authors do not cite and/or compare against the following state-of-the-art recent approaches i.e., GOTSim [3], NeuroMatch [4], Graph embedding network (GEN) [5], and IsoNet [6].\n3) Some aspects of the paper lack details/discussion and the authors do not seem to have tried to experiment with different settings more before finalizing their approach. More concretely, the authors could have tried non-sharing of parameters between query and target graphs to see if it helps. Additionally, the authors could have experimented with alternatives for their Graph Isomorphism Network (GIN) module. Also why did the authors specifically choose sum pool rather than other pooling techniques. The authors could also have tried approximate nearest neighborhood (ANN) based approaches in their work. \n\n[3] Khoa D Doan, Saurav Manchanda, Suchismit Mahapatra, and Chandan K Reddy. Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. pages 665–674, 2021.\n[4] Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. Neural subgraph matching. arXiv preprint arXiv:2007.03092, 2020.\n[5] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In International conference on machine learning, pages 3835–3845. PMLR, 2019\n[6] Indradyumna Roy, Venkata Sai Velugoti, Soumen Chakrabarti, and Abir De. Interpretable neural subgraph matching for graph retrieval. AAAI, 2022.", "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": "-4SHMCrFgu", "reviewer": "Reviewer_ebHE", "summary": "In this work, the authors propose a neural framework to learn two well established metric, GED and SED, for graph similarity computation. By designing a siamese graph neural network to learn GED and SED in a property-preserving manner, the authors also show that the learned functions can guarantee to be a distance metric. Experiments demonstrate the effectiveness of the proposed framework in terms of accuracy and efficiency.", "questions": "Besides the above weakness, one more question is from Section 4.5:\n\nFrom Figure i-k, we can see that Greed-NN shows better performance compared Greed in two out of three datasets, i.e., on PubMed and CiteSeer. The authors should give some analyze of this phenomenon, which is very important to justify their claimed inductive bias.\n", "limitations": "None", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. The idea to unify GED and SED in one learning manner is kind of interesting.\n\n2. The proposed framework is reasonable to approximate GED and SED.\n\n3. The experiments are comprehensive.\n\n### Weaknesses\n1. There have been many works, as mentioned by the authors, on learning graph-based similarity metrics by GNN, thus in general, the novelty of this idea is limited. It is straightforward to include SED into the framework.\n\n2. Though useful, the proposed GNN framework is not novel, which have been proposed in previous works. Especially, the motivation to use Siamese GNN is not clear.\n\n3. The presentation of this work need improvements:\n\n    a) The title ``learning graph distance functions’’ is kind of overclaimed, since the work only learns for graph edit distance, while there are other distances, like maximum common subgraph.\n\n    b) The content of Section 2 is a bit too much, since most of them are established knowledge, not proposed by the authors. The authors can shorten Section 2 by moving some materials to appendix. Moreover, it would be better the authors give the references for GED, SED, and the properties.\n\n    c) In Section 4, the ref of some tables are wrong, e.g., the text following ``4.2 Prediction Accuracy of SED and GED`` and ``4.3 Efficiency`` are all Table 2a and 2b, which is confusing\n\n    d) In Section 4.6, the authors mentioned Table 3a is not found in the paper. \n\n    e) In the Readme of the code, the submission information is still KDD 2022. In fact, I think this is the reason that the table references are messy in the paper. The authors should carefully proofread the paper for NeurIPS submission.\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