Journal of Frontiers of Computer Science and Technology ›› 2020, Vol. 14 ›› Issue (8): 1397-1408.DOI: 10.3778/j.issn.1673-9418.1907032

Previous Articles     Next Articles

Improved GCN Model for Inexact Graph Matching

LI Changhua, CUI Liyang, LI Zhijie   

  1. School of Information and Control Engineering, Xi'an University of Architecture and Technology, Xi'an 710055, China
  • Online:2020-08-01 Published:2020-08-07

用于非精确图匹配的改进GCN模型

李昌华崔李扬李智杰   

  1. 西安建筑科技大学 信息与控制工程学院,西安 710055

Abstract:

Aiming at the problem of mining the features of topology nodes deficiently in the existing inexact graph matching, this paper proposes an improved graph convolutional network (GCN) model for inexact graph matching. Firstly, considering that the selecting nodes should have strong representation, three methods of measuring the centrality of network nodes in the social network analysis are used to obtain the centrality of nodes of graph, and the nodes are sorted based on the size of node centrality. Secondly, for the nodes and edges of graph have corresponding domain features, when mapping the topology to the grid structure, the relationship attributes between the nodes should be maximized. When the node neighborhood size does not meet the receptive field threshold, the centrality is sorted and the neighborhood nodes are sequentially acquired according to the centrality until the neighborhood size meets the receptive field threshold. Then the convolutional neural network is used to classify and identify the graph. Finally, training and testing are performed on multiple standard graph datasets. The experimental results show that the improved GCN model has higher recognition rate than other similar methods in graph matching.

Key words: topology, nodes neighborhood, sort, graph convolutional neural network, imprecise graph matching

摘要:

针对现有图匹配算法对拓扑结构节点特征挖掘不够充分问题,提出了一种用于非精确图匹配的改进图卷积神径网络(GCN)模型。首先,考虑到选取的节点应具有较强的代表性,利用社交网络分析中三种衡量网络节点中心度的方法去获取图中节点的中心度,按照节点的中心度大小排序。其次,针对图的节点和边具有相应的领域特征,把拓扑结构映射到网格结构的同时,应最大化表示节点之间的关系属性,在节点邻域大小不满足感受野阈值时,对节点邻域进行中心度排序并按中心度大小依次获取邻域节点,直到邻域大小满足感受野阈值,进而利用卷积神经网络进行图的分类识别。最后,在多个标准图数据集上进行了训练和测试。实验结果表明,改进的GCN模型在图匹配问题上较同类方法具有更高的识别率。

关键词: 拓扑结构, 节点邻域, 排序, 图卷积神经网络, 非精确图匹配