CS224w图机器学习（六）：Graph Representation Learning

内容简介

本文主要介绍CS224W的第七课，图的表征学习，这里的表征类似于NLP里的word embedding。上一节课讲了图的信息传输和节点分类，节点的类别由节点自身的特征和邻居节点的类别所决定，但节点自身的特征通常依赖于人工干预的特征工程，这里可能会耗时耗力，那么能不能自动化地提取这些信息呢，这就是本节课的主要内容图的表征学习，基于Embedding的方式自动提取节点特征。

此外本文主要介绍Node Embedding手段，对于既定的编码网络结构去优化其参数，并通过优化后的网络自动提取节点特征，但暂不涉及编码网络本身。下一节课将引入图神经网络，专门介绍编码图信息的网络结构。

CS224W Lecture 7: Graph Representation Learning

上图为CS224W第七讲的内容框架，如下链接为第七讲的课程讲义

1 Introduction - Network Embedding

在有监督的机器学习中，针对每个模型都需要特征工程的相关工作，如下图所示。特征工程通常耗时耗力，我们希望有一种手段，能够自动的获取这些特征（Auto ML）。

有监督机器学习的流程

首先我们了解下关于图的特征学习（Feature Learning in Graphs）的目标：高效完成图机器学习过程中的特征工程。

总的来讲，如下图所示，构造一个映射

[公式]

，将图的每个节点都映射到

[公式]

维实数空间，这个过程也可以称之为Embedding（如NLP中的Word Embedding，将每个单词都映射成一个词向量）。

图的特征表示，Embedding

更详细的来讲，如下图所示，我们的任务是将图中的每个节点都映射到低维空间。它有如下特点： 1）实现节点分布式表征（以神经网络识别异常为例，隐藏层的所有特征共同决定节点是否异常，而并非某个单一特征，这个称之为分布式表征）； 2）这个映射过程，既编码图的网络信息，也产生节点表征； 3）低维空间内 向量之间的相似度，能够表示节点之间的相似度。

但是传统的深度学习框架很难解决我们当前的问题。

如下图所示，提取大小固定的图像/网格的特征，我们选择使用CNN（此时输入图像的大小和像素点是固定的）；提取文本序列的特征时，我们选择RNN/ word2vec（此时文本/序列的前后依赖关系是固定的）。

而图的结构比上述场景复杂的多： 1）图有更复杂的拓扑结构； 2）图节点之间不存在固定的顺序关系； 3）图通常是动态变化的，具备多模态特征（multimodal features）。

因此我们需要图场景的Embedding手段。

2 Embedding Nodes

我们将介绍部分的知识，进行问题抽象和数学描述。

假设我们有图

[公式]

，其节点集合为

[公式]

，邻接矩阵为

[公式]

。 对节点进行Embedding（Embedding Nodes）的目标：对节点进行编码，编码后的向量空间中 两节点的相似性 近似于 图

[公式]

中两节点的相似性，即

[公式]

。

学习图节点Embedding的过程，主要分为如下三个步骤：

1）定义编码器（a mapping from nodes to embeddings）； 2）定义节点相似度的衡量方式（a measure of similarity in the original network）； 3）通过

[公式]

优化编码网络的参数。

上述步骤中有两个重要的组成部分，一个是编码器Encoder（

[公式]

），另一个是节点相似度的计算。

关于编码器，我们先引入一个简单的例子：

[公式]

。

[公式]

：如下图，Embedding矩阵

[公式]

的列是节点的Embedding向量，每一行是Embedding向量的一个维度。

[公式]

其实是一个Embedding-lookup（Embedding向量组成的矩阵），每个节点都分配一个唯一的Embedding向量。 这是一个最简单的方法，后续我们会相继介绍DeepWalk、node2vec、TransE等手段。 关于节点相似度的计算，不同Node Embedding方法的核心区别在于他们的相似度计算方法。

3 Random Walk Approaches to Node Embeddings

这部分将主要介绍两种方法：DeepWalk与node2vec，关于这两种方法详情，可参见下述两篇文献。

3.1 DeepWalk

介绍DeepWork前，我们先引入随机游走（random walk）。

如下图所示，给定一张图和一个节点，我们随机选择它的一个邻居，并移动到这个邻居节点。 紧接着我们再以相同的方式选择下一个邻居节点，随后继续以此方式在图上实现随机游走。 为什么要在此处引入随机游走呢？ 1）表达性（Expressivity）：能结合局部和高阶邻域信息的节点相似性 2）效率高（Efficiency）：训练时无需考虑所有节点对，只考虑随机游走时相遇的节点对，而它能提升效率。

在随机游走的基础之上，我们来看基于随机游走的Embedding。

首先引入相似度的衡量方法：节点

[公式]

在网络上随机游走时遇到节点

[公式]

的概率。 定义Embedding向量的相似度计算：使用余弦相似度。 如下图，基于随机游走的Embedding流程则可表示为： 1）在随机游走策略

[公式]

的基础下，估计节点

[公式]

游走到节点

[公式]

的概率

[公式]

； 2）基于

[公式]

和Embedding向量的余弦相似度，优化编码网络的参数。

在上述前提之下，我们有了明确的解决图Node Embedding的思路，现在就提供此思路下的解决方法，我们先看损失函数怎么搞？

给定图

[公式]

，定义映射

[公式]

， 我们的目的是优化目标函数：

[公式]

，其中

[公式]

是根据随机游走策略

[公式]

所得到的节点集合。 使用目标节点替换上述公式中的

[公式]

，我们可知损失函数如下（多一个负号，是因为优化目标为损失函数最小）：

[公式]

[公式]

，通过softmax对随机游走到节点

[公式]

的概率进行处理（因为概率需归一化）。 最终，目标映射

[公式]

参数优化的损失函数以及各部分的含义如下图所示。

依据上述公式不难发现损失函数的计算复杂度为

[公式]

，就这么直接优化计算压力太大。同时我们也发现复杂度高的很重要一部分原因在于

[公式]

预测概率softmax的计算，此时可通过negative sampling降低复杂度。

首先对softmax公式进行拆解：

[公式]

如下图，

[公式]

为softmax函数，目的同样是概率归一化。公式右边将计算复杂度为

[公式]

的向量计算，转变为随机过程，所有节点的计算都服从这一随机分布，然后随机抽样

[公式]

次，使用随机抽样的结果来代替原来的计算，如此右边公式的计算复杂度则降低为

[公式]

。 通常

[公式]

越大，估计的值越可靠，同时负样本的偏差也越大，

[公式]

的经验值通常选5-20。

DeepWalk节点表征只剩了最后一小部分，随机游走的策略。我们先看最简单的游走策略，再对DeepWalk的节点表征步骤进行总结。

随机游走策略：从每个节点开始，进行固定长度且没有偏差的随机游走，

[公式]

固定长度的随机游走访问到的节点集合。 DeepWalk节点表征： 1）基于随机游走策略

[公式]

运行一段固定长度的随机游走； 2）对于每个节点

[公式]

，收集其随机游走所访问到的节点集合

[公式]

； 3）使用随机梯度下降（或其他优化算法）优化损失函数

[公式]

，最终得到映射

[公式]

的最优参数。 DeepWalk的缺点： 1）相似度定义 相对固定； 2）无法检测到距离较远但是相似度很高的节点。

3.2 node2vec

DeepWalk无法检测距离较远但相似度高的节点，核心在于其随机游走策略过于局部，我们需要一个灵活的有偏差的随机游走策略，权衡全局视图游走、局部视图游走以及游走复杂度的策略。这个策略是Biased Walk。

如上图所示，我们如果想要局部的视角，广度优先搜索（BFS）可以满足我们的要求；如果我们想要深度的视角，深度优先搜索（DFS）则可以满足要求。 有偏差的固定长度的随机游走策略

[公式]

，则由两个参数控制： 1）返回参数（Return Parameter）

[公式]

：返回上一个节点的概率； 2）深度/广度参数（In-out Parameter）

[公式]

：节点进行深度优先/广度优先的比例，通常

[公式]

定义为广度优先 / 深度优先。 详情可参见下图，由上述两个参数，控制（从

[公式]

游走到）

[公式]

节点的路径选择概率： 假设广度优先游走的概率为单位1，那么返回上一节点的概率为

[公式]

，深度优先游走的概率为

[公式]

（非归一化的概率）。 总结：参数

[公式]

：广度优先游走/返回上一节点；参数

[公式]

：广度优先游走/深度优先游走。

node2vec节点表征的步骤如下：

1）计算节点随机游走到各个目标节点的概率； 2）按上述概率，模拟从每个节点开始的步长为

[公式]

的

[公式]

次随机游走； 3）使用随机梯度下降（或其他优化算法）优化损失函数

[公式]

依据Goyal和Ferrara等人2017年的调查（详情可参见下述文献），没有一种方法在所有任务上都表现最优，node2vec在节点分类上效果表现更好，而multi-hop（暂未介绍）在关系预测上表现更好。

4 Translating Embeddings for Modeling Multi-relational Data

上一部分讲述的是图的节点表征，这一部分则主要讲述知识图谱的Embedding。知识图谱是相互间有关联的实体（A knowledge graph is composed of facts/statements about inter-related entities）。知识图谱如果不完备，则会影响（依赖当前知识图谱的）系统的运行效率。因此对于知识图谱来讲，我们任务的重点是关系预测（Link Prediction）。

我们介绍一种新的手段：Translating Embedding（TransE）

在TransE中，节点间的关系有如下三元组表征：

[公式]

实体（entity）表征为一个实体空间

[公式]

，类似于上一部分所提到的内容； 关系（relation）表征为translations：如果

[公式]

则关系存在，如果

[公式]

则关系不存在。 再重新审视三元组，（头实体、关系、尾实体）头实体和尾实体都属于实体，关系用来表征头实体和尾实体之间是否存在确切的关系。

我们再看下TransE的算法详情：

算法详情如下图所示。 整体来看算法流程与第三部分所提的内容相似，唯一的差别在于节点的表征方式变成了

[公式]

。

5 Embedding Entire Graphs

如果我们想对整个图进行Embedding，此时又该怎么办呢？比如我们想识别异常图的时候，（化学场景中）想区分有毒和无毒的化学分子的时候（化学分子的有毒无毒，和分子内部的原子组成有一定程度的关系，对原子构造进行Embedding，可用于判断分子是否有毒）。

文章简单描述了三种整图的Embedding手段（但并未进行详细介绍），整图和节点Embedding的主要差别还是如何处理图内的节点，当处理好图内节点后，整图的Embedding和节点Embedding的差别也就不大。关于整图的处理手段 如下：

方法一：

[公式]

写出这个公式，基本不难猜测该方法的基本思想，把图内每个节点的Embedding向量求和，作为整图的Embedding向量。 详情可参考下述文献：

方法二： 引入“虚拟节点”的概念，将子图看作是虚拟节点，与子图内节点存在连接的节点，都看作与虚拟节点之间存在连接。 详情可参考下述文献：

方法三： 匿名游走（anonymous walk）的思想如下图： 其核心思想在于：在随机游走时不考虑具体某个单一节点，而只考虑游走的模式，并对游走模式进行Embedding。

详情可参考下述文献：