Year: 2021

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

heading: 1 INTRODUCTION AND RELATED WORK
text: Graphs are used to model data in a wide variety of domains. Examples include chemical compounds (Sankar et al., 2017), protein-protein interaction networks (PPI) (Alon et al., 2008), knowledge graphs (Ebsch et al., 2020), and social networks (Kempe et al., 2003). 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 (Liang & Zhao, 2017; Zhao et al., 2013; Bougleux et al., 2017; Daller et al., 2018; Fankhauser et al., 2011; Riesen & Bunke, 2009; Zeng et al., 2009; He & Singh, 2006). Edit distance can be posed in two forms: graph edit distance (GED) and subgraph edit distance (SED). Given two graphs G1 and G2, GED(G1,G2) returns the minimum cost of edits needed to convert G1 to G2. i.e., for G1 to become isomorphic to G2. An edit can be the addition or deletion of edges and nodes, or replacement of edge or node labels, with an associated cost. In SED(G1,G2), the goal is to identify the minimum cost of edits so that G1 is a subgraph (subgraph isomorphic) of G2. For examples, see Fig. 5a in the appendix. While the applications of GED and SED are beyond doubt, their applicability is constrained by their computation costs. Specifically, both GED and SED are NP-complete (Zeng et al., 2009; Neuhaus et al., 2006; He & Singh, 2006). To mitigate this computational bottleneck, several heuristics (Bougleux et al., 2017; Daller et al., 2018; Fankhauser et al., 2011; Riesen & Bunke, 2009; Neuhaus et al., 2006) and index structures (He & Singh, 2006; Zeng et al., 2009; Liang & Zhao, 2017; Zhao et al., 2013) have been proposed. Recently, graph neural networks have been shown to be effective in learning and predicting GED (Bai et al., 2019; Wang et al., 2021; Li et al., 2019; Bai et al., 2020; Zhang et al., 2021; Xiu et al., 2020) and subgraph isomorphism (Rex et al., 2020). The basic goal in all these 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. Wang et al. (2020) designed an algorithm to characterize graphs through sampling random walks and then embedding them in a feature space. While Wang et al. (2020) has not been studied in the context of GED or SED, the authors have shown that they can detect graph isomorphism. While this progress in the area of graph querying is undoubtedly impressive, there is scope to do more. • Modeling SED: Existing neural approaches to learning GED cannot easily be adapted to learn
SED. While GED is symmetric, SED is not. Most neural architectures for GED have the assumption of symmetry at its core and hence modeling SED is non-trivial. In App. A, we provide a detailed analysis of the limitations of prior architectures in failing to model SED.
• Exponential Search Space: Computing SED(G1,G2) conceptually requires us to compare the query graph G1 with the exponentially many subgraphs of the target graph G2. Therefore, it is imperative that the model has an efficient and effective mechanism to prune the search space without compromising on the prediction accuracy. We note that while several index structures and heuristics exist for GED (He & Singh, 2006; Zeng et al., 2009; Bai et al., 2019; Wang et al., 2021), none exist for SED. Thus, scalability of SED on large graphs remains an unsolved problem. • Preservation of theoretical properties: GED is a metric distance function. While SED is not metric due to being asymmetric, it satisfies the triangle inequality, non-negativity, and subgraphidentity. Several higher-order tasks such as clustering and indexing rely on such properties (Hadi, 1991; Dohnal et al., 2003; Hjaltason & Samet, 2003; Samet, 2005; Uhlmann, 1991; Yianilos, 1993; Zezula et al., 2006; Brin, 1995; Chávez et al., 2001). Existing neural approaches do not preserve these properties, which limits their usability for these higher order tasks. • Pair-independent computation: There is little scope for pre-computation in existing approaches (either neural or non-neural), as the major computations are pair-dependent, i.e., both G1 and G2 need to be known. In a typical graph querying framework, the graph database is known apriori; only the query graph is provided at runtime. If we can generate pair-independent embeddings, and make efficient predictions directly in the embedding space, then retrieval can be sped up tremendously by pre-computing and indexing the embeddings of the database graphs beforehand. • Learning with low-volume data: Generating a large amount of high quality training data is computationally prohibitive for SED/GED. So, an effective model should encode powerful priors for SED/GED prediction, to enable generalization even with scarce training data.
We address these challenges by 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 (Xu et al., 2018a) 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 G1 and G2, which captures the prior that similar topological properties need to be considered for both graphs. The carefully crafted prediction function serves as another inductive bias for the model, which, in addition to enabling high generalization accuracy, preserves the key properties of SED/GED, which is a major contribution of our work over existing neural approaches. • Indexable embeddings: The prediction function satisfies the triangle inequality over the embedding space for both SED and GED. This allows utilization of the rich literature on index structures (Elkan, 2003; Kwedlo & Czochanski, 2019; Ciaccia et al., 1997) to boost efficiency. • Accurate, Fast and Scalable: Extensive experiments on real graph datasets containing up to a million nodes establish that NEUROSED is more accurate in both GED and SED when compared to the state of the art and is more than 3 orders of magnitude faster in range and k-NN queries.

heading: 2 PRELIMINARIES AND PROBLEM FORMULATION
text: We denote a labeled undirected graph as G = (V, E ,L) where V is the node set, E is the edge set and L : V ∪ E → Σ is the labeling function over nodes and edges. Σ is the universe of all labels and contains a special empty label . L(v) and L(e) denote the labels of node v and edge e respectively. G1 ⊆ G2 denotes that G1 is a subgraph of G2. All notations used in our work are summarized in Table 6 in the appendix. For the definitions of subgraph and graph isomorphism, refer to App. B in the supplementary. The computation of GED relies on a graph mapping.
Definition 1 (Graph Mapping) Given two graphs G1 and G2, let G̃1 = (Ṽ1, Ẽ1, L̃1) and G̃2 = (Ṽ2, Ẽ2, L̃2) be obtained by adding dummy nodes and edges (labeled with ) to G1 and G2 respectively, such that |V1| = |V2| and |E1| = |E2|. A node mapping between G1 and G2 is a bijection π : G̃1 → G̃2 where (i) ∀v ∈ Ṽ1, π(v) ∈ Ṽ2 and at least one of v and π(v) is not a dummy; (ii) ∀e = (v1, v2) ∈ Ẽ1, π(e) = (π(v1), (π(v2))) ∈ Ẽ2 and at least one of e and π(e) is not a dummy.
Example 1 Fig. 5b shows a graph mapping. Edge mappings can be trivially inferred, so are omitted.
Definition 2 (Graph Edit Distance (GED) under mapping π) GED between G1 and G2 under π is GEDπ(G1,G2) = ∑ v∈Ṽ1 d(L(v),L(π(v))) + ∑ e∈Ẽ1 d(L(e),L(π(e))) (1)
where d : Σ× Σ→ R+0 is a distance function over the label set. d(`1, `2) models an insertion if `1 = , deletion if `2 = and replacement if `1 6= `2 and neither `1 nor `2 is a dummy. We assume d to be a binary function, where d(`1, `2) = 1 if `1 6= `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. 5b is 3. The red mappings incur a cost of 1.
Definition 3 (Graph Edit Distance (GED)) GED is the minimum distance under all mappings. GED(G1,G2) = min
∀π∈Φ(G1,G2) GEDπ(G1,G2) (2)
where Φ(G1,G2) denotes the set of all possible node maps from G1 to G2.
Definition 4 (Subgraph Edit Distance (SED)) SED is the minimum GED over all subgraphs of G2. SED(G1,G2) = min
S⊆G2 GED(G1,S) (3)
Example 3 Revisiting Fig. 5b, GED(G1,G2) = 3. The shown mapping incurs the minimum cost. SED(G1,G2) = 1. Refer to Fig. 5a for more examples.
Problem 1 (Learning SED) Given a training set of tuples of the form 〈G1,G2, SED(G1,G2)〉, learn a neural model to predict SED(Q1,Q2) on unseen graphs Q1 and Q2.
Problem 2 (Learning GED) Given a training set of tuples of the form 〈G1,G2,GED(G1,G2)〉, learn a neural model to predict GED(Q1,Q2) on unseen graphs Q1 and Q2.

heading: 2.1 PROPERTIES OF SED AND GED
text: Observation 1 (i) GED(G1,G2) ≥ 0, (ii) SED(G1,G2) ≥ 0.
Observation 2 (i) GED(G1,G2) = 0 iff G1 is isomorphic to G2, (ii) SED(G1,G2) = 0 iff G1 is subgraph isomorphic to G2.
Observation 3 GED is a metric if the distance function d over label set Σ is metric (He & Singh, 2006). d as defined in § 2 is metric (He & Singh, 2006). Hence, GED from § 2 is metric. We next prove that SED satisfies the triangle inequality in Theorem 1.
Theorem 1 SED(G1,G3) ≤ SED(G1,G2) + SED(G2,G3). PROOF: See App. D.1 for details.

heading: 3 NEUROSED
text: Fig. 1 presents the architecture of NEUROSED. The input to our learning framework is a pair of graphs GQ (query), GT (target) along with the supervision data SED(GQ,GT ). 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: 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.

heading: 3.1 SIAMESE GRAPH NEURAL NETWORK
text: As depicted in Fig. 1a, we use a siamese graph neural network (GNN) with shared parameters to embed both GQ and GT . Fig. 1b 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 xv denote the initial feature set of node v. The MLP learns a hidden representation µGv = MLP (xv). In our implementation, xv 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 by strategies such as using GINE (Hu et al., 2019) layers instead of GIN layers (see App. C).
Graph Isomorphism Network (GIN): GIN (Xu et al., 2018b) 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 (Leman & Weisfeiler, 1968) 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 G is characterized by the representation learned by the MLP, i.e., hGv,0 = µGv . Subsequently, in each hidden layer i, we learn an embedding through the following transformation.
hGv,i = MLP (1 + i) · hGv,i−1 + ∑ u∈NG(v) hGu,i−1  (4) Here, i is a layer-specific learnable parameter, NG(v) is one-hop neighbourhood of the node v, and hGv,0 = µ G v . The k-th layer embedding is h G v,k, where k is final hidden layer.
Concatenation, Pool and Post-MLP: Intuitively, hGv,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 zGv = CONCAT ( hGv,i,∀i ∈ {1, 2, · · · , k} ) . 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:
ZG = MLP(zG) = MLP (∑ v∈V zGv ) (5)
SED Prediction: The final task is to predict the SED as a function of query graph embedding ZGQ and target graph embedding ZGT . The natural choice would be to feed these embeddings into another MLP to learn SED(ZGQ ,ZGT ). This MLP can then be trained jointly with the graph embedding model in an end-to-end fashion. However, an MLP prediction does not have any theoretical guarantees.
To ensure preservation of original space properties, we introduce an inductive bias in the form of a simple fixed computation function F(ZGQ ,ZGT ) to predict the SED. By training the model to produce embeddings ZGQ and ZGT such that F(ZGQ ,ZGT ) ≈ SED(ZGQ ,ZGT ), 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 (Bai et al., 2019; Wang et al., 2021; Bai et al., 2020; Zhang et al., 2021). F is defined as follows:
F(ZGQ ,ZGT ) = ‖ReLU(ZGQ − ZGT )‖2 = ‖max {0,ZGQ − ZGT }‖2 (6) Intuitively, for those co-ordinates where the value of ZGQ is greater than ZGT ; a distance penalty is accounted by F in terms of how much those values differ, otherwise F considers 0. This follows the intuition that the SED accounts for those features of GQ that are not in GT . Moreover, consistent with SED, the additional features in GT that are not in GQ, do not incur any cost. Finally, the parameters of the entire model are learned by minimizing the mean squared error1 (here T is the training set).
L = 1 |T| ∑
∀〈GQ,GT 〉∈T
( F(ZGQ ,ZGT )− SED(GQ,GT ) )2 (7)
1Since SED computation is NP-hard, in App. G, we discuss a loss function based on SED lower and upper bounds, which are faster to compute.
Adaptation for GED (NEUROSEDG): The proposed architecture naturally extends to GED (denoted by NEUROSEDG) with a simple modification of the computation function. Specifically, instead of Eq. 6, we use Fg(ZGQ ,ZGT ) = ‖ZGQ − ZGT ‖2 (8)

heading: 3.2 THEORETICAL CHARACTERIZATION
text: Lemma 1 The following properties hold on predicted SED F(ZGQ ,ZGT ): 1. F(ZGQ ,ZGT ) ≥ 0 2. F(ZGQ ,ZGT ) = 0 ⇐⇒ ZGQ ≤ ZGT 3. F(ZGQ ,ZGT ) ≤ F(ZGQ ,ZGT ′ ) + F(ZGT ′ ,ZGT ) PROOF. Properties (1) and (2) follow from the definition of F itself. Property (3) follows from the fact that we take the L2 norm (holds for any monotonic norm, details are available in App. D).
We see that F satisfies the analogue of properties of SED (§ 2.1). Conditions 1, 2, and 3 captures non-negativity, the subgraph relation (Rex et al., 2020), and triangle inequality respectively.
Furthermore, we show in App. E a complete constructive characterization for any F which can model SED in the embedding space, while being translation-invariant and non-negative homogeneous. Specifically, we show that the general form for F involves solving a constrained optimization problem (intractable in general), but under a mild technical assumption a closed form can be obtained which coincides with equation 6. This asserts that equation 6 is the natural choice for F , modulo the choice of norm. L2 norm is a natural choice due to its isotropy (direction/rotation invariance) and good empirical performance.
Lemma 2 The predicted GED, i.e., Fg is metric. (i) Non-negativity: Fg(ZGQ ,ZGT ) ≥ 0, (ii) Identity: Fg(ZGQ ,ZGT ) = 0 ⇐⇒ ZGQ = ZGT , (iii) Symmetry: Fg(ZGQ ,ZGT ) = Fg(ZGT ,ZGQ), (iv) Triangle Inequality: Fg(ZGQ ,ZGT ) ≤ Fg(ZGQ ,ZT ′) + Fg(ZT ′ ,ZGT ). PROOF. Follows trivially from the fact that Fg forms a Euclidean space. Similar to F , the form for Fg also comes naturally from some mild technical assumptions for any embedding space function which models GED (see App. E).
Theorem 2 The properties of SED (and GED) in § 2.1 are satisfied by the prediction functions NEUROSED(G1,G2) (and the GED version NEUROSEDG(G1,G2)). PROOF SKETCH. (For SED) Let E be the embedding function learned by NEUROSED’s GNN. Then NEUROSED(G1,G2) = F(E(G1), E(G2)). Now, the relevant properties follow from Lemma 1 using the substitutions ZGQ 7→ E(G1),ZGT 7→ E(G2), and ZGT ′ 7→ E(G3). We note here that if different embedding models are used for G1 and G2, or if the distance computations are pair-dependent (Li et al., 2019), then Theorem 2 would not hold. It is easy to verify that the proof fails if EQ and ET are different embedding functions corresponding to the query and the target, or if E is a function of both G1 and G2. Hence, the siamese architecture is crucial. Complexity analysis: Inference is linear in query and target sizes (see App. F for details).

heading: 3.3 COMPARISON WITH NEUROMATCH (REX ET AL., 2020):
text: Both NEUROSED and NEUROMATCH use siamese GNNs. However, there are important differences in (1) their objectives, (2) training and (3) inference procedures and (4) theoretical characterization.
1. Objective: While NEUROSED is trained to predict GED and SED directly, NEUROMATCH studies the simpler task of anchored subgraph isomorphism. Thus, NEUROSED subsumes the objective of NEUROMATCH. 2. Training: NEUROMATCH trains the model to construct order embeddings wherein if G1 ⊆ G2, then ∀i, ZG1 [i] ≤ ZG2 [i], where ZG denotes the embedding of graph G. To inject this bias, the model is trained using max-margin loss. NEUROSED does not enforce order embeddings. Rather it learns embeddings that make the proposed prediction functions (Eq. 6 and Eq. 8) effective through RMSE loss. In the context of SED, Eq. 6 is used in the loss function of both NEUROSED and NEUROMATCH. However, the loss function themselves are different, which results in the proposed embedding space being considerably richer in its ability to preserve properties from the original space. In addition, in App. E, we characterize the class of functions that may act as a substitute for Eq. 6, and thereby perform a thorough theoretical characterization of our work.
3. Inference: NEUROSED creates a single embedding of the query graph, based on which the SED and GED predictions are made. In contrast, NEUROMATCH generates embeddings for each node neighborhood in the query and target graph and makes |VQ||VT | predictions corresponding to each pair of neighborhoods. The final decision of whether the query is a subgraph of the target is performed using a voting mechanism.

heading: 4 EMPIRICAL EVALUATION
text: In this section, we establish the following: • Subgraph Search: NEUROSED outperforms the state of the art approaches for SED prediction. • Graph Search: NEUROSEDG , the variation to predict GED, outperforms the state of the art
approaches for GED prediction. • Scalability: NEUROSED and NEUROSEDG are orders of magnitude faster than existing approaches
and scale well to graphs with millions of nodes.
The code base and datasets are available at https://anonymous.4open.science/r/NeuroSED/.

heading: 4.1 EXPERIMENTAL SETUP
text: Details on the hardware and software platform and parameters are provided in App. I. Datasets: Table 4.1 lists the datasets used for benchmarking. Further details on the dataset semantics are provided in the App. H. 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.|V| Avg.|E| |Σ| #Graphs Avg.|VQ| |Avg.EQ| Dblp 1.66M 7.2M 8 1 15 14 Amazon 334k 925k 1 1 12 16 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
5 10 15
20
25
Q ue ry S iz e
Figure 2: Heat Map of SED error against query size in Dblp. Darker means higher error.
Training (and Test) Data Generation: For GED, we use 〈query, target〉 graph pairs from IMDB, AIDS’, and Linux. Our setup is identical to SIMGNN (Bai et al., 2019) and H2MN-RW (Zhang et al., 2021). For SED, the procedure is more intricate. The details of datasets can be found in App. H.
• Queries: In single large graphs, queries are sampled by performing a random BFS traversal (depth up to 5) on a randomly chosen target graph. In addition, for AIDS, we use known functional groups as test queries (See App. G for details). This allows us to benchmark NEUROSED on both natural as well synthetic queries. The average query sizes (|VQ|, |EQ|) are listed in Table 4.1. • Ground-truth: We use mixed integer programming method F2 (Lerouge et al., 2017) implemented in GEDLIB (Blumenthal et al., 2019) 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.
Baselines: To evaluate performance in GED, we compare with SIMGNN2 (Bai et al., 2019), GENNA∗ (Wang et al., 2021) and H2MN(Zhang et al., 2021). 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 (Rex et al., 2020) 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 in to adapt to SED are in App. I.
2We use the PyTorch implementation of SIMGNN given on paperswithcode. The code of all other neural algorithms have been obtained from the respective authors.
In the non-neural category, we use mixed integer programming based method MIP-F2 (Lerouge et al., 2017) with a time bound of 0.1 seconds per pair for both GED and SED. MIP-F2 provides the optimal solution given infinite time. In addition, we also compare with BRANCH (Blumenthal, 2019), which achieves an excellent trade-off between accuracy and runtime (Blumenthal et al., 2020). BRANCH uses linear sum assignment problem with error-correction (LSAPE) to process the search space. We use GEDLIB’s (Blumenthal et al., 2019) implementation of these methods.

heading: 4.2 PREDICTION ACCURACY OF SED AND GED
text: Tables 2a and 2b present the accuracy of all techniques on SED and GED in terms of Root Mean Square Error (RMSE). In App. J, we evaluate the same performance using several other metrics such as R2 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. 2, we plot the heat map of RMSE against query graph size in Dblp. Specifically in this plot, each dot corresponds to a query graph GQ. The co-ordinate of a query is (SED(GQ,GT ), |VQ|). 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 are provided in App. L.
Range and 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 θ, the goal is to retrieve all database graphs that are within θ 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) and Kendalls’s tau (k-NN) (Kendall, 1938) of the predicted answer set, when compared against the ground truth.
As visible in Figs. 3a-3h, NEUROSED consistently outperforms all baselines in F1-score. Similar trend is also visible in k-NN queries. Specifically, in Kendall’s tau (Tables 3a and 3b), barring the exception of GED in Linux, NEUROSED consistently scores the highest indicating best preservation of the ranking order. Overall, this shows that accurate prediction of distance also transfers to accurate querying accuracy. In App. K, we also report k-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.

heading: 4.3 EFFICIENCY
text: Table 4 presents the inference time per 10K graph pairs. As visible, NEUROSED is up to 1800 times faster than the non-neural baselines and up to 10 to 20 times faster than H2MN-RW, the current state of the art in GED prediction. Also note that GENN-A∗ is exorbitantly slow (Table 4b). GENN-A∗ is slower since it not only predicts the GED but also the alignment via an A∗ search. While the alignment information is indeed useful, computing this information across all graphs in the database may generate redundant information since an user is typically interested only on a small minority of graphs that are in the answer set. In App. K.2, 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 (Uhlmann, 1991) index structure adapted to asymmetric distance functions. Consequently, for NEUROSED, we only need to embed the query graph and evaluate F to make predictions at query time. Table 5a 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 ≈ 50 times faster than GPU-based H2MN-RW. Note that indexing enables up to 3-times speed-up on NEUROSED over linear scan, which demonstrates the gain from ensuring triangle inequality. These results show the benefits of using an easily computable and parallelisable prediction function F with theoretical guarantees.

heading: 4.4 ABLATION STUDY
text: 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 F . Both have strictly better representational capacity than NEUROSED, so are expected to match the performance with infinite data. 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 F . Overall, these trends indicate that F enables better generalization and scalability with respect to accuracy. Furthermore, given that its
performance is close to an MLP, and it enables indexing, the benefits outweigh the marginal reduction in accuracy. More ablations studies are provided in App. K.1.

heading: 4.5 GENERALIZATION TO UNSEEN QUERY DISTRIBUTIONS
text: We train the model by sampling queries from the graph database through BFS enumerations. How does NEUROSED generalize to unseen distributions? Towards that end, we generate queries from the three unseen distributions of (1) Random Walks (RW), (2) Random Walks with Restarts (RWR), and (3) SHADOW (Zeng et al., 2021). Table 5b presents the results. As visible, the errors remain low. Even more surprisingly, the errors on RW and RWR are better than the train distribution of BFS itself. This indicates good generalization to unseen distributions. See App. O for further details on the sampling strategies.

heading: 5 CONCLUSIONS, LIMITATIONS AND FUTURE WORK
text: Similarity search is a fundamental operator for graph analytics. Edit distance is one of the most popular similarity measures defined over graphs. The applicability of SED and GED, 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.
One limitation of our work (and all neural approaches(Rex et al., 2020; Zhang et al., 2021; Wang et al., 2021; Li et al., 2019; Bai et al., 2019; 2020)) is the ability to predict on large query graph sizes. While the deterioration in prediction quality with larger query sizes is manageable if the same query sizes are seen in the train data, generalizing from small query sizes to large query sizes remain an unsolved problem (See App. M). The ability to generalize to unseen larger query sizes is important since computing GED and SED are NP-complete. Hence, generating training data on large query graphs is computationally intractable. To further advance the field of neural graph distance learning, this generalization ability .

heading: 6 REPRODUCIBILITY STATEMENT
text: Please find all code, experiments and generated data at the following anonymous link: https:// anonymous.4open.science/r/NeuroSED/.
In Appendix, we have given details that are needed to make our work more reproducible. In particular, we have (1) additional proofs in App. D, (2) descriptions of datasets in App. H, (3) additional definitions in App. B, (4) analyses of computation cost for SED and GED computation in App. F, (5) additional details of the pipeline of our architecture in App. G, (6) additional details of the experimental setup in App. I, and (7) additional experimental results in App. J.

heading: APPENDIX
text: 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 (Li et al., 2019): 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 (Li et al., 2019)). The assumption of euclidean distance prohibits the model from learning an asymmetric distance function. Certainly, the loss function can be changed to incorporate an asymmetric distance measure and the performance of the architecture following this change may be studied. However, the selection of an appropriate loss function that works well with the GMN architecture is 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 (Li et al., 2019)). • GraphSim (Bai et al., 2020): GraphSim computes a square similarity matrix across node pairs of two graphs G1 = (V1, E1), G2 = (V2, E2) on which CNNs are applied to predict the similarity. Since G1 and G2 may be of different sizes, the smaller graph is padded with ||V1| − |V2|| 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 ||V1| − |V2|| 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 (Bai et al., 2019): 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.

heading: B DEFINITIONS
text: Definition 5 (Graph Isomorphism) Graph G1 = (V1, E1,L1) is isomorphic to G2 = (V2, E2,L2) if there exists a bijection π : V1 → V2 such that (i) ∀v ∈ V1 : L(v) = L(π(v)), (ii) ∀e = (v1, v2) ∈ E1 : π(e) = (π(v1), π(v2)) ∈ E2, and (iii) ∀e ∈ E1 : L(e) = L(π(e)).
Subgraph isomorphism is defined analogously by using an injection instead of a bijection.
Definition 6 (Nearest Subgraph) S is a nearest subgraph to G1 in G2 if SED(G1,G2) = GED(G1,S).

heading: C HANDLING EDGE LABELS
text: A straight-forward extension of NEUROSED to handle edge labels is to use GINE (Hu et al., 2019) layers instead of GIN layers. Equation 4 can be modified as follows:
hGv,i = MLP (1 + i) · hGv,i−1 + ∑ u∈NG(v) ReLU(hGu,i−1 + e G v,u)  (9) where eGv,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 G′ with a vertex wv,u for every edge (v, u) and edges from v to wv,u and from wv,u to u. The node representation for wv,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 wv,u for some (v, u) ∈ EG and 0 otherwise. NEUROSED (and NEUROSEDG) can then be trained with such modified graphs as inputs, but using the ground truth SED (respectively GED) for the original graphs in the loss function.

heading: D ADDITIONAL PROOFS

heading: D.1 THE TRIANGLE INEQUALITY OF SED: PROOF OF THEOREM. 1
text: Our proof relies on two lemmas.
Lemma 3 Let d̂ : Σ×Σ→ R+0 be a distance function over Σ, where (i) d̂(`1, `2) = 0 if `1 = , and (ii) d̂(`1, `2) = d(`1, `2) otherwise; the following holds: SED(G1,G2) = ĜED(G1,G2), where ĜED denotes GED with 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) SED(G1,G2) ≥ ĜED(G1,G2) and (ii) ĜED(G1,G2) ≥ SED(G1,G2). (i) Let S = (VS , ES ,LS) ⊆ G2 be the subgraph minimizing SED(G1,S) (Recall Eq. 3). Consider the mapping π from G1 to S corresponding to SED(G1,S) (and hence GED(G1,S) as well). We extend π to define a mapping π̂ from G1 to G2 by mapping of all nodes in set V2 \ VS to dummy nodes in G1; the edge mappings are defined analogously.
Under this construction, SED(G1,S) = GED(G1,G2) = ĜEDπ̂(G1,G2) ≥ ĜED(G1,G2). This follows from the property that under d̂, insertion costs are zero, that is d̂( , `) = 0. Thus, the additional mappings introduced in π̂ do not incur additional costs under d̂.
(ii) Consider S ⊆ G2 and a mapping π from G1 to S such that GEDπ(G1,S) = ĜED(G1,G2). The existence of such a subgraph is guaranteed (See Lemma 5 in Supplementary). From the definition of GED, GEDπ(G1,S) ≥ GED(G1,S). Furthermore, since S ⊆ G2, GED(G1, S) ≥ SED(G1,G2). Combining all these results, we have ĜED(G1,G2) ≥ GED(G1, S) ≥ SED(G1,G2). Hence, the claim is proved.
Lemma 4 d̂, as defined in Lemma 3, satisfies the triangle inequality. PROOF. We need to show d̂(`1, `3) ≤ d̂(`1, `2) + d̂(`2, `3). We divide the proof into four cases: (i) None of `1, `2, `3 is . Hence, d̂(`1, `3) = d(`1, `3) and the triangle inequality is satisfied. (ii) `1 = . The LHS is 0 and hence the triangle inequality is satisfied. (iii) `1 6= and `2 = . LHS≤ 1 and RHS= 1. Hence, satisfied. (iv) Only `3 = . Here, LHS= 1 and RHS≥ 1. These four cases cover all possible situations and hence, the triangle inequality is established.
From Lemma 3, we know SED(G1,G2) = ĜED(G1,G2). Combining Obs. 3 with Lemma 4, ĜED satisfies the triangle inequality. Thus, SED satisfies the triangle inequality.

heading: D.2 PROOF OF LEMMA 5
text: Lemma 5 There exists a subgraph S of G2 and a node map π from G1 to S such that GEDπ(G1,S) = ĜED(G1,G2).
PROOF. Let π′ be a node map from G1 to G2 corresponding to ĜED(G1,G2). Let h1, · · · , hl be the nodes of G2 which are inserted in π′. Construct subgraph S of G2 by removing nodes h1, · · · , hl and their incident edges from G2. Let π be the node map from G1 to S which is obtained by removing h′1, · · · , h′l from the domain and h1, · · · , hl from the co-domain of π. Since insertion costs are 0 in d̂ and π contains only non-insert operations, then GEDπ(G1,S) = ĜED(G1,G2). Hence, the claim is proved.
Corollary 1 There exists a nearest subgraph (Def. 6) S to G1 in G2 such that S ⊆ G1.
PROOF. The node map π in the above proof contains only non-insert operations. So, S in the above proof is a subgraph of G1 ignoring node and edge labels. Since equality holds in Lemma 3, this π gives an optimal edit distance. Thus, S in the above proof is also a nearest subgraph to G1 in G2.

heading: D.3 MORE GENERAL DISTANCE FUNCTIONS
text: 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 Σ for which replacement is no more expensive than deletion, i.e. d(`1, `2) ≤ d(`1, )∀`1, `2 ∈ Σ. 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 generalization of Lemma 4 to such distance functions d. The other proofs mentioned in the paper are directly applicable.
Lemma 6 Let d : Σ × Σ → R+0 be a metric and d(`1, `2) ≤ d(`1, )∀`1, `2 ∈ Σ. As in Lemma 3, let d̂ : Σ × Σ → R+0 be a distance function over Σ, where (i) d̂(`1, `2) = 0 if `1 = , and (ii) d̂(`1, `2) = d(`1, `2) otherwise. Then, d̂ satisfies the triangle inequality.
PROOF. We need to show d̂(`1, `3) ≤ d̂(`1, `2) + d̂(`2, `3). Consider the three cases: (i) `1 = . LHS = 0,RHS = d̂(`2, `3) ≥ 0 by non-negativity of d. Hence, LHS ≤ RHS. (ii) `1 6= and `2 = . LHS = d(`1, `2),RHS = d(`1, ). Hence, LHS ≤ RHS by assumption. (iii) `1 6= and `2 6= . LHS = d(`1, `3),RHS = d(`1, `2) + d(`2, `3). LHS ≤ RHS by triangle inequality for d. These cases cover all possible situations. Hence, triangle inequality is established.

heading: D.4 DATA AUGMENTATION
text: Observation 4 Let S be a nearest subgraph (Def. 6) of G1 in G2. Let S ′ be a subgraph of G2 which is also a supergraph of S. Then S is also a nearest subgraph of G1 in S ′ and SED(G1,S ′) = SED(G1,G2).
PROOF. The set of subgraphs of S ′ is a subset of the set of subgraphs of G2. S achieves the minimum GED(G1,S) among all subgraphs of G2 and so also the minimum GED(G1,S) among all subgraphs of S ′. Thus, SED(G1,S ′) = SED(G1,G2) = GED(G1,S). Observation 4 gives a natural strategy for data augmentation. Once we have SED(G1,G2) and a nearest subgraph S from the expensive non-neural computation of GED(G1,G2), we can use (G1,S ′, SED(G1,G2)) for all S ⊆ S ′ ⊆ G2 as training examples.

heading: D.5 THE TRIANGLE INEQUALITY FOR F
text: This is referred to in the proof for Lemma 1.
Lemma 7 F(ZGQ ,ZGT ) ≤ F(ZGQ ,ZGT ′ ) + F(ZGT ′ ,ZGT ), where F(x,y) = ‖ReLU(x − y)‖ for any monotonic norm ‖.‖.
PROOF. Let x,y ∈ Rn. We observe that (ReLU(x) + ReLU(y))i = ReLU(x)i + ReLU(y)i = ReLU(xi) + ReLU(yi) ≥ ReLU(xi + yi) = (ReLU(x+ y))i. Since ‖.‖ is monotonic, this implies ‖ReLU(x) + ReLU(y)‖ ≥ ‖ReLU(x + y)‖. Using the triangle inequality for ‖.‖, we get ‖ReLU(x)‖+‖ReLU(y)‖ ≥ ‖ReLU(x)+ReLU(y)‖ ≥ ‖ReLU(x + y)‖). Substituting x = ZGQ −ZGT ′ ,y = ZGT ′ −ZGT , we get, ‖ReLU(ZGQ −ZGT ′ )‖+ ‖ReLU(ZGT ′ − ZGT )‖ ≥ ‖ReLU(ZGQ − ZGT )‖ This implies that F(ZGQ ,ZGT ′ ) + F(ZGT ′ ,ZGT ) ≥ F(ZGQ ,ZGT ). Our claim is proved.

heading: E FURTHER CHARACTERIZATION OF F
text: Let E : G → Rd, where G is the space of graphs, be the learned embedding function and F : Rd × Rd → R be the embedding space prediction function. We aim to have the graph space prediction function P : G × G → R, defined by P (G,H) = F (E(G), E(H)), to be able to approximate SED : G × G → R in the best possible way, while preserving the key theoretical properties listed below:
SED(G,H) ≥ 0 (10) SED(G,H) = 0 ⇐⇒ G ⊆ H (11)
SED(G,H) ≤ SED(G,T ) + SED(T,H) (12) We allow E to be arbitrary. Then, P satisfies the analogous properties
P (G,H) ≥ 0 (13) P (G,H) ≤ P (G,T ) + P (T,H) (14)
if and only if F satisfies F(g, h) ≥ 0 (15)
F(g, h) ≤ F(g, t) + F(t, h) (16)
For the analogue to property in Eq. 11, we first define the subgraph prediction function PS : G×G→ {0, 1} as PS(G,H) = [[∀i : E(G)[i] ≤ E(H)[i]]]. PS is motivated by NEUROMATCH (Rex et al., 2020) where a subgraph prediction function of this form satisfies the key properties of subgraph isomorphism: transitivity, anti-symmetry, intersection set and non-trivial intersection. Hence, P must satisfy:
P (G,H) = 0 ⇐⇒ PS(G,H) = 1 (17) Again, E being arbitrary, Eq. 17 holds if and only if, F satisfies:
F(g, h) = 0 ⇐⇒ ∀i : g[i] ≤ h[i] (18) Any F that satisfies Eqs. 15, 16 and 18 is acceptable in our framework. However, it is not trivial to
characterize such functions. To show a complete constructive characterization we add two important properties in our desiderata for F . To motivate these properties, we first discuss about Fg in GED and then SED.

heading: E.1 GED:
text: For GED, we require the following three properties:
Fg(g, h) ≥ 0 (19)
Fg(g, h) = 0 ⇐⇒ ∀i : g[i] = h[i] (20) Fg(g, h) ≤ Fg(g, t) + Fg(t, h) (21)
With these properties in Eqs. 19, 20, and 21; Fg is a metric. However, giving a complete constructive characterization of metrics is not trivial. To achieve this, we establish an important connection of metrics on vector spaces to norms. Every norm ‖.‖ gives a metric (x, y) 7→ ‖x− y‖. Moreover for a metric, there exists a norm ‖.‖ such that the metric can be expressed as (x, y) 7→ ‖x− y‖, if and only if the metric is translation invariant and homogeneous. Thus, we add these properties to the desiderata for Fg:
Fg(g + k, h+ k) = Fg(g, h),∀k ∈ Rd (22)
Fg(rg, rh) = |r|Fg(g, h),∀r ∈ R (23)
Observation 5 The followings give a complete constructive characterization of Fg satisfying Eqs. 19 - 23:
1. Fg is (x, y) 7→ ‖x− y‖ for some norm ‖.‖ over the vector space Rd. 2. For any norm ‖.‖ over the vector space Rd, (x, y) 7→ ‖x− y‖ is a valid Fg .
Hence, the L2 norm is a natural choice because it is isotropic (i.e. direction/rotation invariant).

heading: E.2 SED:
text: For SED, we add translation invariance and non-negative homogeneity to the desiderata, to make a complete constructive characterization feasible:
F(g + k, h+ k) = F(g, h),∀k ∈ Rd (24)
F(rg, rh) = rF(g, h),∀r ∈ R+0 (25) Note that non-negativity of r in Eq. 25 is necessary to be consistent with Eq. 11. If r is negative,
then with r = −1, we will have x ≤ y =⇒ F(x, y) = 0 =⇒ F(−x,−y) = 0 =⇒ −x ≤ −y =⇒ x ≥ y, which is a contradiction for x 6= y. For these two properties, translation invariance and non-negative homogeneity, we provide intuitive interpretations in the context of SED. The translation invariance would imply that if graphs G and H are modified in the same way then the SED(G,H) will be preserved. The positive homogeneity would mean that if the costs are scaled by a positive factor, then the SED is also scaled by the same positive factor.
From Eq. 24, we have F(g, h) = F(g − h, 0) = p(g − h), where p : Rd → R is defined as p(x) = F(x, 0). Then Eqs. 16 and 25 are satisfied if and only if:
p(x+ y) ≤ p(x) + p(y) (26)
p(rx) = rp(x),∀r ∈ R+0 (27) Here, Eq. 26 reflects subadditivity property and Eq. 27 is nonnegative homogeneity. With these
properties, p is an asymmetric seminorm. Additionally, Eq. 18 is satisfied if and only if:
p(x) = 0 ⇐⇒ ∀i : x[i] ≤ 0 (28)
We call this Eq. 28 as rectification property and refer to the seminorms satisfying this property as rectified seminorms.
Our claim is that F satisfies all the desired properties presented earlier, if and only if p is a rectified asymmetric seminorm. Thus, we have the following complete characterization for F .
Observation 6 The followings give a complete characterization for F:
1. F is (g, h) 7→ p(g − h) for some rectified asymmetric seminorm p. 2. For any rectified asymmetric seminorm p, (g, h) 7→ p(g − h) is a valid F . Now, we describe the following characterization for p. Recall that in d-dimensional vector spaces, asymmetric seminorms are in one-to-one correspondence with convex sets containing the origin. Specifically, every asymmetric seminorm p corresponds to a convex set B, containing the origin, called the dual unit ball of p. Furthermore, p and B are related as follows:
p(x) = sup z∈B
z · x (29)
Additionally, p is symmetric if and only if B is symmetric about the origin and p is positive definite (i.e. p(x) = 0 =⇒ x = 0) if and only if B contains the origin in its topological interior. Note that monotonic norms are also asymmetric seminorms.
Lemma 8 (Rectified dual unit ball) Eq. 28 holds if and only if B satisfies the following:
∀z ∈ B : ∀i : z[i] ≥ 0 (30)

heading: In other words, the necessary and sufficient conditions say that B lies completely in the positive
text: orthant.

heading: PROOF.
text: 1. ( =⇒ ) If z[i] < 0 for some i and some z ∈ B, then taking x in the negative orthant, with x[i] having a sufficiently large magnitude, gives positive z · x, which leads to a positive p(x), contradicting the requirement that p(x) = 0 when ∀i : x[i] ≤ 0. 2. ( ⇐= ) If ∀z ∈ B : ∀i : z[i] ≥ 0, then for any x in the negative orthant, z · x ≤ 0,∀z ∈ B. 0 ∈ B, so the upper bound of 0 is achievable, hence p(x) = 0.
Note that, Lemma 8 implies that the origin is at the boundary of B, which negates the positive definiteness of p. Hence, every valid p can be constructed by first choosing a convex set B in the positive orthant of Rd and then defining p(x) using Eq. 29. Conversely, any such construction gives a valid p. However, depending on B, it may not be always be feasible to simplify or solve the optimization problem of Eq. 29. In the special case where B is restricted to polytopes, Eq. 29 is a Linear Program. With recently proposed differentiable Linear Programming layers, B could be learnt in an end-to-end fashion via backpropagation (with non-negativity constraints on the variables to enforce the positive orthant). However, this adds more parameters to learn and hyperparameters to tune, and makes training and inference significantly costlier. Instead we add a different, and arguably milder, restriction on B, to get a closed form for Eq. 29 in terms of norms. Specifically, we assume that B is such that mirroring it on all orthants results in a convex set. Not surprisingly, this closed form coincides with the form of F used in the paper. This establishes that our embedding space prediction function is a natural choice for modelling SED.
First, we show a characterization for the dual unit ball of a monotonic norm. Recall that a norm ‖.‖ on the vector space Rd is said to be monotonic if (∀i : |x′[i]| ≥ |x[i]|) =⇒ (‖x′‖ ≥ ‖x‖). This characterization allows us to construct the dual unit ball of a rectified asymmetric seminorm p from the dual unit ball of a monotonic seminorm ‖.‖, and vice versa, such that p(x) = ‖max(0, x)‖.
Lemma 9 Let ‖.‖ be a norm over Rd. Let B′ be its dual unit ball. ‖.‖ is monotonic if and only if the following holds: ∀x : ∀i : z[i]x[i] ≥ 0, where, z ∈ arg maxz∈B′ z · x.

heading: PROOF.
text: 1. ( =⇒ ) Assume that z[i]x[i] < 0 for some i and x. Wlog, assume x[i] > 0. Then, by assumption, z[i] < 0. Construct x′ by replacing x[i] in x′ with x[i] + ∆, with ∆ > 0. Let z′ ∈ arg maxz′∈B′ z′ · x′. By continuity, for sufficiently small ∆, there is a z′, which is arbitrarily close to z. In particular, for such ∆, z′[i] < 0. This gives z′ · x′ < z′ · x. But monotonicity gives z′ ·x′ ≥ z ·x and maximality of z for x gives z ·x ≥ z′ ·x, which on chaining give z′ ·x′ ≥ z′ ·x. This contradicts the previous inequality. 2. ( ⇐= ) Consider x and x′ with |x[i]| ≤ |x′[i]|,∀i. Let z ∈ arg maxz∈B′ z · x, such that z[i]x[i] ≥ 0,∀i. Then ‖x′‖ ≥ z · x′ ≥ z · x = ‖x‖. Hence, ‖.‖ is monotonic.
Lemma 10 Let ‖.‖ be a monotonic norm. Then x 7→ ‖max(0, x)‖ is a rectified asymmetric seminorm.
PROOF. Let B′ be the dual unit ball of a monotonic norm ‖.‖. Let B be the positive orthant of B′. Clearly B is convex and contains the origin, so let B be the dual unit ball of a rectified asymmetric seminorm p (see Lemma 8). We show that ‖max(0, x)‖ = p(x), which completes the proof.
‖max(0, x)‖ = sup z∈B′ z ·max(0, x)
= sup z∈B
z ·max(0, x)[max(0, x) ≥ 0]
= sup z∈B
z · x
= p(x)
Here, max(0, x) ≥ 0, as by Lemma 9 it suffices to consider z’s in the positive orthant, where B coincides with B′. Additionally, for x[i] < 0 as the supremum is at z[i] = 0; max(0, x) coincides with x at i : x[i] ≥ 0.
Lemma 11 Let p be a rectified asymmetric seminorm with a dual unit ball B such that mirroring B on all orthants results in a convex set. Then p is x 7→ ‖max(0, x)‖ for some monotonic norm ‖.‖.
PROOF. Let B be the dual unit ball of p. Let B′ = {z : |z| ∈ B}. B′ is convex (by mirroring assumption), symmetric about the origin, and contains the origin in its topological interior (except in degenerate cases which we ignore), so B′ is the dual unit ball for a norm ‖.‖. For any x, let z ∈ arg maxz∈B′ z ·x, and consider z′ obtained from z by keeping the magnitudes of z[i]’s but taking the sign of x[i]’s. By construction z′ ∈ B′, and z′ · x ≥ z · x, which gives z′ ∈ arg maxz∈B′ z · x. So by Lemma 9, ‖.‖ is a monotonic norm. Now, B is the positive orthant of B′, so by the reasoning of Lemma 10, p(x) = ‖max(0, x)‖, and it completes the proof. Discussion: Lp norms are natural choices for the monotonic norms ‖.‖. For L1 norm, the dual unit ball is a hypercube with side length 2 units and centered at the origin. For L2 norm, the dual unit ball is a hypersphere of unit radius centered at the origin. The dual unit balls of the corresponding rectified asymmetric seminorms are simply the positive orthants of the hypercube and the hypersphere respectively, which easily satisfy the mirroring assumption. We choose L2 norm because of it’s isotropy, although other Lp norms are also likely to work as well as the L2 norm. In fact, any rectified asymmetric seminorm whose dual unit ball is obtained by taking the positive orthant of a monotonic norm’s dual unit ball will satisfy the mirroring assumption, and will therefore be expressible in the form ‖max(0, x)‖.

heading: F COMPUTATION COST OF SED AND GED INFERENCE
text: 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 xv of dimension |Σ|, followed by non-linearity. This results in O(|V|(|Σ| · d+ d2L)) cost. • GIN: GIN aggregates information from each of the neighbors, which consumes O(d · g) time. The linear transformation consumes an additional O(d2) 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(d2 + dg)) computation time per node. Across, all nodes, the total cost is O(|V|kd2 + |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(|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(kd2 + d2L) time.
Combining all these factors, the total inference complexity for a graph isO(|V|(|Σ| ·d+d2L+kd2)+ |E|kd). This operation is repeated on both the query and target graphs to compute their embeddings, on which distance function F is operated. Thus, the final cost is O(n(|Σ| · d+ d2L+ kd2) +mkd), where n = |VQ|+ |VT | and m = |EQ|+ |ET |.

heading: G PIPELINE DETAILS
text: Additional Model Details: We use residual connections 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 5x speedup in convergence and a marginal improvement in the generalization error with residual connections. We use 8 layers, 64 hidden dimensions and 64 embedding dimensions. We use a single layer for pre-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 (Lerouge et al., 2017), which provides us with the best so far lower bound and upper bound for SED. The time limit is kept at 60 seconds per pair. Each pair is run with 64 threads on a 64 core machine. This gives sufficiently tight bounds (with exact values for a large majority of pairs). For evaluation, we use SED = (LB + UB)/2 as the ground truth, where LB and UB are the lower and upper bounds respectively. Fig. 6 presents a visualization of tightness of SED bounds.
Real queries for AIDS: The queries for AIDS constitute of known functional groups. They have been compiled from Table 1 in ‘‘Mining statistically significant molecular substructures for efficient molecular classification S Ranu, AK Singh - Journal of chemical information and modeling, 2009.”
Loss Function: While ZGQ and ZGT be the embeddings for the query graph GQ and target graph GT respectively, we use the following function (for training):
H(ZGQ ,ZGT , l, u) =  (F(ZGQ ,ZGT )− u)2, F(ZGQ ,ZGT ) > u 0, l ≤ F(ZGQ ,ZGT ) ≤ u (l −F(ZGQ ,ZGT ))2, F(ZGQ ,ZGT ) < l
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.
L = 1 |T| ∑
∀〈GQ,GT ,l,u〉∈T
H(ZGQ ,ZGT , l, u) (31)
Here, T is the set of all training samples.
Training details: NEUROSED, NEUROSED-NN and NEUROSED-Dual were trained using the AdamW optimizer with a weight decay of 10−3. A batch-size of 200 graph pairs per mini-batch was used. The learning rate schedule was cyclic. In each cycle, learning rate was increased from 0 to 10−3 for 2000 iterations and then decreased back to 0 for 2000 iterations. Training was stopped when the best validation loss did not improve for 5 cycles. We observe that 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 regularization due to the high learning rates seen in each cycle encouraging the optimizer to find flatter regions of minima, giving better generalization. It is also robust to 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 nearest subgraph is found. We rank these neighbourhoods and that allows us to consider regions of the target graph in order of relevance. This generates much smaller candidate sets and traditional expensive methods can be used to refine these candidate sets further.
In this section, we seek to give further insight into the efficacy of neighborhood decomposition and design guidelines for choosing the right value of k depending on the expected query distribution. In practice, we are concerned only with connected subgraphs. Assuming that all the nearest subgraphs (Def. 6) are connected leads to the following result:
Theorem 3 Assuming that the nearest subgraph to the query is a connected graph, a nearest subgraph S to G1 in G2 can be found in an l/2-hop neighborhood Nv, centered at some v ∈ VG2 , where l is the length of the longest path in G1.
PROOF. By Corollary 1, there exists a nearest subgraph S of G1 in G2 which is also a subgraph of G1 ignoring node and edge labels. So, the diameter of S is ≤ the length l of the longest path in G1. Since S ⊆ G2, S is contained in some l/2 neighborhood of G2. 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 nearest subgraph having a diameter equal to l is rare. In practice, the diameter of the nearest 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.

heading: H DATASETS
text: 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.
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 (Leskovec & Sosič, 2016).
PubMed: PubMed dataset is a citation network which consists of scientific publications from PubMed database pertaining to diabetes classified into one of three classes.
Protein: Protein dataset consists of protein graphs. Each node 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 (Bojchevski & Günnemann, 2017).
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 (Bojchevski & Günnemann, 2017).
AIDS’: AIDS’ dataset is another collection of graphs constructed from the AIDS antiviral screen database. The graphs and their properties differ from those in AIDS. These graphs also represent chemical compound structures.
Linux: Linux dataset is 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 (Bai et al., 2019).

heading: I EXPERIMENTAL SETUP
text: 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 (Bai et al., 2019): We train the model with LB+UB2 as the ground truth value of SED (LB and UB are lower and upper bounds for SED respectively). Now let G1 be the query graph, and G2 be the target graph, we use nSED(G1,G2) = SED(G1,G2)|G1| instead of nGED(G1,G2) = GED(G1,G2) (|G1|+|G2|)/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 (Rex et al., 2020): We use the un-anchored version of NEUROMATCH trained on its original task (subgraph isomorphism decision problem) using its own training framework. For ranking, we use the violation scores it produces directly rather than thresholding the violation and predicting subgraph isomorphism as intended. We change the size limits for sampling query/target graphs in training to better fit our data distribution.
Querying for SED: We embed the neighbourhoods of the nodes in the given graph (or set of graphs) and store the embeddings (denoted by set ZGT ) accordingly. For a new query GQ, we first obtain its embedding ZGQ . Based on the stored embeddings ZGT , we compute SED(ZGQ ,ZGT ) for all ZGT ∈ ZGT using the function F(ZGQ ,ZGT ). We sort the targets based on the obtained SED values and it can trivially answer top-k or range queries. From the selected targets one can extract the nearest subgraph by running a traditional algorithm to compute SED and use the returned node mapping to interpret it. An alternative is to choose a larger (k′, where k′ > k) top set and use traditional methods to further filter these. Note that usually the graphs required in the top-k or range queries are much smaller than the total number of targets, so using our model to filter out the unimportant targets from the target candidate set can save significant amount of resources.
Software details: We used Pytorch and Pytorch-Geometric for implementation. All experiments were done using Jupyter Notebooks. The full code, notebooks for all experiments and the generated data are available on an anonymous github repository 3.
License: The provided code and data are licensed under CC-BY-SA.

heading: J ADDITIONAL RESULTS

heading: J.1 OTHER MEASURES FOR PREDICTING SED AND GED
text: 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 R2. Tables 7a and 7b show the MAE scores for SED and GED respectively. Tables 8a and 8b present the results based on R2 results. Consistent with the previous results, NEUROSED outperforms all techniques both in SED and GED in these two measures except
3https://anonymous.4open.science/r/NeuroSED/
BRANCH is competitive only on IMDB for GED prediction and H2MN-NE is better in Linux only for GED prediction.
K PRECISION@k ON k-NN QUERIES
Fig. 7 shows Precision@k on k-NN queries. As visible, either NEUROSED comfortably performs better than all baselines or is among the best performing algorithms.

heading: K.1 ADDITIONAL RESULTS ON ABLATION STUDY
text: 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 10, GIN consistently achieves the best accuracy. This is not surprising since GIN is provably the most expressive among GNNs in distinguishing graph structures (essential to SED or GED computation) and is as powerful as the Weisfeiler-Lehman Graph Isomorphism test (Xu et al., 2018b).
Impact 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 11 that sum-pool is the best choice among the considered alternatives.

heading: K.2 ALIGNMENT
text: 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 1 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.

heading: L HEAT MAPS FOR PREDICTION ERROR
text: In Figures 8 to 17, we show the variation of the errors on SED and GED prediction with query sizes and ground truth values for NEUROSED (NEUROSEDG for GED) and the baselines on all the corresponding datasets. This experiment is an extension of the heat-map results in Fig. 2 in the main paper. These datasets show variations in the distributions of SED and GED values. It is interesting to observe that among the baselines, different methods perform well on different regions (e.g., combinations of high/low SED and high/low query sizes). In the figures, darker means higher error. The baselines do not show good performance on all regions. However, for NEUROSED and NEUROSEDG , 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.

heading: M SCALABILITY WITH QUERY SIZE AND GENERALIZABILITY TO UNSEEN LARGER QUERY SIZES
text: In this analysis, we aim to analyze the following aspects:
1. Performance on larger query sizes. 2. Generalizability to unseen larger query sizes
In Table 13 sheds light on the above objectives. We notice that although there is some deterioration in the quality for query sizes in the range [25, 50] when compared to the entire set, it is not severe (NEUROSED-50 in Table 13). However, if we the train set only contains queries till size 25 and we deploy the learned model to infer on queries of larger unseen sizes, the drop in quality is significant (NEUROSED-25 in Table 13). Nonetheless, NEUROSED remains superior to the optimal non-neural approach (MIP-F2) when run with a generous time limit of 60 seconds per query. Overall, this experiment highlights one direction that needs further study and improvement.
N VISUALIZATION AND APPLICATION OF SED Searching for molecular fragment containment is a routine task in drug discovery (Ranu et al., 2011). Motivated by this, we show the top-5 matches to an SED query on the AIDS dataset produced by NEUROSED in Fig. 18. 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.

heading: O ALTERNATIVE QUERY DISTRIBUTIONS
text: In RWR, we perform fixed length random walks, where the length of a walk is the average diameter size of the queries generated through BFS during training. Next, we merge the walks to form a graph.
In RW, we perform random walks, till the diameter of the resultant graph is the same as the average diameter of the BFS sampled train graphs.
The details of the SHADOW sampler is explained in Zeng et al. (2021).

Review summaries:
The paper addresses the problem of graph/subgraph similarity search in terms of the edit distance, termed GED/SED, respectively. Unfortunately, both GED and SED are NP hard, with exponential search space, making the cost prohibitive on even moderately large graphs/queries. Instead, the authors apply a neural network based approach, by designing a siamese graph neural network called NEUROSED. In particular, NEUROSED is able to preserve theoretical properties of  SED/GED, such as triangle inequality, through a purposely designed prediction function. Experiments are conducted on real graph datasets for both SED and GED, which evaluates the effectiveness and efficiency of GED/SED.

This paper presents a simple and effective model for subgraph similarity search. Two GNNs with shared weights are applied first to get the graph embeddings of the query and target graphs. Then, instead of using an MLP over the concatenated graph embeddings to regress the subgraph edit distance (SED) score, the paper proposes to use the l2 norm of the positive portion of the difference between two embeddings. This inductive bias is proved to preserve SED's triangle inequality property, and shows better accuracy and generalization power for large graphs. Experiments show the proposed model outperforms state-of-the-art neural approaches in both graph similarity search and subgraph similarity search tasks.

The paper proposes a supervised model, NeuroSED, to compute Subgraph Edit Distance (SED) (and Graph Edit Distance (GED)). To this end, given two graphs, target and query graphs, NeuroSED uses a shared GNN to encourage embeddings for both graphs representing similar topological features. Then a dedicated learning metric w.r.t. SED is introduced to ensure the learned embeddings hold key properties of SED and the embeddings are indexable. The indexable embeddings further support fast prediction. Extensive experiments show NeuroSED significantly improves SOTA methods.