Research On Subgraph Isomorphism Constraint Solving Technology Based On Graph Representation Learning

Graph,as a structured data structure,is very easy to describe the inline relationship between things.Many data in real life can be expressed by graph.As a query technique,the subgraph isomorphism problem in graph matching has been widely used in social networks,network security,computational biology,chemistry and other fields.The problem of subgraph isomorphism belongs to NP-hard problem,as the scale of its data increases,the complexity of its solution tends to increase exponentially.Graph representation learning,as a representation technology for processing graph data,can efficiently learn feature vectors representing graph structure and attribute information.In addition,for the “combination explosion” problem,the Constraint Satisfaction Problem Model can inhibit to a certain extent.In the technology of graph representation learning and CSP,this paper mainly studies the subgraph isomorphism constraint solving algorithm based on neighbor information aggregation and the subgraph isomorphism filtering algorithm based on random walk graph representation learning.The main tasks are as follows:(1)Most conventional subgraph isomorphism algorithm is constructed based on the neighbor relationship constraint,while ignoring the local neighborhood node information.To solve this problem,a subgraph isomorphism constraint algorithm based on neighborhood information aggregation is proposed.Firstly,optimize the matching order of nodes according to the feature attributes such as the label and degree of the graph to reduce the search branch.Secondly,the aggregation weight constraints by import the pattern graph and the target graph into the improved graph convolutional neural network to get the local neighborhood information of the nodes after aggregation,and build a new model of CSP with isomorphic subgraphs.Finally,the CSP is solved by the CSP backtracking algorithm.Experimental results show that compared this algorithm can effectively improve the efficiency of solving subgraph isomorphisms with the classic algorithm.(2)The edges in graph data usually also have certain practical meanings and attributes in real life.An improved algorithm is proposed to solve the problem that only the node-centered neighborhood information is extracted when the feature is extracted in(1).On the basis of the study in(1),the algorithm converts the graph into an association matrix for description,and uses another set of graph convolutional neural network to aggregate the neighborhood information of its edges and integrate it to obtain the eigenvector containing the local neighborhood information of nodes and edges.Experimental results show that the improved algorithm can further improve the efficiency of solving subgraph isomorphisms.(3)In order to reduce the search space of the problem and reduce unnecessary solutions,a subgraph isomorphism filtering algorithm based on random walk graph representation learning is proposed to preprocess the subgraph isomorphism problem.Firstly,according to the matching characteristics of the subgraph isomorphism problem,a "nearest neighbor" biased random walk strategy is given,which is used for random walk sampling.Secondly,for the attribute characteristics of the graph,node labels are added for training.Finally,the infeasible solutions are filtered by the similarity measure.Experimental results show that the filtering algorithm can effectively reduce the search space to improve the efficiency of problem solving.