D2Match: Leveraging Deep Learning and Degeneracy for  Subgraph Matching
Authors: Xuanzhou Liu
Lin Zhang
Jiaqi Sun
Yujiu Yang
Haiqin Yang
Venue: Submitted to ICLR 2023 (2023)

Abstract: Subgraph matching is a fundamental building block for many graph-based applications and is challenging due to its high-order combinatorial nature.  However, previous methods usually tackle it by combinatorial optimization or representation learning and suffer from exponential computational cost or matching without theoretical guarantees.  In this paper, we develop D2Match by leveraging the efficiency of Deep learning and Degeneracy for subgraph matching. More specifically, we prove that subgraph matching can degenerate to subtree matching, and subsequently is equivalent to finding a perfect matching on a bipartite graph.  This matching procedure can be implemented by the built-in tree-structured aggregation mechanism on graph neural networks, which yields linear time complexity.  Moreover, circle structures, abstracted as {\em supernodes}, and node attributes can be easily incorporated in D2Match to boost the matching. Finally, we conduct extensive experiments to show the superior performance of our D2Match and confirm that our D2Match indeed tries to exploit the subtrees and differs from existing learning-based subgraph matching methods that depend on memorizing the data distribution divergence.

Under review as a conference paper at ICLR 2023
D2 MATCH: LEVERAGING DEEP LEARNING AND DE- GENERACY FOR SUBGRAPH MATCHING
Anonymous authors Paper under double-blind review
ABSTRACT
Subgraph matching is a fundamental building block for many graph-based appli- cations and is challenging due to its high-order combinatorial nature. However, previous methods usually tackle by combinatorial optimization or representa- tion learning and suffer from exponential computational cost or matching without theoretical guarantees. In this paper, we develop Ma by leveraging the ef- ficiency of Deep learning and Degeneracy for subgraph matching. More specifi- cally, we prove that subgraph matching can degenerate to subtree matching, and subsequently is equivalent to finding perfect matching a bipartite graph. This matching procedure can be implemented by the built-in tree-structured aggrega- tion mechanism graph neural networks, which yields linear time complexity. Moreover, circle structures, abstracted as supernodes, and node attributes can be easily incorporated in D to boost the matching. Finally, we conduct exten- sive experiments to show the superior performance of our D²Match and confirm that our Match indeed tries to exploit the subtrees and differs from existing learning- barning-based subgraph matching methods that depend on memorizing the data distribution divergence.
INTRODUCTION
Graphs serve as a common language for modeling wide range of applications (Georgousis et all 202IT) because of their superior performance in abstracting representations for complex structures. Notably, subgraph isomorphism is a critical yet particularly challenging graph-related task, a.k.a., subgraph matching at the node level (McCreesh al. 2018). Subgraph matching aims to deter- mine whether a query graph is isomorphic to a subgraph of a large target graph. It is an essential building block for many applications, as it can used for alignment Ch (022),, canonical- ization (Zhou & Torre, 2009), motif matching (Milo et all 2002: Peng et al, 2020), etc.
Previous work tries to resolve subgraph matching two main streams, i.e., combinatorial opti- mization (CO)-based and lcarning-bai based methods (Vesselinoye et all 2020). Early algorithms often formulate subgraph matching as CO problem that aims to find all exact matches in a target graph. Unfortunately, this yields NP-complete issue (Ullmann, 1976: Cordella et all (004) and suffers from exponential time cost. To alleviate the computational cost, researchers have employed approx- imate techniques to seek inexact solutions (Mongiovi all 20TE; Yan et all 2005: Shang all 2008). An alternative solution is to frame subgraph matching as a machine learning problem (Ban all 2019; Rex alall 2020; all 2020) by computing the similarity of the learned represen- tations at the node or graph levels from two graphs. Though learning-basee
models can attain solution in polynomial time, they provide little theoretical guarantee, making the results suboptimal and lacking interpretability. If not worse, the learning- based methods often cannot obtain the exact match subgraphs.
Ideally, we hope to develop subgraph matching algorithm that can leverage the efficiency of learn- ing methods while still maintaining theoretical guarantees. We approach this by building the connec- tion between subgraph matching and perfect matching bipartite graph. We prove that finding the corresponding nodes between the query graph and the target one is equivalent to checking whether there is a perfect matching the bipartite graphs generated by the nodes from the query graph and the target one recursely, yielding a much more efficient subgraph matching algorithm solved in polynomial time.

---

Under review as a conference paper at ICLR 2023
Theorem 4.2 (ourdioon 26:3)
12
Thaoren 4.1
Thaorem 4 (oondiion 1822
M(c') (4)
(1)
(2)
(9)
Figure 1: An illustration of the proposed degeneracy procedure for subgraph matching. Step (1) & (2) are
to determine the isomorphism of pair (a,a') by examining whether their corresponding subtrees, i.e. T((+1)
and a' 7((++) are subtree isomorphic based on Theorem 1. Step (2) & (3) are to simplify the determination of r:41 1 by checking whether subtree- isstooohismmm holds for every L-depth rooted subtree in N ((a))
a unique I-depth subtree in (a) based on Theorem 2. Step (3) & (4) are to transform the aubtreeissmmorphise
relation between N (a') and N (a) to edges in a bipartite graph and interpret the problem as perfect matching
on a bipartite graph.
This degeneracy allows us to harness the power of Graph Neural Networks (GNNs) to fulfill the matching by deploying built-in tree-structured aggregation mechanism in GNNs. Operating on node-level correspondences offers a node matching matrix, which allows us to locate the matched subgraph directly. To incorporate more information, we augment the bipartite graph with supern- odes, which wraps the circles, into the perfect matching procedure; see Fig. II for an illustration of the basic idea. Moreover, node attributes can be easily included accordingly.
Our primary contribution is three-fold: (1) D2Match proposes a novel learning- based subgraph matching method, which frames the subgraph matching problem perfect matching on a bipartite graph. (2) We theoretically prove that this matching procedure can be implemented by the built- in tree structured aggregation mechanism on GNNs and yields linear time complexity. Moreover, we can easily incorporate circle structures, abstracted as supernodes, and node attributes into our Ma to boost the performance. (3) Extensive empirical evaluations show that D*Match outper- forms state-of of-the-art subgraph matching methods by a substantial margin and uncover that learning- based methods tend to capture the data distribution divergence rather than performing matching.
2 RELATED WORK
Subgraph matching is to check whether query graph is subgraph isomorphic to the target one (Mea Creesh 2018). Here, we highlight three main lines of related work:
Combinatorial optimization bbaed methods first tackle subgraph matching by only model- ing graph structure (Ullmaan. 1976). Recent work starts to facilitate both graph structure and node attributes (Han et all 201 Shang et all 2008). These combinatorial optimization methods often rely on backtracking (Prisstlyy & Ward, 1994), i.e., heuristically performing matching on each pair of nodes from the query and the target graphs. Such methods suffer from exponential computing costs. A mitigated solution is to employ an inexact matching strategy. Early methods first define metrics to measure the similarity between the query graph and the target graph. Successive algo- rithms follow this strategy and propose more complex metrics. For example, Mongrovi et all (201)) convert the graph matching problem into a set-cover problem to attain polynomial complexity solu- tion. Yan et all (2005) introduce thresholding method to filter out mismatched graphs. Khhan et all (20T)) define a metric based on neighborhood similarity and employ an information propagation model to find similar graphs. Kosinov & Caelli (2002) and Caelli & Kosinov (2(X44) align the nodes' eigenspace and project them to the eigenspace via clustering for matching. However, most of these algorithms cannot scale to large graphs due to the high computational cost, and their hand-crafted features make them hard to generalize to complex tasks.
Learning- methods typically compute the similarity between the query and target graphs, e.g., comparing their embedding vectors. Ba all (2019) adopt GNNs to learn node represen- tations of the query and target graphs, which employs neural tensor network to match the graph pairs. One immediate challenge is that a single graph embedding vector cannot capture the partial order information for subgraph matching. Thus, Rex et all (2020) train GNN model represent
2

---

Under review as a conference paper at ICLR 2023
graphs while incorporating order embeddings learn the partial order. These methods can com- pute graph-level representations, achieving high computational efficiency. However, they miss the node-level information, which may lose critical details in subgraph matching. To perform node-level matching, several methods (Bai et all 2020; ei all, 2019) introduce the graph-level representation into the node-level matching problem. These methods often adopt different attention mechanisms to generate pairwise relations. However, abusing the attention mechanism makes the model lack interpretability and theoretical guarantee. Others transform the subgraph matching problem into an edge matching problem and generate prediction results through the matching matrix obtained by Sinkhorn's 's algorithm (Roy et all, (022), thereby providing interpretability for the model. The process of turning node matching into edge matching, however, loses necessary information about edges' relation, such as edges' common nodes, which hurts the expressibility of the model.
Graph Neural Networks (GNNs) are powerful techniques (Xu et all 2019; Kipt & Welling 2017)
yielding breakthroughs in many key applications (Hamiloon et al. 7017)) Over the last years, there has been considerable progress in proposing different ways of aggregating. For example, Graph- SAGE (Hamiloo et all 20176) aggregates nodes features with mean/max/LSSM pooled neighbor- ing information. Graph Attention Network (GAT) (Velickovic et all, 201) aggregates neighbor information using learaale attention weights. Graph Isomorphism Network (GIN) et 2019) converts aggregation
learnable function based on the Weisfeiler-Lehman (WL. test instead of prefixed ones as other GNNs, aiming to maximize the performance of GNNs. However, the WL. test (Xu all MTT)) cannot address the subgraph matching problem because hashes the tree structure and loses the partial order information of subgraph matching.
PRELIMINARY
To make the notation consistent, we define them as follows: Let Ao and Ay be the adjacency matrix of the query graph Go and the target graph GT, respectively. (.) denotes the neighbor set of a given node. |- denotes the size of a set. T( defines the subtree whose root is and expands up to 1-hop neighbors of v or (-layer of the subtree. the paper, the concepts the I-hop neighbors and the l-layer subtrees are interchangeable.
Problem Definition: Suppose we are given query graph, Go(Ve, Eg), and a target graph, ET) Here, (Ve, Eo) and (VT,ET) are the pairs of vertices and edges related to the query graph and the target graph, respectively. Besides, the node attributes of the query graph and the target graph are denoted as Xo E R R and Xy E RIVT|xD, respectively, where D the size of the node attributes.
The problem of subgraph matching to identify whether the query graph is subgraph isomorphic to the target graph, i.e. if there exists an injective ʃ Ve + VT such that Vu, E Vo, (u, u) E EQ + (f(u), f(v)) E ET. Without loss of generality, we hypothesize that Go is the subgraph of GT. i... Go C GT with [Vol < [VTl. In essence, the subgraph isomorphism test is to check matching matrix S E {0, (VV \VVll, where Sij = 1 if and only if node pair(i, j) is matched. Go is isomorphic to G7 is equivalent to checking whether the following conditions hold:
IVol
S.
S. S
(1)
In the following, we first define several key concepts in our work.
WL Subtree: The Weisfeiler-Lehman (WL) test is an approximate solution to the graph isomor- phism problem with linear computational complexity (Shervashidze.ct. all 20LI). The WL test per- forms the aggregation on nodes' labels and their neighborhoods recursively, followed by hashing the aggregated results into unique new labels. As result, this test produces an unordered tree for each node, called the WL subtree, which is a balanced tree with the height of the number of iterations. After repeating the algorithm & times, the obtained WL subtree for node includes the structural information of the k-hop subgraph from that node. Research shows that the expressiveness of the WL subtree is the upper limit of message passing GNNs (Xu et all 2019).
Subtree Generation: Considering a node v, we can obtain a subgraph Sub! by taking the I- hop neighbor of v. Given any tree generation method, e.g., the WL subtree, we always obtain corresponding subtree whose root is u:
(! V ((Su(())
3

---

Under review as a conference paper at ICLR 2023
where V/ is subtree generation function. Unless stated otherwise, we employ the WL subtree to generate subtrees for a given node due to its uniqueness (Xu 2018). Instead of explicitly con- structing such trees, we run GNNs in graph, since building k-order WL subtree is equivalent to aggregating & times in GNNs (Xu all, 2018). Notice that traditional methods such as Breadth- First-Search (BFS) and Depth-First-Searce not satisfy the uniqueness property. In particular, the tree generated for the same node by BFS or DFS will be different due different search order.
(DFS) not applicable at this work because they do
Perfect Matching in Bipartite Graphs: A perfect matching (Gibbons, (985) is matching of a graph in which every node of the graph is incident to exactly one edge. Performing perfect matching on a bipartite graph can be solved according to Hall's marriage theorem (Hall, (935).
Theorem 3.1. (Hall's 's marriage theorem) Given bipartite graph, [ Y, E)) that has two partitions: X and Y and YY| < |, where E denotes the edges. The necessary and sufficient condition of the existence of the perfect matching in ( Y. E) is W CY, [W| < [WN) where N (W) is the neighborhood W defined by N(W) (b₃ E X 3a, E W, (as, by) E E..
THE PROPOSED METHOD
This section describes the proposed MaMatch We first introduce the degeneracy of subgraph match- ing and propose an aggregation- based operation to address the degenerated problem, an efficient so- lution with linear time complexity. Following, we introduce two components designed to strengthen the matching ability by incorporating the circle structure and node attributes.
4.1 ON THE DEGENERACY OF THE SUBGRAPH MATCHING PROBLEM
We approach the subgraph matching problem from a degeneracy perspective, framing this problem as a subtree matching problem with linear complexity. A fundamental question to the subgraph matching problem is on what conditions one subgraph is isomorphic to the other. Since the subgraph matching problem is NP-complete, the exact answer this question becomes impractical. Instead, we can reduce the answer of finding both sufficient and necessary conditions to that of necessary only. What follows is to construct criterion that any isomorphic pairs can meet. We know that the subtree matching problem yields polynomial time cost. Inspired by this, we attempt to construct the criterion by taking advantage of the subtrees rooted at these nodes, which degenerate subgraph matching subtree matching and are guaranteed by the following theorem.
Theorem 4.1. Given target graph GT (V7, ET) and a query graph Go(Ve, Eo), if Go C GT. and the subtree generation function V as defined in Eq. (2) meets the following condition:
V graph pair GGs.G),iff Gs C G, then (Gs) C (G),
(3)
then there exists an injective function Vo - VT, ensuring the I-hop subtrees of the subgraph is isomorphic to the subtrees of the corresponding subgraph:
1I 2
f(q) E Vr + T CT.
(4)
Please find the proof in Appendix A. J. This theorem provides necessary condition for the potential isomorphic pairs, i.e., those who pass the test. Given a query graph and a target graph, we can construct an indicator matrix S E R\Velx(Vel by setting S, to when T, C T, and otherwise. The isomorphic test becomes check the validity of Eq. (I)) Due the favorite property of uniqueness, we employ the WI. subtree as the generation function. Thanks to the built-in connection between the WL subtree and GNNs, we can convert the subtree matching problem the problem of perfect matching on a bipartite graph and derive a GNN-based solution. The following theorem guarantees the conversion:
Theorem 4.2. Given a node q in the query graph and node in the target graph, the following three conditions are equivalent:
1) T (++1) T((++1)
2) There exists an injective function on the neighborhood of these nodes as f: (q) > N(t), s.t.
V4, E NQ(g), 4 f(q)), T(l c (!)
4

---

Under review as a conference paper at ICLR 2023
3) There exists perfect matching on the bipartite graph B (V)),)) where Vt, ((),, 9, E N(q),. (t,,q) E E if and only if TT() 44 C C...
The proof is provided in Appendix A The equivalence of the first two conditions implies that matching subtrees of a pair of nodes is equivalent to matching all subtrees from their child nodes, As result, the indicator matrix needs to be updated recursively. That is, the indicator matrix at the (1 + 1)-th layer, i.e., g(++1,, should rely on 8W,, Meanwhile, the equivalence of the last two conditions means that matching the subtrees from these child nodes is equivalent to solving the perfect matching the corresponding bipartite graph whose nodes represent the subtrees of the child nodes. In summary, Theorem H.2 tells us that subgraph matching is equivalent to delivering perfect matching bipartite graph. A visualization of this procedure is shown in Fig. III
Motivated by Hall's marriage Theorem G we develop an efficient algorithm to address the per- feet matching procedure. straightforward solution to randomly select subset W from the given set of neighbors, N(q) in Gg. and count whether the corresponding neighbors of W in (O((N) (q)) E), i.e. NW). have more elements than this subset. After repeating this pro- cess multiple times for all node pairs, we obtain a perfect matching when no instance violates the criterion.
Is it possible to execule all pairs in parallel? Luckily, we can borrow GNNs to accomplish the perfect matching. Specifically, when computing perfect matching between node E Go and node t GT. one needs to find W such that satisfies W C Y N (g) according to Theorem B In practice, we can obtain this by sampling the neighbors of node q. equating to sampling the edges, or the Drop Edge operation (Hamilton et all, 2017a). In this way, we obtain a sampled graph C² from
the query graph Go along with its adjacency matrix Ag. Following Theorem Bill we conclude that W (q) with (g) (q)) since node q's neighbors Go are a subset of the original graph. At each iteration, we will perform the counting w.r.t. W and its neighbor set N(W) for each node pair q), and check whether [N(W)) 2 [W| holds. To be efficient, we define a binary matrix, T E RIVrix xVVel, where its element (t. q) corresponds to the result of the node pair (t, q)-
Based on Theorem I. we need to update the indicator matrix S recursively, making the update of executed in recursion accordingly. We next show that computing t is equivalent to performing the GNN-based aggregation on the related graphs for any given 5(1).
Theorem 4.3. Given the sampled query graph and the target graph, we can construct their adjacency
matrices, Ag and AT, and the degree matrix of the sampled query graph Do diag (,, (())):)).. Here, we denote the indicator matrix at the 1-th hop as ((() To check the validity of [N(WW) 2 [W] for each node pair, we can check whether each element of + is true or not, where = ZN(W) 2 1,
ZN(W) = aggregate (Ar, Z and Zw = aggregate (Ōe) do. (S())T).
The proof is provided in Appendix for each node pair (t, q). i.c., to check whether each element of 4 is true for each sampled A The condition is valid only when & is true for all iterations. Hence we can check the criterion by the following element- wise product:
Recalling Theorem 1 we need to check [N(W)] 2 W
K
((++))
a (1+
(A AT),
(5)
subtree
k=
where O denotes the element-wise multiplication between matrices. In practice, ((++1((A()) considers three cases:
.A)
aggregate,mn. (AT, aggregate (D Ae, (SW))T
if k=
aggregate sum (A7, aggregate max (Do¹ (K) (S)))) 21 if [1, - if k=
(6)
aggregate min (Aq, aggregate, max (A7, (T) 21
The above three cases allow us to balance the computation cost and accuracy. Initially, when k = 0. deliver full-size sampling for all nodes to avoid induction bias. When k = K, perform the single-node sampling such that no node is omitted. The cases of l E [1, K - 1] are computed via downsampling.
We want to highlight the difference between ours and other learning- based methods regarding GNNs. Here employ GNN model to accomplish the procedure of subtree matching, along with theo-
5

---

Under review as a conference paper at ICLR 2023
retical equivalence. With the subtree representation learning, GNNs let other learning baasd models capture the variance of data distribution for similarity inference since deep learning models learn distributional information to distinguish samples from different classes.
4.2 BOOSTING THE MATCHING
The last section introduced method to address the subgraph matching problem based on the proposed necessary condition, which we call the base model. Without sufficient conditions, it cannot guarantee that all positive isomorphism pairs to be selected precisely. To mitigate this issue, further incorporate information such as circle structure and node attributes to filter out more non- isomorphism pairs.
4.2.1 DEALING WITH CIRCLES
Prior methods often leave the circle structure aside, however, such a structure is often unavoidable and critical in graphs. In particular, learning-basee methods rely on the expressibility of GNNs, which cannot model circles due to their bubtree-structured aggregation. The underlying idea of our D*Match is to construct the circle structures as supernodes, which allow us to formulate the circle matching standard subtree matching problem. Before detailing our strategy, we first present two desired properties of the set of circles in graph.
Atomic: Let
(U1...., [[()) 01) C define circle and v(r) be the set of nodes of circle
circle is an atomic circle if it does not contain smaller circle. That is, there is no circle r' such that v(r') C v((). Here, the circle set.
Consistency: Each query circle must correspond to one circle in the target graph, i.e., 3 S Vr ((r) E CT. Co and Cy are the circle sets of the query graph and the target graph, respectively.
The atomic property aims to ensure the compactness of circles, and the consistency attempts to ensure that the relation between a query and a target set of circles is injective. These two prop- erties ensure a well-qualified set for matching. In practice, we can take advantage of chordless cycles (West, 2000), to serve our goal of matching circles. We now state our theorem below to show that these eycles satisfy the above consistency and atomic property.
Theorem 4.4. Every chordless cycle is atomic. Every chordless cycle Co in an induced subgraph of the original query graph Go must correspond to a chordless cycle Cy in the origin graph Gr.
Please find the proof in Appendix, A.G. This theorem suggests that chordless eycles satisfy the above two properties, making them suitable for representing circles in graph. To match circles, we introduce an augmented graph by inserting supernodes that embody these circles. Given length I. we can acquire corresponding chordless cycles for the query and target graphs as CT {((r)= < L,r E CC(GT)),CC = (l(r) S L,r E (C( By setting V, as the supernode of any chordless circle graph. Note that supernodes can only match other supernodes to keep the matching of non-circles untainted. To this end, we transform the circle matching as the subtree matching problem such that we can employ the proposed method on the augmented graph directly. Unless otherwise stated, we keep all notations the same in the augmented graph avoid abusing the notations.
connect nodes from the circle to this supermode, resulting in an augmented
4.2.2 DEALING WITH NODES' ATTRIBUTES
Apart from the above structure information, subgraph matching also involves node attributes. Within the context of subgraph matching, learning with node attributes alone may be misled because these cannot catch structural isomorphism. As a result, we employ the obtained subtree indicator matrix to supervise the learning process, aiming to filter out pairs that do not pass the test in the subtree matching. We are thus motivated to enhance the node attributes by concatenating the subtree match- ing indicator, resulting in the node representation for the query and target graphs as follows:
{
(+ = GN N (AT, concat(H MLP(S H = GNN (Aa, concat(H MLP((S0)TM
Here, we employ an MLP model to reduce the effect of the difference between the node attributes and the indicator matrix, where the latter behaves like one-hot feature. We concatenate each pair

---

Under review as a conference paper at ICLR 2023
of representations and then pass it to the MLP to obtain their similarity. For the node pair (f.j), have the similarity computed as
[S lij = MLL((concat (H, (
(8)
Now we arrive a generalized indicator matrix that considers both the structure and node attribute information (((+1) s((+2)
s(1+1)
gnn
subtree"
Algorithm The D2 Mathh algorithm
Require: query graph (V2. Eq) with attributes Xg. tarpet graph Gr(Vr, Er) with attributes X iteration number:
L. sample number: K.
Ensure: Gg isomorphic Gi
1: Ga(Va, Ee) Chhoooleesecccc./gneennneaCaCCaa
2: He Xe: 41 XT:
3: (
Subbtree =nabsal/AssggnMaarrrkrk...
Initialize assignment matrix;
4: for p=r==0 1,.1..,.4
do 5: for === 0. I...... K de
6:
A DropEdde(Aaa)
Sample adjacency matrix
7:
Calenlate 4tt (1) (A Ar) according to E
8:
end for
9:
Suberee - (114)) (1))) Ar):
Final subtrec assignment
10:
H = GNNN (AT, concad L B.S..MLPEEE MLP(S())):
11:
#0+1 GNN (Aa, concat|H MLP((S()))
update
12:
Compute s(Li)) according to Eq
> Final GNN assignment matrix
5 1) s @ subtrac
s(111)
Final assignment
end for
15: result CheckAeeign(Stt)
4.3 IMPLEMENTATION DETAILS AND COMPLEXITY ANALYSIS
We summarize the overall procedures in Algorithm. II The computation of D*Match has two major parts: the subtree and GNN modules. Given L layers and times of sampling, the complexity of the subtree and GNN modules are O(L K +V |Eo + L+ [=<VV |E and O(L* E L [Eo++ |Vr|+ * IVel). respectively. Since the query graph is often very small, we can treat (Vol and |E as constants. A detailed runtime comparison is in Appendix A. Therefore, the overall complexity is reduced to O + [), attaining linear time complexity. Please refer to Appendix A. for more details about the implementation.
EXPERIMENTS
Here, we conduct extensive experiments to answer the following questions: (1) How does our proposed D2MMatch compare to SOTA methods? (2) Why GNNs in ours and others yield different results? (3) How robust does D2 Match perform? Sec. accordingly.
Sec. answer the above questions
5.1 EXPERIMENTAL SETTINGS
Datasets and Experimental Setup. We implement our experiments both synthetic and real- world datasets, which are collected from a large variety of applications. We aim to obtain pairs of query and target graphs, along with labels indicating whether query isomorphic the target. We first generate synthetic data by utilizing ER-random graphs and WS-random graphs (Rex all 202T). We keep edge densities the same in both positive and negative samples ensure consistency in the distribution. This balance avoids potential biases during learning. For the real-world data, we follow the setting in (Rex et all 2020), including Cox2, Enzymes, Proteins, IMDB- IMDB-Binary. MUTAG, Aids, and FirstMMDB. We also conduct additional experiments on the Open Graph Benchmark datasets(Hu
(02L) and three datasets with continuous features in Appendix A. We employ these raw graphs as target graphs and generate the positive query graphs by randomly sampling from the target graphs. The negative query graphs are randomly generated. Similar to the synthetic data, require the edge density in both positive and negative samples to be close possible. We split each dataset into training and testing at a ratio 4 and report the average classification accuracy under the five-fold coss-validation.
7

---

Under review as a conference paper at ICLR 2023
Table 1: Overall performance comparison terms of accuracy.
Syothetic
Proteins
Mutag
Enzymes
Aids
IMDB-Binary
Cox2
FistMMDB
SimGNN
70.5
96. 96.2+am7
98. 28.7+0.0
98.6 98.6+1.0
96.5
85,0 p
99.9
82,40+0.7
NeuroMatch
7
17.5
99, 22
97. 97.9
97.4-m0
86.5
100.0gm00
80.80ga.
IsoNet
50.0
60.02100z
44.14254
91.0=775
61.5-a5t
83.1
95.8
GMN-embed
56.62x6
93. 93.8g241
90.81616
89.4
78.3_4
69.3
69. (9.72118
69, 1
GraphSim
50.0
82.5
89.5
88 88.2
75.6-68a
88 9:2ai
95.5 2004
66.64
GOT-Sim
53.0+274
$7.2+852
86.8
68.7+1415
70.6-3m
81.3
94.8+1.04
MaMathh
74.3
100.0_am
10.00
g.222
99.5_a.7
93.3
100.00
100.00_...
Baselines. To get fair comparison, we select the following SOTA competitors: SimGNN (Bai
ctall 2011) NeuralMatch alll 202T), IsoNet (Roy et all 2022), GMN-ember (Laetall, 2019)
GraphSim (Baret all, (020), and GOT-Sim (Dean et all (024)). These all incorporate graph neural networks into subgraph matching. We present the comparison with exact methods in Appendix A.N
5.2 MAIN RESULTS
Table M reports the overall performance of all compared models, where each model achieves the best results in all possible settings up to 500 epochs. The accuracy of GOT-Sim and IsoNet on FirstMMDDB is omitted due exceeding time and memories. We observe that
For the synthetic dataset, the overall performance is much lower than that the real-world datasets. A reason is that the synthetic dataset is more complicated, e.g., with a higher edge density, than real-world datasets, which makes the matching more challenging. By examining more details, IsoNet, GMN-embed, GraphSim, and GOT-Sim attempt to employ a node-level assignment ma- trix to capture matching between graphs, which underestimate the importance of global structure. They can only yield around 50% accuracy. SimGNN and NeuroMatch try to learn the global representation and attain the accuracy of 70.5% and 65.7%, respectively.
For the real-world datasets, Match attains superior performance and beats all baselines. Among seven real-world datasets, M2 attains 100% accuracy in four datasets, i.e., Protein, Mutag, Cox2, and FirsMMMBB, while at least 99.5% in Enzymes and Aids, and 93.3% in IMDB-Binary. Overall, Match has explicitly modeled subtress and consistently attained the best performance among all compared methods. The promising results confirm our theoretical analysis.
5.3 BENEFIT OF OUR CORE DESIGN: THE SUBTREE MATCHING
Though GNNs deployed in D2Match and existing learning- -based subgraph matching methods, they function differently. Matat utilizes GNNs to explicitly models subtrees while learning-based methods learn the graph representations via memorizing the data distribution divergence. To validate this, we construct new datasets and denote them with by excluding the data distribution effect. We first follow the same way as generating positive samples, then continue to perform edge dropping and insertion on the clipped graphs together to obtain the final negative samples. This strategy aims to make sure the generated samples, both positive and negative, following the same distribution in terms of edges. We also build an new synthetic dataset without following this property, called Synthetic+, for better comparison. Since SimGNN and NeuoMatch are the best-performing GNN- based methods in Table II, we select them in the comparison.
Results in Table Q show that Match outperforms SimGNN and NeuoMatch by much larger margin, achieving 2.5% 33.2% improvement. This phenomenon aligns with our hypothesis that the gain of other tearning-based methods is distribution-dependentt which results in a significant performance drop on evenly-distre -enty-distributed data. Moreover, the overall performance on Synthetic* is much better than that on Synthetic. This implies that data following non-even distribution will make the matching much easier. This is in line with the results in Table II i.e.. the learning- based methods tend to capture the distribution divergence rather than performing matching. 5.4 ABLATION STUDIES
Effect of L, the depth of a subtree. We test the effect of the depth of a subtree, i.c., the number of the hidden layers, and change it from I to 7. Results in Fig. B(al shows that M reaches
8

---

Under review as a conference paper at ICLR 2023
Table 2: Results of experimenting the uniformly distributed data in terms of accuracy.
Symthetic
Symthetic
Proteins"
Mulag"
Enzymes"
Aids"
IMDB Binary"
Cox2"
FirstMMDB
SimCiNN
20.5
64.6_.
76.0ga17
2302
22.0 60.4_m
2
53.2
NeuroMatch
65.7
52.8_40
90.4
86.0136
75.6
91.01sm0
50.0
Matthh
86.62141
24.3
83.4
99.2
96.0.216
95.0g141
20.2
99.8
86.4
its best performance when the number of layers is 6. Da only needs few layers to achieve decent performance, suggesting it can scale up large size graphs.
Effect of K, the times of samples. Intuitively, sampling more data to train the model will yield better performance. We vary from results show that by sampling five times, we can obtain the best performance on all datasets. This demonstrates that Matchh can attain decent performance in low computation cost.
and show the results in Fig. 2bb Surprisingly, the
We also ablate D with circles and node attributes at different settings, and all experiments show results consistent with our theoretical analysis. Please refer to Appendix A.3 for more details.
Synthotic
Synthatic
D' M'Machh
Proteins"
Froteins"
NeuroMatch
90
Enaymee"
Accursoi (h)
Encymes
mormallzed)
Accuracy
2.4
COTSim
GraphSim
80
1.2
1.0
150
300
450
Layer number
Sample number
Spoch
(a) # layers vs. accuracy
(b) sampling vs. accuracy
(c) The convergence comparison
Figure 2:
We conduct sensitivity analysis on our Matah by varying the number of layers and sampling. In Fig. Pic. we present the convergence curve on our D Match and four strong baselines.
5.5 CONVERGENCE ANALYSIS
Figure C provides the training loss of D and four baselines on Synthetic, where we only select baselines with the same loss functions as ours, such as MSE or CE, for a fair comparison. The results show that (1) Matat converges the fastest due its power of explicitly modeling the sub- trees. (2) MauroMatch and SimGNN perform matching through learning graph-level representations, which need more epochs to converge for capturing the local structure. (3) GOTSim and GraphSim attain the lowest loss in the beginning but show the weakest convergence ability compared to others because they can only capture the node-level representations and fail learn meaningful subgraph matching. Consequently, they yield the worst performance as reported in Table II.
6 CONCLUSION AND FUTURE WORK
In this paper, we propose Matat for subgraph matching, which degenerates the subgraph match- ing problem into perfect matching a bipartite graph and prove that the matching procedure can be implemented via the built-in tree-structure aggregation complexity. We also incorporate circle structures and node attributes to boost the matching. Finally, conduct extensive experiments to show that Matatch achieves significant improvement over competitive baselines and indeed exploits subtrees for the matching, which is different from existing learning-based methods for memorizing the data distribution divergence.
GNNs, which yields polynomial time
1)² Match can be further explored in several promising directions. First, we can investigate more degeneracy mechanisms to tackle more complicated graphs. Second, we can extend our DaMatch to more real-world applications, e.g., document matching, to know its capacity.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
The supplemental material includes the code for our experiments. An detailed description of the datasets used in the experiments is provided in Appendix A.
REFERENCES
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. WSDM '19, pp. 384392, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450359405.
Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. Proceedings of the AAAI Con- ference on Artificial Intelligence, 34:3219-3226, 04 2020.
T. Caelli and Kosinov. An cigenspace projection clustering method for inexact graph matching. IEEE Transactions Pattern Analysis and Machine Intelligence, 26(4):515-519) 2004.
Liqun Chen, Zhe Gan, Yu Cheng, Linjie Li, Lawrence Carin, and Jingjing Liu. Graph optimal transport for cross-domain alignment. 2020.
L.P. Cordella, P. Foggia, C. Sansone, and M. Vento. A (sub)graph isomorphism algorithm for match- ing large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(10):1367- 1372, 2004.
Khoa D. Doan, Saurav Manchanda, Suchismit Mahapatra, and Chandan K. Reddy. Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. In Pro- ceedings of the 44th International ACM SIGIR Conference Research and Development in Infor- mation Retrieval, SIGIR '21, pp. 665674, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450380377
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. CoRR, abs/2003.00982, 2020. URL https:
bxg/abs/2003. 00982.
Stavros Georgousis, Michael P. Kenning, and Xianghua Xie. Graph deep learning: State of the art and challenges. IEEE Access, 9:22106-22140, 2021.
Alan Gibbons. Algorithmic graph theory. Cambridge university press, 1985.
Peter Hall. On representatives of subsets. Journal of The London Mathematical Society-second Series, pp. 26-30, 1935.
William L. Hamilton, Rex Ying. and Jure Leskovec. Inductive representation learning on large graphs. CoRR, abs/1706.022) 02216. 2017a. URL /ttp:///aa.....oo/////////// 02216
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017b.
Wook-Shin Han, Jinsoo Lee, and Jeong-Hoon Lee. Turboiso: towards ultrafast and robust subgraph isomorphism search large graph databases. In SIGMOD '13, 2013.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00653 2020.
Arijit Khan, Nan Li, Xifeng Yan, Ziyu Guan, Supriyo Chakraborty, and Shu Tao. Neighborhood based fast graph search large networks. In Proceedings of the 20/ ACM SIGMOD Interna- tional Conference Management of Data, SIGMOD '11, pp. 901912, New York, NY, USA, 1. Association for Computing Machinery. ISBN 9784400306614
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICI.R, 2017.
10

---

Under review as a conference paper at ICLR 2023
Serhiy Kosinov and Terry Caelli. Inexact multisubgraph matching using graph eigenspace and clus- tering models. pp. 133-142, 08 2002. ISBN 978-3-540-44011-
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity of graph structured objects. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 3835 3845. PMLR, 09-15 Jun htmll
2019. URL attps:
Ciaran McCreesh, Patrick Prosser, Christine Solnon, and James Trimble. When subgraph isomor- phism really hard, and why this matters for graph databases. J. Artif. Int. Res., 61(1:723375, jan 2018. ISSN 1076-9757.
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Net- work motifs: Simple building blocks of complex networks. Science (New York, N.Y.), 298:824-7, 11 2002.
Misael Mongiovi, Raffaele Di Natale, Rosalba Giugno, Alfredo Pulvirenti, Alfredo Ferro, and Roded Sharan. Sigma: set-cover-based inexact graph matching algorithm. Journal of bioin- formatics and computational biology, 111199-218, 2010.
Hao Peng, Jianxin Li, Qiran Gong, Yuanxing Ning, Senzhang Wang, and Lifang He. Motif-matching based subgraph-level attentional convolutional network for graph classification. In AAAI, 2020.
Hilary A. Priestley and Martin P. Ward. A multipurpose backtracking algorithm. J. Symb. Comput., 18(1):1-48 1994. URL http://dbbl uni uuni-tzie ttt.ttrreee..ee///oooaaaaaa///// htm [Eml#Priestten leyn94
Rex, Ying, Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, and Jure Leskovec. Neural subgraph matching, 2020.
Indradyumna Roy, Venkata Sai Baba Reddy Velugoti, Soumen Chakrabarti, and Abir De. Inter- pretable neural subgraph matching for graph retrieval. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7):8115-8122 Jun. 2022.
Haichuan Shang, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu. Taming verification hardness: An efficient algorithm for testing subgraph isomorphism. 1(1):364375, aug 2008. ISSN 2150-8097.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lehman graph kemels. Journal of Machine Learning Research, 12(9), 2011.
R. Ullmann. An algorithm for subgraph isomorphism. ACM, 23(1):3142, jan 1976. ISSN 0004-5411.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Natalia Vesselinova, Rebecca Steinert, Daniel F, Perez-Ramirez, and Magnus Boman. Learning combinatorial optimization graphs: A survey with applications to networking. IEEE Access, 2:120388-120414 2020.
Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2 edition, September 2000. ISBN 0130144002.
Keyulu Xu. Weihua Hu. Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? CoRR, abs/1810.00826, 2018. URL http: http:h//tkaattt /ttp.//wwww/bb///.1...oooo
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICMI., 2019.
Xifeng Yan, Philip S. Yu, and Jiawei Han. Substructure similarity search in graph databases. In Proceedings of the 2005 ACM SIGMOD International Conference Management of Data, SIG- MOD '05, pp. 766777, New York, NY, USA, 2005. Association for Computing Machinery. ISBN 1595930604.
11

---

Under review as a conference paper at ICLR 2023
Feng Zhou and Fernando Tore. Canonical time warping for alignment of human behavior. Advances in neural information processing systems, 22, 2009.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. CoRR, abs/1707.04638, 2017, URL http::/arxixx
http://arxxi.rogbbb/////aa wtt.:oo/g/aaaaoaao.oooo 04638
12

---

Under review as a conference paper at ICLR 2023
A APPENDIX
Theorem A.1. Given a target graph (VT, ET) and a query graph Ge(Ve, Ee). if Ge C GT. and the subtree generation function v as defined in Eq. (L) meets the following condition:
A graph pair (Gs, G) Gs C G, then (Gs) C (G),,
(9)
then there exists an injective function VVV VT, ensuring the I-hop subtrees of the subgraph is isomorphic to the subtrees of the corresponding subgraph:
vI 1, Ve.t f(q) E VT T c I!"
(10)
Proof. According to the definition of subgraph matching (McCreesh all 2018), when Gg is a subgraph of GT, there must exists an injective function f: Ve - Vr, such that Vq: 9, E Ve, (q. (g. E Eo + (f(g.), f(q,)) E ET. For any subgraph in the query graph, c.g., S(Vs, E's) e Go. we always have a subgraph in the original graph Gr, denoted as Gs EG), that corresponds to the set of the query node as Va f(Vs). This tells us that S C Gş. According to this, consider any given node from Ve: q Ve. s is a subgraph of Go and its image Go in
GT. i.c. sQ C G Ggmn By definition, the node in (())) or Gg is at most (-hop from node q or t= f(()), we know that Ggm must be a subgraph of (!!) i...G.G... s C c(((). Put all together, we have ( c G sg C c( Based on the listed constrain, we then have T C CT
Theorem A.2. Given node q in the query graph and node in the target graph, the following three conditions are equivalent:
1) (1(+)) cI(++))
2) There exists an injective function on the neighborhood of these nodes as f: - (t),, s.t.
Vq, E (q)) f(q.), T() TT())
3) There exists perfect matching on the bipartite graph (N)),, (q)), E), where Vt,
N(t), 9; E N()), (4,, 9,) F if and only if ( c cT...
We prove this theorem by introducing the following two theorem. Theorem AW shows that con- dition 1) is equivalent condition 2), i.e. the WL subtree isomorphism test be accomplished in a recursive manner then prove Theorem. A.4 that the condition 2) equals to condition 3) which means every iteration in the recursive process equals examine the existence of perfect matching, respectively.
Theorem A.3, Given a node q in the query graph and a node in the target graph, the following two conditions are equal:
1) TT((+1) cT(+)), where 7 an integer and 2 2) There exists an injective function on the neighboring set of these nodes as f N(g)) 7 N(t), s.L.q, E N()q), 4 = f(q)), C T())
Proof. We assume fy is subtree isomorphism injective function in the condition 1), that V node u, E (1(++) (u, v) is an edge of I (1+1) + (w), fu))) is an edge of 2: (1(+)) Similarly We also assume fg. subtree isomorphism injective in the condition 2).
On the one hand, if condition 1) is true then fy exists. Using the property of WL tree, we have Vq, E (q),, TQ( C (T(+1), which means the (-order WL tree of any node q; in q's neighbourhood belongs the | + 1-order WL tree originate from the node q. This suggests that fg maps (:(() into tree T f(q,) I which is subtree of T ((++1) Then the condition 2) is true.
On the other hand, if condition 2) holds, then we define the mapping as fa(v) = (gg(1)) VE T(()
44.
4. v= q
13

---

Under review as a conference paper at ICLR 2023
Here, the function (u( is standard injective function T This implies this is subtree isomorphic mapping, so 1) holds.
The above theorem provides recursive solution to the WL subtree isomorphism algorithm. Intu- itively, we can maintain an indicator matrix 5t)) E RIVrIxIVal, where
1. T CT
5(0) bq
0. else
This matrix captures the relation between all pairs of nodes and thus can be used for recursion up- date. Next, we will show that the update process can be implemented as perfect matching problem, i.., what makes condition 2) true is equivalent finding a perfect matching on a bipartite graph, as shown in the following theorem:
Theorem A.4. Assume the neighboring set of node and q as X (t) and Y Ng)), re- spectively, Accordingly, we form bipartite graph as B.y (X, Y, E). Here, we define the edges as E q() I IT"), where and 9, represent the ith and jth neighbour of node and q. respectively. Under this setting, the injective function f from the condition 2) in Theorem. induces a perfect matching.
Proof. The injective function f of condition 2) in Theorem A maps every node in N(q) to f(q,)) N and T ( holds. While TT()) T:()) means 4.) E E, the injective naturally
corresponds every node q; to an edge (4, ty). Since f is an injective function, 9,, * 9, = 4 $ lig.
4), = 1,.... [q)) are different, which actually forms a perfect indicating that all these edges (q,:4),
matching.
Theorem A.5. Given the sampled query graph and the target graph, we can construct their adjacency matrices, Ag and A7, and the degree matrix of the sampled query graph De diag (iag(E,40 ((Ag):s)) Here, we denote the indicator matrix at the I-th hop as S()), To check the validity of (N(WW) 2 [W) we can check whether each element of + is true or not, where + = ZN(w) 2 1, ZN(W) = aggregate (AT, )w) and Zw aggregate max (D Ao (S(0)T).
Proof. For each node pair t, q and their corresponding W = (q) in the sampled query graph, We first transform the neighboring of W, i.e., (W), as following:
N(W) =44 E (())Bg; E W (N'(9), s...1 cT
(4 E N(0)3g, E W = N')) =
=(4 E N()) max 5 1}
(11)
('EN(())
NN( (tal
max
5(0))
" = 1}
(q)
((()
{t. ma 1h) 1}. we compute (q) via standard maximizing aggregation process on the sampled adjacency matrix Åg, in which treats the indicator matrix (Sthy" E ||Vr| as node attributes. This process will output the representation of node follows,
Let (q)
z maar(((())) T. Vj E (q)),
(12)
1,
i M(q)
The obtained vector zy is to represent (g) where Eqp = (0,
We rewrite this into
else
matrix format as
Zw = aggregate max (Āg, (T)
(13)
where Zw E VelxVll and its q-th row vector is zq--
14

---

Under review as a conference paper at ICLR 2023
Recall that we demand (WW (() After acquiring (q), compute the (N) as follows,
{
- [M())== [N(W)] = Σ &q.in i ((t)
Zq,i
(14)
In essence, this is to implement a summation aggregation on the target graph using the node repre- sentation Zw, i.e.,
ZN(W) aggregate sum (AT, Z
(15)
where ZN(w) E R VTV is an integer matrix and its element (t, q) shows the score of [WV(W) between node and q. This transformation converts the counting operation aggregation such that we can check the aggregated values to determine whether there is a perfect matching. Given a node pair (t, q). we have [N(W)] = [Z and [W| = [ = Σ, [Aglqs. Therefore, the question
becomes to check whether (Zaaw)ly 2 E.(Aoll AAlle holds. We can then derive the perfect matching
as follows:
[ZN(w)ly N
Σ [Aelar
Kx(w)la// (Aolee 2
(16)
lggreggtte sum LAT,2i0 (iyy dd
aggregate sum (AT, Deell 1y 21
/aggregate.... (Ar, Zw Do')lyy 21
where dy is the degree of node in the sampled graph. The degree matrix of the sample graph is defined De diag Σ, ((Ag):=)] Now recall that & is the matrix whose (t, element is the comparison result of ((W) and [W] of (t, q), according to eq IG, we have:
(1+1) (Ag, AT) aggregate sum (Ar, Zt De')) 1,
(17)
where
Zty De Jaggregate max (Ae, (8())) De'
!وزا aggregate max (S()))
(18)
laggregate max (D (S()))
Theorem A.6. Every chordless cycle is atomic. Every chordless cycle Co in an induced subgraph Go must correspond to a chordless cycle Cy in the origin graph Gy.
Proof. Chordless cycle does not have any chord, thus there is smaller cycle in the chordless cycle, which means chordless cycle atomic. Assuming Go a subgraph of Gy, every node of Co must correspond to node in GT, and these nodes form circle CT GT. Since Go is induced subgraph of G7, if CT has a chord, then Co must have a chord, which contradicts the condition that Co is a chordless graph.
A.1 IMPLEMENTATION DETAILS
The python implementation of D*Match is available at:
/ttps://www.rr https:/wwww..aoooooooooooo//////
21=0
At the beginning of subtree isomorphism test, the model needs an initial indicator matrix S(D)
((0) the input of the first iteration. According the definition of the indicator matrix, Suubtree shows the isomorphism relation between the subtree of O-hop neighbors, which are the nodes themselves in this case. Since all nodes will be isomorphic to each other if not considering the node attributes.
(()) the indicator matrix subtree is actually a similarity matrix w.r.t node attributes. To get a similarity matrix of attributes, we can either directly calculate the similarity between nodes employ neural
15

---

Under review as a conference paper at ICLR 2023
networks on these attributes to learn the matrix. In model, implement both methods to initialize the matrix, called the initialization of the raw and the learnable:
Raw s(0)
subtree CosineSimilarityy (X,, Xe) NNrrm(T)) Norm((2))
(19)
Learnable (
subtrer. MLP(XT) MML(X)))
where the raw initialization is to calculate the cosine similarity between the nodes' attributes, and the learnable initialization employs MLP to generate hidden representations of nodes and compute their dot similarities.
In practice, find the raw initialization performs better. This is because the node attributes of datasets are usually binary categorical vectors, which induces clear identification information of the nodes and can be easily captured by cosine similarity.
Our implementation of the GNN block in the model is slightly different from the description. Specif- ically, we use compute the similarity of each pair of nodes as:
[S(+)] Júj (MT.P(concal((f)) (1H 1)))
(20)
The main difference is that we do not output a |Vr| x [Vol matrix, but a [V / [Vol x D(++1) tensor, where ( denotes the hidden dim of / + layer. The intuition is that a tensor that represents retain more information than similarity matrix with
the node pairs' similarity with vectors
scalar elements. In this setting, the final indicator matrix ((++1) can not be generated as S(1+1)_ Thus
s(t))) @ I((+1) subtrec? because I((+1) E RXVil but Sgatt) B|
Peubtree to 5(1+1) where Vk: E ((t+)), [S subtreeligk [ subtreeliy and the final 5(1+1) indicator matrix 5(++) Syn @ subtree
broadcast S s((+1)
At the end of our models, we get the subtree indicator matrix ( Subtree and the GNN indicator matrix Syn The model will output the final score from s(L) subtree and S Synn, respectively. For the subtree module, we check whether the indicator matrix is feasible to induce the subgraph isomorphism. Note that for node in the target graph and node in the query graph, is possible to match unless [L) subtreelss 1. So we check whether the subtree indicator matrix meets the following two conditions:
s(L)
1) Every node query graph should match at least one node in the target graph:
Vj. max(s subtree)is
Σ max subtree Daj IVel
((L)
(21)
Σ max ((L)
) =1
2) The number of nodes in the target graph that match at least one node in the query graph is more than the number of nodes of query graph:
Σ
( 2 VVll mm
(22)
To make the subtree model differentiable, we use a learnable sigmoid to replace all the logical judgment in the model:
[Sigmoid(x)) = a(a + where a, b are learnable parameters; is the sigmoid function. The result of subtree module can be
(23)
fomulated as:
Tsubtree = LSigmoid
Σ m ((L) Sis LSigmoid E Da (24)
subttree
For the GNN module, employ the neural tensor netW (Ba all 2019) and generate score according to the output of NTN and the aggregated indicator tensor:
Tynn {M [ HH!) (1)))
ΣV s(L) su)tree)))
(25)
16

---

Under review as a conference paper at ICLR 2023
Where H H the node representations generated by the GNNs. NTN is the NTN layer.
(b)
The final prediction is:
gnn Psubtree
(26)
Although the model's prediction is obtained by integrating the modules, not directly train the model through the final score because it will bring difficulties in the training process. When fitting negative sample, the resulting subtree module tends to be zero, forcing the overall gradient to be zero which hinders the training of the GNN module.
Therefore, we train the two blocks with different objectives. For the subtree module which aims to lear the isomorphism relation, the result should be either 0 for not matching or I for matching. So we employ MAE loss enforce the results be either 0 or For the GNN module, we use MSE to encourage the output of GNNs capture the similarity. Suppose the ground-truth label is and our loss function is
MSE(E gnn. y) + (A sublree:!)
(27)
Both model and all baselines use the Adam optimizer and set the learning rate to 3e 4. To ensure fairness, we set all models with adjustable number of layers to layers, and set the hidden dimension to 10.
tarae soaP
DigH grOc
(2)
(b)
(c)
Figure 3: The detected subgraphs by D Match
A.2 DºMATCH AT WORK
Recall that Da learns indicator matrix to capture pairwise similarities. plays the role of permutation matrix in matching, allowing us to pinpoint the matched subgraph. This is particularly useful since the exact position is required for some downstream applications such as web search. In comparison, other learning- barning-based methods are unable to pinpoint local correspondences, but only establish the existence of matching. We provide visualization the matched subgraph to better understand the problem difficulty and the effectiveness of our method, as shown in the Fig. B.
A.3 ABLATION STUDIES
We perform ablation studies for the GNN module, subtree module, and chordless cycle.
The GNN module in our analysis will capture the distributional features on the graph, such as the edge density difference between classes. The GNN module is thus essential for datasets with mul- tiple distributions, also called biased data. We run experiments on both the biased and unbiased synthetic datasets to show the performance of our method and its variation that without the GNN module, shown in Table BL Match outperforms Matat without the GNN module our theory predicts. But our GNN module shares the same weaknesses as the other GNN models when dealing with evenly distributed data. We observe that the performance of the GNN module drops significantly on hard datasets similar to other GNN models. The subtree module can significantly improve the performance because it hamnesses the property of subgraph-matek robust to data's 's distribution. Our subtree module outperformed the GNN module on all datasets in ablation study, demonstrating its effectiveness.
data, making
17

---

Under review as a conference paper at ICLR 2023
Table The ablation study of D2Match module
Syuthetic
Syuthetic"
Proseioss
Proteins"
IMDB-Bisary
IMDBB-inary"
HosMMDD
FinsMMDB
D Match igan only)
102+
95-2+
72.2+
50,0+2000
64.4+19775
69.7-2x08
67.8-248
Match (subaree unly)
70.0azar
74,8
1000
82.0
92.9
82.8
100,
72.0
DaMacch
72.7
86.6
100.0
83.4g330
y
100
86.44744
Table 7: The hard dataset details
Synthetic*
Proteins'
Mutag"
Enzymes"
Aids'
IMDB-Binary'
Cox2'
FirstMMDIB
Averuge nodes (target)
40.0
38.8
18.2
31.5
14.7
19.0
41.3
1376.7
Average nodes (query)
15.0
11.4
9.1
15.4
4.4
14.2
15.0
15.0
Average edges (target)
259.5
146.7
40.2
120.6
30.0
177.1
87.0
6141.6
Average edges (query)
67.3
35.5
17.6
52.6
7.1
102.6
29.9
45.6
We also perform the ablation study the Synthetic dataset to test the effect of chordless cycles,as shown in Table gl Results show the chordless cycles boost the performance with limited extra time consumption.
Synthetic
RunTune
Trainingts/epoch)
Inference(s/epoct)
DaMatch
14
19.7s/epoch 10.3/eppcc
SimGNNN
1.732
0.385
Match (wie
72.7
NeuroMatch
2,234
0.311
embed
1.850
GraphSim
3.223
0.433
Table 4: The ablation study of
IsoNet
10.553
1.939
proteins
D Match Subterl)) D Match-Subbooo((S=)
2,940
0.456
3,889
0.581
Sood(O)
100.0
100.0.00
Seed(1)
100.0
10000
Match (Sbure))
4,410
0.673
Seed(2)
100.0
100.0.om
D Match Subtree(S=5)
5.143
D Match GNN
2.678
0.495
Fixed
100.0+0.0
100.0
Match
8.163
1.114
Table 5: Random seed comparison
Table 6: Runtime analysis
A.4 RANDOM EFFECT
Although our experiments do not rely random seeds, random split may affect the results. To test this, we set several random seeds and permute the raw data order before getting the five-fold. We experiment on the Protein and Mutag datasets with trivial random seed 0,1,2 and obtain nearly identical performance. See Table GL
While other methods based on GNNs tend capture the divergence of distributions in the training set and hence are easily affected by randomness, our subtree module performs the matching explic- itly by the degeneracy property, as opposed to modeling data distribution others, hence ours is insensitive to data partitioning.
A.5 RUNTIME ANALYSIS
We add the runtime analysis experiment follows. We compare our method with baselines on the synthetic dataset and record the training and inference time (second) per epoch. The results are shown in Table F
Our model slower than some strong basclines like SimGNN and NeuroMatch in the experiment because they deal with the graph-level representations. Our model is faster than IsoNet, which performs edge-level matching.
We conduct additional ablation study to explore the time consumption of each module in model. The results show that the time consumption our model mainly comes from the sampling in the subtree module whose running time is linearly related the sampling number. When we set
18

---

Under review as a conference paper at ICLR 2023
Table 8: The dataset details
Syathetic
Proteins
Mutag
Enzymes
Aids
IMDB-Binee
Cox2
FirstMDD
Average nodes (target)
40.0
39.1
17.9
33.0
15.7
19.8
41.3
1376.5
Average nodes (query)
15.0
14.4
9.0
14.8
14.6
Average edges (target)
241.7
146.5
39.5
125.6
32,4
193.1
87.0
6144.3
Average odges (query)
50.6
68.9
25.1
75.3
17.1
141.0
42.8
68.1
the sampling number 2, the running time is on par with the others. Furthermore, the running time for the GNN module is the same as for the other baselines. In sum, we observe that our model's scalability acceptable as both complexity analysis and empirical running time show ours is slower than others only by constant factor.
A.6 DATASET DETAILS
We describe the average node number and average edge number of the target graph and query graph in the Table g and Table Q Except the hard datasets, generate 1000 graph pairs for Synthetic, Proteins, Mutag, Enzymes, Cox2 and FirstMMDB and 2000 graph pairs for Aids and IMDB- MuB--Binary which have smaller graph size. For the hard dataset, we uniformly generate 500 graph pairs.
A.7 RESULTS ON MORE DATASETS
We conduct experiments on the OGB benchmark dataset (Hu 2020), including Ogbg moohiv and Oghg-molpch. We follow the same strategy the paper to construct normal and hard versions for these datasets and choose the hest-performing baselines for comparison, including SimGNN and NeuroMatch, We present new results in Table g
We find that model performs slightly better than others on normal datasets while gaining significant advantage over baselines on hard datasets. These results are consistent with our previous experiments, demonstrating that our model exploits the subgraph matching property, rather than simply modeling the divergence of the data distribution as other GNNs.
We experiment continuous features from the MNIST, CIFARIO and PPI datasets, these constructed from vision Mata@wwived et all 2020) or biological information data(Zitmı & Leskoved 2017) We As expected, model achieves consistent performance as well. See Table III
ogo
mothor"
ogh molpeta
ogh molpcta"
SinGNN
054421
81.6ga
86.2
290
17002477
NeumMMachh
98.3
86.0
99.8 jaz0
NeuroMasch
95.1..14
50.0.000
Masch
100,0
D7 March
993 988
08.5.00
Table 9: Obg dataset performance comparison
Table 10: Continues dataset perfor- mance
A.8 COMPARISON WITH EXACT METHOD
we compare exact matching solutions, including VF2[1] and ISMAGS[2). By nature, we know that exact matching methods obtain 100 % accuracy.
As trade-off between accuracy and execution time, we make the comparison inspired by the setup in MeuroMatch et (02I). We say an execution succeeds when its run time less than 60s. We compare the success rate of the exact methods by varying the query graph size from 10 to 50 on the synthetic data, as shown Figure.4.
We show in our experiment that the failure of exact matching methods increases significantly when the target graph has more than 30 nodes, compared to our stable performance, indicating the incom- petence of these methods on large-scale datasets.
19

---

Under review as a conference paper at ICLR 2023
100
100
VF2
ISMAGS
D2Match
Success rate (%)
Accuracy (%)
40
20
20
D2Match
10
15
20
25
Query size
Figure 4: Comparison with exact method
20


Reviews:
[{"review_id": "gNRYCE6fpa9", "reviewer": "Reviewer_9bfF", "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 authors propose a statement that subgraph matching can be degenerated to subtree matching and provide proof. Based on this degeneracy property, the authors propose a matching method that utilizes GNN to model subtrees. Also, they adopt GNN to learn node representations to boost the performance of matching.", "summary_of_the_review": "The paper proposes a novel idea on the degeneracy property of subgraph matching, and the tree-degeneration fits the way of aggregation of GNN. The theoretical results seem novel and interesting. Empirical results show the shortcomings of GNN, which is significant for future research. ", "strength_and_weaknesses": "**Strength:**\n1. The idea of degenerating subgraph matching to subtree matching is novel. The theoretical study is interesting, regarding existing graph matching learning papers are usually empirical.\n2. The proposed method improves performances on 7 experimented datasets, some by a substantial margin.\n3. The empirical results show that GNNs tend to capture the data distribution divergence, and have bad performance on evenly distributed data, motivating further research.\n\n**Weakness:**\n1. The degeneracy property can be broken by simply inserting or removing an edge, so the model can be easily attacked and may not be robust to noise.\n2. The ablation study of GNN shows that the improvement is mainly from the GNN module. Also, the paper does not show the subtree modeling's effect on performance improvement, such as demonstrating recall on experimented datasets.", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "IwOSXGt_Rd", "reviewer": "Reviewer_6wEv", "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": "This main contribution of this paper is that it provides an idea and corresponding theoretical proof about degenerating subgraph matching problem to subtree matching with the help of Graph Neural Network.", "summary_of_the_review": "This study proposes an interesting method with theoretical proof. Experimental results are good. Running experiments on the suggested datasets will strengthen the paper. Writing can be improved. The paper lacks discussions about the application of the proposed method to graphs with continuous node/edge attributes.", "strength_and_weaknesses": "Strength: Theoretical proof and support for each claims mentioned. \n\nWeakness:\n1. The datasets used in the experiments are relative small and old. It will be interesting to see the performance of the proposed method on more recent datasets, such as ogb (https://ogb.stanford.edu/)\n2. Training-test split may have large impact on the performance, e.g., on Mutag and Protein. Please specify the details (e.g., random seeds, how many time the 5-fold CV was run)\n3. It is unclear if the proposed method work for graphs containing edges/nodes with continuous attributes. \n\n\n\n\n\n\n\n\n\n\t From the examples above, they have the same chordless cycle ABC and ACD\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": "Cm9PTEuOVjV", "reviewer": "Reviewer_763b", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This paper identifies a degenerated case of subgraph matching, in which it falls to subtree matching. Then, the matching procedure can be implemented by the built-in tree-structured aggregation mechanism on graph neural networks. The paper proposes a new deep learning method for approximate subgraph matching.", "summary_of_the_review": "Overall, this paper outlines a novel approach for deep learning based subgraph matching. Although I agree with the novelty of the proposed idea, I feel the paper is kind of overclaiming the theoretical contribution of the paper. The paper also needs to evaluate the proposed approach more thoroughly, by including runtime analysis and comparing against exact graph-matching baselines. Finally, the writing of the paper should be improved.\nOverall, I think there is significant room for improving this paper.", "strength_and_weaknesses": "Strength:\n- The proposed idea is novel.\n- The experimental results are strong.\n\nWeakness:\n- The writing of the paper should be improved.\n- Although the paper provides a complexity analysis, the paper should also provide a runtime analysis to compare with baseline approaches. Given that there is an extra operation of converting a graph to a subtree, I assume the proposed method is slower compared to other deep learning based approaches. However, this is not discussed in the paper.\n- Although I understand that this approach is proposed for approximate subgraph matching, I believe the paper should at least include some comparisons with exact subgraph matching methods. Please feel free to skip CO-based methods in settings where they are not applicable.\n- The paper is kind of overclaiming the theoretical contribution of the paper. The paper relaxes the sufficient and necessary conditions to that of necessary only. However, I didn't find a bound or analysis regarding the error introduced in this relaxation.", "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": {}}]

Author rebuttal:

Decision: Reject