第3章



图表示学习


在本章中，将介绍图表示学习(Graph Representation Learning，GRL)的基本概念和相关算法。图表示学习是表示学习与图结构数据相结合产生的方法，其目的是将高维稀疏的图结构数据映射到低维稠密向量，同时来捕获网络拓扑结构及网络中节点的内在特征。现有的图表示学习方法按照图的学习技术可以大致分为三类： 基于矩阵分解的图表示学习
、基于随机游走的图表示学习和基于深度学习的图表示学习。按照研究图的类型可以分为同质图表示学习和异质图表示学习。本章将围绕这些图表示学习方法进行详细介绍。
3.1图表示学习的意义

图是一种简单、易于理解的数据表现形式。一般而言，工业图中的节点数量巨大，而且边与边之间的连接并不稠密，
如微博社交网络。在如此大而稀疏的图数据上，直接进行深度学习存在一定的局限性。图上的节点和边
的关系，一般只能使用统计或者特定的子集进行表示，或者
使用邻接矩阵表示。若直接在节点集合上做计算，或者直接采用维度较高的邻接矩阵来做计算都不太合适。
例如，一个具有百万节点的图，其邻接矩阵的图占据的存储空间将至少达到数百
吉比特。直接用邻接矩阵做计算将带来严重的内存消耗问题，同时也会影响计算效率。基于这些弊端，人们提出了图表示学习方法。
如图31所示，图表示学习是一种将图数据(通常为高维稀疏的矩阵)映射为低维稠密向量的方法，同时通过图表示学习来捕获网络拓扑结构及图中节点的本质属性，用来加速图数据的计算效率，提高建模灵活性。图表示学习需要保持
原有图的拓扑结构特征，例如，原图连接的节点，在嵌入向量空间中需要保持彼此靠近。


图31顶点表示学习示意图


根据嵌入粒度的程度，可以将图表示学习分为两类，即顶点嵌入和整图表示学习。顶点嵌入
是针对每个节点生成一个低维度的向量表征。这种图表示学习方式粒度较细，一般用于在节点层面上进行预测，
如节点分类。如图31所示，将
G(V,E)的稀疏的节点信息，映射到低维的向量空间中，这里V是顶点集合，E为边集合，映射到
|V|个维度为Rd的向量空间中。整图表示学习则是针对全图生成一个向量，这种图表示学习方式粒度较粗，一般用于在整图层面上进行预测或比较的场景。

在过去的数十年里，学术界一直没有停止对图表示学习方法的研究。总结过去的研究成果，可以将图表示学习按方法分为三类，如图32所示，包括基于矩阵分解的图表示学习方法、基于随机游走的图表示学习方法和基于
神经网络的图表示学习方法。在本章中，介绍各类方法的一些具体算法，帮助读者
全面深入地了解图表示学习。


图32图表示学习算法的分类



3.2基于矩阵分解的图表示学习方法

图结构的矩阵表示通常包括邻接矩阵(Adjacency Matrix)和拉普拉斯矩阵(Laplacian Matrix)。基于矩阵分解的图表示学习通过矩阵分解获取图中的节点向量表征。在本节中
将详细介绍一个典型的基于分解的图表示学习： 拉普拉斯映射(Laplacian Eigenmaps，LE)。

LE算法是Mikhail Belkin和Partha Niyogi于2002年提出的基于图的降维方法，其核心思想是希望相互有连接的点在降维后的空间中能尽可能地被拉近，从而尽量维持降维之前的数据结构特征。如图33所示，假设在一个维度为
Rn的流形空间中存在点集合X={x1,x2,…,xN}，其中xi∈Rn,LE算法的目标是将这些点映射到一个低维度空间Rd
中(dn)，对应的映射坐标集合为Y=
{y1,y2,…，yN}，其中yi∈Rd，且保证高维空间中离得很近的点投影到低维空间中的像也应该离得很近。LE算法的主要目的是学习映射关系y=F(x)。


图33LE算法



给定的流形空间中的数据点集X={x1,x2,…,xN}属于散点集合，可以被视为图中顶点集合V，然而边却不是预先给定的。那么如何构建点之间的边呢？这里介绍一种基于近邻距离的构建边的方法，即如果点xi和xj足够接近，则在这两点之间添加一条边来构建边集合E。如图33(b)所示，如果两个点落在以ε为半径的球内则构建边，即‖xi-xj‖2<ε作为判断条件决定是否在点xi与点xj之间构建边。当然也可以给边赋予一定的权重，一种方式是存在边则Wij=1，否则为0，称为二元权重(Binary Weight)，另一种方式是给边赋予高斯权重Wij=e-‖xi-xj‖22σ2，σ2为标准差。

上述过程已经可以构建起图G(V,E)。接下来具体讲解LE算法利用图结构来实现降维的原理。按照
LE算法的核心思想，降维的关键在于尽可能使原空间中相近的点在降维后的目标空间中也尽可能相近，可以将此问题转化为优化目标，公式如下：



miny∈Rd∑i∑jWij
‖yi-yj‖2(3.1)


其中，‖yi-yj‖2表示目标空间内两个数据点间的距离，Wij表示原空间内两个数据点间的边权重，这里采用高斯权重，即连续型变量Wij∈(0,1］。原空间中xi与xj越靠近，Wij越大，此时yi和yj也必须靠近； 
原空间中xi与xj越远，Wij越小，yi和yj相对位置则比较灵活。

然而，式(3.1)并不能很好地约束y，例如yi=yj=
0。为了避免所有新坐标均为0或受缩放效应的影响，加一个约束‖yi‖2=1。需要指出的是，式(3.1)可以做进一步转化。


∑i∑jWij‖yi-yj‖2=2YTLY(3.2)


其中，Y=
［y1，y2,…，yn］∈Rn×d,L为图G(V,E)的拉普拉斯矩阵，可以改写为



minYTDY=12YTLY(3.3)


该问题便转化为一个广义特征值的问题，即求解如下特征方程： 


Lrwvi=λivi(3.4)


其中，Lrw=D-1L=D-1(D-W)=I-D-1W。D为度矩阵。根据式(3.4)计算拉普拉斯矩阵的特征向量和特征值，并以此得出降维后的结果输出。Y=
［v2，…，vd+1］∈Rn×d。

LE算法可以将已有的特征高维变换获取简约特征。LE算法可用于高维的数据降维和可视化，例如降低维度为二维或者三维。然而，LE算法的复杂度为节点数量的平方，导致该算法不能适用于大规模图。
3.3基于随机游走的图表示学习

本节重点讲解基于随机游走的图表示学习，随机游走学习节点相似度是基于领域节点相似的。随机游走的图表示学习借鉴了经典的词嵌入算法Word2Vec，通过随机游走等采样方法从图中采样若干条由节点序列，将其视为自然语言中的句子，然后使用Word2Vec模型训练得到节点的嵌入向量。
首先介绍Word2Vec算法，然后介绍DeepWalk和Node2Vec两个典型的基于随机游走的模型，最后介绍随机游走算法的优化技术。
3.3.1Word2Vec算法

Word2Vec算法在2013年由Google提出，该算法将语料中的词的高维度独热(OneHot)表征形式，通过神经网络学习得到低维词向量。在自然语言模型中，单词是划分后的最细粒度，单词组成句子，句子再组成段落和文章。对于语料中的单词，一种最简单的词向量方式是独热表征，即采用一个很长的向量来表示一个词。
独热向量的长度为词汇表的大小，词典中的位置表示为1，其他均为0。如图34所示。
‘我’表示为［1,0,0,0,0］T，‘在’表示为［0,1,0,0,0］T。然而每一种语言都有成千上万个单词，如果想用独热的方式表示这些单词，就会导致每一个单词的维度非常大，造成维度灾难。同时词语之间的独热编码是正交的，无法计

算词之间的相似性。为此就需要用词嵌入算法找到一个合适的映射函数，能使高维度的索引向量嵌入到一个相对低维的向量空间内。Word2Vec算法的最终目的是为了得到各个词的低维向量表达，解决独热编码的不足。Word2Vec学习到的词向量的意义更为清晰，相关联的词在词向量空间中是相互靠近的。在数学上，意义相关的词之间的距离比无关的词之间的距离小。如图35所示，意义相近的词“美丽”与“漂亮”之间的距离会比较靠近。Word2Vec包含连续词袋模型(Continuous Bag Of Words,CBOW)和跳字模型(SkipGram)两种算法。


图34独热词表达转化低维词向量示意图




图35词向量空间中词的相对关系示意图


强调一下，Word2Vec学习的目的是为了获得词在低维空间的向量表达，学习到的低维度的向量表达需要能描述词之间近似或者关联。因此，设计的模型要预测上下文，从而调整好模型参数，得到最终的词向量表达。

(1) 连续词袋模型。

CBOW是一个用上下文单词预测当前词的模型，如图36所示。当前语料的词序列为
w(1),w(2),…,w(T)，其中包含
|V|个相异的词，构成词表集合W={w1,w2,…,w|V|}。词wk的
独热表征为Xk=
［x1,x2,…,x|V|］，向量Xk的分量中只有xk=1，其余均为0。
CBOW算法的目的是根据背景词w(t-n),w(t-n+1),…,w(t+n-1),w(t+n)简写为w
B(t)来预测中心词w(t)的概率，即p(w(t)|wB(t))，n表示背景窗口大小，即句子内中心词前后n个词作为背景。算法结构如图36所示，首先将2n个背景词的独热表征形式
Xb1,Xb2,…,
Xb2n通过共享权重矩阵W∈R|V|×d映射到维度为Rd的向量： 


zbk=WTXbk=WT(bk,:)(3.5)




图36CBOW计算结构示意图



zbk∈Rd对应矩阵WT的第bk行，称为词wbk的输入词向量
(Input Embedding Vector)，得到
{zb1,zb2,…,zb2n}。隐藏层h∈Rd，是直接对周围词向量的求和
h=∑2ni=1zbi或者平均
h=12n∑2ni=1zbi。从隐藏层到输出层的共享权重矩阵为W′∈Rd×|V|,设中心词w(t)对应词表中的第j
*个词，w(t)对应的词向量为W′的第j*列
z′j*，z′j*称为词w(t)的输出词向量
(Output Embedding Vector)。将隐藏层h映射到维度R|V|的向量
u=W′Th∈R|V|，并通过一个
Softmax层计算词表中的词为中心词的概率：


P(w(t)|wB(t))=exp(uj)∑|V|iexp(ui)=exp(
z′Tj*h)∑|V|iexp(z′Tih)(3.6)


(2) 跳字模型。

跳字模型根据中心词w(t)来预测背景词wB(t)的条件概率，用数学公式可以描述为P(wB(t)|w(t))∈R1。若假设中心词预测周围词的概率是相互独立的，则有


P(wB(t)|w(t))=∏-n≤j≤n,j≠0P(w(t+j)|w(t))(3.7)


举个例子，在句子“我在京东买手机”中，我们根据“京东”来预测周围词的概率，则可以表述为： P(我,在,买,手机|京东)=P(我|京东)P(在|京东)P(买|京东)P(手机|京东)。
如图37所示，SkipGram算法结构与CBOW模型类似，但是其输入为中心词wc，首先根据中心词的独热表征Xc映射得到隐藏层h∈Rd。


h=WT·Xc(3.8)




图37SkipGram算法结构示意图


通过输出变换矩阵W′∈Rd×|V|，将隐藏层h映射到维度
R|V|的向量u=W′Th，并通过一个Softmax层计算词表中各词的概率： 


P(w1|wc)

P(w2|wc)

P(w3|wc)

︙

P(w|V||wc)=exp(
W′T·h)∑Vi=1exp(
W′T·h)=exp(u)∑
|V|iexp(ui)(3.9)


设背景词wB(t)对应词表的序列为j*1,j*2,…,j*2n，对应W′的第j*1,j*2,…,j*2n列，可以得到背景词的预测概率： 


P(wB(t)|w(t))=∏2nk=1exp(uj*k)∑|V|iexp(ui)(3.10)


(3) 模型训练。

在深度学习中，一般方式是最小化损失函数，而不是最大化损失函数。为了与之对应，在
式(3.6)与式(3.10)上加一个负号。同时，对P(w(t)|wB(t))和P(wB(t)|w(t))采用单调递增的自然对数是为了降低计算复杂度。在整个语料w(1),w(2),…,w(T)上计算平均损失函数，公式如下： 


LCBOW(W,W′)=-∑Tt=1
ln(P(w(t)|wB(t)))(3.11)

LSkipGram(W,W′)=-∑Tt=1ln
(P(wB(t)|w(t)))(3.12)


为了得到权重参数W、W′，只需要利用反向传播算法来训练这个神经网络即可，反向传播算法可参考第1章。由损失函数形式可知，
CBOW模型比Skip模型训练速度更快。一般而言，SkipGram模型对词频较低的词优于CBOW模型。需要
强调的是，Word2Vec模型的最终目的是得到词表的向量化表达，即矩阵WT的列向量(输入词向量)或者W′T的行向量(输出词向量)。

3.3.2DeepWalk
DeepWalk由Bryan Perozzi等人
Perozzi B,AlRfou R,Skiena S.Deepwalk：  Online learning of social representations［C］//Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining.2014：  701710.
于2014年提出的。DeepWalk借鉴了Word2Vec的思想，希望借助两个点之间的共现关系(Cooccurrences)来学习向量表征表示。Word2Vec中所对应的数据输入格式是由一个个单词组成的句子，通过句子中单词的共现关系学习表征，但对于图数据结构，如何获取类似的数据呢？ 由于图是非线性的，所以
需要一个策略将其转换为线性输入。DeepWalk通过随机游走的方式提取顶点序列，根据顶点和顶点的共现关系，学习顶点的向量表示。DeepWalk抽取顶点序列的方法是随机游走(Random Walk)，可以说随机游走是整个DeepWalk中最重要也是最具有开创性的一部分算法。


随机游走是一种可重复访问已访问节点的深度优先遍历算法。对于给定的一个图中的起始节点，随机游走算法会从其邻居
节点中随机抽取一个节点作为下一个访问点，游走到下一个节点后重复上述过程，直到访问序列达到预设长度(
需要注意的是，被访问的点不会被标记删除，也不会更新访问它的概率，因而随机游走可以重复访问已访问的节点)。

在图G(V,E)，顶点vi∈V的邻居节点集合记作N(vi)，vi的度记为D(vi)。对于顶点vi∈V为随机游走起点，记作tr(0)vi，生成一个随机序列
Tr=tr(0)vi,tr(1)vi,…,tr(T-1)vi，如图38所示
，其中T是一个超参数，表示游走序列长度。这里按照对邻居节点等概率采样机序列


P(tr(t+1)vi|tr(t)vi)=

1d(tr(t)vi),tr(t+1)vi∈N(tr(t)vi)

0，其他
(3.13)




图38随机游走示意图



其中，N(tr(t)vi)表示节点tr(t)vi的邻居集合，d(tr(t)vi)表示节点tr(t)vi的度。依次从上一个访问顶点的邻居节点中均匀随机采样一个顶点作为序列的下一个点。经T步随机游走，

为了充分挖掘节点vi在全图中的上下文信息，DeepWalk算法中，可以每个节点vi∈V为中心，生成γ个独立随机游走序列，记作Tr(0)vi，Tr(1)vi,…,Tr(γ-1)vi，总共会产生γ|V|个随机游走序列，类似
于Word2Vec语料中的γ|V|个句子。

随机游走还有并行化和适应性两大优势。并行化体现在一个大的网络中可以同时开始多个从不同顶点开始的随机游走，这可以大大减少运行时间； 适应性指的是由于随机游走具有局部性，使
其能很好地适应网络的局部变化，网络在演变过程中通常只会有部分点和边产生变化，这些变化只会对一部分随即游走
的路径产生影响，因此在网络变化后只需要重新采样这部分改变的点和边，不需要重新计算整图的随机游走。

如图39所示，与SkipGram算法相对应，在DeepWalk中，对于随机游走序列
Tr=tr(0)vi,tr(1)vi,…,tr(T-1)vi，设观测窗口大小为n，顶点tr(j)vi作为中心词其前后n个顶点tr(j-n)vi，tr(j-n+1)vi，…,tr(j+1)vi,…，tr(j+n)vi是tr(j)vi的上下文。按照
SkipGram算法，以tr(j)vi为输入，预测邻居节点tr(j+k)vi的条件概率
，可写为P(tr(j+k)vi|tr(j)vi)。若节点tr(j)vi在顶点表中
的序号为sj，类似于Word2Vec算法，需要将
独热形式的节点表征Xsj∈R|V|通过共享权重矩阵
W∈R|V|×d映射为zsj=
WTXsj∈Rd的低维向量表征。W′∈Rd×|V|为输出权重矩阵，设z′i∈Rd为输出权重矩阵
W′T的第i行，则通过Softmax函数来计算概率： 


P(tr(j+k)vi|tr(j)vi)=z′sj+k·zsj∑vi∈Vexp(z′i·zsj)(3.14)





图39随机游走序列Tr中节点tr(j)vi的上下文关系示意图


对于采样序列Tr的优化目标为


maxW，W′
∏tr(j)vi∈Tr∏-n≤k≤n,k≠0z′sj+k·zsj∑vi∈Vexp(z′i·zsj)(3.15)


通过随机游走获得序列数据之后，便可以使用Word2Vec中的两个模型来进行训练。这里只介绍使用SkipGram模
型获取这些节点的向量嵌入，SkipGram模型的细节见3.2节相关部分。


整体过程如图310所示，由于图是非线性的，DeepWalk先采用随机游走生成节点的随机序列，后将游走序列视为句子，然后采用SkipGram算法对顶点共现关系建模，来学习节点表征。


图310DeepWalk计算示意图


3.3.3Node2Vec
首先回顾一下图算法中经典的采样策略，即广度优先采样(Bre
adthfirst Sampling，BFS)和深度优先采样(Depthfirst Sampling，DFS)两种采样策略。如图311所示，以u节点为起点深度优先采样出
s4、s5、s6,而广度优先则采样出s1、s3、s4。


图311源节点为u的深度优先和广度优先遍历策略示意图



图表征的目的是得到节点间的相似性。网络的相似性有同质性(Homophily)和结构等价性(Structural Equivalence)两个评价标准。同质性是指属于同一集聚结构的两个节点更加相似，如图311中的s1和u。结构等价性是指在两个近似的集聚结构中扮演类似角色的节点间更具有相似性，如节点s6和u。那么采样策略对图节点的向量表征的学习有什么影响呢？

广度优先可以获得每个节点的所有邻居，强调的是局部微观视图，所以通过BFS采样的网络更能体现网络的局部结构，从而产生的表征更能体现结构等价性； 而DFS可以探索更大的网络结构，只有从更高的角度才能观察到更大的集群，所以其嵌入结果更能体现同质性。

Node2Vec是另一种基于随机游走的图表示学习算法，于2016年被Aditya Grover等人
Grover A,Leskovec J.node2vec：  Scalable feature learning for networks［C］//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.2016：  855864.
提出。Node2Vec的最大突破
是改进了DeepWalk中的
随机游走采样策略。接下来
将详细介绍Node2Vec中采用的有偏向的游走策略。Node2Vec是一种综合考虑DFS邻域和BFS邻域的图表示学习方法。此处设计了一种灵活的邻居节点抽样策略，它允许
用户在BFS和DFS间进行平衡。Node2Vec 可以通过参数设置来控制搜索策略，从而有效
地平衡图表示学习的同质性和结构有效性。

Node2Ve引入了两步随机游走算法，如图312所示。第一步从节点t游走到节点v，第二步从节点v游走至其邻居节点，如x1、x2、t等。节点v跳转到邻居节点的
概率不再是均匀分布的，而是根据节点t与节点x来共同确定，可以表示为α(vt+1|vt,vt-1)。这里是根据节点t与节点x的最短路径距离来确定，可将候选游走节点分为三类，并由两个超参数p和q来调控，α(vt+1|vt,vt-1)具体为


α(vt+1|vt,vt-1)=

1p，d(vt-1,vt+1)=0

1，d(vt-1,vt+1)=1

1q，d(vt-1,vt+1)=2(3.16)




图312Node2Vec随机游走


其中，d(vt-1,vt+1)表示从节点vt+1到节点vt-1的最短路径距离。当d(vt-1,vt+1)=0时，即节点vt跳转回节点vt-1，α(vt+1|vt,vt-1)=1/p；  若d(vt-1,vt+1)=1，即vt+1∈N(vt-1)，也就是说vt+1为vt-1的邻居节点，此时α(vt+1|vt,vt-1)=1； 若d(vt-1,vt+1)=2，即vt+1N(vt-1)，此时α(vt+1|vt,vt-1)=1/q。其中p被称为返回参数(Return Parameter)，q被称为进出参数(Inout Parameter)。

对于参数q：  若q>1，随机游走会倾向于访问与t相连的节点，从而体现出BFS特性；  若q<1，那么随机游走会倾向于访问远离t的节点，即朝着更深的节点游走，从而体现出DFS特性。对于返回参数p： 若p>max(1,q)，则返回的概率会变得相对较小，这时候游走会倾向于不往回走，更倾向DFS特性； 若p<max(1,q)，则返回的概率会变得相对较大，这时候游走会倾向于往回走，多步游走会倾向于围绕在起始点附近，更倾向DFS特性。

获得采样序列后，接下来的处理流程与DeepWalk相同，总体流程如图313所示。
当Node2Vec设置p=q=1时，等价于DeepWalk。


图313Node2Vec算法流程


3.3.4随机游走模型的优化策略

随机游走策略的图表示学习方法，预测共现关系的模块为SkipGram算法。在传统模型的预测阶段，需要利用一个Rd×|V|的权重参数将Rd维的中间向量
转回一个|V|维的向量，再通过Softmax归一化计算每个节点的预测概率，最后进行损失计算和预测。这种方法在处理大量节点的图时会有速度过慢的问题。下面介绍分层Softmax(Hierarchical Softmax)和负采样(Negative Sampling)两种优化算法。
1. 分层Softmax

分层Softmax算法重新设计了SkipGram的输出层。以图
G(V,E)中的节点为叶子节点，以节点的度为权重构造一棵霍夫曼树(Huffman Tree)
，如图314所示，用此霍夫曼二叉树结构的神经网络代替原先的
SkipGram神经网络层。在这棵二叉树中，叶子节点共有|V|个
，
非叶子节点共有|V|-1
。在分层Softmax算法中，隐藏层到预测概率的输出不是一下子完成的，而是沿着霍夫曼树从根节点一步步向前传播至叶子节点完成的，相应传播路径上的内部节点则起到隐藏层神经元的作用。


图314霍夫曼树示意图



如图314所示，假设输入节点为vi预测节点vp图中示例预测目标为
(vp=v3)，先将独热编码的输入节点向量
Xi∈R|V|转换为低维度的隐藏层向量
h∈Rd，再沿着霍夫曼
树向前传播至叶子节点。对二叉树中的每一个叶子节点，存在唯一由根节点到该叶子节点的路径。在
分层Softmax中，我们利用这条路径估计当前预测值是否为该叶子节点表示的单词的概率
P(vp|vi)。在图314中，从根节点传播至vp的路径如红色路线所示。在
分层Sotfmax模型中，假设这条传播路径是随机游走形成的，每步游走过程是相互独立的，于是根据独立事件的联合概率原则可以得到


P(vp=v3|vi)=P(n(vp,1),left)·P(n(vp,2),right)·P(n(vp,1),left)(3.17)



其中，n(vp,j)表示从根节点到叶子节点vp路径上的第j个霍夫曼树节点。P(n(vp,j),left)表示节点
n(vp,j)指向它的左孩子的概率，而P(n(vp,j),left)则表示节点n(vp,j)指向它的右孩子的概率。此处向左向右的选择，可以视为一个二分类问题，每一个内部节点向左孩子节点游走的概率为


P(n(vp,j),left)=σ(θvpj·hT)(3.18)


其中，θvpj∈Rd表示内部节点n(vp,j)的可学习向量，
σ(x)=11+e-x表示Sigmoid激活函数。在二叉树中，每个内部节点只会存在左孩子或者右孩子节点，则节点n(vp,j)指向右孩子的概率为


P(n(vp,j),right)=1-σ(θvpj·hT)=σ(-θvpj·hT)(3.19)


式(3.17)更一般的形式为


P(vp|vi)=∏L(vp)-1j=1σ(
［n(vp,j+1)=ch(n(vp,j))］·θvpjT·h)(3.20)


ch(n(vp,j))表示节点n(vp,j)的左孩子节点，L(vp)是根节点到叶子节点的路径长度，
［x］为一个符号函数：


［x］=
1，x为true


-1，其他(3.21)


［n(vp,j+1)=ch(n(vp,j))］用来指示节点n(vp,j)下一步游走至左孩子还是右孩子。为了最大化
预测概率P(vp|vi)，在分层Softmax模型中的损失函数可以定义为



L=-ln(P(vp|vi))=-∑L(vp)-1j=1lnσ(［n(
vp,j+1)=ch(n(vp,j))］·θvpjT·h)

(3.22)


训练的复杂度，从原来的O(|V|)下降到O(ln(|V|))。
2. 负采样(Negative Sampling)
在DeepWalk和Node2Vec算法中，使用
随机游走嵌入算法在图G(V,E)采样，生成线性序列，然后使用中心节点来预测观测窗口内的共现节点出现的概率。节点
预先采用维度为R|V|独热编码,训练后得到Rd的低维度表征。如图315所示，
观测窗口为2时，我们使用训练样本(输入节点为tr(j)vi,预测节点
为tr(j-2)vi、tr(j-1)vi、tr(j+1)vi、tr(j+2)vi)。出现在
观测窗口中的样本称为正样本(Positive Sample)。不在窗口内的样本称为负样本(Negative Sample)。对于正样本，其对应的神经元的期望值为1，剩下的元素则为0。图的节点个数
|V|决定SkipGram神经网络会存在大规模的权重矩阵，这些权重需要通过
大量的训练样本进行调整，会
消耗大量的计算资源。负采样方法中，选择留下正样本及部分采样得到的负样本，并不对每个样本更新所有权重，而是每次让一个训练样本仅仅更新一小部分权重，其他权重全部固定，从而降低梯度下降过程中的计算量，提升训练速度。


图315随机游走嵌入算法示意图



为了提升训练权重参数矩阵的质量，负采样修改目标函数，既考虑正样本也考虑负样本，需要最大化成对的概率，而最小化不关联节点对的概率，对应的损失函数为



L=∑nj=-n-p(tr(j+k)vi|tr(j)vi)+∑j+kn∈trnegp(tr(j+kn)vi|tr(j)vi)(3.23)


其中，trneg表示负样本集合，即不处在节点tr(j)vi观测窗口内的节点集合，这里只抽取部分负样本来计算，故称为负采样。如图315所示，正样本是处于观测邻居内的节点集合。负采样因为只计算部分负样本，故能加速计算，使得随机游走模型能适应规模更大的图。

这里通过图315讲解负采样的过程。假设图的节点个数
为|V|，当输入节点tr(j)vi进入预测模型时，对其共现节点tr(j+1)vi的输出向量维度为
R|V|,在此向量中我们希望tr(j+1)vi对应的位置为1，其余位置
为0。如果按照传统的训练方式，这里所有的输出向量对应的权重参数都需要更新，而负采样的对象
是|V|-1位，负采样策略是从中选择一小部分，并用这一小部分负样本进行权重更新。在小规模数据集上，一般对每个顶点选择5~20个负样本会比较好，而在大规模数据集上可以仅选择2~5个负样本。假设负采样的个数为k，则计算复杂度为全部采样的k|V|。

从负样本中抽取样本时，需要按照合适的概率分布来抽取，才能让学习到的权重参数更好。这里
介绍一种常用的采样概率分布： P(v)~d(v)3/4，具体为


P(vi)=d(vi)34∑v∈V(d(v)34)(3.24)


其中，d(vi)代表顶点vi出现的度。
3.3.5其他随机游走方法

DeepWalk可以视作一个基于深度优先的随机游走算法，Node2Vec则综合了深度优先与广度优先。这两种算法
都是基于邻域相似假设的方法，即网络中相似的点在向量表示中的距离比较近，但是这两种算法只考虑了成边的顶点之间的相似度，并未对不成边顶点之间关系的建模。LINE(Largescale Information Network Embedding)模型
既考虑成边的顶点对之间的关系(称为局域相似度)，也考虑未成边顶点的相似度(称为全局相似度)。LINE算法为图的局域相似度和全局相似度设计了专门的度量函数，用来学习得到保持图局域和全局结构的低维节点表征
ui∈Rd，且能适用于无向图和有向图。

局域相似度用一阶相似度(Firstorder Proximity)描述，表示图中直接相连的节点之间的相似
度。具体来说，存在边的两个节点之间的相似度为其边的权重ei,j，对于不存在边的节点间，则权重为0，图316中6和7就是一阶相似，因为6和7直接相连。对于每一条无向边(vi,vj)，节点vi、vj之间的一阶联合概率为



P1(vi,vj)=11+exp(-zTi·zj)(3.25)




图316网络中一阶关系和二阶关系示意图


其中，zi∈Rd是节点vi的需要学习的低维向量表征。同时定义需要拟合经验概率(Empirical Probability)，即归一化的边权重： 



P^1(vi,vj)=Wij∑(m,n)∈EWmn(3.26)


优化目标就是尽可能拉近这两个分布的距离。常用的衡量两个概率分布差异的指标为KL散度,目标函数可写为



O1=-∑(i,j)∈EWijlnP1(vi,vj)(3.27)


需要注意的是，一阶相似度只能用于无向图。

全局相似度是用二阶相似度(Secondorder Proximity)来衡量两个节点的邻居节点之间的相似度。二阶相似度假设那些具有相同邻居节点的节点在特征上较为相似，具体来说，若两个节点的邻居节点集合
Ni与Nj之间有许多重叠，则认为两个节点之间拥有很高的二阶相似度。直观地来解释就是拥有共享邻居的节点
更为相似，在许多现实的例子中可以印证这一点，例如，拥有相同社交网络的两个人很可能有共同的兴趣。图中的5和6就是二阶相似，因为它们虽然没有直接相连，但是它们连接的其他节点中有重合(1,2,3,4)，因此节点5和6在特征空间内的表示也会十分接近。

在二阶相似度中，对于任意顶点v∈V，算法中维护两个向量，一个是该节点本身的表示向
量u∈Rd，另一个是该节点作为其他节点的邻居时的表示向量
u′∈Rd，即作为其他节点的上下文。对于任意一对有向边(vi,vj)，我们可以定义在给定一个节点vi的条件下，产生邻居节点vj的概率为



P2(vj|vi)=exp(u′Tj·ui)∑|V|k=1exp(
u′kT·ui)(3.28)


其中，ui为给定节点vi对应的表征向量，此时观测其邻居为vj的概率，u′j为顶点vj充当邻居角色的向量表征。式(3.28)实际上定义了P2(·|vi)对所有上下文的条件分布。为了能够保留二阶相似
度，需要使上下文的条件概率分布和其经验分布P^2(·|vi)之间的距离尽可能的小，其经验分布为


P^2(vj|vi)=Wij∑k∈Vwik


二阶相似度的目标是尽可能让两个节点的邻居节点集合，所以其优化目标为



O2=∑i∈Vλid(P^2(·|vi),P2(·|vi))(3.29)


其中d(·)代表两个分布的距离，同样使用KL散度来进行度量，另外引入了控制节点重要性的因子λi,这里将λi定义为顶点的出度di，则二阶相似度的目标函数可以优化为


O2=-∑(i,j)∈Eωijlnp2(vj|vi)(3.30)


之后通过合并一阶、二阶相似度的优化目标完成LINE的模型优化。

在计算二阶相似度中的条件概率p2(vj|vi)时，需要对所有顶点进行计算，这样的计算成本是非常高的，为了解决这个问题，原论文

Tang J,Qu M,Wang M,et al.Line： Largescale information network embedding［C］//Proceedings of the 24th international conference on world wide web.2015： 10671077.

中提出了负采样的方法，通过使用一些噪声分布进行负样本采样，于是可以将对于每一条边(i,j)的优化目标转化为



lnσ(
u′jT·ui)+
∑Ki=1
Evn~Pn(v)［lnσ(-u′nT·ui)］(3.31)


其中，激活函数为σ(x)=1/(1+exp(-x))，第一项为对一阶相似度进行建模，第二项是对从噪声分布中提取的负样本进行二阶相似度建模，K为负样本的个数。

同时，模型中还存在着另一个问题，
在O1和O2的优化函数中，ln前有一个权重参数wij，在使用梯度下降优化参数时，wij会直接
与梯度相乘，这时如果wij的方差过大，就会很难选择一个合适的学习率，如果学习率选择过大，则较大的wij
可能出现梯度爆炸，而如果学习速率选择过小，则较小的wij可能出现梯度过小。
对于上述问题，一种最简单的方法是将带权边拆成等权边，如果所有边的权相同，那么选择一个合适的学习率就会比较方便，举例来说，这种方法可以将一条权重为w的边拆成w条权重为1的边。

3.4基于深度学习的图表示学习

本节将重点介绍基于深度学习的图表示学习。随着时代的发展和算力的提升，深度学习也再次成为了热门的研究内容，利用深层的神经网络对图结构进行嵌入表征也成为了图研究学习中的一类不可忽视的重要方法。在本节内容中，我们将以SDNE为例，向读者介绍深度学习是如何被运用到图表示学习中的。

结构深层网络嵌入(Structural Deep Network Embedding，SDNE)是Daixin Wang等人
Wang D,Cui P,Zhu W.Structural deep network embedding［C］//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.2016：  12251234.
于2016年提出的一种图表示学习方法，同时也是第一种将深度学习应用于网络表征学习的方法。在SDNE中，使用了一个自动编码器优化图中节点的一阶、二阶相似
度，采用一阶相似度学习局域网络结构，采用二阶相似度来学习全局的相似度，这使得该方法所获得的表征向量能同时保留图的局部和全局结构。
3.4.1局域相似度和全局相似度

假设有图G(V,E)，其中V={v1,v2,…,vn}表示图中的n个节点，E=
{ei,j}ni,j=1表示边，其中每一条边都有其权重si,j，若两个节点间没有边，则其权重为0。一阶相似
度用来表示图中成对节点之间的相似度，用来学习局域图结构。具体来说，两个节点i、j之间的相似
度即为两点之间边的权重si,j，若之间没有连接，则相似度为0。一阶相似度可以直接表示节点对之间的相似度，
然而真实环境下的信息网络往往存在大量的信息缺失，导致存在许多一阶相似度为0的节点，而它们相似
度也很高。例如，构建的人际档案信息中，如果两个人存在很多共同的朋友，那么这两个人很有可能也认识。为此，基于节点邻居的相似度，提出了二阶相似度，用来表征全局相似度。二阶相似度是两个节点的邻居节点之间的相似度。具体来说，若两个节点的邻居节点集合之间有许多重叠，则认为两个节点之间拥有很高的二阶相似度。假设
Ni={si,1,…,si,|V|}表示节点vi的一阶邻居，Nj={sj,1,…,sj,|V|}表示节点vj的一阶邻居，则节点i和j的二阶相似度表示为Ni与Nj之间的相似度。引入二阶相似度后，更能表征网络结构，使得稀疏网络更具有
健壮性。
3.4.2SDNE算法结构图
图317是SDNE算法的结构，SDNE分为两部分来实现局域相似和全局相似。局域相似度采用拉普拉斯映射的方法，在嵌入空间中保留原图的节点的相对距离。SDNE采用节点邻居间的相似度来表示全局相似度。
对于节点vi对应的邻居信息为邻接矩阵S∈
R|V|×|V|的第i行，表示为si∈R|V|。同理，对于节点vj，邻居信息表示为sj。si和sj已经蕴含了两个节点间的二阶相似度，这里并未直接给出二者相似度的大小，而是希望在嵌入向量y(K)∈Rd中保存节点的邻接特性。


图317SDNE的模型框架图


SDNE使用了自编码器对图的邻接矩阵S进行解码重构，通过这样的重构过程能够使得结构相似的顶点具有相似的表示向量。图317中的自编码器的结构包含一个编码
(Encoder)部分和一个解码(Decoder)部分。编码
部分的作用是将节点vi对应的输入向量
xi=si∈R|V|，压缩到一个低维向量
y(K)i∈Rd，
解码部分的作用是将压缩后的向量还原到原始输入向量空间
x^i∈R|V|，
d|V|。此处采用K层神经网络进行编码，公式如下：



y(1)i=σ(W(1)xi+b(1))(3.32)

y(k)i=σ(W(k)y(k-1)i+b(k)),k=2,3，…,K(3.33)



其中，σ(·)为Sigmoid激活函数。经过编码后得到低维度
向量y(K)i∈Rd，然后经过编码的逆过程解码得到x^i∈R|V|。
W(k)表示
编码第k层的权重矩阵。一般而言，根据解码还原的x^i与输入xi，可以构建如下损失函数： 



L=∑|V|i=1‖x^i-xi‖22(3.34)


由于数据的稀疏性，在邻接矩阵中，存在着很多0值，这使得自编码器在学习过程中学习
了过多的0，
直接导致模型的效果不佳。考虑到由于数据的稀疏性，图的邻接矩阵可能会缺少很多实际上潜在的连接。以推荐系统中用户
—商品的购买二部图为例，用户没有购买商品(即这两个节点之间没有边)的原因可能是
用户不喜欢该商品，也有可能是
用户没有浏览到该商品，因此用户对此商品是有潜在购买可能的。SDNE在传统自编码器的损失函数上进行了一些改动： 


L2nd=∑|V|i=1‖(x^i-xi)⊙bi‖22(3.35)


其中，bi∈R|V|，如果si,j=0,bi,j=1，否则
bi,j=β>1，⊙表示哈达玛积(Hadamard Product)。这样设置可以使模型在将一个非0值的节点预测为0时受到更多惩罚。

局域相似度部分使用了3.3.2节介绍的拉普拉斯特征映射方法，让图中相邻的两个顶点对应的嵌入向量在嵌入空间接近，提取图中的局部特征。在SDNE中，这种想法被融入深度模型中，使得有连接的两个点被映射到附近空间中。损失函数定义如下 



L1st=∑|V|i∑|V|jsi,j
‖y(K)i-y(K)j‖22=
2trace(YTLY)(3.36)


其中，Y=［y(K)1； y(K)2； …； y(K)|V|］,除了这两个损失函数之外，SDNE还增加了一个L2正则化项来防止过拟合： 



Lreg=12∑|V|k=1(
‖W^(k)‖2
F+‖W(k)‖2F)(3.37)


其中，W(k)，
W^(k)分别表示
编码和解码层中第k层的权重矩阵。于是可以得到总的损失函数，即


Lmix=L1st+αL2nd+βLreg(3.38)


其中，α和β是超参数。损失函数可以通过反向传播算法进行优化。
3.5异质图表示学习

上述算法虽然可以用于同构网络(Homogeneous Networks)，即仅适合只包含单一顶点类型和边类型的网络表示学习，
但并不能很好地用于包含多种顶点类型和边类型的复杂关系网络。而在现实世界中，节点类型或者关系类型是
多种多样的。如图318所示的异质图中，存在机构、作者、论文和期刊
4种节点，以及作者与学术机构的归属关系、作者与论文的发表关系、论文与学术期刊的归属关系。针对同构网络设计的模型很多都没法应用于异质网络，例如，对于一个学术网络而言，如何根据上下文信息表征不同类型的节点？为此需要给异质图来设计图表示学习算法。


图318异质图学术网络的Metapath2Vec与Metapath2Vec++算法结构图



给定异质图G=(V,E,X)，其中，V={v1,v2,…,v|V|}为顶点集合，对应的点类型集合为
Tv，顶点映射到对应类型的函数为v，边集合为
E={e1,e2,…,e|E|}，对应的边类型集合为
Te，边映射到对应类型的函数为e。在具体实践中，为了分辨异质的特点，
引入了元路径(metapath)的概念。元路径是在异质图G上按照
元路径模式ψ： A1R1A2R2A3…
RK-1AK来游走产生路径,其中，类型Ai∈Tv，关系
Ri∈Te。复合关系组合为可表示为R1R2…RK-1,其中表示关系运算符，Rl表示第K-1个节点与第K个节点之间的关系。

先介绍基于元路径的随机游走，元路径的模式ψ被用来限制随机游走的决策，即每一步游走需要按照模式ψ设计的节点类型和边类型进行游走，给定类型为Ai节点vψi，跳转概率为


P(vψi+1|vψi)=

1NRii+1(vψi),vψi+1∈NRii+1(vψi)

0,其他(3.39)


其中，NRii+1(vψi)表示节点vψi的邻居中满足边关系为Ri且节点类型为Ai+1的邻居顶点集合。除此之外，元路径通常以一种对称的方式使用，如图318中的元路径是对称的，即顶点A1的类型和AK的类型相同。根据对称性的元路径，P(vi+1|vit)=p(vi+1|vi1)，如果t=K。可以看出，元路径的受限随机采样过程中，对顶点类型与关系都具有限定作用。基于元路径的随机游走可保证不同类型顶点之间的语义关系可以适当地融入SkipGram模型中。

基于元路径的表示学习有两种方法，分别是Metapath2Vec和Metapath2Vec++。在Metapath2Vec中使用基于元路径的随机游走来构建每个顶点的异质邻域，然后使用SkipGram模型，
通过在顶点v的领域Nt(v)，t∈Tv最大化保留一个异质网络的结构和语义信息的似然：


arg maxθ∑v∈V∑t∈Tv∑
ct∈Nt(v)lnP(ct|v;θ)(3.40)


其中，ct为节点类型为Ri的邻居集合NRi(v)，θ为待学习参数，似然概率为


P(ct|v;θ)=eXct·Xv
∑u∈VeXu·Xv(3.41)


图318中，沿着元路径OAPVPAO的节点a4的邻居包括作者(Author)类型节点{a2,a3,a5}、期刊(
Venue)类型节点{ACL,KDD}、机构(Org)类型节点{CMU}、论文(Paper)类型节点
{p2,p3}，k为路径中各种类型邻居的个数之和，即k=kV+kA+kO+kP。为了加速优化过程，可以引入负采样，改进为



arg maxθ∑v∈V∑t∈Tv∑ct∈
Nt(v)lnσ(Xct·Xv)+
∑Mm=1Eum~P(u)［lnσ(-
Xum·Xv)］(3.42)


P(u)是负采样的节点um在M次采样中的预定义分布。

Metapath2Vec在为每个顶点构建领域时，通过元路径来指导随机游走过程向指定类型的顶点进行有偏游走。但是在Softmax环节中，没有分辨顶点的类型，而是将所有的顶点视作同一类型的顶点，如式(3.41)。也就是说，
Metapath2Vec在负采样环节采样的负样本并没有考虑顶点的类型。
在Metapath2Vec++中，Softmax函数根据不同类型的顶点的上下文
ct进行归一化。也就是说P(ct|v;θ)根据固定类型的顶点进行调整，即


P(ct|v;θ)=eXct·Xv∑
ut∈NteXut·Xv(3.43)


其中，Nt是网络中t类型顶点集合。
Metapath2Vec++给SkipGram模型的每种类型的领域指定特定的集合。如图
318所示。最终得到如下的目标函数： 


O(X)=lnσ(Xct·Xv)+∑Mm=1Eumt~Pt(ut)［lnσ(
-Xumt·Xv)］(3.44)


3.6本章小结

本章介绍了以拉普拉斯特征映射为代表的矩阵分解方法，DeepWalk、Node2Vec和LINE的随机游走算法，
以及基于深度学习的SNDE算法，最后介绍了Metapath2Vec和Metapath2Vec++的异质图表示学习算法。
拉普拉斯特征映射算法依据原有高维空间数据的相对位置来构图，优化的目标是在低维空间中尽可能使原空间中相近的点在降维后的目标空间中也尽可能相近，从而得到节点的低维度表示。随机游走算法是一种基于
邻域相似假设的算法，受启发于Word2Vec，来学习节点的向量表示。DeepWalk通过截断深度优先随机游走获取游走序列，Node2Vec的随机游走方式则综合了深度优先和广度优先游走，二者都是通过节点的局域网络特征来学习节点的低维表示。LINE也是一种基于邻域相似假设的方法，可以看作是一种使用广度优先构造邻域的算法。LINE算法同时考虑
网络的局域结构相似度(一阶相似度)和节点邻域的全局相似度(二阶相似度)，然而这两种相似
度是分开考虑的，只是一种简单的组合。SDNE算法是一种深度学习算法，利用深度自编码器学习图中节点的表征向量，结合一阶和二阶相似度进行联合训练。相对于同质图，异质图
的存在更为广泛，在
Metapth2Vec和Metapath2Vec++中采用元路径指导随机游走的邻居节点的选择，即为有偏置的随机游走构建邻居集合，在
SkipGram学习阶段，Metapath2Vec与DeepWalk和Node2Vec一样不考虑节点类型，而
Metapath2Vec++则对不同类型节点单独处理。