图神经网络知识总结

date

Feb 27, 2022

slug

gnn-study

status

Published

图神经网络(Graph Neural Networks, GNN)基础知识

什么是图(Graph)

图定义为G=(V,E)，其中V为点的集合，E为连接节点的边的集合。如果边连接的节点直接有依赖关系则为有向边，若无依赖关系则为无向边。

图常用邻接矩阵表示。若一个图有n个点，则邻接矩阵为n*n。通常节点会有f个特征，那么某一结点的特征矩阵为n*f。

为什么引入图神经网络

图神经网络是用于图描述的数据的一类深度学习方法，它可以直接用于图。

首先我们要说到卷积神经网络(Convolutional Neural Networks, CNN)。CNN常用于可视化任务，如图像分类、图像识别或对象检测。CNN算法隐藏层使用了卷积层和池化层，通过一组内核的形式识别空间局部化特征。而图的大小以及复杂的拓扑结构使得CNN原有的这种方法难以在图上实现，并且我们希望当改变图像点的输入顺序不会影响到结果的获得，正是这些局限性造成了GNN的发展。

常见图神经网络

GNN

在图理论里面，我们使用节点嵌入的概念，这意味着节点被映射到一个d维空间(维度低于实际空间)，以便于节点之间相似的点之间接近。

如u和v两个节点，特征向量为和，我们定义编码器函数和，使之转化为和，再求其相似函数。其中，相似函数可以是欧氏距离。流程如下图。

那么问题的重点落在的编码器函数的构造上，好的编码器函数需要能表示位置信息、汇聚信息且能堆叠多层计算。位置信息我们可以用计算图来表示，以此来同时携带结构信息和特征信息。当图信息保存至计算图后，我们使用神经网络进行汇聚。汇聚操作需要做到顺序不变，常用汇聚函数有求和、平均值最大值等，因为他们属于置换不变函数。然后，就可以进行计算操作，例如GNN中的前向传播规则中，节点的特征向量，同样的有等，神经网络汇聚他们，并且传递到下一层，而之后对于节点特征的表示形式都是潜在于隐藏层之中的。

GCN

最简单的图卷积神经网络(Graph Convolutional Networks, GCN)只有三个不同的操作：1、图卷积。2、线性层。3、非线性激活。顺序执行这些操作，我们可以得到一个网络层，通过网络层的组合我们可以得到一个完整的GCN。在Python中用PyTorch构建一个简单的GCN代码如下：

GraphSAGE

GraphSAGE是用于动态图的一种表示学习，它可以不重新训练程序的前提下预测新的点的嵌入。为了做到这一目标，GraphSAGE使用归纳学习，它的聚合函数使用到了节点的特征以及相邻节点。

此前我们使用的都是平均聚合函数——简单的求和相邻节点携带的信息，然后用相邻节点数归一化。现在我们可以使用池化类型的方法，或是运用一个像LSTM的深度神经网络。

图神经网络的应用

节点分类

通过查看相邻样本的标签来确定样本(节点)的标签。通常为半监督的方式训练，只有一部分图被标记。

图分类

将整个图分类为不同的类别，类似于图像分类，但是目标变成了图域。图分类应用范围很广，如生物信息学中确定蛋白质是否是酶，在NLP或社交网络分析中对文档进行分类。

图形可视化

数学和计算机科学的一个领域，处于几何图论和信息可视化的交叉点。关注图像的可视化表示，揭示数据中可能存在的结构和异常，帮助用户理解图形。

链接预测

理解图中实体间的关系，并且预测两个实体之间是否存在联系。在社交网络中，推断社交互动或向用户推荐可能的朋友是必不可缺少的。它还被用于推荐系统问题和预测犯罪关联。

图聚类

以图的形式对数据进行聚类，分为两种不同形式的聚类：顶点聚类和图作为对象的聚类。顶点聚类根据边权重或边距离将图的节点聚类成为密集链接的区域组。图作为对象的聚类根据图的相似性进行对象的聚类。