基于邻居信息聚合的子图同构匹配算法  

Subgraph isomorphism matching algorithm based on neighbor information aggregation

作　　者：徐周波[1] 李珍 刘华东[1] 李萍 XU Zhoubo;LI Zhen;LIU Huadong;LI Ping(Guangxi Key Laboratory of Trusted Software(Guilin University of Electronic Technology),Guilin Guangxi 541004,China)

机构地区：[1]广西可信软件重点实验室(桂林电子科技大学),广西桂林541004

出　　处：《计算机应用》2021年第1期43-47,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61762027);广西自然科学基金资助项目(2017GXNSFAA198172)。

摘　　要：图匹配在现实中被广泛运用,而子图同构匹配是其中的研究热点,具有重要的科学意义与实践价值。现有子图同构匹配算法大多基于邻居关系来构建约束条件,而忽略了节点的局部邻域信息。对此,提出了一种基于邻居信息聚合的子图同构匹配算法。首先,将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习,从而得到聚合后的节点局部邻域信息;然后,根据图的标签、度等特征对匹配顺序进行优化,以提高算法的效率;最后,将得到的特征向量和优化的匹配顺序与搜索算法相结合,建立子图同构的约束满足问题(CSP)模型,并结合CSP回溯算法对模型进行求解。实验结果表明,与经典的树搜索算法和约束求解算法相比,该算法可以有效地提高子图同构的求解效率。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.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]