基于邻域选择策略的图卷积网络模型

陈可佳　杨泽宇

摘 要：邻域的组成对于基于空间域的图卷积网络（GCN）模型有至关重要的作用。针对模型中节点邻域排序未考虑结构影响力的问题，提出了一种新的邻域选择策略，从而得到改进的GCN模型。首先，为每个节点收集结构重要的邻域并进行层级选择得到核心邻域;然后，将节点及其核心邻域的特征组成有序的矩阵形式;最后，送入深度卷积神经网络（CNN）进行半监督学习。节点分类任务的实验结果表明，该模型在Cora、Citeseer和Pubmed引文网络数据集中的节点分类准确性均优于基于经典图嵌入的节点分类模型以及四种先进的GCN模型。作为一种基于空间域的GCN，该模型能有效运用于大规模网络的学习任务。

关键词：图卷积网络;邻域选择策略;图嵌入;节点分类;半监督学习

中图分类号： TP311文献标志码：A

文章编号：1001-9081（2019）12-3415-05

DOI：10.11772/j.issn.1001-9081.2019071281

Graph convolutional network model using neighborhood selection strategy

CHEN Kejia1，2， YANG Zeyu， LU Hao1，2

1. School of Computer Science， Nanjing University of Posts and Telecommunications， Nanjing Jiangsu 210046， China;

2. Jiangsu Key Laboratory of Big Data Security and Intelligent Processing， Nanjing Jiangsu 210046， China

Abstract： The composition of neighborhoods is crucial for the spatial domain-based Graph Convolutional Network （GCN） model. To solve the problem that the structural influence is not considered in the neighborhood ordering of nodes in the model， a novel neighborhood selection strategy was proposed to obtain an improved GCN model. Firstly， the structurally important neighborhoods were collected for each node and the core neighborhoods were selected hierarchically. Secondly， the features of the nodes and their core neighborhoods were organized into a matrix. Finally， the matrix was sent to deep Convolutional Neural Network （CNN） for semi-supervised learning. The experimental results on Cora， Citeseer and Pubmed citation network datasets show that， the proposed model has a better accuracy in node classification tasks than the model based on classical graph embedding and four state-of-the-art GCN models. As a spatial domain-based GCN， the proposed model can be effectively applied to the learning tasks of large-scale networks.

Key words： Graph Convolutional Network （GCN）; neighborhood selection strategy; graph embedding; node classification; semi-supervised learning

0 引言

圖或网络广泛存在于日常生活中，是抽象现实世界中对象与对象之间关系的一种重要数据结构。如作者之间的引用关系、个人之间的社交关系、城市之间的物流和交通关系、蛋白质之间的交互关系等数据都可以通过图或网络抽象地表达。对这类数据的分析和建模能够挖掘丰富的潜在信息，可广泛应用于节点分类、社区发现、链接预测、推荐系统等任务。

传统的网络表示（如邻接矩阵）存在结构稀疏和维度过高的问题，难以有效地学习。而手动抽取网络的结构特征（如共同邻居数）需要丰富的领域知识，根据网络特点人工选择有效的特征，因此不具有普适性。直觉上来看，在网络中拓扑结构相似的节点也应该具有相近的向量表示[1]。因此，研究者开始学习图或网络的内在表示形式，自动融合网络的结构特征和节点的内在特征。之后，这些学得的特征能够更好地用于各类学习任务。由于网络表示学习研究具有重要的学术价值和应用背景，近年来吸引了大量研究者的关注，出现了诸如DeepWalk[2]、node2vec[3]、大规模信息网络嵌入（Large-scale Information Network Embedding， LINE） [4]等一系列经典而有效的算法。

最近，研究者尝试将卷积神经网络（Convolutional Neural Network， CNN）用于图数据的处理，进行了图卷积网络（Graph Convolutional Network， GCN）机器学习范式的研究，并已取得阶段性的成果。CNN具有自动抽取高阶语义和自动编码降维的优势，在图像分类[5]、目标检测[6]等图像处理任务中表现突出。图像数据具有规则的栅格结构（图1（a）），CNN通过固定的卷积核扫描整幅图像，获得卷积核覆盖范围内的局部信息，通过训练获得卷积核参数，实现特征的自动抽取。然而，图数据一般不具备规则的空间结构，每个节点的连接数量不尽相同（图1（b）），因此CNN的平移不变性在图上不再适用，需要为待编码节点选择固定数量且有序的近邻节点，以满足传统卷积的输入要求。

已有的GCN方法大致可以分为两类：第一類是基于谱域的卷积，也是GCN的理论基础。经典的工作如：Bruna等[7]通过傅里叶变换将图拉普拉斯矩阵进行特征分解，之后再进行图卷积，但该方法的复杂度较高;Defferrard等[8]使用切比雪夫多项式逼近谱图滤波器，降低了算法复杂度;Kipf等[9]提出谱图滤波器的一阶线形逼近，进一步简化了计算。基于谱域的卷积方法受谱图理论限制，因此难以有效扩展至大规模网络中。第二类是基于空间域的卷积，与基于谱域的卷积相比具有较好的扩展性。经典的方法如：Niepert等[10]提出的方法PATCHY-SAN（Patch Select-Assemble-Normalize），在预处理时对所有节点的重要程度和相似程度进行编号，但编号固定导致后续难以通过堆叠卷积层获取更多的信息;Velickovic等[11]提出图关注网络（Graph ATtention network， GAT），在卷积的过程中引入了注意机制以学习不同近邻节点的权重，得到改进的GCN;还有Gao等[12]提出的大规模可学习图卷积神经网络（large-scale Learnable GCN， LGCN），通过对邻居节点的单个特征值大小进行排序以实现数据预处理，训练时采用传统的卷积。

在基于空间域的GCN模型中，节点的邻域组成较为简单，通常由一阶邻居节点组成，而忽视了二阶乃至高阶邻居节点;此外，邻居节点的排序也仅仅根据节点的自身属性，而没有考虑到节点的结构重要性。因此，为获得找到更有效的邻域序列，本文提出了一种基于邻域选择策略的GCN模型——CoN-GCN（Core Neighbors-GCN）。该模型主要工作在于提出了一种启发式的邻域选择策略，为待编码节点选择重要的邻域节点并分级采样得到固定数量的核心邻域节点。经过初步编码后，将节点及其邻域的特征矩阵送入卷积层，和传统GCN模型一样进行半监督的节点分类。通过为每个节点聚合其邻域节点的特征，能够学得该节点的有效嵌入表示。

1 相关工作

由于基于空间域的卷积更易扩展，最近得到研究者的密切关注，也出现了许多新的方法。

一些方法着重于采样策略的设计，例如：PATCHY-SAN方法[10]使用图形标记方法（如Weisfeiler-Lehman核[13]）为节点分配序号，在每个节点vi的k步邻域Nk（i）中选择固定数量的节点定义vi的“接收场”，然后采用标准的1-D CNN并进行归一化处理。不过该方法依赖于图形标记过程，并且节点排序策略较为简单。PinSage方法[14]是在图上进行随机游走以改进邻域采样方法，在真正的超大规模网络中具有良好的性能。在FastGCN方法[15]中，研究者不是对每个节点的邻居进行采样，而是将图卷积操作视为积分过程，按照生成的积分函数对每个卷积层中的节点进行采样。

另一些方法设计如何聚合邻居节点的特征，例如：图采样与聚合（Graph Sample and AGgrEgate， GraphSAGE）算法[16]提出了一种邻居节点特征聚集方法，每个节点都采样固定数量的邻居，通过聚集邻居节点的特征更新当前节点的特征。随着模型层数的增加，每个节点可以获取到距离更远的节点信息。LGCN[12]使用了对邻居节点特征值排序的方式进行聚合，首先将节点及其邻域整合为一个矩阵，并按特征值的大小对每列元素进行排序，不过该方法改变了节点的原始特征，可解释性较差。GAT方法[11]采用注意力机制学习相邻节点的特征权重并聚合，每一个节点由局部过滤器得到所有的相邻节点，并通过度量每个邻居节点与中心节点之间特征向量的相关性来获得不同的权重。

此外，还有一些方法对卷积的过程进行设计，例如：跳跃知识网络（Jumping Knowledge Networks， JK-Nets）[17]将所有中间层的信息跳至输出层，使得模型有选择性地学习全局和局部结构，解决了GCN模型随层数加深而效果变差的问题。 双图卷积网络（Dual GCN， DGCN）[18]基于全局一致性和局部一致性的概念，采用基于邻域节点和基于邻域扩散的双图卷积模式，通过引入无监督时间损失函数将两个网络进行整合。

2 本文模型CoN-GCN

本文提出了一种基于空间域的GCN模型CoN-GCN，其伪代码见算法1。该模型的重点在于如何设计新的采样策略，以更好地聚合邻域节点的特征。首先为待编码节点选择核心邻域节点，随后将待编码节点及其核心邻域节点的特征矩阵送入深度CNN中进行训练，最终实现节点分类任务。其中，核心邻域节点的选择可分为两步：第一步是根据结构紧密度获得每个待编码节点的候选邻域节点序列;第二步是从候选邻域节点序列中为待编码节点按级数从小到大选择k个固定数量的核心邻域节点。

2.1 邻域节点重要性排序

假设图中的每个节点v有M个描述特征，即每个节点可以表示为x∈R1×M，其中，x=〈x1，x2，…，xM〉。令v0表示待编码的节点，xv0i表示v0的第i个特征（i=1，2，…，M）。为了获得v0的核心邻域节点，需要先对候选节点的重要性进行排序，得到v0的候选邻域节点序列N（v0）。为将本文提出的算法应用范围扩展到仅有连接关系而没有具体特征值的数据集上，采用了结构优先原则，具体为：

1）计算网络中所有节点与中心节点之间的结构度量作为关系紧密度，值越高则说明该节点对于中心节点越重要。其中，结构度量可使用共同邻居数[19]、Jaccard系数[20]、Adamic/Adar系数[21]等常用指标，相关计算式如下。

其中Γ（v）表示节点v的1阶邻居节点集合。

2）如果序列中出现结构度量值相同的节点，表示从结构上看这些候选节点对中心节点同等重要。为进一步区分它们的重要性，本文采用距离度量方法，即在节点的外部特征向量空间中，按候选节点与中心节点之间距离进一步判定候选节点的重要程度，距离越小候选节点越重要。式（4）表示欧氏距离度量：

Dist（v0，vk）=（∑Mi=1（xvki-xv0i）1/2; vk∈N（v0）

（4）

考虑到节点特征的稀疏性问题，算法1先对v0进行降维（第1）行），第4）～5）行实现了邻域节点重要性排序。第4）行是根据结构重要性对候选节点排序。第5）行表示在结构重要性一致的情况下，使用特征相似度对候选节点序列进一步调整。

2.2 核心邻域节点的选择

传统CNN要求卷积对象的每次输入格式固定，因此需要确定k个最核心的邻域节点，组成C（v0）。在邻域节点重要性排序后，可能出现高阶邻居节点排在低阶邻居节点之前的情况。此外，还可能存在节点的邻居数量较少而无法获得足够核心邻域节点的情况。因此，本文采用层级扩展策略：先对低阶邻居节点按重要性顺序采样，再逐步进入高阶邻居节点层采样，直至C（v0）达到k为止。当遇到候选节点的结构重要度为0而C（v0）还未达到k时，则由序列中的第一个节点补足。

算法1中的第7）～11）行表示核心邻域选择过程。Select （·）表示从C（v0）中选出当前层的邻居序列。

2.3 1-D CNN生成节点嵌入

经过上述操作，本文获得了维度固定且高度有序的矩阵结构V0∈R（k+1）×M，随后使用1-D卷积核进行特征抽取，将核心邻域节点的信息向待编码节点进行整合。多次卷积操作之后，v0节点编码为x∈R1×m，即节点维度从M维变为m维。

算法1中的第12）行描述了通过1-D CNN得到节点v0的嵌入表示。STACK（·）表示将v0和C（v0）的特征向量按行进行拼接。

图2为CoN-GCN单层卷积过程示例，左侧部分即为核心邻域节点的采样（k=4，M=4）。图例中，结构重要度通过Jaccard系数判定。当Jaccard系数相同，如图中JC（v1）=JC（v2），根据式（4），v1比v2更接近v0，因此v1的特征向量排在v2前面。随后，将中心节点v0的原始向量放在首行，按顺序拼接核心邻域节点的外部特征向量，构造出由k+1个向量组成的矩阵结构。图2的右侧部分表示使用两层1-D CNN对其进行操作，两层卷积核的数量分别为n和m。其中，1-D CNN也可采用其他CNN模型。

2.4 深度CoN-GCN

单层CoN-GCN中聚合的是经过选择的邻域节点的信息，较为有限。为了获得更好的特征，本文还提供了更深的CoN-GCN模型，如图3所示，能够逐步聚合更远节点的信息。CoN-GCN的堆叠数量一般取决于任务的复杂性，如类的数量、图中节点的数量等参数。为了提升CoN-GCN模型性能并促进训练过程，本文在堆叠的过程中加入了前层信息。在整个模型的最后使用全连接层完成对全部节点信息的收集，并通过softmax函数得到节点分类结果。

在算法1中，外层循环（第3）行）描述了这一过程。CAT（·）表示将特征向量按列进行拼接。

3 实验结果与分析

本章比较了CoN-GCN与经典的节点嵌入方法DeepWalk[2]以及四种近期提出的GCN方法[8-9，12，22]在节点分类任务上的准确性，并针对不同的结构度量指标和不同的超参数k进行了性能对比实验。

3.1 数据集

本文使用了Cora、Citeseer和Pubmed三个标准数据集，统计信息见表1。这三个数据集均为引用被引用网络数据集，其中节点表示论文，边表示引用关系。每个节点的特征为该论文的词袋表示（bag of words）。为了便于比较，所有方法均采用了相同的实验设置：对于每个类，20个节点用于训练，500个节点用于验证，1000个节点用于测试。

实验进行了直推学习（transductive learning）下的节点分类任务。直推学习是一种半监督学习算法，在节点分类任务中，由于数据集里仅存在一部分有类别标签的节点，该方法可以在训练过程中使用其他节点（包括测试节点）的特征以及节点间的连接关系。

3.2 实验设置

由于数据集中节点的特征维度较高，实验使用了GCN算法[9]将特征降维至32维。在分类准确性的比较实验中，本文在三种结构度量指标（CN、JC、AA）下均进行了CoN-GCN方法的实验，并将核心节点数k设置为8。在Cora、Citeseer和Pubmed中，CoN-GCN的層数分别为2、1和1。最后使用一个全连接层用于节点分类和预测。在全连接层之前，本文对特征进行拼接。为了防止过拟合，输入层使用失活率为0.16的Dropout算法，卷积层使用L2正则化（λ=0.0005）。在训练过程中，本文使用Adam优化器对训练速度进行优化，学习率为0.1，当验证集错误率出现持续上升时，则停止训练。

3.3 节点分类比较结果与分析

表2给出了不同方法（DeepWalk[2]、Planetoid[22]、Chebyshev[8]、GCN[9]、LGCN[12]、CoN-GCNCN、CoN-GCNJC、CoN-GCNAA）在节点分类中运行10次得到的平均准确率。实验结果表明，CoN-GCN模型在不同数据集的节点分类任务中的表现均优于其他模型，验证了本文邻域采样策略的有效性。在对比算法中，GCN等由于所使用的种子固定具有复现性，而LGCN等不具备复现性，同时为了观察不同结构度量对于邻域选择的影响，还比较了本文方法在三种配置下（CoN-GCNCN、CoN-GCNJC和CoN-GCNAA）的实验结果，发现总体上CoN-GCNCN表现更好，这表明共同邻居数依然是最有效的结构相似性度量方法。Admic/Adar系数表现较差，可能的原因是该系数常用于度量社交网络的节点结构相似性，而不太适用于引用被引用网络。

3.4 超參数k的影响

为了观察不同超参数k对CoN-GCN的影响，本文对多个k值（k=4，6，8，10，12，14，16）分别进行了实验，观察CoN-GCN在三个数据集上的分类结果变化情况，结果如图4所示。

实验结果表明，当k=8时，CoN-GCN模型在所有三个数据集中均具有良好的表现。经过统计可知，Cora、Citeseer和Pubmed数据集的平均节点度分别为4、5和6。从实验结果推测，k值通常可选择比网络平均节点度稍大的值。图4中，当k值过大时，模型的性能有所下降。可能的原因是核心邻域节点中存在过多的零向量，而简单的填充操作会降低卷积的特征提取能力。

4 结语

本文提出了一种基于空间域的图卷积模型——CoN-GCN，通过邻域采样策略实现对通用图数据的处理，然后进行常规的卷积操作。实验结果表明，在直推学习节点分类任务中， CoN-GCN具有更优的准确率。接下来的工作中，我们将继续探讨CoN-GCN的深度对于分类性能的影响，并在更多任务（如链接预测、社团检测等）中考察CoN-GCN的鲁棒性。此外，我们还将继续探讨异质信息网络[23]中的CoN-GCN模型。

参考文献 （References）

[1]涂存超，杨成，刘知远，等.网络表示学习综述[J].中国科学：信息科学，2017，47（8）：980-996.（TU C C， YANG C， LIU Z Y， et al. Network representation learning： an overview [J]. SCIENTIA SINICA Informationis， 2017， 47（8）： 980-996.）

[2]PEROZZI B， AL-RFOU R， SKIENA S. DeepWalk： online learning of social representations [C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2014： 701-710.

[3]GROVER A， LESKOVEC J. Node2Vec： scalable feature learning for networks [C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2016： 855-864.

[4]TANG J， QU M， WANG M， et al. LINE： large-scale information network embedding [C]// Proceedings of the 24th International Conference on World Wide Web. New York： ACM， 2015： 1016-1077.

[5]DENG J， DONG W， SOCHER R， et al. ImageNet： a large-scale hierarchical image database [C]// Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2009： 248-255.

[6]REN S， HE K， GIRSHICK R， et al. Faster R-CNN： towards real-time object detection with region proposal networks [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2017， 39（6）： 1137-1149.

[7]BRUNA J， ZAREMBA W， SZLAM A， et al. Spectral networks and locally connected networks on graphs [EB/OL]. [2018-10-13]. https：//arxiv.org/pdf/1312.6203.

[8]DEFFERRARD M， BRESSON X， VANDERGHEYNST P. Convolutional neural networks on graphs with fast localized spectral filtering [C]// Proceedings of the 30th Conference on Neural Information Processing Systems. New York： JMLR， 2016： 3837-3845.

[9]KIPF T N， WELLING M. Semi-supervised classification with graph convolutional networks [EB/OL]. [2018-11-20]. https：//arxiv.org/pdf/1609.02907.

[10]NIEPERT M， AHMED M， KUTZKOV K. Learning convolutional neural networks for graphs [C]// Proceedings of the 33nd International Conference on Machine Learning. New York： PMLR， 2016： 2014-2023.

[11]VELICKOVIC P， CUCURULL G， CASANOVA A， et al. Graph attention networks [EB/OL]. [2018-09-10]. https：//arxiv.org/pdf/1710.10903.

[12]GAO H Y， WANG Z， JI S. Large-scale learnable graph convolutional networks [C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2018： 1416-1424.

[13]SHERVASHIDZE N， SCHWEITZER P， VAN LEEUWEN E J， et al. Weisfeiler-Lehman graph kernels [J]. Journal of Machine Learning Research， 2011， 12（9）： 2539-2561.

[14]YING R， HE R， CHEN K， et al. Graph convolutional neural networks for web-scale recommender systems [C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2018： 974-983.

[15]CHEN J， MA T， XIAO C. FastGCN： fast learning with graph convolutional networks via importance sampling [EB/OL]. [2018-12-20]. https：//arxiv.org/pdf/1801.10247.

[16]HAMILTON W， YING Z， LESKOVEC J. Inductive representation learning on large graphs [C]// Proceedings of the 2017 Conference on Neural Information Processing Systems. San Mateo， CA： Morgan Kaufmann， 2017： 1024-1034.

[17]XU K， LI C， TIAN Y， et al. Representation learning on graphs with jumping knowledge networks [C]// Proceedings of the 35th International Conference on Machine Learning. New York： JMLR， 2018： 5453-5462.

[18]ZHUANG C， MA Q. Dual graph convolutional networks for graph-based semi-supervised classification [C]// Proceedings of the 2018 World Wide Web Conference. New York： ACM， 2018： 499-508.

[19]LYU L， ZHOU T. Link prediction in complex networks： a survey [J]. Physica A： Statistical Mechanics and its Applications， 2011， 390（6）： 1150-1170.

[20]JACCARD P. The distribution of the flora in the alpine zone [J]. New Phytologist， 1912， 11（2）： 37-50.

[21]ADAMIC L， ADAR E. How to search a social network [J]. Social Networks， 2005， 27（3）： 187-203.

[22]YANG Z， COHEN W W， SALAKHUTDINOV R. Revisiting semi-supervised learning with graph embeddings [C]// Proceedings of the 33rd International Conference on Machine Learning. New York： JMLR， 2016： 40-48.

[23]SHI C， LI Y， ZHANG J， et al. A survey of heterogeneous information network analysis [J]. IEEE Transactions on Knowledge and Data Engineering， 2017， 29（1）： 17-37.

This work is partially supported by the National Natural Science Foundation of China （61603197， 61772284）.

CHEN Kejia， born in 1980， Ph. D.， associate professor. Her research interests include data mining， complex network analysis.

YANG Zeyu， born in 1994， M. S. candidate. His research interests include graph convolutional network.

LIU Zheng， born in 1980， Ph. D.， lecturer. His research interests include graph data mining.

LU Hao， born in 1995， M. S. candidate. His research interests include graph convolutional network， network representation learning.

收稿日期：2019-04-29;修回日期：2019-08-07;錄用日期：

2019-08-12。基金项目：国家自然科学基金资助项目（61603197，61772284）。

作者简介：陈可佳（1980—），女，江苏淮安人，副教授，博士， CCF会员，主要研究方向：数据挖掘、复杂网络分析;杨泽宇（1994—），男，山西晋中人，硕士研究生，主要研究方向：图卷积网络;刘峥（1980—） ，男，江苏南京人，讲师，博士， CCF会员，主要研究方向：图数据挖掘;鲁浩（1995—） ，男，河南濮阳人，硕士研究生，主要研究方向：图卷积网络、网络表示学习。