GCN图卷积网络入门详解
在这篇文章中，我们将仔细研究一个名为GCN的著名图神经网络。首先，我们先直观的了解一下它的工作原理，然后再深入了解它背后的数学原理。
字幕组双语原文： 【GCN】图卷积网络(GCN)入门详解
英语原文： Graph Convolutional Networks (GCN)
翻译： 听风1996 、 大表哥
许多问题的本质上都是图。在我们的世界里，我们看到很多数据都是图，比如分子、社交网络、论文引用网络。
图的例子。(图片来自[1])
在图中，我们有节点特征（代表节点的数据）和图的结构（表示节点如何连接）。
对于节点来说，我们可以很容易地得到每个节点的数据。但是当涉及到图的结构时，要从中提取有用的信息就不是一件容易的事情了。例如，如果2个节点彼此距离很近，我们是否应该将它们与其他对节点区别对待呢？高低度节点又该如何处理呢？其实，对于每一项具体的工作，仅仅是特征工程，即把图结构转换为我们的特征，就会消耗大量的时间和精力。
图上的特征工程。(图片来自[1])
如果能以某种方式同时得到图的节点特征和结构信息作为输入，让机器自己去判断哪些信息是有用的，那就更好了。
这也是为什么我们需要图表示学习的原因。
我们希望图能够自己学习 "特征工程"。(图片来自[1])
论文 ：基于图神经网络的半监督分类 （2017）[3]
GCN是一种卷积神经网络，它可以直接在图上工作，并利用图的结构信息。
它解决的是对图（如引文网络）中的节点（如文档）进行分类的问题，其中仅有一小部分节点有标签（半监督学习）。
在Graphs上进行半监督学习的例子。有些节点没有标签（未知节点）。
就像"卷积"这个名字所指代的那样，这个想法来自于图像，之后引进到图（Graphs）中。然而，当图像有固定的结构时，图（Graphs）就复杂得多。
从图像到图形的卷积思想。 (图片来自[1])
GCN的基本思路：对于每个节点，我们从它的所有邻居节点处获取其特征信息，当然也包括它自身的特征。假设我们使用average()函数。我们将对所有的节点进行同样的操作。最后，我们将这些计算得到的平均值输入到神经网络中。
在下图中，我们有一个引文网络的简单实例。其中每个节点代表一篇研究论文，同时边代表的是引文。我们在这里有一个预处理步骤。在这里我们不使用原始论文作为特征，而是将论文转换成向量（通过使用NLP嵌入，例如tf-idf）。NLP嵌入，例如TF-IDF)。
让我们考虑下绿色节点。首先，我们得到它的所有邻居的特征值，包括自身节点，接着取平均值。最后通过神经网络返回一个结果向量并将此作为最终结果。
GCN的主要思想。我们以绿色节点为例。首先，我们取其所有邻居节点的平均值，包括自身节点。然后，将平均值通过神经网络。请注意，在GCN中，我们仅仅使用一个全连接层。在这个例子中，我们得到2维向量作为输出（全连接层的2个节点）。
在实际操作中，我们可以使用比average函数更复杂的聚合函数。我们还可以将更多的层叠加在一起，以获得更深的GCN。其中每一层的输出会被视为下一层的输入。
2层GCN的例子：***层的输出是第二层的输入。同样，注意GCN中的神经网络仅仅是一个全连接层（图片来自[2]）。
让我们认真从数学角度看看它到底是如何起作用的。
首先，我们需要一些注解
我们考虑图G，如下图所示。
从图G中，我们有一个邻接矩阵A和一个度矩阵D。同时我们也有特征矩阵X。
那么我们怎样才能从邻居节点处得到每一个节点的特征值呢？解决方法就在于A和X的相乘。
看看邻接矩阵的***行，我们看到节点A与节点E之间有连接，得到的矩阵***行就是与A相连接的E节点的特征向量（如下图）。同理，得到的矩阵的第二行是D和E的特征向量之和，通过这个方法，我们可以得到所有邻居节点的向量之和。
计算 "和向量矩阵 "AX的***行。
在问题（1）中，我们可以通过在A中增加一个单位矩阵I来解决，得到一个新的邻接矩阵Ã。
取lambda=1（使得节点本身的特征和邻居一样重要），我们就有Ã=A+I，注意，我们可以把lambda当做一个可训练的参数，但现在只要把lambda赋值为1就可以了，即使在论文中，lambda也只是简单的赋值为1。
通过给每个节点增加一个自循环，我们得到新的邻接矩阵
对于问题(2): 对于矩阵缩放，我们通常将矩阵乘以对角线矩阵。在当前的情况下，我们要取聚合特征的平均值，或者从数学角度上说，要根据节点度数对聚合向量矩阵ÃX进行缩放。直觉告诉我们这里用来缩放的对角矩阵是和度矩阵D̃有关的东西（为什么是D̃，而不是D？因为我们考虑的是新邻接矩阵Ã 的度矩阵D̃，而不再是A了）。
现在的问题变成了我们要如何对和向量进行缩放/归一化？换句话说：
我们如何将邻居的信息传递给特定节点？我们从我们的老朋友average开始。在这种情况下，D̃的逆矩阵（即，D̃^{-1}）就会用起作用。基本上，D̃的逆矩阵中的每个元素都是对角矩阵D中相应项的倒数。
例如，节点A的度数为2，所以我们将节点A的聚合向量乘以1/2，而节点E的度数为5，我们应该将E的聚合向量乘以1/5，以此类推。
因此，通过D̃取反和X的乘法，我们可以取所有邻居节点的特征向量（包括自身节点）的平均值。
到目前为止一切都很好。但是你可能会问加权平均()怎么样？直觉上，如果我们对高低度的节点区别对待，应该会更好。
但我们只是按行缩放，但忽略了对应的列（虚线框）。
为列增加一个新的缩放器。
新的缩放方法给我们提供了 "加权 "的平均值。我们在这里做的是给低度的节点加更多的权重，以减少高度节点的影响。这个加权平均的想法是，我们假设低度节点会对邻居节点产生更大的影响，而高度节点则会产生较低的影响，因为它们的影响力分散在太多的邻居节点上。
在节点B处聚合邻接节点特征时，我们为节点B本身分配***的权重（度数为3），为节点E分配最小的权重（度数为5）。
因为我们归一化了两次，所以将"-1 "改为"-1/2"
例如，我们有一个多分类问题，有10个类，F 被设置为10。在第2层有了10个维度的向量后，我们将这些向量通过一个softmax函数进行预测。
Loss函数的计算方法很简单，就是通过对所有有标签的例子的交叉熵误差来计算，其中Y_{l}是有标签的节点的集合。
层数是指节点特征能够传输的最远距离。例如，在1层的GCN中，每个节点只能从其邻居那里获得信息。每个节点收集信息的过程是独立进行的，对所有节点来说都是在同一时间进行的。
当在***层的基础上再叠加一层时，我们重复收集信息的过程，但这一次，邻居节点已经有了自己的邻居的信息（来自上一步）。这使得层数成为每个节点可以走的***跳步。所以，这取决于我们认为一个节点应该从网络中获取多远的信息，我们可以为#l***ers设置一个合适的数字。但同样，在图中，通常我们不希望走得太远。设置为6-7跳，我们就几乎可以得到整个图，但是这就使得聚合的意义不大。
例： 收集目标节点 i 的两层信息的过程
在论文中，作者还分别对浅层和深层的GCN进行了一些实验。在下图中，我们可以看到，使用2层或3层的模型可以得到***的结果。此外，对于深层的GCN（超过7层），反而往往得到不好的性能（虚线蓝色）。一种解决方案是借助隐藏层之间的残余连接（紫色线）。
不同层数#的性能。图片来自论文[3]
论文作者的说明
该框架目前仅限于无向图（加权或不加权）。但是，可以通过将原始有向图表示为一个无向的两端图，并增加代表原始图中边的节点，来处理有向边和边特征。
对于GCN，我们似乎可以同时利用节点特征和图的结构。然而，如果图中的边有不同的类型呢？我们是否应该对每种关系进行不同的处理？在这种情况下如何聚合邻居节点？最近有哪些先进的方法？
在图专题的下一篇文章中，我们将研究一些更复杂的方法。
如何处理边的不同关系（兄弟、朋友、......）？
[1] Excellent slides on Graph Representation Learning by Jure Leskovec (Stanford):
[2] Video Graph Convolutional Networks (GCNs) made simple:
[3] Paper Semi-supervised Classification with Graph Convolutional Networks (2017):
[4] GCN source code:
[5] Demo with StellarGraph library:
雷锋字幕组是一个由AI爱好者组成的翻译团队，汇聚五五多位志愿者的力量，分享最新的海外AI资讯，交流关于人工智能技术领域的行业转变与技术创新的见解。
团队成员有大数据专家，算法工程师，图像处理工程师，产品经理，产品运营，IT咨询人，在校师生；志愿者们来自IBM，AVL，Adobe，阿里，百度等知名企业，北大，清华，港大，中科院，南卡罗莱纳大学，早稻田大学等海内外高校研究所。
如果，你也是位热爱分享的AI爱好者。欢迎与雷锋字幕组一起，学习新知，分享成长。
图卷积网络(GCN)原理解析
Graph Convolutional Networks涉及到两个很重要的概念：graph和Convolution。传统的卷积方式在欧式数据空间中大展神威，但是在非欧式数据空间中却哑火，很重要的一个原因就是传统的卷积方式在非欧式的数据空间上无法保持“平移不变性”。为了能够将卷积推广到Graph等非欧式数据结构的拓扑图上，GCN横空出世。在深入理解GCN： 的来龙去脉之前，我觉着我们有必要提前对以下概念有点印象：
论文链接 Semi-supervised Classification with Graph Convolutional Networks
1.拉普拉斯矩阵及其变体
给定一个节点数为 的简单图 ， 是 的度矩阵， 是 的邻接矩阵，则 的拉普拉斯矩阵可以表示为 . 中的各个元素表示如下：
1.传统的傅里叶变换
当变换对象为离散变量时，求积分相当于求内积，即
这里的 就是传说中似乎有点神秘的拉普拉斯算子的特征函数（拉普拉斯算子是欧式空间中的二阶微分算子，卸了妆之后的样子是 ）。
为何这样说呢？是因为从广义的特征方程定义看 , 本身是一种变换， 是特征向量或者特征函数， 是特征值。我们对基函数 求二阶导， . 可以看出 是变换 的特征函数。
在Graph中，拉普拉斯矩阵 可以谱分解(特征分解)，其特征向量组成的矩阵是 ，根据特征方程的定义我们可以得到 。通过对比我们可以发现 相当于 , 相当于 。因此在Graph上的傅里叶变换可以写作 .
从傅里叶变换的基本思想来看，对 进行傅里叶变换的本质就是将 转换为一组正交基下的坐标表示，进行线性变换，而坐标就是傅里叶变换的结果，下图中的 就是 在***个基上的投影分量的大小。
我们通过矩阵乘法将Graph上的傅里叶变换推广到矩阵形式：
是Graph上第 个节点的特征向量，可得Graph上的傅里叶变换形式：
。
此处的 是Graph的拉普拉斯矩阵的特征向量组成的特征矩阵的转置，在拉普拉斯矩阵的优良性质中我们知道拉普拉斯矩阵的特征向量组成的矩阵为正交阵，即满足 ，所以Graph的逆傅里叶变换形式为 ，矩阵形式如下：
到此为止我们已经通过类比从传统的傅里叶变换推广到了Graph上的傅里叶变换。接下来我们就要借助傅里叶变换这个桥梁使得Convolution与Graph把酒言欢了。
在前言中我们了解了大名鼎鼎的卷积定理：函数卷积的傅里叶变换是其傅里叶变换的乘积，即对于 ,两者的卷积是其傅里叶变换的逆变换：
我们把上一节中得到的Graph上的傅里叶变换公式代入得到：
是Hamada积，表示逐点相乘。
我们一般将 看作输入的Graph的节点特征，将 视为可训练且参数共享的卷积核来提取拓扑图的空间特征。为了进一步看清楚卷积核 ，我们将上式改写为：
也许有人对于上式的变换心存疑虑，证明其实很简单，有意者请看这位答主的解答 GCN中的等式证明 - 知乎
至此，我们已经推导出来GCN的雏形。
1. ***代GCN
卷积操作的核心是由可训练且参数共享的卷积核，所以***代GCN是直接把上式中的 中的对角线元素 替换为参数 。先初始化赋值，然后通过反向传播误差来调整参数 。
所以***代GCN就变成了酱个样子：
是Graph中每个节点特征的表示向量， 是每个节点经过GCN卷积之后的输出。Graph中的每个节点都要经过卷积核卷积来提取其相应的拓扑空间，然后经过激活函数 传播到下一层。
***代GCN的缺点也是显而易见的，主要有以下几点，
2. 第二代GCN
面对***代GCN参数过多的缺点，第二代GCN进行了针对性的改进。由于Graph上的傅里叶变换是关于特征值的函数 ， 也可写作 ，用k阶多项式对卷积核进行改进:
将其代入到 可以得到：
所以第二代GCN是介个样子：
可以看出二代GCN的最终化简结果不需要进行矩阵分解，直接对拉普拉斯矩阵进行变换。参数是 ，k一般情况下远小于Graph中的节点的数量 ，所以和***代GCN相比，第二代GCN的参数量明显少于***代GCN，减低了模型的复杂度。对于参数 ，先对其进行初始化，然后根据误差反向传播来更新参数。但是仍旧需要计算 ，时间复杂度为 .
另外我们知道对于一个矩阵的k次方，我们可以得到与中心节点k-hop相连的节点，即 中的元素是否为0表示Graph中的一个结点经过k跳之后是否能够到达另外一个结点，这里的k其实表示的就是卷积核感受野的大小，通过将每个中心节点k-hop内的邻居节点聚合来更新中心节点的特征表示，而参数 就是第k-hop邻居的权重。
未完待续。
1.在谱域图卷积中，我们对图的拉普拉斯矩阵进行特征分解。通过在傅里叶空间中进行特征分解有助于我们我们理解潜在的子图结构。ChebyNet, GCN是使用谱域卷积的典型深度学习架构。
2.空域卷积作用在节点的邻域上，我们通过节点的k-hop邻居来聚合得到节点的特征表示。空域卷积相比谱域卷积更加简单和高效。GraphSAGE和GAT 是空域卷积的典型代表。
参考文献
1.
2.
3.
为什么有图卷积神经网络？
本质上说，世界上所有的数据都是拓扑结构，也就是网络结构，如果能够把这些网络数据真正的收集、融合起来，这确实是实现了AI智能的***步。所以，如何利用深度学习处理这些复杂的拓扑数据，如何开创新的处理图数据以及知识图谱的智能算法是AI的一个重要方向。
深度学习在多个领域的成功主要归功于计算资源的快速发展（如 GPU）、大量训练数据的收集，还有深度学习从欧几里得数据（如图像、文本和视频）中提取潜在表征的有效性。但是，尽管深度学习已经在欧几里得数据中取得了很大的成功，但从非欧几里得域生成的数据已经取得更广泛的应用，它们需要有效分析。如在电子商务领域，一个基于图的学习系统能够利用用户和产品之间的交互以实现高度精准的推荐。在化学领域，分子被建模为图，新药研发需要测定其生物活性。在论文引用网络中，论文之间通过引用关系互相连接，需要将它们分成不同的类别。自2012年以来，深度学习在计算机视觉以及自然语言处理两个领域取得了巨大的成功。假设有一张图，要做分类，传统方法需要手动提取一些特征，比如纹理，颜色，或者一些更高级的特征。然后再把这些特征放到像随机森林等分类器，给到一个输出标签，告诉它是哪个类别。而深度学习是输入一张图，经过神经网络，直接输出一个标签。特征提取和分类一步到位，避免了手工提取特征或者人工规则，从原始数据中自动化地去提取特征，是一种端到端（end-to-end）的学习。相较于传统的方法，深度学习能够学习到更高效的特征与模式。
图数据的复杂性对现有机器学习算法提出了重大挑战，因为图数据是不规则的。每张图大小不同、节点无序，一张图中的每个节点都有不同数目的邻近节点，使得一些在图像中容易计算的重要运算（如卷积）不能再直接应用于图。此外，现有机器学习算法的核心假设是实例彼此独立。然而，图数据中的每个实例都与周围的其它实例相关，含有一些复杂的连接信息，用于捕获数据之间的依赖关系，包括引用、朋友关系和相互作用。
最近，越来越多的研究开始将深度学习方法应用到图数据领域。受到深度学习领域进展的驱动，研究人员在设计图神经网络的架构时借鉴了卷积网络、循环网络和深度自编码器的思想。为了应对图数据的复杂性，重要运算的泛化和定义在过去几年中迅速发展。
关于图卷积和图卷积神经网络代码的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。