Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning
Authors: Kaiyang Li, Shihao Ji, Zhipeng Cai, Wei Li
Organizations: University of Connecticut, 352 Mansfield Road, Storrs, CT 06269, USA · Georgia State University, 33 Gilmer Street SE, Atlanta, GA 30303, USA
Approximate subgraph matching (ASM) is a task that determines the approximate presence of a given query graph in a large target graph. Being an NP-hard problem, ASM is critical in graph analysis with a myriad of applications ranging from database systems and network science to biochemistry and privacy. Existing techniques often employ heuristic search strategies, which cannot fully utilize the graph information, leading to sub-optimal solutions. This paper proposes a Reinforcement Learning based Approximate Subgraph Matching (RL-ASM) algorithm that exploits graph transformers to effectively extract graph representations and RL-based policies for ASM. Our model is built upon the branch-and-bound algorithm that selects one pair of nodes from the two input graphs at a time for potential matches. Instead of using heuristics, we exploit a Graph Transformer architecture to extract feature representations that encode the full graph information. To enhance the training of the RL policy, we use supervised signals to guide our agent in an imitation learning stage. Subsequently, the policy is fine-tuned with the Proximal Policy Optimization (PPO) that optimizes the accumulative long-term rewards over episodes. Extensive experiments on both synthetic and real-world datasets demonstrate that our RL-ASM outperforms existing methods in terms of effectiveness and efficiency. Our source code is available at https://github.com/KaiyangLi1992/RL-ASM.
Figures & tables
Fig. 1 : An example of approximate subgraph matching, where {(u1,v1),(u2,v2),(u3,v4),(u4,v3)} achieves the best approximate matching from query graph Gq to target graph Gt with the smallest graph edit distance of 1.
Fig. 2 : An illustration of the search process of ASM on (Gq,Gt) . The branch-and-bound search algorithm (Algorithm 1 ) produces a tree structure, where each node represents a state ( st ), the node ID reflects the order in which the state is visited, and each direct edge represents an action ( at ), which adds a node-pair to the current node-node mapping Mt . The search is essentially depth-first with pruning through the lower bound check. The policy (Line 12 of Algorithm 1 ) refers to a node-pair selection strategy, i.e., which state to visit next? The visiting order affects the performance of searching in the tree. For example, if state 6 can be visited before state 1, a better solution can be found in fewer iterations. This means the GED of the current best match currentMiniDist will be smaller, allowing the algorithm to prune more branches in subsequent search steps. Hence, the search efficiency will be higher. When the search completes or a pre-defined search iteration budget is exhausted, the best solution identified by then will be returned. For the clarity of visualization, some nodes and edges in the search tree are omitted.
Fig. 3 : Overview of RL-ASM. RL-ASM consists of two major components: encoder and decoder. The encoder processes node label, mapping info, positional and/or structural encodings by alternating intra- and inter-components L times (with L layers) to extract powerful node representations. The decoder leverages self-attention to node embeddings of Gq to generate a global state representation xst . The action representations are then generated by the product of embeddings of node unext∈Gq (according to ϕ ), learnable weight tensors W3 , and embeddings of unmapped candidate nodes v1,v2,v3 , and v4 from Gt . Subsequently, the representations of state and actions are concatenated, which is fed to a MLP and a softmax classifier to calculate the probability distribution over the actions Pθ(at∣st) .
Fig. 4 : Example graphs that are indistinguishable by MPNN.
Dataset
SYNTHETIC
AIDS
MSRC_21
Email
Target size (nodes)
100
17.03
77.48
1005
Target size (edges)
196
17.58
198.18
25571
Query size (nodes)
15.75
8.09
24.12
13.19
Query size (edges)
18.13
8.24
57.29
60.04
Num. of Node Labels
13
40
27
47
Sampling range of ∣Vq∣
[10, 20]
[6, 10]
[16, 32]
[8, 16]
TABLE I : Statistics of query graphs and target graphs.
Training Stage
Hyperparameter
AIDS
SYNTHETIC
MSRC_21
EMAIL
Hidden Dimension
32
32
32
32
# Encoder Layers
4
4
4
4
Interaction Dimension F
32
32
32
32
Positional and Structural Encodings
RWSE
RWSE
LapPE
RWSE
Imitation Learning
Batch Size
1024
1024
1024
1024
Learning Rate
0.001
0.0005
0.001
0.001
TABLE II : The hyperparameters of RL-ASM used for different benchmark datasets.
Dataset
SYNTHETIC
AIDS
MSRC_21
EMAIL
Noise Ratio
0%
5%
10%
0%
5%
10%
0%
5%
10%
0%
5%
10%
GroundTruth
0.00
1.70
3.39
0.00
1.00
1.67
0.00
3.99
8.03
0.00
3.66
7.32
NeuroMatch [ 45 ]
1.52
4.42
7.96
0.80
3.12
7.49
3.56
11.46
22.43
3.71
17.41
26.51
APM [ 10 ]
0.00
2.45
4.57
0.00
1.24
2.43
0.00
7.46
13.43
0.00
8.11
15.61
ISM-FR
8.14
9.13
11.03
0.79
1.91
2.92
18.50
21.66
26.87
4.97
11.25
13.32
ISM [ 12 ]
7.00
8.35
10.60
0.01
1.04
2.00
17.07
20.69
26.26
4.67
10.74
12.90
TABLE III: Graph Edit Distance (GED) between query graph and its matched subgraph identified from target graph. Note that the “GroundTruth” number denotes the GED between the “noisy” query graph and its corresponding seed query graph sampled from target graph.
Fig. 5 : The probabilities that ISM and our method find the optimal solutions within 600s.
Dataset
SYNTHETIC
Noise-Ratio
0%
5%
10%
RL-ASM w/o node-sorting
0
1.63
3.38
RL-ASM w/o GraphGPS
0
1.67
3.47
RL-ASM
0
1.54
3.18
TABLE IV : Ablation study of design choices on node-sorting and GraphGPS.
Dataset
SYNTHETIC
Noise-Ratio
0%
5%
10%
ASP
0
2.03
4.04
ISM
5.58
7.69
8.51
RL-ASM
0
1.47
3.42
TABLE V : Effectiveness on the random walk sampled dataset.
Fig. 6 : Efficiency on the random walk sampled dataset.