Node2vec
本文转载自 【Graph Embedding】node2vec：算法原理，实现和应用 - 浅梦的文章 - 知乎
https://zhuanlan.zhihu.com/p/56542707
前面介绍过基于DFS邻域的DeepWalk和基于BFS邻域的LINE。
node2vec是一种综合考虑DFS邻域和BFS邻域的Graph Embedding方法。简单来说，可以看作是deepwalk的一种扩展，是结合了DFS和BFS随机游走的deepwalk。
node2vec算法原理
优化目标
设是将顶点
映射为embedding向量的映射函数，对于图中每个顶点
，定义
为通过采样策略
采样出的顶点
的近邻点集合。
node2vec优化的目标是给定每个顶点条件下，令其近邻顶点（如何定义近邻顶点很重要）出现的概率最大。
为了将上述最优化问题可解，文章提出两个假设：
-
条件独立性假设
假设给定源顶点下，其近邻顶点出现的概率与近邻集合中其余顶点无关。
-
特征空间对称性假设
这里是说一个顶点作为源顶点和作为近邻顶点的时候共享同一套embedding向量。(对比LINE中的2阶相似度，一个顶点作为源点和近邻点的时候是拥有不同的embedding向量的)
在这个假设下，上述条件概率公式可以表示为
根据以上两个假设条件，最终的目标函数表示为：
由于归一化因子
的计算代价高，所以采用负采样技术优化。
顶点序列采样策略
node2vec依然采用随机游走的方式获取顶点的近邻序列，不同的是node2vec采用的是一种有偏的随机游走。
给定当前顶点，访问下一个顶点
的概率为:
其中是顶点
和顶点
之间的未归一化转移概率，
是归一化常数。
node2vec引入两个超参数和
来控制随机游走的策略，假设当前随机游走经过边
到达顶点
，设
，
是顶点
和
之间的边权，
考虑超参数和
对游走策略的影响：
-
Return parameter, p
-
In-out parameter, q
学习算法
采样完顶点序列后，剩下的步骤就和deepwalk一样了，用word2vec去学习顶点的embedding向量。 值得注意的是node2vecWalk中不再是随机抽取邻接点，而是按概率抽取，node2vec采用了Alias算法进行顶点采样。
Alias Method:时间复杂度O(1)的离散采样方法
node2vec算法伪代码
node2vecWalk
通过上面的伪代码可以看到，node2vec和deepwalk非常类似，主要区别在于顶点序列的采样策略不同，所以这里我们主要关注node2vecWalk的实现。
由于采样时需要考虑前面2步访问过的顶点，所以当访问序列中只有1个顶点时，直接使用当前顶点和邻居顶点之间的边权作为采样依据。 当序列多余2个顶点时，使用文章提到的有偏采样。
作者：浅梦
链接：https://zhuanlan.zhihu.com/p/56542707
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
def node2vec_walk(self, walk_length, start_node):
G = self.G
alias_nodes = self.alias_nodes
alias_edges = self.alias_edges
walk = [start_node]
while len(walk) < walk_length:
cur = walk[-1]
cur_nbrs = list(G.neighbors(cur))
if len(cur_nbrs) > 0:
if len(walk) == 1:
walk.append(cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])])
else:
prev = walk[-2]
edge = (prev, cur)
next_node = cur_nbrs[alias_sample(alias_edges[edge][0],alias_edges[edge][1])]
walk.append(next_node)
else:
break
return walk
构造采样表
preprocess_transition_probs分别生成alias_nodes和alias_edges，alias_nodes存储着在每个顶点时决定下一次访问其邻接点时需要的alias表（不考虑当前顶点之前访问的顶点）。
alias_edges存储这在前一个访问顶点为，当前访问顶点为
时到下一个顶点
的未归一化转移概率
def get_alias_edge(self, t, v):
G = self.G
p = self.p
q = self.q
unnormalized_probs = []
for x in G.neighbors(v):
weight = G[v][x].get('weight', 1.0)# w_vx
if x == t:# d_tx == 0
unnormalized_probs.append(weight/p)
elif G.has_edge(x, t):# d_tx == 1
unnormalized_probs.append(weight)
else:# d_tx == 2
unnormalized_probs.append(weight/q)
norm_const = sum(unnormalized_probs)
normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]
return create_alias_table(normalized_probs)
def preprocess_transition_probs(self):
G = self.G
alias_nodes = {}
for node in G.nodes():
unnormalized_probs = [G[node][nbr].get('weight', 1.0) for nbr in G.neighbors(node)]
norm_const = sum(unnormalized_probs)
normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]
alias_nodes[node] = create_alias_table(normalized_probs)
alias_edges = {}
for edge in G.edges():
alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])
self.alias_nodes = alias_nodes
self.alias_edges = alias_edges
return
node2vec应用
使用node2vec在wiki数据集上进行节点分类任务和可视化任务。 wiki数据集包含 2,405 个网页和17,981条网页之间的链接关系，以及每个网页的所属类别。 通过简单的超参搜索，这里使用p=0.25,q=4的设置。
G = nx.read_edgelist('../data/wiki/Wiki_edgelist.txt',create_using=nx.DiGraph(),nodetype=None,data=[('weight',int)])
model = Node2Vec(G,walk_length=10,num_walks=80,p=0.25,q=4,workers=1)
model.train(window_size=5,iter=3)
embeddings = model.get_embeddings()
evaluate_embeddings(embeddings)
plot_embeddings(embeddings)
分类任务
'micro-F1': 0.6548856548856549,
'macro-F1': 0.5725043917959665
这个结果相比于DeepWalk和LINE是有提升的。
可视化
这个结果相比于DeepWalk和LINE可以看到不同类别的分布更加分散了。
最后补充一个node2vec在业界的应用介绍
