论文阅读笔记：《一种改进的图卷积网络半监督节点分类》

《一种改进的图卷积网络半监督节点分类》

摘要：

目前大多数图卷积( GCN) 关注于提取局部特征信息，忽略了全局特征，使得标签不能有效地传播到整个图上。

对此，设计一种可以用于半监督节点分类任务的深度池化对偶图神经网络( DPDNN) 。该网络引入池化机制，将结构相似的节点聚合为超节点，扩大节点的接收域。通过随机游走得到图全局信息的潜在表示，使用随机游走模型与GCN 进行协同训练，从而补充GCN 模型在获取整个图拓扑结构信息上的能力。

实验结果表明，该网络模型与现有方法相比提高了分类精度，在少量数据标记时效果更为明显。

引言

非欧几里得数据

深度学习在欧几里得数据上取得了巨大的成功，但是越来越多的应用需要对非欧几里得数据如图或流形进行分析。例如，在电子商务中，一个基于图的学习系统能够利用用户与商品之间的交互做出推荐; 在化学中，需要识别被建模为图结构的分子的生物活性以发现新药物; 在引文网络中，论文需要通过被引用的关系相互连接，然后通过挖掘关系被分成不同的组。挖掘这些图结构数据隐含的信息，成为当今学者研究的热门话题。

本文设计了深度池化对偶图神经网络，主要工作概括如下:

• (1) 在图卷积神经网络引入图池化机制加深了模型层数，将结构相似的点聚合为超节点，扩大节点的接收域;
• (2) 使用随机游走模型获得节点全局信息，与GCN 进行协同训练，解决了卷积核局部性问题，扩大了局部特征信息，利用局部信息和全局信息进行特征提取;
• (3) 在公开数据集Cora、Citeseer、Pubmed 上进行了实验，与多种类型的算法进行对比，在少量数据标记时能更好地将数据标签传播到图上，从而提取更深层次的特征，提高数据集的分类精确度。

1 深度池化对偶图神经网络

本文模型主要分为三步:

• ( 1) 利用图的邻接矩阵和特征输入构建深度池化神经网络;
• ( 2) 构建基于随机游走的卷积神经网络;
• ( 3) 将二者结合进行协同训练。

1.1 图卷积神经网络

图卷积神经网络( GCN) 在网络节点分类任务中有很好的泛化效果.

这篇文章使用了最基础的GCN。

1.2 图池化和细化

图的池化就是将结构相似节点聚合在一起，相当于保留局部几何多尺度结构。图的细化目的是为了恢复节点的拓扑结构，方便进行节点的分类。每个池化层包括图卷积和图池化两个步骤。首先用GCN进行邻域信息的聚集来提取结构特征和属性特征，再通过结构等效分组和结构相似分组。

1. 结构等效分组。

   如果两个节点共享同一组邻居，则它们在结构上是等效的。然后将这两个节点分配为超节点。如图1 所示，节点B 和D 在结构上是等效的，因此将这两个节点分配为超节点。对这些在结构上等效的节点进行标记，保留其他未分组没有标记的节点，以避免在节点上重复进行分组操作。

   

2. 结构相似分组。

   在未标记的节点对( vj，vk) 之间进行结构相似性计算作为归一化连接权重s ( vj，vk) ，计算公式如下:

   

   式中: Ajk是节点对( vj，vk) 的边权重; D( ·) 是节点的度。在进行结构相似分组时，迭代取出未标记的节点vj，并计算与其所有未标记的邻居节点vk的归一化连接权重，之后选择结构相似度最大的邻居节点形成一个新的超级节点并标记这两个节点。

   如果一个节点未标记，而其他所有邻居节点都被标记，那么它也将被标记，并独自构成一个超节点。例如，在图1 中，节点对( C，E) 具有最大的结构相似性，因此将它们组合在一
   起以形成一个超节点。由于仅节点A 没有标记，其他邻居节点都被标记，所以本身构成了一个超节点。

为了恢复原有节点的拓扑结构，方便进行节点分类，在矩阵Mi中保留了节点及其对应的超节点之间的分组关系。

图池化过程具体步骤如下:
输入: 图Gi和节点特征表示Hi。
输出: 池化图Gi + 1和池化节点特征表示Hi + 1。

• ( 1) 根据式( 1) 计算GCN 的输出Gi;
• ( 2) 计算结构等效分组;
• ( 3) 根据式( 2) 进行结构相似分组;
• ( 4) 更新节点权重和边权重;
• ( 5) 根据式( 3) 保留超节点分组关系;
• ( 6) 根据式( 4 ) 计算特征矩阵Hi + 1和池化图Gi + 1。

3. 图的细化层。为了恢复图的原始拓扑结构进一步促进节点分类，恢复与池化层相同数量的细化层，然后经过短连接，与图池化层一样也分为两步: 节点的嵌入，恢复节点表示。节点的分层表示主要是通过GCN，由于在池化过程中将分组关系保存在分组矩阵
   中，因此利用Ml － i恢复第i 层的细化节点表示矩阵.

如图所示，深度池化神经网络主要由池化层和细化层组成。对于每个池化层，首先进行图卷积运算以学习节点表示; 然后，执行池化操作以结构相似的节点聚合为超节点。池化操作后，每个超节点有了更大的接收域，这有利于捕获节点信息。在池化层之后，运用对称图细化层以恢复用于节点分类任务的原始图结构，将池化层和细化层进行短连接，最后经过Softmax分类器进行分类。这样分层模型可以从局部到全局的角度全面捕获节点的信息，从而更好地表示节点。

1.3 基于随机游走的卷积神经网络

除了由邻接矩阵A 得到的图结构信息之外，本文进一步计算正点态互信息矩阵，得到图全局相关信息的潜在表示，该信息矩阵被表示为P∈Ｒn × n，与邻接矩阵有相似的结构。首先利用随机游走来计算频率矩阵F，在F 基础上计算P。最后，本文设计了基于随机游走的卷积神经网络ConvP。

PPMI 主要用来编码语义特征信息，已经在自然语言处理获得广泛的研究，并在相似性任务上得到很好的效果，可以衡量两个变量的相关性，在本文中主要用随机游走的方式计算节点多跳之间的关联度，能获取全局特征信息。

本文采用随机游走卷积神经网络优点如下: ( 1) 能够将标记的数据有效的传播到整个图上，解决卷积核局部性问题。( 2) P 矩阵在不同数据点之间形成了更多的潜在关系，是邻接矩阵另一种形式的表示。

1 4 深度池化和随机游走协同训练

深度池化神经网络通过池化操作加深了图卷积神经网络模型，将结构相似的节点聚集在一起形成超节点，丰富了节点的信息，而卷积核局部性问题则通过随机游走网络模型得到解决。

为了实现二者的协同训练以更好地互补，提出将ConvA 和ConvP 进行集成学习。本文使用有
标签的数据来训练ConvA，得到监督损失L0( ConvA) ，通过训练P 来得到无监督正则化损失Lreg( ConvA，ConvP) 。

实验