Advanced Search
    Xue Xin, Zhu Tianchen, Sun Qingyun, Zhou Haoyi, Li Jianxin. Efficient Subgraph Matching Algorithm with Graph Neural Network[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202330732
    Citation: Xue Xin, Zhu Tianchen, Sun Qingyun, Zhou Haoyi, Li Jianxin. Efficient Subgraph Matching Algorithm with Graph Neural Network[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202330732

    Efficient Subgraph Matching Algorithm with Graph Neural Network

    • Subgraph matching is an optimization problem in graph, which is to find all matching subgraphs of the query graph in a large target graph. Although subgraph matching is an NP-Hard problem, the problem is common in many fields such as Social Networks, Biochemistry, and Cognitive Science. Backtracking searching algorithms for subgraph matching have high time complexity, and the pruning strategy is essential to reduce the operating time. However, complex expanding in the existing pruning strategy leads to high complexity of time and space. To balance the efficiency and the effectiveness, only limited neighborhood structure information can be used in conflicting judging, which lets lots of useless states pass the pruning judging and wastes time. An efficient, accurate, and adaptive subgraph matching algorithm is proposed. The algorithm captures the detail structure of the whole graph by graph neural network, builds structure connections, and generates pruning possibilities for all candidate searching states. It replaces complex expanding pruning method with inferring by the neural network model to rapidly estimate the probability of pruning during searching. A data sampling mechanism is designed to alleviate the problem of network training collapse. Experiments shows that using our pruning method in traditional backtracking search can improve search efficiency.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return