Detecting Small Query Graphs in A Large Graph via Neural Subgraph Search
Authors: Yunsheng Bai
Derek Qiang Xu
Yizhou Sun
Wei Wang
Venue: Submitted to ICLR 2023 (2023)
Keywords: subgraph matching
subgraph isomorphism search

Abstract: Recent advances have shown the success of using reinforcement learning and search to solve NP-hard graph-related tasks, such as Traveling Salesman Optimization, Graph Edit Distance computation, etc. However, it remains unclear how one can efficiently and accurately detect the occurrences of a small query graph in a large target graph, which is a core operation in graph database search, biomedical analysis, social group finding, etc. This task is called Subgraph Matching which essentially performs subgraph isomorphism check between a query graph and a large target graph. One promising approach to this classical problem is the “learning-to-search” paradigm, where a reinforcement learning (RL) agent is designed with a learned policy to guide a search algorithm to quickly find the solution without any solved instances for supervision. However, for the specific task of Subgraph Matching, though the query graph is usually small given by the user as input, the target graph is often orders-of-magnitude larger. It poses challenges to the neural network design and can lead to solution and reward sparsity. In this paper, we propose NSUBS with two innovations to tackle the challenges: (1) A novel encoder-decoder neural network architecture to dynamically compute the matching information between the query and the target graphs at each search state; (2) A novel look-ahead loss function for training the policy network. Experiments on six large real-world target graphs show that NSUBS can significantly improve the subgraph matching performance.

Under review as a conference paper at ICLR 2023
DETECTING SMALL QUERY GRAPHS IN A LARGE GRAPH VIA NEURAL SUBGRAPH SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Recent advances have shown the success of using reinforcement learning and search to solve NP-hard graph-related tasks, such as Traveling Salesman Optimiza- tion, Graph Edit Distance computation, etc. However, it remains unclear how one can efficiently and accurately detect the occurrences of a small query graph in a large target graph, which a core operation in graph database search, biomed- ical analysis, social group finding, etc. This task is called Subgraph Matching which essentially performs subgraph isomorphism check between a query graph and large target graph. One promising approach to this classical problem is the "learning-to- teng-tt--serrc" paradigm, where a reinforcement learning (RL) agent is de- signed with a learned policy guide search algorithm to quickly find the solution without any solved instances for supervision. However, for the specific task of Subgraph Matching. though the query graph is usually small given by the user as input, the target graph is often orders-of-magntuue larger. It poses challenges to the neural network design and can lead solution and reward sparsity. In this paper, we propose NSUBS with two innovations to tackle the challenges: (1) A novel encoder-decoder neural network architecture to dynamically compute the matching information between the query and the target graphs at each search state; (2) novel look-ahead loss function for training the policy network. Experiments six large real-world target graphs show that NSUBS can significantly improve the subgraph matching performance.
INTRODUCTION
With the growing amount of graph data that naturally arises in many domains, solving graph-related tasks via machine learning has gained increasing attention. Many NP hard tasks, e.g. Traveling Salesman Optimization (Xing & Tu, 2020). Graph Edit Distance computation (Wang al., 2021), Maximum Common Subgraph detection (Bai et al., 2021), have recently been tackled via learning- based methods. These works on the one hand rely on search to enumerate the large solution space, and on the other hand use reinforcement learning (RL) to learn good search policy from training data, thus obviating the need for hand-crafted heuristics adopted by traditional solvers. Such learning-to- search paradigm (Bai al., 2021) also allows the training the RI. agent without any solved instances for supervision. However, how to design a neural network architecture under the RL.-guided search framework remains unclear for the task of Subgraph Matching, which requires the detection of all occurrences of a small query graph in an orders-of -maggi-d-- larger target graph. Subgraph Matching has wide applications in graph database search (Lee et al., 2012), knowledge graph query (Kim et al., 2015), biomedical analysis (Zhang et al.. 2009), social group finding (Ma et al., 2018), quantum circuit design (Jiang et al., 2021), etc. As a conerete example, Subgraph Matching used for protein complex search in protein-protein interaction network to test whether the interactions within protein complex
species are also present in other species (Bonnici et al., 2013).
Due to its NP-hard nature, the state-of-the-art Subgraph Matching algorithms rely on backtracking search with various techniques proposed to reduce the large search space (Sun & Luo, 2020; Kim et al., 2021; Wang et al., 2022). However, these techniques are mostly driven by heuristics, and as a result, we observe that such solvers often fail to find any solution on large target graphs under reasonable time limit, although they tend to work well small graph pairs. We denote this phenomenon as solution sparsity. Such solution sparsity requires the designed model to not only have enough capacity but also to run efficiently under limited computational budget. Another consequence

---

Under review as a conference paper at ICLR 2023
of solution sparsity is that, there can be little-to-no reward signals for the RL agent under an RL training framework (Silver et al., 2017), which we denote as reward sparsity.
In this paper, propose NSUBS with two means to address the aforementioned challenges. First, propose a novel graph encoder-decoder neural network to dynamically match the query graph with the target graph and perform aggregation operation only the query graph reduce information loss. The novel encoder decouples the intra-graph message passing module (the "propagation" module) that yields ieleeinneeennent node embeddings, and the inter-graph message passing module (the "matching" module) that refines the node embeddings via subgraph-to-grapp intra-ge giira-grpphhe embeddings can be computed only once at the beginning of search for efficient inference. We further advance the inter-graph graph message passing by propagating only between nodes that either are already matched or can be matched in future by running a local candidate search space computation algorithm at each search state. Such algorithm leverages the key requirement of Subgraph Matching that every node and edge in the query graph must be matched to the target graph, and therefore reduces the amount of candidates from all the nodes in the target graph to much smaller amount. Compared with a Graph Matching Network (Li et al., 2019) which computes all the pairwise node-to-node message passing between two input graphs, our matching module is able to focus only the node pairs that can contribute to the solution, and thus is both more effective and more efficient. In addition, node-node
matching. Thus, the
we propose the use of sampling of subgraphs to obtain ground-truth subgraph-to-gran mappings to alleviate the reward sparsity issue during training. We design novel look-ahead loss function where the positive node-node pairs are augmented with positive node-node pairs in future states to boost the amount of training signals at each search state.
Experiments on synthetic and real graph datasets demonstrate that NSUBS outperforms baseline solvers in terms of effectiveness by a large margin. Our contributions can be summarized as follows:
We address the challenging yet important task of Subgraph Matching with a vast amount of practical applications and propose NSUBS as the solution.
One key novelty is a proposed encoder layer consisting of a propagation module and a matching module that dynamically passes the information between the input graphs.
We conduct extensive experiments on real-world graphs to demonstrate the effectiveness of the proposed approach compared against series of strong baselines in Subgraph Matching.
2 PRELIMINARIES
2.1 PROBLEM DEFINITION
We denote a query graph as g = (Vy, Fig) and a target graph as FG) where V and E denote the node and edge sets. q and G are associated with node labeling function L, which maps every node into a label in a label set Σ. Subgraph: For a subset of nodes of Vg, q[S] denotes the subgraph of q with node set S and a edge set consisting of all the edges in Eg that have both endpoints in S. In this paper, we adopt the definition of non-induces subgraph. Subgraph isomorphism: q is subgraph isomorphic to G if there exists injective node-to-node mapping
M: Vg VG such that (1) Vu E Vg. [u) ) = I.g (M (u)); and (2) Ve E F.g. ((M E EG. Subgraph Matching: The task of Subgraph Matching aims find the subgraphs in G that
isomorphic to q. We call M a solution, or a match of q to G. We call a pair (g, G) is solved if the
algorithm can find any match under a given time limit, which we find a challenge for existing solvers on input graphs in experiments especially on large graphs. For solved pairs, the number of found subgraphs by an algorithm reported.
2.2 RELATED WORK
Non-learning methods on Subgraph Matching Existing methods on Subgraph Matching can be broadly categorized into backtracking search algorithms (Shang et al., 2008; He & Singh, 2008; Han et al., 2013; 2019; Kim et al., 2021; Wang et al., 2022) and multi-way join approaches (Lai et al., 2015; 2016; 2019; Kankanamge et al., 2017). The former category of approaches employ a branch and bound approach to grow the solution from an empty subgraph by gradually seeking one matching node pair at a time following a strategic order until the entire search space is explored. The multi-way join approaches rely on decomposing the query graph into nodes and edges and performing join
2

---

Under review as a conference paper at ICLR 2023
operations repeatedly to combine the partially matched subgraphs q. However, they tend to work well on small query graphs generally with less than 10 nodes (Sun & Luo, 2020), and thus we follow and compare against methods in the former category, whose details will be shown in Section 2.3.
Learning- methods for subgraph-related problems The idea of designing graph neural networks for graph-graph similarity has been explored, but not Subgraph Matching. GMN (Ling et al., 2020) captures general notions of graph similarity through inter-graph message passing, but outputs similarity score instead of the discrete matching between 2 graphs. DMPNN (Liu & Song, 2022) uses node to edge conversions to obtain node and edge representations that better preserve isomorphism properties, but outputs approximate subgraph isomorphism counts instead of a discrete matching.
Representation learning methods for Subgraph Matching use a geometric loss to provide soft node- node correspondance scores, stops short of providing a discrete mapping of where the query occurs in the target graph. For example, NMATCH (Lou et al., 2020) learns node embeddings to predict score for an input subgraph-grape pair indicating whether the subgraph is contained in another graph. ISONET (Roy al., 2022) extends this idea using edge-edge correspondence scores to rank which query graphs are most likely to appear in the target.
Another direction of research aims perform subgraph counting (Liu al., 2020; Chen al., 2020) supervised on the number of specific substructures, and again lacks an explicitly search strategy and thus falls short of yielding solutions for Subgraph Matching. Researchers tackling consistent subgraph matching (Yuan et al., 2022) handle complex node or edge constraints using Subgraph Matching subroutine. Hence, advancements to Subgraph Matching can directly benefit such works.
Efforts on using RL for graph NP-hard problems The idea of using RL to replace heuristics in search algorithms for NP-hard graph-related tasks is not new, and we identify three works similar to the present work. (1) GLSEARCH (Bai et al., 2021) detects the maximum common subgraph (MCS) in an input graph pair, which is different from Subgraph Matching which requires the entire q to be matched with G, allowing further improvement in the neural network and search design. (2) RL- RL-QVO (Wang et al., 2022) tackles Subgraph Matching via ordering the nodes in the query graph as global pre- pre-processing step before search, which is an orthogonal direction to our approach to select nodes in the target graph computed at each search step.
2.3 SEARCH-BANE BASSD METHODS FOR SUBGRAPH MATCHING
Due to the NP-hard nature of Subgraph Match- ing, backtracking search is a naturally suitable algorithm since it exhaustively explores the solu- tion space by starting with an empty match and adding one new node pair to the current match
Algorithm 1 Search-based Subgraph Matching.
1: Input: Query graph g, data graph G.
at each step. When the current match cannot be
2: Output: Matches from q G.
further extended, the search backtracks to its pre-
3: Filter: C' < generate candidate node sets.
vious search state, and explores other node pairs
4: Order: ø t generate an ordering for Vg.
5: Search: tockkrackkngg( C,C, ())
to extend the match. However, naively enumer-
ating all the possible states in the entire search
space is intractable in practice, and therefore existing efforts mainly aim to reduce the total number of search steps
for the backtracking search via mainly three ways (Sun & Luo, 2020): (1) Filter nodes in G obtain small set of candidate nodes for each node in g pre-processing step before the backtracking search; (2) Order the nodes in q before the search; (3) Generate a local candidate set of nodes in each step of the search based on the current search state. Algorithm I summarizes the overall backtracking search based framework for Subgraph Matching. It is worth noting that the first three means correspond to the three steps in the algorithm, and therefore any improvement in any of the three steps can be regarded as orthogonal to each other.
The basic idea of backtracking search is outlined in Algorithm 2. The recursive algorithm starts with an empty node-node mapping, and tries to add one new node pair to the mapping M at each recursive call. The action is the new node pair (we, Vz), where u, E V, is selected according to the
3

---

Under review as a conference paper at ICLR 2023
heuristic-basee ordering Ø, and U/ VG is selected according to a policy (which is to be learned by NSUBS) to be one of the local candidate nodes (line 8). that can be mapped to ue. It is noteworthy that this local candidate node set "A,, S VG" is refined over the global candidate sets C' based on the current search state 8t- 8t is defined as (z. G) along with the current mapping M and u4 An, S Va ensures any node in Au, would lead the extended subgraphs 8, still being isomorphic each other. Thus, the local candidate set A., for 2t is the action space, for which we learn a policy (line 9) order the nodes, resulting in an ordered list Au, ordered.
Despite existing efforts to compute small C, good Φ, and small A... reduce search space, we observe that the size of Au, can be up to thousands of nodes for many real-world large
Algorithm 2 Backtrackingle G, C,
target graphs, calling for a smarter policy to or-
1: Input: q. G. C, é. and current mapping M.
der the nodes not only in q but also in G (Au. to be specific). To the best of our knowledge, all the existing methods adopt a random ordering
2: Output: Subgraph match mappings.
3: if |M = =[V, then
4: output M;
in Au,, orderred We conjecture it is because exist-
5: return;
ing local candidate computation techniques can
6: end if
further prune nodes from C. and thus enumer-
7: u, E V o(M);
ating Au, in a random ordering can be tractable
8: Au, +- ae
on small graph pairs. We will experimentally show that this attributes to their failure to find a match for many large graph pairs. In fact, theoretically perfect policy, policy", can find the entire match of the query graph Vg steps or recursive calls, assuming q has at least one match with G. This again inspires our proposed method to improve the policy for node selection from Au,-
9: Auq t policyl St, Au;);
10: for U/ in orderreedd do
M + M.add(uu, Ut):
12: Backtracking G, C) M M.remove (4, U1);
14: end for
3 PROPOSED METHOD
In this section we formulate the problem of Subgraph Matching as learning an RL agent that grows the extracted subgraphs by adding new node pairs to the current subgraphs. We first describe the environment setup, then depict our proposed encoder-decoder neural network which provides actions for our agent to grow the subgraphs in search context.
3.1 RL FORMULATION OF SUBGRAPH MATCHING
We formulate the Subgraph Matching problem Markov Decision Process (MDP), where the RL agent starts with an empty solution, and iteratively matches one node pair at a time until no more nodes can be matched. As mentioned in Section 2.3, our policy assigns a score each action in Au and therefore can be modeled as policy network Pe(aelst) that computes a probability distribution over As, for the current state 8t, where the node pair to select consists of (u,, Uz). However, since de is chosen by Φ we regard an action as a node 1/ selected from Au,- Since each action is target node in Aa,, the neural network must learn good node embeddings that capture the current matching status in each search state, which will be shown in Section 3.2. We define our reward as R(+) 1 the subgraph is fully matched and R(-) = 0 otherwise.
To provide ample training signals to the neural network model, during training, we randomly sample subgraphs from the target graph and record the mapping between the nodes in the sampled subgraph and Va. Therefore, after the search, we collect the positive training signals at each state as all the node-node pairs (u, v) that lead to solution. The collection of such positive pairs is denoted as P(s.). Negative pairs N (st) can be obtained by randomly sampling node-node pairs at each 8, from the action space Au.. However, the solution sparsity issue mentioned previously causes insufficient positive pairs. We therefore propose the following look-ahead loss function which augments P(s,) with the positive node-node pairs in future states. Overall, the look-ahead loss function can be
4

---

Under review as a conference paper at ICLR 2023
formulated as
T-1
Lia (st) = Σ (co()(4k)
Amm
where T corresponds to the final step that matches the entire subgraph, and L/a is the cross-entropy loss computed at St+4- Specifically, Loe (80())))) is the cross entropy loss and computed as the negative of the following:
E(uoojE((aLs) R Rotho ((u, u)) (st) + (1 Rog 1 no ((u, 21) (se)
E(u.))N(scHH) R(-) logTo (ggroo(u, (u. u)}ss)) + (1 R )oo T ((u, ssss))
where To ((u, s)) = =o =o ((u, w)] denotes the raw output of the policy network followed
by applying the Sigmoid function. Since we define R((+) = and R((-) 0, Len (81+4) is simplified as
(E(n)))P((ss)) logTo ( ((u, 2))ss) - [(u,n)eN(Me))) log (1 To To( e))ss))
(3)
In addition to the look-ahead loss that encourages the policy network to recognize positive node-node pairs, we also adopt the max margin loss, Lum- proposed in Lou et al. (2020) to encourage the encoder to produce subgraph- -raph relation aware node embeddings h. Our overall loss function is the combination of the novel look-ahead loss function and the max margin loss function, i.c.
Tsotal Tta + Tumn- More details can be found in the appendix.
3.2 ENCODER DECODER DESIGN FOR POLICY ESTIMATION
Our neural network consists of encoder which produces node-level embeddings for V, and Va and a decoder which transforms the node embeddings into Pa(a)):)) We identify the following challenges: (1) Each state St consists of g. G. and the mapping M, between the matched nodes St.g S Vg and Sr,G C VG. which should be effectively represented and utilized in predicting Po(a:]st); (2) (a is dependent on 8t and a, potentially requiring the node embeddings to be recomputed at every search step and incurring too much computational overhead: (3) Existing Graph Neural Networks (GNN) relying on message passing (e.g. Kipf & Welling (2016); Velickovic et al. (2018); You et al. (2020)) are inherently local, which are incompatible with the policy estimation requiring global matching of q to G. Even the more recent GNNs that enhance expressiveness beyond 1-Weisfeiler- Lehman test (Morris et al.. 2020; Wijesinghe & Wang, 2022) still cannot guarantee the capturing of nodes in the solution, since otherwise the NP-hard task would then be solved. This motivates the following design leveraging the properties of Subgraph Matching as much possible.
3.2.1 ENCODER: EMBEDDING GENERATION VIA QC-SGMNN
The nodes of q and G are encoded into initial one-hot embeddings (0) RI and fed into K sequentially stacked Duery-Conditionee Subgraph Matching Neural Networks (QC-SGMNN) layers to obtain h (K) E DR., where D is the dimension of embeddings, followed by a JUMPING KNOWLEDGE (Xu et al., 2018) network combine the node embeddings from the K layers obtain the final node embeddings, denoted as "Aggregate" in Figure 5.
We start by observing that Subgraph Matching desires all nodes in g to be matched with G, and existing works in Subgraph Matching aiming at reduce A., (Section 2.3) guarantee no false pruning. In other words, Au, is guaranteed to contain the solution nodes G that should match with u that is, A,,, provides useful hints of which nodes should be matched together. We then compute the candidate space A. for every remaining query graph node w' St.g. resulting in a mapping Mj- = [u/ + Aur, Vu' E Vg \ St Intuitively, Mr can be regarded as hints of future node-node mappings. In contrast, Me = {u + (v), Vu E St,g) reflects the current state St, which maps each node in St.g to unique node in G. We define M, as the union of M, and Mf, and define M, as the reverse mapping of M,, which serve the basis for the matching module.
Qc-SGMNN consists of a propagation module, which performs regular intra graph message passing on q and G individually, and matching module, which performs state-dependent subgraph-graph
5

---

Under review as a conference paper at ICLR 2023
State-independent node embeddings: Computed at Sp and cached during search
So
0
S
Propgger
Popegaxe
Propegate
Pageegare
Aguregate
Policy
Encoder
Match
Match
Musch
Manch
S1
Guide
State-dependent graph matching: Computed at every scurch state
Time
Figure I: The overall process of Subgraph Matching is search algorithm that matches one node pair at a time for the input query and target graph G guided by a learned policy. Due to the large action space incurred by the large G in practice, we propose to train a policy network to guide the selection of local candidate nodes in G' at each search state. This requires effective node embeddings to learned that can reflect the vode-to-node mapping the current state and contribute to prediction of the policy and reward. To achieve this end, we propose novel QC-SGMNN encoder layer consisting of a "Propagation" module that performs intra-graph message passing as a typical GNN and "Matching" module that performs state-dependent inter-graph matching (Section 3.2.1). The Po(a, st) is trained using the novel loss functions described Section 3.1.
matching leveraging Mr to pass information between and G. Specifically,
h (k+1)
Sagx (1mssg (h uintrus h. (K)
(k)
Lintra w/ EN)))),
uiintra h (k+1)
faga (ffmsg (h vintra
(8) h of Noteaaoo (N()))),
(K)
giitra
h (k+1)
gintra
freadout (th (R+1)
uiinrra I E VgD).
h (K+1)
(k+1) h vintra = Sagy (fmms (h uintea
(1+1) Dlu E M((u)),,
(4)
u.G+t
B.g. Sags (fmss wintrar h uniinta minntaa Hu E M, (v))),
(6+1)*
(1++)
(R+1)
(++1)
fcombine (h u. G-ag" h wintral:
(k+1)
(k+1)
ho (k++) = fcombine V.
(k+1) (K+1))
The first two steps be any intra- aetra-graph message passing GNNs such as Graph Attention Net- works (Velickovic et al., 2018) with a message function faeg and an aggregation function fagg- corresponding the propagation module. The middle three steps compute intermediate embeddings
that will be used for the last two steps, i.e. the matching module. Specifically, h Ga,G- and h h
(k+1)
compute the cross-graph message passing from G to q and g to using M, and M, respectively (represented as the red dashed lines in Figure 5). A graph-level embedding h h.gintra is computed via freadout and used in the information passing from q to G' to let the embeddings of Ve query- conditioned. We do not inject the graph-level embeddings of G into h (k+1) G could result in too much information loss in the readout operation. The last two steps combine the intra-graph embeddings and inter-graph embeddings via fcombino to produce the final output embeddings. It noteworthy that fmeeg and fagx refer to the general class of functions that yield messages between two nodes and performs aggregation on a set of messages, and in practice, the propagation and matching modules can use different functions for fmeg and fagg.
u.G-gg' since the large size of
To address challenge (2), we make the observation that h (k) only depends on 9 and G and is independent of M,, and thus can be computed once and cached at the beginning of the search (denoted as the top branch in Figure 5) and later reused throughout the search. Our QC-SGMNN decouples the propagation and matching steps and outputs two sources of information separately, allowing the search cache the state-independent node embeddings and dynamically select the computational paths during search. Thanks to the caching, only the initial iteration requires the O(EE EEll computation, and all the subsequent iterations only involve ([V]]AAu,)) complexity, where Am, is the average size of local candidate space.

---

Under review as a conference paper at ICLR 2023
3.2.2 DECODER: ps(ay(st) ESTIMATION
Since the node embeddings of 9 has received the right amount of information from M,. we propose an attention-based mechanism compute the state embedding: h., Euev, fatt (hu {h', ju' h... where fatt computes one attention score per node normalized across Vg to tackle challenge (3). Intuitively, the attention function learns which nodes are important for contributing the eventual subgraph selected by sT. Due to the cross-graph communication in QC-SGMNN, we only aggregate nodes from Vg to obtain the state representation h... taking advantage of the fact that [Vg typically much smaller than |Val in Subgraph Matching, further addressing challenge (2).
For the policy, we aim tackle challenge (3), by using h... The reasons are two-fold. First, by definition Po (aylss) requires as input; Second, the attention mechanism used to compute h.s capturing the future subgraph. Combined with bilinear tensor product with learnable parameter W[IFF] DxDXX with a hyperparameter F to allow the action node embeddings h and h to fully interact, we obtain Pogit (ae(st) MLP AALP(CONCATU a softmax normalization over the logits for all the actions. The decoder has time complexity
W(1Fi h ht.)). followed by
(lVg) + IA
4 EXPERIMENTS
We evaluate NSUBS against seven backtracking-basse algorithms for exact Subgraph Matching, and conduct experiments on six real-word target graphs from various domains, whose details can be found in the supplementary material. We find NSUBS written in Python can outperform the state-of-the-ar solver under most cases, suggesting the effectiveness of the learned policy for ordering nodes in G. Code, trained model, and all the datasets used in the experiments are released as part of the supplementary material for reproducibility. More results and the ablation study can be found the supplementary material.
4.1 DATASETS AND EVALUATION PROTOCOL
We use one synthetic dataset BA and six real- world target graphs. For DBLP and YOUTUBE, we prepare two query sets of small and large query graphs, denoted as "-S" and "-L", respec- tively, i.c. DBLP-S, DBLP-L, and YT-S, YT-L. As shown in Table 1. the largest target graph, YOUTUBE, has over 1M nodes and 2M edges.
Table 1: Target graph description.
Dataset
Domain
VVl
Fgg
BA
Synthetic
10,000
29,991
BRAIN
Biology
1,076
90,811
HPRD
Biology
9,045
34,853
COSMOS
Astronomy
21,596
176,830
To train our model, we sample query graphs of any sizes and let NSUBS perform the search al- gorithm and collect training data from the search tree. Therefore, we sample query graphs from each target graph of sizes ranging from nodes to 128 nodes, and validate that no query graph in the testing set is visible to the model, that is, no graph in the training set is isomorphic to any graphs in the testing set. During the testing stage, for each target graph, we use the following evaluation protocol. For each graph pair, we set time limit of minutes, and record the result of whether a solution found or not, and the number of solutions for solved pairs.
DBLP
Citation
317,080
1,049,866
ETHE
Financial
709,351
946,582
YOUTUBE
Social
1,134,890
2,987,624
4.2 BASELINES AND PARAMETER SETTINGS
We compare NSUBS against series of baseline solvers whose source codes are provided by (Sun & Luo, 2020): LDF (Sun & Luo, 2020), NLF (Sun & Luo, 2020), QUICKSI (Shang et al., 2008), GRAPHIQL (He & Singh, 2008), Tso (Han et al., 2013), CFL (Bi et al., 2016), CECI (Bhattarai et al., 2019), and DP-ISO (Han et al., 2019). We also include NMATCII (Lou et al., 2020) learning- based method for exact Subgraph Matching, by adapting the original implementation provided by the authors of (Lou et al., 2020) into backtracking search framework. Specifically, at each search step, we invoke the inference step of the released trained NMATCH model over the input graphs, and obtain a matching score for each (we, v2) action node pair guide the selection of nodes in Aug-
7

---

Under review as a conference paper at ICLR 2023
Since among the first to learn policy for selecting nodes in G, DP-1SO for filtering and GRAPHQL for query node ordering. We implement the backtracking search framework and DP-1SO's local candidate computation algorithm in Python.
NSUBS uses layers of the proposed Qc- DC-SGMNN encoders. w is set to 10 and max itters is set to 120. Training is performed
server with NVIDIA Tesla V100 GPUs. We train NSUBS for approximately 2 days with randomly sampled subgraphs for each target graph with the Adam optimizer (Loshchilov & Hutter, 2017) with the initial learning rate 0.0005 and the parameter to 0.01 for numerical stability. Gradient clipping is applied with the maximum norm of the gradients set 0.1. We use validation set to select the best model to evaluate.
13
Splved Parr
LDF
40
LDF
GraphOL
NLF
NLF
12
TSO
Grash2L
Salved
TSO
GrashKQL
Solved
DP
12
DPL
DA-4P
DN-sp
CPL
LEE1
1821
Kiaathh
Nitatch
NSuDS
50
120
120
200
250
50
100
Ibp
200
200
200
100
150
300
Time (sec)
Time (sec)
Time (sec)
(a) BA
(b) BRAIN
(c) HPRD
LDF
KLF
S.hhea Faare
25-
NLF
Selved Pairs
GrashOL
15O
Solved Pairs
Grup)(0
DRL
ShapfQL
12
DP iso
CL
CECI
DP-lac
NMazch
NSutd
Wiathh
WWatth
0
50
120
120
2001
230
300
50
100
1b0
200
250
300
50
100
150
200
250
500
Time (sec)
Time
(d) COSMOS
(c) DBLP-S
(f) DBLP-L
40
NLF GraohOL TSD
LDF
Selved Pairs
Salved Pairs
-0
GrephOL TSO
GrashOL T5O
13
CRL
niiie
CECI
DPiss
10
WWltthh
CECT
NSub6
NS. b5
NSJ05
150
30C
Time (swc)
Time
(g)
ETHE
(h) YT-S
YT-L
Figure 2: The growth of the number of solved pairs across time.
4.3 RESULTS
To examine the efficiency of each method and analyze the efficacy across time, we conduct the following evaluation. For each (q, G)) pair, we record the time the method takes to find a solution, and accumulate the number of solved pairs across time. From at t indicates the method solves one graph pair at t. The carlier a method solves the graph pairs, the faster and better the method is.
to 1 300 seconds, an increase
In theory, given infinite amount of time, every method adopting the backtracking search algorithm would be able to solve a graph pair. However, such assumption is not practical. Thus, the curves in Figure 2 have the practical implication that under reasonable amount of time budget, the idea of using a smarter policy indeed brings better performance to Subgraph Matching. Another observation is that the baseline solvers flatten towards the end of 5 minutes, indicating that they get stuck in
8

---

Under review as a conference paper at ICLR 2023
Table Number of solutions found by each method after minutes averaged by the number of the graph pairs in each dataset. For clarity and compactness, each result has been divided by 1000, i.e. each number is in the unit of 10
Method
BA
BRAIN
HPRD
COSMOS
DBLP-S
DBLP-L
ETHE
YT-S
YT-L
LDF
1.21
2.05
0.69
4.80
4.82
I.51
2.50
2.73
1.75
NLF
1.29
2.24
0.37
7.05
4.26
1.06
2.34
2.52
1.06
GRAPHQL
1.42
3.95
1.24
7.70
5.23
2.55
3,53
2.73
1.23
Tso
1,41
1.26
0.50
5.53
4.36
1.36
2.30
2.57
1.24
CFI.
1.56
1.12
0.18
6.97
5.70
1.13
2.32
2.84
0.90
DP-1SO
1.31
2.11
0.54
6.93
4.86
2.63
2.58
3.32
1.88
CECI
1.21
1.03
1.05
6.96
4.18
1.35
1.70
1.60
0.55
NMATCH
1.02
0.00
0.00
0.24
1.25
0.24
1.39
0.37
0.00
NSUBS
2.37
4.58
4.17
3.70
8.32
6.24
2.53
7.93
3.62
unpromising search states that are unlikely to contain the solution, confirming the severity of the aforementioned challenges of solution and reward sparsity.
As shown in Figure 2, NSUBS initially seems not good as other models in the first few seconds due to the additional neural network computational overhead at each step, but achieves the same or better performance all of the 9 query sets after 5 minutes. We observe baseline solvers tend to fail on larger target graphs, as search space pruning on its own is not effective enough to guarantee solutions in such cases with large amount of candidate nodes. Learning-basee based methods outperform solver baselines because they provide a better target graph node ordering, under the same search framework.
Out of the learning- ceaseigg-based methods, NSUBS consistently outperforms NMATCH, it features more powerful encoder that efficiently computes a policy conditioned on the current search state with a better inter-graph communication mechanism. This also suggests that the target graph node ordering provided by NSUBS is much better than the random ordering adopted by solver baselines, confirming that our novelties indeed greatly improve Subgraph Matching performance.
We observe that when the query graph size increase, all methods tend to show lower performance, which can be attributed to the exponentially growing search space. It is noteworthy that the survey paper comparing existing solvers (Sun & Luo, 2020) uses query graphs up to 32 nodes, whereas we challenge all methods by testing on query graphs up to hundreds of nodes. The fact that NSUBS able to solve more graph pairs than baselines when the target graphs are large demonstrates good scalability of NSUBS.
Given the nature of Subgraph Matching, we also evaluate the ability of each method to find as many solutions as possible. As Table indicates, NSUBS outperforms baseline methods on 7 out of datasets, suggesting that the slower but more intelligent NSUBS can not only ensure one solution found, but also provide as many as and even more solutions compared against the faster baseline solvers. The exceptions Figure 2, but on average finds more solutions per graph pair across these two datasets. We empirically observe that the baseline solvers tend find many solutions because nearby solutions can be found. In contrast, NSUBS continues performing neural network operations after one solution found. This indicates the efficiency limitation of the current model, and calls for the need for future efforts to speed up the neural network computation, design even better policy network and training methods to allow discovery of more solutions in lesser iterations, etc.
HPRD and ETHE, where GRAPHQL solves less pairs shown in
solution is found,
CONCLUSION
In this paper, we tackle the challenging and important task of Subgraph Matching, and present a new method for efficient and effective exact Subgraph Matching. It contains a novel encoder-decoder neural network architecture trained using novel look-ahead loss function and max margin loss to improve the policy estimation as well as the encoder. The core component, QC-SGMNN, is query- conditioned graph encoder that performs intra-graph propagation and inter-graph node matching to capture each state. To address the reward sparsity issue posed by the large action space, we augment the positive node-node pairs at each search step with future states' node-node pairs. We experimentally show the utility of the proposed NSUBS method the important Subgraph Matching task. Specifically, NSUBS is able to solve more graph pairs than several existing Subgraph Matching solvers synthetic dataset and six large real-world datasets.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Blair Archibald, Fraser Dunlop, Ruth Hoffmann, Ciaran McCreesh, Patrick Prosser, and James Trimble. Sequential and parallel solution-biased search for subgraph algorithms. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 20-38. Springer, 2019.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.
Yunsheng Bai. Derek Xu, Yizhou Sun, and Wei Wang. Glsearch: Maximum common subgraph detection via learning to search. In ICMI,, pp. 388-598. PMIR, 2021.
Albert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-33) 1999.
Bibek Bhattarai, Hang Liu, and Howie Huang. Ceci: Compact embedding cluster index for scalable subgraph matching. In Proceedings of the 2019 International Conference Management of Data, pp. 1447-1462, 2019.
Fei Bi, Lijun Chang, Xuemin Lin, Lu Qin, and Wenjie Zhang. Efficient subgraph matching by post- poning cartesian products. In Proceedings of the 2016 International Conference Management of Data, pp. 1199-1214, 2016.
Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. A subgraph isomorphism algorithm and application to biochemical data. BMC bioinformatics, 14 (7):1-13, 2013.
Chen Cai and Yusu Wang. A simple yet effective bascline for non-attributed graph classification. arXiv preprint arXiv:1811.03500 2018
Tianyi Chen and Charalampos Tsourakakis. Antibenford subgraphs: Unsupervised anomaly detection in financial networks. In Proceedingy of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2762-2770, 2022.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? NeurlPS, 33:10383-10395 2020.
BC Coutinho, Sungryong Hong, Kim Albrecht, Arjun Dey, Albert-Lász1ó Barabási, Paul Torrey, Mark Vogelsberger, and Lars Hernquist. The network behind the cosmic web. arXiv preprint arXiv:1604.032366, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NewrIPS, pp. 1024-1034, 2017.
Myoungji Han, Hyunjoon Kim, Geonmo Gu, Kunsoo Park, and Wook-Shin Han. Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together. In Proceedings of the 2019 International Conference on Management of Data, pp. 1429 1446, 2019.
Wook-Shin Han, Jinsoo Lee, and Jeong- Hoon Lee. Turboiso: towards ultrafast and robust sub- graph isomorphism search in large graph databases. In Proceedings of the 2013 ACM SIGMOD International Conference Management of Data, pp. 337-348 2013.
Huahai He and Ambuj K Singh. Graphs-at-a-time at---mmm: query language and access methods for graph databases, In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 405-418, 2008
Moritz Helmstaedter, Kevin Briggman, Srinivas C Turaga, Viren Jain, H Sebastian Seung, and Winfried Denk. Connectomic reconstruction of the inner plexiform layer in the mouse retina. Nature, 500(7461):168-1744 2013.
Hui Jiang, Yuxin Deng, and Ming Xu. Quantum circuit transformation based on subgraph isomor- phism and tabu search. arXiv e-prints, pp. arXiv-2104, 2021.
10

---

Under review as a conference paper at ICLR 2023
Eric Jonas, circuitcatt//mouusrettin. https:
htte://aBBteer/mmuuurttttt.aaaa, 2015.
Chathura Kankanamge, Siddhartha Sahu, Amine Mhedbhi, Jeremy Chen, and Semih Salihoglu. Graphflow: An active graph database. In Proceedings of the 2017 ACM International Conference on Management of Data, pp. 1695-1698, 2017.
Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81-93, 1938.
Hyunjoon Kim, Yunyoung Choi, Kunsoo Park, Xuemin Lin, Seok-Hee Hong, and Wook-Shin Han. Versatile equivalences: Speeding up subgraph query processing and subgraph matching. In Proceedings of the 2021 International Conference on Management of Data, pp. 925-937, 2021.
Jinha Kim, Hyungyu Shin, Wook-Shin Han, Sungpack Hong, and Hassan Chafi. Taming subgraph isomorphism for rdf query processing. arXiv preprint arXiv:1506. 01973, 2015.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2016.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
Longbin Lai, Lu Qin, Xuemin Lin, and Lijun Chang. Scalable subgraph enumeration in mapreduce. Proceedings of the VLDB Endowment, 8 8(10):974-985, 2015.
Longin Lai, Lu Qin, Xuemin Lin, Ying Zhang, Lijun Chang, and Shiyu Yang. Scalable distributed subgraph enumeration. Proceedings of the VLDB Endowment, 103))217-228, 2016.
Longbin Lai, Zhu Qing. Zhengyi Yang, Xin Jin, Zhengmin Lai, Ran Wang, Kongzhang Hao, Xuemin Lin, Lu Qin, Wenjie Zhang, et al. Distributed subgraph matching timely dataflow. Proceedings of the VLDB Endowment, (2(10):109--110 2019.
Jinsoo Lee, Wook-Shin Han, Romans Kasperovics, and Jeong-Hoon Lec. An in-depth comparison of subgraph isomorphism algorithms in graph databases. Proceedings of the VLDB Endowment, 6(2): 133-144, 2012.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: // www...a.aaaafooom edu datta, June 2014.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. ICML, 2019.
Xiang Ling, Lingfei Wu, Saizhuo Wang, Tengfei Ma, Fangli Xu, Chunming Wu, and Shouling Ji. Hierarchical graph matching networks for deep graph similarity learning, 2020. URL https: // //oppnrevviww.o net. hott://oormmmmdrreeeer-----
Xin Liu and Yanggiu Song. Graph convolutional networks with dual message passing for subgraph isomorphism counting and matching. In AAAI, volume 36, pp. 7594-7602, 2022.
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 & Data Mining, pp. 1959-1969, 2020.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 11X1v:1711.05101, 2017.
Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovee, et al. Neural subgraph matching. arXiv preprint arXiv:2007.03099, 2020.
Tinghuai Ma, Siyang Yu, Jie Cao, Yuan Tian, Abdullah Al-Dhelaan, and Mznah Al-Rodhaan. A comparative study of subgraph matching isomorphic methods in social networks. IEEE Access, 6: 66621-66631, 2018.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. NeurIPS, 33:21824-21840, 2020.

---

Under review as a conference paper at ICLR 2023
Indradyumna Roy, Venkata Sai Baba Reddy Velugoti, Soumen Chakrabarti, and Abir De. Interpretable neural subgraph matching for graph retrieval. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp.
2022.
Haichuan Shang, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proceedings of the VLDB Endowment, 1(1): 364-375, 2008.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-3555 2017.
Shixuan Sun and Qiong Luo. In-memory subgraph matching: An in-depth study. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 1083-1099 1098, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018.
Hanchen Wang, Ying Zhang, Lu Qin, Wei Wang, Wenjie Zhang, and Xuemin Lin. Reinforce- ment learning based query vertex ordering model for subgraph matching. arXiv preprint arXiv:2201.11251, 2022.
Runzhong Wang, Zhigang Hua, Gan Liu, Jiayi Zhang, Junchi Yan, Feng Qi, Shuang Yang. Jun Zhou, and Xiaokang Yang. A bi-level framework for learning to solve combinatorial optimization on graphs. NeurlPS, 34, 2021.
Asiri Wijesinghe and Qing Wang. A perspective on" how graph neural networks go beyond weisfeiler-lehman." In ICLR, 2022.
Zhihao Xing and Shikui Tu. A graph neural network assisted monte carlo tree search approach to traveling salesman problem. IEEE Access, 8:108418-104427 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie
Jegelka. Representation learning graphs with jumping knowledge networks. ICML, 2018.
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, pp. 1-8, 2012.
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. NewrIPS, 33: 17009-17021, 2020.
Ye Yuan, Delong Ma. Aoqian Zhang, and Guoren Wang. Consistent subgraph matching over large graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pp. 2536-2548. IEEE, 2022.
Shijie Zhang, Shirong Li, and Jiong Yang. Gaddi: distance index based subgraph matching in biological networks. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, pp. 192-203, 2009.
A DETAILS ON TRAINING AND TESTING OF NSUBS
A.1 DETAILS ON COLLECTING TRAINING SIGNALS
As mentioned the main text, we utilize the max margin loss proposed Lou et al. (2020) which can be written as
L (St+k)
Σ
E(hn, +
Σ
max(0, a E(h,,
(14))
12

---

Under review as a conference paper at ICLR 2023
where
E(hu, h.) ||max h. - ho
The intuition behind the loss function to encourage the encoder to produce node embeddings that capture the subgraph-gran relationship. Specifically, the loss encourages each dimension of h. to be less than h, and the error term measures the deviation of the current node embeddings from this desired property.
is noteworthy that both Lıs and Lum rely on the positive and negative node-node pairs, which are obtained by performing search on (g. G)) pairs where q is the randomly sampled training subgraph queries from G. Therefore, the overall NSUBS model does not need any pre-solved graph pairs for training.
Here we describe more details on how we prepare the positive node-node pairs P(st). During training, we set time limit of 5 minutes for each (g. G) pair, and at the end of the search process, we obtain search tree where each node in the search tree corresponds to a state 8t. For a state 8t, we look ahead at all sequences of states leading to solution starting from St. and compute the Lia loss according to Equation for each sequence, and sum up the loss for all such sequences. To obtain N (s,), we randomly sample P(s:) node-node pairs from the action space Au,, where we is the query graph node selected by Φ as described in Section 2.3, and Au, is the local candidate nodes in G to be selected by the neural network.
We provide an illustration of the collection of positive node-node pairs in Figure 3. In this example, there are two sequences of states leading to a solution of the full match of q G. for which we label the action node pair associated with each action. For clarity, we only show the first few states and omit the later states. It is noteworthy that search states that do not lead to a solution, e-g. $1, do not produce any training signal, since there is insufficient information regarding such states. Since we always perform random subgraph sampling to generate training graph pairs, we ensure least one sequence of actions leading to solution by forcing the initial search trajectory to follow the ground-truth node-node mapping obtained when conducting sampling. In Figure 3, this corresponds to the initial trajectory (0,0), (1,2), (2,5), (3,9), (4.7)...
Search Tree
(1.2)
(2:5)
(3.9)
(4.7)
Positive node- node pairs for
Positive node- node pairs for
Positive node- node pairs for the Szi
the Sp:
the Sy:
Ixtal Sux
(0,0)
(1,2)
(2,5)
0L1
(1.2)
(2,5)
(3,9)
(2.5)
(3,9)
(4,7)
(3,9)
(4.7)
(1.))
(4.7)
Node
(2.21
(3.9)
(4.10)
(0.11)
(1,5)
State
State Transition
(2.2)
(4.10)
Example illustrating
Figure 3: The search tree after the 5-minute time budget provides positive training signals, An action node pair (we, Uz) where E V, and U. E VG is associated with an edge. Negative training pairs are randomly sampled from Vg VG.
A.2 DETAILS ON TESTING GRAPH PAIRS
We conduct evaluation on the following testing graph datasets:
1. The synthetic dataset BA is unlabeled and generated using the Barabási-Allert model (Barabási Albert, 1999) with the parameter of attachment set to 3. We sam- ple 50 query graphs each of 64 nodes the query set. The sampling algorithm starts with randomly selected initial node, and then performs random walk until a subgraph consisting of pre-defined number of nodes is sampled. Each step in the random walk selects node from the neighboring nodes the current node to visit in the next step, where the node can be node or already selected node, i.e. the random walk is allowed to backtrack. We
13

---

Under review as a conference paper at ICLR 2023
define the raw sampling probability to be 1/p if the node is the selected subgraph, and p otherwise. A small therefore encourages re- re-visitation and the final subgraph tends to be "star"-like, while a large p typically yields more "path"-like subgraph. Each of the 50 sam- pled subgraphs uses a different p parameter by sweeping across the range from 0.001 to 1000. Specifically, the i-th sampled subgraph uses p 0.001 exp (log(109) (109) )/99 (i - 1)), i.e. the first subgraph uses p = 0.001, the second uses p = 0.00133, the third uses 0.00176, etc. The 49th subgraph uses p 754.312, and the last uses p = 1000. Without specific mentioning, the sampling of subgraphs for other datasets uses this algorithm.
2. The BRAIN dataset is obtained from mouse retina connectome (Helmstaedter et al., 2013) with node labels representing the coarse type determined from supplemental text (Jonas, 2015). We sample 50 query graphs each of of 64 nodes. There are 5 stypss of node labels in total.
3. The HPRD target graph is a protein-protein interaction graph obtained from a recent survey paper on Subgraph Matching (Sun & Luo, 2020) without node labels. Similar to BRAIN, we sample 50 64-node graphs as the query graphs.
4. The COSMOS graph represents the network of galaxies (Coutinho et al., 2016) without node labels, for which we sample 50 query graphs each of 32 nodes as queries.
5. The DBLP and YOUTUBE target graphs are also used in the survey paper (Sun & Luo, 2020), but instead of sampling subgraphs as query graphs, we rely on ground-truth com- munities mined from an algorithm (Yang & Leskovec, 2012) as query graphs. According to Leskovee Krevl (2014), for DBLP, authors who published to a certain journal or conference form a community, and for YOUTUBE, user-defined groups are considered as ground-trute communities. Since many ground-truti communities are provided by Leskovee & Krevl (2014), we sample a 50-graph small query set and 50-graph larger query set for these two datasets. Specifically, DBLP-S contains communities of 20-30 nodes, DBLP-L contains communities of 30-60 nodes, YT-S contains communities of 30-40 nodes, and YT-L contains communitics of 100100 nodes.
6. The ETHE dataset is obtained from a recent paper on financial anomoly detection (Chen & Tsourakakis, 2022). The graph represents 1-week Ethereum blockchain transactions where each edge represents a transaction with the amount. We run the released code provided by the paper to extract top anomalous subgraphs, and filtering subgraphs that are too small or too large, yielding 24 subgraphs ranging from to 822 nodes as query graphs. Intuitively, these subgraphs are relatively dense and correlate with possibly malicious behavior. We remove the transaction amount from the edges, and run Subgraph Matching using the mined subgraphs as query graphs and the original transaction graph as the target graph. Although NSUBS can potentially be extended for clique or anomaly detection, we leave the investigation as future work.
A.3 DETAILS ON TRAINING AND VALIDATION GRAPH PAIRS
For each target graph, we sample query graphs of various sizes to perform curriculum learning, as shown effective by carlier graph matching works (Bai et al., 2021; Lou et al., 2020). We ensure the testing query graphs and training query graphs are different by using different random seeds and further rumning an isomorphism checker to ensure none of the testing query graphs are visible during training. The query graphs come in the following sizes: 8, 16, 24, 32, 48, 64, 96, and 128 nodes. noteworthy that the query graphs are obtained from provided ground-truth communities or mined subgraphs for DBLP, ETHE and YOUTUBE for testing, but during training, all the query graphs are obtained via subgraph sampling.
Regarding the validation scheme, we use the following validation set for validating the models: query graphs of size 8, 3 query graphs of size 16, 3 query graphs of size 32, 3 query graphs of size 64, and 3 query graphs of size 128. These 15 query graphs are sampled from the same target graph with different random seeds, and ensure they are not isomorphic to any query graphs in the training set (nor isomorphic to any query in the testing set if the testing set is obtained via random subgraph sampling).
The overall training process consists of the following iterative steps: (1) Sample a query graph from G and perform search with limit of 5 minutes; (2) Collect training signals and add them to a replay
14

---

Under review as a conference paper at ICLR 2023
buffer; (3) Perform training by sampling batch of training examples from the replay buffer and running back prockk-ppagttion (4) Once every times of performing search on training graph pairs, we iterate through the 15 graph pairs in the validation set with time budget of 40 seconds, and record the validation reward, which is defined as the average best subgraph size. We accept the trained model if the validation reward improves, and revert the previous best model otherwise by loading the best model's s checkpoint. At the end of the training process, we evaluate the best model that achieves the best validation performance.
A.4 DETAILS ON HYPERPARAMETERS
For the encoder, we set the intra-graph fagg and faag functions to GRAPHSAGE (Hamilton et al., 2017), and set the inter-graph fagg function to be SUM and fmag function to be dot-product style attention (Vaswani et al., 2017) over incoming messages. Specifically, the message collected by each query node, hu.G- E IR consists of attended node embeddings from v' E MM(u). Overall, Gu, is computed as
Σ (MEM,(w)
softmax (MLP,
(nn,aa (hu,,iiniittrrr)
MLP (intra MLL. (ho'' intra)-
(5)
The message collected by each target node, hu.q E R2D, consists of attended node embeddings from w' E (v) and the whole query graph embedding, hqgintra Overall, huggGG computed as
hag-a = Σ CONCAT(K', u. lggintra), (MM
(6)
where
h h softmax
W'E,," (v) (MLP, (iutr)))))) MMP (he,ic((, MLLA imtra).
In total, we use four different MIPss i.e. ML.P,, MLPG, MLP and MLPvAL. following (Vaswani et al., 2017), with an ELU(-) activation after the final layer.
We set the foombine function to be the concatenation CONCAT followed by MLP. We choose MEAN the readout function freadout for computing the query graph-level embedding. We choose the MAX function as the aggregation function for our Jumping Knowledge network which aggregates the node embeddings. We apply layer normalization (Ba et al., 2016) to the final node embeddings before feeding into the decoder.
For the encoder, we stack layers of intra-graph message passing with dimension 16. We stack 8layers of the inter-graph message passing with all MLPs outputting dimension 16. For the decoder, we set MI.P att to dimensions [16, 1] and MLP, dimensions [16, 32, 16, 8, 4, 1]. We set the policy head's bilinear layer, W 11FF,, to output dimension F' = 32 and the policy head's 's MLP to dimensions [48, 32, 16, 8, 1J. For all the MLPs, we use the (LU(x) activation function on the hidden layers. For MLP... ., apply LeakyReLU(() function following the final layer.
The goal of the encoder is to learn good node embeddings that capture the structural matching of q and G, and thus we do not encode the node labels initial encodings. Instead, we rely the candidate set generation algorithm to handle the constraint that only nodes of the same label can match. Therefore, it is critical to encode the nodes into initial encodings properly. A simple way to encode the nodes is to assign constant encoding to every node in both and G. To enhance the initial encodings, we adopt Local Degree Profile (LDP) scheme (Cai & Wang, 2018) concatenated with 2-dimensional one-hot vector indicating whether a node is currently selected or not.
Our replay buffer of size 128. During the training process. we repeatedly run minutes of search, populating the replay buffer, 3 minutes of replay buffer sampling and buck-propagation training on as many replay buffer samples possible, and performing validation choose whether or not we commit the learned model. One iteration of this process typically takes around 10 minutes. Hyperparameters were found by tnnig for performance manually against the validation dataset.
B NOTES ON SEARCH
B. INDUCED VS NON- SUBGRAPHS
15

---

Under review as a conference paper at ICLR 2023
One key detail regarding the subgraph definition is whether the subgraph is induced or non- non-induced. An induced sub- graph q|S] consists of all the nodes 5 S Vi and requies that for every edge (u, u') E Feg. if both u and u' are in S. then the edge (u, v must be included in the edges of q(S) as well. Intuitively, an induced subgraph does not allow any edges in the original graph to be dropped, as long as both endpoints of the edge are included by the subgraph. In contrast, a non-induced subgraph q[S] consists of all the nodes S C V, but allows edges in Egg to be dropped. In this paper, we adopt the definition of non-induced sub- graph, which is consistent with Han et al. (2019).
q is an induced subgraph of G.
q is a non-induced subgraph of G.
Figure 4: Comparison between an in- duced (left) and a non-induced (right) subgraph. We use the red color to denote the nodes that are included in the match.
B.2 CHOICE OF FILTERING, QUERY NODE ORDERING, AND LOCAL CANDIDATE COMPUTATION
Motivated by prior work benchmarking solver baselines (Sun & Luo, 2020), we adopt DP-1SO as the filtering method, GRAPHQL. as the query node ordering method, and GRAPHQL as the local candidate computation method in NSUBS and NMATCH. As shown by the experimental results in the main paper, this design choice plays much smaller role in Subgraph Matching than smart target graph node ordering, highlighting the need for NSUBS. Furthermore, we find that optimal filtering, query node ordering. and local candidate computation settings are highly dataset-dependent and hard to determine beforehand; however, because NSUBS's design is orthogonal to such choices, it could easily be adapted to different filtering and query node ordering algorithms. We leave such study to future work.
The filtering method produces global candidate set, C: V - Vi, drastically prune the search space of possible matchings. A simple method to compute C' is to only allow mappings from u, to o if 0t has degree higher than or equal to the degree of u, Different filtering algorithms use different such rules (Sun& & Luo, 2020). The query node ordering gives a search plan on which nodes to select first. simple method is picking the u nodes with the least candidate target nodes given by C. Different node ordering algorithms use different such rules (Sun & Luo, 2020).
During the search process, the local candidate set guarantees all subgraph mappings found throughout the search process are isomorphic. Specifically, it ensures u, is matchable to tt i.e. E Au, only if (1) all edges between U4 and the currently matched query subgraph (with node set S) exist between ie and the currently matched target subgraph: (Me; u') E E u' E S = (v,, M(u)) E Eg and (2) the matching, (ue, Uz) exists in the candidate set: Vy E C(us). There are many different implementations and optimizations to ensure these conditions hold. For instance, query tree data structure (Han et al., 2019) can be stored, allowing O(1) lookup for (u,, u/) E Eg connections given particular query node ordering. Different local candidate computation algorithms use different such optimizations (Sun & Luo, 2020). Even though the subgraph isomorphism constraint is ensured through the local candidate set, Subgraph Matching is by no means an easy task due to the large amount of nodes in A...
Among different techniques to further improve the accuracy of Subgraph Matching approaches, learning a state-dependent policy to select nodes from is one direction worth mentioning. We currently only learn to select nodes in A,, VG partly because there is usually a small amount of nodes in 4, e.g. 32 nodes or 128 nodes, while the number of nodes in Au, is much larger. As mentioned in the main text, RL-QVO (Wang al., 2022) learns a inteednndeen node ordering policy, Φ. via RI that is executed before search. We call such & query node ordering. We argue it is promising future direction to explore learning to select both nodes in q and nodes in G at each search iteration.
As shown effective by previous works, we adapt a promise-based search strategy (Bai et al., 2021), which backtracks to any earlier search state, instead of the immediate parent, whenever a terminal state is reached. We choose which earlier search state to backtrack to by computing a 2:1 weighted average of the search depth normalized by the query graph size and the percentage of explored actions, allowing search to quickly exit local minima. We include this adaptation on all learning methods. We also tried the promise-bane based search on the solver baselines, but found the performance difference
16

---

Under review as a conference paper at ICLR 2023
is minimal, typically around 2%. This is because solver baselines do not assign any ordering to the target graph nodes, thus there is no clear incentive to backtracking early.
C COMPARISON WITH RELATED WORKS
C.I COMPARISON WITH GRAPH MATCHING NETWORKS
Although GRAPH MATCHING NETWORKS (Ling et al., 2020) provides soft node-node correspon- dence scores, does not provide a discrete subgraph matching. A naive solution is thresholding the soft correspondence matrix to obtain matching. But thresholding does not guarantee 1-1 mapping between query graph and target graph nodes. Another idea is to use the hungarian algorithm (Kuhn, 1955) obtain 1-1 mapping, but this doesn't guarantee the matched subgraphs would be isomorphic. Hence, a search framework is required to extract the discrete subgraph matching.
We experimentally verify that NSUBS's QC- DC-SGMNN encoder is superior to GRAPH MATCHING NETWORKS' s encoder. This is because QC-SGMNN ignores noisy inter-graph messages by filtering them out with the local candidate set, learns unique representations for each state by being search state dependent, and caches intra- gulta-graph messages for more efficient execution.
C.2 COMPARISON WITH DMPNN
Although DMPNN (Yuan al., 2022) provides soft node scores in the target graph, it does not provide the discrete subgraph matching. A naive solution is thresholding the soft scores to obtain a discrete subset of target graph nodes, but this cannot guarantee the extracted nodes are isomorphic to the query due to the lack of any way to guarantee that. Hence, a search framework is required to extract the discrete subgraph matching.
We experimentally verify that NSUBS's 's QC-SGMNN encoder is superior DMPNN's s encoder in Section D. ..1.1. .2. This because QC-SGMNN state-dependent and can learn unique representations for each search state. Furthermore, Qc- DC-SGMNN performs interg-raph message passing, that DMPNN misses.
C.3 COMPARISON WITH MAXIMUM COMMON SUBGRAPH (MCS) DETECTION AN GLSEARCH
C.3.1 COMPARISON WITH MCS
Subgraph Matching and MCS detection are highly related tasks, and one can convert Subgraph Matching to MCS detection by feeding the input (g. G) pair to an MCS solver, and check if the MCS between & and G is identical to q. However, we note the following differences at the task level:
1. Subgraph Matching requires all the nodes and edges in g to be matched with G, whereas MCS detection does not require one of two input graphs to be contained in another.
2. Subgraph Matching by definition requires q be smaller or equal to G, since otherwise the solver can immediately return "no solution". In practice, the query graph is usually given by the user as input, and usually contains less than 100 nodes (Sun & Luo, 2020).
The first difference has several consequences. First, although one can solve Subgraph Matching via an MCS solver, the other way does not hold, i.e. one cannot use a Subgraph Matching solver for MCS detection, since Subgraph Matching has the stronger constraint of matching the entire 9. Second, the stronger constraint of Subgraph Matching allows existing search algorithms to design pruning techniques as mentioned in the main text.
The second difference implies that the learning models designed for Subgraph Matching may not work well for MCS detection and vice versa. For example, NSUBS has a novel encoder layer with matching module that has time complexity (VV, || l)- However, if q becomes prohibitively large, e.g. large as G' containing millions of nodes, then the matching step would become bottleneck and make the overall approach too slow to be useful in practice. Therefore, NSUBS cannot be used for MCS detection not only because fundamentally the search algorithm leverages the stronger constraint Subgraph Matching, but also because the learning model would be inefficient and thus useless in practice. By the same reasoning, NSURS is likely be ineffective for graph isomorphism checking
17

---

Under review as a conference paper at ICLR 2023
when both imput graphs are of the same size and very large. This suggests the difficulty of designing a general neural network architecture that works efficiently and effectively for a series of related but different combinatorial optimization tasks. In theory, many such tasks are equivalent and can be converted to each other, but in practice, specialized models should be designed to render a truly useful learning- based approach.
C.3.2 COMPARISON WITH GLSEARCH
Although GLSEARCH 's maximum common subgraph (MCS) framework can theoretically be applied for subgraph matching. in practice, search algorithms designed specifically for subgraph matching work much better than those designed for maximum common subgraph (Archibald et al., 2019). Thus, adaptations are needed to effectively use GLSEARCH for Subgraph Matching.
In terms of RL framework, GLSEARCH uses value networks instead of policy networks, which not effective for Subgraph Matching. Concretely, GLSEARCH performs the execution of each action to get its next state 1,,1, and compute the value associated with 8c+11 for the Qsst, (()),a)). This named as "factoring out action" in Bai et al. (2021), and requires sequentially going through all the actions to obtain the next states, for which GLSEARCH adopts heuristic to reduce the amount of actions. There is not such a heuristic in Subgraph Matching, and hence value networks become very inefficient. In contrast, NSUBS efficiently computes one embedding per node for both g and G using the QC-SGMNN encoder layer, and computes Po (st) in the decoder by batching the node embeddings that are in the action space, i.e. Ploga (or|st) = MLP (CONCAT(H)) W hu,, h).)) can be turned into a batch operation for all the node embeddings involved in the action space of 8t-
In terms of model design, GLSEARCH only performs interaction between the graphs in the decoder, whereas NSUBS interacts the 2 graphs after each graph neural network layer. Because of this, NSUBS decouples the propagation and matching modules to cache the intra-graph embeddings for efficient computation. Furthermore, the query-conditioning in NSUBS's QC-SGMNN captures the asymmetric nature of Subgraph Matching, unlike GLSEARCII's model.
In terms of loss design, GLSEARCH opts for Deep-Q Network loss instead of lookahead loss, because it uses factored out netue-ns This means it does not fully exploit the loss signal. Most importantly, GLSEARCH cannot use the max margin geometric loss term (Lou et al., 2020), since GLSEARCH does not provide node embedding pairs at state 8; to represent action
We experimentally verify that NSUBS's choice of policy network, model design, and loss is superior to GLSEARCH.
C.4 COMPARISON WITH ISONET
We appreciate ISONET'S contribution towards using edge-centric geometric representations (Roy et al., 2022); however, it is not directly comparable because ISONET aims to rank which query graphs are most likely to appear in the target graph, without providing the discrete subgraph matching.
While ISONET provides soft edge-edge and node-node correspondence scores for interpretability. it does not guarantee& discrete sugbraph matching. ISONET indeed reports some case studies where the hungarian algorithm can extract some subgraph matchings that satisfies isomorphism constraints, this fails to scale to very large query and target graphs. Thus, a search framework is required to reliably extract the discrete subgraph matching.
Mosel-wise, ISONET passes each graph through autra-graph message passing then computes the edge-egde or node-node dignmeen/permutatioon matrix by taking the dot product of node or edge embeddings from the query and target graphs. NSUBS's QC-SGMNN improves this by introducing an efficient query-conditioned matching module between intra-graph message passing layers. Loss-wise NSUBS's 's lookahead loss improves ISONET by merging contrastive learning loss (Lou et al., 2020; Roy et al., 2022) with RL loss.
C.5 COMPARISON WITH RL-QVO
RL- RL-QVO is orthogonal to NSUBS, proposing a better query vertex-ordering scheme for subgraph matching. For large graphs, target-vertex ordering becomes the bottleneck instead of query vertex-
18

---

Under review as a conference paper at ICLR 2023
ordering, as enumerating all target vertices for each query vertex becomes infeasible by the NP-Hard nature of subgraph matching.
Unlike RL-QVO, which uses random target vertex vertex-ordering, NSUBS learns policy network to perform target vertex-ordering In addition to RL-QVO 's single graph encoder, NSuBS considers the query target graph matching with QC-SGMNN. Unlike RL-QVO 's simple PPO loss, NSUBS learns geometric node representations with lookahead loss.
D ABLATION STUDIES AND ADDITIONAL RESULTS
D.I ABLATION STUDIES
We perform a series of ablation studies whose results are shown in Table 3. We find our key novelties indeed greatly contribute NSCBS's superior performance on Subgraph Matching, particularly the encoder-decoder design.
D.1.1 VARIANTS NSUBS
Table 3: Ablation study results Subgraph Matching over HPRD. The ratio of the number of solved pairs over the 50 pairs in the query set is reported. The average number of solutions (divided by 103) reported too.
Model
Solved %
# Solutions
LDF
0.08
0.69
NLF
0.04
0.37
GRAPHQL
0.16
1.24
Tso
0.06
0.50
CFL
0.02
0.18
DP-ISO
0.06
0.54
CECI
0.12
1.05
NMATCH
0.00
0.00
NSUBS
0.48
4.17
NSUBS-rand-neg
0.36
3.35
NSUuS-no-look-ahaud
0.42
3.68
NSUBS-nO-mm
0.08
0.73
NSUURS-2-encoder-lyyer
0.24
0.25
NSUBS-D =
0.04
0.30
NSUBS-GIN
0.30
2.73
NSUBS-nn-QQ-machinn
0.34
2.98
0.26
2.39
GMN-encoder
0.30
2.89
DMPNN-encoder
0.32
2.25
GLSeARCH-adapted
0.22
1.88
Table 3 shows the ablation study results.
1. We first perform the random sampling of negative node-node pairs (N(s:) in Equation 2) from all the node-node pairs Vg and Va instead of from Au,- We denote the model as which performs worse than NSUBS but still outperforms baselines. This suggests that the negative sampling should be performed using "harder" examples sampled from the local candidate space instead of all the possible node-node pairs. Such harder negative examples train the model to better identify the promising actions over the unpromising ones at each state.
2. We replace the look-ahead loss with simpler version, by only looking at the current state's positive node-node pairs without considering future states. ASScB--no-look-hhee performs worse than NSUBS, indicating the usefulness of the look-ahead loss.
3. We remove the max margin loss, and as result, NSUBS-no -oommm performs much worse, suggesting the necessity for training the encoder produce good node embeddings. Since
19

---

Under review as a conference paper at ICLR 2023
Encoder: QC-SGMNN
Policy p(a,ss,)
Ur
State St
Action ag (ue, 2t))
Section Replaced with: I.GMN DMPNN G.arch
Section D.1.2
Replaced with: G.G.Scarch
Figure 5: Summary of ablation studies performed in Section D.1.2. For GMN and DMPNN, only the encoder design is changed to other models, and all the other components, including the decoder choice, the search method, the training data and scheme, etc. are exactly the same as our proposed NSUBS.
the encoder training is shown to be important, we then perform series of ablation study experiments on the encoder.
4.
uses 2 encoder layers instead of 8. NSUBS-D 4 decreases the embedding dimension from 8 to 4. NSUBS replaces the GRAPHS AGE model with GIN. These models perform worse than NSUBS, among which NSUBS-D 4 performs the worst, indicating that a dimension that is too small cannot capture enough information for the HPRD dataset.
5. "SSuBSnnoQ-maile
removes the concatenation of h inttra in the computation of h h((+t) b..g-a
(k+1)
(k+1)
in Equation 4. The worse performance shows the contribution of making the attention from to G conditioned on the whole-graph representation of
6. ASUuBS-no-LDP-encoe
removes the Local Degree Profile encoding mentioned Sec- tion A.4. The worse performance shows the importance of encoding the nodes initially with degree information.
D.1.2
REPLACEMENT
In addition, we perform the ablation study by replacing our QC-SGMNN encoder with the Graph Matching Neural Network (GMN) (Li et al., 2019) encoder. GMN introduces the idea of inter-graph message passing, but our novelties make feasible, in terms of efficiency and effectiveness, for Subgraph Matching.
We summarize three key differences between GMN and QC-SGMNN:
GMN produces soft node-node matching matrix between two graphs instead of hard node selections indicating which nodes should be matched between and G. We therefore only utilize GMN's encoder layer and everything else being the same decoder, the training scheme, the search framework, etc. In other words, we adapt GMN for Subgraph Matching denoted GMN-encoder Table 3.
model, including the
To improve GMN's efficiency, Qc-SGMNN (1) prunes the intergraph interaction space using the local candidate set and (2) decouples the intra- and inter- message passing for caching. Section D.2 provides more details.
To improve GMN's effectiveness, QC-SGMNN (1) prunes noisy inter-graph interactions with the local candidate set and (2) proposes carefully designed graph-to-node propagation.
The worse performance of GMN indicates the necessity of the proposed DC-SGMNN designed for Subgraph Matching.
Although DMPNN outputs approximate count between 9 and G, adapt DMPNN's 's encoder in our framework, and the worse performance of eepdder again validates the usefulness of QC-SGMNN.
20

---

Under review as a conference paper at ICLR 2023
Besides what is mentioned in Section C.3, there some additional notes regarding how adapt GLSEARCH. To adapt GLSEARCH for subgraph matching, we first convert GLSEARCH's value network into a policy network by pipelining (1) an action execution engine, which executes each action, at, in the action space for an input state, St, to obtain a set of next states (St41/va, E Au, (2) the GLSEARCH value network, which converts each next state, 8141, into single policy network score, p(a,
Generalizing the equivalence class idea from GLSEARCH subgraph matching, we use the local candidate sets in place of bidomains within the adapted GLSEARCH. Notice, since GLSEARCI does not create node embeddings for action, at we remove the max margin component of lookahead loss for these experiments. We use the same graph neural network encoder type as QC-SGMNN, but unlike NSUBS, which only runs the graph neural network once, GL.SFARCH runs the graph neural network for each action in the action space. Hence, to prevent out of memory errors, GLSEARCH only uses layers instead of 8. We use the same hyperparameters for interact and pooling model architecture, dimensions, and strides described in the GLSEARCH paper. We call this model GLSEARCI--adapted
The worse performance of GLSEARCTT-aaated verifies NSUBS's choice of policy network, model design, and loss greatly improves performance.
D.2 REDUCTION OF CANDIDATE SPACE
We plot the change of global candidate space (CS) size and the local candidate space (I.CS) size across time in Figure 6. Specifically, at each search iteration. node u from the query graph is chosen by o, and the local candi- date space is computed for ue. Therefore, we can record the number of candidates for ue in the global candidate space and in the local candidate space, and plot the change of CS and LCS sizes across search iterations. As shown in Figure 6, there is large reduction of candidate nodes from CS to LCS, suggesting the importance of computing a smaller local candidate space based on the current match- ing and the selected uy. Without any LCS computation technique, the action space would be the global CS, which may contain up to 100, 000 nodes. Another important observation is that, the number of local candidate nodes varies dramatically across iterations. For example, in the initial iteration, since no nodes are matched, LCS is of the same size as CS, but as soon as one node pair is matched, the LCS computation can leverage the matched nodes by narrowing down the action space from all the nodes in CS to the first-order neighbors of the matched nodes. Existing LCS computation has several other techniques to reduce the candidate space size other than simply using the first-
20
10a
522 ofdee)
102
309
.C5
200
400
600
1300
Beration count
Figure 6: Demonstration of the sizes of global candidate space (CS) and local candidate space (LCS) across search it- erations, by running NSUBS on a ran- domly sampled graph pair from HPRD, and collecting the size CS and LCS at each search iteration. The y-axis is in the log scale. We stop recording the CS and LCS sizes after 1000 search iterations.
order neighbors of the matched subgraphs, and as a result, there can be less than 10 nodes in A.,, in some iterations. However, when the search backtracks to earlier state, there can be more candidate nodes in LCS, resulting in the varying LCS sizes across search.
The reduction of candidate space size from CS to LCS confirms the proposed usage of LCS to compute message passing between g and G, i.e the computation of M, and M." used in Equation The GMN model in contrast does not consider the state-dependent LCS, and uses all the quadratic node-node pairs the gross message passing mechanism, as explained in the ablation study (Section D.
D.3 PERFORMANCE ACROSS ITERATION
We show the number of solved pairs across search iterations in Figure 7, similar to Figure 2 except for the x-axis which is replaced with search iterations. It is noteworthy that all the methods
21

---

Under review as a conference paper at ICLR 2023
LDF
40
-0
NLF
GrashILL
Scbaed Paire
NLF
Selved Paira
NLF
Salved Pairs
150
15
TSO
BrushiQL
CPL
DP
DEC
12
DP-
MMatth
12
N5ud6
Nilttzh
Mitatch
Notto
100000 acticto su0cuc 400200 500000
50000
1000000
150000
500230
150000
(a) BA
(b) BRAIN
(c) HPRD
LDF
NLF
BrashQL
Sooved Parr
150
Solved Pairs
LPC
TSD
DP-50
NHatth
NS.1S
2010000
3c0000
4020C0
150000 J000iC 751000
2crionc
Berrtion
(d) COSMOS
(e) DBLP-S
( DBLP-L
LDF NLF
Saleed Pairs
GrashOL
Selved Pairs
GraphOL
GrashOL TSO
En-s0
ORL
10
NMatch
LEL1
16
N5ub6
kMazzn
KS.bs
0
1009
1000
2000
8020
530
1000
2000
2500
Iteration
Iteration
(g)
ETHE
(h) YT-S
(i) YT-L
Figure 7: The growth of the number of solved pairs across search iterations.
implemented under the search framework, and therefore the search iteration counting and measurement are consistent across the methods.
D.4 PERFORMANCE W.R.T. QUERY SIZES
We show the performance of each method under different query graph sizes for BA and HPRD. As shown in Table 4 and the difficulty of solving Subgraph Matching increases the query graph sizes increase. When the query graph only contains 8 nodes, all the methods can solve all the graph pairs under the 5 minutes time budget. However. as VV, increases to 128 nodes, all the methods fail to solve any graph pair, suggesting the room for improvement. In the main text, we report the results for V,, = 64, which is of moderate difficulty. Under other graph sizes, the proposed NSUBS performs either the best or very close to the best method highlighted in bold.
E RESULT VISUALIZATION
E. ILLUSTRATION OF SEARCH TRAJECTORY
We first show an animation of the actions selected by NSUBS across search in Figures 9 10, and 11. For each plot, we (1) find the search branch with the largest found subgraph across the search tree, then (2) plot the actions executed that search branch. For each action, we plot the resulting state, with the query graph on the left and target graph the right. For clarity, we do not plot the whole
22

---

Under review as a conference paper at ICLR 2023
Table 4: Solved percentage ("Sol%") and number of solutions ("#Sol") found by each method after minutes averaged by the number of the graph pairs in the BA dataset by varying IV, ("BA-IVgl")) For clarity and compactness, the number of solutions result has been divided by 1000, i.e. each number is in the unit of 10 For BA-128, since all the methods fail to solve any pair, we report the average ratio of largest match solution with respect to the query graph size denoted as "Ratio".
BA-8
BA-16
BA-32
BA-64
BA-128
Method
Sol%
#Sol
Sol %
#Sol
Sol %
#Sol
Sol%
#Sol
Sol%
Ratio
LDF
1.00
14.11
0.86
10.70
0.74
7.21
0.18
1.21
0.00
0.19
NLF
1.00
14.30
0.92
11.18
0.72
6.60
0.16
1.29
0.00
0.23
GRAPHQL
1.00
14.21
0.94
12.03
0.78
7.64
0.16
1.42
0.00
0.16
Tso
1.00
14.15
0.64
11.91
0.74
6.95
0.18
1.41
0.00
0.18
CFL
1.00
14.30
0.94
11.82
0.76
7.13
0.18
1.56
0.00
0.16
DP-ISO
1.00
14.27
0.94
11.71
0.82
7.35
0.18
1.31
0.00
0.17
CECI
1.00
14.00
0.92
11.57
0.72
6.91
0.16
1.21
0.00
0.17
NMATCI
1.00
14.55
0.88
11.35
0.66
6.18
0.14
1.02
0.00
0.14
NSUBS
1.00
13.06
1.00
12.01
0.98
8.27
0.62
2.37
0.00
0.35
Table 5: Performance of each method by varying [V/] ("HPRD-IV(I") for HPRD.
HPRD-8
HPRD-16
HPRD-32
HPRD-64
HPRD-128
Method
Sol%
#Sol
Sol %
#Sol
Sol%
#Sol
Sol%
#Sol
Sol%
Ratio
LDF
1.00
14.50
0.92
11.92
0.64
6.48
0.08
0.69
0.00
0.13
NLF
1.00
14.74
0.96
12.28
0.64
6.51
0.04
0.37
0.00
0.13
GRAPHQL
1.00
14.33
1.00
13.07
0.90
9.34
0.16
1.24
0.00
0.13
Tso
1.00
14.47
0.98
12.64
0.66
6.81
0.06
0.50
0.00
0.11
CFI.
1.00
14.44
0.94
12.12
0.58
5.63
0.02
0.18
0.00
0.11
DP-ISO
1.00
14.28
0.96
12.44
0.68
6.85
0.06
0.54
0.00
0.12
CECI
1.00
14.44
1.00
13.13
0.64
6.28
0.12
1,05
0.00
0.12
NMATCH
1.00
16.06
0.82
10.98
0.32
3.03
0.00
0.00
0.00
0.12
NSUBS
1.00
13.71
1.00
12.68
0.90
9.10
0.50
4.17
0.00
0.19
target graph, instead fixed percentage of one-hop and two-hop neighbors of that target graph. We make the following deductions based on the animations. The colors of nodes shows the mapping.
First, NSUBS tends to pick high degree nodes in the tar- get graph as shown in Figure This makes sense as every edge in the query must match some edge in the target. High degree nodes have more edges to satisfy this constraint. Existing works also find high correla- tion between static geometric representations and node degree (Lou al., 2020), indicating the geometric com- ponent of lookahead loss is working. A natural question then whether simple degree based policy would work equally well or even better than the proposed model. To confirm the necessity of learning- policy, we find that setting the raw output of policy to the degree of v, E A... Deg(e;), solves 36% of the pairs HPRD, which is worse than NSUBS yet better than many baselines as in Table Since existing baseline methods place focus improving node selection in q. i.e. the ordering method & for Vg, the selection of nodes in is random (Section 2.3). Our work is the first to improve selection from Ve, suggesting a new direction for tackling Subgraph Matching.
tau-0.641
250
000
00400
depres
230
200
30
Praw- ((M,, 0t) {s)))))
Q. @ddgroo
Figure 8: Correlation between node de- gree and the raw policy output before normalization learned by NSUBS. The Kendall's 7 coefficient (Kendall, 1938) between the two is shown on the top.
23

---

Under review as a conference paper at ICLR 2023
NSUBS tends map hub nodes in the query to hub nodes in the target. This suggests QC-SGMNN effectively captures structural properties the graph pair, as the model can look beyond hop neighborhoods to determine whether the node should be in hub or just a dangling high degree node.
NSUBS tends to map dangling degree one nodes in the query to low degree nodes in the target. This makes sense in the context of search, matching low degree query node to high degree target node means said higher degree target node cannot be matched later in search on query nodes with more constraints. This indicates the RL component of lookahead loss is working.
Figure 9: Illustration of the search trajectory on graph pair pair BA.
I
Figure 10: Illustration of the search trajectory graph pair pair of CosMOS.
E.2 VISUALIZATION OF SOLVED PAIRS
We show five instances of solved graph pairs by NSUBS in Figures 12, 13, 14, 15, 16. 17. 18 and 19. first plot (1) the query graph on its own, then plot (2) the query graph matched to the target graph, and finally plot (3) the target graph.
In other words, the first and second plots correspond to the same query graph but their node posi- tions/layouts different due different layouts. In the second plot fix the positions of nodes in q to match the positions of their matched nodes in G, i.c the nodes the second and the third plots have the same relative node positions for visualizing the node-node mapping. The colors of nodes
24

---

Under review as a conference paper at ICLR 2023
Figure 11: Illustration of the search trajectory on a graph pair pair DBLP.
for the purpose of visualizing the mapping. For clarity, we only show subgraph of G instead of the entire G as it contains too many nodes and edges to show. Specifically, we include the matched in G and grow the matched subgraph by including the first-order neighbors of the matched nodes.
Figure 12: Visualization of solved pair on BA.
Figure 13: Visualization of a solved pair on BRAIN.
25

---

Under review as a conference paper at ICLR 2023
Figure 14: Visualization of solved pair HPRD.
Figure 15: Visualization of a solved pair on COSMOS.
Figure 16: Visualization of a solved pair on DBLP.
26

---

Under review as a conference paper at ICLR 2023
Figure 17: Visualization of a solved pair on DBLP.
Figure 18: Visualization of a solved pair on ETHIE
Figure 19: Visualization of a solved pair on ETHE.
27


Reviews:
[{"review_id": "VzxV5fDhh_s", "reviewer": "Reviewer_181W", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the subgraph matching problem to perform a subgraph isomorphism check between a query graph and a large target graph. The authors attempt to solve the solution and reward sparsity issues by designing an encoder-decoder neural network and look-ahead loss function based on reinforcement learning. Experiments conducted on six datasets show the effectiveness.", "summary_of_the_review": "The paper proposes a reinforcement learning framework to solve the subgraph matching problem and designs an encoder and a decoder. The paper is technically sound but missed several related works and is not easy to follow. Also from my perspective, the methodology contribution is limited.", "strength_and_weaknesses": "Strengths:\n1. Detailed preliminary introduction to help the readers to understand the pipeline.\n2. The problem is not easy and deserves more attention.\n3. The proposed method is technically sound. \n\nWeaknesses:\n1. As far as I know, the related work for learning-based methods for subgraph matching is incomplete.\n2. The paper contains many notations and is hard to follow. Some preliminary knowledge could be moved to the Appendix because the main focus of this paper is on neural design.\n3. The methodology contribution is limited. Several works have adopted the idea of designing the encoder to encode two graphs and the design of the decoder is not novel.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Vbmn9fHcUm", "reviewer": "Reviewer_vmC2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper provides a reinforcement learning method for subgraph matching problem. Given a query graph, they attempt to find the subgraph from a large graph that matches a query graph. Then the paper compare the underlying method against several baselines on real world datasets.", "summary_of_the_review": "I have two key concerns with the paper. \nFirst, lack of powerful baselines. The paper acknowledges that most baselines are supervised learning methods. Thus, they adapted it into the RL method, which we appreciate. In this context, there are two powerful baselines which are never used:\n(1) https://arxiv.org/abs/1904.12787 and\n(2) https://ojs.aaai.org/index.php/AAAI/article/view/20784\n\nSecond, I really did not find any significant difference (of course there is some difference but they are not significant) from the approach adapted in https://arxiv.org/abs/2002.03129.\n\n", "strength_and_weaknesses": "Strengths:\n+ Important problem\n+ Intuitive approach\n\nWeakness:\n- Lack of well known baselines\n- Lack of novelty", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "SEVJoCfZ0zL", "reviewer": "Reviewer_HPUs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors presented a neural search method NSUBS to solve the subgraph search problem. The key idea is to pass information between the query and a local candidates pool at every search step to optimize the search. ", "summary_of_the_review": "I am willing to increase my score if the authors could address my questions and provides some more fair comparison and insights/limitations of the model.", "strength_and_weaknesses": "The paper is well-executed and easy to follow. All parts are clearly presented and convincing. Experiences are thoroughly done. \nThe key contribution also involves the dynamic message passing + a look-ahead loss to guide the RL to find the optimal order of search. \n\n1. It is great that the authors provided time complexity and empirically validated it via experiments. But It is unclear the training complexity. Especially with the look-ahead loss, do we have to add up many future steps to compute the loss at every step?\n2. It would be helpful in the experiments the authors could provide a total time for training the learnable models, including this model. For models that often get stuck in a local minimum and often do not improve further after the first 20-60 seconds (fig 2), would it be fair to restart them with some different random seeds and repeat them until 5min? \n3. I was a bit confused: does NSUBS also follow a general DFS + backtracking approach? If so, wouldn't it suffer from the local minimum problem as well? \n4. The authors claimed NSUBS works better at large query graphs. But the results section doesn't provide further performance stratifications on queries w. different sizes. It would strengthen the paper if the readers can see some breakdown numbers to better understand this claim. \n5. Related to 4, it would be helpful if the authors could have some effort into the model interpretation. For example, show an actual search trajectory and show how the NSUBS modifies the local candidate list to speed up and optimize the search. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "DxdSy0Uq2l", "reviewer": "Reviewer_AyD2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a learning based method for subgraph matching, using a graph neural network-based encoder-decoder architecture, and a reinforcement learning strategy. The GNN consists of two main modules: intra-graph message passing for modeling graph structures, and inter-graph message passing for query-graph matching. Furthermore, a look-ahead loss is formulated to supplement training signals.", "summary_of_the_review": "Overall I think the weaknesses slightly overweigh the strengths.\n\n---\n\nUpdate: I'm largely satisfied with the responses, except for the initial overhead. The cost of executing NNs is part of the cost, which cannot be simply discounted. Overall, i will upgrade my score.", "strength_and_weaknesses": "Strengths:\n1. The idea of inter-graph message passing for matching is novel to me. Existing GNN architectures only focus on the intra-graph counterpart.\n\n2. The use of reinforcement learning can reduce or eliminate labeling effort. \n\n\n\nWeaknesses:\n1. There is a large body of literature on the related subgraph isomorphism counting problem. In many applications, the profile of subgraph counts can sufficiently characterize a graph and it is not necessary to find all or most instances of the query.  Discussing some case studies and example applications could be useful to motivate why it is necessary beyond counting. \n\n2. The proposed model has high initial overhead. The methods only show significant advantage after a few mins. However, in many cases it might be important to get a few matching instances fast rather than getting many instances later on. \n\n3. Some parts are not well explained in detail.\n- 3.1: \"We define our reward as R(+) = 1 if the subgraph is fully matched and R(−) = 0 otherwise.\" Do you actually mean the \"current\" subgraph is fully matched?\n- 3.1: \"Therefore, after the search, we collect the positive training signals at each state as all the node-node pairs (u, v) that lead to a solution\" I'm not clearly how this is exactly done. A step-by-step explanation might be useful.\n- 3.2.1: How are the mapping M, M' are constructed? Again, a step-by-step instruction might be clearer.\n\nMinor issues:\nThe ablation study is important and should be moved to the main paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject