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

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

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

　　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)。为将本文提出的算法应用范围扩展到仅有连接关系而没有具体特征值的数据集上，采用了结构优先原则。

　　推荐阅读：计算机专业论文投稿

期刊VIP网，您身边的高端学术顾问

文章名称： 基于邻域选择策略的图卷积网络模型

文章地址： http://www.qikanvip.com/jisuanjiwangluo/50187.html