图形卷积神经网络有多强大？一文让你熟练掌握GCN

点击上方关注，All in AI中国

作者——Tobias Skovgaard Jepsen

由于高度复杂但信息丰富的图形结构，图形上的机器学习一直以来都是一项艰巨的任务。本文是关于如何使用图形卷积网络（GCN）进行图形深度学习的系列文章中的第二篇。GCN是一种强大的神经网络，旨在利用图形结构信息并直接在图形上工作。在本文开头我将简要回顾一下上一篇文章，你也可以直接点击下方链接，进行更加仔细，详细的阅读。

1.图形卷积网络的高级介绍（https://towardsdatascience.com/how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-7d2250723780）

2.谱图卷积的半监督学习（本文）

简要回顾

在我之前关于GCN的文章中（https://towardsdatascience.com/how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-7d2250723780），我们看到了在GCN中的一个简单的数学框架。简而言之，给定一个N×F⁰特性矩阵X和一个图的矩阵表示结构，例如G的N×N邻接矩阵A，GCN中的每个隐藏层可表示为Hⁱ= f（Hⁱ-1， A）其中H⁰= X且f是传播规则。每个层Hⁱ对应于N×Fⁱ特性矩阵，其中每一行是节点的特性表示。

我们看到了这种形式的传播规则

1.f（Hⁱ，A）=σ（AHⁱWⁱ）

2.f（Hⁱ，A）=σ（D-1HⁱWⁱ）其中Â= A + I，I是单位矩阵，D -1是Â的度矩阵。

这些规则在通过应用权重Wⁱ和激活函数σ进行变换之前，将节点的特性表示计算为其邻居的特性表示的集合。通过将上面的传播规则1和2表示为f（Hⁱ，A）=transform(aggregate

（A，Hⁱ），Wⁱ），我们可以使聚合和变换步骤更加明确，其中transform（M，Wⁱ）=σ（MWⁱ）和规则1的aggregate（A，Hⁱ）=AHⁱ，规则2的aggregate（A，Hⁱ）= D-1Hⁱ。

正如我们在上一篇文章中所讨论的，规则1中的聚合将节点表示为其邻居特性表示的总和，这有两个明显的缺点：

• 节点的聚合表示不包括其自身的特性。
• 具有较大度数的节点将在其特性表示中具有较大值，而具有较小度数的节点将具有较小值，这会导致出现梯度爆炸的问题并使得使用对特性敏感的随机梯度下降等算法进行训练变得更加困难。

为了解决这两个问题，规则2首先通过向A添加单位矩阵来强制执行自循环，并使用变换后的邻接矩阵Â= A + I进行聚合。接下来，通过乘以逆度矩阵D -1来对特性表示进行标准化。将聚合转换为聚合特性表示的规模对节点次数不变的均值。

在下文中，我将规则1称为求和规则，将规则2称为均值规则。

谱图卷积

Kipf和Welling最近的一篇论文提出了使用光谱传播规则的快速近似谱图卷积[1]：

与前一篇文章中讨论的总和均值规则相比，谱学规律仅在聚合函数的选择上有所不同。虽然它有点类似于均值规则，因为它使用提升到负幂的度矩阵D对聚合进行标准化，但标准化是不对称的。让我们试一试，看看它的作用。

作为加权和的聚合

到目前为止，我们可以理解我所介绍的作为加权和的聚合函数，其中每个聚合规则仅在它们的权重选择上有所不同。我们先来看看如何用加权和来表示相对简单的和与均值规则，然后再讨论谱学规律。

求和规则

为了了解如何使用求和规则计算第i个节点的聚合特性表示，我们看到如何计算聚合中的第i行。

求和规则作为加权和

如等式1a所示，我们可以将第i个节点的聚合特性表示作为向量矩阵乘积来计算。我们可以将这个向量矩阵乘积表示为一个简单的加权和，如公式1b所示，我们对X中的N行中的每一行求和。

公式1b中第j个节点在聚合中的贡献由A的第i行的第j列的值确定。由于A是邻接矩阵，如果第j个节点是第i个节点的邻居，则该值为1，否则为0。等式1b对应于对第i个节点的相邻的特性表示求和。这证实了上一篇文章的看法。

总之，每个邻居的贡献仅取决于邻接矩阵A定义的邻域。

均值规则

要查看均值规则如何用聚合节点表示，我们再次查看如何计算聚合中的第i行。为简单起见，我们只考虑"原始"邻接矩阵的均值规则，而不考虑A和单位矩阵I之间的加法，这相当于向图形中添加自循环。

均值规则作为加权和

在等式2a中，我们现在首先通过将邻接矩阵A乘以逆矩阵D来变换邻接矩阵A。在等式2b中使该计算更明确。逆矩阵是一个区域矩阵，其中沿对角线的值是逆节点度s.t.的位置，（i，i）处的值是第i个节点的反度。因此，我们可以移除其中一个求和符号，得到等式2c。在等式2d和2e中可以进一步减少等式2c。

如等式2e所示，我们现在再次对邻接矩阵A中的N行中的每一行求和。如在求和规则的讨论期间所提到的，这相当于对每个第i个节点的邻居进行求和。然而，等式2e中的加权和的权重与第i个节点的次数之和1。因此，等式2e对应于第i个节点的相邻特性表示均值。

求和规则仅取决于邻接矩阵A定义的邻域，而均值规则也仅取决于节点度。

谱学规律

我们现在有一个有用的框架来分析谱学规律。让我们看看它！

作为加权和的谱学规律

与均值规则一样，我们使用度矩阵D来变换邻接矩阵A。但是，如等式3a所示，我们将度矩阵提高到-0.5的幂并将其乘以A的每一边。此操作可以是分解如公式3b所示。再次回想一下，次数矩阵（及其幂）是对角线的。因此，我们可以进一步简化方程3b，直到达到方程3e中的表达式。

公式3e很有趣。在计算第i个节点的聚合特性表示时，我们不仅要考虑第i个节点的度，还要考虑第j个节点的度。

与均值规则类似，谱学规律对聚合s.t进行标准化。聚合特性表示与输入特性大致保持相同的比例。然而，如果谱学规律具有低度，则谱学规律将加权和中的邻域加权，如果它们具有高度则加权较低。当低次数邻居提供比高次数邻居更有用的信息时，这可能是有用的。

GCN的半监督分类

除谱学规律外，Kipf和Welling还演示了GCN如何用于半监督分类[1]。到目前为止，我们假设整个图表是可用的，即我们处于转换的环境中。换句话说，我们知道所有节点，但不知道所有节点标签。

在我们看到的所有规则中，我们在节点邻域上进行聚合，因此共享邻居的节点往往具有相似的特性表示。如果图形表现出同质性，即连接的节点倾向于相似（例如具有相同的标签），则该特性非常有用。同质性发生在许多真实网络中，尤其是社交网络表现出非常强烈的同质性。

正如我们在上一篇文章中看到的那样，即使是随机初始化的GCN也可以通过使用图形结构，在同构图中实现节点的特性表示之间的良好分离。通过在标记节点上训练GCN，我们可以更进一步，有效地将节点标签信息传播到未标记的节点。这可以通过以下方式完成：

1.通过GCN执行正向传播。

2.将sigmoid函数逐行应用于GCN中的最后一层。

3.计算已知节点标签上的交叉熵损失。

4.反向传播损失并更新每层中的权重矩阵W。

Zachary空手道俱乐部的预测

让我们看看谱学规律如何使用半监督学习将节点标签信息传播到未标记的节点。与前一篇文章一样，我们将以Zachary的空手道俱乐部为例。

Zachary的空手道俱乐部

简而言之，Zachary的空手道俱乐部是一个小型的社交网络，在这里，管理员和空手道俱乐部的教练之间会发生冲突。任务是预测空手道俱乐部的每个成员会选择的冲突的哪一方。网络的图形表示如下图所示。每个节点代表空手道俱乐部的成员，并且成员之间的链接表示他们在俱乐部外进行交互。管理员和教练分别标有A和I。

Zachary的空手道俱乐部

MXNet中的谱图卷积

我在MXNet中实现了谱学规律，这是一个易于使用且高效的深度学习框架。实施如下：

init将邻接矩阵Aalong作为输入，其中每个节点的特性表示的输入和输出维数分别来自图卷积层。in_units和out_units分别为输入和输出维数。通过与单位矩阵I相加，将自循环添加到邻接矩阵A，计算度矩阵D，并将邻接矩阵A变换为由谱学规律指定的A_hat。这种变换不是严格必要的，但是计算效率更高，因为在层的每次前向传递期间都会执行变换。

最后，在init的with子句中，我们存储了两个模型参数A_hat存储为常量，权重矩阵W存储为可训练参数。

在正向传递中，我们使用以下输入执行此方法：X，前一层的输出，以及我们在构造函数init中定义的参数A_hat和W。

构建图形卷积网络

现在我们已经实现了谱学规律，我们可以将这些层叠加在一起。我们使用类似于前一篇文章中的两层架构，其中第一个隐藏层有4个单元，第二个隐藏层有2个单元。这种架构可以轻松地显示最终的二维嵌入。它与前一篇文章中的架构有三点不同：

• 我们使用谱学规律而不是均值规则。
• 我们使用不同的激活函数：tanh激活函数用于第一层，否则死亡神经元的概率会非常高，第二层使用identity函数，因为我们使用最后一层来对节点进行分类。
• 最后，我们在GCN顶部添加逻辑回归层以进行节点分类。

上述体系结构的Python实现如下。

我已将包含图形卷积层的网络的特性学习部分分离为特性组件，将分类部分分离为分类器组件。单独的特性组件使以后更容易可视化这些层的激活。用作分类器的逻辑回归是一个分类层，它通过对最后一个图形卷积层提供的每个节点的特性求和并对该和应用sigmoid函数来执行逻辑回归。

为了完整起见，构造特性组件的代码是

而逻辑回归的代码是

训练GCN

训练GCN模型的代码如下所示。简而言之，我初始化了一个二进制交叉熵损失函数cross_entropy和SGD优化器、训练器来学习网络参数。然后针对指定数量的纪元训练模型，其中针对每个训练示例计算损失，并且使用loss.backward（）反向传播错误。然后调用trainer.step来更新模型参数。在每个纪元之后，由GCN层构建的特性表示存储在feature_representations列表中。

至关重要的是，只标记了教练和管理员的标签，网络中的其余节点是已知的，但它们未标记！GCN可以在图形卷积期间找到标记和未标记节点的表示，并且可以在训练期间利用这两种信息源来执行半监督学习。

可视化特性

如上所述，存储每个时期的特性表示，这允许我们在训练期间看到特性表示如何改变。在下面我考虑两个输入特性表示。

表示1

在第一种表示中，我们简单地使用稀疏的34×34单位矩阵I作为特性矩阵X。该表示具有可以在任何图中使用的优点，但是会导致网络中每个节点的输入参数需要大量的记忆和计算能力，以便在大型网络上进行训练，并可能导致过度拟合。值得庆幸的是，空手道俱乐部网络非常小。使用该表示对网络进行5000个历元的训练。

通过对网络中的所有节点进行分类，我们可以获得上面显示的网络中的错误分布。在这里，黑色表示错误分类。尽管近一半（41％）的节点被错误分类，但与管理员或教练（但不是两者都有）紧密相连的节点往往被正确分类。

使用表示法1训练期间特性表示的变化

在左侧，我已经说明了在训练期间特性表示如何变化。节点最初是紧密地聚集在一起的，但随着训练的进行，教练和管理员被分开，用它们带动一些节点。

虽然管理员和教练的表示方式完全不同，但他们拖动的节点不一定属于他们的社区。这是因为图形卷积在特性空间中嵌入了共享邻居的节点，但是共享邻居的两个节点可能无法同等地连接到管理员和教练。特别地，使用单位矩阵作为特性矩阵会导致每个节点的高度局部表示。即，属于图的相同区域的节点可能紧密地嵌入在一起。这使得网络难以以归纳的方式在远程区域之间共享公共知识。

表示2

我们将通过添加两个不特定于网络的任何节点或区域的特性来改进表示1。为此，我们计算从网络中的每个节点到管理员和教练的最短路径距离，并将这两个特性连接到先前的表示。

也许可能会认为这种行为有点欺骗性，因为我们会在图表中注入有关每个节点位置的全局信息，应该（理想地）由特性组件中的图卷积层捕获的信息。但是，图形卷积层始终具有局部视角，并且捕获此类信息的能力有限。尽管如此，它仍然是理解GCN的有用工具。

我们共同对网络中的所有节点进行分类，并绘制出上图的网络中的错误分布。这次，只有四个节点被错误分类，相对于表示1有显著改进！仔细检查特性矩阵后，这些节点要么与教练和管理员等距（在最短路径意义上），要么离管理员更近，但属于教练社区。使用表示1训练GCN 250个时期。

使用表示2训练期间特性表示的变化

如图所示，节点最初再次非常紧密地聚集在一起，但在训练甚至开始之前，它们在某种程度上分成了社区！随着训练的进行，社区之间的距离也会增加。

下一步是什么？

在这篇文章中，我已经深入解释了GCN中的聚合如何执行，展示了如何将其表示为加权和。并使用均值、求和、谱学规律作为示例。我真诚地希望你会发现这个框架对于在你自己的图形卷积网络中聚合期间可能需要哪些权重非常有用。

我还展示了如何在MXNet中实施和训练GCN，使用Zachary的空手道俱乐部作为一个简单的示例网络，使用谱图卷积对图形进行半监督分类。我们看到如何使用两个标记的节点，GCN仍然可以在表示空间中实现两个网络社区之间的高度分离。

虽然有关图形卷积网络的更多信息，我希望将来有时间与你分享，但这是（目前）系列中的最后一篇文章。如果你有兴趣进一步阅读，我想推荐一些我发现非常有趣的论文：

1. Inductive Representation Learning on Large Graphs（https://arxiv.org/abs/1706.02216）

在本文中，Hamilton等人提出了几种新的聚合函数，例如，使用最大/平均聚合或多层感知器。此外，他们还提出了一种简单的方法来进行GCN的小批量训练，大大提高了训练速度。

2. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samping（https://arxiv.org/pdf/1801.10247.pdf）

Hamilton等人提出的小批量方法的缺点在于，批量中的节点数量由于它们的递归而在执行的聚合的数量中呈指数增长。Chen等人提出了他们的FastGCN方法，通过独立地执行图卷积层的批量训练来解决这个缺点。

3.N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification（https://arxiv.org/pdf/1802.08888.pdf）

在FastGCN解决训练递归图卷积网络问题的地方，N-GCN挑战了GCN需要递归的前提！ Abu-El-Haija等人提出了一种具有多个（N）GCN的平面架构，其输出被连接在一起。每个GCN捕获不同距离的邻域，从而避免递归聚合。

参考

[1] Thomas Kipf和Max Welling撰写的带有图形卷积网络的半监督分类论文。（https://arxiv.org/abs/1609.02907）