Research On Subgraph Isomorphism Symbol Solving Technology Based On Graph Neural Network

As an important data structure,graph can effectively describe the complex relationship between things in the real world.The subgraph matching problem is a fundamental problem in graph data analysis and has important research significance.Since the subgraph matching problem is NP-hard,its computational complexity increases exponentially with the growth of the data size.Therefore,the current research on subgraph matching algorithms focuses on how to improve the time and space efficiency of the algorithm.The graph neural network can effectively aggregate the neighborhood information of the graph nodes,so that the feature vector of the node contains the local neighborhood information.In addition,algebraic decision graph is a highly compact and easy-to-operate implicit storage structure,which can realize the operation of large-scale graphs in a small storage space.Combining graph neural network and algebraic decision diagram technology,this thesis mainly studies the subgraph matching symbol algorithm based on graph neural network and the subgraph isomorphism filtering algorithm based on algebraic decision diagram.The main work is as follows:(1)Aiming at the problem of large search space in existing subgraph isomorphism algorithms,this thesis proposed a subgraph matching symbol algorithm based on graph neural network(SMMGNN).The algorithm used the graph convolutional neural network to obtain the feature vector containing the local neighborhood information of the node,and used the vector as the filter condition to obtain the node candidate set of the query graph.In addition,SMMGNN introduced a symbolic algebraic decision diagram storage structure,which realized the parallel operation of each candidate region and the shared storage of common subgraphs in the data graph.Second,in order to reduce the number of backtracking searches,the calculation method of the matching order was optimized.Experiments show that,compared with the classical algorithm,the algorithm in this thesis significantly improves the solution performance of subgraph matching.(2)Aiming at the problem of ignoring the influence of different adjacent nodes on the central node when extracting feature vectors in(1),an improvement was proposed to the node feature extraction method,and the graph attention neural network was used to extract node features.According to the characteristics of adjacent nodes,the model can assign different weights to adjacent nodes.At the same time,considering the degree centrality of adjacent nodes and the different effects of adjacent nodes of different orders on the central node,the attention coefficient is optimized to extract more critical information.(3)Aiming at the problem that invalid nodes in the candidate set lead to a large number of redundant searches,a subgraph isomorphic filtering algorithm based on algebraic decision diagram was proposed.Firstly,a new coding method of candidate set was presented to use algebraic decision diagram operation to search node candidate set in parallel.Then,based on the matching order of the SSMGNN algorithm,the query graph hierarchy information was considered,and a new matching order was given.Then,the pruning strategy was optimized according to the relationship between query graph nodes and adjacent nodes.Finally,taking the query graph radius as the number of iterations,through repeated iterations,the invalid nodes in the candidate set were completely eliminated and the edge set in the candidate area was reduced.Experiments show that the filtering algorithm can eliminate all invalid nodes in the candidate set and improve the search efficiency.