# A Neural Framework for Learning Subgraph and Graph Similarity Measures

Rishabh Ranjan
IIT Delhi, India
<EMAIL_ADDRESS>&Siddharth Grover
IIT Delhi, India
<EMAIL_ADDRESS>&Sourav Medya
Northwestern University, USA
<EMAIL_ADDRESS>&Venkatesan Chakaravarthy
IBM Research, India
<EMAIL_ADDRESS>&Yogish Sabharwal
IBM Research, India
<EMAIL_ADDRESS>&Sayan Ranu
IIT Delhi, India
<EMAIL_ADDRESS>
###### 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 for
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 $\approx$ 3 orders of magnitude faster retrieval of graphs and
subgraphs.

##  1 Introduction and Related work

Graphs are used to model data in a wide variety of domains. Examples include
chemical compounds [44], protein-protein interaction networks (PPI) [1],
knowledge graphs [17], and social networks [26]. A distance function on any
dataset, including graphs, is a fundamental operator. Among several distance
measures on graphs, edit distance is one of the most powerful and popular
mechanisms [35, 54, 9, 14, 19, 42, 51, 22]. Edit distance can be posed in two
forms: graph edit distance (Ged) and subgraph edit distance (Sed). Given two
graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$,
$\textsc{Ged}(\mathcal{G}_{1},\mathcal{G}_{2})$ returns the minimum cost of
edits needed to convert $\mathcal{G}_{1}$ to $\mathcal{G}_{2}$. i.e., for
$\mathcal{G}_{1}$ to become isomorphic to $\mathcal{G}_{2}$. An edit can be
addition or deletion of edges and nodes, or replacement of edge or node
labels, with an associated cost. In
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})$, the goal is to identify the
minimum cost of edits so that $\mathcal{G}_{1}$ is subgraph isomorphic to
$\mathcal{G}_{2}$. For examples, see Fig. 1a. We define these notions more
formally in § 2.

Ged is typically restricted to graph databases containing small graphs to
facilitate distance computation with queries of similar sizes. As an example,
given a repository of molecules, and a query molecule, we may want to identify
the closest molecule in the repository that is similar to the query. Sed, on
the other hand, is useful when the database has large graphs and the query is
a comparatively smaller graph. As examples, subgraph queries are used on
knowledge graphs for analogy reasoning [17]. In PPI and chemical compounds,
Sed is of central importance to identify functional motifs and binding pockets
[44, 22, 16].

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 [51, 38, 22]. To mitigate this computational bottleneck, several
heuristics [9, 14, 19, 42, 38] and index structures [22, 51, 35, 54] have been
proposed. Recently, graph neural networks have been shown to be effective in
learning and predicting Ged [2, 47, 34, 3, 53, 48] and subgraph isomorphism
[37]. The basic goal in all these algorithms is to learn a neural model from a
training set of graph pairs and their distances, such that, at inference time,
given an unseen graph pair, we are able to predict its distance accurately.
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. A, we provide a detailed analysis of the
limitations of prior architectures in failing to model Sed.

  * •

Exponential Search Space:  Computing
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})$ conceptually requires us to
compare the query graph $\mathcal{G}_{1}$ with the exponentially many
subgraphs of the target graph $\mathcal{G}_{2}$. 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 [22, 51, 2, 47], 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 triangle
inequality, non-negativity, and subgraph-identity. Several higher-order tasks
such as clustering and indexing rely on such properties [21, 15, 24, 43, 46,
50, 52, 10, 12]. Existing neural approaches do not preserve these properties,
which limits their usability for these higher order tasks.

  * •

Pair-independent embedding: There is little scope for pre-computation in
existing approaches (either neural or non-neural), as the major computations
are pair-dependent, i.e., both $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ 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.

(a) Ged and Sed

(b) Graph Mapping

Figure 1: (a) A sample set of graphs and their corresponding Ged and Sed
matrices. (b) Example of a graph mapping. The dashed nodes and edges represent
dummy nodes and edges. The red arrows denote either insertion or change of
label.

We address these challenges by a novel architecture called NeuroSed. Our key
contributions are:

  * •

Novel formulation: 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.

  * •

Neural architecture: NeuroSed utilizes a siamese graph isomorphism network
[49] to embed graphs in a pair-independent fashion to an embedding space over
which a simple function can predict the Sed (or Ged). The same embedding model
is used for both $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, 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 generalisation
accuracy, preserves the key properties of Sed/Ged, which is a major
contribution of our work over existing neural approaches.

  * •

Indexable embeddings: The prediction function satisfies triangle inequality
over the embedding space for both Sed and Ged. This allows utilization of the
rich literature on index structures [18, 30, 13] for boosting querying
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 $3$
orders of magnitude faster in range and $k$-NN queries.

##  2 Preliminaries and Problem Formulation

We denote a labelled undirected graph as
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{L})$ where $\mathcal{V}$ is the
node set, $\mathcal{E}$ is the edge set and
$\mathcal{L}:\mathcal{V}\cup\mathcal{E}\rightarrow\Sigma$ is the labeling
function over nodes and edges. $\Sigma$ is the universe of all labels and
contains a special empty label $\epsilon$. $\mathcal{L}(v)$ and
$\mathcal{L}(e)$ denotes the labels of node $v$ and edge $e$ respectively.
$\mathcal{G}_{1}\subseteq\mathcal{G}_{2}$ denotes that $\mathcal{G}_{1}$ is a
subgraph of $\mathcal{G}_{2}$. For the definitions of subgraph and graph
isomorphism, refer to App. B in the supplementary. The computation of Ged
relies on a graph mapping.

######  Definition 1 (Graph Mapping)

Given two graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, let
$\tilde{\mathcal{G}_{1}}=(\tilde{\mathcal{V}_{1}},\tilde{\mathcal{E}_{1}},\tilde{\mathcal{L}_{1}})$
and
$\tilde{\mathcal{G}_{2}}=(\tilde{\mathcal{V}_{2}},\tilde{\mathcal{E}_{2}},\tilde{\mathcal{L}_{2}})$
be obtained by adding dummy nodes and edges (labeled with $\epsilon$) to
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ respectively, such that
$|\mathcal{V}_{1}|=|\mathcal{V}_{2}|$ and
$|\mathcal{E}_{1}|=|\mathcal{E}_{2}|$. A node mapping between
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ is a bijection
$\pi:\tilde{\mathcal{G}_{1}}\rightarrow\tilde{\mathcal{G}_{2}}$ where (i)
$\forall v\in\tilde{\mathcal{V}_{1}},\pi(v)\in\tilde{\mathcal{V}_{2}}$ and at
least one of $v$ and $\pi(v)$ is not a dummy; (ii) $\forall
e=(v_{1},v_{2})\in\tilde{\mathcal{E}_{1}},\pi(e)=(\pi(v_{1}),(\pi(v_{2})))\in\tilde{\mathcal{E}_{2}}$
and at least one of $e$ and $\pi(e)$ is not a dummy.

###### Example 1

Fig. 1b shows a graph mapping. Edge mappings can be trivially inferred, so are
omitted.

######  Definition 2 (Graph Edit Distance (Ged) under mapping $\pi$)

Ged between $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ under $\pi$ is

$\textsc{Ged}_{\pi}(\mathcal{G}_{1},\mathcal{G}_{2})=\sum_{v\in\tilde{V_{1}}}d(\mathcal{L}(v),\mathcal{L}(\pi(v)))+\sum_{e\in\tilde{E_{1}}}d(\mathcal{L}(e),\mathcal{L}(\pi(e)))$
(1)

where $d:\Sigma\times\Sigma\rightarrow\mathbb{R}^{+}_{0}$ is a distance
function over the label set.

$d(\ell_{1},\ell_{2})$ models an insertion if $\ell_{1}=\epsilon$, deletion if
$\ell_{2}=\epsilon$ and replacement if $\ell_{1}\neq\ell_{2}$ and neither
$\ell_{1}$ nor $\ell_{2}$ is a dummy. We assume $d$ to be a binary function,
where $d(\ell_{1},\ell_{2})=1$ if $\ell_{1}\neq\ell_{2}$, otherwise, $0$. Our
framework easily extends to more general distance functions (details in App.
D).

###### Example 2

Ged for the shown mapping in Fig. 1b is 3. The red mappings incur a cost of
$1$.

######  Definition 3 (Graph Edit Distance (Ged))

Ged is the minimum distance under all mappings.

$\textsc{Ged}(\mathcal{G}_{1},\mathcal{G}_{2})=\min_{\forall\pi\in\Phi(\mathcal{G}_{1},\mathcal{G}_{2})}\textsc{Ged}_{\pi}(\mathcal{G}_{1},\mathcal{G}_{2})$
(2)

where $\Phi(\mathcal{G}_{1},\mathcal{G}_{2})$ denotes the set of all possible
node maps from $\mathcal{G}_{1}$ to $\mathcal{G}_{2}$.

######  Definition 4 (Subgraph Edit Distance (Sed))

Sed is the minimum Ged over all subgraphs of $\mathcal{G}_{2}$.

$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})=\min_{\mathcal{S}\subseteq\mathcal{G}_{2}}\textsc{Ged}(\mathcal{G}_{1},\mathcal{S})$
(3)

###### Example 3

Revisiting Fig. 1b, $\textsc{Ged}(\mathcal{G}_{1},\mathcal{G}_{2})=3$. The
shown mapping incurs the minimum cost.
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})=1$. Refer to Fig. 1a for more
examples.

######  Problem 1 (Learning Sed)

Given a training set of tuples of the form
$\langle\mathcal{G}_{1},\mathcal{G}_{2},\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})\rangle$,
learn a neural model to predict
$\textsc{Sed}(\mathcal{Q}_{1},\mathcal{Q}_{2})$ on unseen graphs
$\mathcal{Q}_{1}$ and $\mathcal{Q}_{2}$.

######  Problem 2 (Learning Ged)

Given a training set of tuples of the form
$\langle\mathcal{G}_{1},\mathcal{G}_{2},\textsc{Ged}(\mathcal{G}_{1},\mathcal{G}_{2})\rangle$,
learn a neural model to predict
$\textsc{Ged}(\mathcal{Q}_{1},\mathcal{Q}_{2})$ on unseen graphs
$\mathcal{Q}_{1}$ and $\mathcal{Q}_{2}$.

###  2.1 Properties of Sed and Ged

###### Observation 1

(i) $\textsc{Ged}(\mathcal{G}_{1},\mathcal{G}_{2})\geq 0$, (ii)
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})\geq 0$.

###### Observation 2

(i) $\textsc{Ged}(\mathcal{G}_{1},\mathcal{G}_{2})=0$ iff $\mathcal{G}_{1}$ is
isomorphic to $\mathcal{G}_{2}$, (ii)
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})=0$ iff $\mathcal{G}_{1}$ is
subgraph isomorphic to $\mathcal{G}_{2}$.

###### Observation 3

Ged is a metric if the distance function $d$ over label set $\Sigma$ is metric
[22]. $d$ as defined in $\S$ 2 is metric [22]. Hence, Ged from $\S$ 2 is
metric.

We next prove that Sed satisfies triangle inequality in Theorem 1.

###### Theorem 1

$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{3})\leq\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})+\textsc{Sed}(\mathcal{G}_{2},\mathcal{G}_{3})$.

Proof Sketch: Lemma 3 (App. D.1) shows that Sed can be viewed as Ged under a
modified cost function. Specifically, the Sed is equivalent to Ged with a
label set distance function where we ignore insertion costs. Furthermore, this
modified distance function satisfies triangle inequality, which leads to
triangle inequality for Sed (similar to Observation 3). See App. D.1 for
details.$\hfill\square$

##  3 NeuroSed

Fig. 2 presents the architecture of NeuroSed. The input to our learning
framework is a pair of graphs $\mathcal{G}_{\mathcal{Q}}$ (query),
$\mathcal{G}_{\mathcal{T}}$ (target) along with the supervision data
$\textsc{Sed}(\mathcal{G}_{Q},\mathcal{G}_{T})$. Our objective is to train a
model that can predict Sed on unseen query and target graphs. The design of
our model must be cognizant of the fact that computing Sed is NP-hard and high
quality training data is scarce. Thus, we use a 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: Siamese networks [11] are neural network models that were
originally proposed for visual similarity learning, for which they have
achieved significant success [29, 4]. In these models, there are two networks
with shared parameters applied to two inputs independently to compute
representations. These representations are then passed through another module
to compute a similarity score.

###  3.1 Siamese Graph Neural Network

As depicted in Fig. 2a, we use a siamese graph neural network (Gnn) with
shared parameters to embed both $\mathcal{G}_{\mathcal{Q}}$ and
$\mathcal{G}_{\mathcal{T}}$. Fig. 2b focuses on the Gnn component of NeuroSed.
We next discuss each of its individual components.

Pre-Mlp: The primary task of the Pre-Mlp is to learn representations for the
node labels (or features). Towards that end, let $\mathbf{x}_{v}$ denote the
initial feature set of node $v$. The Mlp learns a hidden representation
$\boldsymbol{\mu}^{\mathcal{G}}_{v}=\textsc{Mlp}\left(\mathbf{x}_{v}\right)$.
In our implementation, $\mathbf{x}_{v}$ is a one-hot encoding of the
categorical node labels. We do not explicitly model edge labels in our
experiments. NeuroSed can easily be extended to edge labels, such as using
Gine [25] layers instead of Gin layers (see App. C).

Graph Isomorphism Network (Gin): Gin [49] consumes the information from the
Pre-Mlp to learn hidden representations that encode both the graph structure
as well as the node feature information. Gin is as powerful as the Weisfeiler-
Lehman (WL) graph isomorphism test [31] in distinguishing graph structures.
Since our goal is to accurately characterize graph topology and learn
similarity, Gin emerges as the natural choice. Gin develops its expressive
power by using an injective aggregation function. Specifically, in the initial
layer, each node $v$ in graph $\mathcal{G}$ is characterized by the
representation learned by the Mlp, i.e.,
$\mathbf{h}^{\mathcal{G}}_{v,0}=\boldsymbol{\mu}_{v}^{\mathcal{G}}$.
Subsequently, in each hidden layer $i$, we learn an embedding through the
following transformation.

$\mathbf{h}^{\mathcal{G}}_{v,i}=\textsc{Mlp}\left((1+\epsilon^{i})\cdot\mathbf{h}^{\mathcal{G}}_{v,i-1}+\sum_{u\in\mathcal{N}_{\mathcal{G}}(v)}\mathbf{h}^{\mathcal{G}}_{u,i-1}\right)$
(4)

Here, $\epsilon^{i}$ is a layer-specific learnable parameter,
$\mathcal{N}_{\mathcal{G}}(v)$ is one-hop neighbourhood of the node $v$, and
$\mathbf{h}^{\mathcal{G}}_{v,0}=\boldsymbol{\mu}^{\mathcal{G}}_{v}$. The
$k$-th layer embedding is $\mathbf{h}^{\mathcal{G}}_{v,k}$, where $k$ is final
hidden layer.

(a) Siamese architecture

(b) Gnn component

Figure 2: The architecture of NeuroSed.

Concatenation, Pool and Post-Mlp: Intuitively,
$\mathbf{h}^{\mathcal{G}}_{v,i}$ captures a feature-space representation of
the $i$-hop neighborhood of $v$. Typically, Gnns operate on node or edge level
predictive tasks, such as node classification or link prediction, and hence,
the node representations are passed through an Mlp for the final prediction
task. In our problem, we need to capture a 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 a node across all hidden layers, i.e., the final node
embedding is
$\mathbf{z}_{v}^{\mathcal{G}}=\textsc{Concat}\left(\mathbf{h}^{\mathcal{G}}_{v,i},\forall
i\in\\{1,2,\cdots,k\\}\right)$. This allows us to capture a multi-granular
view of the subgraphs centered on $v$ at different radii in the range $[1,k]$.
Next, to construct the graph-level representation, we perform a sum-pool,
which adds the node representations to give a single vector. This information
is then fed to the Post-Mlp to enable post-processing. Mathematically:

$\mathbf{Z}_{\mathcal{G}}=\textsc{Mlp}(\mathbf{z}^{\mathcal{G}})=\textsc{Mlp}\left(\sum_{v\in\mathcal{V}}\mathbf{z}_{v}^{\mathcal{G}}\right)$
(5)

Sed Prediction: The final task is to predict the Sed as a function of query
graph embedding $\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}$ and target graph
embedding $\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}$. The natural choice would
be to feed these embeddings into another Mlp to learn
$\textsc{Sed}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})$.
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
$\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})$
to predict the Sed. By training the model to produce embeddings
$\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}$ and
$\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}$ such that
$\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})\approx\textsc{Sed}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})$,
we enforce a rich structure on the embedding space. We show that these
embeddings satisfy many key properties of the Sed (and Ged) function that
existing neural algorithms fail to do [2, 47, 3, 53]. $F$ is defined as
follows:

$\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})=\lVert
ReLU(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}-\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})\rVert_{2}=\left\lVert\max\left\\{0,\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}-\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}\right\\}\right\rVert_{2}$
(6)

Intuitively, for those co-ordinates where the value of
$\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}$ is greater than
$\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}$; a distance penalty is accounted by
$\mathcal{F}$ in terms of how much those values differ, otherwise
$\mathcal{F}$ considers $0$. This follows the intuition that the Sed accounts
for those features of $\mathcal{G}_{\mathcal{Q}}$ that are not in
$\mathcal{G}_{\mathcal{T}}$. Moreover, consistent with Sed, the additional
features in $\mathcal{G}_{\mathcal{T}}$ that are not in
$\mathcal{G}_{\mathcal{Q}}$, do not incur any cost. Finally, the parameters of
the entire model are learned by minimizing the mean squared error111Since Sed
computation is NP-hard, in App. F, we discuss a loss function based on Sed
lower and upper bounds, which are faster to compute. (here $\mathbb{T}$ is the
training set).

$\mathscr{L}=\frac{1}{\lvert\mathbb{T}\rvert}\sum_{\forall\langle\mathcal{G}_{\mathcal{Q}},\mathcal{G}_{\mathcal{T}}\rangle\in\mathbb{T}}\big{(}\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})-\textsc{Sed}(\mathcal{G}_{\mathcal{Q}},\mathcal{G}_{\mathcal{T}})\big{)}^{2}$
(7)

Adaptation for Ged ($\textsc{NeuroSed}_{\mathcal{G}}$): The architecture
naturally extends to Ged (denoted by $\textsc{NeuroSed}_{\mathcal{G}}$) with a
modification of the prediction function. Specifically, instead of Eq. 6, we
use:

$\mathcal{F}_{g}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})=\left\lVert\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}-\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}\right\rVert_{2}$
(8)

###  3.2 Theoretical Characterization

###### Lemma 1

The following properties hold on predicted Sed
$\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})$:

  1. 1.

$\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})\geq
0$

  2. 2.

$\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})=0\iff\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}\leq\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}$

  3. 3.

$\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})\leq\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}^{\prime}}})+\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{T}^{\prime}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})$

Proof. Properties (1) and (2) follow from the definition of $F$ itself.
Property (3) follows from the fact that we take the $L_{2}$ norm (holds for
any monotonic norm, details are available in App. D).$\hfill\square$

We see that $\mathcal{F}$ satisfies the analogue of properties of Sed (§ 2.1).
Conditions 1, 2, and 3 captures non-negativity, the subgraph relation [37],
and triangle inequality respectively.

###### Lemma 2

The predicted Ged, i.e., $\mathcal{F}_{g}$ is metric. (i) Non-negativity:
$F_{g}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})\geq
0$, (ii) Identity:
$F_{g}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})=0\iff\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}=\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}$,
(iii) Symmetry:
$F_{g}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})=F_{g}(\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}})$,
(iv) Triangle Inequality:
$F_{g}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})\leq\mathcal{F}_{g}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{T}^{\prime}})+\mathcal{F}_{g}(\mathbf{Z}_{\mathcal{T}^{\prime}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})$.

Proof. Follows trivially from the fact that $\mathcal{F}_{g}$ forms a
Euclidean space. $\hfill\square$

###### Theorem 2

The properties of Sed (and Ged) in $\S$ 2.1 are satisfied by the prediction
functions $\textsc{NeuroSed}(\mathcal{G}_{1},\mathcal{G}_{2})$ (and the Ged
version $\textsc{NeuroSed}_{\mathcal{G}}(\mathcal{G}_{1},\mathcal{G}_{2})$).

Proof Sketch. (For Sed) Let $\mathcal{E}$ be the embedding function learned by
NeuroSed’s GNN. Then
$\textsc{NeuroSed}(\mathcal{G}_{1},\mathcal{G}_{2})=\mathcal{F}(\mathcal{E}(\mathcal{G}_{1}),\mathcal{E}(\mathcal{G}_{2}))$.
Now, the relevant properties follow from Lemma 1. $\hfill\square$

We note here that if different embedding models were used for
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, or if the embeddings were pair-
dependent [34], then Theorem 2 would not hold.

Complexity analysis: Inference is linear in query and target sizes (see App. E
for details).

##  4 Empirical Evaluation

In this section, we establish the following222Code, data and experiments are
available at https://github.com/idea-iitd/NeuroSED.:

  * •

Subgraph Search: NeuroSed outperforms the state of the art approaches for Sed
prediction.

  * •

Graph Search: $\textsc{NeuroSed}_{\mathcal{G}}$, the variant to predict Ged,
outperforms the state of the art approaches for Ged prediction.

  * •

Scalability: NeuroSed and $\textsc{NeuroSed}_{\mathcal{G}}$ are orders of
magnitude faster than existing approaches and scale well to graphs with
millions of nodes.

###  4.1 Experimental Setup

Details on the hardware and software platform are provided in App. H.

Datasets: Table 4.1 lists the datasets used for benchmarking. Further details
on the dataset semantics are provided in the App. G. We include a mixture of
both graph databases (#graphs >1), as well as single large graphs (#graphs =
1). Linux and IMDB contain unlabeled graphs.

Name | $Avg.|\mathcal{V}|$ | $Avg.|\mathcal{E}|$ | $|\Sigma|$ | #Graphs | $|\mathcal{V}_{\mathcal{Q}}|$ | $|\mathcal{E}_{\mathcal{Q}}|$
---|---|---|---|---|---|---
Dblp | $1.66M$ | $7.2M$ | $8$ | $1$ | $284$ | $1692$
Amazon | $334k$ | $925k$ | $1$ | $1$ | $43$ | $194$
PubMed | $19.7k$ | $44.3k$ | $3$ | $1$ | $12$ | $11$
CiteSeer | $4.2k$ | $5.3k$ | $6$ | $1$ | $12$ | $12$
Cora_ML | $3k$ | $8.2k$ | $7$ | $1$ | $11$ | $11$
Protein | $38$ | $70$ | $3$ | $1,071$ | $9$ | $11$
AIDS | $14$ | $15$ | $38$ | $1,811$ | $7$ | $7$
AIDS’ | $9$ | $9$ | $29$ | $700$ | $9$ | $9$
Linux | $8$ | $7$ | $1$ | $1,000$ | $8$ | $7$
IMDB | $13$ | $65$ | $1$ | $1,500$ | $13$ | $65$

tableDatasets used for benchmarking.

figureHeat Map of Sed error against query size in Dblp. Darker means higher
error.

Training (and Test) Data Generation:  For Ged, we use $\langle
query,target\rangle$ graph pairs from IMDB, AIDS’, and Linux. Our setup is
identical to SimGnn [2] and H2MN-rw [53]. For Sed, the procedure is more
intricate. The details of datasets can be found in App. G.

  * •

Targets: For single large graphs, we generate target graphs from
neighbourhoods (up to $5$-hop) from every node in the graph. The average
number of (nodes, edges) in target graphs from PubMed, CiteSeer, Cora_ML,
Amazon and Dblp are $(60,129)$, $(73,192)$, $(98,179)$, $(43,97)$ and
$(240,238)$ respectively. Theorem 3 in App. F justifies this neighborhood
decomposition for subgraph search. For graph databases (Protein, AIDS’, Linux
and IMDB), each graph is a target.

  * •

Queries: In single large graphs, queries are sampled by performing a random
BFS traversal (depth upto 5) on a randomly chosen target graph. In addition,
for AIDS, we use known functional groups from Table 1 in [41]) as test
queries. This allows us to benchmark NeuroSed on both natural as well
synthetic queries. The average query sizes ($|\mathcal{V}_{\mathcal{Q}}|$,
$|\mathcal{E}_{\mathcal{Q}}|$) are listed in Table 4.1.

  * •

Ground-truth: We use mixed integer programming method F2 [32] implemented in
Gedlib [7] with a large time limit to generate ground-truth data.

Train-Validation-Test Split: We use $100K$ query-target pairs for training and
$10K$ pairs each for validation and test. We also use data for $10-50$ queries
on all targets for ranking and range tests.

Baselines: To evaluate performance in Ged, we compare with SimGnn 333We use
the PyTorch implementation of SimGnn given on paperswithcode. The code of all
other neural algorithms have been obtained from the respective authors. [2],
Genn-A∗ [47] and H2MN[53]. H2MN has two versions based on random walks (H2MN-
rw) and $k$-hop neighborhood (H2MN-ne). We include both.

For Sed, no neural approaches exist. However, H2MN and SimGnn can be trained
by replacing Ged with Sed along with minor modifications in training. While
NeuroMatch [37] cannot predict Sed, it generates a 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$-NearestNeighbour) queries. Thus, NeuroMatch comparisons are
limited to $k$-NN queries on Sed. The changes required to adapt to Sed are in
App. H.

GMN [34] and GraphSim [3] are not included since they cannot be easily adapted
for Sed (See App. A for details). Furthermore, H2MN and Genn-A∗ are more
recent, have better reported results, and therefore considered the state of
the art. Genn-A∗ is not included for Sed since it is exorbitantly slow and
does not scale on graphs beyond $10$ nodes (See Sec. 4.3).

In the non-neural category, we use mixed integer programming based method
Mip-F2 [32] 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 [5], which achieves an excellent trade-off between
accuracy and runtime [6]. Branch uses linear sum assignment problem with
error-correction (Lsape) to process the search space. We use Gedlib [7] for
these methods.

Methods | Dblp | Amazon | PubMed | CiteSeer | Cora_ML | Protein | AIDS
---|---|---|---|---|---|---|---
NeuroSed | 0.964 | 0.495 | 0.728 | 0.519 | 0.635 | 0.524 | 0.512
H2MN-rw | 1.470 | 1.294 | 1.213 | 1.502 | 1.446 | 0.941 | 0.749
H2MN-ne | 1.552 | 0.971 | 1.326 | 1.827 | 1.229 | 0.755 | 0.657
SimGnn | 1.482 | 2.810 | 1.322 | 1.781 | 1.289 | 1.223 | 0.696
Branch | 2.917 | 4.513 | 2.613 | 3.161 | 3.102 | 2.391 | 1.379
MIP-F2 | 3.427 | 5.595 | 3.399 | 4.474 | 3.871 | 2.249 | 1.537

(a) Prediction of Sed.

Methods | AIDS’ | Linux | IMDB
---|---|---|---
$\textsc{NeuroSed}_{\mathcal{G}}$ | 0.796 | 0.415 | 6.734
H2MN-rw | 0.994 | 0.734 | 86.077
H2MN-ne | 1.000 | 0.319 | 87.594
Genn-A∗ | 0.907 | 0.267 | NA
SimGnn | 1.037 | 0.666 | 66.250
Branch | 3.322 | 2.474 | 6.875
MIP-F2 | 2.929 | 1.245 | 82.124

(b) Prediction of Ged

table 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.

###  4.2 Prediction Accuracy of Sed and Ged

Tables 1a and 1b present the accuracy of all techniques on Sed and Ged in
terms of Root Mean Square Error (RMSE). In App. I, we evaluate the same
performance using several other metrics such as $R^{2}$ and Mean Absolute
Error (MAE). NeuroSed outperforms all other techniques in 9 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 AIDS’ or
Linux. Thus, computing the optimal Ged is harder. While all techniques have
higher errors in IMDB, the deterioration is more severe in the baselines
indicating that NeuroSed scales better with graph sizes.

To gain insight on whether the same patterns also hold in Sed, in Fig. 4.1, we
plot the heat map of RMSE against query graph size in Dblp. Specifically in
this plot, each dot corresponds to a query graph $\mathcal{G}_{\mathcal{Q}}$.
The co-ordinate of a query is
$(\textsc{Sed}(\mathcal{G}_{\mathcal{Q}},\mathcal{G}_{\mathcal{T}}),|\mathcal{V}_{\mathcal{Q}}|)$.
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 H2MN-
rw, we observe that H2MN-rw 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 for all datasets are provided in App. K.

Range and $\mathbf{k}$-NN queries: 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. In a range query, given a distance threshold
$\theta$, the goal is to retrieve all database graphs that are within $\theta$
distance from the query graph. In a $k$-NN query, given the query graph, we
identify the $k$ nearest neighbors from the search space in distance-ascending
order. For Sed, the search space includes all target graphs of the database
graphs, whereas for Ged, the search space constitutes of the database graphs.
The performance measures are:

  * •

F1-score (Range query): The accuracy is quantified using F1-score by comparing
with the ground truth answer set.

  * •

Kendalls’s tau ($k$-NN) [27]: $\kappa$ measures how well the ranking is
preserved between two ranked lists. In this case, we compare the ground truth
rank order with the predicted.

As visible in Figs. 6a-6h, NeuroSed consistently outperforms all baselines in
F1-score. Similar trend is also visible in $k$-NN queries. Specifically, in
Kendall’s tau (Tables 1c and 1d), 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. I.2, we also report $k$-NN
performance based on Precision$@k$. In this analysis, we do not include
Genn-A∗ since it is orders of magnitude slower than all neural-baselines and
provides a comparable distance accuracy to H2MN. Next, we discuss efficiency
in detail.

Methods | PubMed | CiteSeer | Cora_ML | Protein | AIDS
---|---|---|---|---|---
NeuroSed | 0.90 | 0.90 | 0.91 | 0.75 | 0.80
H2MN-rw | 0.87 | 0.88 | 0.88 | 0.70 | 0.72
H2MN-ne | 0.87 | 0.87 | 0.87 | 0.72 | 0.73
SimGnn | 0.85 | 0.87 | 0.86 | 0.63 | 0.73
NeuroMatch | 0.70 | 0.75 | 0.73 | 0.57 | 0.59

(c) Ranking in Sed.

Methods | AIDS’ | Linux | IMDB
---|---|---|---
$\textsc{NeuroSed}_{\mathcal{G}}$ | 0.78 | 0.90 | 0.87
H2MN-rw | 0.72 | 0.89 | 0.80
H2MN-ne | 0.73 | 0.93 | 0.82
SimGnn | 0.70 | 0.84 | 0.70

(d) Ranking in Ged

tableKendall’s tau scores (higher is better).

Methods | Dblp | Amazon | PubMed | CiteSeer | Cora_ML | Protein | AIDS
---|---|---|---|---|---|---|---
NeuroSed | 6.84 | 1.46 | 1.30 | 1.28 | 1.25 | 0.86 | 0.84
H2MN-rw | 44.68 | 23.2 | 25.79 | 27.54 | 29.04 | 19.33 | 9.63
H2MN-ne | 56.82 | 40.34 | 50.64 | 54.46 | 70.59 | 28.99 | 15.76
SimGnn | 109.56 | 47.68 | 39.80 | 39.40 | 40.73 | 39.02 | 43.83
Branch | 626.489 | 79.25 | 99.11 | 155.09 | 132.98 | 52.26 | 12.93
Mip-F2 | 1979.185 | 861.95 | 606.01 | 827.65 | 790.01 | 881.77 | 360.12

(e) Sed.

Methods | AIDS’ | Linux | IMDB
---|---|---|---
$\textsc{NeuroSed}_{\mathcal{G}}$ | 0.49 | 0.70 | 0.63
H2MN-rw | 9.50 | 8.74 | 8.83
H2MN-ne | 10.38 | 9.80 | 10.69
Genn-A∗ | 12190 | 1340 | NA
SimGnn | 39.21 | 38.62 | 38.98
Branch | 10.70 | 8.24 | 127.90
Mip-F2 | 593.34 | 191.88 | 1173.548

(f) Ged

tableRunning times of all methods in seconds per 10k pair (lower is better).

Datasets | Range ($\theta=2$) |  $10$-NN
---|---|---
| CPU | GPU | CPU | GPU
| L-Scan | M-Tree | L-Scan | H2MN-rw | H2MN-ne | L-Scan | M-Tree | L-Scan | H2MN-rw | H2MN-ne
Dblp | 48 | 20.9 | 0.070 | 696 | 8910 | 50.4 | 18.6 | 0.126 | 698 | 9790
Amazon | 9.09 | 5.07 | 0.025 | 371 | 8550 | 11.3 | 4.75 | 0.027 | 372 | 8760
PubMed | 0.693 | 0.56 | 0.004 | 26.6 | 35.2 | 1.01 | 0.49 | 0.004 | 27.5 | 35.5

tableQuerying 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.

###  4.3 Efficiency

Table 1f 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 Genn-A∗ is exorbitantly slow (Table 1f). 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. I.4, we discuss this issue in
detail.

Scalability:  Here, we showcase how pair-independent embeddings, and ensuring
triangle inequality leads to further boost in scalability. For this
experiment, we use the three largest datasets of PubMed, Amazon and Dblp. 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 [46] index structure adapted to
asymmetric distance functions (see App. J). Consequently, for NeuroSed, we
only need to embed the query graph and evaluate $\mathcal{F}$ to make
predictions at query time. Table 4.2 presents the results on range and $10$-NN
queries. When computations are done on a GPU, NeuroSed is more than $1000$
times faster than both H2MN-rw and H2MN-ne. In the absence of a GPU, H2MN is
practically infeasible since expensive pair-dependent computations are done at
query time. In contrast, even on a CPU, with tree indexing, NeuroSed is
$\approx 50$ times faster than GPU-based H2MN. Note that indexing enables up
to $3$-times speed-up on NeuroSed over linear scan, which demonstrates the
gain from ensuring triangle inequality. Overall, these results show the
benefits of using an easily computable and parallelisable prediction function
$\mathcal{F}$ with theoretical guarantees.

(a) PubMed

(b) CiteSeer

(c) Cora_ML

(d) Protein

(e) AIDS

(f) AIDS’

(g) Linux

(h) IMDB

Figure 3: F1-score in range queries on Sed (a-e) and Ged (f-h). The range
threshold is set as a percentage of the max distance observed in the test set.

(a) Dblp

(b) PubMed

(c) PubMed

Figure 4: Ablation study to analyze the impact of siamese architecture and
function $\mathcal{F}$.

###  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-Dual trains
the two parallel Gnn models separately without weight-sharing, and (2)
NeuroSed-NN uses an MLP instead of $\mathcal{F}$. Both have strictly higher
representational capacity than NeuroSed. Figs. 4a-4c present the results. The
RMSE of NeuroSed is 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 $\mathcal{F}$. Overall, these trends
indicate that $\mathcal{F}$ enables better generalization and scalability with
respect to accuracy. Furthermore, given that its performance is close to an
MLP, and it enables indexing, the benefits outweigh the marginal reduction in
accuracy. More ablations studies are provided in App. I.3.

###  4.5 Visualization and Application of Sed

Searching for molecular fragment containment is a routine task in drug
discovery [40]. Motivated by this, we show the top-$5$ matches to an Sed query
on the AIDS dataset produced by NeuroSed in Fig. 5. The query is a functional
group (Hydrogen atoms are not represented). NeuroSed is able to extract
chemical compounds that contain this molecular fragment (except for ranks $3$
and $5$, which contain this group with $1$ edit) from around $2000$ chemical
compounds with varying sizes and structures. This validates the efficacy of
NeuroSed at a semantic level.

(a) Query (b) Rank 1 (c) Rank 2 (d) Rank 3 (e) Rank 4 (f) Rank 5

Figure 5: 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$.

##  5 Conclusions

Subgraph similarity search is a fundamental operator for graph analytics.
Subgraph edit distance is one of the most popular similarity measures defined
for subgraphs. The applicability of Sed, however, is constrained by its
exponential computation complexity. Our work is motivated by the following
question: Is it possible to design a neural framework that generalizes to 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: a siamese
architecture to reduce dependence on high-volume training data, a carefully
designed function to introduce an inductive bias and mimic important
properties of the original space, and pair-independent embeddings to enable
massive scalability.

## References

  * [1] 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), pages 241–249, 2008.
  * [2] 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, page 384–392, 2019.
  * [3] 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 Conference on Artificial Intelligence, 34(04):3219–3226, Apr. 2020.
  * [4] Luca Bertinetto, Jack Valmadre, Joao F Henriques, Andrea Vedaldi, and Philip HS Torr.  Fully-convolutional siamese networks for object tracking.  In European conference on computer vision, pages 850–865. Springer, 2016.
  * [5] David B Blumenthal.  New techniques for graph edit distance computation.  arXiv preprint arXiv:1908.00265, 2019.
  * [6] 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.
  * [7] 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 Representations in Pattern Recognition, pages 14–24. Springer, 2019.
  * [8] Aleksandar Bojchevski and Stephan Günnemann.  Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking.  arXiv preprint arXiv:1707.03815, 2017.
  * [9] Sébastien Bougleux, Luc Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Gaüzère, and Mario Vento.  Graph edit distance as a quadratic assignment problem.  Pattern Recognition Letters, 87:38–46, 2017.  Advances in Graph-based Pattern Recognition.
  * [10] Sergey Brin.  Near neighbor search in large metric spaces.  In Proceedings of the 21th International Conference on Very Large Data Bases, VLDB ’95, page 574–584, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.
  * [11] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah.  Signature verification using a" siamese" time delay neural network.  Advances in neural information processing systems, 6:737–744, 1993\.
  * [12] Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates, and Jose Marroquin.  Searching in metric spaces.  ACM Comput. Surv., 33:273–321, 09 2001.
  * [13] Paolo Ciaccia, Marco Patella, and Pavel Zezula.  M-tree: An efficient access method for similarity search in metric spaces.  In VLDB, 1997.
  * [14] Évariste Daller, Sébastien Bougleux, Benoit Gaüzère, and Luc Brun.  Approximate Graph Edit Distance by Several Local Searches in Parallel.  In 7th International Conference on Pattern Recognition Applications and Methods, 2018.
  * [15] Vlastislav Dohnal, Claudio Gennaro, Pasquale Savino, and Pavel Zezula.  D-index: Distance searching index for metric data sets.  Multim. Tools Appl., 21(1):9–33, 2003.
  * [16] Chi Thang Duong, Trung Dung Hoang, Hongzhi Yin, Matthias Weidlich, Quoc Viet Hung Nguyen, and Karl Aberer.  Efficient streaming subgraph isomorphism with graph neural networks.  Proc. VLDB Endow., 14(5):730–742, January 2021.
  * [17] Christopher L. Ebsch, Joseph A. Cottam, Natalie C. Heller, Rahul D. Deshmukh, and George Chin.  Using graph edit distance for noisy subgraph matching of semantic property graphs.  In 2020 IEEE International Conference on Big Data (Big Data), pages 2520–2525, 2020.
  * [18] Charles Elkan.  Using the triangle inequality to accelerate k-means.  In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML’03, page 147–153, 2003.
  * [19] Stefan Fankhauser, Kaspar Riesen, and Horst Bunke.  Speeding up graph edit distance computation through fast bipartite matching.  In Proceedings of the 8th International Conference on Graph-Based Representations in Pattern Recognition, page 102–111, 2011.
  * [20] Matthias Fey and Jan Eric Lenssen.  Fast graph representation learning with pytorch geometric.  arXiv preprint arXiv:1903.02428, 2019.
  * [21] Ali S. Hadi.  Finding groups in data: An introduction to chster analysis.  Technometrics, 34:111–112, 1991.
  * [22] Huahai He and Ambuj K Singh.  Closure-tree: An index structure for graph queries.  In 22nd International Conference on Data Engineering (ICDE), pages 38–38. IEEE, 2006.
  * [23] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [24] 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.
  * [25] 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:1905.12265, 2019.
  * [26] David Kempe, Jon Kleinberg, and Éva Tardos.  Maximizing the spread of influence through a social network.  In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 137–146, 2003.
  * [27] M. G. Kendall.  A new measure of rank correlation.  Biometrika, 30(1/2):81–93, 1938.
  * [28] Thomas Kluyver, Benjamin Ragan-Kelley, Fernando Pérez, Brian E Granger, Matthias Bussonnier, Jonathan Frederic, Kyle Kelley, Jessica B Hamrick, Jason Grout, Sylvain Corlay, et al.  Jupyter notebooks-a publishing format for reproducible computational workflows.  In International Conference on Electronic Publishing, 2016.
  * [29] Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov.  Siamese neural networks for one-shot image recognition.  In ICML deep learning workshop, volume 2. Lille, 2015.
  * [30] Wojciech Kwedlo and Pawel J. Czochanski.  A hybrid mpi/openmp parallelization of $k$ -means algorithms accelerated using the triangle inequality.  IEEE Access, 7:42280–42297, 2019.
  * [31] AA Leman and B Weisfeiler.  A reduction of a graph to a canonical form and an algebra arising during this reduction.  Nauchno-Technicheskaya Informatsiya, 2(9):12–16, 1968.
  * [32] 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.
  * [33] Jure Leskovec and Rok Sosič.  Snap: A general-purpose network analysis and graph-mining library.  ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1, 2016.
  * [34] 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, pages 3835–3845, 2019.
  * [35] 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), pages 783–794, 2017.
  * [36] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  arXiv preprint arXiv:1711.05101, 2017.
  * [37] Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al.  Neural subgraph matching.  arXiv preprint arXiv:2007.03092, 2020.
  * [38] Michel Neuhaus, Kaspar Riesen, and Horst Bunke.  Fast suboptimal algorithms for the computation of graph edit distance.  In Dit-Yan Yeung, James T. Kwok, Ana Fred, Fabio Roli, and Dick de Ridder, editors, Structural, Syntactic, and Statistical Pattern Recognition, pages 163–172, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [39] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  Advances in neural information processing systems, 32:8026–8037, 2019.
  * [40] Sayan Ranu, Bradley T Calhoun, Ambuj K Singh, and S Joshua Swamidass.  Probabilistic substructure mining from small-molecule screens.  Molecular Informatics, 30(9):809–815, 2011.
  * [41] Sayan Ranu and Ambuj K Singh.  Mining statistically significant molecular substructures for efficient molecular classification.  Journal of chemical information and modeling, 49(11):2537–2550, 2009.
  * [42] Kaspar Riesen and Horst Bunke.  Approximate graph edit distance computation by means of bipartite graph matching.  Image Vision Comput., 27(7):950–959, June 2009.
  * [43] 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.
  * [44] Aravind Sankar, Sayan Ranu, and Karthik Raman.  Predicting novel metabolic pathways through subgraph mining.  Bioinformatics, 33(24):3955–3963, 2017.
  * [45] Leslie N Smith.  Cyclical learning rates for training neural networks.  In 2017 IEEE winter conference on applications of computer vision (WACV), pages 464–472. IEEE, 2017.
  * [46] Jeffrey K. Uhlmann.  Satisfying general proximity/similarity queries with metric trees.  Inf. Process. Lett., 40:175–179, 1991.
  * [47] Runzhong Wang, Tianqi Zhang, Tianshu Yu, Junchi Yan, and Xiaokang Yang.  Combinatorial learning of graph edit distance via dynamic embedding.  In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pages 5241–5250, 2021.
  * [48] Haibo Xiu, Xiao Yan, Xiaoqiang Wang, James Cheng, and Lei Cao.  Hierarchical graph matching network for graph similarity computation, 2020\.
  * [49] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  arXiv preprint arXiv:1810.00826, 2018.
  * [50] Peter N. Yianilos.  Data structures and algorithms for nearest neighbor search in general metric spaces.  In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’93, page 311–321, USA, 1993. Society for Industrial and Applied Mathematics.
  * [51] 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.
  * [52] Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, and Michal Batko.  Similarity Search: The Metric Space Approach, volume 32 of Advances in Database Systems.  Springer, 2006.
  * [53] Zhen Zhang, Jiajun Bu, Martin Ester, Zhao Li, Chengwei Yao, Zhi Yu, and Can Wang.  H2mn: Graph similarity learning with hierarchical hypergraph matching networks.  In KDD, page 2274–2284, 2021.
  * [54] 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.

## Appendix

###  A Inability of existing neural approaches Ged in 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.

  * •

GMN [34]: The loss function of GMN computes the euclidean distance between the
embeddings and then this signal is used to learn the weight parameters (See
Eq. 12 in [34]). 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 a
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 $i$ and $j$ in Eqns. (4-8) in [34]).

  * •

GraphSim [3]: GraphSim computes a square similarity matrix across node pairs
of two graphs $\mathcal{G}_{1}=(\mathcal{V}_{1},\mathcal{E}_{1})$,
$\mathcal{G}_{2}=(\mathcal{V}_{2},\mathcal{E}_{2})$ on which CNNs are applied
to predict the similarity. Since $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ may
be of different sizes, the smaller graph is padded with
$||\mathcal{V}_{1}|-|\mathcal{V}_{2}||$ 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 a padding of $||\mathcal{V}_{1}|-|\mathcal{V}_{2}||$ zeros
instead of a 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 a 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 vs. hundreds), Sed can be 0. Thus, the above
mentioned design of relying on node-to-node square similarity matrix is not
well suited.

  * •

SimGNN [2]: SimGnn relies on a 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.

###  B Definitions

######  Definition 5 (Graph Isomorphism)

Graph $\mathcal{G}_{1}=(\mathcal{V}_{1},\mathcal{E}_{1},\mathcal{L}_{1})$ is
isomorphic to
$\mathcal{G}_{2}=(\mathcal{V}_{2},\mathcal{E}_{2},\mathcal{L}_{2})$ if there
exists a bijection $\pi:\mathcal{V}_{1}\rightarrow\mathcal{V}_{2}$ such that
(i) $\forall v\in\mathcal{V}_{1}:\mathcal{L}(v)=\mathcal{L}(\pi(v))$, (ii)
$\forall
e=(v_{1},v_{2})\in\mathcal{E}_{1}:\pi(e)=(\pi(v_{1}),\pi(v_{2}))\in\mathcal{E}_{2}$,
and (iii) $\forall e\in\mathcal{E}_{1}:\mathcal{L}(e)=\mathcal{L}(\pi(e))$.

Subgraph isomorphism is defined analogously by using an injection instead of a
bijection.

######  Definition 6 (Closest Subgraph)

$\mathcal{S}$ is a closest subgraph to $\mathcal{G}_{1}$ in $\mathcal{G}_{2}$
if
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})=\textsc{Ged}(\mathcal{G}_{1},\mathcal{S})$.

###  C Handling Edge Labels

A straight-forward extension of NeuroSed to handle edge labels is to use Gine
[25] layers instead of Gin layers. Equation 4 can be modified as follows:

$\mathbf{h}^{\mathcal{G}}_{v,i}=\textsc{Mlp}\left((1+\epsilon^{i})\cdot\mathbf{h}^{\mathcal{G}}_{v,i-1}+\sum_{u\in\mathcal{N}_{\mathcal{G}}(v)}\text{ReLU}(\mathbf{h}^{\mathcal{G}}_{u,i-1}+\mathbf{e}^{\mathcal{G}}_{v,u})\right)$
(9)

where $\mathbf{e}^{\mathcal{G}}_{v,u}$ denotes the vector representation of
the edge label for edge $(v,u)$.

It is also possible to represent edge labels in the current architecture by
constructing a new graph $\mathcal{G}^{\prime}$ with a vertex $w_{v,u}$ for
every edge $(v,u)$ and edges from $v$ to $w_{v,u}$ and from $w_{v,u}$ to $u$.
The node representation for $w_{v,u}$ is a 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 $1$ if the node is $w_{v,u}$ for some
$(v,u)\in\mathcal{E}_{\mathcal{G}}$ and $0$ otherwise. NeuroSed (and
$\textsc{NeuroSed}_{\mathcal{G}}$) 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 Triangle Inequality of Sed: Proof of Theorem. 1

Our proof relies on two lemmas.

###### Lemma 3

Let $\widehat{d}:\Sigma\times\Sigma\rightarrow\mathbb{R}^{+}_{0}$ be a
distance function over $\Sigma$, where (i) $\widehat{d}(\ell_{1},\ell_{2})=0$
if $\ell_{1}=\epsilon$, and (ii)
$\widehat{d}(\ell_{1},\ell_{2})=d(\ell_{1},\ell_{2})$ otherwise; the following
holds:
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})=\widehat{\textsc{Ged}}(\mathcal{G}_{1},\mathcal{G}_{2})$,
where $\widehat{\textsc{Ged}}$ denotes Ged with $\widehat{d}$ as the label set
distance function. In simple words, the Sed between two graphs is equivalent
to Ged with a label set distance function where we ignore insertion costs.

Proof. It suffices to prove (i)
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})\geq\widehat{\textsc{Ged}}(\mathcal{G}_{1},\mathcal{G}_{2})$
and (ii)
$\widehat{\textsc{Ged}}(\mathcal{G}_{1},\mathcal{G}_{2})\geq\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})$.

(i) Let
$\mathcal{S}=(\mathcal{V}_{\mathcal{S}},\mathcal{E}_{\mathcal{S}},\mathcal{L}_{\mathcal{S}})\subseteq\mathcal{G}_{2}$
be the subgraph minimizing $\textsc{Sed}(\mathcal{G}_{1},\mathcal{S})$ (Recall
Eq. 3). Consider the mapping $\pi$ from $\mathcal{G}_{1}$ to $\mathcal{S}$
corresponding to $\textsc{Sed}(\mathcal{G}_{1},\mathcal{S})$ (and hence
$\textsc{Ged}(\mathcal{G}_{1},\mathcal{S})$ as well). We extend $\pi$ to
define a mapping $\widehat{\pi}$ from $\mathcal{G}_{1}$ to $\mathcal{G}_{2}$
by mapping of all nodes in set
$\mathcal{V}_{2}\setminus\mathcal{V}_{\mathcal{S}}$ to dummy nodes in
$\mathcal{G}_{1}$; the edge mappings are defined analogously.

Under this construction,
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{S})=\textsc{Ged}(\mathcal{G}_{1},\mathcal{G}_{2})=\widehat{\textsc{Ged}}_{\widehat{\pi}}(\mathcal{G}_{1},\mathcal{G}_{2})\geq\widehat{\textsc{Ged}}(\mathcal{G}_{1},\mathcal{G}_{2})$.
This follows from the property that under $\widehat{d}$, insertion costs are
zero, that is $\widehat{d}(\epsilon,\ell)=0$. Thus, the additional mappings
introduced in $\widehat{\pi}$ do not incur additional costs under
$\widehat{d}$.

(ii) Consider $\mathcal{S}\subseteq\mathcal{G}_{2}$ and a mapping $\pi$ from
$\mathcal{G}_{1}$ to $\mathcal{S}$ such that
$\textsc{Ged}_{\pi}(\mathcal{G}_{1},\mathcal{S})=\widehat{\textsc{Ged}}(\mathcal{G}_{1},\mathcal{G}_{2})$.
The existence of such a subgraph is guaranteed (See Lemma 5 in Supplementary).
From the definition of Ged,
$\textsc{Ged}_{\pi}(\mathcal{G}_{1},\mathcal{S})\geq\textsc{Ged}(\mathcal{G}_{1},\mathcal{S})$.
Furthermore, since $\mathcal{S}\subseteq\mathcal{G}_{2}$,
$\textsc{Ged}(\mathcal{G}_{1},S)\geq\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})$.
Combining all these results, we have
$\widehat{\textsc{Ged}}(\mathcal{G}_{1},\mathcal{G}_{2})\geq\textsc{Ged}(\mathcal{G}_{1},S)\geq\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})$.
Hence, the claim is proved. $\hfill\square$

###### Lemma 4

$\widehat{d}$, as defined in Lemma 3, satisfies triangle inequality.

Proof. We need to show
$\widehat{d}(\ell_{1},\ell_{3})\leq\widehat{d}(\ell_{1},\ell_{2})+\widehat{d}(\ell_{2},\ell_{3})$.
We divide the proof into four cases:
(i) None of $\ell_{1}$, $\ell_{2}$, $\ell_{3}$ is $\epsilon$. Hence,
$\widehat{d}(\ell_{1},\ell_{3})=d(\ell_{1},\ell_{3})$ and triangle inequality
is satisfied.
(ii) $\ell_{1}=\epsilon$. The Lhs is $0$ and hence triangle inequality is
satisfied.
(iii) $\ell_{1}\neq\epsilon$ and $\ell_{2}=\epsilon$. Lhs$\leq 1$ and Rhs$=1$.
Hence, satisfied.
(iv) Only $\ell_{3}=\epsilon$. Here, Lhs$=1$ and Rhs$\geq 1$.
These four cases cover all possible situations and hence, triangle inequality
is established.$\hfill\square$

From Lemma 3, we know
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})=\widehat{\textsc{Ged}}(\mathcal{G}_{1},\mathcal{G}_{2})$.
Combining Obs. 3 with Lemma 4, $\widehat{\textsc{Ged}}$ satisfies triangle
inequality. Thus, Sed satisfies triangle inequality.$\hfill\square$

####  D.2 Proof of Lemma 5

###### Lemma 5

There exists a subgraph $\mathcal{S}$ of $\mathcal{G}_{2}$ and a node map
$\pi$ from $\mathcal{G}_{1}$ to $\mathcal{S}$ such that
$\textsc{Ged}_{\pi}(\mathcal{G}_{1},\mathcal{S})=\widehat{\textsc{Ged}}(\mathcal{G}_{1},\mathcal{G}_{2})$.

Proof. Let $\pi^{\prime}$ be a node map from $\mathcal{G}_{1}$ to
$\mathcal{G}_{2}$ corresponding to
$\widehat{\textsc{Ged}}(\mathcal{G}_{1},\mathcal{G}_{2})$. Let
$h_{1},\cdots,h_{l}$ be the nodes of $\mathcal{G}_{2}$ which are inserted in
$\pi^{\prime}$. Construct subgraph $\mathcal{S}$ of $\mathcal{G}_{2}$ by
removing nodes $h_{1},\cdots,h_{l}$ and their incident edges from
$\mathcal{G}_{2}$. Let $\pi$ be the node map from $\mathcal{G}_{1}$ to
$\mathcal{S}$ which is obtained by removing
$h_{1}^{\prime},\cdots,h_{l}^{\prime}$ from the domain and
$h_{1},\cdots,h_{l}$ from the co-domain of $\pi$. Since insertion costs are
$0$ in $\widehat{d}$ and $\pi$ contains only non-insert operations, then
$\textsc{Ged}_{\pi}(\mathcal{G}_{1},\mathcal{S})=\widehat{\textsc{Ged}}(\mathcal{G}_{1},\mathcal{G}_{2})$.
Hence, the claim is proved. $\square$

###### Corollary 1

There exists a closest subgraph (Def. 6) $\mathcal{S}$ to $\mathcal{G}_{1}$ in
$\mathcal{G}_{2}$ such that $\mathcal{S}\subseteq\mathcal{G}_{1}$.

Proof. The node map $\pi$ in the above proof contains only non-insert
operations. So, $\mathcal{S}$ in the above proof is a subgraph of
$\mathcal{G}_{1}$ ignoring node and edge labels. Since equality holds in Lemma
3, this $\pi$ gives an optimal edit distance. Thus, $\mathcal{S}$ in the above
proof is also a closest subgraph to $\mathcal{G}_{1}$ in $\mathcal{G}_{2}$.
$\square$

####  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 a
certain kind of distortion, the smaller is its corresponding edit cost.
Concrete values for the edit costs are application-dependent. In this paper we
have discussed binary distance functions which impose a cost of $1$ 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 to 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
$\Sigma$ for which replacement is no more expensive than deletion, i.e.
$d(\ell_{1},\ell_{2})\leq
d(\ell_{1},\epsilon)\forall\ell_{1},\ell_{2}\in\Sigma$. A replacement can be
seen as a compound edit operation consisting of deletion(s) followed by
insertion(s). If a 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 a large class of interesting distance functions which might be used
for the Sed prediction task. We show a generalisation of Lemma 4 to such
distance functions $d$. The other proofs mentioned in the paper are directly
applicable.

###### Lemma 6

Let $d:\Sigma\times\Sigma\rightarrow\mathbb{R}^{+}_{0}$ be a metric and
$d(\ell_{1},\ell_{2})\leq
d(\ell_{1},\epsilon)\forall\ell_{1},\ell_{2}\in\Sigma$. As in Lemma 3, let
$\widehat{d}:\Sigma\times\Sigma\rightarrow\mathbb{R}^{+}_{0}$ be a distance
function over $\Sigma$, where (i) $\widehat{d}(\ell_{1},\ell_{2})=0$ if
$\ell_{1}=\epsilon$, and (ii)
$\widehat{d}(\ell_{1},\ell_{2})=d(\ell_{1},\ell_{2})$ otherwise. Then,
$\widehat{d}$ satisfies the triangle inequality.

Proof. We need to show
$\widehat{d}(\ell_{1},\ell_{3})\leq\widehat{d}(\ell_{1},\ell_{2})+\widehat{d}(\ell_{2},\ell_{3})$.
Consider the three cases:
(i) $\ell_{1}=\epsilon$.
$\textsc{Lhs}=0,\textsc{Rhs}=\widehat{d}(\ell_{2},\ell_{3})\geq 0$ by non-
negativity of $d$. Hence, $\textsc{Lhs}\leq\textsc{Rhs}$.
(ii) $\ell_{1}\neq\epsilon$ and $\ell_{2}=\epsilon$.
$\textsc{Lhs}=d(\ell_{1},\ell_{2}),\textsc{Rhs}=d(\ell_{1},\epsilon)$. Hence,
$\textsc{Lhs}\leq\textsc{Rhs}$ by assumption.
(iii) $\ell_{1}\neq\epsilon$ and $\ell_{2}\neq\epsilon$.
$\textsc{Lhs}=d(\ell_{1},\ell_{3}),\textsc{Rhs}=d(\ell_{1},\ell_{2})+d(\ell_{2},\ell_{3})$.
$\textsc{Lhs}\leq\textsc{Rhs}$ by triangle inequality for $d$.
These cases cover all possible situations. Hence, triangle inequality is
established. $\square$

####  D.4 Data Augmentation

###### Observation 4

Let $\mathcal{S}$ be a closest subgraph (Def. 6) of $\mathcal{G}_{1}$ in
$\mathcal{G}_{2}$. Let $\mathcal{S}^{\prime}$ be a subgraph of
$\mathcal{G}_{2}$ which is also a supergraph of $\mathcal{S}$. Then
$\mathcal{S}$ is also a closest subgraph of $\mathcal{G}_{1}$ in
$\mathcal{S}^{\prime}$ and
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{S}^{\prime})=\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})$.

Proof. The set of subgraphs of $\mathcal{S}^{\prime}$ is a subset of the set
of subgraphs of $\mathcal{G}_{2}$. $\mathcal{S}$ achieves the minimum
$\textsc{Ged}(\mathcal{G}_{1},\mathcal{S})$ among all subgraphs of
$\mathcal{G}_{2}$ and so also the minimum
$\textsc{Ged}(\mathcal{G}_{1},\mathcal{S})$ among all subgraphs of
$\mathcal{S}^{\prime}$. Thus,
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{S}^{\prime})=\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})=\textsc{Ged}(\mathcal{G}_{1},\mathcal{S})$.
$\square$

Observation 4 gives a natural strategy for data augmentation. Once we have
$\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})$ and a closest subgraph
$\mathcal{S}$ from the expensive non-neural computation of
$\textsc{Ged}(\mathcal{G}_{1},\mathcal{G}_{2})$, we can use
$(\mathcal{G}_{1},\mathcal{S}^{\prime},\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2}))$
for all $\mathcal{S}\subseteq\mathcal{S}^{\prime}\subseteq\mathcal{G}_{2}$ as
training examples.

####  D.5 Triangle Inequality for $\mathcal{F}$

This is referred to in the proof for Lemma 1.

###### Lemma 7

$\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})\leq\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}^{\prime}}})+\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{T}^{\prime}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})$,
where
$\mathcal{F}(\mathbf{x},\mathbf{y})=\|\text{ReLU}(\mathbf{x}-\mathbf{y})\|$
for any monotonic norm $\|.\|$.

Proof. Let $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$. We observe that
$(\text{ReLU}(\mathbf{x})+\text{ReLU}(\mathbf{y}))_{i}=\text{ReLU}(\mathbf{x})_{i}+\text{ReLU}(\mathbf{y})_{i}=\text{ReLU}(\mathbf{x}_{i})+\text{ReLU}(\mathbf{y}_{i})\geq\text{ReLU}(\mathbf{x}_{i}+\mathbf{y}_{i})=(\text{ReLU}(\mathbf{x}+\mathbf{y}))_{i}$.
Since $\|.\|$ is monotonic, this implies
$\|\text{ReLU}(\mathbf{x})+\text{ReLU}(\mathbf{y})\|\geq\|\text{ReLU}(\mathbf{x}+\mathbf{y})\|$.

Using the triangle inequality for $\|.\|$, we get
$\|\text{ReLU}(\mathbf{x})\|+\|\text{ReLU}(\mathbf{y})\|\geq\|\text{ReLU}(\mathbf{x})+\text{ReLU}(\mathbf{y})\|\geq\|\text{ReLU}(\mathbf{x}+\mathbf{y})\|$).

Substituting
$\mathbf{x}=\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}-\mathbf{Z}_{\mathcal{G}_{\mathcal{T}^{\prime}}},\mathbf{y}=\mathbf{Z}_{\mathcal{G}_{\mathcal{T}^{\prime}}}-\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}$,
we get,
$\|\text{ReLU}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}-\mathbf{Z}_{\mathcal{G}_{\mathcal{T}^{\prime}}})\|+\|\text{ReLU}(\mathbf{Z}_{\mathcal{G}_{\mathcal{T}^{\prime}}}-\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})\|\geq\|\text{ReLU}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}-\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})\|$

This implies that
$\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}^{\prime}}})+\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{T}^{\prime}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})\geq\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})$.
Our claim is proved. $\hfill\square$

###  E Computation Cost of Sed and Ged Inference

For this analysis, we 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 $g$. 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 $\mathbf{x}_{v}$ of dimension $|\Sigma|$, followed by non-
linearity. This results in $O(|\mathcal{V}|(\lvert\Sigma\rvert\cdot
d+d^{2}L))$ cost.

  * •

Gin: Gin aggregates information from each of the neighbors, which consumes
$O(d\cdot g)$ time. The linear transformation consumes an additional
$O(d^{2})$ time. Applying non-linearity takes $O(d)$ time since it is a linear
pass over the hidden dimensions. Finally these operations are repeated over
each of the $k$ hidden layers, results in a total $O(k(d^{2}+dg))$ computation
time per node. Across, all nodes, the total cost is
$O(|\mathcal{V}|kd^{2}+|\mathcal{E}|kd)$ time. The degree $g$ terms gets
absorbed since each edge passes message twice across all nodes.

  * •

Concatenation: This step consumes $O(kd)$ time per node.

  * •

Pool: Pool iterates over the Gin representation of each node requiring
$O(|\mathcal{V}|dk)$ time.

  * •

Post-Mlp: The final Mlp takes $dk$ dimensional vector as input and maps it to
a $d$ dimensional vector over $L$ layers. This consumes $O(kd^{2}+d^{2}L)$
time.

Combining all these factors, the total inference complexity for a graph is
$O(|\mathcal{V}|(\lvert\Sigma\rvert\cdot d+d^{2}L+kd^{2})+|\mathcal{E}|kd)$.
This operation is repeated on both the query and target graphs to compute
their embeddings, on which distance function $\mathcal{F}$ is operated. Thus,
the final cost is $O(n(\lvert\Sigma\rvert\cdot d+d^{2}L+kd^{2})+mkd)$, where
$n=|\mathcal{V}_{\mathcal{Q}}|+|\mathcal{V}_{\mathcal{T}}|$ and
$m=|\mathcal{E}_{\mathcal{Q}}|+|\mathcal{E}_{\mathcal{T}}|$.

###  F Pipeline Details

Additional Model Details: We add residual connections [23] across blocks of
two Gin convolution layers. This eases the flow of gradients to the earlier
layers by skipping the intermediate non-linearities. We observed about $5$x
speedup in convergence and a marginal improvement in the generalisation error
with residual connections. We use $8$ layers, $64$ hidden dimensions and $64$
embedding dimensions. We use a single layer for pre-Mlp and $2$ layers with
ReLU non-linearity for the other Mlp’s.

Data generation: We generate training data under two different settings
(described in § 4). Sed 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 3 which establishes the relationship between Sed and Ged. More
specifically, we use time limited _mixed integer programming_ method Mip-F2
[32], 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 on a $64$ core machine. This gives sufficiently tight bounds
(with exact values for a large majority of pairs). For evaluation, we use
$\textsc{Sed}=(\textsc{Lb}+\textsc{Ub})/2$ as the ground truth, where Lb and
Ub are the lower and upper bounds respectively. Table F gives the tightness of
Sed bounds in the generated data.

| Dblp | Amazon | PubMed | CiteSeer | Cora_ML | Protein | AIDS
---|---|---|---|---|---|---|---
Range / Sed | 0.434 | 0.409 | 0.039 | 0.188 | 0.103 | 0.202 | 0.004

tableMean Relative Error in Generated Data. Here Range =
$\textsc{Ub}-\textsc{Lb}$, and Sed = $(\textsc{Lb}+\textsc{Ub})/2$.

Loss Function: While $\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}$ and
$\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}$ be the embeddings for the query graph
$\mathcal{G}_{\mathcal{Q}}$ and target graph $\mathcal{G}_{\mathcal{T}}$
respectively, we use the following function (for training):

$H(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}},l,u)=\begin{cases}(F(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})-u)^{2},&F(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})>u\\\
0,&l\leq
F(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})\leq
u\\\
(l-F(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}))^{2},&F(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})<l\end{cases}$

where $l$ 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.

$\mathscr{L}=\frac{1}{\lvert\mathbb{T}\rvert}\sum_{\forall\langle\mathcal{G}_{\mathcal{Q}},\mathcal{G}_{\mathcal{T}},l,u\rangle\in\mathbb{T}}H(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}},l,u)$
(10)

Here, $\mathbb{T}$ is the set of all training samples.

Training details: NeuroSed, NeuroSed-NN and NeuroSed-Dual were trained using
the AdamW [36] 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 [45]. 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 a 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 regularisation due to the high learning rates seen in
each cycle encouraging the optimizer to find flatter regions of minima, giving
better generalisation. It is also robust to hyper-parameter settings.

Subgraph search via neighborhood decomposition:

For large target graphs, it is 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
$k$-hop neighborhood centered at each node in the target graph for some
suitable $k$. The minimum Sed thus computed can be considered as an
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 closest
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 $k$ depending on the expected query distribution. In practice, we are
concerned only with connected subgraphs. Assuming that all the closest
subgraphs (Def. 6) are connected leads to the following result:

###### Theorem 3

Assuming that all closest subgraphs are connected, a closest subgraph
$\mathcal{S}$ to $\mathcal{G}_{1}$ in $\mathcal{G}_{2}$ can be found in an
$l/2$-hop neighborhood $\mathcal{N}_{v}$, centered at some
$v\in\mathcal{V}_{\mathcal{G}_{2}}$, where $l$ is the length of the longest
path in $\mathcal{G}_{1}$.

Proof. By Corollary 1, there exists a closest subgraph $\mathcal{S}$ of
$\mathcal{G}_{1}$ in $\mathcal{G}_{2}$ which is also a subgraph of
$\mathcal{G}_{1}$ ignoring node and edge labels. Under our assumption
$\mathcal{S}$ is connected. So, the diameter of $\mathcal{S}$ is $\leq$ the
length $l$ of the longest path in $\mathcal{G}_{1}$. Since
$\mathcal{S}\subseteq\mathcal{G}_{2}$, $\mathcal{S}$ is contained in some
$l/2$ neighborhood of $\mathcal{G}_{2}$. $\hfill\square$

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 $l$. The closest
subgraph having a diameter equal to $l$ is rare. In practice, the diameter of
the closest subgraph is unlikely to 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 in 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.

###  G 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 a node is the venue where the authors has published most frequently. The
dataset has been obtained from https://www.aminer.org/citation. Considering
the intractability of obtaining ground-truth Sed for large graphs and many
node labels, we only take nodes with neighborhood size $\leq 1000$, and group
the node labels into $8$ classes.

Amazon: Each node in Amazon 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 a single label on all nodes. The
dataset has been downloaded from [33].

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 is 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: CiteSeer is a 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 [8].

Cora_ML: Cora dataset is a citation dataset consisting of many scientific
publications classified into one of seven classes based on paper topic.
Cora_ML is a smaller datset extracted from Cora [8].

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 a collection of program dependence graphs, where each
graph is a function and nodes represent statements while edges represent
dependency between statements.

IMDB: IMDB dataset is a collection of ego-networks of actors/actresses that
have appeared together in any movie.

We use the same versions of AIDS’, Linux, and IMDB as used in [2]. For all
datasets, we use only connected graphs.

###  H Experimental Setup

Hardware Details: We use a 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 [2] and H2MN-ne/H2MN-rw [53]: We train the model with
$\frac{\textsc{Lb}+\textsc{Ub}}{2}$ as the ground truth value of Sed (Lb and
Ub are lower and upper bounds for Sed respectively). Now let $\mathcal{G}_{1}$
be the query graph, and $\mathcal{G}_{2}$ be the target graph, we use
$n\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})$ =
$\frac{\textsc{Sed}(\mathcal{G}_{1},\mathcal{G}_{2})}{|\mathcal{G}_{1}|}$
instead of $n\textsc{Ged}(\mathcal{G}_{1},\mathcal{G}_{2})$ =
$\frac{\textsc{Ged}(\mathcal{G}_{1},\mathcal{G}_{2})}{(|\mathcal{G}_{1}|+|\mathcal{G}_{2}|)/2}$
as the normalized value of similarity in SimGnn. This is because the absolute
value of Sed scales with the size of the query, as opposed to Ged, which
scales with size of the query as well as the target.

  * •

NeuroMatch [37]: 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 to better fit our data distribution.

Software details: We used PyTorch [39] and PyTorch-Geometric [20] for
implementation. All experiments were done using Jupyter Notebooks [28]. The
full code, notebooks for all experiments and the generated data are available
at our GitHub repository444https://github.com/idea-iitd/NeuroSED.

###  I Additional Results

####  I.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 we evaluate the same performance
using several other metrics such as Mean Absolute Error (MAE) and $R^{2}$.
Tables 1g and 1h show the MAE scores for Sed and Ged respectively. Tables 1i
and 1j 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 Branch is competitive only on IMDB for Ged
prediction and H2MN-ne is better in Linux only for Ged prediction.

Methods | Dblp | Amazon | PubMed | CiteSeer | Cora_ML | Protein | AIDS
---|---|---|---|---|---|---|---
NeuroSed | 0.626 | 0.207 | 0.474 | 0.332 | 0.432 | 0.377 | 0.401
H2MN-rw | 0.926 | 0.480 | 0.764 | 0.882 | 0.824 | 0.575 | 0.566
H2MN-ne | 0.966 | 0.465 | 0.831 | 1.094 | 0.797 | 0.518 | 0.510
SimGnn | 0.911 | 1.257 | 0.853 | 1.068 | 0.841 | 0.835 | 0.545
Branch | 2.156 | 3.697 | 1.692 | 2.275 | 2.277 | 1.986 | 1.092
Mip-F2 | 2.165 | 3.303 | 1.528 | 1.940 | 1.834 | 1.264 | 0.684

(g) Prediction of Sed.

Methods | AIDS’ | Linux | IMDB
---|---|---|---
$\textsc{NeuroSed}_{\mathcal{G}}$ | 0.629 | 0.318 | 3.612
H2MN-rw | 0.777 | 0.534 | 28.486
H2MN-ne | 0.779 | 0.176 | 28.182
SimGnn | 0.816 | 0.489 | 28.082
Branch | 2.895 | 2.017 | 3.303
MIP-F2 | 2.184 | 0.480 | 36.460

(h) Prediction of Ged

table MAE scores (lower is better) in (a) Sed and (b) Ged.

Methods | Dblp | Amazon | PubMed | CiteSeer | Cora_ML | Protein | AIDS
---|---|---|---|---|---|---|---
NeuroSed | 0.97 | 0.99 | 0.99 | 0.99 | 0.99 | 0.98 | 0.98
H2MN-rw | 0.94 | 0.97 | 0.97 | 0.98 | 0.97 | 0.94 | 0.95
H2MN-ne | 0.93 | 0.98 | 0.97 | 0.97 | 0.98 | 0.96 | 0.96
SimGnn | 0.94 | 0.85 | 0.97 | 0.97 | 0.97 | 0.9 | 0.95
Branch | 0.75 | 0.63 | 0.88 | 0.91 | 0.86 | 0.64 | 0.82
Mip-F2 2 | 0.65 | 0.44 | 0.80 | 0.83 | 0.79 | 0.68 | 0.78

(i) Prediction of Sed.

Methods | AIDS’ | Linux | IMDB
---|---|---|---
$\textsc{NeuroSed}_{\mathcal{G}}$ | .91 | .97 | .99
H2MN-rw | .86 | .92 | .66
H2MN-ne | .86 | .98 | .65
SimGnn | .84 | .93 | .80
Branch | -.55 | .14 | .98
MIP-F2 | -.20 | .78 | .69

(j) Prediction of Ged

table $R^{2}$ scores (higher is better, $1$ is maximum) in (a) Sed and (b)
Ged.

####  I.2 Precision$@k$ on $k$-NN queries

Fig. 6 shows Precision$@k$ on $k$-NN queries. As visible, NeuroSed is
comfortably among the best performing algorithms.

(a) PubMed

(b) CiteSeer

(c) Cora_ML

(d) Protein

(e) AIDS

(f) AIDS’

(g) Linux

(h) IMDB

Figure 6: Precision@$k$ for $k$-NN queries on Sed (a-e) and Ged (f-h).

####  I.3 Additional Results on Ablation Study

Impact of Gin: 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 I.3, 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 [49].

Methods |  Amazon (Sed) |  PubMed (Sed) |  CiteSeer (Sed) |  IMDB (Ged)
---|---|---|---|---
NeuroSed (Gin) | 0.495 | 0.728 | 0.519 | 6.734
NeuroSed-GCN | 0.532 | 0.756 | 0.556 | 12.151
NeuroSed-GraphSage | 1.841 | 1.156 | 1.364 | 91.312
NeuroSed-GAT | 1.843 | 1.259 | 1.294 | 89.034

tableAblation 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 our choice of the pooling layer, we have
performed ablation studies with various pooling functions as replacements for
sum-pool. It is clear from Table I.3 that sum-pool is the best choice among
the considered alternatives.

Pool functions |  Amazon (Sed) |  PubMed (Sed) |  CiteSeer (Sed) |  IMDB (Ged)
---|---|---|---|---
NeuroSed (Sum) | 0.495 | 0.728 | 0.519 | 6.734
NeuroSed-Max | 0.603 | 0.709 | 0.795 | 52.519
NeuroSed-Mean | 0.846 | 0.732 | 0.922 | 52.483
NeuroSed-Attention | 0.868 | 0.797 | 0.914 | 130.47

tableAblation studies: sum-pool vs others. The sum-pool is the best choice
among the considered alternatives.

####  I.4 Alignment

In real-world applications of subgraph similarity search, alignments are of
interest only for a small number of similar subgraphs. Our framework is
intended to serve as a filter to retrieve this small set of similar subgraphs
from a large number of candidates. To elaborate, a graph database may contain
thousands or millions of graphs (or alternatively, thousands or millions of
neighborhoods of a large graph) which need to be inspected for similar
subgraphs. A user is typically interested in only a handful of these subgraphs
that are highly similar to the query. Since the filtered set is significantly
smaller, a non-neural exact algorithm suffices to construct the alignments
(Lemma 3 allows us to adapt general cost Ged alignment techniques for Sed
alignment). Computing alignments across the entire database is 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$-NN
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 Amazon since it
computes alignments across all (sub)graphs.

Methods | Amazon | PubMed
---|---|---
NeuroSed Retrieval | 6.471 | 0.373
Mip-F2 Alignment | 68.4 | 52.8

tableThe average runtime components in seconds for $10$-NN query. Mip-F2
alignment is feasible for a small number of graphs retrieved by NeuroSed.

###  J Retrieval using Index Structures

Linear Scan: For a new query $G_{Q}$, we first obtain its embedding
$\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}}$. Based on the stored embeddings
$\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}$ of the target graphs, we compute
$\textsc{Sed}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})$
for all
$\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}\in\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}}$
using the function
$\mathcal{F}(\mathbf{Z}_{\mathcal{G}_{\mathcal{Q}}},\mathbf{Z}_{\mathcal{G}_{\mathcal{T}}})$.
We sort the targets based on the obtained Sed values and use it to answer
$k$-NN and range queries. Note that all target graphs are scanned for every
query.

Adapted Metric Tree: Our adaptation of Metric Tree [46] to asymmetric
functions satisfying triangle inequality is shown in Algorithms 1 and 2
($k$-NN query is similar, see code for details). This speeds up retrieval by
avoiding Sed prediction for subtrees pruned using bounds derived from triangle
inequality. A similar modification can be applied to more advanced index
structures, such as M-Tree [13] which also supports efficient dynamic
insertion and deletion of graphs from the database.

The tree construction times were $0.139$s, $2.98$s and $16.8$s for PubMed,
Amazon and Dblp respectively.

Algorithm 1 Build

0: set $D$ of objects, distance function $d(x,y)$ which satisfies triangle
inequality

0: root node of the constructed tree

if $D=\phi$ then

return null

end if

select arbitrary pivot $p\in D$

$m_{1}\leftarrow\textsc{Median}(\\{d(p,y):y\in D-\\{p\\}\\})$

$m_{2}\leftarrow\textsc{Median}(\\{d(y,p):y\in D-\\{p\\}\\})$

$D_{1}\leftarrow\\{y:d(p,y)\leq m_{1},d(y,p)\leq m_{2}\\}$

$D_{2}\leftarrow\\{y:d(p,y)\leq m_{1},d(y,p)>m_{2}\\}$

$D_{3}\leftarrow\\{y:d(p,y)>m_{1},d(y,p)\leq m_{2}\\}$

$D_{4}\leftarrow\\{y:d(p,y)>m_{1},d(y,p)>m_{2}\\}$

for $i=1$ to $4$ do

$t_{i}\leftarrow\textsc{Build}(D_{i},d)$

end for

return $\textsc{node}(p,m_{1},m_{2},t_{1},t_{2},t_{3},t_{4})$

Algorithm 2 RangeQuery

0: query object $q$, threshold $r$, root node $t$ of (sub)tree

0: $\\{y|d(q,y)\leq r\\}$

if $t=\textsc{null}$ then

return $\phi$

end if

let $t=\textsc{node}(p,m_{1},m_{2},t_{1},t_{2},t_{3},t_{4})$

if $d(p,q)\leq m_{1}-r$ then

mark $t_{3}$ and $t_{4}$ for pruning

end if

if $d(q,p)>m_{2}+r$ then

mark $t_{1}$ and $t_{3}$ for pruning

end if

if $d(q,p)\leq r-m_{1}$ then

$S\leftarrow$ all $y$ in $t_{1}$ and $t_{2}$

mark $t_{1}$ and $t_{2}$ for pruning

else

$S\leftarrow\phi$

end if

for $i=1$ to $4$ do

if $t_{i}$ is not marked for pruning then

$S\leftarrow S\cup\textsc{RangeQuery}(q,r,t_{i})$

end if

end for

return $S$

###### Theorem 4

Correctness of the adaptation.

Proof. We show that any pruning does not affect the correctness of the
returned answer set.

  1. 1.

If $d(p,q)\leq m_{1}-r$, then for any $y$ in the solution set $\\{y|d(q,y)\leq
r\\}$, we have $d(p,y)\leq m_{1}$ using $d(p,y)\leq d(p,q)+d(q,y)$. Since
$t_{3}$ and $t_{4}$ contain only $y$ such that $d(p,y)>1$, pruning them
preserves the solution set.

  2. 2.

If $d(q,p)>m_{2}+r$, then for any $y$ in the solution set $\\{y|d(q,y)\leq
r\\}$, we have $d(y,p)>m_{2}$ using $d(q,p)\leq d(q,y)+d(y,p)$. Since $t_{1}$
and $t_{3}$ contain only $y$ such that $d(y,p)\leq m_{2}$, pruning them
preserves the solution set.

  3. 3.

If $d(q,p)\leq r-m_{1}$, then for all y such that $d(p,y)\leq m_{1}$ we have
$d(q,y)\leq r$ using $d(q,y)\leq d(q,p)+d(p,y)$. Since $d(p,y)\leq m_{1}$ for
all $y$ in the subtrees $t_{1}$ and $t_{2}$, all $y$’s in $t_{1}$ and $t_{2}$
are parts of the solution set.

$\hfill\square$

###  K Heat Maps for Prediction Error

In Figures 7 to 16, we show the variation of the errors on Sed and Ged
prediction with query sizes and ground truth values for NeuroSed
($\textsc{NeuroSed}_{\mathcal{G}}$ for Ged) and the baselines on all the
corresponding datasets. This experiment is an extension of the heat-map
results in Fig. 4.1 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 $\textsc{NeuroSed}_{\mathcal{G}}$, we see a 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.

(a) NeuroSed (b) H2MN-rw (c) H2MN-ne (d) SimGnn (e) Branch (f) Mip-F2

Figure 7: Heat Maps of Sed error against query size and Sed values for Dblp.
Darker means higher error.

(a) NeuroSed (b) H2MN-rw (c) H2MN-ne (d) SimGnn (e) Branch (f) Mip-F2

Figure 8: Heat Maps of Sed error against query size and Sed values for Amazon.
Darker means higher error.

(a) NeuroSed (b) H2MN-rw (c) H2MN-ne (d) SimGnn (e) Branch (f) Mip-F2

Figure 9: Heat Maps of Sed error against query size and Sed values for PubMed.
Darker means higher error.

(a) NeuroSed (b) H2MN-rw (c) H2MN-ne (d) SimGnn (e) Branch (f) Mip-F2

Figure 10: Heat Maps of Sed error against query size and Sed values for
CiteSeer. Darker means higher error.

(a) NeuroSed (b) H2MN-rw (c) H2MN-ne (d) SimGnn (e) Branch (f) Mip-F2

Figure 11: Heat Maps of Sed error against query size and Sed values for
Cora_ML. Darker means higher error.

(a) NeuroSed (b) H2MN-rw (c) H2MN-ne (d) SimGnn (e) Branch (f) Mip-F2

Figure 12: Heat Maps of Sed error against query size and Sed values for
Protein. Darker means higher error.

(a) NeuroSed (b) H2MN-rw (c) H2MN-ne (d) SimGnn (e) Branch (f) Mip-F2

Figure 13: Heat Maps of Sed error against query size and Sed values for AIDS.
Darker means higher error.

(a) NeuroSed G (b) H2MN-rw (c) H2MN-ne (d) SimGnn (e) Branch (f) Mip-F2

Figure 14: Heat Maps of Ged error against query size and Ged values for AIDS’.
Darker means higher error.

(a) NeuroSed G (b) H2MN-rw (c) H2MN-ne (d) SimGnn (e) Branch (f) Mip-F2

Figure 15: Heat Maps of Ged error against query size and Ged values for Linux.
Darker means higher error.

(a) NeuroSed G (b) H2MN-rw (c) H2MN-ne (d) SimGnn (e) Branch (f) Mip-F2

Figure 16: Heat Maps of Ged error against query size and Ged values for IMDB.
Darker means higher error.