image.png

文章是一片使用谱图卷积的一节近似方法简化一种有效的卷积神经网络的直接应用在图上的变体, 实现对于图结构数据的半监督学习,

  • We motivate the choice of our convolutional architecture via a localized first-order approximation of spectral graph convolutions.
  • Our model scales linearly in the number of graph edges(模型的规模随着图的边的数量线性增长) and learns hidden layer representations that encode both local graph structure and features of nodes.

主要贡献:

  1. 首先，我们为直接作用于图的神经网络模型引入了一个简单且性能良好的层级传播规则，并展示了如何从谱图卷积的一阶近似中推导该规则(Hammond et al.，2011)。
  2. 其次，我们展示了这种基于图形的神经网络模型如何用于快速和可伸缩的图中节点的半监督分类。

论文记录

谱图卷积

image.png

这里提到, 对应的Semi-supervised Classification with Graph Convolutional Networks - 图3是一个对角矩阵, 对角线的值是一个傅里叶域的参数. 这里具体可见参考链接2.

在这里，可以将Semi-supervised Classification with Graph Convolutional Networks - 图4看作是Semi-supervised Classification with Graph Convolutional Networks - 图5特征值的函数，也就是Semi-supervised Classification with Graph Convolutional Networks - 图6.

等式3计算消耗大, 有着n2的复杂度, 此外，在第一个位置计算L的特征分解对于大图来说可能是非常昂贵的.

为了克服这个问题, 这里使用了[David K. Hammond, Pierre Vandergheynst, and R´ emi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129–150, 2011.]的方法, 使用一个切比雪夫多项式K阶截断近似.

image.png

其中的 lambda_max 表示L的最大特征值, 也就是谱半径. 注意这里有了一个新的维度参数K, 一般K<N.

这时候就可以近似替换了.

image.png

Semi-supervised Classification with Graph Convolutional Networks - 图9 而 Semi-supervised Classification with Graph Convolutional Networks - 图10 是 Semi-supervised Classification with Graph Convolutional Networks - 图11 的 Semi-supervised Classification with Graph Convolutional Networks - 图12 阶多项式，且有 Semi-supervised Classification with Graph Convolutional Networks - 图13 . 这样就得到了公式如下. Semi-supervised Classification with Graph Convolutional Networks - 图14

这个时候, 可以看这个表达式, 这个卷积的计算只依赖于中心节点的K阶邻居.(K步以内可达的节点)

层级线性模型

因此，基于图卷积的神经网络模型可以通过将多个卷积层叠加如式5所示，每层叠加一个点级非线性来构建。现在，假设我们将分层卷积运算限制为K = 1(参见Eq. 5)，即一个线性的关于L的函数，因此它是拉普拉斯谱图上的一个线性函数。这样，我们仍然可以通过叠加多个这样的层来恢复一类丰富的卷积滤波函数，但是我们并不局限于Chebyshev多项式给出的显式参数化。我们直观地认为，对于节点度分布非常宽的图，该模型可以缓解局部邻域结构过拟合的问题. 另外，对于固定的计算预算，这种分层线性公式允许我们构建更深入的模型，这是一种提高许多领域建模能力的实践.

在这个GCN的线性表示中, 近似参数 lambda_max为2, 以消掉分数项, 这样展开迭代多项式, 可以得到简化后的卷积公式:

image.png

这里实际上希望, 网络在训练的时候, 可以自己学习适应这种参数简化后的表示所带来的改变. 所以一定程度上来讲, 这样的设定是可以的.

为了进一步降低参数数量, 减轻过拟合的问题, 以及减少操作数量, 这里进一步简化, 让上式中的两个 theta 值相同. 表示为:

image.png

需要注意的是， Semi-supervised Classification with Graph Convolutional Networks - 图17 的特征值范围为[0,2]，这意味着，当不停地重复该操作时（网络非常深时），可能会引起梯度爆炸或梯度消失。

image.png 这里的操作还是有些不太理解?

当图中每个节点的表示不是单独的标量而是一个大小为 Semi-supervised Classification with Graph Convolutional Networks - 图19 的向量时，可以使用其变体进行处理：

Semi-supervised Classification with Graph Convolutional Networks - 图20

其中， Semi-supervised Classification with Graph Convolutional Networks - 图21 表示参数矩阵， Semi-supervised Classification with Graph Convolutional Networks - 图22 为相应的卷积结果。此时，每个节点的节点表示被更新成了一个新的 Semi-supervised Classification with Graph Convolutional Networks - 图23 维向量，该 Semi-supervised Classification with Graph Convolutional Networks - 图24 维向量包含了相应的一阶邻居上的信息。

层间传播规则

经过上面的推导, 这里的得到了层间传播规则.

image.png

这里的W实际上就是和那个卷积核h有关系的参数.

这就是这里提出的GCN的最终表示.

模型

对于一个大图（例如“文献引用网络”），我们有时需要对其上的节点进行分类。然而，在该图上，仅有少量的节点是有标注的。此时，我们需要依靠这些已标注的节点来对那些没有标注过的节点进行分类，此即半监督节点分类问题。在这类问题中，由于大部分节点都没有已标注的标签，因此往往需要使用某种形式的图正则项对标签信息进行平滑（例如在损失函数中引入图拉普拉斯正则（graph Laplacian regularization））：

Semi-supervised Classification with Graph Convolutional Networks - 图26

其中， Semi-supervised Classification with Graph Convolutional Networks - 图27 表示有监督的损失， Semi-supervised Classification with Graph Convolutional Networks - 图28 可以是一个类似于神经网络的可微函数。 Semi-supervised Classification with Graph Convolutional Networks - 图29 表示一个权值因子， Semi-supervised Classification with Graph Convolutional Networks - 图30 则是相应的节点向量表示。 Semi-supervised Classification with Graph Convolutional Networks - 图31 表示未归一化的图拉普拉斯矩阵。这种处理方式的一个基本假设是：相连的节点可能有相同的标签。然而，这种假设却往往会限制模型的表示能力，因为图中的边不仅仅可以用于编码节点相似度，而且还包含有额外的信息。

GCN的使用可以有效地避开这一问题。GCN通过一个简单的映射函数 Semi-supervised Classification with Graph Convolutional Networks - 图32 ，可以将节点的局部信息汇聚到该节点中，然后仅使用那些有标注的节点计算 Semi-supervised Classification with Graph Convolutional Networks - 图33 即可，从而无需使用图拉普拉斯正则。

具体来说，本文使用了一个两层的GCN进行节点分类。模型结构图如下图所示：

Semi-supervised Classification with Graph Convolutional Networks - 图34

其具体流程为：
首先获取节点的特征表示 Semi-supervised Classification with Graph Convolutional Networks - 图35 并计算图的邻接矩阵 Semi-supervised Classification with Graph Convolutional Networks - 图36 。

将其输入到一个两层的GCN网络中，得到每个标签的预测结果：

Semi-supervised Classification with Graph Convolutional Networks - 图37

其中:

  • Semi-supervised Classification with Graph Convolutional Networks - 图38 为第一层的权值矩阵，用于将节点的特征表示映射为相应的隐层状态。
  • Semi-supervised Classification with Graph Convolutional Networks - 图39 为第二层的权值矩阵，用于将节点的隐层表示映射为相应的输出（ Semi-supervised Classification with Graph Convolutional Networks - 图40 对应节点标签的数量）。

最后将每个节点的表示通过一个softmax函数，即可得到每个标签的预测结果。

对于半监督分类问题，使用所有有标签节点上的期望交叉熵作为损失函数：

Semi-supervised Classification with Graph Convolutional Networks - 图41

注意这里的索引, 这里使用交叉熵来计算, 其中的Ylf表示的是对于有标签的第l个节点, 对应的输出的F维度的特征, 和真值的F维度进行交叉熵计算.

其中， Semi-supervised Classification with Graph Convolutional Networks - 图42 表示有标签的节点集。

总结

本文提出了一种图卷积神经网络，该网络可以被有效地用于处理图结构的数据。图卷积神经网络具有几个特点：

  • 局部特性：图卷积神经网络关注的是图中以某节点为中心，K阶邻居之内的信息，这一点与GNN有本质的区别；
  • 一阶特性：经过多种近似之后，GCN变成了一个一阶模型。也就是说，单层的GCN可以被用于处理图中一阶邻居上的信息；若要处理K阶邻居，可以采用多层GCN来实现；
  • 参数共享：对于每个节点，其上的滤波器参数 Semi-supervised Classification with Graph Convolutional Networks - 图43 是共享的，这也是其被称作图卷积网络的原因之一。

总的来说，图卷积神经网络是神经网络技术在图结构数据上的一个重要应用。目前，已经出现了很多GCN的变体，这也反映了如何将神经网络与图结构数据结合起来，已经成为了目前的一个热点问题。这一研究可以被广泛应用在graph embedding、node embedding等图相关的任务上，它也为处理大型图结构数据提供了一种有效的手段。

参考链接