Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (1): 43-47.DOI: 10.11772/j.issn.1001-9081.2020060935

Special Issue: 第八届中国数据挖掘会议(CCDM 2020)

• China Conference on Data Mining 2020 (CCDM 2020) • Previous Articles     Next Articles

Subgraph isomorphism matching algorithm based on neighbor information aggregation

XU Zhoubo, LI Zhen, LIU Huadong, LI Ping   

  1. Guangxi Key Laboratory of Trusted Software(Guilin University of Electronic Technology), Guilin Guangxi 541004, China
  • Received:2020-05-31 Revised:2020-07-16 Online:2021-01-10 Published:2020-11-12
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61762027), the Natural Science Foundation of Guangxi (2017GXNSFAA198172).

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

徐周波, 李珍, 刘华东, 李萍   

  1. 广西可信软件重点实验室(桂林电子科技大学), 广西 桂林 541004
  • 通讯作者: 刘华东
  • 作者简介:徐周波(1976-),女,浙江奉化人,教授,博士,CCF高级会员,主要研究方向:符号计算、智能规划、约束求解;李珍(1995-),女,浙江温州人,硕士研究生,主要研究方向:图匹配、图数据挖掘;刘华东(1978-),男,江西瑞金人,讲师,硕士,主要研究方向:图数据表示;李萍(1996-),女,安徽六安人,硕士研究生,主要研究方向:图匹配、图数据挖掘。
  • 基金资助:
    国家自然科学基金资助项目(61762027);广西自然科学基金资助项目(2017GXNSFAA198172)。

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

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

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

CLC Number: