Neural Subgraph Matching
Authors: Zhitao Ying
Andrew Wang
Jiaxuan You
Chengtao Wen
Arquimedes Canedo
Jure Leskovec
Venue:  (2021)
Keywords: Graph neural networks
Subgraph matching
Order Embedding

Abstract: Subgraph matching is the problem of determining the presence and location(s) of a given query graph in a large target graph. 
Despite being an NP-complete problem, the subgraph matching problem is crucial in domains ranging from network science and database systems to biochemistry and cognitive science. 
However, existing techniques based on combinatorial matching and integer programming cannot handle matching problems with both large target and query graphs.
Here we propose NeuroMatch, an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch decomposes query and target graphs into small subgraphs and embeds them using graph neural networks. Trained to capture geometric constraints corresponding to subgraph relations, NeuroMatch then efficiently performs subgraph matching directly in the embedding space. Experiments demonstrate NeuroMatch is 100x faster than existing combinatorial approaches and 18% more accurate than existing approximate subgraph matching methods.

Under review as a conference paper at ICLR 2021
NEURAL SUBGRAPH MATCHING
Anonymous authors Paper under double-blind review
ABSTRACT
Subgraph matching is the problem of determining the presence of a given query graph in a large target graph. Despite being an NP-complete problem, the subgraph matching problem is crucial in domains ranging from network science and database systems to biochemistry and cognitive science. However, existing techniques based combinatorial matching and integer programming cannot handle matching problems with both large target and query graphs. Here we propose NeuroMatch, an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch decomposes query and targel graphs inlo small subgraphs and embeds them using graph neural networks. Trained to capture geometric constraints corresponding to subgraph relations, NeuroMatch then efficiently performs subgraph matching directly in the embedding space. Experiments demonstrate that NeuroMatch is 100x faster than existing combinatorial approaches and 18% more accurate than existing approximate subgraph matching methods.
1. INTRODUCTION
Given query graph, the problem of subgraph isomorphism matching is to determine if a query graph is isomorphic to a subgraph a large target graph. If the graphs include node and edge features, both the topology well as the features should be matched.
Subgraph matching is a crucial problem in many biology, social network and knowledge graph applications (Gentner, 1983; Raymond al., 2002; Yang & Sze, 2007; Dai et al., 2019). For example, in social networks and biomedical network science, researchers investigate important subgraphs by counting them in a given network (Alon al., 2008). In knowledge graphs, common substructures are extracted by querying them in the larger larget graph (Gentner, 1983; Plotnick, 1997).
Traditional approaches make use of combinatorial search algorithms (Cordella al., 2004; Gallagher, 2006; Ullmann, 1976). However, they do not scale to large problem sizes due to the NP-complete nature of the problem. Existing efforts to scale up subgraph isomorphism (Sun et al., 2012) make use of expensive pre-processing store locations of many small 2-4 node components, and decompose the queries into these components. Although this allows matching to scale to large target graphs, the size of the query cannot scale to more than few tens of nodes before decomposing the query becomes a hard problem by itself.
Here we propose Neuro.atthh, an efficient neural approach for subgraph matching. The core of NcuroMatch is to decompose the target GT as well as the query Go into many small overlapping graphs and use Graph Neural Network (GNN) to embed the individual graphs such that can then quickly determine whether one graph is a subgraph of another.
Our approach works in two stages, an embedding stage and query stage. At the embedding stage, we decompose the target graph GT into many sub-networks G, For every node u E Gr we extract k-hop sub-network G, around u and use GNN to obtain an embedding for u, capturing the neighborhood structure of u. At the query stage, we compute embedding of every node in the query graph Go based on g's neighborhood. We then compare embeddings of all pairs of nodes q and determine whether GQ is subgraph of GT.
The key insight that makes NeuroMatch work is define an embedding space where subgraph rela- tions are preserved. We observe that subgraph relationships induce a partial ordering over subgraphs. This observation inspires the use of geometric set emheddings such as order embeddings (McFee & Lanckriet, which induce a partial ordering embeddings with geometric shapes. By ensuring that the partial ordering on embeddings reflects the ordering on subgraphs, we equip our model with

---

Under review as a conference paper at ICLR 2021
Target graph
2-hop mode subgraphs Ga
Embedding space with subgraph constraints
Center node subgraphs
Query 6g
Query
hep odge
Query Stage
Rinheddling
layers
layers
Figure I: Overview of NeuroMatch. We decompose target graph Gr by extracting k-hop neighbor- hood G. around at every node u. We then use a GNN embed each G. (left). We refer to u as the center node of G.. We train the GNN to reflect the subgraph relationships: If G, is subgraph of Gu. then node v should be embedded to the lower-left of u. For example, since the 2-hop graph of the violet node is a subgraph of the 2-hop graph of the red node, the embedding of the violet square to the lower-left of the red square node. At the query stage, we decompose the query G2 by picking anchor node g and embed it. From the embedding itself we can quickly determine that Query 1 is a subgraph of the neighborhood around red, blue, and green nodes in target graph because its embedding is to the lower-left of them. Similarly, Query 2 is subgraph of the purple and red nodes and is thus positioned to the lower-left of both nodes. Notice NeuroMatch avoids expensive combinatorial matching of subgraphs.
powerful set of inductive biases while greatly simplifying the query process. Our work differs from many previous works (Bai et al., 2019; Li et al., 2019; Xu et al., 2019) that embed graphs into vector spaces, which do not impose geometric structure in the embedding space. In contrast, order embed- dings have properties that naturally correspond to many properties of subgraph relationships, such as transitivity, symmetry and closure under intersection. Enforcing the order embedding constraint both leads to a well-structured embedding space and also allows us to efficiently navigate it in order to find subgraphs as well as supergraphs (Fig. 1).
MauroMatch trains a graph neural network to learn the order embedding, and uses a max- max-ma loss to ensure that the subgraph relationships are captured. Furthermore, the embedding stage can be conducted offline, producing precomputed embeddings for the query stage. The query stage is extremely efficient due to the geometric constraints imposed at training time, and it only requires linear time both in the size of the query and the target graphs. Lastly, NcuroMatch can naturally operate on graphs which include categorical node and edge features, as well as multiple target graphs.
We compare the accuracy and speed of NeuroMatch with state-of-the of-thh--rt exact and approximate methods for subgraph matching (Cordella et al., 2004; Bonnici et al., 2013) as well as recent neural methods for graph matching, which adapted to the subgraph matching problem. Experiments show that NeuroMatch runs two orders of magnitude faster than exact combinatorial approaches and can scale larger query graphs. Compared neural graph matching methods, NeuroMatch achieves an 18% improvement in AUROC for subgraph matching. Furthermore, we demonstrate the generalization of NeuroMatch, by testing on queries sampled with different sampling strategies. and transferring the model trained on synthetic datasets to make subgraph predictions on real datasets.
2. NEUROMATCH ARCHITECTURE
2. PROBLEM SETUP
We first describe the general problem of subgraph matching. Let Gr (Vr, ET) be a large target graph where we aim to identify the query graph. Let X be the associated categorical node features for all nodes in Vl, Let GQ (Vq, EQ) be a query graph with associated node features XQ. The goal of a subgraph matching algorithm is to identify the set of all subgraphs 7. H H C GT that isomorphic to Go, that is, 3 bijection Furthermore, we say Go is a subgraph of Gr H. is non-empty. When node and edge features are present, the subgraph isomorphism further requires that the bijection has match these features.
Vи + Vo such that (f(u), f(u) Eq iff (v, u) EØ-
We consider the case of a single target and query graph, but NeuroMatch applics any number target/query graphs. We also assume that the query is connected (otherwise can be easily split into 2 queries).

---

Under review as a conference paper at ICLR 2021
Algorithm 1: NeuroMatch Query Stage
Input: Target graph Gr, graph embeddings Zu of node u E Gr, and query graph Gq-
Output: Subgraph of GT that is isomorphic to Gq.
1: For every node q E Go, create Gg. and embed its center node q.
2: Compute matching between embeddings Z, and embeddings ZT using subgraph prediction function fzg Zu).
3: Repeat for all 9 C Gq, u E GT; make prediction based the average score of all {zg zw)-
In the literature, subgraph matching commonly refers to two subproblems: node-induced matching and edge-induced matching. In node-induced matching, the set of possible subgraphs of GT are restricted to graphs H = (VH, Eн) such that Vи S Vr and Еμ - {uu, u)|u, E VH, (u, v) E Er}. Edge-induced matching. in contrast, restricts possible subgraphs by Eи S Er, and contains all nodes that are incident to edges in Eн. To demonstrate, here we consider the more general edge-induced matching, although NeuroMatch can be applied to both.
In this paper, we investigate the following decision problems of subgraph matching. Problem 1. Matching query to datasets. Given a larget graph GT and a query Gq, predict if Go is isomorphic to a subgraph of GT.
We use neural model to decompose Problem 1 and solve (with certain accuracy) the following neighborhood matching subproblem.
Problem 2. Matching neighborhoods. Given a neighborhood G. around node u and query Go anchored at node q. make binary prediction of whether Gg is a subgraph of Gv where node q corresponds to u.
Here we define anchor node q E Gq. and predict existence of subgraph isomorphism mapping that also maps g to u. At prediction time, similar to (Bai et al., 201 8), we compute the alignment score that measures how likely Go anchored at g is subgraph of Gu, for all q E Gq and E G.. and aggregate the scores to make the final prediction to Problem 1.
2.2. OVERVIEW OF NEUROMATCH
NeuroMatch adopts a stage process: embedding stage where Gr is decomposed into many small overlapping graphs and each graph is embedded. And the query stage where query graph is compared to the target graph directly in the embedding space no expensive combinatorial search is required.
Embedding stage. In the embedding stage, NeuroMatch decomposes target graph Gr into many small overlapping neighborhoods G and uses graph neural network embed them. For every node u in GT, we extract the k-hop neighborhood of u, G. (Figure 1). GNN then maps node u (that is, the structure of its network neighborhood G.)) into an embedding Zu-
Note subtle but an important point: By using k-layer GNN to embed node we are essentially embedding/capturing the k-hop network neighborhood structure G. around the center node u. Thus, embedding и is equivalent to embedding G, (a k-hop subgraph centered at node u)), and by comparing embeddings of two nodes u and v, we are essentially comparing the structure of subgraphs Gu,, G.
Query stage (Alg. 1). The goal of the query stage is to determine whether CQq is subgraph of GT and identify the mapping of nodes of Go to nodes of GT. However, rather than directly solving this problem, we develop fast routine to determine whether G, is subgraph of G,; We design a subgraph prediction function f( z.) that predicts whether the Go anchored at q E GQ is a subgraph of the k--hpp neighborhood of node Gr, which implies that q corresponds to in the subgraph isomorphism mapping by Problem 2. We thus formulate the subgraph matching problem as node-level task by using f(z =u) predict the set of nodes u that can be matched node q (that is, find a set of graphs G. that are super-graphs of G.y) To determine wither Go is subgraph of Gr. we then aggregate the alignment matrix consisting of f(z, zw) for all q E GQ and u E Gr make the binary prediction for the decision problem of subgraph matching.
Practical considerations and design choices. The choice of the number of layers, depends on the size of the query graphs. We assume k is at least the diameter of the query graph, to allow the information of all nodes to be propagated to the anchor node in the query. experiments, we observe that inference via voting can consistently reach peak performance for k = 10, due to the soall-world property of many real-world graphs.

---

Under review as a conference paper at ICLR 2021
NeuroMatch is flexible in terms of the GNN model used for the embedding step. We adopt variant of GIN (Xu et al., 2018) incorporating skip layers to encode the query graphs and the neighborhoods, which shows performance advantages. Although GIN showed limitation in expressive power beyond WL test, our GNN additionally uses feature to distinguish anchor nodes, which results in higher expressive power in distinguishing d-regular graphs, beyond WL test (see Limitation Section and Appendix I).
2.3.
SUBGRAPH PREDICTION FUNCTION f(g (a))
Given the target graph node embeddings 2n and the center node q E Gq, the subgraph prediction function decides if GT has k-hop neighborhood that is subgraph isomorphic to q's k-hop neighborhood in Gq- The key is that subgraph prediction function makes this decision based only on the embeddings By and zn of nodes q and (Figure 1).
Capturing subgraph relations in the embedding space. We enforce the embedding geometry to directly capture subgaph relations. This approach has the additional benefit of ensuring that the subgraph predictions have negligible cost at the query stage, since we can just compare the coordinates of two node embeddings. In particular, NeuroMatch satisfies the following properties for subgraph relations (Refer to Appendix A for proofs of the properties):
Transitivity: If G1 a subgraph G2 and G2 a subgraph of G3, then G1 a subgraph of G3- Anti-symmetry: If G is subgraph of G2, G2 is subgraph of G1 iff they are isomorphic.
Intersection set: The intersection of the set of G1 's subgraphs and the set of G2 ' subgraphs contains all common subgraphs of G1 and G2.
Non-trivial intersection: The intersection of any two graphs contains at least the trivial graph.
Wc use the notion of set embeddings (McFee & Lanckriet, 2009) to capture these inductive biases. Common examples include order embeddings and box embeddings. In contrast to Euclidean point embeddings, set embeddings enjoy properties that correspond naturally to the subgraph relationships.
Subgraph prediction function. The idea of order embeddings is illustrated in Figure 1. Order embeddings ensure that the subgraph relations are properly reflected in the embedding space: if G, is a subgraph of Gu, then the embedding 2n of node has to be to the "lower-left" of u's embedding z.:
Eq [0] < z livE
iff Gy C.C.G G.
(1)
where is the embedding dimension. We thus train the GNN that produces the embeddings using the max margin loss:
L(zg: Zu)
Σ (FE
B(Eg: zu) +
Σ max(0,e a ElZzg zu)}, where
(2)
(AN
E(zg: zy) = max - 2031
(3)
Here P denotes the set of positive examples in minibatch where the neighborhood of q is subgraph of neighborhood of and N denotes the set of negative examples. A violation of the subgraph constraint happens when in any dimension i, [ > z,. [. [1) and E(zy, z..) represents its magnitude. For positive examples P, E( =u) is minimized when all the elements in the query node embedding
Zg are less than the corresponding elements in target node embedding 2.. For negative pairs (Zy. zu) the amount of violation E(zy, zu) should be at least a, in order to have zero loss.
We further use a threshold on the violation E(zy, zu) to make decision of whether the query is a subgraph of the target. The subgraph prediction function f is defined as:
flz = {
iff E(zy, zw) < t
(4)
otherwise
2.4. MATCHING NODES VIA VOTING
At the query time, our goal is to predict if query node 9 E Go and target node u E Gr have subgraph-isomorphic k-hop neighborhoods G, and G. (Problem 2). A simple solution is to use the subgraph prediction function [zz, z.)) to predict the subgraph relationship between G, and Gy,
Matching via voting. We further propose voting method that improves the accuracy of matching a pair of anchor nodes based on their neighboring nodes. Our insight is that matching a pair of anchor

---

Under review as a conference paper at ICLR 2021
nodes imposes constraints on the neighborhood structure of the pair. Suppose we want to predict if node E Go and node v. E Gr match. We have (proof in Appendix C): Observation Let N (u) denote the k-hop network neighborhood node u. Then, if q E G and node u E G. match, then for all nodes i E ((*) (q), 3 node j E (N) S such that node i and node j match.
Based on this observation, we propose a voting- inference method. Suppose that node q E Go matches node Gr. We check if all neighbors of node satisfy Observation 1, i.c. each neighbor of has a match to neighbor of u, as summarized in Appendix Algorithm 2.
2.5. TRAINING NEUROMATCH
The training of subgraph matching consists of the following component: (1) Sample training query Go from target graph GT. (2) Sample node q and neighborhood G, in Go and find q'ss corresponding node and its G S Gr. (3) Generate negative example and its Gw S Gr. (4) Compute node embeddings for q, u, w with GNN, and the loss in Equation 2 for backprop. We now detail the following components in this training process.
Training data. To achieve high gencralization performance on unseen queries, we train the network with randomly generated query graphs. We sample a positive pair, sample G₁ Gr, and Gg E Gu- To sample G.,, we first selecting a node u E Gr, and perform a random breadth-first traversal (BFS) of the graph. The sampler traverse each edge in BFS with fixed probability. We then sample Gg by performing the same random BFS traversal on G, starting at u, and treat u as the anchor in Gq. which ensures existence of subgraph isomorphism mapping that maps q to u.
Given positive pair (G,, G.), wc generate 2 types of negative examples. The first type of negative examples are created by randomly choosing different nodes u and 9 GT and perform random traversal. The second type of negatives are generated by perturbing the query to make it no longer a subgraph of the target graph, which is a more challenging case for the model to distinguish.
Test data. To demonstrate generalization, we use 3 different sampling strategies to generate test queries. Aside from the mentioned random BFS traversal, we further use the random walk sampling by performing random walk with restart at u, and the weighted sampling strategy used in the motif mining algorithm MFinder (Cho et al., 2013). Experiments demonstrate that NeuroMatch can generalize to test queries with different sampling strategics.
Curriculum.
Query Example for each Curriculum Level
We introduce curriculum training scheme that im- proves performance. We first train the model on a small number of easy queries and then train cessively more complex queries with increased batch size. Initially the model is trained with a single hop query. Each time the training performance platcaus, the model samples larger queries. Figure/ shows examples of queries at each curriculum level. The complexity of queries increases as training proceeds.
Figure 2: Example sampled queries Go at each level of the curriculum in the MSRC_ 21 dataset. The diameter and number of nodes increase curriculum level advances.
2.6. RUNTIME COMPLEXITY
The embedding stage uses GNNs to train embeddings to obey the subgraph constraint. Its complexity + ((K(Er)
(El)); where K the number of GNN layers. In the query stage, solve Problem I we need to compute a total of V ([V))) scores. The quadratic time complexity allows NeuroMatch to scale to larger datasets, whereas the complexity of the exact methods grow exponentially with size.
In many use cases, the target graphs are available in advance, but we need to solve for new incoming unseen queries. Prior to inference time, the embeddings for all nodes in the target graph can be pre-computed with complexity OrK)rr)) For a new query, its node embeddings can be computed in (({ EEl) time, which is much faster since queries are smaller. With order embedding, we do not need additional neural network modules at query stage and simply compute the order relations between query node embeddings and the pre-computed node embeddings in the target graph.
3. EXPERIMENTS
To investigate the effectiveness of NeuroMatch, we compare its runtime and performance with a range of existing popular subgraph matching methods. We evaluate performance on synthetic datasets
5

---

Under review as a conference paper at ICLR 2021
Dulaset
SYNTHETIC
COX2
DD
MSRC_21 211
FIRSTMMDB
PPI
WORDNET18
Ablaton Bosc
GMNN (Xa et al., 2019)
73.6 +: 1.1
75.9 :: 0.8
80.6
1.5
82.5 # 1.7
81.5 = 2.9
72.0 :: 1.9
80.3 = 2.0
RDGCN (Wa et 2019)
79.5 1.2
80.1
0.4
81.3 +: 1.2
81.9
1.9
82.4 + 3.4
76.8
2.2
79.6 + 2.5
No CURRICULUM
95.0 0.6
96.7
2.1
89.22.0
67
82.6
1.7
81.4 = 2.2
NM-MLP
88.7 0.5
95.4 1.6
97.1
0.3
93.5
1.0
93
85.5
14
86.3 0.9
NM-NIN
89.1 1.9
8.
96.4
14
94.7
0 3.2
89.6 1.1
85.7
2.4
85.0
1.1
NM-BoX
84.5
88.5 1.2
914
90.8
1.4
93.1 1.7
77.4
82.7
2.5
NEUROMATCH
93.52 1.1
97.2 = 0.4
97.9
11991. 1.3
96.1 = 0.2
95.5 = 2.1
89.9 =
1.9
89.3 = 2.4
IMPROVEMENT
Table 1: Given neighborhood G. of and query Go containing 4, make binary prediction of whether C. is a subgraph of C, where node q corresponds to u. We report AUROC (unit 0.01). NeuroMatch performs the best with median AUROC 95.5, 20% higher than the neural baselines.
to probe data efficiency and generalization ability, as well as a variety of real-world datasets spanning many fields evaluate whether the model can be adapted to real-world graph structures.
3.1. DATASETS AND BASELINES
Synthetic dataset. We use synthetic dataset including Erdōs-Rényi (ER) random graphs (Erdös & Rényi, 1960) and extended Barabasi graphs (Albert & Barabási, 2000). At test time, we evaluate on test query graphs that were seen during training. See Appendix for dataset details, where we also show experiments to transfer the learned model to unseen real dataset without fine-tuning.
Real-world datasets. We use a variety of real-world datasets from different domains. We evaluate on graph benchmarks in chemistry (COX2), biology (Enzymes, DD, PPI networks), image processing (MSRC_ 21), point cloud MFRRSTMMDB), and knowledge graph (WORDNET15) 8). We do not include node features for PPI networks since the goal is to match various protein interaction patterns without considering the identity of proteins. WORDNET18 contains no node features, but we use its edge types information in matching. For all other datasets, require that the matching takes categorical features of nodes into account. Refer to the Appendix for statistics of all datasets.
Baselines. We first consider popular existing combinatorial approaches. We adopt the most com- monly used efficient methods: the VF2 (Cordella et al., 2004) and the RI algorithm (Bonnici et al., 2013). We further consider popular approximate matching algorithms FastPFP (Lu et al., 2012) and IsoRankN (Liao et al., 2009), and compare with neural approaches in terms of accuracy and runtime.
Recent development of GNNs has not been applied subgraph matching. We therefore adapt two recent state-of- of-th-of-the-art methods for graph matching, Graph Matching Neural Networks (GMNN) (Xu al., 2019) and RDGCN (Wu al., 2019), by changing their objective from predicting whether two graphs have a match to predicting the subgraph relationship. Both methods are computationally more expensive than NeuroMaich due to gross-graph attention between nodes.
Training details. We use the epoch with the best validation result for testing. See Appendix D for hardware and hyperparameter configurations.
3.2. RESULTS
(1) Matching individual node network neighborhoods (Problem 2). Table I summarizes the AUROC results for predicting subgraph relation for Problem 2: is node q's k-hop neighborhood Gj a subgraph of u's neighborhood G,, This is a subroutine to determine is a query present in large target graph. The number of pairs Gg., G. with positive labels is equal to the number of pairs with negative labels. We observe that NeuroMatch with order embeddings obtains, on average, a 20% improvement over neural baselines. This benefit is result of avoiding the loss of information when pooling node embeddings and a better inductive bias stemming from order embeddings.
(2) Ablation studies. Although learning subgraph matching has not been extensively studied, we explore alternatives to components of NeuroMatch. We compare with the following variants:
No CURRICULUM: Same NEUROMATCH but with curriculum training scheme. NM-MLP: uses MLP and cross entropy to replace the order embedding loss.
NM-NTN: uses Neural Tensor Network (Socher et al., 2013) and cross entropy replace order embedding loss.
NM-BoX: uses box embedding loss (Vilnis al., 2018) to replace the order embedding loss.

---

Under review as a conference paper at ICLR 2021
Dataset
COX2
DD
MSRC_21
FIRSTMMDB
ENZYMES
SYNTHETIC
Avg Runtime
ISORANEN
72.1 = 2.5
61.2 + 1.3
67.0 = 2.0
77.0 2.3
50.4
62.7 =
1.45 0.04
FASTPFP
63.2 1: 3.8
72.9 4: 111
83.5 1: 1.5
8300 1.5
76.6 :: 1.9
77.0 2.0
0.56 0.01
NM-MLP
7.0
87.8
+ 1.5
74.2 1.0
88.9
87.9 = 1.0
92.1 0.5
1.29 = 0.10
NEUROMATCH
89.9 1.1
95.7
15.7
84.5
- 1.5
019:10 1.0
92.9
75.2
0.90 0.09
Table 2: Given query Go and target graph GT from a dataset, make binary prediction for whether Go is a subgraph of Gr (the decision problem of subgraph isomorphism), in AUROC (unit: 0.01).
As shown in Table 1, box embeddings cannot guarantee intersection, i.e. common subgraphs, between two graphs, while variable sizes of the target graph makes neural tensor network (NTN) variant hard to learn. Neuro.atch outperforms all the variants.
We additionally observe that the learning curriculum is crucial to the performance of learning the subgraph relationships. The use of the curriculum increases the performance by an average of 6%, while significantly reducing the performance variance and increasing the convergence speed. This benefit is due to the compositional nature of the subgraph matching task.
3) Matching query to target graph (Problem 1). Given a target Gr, we randomly sample a query Go centered at g. The goal is to answer the decision problem of whether Go is a subgraph of Gr- Unlike the previous tasks, it requires prediction of subgraph relations between Go and neighborhoods G for all u Gr. We perform the tasks by traversing over all nodes in query graph, and all nodes in target graph as anchor nodes, and outputs an aligmment matrix A of dimension Vrrl (V/ol, where A denotes the matching score f(z,, žj), as illustrated in Algorithm 1. The performance trend of Table 1 also holds here in Problem 1. We further compare Mauho.atch with high-performing hueristic methods, FastPFP and IsoRankN, and show an average of 18. 18.4% improvement in AUROC over all datasets. Appendix D contains additional implementation details.
Additionally, we make the task harder by sampling test queries with a different sampling strategy, At training time, the query is randomly sampled with the random BFS procedure, whereas at test time the query randomly sampled using sgrree-weighted sampling (see Section 2.5).
We further compute the statistics of query graphs and target graphs (in Appendix E). On average across all datasets, the size of query 51% of the size of the target graphs, indicating that the model is learning the problem of subgraph matching in data-driven way, rather than learning graph isomorphism, which previous works focus on.
4) Generalization. We further conduct experiments to demonstrate the generalization of MauroMatch.
Firstly, we investigate model generalization to un- seen subgraph queries sampled from different distri- butions. We consider sampling strategies: random BFS, degree- sampling (see Section 2.5). Table shows the perfor- mance of NeuroMatch when trained with examples sampled with one strategy (rows), and tested with examples sampled with another strategy (columns). We observe that Matro can generalize to queries generated with different sampling strategies, without much performance change. Among strategies considered, random BFS the most robust sampling strategy for training.
BFS
MFinder
Random Walks
BFS
9K.79
58
98.38
MFinder
93.09
96.34 34
96.07
sampling and random walk
Random Walks 95.65
97.21
97.53
Table 3: Generalization to new sampling methods for MSRC dataset. Performance measured in AUROC (unit 0.01).
Secondly, we investigate whether the model is able to generalize to perform matching on pairs of query and target that are from variety of datasets, while only training on synthetic dataset. In Appendix F, we similarly find that NeuroMatch robust to test queries sampled from different real-world datasets.
Order embedding space analysis. Figure 3 shows the TSNE embedding of the learned order embedding space. The yellow color points correspond to embeddings of graphs with larger sizes; the purple color points correspond to embeddings of graphs with smaller sizes. Red points are example embeddings for which we also visualize the corresponding graphs. We observe that the order constraints are well-preserved. We further conduct experiment by randomly sampling 2 graphs in the dataset and test their subgraph relationship. NeuroMatch achieves 0.61 average precision, compared to 0.35 with the NM-MLP baseline.
Comparison with exact methods.

---

Under review as a conference paper at ICLR 2021
Although exact methods always achieve the correct answer, they take exponential time in worst case. We the exact methods VF2 and RI and record the av- erage runtime, using exactly the same lest queries and target as in Table 2. If the subgraph matching runs for more than 10 minutes, it is deemed as unsuccess- ful. We show Appendix F the runtime comparison showing 100 times speedup with NeuroMatch, and the figure of the success rate the baselines, which drop below 60% when the query size is more than 30. As query size grows, the runtime of the exact methods grow exponentially, whereas the runtime of NeuroMatch grows linearly. Although VF2 and RI exact algorithms, NeuroMatch shows the poten-
AsB
Asc
A
cct
CEF
Figure 3: TSNE visualization of order embed- ding for a subset of subgraphs sampled from the ENZYMES dataset. As seen by examples to the right, the order constraints are well- preserved. Graphs are colored by number of edges.
tial of learning to predict subgraph relationship. in applications requiring high-throughput inference. Additionally, NeuroMatch is also 10 times more efficient than the other basclines such NM-MLP and GMNN due to its efficient inference using order embedding properties.
4. LIMITATIONS
NeuroMatch provides a novel approach to demonstrate the promising potential of GNNs and geomel- ric embeddings to make predictions of subgraph relationships. However, future work is needed in exploring neural approaches to this NP-Complete problem. Previous works (Xu et al., 2018) have identified expressive power limitations of GNNs in terms of the WL graph isomorphism test. In NeuroMatthh we alleviate the limitation by distinguishing between the anchor node via node features (illustrated Appendix H). Since NeuroMatch does not explicitly rely on GNN backbone, future work more expressive GNNs can be directly applied to NeuroMatch. We hope that NeuroMatch opens a new direction in investigating subgraph matching as a potential application and benchmark in graph representation learning.
5. RELATED WORK
Subgraph matching algorithms. Determining a query is a subgraph of a target graph requires comparison of their structure and features (Gallagher, 2006). Conventional algorithms (Ullmann, 1976) focus on graph structures only. Other works (Aleman-Med) et al., 2005; Coffman et al., 2004) also consider categorical node features. Our NeuroMatch model can operate under both settings. Approximate solutions to the problem have also been proposed (Christmas et al., 1995; Umeyama, 1988) NeuroMatch is related in sense that it is an approximate algorithm using machine learning. We further provide detailed comparison with a survey of heuristic methods (Ribeiro et al., 2019).
Neural graph matching. Earlier work (Scarselli al., 2008) has demonstrated the potential of GNN in small-scale subgraph matching, showing advantage of GNN over feed forward neural networks. Recently, graph neural networks (Kipf & Welling, 2017; Hamilton al., 2017; Xu et al., 2018) have been proposed for graph isomorphism (Bai et al., 2019; Li et al., 2019; Guo et al., 2018) and have achieved state-of-the-art results (Zhang Lee, 2019; Wang et al., 2019 Xu al., 2019). However, these methods cannot be directly employed in subgraph isomorphism since there is no one-to-one correspondence between nodes query and target graphs. We demonstrate that our contributions using node-based representations, order embedding space can significantly outperform applications of graph matching methods in the subgraph isomorphism setting. Additionally, recent works (Bai et al., 2018; Fey et al., 2020) provide solutions to compute discrete matching correspondences from the neural prediction of isomorphism mapping and are complementary to our work.
6. CONCLUSION
In this paper we presented a neural subgraph matching algorithm, NeuroMatch, that uses graph neural networks and geometric embeddings to learn subgraph relationships. We observe that order embeddings are natural fit to model subgraph relationships in embedding space. NeuroMatch out- performs adaptations of existing graph-isomorphism related architectures and show advantages and potentials compared to heuristic algorithms.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Réka Albert and Albert-László Barabási. Topology evolving networks: local events and universality. Physical review letters, 85(24):5234, 2000.
Boanerges Aleman-Meza, Christian Halaschek--Wenen Satya Sanket Sahoo, Amit Sheth, and Budak Arpinar. Template based semantic similarity for security applications. International Conference on Intelligence and Security Informatics. Springer, 2005.
Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S Cenk Sahinalp. Biomolccular network motif counting and discovery by color coding. Bioinformatics, 2008.
Yunsheng Bai, Hao Ding, Yizhou Sun, and Wei Wang. Convolutional set matching for graph similarity. In NeurlPS, 2018
Yunsheng Bai, Hao Ding. Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In WSDM ACM, 2019.
Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. subgraph isomorphism algorithm and its application biochemical data. BMC bioinformatics, 2013.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In NeurIPS, 2019.
Roeng-Rae Cho, Marco Mina, Yanxin Lu, Nayoung Kwon, and Pietro H Guzzi. M-finder: Uncovering functionally associated proteins from interactome data integrated with go annotations. Proteome science, 2013.
William Christmas, Josef Kittler, and Maria Petrou. Structural matching in computer vision using probabilistic relaxation. PAMI, 1995.
Thayne Coffman, Seth Greenblatt, and Sherry Marcus. Graph-based technologies for intelligence analysis. Communications of the ACM, 2004.
Luigi Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. (sub) graph isomorphism algorithm for matching large graphs. PAMI, 2004.
Hanjun Dai, Chengtao Li, Comnor Coley, Bo Dai, and Le Song. Retrosynthesis prediction with conditional graph logic network. In NeuriPS, 2019.
Paul Erdōs and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 1960.
Matthias Fey, Jan E. Lenssen, Christopher Morris, Jonathan Masci, and Nils M. Kriege. Deep graph matching consensus. In ICLR, 2020.
Brian Gallagher. Matching structure and semantics: A survey on graph- pattern matching. In AAAI Fall Symposium, 2006.
Dedre Gentner. Structure-mapping: A theoretical framework for analogy. Cognitive science, 1983.
Michelle Guo, Edward Chou, De-An Huang, Shuran Song, Serena Yeung, and Li Fei-Fei. Neural graph matching networks for fewshot 3d action recognition. ECCV, 2018.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeuriPS, 2017.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In ICML, 2019.
Chung-Shou l Liao, Kanghao Lu, Michael Baym, Rohit Singh, and Bonnie Berger. Isorankn: spectral methods for global alignment of multiple protein networks. Bieinformatics, 2009.

---

Under review as a conference paper at ICLR 2021
Yao Lu, Kaizhu Huang, and Cheng-Lin Liu. A fast projected fixed-point algorithm for large graph matching. arXiv preprint arXiv:/207.11 2012.
Brian McFee and Gert Lanckrict. Partial order embedding with multiple kernels. In ICML. ACM, 2009.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, pp. 4602-4609, 2019.
Eric Plotnick. Concept mapping: A graphical system for understanding the relationship between concepis. ERIC Clearinghouse on Information and Technology Syracuse, NY, 1997.
John W Raymond, Eleanor Gardiner, and Peter Willett. Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm. Journal of chemical information and computer sciences, 2002.
Pedro Ribciro, Pedro Paredes, Miguel EP Silva, David Aparicio, and Fernando Silva. A survey on subgraph counting: concepts, algorithms and applications to network motifs and graphlets. arXiv preprint ArXiv:/910. /3011, 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 2008
Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Ng. Reasoning with neural tensor networks for knowledge base completion. In NeurIPS, 2013.
Zhao Sun, Hongzhi Wang, Haixun Wang, Bin Shao, and Jianzhong Li. Efficient subgraph matching on billion node graphs. Proceedings of the VLDB Endowment, 2012.
Julian R Ullmann. An algorithm for subgraph isomorphism. Journal of the ACM (JACM), 1976.
Shinji Umeyama. An eigendecomposition approach to weighted graph matching problems. PAMI, 1988.
Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum. Probabilistic embedding of knowledge graphs with box lattice measures. ACL, 2018.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. In ICCV, 2019.
John Winn, Antonio Criminisi, and Thomas Minka. Object categorization by learned universal visual dictionary. In ICCV. IEEE, 2005.
Yuting Wu, Xiao Liu, Yansong Feng, Zheng Wang, Rui Yan, and Dongyan Zhao. Relation-aware entity alignment for heterogeneous knowledge graphs. 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2018.
Kun Xu, Liwei Wang, Mo Yu, Yansong Feng, Yan Song, Zhiguo Wang, and Dong Yu. Cross-lingual knowledge graph alignment via graph matching neural network. 2019.
Qingwu Yang and Sing-Hoi Sze. Path matching and graph matching biological networks. Journal of Computational Biology, 2007.
Zhen Zhang and Wee Sun Lee. Deep graphical feature learning for the feature matching problem. In ICCV, 2019.
10


Reviews:
[{"review_id": "oKt4h_7Ncs_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a new algorithm for performing subgraph matching under deep learning framework. To this end, the problem is formulated as a node-level metric learning problem. A main contribution of the paper is to introduce partial order preserving property for the metric and yields significant improvements over existing methods. I believe the paper is above the threshold in general.\n\nHowever, I have the following concerns about the paper.\n\n1) I see the author conduct the experiment with k up to 10. While this is a rational number for synthetic and small scale graphs, a feasible k can be much larger in other scenarios. I would like to see how the choice of k can be influenced by different datasets and what is the connection.\n\n2) The result of the matching can rely heavily on the quality of the construction of the graphs. However, in real cases, a query graph may be constructed using some heuristic ways (e.g. k-nearest, \\epsilon-ball or Delauney in graphics). This heuristic construction of graphs may lead to changes to the topology of the graph. Therefore, I think the authors should present more discussion on how to handle such uncertainty in practice.\n\n3) The way of generating training and testing samples seems naive. In practice, both subgraphs of query and target can have semantic meanings, thus a random sampling of subgraphs cannot fully represent the true distribution. I would recommend the authors consider about more practical cases rather than synthetic ones.\n\n4) What changes were made to the two selected baselines (GMNN and RDGCN) to adapt the subgraph matching tasks? It is necessary to give more details showing how the modifications are made. This can help to better understand the baselines.\n\n5) While the authors claimed that subgraph isomorphism can be defined with both node and edges features, I didn't see any part of the paper handling edge features. Throughout the paper, only node features are considered. While edge features are essentials in a large variety of applications (e.g. drug compound matching, DNA matching), I think missing this portion can greatly limit the contribution of this paper. To me, it also seems that the proposed method cannot be readily extended to edge features. I suggest the authors to at least discuss the feasibility of extending this method to edge features.\n\nI would consider raising the rating if the authors can address the aforementioned questions well.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_JHNIR8THDM", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a sub-graph isomorphism method using neural networks and embeddings that are supposed to preserve important topological structure of subgraphs. Sub-graph isomorphism is NP-complete and has fascinated researchers with approximate solutions using heuristics and pre-processing (graph indexes) of many varieties over the years. The approach of using a neural network to learn to perform tasks such as link prediction, label prediction etc., through meaningful node embeddings, is a welcome extension when applied to sub-graph matching.\n\nThat being said, the paper skips over large volumes of progress in sub-graph matching work. From indexing methods, analysis of vertex relationships etc., many methods have proven efficient and effective in sub-graph isomorphism ( http://www.vldb.org/pvldb/vol8/p617-ren.pdf , https://dl.acm.org/doi/10.1145/2463676.2465300 , https://dl.acm.org/doi/10.1145/3299869.3319880 to cite a few) . It is only appropriate that a paper on this topic present a reasonable analysis of the prior work. Also, the embedding design decisions could possibly take-away important conclusions from these methods and lastly, compare against solid benchmarks instead of much older and outdated ones.\n\nIn conclusion, this work is quite interesting. However, at the moment it is not clear for this reviewer how to put it in perspective with respect to decades of systems and theoretical work on sub-graph isomorphism. A fair empirical evaluation should compare the GNN method to one of the state of the art non-neural methods. \n\nThanks to the authors for providing a response to the review comments.", "extra_scores": {}, "extra_text": {}}, {"review_id": "NIOQ8ec3T82", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose neural network schemes for subgraph isomorphism.  Their main subroutine is a subgraph embedding that is trained to encourage the property that if A is a subgraph of B then the embedding emb(B) coordinatewise dominates emb(A).  Given this subroutine, the paper proceeds by producing an embedding of the neighborhood around each vertex of the original graph, then searching for the embeddings of the query subgraph, again centered at each node.  The results of this computation are then used to guess an alignment between the vertices of the query and (a subset of) the vertices of the target graph.\n\nStrengths of the paper:\n* The authors propose the study of this neural subgraph matching problem.  I believe we're past the days in which applying deep learning to a new problem is considered a novel contribution in its own right, but it's still an interesting topic to read about.\n* The authors generate training data for the system by sampling subgraphs from a given graph.  This has the advantage of tailoring the subgraphs they find to the input distribution, and provides a clean way to structure the training data.  They also do some nice study of alternate sampling approaches at inference, to test sensitivity to the particulars of the data generation scheme.\n* The authors propose a particular approach to the embedding learning based on geometric set embeddings that is well chosen for this problem, and seems to perform well in practice.  \n* The post-inference alignment problem is a way to bring significant knowledge about the problem domain into the solution, after the learned part of the system completes.\n\nWeaknesses of the paper:\n* I feel that the runtime isn't well described or analyzed, including in Section F of the supplementary material appendix.  Without the coordinatewise constraint on embeddings, it would be natural to implement the matching of each query subgraph using nearest neighbor search.  However, I didn't see discussion of how to perform the lookups efficiently in the proposed scheme.  Scanning the entire database of target subgraphs doesn't seem ideal.\n* I don't have a good sense of whether an 18% improvement from a general graph matching solution to this tailored solution for subgraphs is a significant advance or not.\n* I felt that the details of the sampling scheme and the alignment algorithm would result in significant changes to the performance of the system, but I didn't see detailed discussion of these issues.\n\nQuestions:\nQ1: Could the authors speak a little to efficiently querying for the best dominating target subgraph at runtime?\nQ2 The embedding constraint has the interesting property that it is not invariant under rotations.  Do the authors have any observations about whether this results in difficulties in the learning?\nQ3: In section 3.2, you comment \"This benefit is a result of avoiding the loss of information when pooling node embeddings and a better inductive bias stemming from order embeddings.\"  Could you describe the evidence in support of this hypothesis?\nQ4: Why is it that in Table 2, FastPFP performs better than NeuroMatch for synthetic data?  It's not a concern for the overall eval, but NeuroMatch by design seems as though it should perform well in this setting.\n\nOther comments:\n* I suggest introducing the set embeddings (McFee & Lanckriet '90) in the paper.\n\nSummary of recommendation: I think this is a borderline paper.  The approach seems reasonable.  There is some novelty in the problem choice, in the framework of generating training data, and in the geometric constraints on the embeddings, but none of these alone is a significant advance in the area.  The empirical results look quite good, but of course the problem hasn't had the same level of scrutiny as better-known pieces of the ML canon.  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7s-j4HgZQfb", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis paper presents a method to solve the subgraph matching problem based on training a graph neural network to produce embeddings of 10-hop, apparently labelled, node neighborhoods in a way that allow for recognizing subgraph relationships among graphs via dominance relationships among their embeddings.\n\nThe results presented in the paper appear occasionally simply too good to be true, while several aspects of the presented method are poorly defined, or totally undefined. Among them the following:\n\n1. Algorithm 1, which provides the main tool to be used in order to answer Problem 1, is defined as returning a subgraph of G_T that is isomorphic to G_Q. However, it is not clear how that is supposed to happen, and the algorithm's pseudocode provides no clue about it. Appendix D revisits this question, and offers that the Hungarian algorithm may be used in case when an explicit matching is desired, yet there is no elaboration on the topic and no results on it.\n\n2. The pseudocode states that a binary prediction is made based on the *average* score of all value of subgraph prediction function f(z_q, z_u); there does not appear to be any way of returning an subgraph as output, apart from this prediction. In itself, the idea that merely taking an average of a binary subgraph prediction function over all node pairs would result in a correct prediction appears simply too good to be true.\n\n3. The paper lacks a sufficient explanation of details regarding this predictive method. There appears to be a threshold t, or perhaps α (both names are used for it) on the magnitude of a violation E(z_q, z_u) on the subgraph constraint among the embedding dimensions of q and u. This threshold is mentioned in Section 2.3 by two names, and then it is never mentioned again. No discussion is offered on what values it has in experiments.\n\n4. Appendix D mentions a sweep over hyperparameters, whose effect is supposed to be shown in Table 4. However, Table 4 shows the accuracy of matching on the ENZYMES data set in an unsystematic manner. No discussion is offered on the threshold parameter. The section on Hyperparameters lists a number of conclusions, which do not appear to relate directly to Table 4.\n\n5. The writing fluctuates several times between the idea of using categorical node features and not using them. Eventually, the matter is left undefined, and the reader cannot tell whether such features are used or not. Section 2.1 leaves the question open. Appendix D comes back to this question, and defines that, with the FastPFP method, a prediction score uses the features matrices of nodes. This is the first time when it eventually becomes apparent that experiments are indeed using node labels all the way, yet the matter is not previously discussed.\n\n6. The size of a k-hop subgraph is not explicitly specified. Section 2.1 suggests that k = 10 in experiments. The value of k is called number of layers. Table 4 in the Appendix also refers to a number of layers. It is not clear whether that refers to k or to a neural network architecture.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an interesting approach for learning to decide whether a query graph is isomorphic to a subgraph within the target graph.  The approach has a number of interesting aspects from the machine learning perspective, e.g. the anchored graphs and the order embeddings.  Empirical results show promise in ablation studies and against a few baselines.

However this paper also has a number of issues as pointed out by the reviewers, placing it right on the borderline.  Most notably the clarity of the presentation could be improved as it seems to confuse a few reviewers at various points.  Another thing that I’d like to highlight is that the way to convert the pairwise scores f(z_q, z_u) into the final decision about G_T and G_Q seems worthy of a longer discussion.  Is a simple average across all pairs the best we can do?  I imagine if the query graph is small but the target graph is large then even if the G_Q does match a subgraph of G_T the average score can be quite low.

Overall I do like the ideas proposed in this paper, but also recognize that the paper can benefit from more improvement, so I’d like to recommend rejection but encourage the authors to submit again in the next round.
Decision: Reject