NeuroSED: Learning Subgraph Similarity via Graph Neural Networks
Authors: Rishabh Ranjan
Siddharth Grover
Sourav Medya
Venkatesan Chakaravarthy
Yogish Sabharwal
Sayan Ranu
Venue: ICLR 2022 Submitted (2022)
Keywords: Subgraph similarity
graph neural networks

Abstract: Subgraph similarity search is a fundamental operator in graph analysis. In this framework, given a query graph and a graph database, the goal is to identify subgraphs of the database graphs that are structurally similar to the query. Subgraph edit distance (SED) is one of the most expressive measures of subgraph similarity. In this work, we study the problem of learning SED from a training set of graph pairs and their SED values. Towards that end, we design a novel siamese graph neural network called NeuroSED, which learns an embedding space with a rich structure reminiscent of SED. With the help of a specially crafted inductive bias, NeuroSED not only enables high accuracy but also ensures that the predicted SED, like true SED, satisfies triangle inequality. The design is generic enough to also model graph edit distance (GED), while ensuring that the predicted GED space is metric, like the true GED space. Extensive experiments on real graph datasets, for both SED and GED, establish that NeuroSED achieves $\approx 2$ times lower RMSE than the state of the art and is $\approx 18$ times faster than the fastest baseline. Further, owing to its pair-independent embeddings and theoretical properties, NeuroSED allows orders-of-magnitude faster graph/subgraph retrieval.

Under review as a conference paper at ICLR 2022
NEUROSED: LEARNING SUBGRAPH SIMILARITY VIA GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Subgraph similarity search is fundamental operator in graph analysis. In this framework, given query graph and graph database, the goal is to identify subgraphs of the database graphs that are structurally similar to the query. Subgraph edit distance (SED) is one of the most expressive measures of subgraph similarity. In this work, we study the problem of learning SED from training set of graph pairs and their SED values. Towards that end, we design a novel siamese graph neural network called NEUROSED, which learns an embedding space with rich structure reminiscent of SED. With the help of a specially crafted inductive bias, NEuROSED not only enables high accuracy but also ensures that the predicted SED, like true SED, satisfies the triangle inequality. The design is generic enough to also model graph edit distance (GED), while ensuring that the predicted GED space is metric, like the true GED space. Extensive experiments on real graph datasets, for both SED and GED, establish that NEUROSED achieves R 2 times lower RMSE than the state of the art and is = 18 times faster than the fastest baseline. Further, owing to its mair-independent embeddings and theoretical properties. NEUROSED allows up to 3 orders of magnitude faster graph/subgraph retrieval.
INTRODUCTION AND RELATED WORK
Graphs are used to model data in a wide variety of domains. Examples include chemical com- pounds (Sankar et al. 2017). protein-protein interaction networks (PPI) (Alon al.) 2008). knowledge graphs (Ebsch et al. 2020). and social networks (Kempe et al. 2003). A distance function on any dataset, including graphs, is fundamental operator. Among several distance measures on graphs. edit distance is one of the most powerful and popular mechanisms (Liang & Zhao 2017] Zhao et al., 2013; Bougleux et al. 2017; Daller et al. 2018 Fankhauser et al. 201 1 & Bunke 2009 Zeng et al. 2009 He & Singh 2006). Edit distance can be posed in two forms: graph edit distance (GED) and subgraph edit distance (SED). Given two graphs G1 and G2, GED(G1, G2) returns the minimum cost of edits needed to convert 91 to Gz. i... for G1 to become isomorphic to G2. An edit can be the addition or deletion of edges and nodes, or replacement of edge or node labels, with an associated cost. In SED(G1, 22), the goal is identify the minimum cost of edits so that G1 is subgraph (subgraph isomorphic) of G2. For examples, see Fig, Salin in the appendix.
While the applications of GED and SED are beyond doubt, their applicability is constrained by their computation costs. Specifically, both GED and SED are NP-complete (Zeng et al. 2009 Neuhaus el al.
2006 He& & Singh 2006). To mitigate this computational bottleneck, several heuristics (Bougleux
et al. 2017 Daller et al. 2018 Fankhauser et al. [201]] Riesen & Bunke| [2009] Neuhaus et al. 2006
and index structures (He & Singh| 2006) Zeng et al.) 2009 2 & Zhao 201 7 /hha et al. 2013
have been proposed. Recently, graph neural networks have been shown to be effective in learning and predicting GED (Bai al., 2019 Wang et al.) 202T Li et al. 2019 Bai et al.) 2020 Zhang et al.. 2021 Xiu et al. 2020) and subgraph isomorphism (Rex et al. 2020). The basic goal in all these algorthmms is to learn a neural model from a training set of graph pairs and their distances, such that, at inference time, given unseen graph pair, we able to predict its distance accurately. Waang et al. (2200) designed an algorithm to characterize graphs through sampling random walks and then embedding them in feature space. While Wang et al. (2020) has not been studied in the context of GED or SED, the authors have shown that they can detect graph isomorphism. While this progress in the area of graph querying is undoubtedly impressive, there is scope to do more.
Modeling SED: Existing neural approaches to learning GED cannot easily be adapted to learn SED. While GED is symmetric. SED is not. Most neural architectures for GED have the assumption of symmetry at its core and hence modeling SED is non-trivial. In App. we provide a detailed analysis of the limitations of prior architectures in failing to model SED.

---

Under review as a conference paper at ICLR 2022
Exponential Search Space: Computing SED(G1. G2) conceptually requires to compare the query graph 91 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. We note that while several index structures and
heuristics exist for GED (He & Singh 2006 Zeng et al. 2009; Bai et al. 2019 WWan et al. 2002). none exist for SED. Thus, scalability of SED on large graphs remains an unsolved problem.
Preservation of theoretical properties: 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. Several higher-orde tasks such as clustering and indexing rely on such properties (Hadi)
1991 Dohnal et al. 2003 Hjaltason & Samet 2003 Samet 2005 [Uhmmann
1991 Yianilos 1993
Zezula et al. 2006 Brin |
Chávez et al. (001). Existing neural approaches do not preserve
these properties, which limits their usability for these higher order tasks.
Pair-independent computation: There is little scope for pre-computation in existing approaches (either neural or non-neural), the major computations are pair- peir-dependent, i.c., both 91 and G2 need to be known. In a typical graph querying framework, the graph database is known apriori; only the query graph is provided at runtime. If we can generate pair-independent embeddings, and make efficient predictions directly in the embedding space, then retrieval can be sped up tremendously by pre-computing and indexing the embeddings of the database graphs beforehand. Learning with low-volume data: Generating a large amount of high quality training data is computationally prohibitive for SED/GED. So, an effective model should encode powerful priors for SED/GED prediction, to enable generalization even with scarce training data.
We address these challenges by novel architecture called NEUROSED. Our key contributions are:
We formulate the problem of learning subgraph edit distance (SED) for graphs. Since SED is more general than subgraph isomorphism and GED, the proposed theory extends to prediction of GED, graph isomorphism and subgraph isomorphism.
Novel formulation:
Neural architecture: NEUROSED utilizes siamese graph isomorphism network (Xu al. 2018a) to embed graphs in a mai-inndeeenent fashion to an embedding space over which simple function can predict the SED (or GED). The same embedding model is used for both Gi and G2, which captures the prior that similar topological properties need to be considered for both graphs. The carefully crafted prediction function serves as another inductive bias for the model, which, in addition to enabling high generalization accuracy, preserves the key properties of SED/GED, which is major contribution of our work over existing neural approaches.
Indexable embeddings: The prediction function satisfies the triangle inequality over the em- bedding space for both SED and GED. This allows utilization of the rich literature on index structures (Elkan) 2003; Kwedlo& & Czochanski] 2019 Ciaccia et al. 1997) to boost efficiency. Accurate, Fast and Scalable: Extensive experiments on real graph datasets containing up to a million nodes establish that NEUROSED is more accurate in both GED and SED when compared to the state of the art and is more than orders of magnitude faster in range and k-NN queries.
PRELIMINARIES AND PROBLEM FORMULATION
We denote a labeled undirected graph as G (V, L) where V is the node set, E is the edge set and C: VUE + Σ is the labeling function over nodes and edges. Σ is the universe of all labels and contains special empty label e. L(v) and L(e) denote the labels of node and edge respectively. 9. C G2 denotes that G, is a subgraph of G2- All notations used in our work are summarized in Table 6 in the appendix. For the definitions of subgraph and graph isomorphism, refer to App. B in the supplementary. The computation of GED relies on graph mapping.
Definition 1 (Graph Mapping) Given two graphs 91 and G2, let Gr Ei,, and S2 (V2, Eg, L2) be obtained by adding dummy nodes and edges (labeled with e) to G1 and G2 respectively, such that [i = |21 and |& = |Ez]. A node mapping between 9n and G2 is a bijection n : 9 - G2 where (i) Vo E Di, (v) E 122 and at least one of v and T(v) is not a dummy; (ii) Ve = -v1, E E, (e) = (I(v1), (T())) e Eg and at least one of e and x (e) is not a dummy.
Example 1 Fig. 5h shows graph mapping. Edge mappings can be trivially inferred, so are omitteed
Definition 2 (Graph Edit Distance (GED) under mapping X) GED between I1 and Gz under n is
GED, (0) = Σ
+ Σ d(L(e), ((T(e))
(1)
e
2

---

Under review as a conference paper at ICLR 2022
where
is a distance function over the label set.
d(f1,6) (2) models an insertion if { c, deletion if Eg = and replacement if E1 + E and neither L nor Eg is dummy. We assume d to binary function, where d(li, (2) if & + f2, otherwise, 0. Our framework easily extends to more general distance functions (details in App. D
Example 2 GED for the shown mapping in Fig. 5b 3. The red mappings incur a cost of L.
Definition 3 (Graph Edit Distance (GED)) GED is the minimum distance under all mappings.
min GED(G1, VTE
GED,(91,
where (G 92) denotes the set of all possible node maps from 91 to G2.
Definition 4 (Subgraph Edit Distance (SED)) SED is the minimum GED over all subgraphs of G2-
SED(GI, = min GED(GI, SC9:
Example 3 Revisiting Fig.
5b
GED (2) 3. The shown mapping incurs the minimun cost. 5a for more examples.
SED(S1, G2) = 1. Refer Fig.
Problem (Learning SED) Given a training set of tuples of the form (9, SED((1, learn neural model to predict SED Q1, Q2) on unseen graphs Q1 and Q2.
Problem 2 (Learning GED) Given training set of tuples of the form (91, G2, GED(G1, G2)), learn a neural model to predict GED Q1, Q2) on unseen graphs Q1 and O2.
2.1 PROPERTIES OF SED AND GED
Observation 1 (i) GED G2) 2 0, (ii) SED 92) 2 O.
Observation 2 (i) GED 92) 0 iff 91 is isomorphic to Gz. (ii SED(GI, G2) = 0 iff 91 is subgraph isomorphic to G2.
Observation 3 GED is metric if the distance function over label set E is metric (e Singh 2006). d as defined in $ is metric (He & Singh 2006). Hence, GED from is metric.
next prove that SED satisfies the triangle inequality in Theorem
Theorem SFD(GI, < SED(GI, 92) + SHD(G2,9)).
PROOF: See App. D.T for details.
NEUROSED
Fig. Presents the architecture of NEUROSED. The input to our learning framework is a pair of graphs Go (query), GT (target) along with the supervision data SED(GQ, Our objective is to train a model that can predict SED on unseen query and target graphs. The design our model must be cognizant of the fact that computing SED NP-hard and high quality training data is scarce. Thus, we use Siamese architecture in which the weight sharing between the embedding models boosts learnability and generalization from low-volume data by imposing a strong prior that the same topological features must be extracted for both graphs.
Siamese Networks: In these models, there are two networks with shared parameters applied two inputs independently to compute representations, These representations are then passed through another module to compute similarity score.
3.1 SIAMESE GRAPH NEURAL NETWORK
As depicted in Fig. Ta we use siamese graph neural network (GNN) with shared parameters to embed both Go and GT. Fig. Tb focuses on the GNN component of NEUROSED. We next discuss each of its individual components.
Pre-MLP: The primary task the Pre-MLP is to learn representations for the node labels (or features). Towards that end, let x,, denote the initial feature set of node The MLP learns a hidden representation و = MLP (x.). In our implementation, x, a one-hot encoding of the categorical node labels. We do not explicitly model edge labels in experiments. NEUROSED easily be extended to edge labels by strategies such as using GINE (Hu et al. 2019) layers instead GIN layers (see App. C
3

---

Under review as a conference paper at ICLR 2022
GRAPHS
FINREDINGG VECTORS
NODE FEATURE VECTORS
Contalaneee Boom all
EMBEDDING VECTOR
GNN
GO
PREDICTION
GGN byyrrs
layers
PC LA
Shared Weights
FiZoZ21
Pre MLP
FOOL
Post MIPP
GNN
Lnzy
x
Zpp
4
(a) Siamesc architecture
(b) GNN component
Figure 1: The architecture of NEUROSED.
Graph Isomrrphism Network (Gin): GIN (Xu et al. 2018b) consumes the information from the Pre-MI. to learn hidden representations that encode both the graph structure as well as the node feature information. GIN is as powerful as the Weisfeiler-Lehman (WL) graph isomorphism test (Leman& & Weisfeiler 1968) in distinguishing graph structures. Since our goal is to accurately characterize graph topology and learn similarity, GIN emerges the natural choice. GIN develops its expressive power by using an injective aggregation function. Specifically, in the initial layer, each node e in graph G is characterized by the representation learned by the MLP, i.e., h - n Subsequently, in each hidden layer i, we learn an embedding through the following transformation.
h MLP (1 (1+e) h
E
h
(4)
(EN((V)
Here, c is a layer-specific learnable parameter, (g) is one-hop neighbourhood of the node v, and bg u The k-th layer embedding is hy where k is final hidden layer.
Concatenation, Pool and Post-MLP: Intuitively, y captures a feature- space representation of the i-hop neighborhood of v. Typically, GNNS operate node edge level predictive tasks, such as node classification or link prediction, and hence, the node representations are passed through an MI.P for the final prediction task. In our problem, need 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 2 = CONCAT (hS,, Vi E {1, 2......... .k]). the subgraphs centered on v at different radii in the range [1, kj. 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-processing. Mathematically:
.2.....,,,,
This allows us to capture a multi-granular view of
Zg = MLP(2 MLP
Σ WEV
(5)
SED Prediction: The final task is to predict the SED as a function of query graph embedding Zg and target graph emhedding Zgy- The natural choice would be to feed these embeddings into another MLP learn SED Zgz) ). This MLP can 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.
To ensure preservation of original space properties, we introduce an inductive bias in the form of a simple fixed computation function F(Zg., Ze,) to predict the SED. By training the model to produce embeddings Zgo and Zg, such that F(Zga Ze,) SED Zgy). we enforce a rich structure on the embedding space. We show that these embeddings satisfy many key properties of the
SED (and GFD) function that existing neural algorithms fail to do (Bai et al. 2019 Wang et al. 202T Bai et al. 2020 Zhang et al. 2021). F is defined as follows:
(6) 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 O. This follows the intuition that the SED accounts for those features of Go that are not in Gr. Moreover, consistent with SED, the additional features in G7 that are not in Go. do not incur any cost. Finally, the parameters of the entire model are learned by minimizing the mean squared erro (here is the training set).
F(Zgo Zgr)= ||| [ege
Zl = |lmax {0, Zgo Zgg
L
1
Σ
(FiZea: Zo,) - (T)
T
GTJET
'Since SED computation is NP-hard, in App. G we discuss loss function hased on SED lower and upper hounds, which are faster compute.
4

---

Under review as a conference paper at ICLR 2022
Adaptation for GED (NEUROSEDg): The proposed architecture naturally extends to GED (denoted by NEUROSEDg) with simple modification the computation function. Specifically, instead of Eq. 6 we
F9 FZ Zer) / Z ll2
(8)
3.2 THEORETICAL CHARACTERIZATION
Lemma The following properties hold on predicted SED F(Z Zor):
F(ZGa Zer] 2 0
2. F(Zge Zor = + Zge S. Zor F(zg,,
F(Zgo Z F(zgo
PROOF. Properties (1) and (2) follow from the definition of F itself. Property (3) follows from the fact that we take the 122 norm (holds for any monotonic norm, details are available in App. D M
We see that FF satisfies the analogue of properties of SED ($ 2.T). Conditions 1, 2, and captures non-negativity, the subgraph relation (Rex al. 2020), and triangle inequality respectively.
Furthermore, we show App. a complete constructive characterization for any which can model SED in the embedding space, while being translation-invarian and non-negative homogeneous. Specifically, we show that the general form for JF involves solving a constrained optimization problem (intractable in general), but under a mild technical assumption closed form can be obtained which coincides with equation 6 This asserts that equation 6 is the natural choice for F,, modulo the choice of norm. L2 norm is natural choice due to its isotropy (direction/rotation invariance) and good empirical performance.
Lemma 2 The predicted GED, i.e., Fg is metric. (i) Non-negativity: F FZ Zor > 0, (ii) Identity: (Z (igg,
) = 0 > Zge = Zg. (iii) Symmetry: F (Zge: Zog) = F, (Z Zge):
(iv) Triangle Inequality: Fy (Z Zgr) S F (Z ZT) + F Zgr).
PROOF. Follows trivially from the fact that F, forms a Euclidean space.
Similar to F, the form for F, also comes naturally from some mild technical assumptions for any embedding space function which models GED (see App.
Theorem 2 The properties of SED (and GED) in 2.7 are satisfied by the prediction functions NEUROSED(CI; G2) (and the GED version NEUROSEDG (G,, G2)).
PROOF SKETCH. (For SED) Let & be the embedding function leamned by NEUROSED's GNN. Then Now, the relevant properties follow from Lemma | using the substitutions Zgo + E(G)), Zg, + E(G2), and Zg,, EGs).
NEUROSED(C G2) = E
We note here that if different embedding models are used for G1 and G2, or if the distance computations are pair-dependent (Li al. 2019), then Theorem 2 would hold. is easy to verify that the proof fails if Eo and Ey are different embedding functions corresponding to the query and the target, if & is a function of both 91 and G2. Hence, the siamese architecture is crucial. Complexity analysis: Inference is linear in query and target sizes (see App. for details).
3.3 COMPARISON WITH NEUROMATCH REX ET AL.. 2020
Both NEUROSED and NEUROMATCH use siamese GNNs. However, there are important differences in (1) their objectives, (2) training and (3) inference procedures and (4) theoretical characterization.
1. Objective: While NEUROSED is trained to predict GED and SED directly. NEUROMATCH studies the simpler task of anchored subgraph isomorphism. Thus, NEUROSED subsumes the objective of AECROMATCH.
2. Training: NEUROMATCH trains the model to construct order embeddings wherein if G1 C G2. then Vi, Zg, S Ze, [t). where Zg denotes the embedding of graph g. To inject this bias, the model is trained using max-margin loss. NEUROSED does not enforce order embeddings. Rather learns embeddings that make the proposed prediction functions (Eq. 6 and Eq. S effective through RMSE loss. In the context of SED, Eq, i used in the loss function of both NEUROSED and NEUROMATCH. However, the loss function themselves are different, which results in the proposed embedding space being considerably richer in its ability preserve properties from the original space. In addition, in App. E we characterize the class of functions that may act as a substitute for Eq. 6 and thereby perform thorough theoretical characterization of our work.
5

---

Under review as a conference paper at ICLR 2022
3. Inference: NEUROSED creates single embedding of the query graph, based on which the SED and GED predictions are made. In contrast, NEUROMATCH generates embeddings for each node neighborhood in the query and target graph and makes [Vol|Vrl predictions corresponding to each pair of neighborhoods. The final decision of whether the query is a subgraph of the target is performed using voting mechanism.
4 EMPIRICAL EVALUATION
In this section, we establish the following:
Subgraph Search: NEUROSED outperforms the state of the art approaches for SED prediction.
Graph Search: NEUROSEDG, the variation to predict GED, outperforms the state of the art approaches for GED prediction.
Scalability: NEUROSED and NEUROSEDG are orders of magnitude faster than existing approaches
and scale well to graphs with millions of nodes.
The code base and datasets are available at http://wwyyyoooosooooooosssscc/r
4.1 EXPERIMENTAL SETUP
Details on the hardware and software platform and parameters are provided in App. Datasets: Table 4.1 lists the datasets used for benchmarking. Further details on the dataset se- mantics are provided in the App. H We include mixture of both graph databases (#graphs >), as well as single large graphs (#graphs 1). Linux and IMDB contain unlabeled graphs.
Aug [1|
Aug [8
[X]
4Cimphs
Ang Vol
(Ang.6o
Dbip
7.2M
4
Anazon
20:
CiceSeec
PubMed
19:72
4.2k
44.3k
5.36
1
1
12
12
12
3
Cora_Mil
33k
8.28
1
11
Protein
38
70
3
1,071
11
2
AIDS'
A105
14
16
9
29
58
700
1.811
10
Linux
1,000
INDB
65
1,500
13
0
20 40
20 40
Table 1: Datasets used for benchmarking.
SED NeuroSED
SED in HPMN-RW
Figure 2: Heat Map of SED error against query size in Dblp. Darker means higher error. Training (and Test) Data Generation: For GED, AIDS', and Linux. Our setup is identical to SIMGNN (Bai et al. 2019) and M2 Zhang al. 2021). For SED, the procedure more intricate. The details of datasets can be found in App.
anmery.karger graph pairs from IMDB,
Queries: In single large graphs, queries are sampled by performing random BFS traversal (depth up to 5) on a randomly chosen target graph. In addition, for ATDS, we use known functional groups test queries (See App. G for details). This allows us to benchmark NEUROSED on both
natural as well synthetic queries. The average query sizes (Vol. (Eo)) are listed in Table 4. Ground-truth: We use mixed integer programming method F2 (Lerouge al. 2017 implemented in GEDLIB (Blumenthal et al. 2019) with a large time limit to generate ground-trum truth data.
Train-Validan Loan-Validation-Teel Split: We use 100K query-target pairs for training and 10K pairs each for validation and test.
B Bai al. 2019). GENN- A" (Wang et al. 2021) and H (Zhnn et al. 2021). H2MN has two versions based on random walks (H'MN- RW) and k-hop neighborhood (H "MN-NE) We include both.
Baselines: To evaluate performance in GED, we compare with SIMGNY
For SED, no neural approaches cxist. However, H and SIMGNN can be trained by replacing GED with SED along with minor modifications in training. While NEUROMATCH (Rex al. 2020) cannot predict SED, it generates violation score which can be interpreted as 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-N (--Nearesteeighbour)) queries. Thus, NEUROMATCHI comparisons are limited to k-NN queries on SED. The changes required to adapt to SED are in App. [
We the Py Torch implementation of SIMGNN given paperswi theade The code of all other neural algorithms have been obtained from the respective authors.

---

Under review as a conference paper at ICLR 2022
Methods
>bipp
Amazon
Pubbted
CiteSeer
Cors__X
Protein
AIDS
Methods
ATDS
Linux
TH03
NEUROSED
0.964
0,495
0.728
0.519
0.635
0.524
0.512
NLuRoSeng
0.7%6
0.415
6.734
MNW
1.470
1.294
1.213
1,502
1.466
0.941
0.749
I-MN-Rw
0.994
0,734
86.077
B-MN--E
1.000
0,319
87.594
H' MN-NE
1.552
0.971
1.326
1.827
1.229
0.755
0.657
GENN-A"
0.907
0.267
NA
SIMGNN
1,482
2,800
1,322
1,781
1,289
1,223
0.696
SIMGAN
1.087
0.666
66.250
Branch
2.917
4.513
2.613
3,161
3.102
2.391
1.379
Beanch
3,302
2,474
6,755
MIP-F2
3,427
5.595
3,399
4,474
3,871
2.249
1,537
MIPF2
2.929
1,245
82.124
(a) Prediction of SED.
(b) Prediction of GED
Table 2: RMSE scores (lower is better) in (a) SED and (b) GED. GENN-A does not scale on graphs beyond 10 nodes and hence the results in IMDB are not reported.
In the non-neural category, we use mixed integer programming based method MIP-F2 (Lerouge) et al. 2017) with a time bound of 0.1 seconds per pair for both GED and SED. MIP-F2 provides the optimal solution given infinite time. In addition, we also compare with BRANCH (Blumenthal 2019), which achieves an excellent trade-off between accuracy and runtime (Blumenthal et al.) 2020).
BRANCH uses linear sum assignment problem with error-correction (LSAPE) to process the search space. We use GEDLIB's (Blumenthal et al. 2019) implementation of these methods.
4.2 PREDICTION ACCURACY OF SED AND GED
Tables 2a and 2b present the accuracy of all techniques on SED and GED in terms of Root Mean Square Error (RMSE). In App. D we evaluate the same performance using several other metrics such as R² and Mean Absolute Error (MAE). NEUROSED outperforms all other techniques in out of 10 settings. The gap in accuracy is the highest in IMDB for GED, where NEUROSED is more than 10 times better than the neural baselines. A deeper analysis reveals that IMDB graphs are significantly denser and larger than AI techniques have higher errors in IMDB, the deterioration is more severe in the baselines indicating that NEUROSED scales better with graph sizes.
Linux. Thus, computing the optimal GED is harder. While all
To gain insight on whether the same patterns also hold in SED, in Fig. 2. RMSE against query graph size in Db1 p. Specifically in this plot, each dot corresponds to query graph Go. The co-ordinate of a query is (SED(Go, (Vel.. The color of a dot is the RMSE; the darker the color, the higher is the RMSE. When we compare the heat maps of NEUROSED with the most recent baseline H we observe that M is noticeably darker. Furthermore, the dark colors are clustered on higher SED values and large query sizes (upper-right corner). This indicates that NEUROSED scales better with query size and higher SED. The heatmaps of all techniques are provided in App. [
we plot the heat map of
Range and k-NN queries are two of the most common database queries. We next evaluate the performance of the various algorithms on these queries. a distance threshold 0, the goal is to retrieve all database graphs that are within 0 distance from the query graph. In a A--N query, given the query graph, we identify the k nearest neighbors from the search space in the database graphs, whereas for GED, the search space constitutes of the database graphs. The performance measures are F1-score (Range query) and Kendalls's tau (k-NN) (Kendall 1938) of the predicted answer set, when compared against the ground truth.
Range and k-NN queries:
range query, given
order. For SED, the search space includes all target graphs of
NEUROSED consistently outperforms all baselines in F1-score. Similar trend is also visible in K-NN queries. Specifically, in Kendall's 's tau (Tables (3 and (3b). barring the exception of GED in Linux, NEUROSED consistently scores the highest indicating best preservation of the ranking order. Overall, this shows that accurate prediction of distance also transfers to accurate querying accuracy. In App. K we also report K--N performance based on Precision@k, In this analysis, we do not include GENN-A" since it is orders of magnitude slower than all neural-baseling and provides comparable distance accuracy to MN. Next, we discuss efficiency in detail.
As visible in Figs. 3a 3h
Methods
F Fal2sed
Ci Bwes
Cors_ML,
Frotwin
AIDS
Methods
AIDS'
Linux
1M08
NEUROSED
0.90
0.90
0.91
0.75
0.50
NEUROSEDG
0.78
0.90
0.87
R'MN-ww
0,88
0.70
0.72
HFMN-RW
0.72
0.89
0.80
H-MN-NE
0.87
HPMN-NE
0.93
SIMGAN
088
087
0.86
NEUROMATCH
0.70
0.75
0.73
0.57
0.59
SIMGNN
0.70
0.84
0.70
(a) Ranking in SED.
(b) Ranking in GED
Table 3: Kendall's tau scores (higher is better).
7

---

Under review as a conference paper at ICLR 2022
Methods
Db
Ama
FubMed
ClteSeer
Cora_ NT.
Protein
ATDS
Methods
ACDSS
Linux
INDE
NEUROSED
6.84
1.46
1.30
1,28
1.25
0.86
0.84
NEUROSEDG
0.49
0.70
0.63
IPMN-RW
44.68
23.2
25.79
27.54
29.04
19.33
9.63
IFMN-aw
9.50
5.74
8.81
H-MNN-RR
56.82
40.34
50.64
54.46
70.59
28.99
15.76
H-MN-NE
10.35
9.80
10.69
GENN-A
12190
1340
NA
SIMGNN
47.68
39.40
40.73
39.02
SIMGIN
3921
38,98
BRANCH
626.489
79.25
99.11
155.09
132.98
52.26
12,93
BRANCH
10.70
8.24
127.00
MIP-F2
1979.185
861.95
606.01
827.65
790.01
881.77
360.12
MiP-F2
191,8
1175,588
(a) SED.
(b) GED
Table 4: Running times of all methods in seconds per 10k pair (lower is better).
Datasets
Range (f/ -
2)
16-NN
Sampler
Pubdled
CiteSSer
Amazoon
CPU
GPU
CPU
GPU HEMMN
L:Scun
Mrlree
HENNN
L-Scun
Mr-ree
L:Scun
DFS
0.728
0.519
0.495
0,603
1.01
0.004
27.5
RW
0.508
0.770
0.450
Anazon
9.09
5,07
0.027
372
RWR 0.545
0.754
0.299
05-1p
20,9
18.6
0.136
698
SHADOW
0.966
0.753
0,530
(a) Scalability
(b) Query generalization
Table 5: (a) Querying time (s) for SED in the three largest datasets. L-Scan indicates time taken by linear scan in NEUROSED (times differs based on whether executed on a CPU or in GPU). M-Tree indicates time taken by NEUROSED when indexed using an adapted Metric Tree. We only present the time of M2MN-RW since MN is exorbitantly slow. The full table is provided in Table Appendix. (b) Generalization unseen query distributions. BFS (seen) acts as the baseline to compare against. The numbers represent RMSE.
4.3 EFFICIENCY
Table 4 presents the inference time per 10K graph pairs. As visible, NEUROSED is up to 1800 times faster than the non-neural baselines and up to 10 to 20 times faster than H2MN-RW, the current state of the art in GED prediction. Also note that - * is exorbitantly slow (Table 4b). GENN-A is slower since it not 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 a small minority of graphs that are in the answer set. In App. K.
we discuss this issue in detail.
Here, we showcase how pair- indepennttnd embeddings, and ensuring triangle inequality leads to further boost in scalability. For this experiment, we the three largest datasets of PubMed, Amazon and Dbl For each dataset, we pre-compute NEUROSED embeddings of all database graphs by exploiting pair-independent embeddings. Such pre-computation is not possible in the neural or non-neural baselines. Furthermore, since the predictions of NEUROSED satisfy triangle inequality, we index the pre-computed embeddings of the database graphs using the Metric Tree (Uhlmann 1991) index structure adapted to asymmetric distance functions. Consequently, for NEUROSED, we only need embed the query graph and evaluate F make predictions at query time. Table [5a presents the results range and 10-NN queries. When computations are done on a GPU, NEUROSED more than 1000 times faster than both M2 and M In the absence of a GPU, H'MN is practically infeasible since expensive weir-dependent computations In contrast, even on a CPU, with tree indexing, NEUROSED is se 50 times faster than Gased H2 RW. Note that indexing enables up to 3-times speed-up NEUROSED over linear scan, which demonstrates the gain from ensuring triangle inequality. These results show the benefits of using an easily computable and parallelisable prediction function J with theoretical guarantees.
Scalability:
done query time.
4.4 ABLATION STUDY
In this study, we explore the impact of our inductive biases in learning from low-volume data. We create two variants of NEUROSED: (1) NEUROSED--ual trains the two parallel GNN models separately without weight-sharing and (2) NEUROSED-NN uses an MLP instead of F. Both have strictly better representational capacity than NEUROSED, so are expected to match the performance with infinite data. Figs. 44|44] present the results. The RMSE of NEUROSED consistently better than NEUROSED-Dual, with the difference being more significant at low volumes. This indicates that siamese structure helps. Compared to NEUROSED. NEUROSED-NN achieves marginally better performance at larger train sizes in PubMed and CiteSeer. However, in Dblp. NEUROSED is consistently better. The number of subgraphs in a dataset grows exponentially with the node set size. Hence, an MLP needs growing training data to accurately model the intricacies of this search space. In Dblp, even 100k pairs is not enough to improve upon F. Overall, these trends indicate that F enables better generalization and scalability with respect accuracy. Furthermore, given that its
8

---

Under review as a conference paper at ICLR 2022
100
100
100
100
100
(1-Scor((%)
90
80
80
SimfiNN
90
50
HRMN-NE
60
60
NeursSED
85
10
20
10
10
10
10
20
(ange(%)
(ange(%)
Range(%%)
Range(%)
Range(%)
PubMed
(b) CiteSeer
Cora_ML
(d) Protein
(e) AIDS
100
100
100
F1- F1-Score(%)
98
80
96
90
SimONN
H-MN-NE
60
91
80
HMN--RW
NeuroSED;
10
15
20
10
15
20
20
Range(%)
Range(%)
Range(%)
(f) AIDS'
Linux
(h) IMDB
Figure 3: Fl-score range queries on SED (a-e) and GED (f-h), The range threshold is set as percentage of the max distance observed in the test set.
NeusSED-Ne AN NourSED Dual NecreStE
1.5
1.5
RMS
1.0
1.6
0.5
10
10
10
10
10
107
10
10
Training Pairs
Training Pairs
Training Pairs
(a) Dblp
(b) PubMed
(c) PubMed
Figure 4: Ablation study to analyze the impact of siamese architecture and function F.
performance is close to an MLP, and it enables indexing, the benefits outweigh the marginal reduction accuracy. More ablations studies are provided in App. K.1
4.5 GENERALIZATION TO UNSEEN QUERY DISTRIBUTIONS
We train the model by sampling queries from the graph database through BFS enumerations. How does NEUROSED generalize to unseen distributions? Towards that end, we generate queries from the three unseen distributions of (1) Random Walks (Rw), (2) Random Walks with Restarts (RwR), and (3) SHADOW (Zeng et al. 2021 Table 5b presents the results. As visible, the errors remain low. Even more surprisingly, the errors Rw and RwR better than the train distribution of BFS itself. This indicates good generalization to unseen distributions. See App. for further details on the sampling strategies.
5 CONCLUSIONS. LIMITATIONS AND FUTURE WORK
Similarity search is a fundamental operator for graph analytics. Edit distance one of the most popular similarity measures defined graphs. The applicability of SED and GED, however, is constrained by its exponential computation complexity. Our work motivated by the following question: Is it possible design a neural framework that generalizes both SED and GED, preserves their key properties and is capable of learning from a low-volume training data? We show that this is indeed possible. The efficacy and efficiency of NEUROSED stems from three algorithmic innovations: siamese architecture to reduce dependence on high-volum training data, carefully designed function introduce an inductive bias and mimic important properties of the original space, and pair-independent embeddings to enable massive scalability.
One limitation of our work (and all neural approaches (eex et al., 2020 Zhang al. 2021 Wang et all],2202 [2021] [Li et al. 2019 Bai et al. 2019 2020)) is the ability to predict on large query graph sizes. While the deterioration in prediction quality with larger query sizes manageable the same query sizes are seen in the train data, generalizing from small query sizes to large query sizes remain an unsolved problem (See App. M). The ability to generalize to unseen larger query sizes is important since computing GED and SED graphs is computationally intractable. To further advance the field of neural graph distance learning, this generalization ability.
SP-complete. Hence, generating training data on large query

---

Under review as a conference paper at ICLR 2022
6 REPRODUCIBILITY STATEMENT
Please find all code, experiments and generated data at the following anonymous link: https://
In Appendix, we have given details that are needed to make our work more reproducible. In particular,
have (1) additional proofs in App. [ (2) descriptions of datasets in App. H (3) additional
definitions in App. B (4) analyses of computation cost for SED and GED computation in App-
F (5) additional details of the pipeline of our architecture in App. G (6) additional details of the
experimental setup in App. I and (7) additional experimental results in App.
REFERENCES
Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and Süleyman Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. In Proceedings 16th International Conference on Intelligent Systems for Molecular Biology (ISMB), pp. 241-249, 2008.
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM '19, pp. 384-392, 2019.
Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. Proceedings of the AAAI Con- ference on Artificial Intelligence, 34(04):3219 3226, Apr. 2020. doi:
URL https://ojs.aaee http:/ossaaai.orrg.o... http://oo..aaa.ooginndeee.. www..oinwe...p/AAA//aate..ee.dd. pttppAAAA//artoceviiiw/./2/
David B Blumenthal. New techniques for graph edit distance computation. arXiv preprint
arXiv: arXivv/908.000 00265, 2019.
David B Blumenthal, Sébastien Bougleux, Johann Gamper, and Luc Brun. Gedlib: a c++ library for graph edit distance computation. In International Workshop on Graph-Based Based Representations in Pattern Recognition, pp. 14-24. Springer, 2019.
David B Blumenthal, Nicolas Boria, Johann Gamper, Sébastien Bougleux, and Luc Brun. Comparing heuristics for graph edit distance computation. The VLDB Journal, 29(1):419 458, 2020.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. arXiv preprint arXiv:1707.03873 2017.
Sébastien Bougleux, Luc Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Gaüzère, and Mario Vento. Graph edit distance quadratic assignment problem. Pattern Recognition Letters, 87: 38-46, 2017.
ISSN 0167-8655. Advances in Graph-baser Pattern Recognition.
Sergey Brin. Near neighbor search large metric spaces. In Proceedings of the 21th International Conference Very Large Data Bases, VLDB '95, pp. 574-584, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. ISBN 1558603794.
Edgar Chávez, Gonzalo Navarro, Ricardo Bacza- Yates, and Jose Marroquin. Searching in metric spaces. ACM Comput. Surv. 33:273-321, 09 2001. doi: 10. N0.1145/502807.5022
Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB, 1997.
Évariste Daller, Sébastien Bougleux, Benoit Gaüzère, and Lue Brun. Approximate Graph Edit Distance by Several Local Searches in Parallel. In 7th International Conference on Pattern Recognition Applications and Methods, 2018.
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, doi: 10. (0.1022/A:1025506000888 URL http::///oi.org//////// T0. 10255220000000000000
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 JEEE International Conference Big Data (Big Data), pp. 2520-2525, 2020.
10

---

Under review as a conference paper at ICLR 2022
Charles Elkan. Using the triangle inequality to accelerate k-means. In Proceedings of the Twenti- eth International Conference on International Conference on Machine Learning. ICML'03, pp. 147-153, 2003.
Stefan Fankhauser, Kaspar Riesen, and Horst Bunke. Speeding up graph edit distance computation through fast bipartite matching. In Proceedings of the 8th International Conference Graph- Based Representations in Pattern Recognition, pp. 102-111, 2011.
Ali S. Hadi. Finding groups in data: An introduction to chster analysis. Technometrics, 34:111-112, 1991.
Huahai He and Ambuj K Singh. Closure-tree: An index structure for graph queries. In 22nd International Conference Data Engineering (ICDE), pp. 38 38. IEEE, 2006.
Gisli R. Hjaltason and Hanan Samet. Index-driven similarity search in metric spaces (survey article).
ACM Trans. Database Syst., 28(4):517-580, December 2003.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint arXiv: 12265, 2019.
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137-146, 2003.
M. G. Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81-93, 1938. ISSN 00063444.
URL http://wwww..koorro//ssbb2222222
Wojciech Kwedlo and Pawel J. Czochanski. A hybrid mpi/opemmp parallelization of $k$ -means algorithms accelerated using the triangle incquality. IEEE Access, 7:42280-42297, 2019.
AA Leman and B Weisfeiler. A reduction of a graph canonical form and an algebra arising during this reduction. Pauchno-Techhnicheskkyy Informatsiya, 2(9):12-16, 1968.
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, 2017. ISSN 0031-3203. doi: https://doi.co http:///doi.rg/1000 10.6//......00//1........1..111.
http://///to/.2000000 patcog.2017.07.02. URL
https:/wwww.scienee.
Jure Leskovec and Rok Sosič. Snap: A general-purpose network analysis and graph-minine library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1, 2016.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In Proceedings of the 36th International Conference on Machine Learning, pp. 3835-3845, 2019.
Yongjiang Liang and Peixiang Zhao. Similarity search in graph databases: A multi-layered indexing approach. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pp. 783-794, 2017. doi: 20.100/
Michel Neuhaus, Kaspar Riesen, and Horst Bunke. Fast suboptimal algorithms for the computation of graph edit distance. In Yan Yeung, James T. Kwok, Ana Fred, Fabio Roli, and Dick de Ridder (eds.), Structural, Syntactic, and Statistical Pattern Recognition, pp. 163-172, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-37241-7
Sayan Ranu, Bradley Calhoun, Ambuj K Singh, and Joshua Swamidass. Probabilistic substructure mining from small-molecule screens. Molecular Informatics. 30(9):809-815, 2011.
Rex, Ying, Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, and Jure Leskovec. Neural subgraph matching, 2020.
Kaspar Riesen and Horst Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Comput., 27(7):55-955 June 2009. ISSN 0262-8856. doi: 10.10066/.imar
http://tn////dii.oo//00100f.fi.p http://...maaiis........o 2000.044.00

---

Under review as a conference paper at ICLR 2022
Hanan Samet. Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2005. ISBN 0123694469.
Aravind Sankar, Sayan Ranu, and Karthik Raman. Predicting novel metabolic pathways through subgraph mining. Bioinformatics, 33(24):3955-33)) -3663, 2017.
Jeffrey K. Uhlmann. Satisfying general proximity/similaity queries with metric trees. Inf. Process. Lett., 40: 175-197, 1991.
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 International Conference on Learning Representations, 2020. URL https:
Runzhong Wang, Tianqi Zhang, Tianshu Yu, Junchi Yan, and Xiaokang Yang. Combinatorial learning of graph edit distance via dynamic embedding. IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pp. 5241-5250, 2021.
Haibo Xiu, Xiao Yan, Xiaoqiang Wang, James Cheng, and Lei Cao. Hierarchical graph matching network for graph similarity computation, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826. 2018a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826. 2018b.
Peter N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proceedings of the Fourth Annual ACM-SIAM Symposium Discrete Algorithms, SODA '93, pp. 311-321, USA, 1993. Society for Industrial and Applied Mathematics. ISBN 0898713137
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 NeurIPS, 2021. URL
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, August 2009.
Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, and Michal Batko. Similarity Search: The Metric Space Approach, volume 32 of Advances in Database Systems. Springer, 2006. ISBN 0-387-29146-6.
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, pp. 2274 2284, 2021.
Xiang Zhao, Chuan Xiao, Xuemin Lin, Qing Liu, and Wenjie Zhang A partition-based approach to structure similarity search. Proc. VLDB Endow, 7(3): 169-180, November 2013. ISSN 2150-8097. doi: 10.4477827332322222256. URL UKL.hhpp///bblorr///0//177722222
APPENDIX
A INABILITY EXISTING NEURAL APPROACHES GED MODELING SED
A key difference between SED and GED is that while GED is symmetric, SED is not. Hence, if the architecture or training procedure relies heavily on the assumption of symmetry, then the modeling capacity is compromised.
12

---

Under review as a conference paper at ICLR 2022
%
9
9
GED matdi
SED MastI
(b) Graph Mapping Figure (a) A sample set of graphs and their corresponding GED and SED matrices. (b) Example of graph mapping. The dashed nodes and edges represent dummy nodes and edges. The red arrows denote either insertion or change of label.
(a) GED and SED
GMN (Li et al., 2019): The loss function of GMN computes the euclidean distance between the embeddings and then this signal is used learn the weight parameters (See Eq. 12 in (Li al. 2019)). The assumption of euclidean distance prohibits the model from learning an asymmetric distance function. Certainly, the loss function can be changed to incorporate an asymmetric distance measure and the performance of the architecture following this change may be studied. However, the selection of an appropriate loss function that works well with the GMN architecture is research problem in itself. Apart from the loss function, the proposed architecture along with the attention mechanism is also motivated by symmetry (note the quantifications for and j in Eqns. (4-8) in (Li ct al. 2019)).
GraphSim (Bai et al. 2020): GraphSim computes a square similarity matrix across node pairs of two graphs 91 (V1,& &1). G2 (V2, &2) which CNNs applied to predict the similarity. Since G, and G2 may be of different sizes, the smaller graph is padded with [ [22l zeros. When the similarity matrix has a large number of zeros, it confuses the model into thinking that the two graphs are dissimilar. The authors of GraphSim acknowledge this themselves while justifying padding of [/1 |12 zeros instead of fixed maximum size limit. We quote an exact line from the paper:
"the similarity matrix between two small but isomorphic graphs may be padded with lot of zeros, potentially misleading the CNNs to predict they are dissimilar."
In our problem, even if the query graph is significantly smaller than the target graph (tens of nodes hundreds), SED can be 0. Thus, the above mentioned design of relying on node-to-node square similarity matrix is not well suited.
SimGNN (Bai et al., 2019): SIMGNN relies on neural tensor network and a pairwise node comparison module to compute similarity between two graphs. The pairwise node comparison module assumes the comparison matrix to be symmetric. Hence, in our adaptation of SIMGNN for SED, we remove this particular module and only use the neural tensor network.
DEFINITIONS
Definition (Graph Isomorphism) Graph 91 E1,,E,, L1) is isomorphic to G2 (V2, E2, L2) if there exists a bijection x Vi + V2 such that (i) Vu E V1 L(v) [(T(v)), (ii) Ve = (e), U2) E & (()) (I(w1), n (v2)) E2, and (iii) Ve E E L(e) = ((x(e)).
Subgraph isomorphism is defined analogously by using an injection instead of bijection.
Definition 6 (Nearest Subgraph) S is nearest subgraph Gi in G2 if SED(G,, G2) GED(GI,S),
HANDLING EDGE LABELS
trrighhtforwwad extension of NEUROSED handle edge labels is GINE (Hu et al. 2019 layers instead of GIN layers. Equation can be modified as follows:
h MLP (1 (1+c) h2 2
Σ
ReLU
u of
(9)
wENg(t)
where @g denotes the vector representation of the edge label for edge (v, u).
13

---

Under review as a conference paper at ICLR 2022
It is also possible represent edge labels in the current architecture by constructing new graph g' with a vertex We, for every edge (v, u) and edges from v to Wv and from We, to u. The node representation for w., is vector representation for the label on the edge (v, u) (suitably padded for uniformity). Furthermore a new dimension is introduced which separates these new nodes from the old ones and this dimension is set to if the node is W,,a for some (v, u) &g and 0 otherwise. NEUROSED (and NEUROSEDG) can then be trained with such modified graphs as inputs, but using the ground truth SED (respectively GED) for the original graphs in the loss function.
D ADDITIONAL PROOFS
D.1 THE TRIANGLE INEQUALITY OF SED: PROOF OF THEOREM.
Our proof relies two lemmas.
Lemma 3 Let d Σ x + Ri be distance function over Σ. where (i) d(f,, k2) 0 ift and (ii) dil, (2) = d(l,, 22) otherwise; the following holds: SED(GI,, = GED(G), G2), where GED denotes GED with d as the label set distance function. In simple words, the SED between two graphs equivalent to GED with a label set distance function where we ignore insertion costs.
PROOF. suffices to prove (i) SED(GI, 92) 2 GED(GI, G2) and (ii) GED 92) > (2)(
(i Let S = (Vs, Es, Ls) C G2 be the subgraph minimizing SED S) (Recall Eq 3 Consider the mapping from Gi to corresponding
SED(GI, S) (and hence GED 8) as well). We extend to define a mapping म from G1 to G2 by mapping of all nodes in set V2 \ Vs to dummy nodes in 91; the edge mappings are defined analogously.
Under this construction, SED(GI, S) = GED(S), = GEDs (91,92) > GED(GI, This follows from the property that under d, insertion costs are zero, that is d(c, () = 0. Thus, the additional mappings introduced in के do not incur additional costs under d.
(ii) Consider S S G2 and a mapping π from Gi S such that GED,, (G1, S) GED 92). The existence of such subgraph is guaranteed (See Lemma 5 in Supplementary). From the definition of GED, GED,(Gr S) 2 GED S). Furthermore, since S S G2, GED S) > SED(G,, (2).. Combining all these results, we have GED(G,, G2) 2 GED(GI, 2 (2, Hence, the claim is proved.
Lemma 4 d, as defined in Lemma satisfies the triangle inequality.
PROOF. We need to show d(li, fs) < d(Lc, (2) + dg2, Ez). We divide the proof into four cases:
(i) None of f,. Zg, ly is c. Hence, d((2, f3) d(f1, 1, E3) and the triangle inequality is satisfied.
(ii) E = e. The LHS is 0 and hence the triangle inequality is satisfied.
(iii) 61 * and la = e. LHSS and RHS= 1. Hence, satisfied.
(iv) Only & = e. Here, LHS=1 1 and RHS² 1.
These four cases cover all possible situations and hence, the triangle incquality is established.
From Lemma 3 we know SED(GI, G2) = GED(GI, G2). Combining Obs. 3 with Lemma
GED
satisfies the triangle inequality. Thus, SED satisfies the triangle inequality.
D.2 PROOF OF LEMMA 5
Lemma 5 There exists subgraph S of G2 and node map т from G1 to S such that GED, GED(GI, Gz).
PROOF, Let T' be node map from Gi to G2 corresponding to GED(G,, G2). Let hj...... f/ be the nodes of G2 which are inserted n'. Construct subgraph S of G2 by removing nodes h-, by and their incident edges from Gz. Let be the node map from G1 to S which is obtained by removing h4. hf from the domain and hı. hy from the co-domain of Since insertion costs are 0 in d and ग contains only non-insert operations, then GG), S) GED G2). Hence, the claim is proved.
Corollary There exists nearest subgraph (Def. 6 8 91 in G2 such that S C 91.
14

---

Under review as a conference paper at ICLR 2022
Symbols
Descriptions
The set of nodes
The set of edges
The labeling function over nodes and edges
Σ
The universe of all labels
The special empty label
[(v)
The label of node e
[(e)
The label of edge e
The node mapping (bijection)
GFD
The graph edit distance
SED
The subgraph edit distance The distance function over the label set
Go
The query graph
GT
The target graph
Table 6: Frequently used symbols
PROOF. The node map in the above proof contains only non-insert operations. So, S in the above proof a subgraph of G1 ignoring node and edge labels. Since equality holds Lemma 3 this и gives optimal edit distance. Thus, S in the above proof is also nearest subgraph to G1 in G2. D
D.3 MORE GENERAL DISTANCE FUNCTIONS
GED and SED can be viewed as error-tolerant graph and subgraph matching respectively. In practice, the edit costs are used to model the acceptable deviations from ideal graph patterns. The more tolerant we are towards certain kind of distortion, the smaller its corresponding edit cost. Concrete values for the edit costs are application-dependenn In this paper we have discussed binary distance functions which impose a cost of for unequal labels and 0 for equal labels as these are the most popular distance functions used in literature. However our framework is also suitable for more general distance functions.
The results for GED directly extend any metric distance function over the label set. The relevant proofs mentioned in the paper are directly applicable.
The results for SED can be extended to metric distance functions d over Σ for which replacement is no more expensive than deletion, i.e. d(fi, f2) S d(Li,e)Vl,, v),,,, & E Σ. A replacement can be seen compound edit operation consisting of deletion(s) followed by insertion(s). If replacement cost is too high, replacement can be better achieved by deletion(s) followed by insertion(s), of which insertion(s) do not contribute to the cost in SED, Hence, this assumption is general enough to capture large class of interesting distance functions which might be used for the SED prediction task. We show a generalization of Lemma such distance functions d. The other proofs mentioned in the paper are directly applicable.
Lemma 6 Let d Σ x + RJJ be a metric and d(L2, 12) S d(f),c)Vl,, E E. As in Lemma 3 let d Σ d((1,6)) = d(1,, 62) otherwise. Then, d satisfies the triangle inequality.
RJ be distance function over E, where (i) d((i, i c, and (ii)
PROOF. We need show dsl)) s d((), + 2(l2, Consider the three cases:
(i) f = c. LHS = 0, RHS d(L2, E3) 2 0 by non-negativity of d. Hence, LHS < RHS.
(ii) 81 # and fg c. LHS d(E,, f2), RHS d(Li, e). Hence, LHS < RHS by assumption.
(iii) l * and & # e. LHS = d(l,, RHS = d(E: E2) + d(2,, fa). LHS < RHS by triangle
inequality for d.
These cases cover all possible situations. Hence, triangle inequality is established.
D.4 DATA AUGMENTATION
Observation 4 Let S be a nearest subgraph (Def. 6 of G1 in Gz. Let S' be subgraph of G2 which is also a supergraph of S. Then S is also a nearest subgraph of &n in S' and SED(G, S') SED(G1, G2).
15

---

Under review as a conference paper at ICLR 2022
PROOF. The set of subgraphs of S' is subset of the set of subgraphs of G2. S achieves the minimum GED(GI,S) among all subgraphs of G2 and so also the minimum GED S) among all subgraphs S'. Thus, SE" SED(GI,
G))
Observation gives a natural strategy for data augmentation. Once we have SED (22 and nearest subgraph 8 from the expensive non-neural computation of GED(GI, 92), (9,,S,, (ED(91,92)) for all S - S'' C 92 as training examples.
D.5 THE TRIANGLE INEQUALITY FOR F
This is referred to in the proof for Lemma
[
Lemma 7 F(Zga Zgr) < F(Zge Zgn)) + F(Zg,r Zgr), where F(x,y) |ReLU(x y)ll for any monotonic norm ||-1|-
R We observe that (ReLU(x) + ReLU(y)); ReLU(X); + ReLU(y); ReLU(x;) + Ry, 2 RxLU(x; +.) = (ReLU(x y)) Since ||-|| is monotonic, this implies (eLU(x+y)))
PROOF. Let y
[ReLU(x] ReLU(y)
Using the triangle inequality for ||-I|, we get [[RLLU[]]|+[[eLUj]]] > -RLLU()))RLU(()) 2 |ReLLU(x + I)
Substituting Zge Z Zg, Zg,, we get, [ReLL Zg,,, )ll + ||ReLU Ze, )l 2 [eeL Zgy)l )1
y=
This implies that F(Zge Zo) + F(Zg,, Zgr) 2 F(Zge Zgr) Our claim is proved.
E FURTHER CHARACTERIZATION OF F.
Let E: + Rd, where G is the space of graphs, be the learned embedding function and F Rd x IRd + IR be the embedding space prediction function. We aim have the graph space prediction function P G G + R, defined by P(G, H) = F(F(G), E(H)), be able to approximate SED G x G IR in the best possible way, while preserving the key theoretical
properties listed below:
H) 0 SED(G, H) = = GCH
(10)
(11)
SED(G, H) S + SED(T, +
(12)
We allow E to be arbitrary. Then, P satisfies the analogous properties
P(G, H)
(13)
P(G,H)&P(G.TT) P(T.))
(14)
if and only if F satisfies
Flg.h)20 F(g, < Flg, () F(G,)
(15)
(16)
C {0.1) (s H) [[vi: [ E(H)[:]]] Ps is motivated by NEUROMATCH (Rex et al. 2020) where a subgraph prediction function of this form satisfies the key properties of subgraph transitivity, anti-symmetry, intersection set and non-trivial intersection. Hence, P must
For the analogue to property in Eq. we first define the subgraph prediction function Ps
isomorphism:
satisfy:
P(G, H) 0
+ Ps(G. =1
(17)
Again, E being arbitrary, Eq.
17 holds if and only if, F satisfies:
F(g. h) = - Vi gfll < hl]
(18)
18 is acceptable in our framework. However, it is not trivial to characterize such functions. To show complete constructive characterization add two important
Any F that satisfies Eqs. 15
16 and
properties in our desiderata for F. To motivate these propertics, we first discuss about F, in GED and then SED.
16

---

Under review as a conference paper at ICLR 2022
E.1 GED:
For GED, require the following three properties:
Fglg.h) h) 2 0
(19)
0 - : [[1]
=0
(20)
Fo ()
(21)
With these properties in Eqs. characterization of metries not trivial. To achieve this, we establish an important connection of
19 20 and 2T F, is a metric. However, giving complete constructive
metrics on vector spaces to norms. Every norm |I-I gives metric (Ir, v) + || vll- Moreover for a metric, there exists a norm ||-I| such that the metric can expressed as (æ, y) + || - yll, if and
only if the metric is translation invariant and homogeneous. Thus, we add these properties to the desiderata for Fg:
Fgl k
(22)
= (r
(23)
Observation 5 The followings give complete constructive characterization of Fg satisfying Eqs.
19
23
Fg is (x. + || - for some norm ||-||| over the vector space TR. For any norm ||-|] over the vector space B.d, (x. y) + || yll a valid Fg-
Hence, the L2 norm is natural choice because it is isotropic (i.e. direction/rotation invariant).
E.2 SED:
For SED, we add translation invariance and non-negative homogeneity to the desiderata, to make a complete constructive characterization feasible:
Fl = F(g, Vk E Rd
(24)
F(rg.rh) = FFg h). Vr E R
(25)
Note that non-negativity of r in Eq. 25 necessary to be consistent with Eq. If is negative, then with r = 11, we will have x
F(z, v) = 0 F(-r,
S
-y = y. which is contradiction for x * y. For these two properties, translation invariance and non-negative homogeneity, we provide intuitive interpretations the context of SED, The translation invariance would imply that if graphs G and И are modified in the same way then the SED(G, H)) will be preserved. The positive homogeneity would mean that if the costs are scaled by a positive factor, then the SED is also scaled by the same positive factor.
From Eq. 24
we have F(g. h)
Flg 0) p(g h), where p Rd - R defined as and 25 are satisfied if and only if:
p(x) = F (z. 0). Then Eqs. and
p(a + v) S p(x) + p(y)
(26)
p(ræ) = rp (x:), E R55
(27)
Here, Eq. 26 reflects subadditivity property and Eq. 27 nonnegative homogeneity, With these properties, is an asymmetric seminorm. Additional ly, Eq. T8 satisfied if and only if:
p(x) > Vi x|| S
(28)
We call this Eq. 28 as rectification property and refer to the seminorms satisfying this property as rectified seminorms.
Our claim is that F satisfies all the desired properties presented earlier, if and only if p is rectified asymmetric seminorm. Thus, we have the following complete characterization for
Observation 6 The followings give complete characterization for F:
17

---

Under review as a conference paper at ICLR 2022
1. Fis (g. p(g- h) for some rectified asymmetric seminorm p.
2. For any rectified asymmetric seminorm p. (g, h) + p(g- - h) is a valid F.
Now, we describe the following characterization for p. Recall that in d-dimensional vector spaces, asymmetric seminorms are in one-to-one correspondence with convex sets containing the origin. Specifically, every asymmetric seminorm p corresponds called the dual unit ball of p. Furthermore, p and B are related as follows:
convex set B, containing the origin,
p(z) = sup 2 #EB
(29)
Additionally, p is symmetric and only if B is symmetric about the origin and is positive definite (i.e. p(r) = x = 0) if and only if B contains the origin in its topological interior. Note that monotonic norms are also asymmetric seminorms.
Lemma (Rectified dual unit ball) Eq. 28 holds if and only if B satisfies the following:
V2 B vi: 2
(30)
In other words, the necessary and sufficient conditions say that B lies completely in the positive orthant.
PROOF.
1.
If 2|1] 0 for some i and some B, then taking in the negative orthant, with zfd having a sufficiently large magnitude, gives positive 2 . I, which leads to a positive p(z),
contradicting the requirement that p(æ) = 0 when Vi xrii] s O.
2. ( [4] II If & B : Vi =[i] 2 0, then for any x in the negative orthant, = S 0, V2 E B.
E B, so the upper bound of 0 achievable, hence p(z)
Note that, Lemma 8 implies that the origin at the boundary of B, which negates the positive definiteness of p. Hence, every valid can be constructed by first choosing a convex set B in the positive orthant of IRd and then defining p(z) using Eq. 29 Conversely, any such construction
gives valid However, depending on B, it may not be al wlwss be feasible to simplify or solve the optimization problem of Eq. 29 In the special case where is restricted to polytopes, Eq. 29 is Linear Program. With recently proposed differentiable Linear Programming layers, B could be learnt in an end-to-end fashion via backpropagation (with non-negativity constraints on the variables to enforce the positive orthant). However, this adds more parameters to learn and hyperparameters to tune, and makes training and inference significantly costlier. Instead we add a different, and arguably milder, restriction on B. to get closed form for Eq. 29 in terms of norms. Specifically, we assume that is such that mirroring it on all orthants results in a convex set. Not surprisingly, this closed form coincides with the form of F used in the paper. This establishes that our embedding space prediction function is a natural choice for modelling STDD.
First, we show characterization for the dual unit ball of a monotonic norm. Recall that norm |IIll on the vector space Idd is said to be monotonic if (Vi |a'[o]| Z [x[l]] = ([|='|| 2 ||=]])) This characterization allows to construct the dual unit ball of rectified asymmetric seminorm p from the dual unit ball of a monotonic seminorm [|-I], and vice versa, such that p(z) = ||maz(() (0, x|
Lemma Let II-I| be a norm over Rdd Let B' be its dual unit ball. |||| is monotonic if and only if the following holds: Vx Vi 2[i]=[i] 2 0, where, E arg max B E.
PROOF.
for some and x. Wlog, assume æ1i]] > Then, by assumption, 2[i] < 0. Construct x' by replacing œ[i] in x' with æ+i]] + A, with A > 0. Let z' E arg e z' x'. By continuity, for sufficiently small A, there a z', which is arbitrarily close to In particular, for such A, = < 0. This gives z' x' z' x. But monotonicity gives z'-x' 2 2 x and maximality of z for x gives 2 x 2 2 x. which on chaining give 2''x' 2 This contradicts the previous inequality.
(=) ) Assume that =[i]=[ii]
2.
Consider x and x' with |x[|]] S
[ Vi. Let 2 E arg max 2 x, such that | Hence, ||-I| is monotonic.
+ 2 0, Vi. Then || > x 22-1-
18

---

Under review as a conference paper at ICLR 2022
Lemma 10 Let |I-II be a monotonic norm. Then x
+ max((0, x) is a rectified asymmetric
seminorm.
PROOF. Let B' be the dual unit ball of monotonic norm ||- Let B be the positive orthant of B'. Clearly B is convex and contains the origin, so let be the dual umit ball of rectified asymmetric seminorm p (see Lemma 8). We show that max(0, = p(z), which completes the proof.
max (0, .)
sup 2- (0,
=E
sup z 10.am0a000p max (0, 2
=EB
supp222 .
=EB
p((2)
Here, max(0, x²) 2 0. as by Lemma 9 it suffices to consider z's in the positive orthant, where B
coincides with B'. Additionally, for r the supremum is 2|0] 0; max(0, z) coincides with x at i: x[i] 220 0.
Lemma 11 Let p be rectified asymmetric seminorm with a dual unit ball B such that mirroring B on all orthants results in convex set. Then is + max(0, x) for some monotonic norm ||-||
PROOF Let B be the dual unit ball of p. Let B' {= : |æ| E B}. B' is convex (by mirroring assumption), symmetric about the origin, and contains the origin in its topological interior (except in degenerate cases which we ignore), so B' is the dual unit ball for a norm ||-I|- For any x, let E arg m 2. and consider z' obtained from by keeping the magnitudes of 2[i]'s but taking the sign of x[i]] s.. By construction z' E B', and z' x 2 = I. which gives 2' E arg maxzer' z a. So by Lemma 9 |1-I1 is a monotonic norm. Now, B the positive orthant of B", so by the reasoning max(0, 2). and it completes the proof.
of Lemma
10
Discussion: Lp norms are natural choices for the monotonic norms ||-||- For L1 norm, the dual unit ball is a hypercube with side length 2 units and centered at the origin. For L2 norm, the dual unit ball is a hypersphere of unit radius centered the origin. The dual unit balls of the corresponding rectified asymmetric seminorms are simply the positive orthants of the hypercube and the hypersphere respectively, which easily satisfy the mirroring assumption. We choose L2 norm because of it's isotropy, although other Lp norms are also likely to work as well as the Le norm. In fact, any rectified asymmetric seminorm whose dual unit ball obtained by taking the positive orthant of monotonic norm's 's dual unit ball will satisfy the mirroring assumption, and will therefore be expressible in the form max (0, |-
COMPUTATION COST OF SED AND GED INFERENCE
For this analysis, make the simplifying assumption that the hidden dimension in the Pre-MLP, GIN and Post-MLP are all d. The average density of the graph is The number of hidden layers in Pre-MLP, and Post-MLP are L, and k in GIN.
The computation cost per node for each of these components are as follows.
Pre-MLP: The operations in the MLP involve linear transformation over the input vector x,, of dimension [S) followed by non-linearity. This results in ([V) d L)) cost.
Gin: GIN aggregates information from each of the neighbors, which consumes O(d g) time. The linear transformation consumes an additional ((d2) time. Applying non non-linearity takes ((d) time since it a linear pass over the hidden dimensions, Finally these operations are repeated over each of the l hidden layers, results in total (kd(d2 + dg)) computation time per node. Across, all nodes, the total cost ( + |g| kd) time. The degree g terms gets absorbed since each edge passes message twice across all nodes.
Concatenation: This step consumes (kkd) time per node.
Pool: Pool iterates over the GIN representation of each node requiring O(V)dk) time.
Post-MMP: The final MLP takes dk dimensional vector as input and maps to a d dimensional
vector over T. layers. This consumes (kkd + d² d?T.) time.
19

---

Under review as a conference paper at ICLR 2022
Combining all these factors, the total inference complexity for graph is (( d' of kdf) [E (ldd). This operation is repeated on both the query and target graphs to compute their embeddings, on which distance function FF is operated. Thus, the final cost is ((n( + da L kd?) mkd), where n = [Vol= + [ and m = [Eg] + |-
G PIPELINE DETAILS
Additional Model Details: We use residual connections across blocks of two GIN convolution layers. This cases the flow of gradients to the earlier layers by skipping the intermediate non non-linearities. We observed about 5x speedup convergence and a marginal improvement in the generalization error with residual connections. We use 8 layers, 64 hidden dimensions and 64 embedding dimensions. We use a single layer for pre-MI.P and layers with ReLU non-linearee for the other MI.P's.
We generate training data under two different settings (described in $ 4). SHD computation is NP-hard, and to the best of our knowledge, there is no existing method which computes SED directly. Therefore, we generate the ground truth SED using existing methods on GED by leveraging Lemma which establishes the relationship between SED and GED. More specifically, time limited mixed integer programming method MIP-F2 (Lerouge et al. 2017), which provides us with the best so far lower bound and upper bound for SED. The time limit is kept at 60 seconds per pair. Each pair is run with 64 threads a 64 core machine. This gives sufficiently tight bounds (with exact values for a large majority of pairs). For evaluation, we use SED = (LB UB)/2 the ground truth, where LB and UB are the lower and upper bounds respectively. Fig. presents visualization of tightness of SED bounds.
Data generation:
0.05
0.4
0.0050
0.2
Range
0.2
0.0025
0.1
0.00
0.0
0.0000
0.0-
0.0
25
SED
(a) PubMed
(b) CiteSeer
(c) AIDS
(d) Protein
(e) Cora_Mi ML
Figure Mean Relative Error Generated Data. Here Range UB LB, and SED (LB + UB)/2
The queries for AIDS constitute of known functional groups. They have been compiled from Table in "Mining statistically significant molecular substructures for efficient molecular classification S Ranu, AK Singh Journal of chemical information and modeling, 2009."
Real queries for AIDS:
Loss Function: While Zgo and ZG, be the embeddings for the query graph Go and target graph Gr respectively, we use the following function (for training):
(F(Zgo Zg,) u
F(Zgo ZZ
HiZgo (,)
0, (1 - F(Zge, Zor))²
1 F(Zga Zgr) S u F(Zg, Zot) <
where and u are the lower and upper bounds to SED in our generated data. With H, the parameters of the entire model are learned by minimizing the mean squared error.
L
Σ
H(Zggs Zgr, u,
(31)
ST..)ee
Here, T is the set of all training samples.
Training details: NEUROSED, NEUROSED-NN and NEUROSED-Dua were trained using the AdamW optimizer with a weight decay of 10-3, A batch-size of 200 graph pairs per mini-batch was used. The learning rate schedule was cyclic. In each cycle, learning rate was increased from 0 to 10-3 for 2000 iterations and then decreased back to 0 for 2000 iterations. Training was stopped when the best validation loss did not improve for 5 cycles. We observe that cyclic learning rate schedule usually gives faster and better convergence than the other attempted training schemes. A cyclic learning rate schedule allows using higher learning rates and thus speeds up training. It offers some regularization due to the high learning rates seen in each cycle encouraging the optimizer to find flatter regions of minima, giving better generalization. It is also robust to syper-parameter settings.
20

---

Under review as a conference paper at ICLR 2022
Subgraph search via neighborhood decomposition:
For large target graphs, it infeasible to compute the SED. In this paper. we proposed a neighborhood decomposition scheme to handle subgraph similarity queries in the following setting: compute the SED between the query and the λ-hop neighborhood centered at each node in the target graph for some suitable k. The minimum SED thus computed can be considered as approximation for the true SED. Ideally, such an SED would be an upper bound to the true SED. In our experiments the minimum SED is usually small. This is expected in general as the large targets graphs are likely to contain small query graphs (or their small variations). Thus the neighborhood decomposition is satisfactory for SED computation between small queries and large targets in practice. One practical advantage of using neighborhood decomposition is that it facilitates locating the region of the target graph where the nearest subgraph is found. We rank these neighbourhoods and that allows us to consider regions of the target graph in order of relevance. This generates much smaller candidate sets and traditional expensive methods can be used to refine these candidate sets further.
In this section, we seek to give further insight into the efficacy of neighborhood decomposition and design guidelines for choosing the right value of depending on the expected query distribution. In practice, we are concerned only with connected subgraphs. Assuming that all the nearest subgraphs (Def. 6) are connected leads to the following result:
Theorem 3 Assuming that the nearest subgraph to the query is a connected graph, a nearest subgraph S to G1 in G2 can be found in an 1/2-hop neighborhood No, centered some v E Vç2 where is the length of the longest path in G1.
PROOF. By Corollary I there exists nearest subgraph S of G1 in G2 which is also subgraph of G1 ignoring node and edge labels. So, the diameter is I the length I of the longest path in G1- Since S C 92. S is contained in some 1/2 neighborhood of G2-
0
Finding the length of the longest path is NP-hard. However, we do not need to find the exact length of the longest path: any upper bound suffices. Moreover we do not even need the length of the longest path for I. The nearest subgraph having a diameter equal to / is rare. In practice, the diameter of the nearest subgraph is unlikely be much higher than the diameter of the query itself.
In conclusion, subgraph similarity search suffers from the problem of an exponential search space of subgraphs. We resolve this issue two ways: the neighborhood decomposition allows us to consider a number of subgraphs linear in the number of nodes in the target, all of which are much smaller than the target graph itself. Second, our neural model learns to predict the SED directly with the small neighborhood sizes which make training data generation as well as neural processing using GNNs computationally feasible.
H DATASETS
Dblp:
Dblp is a co-authorship network where each node is an author and two authors are connected by an edge if they have co-authored a paper. The label of node is the venue where the authors has published most frequently. The dataset has been obtained from https://www www.wwww.eea....mm..mm.. ortphiitatro//oiiiiinnoo
Amazon:
Each node in Ama represents a product and two nodes are connected by an edge if they are frequently co-purchased. The graph is unlabeled and hence equivalent to a graph containing single label on all nodes. The dataset has been downloaded from (Leskovec & Sosić 2016)..
PubMed: PubMed dataset is a citation network which consists of scientific publications from
PubMed database pertaining to diabetes classified into one of three classes.
Protein: Protein dataset consists of protein graphs. Each node labeled with a one of three functional roles of the protein.
AIDS: AIDS dataset consists of graphs constructed from the AIDS antiviral screen database. These graphs representing molecular compounds with Hydrogen atoms omitted. Atoms are represented as nodes and chemical bonds as edges.
CiteSeer is citation network which consists of scientific publications classified into one of six classes. Generally a smaller version is used for this dataset, but we use the larger version from (Bojchevski & Günnemann] 2017).
CiteSeer:
21

---

Under review as a conference paper at ICLR 2022
Cora ML: Cora dataset is citation dataset consisting of many scientific publications classified into one of seven classes based on paper topic. Cora __L is a smaller datset extracted from Cora (Bo jehevski & Günnemann, 2017).
AIDS': AIDS' dataset is another collection of graphs constructed from the AIDS antiviral screen database. The graphs and their properties differ from those in AIDS. These graphs also represent chemical compound structures.
Linux:
Linux dataset is collection of program dependence graphs, where each graph is function and nodes represent statements while edges represent dependency between statements.
IMDB: TMDR dataset is collection of ego-networks of actors/actresses that have appeared together in any movie.
We use the same versions of AIDS', Linux, and IMDB used in (Bai et al. 2019).
I EXPERIMENTAL SETUP
Hardware Details: We use machine with an Intel Xeon Gold 6142 processor and GeForce GTX 1080 Ti GPU for all our experiments.
Baselines: Here we describe the changes made to neural baselines to adapt to SED problem.
SIMGNN (Bai et al. 2019): We train the model with La+UB as the ground truth value of SED (LB and UB are lower and upper bounds for SED respectively). Now let G1 be the query graph, and G2
2
GEo G C2) be the target graph, we use nSED(G1: G2) SED(GL instead of nGED(G G2) ( H+ (aal)/2 as the normalized value of similarity in SIMGNN. This is because the absolute value of SED scales with the size of the query, opposed to GED, which scales with size of the query well as the target.
NEUROMATCH (Rex et al. 2020): We use the un-anchored version of NEUROMATCH trained on its original task (subgraph isomorphism decision problem) using its own training framework. For ranking, we use the violation scores it produces directly rather than thresholding the violation and predicting subgraph isomorphism as intended. We change the size limits for sampling query/target graphs in training better fit our data distribution.
Querying for SED: We embed the neighbourhoods of the nodes in the given graph (or set of graphs) and store the embeddings (denoted by set Zg,) accordingly. For a new query Go. we first obtain its embedding Zgo. Based on the stored embeddings Zg., we compute SED(ZGo: Zg,) for all Zg, E Zgr using the function F(Zgo: Zgy). ). We sort the targets based on the obtained SED values and it can trivially answer top-k range queries. From the selected targets one can extract the nearest subgraph by running a traditional algorithm to compute SED and use the returned node mapping to interpret it. An alternative is to choose larger (k', where k >> k) top set and use traditional methods to further filter these. Note that usually the graphs required in the top-k or range queries are much smaller than the total number of targets, using model to filter out the unimportant targets from the target candidate set can save significant amount of resources.
We used Pytorch and Geomeriie for implementation. All experiments were done using Jupyter Notebooks. The full code, notebooks for all experiments and the generated data available on an anonymous github repository
Software details:
License: The provided code and data are licensed under CC-BY-SA.
J ADDITIONAL RESULTS
J.1 OTHER MEASURES FOR PREDICTING SED AND GED
In Section 4.2 we present the accuracy of all techniques on SED and GED in terms of Root Mean Square Error (RMSE). Here evaluate the same performance using several other metrics such as Mean Absolute Error (MAE) and R Tables 7a and /bb show the MAE scores for SED and GED respectively. Tables and 8b present the results based on R²2 results. Consistent with the previous results, NEUROSED outperforms all techniques both in SED and GED in these two measures except
https::/ancnymouut 4open sci wew.eene///eeueoee/
22

---

Under review as a conference paper at ICLR 2022
Methods
AIDS'
Linux
Methods
FubMed
Protein
AIDS
Citeseer
Cora_MM,
Amazon
Dhip
NEUROSED
0.474
0.377
0.432
0.207
NEUROSEDG
0.629
0.318
3.612
H'MN-RW
0.764
0,575
0,366
0.882
0.824
0,400
0.926
M-
0.777
0.534
28.486
II' I'M---E
0.831
0.518
0,510
1.094
0.797
0.465
0.966
H-MN-NE
0.779
0.176
28.182
SIMGNN
0.853
0.855
0.545
1,068
0.841
1.257
0.911
SIMGNN
0.816
0.489
28.082
Brunch
1.692
1986
1.092
2.275
2.277
3.697
2.156
Branch
2,895
2.017
3,303
MIP-F2
1.528
1,264
0.684
1,940
MIP-F2
2.184
0.480
36.460
(a) Prediction of SED.
(b) Prediction GED
Table 7: MAE scores (lower is better) in (a) SED and (h) GED.
Methods ATDS'
Linux
IMDB
Methods
PubMeed
Protein
AT03
CiteSear
Cora_Mi MT.
Amanon
Dhip
NEUROSED
NEUROSEDS
.91
.99
M-MN-RW
97
994
.95
.98
97
.97
94
HºMN-RW
.86
.92
.66
WOMN-NE
97
.6
96
HºMN-NE
.86
.98
.65
SIMGNN
97
.95
.97
.97
.85
SIMGNN
84
.93
.0
Branch
88
.44
82
91
86
43
.75
Branch
-,5
.14
.98
MIP-F2
MIP-F2
-20
.78
.69
(a) Prediction of SED.
(b) Prediction of GED
Table 8: R scores (higher is better, 1 maximum) (a) SED and (b) GED.
BRANCH is competitive only IMDB for GED prediction and MN is better in Linux only for GED prediction.
K PRECISION@A ON K--N QUERIES
Fig. 7 shows Precision&k on k-NN queries. As visible, either NEUROSED comfortably performs better than all baselines or is among the best performing algorithms.
K.1 ADDITIONAL. RESULTS ON ABLATION STUDY
To highlight the importance of GIN, we conduct ablation studies by replacing the GIN convolution layers in the model with several other convolution layers. As visible in the Table TT] GIN consistently achieves the best accuracy. This is not surprising since GIN is provably the most expressive among GNNs in distinguishing graph structures (essential to SED or GED computation) and is as powerful as the Weisfeiler-Lehman Graph Isomorphism test (Xu et al. 2018b).
Impact GIN:
Methods
CiteSeer (SED)
PubMed (SED)
Amazor (SED)
IMDB (GED)
NEUROSED (GIN)
0.519
0.728
0.495
6.734
NEUROSED-GCN
0.556
0.756
0.532
12.151
NEUROSED-GRAPHHSCE
1.364
1.156
1.841
91.312
NEUROSED-GAT
1.294
1.259
1.843
89.034
Table 10: Ablation studies: GIN vs others. RMSE produced by different methods are shown and NEUROSED with GIN produces the best results.
Impact of sum-pool: To substantiate choice of the pooling layer, have performed ablation studies with various pooling functions as replacements for sum-pool. is clear from Table [] that sum-pool is the best choice among the considered alternatives.
23

---

Under review as a conference paper at ICLR 2022
Dotasets
Range (f 2)
10-NN
CPU
GPU
CPU
GPU
L-Scan
M-Tree
L-Scin
M-NN-RW
H-MN-NE
L-Sen
M-Tree
L-toi
HPMN-RW
HONN-NE
0,093
0.044
2666
35.2
0.49
0.25
8760
DB3p
Table 9: Querying time (s) for SED in the three largest datasets. L-Scan indicates time taken by linear scan in NEUROSED (times differs based on whether executed CPU in GPU). M-Tree indicates time taken by NEUROSED when indexed using an adapted Metric Tree.
Pool functions
CiteSecr (SED)
PubMed (SED)
Amazon (SED)
IMDB (GED)
NEUROSED (Sum)
0.519
0.728
0.495
6.734
NEUROSED-Max
0.795
0.709
0.603
52.519
NEUROSED-Mean
0.922
0.732
0.846
52.483
NEUROSED--Atennton
0.914
0.797
0.868
130.47
Table 11: Ablation studies: sum-pool vs others. The sum-pool is the best choice among the considered alternatives.
K.2 ALIGNMENT
In real-world applications of subgraph similarity search, alignments of interest only for small number similar subgraphs. Our framework is intended to serve as filter to retrieve this small set of similar subgraphs from large number of candidates. To elaborate, graph database may contain thousands or millions graphs (or alternatively, thousands or millions of neighhorhoods of large graph) which need be inspected for similar subgraphs. A user is typically interested in only handful of these subgraphs that are highly similar to the query. Since the filtered set is significantly smaller, non-neural exact algorithm suffices to construct the alignments (Lemma 1 allows us to adapt general cost GED alignment techniques for SED alignment). Computing alignments across the entire database unnecessary and slows down the query response time.
To substantiate our claim, we show the average running time for answering 10-NN queries. We break up the running time into two components: (i) k--N retrieval time by NEUROSED, (ii) exact alignment time using MIP-F2 for the 10-NN neighborhoods retrieved by NEUROSED. We observe that exact alignment by existing methods on the 10-NN neighborhoods completes in reasonable time. In contrast, GENN-A does not scale on either PubMed or Amazo since it computes alignments across all (sub)graphs.
Methods
PubMed
Amazon
NEUROSED Retrieval
0.373
6.471
MIP-F2 Alignment
52.8
68.4
Table 12: The average running times in seconds per top-10 query. Our technique is much faster than MIP-F2 alignment.
HEAT MAPS FOR PREDICTION ERROR
In Figures g to 7 we show the variation of the emror on SED and GED prediction with query sizes and ground truth values for NEUROSED (NEUROSEDG for GED) and the baselines on all the corresponding datasets. This experiment is an extension of the heat-map results Fig. 2 in the main paper. These datasets show variations in the distributions of SED and GED values. It is interesting to observe that among the baselines, different methods perform well on different regions (e.g., combinations of high/low SED and high/low query sizes). In the figures, darker means higher error. The baselines do not show good performance on all regions. However, for NEUROSED and NEUROSEDG. see much better coverage for all types of regions in the domain. Furthermore, for every region, our models outperform (or are at least competitive with) the best performing baseline for that region.
24

---

Under review as a conference paper at ICLR 2022
100
100
100
Precision Ok
Precision tak
Precision
90-
Precision
75
80-
50-
264
25+
00-
20
20
10
20
10
20
(a) PubMed-SED
(b) Protein-SED
(c) AIDS-SED
(d) CitteSer--Se
100
100
100
NeuroSED
Precision@ll
80-
Precision
Precision
SimGNN
80
60-
H-MN-RW
80
H
40-
60
NeuroMatch
20
70
10
20
(h) Legend
k
(c) AAISS-SDGBSS
Linux-Grii GED
(g) IMDE-GED
Figure 7: Precision&k on k-NN queries.
25
20
15
10
20
40
40
20
40
40
20
40
0
20
40
SED
SED
SED
SED
SED
SED
(a) NEUROSED
(b) (C HºMN-NE (d) SIMGNN
(e) BRANCH
(f)
MIP-F2
Figure 8: Heat Maps of SED error against query size and SED values for Dblp. Darker means higher error.
M SCALABILITY WITH QUERY SIZE AND GENERALIZABILITY TO UNSEEN LARGER QUERY SIZES
In this analysis, aim analyze the following aspects:
1. Performance on larger query sizes.
2. Generalizability unseen larger query sizes
In Table 13 sheds light on the above objectives. We notice that although there is some deterioration in the quality for query sizes in the range [25, 50] when compared to the entire set, is not severe (NEUROSED-50 in Table 13 However, if we 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 (NEUROSED-22 in Table [3). Nonetheless, NEUROSED 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.
Method
PubMed
CiteSeer
V4 [0, 50]
Vi (25,50)
[0,50]
Vo [25,50]
V4 (0,50)
Vi '25, 50)
NEUROSED-50
1.294
1.917
0.728
0.948
0.638
0.782
NBUROSED-25
2.824
4.999
4,740
9.052
1.152
1.724
MIP-F2
3.507
6.278
4.831
8.505
6.454
10.293
Table 13: RMSE of prediction quality. NEUROSED-50 indicates NEUROSED trained dataset containing queries size up 50. NEUROSED-25 defined analogously.
25

---

Under review as a conference paper at ICLR 2022
20
Query
10
5
SED
SED
SED
SED
SED
SED
(a) NEUROSED (b) (N MN-NE (d) SIMGNN
(e) BRANCH
(I) MIP-F2
Figure 9: Heat Maps of SED error against query size and SED values for Amazon, Darker means higher error.
15
20
SED
SED
SED
SED
SED
SED
(a) NEUROSED (b) (CM HºMN-NE (d) SIMGNN
(e) BRANCH
(f) MIP-F2
Figure 10: Heat Maps of SED error against query size and SED values for PubMed. Darker means higher error.
VISUALIZATION AND APPLICATION OF SED
Searching for molecular fragment containment is a routine task in drug discovery (Ranu et al. (011 Motivated by this, show the top-5 matches
SED query on the AIDS dataset produced by NEUROSED in Fig. 18] The query is functional group (Hydrogen atoms are not represented). NEUROSED is able extract chemical compounds that contain this molecular fragment (except for ranks 3 and 5, which contain this group with edit) from around 2000 chemical compounds with varying sizes and structures. This validates the efficacy of NEUROSeD a semantic level.
ALTERNATIVE QUERY DISTRIBUTIONS
In RWR, perform fixed length random walks, where the length of walk is the average diameter size the queries generated through BFS during training. Next, we merge the walks to form graph.
In Rw, perform random walks, till the diameter of the resultant graph is the same the average diameter of the BFS sampled train graphs.
The details of the SHADOW sampler is explained in Zeng al. (2021
26

---

Under review as a conference paper at ICLR 2022
25
Querya
40
20
20
20 SED
SED
SED
SED
SED
SED
(a) NEUROSED (b) M (c) MN-NE (d) SIMGNN
(e) BRANCI
(f) MIP-F2
Figure 11: Heat Maps of SED error against query size and SED values for CiteSeer. Darker means higher error.
Query Size
15
5.
SED
SED
SED
SED
SED
SED
(a) NEUROSED (b) (c) H-MN-NE (d) SIMGNN
(e) BRANCH
(f) MIP-F2
Figure 12: Heat Maps of SED error against query size and SED values for Cora ML. Darker means higher error.
25
15
49
20
SED
SED
SED
SED
SED
SED
(a) NEUROSED (b) H (c) M (d) SIMGNN
(e) BRANCI
(f) MIP-F2
Figure 13: Heat Maps of SED error against query size and SED values for Protein. Darker means higher error.
14
Query
10.
8-
10
20
20
20
20
20
10
20
SED
SED
SED
SED
SED
SED
(a) NEUROSED
(b) (C H'MN-NE (d) SIMGNN
(e) BRANCH
(f) MIP-F2
Figure 14: Heat Maps of SED error against query size and SED values for AIDS. Darker means higher error.
27

---

Under review as a conference paper at ICLR 2022
10
Query Size
6-
910
6
000910104046
08-000004400
+0
00:0/000009
2
0-0-0
10
20
30
20
10
20
10
20
10
20
30
20
GED
GED
GED
GED
GED
GED
NEUROSED g (b) (CMN-RW(C) HºMN-NE (d) SIMGNN (e) BRANCI
(f) MIP-F2
Figure 15: Heat Maps of GED error against query size and GED values for AIDS'. Darker means higher error.
10
Query Size
010102001
10
13
10
10
10
15
GED
GED
GED
GED
GED
GED
(a) NEUROSED g. (b) (M HºMN-NE (d) SIMGNN
(e) BRANCH
(f) MIP-F2
Figure 16: Heat Maps of GED error against query size and GED values for Linux. Darker means higher error.
28

---

Under review as a conference paper at ICLR 2022
20
20
Query
15
10
10
40
20
20
20
GED
GED
GED
GED
GED
GED
(a) NEUROSED (b) (C HºMN-NE (d) SIMGNN
(e) BRANCH
(f) MIP-F2
Figure 17: Heat Maps of GED error against query size and GED values IMDB, Darker means higher error.
29

---

Under review as a conference paper at ICLR 2022
(c) Rank 2 (d) Rank 3 Figure 18: Visualizations of query and resulting matches produced by NEUROSED. Red, Green and Yellow colors indicate Carbon, Nitrogen and Oxygen atoms respectively. The actual and predicted SED for the target graphs are (b) 0, 0.4, (c) 0, 0.5, (d) 1, 0.6, (e) 0, 0.6 and (f) 1, 0.6.
(a) Query (b) Rank
(e) Rank 4
(f) Rank
30


Reviews:
[{"review_id": "svD6eW0rm9I", "reviewer": "Reviewer_gqTK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My minor concerns are:\n\n1). Some notations are not used after definition. For example, what is π? I can only find the definition in the appendix PROOF OF LEMMA 5. This will make the reader hard to follow. Please check all notations and make sure all usage happens after a clear definition.\n\n2). Missing some related work, such as the following one. [1] uses random walk sampling paths and model the graph as a set of paths to measure the distance between graphs.\n[1] Inductive and unsupervised representation learning on graph structured objects\nL Wang, B Zong, Q Ma, W Cheng, J Ni, W Yu, Y Liu, D Song, H Chen, ...\nInternational conference on learning representations, 2020\n\nBesides, the following paper although is cited, it is suggested to discuss the superiority of the method over the work listed below in the introduction or related work section.\n[2] Rex Ying, Andrew Wang, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec NEURAL SUBGRAPH MATCHING \n\nMy major concerns are the draft includes too many typos and grammar errors, I listed some. Please fix all.\n typos:\nL(v) and L(e) denotes==>L(v) and L(e) denote\nsatisfies triangle inequality==> satisfies the triangle inequality\nAn edit can be addition or deletion ==>An edit can be the addition or deletion \nthat G1 is subgraph isomorphic==>that G1 is a subgraph isomorphic\nit satisfies triangle inequality==>it satisfies a triangle inequality\nhigh generalisation accuracy==>high generalization accuracy\ndenote a labelled==>denote a labeled", "summary_of_the_paper": "The submission proposed to use GNN to encode graphs and calculate graph edit distance and subgraph edit distance based upon supervised learning with the generated graph embeddings. ", "summary_of_the_review": "In general, the idea is novel and interesting. The authors also provide proof of the properties of the proposed metric. Basically, SUBGRAPH search and matching is an important problem. The work well validated the effectiveness to use GNN for this problem. I weakly champion the acceptance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ezpB2buvbe", "reviewer": "Reviewer_L1VP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points:\n\n- The paper is well presented and organized. It is easy to follow with adequate examples.\n\n- The ideas are intuitive and technically sound, although alternative or even better solutions could exist.\n\n- There is a good balance of empirical and theoretical results.\n\nWeak points:\n\n- The paper emphasizes a lot on the ability to preserve theoretical properties. But these theoretical properties are direct consequences of the prediction function, and has nothing to do with the rest of the model (e.g. the siamese network, the GNN layers). In theory, any neural network architecture, followed by the same prediction function, would preserve these theoretical properties.\n\n- The prediction function is manually crafted. Why not make it learnable? In theory, an MLP can universally approximate any continuous function in a specified input range--- which could automatically discover the right prediction function, including the proposed handcrafted function. To improve learning, as a prior, some regularization can be added to guide the MLP toward the theoretical properties.\n\n- Some important neural baselines are missing for SED. \n\n[a] Neural Subgraph Isomorphism Counting. KDD2020.\n\n[b] Subgraph Neural Networks. NeurIPS 2020.\n\nBoth are based on graph neural networks. Although they are not for SED, they are for subgraph isomorphism counting, the difference only lies in the loss function. If they are replaced with the same loss on SED, they can be reasonable baselines.\n\n- The pair-independent advantage is not unique to this method (see [a]). Moreover, it may not be that useful. First, it is only applied at inference time, which is typically fast for neural networks. Second, this only applies to cases where query/graph repeatedly appear in different combinations from a fixed pool. In cases where each incoming query/graph is new, the model has to compute their embeddings on the fly anyway. \n\nMinor issue:\n\n- F are sometimes used instead of \\mathcal{F}.\n\n--- update after rebuttal ---\nI see some valid points in the rebuttal, hence upgrading the score.", "summary_of_the_paper": "The paper addresses the problem of graph/subgraph similarity search in terms of the edit distance, termed GED/SED, respectively. Unfortunately, both GED and SED are NP hard, with exponential search space, making the cost prohibitive on even moderately large graphs/queries. Instead, the authors apply a neural network based approach, by designing a siamese graph neural network called NEUROSED. In particular, NEUROSED is able to preserve theoretical properties of  SED/GED, such as triangle inequality, through a purposely designed prediction function. Experiments are conducted on real graph datasets for both SED and GED, which evaluates the effectiveness and efficiency of GED/SED.", "summary_of_the_review": "Based on the weaknesses stated above, the handcrafted prediction function is the key but there may be better alternatives. Additionally, other subgraph-based GNN can be easily ported over to solve the SED problem.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OAmOQN6sME", "reviewer": "Reviewer_ECCJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. Simple yet effective approach for estimating the SED from two graph embeddings.\n2. The adopted score function Eq. (6) can preserve SED's properties of nonnegativity, subgraph identity, and triangle inequality, which is theoretically proved.\n3. Solid experiments show state-of-the-art performance and orders of reduction in computation time.\n4. The writing is clear. The paper is easy to follow and demonstrates the key insights very well.\n\nWeaknesses:\n1. Equation (6) seems the key technical innovation of the proposed model, which seems a bit simple and appears to be the same one as in Neural Subgraph Matching [1]. Although theoretical analysis is given to show it satisfies three properties in Lemma 1. However, it should not be the only one satisfying the three properties. Then why is Eq. (6) exclusively better? Is it possible to improve (6) further? A discussion of [1] should also be included.\n2. The title of Table 4 is too close to Table 5, making it look like the title of Table 5. \n\n[1] Lou, Zhaoyu, et al. \"Neural Subgraph Matching.\" arXiv preprint arXiv:2007.03092 (2020).", "summary_of_the_paper": "This paper presents a simple and effective model for subgraph similarity search. Two GNNs with shared weights are applied first to get the graph embeddings of the query and target graphs. Then, instead of using an MLP over the concatenated graph embeddings to regress the subgraph edit distance (SED) score, the paper proposes to use the l2 norm of the positive portion of the difference between two embeddings. This inductive bias is proved to preserve SED's triangle inequality property, and shows better accuracy and generalization power for large graphs. Experiments show the proposed model outperforms state-of-the-art neural approaches in both graph similarity search and subgraph similarity search tasks.", "summary_of_the_review": "Considering the strong empirical performance and the theoretical guarantee, I recommend an acceptance. My only concern is the possible limited technical innovation in Eq. (6), which desires more in-depth analysis and discussion. Besides, it already appears in previous papers and a discussion is lacking.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "8q-CSU-jn6s", "reviewer": "Reviewer_Y8L2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- Efficiently computing SED is a vital problem. NeuroSED is a promising model that supports accurate and fast computation. It is a good contribution to the SED field.\n- The learned embeddings hold key properties of SED, such as triangle inequality. These embeddings also support indexing strategies for fast prediction.\n- Extensive experiments show how NeuroSED is a better choice than SOTA neural and non-neural methods. Sufficient ablation studies on each component of NeuroSED give evidence of why NeuroSED works.\n- The paper is fairly well written.\n\nWeaknesses\n- Technique contribution is limited.\n  * Although the paper argues the model is inspired by Siamese networks, it is indeed just using a shared GNN to encode both target and query graphs. In the field of combinatorial optimization, encoding graphs using GNN is straightforward and not new (Cappart et al., 2021).\n  * Besides, NeuroSED is very similar to Neural Subgraph Matching (NeuroMatch, Lou et al., 2020): both models use a shared GNN to encode target and query graphs, the learning metric of NeuroSED is simply the violation penalty in NeuroMatch. NeuroMatch also studies subgraph relations in terms of subgraph embeddings as in this paper. From this regard, it seems like NeuroSED merely adopt NeuroMatch to compute SDE. Clarifications are needed.\n\n- An advantage of neural methods over heuristic methods is the ability to efficiently predict large graphs. However, it is unclear how to extend the model to predict large graphs accurately.\n\n  * The model is supervised, but obtaining training data for SED in practice is nontrivial. NeuroSED has to train on small target and query graph pairs with labels computed from a mixed integer programming (Lerouge et al., 2017), which is at high costs and not scalable to large graphs. As a result, training NeuroSED on large target and query graphs may be infeasible.\n\n  * If NeuroSED trains on small graphs and predicts on large graphs, the prediction performance can be bad due to the extrapolation capacity of GNNs (Xu et al., 2021).\n\n  * The experiments are limited to small target and query graphs with graph diameters at most 10. Showing the performance on large graphs is necessary.\n\n- The constructed training data may have a different distribution than test data distribution in real-world applications. The training data is a collection of (target graph, query graph, label) triples, where the query graph is generated using BFS traversal on target graphs. In practice, the underlying query graph distribution can be unknown and be much different from these BFS traversal samples. Then the training distribution is different than the test distribution, making the trained model not generalized to test data.\n\n- Pair-independent embeddings condense the target/query graph into a single vector seems to be too simple. It pushes much burden on the expressiveness of GNNs. GNNs are forced to summarize the target graph according to a large amount of query graphs. However, GNNs may not be that flexible, e.g., it is difficult for GNNs to identify simple substructures (Chen et al., 2020). It would be better to understand what features are captured in the trained GNN embeddings and ensure the pair-independent embeddings are sufficient for SED.", "summary_of_the_paper": "The paper proposes a supervised model, NeuroSED, to compute Subgraph Edit Distance (SED) (and Graph Edit Distance (GED)). To this end, given two graphs, target and query graphs, NeuroSED uses a shared GNN to encourage embeddings for both graphs representing similar topological features. Then a dedicated learning metric w.r.t. SED is introduced to ensure the learned embeddings hold key properties of SED and the embeddings are indexable. The indexable embeddings further support fast prediction. Extensive experiments show NeuroSED significantly improves SOTA methods.", "summary_of_the_review": "I think there is still room to improve the paper. The model seems reasonable, and the experiments show promising results under specific settings. However, the technical novelty, strategies of generating training data, and the ability to generalize the model to large graphs are not well discussed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new method for subgraph similarity search by learning embeddings via a GNN-based approach to reflect the edit distance between subgraphs. Reviewers highlighted that the paper proposes an intuitive and promising approach to an interesting problem and provides a good balance between theoretical and empirical results. However, reviewers raised also concerns regarding the significance of technical contributions, limited analysis (e.g, performance on large-scale graphs, baselines, evaluation) and comparison to related work. After author response and discussion, reviewers did not come to a full agreement with two reviewers indicating weak acceptance and two reviewers indicating (weak) reject. Taking rebuttal and discussion into account, I agree with the viewpoint that the paper is not yet ready for acceptance at ICLR as it would require an additional revision to fully address the raised concerns. However, I encourage the authors to revise and resubmit their manuscript based on the feedback from this reviewing round.
Decision: Reject