视频链接:【图神经网络】GNN从入门到精通
代码连接:《图嵌入》
零、引言
- 图嵌入包括:
DeepWalk
,LINE
,SDNE
,Node2vec
,Struc2vec
- one-hot的缺点:
- 向量长度===节点的数量,不适合节点数量大的
- 丢失节点在图中的部分信息(我理解的是拓扑信息)
- graph embedding的作用
- 简化了向量的长度
- 保留了节点中的信息(猜测是拓扑信息)
一、Deep Walk
1 .1 随机游走与深度游走
参考资料:
RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。给定当前访问起始节点,从其邻居中随机采样节点作为下一个访问节点,重复此过程,直到访问序列长度满足预设条件。假设图为,其中,表示图中点的集合,表示图中边的集合,在RandomWalk中关键的问题是如何计算从节点跳转到 的概率
其中,是图中所有边的集合, 是节点的 所有的出边的集合, 是节点 到节点 的边的权重,对于无向无权图
1.2 伪算法
- deepwalk理论演示
- 图a展示了原始的用户行为序列
- 图b基于这些用户行为序列构建了物品相关图,可以看出,物品A,B之间的边产生的原因就是因为用户U1先后购买了物品A和物品B,所以产生了一条由A到B的有向边。如果后续产生了多条相同的有向边,则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后,全局的物品相关图就建立起来了。
- 图c采用随机游走的方式随机选择起始点,重新产生物品序列。
- 图d最终将这些物品序列输入word2vec模型,生成最终的物品Embedding向量。
- 如下图所示,在给定节点时,计算节点同时出现的概率.
Q:那么如何给出节点的embedding represent?
-
window size :以某个 节点为中心在随机游走链上向前或向后的扩展的范围。正因为限制了范围,我们可以忽略窗口之外的链子上的节点,减少工作量(自己的猜测)。进而,限制了游走链的长度。。 如果对于一全连通图来说,如果不限制游走链的长度,那么概率恒为1,则没有意义了。
-
embedding size :
-
walks per vertex : 以顶点为root进行walk的次数
-
walk length :每次随机游走的长度
-
SkipGram:见博文 《skip-gram(含详细代码)》,
-
《skip-gram的上下文预测算法》。
在这里我理解是:在前面距离中我们要计算在的窗口内出现的概率,与NLP中的skipgram类似,借鉴了该算法用于计算概率。
算法代码:deepwalk
二、LINE
Large-scale Information Network Embedding
提醒:该思想与度大的图没有关系,只是该方法在度大的图上效果比较好。
提醒:DeepWalk在无向图上 作embedding,LINE既可以在无向图又可以在有向图中使用。
2.1 一阶相似性(First-order Proximity)
定义
两个顶点之间的⾃⾝相似(不考虑其他顶点)。 对于由边连接的每⼀对顶点,边上的权重表⽰u和v之间的相似度,如果在u和v之间没有观察到边,则它们的⼀阶相似度为0。⼀阶邻近通常意味着现实世界⽹络中两个节点的相似性。如上图中的节点6合节点7之间的权重很大(线条粗),则说明两者之间具有一阶相似度。
embedding
联合概率分布
定义了无向边的联合概率(见Eq.1),其中是节点的低维空间向量表示(即嵌入表示)。也就是说,节点的嵌入表示经过一个sigmoid函数获得联合概率分布。
经验概率分布
,其中表示节点和节点的权重,表示所有的权重之和。
距离–>KL散度
如果联合概率分布和经验概率分布的距离越小,则说明我们的嵌入表示越好。采用KL散度(见Fig2-2 右侧公式)表示两个函数的距离。
目标函数
我们要最小化距离公式(见公式Eq.2)。将联合概率分布和经验概率分布带入KL散度公式后(展开见Fig.2-2右下角)。在最后一行公式中第一部分是一个常数,第二部分中的是一个常数,因此简化后的距离公式见公式Eq.3。
2.2 二阶相似性(Second-order Proximity)
定义
⽹络中⼀对顶点之间的⼆阶相似度是它们邻近⽹络结构之间的相似性。 在数学上,设表⽰u与所有其他顶点的⼀阶相似度,则u和v之间的⼆阶相似度 由 和决定。 如果没有顶点与u和v都连接,则u和v之间的⼆阶相似度为0。因为有些边观察不到等原因,⼀阶相似度不⾜以保存
⽹络结构。因此提出共享相似邻居的顶点倾向于彼此相似,即⼆阶相似度。 Fig.2-1,节点5和节点6虽然不共边但是具有共有的邻居节点1,节点2,节点3和节点4,说明两者具有二阶相似度.
embedding
如下图,对每个节点定义两个表示向量。
条件概率公式
给定节点时求节点的概率=节点的向量表示乘以节点作为其他节点邻居的向量表示,再进行归一化操作(见公式Eq.4)。
举个栗子。如Fig.2-3右边所示,给定节点求节点的概率的时候,分母选择的时由节点指向的节点们,而不包含.从这也可以看出该算法可以用于有向图。
经验概率公式
,其中表示节点和节点之间的权重,表示节点的出度。栗子如上图所示。
距离-优化目标
Eq.5表示两个概率分布地距离公式,公式中表示用来控制节点重要性地因子。当采用KL散度来求解距离两个概率公式的距离(KL散度公式如图上所示)会得到右下角最后一行公式。从中看到有一个与节点 相关地变量,其他变量都是同时与节点和节点相关,且不存在常数项。尽量使优化目标都同时与两个节点相关。去掉度的影响。
假设,可以使目标函数(见公式Eq.6)只与向量表示有关。
最小化后,选择作为图嵌入表示。
2.3 拼接一阶和二阶embedding
三、node2vec
相关佳文:
- 《万物皆Embedding,从经典的word2vec到深度学习基本操作item2vec》
- 《深度学习中不得不学的Graph Embedding方法》
- 《关于Node2vec算法中Graph Embedding同质性和结构性的进一步探讨》
在node2vec中涉及了两个新概念。BFS应该反映了结构性,DFS反应了同质性. ❓
3.1 同质性(homophily )
在网络中,节点与其周围邻居节点的embedding应该是尽量相似的。在Fig.3-1中,在右上图中颜色相近的节点表示邻居关系,则他们的embedding是相似的。换个栗子,在Figure1中,节点与其相连的节点的embedding表达应该是接近的,这就是“同质性“的体现。
3.2 结构等价性(structural equivalence)
在网络中,节点的结构(所处的功能)相似的节点的embedding应该是尽量接近的。在Fig.3-1中,在右下图中蓝色的节点都是具有中心纽带作用的,其embedding应该是尽量相似的。再来个栗子,在Figure1中,节点和节点都是各自局域网络的中心节点,结构上相似,其embedding的表达也应该近似.
3.3 有策略地游走
这个名字也不知道正确否。
在图中利用来控制偏向DFS或BFS.是转移概率。提醒,Fig.3-2中的Figure2中的不是指节点跳跃到节点的转移概率,而是指节点经过节点后跳转到节点的偏好,在求节点跳跃到节点的转移概率的时候,在偏好的基础上乘以权重,即。
3.4 算法伪代码
- Dimensions :图嵌入地维度
- walks per node : 每个节点随机游走的次数
- walk length :游走地长度
- context size :skipgram的窗口大小
- Return :
- In-out :
- : 图G在下随机游走的概率?
优化目标
见Fig.3-3中公式(1)中,红线表示在给定节点的情况下,其邻居节点出现的概率。
提高效率
在上图右侧,提出了在一个比较长的游走链中,可以分别获得节点的邻居节点。
StochasticGradientDescent随机梯度下降
相关博文
3.5 DFS和BFS的关系
BFS应该反映了结构性,DFS反应了同质性.
3.6 边的embedding
四、Struc2vec
如下图中节点和节点没有直接连边,其邻居也不相连,但是具有结构相似性。考虑通过这种结构相似性,进行embedding表示。
4.1 节点k-hop距离
节点的k-hop距离是一个迭代公式。k-1的hop距离+两个节点k-hop邻居的度距离。这里的度距离是采用DTW的方式求解的。
4.2 DTW距离
DTW的思想和代码:见《时间序列的相似性》
4.3 构建多层加权图
猜测建立多层图的原因:
对于Fig.4-2中的以节点为中心的图,会得到
0-hop的节点集:
1-hop的节点集:
2-hop的节点集:
为了更清晰的表达,将其如Fig.4-4中所变化表示。这样就建立一个节点的0-hop层,1-hop层,2-hop层。显然,对于每个的节点建立自己的一个多层hop图是不科学的。将每个节点的多层hop图融合。因此,每个hop层都要包含所有的节点。至于节点之间的权重(包括层内边的权重和层间边的权重)如何计算呢???
构建方法
- 建立k层多重图
- 确定层内连边和层间连边的权重(公式间Fig.4-5)
- 可以构建有向的图。
4.4 顶点采样序列
4.4 使用skip-gram生成embedding
五、 SDNE:Structural Deep Network Embedding
之前的Deepwalk,LINE,node2vec,struc2vec都使用了浅层的结构,
浅层模型往往不能捕获高度非线性的网络结构。即产生了SDNE方法,
使用多个非线性层来捕获node的embedding.
5.1 encoder-decoder结构
Encoder-Decoder是一个模型构架,是一类算法统称,并不是特指某一个具体的算法,在这个框架下可以使用不同的算法来解决不同的任务。首先,编码(encode)由一个编码器将输入序列转化成一个固定维度的稠密向量,解码(decode)阶段将这个激活状态生成目标译文。
相关佳文:
5.2 算法思想
结构
如图Fig.5-1所示,模型的
- 输入: 是节点的向量表示(见黄色高亮部分), ,在这里表示节点与其他节点的邻居关系
- encoder: 是编码部分(见绿色高亮部分),,对于所有的节点编码部分的参数共享
- 嵌入表示: (见墨绿部分)
- decoder: 是解码部分(见橙色高亮),,对于所有的节点解码部分的参数共享
- 输出:是预测值(见粉色高亮部分), ,且与输入值的维度完全相同
优化目标
二阶相似度
显然,如上流程图红色所示,【节点固有的邻居关系】与【节点预测的邻居关系】越接近则说明我们的【压缩表示】越好,则我们就有助于完成图嵌入这项工作。因此,我们求输入向量和输出向量的距离。
六、总结
文章出处登录后可见!