概述
Node2Vec 图嵌入算法是一种综合考虑节点 BFS 邻域和 DFS 邻域的图嵌入方法,通过有偏差的二阶随机游走产生游走序列,将这些序列视为文本,然后使用 Word2Vec 算法的 Skip-gram 模型训练得到图中节点的嵌入向量。Node2Vec 算法是由斯坦福大学的 Aditya Grover 和 Jure Leskovec 于 2016 年提出的。
算法的相关资料如下:
- A. Grover, J. Leskovec, node2vec: Scalable Feature Learning for Networks (2016)
- B. Perozzi, R. Al-Rfou, S. Skiena, DeepWalk: Online Learning of Social Representations (2014)
基本概念
节点相似性
网络中节点的相似性一般有两种:同质性(Homophily)和结构等效性(Structural Equivalence)。同质性强调节点间的连接关系,而结构等效性仅考虑节点的局部拓扑结构而非连接性,具有结构等效性或相似性的节点在网络中也许相距较远。
同质性
同质性是指节点的邻居通常与节点有类似的属性特征。典型地,在社交网络中,一个用户(节点)与其好友(邻居节点)往往有类似的兴趣、年龄等。有同质性的节点通常在网络中位置比较靠近。基于同质性的图嵌入算法一般会将属于同一社区的节点嵌入到彼此靠近的位置。上图中,节点 u、s1、s2、s3 和 s4 位于同一社区,它们具有同质性。
结构等效性
一般而言,结构等效性是指两个节点的邻域拓扑结构是同构或对称的。考虑结构等效性时要注意两个问题:首先,现实网络中出现完全结构等效的两个节点的频率并不高,更多考虑的是结构相似性(Structural Similarity);其次,通常考虑的邻域越大,两个节点的结构相似性越低。上图中,节点 u、v 在各自的社区中都位于中心位置,它们具有相当程度的结构等效性。
BFS 和 DFS
在图论中,广度优先搜索(Breadth First Search,简写为 BFS)指的是从某个顶点出发,由浅及深地遍历相邻节点的方式。它会先把前一层的邻居都遍历完毕后,才遍历之后一层的邻居。例如图上的 K 邻查询就是典型的 BFS 操作。
相对于 BFS 的横向(广度)优先搜索而言,DFS(Depth First Search,简写为 DFS)则是纵向(深度)优先搜索,它会从当前节点出发先进行深度探索,在到达最大限定的搜索深度或当前路径上无路可寻时才折返回到上一层继续搜索,直到找到符合搜索终止条件的点或边,或遍历完全图。
二阶随机游走
在经典随机游走中,默认每条边被经过的可能性相同(详见《完全随机游走》一章),节点每次选择的下一步节点不受之前经过的节点影响。而所谓二阶随机游走(Second-order Random Walk, 简写为 RW2),是指选择下一步节点时,还要考虑之前已访问过的节点。
Node2Vec 游走
Node2Vec 随机游走引入了两个参数 p
和 q
来控制游走更偏向于 BFS 还是 DFS。假设节点从 t
走到 v
且 v
有邻居节点 x
,Node2Vec 游走根据 t
、x
间的最短距离 d
并使用参数 p
、q
对原始边权重进行修正:
- 当
d = 0
(即x
为t
本身),修正值为1/p
。x
为t
本身意味着节点往回走,因此p
参数又称为return
参数;p
的值越大,往回走的概率越小。 - 当
d = 1
(如下图点x1
),不进行修正。x1
与t
同为v
的一步邻居,若下一步走向x1
意味着节点没有走远。 - 当
d = 2
(如下图点x2
),修正值为1/q
。下一步选择x2
意味着节点向远处游走,因此q
参数又称为in-out
参数;q > 1
代表倾向在同级游走,q < 1
代表倾向向远处游走。
用上述修正值与原始边权重相乘,就得到修正后的权重,再将各条边的权重进行归一化处理,即可得到节点下一步沿各条邻边游走的概率。
偏向 BFS 邻域游走时,最终的嵌入结果会更体现节点的结构等效性,因为此时的游走过程相当于探索节点自身周围的环境(拓扑结构)。偏向 DFS 邻域游走时,最终的嵌入结果会更体现节点的同质性,因为此时节点向外游走,相当于在探索自身所处社区内的环境。
节点的嵌入向量表示
B. Perozzi 等人于 2014 年提出 DeepWalk 图嵌入算法时,首次将广泛应用于自然语言处理(NLP)领域的深度学习技术应用在网络分析中。DeepWalk 将语言建模泛化为通过随机游走探索图的过程,将游走序列视为一种特殊的短句或短语。类似地,Node2Vec 使用 Skip-gram 语言模型和 SGD 训练游走序列得到节点在向量空间的表示,并采用负采样(Negative Sampling)等技术进行优化。
关于 Skip-gram 模型,请阅读文档—— Skip-gram 模型 和 Skip-gram 模型优化
特殊处理
孤点、不连通图
孤点没有邻居节点,因此无法游走到其他节点;如果孤点有自环边,只能沿着自环边进行游走。非孤点的游走路径上不会出现孤点。
节点只会在自身所处的连通分量内进行游走。
自环边
节点可以沿自环边进行游走。
有向边
Node2Vec 图嵌入算法的结果与边的方向无关。
命令和参数配置
- 命令:
algo(node2vec)
params()
参数配置如下:
名称 | 类型 |
默认值 |
规范 |
描述 |
---|---|---|---|---|
ids 或 uuids | []_id 或 []_uuid |
/ | / | 起点的 ID 或 UUID;忽略表示选择全部点 |
walk_length | int | 1 | >=1 | 每次游走的深度,即游走经过的节点数量 |
walk_num | int | 1 | >=1 | 游走的次数 |
p | float | 1 | >0 | return 参数,值越大,向回走的概率越小 |
q | float | 1 | >0 | in-out 参数,代表能向远处走的概率;>1 代表倾向在同级游走,<1 代表倾向向远处游走 |
edge_schema_property | []@<schema>?.<property> |
/ | 数值类的边属性,需LTE | 边权重的一个或多个属性名称,带不带 schema 均可;节点只会沿着带有这些属性的边游走,且经过这些边的概率与边权重成正比;如果边带有多个指定属性,权重值为这些属性值的和;忽略表示所有边权重为 1 |
window_size | int | / | >=1 | 采样窗口大小,在窗口中心左边和右边各采样 window_size 个节点 |
dimension | int | / | >=1 | 节点嵌入向量的维度 |
learning_rate | float | / | (0,1) | 初始学习率,每次迭代后学习率都会降低,直至减到 min_learning_rate |
min_learning_rate | float | / | (0,learning_rate ) |
最小学习率 |
min_frequency | int | / | >=0 | 出现次数小于该值的节点将被模型舍弃,<=1 时保留全部节点 |
sub_sample_alpha | float | / | / | 二次采样策略中的阈值,小于等于 0 时不进行二次采样 |
resolution | int | / | >=1 | 如 10、100 |
neg_num | int | / | >=0 | 负采样时的负样本数量,建议 0~10 |
loop_num | int | / | >=1 | 训练迭代轮数 |
buffer_size | int | 1000 | / | 开始训练前需完成的随机游走次数,<0 代表需等待全部随机游走完成 |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
示例:在全图进行 Node2Vec 图嵌入
algo(node2vec).params({
walk_length: 3,
walk_num: 2,
p: 1,
q: 1,
window_size: 5,
dimension: 5,
learning_rate: 0.025,
min_learning_rate: 0.00025,
min_frequency: -1,
sub_sample_alpha: -1,
resolution: 2,
neg_num: 0,
loop_num: 2,
limit: -1
}) as results
return results
算法执行
任务回写
1. 文件回写
配置项 |
各列数据 |
---|---|
filename | _id ,embedding_result |
2. 属性回写
算法不支持属性回写。
3. 统计回写
算法无统计值。
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 各点及其图嵌入结果 | _uuid , embedding_result |
流式返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 各点及其图嵌入结果 | _uuid , embedding_result |
实时统计
算法无统计值。