关键词: 子图同构, 约束满足问题, 图卷积神经网络, 信息聚合, 图匹配

Abstract: Graph matching is widely used in reality, of which subgraph isomorphic matching is a research hotspot and has important scientific significance and practical value. Most existing subgraph isomorphism algorithms build constraints based on neighbor relationships, ignoring the local neighborhood information of nodes. In order to solve the problem, a subgraph isomorphism matching algorithm based on neighbor information aggregation was proposed. Firstly, the aggregated local neighborhood information of the nodes was obtained by importing the graph attributes and structure into the improved graph convolutional neural network to perform the representation learning of feature vector. Then, the efficiency of the algorithm was improved by optimizing the matching order according to the characteristics such as the label and degree of the graph. Finally, the Constraint Satisfaction Problem (CSP) model of subgraph isomorphism was established by combining the obtained feature vector and the optimized matching order with the search algorithm, and the model was solved by using the CSP backtracking algorithm. Experimental results show that the proposed algorithm significantly improves the solving efficiency of subgraph isomorphism compared with the traditional tree search algorithm and constraint solving algorithm.

Key words: subgraph isomorphism, Constraint Satisfaction Problem (CSP), graph convolutional neural network, information aggregation, graph matching