图表示学习

简介

综合转载于：

• 图表示学习极简教程

• 深度学习中不得不学的Graph Embedding方法

• 关于Node2vec算法中Graph Embedding同质性和结构性的进一步探讨

Introduction

随着Deep Learning的爆火，图数据挖掘和CV、NLP等领域一样，存在着“爆发式”发展的趋势。更加准确地说，笔者认为图数据挖掘正处在爆发的前夜。本文主要从基于图结构的表示学习和基于图特征的表示学习两个角度简要介绍图表示学习的现状和自己的认识。

在非图的表示学习中，研究者们主要考虑的是每一个研究对象的特征(姓名、年龄、身高等)信息。然而，研究对象是存在于客观世界的主体，存在一定的图结构信息(QQ、微信好友，师生关系等都构成了图网络)。如何对图结构进行表示学习以表示图的结构信息是一个很重要的topic。

图表示学习的主要目标是：将结点映射为向量表示的时候尽可能多地保留图的拓扑信息。图表示学习主要分为基于图结构的表示学习和基于图特征的表示学习。如图1，基于图结构的表示学习对结点的向量表示只来源于图的拓扑结构( $n \times n$ 的邻接矩阵表达的图结构)，只是对图结构的单一表示，缺乏对图结点特征消息的表示。如图2，基于图特征的表示学习对结点的向量表示既包含了图的拓扑信息( $n \times n$的邻接矩阵表达的图结构)也包含了已有的特征向量( $n$个维度为$f$包含结点特征的向量，如姓名、年龄、身高等信息)。

通过上述的介绍，我们可以知道图表示学习的task就是用 n 个向量表示图上的 n 个结点，这样我们就可以将一个难以表达的拓扑结构转化为可以丢进炼丹炉的vector啦。

基于图结构的表示学习

在我们的图表示学习中，我们希望Embedding出来的向量在图上“接近”时在向量空间也“接近”。对于第2个“接近”，就是欧式空间两个向量的距离。对于第一个“接近”，可以有很多的解释：

• 1-hop：两个相邻的结点就可以定义为临近；
• k-hop：两个k阶临近的结点也可以定义为临近；
• 具有结构性：结构性相对于异质性而言。异质性关注的是结点的邻接关系；结构性将两个结构上相似的结点定义为“临近”。比方说，某两个点是各自小组的中心，这样的两个节点就具有结构性。

DeepWalk

早期影响力较大的graph embedding方法是2014年提出的DeepWalk，它的主要思想是在由物品组成的图结构上进行随机游走，产生大量物品序列，然后将这些物品序列作为训练样本输入word2vec进行训练，得到物品的embedding。图3用图示的方法展现了DeepWalk的过程。

如图3，整个DeepWalk的算法流程可以分为四步：

1. 图a展示了原始的用户行为序列
2. 图b基于这些用户行为序列构建了物品相关图，可以看出，物品A，B之间的边产生的原因就是因为用户U1先后购买了物品A和物品B，所以产生了一条由A到B的有向边。如果后续产生了多条相同的有向边，则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后，全局的物品相关图就建立起来了。
3. 图c采用随机游走的方式随机选择起始点，重新产生物品序列。
4. 图d最终将这些物品序列输入word2vec模型，生成最终的物品Embedding向量。

在上述DeepWalk的算法流程中，核心是第三步，其中唯一需要形式化定义的是随机游走的跳转概率，也就是到达节点 $v_i$ 后，下一步遍历 $v_i$ 的临接点 $v_j$ 的概率。如果物品的相关图是有向有权图，那么从节点 $v_i$ 跳转到节点 $v_j$ 的概率定义如下：

$$P\left(v_j \mid v_i\right)= \begin{cases}\frac{\mathbf{M}_{i j}}{\sum_{j \in N_{+}\left(v_i\right)} \mathbf{M}_{i j}}, & v_j \in N_{+}\left(v_i\right), \\ 0, & e_{i j} \notin \mathcal{E},\end{cases}$$

其中$N_+(v_i)$是节点 $v_i$ 所有的出边集合，$Mij是节点vi到节点vj边的权重。

如果物品相关图是无向无权重图，那么跳转概率将是上面公式的一个特例，即权重Mij将为常数1，且N+(vi)应是节点vi所有“边”的集合，而不是所有“出边”的集合。

Node2vec

2016年，斯坦福大学在DeepWalk的基础上更进一步，通过调整随机游走权重的方法使graph embedding的结果在网络的同质性（homophily）和结构性（structural equivalence）中进行权衡权衡。

具体来讲，网络的“同质性”指的是距离相近节点的embedding应该尽量近似，如图4，节点u与其相连的节点s1、s2、s3、s4的embedding表达应该是接近的，这就是“同质性“的体现。

“结构性”指的是结构上相似的节点的embedding应该尽量接近，图4中节点u和节点s6都是各自局域网络的中心节点，结构上相似，其embedding的表达也应该近似，这是“结构性”的体现。

其中，网络的“同质性”指的是距离相近节点的embedding应该尽量近似，如图1中，节点u与其相连的节点s1、s2、s3、s4的embedding表达应该是接近的，这就是“同质性“的体现。

“结构性”指的是结构上相似的节点的embedding应该尽量接近，图1中节点u和节点s6都是各自局域网络的中心节点，结构上相似，其embedding的表达也应该近似，这是“结构性”的体现。

Node2vec在具体的实现上，是通过调整模型参数，使随机游走更倾向于宽度优先搜索（BFS），或者深度优先搜索（DFS），从而在embedding结果中更好的体现“结构性”或者“同质性”，那么，下面就到了比较容易让人困惑的问题了：

到底是宽度优先搜索（BFS）更能体现“结构性”，还是深度优先搜索（DFS）更能体现“结构性”呢？

当然，对于“同质性”，我们同样可以问出一个对偶问题。到底是宽度优先搜索（BFS）更能体现“同质性”，还是深度优先搜索（DFS）更能体现“同质性”呢？

为了使Graph Embedding的结果能够表达网络的同质性，在随机游走的过程中，需要让游走的过程更倾向于宽度优先搜索（BFS），因为BFS更喜欢游走到跟当前节点有直接连接的节点上，因此就会有更多同质性信息包含到生成的样本序列中，从而被embedding表达；另一方面，为了抓住网络的结构性，就需要随机游走更倾向于深度优先搜索（DFS），因为DFS会更倾向于通过多次跳转，游走到远方的节点上，使得生成的样本序列包含更多网络的整体结构信息。

不知道大家跟我最初的想法是不是一致，遗憾的是，这种想法是与论文原文的解释相反的，恰恰是BFS更多抓住了网络的结构性，而DFS更能体现网络的同质性。为什么？

结合原文和自己的理解，我这里给出一个可能正确的解释，因为并没有通过实验去验证，最“正确”的做法当然是你自己实现之后评估一下哪种结果更能体现同质性。

对于宽度优先搜索（BFS）来说，其搜索往往是在当前节点（这里以节点u为例）的邻域进行的，特别是在node2vec中，由于存在所谓的“返回概率”，所以即使从u搜索到了s1，也有很大概率从s1再返回u，所以BFS产生的序列往往是在u附近的节点间进行来回的震荡，这就相当于对u周围的网络结构进行了一次微观扫描（microscope view）。

那么这个微观扫描当然更容易得到微观结构的观察，所以BFS就更容易使embedding结果更多反应网络的“结构性”。这里我需要纠正一下大家对“结构性”的理解，正如上面所说的一样，这里的“结构”更多的指的是微观结构，而不是大范围内，甚至整个网络范围内的宏观结构，而是一阶、二阶范围内的微观结构。

再举个例子理解一下，比如对于节点u和节点s9这两个节点来说，节点u是局部网络的中心节点，节点s9是一个十分边缘的节点。那么在对这个网络进行多次BFS随机游走的过程中，节点u肯定会被多次遍历到，而且会与s1-s4等更多节点发生联系，而边缘节点s9无论从遍历次数，还是从邻接点的丰富程度来说都远不及节点u，因此两者的embedding自然区别很大。

如果用DFS进行遍历，由于遍历存在更大的不确定性，因此s9有更大的可能被包含在更多的序列中，并跟更多的节点发生联系，这就减弱了局部结构性的信息。类似于平滑了结构性的信息，自然是不如BFS更能反应“微观结构”了。

另一方面，为什么说DFS更能反应“同质性”呢？

这里还要对“同质性”也进行一个纠正，这里的“同质性”不是指一阶、二阶这类非常局限的同质性，而是在相对较广范围内的，能够发现一个社区、一个群、一个聚集类别的“同质性”。要发现这类同质性，当然需要使用DFS进行更广范围内的探索。如果仅用BFS在微观范围内探索，如何发现一个社区的边界在哪里呢？

所以，DFS相当于对网络结构进行了一次宏观扫描（macroscope view），只有在宏观的视角，才能发现大的集团、社区的聚集性，和集团内部节点的“同质性”。

那么在node2vec算法中，是怎样控制BFS和DFS的倾向性的呢？主要是通过节点间的跳转概率。图5显示了node2vec算法从节点t跳转到节点v后，下一步从节点v跳转到周围各点的跳转概率。

形式化来讲，从节点v跳转到下一个节点x的概率为

$$\pi_{\mathrm{vx}}=\alpha_{p q}(t, x) \cdot \omega_{v x}$$

其中$\omega_{v x}$是边vx的权重，$\alpha_{p q}(t, x)$的定义如下：

$$\alpha_{p q}(t, x)= \begin{cases}\frac{1}{p} & \text { if } d_{t x}=0 \\ 1 & \text { if } d_{t x}=1 \\ \frac{1}{q} & \text { if } d_{t x}=2\end{cases}$$

其中，$d_{tx}$指的是节点$t$到节点$x$的距离，参数$p$和$q$共同控制着随机游走的倾向性。参数$p$被称为返回参数（return parameter），$p$越小，随机游走回节点t的可能性越大，node2vec就更注重表达网络的同质性，参数$q$被称为进出参数（in-out parameter），$q$越小，则随机游走到远方节点的可能性越大，node2vec更注重表达网络的结构性，反之，当前节点更可能在附近节点游走。

论文中最后通过实验的方式验证了DFS和BFS对于“同质性”和“结构性”的挖掘结果。颜色接近的节点代表其embedding的相似性更强。图2上图是node2vec更倾向于DFS的结果，可以看到各聚类的内部节点相似，这是网络“同质性”的体现；而图2下图中，结构类似节点的embedding更为相似，这是“结构性”的体现。

node2vec所体现的网络的同质性和结构性在推荐系统中也是可以被很直观的解释的。同质性相同的物品很可能是同品类、同属性、或者经常被一同购买的物品，而结构性相同的物品则是各品类的爆款、各品类的最佳凑单商品等拥有类似趋势或者结构性属性的物品。毫无疑问，二者在推荐系统中都是非常重要的特征表达。由于node2vec的这种灵活性，以及发掘不同特征的能力，甚至可以把不同node2vec生成的embedding融合共同输入后续深度学习网络，以保留物品的不同特征信息。

阿里的EGES

2018年阿里公布了其在淘宝应用的Embedding方法EGES（Enhanced Graph Embedding with Side Information），其基本思想是在DeepWalk生成的graph embedding基础上引入补充信息。

如果单纯使用用户行为生成的物品相关图，固然可以生成物品的embedding，但是如果遇到新加入的物品，或者没有过多互动信息的长尾物品，推荐系统将出现严重的冷启动问题。为了使“冷启动”的商品获得“合理”的初始Embedding，阿里团队通过引入了更多补充信息来丰富Embedding信息的来源，从而使没有历史行为记录的商品获得Embedding。

生成Graph embedding的第一步是生成物品关系图，通过用户行为序列可以生成物品相关图，利用相同属性、相同类别等信息，也可以通过这些相似性建立物品之间的边，从而生成基于内容的knowledge graph。而基于knowledge graph生成的物品向量可以被称为补充信息（side information）embedding向量，当然，根据补充信息类别的不同，可以有多个side information embedding向量。

那么如何融合一个物品的多个embedding向量，使之形成物品最后的embedding呢？最简单的方法是在深度神经网络中加入average pooling层将不同embedding平均起来，阿里在此基础上进行了加强，对每个embedding加上了权重，如图7所示，对每类特征对应的Embedding向量，分别赋予了权重$a_0$，$a_1…a_n$。图中的Hidden Representation层就是对不同Embedding进行加权平均操作的层，得到加权平均后的Embedding向量后，再直接输入softmax层，这样通过梯度反向传播，就可以求的每个embedding的权重$a_i(i=0…n)$。

在实际的模型中，阿里采用了$e^{a_j}$而不是$a_j$作为相应embedding的权重，一是避免权重为0，二是因为$e^{a_j}$在梯度下降过程中有良好的数学性质。阿里的EGES并没有过于复杂的理论创新，但给出一个工程性的结合多种Embedding的方法，降低了某类Embedding缺失造成的冷启动问题，是实用性极强的Embedding方法。

时至今日，Graph Embedding仍然是工程和学术领域研究和实践的热点，除了本节介绍的DeepWalk，Node2vec，EGES等主流的方法，还有LINE，SDNE等方法也很流行。

基于图特征的表示学习

在基于图特征的表示学习中，由于加入了结点的特征矩阵 $X$ (姓名、年龄、身高等这样的特征)，需要同基于图结构的表示学习区别开来。这一类的模型通常被叫做“图神经网络”。

GCN

Graph Convolutional Networks(图卷积网络)是非常基本第一个GNN模型。在讨论GCN之前，我们先来看一下CNN(卷积神经网络)是怎么做卷积运算的。如图6所示，CNN的两个主要特点是局部感知与权值共享。换句话说，就是聚合某个像素点周围的像素特征。

类似地，在GCN中，新的特征也是对上一层邻居结点特征的聚合，公式如下：

$$H^{(l)}=\sigma\left(D^{-\frac{1}{2}}(A+I) D^{-\frac{1}{2}} H^{(l-1)} W^l\right)$$

其中 $A$ 是邻接矩阵，$D=\operatorname{diag}\left(d_1, d_2, \ldots, d_n\right)$是顶点的度矩阵(对角阵)，$I$是单位阵，$W$是神经网络层与层之间传播的系数矩阵。此外$H$表示的是该层的结点特征矩阵，第一层的特征矩阵$H_0$是原始的结点特征矩阵$X$。也许有人会有疑问，DNN的输入应该是一个向量，为什么这里用的是矩阵的表示呢？其实，这里的矩阵可以视作是由多个向量组成的，可以类比于CNN中的“多通道”概念。我们来看一下下面的公式推演：

$$\begin{aligned} & H(X)=D^{-0.5} A D^{-0.5} X W \\ & \Rightarrow\left[\begin{array}{ccccc} \frac{1}{\sqrt{d_1}} & & & \\ & \frac{1}{\sqrt{d_2}} & & & \\ & & \ddots & \\ & & & \frac{1}{\sqrt{d_n}} \end{array}\right]\left[\begin{array}{cccc} A_{11} & A_{12} & \cdots & A_{1 n} \\ A_{21} & A_{22} & \cdots & A_{2 n} \\ \vdots & \vdots & \ddots & \vdots \\ A_{n 1} & A_{n 2} & \cdots & A_{n n} \end{array}\right]\left[\begin{array}{cccc} \frac{1}{\sqrt{d_1}} & & & \\ & \frac{1}{\sqrt{d_2}} & & \\ & \ddots & \\ & & & \frac{1}{\sqrt{d_n}} \end{array}\right] \\ & \Rightarrow\left[\begin{array}{cccc} \frac{A_{11}}{\sqrt{d_1}} & \frac{A_{12}}{\sqrt{d_1}} & \cdots & \frac{A_{1 n}}{\sqrt{d_1}} \\ \frac{A_{21}}{\sqrt{d_2}} & \frac{A_{22}}{\sqrt{d_2}} & \cdots & \frac{A_{2 n}}{\sqrt{d_2}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{A_{n 1}}{\sqrt{d_n}} & \frac{A_{n 2}}{\sqrt{d_n}} & \cdots & \frac{A_{n n}}{\sqrt{d_n}} \end{array}\right]\left[\begin{array}{llll} \frac{1}{\sqrt{d_1}} & & & \\ & \frac{1}{\sqrt{d_2}} & & \\ & & \ddots & \\ & & & \frac{1}{\sqrt{d_n}} \end{array}\right] \\ & \Rightarrow\left[\begin{array}{cccc} \frac{A_{11}}{\sqrt{d_1} \sqrt{d_1}} & \frac{A_{12}}{\sqrt{d_1} \sqrt{d_2}} & \cdots & \frac{A_{1 n}}{\sqrt{d_1} \sqrt{d_n}} \\ \frac{A_{21}}{\sqrt{d_2} \sqrt{d_1}} & \frac{A_{22}}{\sqrt{d_2} \sqrt{d_2}} & \cdots & \frac{A_{2 n}}{\sqrt{d_2} \sqrt{d_n}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{A_{n 1}}{\sqrt{d_n} \sqrt{d_1}} & \frac{A_{n 2}}{\sqrt{d_n} \sqrt{d_2}} & \cdots & \frac{A_{n n}}{\sqrt{d_n} \sqrt{d_n}} \end{array}\right] \Rightarrow \sum_i \frac{A_{i j}}{\sqrt{d_i d_j}} X W, j \in \text { Neighbor }(i) \\ & \end{aligned}$$

根据上面的推导，我们不难从最后一个公式中看看出结点 $i$ 在下一层的表示是由其所有的邻居结点 $j$ 所构成集合 Neighbor $(i)$ 来决定的。因此，我们换一个视角，从每一个结点的角度来看GCN的公式。我们可以发现公式可以表示为：

$$h_v^l=\sigma\left(W^l \sum_{u \in \mathcal{N} i} \bigcup v \frac{h_u^{l-1}}{\sqrt{\left|N_u\right| \cdot\left|N_v\right|}}\right)$$

其中$h_v^l$是第$l$层网络中结点 $v$的向量表示，$h_v^{l-1}$是第$l-1$层网络上一结点$v$的向量表示。$\mathcal{N}_i$表示的是结点$i$的邻居结点构成的集合。公式和上面的一堆推导可以说是殊途同归。其核心的意思都表示的是“邻居结点的聚合”。从直观层面，GCN的含义就是“聚合”的含义。然而，从图信号角度对GCN进行分析，又会是一番新的境界。

GraphSAGE

GCN提出之后，同年的NIPS上GraphSAGE也横空出世，其主要的特点是固定的采样倍率和不同的聚合方式。

采样倍率

在GCN中，我们采用的聚合方式是将一个结点的所有邻居进行聚合。若每一层结点的邻居结点个数为 $\bar{d}$ ，那么经过$K$层的聚合后，结点的聚合代价为$\sum_{i=0}^k \bar{d}^i$。若$\bar{d}=10, K=3$，那么每个结点就要有1111个结点参与计算，要是乘上所有的结点个数，计算的代价简直credible。

对于邻居节点的聚合，GraphSAGE在一个epoch中，作者并未将某个结点所有的邻居结点进行聚合，而是设置一个定值$S_k$，在第$k$层选择邻居的时候只从中选最多只选择$S_k$个邻居结点进行聚合，计算的复杂度大致在$\mathcal{O}\left(\prod_{k=1}^K S_k\right)$这个水平。这一改进对GNN的落地有着重要意义。

聚合方式

结点聚合应该满足：

1. 对聚合结点的数量自适应：向量的维度不应随邻居结点和总结点个数改变。
2. 聚合操作对聚合结点具有排列不变性：e.g.$\operatorname{Agg}\left(v_1, v_2\right)=\operatorname{Agg}\left(v_2, v_1\right)$。
3. 显然，在优化过程中，模型的计算要是可导的。

根据上述的几点原则，作者提出了几种聚合方式：

• 平均/求和聚合算子(mean/sum)

  $$\text{Agg}^{\text {sum }}=\sigma\left(\text{SUM}\left\{W h_i+b, \forall v_j \in \mathcal{N}\left(v_i\right)\right\}\right)$$

  其中 $W$ 和 $b$ 都是需要learning的参数。

• 池化算子(pooling)

  $$\text{Agg}^{\text {pooling }}=\text{MAX}\sigma\left(\left\{W h_i+b, \forall v_j \in \mathcal{N}\left(v_i\right)\right\}\right)$$

  对其中的MAX的含义是各元素上运用max算子计算。

• LSTM聚合

  与平均聚合相比，LSTM聚合具有更大的表达能力。但是，重要的是LSTM并不具有排列不变性，因为它们是以顺序方式处理其输入。因此，需要将LSTM应用于节点邻居的随机排列，这可以使LSTM适应无序集合。

GAT

自从有了Attention机制之后，似乎万物皆可Attention了。在图学习中，Graph Attention Network就是引入了注意力机制的GNN。说到底，GAT还是对邻居结点信息的聚合：

$$h_{v_i}^l=W^l \sigma\left(\sum_{v_j \in \mathcal{N}\left(v_i\right)} \alpha_{i j}^l h^{l-1} v_j\right)$$

其中$\alpha_{i j}$是结点$v_i$与其相邻结点 $v_j$ 之间的权重系数，$\alpha_{i j}$ 的计算公式为：

$$\alpha_{i j}=\frac{\exp \left(\text { LeakyReLU }\left(\alpha^T\left[W h_i \| W h_j\right]\right)\right)}{\sum_{v(k) \in \mathcal{N}\left(v_i\right)} \operatorname{LeakyReLU}\left(\alpha^T\left[W h_i \| W h_k\right]\right)}$$

其中 $||$ 是concat操作，权重参数向量$\alpha \in R^{2 \cdot d^{l+1}}$ 。这个公式乍一看比较复杂，其实是由两个部分组成。如图7(左)，首先算出相关度的权重系数$e_{i j}=\operatorname{LeakyReLU}\left(\alpha^T\left[W h_i | W h_j\right]\right)$，然后在对 $e_{ij}$进行softmax归一化处理，以确保权重之和为1。其实这里的Attention不就是一个加权嘛。

此外，作者在提出GAT时也提出了多头注意力机制的方法。如图7(右)所示，不同的颜色代表了不同的注意力计算过程，并将结果进行拼接或平均。具体公式如下：

$$\begin{aligned} h^{\prime} v_i & =\|_{k=1}^K \sigma\left(\sum_{v_j \in \mathcal{N}\left(v_i\right)} \alpha_{i j}^l W^l h_{v_j}\right) \\ \text { or : } h^{\prime} v_i & =\sigma\left(\frac{1}{K} \sum_{k=1}^K \sum_{v_j \in \mathcal{N}\left(v_i\right)} \alpha_{i j}^l W^l h_{v_j}\right) \end{aligned}$$