作者 | 徐少迪/庄若愚

编辑 | 孟繁贵

       现实生活中有很多图结构的例子，比如我们熟悉的社交网络、经济网络、生物医学网络、信息网络等。在计算机科学中，一个图就是一些节点（Vertice）的集合，某些节点之间通过一系列边(Edge)相连。

         一旦有了图结构的数据，就可以通过提取图特征来进行机器学习任务。但图的特征提取却十分复杂，因为一般机器学习任务多处理欧几里得结构（Euclidean Structure ）的数据，例如图像或者视频数据中像素点是排列成很整齐的矩阵，可以利用CNN来处理。而图却是非欧几里得结构（Non Euclidean Structure），表现在图的结构可以任意变化，一个图可以具备各种形状，尽管他们的节点位置不一样，但是连接关系没变，所以图完全一样。节点也可以以任意顺序标记，同样一个5个节点的图，节点可以标记为1、2、3、4、5，也可以标记为4、2、1、3、5，节点编号变了，而图却完全没变。

       这样的非欧几里得结构的网络数据就是图论中抽象意义上的拓扑图。广义上来讲任何数据在赋范空间内都可以建立拓扑关联，所以说拓扑连接是一种广义的数据结构。正因为很多数据都可以表达成图的形式，因此图也有非常广泛的应用和极大的研究价值。

       那如何有效的提取图特征，进而进行机器学习任务呢，这就需要用到图表示学习的方法了。图表示学习顾名思义，是指图（Graph）这一数据形式的表示学习（Representation Learning），核心是将图特征向量化，尽量保留原有数据中对后续任务有价值的信息，为后续的数据分析或机器学习任务做准备。

       与其他非结构化数据的向量化表达相似，图表示学习狭义上来说是指图嵌入（Graph Embedding）的方法，图嵌入也区分为子图嵌入（Subgraph Embedding）、节点嵌入（Node Embedding）、边嵌入（Edge Embedding）等，其中节点嵌入是现在研究较多、应用也较为广泛的领域，本文也主要针对节点嵌入的方法进行阐述。

       对图嵌入概念的理解可以从文本嵌入入手，文本嵌入是根据元素及其上下文结构构造词对形式的训练数据，然后训练浅层神经网络，神经网络中的隐藏层即为“嵌入”。相似的，节点嵌入也是指根据节点及其周边关系、周边节点信息作为相应的训练样本，通过神经网络学习训练，得到相应隐藏层的向量作为节点的嵌入。

         图表示学习的应用和发展主要基于两个方面：第一，由于图数据类型本身的特点，其结构复杂、属性类型多样，其中蕴含的信息丰富，对应特征提取的方法应能合理针对此类数据的结构特点；第二，图中的信息要应用到其他的数据分析和学习任务中，就需要有合适的表达形式，通过图表示学习进行向量化就是合适的选择之一。

       node2vec的原理是通过图结构里的遍历，生成节点的序列，再将这些序列视为文本导入word2vec中的cbow或者skip-gram模型，最终从隐层权重中抽取出embedding。通过这种方式即可得到每个节点的向量（对应word2vec中每个词的向量）。

       图结构中， 如果任意生成序列，会导致序列的意义坏掉。所以node2vec中采样方法是一种综合考虑DFS邻域和BFS邻域的graph embedding方法。简单来说，可以看作是deepwalk的一种扩展，可以看作是结合了DFS和BFS随机游走的deepwalk。

       这种方式实际上是一种带偏随机游走（Biased Random Walk），它相当于插值BFS和DFS，并通过两个参数p，q来调节两者的比例。

       通过这样的操作就抽取出了节点序列，再利用skip-gram建模，输入为中心节点，输出为此中心节点的周边节点，神经网络隐层向量即为对应节点的embedding。Embedding主要是从网络中学到隐式的表达矩阵，使得图的重要信息如图的结构信息以及语义信息等能被包含在一个新的相对低维的空间向量中。

metapath2vec是Yuxiao Dong等人在2017年KDD发表的论文中提出的方法，是异构图表示学习领域较早、应用较多的一个重要方法，在最近几年相关领域的研究中也常作为benchmark之一。该方法和node2vec的相似点在于都是采用了词嵌入的解决思路，区别在于metapath2vec将这类方法扩展到了异构图的处理中。

异构图是指存在不同类型的节点和边的图，这类数据在现实中是天然存在的，对于异构性不能忽略的任务，比如金融场景下的图结构数据，研究相对较多的同构图表达方法是不能够满足需求的，但其异构性也是表示学习过程中的难点。metapath2vec提出的方法是通过预定义metapath将异构信息分别提取表示，以文献引用数据为例，算法流程大致如下图所示：

按照预定义的metapath（如图a中APA，APVPA，OAPVPAO）用条件概率随机游走的方式抽取节点序列，构建节点对，用skip-gram的方法进行训练，构建一层隐藏层的神经网络，训练完成后隐藏层即为对应节点的表示向量。为了使整个框架更好地处理异构性，metapath2vec还有一个升级版metapath2vec++，在skip-gram这一步中使用的概率分布替换为对应不同节点类型的概率分布，相比使用总体分布而言更好的区分了不同类型节点在embedding过程中的作用。

下图为采用metapath2vec的方法对文献引用数据集的节点进行128维的节点嵌入实验结果的2维t-SNE可视化，可以看出，其特征向量的区分效果还是不错的。

损失函数的基本形式可以表达为：

可以用梯度下降等学习算法训练参数。

此后，在GNN大框架之下，后续涌现了各种各样的图神经网络模型，下图展示了按照图类型、训练方法和传播形式三种不同分类标准下细分的各类GNN模型，有基于CNN、RNN的方法，也有基于文本处理的方法，最近几年比较多的研究把关注点放在GCN（Graph Convolutional Network）、GAT（Graph Attention Network）、GGNN（Gated Graph Neural Network）等方向，解决网络深度、感受野、规模化、动态、异构型等等技术难点。

这里的函数输入是节点的属性和图的邻接矩阵，输出是一个特征矩阵。

其中H是输入节点矩阵，W是参数矩阵，A是图的邻接矩阵，右边括号内的式子，就是当前节点的输出等于邻接节点的加权平均，sigma函数是利用一次非线性变换来增强模型的能力。

对上面这个式子进行改进，A只考虑了邻接节点，缺少自身节点的信息，可以用A+I来替换A，以保持与传统卷积定义一致。另外，用节点的出入度来对加权平均进行归一化处理，D表示度矩阵，改进后的公式如下所示：

实际上，GCN就是在用周围点的向量传播出自己的embedding，这个过程可分为图中信息收集和更新两步。

简言之，收集是对上一层的所有邻接节点的embedding按照某种方式进行汇总，获得一个embedding，供本层进行更新。

而更新就是对本层已经收集完毕的邻接节点数据乘上矩阵W之后再加上一个激活函数，最终输出本层的embedding。

       GCN能同时对节点特征信息与结构信息进行端到端学习，是目前图表示学习中受到广泛关注的一种方法。

       本文对什么是图表示学习进行了介绍，对图表示学习的主要方法和最新的研究进展进行了讨论。随着图特征提取技术的进步，图将会更好地应用到机器学习任务中去，并在越来越多的领域发挥作用。