GERNS: A Graph Embedding with Repeat-Free Neighborhood Structure for Subgraph Matching Optimization

Subgraph matching is used to determine whether a query graph exists within a target graph, and appears in a lot applications of domains including social sciences, chemistry, biology and database systems. Existing subgraph matching approaches can be broadly categorized into two types: exact matching and approximate matching. Due to allowing for slight variations between the target and query graphs, approximate matching has become a more practical solution with the introduce of graph neural networks (GNN). However, when dealing with large-scale target and query graphs, existing GNN-based approximate matching approaches still have to face the challenge that how to further improve the accuracy and promote the query efficiency. Therefore, we propose the GERNS, a graph embedding with repeat-free neighborhood structure for subgraph matching optimization. Through extracting subgraphs from the target graph based on a specified hop count limit, we incorporate and embed a repeat-free neighborhood structure using a two-layer GNN. Then we generate the relation constrains of subgraphs based on vector order embedding to form the embedding space. Finally, approximate subgraph matching can be realized based on graph embedding. Extensive experiments on both public graph datasets and real-world datasets show the effectiveness of our approach.