Sub-GMN: The Subgraph Matching Network Model
  As one of the most fundamental tasks in graph theory, subgraph matching is a
crucial task in many fields, ranging from information retrieval, computer
vision, biology, chemistry and natural language processing. Yet subgraph
matching problem remains to be an NP-complete problem. This study proposes an
end-to-end learning-based approximate method for subgraph matching task, called
subgraph matching network (Sub-GMN). The proposed Sub-GMN firstly uses graph
representation learning to map nodes to node-level embedding. It then combines
metric learning and attention mechanisms to model the relationship between
matched nodes in the data graph and query graph. To test the performance of the
proposed method, we applied our method on two databases. We used two existing
methods, GNN and FGNN as baseline for comparison. Our experiment shows that, on
dataset 1, on average the accuracy of Sub-GMN are 12.21\% and 3.2\% higher than
that of GNN and FGNN respectively. On average running time Sub-GMN runs 20-40
times faster than FGNN. In addition, the average F1-score of Sub-GMN on all
experiments with dataset 2 reached 0.95, which demonstrates that Sub-GMN
outputs more correct node-to-node matches.
  Comparing with the previous GNNs-based methods for subgraph matching task,
our proposed Sub-GMN allows varying query and data graphes in the
test/application stage, while most previous GNNs-based methods can only find a
matched subgraph in the data graph during the test/application for the same
query graph used in the training stage. Another advantage of our proposed
Sub-GMN is that it can output a list of node-to-node matches, while most
existing end-to-end GNNs based methods cannot provide the matched node pairs.
