Research On Symbolic Algorithms For Graph Pattern Matching Based On Constraint Framework

As a data structure,a graph can effectively describe the relationship between things.Many complex application scenarios in real life can be abstracted using the graph data structure.The graph matching problem is to find a mapping function between two graphs,which can guarantee the structural similarity between the query graph and the data graph.As a basic problem in graph matching,subgraph matching has important research significance.Traditional subgraph matching algorithms are subject combinatorial complexity constraints.As the data size increases,the time complexity of the algorithm will also increase exponentially.Constraint Satisfaction Problem model provides a general solution framework and an effective solution strategy for combinatorial optimization problems,and combines the characteristics of Algebraic Decision Diagrams（ADD）,which are efficient,compact and easy to operate,and uses symbolic techniques to carry out matching model.Implicit description is a feasible strategy to reduce the combinatorial complexity in the subgraph matching problem.At the same time,parallel constraint processing between Algebraic Decision Diagrams can effectively speed up the search and reduce the space requirement of the problem.Therefore,on the basis of CSP and Algebraic Decision Diagrams,this paper studies the algorithm for solving subgraph isomorphism based on symbolic techniques,and extends this technique to the solution of multi-subgraph matching problems.The specific research content is as follows:（1）For the existing subgraph matching algorithms,serial matching is performed according to the order of nodes,and each matching needs to make constraint judgments on the nodes in the candidate set one by one,which will lead to the algorithm having exponential performance in the worst case.The time complexity limits the solution efficiency of the algorithm.In view of the fact that the same constraints are used for each evaluation of candidate nodes,this paper proposes the DDSubISO algorithm,which combines the ADD symbolic operation with the heuristic search pruning strategy,and proposes multiple parallel symbolic constraint solving strategies.Realize the parallel constraint processing of all candidate points during the search process,which significantly improves the solution efficiency of the subgraph matching algorithm on a single-core processor.（2）The multi-subgraph matching problem is an extended form of the subgraph matching problem,which aims to accelerate the efficiency of matching by utilizing common subgraphs between query graphs.Aiming at the high time complexity of pairwise similarity detection and the high space complexity of storing query intermediate results in multi-subgraph matching query,this paper proposes a new multi-subgraph matching symbolic algorithm.By introducing graph neural network technology to pre-group query graph sets,the complexity of graph similarity detection is reduced;Algebraic Decision Diagrams（ADD）are used to store and represent query graphs and data graphs,reducing the complexity of storage space.In order to further improve the detection efficiency of effectively shared subgraphs,a new maximum common connected subgraph notation algorithm DDMCS is proposed.Finally,the improved subgraph matching symbolic algorithm SSMGNN_MQOis used to solve the multi-subgraph matching problem,which improves the solution efficiency of multi-subgraph matching.In order to further improve the solving efficiency of multi-subgraph matching algorithm,the DDSubISO algorithm proposed in（1）is modified to replace the subgraph matching symbol algorithm SMMGNN_MQO.Because the output result of DDSubISO algorithm is the implicit expression of the solution,it not only has better solving efficiency than SMMGNN_MQOalgorithm,but also helps to embed the subgraph isomorphic solution set of the common subgraph into the query graph efficiently and conveniently,so as to further improve the solving efficiency.