DeepWalk原理介绍

与词嵌入类似，图嵌入基本理念是基于相邻顶点的关系，将目的顶点映射为稠密向量，以数值化的方式表达图中的信息，以便在下游任务中运用。

Word2Vec根据词与词的共现关系学习向量的表示，DeepWalk受其启发。它通过随机游走的方式提取顶点序列，再用Word2Vec模型根据顶点和顶点的共现关系，学习顶点的向量表示。可以理解为用文字把图的内容表达出来，如下图所示。

DeepWalk训练图表示的整个过程大致可以分为2步：

• 随机游走提取顶点序列
• 使用skip-gram学习顶点嵌入

训练时采用层次Softmax（Hierarchical Softmax）优化算法，避免计算所有词的softmax。

Node2vec原理

DeepWalk不适用于有权图，它无法学习边上的权重信息。Node2Vec可以看作DeepWalk的扩展，它学习嵌入的过程也可以分两步：

• 二阶随机游走（2ndorderrandomwalk）
• 使用skip-gram学习顶点嵌入

可以看到与DeepWalk的区别就在于游走的方式，在二阶随机游走中，转移概率 ${\pi }_{vx}$ 受权值 $w_{vx}$ 影响（无权图中$w_{vx}$ 为1）：
$${\pi }_{vx}={\alpha }_{pq}(t,x)\cdot w_{vx}$$

$${\alpha }_{pq}(t,x)=\{\begin{array}{rl}\frac{1}{p},& if{d}_{tx}=0\\ 1,& if{d}_{tx}=1\\ \frac{1}{q},& if{d}_{tx}=2\end{array}$$

t 代表上一个节点，v 代表当前节点，x 代表下一个准备访问的节点。 $d_{tx}$代表上一个节点与待访问节点的距离。 $d_{tx}=0$ 代表从当前节点返回上一个访问节点，即“t->v->t”。

算法通过p、q两个超参数来控制游走到不同顶点的概率。

• q：被称作进出参数， 控制“向内”还是“向外”游走。若q>1，倾向于访问与 t 接近的顶点，若 q<1 则倾向于访问远离 t 的顶点。
• p：被称为返回参数，控制重复访问刚刚访问过的顶点的概率。若设置的值较大，就不大会刚问刚刚访问过的顶点。若设置的值较小，那就可能回路返回一步。

p,q的大小可以控制算法是偏向于DFS还是BFS。p越小，随机游走回节点t的可能性越大，算法倾向于表达结构性；q越小，随机游走到远方的可能性越大，网络倾向于表达同质性。

也即，BFS偏向于表达结构性，DFS倾向于表达同质性。

这里解释一下，网络的“同质性”指的是距离相近节点的embedding应该尽量近似，如图，节点u与其相连的节点s1、s2、s3、s4的embedding表达应该是接近的，这就是“同质性“的体现。

“结构性”指的是结构上相似的节点的embedding应该尽量接近，图中节点u和节点s6都是各自局域网络的中心节点，结构上相似，其embedding的表达也应该近似，这是“结构性”的体现。

总的来说，node2vec是一种综合考虑DFS邻域和BFS邻域的graph embedding方法。简单来说，可以看作是deepwalk的一种扩展，是结合了DFS和BFS随机游走的deepwalk。

Node2vec实现代码详解

Node2vec的算法分为如下几步：

1. 生成整图的转移概率矩阵W， 生成过程中要考虑(preNode, curNode, [curNode所有邻居dstNode的跳转概率] )三节跳跃
2. 基于W生成节点游走序列。会采用Alias Sample采样。
3. 对序列采用word2vec训练，得到node embedding。可能采用负采样训练方法。

伪代码如下：

维度d，每个节点生成r个长度为l的语料序列。上下文context长度为k。
start node : u
初始节点u和它的邻域表示：{u,s4,s5,s6,s8,s9}

u的邻域：$N_s(u)=(s_4,s_5,s_6,s_8,s_9)$

walk是节点u生成的随机游走的样本结果集。为了便于说明，上下两个伪代码框分别从0开始编号。

第5行到第8行对每个顶点进行r轮游走，生成长度为l的顶点序列，保存在集合walks中。

第9行是做梯度下降优化。推荐使用负采样

node2vecWalk部分的第1步是初始化序列walk，只需注意此时walk已经包含了两个元素[pre, curr]，然后进行l步n2v游走。第3行获取walk中上一步的节点作为当前节点curr，…剩下就没有难度了。

注意，在GetNeighbors中，对于当前节点curr，可以对所有邻居采样，再计算。

代码写得很清楚，只需要注意构建图的时候，对每个节点先走一步，产生(prevNodeId ,currentNodeId) 这个itempair，在调用node2vecWalk，对currentNodeId走l轮，产生(item1,item2,item3…)

---

具体源码如下：

这部分为Alias Sample采样算法

import numpy as np
def alias_setup(probs):'''Compute utility lists for non-uniform sampling from discrete distributions.Refer to https://hips.seas.harvard.edu/blog/2013/03/03/the-alias-method-efficient-sampling-with-many-discrete-outcomes/for details'''K = len(probs)q = np.zeros(K)    #保存样本概率J = np.zeros(K, dtype=np.int)  #保存补1的事件smaller = []larger = []for kk, prob in enumerate(probs):q[kk] = K*probif q[kk] < 1.0:smaller.append(kk)else:larger.append(kk)while len(smaller) > 0 and len(larger) > 0:small = smaller.pop()large = larger.pop()J[small] = largeq[large] = q[large] + q[small] - 1.0  #q[large]-(1-q[small])if q[large] < 1.0:smaller.append(large)else:larger.append(large)return J, q    #（alias，prab）def alias_draw(J, q):'''Draw sample from a non-uniform discrete distribution using alias sampling.'''K = len(J)kk = int(np.floor(np.random.rand()*K))if np.random.rand() < q[kk]:return kkelse:return J[kk]

这部分为真正的源码。

import numpy as np
import networkx as nx
import random
from gensim.models import word2vecclass Graph():def __init__(self, nx_G, is_directed, p, q):self.G = nx_Gself.is_directed = is_directedself.p = pself.q = qdef node2vec_walk(self, walk_length, start_node):'''Simulate a random walk starting from start node.'''G = self.Galias_nodes = self.alias_nodesalias_edges = self.alias_edgeswalk = [start_node]while len(walk) < walk_length:cur = walk[-1]cur_nbrs = sorted(G.neighbors(cur))if len(cur_nbrs) > 0:# 如果序列中仅有一个结点，即第一次游走# alias_nodes中保存了alias_setup的[alias, accept]，通过alias_draw返回采样的下一个索引号if len(walk) == 1:walk.append(cur_nbrs[alias_draw(alias_nodes[cur][0], alias_nodes[cur][1])])else:# 当前游走结点的前一个结点和下一个节点prev = walk[-2]# 使用alias_edges中记录的[alias, accept]，来采样邻居中的下一个节点next = cur_nbrs[alias_draw(alias_edges[(prev, cur)][0], alias_edges[(prev, cur)][1])]walk.append(next)else:breakreturn walkdef simulate_walks(self, num_walks, walk_length):'''Repeatedly simulate random walks from each node.'''G = self.Gwalks = []nodes = list(G.nodes())# nodes采样一次为一个epoch，此处就是num_walks个epochprint('Walk iteration:')for walk_iter in range(num_walks):print(str(walk_iter+1), '/', str(num_walks))random.shuffle(nodes)for node in nodes:walks.append(self.node2vec_walk(walk_length=walk_length, start_node=node))return walksdef get_alias_edge(self, src, dst):'''Get the alias edge setup lists for a given edge.:return alias_setup(): 在上一次访问顶点 t ，当前访问顶点为 v 时到下一个顶点 x 的未归一化转移概率。:param src:  随机游走序列种的上一个结点:param dst:  当前结点参数p控制重复访问刚刚访问过的顶点的概率。若p较大，则访问刚刚访问过的顶点的概率会变低。参数q控制着游走是向外还是向内：若q>1，随机游走倾向于访问和上一次的t接近的顶点(偏向BFS)；若q<1，倾向于访问远离t的顶点(偏向DFS)'''G = self.Gp = self.pq = self.qunnormalized_probs = []for dst_nbr in sorted(G.neighbors(dst)):if dst_nbr == src:   # 如果是要返回上一个节点unnormalized_probs.append(G[dst][dst_nbr]['weight']/p)elif G.has_edge(dst_nbr, src):   # 如果接下来访问的节点与src的距离与当前节点相等unnormalized_probs.append(G[dst][dst_nbr]['weight'])else:unnormalized_probs.append(G[dst][dst_nbr]['weight']/q)norm_const = sum(unnormalized_probs)normalized_probs =  [float(u_prob)/norm_const for u_prob in unnormalized_probs]return alias_setup(normalized_probs)def preprocess_transition_probs(self):'''Preprocessing of transition probabilities for guiding the random walks.用于引导随机游走的预处理，得到马尔可夫转移概率矩阵。'''G = self.Gis_directed = self.is_directedalias_nodes = {}# G.neighbors(node) 与顶点相邻的所有顶点，更方便更快的访问adjacency字典用: G[cur]for node in G.nodes():# 根据邻居节点的权重，计算转移概率unnormalized_probs = [G[node][nbr]['weight'] for nbr in sorted(G.neighbors(node))]norm_const = sum(unnormalized_probs)# 计算当前节点到邻居节点的转移概率，其实就是权重归一化normalized_probs =  [float(u_prob)/norm_const for u_prob in unnormalized_probs]# 设置alias table，保存每个节点的accept[i]和alias[i]，为后面alias采样做准备。alias_nodes[node] = alias_setup(normalized_probs)alias_edges = {}triads = {}# 保存每条边的accept[i]和alias[i]if is_directed:for edge in G.edges():alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])else:for edge in G.edges():alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])   # 随机游走序列种的上一个结点 当前节点alias_edges[(edge[1], edge[0])] = self.get_alias_edge(edge[1], edge[0])self.alias_nodes = alias_nodesself.alias_edges = alias_edgesprint(self.alias_nodes)print(self.alias_edges)returndef alias_setup(probs):'''Compute utility lists for non-uniform sampling from discrete distributions.Refer to https://hips.seas.harvard.edu/blog/2013/03/03/the-alias-method-efficient-sampling-with-many-discrete-outcomes/for details:param probs: 指定的采样结果概率分布列表。期望按这个概率列表来采样每个随机变量X。:return J: alias[i]表示第i列中不是事件i的另一个事件的编号。:return p: accept[i]表示事件i占第i列矩形的面积的比例。'''K = len(probs)# q表示：accept数组q = np.zeros(K)# J表示：alias数组J = np.zeros(K, dtype=np.int)# Alias方法将整个概率分布压成一个 1*N 的矩形，每个事件转换为矩形中的面积。# 将面积大于1的事件多出的面积补充到面积小于1对应的事件中，以确保每一个小方格的面积为1，# 同时，保证每一方格至多存储两个事件。smaller = [] # 面积小于1的事件larger = []  # 面积大于1的事件for kk, prob in enumerate(probs):q[kk] = K*probif q[kk] < 1.0:smaller.append(kk)else:larger.append(kk)while len(smaller) > 0 and len(larger) > 0:small = smaller.pop()large = larger.pop()J[small] = large# 其实是 q[large] - (1.0 - q[small])，把大的削去(1.0 - q[small])填充到小的上q[large] = q[large] + q[small] - 1.0# 大的剩下的面积，放到下一轮继续倒腾if q[large] < 1.0:smaller.append(large)else:larger.append(large)return J, qdef alias_draw(J, q):'''Draw sample from a non-uniform discrete distribution using alias sampling.参考：https://zhuanlan.zhihu.com/p/54867139:param q: accept数组，表示事件i占第i列矩形的面积的比例；:param J: alias数组，表示alias矩形的第i列中不是事件i的另一个事件的编号，也就是填充的那一列的序号；生成一个随机数 kk in [0, K]，另一个随机数 x in [0,1],如果 x < accept[kk]，表示接受事件kk，返回kk，否则拒绝事件kk，返回alias[kk]'''K = len(J)kk = int(np.floor(np.random.rand()*K))if np.random.rand() < q[kk]:return kkelse:return J[kk]def read_graph(input_file, directed):'''Reads the input network in networkx.'''if directed:G = nx.read_edgelist(input_file, delimiter=",", nodetype=int, data=(('weight',float),), create_using=nx.DiGraph())else:G = nx.read_edgelist(input_file, delimiter=",", nodetype=int, create_using=nx.DiGraph())for edge in G.edges():G[edge[0]][edge[1]]['weight'] = 1if not directed:G = G.to_undirected()return Gdef learn_embeddings(walks):'''Learn embeddings by optimizing the Skipgram objective using SGD.'''walks = [list(map(str, walk)) for walk in walks]print(walks)
#     model = word2vec.Word2Vec(walks, vector_size=64, window=3, min_count=0, sg=1, workers=1, epochs=5)# model.save_word2vec_format(args.output)#model.wv.save_word2vec_format(args.output, binary=False)returndef main(directed):'''Pipeline for representational learning for all nodes in a graph.'''nx_G = read_graph(r"C:\Users\Administrator\TensorFlow\game.csv", directed)print(list(nx_G.edges(data=True)), list(nx_G))for node in nx_G.neighbors(2):print(node)G = Graph(nx_G, False, 1, 2)G.preprocess_transition_probs()walks = G.simulate_walks(5, 3)learn_embeddings(walks)if __name__ == "__main__":main(directed = False)

Alias Sample Method 别名采样算法

更详细的可以观看如下blog：
Darts, Dice, and Coins: Sampling from a Discrete Distribution

在随机游走的过程中，假设已经游走到当前节点，则下一步的游走要参考下面的公式。
$${\pi }_{vx}={\alpha }_{pq}(t,x)\cdot w_{vx}$$

则对于不同的节点，被采样到的概率是不一样的，因此需要采用采样算法。Alias Sample算法是一种时间复杂度为O(1)的算法，因此特别适合大规模的网络游走情况。

构建Alias Table

每个概率乘以四（事件数）。

然后拼凑使每列值为 1，并保证每列最多只包含两个事件。

至此整个方法大功告成。

Alias Method具体算法如下：

1. 按照上面说的方法，将整个概率分布拉平成为一个1*N的长方形即为Alias Table，构建上面那张图之后，储存两个数组，一个里面存着第i列对应的事件ii矩形站的面积百分比【也即其概率】，上图的话数组就为$Prab[2/3,1/1,1/3,1/3]$，另一个数组里面储存着第i列不是事件i的另外一个事件的标号，像上图就是Alias[2 NULL 1 1]
   2.产生两个随机数，第一个产生1~N 之间的整数i，决定落在哪一列。扔第二次骰子，0~1之间的任意数，判断其与Prab[i]大小，如果小于Prab[i]，则采样i，如果大于Prab[i]，则采样Alias[i]

读者可以采样自己运行一下Alias算法，体会一下，代码在上面。