Improved GCN Model for Inexact Graph Matching

doi:10.3778/j.issn.1673-9418.1907032

Abstract

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模型在图匹配问题上较同类方法具有更高的识别率。

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

LI Changhua, CUI Liyang, LI Zhijie. Improved GCN Model for Inexact Graph Matching[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(8): 1397-1408.

李昌华，崔李扬，李智杰. 用于非精确图匹配的改进GCN模型[J]. 计算机科学与探索, 2020, 14(8): 1397-1408.

References

[1] Cordella L P, Foggia P, Sansone C, et al. A (sub) graph iso-morphism algorithm for matching large graphs[J]. IEEE Tran-sactions on Pattern Analysis and Machine Intelligence, 2004, 26(10): 1367-1372.
[2] Krizhevsky A, Sutskever I, Hinton G. ImageNet classifica-tion with deep convolutional neural networks[C]//Proceed-ings of the 26th Annual Conference on Neural Information Processing Systems, Lake Tahoe, Dec 3-6, 2012. Red Hook: Curran Associates, 2012: 1106-1114.
[3] Abdel-Hamid O, Mohamed A R, Jiang H, et al. Convolu-tional neural networks for speech recognition[J]. IEEE/ACM Transactions on Audio Speech & Language Processing, 2014, 22(10): 1533-1545.
[4] Silver D, Schrittwieser J, Simonyan K, et al. Mastering the game of Go without human knowledge[J]. Nature, 2017, 550(7676): 354-359.
[5] Lin H H, Chuang J H, Liu T L. Regularized background adaptation: a novel learning rate control scheme for Gaussian mixture modeling[J]. IEEE Transactions on Image Processing, 2011, 20(3): 822-836.
[6] Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filter-ing[C]//Proceedings of the 30th Annual Conference on Neural Information Processing Systems, Barcelona, Dec 5-10, 2016. Red Hook: Curran Associates, 2016: 3837-3845.
[7] Simonyan K, Zisserman A. Very deep convolutional networks for large-scale image recognition[J]. arXiv:1409.1556, 2014.
[8] Ren S Q, He K M, Girshick R B, et al. Faster R-CNN: towards real-time object detection with region proposal networks[J]. IEEE Transactions on Pattern Analysis and Machine Intellig-ence, 2017, 39(6): 1137-1149.
[9] Verma N, Boyer E, Verbeek J. Dynamic filters in graph con-volutional networks[J]. arXiv:1706.05206, 2017.
[10] Niepert M, Ahmed M, Kutzkov K. Learning convolutional neural networks for graphs[C]//Proceedings of the 33rd Inter-national Conference on Machine?Learning, New York, Jun 19-24, 2016: 2014-2023.
[11] Bing L. Social network analysis[M]. Berlin, Heidelberg: Spr-inger, 2011.
[12] Chen H, Li C F. Stereoscopic color image quality assessment via deep convolutional neural network[J]. Journal of Fron-tiers of Computer Science and Technology, 2018, 12(8): 1315-1322.陈慧, 李朝锋. 深度卷积神经网络的立体彩色图像质量评价[J]. 计算机科学与探索, 2018, 12(8): 1315-1322.
[13] Scarselli F, Gori M, Tsoi A C, et al. The graph neural net-work model[J]. IEEE Transactions on Neural Networks, 2009, 20(1): 61-80.
[14] Li Y J, Tarlow D, Brockschmidt M, et al. Gated graph sequ-ence neural networks[J]. arXiv:1511.05493, 2015.
[15] Gregor K, Lecun Y. Emergence of complex-like cells in a temporal product network with local receptive fields[J]. arXiv: 1006.0448, 2010.
[16] Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv:1312.6203, 2013.
[17] Henaff M, Bruna J, LeCun Y. Deep convolutional networks on graph-structured data[J]. arXiv:1506.05163, 2015.
[18] Wu B, Liu Y, Lang B, et al. DGCNN: disordered graph con-volutional neural network based on the Gaussian mixture model[J]. Neurocomputing, 2018, 321: 346-356.
[19] Zhang M H, Cui Z C, Neumann M, et al. An end-to-end deep learning architecture for graph classification[C]//Procee-dings of the 32nd AAAI Conference on Artificial Intellig-ence, New Orleans, Feb 2-7, 2018. Menlo Park: AAAI, 2018: 4438-4445.
[20] Debnath A K, Compadre R L L D, Debnath G, et al. Structure-activity relationship of mutagenic aromatic and heteroarom-atic nitro compounds. Correlation with molecular orbital ener-gies and hydrophobicity[J]. Journal of Medicinal Chemistry, 1991, 34(2): 786-797.
[21] Kapucu N, Arslan T, Collins M L. Examining intergovern-mental and interorganizational response to catastrophic dis-asters toward a network-centered approach[J]. Administra-tion & Society, 2010, 42(2): 222-247.
[22] Baglioni M, Geraci F, Pellegrini M, et al. Fast exact and app-roximate computation of betweenness centrality in social net-works[M]//Can F, ?zyer T, Polat F. State of the Art Applica-tions of Social Network Analysis. Berlin, Heidelberg: Springer, 2014: 53-73.
[23] Toivonen H, Srinivasan A, King R D, et al. Statistical evalu-ation of the predictive toxicology challenge 2000-2001[J]. Bioinformatics, 2003, 19(10): 1183-1193.
[24] Sutherland J J, O'Brien L A, Weaver D F. Spline‐fitting with a genetic algorithm: a method for developing classification structure—activity relationships[J]. Journal of Chemical Infor-mation and Computer Sciences, 2003, 43(6): 1906-1915.
[25] Wang Y C, Tian Y J, Deng N Y. Distinguishing enzymes from non-enzymes via support vector machine[C]//Proceed-ings of the 2nd International Symposium on Optimization and Systems Biology, Lijiang, Oct 31-Nov 3, 2008. Beijing: ORSC & APORC, 2008: 166-173.
[26] Duvenaud D, Maclaurin D, Aguilera-Iparraguirre J, et al. Convolutional networks on graphs for learning molecular fingerprints[C]//Proceedings of the 2015 Annual Conference on Neural Information Processing Systems, Montreal, Dec 7-12, 2015. Red Hook: Curran Associates, 2015: 2224-2232.
[27] Borgwardt K M, Kriegel H P. Shortest-path kernels on graphs [C]//Proceedings of the 5th IEEE International Conference on?Data Mining, Houston, Nov 27-30, 2005. Washington: IEEE Computer Society, 2005: 74-81.
[28] Weisfeiler B, Lehman A A. A reduction of a graph to a can-onical form and an algebra arising during this reduction[J]. Nauchno-Technicheskaya Informatsia, 1968, 2(9): 12-16.