图卷积网络(Graph Convolutional Networks, GCN)详细介绍
图卷积网络(Graph Convolutional Networks, GCN)详细介绍
于 2021-02-17 10:50:40 发布
机器学习笔记
版权
4 篇文章8 订阅
订阅专栏
本文转自博客。
为什么要使用图(Graph)？
在本质上诸多问题均可表现为图的形式，在实际场景中，在真实世界范围内存在大量数据以图的形式呈现；例如分子网络、社交网络领域以及论文引用关系网等
基于图的任务
针对图数据，通常有以下几种比较常见的任务类型：
- 结点分类(node classification task)：给定一个节点（node），预测其所属类别（class）。
- 链路预测(link prediction task)：评估两个节点之间是否存在链接（link）。
- 社区发现任务(community discovery task)：识别图中具有紧密联系的节点群（node cluster）。
- 网络相似性评估任务(network similarity assessment task)：计算两个网络或子网络之间的相似性（similarity score）。
机器学习工作流
在图中不仅包含节点属性（节点数据），还包括节点之间的连接模式（节点间的连接关系）。对于前者来说相对容易获取每个节点的数据信息；但对于后者来说，则需要付出更多努力。例如，在某些情况下两个节点可能比其他节点更为相似；那么在这种情况下是否应该采取不同的处理方法？对于度数特别高或特别低的节点又该如何处理？实际上，在这些任务中构建特征以表示结构信息是一项极具技巧性的工作。
采用结点的特征与结构的信息作为输入数据，并通过机制使得机器能够自主选择如何利用这些信息来提高效率和简化过程；这一做法正是图表示学习方法被引入的重要原因所在。
图卷积网络(GCN)
论文地址：Semi-supervised Classification with Graph Convolutional Networks
GCN 是一种能够直接作用于图 并且利用其结构信息的卷积神经网络 。
这篇文章解决的是在一个图中，只有少部分结点的标签是已知情况下(Semi-supervised learning)的结点分类问题。
主要思想
正如其名称中的卷积一词暗示的那样, 这一概念最初源于图像处理领域, 并随后被扩展至更为一般的图结构. 然而，在传统的图像处理中，默认的数据结构往往较为固定, 这与图数据所具有的动态连接性形成了鲜明对比.
基于图卷积网络（GCN）的核心理念，在每个节点上都需要整合该节点自身的属性信息及其所有相连邻居的信息。当采用平均池化操作时，在完成这一系列操作后即可得到一种能够直接输入至神经网络进行处理的有效表征。
如图所示，在上图中我们选取了一个简单的引用网络案例进行分析。在这个网络中每个节点代表一篇论文而边则表示文章之间的引用关系首先我们需要对原始文本进行预处理具体而言就是利用NLP技术将论文内容转换为向量表示
在这一部分分析绿色节点时我们首先计算了该节点及其所有邻居节点的特征向量并对其取平均值这一操作能够有效提取出与该文章相关的关键词信息随后将此平均值向量输入到神经网络模型中从而获得最终的表征结果
值得注意的是上述分析采用了简单的平均池化操作作为特征提取方法但在实际场景中通常会采用更加复杂的聚合机制例如基于图卷积神经网络（GCN）的设计能够通过多层非线性变换捕获更为丰富的文本语义信息如图所示的是一个典型的两层全连接GCN架构示意图其中各层输出作为下一层输入形成了完整的前馈传播路径
直观理解与数学原理
让我们深入了解GCN所依据的数学基础。
接下来我们将明确一些必要的符号。
考虑一个无向图G=(V,E)，其中V包含该网络中的所有N个节点；v_i∈V表示第i个节点；E代表节点之间的连接关系（v_i,v_j）∈E；邻接矩阵A∈ℝ^{N×N}中的元素既可以表示为二进制指示符也可以取实数值权重；度矩阵D_{ii}=∑j A{ij}；特征向量矩阵X∈ℝ^{N×C}具有维度N乘以C；我们来考察一个示例图：
What manner can we obtain the information about a node's neighbors' feature vectors? One feasible approach is to multiply A and X.
观察到邻接矩阵的第一行后发现可以看出节点A连接到了节点E；与此同时在结果矩阵中可以看到第1行实际上对应于节点E所具有的特征向量；类似地在第2行则体现了节点D与节点E之间的关系总和；通过这种方式处理后会生成每个节点所有邻居对应的特征向量之和；然而这种方法存在明显的缺陷：
- 我们未能包含所分析节点自身的信息，在结果矩阵的第一行中应当体现节点A的相关信息。
- 我们建议采用平均值函数或更优的加权平均值函数来替代简单的线性叠加方法用于处理邻居特征向量。
- 那么为何不用线性叠加呢？原因在于较大的度值节点会产生显著的表示向量而较低度节点则会生成较小的聚合向量这可能导致梯度爆炸或梯度消失现象（例如在使用sigmoid激活函数时会遇到此问题）。
- 此外神经网络对于输入数据尺度极为敏感因此我们需通过归一化处理消除潜在问题。
关于第一个问题, 可以通过在基础矩阵AA的基础上加入单位矩阵来获得新的邻接矩阵\tilde{A}. 其数学表达式为\tilde{A} = A + I_N. 当λ取值为1时, 表明节点自身特性和其邻居的重要性程度相当. 此时邻接矩阵可表示为AA与单位矩阵I_N之和. 需要注意的是, λ本身是一个可由训练过程确定的参数, 但为了简化运算, 本文将其固定设为1
针对第二步的问题，请问是否可以通过一种更加系统的方式来实现这一过程？
例如，在结点A的情况下（度是2），其对应的和向量则需乘以一个因子为\frac{1}{2}；而在结点E的情况下（度是5），对应的和向量则需乘以因子\frac{1}{5}。基于此，在计算时会将矩阵\tilde{D}^{-1}与该矩阵进行相乘运算；这样做的结果就是计算出每个节点及其邻居特征向量的平均值。
通过均值计算已经展现出了良好的效果，在这种情况下我们是否应该尝试另一种方法呢？从直觉上看，在处理高度与低度节点时应用不同的权重可能会带来更好的结果。然而，在实际操作中我们发现一个问题：当我们直接采用\tilde{D}^{-1}(\tilde{A}X)来进行计算时会出现的问题是——仅对方阵中的每一行进行了归一化处理而未考虑列向量的情况。
该方法通过引入矩阵\tilde{D}^{-1}\tilde{A}\tilde{D}^{-1}作用于向量X来进行图归一化处理。该标准化策略的核心理念即是一种加权平均机制，在实际应用中能够赋予那些具有较低度数节点更大的权重值的同时，在某种程度上削弱那些拥有较高度数节点的影响强度。这种设计思路在于考虑到低度节点会对邻居节点产生较大的影响效果而高阶节点由于连接广泛其单个影响力会被分散到更多的邻居节点上从而起到减弱的作用。
根据图所示，在获取结点B的聚合特征时，则会赋予较高的权重给B（自身及其度值为3），相对而言则会对E（度值为5）分配较低的权重
例如，在构建一个十分类的任务模型时，参数F FF会被设定为10。经过第二层神经网络处理后输出十维向量，并通过softmax函数进行预测操作；此时选择采用交叉熵损失函数作为训练目标即可完成模型训练工作。
GCN网络层数
网络层数的含义
网络的深度决定了节点特征能够传播的最大范围。例如，在使用一层GCN时, 每个节点仅能获取其直接邻居的信息.对于整个网络中的所有节点而言, 信息传递过程是相互独立且同步进行的.当我们在单层GCN基础上再增加一层时, 就能依次收集邻居的信息, 并将上一层次邻居所获取的信息纳入当前层次.这样一来, GCN的网络深度也就等同于每个节点所能到达的最大hops数目.因此我们选择的网络深度应根据所需传播的距离来确定.需要注意的是, 通常情况下我们并不需要节点间信息传递过于广泛.经过6~7次hops之后, 节点间的信息基本上就能覆盖整个网络, 这也使得进一步扩展变得意义不大.
我们所使用的GCN应该有多少层？
在文章中进行实验分析时
小结笔记
- 该方法适用于处理图数据中的半监督学习任务。
- 这种技术旨在分析图中节点属性与拓扑结构之间的关系。
- 核心概念在于通过加权融合每个节点及其邻居的信息来生成输入层向量。
- 增加深度能够扩展信息传播范围；为了提升性能，在较深层数下建议采用残差连接机制。
- 观察到矩阵形式时；相当于一种标准化操作。
- 有一个GCN的 demo库；提供了包括GCN在内的多种GNN算法实现。
**注意：**本文所提出的框架仅限于处理有权或无权的无向图。通过添加额外结点将有向图转换为无相图。