基于图卷积神经网络的图匹配算法研究

宫月君 贺佳佳

摘要：为了进一步解决非精确图匹配中，深度神经网络算法层级之间全连接造成的参数冗余所导致的数量级问题，本文提出利用改进的卷积神经网络实现非精确图匹配算法。首先，利用建筑学与城市规划学科中空间关系理论-空间句法的思路，对图结构数据进行描述，其次对数据进行处理。最后通过在图上定义卷积运算，对图节点的特征信息和结构信息进行端到端的学习，实验表明，该算法能够高效的降低运算的时间，并且有效的提升准确率。

关键词：非精确图匹配;空间句法; 图卷积神经网络

中图分类号：TP393        文献标识码：A

文章编号：1009-3044（2019）18-0191-03

由于现实世界中无处不在的网络，图形分析近年来越来越受到关注。图已被用于表示各个领域的信息，包括生物学，社会科学，和语言学[1]。将实体之间的交互作为图形进行建模，使研究人员能够系统地了解各种网络系统。例如社会关系网络，实体和实体之间可以用图的形式来表示，在这种社会关系网络中查询特定关系的人或团体可以转化为图上指定节点和子图匹配问题。在生物分析领域，通过图匹配技术查询具有已知性质的蛋白质结构，可以快速有效地对未知性质的蛋白质与基因进行辅助分析，为研究生物组织的结构及功能提供了技术手段。

根据调查以往的图匹配研究成果，可分为精确和非精确图匹配两类思路[2]：前者计算过程比较复杂，大多归类为NP难问题;后者则允许在非完全匹配情况下，实现快速分类识别的效果。现有的非精确图匹配方法有二分图匹配[3]、基于BP神经网络的图匹配[4]、以及基于图嵌入的图匹配[5]等诸多成果，其中，图嵌入技术，通过学习图中节点、边或子图的低维向量空间表示。如DeepWalk[6]、LINE[7]、SDNE[8]等方法在网络表示学习领域取得了很大成功，然而，这些方法在计算上较为复杂并且在大规模图上并不是最优的，而GNN旨在解决这些问题，如 21世纪初，研究人员开发了图嵌入算法，作为降维技术的一部分，他们将一组基于邻域的N维点构造一个相似度图，然后将该图的节点嵌入到d维向量空间中，其中，[d?N]。嵌入的思路是保证连接点在向量空间中彼此接近。拉普拉斯特征映射和局部线性嵌入是基于这一原理算法的例子，然而这种方法的主要问题是，其时间复杂度为[OV2].自2010年以来，关于图嵌入的研究已转向可扩展的图嵌入技术，该技术利用了现实世界的稀疏性，图嵌入技术的分类涵盖因式分解[9]、隨机游走[10]和深度学习[11][12]。因此如何在保证精度的同时减少参数冗余，避免高维度数据所引发的应用限制，是图匹配问题研究优化的关键所在。

因此本文借鉴建筑学与城市规划学科中空间关系理论-空间句法的思路对图中的每个节点构造描述图的拓扑特征的量化描述，并融合节点和边领域属性等非拓扑特征[16]，利用统计的方法构造分布于图节点上的特征向量，并以此为桥梁将图节点的特征信息与结构信息在卷积神经网络中进行端到端的学习，进而实现非精确图匹配。

本文的组织结构图如图1所示：

1 数据集的特征空间表示

1.1 节点拓扑特征的表示

利用建筑学与城市规划学科中的空间句法理论，构造适合于非精确图匹配的图节点的结构信息。本文采用的空间句法变量[14]有连接值、控制值、集成度、可理解度。因为连接值、控制值、平均深度值以及集成度都是在邻接矩阵的基础上得到的，因此维数与节点数相同。

1.2数据预处理

本文利用节点的特征对中心节点的邻域进行随机采样，作为图卷积网络的输入。

2 卷积神经网络的图匹配算法

2.1算法描述

卷积神经网络（CNN，Convolutional Neural Network）属于神经网络的一种[15]，是近年来高速发展的一类高效的机器学习算法。本文是在卷积神经网络的基础上，结合建筑学与城市规划学科中空间关系理论-空间句法，将图数据进行特征表达，其次，将图数据通过预处理。最后，将数据放入卷积神经网络进行训练。

2.2改进的算法原理

该算法的原理步骤如下：

（1）数据的准备：首先将已有的xml格式的图数据，利用空间句法的知识，进行节点的特征表示，其次，将特征矩阵进行数据预处理。

（2）卷积层：卷积层的作用是聚合传递过来的邻居节点的特征[13]，然后在迭代的最后一层进行引入readout函数，该函数的作用是从局部特征映射到全局特征，来聚合节点特征获得全局特征。

（3）激活函数：

卷积运算是一种线性运算，所以，卷积操作只能表达和模拟线性映射关系。本文使用ReLU函数[18]该函数的优点主要有：当[x<0]时，输出恒为0，可以增加网络稀疏性，提高泛化能力;当[x>0]时，其梯度恒为1，解决了梯度饱和的问题，收敛会比较快;数学表达式简练，便于运算。

（4）全连接层：本文的全连接层主要是将特征表示映射到输入数据的标记空间。

（5）softmax层：softmax可以理解为归一化[19]，如待分类的文本一共有N个类别，那么，经过softmax层的输出就是一个N维的向量。

（1） 反向传播算法

根据神经网络的实际输出和期望输出之间的误差来决定网络各层之间连接权值的调整方向和步长。从最后输出层的误差开始，利用链式求导法则计算损失函数对权值与偏置的偏导数，将一定比例的误差分配给每个权值。误差反向传播之后，利用梯度下降学习算法对权值进行上下调整以减少误差。

由于学习的图函数具有非凸性，本文采用RMSProp[21]算法，该算法是在AdaGrad[17]算法的基础上的改进，以在非凸设定条件下更好。

训练流程如图2所示：

3 实验结果与分析

本文的实验平台采用Intel（R）Xeon E5-2603 CPU处理器，主频为1.7GHz（2处理器），内存64GB，NVIDIA Quadro P2000显示卡，Windows10操作系统以及以下软件环境。

① Anconda3，Python版本：64位版本的Python 3.5。

② Visual Studio版本：VS2015 with Update 3。

③ CUDA版本：CUDA 8.0。

④ CuDnn版本：CuDnn 6.0

⑤ Tensorflow GPU

本文实验数据来源为伯尔尼大学基于图形模式识别和机器学习的IAM图形数据库的知识库（IAM Graph DataBase Repository）[22]，所有的图数据均使用XML文件格式进行记录。本文从IAM图形数据库选择AIDS和GREC数据库进行实验，GREC数据集是由表示建筑和电子图纸符号的图形组成。是根据每幅图像的失真水平，应用侵蚀、膨胀或其他形态学方法进行的操作处理，通过描绘线条并检测交点和拐角，从而得到的去噪图像中提取图的结构。AIDS数据集是由代表分子化合物的图组成，包括活跃与不活跃两个类别，通过将原子表示为节点而将共价键表示为边缘，将分子直接转换为图的形式。XML文件中主要包含了node，edge，node-symbol，node-labels，node-charge以及edge-valence等相关属性。根据当前特征空间构成，下表1给出了AIDS及GREC数据集的部分特征信息的情况，其中class-Num为类别数，maxnode-Num平均节点数，maxedge-Num为平均边数，labels_Num为实验选取的标签数：

在本文中的图卷积神经网络图匹配算法实验中，为了使模型达到最优，本文采用不同的参数对图卷积神经网络进行调节。通过实验，我们发现当Dropout的参数设为0.8的时候，同时学习率调整为0.01时准确率能达到最高。本文还设置了不同的卷积层数，对准确率的结果产生了不一样的影响，如图3和图4分别表示了不同的层数对性能的影响。从图3和图4中可以看出，准确率并不是随着层数的增加而增加。

本文在分析图卷积神经网络实验中使用准确率（Accuracy_rate）指标用来衡量图匹配算法的性能，通过下图4和图5可以看出，随着迭代次数的增加，准确率持续的上升，当迭代次数在180到200区间时，算法的准确率能达到平稳。

4 结束语

本文使用了一种基于图卷積神经网络图匹配算法，在融合了图的全局拓扑特征的基础上，进行数据预处理。其次通过卷积运算将不同层的节点本身及其邻居的特征进行聚合，最后通过反向传播进行参数的更新进而完成分类任务。该算法有效地解决了全链接造成的参数冗余，以及在反向传播中的梯度消失问题。同时避免了传统算法所面临的维数灾难问题。

经实例验证，本文算法以往研究方法的基础上，均达到了有效的提升，对AIDS数据集上的识别准确率最高，达到了98.5%，从而证明了该算法的可行性和有效性。

参考文献：

[1] 于静， 刘燕兵， 张宇，等. 大规模图数据匹配技术综述[J].计算机研究与发展，2015， 52（2）：391-409.

[2] 严骏驰. 图匹配问题的研究和算法设计[D].上海交通大学，2015.

[3] 邓水光， 尹建伟， 李莹，等. 基于二分图匹配的语义Web服务发现方法[J].计算机学报，2008， 31（8）：1364-1375.

[4] 强保华， 陈凌， 余建桥，等.基于BP神经网络的属性匹配方法研究[J].计算机科学，2006， 33（1）：249-251.

[5] Goyal P， Ferrara E. Graph Embedding Techniques， Applications， and Performance： A Survey[J]. Knowledge-Based Systems， 2018.

[6] Perozzi B， Al-Rfou R， Skiena S. DeepWalk：online learning of social representations[C]Acm Sigkdd International Conference on Knowledge Discovery & Data Mining， 2014.

[7] Tang J ， Qu M ， Wang M ， et al. LINE： Large-scale information network embedding[J]. 24th International Conference on World Wide Web， WWW 2015， 2015.

[8] Wang D， Peng C， Zhu W. Structural Deep Network Embedding[C]Acm Sigkdd International Conference on Knowledge Discovery & Data Mining. 2016.

[9] Ahmed A， Shervashidze N， Narayanamurthy S， et al. Distributed large-scale natural graph factorization[C]// International Conference on World Wide Web. 2013.

[10] Fouss F， Pirotte A， Saerens M. A Novel Way of Computing Similarities between Nodes of a Graph， with Application to Collaborative Recommendation[C]// IEEE/WIC/ACM International Conference on Web Intelligence. 2005.

[11] Wang D， Peng C， Zhu W. Structural Deep Network Embedding[C]// Acm Sigkdd International Conference on Knowledge Discovery & Data Mining. 2016.

[12] Cao S， Wei L， Xu Q. Deep neural networks for learning graph representations[C]// Thirtieth Aaai Conference on Artificial Intelligence. 2016.

[13] Hamilton W L ， Ying R ， Leskovec J . Inductive Representation Learning on Large Graphs[J]. 2017.

[14] 张愚， 王建国. 再论“空间句法”[J]. 建筑师， 2004（3）：33-44.

[15] 周飞燕，金林鹏，董军.卷积神经网络研究综述[J].计算机学报，2017， 40（6）：1229-1251.

[16] 李智杰，李昌华，刘欣.融合拓扑特征和领域特征的非精确图匹配算法[J].计算机应用与软件，2015.

[17] Mehta N A， Rendell A， Varghese A， et al. CompAdaGrad： A Compressed， Complementary， Computationally-Efficient Adaptive Gradient Method[J]. 2016.

[18] Schmidthieber J. Nonparametric regression using deep neural networks with ReLU activation function[J]. 2018.

[19] Jang E， Gu S， Poole B. Categorical Reparameterization with Gumbel-Softmax[J]. 2016.

[20] Srivastava N， Hinton G， Krizhevsky A， et al. Dropout： a simple way to prevent neural networks from overfitting[J]. Journal of Machine Learning Research， 2014， 15（1）：1929-1958.

[21] Mukkamala M C， Hein M. Variants of RMSProp and Adagrad with Logarithmic Regret Bounds[J]. 2017.

[22] Riesen K， Bunke H. IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[C]// Structural， Syntactic， & Statistical Pattern Recognition， Joint Iapr International Workshop， Sspr & Spr， Orlando， Usa， December. 2008.

[23] 李航.統计学习方法[M].北京：清华大学出版社，2012.

【通联编辑：唐一东】