Towards Accurate Subgraph Similarity Computation via Neural Graph Pruning
Authors: Linfeng Liu
XU HAN
Dawei Zhou
Liping Liu
Venue: Accepted by TMLR ()

Abstract: Subgraph similarity search, one of the core problems in graph search, concerns whether a target graph approximately contains a query graph. The problem is recently touched by neural methods. However, current neural methods do not consider pruning the target graph, though pruning is critically important in traditional calculations of subgraph similarities. One obstacle to applying pruning in neural methods is the discrete property of pruning. In this work, we convert graph pruning to a problem of node relabeling and then relax it to a differentiable problem. Based on this idea, we further design a novel neural network to approximate a type of subgraph distance: the subgraph edit distance (SED). In particular, we construct the pruning component using a neural structure, and the entire model can be optimized end-to-end. In the design of the model, we propose an attention mechanism to leverage the information about the query graph and guide the pruning of the target graph. Moreover, we develop a multi-head pruning strategy such that the model can better explore multiple ways of pruning the target graph. The proposed model establishes new state-ofthe-art results across seven benchmark datasets. Extensive analysis of the model indicates that the proposed model can reasonably prune the target graph for SED computation.

Published in Transactions on Machine Learning Research (10/2022)
Towards Accurate Subgraph Similarity Computation via Neural Graph Pruning
Linfeng Liu
linfenglu@@eeta.comm com
Meta, Boston
Xu Han
Xu. Xu.Han&taft edu
Department of Computer Science Tufts University
Dawei Zhou
zhoud@rt edu
Department Computer Science Virginia Tech
Li-Ping Liu Department of Computer Science Tufts University
liping. liue Stufts..dd
Reviewed OpenReview: https: https:://pperreviau openreview. net/ forum? id= CfzIsWWBLo
Abstract
Subgraph similarity search, one of the core problems in graph search, concerns whether target graph approximately contains query graph. The problem is recently touched by neural methods. However, current neural methods do not consider pruming the target graph, though pruning is critically important in traditional calculations of subgraph similarities. One obstacle to applying pruning in noural methods is the discrete proporty of pruning. In this work, we convert graph pruning to a problem of node relabeling and then relax it to a differentiable problem. Based on this idea, we further design novel neural network to approximate type of subgraph distance: the subgraph edit distance (SED). In particular, construct the pruning component using neural structure, and the entire model can be optimized end-to-end. In the design of the model, we propose an attention mechanism to leverage the information about the query graph and guide the pruning of the target graph. Moreover, we develop a multi-head pruning strategy such that the model can better explore multiple ways pruning the target graph. The proposed model establishes new state-of- the-art results across seven benchmark datasets. Extensive analysis of the model indicates that the proposed model can reasonably prune the target graph for SED computation. The implemenlation of our algorithm is released at. our Github repo: httpss//giithb. tufts-nl/Prune4SeD
1 Introduction
Graphs are important tools for describing structured and relational data (Wu et al.) 2020b from small molecules and large social networks. Among fundamental operations in graph analysis, the calculation of subgraph similarity is one important problem (aan et al. 2005). Subgraph similarity search concerns whether
target graph approxinately contains query graph (Samanvi & Sivadasan 2015 Shang et al. 2010 Peng
et al. 2014 Zhu et al.) 2012 Yuan et al. 2012). Subgraph similarity search has a wide range of applications, which span over various fields, including drug discovery (Ranu et al.) 2011). computer vision (Petrakis &
Faloutsos 1997,, social networks (Samanvi & Sivadasan 2015), and software engineering (Wu el al.) 2020a)
"ork done while Tufts University.

---

Published in Transactions on Machine Learning Research (10/2022)
There are multiple ways of defining the similarity or distance between a query graph and target graph. This work focuses on Subgraph Edit, Distance (SED) [Riesen 2015 which is a type of psendo-distance from the query graph to the target graph (Bunke] 1997 Bougleux et al. 2017 Zeng et al. 2009 Fankhauser et al, 2011 Daller et al., 2018; Ricsen & Bunke 2009). Concretely speaking, SED is the minimum number of edits that transform the query graph to a subgraph of the largel graph. Such edits include insertion of nodes or odges, deletion of nodes or odges, and substitution of nodes or edge labels. When SED is zero, then the query graph is isomorphic to a subgraph of the target graph.
Exact computation of SED is NP-hard, which is from the fact that SED is a generalization of an NP- complete problem: the subgraph isomorphism problem. The core problem of SED calculation is to identify the subgraph in the target graph that best matches the query graph. In this type of problem, pruning plays an important role. Traditional algorithms often use a pruning procedure to remove from the target graph those nodes that are unlikely to match any nodes in the query graph. An effective pruning procedure can greatly reduce the space of the following searching procodure and thus improve both the speed and accuracy of similarity calculation. Improving the effectiveness of pruning algorithms is not an easy problem and is still a hot topic in the research of traditional algorithms (Lee et al. 2010b).
In this work, we consider neural methods for graph pruming, The main difficulty here is that graph pruming usually consists of discrete operations and is not differentiable. We overcome the difficulty by converting graph pruning to a node relabeling problem and then relaxing it to a continuous problem. This novel formulation enables the possibility of fitting a pruning model with neural networks.
We further design new learning model, Neural Graph Pruning for SED (Prune4SEDD), to learn SEDs of graph pairs. The model first uses query-aware learning component to compute node representations for the larget graph such that these representations also contain information about the query graph. Then the model considers multiple prumings of the target graph using multi-head structure. Finally the model compute the SED between the query and the pruned target graph. The entire model can be trained end-to-end.
The empirical study shows that Prune4SED establishes new state-of-the-arl results across seven benchmark datasets. In particular, Prune4SED achieves an average of 23% improvement per dataset over the previous neural model. We also demonstrate promising results for application of molecular fragment containment search in drug discovery: our model can accurately retrieve molecules containing given functional groups. Finally, extensive analysis of our model confirms that it can effectively prune significant fraction of nodes that cannot match the query graph.
2 Related Work
Based on edit distance Bougleux et al. 2017 Zeng et al. 2009 Fankhauser et al. 2011 Riesen 2015
Daller al.] 2018 Rieson & Bunke 2009), SED an expressive form to quantify subgraph similarity. Exact computation of SED is often infeasible because it is NP-hard. Pruning is an effective strategy in the detection of query graphs from target graphs
[Lee et al. 2010b).
2020b apply deep learning models to learn from graph-structured data. GNNs have been lested powerful to embed a graph structures into vector representations. (Hamilton
Graph Neural Networks (GNNs) (Wu ct al.
et al.
2017: Veličković et al. 2017 Xu et al.
2018 Liu et al. 2020 Chen et al. 2020). Though standard
message-passing GNNs (Chen et al. 2020) has limitations in identifying subgraphs, various remedies (Sato 2020) help to overcome these problems.
Recent advancements in GNNs open the possibility of neural combinatorial optimization Cappart et al. 2021p. For example, GNNs have been used to count isomorphic subgraphs (Liu et al. 2020), graph matching
Liu et al.) 2021]. 1, and subgraph matching (Lou et al. 2020). Recently GNNs are applied to compute edit
distance (Li et al. 2019 Bai et al. 2019 2020 Zhang et al. 2021). The most relevant work is NeuroSED Ranjan et al. 2021), which learns to predict SED via GNNs. While the method shows promising results for SED calculations, it faces difficulties when the target graph is much larger than the query: it becomes
Here "distance" loose term and but not "metric that has strict definition in math.
2

---

Published in Transactions on Machine Learning Research (10/2022)
Gq
Gr
Step
Step 2
Step
Figure 1: An example computing SED between a query graph Gg and a target graph G.. The first step is find an optimal subgraph in G.. The last. two steps are substituting node label and deleting an edge in Gg. ending up SED 2.
harder for the model to identify the subgraph that is most similar to the query. This issue motivates us explicitly consider pruning in a neural model.
For applications such graph matching where the input is a graph pair, it is beneficial to use cross-graph information in GNNs.. The main idea is to allow information flow during GNN's propagation (Li et al. 2019;
Ling et al.] 2020 2021 Wang et al. 2019). For example, after a GNN propagation, node representation in one graph will be further updated by using node representation from the other graph (Li et al., 2019
3 Preliminaries
A graph = (V, E.) consists of node set V and an edge set E. X(i) represents the label of node i Vi let x; = (NEHOT(X(i) be the one-hot encoding of i's node label; and let X = (xx)ev denote the node label matrix, whose rows are one-hot encodings of node labels. Let Σ be the universe of all node labels. We do not consider graphs with edge labels for now but will discuss extensions to include such cases.
Subgraph Edit Distance (SED). Given a query graph G3 (Vg: Egg X.)) and target graph G2 (V,, E, X2), SED represents the minimum cost of edits on Gg such that the edited query is isomorphic to subgraph in Gt. An edit. operation can be inserting node modifying node or edge label (Zeng et al. 2009). Alternatively, the computation of SED seeks to identify subgraph G, in the target graph Gj such that G, and Gg have the minimum graph edit distance (GED), which is the minimum number of edits that convert Gg to be isomorphic G²
edge, deleting node or edge,
SED(G,, min GED(G,, Gy)- G.SG.
(1)
Here we only consider connected graphs G, and Gg. Figure illustrates an example of SED computation. In a geneal version of SED, each lype of edit operation has cost, which is application-deeenderr consider the basic version and set 1 as cost for all types of edits (e.g. (Zheng et al. 2013 Bai et al. 2019)
Here we
Graph Neural Networks (GNNs). GNNs learn node representations by itcratively updating node representations and sending messages to neighbors.
h UPDATE (h, AGGREGATE ((h, : (1.5) E E))).
(2)
Here UPDATE denotes an update function and AGGREGATE denotes an aggregation function. For exam- ple, AGGREGATE sums up all input vectors, and UPDATE is a dense layer that applies to the concatenation of its two arguments. h, denotes the current representation of i, and h' denotes updated representation. GNNs capture node features and topological features of graph simultancously (Wu et al.) (020b). GNN variants different. UPDATE and AGGREGATE functions. This work uses GATv2Conv (Brody et. al. 2021), but other GNN alternatives such as Papp et al. (2021); Zhang & Li 2021 also be considered. The choice of GNN architectures is model selection problem and we leave such exploration to the future.
A pooling ion often applied to aggregate all node vectors into a single graph vector.
POOL ((h;iee VJ)
(3)
3

---

Published in Transactions on Machine Learning Research (10/2022)
The POOL function is invariant to the order of elements in its input and has several implementations. For example, the POOT function can be an average function followed by dense layer (Hamilton et al. 2017).
NeuroSED. NeuroSED (Ranjan et al. 2021 is a neural network designed to mimic the calculation of SEDs from graph pairs. It uses Graph Isomorphism Network (GIN) (Xu et al., 2018) to encode both G, and G3 into vectors and then predicts SED using a simple fixed function. Formally, NeuroSED writes as:
H. GIN(G.), H₃ GIN(G
(4)
SED = |ReLUU (POOL(HH)) (H,)
(5)
Here ||-1l2 is the bn norm.
4 Neural Graph Pruning for SED Calculation
4.1 Graph Pruning as a Node Relabeling Problem
Graph pruning aims to remove nodes in the target graph without affecting the SED between the target graph and the query graph. Suppose graph pruning keeps a node subset V2 C V22 of the target graph and get the induced subgraph G²² (V/, XVV)). The purpose of pruning is to maintain that
SED(GL, GG) SED(G,, Gg)
(6)
while maximizing the number [V]] - IV/| of pruned nodes. Graph pruning is discrete operation, and the solution Vy exists in a large searching space.
Here we formulate graph pruning as a node relabeling problem, which is more convenient for learning models. We use a new node label ó & 2 to indicate that a node is pruned. Specifically, we relabel the target graph by X²" such that
X(() - { Xi(1) Φ otherwise
iiEV
(7)
We further assign a large cost (e.g. the size of G.) the edit operation that switches an actual label with d. Since the cost exceeds the edit distance from Gg any subgraph of G2, the new graph G²² (Ve, E,, X," with relabeling is equivalent to the pruned graph G' in terms of SED calculation:
SED(G,, = SED(G",
(8)
Gq
GE
This is because the latter calculation will not match any node outside of Vi to a node in Gys otherwise, node outside of
Figure 2: Graph pruning in SED as node relabeling problem. Gray nodes, which take the special label o, are treated as pruned.
V/ will incur a large edit distance due to its new label ø. A target graph with relabeling is shown in Figure 2
To incorporate graph pruning in a neural network, we further formulate node relabeling to a contimuous prob lem. In a neural network, the label of a node is usually expressed by a one-hot vector x; = ONEHOT(X(()), then we relabel each node i by
(9)
Here a; is binary. If a; = 0, which indicates the pruning of node i, then x² is zero vector, which is different from any one-hot representation of original labels in E. The vector a = (a, : i Vi)) is a binary vector indicating which nodes are kept.
Then we relax the indicator voctor to be continuous, a E [0, V.l We call the continuous vector as keep probability: nodes with small probabilities are considered to be "pruned" from the graph. Now a neural network compute from G, and G2 a learnable pruning component for neural SED calculation.
4

---

Published in Transactions on Machine Learning Research (10/2022)
Query-aware representation learning
QAL Block
Stage
Stage 2
Stage L
Gq
EMB
GAT
GAT
Hc
QAL block
QAL block
QAL block
Sigmoid
Ge
EMB
GAT
GAT
Fully-Connected Layer
Layer Normalization
Hard pruning
Soft pruning
Prediction
Multi-Head Attention
Ge
81
1
[K
tv
He
Xt
GNN
Linear
Linear
G
9M
Top k
hop
G
Gg
11c
H4
Figure The overall framework of Prune4SED, including query-aware representation learning, hard/soft pruning, and multi-head SED prediction. The query-aware learning (QAL) block is implemented by multi-head attention layer.
In the neural model, there is no need to specify the editing cost between a zero vector and a one-hot vector because the model can automatically decide it when fitting the training data. If a reflexes accurate pruning, then a flexible learning model would avoid using nodes with zero vectors to predict accurate SED values.
4.2 Graph Pruning for SED Calculation
With the formulation above, we design an end-to-end neural model for computing SED. An overview of the model depicted in Figure 3 (left). Specifically, Prune4SED has three components, i.e., (1) query-aware representation learning, (2) h pruning, and (3) multi-head SED predicting. The first component learns node representation for G, conditioned Gg. The second component learns to keep probability and also does the pruning. The third component predicts the final SED value.
Query-aware representation learning. The representation learning component takes the target G3 and the query G2 and outputs node representations of G,. We design neural architecture as the component to effectively use the information about Gg when calculating node representations for Gt-
The core part of the component is the query-aware learning (QAL) block, which allows the information of Gg to flow into node representations of G.. Figure 3 (right) shows the structure of QAL. The inputs to the block are node representations H, of G, and node representations H, G.. These representations are either from node features or learned by GNNs, which we will elaborate on later. Then the QAL block updates H, to new representations H, using attention mechanism (Vawwani et al. 2017).
H. QAL (H..H,).
(10)
The function of the QAL is specified as below:
H, diag(s) H., sigmoid (MLP(R)), R MHA (Q QQ H, V -H,)
(11)
Here MHA is multi-head attention layer VVawanni et al. 2017 described in A.1 An intuitive understanding here is that representations of the target graph queries information from the query graph. Then we compute a weight vector s E [o, l| that measures node importance in G, Then we scale H, according to s, yielding the updated node representation H. for G,,
Now we are ready to compose the entire representation learning component with QAL blocks and GNN layers. We first embedding layer (the function EMB(-)) to encode node labels of both G2 and G, into
5

---

Published in Transactions on Machine Learning Research (10/2022)
vector representations H. and H. Then alternately apply QAL blocks and GNN layers to compute G2 and G representations Hi and Hy
H = QAL H = QAL
H. H H H
H. = EMB (X:), H = (MMBXX,)
(12)
H. = GNN H Ed):
H = GNN (H Egg:
1= 1..,...,
(13)
Here GNN is a l-layer graph attention convolution [Brody et al. 2021 (see A.2 GAT layers are shared by Gg and G..
The embedding layer and
We compute the final node representations H, for G. using node representations after each QAL block.
H MLP (CONCAT (II....,)))
(14)
Here CONCAT concatenates node representations of G, at all stages to capture multi-granular views at various granularity levels. The MLP then encodes the concatenated node representations, further distilling essential information for pruning.
The query-aware learning component learns node representations of G2 in the context of Gy- Each QAL block checks whether node in G, can be matched to nodes in Gg by considering their respective surrounding structures. Since GAT layers encode structural information at different levels of granularity, QAL blocks consider neighborhoods also at different levels. Therefore, it is beneficial to concatenate representations learned from all QAL blocks to capture information at different levels.
Hard/soft pruning. Then we compute the keep probability a for G, using H,.
We calculate a from G,'s node representations after each QAL block.
H.P |pl
a Sigmoid
(15)
Here a is computed by scalar projection along rows H, on a learnable vector p, then is scaled to (0, 1)
by the sigmoid function. The projection is inspired by previous works in graph pooling (Gao & 2019 Cangea et al. 2018 Knyazev et al. 2019).
Next we use to prune G.. Before apply the type of pruning we discussed in equation g we first apply hard pruning to remove some nodes from Gr. We first keep set S of k nodes corresponding to the largest value in a. We also keep all h hop neighbors of each node in S to increase connectivity and balance computation and information loss. Then we get a set V/ of nodes as the result of hard pruning from a. Thus, we define hard pruning as follows:
S top k(a))
(16)
V h hop(hspp))))
(17)
Here top (op_k(a) selects top l nodes corresponding to the i largest values in o; and h hop(S, G,) extracts h hop neighbors surrounding nodes in S.
The hard pruning is useful when Ge has a much larger diameter than Gg. In this case, it removes a decent fraction of nodes in G,, which beneficial both accuracy and speed. Later we show the effectiveness of hard pruning in real examples in Figure 5 Hard pruning shares the same principle as Graph U-Net (Gao & Ji 2019), which shows that the discrete operation does not pose issues to loss minimization.
Then we apply a to these nodes in Vi to do soft pruning as introduced in Section 4.1
x((1) = ox), IEV!
(18)
The pruned graph is G. = E, Here E keeps all G.'s edges that are incident with nodes in V/" We put the entire pruming procedure into single function G², = PRUNE(H, Gt), which computes a from H, and then executes hard and soft pruning on G2 to get G Note that soft pruning is differentiable and

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm Prume4SED
Input: Gg. G2
Query-aware representation learning
for /= = 1 to L do
EMB (X:), EMB (X₂): GAT (H!-1, F GAT (H Fug, O.W.
=
3: H H
4: H. = QAL(H, )
> QAL block from equation
10
5: end for
H, MLP (CONCAT (H) ...,. H.)))
M do 8: G = PRUNEM (H,, G+)
for
Multi-head pruning
Om PRED GG)
10: end for
11: D = MEAN (f...... .MM)
12: Return 9
helps to learn the keep probability The model learns to small keep probabilities to indicate that their corresponding nodes cannot be matched to nodes in the query graph. Hard pruning is not differentiable, but it is still meaningful to remove nodes with small keep probabilities.
Multi-head prediction of SEDs. Once we have the pruned graph Gū, we use a neural module to "predict" the SED between G₁ and Gg. For example, we can use the NeuralSED network as the predictive module.
However, given the combinatorial nature of graph pruning, there might be many locally optimal solutions of a, and it is hard for the model to identify good values in one-shot. Inspired by multi-head attention, we propose multi-head predicting module.
We use M separate pruning functions, PRUNEE)).,,PRUEEss) each of which optimizes its own parameter Pm in equation 15 to obtain M different pruned graphs G.,...... G. Then we use the same predictive module PRED to compute SED values from these pruned graphs.
G²
PRUNEm (H,, G.), im = PRED Gg), m = 1...., M.
(19)
Then we take the average to get the final prediction.
MEAN (01 .......,MM.
(20)
Here we use NeuroSED in equation the PRED function.
With multi-head pruning model is able to explore multiple ways of pruning G, and thus has chances to capture good ones. At the same time, we only compute multiple prunings from different projections of the same set of node representations, so we only slightly increase the number of parameters.
4.3 Optimization
Prune4SED is summarized Algorithm I First, query-aware representation learning encodes target graph G. (Line 1-5). Then multi-head pruning is used to prune G, from multiple views to predict SED (Line 6-9). Each head contains sequence of operations, including computation, hard/soft pruning, and SED prediction. Finally, predictions from multi-head pruning are combined as the final prediction (Line 10).
For model training, model predictions are compared against SED values computed by a MIP-F2 solver (Lerouge et al. 2017). Given pair of graphs (G,, G,), the model makes a prediction ÿ. For the same pair the solver returns lower bound yr and an upper bound yo of the true solution. In most cases yr = VU. which means that the solver find the true solution. For the same pair. To handle the general case, we penalize
7

---

Published in Transactions on Machine Learning Research (10/2022)
the prediction with squared error when it is outside of [VL. We minimize the following training loss computed from a dataset 'D to train the model.
min
L Σ
CUL - -0-0--++++- + (10 - y0l+)²
(21)
(Gg GA)DD
Here [+ truncate negative values to zero. The loss is equivalent to squared loss when Vr = yt-
Next we analyze time complexity of Prune4SED. We first consider graph sizes. The attention layer in the QAL block needs consider every node in G, against every node in Gg. so its running time is O (Vg). GAT layers runs in linear time about O + [E)), Processing node vectors need time O([Va] [V,)), the overall running time is O( + Egg + [Vil [V()).
The running time is in linear time with network hyperparameters, including the width of the network, the number of layers, the number of attention heads, or the number of pruning heads.
5 Experiments
In this section, we aim to validate the effectiveness of Prunc4SED through experiments and also examine the model to understand how it works. We have the following sub-aims: 1) benchmarking the performance of Prunc4SED against existing SED solvers/predicts
models; 2) understanding the uscfulness of our model designs through ablation studies; 3) examining pruned graphs to check whether neural graph pruning aligns with SED calculation; and 4) applying the model to a world applications.
stages for Prunc4SED. In hard pruning, we take top k (k= = 5) important nodes and their h (4= L 1 = 4) hop neighbors. The SED predictor contains an 8-layer GIN with 64 hidden units at every layer. We use M = 5 heads to produce the final prediction. More details about model hyperparameters and platforms are given in B.2
Experiment scttings. By default, we use L
Datasets. We use seven datasets (AIDS, CiteSeer, Cora ML, Amazon, DBLP, PubMed, and Protein) to evaluate our model for SED approximation.
B.1 provides more descriptions about these datasets.
We extract query-target pairs from each dataset to train, validato, and test models. For datasets with a single network (CiteSeer, Cora_ ML, Amazon, DBLP, and PubMed), the target graph G. is ego-net (up to 5-hop) of random node sampled from large network. For datasets with multiple graphs (AIDS and Protein), the target graph is graph in the dataset. Except the AIDS datset, the query graph is subgraph from a random target graph (sampled from all target graphs). The subgraph is randomly sampled by starting from the center node of the target Ge, progressively selecting unseen neighbors with a probability 0.5 of the current nodes, and stopping at depth up to 5. Query graphs of the AIDS dataset are known functional groups from Ranu & Singh
Table 1: Dataset Statistics.
Dataset
[Vg
[V]
[
AIDS
9
14
38
CiteSocr
12
73
6
Cora ML
11
98
7
Amazon
12
43
1
DBLP
14
240
8
PubMed
12
60
3
Protein
9
38
3
(2009). To compute the SED between Gg and G., we use mixed- progger-rogrammmin solver, MIP-F2 (Lerouge et al. (201)). The solver runs on a 64 core machine with maximum of 60 seconds to compute lower and upper bounds the true SED. From each dataset, we randomly pair target and query graphs to get. 100K pairs for training, 10K for validation, and another 10K for testing. Table shows average sizes (rounded to 1) of target and query graphs and the number of node labels in the data extracted from each dataset.
We compare PruDe4SED with five other approaches. The first three are neural models: HºMN [Zhang et al. 2021), SIMGNN [Bai et al. 2019), and NeuroSED (Ranjan et al. 2021). For HºMN and SIMGNN, we use their modified versions from Ranjan et al. (2021) that better suit. SED prediction. For H'MN, we include its two versions random walks (H'MN- RW) and the k-hop version (H'MN-NE). The second comparison contains two non-neural methods MIP-F2 LLe et al. 2010a) and BRANCH (Blumenthal 2019), both of which are implemented by an efficient C++ library GEDLIB (Blumenthal
Baselines.
2019 2020).
As competing methods, both are given 0.1 second to compute the upper bound yu and lower bounds yı. of
8

---

Published in Transactions on Machine Learning Research (10/2022)
Table 2: RMSE on seven datasets.
ATDS
CiteSeer
Cora ML
Amazon
Dblp
PubMed
Protein
Branch
1.379
3.161
3.102
4.513
2.917
2.613
2.391
MIP-F2
1.537
4.474
3.871
5.595
3.427
3.399
2.249
H'MN-RW
0.749
1.502
1.446
1.294
1.47
1.213
0.941
HºMN-NE
0.637
1.827
1.229
0.971
1.552
1.326
0.755
SIMGNN
0.696
1.781
1.289
2.81
1.482
1.322
1.223
NeuroSED
0.512
0.519
0.635
0.495
0.964
0.728
0.524
PruDe1SED
0.480
0.365
0.437
0.322
0.859
0.447
0.485
Improv, over best lasoline
6.3%
29.7%
31.2%
34.9%
10.9%
38.6%
7.4%
PruneISED w/o. QAL
0.496
0.439
0.575
0.359
0.953
0.585
0.505
Prune4SED w. head
0.497
0.383
0.458
0.324
0.915
0.495
Prune4SED w. heads
0.482
0.373
0.449
0.321
0.817
0.488
0.488
the true SED, then 9 = (yu + #2)/2 is used as the prediction. Note that 0.1 second is already much longer than our model's predicting time.
The predictive performance of these models evaluated by root-mean-square error (RMSE), which is the square root of the mean squared crror defined in equation 21
5.1
Benchmark Predictive Performances
Table summarizes performances of different models. The results of baselines are taken from Ranjan et al. 2021b. h. The results show that neural methods outperform non-ncural methods (Branch and MIP-F2). This is consistent with findings in previous work. H2MN and SIMGNN are designed for Graph Edit Distance. They compare the entire target graph to the query to compute the target value. This calculation is not appropriate for SED because many nodes in the target graph are irrelevant to the true SED.
Prune4SED outperforms all baselines and establishes new state-of-the-art performances across all seven datasets in terms of RMSF, as shown in Table 2 Specifically, Prune4SED substantially improves the best neural solver, NeuroSED, with an average 23% improvement. Our analysis later shows that our model gains an advantage by removing some irrelevant nodes from the target graph before predicting SED values.
We further study the performance of our model with graph sizes. By controlling the random sampling procedure, get graph pairs with different sizes and form three sets (small, medium, and large) of graph pairs. Each set has 2000 query-target pairs. We separately extract such sets from Cora_ML, and Citeseer datasets. In the three sets (small/mediiee haall//mdiimllargge
0.9
CiteSeer Prune4SED
Corn Prune4SED
0.8
CiteSeer-NeuroSED Cora-NeuroSED
0.7
the target graphs extracted from CiteSeer have average sizes 16/62/122, and those extracted from Cora have average sizes 17/64/ (141 The average sizes of queries about 12 across all sets extracted from the two datasets. Each set are split into training (80%) validation (10%), and testing (10%). We run our model on each set to get an RMSE, then we can plot RMSEs from three sets against their sizes. We also run NeuroSED as a baseline here for comparison.
0.6
0.5
0.4 small
medium
large
Figure RMSE versus node number
Figure shows the results. We see that both models have worse performances on larger graphs, which indicates that SED prob- lems on larger graphs are more challenging for neural models. Nevertheless, the RMSE of our model is less than 1, which is still fairly accurate, considering that query graphs often have dozens of edges. Our model is still significantly better than NeuroSED.
Table 3: Inference time (seconds).
Dataset MIP-F2
Cora ML
CiteSeer
1.0 10-1
1.0 x 10
NeuroSED Prune4SED
1.5 x 10-4
1.5 x 10-4
1.9 10-3
1.7 x 10-3
We also test the predicting time of all models and report the comparison in Table The optimization-based approach for
9

---

Published in Transactions on Machine Learning Research (10/2022)
SED calculation can take very long time to get the true answer. Here give time limit of 0.1 second to MIP-F2, and the time is already much longer than the prediction time of neural methods, but its performance is worse than neural methods as we have shown above. Prune4SED is slower than NeuroSED because it uses more neural layers. But considering the performance improvement, our model still has advantages in many applications. Furthermore, the compulation time not. relevant lo graph sizes and thus can be sped up by improving network architectures. We leave such work to the future.
5.2 Examine pruned graphs
To understand the good performance of the proposed model, we examine how the model prines target graphs. We visualize a few examples of hard and soft pruning over the graph in Figure 5 Here node colors represent node labels. Nodes removed by hard pruning are not shown in the figure, and node sizes are proportional to keep probabilitics.
G4
Gt
hard
soft
Gq
G
hard
soft
Gq
Gt
hard
soft
AIDS
CiteSeer
Protein
Figure 5: Visualization of pruned graphs on AIDS, CiteSeer, and Proteins datasets. Every four graphs is a group, representing query graph Gy, target graph Gt, target graph after hard pruning and after soft pruning. Node colors represent node labels. In soft pruning, nodes are resized according to their keep probabilities. Nodes with red circles mark the optimal subgraph.
These examples show that the pruning component removes a significant amount unrelated nodes in the target graph. Hard and soft prunings obtained from a are reasonable for matching the query. In the first example, removes the long-chain, which obviously cannot match the query graph. We also observe that the pruning of the same (arget graph is different for different query graphs. In the AIDS example, nodes the top part of the target graph are pruned differently; In the CiteSeer example, the nodes the right side are pruned differently. It is strong indication that the model does consider the query graph when it prunes the target graph.
We further check the effect of graph pruning over SED calculations. Ideally graph pruming should not affect SED calculation, that is, SEDs computed from pruned graphs should still be the same as SEDs computod from original target graphs. We truncate keep probabilities with threshold and then prune all nodes with probabilities below the threshold, then
exact. SED solver to check how much this hard way of
10

---

Published in Transactions on Machine Learning Research (10/2022)
AIDS with pruning ratio 0.1
AIDS with pruning ratio 0.3
AIDS with pruning ratio 0.5
Ground auth SED
20
Ground auth SED
20
8
Ground auth
10
0.
0
10
20
10
20
10
20
SED after praning
SED after proning
SED aEDa praning
Figure 6: Correlation between SEDs computed from pruned graphs and SEDs computed from the original graphs. The size of dots indicates the number of SED pairs occurring at that location.
Table 4: Pearson correlation coefficient p and mean absolute error (MAE) computed between ground truth SED and SED computed from pruned graph using exact solver. The pruning ratio indicates the average node ratio impacted by hard pruning and soft pruning per graph. Larger results are better for p and smaller results are better for MAE.
0.1
T=
0.3
0.5
Dataset
p1
MAE
p
MAE 1
p
MAE 1
AIDS
0.999
0.026
0.998
0.036
0.983
0.144
CiteSeer
1.000
0.022
1.000
0.026
1.000
0.032
Protein
0.996
0.092
0.995
0.110
0.980
0.237
pruning affects the SED. If the SED does not change much, then it means that node probabilities do indicate good pruning of the target graph.
We conduct this experiment with 500 randomly selected graphs from the AIDS, CiteSeer, and Protein datasets. We adjust the threshold to prune r = 0.1, 0.3, and 0.5 of all graph nodes. Then we compare the calculated SEDs against. SEDs computed from the original graphs (ground truth). The solver cannot get the truc SED for a small number cases, then we use (yu + y2)/2 as the true SED. We use MAE to measure the difference and also compute the correlation coefficient between the two groups of SEDs.
Table summarizes the results of MAE and correlation coefficient. We see that the difference is fairly small when the ratio is small. When the pruming ratio is low (0.1 and 0.3), SEDs computed from pruned graphs only have slight differences with SEDs computed from the original graph. The average difference is less than 0.04 on the first two datasets and only 0.11 on the third dataset; the Pearson correlation coefficient is above 0.99. When the pruming ratio is as aggressive as 0.5, the difference still at an acceptable level. Figure
0 further visualizes the correlation between SEDs computed from original graphs and pruned graphs respectively. The size of dots the figure indicate the number of graph pairs occurring at that location the plot. We again see that pruning does not affect SED computation on most graphs. These results confirm that our pruning weights correctly recognize and retain important nodes in G2-
5.3 Ablation Studies
We conduct two ablation studies to investigate the effectiveness of the QAL block and multi-head pruning, and we report results in the bottom three rows 2
Query-aware representation learning. Recall that query-aware learning aims to leverage query graph to learn representations for the target graph so that neural graph pruning is adaptive to the query graph.
To this end, we compare Prunc4SED with and without query-aware learning. In the setup of Prunc4SED without query-aware learning, we remove all QAL blocks in representation learning (i.c., H. Hi in equa- tion 12 and equation 13 Therefore, representation learning solely depends the target graph.
11

---

Published in Transactions on Machine Learning Research (10/2022)
G4
C₁
Head
Head
Head
Head 4
Head
Figure 7: Multiple heads have learned different pruning strategies. By average, the final prediction obtained from multiple heads is close to ground truth (4.1 v.s. 4).
4SD
0/0.4
1/0.4
0/0.5
0/0.5
0/0.5
Query
SED/NeuroSED
0/0.6
1/0.6
1/0.6
1/0.6
1/0.7
Figure Retricving chemical compounds given query graph, which is a functional group. The retrieved compounds are ranked according to their prodicted SED, Two values under each compound are ground truth SED and predicted SED.
We see that removing QAL blocks consistently increases RMSE values across seven datasets. The results verify the effectiveness of query-aware learning in terms of extracting information from query graphs.
Multi-head pruning. We use M = M = (default), and M 10 heads to Prune4SED and compare their performances. Prune4SED with multiple heads (M = 5 and MM = 10) clearly improves the performance compared with Prunc4SED with a single predictive head, confirming the contribution of multiple heads. The results also suggest that
is a reasonable choice in practice.
Figure 7 further show an example where five predictive heads prune the target G, in different ways. Multiple predictive heads allow the model to discover more structures that are similar to the query graph and smooth out some predictive errors. The final prediction (averaged over 5 heads) is close to the ground truth (ground truth SED is 4, and the predicted SED is 4.1).
5.4 Application: Molecular Fragment Containment Search
Molecular fragment containment searching is a fundamental problem in drug discovery (Ramu et al.) 2011 Ranjan et al. 2021). The problem can be formulated as standard problem of subgraph similarity scarch: given query graph representing some functional group, the task is to retrieve from database chemical compounds that contain the functional group.
12

---

Published in Transactions on Machine Learning Research (10/2022)
We apply Prunc4SED to solve this task. We evaluate AIDS dataset, where target graphs are antivirus screen chemical compounds collected from NCI and query graphs are known functional groups. The dataset does not include Hydrogen atomns.
Figure visualizes one set of retrieval results. The five molecules with the smallest predicted SEDs are shown in the Figure. Four out of these five molecules actually contain the function group. Prune4SED has better retrieval results than NeuroSED, More examples can be found in Figure 12 of B.4
We also observe that Prune4SED can find molecules that contain the query but is much larger than the query. We hypothesize that our model is able to prune unnecessary nodes and identify the subgraph corresponding to the query, while NeuroSED either tries to find target graphs that are similar to the query graph or bet its luck on very large molecules. It is another evidence that pruning is necessary for SED calculation.
6 Conclusion
In this work, we study the problem of using a learning model to predict the SED between a target graph and a query graph. We present Prunc4SED, an end-to-end model to address the problem. Notably, Prunc4SED learns to prune the target graph to reduce interference from irrelevant nodes. It converts graph pruming to a node relabeling problem and enables pruning in a differentiable neural model. Our new model Prune4SED combines two novel techniques, query-aware representation learning and multi-head pruning to improve the model's ability of learning good prunings. Extensive experiments validate the superiority of Prunc4SED.
Acknowledgments
We thank all reviewers and editors for their insightful comments. Linfeng Liu and Li-Ping Liu were supported by NSF 1908617. Xu Han was supported by Tufts RA support. Part of the computation resource is provided by Amazon AWS.
References
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network ap- proach to fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. 384-392, 2019.
Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. bearning-basod efficient graph similar- ity computation via multi-scale convolutional set matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3219-3226, 2020.
David B Blumenthal. New techniques for graph edit distance computation. arXiv preprint or arx:x:1908 00260. 2019.
David B Blumenthal, Sébastien Bougleux, Johann Gamper, and Luc Brun. Gedlib: a c++ library for graph edit distance computation. In International Workshop Graph- Bascd Representations in Pattern Recognilion, pp. 14 24. Springer, 2019.
David B Blumenthal, Nicolas Boria, Johann Gamper, Sébastien Bougleux, and Luc Brun. Comparing heuristics for graph edit distance computation. The VLDB Journal, 29(1):419 458, 2020.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised induc- tive learning via ranking. Xixiv preprint vxXi:11777.0855 2017.
Sebastien Bougleux, Luc Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Gaüzère, and Mario Vento. Graph odit distance quadratic assignment problem. Pattern Recognition Letters, 87:38-46, 2017.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? arXio preprint wwXiv:2105.14491, 2021.
hhttps:/wskki... mih. htt.a//www..a........////....aaa
13

---

Published in Transactions on Machine Learning Research (10/2022)
Horst Bunke. On relation between graph edit distance and maximum common subgraph. Pattern Recog- nilion Letters, (8(8):689-66)) 1997.
Cätälina Cangea, Petar Veličković, Nikola Jovanovié, Thomas Kipf, and Pietro Liò. Towards sparse hierar- chical graph classifiers. arXiv preprint arXin:1811.01285 2018.
Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Velićković. Combinatorial optimization and reasoning with graph neural networks. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 4348 4355. International Joint Conferences Artificial Intelligence Organization, 2021.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures Advances in neural information processing systems, 33:10383 10395, 2020.
Evariste Daller, Sébastien Bougleux, Benoit, Gaüzère, and Luc Brun. Approximate graph edit distance by several local scarches in parallel. In 7th International Conference on Pattern Recognition Applications and Methods, 2018.
Paul D Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4))7711788) 2003.
Stefan Fankhauser, Kaspar Riesen, and Horst Bunke. Speeding up graph edit distance computation through fast bipartite matching. In International Workshop on Graph-Base Based Representations in Pattern Recogni- tion, pp. 101-111. Springer, 2011.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometrie. arXiv preprint 1iv: 02428, 2019.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference on machine learning, pp. 2083- 2092. PMLR, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Boris Knyazev, Graham W Taylor, and Mohamed R Amer. Understanding attention and generalization in graph neural networks. arXiv preprinl arXiv:1905 1905.005000 2019.
Jungmin Lee, Minsu Cho, and Kyoung Mu Lee. A graph matching algorithm using data-driven markov chain monte carlo sampling. In 2010 20th International Conference on Pattern Recognition, pp. 2816- 2819. IEEE, 2010a.
Victor E Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. A survey of algorithms for dense subgraph discovery. In Managing and mining graph data pp. 303-336. Springer, 2010b.
Julien Lerouge, Zeina Abu-Aisheh, Romain Raveaux, Picrre Héroux, and Sébastion Adam. New binary lincar programming formulation to compute the graph edit distance. Pallern Recognition, 72:254 265, 2017.
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-20, 2016.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. arXiv preprint arXie:1904.12777, 2019.
Xiang Ling, Lingfei Wu, Saizhuo Wang, Tengfei Ma, Fangli Xu, Alex X Liu, Chunming Wu, and Shouling Ji. Multi-level graph matching networks for deep graph similarity learning. arXiv preprint orXiv:2007. 04335, 2020.
Xiang Ling, Lingfei Wu, Saizhuo Wang, Gaoning Pan, Tengfei Ma, Fangli Xu, Alex Liu, Chunming Wu. and Shouling Ji. Deep graph matching and searching for semantic code retrieval. ACM Transactinn on Knowledge Discovery from Data (TKDD), 15(5):1 21, 2021.
14

---

Published in Transactions on Machine Learning Research (10/2022)
Linfeng Liu, Michael C Hughes, Soha. Hassoun, and Liping Liu. Stochastic iterative graph matching. In International Conference on Machine Learning, pp. 6815 6825. PMTR, 2021.
Xin Liu, Haojie Pan, Mutian He, Yangqiu Song, Xin Jiang, and Lifeng Shang, Neural subgraph isomorphism counting. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery 8 Data Mining, pp. 1959-1969, 2020.
lyya Loshchilov and Frank Hutter. Decoupled weight decay regularization. aiv preprint arXi::1711.05101, 2017.
Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovee, et al. Neural subgraph matching. arXiv preprint arXiv:2007.03022 2020.
Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the exprossiveness of graph neural networks. Advances in Neural Information Processing Systems. 34, 2021.
Yun Peng, Zhe Fan, Byron Choi, Jianliang Xu, and Sourav Bhowmick. Authenticated subgraph similarity searchin outsourced graph databases. IEEE transactions on knowledge and dato engineering, 27(7):1838 1860, 2014.
Euripides G. M. Petrakis and A Faloutsos. Similarity searching in medical image databases. IEEE transac- lions on knowledge and dala engineering, 9(3):435 447, 1997.
Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabharwal, and Sayan Ranu. A neural framework for learning subgraph and graph similarity measures. arXiv preprint arXiv:2122 12. 13143, 2021.
Sayan Ranu and Ambuj K Singh. Mining statistically significant molecular substructures for efficient molec- ular classification. Journal of chemical information and modeling, (0(11):2537-5500 2009.
Sayan Ranu, Bradley T Calhoun, Ambuj K Singh, and Joshua Swamidass. Probabilistic substructure mining from small-molecule screens. Molecular Informatics, 30(9):809 8100-81,.4 2011.
Kaspar Riesen. Structural pattern recognition with graph edit distance. In Advances in computer vision and pattern recognition. Springer, 2015.
Kaspar Riesen and Horst Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision computing, 27(7):950 959, 2009.
Kanigalpula Samanvi and Naveen Sivadasan. Subgraph similarity search in large graphs. arXiv preprint arXiv:1512.05256 2015.
Ryoma Sato. A survey on the expressive power of graph neural net worksrs. ar preprint wxXi:2003.04078 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collec- tive classification in network data. AI magazine, (93)9933, 2008.
Haichuan Shang, Xuemin Lin, Ying Zhang, Jeffrey Xu Yu, and Wei Wang. Connected substructure similarity search. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD, pp. 903 914. Association for Computing Machinery, 2010.
Leslie N Smith. Cyclical learning rates for training neural networks. Tn 2017 IEEE winter conference on applications of computer vision (WACV), pp. 464 472. IEEE, 2017.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Arnetminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 990- 998, 2008
15

---

Published in Transactions on Machine Learning Research (10/2022)
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Iilia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998 6008, 2017.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1110.10003 2017.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 2019.
Jintao Wu, Xing Guo, Guijun Yang, Shuhui Wu, and Jianguo Wu. Substructure similarity search for engineering service-based systems. Journal of Systems and Software, 165, 2020a.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020b.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks?
arXiv preprint 181: 00826, 2018.
Xifeng Yan, Philip S. Yu, and Jiawei Han. Substructure similarity search in graph databases. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, SIGMOD, pp. 766 777. Association for Computing Machinery, 2005.
Ye Yuan, Guoren Wang, Lei Chen, and Haixun Wang. Efficient subgraph similarity search on large proba- bilistic graph databases. orXiv preprint arXiv:1205. 6692, 2012.
Zhiping Zeng, Anthony KH Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou. Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endoument, 2(1):25-36, 2009.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34:15734-15747, 2021.
Zhen Zhang, Jiajun Bu, Martin Ester, Zhao Li, Chengwei Yao, Zhi Yu, and Can Wang. H2mm: Graph similarity learning with hierarchical hypergraph matching networks. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 2274-2284, 2021.
Weiguo Zheng, Lei Zou, Xiang Lian, Dong Wang, and Dongyan Zhao. Graph similarity search with edit distance constraint in large graph databases. In Proceedings of the 22nd ACM international conference on Information Knowledge Management, pp. 1595 1600, 2013.
Yuanyuan Zhu, Lu Qin, Jeffrey Xu Yu, and Hong Cheng. Finding top-k similar graphs in graph databases. In Proceedings of the 15th International Conference on Extending Database Technology, pp. 456-467, 2012.
16


Reviews:
[{"review_id": "aKhBt97Sok", "reviewer": "Reviewer_aL42", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. the paper studies an interesting question with clear motivation\n2. the proposed method is novel\n3. the proposed method is empirically strong compared to prior baselines\n4. the submission carries out detailed ablation studies and qualitative studies to understand the proposed method\n\nWeakness: \n1. Minor concern: all the benchmarks used to evaluate this work is created automatically. Does such automatic transformation reflects the problems we see in real-world applications? Can the authors comment on this?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission studies the important question of subgraph similarity matching. The submission proposes to convert the subgraph matching problem to a graph pruning problem, which is instantiated as a node labeling problem (labeling nodes as keep or pruned). Such problem formulation enables end-to-end differentiable learning, which motivates the usage of neural methods. The submission also designs special architecture for this application. Namely, the authors propose a query-aware graph encoding network and proposes to use multi-head prediction for the node relabeling problem. \n\nThis work evaluates on seven datasets to study the problem of subgraph similarity search. The datasets are created by automatically converting existing graph benchmarks. The proposed method is compared to seven prior baselines and demonstrated superior performance on all seven benchmarks. \n\nOverall, I think this submission studies an interesting problem in practice, proposes a novel perspective that converts the similarity search into a pruning problem, and proposes an empirically strong method to solve this. I enjoyed reading the submission and would recommend acceptance. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Some comments on writing:\n1. Page 16, under section A.2 equation number is missing", "broader_impact_concerns": "I do not have ethical concerns with the submission", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KmrlbshFem", "reviewer": "Reviewer_qdtj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n--\n- Overall, in my view, the paper is interesting. The problem of discovering one or more subgraphs that are as similar as possible to a query graph is essential for many applications and this paper is one of the first steps towards this direction (in the field of graph representation learning).\n\n- The proposed model seems to be novel. To be precise, the different components of the model are not entirely novel since they have been introduced/employed in previous works, however, in my opinion, combining those components to deal with the subgraph search task is not so trivial.\n\n- The proposed model establishes a new state-of-the-art in the subgraph search task. On some datasets, Prune4SED provides significant improvements, while the experiments reported in Table 3 indicate that the pruning component indeed removes from the target graph mainly nodes that are not of any interest.\n\nWeaknesses\n--\n- The main contribution of the paper (and its main selling point) is that it provides a differentiable pruning component. However, the authors apply hard pruning to remove most of the nodes (they keep $k=5$ nodes and their neighborhoods). First of all, it is not clear to me how the proposed model is end-to-end trainable since the hard pruning is not differentiable in my understanding.\n\n- The authors also fail to give proper explanations on why both hard and soft pruning are applied and what is the exact purpose of soft pruning.\n\n- To update the representations of the nodes of both target and query graphs, the authors employ the GATv2 model. GAT is less expressive that 1-WL in terms of distinguishing non-isomorphic graphs (I guess the same is true for GATv2). This is a major limitation of the proposed model since it will fail to retrieve subgraphs of good quality in case of symmetries. I know that in most real-word graphs, this is not the case, however, it would strengthen the approach if more expressive node representations were learned.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The main contribution of the paper is a model that learns to extract (from a target graph) a subgraph that is similar to a query graph. The considered problem generalizes the subgraph isomorphism problem and is thus hard. The proposed (heuristic) approach uses a neural network to prune nodes that are potentially not of interest, and then another component of the model predicts the subgraph edit distance. The proposed model is evaluated on several benchmark datasets where it outperforms the baselines.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- The authors should discuss in more details why hard pruning is necessary and how exactly training is performed (since hard pruning is not differentiable in my understanding). Furthermore, in case hard pruning is performed, what does soft pruning further offer? I would expect the model to perform either hard or soft pruning, but not both. The authors should provide clear explanations on that.\n\n- Since the neighborhood aggregation approach (GATv2) is one of the main components of Prune4SED, and Prune4SED's performance depends a lot on it, I would like to see some more experiments where some more expressive neighborhood aggregation approach is employed.\n\n- The problem becomes more challenging when the size (number of nodes) of both the target graph and the query graph increases. The average size of the graphs in the different datasets is not very large in most cases. I suggest the authors also experiment with some larger graphs (both query and target) such that it becomes clear what is the impact of graph size on the model's performance.\n\n- The authors should also report the running time of the model (both training and inference time) since this is the main advantage of the proposed model compared to existing solvers. I suggest they also compare the running time of the proposed Prune4SED model against those of the baselines.\n\n- Algorithm 1 has some issues. For instance, in line 7, it is not clear from the previous lines what does exactly $\\mathbf{H}_t$ represent. In addition, I think that in line 11, $y$ should be replaced with $\\hat{y}$.\n\n- There are some typos that the authors should fix. For example:\\\np.3: \"PRELIMINARIES\" -> \"Preliminaries\"\\\np.7: \"each of which optimize\" -> \"each of which optimizes\"\\\np.7: \"Then they get\" -> \"Then we get\"\\\np.7: \"in equation equation\" -> \"in equation\"\\\np.8: \"datset, The\" -> \"dataset, the\"", "broader_impact_concerns": "A Broader Impact Statement  is not required.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bZP2Cp62GE", "reviewer": "Reviewer_LCjD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n\n1. The paper is well-written and easy to follow.\n2. Starting from a traditional problem, namely a non-differentiable labeling problem, and relaxing to a differentiable neural network, I think is a good direction for problem analysis.\n\n\n\nWeaknesses:\n\n1. The related studies are not quite sufficient. Some related studies are not cited and well-discussed, such as the subgraph isomorphism counting approaches [1,2].\n\n2. The proposed neural network model is straightforward and simple.\n\n3. It seems that the employed datasets are not large, and only a few query and target graphs are utilized, which may give rise to unconvincing results. Besides, the division of datasets is not clear. \n\n4. The analysis for the experiments is not sufficient. Only the observations are given, but the insights that why the model can outperform the baselines (or other observations) are not well-illustrated. It is the same case for the other experimental results, such as the ablation study.\n\n\n[1] neural subgraph isomorphism counting. KDD 2020\n[2] Can graph neural networks count substructures? NeurIPS 2020\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the problem of subgraph similarity computation via neural graph pruning. Subgraph similarity computation is a hot topic in the field of graph analysis, and has many applications in real-world scenarios. To address this problem, the authors start from converting graph pruning to a problem of node relabeling, then relax it to a differentiable problem. Therefore, the authors then propose a neural network for SED based on this point. Experiments on several benchmarks demonstrate the effectiveness of this proposed model.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please see the weaknesses in Strengths And Weaknesses.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel and interesting approach to compute approximate Subgraph Edit Distance using Graph neural networks.  The simultaneous smooth and hard pruning is interesting and works well in practice despite the loss of differentiability. The reviewers found the paper interesting and all believe it will be helpful to the community. But they also had several concerns about the paper.

Most of those concerns have been addressed in the discussion with reviewers and in the current version.  For these reasons the paper should be accepted but there remain several small but important points that must be integrated to the paper so we will require minor revisions.

Below are the expected revisions:
+ The discussion with the reviewers about inference time is interesting and state that it is provided in section 5.1 which is false. The authors need to add a an inference time table that compare the methods from a computational time perspective. This is necessary to show the interest of the method independently of performance.  
+ The question about the quality of the method as a function of the size of the graphs is important. the authors did a new experiments on a smaller number of larger graphs that suggests that the method still works better than the state of the art competitor which should be integrated in the paper with a discussion. Also it might be interesting to see the effect of the size of the graphs (both query and target) on the performance for instance by plotting on a dataset a scatterplot of the performance VS size to see if there is indeed a loss in performance. In any case all this should be integrated in the paper instead of just in the comments.
+ The authors add the relative improvement of the method in parenthesis after their performance. This is a non standard way to show this and might be confused with variances that are traditionally given similarly. The authors should have a separate line in the tables clearly named to report the improvement of the method.

Decision: Accept (poster)