图嵌入 Node2Vec
文章目录
- 图嵌入之 Node2Vec
-
- 1 两个概念
- 2 两种节点采样方法
- 3 Node2Vec 中的二阶 Random Walk
-
- 3.1 Random Walks 的定义
- 3.2 搜索偏置 α\\alphaα
- 4 二阶 Random Walk 的优势
- 5 算法步骤
图嵌入之 Node2Vec
论文地址 https://arxiv.org/pdf/1607.00653.pdf
对 Random Walk 中随机地选择游走序列进行了改进,别的地方与 Deep Walk 大致相同
1 两个概念
-
homophily:同质性,越是相邻的节点同质的趋势更大
-
structural equivalence:结构相似性,如 Figure 1 中 u 节点和 S6S_6S6 节点在结构上很相似
2 两种节点采样方法
-
广度优先采样BFS:采样的节点序列更能挖掘结构相似性(微观)
-
深度优先采样DFS:采样的节点序列更能挖掘同质性(宏观)
3 Node2Vec 中的二阶 Random Walk
3.1 Random Walks 的定义
设 cic_ici 表示随机游走中的第 i 个节点,cic_ici 的选择遵循如下分布:
πvx\\pi_{vx}πvx 表示节点 vvv 和 xxx 之间未归一化的过渡概率,ZZZ 是进行归一化的常数
即从当前节点 v 到下一个节点 x 的条件概率等于 πvxZ\\frac{\\pi_{vx}}{Z}Zπvx,πvx\\pi_{vx}πvx 怎么算往下看
3.2 搜索偏置 α\\alphaα
定义两个参数 ppp 和 qqq (超参数)来引导随机序列的选择,
返回参数 ppp(Return parameter):控制从一个节点回退一步的似然,在 Figure 2中,设 t 为走过的上一个节点,v 为当前节点,用 α=1/p\\alpha=1/pα=1/p 表示从 v 到 t 的权重
区分似然(likelihood)与 概率(probability)
- 对于联合概率函数 P(yi^∣xi,θ)P(\\hat{y_i}|x_i,θ)P(yi^∣xi,θ) 而言。
- 概率探究的是自变量与因变量之间的关系,即 θ\\thetaθ 已知,在不同的特征向量 xix_ixi 下,得到 yi^\\hat{y_i}yi^ 的可能性。
- 似然探究的是参数向量与因变量之间的关系,即 xix_ixi 已知,在不同的参数向量 θ\\thetaθ 下,得到 yi^\\hat{y_i}yi^ 的可能性。
进出参数 qqq(In-out parameter):若 q>1q > 1q>1,随机游走算法会偏向于选择,当前节点局部范围(local view)内的节点,类似 BFS ;若 q<1q < 1q<1,随机游走算法倾向于选择更深一步(further away)的节点,类似 DFS
基于边的权重来对下一个节点进行采样,定义边的权重 πvx=αpq(t,x)∗wvx\\pi_{vx} = \\alpha_{pq}(t,x)*w_{vx}πvx=αpq(t,x)∗wvx,当前节点到下一个节点的转移概率由 α\\alphaα 进行加权,其中 α\\alphaα 定义为:
dtxd_{tx}dtx 表示节点 t 到节点 x 的最短路径长度
4 二阶 Random Walk 的优势
快!