【GNN笔记】Graph Embedding(二)

视频链接:【图神经网络】GNN从入门到精通

代码连接:《图嵌入》

零、引言

  • 图嵌入包括:DeepWalk,LINE,SDNE,Node2vec,Struc2vec
  • one-hot的缺点:
  1. 向量长度===节点的数量,不适合节点数量大的
  2. 丢失节点在图中的部分信息(我理解的是拓扑信息)
  • graph embedding的作用
  1. 简化了向量的长度
  2. 保留了节点中的信息(猜测是拓扑信息)

一、Deep Walk

1 .1 随机游走与深度游走

参考资料:

RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。给定当前访问起始节点,从其邻居中随机采样节点作为下一个访问节点,重复此过程,直到访问序列长度满足预设条件。假设图为【GNN笔记】Graph Embedding(二),其中,【GNN笔记】Graph Embedding(二)表示图中点的集合,【GNN笔记】Graph Embedding(二)表示图中边的集合,在RandomWalk中关键的问题是如何计算从节点【GNN笔记】Graph Embedding(二)跳转到【GNN笔记】Graph Embedding(二) 的概率【GNN笔记】Graph Embedding(二)
【GNN笔记】Graph Embedding(二)
其中,【GNN笔记】Graph Embedding(二)是图中所有边的集合,【GNN笔记】Graph Embedding(二) 是节点【GNN笔记】Graph Embedding(二)的 所有的出边的集合,【GNN笔记】Graph Embedding(二) 是节点【GNN笔记】Graph Embedding(二) 到节点【GNN笔记】Graph Embedding(二) 的边的权重,对于无向无权图【GNN笔记】Graph Embedding(二)

1.2 伪算法

  • deepwalk理论演示
Fig.1-1 Deepwalk的工作流程
  1. 图a展示了原始的用户行为序列
  2. 图b基于这些用户行为序列构建了物品相关图,可以看出,物品A,B之间的边产生的原因就是因为用户U1先后购买了物品A和物品B,所以产生了一条由A到B的有向边。如果后续产生了多条相同的有向边,则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后,全局的物品相关图就建立起来了。
  3. 图c采用随机游走的方式随机选择起始点,重新产生物品序列。
  4. 图d最终将这些物品序列输入word2vec模型,生成最终的物品Embedding向量。
  • 如下图所示,在给定节点【GNN笔记】Graph Embedding(二)时,计算节点【GNN笔记】Graph Embedding(二)同时出现的概率.

Q:那么如何给出节点【GNN笔记】Graph Embedding(二)的embedding represent?

  • window size 【GNN笔记】Graph Embedding(二) :以某个 节点为中心在随机游走链向前或向后的扩展的范围。正因为限制了范围,我们可以忽略窗口之外的链子上的节点,减少工作量(自己的猜测)。进而,限制了游走链的长度。。 如果对于一全连通图来说,如果不限制游走链的长度,那么概率恒为1,则没有意义了。

  • embedding size 【GNN笔记】Graph Embedding(二):

  • walks per vertex 【GNN笔记】Graph Embedding(二): 以顶点为root进行walk的次数

  • walk length 【GNN笔记】Graph Embedding(二):每次随机游走的长度

  • SkipGram:见博文 《skip-gram(含详细代码)》

  • 《skip-gram的上下文预测算法》
    在这里我理解是:在前面距离中我们要计算【GNN笔记】Graph Embedding(二)【GNN笔记】Graph Embedding(二)的窗口内出现的概率,与NLP中的skipgram类似,借鉴了该算法用于计算概率。

Fig.1-2 DeepWalk的伪算法

算法代码:deepwalk

二、LINE

Large-scale Information Network Embedding
提醒:该思想与度大的图没有关系,只是该方法在度大的图上效果比较好。
一阶和二阶相似性的案例

Fig.2-1 一阶相似和二阶相似的案例

提醒:DeepWalk在无向图上 作embedding,LINE既可以在无向图又可以在有向图中使用。

2.1 一阶相似性(First-order Proximity)

定义

两个顶点之间的⾃⾝相似(不考虑其他顶点)。 对于由边【GNN笔记】Graph Embedding(二)连接的每⼀对顶点,边上的权重【GNN笔记】Graph Embedding(二)表⽰u和v之间的相似度,如果在u和v之间没有观察到边,则它们的⼀阶相似度为0。⼀阶邻近通常意味着现实世界⽹络中两个节点的相似性。如上图中的节点6合节点7之间的权重很大(线条粗),则说明两者之间具有一阶相似度。

embedding

Fig.2-2 一阶相似性的推演

联合概率分布
定义了无向边【GNN笔记】Graph Embedding(二)的联合概率(见Eq.1),其中【GNN笔记】Graph Embedding(二)是节点【GNN笔记】Graph Embedding(二)低维空间向量表示(即嵌入表示)。也就是说,节点的嵌入表示经过一个sigmoid函数获得联合概率分布。
经验概率分布
【GNN笔记】Graph Embedding(二),其中【GNN笔记】Graph Embedding(二)表示节点【GNN笔记】Graph Embedding(二)和节点【GNN笔记】Graph Embedding(二)的权重,【GNN笔记】Graph Embedding(二)表示所有的权重之和。
距离–>KL散度
如果联合概率分布和经验概率分布的距离越小,则说明我们的嵌入表示越好。采用KL散度(见Fig2-2 右侧公式)表示两个函数的距离。
目标函数
我们要最小化距离公式(见公式Eq.2)。将联合概率分布和经验概率分布带入KL散度公式后(展开见Fig.2-2右下角)。在最后一行公式中第一部分是一个常数,第二部分中的【GNN笔记】Graph Embedding(二)是一个常数,因此简化后的距离公式见公式Eq.3。

2.2 二阶相似性(Second-order Proximity)

定义

⽹络中⼀对顶点【GNN笔记】Graph Embedding(二)之间的⼆阶相似度是它们邻近⽹络结构之间的相似性。 在数学上,设【GNN笔记】Graph Embedding(二)表⽰u与所有其他顶点的⼀阶相似度,则u和v之间的⼆阶相似度 由 【GNN笔记】Graph Embedding(二)【GNN笔记】Graph Embedding(二)决定。 如果没有顶点与u和v都连接,则u和v之间的⼆阶相似度为0。因为有些边观察不到等原因,⼀阶相似度不⾜以保存
⽹络结构。因此提出共享相似邻居的顶点倾向于彼此相似,即⼆阶相似度。 Fig.2-1,节点5和节点6虽然不共边但是具有共有的邻居节点1,节点2,节点3和节点4,说明两者具有二阶相似度.

embedding

如下图,对每个节点定义两个表示向量【GNN笔记】Graph Embedding(二)

Fig.2-3 二阶相似性的推演

条件概率公式
给定节点【GNN笔记】Graph Embedding(二)时求节点【GNN笔记】Graph Embedding(二)的概率=节点【GNN笔记】Graph Embedding(二)的向量表示乘以节点【GNN笔记】Graph Embedding(二)作为其他节点邻居的向量表示,再进行归一化操作(见公式Eq.4)。
举个栗子。如Fig.2-3右边所示,给定节点【GNN笔记】Graph Embedding(二)求节点【GNN笔记】Graph Embedding(二)的概率的时候,分母选择的时由节点【GNN笔记】Graph Embedding(二)指向的节点们【GNN笔记】Graph Embedding(二),而不包含【GNN笔记】Graph Embedding(二).从这也可以看出该算法可以用于有向图。
经验概率公式
【GNN笔记】Graph Embedding(二),其中【GNN笔记】Graph Embedding(二)表示节点【GNN笔记】Graph Embedding(二)和节点【GNN笔记】Graph Embedding(二)之间的权重【GNN笔记】Graph Embedding(二)表示节点【GNN笔记】Graph Embedding(二)出度。栗子如上图所示。
距离-优化目标
Eq.5表示两个概率分布地距离公式,公式中【GNN笔记】Graph Embedding(二)表示用来控制节点重要性地因子。当采用KL散度来求解距离两个概率公式的距离(KL散度公式如图上所示)会得到右下角最后一行公式。从中看到有一个与节点 【GNN笔记】Graph Embedding(二) 相关地变量【GNN笔记】Graph Embedding(二),其他变量都是同时与节点【GNN笔记】Graph Embedding(二)和节点【GNN笔记】Graph Embedding(二)相关,且不存在常数项尽量使优化目标都同时与两个节点相关。去掉度的影响。
假设【GNN笔记】Graph Embedding(二),可以使目标函数(见公式Eq.6)只与向量表示有关。

最小化后,选择【GNN笔记】Graph Embedding(二)作为图嵌入表示。

2.3 拼接一阶和二阶embedding

Fig.2-4 拼接

三、node2vec

相关佳文:

Fig.3-1 同质性和结构等价性案例

3.1 同质性(homophily )

在网络中,节点与其周围邻居节点的embedding应该是尽量相似的。在Fig.3-1中,在右上图中颜色相近的节点表示邻居关系,则他们的embedding是相似的。换个栗子,在Figure1中,节点【GNN笔记】Graph Embedding(二)与其相连的节点【GNN笔记】Graph Embedding(二)的embedding表达应该是接近的,这就是“同质性“的体现。

3.2 结构等价性(structural equivalence)

在网络中,节点的结构(所处的功能)相似的节点的embedding应该是尽量接近的。在Fig.3-1中,在右下图中蓝色的节点都是具有中心纽带作用的,其embedding应该是尽量相似的。再来个栗子,在Figure1中,节点【GNN笔记】Graph Embedding(二)和节点【GNN笔记】Graph Embedding(二)都是各自局域网络的中心节点,结构上相似,其embedding的表达也应该近似.

3.3 有策略地游走

这个名字也不知道正确否。

Fig.3-2 randwalk in node2vec或DFS和BFS之间的关系

在图中利用【GNN笔记】Graph Embedding(二)来控制偏向DFS或BFS.【GNN笔记】Graph Embedding(二)是转移概率。提醒,Fig.3-2中的Figure2中的【GNN笔记】Graph Embedding(二)不是指节点【GNN笔记】Graph Embedding(二)跳跃到节点【GNN笔记】Graph Embedding(二)的转移概率,而是指节点【GNN笔记】Graph Embedding(二)经过节点【GNN笔记】Graph Embedding(二)后跳转到节点【GNN笔记】Graph Embedding(二)的偏好,在求节点【GNN笔记】Graph Embedding(二)跳跃到节点【GNN笔记】Graph Embedding(二)的转移概率的时候,在偏好【GNN笔记】Graph Embedding(二)的基础上乘以权重【GNN笔记】Graph Embedding(二),即【GNN笔记】Graph Embedding(二)

3.4 算法伪代码

  • Dimensions 【GNN笔记】Graph Embedding(二):图嵌入地维度
  • walks per node 【GNN笔记】Graph Embedding(二): 每个节点随机游走的次数
  • walk length 【GNN笔记】Graph Embedding(二):游走地长度
  • context size 【GNN笔记】Graph Embedding(二):skipgram的窗口大小
  • Return 【GNN笔记】Graph Embedding(二):
  • In-out 【GNN笔记】Graph Embedding(二):
  • 【GNN笔记】Graph Embedding(二): 图G在【GNN笔记】Graph Embedding(二)下随机游走的概率?
Fig.3-3算法伪代码

优化目标
Fig.3-3中公式(1)中,红线表示在给定节点【GNN笔记】Graph Embedding(二)的情况下,其邻居节点【GNN笔记】Graph Embedding(二)出现的概率
提高效率
在上图右侧,提出了在一个比较长的游走链中,可以分别获得节点【GNN笔记】Graph Embedding(二)的邻居节点。

StochasticGradientDescent随机梯度下降

相关博文

3.5 DFS和BFS的关系

BFS应该反映了结构性,DFS反应了同质性.

Fig.3-4 DFS和BFS的关系

3.6 边的embedding

Fig.3-5 边的嵌入方式

四、Struc2vec

如下图中节点【GNN笔记】Graph Embedding(二)和节点【GNN笔记】Graph Embedding(二)没有直接连边,其邻居也不相连,但是具有结构相似性。考虑通过这种结构相似性,进行embedding表示。

Fig.4-1 网络中节点的结构性

4.1 节点k-hop距离

节点的k-hop距离是一个迭代公式。k-1的hop距离+两个节点k-hop邻居的度距离。这里的度距离是采用DTW的方式求解的。

Fig.4-2节点k-hop距离

4.2 DTW距离

Fig.4-3 DTW距离演示图

DTW的思想和代码:见《时间序列的相似性》

4.3 构建多层加权图

猜测建立多层图的原因:

Fig.4-4 建立多层图的原因

对于Fig.4-2中的以节点【GNN笔记】Graph Embedding(二)为中心的图,会得到

0-hop的节点集:【GNN笔记】Graph Embedding(二)
1-hop的节点集:【GNN笔记】Graph Embedding(二)
2-hop的节点集:【GNN笔记】Graph Embedding(二)
为了更清晰的表达,将其如Fig.4-4中所变化表示。这样就建立一个节点的0-hop层,1-hop层,2-hop层。显然,对于每个的节点建立自己的一个多层hop图是不科学的。将每个节点的多层hop图融合。因此,每个hop层都要包含所有的节点至于节点之间的权重(包括层内边的权重和层间边的权重)如何计算呢???
构建方法

  1. 建立k层多重图
  2. 确定层内连边和层间连边的权重(公式间Fig.4-5)
  3. 可以构建有向的图。
Fig.4-5 多层加权hop图的构建方法

4.4 顶点采样序列

Fig.4-6 random walk的方法

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 SDNE框架

如图Fig.5-1所示,模型的

  • 输入: 是节点的向量表示(见黄色高亮部分), 【GNN笔记】Graph Embedding(二)在这里表示节点【GNN笔记】Graph Embedding(二)与其他节点的邻居关系
  • encoder: 是编码部分(见绿色高亮部分),【GNN笔记】Graph Embedding(二),对于所有的节点编码部分的参数共享
  • 嵌入表示: 【GNN笔记】Graph Embedding(二)(见墨绿部分)
  • decoder: 是解码部分(见橙色高亮),【GNN笔记】Graph Embedding(二)对于所有的节点解码部分的参数共享
  • 输出:是预测值(见粉色高亮部分), 【GNN笔记】Graph Embedding(二) ,且与输入值的维度完全相同

优化目标

二阶相似度
显然,如上流程图红色所示,【节点固有的邻居关系】与【节点预测的邻居关系】越接近则说明我们的【压缩表示】越好,则我们就有助于完成图嵌入这项工作。因此,我们求输入向量和输出向量的距离。

六、总结

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
扎眼的阳光的头像扎眼的阳光普通用户
上一篇 2022年5月22日
下一篇 2022年5月22日

相关推荐